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::{Field, ProjectionKind};
   7 use crate::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable};
   8 use crate::ty::print::{with_no_trimmed_paths, FmtPrinter, Printer};
   9 use crate::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor};
  10 use crate::ty::{self, InferConst, Lift, Term, TermKind, Ty, TyCtxt};
  11 use rustc_data_structures::functor::IdFunctor;
  12 use rustc_hir::def::Namespace;
  13 use rustc_index::vec::{Idx, IndexVec};
  14
  15 use std::fmt;
  16 use std::mem::ManuallyDrop;
  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                 f.write_str(
  26                     &FmtPrinter::new(tcx, Namespace::TypeNS)
  27                         .print_def_path(self.def_id, &[])?
  28                         .into_buffer(),
  29                 )
  30             })
  31         })
  32     }
  33 }
  34
  35 impl<'tcx> fmt::Debug for ty::AdtDef<'tcx> {
  36     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  37         ty::tls::with(|tcx| {
  38             with_no_trimmed_paths!({
  39                 f.write_str(
  40                     &FmtPrinter::new(tcx, Namespace::TypeNS)
  41                         .print_def_path(self.did(), &[])?
  42                         .into_buffer(),
  43                 )
  44             })
  45         })
  46     }
  47 }
  48
  49 impl fmt::Debug for ty::UpvarId {
  50     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  51         let name = ty::tls::with(|tcx| tcx.hir().name(self.var_path.hir_id));
  52         write!(f, "UpvarId({:?};`{}`;{:?})", self.var_path.hir_id, name, self.closure_expr_id)
  53     }
  54 }
  55
  56 impl<'tcx> 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<'tcx> 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.is_crate_root() {
  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::FreeRegion {
  85     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  86         write!(f, "ReFree({:?}, {:?})", self.scope, self.bound_region)
  87     }
  88 }
  89
  90 impl<'tcx> fmt::Debug for ty::FnSig<'tcx> {
  91     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  92         write!(f, "({:?}; c_variadic: {})->{:?}", self.inputs(), self.c_variadic, self.output())
  93     }
  94 }
  95
  96 impl<'tcx> fmt::Debug for ty::ConstVid<'tcx> {
  97     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  98         write!(f, "_#{}c", self.index)
  99     }
 100 }
 101
 102 impl fmt::Debug for ty::RegionVid {
 103     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 104         write!(f, "'_#{}r", self.index())
 105     }
 106 }
 107
 108 impl<'tcx> fmt::Debug for ty::TraitRef<'tcx> {
 109     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 110         with_no_trimmed_paths!(fmt::Display::fmt(self, f))
 111     }
 112 }
 113
 114 impl<'tcx> fmt::Debug for Ty<'tcx> {
 115     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 116         with_no_trimmed_paths!(fmt::Display::fmt(self, f))
 117     }
 118 }
 119
 120 impl fmt::Debug for ty::ParamTy {
 121     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 122         write!(f, "{}/#{}", self.name, self.index)
 123     }
 124 }
 125
 126 impl fmt::Debug for ty::ParamConst {
 127     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 128         write!(f, "{}/#{}", self.name, self.index)
 129     }
 130 }
 131
 132 impl<'tcx> fmt::Debug for ty::TraitPredicate<'tcx> {
 133     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 134         if let ty::BoundConstness::ConstIfConst = self.constness {
 135             write!(f, "~const ")?;
 136         }
 137         write!(f, "TraitPredicate({:?}, polarity:{:?})", self.trait_ref, self.polarity)
 138     }
 139 }
 140
 141 impl<'tcx> fmt::Debug for ty::ProjectionPredicate<'tcx> {
 142     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 143         write!(f, "ProjectionPredicate({:?}, {:?})", self.projection_ty, self.term)
 144     }
 145 }
 146
 147 impl<'tcx> fmt::Debug for ty::Predicate<'tcx> {
 148     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 149         write!(f, "{:?}", self.kind())
 150     }
 151 }
 152
 153 impl<'tcx> fmt::Debug for ty::PredicateKind<'tcx> {
 154     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 155         match *self {
 156             ty::PredicateKind::Trait(ref a) => a.fmt(f),
 157             ty::PredicateKind::Subtype(ref pair) => pair.fmt(f),
 158             ty::PredicateKind::Coerce(ref pair) => pair.fmt(f),
 159             ty::PredicateKind::RegionOutlives(ref pair) => pair.fmt(f),
 160             ty::PredicateKind::TypeOutlives(ref pair) => pair.fmt(f),
 161             ty::PredicateKind::Projection(ref pair) => pair.fmt(f),
 162             ty::PredicateKind::WellFormed(data) => write!(f, "WellFormed({:?})", data),
 163             ty::PredicateKind::ObjectSafe(trait_def_id) => {
 164                 write!(f, "ObjectSafe({:?})", trait_def_id)
 165             }
 166             ty::PredicateKind::ClosureKind(closure_def_id, closure_substs, kind) => {
 167                 write!(f, "ClosureKind({:?}, {:?}, {:?})", closure_def_id, closure_substs, kind)
 168             }
 169             ty::PredicateKind::ConstEvaluatable(uv) => {
 170                 write!(f, "ConstEvaluatable({:?}, {:?})", uv.def, uv.substs)
 171             }
 172             ty::PredicateKind::ConstEquate(c1, c2) => write!(f, "ConstEquate({:?}, {:?})", c1, c2),
 173             ty::PredicateKind::TypeWellFormedFromEnv(ty) => {
 174                 write!(f, "TypeWellFormedFromEnv({:?})", ty)
 175             }
 176         }
 177     }
 178 }
 179
 180 ///////////////////////////////////////////////////////////////////////////
 181 // Atomic structs
 182 //
 183 // For things that don't carry any arena-allocated data (and are
 184 // copy...), just add them to this list.
 185
 186 TrivialTypeTraversalAndLiftImpls! {
 187     (),
 188     bool,
 189     usize,
 190     ::rustc_target::abi::VariantIdx,
 191     u32,
 192     u64,
 193     String,
 194     crate::middle::region::Scope,
 195     crate::ty::FloatTy,
 196     ::rustc_ast::InlineAsmOptions,
 197     ::rustc_ast::InlineAsmTemplatePiece,
 198     ::rustc_ast::NodeId,
 199     ::rustc_span::symbol::Symbol,
 200     ::rustc_hir::def::Res,
 201     ::rustc_hir::def_id::DefId,
 202     ::rustc_hir::def_id::LocalDefId,
 203     ::rustc_hir::HirId,
 204     ::rustc_hir::MatchSource,
 205     ::rustc_hir::Mutability,
 206     ::rustc_hir::Unsafety,
 207     ::rustc_target::asm::InlineAsmRegOrRegClass,
 208     ::rustc_target::spec::abi::Abi,
 209     crate::mir::coverage::ExpressionOperandId,
 210     crate::mir::coverage::CounterValueReference,
 211     crate::mir::coverage::InjectedExpressionId,
 212     crate::mir::coverage::InjectedExpressionIndex,
 213     crate::mir::coverage::MappedExpressionIndex,
 214     crate::mir::Local,
 215     crate::mir::Promoted,
 216     crate::traits::Reveal,
 217     crate::ty::adjustment::AutoBorrowMutability,
 218     crate::ty::AdtKind,
 219     crate::ty::BoundConstness,
 220     // Including `BoundRegionKind` is a *bit* dubious, but direct
 221     // references to bound region appear in `ty::Error`, and aren't
 222     // really meant to be folded. In general, we can only fold a fully
 223     // general `Region`.
 224     crate::ty::BoundRegionKind,
 225     crate::ty::AssocItem,
 226     crate::ty::AssocKind,
 227     crate::ty::Placeholder<crate::ty::BoundRegionKind>,
 228     crate::ty::ClosureKind,
 229     crate::ty::FreeRegion,
 230     crate::ty::InferTy,
 231     crate::ty::IntVarValue,
 232     crate::ty::ParamConst,
 233     crate::ty::ParamTy,
 234     crate::ty::adjustment::PointerCast,
 235     crate::ty::RegionVid,
 236     crate::ty::UniverseIndex,
 237     crate::ty::Variance,
 238     ::rustc_span::Span,
 239     ::rustc_errors::ErrorGuaranteed,
 240     Field,
 241     interpret::Scalar,
 242     rustc_target::abi::Size,
 243     ty::DelaySpanBugEmitted,
 244     rustc_type_ir::DebruijnIndex,
 245     ty::BoundVar,
 246     ty::Placeholder<ty::BoundVar>,
 247 }
 248
 249 TrivialTypeTraversalAndLiftImpls! {
 250     for<'tcx> {
 251         ty::ValTree<'tcx>,
 252     }
 253 }
 254
 255 ///////////////////////////////////////////////////////////////////////////
 256 // Lift implementations
 257
 258 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>> Lift<'tcx> for (A, B) {
 259     type Lifted = (A::Lifted, B::Lifted);
 260     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 261         Some((tcx.lift(self.0)?, tcx.lift(self.1)?))
 262     }
 263 }
 264
 265 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>, C: Lift<'tcx>> Lift<'tcx> for (A, B, C) {
 266     type Lifted = (A::Lifted, B::Lifted, C::Lifted);
 267     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 268         Some((tcx.lift(self.0)?, tcx.lift(self.1)?, tcx.lift(self.2)?))
 269     }
 270 }
 271
 272 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Option<T> {
 273     type Lifted = Option<T::Lifted>;
 274     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 275         tcx.lift(self?).map(Some)
 276     }
 277 }
 278
 279 impl<'tcx, T: Lift<'tcx>, E: Lift<'tcx>> Lift<'tcx> for Result<T, E> {
 280     type Lifted = Result<T::Lifted, E::Lifted>;
 281     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 282         match self {
 283             Ok(x) => tcx.lift(x).map(Ok),
 284             Err(e) => tcx.lift(e).map(Err),
 285         }
 286     }
 287 }
 288
 289 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Box<T> {
 290     type Lifted = Box<T::Lifted>;
 291     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 292         Some(Box::new(tcx.lift(*self)?))
 293     }
 294 }
 295
 296 impl<'tcx, T: Lift<'tcx> + Clone> Lift<'tcx> for Rc<T> {
 297     type Lifted = Rc<T::Lifted>;
 298     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 299         Some(Rc::new(tcx.lift(self.as_ref().clone())?))
 300     }
 301 }
 302
 303 impl<'tcx, T: Lift<'tcx> + Clone> Lift<'tcx> for Arc<T> {
 304     type Lifted = Arc<T::Lifted>;
 305     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 306         Some(Arc::new(tcx.lift(self.as_ref().clone())?))
 307     }
 308 }
 309 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Vec<T> {
 310     type Lifted = Vec<T::Lifted>;
 311     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 312         self.into_iter().map(|v| tcx.lift(v)).collect()
 313     }
 314 }
 315
 316 impl<'tcx, I: Idx, T: Lift<'tcx>> Lift<'tcx> for IndexVec<I, T> {
 317     type Lifted = IndexVec<I, T::Lifted>;
 318     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 319         self.into_iter().map(|e| tcx.lift(e)).collect()
 320     }
 321 }
 322
 323 impl<'a, 'tcx> Lift<'tcx> for Term<'a> {
 324     type Lifted = ty::Term<'tcx>;
 325     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 326         Some(
 327             match self.unpack() {
 328                 TermKind::Ty(ty) => TermKind::Ty(tcx.lift(ty)?),
 329                 TermKind::Const(c) => TermKind::Const(tcx.lift(c)?),
 330             }
 331             .pack(),
 332         )
 333     }
 334 }
 335 impl<'a, 'tcx> Lift<'tcx> for ty::ParamEnv<'a> {
 336     type Lifted = ty::ParamEnv<'tcx>;
 337     fn lift_to_tcx(self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 338         tcx.lift(self.caller_bounds())
 339             .map(|caller_bounds| ty::ParamEnv::new(caller_bounds, self.reveal(), self.constness()))
 340     }
 341 }
 342
 343 ///////////////////////////////////////////////////////////////////////////
 344 // TypeFoldable implementations.
 345
 346 /// AdtDefs are basically the same as a DefId.
 347 impl<'tcx> TypeFoldable<'tcx> for ty::AdtDef<'tcx> {
 348     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, _folder: &mut F) -> Result<Self, F::Error> {
 349         Ok(self)
 350     }
 351 }
 352
 353 impl<'tcx> TypeVisitable<'tcx> for ty::AdtDef<'tcx> {
 354     fn visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> ControlFlow<V::BreakTy> {
 355         ControlFlow::CONTINUE
 356     }
 357 }
 358
 359 impl<'tcx, T: TypeFoldable<'tcx>, U: TypeFoldable<'tcx>> TypeFoldable<'tcx> for (T, U) {
 360     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(
 361         self,
 362         folder: &mut F,
 363     ) -> Result<(T, U), F::Error> {
 364         Ok((self.0.try_fold_with(folder)?, self.1.try_fold_with(folder)?))
 365     }
 366 }
 367
 368 impl<'tcx, T: TypeVisitable<'tcx>, U: TypeVisitable<'tcx>> TypeVisitable<'tcx> for (T, U) {
 369     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 370         self.0.visit_with(visitor)?;
 371         self.1.visit_with(visitor)
 372     }
 373 }
 374
 375 impl<'tcx, A: TypeFoldable<'tcx>, B: TypeFoldable<'tcx>, C: TypeFoldable<'tcx>> TypeFoldable<'tcx>
 376     for (A, B, C)
 377 {
 378     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(
 379         self,
 380         folder: &mut F,
 381     ) -> Result<(A, B, C), F::Error> {
 382         Ok((
 383             self.0.try_fold_with(folder)?,
 384             self.1.try_fold_with(folder)?,
 385             self.2.try_fold_with(folder)?,
 386         ))
 387     }
 388 }
 389
 390 impl<'tcx, A: TypeVisitable<'tcx>, B: TypeVisitable<'tcx>, C: TypeVisitable<'tcx>>
 391     TypeVisitable<'tcx> for (A, B, C)
 392 {
 393     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 394         self.0.visit_with(visitor)?;
 395         self.1.visit_with(visitor)?;
 396         self.2.visit_with(visitor)
 397     }
 398 }
 399
 400 EnumTypeTraversalImpl! {
 401     impl<'tcx, T> TypeFoldable<'tcx> for Option<T> {
 402         (Some)(a),
 403         (None),
 404     } where T: TypeFoldable<'tcx>
 405 }
 406 EnumTypeTraversalImpl! {
 407     impl<'tcx, T> TypeVisitable<'tcx> for Option<T> {
 408         (Some)(a),
 409         (None),
 410     } where T: TypeVisitable<'tcx>
 411 }
 412
 413 EnumTypeTraversalImpl! {
 414     impl<'tcx, T, E> TypeFoldable<'tcx> for Result<T, E> {
 415         (Ok)(a),
 416         (Err)(a),
 417     } where T: TypeFoldable<'tcx>, E: TypeFoldable<'tcx>,
 418 }
 419 EnumTypeTraversalImpl! {
 420     impl<'tcx, T, E> TypeVisitable<'tcx> for Result<T, E> {
 421         (Ok)(a),
 422         (Err)(a),
 423     } where T: TypeVisitable<'tcx>, E: TypeVisitable<'tcx>,
 424 }
 425
 426 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Rc<T> {
 427     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(
 428         mut self,
 429         folder: &mut F,
 430     ) -> Result<Self, F::Error> {
 431         // We merely want to replace the contained `T`, if at all possible,
 432         // so that we don't needlessly allocate a new `Rc` or indeed clone
 433         // the contained type.
 434         unsafe {
 435             // First step is to ensure that we have a unique reference to
 436             // the contained type, which `Rc::make_mut` will accomplish (by
 437             // allocating a new `Rc` and cloning the `T` only if required).
 438             // This is done *before* casting to `Rc<ManuallyDrop<T>>` so that
 439             // panicking during `make_mut` does not leak the `T`.
 440             Rc::make_mut(&mut self);
 441
 442             // Casting to `Rc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
 443             // is `repr(transparent)`.
 444             let ptr = Rc::into_raw(self).cast::<ManuallyDrop<T>>();
 445             let mut unique = Rc::from_raw(ptr);
 446
 447             // Call to `Rc::make_mut` above guarantees that `unique` is the
 448             // sole reference to the contained value, so we can avoid doing
 449             // a checked `get_mut` here.
 450             let slot = Rc::get_mut_unchecked(&mut unique);
 451
 452             // Semantically move the contained type out from `unique`, fold
 453             // it, then move the folded value back into `unique`.  Should
 454             // folding fail, `ManuallyDrop` ensures that the "moved-out"
 455             // value is not re-dropped.
 456             let owned = ManuallyDrop::take(slot);
 457             let folded = owned.try_fold_with(folder)?;
 458             *slot = ManuallyDrop::new(folded);
 459
 460             // Cast back to `Rc<T>`.
 461             Ok(Rc::from_raw(Rc::into_raw(unique).cast()))
 462         }
 463     }
 464 }
 465
 466 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for Rc<T> {
 467     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 468         (**self).visit_with(visitor)
 469     }
 470 }
 471
 472 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Arc<T> {
 473     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(
 474         mut self,
 475         folder: &mut F,
 476     ) -> Result<Self, F::Error> {
 477         // We merely want to replace the contained `T`, if at all possible,
 478         // so that we don't needlessly allocate a new `Arc` or indeed clone
 479         // the contained type.
 480         unsafe {
 481             // First step is to ensure that we have a unique reference to
 482             // the contained type, which `Arc::make_mut` will accomplish (by
 483             // allocating a new `Arc` and cloning the `T` only if required).
 484             // This is done *before* casting to `Arc<ManuallyDrop<T>>` so that
 485             // panicking during `make_mut` does not leak the `T`.
 486             Arc::make_mut(&mut self);
 487
 488             // Casting to `Arc<ManuallyDrop<T>>` is safe because `ManuallyDrop`
 489             // is `repr(transparent)`.
 490             let ptr = Arc::into_raw(self).cast::<ManuallyDrop<T>>();
 491             let mut unique = Arc::from_raw(ptr);
 492
 493             // Call to `Arc::make_mut` above guarantees that `unique` is the
 494             // sole reference to the contained value, so we can avoid doing
 495             // a checked `get_mut` here.
 496             let slot = Arc::get_mut_unchecked(&mut unique);
 497
 498             // Semantically move the contained type out from `unique`, fold
 499             // it, then move the folded value back into `unique`.  Should
 500             // folding fail, `ManuallyDrop` ensures that the "moved-out"
 501             // value is not re-dropped.
 502             let owned = ManuallyDrop::take(slot);
 503             let folded = owned.try_fold_with(folder)?;
 504             *slot = ManuallyDrop::new(folded);
 505
 506             // Cast back to `Arc<T>`.
 507             Ok(Arc::from_raw(Arc::into_raw(unique).cast()))
 508         }
 509     }
 510 }
 511
 512 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for Arc<T> {
 513     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 514         (**self).visit_with(visitor)
 515     }
 516 }
 517
 518 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<T> {
 519     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 520         self.try_map_id(|value| value.try_fold_with(folder))
 521     }
 522 }
 523
 524 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for Box<T> {
 525     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 526         (**self).visit_with(visitor)
 527     }
 528 }
 529
 530 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Vec<T> {
 531     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 532         self.try_map_id(|t| t.try_fold_with(folder))
 533     }
 534 }
 535
 536 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for Vec<T> {
 537     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 538         self.iter().try_for_each(|t| t.visit_with(visitor))
 539     }
 540 }
 541
 542 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for &[T] {
 543     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 544         self.iter().try_for_each(|t| t.visit_with(visitor))
 545     }
 546 }
 547
 548 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for Box<[T]> {
 549     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 550         self.try_map_id(|t| t.try_fold_with(folder))
 551     }
 552 }
 553
 554 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for Box<[T]> {
 555     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 556         self.iter().try_for_each(|t| t.visit_with(visitor))
 557     }
 558 }
 559
 560 impl<'tcx, T: TypeFoldable<'tcx>> TypeFoldable<'tcx> for ty::Binder<'tcx, T> {
 561     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 562         folder.try_fold_binder(self)
 563     }
 564 }
 565
 566 impl<'tcx, T: TypeVisitable<'tcx>> TypeVisitable<'tcx> for ty::Binder<'tcx, T> {
 567     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 568         visitor.visit_binder(self)
 569     }
 570 }
 571
 572 impl<'tcx, T: TypeFoldable<'tcx>> TypeSuperFoldable<'tcx> for ty::Binder<'tcx, T> {
 573     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
 574         self,
 575         folder: &mut F,
 576     ) -> Result<Self, F::Error> {
 577         self.try_map_bound(|ty| ty.try_fold_with(folder))
 578     }
 579 }
 580
 581 impl<'tcx, T: TypeVisitable<'tcx>> TypeSuperVisitable<'tcx> for ty::Binder<'tcx, T> {
 582     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 583         self.as_ref().skip_binder().visit_with(visitor)
 584     }
 585 }
 586
 587 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Binder<'tcx, ty::ExistentialPredicate<'tcx>>> {
 588     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 589         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_poly_existential_predicates(v))
 590     }
 591 }
 592
 593 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ProjectionKind> {
 594     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 595         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_projs(v))
 596     }
 597 }
 598
 599 impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
 600     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 601         folder.try_fold_ty(self)
 602     }
 603 }
 604
 605 impl<'tcx> TypeVisitable<'tcx> for Ty<'tcx> {
 606     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 607         visitor.visit_ty(*self)
 608     }
 609 }
 610
 611 impl<'tcx> TypeSuperFoldable<'tcx> for Ty<'tcx> {
 612     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
 613         self,
 614         folder: &mut F,
 615     ) -> Result<Self, F::Error> {
 616         let kind = match *self.kind() {
 617             ty::RawPtr(tm) => ty::RawPtr(tm.try_fold_with(folder)?),
 618             ty::Array(typ, sz) => ty::Array(typ.try_fold_with(folder)?, sz.try_fold_with(folder)?),
 619             ty::Slice(typ) => ty::Slice(typ.try_fold_with(folder)?),
 620             ty::Adt(tid, substs) => ty::Adt(tid, substs.try_fold_with(folder)?),
 621             ty::Dynamic(trait_ty, region, representation) => ty::Dynamic(
 622                 trait_ty.try_fold_with(folder)?,
 623                 region.try_fold_with(folder)?,
 624                 representation,
 625             ),
 626             ty::Tuple(ts) => ty::Tuple(ts.try_fold_with(folder)?),
 627             ty::FnDef(def_id, substs) => ty::FnDef(def_id, substs.try_fold_with(folder)?),
 628             ty::FnPtr(f) => ty::FnPtr(f.try_fold_with(folder)?),
 629             ty::Ref(r, ty, mutbl) => {
 630                 ty::Ref(r.try_fold_with(folder)?, ty.try_fold_with(folder)?, mutbl)
 631             }
 632             ty::Generator(did, substs, movability) => {
 633                 ty::Generator(did, substs.try_fold_with(folder)?, movability)
 634             }
 635             ty::GeneratorWitness(types) => ty::GeneratorWitness(types.try_fold_with(folder)?),
 636             ty::Closure(did, substs) => ty::Closure(did, substs.try_fold_with(folder)?),
 637             ty::Projection(data) => ty::Projection(data.try_fold_with(folder)?),
 638             ty::Opaque(did, substs) => ty::Opaque(did, substs.try_fold_with(folder)?),
 639
 640             ty::Bool
 641             | ty::Char
 642             | ty::Str
 643             | ty::Int(_)
 644             | ty::Uint(_)
 645             | ty::Float(_)
 646             | ty::Error(_)
 647             | ty::Infer(_)
 648             | ty::Param(..)
 649             | ty::Bound(..)
 650             | ty::Placeholder(..)
 651             | ty::Never
 652             | ty::Foreign(..) => return Ok(self),
 653         };
 654
 655         Ok(if *self.kind() == kind { self } else { folder.tcx().mk_ty(kind) })
 656     }
 657 }
 658
 659 impl<'tcx> TypeSuperVisitable<'tcx> for Ty<'tcx> {
 660     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 661         match self.kind() {
 662             ty::RawPtr(ref tm) => tm.visit_with(visitor),
 663             ty::Array(typ, sz) => {
 664                 typ.visit_with(visitor)?;
 665                 sz.visit_with(visitor)
 666             }
 667             ty::Slice(typ) => typ.visit_with(visitor),
 668             ty::Adt(_, substs) => substs.visit_with(visitor),
 669             ty::Dynamic(ref trait_ty, ref reg, _) => {
 670                 trait_ty.visit_with(visitor)?;
 671                 reg.visit_with(visitor)
 672             }
 673             ty::Tuple(ts) => ts.visit_with(visitor),
 674             ty::FnDef(_, substs) => substs.visit_with(visitor),
 675             ty::FnPtr(ref f) => f.visit_with(visitor),
 676             ty::Ref(r, ty, _) => {
 677                 r.visit_with(visitor)?;
 678                 ty.visit_with(visitor)
 679             }
 680             ty::Generator(_did, ref substs, _) => substs.visit_with(visitor),
 681             ty::GeneratorWitness(ref types) => types.visit_with(visitor),
 682             ty::Closure(_did, ref substs) => substs.visit_with(visitor),
 683             ty::Projection(ref data) => data.visit_with(visitor),
 684             ty::Opaque(_, ref substs) => substs.visit_with(visitor),
 685
 686             ty::Bool
 687             | ty::Char
 688             | ty::Str
 689             | ty::Int(_)
 690             | ty::Uint(_)
 691             | ty::Float(_)
 692             | ty::Error(_)
 693             | ty::Infer(_)
 694             | ty::Bound(..)
 695             | ty::Placeholder(..)
 696             | ty::Param(..)
 697             | ty::Never
 698             | ty::Foreign(..) => ControlFlow::CONTINUE,
 699         }
 700     }
 701 }
 702
 703 impl<'tcx> TypeFoldable<'tcx> for ty::Region<'tcx> {
 704     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 705         folder.try_fold_region(self)
 706     }
 707 }
 708
 709 impl<'tcx> TypeVisitable<'tcx> for ty::Region<'tcx> {
 710     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 711         visitor.visit_region(*self)
 712     }
 713 }
 714
 715 impl<'tcx> TypeSuperFoldable<'tcx> for ty::Region<'tcx> {
 716     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
 717         self,
 718         _folder: &mut F,
 719     ) -> Result<Self, F::Error> {
 720         Ok(self)
 721     }
 722 }
 723
 724 impl<'tcx> TypeSuperVisitable<'tcx> for ty::Region<'tcx> {
 725     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> ControlFlow<V::BreakTy> {
 726         ControlFlow::CONTINUE
 727     }
 728 }
 729
 730 impl<'tcx> TypeFoldable<'tcx> for ty::Predicate<'tcx> {
 731     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 732         folder.try_fold_predicate(self)
 733     }
 734 }
 735
 736 impl<'tcx> TypeVisitable<'tcx> for ty::Predicate<'tcx> {
 737     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 738         visitor.visit_predicate(*self)
 739     }
 740
 741     #[inline]
 742     fn has_vars_bound_at_or_above(&self, binder: ty::DebruijnIndex) -> bool {
 743         self.outer_exclusive_binder() > binder
 744     }
 745
 746     #[inline]
 747     fn has_type_flags(&self, flags: ty::TypeFlags) -> bool {
 748         self.flags().intersects(flags)
 749     }
 750 }
 751
 752 impl<'tcx> TypeSuperFoldable<'tcx> for ty::Predicate<'tcx> {
 753     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
 754         self,
 755         folder: &mut F,
 756     ) -> Result<Self, F::Error> {
 757         let new = self.kind().try_fold_with(folder)?;
 758         Ok(folder.tcx().reuse_or_mk_predicate(self, new))
 759     }
 760 }
 761
 762 impl<'tcx> TypeSuperVisitable<'tcx> for ty::Predicate<'tcx> {
 763     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 764         self.kind().visit_with(visitor)
 765     }
 766 }
 767
 768 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ty::Predicate<'tcx>> {
 769     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 770         ty::util::fold_list(self, folder, |tcx, v| tcx.intern_predicates(v))
 771     }
 772 }
 773
 774 impl<'tcx, T: TypeFoldable<'tcx>, I: Idx> TypeFoldable<'tcx> for IndexVec<I, T> {
 775     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 776         self.try_map_id(|x| x.try_fold_with(folder))
 777     }
 778 }
 779
 780 impl<'tcx, T: TypeVisitable<'tcx>, I: Idx> TypeVisitable<'tcx> for IndexVec<I, T> {
 781     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 782         self.iter().try_for_each(|t| t.visit_with(visitor))
 783     }
 784 }
 785
 786 impl<'tcx> TypeFoldable<'tcx> for ty::Const<'tcx> {
 787     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 788         folder.try_fold_const(self)
 789     }
 790 }
 791
 792 impl<'tcx> TypeVisitable<'tcx> for ty::Const<'tcx> {
 793     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 794         visitor.visit_const(*self)
 795     }
 796 }
 797
 798 impl<'tcx> TypeSuperFoldable<'tcx> for ty::Const<'tcx> {
 799     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
 800         self,
 801         folder: &mut F,
 802     ) -> Result<Self, F::Error> {
 803         let ty = self.ty().try_fold_with(folder)?;
 804         let kind = self.kind().try_fold_with(folder)?;
 805         if ty != self.ty() || kind != self.kind() {
 806             Ok(folder.tcx().mk_const(ty::ConstS { ty, kind }))
 807         } else {
 808             Ok(self)
 809         }
 810     }
 811 }
 812
 813 impl<'tcx> TypeSuperVisitable<'tcx> for ty::Const<'tcx> {
 814     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 815         self.ty().visit_with(visitor)?;
 816         self.kind().visit_with(visitor)
 817     }
 818 }
 819
 820 impl<'tcx> TypeFoldable<'tcx> for InferConst<'tcx> {
 821     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, _folder: &mut F) -> Result<Self, F::Error> {
 822         Ok(self)
 823     }
 824 }
 825
 826 impl<'tcx> TypeVisitable<'tcx> for InferConst<'tcx> {
 827     fn visit_with<V: TypeVisitor<'tcx>>(&self, _visitor: &mut V) -> ControlFlow<V::BreakTy> {
 828         ControlFlow::CONTINUE
 829     }
 830 }
 831
 832 impl<'tcx> TypeFoldable<'tcx> for ty::Unevaluated<'tcx> {
 833     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 834         folder.try_fold_unevaluated(self)
 835     }
 836 }
 837
 838 impl<'tcx> TypeVisitable<'tcx> for ty::Unevaluated<'tcx> {
 839     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 840         visitor.visit_unevaluated(*self)
 841     }
 842 }
 843
 844 impl<'tcx> TypeSuperFoldable<'tcx> for ty::Unevaluated<'tcx> {
 845     fn try_super_fold_with<F: FallibleTypeFolder<'tcx>>(
 846         self,
 847         folder: &mut F,
 848     ) -> Result<Self, F::Error> {
 849         Ok(ty::Unevaluated {
 850             def: self.def,
 851             substs: self.substs.try_fold_with(folder)?,
 852             promoted: self.promoted,
 853         })
 854     }
 855 }
 856
 857 impl<'tcx> TypeSuperVisitable<'tcx> for ty::Unevaluated<'tcx> {
 858     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 859         self.substs.visit_with(visitor)
 860     }
 861 }
 862
 863 impl<'tcx> TypeFoldable<'tcx> for ty::Unevaluated<'tcx, ()> {
 864     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
 865         Ok(self.expand().try_fold_with(folder)?.shrink())
 866     }
 867 }
 868
 869 impl<'tcx> TypeVisitable<'tcx> for ty::Unevaluated<'tcx, ()> {
 870     fn visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> ControlFlow<V::BreakTy> {
 871         self.expand().visit_with(visitor)
 872     }
 873 }