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