27 files changed, 414 insertions, 305 deletions

diff --git a/Cargo.lock b/Cargo.lock
index e40c12a92..ca0311595 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1867,6 +1867,7 @@ name = "vfs"
 version = "0.0.0"
 dependencies = [
  "fst",
+ "indexmap",
  "paths",
  "rustc-hash",
 ]
diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 813cd1295..8d00f7401 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -59,7 +59,7 @@ use hir_ty::{
     traits::FnTrait,
     AliasEq, AliasTy, BoundVar, CallableDefId, CallableSig, Canonical, CanonicalVarKinds, Cast,
     DebruijnIndex, InEnvironment, Interner, QuantifiedWhereClause, Scalar, Solution,
-    SolutionVariables, Substitution, TraitEnvironment, Ty, TyBuilder, TyDefId, TyKind,
+    SolutionVariables, Substitution, TraitEnvironment, Ty, TyBuilder, TyDefId, TyExt, TyKind,
     TyVariableKind, WhereClause,
 };
 use itertools::Itertools;
@@ -1888,7 +1888,7 @@ impl Type {
                     substs.iter(&Interner).filter_map(|a| a.ty(&Interner)).any(go)
                 }
 
-                TyKind::Array(ty)
+                TyKind::Array(ty, _)
                 | TyKind::Slice(ty)
                 | TyKind::Raw(_, ty)
                 | TyKind::Ref(_, _, ty) => go(ty),
@@ -2151,7 +2151,7 @@ impl Type {
 
                 TyKind::Ref(_, _, ty)
                 | TyKind::Raw(_, ty)
-                | TyKind::Array(ty)
+                | TyKind::Array(ty, _)
                 | TyKind::Slice(ty) => {
                     walk_type(db, &type_.derived(ty.clone()), cb);
                 }
diff --git a/crates/hir_def/src/body/lower.rs b/crates/hir_def/src/body/lower.rs
index 63e89a1f4..bfb75a8a5 100644
--- a/crates/hir_def/src/body/lower.rs
+++ b/crates/hir_def/src/body/lower.rs
@@ -30,6 +30,7 @@ use crate::{
         LabelId, Literal, LogicOp, MatchArm, Ordering, Pat, PatId, RecordFieldPat, RecordLitField,
         Statement,
     },
+    intern::Interned,
     item_scope::BuiltinShadowMode,
     path::{GenericArgs, Path},
     type_ref::{Mutability, Rawness, TypeRef},
@@ -322,8 +323,10 @@ impl ExprCollector<'_> {
                     Vec::new()
                 };
                 let method_name = e.name_ref().map(|nr| nr.as_name()).unwrap_or_else(Name::missing);
-                let generic_args =
-                    e.generic_arg_list().and_then(|it| GenericArgs::from_ast(&self.ctx(), it));
+                let generic_args = e
+                    .generic_arg_list()
+                    .and_then(|it| GenericArgs::from_ast(&self.ctx(), it))
+                    .map(Box::new);
                 self.alloc_expr(
                     Expr::MethodCall { receiver, method_name, args, generic_args },
                     syntax_ptr,
@@ -385,7 +388,7 @@ impl ExprCollector<'_> {
                 self.alloc_expr(Expr::Yield { expr }, syntax_ptr)
             }
             ast::Expr::RecordExpr(e) => {
-                let path = e.path().and_then(|path| self.expander.parse_path(path));
+                let path = e.path().and_then(|path| self.expander.parse_path(path)).map(Box::new);
                 let record_lit = if let Some(nfl) = e.record_expr_field_list() {
                     let fields = nfl
                         .fields()
@@ -430,7 +433,7 @@ impl ExprCollector<'_> {
             }
             ast::Expr::CastExpr(e) => {
                 let expr = self.collect_expr_opt(e.expr());
-                let type_ref = TypeRef::from_ast_opt(&self.ctx(), e.ty());
+                let type_ref = Interned::new(TypeRef::from_ast_opt(&self.ctx(), e.ty()));
                 self.alloc_expr(Expr::Cast { expr, type_ref }, syntax_ptr)
             }
             ast::Expr::RefExpr(e) => {
@@ -464,13 +467,16 @@ impl ExprCollector<'_> {
                 if let Some(pl) = e.param_list() {
                     for param in pl.params() {
                         let pat = self.collect_pat_opt(param.pat());
-                        let type_ref = param.ty().map(|it| TypeRef::from_ast(&self.ctx(), it));
+                        let type_ref =
+                            param.ty().map(|it| Interned::new(TypeRef::from_ast(&self.ctx(), it)));
                         args.push(pat);
                         arg_types.push(type_ref);
                     }
                 }
-                let ret_type =
-                    e.ret_type().and_then(|r| r.ty()).map(|it| TypeRef::from_ast(&self.ctx(), it));
+                let ret_type = e
+                    .ret_type()
+                    .and_then(|r| r.ty())
+                    .map(|it| Interned::new(TypeRef::from_ast(&self.ctx(), it)));
                 let body = self.collect_expr_opt(e.body());
                 self.alloc_expr(Expr::Lambda { args, arg_types, ret_type, body }, syntax_ptr)
             }
@@ -625,7 +631,8 @@ impl ExprCollector<'_> {
                     return;
                 }
                 let pat = self.collect_pat_opt(stmt.pat());
-                let type_ref = stmt.ty().map(|it| TypeRef::from_ast(&self.ctx(), it));
+                let type_ref =
+                    stmt.ty().map(|it| Interned::new(TypeRef::from_ast(&self.ctx(), it)));
                 let initializer = stmt.initializer().map(|e| self.collect_expr(e));
                 self.statements_in_scope.push(Statement::Let { pat, type_ref, initializer });
             }
@@ -755,7 +762,7 @@ impl ExprCollector<'_> {
                 }
             }
             ast::Pat::TupleStructPat(p) => {
-                let path = p.path().and_then(|path| self.expander.parse_path(path));
+                let path = p.path().and_then(|path| self.expander.parse_path(path)).map(Box::new);
                 let (args, ellipsis) = self.collect_tuple_pat(p.fields());
                 Pat::TupleStruct { path, args, ellipsis }
             }
