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