做 BFS 时借用检查器问题

Question

我正在编写一个小程序来计算 PERT 图 (https://en.wikipedia.org/wiki/Program_evaluation_and_review_technique) 中的关键路径。

我正在将 Task 个对象存储在哈希图中。哈希图由一个名为 Pert 的对象拥有。每个 Task 对象拥有两个 Vec<String> 对象，标识任务的先决条件和后续任务，并有一个 i32 来指定其持续时间。任务在 main.rs 中创建并通过 add 函数添加到 Pert 对象。

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
    }
}

要评估关键路径，需要计算所有任务的最大持续时间总和，并记录每个任务的最早开始和结束时间，以及最晚开始和结束时间。可以做到的方法是添加一个“开始”和“结束”任务，分别标记图形的开始和结束。从“开始”任务开始，对图执行 BFS，直到我们到达“结束”任务。 BFS 在 Pert 对象的方法 completion_time 中完成。

在我当前的实现中，我遇到了借用检查器的问题，因为我不止一次地以可变方式借用包含任务的哈希图。除了借用两次之外，我没有看到其他方法可以做到这一点，但我对生锈很陌生并且没有函数式编程经验，所以如果有一种简单的方法可以用函数式编程来做到这一点，我看不到它要么。

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
    }
}

用空 main.rs 构建项目应该足以触发以下错误消息：

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

Answer 1

这里的问题是您试图从 HashMap 获取多个可变引用，它拥有任务并且一次只能安全地给出一个可变引用。通过将 VecDeque 更改为采用 &Task，并在 completion_time() 中的 hashmap 上使用 .get() 而不是 .get_mut()，程序将编译。

在这个例子中你看起来不像是在改变任务，但假设你想修改这个例子来改变任务，最好的方法是在 Task 结构本身中使用内部可变性，这通常使用 RefCell 类型实现。 Task 结构中任何你想改变的值，你可以包装在 RefCell<> 中，当你需要改变值时，你可以在结构字段上调用 .borrow_mut() 来临时获得一个可变参考。这个答案更详细地解释了它：

做 BFS 时借用检查器问题

Borrow checker issues when doing a BFS

breadth-first-search

rust

borrow-checker