CODEWITHSUNDEEP
dynamicrusttreeborrow-checker
Oliver Walter
Oliver Walter

Reputation: 3

Rust - update tree node with output from children

I'm trying to implement a tree structure where each node is updated using some output from its children.

The output can't be cloned or moved in the final applicaton. I'm running into multiple borrows errors, when I give the node ref's of its children to update it.

I'm using the indextree crate.

Can't get my head around it... Can't find anything like this with this updating behavior.

my example code :

The tree contains dynamic nodes like this

type NodeOutput = i64; //(Can't be copied) wgpu::TextureView in final version  

trait CalcNode {
    fn update(&mut self, input: Vec<&dyn CalcNode>);
    fn output(&self) -> NodeOutput;
}
 
struct NodeModel {
    output: NodeOutput, // generated output ()
    internal: i64,      // some internal state
}
 
impl CalcNode for NodeModel {
    //input can't be cloned/copied in final version
    fn update(&mut self, input: Vec<&dyn CalcNode>) {
        //example for a possible update function
        let child_input: i64 = input.iter().map(|&f| f.output()).sum();
        self.output = self.internal * child_input;
        self.internal += 1 
        // this is only an simplified example 
        //the final version is rendering to a Texture
    }
 
    fn output(&self) -> NodeOutput {
        // output is not copy-able in final version
        self.output
    }
}
 
impl NodeModel {
    fn new(internal: i64) -> Self {
        Self {
            output: internal,
            internal,
        }
    }
}

And then I'm trying to update the tree like this:

use indextree::{Arena, NodeId};

fn main() {
    let (mut arena_, root) = build_tree(); //generate some Tree
    let arena = &mut arena_;
 

    let node_stack: Vec<NodeId> = root.descendants(arena).collect(); //collect all nodes depth first
 

        //update in reverse order deepest node first, ROOT LAST.
        for &n in node_stack.iter().rev() {

            // collect updated children when available
            let children: Vec<&dyn CalcNode> = {
                n.children(arena)
                    .map(|f| arena.get(f).unwrap().get().as_ref())
                    .collect()
            };
 
            //get the node to update
            //--- can't borrow arena here to get the node ---
            let node = { arena.get_mut(n).unwrap().get_mut().as_mut() }; 
 
            // update the node
            node.update(children);
        }
    
}

Upvotes: 0

Views: 238

Answers (1)

apilat
apilat

Reputation: 1510

The CalcNode::update function does not actually need access to its children - really it just wants the value that is calculated from them, so you can move the calculation out of the update function to prevent aliasing references:

fn update(&mut self, child_input: i64) {
    self.output = self.internal * child_input;
    self.internal += 1
}

// <-- Main loop
for &n in node_stack.iter().rev() {
    // collect updated children when available
    let children: Vec<&dyn CalcNode> = {
        n.children(arena)
            .map(|f| arena.get(f).unwrap().get().as_ref())
            .collect()
    };
    //example for n possible update funciton
    let child_input: i64 = children.iter().map(|&f| f.output()).sum();

    //get the node to update
    let node = { arena.get_mut(n).unwrap().get_mut().as_mut() };
    node.update(child_input);
}

Upvotes: 0

Related Questions