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

Answer 1

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.