Move RegionKind to rustc_type_ir

12 files changed, 597 insertions, 344 deletions

diff --git a/compiler/rustc_borrowck/src/region_infer/mod.rs b/compiler/rustc_borrowck/src/region_infer/mod.rs
index 2c460bcb72d..fcb0978111e 100644
--- a/compiler/rustc_borrowck/src/region_infer/mod.rs
+++ b/compiler/rustc_borrowck/src/region_infer/mod.rs
@@ -500,7 +500,7 @@ impl<'tcx> RegionInferenceContext<'tcx> {
     }
 
     /// Returns an iterator over all the region indices.
-    pub fn regions(&self) -> impl Iterator<Item = RegionVid> + '_ {
+    pub fn regions(&self) -> impl Iterator<Item = RegionVid> + 'tcx {
         self.definitions.indices()
     }
 
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index c43cf07b3ad..c9589a70488 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -114,6 +114,12 @@ impl<'tcx> Interner for TyCtxt<'tcx> {
     type DelaySpanBugEmitted = DelaySpanBugEmitted;
     type PredicateKind = ty::PredicateKind<'tcx>;
     type AllocId = crate::mir::interpret::AllocId;
+
+    type EarlyBoundRegion = ty::EarlyBoundRegion;
+    type BoundRegion = ty::BoundRegion;
+    type FreeRegion = ty::FreeRegion;
+    type RegionVid = ty::RegionVid;
+    type PlaceholderRegion = ty::PlaceholderRegion;
 }
 
 /// A type that is not publicly constructable. This prevents people from making [`TyKind::Error`]s
@@ -136,7 +142,7 @@ pub struct CtxtInterners<'tcx> {
     type_: InternedSet<'tcx, WithStableHash<TyS<'tcx>>>,
     substs: InternedSet<'tcx, InternalSubsts<'tcx>>,
     canonical_var_infos: InternedSet<'tcx, List<CanonicalVarInfo<'tcx>>>,
-    region: InternedSet<'tcx, RegionKind>,
+    region: InternedSet<'tcx, RegionKind<'tcx>>,
     poly_existential_predicates:
         InternedSet<'tcx, List<ty::Binder<'tcx, ExistentialPredicate<'tcx>>>>,
     predicate: InternedSet<'tcx, PredicateS<'tcx>>,
@@ -2175,7 +2181,7 @@ macro_rules! direct_interners {
 }
 
 direct_interners! {
-    region: mk_region(RegionKind): Region -> Region<'tcx>,
+    region: mk_region(RegionKind<'tcx>): Region -> Region<'tcx>,
     const_: mk_const(ConstS<'tcx>): Const -> Const<'tcx>,
     const_allocation: intern_const_alloc(Allocation): ConstAllocation -> ConstAllocation<'tcx>,
     layout: intern_layout(LayoutS<'tcx>): Layout -> Layout<'tcx>,
@@ -2274,7 +2280,7 @@ impl<'tcx> TyCtxt<'tcx> {
     /// Same a `self.mk_region(kind)`, but avoids accessing the interners if
     /// `*r == kind`.
     #[inline]
-    pub fn reuse_or_mk_region(self, r: Region<'tcx>, kind: RegionKind) -> Region<'tcx> {
+    pub fn reuse_or_mk_region(self, r: Region<'tcx>, kind: RegionKind<'tcx>) -> Region<'tcx> {
         if *r == kind { r } else { self.mk_region(kind) }
     }
 
diff --git a/compiler/rustc_middle/src/ty/impls_ty.rs b/compiler/rustc_middle/src/ty/impls_ty.rs
index 42e5a05d63b..88397a2bb56 100644
--- a/compiler/rustc_middle/src/ty/impls_ty.rs
+++ b/compiler/rustc_middle/src/ty/impls_ty.rs
@@ -11,7 +11,6 @@ use rustc_data_structures::stable_hasher::HashingControls;
 use rustc_data_structures::stable_hasher::{HashStable, StableHasher, ToStableHashKey};
 use rustc_query_system::ich::StableHashingContext;
 use std::cell::RefCell;
-use std::mem;
 
 impl<'a, 'tcx, T> HashStable<StableHashingContext<'a>> for &'tcx ty::List<T>
 where
@@ -102,43 +101,12 @@ impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for ty::subst::GenericArgKin
     }
 }
 
-impl<'a> HashStable<StableHashingContext<'a>> for ty::RegionKind {
+impl<'a> HashStable<StableHashingContext<'a>> for ty::EarlyBoundRegion {
+    #[inline]
     fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
-        mem::discriminant(self).hash_stable(hcx, hasher);
-        match *self {
-            ty::ReErased | ty::ReStatic => {
-                // No variant fields to hash for these ...
-            }
-            ty::ReEmpty(universe) => {
-                universe.hash_stable(hcx, hasher);
-            }
-            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrAnon(i), .. }) => {
-                db.hash_stable(hcx, hasher);
-                i.hash_stable(hcx, hasher);
-            }
-            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrNamed(def_id, name), .. }) => {
-                db.hash_stable(hcx, hasher);
-                def_id.hash_stable(hcx, hasher);
-                name.hash_stable(hcx, hasher);
-            }
-            ty::ReLateBound(db, ty::BoundRegion { kind: ty::BrEnv, .. }) => {
-                db.hash_stable(hcx, hasher);
-            }
-            ty::ReEarlyBound(ty::EarlyBoundRegion { def_id, index, name }) => {
-                def_id.hash_stable(hcx, hasher);
-                index.hash_stable(hcx, hasher);
-                name.hash_stable(hcx, hasher);
-            }
-            ty::ReFree(ref free_region) => {
-                free_region.hash_stable(hcx, hasher);
-            }
-            ty::RePlaceholder(p) => {
-                p.hash_stable(hcx, hasher);
-            }
-            ty::ReVar(reg) => {
-                reg.hash_stable(hcx, hasher);
-            }
-        }
+        self.def_id.hash_stable(hcx, hasher);
+        self.index.hash_stable(hcx, hasher);
+        self.name.hash_stable(hcx, hasher);
     }
 }
 
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index 749feb850b0..77722085f2d 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -55,6 +55,7 @@ use std::{fmt, str};
 
 pub use crate::ty::diagnostics::*;
 pub use rustc_type_ir::InferTy::*;