@@ -765,7 +772,7 @@ impl ExprCollector<'_> {
                 Pat::Ref { pat, mutability }
             }
             ast::Pat::PathPat(p) => {
-                let path = p.path().and_then(|path| self.expander.parse_path(path));
+                let path = p.path().and_then(|path| self.expander.parse_path(path)).map(Box::new);
                 path.map(Pat::Path).unwrap_or(Pat::Missing)
             }
             ast::Pat::OrPat(p) => {
@@ -779,7 +786,7 @@ impl ExprCollector<'_> {
             }
             ast::Pat::WildcardPat(_) => Pat::Wild,
             ast::Pat::RecordPat(p) => {
-                let path = p.path().and_then(|path| self.expander.parse_path(path));
+                let path = p.path().and_then(|path| self.expander.parse_path(path)).map(Box::new);
                 let args: Vec<_> = p
                     .record_pat_field_list()
                     .expect("every struct should have a field list")
diff --git a/crates/hir_def/src/expr.rs b/crates/hir_def/src/expr.rs
index 6c7376fad..b4ad984bd 100644
--- a/crates/hir_def/src/expr.rs
+++ b/crates/hir_def/src/expr.rs
@@ -18,6 +18,7 @@ use syntax::ast::RangeOp;
 
 use crate::{
     builtin_type::{BuiltinFloat, BuiltinInt, BuiltinUint},
+    intern::Interned,
     path::{GenericArgs, Path},
     type_ref::{Mutability, Rawness, TypeRef},
     BlockId,
@@ -86,7 +87,7 @@ pub enum Expr {
         receiver: ExprId,
         method_name: Name,
         args: Vec<ExprId>,
-        generic_args: Option<GenericArgs>,
+        generic_args: Option<Box<GenericArgs>>,
     },
     Match {
         expr: ExprId,
@@ -106,7 +107,7 @@ pub enum Expr {
         expr: Option<ExprId>,
     },
     RecordLit {
-        path: Option<Path>,
+        path: Option<Box<Path>>,
         fields: Vec<RecordLitField>,
         spread: Option<ExprId>,
     },
@@ -131,7 +132,7 @@ pub enum Expr {
     },
     Cast {
         expr: ExprId,
-        type_ref: TypeRef,
+        type_ref: Interned<TypeRef>,
     },
     Ref {
         expr: ExprId,
@@ -161,8 +162,8 @@ pub enum Expr {
     },
     Lambda {
         args: Vec<PatId>,
-        arg_types: Vec<Option<TypeRef>>,
-        ret_type: Option<TypeRef>,
+        arg_types: Vec<Option<Interned<TypeRef>>>,
+        ret_type: Option<Interned<TypeRef>>,
         body: ExprId,
     },
     Tuple {
@@ -240,7 +241,7 @@ pub struct RecordLitField {
 
 #[derive(Debug, Clone, Eq, PartialEq)]
 pub enum Statement {
-    Let { pat: PatId, type_ref: Option<TypeRef>, initializer: Option<ExprId> },
+    Let { pat: PatId, type_ref: Option<Interned<TypeRef>>, initializer: Option<ExprId> },
     Expr(ExprId),
 }
 
@@ -412,13 +413,13 @@ pub enum Pat {
     Wild,
     Tuple { args: Vec<PatId>, ellipsis: Option<usize> },
     Or(Vec<PatId>),
-    Record { path: Option<Path>, args: Vec<RecordFieldPat>, ellipsis: bool },
+    Record { path: Option<Box<Path>>, args: Vec<RecordFieldPat>, ellipsis: bool },
     Range { start: ExprId, end: ExprId },
     Slice { prefix: Vec<PatId>, slice: Option<PatId>, suffix: Vec<PatId> },
-    Path(Path),
+    Path(Box<Path>),
     Lit(ExprId),
     Bind { mode: BindingAnnotation, name: Name, subpat: Option<PatId> },
-    TupleStruct { path: Option<Path>, args: Vec<PatId>, ellipsis: Option<usize> },
+    TupleStruct { path: Option<Box<Path>>, args: Vec<PatId>, ellipsis: Option<usize> },
     Ref { pat: PatId, mutability: Mutability },
     Box { inner: PatId },
     ConstBlock(ExprId),
diff --git a/crates/hir_def/src/path.rs b/crates/hir_def/src/path.rs
index f9c8328f0..b528ff8ba 100644
--- a/crates/hir_def/src/path.rs
+++ b/crates/hir_def/src/path.rs
@@ -289,6 +289,12 @@ impl From<Name> for Path {
     }
 }
 
+impl From<Name> for Box<Path> {
+    fn from(name: Name) -> Box<Path> {
+        Box::new(Path::from(name))
+    }
+}
+
 impl From<Name> for ModPath {
     fn from(name: Name) -> ModPath {
         ModPath::from_segments(PathKind::Plain, iter::once(name))
diff --git a/crates/hir_ty/src/builder.rs b/crates/hir_ty/src/builder.rs
index 791915fe0..09512d1ce 100644
--- a/crates/hir_ty/src/builder.rs
+++ b/crates/hir_ty/src/builder.rs
@@ -13,7 +13,7 @@ use smallvec::SmallVec;
 use crate::{
     db::HirDatabase, primitive, to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders,
     CallableSig, FnPointer, FnSig, FnSubst, GenericArg, Interner, ProjectionTy, Substitution,
-    TraitRef, Ty, TyDefId, TyKind, TypeWalk, ValueTyDefId,
+    TraitRef, Ty, TyDefId, TyExt, TyKind, TypeWalk, ValueTyDefId,
 };
 
 /// This is a builder for `Ty` or anything that needs a `Substitution`.
diff --git a/crates/hir_ty/src/chalk_ext.rs b/crates/hir_ty/src/chalk_ext.rs
index 0f4cb43e9..8e8a1aa48 100644
--- a/crates/hir_ty/src/chalk_ext.rs
+++ b/crates/hir_ty/src/chalk_ext.rs
@@ -1,20 +1,243 @@
 //! Various extensions traits for Chalk types.
 
-use hir_def::{AssocContainerId, Lookup, TraitId};
+use chalk_ir::Mutability;
+use hir_def::{
+    type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule, Lookup, TraitId,
+};
 
 use crate::{
-    db::HirDatabase, from_assoc_type_id, to_chalk_trait_id, Interner, ProjectionTy, TraitRef, Ty,
-    TyKind,
+    db::HirDatabase, from_assoc_type_id, from_chalk_trait_id, from_foreign_def_id,
+    from_placeholder_idx, to_chalk_trait_id, AdtId, AliasEq, AliasTy, Binders, CallableDefId,
+    CallableSig, ImplTraitId, Interner, Lifetime, ProjectionTy, QuantifiedWhereClause,
+    Substitution, TraitRef, Ty, TyBuilder, TyKind, WhereClause,
 };
 
 pub trait TyExt {
     fn is_unit(&self) -> bool;
+    fn is_never(&self) -> bool;
+    fn is_unknown(&self) -> bool;
+
+    fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)>;
+    fn as_tuple(&self) -> Option<&Substitution>;
+    fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId>;
+    fn as_reference(&self) -> Option<(&Ty, Lifetime, Mutability)>;
+    fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)>;
+    fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId>;
+
+    fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId>;
+    fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig>;
+
+    fn strip_references(&self) -> &Ty;
+
+    /// If this is a `dyn Trait`, returns that trait.
+    fn dyn_trait(&self) -> Option<TraitId>;
+
+    fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>>;
+    fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId>;
 }
 
 impl TyExt for Ty {
     fn is_unit(&self) -> bool {
         matches!(self.kind(&Interner), TyKind::Tuple(0, _))
     }
+
+    fn is_never(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Never)
+    }
+
+    fn is_unknown(&self) -> bool {
+        matches!(self.kind(&Interner), TyKind::Error)
+    }
+
+    fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
+        match self.kind(&Interner) {
+            TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
+            _ => None,
+        }
+    }
+
+    fn as_tuple(&self) -> Option<&Substitution> {
+        match self.kind(&Interner) {
+            TyKind::Tuple(_, substs) => Some(substs),
+            _ => None,
+        }
+    }
+
+    fn as_fn_def(&self, db: &dyn HirDatabase) -> Option<FunctionId> {
+        if let Some(CallableDefId::FunctionId(func)) = self.callable_def(db) {
+            Some(func)
+        } else {
+            None
+        }
+    }
+    fn as_reference(&self) -> Option<(&Ty, Lifetime, Mutability)> {
+        match self.kind(&Interner) {
+            TyKind::Ref(mutability, lifetime, ty) => Some((ty, *lifetime, *mutability)),
+            _ => None,
+        }
+    }
+
+    fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
+        match self.kind(&Interner) {
+            TyKind::Ref(mutability, _, ty) => Some((ty, Rawness::Ref, *mutability)),
+            TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
+            _ => None,
+        }
+    }
+
+    fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
+        match *self.kind(&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::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
+            _ => None,
+        }
+    }
+
+    fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
+        match self.kind(&Interner) {
+            &TyKind::FnDef(def, ..) => Some(db.lookup_intern_callable_def(def.into())),
+            _ => None,
+        }
+    }
+
+    fn callable_sig(&self, db: &dyn HirDatabase) -> Option<CallableSig> {
+        match self.kind(&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.substitute(&Interner, &parameters))
+            }
+            TyKind::Closure(.., substs) => {
+                let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
+                sig_param.callable_sig(db)
+            }
+            _ => None,
+        }
+    }
+
+    fn dyn_trait(&self) -> Option<TraitId> {
+        let trait_ref = match self.kind(&Interner) {
+            TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
+                match b.skip_binders() {
+                    WhereClause::Implemented(trait_ref) => Some(trait_ref),
+                    _ => None,
+                }
+            }),
+            _ => None,
+        }?;
+        Some(from_chalk_trait_id(trait_ref.trait_id))
+    }
+
+    fn strip_references(&self) -> &Ty {
+        let mut t: &Ty = self;
+        while let TyKind::Ref(_mutability, _lifetime, ty) = t.kind(&Interner) {
+            t = ty;
+        }
+        t
+    }
+
+    fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
+        match self.kind(&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())
+                            .and_then(|item| item.as_trait())
+                        {
+                            // This is only used by type walking.
+                            // Parameters will be walked outside, and projection predicate is not used.
+                            // So just provide the Future trait.
+                            let impl_bound = Binders::empty(
+                                &Interner,
+                                WhereClause::Implemented(TraitRef {
+                                    trait_id: to_chalk_trait_id(future_trait),
+                                    substitution: Substitution::empty(&Interner),
+                                }),
+                            );
+                            Some(vec![impl_bound])
+                        } else {
+                            None
+                        }
+                    }
+                    ImplTraitId::ReturnTypeImplTrait(..) => None,
+                }
+            }
+            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.substitute(&Interner, &opaque_ty.substitution)
+                        })
+                    }
+                    // It always has an parameter for Future::Output type.
+                    ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
+                };
+
+                predicates.map(|it| it.into_value_and_skipped_binders().0)
+            }
+            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 substs = TyBuilder::type_params_subst(db, id.parent);
+                        let predicates = db
+                            .generic_predicates(id.parent)
+                            .into_iter()
+                            .map(|pred| pred.clone().substitute(&Interner, &substs))
+                            .filter(|wc| match &wc.skip_binders() {
+                                WhereClause::Implemented(tr) => {
+                                    tr.self_type_parameter(&Interner) == self
+                                }
+                                WhereClause::AliasEq(AliasEq {
+                                    alias: AliasTy::Projection(proj),
+                                    ty: _,
+                                }) => proj.self_type_parameter(&Interner) == self,
+                                _ => false,
+                            })
+                            .collect::<Vec<_>>();
+
+                        Some(predicates)
+                    }
+                    _ => None,
+                }
+            }
+            _ => None,
+        }
+    }
+
+    fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
+        match self.kind(&Interner) {
+            TyKind::AssociatedType(id, ..) => {
+                match from_assoc_type_id(*id).lookup(db.upcast()).container {
+                    AssocContainerId::TraitId(trait_id) => Some(trait_id),
+                    _ => None,
+                }
+            }
+            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,
+                }
+            }
+            _ => None,
+        }
+    }
 }
 
 pub trait ProjectionTyExt {
diff --git a/crates/hir_ty/src/db.rs b/crates/hir_ty/src/db.rs
index 07510ae02..326c20240 100644
--- a/crates/hir_ty/src/db.rs
+++ b/crates/hir_ty/src/db.rs
@@ -88,6 +88,8 @@ pub trait HirDatabase: DefDatabase + Upcast<dyn DefDatabase> {
     #[salsa::interned]
     fn intern_lifetime_param_id(&self, param_id: LifetimeParamId) -> InternedLifetimeParamId;
     #[salsa::interned]
+    fn intern_const_param_id(&self, param_id: ConstParamId) -> InternedConstParamId;
+    #[salsa::interned]
     fn intern_impl_trait_id(&self, id: ImplTraitId) -> InternedOpaqueTyId;
     #[salsa::interned]
     fn intern_closure(&self, id: (DefWithBodyId, ExprId)) -> InternedClosureId;
@@ -162,6 +164,10 @@ pub struct InternedLifetimeParamId(salsa::InternId);
 impl_intern_key!(InternedLifetimeParamId);
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct InternedConstParamId(salsa::InternId);
+impl_intern_key!(InternedConstParamId);
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct InternedOpaqueTyId(salsa::InternId);
 impl_intern_key!(InternedOpaqueTyId);
 
diff --git a/crates/hir_ty/src/diagnostics/match_check.rs b/crates/hir_ty/src/diagnostics/match_check.rs
index 34291578a..e9762622f 100644
--- a/crates/hir_ty/src/diagnostics/match_check.rs
+++ b/crates/hir_ty/src/diagnostics/match_check.rs
@@ -227,7 +227,7 @@ use hir_def::{
 use la_arena::Idx;
 use smallvec::{smallvec, SmallVec};
 
-use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, TyKind};
+use crate::{db::HirDatabase, AdtId, InferenceResult, Interner, TyExt, TyKind};
 
 #[derive(Debug, Clone, Copy)]
 /// Either a pattern from the source code being analyzed, represented as
diff --git a/crates/hir_ty/src/diagnostics/unsafe_check.rs b/crates/hir_ty/src/diagnostics/unsafe_check.rs
index b5efe9df5..ed97dc0e3 100644
--- a/crates/hir_ty/src/diagnostics/unsafe_check.rs
+++ b/crates/hir_ty/src/diagnostics/unsafe_check.rs
@@ -11,7 +11,9 @@ use hir_def::{
 };
 use hir_expand::diagnostics::DiagnosticSink;
 
-use crate::{db::HirDatabase, diagnostics::MissingUnsafe, InferenceResult, Interner, TyKind};
+use crate::{
+    db::HirDatabase, diagnostics::MissingUnsafe, InferenceResult, Interner, TyExt, TyKind,
+};
 
 pub(super) struct UnsafeValidator<'a, 'b: 'a> {
     owner: DefWithBodyId,
diff --git a/crates/hir_ty/src/display.rs b/crates/hir_ty/src/display.rs
index 22416c0cf..8fe4ed3fa 100644
--- a/crates/hir_ty/src/display.rs
+++ b/crates/hir_ty/src/display.rs
@@ -5,6 +5,7 @@ use std::{
     fmt::{self, Debug},
 };
 
+use chalk_ir::BoundVar;
 use hir_def::{
     db::DefDatabase,
     find_path,
@@ -18,12 +19,12 @@ use hir_def::{
 use hir_expand::name::Name;
 
 use crate::{
-    db::HirDatabase, from_assoc_type_id, from_foreign_def_id, from_placeholder_idx,
-    lt_from_placeholder_idx, primitive, subst_prefix, to_assoc_type_id, traits::chalk::from_chalk,
-    utils::generics, AdtId, AliasEq, AliasTy, CallableDefId, CallableSig, DomainGoal, GenericArg,
-    ImplTraitId, Interner, Lifetime, LifetimeData, LifetimeOutlives, Mutability, OpaqueTy,
-    ProjectionTy, ProjectionTyExt, QuantifiedWhereClause, Scalar, TraitRef, Ty, TyExt, TyKind,
-    WhereClause,
+    const_from_placeholder_idx, db::HirDatabase, from_assoc_type_id, from_foreign_def_id,
+    from_placeholder_idx, lt_from_placeholder_idx, primitive, subst_prefix, to_assoc_type_id,
+    traits::chalk::from_chalk, utils::generics, AdtId, AliasEq, AliasTy, CallableDefId,
+    CallableSig, Const, ConstValue, DomainGoal, GenericArg, ImplTraitId, Interner, Lifetime,
+    LifetimeData, LifetimeOutlives, Mutability, OpaqueTy, ProjectionTy, ProjectionTyExt,
+    QuantifiedWhereClause, Scalar, TraitRef, Ty, TyExt, TyKind, WhereClause,
 };
 
 pub struct HirFormatter<'a> {
@@ -290,6 +291,29 @@ impl HirDisplay for GenericArg {
     }
 }
 
+impl HirDisplay for Const {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        let data = self.interned();
+        match data.value {
+            ConstValue::BoundVar(idx) => idx.hir_fmt(f),
+            ConstValue::InferenceVar(..) => write!(f, "_"),
+            ConstValue::Placeholder(idx) => {
+                let id = const_from_placeholder_idx(f.db, idx);
+                let generics = generics(f.db.upcast(), id.parent);
+                let param_data = &generics.params.consts[id.local_id];
+                write!(f, "{}", param_data.name)
+            }
+            ConstValue::Concrete(_) => write!(f, "_"),
+        }
+    }
+}
+
+impl HirDisplay for BoundVar {
+    fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
+        write!(f, "?{}.{}", self.debruijn.depth(), self.index)
+    }
+}
+
 impl HirDisplay for Ty {
     fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
         if f.should_truncate() {
@@ -309,10 +333,12 @@ impl HirDisplay for Ty {
                 t.hir_fmt(f)?;
                 write!(f, "]")?;
             }
-            TyKind::Array(t) => {
+            TyKind::Array(t, c) => {
                 write!(f, "[")?;
                 t.hir_fmt(f)?;
-                write!(f, "; _]")?;
+                write!(f, "; ")?;
+                c.hir_fmt(f)?;
+                write!(f, "]")?;
             }
             TyKind::Raw(m, t) | TyKind::Ref(m, _, t) => {
                 let ty_display =
@@ -617,7 +643,7 @@ impl HirDisplay for Ty {
                     }
                 }
             }
-            TyKind::BoundVar(idx) => write!(f, "?{}.{}", idx.debruijn.depth(), idx.index)?,
+            TyKind::BoundVar(idx) => idx.hir_fmt(f)?,
             TyKind::Dyn(dyn_ty) => {
                 write_bounds_like_dyn_trait_with_prefix(
                     "dyn",
@@ -850,7 +876,7 @@ impl HirDisplay for Lifetime {
 impl HirDisplay for LifetimeData {
     fn hir_fmt(&self, f: &mut HirFormatter) -> Result<(), HirDisplayError> {
         match self {
-            LifetimeData::BoundVar(idx) => write!(f, "?{}.{}", idx.debruijn.depth(), idx.index),
+            LifetimeData::BoundVar(idx) => idx.hir_fmt(f),
             LifetimeData::InferenceVar(_) => write!(f, "_"),
             LifetimeData::Placeholder(idx) => {
                 let id = lt_from_placeholder_idx(f.db, *idx);
diff --git a/crates/hir_ty/src/infer.rs b/crates/hir_ty/src/infer.rs
index 1c3faf5cb..5146d873b 100644
--- a/crates/hir_ty/src/infer.rs
+++ b/crates/hir_ty/src/infer.rs
@@ -42,7 +42,7 @@ use super::{
 };
 use crate::{
     db::HirDatabase, infer::diagnostics::InferenceDiagnostic, lower::ImplTraitLoweringMode,
-    to_assoc_type_id, AliasEq, AliasTy, Interner, TyBuilder, TyKind,
+    to_assoc_type_id, AliasEq, AliasTy, Interner, TyBuilder, TyExt, TyKind,
 };
 
 // This lint has a false positive here. See the link below for details.
diff --git a/crates/hir_ty/src/infer/coerce.rs b/crates/hir_ty/src/infer/coerce.rs
index d6c48870a..159a53a63 100644
--- a/crates/hir_ty/src/infer/coerce.rs
+++ b/crates/hir_ty/src/infer/coerce.rs
@@ -7,7 +7,7 @@
 use chalk_ir::{cast::Cast, Mutability, TyVariableKind};
 use hir_def::lang_item::LangItemTarget;
 
-use crate::{autoderef, Interner, Solution, Ty, TyBuilder, TyKind};
+use crate::{autoderef, Interner, Solution, Ty, TyBuilder, TyExt, TyKind};
 
 use super::{InEnvironment, InferenceContext};
 
diff --git a/crates/hir_ty/src/infer/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 796487d02..5b3cdab4e 100644
--- a/crates/hir_ty/src/infer/expr.rs
+++ b/crates/hir_ty/src/infer/expr.rs
@@ -15,7 +15,7 @@ use stdx::always;
 use syntax::ast::RangeOp;
 
 use crate::{
-    autoderef,
+    autoderef, dummy_usize_const,
     lower::lower_to_chalk_mutability,
     method_resolution, op,
     primitive::{self, UintTy},
@@ -23,7 +23,8 @@ use crate::{
     traits::{chalk::from_chalk, FnTrait},
     utils::{generics, variant_data, Generics},
     AdtId, Binders, CallableDefId, FnPointer, FnSig, FnSubst, InEnvironment, Interner,
-    ProjectionTyExt, Rawness, Scalar, Substitution, TraitRef, Ty, TyBuilder, TyKind, TypeWalk,
+    ProjectionTyExt, Rawness, Scalar, Substitution, TraitRef, Ty, TyBuilder, TyExt, TyKind,
+    TypeWalk,
 };
 
 use super::{
@@ -317,7 +318,13 @@ impl<'a> InferenceContext<'a> {
                 self.normalize_associated_types_in(ret_ty)
             }
             Expr::MethodCall { receiver, args, method_name, generic_args } => self
-                .infer_method_call(tgt_expr, *receiver, &args, &method_name, generic_args.as_ref()),
+                .infer_method_call(
+                    tgt_expr,
+                    *receiver,
+                    &args,
+                    &method_name,
+                    generic_args.as_deref(),
+                ),
             Expr::Match { expr, arms } => {
                 let input_ty = self.infer_expr(*expr, &Expectation::none());
 
@@ -398,7 +405,7 @@ impl<'a> InferenceContext<'a> {
                 TyKind::Never.intern(&Interner)
             }
             Expr::RecordLit { path, fields, spread } => {
-                let (ty, def_id) = self.resolve_variant(path.as_ref());
+                let (ty, def_id) = self.resolve_variant(path.as_deref());
                 if let Some(variant) = def_id {
                     self.write_variant_resolution(tgt_expr.into(), variant);
                 }
@@ -702,7 +709,7 @@ impl<'a> InferenceContext<'a> {
             }
             Expr::Array(array) => {
                 let elem_ty = match expected.ty.kind(&Interner) {
-                    TyKind::Array(st) | TyKind::Slice(st) => st.clone(),
+                    TyKind::Array(st, _) | TyKind::Slice(st) => st.clone(),
                     _ => self.table.new_type_var(),
                 };
 
@@ -726,7 +733,7 @@ impl<'a> InferenceContext<'a> {
                     }
                 }
 
-                TyKind::Array(elem_ty).intern(&Interner)
+                TyKind::Array(elem_ty, dummy_usize_const()).intern(&Interner)
             }
             Expr::Literal(lit) => match lit {
                 Literal::Bool(..) => TyKind::Scalar(Scalar::Bool).intern(&Interner),
@@ -736,7 +743,8 @@ impl<'a> InferenceContext<'a> {
                 }
                 Literal::ByteString(..) => {
                     let byte_type = TyKind::Scalar(Scalar::Uint(UintTy::U8)).intern(&Interner);
-                    let array_type = TyKind::Array(byte_type).intern(&Interner);
+                    let array_type =
+                        TyKind::Array(byte_type, dummy_usize_const()).intern(&Interner);
                     TyKind::Ref(Mutability::Not, static_lifetime(), array_type).intern(&Interner)
                 }
                 Literal::Char(..) => TyKind::Scalar(Scalar::Char).intern(&Interner),
diff --git a/crates/hir_ty/src/infer/pat.rs b/crates/hir_ty/src/infer/pat.rs
index 2848a393c..12431ae07 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -14,7 +14,7 @@ use hir_expand::name::Name;
 use super::{BindingMode, Expectation, InferenceContext};
 use crate::{
     lower::lower_to_chalk_mutability, static_lifetime, utils::variant_data, Interner, Substitution,
-    Ty, TyBuilder, TyKind,
+    Ty, TyBuilder, TyExt, TyKind,
 };
 
 impl<'a> InferenceContext<'a> {
@@ -174,7 +174,7 @@ impl<'a> InferenceContext<'a> {
                 TyKind::Ref(mutability, static_lifetime(), subty).intern(&Interner)
             }
             Pat::TupleStruct { path: p, args: subpats, ellipsis } => self.infer_tuple_struct_pat(
-                p.as_ref(),
+                p.as_deref(),
                 subpats,
                 expected,
                 default_bm,
@@ -182,7 +182,7 @@ impl<'a> InferenceContext<'a> {
                 *ellipsis,
             ),
             Pat::Record { path: p, args: fields, ellipsis: _ } => {
-                self.infer_record_pat(p.as_ref(), fields, expected, default_bm, pat)
+                self.infer_record_pat(p.as_deref(), fields, expected, default_bm, pat)
             }
             Pat::Path(path) => {
                 // FIXME use correct resolver for the surrounding expression
@@ -214,17 +214,20 @@ impl<'a> InferenceContext<'a> {
                 return inner_ty;
             }
             Pat::Slice { prefix, slice, suffix } => {
-                let (container_ty, elem_ty): (fn(_) -> _, _) = match expected.kind(&Interner) {
-                    TyKind::Array(st) => (TyKind::Array, st.clone()),
-                    TyKind::Slice(st) => (TyKind::Slice, st.clone()),
-                    _ => (TyKind::Slice, self.err_ty()),
+                let elem_ty = match expected.kind(&Interner) {
+                    TyKind::Array(st, _) | TyKind::Slice(st) => st.clone(),
+                    _ => self.err_ty(),
                 };
 
                 for pat_id in prefix.iter().chain(suffix) {
                     self.infer_pat(*pat_id, &elem_ty, default_bm);
                 }
 
-                let pat_ty = container_ty(elem_ty).intern(&Interner);
+                let pat_ty = match expected.kind(&Interner) {
+                    TyKind::Array(_, const_) => TyKind::Array(elem_ty, const_.clone()),
+                    _ => TyKind::Slice(elem_ty),
+                }
+                .intern(&Interner);
                 if let Some(slice_pat_id) = slice {
                     self.infer_pat(*slice_pat_id, &pat_ty, default_bm);
                 }
diff --git a/crates/hir_ty/src/infer/path.rs b/crates/hir_ty/src/infer/path.rs
index 14f705173..b19d67bb1 100644
--- a/crates/hir_ty/src/infer/path.rs
+++ b/crates/hir_ty/src/infer/path.rs
@@ -10,7 +10,9 @@ use hir_def::{
 };
 use hir_expand::name::Name;
 
-use crate::{method_resolution, Interner, Substitution, Ty, TyBuilder, TyKind, ValueTyDefId};
+use crate::{
+    method_resolution, Interner, Substitution, Ty, TyBuilder, TyExt, TyKind, ValueTyDefId,
+};
 
 use super::{ExprOrPatId, InferenceContext, TraitRef};
 
diff --git a/crates/hir_ty/src/infer/unify.rs b/crates/hir_ty/src/infer/unify.rs
index c7878ebfd..7d76cda68 100644
--- a/crates/hir_ty/src/infer/unify.rs
+++ b/crates/hir_ty/src/infer/unify.rs
@@ -317,9 +317,11 @@ impl InferenceTable {
                 | (TyKind::Closure(.., substs1), TyKind::Closure(.., substs2)) => {
                     self.unify_substs(substs1, substs2, depth + 1)
                 }
+                (TyKind::Array(ty1, c1), TyKind::Array(ty2, c2)) if c1 == c2 => {
+                    self.unify_inner(ty1, ty2, depth + 1)
+                }
                 (TyKind::Ref(_, _, ty1), TyKind::Ref(_, _, ty2))
                 | (TyKind::Raw(_, ty1), TyKind::Raw(_, ty2))
-                | (TyKind::Array(ty1), TyKind::Array(ty2))
                 | (TyKind::Slice(ty1), TyKind::Slice(ty2)) => self.unify_inner(ty1, ty2, depth + 1),
                 _ => true, /* we checked equals_ctor already */
             }
diff --git a/crates/hir_ty/src/lib.rs b/crates/hir_ty/src/lib.rs
index bccc73449..f5b658cba 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -30,12 +30,11 @@ mod test_db;
 
 use std::sync::Arc;
 
-use itertools::Itertools;
-
 use base_db::salsa;
+use chalk_ir::UintTy;
 use hir_def::{
-    expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule,
-    LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
+    expr::ExprId, type_ref::Rawness, ConstParamId, LifetimeParamId, TraitId, TypeAliasId,
+    TypeParamId,
 };
 
 use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
@@ -71,6 +70,11 @@ pub type Lifetime = chalk_ir::Lifetime<Interner>;
 pub type LifetimeData = chalk_ir::LifetimeData<Interner>;
 pub type LifetimeOutlives = chalk_ir::LifetimeOutlives<Interner>;
 
+pub type Const = chalk_ir::Const<Interner>;
+pub type ConstData = chalk_ir::ConstData<Interner>;
+pub type ConstValue = chalk_ir::ConstValue<Interner>;
+pub type ConcreteConst = chalk_ir::ConcreteConst<Interner>;
+
 pub type ChalkTraitId = chalk_ir::TraitId<Interner>;
 
 pub type FnSig = chalk_ir::FnSig<Interner>;
@@ -165,69 +169,12 @@ impl CallableSig {
 }
 
 impl Ty {
-    pub fn as_reference(&self) -> Option<(&Ty, Lifetime, Mutability)> {
-        match self.kind(&Interner) {
-            TyKind::Ref(mutability, lifetime, ty) => Some((ty, *lifetime, *mutability)),
-            _ => None,
-        }
-    }
-
-    pub fn as_reference_or_ptr(&self) -> Option<(&Ty, Rawness, Mutability)> {
-        match self.kind(&Interner) {
-            TyKind::Ref(mutability, _, ty) => Some((ty, Rawness::Ref, *mutability)),
-            TyKind::Raw(mutability, ty) => Some((ty, Rawness::RawPtr, *mutability)),
-            _ => None,
-        }
-    }
-
-    pub fn strip_references(&self) -> &Ty {
-        let mut t: &Ty = self;
-
-        while let TyKind::Ref(_mutability, _lifetime, ty) = t.kind(&Interner) {
-            t = ty;
-        }
-
-        t
-    }
-
-    pub fn as_adt(&self) -> Option<(hir_def::AdtId, &Substitution)> {
-        match self.kind(&Interner) {
-            TyKind::Adt(AdtId(adt), parameters) => Some((*adt, parameters)),
-            _ => None,
-        }
-    }
-
-    pub fn as_tuple(&self) -> Option<&Substitution> {
-        match self.kind(&Interner) {
-            TyKind::Tuple(_, substs) => Some(substs),
-            _ => None,
-        }
-    }
-
-    pub fn as_generic_def(&self, db: &dyn HirDatabase) -> Option<GenericDefId> {
-        match *self.kind(&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::Foreign(type_alias, ..) => Some(from_foreign_def_id(type_alias).into()),
-            _ => None,
-        }
-    }
-
-    pub fn is_never(&self) -> bool {
-        matches!(self.kind(&Interner), TyKind::Never)
-    }
-
-    pub fn is_unknown(&self) -> bool {
-        matches!(self.kind(&Interner), TyKind::Error)
-    }
-
     pub fn equals_ctor(&self, other: &Ty) -> bool {
         match (self.kind(&Interner), other.kind(&Interner)) {
             (TyKind::Adt(adt, ..), TyKind::Adt(adt2, ..)) => adt == adt2,
-            (TyKind::Slice(_), TyKind::Slice(_)) | (TyKind::Array(_), TyKind::Array(_)) => true,
+            (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, ..)) => {
@@ -252,24 +199,6 @@ impl Ty {
         }
     }
 
-    /// If this is a `dyn Trait` type, this returns the `Trait` part.
-    fn dyn_trait_ref(&self) -> Option<&TraitRef> {
-        match self.kind(&Interner) {
-            TyKind::Dyn(dyn_ty) => dyn_ty.bounds.skip_binders().interned().get(0).and_then(|b| {
-                match b.skip_binders() {
-                    WhereClause::Implemented(trait_ref) => Some(trait_ref),
-                    _ => None,
-                }
-            }),
-            _ => None,
-        }
-    }
-
-    /// If this is a `dyn Trait`, returns that trait.
-    pub fn dyn_trait(&self) -> Option<TraitId> {
-        self.dyn_trait_ref().map(|it| it.trait_id).map(from_chalk_trait_id)
-    }
-
     fn builtin_deref(&self) -> Option<Ty> {
         match self.kind(&Interner) {
             TyKind::Ref(.., ty) => Some(ty.clone()),
@@ -278,37 +207,6 @@ impl Ty {
         }
     }
 
-    pub fn callable_def(&self, db: &dyn HirDatabase) -> Option<CallableDefId> {
-        match self.kind(&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.kind(&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.substitute(&Interner, &parameters))
-            }
-            TyKind::Closure(.., substs) => {
-                let sig_param = substs.at(&Interner, 0).assert_ty_ref(&Interner);
-                sig_param.callable_sig(db)
-            }
-            _ => None,
-        }
-    }
-
     /// 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<&Substitution> {
@@ -336,104 +234,6 @@ impl Ty {
             _ => None,
         }
     }
-
-    pub fn impl_trait_bounds(&self, db: &dyn HirDatabase) -> Option<Vec<QuantifiedWhereClause>> {
-        match self.kind(&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())
-                            .and_then(|item| item.as_trait())
-                        {
-                            // This is only used by type walking.
-                            // Parameters will be walked outside, and projection predicate is not used.
-                            // So just provide the Future trait.
-                            let impl_bound = Binders::empty(
-                                &Interner,
-                                WhereClause::Implemented(TraitRef {
-                                    trait_id: to_chalk_trait_id(future_trait),
-                                    substitution: Substitution::empty(&Interner),
-                                }),
-                            );
-                            Some(vec![impl_bound])
-                        } else {
-                            None
-                        }
-                    }
-                    ImplTraitId::ReturnTypeImplTrait(..) => None,
-                }
-            }
-            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.substitute(&Interner, &opaque_ty.substitution)
-                        })
-                    }
-                    // It always has an parameter for Future::Output type.
-                    ImplTraitId::AsyncBlockTypeImplTrait(..) => unreachable!(),
-                };
-
-                predicates.map(|it| it.into_value_and_skipped_binders().0)
-            }
-            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 substs = TyBuilder::type_params_subst(db, id.parent);
-                        let predicates = db
-                            .generic_predicates(id.parent)
-                            .into_iter()
-                            .map(|pred| pred.clone().substitute(&Interner, &substs))
-                            .filter(|wc| match &wc.skip_binders() {
-                                WhereClause::Implemented(tr) => {
-                                    tr.self_type_parameter(&Interner) == self
-                                }
-                                WhereClause::AliasEq(AliasEq {
-                                    alias: AliasTy::Projection(proj),
-                                    ty: _,
-                                }) => proj.self_type_parameter(&Interner) == self,
-                                _ => false,
-                            })
-                            .collect_vec();
-
-                        Some(predicates)
-                    }
-                    _ => None,
-                }
-            }
-            _ => None,
-        }
-    }
-
-    pub fn associated_type_parent_trait(&self, db: &dyn HirDatabase) -> Option<TraitId> {
-        match self.kind(&Interner) {
-            TyKind::AssociatedType(id, ..) => {
-                match from_assoc_type_id(*id).lookup(db.upcast()).container {
-                    AssocContainerId::TraitId(trait_id) => Some(trait_id),
-                    _ => None,
-                }
-            }
-            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,
-                }
-            }
-            _ => None,
-        }
-    }
 }
 
 #[derive(Copy, Clone, PartialEq, Eq, Debug, Hash)]
@@ -488,6 +288,12 @@ pub fn lt_from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> L
     db.lookup_intern_lifetime_param_id(interned_id)
 }
 
+pub fn const_from_placeholder_idx(db: &dyn HirDatabase, idx: PlaceholderIndex) -> ConstParamId {
+    assert_eq!(idx.ui, chalk_ir::UniverseIndex::ROOT);
+    let interned_id = salsa::InternKey::from_intern_id(salsa::InternId::from(idx.idx));
+    db.lookup_intern_const_param_id(interned_id)
+}
+
 pub fn to_chalk_trait_id(id: TraitId) -> ChalkTraitId {
     chalk_ir::TraitId(salsa::InternKey::as_intern_id(&id))
 }
@@ -499,3 +305,12 @@ pub fn from_chalk_trait_id(id: ChalkTraitId) -> TraitId {
 pub fn static_lifetime() -> Lifetime {
     LifetimeData::Static.intern(&Interner)
 }
+
+pub fn dummy_usize_const() -> Const {
+    let usize_ty = chalk_ir::TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner);
+    chalk_ir::ConstData {
+        ty: usize_ty,
+        value: chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst { interned: () }),
+    }
+    .intern(&Interner)
+}
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index df6619af3..8be1bcddb 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -27,7 +27,7 @@ use stdx::impl_from;
 
 use crate::{
     db::HirDatabase,
-    static_lifetime, to_assoc_type_id, to_chalk_trait_id, to_placeholder_idx,
+    dummy_usize_const, static_lifetime, to_assoc_type_id, to_chalk_trait_id, to_placeholder_idx,
     traits::chalk::{Interner, ToChalk},
     utils::{
         all_super_trait_refs, associated_type_by_name_including_super_traits, generics,
@@ -166,7 +166,7 @@ impl<'a> TyLoweringContext<'a> {
             }
             TypeRef::Array(inner) => {
                 let inner_ty = self.lower_ty(inner);
-                TyKind::Array(inner_ty).intern(&Interner)
+                TyKind::Array(inner_ty, dummy_usize_const()).intern(&Interner)
             }
             TypeRef::Slice(inner) => {
                 let inner_ty = self.lower_ty(inner);
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index 436dea22b..ee725fd46 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -22,7 +22,7 @@ use crate::{
     static_lifetime,
     utils::all_super_traits,
     AdtId, Canonical, CanonicalVarKinds, DebruijnIndex, FnPointer, FnSig, ForeignDefId,
-    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyBuilder, TyKind,
+    InEnvironment, Interner, Scalar, Substitution, TraitEnvironment, Ty, TyBuilder, TyExt, TyKind,
     TypeWalk,
 };
 
@@ -842,7 +842,9 @@ fn autoderef_method_receiver(
 ) -> Vec<Canonical<Ty>> {
     let mut deref_chain: Vec<_> = autoderef::autoderef(db, Some(krate), ty).collect();
     // As a last step, we can do array unsizing (that's the only unsizing that rustc does for method receivers!)
-    if let Some(TyKind::Array(parameters)) = deref_chain.last().map(|ty| ty.value.kind(&Interner)) {
+    if let Some(TyKind::Array(parameters, _)) =
+        deref_chain.last().map(|ty| ty.value.kind(&Interner))
+    {
         let kinds = deref_chain.last().unwrap().binders.clone();
         let unsized_ty = TyKind::Slice(parameters.clone()).intern(&Interner);
         deref_chain.push(Canonical { value: unsized_ty, binders: kinds })
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index 5a8b5cd86..f03b92422 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -22,7 +22,7 @@ use crate::{
     to_assoc_type_id, to_chalk_trait_id,
     utils::generics,
     AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId, ProjectionTy, Substitution,
-    TraitRef, Ty, TyBuilder, TyKind, WhereClause,
+    TraitRef, Ty, TyBuilder, TyExt, TyKind, WhereClause,
 };
 use mapping::{
     convert_where_clauses, generic_predicate_to_inline_bound, make_binders, TypeAliasAsValue,
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 9267e32b5..cf73cb078 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -10,9 +10,10 @@ use base_db::salsa::InternKey;
 use hir_def::{GenericDefId, TypeAliasId};
 
 use crate::{
-    chalk_ext::ProjectionTyExt, db::HirDatabase, primitive::UintTy, static_lifetime, AliasTy,
-    CallableDefId, Canonical, DomainGoal, FnPointer, GenericArg, InEnvironment, Lifetime, OpaqueTy,
-    ProjectionTy, QuantifiedWhereClause, Scalar, Substitution, TraitRef, Ty, TypeWalk, WhereClause,
+    chalk_ext::ProjectionTyExt, db::HirDatabase, dummy_usize_const, static_lifetime, AliasTy,
+    CallableDefId, Canonical, Const, DomainGoal, FnPointer, GenericArg, InEnvironment, Lifetime,
+    OpaqueTy, ProjectionTy, QuantifiedWhereClause, Substitution, TraitRef, Ty, TypeWalk,
+    WhereClause,
 };
 
 use super::interner::*;
@@ -23,7 +24,7 @@ impl ToChalk for Ty {
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Ty<Interner> {
         match self.into_inner() {
             TyKind::Ref(m, lt, ty) => ref_to_chalk(db, m, lt, ty),
-            TyKind::Array(ty) => array_to_chalk(db, ty),
+            TyKind::Array(ty, size) => array_to_chalk(db, ty, size),
             TyKind::Function(FnPointer { sig, substitution: substs, .. }) => {
                 let substitution = chalk_ir::FnSubst(substs.0.to_chalk(db));
                 chalk_ir::TyKind::Function(chalk_ir::FnPointer {
@@ -110,7 +111,7 @@ impl ToChalk for Ty {
     fn from_chalk(db: &dyn HirDatabase, chalk: chalk_ir::Ty<Interner>) -> Self {
         match chalk.data(&Interner).kind.clone() {
             chalk_ir::TyKind::Error => TyKind::Error,
-            chalk_ir::TyKind::Array(ty, _size) => TyKind::Array(from_chalk(db, ty)),
+            chalk_ir::TyKind::Array(ty, size) => TyKind::Array(from_chalk(db, ty), size),
             chalk_ir::TyKind::Placeholder(idx) => TyKind::Placeholder(idx),
             chalk_ir::TyKind::Alias(chalk_ir::AliasTy::Projection(proj)) => {
                 let associated_ty = proj.associated_ty_id;
@@ -203,15 +204,9 @@ fn ref_to_chalk(
 
 /// We currently don't model constants, but Chalk does. So, we have to insert a
 /// fake constant here, because Chalks built-in logic may expect it to be there.
-fn array_to_chalk(db: &dyn HirDatabase, ty: Ty) -> chalk_ir::Ty<Interner> {
+fn array_to_chalk(db: &dyn HirDatabase, ty: Ty, _: Const) -> chalk_ir::Ty<Interner> {
     let arg = ty.to_chalk(db);
-    let usize_ty = chalk_ir::TyKind::Scalar(Scalar::Uint(UintTy::Usize)).intern(&Interner);
-    let const_ = chalk_ir::ConstData {
-        ty: usize_ty,
-        value: chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst { interned: () }),
-    }
-    .intern(&Interner);
-    chalk_ir::TyKind::Array(arg, const_).intern(&Interner)
+    chalk_ir::TyKind::Array(arg, dummy_usize_const()).intern(&Interner)
 }
 
 impl ToChalk for GenericArg {
diff --git a/crates/hir_ty/src/types.rs b/crates/hir_ty/src/types.rs
index 844e57896..89c0ddd1a 100644
--- a/crates/hir_ty/src/types.rs
+++ b/crates/hir_ty/src/types.rs
@@ -10,7 +10,7 @@ use chalk_ir::{
 use smallvec::SmallVec;
 
 use crate::{
-    AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, FnDefId, FnSig, ForeignDefId,
+    AssocTypeId, CanonicalVarKinds, ChalkTraitId, ClosureId, Const, FnDefId, FnSig, ForeignDefId,
     InferenceVar, Interner, Lifetime, OpaqueTyId, PlaceholderIndex, TypeWalk, VariableKind,
     VariableKinds,
 };
@@ -114,7 +114,7 @@ pub enum TyKind {
     Tuple(usize, Substitution),
 
     /// An array with the given length. Written as `[T; n]`.
-    Array(Ty),
+    Array(Ty, Const),
 
     /// The pointee of an array slice.  Written as `[T]`.
     Slice(Ty),
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs
index 4cc4e24fd..41ebf6137 100644
--- a/crates/hir_ty/src/walk.rs
+++ b/crates/hir_ty/src/walk.rs
@@ -153,7 +153,10 @@ impl TypeWalk for Ty {
                     p.walk(f);
                 }
             }
-            TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, _, ty) | TyKind::Raw(_, ty) => {
+            TyKind::Slice(ty)
+            | TyKind::Array(ty, _)
+            | TyKind::Ref(_, _, ty)
+            | TyKind::Raw(_, ty) => {
                 ty.walk(f);
             }
             TyKind::Function(fn_pointer) => {
@@ -187,7 +190,10 @@ impl TypeWalk for Ty {
             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) => {
+            TyKind::Slice(ty)
+            | TyKind::Array(ty, _)
+            | TyKind::Ref(_, _, ty)
+            | TyKind::Raw(_, ty) => {
                 ty.walk_mut_binders(f, binders);
             }
             TyKind::Function(fn_pointer) => {
diff --git a/crates/rust-analyzer/src/cli/analysis_stats.rs b/crates/rust-analyzer/src/cli/analysis_stats.rs
index 18fd7ea74..fe9f273b0 100644
--- a/crates/rust-analyzer/src/cli/analysis_stats.rs
+++ b/crates/rust-analyzer/src/cli/analysis_stats.rs
@@ -12,7 +12,7 @@ use hir::{
     AssocItem, Crate, Function, HasSource, HirDisplay, ModuleDef,
 };
 use hir_def::FunctionId;
-use hir_ty::TypeWalk;
+use hir_ty::{TyExt, TypeWalk};
 use ide::{AnalysisHost, RootDatabase};
 use ide_db::base_db::{
     salsa::{self, ParallelDatabase},
diff --git a/crates/vfs/Cargo.toml b/crates/vfs/Cargo.toml
index c318a68f7..894944b18 100644
--- a/crates/vfs/Cargo.toml
+++ b/crates/vfs/Cargo.toml
@@ -14,3 +14,4 @@ rustc-hash = "1.0"
 fst = "0.4"
 
 paths = { path = "../paths", version = "0.0.0" }
+indexmap = "1.6.2"
diff --git a/crates/vfs/src/path_interner.rs b/crates/vfs/src/path_interner.rs
index 2189e5e25..6e049f0d4 100644
--- a/crates/vfs/src/path_interner.rs
+++ b/crates/vfs/src/path_interner.rs
@@ -1,15 +1,22 @@
 //! Maps paths to compact integer ids. We don't care about clearings paths which
 //! no longer exist -- the assumption is total size of paths we ever look at is
 //! not too big.
-use rustc_hash::FxHashMap;
+use std::hash::BuildHasherDefault;
+
+use indexmap::IndexSet;
+use rustc_hash::FxHasher;
 
 use crate::{FileId, VfsPath};
 
 /// Structure to map between [`VfsPath`] and [`FileId`].
-#[derive(Default)]
 pub(crate) struct PathInterner {
-    map: FxHashMap<VfsPath, FileId>,
-    vec: Vec<VfsPath>,
+    map: IndexSet<VfsPath, BuildHasherDefault<FxHasher>>,
+}
+
+impl Default for PathInterner {
+    fn default() -> Self {
+        Self { map: IndexSet::default() }
+    }
 }
 
 impl PathInterner {
@@ -17,7 +24,7 @@ impl PathInterner {
     ///
     /// If `path` does not exists in `self`, returns [`None`].
     pub(crate) fn get(&self, path: &VfsPath) -> Option<FileId> {
-        self.map.get(path).copied()
+        self.map.get_index_of(path).map(|i| FileId(i as u32))
     }
 
     /// Insert `path` in `self`.
@@ -25,13 +32,9 @@ impl PathInterner {
     /// - If `path` already exists in `self`, returns its associated id;
     /// - Else, returns a newly allocated id.
     pub(crate) fn intern(&mut self, path: VfsPath) -> FileId {
-        if let Some(id) = self.get(&path) {
-            return id;
-        }
-        let id = FileId(self.vec.len() as u32);
-        self.map.insert(path.clone(), id);
-        self.vec.push(path);
-        id
+        let (id, _added) = self.map.insert_full(path);
+        assert!(id < u32::MAX as usize);
+        FileId(id as u32)
     }
 
     /// Returns the path corresponding to `id`.
@@ -40,6 +43,6 @@ impl PathInterner {
     ///
     /// Panics if `id` does not exists in `self`.
     pub(crate) fn lookup(&self, id: FileId) -> &VfsPath {
-        &self.vec[id.0 as usize]
+        self.map.get_index(id.0 as usize).unwrap()
     }
 }