Need help with tree creation

This is the java code which I am trying to convert in rust for practice. but struck in one error.

   public class Path {
        public String word;
        public Path next;
        public int length;
    }
    public class Nodemapper {
        public Category category = null;
        public int height = MagicNumbers.max_graph_height;
        public StarBindings starBindings = null;
        public HashMap<String, Nodemapper> map = null;
        public String key = null;
        public Nodemapper value = null;
        public boolean shortCut = false;
        public ArrayList<String> sets;

     }
 void addPath(Nodemapper node, Path path, Category category) {
        if (path == null) {
            node.category = category;
            node.height = 0;
        }
        else if (enableShortCuts && thatStarTopicStar(path)) {
            node.category = category;
            node.height = Math.min(4, node.height);
            node.shortCut = true;
        }
        else if (NodemapperOperator.containsKey(node, path.word)) {
            if (path.word.startsWith("<SET>")) addSets(path.word, bot, node);
            Nodemapper nextNode = NodemapperOperator.get(node, path.word);
            addPath(nextNode, path.next, category);
            int offset = 1;
            if (path.word.equals("#") || path.word.equals("^")) offset = 0;
            node.height = Math.min(offset + nextNode.height, node.height);
        }
        else {
            Nodemapper nextNode = new Nodemapper();
            if (path.word.startsWith("<SET>")) {
                addSets(path.word, bot, node);
            }
            if (node.key != null)  {
                NodemapperOperator.upgrade(node);
                upgradeCnt++;
            }
            NodemapperOperator.put(node, path.word, nextNode);
            addPath(nextNode, path.next, category);
            int offset = 1;
            if (path.word.equals("#") || path.word.equals("^")) offset = 0;
            node.height = Math.min(offset + nextNode.height, node.height);
        }
    }

This is the code in Rust .

pub fn add_path_to_node(nodes : &mut HashMap<isize, Nodemapper> ,nodeIdx:isize, path: &mut Path, pathindex : isize, category:Category) -> usize

    {

        let mut pathword = path.get_word(pathindex).to_string();

        let node = nodes.get_mut(&nodeIdx).unwrap();

        if GraphMaster::that_star_topic_star(&path,pathindex as usize)

        {

            //let node = nodes.get_mut(&nodeIdx).unwrap();

            node.category = Some(category);

            node.height = std::cmp::min(4, node.height);

            node.short_cut = true;

            return node.height;

        }

        

       // let node = self.get_node(&nodeIdx);

        if NodemapperOperator::contains_key(node,  &pathword) {

            

            if pathword.starts_with("<SET>"){

                //add sets

            }

           

            let nextNodeIdx = NodemapperOperator::get(node, &pathword);

           

            let nxh = GraphMaster::add_path_to_node(nodes,nextNodeIdx as isize, path,pathindex+1, category);

            let mut offset = 1;

            if pathword == "#" || pathword == "^"  { offset = 0; }

            let nh = std::mem::replace(&mut node.height, 0);

            node.height = std::cmp::min(offset + nxh, nh);

            return node.height;

        }

        else{

            let mut nextnodeidx = nodes.len() as isize;

        

            let n = Nodemapper::new();

            nodes.insert(nextnodeidx, n);

            //(self.nodeIndex.nodes.get_mut(&l).unwrap(),l)

            //let (nextNode,nextnodeidx) = GraphMaster::new_node(graph);

            if  pathword.starts_with("<SET>") {

                //addSets(path.word, bot, node);

            }

            if node.key.is_some() {

               // NodemapperOperator::upgrade(node);

                // upgradeCnt++;

            }

            //NodemapperOperator::put(node, pathword, nextNode);

            let nxh = GraphMaster::add_path_to_node(nodes, nextnodeidx , path,pathindex+1, category);

            let mut offset = 1;

            if pathword == "#" || pathword == "^"  { offset = 0; }

            let nh = node.height.to_owned();

            node.height = std::cmp::min(offset + nxh, nh);

            return node.height;

        }

        return 0 as usize;

    }

But i'm getting this error: cannot borrow *nodes as mutable more than once at a time label

The problem here is your access pattern

/* nodes: &mut HashMap<isize, Nodemapper> */

let node = nodes.get_mut(&nodeIdx).unwrap();

// use `node`

// use/modify `nodes` again

// use/modify `node` again

