Hello, I am a beginner trying to understand the difference between stable borrow checking and Polonius. Why does NLL reject this code, but Polonius allow it? I would also appreciate feedback about style issues in the code itself; likely I am doing many things wrong.
Briefly, NLL does not "realize" that a particular borrow is never used again after my loop scope ends, but Polonius does. Maybe using break to end this loop is the problem? But I really don't understand why: my code appears similar to Walking Down a Data Structure (Problem Case 4) of the NLL RFC, so I expected it to be admitted by the current borrow checker. I did search for visualization tools for borrow checking, but could not find anything easy to use. I tried to find something that would call promising-sounding functions like explain_borrow from rustc_borrowck and build a graph, but couldn't. Any references appreciated.
Anyway, I am doing the Stanford Linked Lists problems with the safe types from Rust With Too Many Linked Lists. I'm working on "insert in sorted order," and I know this solution is wrong --- but it still summarizes my confusion about borrow checking, so I'd like some help with that before I fix all the edge cases. Here are the types:
pub struct List {
head: Link,
}
type Link = Option<Box<Node>>;
struct Node {
elem: i32,
next: Link,
}
Here is the implementation that NLL allows:
pub fn sorted_insert_nll(&mut self, data: i32){
let mut cur_link = &mut self.head;
while let Some(node) = cur_link {
// "peek" at next item: rather do it with a reference?
let next_item = node.next.as_ref().unwrap().elem;
if data >= node.elem && data <= next_item {
println!("Place new element between {} and {}",
node.elem, next_item);
let new_node = Box::new(Node {
elem: data,
next: node.next.take(),
});
node.next = Some(new_node);
break;
}
cur_link = &mut node.next;
}
}
Here is the implementation that NLL rejects, but Polonius accepts. As far as I can tell the only difference is moving a section use of cur_link outside the loop that "walks" down the data structure.
pub fn sorted_insert_pol(&mut self, data: i32){
let mut cur_link = &mut self.head;
while let Some(node) = cur_link {
// "peek" at next item
let next_item = node.next.as_ref().unwrap().elem;
if data >= node.elem && data <= next_item {
println!("Place new element between {} and {}",
node.elem, next_item);
break;
}
cur_link = &mut node.next;
}
if let Some(node) = cur_link {
let new_node = Box::new(Node {
elem: data,
next: node.next.take(),
});
node.next = Some(new_node);
}
}
If I run:
cargo test -- --show-output
I get borrow checking errors in the _pol implementation:
error[E0503]: cannot use `*cur_link` because it was mutably borrowed
--> src/question.rs:54:16
error[E0499]: cannot borrow `cur_link.0` as mutable more than once at a time
--> src/question.rs:54:21
If I run:
RUSTFLAGS="-Z polonius" cargo test -- --show-output
both sorted inserts compile, my tests run, and they behave as expected (incorrect, but working for non-edge-cases). Please help me improve my mental model of the current borrow checker vs. Polonius vs. the "platonic ideal" of borrow checking.
