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

#![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

(This needs investigation.)

I'd like to work on this.

@Aaron1011

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

@shepmaster

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() {}

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:

We create the borrow in add_word with the call to cursor.get_child. It has lifetime _#33r.
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
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.
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.

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.

@shepmaster

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

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.

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 => { }
        }
    }
}

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

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.

@nikomatsakis

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

@nikomatsakis

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

@shepmaster

@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;
    }
}

Hi folks, how is it going now? I recently found this code that failed to compile, either:

fn get_default<'a, T: Default>(opt: &'a mut Option<T>) -> &'a mut T {
    match opt.as_mut() {
        Some(value) => value,
        None => opt.insert(T::default()),
    }
}

error[E0499]: cannot borrow `*opt` as mutable more than once at a time
 --> main.rs:4:17
  |
1 |   fn get_default<'a, T: Default>(opt: &'a mut Option<T>) -> &'a mut T {
  |                  -- lifetime `'a` defined here
2 |       match opt.as_mut() {
  |       -     ------------ first mutable borrow occurs here
  |  _____|
  | |
3 | |         Some(value) => value,
4 | |         None => opt.insert(T::default()),
  | |                 ^^^^^^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here
5 | |     }
  | |_____- returning this value requires that `*opt` is borrowed for `'a`

I don't think the second mutable borrow (line 4) on branch None is related to the first mutable borrow (line 2).

@frank-king

Thanks @frank-king for the minimal reproducer. I can confirm the issue on stable 1.83.0.

My workaround, in hopes that moves are elided:

pub fn get_default<'a, T: Default>(opt: &'a mut Option<T>) -> &'a mut T {
    let inner = match opt.take() {
        Some(inner) => inner,
        None => T::default(),
    };
    opt.insert(inner)
}

(didn't check if they are elided in my case, but it compiles)

Navigation Menu

Repository navigation

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

6 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

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

Description

Activity

nikomatsakis commented on Jan 23, 2018

Aaron1011 commented on Feb 1, 2018

nikomatsakis commented on Feb 1, 2018

Aaron1011 commented on Feb 1, 2018

nikomatsakis commented on Feb 1, 2018

Aaron1011 commented on Feb 2, 2018

nikomatsakis commented on Feb 5, 2018

nikomatsakis commented on Feb 5, 2018

nikomatsakis commented on Feb 5, 2018

nikomatsakis commented on Feb 5, 2018

6 remaining items

nikomatsakis commented on Apr 3, 2018

Aaron1011 commented on Apr 21, 2018

shepmaster commented on Nov 19, 2018

justhsu commented on Mar 29, 2019

frank-king commented on Jan 10, 2022

ahirner commented on Feb 16, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions