How to work with !Sized types in Rust

On January 21, 2024 by Sosthène Guédon

Sizedness in Rust is a peculiar topic. I recently found myself having to work with unsized types when trying to reduce the use of const generics in the heapless crate. Here I will document the approaches I considered and the pros and cons of each of them.

The problem

Heapless is a crate used a lot in Embedded Rust. It's used to implement common collections and patterns you would usually find in the standard library, but that are not available in embedded context due to the lack of an allocator. The most used feature of this crate is the Vec structure, mimicking the API of the standard library Vec.

Heapless' Vec

Since an allocator is not available, the heapless Vec is backed by an array for which the size is known at compile time.

A standard library Vec would look like that ¹ :

pub struct Vec<T> {
  buffer: *mut T,
  len: usize,
  capacity: usize,
}

Where the buffer is a allocation of size capacity with the only first len items being initialized. To add an item to the buffer, the implementation would first check if len is equal to the capacity. If it is, reallocate the current buffer with additional space. Then, bump len by one and write the item to the remaining space in the buffer.

On the other side, an heapless buffer looks like this:

pub struct Vec<T, const N: usize> {
  len: usize,
  buffer: [MaybeUninit<T>; N],
}

In this case the capacity is always N. This means it cannot grow when the Vec is full so the push operation is now faillible:

impl<T, const N: usize> Vec<T, N> {
    pub fn push(&mut self, value: T) -> Result<(), T> {
        // If the len is already N, it is not possible to store any more items.
        if self.len == N {
            return Err(value);
        }

        unsafe { *self.buffer.get_unchecked_mut(self.len) = MaybeUninit::new(value)};
        self.len += 1;
        Ok(())
    }
}

Accessing the data is done through a Deref:

impl<T, const N: usize> Deref for Vec<T, N> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        unsafe { slice::from_raw_parts(self.buffer.as_ptr() as *const T, self.len) }
    }
}

impl<T, const N: usize> DerefMut for Vec<T, N> {
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe { slice::from_raw_parts_mut(self.buffer.as_mut_ptr() as *mut T, self.len) }
    }
}

Now this is very practical. This can be used everywhere to store dynamic data.

In our case at Nitrokey, a large use case for this structure are the response buffer of the various applications, all of which follow a request-response pattern.

The limitations

Object safety

Since the application all follow a request-response pattern, generally representing a standard interface (CTAHPID or CCID in our case), we want all applications to implement a trait to call them with arbitrary commands. Like this:

trait App {
    fn call<const R: usize>(
        &mut self,
        request: &[u8],
        response: &mut Vec<u8, R>,
    ) -> Result<(), Error>;
}

That way the response buffer can be managed by the transport layer to avoid unnecessary copying and save memory. But there is one problem with this approach, it's not Object Safe. This means, it is not possible to construct a dyn App because of the const-generic. For that to work, the &dyn fat pointer's virtual table would need to be able to store an quasi-infinite amount of implementations of the call function, one for each value of R.

There are workarounds for this, but they generally lose some flexibility in the process by giving R a fixed value.

Monomorphization

Since N in the vec is a const-generic, that means that for each value of N that is ever used, the code needs to be monomorphized. This can lead to a large binary size of the final program and cause the compile times to suffer. Since embedded often requires compilation with size optimizations turned on to fit on the device it can be a serious limitation. Luckily the optimizer is sometimes capable of merging the duplicate implementation together when they are similar, but it is not always the case.

Removing the const generic

The const generic is the cause of most of the issues, let's take a look at the first approach I implemented, and suggested in a issue.

Simple approach, using references

For our usage, I realized that we were not using owned Vecs a lot, and were instead using a lot of &mut Vec<T, N>. This meant that instead of passing a reference to the vec, we could very well pass a "view" to the Vec, consisting in a mutable reference to the len field and a mutable slice to the buffer field:

pub struct VecView<'a, T> {
    len: &'a mut usize,
    buffer: &'a mut [MaybeUninit<T>],
} 

In this struct, the buffer now as a size known at runtime, meaning that the const N: usize is not there anymore. The size is instead stored in the &'a mut of the buffer, which is a fat pointer, containing both the address of the buffer and its size. The capacity of the view is still available through buffer.len().

A VecView can be obtained from a Vec, and implement all operations available on either a &Vec or a &mut Vec:

impl<T, const N: usize> Vec<T, N> {
    pub fn as_view<'a>(&'a mut self) -> VecView<'a, T> {
        VecView {
            len: &mut self.len,
            buffer: &mut self.buffer,
        }
    }
}

