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

Question

我正在尝试一些随机的东西来加深我对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 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

struct和enum中的数据(以及元组)直接内联存储在结构值的内存中。给定一个像这样的结构

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

让我们计算一下大小：size_of::<Recursive>()。显然，它有1个字节来自x字段，然后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

关于递归类型，是这样说的：

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

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