Merge #5319

5319: Chalk upgrade r=flodiebold a=flodiebold

 - upgrade Chalk
 - make use of Chalk's `Unsize` impls, remove ours
 - use Chalk's built-in array type
 - search efficiently for impls for an int/float variable
 - output Chalk tracing logs in hir_ty tests

Fixes #2534.
Fixes #5057.
Fixes #4374.
Fixes #4281.

Co-authored-by: Florian Diebold <[email protected]>
Co-authored-by: Florian Diebold <[email protected]>

3 files changed, 66 insertions, 13 deletions

diff --git a/crates/ra_hir_ty/src/traits/chalk/interner.rs b/crates/ra_hir_ty/src/traits/chalk/interner.rs
index 15426b022..156b691b4 100644
--- a/crates/ra_hir_ty/src/traits/chalk/interner.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/interner.rs
@@ -39,6 +39,7 @@ impl chalk_ir::interner::Interner for Interner {
     type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
     type InternedVariableKinds = Vec<chalk_ir::VariableKind<Self>>;
     type InternedCanonicalVarKinds = Vec<chalk_ir::CanonicalVarKind<Self>>;
+    type InternedConstraints = Vec<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>>;
     type DefId = InternId;
     type InternedAdtId = crate::TypeCtorId;
     type Identifier = TypeAliasId;
@@ -349,6 +350,20 @@ impl chalk_ir::interner::Interner for Interner {
     ) -> &'a [chalk_ir::CanonicalVarKind<Self>] {
         &canonical_var_kinds
     }
