src/librustc/ty/fold.rs

   1 // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Generalized type folding mechanism. The setup is a bit convoluted
  12 //! but allows for convenient usage. Let T be an instance of some
  13 //! "foldable type" (one which implements `TypeFoldable`) and F be an
  14 //! instance of a "folder" (a type which implements `TypeFolder`). Then
  15 //! the setup is intended to be:
  16 //!
  17 //!   T.fold_with(F) --calls--> F.fold_T(T) --calls--> T.super_fold_with(F)
  18 //!
  19 //! This way, when you define a new folder F, you can override
  20 //! `fold_T()` to customize the behavior, and invoke `T.super_fold_with()`
  21 //! to get the original behavior. Meanwhile, to actually fold
  22 //! something, you can just write `T.fold_with(F)`, which is
  23 //! convenient. (Note that `fold_with` will also transparently handle
  24 //! things like a `Vec<T>` where T is foldable and so on.)
  25 //!
  26 //! In this ideal setup, the only function that actually *does*
  27 //! anything is `T.super_fold_with()`, which traverses the type `T`.
  28 //! Moreover, `T.super_fold_with()` should only ever call `T.fold_with()`.
  29 //!
  30 //! In some cases, we follow a degenerate pattern where we do not have
  31 //! a `fold_T` method. Instead, `T.fold_with` traverses the structure directly.
  32 //! This is suboptimal because the behavior cannot be overridden, but it's
  33 //! much less work to implement. If you ever *do* need an override that
  34 //! doesn't exist, it's not hard to convert the degenerate pattern into the
  35 //! proper thing.
  36 //!
  37 //! A `TypeFoldable` T can also be visited by a `TypeVisitor` V using similar setup:
  38 //!   T.visit_with(V) --calls--> V.visit_T(T) --calls--> T.super_visit_with(V).
  39 //! These methods return true to indicate that the visitor has found what it is looking for
  40 //! and does not need to visit anything else.
  41
  42 use middle::const_val::ConstVal;
  43 use ty::{self, Binder, Ty, TyCtxt, TypeFlags};
  44
  45 use std::fmt;
  46 use util::nodemap::{FxHashMap, FxHashSet};
  47
  48 /// The TypeFoldable trait is implemented for every type that can be folded.
  49 /// Basically, every type that has a corresponding method in TypeFolder.
  50 pub trait TypeFoldable<'tcx>: fmt::Debug + Clone {
  51     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self;
  52     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
  53         self.super_fold_with(folder)
  54     }
  55
  56     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool;
  57     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
  58         self.super_visit_with(visitor)
  59     }
  60
  61     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  62         self.visit_with(&mut HasEscapingRegionsVisitor { depth: depth })
  63     }
  64     fn has_escaping_regions(&self) -> bool {
  65         self.has_regions_escaping_depth(0)
  66     }
  67
  68     fn has_type_flags(&self, flags: TypeFlags) -> bool {
  69         self.visit_with(&mut HasTypeFlagsVisitor { flags: flags })
  70     }
  71     fn has_projections(&self) -> bool {
  72         self.has_type_flags(TypeFlags::HAS_PROJECTION)
  73     }
  74     fn references_error(&self) -> bool {
  75         self.has_type_flags(TypeFlags::HAS_TY_ERR)
  76     }
  77     fn has_param_types(&self) -> bool {
  78         self.has_type_flags(TypeFlags::HAS_PARAMS)
  79     }
  80     fn has_self_ty(&self) -> bool {
  81         self.has_type_flags(TypeFlags::HAS_SELF)
  82     }
  83     fn has_infer_types(&self) -> bool {
  84         self.has_type_flags(TypeFlags::HAS_TY_INFER)
  85     }
  86     fn needs_infer(&self) -> bool {
  87         self.has_type_flags(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER)
  88     }
  89     fn needs_subst(&self) -> bool {
  90         self.has_type_flags(TypeFlags::NEEDS_SUBST)
  91     }
  92     fn has_re_skol(&self) -> bool {
  93         self.has_type_flags(TypeFlags::HAS_RE_SKOL)
  94     }
  95     fn has_closure_types(&self) -> bool {
  96         self.has_type_flags(TypeFlags::HAS_TY_CLOSURE)
  97     }
  98     fn has_erasable_regions(&self) -> bool {
  99         self.has_type_flags(TypeFlags::HAS_RE_EARLY_BOUND |
 100                             TypeFlags::HAS_RE_INFER |
 101                             TypeFlags::HAS_FREE_REGIONS)
 102     }
 103     fn is_normalized_for_trans(&self) -> bool {
 104         !self.has_type_flags(TypeFlags::HAS_RE_EARLY_BOUND |
 105                              TypeFlags::HAS_RE_INFER |
 106                              TypeFlags::HAS_FREE_REGIONS |
 107                              TypeFlags::HAS_TY_INFER |
 108                              TypeFlags::HAS_PARAMS |
 109                              TypeFlags::HAS_NORMALIZABLE_PROJECTION |
 110                              TypeFlags::HAS_TY_ERR |
 111                              TypeFlags::HAS_SELF)
 112     }
 113     /// Indicates whether this value references only 'global'
 114     /// types/lifetimes that are the same regardless of what fn we are
 115     /// in. This is used for caching. Errs on the side of returning
 116     /// false.
 117     fn is_global(&self) -> bool {
 118         !self.has_type_flags(TypeFlags::HAS_LOCAL_NAMES)
 119     }
 120 }
 121
 122 /// The TypeFolder trait defines the actual *folding*. There is a
 123 /// method defined for every foldable type. Each of these has a
 124 /// default implementation that does an "identity" fold. Within each
 125 /// identity fold, it should invoke `foo.fold_with(self)` to fold each
 126 /// sub-item.
 127 pub trait TypeFolder<'gcx: 'tcx, 'tcx> : Sized {
 128     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'gcx, 'tcx>;
 129
 130     fn fold_binder<T>(&mut self, t: &Binder<T>) -> Binder<T>
 131         where T : TypeFoldable<'tcx>
 132     {
 133         t.super_fold_with(self)
 134     }
 135
 136     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 137         t.super_fold_with(self)
 138     }
 139
 140     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 141         r.super_fold_with(self)
 142     }
 143
 144     fn fold_const(&mut self, c: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> {
 145         c.super_fold_with(self)
 146     }
 147 }
 148
 149 pub trait TypeVisitor<'tcx> : Sized {
 150     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 151         t.super_visit_with(self)
 152     }
 153
 154     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 155         t.super_visit_with(self)
 156     }
 157
 158     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 159         r.super_visit_with(self)
 160     }
 161
 162     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool {
 163         c.super_visit_with(self)
 164     }
 165 }
 166
 167 ///////////////////////////////////////////////////////////////////////////
 168 // Some sample folders
 169
 170 pub struct BottomUpFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a, F>
 171     where F: FnMut(Ty<'tcx>) -> Ty<'tcx>
 172 {
 173     pub tcx: TyCtxt<'a, 'gcx, 'tcx>,
 174     pub fldop: F,
 175 }
 176
 177 impl<'a, 'gcx, 'tcx, F> TypeFolder<'gcx, 'tcx> for BottomUpFolder<'a, 'gcx, 'tcx, F>
 178     where F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
 179 {
 180     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 181
 182     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 183         let t1 = ty.super_fold_with(self);
 184         (self.fldop)(t1)
 185     }
 186 }
 187
 188 ///////////////////////////////////////////////////////////////////////////
 189 // Region folder
 190
 191 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 192     /// Collects the free and escaping regions in `value` into `region_set`. Returns
 193     /// whether any late-bound regions were skipped
 194     pub fn collect_regions<T>(self,
 195         value: &T,
 196         region_set: &mut FxHashSet<ty::Region<'tcx>>)
 197         -> bool
 198         where T : TypeFoldable<'tcx>
 199     {
 200         let mut have_bound_regions = false;
 201         self.fold_regions(value, &mut have_bound_regions, |r, d| {
 202             region_set.insert(self.mk_region(r.from_depth(d)));
 203             r
 204         });
 205         have_bound_regions
 206     }
 207
 208     /// Folds the escaping and free regions in `value` using `f`, and
 209     /// sets `skipped_regions` to true if any late-bound region was found
 210     /// and skipped.
 211     pub fn fold_regions<T,F>(self,
 212         value: &T,
 213         skipped_regions: &mut bool,
 214         mut f: F)
 215         -> T
 216         where F : FnMut(ty::Region<'tcx>, u32) -> ty::Region<'tcx>,
 217               T : TypeFoldable<'tcx>,
 218     {
 219         value.fold_with(&mut RegionFolder::new(self, skipped_regions, &mut f))
 220     }
 221 }
 222
 223 /// Folds over the substructure of a type, visiting its component
 224 /// types and all regions that occur *free* within it.
 225 ///
 226 /// That is, `Ty` can contain function or method types that bind
 227 /// regions at the call site (`ReLateBound`), and occurrences of
 228 /// regions (aka "lifetimes") that are bound within a type are not
 229 /// visited by this folder; only regions that occur free will be
 230 /// visited by `fld_r`.
 231
 232 pub struct RegionFolder<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 233     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 234     skipped_regions: &'a mut bool,
 235     current_depth: u32,
 236     fld_r: &'a mut (FnMut(ty::Region<'tcx>, u32) -> ty::Region<'tcx> + 'a),
 237 }
 238
 239 impl<'a, 'gcx, 'tcx> RegionFolder<'a, 'gcx, 'tcx> {
 240     pub fn new<F>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 241                   skipped_regions: &'a mut bool,
 242                   fld_r: &'a mut F) -> RegionFolder<'a, 'gcx, 'tcx>
 243         where F : FnMut(ty::Region<'tcx>, u32) -> ty::Region<'tcx>
 244     {
 245         RegionFolder {
 246             tcx,
 247             skipped_regions,
 248             current_depth: 1,
 249             fld_r,
 250         }
 251     }
 252 }
 253
 254 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionFolder<'a, 'gcx, 'tcx> {
 255     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 256
 257     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 258         self.current_depth += 1;
 259         let t = t.super_fold_with(self);
 260         self.current_depth -= 1;
 261         t
 262     }
 263
 264     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 265         match *r {
 266             ty::ReLateBound(debruijn, _) if debruijn.depth < self.current_depth => {
 267                 debug!("RegionFolder.fold_region({:?}) skipped bound region (current depth={})",
 268                        r, self.current_depth);
 269                 *self.skipped_regions = true;
 270                 r
 271             }
 272             _ => {
 273                 debug!("RegionFolder.fold_region({:?}) folding free region (current_depth={})",
 274                        r, self.current_depth);
 275                 (self.fld_r)(r, self.current_depth)
 276             }
 277         }
 278     }
 279 }
 280
 281 ///////////////////////////////////////////////////////////////////////////
 282 // Late-bound region replacer
 283
 284 // Replaces the escaping regions in a type.
 285
 286 struct RegionReplacer<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
 287     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 288     current_depth: u32,
 289     fld_r: &'a mut (FnMut(ty::BoundRegion) -> ty::Region<'tcx> + 'a),
 290     map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>
 291 }
 292
 293 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 294     pub fn replace_late_bound_regions<T,F>(self,
 295         value: &Binder<T>,
 296         mut f: F)
 297         -> (T, FxHashMap<ty::BoundRegion, ty::Region<'tcx>>)
 298         where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx>,
 299               T : TypeFoldable<'tcx>,
 300     {
 301         let mut replacer = RegionReplacer::new(self, &mut f);
 302         let result = value.skip_binder().fold_with(&mut replacer);
 303         (result, replacer.map)
 304     }
 305
 306     /// Flattens two binding levels into one. So `for<'a> for<'b> Foo`
 307     /// becomes `for<'a,'b> Foo`.
 308     pub fn flatten_late_bound_regions<T>(self, bound2_value: &Binder<Binder<T>>)
 309                                          -> Binder<T>
 310         where T: TypeFoldable<'tcx>
 311     {
 312         let bound0_value = bound2_value.skip_binder().skip_binder();
 313         let value = self.fold_regions(bound0_value, &mut false,
 314                                       |region, current_depth| {
 315             match *region {
 316                 ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => {
 317                     // should be true if no escaping regions from bound2_value
 318                     assert!(debruijn.depth - current_depth <= 1);
 319                     self.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(current_depth), br))
 320                 }
 321                 _ => {
 322                     region
 323                 }
 324             }
 325         });
 326         Binder(value)
 327     }
 328
 329     pub fn no_late_bound_regions<T>(self, value: &Binder<T>) -> Option<T>
 330         where T : TypeFoldable<'tcx>
 331     {
 332         if value.0.has_escaping_regions() {
 333             None
 334         } else {
 335             Some(value.0.clone())
 336         }
 337     }
 338
 339     /// Returns a set of all late-bound regions that are constrained
 340     /// by `value`, meaning that if we instantiate those LBR with
 341     /// variables and equate `value` with something else, those
 342     /// variables will also be equated.
 343     pub fn collect_constrained_late_bound_regions<T>(&self, value: &Binder<T>)
 344                                                      -> FxHashSet<ty::BoundRegion>
 345         where T : TypeFoldable<'tcx>
 346     {
 347         self.collect_late_bound_regions(value, true)
 348     }
 349
 350     /// Returns a set of all late-bound regions that appear in `value` anywhere.
 351     pub fn collect_referenced_late_bound_regions<T>(&self, value: &Binder<T>)
 352                                                     -> FxHashSet<ty::BoundRegion>
 353         where T : TypeFoldable<'tcx>
 354     {
 355         self.collect_late_bound_regions(value, false)
 356     }
 357
 358     fn collect_late_bound_regions<T>(&self, value: &Binder<T>, just_constraint: bool)
 359                                      -> FxHashSet<ty::BoundRegion>
 360         where T : TypeFoldable<'tcx>
 361     {
 362         let mut collector = LateBoundRegionsCollector::new(just_constraint);
 363         let result = value.skip_binder().visit_with(&mut collector);
 364         assert!(!result); // should never have stopped early
 365         collector.regions
 366     }
 367
 368     /// Replace any late-bound regions bound in `value` with `'erased`. Useful in trans but also
 369     /// method lookup and a few other places where precise region relationships are not required.
 370     pub fn erase_late_bound_regions<T>(self, value: &Binder<T>) -> T
 371         where T : TypeFoldable<'tcx>
 372     {
 373         self.replace_late_bound_regions(value, |_| self.types.re_erased).0
 374     }
 375
 376     /// Rewrite any late-bound regions so that they are anonymous.  Region numbers are
 377     /// assigned starting at 1 and increasing monotonically in the order traversed
 378     /// by the fold operation.
 379     ///
 380     /// The chief purpose of this function is to canonicalize regions so that two
 381     /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
 382     /// structurally identical.  For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
 383     /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
 384     pub fn anonymize_late_bound_regions<T>(self, sig: &Binder<T>) -> Binder<T>
 385         where T : TypeFoldable<'tcx>,
 386     {
 387         let mut counter = 0;
 388         Binder(self.replace_late_bound_regions(sig, |_| {
 389             counter += 1;
 390             self.mk_region(ty::ReLateBound(ty::DebruijnIndex::new(1), ty::BrAnon(counter)))
 391         }).0)
 392     }
 393 }
 394
 395 impl<'a, 'gcx, 'tcx> RegionReplacer<'a, 'gcx, 'tcx> {
 396     fn new<F>(tcx: TyCtxt<'a, 'gcx, 'tcx>, fld_r: &'a mut F)
 397               -> RegionReplacer<'a, 'gcx, 'tcx>
 398         where F : FnMut(ty::BoundRegion) -> ty::Region<'tcx>
 399     {
 400         RegionReplacer {
 401             tcx,
 402             current_depth: 1,
 403             fld_r,
 404             map: FxHashMap()
 405         }
 406     }
 407 }
 408
 409 impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionReplacer<'a, 'gcx, 'tcx> {
 410     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.tcx }
 411
 412     fn fold_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T> {
 413         self.current_depth += 1;
 414         let t = t.super_fold_with(self);
 415         self.current_depth -= 1;
 416         t
 417     }
 418
 419     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 420         if !t.has_regions_escaping_depth(self.current_depth-1) {
 421             return t;
 422         }
 423
 424         t.super_fold_with(self)
 425     }
 426
 427     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 428         match *r {
 429             ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => {
 430                 let fld_r = &mut self.fld_r;
 431                 let region = *self.map.entry(br).or_insert_with(|| fld_r(br));
 432                 if let ty::ReLateBound(debruijn1, br) = *region {
 433                     // If the callback returns a late-bound region,
 434                     // that region should always use depth 1. Then we
 435                     // adjust it to the correct depth.
 436                     assert_eq!(debruijn1.depth, 1);
 437                     self.tcx.mk_region(ty::ReLateBound(debruijn, br))
 438                 } else {
 439                     region
 440                 }
 441             }
 442             _ => r
 443         }
 444     }
 445 }
 446
 447 ///////////////////////////////////////////////////////////////////////////
 448 // Region eraser
 449
 450 impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
 451     /// Returns an equivalent value with all free regions removed (note
 452     /// that late-bound regions remain, because they are important for
 453     /// subtyping, but they are anonymized and normalized as well)..
 454     pub fn erase_regions<T>(self, value: &T) -> T
 455         where T : TypeFoldable<'tcx>
 456     {
 457         let value1 = value.fold_with(&mut RegionEraser(self));
 458         debug!("erase_regions({:?}) = {:?}",
 459                value, value1);
 460         return value1;
 461
 462         struct RegionEraser<'a, 'gcx: 'a+'tcx, 'tcx: 'a>(TyCtxt<'a, 'gcx, 'tcx>);
 463
 464         impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for RegionEraser<'a, 'gcx, 'tcx> {
 465             fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { self.0 }
 466
 467             fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 468                 if let Some(u) = self.tcx().normalized_cache.borrow().get(&ty).cloned() {
 469                     return u;
 470                 }
 471
 472                 // FIXME(eddyb) should local contexts have a cache too?
 473                 if let Some(ty_lifted) = self.tcx().lift_to_global(&ty) {
 474                     let tcx = self.tcx().global_tcx();
 475                     let t_norm = ty_lifted.super_fold_with(&mut RegionEraser(tcx));
 476                     tcx.normalized_cache.borrow_mut().insert(ty_lifted, t_norm);
 477                     t_norm
 478                 } else {
 479                     ty.super_fold_with(self)
 480                 }
 481             }
 482
 483             fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
 484                 where T : TypeFoldable<'tcx>
 485             {
 486                 let u = self.tcx().anonymize_late_bound_regions(t);
 487                 u.super_fold_with(self)
 488             }
 489
 490             fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 491                 // because late-bound regions affect subtyping, we can't
 492                 // erase the bound/free distinction, but we can replace
 493                 // all free regions with 'erased.
 494                 //
 495                 // Note that we *CAN* replace early-bound regions -- the
 496                 // type system never "sees" those, they get substituted
 497                 // away. In trans, they will always be erased to 'erased
 498                 // whenever a substitution occurs.
 499                 match *r {
 500                     ty::ReLateBound(..) => r,
 501                     _ => self.tcx().types.re_erased
 502                 }
 503             }
 504         }
 505     }
 506 }
 507
 508 ///////////////////////////////////////////////////////////////////////////
 509 // Region shifter
 510 //
 511 // Shifts the De Bruijn indices on all escaping bound regions by a
 512 // fixed amount. Useful in substitution or when otherwise introducing
 513 // a binding level that is not intended to capture the existing bound
 514 // regions. See comment on `shift_regions_through_binders` method in
 515 // `subst.rs` for more details.
 516
 517 pub fn shift_region(region: ty::RegionKind, amount: u32) -> ty::RegionKind {
 518     match region {
 519         ty::ReLateBound(debruijn, br) => {
 520             ty::ReLateBound(debruijn.shifted(amount), br)
 521         }
 522         _ => {
 523             region
 524         }
 525     }
 526 }
 527
 528 pub fn shift_region_ref<'a, 'gcx, 'tcx>(
 529     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 530     region: ty::Region<'tcx>,
 531     amount: u32)
 532     -> ty::Region<'tcx>
 533 {
 534     match region {
 535         &ty::ReLateBound(debruijn, br) if amount > 0 => {
 536             tcx.mk_region(ty::ReLateBound(debruijn.shifted(amount), br))
 537         }
 538         _ => {
 539             region
 540         }
 541     }
 542 }
 543
 544 pub fn shift_regions<'a, 'gcx, 'tcx, T>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
 545                                         amount: u32,
 546                                         value: &T) -> T
 547     where T: TypeFoldable<'tcx>
 548 {
 549     debug!("shift_regions(value={:?}, amount={})",
 550            value, amount);
 551
 552     value.fold_with(&mut RegionFolder::new(tcx, &mut false, &mut |region, _current_depth| {
 553         shift_region_ref(tcx, region, amount)
 554     }))
 555 }
 556
 557 /// An "escaping region" is a bound region whose binder is not part of `t`.
 558 ///
 559 /// So, for example, consider a type like the following, which has two binders:
 560 ///
 561 ///    for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
 562 ///    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
 563 ///                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~  inner scope
 564 ///
 565 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
 566 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
 567 /// fn type*, that type has an escaping region: `'a`.
 568 ///
 569 /// Note that what I'm calling an "escaping region" is often just called a "free region". However,
 570 /// we already use the term "free region". It refers to the regions that we use to represent bound
 571 /// regions on a fn definition while we are typechecking its body.
 572 ///
 573 /// To clarify, conceptually there is no particular difference between an "escaping" region and a
 574 /// "free" region. However, there is a big difference in practice. Basically, when "entering" a
 575 /// binding level, one is generally required to do some sort of processing to a bound region, such
 576 /// as replacing it with a fresh/skolemized region, or making an entry in the environment to
 577 /// represent the scope to which it is attached, etc. An escaping region represents a bound region
 578 /// for which this processing has not yet been done.
 579 struct HasEscapingRegionsVisitor {
 580     depth: u32,
 581 }
 582
 583 impl<'tcx> TypeVisitor<'tcx> for HasEscapingRegionsVisitor {
 584     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 585         self.depth += 1;
 586         let result = t.super_visit_with(self);
 587         self.depth -= 1;
 588         result
 589     }
 590
 591     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 592         t.region_depth > self.depth
 593     }
 594
 595     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 596         r.escapes_depth(self.depth)
 597     }
 598 }
 599
 600 struct HasTypeFlagsVisitor {
 601     flags: ty::TypeFlags,
 602 }
 603
 604 impl<'tcx> TypeVisitor<'tcx> for HasTypeFlagsVisitor {
 605     fn visit_ty(&mut self, t: Ty) -> bool {
 606         debug!("HasTypeFlagsVisitor: t={:?} t.flags={:?} self.flags={:?}", t, t.flags, self.flags);
 607         t.flags.intersects(self.flags)
 608     }
 609
 610     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 611         let flags = r.type_flags();
 612         debug!("HasTypeFlagsVisitor: r={:?} r.flags={:?} self.flags={:?}", r, flags, self.flags);
 613         flags.intersects(self.flags)
 614     }
 615
 616     fn visit_const(&mut self, c: &'tcx ty::Const<'tcx>) -> bool {
 617         if let ConstVal::Unevaluated(..) = c.val {
 618             let projection_flags = TypeFlags::HAS_NORMALIZABLE_PROJECTION |
 619                 TypeFlags::HAS_PROJECTION;
 620             if projection_flags.intersects(self.flags) {
 621                 return true;
 622             }
 623         }
 624         c.super_visit_with(self)
 625     }
 626 }
 627
 628 /// Collects all the late-bound regions it finds into a hash set.
 629 struct LateBoundRegionsCollector {
 630     current_depth: u32,
 631     regions: FxHashSet<ty::BoundRegion>,
 632     just_constrained: bool,
 633 }
 634
 635 impl LateBoundRegionsCollector {
 636     fn new(just_constrained: bool) -> Self {
 637         LateBoundRegionsCollector {
 638             current_depth: 1,
 639             regions: FxHashSet(),
 640             just_constrained,
 641         }
 642     }
 643 }
 644
 645 impl<'tcx> TypeVisitor<'tcx> for LateBoundRegionsCollector {
 646     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &Binder<T>) -> bool {
 647         self.current_depth += 1;
 648         let result = t.super_visit_with(self);
 649         self.current_depth -= 1;
 650         result
 651     }
 652
 653     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 654         // if we are only looking for "constrained" region, we have to
 655         // ignore the inputs to a projection, as they may not appear
 656         // in the normalized form
 657         if self.just_constrained {
 658             match t.sty {
 659                 ty::TyProjection(..) | ty::TyAnon(..) => { return false; }
 660                 _ => { }
 661             }
 662         }
 663
 664         t.super_visit_with(self)
 665     }
 666
 667     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 668         match *r {
 669             ty::ReLateBound(debruijn, br) if debruijn.depth == self.current_depth => {
 670                 self.regions.insert(br);
 671             }
 672             _ => { }
 673         }
 674         false
 675     }
 676 }