Merge #2872

2872: Upgrade Chalk r=matklad a=flodiebold

This is just keeping track of the changes required to upgrade Chalk; currently we can't really merge it since it breaks opaque types.

Now also makes use of the newly introduced `solve_limited` to implement fuel.

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

4 files changed, 73 insertions, 62 deletions

diff --git a/crates/ra_hir_ty/Cargo.toml b/crates/ra_hir_ty/Cargo.toml
index d229639d9..f5484bf70 100644
--- a/crates/ra_hir_ty/Cargo.toml
+++ b/crates/ra_hir_ty/Cargo.toml
@@ -21,9 +21,9 @@ ra_prof = { path = "../ra_prof" }
 ra_syntax = { path = "../ra_syntax" }
 test_utils = { path = "../test_utils" }
 
-chalk-solve =   { git = "https://github.com/rust-lang/chalk.git", rev = "ff65b5ac9860f3c36bd892c865ab23d5ff0bbae5" }
-chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "ff65b5ac9860f3c36bd892c865ab23d5ff0bbae5" }
-chalk-ir =      { git = "https://github.com/rust-lang/chalk.git", rev = "ff65b5ac9860f3c36bd892c865ab23d5ff0bbae5" }
+chalk-solve =   { git = "https://github.com/rust-lang/chalk.git", rev = "af48f302a1f571b3ca418f7c5aa639a144a34f75" }
+chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "af48f302a1f571b3ca418f7c5aa639a144a34f75" }
+chalk-ir =      { git = "https://github.com/rust-lang/chalk.git", rev = "af48f302a1f571b3ca418f7c5aa639a144a34f75" }
 
 lalrpop-intern = "0.15.1"
 
diff --git a/crates/ra_hir_ty/src/tests/traits.rs b/crates/ra_hir_ty/src/tests/traits.rs
index 4b268510c..bc20a49cc 100644
--- a/crates/ra_hir_ty/src/tests/traits.rs
+++ b/crates/ra_hir_ty/src/tests/traits.rs
@@ -850,6 +850,7 @@ fn test<T: ApplyL>(t: T) {
 }
 
 #[test]
