From 801c3f060fc3bf25a730d89aa0b80da4493f3584 Mon Sep 17 00:00:00 2001 From: Santiago Pastorino Date: Tue, 20 Nov 2018 17:48:16 -0300 Subject: [PATCH] Fix erroneous loop diagnostic in nll This commit fixes the logic of detecting when a use happen in a later iteration of where a borrow was defined Fixes #53773 --- .../borrow_check/nll/explain_borrow/mod.rs | 179 ++++++++++++------ .../borrowck-for-loop-head-linkage.nll.stderr | 4 +- .../borrowck-lend-flow-loop.nll.stderr | 4 +- ...ck-mut-borrow-linear-errors.ast.nll.stderr | 4 +- ...rrowck-mut-borrow-linear-errors.mir.stderr | 4 +- .../mut-borrow-outside-loop.nll.stderr | 2 +- ...ssue-52126-assign-op-invariance.nll.stderr | 2 +- src/test/ui/nll/issue-53773.rs | 49 +++++ src/test/ui/nll/issue-53773.stderr | 16 ++ .../borrowck-issue-49631.nll.stderr | 2 +- ...egions-escape-loop-via-variable.nll.stderr | 2 +- .../regions-escape-loop-via-vec.nll.stderr | 8 +- .../ui/vec/vec-mut-iter-borrow.nll.stderr | 2 +- 13 files changed, 205 insertions(+), 73 deletions(-) create mode 100644 src/test/ui/nll/issue-53773.rs create mode 100644 src/test/ui/nll/issue-53773.stderr diff --git a/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs b/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs index a6a6962bb15..86cab6cbfb2 100644 --- a/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs +++ b/src/librustc_mir/borrow_check/nll/explain_borrow/mod.rs @@ -1,3 +1,5 @@ +use std::collections::VecDeque; + use crate::borrow_check::borrow_set::BorrowData; use crate::borrow_check::error_reporting::UseSpans; use crate::borrow_check::nll::ConstraintDescription; @@ -9,6 +11,7 @@ Place, Projection, ProjectionElem, Rvalue, Statement, StatementKind, TerminatorKind }; +use rustc_data_structures::fx::FxHashSet; use rustc_errors::DiagnosticBuilder; use syntax_pos::Span; @@ -220,7 +223,8 @@ pub(in crate::borrow_check) fn explain_why_borrow_contains_point( let spans = self.move_spans(&Place::Local(local), location) .or_else(|| self.borrow_spans(span, location)); - if self.is_borrow_location_in_loop(context.loc) { + let borrow_location = context.loc; + if self.is_use_in_later_iteration_of_loop(borrow_location, location) { let later_use = self.later_use_kind(borrow, spans, location); BorrowExplanation::UsedLaterInLoop(later_use.0, later_use.1) } else { @@ -285,76 +289,139 @@ pub(in crate::borrow_check) fn explain_why_borrow_contains_point( } } - /// Checks if a borrow location is within a loop. - fn is_borrow_location_in_loop( + /// true if `borrow_location` can reach `use_location` by going through a loop and + /// `use_location` is also inside of that loop + fn is_use_in_later_iteration_of_loop( &self, borrow_location: Location, + use_location: Location, ) -> bool { - let mut visited_locations = Vec::new(); - let mut pending_locations = vec![ borrow_location ]; - debug!("is_in_loop: borrow_location={:?}", borrow_location); - - while let Some(location) = pending_locations.pop() { - debug!("is_in_loop: location={:?} pending_locations={:?} visited_locations={:?}", - location, pending_locations, visited_locations); - if location == borrow_location && visited_locations.contains(&borrow_location) { - // We've managed to return to where we started (and this isn't the start of the - // search). - debug!("is_in_loop: found!"); - return true; - } + let back_edge = self.reach_through_backedge(borrow_location, use_location); + back_edge.map_or(false, |back_edge| { + self.can_reach_head_of_loop(use_location, back_edge) + }) + } - // Skip locations we've been. - if visited_locations.contains(&location) { continue; } + /// Returns the outmost back edge if `from` location can reach `to` location passing through + /// that back edge + fn reach_through_backedge(&self, from: Location, to: Location) -> Option { + let mut visited_locations = FxHashSet::default(); + let mut pending_locations = VecDeque::new(); + visited_locations.insert(from); + pending_locations.push_back(from); + debug!("reach_through_backedge: from={:?} to={:?}", from, to,); + + let mut outmost_back_edge = None; + while let Some(location) = pending_locations.pop_front() { + debug!( + "reach_through_backedge: location={:?} outmost_back_edge={:?} + pending_locations={:?} visited_locations={:?}", + location, outmost_back_edge, pending_locations, visited_locations + ); + + if location == to && outmost_back_edge.is_some() { + // We've managed to reach the use location + debug!("reach_through_backedge: found!"); + return outmost_back_edge; + } let block = &self.mir.basic_blocks()[location.block]; - if location.statement_index == block.statements.len() { - // Add start location of the next blocks to pending locations. - match block.terminator().kind { - TerminatorKind::Goto { target } => { - pending_locations.push(target.start_location()); - }, - TerminatorKind::SwitchInt { ref targets, .. } => { - pending_locations.extend( - targets.into_iter().map(|target| target.start_location())); - }, - TerminatorKind::Drop { target, unwind, .. } | - TerminatorKind::DropAndReplace { target, unwind, .. } | - TerminatorKind::Assert { target, cleanup: unwind, .. } | - TerminatorKind::Yield { resume: target, drop: unwind, .. } | - TerminatorKind::FalseUnwind { real_target: target, unwind, .. } => { - pending_locations.push(target.start_location()); - if let Some(unwind) = unwind { - pending_locations.push(unwind.start_location()); - } - }, - TerminatorKind::Call { ref destination, cleanup, .. } => { - if let Some((_, destination)) = destination { - pending_locations.push(destination.start_location()); - } - if let Some(cleanup) = cleanup { - pending_locations.push(cleanup.start_location()); - } - }, - TerminatorKind::FalseEdges { real_target, ref imaginary_targets, .. } => { - pending_locations.push(real_target.start_location()); - pending_locations.extend( - imaginary_targets.into_iter().map(|target| target.start_location())); - }, - _ => {}, + + if location.statement_index < block.statements.len() { + let successor = location.successor_within_block(); + if visited_locations.insert(successor) { + pending_locations.push_back(successor); } } else { - // Add the next statement to pending locations. - pending_locations.push(location.successor_within_block()); + pending_locations.extend( + block + .terminator() + .successors() + .map(|bb| Location { + statement_index: 0, + block: *bb, + }) + .filter(|s| visited_locations.insert(*s)) + .map(|s| { + if self.is_back_edge(location, s) { + match outmost_back_edge { + None => { + outmost_back_edge = Some(location); + } + + Some(back_edge) + if location.dominates(back_edge, &self.dominators) => + { + outmost_back_edge = Some(location); + } + + Some(_) => {} + } + } + + s + }), + ); } + } + + None + } + + /// true if `from` location can reach `loop_head` location and `loop_head` dominates all the + /// intermediate nodes + fn can_reach_head_of_loop(&self, from: Location, loop_head: Location) -> bool { + self.find_loop_head_dfs(from, loop_head, &mut FxHashSet::default()) + } - // Keep track of where we have visited. - visited_locations.push(location); + fn find_loop_head_dfs( + &self, + from: Location, + loop_head: Location, + visited_locations: &mut FxHashSet, + ) -> bool { + visited_locations.insert(from); + + if from == loop_head { + return true; + } + + if loop_head.dominates(from, &self.dominators) { + let block = &self.mir.basic_blocks()[from.block]; + + if from.statement_index < block.statements.len() { + let successor = from.successor_within_block(); + + if !visited_locations.contains(&successor) + && self.find_loop_head_dfs(successor, loop_head, visited_locations) + { + return true; + } + } else { + for bb in block.terminator().successors() { + let successor = Location { + statement_index: 0, + block: *bb, + }; + + if !visited_locations.contains(&successor) + && self.find_loop_head_dfs(successor, loop_head, visited_locations) + { + return true; + } + } + } } false } + /// True if an edge `source -> target` is a backedge -- in other words, if the target + /// dominates the source. + fn is_back_edge(&self, source: Location, target: Location) -> bool { + target.dominates(source, &self.mir.dominators()) + } + /// Determine how the borrow was later used. fn later_use_kind( &self, diff --git a/src/test/ui/borrowck/borrowck-for-loop-head-linkage.nll.stderr b/src/test/ui/borrowck/borrowck-for-loop-head-linkage.nll.stderr index c0549c91e33..32ca24ba6ec 100644 --- a/src/test/ui/borrowck/borrowck-for-loop-head-linkage.nll.stderr +++ b/src/test/ui/borrowck/borrowck-for-loop-head-linkage.nll.stderr @@ -5,7 +5,7 @@ LL | for &x in &vector { | ------- | | | immutable borrow occurs here - | immutable borrow used here, in later iteration of loop + | immutable borrow later used here LL | let cap = vector.capacity(); LL | vector.extend(repeat(0)); //~ ERROR cannot borrow | ^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here @@ -17,7 +17,7 @@ LL | for &x in &vector { | ------- | | | immutable borrow occurs here - | immutable borrow used here, in later iteration of loop + | immutable borrow later used here ... LL | vector[1] = 5; //~ ERROR cannot borrow | ^^^^^^ mutable borrow occurs here diff --git a/src/test/ui/borrowck/borrowck-lend-flow-loop.nll.stderr b/src/test/ui/borrowck/borrowck-lend-flow-loop.nll.stderr index 19de3582c88..396fd6ffa0c 100644 --- a/src/test/ui/borrowck/borrowck-lend-flow-loop.nll.stderr +++ b/src/test/ui/borrowck/borrowck-lend-flow-loop.nll.stderr @@ -8,13 +8,13 @@ LL | borrow(&*v); //[ast]~ ERROR cannot borrow | ^^^ immutable borrow occurs here ... LL | *x = box 5; - | -- mutable borrow used here, in later iteration of loop + | -- mutable borrow later used here error[E0502]: cannot borrow `*v` as immutable because it is also borrowed as mutable --> $DIR/borrowck-lend-flow-loop.rs:109:16 | LL | **x += 1; - | -------- mutable borrow used here, in later iteration of loop + | -------- mutable borrow later used here LL | borrow(&*v); //[ast]~ ERROR cannot borrow | ^^^ immutable borrow occurs here ... diff --git a/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.ast.nll.stderr b/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.ast.nll.stderr index 806c3a623bc..0f077765336 100644 --- a/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.ast.nll.stderr +++ b/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.ast.nll.stderr @@ -4,7 +4,7 @@ error[E0499]: cannot borrow `x` as mutable more than once at a time LL | 1 => { addr.push(&mut x); } //[ast]~ ERROR [E0499] | ---- ^^^^^^ second mutable borrow occurs here | | - | first borrow used here, in later iteration of loop + | first borrow later used here ... LL | _ => { addr.push(&mut x); } //[ast]~ ERROR [E0499] | ------ first mutable borrow occurs here @@ -13,7 +13,7 @@ error[E0499]: cannot borrow `x` as mutable more than once at a time --> $DIR/borrowck-mut-borrow-linear-errors.rs:15:30 | LL | 1 => { addr.push(&mut x); } //[ast]~ ERROR [E0499] - | ---- first borrow used here, in later iteration of loop + | ---- first borrow later used here LL | //[mir]~^ ERROR [E0499] LL | 2 => { addr.push(&mut x); } //[ast]~ ERROR [E0499] | ^^^^^^ second mutable borrow occurs here diff --git a/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.mir.stderr b/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.mir.stderr index 806c3a623bc..0f077765336 100644 --- a/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.mir.stderr +++ b/src/test/ui/borrowck/borrowck-mut-borrow-linear-errors.mir.stderr @@ -4,7 +4,7 @@ error[E0499]: cannot borrow `x` as mutable more than once at a time LL | 1 => { addr.push(&mut x); } //[ast]~ ERROR [E0499] | ---- ^^^^^^ second mutable borrow occurs here | | - | first borrow used here, in later iteration of loop + | first borrow later used here ... LL | _ => { addr.push(&mut x); } //[ast]~ ERROR [E0499] | ------ first mutable borrow occurs here @@ -13,7 +13,7 @@ error[E0499]: cannot borrow `x` as mutable more than once at a time --> $DIR/borrowck-mut-borrow-linear-errors.rs:15:30 | LL | 1 => { addr.push(&mut x); } //[ast]~ ERROR [E0499] - | ---- first borrow used here, in later iteration of loop + | ---- first borrow later used here LL | //[mir]~^ ERROR [E0499] LL | 2 => { addr.push(&mut x); } //[ast]~ ERROR [E0499] | ^^^^^^ second mutable borrow occurs here diff --git a/src/test/ui/borrowck/mut-borrow-outside-loop.nll.stderr b/src/test/ui/borrowck/mut-borrow-outside-loop.nll.stderr index 7e183116c46..9b20fc02319 100644 --- a/src/test/ui/borrowck/mut-borrow-outside-loop.nll.stderr +++ b/src/test/ui/borrowck/mut-borrow-outside-loop.nll.stderr @@ -17,7 +17,7 @@ LL | let inner_second = &mut inner_void; //~ ERROR cannot borrow | ^^^^^^^^^^^^^^^ second mutable borrow occurs here LL | inner_second.use_mut(); LL | inner_first.use_mut(); - | ----------- first borrow used here, in later iteration of loop + | ----------- first borrow later used here error: aborting due to 2 previous errors diff --git a/src/test/ui/issues/issue-52126-assign-op-invariance.nll.stderr b/src/test/ui/issues/issue-52126-assign-op-invariance.nll.stderr index 8332cf1b3a3..d231f621e59 100644 --- a/src/test/ui/issues/issue-52126-assign-op-invariance.nll.stderr +++ b/src/test/ui/issues/issue-52126-assign-op-invariance.nll.stderr @@ -5,7 +5,7 @@ LL | let v: Vec<&str> = line.split_whitespace().collect(); | ^^^^ borrowed value does not live long enough ... LL | acc += cnt2; - | --- borrow used here, in later iteration of loop + | --- borrow later used here ... LL | } | - `line` dropped here while still borrowed diff --git a/src/test/ui/nll/issue-53773.rs b/src/test/ui/nll/issue-53773.rs new file mode 100644 index 00000000000..62e1631dcf3 --- /dev/null +++ b/src/test/ui/nll/issue-53773.rs @@ -0,0 +1,49 @@ +#![feature(nll)] + +struct Archive; +struct ArchiveIterator<'a> { + x: &'a Archive, +} +struct ArchiveChild<'a> { + x: &'a Archive, +} + +struct A { + raw: &'static mut Archive, +} +struct Iter<'a> { + raw: &'a mut ArchiveIterator<'a>, +} +struct C<'a> { + raw: &'a mut ArchiveChild<'a>, +} + +impl A { + pub fn iter(&self) -> Iter<'_> { + panic!() + } +} +impl Drop for A { + fn drop(&mut self) {} +} +impl<'a> Drop for C<'a> { + fn drop(&mut self) {} +} + +impl<'a> Iterator for Iter<'a> { + type Item = C<'a>; + fn next(&mut self) -> Option> { + panic!() + } +} + +fn error(archive: &A) { + let mut members: Vec<&mut ArchiveChild<'_>> = vec![]; + for child in archive.iter() { + members.push(child.raw); + //~^ ERROR borrow may still be in use when destructor runs [E0713] + } + members.len(); +} + +fn main() {} diff --git a/src/test/ui/nll/issue-53773.stderr b/src/test/ui/nll/issue-53773.stderr new file mode 100644 index 00000000000..92a9946068c --- /dev/null +++ b/src/test/ui/nll/issue-53773.stderr @@ -0,0 +1,16 @@ +error[E0713]: borrow may still be in use when destructor runs + --> $DIR/issue-53773.rs:43:22 + | +LL | members.push(child.raw); + | ^^^^^^^^^ +LL | //~^ ERROR borrow may still be in use when destructor runs [E0713] +LL | } + | - here, drop of `child` needs exclusive access to `*child.raw`, because the type `C<'_>` implements the `Drop` trait +LL | members.len(); + | ------- borrow later used here + | + = note: consider using a `let` binding to create a longer lived value + +error: aborting due to previous error + +For more information about this error, try `rustc --explain E0713`. diff --git a/src/test/ui/rfc-2005-default-binding-mode/borrowck-issue-49631.nll.stderr b/src/test/ui/rfc-2005-default-binding-mode/borrowck-issue-49631.nll.stderr index 9e242712b9e..3a6f66ca4da 100644 --- a/src/test/ui/rfc-2005-default-binding-mode/borrowck-issue-49631.nll.stderr +++ b/src/test/ui/rfc-2005-default-binding-mode/borrowck-issue-49631.nll.stderr @@ -7,7 +7,7 @@ LL | foo.mutate(); | ^^^^^^^^^^^^ mutable borrow occurs here LL | //~^ ERROR cannot borrow `foo` as mutable LL | println!("foo={:?}", *string); - | ------- immutable borrow used here, in later iteration of loop + | ------- immutable borrow later used here error: aborting due to previous error diff --git a/src/test/ui/span/regions-escape-loop-via-variable.nll.stderr b/src/test/ui/span/regions-escape-loop-via-variable.nll.stderr index 841e3c48414..42df6685297 100644 --- a/src/test/ui/span/regions-escape-loop-via-variable.nll.stderr +++ b/src/test/ui/span/regions-escape-loop-via-variable.nll.stderr @@ -2,7 +2,7 @@ error[E0597]: `x` does not live long enough --> $DIR/regions-escape-loop-via-variable.rs:11:13 | LL | let x = 1 + *p; - | -- borrow used here, in later iteration of loop + | -- borrow later used here LL | p = &x; | ^^ borrowed value does not live long enough LL | } diff --git a/src/test/ui/span/regions-escape-loop-via-vec.nll.stderr b/src/test/ui/span/regions-escape-loop-via-vec.nll.stderr index ea64828fedd..e07fb727782 100644 --- a/src/test/ui/span/regions-escape-loop-via-vec.nll.stderr +++ b/src/test/ui/span/regions-escape-loop-via-vec.nll.stderr @@ -7,7 +7,7 @@ LL | while x < 10 { //~ ERROR cannot use `x` because it was mutably borrowed | ^ use of borrowed `x` LL | let mut z = x; //~ ERROR cannot use `x` because it was mutably borrowed LL | _y.push(&mut z); - | -- borrow used here, in later iteration of loop + | -- borrow later used here error[E0503]: cannot use `x` because it was mutably borrowed --> $DIR/regions-escape-loop-via-vec.rs:6:21 @@ -18,7 +18,7 @@ LL | while x < 10 { //~ ERROR cannot use `x` because it was mutably borrowed LL | let mut z = x; //~ ERROR cannot use `x` because it was mutably borrowed | ^ use of borrowed `x` LL | _y.push(&mut z); - | -- borrow used here, in later iteration of loop + | -- borrow later used here error[E0597]: `z` does not live long enough --> $DIR/regions-escape-loop-via-vec.rs:7:17 @@ -26,7 +26,7 @@ error[E0597]: `z` does not live long enough LL | _y.push(&mut z); | -- ^^^^^^ borrowed value does not live long enough | | - | borrow used here, in later iteration of loop + | borrow later used here ... LL | } | - `z` dropped here while still borrowed @@ -38,7 +38,7 @@ LL | let mut _y = vec![&mut x]; | ------ borrow of `x` occurs here ... LL | _y.push(&mut z); - | -- borrow used here, in later iteration of loop + | -- borrow later used here LL | //~^ ERROR `z` does not live long enough LL | x += 1; //~ ERROR cannot assign | ^^^^^^ use of borrowed `x` diff --git a/src/test/ui/vec/vec-mut-iter-borrow.nll.stderr b/src/test/ui/vec/vec-mut-iter-borrow.nll.stderr index 73cddd8d680..c77be26f019 100644 --- a/src/test/ui/vec/vec-mut-iter-borrow.nll.stderr +++ b/src/test/ui/vec/vec-mut-iter-borrow.nll.stderr @@ -5,7 +5,7 @@ LL | for x in &mut xs { | ------- | | | first mutable borrow occurs here - | first borrow used here, in later iteration of loop + | first borrow later used here LL | xs.push(1) //~ ERROR cannot borrow `xs` | ^^ second mutable borrow occurs here -- 2.44.0