CODEWITHSUNDEEP
rust
BowlingHawk95
BowlingHawk95

Reputation: 1648

Are there any constructs I can use to enable mutating a HashMap within a call to HashMap::get?

I'm trying to implement Dijkstra's algorithm in Rust. I am getting an error because I'm mutating a HashMap inside a match expression on a value obtained from .get(). I understand why this is a violation of the borrowing and mutation principles of Rust, but I haven't found a workaround.

I have tried using .entry() and .and_modify() to perform an in-place modification, but I also need to insert and/or modify other keys besides the one being matched on.

Are there any constructs/functions I can use to safely enable this mutation within a get, or, failing that, is there another approach to this algorithm that steers clear of this issue?

(Unfinished) Code Snippet:

use std::collections::{HashMap, HashSet};

struct Graph {
    vertices: Vec<i32>,
    edges: HashMap<i32, HashMap<i32, i32>>, // start -> {end -> weight}
}

fn dijkstra(start: i32, g: Graph) -> HashMap<i32, HashMap<i32, (i32, Vec<i32>)>> {
    let mut known_paths: HashMap<i32, (i32, Vec<i32>)> = HashMap::new(); // end -> (total_weight, path)

    known_paths.insert(start, (0, Vec::new()));

    let mut current = &start;
    let mut unvisited: HashSet<i32> = g.edges.keys().cloned().collect();

    while unvisited.len() > 0 {
        match known_paths.get(current) {
            Some((current_dist, current_path)) => if let Some(ref incident_edges) =
                g.edges.get(current)
            {
                for (neighbor, dist) in incident_edges.iter() {
                    match known_paths.get(&neighbor) {
                        Some((old_distance, _old_path)) => if current_dist + dist < *old_distance {
                            let mut new_path = current_path.clone();
                            new_path.push(*current);
                            known_paths.insert(*neighbor, (current_dist + dist, new_path));
                        },
                        None => {
                            let mut new_path = current_path.clone();
                            new_path.push(*current);
                            known_paths.insert(*neighbor, (current_dist + dist, new_path));
                        }
                    }
                }
            },
            None => panic!("Something went wrong with current={}", current),
        }
    }
    HashMap::new()
}

Error:

error[E0502]: cannot borrow `known_paths` as mutable because it is also borrowed as immutable
  --> src/lib.rs:26:29
   |
17 |         match known_paths.get(current) {
   |               ----------- immutable borrow occurs here
...
26 |                             known_paths.insert(*neighbor, (current_dist + dist, new_path));
   |                             ^^^^^^^^^^^ mutable borrow occurs here
...
37 |         }
   |         - immutable borrow ends here

error[E0502]: cannot borrow `known_paths` as mutable because it is also borrowed as immutable
  --> src/lib.rs:31:29
   |
17 |         match known_paths.get(current) {
   |               ----------- immutable borrow occurs here
...
31 |                             known_paths.insert(*neighbor, (current_dist + dist, new_path));
   |                             ^^^^^^^^^^^ mutable borrow occurs here
...
37 |         }
   |         - immutable borrow ends here

Upvotes: 1

Views: 137

Answers (1)

Matthieu M.
Matthieu M.

Reputation: 300099

No.

I am getting an error because I'm mutating a HashMap inside a match expression on a value obtained from .get(). I understand why this is a violation of the borrowing and mutation principles of Rust, but I haven't found a workaround.

I am afraid you have not actually understood the borrowing principles.

The key principle which underpins Rust's safety is: Mutation NAND Aliasing.

This principle is then enforced either at run-time or at compile-time, with a strong preference for compile-time when feasible since it is free of run-time overhead.

In your situation, you have:

  1. A reference inside HashMap, obtained from HashMap::get().
  2. You attempt to modify said HashMap while holding onto the reference.

Let's imagine, for a second, that some constructs allows this code to compile and run; what would happen? BOOM.

When inserting an element in the HashMap, the HashMap may:

  1. Shuffle existing elements, since it is using Robin Hood hashing.
  2. Transfer all elements to another (larger) heap-allocated array.

Therefore, HashMap::insert means that any existing reference to an element of the HashMap may become dangling and point to either another element, or random memory.

There is no safe way to insert into the HashMap while holding a reference to an element of the HashMap.

You need to find a solution which does not involve keeping a reference to the HashMap.

My advice would be to simply clone: match known_paths.get(current).clone(). Once you have a first working implementation of the algorithm, you can look into possibly improving its performance, as necessity dictates.

Upvotes: 2

Related Questions