From 3659502816134b45448799acf428055e40fdf4fc Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Fri, 27 Mar 2020 14:50:08 +0100 Subject: Upgrade Chalk --- crates/ra_hir_ty/src/traits.rs | 6 +- crates/ra_hir_ty/src/traits/chalk.rs | 123 ++++++++++++++++++++++++++++------- 2 files changed, 102 insertions(+), 27 deletions(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs index a1ca33c98..80eae4eca 100644 --- a/crates/ra_hir_ty/src/traits.rs +++ b/crates/ra_hir_ty/src/traits.rs @@ -153,7 +153,7 @@ pub(crate) fn trait_solve_query( } } - let canonical = goal.to_chalk(db).cast(); + let canonical = goal.to_chalk(db).cast(&Interner); // We currently don't deal with universes (I think / hope they're not yet // relevant for our use cases?) @@ -194,8 +194,8 @@ fn solution_from_chalk( let convert_subst = |subst: chalk_ir::Canonical>| { let value = subst .value - .into_iter() - .map(|p| match p.ty() { + .iter(&Interner) + .map(|p| match p.ty(&Interner) { Some(ty) => from_chalk(db, ty.clone()), None => unimplemented!(), }) diff --git a/crates/ra_hir_ty/src/traits/chalk.rs b/crates/ra_hir_ty/src/traits/chalk.rs index 943d5f125..ab4cb33b4 100644 --- a/crates/ra_hir_ty/src/traits/chalk.rs +++ b/crates/ra_hir_ty/src/traits/chalk.rs @@ -59,53 +59,126 @@ impl chalk_ir::interner::Interner for Interner { None } + fn debug_ty(_ty: &chalk_ir::Ty, _fmt: &mut fmt::Formatter<'_>) -> Option { + None + } + + fn debug_lifetime( + _lifetime: &chalk_ir::Lifetime, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + + fn debug_parameter( + _parameter: &Parameter, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + + fn debug_goal(_goal: &Goal, _fmt: &mut fmt::Formatter<'_>) -> Option { + None + } + + fn debug_goals( + _goals: &chalk_ir::Goals, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + + fn debug_program_clause_implication( + _pci: &chalk_ir::ProgramClauseImplication, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + + fn debug_application_ty( + _application_ty: &chalk_ir::ApplicationTy, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + + fn debug_substitution( + _substitution: &chalk_ir::Substitution, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + + fn debug_separator_trait_ref( + _separator_trait_ref: &chalk_ir::SeparatorTraitRef, + _fmt: &mut fmt::Formatter<'_>, + ) -> Option { + None + } + fn intern_ty(&self, ty: chalk_ir::TyData) -> Box> { Box::new(ty) } - fn ty_data(ty: &Box>) -> &chalk_ir::TyData { + fn ty_data<'a>(&self, ty: &'a Box>) -> &'a chalk_ir::TyData { ty } - fn intern_lifetime(lifetime: chalk_ir::LifetimeData) -> chalk_ir::LifetimeData { + fn intern_lifetime( + &self, + lifetime: chalk_ir::LifetimeData, + ) -> chalk_ir::LifetimeData { lifetime } - fn lifetime_data(lifetime: &chalk_ir::LifetimeData) -> &chalk_ir::LifetimeData { + fn lifetime_data<'a>( + &self, + lifetime: &'a chalk_ir::LifetimeData, + ) -> &'a chalk_ir::LifetimeData { lifetime } - fn intern_parameter(parameter: chalk_ir::ParameterData) -> chalk_ir::ParameterData { + fn intern_parameter( + &self, + parameter: chalk_ir::ParameterData, + ) -> chalk_ir::ParameterData { parameter } - fn parameter_data(parameter: &chalk_ir::ParameterData) -> &chalk_ir::ParameterData { + fn parameter_data<'a>( + &self, + parameter: &'a chalk_ir::ParameterData, + ) -> &'a chalk_ir::ParameterData { parameter } - fn intern_goal(goal: GoalData) -> Arc> { + fn intern_goal(&self, goal: GoalData) -> Arc> { Arc::new(goal) } - fn intern_goals(data: impl IntoIterator>) -> Self::InternedGoals { + fn intern_goals(&self, data: impl IntoIterator>) -> Self::InternedGoals { data.into_iter().collect() } - fn goal_data(goal: &Arc>) -> &GoalData { + fn goal_data<'a>(&self, goal: &'a Arc>) -> &'a GoalData { goal } - fn goals_data(goals: &Vec>) -> &[Goal] { + fn goals_data<'a>(&self, goals: &'a Vec>) -> &'a [Goal] { goals } fn intern_substitution( + &self, data: impl IntoIterator, E>>, ) -> Result>, E> { data.into_iter().collect() } - fn substitution_data(substitution: &Vec>) -> &[Parameter] { + fn substitution_data<'a>( + &self, + substitution: &'a Vec>, + ) -> &'a [Parameter] { substitution } } @@ -145,12 +218,14 @@ impl ToChalk for Ty { Ty::Apply(apply_ty) => { let name = apply_ty.ctor.to_chalk(db); let substitution = apply_ty.parameters.to_chalk(db); - chalk_ir::ApplicationTy { name, substitution }.cast().intern(&Interner) + chalk_ir::ApplicationTy { name, substitution }.cast(&Interner).intern(&Interner) } Ty::Projection(proj_ty) => { let associated_ty_id = proj_ty.associated_ty.to_chalk(db); let substitution = proj_ty.parameters.to_chalk(db); - chalk_ir::AliasTy { associated_ty_id, substitution }.cast().intern(&Interner) + chalk_ir::AliasTy { associated_ty_id, substitution } + .cast(&Interner) + .intern(&Interner) } Ty::Placeholder(id) => { let interned_id = db.intern_type_param_id(id); @@ -173,14 +248,14 @@ impl ToChalk for Ty { chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner) } Ty::Opaque(_) | Ty::Unknown => { - let substitution = chalk_ir::Substitution::empty(); + let substitution = chalk_ir::Substitution::empty(&Interner); let name = TypeName::Error; - chalk_ir::ApplicationTy { name, substitution }.cast().intern(&Interner) + chalk_ir::ApplicationTy { name, substitution }.cast(&Interner).intern(&Interner) } } } fn from_chalk(db: &dyn HirDatabase, chalk: chalk_ir::Ty) -> Self { - match chalk.data().clone() { + match chalk.data(&Interner).clone() { chalk_ir::TyData::Apply(apply_ty) => match apply_ty.name { TypeName::Error => Ty::Unknown, _ => { @@ -218,13 +293,13 @@ impl ToChalk for Substs { type Chalk = chalk_ir::Substitution; fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution { - chalk_ir::Substitution::from(self.iter().map(|ty| ty.clone().to_chalk(db))) + chalk_ir::Substitution::from(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db))) } fn from_chalk(db: &dyn HirDatabase, parameters: chalk_ir::Substitution) -> Substs { let tys = parameters - .into_iter() - .map(|p| match p.ty() { + .iter(&Interner) + .map(|p| match p.ty(&Interner) { Some(ty) => from_chalk(db, ty.clone()), None => unimplemented!(), }) @@ -400,8 +475,8 @@ impl ToChalk for Obligation { fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::DomainGoal { match self { - Obligation::Trait(tr) => tr.to_chalk(db).cast(), - Obligation::Projection(pr) => pr.to_chalk(db).cast(), + Obligation::Trait(tr) => tr.to_chalk(db).cast(&Interner), + Obligation::Projection(pr) => pr.to_chalk(db).cast(&Interner), } } @@ -438,8 +513,8 @@ impl ToChalk for Arc { continue; } let program_clause: chalk_ir::ProgramClause = - pred.clone().to_chalk(db).cast(); - clauses.push(program_clause.into_from_env_clause()); + pred.clone().to_chalk(db).cast(&Interner); + clauses.push(program_clause.into_from_env_clause(&Interner)); } chalk_ir::Environment::new().add_clauses(clauses) } @@ -578,9 +653,9 @@ impl<'a> chalk_solve::RustIrDatabase for ChalkContext<'a> { .map(|impl_| impl_.to_chalk(self.db)) .collect(); - let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref().clone()); + let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone()); let arg: Option = - parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref().clone())); + parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone())); builtin::get_builtin_impls(self.db, self.krate, &ty, &arg, trait_, |i| { result.push(i.to_chalk(self.db)) -- cgit v1.2.3 From 952714685a7c0e0a1c9970839ce307806adaa176 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 5 Apr 2020 18:24:18 +0200 Subject: 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. --- crates/ra_hir_ty/src/autoderef.rs | 19 +++--- crates/ra_hir_ty/src/display.rs | 2 +- crates/ra_hir_ty/src/infer/unify.rs | 28 ++++---- crates/ra_hir_ty/src/lib.rs | 103 +++++++++++++++++++++--------- crates/ra_hir_ty/src/lower.rs | 28 ++++---- crates/ra_hir_ty/src/method_resolution.rs | 16 +++-- crates/ra_hir_ty/src/traits.rs | 10 ++- crates/ra_hir_ty/src/traits/builtin.rs | 53 +++++++++------ crates/ra_hir_ty/src/traits/chalk.rs | 30 +++++---- crates/ra_hir_ty/src/utils.rs | 6 +- 10 files changed, 189 insertions(+), 106 deletions(-) (limited to 'crates/ra_hir_ty/src') diff --git a/crates/ra_hir_ty/src/autoderef.rs b/crates/ra_hir_ty/src/autoderef.rs index 53e81e85d..d91c21e24 100644 --- a/crates/ra_hir_ty/src/autoderef.rs +++ b/crates/ra_hir_ty/src/autoderef.rs @@ -14,7 +14,7 @@ use crate::{ db::HirDatabase, traits::{InEnvironment, Solution}, utils::generics, - Canonical, Substs, Ty, TypeWalk, + BoundVar, Canonical, DebruijnIndex, Substs, Ty, }; const AUTODEREF_RECURSION_LIMIT: usize = 10; @@ -61,14 +61,13 @@ fn deref_by_trait( return None; } - // FIXME make the Canonical handling nicer + // FIXME make the Canonical / bound var handling nicer - let parameters = Substs::build_for_generics(&generic_params) - .push(ty.value.value.clone().shift_bound_vars(1)) - .build(); + let parameters = + Substs::build_for_generics(&generic_params).push(ty.value.value.clone()).build(); let projection = super::traits::ProjectionPredicate { - ty: Ty::Bound(0), + ty: Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, ty.value.num_vars)), projection_ty: super::ProjectionTy { associated_ty: target, parameters }, }; @@ -93,12 +92,16 @@ fn deref_by_trait( // we have `impl Deref for Foo { Target = T }`, that should be // the case. for i in 1..vars.0.num_vars { - if vars.0.value[i] != Ty::Bound((i - 1) as u32) { + if vars.0.value[i - 1] != Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i - 1)) + { warn!("complex solution for derefing {:?}: {:?}, ignoring", ty.value, solution); return None; } } - Some(Canonical { value: vars.0.value[0].clone(), num_vars: vars.0.num_vars }) + Some(Canonical { + value: vars.0.value[vars.0.value.len() - 1].clone(), + num_vars: vars.0.num_vars, + }) } Solution::Ambig(_) => { info!("Ambiguous solution for derefing {:?}: {:?}", ty.value, solution); diff --git a/crates/ra_hir_ty/src/display.rs b/crates/ra_hir_ty/src/display.rs index 13ecd537a..1f5168ee3 100644 --- a/crates/ra_hir_ty/src/display.rs +++ b/crates/ra_hir_ty/src/display.rs @@ -303,7 +303,7 @@ impl HirDisplay for Ty { } } } - Ty::Bound(idx) => write!(f, "?{}", idx)?, + Ty::Bound(idx) => write!(f, "?{}.{}", idx.debruijn.depth(), idx.index)?, Ty::Dyn(predicates) | Ty::Opaque(predicates) => { match self { Ty::Dyn(_) => write!(f, "dyn ")?, diff --git a/crates/ra_hir_ty/src/infer/unify.rs b/crates/ra_hir_ty/src/infer/unify.rs index 0bf8fbd63..ac25f8a80 100644 --- a/crates/ra_hir_ty/src/infer/unify.rs +++ b/crates/ra_hir_ty/src/infer/unify.rs @@ -7,7 +7,9 @@ use ena::unify::{InPlaceUnificationTable, NoError, UnifyKey, UnifyValue}; use test_utils::tested_by; use super::{InferenceContext, Obligation}; -use crate::{Canonical, InEnvironment, InferTy, Substs, Ty, TypeCtor, TypeWalk}; +use crate::{ + BoundVar, Canonical, DebruijnIndex, InEnvironment, InferTy, Substs, Ty, TypeCtor, TypeWalk, +}; impl<'a> InferenceContext<'a> { pub(super) fn canonicalizer<'b>(&'b mut self) -> Canonicalizer<'a, 'b> @@ -47,7 +49,7 @@ where }) } - fn do_canonicalize(&mut self, t: T, binders: usize) -> T { + fn do_canonicalize(&mut self, t: T, binders: DebruijnIndex) -> T { t.fold_binders( &mut |ty, binders| match ty { Ty::Infer(tv) => { @@ -72,7 +74,7 @@ where InferTy::MaybeNeverTypeVar(_) => InferTy::MaybeNeverTypeVar(root), }; let position = self.add(free_var); - Ty::Bound((position + binders) as u32) + Ty::Bound(BoundVar::new(binders, position)) } } _ => ty, @@ -89,7 +91,7 @@ where } pub(crate) fn canonicalize_ty(mut self, ty: Ty) -> Canonicalized { - let result = self.do_canonicalize(ty, 0); + let result = self.do_canonicalize(ty, DebruijnIndex::INNERMOST); self.into_canonicalized(result) } @@ -98,8 +100,12 @@ where obligation: InEnvironment, ) -> Canonicalized> { let result = match obligation.value { - Obligation::Trait(tr) => Obligation::Trait(self.do_canonicalize(tr, 0)), - Obligation::Projection(pr) => Obligation::Projection(self.do_canonicalize(pr, 0)), + Obligation::Trait(tr) => { + Obligation::Trait(self.do_canonicalize(tr, DebruijnIndex::INNERMOST)) + } + Obligation::Projection(pr) => { + Obligation::Projection(self.do_canonicalize(pr, DebruijnIndex::INNERMOST)) + } }; self.into_canonicalized(InEnvironment { value: result, @@ -112,13 +118,13 @@ impl Canonicalized { pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty { ty.walk_mut_binders( &mut |ty, binders| { - if let &mut Ty::Bound(idx) = ty { - if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() { - *ty = Ty::Infer(self.free_vars[idx as usize - binders]); + if let &mut Ty::Bound(bound) = ty { + if bound.debruijn >= binders { + *ty = Ty::Infer(self.free_vars[bound.index]); } } }, - 0, + DebruijnIndex::INNERMOST, ); ty } @@ -150,7 +156,7 @@ pub fn unify(ty1: &Canonical, ty2: &Canonical) -> Option { // (kind of hacky) for (i, var) in vars.iter().enumerate() { if &*table.resolve_ty_shallow(var) == var { - table.unify(var, &Ty::Bound(i as u32)); + table.unify(var, &Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, i))); } } Some( diff --git a/crates/ra_hir_ty/src/lib.rs b/crates/ra_hir_ty/src/lib.rs index 6c5469ecd..a9022dee7 100644 --- a/crates/ra_hir_ty/src/lib.rs +++ b/crates/ra_hir_ty/src/lib.rs @@ -64,6 +64,8 @@ pub use lower::{ }; pub use traits::{InEnvironment, Obligation, ProjectionPredicate, TraitEnvironment}; +pub use chalk_ir::{BoundVar, DebruijnIndex}; + /// A type constructor or type name: this might be something like the primitive /// type `bool`, a struct like `Vec`, or things like function pointers or /// tuples. @@ -265,7 +267,11 @@ impl TypeWalk for ProjectionTy { self.parameters.walk(f); } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { self.parameters.walk_mut_binders(f, binders); } } @@ -299,7 +305,7 @@ pub enum Ty { /// parameters get turned into variables; during trait resolution, inference /// variables get turned into bound variables and back; and in `Dyn` the /// `Self` type is represented with a bound variable as well. - Bound(u32), + Bound(BoundVar), /// A type variable used during type checking. Infer(InferTy), @@ -337,7 +343,11 @@ impl TypeWalk for Substs { } } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { for t in make_mut_slice(&mut self.0) { t.walk_mut_binders(f, binders); } @@ -381,7 +391,13 @@ impl Substs { /// Return Substs that replace each parameter by a bound variable. pub(crate) fn bound_vars(generic_params: &Generics) -> Substs { - Substs(generic_params.iter().enumerate().map(|(idx, _)| Ty::Bound(idx as u32)).collect()) + Substs( + generic_params + .iter() + .enumerate() + .map(|(idx, _)| Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx))) + .collect(), + ) } pub fn build_for_def(db: &dyn HirDatabase, def: impl Into) -> SubstsBuilder { @@ -425,8 +441,8 @@ impl SubstsBuilder { self.param_count - self.vec.len() } - pub fn fill_with_bound_vars(self, starting_from: u32) -> Self { - self.fill((starting_from..).map(Ty::Bound)) + pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self { + self.fill((starting_from..).map(|idx| Ty::Bound(BoundVar::new(debruijn, idx)))) } pub fn fill_with_unknown(self) -> Self { @@ -507,7 +523,11 @@ impl TypeWalk for TraitRef { self.substs.walk(f); } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { self.substs.walk_mut_binders(f, binders); } } @@ -558,7 +578,11 @@ impl TypeWalk for GenericPredicate { } } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { match self { GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), GenericPredicate::Projection(projection_pred) => { @@ -616,7 +640,11 @@ impl TypeWalk for FnSig { } } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { for t in make_mut_slice(&mut self.params_and_return) { t.walk_mut_binders(f, binders); } @@ -755,7 +783,7 @@ impl Ty { pub trait TypeWalk { fn walk(&self, f: &mut impl FnMut(&Ty)); fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { - self.walk_mut_binders(&mut |ty, _binders| f(ty), 0); + self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST); } /// Walk the type, counting entered binders. /// @@ -767,9 +795,17 @@ pub trait TypeWalk { /// that. Currently, the only thing that introduces bound variables on our /// side are `Ty::Dyn` and `Ty::Opaque`, which each introduce a bound /// variable for the self type. - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize); - - fn fold_binders(mut self, f: &mut impl FnMut(Ty, usize) -> Ty, binders: usize) -> Self + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ); + + fn fold_binders( + mut self, + f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty, + binders: DebruijnIndex, + ) -> Self where Self: Sized, { @@ -795,40 +831,43 @@ pub trait TypeWalk { } /// Substitutes `Ty::Bound` vars with the given substitution. - fn subst_bound_vars(mut self, substs: &Substs) -> Self + fn subst_bound_vars(self, substs: &Substs) -> Self + where + Self: Sized, + { + self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST) + } + + /// Substitutes `Ty::Bound` vars with the given substitution. + fn subst_bound_vars_at_depth(mut self, substs: &Substs, depth: DebruijnIndex) -> Self where Self: Sized, { self.walk_mut_binders( &mut |ty, binders| { - if let &mut Ty::Bound(idx) = ty { - if idx as usize >= binders && (idx as usize - binders) < substs.len() { - *ty = substs.0[idx as usize - binders].clone(); - } else if idx as usize >= binders + substs.len() { - // shift free binders - *ty = Ty::Bound(idx - substs.len() as u32); + if let &mut Ty::Bound(bound) = ty { + if bound.debruijn >= binders { + *ty = substs.0[bound.index].clone(); } } }, - 0, + depth, ); self } - - /// Shifts up `Ty::Bound` vars by `n`. - fn shift_bound_vars(self, n: i32) -> Self + // /// Shifts up debruijn indices of `Ty::Bound` vars by `n`. + fn shift_bound_vars(self, n: DebruijnIndex) -> Self where Self: Sized, { self.fold_binders( &mut |ty, binders| match ty { - Ty::Bound(idx) if idx as usize >= binders => { - assert!(idx as i32 >= -n); - Ty::Bound((idx as i32 + n) as u32) + Ty::Bound(bound) if bound.debruijn >= binders => { + Ty::Bound(bound.shifted_in_from(n)) } ty => ty, }, - 0, + DebruijnIndex::INNERMOST, ) } } @@ -856,7 +895,11 @@ impl TypeWalk for Ty { f(self); } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { match self { Ty::Apply(a_ty) => { a_ty.parameters.walk_mut_binders(f, binders); @@ -866,7 +909,7 @@ impl TypeWalk for Ty { } Ty::Dyn(predicates) | Ty::Opaque(predicates) => { for p in make_mut_slice(predicates) { - p.walk_mut_binders(f, binders + 1); + p.walk_mut_binders(f, binders.shifted_in()); } } Ty::Placeholder { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {} diff --git a/crates/ra_hir_ty/src/lower.rs b/crates/ra_hir_ty/src/lower.rs index d7f250783..6c7bbc448 100644 --- a/crates/ra_hir_ty/src/lower.rs +++ b/crates/ra_hir_ty/src/lower.rs @@ -29,8 +29,8 @@ use crate::{ all_super_traits, associated_type_by_name_including_super_traits, generics, make_mut_slice, variant_data, }, - Binders, FnSig, GenericPredicate, PolyFnSig, ProjectionPredicate, ProjectionTy, Substs, - TraitEnvironment, TraitRef, Ty, TypeCtor, + Binders, BoundVar, DebruijnIndex, FnSig, GenericPredicate, PolyFnSig, ProjectionPredicate, + ProjectionTy, Substs, TraitEnvironment, TraitRef, Ty, TypeCtor, }; #[derive(Debug)] @@ -131,7 +131,7 @@ impl Ty { Ty::apply(TypeCtor::FnPtr { num_args: sig.len() as u16 - 1 }, sig) } TypeRef::DynTrait(bounds) => { - let self_ty = Ty::Bound(0); + let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)); let predicates = bounds .iter() .flat_map(|b| GenericPredicate::from_type_bound(ctx, b, self_ty.clone())) @@ -141,7 +141,7 @@ impl Ty { TypeRef::ImplTrait(bounds) => { match ctx.impl_trait_mode { ImplTraitLoweringMode::Opaque => { - let self_ty = Ty::Bound(0); + let self_ty = Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0)); let predicates = bounds .iter() .flat_map(|b| { @@ -177,12 +177,10 @@ impl Ty { } else { (0, 0, 0, 0) }; - Ty::Bound( - idx as u32 - + parent_params as u32 - + self_params as u32 - + list_params as u32, - ) + Ty::Bound(BoundVar::new( + DebruijnIndex::INNERMOST, + idx as usize + parent_params + self_params + list_params, + )) } ImplTraitLoweringMode::Disallowed => { // FIXME: report error @@ -249,7 +247,11 @@ impl Ty { let ty = match resolution { TypeNs::TraitId(trait_) => { // if this is a bare dyn Trait, we'll directly put the required ^0 for the self type in there - let self_ty = if remaining_segments.len() == 0 { Some(Ty::Bound(0)) } else { None }; + let self_ty = if remaining_segments.len() == 0 { + Some(Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, 0))) + } else { + None + }; let trait_ref = TraitRef::from_resolved_path(ctx, trait_, resolved_segment, self_ty); let ty = if remaining_segments.len() == 1 { @@ -289,7 +291,7 @@ impl Ty { TypeParamLoweringMode::Placeholder => Ty::Placeholder(param_id), TypeParamLoweringMode::Variable => { let idx = generics.param_idx(param_id).expect("matching generics"); - Ty::Bound(idx) + Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx)) } } } @@ -558,7 +560,7 @@ impl GenericPredicate { TypeParamLoweringMode::Placeholder => Ty::Placeholder(param_id), TypeParamLoweringMode::Variable => { let idx = generics.param_idx(param_id).expect("matching generics"); - Ty::Bound(idx) + Ty::Bound(BoundVar::new(DebruijnIndex::INNERMOST, idx)) } } } diff --git a/crates/ra_hir_ty/src/method_resolution.rs b/crates/ra_hir_ty/src/method_resolution.rs index 533c6ccfb..74a0bc7db 100644 --- a/crates/ra_hir_ty/src/method_resolution.rs +++ b/crates/ra_hir_ty/src/method_resolution.rs @@ -20,7 +20,8 @@ use crate::{ db::HirDatabase, primitive::{FloatBitness, Uncertain}, utils::all_super_traits, - ApplicationTy, Canonical, InEnvironment, TraitEnvironment, TraitRef, Ty, TypeCtor, TypeWalk, + ApplicationTy, Canonical, DebruijnIndex, InEnvironment, TraitEnvironment, TraitRef, Ty, + TypeCtor, TypeWalk, }; /// This is used as a key for indexing impls. @@ -507,8 +508,9 @@ pub(crate) fn inherent_impl_substs( ) -> Option { // we create a var for each type parameter of the impl; we need to keep in // mind here that `self_ty` might have vars of its own - let vars = - Substs::build_for_def(db, impl_id).fill_with_bound_vars(self_ty.num_vars as u32).build(); + let vars = Substs::build_for_def(db, impl_id) + .fill_with_bound_vars(DebruijnIndex::INNERMOST, self_ty.num_vars) + .build(); let self_ty_with_vars = db.impl_self_ty(impl_id).subst(&vars); let self_ty_with_vars = Canonical { num_vars: vars.len() + self_ty.num_vars, value: self_ty_with_vars }; @@ -526,8 +528,8 @@ pub(crate) fn inherent_impl_substs( fn fallback_bound_vars(s: Substs, num_vars_to_keep: usize) -> Substs { s.fold_binders( &mut |ty, binders| { - if let Ty::Bound(idx) = &ty { - if *idx >= binders as u32 { + if let Ty::Bound(bound) = &ty { + if bound.index >= num_vars_to_keep && bound.debruijn >= binders { Ty::Unknown } else { ty @@ -536,7 +538,7 @@ fn fallback_bound_vars(s: Substs, num_vars_to_keep: usize) -> Substs { ty } }, - num_vars_to_keep, + DebruijnIndex::INNERMOST, ) } @@ -586,7 +588,7 @@ fn generic_implements_goal( let num_vars = self_ty.num_vars; let substs = super::Substs::build_for_def(db, trait_) .push(self_ty.value) - .fill_with_bound_vars(num_vars as u32) + .fill_with_bound_vars(DebruijnIndex::INNERMOST, num_vars) .build(); let num_vars = substs.len() - 1 + self_ty.num_vars; let trait_ref = TraitRef { trait_, substs }; diff --git a/crates/ra_hir_ty/src/traits.rs b/crates/ra_hir_ty/src/traits.rs index 80eae4eca..07854a062 100644 --- a/crates/ra_hir_ty/src/traits.rs +++ b/crates/ra_hir_ty/src/traits.rs @@ -7,7 +7,7 @@ use ra_db::{impl_intern_key, salsa, CrateId}; use ra_prof::profile; use rustc_hash::FxHashSet; -use crate::db::HirDatabase; +use crate::{db::HirDatabase, DebruijnIndex}; use super::{Canonical, GenericPredicate, HirDisplay, ProjectionTy, TraitRef, Ty, TypeWalk}; @@ -128,7 +128,11 @@ impl TypeWalk for ProjectionPredicate { self.ty.walk(f); } - fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { self.projection_ty.walk_mut_binders(f, binders); self.ty.walk_mut_binders(f, binders); } @@ -144,7 +148,7 @@ pub(crate) fn trait_solve_query( Obligation::Trait(it) => db.trait_data(it.trait_).name.to_string(), Obligation::Projection(_) => "projection".to_string(), }); - log::debug!("trait_solve_query({})", goal.value.value.display(db)); + eprintln!("trait_solve_query({})", goal.value.value.display(db)); if let Obligation::Projection(pred) = &goal.value.value { if let Ty::Bound(_) = &pred.projection_ty.parameters[0] { 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(¤t_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) } - 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 { 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) } diff --git a/crates/ra_hir_ty/src/utils.rs b/crates/ra_hir_ty/src/utils.rs index b40d4eb73..1e5022fa4 100644 --- a/crates/ra_hir_ty/src/utils.rs +++ b/crates/ra_hir_ty/src/utils.rs @@ -201,11 +201,11 @@ impl Generics { (parent, self_params, list_params, impl_trait_params) } - pub(crate) fn param_idx(&self, param: TypeParamId) -> Option { + pub(crate) fn param_idx(&self, param: TypeParamId) -> Option { Some(self.find_param(param)?.0) } - fn find_param(&self, param: TypeParamId) -> Option<(u32, &TypeParamData)> { + fn find_param(&self, param: TypeParamId) -> Option<(usize, &TypeParamData)> { if param.parent == self.def { let (idx, (_local_id, data)) = self .params @@ -215,7 +215,7 @@ impl Generics { .find(|(_, (idx, _))| *idx == param.local_id) .unwrap(); let (_total, parent_len, _child) = self.len_split(); - Some(((parent_len + idx) as u32, data)) + Some((parent_len + idx, data)) } else { self.parent_generics.as_ref().and_then(|g| g.find_param(param)) } -- cgit v1.2.3