Add tracking of causes for nll

7 files changed, 185 insertions, 39 deletions

diff --git a/src/librustc_mir/borrow_check/nll/constraint_generation.rs b/src/librustc_mir/borrow_check/nll/constraint_generation.rs
index 673e85e6b61..bdacd831cb6 100644
--- a/src/librustc_mir/borrow_check/nll/constraint_generation.rs
+++ b/src/librustc_mir/borrow_check/nll/constraint_generation.rs
@@ -20,7 +20,7 @@ use rustc::ty::subst::Substs;
 use rustc::ty::fold::TypeFoldable;
 
 use super::ToRegionVid;
-use super::region_infer::RegionInferenceContext;
+use super::region_infer::{RegionInferenceContext, Cause};
 
 pub(super) fn generate_constraints<'cx, 'gcx, 'tcx>(
     infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
@@ -53,14 +53,14 @@ impl<'cg, 'cx, 'gcx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'gcx
     /// We sometimes have `substs` within an rvalue, or within a
     /// call. Make them live at the location where they appear.
     fn visit_substs(&mut self, substs: &&'tcx Substs<'tcx>, location: Location) {
-        self.add_regular_live_constraint(*substs, location);
+        self.add_regular_live_constraint(*substs, location, Cause::LiveOther(location));
         self.super_substs(substs);
     }
 
     /// We sometimes have `region` within an rvalue, or within a
     /// call. Make them live at the location where they appear.
     fn visit_region(&mut self, region: &ty::Region<'tcx>, location: Location) {
-        self.add_regular_live_constraint(*region, location);
+        self.add_regular_live_constraint(*region, location, Cause::LiveOther(location));
         self.super_region(region);
     }
 
@@ -75,7 +75,7 @@ impl<'cg, 'cx, 'gcx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'gcx
                           ty_context);
             }
             TyContext::Location(location) => {
-                self.add_regular_live_constraint(*ty, location);
+                self.add_regular_live_constraint(*ty, location, Cause::LiveOther(location));
             }
         }
 
@@ -85,7 +85,7 @@ impl<'cg, 'cx, 'gcx, 'tcx> Visitor<'tcx> for ConstraintGeneration<'cg, 'cx, 'gcx
     /// We sometimes have `closure_substs` within an rvalue, or within a
     /// call. Make them live at the location where they appear.
     fn visit_closure_substs(&mut self, substs: &ClosureSubsts<'tcx>, location: Location) {
-        self.add_regular_live_constraint(*substs, location);
+        self.add_regular_live_constraint(*substs, location, Cause::LiveOther(location));
         self.super_closure_substs(substs);
     }
 
@@ -112,7 +112,7 @@ impl<'cx, 'cg, 'gcx, 'tcx> ConstraintGeneration<'cx, 'cg, 'gcx, 'tcx> {
     /// `location` -- i.e., it may be used later. This means that all
     /// regions appearing in the type `live_ty` must be live at
     /// `location`.
-    fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location)
+    fn add_regular_live_constraint<T>(&mut self, live_ty: T, location: Location, cause: Cause)
     where
         T: TypeFoldable<'tcx>,
     {
@@ -126,7 +126,7 @@ impl<'cx, 'cg, 'gcx, 'tcx> ConstraintGeneration<'cx, 'cg, 'gcx, 'tcx> {
             .tcx
             .for_each_free_region(&live_ty, |live_region| {
                 let vid = live_region.to_region_vid();
-                self.regioncx.add_live_point(vid, location);
+                self.regioncx.add_live_point(vid, location, &cause);
             });
     }
 
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs b/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs
index 59860d61ab9..d55b6018232 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/dfs.rs
@@ -15,6 +15,7 @@ use borrow_check::nll::universal_regions::UniversalRegions;
 use borrow_check::nll::region_infer::RegionInferenceContext;
 use borrow_check::nll::region_infer::values::{RegionElementIndex, RegionValueElements,
                                               RegionValues};
+use syntax::codemap::Span;
 use rustc::mir::{Location, Mir};
 use rustc::ty::RegionVid;
 use rustc_data_structures::fx::FxHashSet;
@@ -127,6 +128,7 @@ pub(super) struct CopyFromSourceToTarget<'v> {
     pub target_region: RegionVid,
     pub inferred_values: &'v mut RegionValues,
     pub constraint_point: Location,
+    pub constraint_span: Span,
 }
 
 impl<'v> DfsOp for CopyFromSourceToTarget<'v> {
@@ -143,14 +145,22 @@ impl<'v> DfsOp for CopyFromSourceToTarget<'v> {
     }
 
     fn add_to_target_region(&mut self, point_index: RegionElementIndex) -> Result<bool, !> {
-        Ok(self.inferred_values.add(self.target_region, point_index))
+        Ok(self.inferred_values.add_due_to_outlives(
+            self.source_region,
+            self.target_region,
+            point_index,
+            self.constraint_point,
+            self.constraint_span,
+        ))
     }
 
     fn add_universal_regions_outlived_by_source_to_target(&mut self) -> Result<bool, !> {
-        Ok(
-            self.inferred_values
-                .add_universal_regions_outlived_by(self.source_region, self.target_region),
-        )
+        Ok(self.inferred_values.add_universal_regions_outlived_by(
+            self.source_region,
+            self.target_region,
+            self.constraint_point,
+            self.constraint_span,
+        ))
     }
 }
 
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
index 58e16e7673a..28cb1489c43 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -17,7 +17,7 @@ use rustc::infer::RegionVariableOrigin;
 use rustc::infer::SubregionOrigin;
 use rustc::infer::region_constraints::{GenericKind, VarOrigins};
 use rustc::mir::{ClosureOutlivesRequirement, ClosureOutlivesSubject, ClosureRegionRequirements,
-                 Location, Mir};
+                 Local, Location, Mir};
 use rustc::traits::ObligationCause;
 use rustc::ty::{self, RegionVid, Ty, TypeFoldable};
 use rustc_data_structures::indexed_vec::IndexVec;
