4

In Rust if a structure is like this

struct Node {
    next: Option<Box<Node>>,
}

Then to implement a method to find the tail and add a new node on it might look like this

fn add1<'a>(mut node: &'a mut Node) {
    while let Some(next) = node.next.as_deref_mut() {
        node = next;
    }
    node.next = Some(Box::new(Node { next: None }));
}

Then error like this encountered:

error[E0506]: cannot assign to `node.next` because it is borrowed
  --> src/lib.rs:16:5
   |
12 | fn add1<'a>(mut node: &'a mut Node) {
   |         -- lifetime `'a` defined here
13 |     while let Some(next) = node.next.as_deref_mut() {
   |                            ------------------------
   |                            |
   |                            borrow of `node.next` occurs here
   |                            argument requires that `node.next` is borrowed for `'a`
...
16 |     node.next = Some(Box::new(Node { next: None }));
   |     ^^^^^^^^^ assignment to borrowed `node.next` occurs here

Some other variation also cannot work:

fn add1_borken_ergonomics(mut node: &mut Node) {
    while let Some(next) = &mut node.next {
        node = next;
    }
    node.next = Some(Box::new(Node { next: None }));
}

fn add1_borken_explicit<'a>(mut node: &'a mut Node) {
    while let Some(ref mut next) = *&mut node.next {
        node = next;
    }
    node.next = Some(Box::new(Node { next: None }));
}

which gives similar error like

error[E0506]: cannot assign to `node.next` because it is borrowed
  --> src/lib.rs:30:5
   |
26 | fn add1_borken_explicit(mut node: &mut Node) {
   |                                   - let's call the lifetime of this reference `'1`
27 |     while let Some(ref mut next) = *&mut node.next {
   |                    ------------     -------------- borrow of `node.next` occurs here
   |                    |
   |                    assignment requires that `node.next` is borrowed for `'1`
...
30 |     node.next = Some(Box::new(Node { next: None }));
   |     ^^^^^^^^^ assignment to borrowed `node.next` occurs here

So the questions is, why writing like this blow it will then work

fn add1_working<'a>(mut node: &'a mut Node) {
    while let Some(ref mut next) = node.next {
        node = next;
    }
    node.next = Some(Box::new(Node { next: None }));
}

The code above should all mean the same but compilers treat them differently?

Rust playground for the example code above. And the same issue can be seen with another simpler code example as well (from the issue page, see below.)

After asked around I found an issue related to this https://github.com/rust-lang/rust/issues/67957, but it seems not mentioning whether it is some compiler bug that can be fixed later, or it is because we need some better understanding in some aspects of the language?

E_net4
  • 27,810
  • 13
  • 101
  • 139
Fuyang Liu
  • 1,496
  • 13
  • 26
  • 1
    Does this answer your question? [Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time](https://stackoverflow.com/questions/37986640/cannot-obtain-a-mutable-reference-when-iterating-a-recursive-structure-cannot-b) – Stargateur Feb 26 '21 at 11:09
  • 2
    Not sure if that answers my question as we know there is a working solution. But my question is more about why the other way of writing not working, as from my simple understanding of the language syntax they should have worked as well? – Fuyang Liu Feb 26 '21 at 11:13
  • I don't really know why exactly, either it's impossible to write this using rust rule or the borrow checker is not smart enough (I'm always surprise sometime). Rust use strict rules and these rules make it REALLY hard to write recursive data structure. If you really want write a linked list in rust I would advice use unsafe and raw pointer xd. So unless a rust core team come here I don't think you will find a precise explanation of why this happen, I don't even know if the answer is clearly explain in [Too Many Linked Lists](https://rust-unofficial.github.io/too-many-lists/) – Stargateur Feb 26 '21 at 11:22
  • 1
    The difference is that you are creating a new borrow in all of them except the last. I am in the process of writing an answer which will try to be clear about it. :) – Hadus Feb 26 '21 at 11:29
  • 1
    Wouldn't the last one also borrows via `Some(ref mut next)` ? The type of `next` is evaluated exactly the same for different examples. – Fuyang Liu Feb 26 '21 at 11:35
  • 1
    No. Matching with `Some(ref mut next)` is in some way the opposite of matching with `Some(&mut next)` – Hadus Feb 26 '21 at 11:36
  • That could be true. But in my examples there is two `Some(ref mut next)` but only one works. The rest are `Some(next)` but they are not working – Fuyang Liu Feb 26 '21 at 11:59
  • 2
    using `*&mut node.next` in the other one makes the difference. I'm sorry mate it is taking me really long to come up with a legible example that explains it well. bear with me – Hadus Feb 26 '21 at 12:01
  • 1
    Well no problem. Take your time :) And thank you for helping us here. – Fuyang Liu Feb 26 '21 at 12:02
  • What I feel is that every case actually borrows on that `node.next` at the while loop part. You need to borrow a reference of `next` to access to the node inside `next`. But the borrowing of that all stopped after the while loop finishes. Then how come one format can be fine while others the compiler failed to recognise it? – Fuyang Liu Feb 26 '21 at 12:07
  • @FuyangLiu I think I was wrong. After spending 5 hours on this I don't think I understand why it works the way it does. Maybe its a bug maybe this corner case isn't documented. I will ask on the rust forums too if you haven't already. I thought I could help but its over my head. – Hadus Feb 26 '21 at 17:29
  • 1
    @FuyangLiu I asked on the rust forum also: https://users.rust-lang.org/t/56193 – Hadus Feb 26 '21 at 17:42
  • @Hadus Thank you very much, that is very nice of you. I will follow the discussion there as well. – Fuyang Liu Feb 27 '21 at 06:41

1 Answers1

2

This is a known bug.

I got the explanation from the rust forum:

There's another bug report related to this, similar to the one linked in that StackOverflow thread but with a bit more discussion: if/while Some(n) = &mut foo sugar will leak a temporary mutable borrow to current scope in particular situation · Issue #62013 · rust-lang/rust · GitHub

I didn't follow all of the details, but I believe the difference in behavior here is unintentional and will be fixed eventually. When compiling with the next-generation borrow checker Polonius, both functions compile successfully.

Hadus
  • 1,551
  • 11
  • 22
  • That is very good to know. Thank you very much. Now I can kind of relax to know it is not because I could not understand some aspects of the language as I feel Rust should be "that hard" :) – Fuyang Liu Feb 27 '21 at 06:47
  • Is there some way to use `-Zpolonius` with `cargo` to conveniently run the code? – Fuyang Liu Feb 27 '21 at 15:14