fix bug in NLL error reporting

Account for incompatible universes and higher-ranked subtyping.

4 files changed, 111 insertions, 8 deletions

diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 4e214394399..9f1af50a6d5 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1522,10 +1522,17 @@ impl UniverseIndex {
 
     /// True if `self` can name a name from `other` -- in other words,
     /// if the set of names in `self` is a superset of those in
-    /// `other`.
+    /// `other` (`self >= other`).
     pub fn can_name(self, other: UniverseIndex) -> bool {
         self.private >= other.private
     }
+
+    /// True if `self` cannot name some names from `other` -- in other
+    /// words, if the set of names in `self` is a strict subset of
+    /// those in `other` (`self < other`).
+    pub fn cannot_name(self, other: UniverseIndex) -> bool {
+        self.private < other.private
+    }
 }
 
 /// The "placeholder index" fully defines a placeholder region.
diff --git a/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs
index bf150dbe460..3358e5851f9 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/error_reporting/mod.rs
@@ -16,6 +16,7 @@ use borrow_check::nll::ConstraintDescription;
 use rustc::hir::def_id::DefId;
 use rustc::infer::error_reporting::nice_region_error::NiceRegionError;
 use rustc::infer::InferCtxt;
+use rustc::infer::NLLRegionVariableOrigin;
 use rustc::mir::{ConstraintCategory, Location, Mir};
 use rustc::ty::{self, RegionVid};
 use rustc_data_structures::indexed_vec::IndexVec;
