"Expected type parameter, found reference to type parameter" when implementing a generic cache struct

Question

In the Closures chapter of the second edition of The Rust Programming Language, the writer implements a Cache struct and leaves it with a few problems for the reader to fix up, such as:

Accepting generic parameters and return values on the closure function
Allowing more than one value to be cached

I've attempted to fix those problems but I am quite stuck and can't make it work.

use std::collections::HashMap;
use std::hash::Hash;

struct Cacher<T, X, Y>
where
    T: Fn(&X) -> &Y,
    X: Eq + Hash,
{
    calculation: T,
    results: HashMap<X, Y>,
}

impl<T, X, Y> Cacher<T, X, Y>
where
    T: Fn(&X) -> &Y,
    X: Eq + Hash,
{
    fn new(calculation: T) -> Cacher<T, X, Y> {
        Cacher {
            calculation,
            results: HashMap::new(),
        }
    }

    fn value<'a>(&'a mut self, arg: &'a X) -> &'a Y {
        match self.results.get(arg) {
            Some(v) => v,
            None => {
                let res = (self.calculation)(arg);
                self.results.insert(*arg, res);
                res
            }
        }
    }
}

Where T is the closure function type, X is the argument type and Y is the return value type.

The error I get:

error[E0308]: mismatched types
  --> src/main.rs:30:43
   |
30 |                 self.results.insert(*arg, res);
   |                                           ^^^ expected type parameter, found &Y
   |
   = note: expected type `Y`
              found type `&Y`

I understand this, but I can't think of an elegant solution for the whole ordeal.

Shepmaster Shepmaster · Accepted Answer · 2017-09-29T15:51:43

You've stated that your closure returns a reference:

T: Fn(&X) -> &Y,

but then you are trying to store something that isn't a reference:

results: HashMap<X, Y>,

This is fundamentally incompatible; you need to unify the types.

In many cases, there's no reason to have a reference to a generic type because a generic type can already be a reference. Additionally, forcing the closure to return a reference means that a closure like |_| 42 would not be valid. Because of that, I'd say you should return and store the value type.

Next you need to apply similar logic to value, as it needs to take the argument by value in order to store it. Additionally, remove all the lifetimes from it as elision does the right thing: fn value(&mut self, arg: X) -> &Y.

Once you've straightened that out, apply the knowledge from How to lookup from and insert into a HashMap efficiently?:

fn value(&mut self, arg: X) -> &Y {
    match self.results.entry(arg) {
        Entry::Occupied(e) => e.into_mut(),
        Entry::Vacant(e) => {
            let res = (self.calculation)(e.key());
            e.insert(res)
        }
    }
}

Round it off with some tests that assert it's only called once, and you are good to go. Note that we had to make decisions along the way, but they aren't the only ones we could have chosen. For example, we could have made it so that the cached value is cloned when returned.

use std::collections::HashMap;
use std::collections::hash_map::Entry;
use std::hash::Hash;

struct Cacher<F, I, O>
where
    F: Fn(&I) -> O,
    I: Eq + Hash,
{
    calculation: F,
    results: HashMap<I, O>,
}

impl<F, I, O> Cacher<F, I, O>
where
    F: Fn(&I) -> O,
    I: Eq + Hash,
{
    fn new(calculation: F) -> Self {
        Cacher {
            calculation,
            results: HashMap::new(),
        }
    }

    fn value(&mut self, arg: I) -> &O {
        match self.results.entry(arg) {
            Entry::Occupied(e) => e.into_mut(),
            Entry::Vacant(e) => {
                let res = (self.calculation)(e.key());
                e.insert(res)
            }
        }
    }
}

#[test]
fn called_once() {
    use std::sync::atomic::{AtomicUsize, Ordering};
    let calls = AtomicUsize::new(0);

    let mut c = Cacher::new(|&()| {
        calls.fetch_add(1, Ordering::SeqCst);
        ()
    });

    c.value(());
    c.value(());
    c.value(());

    assert_eq!(1, calls.load(Ordering::SeqCst));
}

"Expected type parameter, found reference to type parameter" when implementing a generic cache struct

1 Answers