Techniques for recursively mutating a tree, or graph, of nodes?

Below is some boiled down example code. It use integer node IDs into a slotmap of structs, to represent a tree. I could also say it's a graph, since in my actual code the tree will have up-pointers, but they are not shown in this example.

In another programming language, I would implement this layout function by recursively calling layout on the Node's children, and combining the results in some way to get the values for the current Node.

Please ignore the widths and heights and this fake "layout" computation. The only important part, for the example, is that the layout function takes inputs from its caller, uses the results of the recursive calls. This means it cannot easily be changed into a linear iteration. If the recursive calls to layout were in "tail position", or didn't use intermediate results, it would be easier to turn the recursion into a straight iteration.

use slotmap::SlotMap;

type NodeId = slotmap::DefaultKey;

struct Node {
    children: Vec<NodeId>,
    w: f32,
    h: f32
}
impl Node {
    fn layout(&mut self, width: f32, height: f32, collection: &mut Collection) {
        let mut w: f32 = width;
        let mut h: f32 = height;
        for id in &self.children {
            collection.nodes[*id].layout(w, h, collection);
            // Uses children nodes to compture layout result for this node.
            w = w + collection.nodes[*id].w;
            h = h.max(collection.nodes[*id].h);
        }
        self.w = w;
        self.h = h;
    }
}

struct Collection {
    nodes: SlotMap<NodeId, Node>,
    root: Option<NodeId>, 
    width: f32, 
    height: f32
}

impl Collection {
    fn layout(&mut self) {
        let id = self.root.unwrap();
        self.nodes[id].layout(self.width, self.height, self);
    }
}

impl Collection {
    fn layout(&mut self) {
        let id = self.root.unwrap();
        self.nodes[id].layout(self)
    }
}

The problem is of course, that you can't mutably borrow twice.

error[E0499]: cannot borrow `*collection` as mutable more than once at a time
  --> learning/mut_graph.rs:15:48
   |
15 |      collection.nodes[*id].layout(w, h, collection);
   |      ----------------      ------       ^^^^^^^^^^ second mutable borrow occurs here
   |      |                     |
   |      |                     first borrow later used by call
   |      first mutable borrow occurs here

What can be done here? This is also a place where performance matters, so I'd prefer to not add lots of indirection or locking.

1 post - 1 participant

Read full topic