@@ -65,6 +65,8 @@ pub struct RegionInferenceContext<'tcx> {
     universal_regions: UniversalRegions<'tcx>,
 }
 
+struct TrackCauses(bool);
+
 struct RegionDefinition<'tcx> {
     /// Why we created this variable. Mostly these will be
     /// `RegionVariableOrigin::NLL`, but some variables get created
@@ -83,6 +85,38 @@ struct RegionDefinition<'tcx> {
     external_name: Option<ty::Region<'tcx>>,
 }
 
+/// NB: The variants in `Cause` are intentionally ordered. Lower
+/// values are preferred when it comes to error messages. Do not
+/// reorder willy nilly.
+#[derive(Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
+pub(crate) enum Cause {
+    /// point inserted because Local was live at the given Location
+    LiveVar(Local, Location),
+
+    /// point inserted because Local was dropped at the given Location
+    DropVar(Local, Location),
+
+    /// point inserted because the type was live at the given Location,
+    /// but not as part of some local variable
+    LiveOther(Location),
+
+    /// part of the initial set of values for a universally quantified region
+    UniversalRegion,
+
+    /// Element E was added to R because there was some
+    /// outlives obligation `R: R1 @ P` and `R1` contained `E`.
+    Outlives {
+        /// the reason that R1 had E
+        original_cause: Rc<Cause>,
+
+        /// the point P from the relation
+        constraint_location: Location,
+
+        /// The span indicating why we added the outlives constraint.
+        constraint_span: Span,
+    },
+}
+
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
 pub struct Constraint {
     // NB. The ordering here is not significant for correctness, but
@@ -212,7 +246,11 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         let mut result = Self {
             definitions,
             elements: elements.clone(),
-            liveness_constraints: RegionValues::new(elements, num_region_variables),
+            liveness_constraints: RegionValues::new(
+                elements,
+                num_region_variables,
+                TrackCauses(true),
+            ),
             inferred_values: None,
             constraints: Vec::new(),
             type_tests: Vec::new(),
@@ -262,11 +300,11 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
             // Add all nodes in the CFG to liveness constraints
             for point_index in self.elements.all_point_indices() {
-                self.liveness_constraints.add(variable, point_index);
+                self.liveness_constraints.add(variable, point_index, &Cause::UniversalRegion);
             }
 
             // Add `end(X)` into the set for X.
-            self.liveness_constraints.add(variable, variable);
+            self.liveness_constraints.add(variable, variable, &Cause::UniversalRegion);
         }
     }
 
@@ -306,13 +344,13 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     ///
     /// Returns `true` if this constraint is new and `false` is the
     /// constraint was already present.
