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