compiler/rustc_middle/src/ty/fold.rs

   1 //! Generalized type folding mechanism. The setup is a bit convoluted
   2 //! but allows for convenient usage. Let T be an instance of some
   3 //! "foldable type" (one which implements `TypeFoldable`) and F be an
   4 //! instance of a "folder" (a type which implements `TypeFolder`). Then
   5 //! the setup is intended to be:
   6 //!
   7 //!     T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F)
   8 //!
   9 //! This way, when you define a new folder F, you can override
  10 //! `fold_T()` to customize the behavior, and invoke `T.super_fold_with()`
  11 //! to get the original behavior. Meanwhile, to actually fold
  12 //! something, you can just write `T.fold_with(F)`, which is
  13 //! convenient. (Note that `fold_with` will also transparently handle
  14 //! things like a `Vec<T>` where T is foldable and so on.)
  15 //!
  16 //! In this ideal setup, the only function that actually *does*
  17 //! anything is `T.super_fold_with()`, which traverses the type `T`.
  18 //! Moreover, `T.super_fold_with()` should only ever call `T.fold_with()`.
  19 //!
  20 //! In some cases, we follow a degenerate pattern where we do not have
  21 //! a `fold_T` method. Instead, `T.fold_with` traverses the structure directly.
  22 //! This is suboptimal because the behavior cannot be overridden, but it's
  23 //! much less work to implement. If you ever *do* need an override that
  24 //! doesn't exist, it's not hard to convert the degenerate pattern into the
  25 //! proper thing.
  26 //!
  27 //! A `TypeFoldable` T can also be visited by a `TypeVisitor` V using similar setup:
  28 //!
  29 //!     T.visit_with(V) --calls--> V.visit_T(T) --calls--> T.super_visit_with(V).
  30 //!
  31 //! These methods return true to indicate that the visitor has found what it is
  32 //! looking for, and does not need to visit anything else.
  33 use crate::mir;
  34 use crate::ty::{self, flags::FlagComputation, Binder, Ty, TyCtxt, TypeFlags};
  35 use rustc_hir as hir;
  36 use rustc_hir::def_id::DefId;
  37
  38 use rustc_data_structures::fx::FxHashSet;
  39 use rustc_data_structures::sso::SsoHashSet;
  40 use std::collections::BTreeMap;
  41 use std::fmt;
  42 use std::ops::ControlFlow;
  43
  44 /// This trait is implemented for every type that can be folded.
  45 /// Basically, every type that has a corresponding method in `TypeFolder`.
  46 ///
  47 /// To implement this conveniently, use the derive macro located in `rustc_macros`.
  48 pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
  49     /// Consumers may find this more convenient to use with infallible folders than
  50     /// [`try_super_fold_with`][`TypeFoldable::try_super_fold_with`], to which the
  51     /// provided default definition delegates.  Implementors **should not** override
  52     /// this provided default definition, to ensure that the two methods are coherent
  53     /// (provide a definition of `try_super_fold_with` instead).
  54     fn super_fold_with<F: TypeFolder<'tcx, Error = !>>(self, folder: &mut F) -> Self {
  55         self.try_super_fold_with(folder).into_ok()
  56     }
  57     /// Consumers may find this more convenient to use with infallible folders than
  58     /// [`try_fold_with`][`TypeFoldable::try_fold_with`], to which the provided
  59     /// default definition delegates.  Implementors **should not** override this
  60     /// provided default definition, to ensure that the two methods are coherent
  61     /// (provide a definition of `try_fold_with` instead).
  62     fn fold_with<F: TypeFolder<'tcx, Error = !>>(self, folder: &mut F) -> Self {
  63         self.try_fold_with(folder).into_ok()
  64     }
  65
  66     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
  67         self,
  68         folder: &mut F,
  69     ) -> Result<Self, F::Error>;
  70
  71     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
  72         self.try_super_fold_with(folder)
  73     }
  74
  75     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy>;
  76     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
  77         self.super_visit_with(visitor)
  78     }
  79
  80     /// Returns `true` if `self` has any late-bound regions that are either
  81     /// bound by `binder` or bound by some binder outside of `binder`.
  82     /// If `binder` is `ty::INNERMOST`, this indicates whether
  83     /// there are any late-bound regions that appear free.
  84     fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
  85         self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder }).is_break()
  86     }
  87
  88     /// Returns `true` if this `self` has any regions that escape `binder` (and
  89     /// hence are not bound by it).
  90     fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool {
  91         self.has_vars_bound_at_or_above(binder.shifted_in(1))
  92     }
  93
  94     fn has_escaping_bound_vars(&self) -> bool {
  95         self.has_vars_bound_at_or_above(ty::INNERMOST)
  96     }
  97
  98     fn definitely_has_type_flags(&self, tcx: TyCtxt<'tcx>, flags: TypeFlags) -> bool {
  99         self.visit_with(&mut HasTypeFlagsVisitor { tcx: Some(tcx), flags }).break_value()
 100             == Some(FoundFlags)
 101     }
 102
 103     #[instrument(level = "trace")]
 104     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 105         self.visit_with(&mut HasTypeFlagsVisitor { tcx: None, flags }).break_value()
 106             == Some(FoundFlags)
 107     }
 108     fn has_projections(&self) -> bool {
 109         self.has_type_flags(TypeFlags::HAS_PROJECTION)
 110     }
 111     fn has_opaque_types(&self) -> bool {
 112         self.has_type_flags(TypeFlags::HAS_TY_OPAQUE)
 113     }
 114     fn references_error(&self) -> bool {
 115         self.has_type_flags(TypeFlags::HAS_ERROR)
 116     }
 117     fn potentially_has_param_types_or_consts(&self) -> bool {
 118         self.has_type_flags(
 119             TypeFlags::HAS_KNOWN_TY_PARAM
 120                 | TypeFlags::HAS_KNOWN_CT_PARAM
 121                 | TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS,
 122         )
 123     }
 124     fn definitely_has_param_types_or_consts(&self, tcx: TyCtxt<'tcx>) -> bool {
 125         self.definitely_has_type_flags(
 126             tcx,
 127             TypeFlags::HAS_KNOWN_TY_PARAM | TypeFlags::HAS_KNOWN_CT_PARAM,
 128         )
 129     }
 130     fn has_infer_regions(&self) -> bool {
 131         self.has_type_flags(TypeFlags::HAS_RE_INFER)
 132     }
 133     fn has_infer_types(&self) -> bool {
 134         self.has_type_flags(TypeFlags::HAS_TY_INFER)
 135     }
 136     fn has_infer_types_or_consts(&self) -> bool {
 137         self.has_type_flags(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_CT_INFER)
 138     }
 139     fn needs_infer(&self) -> bool {
 140         self.has_type_flags(TypeFlags::NEEDS_INFER)
 141     }
 142     fn has_placeholders(&self) -> bool {
 143         self.has_type_flags(
 144             TypeFlags::HAS_RE_PLACEHOLDER
 145                 | TypeFlags::HAS_TY_PLACEHOLDER
 146                 | TypeFlags::HAS_CT_PLACEHOLDER,
 147         )
 148     }
 149     fn potentially_needs_subst(&self) -> bool {
 150         self.has_type_flags(
 151             TypeFlags::KNOWN_NEEDS_SUBST | TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS,
 152         )
 153     }
 154     fn definitely_needs_subst(&self, tcx: TyCtxt<'tcx>) -> bool {
 155         self.definitely_has_type_flags(tcx, TypeFlags::KNOWN_NEEDS_SUBST)
 156     }
 157     /// "Free" regions in this context means that it has any region
 158     /// that is not (a) erased or (b) late-bound.
 159     fn has_free_regions(&self, tcx: TyCtxt<'tcx>) -> bool {
 160         self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_REGIONS)
 161     }
 162
 163     fn has_erased_regions(&self) -> bool {
 164         self.has_type_flags(TypeFlags::HAS_RE_ERASED)
 165     }
 166
 167     /// True if there are any un-erased free regions.
 168     fn has_erasable_regions(&self, tcx: TyCtxt<'tcx>) -> bool {
 169         self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_REGIONS)
 170     }
 171
 172     /// Indicates whether this value definitely references only 'global'
 173     /// generic parameters that are the same regardless of what fn we are
 174     /// in. This is used for caching.
 175     ///
 176     /// Note that this function is pessimistic and may incorrectly return
 177     /// `false`.
 178     fn is_known_global(&self) -> bool {
 179         !self.has_type_flags(TypeFlags::HAS_POTENTIAL_FREE_LOCAL_NAMES)
 180     }
 181
 182     /// Indicates whether this value references only 'global'
 183     /// generic parameters that are the same regardless of what fn we are
 184     /// in. This is used for caching.
 185     fn is_global(&self, tcx: TyCtxt<'tcx>) -> bool {
 186         !self.definitely_has_type_flags(tcx, TypeFlags::HAS_KNOWN_FREE_LOCAL_NAMES)
 187     }
 188
 189     /// True if there are any late-bound regions
 190     fn has_late_bound_regions(&self) -> bool {
 191         self.has_type_flags(TypeFlags::HAS_RE_LATE_BOUND)
 192     }
 193
 194     /// Indicates whether this value still has parameters/placeholders/inference variables
 195     /// which could be replaced later, in a way that would change the results of `impl`
 196     /// specialization.
 197     fn still_further_specializable(&self) -> bool {
 198         self.has_type_flags(TypeFlags::STILL_FURTHER_SPECIALIZABLE)
 199     }
 200 }
 201
 202 impl TypeFoldable<'tcx> for hir::Constness {
 203     fn try_super_fold_with<F: TypeFolder<'tcx>>(self, _: &mut F) -> Result<Self, F::Error> {
 204         Ok(self)
 205     }
 206     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> ControlFlow<V::BreakTy> {
 207         ControlFlow::CONTINUE
 208     }
 209 }
 210
 211 /// The `TypeFolder` trait defines the actual *folding*. There is a
 212 /// method defined for every foldable type. Each of these has a
 213 /// default implementation that does an "identity" fold. Within each
 214 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
 215 /// sub-item.
 216 ///
 217 /// If this folder is fallible (and therefore its [`Error`][`TypeFolder::Error`]
 218 /// associated type is something other than the default, never),
 219 /// [`FallibleTypeFolder`] should be implemented manually; otherwise,
 220 /// a blanket implementation of [`FallibleTypeFolder`] will defer to
 221 /// the infallible methods of this trait to ensure that the two APIs
 222 /// are coherent.
 223 pub trait TypeFolder<'tcx>: Sized {
 224     type Error = !;
 225
 226     fn tcx<'a>(&'a self) -> TyCtxt<'tcx>;
 227
 228     fn fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Binder<'tcx, T>
 229     where
 230         T: TypeFoldable<'tcx>,
 231         Self: TypeFolder<'tcx, Error = !>,
 232     {
 233         t.super_fold_with(self)
 234     }
 235
 236     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx>
 237     where
 238         Self: TypeFolder<'tcx, Error = !>,
 239     {
 240         t.super_fold_with(self)
 241     }
 242
 243     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx>
 244     where
 245         Self: TypeFolder<'tcx, Error = !>,
 246     {
 247         r.super_fold_with(self)
 248     }
 249
 250     fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>
 251     where
 252         Self: TypeFolder<'tcx, Error = !>,
 253     {
 254         c.super_fold_with(self)
 255     }
 256
 257     fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx>
 258     where
 259         Self: TypeFolder<'tcx, Error = !>,
 260     {
 261         p.super_fold_with(self)
 262     }
 263
 264     fn fold_mir_const(&mut self, c: mir::ConstantKind<'tcx>) -> mir::ConstantKind<'tcx>
 265     where
 266         Self: TypeFolder<'tcx, Error = !>,
 267     {
 268         bug!("most type folders should not be folding MIR datastructures: {:?}", c)
 269     }
 270 }
 271
 272 /// The `FallibleTypeFolder` trait defines the actual *folding*. There is a
 273 /// method defined for every foldable type. Each of these has a
 274 /// default implementation that does an "identity" fold. Within each
 275 /// identity fold, it should invoke `foo.try_fold_with(self)` to fold each
 276 /// sub-item.
 277 ///
 278 /// A blanket implementation of this trait (that defers to the relevant
 279 /// method of [`TypeFolder`]) is provided for all infallible folders in
 280 /// order to ensure the two APIs are coherent.
 281 pub trait FallibleTypeFolder<'tcx>: TypeFolder<'tcx> {
 282     fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error>
 283     where
 284         T: TypeFoldable<'tcx>,
 285     {
 286         t.try_super_fold_with(self)
 287     }
 288
 289     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 290         t.try_super_fold_with(self)
 291     }
 292
 293     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 294         r.try_super_fold_with(self)
 295     }
 296
 297     fn try_fold_const(
 298         &mut self,
 299         c: &'tcx ty::Const<'tcx>,
 300     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 301         c.try_super_fold_with(self)
 302     }
 303
 304     fn try_fold_predicate(
 305         &mut self,
 306         p: ty::Predicate<'tcx>,
 307     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
 308         p.try_super_fold_with(self)
 309     }
 310
 311     fn try_fold_mir_const(
 312         &mut self,
 313         c: mir::ConstantKind<'tcx>,
 314     ) -> Result<mir::ConstantKind<'tcx>, Self::Error> {
 315         bug!("most type folders should not be folding MIR datastructures: {:?}", c)
 316     }
 317 }
 318
 319 // Blanket implementation of fallible trait for infallible folders
 320 // delegates to infallible methods to prevent incoherence
 321 impl<'tcx, F> FallibleTypeFolder<'tcx> for F
 322 where
 323     F: TypeFolder<'tcx, Error = !>,
 324 {
 325     fn try_fold_binder<T>(&mut self, t: Binder<'tcx, T>) -> Result<Binder<'tcx, T>, Self::Error>
 326     where
 327         T: TypeFoldable<'tcx>,
 328     {
 329         Ok(self.fold_binder(t))
 330     }
 331
 332     fn try_fold_ty(&mut self, t: Ty<'tcx>) -> Result<Ty<'tcx>, Self::Error> {
 333         Ok(self.fold_ty(t))
 334     }
 335
 336     fn try_fold_region(&mut self, r: ty::Region<'tcx>) -> Result<ty::Region<'tcx>, Self::Error> {
 337         Ok(self.fold_region(r))
 338     }
 339
 340     fn try_fold_const(
 341         &mut self,
 342         c: &'tcx ty::Const<'tcx>,
 343     ) -> Result<&'tcx ty::Const<'tcx>, Self::Error> {
 344         Ok(self.fold_const(c))
 345     }
 346
 347     fn try_fold_predicate(
 348         &mut self,
 349         p: ty::Predicate<'tcx>,
 350     ) -> Result<ty::Predicate<'tcx>, Self::Error> {
 351         Ok(self.fold_predicate(p))
 352     }
 353
 354     fn try_fold_mir_const(
 355         &mut self,
 356         c: mir::ConstantKind<'tcx>,
 357     ) -> Result<mir::ConstantKind<'tcx>, Self::Error> {
 358         Ok(self.fold_mir_const(c))
 359     }
 360 }
 361
 362 pub trait TypeVisitor<'tcx>: Sized {
 363     type BreakTy = !;
 364     /// Supplies the `tcx` for an unevaluated anonymous constant in case its default substs
 365     /// are not yet supplied.
 366     ///
 367     /// Returning `None` for this method is only recommended if the `TypeVisitor`
 368     /// does not care about default anon const substs, as it ignores generic parameters,
 369     /// and fetching the default substs would cause a query cycle.
 370     ///
 371     /// For visitors which return `None` we completely skip the default substs in `ty::Unevaluated::super_visit_with`.
 372     /// This means that incorrectly returning `None` can very quickly lead to ICE or other critical bugs, so be careful and
 373     /// try to return an actual `tcx` if possible.
 374     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>>;
 375
 376     fn visit_binder<T: TypeFoldable<'tcx>>(
 377         &mut self,
 378         t: &Binder<'tcx, T>,
 379     ) -> ControlFlow<Self::BreakTy> {
 380         t.super_visit_with(self)
 381     }
 382
 383     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 384         t.super_visit_with(self)
 385     }
 386
 387     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 388         r.super_visit_with(self)
 389     }
 390
 391     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
 392         c.super_visit_with(self)
 393     }
 394
 395     fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> {
 396         uv.super_visit_with(self)
 397     }
 398
 399     fn visit_predicate(&mut self, p: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
 400         p.super_visit_with(self)
 401     }
 402 }
 403
 404 ///////////////////////////////////////////////////////////////////////////
 405 // Some sample folders
 406
 407 pub struct BottomUpFolder<'tcx, F, G, H>
 408 where
 409     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 410     G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 411     H: FnMut(&'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>,
 412 {
 413     pub tcx: TyCtxt<'tcx>,
 414     pub ty_op: F,
 415     pub lt_op: G,
 416     pub ct_op: H,
 417 }
 418
 419 impl<'tcx, F, G, H> TypeFolder<'tcx> for BottomUpFolder<'tcx, F, G, H>
 420 where
 421     F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 422     G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 423     H: FnMut(&'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx>,
 424 {
 425     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 426         self.tcx
 427     }
 428
 429     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 430         let t = ty.super_fold_with(self);
 431         (self.ty_op)(t)
 432     }
 433
 434     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 435         let r = r.super_fold_with(self);
 436         (self.lt_op)(r)
 437     }
 438
 439     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 440         let ct = ct.super_fold_with(self);
 441         (self.ct_op)(ct)
 442     }
 443 }
 444
 445 ///////////////////////////////////////////////////////////////////////////
 446 // Region folder
 447
 448 impl<'tcx> TyCtxt<'tcx> {
 449     /// Folds the escaping and free regions in `value` using `f`, and
 450     /// sets `skipped_regions` to true if any late-bound region was found
 451     /// and skipped.
 452     pub fn fold_regions<T>(
 453         self,
 454         value: T,
 455         skipped_regions: &mut bool,
 456         mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 457     ) -> T
 458     where
 459         T: TypeFoldable<'tcx>,
 460     {
 461         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f))
 462     }
 463
 464     /// Invoke `callback` on every region appearing free in `value`.
 465     pub fn for_each_free_region(
 466         self,
 467         value: &impl TypeFoldable<'tcx>,
 468         mut callback: impl FnMut(ty::Region<'tcx>),
 469     ) {
 470         self.any_free_region_meets(value, |r| {
 471             callback(r);
 472             false
 473         });
 474     }
 475
 476     /// Returns `true` if `callback` returns true for every region appearing free in `value`.
 477     pub fn all_free_regions_meet(
 478         self,
 479         value: &impl TypeFoldable<'tcx>,
 480         mut callback: impl FnMut(ty::Region<'tcx>) -> bool,
 481     ) -> bool {
 482         !self.any_free_region_meets(value, |r| !callback(r))
 483     }
 484
 485     /// Returns `true` if `callback` returns true for some region appearing free in `value`.
 486     pub fn any_free_region_meets(
 487         self,
 488         value: &impl TypeFoldable<'tcx>,
 489         callback: impl FnMut(ty::Region<'tcx>) -> bool,
 490     ) -> bool {
 491         struct RegionVisitor<'tcx, F> {
 492             tcx: TyCtxt<'tcx>,
 493             /// The index of a binder *just outside* the things we have
 494             /// traversed. If we encounter a bound region bound by this
 495             /// binder or one outer to it, it appears free. Example:
 496             ///
 497             /// ```
 498             ///    for<'a> fn(for<'b> fn(), T)
 499             /// ^          ^          ^     ^
 500             /// |          |          |     | here, would be shifted in 1
 501             /// |          |          | here, would be shifted in 2
 502             /// |          | here, would be `INNERMOST` shifted in by 1
 503             /// | here, initially, binder would be `INNERMOST`
 504             /// ```
 505             ///
 506             /// You see that, initially, *any* bound value is free,
 507             /// because we've not traversed any binders. As we pass
 508             /// through a binder, we shift the `outer_index` by 1 to
 509             /// account for the new binder that encloses us.
 510             outer_index: ty::DebruijnIndex,
 511             callback: F,
 512         }
 513
 514         impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<'tcx, F>
 515         where
 516             F: FnMut(ty::Region<'tcx>) -> bool,
 517         {
 518             type BreakTy = ();
 519
 520             fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 521                 Some(self.tcx)
 522             }
 523
 524             fn visit_binder<T: TypeFoldable<'tcx>>(
 525                 &mut self,
 526                 t: &Binder<'tcx, T>,
 527             ) -> ControlFlow<Self::BreakTy> {
 528                 self.outer_index.shift_in(1);
 529                 let result = t.as_ref().skip_binder().visit_with(self);
 530                 self.outer_index.shift_out(1);
 531                 result
 532             }
 533
 534             fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
 535                 match *r {
 536                     ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => {
 537                         ControlFlow::CONTINUE
 538                     }
 539                     _ => {
 540                         if (self.callback)(r) {
 541                             ControlFlow::BREAK
 542                         } else {
 543                             ControlFlow::CONTINUE
 544                         }
 545                     }
 546                 }
 547             }
 548
 549             fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 550                 // We're only interested in types involving regions
 551                 if ty.flags().intersects(TypeFlags::HAS_POTENTIAL_FREE_REGIONS) {
 552                     ty.super_visit_with(self)
 553                 } else {
 554                     ControlFlow::CONTINUE
 555                 }
 556             }
 557         }
 558
 559         value
 560             .visit_with(&mut RegionVisitor { tcx: self, outer_index: ty::INNERMOST, callback })
 561             .is_break()
 562     }
 563 }
 564
 565 /// Folds over the substructure of a type, visiting its component
 566 /// types and all regions that occur *free* within it.
 567 ///
 568 /// That is, `Ty` can contain function or method types that bind
 569 /// regions at the call site (`ReLateBound`), and occurrences of
 570 /// regions (aka "lifetimes") that are bound within a type are not
 571 /// visited by this folder; only regions that occur free will be
 572 /// visited by `fld_r`.
 573
 574 pub struct RegionFolder<'a, 'tcx> {
 575     tcx: TyCtxt<'tcx>,
 576     skipped_regions: &'a mut bool,
 577
 578     /// Stores the index of a binder *just outside* the stuff we have
 579     /// visited.  So this begins as INNERMOST; when we pass through a
 580     /// binder, it is incremented (via `shift_in`).
 581     current_index: ty::DebruijnIndex,
 582
 583     /// Callback invokes for each free region. The `DebruijnIndex`
 584     /// points to the binder *just outside* the ones we have passed
 585     /// through.
 586     fold_region_fn:
 587         &'a mut (dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx> + 'a),
 588 }
 589
 590 impl<'a, 'tcx> RegionFolder<'a, 'tcx> {
 591     #[inline]
 592     pub fn new(
 593         tcx: TyCtxt<'tcx>,
 594         skipped_regions: &'a mut bool,
 595         fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 596     ) -> RegionFolder<'a, 'tcx> {
 597         RegionFolder { tcx, skipped_regions, current_index: ty::INNERMOST, fold_region_fn }
 598     }
 599 }
 600
 601 impl<'a, 'tcx> TypeFolder<'tcx> for RegionFolder<'a, 'tcx> {
 602     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 603         self.tcx
 604     }
 605
 606     fn fold_binder<T: TypeFoldable<'tcx>>(
 607         &mut self,
 608         t: ty::Binder<'tcx, T>,
 609     ) -> ty::Binder<'tcx, T> {
 610         self.current_index.shift_in(1);
 611         let t = t.super_fold_with(self);
 612         self.current_index.shift_out(1);
 613         t
 614     }
 615
 616     #[instrument(skip(self), level = "debug")]
 617     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 618         match *r {
 619             ty::ReLateBound(debruijn, _) if debruijn < self.current_index => {
 620                 debug!(?self.current_index, "skipped bound region");
 621                 *self.skipped_regions = true;
 622                 r
 623             }
 624             _ => {
 625                 debug!(?self.current_index, "folding free region");
 626                 (self.fold_region_fn)(r, self.current_index)
 627             }
 628         }
 629     }
 630 }
 631
 632 ///////////////////////////////////////////////////////////////////////////
 633 // Bound vars replacer
 634
 635 /// Replaces the escaping bound vars (late bound regions or bound types) in a type.
 636 struct BoundVarReplacer<'a, 'tcx> {
 637     tcx: TyCtxt<'tcx>,
 638
 639     /// As with `RegionFolder`, represents the index of a binder *just outside*
 640     /// the ones we have visited.
 641     current_index: ty::DebruijnIndex,
 642
 643     fld_r: Option<&'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a)>,
 644     fld_t: Option<&'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a)>,
 645     fld_c: Option<&'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx> + 'a)>,
 646 }
 647
 648 impl<'a, 'tcx> BoundVarReplacer<'a, 'tcx> {
 649     fn new(
 650         tcx: TyCtxt<'tcx>,
 651         fld_r: Option<&'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a)>,
 652         fld_t: Option<&'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a)>,
 653         fld_c: Option<&'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx> + 'a)>,
 654     ) -> Self {
 655         BoundVarReplacer { tcx, current_index: ty::INNERMOST, fld_r, fld_t, fld_c }
 656     }
 657 }
 658
 659 impl<'a, 'tcx> TypeFolder<'tcx> for BoundVarReplacer<'a, 'tcx> {
 660     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 661         self.tcx
 662     }
 663
 664     fn fold_binder<T: TypeFoldable<'tcx>>(
 665         &mut self,
 666         t: ty::Binder<'tcx, T>,
 667     ) -> ty::Binder<'tcx, T> {
 668         self.current_index.shift_in(1);
 669         let t = t.super_fold_with(self);
 670         self.current_index.shift_out(1);
 671         t
 672     }
 673
 674     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 675         match *t.kind() {
 676             ty::Bound(debruijn, bound_ty) if debruijn == self.current_index => {
 677                 if let Some(fld_t) = self.fld_t.as_mut() {
 678                     let ty = fld_t(bound_ty);
 679                     return ty::fold::shift_vars(self.tcx, &ty, self.current_index.as_u32());
 680                 }
 681             }
 682             _ if t.has_vars_bound_at_or_above(self.current_index) => {
 683                 return t.super_fold_with(self);
 684             }
 685             _ => {}
 686         }
 687         t
 688     }
 689
 690     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 691         match *r {
 692             ty::ReLateBound(debruijn, br) if debruijn == self.current_index => {
 693                 if let Some(fld_r) = self.fld_r.as_mut() {
 694                     let region = fld_r(br);
 695                     return if let ty::ReLateBound(debruijn1, br) = *region {
 696                         // If the callback returns a late-bound region,
 697                         // that region should always use the INNERMOST
 698                         // debruijn index. Then we adjust it to the
 699                         // correct depth.
 700                         assert_eq!(debruijn1, ty::INNERMOST);
 701                         self.tcx.mk_region(ty::ReLateBound(debruijn, br))
 702                     } else {
 703                         region
 704                     };
 705                 }
 706             }
 707             _ => {}
 708         }
 709         r
 710     }
 711
 712     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 713         match *ct {
 714             ty::Const { val: ty::ConstKind::Bound(debruijn, bound_const), ty }
 715                 if debruijn == self.current_index =>
 716             {
 717                 if let Some(fld_c) = self.fld_c.as_mut() {
 718                     let ct = fld_c(bound_const, ty);
 719                     return ty::fold::shift_vars(self.tcx, &ct, self.current_index.as_u32());
 720                 }
 721             }
 722             _ if ct.has_vars_bound_at_or_above(self.current_index) => {
 723                 return ct.super_fold_with(self);
 724             }
 725             _ => {}
 726         }
 727         ct
 728     }
 729 }
 730
 731 impl<'tcx> TyCtxt<'tcx> {
 732     /// Replaces all regions bound by the given `Binder` with the
 733     /// results returned by the closure; the closure is expected to
 734     /// return a free region (relative to this binder), and hence the
 735     /// binder is removed in the return type. The closure is invoked
 736     /// once for each unique `BoundRegionKind`; multiple references to the
 737     /// same `BoundRegionKind` will reuse the previous result. A map is
 738     /// returned at the end with each bound region and the free region
 739     /// that replaced it.
 740     ///
 741     /// This method only replaces late bound regions and the result may still
 742     /// contain escaping bound types.
 743     pub fn replace_late_bound_regions<T, F>(
 744         self,
 745         value: Binder<'tcx, T>,
 746         mut fld_r: F,
 747     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 748     where
 749         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 750         T: TypeFoldable<'tcx>,
 751     {
 752         let mut region_map = BTreeMap::new();
 753         let mut real_fld_r =
 754             |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
 755         let value = value.skip_binder();
 756         let value = if !value.has_escaping_bound_vars() {
 757             value
 758         } else {
 759             let mut replacer = BoundVarReplacer::new(self, Some(&mut real_fld_r), None, None);
 760             value.fold_with(&mut replacer)
 761         };
 762         (value, region_map)
 763     }
 764
 765     /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping
 766     /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c`
 767     /// closure replaces escaping bound consts.
 768     pub fn replace_escaping_bound_vars<T, F, G, H>(
 769         self,
 770         value: T,
 771         mut fld_r: F,
 772         mut fld_t: G,
 773         mut fld_c: H,
 774     ) -> T
 775     where
 776         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 777         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 778         H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx>,
 779         T: TypeFoldable<'tcx>,
 780     {
 781         if !value.has_escaping_bound_vars() {
 782             value
 783         } else {
 784             let mut replacer =
 785                 BoundVarReplacer::new(self, Some(&mut fld_r), Some(&mut fld_t), Some(&mut fld_c));
 786             value.fold_with(&mut replacer)
 787         }
 788     }
 789
 790     /// Replaces all types or regions bound by the given `Binder`. The `fld_r`
 791     /// closure replaces bound regions while the `fld_t` closure replaces bound
 792     /// types.
 793     pub fn replace_bound_vars<T, F, G, H>(
 794         self,
 795         value: Binder<'tcx, T>,
 796         mut fld_r: F,
 797         fld_t: G,
 798         fld_c: H,
 799     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 800     where
 801         F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 802         G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 803         H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::Const<'tcx>,
 804         T: TypeFoldable<'tcx>,
 805     {
 806         let mut region_map = BTreeMap::new();
 807         let real_fld_r = |br: ty::BoundRegion| *region_map.entry(br).or_insert_with(|| fld_r(br));
 808         let value = self.replace_escaping_bound_vars(value.skip_binder(), real_fld_r, fld_t, fld_c);
 809         (value, region_map)
 810     }
 811
 812     /// Replaces any late-bound regions bound in `value` with
 813     /// free variants attached to `all_outlive_scope`.
 814     pub fn liberate_late_bound_regions<T>(
 815         self,
 816         all_outlive_scope: DefId,
 817         value: ty::Binder<'tcx, T>,
 818     ) -> T
 819     where
 820         T: TypeFoldable<'tcx>,
 821     {
 822         self.replace_late_bound_regions(value, |br| {
 823             self.mk_region(ty::ReFree(ty::FreeRegion {
 824                 scope: all_outlive_scope,
 825                 bound_region: br.kind,
 826             }))
 827         })
 828         .0
 829     }
 830
 831     pub fn shift_bound_var_indices<T>(self, bound_vars: usize, value: T) -> T
 832     where
 833         T: TypeFoldable<'tcx>,
 834     {
 835         self.replace_escaping_bound_vars(
 836             value,
 837             |r| {
 838                 self.mk_region(ty::ReLateBound(
 839                     ty::INNERMOST,
 840                     ty::BoundRegion {
 841                         var: ty::BoundVar::from_usize(r.var.as_usize() + bound_vars),
 842                         kind: r.kind,
 843                     },
 844                 ))
 845             },
 846             |t| {
 847                 self.mk_ty(ty::Bound(
 848                     ty::INNERMOST,
 849                     ty::BoundTy {
 850                         var: ty::BoundVar::from_usize(t.var.as_usize() + bound_vars),
 851                         kind: t.kind,
 852                     },
 853                 ))
 854             },
 855             |c, ty| {
 856                 self.mk_const(ty::Const {
 857                     val: ty::ConstKind::Bound(
 858                         ty::INNERMOST,
 859                         ty::BoundVar::from_usize(c.as_usize() + bound_vars),
 860                     ),
 861                     ty,
 862                 })
 863             },
 864         )
 865     }
 866
 867     /// Returns a set of all late-bound regions that are constrained
 868     /// by `value`, meaning that if we instantiate those LBR with
 869     /// variables and equate `value` with something else, those
 870     /// variables will also be equated.
 871     pub fn collect_constrained_late_bound_regions<T>(
 872         self,
 873         value: &Binder<'tcx, T>,
 874     ) -> FxHashSet<ty::BoundRegionKind>
 875     where
 876         T: TypeFoldable<'tcx>,
 877     {
 878         self.collect_late_bound_regions(value, true)
 879     }
 880
 881     /// Returns a set of all late-bound regions that appear in `value` anywhere.
 882     pub fn collect_referenced_late_bound_regions<T>(
 883         self,
 884         value: &Binder<'tcx, T>,
 885     ) -> FxHashSet<ty::BoundRegionKind>
 886     where
 887         T: TypeFoldable<'tcx>,
 888     {
 889         self.collect_late_bound_regions(value, false)
 890     }
 891
 892     fn collect_late_bound_regions<T>(
 893         self,
 894         value: &Binder<'tcx, T>,
 895         just_constraint: bool,
 896     ) -> FxHashSet<ty::BoundRegionKind>
 897     where
 898         T: TypeFoldable<'tcx>,
 899     {
 900         let mut collector = LateBoundRegionsCollector::new(self, just_constraint);
 901         let result = value.as_ref().skip_binder().visit_with(&mut collector);
 902         assert!(result.is_continue()); // should never have stopped early
 903         collector.regions
 904     }
 905
 906     /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also
 907     /// method lookup and a few other places where precise region relationships are not required.
 908     pub fn erase_late_bound_regions<T>(self, value: Binder<'tcx, T>) -> T
 909     where
 910         T: TypeFoldable<'tcx>,
 911     {
 912         self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0
 913     }
 914
 915     /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
 916     /// assigned starting at 0 and increasing monotonically in the order traversed
 917     /// by the fold operation.
 918     ///
 919     /// The chief purpose of this function is to canonicalize regions so that two
 920     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 921     /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 922     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 923     pub fn anonymize_late_bound_regions<T>(self, sig: Binder<'tcx, T>) -> Binder<'tcx, T>
 924     where
 925         T: TypeFoldable<'tcx>,
 926     {
 927         let mut counter = 0;
 928         let inner = self
 929             .replace_late_bound_regions(sig, |_| {
 930                 let br = ty::BoundRegion {
 931                     var: ty::BoundVar::from_u32(counter),
 932                     kind: ty::BrAnon(counter),
 933                 };
 934                 let r = self.mk_region(ty::ReLateBound(ty::INNERMOST, br));
 935                 counter += 1;
 936                 r
 937             })
 938             .0;
 939         let bound_vars = self.mk_bound_variable_kinds(
 940             (0..counter).map(|i| ty::BoundVariableKind::Region(ty::BrAnon(i))),
 941         );
 942         Binder::bind_with_vars(inner, bound_vars)
 943     }
 944 }
 945
 946 pub struct ValidateBoundVars<'tcx> {
 947     bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
 948     binder_index: ty::DebruijnIndex,
 949     // We may encounter the same variable at different levels of binding, so
 950     // this can't just be `Ty`
 951     visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>,
 952 }
 953
 954 impl<'tcx> ValidateBoundVars<'tcx> {
 955     pub fn new(bound_vars: &'tcx ty::List<ty::BoundVariableKind>) -> Self {
 956         ValidateBoundVars {
 957             bound_vars,
 958             binder_index: ty::INNERMOST,
 959             visited: SsoHashSet::default(),
 960         }
 961     }
 962 }
 963
 964 impl<'tcx> TypeVisitor<'tcx> for ValidateBoundVars<'tcx> {
 965     type BreakTy = ();
 966
 967     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
 968         // Anonymous constants do not contain bound vars in their substs by default.
 969         None
 970     }
 971
 972     fn visit_binder<T: TypeFoldable<'tcx>>(
 973         &mut self,
 974         t: &Binder<'tcx, T>,
 975     ) -> ControlFlow<Self::BreakTy> {
 976         self.binder_index.shift_in(1);
 977         let result = t.super_visit_with(self);
 978         self.binder_index.shift_out(1);
 979         result
 980     }
 981
 982     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
 983         if t.outer_exclusive_binder < self.binder_index
 984             || !self.visited.insert((self.binder_index, t))
 985         {
 986             return ControlFlow::BREAK;
 987         }
 988         match *t.kind() {
 989             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 990                 if self.bound_vars.len() <= bound_ty.var.as_usize() {
 991                     bug!("Not enough bound vars: {:?} not found in {:?}", t, self.bound_vars);
 992                 }
 993                 let list_var = self.bound_vars[bound_ty.var.as_usize()];
 994                 match list_var {
 995                     ty::BoundVariableKind::Ty(kind) => {
 996                         if kind != bound_ty.kind {
 997                             bug!(
 998                                 "Mismatched type kinds: {:?} doesn't var in list {:?}",
 999                                 bound_ty.kind,
1000                                 list_var
1001                             );
1002                         }
1003                     }
1004                     _ => {
1005                         bug!("Mismatched bound variable kinds! Expected type, found {:?}", list_var)
1006                     }
1007                 }
1008             }
1009
1010             _ => (),
1011         };
1012
1013         t.super_visit_with(self)
1014     }
1015
1016     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1017         match r {
1018             ty::ReLateBound(index, br) if *index == self.binder_index => {
1019                 if self.bound_vars.len() <= br.var.as_usize() {
1020                     bug!("Not enough bound vars: {:?} not found in {:?}", *br, self.bound_vars);
1021                 }
1022                 let list_var = self.bound_vars[br.var.as_usize()];
1023                 match list_var {
1024                     ty::BoundVariableKind::Region(kind) => {
1025                         if kind != br.kind {
1026                             bug!(
1027                                 "Mismatched region kinds: {:?} doesn't match var ({:?}) in list ({:?})",
1028                                 br.kind,
1029                                 list_var,
1030                                 self.bound_vars
1031                             );
1032                         }
1033                     }
1034                     _ => bug!(
1035                         "Mismatched bound variable kinds! Expected region, found {:?}",
1036                         list_var
1037                     ),
1038                 }
1039             }
1040
1041             _ => (),
1042         };
1043
1044         r.super_visit_with(self)
1045     }
1046 }
1047
1048 ///////////////////////////////////////////////////////////////////////////
1049 // Shifter
1050 //
1051 // Shifts the De Bruijn indices on all escaping bound vars by a
1052 // fixed amount. Useful in substitution or when otherwise introducing
1053 // a binding level that is not intended to capture the existing bound
1054 // vars. See comment on `shift_vars_through_binders` method in
1055 // `subst.rs` for more details.
1056
1057 struct Shifter<'tcx> {
1058     tcx: TyCtxt<'tcx>,
1059     current_index: ty::DebruijnIndex,
1060     amount: u32,
1061 }
1062
1063 impl Shifter<'tcx> {
1064     pub fn new(tcx: TyCtxt<'tcx>, amount: u32) -> Self {
1065         Shifter { tcx, current_index: ty::INNERMOST, amount }
1066     }
1067 }
1068
1069 impl TypeFolder<'tcx> for Shifter<'tcx> {
1070     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
1071         self.tcx
1072     }
1073
1074     fn fold_binder<T: TypeFoldable<'tcx>>(
1075         &mut self,
1076         t: ty::Binder<'tcx, T>,
1077     ) -> ty::Binder<'tcx, T> {
1078         self.current_index.shift_in(1);
1079         let t = t.super_fold_with(self);
1080         self.current_index.shift_out(1);
1081         t
1082     }
1083
1084     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
1085         match *r {
1086             ty::ReLateBound(debruijn, br) => {
1087                 if self.amount == 0 || debruijn < self.current_index {
1088                     r
1089                 } else {
1090                     let debruijn = debruijn.shifted_in(self.amount);
1091                     let shifted = ty::ReLateBound(debruijn, br);
1092                     self.tcx.mk_region(shifted)
1093                 }
1094             }
1095             _ => r,
1096         }
1097     }
1098
1099     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
1100         match *ty.kind() {
1101             ty::Bound(debruijn, bound_ty) => {
1102                 if self.amount == 0 || debruijn < self.current_index {
1103                     ty
1104                 } else {
1105                     let debruijn = debruijn.shifted_in(self.amount);
1106                     self.tcx.mk_ty(ty::Bound(debruijn, bound_ty))
1107                 }
1108             }
1109
1110             _ => ty.super_fold_with(self),
1111         }
1112     }
1113
1114     fn fold_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
1115         if let ty::Const { val: ty::ConstKind::Bound(debruijn, bound_ct), ty } = *ct {
1116             if self.amount == 0 || debruijn < self.current_index {
1117                 ct
1118             } else {
1119                 let debruijn = debruijn.shifted_in(self.amount);
1120                 self.tcx.mk_const(ty::Const { val: ty::ConstKind::Bound(debruijn, bound_ct), ty })
1121             }
1122         } else {
1123             ct.super_fold_with(self)
1124         }
1125     }
1126 }
1127
1128 pub fn shift_region<'tcx>(
1129     tcx: TyCtxt<'tcx>,
1130     region: ty::Region<'tcx>,
1131     amount: u32,
1132 ) -> ty::Region<'tcx> {
1133     match region {
1134         ty::ReLateBound(debruijn, br) if amount > 0 => {
1135             tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), *br))
1136         }
1137         _ => region,
1138     }
1139 }
1140
1141 pub fn shift_vars<'tcx, T>(tcx: TyCtxt<'tcx>, value: T, amount: u32) -> T
1142 where
1143     T: TypeFoldable<'tcx>,
1144 {
1145     debug!("shift_vars(value={:?}, amount={})", value, amount);
1146
1147     value.fold_with(&mut Shifter::new(tcx, amount))
1148 }
1149
1150 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
1151 struct FoundEscapingVars;
1152
1153 /// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a
1154 /// bound region or a bound type.
1155 ///
1156 /// So, for example, consider a type like the following, which has two binders:
1157 ///
1158 ///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
1159 ///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
1160 ///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
1161 ///
1162 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
1163 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
1164 /// fn type*, that type has an escaping region: `'a`.
1165 ///
1166 /// Note that what I'm calling an "escaping var" is often just called a "free var". However,
1167 /// we already use the term "free var". It refers to the regions or types that we use to represent
1168 /// bound regions or type params on a fn definition while we are type checking its body.
1169 ///
1170 /// To clarify, conceptually there is no particular difference between
1171 /// an "escaping" var and a "free" var. However, there is a big
1172 /// difference in practice. Basically, when "entering" a binding
1173 /// level, one is generally required to do some sort of processing to
1174 /// a bound var, such as replacing it with a fresh/placeholder
1175 /// var, or making an entry in the environment to represent the
1176 /// scope to which it is attached, etc. An escaping var represents
1177 /// a bound var for which this processing has not yet been done.
1178 struct HasEscapingVarsVisitor {
1179     /// Anything bound by `outer_index` or "above" is escaping.
1180     outer_index: ty::DebruijnIndex,
1181 }
1182
1183 impl<'tcx> TypeVisitor<'tcx> for HasEscapingVarsVisitor {
1184     type BreakTy = FoundEscapingVars;
1185
1186     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1187         // Anonymous constants do not contain bound vars in their substs by default.
1188         None
1189     }
1190
1191     fn visit_binder<T: TypeFoldable<'tcx>>(
1192         &mut self,
1193         t: &Binder<'tcx, T>,
1194     ) -> ControlFlow<Self::BreakTy> {
1195         self.outer_index.shift_in(1);
1196         let result = t.super_visit_with(self);
1197         self.outer_index.shift_out(1);
1198         result
1199     }
1200
1201     #[inline]
1202     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1203         // If the outer-exclusive-binder is *strictly greater* than
1204         // `outer_index`, that means that `t` contains some content
1205         // bound at `outer_index` or above (because
1206         // `outer_exclusive_binder` is always 1 higher than the
1207         // content in `t`). Therefore, `t` has some escaping vars.
1208         if t.outer_exclusive_binder > self.outer_index {
1209             ControlFlow::Break(FoundEscapingVars)
1210         } else {
1211             ControlFlow::CONTINUE
1212         }
1213     }
1214
1215     #[inline]
1216     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1217         // If the region is bound by `outer_index` or anything outside
1218         // of outer index, then it escapes the binders we have
1219         // visited.
1220         if r.bound_at_or_above_binder(self.outer_index) {
1221             ControlFlow::Break(FoundEscapingVars)
1222         } else {
1223             ControlFlow::CONTINUE
1224         }
1225     }
1226
1227     fn visit_const(&mut self, ct: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
1228         // we don't have a `visit_infer_const` callback, so we have to
1229         // hook in here to catch this case (annoying...), but
1230         // otherwise we do want to remember to visit the rest of the
1231         // const, as it has types/regions embedded in a lot of other
1232         // places.
1233         match ct.val {
1234             ty::ConstKind::Bound(debruijn, _) if debruijn >= self.outer_index => {
1235                 ControlFlow::Break(FoundEscapingVars)
1236             }
1237             _ => ct.super_visit_with(self),
1238         }
1239     }
1240
1241     #[inline]
1242     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
1243         if predicate.inner.outer_exclusive_binder > self.outer_index {
1244             ControlFlow::Break(FoundEscapingVars)
1245         } else {
1246             ControlFlow::CONTINUE
1247         }
1248     }
1249 }
1250
1251 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
1252 struct FoundFlags;
1253
1254 // FIXME: Optimize for checking for infer flags
1255 struct HasTypeFlagsVisitor<'tcx> {
1256     tcx: Option<TyCtxt<'tcx>>,
1257     flags: ty::TypeFlags,
1258 }
1259
1260 impl std::fmt::Debug for HasTypeFlagsVisitor<'tcx> {
1261     fn fmt(&self, fmt: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1262         self.flags.fmt(fmt)
1263     }
1264 }
1265
1266 impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor<'tcx> {
1267     type BreakTy = FoundFlags;
1268     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1269         bug!("we shouldn't call this method as we manually look at ct substs");
1270     }
1271
1272     #[inline]
1273     #[instrument(level = "trace")]
1274     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1275         let flags = t.flags();
1276         trace!(t.flags=?t.flags());
1277         if flags.intersects(self.flags) {
1278             ControlFlow::Break(FoundFlags)
1279         } else {
1280             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1281                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, t),
1282                 _ => ControlFlow::CONTINUE,
1283             }
1284         }
1285     }
1286
1287     #[inline]
1288     #[instrument(skip(self), level = "trace")]
1289     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1290         let flags = r.type_flags();
1291         trace!(r.flags=?flags);
1292         if flags.intersects(self.flags) {
1293             ControlFlow::Break(FoundFlags)
1294         } else {
1295             ControlFlow::CONTINUE
1296         }
1297     }
1298
1299     #[inline]
1300     #[instrument(level = "trace")]
1301     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
1302         let flags = FlagComputation::for_const(c);
1303         trace!(r.flags=?flags);
1304         if flags.intersects(self.flags) {
1305             ControlFlow::Break(FoundFlags)
1306         } else {
1307             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1308                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, c),
1309                 _ => ControlFlow::CONTINUE,
1310             }
1311         }
1312     }
1313
1314     #[inline]
1315     #[instrument(level = "trace")]
1316     fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> {
1317         let flags = FlagComputation::for_unevaluated_const(uv);
1318         trace!(r.flags=?flags);
1319         if flags.intersects(self.flags) {
1320             ControlFlow::Break(FoundFlags)
1321         } else {
1322             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1323                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, uv),
1324                 _ => ControlFlow::CONTINUE,
1325             }
1326         }
1327     }
1328
1329     #[inline]
1330     #[instrument(level = "trace")]
1331     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
1332         let flags = predicate.inner.flags;
1333         trace!(predicate.flags=?flags);
1334         if flags.intersects(self.flags) {
1335             ControlFlow::Break(FoundFlags)
1336         } else {
1337             match flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1338                 true if self.tcx.is_some() => UnknownConstSubstsVisitor::search(&self, predicate),
1339                 _ => ControlFlow::CONTINUE,
1340             }
1341         }
1342     }
1343 }
1344
1345 struct UnknownConstSubstsVisitor<'tcx> {
1346     tcx: TyCtxt<'tcx>,
1347     flags: ty::TypeFlags,
1348 }
1349
1350 impl<'tcx> UnknownConstSubstsVisitor<'tcx> {
1351     /// This is fairly cold and we don't want to
1352     /// bloat the size of the `HasTypeFlagsVisitor`.
1353     #[inline(never)]
1354     pub fn search<T: TypeFoldable<'tcx>>(
1355         visitor: &HasTypeFlagsVisitor<'tcx>,
1356         v: T,
1357     ) -> ControlFlow<FoundFlags> {
1358         if visitor.flags.intersects(TypeFlags::MAY_NEED_DEFAULT_CONST_SUBSTS) {
1359             v.super_visit_with(&mut UnknownConstSubstsVisitor {
1360                 tcx: visitor.tcx.unwrap(),
1361                 flags: visitor.flags,
1362             })
1363         } else {
1364             ControlFlow::CONTINUE
1365         }
1366     }
1367 }
1368
1369 impl<'tcx> TypeVisitor<'tcx> for UnknownConstSubstsVisitor<'tcx> {
1370     type BreakTy = FoundFlags;
1371     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1372         bug!("we shouldn't call this method as we manually look at ct substs");
1373     }
1374
1375     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1376         if t.flags().intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1377             t.super_visit_with(self)
1378         } else {
1379             ControlFlow::CONTINUE
1380         }
1381     }
1382
1383     #[inline]
1384     fn visit_unevaluated_const(&mut self, uv: ty::Unevaluated<'tcx>) -> ControlFlow<Self::BreakTy> {
1385         if uv.substs_.is_none() {
1386             self.tcx
1387                 .default_anon_const_substs(uv.def.did)
1388                 .visit_with(&mut HasTypeFlagsVisitor { tcx: Some(self.tcx), flags: self.flags })
1389         } else {
1390             ControlFlow::CONTINUE
1391         }
1392     }
1393
1394     #[inline]
1395     fn visit_predicate(&mut self, predicate: ty::Predicate<'tcx>) -> ControlFlow<Self::BreakTy> {
1396         if predicate.inner.flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1397             predicate.super_visit_with(self)
1398         } else {
1399             ControlFlow::CONTINUE
1400         }
1401     }
1402 }
1403
1404 impl<'tcx> TyCtxt<'tcx> {
1405     /// This is a HACK(const_generics) and should probably not be needed.
1406     /// Might however be perf relevant, so who knows.
1407     ///
1408     /// FIXME(@lcnr): explain this function a bit more
1409     pub fn expose_default_const_substs<T: TypeFoldable<'tcx>>(self, v: T) -> T {
1410         v.fold_with(&mut ExposeDefaultConstSubstsFolder { tcx: self })
1411     }
1412 }
1413
1414 struct ExposeDefaultConstSubstsFolder<'tcx> {
1415     tcx: TyCtxt<'tcx>,
1416 }
1417
1418 impl<'tcx> TypeFolder<'tcx> for ExposeDefaultConstSubstsFolder<'tcx> {
1419     fn tcx(&self) -> TyCtxt<'tcx> {
1420         self.tcx
1421     }
1422
1423     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
1424         if ty.flags().intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1425             ty.super_fold_with(self)
1426         } else {
1427             ty
1428         }
1429     }
1430
1431     fn fold_predicate(&mut self, pred: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> {
1432         if pred.inner.flags.intersects(TypeFlags::HAS_UNKNOWN_DEFAULT_CONST_SUBSTS) {
1433             pred.super_fold_with(self)
1434         } else {
1435             pred
1436         }
1437     }
1438 }
1439
1440 /// Collects all the late-bound regions at the innermost binding level
1441 /// into a hash set.
1442 struct LateBoundRegionsCollector<'tcx> {
1443     tcx: TyCtxt<'tcx>,
1444     current_index: ty::DebruijnIndex,
1445     regions: FxHashSet<ty::BoundRegionKind>,
1446
1447     /// `true` if we only want regions that are known to be
1448     /// "constrained" when you equate this type with another type. In
1449     /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
1450     /// them constraints `'a == 'b`. But if you have `<&'a u32 as
1451     /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
1452     /// types may mean that `'a` and `'b` don't appear in the results,
1453     /// so they are not considered *constrained*.
1454     just_constrained: bool,
1455 }
1456
1457 impl LateBoundRegionsCollector<'tcx> {
1458     fn new(tcx: TyCtxt<'tcx>, just_constrained: bool) -> Self {
1459         LateBoundRegionsCollector {
1460             tcx,
1461             current_index: ty::INNERMOST,
1462             regions: Default::default(),
1463             just_constrained,
1464         }
1465     }
1466 }
1467
1468 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector<'tcx> {
1469     fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
1470         Some(self.tcx)
1471     }
1472
1473     fn visit_binder<T: TypeFoldable<'tcx>>(
1474         &mut self,
1475         t: &Binder<'tcx, T>,
1476     ) -> ControlFlow<Self::BreakTy> {
1477         self.current_index.shift_in(1);
1478         let result = t.super_visit_with(self);
1479         self.current_index.shift_out(1);
1480         result
1481     }
1482
1483     fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
1484         // if we are only looking for "constrained" region, we have to
1485         // ignore the inputs to a projection, as they may not appear
1486         // in the normalized form
1487         if self.just_constrained {
1488             if let ty::Projection(..) | ty::Opaque(..) = t.kind() {
1489                 return ControlFlow::CONTINUE;
1490             }
1491         }
1492
1493         t.super_visit_with(self)
1494     }
1495
1496     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
1497         // if we are only looking for "constrained" region, we have to
1498         // ignore the inputs of an unevaluated const, as they may not appear
1499         // in the normalized form
1500         if self.just_constrained {
1501             if let ty::ConstKind::Unevaluated(..) = c.val {
1502                 return ControlFlow::CONTINUE;
1503             }
1504         }
1505
1506         c.super_visit_with(self)
1507     }
1508
1509     fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
1510         if let ty::ReLateBound(debruijn, br) = *r {
1511             if debruijn == self.current_index {
1512                 self.regions.insert(br.kind);
1513             }
1514         }
1515         ControlFlow::CONTINUE
1516     }
1517 }