compiler/rustc_middle/src/ty/visit.rs

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