Create VarValue::Empty

6 files changed, 191 insertions, 22 deletions

diff --git a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs
index 0392367288c..3e6a48195f8 100644
--- a/compiler/rustc_borrowck/src/region_infer/opaque_types.rs
+++ b/compiler/rustc_borrowck/src/region_infer/opaque_types.rs
@@ -109,7 +109,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
                         .iter()
                         .find(|ur_vid| self.eval_equal(vid, **ur_vid))
                         .and_then(|ur_vid| self.definitions[*ur_vid].external_name)
-                        .unwrap_or(infcx.tcx.lifetimes.re_root_empty),
+                        .unwrap_or(infcx.tcx.lifetimes.re_erased),
                     _ => region,
                 });
 
diff --git a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs
index 13b7e8eb964..41695d6807b 100644
--- a/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs
+++ b/compiler/rustc_infer/src/infer/lexical_region_resolve/mod.rs
@@ -51,6 +51,13 @@ pub struct LexicalRegionResolutions<'tcx> {
 
 #[derive(Copy, Clone, Debug)]
 pub(crate) enum VarValue<'tcx> {
+    /// Empty lifetime is for data that is never accessed.  We tag the
+    /// empty lifetime with a universe -- the idea is that we don't
+    /// want `exists<'a> { forall<'b> { 'b: 'a } }` to be satisfiable.
+    /// Therefore, the `'empty` in a universe `U` is less than all
+    /// regions visible from `U`, but not less than regions not visible
+    /// from `U`.
+    Empty(ty::UniverseIndex),
     Value(Region<'tcx>),
     ErrorValue,
 }
@@ -117,7 +124,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
         &mut self,
         errors: &mut Vec<RegionResolutionError<'tcx>>,
     ) -> LexicalRegionResolutions<'tcx> {
