Representation of enums

[nikomatsakis]

Discussion topic about how enums are represented in Rust. Some things to work out:

• What are the #[repr] options available for enums?
  • RFC 2195 defined the layout of #[repr(C)] enums with payloads.
  • RFC 2363 offers a proposal to permit specifying discriminations
• When do we currently perform Option<T>-like layout optimizations?
• When do we guarantee Option<T>-like layout optimizations?
  • For any Option-like enum? What about things like Result<T, ()>?
  • What are the conditions on T? (Obviously, must have some undefined values)
  • the Rustonomicon has some text on this topic
• Are there important enum variant optimizations we want freedom to do in the future that we might want to keep in mind?
• Size of empty enums and !: defined to be 0
• C-like enums: define, what does it say about representation?
  • document the effect of #[repr(C) and friends here

[nikomatsakis]

I'm surprised to see so little activity here. I'm going to stake out a position that:

• We need to guarantee Option<T> is optimized for some range of types T
  • I think we should guarantee that this is true for any enum where you have one nullary variant and one non-nullary variant
  • I think the types where this applies should include &T, extern fn, and stdlib types like NonZeroU32 that are designed for this
• Otherwise, we should reserve the right to optimize (or not optimize) other sorts of enums as we choose

We also probably want to document (but perhaps not guarantee forever?) our layout rules around ! -- in particular, we currently say that if you have an enum with a variant whose types are "completely" uninhabited (e.g., excluding product types), then this variant is ignored. This is needed, iirc, to handle uninitialized data, where we may try to initialize and use just those parts that are inhabited.

[hanna-kruppe]

• I think we should guarantee that this is true for any enum where you have one nullary variant and one non-nullary variant

+1

• I think the types where this applies should include &T, extern fn, and stdlib types like NonZeroU32 that are designed for this

