Pre-Pre-RFC: Dynamically sized enum types

language design
1

Currently, an enum type is always statically sized. I propose to allow dynamically sized enum types. This proposal does not allow recursive enum (aka. infinitely sized) types. I use terminology from RFC #2580: Pointer metadata & VTable.

The strategy is to put the discriminant in the pointer metadata if the enum type is dynamically sized. In other words, a pointer of a dynamically sized enum type is a wide pointer. In this way, the subtleties of thin DSTs are circumvented.

The unsizing coercion cannot modify the value behind the reference. Thus, the value representation of the dynamically sized enum and statically sized enum must be identical. Because a statically sized enum value has no metadata, the discriminant has to be stored in the enum value. Would that mean the discriminant is duplicated in both metadata and value? Partially yes, but actually no. Let me explain.

The critical idea is to put the enum tag at the end of an enum value instead of the beginning. The enum tag is "forgotten" when coerced to the dynamically sized enum value, and the metadata is now used when matching the enum value. In this way, the unsizing coercion is always just a transmute for the pointer. It is even possible to construct an enum value by allocating just the variant size, not the maximum size of all variants!

Edit: it turns out this design is inheritly incompatible with CoerceUnsized because the enum tag cannot be extracted from a possiblely dangling pointer. It should be possible to unsize a reference or a Box (original layout has to be saved), but doesn't work for a Weak (because it can be dangling).

Reference-level explanation

Consider this enum:

enum Either<L: ?Sized, R: ?Sized> {
  Left(L),
  Right(R),
}

enum Foo<T: ?Sized> {
  First,
  Second(String, T),
}

What would be the Pointee::Metadata of Either<L, R>? When the type is dynamically sized (either L or R is a DST), it should be isomorphic to Either<L::Metadata, R::Metadata>.

However, note that the metadata of Foo<DynT> is not Foo<DynT::Metadata>, because the String field of the Second variant is not needed. The metadata is isomorphic to Option<DynT::Metadata>.

Also, note that the metadata type should derive the needed trait implementations (Copy + Send + Sync + Ord + Hash + Unpin) required by the trait bound on the Metadata, even if the underlying type (Either or Foo) doesn't implement those traits.

A possible representation of the type Either<L,R> is the union of following types:

#[repr(C)]
struct Left {
  value: L,
  pad: [u8; max(0, size_of_R - size_of_L)],
  tag: u8 = 0
}

#[repr(C)]
struct Right {
  value: R,
  pad: [u8; max(0, size_of_L - size_of_R)],
  tag: u8 = 1
}

Then, the size (not counting alignment padding) of Either<L, R> is max(size_of_L, size_of_R) + 1. When a reference of &Either<L, R> is coerced to &Either<DynL, DynR>, the pointer is identical, but now the padding and the enum tag are not included in the size. That is, size_of_val(&Either::Left<L>(x) as &Either<DynL, DynR>) is size_of_L.

If the metadata type is represented in a Rust code, except that the implementation Pointee of is language-level, it would be:

#![feature(ptr_metadata)]
#![feature(unsize)]

use std::{ptr::{self, Pointee}, alloc::Layout, marker::Unsize};

enum Either<L, R> {
  Left(L),
  Right(R),
}

#[derive(Clone, Copy, Ord, Hash)]
enum EitherMetadata<MetaL, MetaR> {
  Left(MetaL),
  Right(MetaR),
}

impl<L: ?Sized, R: ?Sized> Pointee for Either<L, R> {
  type Metadata = EitherMetadata<<L as Pointee>::Metadata, <R as Pointee>::Metadata>;
}

// Specialization is needed when the type is statically sized.
// Note: `EitherMetadata<(), ()>` is not isomorphic to `()`.
impl<L, R> Pointee for Either<L, R> {
  type Metadata = ();
}

