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

13 files changed, 205 insertions, 73 deletions

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 @@ use rustc::mir::{
     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 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
                 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 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> {
         }
     }
 
-    /// 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<Location> {
+        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<Location>,
+    ) -> 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<C<'a>> {
+        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