+pub use rustc_type_ir::RegionKind::*;
 pub use rustc_type_ir::TyKind::*;
 pub use rustc_type_ir::*;
 
@@ -80,7 +81,6 @@ pub use self::list::List;
 pub use self::parameterized::ParameterizedOverTcx;
 pub use self::rvalue_scopes::RvalueScopes;
 pub use self::sty::BoundRegionKind::*;
-pub use self::sty::RegionKind::*;
 pub use self::sty::{
     Article, Binder, BoundRegion, BoundRegionKind, BoundTy, BoundTyKind, BoundVar,
     BoundVariableKind, CanonicalPolyFnSig, ClosureSubsts, ClosureSubstsParts, ConstVid,
@@ -1161,83 +1161,6 @@ impl<'tcx> OpaqueHiddenType<'tcx> {
     }
 }
 
-rustc_index::newtype_index! {
-    /// "Universes" are used during type- and trait-checking in the
-    /// presence of `for<..>` binders to control what sets of names are
-    /// visible. Universes are arranged into a tree: the root universe
-    /// contains names that are always visible. Each child then adds a new
-    /// set of names that are visible, in addition to those of its parent.
-    /// We say that the child universe "extends" the parent universe with
-    /// new names.
-    ///
-    /// To make this more concrete, consider this program:
-    ///
-    /// ```ignore (illustrative)
-    /// struct Foo { }
-    /// fn bar<T>(x: T) {
-    ///   let y: for<'a> fn(&'a u8, Foo) = ...;
-    /// }
-    /// ```
-    ///
-    /// The struct name `Foo` is in the root universe U0. But the type
-    /// parameter `T`, introduced on `bar`, is in an extended universe U1
-    /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
-    /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
-    /// region `'a` is in a universe U2 that extends U1, because we can
-    /// name it inside the fn type but not outside.
-    ///
-    /// Universes are used to do type- and trait-checking around these
-    /// "forall" binders (also called **universal quantification**). The
-    /// idea is that when, in the body of `bar`, we refer to `T` as a
-    /// type, we aren't referring to any type in particular, but rather a
-    /// kind of "fresh" type that is distinct from all other types we have
-    /// actually declared. This is called a **placeholder** type, and we
-    /// use universes to talk about this. In other words, a type name in
-    /// universe 0 always corresponds to some "ground" type that the user
-    /// declared, but a type name in a non-zero universe is a placeholder
-    /// type -- an idealized representative of "types in general" that we
-    /// use for checking generic functions.
-    pub struct UniverseIndex {
-        derive [HashStable]
-        DEBUG_FORMAT = "U{}",
-    }
-}
-
-impl UniverseIndex {
-    pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0);
-
-    /// Returns the "next" universe index in order -- this new index
-    /// is considered to extend all previous universes. This
-    /// corresponds to entering a `forall` quantifier. So, for
-    /// example, suppose we have this type in universe `U`:
-    ///
-    /// ```ignore (illustrative)
-    /// for<'a> fn(&'a u32)
-    /// ```
-    ///
-    /// Once we "enter" into this `for<'a>` quantifier, we are in a
-    /// new universe that extends `U` -- in this new universe, we can
-    /// name the region `'a`, but that region was not nameable from
-    /// `U` because it was not in scope there.
-    pub fn next_universe(self) -> UniverseIndex {
-        UniverseIndex::from_u32(self.private.checked_add(1).unwrap())
-    }
-
-    /// Returns `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` (`self >= other`).
-    pub fn can_name(self, other: UniverseIndex) -> bool {
-        self.private >= other.private
-    }
-
-    /// Returns `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, type, or const. Placeholders are
 /// identified by both a universe, as well as a name residing within that universe. Distinct bound
 /// regions/types/consts within the same universe simply have an unknown relationship to one
diff --git a/compiler/rustc_middle/src/ty/print/mod.rs b/compiler/rustc_middle/src/ty/print/mod.rs
index 7ae23d371e5..d57cf8f0149 100644
--- a/compiler/rustc_middle/src/ty/print/mod.rs
+++ b/compiler/rustc_middle/src/ty/print/mod.rs
@@ -57,7 +57,7 @@ pub trait Printer<'tcx>: Sized {
         self.default_print_impl_path(impl_def_id, substs, self_ty, trait_ref)
     }
 
