Move a few more types to `rustc_type_ir`

9 files changed, 426 insertions, 265 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c2c06a2adb1..bea1879e793 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -4314,6 +4314,7 @@ dependencies = [
  "bitflags",
  "rustc_data_structures",
  "rustc_index",
+ "rustc_macros",
  "rustc_serialize",
 ]
 
diff --git a/compiler/rustc_middle/src/infer/unify_key.rs b/compiler/rustc_middle/src/infer/unify_key.rs
index 16e9aafb25a..8318bdefc8e 100644
--- a/compiler/rustc_middle/src/infer/unify_key.rs
+++ b/compiler/rustc_middle/src/infer/unify_key.rs
@@ -1,4 +1,4 @@
-use crate::ty::{self, FloatVarValue, InferConst, IntVarValue, Ty, TyCtxt};
+use crate::ty::{self, InferConst, Ty, TyCtxt};
 use rustc_data_structures::snapshot_vec;
 use rustc_data_structures::undo_log::UndoLogs;
 use rustc_data_structures::unify::{
@@ -15,36 +15,6 @@ pub trait ToType {
     fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx>;
 }
 
-/// Raw `TyVid` are used as the unification key for `sub_relations`;
-/// they carry no values.
-impl UnifyKey for ty::TyVid {
-    type Value = ();
-    fn index(&self) -> u32 {
-        self.index
-    }
-    fn from_index(i: u32) -> ty::TyVid {
-        ty::TyVid { index: i }
-    }
-    fn tag() -> &'static str {
-        "TyVid"
-    }
-}
-
-impl UnifyKey for ty::IntVid {
-    type Value = Option<IntVarValue>;
-    fn index(&self) -> u32 {
-        self.index
-    }
-    fn from_index(i: u32) -> ty::IntVid {
-        ty::IntVid { index: i }
-    }
-    fn tag() -> &'static str {
-        "IntVid"
-    }
-}
-
-impl EqUnifyValue for IntVarValue {}
-
 #[derive(PartialEq, Copy, Clone, Debug)]
 pub struct RegionVidKey {
     /// The minimum region vid in the unification set. This is needed
@@ -80,7 +50,7 @@ impl UnifyKey for ty::RegionVid {
     }
 }
 
-impl ToType for IntVarValue {
+impl ToType for ty::IntVarValue {
     fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
         match *self {
             ty::IntType(i) => tcx.mk_mach_int(i),
@@ -89,24 +59,7 @@ impl ToType for IntVarValue {
     }
 }
 
-// Floating point type keys
-
-impl UnifyKey for ty::FloatVid {
-    type Value = Option<FloatVarValue>;
-    fn index(&self) -> u32 {
-        self.index
-    }
-    fn from_index(i: u32) -> ty::FloatVid {
-        ty::FloatVid { index: i }
-    }
-    fn tag() -> &'static str {
-        "FloatVid"
-    }
-}
-
-impl EqUnifyValue for FloatVarValue {}
-
-impl ToType for FloatVarValue {
+impl ToType for ty::FloatVarValue {
     fn to_type<'tcx>(&self, tcx: TyCtxt<'tcx>) -> Ty<'tcx> {
         tcx.mk_mach_float(self.0)
     }
diff --git a/compiler/rustc_middle/src/ty/diagnostics.rs b/compiler/rustc_middle/src/ty/diagnostics.rs
index 3adcdbe591f..e386d973ee4 100644
--- a/compiler/rustc_middle/src/ty/diagnostics.rs
+++ b/compiler/rustc_middle/src/ty/diagnostics.rs
@@ -1,8 +1,7 @@
 //! Diagnostics related methods for `TyS`.
 
-use crate::ty::sty::InferTy;
 use crate::ty::TyKind::*;
-use crate::ty::{TyCtxt, TyS};
+use crate::ty::{InferTy, TyCtxt, TyS};
 use rustc_errors::{Applicability, DiagnosticBuilder};
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index c6970df0178..87730197da0 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -65,7 +65,6 @@ use std::ptr;
 use std::str;
 
 pub use self::sty::BoundRegionKind::*;
-pub use self::sty::InferTy::*;
 pub use self::sty::RegionKind;
 pub use self::sty::RegionKind::*;
 pub use self::sty::TyKind::*;
@@ -74,13 +73,14 @@ pub use self::sty::{BoundRegion, BoundRegionKind, EarlyBoundRegion, FreeRegion,
 pub use self::sty::{CanonicalPolyFnSig, FnSig, GenSig, PolyFnSig, PolyGenSig};
 pub use self::sty::{ClosureSubsts, GeneratorSubsts, TypeAndMut, UpvarSubsts};
 pub use self::sty::{ClosureSubstsParts, GeneratorSubstsParts};
-pub use self::sty::{ConstVid, FloatVid, IntVid, RegionVid, TyVid};
-pub use self::sty::{ExistentialPredicate, InferTy, ParamConst, ParamTy, ProjectionTy};
+pub use self::sty::{ConstVid, RegionVid};
+pub use self::sty::{ExistentialPredicate, ParamConst, ParamTy, ProjectionTy};
 pub use self::sty::{ExistentialProjection, PolyExistentialProjection};
 pub use self::sty::{ExistentialTraitRef, PolyExistentialTraitRef};
 pub use self::sty::{PolyTraitRef, TraitRef, TyKind};
 pub use crate::ty::diagnostics::*;
-pub use rustc_type_ir::{DebruijnIndex, TypeFlags, INNERMOST};
+pub use rustc_type_ir::InferTy::*;
+pub use rustc_type_ir::*;
 
 pub use self::binding::BindingMode;
 pub use self::binding::BindingMode::*;
@@ -421,14 +421,6 @@ impl Visibility {
     }
 }
 
-#[derive(Copy, Clone, PartialEq, TyDecodable, TyEncodable, HashStable)]
-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
-}
-
 /// The crate variances map is computed during typeck and contains the
 /// variance of every item in the local crate. You should not use it
 /// directly, because to do so will make your pass dependent on the
