]>
Commit | Line | Data |
---|---|---|
064997fb FG |
1 | //! A folding traversal mechanism for complex data structures that contain type |
2 | //! information. | |
e9174d1e | 3 | //! |
064997fb FG |
4 | //! This is a modifying traversal. It consumes the data structure, producing a |
5 | //! (possibly) modified version of it. Both fallible and infallible versions are | |
6 | //! available. The name is potentially confusing, because this traversal is more | |
7 | //! like `Iterator::map` than `Iterator::fold`. | |
e9174d1e | 8 | //! |
064997fb | 9 | //! This traversal has limited flexibility. Only a small number of "types of |
5099ac24 | 10 | //! interest" within the complex data structures can receive custom |
064997fb FG |
11 | //! modification. These are the ones containing the most important type-related |
12 | //! information, such as `Ty`, `Predicate`, `Region`, and `Const`. | |
e9174d1e | 13 | //! |
064997fb FG |
14 | //! There are three groups of traits involved in each traversal. |
15 | //! - `TypeFoldable`. This is implemented once for many types, including: | |
2b03887a | 16 | //! - Types of interest, for which the methods delegate to the folder. |
923072b8 | 17 | //! - All other types, including generic containers like `Vec` and `Option`. |
064997fb | 18 | //! It defines a "skeleton" of how they should be folded. |
923072b8 | 19 | //! - `TypeSuperFoldable`. This is implemented only for each type of interest, |
064997fb FG |
20 | //! and defines the folding "skeleton" for these types. |
21 | //! - `TypeFolder`/`FallibleTypeFolder. One of these is implemented for each | |
22 | //! folder. This defines how types of interest are folded. | |
e9174d1e | 23 | //! |
064997fb FG |
24 | //! This means each fold is a mixture of (a) generic folding operations, and (b) |
25 | //! custom fold operations that are specific to the folder. | |
5099ac24 | 26 | //! - The `TypeFoldable` impls handle most of the traversal, and call into |
064997fb FG |
27 | //! `TypeFolder`/`FallibleTypeFolder` when they encounter a type of interest. |
28 | //! - A `TypeFolder`/`FallibleTypeFolder` may call into another `TypeFoldable` | |
29 | //! impl, because some of the types of interest are recursive and can contain | |
30 | //! other types of interest. | |
31 | //! - A `TypeFolder`/`FallibleTypeFolder` may also call into a `TypeSuperFoldable` | |
32 | //! impl, because each folder might provide custom handling only for some types | |
33 | //! of interest, or only for some variants of each type of interest, and then | |
34 | //! use default traversal for the remaining cases. | |
9cc50fc6 | 35 | //! |
5099ac24 | 36 | //! For example, if you have `struct S(Ty, U)` where `S: TypeFoldable` and `U: |
064997fb | 37 | //! TypeFoldable`, and an instance `s = S(ty, u)`, it would be folded like so: |
04454e1e | 38 | //! ```text |
064997fb FG |
39 | //! s.fold_with(folder) calls |
40 | //! - ty.fold_with(folder) calls | |
41 | //! - folder.fold_ty(ty) may call | |
42 | //! - ty.super_fold_with(folder) | |
43 | //! - u.fold_with(folder) | |
5099ac24 | 44 | //! ``` |
064997fb FG |
45 | use crate::ty::{self, Binder, BoundTy, Ty, TyCtxt, TypeVisitable}; |
46 | use rustc_data_structures::fx::FxIndexMap; | |
dfeec247 | 47 | use rustc_hir::def_id::DefId; |
e9174d1e | 48 | |
94b46f34 | 49 | use std::collections::BTreeMap; |
e9174d1e | 50 | |
064997fb | 51 | /// This trait is implemented for every type that can be folded, |
5099ac24 | 52 | /// providing the skeleton of the traversal. |
0531ce1d | 53 | /// |
5099ac24 FG |
54 | /// To implement this conveniently, use the derive macro located in |
55 | /// `rustc_macros`. | |
064997fb | 56 | pub trait TypeFoldable<'tcx>: TypeVisitable<'tcx> { |
923072b8 | 57 | /// The entry point for folding. To fold a value `t` with a folder `f` |
5099ac24 FG |
58 | /// call: `t.try_fold_with(f)`. |
59 | /// | |
923072b8 FG |
60 | /// For most types, this just traverses the value, calling `try_fold_with` |
61 | /// on each field/element. | |
62 | /// | |
63 | /// For types of interest (such as `Ty`), the implementation of method | |
64 | /// calls a folder method specifically for that type (such as | |
5099ac24 FG |
65 | /// `F::try_fold_ty`). This is where control transfers from `TypeFoldable` |
66 | /// to `TypeFolder`. | |
923072b8 | 67 | fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error>; |
5099ac24 FG |
68 | |
69 | /// A convenient alternative to `try_fold_with` for use with infallible | |
70 | /// folders. Do not override this method, to ensure coherence with | |
71 | /// `try_fold_with`. | |
064997fb | 72 | fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { |
a2a8927a XL |
73 | self.try_fold_with(folder).into_ok() |
74 | } | |
e9174d1e SL |
75 | } |
76 | ||
923072b8 FG |
77 | // This trait is implemented for types of interest. |
78 | pub trait TypeSuperFoldable<'tcx>: TypeFoldable<'tcx> { | |
79 | /// Provides a default fold for a type of interest. This should only be | |
80 | /// called within `TypeFolder` methods, when a non-custom traversal is | |
81 | /// desired for the value of the type of interest passed to that method. | |
82 | /// For example, in `MyFolder::try_fold_ty(ty)`, it is valid to call | |
83 | /// `ty.try_super_fold_with(self)`, but any other folding should be done | |
84 | /// with `xyz.try_fold_with(self)`. | |
85 | fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>( | |
86 | self, | |
87 | folder: &mut F, | |
88 | ) -> Result<Self, F::Error>; | |
89 | ||
90 | /// A convenient alternative to `try_super_fold_with` for use with | |
91 | /// infallible folders. Do not override this method, to ensure coherence | |
92 | /// with `try_super_fold_with`. | |
064997fb | 93 | fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { |
923072b8 FG |
94 | self.try_super_fold_with(folder).into_ok() |
95 | } | |
923072b8 FG |
96 | } |
97 | ||
064997fb FG |
98 | /// This trait is implemented for every infallible folding traversal. There is |
99 | /// a fold method defined for every type of interest. Each such method has a | |
100 | /// default that does an "identity" fold. Implementations of these methods | |
101 | /// often fall back to a `super_fold_with` method if the primary argument | |
102 | /// doesn't satisfy a particular condition. | |
a2a8927a | 103 | /// |
064997fb | 104 | /// A blanket implementation of [`FallibleTypeFolder`] will defer to |
a2a8927a XL |
105 | /// the infallible methods of this trait to ensure that the two APIs |
106 | /// are coherent. | |
064997fb | 107 | pub trait TypeFolder<'tcx>: FallibleTypeFolder<'tcx, Error = !> { |
dc9dc135 | 108 | fn tcx<'a>(&'a self) -> TyCtxt<'tcx>; |
e9174d1e | 109 | |
cdc7bbd5 | 110 | fn fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Binder<'tcx, T> |
dfeec247 XL |
111 | where |
112 | T: TypeFoldable<'tcx>, | |
e9174d1e | 113 | { |
9cc50fc6 | 114 | t.super_fold_with(self) |
e9174d1e SL |
115 | } |
116 | ||
064997fb | 117 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { |
9cc50fc6 | 118 | t.super_fold_with(self) |
e9174d1e SL |
119 | } |
120 | ||
064997fb | 121 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9cc50fc6 | 122 | r.super_fold_with(self) |
e9174d1e | 123 | } |
ea8adc8c | 124 | |
064997fb | 125 | fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { |
ea8adc8c XL |
126 | c.super_fold_with(self) |
127 | } | |
cdc7bbd5 | 128 | |
064997fb | 129 | fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { |
94222f64 XL |
130 | p.super_fold_with(self) |
131 | } | |
e9174d1e SL |
132 | } |
133 | ||
5099ac24 FG |
134 | /// This trait is implemented for every folding traversal. There is a fold |
135 | /// method defined for every type of interest. Each such method has a default | |
136 | /// that does an "identity" fold. | |
a2a8927a XL |
137 | /// |
138 | /// A blanket implementation of this trait (that defers to the relevant | |
139 | /// method of [`TypeFolder`]) is provided for all infallible folders in | |
140 | /// order to ensure the two APIs are coherent. | |
064997fb FG |
141 | pub trait FallibleTypeFolder<'tcx>: Sized { |
142 | type Error; | |
143 | ||
144 | fn tcx<'a>(&'a self) -> TyCtxt<'tcx>; | |
145 | ||
a2a8927a XL |
146 | fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error> |
147 | where | |
148 | T: TypeFoldable<'tcx>, | |
149 | { | |
150 | t.try_super_fold_with(self) | |
151 | } | |
152 | ||
153 | fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> { | |
154 | t.try_super_fold_with(self) | |
155 | } | |
156 | ||
157 | fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> { | |
158 | r.try_super_fold_with(self) | |
159 | } | |
160 | ||
5099ac24 | 161 | fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, Self::Error> { |
a2a8927a XL |
162 | c.try_super_fold_with(self) |
163 | } | |
164 | ||
165 | fn try_fold_predicate( | |
166 | &mut self, | |
167 | p: ty::Predicate<'tcx>, | |
168 | ) -> Result<ty::Predicate<'tcx>, Self::Error> { | |
169 | p.try_super_fold_with(self) | |
170 | } | |
a2a8927a XL |
171 | } |
172 | ||
5099ac24 FG |
173 | // This blanket implementation of the fallible trait for infallible folders |
174 | // delegates to infallible methods to ensure coherence. | |
a2a8927a XL |
175 | impl<'tcx, F> FallibleTypeFolder<'tcx> for F |
176 | where | |
064997fb | 177 | F: TypeFolder<'tcx>, |
a2a8927a | 178 | { |
064997fb FG |
179 | type Error = !; |
180 | ||
181 | fn tcx<'a>(&'a self) -> TyCtxt<'tcx> { | |
182 | TypeFolder::tcx(self) | |
183 | } | |
184 | ||
185 | fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, !> | |
a2a8927a XL |
186 | where |
187 | T: TypeFoldable<'tcx>, | |
188 | { | |
189 | Ok(self.fold_binder(t)) | |
190 | } | |
191 | ||
064997fb | 192 | fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, !> { |
a2a8927a XL |
193 | Ok(self.fold_ty(t)) |
194 | } | |
195 | ||
064997fb | 196 | fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, !> { |
a2a8927a XL |
197 | Ok(self.fold_region(r)) |
198 | } | |
199 | ||
064997fb | 200 | fn try_fold_const(&mut self, c: ty::Const<'tcx>) -> Result<ty::Const<'tcx>, !> { |
a2a8927a XL |
201 | Ok(self.fold_const(c)) |
202 | } | |
203 | ||
064997fb | 204 | fn try_fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> Result<ty::Predicate<'tcx>, !> { |
a2a8927a XL |
205 | Ok(self.fold_predicate(p)) |
206 | } | |
a2a8927a XL |
207 | } |
208 | ||
e9174d1e SL |
209 | /////////////////////////////////////////////////////////////////////////// |
210 | // Some sample folders | |
211 | ||
dc9dc135 XL |
212 | pub struct BottomUpFolder<'tcx, F, G, H> |
213 | where | |
214 | F: FnMut(Ty<'tcx>) -> Ty<'tcx>, | |
215 | G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>, | |
5099ac24 | 216 | H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>, |
a7813a04 | 217 | { |
dc9dc135 | 218 | pub tcx: TyCtxt<'tcx>, |
48663c56 XL |
219 | pub ty_op: F, |
220 | pub lt_op: G, | |
221 | pub ct_op: H, | |
e9174d1e SL |
222 | } |
223 | ||
dc9dc135 XL |
224 | impl<'tcx, F, G, H> TypeFolder<'tcx> for BottomUpFolder<'tcx, F, G, H> |
225 | where | |
226 | F: FnMut(Ty<'tcx>) -> Ty<'tcx>, | |
227 | G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>, | |
5099ac24 | 228 | H: FnMut(ty::Const<'tcx>) -> ty::Const<'tcx>, |
e9174d1e | 229 | { |
dc9dc135 XL |
230 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { |
231 | self.tcx | |
dfeec247 | 232 | } |
e9174d1e SL |
233 | |
234 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
48663c56 XL |
235 | let t = ty.super_fold_with(self); |
236 | (self.ty_op)(t) | |
e9174d1e | 237 | } |
8faf50e0 XL |
238 | |
239 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { | |
240 | let r = r.super_fold_with(self); | |
48663c56 XL |
241 | (self.lt_op)(r) |
242 | } | |
243 | ||
5099ac24 | 244 | fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
48663c56 XL |
245 | let ct = ct.super_fold_with(self); |
246 | (self.ct_op)(ct) | |
8faf50e0 | 247 | } |
e9174d1e SL |
248 | } |
249 | ||
250 | /////////////////////////////////////////////////////////////////////////// | |
251 | // Region folder | |
252 | ||
dc9dc135 | 253 | impl<'tcx> TyCtxt<'tcx> { |
e9174d1e SL |
254 | /// Folds the escaping and free regions in `value` using `f`, and |
255 | /// sets `skipped_regions` to true if any late-bound region was found | |
256 | /// and skipped. | |
94b46f34 XL |
257 | pub fn fold_regions<T>( |
258 | self, | |
fc512014 | 259 | value: T, |
94b46f34 XL |
260 | mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, |
261 | ) -> T | |
262 | where | |
dfeec247 | 263 | T: TypeFoldable<'tcx>, |
e9174d1e | 264 | { |
064997fb | 265 | value.fold_with(&mut RegionFolder::new(self, &mut f)) |
abe05a73 | 266 | } |
f2b60f7d FG |
267 | |
268 | pub fn super_fold_regions<T>( | |
269 | self, | |
270 | value: T, | |
271 | mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, | |
272 | ) -> T | |
273 | where | |
274 | T: TypeSuperFoldable<'tcx>, | |
275 | { | |
276 | value.super_fold_with(&mut RegionFolder::new(self, &mut f)) | |
277 | } | |
e9174d1e SL |
278 | } |
279 | ||
280 | /// Folds over the substructure of a type, visiting its component | |
281 | /// types and all regions that occur *free* within it. | |
282 | /// | |
283 | /// That is, `Ty` can contain function or method types that bind | |
284 | /// regions at the call site (`ReLateBound`), and occurrences of | |
285 | /// regions (aka "lifetimes") that are bound within a type are not | |
286 | /// visited by this folder; only regions that occur free will be | |
287 | /// visited by `fld_r`. | |
288 | ||
dc9dc135 XL |
289 | pub struct RegionFolder<'a, 'tcx> { |
290 | tcx: TyCtxt<'tcx>, | |
94b46f34 XL |
291 | |
292 | /// Stores the index of a binder *just outside* the stuff we have | |
293 | /// visited. So this begins as INNERMOST; when we pass through a | |
294 | /// binder, it is incremented (via `shift_in`). | |
295 | current_index: ty::DebruijnIndex, | |
296 | ||
297 | /// Callback invokes for each free region. The `DebruijnIndex` | |
298 | /// points to the binder *just outside* the ones we have passed | |
299 | /// through. | |
dc9dc135 XL |
300 | fold_region_fn: |
301 | &'a mut (dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx> + 'a), | |
e9174d1e SL |
302 | } |
303 | ||
dc9dc135 | 304 | impl<'a, 'tcx> RegionFolder<'a, 'tcx> { |
a1dfa0c6 | 305 | #[inline] |
94b46f34 | 306 | pub fn new( |
dc9dc135 | 307 | tcx: TyCtxt<'tcx>, |
94b46f34 | 308 | fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, |
dc9dc135 | 309 | ) -> RegionFolder<'a, 'tcx> { |
064997fb | 310 | RegionFolder { tcx, current_index: ty::INNERMOST, fold_region_fn } |
e9174d1e SL |
311 | } |
312 | } | |
313 | ||
dc9dc135 XL |
314 | impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> { |
315 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { | |
316 | self.tcx | |
dfeec247 | 317 | } |
e9174d1e | 318 | |
cdc7bbd5 XL |
319 | fn fold_binder<T: TypeFoldable<'tcx>>( |
320 | &mut self, | |
321 | t: ty::Binder<'tcx, T>, | |
322 | ) -> ty::Binder<'tcx, T> { | |
94b46f34 | 323 | self.current_index.shift_in(1); |
54a0048b | 324 | let t = t.super_fold_with(self); |
94b46f34 | 325 | self.current_index.shift_out(1); |
54a0048b | 326 | t |
e9174d1e SL |
327 | } |
328 | ||
f2b60f7d | 329 | #[instrument(skip(self), level = "debug", ret)] |
7cac9316 | 330 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 331 | match *r { |
94b46f34 | 332 | ty::ReLateBound(debruijn, _) if debruijn < self.current_index => { |
c295e0f8 | 333 | debug!(?self.current_index, "skipped bound region"); |
e9174d1e SL |
334 | r |
335 | } | |
336 | _ => { | |
c295e0f8 | 337 | debug!(?self.current_index, "folding free region"); |
94b46f34 | 338 | (self.fold_region_fn)(r, self.current_index) |
e9174d1e SL |
339 | } |
340 | } | |
341 | } | |
342 | } | |
343 | ||
344 | /////////////////////////////////////////////////////////////////////////// | |
a1dfa0c6 | 345 | // Bound vars replacer |
e9174d1e | 346 | |
064997fb FG |
347 | pub trait BoundVarReplacerDelegate<'tcx> { |
348 | fn replace_region(&mut self, br: ty::BoundRegion) -> ty::Region<'tcx>; | |
349 | fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx>; | |
350 | fn replace_const(&mut self, bv: ty::BoundVar, ty: Ty<'tcx>) -> ty::Const<'tcx>; | |
351 | } | |
352 | ||
f2b60f7d FG |
353 | pub struct FnMutDelegate<'a, 'tcx> { |
354 | pub regions: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a), | |
355 | pub types: &'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a), | |
356 | pub consts: &'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> ty::Const<'tcx> + 'a), | |
064997fb | 357 | } |
f2b60f7d FG |
358 | |
359 | impl<'a, 'tcx> BoundVarReplacerDelegate<'tcx> for FnMutDelegate<'a, 'tcx> { | |
064997fb FG |
360 | fn replace_region(&mut self, br: ty::BoundRegion) -> ty::Region<'tcx> { |
361 | (self.regions)(br) | |
362 | } | |
363 | fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx> { | |
364 | (self.types)(bt) | |
365 | } | |
366 | fn replace_const(&mut self, bv: ty::BoundVar, ty: Ty<'tcx>) -> ty::Const<'tcx> { | |
367 | (self.consts)(bv, ty) | |
368 | } | |
369 | } | |
370 | ||
a1dfa0c6 | 371 | /// Replaces the escaping bound vars (late bound regions or bound types) in a type. |
064997fb | 372 | struct BoundVarReplacer<'tcx, D> { |
dc9dc135 | 373 | tcx: TyCtxt<'tcx>, |
94b46f34 XL |
374 | |
375 | /// As with `RegionFolder`, represents the index of a binder *just outside* | |
376 | /// the ones we have visited. | |
377 | current_index: ty::DebruijnIndex, | |
378 | ||
064997fb | 379 | delegate: D, |
a1dfa0c6 XL |
380 | } |
381 | ||
064997fb FG |
382 | impl<'tcx, D: BoundVarReplacerDelegate<'tcx>> BoundVarReplacer<'tcx, D> { |
383 | fn new(tcx: TyCtxt<'tcx>, delegate: D) -> Self { | |
384 | BoundVarReplacer { tcx, current_index: ty::INNERMOST, delegate } | |
a1dfa0c6 XL |
385 | } |
386 | } | |
387 | ||
064997fb FG |
388 | impl<'tcx, D> TypeFolder<'tcx> for BoundVarReplacer<'tcx, D> |
389 | where | |
390 | D: BoundVarReplacerDelegate<'tcx>, | |
391 | { | |
dc9dc135 XL |
392 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { |
393 | self.tcx | |
dfeec247 | 394 | } |
a1dfa0c6 | 395 | |
cdc7bbd5 XL |
396 | fn fold_binder<T: TypeFoldable<'tcx>>( |
397 | &mut self, | |
398 | t: ty::Binder<'tcx, T>, | |
399 | ) -> ty::Binder<'tcx, T> { | |
a1dfa0c6 XL |
400 | self.current_index.shift_in(1); |
401 | let t = t.super_fold_with(self); | |
402 | self.current_index.shift_out(1); | |
403 | t | |
404 | } | |
405 | ||
406 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
1b1a35ee | 407 | match *t.kind() { |
6a06907d | 408 | ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => { |
064997fb | 409 | let ty = self.delegate.replace_ty(bound_ty); |
487cf647 | 410 | debug_assert!(!ty.has_vars_bound_above(ty::INNERMOST)); |
923072b8 | 411 | ty::fold::shift_vars(self.tcx, ty, self.current_index.as_u32()) |
a1dfa0c6 | 412 | } |
923072b8 FG |
413 | _ if t.has_vars_bound_at_or_above(self.current_index) => t.super_fold_with(self), |
414 | _ => t, | |
a1dfa0c6 XL |
415 | } |
416 | } | |
417 | ||
418 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { | |
419 | match *r { | |
420 | ty::ReLateBound(debruijn, br) if debruijn == self.current_index => { | |
064997fb | 421 | let region = self.delegate.replace_region(br); |
923072b8 FG |
422 | if let ty::ReLateBound(debruijn1, br) = *region { |
423 | // If the callback returns a late-bound region, | |
424 | // that region should always use the INNERMOST | |
425 | // debruijn index. Then we adjust it to the | |
426 | // correct depth. | |
427 | assert_eq!(debruijn1, ty::INNERMOST); | |
064997fb | 428 | self.tcx.reuse_or_mk_region(region, ty::ReLateBound(debruijn, br)) |
923072b8 FG |
429 | } else { |
430 | region | |
a1dfa0c6 XL |
431 | } |
432 | } | |
923072b8 | 433 | _ => r, |
a1dfa0c6 XL |
434 | } |
435 | } | |
48663c56 | 436 | |
5099ac24 | 437 | fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
923072b8 | 438 | match ct.kind() { |
5099ac24 | 439 | ty::ConstKind::Bound(debruijn, bound_const) if debruijn == self.current_index => { |
064997fb | 440 | let ct = self.delegate.replace_const(bound_const, ct.ty()); |
487cf647 | 441 | debug_assert!(!ct.has_vars_bound_above(ty::INNERMOST)); |
923072b8 | 442 | ty::fold::shift_vars(self.tcx, ct, self.current_index.as_u32()) |
48663c56 | 443 | } |
064997fb | 444 | _ => ct.super_fold_with(self), |
48663c56 XL |
445 | } |
446 | } | |
064997fb FG |
447 | |
448 | fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { | |
449 | if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p } | |
450 | } | |
e9174d1e SL |
451 | } |
452 | ||
dc9dc135 | 453 | impl<'tcx> TyCtxt<'tcx> { |
9fa01778 | 454 | /// Replaces all regions bound by the given `Binder` with the |
ff7c6d11 XL |
455 | /// results returned by the closure; the closure is expected to |
456 | /// return a free region (relative to this binder), and hence the | |
457 | /// binder is removed in the return type. The closure is invoked | |
fc512014 XL |
458 | /// once for each unique `BoundRegionKind`; multiple references to the |
459 | /// same `BoundRegionKind` will reuse the previous result. A map is | |
ff7c6d11 XL |
460 | /// returned at the end with each bound region and the free region |
461 | /// that replaced it. | |
a1dfa0c6 | 462 | /// |
923072b8 FG |
463 | /// # Panics |
464 | /// | |
465 | /// This method only replaces late bound regions. Any types or | |
466 | /// constants bound by `value` will cause an ICE. | |
a1dfa0c6 XL |
467 | pub fn replace_late_bound_regions<T, F>( |
468 | self, | |
cdc7bbd5 | 469 | value: Binder<'tcx, T>, |
fc512014 | 470 | mut fld_r: F, |
a1dfa0c6 | 471 | ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>) |
dfeec247 XL |
472 | where |
473 | F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, | |
474 | T: TypeFoldable<'tcx>, | |
a1dfa0c6 | 475 | { |
fc512014 | 476 | let mut region_map = BTreeMap::new(); |
923072b8 FG |
477 | let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br)); |
478 | let value = self.replace_late_bound_regions_uncached(value, real_fld_r); | |
479 | (value, region_map) | |
480 | } | |
481 | ||
482 | pub fn replace_late_bound_regions_uncached<T, F>( | |
483 | self, | |
484 | value: Binder<'tcx, T>, | |
f2b60f7d | 485 | mut replace_regions: F, |
923072b8 FG |
486 | ) -> T |
487 | where | |
488 | F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, | |
489 | T: TypeFoldable<'tcx>, | |
490 | { | |
6a06907d | 491 | let value = value.skip_binder(); |
923072b8 | 492 | if !value.has_escaping_bound_vars() { |
6a06907d XL |
493 | value |
494 | } else { | |
064997fb | 495 | let delegate = FnMutDelegate { |
f2b60f7d FG |
496 | regions: &mut replace_regions, |
497 | types: &mut |b| bug!("unexpected bound ty in binder: {b:?}"), | |
498 | consts: &mut |b, ty| bug!("unexpected bound ct in binder: {b:?} {ty}"), | |
064997fb FG |
499 | }; |
500 | let mut replacer = BoundVarReplacer::new(self, delegate); | |
6a06907d | 501 | value.fold_with(&mut replacer) |
923072b8 | 502 | } |
a1dfa0c6 XL |
503 | } |
504 | ||
9fa01778 | 505 | /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping |
48663c56 XL |
506 | /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c` |
507 | /// closure replaces escaping bound consts. | |
064997fb | 508 | pub fn replace_escaping_bound_vars_uncached<T: TypeFoldable<'tcx>>( |
a1dfa0c6 | 509 | self, |
fc512014 | 510 | value: T, |
064997fb FG |
511 | delegate: impl BoundVarReplacerDelegate<'tcx>, |
512 | ) -> T { | |
a1dfa0c6 | 513 | if !value.has_escaping_bound_vars() { |
fc512014 | 514 | value |
a1dfa0c6 | 515 | } else { |
064997fb | 516 | let mut replacer = BoundVarReplacer::new(self, delegate); |
fc512014 | 517 | value.fold_with(&mut replacer) |
a1dfa0c6 XL |
518 | } |
519 | } | |
520 | ||
9fa01778 | 521 | /// Replaces all types or regions bound by the given `Binder`. The `fld_r` |
923072b8 FG |
522 | /// closure replaces bound regions, the `fld_t` closure replaces bound |
523 | /// types, and `fld_c` replaces bound constants. | |
064997fb | 524 | pub fn replace_bound_vars_uncached<T: TypeFoldable<'tcx>>( |
a1dfa0c6 | 525 | self, |
cdc7bbd5 | 526 | value: Binder<'tcx, T>, |
064997fb FG |
527 | delegate: impl BoundVarReplacerDelegate<'tcx>, |
528 | ) -> T { | |
529 | self.replace_escaping_bound_vars_uncached(value.skip_binder(), delegate) | |
e9174d1e SL |
530 | } |
531 | ||
9fa01778 | 532 | /// Replaces any late-bound regions bound in `value` with |
ff7c6d11 | 533 | /// free variants attached to `all_outlive_scope`. |
cdc7bbd5 XL |
534 | pub fn liberate_late_bound_regions<T>( |
535 | self, | |
536 | all_outlive_scope: DefId, | |
537 | value: ty::Binder<'tcx, T>, | |
538 | ) -> T | |
dfeec247 XL |
539 | where |
540 | T: TypeFoldable<'tcx>, | |
541 | { | |
923072b8 | 542 | self.replace_late_bound_regions_uncached(value, |br| { |
ff7c6d11 XL |
543 | self.mk_region(ty::ReFree(ty::FreeRegion { |
544 | scope: all_outlive_scope, | |
fc512014 | 545 | bound_region: br.kind, |
ff7c6d11 | 546 | })) |
dfeec247 | 547 | }) |
ff7c6d11 XL |
548 | } |
549 | ||
cdc7bbd5 XL |
550 | pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T |
551 | where | |
552 | T: TypeFoldable<'tcx>, | |
553 | { | |
064997fb | 554 | let shift_bv = |bv: ty::BoundVar| ty::BoundVar::from_usize(bv.as_usize() + bound_vars); |
923072b8 | 555 | self.replace_escaping_bound_vars_uncached( |
cdc7bbd5 | 556 | value, |
064997fb | 557 | FnMutDelegate { |
f2b60f7d | 558 | regions: &mut |r: ty::BoundRegion| { |
064997fb | 559 | self.mk_region(ty::ReLateBound( |
cdc7bbd5 | 560 | ty::INNERMOST, |
064997fb FG |
561 | ty::BoundRegion { var: shift_bv(r.var), kind: r.kind }, |
562 | )) | |
563 | }, | |
f2b60f7d | 564 | types: &mut |t: ty::BoundTy| { |
064997fb FG |
565 | self.mk_ty(ty::Bound( |
566 | ty::INNERMOST, | |
567 | ty::BoundTy { var: shift_bv(t.var), kind: t.kind }, | |
568 | )) | |
569 | }, | |
f2b60f7d | 570 | consts: &mut |c, ty: Ty<'tcx>| { |
487cf647 | 571 | self.mk_const(ty::ConstKind::Bound(ty::INNERMOST, shift_bv(c)), ty) |
064997fb | 572 | }, |
cdc7bbd5 XL |
573 | }, |
574 | ) | |
575 | } | |
576 | ||
9fa01778 | 577 | /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also |
e9174d1e | 578 | /// method lookup and a few other places where precise region relationships are not required. |
cdc7bbd5 | 579 | pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T |
dfeec247 XL |
580 | where |
581 | T: TypeFoldable<'tcx>, | |
e9174d1e | 582 | { |
48663c56 | 583 | self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0 |
e9174d1e SL |
584 | } |
585 | ||
9fa01778 | 586 | /// Rewrite any late-bound regions so that they are anonymous. Region numbers are |
29967ef6 | 587 | /// assigned starting at 0 and increasing monotonically in the order traversed |
e9174d1e SL |
588 | /// by the fold operation. |
589 | /// | |
590 | /// The chief purpose of this function is to canonicalize regions so that two | |
591 | /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become | |
9fa01778 | 592 | /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and |
e9174d1e | 593 | /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization. |
cdc7bbd5 | 594 | pub fn anonymize_late_bound_regions<T>(self, sig: Binder<'tcx, T>) -> Binder<'tcx, T> |
dfeec247 XL |
595 | where |
596 | T: TypeFoldable<'tcx>, | |
e9174d1e SL |
597 | { |
598 | let mut counter = 0; | |
cdc7bbd5 XL |
599 | let inner = self |
600 | .replace_late_bound_regions(sig, |_| { | |
601 | let br = ty::BoundRegion { | |
602 | var: ty::BoundVar::from_u32(counter), | |
487cf647 | 603 | kind: ty::BrAnon(counter, None), |
cdc7bbd5 | 604 | }; |
fc512014 | 605 | let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br)); |
dfeec247 | 606 | counter += 1; |
29967ef6 | 607 | r |
dfeec247 | 608 | }) |
cdc7bbd5 XL |
609 | .0; |
610 | let bound_vars = self.mk_bound_variable_kinds( | |
487cf647 | 611 | (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i, None))), |
cdc7bbd5 XL |
612 | ); |
613 | Binder::bind_with_vars(inner, bound_vars) | |
614 | } | |
cdc7bbd5 | 615 | |
064997fb FG |
616 | /// Anonymize all bound variables in `value`, this is mostly used to improve caching. |
617 | pub fn anonymize_bound_vars<T>(self, value: Binder<'tcx, T>) -> Binder<'tcx, T> | |
618 | where | |
619 | T: TypeFoldable<'tcx>, | |
620 | { | |
621 | struct Anonymize<'a, 'tcx> { | |
622 | tcx: TyCtxt<'tcx>, | |
623 | map: &'a mut FxIndexMap<ty::BoundVar, ty::BoundVariableKind>, | |
cdc7bbd5 | 624 | } |
064997fb FG |
625 | impl<'tcx> BoundVarReplacerDelegate<'tcx> for Anonymize<'_, 'tcx> { |
626 | fn replace_region(&mut self, br: ty::BoundRegion) -> ty::Region<'tcx> { | |
627 | let entry = self.map.entry(br.var); | |
628 | let index = entry.index(); | |
629 | let var = ty::BoundVar::from_usize(index); | |
630 | let kind = entry | |
487cf647 FG |
631 | .or_insert_with(|| { |
632 | ty::BoundVariableKind::Region(ty::BrAnon(index as u32, None)) | |
633 | }) | |
064997fb FG |
634 | .expect_region(); |
635 | let br = ty::BoundRegion { var, kind }; | |
636 | self.tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)) | |
cdc7bbd5 | 637 | } |
064997fb FG |
638 | fn replace_ty(&mut self, bt: ty::BoundTy) -> Ty<'tcx> { |
639 | let entry = self.map.entry(bt.var); | |
640 | let index = entry.index(); | |
641 | let var = ty::BoundVar::from_usize(index); | |
642 | let kind = entry | |
643 | .or_insert_with(|| ty::BoundVariableKind::Ty(ty::BoundTyKind::Anon)) | |
644 | .expect_ty(); | |
645 | self.tcx.mk_ty(ty::Bound(ty::INNERMOST, BoundTy { var, kind })) | |
cdc7bbd5 | 646 | } |
064997fb FG |
647 | fn replace_const(&mut self, bv: ty::BoundVar, ty: Ty<'tcx>) -> ty::Const<'tcx> { |
648 | let entry = self.map.entry(bv); | |
649 | let index = entry.index(); | |
650 | let var = ty::BoundVar::from_usize(index); | |
651 | let () = entry.or_insert_with(|| ty::BoundVariableKind::Const).expect_const(); | |
487cf647 | 652 | self.tcx.mk_const(ty::ConstKind::Bound(ty::INNERMOST, var), ty) |
064997fb FG |
653 | } |
654 | } | |
cdc7bbd5 | 655 | |
064997fb FG |
656 | let mut map = Default::default(); |
657 | let delegate = Anonymize { tcx: self, map: &mut map }; | |
658 | let inner = self.replace_escaping_bound_vars_uncached(value.skip_binder(), delegate); | |
659 | let bound_vars = self.mk_bound_variable_kinds(map.into_values()); | |
660 | Binder::bind_with_vars(inner, bound_vars) | |
e9174d1e SL |
661 | } |
662 | } | |
663 | ||
a1dfa0c6 XL |
664 | /////////////////////////////////////////////////////////////////////////// |
665 | // Shifter | |
666 | // | |
667 | // Shifts the De Bruijn indices on all escaping bound vars by a | |
668 | // fixed amount. Useful in substitution or when otherwise introducing | |
669 | // a binding level that is not intended to capture the existing bound | |
670 | // vars. See comment on `shift_vars_through_binders` method in | |
671 | // `subst.rs` for more details. | |
672 | ||
dc9dc135 XL |
673 | struct Shifter<'tcx> { |
674 | tcx: TyCtxt<'tcx>, | |
a1dfa0c6 XL |
675 | current_index: ty::DebruijnIndex, |
676 | amount: u32, | |
a1dfa0c6 XL |
677 | } |
678 | ||
a2a8927a | 679 | impl<'tcx> Shifter<'tcx> { |
29967ef6 XL |
680 | pub fn new(tcx: TyCtxt<'tcx>, amount: u32) -> Self { |
681 | Shifter { tcx, current_index: ty::INNERMOST, amount } | |
e9174d1e SL |
682 | } |
683 | } | |
684 | ||
a2a8927a | 685 | impl<'tcx> TypeFolder<'tcx> for Shifter<'tcx> { |
dc9dc135 XL |
686 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { |
687 | self.tcx | |
dfeec247 | 688 | } |
e9174d1e | 689 | |
cdc7bbd5 XL |
690 | fn fold_binder<T: TypeFoldable<'tcx>>( |
691 | &mut self, | |
692 | t: ty::Binder<'tcx, T>, | |
693 | ) -> ty::Binder<'tcx, T> { | |
94b46f34 | 694 | self.current_index.shift_in(1); |
54a0048b | 695 | let t = t.super_fold_with(self); |
94b46f34 | 696 | self.current_index.shift_out(1); |
54a0048b | 697 | t |
e9174d1e SL |
698 | } |
699 | ||
7cac9316 | 700 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 701 | match *r { |
487cf647 FG |
702 | ty::ReLateBound(debruijn, br) if debruijn >= self.current_index => { |
703 | let debruijn = debruijn.shifted_in(self.amount); | |
704 | let shifted = ty::ReLateBound(debruijn, br); | |
705 | self.tcx.mk_region(shifted) | |
e9174d1e | 706 | } |
dfeec247 | 707 | _ => r, |
e9174d1e SL |
708 | } |
709 | } | |
e9174d1e | 710 | |
48663c56 | 711 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { |
1b1a35ee | 712 | match *ty.kind() { |
487cf647 FG |
713 | ty::Bound(debruijn, bound_ty) if debruijn >= self.current_index => { |
714 | let debruijn = debruijn.shifted_in(self.amount); | |
715 | self.tcx.mk_ty(ty::Bound(debruijn, bound_ty)) | |
a1dfa0c6 | 716 | } |
e9174d1e | 717 | |
487cf647 FG |
718 | _ if ty.has_vars_bound_at_or_above(self.current_index) => ty.super_fold_with(self), |
719 | _ => ty, | |
e9174d1e SL |
720 | } |
721 | } | |
48663c56 | 722 | |
5099ac24 | 723 | fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> { |
487cf647 FG |
724 | if let ty::ConstKind::Bound(debruijn, bound_ct) = ct.kind() |
725 | && debruijn >= self.current_index | |
726 | { | |
727 | let debruijn = debruijn.shifted_in(self.amount); | |
728 | self.tcx.mk_const(ty::ConstKind::Bound(debruijn, bound_ct), ct.ty()) | |
48663c56 XL |
729 | } else { |
730 | ct.super_fold_with(self) | |
731 | } | |
732 | } | |
487cf647 FG |
733 | |
734 | fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { | |
735 | if p.has_vars_bound_at_or_above(self.current_index) { p.super_fold_with(self) } else { p } | |
736 | } | |
e9174d1e SL |
737 | } |
738 | ||
dc9dc135 XL |
739 | pub fn shift_region<'tcx>( |
740 | tcx: TyCtxt<'tcx>, | |
7cac9316 | 741 | region: ty::Region<'tcx>, |
dc9dc135 | 742 | amount: u32, |
a1dfa0c6 | 743 | ) -> ty::Region<'tcx> { |
5099ac24 | 744 | match *region { |
a1dfa0c6 | 745 | ty::ReLateBound(debruijn, br) if amount > 0 => { |
5099ac24 | 746 | tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), br)) |
cc61c64b | 747 | } |
dfeec247 | 748 | _ => region, |
cc61c64b XL |
749 | } |
750 | } | |
751 | ||
fc512014 | 752 | pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T |
dc9dc135 XL |
753 | where |
754 | T: TypeFoldable<'tcx>, | |
755 | { | |
dfeec247 | 756 | debug!("shift_vars(value={:?}, amount={})", value, amount); |
a1dfa0c6 | 757 | |
487cf647 FG |
758 | if amount == 0 || !value.has_escaping_bound_vars() { |
759 | return value; | |
760 | } | |
761 | ||
29967ef6 | 762 | value.fold_with(&mut Shifter::new(tcx, amount)) |
e9174d1e | 763 | } |