Modifying "Cacher" example from book to use Inner Mutability

Hi,

Sorry for my beginners questions... I hope they are not too much out of place here.
I updated the "Cacher" example from the Rust Book to work with generics and to return references.
Now I want to get rid of the &mut self and use the "Inner Mutability" pattern explained in chapter 15 of the book to hold the map with values.

I made two versions -- one which only stores u32 types, and one that should work with generic types.
The one storing u32 works because a u32 can be copied.

However in the generic version I'm trying to return references, and that doesn't work.
When not using inner mutability, the following code works:

    pub struct Cacher<F, V, R>
        where F: Fn(V) -> R
    {
        calculation: F,
        values: HashMap<V, R>,
    }
    ​
    impl<F, V, R> Cacher<F, V, R> where
        F: Fn(V) -> R,
        V: std::marker::Copy + std::cmp::Eq + Hash,
        R: std::marker::Copy,
    {
        // (skipping the ctor)
        pub fn value_ref(&mut self, arg: V) -> &R {
            if !self.values.contains_key(&arg) {
                let result = (self.calculation)(arg);
                self.values.insert(arg, result);
            }
            return &self.values[&arg];
        }
    }

Using a RefCell to wrap around the HashMap however, the compiler complains.

    struct Cacher<F, V, R>
        where F: Fn(V) -> R,
        V: Hash + Eq,
        R: Copy,
    {
        calculation: F,
        values: RefCell<HashMap<V, R>>,
    }

    impl<F, V, R> Cacher<F, V, R>
        where F: Fn(V) -> R,
              V: Hash + Eq + Copy,
              R: Copy,
    {
        fn value_ref(&self, arg: V) -> &R {
            let mut map = self.values.borrow_mut();
            if !map.contains_key(&arg) {
                let result = (self.calculation)(arg);
                map.insert(arg, result);
            }
            &map[&arg] // Compiler error: returns a value referencing data owned by the current function
        }
    }

I tried adding lifetime-annotations but my understanding of them is limited still:

        fn value_ref<'a>(&'a self, arg: V) -> &'a R {

            let mut map = self.values.borrow_mut();
            if !map.contains_key(&arg) {
                let result = (self.calculation)(arg);
                map.insert(arg, result);
            }
            let answer:&'a R = map.get(&arg).unwrap(); // borrowed value does not live long enough
            answer
        }

As far as I can read the code, the lifetime of the values in the map is limited by the lifetime of the Cacher instance so as long as long as I still have that in scope, I should be able to have a reference to one of the values stored in it.
And it works when not wrapping the HashMap in a RefCell.

How do I make the Rust compiler understand, in a safe way, that the results I get out of the map do in fact live long enough to be safely returned from this function?

RefCell provides runtime borrow checking, which depends on interior mutability. To ensure that you never have more than one mutable borrow to something, you must have some kind of a "hook" to signal back that the borrow has ended. Hence, the borrow and borrow_mut functions return something other than &T: a Ref<T> and a RefMut<T> respectively.

The point of both of those is that when they're dropped, they will signal back to the RefCell that it can decrement its borrow counter (Or reset it in the case of RefMut since there can only ever be one unique observer). So, when the compiler gets mad at you in this code:

fn value_ref<'a>(&'a self, arg: V) -> &'a R {
    let mut map = self.values.borrow_mut();
    if !map.contains_key(&arg) {
        let result = (self.calculation)(arg);
        map.insert(arg, result);
    }
    let answer:&'a R = map.get(&arg).unwrap(); // borrowed value does not live long enough
    answer
}

It's because the declaration of map is actually as follows:

let mut map: RefMut<'a, R> = self.values.borrow_mut();

And then we can see where the error comes into play: we try to return a reference to something in map, but the lifetime of that thing in map only lasts until the end of the function, since map only lasts until the end of the function.

You can fix it by returning a RefMut:

fn value_ref<'a>(&'a self, arg: V) -> RefMut<'a, R> {
    let mut map = self.values.borrow_mut();
    if !map.contains_key(&arg) {
        let result = (self.calculation)(arg);
        map.insert(arg, result);
    }
    let answer = RefMut::<'a, _>::map::<R, _>(map, |x| &mut x[arg]);
    answer
}
1 Like

Thanks, I did see that the actual type was RefMut and I do understand that this is the mechanism by which the ref-counting is updated... I also can understand that the variable map indeed goes out of scope, so if the answer would indeed really come from a local map it goes out of scope.
I did not think of returning a RefMut though (or a Ref for that matter).
I also don't find the code of your fix to be easy to read unfortunately -- I wouldn't have come up with it myself and didn't even know that legal syntax!

Thanks, I will be playing around with this and I hope I can properly apply this myself in future... :slight_smile:

If you need it; here's the link to RefMut::map:
https://doc.rust-lang.org/beta/std/cell/struct.RefMut.html#method.map
Note that it doesn't take a self parameter and instead makes you pass the RefMut by itself.

1 Like

Allow me to point out that the RefMut::map call can be simplified:

fn value_ref<'a>(&'a self, arg: V) -> RefMut<'a, R> {
    let mut map = self.values.borrow_mut();
    if !map.contains_key(&arg) {
        let result = (self.calculation)(arg);
        map.insert(arg, result);
    }
    let answer = RefMut::map(map, |x| x.get_mut(&arg).unwrap());
    answer
}

playground

Unfortunately your suggestion doesn't work either, because type HashMap doesn't implement trait IndexMut.

