How to walk a mutually recursive graph in safe Rust?

Question

How do I express mutually recursive structures in Rust? explains how to represent graph-like structures but it does not explain how to walk the graph (only to add more children). The Rc<RefCell<T>> solution I tried to adapt did not compile.

I am looking for a way to design and walk a graph-like structure in safe Rust, utilizing Rc<T> and/or RefCell<T> for interior mutability. My current Node does not compile because of &mut T aliasing rules:

struct Node {
    parent: Option<&mut Node>, // a mutable reference to the Node's owner
    children: Vec<Node>,       // each Node owns its children
}

impl Node {
    fn add_child(&mut self, x: Node) {
        self.children.push(x);
    }
    fn get_child(&mut self, i: usize) -> &mut Node {
        &mut self.children[i]
    }
    fn get_parent(&mut self) -> &mut Node {
        self.parent.expect("No parent!")
    }
}

Example functionality:

let mut top_node = Node::new(None); 

let mut ptr = &mut top_node; 

ptr.add_child(Node::new(&mut ptr)); // add a child to top_node

ptr = ptr.get_child(0); // walk down to top_node's 0th child.

ptr = ptr.get_parent(); // walk back up to top_node

I repeatedly rewrote this implementation replacing &mut T with combinations of Rc, Weak, RefCell, and RefMut to no avail. I don't understand enough about the underlying memory management.

Could someone with more experience using interior mutability explain how to correctly design and walk this graph?

Here is a great source that should help you with your issue. It explains this exact problem in the context of linked lists as well as a few other easy traps to fall into when making these types of data structures. https://rust-unofficial.github.io/too-many-lists/index.html — Locke, Mar 29 '20 at 22:38

springworks00 · Answer 1 · 2020-03-31T16:25:33.980

The key was to use a hybrid Arena/Cell solution. The parents and children are now just references to Nodes, but mutability is enabled using Cell and RefCell:

struct Node<'a> {
    arena: &'a Arena<Node<'a>>,
    parent: Cell<Option<&'a Node<'a>>>,
    children: RefCell<Vec<&'a Node<'a>>>,
}

impl<'a> Node<'a> {
    fn add_child(&'a self) {
        let child = new_node(self.arena);
        child.parent.set(Some(self));
        self.children.borrow_mut().push(child);
    }
    fn get_child(&'a self, i: usize) -> &'a Node<'a> {
        self.children.borrow()[i]
    }
    fn get_parent(&'a self) -> &'a Node<'a> {
        self.parent.get().expect("No Parent!")
    }
}

Now, the Arena owns every node instead of the parents owning their children (this is only an implementation detail and does not hinder any functionality). Resultantly, there is no need to pass the parent to add_child:

let arena: Arena<Node> = Arena::new();
let top_node = new_node(&arena);
top_node.add_child();

let mut ptr = top_node.get_child(0);

ptr.add_child();

ptr = ptr.get_child(0);
ptr = ptr.get_parent();

The solution uses the following helper function to start and keep ownership with the Arena:

fn new_node<'a>(arena: &'a Arena<Node<'a>>) -> &'a mut Node<'a> {
    arena.alloc(Node {
        arena: arena,
        parent: Cell::new(None),
        children: RefCell::new(vec![]),
    })
}

How to walk a mutually recursive graph in safe Rust?

1 Answers1