dyn* doesn't need to be special

or: more storage API propaganda

A response to @nikomatsakis's dyn*: can we make dyn sized?

dyn* Trait is a way to own a value of dyn Trait without knowing how the pointee is stored. In short, dyn* Trait acts as "&move dyn Trait", owning the pointee and dropping it, while also containing a clever feature I'm calling "owning vtables" allowing it to also transparently own the memory the pointee is stored in.

When you have a normal Box<dyn Trait>, the pointer itself looks something like

struct Box<dyn Trait> {
    data: ptr::NonNull<{unknown}>,
    vtable: &'static TraitVtable<{unknown}>,
}

and the vtable something like

struct TraitVtable<T: Trait> {
    layout: Layout = Layout::new::<T>();
    drop_in_place: unsafe fn(*mut T)
        = ptr::drop_in_place::<T>;
    // ... the contents of Trait
}

so that dyn Trait can recover the type information needed to interact with the pointee. The trick of dyn* is in using an owning vtable, best explained with a simple example:

• Box<T as dyn Trait>'s vtable's drop_in_place is ptr::drop_in_place::<T>
• Box<T as dyn Trait> as dyn* Trait's vtable's drop_in_place is Box::drop

In this manner, any smart pointer with an into_raw(self) -> *mut T can be owned transparently as dyn* Trait by generating a new vtable which replaces drop_in_place with a shim that from_raws the smart pointer and then drops it¹.

With more complicated vtable shims, you can even shove any pointer-sized value into a dyn*, by dealing it a data "pointer" of ptr::invalid(value) and the vtable shimming back to the original trait implementation on value directly.

And now, we need to talk about the storages API proposal for a bit.

But what does this have to with dyn*?

We'll get there! ... Hey, does Amos know you're here?

Actually, yes.

... Anyway, on the current nightly, Box and other allocating types are generic over trait Allocator. Allocator is a fairly standard abstraction over heap allocation, providing methods fn allocate(&self, Layout) -> Result<ptr::NonNull<[u8]>, AllocError> and fn deallocate(&self, ptr::NonNull<u8>, Layout).

The storages API adds another layer on top of this, dealing in a generic Self::Handle<T> type instead of ptr::NonNull<T> directly. In short²:

trait Storage {
    type Handle<T: ?Sized>: Copy;
    type Error;
    fn create(&mut self, meta: <T as Pointee>::Metadata) -> Result<Self::Handle<T>, Self::Error>;
    fn destroy(&mut self, Self::Handle<T>);
    // 👇
    fn resolve(&self, Self::Handle<T>) -> ptr::NonNull<T>;
}

To illustrate the benefit, consider a potential implementation:

struct InlineStorage<const LAYOUT: Layout> {
    data: UnsafeCell<MaybeUninit<[u8; LAYOUT.size()]>>,
    align: PhantomAlignTo<LAYOUT.align()>,
}

impl<const LAYOUT: Layout> Storage for InlineStorage<LAYOUT> {
    type Handle<T: ?Sized> = <T as Pointee>::Metadata;
    type Error = !;
    fn create(&mut self, meta: Self::Handle<T>) -> Result<Self::Handle<T>, !> { meta }
    fn destroy(&mut self, _: Self::Handle<T>) {}
    // 👇
    fn resolve(&self, meta: Self::Handle<T>) -> ptr::NonNull<T> {
        ptr::NonNull::from_raw_parts((self as *const _).cast(), meta)
    }
}

Now, you can have Box<T, InlineStorage<Layout::new::<T>()>> be layout-equivalent to storing T directly on the stack.

Amazing.

More importantly, though, is that you can have Box<dyn Trait, InlineStorage<Layout::new::<T>()>> also be layout-equivalent to storing T directly on the stack (plus a vtable pointer), but type-erased so you don't actually know about T anymore.

Oh, I think I see where you're going with this!

So, if we add a fallback to heap allocation ...

struct SmallStorage<const LAYOUT: Layout, A: Allocator = Global> {
    inline: InlineStorage<LAYOUT>,
    outline: AllocStorage<A>,
}

