Polonius: emit initialization/move tracking facts

- var_starts_path
- parent
- initialized_at
- moved_out_at

This also switches to the intended emission of `var_drop_used` fact emission,
where that fact is always emitted on a drop-use of a variable, regardless of its
initialization status, as Polonius now handles that.

4 files changed, 74 insertions, 9 deletions

diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs
index 19a3d0eb03d..9b920eb1559 100644
--- a/src/librustc_mir/borrow_check/nll/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/mod.rs
@@ -4,14 +4,14 @@ use crate::borrow_check::nll::facts::AllFactsExt;
 use crate::borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints};
 use crate::borrow_check::nll::region_infer::values::RegionValueElements;
 use crate::dataflow::indexes::BorrowIndex;
-use crate::dataflow::move_paths::{MoveData, MovePathIndex};
+use crate::dataflow::move_paths::{InitLocation, MoveData, MovePathIndex, InitKind};
 use crate::dataflow::FlowAtLocation;
 use crate::dataflow::MaybeInitializedPlaces;
 use crate::transform::MirSource;
 use crate::borrow_check::Upvar;
 use rustc::hir::def_id::DefId;
 use rustc::infer::InferCtxt;
-use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Local, Body, Promoted};
+use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Local, Location, Body, LocalKind, BasicBlock, Promoted};
 use rustc::ty::{self, RegionKind, RegionVid};
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc_errors::Diagnostic;
@@ -69,6 +69,61 @@ pub(in crate::borrow_check) fn replace_regions_in_mir<'cx, 'tcx>(
     universal_regions
 }
 
+
+// This function populates an AllFacts instance with base facts related to
+// MovePaths and needed for the move analysis.
+fn populate_polonius_move_facts(all_facts: &mut AllFacts, move_data: &MoveData<'_>, location_table: &LocationTable, body: &Body<'_>) {
+    all_facts.var_starts_path.extend(move_data.rev_lookup.iter_locals_enumerated().map(|(v, &m)| (v, m)));
+
+    for (idx, move_path) in move_data.move_paths.iter_enumerated() {
+        all_facts.parent.extend(move_path.parents(&move_data.move_paths).iter().map(|&parent| (parent, idx)));
+    }
+
+    // initialized_at
+    for init in move_data.inits.iter() {
+
+        match init.location {
+            InitLocation::Statement(location) => {
+                let block_data = &body[location.block];
+                let is_terminator = location.statement_index == block_data.statements.len();
+
+                if is_terminator && init.kind == InitKind::NonPanicPathOnly {
+                    // We are at the terminator of an init that has a panic path,
+                    // and where the init should not happen on panic
+
+                    for &successor in block_data.terminator().successors() {
+                        if body[successor].is_cleanup {
+                            continue;
+                        }
+
+                        // The initialization happened in (or rather, when arriving at)
+                        // the successors, but not in the unwind block.
+                        let first_statement = Location { block: successor, statement_index: 0};
+                        all_facts.initialized_at.push((init.path, location_table.start_index(first_statement)));
+                    }
+
+                } else {
+                    // In all other cases, the initialization just happens at the
+                    // midpoint, like any other effect.
+                    all_facts.initialized_at.push((init.path, location_table.mid_index(location)));
+                }
+            },
+            // Arguments are initialized on function entry
+            InitLocation::Argument(local) => {
+                assert!(body.local_kind(local) == LocalKind::Arg);
+                let fn_entry = Location {block: BasicBlock::from_u32(0u32), statement_index: 0 };
+                all_facts.initialized_at.push((init.path, location_table.start_index(fn_entry)));
+
+            }
+        }
+    }
+
+
+    // moved_out_at
+    // deinitialisation is assumed to always happen!
+    all_facts.moved_out_at.extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source))));
+}
+
 /// Computes the (non-lexical) regions from the input MIR.
 ///
 /// This may result in errors being reported.
@@ -123,6 +178,7 @@ pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
         all_facts
             .universal_region
             .extend(universal_regions.universal_regions());
