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     /// True if there are any late-bound non-region variables
 169     fn has_non_region_late_bound(&self) -> bool {
 170         self.has_type_flags(TypeFlags::HAS_LATE_BOUND - TypeFlags::HAS_RE_LATE_BOUND)
 171     }
 172     /// True if there are any late-bound variables
 173     fn has_late_bound_vars(&self) -> bool {
 174         self.has_type_flags(TypeFlags::HAS_LATE_BOUND)
 175     }
 176
 177     /// Indicates whether this value still has parameters/placeholders/inference variables
 178     /// which could be replaced later, in a way that would change the results of `impl`
 179     /// specialization.
 180     fn still_further_specializable(&self) -> bool {
 181         self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE)
 182     }
 183 }
 184
 185 pub trait TypeSuperVisitable<'tcx>: TypeVisitable<'tcx> {
 186     /// Provides a default visit for a type of interest. This should only be
 187     /// called within `TypeVisitor` methods, when a non-custom traversal is
 188     /// desired for the value of the type of interest passed to that method.
 189     /// For example, in `MyVisitor::visit_ty(ty)`, it is valid to call
 190     /// `ty.super_visit_with(self)`, but any other visiting should be done
 191     /// with `xyz.visit_with(self)`.
 192     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
 193 }
 194
 195 /// This trait is implemented for every visiting traversal. There is a visit
 196 /// method defined for every type of interest. Each such method has a default
 197 /// that recurses into the type's fields in a non-custom fashion.
 198 pub trait TypeVisitor<'tcx>: Sized {
 199     type BreakTy = !;
 200
 201     fn visit_binder<T: TypeVisitable<'tcx>>(
 202         &mut self,
 203         t: &Binder<'tcx, T>,
 204     ) -> ControlFlow<Self::BreakTy> {
 205         t.super_visit_with(self)
 206     }
 207
 208     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 209         t.super_visit_with(self)
 210     }
 211
 212     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 213         r.super_visit_with(self)
 214     }
 215
 216     fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 217         c.super_visit_with(self)
 218     }
 219
 220     fn visit_predicate(&mut self, p: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 221         p.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     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 574         let flags = t.flags();
 575         if flags.intersects(self.flags) {
 576             ControlFlow::Break(FoundFlags)
 577         } else {
 578             ControlFlow::CONTINUE
 579         }
 580     }
 581
 582     #[inline]
 583     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 584         let flags = r.type_flags();
 585         if flags.intersects(self.flags) {
 586             ControlFlow::Break(FoundFlags)
 587         } else {
 588             ControlFlow::CONTINUE
 589         }
 590     }
 591
 592     #[inline]
 593     fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 594         let flags = FlagComputation::for_const(c);
 595         trace!(r.flags=?flags);
 596         if flags.intersects(self.flags) {
 597             ControlFlow::Break(FoundFlags)
 598         } else {
 599             ControlFlow::CONTINUE
 600         }
 601     }
 602
 603     #[inline]
 604     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 605         if predicate.flags().intersects(self.flags) {
 606             ControlFlow::Break(FoundFlags)
 607         } else {
 608             ControlFlow::CONTINUE
 609         }
 610     }
 611 }
 612
 613 /// Collects all the late-bound regions at the innermost binding level
 614 /// into a hash set.
 615 struct LateBoundRegionsCollector {
 616     current_index: ty::DebruijnIndex,
 617     regions: FxHashSet<ty::BoundRegionKind>,
 618
 619     /// `true` if we only want regions that are known to be
 620     /// "constrained" when you equate this type with another type. In
 621     /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
 622     /// them constraints `'a == 'b`. But if you have `<&'a u32 as
 623     /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
 624     /// types may mean that `'a` and `'b` don't appear in the results,
 625     /// so they are not considered *constrained*.
 626     just_constrained: bool,
 627 }
 628
 629 impl LateBoundRegionsCollector {
 630     fn new(just_constrained: bool) -> Self {
 631         LateBoundRegionsCollector {
 632             current_index: ty::INNERMOST,
 633             regions: Default::default(),
 634             just_constrained,
 635         }
 636     }
 637 }
 638
 639 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
 640     fn visit_binder<T: TypeVisitable<'tcx>>(
 641         &mut self,
 642         t: &Binder<'tcx, T>,
 643     ) -> ControlFlow<Self::BreakTy> {
 644         self.current_index.shift_in(1);
 645         let result = t.super_visit_with(self);
 646         self.current_index.shift_out(1);
 647         result
 648     }
 649
 650     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 651         // if we are only looking for "constrained" region, we have to
 652         // ignore the inputs to a projection, as they may not appear
 653         // in the normalized form
 654         if self.just_constrained {
 655             if let ty::Alias(..) = t.kind() {
 656                 return ControlFlow::CONTINUE;
 657             }
 658         }
 659
 660         t.super_visit_with(self)
 661     }
 662
 663     fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 664         // if we are only looking for "constrained" region, we have to
 665         // ignore the inputs of an unevaluated const, as they may not appear
 666         // in the normalized form
 667         if self.just_constrained {
 668             if let ty::ConstKind::Unevaluated(..) = c.kind() {
 669                 return ControlFlow::CONTINUE;
 670             }
 671         }
 672
 673         c.super_visit_with(self)
 674     }
 675
 676     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 677         if let ty::ReLateBound(debruijn, br) = *r {
 678             if debruijn == self.current_index {
 679                 self.regions.insert(br.kind);
 680             }
 681         }
 682         ControlFlow::CONTINUE
 683     }
 684 }
 685
 686 /// Finds the max universe present
 687 pub struct MaxUniverse {
 688     max_universe: ty::UniverseIndex,
 689 }
 690
 691 impl MaxUniverse {
 692     pub fn new() -> Self {
 693         MaxUniverse { max_universe: ty::UniverseIndex::ROOT }
 694     }
 695
 696     pub fn max_universe(self) -> ty::UniverseIndex {
 697         self.max_universe
 698     }
 699 }
 700
 701 impl<'tcx> TypeVisitor<'tcx> for MaxUniverse {
 702     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 703         if let ty::Placeholder(placeholder) = t.kind() {
 704             self.max_universe = ty::UniverseIndex::from_u32(
 705                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 706             );
 707         }
 708
 709         t.super_visit_with(self)
 710     }
 711
 712     fn visit_const(&mut self, c: ty::consts::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 713         if let ty::ConstKind::Placeholder(placeholder) = c.kind() {
 714             self.max_universe = ty::UniverseIndex::from_u32(
 715                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 716             );
 717         }
 718
 719         c.super_visit_with(self)
 720     }
 721
 722     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 723         if let ty::RePlaceholder(placeholder) = *r {
 724             self.max_universe = ty::UniverseIndex::from_u32(
 725                 self.max_universe.as_u32().max(placeholder.universe.as_u32()),
 726             );
 727         }
 728
 729         ControlFlow::CONTINUE
 730     }
 731 }