impl<const LAYOUT: Layout, A: Allocator> for SmallStorage<LAYOUT, A> {
    type Handle<T: ?Sized> = ptr::NonNull<T>;
    type Error = AllocError;

    fn create(&mut self, meta: <T as Pointee>::Metadata) -> Result<Self::Handle<T>, AllocError> {
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.create(meta)
        } else {
            let meta = self.outline.create(meta)?;
            Ok(NonNull::from_raw_parts(layout.dangling(), meta))
        }
    }

    fn destroy(&mut self, handle: Self::Handle<T>) {
        let meta = handle.metadata();
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.destroy(meta)
        } else {
            self.outline.destroy(handle)
        }
    }

    fn resolve(&self, handle: Self::Handle<T>) -> ptr::NonNull<T> {
        let meta = handle.metadata();
        let layout = Layout::for_metadata(meta)?;
        if layout.fits_in(LAYOUT) {
            self.inline.resolve(meta)
        } else {
            self.outline.resolve(handle)
        }
    }
}

... and maybe a type alias for convenience ...

type Dyn<T: ?Sized> = Box<T, SmallStorage<Layout::new::<usize>()>>;

We have the functionality of dyn* as a library type! Instead of dyn* Trait, we have Dyn<dyn Trait> (the stutter is unfortunate³). This is our type that is

• The size of Box<dyn Trait>,
• Stores small values of dyn Trait inline, and
• Owns the storage of dyn Trait, dellocating it on drop.

But wait, you're still missing something.

What, Cool Bear?

dyn* can hold any smart pointer, not just Box. You said so yourself!

Well, but there's a catch: dyn* needs to be DerefMut if it wants to fulfil its life goal of facilitating Pin<dyn* Future> usage. This means that it's restricted to single-ownership smart pointers wait hey that sounds like Box.

It's my belief that there aren't really any Pin<P<dyn Future>> types out there for a P that's not &mut or Box. I don't have any proof, just a feeling.

But the storages Dyn can be extended to support other DerefMut smart pointers, though it might require a second vtable pointer without the language support for easily wrapping the vtable into an owning vtable⁴.

So, storages get us the benefit of dyn* without any of the main problems with dyn*. I think that more than justifies bringing the storages API to std so we can properly spin the wheels on this design and find where it falls short. There's definitely flaws in the storages proposal I haven't spotted yet⁵, but we need to use it to find the rest of them.

Oh, and &move also falls out of storages as Box<T, &mut MaybeUninit<T>>, so that's even more proposed language features handled by the library feature. The storage API is good.

1. You can do clever things to avoid the from_raw shim, like with Box, where you can just call Box::drop directly, by patching up the other vtable members to take into account the container the smart pointer puts it in. However, since you use the dyn* many times and only drop it once, it seems better to just shim drop_in_place. ↩

2. For brevity, I omit a lot of details included in the full proposal. Notably, I omit a lot of safety concerns that are put on the user, and the full proposal has static controls for whether a storage can only create a single handle at a time or manages multiple handles, whether a handle is to a single element or to a slice of elements, as well as whether you need exclusive access to the storage to get mutable access to the pointee. ↩

3. In the olden days (before Rust 2018), we didn't have dyn Trait, it was just &Trait. dyn Trait is better, because you can immediately know that you're dealing with a dyn type rather than a fixed type. However, in this one specific case, omitting the dyn would allow us to write Dyn<Trait> instead, so it's impossible to say if it's good or not,, ↩

4. Then remaining concern is actually unowning references like &mut dyn Trait. The important thing to note here is that Box<Type, Storage> gives us two axis of customization: I've talked here about Storage for customization of the owning memory, but Type still gives us customization over how its used. For fn(&mut dyn Trait) -> Dyn<dyn Trait>, you can wrap the vtable to remove any drop glue with e.g. ManuallyDrop<dyn Trait>. This is where language support would be useful. ↩

5. In fact, I spotted one while drafting this post; as currently prototyped, storages are unsound, because the only handle resolution option is by-shared-ref and inline storages aren't using UnsafeCell, thus ultimately violating the aliasing guarantees 💣💥😱 ↩