Is this case a bug of the borrow checker?

I saw a code to solve the problem of merge k sorted linkedlist, and one of the solution introduced finding the last node no greater then a give value, and i tried to rewrite the code in reference(although the original code is &mut Boxed which will be zero cost compare to reference), and i found out the following problem, this code will not compile:

use std::boxed::Box;

struct BorrowTest {
  val: i32,
  next: Option<Box<BorrowTest>>
}

impl BorrowTest {
  fn find_last<'find_last>(&'find_last mut self, val: i32) -> &'find_last mut Self {
    let mut curr = self;
    loop {
      let r = match &mut curr.next { 
        Some(x) => {
          if x.val > val {
            None
          } else {
            Some(x)
          }
        } 
        None => None,
      };
      if r.is_none() {
        return curr
      } 
      curr = r.unwrap(); 
      // switch to the following line will compile
      // curr = curr.next.as_mut().unwrap();
    }
  }
}

It seems at line 23 'return curr', the compiler regards the borrow of *curr by r is still in active, as long as the r is in use at line 25 'curr = r.unwrap()'. I think the line 23 and line 25 are on different branch and line 23 will end the whole iteration and function scope, so it should not be affected by line 25. Is it a bug of complier or it is indeed a memory safety issue?

Yes, this is a known limitation of the current borrow checker. Your code is safe, and rustc will compile it without errors in the future. It already compiles in the nightly toolchain when the experimental new borrow checker Polonius is enabled.

3 Likes

Note that while this is an limitation of the borrow checker and can be improved later, it's not something considered bug. It is proved that any non-trivial static analyzer can either be sound or complete, but can't be both. Sound checker never allows incorrect code. Complete checker never rejects correct code.

For example, type systems usually are sound checker. If a variable has the type int, the type system never allows code which assigns some string value into it. But it's not complete, some correct code which works well on dynamically typed languages can't be translated as-is to the statically typed language.

The borrow checker is a sound checker so it may rejects some correct code. Reducing such cases is considered as improvement, not bugfix.

4 Likes

Thank you, it will be excited to experience the new borrow checker.

By the way, this is only true when you’re ignoring a few open soundness bugs in Rust’s type system.
(Freel free to click on every single word. The first one of these comes with its own “joke crate” which might keep working for quite a while, taking into account that it’s using a bug that’s now open for almost 6 years already. If you only want to open a single of these links, take a look at that crate :wink: .
Also, these are coming chronologically and half of these (the last 4) are my own issues; seems like I enjoy breaking Rust in my free-time, I did it again just yesterday (last link).)

Edit: And here’s my next, new unsoundness bug: #84366

Edit2: I’m on a streak… it’s 4 days later, and here’s another one: #84533

Edit3: Sorry for the many edits, but I just have to also mention this new one: #84591

11 Likes