1 files changed, 275 insertions, 340 deletions

diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index 50d248674..e77f24e4e 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -25,32 +25,31 @@ mod test_db;
 
 use std::{iter, mem, ops::Deref, sync::Arc};
 
-use base_db::{salsa, CrateId};
+use base_db::salsa;
 use hir_def::{
-    builtin_type::BuiltinType,
-    expr::ExprId,
-    type_ref::{Mutability, Rawness},
-    AdtId, AssocContainerId, DefWithBodyId, FunctionId, GenericDefId, HasModule, LifetimeParamId,
-    Lookup, TraitId, TypeAliasId, TypeParamId,
+    builtin_type::BuiltinType, expr::ExprId, type_ref::Rawness, AssocContainerId, DefWithBodyId,
+    FunctionId, GenericDefId, HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId,
+    TypeParamId,
 };
 use itertools::Itertools;
 
 use crate::{
     db::HirDatabase,
     display::HirDisplay,
-    primitive::{FloatTy, IntTy},
     utils::{generics, make_mut_slice, Generics},
 };
 
 pub use autoderef::autoderef;
-pub use infer::{InferTy, InferenceResult};
+pub use infer::{InferenceResult, InferenceVar};
 pub use lower::{
     associated_type_shorthand_candidates, callable_item_sig, CallableDefId, ImplTraitLoweringMode,
     TyDefId, TyLoweringContext, ValueTyDefId,
 };
 pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
 
