I'm trying out random things to deepen my understanding of Rust. I just ran into the following error with this code:
struct Person {
mother: Option<Person>,
father: Option<Person>,
partner: Option<Person>,
}
pub fn main() {
let susan = Person {
mother: None,
father: None,
partner: None,
};
let john = Person {
mother: None,
father: None,
partner: Some(susan),
};
}
error[E0072]: recursive type `Person` has infinite size
--> src/main.rs:1:1
|
1 | struct Person {
| ^^^^^^^^^^^^^ recursive type has infinite size
2 | mother: Option<Person>,
| ---------------------- recursive without indirection
3 | father: Option<Person>,
| ---------------------- recursive without indirection
4 | partner: Option<Person>,
| ----------------------- recursive without indirection
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Person` representable
I understand that I can fix it if I put the Person
in a Box
, so this works:
struct Person {
mother: Option<Box<Person>>,
father: Option<Box<Person>>,
partner: Option<Box<Person>>,
}
pub fn main() {
let susan = Person {
mother: None,
father: None,
partner: None,
};
let john = Person {
mother: None,
father: None,
partner: Some(Box::new(susan)),
};
}
I would like to understand the full story behind that. I know that boxing means that it will be stored on the heap rather than the stack but I don't get why this indirection is necessary.
Data inside
struct
s andenum
s (and tuples) is stored directly inline inside the memory of the struct value. Given a struct likelet's compute the size:
size_of::<Recursive>()
. Clearly it has 1 byte from thex
field, and then theOption
has size 1 (for the discriminant) +size_of::<Recursive>()
(for the contained data), so, in summary, the size is the sum:That is, the size would have to be infinite.
Another way to look at it is just expanding
Recursive
repeatedly (as tuples, for clarity):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 regardBox<T>
is that it's a normalT
with the guarantee that it has a fixed size.)The Rust Programming Language, second edition has this to say about 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.