index ReEmpty by universe

We now make `'empty` indexed by a universe index, resulting
in a region lattice like this:

```
static ----------+-----...------+       (greatest)
|                |              |
early-bound and  |              |
free regions     |              |
|                |              |
scope regions    |              |
|                |              |
empty(root)   placeholder(U1)   |
|            /                  |
|           /         placeholder(Un)
empty(U1) --         /
|                   /
...                /
|                 /
empty(Un) --------                      (smallest)
```

Therefore, `exists<A> { forall<B> { B: A } }` is now unprovable,
because A must be at least Empty(U1) and B is placeholder(U2), and hence
the two regions are unrelated.

22 files changed, 269 insertions, 58 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 6af0cee948d..844250f51a0 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -63,9 +63,12 @@ impl<'a> HashStable<StableHashingContext<'a>> for ty::RegionKind {
     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
         mem::discriminant(self).hash_stable(hcx, hasher);
         match *self {
-            ty::ReErased | ty::ReStatic | ty::ReEmpty => {
+            ty::ReErased | ty::ReStatic => {
                 // No variant fields to hash for these ...
             }
+            ty::ReEmpty(universe) => {
+                universe.hash_stable(hcx, hasher);
+            }
             ty::ReLateBound(db, ty::BrAnon(i)) => {
                 db.hash_stable(hcx, hasher);
                 i.hash_stable(hcx, hasher);
diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index b720168f356..48a6c6d7413 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -167,11 +167,17 @@ impl CanonicalizeRegionMode for CanonicalizeQueryResponse {
         r: ty::Region<'tcx>,
     ) -> ty::Region<'tcx> {
         match r {
-            ty::ReFree(_) | ty::ReEmpty | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r,
+            ty::ReFree(_)
+            | ty::ReErased
+            | ty::ReStatic
+            | ty::ReEmpty(ty::UniverseIndex::ROOT)
+            | ty::ReEarlyBound(..) => r,
+
             ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
                 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(*placeholder) },
                 r,
             ),
+
             ty::ReVar(vid) => {
                 let universe = canonicalizer.region_var_universe(*vid);
                 canonicalizer.canonical_var_for_region(
@@ -179,6 +185,11 @@ impl CanonicalizeRegionMode for CanonicalizeQueryResponse {
                     r,
                 )
             }
+
+            ty::ReEmpty(ui) => {
+                bug!("canonicalizing 'empty in universe {:?}", ui) // FIXME
+            }
+
             _ => {
                 // Other than `'static` or `'empty`, the query
                 // response should be executing in a fully
@@ -213,7 +224,7 @@ impl CanonicalizeRegionMode for CanonicalizeUserTypeAnnotation {
         r: ty::Region<'tcx>,
     ) -> ty::Region<'tcx> {
         match r {
-            ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReEmpty | ty::ReStatic => r,
+            ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r,
             ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
             _ => {
                 // We only expect region names that the user can type.
@@ -320,8 +331,8 @@ impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
             | ty::ReEarlyBound(..)
             | ty::ReFree(_)
             | ty::ReScope(_)
+            | ty::ReEmpty(_)
             | ty::RePlaceholder(..)
-            | ty::ReEmpty
             | ty::ReErased => self.canonicalize_region_mode.canonicalize_free_region(self, r),
 
             ty::ReClosureBound(..) => {
diff --git a/src/librustc/infer/combine.rs b/src/librustc/infer/combine.rs
index 5d765a2a3d3..2518805a1ec 100644
--- a/src/librustc/infer/combine.rs
+++ b/src/librustc/infer/combine.rs
@@ -577,7 +577,7 @@ impl TypeRelation<'tcx> for Generalizer<'_, 'tcx> {
 
             ty::RePlaceholder(..)
             | ty::ReVar(..)
-            | ty::ReEmpty
+            | ty::ReEmpty(_)
             | ty::ReStatic
             | ty::ReScope(..)
             | ty::ReEarlyBound(..)
diff --git a/src/librustc/infer/error_reporting/mod.rs b/src/librustc/infer/error_reporting/mod.rs
index 58566bdcc35..57a52a991ed 100644
--- a/src/librustc/infer/error_reporting/mod.rs
+++ b/src/librustc/infer/error_reporting/mod.rs
@@ -138,7 +138,10 @@ pub(super) fn note_and_explain_region(
             msg_span_from_free_region(tcx, region)
         }
 
-        ty::ReEmpty => ("the empty lifetime".to_owned(), None),
+        ty::ReEmpty(ty::UniverseIndex::ROOT) => ("the empty lifetime".to_owned(), None),
+
+        // uh oh, hope no user ever sees THIS
+        ty::ReEmpty(ui) => (format!("the empty lifetime in universe {:?}", ui), None),
 
         ty::RePlaceholder(_) => (format!("any other region"), None),
 
@@ -181,7 +184,8 @@ fn msg_span_from_free_region(
             msg_span_from_early_bound_and_free_regions(tcx, region)
         }
         ty::ReStatic => ("the static lifetime".to_owned(), None),
-        ty::ReEmpty => ("an empty lifetime".to_owned(), None),
+        ty::ReEmpty(ty::UniverseIndex::ROOT) => ("an empty lifetime".to_owned(), None),
+        ty::ReEmpty(ui) => (format!("an empty lifetime in universe {:?}", ui), None),
         _ => bug!("{:?}", region),
     }
 }
@@ -375,6 +379,31 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                         }
                     }
 
+                    RegionResolutionError::UpperBoundUniverseConflict(
+                        _,
+                        _,
+                        var_universe,
+                        sup_origin,
+                        sup_r,
+                    ) => {
+                        assert!(sup_r.is_placeholder());
+
+                        // Make a dummy value for the "sub region" --
+                        // this is the initial value of the
+                        // placeholder. In practice, we expect more
+                        // tailored errors that don't really use this
+                        // value.
+                        let sub_r = self.tcx.mk_region(ty::ReEmpty(var_universe));
+
+                        self.report_placeholder_failure(
+                            region_scope_tree,
+                            sup_origin,
+                            sub_r,
+                            sup_r,
+                        )
+                        .emit();
+                    }
+
                     RegionResolutionError::MemberConstraintFailure {
                         opaque_type_def_id,
                         hidden_ty,
@@ -429,6 +458,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             RegionResolutionError::GenericBoundFailure(..) => true,
             RegionResolutionError::ConcreteFailure(..)
             | RegionResolutionError::SubSupConflict(..)
+            | RegionResolutionError::UpperBoundUniverseConflict(..)
             | RegionResolutionError::MemberConstraintFailure { .. } => false,
         };
 
@@ -443,6 +473,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             RegionResolutionError::ConcreteFailure(ref sro, _, _) => sro.span(),
             RegionResolutionError::GenericBoundFailure(ref sro, _, _) => sro.span(),
             RegionResolutionError::SubSupConflict(_, ref rvo, _, _, _, _) => rvo.span(),
+            RegionResolutionError::UpperBoundUniverseConflict(_, ref rvo, _, _, _) => rvo.span(),
             RegionResolutionError::MemberConstraintFailure { span, .. } => span,
         });
         errors
diff --git a/src/librustc/infer/error_reporting/nice_region_error/placeholder_error.rs b/src/librustc/infer/error_reporting/nice_region_error/placeholder_error.rs
index 7b31fe7cd7e..0b0bd61ce77 100644
--- a/src/librustc/infer/error_reporting/nice_region_error/placeholder_error.rs
+++ b/src/librustc/infer/error_reporting/nice_region_error/placeholder_error.rs
@@ -107,6 +107,25 @@ impl NiceRegionError<'me, 'tcx> {
                 found.substs,
             )),
 
+            Some(RegionResolutionError::UpperBoundUniverseConflict(
+                vid,
+                _,
+                _,
+                SubregionOrigin::Subtype(box TypeTrace {
+                    cause,
+                    values: ValuePairs::TraitRefs(ExpectedFound { expected, found }),
+                }),
+                sup_placeholder @ ty::RePlaceholder(_),
+            )) if expected.def_id == found.def_id => Some(self.try_report_placeholders_trait(
+                Some(self.tcx().mk_region(ty::ReVar(*vid))),
+                cause,
+                None,
+                Some(*sup_placeholder),
+                expected.def_id,
+                expected.substs,
+                found.substs,
+            )),
+
             Some(RegionResolutionError::ConcreteFailure(
                 SubregionOrigin::Subtype(box TypeTrace {
                     cause,
diff --git a/src/librustc/infer/freshen.rs b/src/librustc/infer/freshen.rs
index 16087959972..cf61cac0ac4 100644
--- a/src/librustc/infer/freshen.rs
+++ b/src/librustc/infer/freshen.rs
@@ -130,7 +130,7 @@ impl<'a, 'tcx> TypeFolder<'tcx> for TypeFreshener<'a, 'tcx> {
             | ty::ReScope(_)
             | ty::ReVar(_)
             | ty::RePlaceholder(..)
-            | ty::ReEmpty
+            | ty::ReEmpty(_)
             | ty::ReErased => {
                 // replace all free regions with 'erased
                 self.tcx().lifetimes.re_erased
diff --git a/src/librustc/infer/lexical_region_resolve/mod.rs b/src/librustc/infer/lexical_region_resolve/mod.rs
index cd4d2257de8..f4d583d9092 100644
--- a/src/librustc/infer/lexical_region_resolve/mod.rs
+++ b/src/librustc/infer/lexical_region_resolve/mod.rs
@@ -82,6 +82,16 @@ pub enum RegionResolutionError<'tcx> {
         Region<'tcx>,
     ),
 
+    /// Indicates a `'b: 'a` constraint where `'a` is in a universe that
+    /// cannot name the placeholder `'b`
+    UpperBoundUniverseConflict(
+        RegionVid,
+        RegionVariableOrigin,
+        ty::UniverseIndex,     // the universe index of the region variable
+        SubregionOrigin<'tcx>, // cause of the constraint
+        Region<'tcx>,          // the placeholder `'b`
+    ),
+
     /// Indicates a failure of a `MemberConstraint`. These arise during
     /// impl trait processing explicitly -- basically, the impl trait's hidden type
     /// included some region that it was not supposed to.
@@ -149,7 +159,14 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
     fn construct_var_data(&self, tcx: TyCtxt<'tcx>) -> LexicalRegionResolutions<'tcx> {
         LexicalRegionResolutions {
             error_region: tcx.lifetimes.re_static,
-            values: IndexVec::from_elem_n(VarValue::Value(tcx.lifetimes.re_empty), self.num_vars()),
+            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)
+                },
+                self.num_vars(),
+            ),
         }
     }
 
@@ -381,8 +398,11 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
                 // This is a specialized version of the `lub_concrete_regions`
                 // check below for a common case, here purely as an
                 // optimization.
-                if let ReEmpty = a_region {
-                    return false;
+                let b_universe = self.var_infos[b_vid].universe;
+                if let ReEmpty(a_universe) = a_region {
+                    if *a_universe == b_universe {
+                        return false;
+                    }
                 }
 
                 let mut lub = self.lub_concrete_regions(a_region, cur_region);
@@ -399,7 +419,6 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
                 // tighter bound than `'static`.
                 //
                 // (This might e.g. arise from being asked to prove `for<'a> { 'b: 'a }`.)
-                let b_universe = self.var_infos[b_vid].universe;
                 if let ty::RePlaceholder(p) = lub {
                     if b_universe.cannot_name(p.universe) {
                         lub = self.tcx().lifetimes.re_static;
@@ -445,7 +464,11 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
         self.lub_concrete_regions(a, b) == b
     }
 
-    /// Returns the smallest region `c` such that `a <= c` and `b <= c`.
+    /// Returns the least-upper-bound of `a` and `b`; i.e., the
+    /// smallest region `c` such that `a <= c` and `b <= c`.
+    ///
+    /// Neither `a` nor `b` may be an inference variable (hence the
+    /// term "concrete regions").
     fn lub_concrete_regions(&self, a: Region<'tcx>, b: Region<'tcx>) -> Region<'tcx> {
         let r = match (a, b) {
             (&ty::ReClosureBound(..), _)
@@ -457,14 +480,6 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
                 bug!("cannot relate region: LUB({:?}, {:?})", a, b);
             }
 
-            (r @ &ReStatic, _) | (_, r @ &ReStatic) => {
-                r // nothing lives longer than static
-            }
-
-            (&ReEmpty, r) | (r, &ReEmpty) => {
-                r // everything lives longer than empty
-            }
-
             (&ReVar(v_id), _) | (_, &ReVar(v_id)) => {
                 span_bug!(
                     self.var_infos[v_id].origin.span(),
@@ -475,6 +490,41 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
                 );
             }
 
+            (&ReStatic, _) | (_, &ReStatic) => {
+                // nothing lives longer than static
+                self.tcx().lifetimes.re_static
+            }
+
+            (&ReEmpty(_), r @ ReEarlyBound(_))
+            | (r @ ReEarlyBound(_), &ReEmpty(_))
+            | (&ReEmpty(_), r @ ReFree(_))
+            | (r @ ReFree(_), &ReEmpty(_))
+            | (&ReEmpty(_), r @ ReScope(_))
+            | (r @ ReScope(_), &ReEmpty(_)) => {
+                // all empty regions are less than early-bound, free,
+                // and scope regions
+                r
+            }
+
+            (&ReEmpty(a_ui), &ReEmpty(b_ui)) => {
+                // empty regions are ordered according to the universe
+                // they are associated with
+                let ui = a_ui.min(b_ui);
+                self.tcx().mk_region(ReEmpty(ui))
+            }
+
+            (&ReEmpty(empty_ui), &RePlaceholder(placeholder))
+            | (&RePlaceholder(placeholder), &ReEmpty(empty_ui)) => {
+                // 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
+                }
+            }
+
             (&ReEarlyBound(_), &ReScope(s_id))
             | (&ReScope(s_id), &ReEarlyBound(_))
             | (&ReFree(_), &ReScope(s_id))
@@ -800,6 +850,26 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
             }
         }
 
+        // If we have a scenario like `exists<'a> { forall<'b> { 'b:
+        // 'a } }`, we wind up without any lower-bound -- all we have
+        // are placeholders as upper bounds, but the universe of the
+        // variable `'a` doesn't permit those placeholders.
+        for upper_bound in &upper_bounds {
+            if let ty::RePlaceholder(p) = upper_bound.region {
+                if node_universe.cannot_name(p.universe) {
+                    let origin = self.var_infos[node_idx].origin.clone();
+                    errors.push(RegionResolutionError::UpperBoundUniverseConflict(
+                        node_idx,
+                        origin,
+                        node_universe,
+                        upper_bound.origin.clone(),
+                        upper_bound.region,
+                    ));
+                    return;
+                }
+            }
+        }
+
         // Errors in earlier passes can yield error variables without
         // resolution errors here; delay ICE in favor of those errors.
         self.tcx().sess.delay_span_bug(
@@ -914,7 +984,7 @@ impl<'cx, 'tcx> LexicalResolver<'cx, 'tcx> {
             }
 
             VerifyBound::IsEmpty => {
-                if let ty::ReEmpty = min {
+                if let ty::ReEmpty(_) = min {
                     true
                 } else {
                     false
diff --git a/src/librustc/infer/opaque_types/mod.rs b/src/librustc/infer/opaque_types/mod.rs
index c86f9f66ec8..fab753bb0f4 100644
--- a/src/librustc/infer/opaque_types/mod.rs
+++ b/src/librustc/infer/opaque_types/mod.rs
@@ -611,7 +611,7 @@ pub fn unexpected_hidden_region_diagnostic(
     );
 
     // Explain the region we are capturing.
-    if let ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReStatic | ty::ReEmpty = hidden_region {
+    if let ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReStatic | ty::ReEmpty(_) = hidden_region {
         // Assuming regionck succeeded (*), we ought to always be
         // capturing *some* region from the fn header, and hence it
         // ought to be free. So under normal circumstances, we will go
@@ -843,7 +843,7 @@ impl TypeFolder<'tcx> for ReverseMapper<'tcx> {
                         .emit();
                     }
                 }
-                self.tcx.lifetimes.re_empty
+                self.tcx.lifetimes.re_root_empty
             }
             None => {
                 self.tcx
diff --git a/src/librustc/infer/region_constraints/mod.rs b/src/librustc/infer/region_constraints/mod.rs
index 667a4c3a7e2..2c580e2e349 100644
--- a/src/librustc/infer/region_constraints/mod.rs
+++ b/src/librustc/infer/region_constraints/mod.rs
@@ -795,10 +795,10 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         match *region {
             ty::ReScope(..)
             | ty::ReStatic
-            | ty::ReEmpty
             | ty::ReErased
             | ty::ReFree(..)
             | ty::ReEarlyBound(..) => ty::UniverseIndex::ROOT,
+            ty::ReEmpty(ui) => ui,
             ty::RePlaceholder(placeholder) => placeholder.universe,
             ty::ReClosureBound(vid) | ty::ReVar(vid) => self.var_universe(vid),
             ty::ReLateBound(..) => bug!("universe(): encountered bound region {:?}", region),
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index f12032943f9..d56d4fa1485 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -173,8 +173,13 @@ pub struct CommonTypes<'tcx> {
 }
 
 pub struct CommonLifetimes<'tcx> {
-    pub re_empty: Region<'tcx>,
+    /// ReEmpty in the root universe
+    pub re_root_empty: Region<'tcx>,
+
+    /// ReStatic
     pub re_static: Region<'tcx>,
+
+    /// Erased region, used after type-checking
     pub re_erased: Region<'tcx>,
 }
 
@@ -876,7 +881,7 @@ impl<'tcx> CommonLifetimes<'tcx> {
         let mk = |r| interners.region.intern(r, |r| Interned(interners.arena.alloc(r))).0;
 
         CommonLifetimes {
-            re_empty: mk(RegionKind::ReEmpty),
+            re_root_empty: mk(RegionKind::ReEmpty(ty::UniverseIndex::ROOT)),
             re_static: mk(RegionKind::ReStatic),
             re_erased: mk(RegionKind::ReErased),
         }
diff --git a/src/librustc/ty/print/pretty.rs b/src/librustc/ty/print/pretty.rs
index f5c14e73db2..0da680d1f91 100644
--- a/src/librustc/ty/print/pretty.rs
+++ b/src/librustc/ty/print/pretty.rs
@@ -1382,7 +1382,7 @@ impl<F: fmt::Write> PrettyPrinter<'tcx> for FmtPrinter<'_, 'tcx, F> {
 
             ty::ReVar(_) | ty::ReScope(_) | ty::ReErased => false,
 
-            ty::ReStatic | ty::ReEmpty | ty::ReClosureBound(_) => true,
+            ty::ReStatic | ty::ReEmpty(_) | ty::ReClosureBound(_) => true,
         }
     }
 }
@@ -1464,10 +1464,14 @@ impl<F: fmt::Write> FmtPrinter<'_, '_, F> {
                 p!(write("'static"));
                 return Ok(self);
             }
-            ty::ReEmpty => {
+            ty::ReEmpty(ty::UniverseIndex::ROOT) => {
                 p!(write("'<empty>"));
                 return Ok(self);
             }
+            ty::ReEmpty(ui) => {
+                p!(write("'<empty:{:?}>", ui));
+                return Ok(self);
+            }
 
             // The user should never encounter these in unsubstituted form.
             ty::ReClosureBound(vid) => {
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index c1ae4d9fe17..a56684ee8e9 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -108,7 +108,7 @@ impl fmt::Debug for ty::RegionKind {
 
             ty::RePlaceholder(placeholder) => write!(f, "RePlaceholder({:?})", placeholder),
 
-            ty::ReEmpty => write!(f, "ReEmpty"),
+            ty::ReEmpty(ui) => write!(f, "ReEmpty({:?})", ui),
 
             ty::ReErased => write!(f, "ReErased"),
         }
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index dffe86d9462..c0ee14192ff 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -1269,11 +1269,67 @@ rustc_index::newtype_index! {
 
 pub type Region<'tcx> = &'tcx RegionKind;
 
-/// Representation of regions.
+/// Representation of (lexical) regions. Note that the NLL checker
+/// uses a distinct representation of regions. For this reason, it
+/// internally replaces all the regions with inference variables --
+/// the index of the variable is then used to index into internal NLL
+/// data structures. See `rustc_mir::borrow_check` module for more
+/// information.
 ///
-/// Unlike types, most region variants are "fictitious", not concrete,
-/// regions. Among these, `ReStatic`, `ReEmpty` and `ReScope` are the only
-/// ones representing concrete regions.
+/// ## The Region lattice within a given function
+///
+/// In general, the (lexical, and hence deprecated) region lattice
+/// looks like
+///
+/// ```
+/// static ----------+-----...------+       (greatest)
+/// |                |              |
+/// early-bound and  |              |
+/// free regions     |              |
+/// |                |              |
+/// scope regions    |              |
+/// |                |              |
+/// empty(root)   placeholder(U1)   |
+/// |            /                  |
+/// |           /         placeholder(Un)
+/// empty(U1) --         /
+/// |                   /
+/// ...                /
+/// |                 /
+/// empty(Un) --------                      (smallest)
+/// ```
+///
+/// Early-bound/free regions are the named lifetimes in scope from the
+/// function declaration. They have relationships to one another
+/// determined based on the declared relationships from the
+/// function. They all collectively outlive the scope regions. (See
+/// `RegionRelations` type, and particularly
+/// `crate::infer::outlives::free_region_map::FreeRegionMap`.)
+///
+/// The scope regions are related to one another based on the AST
+/// structure. (See `RegionRelations` type, and particularly the
+/// `rustc::middle::region::ScopeTree`.)
+///
+/// Note that inference variables and bound regions are not included
+/// in this diagram. In the case of inference variables, they should
+/// be inferred to some other region from the diagram.  In the case of
+/// bound regions, they are excluded because they don't make sense to
+/// include -- the diagram indicates the relationship between free
+/// regions.
+///
+/// ## Inference variables
+///
+/// During region inference, we sometimes create inference variables,
+/// represented as `ReVar`. These will be inferred by the code in
+/// `infer::lexical_region_resolve` to some free region from the
+/// lattice above (the minimal region that meets the
+/// constraints).
+///
+/// During NLL checking, where regions are defined differently, we
+/// also use `ReVar` -- in that case, the index is used to index into
+/// the NLL region checker's data structures. The variable may in fact
+/// represent either a free region or an inference variable, in that
+/// case.
 ///
 /// ## Bound Regions
 ///
@@ -1356,14 +1412,13 @@ pub enum RegionKind {
     /// Should not exist after typeck.
     RePlaceholder(ty::PlaceholderRegion),
 
-    /// Empty lifetime is for data that is never accessed.
-    /// Bottom in the region lattice. We treat ReEmpty somewhat
-    /// specially; at least right now, we do not generate instances of
-    /// it during the GLB computations, but rather
-    /// generate an error instead. This is to improve error messages.
-    /// The only way to get an instance of ReEmpty is to have a region
-    /// variable with no constraints.
-    ReEmpty,
+    /// 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.
+    ReEmpty(ty::UniverseIndex),
 
     /// Erased region, used by trait selection, in MIR and during codegen.
     ReErased,
@@ -1612,7 +1667,7 @@ impl RegionKind {
             RegionKind::ReStatic => true,
             RegionKind::ReVar(..) => false,
             RegionKind::RePlaceholder(placeholder) => placeholder.name.is_named(),
-            RegionKind::ReEmpty => false,
+            RegionKind::ReEmpty(_) => false,
             RegionKind::ReErased => false,
             RegionKind::ReClosureBound(..) => false,
         }
@@ -1695,7 +1750,7 @@ impl RegionKind {
                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
                 flags = flags | TypeFlags::HAS_RE_EARLY_BOUND;
             }
-            ty::ReEmpty | ty::ReStatic | ty::ReFree { .. } | ty::ReScope { .. } => {
+            ty::ReEmpty(_) | ty::ReStatic | ty::ReFree { .. } | ty::ReScope { .. } => {
                 flags = flags | TypeFlags::HAS_FREE_REGIONS;
             }
             ty::ReErased => {}
@@ -1705,7 +1760,7 @@ impl RegionKind {
         }
 
         match *self {
-            ty::ReStatic | ty::ReEmpty | ty::ReErased | ty::ReLateBound(..) => (),
+            ty::ReStatic | ty::ReEmpty(_) | ty::ReErased | ty::ReLateBound(..) => (),
             _ => flags = flags | TypeFlags::HAS_FREE_LOCAL_NAMES,
         }
 
diff --git a/src/librustc_index/vec.rs b/src/librustc_index/vec.rs
index d14bafb44fd..1dfe97238a3 100644
--- a/src/librustc_index/vec.rs
+++ b/src/librustc_index/vec.rs
@@ -574,6 +574,14 @@ impl<I: Idx, T> IndexVec<I, T> {
         IndexVec { raw: vec![elem; n], _marker: PhantomData }
     }
 
+    /// Create an `IndexVec` with `n` elements, where the value of each
+    /// element is the result of `func(i)`
+    #[inline]
+    pub fn from_fn_n(func: impl FnMut(I) -> T, n: usize) -> Self {
+        let indices = (0..n).map(I::new);
+        Self::from_raw(indices.map(func).collect())
+    }
+
     #[inline]
     pub fn push(&mut self, d: T) -> I {
         let idx = I::new(self.len());
diff --git a/src/librustc_mir/borrow_check/diagnostics/region_name.rs b/src/librustc_mir/borrow_check/diagnostics/region_name.rs
index 47eb2d8940a..09d61d9ad9a 100644
--- a/src/librustc_mir/borrow_check/diagnostics/region_name.rs
+++ b/src/librustc_mir/borrow_check/diagnostics/region_name.rs
@@ -291,7 +291,7 @@ impl<'tcx> MirBorrowckCtxt<'_, 'tcx> {
             | ty::ReScope(..)
             | ty::ReVar(..)
             | ty::RePlaceholder(..)
-            | ty::ReEmpty
+            | ty::ReEmpty(_)
             | ty::ReErased
             | ty::ReClosureBound(..) => None,
         }
diff --git a/src/librustc_mir/borrow_check/type_check/constraint_conversion.rs b/src/librustc_mir/borrow_check/type_check/constraint_conversion.rs
index 8f65a0f01c6..a3e38cd7a5f 100644
--- a/src/librustc_mir/borrow_check/type_check/constraint_conversion.rs
+++ b/src/librustc_mir/borrow_check/type_check/constraint_conversion.rs
@@ -160,7 +160,8 @@ impl<'a, 'b, 'tcx> TypeOutlivesDelegate<'tcx> for &'a mut ConstraintConversion<'
         a: ty::Region<'tcx>,
         b: ty::Region<'tcx>,
     ) {
-        if let ty::ReEmpty = a {
+        // FIXME -- this is not the fix I would prefer
+        if let ty::ReEmpty(ty::UniverseIndex::ROOT) = a {
             return;
         }
         let b = self.to_region_vid(b);
@@ -175,7 +176,8 @@ impl<'a, 'b, 'tcx> TypeOutlivesDelegate<'tcx> for &'a mut ConstraintConversion<'
         a: ty::Region<'tcx>,
         bound: VerifyBound<'tcx>,
     ) {
-        if let ty::ReEmpty = a {
+        // FIXME: I'd prefer if NLL had a notion of empty
+        if let ty::ReEmpty(ty::UniverseIndex::ROOT) = a {
             return;
         }
         let type_test = self.verify_to_type_test(kind, a, bound);
diff --git a/src/librustc_mir/borrow_check/type_check/free_region_relations.rs b/src/librustc_mir/borrow_check/type_check/free_region_relations.rs
index 4caab458025..cf8c3449d66 100644
--- a/src/librustc_mir/borrow_check/type_check/free_region_relations.rs
+++ b/src/librustc_mir/borrow_check/type_check/free_region_relations.rs
@@ -333,7 +333,7 @@ impl UniversalRegionRelationsBuilder<'cx, 'tcx> {
                     // `where Type:` is lowered to `where Type: 'empty` so that
                     // we check `Type` is well formed, but there's no use for
                     // this bound here.
-                    if let ty::ReEmpty = r1 {
+                    if let ty::ReEmpty(_) = r1 {
                         return;
                     }
 
diff --git a/src/librustc_traits/chalk_context/resolvent_ops.rs b/src/librustc_traits/chalk_context/resolvent_ops.rs
index 70e3c4c7ab1..301ebf8adc5 100644
--- a/src/librustc_traits/chalk_context/resolvent_ops.rs
+++ b/src/librustc_traits/chalk_context/resolvent_ops.rs
@@ -246,9 +246,11 @@ impl TypeRelation<'tcx> for AnswerSubstitutor<'cx, 'tcx> {
                 assert_eq!(a_bound.assert_bound_var(), b_bound.assert_bound_var());
             }
 
-            (ty::ReStatic, ty::ReStatic)
-            | (ty::ReErased, ty::ReErased)
-            | (ty::ReEmpty, ty::ReEmpty) => (),
+            (ty::ReStatic, ty::ReStatic) | (ty::ReErased, ty::ReErased) => (),
+
+            (ty::ReEmpty(a_ui), ty::ReEmpty(b_ui)) => {
+                assert_eq!(a_ui, b_ui);
+            }
 
             (&ty::ReFree(a_free), &ty::ReFree(b_free)) => {
                 assert_eq!(a_free, b_free);
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 4d812d2621c..713f41311a6 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -2322,7 +2322,8 @@ fn explicit_predicates_of(tcx: TyCtxt<'_>, def_id: DefId) -> ty::GenericPredicat
                         // compiler/tooling bugs from not handling WF predicates.
                     } else {
                         let span = bound_pred.bounded_ty.span;
-                        let predicate = ty::OutlivesPredicate(ty, tcx.mk_region(ty::ReEmpty));
+                        let re_root_empty = tcx.lifetimes.re_root_empty;
+                        let predicate = ty::OutlivesPredicate(ty, re_root_empty);
                         predicates.push((
                             ty::Predicate::TypeOutlives(ty::Binder::dummy(predicate)),
                             span,
diff --git a/src/librustc_typeck/outlives/utils.rs b/src/librustc_typeck/outlives/utils.rs
index 2d7fc9d62e5..0cc322f8c2d 100644
--- a/src/librustc_typeck/outlives/utils.rs
+++ b/src/librustc_typeck/outlives/utils.rs
@@ -166,7 +166,7 @@ fn is_free_region(tcx: TyCtxt<'_>, region: Region<'_>) -> bool {
         //
         //     struct Bar<T>(<Self as Foo>::Type) where Self: ;
         //     struct Baz<'a>(&'a Self) where Self: ;
-        RegionKind::ReEmpty => false,
+        RegionKind::ReEmpty(_) => false,
 
         // These regions don't appear in types from type declarations:
         RegionKind::ReErased
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index 5ca961ed344..6f5caea250b 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -453,7 +453,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
             | ty::ReScope(..)
             | ty::ReVar(..)
             | ty::RePlaceholder(..)
-            | ty::ReEmpty
+            | ty::ReEmpty(_)
             | ty::ReErased => {
                 // We don't expect to see anything but 'static or bound
                 // regions when visiting member types or method types.
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index 2a35ab812a5..f140f11b090 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -447,7 +447,7 @@ impl Clean<Option<Lifetime>> for ty::RegionKind {
             | ty::ReScope(..)
             | ty::ReVar(..)
             | ty::RePlaceholder(..)
-            | ty::ReEmpty
+            | ty::ReEmpty(_)
             | ty::ReClosureBound(_)
             | ty::ReErased => {
                 debug!("cannot clean region {:?}", self);
@@ -521,7 +521,7 @@ impl<'tcx> Clean<Option<WherePredicate>>
         let ty::OutlivesPredicate(ref a, ref b) = *self;
 
         match (a, b) {
-            (ty::ReEmpty, ty::ReEmpty) => {
+            (ty::ReEmpty(_), ty::ReEmpty(_)) => {
                 return None;
             }
             _ => {}
@@ -539,7 +539,7 @@ impl<'tcx> Clean<Option<WherePredicate>> for ty::OutlivesPredicate<Ty<'tcx>, ty:
         let ty::OutlivesPredicate(ref ty, ref lt) = *self;
 
         match lt {
-            ty::ReEmpty => return None,
+            ty::ReEmpty(_) => return None,
             _ => {}
         }