-        let mut var_data = self.construct_var_data(self.tcx());
+        let mut var_data = self.construct_var_data();
 
         if cfg!(debug_assertions) {
             self.dump_constraints();
@@ -137,13 +144,12 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
 
     /// Initially, the value for all variables is set to `'empty`, the
     /// empty region. The `expansion` phase will grow this larger.
-    fn construct_var_data(&self, tcx: TyCtxt<'tcx>) -> LexicalRegionResolutions<'tcx> {
+    fn construct_var_data(&self) -> LexicalRegionResolutions<'tcx> {
         LexicalRegionResolutions {
             values: IndexVec::from_fn_n(
                 |vid| {
                     let vid_universe = self.var_infos[vid].universe;
-                    let re_empty = tcx.mk_region(ty::ReEmpty(vid_universe));
-                    VarValue::Value(re_empty)
+                    VarValue::Empty(vid_universe)
                 },
                 self.num_vars(),
             ),
@@ -190,19 +196,132 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
     }
 
     fn expansion(&self, var_values: &mut LexicalRegionResolutions<'tcx>) {
+        // In the first pass, we expand region vids according to constraints we
+        // have previously found. In the second pass, we loop through the region
+        // vids we expanded and expand *across* region vids (effectively
+        // "expanding" new `RegSubVar` constraints).
+
+        // Tracks the `VarSubVar` constraints generated for each region vid. We
+        // later use this to expand across vids.
         let mut constraints = IndexVec::from_elem_n(Vec::new(), var_values.values.len());
+        // Tracks the changed region vids.
         let mut changes = Vec::new();
         for constraint in self.data.constraints.keys() {
-            let (a_vid, a_region, b_vid, b_data) = match *constraint {
+            match *constraint {
                 Constraint::RegSubVar(a_region, b_vid) => {
                     let b_data = var_values.value_mut(b_vid);
-                    (None, a_region, b_vid, b_data)
+
+                    if self.expand_node(a_region, b_vid, b_data) {
+                        changes.push(b_vid);
+                    }
                 }
                 Constraint::VarSubVar(a_vid, b_vid) => match *var_values.value(a_vid) {
                     VarValue::ErrorValue => continue,
+                    VarValue::Empty(a_universe) => {
+                        let b_data = var_values.value_mut(b_vid);
+
+                        let changed = (|| match *b_data {
+                            VarValue::Empty(b_universe) => {
+                                // Empty regions are ordered according to the universe
+                                // they are associated with.
+                                let ui = a_universe.min(b_universe);
+
+                                debug!(
+                                    "Expanding value of {:?} \
+                                    from empty lifetime with universe {:?} \
+                                    to empty lifetime with universe {:?}",
+                                    b_vid, b_universe, ui
+                                );
+
+                                *b_data = VarValue::Empty(ui);
+                                true
+                            }
+                            VarValue::Value(cur_region) => {
+                                let lub = match *cur_region {
+                                    ReLateBound(..) | ReErased => {
+                                        bug!("cannot relate region: {:?}", cur_region);
+                                    }
+
+                                    ReVar(v_id) => {
+                                        span_bug!(
+                                            self.var_infos[v_id].origin.span(),
+                                            "lub_concrete_regions invoked with non-concrete regions: {:?}",
+                                            cur_region,
+                                        );
+                                    }
+
+                                    ReStatic => {
+                                        // nothing lives longer than `'static`
+                                        self.tcx().lifetimes.re_static
+                                    }
+
+                                    ReEarlyBound(_) | ReFree(_) => {
+                                        // All empty regions are less than early-bound, free,
+                                        // and scope regions.
+                                        cur_region
+                                    }
+
+                                    ReEmpty(b_ui) => {
+                                        // Empty regions are ordered according to the universe
+                                        // they are associated with.
+                                        let ui = a_universe.min(b_ui);
+                                        self.tcx().mk_region(ReEmpty(ui))
+                                    }
+
+                                    RePlaceholder(placeholder) => {
+                                        // If the empty and placeholder regions are in the same universe,
+                                        // then the LUB is the Placeholder region (which is the cur_region).
+                                        // If they are not in the same universe, the LUB is the Static lifetime.
+                                        if a_universe == placeholder.universe {
+                                            cur_region
+                                        } else {
+                                            self.tcx().lifetimes.re_static
+                                        }
+                                    }
+                                };
+
+                                if lub == cur_region {
+                                    return false;
+                                }
+
+                                debug!(
+                                    "Expanding value of {:?} from {:?} to {:?}",
+                                    b_vid, cur_region, lub
+                                );
+
+                                *b_data = VarValue::Value(lub);
+                                true
+                            }
+
+                            VarValue::ErrorValue => false,
+                        })();
+
+                        if changed {
+                            changes.push(b_vid);
+                        }
+                        match b_data {
+                            VarValue::Value(Region(Interned(ReStatic, _)))
+                            | VarValue::ErrorValue => (),
+                            _ => {
+                                constraints[a_vid].push((a_vid, b_vid));
+                                constraints[b_vid].push((a_vid, b_vid));
+                            }
+                        }
+                    }
                     VarValue::Value(a_region) => {
                         let b_data = var_values.value_mut(b_vid);
-                        (Some(a_vid), a_region, b_vid, b_data)
+
+                        if self.expand_node(a_region, b_vid, b_data) {
+                            changes.push(b_vid);
+                        }
+                        match b_data {
+                            VarValue::Value(Region(Interned(ReStatic, _)))
+                            | VarValue::ErrorValue => (),
+                            _ => {
+                                constraints[a_vid].push((a_vid, b_vid));
+                                constraints[b_vid].push((a_vid, b_vid));
+                            }
+                        }
                     }
                 },
                 Constraint::RegSubReg(..) | Constraint::VarSubReg(..) => {
@@ -210,18 +329,6 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
                     // is done, in `collect_errors`.
                     continue;
                 }
-            };
-            if self.expand_node(a_region, b_vid, b_data) {
-                changes.push(b_vid);
-            }
-            if let Some(a_vid) = a_vid {
-                match b_data {
-                    VarValue::Value(Region(Interned(ReStatic, _))) | VarValue::ErrorValue => (),
-                    _ => {
-                        constraints[a_vid].push((a_vid, b_vid));
-                        constraints[b_vid].push((a_vid, b_vid));
-                    }
-                }
             }
         }
 
@@ -242,6 +349,10 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
         }
     }
 
+    /// Expands the value of the region represented with `b_vid` with current
+    /// value `b_data` to the lub of `b_data` and `a_region`. The corresponds
+    /// with the constraint `'?b: 'a` (`'a <: '?b`), where `'a` is some known
+    /// region and `'?b` is some region variable.
     fn expand_node(
         &self,
         a_region: Region<'tcx>,
@@ -263,6 +374,55 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
         }
 
         match *b_data {
+            VarValue::Empty(empty_ui) => {
+                let lub = match *a_region {
+                    ReLateBound(..) | ReErased => {
+                        bug!("cannot relate region: {:?}", a_region);
+                    }
+
+                    ReVar(v_id) => {
+                        span_bug!(
+                            self.var_infos[v_id].origin.span(),
+                            "expand_node invoked with non-concrete regions: {:?}",
+                            a_region,
+                        );
+                    }
+
+                    ReStatic => {
+                        // nothing lives longer than `'static`
+                        self.tcx().lifetimes.re_static
+                    }
+
+                    ReEarlyBound(_) | ReFree(_) => {
+                        // All empty regions are less than early-bound, free,
+                        // and scope regions.
+                        a_region
+                    }
+
+                    ReEmpty(a_ui) => {
+                        // Empty regions are ordered according to the universe
+                        // they are associated with.
+                        let ui = a_ui.min(empty_ui);
+                        self.tcx().mk_region(ReEmpty(ui))
+                    }
+
+                    RePlaceholder(placeholder) => {
+                        // If this empty region is from a universe that can
+                        // name the placeholder, then the placeholder is
+                        // larger; otherwise, the only ancestor is `'static`.
+                        if empty_ui.can_name(placeholder.universe) {
+                            self.tcx().mk_region(RePlaceholder(placeholder))
+                        } else {
+                            self.tcx().lifetimes.re_static
+                        }
+                    }
+                };
+
+                debug!("Expanding value of {:?} from empty lifetime to {:?}", b_vid, lub);
+
+                *b_data = VarValue::Value(lub);
+                true
+            }
             VarValue::Value(cur_region) => {
                 // This is a specialized version of the `lub_concrete_regions`
                 // check below for a common case, here purely as an
@@ -508,7 +668,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
 
         for (node_vid, value) in var_data.values.iter_enumerated() {
             match *value {
-                VarValue::Value(_) => { /* Inference successful */ }
+                VarValue::Empty(_) | VarValue::Value(_) => { /* Inference successful */ }
                 VarValue::ErrorValue => {
                     // Inference impossible: this value contains
                     // inconsistent constraints.
@@ -876,6 +1036,7 @@ impl<'tcx> LexicalRegionResolutions<'tcx> {
     ) -> ty::Region<'tcx> {
         let result = match *r {
             ty::ReVar(rid) => match self.values[rid] {
+                VarValue::Empty(vid_universe) => tcx.mk_region(ty::ReEmpty(vid_universe)),
                 VarValue::Value(r) => r,
                 VarValue::ErrorValue => tcx.lifetimes.re_static,
             },
diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs
index 9a571837e9f..9d3a1a4a031 100644
--- a/compiler/rustc_trait_selection/src/traits/wf.rs
+++ b/compiler/rustc_trait_selection/src/traits/wf.rs
@@ -101,6 +101,7 @@ pub fn trait_obligations<'a, 'tcx>(
     wf.normalize(infcx)
 }
 
+#[instrument(skip(infcx), ret)]
 pub fn predicate_obligations<'a, 'tcx>(
     infcx: &InferCtxt<'a, 'tcx>,
     param_env: ty::ParamEnv<'tcx>,
@@ -440,6 +441,7 @@ impl<'tcx> WfPredicates<'tcx> {
         let param_env = self.param_env;
         let depth = self.recursion_depth;
         while let Some(arg) = walker.next() {
+            debug!(?arg, ?self.out);
             let ty = match arg.unpack() {
                 GenericArgKind::Type(ty) => ty,
 
@@ -689,6 +691,8 @@ impl<'tcx> WfPredicates<'tcx> {
                     ));
                 }
             }
+
+            debug!(?self.out);
         }
     }
 
diff --git a/compiler/rustc_typeck/src/check/dropck.rs b/compiler/rustc_typeck/src/check/dropck.rs
index 321064ec0fc..ab143c05982 100644
--- a/compiler/rustc_typeck/src/check/dropck.rs
+++ b/compiler/rustc_typeck/src/check/dropck.rs
@@ -144,6 +144,8 @@ fn ensure_drop_predicates_are_implied_by_item_defn<'tcx>(
     let assumptions_in_impl_context = generic_assumptions.instantiate(tcx, &self_to_impl_substs);
     let assumptions_in_impl_context = assumptions_in_impl_context.predicates;
 
+    debug!(?assumptions_in_impl_context, ?dtor_predicates.predicates);
+
     let self_param_env = tcx.param_env(self_type_did);
 
     // An earlier version of this code attempted to do this checking
diff --git a/compiler/rustc_typeck/src/check/wfcheck.rs b/compiler/rustc_typeck/src/check/wfcheck.rs
index 5c6c8aca173..b0ce0de1469 100644
--- a/compiler/rustc_typeck/src/check/wfcheck.rs
+++ b/compiler/rustc_typeck/src/check/wfcheck.rs
@@ -1816,6 +1816,7 @@ fn report_bivariance(
 impl<'tcx> WfCheckingCtxt<'_, 'tcx> {
     /// Feature gates RFC 2056 -- trivial bounds, checking for global bounds that
     /// aren't true.
+    #[instrument(level = "debug", skip(self))]
     fn check_false_global_bounds(&mut self) {
         let tcx = self.ocx.infcx.tcx;
         let mut span = self.span;
diff --git a/compiler/rustc_typeck/src/collect.rs b/compiler/rustc_typeck/src/collect.rs
index e70f728d7dc..c2a34b91ad6 100644
--- a/compiler/rustc_typeck/src/collect.rs
+++ b/compiler/rustc_typeck/src/collect.rs
@@ -1808,6 +1808,7 @@ pub fn get_infer_ret_ty<'hir>(output: &'hir hir::FnRetTy<'hir>) -> Option<&'hir
     None
 }
 
+#[instrument(level = "debug", skip(tcx))]
 fn fn_sig(tcx: TyCtxt<'_>, def_id: DefId) -> ty::PolyFnSig<'_> {
     use rustc_hir::Node::*;
     use rustc_hir::*;
@@ -2038,8 +2039,8 @@ fn early_bound_lifetimes_from_generics<'a, 'tcx: 'a>(
 /// Returns a list of type predicates for the definition with ID `def_id`, including inferred
 /// lifetime constraints. This includes all predicates returned by `explicit_predicates_of`, plus
 /// inferred constraints concerning which regions outlive other regions.
+#[instrument(level = "debug", skip(tcx))]
 fn predicates_defined_on(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericPredicates<'_> {
-    debug!("predicates_defined_on({:?})", def_id);
     let mut result = tcx.explicit_predicates_of(def_id);
     debug!("predicates_defined_on: explicit_predicates_of({:?}) = {:?}", def_id, result,);
     let inferred_outlives = tcx.inferred_outlives_of(def_id);