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