How to avoid cloning parts when changing a mutable struct while recursion over that struct

Question

I try to go recursively through a rose tree. The following code also works as intended but I still have the problem that I need to clone the value due to issues with the borrow checker. Therefore, it would be nice if there is a way to change from cloning to something better.

Without the clone() rust complains (rightfully) that I borrow self mutable by looking at the child nodes and the second time in the closure.

The whole structure and code is more complicated and bigger than shown below but that are the core elements. Do I have to change the data structure or do I miss something obvious? If the data structure is the issue how would you change it?

Also, the NType enum seems kinda useless here but I have some additional kinds that I have to consider. Here Inner nodes always have children and Outer nodes never.

enum NType{
    Inner,
    Outer
}

#[derive(Eq, PartialEq, Clone, Debug)]
struct Node {
    // isn't a i32 actually. In my real program it's another struct 
    count: i32,
    n_type: NType,
    children: Option<Vec<usize>>
}

#[derive(Eq, PartialEq, Clone, Debug)]
struct Tree {
    nodes: Vec<Node>,
}

impl Tree{
    
    pub fn calc(&mut self, features: &Vec<i32>) -> i32{
        // root is the last node
        self.calc_h(self.nodes.len() - 1, features);
        self.nodes[self.nodes.len() - 1].count.clone()
    }

    fn calc_h(&mut self, current: usize, features: &Vec<i32>){

        // do some other things to decide where to go into recursion and where not to
        // also use the features

        if self.nodes[current].n_type == Inner{
            //cloneing is very expensiv and destroys the performance
            self.nodes[current].children.as_ref().unwrap().clone().iter().for_each(|&n| self.calc_h(n, features));
            self.do_smt(current)
        }
        self.do_smt(current)
    }
}

Edit:

Lagerbaer suggested to use as_mut but that results into current being a &mut usize and that doesn't really solve the problem.
changed childs into children

the problem here is that it does too much in one line. add interim vars, a normal for loop, and it's much easier to figure it out. the extra problem with clone() is that you operate on copies of node, and whatever you calculate (I suppose you put results inside nodes if you want to mutate them) will be forgotten on the next line. could you complete the code example? there's no calc_h for a node, and childs type seems wrong. — battlmonstr

apilat apilat · Accepted Answer · 2021-09-13T23:27:41

The correct plural of child is children so this is what I will refer to in this answer. Presumably this is what childs means in your code.

Since node.children is already an Option, the best solution would be to .take() the vector out of the node at the start of the iteration and put it in at the end. This way we avoid holding a reference to tree.nodes during the iteration.

if self.nodes[current].n_type == Inner {
    let children = self.nodes[current].children.take().unwrap();
    for &child in children.iter() {
        self.calc_h(child, features);
    }
    self.nodes[current].children = Some(children);
}

Note that the behavior is different from your original code in case of cycles, but this is not something you need to worry about if the rest of the tree is implemented correctly.

How to avoid cloning parts when changing a mutable struct while recursion over that struct

1 Answers