Yet another fight with the borrow checker

1

I ran into (almost exactly) the 1st problem in this article: Four limitations of Rust’s borrow checker | Considerations on Codecrafting

let's reiterate the problem in this simple example:

use std::collections::HashMap;

struct Cache(HashMap<u32, String>);

impl Cache {
    fn get(&mut self, k: &u32) -> &String {
        if let Some(v) = self.0.get(k) {
            return v;
        }
        self.0.insert(*k, k.to_string());
        self.0.get(k).unwrap()
    }
}

see it in Rust Playground
it won't compile:

error[E0502]: cannot borrow `self.0` as mutable because it is also borrowed as immutable
  --> src/main.rs:10:9
   |
6  |     fn get(&mut self, k: &u32) -> &String {
   |            - let's call the lifetime of this reference `'1`
7  |         if let Some(v) = self.0.get(k) {
   |                          ------ immutable borrow occurs here
8  |             return v;
   |                    - returning this value requires that `self.0` is borrowed for `'1`
9  |         }
10 |         self.0.insert(*k, k.to_string());
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here

For more information about this error, try `rustc --explain E0502`.

clearly borrow checker is at fault here, that's a known fact.

I know refactoring it using HashMap::entry works, like this:

use std::collections::HashMap;

struct Cache(HashMap<u32, String>);

impl Cache {
    fn get(&mut self, k: &u32) -> &String {
        self.0.entry(*k).or_insert_with(|| k.to_string() )
    }
}

see it in Rust Playground
In a way, this is better since it only performs one lookup.

But it's not very flexible, what if I want something a little more complex? like I want to check if a fallback entry exist:

use std::collections::HashMap;

struct Cache(HashMap<u32, String>);

impl Cache {
    fn get(&mut self, k: &u32) -> &String {
        if let Some(v) = self.0.get(k) {
            return v;
        }
        if let Some(v) = self.0.get(&(*k + 42)) {
            return v;
        }
        self.0.insert(*k, k.to_string());
        self.0.get(k).unwrap()
    }
}

fn main() { }

I don't see a way to fix this cleanly.

Another grunt I have is that .entry() wants an owned key, it would be better if it could take a borrow and only calls .to_owned() when required.

2

Use hashbrown directly instead. One thing it exposes is an entry_ref method in addition to a variety of other capabilities that I've personally used.

3 Likes
3

This crate exists too, for the borrow checker portions.

6 Likes
4

this is a classic example of the current borrow checker's limitation, known as "problem case #3" in the NLL rfc.

a new borrow checker called polonius is intended to solve this issue, but last time I checked, it was reported that there was some performance edge cases that delayed polonius from landing on stable, unfortunately.

there's NLL-polonius and fixed-by-polonius labels in the issue tracker you can search for related issues.

if you are on nightly, you can try the -Zpolonius compiler flag. on stable, you can workaround this case with unsafe, but to reduce the chance of accidental unsoundness, it is recommended to use polonius-the-crab crate to do this for you.

5 Likes
5

Thanks to @philomathic_life for pointing me to entry_ref;

And thanks to @quinedot and @nerditation for pointing me to polonius and NLL, this is an eye-opening moment to me. And actually boosted my confidence a little bit, since I thought it's just that I haven't learnt the right pattern to deal with these kinds of problems.

(update, I realized this is not true, but how do I put a strikethrough here?) However, from my understanding, polonius + entry still won't solve the problem in code piece 3? because I want to insert with the original k, if only rust allows upgrading an immutable borrow to an mutable borrow when it's the only borrow.

6

It does, though I'd probably write the tail end using the entry API again.

But that's now how -- instead, you get borrows of different duration depending on if the if let bodies are entered or not, and the shared[1] borrows either expire before the exclusive[2] borrow is created, or don't conflict because you've returned from the method.

  1. immutable ↩︎

  2. mutable ↩︎

2 Likes
7

I was thinking about something like this:

        let vacant = match self.0.entry(k.to_owned()) {
            Entry::Occupied(o) => return o.get(),
            Entry::Vacant(v) => v,
        };

        if let Some(v) = self.0.get(&(*k + 42)) {
            return v;
        }

        vacant.insert(k.to_string())

(it has another problem, but it's not the point)

8

You could do something like this with hashbrown (and polonius).

The standard entry API can't support that (without multiple lookups) due to the fundamental exclusiveness guarantees of &mut _ references (in contrast with shortcomings in the borrow checker).

(Or perhaps if VacantEntry had a get_other(self, key) -> Result<Entry, Self> method, but something like entry_disjoint on HashMap seems more likely to me.)

4 Likes