Есть ли способ построить структуру с циклическими ссылками без затрат времени выполнения?

Question

Я пытаюсь реализовать циклически связанную структуру данных в Rust. мой Nodes определены как:

#[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 "замкнуть цикл". Я пробовал это, но это не работает, потому что я не могу назначить link1, который заимствован строкой выше, и потому link2 будет выходить за рамки, пока на него все еще ссылается 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

Я мог бы попытаться избежать этих проблем, используя Rcs, но это звучит так, как будто бы это разрушило цель управления жизненным циклом 0-runtime-cost в Rust.

Еще одна попытка поместить все узлы в 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

Есть ли способ иметь такую ​​структуру с циклическими ссылками без затрат времени выполнения, например, с чистыми ссылками, как я пытался? Я в порядке с дополнительной стоимостью памяти, как поддержка Vec, владеющая всеми узлами.

Да, есть много способов.

Однако очень важно понимать, что Rust требует постоянного соблюдения принципа псевдонимности XOR. Желательно применять его во время компиляции, чтобы иметь 0 затрат времени выполнения, однако иногда требуется управлять им во время выполнения, и для этого есть несколько структур:

• Cell, RefCell, AtomicXXX, Mutex, RWLock (плохо названный) о безопасном мутировании псевдонимов,
• Rc, Weak, Arc, о наличии нескольких владельцев.

Балансировка потенциальных затрат времени выполнения по сравнению с полученной гибкостью - это искусство; это требует некоторого опыта и экспериментов.

---

В вашем конкретном случае (построение грамматики BNF с узлами, ссылающимися друг на друга), мы действительно можем достичь 0 накладных расходов во время выполнения, используя Cell для изменчивости.

Основная трудность, однако, заключается в получении группы узлов с одинаковым временем жизни. Вы на правильном пути с идеей Vec<Node>, но, как вы заметили, как только вы заимствуете один узел, вы не можете изменить Vec еще раз: это потому, что выращивание Vec может заставить его перераспределить основное хранилище, что приведет к зависанию уже полученной ссылки (указывая на освобожденную память).

Общее решение заключается в использовании небезопасного кода для самостоятельного управления временем жизни узлов. Однако вам повезло: как вы упоминали, ваш случай особенный, потому что количество узлов ограничено (по определению грамматики), и вы отбрасываете их все сразу. Это требует арены.

Поэтому мой совет состоит из двух частей:

1. Копить узлы в typed-arena,
2. использование Cell для изменяемой части (&T является Copy).

Вы не сможете хранить арену в той же структуре, что и остальная часть грамматики, без unsafe код; Вам решать, использовать ли unsafe или структурируйте свою программу так, чтобы арена переживала вычисления.