Circular references or Self-references

If you have read some blog posts on Rust, you might have come across the term "circular references" or " self-references", and that it is impossible to have self-references in Rust. Although it is indeed more difficult to have self-references in Rust using traditional references, You can use Rc or Arc to more easily create self-references in Rust.

use std::rc::{Rc, Weak};

struct Node {
    value: usize,
    parent: Option<Weak<Node>>,
    children: Vec<Rc<Node>>,
}

fn build_tree(root_value: usize, nr_of_children: usize) -> Rc<Node> {
    Rc::new_cyclic(|parent| {
        let children = (1..=nr_of_children)
            .map(|i| Rc::new(Node {
                value: root_value + i,
                parent: Some(parent.clone()),
                children: vec![],
            }))
            .collect();

        Node {
            value: root_value,
            parent: None,
            children,
        }
    })
}

fn main() {
    let root = build_tree(10, 5);
    let nr_of_children = root.children.len();
    println!("Root has {nr_of_children} children");

    for child in root.children.iter() {
        if let Some(parent) = child.parent.as_ref().unwrap().upgrade() {
            println!("Root has one child with value {}; its parent value is {}", child.value, parent.value);
        }
    }
}

The Rc::new_cyclic creates a Weak reference to the parent node. This weak smart pointer is what we can use on the children, even before the parent is fully initialized. Weak references do not increment the reference count, unlike Rc references. This is important because we want to avoid reference cycles.

Later in the code, when the parent is fully initialized, we can upgrade the Weak reference to a Rc reference. This is what we do when we print the parent value. At this point, the Rc reference count is incremented by one, and the parent is not deallocated until the child reference is deallocated (or dropped).

Rust Arena

Another way to create self-references in Rust is by using an Arena. An Arena is a data structure that allows you to store a collection of objects in a single memory block. The Arena is responsible for managing the memory and lifetimes of the objects stored in it. This makes it possible to create self-references in Rust without using Rc or Arc.

Sample code

Add typed-arena to your Cargo.toml file.

Cargo.toml

[dependencies]
typed-arena = "2"

Let's create a simple tree structure using an Arena and Cell.

main.rs

use std::cell::Cell;

use typed_arena::Arena;

struct TreeNode<'a> {
    value: i32,
    parent: Cell<Option<&'a TreeNode<'a>>>,
}

fn main() {
    let arena = Arena::new();

    let root = arena.alloc(TreeNode { value: 1, parent: Cell::new(None) });
    let child_1 = arena.alloc(TreeNode { value: 2, parent: Cell::new(None) });
    let child_2 = arena.alloc(TreeNode { value: 3, parent: Cell::new(None) });
    let grandchild = arena.alloc(TreeNode { value: 4, parent: Cell::new(None) });

    child_1.parent.set(Some(root));
    child_2.parent.set(Some(root));
    grandchild.parent.set(Some(child_1));

    let parent = grandchild.parent.get().unwrap();
    println!("Value of grandchild's parent: {}", parent.value);

    let grandparent = parent.parent.get().unwrap();
    println!("Value of grandchild's grandparent: {}", grandparent.value);
}

With an Arena all the objects are stored in a single memory block, and the Arena is responsible for managing the memory and lifetimes of the objects. This makes it possible to create self-references in Rust without using Rc or Arc. In the example above, we create a simple tree structure using an Arena and Cell. The Cell type allows us to update the parent field of a TreeNode after it has been created. This is called "interior mutability".

Reference material