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