cannot borrow as mutable more than once at a time + the variable is a mutable queue

Question

I'm trying to traverse a graph and extract a sub-tree out of it based on the criteria which is defined in my code. The details of the graph or the criteria is not important. However, the process of creating the tree has been very challenging due to the complexity of references and borrowing in rust. I'm not pro in rust.

To make it simple, I have 2 functions:

1. The first one gets the graph, the depth of graph to traverse and return a sub-tree of type ScriptTree which is a struct.

fn run_subsequent_scripts(&self, graph: &PageGraph, depth: usize) ->  ScriptTree {
    let mut level: usize;
    let mut visited: HashMap<NodeId, bool> = HashMap::new();
    // create a queue for BFS
    let mut queue = vec![];
    // Starting vertex maked as visited and added to queueu
    let script_info = get_script_info(graph, self.query.id);
    let mut root = ScriptTree::new(script_info.0 ,script_info.1, script_info.2);
    
    visited.insert(self.query.id, true);
    queue.push(&mut root);
    
    let mut level_meter: Vec<NodeId> = Vec::new();
    
    // continue until queue is empty
    while queue.len() != 0 && level_meter.len() < depth {
        level = queue.len();

        while level != 0 {
          // Get the front of the queue and remove it
          let mut child_node: ScriptTree;
          let parent_node = queue.remove(0);
          level -= 1;
          // Get all adjacent vertices from that vertex
          // neighbors of the parent
          let neighbors: Vec<NodeId> = get_injected_scripts(&graph,    parent_node.script_info.script_node_id, &Action::script());
          let mut neighbor_nodes: Vec<ScriptTree> = Vec::new();
          for child_id in neighbors {
              if !visited.contains_key(&child_id) {
              //mark as visited
              visited.insert(child_id, true);
              // push back to check this vertex's vertices
              let child_script_info = get_script_info(graph, child_id);
              child_node = ScriptTree::new(child_script_info.0, child_script_info.1, child_script_info.2);
              queue.push(&mut child_node);
              neighbor_nodes.push(child_node);
              level_meter.push(child_id);
              }
          }
        self.update_tree(&mut root, &parent_node, neighbor_nodes);
        }
        level += 1;
    } 
  return root
  }

2. The second function updates the tree by adding the children of the parent_node captured in node_neighbors vectored in the previous function:

fn update_tree(&self, subtree: &mut ScriptTree, parent_node: &ScriptTree, node_neighbors: Vec<ScriptTree>) {
    if subtree.node_id == parent_node.node_id {
      // Return a reference to this node if it has the target ID
      for child in node_neighbors{
        subtree.add_child(child);
      }
    }
    else {

      // Recursively search the children of this node
      for mut child in &subtree.children {
          self.update_tree(&mut child, parent_node, node_neighbors);
      }
    }    
  }

This code gives me error in multiple lines:

In function 1,

• In line child_node = ScriptTree::new(child_script_info.0, child_script_info.1, child_script_info.2); it says "cannot assign to child_node because it is borrowed assignment to borrowed child_node occurs here".
• In line queue.push(&mut child_node); it says "cannot borrow child_node as mutable more than once at a time child_node was mutably borrowed here in the previous iteration of the loop"
• In line neighbor_nodes.push(child_node); it says "cannot move out of child_node because it is borrowed move out of child_node occurs here"
• and in line self.update_tree(&mut root, &parent_node, neighbor_nodes); it says "cannot borrow root as mutable more than once at a time second mutable borrow occurs here"

In function 2:

• In line self.update_tree( &mut child, parent_node, node_neighbors); it says:

1. cannot borrow data in a & reference as mutable cannot borrow as mutable
2. use of moved value: node_neighbors value moved here, in previous iteration of loop

I appreciate any help to solve the issue!

Answer 1

In run_subsequent_scripts:

• Change let mut child_node: ScriptTree to let child_node: ScriptTree.
  • Declare child_node without initializing it, which allows assigning to it later without borrowing it mutably.
• Change queue.push(&mut root) to queue.push(root).
  • Pass a non-mutable reference to root to the queue, which should allow us to borrow it mutably later.
