Trie `insert` implementation & borrowing

[Drip]

Hi, I have the following start of a Trie implementation.

#[derive(Debug)]
struct Trie {
    elem: Option<char>,
    next: Vec<Box<Trie>>,
}

impl Trie {
    fn new_with(elem: char) -> Self {
        Trie {
            elem: Some(elem),
            next: vec![],
        }
    }

    fn insert(&mut self, string: &str) {
        let mut node = self;
        let mut str_iter = string.chars();
        while let Some(ch) = str_iter.next() {
            let maybe_next_node = node.next.iter_mut().find(|tr| tr.elem == Some(ch));
            if let Some(next_node) = maybe_next_node {
                node = next_node;
            } else {
                let mut new_node = Box::new(Trie::new_with(ch));
                unsafe {
                    new_node.insert_linear(str_iter.as_str());
                }
                node.next.push(new_node);
                return;
            }
        }
    }

    /// Adds a string of characters to a leaf node of a Trie.
    /// For example, using insert_linear("cat") on the root node of an empty
    /// Trie gives:
    /// root -> 'c' -> 'a' -> 't'
    ///
    /// ## SAFETY
    /// The resulting Trie cannot have nodes on the same level with the same element.
    unsafe fn insert_linear(&mut self, string: &str) -> &mut Self {
        let mut node = self;
        for ch in string.chars() {
            let next = Trie::new();
            node.next.push(Box::new(next));
            node = node.next.last_mut().unwrap();
            node.elem = Some(ch);
        }
        node
    }
}

However I get the following compiler error:

error[E0499]: cannot borrow `node.next` as mutable more than once at a time
  --> src\trie.rs:36:17
   |
28 |             let maybe_next_node = node.next.iter_mut().find(|tr| tr.elem == Some(ch));
   |                                   -------------------- first mutable borrow occurs here
...
36 |                 node.next.push(new_node);
   |                 ^^^^^^^^^^^^^^^^^^^^^^^^
   |                 |
   |                 second mutable borrow occurs here
   |                 first borrow later used here

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

I'm not sure I understand why node is being borrowed mutably twice here. So why does the compiler complain, and how do I fix it?

[2e71828]

Unfortunately, you've hit one of the corner cases that should work but is beyond the current borrow checker's capabilitites: It can't reason that the first mutable borrow is only used in one branch of the if and shouldn't affect the else branch.

The best workaround right now is to find the correct index first, and then use that to mutably access the child node:

// ...
let maybe_next_node = node.next.iter().enumerate().find(|(_,tr)| tr.elem == Some(ch));
if let Some((i,_)) = maybe_next_node {
    node = &mut node.next[i];
} else {
// ...

Rust Playground

---

_{In the playground, I also replaced your unsafe block with privacy controls, because you aren't doing any unsafe operations: If insert_linear is misused, there won't be any weird UB action-at-a-distance; the Trie just won't operate correctly.}