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

Question

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.

score 31 · Accepted Answer · edited Feb 17 '17 at 18:12

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.

First sentence negated what would have been an up-vote from me. — nathanchere, Jun 08 '15 at 12:44
@nathanchere, I hope it helped you, even if you didn't like how I framed it! :) — huon, Jun 09 '15 at 03:18

Shepmaster · Answer 2 · 2018-05-18T16:21:27.580

The original code works once non-lexical lifetimes are enabled:

#![feature(nll)]

#[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, val, chd }
    }

    fn push_word(&mut self, word: &str) {
        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![]))
            }

            trie = trie.chd.last_mut().unwrap();
        }

        trie.eow = true;
    }
}

fn main() {}

NLL increases the precision of the compiler's borrow checker, allowing it to see that the mutable borrow is no longer used.

Until NLL is enabled by default, there is a slightly more streamlined method that accomplishes the same as huon's answer, but without the need of an explicit temporary variable:

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![]))
        }

        trie = { trie }.chd.last_mut().unwrap(); // Here
    }

    trie.eow = true;
}

We enclose the "old" trie in a block, which transfers ownership, creating an unnamed temporary.

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

2 Answers2

Linked