Heap Allocated "Compact" Tagged Unions

#1

Could heap-allocated tagged unions that only occupy the space required by the current variant make sense as a Rust feature?

Say I’m creating an AST or some kind of persistent data structure. I want a tree of heap allocated enums.

Currently, using plain Rust, you’d do something like:

enum T1 {
    A(A),
    B(B),
    C(C),
}
// Then use it as:
let ptr1: Box<T1>;

or:

enum T2 {
    A(Box<A>),
    B(Box<B>),
    C(Box<C>),
}
// Then use it as
let ptr2: T2;

Neither of these approaches is perfect. The different variants might have very different sizes and using the first approach would always allocate the space required for the biggest variant. The second approach essentially makes T2 a “thick pointer” using twice the space of a normal pointer. In Rust specifically, it would make it awkward to borrow the structure without adding a level of indirection.

We rarely want to mutate AST nodes from one variant to another. It would make sense to only allocate enough memory for the variant we are using. It would also make sense to put the tag at the beginning of the heap-allocated memory instead of with the pointer, since we rarely look at the tag without looking at the data.

In C, you might attempt such a thing using flexible array members and casts (paying close to not get alignment wrong).

What do you think? Would such a feature make sense in Rust or in general? Did anyone ever implement something like this for Rust (using macros maybe)? Do any other programming languages implement both types of tagged unions?

1 Like
#2

This sort of question/proposal should go on internals.rust-lang.org

Also this sounds a lot like trait objects, so look into that before posting on internals

1 Like
#3

Should all discussion related to language features that aren’t simple to emulate in current Rust be asked in the internals forum? Even if part of the question would be “how would I do it in current Rust?”

This isn’t at all like trait objects. 1. Trait objects use fat pointers 2. You interact very differently with trait objects than you do with enums. I like my exhaustive pattern matching.

Trait objects do solve one thing and that’s letting you borrow Box<dyn Trait> without creating an extra level of indirection.

#4

It sounds like you were proposing a change to how Rust operates, which is why I suggested internals. If you weren’t, sorry I misunderstood.

Ok, if this looks like a space optimization, and this should be possible to do with some carefully written unsafe code. I don’t think that there is anything that does this right now.

#5

std::alloc is now stable so you can write a crate you want with it. It’s mostly unsafe of course, please do it extra carefully!