rust - How can I mutate other elements of a HashMap when using the entry pattern?

Question

I'd like to use a HashMap to cache an expensive computation that's dependent on other entries in the map. The entry pattern only provides a mutable reference to the matched value, but not to the rest of the HashMap. I'd really appreciate feedback on a better way to solve this (incorrect) toy example:

use std::collections::HashMap;
use std::collections::hash_map::Entry::{Occupied, Vacant};

fn compute(cache: &mut HashMap<u32, u32>, input: u32) -> u32 {
    match cache.entry(input) {
        Vacant(entry) => if input > 2 {
            // Trivial placeholder for an expensive computation.
            *entry.insert(compute(&mut cache, input - 1) +
                          compute(&mut cache, input - 2))
        } else {
            0
        },
        Occupied(entry) => *entry.get(),
    }
}

fn main() {
    let mut cache = HashMap::<u32, u32>::new();
    let foo = compute(&mut cache, 12);
    println!("{}", foo);
}

(playground)

The issue with the above snippet is that cache.entry borrows cache immutably, but I would like to update cache as well.

Answer 1

hellow has shown how to get working code, but I want to dive a bit more into why your code does not compile.

The code you have proposed cannot be statically verified to be memory safe. It's entirely possible that your recursive calls attempt to access the same index. Check out this simplified code for one possibility:

use std::collections::{hash_map::Entry, HashMap};

fn compute(cache: &mut HashMap<u32, u32>) {
    if let Entry::Vacant(_entry) = cache.entry(42) {
        let _aliased_mutable_reference = cache.get_mut(&42).unwrap();
    }
}

This now has two mutable references pointing to the same value, violating the rules of references.

Additionally, what if the inner call used entry and it didn't exist?

use std::collections::{hash_map::Entry, HashMap};

fn compute(cache: &mut HashMap<u32, u32>) {
    if let Entry::Vacant(entry1) = cache.entry(42) {
        if let Entry::Vacant(entry2) = cache.entry(41) {
            entry2.insert(2);
            entry1.insert(1);
        }
    }
}

Now, when you insert the value into the map via entry2, the map may reallocate the underlying memory, invalidating the reference held by entry1, violating the other rule of references.

Rust has prevented you from introducing two possible types of memory unsafety into your program; just like it was designed to do.