Borrow checker complains when adding memoization to a function

Question

I want to add memoization to a function which can be kind of costly. I tried to make a minimum example below which demonstrates the error.

use std::collections::{HashMap};

struct Foo {
    data: i64,
    memo: HashMap<i64, String>
}

impl Foo {
    fn new(data: i64) -> Foo {
        let memo = HashMap::new();
        Foo {data, memo}
    }

    fn f(&self, x: i64) -> String {
        (self.data + x).to_string()
    }

    fn f_cached(&mut self, x: i64) -> String {
        match self.memo.get(&x) {
            Some(result) => result.clone(),
            None => {
                let result = self.f(x);
                self.memo.insert(x, result.clone());
                result
            }
        }
    }
}

I remove the f_cached function below then everything compiles, but the cached version refuses to compile; the error I get is:

error[E0502]: cannot borrow `self.memo` as mutable because it is also borrowed as immutable
   --> src/main.rs:173:17
    |
169 |         match self.memo.get(&x) {
    |               --------- immutable borrow occurs here
...
173 |                 self.memo.insert(x, result.clone());
    |                 ^^^^^^^^^ mutable borrow occurs here
...
176 |         }
    |         - immutable borrow ends here

I've tried various reworkings of the basic logic, such as assigning self.memo.get(&x) to a variable, using if let, etc etc, but everything produces the same or a different kind of error. Certainly it doesn't look like there's anything unsafe going on in the code.

Possible duplicate of [How to lookup from and insert into a HashMap efficiently?](https://stackoverflow.com/questions/28512394/how-to-lookup-from-and-insert-into-a-hashmap-efficiently) — loganfsmyth, Mar 20 '18 at 20:21
It's related, but the solution in that thread unfortunately did not solve my problem. I changed the body of `f_cached` to `self.memo.entry(x).or_insert_with(|| { self.f(x) })`, but the borrow checker still complains about the immutable borrow of `self` in the closure. — limp_chimp, Mar 20 '18 at 20:34
How about [HashMap borrow issue when trying to implement find or insert](https://stackoverflow.com/q/24287434/155423). You'll need a separate variable to show it's a disjoint borrow. — Shepmaster, Mar 20 '18 at 20:59
Not a duplicate per-se, but related to https://stackoverflow.com/questions/27335252/how-can-i-call-a-mutating-method-while-holding-a-reference-to-self/27335844#27335844. There's no guarantee that `self.f` won't try to access `self.memo` which would be a bug. — loganfsmyth, Mar 20 '18 at 21:24

score 0 · Answer 1 · edited Mar 20 '18 at 23:05

While other references are correct, note that in the nightly version of the compiler a feature called non-lexical lifetimes is available, which, when enabled, makes your code compilable as it is:

#![feature(nll)]

use std::collections::{HashMap};

struct Foo {
    data: i64,
    memo: HashMap<i64, String>
}

impl Foo {
    fn new(data: i64) -> Foo {
        let memo = HashMap::new();
        Foo {data, memo}
    }

    fn f(&self, x: i64) -> String {
        (self.data + x).to_string()
    }

    fn f_cached(&mut self, x: i64) -> String {
        match self.memo.get(&x) {
            Some(result) => result.clone(),
            None => {
                let result = self.f(x);
                self.memo.insert(x, result.clone());
                result
            }
        }
    }
}

fn main() {}

Playground

The tracking issue for the NLL feature is here. It is currently in active development and probably won't be stable in the nearest future, but it is the direction where Rust is going, and if you're okay with using the nightly version of the compiler, you can just use #![feature(nll)].

*compilable as it is* — true, but less efficient than the linked solutions, which only compute the hashcode once. — Shepmaster, Mar 20 '18 at 23:06

Borrow checker complains when adding memoization to a function

1 Answers1