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. =)