Recently someone I was talking to ran into a fun borrow checker problem in Rust which is illustrative of some current underlying limitations of Rust's borrow checker. The problem boiled down to: they took a reference in a loop (dropped on each iteration), and the borrow checker complains that it cannot borrow it mutably multiple times, since it was borrowed in a previous iteration. But: didn't we drop it? Why is it still borrowed?

Here's an example, because one code example is worth a thousand words. In this example, we define a function called find_leading_0s which takes in a slice of bytes and returns the slice containing the prefix of leading 0s as a mutable reference¹.

fn main() {
    let mut bytes = [0, 0, 9, 0, 2, 3];
    let padding = find_leading_0s(&mut bytes);
    println!("padding: {:?}", padding);
}

fn find_leading_0s(bytes: &mut [u8]) -> Option<&mut [u8]> {
    let mut index = 0;

    while index < bytes.len() {
        let padding = &mut bytes[..index];
        if padding[index] != 0 {
            return Some(padding);
        }

        index += 1;
    }

    None
}

Inside each iteration of the loop, we take a slice and if the next element is non-zero we return this slice. Otherwise, we keep going. If we get to the end and we've found no non-zero elements, we can return some default value.

If you compile this, you'll get the following error:

> rustc borrow.rs

error[E0502]: cannot borrow `*bytes` as immutable because it is also borrowed as mutable
  --> borrow.rs:10:19
   |
7  | fn find_leading_0s(bytes: &mut [u8]) -> Option<&mut [u8]> {
   |                           - let's call the lifetime of this reference `'1`
...
10 |     while index < bytes.len() {
   |                   ^^^^^^^^^^^ immutable borrow occurs here
11 |         let padding = &mut bytes[..index];
   |                            ----- mutable borrow occurs here
12 |         if padding[index] == 0 {
13 |             return Some(padding);
   |                    ------------- returning this value requires that `*bytes` is borrowed for `'1`

error[E0499]: cannot borrow `*bytes` as mutable more than once at a time
  --> borrow.rs:11:28
   |
7  | fn find_leading_0s(bytes: &mut [u8]) -> Option<&mut [u8]> {
   |                           - let's call the lifetime of this reference `'1`
...
11 |         let padding = &mut bytes[..index];
   |                            ^^^^^ `*bytes` was mutably borrowed here in the previous iteration of the loop
12 |         if padding[index] == 0 {
13 |             return Some(padding);
   |                    ------------- returning this value requires that `*bytes` is borrowed for `'1`

error: aborting due to 2 previous errors

Some errors have detailed explanations: E0499, E0502.
For more information about an error, try `rustc --explain E0499`.

The key error is this:

`*bytes` was mutably borrowed here in the previous iteration of the loop

The underlying code seems sound, though, because the reference drops and so you will never actually hold the mutable reference across loop iterations. But the borrow checker is rejecting it. Why's that?

A long-standing issue

There are some longstanding issues on the Rust compiler which are related here:

• rust-lang/rust#54663: Borrow checker extends borrow range in code with early return
• rust-lang-rust#70255: Weird error for mutable references in a loop

These relate to the same issue with code samples of their own, some which are loops and some which are conditionals. They all boil down to the same problem, which has been dubbed Polonius. This is best summarized in the Rust blog post Polonius update.

Lifetimes can be named or anonymous. If lifetimes are in the signature of a function, either explicitly (fn f<'a>(x: &'a str) ...) or implicitly, like here, then they're named. Even though our lifetimes are inferred (see the lifetime elision rules) they are part of the signature.

The current way the borrow checker works, if a lifetime is named, then it is deemed to last until the end of the function across all code paths². So even if you have an early return whenever you grab that reference, or you drop it across iterations of the loop, it doesn't matter: it's still going to be treated as if it's held for the whole function! Why this is the case is a much deeper question that I don't have the expertise to answer, but the Polonius update blog post mentioned above goes into some more detail.

This all is a bit of a downer since a lot of code could be made terser and more readable by allowing this kind of pattern. Fortunately we can work around it, and we will eventually not have to.

A workaround

The code example above can be rewritten like this:

fn main() {
    let mut bytes = [0, 0, 9, 0, 2, 3];
    let padding = find_leading_0s(&mut bytes);
    println!("padding: {:?}", padding);
}

fn find_leading_0s(bytes: &mut [u8]) -> Option<&mut [u8]> {
    let mut index = 0;

    while index < bytes.len() {
        if bytes[index] != 0 {
            return Some(&mut bytes[..index]);
        }

        index += 1;
    }

    None
}

In this example, instead of creating a new mut reference into the slice, we use the existing single mut reference across all iterations. You can similarly hoist your references out of the loop and solve things that way.

This example does compile and works as expected. We have a few other workarounds available to us:

• Use the polonius-the-crab crate. By using a macro, your lifetimes end up anonymous instead of named and this issue goes away.
• Use dedicated APIs like get_or_insert() that avoid this problem for us
• Re-order some of the code to avoid this particular problem in a clunky way

This doesn't feel great, because we're limited in the code we can write.

The future!

In a future release of the borrow checker, this should be resolved. Per the working group's update on this issue, the goal is to have the Polonius problem stable by Rust 2024.

The solution they're working on changes some of the underlying machinery of the borrow checker and then tracks things across each point in the control flow graph, instead of once. This will let us use this type of mutable borrow with early return, and make a lot of neat code both safe and compilable!

This looks like quite a big project. I know a lot of people have worked on it for a long time. Hopefully this will land in 2024. I'll be keeping an eye out for more updates on it, and I'm excited to see the ergonomic code we can write once this lands!