src/librustc/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 infer::type_variable;
  12 use middle::const_val::{self, ConstVal, ConstAggregate, ConstEvalErr};
  13 use ty::{self, Lift, Ty, TyCtxt};
  14 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
  15 use rustc_data_structures::accumulate_vec::AccumulateVec;
  16 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  17
  18 use std::rc::Rc;
  19 use syntax::abi;
  20
  21 use hir;
  22
  23 ///////////////////////////////////////////////////////////////////////////
  24 // Lift implementations
  25
  26 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>> Lift<'tcx> for (A, B) {
  27     type Lifted = (A::Lifted, B::Lifted);
  28     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  29         tcx.lift(&self.0).and_then(|a| tcx.lift(&self.1).map(|b| (a, b)))
  30     }
  31 }
  32
  33 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>, C: Lift<'tcx>> Lift<'tcx> for (A, B, C) {
  34     type Lifted = (A::Lifted, B::Lifted, C::Lifted);
  35     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  36         tcx.lift(&self.0).and_then(|a| {
  37             tcx.lift(&self.1).and_then(|b| tcx.lift(&self.2).map(|c| (a, b, c)))
  38         })
  39     }
  40 }
  41
  42 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Option<T> {
  43     type Lifted = Option<T::Lifted>;
  44     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  45         match *self {
  46             Some(ref x) => tcx.lift(x).map(Some),
  47             None => Some(None)
  48         }
  49     }
  50 }
  51
  52 impl<'tcx, T: Lift<'tcx>, E: Lift<'tcx>> Lift<'tcx> for Result<T, E> {
  53     type Lifted = Result<T::Lifted, E::Lifted>;
  54     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  55         match *self {
  56             Ok(ref x) => tcx.lift(x).map(Ok),
  57             Err(ref e) => tcx.lift(e).map(Err)
  58         }
  59     }
  60 }
  61
  62 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Box<T> {
  63     type Lifted = Box<T::Lifted>;
  64     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  65         tcx.lift(&**self).map(Box::new)
  66     }
  67 }
  68
  69 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for [T] {
  70     type Lifted = Vec<T::Lifted>;
  71     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  72         // type annotation needed to inform `projection_must_outlive`
  73         let mut result : Vec<<T as Lift<'tcx>>::Lifted>
  74             = Vec::with_capacity(self.len());
  75         for x in self {
  76             if let Some(value) = tcx.lift(x) {
  77                 result.push(value);
  78             } else {
  79                 return None;
  80             }
  81         }
  82         Some(result)
  83     }
  84 }
  85
  86 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Vec<T> {
  87     type Lifted = Vec<T::Lifted>;
  88     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  89         tcx.lift(&self[..])
  90     }
  91 }
  92
  93 impl<'a, 'tcx> Lift<'tcx> for ty::TraitRef<'a> {
  94     type Lifted = ty::TraitRef<'tcx>;
  95     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
  96         tcx.lift(&self.substs).map(|substs| ty::TraitRef {
  97             def_id: self.def_id,
  98             substs,
  99         })
 100     }
 101 }
 102
 103 impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialTraitRef<'a> {
 104     type Lifted = ty::ExistentialTraitRef<'tcx>;
 105     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 106         tcx.lift(&self.substs).map(|substs| ty::ExistentialTraitRef {
 107             def_id: self.def_id,
 108             substs,
 109         })
 110     }
 111 }
 112
 113 impl<'a, 'tcx> Lift<'tcx> for ty::TraitPredicate<'a> {
 114     type Lifted = ty::TraitPredicate<'tcx>;
 115     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
 116                              -> Option<ty::TraitPredicate<'tcx>> {
 117         tcx.lift(&self.trait_ref).map(|trait_ref| ty::TraitPredicate {
 118             trait_ref,
 119         })
 120     }
 121 }
 122
 123 impl<'a, 'tcx> Lift<'tcx> for ty::EquatePredicate<'a> {
 124     type Lifted = ty::EquatePredicate<'tcx>;
 125     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
 126                              -> Option<ty::EquatePredicate<'tcx>> {
 127         tcx.lift(&(self.0, self.1)).map(|(a, b)| ty::EquatePredicate(a, b))
 128     }
 129 }
 130
 131 impl<'a, 'tcx> Lift<'tcx> for ty::SubtypePredicate<'a> {
 132     type Lifted = ty::SubtypePredicate<'tcx>;
 133     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
 134                              -> Option<ty::SubtypePredicate<'tcx>> {
 135         tcx.lift(&(self.a, self.b)).map(|(a, b)| ty::SubtypePredicate {
 136             a_is_expected: self.a_is_expected,
 137             a,
 138             b,
 139         })
 140     }
 141 }
 142
 143 impl<'tcx, A: Copy+Lift<'tcx>, B: Copy+Lift<'tcx>> Lift<'tcx> for ty::OutlivesPredicate<A, B> {
 144     type Lifted = ty::OutlivesPredicate<A::Lifted, B::Lifted>;
 145     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 146         tcx.lift(&(self.0, self.1)).map(|(a, b)| ty::OutlivesPredicate(a, b))
 147     }
 148 }
 149
 150 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionTy<'a> {
 151     type Lifted = ty::ProjectionTy<'tcx>;
 152     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
 153                              -> Option<ty::ProjectionTy<'tcx>> {
 154         tcx.lift(&self.substs).map(|substs| {
 155             ty::ProjectionTy {
 156                 item_def_id: self.item_def_id,
 157                 substs,
 158             }
 159         })
 160     }
 161 }
 162
 163 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
 164     type Lifted = ty::ProjectionPredicate<'tcx>;
 165     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>)
 166                              -> Option<ty::ProjectionPredicate<'tcx>> {
 167         tcx.lift(&(self.projection_ty, self.ty)).map(|(projection_ty, ty)| {
 168             ty::ProjectionPredicate {
 169                 projection_ty,
 170                 ty,
 171             }
 172         })
 173     }
 174 }
 175
 176 impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialProjection<'a> {
 177     type Lifted = ty::ExistentialProjection<'tcx>;
 178     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 179         tcx.lift(&self.substs).map(|substs| {
 180             ty::ExistentialProjection {
 181                 substs,
 182                 ty: tcx.lift(&self.ty).expect("type must lift when substs do"),
 183                 item_def_id: self.item_def_id,
 184             }
 185         })
 186     }
 187 }
 188
 189 impl<'a, 'tcx> Lift<'tcx> for ty::Predicate<'a> {
 190     type Lifted = ty::Predicate<'tcx>;
 191     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 192         match *self {
 193             ty::Predicate::Trait(ref binder) => {
 194                 tcx.lift(binder).map(ty::Predicate::Trait)
 195             }
 196             ty::Predicate::Equate(ref binder) => {
 197                 tcx.lift(binder).map(ty::Predicate::Equate)
 198             }
 199             ty::Predicate::Subtype(ref binder) => {
 200                 tcx.lift(binder).map(ty::Predicate::Subtype)
 201             }
 202             ty::Predicate::RegionOutlives(ref binder) => {
 203                 tcx.lift(binder).map(ty::Predicate::RegionOutlives)
 204             }
 205             ty::Predicate::TypeOutlives(ref binder) => {
 206                 tcx.lift(binder).map(ty::Predicate::TypeOutlives)
 207             }
 208             ty::Predicate::Projection(ref binder) => {
 209                 tcx.lift(binder).map(ty::Predicate::Projection)
 210             }
 211             ty::Predicate::WellFormed(ty) => {
 212                 tcx.lift(&ty).map(ty::Predicate::WellFormed)
 213             }
 214             ty::Predicate::ClosureKind(closure_def_id, kind) => {
 215                 Some(ty::Predicate::ClosureKind(closure_def_id, kind))
 216             }
 217             ty::Predicate::ObjectSafe(trait_def_id) => {
 218                 Some(ty::Predicate::ObjectSafe(trait_def_id))
 219             }
 220             ty::Predicate::ConstEvaluatable(def_id, substs) => {
 221                 tcx.lift(&substs).map(|substs| {
 222                     ty::Predicate::ConstEvaluatable(def_id, substs)
 223                 })
 224             }
 225         }
 226     }
 227 }
 228
 229 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::Binder<T> {
 230     type Lifted = ty::Binder<T::Lifted>;
 231     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 232         tcx.lift(&self.0).map(|x| ty::Binder(x))
 233     }
 234 }
 235
 236 impl<'a, 'tcx> Lift<'tcx> for ty::ParamEnv<'a> {
 237     type Lifted = ty::ParamEnv<'tcx>;
 238     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 239         tcx.lift(&self.caller_bounds).map(|caller_bounds| {
 240             ty::ParamEnv {
 241                 reveal: self.reveal,
 242                 caller_bounds,
 243             }
 244         })
 245     }
 246 }
 247
 248 impl<'a, 'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::ParamEnvAnd<'a, T> {
 249     type Lifted = ty::ParamEnvAnd<'tcx, T::Lifted>;
 250     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 251         tcx.lift(&self.param_env).and_then(|param_env| {
 252             tcx.lift(&self.value).map(|value| {
 253                 ty::ParamEnvAnd {
 254                     param_env,
 255                     value,
 256                 }
 257             })
 258         })
 259     }
 260 }
 261
 262 impl<'a, 'tcx> Lift<'tcx> for ty::ClosureSubsts<'a> {
 263     type Lifted = ty::ClosureSubsts<'tcx>;
 264     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 265         tcx.lift(&self.substs).map(|substs| {
 266             ty::ClosureSubsts { substs: substs }
 267         })
 268     }
 269 }
 270
 271 impl<'a, 'tcx> Lift<'tcx> for ty::GeneratorInterior<'a> {
 272     type Lifted = ty::GeneratorInterior<'tcx>;
 273     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 274         tcx.lift(&self.witness).map(|witness| {
 275             ty::GeneratorInterior { witness }
 276         })
 277     }
 278 }
 279
 280 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::Adjustment<'a> {
 281     type Lifted = ty::adjustment::Adjustment<'tcx>;
 282     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 283         tcx.lift(&self.kind).and_then(|kind| {
 284             tcx.lift(&self.target).map(|target| {
 285                 ty::adjustment::Adjustment { kind, target }
 286             })
 287         })
 288     }
 289 }
 290
 291 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::Adjust<'a> {
 292     type Lifted = ty::adjustment::Adjust<'tcx>;
 293     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 294         match *self {
 295             ty::adjustment::Adjust::NeverToAny =>
 296                 Some(ty::adjustment::Adjust::NeverToAny),
 297             ty::adjustment::Adjust::ReifyFnPointer =>
 298                 Some(ty::adjustment::Adjust::ReifyFnPointer),
 299             ty::adjustment::Adjust::UnsafeFnPointer =>
 300                 Some(ty::adjustment::Adjust::UnsafeFnPointer),
 301             ty::adjustment::Adjust::ClosureFnPointer =>
 302                 Some(ty::adjustment::Adjust::ClosureFnPointer),
 303             ty::adjustment::Adjust::MutToConstPointer =>
 304                 Some(ty::adjustment::Adjust::MutToConstPointer),
 305             ty::adjustment::Adjust::Unsize =>
 306                 Some(ty::adjustment::Adjust::Unsize),
 307             ty::adjustment::Adjust::Deref(ref overloaded) => {
 308                 tcx.lift(overloaded).map(ty::adjustment::Adjust::Deref)
 309             }
 310             ty::adjustment::Adjust::Borrow(ref autoref) => {
 311                 tcx.lift(autoref).map(ty::adjustment::Adjust::Borrow)
 312             }
 313         }
 314     }
 315 }
 316
 317 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::OverloadedDeref<'a> {
 318     type Lifted = ty::adjustment::OverloadedDeref<'tcx>;
 319     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 320         tcx.lift(&self.region).map(|region| {
 321             ty::adjustment::OverloadedDeref {
 322                 region,
 323                 mutbl: self.mutbl,
 324             }
 325         })
 326     }
 327 }
 328
 329 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::AutoBorrow<'a> {
 330     type Lifted = ty::adjustment::AutoBorrow<'tcx>;
 331     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 332         match *self {
 333             ty::adjustment::AutoBorrow::Ref(r, m) => {
 334                 tcx.lift(&r).map(|r| ty::adjustment::AutoBorrow::Ref(r, m))
 335             }
 336             ty::adjustment::AutoBorrow::RawPtr(m) => {
 337                 Some(ty::adjustment::AutoBorrow::RawPtr(m))
 338             }
 339         }
 340     }
 341 }
 342
 343 impl<'a, 'tcx> Lift<'tcx> for ty::GenSig<'a> {
 344     type Lifted = ty::GenSig<'tcx>;
 345     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 346         tcx.lift(&(self.yield_ty, self.return_ty))
 347             .map(|(yield_ty, return_ty)| {
 348                 ty::GenSig {
 349                     yield_ty,
 350                     return_ty,
 351                 }
 352             })
 353     }
 354 }
 355
 356 impl<'a, 'tcx> Lift<'tcx> for ty::FnSig<'a> {
 357     type Lifted = ty::FnSig<'tcx>;
 358     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 359         tcx.lift(&self.inputs_and_output).map(|x| {
 360             ty::FnSig {
 361                 inputs_and_output: x,
 362                 variadic: self.variadic,
 363                 unsafety: self.unsafety,
 364                 abi: self.abi,
 365             }
 366         })
 367     }
 368 }
 369
 370 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::error::ExpectedFound<T> {
 371     type Lifted = ty::error::ExpectedFound<T::Lifted>;
 372     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 373         tcx.lift(&self.expected).and_then(|expected| {
 374             tcx.lift(&self.found).map(|found| {
 375                 ty::error::ExpectedFound {
 376                     expected,
 377                     found,
 378                 }
 379             })
 380         })
 381     }
 382 }
 383
 384 impl<'a, 'tcx> Lift<'tcx> for type_variable::Default<'a> {
 385     type Lifted = type_variable::Default<'tcx>;
 386     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 387         tcx.lift(&self.ty).map(|ty| {
 388             type_variable::Default {
 389                 ty,
 390                 origin_span: self.origin_span,
 391                 def_id: self.def_id
 392             }
 393         })
 394     }
 395 }
 396
 397 impl<'a, 'tcx> Lift<'tcx> for ty::error::TypeError<'a> {
 398     type Lifted = ty::error::TypeError<'tcx>;
 399     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 400         use ty::error::TypeError::*;
 401
 402         Some(match *self {
 403             Mismatch => Mismatch,
 404             UnsafetyMismatch(x) => UnsafetyMismatch(x),
 405             AbiMismatch(x) => AbiMismatch(x),
 406             Mutability => Mutability,
 407             TupleSize(x) => TupleSize(x),
 408             FixedArraySize(x) => FixedArraySize(x),
 409             ArgCount => ArgCount,
 410             RegionsDoesNotOutlive(a, b) => {
 411                 return tcx.lift(&(a, b)).map(|(a, b)| RegionsDoesNotOutlive(a, b))
 412             }
 413             RegionsInsufficientlyPolymorphic(a, b) => {
 414                 return tcx.lift(&b).map(|b| RegionsInsufficientlyPolymorphic(a, b))
 415             }
 416             RegionsOverlyPolymorphic(a, b) => {
 417                 return tcx.lift(&b).map(|b| RegionsOverlyPolymorphic(a, b))
 418             }
 419             IntMismatch(x) => IntMismatch(x),
 420             FloatMismatch(x) => FloatMismatch(x),
 421             Traits(x) => Traits(x),
 422             VariadicMismatch(x) => VariadicMismatch(x),
 423             CyclicTy => CyclicTy,
 424             ProjectionMismatched(x) => ProjectionMismatched(x),
 425             ProjectionBoundsLength(x) => ProjectionBoundsLength(x),
 426
 427             Sorts(ref x) => return tcx.lift(x).map(Sorts),
 428             TyParamDefaultMismatch(ref x) => {
 429                 return tcx.lift(x).map(TyParamDefaultMismatch)
 430             }
 431             ExistentialMismatch(ref x) => return tcx.lift(x).map(ExistentialMismatch),
 432             OldStyleLUB(ref x) => return tcx.lift(x).map(OldStyleLUB),
 433         })
 434     }
 435 }
 436
 437 impl<'a, 'tcx> Lift<'tcx> for ConstEvalErr<'a> {
 438     type Lifted = ConstEvalErr<'tcx>;
 439     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 440         tcx.lift(&self.kind).map(|kind| {
 441             ConstEvalErr {
 442                 span: self.span,
 443                 kind,
 444             }
 445         })
 446     }
 447 }
 448
 449 impl<'a, 'tcx> Lift<'tcx> for const_val::ErrKind<'a> {
 450     type Lifted = const_val::ErrKind<'tcx>;
 451     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 452         use middle::const_val::ErrKind::*;
 453
 454         Some(match *self {
 455             CannotCast => CannotCast,
 456             MissingStructField => MissingStructField,
 457             NonConstPath => NonConstPath,
 458             UnimplementedConstVal(s) => UnimplementedConstVal(s),
 459             ExpectedConstTuple => ExpectedConstTuple,
 460             ExpectedConstStruct => ExpectedConstStruct,
 461             IndexedNonVec => IndexedNonVec,
 462             IndexNotUsize => IndexNotUsize,
 463             IndexOutOfBounds { len, index } => IndexOutOfBounds { len, index },
 464             MiscBinaryOp => MiscBinaryOp,
 465             MiscCatchAll => MiscCatchAll,
 466             IndexOpFeatureGated => IndexOpFeatureGated,
 467             Math(ref e) => Math(e.clone()),
 468
 469             LayoutError(ref e) => {
 470                 return tcx.lift(e).map(LayoutError)
 471             }
 472             ErroneousReferencedConstant(ref e) => {
 473                 return tcx.lift(e).map(ErroneousReferencedConstant)
 474             }
 475
 476             TypeckError => TypeckError,
 477         })
 478     }
 479 }
 480
 481 impl<'a, 'tcx> Lift<'tcx> for ty::layout::LayoutError<'a> {
 482     type Lifted = ty::layout::LayoutError<'tcx>;
 483     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 484         match *self {
 485             ty::layout::LayoutError::Unknown(ref ty) => {
 486                 tcx.lift(ty).map(ty::layout::LayoutError::Unknown)
 487             }
 488             ty::layout::LayoutError::SizeOverflow(ref ty) => {
 489                 tcx.lift(ty).map(ty::layout::LayoutError::SizeOverflow)
 490             }
 491         }
 492     }
 493 }
 494
 495 ///////////////////////////////////////////////////////////////////////////
 496 // TypeFoldable implementations.
 497 //
 498 // Ideally, each type should invoke `folder.fold_foo(self)` and
 499 // nothing else. In some cases, though, we haven't gotten around to
 500 // adding methods on the `folder` yet, and thus the folding is
 501 // hard-coded here. This is less-flexible, because folders cannot
 502 // override the behavior, but there are a lot of random types and one
 503 // can easily refactor the folding into the TypeFolder trait as
 504 // needed.
 505
 506 macro_rules! CopyImpls {
 507     ($($ty:ty),+) => {
 508         $(
 509             impl<'tcx> Lift<'tcx> for $ty {
 510                 type Lifted = Self;
 511                 fn lift_to_tcx<'a, 'gcx>(&self, _: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self> {
 512                     Some(*self)
 513                 }
 514             }
 515
 516             impl<'tcx> TypeFoldable<'tcx> for $ty {
 517                 fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, _: &mut F) -> $ty {
 518                     *self
 519                 }
 520
 521                 fn super_visit_with<F: TypeVisitor<'tcx>>(&self, _: &mut F) -> bool {
 522                     false
 523                 }
 524             }
 525         )+
 526     }
 527 }
 528
 529 CopyImpls! { (), hir::Unsafety, abi::Abi, hir::def_id::DefId, ::mir::Local }
 530
 531 impl<'tcx, T:TypeFoldable<'tcx>, U:TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
 532     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> (T, U) {
 533         (self.0.fold_with(folder), self.1.fold_with(folder))
 534     }
 535
 536     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 537         self.0.visit_with(visitor) || self.1.visit_with(visitor)
 538     }
 539 }
 540
 541 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Option<T> {
 542     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 543         self.as_ref().map(|t| t.fold_with(folder))
 544     }
 545
 546     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 547         self.iter().any(|t| t.visit_with(visitor))
 548     }
 549 }
 550
 551 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Rc<T> {
 552     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 553         Rc::new((**self).fold_with(folder))
 554     }
 555
 556     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 557         (**self).visit_with(visitor)
 558     }
 559 }
 560
 561 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<T> {
 562     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 563         let content: T = (**self).fold_with(folder);
 564         box content
 565     }
 566
 567     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 568         (**self).visit_with(visitor)
 569     }
 570 }
 571
 572 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
 573     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 574         self.iter().map(|t| t.fold_with(folder)).collect()
 575     }
 576
 577     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 578         self.iter().any(|t| t.visit_with(visitor))
 579     }
 580 }
 581
 582 impl<'tcx, T:TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
 583     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 584         ty::Binder(self.0.fold_with(folder))
 585     }
 586
 587     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 588         folder.fold_binder(self)
 589     }
 590
 591     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 592         self.0.visit_with(visitor)
 593     }
 594
 595     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 596         visitor.visit_binder(self)
 597     }
 598 }
 599
 600 impl<'tcx> TypeFoldable<'tcx> for ty::ParamEnv<'tcx> {
 601     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 602         ty::ParamEnv {
 603             reveal: self.reveal,
 604             caller_bounds: self.caller_bounds.fold_with(folder),
 605         }
 606     }
 607
 608     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 609         let &ty::ParamEnv { reveal: _, ref caller_bounds } = self;
 610         caller_bounds.super_visit_with(visitor)
 611     }
 612 }
 613
 614 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Slice<ty::ExistentialPredicate<'tcx>> {
 615     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 616         let v = self.iter().map(|p| p.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
 617         folder.tcx().intern_existential_predicates(&v)
 618     }
 619
 620     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 621         self.iter().any(|p| p.visit_with(visitor))
 622     }
 623 }
 624
 625 impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialPredicate<'tcx> {
 626     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self  {
 627         use ty::ExistentialPredicate::*;
 628         match *self {
 629             Trait(ref tr) => Trait(tr.fold_with(folder)),
 630             Projection(ref p) => Projection(p.fold_with(folder)),
 631             AutoTrait(did) => AutoTrait(did),
 632         }
 633     }
 634
 635     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 636         match *self {
 637             ty::ExistentialPredicate::Trait(ref tr) => tr.visit_with(visitor),
 638             ty::ExistentialPredicate::Projection(ref p) => p.visit_with(visitor),
 639             ty::ExistentialPredicate::AutoTrait(_) => false,
 640         }
 641     }
 642 }
 643
 644 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Slice<Ty<'tcx>> {
 645     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 646         let v = self.iter().map(|t| t.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
 647         folder.tcx().intern_type_list(&v)
 648     }
 649
 650     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 651         self.iter().any(|t| t.visit_with(visitor))
 652     }
 653 }
 654
 655 impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
 656     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 657         let sty = match self.sty {
 658             ty::TyRawPtr(tm) => ty::TyRawPtr(tm.fold_with(folder)),
 659             ty::TyArray(typ, sz) => ty::TyArray(typ.fold_with(folder), sz.fold_with(folder)),
 660             ty::TySlice(typ) => ty::TySlice(typ.fold_with(folder)),
 661             ty::TyAdt(tid, substs) => ty::TyAdt(tid, substs.fold_with(folder)),
 662             ty::TyDynamic(ref trait_ty, ref region) =>
 663                 ty::TyDynamic(trait_ty.fold_with(folder), region.fold_with(folder)),
 664             ty::TyTuple(ts, defaulted) => ty::TyTuple(ts.fold_with(folder), defaulted),
 665             ty::TyFnDef(def_id, substs) => {
 666                 ty::TyFnDef(def_id, substs.fold_with(folder))
 667             }
 668             ty::TyFnPtr(f) => ty::TyFnPtr(f.fold_with(folder)),
 669             ty::TyRef(ref r, tm) => {
 670                 ty::TyRef(r.fold_with(folder), tm.fold_with(folder))
 671             }
 672             ty::TyGenerator(did, substs, interior) => {
 673                 ty::TyGenerator(did, substs.fold_with(folder), interior.fold_with(folder))
 674             }
 675             ty::TyClosure(did, substs) => ty::TyClosure(did, substs.fold_with(folder)),
 676             ty::TyProjection(ref data) => ty::TyProjection(data.fold_with(folder)),
 677             ty::TyAnon(did, substs) => ty::TyAnon(did, substs.fold_with(folder)),
 678             ty::TyBool | ty::TyChar | ty::TyStr | ty::TyInt(_) |
 679             ty::TyUint(_) | ty::TyFloat(_) | ty::TyError | ty::TyInfer(_) |
 680             ty::TyParam(..) | ty::TyNever | ty::TyForeign(..) => return self
 681         };
 682
 683         if self.sty == sty {
 684             self
 685         } else {
 686             folder.tcx().mk_ty(sty)
 687         }
 688     }
 689
 690     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 691         folder.fold_ty(*self)
 692     }
 693
 694     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 695         match self.sty {
 696             ty::TyRawPtr(ref tm) => tm.visit_with(visitor),
 697             ty::TyArray(typ, sz) => typ.visit_with(visitor) || sz.visit_with(visitor),
 698             ty::TySlice(typ) => typ.visit_with(visitor),
 699             ty::TyAdt(_, substs) => substs.visit_with(visitor),
 700             ty::TyDynamic(ref trait_ty, ref reg) =>
 701                 trait_ty.visit_with(visitor) || reg.visit_with(visitor),
 702             ty::TyTuple(ts, _) => ts.visit_with(visitor),
 703             ty::TyFnDef(_, substs) => substs.visit_with(visitor),
 704             ty::TyFnPtr(ref f) => f.visit_with(visitor),
 705             ty::TyRef(r, ref tm) => r.visit_with(visitor) || tm.visit_with(visitor),
 706             ty::TyGenerator(_did, ref substs, ref interior) => {
 707                 substs.visit_with(visitor) || interior.visit_with(visitor)
 708             }
 709             ty::TyClosure(_did, ref substs) => substs.visit_with(visitor),
 710             ty::TyProjection(ref data) => data.visit_with(visitor),
 711             ty::TyAnon(_, ref substs) => substs.visit_with(visitor),
 712             ty::TyBool | ty::TyChar | ty::TyStr | ty::TyInt(_) |
 713             ty::TyUint(_) | ty::TyFloat(_) | ty::TyError | ty::TyInfer(_) |
 714             ty::TyParam(..) | ty::TyNever | ty::TyForeign(..) => false,
 715         }
 716     }
 717
 718     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 719         visitor.visit_ty(self)
 720     }
 721 }
 722
 723 impl<'tcx> TypeFoldable<'tcx> for ty::TypeAndMut<'tcx> {
 724     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 725         ty::TypeAndMut { ty: self.ty.fold_with(folder), mutbl: self.mutbl }
 726     }
 727
 728     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 729         self.ty.visit_with(visitor)
 730     }
 731 }
 732
 733 impl<'tcx> TypeFoldable<'tcx> for ty::GenSig<'tcx> {
 734     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 735         ty::GenSig {
 736             yield_ty: self.yield_ty.fold_with(folder),
 737             return_ty: self.return_ty.fold_with(folder),
 738         }
 739     }
 740
 741     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 742         self.yield_ty.visit_with(visitor) ||
 743         self.return_ty.visit_with(visitor)
 744     }
 745 }
 746
 747 impl<'tcx> TypeFoldable<'tcx> for ty::FnSig<'tcx> {
 748     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 749         let inputs_and_output = self.inputs_and_output.fold_with(folder);
 750         ty::FnSig {
 751             inputs_and_output: folder.tcx().intern_type_list(&inputs_and_output),
 752             variadic: self.variadic,
 753             unsafety: self.unsafety,
 754             abi: self.abi,
 755         }
 756     }
 757
 758     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 759         self.inputs().iter().any(|i| i.visit_with(visitor)) ||
 760         self.output().visit_with(visitor)
 761     }
 762 }
 763
 764 impl<'tcx> TypeFoldable<'tcx> for ty::TraitRef<'tcx> {
 765     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 766         ty::TraitRef {
 767             def_id: self.def_id,
 768             substs: self.substs.fold_with(folder),
 769         }
 770     }
 771
 772     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 773         self.substs.visit_with(visitor)
 774     }
 775 }
 776
 777 impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialTraitRef<'tcx> {
 778     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 779         ty::ExistentialTraitRef {
 780             def_id: self.def_id,
 781             substs: self.substs.fold_with(folder),
 782         }
 783     }
 784
 785     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 786         self.substs.visit_with(visitor)
 787     }
 788 }
 789
 790 impl<'tcx> TypeFoldable<'tcx> for ty::ImplHeader<'tcx> {
 791     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 792         ty::ImplHeader {
 793             impl_def_id: self.impl_def_id,
 794             self_ty: self.self_ty.fold_with(folder),
 795             trait_ref: self.trait_ref.map(|t| t.fold_with(folder)),
 796             predicates: self.predicates.iter().map(|p| p.fold_with(folder)).collect(),
 797         }
 798     }
 799
 800     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 801         self.self_ty.visit_with(visitor) ||
 802             self.trait_ref.map(|r| r.visit_with(visitor)).unwrap_or(false) ||
 803             self.predicates.iter().any(|p| p.visit_with(visitor))
 804     }
 805 }
 806
 807 impl<'tcx> TypeFoldable<'tcx> for ty::Region<'tcx> {
 808     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, _folder: &mut F) -> Self {
 809         *self
 810     }
 811
 812     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 813         folder.fold_region(*self)
 814     }
 815
 816     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> bool {
 817         false
 818     }
 819
 820     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 821         visitor.visit_region(*self)
 822     }
 823 }
 824
 825 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureSubsts<'tcx> {
 826     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 827         ty::ClosureSubsts {
 828             substs: self.substs.fold_with(folder),
 829         }
 830     }
 831
 832     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 833         self.substs.visit_with(visitor)
 834     }
 835 }
 836
 837 impl<'tcx> TypeFoldable<'tcx> for ty::GeneratorInterior<'tcx> {
 838     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 839         ty::GeneratorInterior::new(self.witness.fold_with(folder))
 840     }
 841
 842     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 843         self.witness.visit_with(visitor)
 844     }
 845 }
 846
 847 impl<'tcx> TypeFoldable<'tcx> for ty::adjustment::Adjustment<'tcx> {
 848     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 849         ty::adjustment::Adjustment {
 850             kind: self.kind.fold_with(folder),
 851             target: self.target.fold_with(folder),
 852         }
 853     }
 854
 855     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 856         self.kind.visit_with(visitor) ||
 857         self.target.visit_with(visitor)
 858     }
 859 }
 860
 861 impl<'tcx> TypeFoldable<'tcx> for ty::adjustment::Adjust<'tcx> {
 862     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 863         match *self {
 864             ty::adjustment::Adjust::NeverToAny |
 865             ty::adjustment::Adjust::ReifyFnPointer |
 866             ty::adjustment::Adjust::UnsafeFnPointer |
 867             ty::adjustment::Adjust::ClosureFnPointer |
 868             ty::adjustment::Adjust::MutToConstPointer |
 869             ty::adjustment::Adjust::Unsize => self.clone(),
 870             ty::adjustment::Adjust::Deref(ref overloaded) => {
 871                 ty::adjustment::Adjust::Deref(overloaded.fold_with(folder))
 872             }
 873             ty::adjustment::Adjust::Borrow(ref autoref) => {
 874                 ty::adjustment::Adjust::Borrow(autoref.fold_with(folder))
 875             }
 876         }
 877     }
 878
 879     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 880         match *self {
 881             ty::adjustment::Adjust::NeverToAny |
 882             ty::adjustment::Adjust::ReifyFnPointer |
 883             ty::adjustment::Adjust::UnsafeFnPointer |
 884             ty::adjustment::Adjust::ClosureFnPointer |
 885             ty::adjustment::Adjust::MutToConstPointer |
 886             ty::adjustment::Adjust::Unsize => false,
 887             ty::adjustment::Adjust::Deref(ref overloaded) => {
 888                 overloaded.visit_with(visitor)
 889             }
 890             ty::adjustment::Adjust::Borrow(ref autoref) => {
 891                 autoref.visit_with(visitor)
 892             }
 893         }
 894     }
 895 }
 896
 897 impl<'tcx> TypeFoldable<'tcx> for ty::adjustment::OverloadedDeref<'tcx> {
 898     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 899         ty::adjustment::OverloadedDeref {
 900             region: self.region.fold_with(folder),
 901             mutbl: self.mutbl,
 902         }
 903     }
 904
 905     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 906         self.region.visit_with(visitor)
 907     }
 908 }
 909
 910 impl<'tcx> TypeFoldable<'tcx> for ty::adjustment::AutoBorrow<'tcx> {
 911     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 912         match *self {
 913             ty::adjustment::AutoBorrow::Ref(ref r, m) => {
 914                 ty::adjustment::AutoBorrow::Ref(r.fold_with(folder), m)
 915             }
 916             ty::adjustment::AutoBorrow::RawPtr(m) => ty::adjustment::AutoBorrow::RawPtr(m)
 917         }
 918     }
 919
 920     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 921         match *self {
 922             ty::adjustment::AutoBorrow::Ref(r, _m) => r.visit_with(visitor),
 923             ty::adjustment::AutoBorrow::RawPtr(_m) => false,
 924         }
 925     }
 926 }
 927
 928 impl<'tcx> TypeFoldable<'tcx> for ty::GenericPredicates<'tcx> {
 929     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 930         ty::GenericPredicates {
 931             parent: self.parent,
 932             predicates: self.predicates.fold_with(folder),
 933         }
 934     }
 935
 936     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 937         self.predicates.visit_with(visitor)
 938     }
 939 }
 940
 941 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Slice<ty::Predicate<'tcx>> {
 942     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 943         let v = self.iter().map(|p| p.fold_with(folder)).collect::<AccumulateVec<[_; 8]>>();
 944         folder.tcx().intern_predicates(&v)
 945     }
 946
 947     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 948         self.iter().any(|p| p.visit_with(visitor))
 949     }
 950 }
 951
 952 impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
 953     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 954         match *self {
 955             ty::Predicate::Trait(ref a) =>
 956                 ty::Predicate::Trait(a.fold_with(folder)),
 957             ty::Predicate::Equate(ref binder) =>
 958                 ty::Predicate::Equate(binder.fold_with(folder)),
 959             ty::Predicate::Subtype(ref binder) =>
 960                 ty::Predicate::Subtype(binder.fold_with(folder)),
 961             ty::Predicate::RegionOutlives(ref binder) =>
 962                 ty::Predicate::RegionOutlives(binder.fold_with(folder)),
 963             ty::Predicate::TypeOutlives(ref binder) =>
 964                 ty::Predicate::TypeOutlives(binder.fold_with(folder)),
 965             ty::Predicate::Projection(ref binder) =>
 966                 ty::Predicate::Projection(binder.fold_with(folder)),
 967             ty::Predicate::WellFormed(data) =>
 968                 ty::Predicate::WellFormed(data.fold_with(folder)),
 969             ty::Predicate::ClosureKind(closure_def_id, kind) =>
 970                 ty::Predicate::ClosureKind(closure_def_id, kind),
 971             ty::Predicate::ObjectSafe(trait_def_id) =>
 972                 ty::Predicate::ObjectSafe(trait_def_id),
 973             ty::Predicate::ConstEvaluatable(def_id, substs) =>
 974                 ty::Predicate::ConstEvaluatable(def_id, substs.fold_with(folder)),
 975         }
 976     }
 977
 978     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 979         match *self {
 980             ty::Predicate::Trait(ref a) => a.visit_with(visitor),
 981             ty::Predicate::Equate(ref binder) => binder.visit_with(visitor),
 982             ty::Predicate::Subtype(ref binder) => binder.visit_with(visitor),
 983             ty::Predicate::RegionOutlives(ref binder) => binder.visit_with(visitor),
 984             ty::Predicate::TypeOutlives(ref binder) => binder.visit_with(visitor),
 985             ty::Predicate::Projection(ref binder) => binder.visit_with(visitor),
 986             ty::Predicate::WellFormed(data) => data.visit_with(visitor),
 987             ty::Predicate::ClosureKind(_closure_def_id, _kind) => false,
 988             ty::Predicate::ObjectSafe(_trait_def_id) => false,
 989             ty::Predicate::ConstEvaluatable(_def_id, substs) => substs.visit_with(visitor),
 990         }
 991     }
 992 }
 993
 994 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionPredicate<'tcx> {
 995     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 996         ty::ProjectionPredicate {
 997             projection_ty: self.projection_ty.fold_with(folder),
 998             ty: self.ty.fold_with(folder),
 999         }
