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,P:RegionEscape> RegionEscape for traits::Obligation<'tcx,P> {
 120     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 121         self.predicate.has_regions_escaping_depth(depth)
 122     }
 123 }
 124
 125 impl<'tcx> RegionEscape for TraitRef<'tcx> {
 126     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 127         self.substs.types.iter().any(|t| t.has_regions_escaping_depth(depth)) ||
 128             self.substs.regions.has_regions_escaping_depth(depth)
 129     }
 130 }
 131
 132 impl<'tcx> RegionEscape for subst::RegionSubsts {
 133     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 134         match *self {
 135             subst::ErasedRegions => false,
 136             subst::NonerasedRegions(ref r) => {
 137                 r.iter().any(|t| t.has_regions_escaping_depth(depth))
 138             }
 139         }
 140     }
 141 }
 142
 143 impl<'tcx,T:RegionEscape> RegionEscape for ty::Binder<T> {
 144     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 145         self.0.has_regions_escaping_depth(depth + 1)
 146     }
 147 }
 148
 149 impl<'tcx> RegionEscape for ty::FnOutput<'tcx> {
 150     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 151         match *self {
 152             ty::FnConverging(t) => t.has_regions_escaping_depth(depth),
 153             ty::FnDiverging => false
 154         }
 155     }
 156 }
 157
 158 impl<'tcx> RegionEscape for ty::EquatePredicate<'tcx> {
 159     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 160         self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
 161     }
 162 }
 163
 164 impl<'tcx> RegionEscape for ty::TraitPredicate<'tcx> {
 165     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 166         self.trait_ref.has_regions_escaping_depth(depth)
 167     }
 168 }
 169
 170 impl<T:RegionEscape,U:RegionEscape> RegionEscape for ty::OutlivesPredicate<T,U> {
 171     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 172         self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
 173     }
 174 }
 175
 176 impl<'tcx> RegionEscape for ty::ProjectionPredicate<'tcx> {
 177     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 178         self.projection_ty.has_regions_escaping_depth(depth) ||
 179             self.ty.has_regions_escaping_depth(depth)
 180     }
 181 }
 182
 183 impl<'tcx> RegionEscape for ty::ProjectionTy<'tcx> {
 184     fn has_regions_escaping_depth(&self, depth: u32) -> bool {
 185         self.trait_ref.has_regions_escaping_depth(depth)
 186     }
 187 }
 188 impl<'tcx,T:HasTypeFlags> HasTypeFlags for Vec<T> {
 189     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 190         self[..].has_type_flags(flags)
 191     }
 192 }
 193
 194 impl<'tcx,T:HasTypeFlags> HasTypeFlags for [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<'tcx,T:HasTypeFlags> HasTypeFlags for VecPerParamSpace<T> {
 201     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 202         self.iter().any(|p| p.has_type_flags(flags))
 203     }
 204 }
 205
 206 impl HasTypeFlags for abi::Abi {
 207     fn has_type_flags(&self, _flags: TypeFlags) -> bool {
 208         false
 209     }
 210 }
 211
 212 impl HasTypeFlags for hir::Unsafety {
 213     fn has_type_flags(&self, _flags: TypeFlags) -> bool {
 214         false
 215     }
 216 }
 217
 218 impl HasTypeFlags for ty::BuiltinBounds {
 219     fn has_type_flags(&self, _flags: TypeFlags) -> bool {
 220         false
 221     }
 222 }
 223
 224 impl<'tcx> HasTypeFlags for ty::ClosureTy<'tcx> {
 225     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 226         self.sig.has_type_flags(flags)
 227     }
 228 }
 229
 230 impl<'tcx> HasTypeFlags for ty::ClosureUpvar<'tcx> {
 231     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 232         self.ty.has_type_flags(flags)
 233     }
 234 }
 235
 236 impl<'tcx> HasTypeFlags for ty::ExistentialBounds<'tcx> {
 237     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 238         self.projection_bounds.has_type_flags(flags)
 239     }
 240 }
 241
 242 impl<'tcx> HasTypeFlags for ty::InstantiatedPredicates<'tcx> {
 243     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 244         self.predicates.has_type_flags(flags)
 245     }
 246 }
 247
 248 impl<'tcx> HasTypeFlags for ty::Predicate<'tcx> {
 249     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 250         match *self {
 251             ty::Predicate::Trait(ref data) => data.has_type_flags(flags),
 252             ty::Predicate::Equate(ref data) => data.has_type_flags(flags),
 253             ty::Predicate::RegionOutlives(ref data) => data.has_type_flags(flags),
 254             ty::Predicate::TypeOutlives(ref data) => data.has_type_flags(flags),
 255             ty::Predicate::Projection(ref data) => data.has_type_flags(flags),
 256             ty::Predicate::WellFormed(data) => data.has_type_flags(flags),
 257             ty::Predicate::ObjectSafe(_trait_def_id) => false,
 258         }
 259     }
 260 }
 261
 262 impl<'tcx> HasTypeFlags for ty::TraitPredicate<'tcx> {
 263     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 264         self.trait_ref.has_type_flags(flags)
 265     }
 266 }
 267
 268 impl<'tcx> HasTypeFlags for ty::EquatePredicate<'tcx> {
 269     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 270         self.0.has_type_flags(flags) || self.1.has_type_flags(flags)
 271     }
 272 }
 273
 274 impl HasTypeFlags for ty::Region {
 275     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 276         if flags.intersects(TypeFlags::HAS_LOCAL_NAMES) {
 277             // does this represent a region that cannot be named in a global
 278             // way? used in fulfillment caching.
 279             match *self {
 280                 ty::ReStatic | ty::ReEmpty => {}
 281                 _ => return true
 282             }
 283         }
 284         if flags.intersects(TypeFlags::HAS_RE_INFER) {
 285             match *self {
 286                 ty::ReVar(_) | ty::ReSkolemized(..) => { return true }
 287                 _ => {}
 288             }
 289         }
 290         false
 291     }
 292 }
 293
 294 impl<T:HasTypeFlags,U:HasTypeFlags> HasTypeFlags for ty::OutlivesPredicate<T,U> {
 295     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 296         self.0.has_type_flags(flags) || self.1.has_type_flags(flags)
 297     }
 298 }
 299
 300 impl<'tcx> HasTypeFlags for ty::ProjectionPredicate<'tcx> {
 301     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 302         self.projection_ty.has_type_flags(flags) || self.ty.has_type_flags(flags)
 303     }
 304 }
 305
 306 impl<'tcx> HasTypeFlags for ty::ProjectionTy<'tcx> {
 307     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 308         self.trait_ref.has_type_flags(flags)
 309     }
 310 }
 311
 312 impl<'tcx> HasTypeFlags for Ty<'tcx> {
 313     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 314         self.flags.get().intersects(flags)
 315     }
 316 }
 317
 318 impl<'tcx> HasTypeFlags for TypeAndMut<'tcx> {
 319     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 320         self.ty.has_type_flags(flags)
 321     }
 322 }
 323
 324 impl<'tcx> HasTypeFlags for TraitRef<'tcx> {
 325     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 326         self.substs.has_type_flags(flags)
 327     }
 328 }
 329
 330 impl<'tcx> HasTypeFlags for subst::Substs<'tcx> {
 331     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 332         self.types.has_type_flags(flags) || match self.regions {
 333             subst::ErasedRegions => false,
 334             subst::NonerasedRegions(ref r) => r.has_type_flags(flags)
 335         }
 336     }
 337 }
 338
 339 impl<'tcx,T> HasTypeFlags for Option<T>
 340     where T : HasTypeFlags
 341 {
 342     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 343         self.iter().any(|t| t.has_type_flags(flags))
 344     }
 345 }
 346
 347 impl<'tcx,T> HasTypeFlags for Rc<T>
 348     where T : HasTypeFlags
 349 {
 350     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 351         (**self).has_type_flags(flags)
 352     }
 353 }
 354
 355 impl<'tcx,T> HasTypeFlags for Box<T>
 356     where T : HasTypeFlags
 357 {
 358     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 359         (**self).has_type_flags(flags)
 360     }
 361 }
 362
 363 impl<T> HasTypeFlags for ty::Binder<T>
 364     where T : HasTypeFlags
 365 {
 366     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 367         self.0.has_type_flags(flags)
 368     }
 369 }
 370
 371 impl<'tcx> HasTypeFlags for ty::FnOutput<'tcx> {
 372     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 373         match *self {
 374             ty::FnConverging(t) => t.has_type_flags(flags),
 375             ty::FnDiverging => false,
 376         }
 377     }
 378 }
 379
 380 impl<'tcx> HasTypeFlags for ty::FnSig<'tcx> {
 381     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 382         self.inputs.iter().any(|t| t.has_type_flags(flags)) ||
 383             self.output.has_type_flags(flags)
 384     }
 385 }
 386
 387 impl<'tcx> HasTypeFlags for ty::BareFnTy<'tcx> {
 388     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 389         self.sig.has_type_flags(flags)
 390     }
 391 }
 392
 393 impl<'tcx> HasTypeFlags for ty::ClosureSubsts<'tcx> {
 394     fn has_type_flags(&self, flags: TypeFlags) -> bool {
 395         self.func_substs.has_type_flags(flags) ||
 396             self.upvar_tys.iter().any(|t| t.has_type_flags(flags))
 397     }
 398 }
 399
 400 ///////////////////////////////////////////////////////////////////////////
 401 // Lift implementations
 402
 403 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>> Lift<'tcx> for (A, B) {
 404     type Lifted = (A::Lifted, B::Lifted);
 405     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 406         tcx.lift(&self.0).and_then(|a| tcx.lift(&self.1).map(|b| (a, b)))
 407     }
 408 }
 409
 410 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for [T] {
 411     type Lifted = Vec<T::Lifted>;
 412     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 413         let mut result = Vec::with_capacity(self.len());
 414         for x in self {
 415             if let Some(value) = tcx.lift(x) {
 416                 result.push(value);
 417             } else {
 418                 return None;
 419             }
 420         }
 421         Some(result)
 422     }
 423 }
 424
 425 impl<'tcx> Lift<'tcx> for ty::Region {
 426     type Lifted = Self;
 427     fn lift_to_tcx(&self, _: &ty::ctxt<'tcx>) -> Option<ty::Region> {
 428         Some(*self)
 429     }
 430 }
 431
 432 impl<'a, 'tcx> Lift<'tcx> for TraitRef<'a> {
 433     type Lifted = TraitRef<'tcx>;
 434     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<TraitRef<'tcx>> {
 435         tcx.lift(&self.substs).map(|substs| TraitRef {
 436             def_id: self.def_id,
 437             substs: substs
 438         })
 439     }
 440 }
 441
 442 impl<'a, 'tcx> Lift<'tcx> for ty::TraitPredicate<'a> {
 443     type Lifted = ty::TraitPredicate<'tcx>;
 444     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<ty::TraitPredicate<'tcx>> {
 445         tcx.lift(&self.trait_ref).map(|trait_ref| ty::TraitPredicate {
 446             trait_ref: trait_ref
 447         })
 448     }
 449 }
 450
 451 impl<'a, 'tcx> Lift<'tcx> for ty::EquatePredicate<'a> {
 452     type Lifted = ty::EquatePredicate<'tcx>;
 453     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<ty::EquatePredicate<'tcx>> {
 454         tcx.lift(&(self.0, self.1)).map(|(a, b)| ty::EquatePredicate(a, b))
 455     }
 456 }
 457
 458 impl<'tcx, A: Copy+Lift<'tcx>, B: Copy+Lift<'tcx>> Lift<'tcx> for ty::OutlivesPredicate<A, B> {
 459     type Lifted = ty::OutlivesPredicate<A::Lifted, B::Lifted>;
 460     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 461         tcx.lift(&(self.0, self.1)).map(|(a, b)| ty::OutlivesPredicate(a, b))
 462     }
 463 }
 464
 465 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
 466     type Lifted = ty::ProjectionPredicate<'tcx>;
 467     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<ty::ProjectionPredicate<'tcx>> {
 468         tcx.lift(&(self.projection_ty.trait_ref, self.ty)).map(|(trait_ref, ty)| {
 469             ty::ProjectionPredicate {
 470                 projection_ty: ty::ProjectionTy {
 471                     trait_ref: trait_ref,
 472                     item_name: self.projection_ty.item_name
 473                 },
 474                 ty: ty
 475             }
 476         })
 477     }
 478 }
 479
 480 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::Binder<T> {
 481     type Lifted = ty::Binder<T::Lifted>;
 482     fn lift_to_tcx(&self, tcx: &ty::ctxt<'tcx>) -> Option<Self::Lifted> {
 483         tcx.lift(&self.0).map(|x| ty::Binder(x))
 484     }
 485 }
 486
 487 ///////////////////////////////////////////////////////////////////////////
 488 // TypeFoldable implementations.
 489 //
 490 // Ideally, each type should invoke `folder.fold_foo(self)` and
 491 // nothing else. In some cases, though, we haven't gotten around to
 492 // adding methods on the `folder` yet, and thus the folding is
 493 // hard-coded here. This is less-flexible, because folders cannot
 494 // override the behavior, but there are a lot of random types and one
 495 // can easily refactor the folding into the TypeFolder trait as
 496 // needed.
 497
 498 macro_rules! CopyImpls {
 499     ($($ty:ty),+) => {
 500         $(
 501             impl<'tcx> TypeFoldable<'tcx> for $ty {
 502                 fn fold_with<F:TypeFolder<'tcx>>(&self, _: &mut F) -> $ty {
 503                     *self
 504                 }
 505             }
 506         )+
 507     }
 508 }
 509
 510 CopyImpls! { (), hir::Unsafety, abi::Abi }
 511
 512 impl<'tcx, T:TypeFoldable<'tcx>, U:TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
 513     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> (T, U) {
 514         (self.0.fold_with(folder), self.1.fold_with(folder))
 515     }
 516 }
 517
 518 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Option<T> {
 519     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Option<T> {
 520         self.as_ref().map(|t| t.fold_with(folder))
 521     }
 522 }
 523
 524 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Rc<T> {
 525     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Rc<T> {
 526         Rc::new((**self).fold_with(folder))
 527     }
 528 }
 529
 530 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<T> {
 531     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Box<T> {
 532         let content: T = (**self).fold_with(folder);
 533         box content
 534     }
 535 }
 536
 537 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
 538     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Vec<T> {
 539         self.iter().map(|t| t.fold_with(folder)).collect()
 540     }
 541 }
 542
 543 impl<'tcx, T:TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
 544     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Binder<T> {
 545         folder.fold_binder(self)
 546     }
 547 }
 548
 549 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for OwnedSlice<T> {
 550     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> OwnedSlice<T> {
 551         self.iter().map(|t| t.fold_with(folder)).collect()
 552     }
 553 }
 554
 555 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for VecPerParamSpace<T> {
 556     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> VecPerParamSpace<T> {
 557
 558         // Things in the Fn space take place under an additional level
 559         // of region binding relative to the other spaces. This is
 560         // because those entries are attached to a method, and methods
 561         // always introduce a level of region binding.
 562
 563         let result = self.map_enumerated(|(space, index, elem)| {
 564             if space == subst::FnSpace && index == 0 {
 565                 // enter new level when/if we reach the first thing in fn space
 566                 folder.enter_region_binder();
 567             }
 568             elem.fold_with(folder)
 569         });
 570         if result.len(subst::FnSpace) > 0 {
 571             // if there was anything in fn space, exit the region binding level
 572             folder.exit_region_binder();
 573         }
 574         result
 575     }
 576 }
 577
 578 impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
 579     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Ty<'tcx> {
 580         folder.fold_ty(*self)
 581     }
 582 }
 583
 584 impl<'tcx> TypeFoldable<'tcx> for ty::BareFnTy<'tcx> {
 585     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::BareFnTy<'tcx> {
 586         folder.fold_bare_fn_ty(self)
 587     }
 588 }
 589
 590 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureTy<'tcx> {
 591     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureTy<'tcx> {
 592         folder.fold_closure_ty(self)
 593     }
 594 }
 595
 596 impl<'tcx> TypeFoldable<'tcx> for ty::TypeAndMut<'tcx> {
 597     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TypeAndMut<'tcx> {
 598         folder.fold_mt(self)
 599     }
 600 }
 601
 602 impl<'tcx> TypeFoldable<'tcx> for ty::FnOutput<'tcx> {
 603     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnOutput<'tcx> {
 604         folder.fold_output(self)
 605     }
 606 }
 607
 608 impl<'tcx> TypeFoldable<'tcx> for ty::FnSig<'tcx> {
 609     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::FnSig<'tcx> {
 610         folder.fold_fn_sig(self)
 611     }
 612 }
 613
 614 impl<'tcx> TypeFoldable<'tcx> for ty::TraitRef<'tcx> {
 615     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitRef<'tcx> {
 616         folder.fold_trait_ref(self)
 617     }
 618 }
 619
 620 impl<'tcx> TypeFoldable<'tcx> for ty::Region {
 621     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Region {
 622         folder.fold_region(*self)
 623     }
 624 }
 625
 626 impl<'tcx> TypeFoldable<'tcx> for subst::Substs<'tcx> {
 627     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> subst::Substs<'tcx> {
 628         folder.fold_substs(self)
 629     }
 630 }
 631
 632 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureSubsts<'tcx> {
 633     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureSubsts<'tcx> {
 634         let func_substs = self.func_substs.fold_with(folder);
 635         ty::ClosureSubsts {
 636             func_substs: folder.tcx().mk_substs(func_substs),
 637             upvar_tys: self.upvar_tys.fold_with(folder),
 638         }
 639     }
 640 }
 641
 642 impl<'tcx> TypeFoldable<'tcx> for ty::ItemSubsts<'tcx> {
 643     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ItemSubsts<'tcx> {
 644         ty::ItemSubsts {
 645             substs: self.substs.fold_with(folder),
 646         }
 647     }
 648 }
 649
 650 impl<'tcx> TypeFoldable<'tcx> for ty::AutoRef<'tcx> {
 651     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::AutoRef<'tcx> {
 652         folder.fold_autoref(self)
 653     }
 654 }
 655
 656 impl<'tcx> TypeFoldable<'tcx> for ty::BuiltinBounds {
 657     fn fold_with<F: TypeFolder<'tcx>>(&self, _folder: &mut F) -> ty::BuiltinBounds {
 658         *self
 659     }
 660 }
 661
 662 impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialBounds<'tcx> {
 663     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ExistentialBounds<'tcx> {
 664         folder.fold_existential_bounds(self)
 665     }
 666 }
 667
 668 impl<'tcx> TypeFoldable<'tcx> for ty::TypeParameterDef<'tcx> {
 669     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TypeParameterDef<'tcx> {
 670         ty::TypeParameterDef {
 671             name: self.name,
 672             def_id: self.def_id,
 673             space: self.space,
 674             index: self.index,
 675             default: self.default.fold_with(folder),
 676             default_def_id: self.default_def_id,
 677             object_lifetime_default: self.object_lifetime_default.fold_with(folder),
 678         }
 679     }
 680 }
 681
 682 impl<'tcx> TypeFoldable<'tcx> for ty::ObjectLifetimeDefault {
 683     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ObjectLifetimeDefault {
 684         match *self {
 685             ty::ObjectLifetimeDefault::Ambiguous =>
 686                 ty::ObjectLifetimeDefault::Ambiguous,
 687
 688             ty::ObjectLifetimeDefault::BaseDefault =>
 689                 ty::ObjectLifetimeDefault::BaseDefault,
 690
 691             ty::ObjectLifetimeDefault::Specific(r) =>
 692                 ty::ObjectLifetimeDefault::Specific(r.fold_with(folder)),
 693         }
 694     }
 695 }
 696
 697 impl<'tcx> TypeFoldable<'tcx> for ty::RegionParameterDef {
 698     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::RegionParameterDef {
 699         ty::RegionParameterDef {
 700             name: self.name,
 701             def_id: self.def_id,
 702             space: self.space,
 703             index: self.index,
 704             bounds: self.bounds.fold_with(folder)
 705         }
 706     }
 707 }
 708
 709 impl<'tcx> TypeFoldable<'tcx> for ty::Generics<'tcx> {
 710     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Generics<'tcx> {
 711         ty::Generics {
 712             types: self.types.fold_with(folder),
 713             regions: self.regions.fold_with(folder),
 714         }
 715     }
 716 }
 717
 718 impl<'tcx> TypeFoldable<'tcx> for ty::GenericPredicates<'tcx> {
 719     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::GenericPredicates<'tcx> {
 720         ty::GenericPredicates {
 721             predicates: self.predicates.fold_with(folder),
 722         }
 723     }
 724 }
 725
 726 impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
 727     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::Predicate<'tcx> {
 728         match *self {
 729             ty::Predicate::Trait(ref a) =>
 730                 ty::Predicate::Trait(a.fold_with(folder)),
 731             ty::Predicate::Equate(ref binder) =>
 732                 ty::Predicate::Equate(binder.fold_with(folder)),
 733             ty::Predicate::RegionOutlives(ref binder) =>
 734                 ty::Predicate::RegionOutlives(binder.fold_with(folder)),
 735             ty::Predicate::TypeOutlives(ref binder) =>
 736                 ty::Predicate::TypeOutlives(binder.fold_with(folder)),
 737             ty::Predicate::Projection(ref binder) =>
 738                 ty::Predicate::Projection(binder.fold_with(folder)),
 739             ty::Predicate::WellFormed(data) =>
 740                 ty::Predicate::WellFormed(data.fold_with(folder)),
 741             ty::Predicate::ObjectSafe(trait_def_id) =>
 742                 ty::Predicate::ObjectSafe(trait_def_id),
 743         }
 744     }
 745 }
 746
 747 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionPredicate<'tcx> {
 748     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ProjectionPredicate<'tcx> {
 749         ty::ProjectionPredicate {
 750             projection_ty: self.projection_ty.fold_with(folder),
 751             ty: self.ty.fold_with(folder),
 752         }
 753     }
 754 }
 755
 756 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionTy<'tcx> {
 757     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ProjectionTy<'tcx> {
 758         ty::ProjectionTy {
 759             trait_ref: self.trait_ref.fold_with(folder),
 760             item_name: self.item_name,
 761         }
 762     }
 763 }
 764
 765 impl<'tcx> TypeFoldable<'tcx> for ty::InstantiatedPredicates<'tcx> {
 766     fn fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::InstantiatedPredicates<'tcx> {
 767         ty::InstantiatedPredicates {
 768             predicates: self.predicates.fold_with(folder),
 769         }
 770     }
 771 }
 772
 773 impl<'tcx,O> TypeFoldable<'tcx> for traits::Obligation<'tcx,O>
 774     where O : TypeFoldable<'tcx>
 775 {
 776     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Obligation<'tcx, O> {
 777         traits::Obligation {
 778             cause: self.cause.clone(),
 779             recursion_depth: self.recursion_depth,
 780             predicate: self.predicate.fold_with(folder),
 781         }
 782     }
 783 }
 784
 785 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableImplData<'tcx, N> {
 786     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableImplData<'tcx, N> {
 787         traits::VtableImplData {
 788             impl_def_id: self.impl_def_id,
 789             substs: self.substs.fold_with(folder),
 790             nested: self.nested.fold_with(folder),
 791         }
 792     }
 793 }
 794
 795 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableClosureData<'tcx, N> {
 796     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableClosureData<'tcx, N> {
 797         traits::VtableClosureData {
 798             closure_def_id: self.closure_def_id,
 799             substs: self.substs.fold_with(folder),
 800             nested: self.nested.fold_with(folder),
 801         }
 802     }
 803 }
 804
 805 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableDefaultImplData<N> {
 806     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableDefaultImplData<N> {
 807         traits::VtableDefaultImplData {
 808             trait_def_id: self.trait_def_id,
 809             nested: self.nested.fold_with(folder),
 810         }
 811     }
 812 }
 813
 814 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableBuiltinData<N> {
 815     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableBuiltinData<N> {
 816         traits::VtableBuiltinData {
 817             nested: self.nested.fold_with(folder),
 818         }
 819     }
 820 }
 821
 822 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Vtable<'tcx, N> {
 823     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Vtable<'tcx, N> {
 824         match *self {
 825             traits::VtableImpl(ref v) => traits::VtableImpl(v.fold_with(folder)),
 826             traits::VtableDefaultImpl(ref t) => traits::VtableDefaultImpl(t.fold_with(folder)),
 827             traits::VtableClosure(ref d) => {
 828                 traits::VtableClosure(d.fold_with(folder))
 829             }
 830             traits::VtableFnPointer(ref d) => {
 831                 traits::VtableFnPointer(d.fold_with(folder))
 832             }
 833             traits::VtableParam(ref n) => traits::VtableParam(n.fold_with(folder)),
 834             traits::VtableBuiltin(ref d) => traits::VtableBuiltin(d.fold_with(folder)),
 835             traits::VtableObject(ref d) => traits::VtableObject(d.fold_with(folder)),
 836         }
 837     }
 838 }
 839
 840 impl<'tcx> TypeFoldable<'tcx> for traits::VtableObjectData<'tcx> {
 841     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableObjectData<'tcx> {
 842         traits::VtableObjectData {
 843             upcast_trait_ref: self.upcast_trait_ref.fold_with(folder),
 844             vtable_base: self.vtable_base
 845         }
 846     }
 847 }
 848
 849 impl<'tcx> TypeFoldable<'tcx> for ty::EquatePredicate<'tcx> {
 850     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::EquatePredicate<'tcx> {
 851         ty::EquatePredicate(self.0.fold_with(folder),
 852                             self.1.fold_with(folder))
 853     }
 854 }
 855
 856 impl<'tcx> TypeFoldable<'tcx> for ty::TraitPredicate<'tcx> {
 857     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::TraitPredicate<'tcx> {
 858         ty::TraitPredicate {
 859             trait_ref: self.trait_ref.fold_with(folder)
 860         }
 861     }
 862 }
 863
 864 impl<'tcx,T,U> TypeFoldable<'tcx> for ty::OutlivesPredicate<T,U>
 865     where T : TypeFoldable<'tcx>,
 866           U : TypeFoldable<'tcx>,
 867 {
 868     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::OutlivesPredicate<T,U> {
 869         ty::OutlivesPredicate(self.0.fold_with(folder),
 870                               self.1.fold_with(folder))
 871     }
 872 }
 873
 874 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureUpvar<'tcx> {
 875     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ClosureUpvar<'tcx> {
 876         ty::ClosureUpvar {
 877             def: self.def,
 878             span: self.span,
 879             ty: self.ty.fold_with(folder),
 880         }
 881     }
 882 }
 883
 884 impl<'a, 'tcx> TypeFoldable<'tcx> for ty::ParameterEnvironment<'a, 'tcx> where 'tcx: 'a {
 885     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::ParameterEnvironment<'a, 'tcx> {
 886         ty::ParameterEnvironment {
 887             tcx: self.tcx,
 888             free_substs: self.free_substs.fold_with(folder),
 889             implicit_region_bound: self.implicit_region_bound.fold_with(folder),
 890             caller_bounds: self.caller_bounds.fold_with(folder),
 891             selection_cache: traits::SelectionCache::new(),
 892             free_id: self.free_id,
 893         }
 894     }
 895 }