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