Need help with mutable and immutable use of *self

[ddalton]

Hi, I am struggling to find an elegant performant solution to the common mutable and immutable use of '*self" error.
The issue occurs in my use case if the mutation is done before the immutable use. It works if the order of operations is changed but requires an extra hashmap check which I want to avoid.

The use case is a LRU data structure implemented using 2 hashmaps (l1_map representing a L1 cache and a l2_map representing a L2 cache).
It has 2 methods get and put. When doing a get if the entry is present in the l1_map return it, otherwise if it is present in the l2_map, move it to the l1_map and return it.

This code runs into the cannot borrow '*self' as mutable because it is also borrowed as immutable error.

use core::borrow::Borrow;
use core::hash::Hash;
use hashbrown::HashMap;
use std::{mem::replace, mem::swap, num::NonZeroUsize};

/// An LRU Cache
pub struct LruCache<K, V> {
    l1_map: HashMap<K, V>,
    l2_map: HashMap<K, V>,
    cap: NonZeroUsize,
}

impl<K: Hash + Eq, V> LruCache<K, V> {
    pub fn new(cap: NonZeroUsize) -> LruCache<K, V> {
        LruCache {
            l1_map: HashMap::with_capacity(cap.into()),
            l2_map: HashMap::with_capacity(cap.into()),
            cap,
        }
    }

    pub fn get<'a, Q>(&'a mut self, k: &Q) -> Option<&'a V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if let Some(v) = self.l1_map.get(k) {
            return Some(v);
        }

        match self.l2_map.remove_entry(k) {
            Some((rk, rv)) => {
                self.put(rk, rv);
                self.l1_map.get(k)
            }
            None => None,
        }
    }

    pub fn put(&mut self, k: K, v: V) -> Option<V> {
        if self.l1_map.len() >= self.cap.into() {
            swap(&mut self.l2_map, &mut self.l1_map);
            let _ = replace(&mut self.l1_map, HashMap::with_capacity(self.cap.into()));
        }
        self.l1_map.insert(k, v)
    }

    pub fn cap(&self) -> NonZeroUsize {
        self.cap
    }

    pub fn len(&self) -> usize {
        self.l1_map.len() + self.l2_map.len()
    }

    pub fn is_empty(&self) -> bool {
        self.l1_map.len() == 0 && self.l2_map.len() == 0
    }
}

#[cfg(test)]
mod tests {
    use super::LruCache;
    use core::{fmt::Debug, num::NonZeroUsize};

    fn assert_opt_eq<V: PartialEq + Debug>(opt: Option<&V>, v: V) {
        assert!(opt.is_some());
        assert_eq!(opt.unwrap(), &v);
    }

    #[test]
    fn test_put_and_get() {
        let mut cache = LruCache::new(NonZeroUsize::new(2).unwrap());
        assert!(cache.is_empty());

        assert_eq!(cache.put("apple", "red"), None);
        assert_eq!(cache.put("banana", "yellow"), None);

        assert_eq!(cache.cap().get(), 2);
        assert_eq!(cache.len(), 2);
        assert!(!cache.is_empty());
        assert_opt_eq(cache.get(&"apple"), "red");
        assert_opt_eq(cache.get(&"banana"), "yellow");
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0502]: cannot borrow `*self` as mutable because it is also borrowed as immutable
  --> src/lib.rs:33:17
   |
22 |     pub fn get<'a, Q>(&'a mut self, k: &Q) -> Option<&'a V>
   |                -- lifetime `'a` defined here
...
27 |         if let Some(v) = self.l1_map.get(k) {
   |                          ------------------ immutable borrow occurs here
28 |             return Some(v);
   |                    ------- returning this value requires that `self.l1_map` is borrowed for `'a`
...
33 |                 self.put(rk, rv);
   |                 ^^^^^^^^^^^^^^^^ mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.
error: could not compile `playground` (lib) due to previous error
warning: build failed, waiting for other jobs to finish...
error: could not compile `playground` (lib test) due to previous error

This code is fine if the order of operations is changed, i.e., if the l1_map is modified before it is read.
i.e., the following code is fine:

    pub fn get<'a, Q>(&'a mut self, k: &Q) -> Option<&'a V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        if !self.l1_map.contains_key(k) {
            match self.l2_map.remove_entry(k) {
                Some((rk, rv)) => {
                    self.put(rk, rv);
                }
                None => (),
            };
        }

        return self.l1_map.get(k);
    }

But I want to avoid this extra check of the l1_map.
Is there a way to elegantly change the original code without touching the signature?
I tried using RefCell but was unsuccessful with it.

[steffahn]

You can likely do this using polonius_the_crab - Rust – I’ll see to create some example code

Edit: Here we go ^^

use polonius_the_crab::{polonius, polonius_return};
impl<K: Hash + Eq, V> LruCache<K, V> {
    pub fn get<'a, Q>(&'a mut self, k: &Q) -> Option<&'a V>
    where
        K: Borrow<Q>,
        Q: Hash + Eq + ?Sized,
    {
        let mut this = self;
        polonius!(|this| -> Option<&'polonius V> {
            if let Some(v) = this.l1_map.get(k) {
                polonius_return!(Some(v));
            }
        });

        match this.l2_map.remove_entry(k) {
            Some((rk, rv)) => {
                this.put(rk, rv);
                this.l1_map.get(k)
            }
            None => None,
        }
    }
}

run on rustexplorer.com

[ddalton]

Thanks @steffahn. This looks promising. Will check out polonius.