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),
};
}
The error is:
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 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With