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