Optimize `repr(Rust)` enums by omitting tags in more cases involving uninhabited variants.

[zachs18]

Proposal

Enable optimizing repr(Rust) enum layout by omitting the tag in uninhabited variants in the tagged and niche-filling layouts, and omitting the tag entirely if there is only one inhabited variant.

Current layout algorithm for repr(Rust) enums

Definition: An "absent" variant is a variant that is uninhabited and has only 1-aligned 0-sized ("1-ZST") fields. A "present" variant is not "absent".

First, if an enum has no "present" variant(s), then it has the same layout as !, with no tag stored.

Second, if an enum has only a single "present" variant, then it has the layout of that variant interpreted as a struct, with no tag stored.

Otherwise, we compute two possible layouts: the tagged layout and the niche-filling layout.

The tagged layout is the "normal" enum layout, where there is an integer tag field encoding the discriminant at offset 0, and the variants fields are laid out after the tag.

The niche-filling layout chooses one variant whose struct-like layout is the largest and has a niche with enough available values for the number of remaining present variants, and where there is enough space before or after the niche field to layout the other present variants struct-like layouts. If there is no niche in the largest variant, the niche-filling layout is not computed and the tagged layout is chosen.

The smaller of these is chosen. If they are the same size, the one with the larger niche is chosen. If they have same niche size, the tagged layout is chosen (as it is simpler).

Proposed changes

1. If all variants are uninhabited, return an uninhabited layout with large enough size/alignment for the variants, but no tag or fields of its own. The variants' layouts (needed for offset_of!) are their struct-like layouts.

