Why doesn't `Option` support `dyn Trait`?

This is a simple question which I suspect is really complex. Rust doesn't appear to support DSTs (?Sized) in any enum. It seems to me that it would be safe, though. So I could implement this in unsafe Rust, but maybe I'm missing something. Is there a good reason why this cannot be supported?

The context is in my actor system (Stakker), it would be good to allow Actor<dyn Trait>, just like you can do an Rc<dyn Trait>. However the core of the actor can be approximated as Rc<RefCell<Option<A>>>. (This is most definitely not the implementation I'm using, rather I'm using qcell and some other enum, but it illustrates the problem). The presence of the Option means I can't support A: ?Sized which is the magic to allow dyn Trait.

Here's the issue so you can see my reasoning so far. (The other issue is CoerceUnsized being unstable, but I think I have a workaround for that, via Box.)

Incidentally, I'm preparing some supplementary documentation for Stakker (design notes, FAQ, etc) and polishing things up in general. If anyone would be interested in doing a technical review of the new docs when I have them ready, let me know. I would prefer there not to be any big technical errors when I announce it. Thanks

As I understand it, the memory layout of an enum is basically the same as

struct MyEnum {
    determinant:  Determinant<MyEnum>,
    data: union {
        variant1: Variant1Data,
        variant2: Variant2Data,
        // ...
    }
}

Allowing !Sized elements would require an alternate layout that includes runtime size information, which prevents it from being used in various situations, like stack allocations. It also runs into some difficulties when reassigning an enum to a new value: there’s no longer a guarantee that enough space is available in the existing allocation for the new value.

It is possible to do this in a rigorous manner, but it’s a big job and would take a significant amount of work to get done. At minimum, it needs to go through the RFC process to ensure the design fits well with the rest of the language and covers all of the relevant edge cases.

Essentially the size information must always be known. For sized types that information comes from the type and is used at compile time, and typically for unsized types it is stored in a fat pointer (a pointer + a size, so twice the size of a normal pointer) which is used at runtime.

Generic types, including on enums, are typically restricted to sized types. They’re easier to work with, since the data doesn’t always need to be behind a pointer, and have better default performance because there is no need to do a pointer lookup to access the data, and the user can always specify their own pointer type (a Box or a reference etc) if they are dealing with unsized data.

Would Actor<Box<dyn Trait>> be acceptable?

If not, I think you’ll have to effectively make your Actor type Rc<RefCell<Option<Box<A>>>> so that A can be unsized, but then all users will have to box their data.

3 Likes

Basically you cannot replace / overwrite a DST with another arbitrary DST, even in the heap. I think this is best seen with slices DSTs, rather than dyn Trait, although the problem is the same: if you had a &mut Option<[u8]>, or even simpler, a &mut [u8] / &mut dyn Trait how would you override that slice / trait object with another? As soon as the metadatas (len of the slice / underlying type (and thus vtable) of the trait object) don't match we are in trouble.

In other words, one has to realize that when you have a Rc<RefCell< Smth<impl !Sized> >>, the unsized metadata is not wrapped in the RefCell; it is not even in the shared contents of the Rc!

That's why:

is the road to go, since that would bundle the metadata within the RefCell part.

  • if the person owns the trait then they can simply impl Trait for Box<dyn Trait> (or more generally, impl Trait for Box<impl ?Sized + Trait>) and then use Actor<Box<dyn Trait>>,

  • otherwise they may need a newtype Wrapper around Box<dyn Trait>, then impl Trait for their Wrapper, and then use Actor<Wrapper>.

Depending on the usage, if you were to be able to handle non-'static types that impl Trait + Sized, then you could even allow them to avoid the extra heap allocation by using &'_ dyn Trait or &'_ mut dyn Trait.


The other option is to drop the arbitrary dynamic dispatch part, and reduce the usability to a statically fixed set of impl Trait types, so as to then use an enum wrapping such types (since the "dynamic metadata", that is, the discriminant of the enum, is inlined within the type and thus part of the RefCell).

2 Likes

Thanks for the replies. I will try and get my brain around them, and reply fully when I've got a clearer understanding and tried a few things.

The frustrating thing is that at a byte level I can see that there is little difference between an Option<T> and a (bool, T), except for controlling access to the T value when it is uninitialised. So it looks totally possible to do in unsafe code, with a wrapper to make it safe, at least concerning the outer mechanism of dyn (vtables and so on). For example Rust accepts struct Actor<T: ?Sized>(Rc<RefCell<(bool, T)>>); as safe.

