]>
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 | //! | |
17 | //! T.fold_with(F) --calls--> F.fold_T(T) --calls--> super_fold_T(F, T) | |
18 | //! | |
19 | //! This way, when you define a new folder F, you can override | |
20 | //! `fold_T()` to customize the behavior, and invoke `super_fold_T()` | |
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* | |
27 | //! anything is `super_fold_T`, which traverses the type `T`. Moreover, | |
28 | //! `super_fold_T` should only ever call `T.fold_with()`. | |
29 | //! | |
30 | //! In some cases, we follow a degenerate pattern where we do not have | |
31 | //! a `fold_T` nor `super_fold_T` method. Instead, `T.fold_with` | |
32 | //! traverses the structure directly. This is suboptimal because the | |
33 | //! behavior cannot be overridden, but it's much less work to implement. | |
34 | //! If you ever *do* need an override that doesn't exist, it's not hard | |
35 | //! to convert the degenerate pattern into the proper thing. | |
36 | ||
37 | use middle::region; | |
38 | use middle::subst; | |
39 | use middle::ty::adjustment; | |
40 | use middle::ty::{self, Binder, Ty, RegionEscape}; | |
41 | ||
42 | use std::fmt; | |
43 | use util::nodemap::{FnvHashMap, FnvHashSet}; | |
44 | ||
45 | /////////////////////////////////////////////////////////////////////////// | |
46 | // Two generic traits | |
47 | ||
48 | /// The TypeFoldable trait is implemented for every type that can be folded. | |
49 | /// Basically, every type that has a corresponding method in TypeFolder. | |
50 | pub trait TypeFoldable<'tcx>: fmt::Debug + Clone { | |
51 | fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self; | |
52 | } | |
53 | ||
54 | /// The TypeFolder trait defines the actual *folding*. There is a | |
55 | /// method defined for every foldable type. Each of these has a | |
56 | /// default implementation that does an "identity" fold. Within each | |
57 | /// identity fold, it should invoke `foo.fold_with(self)` to fold each | |
58 | /// sub-item. | |
59 | pub trait TypeFolder<'tcx> : Sized { | |
60 | fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx>; | |
61 | ||
62 | /// Invoked by the `super_*` routines when we enter a region | |
63 | /// binding level (for example, when entering a function | |
64 | /// signature). This is used by clients that want to track the | |
65 | /// Debruijn index nesting level. | |
66 | fn enter_region_binder(&mut self) { } | |
67 | ||
68 | /// Invoked by the `super_*` routines when we exit a region | |
69 | /// binding level. This is used by clients that want to | |
70 | /// track the Debruijn index nesting level. | |
71 | fn exit_region_binder(&mut self) { } | |
72 | ||
73 | fn fold_binder<T>(&mut self, t: &Binder<T>) -> Binder<T> | |
74 | where T : TypeFoldable<'tcx> | |
75 | { | |
76 | // FIXME(#20526) this should replace `enter_region_binder`/`exit_region_binder`. | |
77 | super_fold_binder(self, t) | |
78 | } | |
79 | ||
80 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
81 | super_fold_ty(self, t) | |
82 | } | |
83 | ||
84 | fn fold_mt(&mut self, t: &ty::TypeAndMut<'tcx>) -> ty::TypeAndMut<'tcx> { | |
85 | super_fold_mt(self, t) | |
86 | } | |
87 | ||
88 | fn fold_trait_ref(&mut self, t: &ty::TraitRef<'tcx>) -> ty::TraitRef<'tcx> { | |
89 | super_fold_trait_ref(self, t) | |
90 | } | |
91 | ||
92 | fn fold_substs(&mut self, | |
93 | substs: &subst::Substs<'tcx>) | |
94 | -> subst::Substs<'tcx> { | |
95 | super_fold_substs(self, substs) | |
96 | } | |
97 | ||
98 | fn fold_fn_sig(&mut self, | |
99 | sig: &ty::FnSig<'tcx>) | |
100 | -> ty::FnSig<'tcx> { | |
101 | super_fold_fn_sig(self, sig) | |
102 | } | |
103 | ||
104 | fn fold_output(&mut self, | |
105 | output: &ty::FnOutput<'tcx>) | |
106 | -> ty::FnOutput<'tcx> { | |
107 | super_fold_output(self, output) | |
108 | } | |
109 | ||
110 | fn fold_bare_fn_ty(&mut self, | |
111 | fty: &ty::BareFnTy<'tcx>) | |
112 | -> ty::BareFnTy<'tcx> | |
113 | { | |
114 | super_fold_bare_fn_ty(self, fty) | |
115 | } | |
116 | ||
117 | fn fold_closure_ty(&mut self, | |
118 | fty: &ty::ClosureTy<'tcx>) | |
119 | -> ty::ClosureTy<'tcx> { | |
120 | super_fold_closure_ty(self, fty) | |
121 | } | |
122 | ||
123 | fn fold_region(&mut self, r: ty::Region) -> ty::Region { | |
124 | r | |
125 | } | |
126 | ||
127 | fn fold_existential_bounds(&mut self, s: &ty::ExistentialBounds<'tcx>) | |
128 | -> ty::ExistentialBounds<'tcx> { | |
129 | super_fold_existential_bounds(self, s) | |
130 | } | |
131 | ||
132 | fn fold_autoref(&mut self, ar: &adjustment::AutoRef<'tcx>) | |
133 | -> adjustment::AutoRef<'tcx> { | |
134 | super_fold_autoref(self, ar) | |
135 | } | |
136 | ||
137 | fn fold_item_substs(&mut self, i: ty::ItemSubsts<'tcx>) -> ty::ItemSubsts<'tcx> { | |
138 | super_fold_item_substs(self, i) | |
139 | } | |
140 | } | |
141 | ||
142 | /////////////////////////////////////////////////////////////////////////// | |
143 | // "super" routines: these are the default implementations for TypeFolder. | |
144 | // | |
145 | // They should invoke `foo.fold_with()` to do recursive folding. | |
146 | ||
147 | pub fn super_fold_binder<'tcx, T, U>(this: &mut T, | |
148 | binder: &Binder<U>) | |
149 | -> Binder<U> | |
150 | where T : TypeFolder<'tcx>, U : TypeFoldable<'tcx> | |
151 | { | |
152 | this.enter_region_binder(); | |
153 | let result = Binder(binder.0.fold_with(this)); | |
154 | this.exit_region_binder(); | |
155 | result | |
156 | } | |
157 | ||
158 | pub fn super_fold_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
159 | ty: Ty<'tcx>) | |
160 | -> Ty<'tcx> { | |
161 | let sty = match ty.sty { | |
162 | ty::TyBox(typ) => { | |
163 | ty::TyBox(typ.fold_with(this)) | |
164 | } | |
165 | ty::TyRawPtr(ref tm) => { | |
166 | ty::TyRawPtr(tm.fold_with(this)) | |
167 | } | |
168 | ty::TyArray(typ, sz) => { | |
169 | ty::TyArray(typ.fold_with(this), sz) | |
170 | } | |
171 | ty::TySlice(typ) => { | |
172 | ty::TySlice(typ.fold_with(this)) | |
173 | } | |
174 | ty::TyEnum(tid, ref substs) => { | |
175 | let substs = substs.fold_with(this); | |
176 | ty::TyEnum(tid, this.tcx().mk_substs(substs)) | |
177 | } | |
178 | ty::TyTrait(box ty::TraitTy { ref principal, ref bounds }) => { | |
179 | ty::TyTrait(box ty::TraitTy { | |
180 | principal: principal.fold_with(this), | |
181 | bounds: bounds.fold_with(this), | |
182 | }) | |
183 | } | |
184 | ty::TyTuple(ref ts) => { | |
185 | ty::TyTuple(ts.fold_with(this)) | |
186 | } | |
187 | ty::TyBareFn(opt_def_id, ref f) => { | |
188 | let bfn = f.fold_with(this); | |
189 | ty::TyBareFn(opt_def_id, this.tcx().mk_bare_fn(bfn)) | |
190 | } | |
191 | ty::TyRef(r, ref tm) => { | |
192 | let r = r.fold_with(this); | |
193 | ty::TyRef(this.tcx().mk_region(r), tm.fold_with(this)) | |
194 | } | |
195 | ty::TyStruct(did, ref substs) => { | |
196 | let substs = substs.fold_with(this); | |
197 | ty::TyStruct(did, this.tcx().mk_substs(substs)) | |
198 | } | |
199 | ty::TyClosure(did, ref substs) => { | |
200 | let s = substs.fold_with(this); | |
201 | ty::TyClosure(did, s) | |
202 | } | |
203 | ty::TyProjection(ref data) => { | |
204 | ty::TyProjection(data.fold_with(this)) | |
205 | } | |
206 | ty::TyBool | ty::TyChar | ty::TyStr | | |
207 | ty::TyInt(_) | ty::TyUint(_) | ty::TyFloat(_) | | |
208 | ty::TyError | ty::TyInfer(_) | | |
209 | ty::TyParam(..) => { | |
210 | ty.sty.clone() | |
211 | } | |
212 | }; | |
213 | this.tcx().mk_ty(sty) | |
214 | } | |
215 | ||
216 | pub fn super_fold_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
217 | substs: &subst::Substs<'tcx>) | |
218 | -> subst::Substs<'tcx> { | |
219 | let regions = match substs.regions { | |
220 | subst::ErasedRegions => { | |
221 | subst::ErasedRegions | |
222 | } | |
223 | subst::NonerasedRegions(ref regions) => { | |
224 | subst::NonerasedRegions(regions.fold_with(this)) | |
225 | } | |
226 | }; | |
227 | ||
228 | subst::Substs { regions: regions, | |
229 | types: substs.types.fold_with(this) } | |
230 | } | |
231 | ||
232 | pub fn super_fold_fn_sig<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
233 | sig: &ty::FnSig<'tcx>) | |
234 | -> ty::FnSig<'tcx> | |
235 | { | |
236 | ty::FnSig { inputs: sig.inputs.fold_with(this), | |
237 | output: sig.output.fold_with(this), | |
238 | variadic: sig.variadic } | |
239 | } | |
240 | ||
241 | pub fn super_fold_output<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
242 | output: &ty::FnOutput<'tcx>) | |
243 | -> ty::FnOutput<'tcx> { | |
244 | match *output { | |
245 | ty::FnConverging(ref ty) => ty::FnConverging(ty.fold_with(this)), | |
246 | ty::FnDiverging => ty::FnDiverging | |
247 | } | |
248 | } | |
249 | ||
250 | pub fn super_fold_bare_fn_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
251 | fty: &ty::BareFnTy<'tcx>) | |
252 | -> ty::BareFnTy<'tcx> | |
253 | { | |
254 | ty::BareFnTy { sig: fty.sig.fold_with(this), | |
255 | abi: fty.abi, | |
256 | unsafety: fty.unsafety } | |
257 | } | |
258 | ||
259 | pub fn super_fold_closure_ty<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
260 | fty: &ty::ClosureTy<'tcx>) | |
261 | -> ty::ClosureTy<'tcx> | |
262 | { | |
263 | ty::ClosureTy { | |
264 | sig: fty.sig.fold_with(this), | |
265 | unsafety: fty.unsafety, | |
266 | abi: fty.abi, | |
267 | } | |
268 | } | |
269 | ||
270 | pub fn super_fold_trait_ref<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
271 | t: &ty::TraitRef<'tcx>) | |
272 | -> ty::TraitRef<'tcx> | |
273 | { | |
274 | let substs = t.substs.fold_with(this); | |
275 | ty::TraitRef { | |
276 | def_id: t.def_id, | |
277 | substs: this.tcx().mk_substs(substs), | |
278 | } | |
279 | } | |
280 | ||
281 | pub fn super_fold_mt<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
282 | mt: &ty::TypeAndMut<'tcx>) | |
283 | -> ty::TypeAndMut<'tcx> { | |
284 | ty::TypeAndMut {ty: mt.ty.fold_with(this), | |
285 | mutbl: mt.mutbl} | |
286 | } | |
287 | ||
288 | pub fn super_fold_existential_bounds<'tcx, T: TypeFolder<'tcx>>( | |
289 | this: &mut T, | |
290 | bounds: &ty::ExistentialBounds<'tcx>) | |
291 | -> ty::ExistentialBounds<'tcx> | |
292 | { | |
293 | ty::ExistentialBounds { | |
294 | region_bound: bounds.region_bound.fold_with(this), | |
295 | builtin_bounds: bounds.builtin_bounds, | |
296 | projection_bounds: bounds.projection_bounds.fold_with(this), | |
297 | } | |
298 | } | |
299 | ||
300 | pub fn super_fold_autoref<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
301 | autoref: &adjustment::AutoRef<'tcx>) | |
302 | -> adjustment::AutoRef<'tcx> | |
303 | { | |
304 | match *autoref { | |
305 | adjustment::AutoPtr(r, m) => { | |
306 | let r = r.fold_with(this); | |
307 | adjustment::AutoPtr(this.tcx().mk_region(r), m) | |
308 | } | |
309 | adjustment::AutoUnsafe(m) => adjustment::AutoUnsafe(m) | |
310 | } | |
311 | } | |
312 | ||
313 | pub fn super_fold_item_substs<'tcx, T: TypeFolder<'tcx>>(this: &mut T, | |
314 | substs: ty::ItemSubsts<'tcx>) | |
315 | -> ty::ItemSubsts<'tcx> | |
316 | { | |
317 | ty::ItemSubsts { | |
318 | substs: substs.substs.fold_with(this), | |
319 | } | |
320 | } | |
321 | ||
322 | /////////////////////////////////////////////////////////////////////////// | |
323 | // Some sample folders | |
324 | ||
325 | pub struct BottomUpFolder<'a, 'tcx: 'a, F> where F: FnMut(Ty<'tcx>) -> Ty<'tcx> { | |
326 | pub tcx: &'a ty::ctxt<'tcx>, | |
327 | pub fldop: F, | |
328 | } | |
329 | ||
330 | impl<'a, 'tcx, F> TypeFolder<'tcx> for BottomUpFolder<'a, 'tcx, F> where | |
331 | F: FnMut(Ty<'tcx>) -> Ty<'tcx>, | |
332 | { | |
333 | fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx } | |
334 | ||
335 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
336 | let t1 = super_fold_ty(self, ty); | |
337 | (self.fldop)(t1) | |
338 | } | |
339 | } | |
340 | ||
341 | /////////////////////////////////////////////////////////////////////////// | |
342 | // Region folder | |
343 | ||
344 | impl<'tcx> ty::ctxt<'tcx> { | |
345 | /// Collects the free and escaping regions in `value` into `region_set`. Returns | |
346 | /// whether any late-bound regions were skipped | |
347 | pub fn collect_regions<T>(&self, | |
348 | value: &T, | |
349 | region_set: &mut FnvHashSet<ty::Region>) | |
350 | -> bool | |
351 | where T : TypeFoldable<'tcx> | |
352 | { | |
353 | let mut have_bound_regions = false; | |
354 | self.fold_regions(value, &mut have_bound_regions, | |
355 | |r, d| { region_set.insert(r.from_depth(d)); r }); | |
356 | have_bound_regions | |
357 | } | |
358 | ||
359 | /// Folds the escaping and free regions in `value` using `f`, and | |
360 | /// sets `skipped_regions` to true if any late-bound region was found | |
361 | /// and skipped. | |
362 | pub fn fold_regions<T,F>(&self, | |
363 | value: &T, | |
364 | skipped_regions: &mut bool, | |
365 | mut f: F) | |
366 | -> T | |
367 | where F : FnMut(ty::Region, u32) -> ty::Region, | |
368 | T : TypeFoldable<'tcx>, | |
369 | { | |
370 | value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f)) | |
371 | } | |
372 | } | |
373 | ||
374 | /// Folds over the substructure of a type, visiting its component | |
375 | /// types and all regions that occur *free* within it. | |
376 | /// | |
377 | /// That is, `Ty` can contain function or method types that bind | |
378 | /// regions at the call site (`ReLateBound`), and occurrences of | |
379 | /// regions (aka "lifetimes") that are bound within a type are not | |
380 | /// visited by this folder; only regions that occur free will be | |
381 | /// visited by `fld_r`. | |
382 | ||
383 | pub struct RegionFolder<'a, 'tcx: 'a> { | |
384 | tcx: &'a ty::ctxt<'tcx>, | |
385 | skipped_regions: &'a mut bool, | |
386 | current_depth: u32, | |
387 | fld_r: &'a mut (FnMut(ty::Region, u32) -> ty::Region + 'a), | |
388 | } | |
389 | ||
390 | impl<'a, 'tcx> RegionFolder<'a, 'tcx> { | |
391 | pub fn new<F>(tcx: &'a ty::ctxt<'tcx>, | |
392 | skipped_regions: &'a mut bool, | |
393 | fld_r: &'a mut F) -> RegionFolder<'a, 'tcx> | |
394 | where F : FnMut(ty::Region, u32) -> ty::Region | |
395 | { | |
396 | RegionFolder { | |
397 | tcx: tcx, | |
398 | skipped_regions: skipped_regions, | |
399 | current_depth: 1, | |
400 | fld_r: fld_r, | |
401 | } | |
402 | } | |
403 | } | |
404 | ||
405 | impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> | |
406 | { | |
407 | fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx } | |
408 | ||
409 | fn enter_region_binder(&mut self) { | |
410 | self.current_depth += 1; | |
411 | } | |
412 | ||
413 | fn exit_region_binder(&mut self) { | |
414 | self.current_depth -= 1; | |
415 | } | |
416 | ||
417 | fn fold_region(&mut self, r: ty::Region) -> ty::Region { | |
418 | match r { | |
419 | ty::ReLateBound(debruijn, _) if debruijn.depth < self.current_depth => { | |
420 | debug!("RegionFolder.fold_region({:?}) skipped bound region (current depth={})", | |
421 | r, self.current_depth); | |
422 | *self.skipped_regions = true; | |
423 | r | |
424 | } | |
425 | _ => { | |
426 | debug!("RegionFolder.fold_region({:?}) folding free region (current_depth={})", | |
427 | r, self.current_depth); | |
428 | (self.fld_r)(r, self.current_depth) | |
429 | } | |
430 | } | |
431 | } | |
432 | } | |
433 | ||
434 | /////////////////////////////////////////////////////////////////////////// | |
435 | // Late-bound region replacer | |
436 | ||
437 | // Replaces the escaping regions in a type. | |
438 | ||
439 | struct RegionReplacer<'a, 'tcx: 'a> { | |
440 | tcx: &'a ty::ctxt<'tcx>, | |
441 | current_depth: u32, | |
442 | fld_r: &'a mut (FnMut(ty::BoundRegion) -> ty::Region + 'a), | |
443 | map: FnvHashMap<ty::BoundRegion, ty::Region> | |
444 | } | |
445 | ||
446 | impl<'tcx> ty::ctxt<'tcx> { | |
447 | pub fn replace_late_bound_regions<T,F>(&self, | |
448 | value: &Binder<T>, | |
449 | mut f: F) | |
450 | -> (T, FnvHashMap<ty::BoundRegion, ty::Region>) | |
451 | where F : FnMut(ty::BoundRegion) -> ty::Region, | |
452 | T : TypeFoldable<'tcx>, | |
453 | { | |
454 | debug!("replace_late_bound_regions({:?})", value); | |
455 | let mut replacer = RegionReplacer::new(self, &mut f); | |
456 | let result = value.skip_binder().fold_with(&mut replacer); | |
457 | (result, replacer.map) | |
458 | } | |
459 | ||
460 | ||
461 | /// Replace any late-bound regions bound in `value` with free variants attached to scope-id | |
462 | /// `scope_id`. | |
463 | pub fn liberate_late_bound_regions<T>(&self, | |
464 | all_outlive_scope: region::CodeExtent, | |
465 | value: &Binder<T>) | |
466 | -> T | |
467 | where T : TypeFoldable<'tcx> | |
468 | { | |
469 | self.replace_late_bound_regions(value, |br| { | |
470 | ty::ReFree(ty::FreeRegion{scope: all_outlive_scope, bound_region: br}) | |
471 | }).0 | |
472 | } | |
473 | ||
474 | /// Flattens two binding levels into one. So `for<'a> for<'b> Foo` | |
475 | /// becomes `for<'a,'b> Foo`. | |
476 | pub fn flatten_late_bound_regions<T>(&self, bound2_value: &Binder<Binder<T>>) | |
477 | -> Binder<T> | |
478 | where T: TypeFoldable<'tcx> | |
479 | { | |
480 | let bound0_value = bound2_value.skip_binder().skip_binder(); | |
481 | let value = self.fold_regions(bound0_value, &mut false, | |
482 | |region, current_depth| { | |
483 | match region { | |
484 | ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => { | |
485 | // should be true if no escaping regions from bound2_value | |
486 | assert!(debruijn.depth - current_depth <= 1); | |
487 | ty::ReLateBound(ty::DebruijnIndex::new(current_depth), br) | |
488 | } | |
489 | _ => { | |
490 | region | |
491 | } | |
492 | } | |
493 | }); | |
494 | Binder(value) | |
495 | } | |
496 | ||
497 | pub fn no_late_bound_regions<T>(&self, value: &Binder<T>) -> Option<T> | |
498 | where T : TypeFoldable<'tcx> + RegionEscape | |
499 | { | |
500 | if value.0.has_escaping_regions() { | |
501 | None | |
502 | } else { | |
503 | Some(value.0.clone()) | |
504 | } | |
505 | } | |
506 | ||
507 | /// Replace any late-bound regions bound in `value` with `'static`. Useful in trans but also | |
508 | /// method lookup and a few other places where precise region relationships are not required. | |
509 | pub fn erase_late_bound_regions<T>(&self, value: &Binder<T>) -> T | |
510 | where T : TypeFoldable<'tcx> | |
511 | { | |
512 | self.replace_late_bound_regions(value, |_| ty::ReStatic).0 | |
513 | } | |
514 | ||
515 | /// Rewrite any late-bound regions so that they are anonymous. Region numbers are | |
516 | /// assigned starting at 1 and increasing monotonically in the order traversed | |
517 | /// by the fold operation. | |
518 | /// | |
519 | /// The chief purpose of this function is to canonicalize regions so that two | |
520 | /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become | |
521 | /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and | |
522 | /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization. | |
523 | pub fn anonymize_late_bound_regions<T>(&self, sig: &Binder<T>) -> Binder<T> | |
524 | where T : TypeFoldable<'tcx>, | |
525 | { | |
526 | let mut counter = 0; | |
527 | Binder(self.replace_late_bound_regions(sig, |_| { | |
528 | counter += 1; | |
529 | ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrAnon(counter)) | |
530 | }).0) | |
531 | } | |
532 | } | |
533 | ||
534 | impl<'a, 'tcx> RegionReplacer<'a, 'tcx> { | |
535 | fn new<F>(tcx: &'a ty::ctxt<'tcx>, fld_r: &'a mut F) -> RegionReplacer<'a, 'tcx> | |
536 | where F : FnMut(ty::BoundRegion) -> ty::Region | |
537 | { | |
538 | RegionReplacer { | |
539 | tcx: tcx, | |
540 | current_depth: 1, | |
541 | fld_r: fld_r, | |
542 | map: FnvHashMap() | |
543 | } | |
544 | } | |
545 | } | |
546 | ||
547 | impl<'a, 'tcx> TypeFolder<'tcx> for RegionReplacer<'a, 'tcx> | |
548 | { | |
549 | fn tcx(&self) -> &ty::ctxt<'tcx> { self.tcx } | |
550 | ||
551 | fn enter_region_binder(&mut self) { | |
552 | self.current_depth += 1; | |
553 | } | |
554 | ||
555 | fn exit_region_binder(&mut self) { | |
556 | self.current_depth -= 1; | |
557 | } | |
558 | ||
559 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
560 | if !t.has_regions_escaping_depth(self.current_depth-1) { | |
561 | return t; | |
562 | } | |
563 | ||
564 | super_fold_ty(self, t) | |
565 | } | |
566 | ||
567 | fn fold_region(&mut self, r: ty::Region) -> ty::Region { | |
568 | match r { | |
569 | ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => { | |
570 | debug!("RegionReplacer.fold_region({:?}) folding region (current_depth={})", | |
571 | r, self.current_depth); | |
572 | let fld_r = &mut self.fld_r; | |
573 | let region = *self.map.entry(br).or_insert_with(|| fld_r(br)); | |
574 | if let ty::ReLateBound(debruijn1, br) = region { | |
575 | // If the callback returns a late-bound region, | |
576 | // that region should always use depth 1. Then we | |
577 | // adjust it to the correct depth. | |
578 | assert_eq!(debruijn1.depth, 1); | |
579 | ty::ReLateBound(debruijn, br) | |
580 | } else { | |
581 | region | |
582 | } | |
583 | } | |
584 | r => r | |
585 | } | |
586 | } | |
587 | } | |
588 | ||
589 | /////////////////////////////////////////////////////////////////////////// | |
590 | // Region eraser | |
591 | ||
592 | impl<'tcx> ty::ctxt<'tcx> { | |
593 | /// Returns an equivalent value with all free regions removed (note | |
594 | /// that late-bound regions remain, because they are important for | |
595 | /// subtyping, but they are anonymized and normalized as well).. | |
596 | pub fn erase_regions<T>(&self, value: &T) -> T | |
597 | where T : TypeFoldable<'tcx> | |
598 | { | |
599 | let value1 = value.fold_with(&mut RegionEraser(self)); | |
600 | debug!("erase_regions({:?}) = {:?}", | |
601 | value, value1); | |
602 | return value1; | |
603 | ||
604 | struct RegionEraser<'a, 'tcx: 'a>(&'a ty::ctxt<'tcx>); | |
605 | ||
606 | impl<'a, 'tcx> TypeFolder<'tcx> for RegionEraser<'a, 'tcx> { | |
607 | fn tcx(&self) -> &ty::ctxt<'tcx> { self.0 } | |
608 | ||
609 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
610 | match self.tcx().normalized_cache.borrow().get(&ty).cloned() { | |
611 | None => {} | |
612 | Some(u) => return u | |
613 | } | |
614 | ||
615 | let t_norm = ty::fold::super_fold_ty(self, ty); | |
616 | self.tcx().normalized_cache.borrow_mut().insert(ty, t_norm); | |
617 | return t_norm; | |
618 | } | |
619 | ||
620 | fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> | |
621 | where T : TypeFoldable<'tcx> | |
622 | { | |
623 | let u = self.tcx().anonymize_late_bound_regions(t); | |
624 | ty::fold::super_fold_binder(self, &u) | |
625 | } | |
626 | ||
627 | fn fold_region(&mut self, r: ty::Region) -> ty::Region { | |
628 | // because late-bound regions affect subtyping, we can't | |
629 | // erase the bound/free distinction, but we can replace | |
630 | // all free regions with 'static. | |
631 | // | |
632 | // Note that we *CAN* replace early-bound regions -- the | |
633 | // type system never "sees" those, they get substituted | |
634 | // away. In trans, they will always be erased to 'static | |
635 | // whenever a substitution occurs. | |
636 | match r { | |
637 | ty::ReLateBound(..) => r, | |
638 | _ => ty::ReStatic | |
639 | } | |
640 | } | |
641 | ||
642 | fn fold_substs(&mut self, | |
643 | substs: &subst::Substs<'tcx>) | |
644 | -> subst::Substs<'tcx> { | |
645 | subst::Substs { regions: subst::ErasedRegions, | |
646 | types: substs.types.fold_with(self) } | |
647 | } | |
648 | } | |
649 | } | |
650 | } | |
651 | ||
652 | /////////////////////////////////////////////////////////////////////////// | |
653 | // Region shifter | |
654 | // | |
655 | // Shifts the De Bruijn indices on all escaping bound regions by a | |
656 | // fixed amount. Useful in substitution or when otherwise introducing | |
657 | // a binding level that is not intended to capture the existing bound | |
658 | // regions. See comment on `shift_regions_through_binders` method in | |
659 | // `subst.rs` for more details. | |
660 | ||
661 | pub fn shift_region(region: ty::Region, amount: u32) -> ty::Region { | |
662 | match region { | |
663 | ty::ReLateBound(debruijn, br) => { | |
664 | ty::ReLateBound(debruijn.shifted(amount), br) | |
665 | } | |
666 | _ => { | |
667 | region | |
668 | } | |
669 | } | |
670 | } | |
671 | ||
672 | pub fn shift_regions<'tcx, T:TypeFoldable<'tcx>>(tcx: &ty::ctxt<'tcx>, | |
673 | amount: u32, value: &T) -> T { | |
674 | debug!("shift_regions(value={:?}, amount={})", | |
675 | value, amount); | |
676 | ||
677 | value.fold_with(&mut RegionFolder::new(tcx, &mut false, &mut |region, _current_depth| { | |
678 | shift_region(region, amount) | |
679 | })) | |
680 | } |