src/librustc/middle/ty/structural_impls.rs

   1 // Copyright 2012-2015 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 use middle::subst::{self, VecPerParamSpace};
  12 use middle::traits;
  13 use middle::ty::{self, TraitRef, Ty, TypeAndMut};
  14 use middle::ty::{HasTypeFlags, Lift, TypeFlags, RegionEscape};
  15 use middle::ty::fold::{TypeFoldable, TypeFolder};
  16
  17 use std::rc::Rc;
  18 use syntax::abi;
  19 use syntax::owned_slice::OwnedSlice;
  20
  21 use rustc_front::hir;
  22
  23 // FIXME(#20298) -- all of these traits basically walk various
  24 // structures to test whether types/regions are reachable with various
  25 // properties. It should be possible to express them in terms of one
  26 // common "walker" trait or something.
  27
  28 impl<'tcx> RegionEscape for Ty<'tcx> {
  29     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  30         self.region_depth > depth
  31     }
  32 }
  33
  34 impl<'tcx> RegionEscape for ty::TraitTy<'tcx> {
  35     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  36         self.principal.has_regions_escaping_depth(depth) ||
  37             self.bounds.has_regions_escaping_depth(depth)
  38     }
  39 }
  40
  41 impl<'tcx> RegionEscape for ty::ExistentialBounds<'tcx> {
  42     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  43         self.region_bound.has_regions_escaping_depth(depth) ||
  44             self.projection_bounds.has_regions_escaping_depth(depth)
  45     }
  46 }
  47
  48 impl<'tcx> RegionEscape for subst::Substs<'tcx> {
  49     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  50         self.types.has_regions_escaping_depth(depth) ||
  51             self.regions.has_regions_escaping_depth(depth)
  52     }
  53 }
  54
  55 impl<'tcx> RegionEscape for ty::ClosureSubsts<'tcx> {
  56     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  57         self.func_substs.has_regions_escaping_depth(depth) ||
  58             self.upvar_tys.iter().any(|t| t.has_regions_escaping_depth(depth))
  59     }
  60 }
  61
  62 impl<T:RegionEscape> RegionEscape for Vec<T> {
  63     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  64         self.iter().any(|t| t.has_regions_escaping_depth(depth))
  65     }
  66 }
  67
  68 impl<'tcx> RegionEscape for ty::FnSig<'tcx> {
  69     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  70         self.inputs.has_regions_escaping_depth(depth) ||
  71             self.output.has_regions_escaping_depth(depth)
  72     }
  73 }
  74
  75 impl<'tcx,T:RegionEscape> RegionEscape for VecPerParamSpace<T> {
  76     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  77         self.iter_enumerated().any(|(space, _, t)| {
  78             if space == subst::FnSpace {
  79                 t.has_regions_escaping_depth(depth+1)
  80             } else {
  81                 t.has_regions_escaping_depth(depth)
  82             }
  83         })
  84     }
  85 }
  86
  87 impl<'tcx> RegionEscape for ty::TypeScheme<'tcx> {
  88     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  89         self.ty.has_regions_escaping_depth(depth)
  90     }
  91 }
  92
  93 impl RegionEscape for ty::Region {
  94     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
  95         self.escapes_depth(depth)
  96     }
  97 }
  98
  99 impl<'tcx> RegionEscape for ty::GenericPredicates<'tcx> {
 100     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 101         self.predicates.has_regions_escaping_depth(depth)
 102     }
 103 }
 104
 105 impl<'tcx> RegionEscape for ty::Predicate<'tcx> {
 106     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 107         match *self {
 108             ty::Predicate::Trait(ref data) => data.has_regions_escaping_depth(depth),
 109             ty::Predicate::Equate(ref data) => data.has_regions_escaping_depth(depth),
 110             ty::Predicate::RegionOutlives(ref data) => data.has_regions_escaping_depth(depth),
 111             ty::Predicate::TypeOutlives(ref data) => data.has_regions_escaping_depth(depth),
 112             ty::Predicate::Projection(ref data) => data.has_regions_escaping_depth(depth),
 113             ty::Predicate::WellFormed(ty) => ty.has_regions_escaping_depth(depth),
 114             ty::Predicate::ObjectSafe(_trait_def_id) => false,
 115         }
 116     }
 117 }
 118
 119 impl<'tcx> RegionEscape for TraitRef<'tcx> {
 120     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 121         self.substs.types.iter().any(|t| t.has_regions_escaping_depth(depth)) ||
 122             self.substs.regions.has_regions_escaping_depth(depth)
 123     }
 124 }
 125
 126 impl<'tcx> RegionEscape for subst::RegionSubsts {
 127     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 128         match *self {
 129             subst::ErasedRegions => false,
 130             subst::NonerasedRegions(ref r) => {
 131                 r.iter().any(|t| t.has_regions_escaping_depth(depth))
 132             }
 133         }
 134     }
 135 }
 136
 137 impl<'tcx,T:RegionEscape> RegionEscape for ty::Binder<T> {
 138     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 139         self.0.has_regions_escaping_depth(depth + 1)
 140     }
 141 }
 142
 143 impl<'tcx> RegionEscape for ty::FnOutput<'tcx> {
 144     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 145         match *self {
 146             ty::FnConverging(t) => t.has_regions_escaping_depth(depth),
 147             ty::FnDiverging => false
 148         }
 149     }
 150 }
 151
 152 impl<'tcx> RegionEscape for ty::EquatePredicate<'tcx> {
 153     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 154         self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
 155     }
 156 }
 157
 158 impl<'tcx> RegionEscape for ty::TraitPredicate<'tcx> {
 159     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 160         self.trait_ref.has_regions_escaping_depth(depth)
 161     }
 162 }
 163
 164 impl<T:RegionEscape,U:RegionEscape> RegionEscape for ty::OutlivesPredicate<T,U> {
 165     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 166         self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
 167     }
 168 }
 169
 170 impl<'tcx> RegionEscape for ty::ProjectionPredicate<'tcx> {
 171     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 172         self.projection_ty.has_regions_escaping_depth(depth) ||
 173             self.ty.has_regions_escaping_depth(depth)
 174     }
 175 }
 176
 177 impl<'tcx> RegionEscape for ty::ProjectionTy<'tcx> {
 178     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 179         self.trait_ref.has_regions_escaping_depth(depth)
 180     }
 181 }
 182 impl<'tcx,T:HasTypeFlags> HasTypeFlags for Vec<T> {
 183     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 184         self[..].has_type_flags(flags)
 185     }
 186 }
 187
 188 impl<'tcx,T:HasTypeFlags> HasTypeFlags for [T] {
 189     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 190         self.iter().any(|p| p.has_type_flags(flags))
 191     }
 192 }
 193
 194 impl<'tcx,T:HasTypeFlags> HasTypeFlags for VecPerParamSpace<T> {
 195     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 196         self.iter().any(|p| p.has_type_flags(flags))
 197     }
 198 }
 199
 200 impl HasTypeFlags for abi::Abi {
 201     fn has_type_flags(&self, _flags: TypeFlags) -> bool {
 202         false
 203     }
 204 }
 205
 206 impl HasTypeFlags for hir::Unsafety {
 207     fn has_type_flags(&self, _flags: TypeFlags) -> bool {
 208         false
 209     }
 210 }
 211
 212 impl HasTypeFlags for ty::BuiltinBounds {
 213     fn has_type_flags(&self, _flags: TypeFlags) -> bool {
 214         false
 215     }
 216 }
 217
 218 impl<'tcx> HasTypeFlags for ty::ClosureTy<'tcx> {
 219     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 220         self.sig.has_type_flags(flags)
 221     }
 222 }
 223
 224 impl<'tcx> HasTypeFlags for ty::ClosureUpvar<'tcx> {
 225     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 226         self.ty.has_type_flags(flags)
 227     }
 228 }
 229
 230 impl<'tcx> HasTypeFlags for ty::ExistentialBounds<'tcx> {
 231     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 232         self.projection_bounds.has_type_flags(flags)
 233     }
 234 }
 235
 236 impl<'tcx> HasTypeFlags for ty::InstantiatedPredicates<'tcx> {
 237     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 238         self.predicates.has_type_flags(flags)
 239     }
 240 }
 241
 242 impl<'tcx> HasTypeFlags for ty::Predicate<'tcx> {
 243     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 244         match *self {
 245             ty::Predicate::Trait(ref data) => data.has_type_flags(flags),
 246             ty::Predicate::Equate(ref data) => data.has_type_flags(flags),
 247             ty::Predicate::RegionOutlives(ref data) => data.has_type_flags(flags),
 248             ty::Predicate::TypeOutlives(ref data) => data.has_type_flags(flags),
 249             ty::Predicate::Projection(ref data) => data.has_type_flags(flags),
 250             ty::Predicate::WellFormed(data) => data.has_type_flags(flags),
 251             ty::Predicate::ObjectSafe(_trait_def_id) => false,
 252         }
 253     }
 254 }
 255
 256 impl<'tcx> HasTypeFlags for ty::TraitPredicate<'tcx> {
 257     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 258         self.trait_ref.has_type_flags(flags)
 259     }
 260 }
 261
 262 impl<'tcx> HasTypeFlags for ty::EquatePredicate<'tcx> {
 263     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 264         self.0.has_type_flags(flags) || self.1.has_type_flags(flags)
 265     }
 266 }
 267
 268 impl HasTypeFlags for ty::Region {
 269     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 270         if flags.intersects(TypeFlags::HAS_LOCAL_NAMES) {
 271             // does this represent a region that cannot be named in a global
 272             // way? used in fulfillment caching.
 273             match *self {
 274                 ty::ReStatic | ty::ReEmpty => {}
 275                 _ => return true
 276             }
 277         }
 278         if flags.intersects(TypeFlags::HAS_RE_INFER) {
 279             match *self {
 280                 ty::ReVar(_) | ty::ReSkolemized(..) => { return true }
 281                 _ => {}
 282             }
 283         }
 284         false
 285     }
 286 }
 287
 288 impl<T:HasTypeFlags,U:HasTypeFlags> HasTypeFlags for ty::OutlivesPredicate<T,U> {
 289     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 290         self.0.has_type_flags(flags) || self.1.has_type_flags(flags)
 291     }
 292 }
 293
 294 impl<'tcx> HasTypeFlags for ty::ProjectionPredicate<'tcx> {
 295     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 296         self.projection_ty.has_type_flags(flags) || self.ty.has_type_flags(flags)
 297     }
 298 }
 299
 300 impl<'tcx> HasTypeFlags for ty::ProjectionTy<'tcx> {
 301     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 302         self.trait_ref.has_type_flags(flags)
 303     }
 304 }
 305
 306 impl<'tcx> HasTypeFlags for Ty<'tcx> {
 307     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 308         self.flags.get().intersects(flags)
 309     }
 310 }
 311
 312 impl<'tcx> HasTypeFlags for TypeAndMut<'tcx> {
 313     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 314         self.ty.has_type_flags(flags)
 315     }
 316 }
 317
 318 impl<'tcx> HasTypeFlags for TraitRef<'tcx> {
 319     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 320         self.substs.has_type_flags(flags)
 321     }
 322 }
 323
 324 impl<'tcx> HasTypeFlags for subst::Substs<'tcx> {
 325     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 326         self.types.has_type_flags(flags) || match self.regions {
 327             subst::ErasedRegions => false,
 328             subst::NonerasedRegions(ref r) => r.has_type_flags(flags)
 329         }
 330     }
 331 }
 332
 333 impl<'tcx,T> HasTypeFlags for Option<T>
 334     where T : HasTypeFlags
 335 {
 336     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 337         self.iter().any(|t| t.has_type_flags(flags))
 338     }
 339 }
 340
 341 impl<'tcx,T> HasTypeFlags for Rc<T>
 342     where T : HasTypeFlags
 343 {
 344     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 345         (**self).has_type_flags(flags)
 346     }
 347 }
 348
 349 impl<'tcx,T> HasTypeFlags for Box<T>
 350     where T : HasTypeFlags
 351 {
 352     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 353         (**self).has_type_flags(flags)
 354     }
 355 }
 356
 357 impl<T> HasTypeFlags for ty::Binder<T>
 358     where T : HasTypeFlags
 359 {
 360     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 361         self.0.has_type_flags(flags)
 362     }
 363 }
 364
 365 impl<'tcx> HasTypeFlags for ty::FnOutput<'tcx> {
 366     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 367         match *self {
 368             ty::FnConverging(t) => t.has_type_flags(flags),
 369             ty::FnDiverging => false,
 370         }
 371     }
 372 }
 373
 374 impl<'tcx> HasTypeFlags for ty::FnSig<'tcx> {
 375     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 376         self.inputs.iter().any(|t| t.has_type_flags(flags)) ||
 377             self.output.has_type_flags(flags)
 378     }
 379 }
 380
 381 impl<'tcx> HasTypeFlags for ty::BareFnTy<'tcx> {
 382     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 383         self.sig.has_type_flags(flags)
 384     }
 385 }
 386
 387 impl<'tcx> HasTypeFlags for ty::ClosureSubsts<'tcx> {
 388     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 389         self.func_substs.has_type_flags(flags) ||
 390             self.upvar_tys.iter().any(|t| t.has_type_flags(flags))
 391     }
 392 }
 393
 394 ///////////////////////////////////////////////////////////////////////////
 395 // Lift implementations
 396
 397 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>> Lift<'tcx> for (A, B) {
 398     type Lifted = (A::Lifted, B::Lifted);
 399     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 400         tcx.lift(&self.0).and_then(|a| tcx.lift(&self.1).map(|b| (a, b)))
 401     }
 402 }
 403
 404 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for [T] {
 405     type Lifted = Vec<T::Lifted>;
 406     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 407         let mut result = Vec::with_capacity(self.len());
 408         for x in self {
 409             if let Some(value) = tcx.lift(x) {
 410                 result.push(value);
 411             } else {
 412                 return None;
 413             }
 414         }
 415         Some(result)
 416     }
 417 }
 418
 419 impl<'tcx> Lift<'tcx> for ty::Region {
 420     type Lifted = Self;
 421     fn lift_to_tcx(&self, _: &ty::ctxt<'tcx>) -> Option<ty::Region> {
 422         Some(*self)
 423     }
 424 }
 425
 426 impl<'a, 'tcx> Lift<'tcx> for TraitRef<'a> {
 427     type Lifted = TraitRef<'tcx>;
 428     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<TraitRef<'tcx>> {
 429         tcx.lift(&self.substs).map(|substs| TraitRef {
 430             def_id: self.def_id,
 431             substs: substs
 432         })
 433     }
 434 }
 435
 436 impl<'a, 'tcx> Lift<'tcx> for ty::TraitPredicate<'a> {
 437     type Lifted = ty::TraitPredicate<'tcx>;
 438     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<ty::TraitPredicate<'tcx>> {
 439         tcx.lift(&self.trait_ref).map(|trait_ref| ty::TraitPredicate {
 440             trait_ref: trait_ref
 441         })
 442     }
 443 }
 444
 445 impl<'a, 'tcx> Lift<'tcx> for ty::EquatePredicate<'a> {
 446     type Lifted = ty::EquatePredicate<'tcx>;
 447     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<ty::EquatePredicate<'tcx>> {
 448         tcx.lift(&(self.0, self.1)).map(|(a, b)| ty::EquatePredicate(a, b))
 449     }
 450 }
 451
 452 impl<'tcx, A: Copy+Lift<'tcx>, B: Copy+Lift<'tcx>> Lift<'tcx> for ty::OutlivesPredicate<A, B> {
 453     type Lifted = ty::OutlivesPredicate<A::Lifted, B::Lifted>;
 454     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 455         tcx.lift(&(self.0, self.1)).map(|(a, b)| ty::OutlivesPredicate(a, b))
 456     }
 457 }
 458
 459 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
 460     type Lifted = ty::ProjectionPredicate<'tcx>;
 461     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<ty::ProjectionPredicate<'tcx>> {
 462         tcx.lift(&(self.projection_ty.trait_ref, self.ty)).map(|(trait_ref, ty)| {
 463             ty::ProjectionPredicate {
 464                 projection_ty: ty::ProjectionTy {
 465                     trait_ref: trait_ref,
 466                     item_name: self.projection_ty.item_name
 467                 },
 468                 ty: ty
 469             }
 470         })
 471     }
 472 }
 473
 474 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::Binder<T> {
 475     type Lifted = ty::Binder<T::Lifted>;
 476     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 477         tcx.lift(&self.0).map(|x| ty::Binder(x))
 478     }
 479 }
 480
 481 ///////////////////////////////////////////////////////////////////////////
 482 // TypeFoldable implementations.
 483 //
 484 // Ideally, each type should invoke `folder.fold_foo(self)` and
 485 // nothing else. In some cases, though, we haven't gotten around to
 486 // adding methods on the `folder` yet, and thus the folding is
 487 // hard-coded here. This is less-flexible, because folders cannot
 488 // override the behavior, but there are a lot of random types and one
 489 // can easily refactor the folding into the TypeFolder trait as
 490 // needed.
 491
 492 macro_rules! CopyImpls {
 493     ($($ty:ty),+) => {
 494         $(
 495             impl<'tcx> TypeFoldable<'tcx> for $ty {
 496                 fn fold_with<F:TypeFolder<'tcx>>(&self, _: &mut F) -> $ty {
 497                     *self
 498                 }
 499             }
 500         )+
 501     }
 502 }
 503
 504 CopyImpls! { (), hir::Unsafety, abi::Abi }
 505
 506 impl<'tcx, T:TypeFoldable<'tcx>, U:TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
 507     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> (T, U) {
 508         (self.0.fold_with(folder), self.1.fold_with(folder))
 509     }
 510 }
 511
 512 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Option<T> {
 513     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Option<T> {
 514         self.as_ref().map(|t| t.fold_with(folder))
 515     }
 516 }
 517
 518 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Rc<T> {
 519     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Rc<T> {
 520         Rc::new((**self).fold_with(folder))
 521     }
 522 }
 523
 524 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<T> {
 525     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Box<T> {
 526         let content: T = (**self).fold_with(folder);
 527         box content
 528     }
 529 }
 530
 531 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
 532     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Vec<T> {
 533         self.iter().map(|t| t.fold_with(folder)).collect()
 534     }
 535 }
 536
 537 impl<'tcx, T:TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
 538     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Binder<T> {
 539         folder.fold_binder(self)
 540     }
 541 }
 542
 543 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for OwnedSlice<T> {
 544     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> OwnedSlice<T> {
 545         self.iter().map(|t| t.fold_with(folder)).collect()
 546     }
 547 }
 548
 549 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for VecPerParamSpace<T> {
 550     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> VecPerParamSpace<T> {
 551
 552         // Things in the Fn space take place under an additional level
 553         // of region binding relative to the other spaces. This is
 554         // because those entries are attached to a method, and methods
 555         // always introduce a level of region binding.
 556
 557         let result = self.map_enumerated(|(space, index, elem)| {
 558             if space == subst::FnSpace && index == 0 {
 559                 // enter new level when/if we reach the first thing in fn space
 560                 folder.enter_region_binder();
 561             }
 562             elem.fold_with(folder)
 563         });
 564         if result.len(subst::FnSpace) > 0 {
 565             // if there was anything in fn space, exit the region binding level
 566             folder.exit_region_binder();
 567         }
 568         result
 569     }
 570 }
 571
 572 impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
 573     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Ty<'tcx> {
 574         folder.fold_ty(*self)
 575     }
 576 }
 577
 578 impl<'tcx> TypeFoldable<'tcx> for ty::BareFnTy<'tcx> {
 579     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::BareFnTy<'tcx> {
 580         folder.fold_bare_fn_ty(self)
 581     }
 582 }
 583
 584 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureTy<'tcx> {
 585     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureTy<'tcx> {
 586         folder.fold_closure_ty(self)
 587     }
 588 }
 589
 590 impl<'tcx> TypeFoldable<'tcx> for ty::TypeAndMut<'tcx> {
 591     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TypeAndMut<'tcx> {
 592         folder.fold_mt(self)
 593     }
 594 }
 595
 596 impl<'tcx> TypeFoldable<'tcx> for ty::FnOutput<'tcx> {
 597     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnOutput<'tcx> {
 598         folder.fold_output(self)
 599     }
 600 }
 601
 602 impl<'tcx> TypeFoldable<'tcx> for ty::FnSig<'tcx> {
 603     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnSig<'tcx> {
 604         folder.fold_fn_sig(self)
 605     }
 606 }
 607
 608 impl<'tcx> TypeFoldable<'tcx> for ty::TraitRef<'tcx> {
 609     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitRef<'tcx> {
 610         folder.fold_trait_ref(self)
 611     }
 612 }
 613
 614 impl<'tcx> TypeFoldable<'tcx> for ty::Region {
 615     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Region {
 616         folder.fold_region(*self)
 617     }
 618 }
 619
 620 impl<'tcx> TypeFoldable<'tcx> for subst::Substs<'tcx> {
 621     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> subst::Substs<'tcx> {
 622         folder.fold_substs(self)
 623     }
 624 }
 625
 626 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureSubsts<'tcx> {
 627     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureSubsts<'tcx> {
 628         let func_substs = self.func_substs.fold_with(folder);
 629         ty::ClosureSubsts {
 630             func_substs: folder.tcx().mk_substs(func_substs),
 631             upvar_tys: self.upvar_tys.fold_with(folder),
 632         }
 633     }
 634 }
 635
 636 impl<'tcx> TypeFoldable<'tcx> for ty::ItemSubsts<'tcx> {
 637     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ItemSubsts<'tcx> {
 638         ty::ItemSubsts {
 639             substs: self.substs.fold_with(folder),
 640         }
 641     }
 642 }
 643
 644 impl<'tcx> TypeFoldable<'tcx> for ty::adjustment::AutoRef<'tcx> {
 645     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::adjustment::AutoRef<'tcx> {
 646         folder.fold_autoref(self)
 647     }
 648 }
 649
 650 impl<'tcx> TypeFoldable<'tcx> for ty::BuiltinBounds {
 651     fn fold_with<F: TypeFolder<'tcx>>(&self, _folder: &mut F) -> ty::BuiltinBounds {
 652         *self
 653     }
 654 }
 655
 656 impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialBounds<'tcx> {
 657     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ExistentialBounds<'tcx> {
 658         folder.fold_existential_bounds(self)
 659     }
 660 }
 661
 662 impl<'tcx> TypeFoldable<'tcx> for ty::TypeParameterDef<'tcx> {
 663     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TypeParameterDef<'tcx> {
 664         ty::TypeParameterDef {
 665             name: self.name,
 666             def_id: self.def_id,
 667             space: self.space,
 668             index: self.index,
 669             default: self.default.fold_with(folder),
 670             default_def_id: self.default_def_id,
 671             object_lifetime_default: self.object_lifetime_default.fold_with(folder),
 672         }
 673     }
 674 }
 675
 676 impl<'tcx> TypeFoldable<'tcx> for ty::ObjectLifetimeDefault {
 677     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ObjectLifetimeDefault {
 678         match *self {
 679             ty::ObjectLifetimeDefault::Ambiguous =>
 680                 ty::ObjectLifetimeDefault::Ambiguous,
 681
 682             ty::ObjectLifetimeDefault::BaseDefault =>
 683                 ty::ObjectLifetimeDefault::BaseDefault,
 684
 685             ty::ObjectLifetimeDefault::Specific(r) =>
 686                 ty::ObjectLifetimeDefault::Specific(r.fold_with(folder)),
 687         }
 688     }
 689 }
 690
 691 impl<'tcx> TypeFoldable<'tcx> for ty::RegionParameterDef {
 692     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::RegionParameterDef {
 693         ty::RegionParameterDef {
 694             name: self.name,
 695             def_id: self.def_id,
 696             space: self.space,
 697             index: self.index,
 698             bounds: self.bounds.fold_with(folder)
 699         }
 700     }
 701 }
 702
 703 impl<'tcx> TypeFoldable<'tcx> for ty::Generics<'tcx> {
 704     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Generics<'tcx> {
 705         ty::Generics {
 706             types: self.types.fold_with(folder),
 707             regions: self.regions.fold_with(folder),
 708         }
 709     }
 710 }
 711
 712 impl<'tcx> TypeFoldable<'tcx> for ty::GenericPredicates<'tcx> {
 713     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::GenericPredicates<'tcx> {
 714         ty::GenericPredicates {
 715             predicates: self.predicates.fold_with(folder),
 716         }
 717     }
 718 }
 719
 720 impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
 721     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Predicate<'tcx> {
 722         match *self {
 723             ty::Predicate::Trait(ref a) =>
 724                 ty::Predicate::Trait(a.fold_with(folder)),
 725             ty::Predicate::Equate(ref binder) =>
 726                 ty::Predicate::Equate(binder.fold_with(folder)),
 727             ty::Predicate::RegionOutlives(ref binder) =>
 728                 ty::Predicate::RegionOutlives(binder.fold_with(folder)),
 729             ty::Predicate::TypeOutlives(ref binder) =>
 730                 ty::Predicate::TypeOutlives(binder.fold_with(folder)),
 731             ty::Predicate::Projection(ref binder) =>
 732                 ty::Predicate::Projection(binder.fold_with(folder)),
 733             ty::Predicate::WellFormed(data) =>
 734                 ty::Predicate::WellFormed(data.fold_with(folder)),
 735             ty::Predicate::ObjectSafe(trait_def_id) =>
 736                 ty::Predicate::ObjectSafe(trait_def_id),
 737         }
 738     }
 739 }
 740
 741 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionPredicate<'tcx> {
 742     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ProjectionPredicate<'tcx> {
 743         ty::ProjectionPredicate {
 744             projection_ty: self.projection_ty.fold_with(folder),
 745             ty: self.ty.fold_with(folder),
 746         }
 747     }
 748 }
 749
 750 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionTy<'tcx> {
 751     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ProjectionTy<'tcx> {
 752         ty::ProjectionTy {
 753             trait_ref: self.trait_ref.fold_with(folder),
 754             item_name: self.item_name,
 755         }
 756     }
 757 }
 758
 759 impl<'tcx> TypeFoldable<'tcx> for ty::InstantiatedPredicates<'tcx> {
 760     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::InstantiatedPredicates<'tcx> {
 761         ty::InstantiatedPredicates {
 762             predicates: self.predicates.fold_with(folder),
 763         }
 764     }
 765 }
 766
 767 impl<'tcx> TypeFoldable<'tcx> for ty::EquatePredicate<'tcx> {
 768     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::EquatePredicate<'tcx> {
 769         ty::EquatePredicate(self.0.fold_with(folder),
 770                             self.1.fold_with(folder))
 771     }
 772 }
 773
 774 impl<'tcx> TypeFoldable<'tcx> for ty::TraitPredicate<'tcx> {
 775     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitPredicate<'tcx> {
 776         ty::TraitPredicate {
 777             trait_ref: self.trait_ref.fold_with(folder)
 778         }
 779     }
 780 }
 781
 782 impl<'tcx,T,U> TypeFoldable<'tcx> for ty::OutlivesPredicate<T,U>
 783     where T : TypeFoldable<'tcx>,
 784           U : TypeFoldable<'tcx>,
 785 {
 786     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::OutlivesPredicate<T,U> {
 787         ty::OutlivesPredicate(self.0.fold_with(folder),
 788                               self.1.fold_with(folder))
 789     }
 790 }
 791
 792 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureUpvar<'tcx> {
 793     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureUpvar<'tcx> {
 794         ty::ClosureUpvar {
 795             def: self.def,
 796             span: self.span,
 797             ty: self.ty.fold_with(folder),
 798         }
 799     }
 800 }
 801
 802 impl<'a, 'tcx> TypeFoldable<'tcx> for ty::ParameterEnvironment<'a, 'tcx> where 'tcx: 'a {
 803     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ParameterEnvironment<'a, 'tcx> {
 804         ty::ParameterEnvironment {
 805             tcx: self.tcx,
 806             free_substs: self.free_substs.fold_with(folder),
 807             implicit_region_bound: self.implicit_region_bound.fold_with(folder),
 808             caller_bounds: self.caller_bounds.fold_with(folder),
 809             selection_cache: traits::SelectionCache::new(),
 810             free_id: self.free_id,
 811         }
 812     }
 813 }