Can someone help me to understand why code complains

The following code complains

let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        // cannot use `*tail` because it was mutably borrowed
        if let Some(ref mut node) = tail {
            if i == 1 {
                node.next = Some(Box::new(ListNode::new(i)));
                tail = &mut node.next;
            }
        }
    }

but the following code compiles,

let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if let Some(ref mut node) = tail {
            node.next = Some(Box::new(ListNode::new(i)));
            tail = &mut node.next;
        }
    }
2 Likes

What is the difference between the snippets? Please post the full error you got, and please also include a full example that compiles.

Code can be found here:
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=ffaf2b084b8d6584277e6e17d691de2c

the first snippet has if i == 1 inside the if let Some block. the first one fails while the second one compiles

In the first example you take a mutable reference to the contents of tail but then you assign a new value to tail each iteration of the loop so there is only ever a single mutable reference used at a time.

In the example where you check i == 1 there is a hidden else case where tail does not change. This is not allowed because then there could be multiple iterations of the loop where a mutable reference to the contents of the same tail is created.

2 Likes

That was what I was thinking, but how to explain the following code compiles,


let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        // cannot use `*tail` because it was mutably borrowed
        if let Some(ref mut node) = tail {
            node.next = Some(Box::new(ListNode::new(i)));
        }
    }

In this case, tail is not changed but multiple mut ref are created ?

Aren't you trying to insert an entry in the linked list? The code that you say compiles does not do this, I think it empties the entire list. It compiles (I assume) because the tail variable (which is always equal to the head) is modified unconditionally in every loop iteration.

I don't know for sure what you're trying to do, but perhaps something like this?:

    for i in 1..=5 {
        if let Some(ref mut node) = tail {
            if i == 1 {
                node.next = Some(Box::new(ListNode::new(i)));
                break;
            } else {
                tail = &mut node.next;
            }
        }
    }

I know how to fix in sense of logic, just wondering why keep tail unchanged can compile, keep tail changing also can compile but if put them into if else, it will not compile

1 Like

The reason in this case is: There is no strong reason why the code shoundn’t compile. There is a work-in-progress rewrite / extension of the borrow-checker called “polonius” that accepts your code

so in conclusion, the only reason why the current borrow checker doesn’t accept it is because it isn’t as smart in some regards. These problems when you’re running past the limits of the borrow checker are often quite subtle, I haven’t taken the time to think about whether I can come up with an intuitive understanding for why this particular code is rejected by the current borrow checker, but perhaps understanding it isn’t worth too much anyways because it doesn’t translate into any “real” problem/flaw in the program.

10 Likes

Thank you, this is what I am looking for. Really appreciate it

Well, now I’m trying it anyways… the borrow checker isn’t particularly good at handling case-distinctions in the borrow pattern. With the if expression, in one loop iteration

        if let Some(ref mut node) = tail {
            if i == 1 {
                node.next = Some(Box::new(ListNode::new(i)));
                tail = &mut node.next;
            }
        }

you have some value *tail borrowed by the reference tail. Then you create a derived reference node. The node.next = Some(Box::new(ListNode::new(i))); line is irrelevant; there are two cases

  • if the if condition evaluates to true, the line tail = &mut node.next executes and creates a new reference &mut node.next derived from node (which was derived froom tail). This reference is stored into the variable tail and must this be long-lived, since tail is used again in the next loop iteration. So the lifetime of the reference that was initially inside of tail must be pretty long.
  • if the if condition evaluates to false, tail still points to the same thing as before

In particular, when then next iteration is reached, the if let Some(ref mut node) = tail needs mutable access to the destination of tail again. Because of the false case, tail might still be the same reference as in the previous iteration, but that one was used to create a long-lived reference, you cannot use it again yet.

If it wasn’t for the false case, the borrow checker would know that by the time the second iteration is reached, the variable tail must contain a new reference to a different destination.

Where polonius shines is in the fact that it’s able to understand the fact that the if statement cannot both be true (resulting in a long-lived re-borrow of tail) and false (resulting in tail still containing the same reference as before).

Only the pessimistic approach of the current borrow checker of considering both the need for a long borrow and the possibility of tail still containing the re-borrowed reference at the same time leads to a compilation error.

4 Likes

Often times, there are good ways to re-write the code in this case so that the current borrow checker accepts it as-well. Assuming that the code does exactly what you want to do, in this case, swapping the order of the if-statements does the job,

fn main() {
    let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if i == 1 {
            if let Some(ref mut node) = tail {
                node.next = Some(Box::new(ListNode::new(i)));
                tail = &mut node.next;
            }
        }
    }
}

however this is a very special-case kind of fix. To name a more general approach: What most often works for code that polonius accepts but stable compiler doesn’t is to re-trace your steps down to the value you’re assigning / returning / etc… conditionally. The value assigned to tail in this case is &mut node.next. It uses the node variable and the borrow-checker isn’t happy. However, if you’re removing the extra step with the node variable from the final connection and just assign something depending on tail to tail itself it turns out to be enough to make the borrow-checker happy. We can unwrap because we know it’s an Option::Some, so node is tail.as_mut().unwrap(), and we get

fn main() {
    let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if let Some(ref mut node) = tail {
            if i == 1 {
                node.next = Some(Box::new(ListNode::new(i)));
                //tail = &mut node.next;
                // re-trace our way here:
                tail = &mut tail.as_mut().unwrap().next;
            }
        }
    }
}

In relation to my previous explanation, this fix demonstrates quite clearly, that it was the lifetime of the reference node in particular that confused the borrow-checker. In a more general setting, you’d often also have the condition itself depend on something like node. The re-tracing approach keeps the lifetime of node unconditionally short, the re-tracing can be done as soon as you’re gone past the innermost conditional. So you could’ve also done it before the node.next = … line, the following code works, too:

fn main() {
    let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if let Some(ref mut node) = tail {
            if i == 1 {
                let node = tail.as_mut().unwrap();
                node.next = Some(Box::new(ListNode::new(i)));
                tail = &mut tail.as_mut().unwrap().next
            }
        }
    }
}

note that the outer node variable is completely unused now; the code further simplifies to

fn main() {
    let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if tail.is_some() {
            if i == 1 {
                let node = tail.as_mut().unwrap();
                node.next = Some(Box::new(ListNode::new(i)));
                tail = &mut node.next
            }
        }
    }
}

and

fn main() {
    let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if tail.is_some() && i == 1 {
            let node = tail.as_mut().unwrap();
            node.next = Some(Box::new(ListNode::new(i)));
            tail = &mut node.next
        }
    }
}

By the way, moving the assignment back out one level instead, i.e.

fn main() {
    let mut head = Some(Box::new(ListNode::new(0)));
    let mut tail = &mut head;
    for i in 1..=5 {
        if tail.is_some() { // compiler unhappy
            let node = tail.as_mut().unwrap();
            if i == 1 {
                node.next = Some(Box::new(ListNode::new(i)));
                tail = &mut node.next
            }
        }
    }
}

fails, as expected. But the error message is a bit nicer than in the original code (because we don’t have all the hints pointing to essentially the same place); try it out for yourself.

5 Likes

ah, this is really nice! This is the part that I love Rust the most, the community, excellent!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.