]>
Commit | Line | Data |
---|---|---|
064997fb FG |
1 | use crate::ty::{self, flags::FlagComputation, Binder, Ty, TyCtxt, TypeFlags}; |
2 | use rustc_errors::ErrorGuaranteed; | |
3 | ||
4 | use rustc_data_structures::fx::FxHashSet; | |
5 | use rustc_data_structures::sso::SsoHashSet; | |
064997fb FG |
6 | use std::ops::ControlFlow; |
7 | ||
9ffffee4 | 8 | pub use rustc_type_ir::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor}; |
064997fb | 9 | |
9ffffee4 | 10 | pub trait TypeVisitableExt<'tcx>: TypeVisitable<TyCtxt<'tcx>> { |
064997fb FG |
11 | /// Returns `true` if `self` has any late-bound regions that are either |
12 | /// bound by `binder` or bound by some binder outside of `binder`. | |
13 | /// If `binder` is `ty::INNERMOST`, this indicates whether | |
14 | /// there are any late-bound regions that appear free. | |
15 | fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool { | |
16 | self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break() | |
17 | } | |
18 | ||
487cf647 | 19 | /// Returns `true` if this type has any regions that escape `binder` (and |
064997fb FG |
20 | /// hence are not bound by it). |
21 | fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool { | |
22 | self.has_vars_bound_at_or_above(binder.shifted_in(1)) | |
23 | } | |
24 | ||
487cf647 FG |
25 | /// Return `true` if this type has regions that are not a part of the type. |
26 | /// For example, `for<'a> fn(&'a i32)` return `false`, while `fn(&'a i32)` | |
27 | /// would return `true`. The latter can occur when traversing through the | |
28 | /// former. | |
29 | /// | |
30 | /// See [`HasEscapingVarsVisitor`] for more information. | |
064997fb FG |
31 | fn has_escaping_bound_vars(&self) -> bool { |
32 | self.has_vars_bound_at_or_above(ty::INNERMOST) | |
33 | } | |
34 | ||
064997fb | 35 | fn has_type_flags(&self, flags: TypeFlags) -> bool { |
9c376795 FG |
36 | let res = |
37 | self.visit_with(&mut HasTypeFlagsVisitor { flags }).break_value() == Some(FoundFlags); | |
38 | trace!(?self, ?flags, ?res, "has_type_flags"); | |
39 | res | |
064997fb FG |
40 | } |
41 | fn has_projections(&self) -> bool { | |
42 | self.has_type_flags(TypeFlags::HAS_PROJECTION) | |
43 | } | |
44 | fn has_opaque_types(&self) -> bool { | |
45 | self.has_type_flags(TypeFlags::HAS_TY_OPAQUE) | |
46 | } | |
9ffffee4 FG |
47 | fn has_generators(&self) -> bool { |
48 | self.has_type_flags(TypeFlags::HAS_TY_GENERATOR) | |
49 | } | |
064997fb FG |
50 | fn references_error(&self) -> bool { |
51 | self.has_type_flags(TypeFlags::HAS_ERROR) | |
52 | } | |
487cf647 | 53 | fn error_reported(&self) -> Result<(), ErrorGuaranteed> { |
064997fb | 54 | if self.references_error() { |
487cf647 FG |
55 | if let Some(reported) = ty::tls::with(|tcx| tcx.sess.is_compilation_going_to_fail()) { |
56 | Err(reported) | |
57 | } else { | |
58 | bug!("expect tcx.sess.is_compilation_going_to_fail return `Some`"); | |
59 | } | |
064997fb | 60 | } else { |
487cf647 | 61 | Ok(()) |
064997fb FG |
62 | } |
63 | } | |
2b03887a FG |
64 | fn has_non_region_param(&self) -> bool { |
65 | self.has_type_flags(TypeFlags::NEEDS_SUBST - TypeFlags::HAS_RE_PARAM) | |
064997fb FG |
66 | } |
67 | fn has_infer_regions(&self) -> bool { | |
68 | self.has_type_flags(TypeFlags::HAS_RE_INFER) | |
69 | } | |
70 | fn has_infer_types(&self) -> bool { | |
71 | self.has_type_flags(TypeFlags::HAS_TY_INFER) | |
72 | } | |
2b03887a FG |
73 | fn has_non_region_infer(&self) -> bool { |
74 | self.has_type_flags(TypeFlags::NEEDS_INFER - TypeFlags::HAS_RE_INFER) | |
064997fb FG |
75 | } |
76 | fn needs_infer(&self) -> bool { | |
77 | self.has_type_flags(TypeFlags::NEEDS_INFER) | |
78 | } | |
79 | fn has_placeholders(&self) -> bool { | |
80 | self.has_type_flags( | |
81 | TypeFlags::HAS_RE_PLACEHOLDER | |
82 | | TypeFlags::HAS_TY_PLACEHOLDER | |
83 | | TypeFlags::HAS_CT_PLACEHOLDER, | |
84 | ) | |
85 | } | |
86 | fn needs_subst(&self) -> bool { | |
87 | self.has_type_flags(TypeFlags::NEEDS_SUBST) | |
88 | } | |
89 | /// "Free" regions in this context means that it has any region | |
90 | /// that is not (a) erased or (b) late-bound. | |
91 | fn has_free_regions(&self) -> bool { | |
92 | self.has_type_flags(TypeFlags::HAS_FREE_REGIONS) | |
93 | } | |
94 | ||
95 | fn has_erased_regions(&self) -> bool { | |
96 | self.has_type_flags(TypeFlags::HAS_RE_ERASED) | |
97 | } | |
98 | ||
99 | /// True if there are any un-erased free regions. | |
100 | fn has_erasable_regions(&self) -> bool { | |
101 | self.has_type_flags(TypeFlags::HAS_FREE_REGIONS) | |
102 | } | |
103 | ||
104 | /// Indicates whether this value references only 'global' | |
105 | /// generic parameters that are the same regardless of what fn we are | |
106 | /// in. This is used for caching. | |
107 | fn is_global(&self) -> bool { | |
108 | !self.has_type_flags(TypeFlags::HAS_FREE_LOCAL_NAMES) | |
109 | } | |
110 | ||
111 | /// True if there are any late-bound regions | |
112 | fn has_late_bound_regions(&self) -> bool { | |
113 | self.has_type_flags(TypeFlags::HAS_RE_LATE_BOUND) | |
114 | } | |
9c376795 FG |
115 | /// True if there are any late-bound non-region variables |
116 | fn has_non_region_late_bound(&self) -> bool { | |
117 | self.has_type_flags(TypeFlags::HAS_LATE_BOUND - TypeFlags::HAS_RE_LATE_BOUND) | |
118 | } | |
119 | /// True if there are any late-bound variables | |
120 | fn has_late_bound_vars(&self) -> bool { | |
121 | self.has_type_flags(TypeFlags::HAS_LATE_BOUND) | |
122 | } | |
064997fb FG |
123 | |
124 | /// Indicates whether this value still has parameters/placeholders/inference variables | |
125 | /// which could be replaced later, in a way that would change the results of `impl` | |
126 | /// specialization. | |
127 | fn still_further_specializable(&self) -> bool { | |
128 | self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE) | |
129 | } | |
130 | } | |
131 | ||
9ffffee4 | 132 | impl<'tcx, T: TypeVisitable<TyCtxt<'tcx>>> TypeVisitableExt<'tcx> for T {} |
064997fb FG |
133 | |
134 | /////////////////////////////////////////////////////////////////////////// | |
135 | // Region folder | |
136 | ||
137 | impl<'tcx> TyCtxt<'tcx> { | |
138 | /// Invoke `callback` on every region appearing free in `value`. | |
139 | pub fn for_each_free_region( | |
140 | self, | |
9ffffee4 | 141 | value: &impl TypeVisitable<TyCtxt<'tcx>>, |
064997fb FG |
142 | mut callback: impl FnMut(ty::Region<'tcx>), |
143 | ) { | |
144 | self.any_free_region_meets(value, |r| { | |
145 | callback(r); | |
146 | false | |
147 | }); | |
148 | } | |
149 | ||
150 | /// Returns `true` if `callback` returns true for every region appearing free in `value`. | |
151 | pub fn all_free_regions_meet( | |
152 | self, | |
9ffffee4 | 153 | value: &impl TypeVisitable<TyCtxt<'tcx>>, |
064997fb FG |
154 | mut callback: impl FnMut(ty::Region<'tcx>) -> bool, |
155 | ) -> bool { | |
156 | !self.any_free_region_meets(value, |r| !callback(r)) | |
157 | } | |
158 | ||
159 | /// Returns `true` if `callback` returns true for some region appearing free in `value`. | |
160 | pub fn any_free_region_meets( | |
161 | self, | |
9ffffee4 | 162 | value: &impl TypeVisitable<TyCtxt<'tcx>>, |
064997fb FG |
163 | callback: impl FnMut(ty::Region<'tcx>) -> bool, |
164 | ) -> bool { | |
165 | struct RegionVisitor<F> { | |
166 | /// The index of a binder *just outside* the things we have | |
167 | /// traversed. If we encounter a bound region bound by this | |
168 | /// binder or one outer to it, it appears free. Example: | |
169 | /// | |
170 | /// ```ignore (illustrative) | |
171 | /// for<'a> fn(for<'b> fn(), T) | |
172 | /// // ^ ^ ^ ^ | |
173 | /// // | | | | here, would be shifted in 1 | |
174 | /// // | | | here, would be shifted in 2 | |
175 | /// // | | here, would be `INNERMOST` shifted in by 1 | |
176 | /// // | here, initially, binder would be `INNERMOST` | |
177 | /// ``` | |
178 | /// | |
179 | /// You see that, initially, *any* bound value is free, | |
180 | /// because we've not traversed any binders. As we pass | |
181 | /// through a binder, we shift the `outer_index` by 1 to | |
182 | /// account for the new binder that encloses us. | |
183 | outer_index: ty::DebruijnIndex, | |
184 | callback: F, | |
185 | } | |
186 | ||
9ffffee4 | 187 | impl<'tcx, F> TypeVisitor<TyCtxt<'tcx>> for RegionVisitor<F> |
064997fb FG |
188 | where |
189 | F: FnMut(ty::Region<'tcx>) -> bool, | |
190 | { | |
191 | type BreakTy = (); | |
192 | ||
9ffffee4 | 193 | fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>( |
064997fb FG |
194 | &mut self, |
195 | t: &Binder<'tcx, T>, | |
196 | ) -> ControlFlow<Self::BreakTy> { | |
197 | self.outer_index.shift_in(1); | |
198 | let result = t.super_visit_with(self); | |
199 | self.outer_index.shift_out(1); | |
200 | result | |
201 | } | |
202 | ||
203 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
204 | match *r { | |
205 | ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => { | |
9c376795 | 206 | ControlFlow::Continue(()) |
064997fb FG |
207 | } |
208 | _ => { | |
209 | if (self.callback)(r) { | |
9c376795 | 210 | ControlFlow::Break(()) |
064997fb | 211 | } else { |
9c376795 | 212 | ControlFlow::Continue(()) |
064997fb FG |
213 | } |
214 | } | |
215 | } | |
216 | } | |
217 | ||
218 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
219 | // We're only interested in types involving regions | |
220 | if ty.flags().intersects(TypeFlags::HAS_FREE_REGIONS) { | |
221 | ty.super_visit_with(self) | |
222 | } else { | |
9c376795 | 223 | ControlFlow::Continue(()) |
064997fb FG |
224 | } |
225 | } | |
226 | } | |
227 | ||
228 | value.visit_with(&mut RegionVisitor { outer_index: ty::INNERMOST, callback }).is_break() | |
229 | } | |
230 | ||
231 | /// Returns a set of all late-bound regions that are constrained | |
232 | /// by `value`, meaning that if we instantiate those LBR with | |
233 | /// variables and equate `value` with something else, those | |
234 | /// variables will also be equated. | |
235 | pub fn collect_constrained_late_bound_regions<T>( | |
236 | self, | |
237 | value: &Binder<'tcx, T>, | |
238 | ) -> FxHashSet<ty::BoundRegionKind> | |
239 | where | |
9ffffee4 | 240 | T: TypeVisitable<TyCtxt<'tcx>>, |
064997fb FG |
241 | { |
242 | self.collect_late_bound_regions(value, true) | |
243 | } | |
244 | ||
245 | /// Returns a set of all late-bound regions that appear in `value` anywhere. | |
246 | pub fn collect_referenced_late_bound_regions<T>( | |
247 | self, | |
248 | value: &Binder<'tcx, T>, | |
249 | ) -> FxHashSet<ty::BoundRegionKind> | |
250 | where | |
9ffffee4 | 251 | T: TypeVisitable<TyCtxt<'tcx>>, |
064997fb FG |
252 | { |
253 | self.collect_late_bound_regions(value, false) | |
254 | } | |
255 | ||
256 | fn collect_late_bound_regions<T>( | |
257 | self, | |
258 | value: &Binder<'tcx, T>, | |
259 | just_constraint: bool, | |
260 | ) -> FxHashSet<ty::BoundRegionKind> | |
261 | where | |
9ffffee4 | 262 | T: TypeVisitable<TyCtxt<'tcx>>, |
064997fb FG |
263 | { |
264 | let mut collector = LateBoundRegionsCollector::new(just_constraint); | |
265 | let result = value.as_ref().skip_binder().visit_with(&mut collector); | |
266 | assert!(result.is_continue()); // should never have stopped early | |
267 | collector.regions | |
268 | } | |
269 | } | |
270 | ||
271 | pub struct ValidateBoundVars<'tcx> { | |
272 | bound_vars: &'tcx ty::List<ty::BoundVariableKind>, | |
273 | binder_index: ty::DebruijnIndex, | |
274 | // We may encounter the same variable at different levels of binding, so | |
275 | // this can't just be `Ty` | |
276 | visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>, | |
277 | } | |
278 | ||
279 | impl<'tcx> ValidateBoundVars<'tcx> { | |
280 | pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self { | |
281 | ValidateBoundVars { | |
282 | bound_vars, | |
283 | binder_index: ty::INNERMOST, | |
284 | visited: SsoHashSet::default(), | |
285 | } | |
286 | } | |
287 | } | |
288 | ||
9ffffee4 | 289 | impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ValidateBoundVars<'tcx> { |
064997fb FG |
290 | type BreakTy = (); |
291 | ||
9ffffee4 | 292 | fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>( |
064997fb FG |
293 | &mut self, |
294 | t: &Binder<'tcx, T>, | |
295 | ) -> ControlFlow<Self::BreakTy> { | |
296 | self.binder_index.shift_in(1); | |
297 | let result = t.super_visit_with(self); | |
298 | self.binder_index.shift_out(1); | |
299 | result | |
300 | } | |
301 | ||
302 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
303 | if t.outer_exclusive_binder() < self.binder_index | |
304 | || !self.visited.insert((self.binder_index, t)) | |
305 | { | |
9c376795 | 306 | return ControlFlow::Break(()); |
064997fb FG |
307 | } |
308 | match *t.kind() { | |
309 | ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => { | |
310 | if self.bound_vars.len() <= bound_ty.var.as_usize() { | |
311 | bug!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars); | |
312 | } | |
313 | let list_var = self.bound_vars[bound_ty.var.as_usize()]; | |
314 | match list_var { | |
315 | ty::BoundVariableKind::Ty(kind) => { | |
316 | if kind != bound_ty.kind { | |
317 | bug!( | |
318 | "Mismatched type kinds: {:?} doesn't var in list {:?}", | |
319 | bound_ty.kind, | |
320 | list_var | |
321 | ); | |
322 | } | |
323 | } | |
324 | _ => { | |
325 | bug!("Mismatched bound variable kinds! Expected type, found {:?}", list_var) | |
326 | } | |
327 | } | |
328 | } | |
329 | ||
330 | _ => (), | |
331 | }; | |
332 | ||
333 | t.super_visit_with(self) | |
334 | } | |
335 | ||
336 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
337 | match *r { | |
338 | ty::ReLateBound(index, br) if index == self.binder_index => { | |
339 | if self.bound_vars.len() <= br.var.as_usize() { | |
340 | bug!("Not enough bound vars: {:?} not found in {:?}", br, self.bound_vars); | |
341 | } | |
342 | let list_var = self.bound_vars[br.var.as_usize()]; | |
343 | match list_var { | |
344 | ty::BoundVariableKind::Region(kind) => { | |
345 | if kind != br.kind { | |
346 | bug!( | |
347 | "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})", | |
348 | br.kind, | |
349 | list_var, | |
350 | self.bound_vars | |
351 | ); | |
352 | } | |
353 | } | |
354 | _ => bug!( | |
355 | "Mismatched bound variable kinds! Expected region, found {:?}", | |
356 | list_var | |
357 | ), | |
358 | } | |
359 | } | |
360 | ||
361 | _ => (), | |
362 | }; | |
363 | ||
364 | r.super_visit_with(self) | |
365 | } | |
366 | } | |
367 | ||
368 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] | |
369 | struct FoundEscapingVars; | |
370 | ||
371 | /// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a | |
372 | /// bound region or a bound type. | |
373 | /// | |
374 | /// So, for example, consider a type like the following, which has two binders: | |
375 | /// | |
376 | /// for<'a> fn(x: for<'b> fn(&'a isize, &'b isize)) | |
377 | /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope | |
378 | /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ inner scope | |
379 | /// | |
380 | /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the | |
381 | /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner | |
382 | /// fn type*, that type has an escaping region: `'a`. | |
383 | /// | |
384 | /// Note that what I'm calling an "escaping var" is often just called a "free var". However, | |
385 | /// we already use the term "free var". It refers to the regions or types that we use to represent | |
386 | /// bound regions or type params on a fn definition while we are type checking its body. | |
387 | /// | |
388 | /// To clarify, conceptually there is no particular difference between | |
389 | /// an "escaping" var and a "free" var. However, there is a big | |
390 | /// difference in practice. Basically, when "entering" a binding | |
391 | /// level, one is generally required to do some sort of processing to | |
392 | /// a bound var, such as replacing it with a fresh/placeholder | |
393 | /// var, or making an entry in the environment to represent the | |
394 | /// scope to which it is attached, etc. An escaping var represents | |
395 | /// a bound var for which this processing has not yet been done. | |
396 | struct HasEscapingVarsVisitor { | |
397 | /// Anything bound by `outer_index` or "above" is escaping. | |
398 | outer_index: ty::DebruijnIndex, | |
399 | } | |
400 | ||
9ffffee4 | 401 | impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for HasEscapingVarsVisitor { |
064997fb FG |
402 | type BreakTy = FoundEscapingVars; |
403 | ||
9ffffee4 | 404 | fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>( |
064997fb FG |
405 | &mut self, |
406 | t: &Binder<'tcx, T>, | |
407 | ) -> ControlFlow<Self::BreakTy> { | |
408 | self.outer_index.shift_in(1); | |
409 | let result = t.super_visit_with(self); | |
410 | self.outer_index.shift_out(1); | |
411 | result | |
412 | } | |
413 | ||
414 | #[inline] | |
415 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
416 | // If the outer-exclusive-binder is *strictly greater* than | |
417 | // `outer_index`, that means that `t` contains some content | |
418 | // bound at `outer_index` or above (because | |
419 | // `outer_exclusive_binder` is always 1 higher than the | |
420 | // content in `t`). Therefore, `t` has some escaping vars. | |
421 | if t.outer_exclusive_binder() > self.outer_index { | |
422 | ControlFlow::Break(FoundEscapingVars) | |
423 | } else { | |
9c376795 | 424 | ControlFlow::Continue(()) |
064997fb FG |
425 | } |
426 | } | |
427 | ||
428 | #[inline] | |
429 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
430 | // If the region is bound by `outer_index` or anything outside | |
431 | // of outer index, then it escapes the binders we have | |
432 | // visited. | |
433 | if r.bound_at_or_above_binder(self.outer_index) { | |
434 | ControlFlow::Break(FoundEscapingVars) | |
435 | } else { | |
9c376795 | 436 | ControlFlow::Continue(()) |
064997fb FG |
437 | } |
438 | } | |
439 | ||
440 | fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { | |
441 | // we don't have a `visit_infer_const` callback, so we have to | |
442 | // hook in here to catch this case (annoying...), but | |
443 | // otherwise we do want to remember to visit the rest of the | |
444 | // const, as it has types/regions embedded in a lot of other | |
445 | // places. | |
446 | match ct.kind() { | |
447 | ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => { | |
448 | ControlFlow::Break(FoundEscapingVars) | |
449 | } | |
450 | _ => ct.super_visit_with(self), | |
451 | } | |
452 | } | |
453 | ||
454 | #[inline] | |
455 | fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> { | |
456 | if predicate.outer_exclusive_binder() > self.outer_index { | |
457 | ControlFlow::Break(FoundEscapingVars) | |
458 | } else { | |
9c376795 | 459 | ControlFlow::Continue(()) |
064997fb FG |
460 | } |
461 | } | |
462 | } | |
463 | ||
464 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] | |
465 | struct FoundFlags; | |
466 | ||
467 | // FIXME: Optimize for checking for infer flags | |
468 | struct HasTypeFlagsVisitor { | |
469 | flags: ty::TypeFlags, | |
470 | } | |
471 | ||
472 | impl std::fmt::Debug for HasTypeFlagsVisitor { | |
473 | fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { | |
474 | self.flags.fmt(fmt) | |
475 | } | |
476 | } | |
477 | ||
9ffffee4 | 478 | impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for HasTypeFlagsVisitor { |
064997fb FG |
479 | type BreakTy = FoundFlags; |
480 | ||
481 | #[inline] | |
064997fb FG |
482 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
483 | let flags = t.flags(); | |
064997fb FG |
484 | if flags.intersects(self.flags) { |
485 | ControlFlow::Break(FoundFlags) | |
486 | } else { | |
9c376795 | 487 | ControlFlow::Continue(()) |
064997fb FG |
488 | } |
489 | } | |
490 | ||
491 | #[inline] | |
064997fb FG |
492 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { |
493 | let flags = r.type_flags(); | |
064997fb FG |
494 | if flags.intersects(self.flags) { |
495 | ControlFlow::Break(FoundFlags) | |
496 | } else { | |
9c376795 | 497 | ControlFlow::Continue(()) |
064997fb FG |
498 | } |
499 | } | |
500 | ||
501 | #[inline] | |
064997fb FG |
502 | fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
503 | let flags = FlagComputation::for_const(c); | |
504 | trace!(r.flags=?flags); | |
505 | if flags.intersects(self.flags) { | |
506 | ControlFlow::Break(FoundFlags) | |
507 | } else { | |
9c376795 | 508 | ControlFlow::Continue(()) |
064997fb FG |
509 | } |
510 | } | |
511 | ||
064997fb | 512 | #[inline] |
064997fb | 513 | fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> { |
064997fb FG |
514 | if predicate.flags().intersects(self.flags) { |
515 | ControlFlow::Break(FoundFlags) | |
516 | } else { | |
9c376795 | 517 | ControlFlow::Continue(()) |
064997fb FG |
518 | } |
519 | } | |
520 | } | |
521 | ||
522 | /// Collects all the late-bound regions at the innermost binding level | |
523 | /// into a hash set. | |
524 | struct LateBoundRegionsCollector { | |
525 | current_index: ty::DebruijnIndex, | |
526 | regions: FxHashSet<ty::BoundRegionKind>, | |
527 | ||
528 | /// `true` if we only want regions that are known to be | |
529 | /// "constrained" when you equate this type with another type. In | |
530 | /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating | |
531 | /// them constraints `'a == 'b`. But if you have `<&'a u32 as | |
532 | /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those | |
533 | /// types may mean that `'a` and `'b` don't appear in the results, | |
534 | /// so they are not considered *constrained*. | |
535 | just_constrained: bool, | |
536 | } | |
537 | ||
538 | impl LateBoundRegionsCollector { | |
539 | fn new(just_constrained: bool) -> Self { | |
540 | LateBoundRegionsCollector { | |
541 | current_index: ty::INNERMOST, | |
542 | regions: Default::default(), | |
543 | just_constrained, | |
544 | } | |
545 | } | |
546 | } | |
547 | ||
9ffffee4 FG |
548 | impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for LateBoundRegionsCollector { |
549 | fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>( | |
064997fb FG |
550 | &mut self, |
551 | t: &Binder<'tcx, T>, | |
552 | ) -> ControlFlow<Self::BreakTy> { | |
553 | self.current_index.shift_in(1); | |
554 | let result = t.super_visit_with(self); | |
555 | self.current_index.shift_out(1); | |
556 | result | |
557 | } | |
558 | ||
559 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { | |
560 | // if we are only looking for "constrained" region, we have to | |
561 | // ignore the inputs to a projection, as they may not appear | |
562 | // in the normalized form | |
563 | if self.just_constrained { | |
9c376795 FG |
564 | if let ty::Alias(..) = t.kind() { |
565 | return ControlFlow::Continue(()); | |
064997fb FG |
566 | } |
567 | } | |
568 | ||
569 | t.super_visit_with(self) | |
570 | } | |
571 | ||
572 | fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { | |
573 | // if we are only looking for "constrained" region, we have to | |
574 | // ignore the inputs of an unevaluated const, as they may not appear | |
575 | // in the normalized form | |
576 | if self.just_constrained { | |
577 | if let ty::ConstKind::Unevaluated(..) = c.kind() { | |
9c376795 | 578 | return ControlFlow::Continue(()); |
064997fb FG |
579 | } |
580 | } | |
581 | ||
582 | c.super_visit_with(self) | |
583 | } | |
584 | ||
585 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
586 | if let ty::ReLateBound(debruijn, br) = *r { | |
587 | if debruijn == self.current_index { | |
588 | self.regions.insert(br.kind); | |
589 | } | |
590 | } | |
9c376795 | 591 | ControlFlow::Continue(()) |
064997fb FG |
592 | } |
593 | } | |
594 | ||
595 | /// Finds the max universe present | |
596 | pub struct MaxUniverse { | |
597 | max_universe: ty::UniverseIndex, | |
598 | } | |
599 | ||
600 | impl MaxUniverse { | |
601 | pub fn new() -> Self { | |
602 | MaxUniverse { max_universe: ty::UniverseIndex::ROOT } | |
603 | } | |
604 | ||
605 | pub fn max_universe(self) -> ty::UniverseIndex { | |
606 | self.max_universe | |
607 | } | |
608 | } | |
609 | ||
9ffffee4 | 610 | impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxUniverse { |
064997fb FG |
611 | fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
612 | if let ty::Placeholder(placeholder) = t.kind() { | |
613 | self.max_universe = ty::UniverseIndex::from_u32( | |
614 | self.max_universe.as_u32().max(placeholder.universe.as_u32()), | |
615 | ); | |
616 | } | |
617 | ||
618 | t.super_visit_with(self) | |
619 | } | |
620 | ||
621 | fn visit_const(&mut self, c: ty::consts::Const<'tcx>) -> ControlFlow<Self::BreakTy> { | |
622 | if let ty::ConstKind::Placeholder(placeholder) = c.kind() { | |
623 | self.max_universe = ty::UniverseIndex::from_u32( | |
624 | self.max_universe.as_u32().max(placeholder.universe.as_u32()), | |
625 | ); | |
626 | } | |
627 | ||
628 | c.super_visit_with(self) | |
629 | } | |
630 | ||
631 | fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
632 | if let ty::RePlaceholder(placeholder) = *r { | |
633 | self.max_universe = ty::UniverseIndex::from_u32( | |
634 | self.max_universe.as_u32().max(placeholder.universe.as_u32()), | |
635 | ); | |
636 | } | |
637 | ||
9c376795 | 638 | ControlFlow::Continue(()) |
064997fb FG |
639 | } |
640 | } |