I have two pieces of code for joining two singly-linked lists. They pretty much follow the same strategy - walk down to the end one list, keeping a mutable reference to the latest node. At the end, mutate the reference so that the last element points to the head of the second list. However, the borrow checker doesn't like one of the snippets, and I'd like to understand why.
Here is one version of an append function, which works:
struct Node {
elem: i32,
next: Option<Box<Node>>,
}
fn append(head: &mut Option<Box<Node>>, tail: Option<Box<Node>>) {
let mut link = head;
while link.as_mut().is_some() {
link = &mut link.as_mut().unwrap().next;
}
*link = tail;
}
Although this is correct, the combination of is_some() and unwrap() is less than elegant, so I'd prefer to use a while let loop instead:
fn append2(head: &mut Option<Box<Node>>, tail: Option<Box<Node>>) {
let mut link = head;
while let Some(node) = link.as_mut() {
link = &mut node.next;
}
*link = tail;
}
But this doesn't compile! The compiler reports an error on the line *link = tail, outside the loop. It "cannot assign to *link because it is borrowed", although the only objects in scope at that point are head, link (which should borrow head) and tail.
What would be the correct way to achieve this with a while let loop?
Editing to add links to the fix, and the explanation, since I can only mark one solution. Fix Explanation
fn append3(head: &mut Option<Box<Node>>, tail: Option<Box<Node>>) {
let mut link = head;
while let Some(node) = link {
link = &mut node.next;
}
*link = tail;
}
Or, being more explicit about what the pattern match is doing here (this is equivalent to above):
fn append3(head: &mut Option<Box<Node>>, tail: Option<Box<Node>>) {
let mut link = head;
while let &mut Some(ref mut node) = link {
link = &mut node.next;
}
*link = tail;
}
@2e71828 you're right, it does! It seems the let matching is smarter than I gave it credit for, seeing as it's able to juggle the &mut part around. I like your second example a bit better since it's more explicit. (I didn't know about the ref mut syntax)
Would you happen to know why the original version which matches on link.as_mut() doesn't work? It should be just another layer of indirection after all.
For some context about why it fails, look at the function definition of as_mut:
pub const fn as_mut(&mut self) -> Option<&mut T>
So it takes an &mut Option<T> and creates an Option<&mut T>. In so doing, it borrows the option and won't let you change link until node goes out of scope.
I think I get it... in the original append2 function, link borrows from the newly-minted Option, which itself borrows from link. By removing the extra Option, the borrow checker can figure out that link is simply borrowing it's own struct member. Thanks!
I think of it more like node borrows from link, and so link can't be changed while node exists. It's not a problem in your original append function because link.as_mut().is_some() immediately drops the returned "newly minted option", allowing link to be changed later.
The intended use of as_mut is usually to edit the underlying value directly inside the option without reassigning, similar to what's in the docs.
For what it's worth, I think this was the best way to do it:
Interestingly, the compiler error is on the line *link = tail outside the loop, at which point node is no longer in scope. The problem is definitely inside loop though.
(Edited the original post to include this information)
But I think that any use of link outside the loop will fail, because *link has to be reborrowed for the entire lifetime on link in the as_mut call (in order for the result to be assignable back to link, which has a single type including that lifetime).
Ah, so in the OP, even though the let match fails in the final iteration, iter_mut was still called, and because of the nuanced relationship between lifetimes and loops, the end result is a "self-borrowed" link.
In the working example, no borrow occurs when the pattern match fails on the last iteration, so the compiler is able to deduce lifetimes in a cleaner fashion.
Thanks for clarifying, and for the links! I'll look through the RFC in a bit more detail later.
It's a doozy, but also one of the best/only technical guides to borrow checking. Some brief notes off the top of my head if you do decide to tackle it...
The birds-eye view of borrow checking which I wish had been in the introduction is something like:
Where lifetimes are alive is calculated based on things like where lifetime-typed values are alive and lifetime constraints
Where every borrow of a place[1] is alive is calculated based on those lifetimes
but may be shorter than the related lifetime due to things like overwriting references
there's also a distinction between shared and exclusive borrows
Every use of every place is checked against the live borrows to see if there's a conflict or not
some uses and borrows are compatible, but others are not
(The RFC is sort of front loaded in that it talks about lifetimes and specific subtopics like drops in terms of lifetimes for a long time, and then spends a relatively brief amount of time explaining the actual borrow checking at the end.)