Borrow checker issues when doing a BFS

Question

I am writing a small program to calculate the critical path on a PERT diagram (https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique) in rust.

I am storing Task objects inside a hashmap. The hashmap is owned by an object called Pert. Each Task object owns two Vec<String> objects, identifying the task's prerequisites and successors, and has an i32 to specify its duration. The tasks are created inside main.rs and added to the Pert object through an add function.

task.rs:

pub struct Task {
    name: String,
    i32: duration,
    followers: Vec<String>,
    prerequisites: Vec<String>
// Additional fields, not relevant for the example
}

impl Task {
    pub fn new(name: &str, duration: i32) -> Task {
        Task {
            name: String::from(name),
            duration: duration,
            followers: Vec::new(),
            prerequisites: Vec::new(),
        }
    }

    pub fn name(&self) -> &str {
        &self.name
    }

    pub fn duration(&self) -> i32 {
        self.duration
    }

    pub fn get_prerequisites(&self) -> & Vec<String> {
        &self.prerequisites
    }

    pub fn get_followers(&self) -> & Vec<String> {
        &self.followers
    }
}

To evaluate the critical path it is necessary to calculate the max sum of duration of all tasks and record the earliest start and finish times of each task, as well as the latest start and finish times. The way that can be done is to add a "begin" and an "end" task that mark the beginning and the end to the graph respectively. Starting from the "begin" task, a BFS is performed on the graph until we get to the "end" task. The BFS is done inside the method completion_time of the Pert object.

In my current implementation I hit a problem with the borrow checker, since I am borrowing mutably the hashmap containing the tasks more than once. I don't see an alternative way to do this other than borrowing twice, but I am very new to rust and have no functional programming experience, so if there is an easy way to do this with functional programming, I can't see it either.

pert.rs:

pub struct Pert {
    tasks: HashMap<String, Task>
}

impl Pert {
    pub fn completion_time(&mut self) -> i32 {
        let mut time = 0;
        let mut q = VecDeque::<&mut Task>::new();

        // put "begin" task at the top of the queue, first mutable borrow of self.tasks
        q.push_back(self.tasks.get_mut("begin").unwrap());
        while !q.is_empty() {
            let old_time = time;
            let mut curr_task = q.pop_front().unwrap();
            for x in curr_task.get_followers() {
                // second mutable borrow of self.tasks happens here
                let task = self.tasks.get_mut(x).unwrap();

                // additional piece of code here modifying other task properties
                time = std::cmp::max(old_time, old_time + task.duration())
            }
        }

        time
    }
}

Building the project with an empty main.rs should be enough to trigger the following error message:

error[E0499]: cannot borrow `self.tasks` as mutable more than once at a time
  --> src/pert.rs:84:28
   |
79 |         q.push_back(self.tasks.get_mut("begin").unwrap());
   |                     ---------- first mutable borrow occurs here
80 |         while !q.is_empty() {
   |                - first borrow later used here
...
84 |                 let task = self.tasks.get_mut(x).unwrap();
   |                            ^^^^^^^^^^ second mutable borrow occurs here

Please try to create a [mre] -- this one is pretty close but there are still a few things missing that make it hard to debug, like the definitions of `duration` and `get_followers`. Thanks! — trent, Mar 23 '21 at 22:16
(Getters and setters for everything aren't particularly idiomatic in Rust, so if you're not doing anything special within `get_followers` you should probably just use `&self.followers` instead.) — trent, Mar 23 '21 at 22:18
@trentcl I have added the definitions inside `Task`, I think this should be enough to trigger the error message at the bottom of the description. Thanks! — antogilbert, Mar 23 '21 at 22:44

score 2 · Accepted Answer · answered Mar 24 '21 at 17:35

The issue here is that you're trying to get multiple mutable references from the HashMap, which owns the tasks and can only safely give out one mutable reference at a time. By changing the VecDeque to take a &Task, and using .get() instead of .get_mut() on the hashmap in completion_time(), the program will compile.

It doesn't look like you're mutating the task in this example, but assuming that you want to modify this example to mutate the task, the best way is to use interior mutability within the Task struct itself, which is usually achieved with the RefCell type. Any value inside of the Task struct that you want to mutate, you can wrap in a RefCell<>, and when you need to mutate the value, you can call .borrow_mut() on the struct field to get a temporarily mutable reference. This answer explains it in a bit more detail: Borrow two mutable values from the same HashMap

Borrow checker issues when doing a BFS

1 Answers1