diff options
Diffstat (limited to 'crates/hir_ty/src/walk.rs')
-rw-r--r-- | crates/hir_ty/src/walk.rs | 287 |
1 files changed, 7 insertions, 280 deletions
diff --git a/crates/hir_ty/src/walk.rs b/crates/hir_ty/src/walk.rs index 91116dcda..6ef1d5336 100644 --- a/crates/hir_ty/src/walk.rs +++ b/crates/hir_ty/src/walk.rs | |||
@@ -1,138 +1,17 @@ | |||
1 | //! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and | 1 | //! The `TypeWalk` trait (probably to be replaced by Chalk's `Fold` and |
2 | //! `Visit`). | 2 | //! `Visit`). |
3 | 3 | ||
4 | use std::mem; | 4 | use chalk_ir::interner::HasInterner; |
5 | |||
6 | use chalk_ir::DebruijnIndex; | ||
7 | 5 | ||
8 | use crate::{ | 6 | use crate::{ |
9 | utils::make_mut_slice, AliasEq, AliasTy, Binders, CallableSig, FnSubst, GenericArg, | 7 | AliasEq, AliasTy, Binders, CallableSig, FnSubst, GenericArg, GenericArgData, Interner, |
10 | GenericArgData, Interner, OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, | 8 | OpaqueTy, ProjectionTy, Substitution, TraitRef, Ty, TyKind, WhereClause, |
11 | WhereClause, | ||
12 | }; | 9 | }; |
13 | 10 | ||
14 | /// This allows walking structures that contain types to do something with those | 11 | /// This allows walking structures that contain types to do something with those |
15 | /// types, similar to Chalk's `Fold` trait. | 12 | /// types, similar to Chalk's `Fold` trait. |
16 | pub trait TypeWalk { | 13 | pub trait TypeWalk { |
17 | fn walk(&self, f: &mut impl FnMut(&Ty)); | 14 | 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 | } | 15 | } |
137 | 16 | ||
138 | impl TypeWalk for Ty { | 17 | impl TypeWalk for Ty { |
@@ -174,45 +53,6 @@ impl TypeWalk for Ty { | |||
174 | } | 53 | } |
175 | f(self); | 54 | f(self); |
176 | } | 55 | } |
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 | } | 56 | } |
217 | 57 | ||
218 | impl<T: TypeWalk> TypeWalk for Vec<T> { | 58 | impl<T: TypeWalk> TypeWalk for Vec<T> { |
@@ -221,43 +61,18 @@ impl<T: TypeWalk> TypeWalk for Vec<T> { | |||
221 | t.walk(f); | 61 | t.walk(f); |
222 | } | 62 | } |
223 | } | 63 | } |
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 | } | 64 | } |
234 | 65 | ||
235 | impl TypeWalk for OpaqueTy { | 66 | impl TypeWalk for OpaqueTy { |
236 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | 67 | fn walk(&self, f: &mut impl FnMut(&Ty)) { |
237 | self.substitution.walk(f); | 68 | self.substitution.walk(f); |
238 | } | 69 | } |
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 | } | 70 | } |
248 | 71 | ||
249 | impl TypeWalk for ProjectionTy { | 72 | impl TypeWalk for ProjectionTy { |
250 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | 73 | fn walk(&self, f: &mut impl FnMut(&Ty)) { |
251 | self.substitution.walk(f); | 74 | self.substitution.walk(f); |
252 | } | 75 | } |
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 | } | 76 | } |
262 | 77 | ||
263 | impl TypeWalk for AliasTy { | 78 | impl TypeWalk for AliasTy { |
@@ -267,17 +82,6 @@ impl TypeWalk for AliasTy { | |||
267 | AliasTy::Opaque(it) => it.walk(f), | 82 | AliasTy::Opaque(it) => it.walk(f), |
268 | } | 83 | } |
269 | } | 84 | } |
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 | } | 85 | } |
282 | 86 | ||
283 | impl TypeWalk for GenericArg { | 87 | impl TypeWalk for GenericArg { |
@@ -286,18 +90,7 @@ impl TypeWalk for GenericArg { | |||
286 | GenericArgData::Ty(ty) => { | 90 | GenericArgData::Ty(ty) => { |
287 | ty.walk(f); | 91 | ty.walk(f); |
288 | } | 92 | } |
289 | } | 93 | _ => {} |
290 | } | ||
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 | } | 94 | } |
302 | } | 95 | } |
303 | } | 96 | } |
@@ -308,44 +101,18 @@ impl TypeWalk for Substitution { | |||
308 | t.walk(f); | 101 | t.walk(f); |
309 | } | 102 | } |
310 | } | 103 | } |
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 | } | 104 | } |
322 | 105 | ||
323 | impl<T: TypeWalk> TypeWalk for Binders<T> { | 106 | impl<T: TypeWalk + HasInterner<Interner = Interner>> TypeWalk for Binders<T> { |
324 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | 107 | fn walk(&self, f: &mut impl FnMut(&Ty)) { |
325 | self.skip_binders().walk(f); | 108 | self.skip_binders().walk(f); |
326 | } | 109 | } |
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 | } | 110 | } |
336 | 111 | ||
337 | impl TypeWalk for TraitRef { | 112 | impl TypeWalk for TraitRef { |
338 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | 113 | fn walk(&self, f: &mut impl FnMut(&Ty)) { |
339 | self.substitution.walk(f); | 114 | self.substitution.walk(f); |
340 | } | 115 | } |
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 | } | 116 | } |
350 | 117 | ||
351 | impl TypeWalk for WhereClause { | 118 | impl TypeWalk for WhereClause { |
@@ -353,17 +120,7 @@ impl TypeWalk for WhereClause { | |||
353 | match self { | 120 | match self { |
354 | WhereClause::Implemented(trait_ref) => trait_ref.walk(f), | 121 | WhereClause::Implemented(trait_ref) => trait_ref.walk(f), |
355 | WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), | 122 | WhereClause::AliasEq(alias_eq) => alias_eq.walk(f), |
356 | } | 123 | _ => {} |
357 | } | ||
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 | } | 124 | } |
368 | } | 125 | } |
369 | } | 126 | } |
@@ -374,16 +131,6 @@ impl TypeWalk for CallableSig { | |||
374 | t.walk(f); | 131 | t.walk(f); |
375 | } | 132 | } |
376 | } | 133 | } |
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 | } | 134 | } |
388 | 135 | ||
389 | impl TypeWalk for AliasEq { | 136 | impl TypeWalk for AliasEq { |
@@ -394,30 +141,10 @@ impl TypeWalk for AliasEq { | |||
394 | AliasTy::Opaque(opaque) => opaque.walk(f), | 141 | AliasTy::Opaque(opaque) => opaque.walk(f), |
395 | } | 142 | } |
396 | } | 143 | } |
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 | } | 144 | } |
410 | 145 | ||
411 | impl TypeWalk for FnSubst { | 146 | impl TypeWalk for FnSubst<Interner> { |
412 | fn walk(&self, f: &mut impl FnMut(&Ty)) { | 147 | fn walk(&self, f: &mut impl FnMut(&Ty)) { |
413 | self.0.walk(f) | 148 | self.0.walk(f) |
414 | } | 149 | } |
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 | } | 150 | } |