+
+    fn intern_constraints<E>(
+        &self,
+        data: impl IntoIterator<Item = Result<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>, E>>,
+    ) -> Result<Self::InternedConstraints, E> {
+        data.into_iter().collect()
+    }
+
+    fn constraints_data<'a>(
+        &self,
+        constraints: &'a Self::InternedConstraints,
+    ) -> &'a [chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>] {
+        constraints
+    }
 }
 
 impl chalk_ir::interner::HasInterner for Interner {
diff --git a/crates/ra_hir_ty/src/traits/chalk/mapping.rs b/crates/ra_hir_ty/src/traits/chalk/mapping.rs
index 433d6aa03..7dc9ee759 100644
--- a/crates/ra_hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/mapping.rs
@@ -29,6 +29,7 @@ impl ToChalk for Ty {
         match self {
             Ty::Apply(apply_ty) => match apply_ty.ctor {
                 TypeCtor::Ref(m) => ref_to_chalk(db, m, apply_ty.parameters),
+                TypeCtor::Array => array_to_chalk(db, apply_ty.parameters),
                 TypeCtor::FnPtr { num_args: _ } => {
                     let substitution = apply_ty.parameters.to_chalk(db).shifted_in(&Interner);
                     chalk_ir::TyData::Function(chalk_ir::Fn { num_binders: 0, substitution })
@@ -61,13 +62,13 @@ impl ToChalk for Ty {
             Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx).intern(&Interner),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
             Ty::Dyn(predicates) => {
-                let where_clauses = chalk_ir::QuantifiedWhereClauses::from(
+                let where_clauses = chalk_ir::QuantifiedWhereClauses::from_iter(
                     &Interner,
                     predicates.iter().filter(|p| !p.is_error()).cloned().map(|p| p.to_chalk(db)),
                 );
                 let bounded_ty = chalk_ir::DynTy {
                     bounds: make_binders(where_clauses, 1),
-                    lifetime: LIFETIME_PLACEHOLDER.to_lifetime(&Interner),
+                    lifetime: FAKE_PLACEHOLDER.to_lifetime(&Interner),
                 };
                 chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner)
             }
@@ -92,6 +93,7 @@ impl ToChalk for Ty {
             chalk_ir::TyData::Apply(apply_ty) => match apply_ty.name {
                 TypeName::Error => Ty::Unknown,
                 TypeName::Ref(m) => ref_from_chalk(db, m, apply_ty.substitution),
+                TypeName::Array => array_from_chalk(db, apply_ty.substitution),
                 _ => {
                     let ctor = from_chalk(db, apply_ty.name);
                     let parameters = from_chalk(db, apply_ty.substitution);
@@ -138,7 +140,7 @@ impl ToChalk for Ty {
     }
 }
 
-const LIFETIME_PLACEHOLDER: PlaceholderIndex =
+const FAKE_PLACEHOLDER: PlaceholderIndex =
     PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::MAX };
 
 /// We currently don't model lifetimes, but Chalk does. So, we have to insert a
@@ -149,10 +151,10 @@ fn ref_to_chalk(
     subst: Substs,
 ) -> chalk_ir::Ty<Interner> {
     let arg = subst[0].clone().to_chalk(db);
-    let lifetime = LIFETIME_PLACEHOLDER.to_lifetime(&Interner);
+    let lifetime = FAKE_PLACEHOLDER.to_lifetime(&Interner);
     chalk_ir::ApplicationTy {
         name: TypeName::Ref(mutability.to_chalk(db)),
-        substitution: chalk_ir::Substitution::from(
+        substitution: chalk_ir::Substitution::from_iter(
             &Interner,
             vec![lifetime.cast(&Interner), arg.cast(&Interner)],
         ),
@@ -173,11 +175,40 @@ fn ref_from_chalk(
     Ty::apply(TypeCtor::Ref(from_chalk(db, mutability)), Substs(tys))
 }
 
+/// 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, subst: Substs) -> chalk_ir::Ty<Interner> {
+    let arg = subst[0].clone().to_chalk(db);
+    let usize_ty = chalk_ir::ApplicationTy {
+        name: TypeName::Scalar(Scalar::Uint(chalk_ir::UintTy::Usize)),
+        substitution: chalk_ir::Substitution::empty(&Interner),
+    }
+    .intern(&Interner);
+    let const_ = FAKE_PLACEHOLDER.to_const(&Interner, usize_ty);
+    chalk_ir::ApplicationTy {
+        name: TypeName::Array,
+        substitution: chalk_ir::Substitution::from_iter(
+            &Interner,
+            vec![arg.cast(&Interner), const_.cast(&Interner)],
+        ),
+    }
+    .intern(&Interner)
+}
+
+/// Here we remove the const from the type we got from Chalk.
+fn array_from_chalk(db: &dyn HirDatabase, subst: chalk_ir::Substitution<Interner>) -> Ty {
+    let tys = subst
+        .iter(&Interner)
+        .filter_map(|p| Some(from_chalk(db, p.ty(&Interner)?.clone())))
+        .collect();
+    Ty::apply(TypeCtor::Array, Substs(tys))
+}
+
 impl ToChalk for Substs {
     type Chalk = chalk_ir::Substitution<Interner>;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution<Interner> {
-        chalk_ir::Substitution::from(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
+        chalk_ir::Substitution::from_iter(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
     }
 
     fn from_chalk(db: &dyn HirDatabase, parameters: chalk_ir::Substitution<Interner>) -> Substs {
@@ -263,6 +294,7 @@ impl ToChalk for TypeCtor {
             TypeCtor::Tuple { cardinality } => TypeName::Tuple(cardinality.into()),
             TypeCtor::RawPtr(mutability) => TypeName::Raw(mutability.to_chalk(db)),
             TypeCtor::Slice => TypeName::Slice,
+            TypeCtor::Array => TypeName::Array,
             TypeCtor::Ref(mutability) => TypeName::Ref(mutability.to_chalk(db)),
             TypeCtor::Str => TypeName::Str,
             TypeCtor::FnDef(callable_def) => {
@@ -271,10 +303,8 @@ impl ToChalk for TypeCtor {
             }
             TypeCtor::Never => TypeName::Never,
 
-            TypeCtor::Adt(_)
-            | TypeCtor::Array
-            | TypeCtor::FnPtr { .. }
-            | TypeCtor::Closure { .. } => {
+            // FIXME convert these
+            TypeCtor::Adt(_) | TypeCtor::FnPtr { .. } | TypeCtor::Closure { .. } => {
                 // other TypeCtors get interned and turned into a chalk StructId
                 let struct_id = db.intern_type_ctor(self).into();
                 TypeName::Adt(struct_id)
@@ -492,6 +522,11 @@ impl ToChalk for GenericPredicate {
                 // we shouldn't get these from Chalk
                 panic!("encountered LifetimeOutlives from Chalk")
             }
+
+            chalk_ir::WhereClause::TypeOutlives(_) => {
+                // we shouldn't get these from Chalk
+                panic!("encountered TypeOutlives from Chalk")
+            }
         }
     }
 }
@@ -570,7 +605,10 @@ where
                 )
             });
         let value = self.value.to_chalk(db);
-        chalk_ir::Canonical { value, binders: chalk_ir::CanonicalVarKinds::from(&Interner, kinds) }
+        chalk_ir::Canonical {
+            value,
+            binders: chalk_ir::CanonicalVarKinds::from_iter(&Interner, kinds),
+        }
     }
 
     fn from_chalk(db: &dyn HirDatabase, canonical: chalk_ir::Canonical<T::Chalk>) -> Canonical<T> {
@@ -691,7 +729,7 @@ where
     T: HasInterner<Interner = Interner>,
 {
     chalk_ir::Binders::new(
-        chalk_ir::VariableKinds::from(
+        chalk_ir::VariableKinds::from_iter(
             &Interner,
             std::iter::repeat(chalk_ir::VariableKind::Ty(chalk_ir::TyKind::General)).take(num_vars),
         ),
diff --git a/crates/ra_hir_ty/src/traits/chalk/tls.rs b/crates/ra_hir_ty/src/traits/chalk/tls.rs
index e6a9d3211..1e226baea 100644
--- a/crates/ra_hir_ty/src/traits/chalk/tls.rs
+++ b/crates/ra_hir_ty/src/traits/chalk/tls.rs
@@ -157,7 +157,7 @@ impl DebugContext<'_> {
             _ => panic!("associated type not in trait"),
         };
         let trait_data = self.0.trait_data(trait_);
-        let params = projection_ty.substitution.parameters(&Interner);
+        let params = projection_ty.substitution.as_slice(&Interner);
         write!(fmt, "<{:?} as {}", &params[0], trait_data.name,)?;
         if params.len() > 1 {
             write!(