@@ -443,66 +435,6 @@ pub struct CrateVariancesMap<'tcx> {
     pub variances: FxHashMap<DefId, &'tcx [ty::Variance]>,
 }
 
-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:
-    ///
-    ///     *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:
-    ///
-    ///     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: ty::Variance) -> ty::Variance {
-        match (self, v) {
-            // Figure 1, column 1.
-            (ty::Covariant, ty::Covariant) => ty::Covariant,
-            (ty::Covariant, ty::Contravariant) => ty::Contravariant,
-            (ty::Covariant, ty::Invariant) => ty::Invariant,
-            (ty::Covariant, ty::Bivariant) => ty::Bivariant,
-
-            // Figure 1, column 2.
-            (ty::Contravariant, ty::Covariant) => ty::Contravariant,
-            (ty::Contravariant, ty::Contravariant) => ty::Covariant,
-            (ty::Contravariant, ty::Invariant) => ty::Invariant,
-            (ty::Contravariant, ty::Bivariant) => ty::Bivariant,
-
-            // Figure 1, column 3.
-            (ty::Invariant, _) => ty::Invariant,
-
-            // Figure 1, column 4.
-            (ty::Bivariant, _) => ty::Bivariant,
-        }
-    }
-}
-
 // Contains information needed to resolve types and (in the future) look up
 // the types of AST nodes.
 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
@@ -804,15 +736,6 @@ pub struct CaptureInfo<'tcx> {
 pub type UpvarListMap = FxHashMap<DefId, FxIndexMap<hir::HirId, UpvarId>>;
 pub type UpvarCaptureMap<'tcx> = FxHashMap<UpvarId, UpvarCapture<'tcx>>;
 
-#[derive(Clone, Copy, PartialEq, Eq)]
-pub enum IntVarValue {
-    IntType(ast::IntTy),
-    UintType(ast::UintTy),
-}
-
-#[derive(Clone, Copy, PartialEq, Eq)]
-pub struct FloatVarValue(pub ast::FloatTy);
-
 impl ty::EarlyBoundRegion {
     /// Does this early bound region have a name? Early bound regions normally
     /// always have names except when using anonymous lifetimes (`'_`).
diff --git a/compiler/rustc_middle/src/ty/print/pretty.rs b/compiler/rustc_middle/src/ty/print/pretty.rs
index 8911de41c6d..9c7e0e60c14 100644
--- a/compiler/rustc_middle/src/ty/print/pretty.rs
+++ b/compiler/rustc_middle/src/ty/print/pretty.rs
@@ -557,14 +557,19 @@ pub trait PrettyPrinter<'tcx>:
             }
             ty::FnPtr(ref bare_fn) => p!(print(bare_fn)),
             ty::Infer(infer_ty) => {
+                let verbose = self.tcx().sess.verbose();
                 if let ty::TyVar(ty_vid) = infer_ty {
                     if let Some(name) = self.infer_ty_name(ty_vid) {
                         p!(write("{}", name))
                     } else {
-                        p!(write("{}", infer_ty))
+                        if verbose {
+                            p!(write("{:?}", infer_ty))
+                        } else {
+                            p!(write("{}", infer_ty))
+                        }
                     }
                 } else {
-                    p!(write("{}", infer_ty))
+                    if verbose { p!(write("{:?}", infer_ty)) } else { p!(write("{}", infer_ty)) }
                 }
             }
             ty::Error(_) => p!("[type error]"),