// Similar to [DynMetadata in std::ptr - Rust](https://doc.rust-lang.org/nightly/std/ptr/struct.DynMetadata.html).
impl<MetaL, MetaR> EitherMetadata<MetaL, MetaR> {
  pub fn layout(self) -> Layout {
    match self {
      EitherMetadata::Left(meta_left) => meta_left.layout(),
      EitherMetadata::Right(meta_right) => meta_right.layout(),
    }
  }
// Similarly,
//   pub fn size_of(self) -> usize;
//   pub fn align_of(self) -> usize;
}

// The implemetation of the unsizing coercion
impl<L, R> Either<L, R> {
  pub fn as_unsize<DynL: ?Sized, DynR: ?Sized>(&self) -> &Either<DynL, DynR>
  where L: Unsize<DynL>, R: Unsize<DynR> {
    let meta = match *self {
      Either::Left(ref left) => EitherMetadata::Left(ptr::metadata(left as &DynL)),
      Either::Right(ref right) => EitherMetadata::Right(ptr::metadata(right as &DynR)),
    };
    unsafe { &*ptr::from_raw_parts(self as *const _, meta) }
  }
}

Interaction to the niche filling optimization

As far as I can tell, the niche filling optimization is unchanged. Option<T> can omit the enum tag if T has a niche value. The as_unsize code above works even if the discriminant is stored implicitly in the niche. The critical requirement solved by "storing enum tag at the end" is that the address of the variant value is the same as the address of the enum value.

Additionally, the metadata type (EitherMetadata in the example above) is a subject of the layout optimization. For example, the metadata of Option<dyn Trait> is isomorphic to Option<DynMetadata<dyn Trait>>, and as a vtable pointer is always non-null, the size of the metadata is the size of the pointer.

Relation to enum variant types

By putting the enum tag at the end, a reference to an enum variant type can be transmuted to the reference of the original enum type (&Sum::A -> &Sum) while allowing the enum variant type to have a smaller size than the original enum type.

Previous discussions

The sealed trait or enum trait idea is also closely related.

2 Likes
2

The most obvious alternative is to make the enum's metadata be a union of all the variants' metadata types, and use the discriminant stored behind the pointer to determine which of the metadata variants should be used. I suspect there are problems with this approach (perhaps re: niche optimization). You might want to summarize them in an "alternatives" section.

1 Like
3

Edit: I misread the message. I'm talking about different thing below.

Such optimization would be "future possibilities" rather than "alternatives" because the approach does not work in general. For example, hundreds of variants cannot be fit to a 1-byte alignment pointer in x86. It is an opportunistic optimization at best.

4

Why not? A union has no discriminant, and is only as large as its largest variant. Given that all metadata types can fit in the second field of a fat pointer, surely a union of them will also.

5

I misread your message. I was thinking about storing discriminant in the pointer value, like lowest bits of the pointer value when align > 1.

6

What I'm missing in the proposal is an answer to the question of why. What use cases does this enable?

3 Likes
7

The main benefit of this, as I understand it, is reducing the number of allocations. For example:

enum Node {
    A,
    B,
    C(i32, Box<Node>),
}

A deeply nested node of this type uses a lot of Boxes, even though a single allocation would suffice to store the node, if self-referential types were unsized instead of infinite.

In the example above, it's pretty easy to make Node unsized:

struct Node {
    tail: NodeTail,
    c: [i32],
}

enum NodeTail {
    A,
    B,
}

But in more complex situations, it's not that easy – especially when there are multiple types that are mutually recursive. It might be doable, but the resulting code might be significantly harder to read and to work with.

An attribute that turns a self-referential type into a unsized type automatically would be beneficial in such cases. One problem is that this is not possible when there are multiple recursion points:

enum Foo {
    A(Foo),
    B(Foo), // this is okay
}

struct Bar {
    bar: Bar,
    ian: Bar, // but this is not!
}

The other problem is that Rust can't convert a self-referential type into an unsized type without changing its semantics. Most importantly, it couldn't be mutably borrowed, and creating an instance of this type would be a challenge.

I believe a custom allocator could solve the performance concern more elegantly.

8

Note that this proposal expressly doesn't cover self-referential enums:

Instead, it allows DSTs like str or dyn Trait to be stored as data inside enum variants, as is already allowed for structs.

1 Like
9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.