Borrow an item inside a nested / tree structure

help
1

I have a tree-like structure of owned elements and some parts of my code need to mutably access specific elements within that structure. A mutable reference to the root of the structure gets passed around to make this possible but accessing the exact elements that I need is inconvenient, here's a simplified example of what I'm talking about:

struct Node {
    children: Vec<Node>,
}

struct Worker {
    node_location: Vec<usize>,
}

impl Worker {
    fn do_the_thing(&mut self, root: &mut Node) {
        let mut node = root;
        for idx in &self.node_location {
            node = &mut node.children[*idx];
        }
        node.the_thing();
    }
}

Now, the code above works and it does what I need it to do, but it has a number of problems, the worst one being that the tree structure changes over time and keeping all the indices up to date is super tricky.

What I would really like to do instead is something like this:

struct Node {
    children: Vec<Rc<RefCell<Node>>>,
}

struct Worker {
    node_location: Rc<RefCell<Node>>,
}

impl Worker {
    fn do_the_thing(&mut self, root: &mut Node) {
        let mude node = self.node_location.borrow_mut();
        node.the_thing();
    }
}

This also works, however, I now no longer have the guarantee that my child node is going to be available, anyone could have a reference to it now and my code could panic.

So basically I'm looking for some kind of reference that only becomes valid when combined with a &mut ref to the root of the tree, or something similar that would let me control who can access the elements of the tree and when.

Any ideas will be much appreciated!

2

Take a look at the qcell crate.

3 Likes
3

Interesting, so I would have a token that would be required to access all the elements. One thing that I forgot to mention is that I would still like to be able to access Node's own children from the node itself without needing any special tokens to do so. But I guess that's a price I have to pay if I use this solution. I'll think about whether it's worth doing it this way, thank you.

4

Perhaps a graph data structure instead of bespoke tree? petgraph is a very popular choice.

Another idea is an arena where you can create your bespoke trees. The "safe cycles" example in the typed_arena docs is good for inspiration.

(I know you don't need cycles. petgraph has a StableGraph data structure that keeps node indices stable in the face of deletes. This can be done in the bespoke tree with BTreeMap<usize, Node> instead of Vec<Node>. And the arena solves the borrowing problem by disallowing dropping individual nodes; the whole arena is dropped in bulk. Just different ways to solve a related group of problems ... including cycles!)

1 Like
5

Yes, that’s about right. In practice, the best thing to do is probably wrap the token and a node reference into some kind of cursor type, and implement most node methods on the cursor instead.