Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 2264 insertions, 0 deletions

diff --git a/compiler/rustc_type_ir/Cargo.toml b/compiler/rustc_type_ir/Cargo.toml
new file mode 100644
index 000000000..5aa3cf017
--- /dev/null
+++ b/compiler/rustc_type_ir/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "rustc_type_ir"
+version = "0.0.0"
+edition = "2021"
+
+[lib]
+doctest = false
+
+[dependencies]
+bitflags = "1.2.1"
+rustc_index = { path = "../rustc_index" }
+rustc_serialize = { path = "../rustc_serialize" }
+rustc_data_structures = { path = "../rustc_data_structures" }
+rustc_macros = { path = "../rustc_macros" }
+smallvec = { version = "1.8.1", features = ["union", "may_dangle"] }
diff --git a/compiler/rustc_type_ir/src/codec.rs b/compiler/rustc_type_ir/src/codec.rs
new file mode 100644
index 000000000..ee249050c
--- /dev/null
+++ b/compiler/rustc_type_ir/src/codec.rs
@@ -0,0 +1,64 @@
+use crate::Interner;
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_serialize::{Decoder, Encoder};
+
+/// The shorthand encoding uses an enum's variant index `usize`
+/// and is offset by this value so it never matches a real variant.
+/// This offset is also chosen so that the first byte is never < 0x80.
+pub const SHORTHAND_OFFSET: usize = 0x80;
+
+/// Trait for decoding to a reference.
+///
+/// This is a separate trait from `Decodable` so that we can implement it for
+/// upstream types, such as `FxHashSet`.
+///
+/// The `TyDecodable` derive macro will use this trait for fields that are
+/// references (and don't use a type alias to hide that).
+///
+/// `Decodable` can still be implemented in cases where `Decodable` is required
+/// by a trait bound.
+pub trait RefDecodable<'tcx, D: TyDecoder> {
+    fn decode(d: &mut D) -> &'tcx Self;
+}
+
+pub trait TyEncoder: Encoder {
+    type I: Interner;
+    const CLEAR_CROSS_CRATE: bool;
+
+    fn position(&self) -> usize;
+    fn type_shorthands(&mut self) -> &mut FxHashMap<<Self::I as Interner>::Ty, usize>;
+    fn predicate_shorthands(
+        &mut self,
+    ) -> &mut FxHashMap<<Self::I as Interner>::PredicateKind, usize>;
+    fn encode_alloc_id(&mut self, alloc_id: &<Self::I as Interner>::AllocId);
+}
+
+pub trait TyDecoder: Decoder {
+    type I: Interner;
+    const CLEAR_CROSS_CRATE: bool;
+
+    fn interner(&self) -> Self::I;
+
+    fn peek_byte(&self) -> u8;
+
+    fn position(&self) -> usize;
+
+    fn cached_ty_for_shorthand<F>(
+        &mut self,
+        shorthand: usize,
+        or_insert_with: F,
+    ) -> <Self::I as Interner>::Ty
+    where
+        F: FnOnce(&mut Self) -> <Self::I as Interner>::Ty;
+
+    fn with_position<F, R>(&mut self, pos: usize, f: F) -> R
+    where
+        F: FnOnce(&mut Self) -> R;
+
+    fn positioned_at_shorthand(&self) -> bool {
+        (self.peek_byte() & (SHORTHAND_OFFSET as u8)) != 0
+    }
+
+    fn decode_alloc_id(&mut self) -> <Self::I as Interner>::AllocId;
+}
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
new file mode 100644
index 000000000..791e9e0f5
--- /dev/null
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -0,0 +1,856 @@
+#![feature(fmt_helpers_for_derive)]
+#![feature(min_specialization)]
+#![feature(rustc_attrs)]
+
+#[macro_use]
+extern crate bitflags;
+#[macro_use]
+extern crate rustc_macros;
+
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_data_structures::unify::{EqUnifyValue, UnifyKey};
+use smallvec::SmallVec;
+use std::fmt;
+use std::fmt::Debug;
+use std::hash::Hash;
+use std::mem::discriminant;
+
+pub mod codec;
+pub mod sty;
+
+pub use codec::*;
+pub use sty::*;
+
+pub trait Interner {
+    type AdtDef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type SubstsRef: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type DefId: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type Ty: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type Const: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type Region: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type TypeAndMut: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type Mutability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type Movability: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type PolyFnSig: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type ListBinderExistentialPredicate: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type BinderListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type ListTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type ProjectionTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type ParamTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type BoundTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type PlaceholderType: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    type InferTy: Clone + Debug + Hash + PartialEq + Eq + PartialOrd + Ord;
+    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> {
+    type Output;
+    fn intern_with<F>(self, f: F) -> Self::Output
+    where
+        F: FnOnce(&T) -> R;
+}
+
+impl<I, T, R, E> InternAs<[T], R> for I
+where
+    E: InternIteratorElement<T, R>,
+    I: Iterator<Item = E>,
+{
+    type Output = E::Output;
+    fn intern_with<F>(self, f: F) -> Self::Output
+    where
+        F: FnOnce(&[T]) -> R,
+    {
+        E::intern_with(self, f)
+    }
+}
+
+pub trait InternIteratorElement<T, R>: Sized {
+    type Output;
+    fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output;
+}
+
+impl<T, R> InternIteratorElement<T, R> for T {
+    type Output = R;
+    fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(
+        mut iter: I,
+        f: F,
+    ) -> Self::Output {
+        // This code is hot enough that it's worth specializing for the most
+        // common length lists, to avoid the overhead of `SmallVec` creation.
+        // Lengths 0, 1, and 2 typically account for ~95% of cases. If
+        // `size_hint` is incorrect a panic will occur via an `unwrap` or an
+        // `assert`.
+        match iter.size_hint() {
+            (0, Some(0)) => {
+                assert!(iter.next().is_none());
+                f(&[])
+            }
+            (1, Some(1)) => {
+                let t0 = iter.next().unwrap();
+                assert!(iter.next().is_none());
+                f(&[t0])
+            }
+            (2, Some(2)) => {
+                let t0 = iter.next().unwrap();
+                let t1 = iter.next().unwrap();
+                assert!(iter.next().is_none());
+                f(&[t0, t1])
+            }
+            _ => f(&iter.collect::<SmallVec<[_; 8]>>()),
+        }
+    }
+}
+
+impl<'a, T, R> InternIteratorElement<T, R> for &'a T
+where
+    T: Clone + 'a,
+{
+    type Output = R;
+    fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(iter: I, f: F) -> Self::Output {
+        // This code isn't hot.
+        f(&iter.cloned().collect::<SmallVec<[_; 8]>>())
+    }
+}
+
+impl<T, R, E> InternIteratorElement<T, R> for Result<T, E> {
+    type Output = Result<R, E>;
+    fn intern_with<I: Iterator<Item = Self>, F: FnOnce(&[T]) -> R>(
+        mut iter: I,
+        f: F,
+    ) -> Self::Output {
+        // This code is hot enough that it's worth specializing for the most
+        // common length lists, to avoid the overhead of `SmallVec` creation.
+        // Lengths 0, 1, and 2 typically account for ~95% of cases. If
+        // `size_hint` is incorrect a panic will occur via an `unwrap` or an
+        // `assert`, unless a failure happens first, in which case the result
+        // will be an error anyway.
+        Ok(match iter.size_hint() {
+            (0, Some(0)) => {
+                assert!(iter.next().is_none());
+                f(&[])
+            }
+            (1, Some(1)) => {
+                let t0 = iter.next().unwrap()?;
+                assert!(iter.next().is_none());
+                f(&[t0])
+            }
+            (2, Some(2)) => {
+                let t0 = iter.next().unwrap()?;
+                let t1 = iter.next().unwrap()?;
+                assert!(iter.next().is_none());
+                f(&[t0, t1])
+            }
+            _ => f(&iter.collect::<Result<SmallVec<[_; 8]>, _>>()?),
+        })
+    }
+}
+
+bitflags! {
+    /// Flags that we track on types. These flags are propagated upwards
+    /// through the type during type construction, so that we can quickly check
+    /// whether the type has various kinds of types in it without recursing
+    /// over the type itself.
+    pub struct TypeFlags: u32 {
+        // Does this have parameters? Used to determine whether substitution is
+        // required.
+        /// Does this have `Param`?
+        const HAS_TY_PARAM                = 1 << 0;
+        /// Does this have `ReEarlyBound`?
+        const HAS_RE_PARAM                = 1 << 1;
+        /// Does this have `ConstKind::Param`?
+        const HAS_CT_PARAM                = 1 << 2;
+
+        const NEEDS_SUBST                 = TypeFlags::HAS_TY_PARAM.bits
+                                          | TypeFlags::HAS_RE_PARAM.bits
+                                          | TypeFlags::HAS_CT_PARAM.bits;
+
+        /// Does this have `Infer`?
+        const HAS_TY_INFER                = 1 << 3;
+        /// Does this have `ReVar`?
+        const HAS_RE_INFER                = 1 << 4;
+        /// Does this have `ConstKind::Infer`?
+        const HAS_CT_INFER                = 1 << 5;
+
+        /// Does this have inference variables? Used to determine whether
+        /// inference is required.
+        const NEEDS_INFER                 = TypeFlags::HAS_TY_INFER.bits
+                                          | TypeFlags::HAS_RE_INFER.bits
+                                          | TypeFlags::HAS_CT_INFER.bits;
+
+        /// Does this have `Placeholder`?
+        const HAS_TY_PLACEHOLDER          = 1 << 6;
+        /// Does this have `RePlaceholder`?
+        const HAS_RE_PLACEHOLDER          = 1 << 7;
+        /// Does this have `ConstKind::Placeholder`?
+        const HAS_CT_PLACEHOLDER          = 1 << 8;
+
+        /// `true` if there are "names" of regions and so forth
+        /// that are local to a particular fn/inferctxt
+        const HAS_FREE_LOCAL_REGIONS      = 1 << 9;
+
+        /// `true` if there are "names" of types and regions and so forth
+        /// that are local to a particular fn
+        const HAS_FREE_LOCAL_NAMES        = TypeFlags::HAS_TY_PARAM.bits
+                                          | TypeFlags::HAS_CT_PARAM.bits
+                                          | TypeFlags::HAS_TY_INFER.bits
+                                          | TypeFlags::HAS_CT_INFER.bits
+                                          | TypeFlags::HAS_TY_PLACEHOLDER.bits
+                                          | TypeFlags::HAS_CT_PLACEHOLDER.bits
+                                          // We consider 'freshened' types and constants
+                                          // to depend on a particular fn.
+                                          // The freshening process throws away information,
+                                          // which can make things unsuitable for use in a global
+                                          // cache. Note that there is no 'fresh lifetime' flag -
+                                          // freshening replaces all lifetimes with `ReErased`,
+                                          // which is different from how types/const are freshened.
+                                          | TypeFlags::HAS_TY_FRESH.bits
+                                          | TypeFlags::HAS_CT_FRESH.bits
+                                          | TypeFlags::HAS_FREE_LOCAL_REGIONS.bits;
+
+        /// Does this have `Projection`?
+        const HAS_TY_PROJECTION           = 1 << 10;
+        /// Does this have `Opaque`?
+        const HAS_TY_OPAQUE               = 1 << 11;
+        /// Does this have `ConstKind::Unevaluated`?
+        const HAS_CT_PROJECTION           = 1 << 12;
+
+        /// Could this type be normalized further?
+        const HAS_PROJECTION              = TypeFlags::HAS_TY_PROJECTION.bits
+                                          | TypeFlags::HAS_TY_OPAQUE.bits
+                                          | TypeFlags::HAS_CT_PROJECTION.bits;
+
+        /// Is an error type/const reachable?
+        const HAS_ERROR                   = 1 << 13;
+
+        /// Does this have any region that "appears free" in the type?
+        /// Basically anything but `ReLateBound` and `ReErased`.
+        const HAS_FREE_REGIONS            = 1 << 14;
+
+        /// Does this have any `ReLateBound` regions? Used to check
+        /// if a global bound is safe to evaluate.
+        const HAS_RE_LATE_BOUND           = 1 << 15;
+
+        /// Does this have any `ReErased` regions?
+        const HAS_RE_ERASED               = 1 << 16;
+
+        /// Does this value have parameters/placeholders/inference variables which could be
+        /// replaced later, in a way that would change the results of `impl` specialization?
+        const STILL_FURTHER_SPECIALIZABLE = 1 << 17;
+
+        /// Does this value have `InferTy::FreshTy/FreshIntTy/FreshFloatTy`?
+        const HAS_TY_FRESH                = 1 << 18;
+
+        /// Does this value have `InferConst::Fresh`?
+        const HAS_CT_FRESH                = 1 << 19;
+    }
+}
+
+rustc_index::newtype_index! {
+    /// A [De Bruijn index][dbi] is a standard means of representing
+    /// regions (and perhaps later types) in a higher-ranked setting. In
+    /// particular, imagine a type like this:
+    /// ```ignore (illustrative)
+    ///    for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
+    /// // ^          ^            |          |           |
+    /// // |          |            |          |           |
+    /// // |          +------------+ 0        |           |
+    /// // |                                  |           |
+    /// // +----------------------------------+ 1         |
+    /// // |                                              |
+    /// // +----------------------------------------------+ 0
+    /// ```
+    /// In this type, there are two binders (the outer fn and the inner
+    /// fn). We need to be able to determine, for any given region, which
+    /// fn type it is bound by, the inner or the outer one. There are
+    /// various ways you can do this, but a De Bruijn index is one of the
+    /// more convenient and has some nice properties. The basic idea is to
+    /// count the number of binders, inside out. Some examples should help
+    /// clarify what I mean.
+    ///
+    /// Let's start with the reference type `&'b isize` that is the first
+    /// argument to the inner function. This region `'b` is assigned a De
+    /// Bruijn index of 0, meaning "the innermost binder" (in this case, a
+    /// fn). The region `'a` that appears in the second argument type (`&'a
+    /// isize`) would then be assigned a De Bruijn index of 1, meaning "the
+    /// second-innermost binder". (These indices are written on the arrows
+    /// in the diagram).
+    ///
+    /// What is interesting is that De Bruijn index attached to a particular
+    /// variable will vary depending on where it appears. For example,
+    /// the final type `&'a char` also refers to the region `'a` declared on
+    /// the outermost fn. But this time, this reference is not nested within
+    /// any other binders (i.e., it is not an argument to the inner fn, but
+    /// rather the outer one). Therefore, in this case, it is assigned a
+    /// De Bruijn index of 0, because the innermost binder in that location
+    /// is the outer fn.
+    ///
+    /// [dbi]: https://en.wikipedia.org/wiki/De_Bruijn_index
+    pub struct DebruijnIndex {
+        DEBUG_FORMAT = "DebruijnIndex({})",
+        const INNERMOST = 0,
+    }
+}
+
+impl DebruijnIndex {
+    /// Returns the resulting index when this value is moved into
+    /// `amount` number of new binders. So, e.g., if you had
+    ///
+    ///    for<'a> fn(&'a x)
+    ///
+    /// and you wanted to change it to
+    ///
+    ///    for<'a> fn(for<'b> fn(&'a x))
+    ///
+    /// you would need to shift the index for `'a` into a new binder.
+    #[inline]
+    #[must_use]
+    pub fn shifted_in(self, amount: u32) -> DebruijnIndex {
+        DebruijnIndex::from_u32(self.as_u32() + amount)
+    }
+
+    /// Update this index in place by shifting it "in" through
+    /// `amount` number of binders.
+    #[inline]
+    pub fn shift_in(&mut self, amount: u32) {
+        *self = self.shifted_in(amount);
+    }
+
+    /// Returns the resulting index when this value is moved out from
+    /// `amount` number of new binders.
+    #[inline]
+    #[must_use]
+    pub fn shifted_out(self, amount: u32) -> DebruijnIndex {
+        DebruijnIndex::from_u32(self.as_u32() - amount)
+    }
+
+    /// Update in place by shifting out from `amount` binders.
+    #[inline]
+    pub fn shift_out(&mut self, amount: u32) {
+        *self = self.shifted_out(amount);
+    }
+
+    /// Adjusts any De Bruijn indices so as to make `to_binder` the
+    /// innermost binder. That is, if we have something bound at `to_binder`,
+    /// it will now be bound at INNERMOST. This is an appropriate thing to do
+    /// when moving a region out from inside binders:
+    ///
+    /// ```ignore (illustrative)
+    ///             for<'a>   fn(for<'b>   for<'c>   fn(&'a u32), _)
+    /// // Binder:  D3           D2        D1            ^^
+    /// ```
+    ///
+    /// Here, the region `'a` would have the De Bruijn index D3,
+    /// because it is the bound 3 binders out. However, if we wanted
+    /// to refer to that region `'a` in the second argument (the `_`),
+    /// those two binders would not be in scope. In that case, we
+    /// might invoke `shift_out_to_binder(D3)`. This would adjust the
+    /// De Bruijn index of `'a` to D1 (the innermost binder).
+    ///
+    /// If we invoke `shift_out_to_binder` and the region is in fact
+    /// bound by one of the binders we are shifting out of, that is an
+    /// error (and should fail an assertion failure).
+    #[inline]
+    pub fn shifted_out_to_binder(self, to_binder: DebruijnIndex) -> Self {
+        self.shifted_out(to_binder.as_u32() - INNERMOST.as_u32())
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
+#[derive(Encodable, Decodable)]
+pub enum IntTy {
+    Isize,
+    I8,
+    I16,
+    I32,
+    I64,
+    I128,
+}
+
+impl IntTy {
+    pub fn name_str(&self) -> &'static str {
+        match *self {
+            IntTy::Isize => "isize",
+            IntTy::I8 => "i8",
+            IntTy::I16 => "i16",
+            IntTy::I32 => "i32",
+            IntTy::I64 => "i64",
+            IntTy::I128 => "i128",
+        }
+    }
+
+    pub fn bit_width(&self) -> Option<u64> {
+        Some(match *self {
+            IntTy::Isize => return None,
+            IntTy::I8 => 8,
+            IntTy::I16 => 16,
+            IntTy::I32 => 32,
+            IntTy::I64 => 64,
+            IntTy::I128 => 128,
+        })
+    }
+
+    pub fn normalize(&self, target_width: u32) -> Self {
+        match self {
+            IntTy::Isize => match target_width {
+                16 => IntTy::I16,
+                32 => IntTy::I32,
+                64 => IntTy::I64,
+                _ => unreachable!(),
+            },
+            _ => *self,
+        }
+    }
+}
+
+#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Copy, Debug)]
+#[derive(Encodable, Decodable)]
+pub enum UintTy {
+    Usize,
+    U8,
+    U16,
+    U32,
+    U64,
+    U128,
+}
+
+impl UintTy {
+    pub fn name_str(&self) -> &'static str {
+        match *self {
+            UintTy::Usize => "usize",
+            UintTy::U8 => "u8",
+            UintTy::U16 => "u16",
+            UintTy::U32 => "u32",
+            UintTy::U64 => "u64",
+            UintTy::U128 => "u128",
+        }
+    }
+
+    pub fn bit_width(&self) -> Option<u64> {
+        Some(match *self {
+            UintTy::Usize => return None,
+            UintTy::U8 => 8,
+            UintTy::U16 => 16,
+            UintTy::U32 => 32,
+            UintTy::U64 => 64,
+            UintTy::U128 => 128,
+        })
+    }
+
+    pub fn normalize(&self, target_width: u32) -> Self {
+        match self {
+            UintTy::Usize => match target_width {
+                16 => UintTy::U16,
+                32 => UintTy::U32,
+                64 => UintTy::U64,
+                _ => unreachable!(),
+            },
+            _ => *self,
+        }
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
+#[derive(Encodable, Decodable)]
+pub enum FloatTy {
+    F32,
+    F64,
+}
+
+impl FloatTy {
+    pub fn name_str(self) -> &'static str {
+        match self {
+            FloatTy::F32 => "f32",
+            FloatTy::F64 => "f64",
+        }
+    }
+
+    pub fn bit_width(self) -> u64 {
+        match self {
+            FloatTy::F32 => 32,
+            FloatTy::F64 => 64,
+        }
+    }
+}
+
+#[derive(Clone, Copy, PartialEq, Eq)]
+pub enum IntVarValue {
+    IntType(IntTy),
+    UintType(UintTy),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq)]
+pub struct FloatVarValue(pub FloatTy);
+
+rustc_index::newtype_index! {
+    /// A **ty**pe **v**ariable **ID**.
+    pub struct TyVid {
+        DEBUG_FORMAT = "_#{}t"
+    }
+}
+
+/// An **int**egral (`u32`, `i32`, `usize`, etc.) type **v**ariable **ID**.
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
+pub struct IntVid {
+    pub index: u32,
+}
+
+/// An **float**ing-point (`f32` or `f64`) type **v**ariable **ID**.
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
+pub struct FloatVid {
+    pub index: u32,
+}
+
+/// A placeholder for a type that hasn't been inferred yet.
+///
+/// E.g., if we have an empty array (`[]`), then we create a fresh
+/// type variable for the element type since we won't know until it's
+/// used what the element type is supposed to be.
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
+pub enum InferTy {
+    /// A type variable.
+    TyVar(TyVid),
+    /// An integral type variable (`{integer}`).
+    ///
+    /// These are created when the compiler sees an integer literal like
+    /// `1` that could be several different types (`u8`, `i32`, `u32`, etc.).
+    /// We don't know until it's used what type it's supposed to be, so
+    /// we create a fresh type variable.
+    IntVar(IntVid),
+    /// A floating-point type variable (`{float}`).
+    ///
+    /// These are created when the compiler sees an float literal like
+    /// `1.0` that could be either an `f32` or an `f64`.
+    /// We don't know until it's used what type it's supposed to be, so
+    /// we create a fresh type variable.
+    FloatVar(FloatVid),
+
+    /// A [`FreshTy`][Self::FreshTy] is one that is generated as a replacement
+    /// for an unbound type variable. This is convenient for caching etc. See
+    /// `rustc_infer::infer::freshen` for more details.
+    ///
+    /// Compare with [`TyVar`][Self::TyVar].
+    FreshTy(u32),
+    /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`IntVar`][Self::IntVar].
+    FreshIntTy(u32),
+    /// Like [`FreshTy`][Self::FreshTy], but as a replacement for [`FloatVar`][Self::FloatVar].
+    FreshFloatTy(u32),
+}
+
+/// Raw `TyVid` are used as the unification key for `sub_relations`;
+/// they carry no values.
+impl UnifyKey for TyVid {
+    type Value = ();
+    #[inline]
+    fn index(&self) -> u32 {
+        self.as_u32()
+    }
+    #[inline]
+    fn from_index(i: u32) -> TyVid {
+        TyVid::from_u32(i)
+    }
+    fn tag() -> &'static str {
+        "TyVid"
+    }
+}
+
+impl EqUnifyValue for IntVarValue {}
+
+impl UnifyKey for IntVid {
+    type Value = Option<IntVarValue>;
+    #[inline] // make this function eligible for inlining - it is quite hot.
+    fn index(&self) -> u32 {
+        self.index
+    }
+    #[inline]
+    fn from_index(i: u32) -> IntVid {
+        IntVid { index: i }
+    }
+    fn tag() -> &'static str {
+        "IntVid"
+    }
+}
+
+impl EqUnifyValue for FloatVarValue {}
+
+impl UnifyKey for FloatVid {
+    type Value = Option<FloatVarValue>;
+    #[inline]
+    fn index(&self) -> u32 {
+        self.index
+    }
+    #[inline]
+    fn from_index(i: u32) -> FloatVid {
+        FloatVid { index: i }
+    }
+    fn tag() -> &'static str {
+        "FloatVid"
+    }
+}
+
+#[derive(Copy, Clone, PartialEq, Decodable, Encodable, Hash)]
+#[rustc_pass_by_value]
+pub enum Variance {
+    Covariant,     // T<A> <: T<B> iff A <: B -- e.g., function return type
+    Invariant,     // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
+    Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
+    Bivariant,     // T<A> <: T<B>            -- e.g., unused type parameter
+}
+
+impl Variance {
+    /// `a.xform(b)` combines the variance of a context with the
+    /// variance of a type with the following meaning. If we are in a
+    /// context with variance `a`, and we encounter a type argument in
+    /// a position with variance `b`, then `a.xform(b)` is the new
+    /// variance with which the argument appears.
+    ///
+    /// Example 1:
+    /// ```ignore (illustrative)
+    /// *mut Vec<i32>
+    /// ```
+    /// Here, the "ambient" variance starts as covariant. `*mut T` is
+    /// invariant with respect to `T`, so the variance in which the
+    /// `Vec<i32>` appears is `Covariant.xform(Invariant)`, which
+    /// yields `Invariant`. Now, the type `Vec<T>` is covariant with
+    /// respect to its type argument `T`, and hence the variance of
+    /// the `i32` here is `Invariant.xform(Covariant)`, which results
+    /// (again) in `Invariant`.
+    ///
+    /// Example 2:
+    /// ```ignore (illustrative)
+    /// fn(*const Vec<i32>, *mut Vec<i32)
+    /// ```
+    /// The ambient variance is covariant. A `fn` type is
+    /// contravariant with respect to its parameters, so the variance
+    /// within which both pointer types appear is
+    /// `Covariant.xform(Contravariant)`, or `Contravariant`. `*const
+    /// T` is covariant with respect to `T`, so the variance within
+    /// which the first `Vec<i32>` appears is
+    /// `Contravariant.xform(Covariant)` or `Contravariant`. The same
+    /// is true for its `i32` argument. In the `*mut T` case, the
+    /// variance of `Vec<i32>` is `Contravariant.xform(Invariant)`,
+    /// and hence the outermost type is `Invariant` with respect to
+    /// `Vec<i32>` (and its `i32` argument).
+    ///
+    /// Source: Figure 1 of "Taming the Wildcards:
+    /// Combining Definition- and Use-Site Variance" published in PLDI'11.
+    pub fn xform(self, v: Variance) -> Variance {
+        match (self, v) {
+            // Figure 1, column 1.
+            (Variance::Covariant, Variance::Covariant) => Variance::Covariant,
+            (Variance::Covariant, Variance::Contravariant) => Variance::Contravariant,
+            (Variance::Covariant, Variance::Invariant) => Variance::Invariant,
+            (Variance::Covariant, Variance::Bivariant) => Variance::Bivariant,
+
+            // Figure 1, column 2.
+            (Variance::Contravariant, Variance::Covariant) => Variance::Contravariant,
+            (Variance::Contravariant, Variance::Contravariant) => Variance::Covariant,
+            (Variance::Contravariant, Variance::Invariant) => Variance::Invariant,
+            (Variance::Contravariant, Variance::Bivariant) => Variance::Bivariant,
+
+            // Figure 1, column 3.
+            (Variance::Invariant, _) => Variance::Invariant,
+
+            // Figure 1, column 4.
+            (Variance::Bivariant, _) => Variance::Bivariant,
+        }
+    }
+}
+
+impl<CTX> HashStable<CTX> for DebruijnIndex {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        self.as_u32().hash_stable(ctx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for IntTy {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        discriminant(self).hash_stable(ctx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for UintTy {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        discriminant(self).hash_stable(ctx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for FloatTy {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        discriminant(self).hash_stable(ctx, hasher);
+    }
+}
+
+impl<CTX> HashStable<CTX> for InferTy {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        use InferTy::*;
+        discriminant(self).hash_stable(ctx, hasher);
+        match self {
+            TyVar(v) => v.as_u32().hash_stable(ctx, hasher),
+            IntVar(v) => v.index.hash_stable(ctx, hasher),
+            FloatVar(v) => v.index.hash_stable(ctx, hasher),
+            FreshTy(v) | FreshIntTy(v) | FreshFloatTy(v) => v.hash_stable(ctx, hasher),
+        }
+    }
+}
+
+impl<CTX> HashStable<CTX> for Variance {
+    fn hash_stable(&self, ctx: &mut CTX, hasher: &mut StableHasher) {
+        discriminant(self).hash_stable(ctx, hasher);
+    }
+}
+
+impl fmt::Debug for IntVarValue {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match *self {
+            IntVarValue::IntType(ref v) => v.fmt(f),
+            IntVarValue::UintType(ref v) => v.fmt(f),
+        }
+    }
+}
+
+impl fmt::Debug for FloatVarValue {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        self.0.fmt(f)
+    }
+}
+
+impl fmt::Debug for IntVid {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "_#{}i", self.index)
+    }
+}
+
+impl fmt::Debug for FloatVid {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "_#{}f", self.index)
+    }
+}
+
+impl fmt::Debug for InferTy {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        use InferTy::*;
+        match *self {
+            TyVar(ref v) => v.fmt(f),
+            IntVar(ref v) => v.fmt(f),
+            FloatVar(ref v) => v.fmt(f),
+            FreshTy(v) => write!(f, "FreshTy({:?})", v),
+            FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
+            FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v),
+        }
+    }
+}
+
+impl fmt::Debug for Variance {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str(match *self {
+            Variance::Covariant => "+",
+            Variance::Contravariant => "-",
+            Variance::Invariant => "o",
+            Variance::Bivariant => "*",
+        })
+    }
+}
+
+impl fmt::Display for InferTy {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        use InferTy::*;
+        match *self {
+            TyVar(_) => write!(f, "_"),
+            IntVar(_) => write!(f, "{}", "{integer}"),
+            FloatVar(_) => write!(f, "{}", "{float}"),
+            FreshTy(v) => write!(f, "FreshTy({})", v),
+            FreshIntTy(v) => write!(f, "FreshIntTy({})", v),
+            FreshFloatTy(v) => write!(f, "FreshFloatTy({})", v),
+        }
+    }
+}
+
+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
new file mode 100644
index 000000000..74737e30b
--- /dev/null
+++ b/compiler/rustc_type_ir/src/sty.rs
@@ -0,0 +1,1329 @@
+#![allow(rustc::usage_of_ty_tykind)]
+
+use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
+use std::{fmt, hash};
+
+use crate::DebruijnIndex;
+use crate::FloatTy;
+use crate::IntTy;
+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;
+use rustc_serialize::{Decodable, Decoder, Encodable};
+
+/// Defines the kinds of types used by the type system.
+///
+/// Types written by the user start out as `hir::TyKind` and get
+/// converted to this representation using `AstConv::ast_ty_to_ty`.
+#[rustc_diagnostic_item = "IrTyKind"]
+pub enum TyKind<I: Interner> {
+    /// The primitive boolean type. Written as `bool`.
+    Bool,
+
+    /// The primitive character type; holds a Unicode scalar value
+    /// (a non-surrogate code point). Written as `char`.
+    Char,
+
+    /// A primitive signed integer type. For example, `i32`.
+    Int(IntTy),
+
+    /// A primitive unsigned integer type. For example, `u32`.
+    Uint(UintTy),
+
+    /// A primitive floating-point type. For example, `f64`.
+    Float(FloatTy),
+
+    /// Algebraic data types (ADT). For example: structures, enumerations and unions.
+    ///
+    /// For example, the type `List<i32>` would be represented using the `AdtDef`
+    /// for `struct List<T>` and the substs `[i32]`.
+    ///
+    /// Note that generic parameters in fields only get lazily substituted
+    /// by using something like `adt_def.all_fields().map(|field| field.ty(tcx, substs))`.
+    Adt(I::AdtDef, I::SubstsRef),
+
+    /// An unsized FFI type that is opaque to Rust. Written as `extern type T`.
+    Foreign(I::DefId),
+
+    /// The pointee of a string slice. Written as `str`.
+    Str,
+
+    /// An array with the given length. Written as `[T; N]`.
+    Array(I::Ty, I::Const),
+
+    /// The pointee of an array slice. Written as `[T]`.
+    Slice(I::Ty),
+
+    /// A raw pointer. Written as `*mut T` or `*const T`
+    RawPtr(I::TypeAndMut),
+
+    /// A reference; a pointer with an associated lifetime. Written as
+    /// `&'a mut T` or `&'a T`.
+    Ref(I::Region, I::Ty, I::Mutability),
+
+    /// The anonymous type of a function declaration/definition. Each
+    /// function has a unique type.
+    ///
+    /// For the function `fn foo() -> i32 { 3 }` this type would be
+    /// shown to the user as `fn() -> i32 {foo}`.
+    ///
+    /// For example the type of `bar` here:
+    /// ```rust
+    /// fn foo() -> i32 { 1 }
+    /// let bar = foo; // bar: fn() -> i32 {foo}
+    /// ```
+    FnDef(I::DefId, I::SubstsRef),
+
+    /// A pointer to a function. Written as `fn() -> i32`.
+    ///
+    /// Note that both functions and closures start out as either
+    /// [FnDef] or [Closure] which can be then be coerced to this variant.
+    ///
+    /// For example the type of `bar` here:
+    ///
+    /// ```rust
+    /// fn foo() -> i32 { 1 }
+    /// let bar: fn() -> i32 = foo;
+    /// ```
+    FnPtr(I::PolyFnSig),
+
+    /// A trait object. Written as `dyn for<'b> Trait<'b, Assoc = u32> + Send + 'a`.
+    Dynamic(I::ListBinderExistentialPredicate, I::Region),
+
+    /// The anonymous type of a closure. Used to represent the type of `|a| a`.
+    ///
+    /// Closure substs contain both the - potentially substituted - generic parameters
+    /// of its parent and some synthetic parameters. See the documentation for
+    /// `ClosureSubsts` for more details.
+    Closure(I::DefId, I::SubstsRef),
+
+    /// The anonymous type of a generator. Used to represent the type of
+    /// `|a| yield a`.
+    ///
+    /// For more info about generator substs, visit the documentation for
+    /// `GeneratorSubsts`.
+    Generator(I::DefId, I::SubstsRef, I::Movability),
+
+    /// A type representing the types stored inside a generator.
+    /// This should only appear as part of the `GeneratorSubsts`.
+    ///
+    /// Note that the captured variables for generators are stored separately
+    /// using a tuple in the same way as for closures.
+    ///
+    /// Unlike upvars, the witness can reference lifetimes from
+    /// inside of the generator itself. To deal with them in
+    /// the type of the generator, we convert them to higher ranked
+    /// lifetimes bound by the witness itself.
+    ///
+    /// Looking at the following example, the witness for this generator
+    /// may end up as something like `for<'a> [Vec<i32>, &'a Vec<i32>]`:
+    ///
+    /// ```ignore UNSOLVED (ask @compiler-errors, should this error? can we just swap the yields?)
+    /// #![feature(generators)]
+    /// |a| {
+    ///     let x = &vec![3];
+    ///     yield a;
+    ///     yield x[0];
+    /// }
+    /// # ;
+    /// ```
+    GeneratorWitness(I::BinderListTy),
+
+    /// The never type `!`.
+    Never,
+
+    /// A tuple type. For example, `(i32, bool)`.
+    Tuple(I::ListTy),
+
+    /// The projection of an associated type. For example,
+    /// `<T as Trait<..>>::N`.
+    Projection(I::ProjectionTy),
+
+    /// Opaque (`impl Trait`) type found in a return type.
+    ///
+    /// The `DefId` comes either from
+    /// * the `impl Trait` ast::Ty node,
+    /// * or the `type Foo = impl Trait` declaration
+    ///
+    /// For RPIT the substitutions are for the generics of the function,
+    /// while for TAIT it is used for the generic parameters of the alias.
+    ///
+    /// During codegen, `tcx.type_of(def_id)` can be used to get the underlying type.
+    Opaque(I::DefId, I::SubstsRef),
+
+    /// A type parameter; for example, `T` in `fn f<T>(x: T) {}`.
+    Param(I::ParamTy),
+
+    /// Bound type variable, used to represent the `'a` in `for<'a> fn(&'a ())`.
+    ///
+    /// For canonical queries, we replace inference variables with bound variables,
+    /// so e.g. when checking whether `&'_ (): Trait<_>` holds, we canonicalize that to
+    /// `for<'a, T> &'a (): Trait<T>` and then convert the introduced bound variables
+    /// back to inference variables in a new inference context when inside of the query.
+    ///
+    /// See the `rustc-dev-guide` for more details about
+    /// [higher-ranked trait bounds][1] and [canonical queries][2].
+    ///
+    /// [1]: https://rustc-dev-guide.rust-lang.org/traits/hrtb.html
+    /// [2]: https://rustc-dev-guide.rust-lang.org/traits/canonical-queries.html
+    Bound(DebruijnIndex, I::BoundTy),
+
+    /// A placeholder type, used during higher ranked subtyping to instantiate
+    /// bound variables.
+    Placeholder(I::PlaceholderType),
+
+    /// A type variable used during type checking.
+    ///
+    /// Similar to placeholders, inference variables also live in a universe to
+    /// correctly deal with higher ranked types. Though unlike placeholders,
+    /// that universe is stored in the `InferCtxt` instead of directly
+    /// inside of the type.
+    Infer(I::InferTy),
+
+    /// A placeholder for a type which could not be computed; this is
+    /// propagated to avoid useless error messages.
+    Error(I::DelaySpanBugEmitted),
+}
+
+impl<I: Interner> TyKind<I> {
+    #[inline]
+    pub fn is_primitive(&self) -> bool {
+        matches!(self, Bool | Char | Int(_) | Uint(_) | Float(_))
+    }
+}
+
+// This is manually implemented for `TyKind` because `std::mem::discriminant`
+// returns an opaque value that is `PartialEq` but not `PartialOrd`
+#[inline]
+const fn tykind_discriminant<I: Interner>(value: &TyKind<I>) -> usize {
+    match value {
+        Bool => 0,
+        Char => 1,
+        Int(_) => 2,
+        Uint(_) => 3,
+        Float(_) => 4,
+        Adt(_, _) => 5,
+        Foreign(_) => 6,
+        Str => 7,
+        Array(_, _) => 8,
+        Slice(_) => 9,
+        RawPtr(_) => 10,
+        Ref(_, _, _) => 11,
+        FnDef(_, _) => 12,
+        FnPtr(_) => 13,
+        Dynamic(_, _) => 14,
+        Closure(_, _) => 15,
+        Generator(_, _, _) => 16,
+        GeneratorWitness(_) => 17,
+        Never => 18,
+        Tuple(_) => 19,
+        Projection(_) => 20,
+        Opaque(_, _) => 21,
+        Param(_) => 22,
+        Bound(_, _) => 23,
+        Placeholder(_) => 24,
+        Infer(_) => 25,
+        Error(_) => 26,
+    }
+}
+
+// This is manually implemented because a derive would require `I: Clone`
+impl<I: Interner> Clone for TyKind<I> {
+    fn clone(&self) -> Self {
+        match self {
+            Bool => Bool,
+            Char => Char,
+            Int(i) => Int(i.clone()),
+            Uint(u) => Uint(u.clone()),
+            Float(f) => Float(f.clone()),
+            Adt(d, s) => Adt(d.clone(), s.clone()),
+            Foreign(d) => Foreign(d.clone()),
+            Str => Str,
+            Array(t, c) => Array(t.clone(), c.clone()),
+            Slice(t) => Slice(t.clone()),
+            RawPtr(t) => RawPtr(t.clone()),
+            Ref(r, t, m) => Ref(r.clone(), t.clone(), m.clone()),
+            FnDef(d, s) => FnDef(d.clone(), s.clone()),
+            FnPtr(s) => FnPtr(s.clone()),
+            Dynamic(p, r) => Dynamic(p.clone(), r.clone()),
+            Closure(d, s) => Closure(d.clone(), s.clone()),
+            Generator(d, s, m) => Generator(d.clone(), s.clone(), m.clone()),
+            GeneratorWitness(g) => GeneratorWitness(g.clone()),
+            Never => Never,
+            Tuple(t) => Tuple(t.clone()),
+            Projection(p) => Projection(p.clone()),
+            Opaque(d, s) => Opaque(d.clone(), s.clone()),
+            Param(p) => Param(p.clone()),
+            Bound(d, b) => Bound(d.clone(), b.clone()),
+            Placeholder(p) => Placeholder(p.clone()),
+            Infer(t) => Infer(t.clone()),
+            Error(e) => Error(e.clone()),
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: PartialEq`
+impl<I: Interner> PartialEq for TyKind<I> {
+    #[inline]
+    fn eq(&self, other: &TyKind<I>) -> bool {
+        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,
+                (&Uint(ref __self_0), &Uint(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Float(ref __self_0), &Float(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Adt(ref __self_0, ref __self_1), &Adt(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (&Foreign(ref __self_0), &Foreign(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Array(ref __self_0, ref __self_1), &Array(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (&Slice(ref __self_0), &Slice(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&RawPtr(ref __self_0), &RawPtr(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (
+                    &Ref(ref __self_0, ref __self_1, ref __self_2),
+                    &Ref(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2),
+                ) => __self_0 == __arg_1_0 && __self_1 == __arg_1_1 && __self_2 == __arg_1_2,
+                (&FnDef(ref __self_0, ref __self_1), &FnDef(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (&FnPtr(ref __self_0), &FnPtr(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Dynamic(ref __self_0, ref __self_1), &Dynamic(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (&Closure(ref __self_0, ref __self_1), &Closure(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (
+                    &Generator(ref __self_0, ref __self_1, ref __self_2),
+                    &Generator(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2),
+                ) => __self_0 == __arg_1_0 && __self_1 == __arg_1_1 && __self_2 == __arg_1_2,
+                (&GeneratorWitness(ref __self_0), &GeneratorWitness(ref __arg_1_0)) => {
+                    __self_0 == __arg_1_0
+                }
+                (&Tuple(ref __self_0), &Tuple(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Projection(ref __self_0), &Projection(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Opaque(ref __self_0, ref __self_1), &Opaque(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (&Param(ref __self_0), &Param(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Bound(ref __self_0, ref __self_1), &Bound(ref __arg_1_0, ref __arg_1_1)) => {
+                    __self_0 == __arg_1_0 && __self_1 == __arg_1_1
+                }
+                (&Placeholder(ref __self_0), &Placeholder(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Infer(ref __self_0), &Infer(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                (&Error(ref __self_0), &Error(ref __arg_1_0)) => __self_0 == __arg_1_0,
+                _ => true,
+            }
+        } else {
+            false
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Eq`
+impl<I: Interner> Eq for TyKind<I> {}
+
+// This is manually implemented because a derive would require `I: PartialOrd`
+impl<I: Interner> PartialOrd for TyKind<I> {
+    #[inline]
+    fn partial_cmp(&self, other: &TyKind<I>) -> Option<Ordering> {
+        Some(Ord::cmp(self, other))
+    }
+}
+
+// This is manually implemented because a derive would require `I: Ord`
+impl<I: Interner> Ord for TyKind<I> {
+    #[inline]
+    fn cmp(&self, other: &TyKind<I>) -> Ordering {
+        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),
+                (&Uint(ref __self_0), &Uint(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Float(ref __self_0), &Float(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Adt(ref __self_0, ref __self_1), &Adt(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,
+                    }
+                }
+                (&Foreign(ref __self_0), &Foreign(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Array(ref __self_0, ref __self_1), &Array(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,
+                    }
+                }
+                (&Slice(ref __self_0), &Slice(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&RawPtr(ref __self_0), &RawPtr(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (
+                    &Ref(ref __self_0, ref __self_1, ref __self_2),
+                    &Ref(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2),
+                ) => match Ord::cmp(__self_0, __arg_1_0) {
+                    Ordering::Equal => match Ord::cmp(__self_1, __arg_1_1) {
+                        Ordering::Equal => Ord::cmp(__self_2, __arg_1_2),
+                        cmp => cmp,
+                    },
+                    cmp => cmp,
+                },
+                (&FnDef(ref __self_0, ref __self_1), &FnDef(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,
+                    }
+                }
+                (&FnPtr(ref __self_0), &FnPtr(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Dynamic(ref __self_0, ref __self_1), &Dynamic(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,
+                    }
+                }
+                (&Closure(ref __self_0, ref __self_1), &Closure(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,
+                    }
+                }
+                (
+                    &Generator(ref __self_0, ref __self_1, ref __self_2),
+                    &Generator(ref __arg_1_0, ref __arg_1_1, ref __arg_1_2),
+                ) => match Ord::cmp(__self_0, __arg_1_0) {
+                    Ordering::Equal => match Ord::cmp(__self_1, __arg_1_1) {
+                        Ordering::Equal => Ord::cmp(__self_2, __arg_1_2),
+                        cmp => cmp,
+                    },
+                    cmp => cmp,
+                },
+                (&GeneratorWitness(ref __self_0), &GeneratorWitness(ref __arg_1_0)) => {
+                    Ord::cmp(__self_0, __arg_1_0)
+                }
+                (&Tuple(ref __self_0), &Tuple(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Projection(ref __self_0), &Projection(ref __arg_1_0)) => {
+                    Ord::cmp(__self_0, __arg_1_0)
+                }
+                (&Opaque(ref __self_0, ref __self_1), &Opaque(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,
+                    }
+                }
+                (&Param(ref __self_0), &Param(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Bound(ref __self_0, ref __self_1), &Bound(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,
+                    }
+                }
+                (&Placeholder(ref __self_0), &Placeholder(ref __arg_1_0)) => {
+                    Ord::cmp(__self_0, __arg_1_0)
+                }
+                (&Infer(ref __self_0), &Infer(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                (&Error(ref __self_0), &Error(ref __arg_1_0)) => Ord::cmp(__self_0, __arg_1_0),
+                _ => 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 TyKind<I> {
+    fn hash<__H: hash::Hasher>(&self, state: &mut __H) -> () {
+        match (&*self,) {
+            (&Int(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Uint(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Float(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Adt(ref __self_0, ref __self_1),) => {
+                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(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Array(ref __self_0, ref __self_1),) => {
+                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(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&RawPtr(ref __self_0),) => {
+                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(&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(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state);
+                hash::Hash::hash(__self_1, state)
+            }
+            (&FnPtr(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Dynamic(ref __self_0, ref __self_1),) => {
+                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(&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(&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(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Tuple(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Projection(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Opaque(ref __self_0, ref __self_1),) => {
+                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(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Bound(ref __self_0, ref __self_1),) => {
+                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(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Infer(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            (&Error(ref __self_0),) => {
+                hash::Hash::hash(&tykind_discriminant(self), state);
+                hash::Hash::hash(__self_0, state)
+            }
+            _ => hash::Hash::hash(&tykind_discriminant(self), state),
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Debug`
+impl<I: Interner> fmt::Debug for TyKind<I> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        use std::fmt::*;
+        match self {
+            Bool => Formatter::write_str(f, "Bool"),
+            Char => Formatter::write_str(f, "Char"),
+            Int(f0) => Formatter::debug_tuple_field1_finish(f, "Int", f0),
+            Uint(f0) => Formatter::debug_tuple_field1_finish(f, "Uint", f0),
+            Float(f0) => Formatter::debug_tuple_field1_finish(f, "Float", f0),
+            Adt(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Adt", f0, f1),
+            Foreign(f0) => Formatter::debug_tuple_field1_finish(f, "Foreign", f0),
+            Str => Formatter::write_str(f, "Str"),
+            Array(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Array", f0, f1),
+            Slice(f0) => Formatter::debug_tuple_field1_finish(f, "Slice", f0),
+            RawPtr(f0) => Formatter::debug_tuple_field1_finish(f, "RawPtr", f0),
+            Ref(f0, f1, f2) => Formatter::debug_tuple_field3_finish(f, "Ref", f0, f1, f2),
+            FnDef(f0, f1) => Formatter::debug_tuple_field2_finish(f, "FnDef", f0, f1),
+            FnPtr(f0) => Formatter::debug_tuple_field1_finish(f, "FnPtr", f0),
+            Dynamic(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Dynamic", f0, f1),
+            Closure(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Closure", f0, f1),
+            Generator(f0, f1, f2) => {
+                Formatter::debug_tuple_field3_finish(f, "Generator", f0, f1, f2)
+            }
+            GeneratorWitness(f0) => Formatter::debug_tuple_field1_finish(f, "GeneratorWitness", f0),
+            Never => Formatter::write_str(f, "Never"),
+            Tuple(f0) => Formatter::debug_tuple_field1_finish(f, "Tuple", f0),
+            Projection(f0) => Formatter::debug_tuple_field1_finish(f, "Projection", f0),
+            Opaque(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Opaque", f0, f1),
+            Param(f0) => Formatter::debug_tuple_field1_finish(f, "Param", f0),
+            Bound(f0, f1) => Formatter::debug_tuple_field2_finish(f, "Bound", f0, f1),
+            Placeholder(f0) => Formatter::debug_tuple_field1_finish(f, "Placeholder", f0),
+            Infer(f0) => Formatter::debug_tuple_field1_finish(f, "Infer", f0),
+            TyKind::Error(f0) => Formatter::debug_tuple_field1_finish(f, "Error", f0),
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Encodable`
+impl<I: Interner, E: TyEncoder> Encodable<E> for TyKind<I>
+where
+    I::DelaySpanBugEmitted: Encodable<E>,
+    I::AdtDef: Encodable<E>,
+    I::SubstsRef: Encodable<E>,
+    I::DefId: Encodable<E>,
+    I::Ty: Encodable<E>,
+    I::Const: Encodable<E>,
+    I::Region: Encodable<E>,
+    I::TypeAndMut: Encodable<E>,
+    I::Mutability: Encodable<E>,
+    I::Movability: Encodable<E>,
+    I::PolyFnSig: Encodable<E>,
+    I::ListBinderExistentialPredicate: Encodable<E>,
+    I::BinderListTy: Encodable<E>,
+    I::ListTy: Encodable<E>,
+    I::ProjectionTy: Encodable<E>,
+    I::ParamTy: Encodable<E>,
+    I::BoundTy: Encodable<E>,
+    I::PlaceholderType: Encodable<E>,
+    I::InferTy: Encodable<E>,
+    I::DelaySpanBugEmitted: Encodable<E>,
+    I::PredicateKind: Encodable<E>,
+    I::AllocId: Encodable<E>,
+{
+    fn encode(&self, e: &mut E) {
+        let disc = tykind_discriminant(self);
+        match self {
+            Bool => e.emit_enum_variant(disc, |_| {}),
+            Char => e.emit_enum_variant(disc, |_| {}),
+            Int(i) => e.emit_enum_variant(disc, |e| {
+                i.encode(e);
+            }),
+            Uint(u) => e.emit_enum_variant(disc, |e| {
+                u.encode(e);
+            }),
+            Float(f) => e.emit_enum_variant(disc, |e| {
+                f.encode(e);
+            }),
+            Adt(adt, substs) => e.emit_enum_variant(disc, |e| {
+                adt.encode(e);
+                substs.encode(e);
+            }),
+            Foreign(def_id) => e.emit_enum_variant(disc, |e| {
+                def_id.encode(e);
+            }),
+            Str => e.emit_enum_variant(disc, |_| {}),
+            Array(t, c) => e.emit_enum_variant(disc, |e| {
+                t.encode(e);
+                c.encode(e);
+            }),
+            Slice(t) => e.emit_enum_variant(disc, |e| {
+                t.encode(e);
+            }),
+            RawPtr(tam) => e.emit_enum_variant(disc, |e| {
+                tam.encode(e);
+            }),
+            Ref(r, t, m) => e.emit_enum_variant(disc, |e| {
+                r.encode(e);
+                t.encode(e);
+                m.encode(e);
+            }),
+            FnDef(def_id, substs) => e.emit_enum_variant(disc, |e| {
+                def_id.encode(e);
+                substs.encode(e);
+            }),
+            FnPtr(polyfnsig) => e.emit_enum_variant(disc, |e| {
+                polyfnsig.encode(e);
+            }),
+            Dynamic(l, r) => e.emit_enum_variant(disc, |e| {
+                l.encode(e);
+                r.encode(e);
+            }),
+            Closure(def_id, substs) => e.emit_enum_variant(disc, |e| {
+                def_id.encode(e);
+                substs.encode(e);
+            }),
+            Generator(def_id, substs, m) => e.emit_enum_variant(disc, |e| {
+                def_id.encode(e);
+                substs.encode(e);
+                m.encode(e);
+            }),
+            GeneratorWitness(b) => e.emit_enum_variant(disc, |e| {
+                b.encode(e);
+            }),
+            Never => e.emit_enum_variant(disc, |_| {}),
+            Tuple(substs) => e.emit_enum_variant(disc, |e| {
+                substs.encode(e);
+            }),
+            Projection(p) => e.emit_enum_variant(disc, |e| {
+                p.encode(e);
+            }),
+            Opaque(def_id, substs) => e.emit_enum_variant(disc, |e| {
+                def_id.encode(e);
+                substs.encode(e);
+            }),
+            Param(p) => e.emit_enum_variant(disc, |e| {
+                p.encode(e);
+            }),
+            Bound(d, b) => e.emit_enum_variant(disc, |e| {
+                d.encode(e);
+                b.encode(e);
+            }),
+            Placeholder(p) => e.emit_enum_variant(disc, |e| {
+                p.encode(e);
+            }),
+            Infer(i) => e.emit_enum_variant(disc, |e| {
+                i.encode(e);
+            }),
+            Error(d) => e.emit_enum_variant(disc, |e| {
+                d.encode(e);
+            }),
+        }
+    }
+}
+
+// This is manually implemented because a derive would require `I: Decodable`
+impl<I: Interner, D: TyDecoder<I = I>> Decodable<D> for TyKind<I>
+where
+    I::DelaySpanBugEmitted: Decodable<D>,
+    I::AdtDef: Decodable<D>,
+    I::SubstsRef: Decodable<D>,
+    I::DefId: Decodable<D>,
+    I::Ty: Decodable<D>,
+    I::Const: Decodable<D>,
+    I::Region: Decodable<D>,
+    I::TypeAndMut: Decodable<D>,
+    I::Mutability: Decodable<D>,
+    I::Movability: Decodable<D>,
+    I::PolyFnSig: Decodable<D>,
+    I::ListBinderExistentialPredicate: Decodable<D>,
+    I::BinderListTy: Decodable<D>,
+    I::ListTy: Decodable<D>,
+    I::ProjectionTy: Decodable<D>,
+    I::ParamTy: Decodable<D>,
+    I::BoundTy: Decodable<D>,
+    I::PlaceholderType: Decodable<D>,
+    I::InferTy: Decodable<D>,
+    I::DelaySpanBugEmitted: Decodable<D>,
+    I::PredicateKind: Decodable<D>,
+    I::AllocId: Decodable<D>,
+{
+    fn decode(d: &mut D) -> Self {
+        match Decoder::read_usize(d) {
+            0 => Bool,
+            1 => Char,
+            2 => Int(Decodable::decode(d)),
+            3 => Uint(Decodable::decode(d)),
+            4 => Float(Decodable::decode(d)),
+            5 => Adt(Decodable::decode(d), Decodable::decode(d)),
+            6 => Foreign(Decodable::decode(d)),
+            7 => Str,
+            8 => Array(Decodable::decode(d), Decodable::decode(d)),
+            9 => Slice(Decodable::decode(d)),
+            10 => RawPtr(Decodable::decode(d)),
+            11 => Ref(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)),
+            12 => FnDef(Decodable::decode(d), Decodable::decode(d)),
+            13 => FnPtr(Decodable::decode(d)),
+            14 => Dynamic(Decodable::decode(d), Decodable::decode(d)),
+            15 => Closure(Decodable::decode(d), Decodable::decode(d)),
+            16 => Generator(Decodable::decode(d), Decodable::decode(d), Decodable::decode(d)),
+            17 => GeneratorWitness(Decodable::decode(d)),
+            18 => Never,
+            19 => Tuple(Decodable::decode(d)),
+            20 => Projection(Decodable::decode(d)),
+            21 => Opaque(Decodable::decode(d), Decodable::decode(d)),
+            22 => Param(Decodable::decode(d)),
+            23 => Bound(Decodable::decode(d), Decodable::decode(d)),
+            24 => Placeholder(Decodable::decode(d)),
+            25 => Infer(Decodable::decode(d)),
+            26 => Error(Decodable::decode(d)),
+            _ => panic!(
+                "{}",
+                format!(
+                    "invalid enum variant tag while decoding `{}`, expected 0..{}",
+                    "TyKind", 27,
+                )
+            ),
+        }
+    }
+}
+
+// This is not a derived impl because a derive would require `I: HashStable`
+#[allow(rustc::usage_of_ty_tykind)]
+impl<CTX, I: Interner> HashStable<CTX> for TyKind<I>
+where
+    I::AdtDef: HashStable<CTX>,
+    I::DefId: HashStable<CTX>,
+    I::SubstsRef: HashStable<CTX>,
+    I::Ty: HashStable<CTX>,
+    I::Const: HashStable<CTX>,
+    I::TypeAndMut: HashStable<CTX>,
+    I::PolyFnSig: HashStable<CTX>,
+    I::ListBinderExistentialPredicate: HashStable<CTX>,
+    I::Region: HashStable<CTX>,
+    I::Movability: HashStable<CTX>,
+    I::Mutability: HashStable<CTX>,
+    I::BinderListTy: HashStable<CTX>,
+    I::ListTy: HashStable<CTX>,
+    I::ProjectionTy: HashStable<CTX>,
+    I::BoundTy: HashStable<CTX>,
+    I::ParamTy: HashStable<CTX>,
+    I::PlaceholderType: HashStable<CTX>,
+    I::InferTy: HashStable<CTX>,
+    I::DelaySpanBugEmitted: 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 {
+            Bool => {}
+            Char => {}
+            Int(i) => {
+                i.hash_stable(__hcx, __hasher);
+            }
+            Uint(u) => {
+                u.hash_stable(__hcx, __hasher);
+            }
+            Float(f) => {
+                f.hash_stable(__hcx, __hasher);
+            }
+            Adt(adt, substs) => {
+                adt.hash_stable(__hcx, __hasher);
+                substs.hash_stable(__hcx, __hasher);
+            }
+            Foreign(def_id) => {
+                def_id.hash_stable(__hcx, __hasher);
+            }
+            Str => {}
+            Array(t, c) => {
+                t.hash_stable(__hcx, __hasher);
+                c.hash_stable(__hcx, __hasher);
+            }
+            Slice(t) => {
+                t.hash_stable(__hcx, __hasher);
+            }
+            RawPtr(tam) => {
+                tam.hash_stable(__hcx, __hasher);
+            }
+            Ref(r, t, m) => {
+                r.hash_stable(__hcx, __hasher);
+                t.hash_stable(__hcx, __hasher);
+                m.hash_stable(__hcx, __hasher);
+            }
+            FnDef(def_id, substs) => {
+                def_id.hash_stable(__hcx, __hasher);
+                substs.hash_stable(__hcx, __hasher);
+            }
+            FnPtr(polyfnsig) => {
+                polyfnsig.hash_stable(__hcx, __hasher);
+            }
+            Dynamic(l, r) => {
+                l.hash_stable(__hcx, __hasher);
+                r.hash_stable(__hcx, __hasher);
+            }
+            Closure(def_id, substs) => {
+                def_id.hash_stable(__hcx, __hasher);
+                substs.hash_stable(__hcx, __hasher);
+            }
+            Generator(def_id, substs, m) => {
+                def_id.hash_stable(__hcx, __hasher);
+                substs.hash_stable(__hcx, __hasher);
+                m.hash_stable(__hcx, __hasher);
+            }
+            GeneratorWitness(b) => {
+                b.hash_stable(__hcx, __hasher);
+            }
+            Never => {}
+            Tuple(substs) => {
+                substs.hash_stable(__hcx, __hasher);
+            }
+            Projection(p) => {
+                p.hash_stable(__hcx, __hasher);
+            }
+            Opaque(def_id, substs) => {
+                def_id.hash_stable(__hcx, __hasher);
+                substs.hash_stable(__hcx, __hasher);
+            }
+            Param(p) => {
+                p.hash_stable(__hcx, __hasher);
+            }
+            Bound(d, b) => {
+                d.hash_stable(__hcx, __hasher);
+                b.hash_stable(__hcx, __hasher);
+            }
+            Placeholder(p) => {
+                p.hash_stable(__hcx, __hasher);
+            }
+            Infer(i) => {
+                i.hash_stable(__hcx, __hasher);
+            }
+            Error(d) => {
+                d.hash_stable(__hcx, __hasher);
+            }
+        }
+    }
+}
+
+/// 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);
+            }
+        }
+    }
+}