The underlying problem of such an usage pattern is that the reference to node can become invalidated if nodes is modified. In Rust’s logic, the problem is that in order to modify nodes, you need exclusive access to the HashMap, which means that as soon as you “use/modify `nodes` again”, the node reference becomes invalidated. Trying to use node later anyways leads to the cannot borrow `*nodes` as mutable more than once at a time kind of error message. When you pay attention to the full error message, it is probably going to be pointing out exactly some places where node is defined, where nodes later used and where node is used again after that.

The easiest fix is to just insert a new HashMap access when necessary, i.e.

/* nodes: &mut HashMap<isize, Nodemapper> */

let node = nodes.get_mut(&nodeIdx).unwrap();

// use `node`

// use/modify `nodes` again

// new lookup after `nodes` was modified
let node = nodes.get_mut(&nodeIdx).unwrap();

// use/modify `node` again

For your code, a change like this might do the job

pub fn add_path_to_node(nodes : &mut HashMap<isize, Nodemapper> ,nodeIdx:isize, path: &mut Path, pathindex : isize, category:Category) -> usize
    {
        let mut pathword = path.get_word(pathindex).to_string();
        let node = nodes.get_mut(&nodeIdx).unwrap();
        if GraphMaster::that_star_topic_star(&path,pathindex as usize)
        {
            //let node = nodes.get_mut(&nodeIdx).unwrap();
            node.category = Some(category);
            node.height = std::cmp::min(4, node.height);
            node.short_cut = true;
            return node.height;
        }
        
       // let node = self.get_node(&nodeIdx);
        if NodemapperOperator::contains_key(node,  &pathword) {
            
            if pathword.starts_with("<SET>"){
                //add sets
            }
           
            let nextNodeIdx = NodemapperOperator::get(node, &pathword);
           
            let nxh = GraphMaster::add_path_to_node(nodes,nextNodeIdx as isize, path,pathindex+1, category);
            let mut offset = 1;
            if pathword == "#" || pathword == "^"  { offset = 0; }
+           let node = nodes.get_mut(&nodeIdx).unwrap();
            let nh = std::mem::replace(&mut node.height, 0);
            node.height = std::cmp::min(offset + nxh, nh);
            return node.height;
        }
        else{
            let mut nextnodeidx = nodes.len() as isize;
        
            let n = Nodemapper::new();
            nodes.insert(nextnodeidx, n);
            //(self.nodeIndex.nodes.get_mut(&l).unwrap(),l)
            //let (nextNode,nextnodeidx) = GraphMaster::new_node(graph);
            if  pathword.starts_with("<SET>") {
                //addSets(path.word, bot, node);
            }
+           let node = nodes.get_mut(&nodeIdx).unwrap();
            if node.key.is_some() {
               // NodemapperOperator::upgrade(node);
                // upgradeCnt++;
            }
            //NodemapperOperator::put(node, pathword, nextNode);
            let nxh = GraphMaster::add_path_to_node(nodes, nextnodeidx , path,pathindex+1, category);
            let mut offset = 1;
            if pathword == "#" || pathword == "^"  { offset = 0; }
+           let node = nodes.get_mut(&nodeIdx).unwrap();
            let nh = node.height.to_owned();
            node.height = std::cmp::min(offset + nxh, nh);
            return node.height;
        }
        return 0 as usize;
    }
2 Likes

Thanks @steffahn for such thorough explanation, I have read many blogs, books for the same problem but your explanation is the best.

1 Like

I've use entry on hash maps to get around problems like this. I didn't study the code, so I don't know if it applies in this case. Still, it's a useful tool to keep handy.

The entry API is for accessing map-entries that may or may not be present and allows modifying the entry if present as well as inserting or removing it. It’s mostly useful just as an optimization to avoid having to look up the same key multiple times (which would need to hash it multiple times and search for it in case of collisions multiple times, etc. to determine the right “slot” in the HashMap), in settings such as for example if you only want to insert something if it doesn’t already exist, or remove something if it has a certain value/property. So it’s more of a tool for optimization (and ergonomics) but not so much to alleviate any lifetime problems. In fact, entry does take &mut self just as get_mut, so the same kinds of restrictions apply that you cannot hold onto your Entry while mutating (other parts of) the collection.

More information on “entry API” concept is here in the std::collections docs.