1 files changed, 249 insertions, 186 deletions

diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index e77f24e4e..503910dde 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -27,9 +27,8 @@ use std::{iter, mem, ops::Deref, sync::Arc};
 
 use base_db::salsa;
 use hir_def::{
-    builtin_type::BuiltinType, expr::ExprId, type_ref::Rawness, AssocContainerId, DefWithBodyId,
-    FunctionId, GenericDefId, HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId,
-    TypeParamId,
+    builtin_type::BuiltinType, expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId,
+    GenericDefId, HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
 };
 use itertools::Itertools;
 
@@ -47,9 +46,16 @@ pub use lower::{
 };
 pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment};
 
-pub use chalk_ir::{AdtId, BoundVar, DebruijnIndex, Mutability, Scalar, TyVariableKind};
+pub use chalk_ir::{AdtId, BoundVar, DebruijnIndex, Mutability, Safety, Scalar, TyVariableKind};
 
-pub(crate) use crate::traits::chalk::Interner;
+pub use crate::traits::chalk::Interner;
+
+pub type ForeignDefId = chalk_ir::ForeignDefId<Interner>;
+pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
+pub type FnDefId = chalk_ir::FnDefId<Interner>;
+pub type ClosureId = chalk_ir::ClosureId<Interner>;
+pub type OpaqueTyId = chalk_ir::OpaqueTyId<Interner>;
+pub type PlaceholderIndex = chalk_ir::PlaceholderIndex;
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub enum Lifetime {
@@ -60,7 +66,7 @@ pub enum Lifetime {
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct OpaqueTy {
     pub opaque_ty_id: OpaqueTyId,
-    pub parameters: Substs,
+    pub substitution: Substs,
 }
 
 /// A "projection" type corresponds to an (unnormalized)
@@ -68,17 +74,17 @@ pub struct OpaqueTy {
 /// trait and all its parameters are fully known.
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct ProjectionTy {
-    pub associated_ty: TypeAliasId,
-    pub parameters: Substs,
+    pub associated_ty_id: AssocTypeId,
+    pub substitution: Substs,
 }
 
 impl ProjectionTy {
     pub fn trait_ref(&self, db: &dyn HirDatabase) -> TraitRef {
-        TraitRef { trait_: self.trait_(db), substs: self.parameters.clone() }
+        TraitRef { trait_: self.trait_(db), substs: self.substitution.clone() }
     }
 
     fn trait_(&self, db: &dyn HirDatabase) -> TraitId {
-        match self.associated_ty.lookup(db.upcast()).container {
+        match from_assoc_type_id(self.associated_ty_id).lookup(db.upcast()).container {
             AssocContainerId::TraitId(it) => it,
             _ => panic!("projection ty without parent trait"),
         }
@@ -87,7 +93,7 @@ impl ProjectionTy {
 
 impl TypeWalk for ProjectionTy {
     fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        self.parameters.walk(f);
+        self.substitution.walk(f);
     }
 
     fn walk_mut_binders(
@@ -95,14 +101,11 @@ impl TypeWalk for ProjectionTy {
         f: &mut impl FnMut(&mut Ty, DebruijnIndex),
         binders: DebruijnIndex,
     ) {
-        self.parameters.walk_mut_binders(f, binders);
+        self.substitution.walk_mut_binders(f, binders);
     }
 }
 
-#[derive(Clone, Copy, PartialEq, Eq, Debug, Hash)]
-pub struct FnSig {
-    pub variadic: bool,
-}
+pub type FnSig = chalk_ir::FnSig<Interner>;
 
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct FnPointer {
@@ -131,7 +134,7 @@ pub enum AliasTy {
 ///
 /// This should be cheap to clone.
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
-pub enum Ty {
+pub enum TyKind {
     /// Structures, enumerations and unions.
     Adt(AdtId<Interner>, Substs),
 
@@ -139,7 +142,7 @@ pub enum Ty {
     /// 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),
+    AssociatedType(AssocTypeId, Substs),
 
     /// a scalar type like `bool` or `u32`
     Scalar(Scalar),
@@ -148,17 +151,17 @@ pub enum Ty {
     Tuple(usize, Substs),
 
     /// An array with the given length. Written as `[T; n]`.
-    Array(Substs),
+    Array(Ty),
 
     /// The pointee of an array slice.  Written as `[T]`.
-    Slice(Substs),
+    Slice(Ty),
 
     /// A raw pointer. Written as `*mut T` or `*const T`
-    Raw(Mutability, Substs),
+    Raw(Mutability, Ty),
 
     /// A reference; a pointer with an associated lifetime. Written as
     /// `&'a mut T` or `&'a T`.
-    Ref(Mutability, Substs),
+    Ref(Mutability, Ty),
 
     /// 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
@@ -179,7 +182,7 @@ pub enum Ty {
     /// fn foo() -> i32 { 1 }
     /// let bar = foo; // bar: fn() -> i32 {foo}
     /// ```
-    FnDef(CallableDefId, Substs),
+    FnDef(FnDefId, Substs),
 
     /// The pointee of a string slice. Written as `str`.
     Str,
@@ -191,10 +194,10 @@ pub enum Ty {
     ///
     /// The closure signature is stored in a `FnPtr` type in the first type
     /// parameter.
-    Closure(DefWithBodyId, ExprId, Substs),
+    Closure(ClosureId, Substs),
 
     /// Represents a foreign type declared in external blocks.
-    ForeignType(TypeAliasId),
+    ForeignType(ForeignDefId),
 
     /// A pointer to a function.  Written as `fn() -> i32`.
     ///
@@ -216,7 +219,7 @@ pub enum Ty {
     /// {}` when we're type-checking the body of that function. In this
     /// situation, we know this stands for *some* type, but don't know the exact
     /// type.
-    Placeholder(TypeParamId),
+    Placeholder(PlaceholderIndex),
 
     /// A bound type variable. This is used in various places: when representing
     /// some polymorphic type like the type of function `fn f<T>`, the type
@@ -244,6 +247,29 @@ pub enum Ty {
     Unknown,
 }
 
+#[derive(Clone, PartialEq, Eq, Debug, Hash)]
+pub struct Ty(Arc<TyKind>);
+
+impl TyKind {
+    pub fn intern(self, _interner: &Interner) -> Ty {
+        Ty(Arc::new(self))
+    }
+}
+
+impl Ty {
+    pub fn interned(&self, _interner: &Interner) -> &TyKind {
+        &self.0
+    }
+
+    pub fn interned_mut(&mut self) -> &mut TyKind {
+        Arc::make_mut(&mut self.0)
+    }
+
+    pub fn into_inner(self) -> TyKind {
+        Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone())
+    }
+}
+
 /// A list of substitutions for generic parameters.
 #[derive(Clone, PartialEq, Eq, Debug, Hash)]
 pub struct Substs(Arc<[Ty]>);
@@ -291,14 +317,22 @@ impl Substs {
     }
 
     /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
-    pub(crate) fn type_params_for_generics(generic_params: &Generics) -> Substs {
-        Substs(generic_params.iter().map(|(id, _)| Ty::Placeholder(id)).collect())
+    pub(crate) fn type_params_for_generics(
+        db: &dyn HirDatabase,
+        generic_params: &Generics,
+    ) -> Substs {
+        Substs(
+            generic_params
+                .iter()
+                .map(|(id, _)| TyKind::Placeholder(to_placeholder_idx(db, id)).intern(&Interner))
+                .collect(),
+        )
     }
 
     /// Return Substs that replace each parameter by itself (i.e. `Ty::Param`).
     pub fn type_params(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substs {
         let params = generics(db.upcast(), def.into());
-        Substs::type_params_for_generics(&params)
+        Substs::type_params_for_generics(db, &params)
     }
 
     /// Return Substs that replace each parameter by a bound variable.
@@ -307,7 +341,7 @@ impl Substs {
             generic_params
                 .iter()
                 .enumerate()
-                .map(|(idx, _)| Ty::BoundVar(BoundVar::new(debruijn, idx)))
+                .map(|(idx, _)| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner))
                 .collect(),
         )
     }
@@ -355,11 +389,14 @@ impl SubstsBuilder {
     }
 
     pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
-        self.fill((starting_from..).map(|idx| Ty::BoundVar(BoundVar::new(debruijn, idx))))
+        self.fill(
+            (starting_from..)
+                .map(|idx| TyKind::BoundVar(BoundVar::new(debruijn, idx)).intern(&Interner)),
+        )
     }
 
     pub fn fill_with_unknown(self) -> Self {
-        self.fill(iter::repeat(Ty::Unknown))
+        self.fill(iter::repeat(TyKind::Unknown.intern(&Interner)))
     }
 
     pub fn fill(mut self, filler: impl Iterator<Item = Ty>) -> Self {
@@ -601,47 +638,50 @@ impl TypeWalk for CallableSig {
 
 impl Ty {
     pub fn unit() -> Self {
-        Ty::Tuple(0, Substs::empty())
+        TyKind::Tuple(0, Substs::empty()).intern(&Interner)
     }
 
     pub fn adt_ty(adt: hir_def::AdtId, substs: Substs) -> Ty {
-        Ty::Adt(AdtId(adt), substs)
+        TyKind::Adt(AdtId(adt), substs).intern(&Interner)
     }
 
     pub fn fn_ptr(sig: CallableSig) -> Self {
-        Ty::Function(FnPointer {
+        TyKind::Function(FnPointer {
             num_args: sig.params().len(),
-            sig: FnSig { variadic: sig.is_varargs },
+            sig: FnSig { abi: (), safety: Safety::Safe, variadic: sig.is_varargs },
             substs: Substs(sig.params_and_return),
         })
+        .intern(&Interner)
     }
 
     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))),
+            BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(&Interner),
+            BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(&Interner),
+            BuiltinType::Str => TyKind::Str.intern(&Interner),
+            BuiltinType::Int(t) => {
+                TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(&Interner)
+            }
+            BuiltinType::Uint(t) => {
+                TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(&Interner)
+            }
+            BuiltinType::Float(t) => {
+                TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(&Interner)
+            }
         }
     }
 
     pub fn as_reference(&self) -> Option<(&Ty, Mutability)> {
-        match self {
-            Ty::Ref(mutability, parameters) => Some((parameters.as_single(), *mutability)),
+        match self.interned(&Interner) {
+            TyKind::Ref(mutability, ty) => Some((ty, *mutability)),
             _ => None,
         }
     }
 
     pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
-        match self {
-            Ty::Ref(mutability, parameters) => {
-                Some((parameters.as_single(), Rawness::Ref, *mutability))
-            }
-            Ty::Raw(mutability, parameters) => {
-                Some((parameters.as_single(), Rawness::RawPtr, *mutability))
-            }
+        match self.interned(&Interner) {
+            TyKind::Ref(mutability, ty) => Some((ty, Rawness::Ref, *mutability)),
+            TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
             _ => None,
         }
     }
@@ -649,73 +689,79 @@ impl Ty {
     pub fn strip_references(&self) -> &Ty {
         let mut t: &Ty = self;
 
-        while let Ty::Ref(_mutability, parameters) = t {
-            t = parameters.as_single();
+        while let TyKind::Ref(_mutability, ty) = t.interned(&Interner) {
+            t = ty;
         }
 
         t
     }
 
     pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substs)> {
-        match self {
-            Ty::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
+        match self.interned(&Interner) {
+            TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
             _ => None,
         }
     }
 
     pub fn as_tuple(&self) -> Option<&Substs> {
-        match self {
-            Ty::Tuple(_, substs) => Some(substs),
+        match self.interned(&Interner) {
+            TyKind::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()),
+    pub fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
+        match *self.interned(&Interner) {
+            TyKind::Adt(AdtId(adt), ..) => Some(adt.into()),
+            TyKind::FnDef(callable, ..) => {
+                Some(db.lookup_intern_callable_def(callable.into()).into())
+            }
+            TyKind::AssociatedType(type_alias, ..) => Some(from_assoc_type_id(type_alias).into()),
+            TyKind::ForeignType(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
             _ => None,
         }
     }
 
     pub fn is_never(&self) -> bool {
-        matches!(self, Ty::Never)
+        matches!(self.interned(&Interner), TyKind::Never)
     }
 
     pub fn is_unknown(&self) -> bool {
-        matches!(self, Ty::Unknown)
+        matches!(self.interned(&Interner), TyKind::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
+        match (self.interned(&Interner), other.interned(&Interner)) {
+            (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
+            (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_), TyKind::Array(_)) => true,
+            (TyKind::FnDef(def_id, ..), TyKind::FnDef(def_id2, ..)) => def_id == def_id2,
+            (TyKind::OpaqueType(ty_id, ..), TyKind::OpaqueType(ty_id2, ..)) => ty_id == ty_id2,
+            (TyKind::AssociatedType(ty_id, ..), TyKind::AssociatedType(ty_id2, ..)) => {
+                ty_id == ty_id2
+            }
+            (TyKind::ForeignType(ty_id, ..), TyKind::ForeignType(ty_id2, ..)) => ty_id == ty_id2,
+            (TyKind::Closure(id1, _), TyKind::Closure(id2, _)) => id1 == id2,
+            (TyKind::Ref(mutability, ..), TyKind::Ref(mutability2, ..))
+            | (TyKind::Raw(mutability, ..), TyKind::Raw(mutability2, ..)) => {
+                mutability == mutability2
             }
-            (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, .. }),
+                TyKind::Function(FnPointer { num_args, sig, .. }),
+                TyKind::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,
+            (TyKind::Tuple(cardinality, _), TyKind::Tuple(cardinality2, _)) => {
+                cardinality == cardinality2
+            }
+            (TyKind::Str, TyKind::Str) | (TyKind::Never, TyKind::Never) => true,
+            (TyKind::Scalar(scalar), TyKind::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 {
-            Ty::Dyn(bounds) => bounds.get(0).and_then(|b| match b {
+        match self.interned(&Interner) {
+            TyKind::Dyn(bounds) => bounds.get(0).and_then(|b| match b {
                 GenericPredicate::Implemented(trait_ref) => Some(trait_ref),
                 _ => None,
             }),
@@ -729,28 +775,37 @@ impl Ty {
     }
 
     fn builtin_deref(&self) -> Option<Ty> {
-        match self {
-            Ty::Ref(.., parameters) => Some(Ty::clone(parameters.as_single())),
-            Ty::Raw(.., parameters) => Some(Ty::clone(parameters.as_single())),
+        match self.interned(&Interner) {
+            TyKind::Ref(.., ty) => Some(ty.clone()),
+            TyKind::Raw(.., ty) => Some(ty.clone()),
             _ => None,
         }
     }
 
-    pub fn as_fn_def(&self) -> Option<FunctionId> {
-        match self {
-            &Ty::FnDef(CallableDefId::FunctionId(func), ..) => Some(func),
+    pub fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
+        match self.interned(&Interner) {
+            &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
             _ => None,
         }
     }
 
+    pub fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
+        if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
+            Some(func)
+        } else {
+            None
+        }
+    }
+
     pub fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
-        match self {
-            Ty::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
-            Ty::FnDef(def, parameters) => {
-                let sig = db.callable_item_signature(*def);
+        match self.interned(&Interner) {
+            TyKind::Function(fn_ptr) => Some(CallableSig::from_fn_ptr(fn_ptr)),
+            TyKind::FnDef(def, parameters) => {
+                let callable_def = db.lookup_intern_callable_def((*def).into());
+                let sig = db.callable_item_signature(callable_def);
                 Some(sig.subst(&parameters))
             }
-            Ty::Closure(.., substs) => {
+            TyKind::Closure(.., substs) => {
                 let sig_param = &substs[0];
                 sig_param.callable_sig(db)
             }
@@ -758,72 +813,39 @@ impl Ty {
         }
     }
 
-    /// If this is a type with type parameters (an ADT or function), replaces
-    /// 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(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
-    }
-
     /// 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> {
-        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),
+        match self.interned(&Interner) {
+            TyKind::Adt(_, substs)
+            | TyKind::FnDef(_, substs)
+            | TyKind::Function(FnPointer { substs, .. })
+            | TyKind::Tuple(_, substs)
+            | TyKind::OpaqueType(_, substs)
+            | TyKind::AssociatedType(_, substs)
+            | TyKind::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),
+    fn substs_mut(&mut self) -> Option<&mut Substs> {
+        match self.interned_mut() {
+            TyKind::Adt(_, substs)
+            | TyKind::FnDef(_, substs)
+            | TyKind::Function(FnPointer { substs, .. })
+            | TyKind::Tuple(_, substs)
+            | TyKind::OpaqueType(_, substs)
+            | TyKind::AssociatedType(_, substs)
+            | TyKind::Closure(.., substs) => Some(substs),
             _ => None,
         }
     }
 
     pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<GenericPredicate>> {
-        match self {
-            Ty::OpaqueType(opaque_ty_id, ..) => {
-                match opaque_ty_id {
-                    OpaqueTyId::AsyncBlockTypeImplTrait(def, _expr) => {
+        match self.interned(&Interner) {
+            TyKind::OpaqueType(opaque_ty_id, ..) => {
+                match db.lookup_intern_impl_trait_id((*opaque_ty_id).into()) {
+                    ImplTraitId::AsyncBlockTypeImplTrait(def, _expr) => {
                         let krate = def.module(db.upcast()).krate();
                         if let Some(future_trait) = db
                             .lang_item(krate, "future_trait".into())
@@ -841,32 +863,34 @@ impl Ty {
                             None
                         }
                     }
-                    OpaqueTyId::ReturnTypeImplTrait(..) => None,
+                    ImplTraitId::ReturnTypeImplTrait(..) => None,
                 }
             }
-            Ty::Alias(AliasTy::Opaque(opaque_ty)) => {
-                let predicates = match opaque_ty.opaque_ty_id {
-                    OpaqueTyId::ReturnTypeImplTrait(func, idx) => {
+            TyKind::Alias(AliasTy::Opaque(opaque_ty)) => {
+                let predicates = match db.lookup_intern_impl_trait_id(opaque_ty.opaque_ty_id.into())
+                {
+                    ImplTraitId::ReturnTypeImplTrait(func, idx) => {
                         db.return_type_impl_traits(func).map(|it| {
                             let data = (*it)
                                 .as_ref()
                                 .map(|rpit| rpit.impl_traits[idx as usize].bounds.clone());
-                            data.subst(&opaque_ty.parameters)
+                            data.subst(&opaque_ty.substitution)
                         })
                     }
                     // It always has an parameter for Future::Output type.
-                    OpaqueTyId::AsyncBlockTypeImplTrait(..) => unreachable!(),
+                    ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
                 };
 
                 predicates.map(|it| it.value)
             }
-            Ty::Placeholder(id) => {
+            TyKind::Placeholder(idx) => {
+                let id = from_placeholder_idx(db, *idx);
                 let generic_params = db.generic_params(id.parent);
                 let param_data = &generic_params.types[id.local_id];
                 match param_data.provenance {
                     hir_def::generics::TypeParamProvenance::ArgumentImplTrait => {
                         let predicates = db
-                            .generic_predicates_for_param(*id)
+                            .generic_predicates_for_param(id)
                             .into_iter()
                             .map(|pred| pred.value.clone())
                             .collect_vec();
@@ -881,15 +905,18 @@ impl Ty {
     }
 
     pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
-        match self {
-            Ty::AssociatedType(type_alias_id, ..) => {
-                match type_alias_id.lookup(db.upcast()).container {
+        match self.interned(&Interner) {
+            TyKind::AssociatedType(id, ..) => {
+                match from_assoc_type_id(*id).lookup(db.upcast()).container {
                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
                     _ => None,
                 }
             }
-            Ty::Alias(AliasTy::Projection(projection_ty)) => {
-                match projection_ty.associated_ty.lookup(db.upcast()).container {
+            TyKind::Alias(AliasTy::Projection(projection_ty)) => {
+                match from_assoc_type_id(projection_ty.associated_ty_id)
+                    .lookup(db.upcast())
+                    .container
+                {
                     AssocContainerId::TraitId(trait_id) => Some(trait_id),
                     _ => None,
                 }
@@ -908,13 +935,13 @@ pub trait TypeWalk {
     }
     /// Walk the type, counting entered binders.
     ///
-    /// `Ty::Bound` variables use DeBruijn indexing, which means that 0 refers
+    /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
     /// to the innermost binder, 1 to the next, etc.. So when we want to
     /// substitute a certain bound variable, we can't just walk the whole type
     /// and blindly replace each instance of a certain index; when we 'enter'
     /// things that introduce new bound variables, we have to keep track of
     /// that. Currently, the only thing that introduces bound variables on our
-    /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound
+    /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
     /// variable for the self type.
     fn walk_mut_binders(
         &mut self,
@@ -932,7 +959,7 @@ pub trait TypeWalk {
     {
         self.walk_mut_binders(
             &mut |ty_mut, binders| {
-                let ty = mem::replace(ty_mut, Ty::Unknown);
+                let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
                 *ty_mut = f(ty, binders);
             },
             binders,
@@ -945,13 +972,13 @@ pub trait TypeWalk {
         Self: Sized,
     {
         self.walk_mut(&mut |ty_mut| {
-            let ty = mem::replace(ty_mut, Ty::Unknown);
+            let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner));
             *ty_mut = f(ty);
         });
         self
     }
 
-    /// Substitutes `Ty::Bound` vars with the given substitution.
+    /// Substitutes `TyKind::Bound` vars with the given substitution.
     fn subst_bound_vars(self, substs: &Substs) -> Self
     where
         Self: Sized,
@@ -959,14 +986,14 @@ pub trait TypeWalk {
         self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
     }
 
-    /// Substitutes `Ty::Bound` vars with the given substitution.
+    /// Substitutes `TyKind::Bound` vars with the given substitution.
     fn subst_bound_vars_at_depth(mut self, substs: &Substs, depth: DebruijnIndex) -> Self
     where
         Self: Sized,
     {
         self.walk_mut_binders(
             &mut |ty, binders| {
-                if let &mut Ty::BoundVar(bound) = ty {
+                if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
                     if bound.debruijn >= binders {
                         *ty = substs.0[bound.index].clone().shift_bound_vars(binders);
                     }
@@ -977,17 +1004,17 @@ pub trait TypeWalk {
         self
     }
 
-    /// Shifts up debruijn indices of `Ty::Bound` vars by `n`.
+    /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
     fn shift_bound_vars(self, n: DebruijnIndex) -> Self
     where
         Self: Sized,
     {
         self.fold_binders(
-            &mut |ty, binders| match ty {
-                Ty::BoundVar(bound) if bound.debruijn >= binders => {
-                    Ty::BoundVar(bound.shifted_in_from(n))
+            &mut |ty, binders| match ty.interned(&Interner) {
+                TyKind::BoundVar(bound) if bound.debruijn >= binders => {
+                    TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
                 }
-                ty => ty,
+                _ => ty,
             },
             DebruijnIndex::INNERMOST,
         )
@@ -996,22 +1023,25 @@ pub trait TypeWalk {
 
 impl TypeWalk for Ty {
     fn walk(&self, f: &mut impl FnMut(&Ty)) {
-        match self {
-            Ty::Alias(AliasTy::Projection(p_ty)) => {
-                for t in p_ty.parameters.iter() {
+        match self.interned(&Interner) {
+            TyKind::Alias(AliasTy::Projection(p_ty)) => {
+                for t in p_ty.substitution.iter() {
                     t.walk(f);
                 }
             }
-            Ty::Alias(AliasTy::Opaque(o_ty)) => {
-                for t in o_ty.parameters.iter() {
+            TyKind::Alias(AliasTy::Opaque(o_ty)) => {
+                for t in o_ty.substitution.iter() {
                     t.walk(f);
                 }
             }
-            Ty::Dyn(predicates) => {
+            TyKind::Dyn(predicates) => {
                 for p in predicates.iter() {
                     p.walk(f);
                 }
             }
+            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
+                ty.walk(f);
+            }
             _ => {
                 if let Some(substs) = self.substs() {
                     for t in substs.iter() {
@@ -1028,17 +1058,20 @@ impl TypeWalk for Ty {
         f: &mut impl FnMut(&mut Ty, DebruijnIndex),
         binders: DebruijnIndex,
     ) {
-        match self {
-            Ty::Alias(AliasTy::Projection(p_ty)) => {
-                p_ty.parameters.walk_mut_binders(f, binders);
+        match self.interned_mut() {
+            TyKind::Alias(AliasTy::Projection(p_ty)) => {
+                p_ty.substitution.walk_mut_binders(f, binders);
             }
-            Ty::Dyn(predicates) => {
+            TyKind::Dyn(predicates) => {
                 for p in make_mut_slice(predicates) {
                     p.walk_mut_binders(f, binders.shifted_in());
                 }
             }
-            Ty::Alias(AliasTy::Opaque(o_ty)) => {
-                o_ty.parameters.walk_mut_binders(f, binders);
+            TyKind::Alias(AliasTy::Opaque(o_ty)) => {
+                o_ty.substitution.walk_mut_binders(f, binders);
+            }
+            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => {
+                ty.walk_mut_binders(f, binders);
             }
             _ => {
                 if let Some(substs) = self.substs_mut() {
@@ -1068,7 +1101,7 @@ impl<T: TypeWalk> TypeWalk for Vec<T> {
 }
 
 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
-pub enum OpaqueTyId {
+pub enum ImplTraitId {
     ReturnTypeImplTrait(hir_def::FunctionId, u16),
     AsyncBlockTypeImplTrait(hir_def::DefWithBodyId, ExprId),
 }
@@ -1082,3 +1115,33 @@ pub struct ReturnTypeImplTraits {
 pub(crate) struct ReturnTypeImplTrait {
     pub(crate) bounds: Binders<Vec<GenericPredicate>>,
 }
+
+pub fn to_foreign_def_id(id: TypeAliasId) -> ForeignDefId {
+    chalk_ir::ForeignDefId(salsa::InternKey::as_intern_id(&id))
+}
+
+pub fn from_foreign_def_id(id: ForeignDefId) -> TypeAliasId {
+    salsa::InternKey::from_intern_id(id.0)
+}
+
+pub fn to_assoc_type_id(id: TypeAliasId) -> AssocTypeId {
+    chalk_ir::AssocTypeId(salsa::InternKey::as_intern_id(&id))
+}
+
+pub fn from_assoc_type_id(id: AssocTypeId) -> TypeAliasId {
+    salsa::InternKey::from_intern_id(id.0)
+}
+
+pub fn from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> TypeParamId {
+    assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
+    let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
+    db.lookup_intern_type_param_id(interned_id)
+}
+
+pub fn to_placeholder_idx(db: &dyn HirDatabase, id: TypeParamId) -> PlaceholderIndex {
+    let interned_id = db.intern_type_param_id(id);
+    PlaceholderIndex {
+        ui: chalk_ir::UniverseIndex::ROOT,
+        idx: salsa::InternKey::as_intern_id(&interned_id).as_usize(),
+    }
+}