• Change let mut neighbor_nodes: Vec<ScriptTree> = Vec::new() to let mut neighbor_nodes = Vec::with_capacity(neighbors.len()).
  • Pre-allocate the neighbor_nodes vector with enough capacity to hold all the neighbors, which should avoid the need for any reallocation that might cause issues with borrowing.
• Change the loop where you iterate over the neighbor_nodes vector to use for child_node in node_neighbors.into_iter() instead.
  • Consume the node_neighbors vector and allows moving the ScriptTree values out of it without borrowing them.

In update_tree:

• Change for mut child in &subtree.children to for child in &mut subtree.children.
  • Allows borrowing the children of subtree mutably, which is necessary to update them.

Updated Code with sample inputs (Rust Playground):

use std::collections::HashMap;

#[derive(Debug, Clone, Hash, PartialEq, Eq)]
struct NodeId(u32);

#[derive(Debug)]
struct PageGraph;

#[derive(Debug, Clone)]
struct ScriptInfo(u32, u32, u32);

#[derive(Debug, Clone)]
struct ScriptTree {
    script_info: ScriptInfo,
    children: Vec<ScriptTree>,
}

impl ScriptTree {
    fn new(a: u32, b: u32, c: u32) -> Self {
        ScriptTree {
            script_info: ScriptInfo(a, b, c),
            children: Vec::new(),
        }
    }

    fn add_child(&mut self, child: ScriptTree) {
        self.children.push(child);
    }
}

enum Action {
    Script,
}

fn get_injected_scripts(
    _graph: &PageGraph,
    _node_id: u32,
    _action: &Action,
) -> Vec<NodeId> {
    vec![NodeId(1), NodeId(2), NodeId(3)]
}

fn get_script_info(_graph: &PageGraph, _node_id: NodeId) -> ScriptInfo {
    ScriptInfo(1, 2, 3)
}

struct Query {
    id: NodeId,
}

struct Example {
    query: Query,
}

impl Example {
    fn run_subsequent_scripts(&self, graph: &PageGraph, depth: usize) -> ScriptTree {
        let mut level: usize = 0;
        let mut visited: HashMap<NodeId, bool> = HashMap::new();
        let mut queue = vec![];
        let script_info = get_script_info(graph, self.query.id.clone());
        let mut root = ScriptTree::new(script_info.0, script_info.1, script_info.2);

        visited.insert(self.query.id.clone(), true);
        queue.push(root.clone());

        let mut level_meter: Vec<NodeId> = Vec::new();

        while !queue.is_empty() && level < depth {
            let level_size = queue.len();

            for _ in 0..level_size {
                let mut neighbor_nodes = Vec::new();
                let parent_node = queue.remove(0);
                let neighbors = get_injected_scripts(&graph, parent_node.script_info.0, &Action::Script);

                for child_id in neighbors {
                    if !visited.contains_key(&child_id) {
                        visited.insert(child_id.clone(), true);
                        let child_script_info = get_script_info(graph, child_id.clone());
                        let child_node = ScriptTree::new(
                            child_script_info.0,
                            child_script_info.1,
                            child_script_info.2,
                        );
                        queue.push(child_node.clone());
                        neighbor_nodes.push(child_node);
                        level_meter.push(child_id);
                    }
                }
                self.update_tree(&mut root, &parent_node, neighbor_nodes);
            }
            level += 1;
        }
        root
    }

    fn update_tree(
        &self,
        subtree: &mut ScriptTree,
        parent_node: &ScriptTree,
        node_neighbors: Vec<ScriptTree>,
    ) {
        if subtree.script_info.0 == parent_node.script_info.0 {
            for child_node in node_neighbors {
                subtree.add_child(child_node);
            }
        } else {
            for child in &mut subtree.children {
                self.update_tree(child, parent_node, node_neighbors.clone());
            }
        }
    }
}

fn main() {
    let graph = PageGraph;
    let example = Example {
        query: Query { id: NodeId(1) },
    };
    let depth = 1;
    let script_tree = example.run_subsequent_scripts(&graph, depth);
    println!("{:#?}", script_tree);
}

Best practice: Providing a minimum viable example code (in question) that can be executable by others.