src/librustc/ty/structural_impls.rs

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