The mutable borrow is released when matching on a Option<&mut Self> in a function, but not when the function is inlined

[shepmaster]

#![feature(nll)]

struct Node {
    value: char,
    children: Vec<Node>,
}

impl Node {
    fn new(value: char) -> Self {
        Self {
            value,
            children: Vec::new(),
        }
    }

    fn add_child(&mut self, value: char) -> &mut Self {
        self.children.push(Self::new(value));
        self.children.last_mut().unwrap()
    }

    fn get_child(&mut self, value: char) -> Option<&mut Self> {
        self.children.iter_mut().find(|n| n.value == value)
    }

    fn add_word(&mut self, word: String) {
        let mut cursor = self;
        for c in word.chars() {
            // The extracted version of the function works
            // cursor = cursor.get_or_add(c);

            // But the inlined version of the function does not.
            cursor = match cursor.get_child(c) {
                Some(node) => node,
                None => cursor.add_child(c),
            };
        }
    }

    fn get_or_add(&mut self, value: char) -> &mut Self {
        match self.get_child(value) {
            Some(node) => node,
            None => self.add_child(value),
        }
    }
}

fn main() {}

error[E0499]: cannot borrow `*cursor` as mutable more than once at a time
  --> src/main.rs:34:25
   |
32 |             cursor = match cursor.get_child(c) {
   |                            ------ first mutable borrow occurs here
33 |                 Some(node) => node,
34 |                 None => cursor.add_child(c),
   |                         ^^^^^^ second mutable borrow occurs here

Originally from Stack Overflow

[nikomatsakis]

(This needs investigation.)

[Aaron1011]

I'd like to work on this.

[nikomatsakis]

@Aaron1011 sounds good - I was digging into this earlier actually but got distracted. I'll take a quick look at where I was, I think I was close to seeing what was going wrong =)

[Aaron1011]

Here's a reduced version of @shepmaster's example (playground)

#![feature(nll)]

struct Foo;

impl Foo {
    fn get_self(&mut self) -> Option<&mut Self> {
        Some(self)
    }
    
    fn match_self(&mut self) -> &mut Self {
        match self.get_self() {
            Some(s) => s,
            None => self.new_self()
        }
    }
    
    fn new_self(&mut self) -> &mut Self {
        self
    }
    
    fn trigger_bug(&mut self) {
        let mut var = self;
        
        // Comment out this loop...
        loop {
            var = var.match_self();
            
            // ...or this statement to make this example compile
            var = match var.get_self() {
                Some(s) => s,
                None => var.new_self()
            }
        }
        
        
    }
}

fn main() {}

[nikomatsakis]

I think this one is gonna be tricky. I think it's a similar problem to the one identified here nikomatsakis/borrowck#18.

I feel like I can't quite describe it precisely, but what happens is something like this:

1. We create the borrow in add_word with the call to cursor.get_child. It has lifetime _#33r.
2. On the Some path, we require that this lifetime '_#33r has to outlive the lifetime associated with cursor (let's call it R)
   • In theory, this ought to exclude the None path
3. But when we assign to cursor, we kill the loan but not the borrow. This is a somewhat confusing aspect of NLL that was covered here in the RFC thread and then later here.
4. As a result, the loan is considered still in scope as we enter the None block.

It may be that we want to make some kind of deeper change to the analysis here.

[Aaron1011]

I've managed to create an even simpler version. This example compiles: (playground):

#![feature(nll)]

struct Foo;

impl Foo {

    fn get_self(&mut self) -> Option<&mut Self> {
        Some(self)
    }

    fn bad_method(&mut self) {
        let mut var = self;
        
        var = match var.get_self() {
            Some(v) => v,
            None => var
        };
            
        var = match var.get_self() {
            Some(v) => v,
            None => var
        };

    }
    
}

fn main() {}

While this version does not: (playground):

#![feature(nll)]

struct Foo;

impl Foo {

    fn get_self(&mut self) -> Option<&mut Self> {
        Some(self)
    }

    fn bad_method(&mut self) {
        let mut var = self;
        
        loop {
            var = match var.get_self() {
                Some(v) => v,
                None => var
            };
        }

    }
    
}

fn main() {}

From looking at the generated MIR, the problem seems to be that the lifetime of the mutable borrow of self is computed to include all points in the generated problem. I think this may be related to how the NLL region inference code performs its depth-first search. I'll investigate further.

[nikomatsakis]

@shepmaster later posted this example:

#![feature(nll)]

#[derive(Debug)]
struct Thing;

impl Thing {
    fn maybe_next(&mut self) -> Option<&mut Self> { None }
}

fn main() {
    let mut thing = Thing;
    let mut temp = &mut thing;
    
    // if let works
    while let Some(next) = temp.maybe_next() {
        temp = next;
    }
    
    println!("{:?}", temp);
}

Same basic idea.

I think the challenge here is the same in all of them -- the code is not wrong per se, but it needs to be improved, and I'm not sure yet how to do it. In particular, the code infers (correctly) that the borrow created in iteration N of the loop may still be used in the None path of iteration N+1. This is why the borrow extends into the None path`. But it fails to see that the variable which was borrowed in iteration N+1 is not the same one.

This comes back to those posts I cited earlier. I think we want to improve the region inference to take into account...well, something. I'm just not quite sure what yet =)

[nikomatsakis]

I have a rough idea I am kicking around: the regions for a borrow can potentially stop the DFS when they reach the borrow point. The idea being that either the borrow itself will cause an error or the path being borrowed must be reassigned between the previous borrow and that point. Have to try and refine it, but I think that's roughly the logic that lets us type the function call case.

