有没有办法在没有运行时开销的情况下构建带有循环链接的结构? [英] Is there a way to build a structure with cyclic links without runtime overhead?

问题描述

我正在尝试在 Rust 中实现一个循环链接的数据结构.我的 Node 定义为:

I am trying to implement a cyclic linked data structure in Rust. My Nodes are defined as:

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

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

I am trying to build a minimal structure like this (extra brackets for better lifetime visibility):

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 的引用替换占位符以关闭循环".我试过这个，但它不起作用，因为我不能分配给 link1，这是借用上面的行，并且因为 link2 会超出范围仍被 link1 引用:

This works, but now I don't know how to replace the placeholder with a reference to link2 to "close the cycle". I tried this, but it doesn't work because I can't assign to link1, which is borrowed the line above, and because link2 would go out of scope while it's still referenced by link1:

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

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

I could try to avoid these lifetime issues by using Rcs, but that sounds like it would defeat the purpose of Rust's 0-runtime-cost lifetime management.

将所有节点放入 Vec 的另一种尝试，但仅直接引用它也不起作用:

Another attempt of putting all nodes into a Vec and only taking direct references to that didn't work either:

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]);

因为我不能在不可变借用的情况下更改任何节点，但它们都已经被永久借用了.

Because I can't change any nodes without mutably borrowing them, but they have all been immutably borrowed already.

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 所有权.

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.

推荐答案

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

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 需要始终执行别名异或可变性原则是很重要的.最好在编译时强制执行它，以便有 0 运行时成本，但是有时需要在运行时管理它，并且有多种结构:

It is however fundamental to realize that Rust requires enforcing the Aliasing XOR Mutability principle at all times. It is preferable to enforce it at compile-time, so as to have 0 run-time cost, however it is sometimes required to manage it at run-time and there are multiple structures for this:

• Cell、RefCell、AtomicXXX、Mutex、RWLock-named) 是关于安全地改变别名项目，
• Rc、Weak、Arc，都是关于拥有多个所有者.

• Cell, RefCell, AtomicXXX, Mutex, RWLock (the ill-named) are about mutating aliased items safely,
• Rc, Weak, Arc, are about having multiple owners.

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

Balancing the potential run-time overhead compared to the obtained flexibility is a fine art; it takes some experience and experimentation.

在您的特定情况下(构建节点相互引用的 BNF 语法)，我们确实可以使用 Cell 实现可变性的 0 运行时开销.

In your specific case (building a BNF grammar with nodes referencing each-other), we can indeed achieve 0 run-time overhead using Cell for mutability.

然而，主要的困难是获得一组具有相同生命周期的节点.您在 Vec 的想法上走在正确的轨道上，但正如您注意到的那样，一旦您借用一个节点，您就不能再次改变 Vec:这是因为增加 Vec 可能会导致它重新分配其底层存储，这会使已经获得的引用悬空(指向已释放的内存).

The main difficulty however is obtaining a group of nodes with the same lifetime. You are on the right track with the idea of a Vec<Node>, but as you noticed as soon as you borrow one node you cannot mutate the Vec again: this is because growing the Vec could cause it to re-allocate its underlying storage which would render the already obtained reference dangling (pointing to freed memory).

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

The generic solution would be to use unsafe code to manage the lifetime of the nodes yourself. You are, however, lucky: as you mentioned, your case is special because the number of nodes is bounded (by the grammar definition), and you drop them all at once. This calls for an arena.

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

My advice is therefore twofold:

1. 将节点存储在 typed-arena、立>
2. 使用Cell对于可变部分(&T 是 Copy).

1. Stash nodes in a typed-arena,
2. Use Cell for the mutable part (&T is Copy).

如果没有 unsafe 代码，您将无法将 arena 存储在与其余语法相同的结构中；是使用 unsafe 还是构建程序，让 arena 的寿命超过计算，这取决于您.

You will not be able to store the arena in the same struct as the rest of the grammar without unsafe code; it's up to you whether to use unsafe or structure your program so that the arena outlives the computation.

这篇关于有没有办法在没有运行时开销的情况下构建带有循环链接的结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！