-pub use chalk_ir::{BoundVar, DebruijnIndex};
+pub use chalk_ir::{AdtId, BoundVar, DebruijnIndex, Mutability, Scalar, TyVariableKind};
+
+pub(crate) use crate::traits::chalk::Interner;
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub enum Lifetime {
@@ -58,211 +57,6 @@ pub enum Lifetime {
     Static,
 }
 
-/// A type constructor or type name: this might be something like the primitive
-/// type `bool`, a struct like `Vec`, or things like function pointers or
-/// tuples.
-#[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub enum TypeCtor {
-    /// The primitive boolean type. Written as `bool`.
-    Bool,
-
-    /// The primitive character type; holds a Unicode scalar value
-    /// (a non-surrogate code point). Written as `char`.
-    Char,
-
-    /// A primitive integer type. For example, `i32`.
-    Int(IntTy),
-
-    /// A primitive floating-point type. For example, `f64`.
-    Float(FloatTy),
-
-    /// Structures, enumerations and unions.
-    Adt(AdtId),
-
-    /// The pointee of a string slice. Written as `str`.
-    Str,
-
-    /// The pointee of an array slice.  Written as `[T]`.
-    Slice,
-
-    /// An array with the given length. Written as `[T; n]`.
-    Array,
-
-    /// A raw pointer. Written as `*mut T` or `*const T`
-    RawPtr(Mutability),
-
-    /// A reference; a pointer with an associated lifetime. Written as
-    /// `&'a mut T` or `&'a T`.
-    Ref(Mutability),
-
-    /// The anonymous type of a function declaration/definition. Each
-    /// function has a unique type, which is output (for a function
-    /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
-    ///
-    /// This includes tuple struct / enum variant constructors as well.
-    ///
-    /// For example the type of `bar` here:
-    ///
-    /// ```
-    /// fn foo() -> i32 { 1 }
-    /// let bar = foo; // bar: fn() -> i32 {foo}
-    /// ```
-    FnDef(CallableDefId),
-
-    /// A pointer to a function.  Written as `fn() -> i32`.
-    ///
-    /// For example the type of `bar` here:
-    ///
-    /// ```
-    /// fn foo() -> i32 { 1 }
-    /// let bar: fn() -> i32 = foo;
-    /// ```
-    // FIXME make this a Ty variant like in Chalk
-    FnPtr { num_args: u16, is_varargs: bool },
-
-    /// The never type `!`.
-    Never,
-
-    /// A tuple type.  For example, `(i32, bool)`.
-    Tuple { cardinality: u16 },
-
-    /// Represents an associated item like `Iterator::Item`.  This is used
-    /// when we have tried to normalize a projection like `T::Item` but
-    /// couldn't find a better representation.  In that case, we generate
-    /// an **application type** like `(Iterator::Item)<T>`.
-    AssociatedType(TypeAliasId),
-
-    /// This represents a placeholder for an opaque type in situations where we
-    /// don't know the hidden type (i.e. currently almost always). This is
-    /// analogous to the `AssociatedType` type constructor.
-    /// It is also used as the type of async block, with one type parameter
-    /// representing the Future::Output type.
-    OpaqueType(OpaqueTyId),
-
-    /// Represents a foreign type declared in external blocks.
-    ForeignType(TypeAliasId),
-
-    /// The type of a specific closure.
-    ///
-    /// The closure signature is stored in a `FnPtr` type in the first type
-    /// parameter.
-    Closure { def: DefWithBodyId, expr: ExprId },
-}
-
-impl TypeCtor {
-    pub fn num_ty_params(self, db: &dyn HirDatabase) -> usize {
-        match self {
-            TypeCtor::Bool
-            | TypeCtor::Char
-            | TypeCtor::Int(_)
-            | TypeCtor::Float(_)
-            | TypeCtor::Str
-            | TypeCtor::Never => 0,
-            TypeCtor::Slice
-            | TypeCtor::Array
-            | TypeCtor::RawPtr(_)
-            | TypeCtor::Ref(_)
-            | TypeCtor::Closure { .. } // 1 param representing the signature of the closure
-            => 1,
-            TypeCtor::Adt(adt) => {
-                let generic_params = generics(db.upcast(), adt.into());
-                generic_params.len()
-            }
-            TypeCtor::FnDef(callable) => {
-                let generic_params = generics(db.upcast(), callable.into());
-                generic_params.len()
-            }
-            TypeCtor::AssociatedType(type_alias) => {
-                let generic_params = generics(db.upcast(), type_alias.into());
-                generic_params.len()
-            }
-            TypeCtor::ForeignType(type_alias) => {
-                let generic_params = generics(db.upcast(), type_alias.into());
-                generic_params.len()
-            }
-            TypeCtor::OpaqueType(opaque_ty_id) => {
-                match opaque_ty_id {
-                    OpaqueTyId::ReturnTypeImplTrait(func, _) => {
-                        let generic_params = generics(db.upcast(), func.into());
-                        generic_params.len()
-                    }
-                    // 1 param representing Future::Output type.
-                    OpaqueTyId::AsyncBlockTypeImplTrait(..) => 1,
-                }
-            }
-            TypeCtor::FnPtr { num_args, is_varargs: _ } => num_args as usize + 1,
-            TypeCtor::Tuple { cardinality } => cardinality as usize,
-        }
-    }
-
-    pub fn krate(self, db: &dyn HirDatabase) -> Option<CrateId> {
-        match self {
-            TypeCtor::Bool
-            | TypeCtor::Char
-            | TypeCtor::Int(_)
-            | TypeCtor::Float(_)
-            | TypeCtor::Str
-            | TypeCtor::Never
-            | TypeCtor::Slice
-            | TypeCtor::Array
-            | TypeCtor::RawPtr(_)
-            | TypeCtor::Ref(_)
-            | TypeCtor::FnPtr { .. }
-            | TypeCtor::Tuple { .. } => None,
-            // Closure's krate is irrelevant for coherence I would think?
-            TypeCtor::Closure { .. } => None,
-            TypeCtor::Adt(adt) => Some(adt.module(db.upcast()).krate()),
-            TypeCtor::FnDef(callable) => Some(callable.krate(db)),
-            TypeCtor::AssociatedType(type_alias) => {
-                Some(type_alias.lookup(db.upcast()).module(db.upcast()).krate())
-            }
-            TypeCtor::ForeignType(type_alias) => {
-                Some(type_alias.lookup(db.upcast()).module(db.upcast()).krate())
-            }
-            TypeCtor::OpaqueType(opaque_ty_id) => match opaque_ty_id {
-                OpaqueTyId::ReturnTypeImplTrait(func, _) => {
-                    Some(func.lookup(db.upcast()).module(db.upcast()).krate())
-                }
-                OpaqueTyId::AsyncBlockTypeImplTrait(def, _) => {
-                    Some(def.module(db.upcast()).krate())
-                }
-            },
-        }
-    }
-
-    pub fn as_generic_def(self) -> Option<GenericDefId> {
-        match self {
-            TypeCtor::Bool
-            | TypeCtor::Char
-            | TypeCtor::Int(_)
-            | TypeCtor::Float(_)
-            | TypeCtor::Str
-            | TypeCtor::Never
-            | TypeCtor::Slice
-            | TypeCtor::Array
-            | TypeCtor::RawPtr(_)
-            | TypeCtor::Ref(_)
-            | TypeCtor::FnPtr { .. }
-            | TypeCtor::Tuple { .. }
-            | TypeCtor::Closure { .. } => None,
-            TypeCtor::Adt(adt) => Some(adt.into()),
-            TypeCtor::FnDef(callable) => Some(callable.into()),
-            TypeCtor::AssociatedType(type_alias) => Some(type_alias.into()),
-            TypeCtor::ForeignType(type_alias) => Some(type_alias.into()),
-            TypeCtor::OpaqueType(_impl_trait_id) => None,
-        }
-    }
-}
-
-/// A nominal type with (maybe 0) type parameters. This might be a primitive
-/// type like `bool`, a struct, tuple, function pointer, reference or
-/// several other things.
-#[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub struct ApplicationTy {
-    pub ctor: TypeCtor,
-    pub parameters: Substs,
-}
-
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct OpaqueTy {
     pub opaque_ty_id: OpaqueTyId,
@@ -305,29 +99,118 @@ impl TypeWalk for ProjectionTy {
     }
 }
 
