Cache implementation in Rust

Question

I've started learning Rust recently using the Rust book.

In one of the chapters, the authors encourage the reader to experiment with closures, and try to create a generic cache implementation.

I've managed to get it working as below. However, it irks me that I need to add Clone trait on the input argument in the get() method. I was wondering if there was a better way of doing this?

Any other comments are also welcome (apart from the main() method which is a sample driver).

use std::collections::HashMap;
use std::thread;
use std::time::Duration;
use std::hash::Hash;
use std::clone::Clone;

struct Cache<T, U, W>
    where T: Fn(U) -> W,
          U: Eq + Hash + Clone {
    calculator: T,
    values: HashMap<U, W>,
}

impl<T, U, W> Cache<T, U, W>
    where T: Fn(U) -> W,
          U: Eq + Hash + Clone {
    fn new(calculator: T) -> Cache<T, U, W> {
        Cache {
            calculator,
            values: HashMap::new(),
        }
    }

    /*
     * The ugliest part in this function is the constraint that we have to clone the input.
     * HashMap::entry() moves the key, which renders it unusable for subsequent calculations.
     * So we can either
     * - always perform the expensive computation
     * (OR)
     * - clone the input so that it can be re-used later
     *   
     * Another problem is that defining a closure in or_insert_with borrows the Cache::calculator, and that creates a problem
     * when we attempt to borrow it again by invoking self.calculator. This is why the following line won't work:
     * self.values.entry(input.clone()).or_insert_with(|| { (self.calculator)(input) })
     */  
    fn get(&mut self, input: U) -> &W {
        let calc = &self.calculator;
        self.values.entry(input.clone()).or_insert_with(|| { (calc)(input) })
    }   
}

fn main() {
    println!("Hello, world!");
    let mut c = Cache::new(|x: &str| {
        println!("performing an expensive calculation with input: {}", x);
        thread::sleep(Duration::from_secs(2));
        format!("Original input: {}", x)
    });

    let x = c.get("10");
    println!("x: {}, cacher after getting {}", x, 10);

    let x = c.get("10");
    println!("x: {}, cacher after getting {}", x, 10);

    let x = c.get("20");
    println!("x: {}, cacher after getting {}", x, 20);

    let x = c.get("10");
    println!("x: {}, cacher after getting {}", x, 10);

    let x = c.get("10");
    println!("x: {}, cacher after getting {}", x, 10);

    let x = c.get("20");
    println!("x: {}, cacher after getting {}", x, 20);
}

Answer 1

You don't need to have the where clause on your struct. General, rust coders prefer to only restrict the impl blocks and not the structs.

You can avoid Clone, by unpacking the Entry enum, like so:

fn get(&mut self, input: U) -> &W {
    use std::collections::hash_map::Entry;
    match self.values.entry(input) {
        Entry::Occupied(entry) => entry.into_mut(),
        Entry::Vacant(entry) => {
            let value = (self.calculator)(entry.key());
            entry.insert(value)
        }
    }
}   

This is, in fact, close to how or_insert_with is implemented.

Note that this calls the function with &U not U. Your calculator cannot take ownership of the key if you also plan to put into the hashmap. This is awkward for your code because it is using &str as the keys. Hence the type passed to the calculator is &&str. We can resolve this by using the borrow trait. The Borrow traits knows that it can convert &&str to &str, so we could implement it as follows.

// Leave the struct unconstrained
struct Cache<T, U, W> {
    calculator: T,
    values: HashMap<U, W>,
}

// The impl block only constrains for Eq + Hash of the keys.
impl<T, U, W> Cache<T, U, W>
    where 
          U: Eq + Hash
         {

    fn new(calculator: T) -> Cache<T, U, W> {
        Cache {
            calculator,
            values: HashMap::new(),
        }
    }

    // We take a new type parameter, Y.
    // The calculation function takes &Y as a parameter
    // It does not need to be sized because we only use references to it.  
    fn get<Y:?Sized>(&mut self, input: U) -> &W 
        where 
             // Our calculator must take a reference to Y.
             T: Fn(&Y) -> W,
             // The borrow trait will let us convert a &U to a &Y
             U: std::borrow::Borrow<Y> {
        use std::collections::hash_map::Entry;
        match self.values.entry(input) {
            Entry::Occupied(entry) => entry.into_mut(),
            Entry::Vacant(entry) => {
                let value = (self.calculator)(entry.key().borrow());
                entry.insert(value)
            }
        }
    }   
}