How to lazily create map entry whose construction uses self in Rust

Question

I'm trying to implement a lazy-construction / memoized evaluation / caching idiom in Rust.

There's an outer type which has a bunch of data and an accessor method. The accessor method needs to either return a cached calculation (if it has one) or calculate it and store the return value in a map for later use. The cached value doesn't need to reference the outer value so there's no circular reference problem; but it does need access to the outer value's data in order to construct itself.

Here's a full example which doesn't pass Rust's borrow checker:

use std::collections::HashMap;

pub struct ContainedThing {
    count: usize,
}

impl ContainedThing {
    fn create(thing: &Thing) -> ContainedThing {
        // create uses an arbitrary number of attributes from Thing
        // it doesn't keep any references after returning though
        let count = thing.map.len();
        ContainedThing { count: count }
    }
}

struct Thing {
    map: HashMap<i32, ContainedThing>,
}

impl Thing {
    pub fn get(&mut self, key: i32) -> &ContainedThing {
        self.map
            .entry(key)
            .or_insert_with(|| ContainedThing::create(&self))
    }
}

fn main() {}

The specific error is:

error[E0502]: cannot borrow `self` as immutable because `self.map` is also borrowed as mutable
  --> src/main.rs:24:29
   |
22 |         self.map
   |         -------- mutable borrow occurs here
23 |             .entry(key)
24 |             .or_insert_with(|| ContainedThing::create(&self))
   |                             ^^                         ---- borrow occurs due to use of `self` in closure
   |                             |
   |                             immutable borrow occurs here
25 |     }
   |     - mutable borrow ends here

I'm having a really hard time figuring out a good way to implement this idiom. I tried pattern matching the return value of get() instead of the entry() API, but still fell foul of the borrow checker: the match expression also ends up borrowing self.

I can rewrite get like this:

pub fn get(&mut self, key: i32) -> &ContainedThing {
    if !self.map.contains_key(&key) {
        let thing = ContainedThing::create(&self);
        self.map.insert(key, thing);
    }
    self.map.get(&key).unwrap()
}

but this is pretty ugly (look at that unwrap) and seems to require more lookups and copies than ought to be necessary. Ideally, I would like

1. to only pay the cost of finding the hash entry once. entry(), done right, ought to track the insertion location when not found.
2. reduce the number of copies of the freshly constructed value. This may be infeasible, ideally I'd have an in-place construction.
3. to avoid using unwrap; without a pointless pattern match, that is.

Is my clumsy code the best that can be achieved?

Answer 1

The answer is that it depends on specifically which state you need access to in the or_insert_with closure. The problem is that or_insert_with definitely cannot have access to the map itself because the entry api takes a mutable borrow of the map.

If all you need for ContainedThing::create is just the size of the map, then you'll just need to calculate the map size ahead of time.

impl Thing {
    pub fn get(&mut self, key: i32) -> &ContainedThing {
        let map_size = self.map.len();
        self.map.entry(&key).or_insert_with(|| {
            // The call to entry takes a mutable reference to the map,
            // so you cannot borrow map again in here
            ContainedThing::create(map_size)
        })
    }
}

I think the spirit of the question was more about general strategies, though, so let's assume there's some other state within Thing that is also required to create ContainedThing.

struct Thing {
    map: HashMap<i32, ContainedThing>,
    some_other_stuff: AnotherType, //assume that this other state is also required in order to create ContainedThing
}

impl Thing {
    pub fn get(&mut self, key: i32) -> &ContainedThing {
        //this is the borrow of self
        let Thing {
            ref mut map,
            ref mut some_other_stuff,
        } = *self;

        let map_size = map.len();
        map.entry(key).or_insert_with(|| {
            // map.entry now only borrows map instead of self
            // Here you're free to borrow any other members of Thing apart from map
            ContainedThing::create(map_size, some_other_stuff)
        })
    }
}

Whether that's really cleaner than your other solution of manually checking if self.map.contains_key(&key) is up for debate. Destructuring tends to be the strategy that I go for, though, to allow borrowing specific members of self instead of the entire struct.

Answer 2

So, the primary motivation for me wanting to pass Thing as an argument to ContainedThing::create was to use Thing's API to help in the construction. However, it turns out that I'll want it to be borrowed mutably, because I need recursive memoized construction here, and that makes it a cycle problem.

So, it looks like my separated check + insert logic is here to stay.