有没有一种方法可以在没有运行时开销的情况下构建具有循环链接的结构？

Question

我正在尝试用 Rust 实现循环链接数据结构。我的 Node 定义为：

#[derive(Debug)]
enum Node<'a> {
    Link(&'a Node<'a>),
    Leaf,
}

我正在尝试构建一个像这样的最小结构（额外的括号以获得更好的生命周期可见性）：

fn main() {
    let placeholder = Node::Leaf;
    {
        let link1 = Node::Link(&placeholder);
        {
            let link2 = Node::Link(&link1);
            println!("{:?}", link2);
        } // link2 gets dropped
    } // link1 gets dropped
}

这行得通，但现在我不知道如何将占位符替换为对 link2 到 "close the cycle" 的引用。我试过这个，但它不起作用，因为我无法分配给 link1，这是借用上面的行，并且因为 link2 仍然被 [=18] 引用时会超出范围=]:

let placeholder = Node::Leaf;
{
    let mut link1 = Node::Link(&placeholder);
    {
        let link2 = Node::Link(&link1);
        link1 = Node::Link(&link2);
        println!("{:?}", link2);
    } // link2 gets dropped
} // link1 gets dropped

error: `link2` does not live long enough
  --> src/main.rs:15:9
   |
13 |             link1 = Node::Link(&link2);
   |                                 ----- borrow occurs here
14 |             println!("{:?}", link2);
15 |         } // link2 gets dropped
   |         ^ `link2` dropped here while still borrowed
16 |     } // link1 gets dropped
   |     - borrowed value needs to live until here

error[E0506]: cannot assign to `link1` because it is borrowed
  --> src/main.rs:13:13
   |
12 |             let link2 = Node::Link(&link1);
   |                                     ----- borrow of `link1` occurs here
13 |             link1 = Node::Link(&link2);
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `link1` occurs here

我可以尝试通过使用 Rcs 来避免这些生命周期问题，但这听起来会违背 Rust 的 0 运行时成本生命周期管理的目的。

另一种将所有节点放入 Vec 并且只直接引用它的尝试也不起作用：

use std::ops::IndexMut;

let mut store = Vec::new();
store.push(Node::Leaf);
store.push(Node::Link(&store[0]));
store.push(Node::Link(&store[1]));
*store.index_mut(1) = Node::Link(&store[2]);

因为我无法在不可变借用的情况下更改任何节点，但它们都已经被不可变地借用了。

error[E0502]: cannot borrow `store` as immutable because it is also borrowed as mutable
  --> src/main.rs:12:28
   |
12 |     store.push(Node::Link(&store[0]));
   |     -----                  ^^^^^    - mutable borrow ends here
   |     |                      |
   |     |                      immutable borrow occurs here
   |     mutable borrow occurs here

error[E0502]: cannot borrow `store` as mutable because it is also borrowed as immutable
  --> src/main.rs:13:5
   |
12 |     store.push(Node::Link(&store[0]));
   |                            ----- immutable borrow occurs here
13 |     store.push(Node::Link(&store[1]));
   |     ^^^^^ mutable borrow occurs here
14 |     *store.index_mut(1) = Node::Link(&store[2]);
15 | }
   | - immutable borrow ends here

error[E0502]: cannot borrow `store` as immutable because it is also borrowed as mutable
  --> src/main.rs:13:28
   |
13 |     store.push(Node::Link(&store[1]));
   |     -----                  ^^^^^    - mutable borrow ends here
   |     |                      |
   |     |                      immutable borrow occurs here
   |     mutable borrow occurs here

error[E0502]: cannot borrow `store` as mutable because it is also borrowed as immutable
  --> src/main.rs:14:6
   |
12 |     store.push(Node::Link(&store[0]));
   |                            ----- immutable borrow occurs here
13 |     store.push(Node::Link(&store[1]));
14 |     *store.index_mut(1) = Node::Link(&store[2]);
   |      ^^^^^ mutable borrow occurs here
15 | }
   | - immutable borrow ends here

有没有一种方法可以在没有运行时开销的情况下拥有这样一个带有循环链接的结构，例如像我试过的那样使用纯引用？我可以接受额外的内存成本，例如支持 Vec 持有所有节点的所有权。

Answer 1

Is there a way to have such a structure with cyclic links without runtime overhead, for example with pure references like I tried? I'm fine with additional memory cost, like a backing Vec holding ownership to all nodes.

是的，有很多方法。

然而，认识到 Rust 需要始终执行 Aliasing XOR Mutability 原则是很重要的。最好在编译时强制执行它，以便有 0 运行-time 成本，但是有时需要在运行-time 管理它并且有多种结构：

Cell、RefCell、AtomicXXX、Mutex、RWLock（错误的命名）是关于安全地改变别名项目，
Rc、Weak、Arc 是关于拥有多个所有者。

与获得的灵活性相比，平衡潜在的运行时间开销是一门艺术；这需要一些经验和实验。

在您的特定情况下（构建节点相互引用的 BNF 语法），我们确实可以使用 Cell 实现 0 运行时间开销。

然而，主要困难是获得一组具有相同生命周期的节点。 Vec<Node> 的想法是正确的，但是正如您注意到的，一旦借用一个节点，您就无法再次改变 Vec：这是因为增加 Vec 可能导致它重新分配其底层存储，这将使已经获得的引用悬空（指向释放的内存）。

通用解决方案是使用不安全代码来自行管理节点的生命周期。但是，您很幸运：正如您所提到的，您的情况很特殊，因为节点的数量是有限的（由语法定义），并且您一次将它们全部删除。这需要一个 arena.

因此，我的建议是双重的：

在 typed-arena、
对可变部分使用 Cell（&T 是 Copy）。

如果没有 unsafe 代码，您将无法将竞技场存储在与其余语法相同的结构中；由您决定是使用 unsafe 还是构建您的程序，以便竞技场比计算更长久。

有没有一种方法可以在没有运行时开销的情况下构建具有循环链接的结构？

Is there a way to build a structure with cyclic links without runtime overhead?

tree

cyclic-reference

rust

cyclic-graph