compiler/rustc_middle/src/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 and proc-macros to help with the tedium.
   4
   5 use crate::mir::interpret;
   6 use crate::mir::ProjectionKind;
   7 use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
   8 use crate::ty::print::{with_no_trimmed_paths, FmtPrinter, Printer};
   9 use crate::ty::{self, InferConst, Lift, Ty, TyCtxt};
  10 use rustc_data_structures::functor::IdFunctor;
  11 use rustc_hir as hir;
  12 use rustc_hir::def::Namespace;
  13 use rustc_hir::def_id::CRATE_DEF_INDEX;
  14 use rustc_index::vec::{Idx, IndexVec};
  15
  16 use std::fmt;
  17 use std::ops::ControlFlow;
  18 use std::rc::Rc;
  19 use std::sync::Arc;
  20
  21 impl fmt::Debug for ty::TraitDef {
  22     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  23         ty::tls::with(|tcx| {
  24             with_no_trimmed_paths(|| {
  25                 FmtPrinter::new(tcx, f, Namespace::TypeNS).print_def_path(self.def_id, &[])
  26             })?;
  27             Ok(())
  28         })
  29     }
  30 }
  31
  32 impl fmt::Debug for ty::AdtDef {
  33     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  34         ty::tls::with(|tcx| {
  35             with_no_trimmed_paths(|| {
  36                 FmtPrinter::new(tcx, f, Namespace::TypeNS).print_def_path(self.did, &[])
  37             })?;
  38             Ok(())
  39         })
  40     }
  41 }
  42
  43 impl fmt::Debug for ty::UpvarId {
  44     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  45         let name = ty::tls::with(|tcx| tcx.hir().name(self.var_path.hir_id));
  46         write!(f, "UpvarId({:?};`{}`;{:?})", self.var_path.hir_id, name, self.closure_expr_id)
  47     }
  48 }
  49
  50 impl fmt::Debug for ty::UpvarBorrow<'tcx> {
  51     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  52         write!(f, "UpvarBorrow({:?}, {:?})", self.kind, self.region)
  53     }
  54 }
  55
  56 impl fmt::Debug for ty::ExistentialTraitRef<'tcx> {
  57     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  58         with_no_trimmed_paths(|| fmt::Display::fmt(self, f))
  59     }
  60 }
  61
  62 impl fmt::Debug for ty::adjustment::Adjustment<'tcx> {
  63     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  64         write!(f, "{:?} -> {}", self.kind, self.target)
  65     }
  66 }
  67
  68 impl fmt::Debug for ty::BoundRegionKind {
  69     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  70         match *self {
  71             ty::BrAnon(n) => write!(f, "BrAnon({:?})", n),
  72             ty::BrNamed(did, name) => {
  73                 if did.index == CRATE_DEF_INDEX {
  74                     write!(f, "BrNamed({})", name)
  75                 } else {
  76                     write!(f, "BrNamed({:?}, {})", did, name)
  77                 }
  78             }
  79             ty::BrEnv => write!(f, "BrEnv"),
  80         }
  81     }
  82 }
  83
  84 impl fmt::Debug for ty::RegionKind {
  85     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  86         match *self {
  87             ty::ReEarlyBound(ref data) => write!(f, "ReEarlyBound({}, {})", data.index, data.name),
  88
  89             ty::ReLateBound(binder_id, ref bound_region) => {
  90                 write!(f, "ReLateBound({:?}, {:?})", binder_id, bound_region)
  91             }
  92
  93             ty::ReFree(ref fr) => fr.fmt(f),
  94
  95             ty::ReStatic => write!(f, "ReStatic"),
  96
  97             ty::ReVar(ref vid) => vid.fmt(f),
  98
  99             ty::RePlaceholder(placeholder) => write!(f, "RePlaceholder({:?})", placeholder),
 100
 101             ty::ReEmpty(ui) => write!(f, "ReEmpty({:?})", ui),
 102
 103             ty::ReErased => write!(f, "ReErased"),
 104         }
 105     }
 106 }
 107
 108 impl fmt::Debug for ty::FreeRegion {
 109     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 110         write!(f, "ReFree({:?}, {:?})", self.scope, self.bound_region)
 111     }
 112 }
 113
 114 impl fmt::Debug for ty::Variance {
 115     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 116         f.write_str(match *self {
 117             ty::Covariant => "+",
 118             ty::Contravariant => "-",
 119             ty::Invariant => "o",
 120             ty::Bivariant => "*",
 121         })
 122     }
 123 }
 124
 125 impl fmt::Debug for ty::FnSig<'tcx> {
 126     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 127         write!(f, "({:?}; c_variadic: {})->{:?}", self.inputs(), self.c_variadic, self.output())
 128     }
 129 }
 130
 131 impl fmt::Debug for ty::TyVid {
 132     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 133         write!(f, "_#{}t", self.index)
 134     }
 135 }
 136
 137 impl<'tcx> fmt::Debug for ty::ConstVid<'tcx> {
 138     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 139         write!(f, "_#{}c", self.index)
 140     }
 141 }
 142
 143 impl fmt::Debug for ty::IntVid {
 144     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 145         write!(f, "_#{}i", self.index)
 146     }
 147 }
 148
 149 impl fmt::Debug for ty::FloatVid {
 150     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 151         write!(f, "_#{}f", self.index)
 152     }
 153 }
 154
 155 impl fmt::Debug for ty::RegionVid {
 156     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 157         write!(f, "'_#{}r", self.index())
 158     }
 159 }
 160
 161 impl fmt::Debug for ty::InferTy {
 162     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 163         match *self {
 164             ty::TyVar(ref v) => v.fmt(f),
 165             ty::IntVar(ref v) => v.fmt(f),
 166             ty::FloatVar(ref v) => v.fmt(f),
 167             ty::FreshTy(v) => write!(f, "FreshTy({:?})", v),
 168             ty::FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
 169             ty::FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v),
 170         }
 171     }
 172 }
 173
 174 impl fmt::Debug for ty::IntVarValue {
 175     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 176         match *self {
 177             ty::IntType(ref v) => v.fmt(f),
 178             ty::UintType(ref v) => v.fmt(f),
 179         }
 180     }
 181 }
 182
 183 impl fmt::Debug for ty::FloatVarValue {
 184     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 185         self.0.fmt(f)
 186     }
 187 }
 188
 189 impl fmt::Debug for ty::TraitRef<'tcx> {
 190     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 191         with_no_trimmed_paths(|| fmt::Display::fmt(self, f))
 192     }
 193 }
 194
 195 impl fmt::Debug for Ty<'tcx> {
 196     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 197         with_no_trimmed_paths(|| fmt::Display::fmt(self, f))
 198     }
 199 }
 200
 201 impl fmt::Debug for ty::ParamTy {
 202     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 203         write!(f, "{}/#{}", self.name, self.index)
 204     }
 205 }
 206
 207 impl fmt::Debug for ty::ParamConst {
 208     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 209         write!(f, "{}/#{}", self.name, self.index)
 210     }
 211 }
 212
 213 impl fmt::Debug for ty::TraitPredicate<'tcx> {
 214     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 215         write!(f, "TraitPredicate({:?})", self.trait_ref)
 216     }
 217 }
 218
 219 impl fmt::Debug for ty::ProjectionPredicate<'tcx> {
 220     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 221         write!(f, "ProjectionPredicate({:?}, {:?})", self.projection_ty, self.ty)
 222     }
 223 }
 224
 225 impl fmt::Debug for ty::Predicate<'tcx> {
 226     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 227         write!(f, "{:?}", self.kind())
 228     }
 229 }
 230
 231 impl fmt::Debug for ty::PredicateKind<'tcx> {
 232     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 233         match *self {
 234             ty::PredicateKind::ForAll(binder) => write!(f, "ForAll({:?})", binder),
 235             ty::PredicateKind::Atom(atom) => write!(f, "{:?}", atom),
 236         }
 237     }
 238 }
 239
 240 impl fmt::Debug for ty::PredicateAtom<'tcx> {
 241     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 242         match *self {
 243             ty::PredicateAtom::Trait(ref a, constness) => {
 244                 if let hir::Constness::Const = constness {
 245                     write!(f, "const ")?;
 246                 }
 247                 a.fmt(f)
 248             }
 249             ty::PredicateAtom::Subtype(ref pair) => pair.fmt(f),
 250             ty::PredicateAtom::RegionOutlives(ref pair) => pair.fmt(f),
 251             ty::PredicateAtom::TypeOutlives(ref pair) => pair.fmt(f),
 252             ty::PredicateAtom::Projection(ref pair) => pair.fmt(f),
 253             ty::PredicateAtom::WellFormed(data) => write!(f, "WellFormed({:?})", data),
 254             ty::PredicateAtom::ObjectSafe(trait_def_id) => {
 255                 write!(f, "ObjectSafe({:?})", trait_def_id)
 256             }
 257             ty::PredicateAtom::ClosureKind(closure_def_id, closure_substs, kind) => {
 258                 write!(f, "ClosureKind({:?}, {:?}, {:?})", closure_def_id, closure_substs, kind)
 259             }
 260             ty::PredicateAtom::ConstEvaluatable(def_id, substs) => {
 261                 write!(f, "ConstEvaluatable({:?}, {:?})", def_id, substs)
 262             }
 263             ty::PredicateAtom::ConstEquate(c1, c2) => write!(f, "ConstEquate({:?}, {:?})", c1, c2),
 264             ty::PredicateAtom::TypeWellFormedFromEnv(ty) => {
 265                 write!(f, "TypeWellFormedFromEnv({:?})", ty)
 266             }
 267         }
 268     }
 269 }
 270
 271 ///////////////////////////////////////////////////////////////////////////
 272 // Atomic structs
 273 //
 274 // For things that don't carry any arena-allocated data (and are
 275 // copy...), just add them to this list.
 276
 277 TrivialTypeFoldableAndLiftImpls! {
 278     (),
 279     bool,
 280     usize,
 281     ::rustc_target::abi::VariantIdx,
 282     u32,
 283     u64,
 284     String,
 285     crate::middle::region::Scope,
 286     ::rustc_ast::FloatTy,
 287     ::rustc_ast::InlineAsmOptions,
 288     ::rustc_ast::InlineAsmTemplatePiece,
 289     ::rustc_ast::NodeId,
 290     ::rustc_span::symbol::Symbol,
 291     ::rustc_hir::def::Res,
 292     ::rustc_hir::def_id::DefId,
 293     ::rustc_hir::def_id::LocalDefId,
 294     ::rustc_hir::HirId,
 295     ::rustc_hir::LlvmInlineAsmInner,
 296     ::rustc_hir::MatchSource,
 297     ::rustc_hir::Mutability,
 298     ::rustc_hir::Unsafety,
 299     ::rustc_target::asm::InlineAsmRegOrRegClass,
 300     ::rustc_target::spec::abi::Abi,
 301     crate::mir::coverage::ExpressionOperandId,
 302     crate::mir::coverage::CounterValueReference,
 303     crate::mir::coverage::InjectedExpressionId,
 304     crate::mir::coverage::InjectedExpressionIndex,
 305     crate::mir::coverage::MappedExpressionIndex,
 306     crate::mir::Local,
 307     crate::mir::Promoted,
 308     crate::traits::Reveal,
 309     crate::ty::adjustment::AutoBorrowMutability,
 310     crate::ty::AdtKind,
 311     // Including `BoundRegionKind` is a *bit* dubious, but direct
 312     // references to bound region appear in `ty::Error`, and aren't
 313     // really meant to be folded. In general, we can only fold a fully
 314     // general `Region`.
 315     crate::ty::BoundRegionKind,
 316     crate::ty::AssocItem,
 317     crate::ty::Placeholder<crate::ty::BoundRegionKind>,
 318     crate::ty::ClosureKind,
 319     crate::ty::FreeRegion,
 320     crate::ty::InferTy,
 321     crate::ty::IntVarValue,
 322     crate::ty::ParamConst,
 323     crate::ty::ParamTy,
 324     crate::ty::adjustment::PointerCast,
 325     crate::ty::RegionVid,
 326     crate::ty::UniverseIndex,
 327     crate::ty::Variance,
 328     ::rustc_span::Span,
 329 }
 330
 331 ///////////////////////////////////////////////////////////////////////////
 332 // Lift implementations
 333
 334 // FIXME(eddyb) replace all the uses of `Option::map` with `?`.
 335 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>> Lift<'tcx> for (A, B) {
 336     type Lifted = (A::Lifted, B::Lifted);
 337     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 338         Some((tcx.lift(self.0)?, tcx.lift(self.1)?))
 339     }
 340 }
 341
 342 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>, C: Lift<'tcx>> Lift<'tcx> for (A, B, C) {
 343     type Lifted = (A::Lifted, B::Lifted, C::Lifted);
 344     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 345         Some((tcx.lift(self.0)?, tcx.lift(self.1)?, tcx.lift(self.2)?))
 346     }
 347 }
 348
 349 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Option<T> {
 350     type Lifted = Option<T::Lifted>;
 351     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 352         match self {
 353             Some(x) => tcx.lift(x).map(Some),
 354             None => Some(None),
 355         }
 356     }
 357 }
 358
 359 impl<'tcx, T: Lift<'tcx>, E: Lift<'tcx>> Lift<'tcx> for Result<T, E> {
 360     type Lifted = Result<T::Lifted, E::Lifted>;
 361     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 362         match self {
 363             Ok(x) => tcx.lift(x).map(Ok),
 364             Err(e) => tcx.lift(e).map(Err),
 365         }
 366     }
 367 }
 368
 369 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Box<T> {
 370     type Lifted = Box<T::Lifted>;
 371     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 372         tcx.lift(*self).map(Box::new)
 373     }
 374 }
 375
 376 impl<'tcx, T: Lift<'tcx> + Clone> Lift<'tcx> for Rc<T> {
 377     type Lifted = Rc<T::Lifted>;
 378     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 379         tcx.lift(self.as_ref().clone()).map(Rc::new)
 380     }
 381 }
 382
 383 impl<'tcx, T: Lift<'tcx> + Clone> Lift<'tcx> for Arc<T> {
 384     type Lifted = Arc<T::Lifted>;
 385     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 386         tcx.lift(self.as_ref().clone()).map(Arc::new)
 387     }
 388 }
 389 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Vec<T> {
 390     type Lifted = Vec<T::Lifted>;
 391     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 392         self.into_iter().map(|v| tcx.lift(v)).collect()
 393     }
 394 }
 395
 396 impl<'tcx, I: Idx, T: Lift<'tcx>> Lift<'tcx> for IndexVec<I, T> {
 397     type Lifted = IndexVec<I, T::Lifted>;
 398     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 399         self.into_iter().map(|e| tcx.lift(e)).collect()
 400     }
 401 }
 402
 403 impl<'a, 'tcx> Lift<'tcx> for ty::TraitRef<'a> {
 404     type Lifted = ty::TraitRef<'tcx>;
 405     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 406         tcx.lift(self.substs).map(|substs| ty::TraitRef { def_id: self.def_id, substs })
 407     }
 408 }
 409
 410 impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialTraitRef<'a> {
 411     type Lifted = ty::ExistentialTraitRef<'tcx>;
 412     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 413         tcx.lift(self.substs).map(|substs| ty::ExistentialTraitRef { def_id: self.def_id, substs })
 414     }
 415 }
 416
 417 impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialPredicate<'a> {
 418     type Lifted = ty::ExistentialPredicate<'tcx>;
 419     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 420         match self {
 421             ty::ExistentialPredicate::Trait(x) => tcx.lift(x).map(ty::ExistentialPredicate::Trait),
 422             ty::ExistentialPredicate::Projection(x) => {
 423                 tcx.lift(x).map(ty::ExistentialPredicate::Projection)
 424             }
 425             ty::ExistentialPredicate::AutoTrait(def_id) => {
 426                 Some(ty::ExistentialPredicate::AutoTrait(def_id))
 427             }
 428         }
 429     }
 430 }
 431
 432 impl<'a, 'tcx> Lift<'tcx> for ty::TraitPredicate<'a> {
 433     type Lifted = ty::TraitPredicate<'tcx>;
 434     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<ty::TraitPredicate<'tcx>> {
 435         tcx.lift(self.trait_ref).map(|trait_ref| ty::TraitPredicate { trait_ref })
 436     }
 437 }
 438
 439 impl<'a, 'tcx> Lift<'tcx> for ty::SubtypePredicate<'a> {
 440     type Lifted = ty::SubtypePredicate<'tcx>;
 441     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<ty::SubtypePredicate<'tcx>> {
 442         tcx.lift((self.a, self.b)).map(|(a, b)| ty::SubtypePredicate {
 443             a_is_expected: self.a_is_expected,
 444             a,
 445             b,
 446         })
 447     }
 448 }
 449
 450 impl<'tcx, A: Copy + Lift<'tcx>, B: Copy + Lift<'tcx>> Lift<'tcx> for ty::OutlivesPredicate<A, B> {
 451     type Lifted = ty::OutlivesPredicate<A::Lifted, B::Lifted>;
 452     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 453         tcx.lift((self.0, self.1)).map(|(a, b)| ty::OutlivesPredicate(a, b))
 454     }
 455 }
 456
 457 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionTy<'a> {
 458     type Lifted = ty::ProjectionTy<'tcx>;
 459     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<ty::ProjectionTy<'tcx>> {
 460         tcx.lift(self.substs)
 461             .map(|substs| ty::ProjectionTy { item_def_id: self.item_def_id, substs })
 462     }
 463 }
 464
 465 impl<'a, 'tcx> Lift<'tcx> for ty::ProjectionPredicate<'a> {
 466     type Lifted = ty::ProjectionPredicate<'tcx>;
 467     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<ty::ProjectionPredicate<'tcx>> {
 468         tcx.lift((self.projection_ty, self.ty))
 469             .map(|(projection_ty, ty)| ty::ProjectionPredicate { projection_ty, ty })
 470     }
 471 }
 472
 473 impl<'a, 'tcx> Lift<'tcx> for ty::ExistentialProjection<'a> {
 474     type Lifted = ty::ExistentialProjection<'tcx>;
 475     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 476         tcx.lift(self.substs).map(|substs| ty::ExistentialProjection {
 477             substs,
 478             ty: tcx.lift(self.ty).expect("type must lift when substs do"),
 479             item_def_id: self.item_def_id,
 480         })
 481     }
 482 }
 483
 484 impl<'a, 'tcx> Lift<'tcx> for ty::PredicateKind<'a> {
 485     type Lifted = ty::PredicateKind<'tcx>;
 486     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 487         match self {
 488             ty::PredicateKind::ForAll(binder) => tcx.lift(binder).map(ty::PredicateKind::ForAll),
 489             ty::PredicateKind::Atom(atom) => tcx.lift(atom).map(ty::PredicateKind::Atom),
 490         }
 491     }
 492 }
 493
 494 impl<'a, 'tcx> Lift<'tcx> for ty::PredicateAtom<'a> {
 495     type Lifted = ty::PredicateAtom<'tcx>;
 496     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 497         match self {
 498             ty::PredicateAtom::Trait(data, constness) => {
 499                 tcx.lift(data).map(|data| ty::PredicateAtom::Trait(data, constness))
 500             }
 501             ty::PredicateAtom::Subtype(data) => tcx.lift(data).map(ty::PredicateAtom::Subtype),
 502             ty::PredicateAtom::RegionOutlives(data) => {
 503                 tcx.lift(data).map(ty::PredicateAtom::RegionOutlives)
 504             }
 505             ty::PredicateAtom::TypeOutlives(data) => {
 506                 tcx.lift(data).map(ty::PredicateAtom::TypeOutlives)
 507             }
 508             ty::PredicateAtom::Projection(data) => {
 509                 tcx.lift(data).map(ty::PredicateAtom::Projection)
 510             }
 511             ty::PredicateAtom::WellFormed(ty) => tcx.lift(ty).map(ty::PredicateAtom::WellFormed),
 512             ty::PredicateAtom::ClosureKind(closure_def_id, closure_substs, kind) => {
 513                 tcx.lift(closure_substs).map(|closure_substs| {
 514                     ty::PredicateAtom::ClosureKind(closure_def_id, closure_substs, kind)
 515                 })
 516             }
 517             ty::PredicateAtom::ObjectSafe(trait_def_id) => {
 518                 Some(ty::PredicateAtom::ObjectSafe(trait_def_id))
 519             }
 520             ty::PredicateAtom::ConstEvaluatable(def_id, substs) => {
 521                 tcx.lift(substs).map(|substs| ty::PredicateAtom::ConstEvaluatable(def_id, substs))
 522             }
 523             ty::PredicateAtom::ConstEquate(c1, c2) => {
 524                 tcx.lift((c1, c2)).map(|(c1, c2)| ty::PredicateAtom::ConstEquate(c1, c2))
 525             }
 526             ty::PredicateAtom::TypeWellFormedFromEnv(ty) => {
 527                 tcx.lift(ty).map(ty::PredicateAtom::TypeWellFormedFromEnv)
 528             }
 529         }
 530     }
 531 }
 532
 533 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::Binder<T> {
 534     type Lifted = ty::Binder<T::Lifted>;
 535     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 536         self.map_bound(|v| tcx.lift(v)).transpose()
 537     }
 538 }
 539
 540 impl<'a, 'tcx> Lift<'tcx> for ty::ParamEnv<'a> {
 541     type Lifted = ty::ParamEnv<'tcx>;
 542     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 543         tcx.lift(self.caller_bounds())
 544             .map(|caller_bounds| ty::ParamEnv::new(caller_bounds, self.reveal()))
 545     }
 546 }
 547
 548 impl<'a, 'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::ParamEnvAnd<'a, T> {
 549     type Lifted = ty::ParamEnvAnd<'tcx, T::Lifted>;
 550     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 551         tcx.lift(self.param_env).and_then(|param_env| {
 552             tcx.lift(self.value).map(|value| ty::ParamEnvAnd { param_env, value })
 553         })
 554     }
 555 }
 556
 557 impl<'a, 'tcx> Lift<'tcx> for ty::ClosureSubsts<'a> {
 558     type Lifted = ty::ClosureSubsts<'tcx>;
 559     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 560         tcx.lift(self.substs).map(|substs| ty::ClosureSubsts { substs })
 561     }
 562 }
 563
 564 impl<'a, 'tcx> Lift<'tcx> for ty::GeneratorSubsts<'a> {
 565     type Lifted = ty::GeneratorSubsts<'tcx>;
 566     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 567         tcx.lift(self.substs).map(|substs| ty::GeneratorSubsts { substs })
 568     }
 569 }
 570
 571 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::Adjustment<'a> {
 572     type Lifted = ty::adjustment::Adjustment<'tcx>;
 573     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 574         let ty::adjustment::Adjustment { kind, target } = self;
 575         tcx.lift(kind).and_then(|kind| {
 576             tcx.lift(target).map(|target| ty::adjustment::Adjustment { kind, target })
 577         })
 578     }
 579 }
 580
 581 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::Adjust<'a> {
 582     type Lifted = ty::adjustment::Adjust<'tcx>;
 583     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 584         match self {
 585             ty::adjustment::Adjust::NeverToAny => Some(ty::adjustment::Adjust::NeverToAny),
 586             ty::adjustment::Adjust::Pointer(ptr) => Some(ty::adjustment::Adjust::Pointer(ptr)),
 587             ty::adjustment::Adjust::Deref(overloaded) => {
 588                 tcx.lift(overloaded).map(ty::adjustment::Adjust::Deref)
 589             }
 590             ty::adjustment::Adjust::Borrow(autoref) => {
 591                 tcx.lift(autoref).map(ty::adjustment::Adjust::Borrow)
 592             }
 593         }
 594     }
 595 }
 596
 597 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::OverloadedDeref<'a> {
 598     type Lifted = ty::adjustment::OverloadedDeref<'tcx>;
 599     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 600         tcx.lift(self.region).map(|region| ty::adjustment::OverloadedDeref {
 601             region,
 602             mutbl: self.mutbl,
 603             span: self.span,
 604         })
 605     }
 606 }
 607
 608 impl<'a, 'tcx> Lift<'tcx> for ty::adjustment::AutoBorrow<'a> {
 609     type Lifted = ty::adjustment::AutoBorrow<'tcx>;
 610     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 611         match self {
 612             ty::adjustment::AutoBorrow::Ref(r, m) => {
 613                 tcx.lift(r).map(|r| ty::adjustment::AutoBorrow::Ref(r, m))
 614             }
 615             ty::adjustment::AutoBorrow::RawPtr(m) => Some(ty::adjustment::AutoBorrow::RawPtr(m)),
 616         }
 617     }
 618 }
 619
 620 impl<'a, 'tcx> Lift<'tcx> for ty::GenSig<'a> {
 621     type Lifted = ty::GenSig<'tcx>;
 622     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 623         tcx.lift((self.resume_ty, self.yield_ty, self.return_ty))
 624             .map(|(resume_ty, yield_ty, return_ty)| ty::GenSig { resume_ty, yield_ty, return_ty })
 625     }
 626 }
 627
 628 impl<'a, 'tcx> Lift<'tcx> for ty::FnSig<'a> {
 629     type Lifted = ty::FnSig<'tcx>;
 630     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 631         tcx.lift(self.inputs_and_output).map(|x| ty::FnSig {
 632             inputs_and_output: x,
 633             c_variadic: self.c_variadic,
 634             unsafety: self.unsafety,
 635             abi: self.abi,
 636         })
 637     }
 638 }
 639
 640 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for ty::error::ExpectedFound<T> {
 641     type Lifted = ty::error::ExpectedFound<T::Lifted>;
 642     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 643         let ty::error::ExpectedFound { expected, found } = self;
 644         tcx.lift(expected).and_then(|expected| {
 645             tcx.lift(found).map(|found| ty::error::ExpectedFound { expected, found })
 646         })
 647     }
 648 }
 649
 650 impl<'a, 'tcx> Lift<'tcx> for ty::error::TypeError<'a> {
 651     type Lifted = ty::error::TypeError<'tcx>;
 652     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 653         use crate::ty::error::TypeError::*;
 654
 655         Some(match self {
 656             Mismatch => Mismatch,
 657             UnsafetyMismatch(x) => UnsafetyMismatch(x),
 658             AbiMismatch(x) => AbiMismatch(x),
 659             Mutability => Mutability,
 660             TupleSize(x) => TupleSize(x),
 661             FixedArraySize(x) => FixedArraySize(x),
 662             ArgCount => ArgCount,
 663             RegionsDoesNotOutlive(a, b) => {
 664                 return tcx.lift((a, b)).map(|(a, b)| RegionsDoesNotOutlive(a, b));
 665             }
 666             RegionsInsufficientlyPolymorphic(a, b) => {
 667                 return tcx.lift(b).map(|b| RegionsInsufficientlyPolymorphic(a, b));
 668             }
 669             RegionsOverlyPolymorphic(a, b) => {
 670                 return tcx.lift(b).map(|b| RegionsOverlyPolymorphic(a, b));
 671             }
 672             RegionsPlaceholderMismatch => RegionsPlaceholderMismatch,
 673             IntMismatch(x) => IntMismatch(x),
 674             FloatMismatch(x) => FloatMismatch(x),
 675             Traits(x) => Traits(x),
 676             VariadicMismatch(x) => VariadicMismatch(x),
 677             CyclicTy(t) => return tcx.lift(t).map(|t| CyclicTy(t)),
 678             CyclicConst(ct) => return tcx.lift(ct).map(|ct| CyclicConst(ct)),
 679             ProjectionMismatched(x) => ProjectionMismatched(x),
 680             Sorts(x) => return tcx.lift(x).map(Sorts),
 681             ExistentialMismatch(x) => return tcx.lift(x).map(ExistentialMismatch),
 682             ConstMismatch(x) => return tcx.lift(x).map(ConstMismatch),
 683             IntrinsicCast => IntrinsicCast,
 684             TargetFeatureCast(x) => TargetFeatureCast(x),
 685             ObjectUnsafeCoercion(x) => return tcx.lift(x).map(ObjectUnsafeCoercion),
 686         })
 687     }
 688 }
 689
 690 impl<'a, 'tcx> Lift<'tcx> for ty::InstanceDef<'a> {
 691     type Lifted = ty::InstanceDef<'tcx>;
 692     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 693         match self {
 694             ty::InstanceDef::Item(def_id) => Some(ty::InstanceDef::Item(def_id)),
 695             ty::InstanceDef::VtableShim(def_id) => Some(ty::InstanceDef::VtableShim(def_id)),
 696             ty::InstanceDef::ReifyShim(def_id) => Some(ty::InstanceDef::ReifyShim(def_id)),
 697             ty::InstanceDef::Intrinsic(def_id) => Some(ty::InstanceDef::Intrinsic(def_id)),
 698             ty::InstanceDef::FnPtrShim(def_id, ty) => {
 699                 Some(ty::InstanceDef::FnPtrShim(def_id, tcx.lift(ty)?))
 700             }
 701             ty::InstanceDef::Virtual(def_id, n) => Some(ty::InstanceDef::Virtual(def_id, n)),
 702             ty::InstanceDef::ClosureOnceShim { call_once } => {
 703                 Some(ty::InstanceDef::ClosureOnceShim { call_once })
 704             }
 705             ty::InstanceDef::DropGlue(def_id, ty) => {
 706                 Some(ty::InstanceDef::DropGlue(def_id, tcx.lift(ty)?))
 707             }
 708             ty::InstanceDef::CloneShim(def_id, ty) => {
 709                 Some(ty::InstanceDef::CloneShim(def_id, tcx.lift(ty)?))
 710             }
 711         }
 712     }
 713 }
 714
 715 ///////////////////////////////////////////////////////////////////////////
 716 // TypeFoldable implementations.
 717 //
 718 // Ideally, each type should invoke `folder.fold_foo(self)` and
 719 // nothing else. In some cases, though, we haven't gotten around to
 720 // adding methods on the `folder` yet, and thus the folding is
 721 // hard-coded here. This is less-flexible, because folders cannot
 722 // override the behavior, but there are a lot of random types and one
 723 // can easily refactor the folding into the TypeFolder trait as
 724 // needed.
 725
 726 /// AdtDefs are basically the same as a DefId.
 727 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::AdtDef {
 728     fn super_fold_with<F: TypeFolder<'tcx>>(self, _folder: &mut F) -> Self {
 729         self
 730     }
 731
 732     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> ControlFlow<V::BreakTy> {
 733         ControlFlow::CONTINUE
 734     }
 735 }
 736
 737 impl<'tcx, T: TypeFoldable<'tcx>, U: TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
 738     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> (T, U) {
 739         (self.0.fold_with(folder), self.1.fold_with(folder))
 740     }
 741
 742     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 743         self.0.visit_with(visitor)?;
 744         self.1.visit_with(visitor)
 745     }
 746 }
 747
 748 impl<'tcx, A: TypeFoldable<'tcx>, B: TypeFoldable<'tcx>, C: TypeFoldable<'tcx>> TypeFoldable<'tcx>
 749     for (A, B, C)
 750 {
 751     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> (A, B, C) {
 752         (self.0.fold_with(folder), self.1.fold_with(folder), self.2.fold_with(folder))
 753     }
 754
 755     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 756         self.0.visit_with(visitor)?;
 757         self.1.visit_with(visitor)?;
 758         self.2.visit_with(visitor)
 759     }
 760 }
 761
 762 EnumTypeFoldableImpl! {
 763     impl<'tcx, T> TypeFoldable<'tcx> for Option<T> {
 764         (Some)(a),
 765         (None),
 766     } where T: TypeFoldable<'tcx>
 767 }
 768
 769 EnumTypeFoldableImpl! {
 770     impl<'tcx, T, E> TypeFoldable<'tcx> for Result<T, E> {
 771         (Ok)(a),
 772         (Err)(a),
 773     } where T: TypeFoldable<'tcx>, E: TypeFoldable<'tcx>,
 774 }
 775
 776 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Rc<T> {
 777     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 778         // FIXME: Reuse the `Rc` here.
 779         Rc::new((*self).clone().fold_with(folder))
 780     }
 781
 782     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 783         (**self).visit_with(visitor)
 784     }
 785 }
 786
 787 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Arc<T> {
 788     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 789         // FIXME: Reuse the `Arc` here.
 790         Arc::new((*self).clone().fold_with(folder))
 791     }
 792
 793     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 794         (**self).visit_with(visitor)
 795     }
 796 }
 797
 798 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<T> {
 799     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 800         self.map_id(|value| value.fold_with(folder))
 801     }
 802
 803     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 804         (**self).visit_with(visitor)
 805     }
 806 }
 807
 808 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
 809     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 810         self.map_id(|t| t.fold_with(folder))
 811     }
 812
 813     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 814         self.iter().try_for_each(|t| t.visit_with(visitor))
 815     }
 816 }
 817
 818 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<[T]> {
 819     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 820         self.map_id(|t| t.fold_with(folder))
 821     }
 822
 823     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 824         self.iter().try_for_each(|t| t.visit_with(visitor))
 825     }
 826 }
 827
 828 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<T> {
 829     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 830         self.map_bound(|ty| ty.fold_with(folder))
 831     }
 832
 833     fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 834         folder.fold_binder(self)
 835     }
 836
 837     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 838         self.as_ref().skip_binder().visit_with(visitor)
 839     }
 840
 841     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 842         visitor.visit_binder(self)
 843     }
 844 }
 845
 846 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Binder<ty::ExistentialPredicate<'tcx>>> {
 847     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 848         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_poly_existential_predicates(v))
 849     }
 850
 851     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 852         self.iter().try_for_each(|p| p.visit_with(visitor))
 853     }
 854 }
 855
 856 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<Ty<'tcx>> {
 857     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 858         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_type_list(v))
 859     }
 860
 861     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 862         self.iter().try_for_each(|t| t.visit_with(visitor))
 863     }
 864 }
 865
 866 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ProjectionKind> {
 867     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 868         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_projs(v))
 869     }
 870
 871     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 872         self.iter().try_for_each(|t| t.visit_with(visitor))
 873     }
 874 }
 875
 876 impl<'tcx> TypeFoldable<'tcx> for ty::instance::Instance<'tcx> {
 877     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 878         use crate::ty::InstanceDef::*;
 879         Self {
 880             substs: self.substs.fold_with(folder),
 881             def: match self.def {
 882                 Item(def) => Item(def.fold_with(folder)),
 883                 VtableShim(did) => VtableShim(did.fold_with(folder)),
 884                 ReifyShim(did) => ReifyShim(did.fold_with(folder)),
 885                 Intrinsic(did) => Intrinsic(did.fold_with(folder)),
 886                 FnPtrShim(did, ty) => FnPtrShim(did.fold_with(folder), ty.fold_with(folder)),
 887                 Virtual(did, i) => Virtual(did.fold_with(folder), i),
 888                 ClosureOnceShim { call_once } => {
 889                     ClosureOnceShim { call_once: call_once.fold_with(folder) }
 890                 }
 891                 DropGlue(did, ty) => DropGlue(did.fold_with(folder), ty.fold_with(folder)),
 892                 CloneShim(did, ty) => CloneShim(did.fold_with(folder), ty.fold_with(folder)),
 893             },
 894         }
 895     }
 896
 897     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 898         use crate::ty::InstanceDef::*;
 899         self.substs.visit_with(visitor)?;
 900         match self.def {
 901             Item(def) => def.visit_with(visitor),
 902             VtableShim(did) | ReifyShim(did) | Intrinsic(did) | Virtual(did, _) => {
 903                 did.visit_with(visitor)
 904             }
 905             FnPtrShim(did, ty) | CloneShim(did, ty) => {
 906                 did.visit_with(visitor)?;
 907                 ty.visit_with(visitor)
 908             }
 909             DropGlue(did, ty) => {
 910                 did.visit_with(visitor)?;
 911                 ty.visit_with(visitor)
 912             }
 913             ClosureOnceShim { call_once } => call_once.visit_with(visitor),
 914         }
 915     }
 916 }
 917
 918 impl<'tcx> TypeFoldable<'tcx> for interpret::GlobalId<'tcx> {
 919     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 920         Self { instance: self.instance.fold_with(folder), promoted: self.promoted }
 921     }
 922
 923     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 924         self.instance.visit_with(visitor)
 925     }
 926 }
 927
 928 impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
 929     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 930         let kind = match *self.kind() {
 931             ty::RawPtr(tm) => ty::RawPtr(tm.fold_with(folder)),
 932             ty::Array(typ, sz) => ty::Array(typ.fold_with(folder), sz.fold_with(folder)),
 933             ty::Slice(typ) => ty::Slice(typ.fold_with(folder)),
 934             ty::Adt(tid, substs) => ty::Adt(tid, substs.fold_with(folder)),
 935             ty::Dynamic(trait_ty, region) => {
 936                 ty::Dynamic(trait_ty.fold_with(folder), region.fold_with(folder))
 937             }
 938             ty::Tuple(ts) => ty::Tuple(ts.fold_with(folder)),
 939             ty::FnDef(def_id, substs) => ty::FnDef(def_id, substs.fold_with(folder)),
 940             ty::FnPtr(f) => ty::FnPtr(f.fold_with(folder)),
 941             ty::Ref(r, ty, mutbl) => ty::Ref(r.fold_with(folder), ty.fold_with(folder), mutbl),
 942             ty::Generator(did, substs, movability) => {
 943                 ty::Generator(did, substs.fold_with(folder), movability)
 944             }
 945             ty::GeneratorWitness(types) => ty::GeneratorWitness(types.fold_with(folder)),
 946             ty::Closure(did, substs) => ty::Closure(did, substs.fold_with(folder)),
 947             ty::Projection(data) => ty::Projection(data.fold_with(folder)),
 948             ty::Opaque(did, substs) => ty::Opaque(did, substs.fold_with(folder)),
 949
 950             ty::Bool
 951             | ty::Char
 952             | ty::Str
 953             | ty::Int(_)
 954             | ty::Uint(_)
 955             | ty::Float(_)
 956             | ty::Error(_)
 957             | ty::Infer(_)
 958             | ty::Param(..)
 959             | ty::Bound(..)
 960             | ty::Placeholder(..)
 961             | ty::Never
 962             | ty::Foreign(..) => return self,
 963         };
 964
 965         if *self.kind() == kind { self } else { folder.tcx().mk_ty(kind) }
 966     }
 967
 968     fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
 969         folder.fold_ty(self)
 970     }
 971
 972     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 973         match self.kind() {
 974             ty::RawPtr(ref tm) => tm.visit_with(visitor),
 975             ty::Array(typ, sz) => {
 976                 typ.visit_with(visitor)?;
 977                 sz.visit_with(visitor)
 978             }
 979             ty::Slice(typ) => typ.visit_with(visitor),
 980             ty::Adt(_, substs) => substs.visit_with(visitor),
 981             ty::Dynamic(ref trait_ty, ref reg) => {
 982                 trait_ty.visit_with(visitor)?;
 983                 reg.visit_with(visitor)
 984             }
 985             ty::Tuple(ts) => ts.visit_with(visitor),
 986             ty::FnDef(_, substs) => substs.visit_with(visitor),
 987             ty::FnPtr(ref f) => f.visit_with(visitor),
 988             ty::Ref(r, ty, _) => {
 989                 r.visit_with(visitor)?;
 990                 ty.visit_with(visitor)
 991             }
 992             ty::Generator(_did, ref substs, _) => substs.visit_with(visitor),
 993             ty::GeneratorWitness(ref types) => types.visit_with(visitor),
 994             ty::Closure(_did, ref substs) => substs.visit_with(visitor),
 995             ty::Projection(ref data) => data.visit_with(visitor),
 996             ty::Opaque(_, ref substs) => substs.visit_with(visitor),
 997
 998             ty::Bool
 999             | ty::Char
1000             | ty::Str
1001             | ty::Int(_)
1002             | ty::Uint(_)
1003             | ty::Float(_)
1004             | ty::Error(_)
1005             | ty::Infer(_)
1006             | ty::Bound(..)
1007             | ty::Placeholder(..)
1008             | ty::Param(..)
1009             | ty::Never
1010             | ty::Foreign(..) => ControlFlow::CONTINUE,
1011         }
1012     }
1013
1014     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1015         visitor.visit_ty(self)
1016     }
1017 }
1018
1019 impl<'tcx> TypeFoldable<'tcx> for ty::Region<'tcx> {
1020     fn super_fold_with<F: TypeFolder<'tcx>>(self, _folder: &mut F) -> Self {
1021         self
1022     }
1023
1024     fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1025         folder.fold_region(self)
1026     }
1027
1028     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> ControlFlow<V::BreakTy> {
1029         ControlFlow::CONTINUE
1030     }
1031
1032     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1033         visitor.visit_region(*self)
1034     }
1035 }
1036
1037 impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
1038     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1039         let new = ty::PredicateKind::super_fold_with(self.inner.kind, folder);
1040         folder.tcx().reuse_or_mk_predicate(self, new)
1041     }
1042
1043     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1044         ty::PredicateKind::super_visit_with(&self.inner.kind, visitor)
1045     }
1046
1047     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1048         visitor.visit_predicate(*self)
1049     }
1050
1051     fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
1052         self.inner.outer_exclusive_binder > binder
1053     }
1054
1055     fn has_type_flags(&self, flags: ty::TypeFlags) -> bool {
1056         self.inner.flags.intersects(flags)
1057     }
1058 }
1059
1060 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Predicate<'tcx>> {
1061     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1062         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_predicates(v))
1063     }
1064
1065     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1066         self.iter().try_for_each(|p| p.visit_with(visitor))
1067     }
1068 }
1069
1070 impl<'tcx, T: TypeFoldable<'tcx>, I: Idx> TypeFoldable<'tcx> for IndexVec<I, T> {
1071     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1072         self.map_id(|x| x.fold_with(folder))
1073     }
1074
1075     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1076         self.iter().try_for_each(|t| t.visit_with(visitor))
1077     }
1078 }
1079
1080 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::Const<'tcx> {
1081     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1082         let ty = self.ty.fold_with(folder);
1083         let val = self.val.fold_with(folder);
1084         if ty != self.ty || val != self.val {
1085             folder.tcx().mk_const(ty::Const { ty, val })
1086         } else {
1087             self
1088         }
1089     }
1090
1091     fn fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1092         folder.fold_const(self)
1093     }
1094
1095     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1096         self.ty.visit_with(visitor)?;
1097         self.val.visit_with(visitor)
1098     }
1099
1100     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1101         visitor.visit_const(self)
1102     }
1103 }
1104
1105 impl<'tcx> TypeFoldable<'tcx> for ty::ConstKind<'tcx> {
1106     fn super_fold_with<F: TypeFolder<'tcx>>(self, folder: &mut F) -> Self {
1107         match self {
1108             ty::ConstKind::Infer(ic) => ty::ConstKind::Infer(ic.fold_with(folder)),
1109             ty::ConstKind::Param(p) => ty::ConstKind::Param(p.fold_with(folder)),
1110             ty::ConstKind::Unevaluated(did, substs, promoted) => {
1111                 ty::ConstKind::Unevaluated(did, substs.fold_with(folder), promoted)
1112             }
1113             ty::ConstKind::Value(_)
1114             | ty::ConstKind::Bound(..)
1115             | ty::ConstKind::Placeholder(..)
1116             | ty::ConstKind::Error(_) => self,
1117         }
1118     }
1119
1120     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
1121         match *self {
1122             ty::ConstKind::Infer(ic) => ic.visit_with(visitor),
1123             ty::ConstKind::Param(p) => p.visit_with(visitor),
1124             ty::ConstKind::Unevaluated(_, substs, _) => substs.visit_with(visitor),
1125             ty::ConstKind::Value(_)
1126             | ty::ConstKind::Bound(..)
1127             | ty::ConstKind::Placeholder(_)
1128             | ty::ConstKind::Error(_) => ControlFlow::CONTINUE,
1129         }
1130     }
1131 }
1132
1133 impl<'tcx> TypeFoldable<'tcx> for InferConst<'tcx> {
1134     fn super_fold_with<F: TypeFolder<'tcx>>(self, _folder: &mut F) -> Self {
1135         self
1136     }
1137
1138     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> ControlFlow<V::BreakTy> {
1139         ControlFlow::CONTINUE
1140     }
1141 }