Crate rsor

source ·
Expand description

Reusable slice of references.

Motivation

The Slice data structure from this crate can be used to solve a very specific problem:

  • We want to create a slice of references (a.k.a. &[&T] or &mut [&mut T]) with a length not known at compile time.

AND

  • Multiple invocations should be able to use incompatible lifetimes (all references within each single invocation must of course have a common lifetime).

AND

  • The allocated memory should be reusable for multiple invocations.

The hard part is fulfilling all three requirements at the same time. If we allow either one of them to be broken, this problem can be solved easily with built-in tools:

  • If the number of references is known at compile time, the built-in array type (a.k.a. [&T; N] or [&mut T; N]) can (and should!) be used. No dynamic memory at all has to be allocated.

  • If all used lifetimes are compatible, a single Vec<&T> can be used and reused.

  • If we don’t care about allocating memory at each invocation, a fresh Vec<&T> can be used each time, allowing for different (and incompatible) lifetimes.

The following example shows the problem with incompatible lifetimes. The number of references in this example is known at compile time, but let’s just pretend it’s not.

ⓘ
fn print_slice(slice: &[&str]) { for s in slice { print!("<{}>", s); } println!(); }

let mut vec = Vec::<&str>::with_capacity(2);

{
    let one = String::from("one");
    let two = String::from("two");
    vec.push(&one);
    vec.push(&two);
    print_slice(&vec);
    vec.clear();
}

let three = String::from("three");
vec.push(&three);
print_slice(&vec);

This example cannot be compiled, the compiler complains:

error[E0597]: `one` does not live long enough
   |
8  |     vec.push(&one);
   |              ^^^^ borrowed value does not live long enough
...
12 | }
   | - `one` dropped here while still borrowed
...
15 | vec.push(&three);
   | --- borrow later used here

For more information about this error, try `rustc --explain E0597`.

Even though the Vec<&str> is emptied at the end of the inner scope, it still “remembers” the lifetime of its previous inhabitants and doesn’t allow future references to have incompatible lifetimes.

The problem can be solved with the Slice type from this crate:

use rsor::Slice;

let mut reusable_slice = Slice::<str>::with_capacity(2);

{
    let one = String::from("one");
    let two = String::from("two");

    let strings = reusable_slice.fill(|mut v| {
        v.push(&one);
        v.push(&two);
        v
    });
    print_slice(strings);
}

let three = String::from("three");

let strings = reusable_slice.fill(|mut v| {
    v.push(&three);
    v
});
print_slice(strings);
assert_eq!(reusable_slice.capacity(), 2);

This example compiles successfully and produces the expected output:

<one><two>
<three>

Note that the capacity has not changed from the initial value, i.e. no additional memory has been allocated.

Common Use Cases

The previous example was quite artificial, in order to illustrate the problem with incompatible lifetimes.

The following, a bit more realistic example is using a Slice<[T]> to create a (mutable) slice of slices (a.k.a. &mut [&mut [T]]) from a (mutable) flat slice (a.k.a. &mut [T]):

use rsor::Slice;

fn sos_from_flat_slice<'a, 'b>(
    reusable_slice: &'a mut Slice<[f32]>,
    flat_slice: &'b mut [f32],
    subslice_length: usize,
) -> &'a mut [&'b mut [f32]] {
    reusable_slice.from_iter_mut(flat_slice.chunks_mut(subslice_length))
}

In some cases, two separate named lifetimes are not necessary; just try combining them into a single one and see if it still works.

The same thing can of course also be done for immutable slices by removing all instances of mut except on the first argument (but including changing .from_iter_mut() to .from_iter() and .chunks_mut() to .chunks()).

If a pointer/length pair is given, it can be turned into a slice with std::slice::from_raw_parts_mut() or std::slice::from_raw_parts().

If a “list of lists” (e.g. something like a Vec<Vec<T>>) is given, it can be turned into a slice of slices with Slice::from_refs() (returning &[&[T]]) or Slice::from_muts() (returning &mut [&mut [T]]).

In C APIs it is common to have a “pointer to pointers”, where one pointer points to a contiguous piece of memory containing further pointers, each pointing to yet another piece of memory.

To turn these nested pointers into nested slices, we can use something like this:

unsafe fn sos_from_nested_pointers<'a, 'b>(
    reusable_slice: &'a mut Slice<[f32]>,
    ptr: *const *mut f32,
    subslices: usize,
    subslice_length: usize,
) -> &'a mut [&'b mut [f32]] {
    let slice_of_ptrs = std::slice::from_raw_parts(ptr, subslices);
    reusable_slice.from_iter_mut(
        slice_of_ptrs
            .iter()
            .map(|&ptr| std::slice::from_raw_parts_mut(ptr, subslice_length)),
    )
}

Note that ptr is supposed to be valid for the lifetime 'a and all other pointers are supposed to be valid for the lifetime 'b. The caller has to make sure that this is actually the case. This is one of the many reasons why this function is marked as unsafe!

Deeper Nesting

The motivation for creating this crate was to enable slices of slices, as shown in the examples above. However, it turns out that it is possible to have deeper nesting, for example slices of slices of slices:

use rsor::Slice;

let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12];
let mut level0 = Slice::with_capacity(6);
let mut level1 = Slice::with_capacity(2);
let sosos = level1.from_iter(level0.from_iter(data.chunks(2)).chunks(3));
assert_eq!(
    sosos,
    [[[1, 2], [3, 4], [5, 6]], [[7, 8], [9, 10], [11, 12]]]
);
assert_eq!(level0.capacity(), 6);
assert_eq!(level1.capacity(), 2);

For each level of nesting, a separate Slice is needed. The above example uses a Slice<[T]> for the innermost level and a Slice<[&[T]]> for the outer level. The resulting slice has the type &[&[&[T]]].

Structs

  • Slice
    Reusable slice of references.