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", ret)]
  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_non_region_param(&self) -> bool {
 108         self.has_type_flags(TypeFlags::NEEDS_SUBST - TypeFlags::HAS_RE_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_non_region_infer(&self) -> bool {
 117         self.has_type_flags(TypeFlags::NEEDS_INFER - TypeFlags::HAS_RE_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_ty_unevaluated(
 203         &mut self,
 204         uv: ty::UnevaluatedConst<'tcx>,
 205     ) -> ControlFlow<Self::BreakTy> {
 206         uv.super_visit_with(self)
 207     }
 208
 209     fn visit_mir_unevaluated(
 210         &mut self,
 211         uv: mir::UnevaluatedConst<'tcx>,
 212     ) -> ControlFlow<Self::BreakTy> {
 213         uv.super_visit_with(self)
 214     }
 215
 216     fn visit_predicate(&mut self, p: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 217         p.super_visit_with(self)
 218     }
 219
 220     fn visit_mir_const(&mut self, c: mir::ConstantKind<'tcx>) -> ControlFlow<Self::BreakTy> {
 221         c.super_visit_with(self)
 222     }
 223 }
 224
 225 ///////////////////////////////////////////////////////////////////////////
 226 // Region folder
 227
 228 impl<'tcx> TyCtxt<'tcx> {
 229     /// Invoke `callback` on every region appearing free in `value`.
 230     pub fn for_each_free_region(
 231         self,
 232         value: &impl TypeVisitable<'tcx>,
 233         mut callback: impl FnMut(ty::Region<'tcx>),
 234     ) {
 235         self.any_free_region_meets(value, |r| {
 236             callback(r);
 237             false
 238         });
 239     }
 240
 241     /// Returns `true` if `callback` returns true for every region appearing free in `value`.
 242     pub fn all_free_regions_meet(
 243         self,
 244         value: &impl TypeVisitable<'tcx>,
 245         mut callback: impl FnMut(ty::Region<'tcx>) -> bool,
 246     ) -> bool {
 247         !self.any_free_region_meets(value, |r| !callback(r))
 248     }
 249
 250     /// Returns `true` if `callback` returns true for some region appearing free in `value`.
 251     pub fn any_free_region_meets(
 252         self,
 253         value: &impl TypeVisitable<'tcx>,
 254         callback: impl FnMut(ty::Region<'tcx>) -> bool,
 255     ) -> bool {
 256         struct RegionVisitor<F> {
 257             /// The index of a binder *just outside* the things we have
 258             /// traversed. If we encounter a bound region bound by this
 259             /// binder or one outer to it, it appears free. Example:
 260             ///
 261             /// ```ignore (illustrative)
 262             ///       for<'a> fn(for<'b> fn(), T)
 263             /// // ^          ^          ^     ^
 264             /// // |          |          |     | here, would be shifted in 1
 265             /// // |          |          | here, would be shifted in 2
 266             /// // |          | here, would be `INNERMOST` shifted in by 1
 267             /// // | here, initially, binder would be `INNERMOST`
 268             /// ```
 269             ///
 270             /// You see that, initially, *any* bound value is free,
 271             /// because we've not traversed any binders. As we pass
 272             /// through a binder, we shift the `outer_index` by 1 to
 273             /// account for the new binder that encloses us.
 274             outer_index: ty::DebruijnIndex,
 275             callback: F,
 276         }
 277
 278         impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<F>
 279         where
 280             F: FnMut(ty::Region<'tcx>) -> bool,
 281         {
 282             type BreakTy = ();
 283
 284             fn visit_binder<T: TypeVisitable<'tcx>>(
 285                 &mut self,
 286                 t: &Binder<'tcx, T>,
 287             ) -> ControlFlow<Self::BreakTy> {
 288                 self.outer_index.shift_in(1);
 289                 let result = t.super_visit_with(self);
 290                 self.outer_index.shift_out(1);
 291                 result
 292             }
 293
 294             fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 295                 match *r {
 296                     ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => {
 297                         ControlFlow::CONTINUE
 298                     }
 299                     _ => {
 300                         if (self.callback)(r) {
 301                             ControlFlow::BREAK
 302                         } else {
 303                             ControlFlow::CONTINUE
 304                         }
 305                     }
 306                 }
 307             }
 308
 309             fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 310                 // We're only interested in types involving regions
 311                 if ty.flags().intersects(TypeFlags::HAS_FREE_REGIONS) {
 312                     ty.super_visit_with(self)
 313                 } else {
 314                     ControlFlow::CONTINUE
 315                 }
 316             }
 317         }
 318
 319         value.visit_with(&mut RegionVisitor { outer_index: ty::INNERMOST, callback }).is_break()
 320     }
 321
 322     /// Returns a set of all late-bound regions that are constrained
 323     /// by `value`, meaning that if we instantiate those LBR with
 324     /// variables and equate `value` with something else, those
 325     /// variables will also be equated.
 326     pub fn collect_constrained_late_bound_regions<T>(
 327         self,
 328         value: &Binder<'tcx, T>,
 329     ) -> FxHashSet<ty::BoundRegionKind>
 330     where
 331         T: TypeVisitable<'tcx>,
 332     {
 333         self.collect_late_bound_regions(value, true)
 334     }
 335
 336     /// Returns a set of all late-bound regions that appear in `value` anywhere.
 337     pub fn collect_referenced_late_bound_regions<T>(
 338         self,
 339         value: &Binder<'tcx, T>,
 340     ) -> FxHashSet<ty::BoundRegionKind>
 341     where
 342         T: TypeVisitable<'tcx>,
 343     {
 344         self.collect_late_bound_regions(value, false)
 345     }
 346
 347     fn collect_late_bound_regions<T>(
 348         self,
 349         value: &Binder<'tcx, T>,
 350         just_constraint: bool,
 351     ) -> FxHashSet<ty::BoundRegionKind>
 352     where
 353         T: TypeVisitable<'tcx>,
 354     {
 355         let mut collector = LateBoundRegionsCollector::new(just_constraint);
 356         let result = value.as_ref().skip_binder().visit_with(&mut collector);
 357         assert!(result.is_continue()); // should never have stopped early
 358         collector.regions
 359     }
 360 }
 361
 362 pub struct ValidateBoundVars<'tcx> {
 363     bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
 364     binder_index: ty::DebruijnIndex,
 365     // We may encounter the same variable at different levels of binding, so
 366     // this can't just be `Ty`
 367     visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>,
 368 }
 369
 370 impl<'tcx> ValidateBoundVars<'tcx> {
 371     pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self {
 372         ValidateBoundVars {
 373             bound_vars,
 374             binder_index: ty::INNERMOST,
 375             visited: SsoHashSet::default(),
 376         }
 377     }
 378 }
 379
 380 impl<'tcx> TypeVisitor<'tcx> for ValidateBoundVars<'tcx> {
 381     type BreakTy = ();
 382
 383     fn visit_binder<T: TypeVisitable<'tcx>>(
 384         &mut self,
 385         t: &Binder<'tcx, T>,
 386     ) -> ControlFlow<Self::BreakTy> {
 387         self.binder_index.shift_in(1);
 388         let result = t.super_visit_with(self);
 389         self.binder_index.shift_out(1);
 390         result
 391     }
 392
 393     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 394         if t.outer_exclusive_binder() < self.binder_index
 395             || !self.visited.insert((self.binder_index, t))
 396         {
 397             return ControlFlow::BREAK;
 398         }
 399         match *t.kind() {
 400             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 401                 if self.bound_vars.len() <= bound_ty.var.as_usize() {
 402                     bug!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
 403                 }
 404                 let list_var = self.bound_vars[bound_ty.var.as_usize()];
 405                 match list_var {
 406                     ty::BoundVariableKind::Ty(kind) => {
 407                         if kind != bound_ty.kind {
 408                             bug!(
 409                                 "Mismatched type kinds: {:?} doesn't var in list {:?}",
 410                                 bound_ty.kind,
 411                                 list_var
 412                             );
 413                         }
 414                     }
 415                     _ => {
 416                         bug!("Mismatched bound variable kinds! Expected type, found {:?}", list_var)
 417                     }
 418                 }
 419             }
 420
 421             _ => (),
 422         };
 423
 424         t.super_visit_with(self)
 425     }
 426
 427     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 428         match *r {
 429             ty::ReLateBound(index, br) if index == self.binder_index => {
 430                 if self.bound_vars.len() <= br.var.as_usize() {
 431                     bug!("Not enough bound vars: {:?} not found in {:?}", br, self.bound_vars);
 432                 }
 433                 let list_var = self.bound_vars[br.var.as_usize()];
 434                 match list_var {
 435                     ty::BoundVariableKind::Region(kind) => {
 436                         if kind != br.kind {
 437                             bug!(
 438                                 "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})",
 439                                 br.kind,
 440                                 list_var,
 441                                 self.bound_vars
 442                             );
 443                         }
 444                     }
 445                     _ => bug!(
 446                         "Mismatched bound variable kinds! Expected region, found {:?}",
 447                         list_var
 448                     ),
 449                 }
 450             }
 451
 452             _ => (),
 453         };
 454
 455         r.super_visit_with(self)
 456     }
 457 }
 458
 459 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 460 struct FoundEscapingVars;
 461
 462 /// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a
 463 /// bound region or a bound type.
 464 ///
 465 /// So, for example, consider a type like the following, which has two binders:
 466 ///
 467 ///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
 468 ///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
 469 ///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
 470 ///
 471 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
 472 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
 473 /// fn type*, that type has an escaping region: `'a`.
 474 ///
 475 /// Note that what I'm calling an "escaping var" is often just called a "free var". However,
 476 /// we already use the term "free var". It refers to the regions or types that we use to represent
 477 /// bound regions or type params on a fn definition while we are type checking its body.
 478 ///
 479 /// To clarify, conceptually there is no particular difference between
 480 /// an "escaping" var and a "free" var. However, there is a big
 481 /// difference in practice. Basically, when "entering" a binding
 482 /// level, one is generally required to do some sort of processing to
 483 /// a bound var, such as replacing it with a fresh/placeholder
 484 /// var, or making an entry in the environment to represent the
 485 /// scope to which it is attached, etc. An escaping var represents
 486 /// a bound var for which this processing has not yet been done.
 487 struct HasEscapingVarsVisitor {
 488     /// Anything bound by `outer_index` or "above" is escaping.
 489     outer_index: ty::DebruijnIndex,
 490 }
 491
 492 impl<'tcx> TypeVisitor<'tcx> for HasEscapingVarsVisitor {
 493     type BreakTy = FoundEscapingVars;
 494
 495     fn visit_binder<T: TypeVisitable<'tcx>>(
 496         &mut self,
 497         t: &Binder<'tcx, T>,
 498     ) -> ControlFlow<Self::BreakTy> {
 499         self.outer_index.shift_in(1);
 500         let result = t.super_visit_with(self);
 501         self.outer_index.shift_out(1);
 502         result
 503     }
 504
 505     #[inline]
 506     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 507         // If the outer-exclusive-binder is *strictly greater* than
 508         // `outer_index`, that means that `t` contains some content
 509         // bound at `outer_index` or above (because
 510         // `outer_exclusive_binder` is always 1 higher than the
 511         // content in `t`). Therefore, `t` has some escaping vars.
 512         if t.outer_exclusive_binder() > self.outer_index {
 513             ControlFlow::Break(FoundEscapingVars)
 514         } else {
 515             ControlFlow::CONTINUE
 516         }
 517     }
 518
 519     #[inline]
 520     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 521         // If the region is bound by `outer_index` or anything outside
 522         // of outer index, then it escapes the binders we have
 523         // visited.
 524         if r.bound_at_or_above_binder(self.outer_index) {
 525             ControlFlow::Break(FoundEscapingVars)
 526         } else {
 527             ControlFlow::CONTINUE
 528         }
 529     }
 530
 531     fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 532         // we don't have a `visit_infer_const` callback, so we have to
 533         // hook in here to catch this case (annoying...), but
 534         // otherwise we do want to remember to visit the rest of the
 535         // const, as it has types/regions embedded in a lot of other
 536         // places.
 537         match ct.kind() {
 538             ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
 539                 ControlFlow::Break(FoundEscapingVars)
 540             }
 541             _ => ct.super_visit_with(self),
 542         }
 543     }
 544
 545     #[inline]
 546     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 547         if predicate.outer_exclusive_binder() > self.outer_index {
 548             ControlFlow::Break(FoundEscapingVars)
 549         } else {
 550             ControlFlow::CONTINUE
 551         }
 552     }
 553 }
 554
 555 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 556 struct FoundFlags;
 557
 558 // FIXME: Optimize for checking for infer flags
 559 struct HasTypeFlagsVisitor {
 560     flags: ty::TypeFlags,
 561 }
 562
 563 impl std::fmt::Debug for HasTypeFlagsVisitor {
 564     fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 565         self.flags.fmt(fmt)
 566     }
 567 }
 568
 569 impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor {
 570     type BreakTy = FoundFlags;
 571
 572     #[inline]
 573     #[instrument(skip(self), level = "trace", ret)]
 574     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 575         let flags = t.flags();
 576         trace!(t.flags=?t.flags());
 577         if flags.intersects(self.flags) {
 578             ControlFlow::Break(FoundFlags)
 579         } else {
 580             ControlFlow::CONTINUE
 581         }
 582     }
 583
 584     #[inline]
 585     #[instrument(skip(self), level = "trace", ret)]
 586     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 587         let flags = r.type_flags();
 588         trace!(r.flags=?flags);
 589         if flags.intersects(self.flags) {
 590             ControlFlow::Break(FoundFlags)
 591         } else {
 592             ControlFlow::CONTINUE
 593         }
 594     }
 595
 596     #[inline]
 597     #[instrument(level = "trace", ret)]
 598     fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 599         let flags = FlagComputation::for_const(c);
 600         trace!(r.flags=?flags);
 601         if flags.intersects(self.flags) {
 602             ControlFlow::Break(FoundFlags)
 603         } else {
 604             ControlFlow::CONTINUE
 605         }
 606     }
 607
 608     #[inline]
 609     #[instrument(level = "trace", ret)]
 610     fn visit_ty_unevaluated(
 611         &mut self,
 612         uv: ty::UnevaluatedConst<'tcx>,
 613     ) -> ControlFlow<Self::BreakTy> {
 614         let flags = FlagComputation::for_unevaluated_const(uv);
 615         trace!(r.flags=?flags);
 616         if flags.intersects(self.flags) {
 617             ControlFlow::Break(FoundFlags)
 618         } else {
 619             ControlFlow::CONTINUE
 620         }
 621     }
 622
 623     fn visit_mir_unevaluated(
 624         &mut self,
 625         uv: mir::UnevaluatedConst<'tcx>,
 626     ) -> ControlFlow<Self::BreakTy> {
 627         let flags = FlagComputation::for_unevaluated_const(uv.shrink());
 628         trace!(r.flags=?flags);
 629         if flags.intersects(self.flags) {
 630             ControlFlow::Break(FoundFlags)
 631         } else {
 632             ControlFlow::CONTINUE
 633         }
 634     }
 635
 636     #[inline]
 637     #[instrument(level = "trace", ret)]
 638     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 639         debug!(
 640             "HasTypeFlagsVisitor: predicate={:?} predicate.flags={:?} self.flags={:?}",
 641             predicate,
 642             predicate.flags(),
 643             self.flags
 644         );
 645         if predicate.flags().intersects(self.flags) {
 646             ControlFlow::Break(FoundFlags)
 647         } else {
 648             ControlFlow::CONTINUE
 649         }
 650     }
 651 }
 652
 653 /// Collects all the late-bound regions at the innermost binding level
 654 /// into a hash set.
 655 struct LateBoundRegionsCollector {
 656     current_index: ty::DebruijnIndex,
 657     regions: FxHashSet<ty::BoundRegionKind>,
 658
 659     /// `true` if we only want regions that are known to be
 660     /// "constrained" when you equate this type with another type. In
 661     /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
 662     /// them constraints `'a == 'b`. But if you have `<&'a u32 as
 663     /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
 664     /// types may mean that `'a` and `'b` don't appear in the results,
 665     /// so they are not considered *constrained*.
 666     just_constrained: bool,
 667 }
 668
 669 impl LateBoundRegionsCollector {
 670     fn new(just_constrained: bool) -> Self {
 671         LateBoundRegionsCollector {
 672             current_index: ty::INNERMOST,
 673             regions: Default::default(),
 674             just_constrained,
 675         }
 676     }
 677 }
 678
 679 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
 680     fn visit_binder<T: TypeVisitable<'tcx>>(
 681         &mut self,
 682         t: &Binder<'tcx, T>,
 683     ) -> ControlFlow<Self::BreakTy> {
 684         self.current_index.shift_in(1);
 685         let result = t.super_visit_with(self);
 686         self.current_index.shift_out(1);
 687         result
 688     }
 689
 690     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 691         // if we are only looking for "constrained" region, we have to
 692         // ignore the inputs to a projection, as they may not appear
 693         // in the normalized form
 694         if self.just_constrained {
 695             if let ty::Projection(..) | ty::Opaque(..) = t.kind() {
 696                 return ControlFlow::CONTINUE;
 697             }
 698         }
 699
 700         t.super_visit_with(self)
 701     }
 702
 703     fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 704         // if we are only looking for "constrained" region, we have to
 705         // ignore the inputs of an unevaluated const, as they may not appear
 706         // in the normalized form
 707         if self.just_constrained {
 708             if let ty::ConstKind::Unevaluated(..) = c.kind() {
 709                 return ControlFlow::CONTINUE;
 710             }
 711         }
 712
 713         c.super_visit_with(self)
 714     }
 715
 716     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 717         if let ty::ReLateBound(debruijn, br) = *r {
 718             if debruijn == self.current_index {
 719                 self.regions.insert(br.kind);
 720             }
 721         }
 722         ControlFlow::CONTINUE
 723     }
 724 }
 725
 726 /// Finds the max universe present
 727 pub struct MaxUniverse {
 728     max_universe: ty::UniverseIndex,
 729 }
 730
 731 impl MaxUniverse {
 732     pub fn new() -> Self {
 733         MaxUniverse { max_universe: ty::UniverseIndex::ROOT }
 734     }
 735
 736     pub fn max_universe(self) -> ty::UniverseIndex {
 737         self.max_universe
 738     }
 739 }
 740
 741 impl<'tcx> TypeVisitor<'tcx> for MaxUniverse {
 742     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 743         if let ty::Placeholder(placeholder) = t.kind() {
 744             self.max_universe = ty::UniverseIndex::from_u32(
 745                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 746             );
 747         }
 748
 749         t.super_visit_with(self)
 750     }
 751
 752     fn visit_const(&mut self, c: ty::consts::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 753         if let ty::ConstKind::Placeholder(placeholder) = c.kind() {
 754             self.max_universe = ty::UniverseIndex::from_u32(
 755                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 756             );
 757         }
 758
 759         c.super_visit_with(self)
 760     }
 761
 762     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 763         if let ty::RePlaceholder(placeholder) = *r {
 764             self.max_universe = ty::UniverseIndex::from_u32(
 765                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 766             );
 767         }
 768
 769         ControlFlow::CONTINUE
 770     }
 771 }