[Closed] Pre-RFC: Sealed Traits take 2


#1

This is a brach off of Pre-RFC: Sealed traits, and has few new semantics and lots of new layout guarantees.

NOTE This Pre-RFC is CLOSED

Sealed Traits

Motivation

There is a large gap between traits and enums. Traits give you lots of freedom when developing an API, and make it really easy to extend the API to handle types that weren’t handled before, or let users implement it for their own types. Traits can also be dynamically dispatched which is allows for code to handle a variety of types that it may not even know about! But this comes at a cost, it uses virtual dispatch, which is slow in comparison to generics or enums.

Enums on the other hand allow you to make a set of types which is internally maintained, but can often be hard to extend, due to stability concerns, and introduce an overhead that often isn’t necessary in the form of a discriminant or wasted space in enums with a large disparity between variants. Enums are also very fast, and this is very nice.

But there is no middle ground, a place where you can get the speed of enums, but the ease and efficiency of traits. This is the space that SealedTraits fill in.

Guide-level explanation

There are two different proposed syntaxes,

#[seal]
trait SealedTrait {}

// or

seal trait SealedTrait {}

For this proposal I will use the keyword syntax.

Trees

Efficient trees can be defined quite easily with this feature.

seal trait Ast { eval(self) -> f32; }

struct Value(f32);
struct BinaryOp<L: Ast, R: Ast, F: FnOnce(f32, f32)>(F, L, R);
struct UnaryOp<V: Ast, F: FnOnce(f32)>(F, V);

impl Ast for Value {
    fn eval(self) -> f32 { self.0 }
}

impl<L: Ast, R: Ast, F: FnOnce(f32, f32)> Ast for BinaryOp<L, R, F> {
    fn eval(self) -> f32 { (self.0)(self.1.eval(), self.2.eval()) }
}

impl<V: Ast, F: FnOnce(f32)> Ast for UnaryOp<V, F> {
    fn eval(self) -> f32 { (self.0)(self.1.eval()) }
}

This Ast is can be defined entirely on the stack (no indirection required!) and runs as fast as an enum without any dynamic dispatch!


note: this section needs work, as I have realized that dyn Trait cannot be Sized due to generic parameters.

Error Handling

Another example use-case for this would be ergonomic error handling within a crate.

In crate A

seal trait CustomError {
    fn message(&self) -> String;
    fn error_pre(&self) -> &'static str;
}

impl CustomError for String {
    fn message(&self) -> String {
        self.clone()
    }

    fn error_pre(&self) -> &'static str {
        "Lazy Error"
    }
}

struct Timeout<T: Display>(T);

impl CustomError for Timeout {
    fn message(&self) -> String {
        format!("{} timed out!", self.0)
    }

    fn error_pre(&self) -> &'static str {
        "Timeout"
    }
}

impl<E: CustomError> Display for E {
    ...
}

fn get_component<C: Component>(timeout: u32) -> Result<C, dyn CustomError> {
    let component = fetch_component_from_database(timeout);
    
    if let Some(component) = component.get() {
        if is_component_valid(&component) {
            Ok(Component)
        } else {
            // look, easy error handling
            // String will be coerced into
            // dyn CustomError, just like
            // any other trait
            Err("Component is not valid".to_string()) // ad hoc error handling till later refactor
        }
    } else {
        // look, easy error handling
        // Timeout will be coerced into
        // dyn CustomError, just like
        // any other trait
        Err(Timeout("Database"))
    }
}

In crate B, which uses crate A


/*
struct NewError;

// Error, you cannot implment a sealed trait outside it's crate!
impl CustomError for NewError {

}
*/

fn foo() {
    let player = crateA::get_component::<Player>(100);

    let player = player.unwrap(); // no need to think of the error type here
    
    // ...
}

Safety

todo

Reference-level explanation

Sealed traits are powerful, and come with a set of guarentees

  • Sealed traits cannot be implemented outside of their crate
  • Sealed traits can be implemented for any type
    • removing some orphan rules because they don’t matter to sealed traits
  • the trait object of sealed traits will be a fat pointer, where the extra data is a discriminant which specifies which type is being used.
    • due to this, SealedTrait can be dynamically dispatched in the same way as enums making it as fast as enums with all the flexibility of traits

Sem-Ver changes

  • adding functions to sealed traits is not a breaking change
  • making a trait sealed is a major breaking change
    • this is because types that used to be able to implement the trait now can’t
  • unsealing a trait is a major breaking change
    • this is because any code relying on the fact that dyn SealedTrait: Sized will become invalid

Drawbacks

Expanding the language adds complexity and maybe a new keyword.

Rationale and Alternatives

This is good for Rust because it bridges the gap between enums and traits, and allows for an efficient middle ground. Thereby allowing Rust to show off more safe zero-cost abstractions.

Prior art

  • Kotlin’s sealed classes
  • Scala’s sealed traits

Unresolved Questions

  • What syntax do we want, a new keyword or an attribute?

