From 351c29d859d74f7a61e654bdbcad634bfb136225 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sat, 16 Nov 2019 12:53:13 +0100 Subject: Fix handling of the binders in dyn/impl Trait We need to be more careful now when substituting bound variables (previously, we didn't have anything that used bound variables except Chalk, so it was not a problem). This is obviously quite ad-hoc; Chalk has more infrastructure for handling this in a principled way, which we maybe should adopt. --- crates/ra_hir/src/ty.rs | 89 ++++++++++++++++++++++++------------- crates/ra_hir/src/ty/infer/unify.rs | 22 ++++----- crates/ra_hir/src/ty/tests.rs | 43 ++++++++++++++++++ crates/ra_hir/src/ty/traits.rs | 7 +-- 4 files changed, 116 insertions(+), 45 deletions(-) (limited to 'crates/ra_hir/src') diff --git a/crates/ra_hir/src/ty.rs b/crates/ra_hir/src/ty.rs index ff6030ac4..a54135188 100644 --- a/crates/ra_hir/src/ty.rs +++ b/crates/ra_hir/src/ty.rs @@ -224,8 +224,8 @@ impl TypeWalk for ProjectionTy { self.parameters.walk(f); } - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { - self.parameters.walk_mut(f); + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + self.parameters.walk_mut_binders(f, binders); } } @@ -291,6 +291,20 @@ pub enum Ty { #[derive(Clone, PartialEq, Eq, Debug, Hash)] pub struct Substs(Arc<[Ty]>); +impl TypeWalk for Substs { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self.0.iter() { + t.walk(f); + } + } + + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + for t in make_mut_slice(&mut self.0) { + t.walk_mut_binders(f, binders); + } + } +} + impl Substs { pub fn empty() -> Substs { Substs(Arc::new([])) @@ -304,18 +318,6 @@ impl Substs { Substs(self.0[..std::cmp::min(self.0.len(), n)].into()) } - pub fn walk(&self, f: &mut impl FnMut(&Ty)) { - for t in self.0.iter() { - t.walk(f); - } - } - - pub fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { - for t in make_mut_slice(&mut self.0) { - t.walk_mut(f); - } - } - pub fn as_single(&self) -> &Ty { if self.0.len() != 1 { panic!("expected substs of len 1, got {:?}", self); @@ -440,8 +442,8 @@ impl TypeWalk for TraitRef { self.substs.walk(f); } - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { - self.substs.walk_mut(f); + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + self.substs.walk_mut_binders(f, binders); } } @@ -491,10 +493,12 @@ impl TypeWalk for GenericPredicate { } } - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { match self { - GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut(f), - GenericPredicate::Projection(projection_pred) => projection_pred.walk_mut(f), + GenericPredicate::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), + GenericPredicate::Projection(projection_pred) => { + projection_pred.walk_mut_binders(f, binders) + } GenericPredicate::Error => {} } } @@ -544,9 +548,9 @@ impl TypeWalk for FnSig { } } - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { for t in make_mut_slice(&mut self.params_and_return) { - t.walk_mut(f); + t.walk_mut_binders(f, binders); } } } @@ -671,7 +675,20 @@ impl Ty { /// types, similar to Chalk's `Fold` trait. pub trait TypeWalk { fn walk(&self, f: &mut impl FnMut(&Ty)); - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)); + fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { + self.walk_mut_binders(&mut |ty, _binders| f(ty), 0); + } + /// Walk the type, counting entered binders. + /// + /// `Ty::Bound` variables use DeBruijn indexing, which means that 0 refers + /// to the innermost binder, 1 to the next, etc.. So when we want to + /// substitute a certain bound variable, we can't just walk the whole type + /// and blindly replace each instance of a certain index; when we 'enter' + /// things that introduce new bound variables, we have to keep track of + /// 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(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self where @@ -700,14 +717,22 @@ pub trait TypeWalk { } /// Substitutes `Ty::Bound` vars (as opposed to type parameters). - fn subst_bound_vars(self, substs: &Substs) -> Self + fn subst_bound_vars(mut self, substs: &Substs) -> Self where Self: Sized, { - self.fold(&mut |ty| match ty { - Ty::Bound(idx) => substs.get(idx as usize).cloned().unwrap_or_else(|| Ty::Bound(idx)), - ty => ty, - }) + self.walk_mut_binders( + &mut |ty, binders| match ty { + &mut Ty::Bound(idx) => { + if idx as usize >= binders && (idx as usize - binders) < substs.len() { + *ty = substs.0[idx as usize - binders].clone(); + } + } + _ => {} + }, + 0, + ); + self } /// Shifts up `Ty::Bound` vars by `n`. @@ -748,22 +773,22 @@ impl TypeWalk for Ty { f(self); } - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { match self { Ty::Apply(a_ty) => { - a_ty.parameters.walk_mut(f); + a_ty.parameters.walk_mut_binders(f, binders); } Ty::Projection(p_ty) => { - p_ty.parameters.walk_mut(f); + p_ty.parameters.walk_mut_binders(f, binders); } Ty::Dyn(predicates) | Ty::Opaque(predicates) => { for p in make_mut_slice(predicates) { - p.walk_mut(f); + p.walk_mut_binders(f, binders + 1); } } Ty::Param { .. } | Ty::Bound(_) | Ty::Infer(_) | Ty::Unknown => {} } - f(self); + f(self, binders); } } diff --git a/crates/ra_hir/src/ty/infer/unify.rs b/crates/ra_hir/src/ty/infer/unify.rs index ca33cc7f8..64d9394cf 100644 --- a/crates/ra_hir/src/ty/infer/unify.rs +++ b/crates/ra_hir/src/ty/infer/unify.rs @@ -134,17 +134,19 @@ where } impl Canonicalized { - pub fn decanonicalize_ty(&self, ty: Ty) -> Ty { - ty.fold(&mut |ty| match ty { - Ty::Bound(idx) => { - if (idx as usize) < self.free_vars.len() { - Ty::Infer(self.free_vars[idx as usize]) - } else { - Ty::Bound(idx) + pub fn decanonicalize_ty(&self, mut ty: Ty) -> Ty { + ty.walk_mut_binders( + &mut |ty, binders| match ty { + &mut Ty::Bound(idx) => { + if idx as usize >= binders && (idx as usize - binders) < self.free_vars.len() { + *ty = Ty::Infer(self.free_vars[idx as usize - binders]); + } } - } - ty => ty, - }) + _ => {} + }, + 0, + ); + ty } pub fn apply_solution( diff --git a/crates/ra_hir/src/ty/tests.rs b/crates/ra_hir/src/ty/tests.rs index 838cb4d23..ca1693679 100644 --- a/crates/ra_hir/src/ty/tests.rs +++ b/crates/ra_hir/src/ty/tests.rs @@ -4184,6 +4184,49 @@ fn test>(x: T, y: impl Trait) { ); } +#[test] +fn impl_trait_assoc_binding_projection_bug() { + let (db, pos) = TestDB::with_position( + r#" +//- /main.rs crate:main deps:std +pub trait Language { + type Kind; +} +pub enum RustLanguage {} +impl Language for RustLanguage { + type Kind = SyntaxKind; +} +struct SyntaxNode {} +fn foo() -> impl Iterator> {} + +trait Clone { + fn clone(&self) -> Self; +} + +fn api_walkthrough() { + for node in foo() { + node.clone()<|>; + } +} + +//- /std.rs crate:std +#[prelude_import] use iter::*; +mod iter { + trait IntoIterator { + type Item; + } + trait Iterator { + type Item; + } + impl IntoIterator for T { + type Item = ::Item; + } +} +"#, + ); + assert_eq!("{unknown}", type_at_pos(&db, pos)); +} + #[test] fn projection_eq_within_chalk() { // std::env::set_var("CHALK_DEBUG", "1"); diff --git a/crates/ra_hir/src/ty/traits.rs b/crates/ra_hir/src/ty/traits.rs index 771525deb..99dbab99e 100644 --- a/crates/ra_hir/src/ty/traits.rs +++ b/crates/ra_hir/src/ty/traits.rs @@ -165,9 +165,9 @@ impl TypeWalk for ProjectionPredicate { self.ty.walk(f); } - fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) { - self.projection_ty.walk_mut(f); - self.ty.walk_mut(f); + fn walk_mut_binders(&mut self, f: &mut impl FnMut(&mut Ty, usize), binders: usize) { + self.projection_ty.walk_mut_binders(f, binders); + self.ty.walk_mut_binders(f, binders); } } @@ -188,6 +188,7 @@ pub(crate) fn trait_solve_query( } let canonical = goal.to_chalk(db).cast(); + // We currently don't deal with universes (I think / hope they're not yet // relevant for our use cases?) let u_canonical = chalk_ir::UCanonical { canonical, universes: 1 }; -- cgit v1.2.3