I don't want to add overhead to most actors, so I don't want the double-indirection of boxing all the time. However maybe I can get boxing to work for those actors which are intending themselves to be used as an instance of a trait rather than directly as themselves. So yes, that might work. I will try it. Thanks

1 Like

I think the problem here is just Option's API. What is option.unwrap() supposed to return if T is unsized? You don't know how much memory to allocate. How is if let Some(t) supposed to bind if t is unsized? (A problem all enums would have.) Maybe if you had something like Option<T> but more restricted that could AsRef into an Option<&T>...

Ah, I see what you mean now, that is more complex, I don’t have a great answer for that.

Putting T: ?Sized on a type that contains a T inhibits layout optimizations because, in order to support unsizing coercion, Option<dyn Trait> has to be layout-compatible with Option<T> regardless of the concrete type T. Allowing Option<dyn Trait> would increase the size and alignment requirements of every Option<T>¹ regardless of whether it was ever used as Option<dyn Trait> or not.

An example (but not the only example) of layout optimization is niche-filling, which includes the nullable pointer optimization. This is widely considered a zero-cost abstraction and a good thing to have.


¹ Except when T is a byte-aligned type without a niche, plus or minus some other conditions.

1 Like

This might be a silly question, but does using a RefCell always imply a pointer access? I can’t tell if RefCell<Option<Box<T>>> really does require two pointer dereferences to access the data in a release build.

No, RefCell<T> is not a pointer; it contains T directly. Same goes for Mutex and Cell.

RefCell is just an inline cell. However the Rc has a pointer access. So Rc around a Box means two indirections from the caller to reach the actor data. I think that would be acceptable workaround for the case where the actor is intentionally implementing a trait, but I don't want to pay it for all actors. I'm still figuring out whether I can make your Actor<Box<dyn Trait>> idea work. It needs a bit more experimentation. I hope I can get it to work.

1 Like

Okay, @Douglas's idea of putting the Box<dyn Trait> inside the actor does actually work quite well, and doesn't require any changes to Stakker. So I think this can work as a workaround. It requires some boilerplate, but it's all on the actor implementation side, so is transparent to the users of the group of actors that implement the trait.

As far as I can see what @trentj said explains best why Option, and enums in general, don't support ?Sized. So if it's just to allow layout optimisations, then there is no fundamental reason why I can't implement my own enum with unsafe code that's compatible with ?Sized. The problem is right now my crate has a "no-unsafe" feature which disables all unsafe, so as there isn't a safe way of doing it, that would break that feature. So I'm limited to the workarounds either entirely within or entirely outside the actor interface.

Thanks everyone for their suggestions. I'll post the workaround code later.

With a bit more work I got rid of the boilerplate in the Actor<Box<dyn Trait>> solution. In the example below I previously had an Animal actor which encapsulated the Box<dyn Trait> and forwarded calls. But I realized that Box will auto-deref if called, so I could get rid of the intermediate type. This works out much cleaner. Everything seems to work fine within the actor. I will just have to add a new macro to Stakker to make it easy to create these actors. So this is okay. Only these trait-based actors will pay the cost of the extra indirection.

use stakker::*;
use std::time::Instant;

// Something like this will go in Stakker
macro_rules! actor_of_trait {
    ($core:expr, $trait:ty, $type:ident :: $init:ident($($x:expr),* $(,)? ), $notify:expr) => {{
        let notify = $notify;
        let core = $core.access_core();
        let actor = ActorOwn::<$trait>::new(core, notify);
        call!([actor], <$type>::$init($($x),*));
        actor
    }};
}

// Trait definition
type Animal = Box<dyn AnimalTrait>;
trait AnimalTrait {
    fn sound(&mut self, cx: CX![Animal]);
}

struct Cat {
    miaow_count: usize,
}
impl Cat {
    fn init(_: CX![Animal]) -> Option<Animal> {
        Some(Box::new(Cat { miaow_count: 0 }))
    }
}
impl AnimalTrait for Cat {
    fn sound(&mut self, _: CX![Animal]) {
        self.miaow_count += 1;
        println!("Miaow {}", self.miaow_count);
    }
}