Pre-RFC: Sealed traits
#2

What about variants as types?


#3

I don’t like that you have to specify the enum every time you need to use a variant (too much of an ergonomic tax for something like this). I find this to be more practical, because I can specify the types in different modules in the same crate allowing me to be more organized. Also, I find this to be easier to teach and understand, at first you could just say that it’s just traits that can’t be implemented outside the module and the speed benefits it provides, then you can teach the benefits with respect to static vs dynamic dispatch (which can be more complicated). Also this proposal allows you to use the types without needing to have a discriminant.

Also how would you transform this

trait Ast {}

struct IntLiteral(u32);
struct Add<L: Ast, R: Ast>(L, R);
// ... more ast variants below

impl Ast for IntLiteral {}
impl<L: Ast, R: Ast> Ast for Add<L, R> {}
// ... more impls below

into an enum?


~edit~

This proposal also allows the compiler to reason about the code more precisely and optimize the code better than enums variants as types will.


#4

(coping over some of my thoughts)

Because the sealed-quality of a trait is so intrinsic to its identity, I think having actual syntax for it rather than an attribute is ideal. Personally, I like spelling this as enum trait. This is because this basically is enum variants are types, just a) requiring you to actually spell out the types (thus you can use privacy in them, yay!) and b) allowing types to belong to multiple enum trait. It also avoids a new contextual keyword.

To be more specific, this would be closest to “preexisting types as variants”.

An alternative within the same design space is to make dyn EnumTrait be !Sized, and put the enum discriminant in the data part of the fat pointer. This loses the key benefit I see in the proposal – being able to use dyn EnumTrait as a error type.

“Unnecessary” boxing:

enum Expr {
    IntLit(u32),
    Add(Box<Expr>, Box<Expr>),
    ..
}

This brings up an edge case (?) that does need to be handled though:

enum trait Expr {}
struct Add(dyn Expr, dyn Expr);

This is OK so far (as dyn Expr is an uninhabited type).

impl Expr for Add {}

Now Add is an infinitely sized recursive type. Where is the error emitted?


#5

Keep in mind you can use Enum::Variant.

Generics can be shoved into enums (I think).

Etc?


#6

Actually, thinking more about this, dyn Trait cannot be Sized, because I can do

seal trait List {}
struct Nil;
struct Link<T, L: List>(T, L);

And it would not be possible to know the size of dyn List at compile-time


#7

I believe variants as types would produce more correct and more optimized code.


#8

Yes, I forgot about that.

Yes they can, but they cannot recursively use the enum without indirection, sealed traits allow this, and the only indirection needed is at the top level.


#9

Enum::<Enum::<Enum::Variant>::Variant>::Variant?

We could add dyn Enum as a thing, for the few cases where that might be relevant. It won’t be usable where a variant is expected, but something like Enum::<Enum::<Enum::Variant>::Variant>::Variant could become an dyn Enum.


#10

Please define the enum.

This is one way to do it, but it requires allocation at every level, which is unnecessary.


#11

It’s not as rare as you think, any Tree structure requires this, and that can be common, one example is the DOM.


#12

Generics can be put on the root enum but not variants. It would never be possible to put generic parameters on variants, even if they were types.

To represent the problem:

// Ok:
enum Maybe<T> {
    Just(T),
    Nothing,
}
// Meaningless?
enum Maybe {
    Just<T>(T),
    Nothing,
}

Translated to enum trait:

// OK?
enum trait Maybe<T> {}
struct Just<T>(T);
impl<T> Maybe<T> for Just<T> {}
struct Nothing;
impl<T> Maybe<T> for Nothing {}
// Disallowed?
enum trait Maybe {}
struct Just<T>(T);
impl<T> Maybe for Just<T> {}
struct Nothing;
impl Maybe for Nothing;

But yes, this shows that if we allow freely parameterizing implementing types of an enum trait, it prevents dyn enum trait: Sized, as you can’t have enough information; there are an infinite number of variants. In fact, the whole idea of representing dyn enum trait as the type + an enum discriminant breaks down; any generic parameters will result in necessitating a vtable dispatch rather than a simple discriminant.

If sealed traits are spelled #[sealed] trait, it’s definitely a very hard sell to put any kind of restriction on the trait other than that it can only be implemented within the same crate.

If it’s spelled enum trait, and the goal is to be somewhat of a middle ground between enum and trait (which I think is a good idea that we should flush out a bit more), I could see this restriction being argued for. To formulate it: "every generic parameter used to impl an enum trait must be used to parameterize said enum trait"; that is, if you do impl<T> EnumTrait for _, T must be provided as a generic parameter to EnumTrait, otherwise it’s an error.

And again, if said restriction doesn’t exist, there’s nothing making a sealed trait special other than being unimplementable outside of the crate (though that still could potentially be used for optimization).


Now, let’s examine the relation both to “variants are types” and “types as variants”.

Variants are types

