Borrow checker is not happy when conditionally popping elements from binary heap

Question

I'm trying to write a simple function which would pop elements from the BinaryHeap satisfying a certain condition. The function looks like this:

fn check_the_queue(mut queue: BinaryHeap<i32>) {
while !queue.is_empty() {
    let entry = queue.peek().unwrap();
    if *entry <= 0 {
        queue.pop();
    } 
}

When compiling the borrow checker starts complaining:

src/main.rs:52:13: 52:18 error: cannot borrow `queue` as mutable because it is also borrowed as immutable

How can I go around this problem and make the borrow checker happy?

Answer 1

The error message is quite descriptive:

<anon>:8:13: 8:18 error: cannot borrow `queue` as mutable because it is also borrowed as immutable
<anon>:8             queue.pop();
                     ^~~~~
<anon>:5:21: 5:26 note: previous borrow of `queue` occurs here; the immutable borrow prevents subsequent moves or mutable borrows of `queue` until the borrow ends
<anon>:5         let entry = queue.peek().unwrap();
                             ^~~~~
<anon>:10:6: 10:6 note: previous borrow ends here
<anon>:4     while !queue.is_empty() {
...
<anon>:10     }
              ^

The problem is that this borrows queue:

let entry = queue.peek().unwrap();

peek() returns an Option<&T>, that is, an option with a reference to a value of type T. The borrow is valid for as long as entry is alive, which is until the end of the function. It points to something that is stored inside the heap, so it borrows the heap immutably. In other words, as long as entry is alive (until the end of the function), the heap is immutably borrowed.

queue.pop() borrows the heap mutably, so, by the time you get to that, the heap is immutably borrowed AND you attempt to mutably borrow it at the same time.

The borrow checker rules state that you can't borrow something mutably and immutably simultaneously, so you have a problem.

To fix it, find a way to avoid borrowing twice at the same time. For example, you could do this instead:

fn check_the_queue(mut queue: BinaryHeap<i32>) {
    while !queue.is_empty() {
        if *queue.peek().unwrap() <= 0 {
            queue.pop();
        } 
    }
}

That is, just drop the variable entry. This works because by the time you reach queue.pop(), there are no other borrows active, and the borrow checker is happy :)

Lifetimes and borrowing rules may be hard to grok at first, but the steep learning curve pays off over time.