[Borrow checker][Recursion] Traversing and mutating a tree


#1

This is yet another request for help with the borrow checker. Sorry.
It seems to me the borrow checker is fundamentally at odds with my use of recursion.
I am traversing a slice of a tree and mutating an LRU along the way.
The LRU is passed mutably, recursively (through self, but that hardly matters).
It seems like I have to rewrite the simple recursive algorithm.
Instead, I could use a vec of iterators (one item per level of the tree) to build my own iterator. Is that correct?


#2

Can you provide a cut down example of what you’re trying to do? You should be able to recursively visit all the nodes in a tree mutating some internal state along the way. One example I can think of is the Visitor trait in the Rust parser.

Here’s a rough implementation of how I’ve done something like this in the past: https://is.gd/CQi7al


#3

My code looks like this:

fn _scan_range(&mut self, alloc_id: u64, bounds: (Bound<Vec<u8>>, Bound<Vec<u8>>)) {
    let children = self.lru.get_mut(&alloc_id).unwrap().ensure_children(self.sb);
    for (_, mut cl) in children.range_mut(bounds.clone()) {
        match *cl {
            ChildLink::Loaded(alloc_id) => {
                self._scan_range(alloc_id, bounds.clone());
            }
            ChildLink::Unloaded(logical) => {
                let alloc_id = self.preload(logical);
                *cl = ChildLink::Loaded(alloc_id);
                self._scan_range(alloc_id, bounds.clone());
            }
        }
    }
}

The LRU is borrowed mutably, then self is used again to call preload (which writes to the LRU) and _scan_range.

(The LRU is a HashMap for now, and children is a BTreeMap).


#4

What’s the particular error the compiler is giving you? It looks like you’re trying to take a second mutable borrow of self when you try to recursively scan the children, while you already have a mutable borrow of self live through the cl variable. That’d normally be an iterator invalidation bug (what happens when the LRU needs to grow?) which is why Rust isn’t letting you compile.

It sounds like you may want to use a RefCell here. Otherwise you may need to rethink the algorithm being used.

If you can, try to formulate the question using a simpler example. Having to break down the problem into a minimal example might help you realise why the compiler is rejecting your code, and how you can restructure it to make the compiler happy.


#5

The error is as you described.

error[E0499]: cannot borrow `*self` as mutable more than once at a time
   --> src/main.rs:153:21
    |
149 |         let children = self.lru.get_mut(&alloc_id).unwrap().ensure_children(self.sb);
    |                        -------- first mutable borrow occurs here
...
153 |                     self._scan_range(alloc_id, bounds.clone());
    |                     ^^^^ second mutable borrow occurs here
...
162 |     }
    |     - first borrow ends here

I’ll try with a RefCell.
As for rethinking the algorithm, my idea is to keep track of the iterator stack and get rid of the recursive calls.


#6

I guess you could always use iteration instead of recursion, but that’s… unsatisfying. Would reformulating it as something like this work?

fn visit_link(&mut self, child: &mut ChildLink) {
    if let ChildLink::Unloaded(logical) = child {
        let id = self.preload(logical);
        *child = ChildLink::Loaded(id);  // may need std::mem::swap()
    }        

    let children = ...;
    for child in children.range_mut(&self.bounds) {
        self.visit_link(child);
    }
}

#7

So I didn’t have to restructure most of my code, but I solved this by introducing interior mutability (one Cell, one RefCell, one Rc<RefCell<_>>). It’s not super satisfying, but I think it was unavoidable. A good lazy initialisation library might have removed the need for the second RefCell.


#8

I recently found I needed to introduce a recursion stack rather than explicitly recursing a directed graph in order to avoid a stack overflow. It wasn’t that painful, although it was annoying. I think it did make my algorithm more clear, though.