Fighting the borrow checker, in a loop

I have a error compiling the following code for a simple recursive tree.

pub struct Node<'a> {
    attribute:&'a str,
    children:Vec<Box<Node<'a>>>,
}
impl <'a> Node<'a> {
    fn add_child(&mut self, child:Node<'a>) -> &'a Node{
        self.children.push(Box::<Node>::new(child));
        self
    }
}

fn main() {
    let v = "c";
    {
        let mut t1 = Node{attribute:"v", children:Vec::new()};
        for _ in 1..1 {
            let td = Node{attribute:v, children:Vec::new()};
            t1.add_child(td);
        }
    }
}

The error is:

error[E0499]: cannot borrow `t1` as mutable more than once at a time
  --> src/main.rs:18:13
   |
18 |             t1.add_child(td);
   |             ^^ mutable borrow starts here in previous iteration of loop
19 |         }
20 |     }
   |     - mutable borrow ends here

If I change the definition of add_child from:
fn add_child(&mut self, child:Node<'a>) -> &'a Node{
to:
fn add_child(&mut self, child:Node<'a>) {
I do not have the compile time error.

I am stumped. I cannot see what the error means mutable borrow starts here in previous iteration of loop. I am confused about what is being borrowed where and when. The previous iteration is out of scope once it is done.(?) Why would a return value, that is discarded, make any difference?

This has been fixed with non-lexical-lifetimes in rust 2018 edition.
Playground
On another note,

fn add_child(&mut self, child:Node<'a>) -> &'a Node{

Desugars (Correct me if I'm wrong) to

fn add_child<'a, 'b: 'a>(&'b mut self, child:Node<'a>) -> &'a Node{

Which I believe is illogical, because 'b has to be greater than or equal to 'a, and since it's possible that 'a is smaller than 'b, returning self which is of 'a should be impossible... :confused:

1 Like

It seems your add_child function

Implies self should have a lifetime that is longer than 'a.

And you borrows

At this point, the mutable borrow should have a life time which is longer than the t1.

And removing the last return self, makes the self has a different lifetime, which is not related to 'a. Thus it's possible to borrow it inside a loop. (Because it doesn't requires a lifetime of 'a)

Similarly, this should compile as well

fn add_child(&mut self, child:Node<'a>) -> &Node

Because it doesn't requires borrow a reference of livetime 'a anymore

But what I am actually seeing is a little bit different. This compiles

    fn add_child(&mut self, child:Node<'a>) -> &'a Node{
        self.children.push(Box::<Node>::new(child));
        self
    }

But this doesn't

    fn add_child<'b:'a>(&'b mut self, child:Node<'a>) -> &'a Node{
        self.children.push(Box::<Node>::new(child));
        self
    }

Could anybody explain why?

I am even more confused! The code at That Playground compiles there, but not here.

At the bottom of the page it says:

As of Rust 1.31, the default edition of Rust is now Rust 2018. Learn more about editions in the Edition Guide. To specify which edition to use, use the advanced compilation options menu.

Is that a clue?

I am totally confused by the life time stuff. I have very little idea what that means. "Desugers" means "after default elicitation", does it?

What does <'a, 'b: 'a> mean? What does the colon mean in that expression?

Yes. Golly. Thank you. I do not know where that came from.

What is the life time of the returned reference?

This is analogous to a “plain” &'a mut self borrow. Even if you don’t return anything, it “locks” that Node instance for its entire lifetime since whatever concrete lifetime 'a becomes, is going to be longer than the lifetime for which a Node lives.

1 Like

Same as the one for &mut self - take a look at lifetime elision rules for more info.

Why?

Which part? :slight_smile:

I expect this one doesn't compile.
I know the reason why it doesn't compile is that &mut self should live at least as long as 'a.
But what surprises me is this compiles.

    fn add_child(&mut self, child:Node<'a>) -> &'a Node{
        self.children.push(Box::<Node>::new(child));
        self
    }

Shouldn't this be de-sugared to exactly the other one ?

It desugars to:

fn add_child<'b>(&'b mut self, child:Node<'a>) -> &'a Node

There’s no (outlives) relationship between 'a and 'b there beyond the implied one - 'b is shorter than 'a.

As I mentioned earlier, it's rust 2018 edition, which means that it has non-lexical-lifetimes which are more lax in certain situations (Which I think includes this one)

<'a, 'b: 'a>

Means that 'a is a lifetime, and that 'b is another lifetime that is greater than or equal to 'a
"Desugars" refers to 'it is equivalent to in the eyes of the compiler'

Ah, I see, Thanks a lot :slight_smile:

but why this works Rust Playground

impl <'a> Node<'a> {
    fn add_child<'b>(&'b mut self, child:Node<'a>) ->  &'a mut Node<'b>{
        self.children.push(Box::<Node>::new(child));
        self
    }
}

But this one doesn't

impl <'a> Node<'a> {
    fn add_child<'b>(&'b mut self, child:Node<'a>) ->  &'a mut Node<'a>{
        self.children.push(Box::<Node>::new(child));
        self
    }
}

And also what is &'a mut Node<'b>, sounds like a reference lives longer than the Node itself ?

This is very deep, and I am drowning.
But...

Outside of the test case that I built to explain the error and in the lib I am building I had the following:

    fn add_child(& mut self, child:Node<'a>) ->  &'a  mut Node{

Which did not compile.

    fn add_child<'b>(&'b mut self, child:Node<'a>) ->  &'a  mut Node{

does.

I have read everything I can get my hands on about life times and I am way out of my depth! As far as I can tell it is throwing paint at a wall...
Is there and literature around rust similar to what Bjarne Stroustrup wrote for C++? I found " The Design and Evolution of C++" really helpful. It would be really helpful for Rust.

I fear that I will not be able to use Rust for anything useful as I am still having problems like these that I have to solve by using random invocations that I do not understand.

(Some of this is presumptions, I'm not the best at lifetimes...)

In this case, it is implied that 'a has to be greater than or equal to 'b (So that a 'b can contain it), in which case, &'b mut self refers to a self which has to live shorter than or equal to 'a, but we attempt to pass it off as 'a, which may be larger than 'b
Edit:
Yeah, vitalyd's post explains it better

But if this is the case how could &'a mut Node<'b> meaningful if 'b lives shorter than 'a

I am not confused about this one, but I am confused about the other one, since I expect the both case should fail.

This is also true in another case, because the self only has a lifetime of 'b. But it compiles when the return type is &'a mut Node<'b>. (Note the lifetime of the returning reference doesn't change)

When you write add_child<'b>(&'b mut self, ...), the compiler selects the right 'b when it calls this method. In this case, it's as-if you wrote:

fn add_child<'b: 'a>(&'b mut self, child:Node<'a>) ->  &'a mut Node<'b>{
        self.children.push(Box::<Node>::new(child));
        self
    }

Prior to NLL, this would prevent you from calling add_child again because the mutable borrow is extended beyond the lifetime of the Node value. With NLL, the compiler can see that the returned reference isn't even used, and so allows the calling code (i.e. the loop) to proceed. Note that the pre-NLL error is at the call/use site.

This is now error at definition site - the signature and body of the method don't align: given a self borrow for 'b, you can't return self as-if it's &'a Node<'a> - you'd need to borrow self for 'a in that case, explicitly in the signature.

Edit: correcting illegible stuff I wrote - responding on mobile is hard :slight_smile:

2 Likes

Ah I see, thanks for the explain. That's really helpful. :slight_smile:

One more question. But why if I write 'b explicitly it prevents me from calling the function again ?

impl <'a> Node<'a> {
    fn add_child<'b:'a>(&'b mut self, child:Node<'a>) ->  &'a mut Node<'b>{
        self.children.push(Box::<Node>::new(child));
        self
    }
}

Isn't the compiler detect the return value isn't used as well ?

What is the colon for in <'b:'a>?

'a is greater than or equal to 'b