-/// A type.
-///
-/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
-/// the same thing (but in a different way).
-///
-/// This should be cheap to clone.
+#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
+pub struct FnSig {
+    pub variadic: bool,
+}
+
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub enum Ty {
-    /// A nominal type with (maybe 0) type parameters. This might be a primitive
-    /// type like `bool`, a struct, tuple, function pointer, reference or
-    /// several other things.
-    Apply(ApplicationTy),
+pub struct FnPointer {
+    pub num_args: usize,
+    pub sig: FnSig,
+    pub substs: Substs,
+}
 
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub enum AliasTy {
     /// A "projection" type corresponds to an (unnormalized)
     /// projection like `<P0 as Trait<P1..Pn>>::Foo`. Note that the
     /// trait and all its parameters are fully known.
     Projection(ProjectionTy),
-
     /// An opaque type (`impl Trait`).
     ///
     /// This is currently only used for return type impl trait; each instance of
     /// `impl Trait` in a return type gets its own ID.
     Opaque(OpaqueTy),
+}
+
+/// A type.
+///
+/// See also the `TyKind` enum in rustc (librustc/ty/sty.rs), which represents
+/// the same thing (but in a different way).
+///
+/// This should be cheap to clone.
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub enum Ty {
+    /// Structures, enumerations and unions.
+    Adt(AdtId<Interner>, Substs),
+
+    /// Represents an associated item like `Iterator::Item`.  This is used
+    /// when we have tried to normalize a projection like `T::Item` but
+    /// couldn't find a better representation.  In that case, we generate
+    /// an **application type** like `(Iterator::Item)<T>`.
+    AssociatedType(TypeAliasId, Substs),
+
+    /// a scalar type like `bool` or `u32`
+    Scalar(Scalar),
+
+    /// A tuple type.  For example, `(i32, bool)`.
+    Tuple(usize, Substs),
+
+    /// An array with the given length. Written as `[T; n]`.
+    Array(Substs),
+
+    /// The pointee of an array slice.  Written as `[T]`.
+    Slice(Substs),
+
+    /// A raw pointer. Written as `*mut T` or `*const T`
+    Raw(Mutability, Substs),
+
+    /// A reference; a pointer with an associated lifetime. Written as
+    /// `&'a mut T` or `&'a T`.
+    Ref(Mutability, Substs),
+
+    /// This represents a placeholder for an opaque type in situations where we
+    /// don't know the hidden type (i.e. currently almost always). This is
+    /// analogous to the `AssociatedType` type constructor.
+    /// It is also used as the type of async block, with one type parameter
+    /// representing the Future::Output type.
+    OpaqueType(OpaqueTyId, Substs),
+
+    /// The anonymous type of a function declaration/definition. Each
+    /// function has a unique type, which is output (for a function
+    /// named `foo` returning an `i32`) as `fn() -> i32 {foo}`.
+    ///
+    /// This includes tuple struct / enum variant constructors as well.
+    ///
+    /// For example the type of `bar` here:
+    ///
+    /// ```
+    /// fn foo() -> i32 { 1 }
+    /// let bar = foo; // bar: fn() -> i32 {foo}
+    /// ```
+    FnDef(CallableDefId, Substs),
+
+    /// The pointee of a string slice. Written as `str`.
+    Str,
+
+    /// The never type `!`.
+    Never,
+
+    /// The type of a specific closure.
+    ///
+    /// The closure signature is stored in a `FnPtr` type in the first type
+    /// parameter.
+    Closure(DefWithBodyId, ExprId, Substs),
+
+    /// Represents a foreign type declared in external blocks.
+    ForeignType(TypeAliasId),
+
+    /// A pointer to a function.  Written as `fn() -> i32`.
+    ///
+    /// For example the type of `bar` here:
+    ///
+    /// ```
+    /// fn foo() -> i32 { 1 }
+    /// let bar: fn() -> i32 = foo;
+    /// ```
+    Function(FnPointer),
+
+    /// An "alias" type represents some form of type alias, such as:
+    /// - An associated type projection like `<T as Iterator>::Item`
+    /// - `impl Trait` types
+    /// - Named type aliases like `type Foo<X> = Vec<X>`
+    Alias(AliasTy),
 
     /// A placeholder for a type parameter; for example, `T` in `fn f<T>(x: T)
     /// {}` when we're type-checking the body of that function. In this
@@ -340,10 +223,10 @@ pub enum Ty {
     /// parameters get turned into variables; during trait resolution, inference
     /// variables get turned into bound variables and back; and in `Dyn` the
     /// `Self` type is represented with a bound variable as well.
-    Bound(BoundVar),
+    BoundVar(BoundVar),
 
     /// A type variable used during type checking.
-    Infer(InferTy),
+    InferenceVar(InferenceVar, TyVariableKind),
 
     /// A trait object (`dyn Trait` or bare `Trait` in pre-2018 Rust).
     ///
@@ -424,7 +307,7 @@ impl Substs {
             generic_params
                 .iter()
                 .enumerate()
-                .map(|(idx, _)| Ty::Bound(BoundVar::new(debruijn, idx)))
+                .map(|(idx, _)| Ty::BoundVar(BoundVar::new(debruijn, idx)))
                 .collect(),
         )
     }
@@ -440,10 +323,6 @@ impl Substs {
         Substs::builder(generic_params.len())
     }
 
-    pub fn build_for_type_ctor(db: &dyn HirDatabase, type_ctor: TypeCtor) -> SubstsBuilder {
-        Substs::builder(type_ctor.num_ty_params(db))
-    }
-
     fn builder(param_count: usize) -> SubstsBuilder {
         SubstsBuilder { vec: Vec::with_capacity(param_count), param_count }
     }
@@ -476,7 +355,7 @@ impl SubstsBuilder {
     }
 
     pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
-        self.fill((starting_from..).map(|idx| Ty::Bound(BoundVar::new(debruijn, idx))))
+        self.fill((starting_from..).map(|idx| Ty::BoundVar(BoundVar::new(debruijn, idx))))
     }
 
     pub fn fill_with_unknown(self) -> Self {
@@ -656,41 +535,41 @@ impl TypeWalk for GenericPredicate {
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct Canonical<T> {
     pub value: T,
-    pub kinds: Arc<[TyKind]>,
+    pub kinds: Arc<[TyVariableKind]>,
 }
 
 impl<T> Canonical<T> {
-    pub fn new(value: T, kinds: impl IntoIterator<Item = TyKind>) -> Self {
+    pub fn new(value: T, kinds: impl IntoIterator<Item = TyVariableKind>) -> Self {
         Self { value, kinds: kinds.into_iter().collect() }
     }
 }
 
-#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
-pub enum TyKind {
-    General,
-    Integer,
-    Float,
-}
-
 /// A function signature as seen by type inference: Several parameter types and
 /// one return type.
 #[derive(Clone, PartialEq, Eq, Debug)]
-pub struct FnSig {
+pub struct CallableSig {
     params_and_return: Arc<[Ty]>,
     is_varargs: bool,
 }
 
 /// A polymorphic function signature.
-pub type PolyFnSig = Binders<FnSig>;
+pub type PolyFnSig = Binders<CallableSig>;
 
-impl FnSig {
-    pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> FnSig {
+impl CallableSig {
+    pub fn from_params_and_return(mut params: Vec<Ty>, ret: Ty, is_varargs: bool) -> CallableSig {
         params.push(ret);
-        FnSig { params_and_return: params.into(), is_varargs }
+        CallableSig { params_and_return: params.into(), is_varargs }
+    }
+
+    pub fn from_fn_ptr(fn_ptr: &FnPointer) -> CallableSig {
+        CallableSig {
+            params_and_return: Arc::clone(&fn_ptr.substs.0),
+            is_varargs: fn_ptr.sig.variadic,
+        }
     }
 
-    pub fn from_fn_ptr_substs(substs: &Substs, is_varargs: bool) -> FnSig {
-        FnSig { params_and_return: Arc::clone(&substs.0), is_varargs }
+    pub fn from_substs(substs: &Substs) -> CallableSig {
+        CallableSig { params_and_return: Arc::clone(&substs.0), is_varargs: false }
     }
 
     pub fn params(&self) -> &[Ty] {
@@ -702,7 +581,7 @@ impl FnSig {
     }
 }
 
-impl TypeWalk for FnSig {
+impl TypeWalk for CallableSig {
     fn walk(&self, f: &mut impl FnMut(&Ty)) {
         for t in self.params_and_return.iter() {
             t.walk(f);
@@ -721,49 +600,46 @@ impl TypeWalk for FnSig {
 }
 
 impl Ty {
-    pub fn simple(ctor: TypeCtor) -> Ty {
-        Ty::Apply(ApplicationTy { ctor, parameters: Substs::empty() })
-    }
-    pub fn apply_one(ctor: TypeCtor, param: Ty) -> Ty {
-        Ty::Apply(ApplicationTy { ctor, parameters: Substs::single(param) })
-    }
-    pub fn apply(ctor: TypeCtor, parameters: Substs) -> Ty {
-        Ty::Apply(ApplicationTy { ctor, parameters })
-    }
     pub fn unit() -> Self {
-        Ty::apply(TypeCtor::Tuple { cardinality: 0 }, Substs::empty())
+        Ty::Tuple(0, Substs::empty())
     }
-    pub fn fn_ptr(sig: FnSig) -> Self {
-        Ty::apply(
-            TypeCtor::FnPtr { num_args: sig.params().len() as u16, is_varargs: sig.is_varargs },
-            Substs(sig.params_and_return),
-        )
+
+    pub fn adt_ty(adt: hir_def::AdtId, substs: Substs) -> Ty {
+        Ty::Adt(AdtId(adt), substs)
     }
-    pub fn builtin(builtin: BuiltinType) -> Self {
-        Ty::simple(match builtin {
-            BuiltinType::Char => TypeCtor::Char,
-            BuiltinType::Bool => TypeCtor::Bool,
-            BuiltinType::Str => TypeCtor::Str,
-            BuiltinType::Int(t) => TypeCtor::Int(IntTy::from(t).into()),
-            BuiltinType::Float(t) => TypeCtor::Float(FloatTy::from(t).into()),
+
+    pub fn fn_ptr(sig: CallableSig) -> Self {
+        Ty::Function(FnPointer {
+            num_args: sig.params().len(),
+            sig: FnSig { variadic: sig.is_varargs },
+            substs: Substs(sig.params_and_return),
         })
     }
 
+    pub fn builtin(builtin: BuiltinType) -> Self {
+        match builtin {
+            BuiltinType::Char => Ty::Scalar(Scalar::Char),
+            BuiltinType::Bool => Ty::Scalar(Scalar::Bool),
+            BuiltinType::Str => Ty::Str,
+            BuiltinType::Int(t) => Ty::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))),
+            BuiltinType::Uint(t) => Ty::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))),
+            BuiltinType::Float(t) => Ty::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))),
+        }
+    }
+
     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
         match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
-                Some((parameters.as_single(), *mutability))
-            }
+            Ty::Ref(mutability, parameters) => Some((parameters.as_single(), *mutability)),
             _ => None,
         }
     }
 
     pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
         match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(mutability), parameters }) => {
+            Ty::Ref(mutability, parameters) => {
                 Some((parameters.as_single(), Rawness::Ref, *mutability))
             }
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::RawPtr(mutability), parameters }) => {
+            Ty::Raw(mutability, parameters) => {
                 Some((parameters.as_single(), Rawness::RawPtr, *mutability))
             }
             _ => None,
@@ -773,39 +649,69 @@ impl Ty {
     pub fn strip_references(&self) -> &Ty {
         let mut t: &Ty = self;
 
-        while let Ty::Apply(ApplicationTy { ctor: TypeCtor::Ref(_mutability), parameters }) = t {
+        while let Ty::Ref(_mutability, parameters) = t {
             t = parameters.as_single();
         }
 
         t
     }
 
-    pub fn as_adt(&self) -> Option<(AdtId, &Substs)> {
+    pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substs)> {
         match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Adt(adt_def), parameters }) => {
-                Some((*adt_def, parameters))
-            }
+            Ty::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
             _ => None,
         }
     }
 
     pub fn as_tuple(&self) -> Option<&Substs> {
         match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::Tuple { .. }, parameters }) => {
-                Some(parameters)
-            }
+            Ty::Tuple(_, substs) => Some(substs),
+            _ => None,
+        }
+    }
+
+    pub fn as_generic_def(&self) -> Option<GenericDefId> {
+        match *self {
+            Ty::Adt(AdtId(adt), ..) => Some(adt.into()),
+            Ty::FnDef(callable, ..) => Some(callable.into()),
+            Ty::AssociatedType(type_alias, ..) => Some(type_alias.into()),
+            Ty::ForeignType(type_alias, ..) => Some(type_alias.into()),
             _ => None,
         }
     }
 
     pub fn is_never(&self) -> bool {
-        matches!(self, Ty::Apply(ApplicationTy { ctor: TypeCtor::Never, .. }))
+        matches!(self, Ty::Never)
     }
 
     pub fn is_unknown(&self) -> bool {
         matches!(self, Ty::Unknown)
     }
 
