13 files changed, 207 insertions, 97 deletions

diff --git a/compiler/rustc_hir_typeck/src/fn_ctxt/_impl.rs b/compiler/rustc_hir_typeck/src/fn_ctxt/_impl.rs
index afa5a3b9379..b5a07f0d3e9 100644
--- a/compiler/rustc_hir_typeck/src/fn_ctxt/_impl.rs
+++ b/compiler/rustc_hir_typeck/src/fn_ctxt/_impl.rs
@@ -26,7 +26,7 @@ use rustc_middle::ty::error::TypeError;
 use rustc_middle::ty::fold::TypeFoldable;
 use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt};
 use rustc_middle::ty::{
-    self, AdtKind, CanonicalUserType, GenericParamDefKind, Ty, TyCtxt, UserType,
+    self, AdtKind, CanonicalUserType, GenericParamDefKind, IsIdentity, Ty, TyCtxt, UserType,
 };
 use rustc_middle::ty::{GenericArgKind, GenericArgsRef, UserArgs, UserSelfTy};
 use rustc_session::lint;
@@ -207,6 +207,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     ) {
         debug!("fcx {}", self.tag());
 
+        // FIXME: is_identity being on `UserType` and not `Canonical<UserType>` is awkward
         if !canonical_user_type_annotation.is_identity() {
             self.typeck_results
                 .borrow_mut()
diff --git a/compiler/rustc_middle/src/infer/canonical.rs b/compiler/rustc_middle/src/infer/canonical.rs
index c8f3c2a20a6..0b5426c3bb1 100644
--- a/compiler/rustc_middle/src/infer/canonical.rs
+++ b/compiler/rustc_middle/src/infer/canonical.rs
@@ -21,35 +21,17 @@
 //!
 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
 
-use crate::infer::MemberConstraint;
-use crate::mir::ConstraintCategory;
-use crate::ty::GenericArg;
-use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt};
 use rustc_macros::HashStable;
+use rustc_type_ir::Canonical as IrCanonical;
 use smallvec::SmallVec;
-use std::fmt::Display;
 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, TyDecodable, TyEncodable)]
-#[derive(HashStable, TypeFoldable, TypeVisitable)]
-pub struct Canonical<'tcx, V> {
-    pub value: V,
-    pub max_universe: ty::UniverseIndex,
-    pub variables: CanonicalVarInfos<'tcx>,
-}
+use crate::infer::MemberConstraint;
+use crate::mir::ConstraintCategory;
+use crate::ty::GenericArg;
+use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt};
 
-impl<'tcx, V: Display> std::fmt::Display for Canonical<'tcx, V> {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        write!(
-            f,
-            "Canonical {{ value: {}, max_universe: {:?}, variables: {:?} }}",
-            self.value, self.max_universe, self.variables
-        )
-    }
-}
+pub type Canonical<'tcx, V> = IrCanonical<TyCtxt<'tcx>, V>;
 
 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo<'tcx>>;
 
@@ -379,56 +361,6 @@ impl<'tcx, R> QueryResponse<'tcx, R> {
     }
 }
 
