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.)
Niko Matsakis at 2018-01-23 15:44:02
I'd like to work on this.
Aaron Hill at 2018-02-01 20:25:04
@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 =)
Niko Matsakis at 2018-02-01 20:32:08
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() {}Aaron Hill at 2018-02-01 20:45:55
I think this one is gonna be tricky. I think it's a similar problem to the one identified here https://github.com/nikomatsakis/borrowck/issues/18.
I feel like I can't quite describe it precisely, but what happens is something like this:
- We create the borrow in
add_wordwith the call tocursor.get_child. It has lifetime_#33r. - On the
Somepath, we require that this lifetime'_#33rhas to outlive the lifetime associated withcursor(let's call itR)- In theory, this ought to exclude the
Nonepath
- In theory, this ought to exclude the
- 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
Noneblock.
It may be that we want to make some kind of deeper change to the analysis here.
Niko Matsakis at 2018-02-01 20:47:17
- We create the borrow in
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
selfis 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.Aaron Hill at 2018-02-02 20:48:18
@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
Nonepath of iteration N+1. This is why the borrow extends into theNonepath`. 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 =)
Niko Matsakis at 2018-02-05 10:42:34
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.
Niko Matsakis at 2018-02-05 12:08:20
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 => { } } } }Niko Matsakis at 2018-02-05 16:07:19
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. =)
Niko Matsakis at 2018-02-05 16:47:51
@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 wherevar(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!
Aaron Hill at 2018-02-06 01:31:53
@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 @ Pso 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.Niko Matsakis at 2018-02-06 17:12:19
@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: '_1if_2is "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 oftemp.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_outlivesto 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?
Aaron Hill at 2018-02-07 23:20:13
-
@Aaron1011 I'll take a look -- might take a day or two though -- as you say, these are delicate changes.
Niko Matsakis at 2018-02-08 16:57:42
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.
Niko Matsakis at 2018-04-03 14:43:50
@nikomatsakis: Sounds good to me! Feel free to ping me on Github or IRC when it's ready.
Aaron Hill at 2018-04-21 23:56:39
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 hereTested with 1.31.0-beta.14 and edition 2018
Jake Goulding at 2018-11-19 21:03:15
@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; } }justhsu at 2019-03-29 17:33:34
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
Noneis related to the first mutable borrow (line 2).Frank King at 2022-01-10 15:15:17
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)
Alexander Hirner at 2025-02-16 19:35:26