+    pub fn equals_ctor(&self, other: &Ty) -> bool {
+        match (self, other) {
+            (Ty::Adt(adt, ..), Ty::Adt(adt2, ..)) => adt == adt2,
+            (Ty::Slice(_), Ty::Slice(_)) | (Ty::Array(_), Ty::Array(_)) => true,
+            (Ty::FnDef(def_id, ..), Ty::FnDef(def_id2, ..)) => def_id == def_id2,
+            (Ty::OpaqueType(ty_id, ..), Ty::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
+            (Ty::AssociatedType(ty_id, ..), Ty::AssociatedType(ty_id2, ..))
+            | (Ty::ForeignType(ty_id, ..), Ty::ForeignType(ty_id2, ..)) => ty_id == ty_id2,
+            (Ty::Closure(def, expr, _), Ty::Closure(def2, expr2, _)) => {
+                expr == expr2 && def == def2
+            }
+            (Ty::Ref(mutability, ..), Ty::Ref(mutability2, ..))
+            | (Ty::Raw(mutability, ..), Ty::Raw(mutability2, ..)) => mutability == mutability2,
+            (
+                Ty::Function(FnPointer { num_args, sig, .. }),
+                Ty::Function(FnPointer { num_args: num_args2, sig: sig2, .. }),
+            ) => num_args == num_args2 && sig == sig2,
+            (Ty::Tuple(cardinality, _), Ty::Tuple(cardinality2, _)) => cardinality == cardinality2,
+            (Ty::Str, Ty::Str) | (Ty::Never, Ty::Never) => true,
+            (Ty::Scalar(scalar), Ty::Scalar(scalar2)) => scalar == scalar2,
+            _ => false,
+        }
+    }
+
     /// If this is a `dyn Trait` type, this returns the `Trait` part.
     pub fn dyn_trait_ref(&self) -> Option<&TraitRef> {
         match self {
@@ -824,41 +730,30 @@ impl Ty {
 
     fn builtin_deref(&self) -> Option<Ty> {
         match self {
-            Ty::Apply(a_ty) => match a_ty.ctor {
-                TypeCtor::Ref(..) => Some(Ty::clone(a_ty.parameters.as_single())),
-                TypeCtor::RawPtr(..) => Some(Ty::clone(a_ty.parameters.as_single())),
-                _ => None,
-            },
+            Ty::Ref(.., parameters) => Some(Ty::clone(parameters.as_single())),
+            Ty::Raw(.., parameters) => Some(Ty::clone(parameters.as_single())),
             _ => None,
         }
     }
 
     pub fn as_fn_def(&self) -> Option<FunctionId> {
         match self {
-            &Ty::Apply(ApplicationTy {
-                ctor: TypeCtor::FnDef(CallableDefId::FunctionId(func)),
-                ..
-            }) => Some(func),
+            &Ty::FnDef(CallableDefId::FunctionId(func), ..) => Some(func),
             _ => None,
         }
     }
 
-    pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<FnSig> {
+    pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
         match self {
-            Ty::Apply(a_ty) => match a_ty.ctor {
-                TypeCtor::FnPtr { is_varargs, .. } => {
-                    Some(FnSig::from_fn_ptr_substs(&a_ty.parameters, is_varargs))
-                }
-                TypeCtor::FnDef(def) => {
-                    let sig = db.callable_item_signature(def);
-                    Some(sig.subst(&a_ty.parameters))
-                }
-                TypeCtor::Closure { .. } => {
-                    let sig_param = &a_ty.parameters[0];
-                    sig_param.callable_sig(db)
-                }
-                _ => None,
-            },
+            Ty::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
+            Ty::FnDef(def, parameters) => {
+                let sig = db.callable_item_signature(*def);
+                Some(sig.subst(&parameters))
+            }
+            Ty::Closure(.., substs) => {
+                let sig_param = &substs[0];
+                sig_param.callable_sig(db)
+            }
             _ => None,
         }
     }
@@ -867,28 +762,66 @@ impl Ty {
     /// the `Substs` for these type parameters with the given ones. (So e.g. if
     /// `self` is `Option<_>` and the substs contain `u32`, we'll have
     /// `Option<u32>` afterwards.)
-    pub fn apply_substs(self, substs: Substs) -> Ty {
-        match self {
-            Ty::Apply(ApplicationTy { ctor, parameters: previous_substs }) => {
-                assert_eq!(previous_substs.len(), substs.len());
-                Ty::Apply(ApplicationTy { ctor, parameters: substs })
+    pub fn apply_substs(mut self, new_substs: Substs) -> Ty {
+        match &mut self {
+            Ty::Adt(_, substs)
+            | Ty::Slice(substs)
+            | Ty::Array(substs)
+            | Ty::Raw(_, substs)
+            | Ty::Ref(_, substs)
+            | Ty::FnDef(_, substs)
+            | Ty::Function(FnPointer { substs, .. })
+            | Ty::Tuple(_, substs)
+            | Ty::OpaqueType(_, substs)
+            | Ty::AssociatedType(_, substs)
+            | Ty::Closure(.., substs) => {
+                assert_eq!(substs.len(), new_substs.len());
+                *substs = new_substs;
             }
-            _ => self,
+            _ => (),
         }
+        self
     }
 
     /// Returns the type parameters of this type if it has some (i.e. is an ADT
     /// or function); so if `self` is `Option<u32>`, this returns the `u32`.
-    pub fn substs(&self) -> Option<Substs> {
+    pub fn substs(&self) -> Option<&Substs> {
         match self {
-            Ty::Apply(ApplicationTy { parameters, .. }) => Some(parameters.clone()),
+            Ty::Adt(_, substs)
+            | Ty::Slice(substs)
+            | Ty::Array(substs)
+            | Ty::Raw(_, substs)
+            | Ty::Ref(_, substs)
+            | Ty::FnDef(_, substs)
+            | Ty::Function(FnPointer { substs, .. })
+            | Ty::Tuple(_, substs)
+            | Ty::OpaqueType(_, substs)
+            | Ty::AssociatedType(_, substs)
+            | Ty::Closure(.., substs) => Some(substs),
+            _ => None,
+        }
+    }
+
+    pub fn substs_mut(&mut self) -> Option<&mut Substs> {
+        match self {
+            Ty::Adt(_, substs)
+            | Ty::Slice(substs)
+            | Ty::Array(substs)
+            | Ty::Raw(_, substs)
+            | Ty::Ref(_, substs)
+            | Ty::FnDef(_, substs)
+            | Ty::Function(FnPointer { substs, .. })
+            | Ty::Tuple(_, substs)
+            | Ty::OpaqueType(_, substs)
+            | Ty::AssociatedType(_, substs)
+            | Ty::Closure(.., substs) => Some(substs),
             _ => None,
         }
     }
 
     pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<GenericPredicate>> {
         match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::OpaqueType(opaque_ty_id), .. }) => {
+            Ty::OpaqueType(opaque_ty_id, ..) => {
                 match opaque_ty_id {
                     OpaqueTyId::AsyncBlockTypeImplTrait(def, _expr) => {
                         let krate = def.module(db.upcast()).krate();
@@ -911,7 +844,7 @@ impl Ty {
                     OpaqueTyId::ReturnTypeImplTrait(..) => None,
                 }
             }
-            Ty::Opaque(opaque_ty) => {
+            Ty::Alias(AliasTy::Opaque(opaque_ty)) => {
                 let predicates = match opaque_ty.opaque_ty_id {
                     OpaqueTyId::ReturnTypeImplTrait(func, idx) => {
                         db.return_type_impl_traits(func).map(|it| {
@@ -949,13 +882,13 @@ impl Ty {
 
     pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
         match self {
-            Ty::Apply(ApplicationTy { ctor: TypeCtor::AssociatedType(type_alias_id), .. }) => {
+            Ty::AssociatedType(type_alias_id, ..) => {
                 match type_alias_id.lookup(db.upcast()).container {
                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
                     _ => None,
                 }
             }
-            Ty::Projection(projection_ty) => {
+            Ty::Alias(AliasTy::Projection(projection_ty)) => {
                 match projection_ty.associated_ty.lookup(db.upcast()).container {
                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
                     _ => None,
@@ -1033,7 +966,7 @@ pub trait TypeWalk {
     {
         self.walk_mut_binders(
             &mut |ty, binders| {
-                if let &mut Ty::Bound(bound) = ty {
+                if let &mut Ty::BoundVar(bound) = ty {
                     if bound.debruijn >= binders {
                         *ty = substs.0[bound.index].clone().shift_bound_vars(binders);
                     }
@@ -1051,8 +984,8 @@ pub trait TypeWalk {
     {
         self.fold_binders(
             &mut |ty, binders| match ty {
-                Ty::Bound(bound) if bound.debruijn >= binders => {
-                    Ty::Bound(bound.shifted_in_from(n))
+                Ty::BoundVar(bound) if bound.debruijn >= binders => {
+                    Ty::BoundVar(bound.shifted_in_from(n))
                 }
                 ty => ty,
             },
@@ -1064,13 +997,13 @@ pub trait TypeWalk {
 impl TypeWalk for Ty {
     fn walk(&self, f: &mut impl FnMut(&Ty)) {
         match self {
-            Ty::Apply(a_ty) => {
-                for t in a_ty.parameters.iter() {
+            Ty::Alias(AliasTy::Projection(p_ty)) => {
+                for t in p_ty.parameters.iter() {
                     t.walk(f);
                 }
             }
-            Ty::Projection(p_ty) => {
-                for t in p_ty.parameters.iter() {
+            Ty::Alias(AliasTy::Opaque(o_ty)) => {
+                for t in o_ty.parameters.iter() {
                     t.walk(f);
                 }
             }
@@ -1079,12 +1012,13 @@ impl TypeWalk for Ty {
                     p.walk(f);
                 }
             }
-            Ty::Opaque(o_ty) => {
-                for t in o_ty.parameters.iter() {
-                    t.walk(f);
+            _ => {
+                if let Some(substs) = self.substs() {
+                    for t in substs.iter() {
+                        t.walk(f);
+                    }
                 }
             }
-            Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
         }
         f(self);
     }
@@ -1095,10 +1029,7 @@ impl TypeWalk for Ty {
         binders: DebruijnIndex,
     ) {
         match self {
-            Ty::Apply(a_ty) => {
-                a_ty.parameters.walk_mut_binders(f, binders);
-            }
-            Ty::Projection(p_ty) => {
+            Ty::Alias(AliasTy::Projection(p_ty)) => {
                 p_ty.parameters.walk_mut_binders(f, binders);
             }
             Ty::Dyn(predicates) => {
@@ -1106,10 +1037,14 @@ impl TypeWalk for Ty {
                     p.walk_mut_binders(f, binders.shifted_in());
                 }
             }
-            Ty::Opaque(o_ty) => {
+            Ty::Alias(AliasTy::Opaque(o_ty)) => {
                 o_ty.parameters.walk_mut_binders(f, binders);
             }
-            Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {}
+            _ => {
+                if let Some(substs) = self.substs_mut() {
+                    substs.walk_mut_binders(f, binders);
+                }
+            }
         }
         f(self, binders);
     }