struct Dog {
    bark_count: usize,
}
impl Dog {
    fn init(_: CX![Animal]) -> Option<Animal> {
        Some(Box::new(Dog { bark_count: 0 }))
    }
}
impl AnimalTrait for Dog {
    fn sound(&mut self, _: CX![Animal]) {
        self.bark_count += 1;
        println!("Woof {}", self.bark_count);
    }
}

pub fn main() {
    let mut stakker = Stakker::new(Instant::now());
    let s = &mut stakker;

    let animal1 = actor_of_trait!(s, Animal, Cat::init(), ret_nop!());
    let animal2 = actor_of_trait!(s, Animal, Dog::init(), ret_nop!());

    let mut list: Vec<Actor<Animal>> = Vec::new();
    list.push(animal1.clone());
    list.push(animal2.clone());
    list.push(animal1.clone());
    list.push(animal1.clone());
    list.push(animal2.clone());

    for a in list {
        call!([a], sound());
    }

    s.run(Instant::now(), false);
}

I was still wondering whether I could implement an unsized enum in an external crate in unsafe (but stable) Rust, and it appears not. The problem is that I need to express to the compiler the size of my enum struct. Both enum and union do this magic, taking the largest size out of a list of types, but enum doesn't support unsized, and union only supports Copy types (on stable). So unless I can find some other way to tell the compiler the size of my type, I've hit a brick wall -- at least until the compiler gets better support for union -- unless someone else can think of a way.

Otherwise, I'll accept defeat and proceed with Actor<Box<dyn Trait>>.

(union seems rather incomplete/broken as described, as it gives no mechanism for dropping a value of one member and putting in a new value of another member. However I could do direct unsafe access to the memory, ignoring the union members, if only I could get union to sort out the size and alignment, which it won't unless the types are Copy.)

As you point out above, the compiler needs to know at compile time the size of the largest alternative in a tagged enum or untagged union so that it can allocate the maximum required amount of memory and compute any required field-access offsets. !sized does not provide the information required for such a compile-time allocation. Therefore the only way to support compile-time allocation, and thus use an enum or union, is to store the !sized component(s) on the heap at run-time and link them into the enum or union via sized references (e.g., box) that the compiler can allocate at compile-time.

Edit: In theory rustc could create a tagged enum or untagged union of DSTs (dynamically sized types) where only the last field of one or more of the alternative sub-structs was !sized, because such a construction would permit the compiler to compute all required field-offsets at compile-time. I don't know whether rustc today supports such a construction. Such a !sized enum or union DST could not be allocated on the stack, but could be stored on the heap.

1 Like

union already accepts ?Sized types, so that is clearly possible (as you said in your Edit). All ?Sized types already have to be created on the heap, by some code that actually knows their sizes, before the pointer has the magic "dyn coercion" happen to it which makes it a ?Sized type. So I think that part's already taken care of.

The problem is that the implementation of union is incomplete. If union just handled size and alignment and left all access to field members to std::ptr methods, that would be fine. As it is, I guess they couldn't figure out how to make dropping stuff sane, and added the Copy restriction. Really there is no way to make dropping sane on a union, because at drop time, you don't know which member is active. So the only solution is to pass this responsibility over to the unsafe coder who's using the union, to use drop_in_place as necessary. It's error-prone but there is no other solution that I can see.

1 Like

There’s some related discussion here: https://github.com/rust-lang/rfcs/issues/1151

Edit: Don't use this as it's unsound. See below. However this will be possible as soon as MaybeUninit supports ?Sized.

For future reference, I've put together a DST-friendly implementation of Option, which does support dyn Trait. So it can be done!

1 Like

That structure is UB to use with types that aren't valid to be all zeroes. You want to use MaybeUninit, not ManuallyDrop.

1 Like

Okay, I tried MaybeUninit but it doesn't support ?Sized. Also, it doesn't matter what those values are as they are not accessed unless active is true. I tried mem::uninitialized() but it claims to be deprecated, but I couldn't find a way to get MaybeUninit::uninit() to work in its place. mem::zeroed() seemed to do the job.

Is there some theoretical reason why this is UB, rather than a practical one? In the None case, the memory won't get dropped or accessed, so it seems to me that it doesn't matter what value it has. What compiler UB could this cause?

Edit: ManuallyDrop might not have quite the right API, but I don't think it's UB how I'm using it. It must be valid to have uninitialised data in ManuallyDrop, because that's how it is after you call ManuallyDrop::drop. Zeros are just a special case of uninitialised data. Or maybe I could just use mem::uninitialized() instead and put up with the warning.