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. --- Cargo.lock | 12 ++-- crates/ra_hir_ty/Cargo.toml | 6 +- 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 +- 12 files changed, 198 insertions(+), 115 deletions(-) diff --git a/Cargo.lock b/Cargo.lock index c46bf9448..2ea0c5cd1 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -114,7 +114,7 @@ checksum = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822" [[package]] name = "chalk-derive" version = "0.1.0" -source = "git+https://github.com/rust-lang/chalk.git?rev=d383af7333cc6014e9d9e3e77668b5d5b0a5b40e#d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" +source = "git+https://github.com/rust-lang/chalk.git?rev=039fc904a05f8cb3d0c682c9a57a63dda7a35356#039fc904a05f8cb3d0c682c9a57a63dda7a35356" dependencies = [ "proc-macro2", "quote", @@ -124,7 +124,7 @@ dependencies = [ [[package]] name = "chalk-engine" version = "0.9.0" -source = "git+https://github.com/rust-lang/chalk.git?rev=d383af7333cc6014e9d9e3e77668b5d5b0a5b40e#d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" +source = "git+https://github.com/rust-lang/chalk.git?rev=039fc904a05f8cb3d0c682c9a57a63dda7a35356#039fc904a05f8cb3d0c682c9a57a63dda7a35356" dependencies = [ "chalk-macros", "rustc-hash", @@ -133,7 +133,7 @@ dependencies = [ [[package]] name = "chalk-ir" version = "0.1.0" -source = "git+https://github.com/rust-lang/chalk.git?rev=d383af7333cc6014e9d9e3e77668b5d5b0a5b40e#d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" +source = "git+https://github.com/rust-lang/chalk.git?rev=039fc904a05f8cb3d0c682c9a57a63dda7a35356#039fc904a05f8cb3d0c682c9a57a63dda7a35356" dependencies = [ "chalk-derive", "chalk-engine", @@ -143,7 +143,7 @@ dependencies = [ [[package]] name = "chalk-macros" version = "0.1.1" -source = "git+https://github.com/rust-lang/chalk.git?rev=d383af7333cc6014e9d9e3e77668b5d5b0a5b40e#d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" +source = "git+https://github.com/rust-lang/chalk.git?rev=039fc904a05f8cb3d0c682c9a57a63dda7a35356#039fc904a05f8cb3d0c682c9a57a63dda7a35356" dependencies = [ "lazy_static", ] @@ -151,7 +151,7 @@ dependencies = [ [[package]] name = "chalk-rust-ir" version = "0.1.0" -source = "git+https://github.com/rust-lang/chalk.git?rev=d383af7333cc6014e9d9e3e77668b5d5b0a5b40e#d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" +source = "git+https://github.com/rust-lang/chalk.git?rev=039fc904a05f8cb3d0c682c9a57a63dda7a35356#039fc904a05f8cb3d0c682c9a57a63dda7a35356" dependencies = [ "chalk-derive", "chalk-engine", @@ -162,7 +162,7 @@ dependencies = [ [[package]] name = "chalk-solve" version = "0.1.0" -source = "git+https://github.com/rust-lang/chalk.git?rev=d383af7333cc6014e9d9e3e77668b5d5b0a5b40e#d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" +source = "git+https://github.com/rust-lang/chalk.git?rev=039fc904a05f8cb3d0c682c9a57a63dda7a35356#039fc904a05f8cb3d0c682c9a57a63dda7a35356" dependencies = [ "chalk-derive", "chalk-engine", diff --git a/crates/ra_hir_ty/Cargo.toml b/crates/ra_hir_ty/Cargo.toml index 2cbab800d..45be08430 100644 --- a/crates/ra_hir_ty/Cargo.toml +++ b/crates/ra_hir_ty/Cargo.toml @@ -23,9 +23,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 = "d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" } -chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" } -chalk-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "d383af7333cc6014e9d9e3e77668b5d5b0a5b40e" } +chalk-solve = { git = "https://github.com/rust-lang/chalk.git", rev = "039fc904a05f8cb3d0c682c9a57a63dda7a35356" } +chalk-rust-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "039fc904a05f8cb3d0c682c9a57a63dda7a35356" } +chalk-ir = { git = "https://github.com/rust-lang/chalk.git", rev = "039fc904a05f8cb3d0c682c9a57a63dda7a35356" } [dev-dependencies] insta = "0.15.0" 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