]>
Commit | Line | Data |
---|---|---|
60c5eb7d XL |
1 | A recursive type has infinite size because it doesn't have an indirection. |
2 | ||
3 | Erroneous code example: | |
4 | ||
5 | ```compile_fail,E0072 | |
6 | struct ListNode { | |
7 | head: u8, | |
8 | tail: Option<ListNode>, // error: no indirection here so impossible to | |
9 | // compute the type's size | |
10 | } | |
11 | ``` | |
12 | ||
13 | When defining a recursive struct or enum, any use of the type being defined | |
14 | from inside the definition must occur behind a pointer (like `Box`, `&` or | |
15 | `Rc`). This is because structs and enums must have a well-defined size, and | |
16 | without the pointer, the size of the type would need to be unbounded. | |
17 | ||
18 | In the example, the type cannot have a well-defined size, because it needs to be | |
19 | arbitrarily large (since we would be able to nest `ListNode`s to any depth). | |
20 | Specifically, | |
21 | ||
22 | ```plain | |
23 | size of `ListNode` = 1 byte for `head` | |
24 | + 1 byte for the discriminant of the `Option` | |
25 | + size of `ListNode` | |
26 | ``` | |
27 | ||
28 | One way to fix this is by wrapping `ListNode` in a `Box`, like so: | |
29 | ||
30 | ``` | |
31 | struct ListNode { | |
32 | head: u8, | |
33 | tail: Option<Box<ListNode>>, | |
34 | } | |
35 | ``` | |
36 | ||
37 | This works because `Box` is a pointer, so its size is well-known. |