2. In the tagged layout, do not reserve space for the tag field in uninhabited variants (allow uninhabited variants' struct-like layouts to overlap the tag field).

3. In the niche-filling layout, do not reserve space for the niche field in uninhabited variants (allow uninhabited variants' struct-like layouts to overlap the niche field). If there are multiple largest variants, prefer an inhabited one as the niche-filled variant.

4. Compute a third layout: the no-tag layout: If there is exactly one inhabited variant, compute the struct-like layout of that variant (with no tag), and pad it to the size and alignment required to fit each other (uninhabited) variant's struct-like layout. That will be the layout of the enum as a whole. If there is not exactly one inhabited variant, this layout is not computed.

   If multiple valid layouts are computed, the smallest is chosen. If multiple are the smallest, and the niche-filling layout's niche covers the whole size of the enum, it is preferred (to preserve the guaranteed-NPO optimization). Otherwise, if multiple are the smallest, the layout with the largest niche is chosen. If multiple have the largest niche, the no-tag layout is preferred over the tagged layout, and the tagged layout is preferred over the niche-filling layout.

5. As a consequence of these changes (specifically changes 1 and 4), the compiler will need to keep track of the layouts of uninhabited variants even when a tag is not stored (Variants::Empty for change 1 and Variants::Single for change 4), so it knows the offsets of fields in such variants for offset_of!. This was not required previously because currently Variants::Empty and Variants::Single are used when only "absent" variants are omitted, and those have only 1-ZST fields which can all be at offset 0. (See also here and here for discussion of possible future optimizations that omit uninhabited variants from layout computation entirely. Nothing related to that is proposed here; under this MCP, there is still always space for the fields of an enum, even if they are in an uninhabited variant).

I propose making all of these changes, but some of them are not strictly required to be implemented together. Specifically: 1 and 4 each require 5; 2 requires 1¹; 3 does not require any other.

Examples:

Layout examples

enum Foo {
  A { a: u8, never: ! },
  B { b: u8, never: ! },
}

Currently laid out:

Variant	Byte 0	Byte 1
A (uninhabited)	tag=0	a
B (uninhabited)	tag=1	b

With the first change:

Variant	Byte 0
A (uninhabited)	a
B (uninhabited)	b

---

enum Foo {
  A,
  B { b: u8, never: ! }
}

Currently laid out:

Variant	Byte 0	Byte 1
A	tag=0	padding
B (uninhabited)	tag=1	b

With the second change:

Variant	Byte 0
A	tag=0
B (uninhabited)	b

(This enum is not affected by the fourth change, since the tagged layout is preferred over the no-tag layout for its niche in this case)

---

enum Bar {
  A { a: u8 },
  B { b: u8, never: ! }
}

Currently laid out:

Variant	Byte 0	Byte 1
A	tag=0	a
B (uninhabited)	tag=1	b

With the second (and not fourth) change:

Variant	Byte 0	Byte 1
A	tag=0	a
B (uninhabited)	b	padding

With the fourth change:

Variant	Byte 0
A	a
B (uninhabited)	b

---

#[repr(C)]
struct InconvenientNicheLocation(u8, bool, u8);

enum Foo {
    A { a: InconvenientNicheLocation },  
    B { b: u8 },
    C { x: u8, y: u8, never: ! },
}

Currently laid out:

Variant	Byte 0	Byte 1	Byte 2	Byte 3
A	tag=0	a.0	a.1	a.2
B	tag=1	b	padding	padding
C (uninhabited)	tag=2	x	y	padding

With the third change:

Variant	Byte 0	Byte 1	Byte 2
A	a.0	a.1 (niche)	a.2
B	b	0x02 (niche a.1)	padding
C (uninhabited)	x	y	padding

---

#[repr(transparent)]
struct NPONever(std::num::NonZero<u8>, !);
enum Foo {
  A { a: NPONever },
  B,
}

Laid out currently and with these changes:

Variant	Byte 0
A (uninhabited)	a.0 (niche)
B	0x00 (niche a.0)

This enum is subject to guaranteed-NPO, so it's layout must not change.

I have a WIP implementation at rust-lang/rust#145337 (the PR description is outdated). The changes are implemented in a different order than they are described in this MCP: change 5 is the first commit ("Prepare..."), change 1 and 2 are the fifth commit ("Don't encode..."), change 4 is the sixth commit ("Do not store tag..."), change 3 is the seventh commit ("Do not hold space...").

Mentors or Reviewers

If you have a reviewer or mentor in mind for this work, mention them here. You can put your own name here if you are planning to mentor the work.

Process

The main points of the Major Change Process are as follows:

• File an issue describing the proposal.
• A compiler team member who is knowledgeable in the area can second by writing @rustbot second or kickoff a team FCP with @rfcbot fcp $RESOLUTION.
  • Refer to Proposals, Approvals and Stabilization docs for when a second is sufficient, or when a full team FCP is required.
• Once an MCP is seconded, the Final Comment Period begins.
  • Final Comment Period lasts for 10 days after all outstanding concerns are solved.
  • Outstanding concerns will block the Final Comment Period from finishing. Once all concerns are resolved, the 10 day countdown is restarted.
  • If no concerns are raised after 10 days since the resolution of the last outstanding concern, the MCP is considered approved.

You can read more about Major Change Proposals on forge.

Note

Concerns (0 active)

• option-layout-guarantees resolved in this comment

Managed by @rustbot—see help for details.

Footnotes

1. or some other handling of the all-uninhabited-variant edge-case; without it enum Foo { A(Aligned2Never), B(Aligned2Never) } got a size-0 layout with an i16 tag field, which I assume would cause problems. ↩

[rustbot]

Important

This issue is not meant to be used for technical discussion. There is a Zulip stream for that.
Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

Concerns or objections can formally be registered here by adding a comment.

@rustbot concern reason-for-concern
<description of the concern>

Concerns can be lifted with:

@rustbot resolve reason-for-concern

See documentation at https://forge.rust-lang.org

cc @rust-lang/compiler

[RalfJung]

@rustbot concern option-layout-guarantees
There's an annoying conflict with the Option layout guarantees due to the fact that repr(transparent) types can have uninhabited 1-ZST in the "ignored" part of the layout. See #t-compiler/major changes > Optimize `repr(Rust)` enums by omitting t… compiler-team#922 @ 💬.

[RalfJung]

@rustbot resolve option-layout-guarantees

Turns out I misunderstood the proposed layout changes.