Could borrow checker do better in the following scenario?

1

Hello,
I am currently stuck with the following problem and looking for some ideas on how to overcome it. Basically, the borrow checker is not allowing me to do something very simple and safe, and to work around this I have to either sacrifice performance or to resort to unsafe code. Consider the following piece of code.

struct StoreEntry;

fn add_entry(key: u32, entry: StoreEntry, store: &mut HashMap<u32, StoreEntry>) {
    let entry_ref: &StoreEntry = store.entry(key).or_insert(entry);
    on_entry_added(entry_ref, store);
}

fn on_entry_added(entry: &StoreEntry, store: &HashMap<u32, StoreEntry>) {
    //
}

This is very simplified version of what I really have. In reality on_entry_added function is part of a trait, and there are several implementations of it. That's why it has to be a separate function.

So that code does not compile because store is considered to be borrowed twice. The first time it is borrowed mutably when we add the entry, and the second time it is borrowed immutably when we pass it to the on_entry_added. I don't necessarily agree with the fact that it is still borrowed mutably. Yes, we created a mutable borrow when we added the entry to the store, however after that we just kept the immutable reference to it, so by the time we call on_entry_added we really have only immutable reference to the store. What safety could be potentially compromised if the code above was allowed? Could borrow checker be potentially improved to handle such situations better in the future?

Now to overcome this I have to rewrite my code to something like this:

fn add_entry(key: u32, entry: StoreEntry, store: &mut HashMap<u32, StoreEntry>) {
    store.entry(key).or_insert(entry);
    on_entry_added(store.get(&key).unwrap(), store);
}

So here I add the entry to the store and then immediately look it up from that store again. This solves the borrow checker problem, but introduces extra runtime overhead which is not very nice.

2

If you were to run the on_entry_added() function you'd effectively need to have a mutable reference to the hashmap (because you're using entry_ref, and that needs to have a shorter lifetime than the original mutable reference taken by store.entry()) and then also an immutable reference to pass to the callback.

That's also why the usual trick of changing mutability with let store = store doesn't work.

fn add_entry(key: u32, entry: StoreEntry, store: &mut HashMap<u32, StoreEntry>) {
    let entry_ref: &StoreEntry = store.entry(key).or_insert(entry);
    let store = store;
    on_entry_added(entry_ref, store);
}

error[E0505]: cannot move out of `store` because it is borrowed
 --> <anon>:6:9
  |
5 |     let entry_ref: &StoreEntry = store.entry(key).or_insert(entry);
  |                                  ----- borrow of `*store` occurs here
6 |     let store = store;
  |         ^^^^^ move out of `store` occurs here

(playground link)

What the borrow checker is trying to do is actually valid (if a little inconvenient), because if your entry_ref could outlive the mutable reference from store.entry(), then later on you could go and add a bunch more keys to store, forcing the underlying buffer to be moved and giving you use-after-free issues.

Getting the entry again feels a bit hacky, but it's the only way I can think of to that would allow you to still follow the lifetime rules.

3

I understand the "use-after-free" issues. However I don't think this would be the case here. We would still have an immutable reference to the store (by having entry_ref still in scope), and an attempt to add a bunch of new keys to the store would result in double borrowing (one mutable, another immutable).

The key problem here in my view is that the borrow checker can't understand that after this line:
let entry_ref: &StoreEntry = store.entry(key).or_insert(entry);
the store is no longer borrowed as mutable. So while the borrow scope of the store is still the same the mutability has changed from mutable to immutable.

4

I probably didn't explain myself very well, but what I was trying to say is that the lifetime of entry_ref must not outlive the mutable borrow of store. Which means that by the very fact that we have a reference to entry_ref, store will still be borrowed mutably.

5

Yes, entry_ref still needs to be counted as a borrow on store, but the idea is that it could be demoted from a &mut borrow to a shared & borrow. However, there are cases where this wouldn't be safe, like with mutexes discussed here:

3 Likes