src/librustc/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
  34 use crate::hir::def_id::DefId;
  35 use crate::mir::interpret::ConstValue;
  36 use crate::ty::{self, Binder, Ty, TyCtxt, TypeFlags, flags::FlagComputation};
  37
  38 use std::collections::BTreeMap;
  39 use std::fmt;
  40 use crate::util::nodemap::FxHashSet;
  41
  42 /// The TypeFoldable trait is implemented for every type that can be folded.
  43 /// Basically, every type that has a corresponding method in TypeFolder.
  44 ///
  45 /// To implement this conveniently, use the
  46 /// `BraceStructTypeFoldableImpl` etc macros found in `macros.rs`.
  47 pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
  48     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self;
  49     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
  50         self.super_fold_with(folder)
  51     }
  52
  53     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool;
  54     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
  55         self.super_visit_with(visitor)
  56     }
  57
  58     /// Returns `true` if `self` has any late-bound regions that are either
  59     /// bound by `binder` or bound by some binder outside of `binder`.
  60     /// If `binder` is `ty::INNERMOST`, this indicates whether
  61     /// there are any late-bound regions that appear free.
  62     fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
  63         self.visit_with(&mut HasEscapingVarsVisitor { outer_index: binder })
  64     }
  65
  66     /// Returns `true` if this `self` has any regions that escape `binder` (and
  67     /// hence are not bound by it).
  68     fn has_vars_bound_above(&self, binder: ty::DebruijnIndex) -> bool {
  69         self.has_vars_bound_at_or_above(binder.shifted_in(1))
  70     }
  71
  72     fn has_escaping_bound_vars(&self) -> bool {
  73         self.has_vars_bound_at_or_above(ty::INNERMOST)
  74     }
  75
  76     fn has_type_flags(&self, flags: TypeFlags) -> bool {
  77         self.visit_with(&mut HasTypeFlagsVisitor { flags })
  78     }
  79     fn has_projections(&self) -> bool {
  80         self.has_type_flags(TypeFlags::HAS_PROJECTION)
  81     }
  82     fn references_error(&self) -> bool {
  83         self.has_type_flags(TypeFlags::HAS_TY_ERR)
  84     }
  85     fn has_param_types(&self) -> bool {
  86         self.has_type_flags(TypeFlags::HAS_PARAMS)
  87     }
  88     fn has_self_ty(&self) -> bool {
  89         self.has_type_flags(TypeFlags::HAS_SELF)
  90     }
  91     fn has_infer_types(&self) -> bool {
  92         self.has_type_flags(TypeFlags::HAS_TY_INFER)
  93     }
  94     fn needs_infer(&self) -> bool {
  95         self.has_type_flags(
  96             TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER | TypeFlags::HAS_CT_INFER
  97         )
  98     }
  99     fn has_placeholders(&self) -> bool {
 100         self.has_type_flags(TypeFlags::HAS_RE_PLACEHOLDER | TypeFlags::HAS_TY_PLACEHOLDER)
 101     }
 102     fn needs_subst(&self) -> bool {
 103         self.has_type_flags(TypeFlags::NEEDS_SUBST)
 104     }
 105     fn has_re_placeholders(&self) -> bool {
 106         self.has_type_flags(TypeFlags::HAS_RE_PLACEHOLDER)
 107     }
 108     fn has_closure_types(&self) -> bool {
 109         self.has_type_flags(TypeFlags::HAS_TY_CLOSURE)
 110     }
 111     /// "Free" regions in this context means that it has any region
 112     /// that is not (a) erased or (b) late-bound.
 113     fn has_free_regions(&self) -> bool {
 114         self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
 115     }
 116
 117     /// True if there are any un-erased free regions.
 118     fn has_erasable_regions(&self) -> bool {
 119         self.has_type_flags(TypeFlags::HAS_FREE_REGIONS)
 120     }
 121
 122     /// Indicates whether this value references only 'global'
 123     /// generic parameters that are the same regardless of what fn we are
 124     /// in. This is used for caching.
 125     fn is_global(&self) -> bool {
 126         !self.has_type_flags(TypeFlags::HAS_FREE_LOCAL_NAMES)
 127     }
 128
 129     /// True if there are any late-bound regions
 130     fn has_late_bound_regions(&self) -> bool {
 131         self.has_type_flags(TypeFlags::HAS_RE_LATE_BOUND)
 132     }
 133
 134     /// A visitor that does not recurse into types, works like `fn walk_shallow` in `Ty`.
 135     fn visit_tys_shallow(&self, visit: impl FnMut(Ty<'tcx>) -> bool) -> bool {
 136
 137         pub struct Visitor<F>(F);
 138
 139         impl<'tcx, F: FnMut(Ty<'tcx>) -> bool> TypeVisitor<'tcx> for Visitor<F> {
 140             fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 141                 self.0(ty)
 142             }
 143         }
 144
 145         self.visit_with(&mut Visitor(visit))
 146     }
 147 }
 148
 149 /// The `TypeFolder` trait defines the actual *folding*. There is a
 150 /// method defined for every foldable type. Each of these has a
 151 /// default implementation that does an "identity" fold. Within each
 152 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
 153 /// sub-item.
 154 pub trait TypeFolder<'gcx: 'tcx, 'tcx> : Sized {
 155     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx>;
 156
 157     fn fold_binder<T>(&mut self, t: &Binder<T>) -> Binder<T>
 158         where T : TypeFoldable<'tcx>
 159     {
 160         t.super_fold_with(self)
 161     }
 162
 163     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 164         t.super_fold_with(self)
 165     }
 166
 167     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 168         r.super_fold_with(self)
 169     }
 170
 171     fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 172         c.super_fold_with(self)
 173     }
 174 }
 175
 176 pub trait TypeVisitor<'tcx> : Sized {
 177     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 178         t.super_visit_with(self)
 179     }
 180
 181     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 182         t.super_visit_with(self)
 183     }
 184
 185     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 186         r.super_visit_with(self)
 187     }
 188
 189     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool {
 190         c.super_visit_with(self)
 191     }
 192 }
 193
 194 ///////////////////////////////////////////////////////////////////////////
 195 // Some sample folders
 196
 197 pub struct BottomUpFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a, F, G, H>
 198     where F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 199           G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 200           H: FnMut(&'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx>,
 201 {
 202     pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
 203     pub ty_op: F,
 204     pub lt_op: G,
 205     pub ct_op: H,
 206 }
 207
 208 impl<'a, 'gcx, 'tcx, F, G, H> TypeFolder<'gcx, 'tcx> for BottomUpFolder<'a, 'gcx, 'tcx, F, G, H>
 209     where F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 210           G: FnMut(ty::Region<'tcx>) -> ty::Region<'tcx>,
 211           H: FnMut(&'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx>,
 212 {
 213     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 214
 215     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 216         let t = ty.super_fold_with(self);
 217         (self.ty_op)(t)
 218     }
 219
 220     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 221         let r = r.super_fold_with(self);
 222         (self.lt_op)(r)
 223     }
 224
 225     fn fold_const(&mut self, ct: &'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx> {
 226         let ct = ct.super_fold_with(self);
 227         (self.ct_op)(ct)
 228     }
 229 }
 230
 231 ///////////////////////////////////////////////////////////////////////////
 232 // Region folder
 233
 234 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 235     /// Collects the free and escaping regions in `value` into `region_set`. Returns
 236     /// whether any late-bound regions were skipped
 237     pub fn collect_regions<T>(self,
 238         value: &T,
 239         region_set: &mut FxHashSet<ty::Region<'tcx>>)
 240         -> bool
 241         where T : TypeFoldable<'tcx>
 242     {
 243         let mut have_bound_regions = false;
 244         self.fold_regions(value, &mut have_bound_regions, |r, d| {
 245             region_set.insert(self.mk_region(r.shifted_out_to_binder(d)));
 246             r
 247         });
 248         have_bound_regions
 249     }
 250
 251     /// Folds the escaping and free regions in `value` using `f`, and
 252     /// sets `skipped_regions` to true if any late-bound region was found
 253     /// and skipped.
 254     pub fn fold_regions<T>(
 255         self,
 256         value: &T,
 257         skipped_regions: &mut bool,
 258         mut f: impl FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 259     ) -> T
 260     where
 261         T : TypeFoldable<'tcx>,
 262     {
 263         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f))
 264     }
 265
 266     /// Invoke `callback` on every region appearing free in `value`.
 267     pub fn for_each_free_region(
 268         self,
 269         value: &impl TypeFoldable<'tcx>,
 270         mut callback: impl FnMut(ty::Region<'tcx>),
 271     ) {
 272         self.any_free_region_meets(value, |r| {
 273             callback(r);
 274             false
 275         });
 276     }
 277
 278     /// Returns `true` if `callback` returns true for every region appearing free in `value`.
 279     pub fn all_free_regions_meet(
 280         self,
 281         value: &impl TypeFoldable<'tcx>,
 282         mut callback: impl FnMut(ty::Region<'tcx>) -> bool,
 283     ) -> bool {
 284         !self.any_free_region_meets(value, |r| !callback(r))
 285     }
 286
 287     /// Returns `true` if `callback` returns true for some region appearing free in `value`.
 288     pub fn any_free_region_meets(
 289         self,
 290         value: &impl TypeFoldable<'tcx>,
 291         callback: impl FnMut(ty::Region<'tcx>) -> bool,
 292     ) -> bool {
 293         return value.visit_with(&mut RegionVisitor {
 294             outer_index: ty::INNERMOST,
 295             callback
 296         });
 297
 298         struct RegionVisitor<F> {
 299             /// The index of a binder *just outside* the things we have
 300             /// traversed. If we encounter a bound region bound by this
 301             /// binder or one outer to it, it appears free. Example:
 302             ///
 303             /// ```
 304             ///    for<'a> fn(for<'b> fn(), T)
 305             /// ^          ^          ^     ^
 306             /// |          |          |     | here, would be shifted in 1
 307             /// |          |          | here, would be shifted in 2
 308             /// |          | here, would be `INNERMOST` shifted in by 1
 309             /// | here, initially, binder would be `INNERMOST`
 310             /// ```
 311             ///
 312             /// You see that, initially, *any* bound value is free,
 313             /// because we've not traversed any binders. As we pass
 314             /// through a binder, we shift the `outer_index` by 1 to
 315             /// account for the new binder that encloses us.
 316             outer_index: ty::DebruijnIndex,
 317             callback: F,
 318         }
 319
 320         impl<'tcx, F> TypeVisitor<'tcx> for RegionVisitor<F>
 321             where F: FnMut(ty::Region<'tcx>) -> bool
 322         {
 323             fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 324                 self.outer_index.shift_in(1);
 325                 let result = t.skip_binder().visit_with(self);
 326                 self.outer_index.shift_out(1);
 327                 result
 328             }
 329
 330             fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 331                 match *r {
 332                     ty::ReLateBound(debruijn, _) if debruijn < self.outer_index => {
 333                         false // ignore bound regions, keep visiting
 334                     }
 335                     _ => (self.callback)(r),
 336                 }
 337             }
 338
 339             fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 340                 // We're only interested in types involving regions
 341                 if ty.flags.intersects(TypeFlags::HAS_FREE_REGIONS) {
 342                     ty.super_visit_with(self)
 343                 } else {
 344                     false // keep visiting
 345                 }
 346             }
 347         }
 348     }
 349 }
 350
 351 /// Folds over the substructure of a type, visiting its component
 352 /// types and all regions that occur *free* within it.
 353 ///
 354 /// That is, `Ty` can contain function or method types that bind
 355 /// regions at the call site (`ReLateBound`), and occurrences of
 356 /// regions (aka "lifetimes") that are bound within a type are not
 357 /// visited by this folder; only regions that occur free will be
 358 /// visited by `fld_r`.
 359
 360 pub struct RegionFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 361     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 362     skipped_regions: &'a mut bool,
 363
 364     /// Stores the index of a binder *just outside* the stuff we have
 365     /// visited.  So this begins as INNERMOST; when we pass through a
 366     /// binder, it is incremented (via `shift_in`).
 367     current_index: ty::DebruijnIndex,
 368
 369     /// Callback invokes for each free region. The `DebruijnIndex`
 370     /// points to the binder *just outside* the ones we have passed
 371     /// through.
 372     fold_region_fn: &'a mut (dyn FnMut(
 373         ty::Region<'tcx>,
 374         ty::DebruijnIndex,
 375     ) -> ty::Region<'tcx> + 'a),
 376 }
 377
 378 impl<'a, 'gcx, 'tcx> RegionFolder<'a, 'gcx, 'tcx> {
 379     #[inline]
 380     pub fn new(
 381         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 382         skipped_regions: &'a mut bool,
 383         fold_region_fn: &'a mut dyn FnMut(ty::Region<'tcx>, ty::DebruijnIndex) -> ty::Region<'tcx>,
 384     ) -> RegionFolder<'a, 'gcx, 'tcx> {
 385         RegionFolder {
 386             tcx,
 387             skipped_regions,
 388             current_index: ty::INNERMOST,
 389             fold_region_fn,
 390         }
 391     }
 392 }
 393
 394 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFolder<'a, 'gcx, 'tcx> {
 395     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 396
 397     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 398         self.current_index.shift_in(1);
 399         let t = t.super_fold_with(self);
 400         self.current_index.shift_out(1);
 401         t
 402     }
 403
 404     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 405         match *r {
 406             ty::ReLateBound(debruijn, _) if debruijn < self.current_index => {
 407                 debug!("RegionFolder.fold_region({:?}) skipped bound region (current index={:?})",
 408                        r, self.current_index);
 409                 *self.skipped_regions = true;
 410                 r
 411             }
 412             _ => {
 413                 debug!("RegionFolder.fold_region({:?}) folding free region (current_index={:?})",
 414                        r, self.current_index);
 415                 (self.fold_region_fn)(r, self.current_index)
 416             }
 417         }
 418     }
 419 }
 420
 421 ///////////////////////////////////////////////////////////////////////////
 422 // Bound vars replacer
 423
 424 /// Replaces the escaping bound vars (late bound regions or bound types) in a type.
 425 struct BoundVarReplacer<'a, 'gcx: 'a + 'tcx, 'tcx: 'a> {
 426     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 427
 428     /// As with `RegionFolder`, represents the index of a binder *just outside*
 429     /// the ones we have visited.
 430     current_index: ty::DebruijnIndex,
 431
 432     fld_r: &'a mut (dyn FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
 433     fld_t: &'a mut (dyn FnMut(ty::BoundTy) -> Ty<'tcx> + 'a),
 434     fld_c: &'a mut (dyn FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::LazyConst<'tcx> + 'a),
 435 }
 436
 437 impl<'a, 'gcx, 'tcx> BoundVarReplacer<'a, 'gcx, 'tcx> {
 438     fn new<F, G, H>(
 439         tcx: TyCtxt<'a, 'gcx, 'tcx>,
 440         fld_r: &'a mut F,
 441         fld_t: &'a mut G,
 442         fld_c: &'a mut H,
 443     ) -> Self
 444         where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 445               G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 446               H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::LazyConst<'tcx>,
 447     {
 448         BoundVarReplacer {
 449             tcx,
 450             current_index: ty::INNERMOST,
 451             fld_r,
 452             fld_t,
 453             fld_c,
 454         }
 455     }
 456 }
 457
 458 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for BoundVarReplacer<'a, 'gcx, 'tcx> {
 459     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 460
 461     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 462         self.current_index.shift_in(1);
 463         let t = t.super_fold_with(self);
 464         self.current_index.shift_out(1);
 465         t
 466     }
 467
 468     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 469         match t.sty {
 470             ty::Bound(debruijn, bound_ty) => {
 471                 if debruijn == self.current_index {
 472                     let fld_t = &mut self.fld_t;
 473                     let ty = fld_t(bound_ty);
 474                     ty::fold::shift_vars(
 475                         self.tcx,
 476                         &ty,
 477                         self.current_index.as_u32()
 478                     )
 479                 } else {
 480                     t
 481                 }
 482             }
 483             _ => {
 484                 if !t.has_vars_bound_at_or_above(self.current_index) {
 485                     // Nothing more to substitute.
 486                     t
 487                 } else {
 488                     t.super_fold_with(self)
 489                 }
 490             }
 491         }
 492     }
 493
 494     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 495         match *r {
 496             ty::ReLateBound(debruijn, br) if debruijn == self.current_index => {
 497                 let fld_r = &mut self.fld_r;
 498                 let region = fld_r(br);
 499                 if let ty::ReLateBound(debruijn1, br) = *region {
 500                     // If the callback returns a late-bound region,
 501                     // that region should always use the INNERMOST
 502                     // debruijn index. Then we adjust it to the
 503                     // correct depth.
 504                     assert_eq!(debruijn1, ty::INNERMOST);
 505                     self.tcx.mk_region(ty::ReLateBound(debruijn, br))
 506                 } else {
 507                     region
 508                 }
 509             }
 510             _ => r
 511         }
 512     }
 513
 514     fn fold_const(&mut self, ct: &'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx> {
 515         if let ty::LazyConst::Evaluated(ty::Const {
 516             val: ConstValue::Infer(ty::InferConst::Canonical(debruijn, bound_const)),
 517             ty,
 518         }) = *ct {
 519             if debruijn == self.current_index {
 520                 let fld_c = &mut self.fld_c;
 521                 let ct = fld_c(bound_const, ty);
 522                 ty::fold::shift_vars(
 523                     self.tcx,
 524                     &ct,
 525                     self.current_index.as_u32()
 526                 )
 527             } else {
 528                 ct
 529             }
 530         } else {
 531             if !ct.has_vars_bound_at_or_above(self.current_index) {
 532                 // Nothing more to substitute.
 533                 ct
 534             } else {
 535                 ct.super_fold_with(self)
 536             }
 537         }
 538     }
 539 }
 540
 541 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 542     /// Replaces all regions bound by the given `Binder` with the
 543     /// results returned by the closure; the closure is expected to
 544     /// return a free region (relative to this binder), and hence the
 545     /// binder is removed in the return type. The closure is invoked
 546     /// once for each unique `BoundRegion`; multiple references to the
 547     /// same `BoundRegion` will reuse the previous result. A map is
 548     /// returned at the end with each bound region and the free region
 549     /// that replaced it.
 550     ///
 551     /// This method only replaces late bound regions and the result may still
 552     /// contain escaping bound types.
 553     pub fn replace_late_bound_regions<T, F>(
 554         self,
 555         value: &Binder<T>,
 556         fld_r: F
 557     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 558         where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 559               T: TypeFoldable<'tcx>
 560     {
 561         // identity for bound types and consts
 562         let fld_t = |bound_ty| self.mk_ty(ty::Bound(ty::INNERMOST, bound_ty));
 563         let fld_c = |bound_ct, ty| {
 564             self.mk_const_infer(ty::InferConst::Canonical(ty::INNERMOST, bound_ct), ty)
 565         };
 566         self.replace_escaping_bound_vars(value.skip_binder(), fld_r, fld_t, fld_c)
 567     }
 568
 569     /// Replaces all escaping bound vars. The `fld_r` closure replaces escaping
 570     /// bound regions; the `fld_t` closure replaces escaping bound types and the `fld_c`
 571     /// closure replaces escaping bound consts.
 572     pub fn replace_escaping_bound_vars<T, F, G, H>(
 573         self,
 574         value: &T,
 575         mut fld_r: F,
 576         mut fld_t: G,
 577         mut fld_c: H,
 578     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 579         where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 580               G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 581               H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::LazyConst<'tcx>,
 582               T: TypeFoldable<'tcx>,
 583     {
 584         use rustc_data_structures::fx::FxHashMap;
 585
 586         let mut region_map = BTreeMap::new();
 587         let mut type_map = FxHashMap::default();
 588         let mut const_map = FxHashMap::default();
 589
 590         if !value.has_escaping_bound_vars() {
 591             (value.clone(), region_map)
 592         } else {
 593             let mut real_fld_r = |br| {
 594                 *region_map.entry(br).or_insert_with(|| fld_r(br))
 595             };
 596
 597             let mut real_fld_t = |bound_ty| {
 598                 *type_map.entry(bound_ty).or_insert_with(|| fld_t(bound_ty))
 599             };
 600
 601             let mut real_fld_c = |bound_ct, ty| {
 602                 *const_map.entry(bound_ct).or_insert_with(|| fld_c(bound_ct, ty))
 603             };
 604
 605             let mut replacer = BoundVarReplacer::new(
 606                 self,
 607                 &mut real_fld_r,
 608                 &mut real_fld_t,
 609                 &mut real_fld_c,
 610             );
 611             let result = value.fold_with(&mut replacer);
 612             (result, region_map)
 613         }
 614     }
 615
 616     /// Replaces all types or regions bound by the given `Binder`. The `fld_r`
 617     /// closure replaces bound regions while the `fld_t` closure replaces bound
 618     /// types.
 619     pub fn replace_bound_vars<T, F, G, H>(
 620         self,
 621         value: &Binder<T>,
 622         fld_r: F,
 623         fld_t: G,
 624         fld_c: H,
 625     ) -> (T, BTreeMap<ty::BoundRegion, ty::Region<'tcx>>)
 626         where F: FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 627               G: FnMut(ty::BoundTy) -> Ty<'tcx>,
 628               H: FnMut(ty::BoundVar, Ty<'tcx>) -> &'tcx ty::LazyConst<'tcx>,
 629               T: TypeFoldable<'tcx>
 630     {
 631         self.replace_escaping_bound_vars(value.skip_binder(), fld_r, fld_t, fld_c)
 632     }
 633
 634     /// Replaces any late-bound regions bound in `value` with
 635     /// free variants attached to `all_outlive_scope`.
 636     pub fn liberate_late_bound_regions<T>(
 637         &self,
 638         all_outlive_scope: DefId,
 639         value: &ty::Binder<T>
 640     ) -> T
 641     where T: TypeFoldable<'tcx> {
 642         self.replace_late_bound_regions(value, |br| {
 643             self.mk_region(ty::ReFree(ty::FreeRegion {
 644                 scope: all_outlive_scope,
 645                 bound_region: br
 646             }))
 647         }).0
 648     }
 649
 650     /// Returns a set of all late-bound regions that are constrained
 651     /// by `value`, meaning that if we instantiate those LBR with
 652     /// variables and equate `value` with something else, those
 653     /// variables will also be equated.
 654     pub fn collect_constrained_late_bound_regions<T>(&self, value: &Binder<T>)
 655                                                      -> FxHashSet<ty::BoundRegion>
 656         where T : TypeFoldable<'tcx>
 657     {
 658         self.collect_late_bound_regions(value, true)
 659     }
 660
 661     /// Returns a set of all late-bound regions that appear in `value` anywhere.
 662     pub fn collect_referenced_late_bound_regions<T>(&self, value: &Binder<T>)
 663                                                     -> FxHashSet<ty::BoundRegion>
 664         where T : TypeFoldable<'tcx>
 665     {
 666         self.collect_late_bound_regions(value, false)
 667     }
 668
 669     fn collect_late_bound_regions<T>(&self, value: &Binder<T>, just_constraint: bool)
 670                                      -> FxHashSet<ty::BoundRegion>
 671         where T : TypeFoldable<'tcx>
 672     {
 673         let mut collector = LateBoundRegionsCollector::new(just_constraint);
 674         let result = value.skip_binder().visit_with(&mut collector);
 675         assert!(!result); // should never have stopped early
 676         collector.regions
 677     }
 678
 679     /// Replaces any late-bound regions bound in `value` with `'erased`. Useful in codegen but also
 680     /// method lookup and a few other places where precise region relationships are not required.
 681     pub fn erase_late_bound_regions<T>(self, value: &Binder<T>) -> T
 682         where T : TypeFoldable<'tcx>
 683     {
 684         self.replace_late_bound_regions(value, |_| self.lifetimes.re_erased).0
 685     }
 686
 687     /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
 688     /// assigned starting at 1 and increasing monotonically in the order traversed
 689     /// by the fold operation.
 690     ///
 691     /// The chief purpose of this function is to canonicalize regions so that two
 692     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 693     /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 694     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 695     pub fn anonymize_late_bound_regions<T>(self, sig: &Binder<T>) -> Binder<T>
 696         where T : TypeFoldable<'tcx>,
 697     {
 698         let mut counter = 0;
 699         Binder::bind(self.replace_late_bound_regions(sig, |_| {
 700             counter += 1;
 701             self.mk_region(ty::ReLateBound(ty::INNERMOST, ty::BrAnon(counter)))
 702         }).0)
 703     }
 704 }
 705
 706 ///////////////////////////////////////////////////////////////////////////
 707 // Shifter
 708 //
 709 // Shifts the De Bruijn indices on all escaping bound vars by a
 710 // fixed amount. Useful in substitution or when otherwise introducing
 711 // a binding level that is not intended to capture the existing bound
 712 // vars. See comment on `shift_vars_through_binders` method in
 713 // `subst.rs` for more details.
 714
 715 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 716 enum Direction {
 717     In,
 718     Out,
 719 }
 720
 721 struct Shifter<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 722     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 723     current_index: ty::DebruijnIndex,
 724     amount: u32,
 725     direction: Direction,
 726 }
 727
 728 impl Shifter<'a, 'gcx, 'tcx> {
 729     pub fn new(tcx: TyCtxt<'a, 'gcx, 'tcx>, amount: u32, direction: Direction) -> Self {
 730         Shifter {
 731             tcx,
 732             current_index: ty::INNERMOST,
 733             amount,
 734             direction,
 735         }
 736     }
 737 }
 738
 739 impl TypeFolder<'gcx, 'tcx> for Shifter<'a, 'gcx, 'tcx> {
 740     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 741
 742     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 743         self.current_index.shift_in(1);
 744         let t = t.super_fold_with(self);
 745         self.current_index.shift_out(1);
 746         t
 747     }
 748
 749     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 750         match *r {
 751             ty::ReLateBound(debruijn, br) => {
 752                 if self.amount == 0 || debruijn < self.current_index {
 753                     r
 754                 } else {
 755                     let debruijn = match self.direction {
 756                         Direction::In => debruijn.shifted_in(self.amount),
 757                         Direction::Out => {
 758                             assert!(debruijn.as_u32() >= self.amount);
 759                             debruijn.shifted_out(self.amount)
 760                         }
 761                     };
 762                     let shifted = ty::ReLateBound(debruijn, br);
 763                     self.tcx.mk_region(shifted)
 764                 }
 765             }
 766             _ => r
 767         }
 768     }
 769
 770     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 771         match ty.sty {
 772             ty::Bound(debruijn, bound_ty) => {
 773                 if self.amount == 0 || debruijn < self.current_index {
 774                     ty
 775                 } else {
 776                     let debruijn = match self.direction {
 777                         Direction::In => debruijn.shifted_in(self.amount),
 778                         Direction::Out => {
 779                             assert!(debruijn.as_u32() >= self.amount);
 780                             debruijn.shifted_out(self.amount)
 781                         }
 782                     };
 783                     self.tcx.mk_ty(
 784                         ty::Bound(debruijn, bound_ty)
 785                     )
 786                 }
 787             }
 788
 789             _ => ty.super_fold_with(self),
 790         }
 791     }
 792
 793     fn fold_const(&mut self, ct: &'tcx ty::LazyConst<'tcx>) -> &'tcx ty::LazyConst<'tcx> {
 794         if let ty::LazyConst::Evaluated(ty::Const {
 795             val: ConstValue::Infer(ty::InferConst::Canonical(debruijn, bound_const)),
 796             ty,
 797         }) = *ct {
 798             if self.amount == 0 || debruijn < self.current_index {
 799                 ct
 800             } else {
 801                 let debruijn = match self.direction {
 802                     Direction::In => debruijn.shifted_in(self.amount),
 803                     Direction::Out => {
 804                         assert!(debruijn.as_u32() >= self.amount);
 805                         debruijn.shifted_out(self.amount)
 806                     }
 807                 };
 808                 self.tcx.mk_const_infer(ty::InferConst::Canonical(debruijn, bound_const), ty)
 809             }
 810         } else {
 811             ct.super_fold_with(self)
 812         }
 813     }
 814 }
 815
 816 pub fn shift_region<'a, 'gcx, 'tcx>(
 817     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 818     region: ty::Region<'tcx>,
 819     amount: u32
 820 ) -> ty::Region<'tcx> {
 821     match region {
 822         ty::ReLateBound(debruijn, br) if amount > 0 => {
 823             tcx.mk_region(ty::ReLateBound(debruijn.shifted_in(amount), *br))
 824         }
 825         _ => {
 826             region
 827         }
 828     }
 829 }
 830
 831 pub fn shift_vars<'a, 'gcx, 'tcx, T>(
 832     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 833     value: &T,
 834     amount: u32
 835 ) -> T where T: TypeFoldable<'tcx> {
 836     debug!("shift_vars(value={:?}, amount={})",
 837            value, amount);
 838
 839     value.fold_with(&mut Shifter::new(tcx, amount, Direction::In))
 840 }
 841
 842 pub fn shift_out_vars<'a, 'gcx, 'tcx, T>(
 843     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 844     value: &T,
 845     amount: u32
 846 ) -> T where T: TypeFoldable<'tcx> {
 847     debug!("shift_out_vars(value={:?}, amount={})",
 848            value, amount);
 849
 850     value.fold_with(&mut Shifter::new(tcx, amount, Direction::Out))
 851 }
 852
 853 /// An "escaping var" is a bound var whose binder is not part of `t`. A bound var can be a
 854 /// bound region or a bound type.
 855 ///
 856 /// So, for example, consider a type like the following, which has two binders:
 857 ///
 858 ///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
 859 ///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
 860 ///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
 861 ///
 862 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
 863 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
 864 /// fn type*, that type has an escaping region: `'a`.
 865 ///
 866 /// Note that what I'm calling an "escaping var" is often just called a "free var". However,
 867 /// we already use the term "free var". It refers to the regions or types that we use to represent
 868 /// bound regions or type params on a fn definition while we are type checking its body.
 869 ///
 870 /// To clarify, conceptually there is no particular difference between
 871 /// an "escaping" var and a "free" var. However, there is a big
 872 /// difference in practice. Basically, when "entering" a binding
 873 /// level, one is generally required to do some sort of processing to
 874 /// a bound var, such as replacing it with a fresh/placeholder
 875 /// var, or making an entry in the environment to represent the
 876 /// scope to which it is attached, etc. An escaping var represents
 877 /// a bound var for which this processing has not yet been done.
 878 struct HasEscapingVarsVisitor {
 879     /// Anything bound by `outer_index` or "above" is escaping.
 880     outer_index: ty::DebruijnIndex,
 881 }
 882
 883 impl<'tcx> TypeVisitor<'tcx> for HasEscapingVarsVisitor {
 884     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 885         self.outer_index.shift_in(1);
 886         let result = t.super_visit_with(self);
 887         self.outer_index.shift_out(1);
 888         result
 889     }
 890
 891     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 892         // If the outer-exclusive-binder is *strictly greater* than
 893         // `outer_index`, that means that `t` contains some content
 894         // bound at `outer_index` or above (because
 895         // `outer_exclusive_binder` is always 1 higher than the
 896         // content in `t`). Therefore, `t` has some escaping vars.
 897         t.outer_exclusive_binder > self.outer_index
 898     }
 899
 900     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 901         // If the region is bound by `outer_index` or anything outside
 902         // of outer index, then it escapes the binders we have
 903         // visited.
 904         r.bound_at_or_above_binder(self.outer_index)
 905     }
 906
 907     fn visit_const(&mut self, ct: &'tcx ty::LazyConst<'tcx>) -> bool {
 908         if let ty::LazyConst::Evaluated(ty::Const {
 909             val: ConstValue::Infer(ty::InferConst::Canonical(debruijn, _)),
 910             ..
 911         }) = *ct {
 912             debruijn >= self.outer_index
 913         } else {
 914             false
 915         }
 916     }
 917 }
 918
 919 struct HasTypeFlagsVisitor {
 920     flags: ty::TypeFlags,
 921 }
 922
 923 impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor {
 924     fn visit_ty(&mut self, t: Ty<'_>) -> bool {
 925         debug!("HasTypeFlagsVisitor: t={:?} t.flags={:?} self.flags={:?}", t, t.flags, self.flags);
 926         t.flags.intersects(self.flags)
 927     }
 928
 929     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 930         let flags = r.type_flags();
 931         debug!("HasTypeFlagsVisitor: r={:?} r.flags={:?} self.flags={:?}", r, flags, self.flags);
 932         flags.intersects(self.flags)
 933     }
 934
 935     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool {
 936         let flags = FlagComputation::for_const(c);
 937         debug!("HasTypeFlagsVisitor: c={:?} c.flags={:?} self.flags={:?}", c, flags, self.flags);
 938         flags.intersects(self.flags) || c.super_visit_with(self)
 939     }
 940 }
 941
 942 /// Collects all the late-bound regions at the innermost binding level
 943 /// into a hash set.
 944 struct LateBoundRegionsCollector {
 945     current_index: ty::DebruijnIndex,
 946     regions: FxHashSet<ty::BoundRegion>,
 947
 948     /// `true` if we only want regions that are known to be
 949     /// "constrained" when you equate this type with another type. In
 950     /// particular, if you have e.g., `&'a u32` and `&'b u32`, equating
 951     /// them constraints `'a == 'b`. But if you have `<&'a u32 as
 952     /// Trait>::Foo` and `<&'b u32 as Trait>::Foo`, normalizing those
 953     /// types may mean that `'a` and `'b` don't appear in the results,
 954     /// so they are not considered *constrained*.
 955     just_constrained: bool,
 956 }
 957
 958 impl LateBoundRegionsCollector {
 959     fn new(just_constrained: bool) -> Self {
 960         LateBoundRegionsCollector {
 961             current_index: ty::INNERMOST,
 962             regions: Default::default(),
 963             just_constrained,
 964         }
 965     }
 966 }
 967
 968 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
 969     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 970         self.current_index.shift_in(1);
 971         let result = t.super_visit_with(self);
 972         self.current_index.shift_out(1);
 973         result
 974     }
 975
 976     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 977         // if we are only looking for "constrained" region, we have to
 978         // ignore the inputs to a projection, as they may not appear
 979         // in the normalized form
 980         if self.just_constrained {
 981             match t.sty {
 982                 ty::Projection(..) | ty::Opaque(..) => { return false; }
 983                 _ => { }
 984             }
 985         }
 986
 987         t.super_visit_with(self)
 988     }
 989
 990     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 991         if let ty::ReLateBound(debruijn, br) = *r {
 992              if debruijn == self.current_index {
 993                 self.regions.insert(br);
 994             }
 995         }
 996         false
 997     }
 998 }