Rollup merge of #117008 - compiler-errors:canonical, r=lcnr

Uplift `Canonical` to `rustc_type_ir`

I plan on moving the new trait solver's canonicalizer into either `rustc_type_ir` or a child crate. One dependency on this is lifting `Canonical<V>` to `rustc_type_ir` so we can actually name the canonicalized values.

I may also later lift `CanonicalVarInfo` into the new trait solver. I can't really tell what other changes need to be done, but I'm just putting this up sooner than later since I'm almost certain it'll need to be done regardless of other design choices.

There are a couple of warts introduced by this PR, since we no longer can define inherent `Canonical` impls in `rustc_middle` -- see the changes to:
* `compiler/rustc_trait_selection/src/traits/query/normalize.rs`
* `compiler/rustc_hir_typeck/src/fn_ctxt/_impl.rs`

r? lcnr

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>,