在递归数据结构中使用常规引用而非`Box`

Question

我是新手 Rust。当我阅读《Rust 编程语言》第 15 章时，我无法理解为什么应该在递归数据结构中使用 Box 而不是常规引用。书的第 15.1 节解释了需要间接引用来避免无限大小的结构，但它没有解释为什么要使用 Box。

#[derive(Debug)]
enum FunctionalList<'a> {
    Cons(u32, &'a FunctionalList<'a>),
    Nil,
}

use FunctionalList::{Cons, Nil};

fn main() {
    let list = Cons(1, &Cons(2, &Cons(3, &Nil)));

    println!("{:?}", list);
}

上面的代码编译并生成了期望的输出结果。似乎使用 FunctionalList 在栈上存储少量数据非常完美。这段代码会引起问题吗？

- user5413830

---

鉴于递归类型无法确定大小的问题，这是如何可能的呢？ - kianenigma

Answer 1

的确，FunctionalList 在这个简单的例子中是有效的。然而，如果我们尝试以其他方式使用这个结构，就会遇到一些困难。例如，假设我们试图构建一个FunctionalList，然后从一个函数中返回它：

#[derive(Debug)]
enum FunctionalList<'a> {
    Cons(u32, &'a FunctionalList<'a>),
    Nil,
}

use FunctionalList::{Cons, Nil};

fn make_list(x: u32) -> FunctionalList {
    return Cons(x, &Cons(x + 1, &Cons(x + 2, &Nil)));
}

fn main() {
    let list = make_list(1);

    println!("{:?}", list);
}

这将导致以下编译错误：

error[E0106]: missing lifetime specifier
 --> src/main.rs:9:25
  |
9 | fn make_list(x: u32) -> FunctionalList {
  |                         ^^^^^^^^^^^^^^ help: consider giving it an explicit bounded or 'static lifetime: `FunctionalList + 'static`

如果我们按照提示添加了一个 'static 生命周期，那么我们将得到以下错误：

error[E0515]: cannot return value referencing temporary value
  --> src/main.rs:10:12
   |
10 |     return Cons(x, &Cons(x + 1, &Cons(x + 2, &Nil)));
   |            ^^^^^^^^^^^^^^^^^^^^^^-----------------^^
   |            |                     |
   |            |                     temporary value created here
   |            returns a value referencing data owned by the current function

问题在于这里内部的FunctionalList值由隐式临时变量拥有，其作用域在make_list函数结束时结束。因此，这些值将在函数结束时被丢弃，留下对它们的悬空引用，这是Rust不允许的，因此借用检查器会拒绝此代码。

相比之下，如果将FunctionalList定义为Box，那么所有权将从临时值移动到包含的FunctionalList中，我们就可以毫无问题地返回它了。

对于你原来的FunctionalList，我们需要考虑的是：在Rust中，每个值都必须在某处拥有所有者；因此，如果像这种情况一样，FunctionalList不是其内部FunctionalList的所有者，则该所有权必须存在于其他地方。在你的例子中，该所有者是一个隐式临时变量，但在更复杂的情况下，我们可以使用另一种不同的外部所有者。以下是使用TypedArena（来自typed-arena crate）拥有数据的示例，以便我们仍然可以实现make_list函数的变体：

use typed_arena::Arena;

#[derive(Debug)]
enum FunctionalList<'a> {
    Cons(u32, &'a FunctionalList<'a>),
    Nil,
}

use FunctionalList::{Cons, Nil};

fn make_list<'a>(x: u32, arena: &'a Arena<FunctionalList<'a>>) -> &mut FunctionalList<'a> {
    let l0 = arena.alloc(Nil);
    let l1 = arena.alloc(Cons(x + 2, l0));
    let l2 = arena.alloc(Cons(x + 1, l1));
    let l3 = arena.alloc(Cons(x, l2));
    return l3;
}

fn main() {
    let arena = Arena::new();
    let list = make_list(1, &arena);

    println!("{:?}", list);
}

在这种情况下，我们调整了 make_list 的返回类型，使其仅返回一个可变引用指向 FunctionalList，而不是返回拥有所有权的 FunctionalList，因为现在所有权属于 arena。

- Brent Kerby