为什么递归结构类型在Rust中是非法的？

Question

我正在尝试随机的事情来加深我对Rust的理解。我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 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)),
    };
}

我想了解背后的全部故事。我知道拳击意味着它将存储在堆而不是堆栈上，但我不明白为什么这种间接是必要的。

Answer 1

structs和enums（和元组）中的数据直接内联存储在struct值的内存中。给出类似的结构

struct Recursive {
    x: u8,
    y: Option<Recursive>
}

让我们计算一下大小：size_of::<Recursive>()。显然，它与x字段有1个字节，然后Option的大小为1（对于判别式）+ size_of::<Recursive>()（对于包含的数据），因此，总的来说，大小是总和：

size_of::<Recursive>() == 2 + size_of::<Recursive>()

也就是说，大小必须是无限的。

另一种看待它的方法是反复扩展Recursive（为了清晰起见，作为元组）：

Recursive ==
(u8, Option<Recursive>) ==
(u8, Option<(u8, Option<Recursive>)>) ==
(u8, Option<(u8, Option<(u8, Option<Recursive>)>)>) ==
...

并且所有这些都内联存储在一块内存中。

Box<T>是一个指针，即它有一个固定的大小，所以(u8, Option<Box<Recursive>>)是1 + 8字节。 （考虑Box<T>的一种方法是它是一个正常的T，保证它有一个固定的大小。）

Answer 2

The Rust Programming Language, second edition有关于递归类型的说法：

Rust需要在编译时知道类型占用了多少空间。在编译时无法知道其大小的一种类型是递归类型，其中值可以作为其自身的一部分具有相同类型的另一个值。这种值的嵌套在理论上可以无限延续，因此Rust不知道递归类型的值需要多少空间。但是，框具有已知大小，因此通过在递归类型定义中插入框，我们可以使用递归类型。

基本上，如果你不使用拳击，结构将是无限大小。例如，苏珊有一位母亲，父亲和伴侣，每个人都有一位母亲，父亲和伴侣......等等。拳击使用一个固定大小的指针和动态内存分配。