@@ -177,6 +178,13 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         deque.push_back(from_region);
 
         while let Some(r) = deque.pop_front() {
+            debug!(
+                "find_constraint_paths_between_regions: from_region={:?} r={:?} value={}",
+                from_region,
+                r,
+                self.region_value_str(r),
+            );
+
             // Check if we reached the region we were looking for. If so,
             // we can reconstruct the path that led to it and return it.
             if target_test(r) {
@@ -238,7 +246,9 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     ) {
         debug!("report_error(fr={:?}, outlived_fr={:?})", fr, outlived_fr);
 
-        let (category, _, span) = self.best_blame_constraint(mir, fr, |r| r == outlived_fr);
+        let (category, _, span) = self.best_blame_constraint(mir, fr, |r| {
+            self.provides_universal_region(r, fr, outlived_fr)
+        });
 
         // Check if we can use one of the "nice region errors".
         if let (Some(f), Some(o)) = (self.to_error_region(fr), self.to_error_region(outlived_fr)) {
@@ -296,6 +306,33 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         };
     }
 
+    /// We have a constraint `fr1: fr2` that is not satisfied, where
+    /// `fr2` represents some universal region. Here, `r` is some
+    /// region where we know that `fr1: r` and this function has the
+    /// job of determining whether `r` is "to blame" for the fact that
+    /// `fr1: fr2` is required.
+    ///
+    /// This is true under two conditions:
+    ///
+    /// - `r == fr2`
+    /// - `fr2` is `'static` and `r` is some placeholder in a universe
+    ///   that cannot be named by `fr1`; in that case, we will require
+    ///   that `fr1: 'static` because it is the only way to `fr1: r` to
+    ///   be satisfied. (See `add_incompatible_universe`.)
+    fn provides_universal_region(&self, r: RegionVid, fr1: RegionVid, fr2: RegionVid) -> bool {
+        debug!(
+            "provides_universal_region(r={:?}, fr1={:?}, fr2={:?})",
+            r, fr1, fr2
+        );
+        let result = {
+            r == fr2 || {
+                fr2 == self.universal_regions.fr_static && self.cannot_name_placeholder(fr1, r)
+            }
+        };
+        debug!("provides_universal_region: result = {:?}", result);
+        result
+    }
+
     /// Report a specialized error when `FnMut` closures return a reference to a captured variable.
     /// This function expects `fr` to be local and `outlived_fr` to not be local.
     ///
@@ -636,11 +673,37 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     // `elem`.
     crate fn find_sub_region_live_at(&self, fr1: RegionVid, elem: Location) -> RegionVid {
         debug!("find_sub_region_live_at(fr1={:?}, elem={:?})", fr1, elem);
-        // Find all paths
-        let (_path, r) = self.find_constraint_paths_between_regions(fr1, |r| {
+        self.find_constraint_paths_between_regions(fr1, |r| {
+            // First look for some `r` such that `fr1: r` and `r` is live at `elem`
+            debug!(
+                "find_sub_region_live_at: liveness_constraints for {:?} are {:?}",
+                r,
+                self.liveness_constraints.region_value_str(r),
+            );
             self.liveness_constraints.contains(r, elem)
-        }).unwrap();
-        r
+        }).or_else(|| {
+                // If we fail to find that, we may find some `r` such that
+                // `fr1: r` and `r` is a placeholder from some universe
+                // `fr1` cannot name. This would force `fr1` to be
+                // `'static`.
+                self.find_constraint_paths_between_regions(fr1, |r| {
+                    self.cannot_name_placeholder(fr1, r)
+                })
+            })
+            .or_else(|| {
+                // If we fail to find THAT, it may be that `fr1` is a
+                // placeholder that cannot "fit" into its SCC. In that
+                // case, there should be some `r` where `fr1: r`, both
+                // `fr1` and `r` are in the same SCC, and `fr1` is a
+                // placeholder that `r` cannot name. We can blame that
+                // edge.
+                self.find_constraint_paths_between_regions(fr1, |r| {
+                    self.constraint_sccs.scc(fr1) == self.constraint_sccs.scc(r)
+                        && self.cannot_name_placeholder(r, fr1)
+                })
+            })
+            .map(|(_path, r)| r)
+            .unwrap()
     }
 
     // Finds a good span to blame for the fact that `fr1` outlives `fr2`.
@@ -650,7 +713,8 @@ impl<'tcx> RegionInferenceContext<'tcx> {
         fr1: RegionVid,
         fr2: RegionVid,
     ) -> (ConstraintCategory, Span) {
-        let (category, _, span) = self.best_blame_constraint(mir, fr1, |r| r == fr2);
+        let (category, _, span) =
+            self.best_blame_constraint(mir, fr1, |r| self.provides_universal_region(r, fr1, fr2));
         (category, span)
     }
 
@@ -684,4 +748,24 @@ impl<'tcx> RegionInferenceContext<'tcx> {
 
         false
     }
+
+    /// If `r2` represents a placeholder region, then this returns
+    /// true if `r1` cannot name that placeholder in its
+    /// value. Otherwise, returns false.
+    fn cannot_name_placeholder(&self, r1: RegionVid, r2: RegionVid) -> bool {
+        debug!("cannot_name_value_of(r1={:?}, r2={:?})", r1, r2);
+
+        match self.definitions[r2].origin {
+            NLLRegionVariableOrigin::Placeholder(placeholder) => {
+                let universe1 = self.definitions[r1].universe;
+                debug!(
+                    "cannot_name_value_of: universe1={:?} placeholder={:?}",
+                    universe1, placeholder
+                );
+                universe1.cannot_name(placeholder.universe)
+            }
+
+            NLLRegionVariableOrigin::FreeRegion | NLLRegionVariableOrigin::Existential => false,
+        }
+    }
 }
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 0e44c8b36a9..376f4459242 100644
--- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs
@@ -345,6 +345,13 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                     if scc_universe.can_name(placeholder.universe) {
                         self.scc_values.add_element(scc, placeholder);
                     } else {
+                        debug!(
+                            "init_free_and_bound_regions: placeholder {:?} is \
+                             not compatible with universe {:?} of its SCC {:?}",
+                            placeholder,
+                            scc_universe,
+                            scc,
+                        );
                         self.add_incompatible_universe(scc);
                     }
                 }
@@ -471,6 +478,9 @@ impl<'tcx> RegionInferenceContext<'tcx> {
             let mut constraints: Vec<_> = self.constraints.iter().collect();
             constraints.sort();
             constraints
+                .into_iter()
+                .map(|c| (c, self.constraint_sccs.scc(c.sup), self.constraint_sccs.scc(c.sub)))
+                .collect::<Vec<_>>()
         });
 
         // To propagate constraints, we walk the DAG induced by the
@@ -560,6 +570,8 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     /// `'a` with `'b` and not `'static`. But it will have to do for
     /// now.
     fn add_incompatible_universe(&mut self, scc: ConstraintSccIndex) {
+        debug!("add_incompatible_universe(scc={:?})", scc);
+
         let fr_static = self.universal_regions.fr_static;
         self.scc_values.add_all_points(scc);
         self.scc_values.add_element(scc, fr_static);
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 eae41c81ff2..8ef810bba9c 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs
@@ -782,7 +782,7 @@ impl MirTypeckRegionConstraints<'tcx> {
             Some(&v) => v,
             None => {
                 let origin = NLLRegionVariableOrigin::Placeholder(placeholder);
-                let region = infcx.next_nll_region_var(origin);
+                let region = infcx.next_nll_region_var_in_universe(origin, placeholder.universe);
                 self.placeholder_index_to_region.push(region);
                 region
             }