Idea: Fixed sized traits

This is an idea I've been thinking about for some time now and I thought I'd share it. This is my first post here, so I hope I'm doing it right. :slight_smile:

Idea

In short, the idea would be to have traits which impose a fixed size on its implementors. For example, by having a special `Fixed` trait. Consequences of this would be: default Sized trait objects, no need for indirection, matching on trait objects,...

Traits and Enums

I got this idea by looking into subtype/inclusion polymorphism in rust. The way I see it, there are two main ways to do "subtyping" (some might not like this term, but I think fits here).

The first is traits with trait objects as the polymorphic types and the implementors as subtypes. Example:

trait MyTrait {
    fn method(&self) -> String;
}
struct Variant1;
struct Variant2;
impl MyTrait for Variant1 {
   fn method(&self) -> String {/*impl*/}
}
impl MyTrait for Variant2 {
   fn method(&self) -> String {/*impl*/}
}

The second is enums with instances of this enum as polymorphic types and its variants as subtypes. Example:

enum MyEnum {
    Variant1,
    Variant2
}
impl MyEnum {
    fn method(&self) -> String {
        match self {
             Variant1 => /*impl*/,
             Variant2 => /*impl*/
        }
    }
}

Both methods have advantages and disadvantages, but there is always a kind of "cost" (not necessarily a runtime cost). For traits, the main cost is the need for indirection, while for enums the main cost is that all variants have the same size (including padding), but there are different costs too (see comparison).

Fixed Sized Traits

Fixed sized traits are an attempt to combine both traits and enums to have a different "cost" option. I see these fixed sized traits in two possible ways: using a vtable or using a tag.

The first makes them very similar to normal traits. The only difference is the sized property. This changes the trait indirection cost into the enum fixed size cost. Example:

trait MyFixedTrait : Fixed<4u> { //arbitrary size
    fn method(&self) -> String;
}
struct Variant1;
struct Variant2;
impl MyFixedTrait for Variant1 {
   fn method(&self) -> String {/*impl*/}
}
impl MyFixedTrait for Variant2 {
   fn method(&self) -> String {/*impl*/}
}

The second option would be to use a tag instead. This makes them similar to enums, so I'll call them enum traits. For a tag to work, the user would need to specify what variants are possible. So a new (type) declaration would be needed that specifies the fixed trait and the variants. Example:

enum trait MyEnumTrait for MyFixedTrait {
    Variant1,
    Variant2
}

Comparison

Trait Fixed sized trait Enum trait Enum
Sized No Yes Yes Yes
Extend with new variants Yes Yes No No
Use variants separately Yes Yes Yes No
Automatic polymorphism* Yes Yes Yes No
Pattern matching No No Yes Yes
Variant differ vtable vtable tag tag
* With Automatic polymorphism, I mean the fact that traits seemingly call the correct function while enums need pattern matching.

Use cases

Both the fixed sized traits and enum traits can be used in use cases where traits or enums would be used. The reason to use them is for example if indirection is too big of a cost, but you want it to be extendible, you could use a fixed sized trait. Or if you would use an enum, but there are too many variants, which make match statements unreadable, you could use enum traits.

Conclusion

For subtype/inclusion polymorphism there is always a cost. So why not give more option to choose the right cost for your problem. Fixed sized traits and enum traits give two new options with different costs.

Could you describe a concrete use case where fixed size traits or enum traits would be more desirable than regular traits or enums? I genuinely can't think of a single even hypothetical case when you'd want either of them.

1 Like

see also: Sealed Traits

4 Likes

FYI this exists: https://docs.rs/enum_dispatch/0.3.0/enum_dispatch/

It addresses most of these needs in a straight forward way.

1 Like

"Enum trait" seems similar to the idea of enum variant types https://github.com/rust-lang/rfcs/pull/2593.

1 Like

@RustyYato When looking for prior art I came across the sealed traits, but I thought it was more about sealing a trait inside a crate rather than removing indirection. I read it again and I see now that it is a lot more similar to my idea than I thought. However, the key difference is that sealed trait try to know the size by sealing it in a crate, while my idea is to let the user decide the size. You would than be able to implement the trait from another crate.

@tkaitchuck I think this enum_dispatch is exactly what I meant with the enum trait. So thank you for mentioning!

@pcpthm Enum variant types are similar to my enum trait, but the thing is that for my enum trait all variants implement the same trait which causes the enum itself to implement this trait. But, as mentioned by @tkaitchuck, you can do this with some macro magic.

I genuinely can't think of a single even hypothetical case when you'd want either of them.

When choosing between traits and enums, you choose between flexibility and performance. The idea is that there can be something in between. Both sealed traits and enum dispatch metioned in this thread, have the same idea, they talk about improving performance for traits.

We should imho leave dyn Trait unsized but instead use small box optimizations, although our current smallbox crate wastes one usize unnecessarily.

You instead want a SmallBox<T,Size> type that determines whether its internal Size holds T, or whether the first usize contains a Box, by invoking mem::size_of_val with the vtable provided by dyn Trait and ptr::null, ala https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=9f175095c2f072317c31d3e5c68e291b

It works because mem::size_of_val never dereferences its data pointer. All dyn Trait record their size n their vtable. We cannot create dyn Traits from unsized types, but even those keep their size in the fat pointer.

We'd make alloc an optional crate feature, so this SmallBox crate still works without std or even alloc. At this point, you define an error type SmallBox<dyn Error,usize> that exists without without std or alloc, provided your Error trait avoids std too.

1 Like

Thanks Jeff! The smallbox crate looks awesome!

As I said, the smallbox crate was designed to support slice-like DSTs where the fat pointer encodes the size, as well as sized types, so the crate wastes an entire usize because they this this wrong!

You want a smallbox designed for trait object style DSTs where the fat pointer encodes the type. We should ideally do a smallbox designed for perhaps only slice-style DSTs too, but not sure exactly how yet.

1 Like

I also think a smallbox type should work with and without alloc / an allocator. I'll try to find some time to adapt the smallbox crate in the next few weeks. If I manage then I'll post back here for help testing it. :slight_smile:

2 Likes