How to avoid mutable borrow after immutable borrow?

Question

I have a struct (Node) that has id: string, child_ids: set[string] and parent_ids: set[string]. Initially only id and parent_ids are passed and I want to fill child_ids later.

Below is my Python code to achieve it. It works without any problem.

from dataclasses import dataclass
from typing import Dict, Set


@dataclass
class Node:
    id: str
    parent_ids: Set[str]
    child_ids: Set[str]
    
    
NodeMap = Dict[str, Node]

def fill_child_ids(node_map: NodeMap):
    for node_id, node in node_map.items():
        for parent_id in node.parent_ids:
            node_map[parent_id].child_ids.add(node_id)

if __name__ == "__main__":
    
    node_map = {
        "n1": Node("n1", set(), set()),
        "n2": Node("n2", set(["n1"]), set()),
        "n3": Node("n3", set(["n2"]), set()),
        
    }
    
    fill_child_ids(node_map)
    
    assert node_map["n1"].child_ids == set(["n2"])
    assert node_map["n2"].child_ids == set(["n3"])

Now I want to do this in Rust. I directly translated the Python code into Rust as follows.

use std::collections::{HashMap, HashSet};

struct Node<'a> {
    id: &'a str,
    child_ids: HashSet<&'a str>,
    parent_ids: HashSet<&'a str>,
}

impl<'a> Node<'a> {
    fn new(id: &'a str, child_ids: HashSet<&'a str>, parent_ids: HashSet<&'a str>) -> Self {
        Self {
            id,
            child_ids,
            parent_ids,
        }
    }
}

type NodeMap<'a> = HashMap<&'a str, Node<'a>>;

fn fill_child_ids(node_map: &mut NodeMap) {
    for (&node_id, node) in node_map.iter() {
        for &parent_id in &node.parent_ids {
            if let Some(parent_node) = node_map.get_mut(parent_id) {
                parent_node.child_ids.insert(node_id);
            }
        }
    }
}

fn main() {
    let mut node_map = HashMap::new();
    node_map.insert("n1", Node::new("n1", HashSet::new(), HashSet::new()));
    node_map.insert("n2", Node::new("n2", HashSet::new(), HashSet::from(["n1"])));
    node_map.insert("n3", Node::new("n3", HashSet::new(), HashSet::from(["n2"])));

    fill_child_ids(&mut node_map);

    assert_eq!(node_map["n1"].child_ids, HashSet::from(["n2"]));
    assert_eq!(node_map["n2"].child_ids, HashSet::from(["n3"]));
}

However this one couldn't be compiled.

error[E0502]: cannot borrow `*node_map` as mutable because it is also borrowed as immutable
  --> src\main.rs:24:40
   |
22 |     for (&node_id, node) in node_map.iter() {
   |                             ---------------
   |                             |
   |                             immutable borrow occurs here
   |                             immutable borrow later used here
23 |         for &parent_id in &node.parent_ids {
24 |             if let Some(parent_node) = node_map.get_mut(parent_id) {
   |                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.

If I modify the fill_child_ids function not to directly loop over iterator of the HashMap, but over copy of the keys, it worked.

fn fill_child_ids(node_map: &mut NodeMap) {
    let node_ids: Vec<&str> = node_map.keys().map(|&node_id| node_id).collect();
    for node_id in node_ids {
        let parent_ids = node_map.get(node_id).unwrap().parent_ids.clone();
        for parent_id in parent_ids {
            if let Some(parent_node) = node_map.get_mut(parent_id) {
                parent_node.child_ids.insert(node_id);
            }
        }
    }
}

But is there any other solution that uses direct loop over the iterator?

Answer 1

Based on the comment from @user4815162342 I found a way by using the RefCell.

type NodeMap<'a> = HashMap<&'a str, RefCell<Node<'a>>>;

fn fill_child_ids(node_map: &NodeMap) {
    for node_ref in node_map.values() {
        let node = node_ref.borrow();
        for parent_id in node.parent_ids.iter() {
            if let Some(parent_node) = node_map.get(parent_id) {
                parent_node.borrow_mut().child_ids.insert(node.id);
            }
        }
    }
}

The point is, the HashMap itself is borrowed immutably while we get mutable borrow of the member by borrow_mut method.

Answer 2

You can clone node_map before accessing its iterator, and you will get an immutable copy of it, which is now a new object and will not conflict with your get_mut() call below it:

fn fill_child_ids(node_map: &mut NodeMap) {
    for (&node_id, node) in node_map.clone().iter() {
        for &parent_id in &node.parent_ids {
            if let Some(parent_node) = node_map.get_mut(parent_id) {
                parent_node.child_ids.insert(node_id);
            }
        }
    }
}