+#[ignore]
 fn impl_trait() {
     assert_snapshot!(
         infer(r#"
@@ -1021,6 +1022,7 @@ fn test() {
 }
 
 #[test]
+#[ignore]
 fn error_bound_chalk() {
     let t = type_at(
         r#"
diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs
index 4aabd66dc..88af61e87 100644
--- a/crates/ra_hir_ty/src/traits.rs
+++ b/crates/ra_hir_ty/src/traits.rs
@@ -50,10 +50,19 @@ impl TraitSolver {
             Err(_) => ra_db::Canceled::throw(),
         };
 
+        let fuel = std::cell::Cell::new(CHALK_SOLVER_FUEL);
+
         let solution = panic::catch_unwind({
             let solver = panic::AssertUnwindSafe(&mut solver);
             let context = panic::AssertUnwindSafe(&context);
-            move || solver.0.solve(context.0, goal)
+            move || {
+                solver.0.solve_limited(context.0, goal, || {
+                    context.0.db.check_canceled();
+                    let remaining = fuel.get();
+                    fuel.set(remaining - 1);
+                    remaining > 0
+                })
+            }
         });
 
         let solution = match solution {
@@ -78,7 +87,9 @@ impl TraitSolver {
 /// This controls the maximum size of types Chalk considers. If we set this too
 /// high, we can run into slow edge cases; if we set it too low, Chalk won't
 /// find some solutions.
-const CHALK_SOLVER_MAX_SIZE: usize = 4;
+const CHALK_SOLVER_MAX_SIZE: usize = 10;
+/// This controls how much 'time' we give the Chalk solver before giving up.
+const CHALK_SOLVER_FUEL: i32 = 100;
 
 #[derive(Debug, Copy, Clone)]
 struct ChalkContext<'a, DB> {
@@ -97,7 +108,8 @@ pub(crate) fn trait_solver_query(
 }
 
 fn create_chalk_solver() -> chalk_solve::Solver<TypeFamily> {
-    let solver_choice = chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE };
+    let solver_choice =
+        chalk_solve::SolverChoice::SLG { max_size: CHALK_SOLVER_MAX_SIZE, expected_answers: None };
     solver_choice.into_solver()
 }
 
@@ -232,7 +244,6 @@ fn solution_from_chalk(
     let convert_subst = |subst: chalk_ir::Canonical<chalk_ir::Substitution<TypeFamily>>| {
         let value = subst
             .value
-            .parameters
             .into_iter()
             .map(|p| {
                 let ty = match p.ty() {
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index 555930c9b..fe9cb556c 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -3,7 +3,7 @@ use std::{fmt, sync::Arc};
 
 use log::debug;
 
-use chalk_ir::{cast::Cast, Parameter, PlaceholderIndex, TypeName, UniverseIndex};
+use chalk_ir::{cast::Cast, GoalData, Parameter, PlaceholderIndex, TypeName, UniverseIndex};
 
 use hir_def::{AssocContainerId, AssocItemId, GenericDefId, HasModule, Lookup, TypeAliasId};
 use ra_db::{
@@ -24,6 +24,8 @@ impl chalk_ir::family::TypeFamily for TypeFamily {
     type InternedType = Box<chalk_ir::TyData<Self>>;
     type InternedLifetime = chalk_ir::LifetimeData<Self>;
     type InternedParameter = chalk_ir::ParameterData<Self>;
+    type InternedGoal = Arc<GoalData<Self>>;
+    type InternedSubstitution = Vec<Parameter<Self>>;
     type DefId = InternId;
 
     // FIXME: implement these
@@ -48,8 +50,8 @@ impl chalk_ir::family::TypeFamily for TypeFamily {
         None
     }
 
-    fn debug_projection(
-        _projection: &chalk_ir::ProjectionTy<Self>,
+    fn debug_alias(
+        _projection: &chalk_ir::AliasTy<Self>,
         _fmt: &mut fmt::Formatter<'_>,
     ) -> Option<fmt::Result> {
         None
@@ -78,6 +80,24 @@ impl chalk_ir::family::TypeFamily for TypeFamily {
     fn parameter_data(parameter: &chalk_ir::ParameterData<Self>) -> &chalk_ir::ParameterData<Self> {
         parameter
     }
+
+    fn intern_goal(goal: GoalData<Self>) -> Arc<GoalData<Self>> {
+        Arc::new(goal)
+    }
+
+    fn goal_data(goal: &Arc<GoalData<Self>>) -> &GoalData<Self> {
+        goal
+    }
+
+    fn intern_substitution<E>(
+        data: impl IntoIterator<Item = Result<Parameter<Self>, E>>,
+    ) -> Result<Vec<Parameter<Self>>, E> {
+        data.into_iter().collect()
+    }
+
+    fn substitution_data(substitution: &Vec<Parameter<Self>>) -> &[Parameter<Self>] {
+        substitution
+    }
 }
 
 impl chalk_ir::family::HasTypeFamily for TypeFamily {
@@ -114,13 +134,13 @@ impl ToChalk for Ty {
         match self {
             Ty::Apply(apply_ty) => {
                 let name = apply_ty.ctor.to_chalk(db);
-                let parameters = apply_ty.parameters.to_chalk(db);
-                chalk_ir::ApplicationTy { name, parameters }.cast().intern()
+                let substitution = apply_ty.parameters.to_chalk(db);
+                chalk_ir::ApplicationTy { name, substitution }.cast().intern()
             }
             Ty::Projection(proj_ty) => {
                 let associated_ty_id = proj_ty.associated_ty.to_chalk(db);
-                let parameters = proj_ty.parameters.to_chalk(db);
-                chalk_ir::ProjectionTy { associated_ty_id, parameters }.cast().intern()
+                let substitution = proj_ty.parameters.to_chalk(db);
+                chalk_ir::AliasTy { associated_ty_id, substitution }.cast().intern()
             }
             Ty::Param { idx, .. } => {
                 PlaceholderIndex { ui: UniverseIndex::ROOT, idx: idx as usize }
@@ -135,23 +155,13 @@ impl ToChalk for Ty {
                     .cloned()
                     .map(|p| p.to_chalk(db))
                     .collect();
-                let bounded_ty = chalk_ir::BoundedTy { bounds: make_binders(where_clauses, 1) };
+                let bounded_ty = chalk_ir::DynTy { bounds: make_binders(where_clauses, 1) };
                 chalk_ir::TyData::Dyn(bounded_ty).intern()
             }
-            Ty::Opaque(predicates) => {
-                let where_clauses = predicates
-                    .iter()
-                    .filter(|p| !p.is_error())
-                    .cloned()
-                    .map(|p| p.to_chalk(db))
-                    .collect();
-                let bounded_ty = chalk_ir::BoundedTy { bounds: make_binders(where_clauses, 1) };
-                chalk_ir::TyData::Opaque(bounded_ty).intern()
-            }
-            Ty::Unknown => {
-                let parameters = Vec::new();
+            Ty::Opaque(_) | Ty::Unknown => {
+                let substitution = chalk_ir::Substitution::empty();
                 let name = TypeName::Error;
-                chalk_ir::ApplicationTy { name, parameters }.cast().intern()
+                chalk_ir::ApplicationTy { name, substitution }.cast().intern()
             }
         }
     }
@@ -161,7 +171,7 @@ impl ToChalk for Ty {
                 TypeName::Error => Ty::Unknown,
                 _ => {
                     let ctor = from_chalk(db, apply_ty.name);
-                    let parameters = from_chalk(db, apply_ty.parameters);
+                    let parameters = from_chalk(db, apply_ty.substitution);
                     Ty::Apply(ApplicationTy { ctor, parameters })
                 }
             },
@@ -169,12 +179,12 @@ impl ToChalk for Ty {
                 assert_eq!(idx.ui, UniverseIndex::ROOT);
                 Ty::Param { idx: idx.idx as u32, name: crate::Name::missing() }
             }
-            chalk_ir::TyData::Projection(proj) => {
+            chalk_ir::TyData::Alias(proj) => {
                 let associated_ty = from_chalk(db, proj.associated_ty_id);
-                let parameters = from_chalk(db, proj.parameters);
+                let parameters = from_chalk(db, proj.substitution);
                 Ty::Projection(ProjectionTy { associated_ty, parameters })
             }
-            chalk_ir::TyData::ForAll(_) => unimplemented!(),
+            chalk_ir::TyData::Function(_) => unimplemented!(),
             chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx as u32),
             chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
             chalk_ir::TyData::Dyn(where_clauses) => {
@@ -183,27 +193,18 @@ impl ToChalk for Ty {
                     where_clauses.bounds.value.into_iter().map(|c| from_chalk(db, c)).collect();
                 Ty::Dyn(predicates)
             }
-            chalk_ir::TyData::Opaque(where_clauses) => {
-                assert_eq!(where_clauses.bounds.binders.len(), 1);
-                let predicates =
-                    where_clauses.bounds.value.into_iter().map(|c| from_chalk(db, c)).collect();
-                Ty::Opaque(predicates)
-            }
         }
     }
 }
 
 impl ToChalk for Substs {
-    type Chalk = Vec<chalk_ir::Parameter<TypeFamily>>;
+    type Chalk = chalk_ir::Substitution<TypeFamily>;
 
-    fn to_chalk(self, db: &impl HirDatabase) -> Vec<Parameter<TypeFamily>> {
-        self.iter().map(|ty| ty.clone().to_chalk(db).cast()).collect()
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Substitution<TypeFamily> {
+        chalk_ir::Substitution::from(self.iter().map(|ty| ty.clone().to_chalk(db)))
     }
 
-    fn from_chalk(
-        db: &impl HirDatabase,
-        parameters: Vec<chalk_ir::Parameter<TypeFamily>>,
-    ) -> Substs {
+    fn from_chalk(db: &impl HirDatabase, parameters: chalk_ir::Substitution<TypeFamily>) -> Substs {
         let tys = parameters
             .into_iter()
             .map(|p| match p.ty() {
@@ -220,13 +221,13 @@ impl ToChalk for TraitRef {
 
     fn to_chalk(self: TraitRef, db: &impl HirDatabase) -> chalk_ir::TraitRef<TypeFamily> {
         let trait_id = self.trait_.to_chalk(db);
-        let parameters = self.substs.to_chalk(db);
-        chalk_ir::TraitRef { trait_id, parameters }
+        let substitution = self.substs.to_chalk(db);
+        chalk_ir::TraitRef { trait_id, substitution }
     }
 
     fn from_chalk(db: &impl HirDatabase, trait_ref: chalk_ir::TraitRef<TypeFamily>) -> Self {
         let trait_ = from_chalk(db, trait_ref.trait_id);
-        let substs = from_chalk(db, trait_ref.parameters);
+        let substs = from_chalk(db, trait_ref.substitution);
         TraitRef { trait_, substs }
     }
 }
@@ -317,8 +318,8 @@ impl ToChalk for GenericPredicate {
                 make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0)
             }
             GenericPredicate::Projection(projection_pred) => make_binders(
-                chalk_ir::WhereClause::ProjectionEq(chalk_ir::ProjectionEq {
-                    projection: projection_pred.projection_ty.to_chalk(db),
+                chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq {
+                    alias: projection_pred.projection_ty.to_chalk(db),
                     ty: projection_pred.ty.to_chalk(db),
                 }),
                 0,
@@ -335,8 +336,8 @@ impl ToChalk for GenericPredicate {
             chalk_ir::WhereClause::Implemented(tr) => {
                 GenericPredicate::Implemented(from_chalk(db, tr))
             }
-            chalk_ir::WhereClause::ProjectionEq(projection_eq) => {
-                let projection_ty = from_chalk(db, projection_eq.projection);
+            chalk_ir::WhereClause::AliasEq(projection_eq) => {
+                let projection_ty = from_chalk(db, projection_eq.alias);
                 let ty = from_chalk(db, projection_eq.ty);
                 GenericPredicate::Projection(super::ProjectionPredicate { projection_ty, ty })
             }
@@ -345,22 +346,22 @@ impl ToChalk for GenericPredicate {
 }
 
 impl ToChalk for ProjectionTy {
-    type Chalk = chalk_ir::ProjectionTy<TypeFamily>;
+    type Chalk = chalk_ir::AliasTy<TypeFamily>;
 
-    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::ProjectionTy<TypeFamily> {
-        chalk_ir::ProjectionTy {
+    fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::AliasTy<TypeFamily> {
+        chalk_ir::AliasTy {
             associated_ty_id: self.associated_ty.to_chalk(db),
-            parameters: self.parameters.to_chalk(db),
+            substitution: self.parameters.to_chalk(db),
         }
     }
 
     fn from_chalk(
         db: &impl HirDatabase,
-        projection_ty: chalk_ir::ProjectionTy<TypeFamily>,
+        projection_ty: chalk_ir::AliasTy<TypeFamily>,
     ) -> ProjectionTy {
         ProjectionTy {
             associated_ty: from_chalk(db, projection_ty.associated_ty_id),
-            parameters: from_chalk(db, projection_ty.parameters),
+            parameters: from_chalk(db, projection_ty.substitution),
         }
     }
 }
@@ -369,10 +370,7 @@ impl ToChalk for super::ProjectionPredicate {
     type Chalk = chalk_ir::Normalize<TypeFamily>;
 
     fn to_chalk(self, db: &impl HirDatabase) -> chalk_ir::Normalize<TypeFamily> {
-        chalk_ir::Normalize {
-            projection: self.projection_ty.to_chalk(db),
-            ty: self.ty.to_chalk(db),
-        }
+        chalk_ir::Normalize { alias: self.projection_ty.to_chalk(db), ty: self.ty.to_chalk(db) }
     }
 
     fn from_chalk(_db: &impl HirDatabase, _normalize: chalk_ir::Normalize<TypeFamily>) -> Self {