]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
11 | //! Generalized type folding mechanism. The setup is a bit convoluted | |
12 | //! but allows for convenient usage. Let T be an instance of some | |
13 | //! "foldable type" (one which implements `TypeFoldable`) and F be an | |
14 | //! instance of a "folder" (a type which implements `TypeFolder`). Then | |
15 | //! the setup is intended to be: | |
16 | //! | |
9cc50fc6 | 17 | //! T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F) |
e9174d1e SL |
18 | //! |
19 | //! This way, when you define a new folder F, you can override | |
9cc50fc6 | 20 | //! `fold_T()` to customize the behavior, and invoke `T.super_fold_with()` |
e9174d1e SL |
21 | //! to get the original behavior. Meanwhile, to actually fold |
22 | //! something, you can just write `T.fold_with(F)`, which is | |
23 | //! convenient. (Note that `fold_with` will also transparently handle | |
24 | //! things like a `Vec<T>` where T is foldable and so on.) | |
25 | //! | |
26 | //! In this ideal setup, the only function that actually *does* | |
9cc50fc6 SL |
27 | //! anything is `T.super_fold_with()`, which traverses the type `T`. |
28 | //! Moreover, `T.super_fold_with()` should only ever call `T.fold_with()`. | |
e9174d1e SL |
29 | //! |
30 | //! In some cases, we follow a degenerate pattern where we do not have | |
9cc50fc6 SL |
31 | //! a `fold_T` method. Instead, `T.fold_with` traverses the structure directly. |
32 | //! This is suboptimal because the behavior cannot be overridden, but it's | |
33 | //! much less work to implement. If you ever *do* need an override that | |
34 | //! doesn't exist, it's not hard to convert the degenerate pattern into the | |
35 | //! proper thing. | |
36 | //! | |
37 | //! A `TypeFoldable` T can also be visited by a `TypeVisitor` V using similar setup: | |
38 | //! T.visit_with(V) --calls--> V.visit_T(T) --calls--> T.super_visit_with(V). | |
39 | //! These methods return true to indicate that the visitor has found what it is looking for | |
40 | //! and does not need to visit anything else. | |
e9174d1e | 41 | |
ea8adc8c | 42 | use middle::const_val::ConstVal; |
ff7c6d11 | 43 | use hir::def_id::DefId; |
54a0048b | 44 | use ty::{self, Binder, Ty, TyCtxt, TypeFlags}; |
e9174d1e | 45 | |
94b46f34 | 46 | use std::collections::BTreeMap; |
e9174d1e | 47 | use std::fmt; |
abe05a73 | 48 | use util::nodemap::FxHashSet; |
e9174d1e | 49 | |
e9174d1e SL |
50 | /// The TypeFoldable trait is implemented for every type that can be folded. |
51 | /// Basically, every type that has a corresponding method in TypeFolder. | |
0531ce1d XL |
52 | /// |
53 | /// To implement this conveniently, use the | |
54 | /// `BraceStructTypeFoldableImpl` etc macros found in `macros.rs`. | |
e9174d1e | 55 | pub trait TypeFoldable<'tcx>: fmt::Debug + Clone { |
a7813a04 XL |
56 | fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self; |
57 | fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self { | |
9cc50fc6 SL |
58 | self.super_fold_with(folder) |
59 | } | |
60 | ||
61 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool; | |
62 | fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool { | |
63 | self.super_visit_with(visitor) | |
64 | } | |
65 | ||
94b46f34 XL |
66 | /// True if `self` has any late-bound regions that are either |
67 | /// bound by `binder` or bound by some binder outside of `binder`. | |
68 | /// If `binder` is `ty::INNERMOST`, this indicates whether | |
69 | /// there are any late-bound regions that appear free. | |
70 | fn has_regions_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool { | |
71 | self.visit_with(&mut HasEscapingRegionsVisitor { outer_index: binder }) | |
9cc50fc6 | 72 | } |
94b46f34 XL |
73 | |
74 | /// True if this `self` has any regions that escape `binder` (and | |
75 | /// hence are not bound by it). | |
76 | fn has_regions_bound_above(&self, binder: ty::DebruijnIndex) -> bool { | |
77 | self.has_regions_bound_at_or_above(binder.shifted_in(1)) | |
78 | } | |
79 | ||
9cc50fc6 | 80 | fn has_escaping_regions(&self) -> bool { |
94b46f34 | 81 | self.has_regions_bound_at_or_above(ty::INNERMOST) |
9cc50fc6 SL |
82 | } |
83 | ||
84 | fn has_type_flags(&self, flags: TypeFlags) -> bool { | |
85 | self.visit_with(&mut HasTypeFlagsVisitor { flags: flags }) | |
86 | } | |
ea8adc8c | 87 | fn has_projections(&self) -> bool { |
9cc50fc6 SL |
88 | self.has_type_flags(TypeFlags::HAS_PROJECTION) |
89 | } | |
90 | fn references_error(&self) -> bool { | |
91 | self.has_type_flags(TypeFlags::HAS_TY_ERR) | |
92 | } | |
93 | fn has_param_types(&self) -> bool { | |
94 | self.has_type_flags(TypeFlags::HAS_PARAMS) | |
95 | } | |
96 | fn has_self_ty(&self) -> bool { | |
97 | self.has_type_flags(TypeFlags::HAS_SELF) | |
98 | } | |
99 | fn has_infer_types(&self) -> bool { | |
100 | self.has_type_flags(TypeFlags::HAS_TY_INFER) | |
101 | } | |
102 | fn needs_infer(&self) -> bool { | |
103 | self.has_type_flags(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER) | |
104 | } | |
83c7162d XL |
105 | fn has_skol(&self) -> bool { |
106 | self.has_type_flags(TypeFlags::HAS_RE_SKOL) | |
107 | } | |
9cc50fc6 SL |
108 | fn needs_subst(&self) -> bool { |
109 | self.has_type_flags(TypeFlags::NEEDS_SUBST) | |
110 | } | |
c30ab7b3 SL |
111 | fn has_re_skol(&self) -> bool { |
112 | self.has_type_flags(TypeFlags::HAS_RE_SKOL) | |
113 | } | |
9cc50fc6 SL |
114 | fn has_closure_types(&self) -> bool { |
115 | self.has_type_flags(TypeFlags::HAS_TY_CLOSURE) | |
116 | } | |
ff7c6d11 XL |
117 | /// "Free" regions in this context means that it has any region |
118 | /// that is not (a) erased or (b) late-bound. | |
119 | fn has_free_regions(&self) -> bool { | |
120 | self.has_type_flags(TypeFlags::HAS_FREE_REGIONS) | |
121 | } | |
122 | ||
123 | /// True if there any any un-erased free regions. | |
9cc50fc6 | 124 | fn has_erasable_regions(&self) -> bool { |
ff7c6d11 | 125 | self.has_type_flags(TypeFlags::HAS_FREE_REGIONS) |
9cc50fc6 | 126 | } |
ff7c6d11 | 127 | |
9cc50fc6 SL |
128 | /// Indicates whether this value references only 'global' |
129 | /// types/lifetimes that are the same regardless of what fn we are | |
94b46f34 | 130 | /// in. This is used for caching. |
9cc50fc6 | 131 | fn is_global(&self) -> bool { |
94b46f34 XL |
132 | !self.has_type_flags(TypeFlags::HAS_FREE_LOCAL_NAMES) |
133 | } | |
134 | ||
135 | /// True if there are any late-bound regions | |
136 | fn has_late_bound_regions(&self) -> bool { | |
137 | self.has_type_flags(TypeFlags::HAS_RE_LATE_BOUND) | |
9cc50fc6 | 138 | } |
e9174d1e SL |
139 | } |
140 | ||
141 | /// The TypeFolder trait defines the actual *folding*. There is a | |
142 | /// method defined for every foldable type. Each of these has a | |
143 | /// default implementation that does an "identity" fold. Within each | |
144 | /// identity fold, it should invoke `foo.fold_with(self)` to fold each | |
145 | /// sub-item. | |
a7813a04 XL |
146 | pub trait TypeFolder<'gcx: 'tcx, 'tcx> : Sized { |
147 | fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx>; | |
e9174d1e SL |
148 | |
149 | fn fold_binder<T>(&mut self, t: &Binder<T>) -> Binder<T> | |
150 | where T : TypeFoldable<'tcx> | |
151 | { | |
9cc50fc6 | 152 | t.super_fold_with(self) |
e9174d1e SL |
153 | } |
154 | ||
155 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
9cc50fc6 | 156 | t.super_fold_with(self) |
e9174d1e SL |
157 | } |
158 | ||
7cac9316 | 159 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9cc50fc6 | 160 | r.super_fold_with(self) |
e9174d1e | 161 | } |
ea8adc8c XL |
162 | |
163 | fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { | |
164 | c.super_fold_with(self) | |
165 | } | |
e9174d1e SL |
166 | } |
167 | ||
9cc50fc6 | 168 | pub trait TypeVisitor<'tcx> : Sized { |
54a0048b SL |
169 | fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool { |
170 | t.super_visit_with(self) | |
171 | } | |
e9174d1e | 172 | |
9cc50fc6 SL |
173 | fn visit_ty(&mut self, t: Ty<'tcx>) -> bool { |
174 | t.super_visit_with(self) | |
e9174d1e | 175 | } |
e9174d1e | 176 | |
7cac9316 | 177 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool { |
9cc50fc6 | 178 | r.super_visit_with(self) |
e9174d1e | 179 | } |
ea8adc8c XL |
180 | |
181 | fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool { | |
182 | c.super_visit_with(self) | |
183 | } | |
e9174d1e SL |
184 | } |
185 | ||
186 | /////////////////////////////////////////////////////////////////////////// | |
187 | // Some sample folders | |
188 | ||
a7813a04 XL |
189 | pub struct BottomUpFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a, F> |
190 | where F: FnMut(Ty<'tcx>) -> Ty<'tcx> | |
191 | { | |
192 | pub tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
e9174d1e SL |
193 | pub fldop: F, |
194 | } | |
195 | ||
a7813a04 XL |
196 | impl<'a, 'gcx, 'tcx, F> TypeFolder<'gcx, 'tcx> for BottomUpFolder<'a, 'gcx, 'tcx, F> |
197 | where F: FnMut(Ty<'tcx>) -> Ty<'tcx>, | |
e9174d1e | 198 | { |
a7813a04 | 199 | fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx } |
e9174d1e SL |
200 | |
201 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
9cc50fc6 | 202 | let t1 = ty.super_fold_with(self); |
e9174d1e SL |
203 | (self.fldop)(t1) |
204 | } | |
205 | } | |
206 | ||
207 | /////////////////////////////////////////////////////////////////////////// | |
208 | // Region folder | |
209 | ||
a7813a04 | 210 | impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { |
e9174d1e SL |
211 | /// Collects the free and escaping regions in `value` into `region_set`. Returns |
212 | /// whether any late-bound regions were skipped | |
a7813a04 | 213 | pub fn collect_regions<T>(self, |
e9174d1e | 214 | value: &T, |
7cac9316 | 215 | region_set: &mut FxHashSet<ty::Region<'tcx>>) |
e9174d1e SL |
216 | -> bool |
217 | where T : TypeFoldable<'tcx> | |
218 | { | |
219 | let mut have_bound_regions = false; | |
9e0c209e | 220 | self.fold_regions(value, &mut have_bound_regions, |r, d| { |
94b46f34 | 221 | region_set.insert(self.mk_region(r.shifted_out_to_binder(d))); |
9e0c209e SL |
222 | r |
223 | }); | |
e9174d1e SL |
224 | have_bound_regions |
225 | } | |
226 | ||
227 | /// Folds the escaping and free regions in `value` using `f`, and | |
228 | /// sets `skipped_regions` to true if any late-bound region was found | |
229 | /// and skipped. | |
94b46f34 XL |
230 | pub fn fold_regions<T>( |
231 | self, | |
e9174d1e SL |
232 | value: &T, |
233 | skipped_regions: &mut bool, | |
94b46f34 XL |
234 | mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, |
235 | ) -> T | |
236 | where | |
237 | T : TypeFoldable<'tcx>, | |
e9174d1e SL |
238 | { |
239 | value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f)) | |
240 | } | |
abe05a73 XL |
241 | |
242 | pub fn for_each_free_region<T,F>(self, | |
243 | value: &T, | |
244 | callback: F) | |
245 | where F: FnMut(ty::Region<'tcx>), | |
246 | T: TypeFoldable<'tcx>, | |
247 | { | |
94b46f34 XL |
248 | value.visit_with(&mut RegionVisitor { |
249 | outer_index: ty::INNERMOST, | |
250 | callback | |
251 | }); | |
abe05a73 XL |
252 | |
253 | struct RegionVisitor<F> { | |
94b46f34 XL |
254 | /// The index of a binder *just outside* the things we have |
255 | /// traversed. If we encounter a bound region bound by this | |
256 | /// binder or one outer to it, it appears free. Example: | |
257 | /// | |
258 | /// ``` | |
259 | /// for<'a> fn(for<'b> fn(), T) | |
260 | /// ^ ^ ^ ^ | |
261 | /// | | | | here, would be shifted in 1 | |
262 | /// | | | here, would be shifted in 2 | |
263 | /// | | here, would be INNERMOST shifted in by 1 | |
264 | /// | here, initially, binder would be INNERMOST | |
265 | /// ``` | |
266 | /// | |
267 | /// You see that, initially, *any* bound value is free, | |
268 | /// because we've not traversed any binders. As we pass | |
269 | /// through a binder, we shift the `outer_index` by 1 to | |
270 | /// account for the new binder that encloses us. | |
271 | outer_index: ty::DebruijnIndex, | |
abe05a73 XL |
272 | callback: F, |
273 | } | |
274 | ||
275 | impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<F> | |
276 | where F : FnMut(ty::Region<'tcx>) | |
277 | { | |
278 | fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool { | |
94b46f34 | 279 | self.outer_index.shift_in(1); |
abe05a73 | 280 | t.skip_binder().visit_with(self); |
94b46f34 | 281 | self.outer_index.shift_out(1); |
abe05a73 XL |
282 | |
283 | false // keep visiting | |
284 | } | |
285 | ||
286 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool { | |
287 | match *r { | |
94b46f34 | 288 | ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => { |
abe05a73 XL |
289 | /* ignore bound regions */ |
290 | } | |
291 | _ => (self.callback)(r), | |
292 | } | |
293 | ||
294 | false // keep visiting | |
295 | } | |
296 | } | |
297 | } | |
e9174d1e SL |
298 | } |
299 | ||
300 | /// Folds over the substructure of a type, visiting its component | |
301 | /// types and all regions that occur *free* within it. | |
302 | /// | |
303 | /// That is, `Ty` can contain function or method types that bind | |
304 | /// regions at the call site (`ReLateBound`), and occurrences of | |
305 | /// regions (aka "lifetimes") that are bound within a type are not | |
306 | /// visited by this folder; only regions that occur free will be | |
307 | /// visited by `fld_r`. | |
308 | ||
a7813a04 XL |
309 | pub struct RegionFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { |
310 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
e9174d1e | 311 | skipped_regions: &'a mut bool, |
94b46f34 XL |
312 | |
313 | /// Stores the index of a binder *just outside* the stuff we have | |
314 | /// visited. So this begins as INNERMOST; when we pass through a | |
315 | /// binder, it is incremented (via `shift_in`). | |
316 | current_index: ty::DebruijnIndex, | |
317 | ||
318 | /// Callback invokes for each free region. The `DebruijnIndex` | |
319 | /// points to the binder *just outside* the ones we have passed | |
320 | /// through. | |
321 | fold_region_fn: &'a mut (dyn FnMut( | |
322 | ty::Region<'tcx>, | |
323 | ty::DebruijnIndex, | |
324 | ) -> ty::Region<'tcx> + 'a), | |
e9174d1e SL |
325 | } |
326 | ||
a7813a04 | 327 | impl<'a, 'gcx, 'tcx> RegionFolder<'a, 'gcx, 'tcx> { |
94b46f34 XL |
328 | pub fn new( |
329 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
330 | skipped_regions: &'a mut bool, | |
331 | fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, | |
332 | ) -> RegionFolder<'a, 'gcx, 'tcx> { | |
e9174d1e | 333 | RegionFolder { |
041b39d2 XL |
334 | tcx, |
335 | skipped_regions, | |
94b46f34 XL |
336 | current_index: ty::INNERMOST, |
337 | fold_region_fn, | |
e9174d1e SL |
338 | } |
339 | } | |
340 | } | |
341 | ||
a7813a04 XL |
342 | impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFolder<'a, 'gcx, 'tcx> { |
343 | fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx } | |
e9174d1e | 344 | |
54a0048b | 345 | fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> { |
94b46f34 | 346 | self.current_index.shift_in(1); |
54a0048b | 347 | let t = t.super_fold_with(self); |
94b46f34 | 348 | self.current_index.shift_out(1); |
54a0048b | 349 | t |
e9174d1e SL |
350 | } |
351 | ||
7cac9316 | 352 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 353 | match *r { |
94b46f34 XL |
354 | ty::ReLateBound(debruijn, _) if debruijn < self.current_index => { |
355 | debug!("RegionFolder.fold_region({:?}) skipped bound region (current index={:?})", | |
356 | r, self.current_index); | |
e9174d1e SL |
357 | *self.skipped_regions = true; |
358 | r | |
359 | } | |
360 | _ => { | |
94b46f34 XL |
361 | debug!("RegionFolder.fold_region({:?}) folding free region (current_index={:?})", |
362 | r, self.current_index); | |
363 | (self.fold_region_fn)(r, self.current_index) | |
e9174d1e SL |
364 | } |
365 | } | |
366 | } | |
367 | } | |
368 | ||
369 | /////////////////////////////////////////////////////////////////////////// | |
370 | // Late-bound region replacer | |
371 | ||
372 | // Replaces the escaping regions in a type. | |
373 | ||
a7813a04 XL |
374 | struct RegionReplacer<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { |
375 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
94b46f34 XL |
376 | |
377 | /// As with `RegionFolder`, represents the index of a binder *just outside* | |
378 | /// the ones we have visited. | |
379 | current_index: ty::DebruijnIndex, | |
380 | ||
0531ce1d | 381 | fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a), |
94b46f34 | 382 | map: BTreeMap<ty::BoundRegion, ty::Region<'tcx>> |
e9174d1e SL |
383 | } |
384 | ||
a7813a04 | 385 | impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> { |
ff7c6d11 XL |
386 | /// Replace all regions bound by the given `Binder` with the |
387 | /// results returned by the closure; the closure is expected to | |
388 | /// return a free region (relative to this binder), and hence the | |
389 | /// binder is removed in the return type. The closure is invoked | |
390 | /// once for each unique `BoundRegion`; multiple references to the | |
391 | /// same `BoundRegion` will reuse the previous result. A map is | |
392 | /// returned at the end with each bound region and the free region | |
393 | /// that replaced it. | |
a7813a04 | 394 | pub fn replace_late_bound_regions<T,F>(self, |
e9174d1e SL |
395 | value: &Binder<T>, |
396 | mut f: F) | |
94b46f34 | 397 | -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>) |
7cac9316 | 398 | where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx>, |
e9174d1e SL |
399 | T : TypeFoldable<'tcx>, |
400 | { | |
e9174d1e SL |
401 | let mut replacer = RegionReplacer::new(self, &mut f); |
402 | let result = value.skip_binder().fold_with(&mut replacer); | |
403 | (result, replacer.map) | |
404 | } | |
405 | ||
ff7c6d11 XL |
406 | /// Replace any late-bound regions bound in `value` with |
407 | /// free variants attached to `all_outlive_scope`. | |
408 | pub fn liberate_late_bound_regions<T>( | |
409 | &self, | |
410 | all_outlive_scope: DefId, | |
411 | value: &ty::Binder<T> | |
412 | ) -> T | |
413 | where T: TypeFoldable<'tcx> { | |
414 | self.replace_late_bound_regions(value, |br| { | |
415 | self.mk_region(ty::ReFree(ty::FreeRegion { | |
416 | scope: all_outlive_scope, | |
417 | bound_region: br | |
418 | })) | |
419 | }).0 | |
420 | } | |
421 | ||
94b46f34 | 422 | /// Flattens multiple binding levels into one. So `for<'a> for<'b> Foo` |
e9174d1e | 423 | /// becomes `for<'a,'b> Foo`. |
a7813a04 | 424 | pub fn flatten_late_bound_regions<T>(self, bound2_value: &Binder<Binder<T>>) |
e9174d1e SL |
425 | -> Binder<T> |
426 | where T: TypeFoldable<'tcx> | |
427 | { | |
428 | let bound0_value = bound2_value.skip_binder().skip_binder(); | |
94b46f34 | 429 | let value = self.fold_regions(bound0_value, &mut false, |region, current_depth| { |
9e0c209e | 430 | match *region { |
94b46f34 XL |
431 | ty::ReLateBound(debruijn, br) => { |
432 | // We assume no regions bound *outside* of the | |
433 | // binders in `bound2_value` (nmatsakis added in | |
434 | // the course of this PR; seems like a reasonable | |
435 | // sanity check though). | |
436 | assert!(debruijn == current_depth); | |
437 | self.mk_region(ty::ReLateBound(current_depth, br)) | |
e9174d1e SL |
438 | } |
439 | _ => { | |
440 | region | |
441 | } | |
442 | } | |
443 | }); | |
83c7162d | 444 | Binder::bind(value) |
e9174d1e SL |
445 | } |
446 | ||
a7813a04 XL |
447 | /// Returns a set of all late-bound regions that are constrained |
448 | /// by `value`, meaning that if we instantiate those LBR with | |
449 | /// variables and equate `value` with something else, those | |
450 | /// variables will also be equated. | |
451 | pub fn collect_constrained_late_bound_regions<T>(&self, value: &Binder<T>) | |
476ff2be | 452 | -> FxHashSet<ty::BoundRegion> |
a7813a04 XL |
453 | where T : TypeFoldable<'tcx> |
454 | { | |
455 | self.collect_late_bound_regions(value, true) | |
456 | } | |
457 | ||
458 | /// Returns a set of all late-bound regions that appear in `value` anywhere. | |
459 | pub fn collect_referenced_late_bound_regions<T>(&self, value: &Binder<T>) | |
476ff2be | 460 | -> FxHashSet<ty::BoundRegion> |
a7813a04 XL |
461 | where T : TypeFoldable<'tcx> |
462 | { | |
463 | self.collect_late_bound_regions(value, false) | |
464 | } | |
465 | ||
466 | fn collect_late_bound_regions<T>(&self, value: &Binder<T>, just_constraint: bool) | |
476ff2be | 467 | -> FxHashSet<ty::BoundRegion> |
a7813a04 XL |
468 | where T : TypeFoldable<'tcx> |
469 | { | |
470 | let mut collector = LateBoundRegionsCollector::new(just_constraint); | |
471 | let result = value.skip_binder().visit_with(&mut collector); | |
472 | assert!(!result); // should never have stopped early | |
473 | collector.regions | |
474 | } | |
475 | ||
94b46f34 | 476 | /// Replace any late-bound regions bound in `value` with `'erased`. Useful in codegen but also |
e9174d1e | 477 | /// method lookup and a few other places where precise region relationships are not required. |
a7813a04 | 478 | pub fn erase_late_bound_regions<T>(self, value: &Binder<T>) -> T |
e9174d1e SL |
479 | where T : TypeFoldable<'tcx> |
480 | { | |
cc61c64b | 481 | self.replace_late_bound_regions(value, |_| self.types.re_erased).0 |
e9174d1e SL |
482 | } |
483 | ||
484 | /// Rewrite any late-bound regions so that they are anonymous. Region numbers are | |
485 | /// assigned starting at 1 and increasing monotonically in the order traversed | |
486 | /// by the fold operation. | |
487 | /// | |
488 | /// The chief purpose of this function is to canonicalize regions so that two | |
489 | /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become | |
490 | /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and | |
491 | /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization. | |
a7813a04 | 492 | pub fn anonymize_late_bound_regions<T>(self, sig: &Binder<T>) -> Binder<T> |
e9174d1e SL |
493 | where T : TypeFoldable<'tcx>, |
494 | { | |
495 | let mut counter = 0; | |
83c7162d | 496 | Binder::bind(self.replace_late_bound_regions(sig, |_| { |
e9174d1e | 497 | counter += 1; |
94b46f34 | 498 | self.mk_region(ty::ReLateBound(ty::INNERMOST, ty::BrAnon(counter))) |
e9174d1e SL |
499 | }).0) |
500 | } | |
501 | } | |
502 | ||
a7813a04 XL |
503 | impl<'a, 'gcx, 'tcx> RegionReplacer<'a, 'gcx, 'tcx> { |
504 | fn new<F>(tcx: TyCtxt<'a, 'gcx, 'tcx>, fld_r: &'a mut F) | |
505 | -> RegionReplacer<'a, 'gcx, 'tcx> | |
7cac9316 | 506 | where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx> |
e9174d1e SL |
507 | { |
508 | RegionReplacer { | |
041b39d2 | 509 | tcx, |
94b46f34 | 510 | current_index: ty::INNERMOST, |
041b39d2 | 511 | fld_r, |
94b46f34 | 512 | map: BTreeMap::default() |
e9174d1e SL |
513 | } |
514 | } | |
515 | } | |
516 | ||
a7813a04 XL |
517 | impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> { |
518 | fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx } | |
e9174d1e | 519 | |
54a0048b | 520 | fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> { |
94b46f34 | 521 | self.current_index.shift_in(1); |
54a0048b | 522 | let t = t.super_fold_with(self); |
94b46f34 | 523 | self.current_index.shift_out(1); |
54a0048b | 524 | t |
e9174d1e SL |
525 | } |
526 | ||
527 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
94b46f34 | 528 | if !t.has_regions_bound_at_or_above(self.current_index) { |
e9174d1e SL |
529 | return t; |
530 | } | |
531 | ||
9cc50fc6 | 532 | t.super_fold_with(self) |
e9174d1e SL |
533 | } |
534 | ||
7cac9316 | 535 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 536 | match *r { |
94b46f34 | 537 | ty::ReLateBound(debruijn, br) if debruijn == self.current_index => { |
e9174d1e SL |
538 | let fld_r = &mut self.fld_r; |
539 | let region = *self.map.entry(br).or_insert_with(|| fld_r(br)); | |
9e0c209e | 540 | if let ty::ReLateBound(debruijn1, br) = *region { |
e9174d1e | 541 | // If the callback returns a late-bound region, |
94b46f34 XL |
542 | // that region should always use the INNERMOST |
543 | // debruijn index. Then we adjust it to the | |
544 | // correct depth. | |
545 | assert_eq!(debruijn1, ty::INNERMOST); | |
9e0c209e | 546 | self.tcx.mk_region(ty::ReLateBound(debruijn, br)) |
e9174d1e SL |
547 | } else { |
548 | region | |
549 | } | |
550 | } | |
9e0c209e | 551 | _ => r |
e9174d1e SL |
552 | } |
553 | } | |
554 | } | |
555 | ||
e9174d1e SL |
556 | /////////////////////////////////////////////////////////////////////////// |
557 | // Region shifter | |
558 | // | |
559 | // Shifts the De Bruijn indices on all escaping bound regions by a | |
560 | // fixed amount. Useful in substitution or when otherwise introducing | |
561 | // a binding level that is not intended to capture the existing bound | |
562 | // regions. See comment on `shift_regions_through_binders` method in | |
563 | // `subst.rs` for more details. | |
564 | ||
7cac9316 | 565 | pub fn shift_region(region: ty::RegionKind, amount: u32) -> ty::RegionKind { |
e9174d1e SL |
566 | match region { |
567 | ty::ReLateBound(debruijn, br) => { | |
94b46f34 | 568 | ty::ReLateBound(debruijn.shifted_in(amount), br) |
e9174d1e SL |
569 | } |
570 | _ => { | |
571 | region | |
572 | } | |
573 | } | |
574 | } | |
575 | ||
cc61c64b XL |
576 | pub fn shift_region_ref<'a, 'gcx, 'tcx>( |
577 | tcx: TyCtxt<'a, 'gcx, 'tcx>, | |
7cac9316 | 578 | region: ty::Region<'tcx>, |
cc61c64b | 579 | amount: u32) |
7cac9316 | 580 | -> ty::Region<'tcx> |
cc61c64b XL |
581 | { |
582 | match region { | |
583 | &ty::ReLateBound(debruijn, br) if amount > 0 => { | |
94b46f34 | 584 | tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), br)) |
cc61c64b XL |
585 | } |
586 | _ => { | |
587 | region | |
588 | } | |
589 | } | |
590 | } | |
591 | ||
a7813a04 | 592 | pub fn shift_regions<'a, 'gcx, 'tcx, T>(tcx: TyCtxt<'a, 'gcx, 'tcx>, |
7cac9316 XL |
593 | amount: u32, |
594 | value: &T) -> T | |
a7813a04 XL |
595 | where T: TypeFoldable<'tcx> |
596 | { | |
e9174d1e SL |
597 | debug!("shift_regions(value={:?}, amount={})", |
598 | value, amount); | |
599 | ||
600 | value.fold_with(&mut RegionFolder::new(tcx, &mut false, &mut |region, _current_depth| { | |
cc61c64b | 601 | shift_region_ref(tcx, region, amount) |
e9174d1e SL |
602 | })) |
603 | } | |
9cc50fc6 SL |
604 | |
605 | /// An "escaping region" is a bound region whose binder is not part of `t`. | |
606 | /// | |
607 | /// So, for example, consider a type like the following, which has two binders: | |
608 | /// | |
609 | /// for<'a> fn(x: for<'b> fn(&'a isize, &'b isize)) | |
610 | /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope | |
611 | /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ inner scope | |
612 | /// | |
613 | /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the | |
614 | /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner | |
615 | /// fn type*, that type has an escaping region: `'a`. | |
616 | /// | |
617 | /// Note that what I'm calling an "escaping region" is often just called a "free region". However, | |
618 | /// we already use the term "free region". It refers to the regions that we use to represent bound | |
619 | /// regions on a fn definition while we are typechecking its body. | |
620 | /// | |
621 | /// To clarify, conceptually there is no particular difference between an "escaping" region and a | |
622 | /// "free" region. However, there is a big difference in practice. Basically, when "entering" a | |
623 | /// binding level, one is generally required to do some sort of processing to a bound region, such | |
624 | /// as replacing it with a fresh/skolemized region, or making an entry in the environment to | |
625 | /// represent the scope to which it is attached, etc. An escaping region represents a bound region | |
626 | /// for which this processing has not yet been done. | |
627 | struct HasEscapingRegionsVisitor { | |
94b46f34 XL |
628 | /// Anything bound by `outer_index` or "above" is escaping |
629 | outer_index: ty::DebruijnIndex, | |
9cc50fc6 SL |
630 | } |
631 | ||
632 | impl<'tcx> TypeVisitor<'tcx> for HasEscapingRegionsVisitor { | |
54a0048b | 633 | fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool { |
94b46f34 | 634 | self.outer_index.shift_in(1); |
54a0048b | 635 | let result = t.super_visit_with(self); |
94b46f34 | 636 | self.outer_index.shift_out(1); |
54a0048b | 637 | result |
9cc50fc6 SL |
638 | } |
639 | ||
640 | fn visit_ty(&mut self, t: Ty<'tcx>) -> bool { | |
94b46f34 XL |
641 | // If the outer-exclusive-binder is *strictly greater* than |
642 | // `outer_index`, that means that `t` contains some content | |
643 | // bound at `outer_index` or above (because | |
644 | // `outer_exclusive_binder` is always 1 higher than the | |
645 | // content in `t`). Therefore, `t` has some escaping regions. | |
646 | t.outer_exclusive_binder > self.outer_index | |
9cc50fc6 SL |
647 | } |
648 | ||
7cac9316 | 649 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool { |
94b46f34 XL |
650 | // If the region is bound by `outer_index` or anything outside |
651 | // of outer index, then it escapes the binders we have | |
652 | // visited. | |
653 | r.bound_at_or_above_binder(self.outer_index) | |
9cc50fc6 SL |
654 | } |
655 | } | |
656 | ||
657 | struct HasTypeFlagsVisitor { | |
658 | flags: ty::TypeFlags, | |
659 | } | |
660 | ||
661 | impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor { | |
662 | fn visit_ty(&mut self, t: Ty) -> bool { | |
7cac9316 XL |
663 | debug!("HasTypeFlagsVisitor: t={:?} t.flags={:?} self.flags={:?}", t, t.flags, self.flags); |
664 | t.flags.intersects(self.flags) | |
9cc50fc6 SL |
665 | } |
666 | ||
7cac9316 | 667 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool { |
c30ab7b3 SL |
668 | let flags = r.type_flags(); |
669 | debug!("HasTypeFlagsVisitor: r={:?} r.flags={:?} self.flags={:?}", r, flags, self.flags); | |
670 | flags.intersects(self.flags) | |
9cc50fc6 | 671 | } |
ea8adc8c XL |
672 | |
673 | fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool { | |
674 | if let ConstVal::Unevaluated(..) = c.val { | |
675 | let projection_flags = TypeFlags::HAS_NORMALIZABLE_PROJECTION | | |
676 | TypeFlags::HAS_PROJECTION; | |
677 | if projection_flags.intersects(self.flags) { | |
678 | return true; | |
679 | } | |
680 | } | |
681 | c.super_visit_with(self) | |
682 | } | |
9cc50fc6 | 683 | } |
a7813a04 | 684 | |
94b46f34 XL |
685 | /// Collects all the late-bound regions at the innermost binding level |
686 | /// into a hash set. | |
a7813a04 | 687 | struct LateBoundRegionsCollector { |
94b46f34 | 688 | current_index: ty::DebruijnIndex, |
476ff2be | 689 | regions: FxHashSet<ty::BoundRegion>, |
94b46f34 XL |
690 | |
691 | /// If true, we only want regions that are known to be | |
692 | /// "constrained" when you equate this type with another type. In | |
693 | /// partcular, if you have e.g. `&'a u32` and `&'b u32`, equating | |
694 | /// them constraints `'a == 'b`. But if you have `<&'a u32 as | |
695 | /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those | |
696 | /// types may mean that `'a` and `'b` don't appear in the results, | |
697 | /// so they are not considered *constrained*. | |
a7813a04 XL |
698 | just_constrained: bool, |
699 | } | |
700 | ||
701 | impl LateBoundRegionsCollector { | |
702 | fn new(just_constrained: bool) -> Self { | |
703 | LateBoundRegionsCollector { | |
94b46f34 | 704 | current_index: ty::INNERMOST, |
476ff2be | 705 | regions: FxHashSet(), |
041b39d2 | 706 | just_constrained, |
a7813a04 XL |
707 | } |
708 | } | |
709 | } | |
710 | ||
711 | impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector { | |
712 | fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool { | |
94b46f34 | 713 | self.current_index.shift_in(1); |
a7813a04 | 714 | let result = t.super_visit_with(self); |
94b46f34 | 715 | self.current_index.shift_out(1); |
a7813a04 XL |
716 | result |
717 | } | |
718 | ||
719 | fn visit_ty(&mut self, t: Ty<'tcx>) -> bool { | |
720 | // if we are only looking for "constrained" region, we have to | |
721 | // ignore the inputs to a projection, as they may not appear | |
722 | // in the normalized form | |
723 | if self.just_constrained { | |
724 | match t.sty { | |
5bcae85e | 725 | ty::TyProjection(..) | ty::TyAnon(..) => { return false; } |
a7813a04 XL |
726 | _ => { } |
727 | } | |
728 | } | |
729 | ||
730 | t.super_visit_with(self) | |
731 | } | |
732 | ||
7cac9316 | 733 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool { |
9e0c209e | 734 | match *r { |
94b46f34 | 735 | ty::ReLateBound(debruijn, br) if debruijn == self.current_index => { |
a7813a04 XL |
736 | self.regions.insert(br); |
737 | } | |
738 | _ => { } | |
739 | } | |
740 | false | |
741 | } | |
742 | } |