Move infer::canonical datatypes to infer::types.

3 files changed, 364 insertions, 334 deletions

diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs
index a588d3d028a..f157d805bcd 100644
--- a/src/librustc/infer/canonical/mod.rs
+++ b/src/librustc/infer/canonical/mod.rs
@@ -21,18 +21,15 @@
 //!
 //! [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html
 
-use crate::infer::region_constraints::MemberConstraint;
 use crate::infer::{ConstVariableOrigin, ConstVariableOriginKind};
 use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin, TypeVariableOriginKind};
-use crate::ty::fold::TypeFoldable;
-use crate::ty::subst::GenericArg;
-use crate::ty::{self, BoundVar, List, Region, TyCtxt};
+use rustc::ty::fold::TypeFoldable;
+use rustc::ty::subst::GenericArg;
+use rustc::ty::{self, BoundVar, List};
 use rustc_index::vec::IndexVec;
-use rustc_macros::HashStable;
-use rustc_serialize::UseSpecializedDecodable;
 use rustc_span::source_map::Span;
-use smallvec::SmallVec;
-use std::ops::Index;
+
+pub use rustc::infer::types::canonical::*;
 
 mod canonicalizer;
 
@@ -40,265 +37,6 @@ pub mod query_response;
 
 mod substitute;
 
