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

Question

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
}

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

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.

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

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.

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.

Yes, there are many ways.

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 (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.

---

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.

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. Stash nodes in a typed-arena,
2. Use Cell for the mutable part (&T is Copy).

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.