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