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