impl<'a, T> VecView<'a, T> {
    pub fn push(&mut self, value: T) -> Result<(), T> {
        // If the len is already N, it is not possible to store any more items.
        if *self.len == self.buffer.len() {
            return Err(value);
        }

        unsafe { *self.buffer.get_unchecked_mut(*self.len) = MaybeUninit::new(value)};
        *self.len += 1;
        Ok(())
    }
}

impl<'a, T> Deref for VecView<'a, T> {
    type Target = [T];
    fn deref(&self) -> &[T] {
        unsafe { slice::from_raw_parts(self.buffer.as_ptr() as *const T, *self.len) }
    }
}

impl<'a, T> DerefMut for VecView<'a, T> {
    fn deref_mut(&mut self) -> &mut [T] {
        unsafe { slice::from_raw_parts_mut(self.buffer.as_mut_ptr() as *mut T, *self.len) }
    }
}

This means that the App trait presented previously can now become:

trait App {
    fn call(&mut self, request: &[u8], response: VecView<'_, u8>) -> Result<(), Error>;
}

This solves many problems. The trait is now Object-Safe, meaning it can be used as dyn App. However, there are still a couple of problems with this approach.

• Size

It is larger than a single reference. VecView is the size of three pointers: one for the length of the data, one for the start of the buffer, and one for its capacity. Since the offset between the length and the beginning of the buffer is known at compile-time, one pointer could be done without. In practice, not many instances of VecView would ever be created, so this is not that important.

• Ergonomics

VecView is not a reference, even though it is meant to behave like one. This means that the lifetime needs to be added to the generic parameters.

There are also some more subtle behaviours that plain references allow but not structures like that. One of them is reborrowing, meaning that in the following example, the first function compiles, but not the second:

fn compiles(buf: &mut Vec<u8, 10>) {
    /// Function that consumes a mutable reference
    fn inner(_: &mut Vec<u8, 10>) {}

    // Here `buf` is reborrowed, i.e. the compiler replaces it with `&mut *buf`, so that `buf` can be used again
    inner(buf);
    inner(buf);
}

fn errors(buf: VecView<'_, u8>) {
    /// Function that consumes a mutable reference
    fn inner(_: VecView<'_, u8>) {}

    // Here `buf` is passed by value instead, meaning that it cannot be used again.
    inner(buf);
    // COMPILE ERROR: buf was moved out of scope by the previous call to `inner`
    inner(buf);
}

There are ways to work around it, either through using &mut VecView everywhere, at the cost of 2 layers of indirection, or by introducing an explicit reborrowing at each such callsite:

impl<'a, T> VecView<'a, T> {
    fn reborrow<'b>(&'b mut self) -> VecView<'b, T> {
        VecView {
            len: self.len,
            buffer: self.buffer,
        }
    }
}  