@@ -1246,7 +1251,7 @@ pub struct FmtPrinterData<'a, 'tcx, F> {
 
     pub region_highlight_mode: RegionHighlightMode,
 
-    pub name_resolver: Option<Box<&'a dyn Fn(ty::sty::TyVid) -> Option<String>>>,
+    pub name_resolver: Option<Box<&'a dyn Fn(ty::TyVid) -> Option<String>>>,
 }
 
 impl<F> Deref for FmtPrinter<'a, 'tcx, F> {
@@ -2007,21 +2012,6 @@ define_print_and_forward_display! {
         p!("fn", pretty_fn_sig(self.inputs(), self.c_variadic, self.output()));
     }
 
-    ty::InferTy {
-        if cx.tcx().sess.verbose() {
-            p!(write("{:?}", self));
-            return Ok(cx);
-        }
-        match *self {
-            ty::TyVar(_) => p!("_"),
-            ty::IntVar(_) => p!(write("{}", "{integer}")),
-            ty::FloatVar(_) => p!(write("{}", "{float}")),
-            ty::FreshTy(v) => p!(write("FreshTy({})", v)),
-            ty::FreshIntTy(v) => p!(write("FreshIntTy({})", v)),
-            ty::FreshFloatTy(v) => p!(write("FreshFloatTy({})", v))
-        }
-    }
-
     ty::TraitRef<'tcx> {
         p!(write("<{} as {}>", self.self_ty(), self.print_only_trait_path()))
     }
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 44c173e356d..0ca94a9f180 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -111,81 +111,24 @@ impl fmt::Debug for ty::FreeRegion {
     }
 }
 
-impl fmt::Debug for ty::Variance {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.write_str(match *self {
-            ty::Covariant => "+",
-            ty::Contravariant => "-",
-            ty::Invariant => "o",
-            ty::Bivariant => "*",
-        })
-    }
-}
-
 impl fmt::Debug for ty::FnSig<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "({:?}; c_variadic: {})->{:?}", self.inputs(), self.c_variadic, self.output())
     }
 }
 
-impl fmt::Debug for ty::TyVid {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "_#{}t", self.index)
-    }
-}
-
 impl<'tcx> fmt::Debug for ty::ConstVid<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "_#{}c", self.index)
     }
 }
 
-impl fmt::Debug for ty::IntVid {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "_#{}i", self.index)
-    }
-}
-
-impl fmt::Debug for ty::FloatVid {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        write!(f, "_#{}f", self.index)
-    }
-}
-
 impl fmt::Debug for ty::RegionVid {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         write!(f, "'_#{}r", self.index())
     }
 }
 
-impl fmt::Debug for ty::InferTy {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match *self {
-            ty::TyVar(ref v) => v.fmt(f),
-            ty::IntVar(ref v) => v.fmt(f),
-            ty::FloatVar(ref v) => v.fmt(f),
-            ty::FreshTy(v) => write!(f, "FreshTy({:?})", v),
-            ty::FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
-            ty::FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v),
-        }
-    }
-}
-
-impl fmt::Debug for ty::IntVarValue {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        match *self {
-            ty::IntType(ref v) => v.fmt(f),
-            ty::UintType(ref v) => v.fmt(f),
-        }
-    }
-}
-
-impl fmt::Debug for ty::FloatVarValue {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        self.0.fmt(f)
-    }
-}
-
 impl fmt::Debug for ty::TraitRef<'tcx> {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         with_no_trimmed_paths(|| fmt::Display::fmt(self, f))
