Auto merge of #45025 - pnkfelix:mir-borrowck-moves-of-supporting-prefixes-invalidate-uses-too, r=arielb1

MIR-borrowck: moves of prefixes invalidate uses too

I overlooked the fact that when we check if a path is moved, we need to check for interference between the (shallow) prefixes and the use in question.

~~Long term, we may want to revise how this computation is done. For example, it might be better to represent the set of invalidated prefixes in the dataflow computation (the `maybe_uninitialized` dataflow), and thus avoid one of the loops in the code here.~~
 * Update: I was wrong in my original recollection of the dataflow code, which actually does the right thing, in terms of precisely tracking substructure initialization and movement.

Fix #44833

----

Update: The initial version of this PR's description (and the code as well) erroneously focused on supporting prefixes. ~~But the two main cases of interest are: 1. the *shallow* prefixes, and 2. the deref-free prefix built off a local (if the lvalue is indeed built off a local)~~

Update 2: The main cases of interest are in fact: 1. the nearest prefix with a MovePath, and 2. the suffixes.

7 files changed, 276 insertions, 17 deletions

diff --git a/src/librustc_mir/borrow_check.rs b/src/librustc_mir/borrow_check.rs
index 62c7c7db13b..ff923ce259f 100644
--- a/src/librustc_mir/borrow_check.rs
+++ b/src/librustc_mir/borrow_check.rs
@@ -586,7 +586,7 @@ impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
                                                 context: Context,
                                                 (lvalue, span): (&Lvalue<'gcx>, Span),
                                                 flow_state: &InProgress<'b, 'gcx>) {
-        let move_data = flow_state.inits.base_results.operator().move_data();
+        let move_data = self.move_data;
 
         // determine if this path has a non-mut owner (and thus needs checking).
         let mut l = lvalue;
@@ -611,7 +611,7 @@ impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
             }
         }
 
