Trie: cannot borrow `_` as mutable more than once at a time

Question

I want to implement some basic methods for Trie.

use std::collections::HashMap;

#[derive(Debug)]
struct TrieNode {
    chs: HashMap<char, TrieNode>,
    value: Option<i32>,
}

#[derive(Debug)]
struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Trie {
        Trie {
            root: TrieNode {
                chs: HashMap::new(),
                value: None,
            },
        }
    }

    fn add_string(&mut self, string: String, value: i32) {
        let mut current_node = &mut self.root;
        for c in string.chars() {
            current_node = current_node.chs.entry(c).or_insert(TrieNode {
                chs: HashMap::new(),
                value: None,
            });
        }
        current_node.value = Some(value);
    }

    fn delete(&mut self, key: &String) -> Option<i32> {
        if key.is_empty() {
            // if key is empty, no need to delete
            return None;
        }
        let mut current_node = &mut self.root;
        for (ind, ch) in key.chars().enumerate() {
            match current_node.chs.get_mut(&ch) {
                Some(node) => {
                    if ind < key.len() - 1 {
                        current_node = node;
                    }
                }
                None => return None,
            }
        }
        // here current_node is actually the previous node of the deleted node
        let temp = current_node.chs.remove(&key.chars().last().unwrap());
        match temp {
            Some(node) => node.value,
            None => None,
        }
    }
}

The method delete is to remove a key (from a Trie) and returns the value corresponding to that key. However, I got the following error.

error[E0499]: cannot borrow `current_node.chs` as mutable more than once at a time
   --> src/main.rs:118:19
    |
118 |             match current_node.chs.get_mut(&ch) {
    |                   ^^^^^^^^^^^^^^^^ mutable borrow starts here in previous iteration of loop

Ibraheem Ahmed · Answer 1 · 2020-11-01T02:45:18.357

0

As the error message explains, you cannot borrow a value (current_node.chs) as mutable more than once at a time.

One solution is to derive the Clone trait for TrieNode. Clone is a common trait for the ability to explicitly duplicate an object:

#[derive(Debug, Clone)]
struct TrieNode {
    chs: HashMap<char, TrieNode>,
    value: Option<i32>,
}

Now instead of borrowing self.root, you can clone it:

fn delete(&mut self, key: &String) -> Option<i32> {
  if key.is_empty() { 
    return None
  }
  // clone `self.root`
  let mut current_node = self.root.clone();
  for (ind, ch) in key.chars().enumerate() {
  match current_node.chs.get_mut(&ch) {
    Some(node) => {
      if ind < key.len() - 1 {
      // clone `node`
        current_node = node.clone();
      }
    // ...

If performance is an issue, then cloning is probably not the best idea. However, it is still an option and may or may not suit your use case.

edited Nov 01 '20 at 02:45

answered Nov 01 '20 at 00:58

Ibraheem Ahmed

11,652
2
48
54

cloning would satisfy the compiler, but it would be fairly extreme to duplicate the whole trie (and again for each subtrie visited) when the goal is just to remove a node – kmdreko Nov 01 '20 at 01:12
@kmdreko If performance is an issue, I agree that cloning is not the best idea. However, it is still an option and may or may not work for the op's use case. I have added a note in my answer regarding performance – Ibraheem Ahmed Nov 01 '20 at 02:44
Although this solution compiled successfully and returned the correct value, I am afraid it didn't delete the node. It just deleted the node in the copied Trie, right? – SpecialYong Nov 01 '20 at 04:41

score 0 · Accepted Answer · answered Nov 01 '20 at 04:32

I'm not exactly sure where the borrow checker is getting tripped up, but you can fix it by hoisting the if check:

    let mut current_node = &mut self.root;
    for (ind, ch) in key.chars().enumerate() {
        if ind < key.len() - 1 {
            match current_node.chs.get_mut(&ch) {
                Some(node) => {
                    current_node = node;
                }
                None => return None,
            }
        }
    }

It skips over even checking if the leaf node exists, but your remove( match already covers that case.

Also, your ind < key.len() - 1 check assumes that the last character is ascii. It may be true for your use case, but if not you can use this answer to iterate until the penultimate character instead.

Your answer works perfectly! Thank you so much. But I don't understand why it can fix the problem simply by adjusting the position of `if` statement, can you explain it a little bit? — SpecialYong, Nov 01 '20 at 05:09
@SpecialYong I can not explain why the original form doesn't work. I've [asked a question](https://stackoverflow.com/q/64639030/2189130) regarding it; hopefully it gets an answer. If this answer solved your question, please consider upvoting and/or accepting it. — kmdreko, Nov 06 '20 at 22:41

Trie: cannot borrow `_` as mutable more than once at a time

2 Answers2