aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
Diffstat (limited to 'crates')
-rw-r--r--crates/hir_ty/src/walk.rs272
1 files changed, 0 insertions, 272 deletions
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs
index c1aecdafc..28875dbe0 100644
--- a/crates/hir_ty/src/walk.rs
+++ b/crates/hir_ty/src/walk.rs
@@ -15,124 +15,6 @@ use crate::{
15/// types, similar to Chalk's `Fold` trait. 15/// types, similar to Chalk's `Fold` trait.
16pub trait TypeWalk { 16pub trait TypeWalk {
17 fn walk(&self, f: &mut impl FnMut(&Ty)); 17 fn walk(&self, f: &mut impl FnMut(&Ty));
18 fn walk_mut(&mut self, f: &mut impl FnMut(&mut Ty)) {
19 self.walk_mut_binders(&mut |ty, _binders| f(ty), DebruijnIndex::INNERMOST);
20 }
21 /// Walk the type, counting entered binders.
22 ///
23 /// `TyKind::Bound` variables use DeBruijn indexing, which means that 0 refers
24 /// to the innermost binder, 1 to the next, etc.. So when we want to
25 /// substitute a certain bound variable, we can't just walk the whole type
26 /// and blindly replace each instance of a certain index; when we 'enter'
27 /// things that introduce new bound variables, we have to keep track of
28 /// that. Currently, the only thing that introduces bound variables on our
29 /// side are `TyKind::Dyn` and `TyKind::Opaque`, which each introduce a bound
30 /// variable for the self type.
31 fn walk_mut_binders(
32 &mut self,
33 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
34 binders: DebruijnIndex,
35 );
36
37 fn fold_binders(
38 mut self,
39 f: &mut impl FnMut(Ty, DebruijnIndex) -> Ty,
40 binders: DebruijnIndex,
41 ) -> Self
42 where
43 Self: Sized,
44 {
45 self.walk_mut_binders(
46 &mut |ty_mut, binders| {
47 let ty = mem::replace(ty_mut, TyKind::Error.intern(&Interner));
48 *ty_mut = f(ty, binders);
49 },
50 binders,
51 );
52 self
53 }
54
55 fn fold(mut self, f: &mut impl FnMut(Ty) -> Ty) -> Self
56 where
57 Self: Sized,
58 {
59 self.walk_mut(&mut |ty_mut| {
60 let ty = mem::replace(ty_mut, TyKind::Error.intern(&Interner));
61 *ty_mut = f(ty);
62 });
63 self
64 }
65
66 /// Substitutes `TyKind::Bound` vars with the given substitution.
67 fn subst_bound_vars(self, substs: &Substitution) -> Self
68 where
69 Self: Sized,
70 {
71 self.subst_bound_vars_at_depth(substs, DebruijnIndex::INNERMOST)
72 }
73
74 /// Substitutes `TyKind::Bound` vars with the given substitution.
75 fn subst_bound_vars_at_depth(mut self, substs: &Substitution, depth: DebruijnIndex) -> Self
76 where
77 Self: Sized,
78 {
79 self.walk_mut_binders(
80 &mut |ty, binders| {
81 if let &mut TyKind::BoundVar(bound) = ty.interned_mut() {
82 if bound.debruijn >= binders {
83 *ty = substs.interned()[bound.index]
84 .assert_ty_ref(&Interner)
85 .clone()
86 .shifted_in_from(binders);
87 }
88 }
89 },
90 depth,
91 );
92 self
93 }
94
95 fn shifted_in(self, _interner: &Interner) -> Self
96 where
97 Self: Sized,
98 {
99 self.shifted_in_from(DebruijnIndex::ONE)
100 }
101
102 /// Shifts up debruijn indices of `TyKind::Bound` vars by `n`.
103 fn shifted_in_from(self, n: DebruijnIndex) -> Self
104 where
105 Self: Sized,
106 {
107 self.fold_binders(
108 &mut |ty, binders| match ty.kind(&Interner) {
109 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
110 TyKind::BoundVar(bound.shifted_in_from(n)).intern(&Interner)
111 }
112 _ => ty,
113 },
114 DebruijnIndex::INNERMOST,
115 )
116 }
117
118 /// Shifts debruijn indices of `TyKind::Bound` vars out (down) by `n`.
119 fn shifted_out_to(self, n: DebruijnIndex) -> Option<Self>
120 where
121 Self: Sized + std::fmt::Debug,
122 {
123 Some(self.fold_binders(
124 &mut |ty, binders| {
125 match ty.kind(&Interner) {
126 TyKind::BoundVar(bound) if bound.debruijn >= binders => {
127 TyKind::BoundVar(bound.shifted_out_to(n).unwrap_or(bound.clone()))
128 .intern(&Interner)
129 }
130 _ => ty,
131 }
132 },
133 DebruijnIndex::INNERMOST,
134 ))
135 }
136} 18}
137 19
138impl TypeWalk for Ty { 20impl TypeWalk for Ty {
@@ -174,45 +56,6 @@ impl TypeWalk for Ty {
174 } 56 }
175 f(self); 57 f(self);
176 } 58 }
177
178 fn walk_mut_binders(
179 &mut self,
180 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
181 binders: DebruijnIndex,
182 ) {
183 match self.interned_mut() {
184 TyKind::Alias(AliasTy::Projection(p_ty)) => {
185 p_ty.substitution.walk_mut_binders(f, binders);
186 }
187 TyKind::Dyn(dyn_ty) => {
188 for p in make_mut_slice(dyn_ty.bounds.skip_binders_mut().interned_mut()) {
189 p.walk_mut_binders(f, binders.shifted_in());
190 }
191 }
192 TyKind::Alias(AliasTy::Opaque(o_ty)) => {
193 o_ty.substitution.walk_mut_binders(f, binders);
194 }
195 TyKind::Slice(ty)
196 | TyKind::Array(ty, _)
197 | TyKind::Ref(_, _, ty)
198 | TyKind::Raw(_, ty) => {
199 ty.walk_mut_binders(f, binders);
200 }
201 TyKind::Function(fn_pointer) => {
202 fn_pointer.substitution.0.walk_mut_binders(f, binders.shifted_in());
203 }
204 TyKind::Adt(_, substs)
205 | TyKind::FnDef(_, substs)
206 | TyKind::Tuple(_, substs)
207 | TyKind::OpaqueType(_, substs)
208 | TyKind::AssociatedType(_, substs)
209 | TyKind::Closure(.., substs) => {
210 substs.walk_mut_binders(f, binders);
211 }
212 _ => {}
213 }
214 f(self, binders);
215 }
216} 59}
217 60
218impl<T: TypeWalk> TypeWalk for Vec<T> { 61impl<T: TypeWalk> TypeWalk for Vec<T> {
@@ -221,43 +64,18 @@ impl<T: TypeWalk> TypeWalk for Vec<T> {
221 t.walk(f); 64 t.walk(f);
222 } 65 }
223 } 66 }
224 fn walk_mut_binders(
225 &mut self,
226 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
227 binders: DebruijnIndex,
228 ) {
229 for t in self {
230 t.walk_mut_binders(f, binders);
231 }
232 }
233} 67}
234 68
235impl TypeWalk for OpaqueTy { 69impl TypeWalk for OpaqueTy {
236 fn walk(&self, f: &mut impl FnMut(&Ty)) { 70 fn walk(&self, f: &mut impl FnMut(&Ty)) {
237 self.substitution.walk(f); 71 self.substitution.walk(f);
238 } 72 }
239
240 fn walk_mut_binders(
241 &mut self,
242 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
243 binders: DebruijnIndex,
244 ) {
245 self.substitution.walk_mut_binders(f, binders);
246 }
247} 73}
248 74
249impl TypeWalk for ProjectionTy { 75impl TypeWalk for ProjectionTy {
250 fn walk(&self, f: &mut impl FnMut(&Ty)) { 76 fn walk(&self, f: &mut impl FnMut(&Ty)) {
251 self.substitution.walk(f); 77 self.substitution.walk(f);
252 } 78 }
253
254 fn walk_mut_binders(
255 &mut self,
256 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
257 binders: DebruijnIndex,
258 ) {
259 self.substitution.walk_mut_binders(f, binders);
260 }
261} 79}
262 80
263impl TypeWalk for AliasTy { 81impl TypeWalk for AliasTy {
@@ -267,17 +85,6 @@ impl TypeWalk for AliasTy {
267 AliasTy::Opaque(it) => it.walk(f), 85 AliasTy::Opaque(it) => it.walk(f),
268 } 86 }
269 } 87 }
270
271 fn walk_mut_binders(
272 &mut self,
273 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
274 binders: DebruijnIndex,
275 ) {
276 match self {
277 AliasTy::Projection(it) => it.walk_mut_binders(f, binders),
278 AliasTy::Opaque(it) => it.walk_mut_binders(f, binders),
279 }
280 }
281} 88}
282 89
283impl TypeWalk for GenericArg { 90impl TypeWalk for GenericArg {
@@ -288,18 +95,6 @@ impl TypeWalk for GenericArg {
288 } 95 }
289 } 96 }
290 } 97 }
291
292 fn walk_mut_binders(
293 &mut self,
294 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
295 binders: DebruijnIndex,
296 ) {
297 match self.interned_mut() {
298 GenericArgData::Ty(ty) => {
299 ty.walk_mut_binders(f, binders);
300 }
301 }
302 }
303} 98}
304 99
305impl TypeWalk for Substitution { 100impl TypeWalk for Substitution {
@@ -308,44 +103,18 @@ impl TypeWalk for Substitution {
308 t.walk(f); 103 t.walk(f);
309 } 104 }
310 } 105 }
311
312 fn walk_mut_binders(
313 &mut self,
314 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
315 binders: DebruijnIndex,
316 ) {
317 for t in self.interned_mut() {
318 t.walk_mut_binders(f, binders);
319 }
320 }
321} 106}
322 107
323impl<T: TypeWalk + HasInterner<Interner = Interner>> TypeWalk for Binders<T> { 108impl<T: TypeWalk + HasInterner<Interner = Interner>> TypeWalk for Binders<T> {
324 fn walk(&self, f: &mut impl FnMut(&Ty)) { 109 fn walk(&self, f: &mut impl FnMut(&Ty)) {
325 self.skip_binders().walk(f); 110 self.skip_binders().walk(f);
326 } 111 }
327
328 fn walk_mut_binders(
329 &mut self,
330 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
331 binders: DebruijnIndex,
332 ) {
333 self.skip_binders_mut().walk_mut_binders(f, binders.shifted_in())
334 }
335} 112}
336 113
337impl TypeWalk for TraitRef { 114impl TypeWalk for TraitRef {
338 fn walk(&self, f: &mut impl FnMut(&Ty)) { 115 fn walk(&self, f: &mut impl FnMut(&Ty)) {
339 self.substitution.walk(f); 116 self.substitution.walk(f);
340 } 117 }
341
342 fn walk_mut_binders(
343 &mut self,
344 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
345 binders: DebruijnIndex,
346 ) {
347 self.substitution.walk_mut_binders(f, binders);
348 }
349} 118}
350 119
351impl TypeWalk for WhereClause { 120impl TypeWalk for WhereClause {
@@ -355,17 +124,6 @@ impl TypeWalk for WhereClause {
355 WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), 124 WhereClause::AliasEq(alias_eq) => alias_eq.walk(f),
356 } 125 }
357 } 126 }
358
359 fn walk_mut_binders(
360 &mut self,
361 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
362 binders: DebruijnIndex,
363 ) {
364 match self {
365 WhereClause::Implemented(trait_ref) => trait_ref.walk_mut_binders(f, binders),
366 WhereClause::AliasEq(alias_eq) => alias_eq.walk_mut_binders(f, binders),
367 }
368 }
369} 127}
370 128
371impl TypeWalk for CallableSig { 129impl TypeWalk for CallableSig {
@@ -374,16 +132,6 @@ impl TypeWalk for CallableSig {
374 t.walk(f); 132 t.walk(f);
375 } 133 }
376 } 134 }
377
378 fn walk_mut_binders(
379 &mut self,
380 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
381 binders: DebruijnIndex,
382 ) {
383 for t in make_mut_slice(&mut self.params_and_return) {
384 t.walk_mut_binders(f, binders);
385 }
386 }
387} 135}
388 136
389impl TypeWalk for AliasEq { 137impl TypeWalk for AliasEq {
@@ -394,30 +142,10 @@ impl TypeWalk for AliasEq {
394 AliasTy::Opaque(opaque) => opaque.walk(f), 142 AliasTy::Opaque(opaque) => opaque.walk(f),
395 } 143 }
396 } 144 }
397
398 fn walk_mut_binders(
399 &mut self,
400 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
401 binders: DebruijnIndex,
402 ) {
403 self.ty.walk_mut_binders(f, binders);
404 match &mut self.alias {
405 AliasTy::Projection(projection_ty) => projection_ty.walk_mut_binders(f, binders),
406 AliasTy::Opaque(opaque) => opaque.walk_mut_binders(f, binders),
407 }
408 }
409} 145}
410 146
411impl TypeWalk for FnSubst<Interner> { 147impl TypeWalk for FnSubst<Interner> {
412 fn walk(&self, f: &mut impl FnMut(&Ty)) { 148 fn walk(&self, f: &mut impl FnMut(&Ty)) {
413 self.0.walk(f) 149 self.0.walk(f)
414 } 150 }
415
416 fn walk_mut_binders(
417 &mut self,
418 f: &mut impl FnMut(&mut Ty, DebruijnIndex),
419 binders: DebruijnIndex,
420 ) {
421 self.0.walk_mut_binders(f, binders)
422 }
423} 151}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 16:59:12 +0000