Unable to port C++ code that inserts into a trie to Rust due to multiple mutable borrows

rust, trie

Solution

See This One Weird Trick To Beat The Borrow Checker: Compilers Hate It.

#[derive(Eq, PartialEq, Debug, Clone)]
struct Trie {
    eow: bool,
    val: char,
    chd: Vec<Trie>,
}

impl Trie {
    fn new(eow: bool, val: char, chd: Vec<Trie>) -> Trie {
        Trie {
            eow: eow,
            val: val,
            chd: chd,
        }
    }

    fn push_word(&mut self, word: &String) {
        let mut trie = self;
        for c in word.chars() {
            if trie.chd.last().map_or(true, |t| t.val != c) {
                trie.chd.push(Trie::new(false, c, vec![]))
            }

            let tmp = trie; // *
            trie = tmp.chd.last_mut().unwrap();
        }

        trie.eow = true;
    }
}

fn main() {}

It is the introduction of the line marked `*` that makes this work. The compiler isn't yet smart enough to see that the mutable sub-borrow of `trie` via `last_mut` is replacing the mutable borrow of `trie`. If it understood this, it would accept the obvious code `trie = trie.chd.last_mut().unwrap();`, but for the moment the programmer has to manually make this guarantee by first moving the borrow out of `trie` and then one is free to reassign. This moves the ownership of the borrow around in a way the compiler can understand.

This is covered by issue #10520.

Problem

I have the following C++ code: ``` #include <vector> #include <string> using namespace std; struct Trie { bool eow; //end of word char val; vector<Trie> chd; //children void push_word(const string& word){ Trie& trie = *this; for (char c: word){ if (trie.chd.empty() || trie.chd.back().val != c) { trie.chd.push_back(Trie{false, c, vector<Trie>{}}); } trie = trie.chd.back(); } trie.eow = true; } }; ``` It's a trie for strings. `push_word` is supposed to only accept strings that are lexicographically greater than any word already contained in the trie; this way the search for the correct child can be skipped at each node. In other words, this allows us to efficiently construct a trie from a sorted vector of words: ``` Trie from_sorted_vector(const vector<string>& words){ Trie trie{false, '\0', vector<Trie>{}}; for (const auto& word: words) { trie.push_word(word); } return trie; } ``` I have the following in Rust: ``` #[derive(Eq, PartialEq, Debug, Clone)] struct Trie { eow: bool, val: char, chd: Vec<Trie>, } impl Trie { fn new(eow: bool, val: char, chd: Vec<Trie>) -> Trie { Trie { eow: eow, val: val, chd: chd, } } fn push_word(&mut self, word: &String) { let mut trie = self; for c in word.chars() { // ??? } } } ``` I can't implement `push_word` in an analogous manner to C++. I always get two mutable borrows or one immutable and one mutable borrow, for `trie` or `trie.chd`, or the last element of `trie.chd`. I'd like to get some directions as to how this should be done.

Original source

Related problems