fn reborrows(mut buf: VecView<'_, u8>) {
    /// Function that consumes a mutable reference
    fn inner(_: VecView<'_, u8>) {}

    // Here we create a temporary `VecView` that has a shorter lifetime than `buf`
    // so that `buf` can be used again after
    inner(buf.reborrow());
    inner(buf);
}

This raises the question: is there a way to create a View that is actually a reference?

Failed attempt with unsafe (and unsound) pointer casts

My first idea was to fix the layout of the Vec struct, so that I could represent the Vec as two structs, one that is the normal Vec, and the View that is unsized, by making sure they have the same layout. It should then be easy to cast a reference from one to the other using pointer casts and unsafe.

I did that using #[repr(C)]:

#[repr(C)]
pub struct Vec<T, const N: usize> {
  len: usize,
  buffer: [MaybeUninit<T>; N],
}

#[repr(C)]
pub struct VecView<T> {
  len: usize,
  buffer: [MaybeUninit<T>],
}

impl<T, const N: usize> Vec<T, N> {
    fn as_mut_view(&mut self) -> &mut VecView<T> {
        let ptr = self as *mut Vec<T, N> as *mut VecView<T>;
        unsafe {
            &mut *ptr
        }
    }
}

Sadly this does not compile:

error[E0607]: cannot cast thin pointer `*mut Vec<T, N>` to fat pointer `*mut VecView<T>`
  --> src/lib.rs:15:19
   |
15 |         let ptr = self as *mut Vec<T, N> as *mut VecView<T>;
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Indeed, *mut VecView needs to be a "fat" pointer that contains not only the address but also the length of the slice, and sadly the compiler is not "smart" enough to infer this information in a pointer cast. There are really no way to create a fat pointer to a user-defined structure, they can only be created by the compiler itself.

One way to solve the issue is to go through a slice and cast it:

impl<T, const N: usize> Vec<T, N> {
    fn as_mut_view(&mut self) -> &mut VecView<T> {
        use std::slice::from_raw_parts_mut;
        let sl: &mut [Self] = unsafe { from_raw_parts_mut(self, 1) };
        unsafe { &mut *(sl as *mut [Self] as *mut VecView<T>) }
    }
}

This compiles, but is undefined behaviour. I initially thought that fat pointers for !Sized object where the pointer and the size in bytes, but it is instead the pointer and the length of the slice in terms of elements it holds. This leads to the resulting VecView being always considered to be of capacity 1, since it was cast from a slice of length 1, leading to obviously wrong behaviour whenever N is not 1.

Just atfer publishing this article, it was pointed to me that there is a way to make it work ² :

impl<T, const N: usize> Vec<T, N> {
    fn as_mut_view(&mut self) -> &mut VecView<T> {
        use std::ptr::slice_from_raw_parts_mut;
        let sl: *mut [MaybeUninit<T>] =
            slice_from_raw_parts_mut(self.buffer.as_mut_ptr(), self.len);
        unsafe { &mut *(sl as *mut VecView<T>) }
    }
}

The sl pointer is invalid, but this is fine since it is never dereferenced. It is known to have a length of len element and the address of the base of the Vec, and can therefore be correctly cas to VecView. This is valid because the the Rust reference documents the content of fat pointers, and how they can be cast.

Since I did not initially find that solution, I kept going assuming that the #[repr(C)] approach would not work.

Unsize coercions, #[repr(transparent)] and the "clean" implementation

After the failure of my first approach, I had the brilliant idea of actually reading documentation on how unsized types can be constructed. It turns out that there is an easier way to create the VecView from a Vec.

Rust specifies a number of possible unsized coercion in the reference:

• [T; n] to [T].

• T to dyn U, when T implements U + Sized, and U is [object safe].

• Foo<..., T, ...> to Foo<..., U, ...>, when:

  • Foo is a struct.
  • T implements Unsize<U>.
  • The last field of Foo has a type involving T.
  • If that field has type Bar<T>, then Bar<T> implements Unsized<Bar<U>>.
  • T is not part of the type of any other fields.

The last case is the one that matters to us. Let's rewrite Vec to make use of it:

struct VecInner<B: ?Sized> {
    len: usize,
    buffer: B,
}  

pub struct Vec<T, const N: usize> {
    inner: VecInner<[MaybeUninit<T>; N]>,
}

#[repr(transparent)]
pub struct VecView<T> {
    inner: VecInner<[MaybeUninit<T>]>,
}

Now, VecView is a !Sized type. The as_mut_view can then be implemented by coercing VecInner into the type we want:

impl<T, const N: usize> Vec<T, N> {
    fn as_mut_view(&mut self) -> &mut VecView<T> {
        // Leveraging unsized coercion
        let r: &mut VecInner<[MaybeUninit<T>]> = &mut self.inner;
        // SAFETY: VecView is #[repr(transparent)]
        unsafe { mem::transmute(r) }
    }
}

As a bonus, contrary to the first aprroach, we can now construct a &VecView whereas the first approach could only deal with mutable VecView, even though for a Vec there is not much use to it.

impl<T, const N: usize> Vec<T, N> {
    fn as_view(&self) -> &VecView<T> {
        // Leveraging unsized coercion
        let r: &VecInner<[MaybeUninit<T>]> = &self.inner;
        // SAFETY: VecView is #[repr(transparent)]
        unsafe { mem::transmute(r) }
    }
}

This approach is implemented in the heapless PR#424.

This approach can easily be adapted to work for the String and the Bytes structure since they are simply a wrapper around a Vec<u8> and therefore can build views easily:

/// A fixed capacity [`String`](https://doc.rust-lang.org/std/string/struct.String.html).
pub struct String<const N: usize> {
    vec: Vec<u8, N>,
}

#[repr(transparent)]
pub struct StringView {
    vec: VecView<u8>,    
}

impl<const N: usize> String<N> {
    fn as_mut_view(&mut self) -> &mut StringView {
        // SAFETY: StringView is `#[repr(transparent)]`
        unsafe {
            std::mem::transmute(self.vec.as_mut_view())
        }
    }
}

This is amazing. We were able to use unsized coercions and a little bit of unsafe to get a very efficient and ergonomic API for the goal.

There are however some problems with this approach, as it does not scale for more complex types.

For example, in the iso7816 crate, we have a Command struct that represents an ISO7816-4 Command APDU:

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Command<const S: usize> {
    class: class::Class,
    instruction: Instruction,
    p1: u8,
    p2: u8,
    le: usize,
    extended: bool,
    data: Vec<u8, S>,
}

Now there is no way to build a "view" out of this. Even with the data at the end we can't allow coercing into a unsized CommandView, since Vec<u8, N> does not coerce into anything.

This means that the "view" of a command must necessarily be a struct of references, with the size inneficiency and the impractible lifetime definitions:

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct CommandView<'a> {
    class: &'a class::Class,
    instruction: &'a Instruction,
    p1: &'a u8,
    p2: &'a u8,
    le: &'a usize,
    extended: &'a bool,
    data: &'a [u8],
}

