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