-    fn print_region(self, region: ty::Region<'_>) -> Result<Self::Region, Self::Error>;
+    fn print_region(self, region: ty::Region<'tcx>) -> Result<Self::Region, Self::Error>;
 
     fn print_type(self, ty: Ty<'tcx>) -> Result<Self::Type, Self::Error>;
 
@@ -291,7 +291,7 @@ pub fn characteristic_def_id_of_type(ty: Ty<'_>) -> Option<DefId> {
     characteristic_def_id_of_type_cached(ty, &mut SsoHashSet::new())
 }
 
-impl<'tcx, P: Printer<'tcx>> Print<'tcx, P> for ty::Region<'_> {
+impl<'tcx, P: Printer<'tcx>> Print<'tcx, P> for ty::Region<'tcx> {
     type Output = P::Region;
     type Error = P::Error;
     fn print(&self, cx: P) -> Result<Self::Output, Self::Error> {
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index 58dab0f96ab..97e5a4983fc 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -182,7 +182,7 @@ impl<'tcx> RegionHighlightMode<'tcx> {
     }
 
     /// Returns `Some(n)` with the number to use for the given region, if any.
-    fn region_highlighted(&self, region: ty::Region<'_>) -> Option<usize> {
+    fn region_highlighted(&self, region: ty::Region<'tcx>) -> Option<usize> {
         self.highlight_regions.iter().find_map(|h| match h {
             Some((r, n)) if *r == region => Some(*n),
             _ => None,
@@ -276,7 +276,7 @@ pub trait PrettyPrinter<'tcx>:
     /// Returns `true` if the region should be printed in
     /// optional positions, e.g., `&'a T` or `dyn Tr + 'b`.
     /// This is typically the case for all non-`'_` regions.
-    fn should_print_region(&self, region: ty::Region<'_>) -> bool;
+    fn should_print_region(&self, region: ty::Region<'tcx>) -> bool;
 
     // Defaults (should not be overridden):
 
@@ -1706,7 +1706,7 @@ impl<'tcx> Printer<'tcx> for FmtPrinter<'_, 'tcx> {
         self.default_print_def_path(def_id, substs)
     }
 
-    fn print_region(self, region: ty::Region<'_>) -> Result<Self::Region, Self::Error> {
+    fn print_region(self, region: ty::Region<'tcx>) -> Result<Self::Region, Self::Error> {
         self.pretty_print_region(region)
     }
 
@@ -1911,7 +1911,7 @@ impl<'tcx> PrettyPrinter<'tcx> for FmtPrinter<'_, 'tcx> {
         Ok(inner)
     }
 
-    fn should_print_region(&self, region: ty::Region<'_>) -> bool {
+    fn should_print_region(&self, region: ty::Region<'tcx>) -> bool {
         let highlight = self.region_highlight_mode;
         if highlight.region_highlighted(region).is_some() {
             return true;
@@ -1978,8 +1978,8 @@ impl<'tcx> PrettyPrinter<'tcx> for FmtPrinter<'_, 'tcx> {
 }
 
 // HACK(eddyb) limited to `FmtPrinter` because of `region_highlight_mode`.
-impl FmtPrinter<'_, '_> {
-    pub fn pretty_print_region(mut self, region: ty::Region<'_>) -> Result<Self, fmt::Error> {
+impl<'tcx> FmtPrinter<'_, 'tcx> {
+    pub fn pretty_print_region(mut self, region: ty::Region<'tcx>) -> Result<Self, fmt::Error> {
         define_scoped_cx!(self);
 
         // Watch out for region highlights.
@@ -2383,15 +2383,6 @@ macro_rules! define_print_and_forward_display {
     };
 }
 
-// HACK(eddyb) this is separate because `ty::RegionKind` doesn't need lifting.
-impl<'tcx> fmt::Display for ty::Region<'tcx> {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        ty::tls::with(|tcx| {
-            f.write_str(&self.print(FmtPrinter::new(tcx, Namespace::TypeNS))?.into_buffer())
-        })
-    }
-}
-
 /// Wrapper type for `ty::TraitRef` which opts-in to pretty printing only
 /// the trait path. That is, it will print `Trait<U>` instead of
 /// `<T as Trait<U>>`.
@@ -2456,6 +2447,7 @@ impl<'tcx> ty::PolyTraitPredicate<'tcx> {
 }
 
 forward_display_to_print! {
+    ty::Region<'tcx>,
     Ty<'tcx>,
     &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>>,
     ty::Const<'tcx>,
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 961792260e4..8ba5b882fdd 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -81,30 +81,6 @@ impl fmt::Debug for ty::BoundRegionKind {
     }
 }
 
-impl fmt::Debug for ty::RegionKind {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match *self {
-            ty::ReEarlyBound(ref data) => write!(f, "ReEarlyBound({}, {})", data.index, data.name),
-
-            ty::ReLateBound(binder_id, ref bound_region) => {
-                write!(f, "ReLateBound({:?}, {:?})", binder_id, bound_region)
-            }
-
-            ty::ReFree(ref fr) => fr.fmt(f),
-
-            ty::ReStatic => write!(f, "ReStatic"),
-
-            ty::ReVar(ref vid) => vid.fmt(f),
-
-            ty::RePlaceholder(placeholder) => write!(f, "RePlaceholder({:?})", placeholder),
-
-            ty::ReEmpty(ui) => write!(f, "ReEmpty({:?})", ui),
-
-            ty::ReErased => write!(f, "ReErased"),
-        }
-    }
-}
-
 impl fmt::Debug for ty::FreeRegion {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "ReFree({:?}, {:?})", self.scope, self.bound_region)
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index cc85859e1cc..296442e2436 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -29,11 +29,13 @@ use std::ops::{ControlFlow, Deref, Range};
 use ty::util::IntTypeExt;
 
 use rustc_type_ir::sty::TyKind::*;
+use rustc_type_ir::RegionKind as IrRegionKind;
 use rustc_type_ir::TyKind as IrTyKind;
 
 // Re-export the `TyKind` from `rustc_type_ir` here for convenience
 #[rustc_diagnostic_item = "TyKind"]
 pub type TyKind<'tcx> = IrTyKind<TyCtxt<'tcx>>;
+pub type RegionKind<'tcx> = IrRegionKind<TyCtxt<'tcx>>;
 
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, TyEncodable, TyDecodable)]
 #[derive(HashStable, TypeFoldable, Lift)]
@@ -1308,12 +1310,12 @@ impl ParamConst {
 /// Use this rather than `RegionKind`, whenever possible.
 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, HashStable)]
 #[rustc_pass_by_value]
-pub struct Region<'tcx>(pub Interned<'tcx, RegionKind>);
+pub struct Region<'tcx>(pub Interned<'tcx, RegionKind<'tcx>>);
 
 impl<'tcx> Deref for Region<'tcx> {
-    type Target = RegionKind;
+    type Target = RegionKind<'tcx>;
 
-    fn deref(&self) -> &RegionKind {
+    fn deref(&self) -> &RegionKind<'tcx> {
         &self.0.0
     }
 }
@@ -1324,157 +1326,19 @@ impl<'tcx> fmt::Debug for Region<'tcx> {
     }
 }
 
-/// Representation of 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_const_eval::borrow_check`
-/// module for more information.
-///
-/// Note: operations are on the wrapper `Region` type, which is interned,
-/// rather than this type.
-///
-/// ## The Region lattice within a given function
-///
-/// In general, the region lattice looks like
-///
-/// ```text
-/// static ----------+-----...------+       (greatest)
-/// |                |              |
-/// early-bound and  |              |
-/// free 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.
-///
-/// 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
-///
-/// These are regions that are stored behind a binder and must be substituted
-/// with some concrete region before being used. There are two kind of
-/// bound regions: early-bound, which are bound in an item's `Generics`,
-/// and are substituted by an `InternalSubsts`, and late-bound, which are part of
-/// higher-ranked types (e.g., `for<'a> fn(&'a ())`), and are substituted by
-/// the likes of `liberate_late_bound_regions`. The distinction exists
-/// because higher-ranked lifetimes aren't supported in all places. See [1][2].
-///
-/// Unlike `Param`s, bound regions are not supposed to exist "in the wild"
-/// outside their binder, e.g., in types passed to type inference, and
-/// should first be substituted (by placeholder regions, free regions,
-/// or region variables).
-///
-/// ## Placeholder and Free Regions
-///
-/// One often wants to work with bound regions without knowing their precise
-/// identity. For example, when checking a function, the lifetime of a borrow
-/// can end up being assigned to some region parameter. In these cases,
-/// it must be ensured that bounds on the region can't be accidentally
-/// assumed without being checked.
-///
-/// To do this, we replace the bound regions with placeholder markers,
-/// which don't satisfy any relation not explicitly provided.
-///
-/// There are two kinds of placeholder regions in rustc: `ReFree` and
-/// `RePlaceholder`. When checking an item's body, `ReFree` is supposed
-/// to be used. These also support explicit bounds: both the internally-stored
-/// *scope*, which the region is assumed to outlive, as well as other
-/// relations stored in the `FreeRegionMap`. Note that these relations
-/// aren't checked when you `make_subregion` (or `eq_types`), only by
-/// `resolve_regions_and_report_errors`.
-///
-/// When working with higher-ranked types, some region relations aren't
-/// yet known, so you can't just call `resolve_regions_and_report_errors`.
-/// `RePlaceholder` is designed for this purpose. In these contexts,
-/// there's also the risk that some inference variable laying around will
-/// get unified with your placeholder region: if you want to check whether
-/// `for<'a> Foo<'_>: 'a`, and you substitute your bound region `'a`
-/// with a placeholder region `'%a`, the variable `'_` would just be
-/// instantiated to the placeholder region `'%a`, which is wrong because
-/// the inference variable is supposed to satisfy the relation
-/// *for every value of the placeholder region*. To ensure that doesn't
-/// happen, you can use `leak_check`. This is more clearly explained
-/// by the [rustc dev guide].
-///
-/// [1]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
-/// [2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
-/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
-#[derive(Clone, PartialEq, Eq, Hash, Copy, TyEncodable, TyDecodable, PartialOrd, Ord)]
-pub enum RegionKind {
-    /// Region bound in a type or fn declaration which will be
-    /// substituted 'early' -- that is, at the same time when type
-    /// parameters are substituted.
-    ReEarlyBound(EarlyBoundRegion),
-
-    /// Region bound in a function scope, which will be substituted when the
-    /// function is called.
-    ReLateBound(ty::DebruijnIndex, BoundRegion),
-
-    /// When checking a function body, the types of all arguments and so forth
-    /// that refer to bound region parameters are modified to refer to free
-    /// region parameters.
-    ReFree(FreeRegion),
-
-    /// Static data that has an "infinite" lifetime. Top in the region lattice.
-    ReStatic,
-
-    /// A region variable. Should not exist outside of type inference.
-    ReVar(RegionVid),
-
-    /// A placeholder region -- basically, the higher-ranked version of `ReFree`.
-    /// Should not exist outside of type inference.
-    RePlaceholder(ty::PlaceholderRegion),
-
-    /// 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,
-}
-
-#[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable, Debug, PartialOrd, Ord)]
+#[derive(Copy, Clone, PartialEq, Eq, Hash, TyEncodable, TyDecodable, PartialOrd, Ord)]
 pub struct EarlyBoundRegion {
     pub def_id: DefId,
     pub index: u32,
     pub name: Symbol,
 }
 
+impl fmt::Debug for EarlyBoundRegion {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "{}, {}", self.index, self.name)
+    }
+}
+
 /// A **`const`** **v**ariable **ID**.
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
 pub struct ConstVid<'tcx> {
@@ -1590,7 +1454,7 @@ impl<'tcx> PolyExistentialProjection<'tcx> {
 
 /// Region utilities
 impl<'tcx> Region<'tcx> {
-    pub fn kind(self) -> RegionKind {
+    pub fn kind(self) -> RegionKind<'tcx> {
         *self.0.0
     }
 
diff --git a/compiler/rustc_middle/src/ty/subst.rs b/compiler/rustc_middle/src/ty/subst.rs
index ca29dd7c08f..ad2898ccd67 100644
--- a/compiler/rustc_middle/src/ty/subst.rs
+++ b/compiler/rustc_middle/src/ty/subst.rs
@@ -82,7 +82,7 @@ impl<'tcx> GenericArgKind<'tcx> {
             GenericArgKind::Lifetime(lt) => {
                 // Ensure we can use the tag bits.
                 assert_eq!(mem::align_of_val(&*lt.0.0) & TAG_MASK, 0);
-                (REGION_TAG, lt.0.0 as *const ty::RegionKind as usize)
+                (REGION_TAG, lt.0.0 as *const ty::RegionKind<'tcx> as usize)
             }
             GenericArgKind::Type(ty) => {
                 // Ensure we can use the tag bits.
@@ -153,7 +153,7 @@ impl<'tcx> GenericArg<'tcx> {
         unsafe {
             match ptr & TAG_MASK {
                 REGION_TAG => GenericArgKind::Lifetime(ty::Region(Interned::new_unchecked(
-                    &*((ptr & !TAG_MASK) as *const ty::RegionKind),
+                    &*((ptr & !TAG_MASK) as *const ty::RegionKind<'tcx>),
                 ))),
                 TYPE_TAG => GenericArgKind::Type(Ty(Interned::new_unchecked(
                     &*((ptr & !TAG_MASK) as *const WithStableHash<ty::TyS<'tcx>>),
diff --git a/compiler/rustc_middle/src/ty/util.rs b/compiler/rustc_middle/src/ty/util.rs
index 33ef0283745..6c9f5a225ba 100644
--- a/compiler/rustc_middle/src/ty/util.rs
+++ b/compiler/rustc_middle/src/ty/util.rs
@@ -574,7 +574,7 @@ impl<'tcx> TyCtxt<'tcx> {
         self,
         closure_def_id: DefId,
         closure_substs: SubstsRef<'tcx>,
-        env_region: ty::RegionKind,
+        env_region: ty::RegionKind<'tcx>,
     ) -> Option<Ty<'tcx>> {
         let closure_ty = self.mk_closure(closure_def_id, closure_substs);
         let closure_kind_ty = closure_substs.as_closure().kind_ty();
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index 6380001b57c..cb1602816ae 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -42,6 +42,12 @@ pub trait Interner {
     type DelaySpanBugEmitted: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
     type PredicateKind: Clone + Debug + Hash + PartialEq + Eq;
     type AllocId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+
+    type EarlyBoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type BoundRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type FreeRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type RegionVid: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type PlaceholderRegion: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
 }
 
 pub trait InternAs<T: ?Sized, R> {
@@ -767,3 +773,85 @@ impl fmt::Display for InferTy {
         }
     }
 }
+
+rustc_index::newtype_index! {
+    /// "Universes" are used during type- and trait-checking in the
+    /// presence of `for<..>` binders to control what sets of names are
+    /// visible. Universes are arranged into a tree: the root universe
+    /// contains names that are always visible. Each child then adds a new
+    /// set of names that are visible, in addition to those of its parent.
+    /// We say that the child universe "extends" the parent universe with
+    /// new names.
+    ///
+    /// To make this more concrete, consider this program:
+    ///
+    /// ```ignore (illustrative)
+    /// struct Foo { }
+    /// fn bar<T>(x: T) {
+    ///   let y: for<'a> fn(&'a u8, Foo) = ...;
+    /// }
+    /// ```
+    ///
+    /// The struct name `Foo` is in the root universe U0. But the type
+    /// parameter `T`, introduced on `bar`, is in an extended universe U1
+    /// -- i.e., within `bar`, we can name both `T` and `Foo`, but outside
+    /// of `bar`, we cannot name `T`. Then, within the type of `y`, the
+    /// region `'a` is in a universe U2 that extends U1, because we can
+    /// name it inside the fn type but not outside.
+    ///
+    /// Universes are used to do type- and trait-checking around these
+    /// "forall" binders (also called **universal quantification**). The
+    /// idea is that when, in the body of `bar`, we refer to `T` as a
+    /// type, we aren't referring to any type in particular, but rather a
+    /// kind of "fresh" type that is distinct from all other types we have
+    /// actually declared. This is called a **placeholder** type, and we
+    /// use universes to talk about this. In other words, a type name in
+    /// universe 0 always corresponds to some "ground" type that the user
+    /// declared, but a type name in a non-zero universe is a placeholder
+    /// type -- an idealized representative of "types in general" that we
+    /// use for checking generic functions.
+    pub struct UniverseIndex {
+        DEBUG_FORMAT = "U{}",
+    }
+}
+
+impl UniverseIndex {
+    pub const ROOT: UniverseIndex = UniverseIndex::from_u32(0);
+
+    /// Returns the "next" universe index in order -- this new index
+    /// is considered to extend all previous universes. This
+    /// corresponds to entering a `forall` quantifier. So, for
+    /// example, suppose we have this type in universe `U`:
+    ///
+    /// ```ignore (illustrative)
+    /// for<'a> fn(&'a u32)
+    /// ```
+    ///
+    /// Once we "enter" into this `for<'a>` quantifier, we are in a
+    /// new universe that extends `U` -- in this new universe, we can
+    /// name the region `'a`, but that region was not nameable from
+    /// `U` because it was not in scope there.
+    pub fn next_universe(self) -> UniverseIndex {
+        UniverseIndex::from_u32(self.private.checked_add(1).unwrap())
+    }
+
+    /// Returns `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` (`self >= other`).
+    pub fn can_name(self, other: UniverseIndex) -> bool {
+        self.private >= other.private
+    }
+
+    /// Returns `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
+    }
+}
+
+impl<CTX> HashStable<CTX> for UniverseIndex {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        self.private.hash_stable(ctx, hasher);
+    }
+}
diff --git a/compiler/rustc_type_ir/src/sty.rs b/compiler/rustc_type_ir/src/sty.rs
index 94072184399..5cd2901324a 100644
--- a/compiler/rustc_type_ir/src/sty.rs
+++ b/compiler/rustc_type_ir/src/sty.rs
@@ -10,7 +10,9 @@ use crate::Interner;
 use crate::TyDecoder;
 use crate::TyEncoder;
 use crate::UintTy;
+use crate::UniverseIndex;
 
+use self::RegionKind::*;
 use self::TyKind::*;
 
 use rustc_data_structures::stable_hasher::HashStable;
@@ -20,8 +22,6 @@ use rustc_serialize::{Decodable, Decoder, Encodable};
 ///
 /// Types written by the user start out as `hir::TyKind` and get
 /// converted to this representation using `AstConv::ast_ty_to_ty`.
-///
-/// The `HashStable` implementation for this type is defined in `rustc_query_system::ich`.
 #[rustc_diagnostic_item = "IrTyKind"]
 pub enum TyKind<I: Interner> {
     /// The primitive boolean type. Written as `bool`.
@@ -202,7 +202,7 @@ impl<I: Interner> TyKind<I> {
 // This is manually implemented for `TyKind` because `std::mem::discriminant`
 // returns an opaque value that is `PartialEq` but not `PartialOrd`
 #[inline]
-const fn discriminant<I: Interner>(value: &TyKind<I>) -> usize {
+const fn tykind_discriminant<I: Interner>(value: &TyKind<I>) -> usize {
     match value {
         Bool => 0,
         Char => 1,
@@ -273,8 +273,8 @@ impl<I: Interner> Clone for TyKind<I> {
 impl<I: Interner> PartialEq for TyKind<I> {
     #[inline]
     fn eq(&self, other: &TyKind<I>) -> bool {
-        let __self_vi = discriminant(self);
-        let __arg_1_vi = discriminant(other);
+        let __self_vi = tykind_discriminant(self);
+        let __arg_1_vi = tykind_discriminant(other);
         if __self_vi == __arg_1_vi {
             match (&*self, &*other) {
                 (&Int(ref __self_0), &Int(ref __arg_1_0)) => __self_0 == __arg_1_0,
@@ -345,8 +345,8 @@ impl<I: Interner> PartialOrd for TyKind<I> {
 impl<I: Interner> Ord for TyKind<I> {
     #[inline]
     fn cmp(&self, other: &TyKind<I>) -> Ordering {
-        let __self_vi = discriminant(self);
-        let __arg_1_vi = discriminant(other);
+        let __self_vi = tykind_discriminant(self);
+        let __arg_1_vi = tykind_discriminant(other);
         if __self_vi == __arg_1_vi {
             match (&*self, &*other) {
                 (&Int(ref __self_0), &Int(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
@@ -444,109 +444,109 @@ impl<I: Interner> hash::Hash for TyKind<I> {
     fn hash<__H: hash::Hasher>(&self, state: &mut __H) -> () {
         match (&*self,) {
             (&Int(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Uint(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Float(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Adt(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&Foreign(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Array(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&Slice(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&RawPtr(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Ref(ref __self_0, ref __self_1, ref __self_2),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state);
                 hash::Hash::hash(__self_2, state)
             }
             (&FnDef(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&FnPtr(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Dynamic(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&Closure(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&Generator(ref __self_0, ref __self_1, ref __self_2),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state);
                 hash::Hash::hash(__self_2, state)
             }
             (&GeneratorWitness(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Tuple(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Projection(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Opaque(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&Param(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Bound(ref __self_0, ref __self_1),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state);
                 hash::Hash::hash(__self_1, state)
             }
             (&Placeholder(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Infer(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
             (&Error(ref __self_0),) => {
-                hash::Hash::hash(&discriminant(self), state);
+                hash::Hash::hash(&tykind_discriminant(self), state);
                 hash::Hash::hash(__self_0, state)
             }
-            _ => hash::Hash::hash(&discriminant(self), state),
+            _ => hash::Hash::hash(&tykind_discriminant(self), state),
         }
     }
 }
@@ -716,7 +716,7 @@ where
     I::AllocId: Encodable<E>,
 {
     fn encode(&self, e: &mut E) {
-        let disc = discriminant(self);
+        let disc = tykind_discriminant(self);
         match self {
             Bool => e.emit_enum_variant(disc, |_| {}),
             Char => e.emit_enum_variant(disc, |_| {}),
@@ -991,3 +991,439 @@ where
         }
     }
 }
+
+/// Representation of 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_const_eval::borrow_check`
+/// module for more information.
+///
+/// Note: operations are on the wrapper `Region` type, which is interned,
+/// rather than this type.
+///
+/// ## The Region lattice within a given function
+///
+/// In general, the region lattice looks like
+///
+/// ```text
+/// static ----------+-----...------+       (greatest)
+/// |                |              |
+/// early-bound and  |              |
+/// free 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.
+///
+/// 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
+///
+/// These are regions that are stored behind a binder and must be substituted
+/// with some concrete region before being used. There are two kind of
+/// bound regions: early-bound, which are bound in an item's `Generics`,
+/// and are substituted by an `InternalSubsts`, and late-bound, which are part of
+/// higher-ranked types (e.g., `for<'a> fn(&'a ())`), and are substituted by
+/// the likes of `liberate_late_bound_regions`. The distinction exists
+/// because higher-ranked lifetimes aren't supported in all places. See [1][2].
+///
+/// Unlike `Param`s, bound regions are not supposed to exist "in the wild"
+/// outside their binder, e.g., in types passed to type inference, and
+/// should first be substituted (by placeholder regions, free regions,
+/// or region variables).
+///
+/// ## Placeholder and Free Regions
+///
+/// One often wants to work with bound regions without knowing their precise
+/// identity. For example, when checking a function, the lifetime of a borrow
+/// can end up being assigned to some region parameter. In these cases,
+/// it must be ensured that bounds on the region can't be accidentally
+/// assumed without being checked.
+///
+/// To do this, we replace the bound regions with placeholder markers,
+/// which don't satisfy any relation not explicitly provided.
+///
+/// There are two kinds of placeholder regions in rustc: `ReFree` and
+/// `RePlaceholder`. When checking an item's body, `ReFree` is supposed
+/// to be used. These also support explicit bounds: both the internally-stored
+/// *scope*, which the region is assumed to outlive, as well as other
+/// relations stored in the `FreeRegionMap`. Note that these relations
+/// aren't checked when you `make_subregion` (or `eq_types`), only by
+/// `resolve_regions_and_report_errors`.
+///
+/// When working with higher-ranked types, some region relations aren't
+/// yet known, so you can't just call `resolve_regions_and_report_errors`.
+/// `RePlaceholder` is designed for this purpose. In these contexts,
+/// there's also the risk that some inference variable laying around will
+/// get unified with your placeholder region: if you want to check whether
+/// `for<'a> Foo<'_>: 'a`, and you substitute your bound region `'a`
+/// with a placeholder region `'%a`, the variable `'_` would just be
+/// instantiated to the placeholder region `'%a`, which is wrong because
+/// the inference variable is supposed to satisfy the relation
+/// *for every value of the placeholder region*. To ensure that doesn't
+/// happen, you can use `leak_check`. This is more clearly explained
+/// by the [rustc dev guide].
+///
+/// [1]: https://smallcultfollowing.com/babysteps/blog/2013/10/29/intermingled-parameter-lists/
+/// [2]: https://smallcultfollowing.com/babysteps/blog/2013/11/04/intermingled-parameter-lists/
+/// [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
+pub enum RegionKind<I: Interner> {
+    /// Region bound in a type or fn declaration which will be
+    /// substituted 'early' -- that is, at the same time when type
+    /// parameters are substituted.
+    ReEarlyBound(I::EarlyBoundRegion),
+
+    /// Region bound in a function scope, which will be substituted when the
+    /// function is called.
+    ReLateBound(DebruijnIndex, I::BoundRegion),
+
+    /// When checking a function body, the types of all arguments and so forth
+    /// that refer to bound region parameters are modified to refer to free
+    /// region parameters.
+    ReFree(I::FreeRegion),
+
+    /// Static data that has an "infinite" lifetime. Top in the region lattice.
+    ReStatic,
+
+    /// A region variable. Should not exist outside of type inference.
+    ReVar(I::RegionVid),
+
+    /// A placeholder region -- basically, the higher-ranked version of `ReFree`.
+    /// Should not exist outside of type inference.
+    RePlaceholder(I::PlaceholderRegion),
+
+    /// 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(UniverseIndex),
+
+    /// Erased region, used by trait selection, in MIR and during codegen.
+    ReErased,
+}
+
+// This is manually implemented for `RegionKind` because `std::mem::discriminant`
+// returns an opaque value that is `PartialEq` but not `PartialOrd`
+#[inline]
+const fn regionkind_discriminant<I: Interner>(value: &RegionKind<I>) -> usize {
+    match value {
+        ReEarlyBound(_) => 0,
+        ReLateBound(_, _) => 1,
+        ReFree(_) => 2,
+        ReStatic => 3,
+        ReVar(_) => 4,
+        RePlaceholder(_) => 5,
+        ReEmpty(_) => 6,
+        ReErased => 7,
+    }
+}
+
+// This is manually implemented because a derive would require `I: Copy`
+impl<I: Interner> Copy for RegionKind<I>
+where
+    I::EarlyBoundRegion: Copy,
+    I::BoundRegion: Copy,
+    I::FreeRegion: Copy,
+    I::RegionVid: Copy,
+    I::PlaceholderRegion: Copy,
+{
+}
+
+// This is manually implemented because a derive would require `I: Clone`
+impl<I: Interner> Clone for RegionKind<I> {
+    fn clone(&self) -> Self {
+        match self {
+            ReEarlyBound(a) => ReEarlyBound(a.clone()),
+            ReLateBound(a, b) => ReLateBound(a.clone(), b.clone()),
+            ReFree(a) => ReFree(a.clone()),
+            ReStatic => ReStatic,
+            ReVar(a) => ReVar(a.clone()),
+            RePlaceholder(a) => RePlaceholder(a.clone()),
+            ReEmpty(a) => ReEmpty(a.clone()),
+            ReErased => ReErased,
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: PartialEq`
+impl<I: Interner> PartialEq for RegionKind<I> {
+    #[inline]
+    fn eq(&self, other: &RegionKind<I>) -> bool {
+        let __self_vi = regionkind_discriminant(self);
+        let __arg_1_vi = regionkind_discriminant(other);
+        if __self_vi == __arg_1_vi {
+            match (&*self, &*other) {
+                (&ReEarlyBound(ref __self_0), &ReEarlyBound(ref __arg_1_0)) => {
+                    __self_0 == __arg_1_0
+                }
+                (
+                    &ReLateBound(ref __self_0, ref __self_1),
+                    &ReLateBound(ref __arg_1_0, ref __arg_1_1),
+                ) => __self_0 == __arg_1_0 && __self_1 == __arg_1_1,
+                (&ReFree(ref __self_0), &ReFree(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&ReStatic, &ReStatic) => true,
+                (&ReVar(ref __self_0), &ReVar(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&RePlaceholder(ref __self_0), &RePlaceholder(ref __arg_1_0)) => {
+                    __self_0 == __arg_1_0
+                }
+                (&ReEmpty(ref __self_0), &ReEmpty(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&ReErased, &ReErased) => true,
+                _ => true,
+            }
+        } else {
+            false
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Eq`
+impl<I: Interner> Eq for RegionKind<I> {}
+
+// This is manually implemented because a derive would require `I: PartialOrd`
+impl<I: Interner> PartialOrd for RegionKind<I> {
+    #[inline]
+    fn partial_cmp(&self, other: &RegionKind<I>) -> Option<Ordering> {
+        Some(Ord::cmp(self, other))
+    }
+}
+
+// This is manually implemented because a derive would require `I: Ord`
+impl<I: Interner> Ord for RegionKind<I> {
+    #[inline]
+    fn cmp(&self, other: &RegionKind<I>) -> Ordering {
+        let __self_vi = regionkind_discriminant(self);
+        let __arg_1_vi = regionkind_discriminant(other);
+        if __self_vi == __arg_1_vi {
+            match (&*self, &*other) {
+                (&ReEarlyBound(ref __self_0), &ReEarlyBound(ref __arg_1_0)) => {
+                    Ord::cmp(__self_0, __arg_1_0)
+                }
+                (
+                    &ReLateBound(ref __self_0, ref __self_1),
+                    &ReLateBound(ref __arg_1_0, ref __arg_1_1),
+                ) => match Ord::cmp(__self_0, __arg_1_0) {
+                    Ordering::Equal => Ord::cmp(__self_1, __arg_1_1),
+                    cmp => cmp,
+                },
+                (&ReFree(ref __self_0), &ReFree(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&ReStatic, &ReStatic) => Ordering::Equal,
+                (&ReVar(ref __self_0), &ReVar(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&RePlaceholder(ref __self_0), &RePlaceholder(ref __arg_1_0)) => {
+                    Ord::cmp(__self_0, __arg_1_0)
+                }
+                (&ReEmpty(ref __self_0), &ReEmpty(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&ReErased, &ReErased) => Ordering::Equal,
+                _ => Ordering::Equal,
+            }
+        } else {
+            Ord::cmp(&__self_vi, &__arg_1_vi)
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Hash`
+impl<I: Interner> hash::Hash for RegionKind<I> {
+    fn hash<__H: hash::Hasher>(&self, state: &mut __H) -> () {
+        match (&*self,) {
+            (&ReEarlyBound(ref __self_0),) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&ReLateBound(ref __self_0, ref __self_1),) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state);
+                hash::Hash::hash(__self_1, state)
+            }
+            (&ReFree(ref __self_0),) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&ReStatic,) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+            }
+            (&ReVar(ref __self_0),) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&RePlaceholder(ref __self_0),) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&ReEmpty(ref __self_0),) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&ReErased,) => {
+                hash::Hash::hash(&regionkind_discriminant(self), state);
+            }
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Debug`
+impl<I: Interner> fmt::Debug for RegionKind<I> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            ReEarlyBound(ref data) => write!(f, "ReEarlyBound({:?})", data),
+
+            ReLateBound(binder_id, ref bound_region) => {
+                write!(f, "ReLateBound({:?}, {:?})", binder_id, bound_region)
+            }
+
+            ReFree(ref fr) => fr.fmt(f),
+
+            ReStatic => write!(f, "ReStatic"),
+
+            ReVar(ref vid) => vid.fmt(f),
+
+            RePlaceholder(placeholder) => write!(f, "RePlaceholder({:?})", placeholder),
+
+            ReEmpty(ui) => write!(f, "ReEmpty({:?})", ui),
+
+            ReErased => write!(f, "ReErased"),
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Encodable`
+impl<I: Interner, E: TyEncoder> Encodable<E> for RegionKind<I>
+where
+    I::EarlyBoundRegion: Encodable<E>,
+    I::BoundRegion: Encodable<E>,
+    I::FreeRegion: Encodable<E>,
+    I::RegionVid: Encodable<E>,
+    I::PlaceholderRegion: Encodable<E>,
+{
+    fn encode(&self, e: &mut E) {
+        let disc = regionkind_discriminant(self);
+        match self {
+            ReEarlyBound(a) => e.emit_enum_variant(disc, |e| {
+                a.encode(e);
+            }),
+            ReLateBound(a, b) => e.emit_enum_variant(disc, |e| {
+                a.encode(e);
+                b.encode(e);
+            }),
+            ReFree(a) => e.emit_enum_variant(disc, |e| {
+                a.encode(e);
+            }),
+            ReStatic => e.emit_enum_variant(disc, |_| {}),
+            ReVar(a) => e.emit_enum_variant(disc, |e| {
+                a.encode(e);
+            }),
+            RePlaceholder(a) => e.emit_enum_variant(disc, |e| {
+                a.encode(e);
+            }),
+            ReEmpty(a) => e.emit_enum_variant(disc, |e| {
+                a.encode(e);
+            }),
+            ReErased => e.emit_enum_variant(disc, |_| {}),
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Decodable`
+impl<I: Interner, D: TyDecoder<I = I>> Decodable<D> for RegionKind<I>
+where
+    I::EarlyBoundRegion: Decodable<D>,
+    I::BoundRegion: Decodable<D>,
+    I::FreeRegion: Decodable<D>,
+    I::RegionVid: Decodable<D>,
+    I::PlaceholderRegion: Decodable<D>,
+{
+    fn decode(d: &mut D) -> Self {
+        match Decoder::read_usize(d) {
+            0 => ReEarlyBound(Decodable::decode(d)),
+            1 => ReLateBound(Decodable::decode(d), Decodable::decode(d)),
+            2 => ReFree(Decodable::decode(d)),
+            3 => ReStatic,
+            4 => ReVar(Decodable::decode(d)),
+            5 => RePlaceholder(Decodable::decode(d)),
+            6 => ReEmpty(Decodable::decode(d)),
+            7 => ReErased,
+            _ => panic!(
+                "{}",
+                format!(
+                    "invalid enum variant tag while decoding `{}`, expected 0..{}",
+                    "RegionKind", 8,
+                )
+            ),
+        }
+    }
+}
+
+// This is not a derived impl because a derive would require `I: HashStable`
+impl<CTX, I: Interner> HashStable<CTX> for RegionKind<I>
+where
+    I::EarlyBoundRegion: HashStable<CTX>,
+    I::BoundRegion: HashStable<CTX>,
+    I::FreeRegion: HashStable<CTX>,
+    I::RegionVid: HashStable<CTX>,
+    I::PlaceholderRegion: HashStable<CTX>,
+{
+    #[inline]
+    fn hash_stable(
+        &self,
+        hcx: &mut CTX,
+        hasher: &mut rustc_data_structures::stable_hasher::StableHasher,
+    ) {
+        std::mem::discriminant(self).hash_stable(hcx, hasher);
+        match self {
+            ReErased | ReStatic => {
+                // No variant fields to hash for these ...
+            }
+            ReEmpty(universe) => {
+                universe.hash_stable(hcx, hasher);
+            }
+            ReLateBound(db, br) => {
+                db.hash_stable(hcx, hasher);
+                br.hash_stable(hcx, hasher);
+            }
+            ReEarlyBound(eb) => {
+                eb.hash_stable(hcx, hasher);
+            }
+            ReFree(ref free_region) => {
+                free_region.hash_stable(hcx, hasher);
+            }
+            RePlaceholder(p) => {
+                p.hash_stable(hcx, hasher);
+            }
+            ReVar(reg) => {
+                reg.hash_stable(hcx, hasher);
+            }
+        }
+    }
+}