I tried re-borrowing the map non-mutably, and returning a Ref instead of a RefMut. That compiles, but panics at runtime on my first attempt to invoke the cacher.

        fn value_ref<'a>(&'a self, arg: V) -> Ref<'a, R> {

            let mut map = self.values.borrow_mut();
            if !map.contains_key(&arg) {
                let result = (self.calculation)(arg);
                map.insert(arg, result);
            }
            let map = self.values.borrow();
            let answer = Ref::<'a, _>::map::<R, _>(map, |x| &x[&arg]);
            answer
        }

Test:

        #[test]
        fn call_with_different_values() {
            let c = Cacher::new(|a| a);

            let v1 = c.value_ref(1);
            let v2 = c.value_ref(2);
            let v3 = c.value_ref(1);

            assert_eq!(*v1, 1);
            assert_eq!(*v2, 2);
            assert_eq!(*v1, *v3);
        }

Panics right away on the line

let v1 = c.value_ref(1);

The posted code panics because the map you got from borrow_mut() still exists when you call borrow(). You can drop it first:

fn value_ref<'a>(&'a self, arg: V) -> Ref<'a, R> {
    let mut map = self.values.borrow_mut();
    if !map.contains_key(&arg) {
        let result = (self.calculation)(arg);
        map.insert(arg, result);
    }
    drop(map);
    let map = self.values.borrow();
    let answer = Ref::<'a, _>::map::<R, _>(map, |x| &x[&arg]);
    answer
}

See also my previous example that uses get_mut instead of indexing to avoid the missing IndexMut issue. Additionally you can simply use Ref::map(map, |x| &x[&arg]) here as well.

That compiles but likewise panics:

already borrowed: BorrowMutError
thread 'cacher5b::tests::call_with_different_values' panicked at 'already borrowed: BorrowMutError', src\libcore\result.rs:1188:5

That panic is due to your test creating multiple RefMut's at the same time, which is not allowed by RefCell.

I had tried making the first borrow of map go out of scope explicitly by surrounding that bit with { ... } but that didn't have any effect, I forgot about the explicit drop function.

Unfortunately it still panics if my test tries to invoke the value_ref function multiple times, even when explicitly dropping the first borrowed ref.

Sure, but the issue is that in your second call to value_ref, you are creating a RefMut while the Ref returned by the first call to value_ref still exists.

1 Like

Ah, OK I see the problem now...

The Ref still exists in the scope of the test function, of course, even though it is no longer in scope in the value_ref function.

Drat, I didn't think about that.

So returning a Ref or RefMut doesn't make the Cacher a whole lot more usable... I need a way to get rid of the Refs, which I can do in the test function:

        #[test]
        fn call_with_different_values() {
            let c = Cacher::new(|a| a);

            let v1 = *c.value_ref(1);
            let v2 = *c.value_ref(2);
            let v3 = *c.value_ref(1);

            assert_eq!(v1, 1);
            assert_eq!(v2, 2);
            assert_eq!(v1, v3);
        }

This now compiles, and doesn't panic!

Thanks for your help, both of you!

Explicit dropping in the value_ref function is also not needed now, if I surround the part where I need mutability with { ... } to make it a separate block scope -- so that now works as I had expected.

Next to try if it also works with string slices!

Be aware that the reason this works is that your * actually makes a copy of the value, which is why you no longer need to borrow the hash map.

I figured as much, when I started to think about using string slices instead of simple integers.

Attempting to return references to the data in the map is really not worth the trouble then, it seems -- if you need access to multiple values from the same map, it seems you are bound to get into errors with multiple borrows!

There is actually an approach that allows this: Don't create the Ref until you need it. Introduce the following type:

struct CacherRef<'a, V, R> {
    values: &'a RefCell<HashMap<V, R>>,
    key: V,
}
fn value_ref<'a>(&'a self, arg: V) -> CacherRef<'a, V, R> {
    let mut map = self.values.borrow_mut();
    if !map.contains_key(&arg) {
        let result = (self.calculation)(arg);
        map.insert(arg, result);
    }
    CacherRef {
        values: &self.values,
        key: arg,
    }
}

and when you wish to access the data, then you create a Ref using

impl<'a, V, R> CacherRef<'a, V, R>
    where V: Hash + Eq + Copy,
{
    pub fn get(&self) -> Ref<'a, R> {
        let r = self.values.borrow();
        Ref::map(r, |map| &map[&self.key])
    }
}

Note that I removed the Copy bound on the value. Take a look at this playground with test that uses a type that cannot be copied as value.

3 Likes

Wanting to simplify the previous solution, and wanting to learn more about how to Rust, I changed the Cacher code to use Rc values in the HashMap. This works, was easier to do than I had expected, and does away with the extra struct that was introduced to hold results before:

struct Cacher<F, V, R>
    where F: Fn(V) -> R,
    V: Hash + Eq,
{
    calculation: F,
    values: RefCell<HashMap<V, Rc<R>>>,
}

impl<F, V, R> Cacher<F, V, R>
    where F: Fn(V) -> R,
          V: Hash + Eq + Copy,
{
    fn value_ref(&self, arg: V) -> Rc<R> {
        {
            let mut map = self.values.borrow_mut();
            if !map.contains_key(&arg) {
                let result = (self.calculation)(arg);
                map.insert(arg, Rc::new(result));
            }
        }
        Rc::clone(&self.values.borrow()[&arg])
    }
}

And a test:

    #[test]
    fn call_with_str_values() {
        let c = Cacher::new(|a| a);

        let v1 = c.value_ref("abc");
        let v2 = c.value_ref("def");
        let v3 = c.value_ref("abc");

        assert_eq!(*v1, "abc");
        assert_eq!(*v2, "def");
        assert_eq!(*v1, *v3);
    }

See also the full code at this playground, with some tests with different types.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.