-/// A "canonicalized" type `V` is one where all free inference
-/// variables have been rewritten to "canonical vars". These are
-/// numbered starting from 0 in order of first appearance.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
-#[derive(HashStable, TypeFoldable, Lift)]
-pub struct Canonical<'tcx, V> {
-    pub max_universe: ty::UniverseIndex,
-    pub variables: CanonicalVarInfos<'tcx>,
-    pub value: V,
-}
-
-pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo>;
-
-impl<'tcx> UseSpecializedDecodable for CanonicalVarInfos<'tcx> {}
-
-/// A set of values corresponding to the canonical variables from some
-/// `Canonical`. You can give these values to
-/// `canonical_value.substitute` to substitute them into the canonical
-/// value at the right places.
-///
-/// When you canonicalize a value `V`, you get back one of these
-/// vectors with the original values that were replaced by canonical
-/// variables. You will need to supply it later to instantiate the
-/// canonicalized query response.
-#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
-#[derive(HashStable, TypeFoldable, Lift)]
-pub struct CanonicalVarValues<'tcx> {
-    pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
-}
-
-/// When we canonicalize a value to form a query, we wind up replacing
-/// various parts of it with canonical variables. This struct stores
-/// those replaced bits to remember for when we process the query
-/// result.
-#[derive(Clone, Debug)]
-pub struct OriginalQueryValues<'tcx> {
-    /// Map from the universes that appear in the query to the
-    /// universes in the caller context. For the time being, we only
-    /// ever put ROOT values into the query, so this map is very
-    /// simple.
-    pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
-
-    /// This is equivalent to `CanonicalVarValues`, but using a
-    /// `SmallVec` yields a significant performance win.
-    pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
-}
-
-impl Default for OriginalQueryValues<'tcx> {
-    fn default() -> Self {
-        let mut universe_map = SmallVec::default();
-        universe_map.push(ty::UniverseIndex::ROOT);
-
-        Self { universe_map, var_values: SmallVec::default() }
-    }
-}
-
-/// Information about a canonical variable that is included with the
-/// canonical value. This is sufficient information for code to create
-/// a copy of the canonical value in some other inference context,
-/// with fresh inference variables replacing the canonical values.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
-pub struct CanonicalVarInfo {
-    pub kind: CanonicalVarKind,
-}
-
-impl CanonicalVarInfo {
-    pub fn universe(&self) -> ty::UniverseIndex {
-        self.kind.universe()
-    }
-
-    pub fn is_existential(&self) -> bool {
-        match self.kind {
-            CanonicalVarKind::Ty(_) => true,
-            CanonicalVarKind::PlaceholderTy(_) => false,
-            CanonicalVarKind::Region(_) => true,
-            CanonicalVarKind::PlaceholderRegion(..) => false,
-            CanonicalVarKind::Const(_) => true,
-            CanonicalVarKind::PlaceholderConst(_) => false,
-        }
-    }
-}
-
-/// Describes the "kind" of the canonical variable. This is a "kind"
-/// in the type-theory sense of the term -- i.e., a "meta" type system
-/// that analyzes type-like values.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
-pub enum CanonicalVarKind {
-    /// Some kind of type inference variable.
-    Ty(CanonicalTyVarKind),
-
-    /// A "placeholder" that represents "any type".
-    PlaceholderTy(ty::PlaceholderType),
-
-    /// Region variable `'?R`.
-    Region(ty::UniverseIndex),
-
-    /// A "placeholder" that represents "any region". Created when you
-    /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
-    /// bound region `'a`.
-    PlaceholderRegion(ty::PlaceholderRegion),
-
-    /// Some kind of const inference variable.
-    Const(ty::UniverseIndex),
-
-    /// A "placeholder" that represents "any const".
-    PlaceholderConst(ty::PlaceholderConst),
-}
-
-impl CanonicalVarKind {
-    pub fn universe(self) -> ty::UniverseIndex {
-        match self {
-            CanonicalVarKind::Ty(kind) => match kind {
-                CanonicalTyVarKind::General(ui) => ui,
-                CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
-            },
-
-            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
-            CanonicalVarKind::Region(ui) => ui,
-            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
-            CanonicalVarKind::Const(ui) => ui,
-            CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe,
-        }
-    }
-}
-
-/// Rust actually has more than one category of type variables;
-/// notably, the type variables we create for literals (e.g., 22 or
-/// 22.) can only be instantiated with integral/float types (e.g.,
-/// usize or f32). In order to faithfully reproduce a type, we need to
-/// know what set of types a given type variable can be unified with.
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
-pub enum CanonicalTyVarKind {
-    /// General type variable `?T` that can be unified with arbitrary types.
-    General(ty::UniverseIndex),
-
-    /// Integral type variable `?I` (that can only be unified with integral types).
-    Int,
-
-    /// Floating-point type variable `?F` (that can only be unified with float types).
-    Float,
-}
-
-/// After we execute a query with a canonicalized key, we get back a
-/// `Canonical<QueryResponse<..>>`. You can use
-/// `instantiate_query_result` to access the data in this result.
-#[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
-pub struct QueryResponse<'tcx, R> {
-    pub var_values: CanonicalVarValues<'tcx>,
-    pub region_constraints: QueryRegionConstraints<'tcx>,
-    pub certainty: Certainty,
-    pub value: R,
-}
-
-#[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
-pub struct QueryRegionConstraints<'tcx> {
-    pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
-    pub member_constraints: Vec<MemberConstraint<'tcx>>,
-}
-
-impl QueryRegionConstraints<'_> {
-    /// Represents an empty (trivially true) set of region
-    /// constraints.
-    pub fn is_empty(&self) -> bool {
-        self.outlives.is_empty() && self.member_constraints.is_empty()
-    }
-}
-
-pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>;
-
-pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
-
-/// Indicates whether or not we were able to prove the query to be
-/// true.
-#[derive(Copy, Clone, Debug, HashStable)]
-pub enum Certainty {
-    /// The query is known to be true, presuming that you apply the
-    /// given `var_values` and the region-constraints are satisfied.
-    Proven,
-
-    /// The query is not known to be true, but also not known to be
-    /// false. The `var_values` represent *either* values that must
-    /// hold in order for the query to be true, or helpful tips that
-    /// *might* make it true. Currently rustc's trait solver cannot
-    /// distinguish the two (e.g., due to our preference for where
-    /// clauses over impls).
-    ///
-    /// After some unifiations and things have been done, it makes
-    /// sense to try and prove again -- of course, at that point, the
-    /// canonical form will be different, making this a distinct
-    /// query.
-    Ambiguous,
-}
-
-impl Certainty {
-    pub fn is_proven(&self) -> bool {
-        match self {
-            Certainty::Proven => true,
-            Certainty::Ambiguous => false,
-        }
-    }
-
-    pub fn is_ambiguous(&self) -> bool {
-        !self.is_proven()
-    }
-}
-
-impl<'tcx, R> QueryResponse<'tcx, R> {
-    pub fn is_proven(&self) -> bool {
-        self.certainty.is_proven()
-    }
-
-    pub fn is_ambiguous(&self) -> bool {
-        !self.is_proven()
-    }
-}
-
-impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
-    pub fn is_proven(&self) -> bool {
-        self.value.is_proven()
-    }
-
-    pub fn is_ambiguous(&self) -> bool {
-        !self.is_proven()
-    }
-}
-
-impl<'tcx, V> Canonical<'tcx, V> {
-    /// Allows you to map the `value` of a canonical while keeping the
-    /// same set of bound variables.
-    ///
-    /// **WARNING:** This function is very easy to mis-use, hence the
-    /// name!  In particular, the new value `W` must use all **the
-    /// same type/region variables** in **precisely the same order**
-    /// as the original! (The ordering is defined by the
-    /// `TypeFoldable` implementation of the type in question.)
-    ///
-    /// An example of a **correct** use of this:
-    ///
-    /// ```rust,ignore (not real code)
-    /// let a: Canonical<'_, T> = ...;
-    /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
-    /// ```
-    ///
-    /// An example of an **incorrect** use of this:
-    ///
-    /// ```rust,ignore (not real code)
-    /// let a: Canonical<'tcx, T> = ...;
-    /// let ty: Ty<'tcx> = ...;
-    /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
-    /// ```
-    pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
-        let Canonical { max_universe, variables, value } = self;
-        Canonical { max_universe, variables, value: map_op(value) }
-    }
-}
-
-pub type QueryOutlivesConstraint<'tcx> =
-    ty::Binder<ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>;
-
 impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
     /// Creates a substitution S for the canonical value with fresh
     /// inference variables and applies it to the canonical value.