+        populate_polonius_move_facts(all_facts, move_data, location_table, body);
     }
 
     // Create the region inference context, taking ownership of the
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs
index 20d7ec55e3e..dcdacbbe5be 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/polonius.rs
@@ -13,6 +13,7 @@ struct LivenessPointFactsExtractor<'me> {
     var_defined: &'me mut VarPointRelations,
     var_used: &'me mut VarPointRelations,
     location_table: &'me LocationTable,
+    var_drop_used: &'me mut VarPointRelations,
 }
 
 // A Visitor to walk through the MIR and extract point-wise facts
@@ -30,6 +31,11 @@ impl LivenessPointFactsExtractor<'_> {
         debug!("LivenessFactsExtractor::insert_use()");
         self.var_used.push((local, self.location_to_index(location)));
     }
+
+    fn insert_drop_use(&mut self, local: Local, location: Location) {
+        debug!("LivenessFactsExtractor::insert_drop_use()");
+        self.var_drop_used.push((local, self.location_to_index(location)));
+    }
 }
 
 impl Visitor<'tcx> for LivenessPointFactsExtractor<'_> {
@@ -37,8 +43,8 @@ impl Visitor<'tcx> for LivenessPointFactsExtractor<'_> {
         match categorize(context) {
             Some(DefUse::Def) => self.insert_def(local, location),
             Some(DefUse::Use) => self.insert_use(local, location),
+            Some(DefUse::Drop) => self.insert_drop_use(local, location),
             _ => (),
-            // NOTE: Drop handling is now done in trace()
         }
     }
 }
@@ -65,6 +71,7 @@ pub(super) fn populate_var_liveness_facts(
         LivenessPointFactsExtractor {
             var_defined: &mut facts.var_defined,
             var_used: &mut facts.var_used,
+            var_drop_used: &mut facts.var_drop_used,
             location_table,
         }
         .visit_body(mir);
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
index de085fc480a..1e1768a8e46 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness/trace.rs
@@ -273,11 +273,6 @@ impl LivenessResults<'me, 'typeck, 'flow, 'tcx> {
             debug_assert_eq!(self.cx.body.terminator_loc(location.block), location,);
 
             if self.cx.initialized_at_terminator(location.block, mpi) {
-                // FIXME: this analysis (the initialization tracking) should be
-                // done in Polonius, but isn't yet.
-                if let Some(facts) = self.cx.typeck.borrowck_context.all_facts {
-                    facts.var_drop_used.push((local, self.cx.location_table.mid_index(location)));
-                }
                 if self.drop_live_at.insert(drop_point) {
                     self.drop_locations.push(location);
                     self.stack.push(drop_point);
diff --git a/src/librustc_mir/dataflow/move_paths/mod.rs b/src/librustc_mir/dataflow/move_paths/mod.rs
index e5a19572170..07b9b662a07 100644
--- a/src/librustc_mir/dataflow/move_paths/mod.rs
+++ b/src/librustc_mir/dataflow/move_paths/mod.rs
@@ -1,9 +1,10 @@
 use rustc::ty::{Ty, TyCtxt};
 use rustc::mir::*;
 use rustc::util::nodemap::FxHashMap;
-use rustc_data_structures::indexed_vec::{Idx, IndexVec};
+use rustc_data_structures::indexed_vec::{Idx, IndexVec, Enumerated};
 use smallvec::SmallVec;
 use syntax_pos::{Span};
+use core::slice::Iter;
 
 use std::fmt;
 use std::ops::{Index, IndexMut};
@@ -262,6 +263,12 @@ impl MovePathLookup {
     pub fn find_local(&self, local: Local) -> MovePathIndex {
         self.locals[local]
     }
+
+    /// An enumerated iterator of `local`s and their associated
+    /// `MovePathIndex`es.
+    pub fn iter_locals_enumerated(&self) -> Enumerated<Local, Iter<'_, MovePathIndex>> {
+        self.locals.iter_enumerated()
+    }
 }
 
 #[derive(Debug)]