Why are recursive struct types illegal in Rust?
Data inside struct
s and enum
s (and tuples) is stored directly inline inside the memory of the struct value. Given a struct like
struct Recursive {
x: u8,
y: Option<Recursive>
}
let's compute the size: size_of::<Recursive>()
. Clearly it has 1 byte from the x
field, and then the Option
has size 1 (for the discriminant) + size_of::<Recursive>()
(for the contained data), so, in summary, the size is the sum:
size_of::<Recursive>() == 2 + size_of::<Recursive>()
That is, the size would have to be infinite.
Another way to look at it is just expanding Recursive
repeatedly (as tuples, for clarity):
Recursive ==
(u8, Option<Recursive>) ==
(u8, Option<(u8, Option<Recursive>)>) ==
(u8, Option<(u8, Option<(u8, Option<Recursive>)>)>) ==
...
and all of this is stored inline in a single chunk of memory.
A Box<T>
is a pointer, i.e. it has a fixed size, so (u8, Option<Box<Recursive>>)
is 1 + 8 bytes. (One way to regard Box<T>
is that it's a normal T
with the guarantee that it has a fixed size.)
The Rust Programming Language has this to say about recursive types:
Rust needs to know at compile time how much space a type takes up. One kind of type whose size can’t be known at compile time is a recursive type where a value can have as part of itself another value of the same type. This nesting of values could theoretically continue infinitely, so Rust doesn’t know how much space a value of a recursive type needs. Boxes have a known size, however, so by inserting a box in a recursive type definition, we are allowed to have recursive types.
Basically, the struct would be of infinite size if you don't use boxing. E.g., Susan has a mother, father, and partner, each of which have a mother, father, and partner....etc. Boxing uses a pointer, which is a fixed size, and dynamic memory allocation.