@@ -424,70 +162,3 @@ impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
         }
     }
 }
-
-CloneTypeFoldableAndLiftImpls! {
-    crate::infer::canonical::Certainty,
-    crate::infer::canonical::CanonicalVarInfo,
-    crate::infer::canonical::CanonicalVarKind,
-}
-
-CloneTypeFoldableImpls! {
-    for <'tcx> {
-        crate::infer::canonical::CanonicalVarInfos<'tcx>,
-    }
-}
-
-impl<'tcx> CanonicalVarValues<'tcx> {
-    pub fn len(&self) -> usize {
-        self.var_values.len()
-    }
-
-    /// Makes an identity substitution from this one: each bound var
-    /// is matched to the same bound var, preserving the original kinds.
-    /// For example, if we have:
-    /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
-    /// we'll return a substitution `subst` with:
-    /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
-    pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
-        use crate::ty::subst::GenericArgKind;
-
-        CanonicalVarValues {
-            var_values: self
-                .var_values
-                .iter()
-                .zip(0..)
-                .map(|(kind, i)| match kind.unpack() {
-                    GenericArgKind::Type(..) => {
-                        tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
-                    }
-                    GenericArgKind::Lifetime(..) => tcx
-                        .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i)))
-                        .into(),
-                    GenericArgKind::Const(ct) => tcx
-                        .mk_const(ty::Const {
-                            ty: ct.ty,
-                            val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
-                        })
-                        .into(),
-                })
-                .collect(),
-        }
-    }
-}
-
-impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
-    type Item = GenericArg<'tcx>;
-    type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;
-
-    fn into_iter(self) -> Self::IntoIter {
-        self.var_values.iter().cloned()
-    }
-}
-
-impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
-    type Output = GenericArg<'tcx>;
-
-    fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
-        &self.var_values[value]
-    }
-}
diff --git a/src/librustc/infer/types/canonical.rs b/src/librustc/infer/types/canonical.rs
new file mode 100644
index 00000000000..133cf1b5928
--- /dev/null
+++ b/src/librustc/infer/types/canonical.rs
@@ -0,0 +1,357 @@
+//! **Canonicalization** is the key to constructing a query in the
+//! middle of type inference. Ordinarily, it is not possible to store
+//! types from type inference in query keys, because they contain
+//! references to inference variables whose lifetimes are too short
+//! and so forth. Canonicalizing a value T1 using `canonicalize_query`
+//! produces two things:
+//!
+//! - a value T2 where each unbound inference variable has been
+//!   replaced with a **canonical variable**;
+//! - a map M (of type `CanonicalVarValues`) from those canonical
+//!   variables back to the original.
+//!
+//! We can then do queries using T2. These will give back constraints
+//! on the canonical variables which can be translated, using the map
+//! M, into constraints in our source context. This process of
+//! translating the results back is done by the
+//! `instantiate_query_result` method.
+//!
+//! For a more detailed look at what is happening here, check
+//! out the [chapter in the rustc guide][c].
+//!
+//! [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html
+
+use crate::infer::region_constraints::MemberConstraint;
+use crate::ty::subst::GenericArg;
+use crate::ty::{self, BoundVar, List, Region, TyCtxt};
+use rustc_index::vec::IndexVec;
+use rustc_macros::HashStable;
+use rustc_serialize::UseSpecializedDecodable;
+use smallvec::SmallVec;
+use std::ops::Index;
+
+/// A "canonicalized" type `V` is one where all free inference
+/// variables have been rewritten to "canonical vars". These are
+/// numbered starting from 0 in order of first appearance.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
+#[derive(HashStable, TypeFoldable, Lift)]
+pub struct Canonical<'tcx, V> {
+    pub max_universe: ty::UniverseIndex,
+    pub variables: CanonicalVarInfos<'tcx>,
+    pub value: V,
+}
+
+pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo>;
+
+impl<'tcx> UseSpecializedDecodable for CanonicalVarInfos<'tcx> {}
+
+/// A set of values corresponding to the canonical variables from some
+/// `Canonical`. You can give these values to
+/// `canonical_value.substitute` to substitute them into the canonical
+/// value at the right places.
+///
+/// When you canonicalize a value `V`, you get back one of these
+/// vectors with the original values that were replaced by canonical
+/// variables. You will need to supply it later to instantiate the
+/// canonicalized query response.
+#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
+#[derive(HashStable, TypeFoldable, Lift)]
+pub struct CanonicalVarValues<'tcx> {
+    pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
+}
+
+/// When we canonicalize a value to form a query, we wind up replacing
+/// various parts of it with canonical variables. This struct stores
+/// those replaced bits to remember for when we process the query
+/// result.
+#[derive(Clone, Debug)]
+pub struct OriginalQueryValues<'tcx> {
+    /// Map from the universes that appear in the query to the
+    /// universes in the caller context. For the time being, we only
+    /// ever put ROOT values into the query, so this map is very
+    /// simple.
+    pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
+
+    /// This is equivalent to `CanonicalVarValues`, but using a
+    /// `SmallVec` yields a significant performance win.
+    pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
+}
+
+impl Default for OriginalQueryValues<'tcx> {
+    fn default() -> Self {
+        let mut universe_map = SmallVec::default();
+        universe_map.push(ty::UniverseIndex::ROOT);
+
+        Self { universe_map, var_values: SmallVec::default() }
+    }
+}
+
+/// Information about a canonical variable that is included with the
+/// canonical value. This is sufficient information for code to create
+/// a copy of the canonical value in some other inference context,
+/// with fresh inference variables replacing the canonical values.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
+pub struct CanonicalVarInfo {
+    pub kind: CanonicalVarKind,
+}
+
+impl CanonicalVarInfo {
+    pub fn universe(&self) -> ty::UniverseIndex {
+        self.kind.universe()
+    }
+
+    pub fn is_existential(&self) -> bool {
+        match self.kind {
+            CanonicalVarKind::Ty(_) => true,
+            CanonicalVarKind::PlaceholderTy(_) => false,
+            CanonicalVarKind::Region(_) => true,
+            CanonicalVarKind::PlaceholderRegion(..) => false,
+            CanonicalVarKind::Const(_) => true,
+            CanonicalVarKind::PlaceholderConst(_) => false,
+        }
+    }
+}
+
+/// Describes the "kind" of the canonical variable. This is a "kind"
+/// in the type-theory sense of the term -- i.e., a "meta" type system
+/// that analyzes type-like values.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
+pub enum CanonicalVarKind {
+    /// Some kind of type inference variable.
+    Ty(CanonicalTyVarKind),
+
+    /// A "placeholder" that represents "any type".
+    PlaceholderTy(ty::PlaceholderType),
+
+    /// Region variable `'?R`.
+    Region(ty::UniverseIndex),
+
+    /// A "placeholder" that represents "any region". Created when you
+    /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
+    /// bound region `'a`.
+    PlaceholderRegion(ty::PlaceholderRegion),
+
+    /// Some kind of const inference variable.
+    Const(ty::UniverseIndex),
+
+    /// A "placeholder" that represents "any const".
+    PlaceholderConst(ty::PlaceholderConst),
+}
+
+impl CanonicalVarKind {
+    pub fn universe(self) -> ty::UniverseIndex {
+        match self {
+            CanonicalVarKind::Ty(kind) => match kind {
+                CanonicalTyVarKind::General(ui) => ui,
+                CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
+            },
+
+            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
+            CanonicalVarKind::Region(ui) => ui,
+            CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
+            CanonicalVarKind::Const(ui) => ui,
+            CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe,
+        }
+    }
+}
+
+/// Rust actually has more than one category of type variables;
+/// notably, the type variables we create for literals (e.g., 22 or
+/// 22.) can only be instantiated with integral/float types (e.g.,
+/// usize or f32). In order to faithfully reproduce a type, we need to
+/// know what set of types a given type variable can be unified with.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
+pub enum CanonicalTyVarKind {
+    /// General type variable `?T` that can be unified with arbitrary types.
+    General(ty::UniverseIndex),
+
+    /// Integral type variable `?I` (that can only be unified with integral types).
+    Int,
+
+    /// Floating-point type variable `?F` (that can only be unified with float types).
+    Float,
+}
+
+/// After we execute a query with a canonicalized key, we get back a
+/// `Canonical<QueryResponse<..>>`. You can use
+/// `instantiate_query_result` to access the data in this result.
+#[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
+pub struct QueryResponse<'tcx, R> {
+    pub var_values: CanonicalVarValues<'tcx>,
+    pub region_constraints: QueryRegionConstraints<'tcx>,
+    pub certainty: Certainty,
+    pub value: R,
+}
+
+#[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
+pub struct QueryRegionConstraints<'tcx> {
+    pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
+    pub member_constraints: Vec<MemberConstraint<'tcx>>,
+}
+
+impl QueryRegionConstraints<'_> {
+    /// Represents an empty (trivially true) set of region
+    /// constraints.
+    pub fn is_empty(&self) -> bool {
+        self.outlives.is_empty() && self.member_constraints.is_empty()
+    }
+}
+
+pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>;
+
+pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
+
+/// Indicates whether or not we were able to prove the query to be
+/// true.
+#[derive(Copy, Clone, Debug, HashStable)]
+pub enum Certainty {
+    /// The query is known to be true, presuming that you apply the
+    /// given `var_values` and the region-constraints are satisfied.
+    Proven,
+
+    /// The query is not known to be true, but also not known to be
+    /// false. The `var_values` represent *either* values that must
+    /// hold in order for the query to be true, or helpful tips that
+    /// *might* make it true. Currently rustc's trait solver cannot
+    /// distinguish the two (e.g., due to our preference for where
+    /// clauses over impls).
+    ///
+    /// After some unifiations and things have been done, it makes
+    /// sense to try and prove again -- of course, at that point, the
+    /// canonical form will be different, making this a distinct
+    /// query.
+    Ambiguous,
+}
+
+impl Certainty {
+    pub fn is_proven(&self) -> bool {
+        match self {
+            Certainty::Proven => true,
+            Certainty::Ambiguous => false,
+        }
+    }
+
+    pub fn is_ambiguous(&self) -> bool {
+        !self.is_proven()
+    }
+}
+
+impl<'tcx, R> QueryResponse<'tcx, R> {
+    pub fn is_proven(&self) -> bool {
+        self.certainty.is_proven()
+    }
+
+    pub fn is_ambiguous(&self) -> bool {
+        !self.is_proven()
+    }
+}
+
+impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
+    pub fn is_proven(&self) -> bool {
+        self.value.is_proven()
+    }
+
+    pub fn is_ambiguous(&self) -> bool {
+        !self.is_proven()
+    }
+}
+
+impl<'tcx, V> Canonical<'tcx, V> {
+    /// Allows you to map the `value` of a canonical while keeping the
+    /// same set of bound variables.
+    ///
+    /// **WARNING:** This function is very easy to mis-use, hence the
+    /// name!  In particular, the new value `W` must use all **the
+    /// same type/region variables** in **precisely the same order**
+    /// as the original! (The ordering is defined by the
+    /// `TypeFoldable` implementation of the type in question.)
+    ///
+    /// An example of a **correct** use of this:
+    ///
+    /// ```rust,ignore (not real code)
+    /// let a: Canonical<'_, T> = ...;
+    /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
+    /// ```
+    ///
+    /// An example of an **incorrect** use of this:
+    ///
+    /// ```rust,ignore (not real code)
+    /// let a: Canonical<'tcx, T> = ...;
+    /// let ty: Ty<'tcx> = ...;
+    /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
+    /// ```
+    pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
+        let Canonical { max_universe, variables, value } = self;
+        Canonical { max_universe, variables, value: map_op(value) }
+    }
+}
+
+pub type QueryOutlivesConstraint<'tcx> =
+    ty::Binder<ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>;
+
+CloneTypeFoldableAndLiftImpls! {
+    crate::infer::canonical::Certainty,
+    crate::infer::canonical::CanonicalVarInfo,
+    crate::infer::canonical::CanonicalVarKind,
+}
+
+CloneTypeFoldableImpls! {
+    for <'tcx> {
+        crate::infer::canonical::CanonicalVarInfos<'tcx>,
+    }
+}
+
+impl<'tcx> CanonicalVarValues<'tcx> {
+    pub fn len(&self) -> usize {
+        self.var_values.len()
+    }
+
+    /// Makes an identity substitution from this one: each bound var
+    /// is matched to the same bound var, preserving the original kinds.
+    /// For example, if we have:
+    /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
+    /// we'll return a substitution `subst` with:
+    /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
+    pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
+        use crate::ty::subst::GenericArgKind;
+
+        CanonicalVarValues {
+            var_values: self
+                .var_values
+                .iter()
+                .zip(0..)
+                .map(|(kind, i)| match kind.unpack() {
+                    GenericArgKind::Type(..) => {
+                        tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
+                    }
+                    GenericArgKind::Lifetime(..) => tcx
+                        .mk_region(ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i)))
+                        .into(),
+                    GenericArgKind::Const(ct) => tcx
+                        .mk_const(ty::Const {
+                            ty: ct.ty,
+                            val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
+                        })
+                        .into(),
+                })
+                .collect(),
+        }
+    }
+}
+
+impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
+    type Item = GenericArg<'tcx>;
+    type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        self.var_values.iter().cloned()
+    }
+}
+
+impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
+    type Output = GenericArg<'tcx>;
+
+    fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
+        &self.var_values[value]
+    }
+}
diff --git a/src/librustc/infer/types/mod.rs b/src/librustc/infer/types/mod.rs
index f9346b99cde..534f4cb179c 100644
--- a/src/librustc/infer/types/mod.rs
+++ b/src/librustc/infer/types/mod.rs
@@ -1,3 +1,5 @@
+pub mod canonical;
+
 use crate::ty::Region;
 use crate::ty::Ty;
 use rustc_data_structures::sync::Lrc;