From 508a1ecad3cf9c9f01022b3e95f9d6a7ad7a4cd5 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 4 Apr 2021 20:22:00 +0200 Subject: Move things in hir_ty into submodules - all the types that will be replaced by Chalk go to `types` - `TypeWalk` impls go to `walk` --- crates/hir_ty/src/walk.rs | 359 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 359 insertions(+) create mode 100644 crates/hir_ty/src/walk.rs (limited to 'crates/hir_ty/src/walk.rs') diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs new file mode 100644 index 000000000..fec5c2f42 --- /dev/null +++ b/crates/hir_ty/src/walk.rs @@ -0,0 +1,359 @@ +//! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and +//! `Visit`). + +use std::mem; + +use chalk_ir::DebruijnIndex; + +use crate::{ + utils::make_mut_slice, AliasTy, Binders, CallableSig, GenericArg, GenericArgData, Interner, + OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, +}; + +/// This allows walking structures that contain types to do something with those +/// 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)) { + self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST); + } + /// Walk the type, counting entered binders. + /// + /// `TyKind::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 `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound + /// variable for the self type. + 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, + { + self.walk_mut_binders( + &mut |ty_mut, binders| { + let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); + *ty_mut = f(ty, binders); + }, + binders, + ); + self + } + + fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self + where + Self: Sized, + { + self.walk_mut(&mut |ty_mut| { + let ty = mem::replace(ty_mut, TyKind::Unknown.intern(&Interner)); + *ty_mut = f(ty); + }); + self + } + + /// Substitutes `TyKind::Bound` vars with the given substitution. + fn subst_bound_vars(self, substs: &Substitution) -> Self + where + Self: Sized, + { + self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST) + } + + /// Substitutes `TyKind::Bound` vars with the given substitution. + fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self + where + Self: Sized, + { + self.walk_mut_binders( + &mut |ty, binders| { + if let &mut TyKind::BoundVar(bound) = ty.interned_mut() { + if bound.debruijn >= binders { + *ty = substs.interned()[bound.index] + .assert_ty_ref(&Interner) + .clone() + .shift_bound_vars(binders); + } + } + }, + depth, + ); + self + } + + /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`. + fn shift_bound_vars(self, n: DebruijnIndex) -> Self + where + Self: Sized, + { + self.fold_binders( + &mut |ty, binders| match ty.kind(&Interner) { + TyKind::BoundVar(bound) if bound.debruijn >= binders => { + TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner) + } + _ => ty, + }, + DebruijnIndex::INNERMOST, + ) + } + + /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`. + fn shift_bound_vars_out(self, n: DebruijnIndex) -> Self + where + Self: Sized + std::fmt::Debug, + { + self.fold_binders( + &mut |ty, binders| match ty.kind(&Interner) { + TyKind::BoundVar(bound) if bound.debruijn >= binders => { + TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone())) + .intern(&Interner) + } + _ => ty, + }, + DebruijnIndex::INNERMOST, + ) + } +} + +impl TypeWalk for Ty { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match self.kind(&Interner) { + TyKind::Alias(AliasTy::Projection(p_ty)) => { + for t in p_ty.substitution.iter(&Interner) { + t.walk(f); + } + } + TyKind::Alias(AliasTy::Opaque(o_ty)) => { + for t in o_ty.substitution.iter(&Interner) { + t.walk(f); + } + } + TyKind::Dyn(dyn_ty) => { + for p in dyn_ty.bounds.value.interned().iter() { + p.walk(f); + } + } + TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { + ty.walk(f); + } + _ => { + if let Some(substs) = self.substs() { + for t in substs.iter(&Interner) { + t.walk(f); + } + } + } + } + f(self); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self.interned_mut() { + TyKind::Alias(AliasTy::Projection(p_ty)) => { + p_ty.substitution.walk_mut_binders(f, binders); + } + TyKind::Dyn(dyn_ty) => { + for p in make_mut_slice(dyn_ty.bounds.value.interned_mut()) { + p.walk_mut_binders(f, binders.shifted_in()); + } + } + TyKind::Alias(AliasTy::Opaque(o_ty)) => { + o_ty.substitution.walk_mut_binders(f, binders); + } + TyKind::Slice(ty) | TyKind::Array(ty) | TyKind::Ref(_, ty) | TyKind::Raw(_, ty) => { + ty.walk_mut_binders(f, binders); + } + _ => { + if let Some(substs) = self.substs_mut() { + substs.walk_mut_binders(f, binders); + } + } + } + f(self, binders); + } +} + +impl TypeWalk for Vec { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self { + t.walk(f); + } + } + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + for t in self { + t.walk_mut_binders(f, binders); + } + } +} + +impl TypeWalk for OpaqueTy { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.substitution.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.substitution.walk_mut_binders(f, binders); + } +} + +impl TypeWalk for ProjectionTy { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.substitution.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.substitution.walk_mut_binders(f, binders); + } +} + +impl TypeWalk for AliasTy { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match self { + AliasTy::Projection(it) => it.walk(f), + AliasTy::Opaque(it) => it.walk(f), + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self { + AliasTy::Projection(it) => it.walk_mut_binders(f, binders), + AliasTy::Opaque(it) => it.walk_mut_binders(f, binders), + } + } +} + +impl TypeWalk for GenericArg { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match &self.interned() { + GenericArgData::Ty(ty) => { + ty.walk(f); + } + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self.interned_mut() { + GenericArgData::Ty(ty) => { + ty.walk_mut_binders(f, binders); + } + } + } +} + +impl TypeWalk for Substitution { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self.iter(&Interner) { + t.walk(f); + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + for t in self.interned_mut() { + t.walk_mut_binders(f, binders); + } + } +} + +impl TypeWalk for Binders { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.value.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.value.walk_mut_binders(f, binders.shifted_in()) + } +} + +impl TypeWalk for TraitRef { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.substitution.walk(f); + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.substitution.walk_mut_binders(f, binders); + } +} + +impl TypeWalk for WhereClause { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + match self { + WhereClause::Implemented(trait_ref) => trait_ref.walk(f), + WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + match self { + WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders), + WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders), + } + } +} + +impl TypeWalk for CallableSig { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + for t in self.params_and_return.iter() { + t.walk(f); + } + } + + 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); + } + } +} -- cgit v1.2.3 From 645a9c3a274109512839b79d8e86a805a39cd6e1 Mon Sep 17 00:00:00 2001 From: Florian Diebold Date: Sun, 4 Apr 2021 20:27:40 +0200 Subject: Move things from `traits` module to `types` as well --- crates/hir_ty/src/walk.rs | 26 ++++++++++++++++++++++++-- 1 file changed, 24 insertions(+), 2 deletions(-) (limited to 'crates/hir_ty/src/walk.rs') diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs index fec5c2f42..bfb3f1041 100644 --- a/crates/hir_ty/src/walk.rs +++ b/crates/hir_ty/src/walk.rs @@ -6,8 +6,8 @@ use std::mem; use chalk_ir::DebruijnIndex; use crate::{ - utils::make_mut_slice, AliasTy, Binders, CallableSig, GenericArg, GenericArgData, Interner, - OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, + utils::make_mut_slice, AliasEq, AliasTy, Binders, CallableSig, GenericArg, GenericArgData, + Interner, OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, }; /// This allows walking structures that contain types to do something with those @@ -357,3 +357,25 @@ impl TypeWalk for CallableSig { } } } + +impl TypeWalk for AliasEq { + fn walk(&self, f: &mut impl FnMut(&Ty)) { + self.ty.walk(f); + match &self.alias { + AliasTy::Projection(projection_ty) => projection_ty.walk(f), + AliasTy::Opaque(opaque) => opaque.walk(f), + } + } + + fn walk_mut_binders( + &mut self, + f: &mut impl FnMut(&mut Ty, DebruijnIndex), + binders: DebruijnIndex, + ) { + self.ty.walk_mut_binders(f, binders); + match &mut self.alias { + AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders), + AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders), + } + } +} -- cgit v1.2.3