Merge #8366

8366: Add chalk_ir::Const to TyKind::Array r=flodiebold a=Veykril

CC #8313

Co-authored-by: Lukas Wirth <[email protected]>

12 files changed, 109 insertions, 45 deletions

diff --git a/crates/hir/src/lib.rs b/crates/hir/src/lib.rs
index 813cd1295..dfc1d8a0c 100644
--- a/crates/hir/src/lib.rs
+++ b/crates/hir/src/lib.rs
@@ -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_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/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/expr.rs b/crates/hir_ty/src/infer/expr.rs
index 796487d02..53d94fd0d 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},
@@ -702,7 +702,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 +726,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 +736,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..c1d7a6b76 100644
--- a/crates/hir_ty/src/infer/pat.rs
+++ b/crates/hir_ty/src/infer/pat.rs
@@ -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/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..a2a5bcc07 100644
--- a/crates/hir_ty/src/lib.rs
+++ b/crates/hir_ty/src/lib.rs
@@ -30,12 +30,13 @@ mod test_db;
 
 use std::sync::Arc;
 
+use chalk_ir::UintTy;
 use itertools::Itertools;
 
 use base_db::salsa;
 use hir_def::{
-    expr::ExprId, type_ref::Rawness, AssocContainerId, FunctionId, GenericDefId, HasModule,
-    LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
+    expr::ExprId, type_ref::Rawness, AssocContainerId, ConstParamId, FunctionId, GenericDefId,
+    HasModule, LifetimeParamId, Lookup, TraitId, TypeAliasId, TypeParamId,
 };
 
 use crate::{db::HirDatabase, display::HirDisplay, utils::generics};
@@ -71,6 +72,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>;
@@ -227,7 +233,9 @@ impl Ty {
     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, ..)) => {
@@ -488,6 +496,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 +513,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..5042bfbca 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -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/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) => {