-    pub(super) fn add_live_point(&mut self, v: RegionVid, point: Location) -> bool {
+    pub(super) fn add_live_point(&mut self, v: RegionVid, point: Location, cause: &Cause) -> bool {
         debug!("add_live_point({:?}, {:?})", v, point);
         assert!(self.inferred_values.is_none(), "values already inferred");
-        debug!("add_live_point: @{:?}", point);
+        debug!("add_live_point: @{:?} Adding cause {:?}", point, cause);
 
         let element = self.elements.index(point);
-        if self.liveness_constraints.add(v, element) {
+        if self.liveness_constraints.add(v, element, &cause) {
             true
         } else {
             false
@@ -416,6 +454,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                         target_region: constraint.sup,
                         inferred_values: &mut inferred_values,
                         constraint_point: constraint.point,
+                        constraint_span: constraint.span,
                     },
                 );
 
@@ -973,7 +1012,7 @@ impl<'gcx, 'tcx> ClosureRegionRequirementsExt<'gcx, 'tcx> for ClosureRegionRequi
     /// Given an instance T of the closure type, this method
     /// instantiates the "extra" requirements that we computed for the
     /// closure into the inference context. This has the effect of
-    /// adding new subregion obligations to existing variables.
+    /// adding new outlives obligations to existing variables.
     ///
     /// As described on `ClosureRegionRequirements`, the extra
     /// requirements are expressed in terms of regionvids that index
@@ -1075,3 +1114,18 @@ impl<'gcx, 'tcx> ClosureRegionRequirementsExt<'gcx, 'tcx> for ClosureRegionRequi
         })
     }
 }