pub struct CommandViewMut<'a> {
    class: &'a mut class::Class,
    instruction: &'a mut Instruction,
    p1: &'a mut u8,
    p2: &'a mut u8,
    le: &'a mut usize,
    extended: &'a mut bool,
    data: &'a mut VecView<u8>,
}

The optimal API, using type aliases

The only thing missing in our API is the unsized coercion from the Vec to the VecView, but that is already available, if we directly expose the VecInner instead of the two types. To still make the API understandable, we can use type aliases, and hide the VecInner type in a private module.

mod sealed {
    pub struct VecInner<B: ?Sized> {
        pub(crate) len: usize,
        pub(crate) buffer: B,
    }
}

use sealed::VecInner;

pub type Vec<T, const N: usize> = VecInner<[MaybeUninit<T>; N]>;
pub type VecView<T> = VecInner<[MaybeUninit<T>]>;

impl<T, const N: usize> Vec<T, N> {
    pub fn as_mut_view(&mut self) -> &mut VecView<T> {
        self
    }
}

impl<T> VecView<T> {
    pub fn push(&mut self, value: T) -> Result<(), T> {
        // If the len is already N, it is not possible to store any more items.
        if self.len == self.buffer.len() {
            return Err(value);
        }

        unsafe { *self.buffer.get_unchecked_mut(self.len) = MaybeUninit::new(value) };
        self.len += 1;
        Ok(())
    }
}

VecInner is "sealed", meaning it is public, but it is not publicly nameable. This allows us to expose it in the public API of the crate in the type aliases, but consumers won't be able to use it directly. Without the pub, we would get a Rust compiler error because the type aliases publicly expose a private type. This sealing pattern is often used for Traits, but it's also available for structures.

But now we have a problem. The documentation of push is missing, and so will the documentation of all other functions implemented on Vec or VecView.

Thankfully, some efforts have been made in the Rust compiler to improve the documentation of type aliases, especially to be able to show the methods and trait implementations they offer. So the documentation should be generated for the push method!

Sadly, when implementing this approach, I realized that this was a bug. Indeed, since the VecInner struct is not publicly accessible, its documentation is not generated. This means that the aliases don't benefit from this documentation on their own pages. I opened an issue for this on rustdoc and looked for a workaround.

Thankfully, due to some weirdness I don't understand, it is possible to fix this with two lines in the top-level module:

#[cfg(doc)]
#[doc(hidden)]
pub use sealed::VecInner as _;

This makes rustdoc "aware" of VecInner, while still making it hidden and not namable. We can now have the documentation for the push method be generated as we want:

This workaround is only required on stable rust, as this has been fixed and will soon be available on nightly, which is used by docs.rs.

This gives us a pretty good API, where Vec<T, N> implements Unsize<VecView<T>>, which is the final PR I opened on heapless.

Let's go back to our CommandView example. It is now possible to implement the same pattern:

mod sealed {
    pub struct CommandInner<V: ?Sized> {
        class: class::Class,
        instruction: Instruction,
        p1: u8,
        p2: u8,
        le: usize,
        extended: bool,
        data: V,
    }
}

use sealed::CommandInner;

type Command<const N: usize> = CommandInner<Vec<u8, N>>;
type CommandView = CommandInner<VecView<u8>>;

Conclusion

After taking a look at the Vec implementation in heapless, we identified some key pain points in its usage. We looked at various approaches to address those painpoints, and learned a lot regarding Unsize coercions.

---