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

Question

我正在尝试随机的事情来加深我对Rust的理解.我刚用这段代码遇到以下错误:

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),
    };
}

错误是:

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

我知道我可以修复它,如果我把Person在Box,所以此工程:

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 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>)>)>) ==
...

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

A Box<T>是指针,即它具有固定的大小,因此(u8, Option<Box<Recursive>>)是1 + 8字节.(一种方法Box<T>是T保证它具有固定的尺寸,这是正常的.)

Answer 2

Rust编程语言,第二版有关于递归类型的说法:

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

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

Answer 3

请注意，虽然 aBox实际上从表面上解决了您的问题，但如果您打算在合作伙伴之间建立双向链接，则无法实际创建它的实例：

struct Person {
    partner: Option<Box<Person>>,
}

pub fn main() {
    let susan = Person { partner: None };

    let mut john = Person {
        partner: Some(Box::new(susan)),
    };

    // This moves `susan` into `john`, meaning `susan` is now only
    // accessible through `john.partner`.
    let susan = john.partner.as_mut().unwrap();

    // It is literally impossible to set john as a partner of susan,
    // no matter what you try. (without using `unsafe`)
    susan.partner = Some(Box::new(john));
}

error[E0505]: cannot move out of `john` because it is borrowed
  --> src/main.rs:18:35
   |
14 |     let susan = john.partner.as_mut().unwrap();
   |                 --------------------- borrow of `john.partner` occurs here
...
18 |     susan.partner = Some(Box::new(john));
   |     -------------                 ^^^^ move out of `john` occurs here
   |     |
   |     borrow later used here

Box仅当您拥有树状所有权链（其中某人拥有最顶层的项目）时才有用。

然而，你的情况并没有完全失败，只是稍微复杂了一点。

这一次，您可以使用Rc而不是Box执行此操作。不过，这有点危险，因为循环Rc链会泄漏并且永远不会掉落，除非您在某个时候手动中断循环。请记住，Rust 没有垃圾收集器。

我可以看到的一个解决方案是，这是一个专门不保持它指向的对象处于活动状态Weak的版本。Rc它是专门为像这样的循环引用而设计的。但请注意，这使得对象不可变，因此我们需要使用 来创建内部可变性RefCell。

error[E0505]: cannot move out of `john` because it is borrowed
  --> src/main.rs:18:35
   |
14 |     let susan = john.partner.as_mut().unwrap();
   |                 --------------------- borrow of `john.partner` occurs here
...
18 |     susan.partner = Some(Box::new(john));
   |     -------------                 ^^^^ move out of `john` occurs here
   |     |
   |     borrow later used here

John: RefCell { value: Person { name: "John", partner: Some((Weak)) } }
John's partner: Some("Susan")

Susan: RefCell { value: Person { name: "Susan", partner: Some((Weak)) } }
Susan's partner: Some("John")

John's partner after dropping Susan:
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/main.rs:16:51