-        if let Some(mpi) = self.move_path_for_lvalue(context, move_data, lvalue) {
+        if let Some(mpi) = self.move_path_for_lvalue(lvalue) {
             if flow_state.inits.curr_state.contains(&mpi) {
                 // may already be assigned before reaching this statement;
                 // report error.
@@ -642,21 +642,107 @@ impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
         let lvalue = self.base_path(lvalue_span.0);
 
         let maybe_uninits = &flow_state.uninits;
-        let move_data = maybe_uninits.base_results.operator().move_data();
-        if let Some(mpi) = self.move_path_for_lvalue(context, move_data, lvalue) {
-            if maybe_uninits.curr_state.contains(&mpi) {
-                // find and report move(s) that could cause this to be uninitialized
+
+        // Bad scenarios:
+        //
+        // 1. Move of `a.b.c`, use of `a.b.c`
+        // 2. Move of `a.b.c`, use of `a.b.c.d` (without first reinitializing `a.b.c.d`)
+        // 3. Move of `a.b.c`, use of `a` or `a.b`
+        // 4. Uninitialized `(a.b.c: &_)`, use of `*a.b.c`; note that with
+        //    partial initialization support, one might have `a.x`
+        //    initialized but not `a.b`.
+        //
+        // OK scenarios:
+        //
+        // 5. Move of `a.b.c`, use of `a.b.d`
+        // 6. Uninitialized `a.x`, initialized `a.b`, use of `a.b`
+        // 7. Copied `(a.b: &_)`, use of `*(a.b).c`; note that `a.b`
+        //    must have been initialized for the use to be sound.
+        // 8. Move of `a.b.c` then reinit of `a.b.c.d`, use of `a.b.c.d`
+
+        // The dataflow tracks shallow prefixes distinctly (that is,
+        // field-accesses on P distinctly from P itself), in order to
+        // track substructure initialization separately from the whole
+        // structure.
+        //
+        // E.g., when looking at (*a.b.c).d, if the closest prefix for
+        // which we have a MovePath is `a.b`, then that means that the
+        // initialization state of `a.b` is all we need to inspect to
+        // know if `a.b.c` is valid (and from that we infer that the
+        // dereference and `.d` access is also valid, since we assume
+        // `a.b.c` is assigned a reference to a initialized and
+        // well-formed record structure.)
+
+        // Therefore, if we seek out the *closest* prefix for which we
+        // have a MovePath, that should capture the initialization
+        // state for the lvalue scenario.
+        //
+        // This code covers scenarios 1, 2, and 4.
+
+        debug!("check_if_path_is_moved part1 lvalue: {:?}", lvalue);
+        match self.move_path_closest_to(lvalue) {
+            Ok(mpi) => {
+                if maybe_uninits.curr_state.contains(&mpi) {
+                    self.report_use_of_moved(context, desired_action, lvalue_span);
+                    return; // don't bother finding other problems.
+                }
+            }
+            Err(NoMovePathFound::ReachedStatic) => {
+                // Okay: we do not build MoveData for static variables
+            }
+
+            // Only query longest prefix with a MovePath, not further
+            // ancestors; dataflow recurs on children when parents
+            // move (to support partial (re)inits).
+            //
+            // (I.e. querying parents breaks scenario 8; but may want
+            // to do such a query based on partial-init feature-gate.)
+        }
+
+        // A move of any shallow suffix of `lvalue` also interferes
+        // with an attempt to use `lvalue`. This is scenario 3 above.
+        //
+        // (Distinct from handling of scenarios 1+2+4 above because
+        // `lvalue` does not interfere with suffixes of its prefixes,
+        // e.g. `a.b.c` does not interfere with `a.b.d`)
+
+        debug!("check_if_path_is_moved part2 lvalue: {:?}", lvalue);
+        if let Some(mpi) = self.move_path_for_lvalue(lvalue) {
+            if let Some(_) = maybe_uninits.has_any_child_of(mpi) {
                 self.report_use_of_moved(context, desired_action, lvalue_span);
-            } else {
-                // sanity check: initialized on *some* path, right?
-                assert!(flow_state.inits.curr_state.contains(&mpi));
+                return; // don't bother finding other problems.
             }
         }
     }
 
+    /// Currently MoveData does not store entries for all lvalues in
+    /// the input MIR. For example it will currently filter out
+    /// lvalues that are Copy; thus we do not track lvalues of shared
+    /// reference type. This routine will walk up an lvalue along its
+    /// prefixes, searching for a foundational lvalue that *is*
+    /// tracked in the MoveData.
+    ///
+    /// An Err result includes a tag indicated why the search failed.
+    /// Currenly this can only occur if the lvalue is built off of a
+    /// static variable, as we do not track those in the MoveData.
+    fn move_path_closest_to(&mut self, lvalue: &Lvalue<'gcx>)
+                            -> Result<MovePathIndex, NoMovePathFound>
+    {
+        let mut last_prefix = lvalue;
+        for prefix in self.prefixes(lvalue, PrefixSet::All) {
+            if let Some(mpi) = self.move_path_for_lvalue(prefix) {
+                return Ok(mpi);
+            }
+            last_prefix = prefix;
+        }
+        match *last_prefix {
+            Lvalue::Local(_) => panic!("should have move path for every Local"),
+            Lvalue::Projection(_) => panic!("PrefixSet::All meant dont stop for Projection"),
+            Lvalue::Static(_) => return Err(NoMovePathFound::ReachedStatic),
+        }
+    }
+
     fn move_path_for_lvalue(&mut self,
-                            _context: Context,
-                            move_data: &MoveData<'gcx>,
                             lvalue: &Lvalue<'gcx>)
                             -> Option<MovePathIndex>
     {
@@ -664,7 +750,7 @@ impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
         // to a direct owner of `lvalue` (which means there is nothing
         // that borrowck tracks for its analysis).
 
-        match move_data.rev_lookup.find(lvalue) {
+        match self.move_data.rev_lookup.find(lvalue) {
             LookupResult::Parent(_) => None,
             LookupResult::Exact(mpi) => Some(mpi),
         }
@@ -733,6 +819,11 @@ impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx>
     }
 }
 
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+enum NoMovePathFound {
+    ReachedStatic,
+}
+
 impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
     fn each_borrow_involving_path<F>(&mut self,
                                      _context: Context,
@@ -846,12 +937,19 @@ mod prefixes {
 
     #[derive(Copy, Clone, PartialEq, Eq, Debug)]
     pub(super) enum PrefixSet {
+        /// Doesn't stop until it returns the base case (a Local or
+        /// Static prefix).
         All,
+        /// Stops at any dereference.
         Shallow,
+        /// Stops at the deref of a shared reference.
         Supporting,
     }
 
     impl<'c, 'b, 'a: 'b+'c, 'gcx, 'tcx: 'a> MirBorrowckCtxt<'c, 'b, 'a, 'gcx, 'tcx> {
+        /// Returns an iterator over the prefixes of `lvalue`
+        /// (inclusive) from longest to smallest, potentially
+        /// terminating the iteration early based on `kind`.
         pub(super) fn prefixes<'d>(&self,
                                    lvalue: &'d Lvalue<'gcx>,
                                    kind: PrefixSet)
@@ -1340,6 +1438,35 @@ impl<'b, 'tcx: 'b> InProgress<'b, 'tcx> {
     }
 }
 
+impl<'b, 'tcx> FlowInProgress<MaybeUninitializedLvals<'b, 'tcx>> {
+    fn has_any_child_of(&self, mpi: MovePathIndex) -> Option<MovePathIndex> {
+        let move_data = self.base_results.operator().move_data();
+
+        let mut todo = vec![mpi];
+        let mut push_siblings = false; // don't look at siblings of original `mpi`.
+        while let Some(mpi) = todo.pop() {
+            if self.curr_state.contains(&mpi) {
+                return Some(mpi);
+            }
+            let move_path = &move_data.move_paths[mpi];
+            if let Some(child) = move_path.first_child {
+                todo.push(child);
+            }
+            if push_siblings {
+                if let Some(sibling) = move_path.next_sibling {
+                    todo.push(sibling);
+                }
+            } else {
+                // after we've processed the original `mpi`, we should
+                // always traverse the siblings of any of its
+                // children.
+                push_siblings = true;
+            }
+        }
+        return None;
+    }
+}
+
 impl<BD> FlowInProgress<BD> where BD: BitDenotation {
     fn each_state_bit<F>(&self, f: F) where F: FnMut(BD::Idx) {
         self.curr_state.each_bit(self.base_results.operator().bits_per_block(), f)
diff --git a/src/test/compile-fail/borrowck/borrowck-init-in-fru.rs b/src/test/compile-fail/borrowck/borrowck-init-in-fru.rs
index 569ddb80c2f..017318b6b21 100644
--- a/src/test/compile-fail/borrowck/borrowck-init-in-fru.rs
+++ b/src/test/compile-fail/borrowck/borrowck-init-in-fru.rs
@@ -8,6 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// revisions: ast mir
+//[mir]compile-flags: -Z emit-end-regions -Z borrowck-mir
+
 #[derive(Clone)]
 struct point {
     x: isize,
@@ -16,6 +19,9 @@ struct point {
 
 fn main() {
     let mut origin: point;
-    origin = point {x: 10,.. origin}; //~ ERROR use of possibly uninitialized variable: `origin.y`
+    origin = point {x: 10,.. origin};
+    //[ast]~^ ERROR use of possibly uninitialized variable: `origin.y` [E0381]
+    //[mir]~^^ ERROR (Ast) [E0381]
+    //[mir]~|  ERROR (Mir) [E0381]
     origin.clone();
 }
diff --git a/src/test/compile-fail/borrowck/borrowck-uninit-field-access.rs b/src/test/compile-fail/borrowck/borrowck-uninit-field-access.rs
new file mode 100644
index 00000000000..957086f6af1
--- /dev/null
+++ b/src/test/compile-fail/borrowck/borrowck-uninit-field-access.rs
@@ -0,0 +1,49 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// revisions: ast mir
+//[mir]compile-flags: -Z emit-end-regions -Z borrowck-mir
+
+// Check that do not allow access to fields of uninitialized or moved
+// structs.
+
+#[derive(Default)]
+struct Point {
+    x: isize,
+    y: isize,
+}
+
+#[derive(Default)]
+struct Line {
+    origin: Point,
+    middle: Point,
+    target: Point,
+}
+
+impl Line { fn consume(self) { } }
+
+fn main() {
+    let mut a: Point;
+    let _ = a.x + 1; //[ast]~ ERROR use of possibly uninitialized variable: `a.x`
+                     //[mir]~^ ERROR       [E0381]
+                     //[mir]~| ERROR (Mir) [E0381]
+
+    let mut line1 = Line::default();
+    let _moved = line1.origin;
+    let _ = line1.origin.x + 1; //[ast]~ ERROR use of collaterally moved value: `line1.origin.x`
+                                //[mir]~^       [E0382]
+                                //[mir]~| (Mir) [E0381]
+
+    let mut line2 = Line::default();
+    let _moved = (line2.origin, line2.middle);
+    line2.consume(); //[ast]~ ERROR use of partially moved value: `line2` [E0382]
+                     //[mir]~^       [E0382]
+                     //[mir]~| (Mir) [E0381]
+}
diff --git a/src/test/compile-fail/borrowck/borrowck-uninit-ref-chain.rs b/src/test/compile-fail/borrowck/borrowck-uninit-ref-chain.rs
new file mode 100644
index 00000000000..71f8693b210
--- /dev/null
+++ b/src/test/compile-fail/borrowck/borrowck-uninit-ref-chain.rs
@@ -0,0 +1,60 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// revisions: ast mir
+//[mir]compile-flags: -Z emit-end-regions -Z borrowck-mir
+
+struct S<X, Y> {
+    x: X,
+    y: Y,
+}
+
+fn main() {
+    let x: &&Box<i32>;
+    let _y = &**x; //[ast]~ ERROR use of possibly uninitialized variable: `**x` [E0381]
+                   //[mir]~^ (Ast) [E0381]
+                   //[mir]~| (Mir) [E0381]
+
+    let x: &&S<i32, i32>;
+    let _y = &**x; //[ast]~ ERROR use of possibly uninitialized variable: `**x` [E0381]
+                   //[mir]~^ (Ast) [E0381]
+                   //[mir]~| (Mir) [E0381]
+
+    let x: &&i32;
+    let _y = &**x; //[ast]~ ERROR use of possibly uninitialized variable: `**x` [E0381]
+                   //[mir]~^ (Ast) [E0381]
+                   //[mir]~| (Mir) [E0381]
+
+
+    let mut a: S<i32, i32>;
+    a.x = 0;
+    let _b = &a.x; //[ast]~ ERROR use of possibly uninitialized variable: `a.x` [E0381]
+                   //[mir]~^ ERROR (Ast) [E0381]
+                   // (deliberately *not* an error under MIR-borrowck)
+
+    let mut a: S<&&i32, &&i32>;
+    a.x = &&0;
+    let _b = &**a.x; //[ast]~ ERROR use of possibly uninitialized variable: `**a.x` [E0381]
+                     //[mir]~^ ERROR (Ast) [E0381]
+                     // (deliberately *not* an error under MIR-borrowck)
+
+
+    let mut a: S<i32, i32>;
+    a.x = 0;
+    let _b = &a.y; //[ast]~ ERROR use of possibly uninitialized variable: `a.y` [E0381]
+                   //[mir]~^ ERROR (Ast) [E0381]
+                   //[mir]~| ERROR (Mir) [E0381]
+
+    let mut a: S<&&i32, &&i32>;
+    a.x = &&0;
+    let _b = &**a.y; //[ast]~ ERROR use of possibly uninitialized variable: `**a.y` [E0381]
+                     //[mir]~^ ERROR (Ast) [E0381]
+                     //[mir]~| ERROR (Mir) [E0381]
+}
diff --git a/src/test/compile-fail/borrowck/borrowck-use-in-index-lvalue.rs b/src/test/compile-fail/borrowck/borrowck-use-in-index-lvalue.rs
index 7291bcd2ce1..2b567ebd2db 100644
--- a/src/test/compile-fail/borrowck/borrowck-use-in-index-lvalue.rs
+++ b/src/test/compile-fail/borrowck/borrowck-use-in-index-lvalue.rs
@@ -8,12 +8,19 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// revisions: ast mir
+//[mir]compile-flags: -Z emit-end-regions -Z borrowck-mir
+
 fn test() {
     let w: &mut [isize];
-    w[5] = 0; //~ ERROR use of possibly uninitialized variable: `*w`
+    w[5] = 0; //[ast]~ ERROR use of possibly uninitialized variable: `*w` [E0381]
+              //[mir]~^ ERROR (Ast) [E0381]
+              //[mir]~| ERROR (Mir) [E0381]
 
     let mut w: &mut [isize];
-    w[5] = 0; //~ ERROR use of possibly uninitialized variable: `*w`
+    w[5] = 0; //[ast]~ ERROR use of possibly uninitialized variable: `*w` [E0381]
+              //[mir]~^ ERROR (Ast) [E0381]
+              //[mir]~| ERROR (Mir) [E0381]
 }
 
 fn main() { test(); }
diff --git a/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast-trait.rs b/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast-trait.rs
index 796b455f5c7..a48d09b195a 100644
--- a/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast-trait.rs
+++ b/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast-trait.rs
@@ -8,6 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// revisions: ast mir
+//[mir]compile-flags: -Z emit-end-regions -Z borrowck-mir
+
 // Variation on `borrowck-use-uninitialized-in-cast` in which we do a
 // trait cast from an uninitialized source. Issue #20791.
 
@@ -16,5 +19,7 @@ impl Foo for i32 { }
 
 fn main() {
     let x: &i32;
-    let y = x as *const Foo; //~ ERROR use of possibly uninitialized variable: `*x`
+    let y = x as *const Foo; //[ast]~ ERROR use of possibly uninitialized variable: `*x`
+                             //[mir]~^ ERROR (Ast) [E0381]
+                             //[mir]~| ERROR (Mir) [E0381]
 }
diff --git a/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast.rs b/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast.rs
index 3f429bbd4b6..bdd90a3ce1e 100644
--- a/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast.rs
+++ b/src/test/compile-fail/borrowck/borrowck-use-uninitialized-in-cast.rs
@@ -8,11 +8,16 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+// revisions: ast mir
+//[mir]compile-flags: -Z emit-end-regions -Z borrowck-mir
+
 // Check that we detect unused values that are cast to other things.
 // The problem was specified to casting to `*`, as creating unsafe
 // pointers was not being fully checked. Issue #20791.
 
 fn main() {
     let x: &i32;
-    let y = x as *const i32; //~ ERROR use of possibly uninitialized variable: `*x`
+    let y = x as *const i32; //[ast]~ ERROR use of possibly uninitialized variable: `*x` [E0381]
+                             //[mir]~^ ERROR (Ast) [E0381]
+                             //[mir]~| ERROR (Mir) [E0381]
 }