Cannot borrow `*self` as mutable more than once in a recursive function

[bruce-wayne]

I've this associated function, where self.words: HashMap<String, Vec<String>>:

fn helper(&mut self, word: &String, defn: &String) {
    let defns = self.words.entry(word.to_string()).or_default();
    let n = defns.len();

    if n == 0 || Some(&(defn.clone(), n - 1)) != defns.last() {
        if defn != word && defn.starts_with(word) {
            let d = defn.clone();
            self.helper(&d, &d);
        }
        defns.push((defn.to_string(), n));
    };
}

I get an error:

84 |         let defns = self.words.entry(word.to_string()).or_default();
   |                     ---------------------------------- first mutable borrow occurs here
...
90 |                 self.helper(&d, &d);
   |                 ^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here
91 |             }
92 |             defns.push((defn.to_string(), n));
   |             --------------------------------- first borrow later used here

I've read this answer, and tried using a RefCell, but that just led to a different error:

85 |         let defns = self.words.borrow_mut().entry(word.to_string()).or_default();
   |                     ----------------------- immutable borrow occurs here
...
91 |                 self.helper(&d, &d);
   |                 ^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
92 |             }
93 |             defns.push((defn.to_string(), n));
   |             --------------------------------- immutable borrow later used here

[bruce-wayne]

Replying to self, I was able to rewrite the function as follows. The latest version is certainly not as clear as the original one, so, I am convinced that the borrow checker has ways to improve.

fn helper(&mut self, word: &String, defn: &String) {
    if defn != word && defn.starts_with(word) {
        let d = defn.clone();
        self.helper(&d, &d);
    }
    let m = self.words.get(defn)
            .map(|d| d.len() - 1)
            .unwrap_or(0);
    let defns = self.words.entry(word.to_string()).or_default();
    let n = defns.len();

    if n == 0 || Some(&(defn.clone(), n - 1)) != defns.last() {
        defns.push((defn.to_string(), m));
    };
}

[bjorn3]

The original function you posted can't work no matter how the borrow checker changes. You are mutably borrowing an entry in self.words, but the recursive call may invalidate self.words (and in fact it does if self.words is a HashMap and .entry() causes the backing storage to resize), which would cause memory corruption when you try to access the entry again. This is effectively the same issue as iterator invalidation that the borrow checker prevented here.

[kornel]

OT: Use &str instead of &String.

The &String type doesn't make sense: it requires the string to be able to grow (this is the key difference between String and Box<str> or &str), but at the same time asks for read-only loan of that type that forbids it from ever growing. It's also a double indirection (performance cost), because String itself has a pointer to string data.

String can dereference to &str for free, so outside of generic contexts you should never need &String.

[chetmurthy]

I don't know if I'm alone in this, but I'm following this post with some interest, b/c it seems to me that an important class of codes that I don't know how to do (yet) is recursive functions that mutate recursive data-structures. For instance, I saw an AVL-tree implementation in Rust ( Understanding Rust Through AVL Trees ) and while it was quite nice, it wasn't recursive. And to boot, it required use of unsafe for a key bit.

In the past I've written an attribute-grammar evaluator-generator, and the generated code was pretty complicated, performing mutations all over the place. It used parent-pointers, but those could have been elided in favor of recursion. There are other pretty complex algorithms over trees that I'd want to implement (having done so in the past) that also mutate their data.

So I'm pretty interested in whether and how this all works out.