enum Maybe<T> {
    Just(T),
    Nothing,
}
  • In the type namespace, Maybe::<T>
  • In the type namespace, Maybe::<T>::Just
  • In the type namespace, Maybe::<T>::Nothing
  • In the value namespace, Maybe::Just: for<T> Fn(T) -> Maybe::<T>
  • In the value namespace, Maybe::Nothing: for<T> Fn() -> Maybe::<T>

Types as variants

enum Maybe<T> {
    Just = Just,
    Nothing = Nothing,
}
struct Just<T>(T);
struct Nothing;
  • In the type namespace, Maybe::<T>
  • In the type namespace, Just::<T>
  • In the type namespace, Nothing
  • In the value namespace, Just: for<T> Fn(T) -> Just::<T>
  • In the value namespace, Nothing: Nothing

Enum Trait (for completeness)

enum trait Maybe<T> {}
struct Just<T>(T); impl<T> Maybe<T> for Just<T> {}
struct Nothing;    impl<T> Maybe<T> for Nothing {}
  • In the type namespace, Maybe::<T> (trait)
  • In the type namespace, Just::<T>
  • In the type namespace, Nothing
  • In the value namespace, Just: for<T> Fn(T) -> Just::<T>
  • In the value namespace, Nothing: Nothing

Any of these three probably could be made to work, but each has their drawbacks.

The primary drawback to “variants are types” is that Maybe::Just isn’t a type. You need to specify the type on Maybe rather than Just. (Though, I suppose, it would be possible to not do it that way, though this seems the most consistent? Maybe? In any case, that’s path to the variant today.)

The primary drawback to “types as variants” I see is duplication between the external type and making it a variant; additionally, the way matching to destructure would work seems unclear.

The primary drawback to “enum trait” is what I mentioned above; applying enum restrictions on internal “types” to the implementations of the enum trait. Also, the method of doing downcasting is as of yet unspecified, but would probably work like a small Any over the small discriminant.


Having enum trait: Sized is what makes this concept so appealing to me. This halfway point between enums and traits seems to offer much of the benefits of both while only really applying the limitations of enum.


#13

Why would this be disallowed? Also what are enum traits? I have never heard of them.

Why? What other restrictions are there? The only other thing I specified is the relaxing of the orphan rules and the representation, which could both be done with an attribute that the compiler recognizes.

This can be done today (in a way) like so

enum Maybe<T> {
    Just(Just<T>),
    Nothing(Nothing),
}

#14

Just another way of spelling sealed trait. I prefer spelling it as enum trait since the properties we’re going for are a mixture of enum and trait.

I was talking in terms of the restriction that would be required to get dyn EnumTrait: Sized. And in fact, what I’m arguing is that without said restriction (putting generic implementation that doesn’t represent in the enum type), you can’t have a simple discriminant and instead need a full vtable to suppot it, so you just have the implementation restriction, and you don’t have the representation guarantee (though it could apply as an optimization when that isn’t the case, but it could for regular traits as well in an application (not a dylib) anyway, as all implementors are known when compiling a binary).

It definitely can, but it’s not stopped it from being brought up before! That section was mostly to compare the different ways of formulating a similar construct as the one that we’re discussing, being seal trait/enum trait depending on how you spell it.


#15

The restriction would require negative trait bounds, because it would need to disallow any type which implements the trait. (badly worded)

Earlier I gave the example

seal trait List<T> {}
struct Nil;
struct Cons<T, L>(T, L);

impl<T> List<T> for Nil {}
impl<T, L> List<T> for Cons<T, L> {}

This would have to be disallowed, or the constraint that L != Cons<_, _> would have to exist, but this constraint doesn’t exist in Rust.

Why? because without that constraint I could have Cons<_, Cons<_, Cons<_, ...>>> (arbitrarily deep), and it wouldn’t be possible to figure out the size of dyn List<_> at compile time for any non-zero sized type.

You could say that a weaker constraint would work, like L: !List<_>, but we don’t have negative trait reasoning either, and that would defeat the purpose of this List<_>. I don’t think it is worth pursuing dyn SealedTrait: Sized, because generics completely break this.


#16

Is the formulation that I provided not enough?

Specifically,

impl<T> List<T> for Nil {}
impl<T, L> List<T> for Cons<T, L> {}
//  ^-----     ^-- error: `L` is not bound by `List`, which is a seal trait

The fact is that with any L provided, you cannot know the size of dyn List<T> if Cons<T, L>: List<T>, because you don’t know L, which could be of any size. And because of this, you need a vtable to handle any interaction with the dyn trait object, so you lose any benefit beyond that of merely preventing implementors outside the crate. That is,

cannot be true if you allow any generics beyond those bound by the seal trait itself.


In other words, what’s the benefit of sealed traits, beyond being unimplementable (which is the point of this take 2 as I understand it), when you allow generics on implementors that aren’t bound by the trait.


#17

I am starting to wonder this myself. I don’t think there is any great benefit to this take 2, some minor changes to the original RFC would be enough, just relaxing orphan rules and adding the details about how sem-ver changes.