+
+trait CauseExt {
+    fn outlives(&self, constraint_location: Location, constraint_span: Span) -> Cause;
+}
+
+impl CauseExt for Rc<Cause> {
+    /// Creates a derived cause due to an outlives constraint.
+    fn outlives(&self, constraint_location: Location, constraint_span: Span) -> Cause {
+        Cause::Outlives {
+            original_cause: self.clone(),
+            constraint_location,
+            constraint_span,
+        }
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/values.rs b/src/librustc_mir/borrow_check/nll/region_infer/values.rs
index b1397c23988..b60f45bcdc4 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/values.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/values.rs
@@ -10,10 +10,14 @@
 
 use std::rc::Rc;
 use rustc_data_structures::bitvec::BitMatrix;
+use rustc_data_structures::fx::FxHashMap;
 use rustc_data_structures::indexed_vec::Idx;
 use rustc_data_structures::indexed_vec::IndexVec;
 use rustc::mir::{BasicBlock, Location, Mir};
 use rustc::ty::RegionVid;
+use syntax::codemap::Span;
+
+use super::{Cause, CauseExt, TrackCauses};
 
 /// Maps between the various kinds of elements of a region value to
 /// the internal indices that w use.
@@ -187,10 +191,22 @@ impl ToElementIndex for RegionElementIndex {
 pub(super) struct RegionValues {
     elements: Rc<RegionValueElements>,
     matrix: BitMatrix,
+
+    /// If cause tracking is enabled, maps from a pair (r, e)
+    /// consisting of a region `r` that contains some element `e` to
+    /// the reason that the element is contained. There should be an
+    /// entry for every bit set to 1 in `BitMatrix`.
+    causes: Option<CauseMap>,
 }
 
+type CauseMap = FxHashMap<(RegionVid, RegionElementIndex), Rc<Cause>>;
+
 impl RegionValues {
-    pub(super) fn new(elements: &Rc<RegionValueElements>, num_region_variables: usize) -> Self {
+    pub(super) fn new(
+        elements: &Rc<RegionValueElements>,
+        num_region_variables: usize,
+        track_causes: TrackCauses,
+    ) -> Self {
         assert!(
             elements.num_universal_regions <= num_region_variables,
             "universal regions are a subset of the region variables"
@@ -199,31 +215,80 @@ impl RegionValues {
         Self {
             elements: elements.clone(),
             matrix: BitMatrix::new(num_region_variables, elements.num_elements()),
+            causes: if track_causes.0 {
+                Some(CauseMap::default())
+            } else {
+                None
+            },
         }
     }
 
     /// Adds the given element to the value for the given region. Returns true if
     /// the element is newly added (i.e., was not already present).
-    pub(super) fn add<E: ToElementIndex>(&mut self, r: RegionVid, elem: E) -> bool {
+    pub(super) fn add<E: ToElementIndex>(&mut self, r: RegionVid, elem: E, cause: &Cause) -> bool {
         let i = self.elements.index(elem);
+        self.add_internal(r, i, |_| cause.clone())
+    }
+
+    /// Internal method to add an element to a region.
+    ///
+    /// Takes a "lazy" cause -- this function will return the cause, but it will only
+    /// be invoked if cause tracking is enabled.
+    fn add_internal<F>(&mut self, r: RegionVid, i: RegionElementIndex, make_cause: F) -> bool
+    where
+        F: FnOnce(&CauseMap) -> Cause,
+    {
         if self.matrix.add(r.index(), i.index()) {
             debug!("add(r={:?}, i={:?})", r, self.elements.to_element(i));
+
+            if let Some(causes) = &mut self.causes {
+                let cause = Rc::new(make_cause(causes));
+                causes.insert((r, i), cause);
+            }
+
             true
         } else {
+            if let Some(causes) = &mut self.causes {
+                let cause = make_cause(causes);
+                let old_cause = causes.get_mut(&(r, i)).unwrap();
+                if cause < **old_cause {
+                    *old_cause = Rc::new(cause);
+                    return true;
+                }
+            }
+
             false
         }
     }
 
     /// Adds all the universal regions outlived by `from_region` to
     /// `to_region`.
+    pub(super) fn add_due_to_outlives<T: ToElementIndex>(
+        &mut self,
+        from_region: RegionVid,
+        to_region: RegionVid,
+        elem: T,
+        constraint_location: Location,
+        constraint_span: Span,
+    ) -> bool {
+        let elem = self.elements.index(elem);
+        self.add_internal(to_region, elem, |causes| {
+            causes[&(from_region, elem)].outlives(constraint_location, constraint_span)
+        })
+    }
+
+    /// Adds all the universal regions outlived by `from_region` to
+    /// `to_region`.
     pub(super) fn add_universal_regions_outlived_by(
         &mut self,
         from_region: RegionVid,
         to_region: RegionVid,
+        constraint_location: Location,
+        constraint_span: Span,
     ) -> bool {
-        // FIXME. We could optimize this by improving
-        // `BitMatrix::merge` so it does not always merge an entire
-        // row.
+        // We could optimize this by improving `BitMatrix::merge` so
+        // it does not always merge an entire row. That would
+        // complicate causal tracking though.
         debug!(
             "add_universal_regions_outlived_by(from_region={:?}, to_region={:?})",
             from_region,
@@ -232,7 +297,13 @@ impl RegionValues {
         let mut changed = false;
         for elem in self.elements.all_universal_region_indices() {
             if self.contains(from_region, elem) {
-                changed |= self.add(to_region, elem);
+                changed |= self.add_due_to_outlives(
+                    from_region,
+                    to_region,
+                    elem,
+                    constraint_location,
+                    constraint_span,
+                );
             }
         }
         changed
diff --git a/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs b/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs
index e42302761bf..32728145b29 100644
--- a/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs
+++ b/src/librustc_mir/borrow_check/nll/subtype_constraint_generation.rs
@@ -51,10 +51,10 @@ impl<'cx, 'tcx> SubtypeConstraintGenerator<'cx, 'tcx> {
             outlives_sets.len()
         );
 
-        for (region, location) in liveness_set {
+        for (region, location, cause) in liveness_set {
             debug!("generate: {:#?} is live at {:#?}", region, location);
             let region_vid = self.to_region_vid(region);
-            self.regioncx.add_live_point(region_vid, *location);
+            self.regioncx.add_live_point(region_vid, *location, &cause);
         }
 
         for OutlivesSet { locations, data } in outlives_sets {
diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
index e41bf7cda8e..50b38f9b46b 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 use dataflow::{FlowAtLocation, FlowsAtLocation};
+use borrow_check::nll::region_infer::Cause;
 use dataflow::MaybeInitializedLvals;
 use dataflow::move_paths::{HasMoveData, MoveData};
 use rustc::mir::{BasicBlock, Location, Mir};
@@ -79,7 +80,8 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
             .simulate_block(self.mir, bb, |location, live_locals| {
                 for live_local in live_locals.iter() {
                     let live_local_ty = self.mir.local_decls[live_local].ty;
-                    self.push_type_live_constraint(live_local_ty, location);
+                    let cause = Cause::LiveVar(live_local, location);
+                    self.push_type_live_constraint(live_local_ty, location, cause);
                 }
             });
 
@@ -121,7 +123,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
                     );
 
                     let live_local_ty = self.mir.local_decls[live_local].ty;
-                    self.add_drop_live_constraint(live_local_ty, location);
+                    self.add_drop_live_constraint(live_local, live_local_ty, location);
                 }
             }
 
@@ -146,7 +148,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
     /// `location` -- i.e., it may be used later. This means that all
     /// regions appearing in the type `live_ty` must be live at
     /// `location`.
-    fn push_type_live_constraint<T>(&mut self, value: T, location: Location)
+    fn push_type_live_constraint<T>(&mut self, value: T, location: Location, cause: Cause)
     where
         T: TypeFoldable<'tcx>,
     {
@@ -160,7 +162,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
             self.cx
                 .constraints
                 .liveness_set
-                .push((live_region, location));
+                .push((live_region, location, cause.clone()));
         });
     }
 
@@ -169,9 +171,15 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
     /// the regions in its type must be live at `location`. The
     /// precise set will depend on the dropck constraints, and in
     /// particular this takes `#[may_dangle]` into account.
-    fn add_drop_live_constraint(&mut self, dropped_ty: Ty<'tcx>, location: Location) {
+    fn add_drop_live_constraint(
+        &mut self,
+        dropped_local: Local,
+        dropped_ty: Ty<'tcx>,
+        location: Location,
+    ) {
         debug!(
-            "add_drop_live_constraint(dropped_ty={:?}, location={:?})",
+            "add_drop_live_constraint(dropped_local={:?}, dropped_ty={:?}, location={:?})",
+            dropped_local,
             dropped_ty,
             location
         );
@@ -196,7 +204,8 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
             // All things in the `outlives` array may be touched by
             // the destructor and must be live at this point.
             for outlive in outlives {
-                self.push_type_live_constraint(outlive, location);
+                let cause = Cause::DropVar(dropped_local, location);
+                self.push_type_live_constraint(outlive, location, cause);
             }
 
             // However, there may also be some types that
@@ -207,7 +216,8 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo
                 let ty = self.cx.normalize(&ty, location);
                 match ty.sty {
                     ty::TyParam(..) | ty::TyProjection(..) | ty::TyAnon(..) => {
-                        self.push_type_live_constraint(ty, location);
+                        let cause = Cause::DropVar(dropped_local, location);
+                        self.push_type_live_constraint(ty, location, cause);
                     }
 
                     _ => if known.insert(ty) {
diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
index 6cdd77048c9..32a016e4a0a 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -11,6 +11,7 @@
 //! This pass type-checks the MIR to ensure it is not broken.
 #![allow(unreachable_code)]
 
+use borrow_check::nll::region_infer::Cause;
 use borrow_check::nll::region_infer::ClosureRegionRequirementsExt;
 use dataflow::FlowAtLocation;
 use dataflow::MaybeInitializedLvals;
@@ -578,7 +579,7 @@ struct TypeChecker<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
 /// A collection of region constraints that must be satisfied for the
 /// program to be considered well-typed.
 #[derive(Default)]
-pub struct MirTypeckRegionConstraints<'tcx> {
+pub(crate) struct MirTypeckRegionConstraints<'tcx> {
     /// In general, the type-checker is not responsible for enforcing
     /// liveness constraints; this job falls to the region inferencer,
     /// which performs a liveness analysis. However, in some limited
@@ -586,7 +587,7 @@ pub struct MirTypeckRegionConstraints<'tcx> {
     /// not otherwise appear in the MIR -- in particular, the
     /// late-bound regions that it instantiates at call-sites -- and
     /// hence it must report on their liveness constraints.
-    pub liveness_set: Vec<(ty::Region<'tcx>, Location)>,
+    pub liveness_set: Vec<(ty::Region<'tcx>, Location, Cause)>,
 
     /// During the course of type-checking, we will accumulate region
     /// constraints due to performing subtyping operations or solving
@@ -889,7 +890,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
                 for &late_bound_region in map.values() {
                     self.constraints
                         .liveness_set
-                        .push((late_bound_region, term_location));
+                        .push((late_bound_region, term_location, Cause::LiveOther(term_location)));
                 }
 
                 if self.is_box_free(func) {