How can I update a mutable reference in a loop?

Question

I'm trying to implement a Trie/Prefix Tree in Rust and I'm having trouble with the borrow checker. Here is my implementation so far and I'm getting an error when I call children.insert.

cannot borrow *children as mutable because it is also borrowed as immutable

use std::collections::HashMap;

#[derive(Clone, Debug)]
struct PrefixTree {
    value: String,
    children: HashMap<char, PrefixTree>
}

fn insert(mut tree: &mut PrefixTree, key: &str, value: String) {

    let mut children = &mut tree.children;

    for c in key.chars() {    
        if !children.contains_key(&c) {
            children.insert(c, PrefixTree {
                value: String::from(&value),
                children: HashMap::new()
            });
        }
        
        let subtree = children.get(&c);

        match subtree {
            Some(s) => {
                children = &mut s.children;
            },
            _ => {}
        }
    }
    tree.value = value;

}

fn main() {

    let mut trie = PrefixTree {
        value: String::new(),
        children: HashMap::new()
    };

    let words = vec!["Abc", "Abca"];

    for word in words.iter() {
        insert(&mut trie, word, String::from("TEST"));        
    }

    println!("{:#?}", trie);
}

I think this problem is related to Retrieve a mutable reference to a tree value but in my case I need to update the mutable reference and continue looping. I understand why I'm getting the error since I'm borrowing a mutable reference twice, but I'm stumped about how to rewrite this so I'm not doing it that way.

Answer 1

When you're doing multiple things with a single key (like find or insert and get) and run into borrow trouble, try using the Entry API (via .entry()):

fn insert(mut tree: &mut PrefixTree, key: &str, value: String) {
    let mut children = &mut tree.children;

    for c in key.chars() {
        let tree = children.entry(c).or_insert_with(|| PrefixTree {
            value: String::from(&value),
            children: HashMap::new(),
        });

        children = &mut tree.children;
    }
    
    tree.value = value;
}