[nikomatsakis]

I think this is my preferred minimization, fyi:

#![feature(nll)]

struct Thing;

impl Thing {
    fn maybe_next(&mut self) -> Option<&mut Self> { None }
}

fn main() {
    let mut temp = &mut Thing;
    
    loop {
        match temp.maybe_next() {
            Some(v) => { temp = v; }
            None => { }
        }
    }
}

[nikomatsakis]

Another important test. This one must remain an error:

#![feature(nll)]

fn create<'a>() -> &'a mut u32 { panic!() }
fn condition() -> bool { panic!() }
fn touch(_: &mut u32) { }

fn foo() {
    // Should be error because:
    // - if we pass through loop one time, then `q` points to `a`
    let mut a = 22;
    let mut x = &mut a;
    let mut q = create();
    
    loop {
        let p = &mut *x;
        if condition() { break; }
        q = p;
        x = create();
    }

    touch(&mut a);
    touch(q);
}

fn main() {
}

Some variations of proposed fixes I had did not pass this test. =)

[Aaron1011]

@nikomatsakis: That's essentially the conclusion that I came to - though I started with a different example.

I had a solution for the first two minimizations working locally - it relied on encoding extra information in a StatementKind::Assign, based on where var (or something like it) was assigned to in the HIR. However, it looks like it's unable to compile your minimization. Relying on the HIR as much as I did seems to be too brittle - if the assignment occurs 'within' an expression related to the original temp reborrow, it won't pick up on it properly.

I'm going to try out a few more ideas locally. Thanks for posting that minimization!

[nikomatsakis]

@Aaron1011 I don't think we should be looking at the HIR. I have this "intuition" that the rule we want is to modify the dfs routine A: B @ P so that if it "loops around" and reaches P again, it includes P in the final set but stops searching. However, I'm not able to convince myself whether this is sound -- if you want to produce a branch that experiments with it, though, I'd be interested to play with it.

[Aaron1011]

@nikomatsakis: I've created a branch that seems to work: https://github.com/Aaron1011/rust/tree/maybe_final_self_assign

It correctly compiles all of the minimizations in this thread, and correctly generates an error for your last example.

The core idea is that, under certain circumstances, we don't need to generate region constraints for assign statements. Specifically, if we have the statement _1 = _2, we don't need to generate the constraint _#2: '_1 if _2 is "derived from" a reborrow of _1. This ends up preventing the regions of temporary reborrows on a variable (in your most recent minimization, temp) from growing to include all points of temp.

However, I'm not entirely certain that the way I test if a variable is "derived from" another is sound. I do this in two parts:

• First, I check if we can directly trace a path from a reborrow of the lhs (e.g. temp) to the rhs. The idea is that a usage of the reborrow (e.g. assigning it to another place, calling a method on it) will generate a constraint that the reborrow outlives the new place. Essentially, we do a breadth-first search through the constraints (ignoring the points for now), seeing if the reborrow's region (transitively) outlives the right-hand side's region

• If the first check passes, we use RegionInferenceContext#eval_outlives to see if the reborrow actually outlives the rhs at the point of assignment

The first part is used to eliminate false positives. It's possible for a particular reborrow to outlive the rhs (as determined by eval_outlives), but be otherwise unrelated to it. The first part essentially approximates a more explicit dataflow analysis to determine if the rhs involves a reborrow of the lhs.

My main concern is that this might break if more constraints are somehow added. I haven't been able to find an example where this happens, but I haven't been able to rule it out, either.

Do you think the basic idea of skipping constraint generation when a reborrow is involved is sound?

[nikomatsakis]

@Aaron1011 I'll take a look -- might take a day or two though -- as you say, these are delicate changes.

[nikomatsakis]

Sorry for not getting back to you @Aaron1011 -- it's been very busy. I'm moving this to NLL-deferred because it doesn't seem like a "must fix" blocker in terms of moving NLL towards stabilization (seeing as the code doesn't work with old borrow checker). That said, I have an experimental new formulation of NLL that does solve this problem, and I'd love to get your feedback on it. I hope to write it up soon.

[Aaron1011]

@nikomatsakis: Sounds good to me! Feel free to ping me on Github or IRC when it's ready.

[shepmaster]

Another example that @nikomatsakis says is the same as this:

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

fn example(mut list: &mut Node) {
    if let Some(node) = &mut list.next {
        list = node;
    }

    if let Some(node) = &mut list.next {
        list = node;
    }
}

error[E0499]: cannot borrow `list.next` as mutable more than once at a time
  --> src/lib.rs:10:25
   |
5  | fn example(mut list: &mut Node) {
   |                      - let's call the lifetime of this reference `'1`
6  |     if let Some(node) = &mut list.next {
   |                 ----    -------------- first mutable borrow occurs here
   |                 |
   |                 assignment requires that `list.next` is borrowed for `'1`
...
10 |     if let Some(node) = &mut list.next {
   |                         ^^^^^^^^^^^^^^ second mutable borrow occurs here

Tested with 1.31.0-beta.14 and edition 2018

[justhsu]

@shepmaster similar to #58787. This works:

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

fn example(mut list: &mut Node) {
    if let Some(ref mut node) = list.next {
        list = node;
    }

    if let Some(ref mut node) = list.next {
        list = node;
    }
}

This does not:

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

fn example(mut list: &mut Node) {
    if let Some(ref mut node) = list.next {
        if true {
            list = node;
        }
    }

    if let Some(ref mut node) = list.next {
        list = node;
    }
}