+1, follow-up question: should we document this as propagating through newtypes? (and what's the exact defintion of newtype for this purpose -- e.g., do PhantomData fields make a difference) late edit: perhaps we'd like to go even further and document it for any aggregate that directly contains one of these types?

I propose guaranteeing one additional fact about repr(Rust) enums: an univariant enum should be represented the same as a struct containing the same data as the sole variant. So for example:

• enum Foo { Foo } is laid out like struct Foo;
• enum Foo { Foo(i32) } is laid out like struct Foo(i32);
• enum Foo { Foo { x: i32, y: i32 } } is laid out like struct Foo { x: i32, y: i32 }

This would be particularly useful if we also guaranteed that fully-uninhabited variants are ignored for layout purposes, because it allows type-punning between T and Result<T, !>.

[gnzlbg]

What about Option<T> where T has enough unused continuous space to store the discriminant (e.g. in padding bytes) ? Could we / should we guarantee anything here ? We can always leave it unguaranteed for now. cc @eddyb

EDIT: Is there a general way to phrase which things allow us to do enum layout optimizations ? E.g. invalid representations, memory that's "invalid to use" (padding bytes), etc.

[hanna-kruppe]

As I wrote earlier in #13, I don't see any way to repurpose padding for these or other purposes (if it's settled to be padding in the contained type's padding -- while determining the layout of T we can futz with the padding between T's immediate members) because code that just writes to the T through a pointer wouldn't be obligated to preserve the discriminant/padding, nor would it even know how to do that.

[alercah]

I would like to see Result<&T, ()> get optimized, but this depends on the representation of (), and in particular, what if we consider platforms where null pointers are nonzero? Do we always make () have a representation such that it can be used in this way?

Newtypes with repr(transparent), at the least, should be able to be optimized in enums in the same way that their underlying types are. This is not something that we can fully commit to until we discuss validity of values, however.

I agree with @eddyb's distinction in rust-lang/rfcs#2363 that the tag and discriminant are different concepts, and only the RFC 2195 reprs necessarily make the discriminant directly affect layout. I think that repr(rust) should offer no guarantees about how the discriminant values are taken into account for layout.

In particular, if RFC 2363 is adopted, I am inclined to say that assigning discriminants does not affect the Option<&T> layout optimization.

[eddyb]

Explicit discriminants won't affect a two-variant enum, because only one invalid value is being used, but the choice of assignments does matter when more variants are involved.

In particular, if there any gaps in between the discriminants of variants that need invalid values, that will use up invalid values as well.
We have a pragmatic limitation, which is that decoding the discriminant from the invalid value representation should be simple/quick: currently it's limited to "rebasing" the invalid value to the discriminant (i.e. they have matching ranges, just different starts).

[alercah]

Can you elaborate a bit more on why this is the case? On a #[repr(Rust)] enum, is the discriminant used for anything other than std::mem::discriminant()?

[eddyb]

@alercah Yes, it's what the MIR switch (really called SwitchInt) works with, for matching on an enum. So we have to decode the tag/invalid value into the discriminant value.

[alercah]

Ah, I see. Why do we support specifying discriminants on repr(Rust) enums at all, then?

[eddyb]

@nox's usecase is matching the tags between two enums for optimization purposes (LLVM generating better code if they match up, without writing any unsafe code).

[alercah]

That usecase isn't repr(Rust), though. What they're trying to do wouldn't work in repr(Rust), since there's no guarantee that the discriminant is stored in the first byte (or, in fact, is stored anywhere, because niche optimizations may mean it doesn't have to be).

If I write enum Foo { Bar = 1 }, it's not clear to me what the = 1 is actually doing. I'd forgotten that std::mem::Discriminant doesn't actually expose the underlying value. So you mentioned that the compiler uses it internally, but as far as I can tell, since we don't offer any layout guarantees, there's no guarantee that Bar is actually represented as a 1 of any kind.

I think this means that we should just deprecate explicitly-specified discriminants on repr(Rust) enums.

[eddyb]

@alercah By "without writing any unsafe code" I meant that nothing actually depends on any specific layout decisions for correctness, it's just that if they do match, the code will run slightly faster.

[alercah]

Ahh, right, I understand. Some testing shows that we don't seem to do these optimizations for repr(Rust) enums: https://play.rust-lang.org/?gist=c67903cbb0b6242b64f14d326c6f5849&version=stable&mode=debug&edition=2015. Note that all of @nox's examples include repr(Int).

Honestly, I had completely forgotten that we expose the discriminants of fieldless #[repr(Rust)] enums in numeric casts. I proposed in rust-lang/rust#46213 just now to not allow specifying discrimimants of #[repr(Rust)] enums with fields.

Still, even with them being observable, I think that we should opt against making any kind of layout guarantees based on discriminants. I frequently write code like that in this comment, except that I specify (almost always by omission, so they start from 0) overlapping discriminants. A very clever compiler could ignore the values of the discriminants as specified, and realize that it has an opportunity to optimize multiple types together. Consider this:

enum First {
  A,
  B,
}

enum Second {
  C,
  D,
}

enum FrontTwo {
  First(First),
  Second(Second),
}

Currently, the compiler lays out First and Second based on the discriminants---0 for A and C, and 1 for B and D. Both types use only 1 bit, but since it's the same bit, FrontTwo can't do any niche optimization. But someone very enterprising doing the layout could see that the representation of Second could be offset by setting C to 2 and D to 3, setting the second bit to 1 always and meaning that the representations now don't overlap. This allows FrontTwo to rely on the niche overlap to only take up one byte.

Now, imagine we have Third, Fourth, and BackTwo defined similarly. If we then define AllFour with FrontTwo and BackTwo variants, we could offset the representations similarly, storing all eight variants in only three bits instead of three bytes.

This tells me that there are potential optimizations that even a guarantee of "A fieldless #[repr(Rust)] enum is laid out as if it is just an unspecified integer of size at most isize, and the value of each variant is the discriminant." Moreover, they are quite significant. Given that the actual underlying integer type is unspecified anyway, it's difficult to depend directly on the layout, and you can always pick #[repr(Int)] if you want to. So I think we should guarantee nothing about #[repr(Rust)] except for any niche optimizations we want to support.

[alercah]

On the subject of Option, the bare minimum guarantee, I think, is as follows.

If an enum has exactly a single inhabited variant with a single nonempty field, it is the same as a newtype struct. If it has exactly two inhabited variants, with exactly one nonempty field between them, and that field is of suitable type, then it is niche-optimized.

This definition would cover Result<&T, ()>, Result<T, !>, and Option<&T>.

"suitable type" is a bit fuzzy. At the very least, Niko's types are definitely suitable, because of the C ABI, but if we accept nonzero values being guaranteed for niche-filling, bool and char could be too, as could any struct containing at least one field of suitable type. Any tagged enum---meaning any enum other than a #[repr(Rust)] enum with fields---that does not have exactly as many variants as it has room for would be eligible as well (although note that a #[repr(Rust)] field-like enum with, say, variants 0-255 would still require a second byte; it's just that we treat 256 like a valid value, put the niche there, and that causes the spillover).

[RalfJung]

bool and char could be too

char can't be 0-optimized

[briansmith]

C-like enums: define, what does it say about representation?

Please document the ABI considerations. In particular, document how Rust C-like enums work w.r.t. -fshort-enums. Note in particular, some targets have short enums as the default and others don't.

[gnzlbg]

• When do we currently perform Option-like layout optimizations?
• When do we guarantee Option-like layout optimizations?

I think we should give these optimizations a proper name instead of calling them Option<T>-like.

They are optimizations that apply to enums with sentinel values. Currently, these sentinel values can be specified via magic types like NonNull and NonZero, but I've wanted to use an Option<NotMax<usize>> in the past (and others have even created libraries around this: https://github.com/llogiq/optional), so it wouldn't be crazy to think that we might want to provide a way for users to specify these sentinel values in the future, and extend this to more than one sentinel value, so that enums with multiple variants can also be optimized.

I think that once we specify exactly what we guarantee about these enum optimizations, we only have to specify how core::option::Option is to be implemented, and that size_of::<Option<&T>>() == size_of::<*const T>() should just follow from that.

[RalfJung]

Using @eddyb's terminology, these are "niche optimizations" because they use a "niche" (a bunch of values that are never allowed in elements of a type) to store the enum discriminant.

[gnzlbg]

If an enum has exactly a single inhabited variant with a single nonempty field, it is the same as a newtype struct. If it has exactly two inhabited variants, with exactly one nonempty field between them, and that field is of suitable type, then it is niche-optimized.

This definition would cover Result<&T, ()>, Result<T, !>, and Option<&T>.

@alercah currently, Option<&T> is C FFI safe, would this definition also make these types FFI safe if the non-zero variant is FFI safe?

Many C APIs return an integer error code, where a value of 0 means success, and all other values denote an error condition. I'd like this to be FFI safe:

#[repr(transparent)] struct Error(NonZero<libc::c_int>);
extern "C" {
    fn foo() -> Result<(), Error>;
}

(edit: the same applies for Result<(), NonNull<*mut T>>, etc.)

[eddyb]

@RalfJung I actually like "sentinel" too. It'd be great to come up with a name to replace "niche" because it has gotten people confused and it's kind of a... niche term.

[gnzlbg]

While I also like sentinel I don't mind much about using "niche". After going through https://en.wikipedia.org/wiki/Sentinel_value I don't know if the "sentinel" term is also commonly used for multiple values.

It'd be great to come up with a name to replace "niche" because it has gotten people confused and it's kind of a... niche term.

The main reason is probably because we don't define this term anywhere yet and because the docs / nomicon / ... do not use it consistently. Whatever term we pick, we should just properly define it in the "enum layout" document and update the book, nomicon, etc. to use the term appropriately.

What terms do other languages use ?