The first thing that we are going to explore are recursive types, that is, a type that contains itself. This cannot be done directly, as the compiler needs to know in advance how much space a type requires. Consider the following struct:
struct Foo {
bar: i32
}
The compiler will ask itself, How much space does it take to create a Foo? and see that it needs just enough space to hold an i32. And how much does an i32 need? Exactly 32 bits. Now, consider the following:
struct Foo {
bar: i32,
baz: Foo,
}
How much space does Foo need? Enough to hold an i32 and a Foo. How much is an i32? 32 bits. And Foo? Enough to hold an i32 and a Foo. And how much does that Foo take? Enough for a Foo, and so on, until the heat death of the universe. Clearly, we don't want to spend that long on compiling. Let's take a look at the solution to our problem:
struct Foo {
bar: i32,
baz: Box<Foo>,
}
One last time, how big is Foo? Enough to hold an i32 and a Foo. How...