]>
Commit | Line | Data |
---|---|---|
e9174d1e SL |
1 | //! Generalized type folding mechanism. The setup is a bit convoluted |
2 | //! but allows for convenient usage. Let T be an instance of some | |
3 | //! "foldable type" (one which implements `TypeFoldable`) and F be an | |
4 | //! instance of a "folder" (a type which implements `TypeFolder`). Then | |
5 | //! the setup is intended to be: | |
6 | //! | |
9fa01778 | 7 | //! T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F) |
e9174d1e SL |
8 | //! |
9 | //! This way, when you define a new folder F, you can override | |
9cc50fc6 | 10 | //! `fold_T()` to customize the behavior, and invoke `T.super_fold_with()` |
e9174d1e SL |
11 | //! to get the original behavior. Meanwhile, to actually fold |
12 | //! something, you can just write `T.fold_with(F)`, which is | |
13 | //! convenient. (Note that `fold_with` will also transparently handle | |
14 | //! things like a `Vec<T>` where T is foldable and so on.) | |
15 | //! | |
16 | //! In this ideal setup, the only function that actually *does* | |
9cc50fc6 SL |
17 | //! anything is `T.super_fold_with()`, which traverses the type `T`. |
18 | //! Moreover, `T.super_fold_with()` should only ever call `T.fold_with()`. | |
e9174d1e SL |
19 | //! |
20 | //! In some cases, we follow a degenerate pattern where we do not have | |
9cc50fc6 SL |
21 | //! a `fold_T` method. Instead, `T.fold_with` traverses the structure directly. |
22 | //! This is suboptimal because the behavior cannot be overridden, but it's | |
23 | //! much less work to implement. If you ever *do* need an override that | |
24 | //! doesn't exist, it's not hard to convert the degenerate pattern into the | |
25 | //! proper thing. | |
26 | //! | |
27 | //! A `TypeFoldable` T can also be visited by a `TypeVisitor` V using similar setup: | |
9fa01778 XL |
28 | //! |
29 | //! T.visit_with(V) --calls--> V.visit_T(T) --calls--> T.super_visit_with(V). | |
30 | //! | |
31 | //! These methods return true to indicate that the visitor has found what it is | |
32 | //! looking for, and does not need to visit anything else. | |
cdc7bbd5 | 33 | use crate::mir; |
dfeec247 | 34 | use crate::ty::{self, flags::FlagComputation, Binder, Ty, TyCtxt, TypeFlags}; |
74b04a01 | 35 | use rustc_hir as hir; |
dfeec247 | 36 | use rustc_hir::def_id::DefId; |
e9174d1e | 37 | |
dfeec247 | 38 | use rustc_data_structures::fx::FxHashSet; |
cdc7bbd5 | 39 | use rustc_data_structures::sso::SsoHashSet; |
94b46f34 | 40 | use std::collections::BTreeMap; |
e9174d1e | 41 | use std::fmt; |
29967ef6 | 42 | use std::ops::ControlFlow; |
e9174d1e | 43 | |
e1599b0c XL |
44 | /// This trait is implemented for every type that can be folded. |
45 | /// Basically, every type that has a corresponding method in `TypeFolder`. | |
0531ce1d | 46 | /// |
cdc7bbd5 | 47 | /// To implement this conveniently, use the derive macro located in `rustc_macros`. |
e9174d1e | 48 | pub trait TypeFoldable<'tcx>: fmt::Debug + Clone { |
fc512014 XL |
49 | fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self; |
50 | fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self { | |
9cc50fc6 SL |
51 | self.super_fold_with(folder) |
52 | } | |
53 | ||
fc512014 XL |
54 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>; |
55 | fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> { | |
9cc50fc6 SL |
56 | self.super_visit_with(visitor) |
57 | } | |
58 | ||
9fa01778 | 59 | /// Returns `true` if `self` has any late-bound regions that are either |
94b46f34 XL |
60 | /// bound by `binder` or bound by some binder outside of `binder`. |
61 | /// If `binder` is `ty::INNERMOST`, this indicates whether | |
62 | /// there are any late-bound regions that appear free. | |
a1dfa0c6 | 63 | fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool { |
29967ef6 | 64 | self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break() |
9cc50fc6 | 65 | } |
94b46f34 | 66 | |
9fa01778 | 67 | /// Returns `true` if this `self` has any regions that escape `binder` (and |
94b46f34 | 68 | /// hence are not bound by it). |
a1dfa0c6 XL |
69 | fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool { |
70 | self.has_vars_bound_at_or_above(binder.shifted_in(1)) | |
94b46f34 XL |
71 | } |
72 | ||
a1dfa0c6 XL |
73 | fn has_escaping_bound_vars(&self) -> bool { |
74 | self.has_vars_bound_at_or_above(ty::INNERMOST) | |
9cc50fc6 SL |
75 | } |
76 | ||
94222f64 XL |
77 | fn definitely_has_type_flags(&self, tcx: TyCtxt<'tcx>, flags: TypeFlags) -> bool { |
78 | self.visit_with(&mut HasTypeFlagsVisitor { tcx: Some(tcx), flags }).break_value() | |
79 | == Some(FoundFlags) | |
80 | } | |
81 | ||
9cc50fc6 | 82 | fn has_type_flags(&self, flags: TypeFlags) -> bool { |
94222f64 XL |
83 | self.visit_with(&mut HasTypeFlagsVisitor { tcx: None, flags }).break_value() |
84 | == Some(FoundFlags) | |
9cc50fc6 | 85 | } |
ea8adc8c | 86 | fn has_projections(&self) -> bool { |
9cc50fc6 SL |
87 | self.has_type_flags(TypeFlags::HAS_PROJECTION) |
88 | } | |
74b04a01 XL |
89 | fn has_opaque_types(&self) -> bool { |
90 | self.has_type_flags(TypeFlags::HAS_TY_OPAQUE) | |
91 | } | |
9cc50fc6 | 92 | fn references_error(&self) -> bool { |
ba9703b0 | 93 | self.has_type_flags(TypeFlags::HAS_ERROR) |
9cc50fc6 | 94 | } |
94222f64 XL |
95 | fn potentially_has_param_types_or_consts(&self) -> bool { |
96 | self.has_type_flags( | |
97 | TypeFlags::HAS_KNOWN_TY_PARAM | |
98 | | TypeFlags::HAS_KNOWN_CT_PARAM | |
99 | | TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS, | |
100 | ) | |
101 | } | |
102 | fn definitely_has_param_types_or_consts(&self, tcx: TyCtxt<'tcx>) -> bool { | |
103 | self.definitely_has_type_flags( | |
104 | tcx, | |
105 | TypeFlags::HAS_KNOWN_TY_PARAM | TypeFlags::HAS_KNOWN_CT_PARAM, | |
106 | ) | |
9cc50fc6 | 107 | } |
f035d41b XL |
108 | fn has_infer_regions(&self) -> bool { |
109 | self.has_type_flags(TypeFlags::HAS_RE_INFER) | |
110 | } | |
9cc50fc6 SL |
111 | fn has_infer_types(&self) -> bool { |
112 | self.has_type_flags(TypeFlags::HAS_TY_INFER) | |
113 | } | |
74b04a01 XL |
114 | fn has_infer_types_or_consts(&self) -> bool { |
115 | self.has_type_flags(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_CT_INFER) | |
116 | } | |
9cc50fc6 | 117 | fn needs_infer(&self) -> bool { |
74b04a01 | 118 | self.has_type_flags(TypeFlags::NEEDS_INFER) |
9cc50fc6 | 119 | } |
a1dfa0c6 | 120 | fn has_placeholders(&self) -> bool { |
48663c56 | 121 | self.has_type_flags( |
dfeec247 XL |
122 | TypeFlags::HAS_RE_PLACEHOLDER |
123 | | TypeFlags::HAS_TY_PLACEHOLDER | |
124 | | TypeFlags::HAS_CT_PLACEHOLDER, | |
48663c56 | 125 | ) |
83c7162d | 126 | } |
94222f64 XL |
127 | fn potentially_needs_subst(&self) -> bool { |
128 | self.has_type_flags( | |
129 | TypeFlags::KNOWN_NEEDS_SUBST | TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS, | |
130 | ) | |
131 | } | |
132 | fn definitely_needs_subst(&self, tcx: TyCtxt<'tcx>) -> bool { | |
133 | self.definitely_has_type_flags(tcx, TypeFlags::KNOWN_NEEDS_SUBST) | |
9cc50fc6 | 134 | } |
ff7c6d11 XL |
135 | /// "Free" regions in this context means that it has any region |
136 | /// that is not (a) erased or (b) late-bound. | |
94222f64 XL |
137 | fn has_free_regions(&self, tcx: TyCtxt<'tcx>) -> bool { |
138 | self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_REGIONS) | |
ff7c6d11 XL |
139 | } |
140 | ||
74b04a01 XL |
141 | fn has_erased_regions(&self) -> bool { |
142 | self.has_type_flags(TypeFlags::HAS_RE_ERASED) | |
143 | } | |
144 | ||
0731742a | 145 | /// True if there are any un-erased free regions. |
94222f64 XL |
146 | fn has_erasable_regions(&self, tcx: TyCtxt<'tcx>) -> bool { |
147 | self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_REGIONS) | |
148 | } | |
149 | ||
150 | /// Indicates whether this value definitely references only 'global' | |
151 | /// generic parameters that are the same regardless of what fn we are | |
152 | /// in. This is used for caching. | |
153 | /// | |
154 | /// Note that this function is pessimistic and may incorrectly return | |
155 | /// `false`. | |
156 | fn is_known_global(&self) -> bool { | |
157 | !self.has_type_flags(TypeFlags::HAS_POTENTIAL_FREE_LOCAL_NAMES) | |
9cc50fc6 | 158 | } |
ff7c6d11 | 159 | |
9cc50fc6 | 160 | /// Indicates whether this value references only 'global' |
532ac7d7 | 161 | /// generic parameters that are the same regardless of what fn we are |
94b46f34 | 162 | /// in. This is used for caching. |
94222f64 XL |
163 | fn is_global(&self, tcx: TyCtxt<'tcx>) -> bool { |
164 | !self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_LOCAL_NAMES) | |
94b46f34 XL |
165 | } |
166 | ||
167 | /// True if there are any late-bound regions | |
168 | fn has_late_bound_regions(&self) -> bool { | |
169 | self.has_type_flags(TypeFlags::HAS_RE_LATE_BOUND) | |
9cc50fc6 | 170 | } |
8faf50e0 | 171 | |
ba9703b0 XL |
172 | /// Indicates whether this value still has parameters/placeholders/inference variables |
173 | /// which could be replaced later, in a way that would change the results of `impl` | |
174 | /// specialization. | |
175 | fn still_further_specializable(&self) -> bool { | |
176 | self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE) | |
177 | } | |
e9174d1e SL |
178 | } |
179 | ||
74b04a01 | 180 | impl TypeFoldable<'tcx> for hir::Constness { |
fc512014 XL |
181 | fn super_fold_with<F: TypeFolder<'tcx>>(self, _: &mut F) -> Self { |
182 | self | |
dfeec247 | 183 | } |
fc512014 | 184 | fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> ControlFlow<V::BreakTy> { |
29967ef6 | 185 | ControlFlow::CONTINUE |
dfeec247 XL |
186 | } |
187 | } | |
188 | ||
9fa01778 | 189 | /// The `TypeFolder` trait defines the actual *folding*. There is a |
e9174d1e SL |
190 | /// method defined for every foldable type. Each of these has a |
191 | /// default implementation that does an "identity" fold. Within each | |
192 | /// identity fold, it should invoke `foo.fold_with(self)` to fold each | |
193 | /// sub-item. | |
dc9dc135 XL |
194 | pub trait TypeFolder<'tcx>: Sized { |
195 | fn tcx<'a>(&'a self) -> TyCtxt<'tcx>; | |
e9174d1e | 196 | |
cdc7bbd5 | 197 | fn fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Binder<'tcx, T> |
dfeec247 XL |
198 | where |
199 | T: TypeFoldable<'tcx>, | |
e9174d1e | 200 | { |
9cc50fc6 | 201 | t.super_fold_with(self) |
e9174d1e SL |
202 | } |
203 | ||
204 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
9cc50fc6 | 205 | t.super_fold_with(self) |
e9174d1e SL |
206 | } |
207 | ||
7cac9316 | 208 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9cc50fc6 | 209 | r.super_fold_with(self) |
e9174d1e | 210 | } |
ea8adc8c | 211 | |
532ac7d7 | 212 | fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { |
ea8adc8c XL |
213 | c.super_fold_with(self) |
214 | } | |
cdc7bbd5 | 215 | |
94222f64 XL |
216 | fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { |
217 | p.super_fold_with(self) | |
218 | } | |
219 | ||
cdc7bbd5 XL |
220 | fn fold_mir_const(&mut self, c: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx> { |
221 | bug!("most type folders should not be folding MIR datastructures: {:?}", c) | |
222 | } | |
e9174d1e SL |
223 | } |
224 | ||
dfeec247 | 225 | pub trait TypeVisitor<'tcx>: Sized { |
fc512014 | 226 | type BreakTy = !; |
94222f64 XL |
227 | /// Supplies the `tcx` for an unevaluated anonymous constant in case its default substs |
228 | /// are not yet supplied. | |
229 | /// | |
230 | /// Returning `None` for this method is only recommended if the `TypeVisitor` | |
231 | /// does not care about default anon const substs, as it ignores generic parameters, | |
232 | /// and fetching the default substs would cause a query cycle. | |
233 | /// | |
234 | /// For visitors which return `None` we completely skip the default substs in `ty::Unevaluated::super_visit_with`. | |
235 | /// This means that incorrectly returning `None` can very quickly lead to ICE or other critical bugs, so be careful and | |
236 | /// try to return an actual `tcx` if possible. | |
237 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>>; | |
fc512014 | 238 | |
cdc7bbd5 XL |
239 | fn visit_binder<T: TypeFoldable<'tcx>>( |
240 | &mut self, | |
241 | t: &Binder<'tcx, T>, | |
242 | ) -> ControlFlow<Self::BreakTy> { | |
54a0048b SL |
243 | t.super_visit_with(self) |
244 | } | |
e9174d1e | 245 | |
fc512014 | 246 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
9cc50fc6 | 247 | t.super_visit_with(self) |
e9174d1e | 248 | } |
e9174d1e | 249 | |
fc512014 | 250 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
9cc50fc6 | 251 | r.super_visit_with(self) |
e9174d1e | 252 | } |
ea8adc8c | 253 | |
fc512014 | 254 | fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
ea8adc8c XL |
255 | c.super_visit_with(self) |
256 | } | |
29967ef6 | 257 | |
94222f64 XL |
258 | fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> { |
259 | uv.super_visit_with(self) | |
260 | } | |
261 | ||
fc512014 | 262 | fn visit_predicate(&mut self, p: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> { |
29967ef6 XL |
263 | p.super_visit_with(self) |
264 | } | |
e9174d1e SL |
265 | } |
266 | ||
267 | /////////////////////////////////////////////////////////////////////////// | |
268 | // Some sample folders | |
269 | ||
dc9dc135 XL |
270 | pub struct BottomUpFolder<'tcx, F, G, H> |
271 | where | |
272 | F: FnMut(Ty<'tcx>) -> Ty<'tcx>, | |
273 | G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>, | |
274 | H: FnMut(&'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>, | |
a7813a04 | 275 | { |
dc9dc135 | 276 | pub tcx: TyCtxt<'tcx>, |
48663c56 XL |
277 | pub ty_op: F, |
278 | pub lt_op: G, | |
279 | pub ct_op: H, | |
e9174d1e SL |
280 | } |
281 | ||
dc9dc135 XL |
282 | impl<'tcx, F, G, H> TypeFolder<'tcx> for BottomUpFolder<'tcx, F, G, H> |
283 | where | |
284 | F: FnMut(Ty<'tcx>) -> Ty<'tcx>, | |
285 | G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>, | |
286 | H: FnMut(&'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>, | |
e9174d1e | 287 | { |
dc9dc135 XL |
288 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { |
289 | self.tcx | |
dfeec247 | 290 | } |
e9174d1e SL |
291 | |
292 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
48663c56 XL |
293 | let t = ty.super_fold_with(self); |
294 | (self.ty_op)(t) | |
e9174d1e | 295 | } |
8faf50e0 XL |
296 | |
297 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { | |
298 | let r = r.super_fold_with(self); | |
48663c56 XL |
299 | (self.lt_op)(r) |
300 | } | |
301 | ||
302 | fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { | |
303 | let ct = ct.super_fold_with(self); | |
304 | (self.ct_op)(ct) | |
8faf50e0 | 305 | } |
e9174d1e SL |
306 | } |
307 | ||
308 | /////////////////////////////////////////////////////////////////////////// | |
309 | // Region folder | |
310 | ||
dc9dc135 | 311 | impl<'tcx> TyCtxt<'tcx> { |
e9174d1e SL |
312 | /// Folds the escaping and free regions in `value` using `f`, and |
313 | /// sets `skipped_regions` to true if any late-bound region was found | |
314 | /// and skipped. | |
94b46f34 XL |
315 | pub fn fold_regions<T>( |
316 | self, | |
fc512014 | 317 | value: T, |
e9174d1e | 318 | skipped_regions: &mut bool, |
94b46f34 XL |
319 | mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, |
320 | ) -> T | |
321 | where | |
dfeec247 | 322 | T: TypeFoldable<'tcx>, |
e9174d1e SL |
323 | { |
324 | value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f)) | |
325 | } | |
abe05a73 | 326 | |
8faf50e0 XL |
327 | /// Invoke `callback` on every region appearing free in `value`. |
328 | pub fn for_each_free_region( | |
329 | self, | |
330 | value: &impl TypeFoldable<'tcx>, | |
331 | mut callback: impl FnMut(ty::Region<'tcx>), | |
332 | ) { | |
333 | self.any_free_region_meets(value, |r| { | |
334 | callback(r); | |
335 | false | |
336 | }); | |
337 | } | |
338 | ||
9fa01778 | 339 | /// Returns `true` if `callback` returns true for every region appearing free in `value`. |
8faf50e0 XL |
340 | pub fn all_free_regions_meet( |
341 | self, | |
342 | value: &impl TypeFoldable<'tcx>, | |
343 | mut callback: impl FnMut(ty::Region<'tcx>) -> bool, | |
344 | ) -> bool { | |
345 | !self.any_free_region_meets(value, |r| !callback(r)) | |
346 | } | |
347 | ||
9fa01778 | 348 | /// Returns `true` if `callback` returns true for some region appearing free in `value`. |
8faf50e0 XL |
349 | pub fn any_free_region_meets( |
350 | self, | |
351 | value: &impl TypeFoldable<'tcx>, | |
352 | callback: impl FnMut(ty::Region<'tcx>) -> bool, | |
353 | ) -> bool { | |
94222f64 XL |
354 | struct RegionVisitor<'tcx, F> { |
355 | tcx: TyCtxt<'tcx>, | |
94b46f34 XL |
356 | /// The index of a binder *just outside* the things we have |
357 | /// traversed. If we encounter a bound region bound by this | |
358 | /// binder or one outer to it, it appears free. Example: | |
359 | /// | |
360 | /// ``` | |
361 | /// for<'a> fn(for<'b> fn(), T) | |
362 | /// ^ ^ ^ ^ | |
363 | /// | | | | here, would be shifted in 1 | |
364 | /// | | | here, would be shifted in 2 | |
9fa01778 XL |
365 | /// | | here, would be `INNERMOST` shifted in by 1 |
366 | /// | here, initially, binder would be `INNERMOST` | |
94b46f34 XL |
367 | /// ``` |
368 | /// | |
369 | /// You see that, initially, *any* bound value is free, | |
370 | /// because we've not traversed any binders. As we pass | |
371 | /// through a binder, we shift the `outer_index` by 1 to | |
372 | /// account for the new binder that encloses us. | |
373 | outer_index: ty::DebruijnIndex, | |
abe05a73 XL |
374 | callback: F, |
375 | } | |
376 | ||
94222f64 | 377 | impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<'tcx, F> |
dfeec247 XL |
378 | where |
379 | F: FnMut(ty::Region<'tcx>) -> bool, | |
abe05a73 | 380 | { |
fc512014 XL |
381 | type BreakTy = (); |
382 | ||
94222f64 XL |
383 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { |
384 | Some(self.tcx) | |
385 | } | |
386 | ||
fc512014 XL |
387 | fn visit_binder<T: TypeFoldable<'tcx>>( |
388 | &mut self, | |
cdc7bbd5 | 389 | t: &Binder<'tcx, T>, |
fc512014 | 390 | ) -> ControlFlow<Self::BreakTy> { |
94b46f34 | 391 | self.outer_index.shift_in(1); |
f035d41b | 392 | let result = t.as_ref().skip_binder().visit_with(self); |
94b46f34 | 393 | self.outer_index.shift_out(1); |
8faf50e0 | 394 | result |
abe05a73 XL |
395 | } |
396 | ||
fc512014 | 397 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
abe05a73 | 398 | match *r { |
94b46f34 | 399 | ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => { |
29967ef6 XL |
400 | ControlFlow::CONTINUE |
401 | } | |
402 | _ => { | |
403 | if (self.callback)(r) { | |
404 | ControlFlow::BREAK | |
405 | } else { | |
406 | ControlFlow::CONTINUE | |
407 | } | |
abe05a73 | 408 | } |
abe05a73 | 409 | } |
8faf50e0 | 410 | } |
abe05a73 | 411 | |
fc512014 | 412 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
8faf50e0 | 413 | // We're only interested in types involving regions |
94222f64 | 414 | if ty.flags().intersects(TypeFlags::HAS_POTENTIAL_FREE_REGIONS) { |
8faf50e0 XL |
415 | ty.super_visit_with(self) |
416 | } else { | |
29967ef6 | 417 | ControlFlow::CONTINUE |
8faf50e0 | 418 | } |
abe05a73 XL |
419 | } |
420 | } | |
29967ef6 | 421 | |
94222f64 XL |
422 | value |
423 | .visit_with(&mut RegionVisitor { tcx: self, outer_index: ty::INNERMOST, callback }) | |
424 | .is_break() | |
abe05a73 | 425 | } |
e9174d1e SL |
426 | } |
427 | ||
428 | /// Folds over the substructure of a type, visiting its component | |
429 | /// types and all regions that occur *free* within it. | |
430 | /// | |
431 | /// That is, `Ty` can contain function or method types that bind | |
432 | /// regions at the call site (`ReLateBound`), and occurrences of | |
433 | /// regions (aka "lifetimes") that are bound within a type are not | |
434 | /// visited by this folder; only regions that occur free will be | |
435 | /// visited by `fld_r`. | |
436 | ||
dc9dc135 XL |
437 | pub struct RegionFolder<'a, 'tcx> { |
438 | tcx: TyCtxt<'tcx>, | |
e9174d1e | 439 | skipped_regions: &'a mut bool, |
94b46f34 XL |
440 | |
441 | /// Stores the index of a binder *just outside* the stuff we have | |
442 | /// visited. So this begins as INNERMOST; when we pass through a | |
443 | /// binder, it is incremented (via `shift_in`). | |
444 | current_index: ty::DebruijnIndex, | |
445 | ||
446 | /// Callback invokes for each free region. The `DebruijnIndex` | |
447 | /// points to the binder *just outside* the ones we have passed | |
448 | /// through. | |
dc9dc135 XL |
449 | fold_region_fn: |
450 | &'a mut (dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx> + 'a), | |
e9174d1e SL |
451 | } |
452 | ||
dc9dc135 | 453 | impl<'a, 'tcx> RegionFolder<'a, 'tcx> { |
a1dfa0c6 | 454 | #[inline] |
94b46f34 | 455 | pub fn new( |
dc9dc135 | 456 | tcx: TyCtxt<'tcx>, |
94b46f34 XL |
457 | skipped_regions: &'a mut bool, |
458 | fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>, | |
dc9dc135 | 459 | ) -> RegionFolder<'a, 'tcx> { |
dfeec247 | 460 | RegionFolder { tcx, skipped_regions, current_index: ty::INNERMOST, fold_region_fn } |
e9174d1e SL |
461 | } |
462 | } | |
463 | ||
dc9dc135 XL |
464 | impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> { |
465 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { | |
466 | self.tcx | |
dfeec247 | 467 | } |
e9174d1e | 468 | |
cdc7bbd5 XL |
469 | fn fold_binder<T: TypeFoldable<'tcx>>( |
470 | &mut self, | |
471 | t: ty::Binder<'tcx, T>, | |
472 | ) -> ty::Binder<'tcx, T> { | |
94b46f34 | 473 | self.current_index.shift_in(1); |
54a0048b | 474 | let t = t.super_fold_with(self); |
94b46f34 | 475 | self.current_index.shift_out(1); |
54a0048b | 476 | t |
e9174d1e SL |
477 | } |
478 | ||
7cac9316 | 479 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 480 | match *r { |
94b46f34 | 481 | ty::ReLateBound(debruijn, _) if debruijn < self.current_index => { |
dfeec247 XL |
482 | debug!( |
483 | "RegionFolder.fold_region({:?}) skipped bound region (current index={:?})", | |
484 | r, self.current_index | |
485 | ); | |
e9174d1e SL |
486 | *self.skipped_regions = true; |
487 | r | |
488 | } | |
489 | _ => { | |
dfeec247 XL |
490 | debug!( |
491 | "RegionFolder.fold_region({:?}) folding free region (current_index={:?})", | |
492 | r, self.current_index | |
493 | ); | |
94b46f34 | 494 | (self.fold_region_fn)(r, self.current_index) |
e9174d1e SL |
495 | } |
496 | } | |
497 | } | |
498 | } | |
499 | ||
500 | /////////////////////////////////////////////////////////////////////////// | |
a1dfa0c6 | 501 | // Bound vars replacer |
e9174d1e | 502 | |
a1dfa0c6 | 503 | /// Replaces the escaping bound vars (late bound regions or bound types) in a type. |
dc9dc135 XL |
504 | struct BoundVarReplacer<'a, 'tcx> { |
505 | tcx: TyCtxt<'tcx>, | |
94b46f34 XL |
506 | |
507 | /// As with `RegionFolder`, represents the index of a binder *just outside* | |
508 | /// the ones we have visited. | |
509 | current_index: ty::DebruijnIndex, | |
510 | ||
6a06907d XL |
511 | fld_r: Option<&'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a)>, |
512 | fld_t: Option<&'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a)>, | |
513 | fld_c: Option<&'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx> + 'a)>, | |
a1dfa0c6 XL |
514 | } |
515 | ||
dc9dc135 | 516 | impl<'a, 'tcx> BoundVarReplacer<'a, 'tcx> { |
6a06907d XL |
517 | fn new( |
518 | tcx: TyCtxt<'tcx>, | |
519 | fld_r: Option<&'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a)>, | |
520 | fld_t: Option<&'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a)>, | |
521 | fld_c: Option<&'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx> + 'a)>, | |
522 | ) -> Self { | |
dfeec247 | 523 | BoundVarReplacer { tcx, current_index: ty::INNERMOST, fld_r, fld_t, fld_c } |
a1dfa0c6 XL |
524 | } |
525 | } | |
526 | ||
dc9dc135 XL |
527 | impl<'a, 'tcx> TypeFolder<'tcx> for BoundVarReplacer<'a, 'tcx> { |
528 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { | |
529 | self.tcx | |
dfeec247 | 530 | } |
a1dfa0c6 | 531 | |
cdc7bbd5 XL |
532 | fn fold_binder<T: TypeFoldable<'tcx>>( |
533 | &mut self, | |
534 | t: ty::Binder<'tcx, T>, | |
535 | ) -> ty::Binder<'tcx, T> { | |
a1dfa0c6 XL |
536 | self.current_index.shift_in(1); |
537 | let t = t.super_fold_with(self); | |
538 | self.current_index.shift_out(1); | |
539 | t | |
540 | } | |
541 | ||
542 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
1b1a35ee | 543 | match *t.kind() { |
6a06907d XL |
544 | ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => { |
545 | if let Some(fld_t) = self.fld_t.as_mut() { | |
a1dfa0c6 | 546 | let ty = fld_t(bound_ty); |
6a06907d | 547 | return ty::fold::shift_vars(self.tcx, &ty, self.current_index.as_u32()); |
a1dfa0c6 XL |
548 | } |
549 | } | |
6a06907d XL |
550 | _ if t.has_vars_bound_at_or_above(self.current_index) => { |
551 | return t.super_fold_with(self); | |
a1dfa0c6 | 552 | } |
6a06907d | 553 | _ => {} |
a1dfa0c6 | 554 | } |
6a06907d | 555 | t |
a1dfa0c6 XL |
556 | } |
557 | ||
558 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { | |
559 | match *r { | |
560 | ty::ReLateBound(debruijn, br) if debruijn == self.current_index => { | |
6a06907d XL |
561 | if let Some(fld_r) = self.fld_r.as_mut() { |
562 | let region = fld_r(br); | |
563 | return if let ty::ReLateBound(debruijn1, br) = *region { | |
564 | // If the callback returns a late-bound region, | |
565 | // that region should always use the INNERMOST | |
566 | // debruijn index. Then we adjust it to the | |
567 | // correct depth. | |
568 | assert_eq!(debruijn1, ty::INNERMOST); | |
569 | self.tcx.mk_region(ty::ReLateBound(debruijn, br)) | |
570 | } else { | |
571 | region | |
572 | }; | |
a1dfa0c6 XL |
573 | } |
574 | } | |
6a06907d | 575 | _ => {} |
a1dfa0c6 | 576 | } |
6a06907d | 577 | r |
a1dfa0c6 | 578 | } |
48663c56 XL |
579 | |
580 | fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { | |
6a06907d XL |
581 | match *ct { |
582 | ty::Const { val: ty::ConstKind::Bound(debruijn, bound_const), ty } | |
583 | if debruijn == self.current_index => | |
584 | { | |
585 | if let Some(fld_c) = self.fld_c.as_mut() { | |
586 | let ct = fld_c(bound_const, ty); | |
587 | return ty::fold::shift_vars(self.tcx, &ct, self.current_index.as_u32()); | |
588 | } | |
48663c56 | 589 | } |
6a06907d XL |
590 | _ if ct.has_vars_bound_at_or_above(self.current_index) => { |
591 | return ct.super_fold_with(self); | |
48663c56 | 592 | } |
6a06907d | 593 | _ => {} |
48663c56 | 594 | } |
6a06907d | 595 | ct |
48663c56 | 596 | } |
e9174d1e SL |
597 | } |
598 | ||
dc9dc135 | 599 | impl<'tcx> TyCtxt<'tcx> { |
9fa01778 | 600 | /// Replaces all regions bound by the given `Binder` with the |
ff7c6d11 XL |
601 | /// results returned by the closure; the closure is expected to |
602 | /// return a free region (relative to this binder), and hence the | |
603 | /// binder is removed in the return type. The closure is invoked | |
fc512014 XL |
604 | /// once for each unique `BoundRegionKind`; multiple references to the |
605 | /// same `BoundRegionKind` will reuse the previous result. A map is | |
ff7c6d11 XL |
606 | /// returned at the end with each bound region and the free region |
607 | /// that replaced it. | |
a1dfa0c6 XL |
608 | /// |
609 | /// This method only replaces late bound regions and the result may still | |
610 | /// contain escaping bound types. | |
611 | pub fn replace_late_bound_regions<T, F>( | |
612 | self, | |
cdc7bbd5 | 613 | value: Binder<'tcx, T>, |
fc512014 | 614 | mut fld_r: F, |
a1dfa0c6 | 615 | ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>) |
dfeec247 XL |
616 | where |
617 | F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, | |
618 | T: TypeFoldable<'tcx>, | |
a1dfa0c6 | 619 | { |
fc512014 | 620 | let mut region_map = BTreeMap::new(); |
6a06907d XL |
621 | let mut real_fld_r = |
622 | |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br)); | |
623 | let value = value.skip_binder(); | |
624 | let value = if !value.has_escaping_bound_vars() { | |
625 | value | |
626 | } else { | |
627 | let mut replacer = BoundVarReplacer::new(self, Some(&mut real_fld_r), None, None); | |
628 | value.fold_with(&mut replacer) | |
629 | }; | |
fc512014 | 630 | (value, region_map) |
a1dfa0c6 XL |
631 | } |
632 | ||
9fa01778 | 633 | /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping |
48663c56 XL |
634 | /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c` |
635 | /// closure replaces escaping bound consts. | |
636 | pub fn replace_escaping_bound_vars<T, F, G, H>( | |
a1dfa0c6 | 637 | self, |
fc512014 | 638 | value: T, |
a1dfa0c6 | 639 | mut fld_r: F, |
48663c56 XL |
640 | mut fld_t: G, |
641 | mut fld_c: H, | |
fc512014 | 642 | ) -> T |
dfeec247 XL |
643 | where |
644 | F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, | |
645 | G: FnMut(ty::BoundTy) -> Ty<'tcx>, | |
646 | H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx>, | |
647 | T: TypeFoldable<'tcx>, | |
a1dfa0c6 | 648 | { |
a1dfa0c6 | 649 | if !value.has_escaping_bound_vars() { |
fc512014 | 650 | value |
a1dfa0c6 | 651 | } else { |
6a06907d XL |
652 | let mut replacer = |
653 | BoundVarReplacer::new(self, Some(&mut fld_r), Some(&mut fld_t), Some(&mut fld_c)); | |
fc512014 | 654 | value.fold_with(&mut replacer) |
a1dfa0c6 XL |
655 | } |
656 | } | |
657 | ||
9fa01778 | 658 | /// Replaces all types or regions bound by the given `Binder`. The `fld_r` |
a1dfa0c6 XL |
659 | /// closure replaces bound regions while the `fld_t` closure replaces bound |
660 | /// types. | |
48663c56 | 661 | pub fn replace_bound_vars<T, F, G, H>( |
a1dfa0c6 | 662 | self, |
cdc7bbd5 | 663 | value: Binder<'tcx, T>, |
fc512014 | 664 | mut fld_r: F, |
48663c56 XL |
665 | fld_t: G, |
666 | fld_c: H, | |
a1dfa0c6 | 667 | ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>) |
dfeec247 XL |
668 | where |
669 | F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>, | |
670 | G: FnMut(ty::BoundTy) -> Ty<'tcx>, | |
671 | H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx>, | |
672 | T: TypeFoldable<'tcx>, | |
e9174d1e | 673 | { |
fc512014 XL |
674 | let mut region_map = BTreeMap::new(); |
675 | let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br)); | |
676 | let value = self.replace_escaping_bound_vars(value.skip_binder(), real_fld_r, fld_t, fld_c); | |
677 | (value, region_map) | |
e9174d1e SL |
678 | } |
679 | ||
9fa01778 | 680 | /// Replaces any late-bound regions bound in `value` with |
ff7c6d11 | 681 | /// free variants attached to `all_outlive_scope`. |
cdc7bbd5 XL |
682 | pub fn liberate_late_bound_regions<T>( |
683 | self, | |
684 | all_outlive_scope: DefId, | |
685 | value: ty::Binder<'tcx, T>, | |
686 | ) -> T | |
dfeec247 XL |
687 | where |
688 | T: TypeFoldable<'tcx>, | |
689 | { | |
ff7c6d11 XL |
690 | self.replace_late_bound_regions(value, |br| { |
691 | self.mk_region(ty::ReFree(ty::FreeRegion { | |
692 | scope: all_outlive_scope, | |
fc512014 | 693 | bound_region: br.kind, |
ff7c6d11 | 694 | })) |
dfeec247 XL |
695 | }) |
696 | .0 | |
ff7c6d11 XL |
697 | } |
698 | ||
cdc7bbd5 XL |
699 | pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T |
700 | where | |
701 | T: TypeFoldable<'tcx>, | |
702 | { | |
703 | self.replace_escaping_bound_vars( | |
704 | value, | |
705 | |r| { | |
706 | self.mk_region(ty::ReLateBound( | |
707 | ty::INNERMOST, | |
708 | ty::BoundRegion { | |
709 | var: ty::BoundVar::from_usize(r.var.as_usize() + bound_vars), | |
710 | kind: r.kind, | |
711 | }, | |
712 | )) | |
713 | }, | |
714 | |t| { | |
715 | self.mk_ty(ty::Bound( | |
716 | ty::INNERMOST, | |
717 | ty::BoundTy { | |
718 | var: ty::BoundVar::from_usize(t.var.as_usize() + bound_vars), | |
719 | kind: t.kind, | |
720 | }, | |
721 | )) | |
722 | }, | |
723 | |c, ty| { | |
724 | self.mk_const(ty::Const { | |
725 | val: ty::ConstKind::Bound( | |
726 | ty::INNERMOST, | |
727 | ty::BoundVar::from_usize(c.as_usize() + bound_vars), | |
728 | ), | |
729 | ty, | |
730 | }) | |
731 | }, | |
732 | ) | |
733 | } | |
734 | ||
a7813a04 XL |
735 | /// Returns a set of all late-bound regions that are constrained |
736 | /// by `value`, meaning that if we instantiate those LBR with | |
737 | /// variables and equate `value` with something else, those | |
738 | /// variables will also be equated. | |
dfeec247 | 739 | pub fn collect_constrained_late_bound_regions<T>( |
1b1a35ee | 740 | self, |
cdc7bbd5 | 741 | value: &Binder<'tcx, T>, |
fc512014 | 742 | ) -> FxHashSet<ty::BoundRegionKind> |
dfeec247 XL |
743 | where |
744 | T: TypeFoldable<'tcx>, | |
a7813a04 XL |
745 | { |
746 | self.collect_late_bound_regions(value, true) | |
747 | } | |
748 | ||
749 | /// Returns a set of all late-bound regions that appear in `value` anywhere. | |
dfeec247 | 750 | pub fn collect_referenced_late_bound_regions<T>( |
1b1a35ee | 751 | self, |
cdc7bbd5 | 752 | value: &Binder<'tcx, T>, |
fc512014 | 753 | ) -> FxHashSet<ty::BoundRegionKind> |
dfeec247 XL |
754 | where |
755 | T: TypeFoldable<'tcx>, | |
a7813a04 XL |
756 | { |
757 | self.collect_late_bound_regions(value, false) | |
758 | } | |
759 | ||
dfeec247 | 760 | fn collect_late_bound_regions<T>( |
1b1a35ee | 761 | self, |
cdc7bbd5 | 762 | value: &Binder<'tcx, T>, |
dfeec247 | 763 | just_constraint: bool, |
fc512014 | 764 | ) -> FxHashSet<ty::BoundRegionKind> |
dfeec247 XL |
765 | where |
766 | T: TypeFoldable<'tcx>, | |
a7813a04 | 767 | { |
94222f64 | 768 | let mut collector = LateBoundRegionsCollector::new(self, just_constraint); |
f035d41b | 769 | let result = value.as_ref().skip_binder().visit_with(&mut collector); |
29967ef6 | 770 | assert!(result.is_continue()); // should never have stopped early |
a7813a04 XL |
771 | collector.regions |
772 | } | |
773 | ||
9fa01778 | 774 | /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also |
e9174d1e | 775 | /// method lookup and a few other places where precise region relationships are not required. |
cdc7bbd5 | 776 | pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T |
dfeec247 XL |
777 | where |
778 | T: TypeFoldable<'tcx>, | |
e9174d1e | 779 | { |
48663c56 | 780 | self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0 |
e9174d1e SL |
781 | } |
782 | ||
9fa01778 | 783 | /// Rewrite any late-bound regions so that they are anonymous. Region numbers are |
29967ef6 | 784 | /// assigned starting at 0 and increasing monotonically in the order traversed |
e9174d1e SL |
785 | /// by the fold operation. |
786 | /// | |
787 | /// The chief purpose of this function is to canonicalize regions so that two | |
788 | /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become | |
9fa01778 | 789 | /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and |
e9174d1e | 790 | /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization. |
cdc7bbd5 | 791 | pub fn anonymize_late_bound_regions<T>(self, sig: Binder<'tcx, T>) -> Binder<'tcx, T> |
dfeec247 XL |
792 | where |
793 | T: TypeFoldable<'tcx>, | |
e9174d1e SL |
794 | { |
795 | let mut counter = 0; | |
cdc7bbd5 XL |
796 | let inner = self |
797 | .replace_late_bound_regions(sig, |_| { | |
798 | let br = ty::BoundRegion { | |
799 | var: ty::BoundVar::from_u32(counter), | |
800 | kind: ty::BrAnon(counter), | |
801 | }; | |
fc512014 | 802 | let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br)); |
dfeec247 | 803 | counter += 1; |
29967ef6 | 804 | r |
dfeec247 | 805 | }) |
cdc7bbd5 XL |
806 | .0; |
807 | let bound_vars = self.mk_bound_variable_kinds( | |
808 | (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))), | |
809 | ); | |
810 | Binder::bind_with_vars(inner, bound_vars) | |
811 | } | |
812 | } | |
813 | ||
cdc7bbd5 XL |
814 | pub struct ValidateBoundVars<'tcx> { |
815 | bound_vars: &'tcx ty::List<ty::BoundVariableKind>, | |
816 | binder_index: ty::DebruijnIndex, | |
817 | // We may encounter the same variable at different levels of binding, so | |
818 | // this can't just be `Ty` | |
819 | visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>, | |
820 | } | |
821 | ||
822 | impl<'tcx> ValidateBoundVars<'tcx> { | |
823 | pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self { | |
824 | ValidateBoundVars { | |
825 | bound_vars, | |
826 | binder_index: ty::INNERMOST, | |
827 | visited: SsoHashSet::default(), | |
828 | } | |
829 | } | |
830 | } | |
831 | ||
832 | impl<'tcx> TypeVisitor<'tcx> for ValidateBoundVars<'tcx> { | |
833 | type BreakTy = (); | |
834 | ||
94222f64 XL |
835 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { |
836 | // Anonymous constants do not contain bound vars in their substs by default. | |
837 | None | |
838 | } | |
839 | ||
cdc7bbd5 XL |
840 | fn visit_binder<T: TypeFoldable<'tcx>>( |
841 | &mut self, | |
842 | t: &Binder<'tcx, T>, | |
843 | ) -> ControlFlow<Self::BreakTy> { | |
844 | self.binder_index.shift_in(1); | |
845 | let result = t.super_visit_with(self); | |
846 | self.binder_index.shift_out(1); | |
847 | result | |
848 | } | |
849 | ||
850 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
851 | if t.outer_exclusive_binder < self.binder_index | |
852 | || !self.visited.insert((self.binder_index, t)) | |
853 | { | |
854 | return ControlFlow::BREAK; | |
855 | } | |
856 | match *t.kind() { | |
857 | ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => { | |
858 | if self.bound_vars.len() <= bound_ty.var.as_usize() { | |
859 | bug!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars); | |
860 | } | |
861 | let list_var = self.bound_vars[bound_ty.var.as_usize()]; | |
862 | match list_var { | |
863 | ty::BoundVariableKind::Ty(kind) => { | |
864 | if kind != bound_ty.kind { | |
865 | bug!( | |
866 | "Mismatched type kinds: {:?} doesn't var in list {:?}", | |
867 | bound_ty.kind, | |
868 | list_var | |
869 | ); | |
870 | } | |
871 | } | |
872 | _ => { | |
873 | bug!("Mismatched bound variable kinds! Expected type, found {:?}", list_var) | |
874 | } | |
875 | } | |
876 | } | |
877 | ||
878 | _ => (), | |
879 | }; | |
880 | ||
881 | t.super_visit_with(self) | |
882 | } | |
883 | ||
884 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
885 | match r { | |
886 | ty::ReLateBound(index, br) if *index == self.binder_index => { | |
887 | if self.bound_vars.len() <= br.var.as_usize() { | |
888 | bug!("Not enough bound vars: {:?} not found in {:?}", *br, self.bound_vars); | |
889 | } | |
890 | let list_var = self.bound_vars[br.var.as_usize()]; | |
891 | match list_var { | |
892 | ty::BoundVariableKind::Region(kind) => { | |
893 | if kind != br.kind { | |
894 | bug!( | |
895 | "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})", | |
896 | br.kind, | |
897 | list_var, | |
898 | self.bound_vars | |
899 | ); | |
900 | } | |
901 | } | |
902 | _ => bug!( | |
903 | "Mismatched bound variable kinds! Expected region, found {:?}", | |
904 | list_var | |
905 | ), | |
906 | } | |
907 | } | |
908 | ||
909 | _ => (), | |
910 | }; | |
911 | ||
912 | r.super_visit_with(self) | |
e9174d1e SL |
913 | } |
914 | } | |
915 | ||
a1dfa0c6 XL |
916 | /////////////////////////////////////////////////////////////////////////// |
917 | // Shifter | |
918 | // | |
919 | // Shifts the De Bruijn indices on all escaping bound vars by a | |
920 | // fixed amount. Useful in substitution or when otherwise introducing | |
921 | // a binding level that is not intended to capture the existing bound | |
922 | // vars. See comment on `shift_vars_through_binders` method in | |
923 | // `subst.rs` for more details. | |
924 | ||
dc9dc135 XL |
925 | struct Shifter<'tcx> { |
926 | tcx: TyCtxt<'tcx>, | |
a1dfa0c6 XL |
927 | current_index: ty::DebruijnIndex, |
928 | amount: u32, | |
a1dfa0c6 XL |
929 | } |
930 | ||
dc9dc135 | 931 | impl Shifter<'tcx> { |
29967ef6 XL |
932 | pub fn new(tcx: TyCtxt<'tcx>, amount: u32) -> Self { |
933 | Shifter { tcx, current_index: ty::INNERMOST, amount } | |
e9174d1e SL |
934 | } |
935 | } | |
936 | ||
dc9dc135 XL |
937 | impl TypeFolder<'tcx> for Shifter<'tcx> { |
938 | fn tcx<'b>(&'b self) -> TyCtxt<'tcx> { | |
939 | self.tcx | |
dfeec247 | 940 | } |
e9174d1e | 941 | |
cdc7bbd5 XL |
942 | fn fold_binder<T: TypeFoldable<'tcx>>( |
943 | &mut self, | |
944 | t: ty::Binder<'tcx, T>, | |
945 | ) -> ty::Binder<'tcx, T> { | |
94b46f34 | 946 | self.current_index.shift_in(1); |
54a0048b | 947 | let t = t.super_fold_with(self); |
94b46f34 | 948 | self.current_index.shift_out(1); |
54a0048b | 949 | t |
e9174d1e SL |
950 | } |
951 | ||
7cac9316 | 952 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 953 | match *r { |
a1dfa0c6 XL |
954 | ty::ReLateBound(debruijn, br) => { |
955 | if self.amount == 0 || debruijn < self.current_index { | |
956 | r | |
e9174d1e | 957 | } else { |
29967ef6 | 958 | let debruijn = debruijn.shifted_in(self.amount); |
a1dfa0c6 XL |
959 | let shifted = ty::ReLateBound(debruijn, br); |
960 | self.tcx.mk_region(shifted) | |
e9174d1e SL |
961 | } |
962 | } | |
dfeec247 | 963 | _ => r, |
e9174d1e SL |
964 | } |
965 | } | |
e9174d1e | 966 | |
48663c56 | 967 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { |
1b1a35ee | 968 | match *ty.kind() { |
a1dfa0c6 XL |
969 | ty::Bound(debruijn, bound_ty) => { |
970 | if self.amount == 0 || debruijn < self.current_index { | |
971 | ty | |
972 | } else { | |
29967ef6 | 973 | let debruijn = debruijn.shifted_in(self.amount); |
dfeec247 | 974 | self.tcx.mk_ty(ty::Bound(debruijn, bound_ty)) |
a1dfa0c6 XL |
975 | } |
976 | } | |
e9174d1e | 977 | |
a1dfa0c6 | 978 | _ => ty.super_fold_with(self), |
e9174d1e SL |
979 | } |
980 | } | |
48663c56 XL |
981 | |
982 | fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { | |
60c5eb7d | 983 | if let ty::Const { val: ty::ConstKind::Bound(debruijn, bound_ct), ty } = *ct { |
48663c56 XL |
984 | if self.amount == 0 || debruijn < self.current_index { |
985 | ct | |
986 | } else { | |
29967ef6 | 987 | let debruijn = debruijn.shifted_in(self.amount); |
dfeec247 | 988 | self.tcx.mk_const(ty::Const { val: ty::ConstKind::Bound(debruijn, bound_ct), ty }) |
48663c56 XL |
989 | } |
990 | } else { | |
991 | ct.super_fold_with(self) | |
992 | } | |
993 | } | |
e9174d1e SL |
994 | } |
995 | ||
dc9dc135 XL |
996 | pub fn shift_region<'tcx>( |
997 | tcx: TyCtxt<'tcx>, | |
7cac9316 | 998 | region: ty::Region<'tcx>, |
dc9dc135 | 999 | amount: u32, |
a1dfa0c6 | 1000 | ) -> ty::Region<'tcx> { |
cc61c64b | 1001 | match region { |
a1dfa0c6 XL |
1002 | ty::ReLateBound(debruijn, br) if amount > 0 => { |
1003 | tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), *br)) | |
cc61c64b | 1004 | } |
dfeec247 | 1005 | _ => region, |
cc61c64b XL |
1006 | } |
1007 | } | |
1008 | ||
fc512014 | 1009 | pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T |
dc9dc135 XL |
1010 | where |
1011 | T: TypeFoldable<'tcx>, | |
1012 | { | |
dfeec247 | 1013 | debug!("shift_vars(value={:?}, amount={})", value, amount); |
a1dfa0c6 | 1014 | |
29967ef6 | 1015 | value.fold_with(&mut Shifter::new(tcx, amount)) |
e9174d1e | 1016 | } |
9cc50fc6 | 1017 | |
fc512014 XL |
1018 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] |
1019 | struct FoundEscapingVars; | |
1020 | ||
a1dfa0c6 XL |
1021 | /// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a |
1022 | /// bound region or a bound type. | |
9cc50fc6 SL |
1023 | /// |
1024 | /// So, for example, consider a type like the following, which has two binders: | |
1025 | /// | |
1026 | /// for<'a> fn(x: for<'b> fn(&'a isize, &'b isize)) | |
1027 | /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope | |
1028 | /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ inner scope | |
1029 | /// | |
1030 | /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the | |
1031 | /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner | |
1032 | /// fn type*, that type has an escaping region: `'a`. | |
1033 | /// | |
a1dfa0c6 XL |
1034 | /// Note that what I'm calling an "escaping var" is often just called a "free var". However, |
1035 | /// we already use the term "free var". It refers to the regions or types that we use to represent | |
1036 | /// bound regions or type params on a fn definition while we are type checking its body. | |
9cc50fc6 | 1037 | /// |
0bf4aa26 | 1038 | /// To clarify, conceptually there is no particular difference between |
a1dfa0c6 | 1039 | /// an "escaping" var and a "free" var. However, there is a big |
0bf4aa26 XL |
1040 | /// difference in practice. Basically, when "entering" a binding |
1041 | /// level, one is generally required to do some sort of processing to | |
a1dfa0c6 XL |
1042 | /// a bound var, such as replacing it with a fresh/placeholder |
1043 | /// var, or making an entry in the environment to represent the | |
1044 | /// scope to which it is attached, etc. An escaping var represents | |
1045 | /// a bound var for which this processing has not yet been done. | |
1046 | struct HasEscapingVarsVisitor { | |
9fa01778 | 1047 | /// Anything bound by `outer_index` or "above" is escaping. |
94b46f34 | 1048 | outer_index: ty::DebruijnIndex, |
9cc50fc6 SL |
1049 | } |
1050 | ||
a1dfa0c6 | 1051 | impl<'tcx> TypeVisitor<'tcx> for HasEscapingVarsVisitor { |
fc512014 XL |
1052 | type BreakTy = FoundEscapingVars; |
1053 | ||
94222f64 XL |
1054 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { |
1055 | // Anonymous constants do not contain bound vars in their substs by default. | |
1056 | None | |
1057 | } | |
1058 | ||
cdc7bbd5 XL |
1059 | fn visit_binder<T: TypeFoldable<'tcx>>( |
1060 | &mut self, | |
1061 | t: &Binder<'tcx, T>, | |
1062 | ) -> ControlFlow<Self::BreakTy> { | |
94b46f34 | 1063 | self.outer_index.shift_in(1); |
54a0048b | 1064 | let result = t.super_visit_with(self); |
94b46f34 | 1065 | self.outer_index.shift_out(1); |
54a0048b | 1066 | result |
9cc50fc6 SL |
1067 | } |
1068 | ||
6a06907d | 1069 | #[inline] |
fc512014 | 1070 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
94b46f34 XL |
1071 | // If the outer-exclusive-binder is *strictly greater* than |
1072 | // `outer_index`, that means that `t` contains some content | |
1073 | // bound at `outer_index` or above (because | |
1074 | // `outer_exclusive_binder` is always 1 higher than the | |
a1dfa0c6 | 1075 | // content in `t`). Therefore, `t` has some escaping vars. |
29967ef6 | 1076 | if t.outer_exclusive_binder > self.outer_index { |
fc512014 | 1077 | ControlFlow::Break(FoundEscapingVars) |
29967ef6 XL |
1078 | } else { |
1079 | ControlFlow::CONTINUE | |
1080 | } | |
9cc50fc6 SL |
1081 | } |
1082 | ||
6a06907d | 1083 | #[inline] |
fc512014 | 1084 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
94b46f34 XL |
1085 | // If the region is bound by `outer_index` or anything outside |
1086 | // of outer index, then it escapes the binders we have | |
1087 | // visited. | |
29967ef6 | 1088 | if r.bound_at_or_above_binder(self.outer_index) { |
fc512014 | 1089 | ControlFlow::Break(FoundEscapingVars) |
29967ef6 XL |
1090 | } else { |
1091 | ControlFlow::CONTINUE | |
1092 | } | |
9cc50fc6 | 1093 | } |
48663c56 | 1094 | |
fc512014 | 1095 | fn visit_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
e74abb32 XL |
1096 | // we don't have a `visit_infer_const` callback, so we have to |
1097 | // hook in here to catch this case (annoying...), but | |
1098 | // otherwise we do want to remember to visit the rest of the | |
1099 | // const, as it has types/regions embedded in a lot of other | |
1100 | // places. | |
1101 | match ct.val { | |
fc512014 XL |
1102 | ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => { |
1103 | ControlFlow::Break(FoundEscapingVars) | |
1104 | } | |
e74abb32 | 1105 | _ => ct.super_visit_with(self), |
48663c56 XL |
1106 | } |
1107 | } | |
9cc50fc6 | 1108 | |
6a06907d | 1109 | #[inline] |
fc512014 | 1110 | fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> { |
29967ef6 | 1111 | if predicate.inner.outer_exclusive_binder > self.outer_index { |
fc512014 | 1112 | ControlFlow::Break(FoundEscapingVars) |
29967ef6 XL |
1113 | } else { |
1114 | ControlFlow::CONTINUE | |
1115 | } | |
f035d41b XL |
1116 | } |
1117 | } | |
1118 | ||
fc512014 XL |
1119 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] |
1120 | struct FoundFlags; | |
1121 | ||
dc9dc135 | 1122 | // FIXME: Optimize for checking for infer flags |
94222f64 XL |
1123 | struct HasTypeFlagsVisitor<'tcx> { |
1124 | tcx: Option<TyCtxt<'tcx>>, | |
9cc50fc6 SL |
1125 | flags: ty::TypeFlags, |
1126 | } | |
1127 | ||
94222f64 | 1128 | impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor<'tcx> { |
fc512014 | 1129 | type BreakTy = FoundFlags; |
94222f64 XL |
1130 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { |
1131 | bug!("we shouldn't call this method as we manually look at ct substs"); | |
1132 | } | |
fc512014 | 1133 | |
6a06907d | 1134 | #[inline] |
94222f64 XL |
1135 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
1136 | let flags = t.flags(); | |
1137 | debug!("HasTypeFlagsVisitor: t={:?} flags={:?} self.flags={:?}", t, flags, self.flags); | |
1138 | if flags.intersects(self.flags) { | |
fc512014 XL |
1139 | ControlFlow::Break(FoundFlags) |
1140 | } else { | |
94222f64 XL |
1141 | match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { |
1142 | true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, t), | |
1143 | _ => ControlFlow::CONTINUE, | |
1144 | } | |
fc512014 | 1145 | } |
9cc50fc6 SL |
1146 | } |
1147 | ||
6a06907d | 1148 | #[inline] |
fc512014 | 1149 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
c30ab7b3 SL |
1150 | let flags = r.type_flags(); |
1151 | debug!("HasTypeFlagsVisitor: r={:?} r.flags={:?} self.flags={:?}", r, flags, self.flags); | |
fc512014 XL |
1152 | if flags.intersects(self.flags) { |
1153 | ControlFlow::Break(FoundFlags) | |
1154 | } else { | |
1155 | ControlFlow::CONTINUE | |
1156 | } | |
9cc50fc6 | 1157 | } |
ea8adc8c | 1158 | |
6a06907d | 1159 | #[inline] |
fc512014 | 1160 | fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
532ac7d7 XL |
1161 | let flags = FlagComputation::for_const(c); |
1162 | debug!("HasTypeFlagsVisitor: c={:?} c.flags={:?} self.flags={:?}", c, flags, self.flags); | |
fc512014 XL |
1163 | if flags.intersects(self.flags) { |
1164 | ControlFlow::Break(FoundFlags) | |
1165 | } else { | |
94222f64 XL |
1166 | match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { |
1167 | true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, c), | |
1168 | _ => ControlFlow::CONTINUE, | |
1169 | } | |
1170 | } | |
1171 | } | |
1172 | ||
1173 | #[inline] | |
1174 | fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> { | |
1175 | let flags = FlagComputation::for_unevaluated_const(uv); | |
1176 | debug!("HasTypeFlagsVisitor: uv={:?} uv.flags={:?} self.flags={:?}", uv, flags, self.flags); | |
1177 | if flags.intersects(self.flags) { | |
1178 | ControlFlow::Break(FoundFlags) | |
1179 | } else { | |
1180 | match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { | |
1181 | true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, uv), | |
1182 | _ => ControlFlow::CONTINUE, | |
1183 | } | |
fc512014 | 1184 | } |
ea8adc8c | 1185 | } |
a7813a04 | 1186 | |
6a06907d | 1187 | #[inline] |
fc512014 | 1188 | fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> { |
94222f64 | 1189 | let flags = predicate.inner.flags; |
f035d41b | 1190 | debug!( |
94222f64 XL |
1191 | "HasTypeFlagsVisitor: predicate={:?} flags={:?} self.flags={:?}", |
1192 | predicate, flags, self.flags | |
f035d41b | 1193 | ); |
94222f64 | 1194 | if flags.intersects(self.flags) { |
fc512014 | 1195 | ControlFlow::Break(FoundFlags) |
94222f64 XL |
1196 | } else { |
1197 | match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { | |
1198 | true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, predicate), | |
1199 | _ => ControlFlow::CONTINUE, | |
1200 | } | |
1201 | } | |
1202 | } | |
1203 | } | |
1204 | ||
1205 | struct UnknownConstSubstsVisitor<'tcx> { | |
1206 | tcx: TyCtxt<'tcx>, | |
1207 | flags: ty::TypeFlags, | |
1208 | } | |
1209 | ||
1210 | impl<'tcx> UnknownConstSubstsVisitor<'tcx> { | |
1211 | /// This is fairly cold and we don't want to | |
1212 | /// bloat the size of the `HasTypeFlagsVisitor`. | |
1213 | #[inline(never)] | |
1214 | pub fn search<T: TypeFoldable<'tcx>>( | |
1215 | visitor: &HasTypeFlagsVisitor<'tcx>, | |
1216 | v: T, | |
1217 | ) -> ControlFlow<FoundFlags> { | |
1218 | if visitor.flags.intersects(TypeFlags::MAY_NEED_DEFAULT_CONST_SUBSTS) { | |
1219 | v.super_visit_with(&mut UnknownConstSubstsVisitor { | |
1220 | tcx: visitor.tcx.unwrap(), | |
1221 | flags: visitor.flags, | |
1222 | }) | |
29967ef6 XL |
1223 | } else { |
1224 | ControlFlow::CONTINUE | |
1225 | } | |
f035d41b XL |
1226 | } |
1227 | } | |
29967ef6 | 1228 | |
94222f64 XL |
1229 | impl<'tcx> TypeVisitor<'tcx> for UnknownConstSubstsVisitor<'tcx> { |
1230 | type BreakTy = FoundFlags; | |
1231 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { | |
1232 | bug!("we shouldn't call this method as we manually look at ct substs"); | |
1233 | } | |
1234 | ||
1235 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
1236 | if t.flags().intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { | |
1237 | t.super_visit_with(self) | |
1238 | } else { | |
1239 | ControlFlow::CONTINUE | |
1240 | } | |
1241 | } | |
1242 | ||
1243 | #[inline] | |
1244 | fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> { | |
1245 | if uv.substs_.is_none() { | |
1246 | self.tcx | |
1247 | .default_anon_const_substs(uv.def.did) | |
1248 | .visit_with(&mut HasTypeFlagsVisitor { tcx: Some(self.tcx), flags: self.flags }) | |
1249 | } else { | |
1250 | ControlFlow::CONTINUE | |
1251 | } | |
1252 | } | |
1253 | ||
1254 | #[inline] | |
1255 | fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> { | |
1256 | if predicate.inner.flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { | |
1257 | predicate.super_visit_with(self) | |
1258 | } else { | |
1259 | ControlFlow::CONTINUE | |
1260 | } | |
1261 | } | |
1262 | } | |
1263 | ||
1264 | impl<'tcx> TyCtxt<'tcx> { | |
1265 | /// This is a HACK(const_generics) and should probably not be needed. | |
1266 | /// Might however be perf relevant, so who knows. | |
1267 | /// | |
1268 | /// FIXME(@lcnr): explain this function a bit more | |
1269 | pub fn expose_default_const_substs<T: TypeFoldable<'tcx>>(self, v: T) -> T { | |
1270 | v.fold_with(&mut ExposeDefaultConstSubstsFolder { tcx: self }) | |
1271 | } | |
1272 | } | |
1273 | ||
1274 | struct ExposeDefaultConstSubstsFolder<'tcx> { | |
1275 | tcx: TyCtxt<'tcx>, | |
1276 | } | |
1277 | ||
1278 | impl<'tcx> TypeFolder<'tcx> for ExposeDefaultConstSubstsFolder<'tcx> { | |
1279 | fn tcx(&self) -> TyCtxt<'tcx> { | |
1280 | self.tcx | |
1281 | } | |
1282 | ||
1283 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
1284 | if ty.flags().intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { | |
1285 | ty.super_fold_with(self) | |
1286 | } else { | |
1287 | ty | |
1288 | } | |
1289 | } | |
1290 | ||
1291 | fn fold_predicate(&mut self, pred: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { | |
1292 | if pred.inner.flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) { | |
1293 | pred.super_fold_with(self) | |
1294 | } else { | |
1295 | pred | |
1296 | } | |
1297 | } | |
1298 | } | |
1299 | ||
94b46f34 XL |
1300 | /// Collects all the late-bound regions at the innermost binding level |
1301 | /// into a hash set. | |
94222f64 XL |
1302 | struct LateBoundRegionsCollector<'tcx> { |
1303 | tcx: TyCtxt<'tcx>, | |
94b46f34 | 1304 | current_index: ty::DebruijnIndex, |
fc512014 | 1305 | regions: FxHashSet<ty::BoundRegionKind>, |
94b46f34 | 1306 | |
9fa01778 | 1307 | /// `true` if we only want regions that are known to be |
94b46f34 | 1308 | /// "constrained" when you equate this type with another type. In |
0731742a | 1309 | /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating |
9fa01778 | 1310 | /// them constraints `'a == 'b`. But if you have `<&'a u32 as |
94b46f34 XL |
1311 | /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those |
1312 | /// types may mean that `'a` and `'b` don't appear in the results, | |
1313 | /// so they are not considered *constrained*. | |
a7813a04 XL |
1314 | just_constrained: bool, |
1315 | } | |
1316 | ||
94222f64 XL |
1317 | impl LateBoundRegionsCollector<'tcx> { |
1318 | fn new(tcx: TyCtxt<'tcx>, just_constrained: bool) -> Self { | |
a7813a04 | 1319 | LateBoundRegionsCollector { |
94222f64 | 1320 | tcx, |
94b46f34 | 1321 | current_index: ty::INNERMOST, |
0bf4aa26 | 1322 | regions: Default::default(), |
041b39d2 | 1323 | just_constrained, |
a7813a04 XL |
1324 | } |
1325 | } | |
1326 | } | |
1327 | ||
94222f64 XL |
1328 | impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector<'tcx> { |
1329 | fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> { | |
1330 | Some(self.tcx) | |
1331 | } | |
1332 | ||
cdc7bbd5 XL |
1333 | fn visit_binder<T: TypeFoldable<'tcx>>( |
1334 | &mut self, | |
1335 | t: &Binder<'tcx, T>, | |
1336 | ) -> ControlFlow<Self::BreakTy> { | |
94b46f34 | 1337 | self.current_index.shift_in(1); |
a7813a04 | 1338 | let result = t.super_visit_with(self); |
94b46f34 | 1339 | self.current_index.shift_out(1); |
a7813a04 XL |
1340 | result |
1341 | } | |
1342 | ||
fc512014 | 1343 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
a7813a04 XL |
1344 | // if we are only looking for "constrained" region, we have to |
1345 | // ignore the inputs to a projection, as they may not appear | |
1346 | // in the normalized form | |
1347 | if self.just_constrained { | |
1b1a35ee | 1348 | if let ty::Projection(..) | ty::Opaque(..) = t.kind() { |
29967ef6 | 1349 | return ControlFlow::CONTINUE; |
a7813a04 XL |
1350 | } |
1351 | } | |
1352 | ||
1353 | t.super_visit_with(self) | |
1354 | } | |
1355 | ||
fc512014 | 1356 | fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
ba9703b0 XL |
1357 | // if we are only looking for "constrained" region, we have to |
1358 | // ignore the inputs of an unevaluated const, as they may not appear | |
1359 | // in the normalized form | |
1360 | if self.just_constrained { | |
1361 | if let ty::ConstKind::Unevaluated(..) = c.val { | |
29967ef6 | 1362 | return ControlFlow::CONTINUE; |
ba9703b0 XL |
1363 | } |
1364 | } | |
1365 | ||
1366 | c.super_visit_with(self) | |
1367 | } | |
1368 | ||
fc512014 | 1369 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
0bf4aa26 | 1370 | if let ty::ReLateBound(debruijn, br) = *r { |
dfeec247 | 1371 | if debruijn == self.current_index { |
fc512014 | 1372 | self.regions.insert(br.kind); |
a7813a04 | 1373 | } |
a7813a04 | 1374 | } |
29967ef6 | 1375 | ControlFlow::CONTINUE |
a7813a04 XL |
1376 | } |
1377 | } |