@@ -274,7 +217,7 @@ TrivialTypeFoldableAndLiftImpls! {
     u64,
     String,
     crate::middle::region::Scope,
-    ::rustc_ast::FloatTy,
+    crate::ty::FloatTy,
     ::rustc_ast::InlineAsmOptions,
     ::rustc_ast::InlineAsmTemplatePiece,
     ::rustc_ast::NodeId,
diff --git a/compiler/rustc_middle/src/ty/sty.rs b/compiler/rustc_middle/src/ty/sty.rs
index e53977b5eb9..aeba1843dbc 100644
--- a/compiler/rustc_middle/src/ty/sty.rs
+++ b/compiler/rustc_middle/src/ty/sty.rs
@@ -2,11 +2,11 @@
 
 #![allow(rustc::usage_of_ty_tykind)]
 
-use self::InferTy::*;
 use self::TyKind::*;
 
 use crate::infer::canonical::Canonical;
 use crate::ty::subst::{GenericArg, InternalSubsts, Subst, SubstsRef};
+use crate::ty::InferTy::{self, *};
 use crate::ty::{
     self, AdtDef, DefIdTree, Discr, Ty, TyCtxt, TypeFlags, TypeFoldable, WithConstness,
 };
@@ -1426,12 +1426,6 @@ pub struct EarlyBoundRegion {
     pub name: Symbol,
 }
 
-/// A **ty**pe **v**ariable **ID**.
-#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
-pub struct TyVid {
-    pub index: u32,
-}
-
 /// A **`const`** **v**ariable **ID**.
 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
 pub struct ConstVid<'tcx> {
@@ -1439,18 +1433,6 @@ pub struct ConstVid<'tcx> {
     pub phantom: PhantomData<&'tcx ()>,
 }
 
-/// An **int**egral (`u32`, `i32`, `usize`, etc.) type **v**ariable **ID**.
-#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, TyEncodable, TyDecodable)]
-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, TyEncodable, TyDecodable)]
-pub struct FloatVid {
-    pub index: u32,
-}
-
 rustc_index::newtype_index! {
     /// A **region** (lifetime) **v**ariable **ID**.
     pub struct RegionVid {
@@ -1464,43 +1446,6 @@ impl Atom for RegionVid {
     }
 }
 
-/// 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, TyEncodable, TyDecodable)]
-#[derive(HashStable)]
-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),
-}
-
 rustc_index::newtype_index! {
     pub struct BoundVar { .. }
 }
diff --git a/compiler/rustc_type_ir/Cargo.toml b/compiler/rustc_type_ir/Cargo.toml
index d50451b7794..3f64bd89997 100644
--- a/compiler/rustc_type_ir/Cargo.toml
+++ b/compiler/rustc_type_ir/Cargo.toml
@@ -12,3 +12,4 @@ 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" }
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index 37abb4496ac..7e70af21c03 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -4,8 +4,13 @@
 
 #[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 std::fmt;
+use std::mem::discriminant;
 
 bitflags! {
     /// Flags that we track on types. These flags are propagated upwards
@@ -197,8 +202,409 @@ impl DebruijnIndex {
     }
 }
 
+#[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);
+
+/// A **ty**pe **v**ariable **ID**.
+#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Encodable, Decodable)]
+pub struct TyVid {
+    pub index: u32,
+}
+
+/// 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 = ();
+    fn index(&self) -> u32 {
+        self.index
+    }
+    fn from_index(i: u32) -> TyVid {
+        TyVid { index: i }
+    }
+    fn tag() -> &'static str {
+        "TyVid"
+    }
+}
+
+impl EqUnifyValue for IntVarValue {}
+
+impl UnifyKey for IntVid {
+    type Value = Option<IntVarValue>;
+    fn index(&self) -> u32 {
+        self.index
+    }
+    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>;
+    fn index(&self) -> u32 {
+        self.index
+    }
+    fn from_index(i: u32) -> FloatVid {
+        FloatVid { index: i }
+    }
+    fn tag() -> &'static str {
+        "FloatVid"
+    }
+}
+
+#[derive(Copy, Clone, PartialEq, Decodable, Encodable)]
+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:
+    ///
+    ///     *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:
+    ///
+    ///     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::*;
+        match self {
+            TyVar(v) => v.index.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 TyVid {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "_#{}t", self.index)
+    }
+}
+
+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),
+        }
+    }
+}