Rust book chapter 13: difficulty understanding how to improve the Cacher type

Apologies if what I'm asking has a completely obvious solution, but I just can't see it.

The Rust book section Limitations of the Cacher Implementation ends by saying this:

Try modifying Cacher to hold a hash map rather than a single value. The keys of the hash map will be the arg values that are passed in, and the values of the hash map will be the result of calling the closure on that key. Instead of looking at whether self.value directly has a Some or a None value, the value function will look up the arg in the hash map and return the value if it’s present. If it’s not present, the Cacher will call the closure and save the resulting value in the hash map associated with its arg value.

The second problem with the current Cacher implementation is that it only accepts closures that take one parameter of type u32 and return a u32 . We might want to cache the results of closures that take a string slice and return usize values, for example. To fix this issue, try introducing more generic parameters to increase the flexibility of the Cacher functionality.

I gave it a go, and ended up with this code. When I try to run it, I get errors to do with lifetimes, errors that at this point I have no idea how to fix or what their cause is. The test code seems all whacked up too, since I'm having to pass references to integer literals, but Cacher::value() doesn't seem like a function that should be taking ownership of its arguments. I seem to have gone into the weeds with the generics here, and so I'd appreciate a guide who could set me back on the right path.

You need to take it by value in Cacher::value since otherwise you cannot put it in the HashMap. On the other hand you'll have to return a reference, since the value is also stored in the HashMap.

I recommend using the entry api.

Thanks. I tried changing Cacher::value() to take a value and return a reference. I also tried changing it so it uses the entry API, but I'm not sure I did it as intended. The error is now more easily understood but I'm stuck again: I now get an error to do with using arg after moving because P does not implement the Copy trait. Is there no way to get this working without adding the Copy trait constraint? I'm also not sure why Cacher::value() insists on taking a reference for the arg parameter even though I don't seem to be defining it that way, or why I'm having to double dereference the returned value in the test.

The core of the issue is here:

    fn value(&mut self, arg: P) -> &R {
        self.values.entry(arg).or_insert((self.calculation)(arg))
    }

Looking at the signature for HashMap::entry:

pub fn entry(&mut self, key: K) -> Entry<K, V>

we can see that it takes ownership of key. This is because the hashmap needs to own its keys. However, the calculation closure also takes ownership of its argument, so that can't work. Either the closure needs to be able to do its work without owing its argument (such as calculating a new value based on the argument), or an independent copy of the argument needs to be created so one can be given to each.

The common way to do that is to require that P implements Clone and change the line to:

        self.values.entry(arg.clone()).or_insert((self.calculation)(arg))

This has she downside that clone is always called, despite the fact that it should only be necessary when arg doesn't already exist inside the hashmap. I'll leave figuring out a way to only call clone when necessary for you to investigate.

Actually that's not true. While or_insert_else doesn't provide access to the key, you can totally just match on the entry:

fn value(&mut self, arg: P) -> &R {
    use std::collections::hash_map::Entry;
    match self.values.entry(arg) {
        Entry::Occupied(entry) => entry.into_mut(),
        Entry::Vacant(entry) => {
            let v = (self.calculation)(entry.key());
            entry.insert(v)
        }
    }
}

@Case
You might want to consider returning *num in expensive_result instead of num, since T: Fn(&P) -> R means the input is a reference, and if you return &P directly you get R = &P.

Also note that you're running expensive_result.value(&intensity), so since we changed Cacher::value to take it by value, it's inferring that P should be &u32. This actually works, since references implement Eq and Hash if their underlying values do, but it's probably better not to borrow.

This is also why you get &&u32 in the errors: if P = &u32 and R = &P then R = &&u32.

1 Like

Thanks a ton! It seems to work now.