-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) }
-    }
-
-    /// 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! See
-    /// the comment of [Canonical::unchecked_map] for more details.
-    pub fn unchecked_rebind<W>(self, value: W) -> Canonical<'tcx, W> {
-        let Canonical { max_universe, variables, value: _ } = self;
-        Canonical { max_universe, variables, value }
-    }
-}
-
 pub type QueryOutlivesConstraint<'tcx> =
     (ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>, ConstraintCategory<'tcx>);
 
diff --git a/compiler/rustc_middle/src/ty/context.rs b/compiler/rustc_middle/src/ty/context.rs
index 6a9a8bcdc06..a669ff8d961 100644
--- a/compiler/rustc_middle/src/ty/context.rs
+++ b/compiler/rustc_middle/src/ty/context.rs
@@ -6,7 +6,7 @@ pub mod tls;
 
 use crate::arena::Arena;
 use crate::dep_graph::{DepGraph, DepKindStruct};
-use crate::infer::canonical::CanonicalVarInfo;
+use crate::infer::canonical::{CanonicalVarInfo, CanonicalVarInfos};
 use crate::lint::struct_lint_level;
 use crate::metadata::ModChild;
 use crate::middle::codegen_fn_attrs::CodegenFnAttrs;
@@ -88,6 +88,7 @@ impl<'tcx> Interner for TyCtxt<'tcx> {
 
     type Binder<T> = Binder<'tcx, T>;
     type TypeAndMut = TypeAndMut<'tcx>;
+    type CanonicalVars = CanonicalVarInfos<'tcx>;
 
     type Ty = Ty<'tcx>;
     type Tys = &'tcx List<Ty<'tcx>>;
diff --git a/compiler/rustc_middle/src/ty/mod.rs b/compiler/rustc_middle/src/ty/mod.rs
index cc0db39ac57..5d6d46e16b7 100644
--- a/compiler/rustc_middle/src/ty/mod.rs
+++ b/compiler/rustc_middle/src/ty/mod.rs
@@ -106,8 +106,8 @@ pub use self::sty::{
 };
 pub use self::trait_def::TraitDef;
 pub use self::typeck_results::{
-    CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, TypeckResults,
-    UserType, UserTypeAnnotationIndex,
+    CanonicalUserType, CanonicalUserTypeAnnotation, CanonicalUserTypeAnnotations, IsIdentity,
+    TypeckResults, UserType, UserTypeAnnotationIndex,
 };
 
 pub mod _match;
diff --git a/compiler/rustc_middle/src/ty/structural_impls.rs b/compiler/rustc_middle/src/ty/structural_impls.rs
index 7f86acd4bf5..6af68bc5dba 100644
--- a/compiler/rustc_middle/src/ty/structural_impls.rs
+++ b/compiler/rustc_middle/src/ty/structural_impls.rs
@@ -449,7 +449,6 @@ TrivialTypeTraversalImpls! {
     crate::ty::IntVarValue,
     crate::ty::adjustment::PointerCoercion,
     crate::ty::RegionVid,
-    crate::ty::UniverseIndex,
     crate::ty::Variance,
     ::rustc_span::Span,
     ::rustc_span::symbol::Ident,
diff --git a/compiler/rustc_middle/src/ty/typeck_results.rs b/compiler/rustc_middle/src/ty/typeck_results.rs
index 7d516410b20..58ad1eb900f 100644
--- a/compiler/rustc_middle/src/ty/typeck_results.rs
+++ b/compiler/rustc_middle/src/ty/typeck_results.rs
@@ -594,10 +594,27 @@ pub struct CanonicalUserTypeAnnotation<'tcx> {
 /// Canonical user type annotation.
 pub type CanonicalUserType<'tcx> = Canonical<'tcx, UserType<'tcx>>;
 
-impl<'tcx> CanonicalUserType<'tcx> {
+/// A user-given type annotation attached to a constant. These arise
+/// from constants that are named via paths, like `Foo::<A>::new` and
+/// so forth.
+#[derive(Copy, Clone, Debug, PartialEq, TyEncodable, TyDecodable)]
+#[derive(Eq, Hash, HashStable, TypeFoldable, TypeVisitable)]
+pub enum UserType<'tcx> {
+    Ty(Ty<'tcx>),
+
+    /// The canonical type is the result of `type_of(def_id)` with the
+    /// given substitutions applied.
+    TypeOf(DefId, UserArgs<'tcx>),
+}
+
+pub trait IsIdentity {
+    fn is_identity(&self) -> bool;
+}
+
+impl<'tcx> IsIdentity for CanonicalUserType<'tcx> {
     /// Returns `true` if this represents a substitution of the form `[?0, ?1, ?2]`,
     /// i.e., each thing is mapped to a canonical variable with the same index.
-    pub fn is_identity(&self) -> bool {
+    fn is_identity(&self) -> bool {
         match self.value {
             UserType::Ty(_) => false,
             UserType::TypeOf(_, user_args) => {
@@ -640,19 +657,6 @@ impl<'tcx> CanonicalUserType<'tcx> {
     }
 }
 
-/// A user-given type annotation attached to a constant. These arise
-/// from constants that are named via paths, like `Foo::<A>::new` and
-/// so forth.
-#[derive(Copy, Clone, Debug, PartialEq, TyEncodable, TyDecodable)]
-#[derive(Eq, Hash, HashStable, TypeFoldable, TypeVisitable)]
-pub enum UserType<'tcx> {
-    Ty(Ty<'tcx>),
-
-    /// The canonical type is the result of `type_of(def_id)` with the
-    /// given substitutions applied.
-    TypeOf(DefId, UserArgs<'tcx>),
-}
-
 impl<'tcx> std::fmt::Display for UserType<'tcx> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
index 349741a698c..c761d0d103e 100644
--- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
@@ -293,7 +293,7 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx>
                     _ => unreachable!(),
                 }?;
                 // We don't expect ambiguity.
-                if result.is_ambiguous() {
+                if !result.value.is_proven() {
                     // Rustdoc normalizes possibly not well-formed types, so only
                     // treat this as a bug if we're not in rustdoc.
                     if !tcx.sess.opts.actually_rustdoc {
diff --git a/compiler/rustc_type_ir/src/canonical.rs b/compiler/rustc_type_ir/src/canonical.rs
new file mode 100644
index 00000000000..c0b6aed98ef
--- /dev/null
+++ b/compiler/rustc_type_ir/src/canonical.rs
@@ -0,0 +1,169 @@
+use std::fmt;
+use std::hash;
+use std::ops::ControlFlow;
+
+use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
+use rustc_serialize::{Decodable, Encodable};
+
+use crate::fold::{FallibleTypeFolder, TypeFoldable};
+use crate::visit::{TypeVisitable, TypeVisitor};
+use crate::TyDecoder;
+use crate::{HashStableContext, Interner, TyEncoder, UniverseIndex};
+
+/// 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.
+pub struct Canonical<I: Interner, V> {
+    pub value: V,
+    pub max_universe: UniverseIndex,
+    pub variables: I::CanonicalVars,
+}
+
+impl<I: Interner, V> Canonical<I, 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<I, T> = ...;
+    /// let b: Canonical<I, (T,)> = a.unchecked_map(|v| (v, ));
+    /// ```
+    ///
+    /// An example of an **incorrect** use of this:
+    ///
+    /// ```rust,ignore (not real code)
+    /// let a: Canonical<I, T> = ...;
+    /// let ty: Ty<I> = ...;
+    /// let b: Canonical<I, (T, Ty<I>)> = a.unchecked_map(|v| (v, ty));
+    /// ```
+    pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<I, W> {
+        let Canonical { max_universe, variables, value } = self;
+        Canonical { max_universe, variables, value: map_op(value) }
+    }
+
+    /// 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! See
+    /// the comment of [Canonical::unchecked_map] for more details.
+    pub fn unchecked_rebind<W>(self, value: W) -> Canonical<I, W> {
+        let Canonical { max_universe, variables, value: _ } = self;
+        Canonical { max_universe, variables, value }
+    }
+}
+
+impl<I: Interner, V: hash::Hash> hash::Hash for Canonical<I, V> {
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        self.value.hash(state);
+        self.max_universe.hash(state);
+        self.variables.hash(state);
+    }
+}
+
+impl<CTX: HashStableContext, I: Interner, V: HashStable<CTX>> HashStable<CTX> for Canonical<I, V>
+where
+    I::CanonicalVars: HashStable<CTX>,
+{
+    fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) {
+        self.value.hash_stable(hcx, hasher);
+        self.max_universe.hash_stable(hcx, hasher);
+        self.variables.hash_stable(hcx, hasher);
+    }
+}
+
+impl<I: Interner, V: Eq> Eq for Canonical<I, V> {}
+
+impl<I: Interner, V: PartialEq> PartialEq for Canonical<I, V> {
+    fn eq(&self, other: &Self) -> bool {
+        self.value == other.value
+            && self.max_universe == other.max_universe
+            && self.variables == other.variables
+    }
+}
+
+impl<I: Interner, V: fmt::Display> fmt::Display for Canonical<I, V> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "Canonical {{ value: {}, max_universe: {:?}, variables: {:?} }}",
+            self.value, self.max_universe, self.variables
+        )
+    }
+}
+
+impl<I: Interner, V: fmt::Debug> fmt::Debug for Canonical<I, V> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.debug_struct("Canonical")
+            .field("value", &self.value)
+            .field("max_universe", &self.max_universe)
+            .field("variables", &self.variables)
+            .finish()
+    }
+}
+
+impl<I: Interner, V: Clone> Clone for Canonical<I, V> {
+    fn clone(&self) -> Self {
+        Canonical {
+            value: self.value.clone(),
+            max_universe: self.max_universe.clone(),
+            variables: self.variables.clone(),
+        }
+    }
+}
+
+impl<I: Interner, V: Copy> Copy for Canonical<I, V> where I::CanonicalVars: Copy {}
+
+impl<I: Interner, V: TypeFoldable<I>> TypeFoldable<I> for Canonical<I, V>
+where
+    I::CanonicalVars: TypeFoldable<I>,
+{
+    fn try_fold_with<F: FallibleTypeFolder<I>>(self, folder: &mut F) -> Result<Self, F::Error> {
+        Ok(Canonical {
+            value: self.value.try_fold_with(folder)?,
+            max_universe: self.max_universe.try_fold_with(folder)?,
+            variables: self.variables.try_fold_with(folder)?,
+        })
+    }
+}
+
+impl<I: Interner, V: TypeVisitable<I>> TypeVisitable<I> for Canonical<I, V>
+where
+    I::CanonicalVars: TypeVisitable<I>,
+{
+    fn visit_with<F: TypeVisitor<I>>(&self, folder: &mut F) -> ControlFlow<F::BreakTy> {
+        self.value.visit_with(folder)?;
+        self.max_universe.visit_with(folder)?;
+        self.variables.visit_with(folder)
+    }
+}
+
+impl<I: Interner, E: TyEncoder<I = I>, V: Encodable<E>> Encodable<E> for Canonical<I, V>
+where
+    I::CanonicalVars: Encodable<E>,
+{
+    fn encode(&self, s: &mut E) {
+        self.value.encode(s);
+        self.max_universe.encode(s);
+        self.variables.encode(s);
+    }
+}
+
+impl<I: Interner, D: TyDecoder<I = I>, V: Decodable<D>> Decodable<D> for Canonical<I, V>
+where
+    I::CanonicalVars: Decodable<D>,
+{
+    fn decode(d: &mut D) -> Self {
+        Canonical {
+            value: Decodable::decode(d),
+            max_universe: Decodable::decode(d),
+            variables: Decodable::decode(d),
+        }
+    }
+}
diff --git a/compiler/rustc_type_ir/src/interner.rs b/compiler/rustc_type_ir/src/interner.rs
index 6e5d3ee0b6d..7f75e5b35a2 100644
--- a/compiler/rustc_type_ir/src/interner.rs
+++ b/compiler/rustc_type_ir/src/interner.rs
@@ -18,6 +18,7 @@ pub trait Interner: Sized {
 
     type Binder<T>;
     type TypeAndMut: Clone + Debug + Hash + Ord;
+    type CanonicalVars: Clone + Debug + Hash + Eq;
 
     // Kinds of tys
     type Ty: Clone + DebugWithInfcx<Self> + Hash + Ord;
diff --git a/compiler/rustc_type_ir/src/lib.rs b/compiler/rustc_type_ir/src/lib.rs
index 3494b24f060..a056fbeda98 100644
--- a/compiler/rustc_type_ir/src/lib.rs
+++ b/compiler/rustc_type_ir/src/lib.rs
@@ -26,6 +26,7 @@ pub mod visit;
 
 #[macro_use]
 mod macros;
+mod canonical;
 mod const_kind;
 mod debug;
 mod flags;
@@ -33,6 +34,7 @@ mod interner;
 mod predicate_kind;
 mod region_kind;
 
+pub use canonical::*;
 pub use codec::*;
 pub use const_kind::*;
 pub use debug::{DebugWithInfcx, InferCtxtLike, WithInfcx};
diff --git a/compiler/rustc_type_ir/src/macros.rs b/compiler/rustc_type_ir/src/macros.rs
index 88314aca6f3..cfed84a35c6 100644
--- a/compiler/rustc_type_ir/src/macros.rs
+++ b/compiler/rustc_type_ir/src/macros.rs
@@ -50,4 +50,5 @@ TrivialTypeTraversalImpls! {
     String,
     crate::DebruijnIndex,
     crate::AliasRelationDirection,
+    crate::UniverseIndex,
 }
diff --git a/compiler/rustc_type_ir/src/region_kind.rs b/compiler/rustc_type_ir/src/region_kind.rs
index 60b90f4fae3..19576ea58f1 100644
--- a/compiler/rustc_type_ir/src/region_kind.rs
+++ b/compiler/rustc_type_ir/src/region_kind.rs
@@ -307,7 +307,7 @@ impl<I: Interner> fmt::Debug for RegionKind<I> {
 }
 
 // This is manually implemented because a derive would require `I: Encodable`
-impl<I: Interner, E: TyEncoder> Encodable<E> for RegionKind<I>
+impl<I: Interner, E: TyEncoder<I = I>> Encodable<E> for RegionKind<I>
 where
     I::EarlyBoundRegion: Encodable<E>,
     I::BoundRegion: Encodable<E>,
diff --git a/compiler/rustc_type_ir/src/ty_kind.rs b/compiler/rustc_type_ir/src/ty_kind.rs
index 2128666c2a4..b542547589a 100644
--- a/compiler/rustc_type_ir/src/ty_kind.rs
+++ b/compiler/rustc_type_ir/src/ty_kind.rs
@@ -622,7 +622,7 @@ impl<I: Interner> fmt::Debug for TyKind<I> {
 }
 
 // This is manually implemented because a derive would require `I: Encodable`
-impl<I: Interner, E: TyEncoder> Encodable<E> for TyKind<I>
+impl<I: Interner, E: TyEncoder<I = I>> Encodable<E> for TyKind<I>
 where
     I::ErrorGuaranteed: Encodable<E>,
     I::AdtDef: Encodable<E>,