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