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

help
1

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.

2

Untested, but I think you can

impl Node {
    // May make more sense as a method on `Collection`
    fn layout(key: NodeId, width: f32, height: f32, collection: &mut Collection) {
        let mut w: f32 = width;
        let mut h: f32 = height;
        let len = collection.nodes[key].children.len();
        for idx in 0..len {
            let id = collection.nodes[key].children[idx];
            // If you needed to, you could
            // let [this, child] = collection.get_disjoint_mut([key, id]).unwrap();
            Self::layout(id, 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);
        }
        collection.nodes[key].w = w;
        collection.nodes[key].h = h;
    }
}

Alternatives include cloning the children, or use std::mem::take to remove it from nodes[key] before the loop and put it back afterwards. (You'll lose it if there's a panic, if you care.)

1 Like
3

Maybe an alternative would be using Rc<RefCell<>>

struct Collection {
    nodes: SlotMap<NodeId, Rc<RefCell<Node>>>,
...

and

        for id in &self.children {
            let node = collection.nodes[*id].borrow_mut();
            node.layout(w, h, collection);
4

In this case the real code has a trait object with the layout method, so I'm not sure I can follow your example of getting rid of the self parameter. I should have included that in the example code, but I'm never sure which details are relevant when creating a simplified example. I think I can follow your suggestion to use std::mem::take. Also, good to learn about get_disjoint_mute and the "splitting borrows" section of Rustonomicon.

5

A stylistic comment: since the method is recursive, it doesn't concern a single Node, it modifies multiple Nodes, and hence it shouldn't really be a method of Node. It should be a method of Collection.

3 Likes
6

You can't pass both &mut Collection and a &mut Node to something in the Collection (without some sort of shared ownership between). That would mean you can get multiple active &mut to the same Node, but &mut are exclusive references.

7

I like that idea, but I'm having trouble implementing it, because my "nodes" are trait objects. Specifically, they are UI components that know how to perform their version of layout. For example, a VStack has a layout method that lays out its child components in a vertical stack. So ... I feel like I need to call the Node/UIComponent::layout to have that point of extensible polymorphism.

And the "collection" in this case in the Window, which owns its UI components, and contains some other resources shared per-window, like font images and GPU render pipelines.