How to avoid key clone while updating and passing a HashMap in idiomatic Rust

I'm trying to write a piece of code that checks if an entry is in a cache, and if it isn't produce the value.

The problem is that to produce the value, I'd like to pass along the cache because the producer might want to use other values, or might want to insert their own.

Current code looks like:

#[derive(Default)]
pub struct R {}

#[derive(Hash, PartialEq, Eq, Clone)]
pub struct Mutation {}

fn create_mutations(s: &Mutation) -> Vec<Mutation> {
    todo!();
}

fn expand(v1: &mut R, v2: &R) {
    todo!();
}

pub fn rec_fn(cache: &mut HashMap<Mutation, R>, s: &Mutation) -> R {
    let mut results: R = R::default();

    let mutations = create_mutations(s);

    for mutation in mutations {
        if cache.get(&mutation).is_none() {
            let r = rec_fn(cache, &mutation);

            cache.insert(mutation.clone(), r);
        }

        let mutations_of_mutation = &cache[&mutation];
        expand(&mut results, mutations_of_mutation);
    }

    results
}

The problem I have is that my Mutation block needs to be Clone.

I am wondering if I can write the block of the cache get & insert differently.

One way that looked promising, but was shut down by the borrow-checker was:

pub fn rec_fn(cache: &mut HashMap<Mutation, R>, s: &Mutation) -> R {
    let mut results: R = R::default();

    let mutations = create_mutations(s);

    for mutation in mutations {

        let mutations_of_mutation = cache.entry(mutation).or_insert_with_key(|m| rec_fn(cache, m));

        expand(&mut results, mutations_of_mutation);
    }

    results
}

With the error:

error[E0500]: closure requires unique access to `*cache` but it is already borrowed
  --> src/main.rs:97:78
   |
97 |         let mutations_of_mutation = cache.entry(mutation).or_insert_with_key(|m| rec_fn(cache, m));
   |                                     --------------------- ------------------ ^^^        ----- second borrow occurs due to use of `*cache` in closure
   |                                     |                     |                  |
   |                                     |                     |                  closure construction occurs here
   |                                     |                     first borrow later used by call
   |                                     borrow occurs here

I understand WHY this happens. But is there a way to write this without having clone mutation?

Solution 1:

There are four steps in the inner loop:

1. Check if key is cached
2. Calculate value to insert (if necessary)
3. Insert new value into cache (if necessary)
4. Pass cache value by reference to expand

Steps 1 and 4 require shared references to cache, while steps 2 and 3 require mutable references to cache. A conflict between these borrows can be avoided by keeping these steps separate. In step 3, we must transfer ownership of mutation to cache, but we can keep a reference to the inserted value with the entry API without needing to clone the key.

Updated code shown below:

use std::collections::HashMap;

#[derive(Default)]
pub struct R {}

#[derive(Hash, PartialEq, Eq)]
pub struct Mutation {}

fn create_mutations(s: &Mutation) -> Vec<Mutation> {
    todo!();
}

fn expand(v1: &mut R, v2: &R) {
    todo!();
}

pub fn rec_fn(cache: &mut HashMap<Mutation, R>, s: &Mutation) -> R {
    let mut results: R = R::default();

    let mutations = create_mutations(s);

    for mutation in mutations {
        // 1. check if key is in cache
        let cached = cache.contains_key(&mutation);

        // 2. calculate value to insert, if necessary
        let to_insert = if cached {
            None // already cached, no need to re-calculate
        } else {
            Some(rec_fn(cache, &mutation))
        };

        // 3. fetch, or insert and keep a reference
        let mutations_of_mutation = match to_insert {
            None => &cache[&mutation],
            Some(r) => cache.entry(mutation).or_insert(r),
        };

        // 4. pass value on to `expand`
        expand(&mut results, mutations_of_mutation);
    }

    results
}

(playground link)