1000     }
1001
1002     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1003         self.projection_ty.visit_with(visitor) || self.ty.visit_with(visitor)
1004     }
1005 }
1006
1007 impl<'tcx> TypeFoldable<'tcx> for ty::ExistentialProjection<'tcx> {
1008     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1009         ty::ExistentialProjection {
1010             ty: self.ty.fold_with(folder),
1011             substs: self.substs.fold_with(folder),
1012             item_def_id: self.item_def_id,
1013         }
1014     }
1015
1016     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1017         self.substs.visit_with(visitor) || self.ty.visit_with(visitor)
1018     }
1019 }
1020
1021 impl<'tcx> TypeFoldable<'tcx> for ty::ProjectionTy<'tcx> {
1022     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1023         ty::ProjectionTy {
1024             substs: self.substs.fold_with(folder),
1025             item_def_id: self.item_def_id,
1026         }
1027     }
1028
1029     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1030         self.substs.visit_with(visitor)
1031     }
1032 }
1033
1034 impl<'tcx> TypeFoldable<'tcx> for ty::InstantiatedPredicates<'tcx> {
1035     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1036         ty::InstantiatedPredicates {
1037             predicates: self.predicates.fold_with(folder),
1038         }
1039     }
1040
1041     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1042         self.predicates.visit_with(visitor)
1043     }
1044 }
1045
1046 impl<'tcx> TypeFoldable<'tcx> for ty::EquatePredicate<'tcx> {
1047     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1048         ty::EquatePredicate(self.0.fold_with(folder), self.1.fold_with(folder))
1049     }
1050
1051     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1052         self.0.visit_with(visitor) || self.1.visit_with(visitor)
1053     }
1054 }
1055
1056 impl<'tcx> TypeFoldable<'tcx> for ty::SubtypePredicate<'tcx> {
1057     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1058         ty::SubtypePredicate {
1059             a_is_expected: self.a_is_expected,
1060             a: self.a.fold_with(folder),
1061             b: self.b.fold_with(folder)
1062         }
1063     }
1064
1065     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1066         self.a.visit_with(visitor) || self.b.visit_with(visitor)
1067     }
1068 }
1069
1070 impl<'tcx> TypeFoldable<'tcx> for ty::TraitPredicate<'tcx> {
1071     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1072         ty::TraitPredicate {
1073             trait_ref: self.trait_ref.fold_with(folder)
1074         }
1075     }
1076
1077     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1078         self.trait_ref.visit_with(visitor)
1079     }
1080 }
1081
1082 impl<'tcx,T,U> TypeFoldable<'tcx> for ty::OutlivesPredicate<T,U>
1083     where T : TypeFoldable<'tcx>,
1084           U : TypeFoldable<'tcx>,
1085 {
1086     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1087         ty::OutlivesPredicate(self.0.fold_with(folder),
1088                               self.1.fold_with(folder))
1089     }
1090
1091     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1092         self.0.visit_with(visitor) || self.1.visit_with(visitor)
1093     }
1094 }
1095
1096 impl<'tcx> TypeFoldable<'tcx> for ty::ClosureUpvar<'tcx> {
1097     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1098         ty::ClosureUpvar {
1099             def: self.def,
1100             span: self.span,
1101             ty: self.ty.fold_with(folder),
1102         }
1103     }
1104
1105     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1106         self.ty.visit_with(visitor)
1107     }
1108 }
1109
1110 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::error::ExpectedFound<T> {
1111     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1112         ty::error::ExpectedFound {
1113             expected: self.expected.fold_with(folder),
1114             found: self.found.fold_with(folder),
1115         }
1116     }
1117
1118     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1119         self.expected.visit_with(visitor) || self.found.visit_with(visitor)
1120     }
1121 }
1122
1123 impl<'tcx> TypeFoldable<'tcx> for type_variable::Default<'tcx> {
1124     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1125         type_variable::Default {
1126             ty: self.ty.fold_with(folder),
1127             origin_span: self.origin_span,
1128             def_id: self.def_id
1129         }
1130     }
1131
1132     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1133         self.ty.visit_with(visitor)
1134     }
1135 }
1136
1137 impl<'tcx, T: TypeFoldable<'tcx>, I: Idx> TypeFoldable<'tcx> for IndexVec<I, T> {
1138     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1139         self.iter().map(|x| x.fold_with(folder)).collect()
1140     }
1141
1142     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1143         self.iter().any(|t| t.visit_with(visitor))
1144     }
1145 }
1146
1147 impl<'tcx> TypeFoldable<'tcx> for ty::error::TypeError<'tcx> {
1148     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1149         use ty::error::TypeError::*;
1150
1151         match *self {
1152             Mismatch => Mismatch,
1153             UnsafetyMismatch(x) => UnsafetyMismatch(x.fold_with(folder)),
1154             AbiMismatch(x) => AbiMismatch(x.fold_with(folder)),
1155             Mutability => Mutability,
1156             TupleSize(x) => TupleSize(x),
1157             FixedArraySize(x) => FixedArraySize(x),
1158             ArgCount => ArgCount,
1159             RegionsDoesNotOutlive(a, b) => {
1160                 RegionsDoesNotOutlive(a.fold_with(folder), b.fold_with(folder))
1161             },
1162             RegionsInsufficientlyPolymorphic(a, b) => {
1163                 RegionsInsufficientlyPolymorphic(a, b.fold_with(folder))
1164             },
1165             RegionsOverlyPolymorphic(a, b) => {
1166                 RegionsOverlyPolymorphic(a, b.fold_with(folder))
1167             },
1168             IntMismatch(x) => IntMismatch(x),
1169             FloatMismatch(x) => FloatMismatch(x),
1170             Traits(x) => Traits(x),
1171             VariadicMismatch(x) => VariadicMismatch(x),
1172             CyclicTy => CyclicTy,
1173             ProjectionMismatched(x) => ProjectionMismatched(x),
1174             ProjectionBoundsLength(x) => ProjectionBoundsLength(x),
1175             Sorts(x) => Sorts(x.fold_with(folder)),
1176             TyParamDefaultMismatch(ref x) => TyParamDefaultMismatch(x.fold_with(folder)),
1177             ExistentialMismatch(x) => ExistentialMismatch(x.fold_with(folder)),
1178             OldStyleLUB(ref x) => OldStyleLUB(x.fold_with(folder)),
1179         }
1180     }
1181
1182     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1183         use ty::error::TypeError::*;
1184
1185         match *self {
1186             UnsafetyMismatch(x) => x.visit_with(visitor),
1187             AbiMismatch(x) => x.visit_with(visitor),
1188             RegionsDoesNotOutlive(a, b) => {
1189                 a.visit_with(visitor) || b.visit_with(visitor)
1190             },
1191             RegionsInsufficientlyPolymorphic(_, b) |
1192             RegionsOverlyPolymorphic(_, b) => {
1193                 b.visit_with(visitor)
1194             },
1195             Sorts(x) => x.visit_with(visitor),
1196             OldStyleLUB(ref x) => x.visit_with(visitor),
1197             TyParamDefaultMismatch(ref x) => x.visit_with(visitor),
1198             ExistentialMismatch(x) => x.visit_with(visitor),
1199             Mismatch |
1200             Mutability |
1201             TupleSize(_) |
1202             FixedArraySize(_) |
1203             ArgCount |
1204             IntMismatch(_) |
1205             FloatMismatch(_) |
1206             Traits(_) |
1207             VariadicMismatch(_) |
1208             CyclicTy |
1209             ProjectionMismatched(_) |
1210             ProjectionBoundsLength(_) => false,
1211         }
1212     }
1213 }
1214
1215 impl<'tcx> TypeFoldable<'tcx> for ConstVal<'tcx> {
1216     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1217         match *self {
1218             ConstVal::Integral(i) => ConstVal::Integral(i),
1219             ConstVal::Float(f) => ConstVal::Float(f),
1220             ConstVal::Str(s) => ConstVal::Str(s),
1221             ConstVal::ByteStr(b) => ConstVal::ByteStr(b),
1222             ConstVal::Bool(b) => ConstVal::Bool(b),
1223             ConstVal::Char(c) => ConstVal::Char(c),
1224             ConstVal::Variant(def_id) => ConstVal::Variant(def_id),
1225             ConstVal::Function(def_id, substs) => {
1226                 ConstVal::Function(def_id, substs.fold_with(folder))
1227             }
1228             ConstVal::Aggregate(ConstAggregate::Struct(fields)) => {
1229                 let new_fields: Vec<_> = fields.iter().map(|&(name, v)| {
1230                     (name, v.fold_with(folder))
1231                 }).collect();
1232                 let fields = if new_fields == fields {
1233                     fields
1234                 } else {
1235                     folder.tcx().alloc_name_const_slice(&new_fields)
1236                 };
1237                 ConstVal::Aggregate(ConstAggregate::Struct(fields))
1238             }
1239             ConstVal::Aggregate(ConstAggregate::Tuple(fields)) => {
1240                 let new_fields: Vec<_> = fields.iter().map(|v| {
1241                     v.fold_with(folder)
1242                 }).collect();
1243                 let fields = if new_fields == fields {
1244                     fields
1245                 } else {
1246                     folder.tcx().alloc_const_slice(&new_fields)
1247                 };
1248                 ConstVal::Aggregate(ConstAggregate::Tuple(fields))
1249             }
1250             ConstVal::Aggregate(ConstAggregate::Array(fields)) => {
1251                 let new_fields: Vec<_> = fields.iter().map(|v| {
1252                     v.fold_with(folder)
1253                 }).collect();
1254                 let fields = if new_fields == fields {
1255                     fields
1256                 } else {
1257                     folder.tcx().alloc_const_slice(&new_fields)
1258                 };
1259                 ConstVal::Aggregate(ConstAggregate::Array(fields))
1260             }
1261             ConstVal::Aggregate(ConstAggregate::Repeat(v, count)) => {
1262                 let v = v.fold_with(folder);
1263                 ConstVal::Aggregate(ConstAggregate::Repeat(v, count))
1264             }
1265             ConstVal::Unevaluated(def_id, substs) => {
1266                 ConstVal::Unevaluated(def_id, substs.fold_with(folder))
1267             }
1268         }
1269     }
1270
1271     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1272         match *self {
1273             ConstVal::Integral(_) |
1274             ConstVal::Float(_) |
1275             ConstVal::Str(_) |
1276             ConstVal::ByteStr(_) |
1277             ConstVal::Bool(_) |
1278             ConstVal::Char(_) |
1279             ConstVal::Variant(_) => false,
1280             ConstVal::Function(_, substs) => substs.visit_with(visitor),
1281             ConstVal::Aggregate(ConstAggregate::Struct(fields)) => {
1282                 fields.iter().any(|&(_, v)| v.visit_with(visitor))
1283             }
1284             ConstVal::Aggregate(ConstAggregate::Tuple(fields)) |
1285             ConstVal::Aggregate(ConstAggregate::Array(fields)) => {
1286                 fields.iter().any(|v| v.visit_with(visitor))
1287             }
1288             ConstVal::Aggregate(ConstAggregate::Repeat(v, _)) => {
1289                 v.visit_with(visitor)
1290             }
1291             ConstVal::Unevaluated(_, substs) => substs.visit_with(visitor),
1292         }
1293     }
1294 }
1295
1296 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Const<'tcx> {
1297     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1298         let ty = self.ty.fold_with(folder);
1299         let val = self.val.fold_with(folder);
1300         folder.tcx().mk_const(ty::Const {
1301             ty,
1302             val
1303         })
1304     }
1305
1306     fn fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
1307         folder.fold_const(*self)
1308     }
1309
1310     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1311         self.ty.visit_with(visitor) || self.val.visit_with(visitor)
1312     }
1313
1314     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
1315         visitor.visit_const(self)
1316     }
1317 }