I'm trying to iterate through a hashmap, and depending on the contents of each entry, make a change to a different entry. It's important that I never change the entry I'm looking at. I think that makes the algorithm safe, but I can't seem to persuade Rust of that fact.
The docs for HashMap::get_mut says "Returns a mutable reference to the value corresponding to the key" but the error message suggests that it's trying to lock the hashmap itself:
type Hash = String;
type Hashes = Vec<Hash>;
...
struct RawNode
{ parents : Hashes,
children : Hashes,
...
fn make_bi() -> HashMap<Hash, RawNode> {
let raw_graph = make_raw(); // Reads stdin to make a map of commits with parents known.
// We want to populate the children of each commit.
for (h, n) in raw_graph.iter() {
for ph in n.parents.iter() {
if let Some(p) = raw_graph.get_mut(ph) {
p.children.push(h.to_string());
}
}
}
raw_graph
}
|| cannot borrow `raw_graph` as mutable because it is also borrowed as immutable
|| |
|| 77 | for (h, n) in raw_graph.iter() {
|| | ----------------
|| | |
|| | immutable borrow occurs here
|| | immutable borrow later used here
|| 78 | for ph in n.parents.iter() {
|| 79 | if let Some(p) = raw_graph.get_mut(ph) {
|| | ^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
||
Perhaps it means that the first immutable borrow catches all the entries in its net - the docs don't specify, but surely that's not necessary just to iterate the collection. When the iteration actually returns a particular entry then obviously there'd be a lock on that entry, but there's no reason for the other entries to be locked at the same time.
I saw this question:
Modify value in HashMap while immutably borrowing the whole HashMap
but that author is trying to read and write a given entry at the same time, so I suspect the advice there is overkill for my purposes. It also involves expensive cloning, which in my case I don't think should be necessary.
So what am I misunderstanding, and how do I get around it without ugliness or waste?
Perhaps it means that the first immutable borrow catches all the entries in its net - the docs don't specify, but surely that's not necessary just to iterate the collection.
It is, actually: while it is now possible (though not trivial) until recently Rust's type system was not able to express "borrowing iteration" aka an iteration where an item is only valid during the loop body. Instead, Rust's iteration requires that iteratees are valid for the entire iteration and beyond e.g.
let mut it = raw_graph.iter();
let i1 = it.next();
let i2 = it.next();
let i3 = it.next();
must be legal.
Not that this is relevant in this case, mind.
When the iteration actually returns a particular entry then obviously there'd be a lock on that entry, but there's no reason for the other entries to be locked at the same time.
You're reasoning dynamically but the borrow checker is static, it has no way of knowing that the entry for ph is different than n in all situations (if that even is the case). Thus getting a mutable reference to a value requires getting a mutable reference to the collection to ensure there can not be aliasing, hence the signature of HashMap::get_mut being unambiguous on the subject:
fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
You can do "dynamic borrow checking" via inner mutability e.g. putting a RefCell around your value will let you mutate the underlying value (after a runtime check) through a shared reference.
You can also try using a concurrent map, although that may make the problem worse e.g. while dashmap allows getting mutable sub-references from a shared reference it will deadlock if the same thread holds an outstanding reference to the same shard (internal blocks used to manage concurrent access).