ilustration
Illustration by Nate Laffan

fixed-slice-vec: an Embedded Rust no-std Vector

If you need a trustworthy collection with a variable number of elements in it, fast random access, contiguous element storage, and you're writing Rust, look no further than the standard library's Vec type. However, what if you're writing for a no-standard-library, no-global-allocator use case, such as an embedded system?

The standard Vec depends on a hidden heap of allocatable bytes through the global allocator, so that's right out. Instead, you should use one of several alternatives which have a fixed-at-compile-time backing region of data (usually on the stack) to present a Vec-like interface. ArrayVec is the most widely used of these options, as judged by recent crates.io downloads. You can specify a backing array type directly to pick the collection's maximum capacity, e.g. ArrayVec::<[bool; 12]>::new(). Heapless accomplishes a similar goal, but by using a typenum type parameter to set the capacity, which is useful if you're bought into the typenum ecosystem of compile-time numerical computation.

What to do, though, if your use case is constrained to not know at compile time how much backing memory will be available for your collection? At Auxon, I ran into this use case developing libraries which maintain variably-sized collections of state on behalf of the libraries' users. Why can't we have compile time type information? Perhaps it's because your library needs to be usable from C, where Rust type information is scarce. Maybe it's because you don't want to pick overly-large default capacities, which have the tendency to blow up stack sizes when nested to any significant depth. Maybe your system needs to allocate coarse chunks of memory based on configuration available at runtime.

I developed the fixed-slice-vec crate to meet this no-std, no-allocator, no-compile-time-capacity set of constraints. The FixedSliceVec type provides a Vec-like interface backed by a mutable Rust slice.

// Create a pre-populated and full vec (capacity 5, initial length 5)
let mut user_provided_array = [3, 1, 4, 1, 7];
let mut fsv = fixed_slice_vec::FixedSliceVec::from(&mut user_provided_array[..]);
assert_eq!(5, fsv.capacity());
assert_eq!(5, fsv.len());
assert_eq!(7, fsv.pop().unwrap());
fsv.push(6);
assert_eq!(&[3, 1, 4, 1, 6], &fsv[..]);

Note that FixedSliceVec threads through the lifetimes of that mutable slice reference, placing the management of that memory solely in the hands of the vector under Rust's safety constraints. The capacity of this vector is the provided slice's length.

Not every Vec starts full. In fact, often the backing memory region available may be completely uninitialized. FixedSliceVec handles this by accepting slices of Rust's modern idiom for possibly-uninitialized-data, MaybeUninit.

// User-provided uninitialized array of `MaybeUninit`. The `assume_init` is
// safe because the type we are claiming to have initialized here is a
// bunch of `MaybeUninit`s, which do not require initialization.
use core::mem::MaybeUninit;
let mut data: [MaybeUninit<u32>; 10] = unsafe {
	MaybeUninit::uninit().assume_init()
};

// Create an empty vec with capacity to add items
let mut fsv = fixed_slice_vec::FixedSliceVec::from(&mut data[..5]);
assert_eq!(5, fsv.capacity());
assert_eq!(0, fsv.len());
fsv.push(3);
fsv.push(1);
fsv.push(4);
assert_eq!(&[3, 1, 4], &fsv[..]);

As suggested by these examples, like the standard Vec, FixedSliceVec can provide a slice view on items that have been added to it and does not expose the uninitialized region of the data during regular operations.

Memory regions don't always show up in the type you care about; often you're handed just a pile of u8s. The from_bytes and from_bytes_uninit functions are convenience constructors that take a byte slice and give you a FixedSliceVec of your desired element type, handling the business of doing alignment-correction and type transmutation by the books.

let mut pile_of_bytes = [0u8; 1024];
let mut fsv: FixedSliceVec<u64> = fixed_slice_vec::FixedSliceVec::from_bytes(&mut pile_of_bytes[..]);
assert_eq!(0, fsv.len());
assert_eq!(Ok(()), fsv.try_push(314));

So, if you need a vector, don't know its capacity until runtime, can't use the standard library, don't have a global allocator, and want the convenience of a vector type, consider seeing if fixed-slice-vec is an improvement over manual array or slice management.

@zacktheengineer