Upgrade Chalk again

The big change here is counting binders, not
variables (https://github.com/rust-lang/chalk/pull/360). We have to adapt to the
same scheme for our `Ty::Bound`. It's mostly fine though, even makes some things
more clear.

2 files changed, 53 insertions, 30 deletions

diff --git a/crates/ra_hir_ty/src/traits/builtin.rs b/crates/ra_hir_ty/src/traits/builtin.rs
index 73e3c5c78..ccab246bf 100644
--- a/crates/ra_hir_ty/src/traits/builtin.rs
+++ b/crates/ra_hir_ty/src/traits/builtin.rs
@@ -8,7 +8,8 @@ use super::{AssocTyValue, Impl, UnsizeToSuperTraitObjectData};
 use crate::{
     db::HirDatabase,
     utils::{all_super_traits, generics},
-    ApplicationTy, Binders, GenericPredicate, Substs, TraitRef, Ty, TypeCtor,
+    ApplicationTy, Binders, BoundVar, DebruijnIndex, GenericPredicate, Substs, TraitRef, Ty,
+    TypeCtor, TypeWalk,
 };
 
 pub(super) struct BuiltinImplData {
@@ -164,11 +165,15 @@ fn closure_fn_trait_impl_datum(
 
     let arg_ty = Ty::apply(
         TypeCtor::Tuple { cardinality: num_args },
-        Substs::builder(num_args as usize).fill_with_bound_vars(0).build(),
+        Substs::builder(num_args as usize)
+            .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+            .build(),
     );
     let sig_ty = Ty::apply(
         TypeCtor::FnPtr { num_args },
-        Substs::builder(num_args as usize + 1).fill_with_bound_vars(0).build(),
+        Substs::builder(num_args as usize + 1)
+            .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+            .build(),
     );
 
     let self_ty = Ty::apply_one(TypeCtor::Closure { def: data.def, expr: data.expr }, sig_ty);
@@ -203,7 +208,7 @@ fn closure_fn_trait_output_assoc_ty_value(
         }
     };
 
-    let output_ty = Ty::Bound(num_args.into());
+    let output_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, num_args.into()));
 
     let fn_once_trait =
         get_fn_trait(db, krate, super::FnTrait::FnOnce).expect("assoc ty value should not exist");
@@ -241,7 +246,7 @@ fn array_unsize_impl_datum(db: &dyn HirDatabase, krate: CrateId) -> BuiltinImplD
         // the existence of the Unsize trait has been checked before
         .expect("Unsize trait missing");
 
-    let var = Ty::Bound(0);
+    let var = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
     let substs = Substs::builder(2)
         .push(Ty::apply_one(TypeCtor::Array, var.clone()))
         .push(Ty::apply_one(TypeCtor::Slice, var))
@@ -270,19 +275,18 @@ fn trait_object_unsize_impl_datum(
         // the existence of the Unsize trait has been checked before
         .expect("Unsize trait missing");
 
-    let self_ty = Ty::Bound(0);
+    let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0));
 
     let target_substs = Substs::build_for_def(db, trait_)
-        .push(Ty::Bound(0))
-        // starting from ^2 because we want to start with ^1 outside of the
-        // `dyn`, which is ^2 inside
-        .fill_with_bound_vars(2)
+        .push(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
+        .fill_with_bound_vars(DebruijnIndex::ONE, 1)
         .build();
     let num_vars = target_substs.len();
     let target_trait_ref = TraitRef { trait_, substs: target_substs };
     let target_bounds = vec![GenericPredicate::Implemented(target_trait_ref)];
 
-    let self_substs = Substs::build_for_def(db, trait_).fill_with_bound_vars(0).build();
+    let self_substs =
+        Substs::build_for_def(db, trait_).fill_with_bound_vars(DebruijnIndex::INNERMOST, 0).build();
     let self_trait_ref = TraitRef { trait_, substs: self_substs };
     let where_clauses = vec![GenericPredicate::Implemented(self_trait_ref)];
 
@@ -305,24 +309,26 @@ fn super_trait_object_unsize_impl_datum(
         // the existence of the Unsize trait has been checked before
         .expect("Unsize trait missing");
 
-    let self_substs = Substs::build_for_def(db, data.trait_).fill_with_bound_vars(0).build();
+    let self_substs = Substs::build_for_def(db, data.trait_)
+        .fill_with_bound_vars(DebruijnIndex::INNERMOST, 0)
+        .build();
+    let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() };
 
     let num_vars = self_substs.len() - 1;
 
-    let self_trait_ref = TraitRef { trait_: data.trait_, substs: self_substs.clone() };
-    let self_bounds = vec![GenericPredicate::Implemented(self_trait_ref.clone())];
-
     // we need to go from our trait to the super trait, substituting type parameters
     let path = crate::utils::find_super_trait_path(db.upcast(), data.trait_, data.super_trait);
 
-    let mut current_trait_ref = self_trait_ref;
+    let mut current_trait_ref = self_trait_ref.clone();
     for t in path.into_iter().skip(1) {
         let bounds = db.generic_predicates(current_trait_ref.trait_.into());
         let super_trait_ref = bounds
             .iter()
             .find_map(|b| match &b.value {
                 GenericPredicate::Implemented(tr)
-                    if tr.trait_ == t && tr.substs[0] == Ty::Bound(0) =>
+                    if tr.trait_ == t
+                        && tr.substs[0]
+                            == Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)) =>
                 {
                     Some(Binders { value: tr, num_binders: b.num_binders })
                 }
@@ -332,7 +338,18 @@ fn super_trait_object_unsize_impl_datum(
         current_trait_ref = super_trait_ref.cloned().subst(&current_trait_ref.substs);
     }
 
-    let super_bounds = vec![GenericPredicate::Implemented(current_trait_ref)];
+    // We need to renumber the variables a bit now: from ^0.0, ^0.1, ^0.2, ...
+    // to ^0.0, ^1.0, ^1.1. The reason for this is that the first variable comes
+    // from the dyn Trait binder, while the other variables come from the impl.
+    let new_substs = Substs::builder(num_vars + 1)
+        .push(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)))
+        .fill_with_bound_vars(DebruijnIndex::ONE, 0)
+        .build();
+
+    let self_bounds =
+        vec![GenericPredicate::Implemented(self_trait_ref.subst_bound_vars(&new_substs))];
+    let super_bounds =
+        vec![GenericPredicate::Implemented(current_trait_ref.subst_bound_vars(&new_substs))];
 
     let substs = Substs::builder(2)
         .push(Ty::Dyn(self_bounds.into()))
diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs
index ab4cb33b4..53ce362ea 100644
--- a/crates/ra_hir_ty/src/traits/chalk.rs
+++ b/crates/ra_hir_ty/src/traits/chalk.rs
@@ -3,7 +3,10 @@ use std::{fmt, sync::Arc};
 
 use log::debug;
 
-use chalk_ir::{cast::Cast, Goal, GoalData, Parameter, PlaceholderIndex, TypeName, UniverseIndex};
+use chalk_ir::{
+    cast::Cast, fold::shift::Shift, Goal, GoalData, Parameter, PlaceholderIndex, TypeName,
+    UniverseIndex,
+};
 
 use hir_def::{AssocContainerId, AssocItemId, GenericDefId, HasModule, Lookup, TypeAliasId};
 use ra_db::{
@@ -235,7 +238,7 @@ impl ToChalk for Ty {
                 }
                 .to_ty::<Interner>(&Interner)
             }
-            Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx as usize).intern(&Interner),
+            Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx).intern(&Interner),
             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
             Ty::Dyn(predicates) => {
                 let where_clauses = predicates
@@ -277,7 +280,7 @@ impl ToChalk for Ty {
                 Ty::Projection(ProjectionTy { associated_ty, parameters })
             }
             chalk_ir::TyData::Function(_) => unimplemented!(),
-            chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx as u32),
+            chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx),
             chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
             chalk_ir::TyData::Dyn(where_clauses) => {
                 assert_eq!(where_clauses.bounds.binders.len(), 1);
@@ -407,15 +410,15 @@ impl ToChalk for GenericPredicate {
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::QuantifiedWhereClause<Interner> {
         match self {
             GenericPredicate::Implemented(trait_ref) => {
-                make_binders(chalk_ir::WhereClause::Implemented(trait_ref.to_chalk(db)), 0)
+                let chalk_trait_ref = trait_ref.to_chalk(db);
+                let chalk_trait_ref = chalk_trait_ref.shifted_in(&Interner);
+                make_binders(chalk_ir::WhereClause::Implemented(chalk_trait_ref), 0)
+            }
+            GenericPredicate::Projection(projection_pred) => {
+                let ty = projection_pred.ty.to_chalk(db).shifted_in(&Interner);
+                let alias = projection_pred.projection_ty.to_chalk(db).shifted_in(&Interner);
+                make_binders(chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq { alias, ty }), 0)
             }
-            GenericPredicate::Projection(projection_pred) => make_binders(
-                chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq {
-                    alias: projection_pred.projection_ty.to_chalk(db),
-                    ty: projection_pred.ty.to_chalk(db),
-                }),
-                0,
-            ),
             GenericPredicate::Error => panic!("tried passing GenericPredicate::Error to Chalk"),
         }
     }
@@ -579,7 +582,8 @@ impl ToChalk for builtin::BuiltinImplAssocTyValueData {
     type Chalk = AssociatedTyValue;
 
     fn to_chalk(self, db: &dyn HirDatabase) -> AssociatedTyValue {
-        let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty: self.value.to_chalk(db) };
+        let ty = self.value.to_chalk(db);
+        let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty };
 
         chalk_rust_ir::AssociatedTyValue {
             associated_ty_id: self.assoc_ty_id.to_chalk(db),
@@ -738,11 +742,13 @@ pub(crate) fn trait_datum_query(
     let associated_ty_ids =
         trait_data.associated_types().map(|type_alias| type_alias.to_chalk(db)).collect();
     let trait_datum_bound = chalk_rust_ir::TraitDatumBound { where_clauses };
+    let well_known = None; // FIXME set this (depending on lang items)
     let trait_datum = TraitDatum {
         id: trait_id,
         binders: make_binders(trait_datum_bound, bound_vars.len()),
         flags,
         associated_ty_ids,
+        well_known,
     };
     Arc::new(trait_datum)
 }