src/librustc/traits/structural_impls.rs

   1 use crate::traits;
   2 use crate::traits::project::Normalized;
   3 use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
   4 use crate::ty::{self, Lift, Ty, TyCtxt};
   5 use chalk_engine;
   6 use rustc_span::symbol::Symbol;
   7 use smallvec::SmallVec;
   8
   9 use std::collections::{BTreeMap, BTreeSet};
  10 use std::fmt;
  11 use std::rc::Rc;
  12
  13 // Structural impls for the structs in `traits`.
  14
  15 impl<'tcx, T: fmt::Debug> fmt::Debug for Normalized<'tcx, T> {
  16     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  17         write!(f, "Normalized({:?}, {:?})", self.value, self.obligations)
  18     }
  19 }
  20
  21 impl<'tcx, O: fmt::Debug> fmt::Debug for traits::Obligation<'tcx, O> {
  22     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  23         if ty::tls::with(|tcx| tcx.sess.verbose()) {
  24             write!(
  25                 f,
  26                 "Obligation(predicate={:?}, cause={:?}, param_env={:?}, depth={})",
  27                 self.predicate, self.cause, self.param_env, self.recursion_depth
  28             )
  29         } else {
  30             write!(f, "Obligation(predicate={:?}, depth={})", self.predicate, self.recursion_depth)
  31         }
  32     }
  33 }
  34
  35 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::Vtable<'tcx, N> {
  36     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  37         match *self {
  38             super::VtableImpl(ref v) => write!(f, "{:?}", v),
  39
  40             super::VtableAutoImpl(ref t) => write!(f, "{:?}", t),
  41
  42             super::VtableClosure(ref d) => write!(f, "{:?}", d),
  43
  44             super::VtableGenerator(ref d) => write!(f, "{:?}", d),
  45
  46             super::VtableFnPointer(ref d) => write!(f, "VtableFnPointer({:?})", d),
  47
  48             super::VtableObject(ref d) => write!(f, "{:?}", d),
  49
  50             super::VtableParam(ref n) => write!(f, "VtableParam({:?})", n),
  51
  52             super::VtableBuiltin(ref d) => write!(f, "{:?}", d),
  53
  54             super::VtableTraitAlias(ref d) => write!(f, "{:?}", d),
  55         }
  56     }
  57 }
  58
  59 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableImplData<'tcx, N> {
  60     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  61         write!(
  62             f,
  63             "VtableImplData(impl_def_id={:?}, substs={:?}, nested={:?})",
  64             self.impl_def_id, self.substs, self.nested
  65         )
  66     }
  67 }
  68
  69 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableGeneratorData<'tcx, N> {
  70     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  71         write!(
  72             f,
  73             "VtableGeneratorData(generator_def_id={:?}, substs={:?}, nested={:?})",
  74             self.generator_def_id, self.substs, self.nested
  75         )
  76     }
  77 }
  78
  79 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableClosureData<'tcx, N> {
  80     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  81         write!(
  82             f,
  83             "VtableClosureData(closure_def_id={:?}, substs={:?}, nested={:?})",
  84             self.closure_def_id, self.substs, self.nested
  85         )
  86     }
  87 }
  88
  89 impl<N: fmt::Debug> fmt::Debug for traits::VtableBuiltinData<N> {
  90     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  91         write!(f, "VtableBuiltinData(nested={:?})", self.nested)
  92     }
  93 }
  94
  95 impl<N: fmt::Debug> fmt::Debug for traits::VtableAutoImplData<N> {
  96     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  97         write!(
  98             f,
  99             "VtableAutoImplData(trait_def_id={:?}, nested={:?})",
 100             self.trait_def_id, self.nested
 101         )
 102     }
 103 }
 104
 105 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableObjectData<'tcx, N> {
 106     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 107         write!(
 108             f,
 109             "VtableObjectData(upcast={:?}, vtable_base={}, nested={:?})",
 110             self.upcast_trait_ref, self.vtable_base, self.nested
 111         )
 112     }
 113 }
 114
 115 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableFnPointerData<'tcx, N> {
 116     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 117         write!(f, "VtableFnPointerData(fn_ty={:?}, nested={:?})", self.fn_ty, self.nested)
 118     }
 119 }
 120
 121 impl<'tcx, N: fmt::Debug> fmt::Debug for traits::VtableTraitAliasData<'tcx, N> {
 122     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 123         write!(
 124             f,
 125             "VtableTraitAlias(alias_def_id={:?}, substs={:?}, nested={:?})",
 126             self.alias_def_id, self.substs, self.nested
 127         )
 128     }
 129 }
 130
 131 impl<'tcx> fmt::Debug for traits::FulfillmentError<'tcx> {
 132     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 133         write!(f, "FulfillmentError({:?},{:?})", self.obligation, self.code)
 134     }
 135 }
 136
 137 impl<'tcx> fmt::Debug for traits::FulfillmentErrorCode<'tcx> {
 138     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 139         match *self {
 140             super::CodeSelectionError(ref e) => write!(f, "{:?}", e),
 141             super::CodeProjectionError(ref e) => write!(f, "{:?}", e),
 142             super::CodeSubtypeError(ref a, ref b) => {
 143                 write!(f, "CodeSubtypeError({:?}, {:?})", a, b)
 144             }
 145             super::CodeAmbiguity => write!(f, "Ambiguity"),
 146         }
 147     }
 148 }
 149
 150 impl<'tcx> fmt::Debug for traits::MismatchedProjectionTypes<'tcx> {
 151     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 152         write!(f, "MismatchedProjectionTypes({:?})", self.err)
 153     }
 154 }
 155
 156 impl<'tcx> fmt::Display for traits::WhereClause<'tcx> {
 157     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 158         use crate::traits::WhereClause::*;
 159
 160         // Bypass `ty::print` because it does not print out anonymous regions.
 161         // FIXME(eddyb) implement a custom `PrettyPrinter`, or move this to `ty::print`.
 162         fn write_region_name<'tcx>(
 163             r: ty::Region<'tcx>,
 164             fmt: &mut fmt::Formatter<'_>,
 165         ) -> fmt::Result {
 166             match r {
 167                 ty::ReLateBound(index, br) => match br {
 168                     ty::BoundRegion::BrNamed(_, name) => write!(fmt, "{}", name),
 169                     ty::BoundRegion::BrAnon(var) => {
 170                         if *index == ty::INNERMOST {
 171                             write!(fmt, "'^{}", var)
 172                         } else {
 173                             write!(fmt, "'^{}_{}", index.index(), var)
 174                         }
 175                     }
 176                     _ => write!(fmt, "'_"),
 177                 },
 178
 179                 _ => write!(fmt, "{}", r),
 180             }
 181         }
 182
 183         match self {
 184             Implemented(trait_ref) => write!(fmt, "Implemented({})", trait_ref),
 185             ProjectionEq(projection) => write!(fmt, "ProjectionEq({})", projection),
 186             RegionOutlives(predicate) => {
 187                 write!(fmt, "RegionOutlives({}: ", predicate.0)?;
 188                 write_region_name(predicate.1, fmt)?;
 189                 write!(fmt, ")")
 190             }
 191             TypeOutlives(predicate) => {
 192                 write!(fmt, "TypeOutlives({}: ", predicate.0)?;
 193                 write_region_name(predicate.1, fmt)?;
 194                 write!(fmt, ")")
 195             }
 196         }
 197     }
 198 }
 199
 200 impl<'tcx> fmt::Display for traits::WellFormed<'tcx> {
 201     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 202         use crate::traits::WellFormed::*;
 203
 204         match self {
 205             Trait(trait_ref) => write!(fmt, "WellFormed({})", trait_ref),
 206             Ty(ty) => write!(fmt, "WellFormed({})", ty),
 207         }
 208     }
 209 }
 210
 211 impl<'tcx> fmt::Display for traits::FromEnv<'tcx> {
 212     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 213         use crate::traits::FromEnv::*;
 214
 215         match self {
 216             Trait(trait_ref) => write!(fmt, "FromEnv({})", trait_ref),
 217             Ty(ty) => write!(fmt, "FromEnv({})", ty),
 218         }
 219     }
 220 }
 221
 222 impl<'tcx> fmt::Display for traits::DomainGoal<'tcx> {
 223     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 224         use crate::traits::DomainGoal::*;
 225
 226         match self {
 227             Holds(wc) => write!(fmt, "{}", wc),
 228             WellFormed(wf) => write!(fmt, "{}", wf),
 229             FromEnv(from_env) => write!(fmt, "{}", from_env),
 230             Normalize(projection) => {
 231                 write!(fmt, "Normalize({} -> {})", projection.projection_ty, projection.ty)
 232             }
 233         }
 234     }
 235 }
 236
 237 impl fmt::Display for traits::QuantifierKind {
 238     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 239         use crate::traits::QuantifierKind::*;
 240
 241         match self {
 242             Universal => write!(fmt, "forall"),
 243             Existential => write!(fmt, "exists"),
 244         }
 245     }
 246 }
 247
 248 /// Collect names for regions / types bound by a quantified goal / clause.
 249 /// This collector does not try to do anything clever like in `ty::print`, it's just used
 250 /// for debug output in tests anyway.
 251 struct BoundNamesCollector {
 252     // Just sort by name because `BoundRegion::BrNamed` does not have a `BoundVar` index anyway.
 253     regions: BTreeSet<Symbol>,
 254
 255     // Sort by `BoundVar` index, so usually this should be equivalent to the order given
 256     // by the list of type parameters.
 257     types: BTreeMap<u32, Symbol>,
 258
 259     binder_index: ty::DebruijnIndex,
 260 }
 261
 262 impl BoundNamesCollector {
 263     fn new() -> Self {
 264         BoundNamesCollector {
 265             regions: BTreeSet::new(),
 266             types: BTreeMap::new(),
 267             binder_index: ty::INNERMOST,
 268         }
 269     }
 270
 271     fn is_empty(&self) -> bool {
 272         self.regions.is_empty() && self.types.is_empty()
 273     }
 274
 275     fn write_names(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 276         let mut start = true;
 277         for r in &self.regions {
 278             if !start {
 279                 write!(fmt, ", ")?;
 280             }
 281             start = false;
 282             write!(fmt, "{}", r)?;
 283         }
 284         for (_, t) in &self.types {
 285             if !start {
 286                 write!(fmt, ", ")?;
 287             }
 288             start = false;
 289             write!(fmt, "{}", t)?;
 290         }
 291         Ok(())
 292     }
 293 }
 294
 295 impl<'tcx> TypeVisitor<'tcx> for BoundNamesCollector {
 296     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> bool {
 297         self.binder_index.shift_in(1);
 298         let result = t.super_visit_with(self);
 299         self.binder_index.shift_out(1);
 300         result
 301     }
 302
 303     fn visit_ty(&mut self, t: Ty<'tcx>) -> bool {
 304         match t.kind {
 305             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 306                 self.types.insert(
 307                     bound_ty.var.as_u32(),
 308                     match bound_ty.kind {
 309                         ty::BoundTyKind::Param(name) => name,
 310                         ty::BoundTyKind::Anon => {
 311                             Symbol::intern(&format!("^{}", bound_ty.var.as_u32()))
 312                         }
 313                     },
 314                 );
 315             }
 316
 317             _ => (),
 318         };
 319
 320         t.super_visit_with(self)
 321     }
 322
 323     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 324         match r {
 325             ty::ReLateBound(index, br) if *index == self.binder_index => match br {
 326                 ty::BoundRegion::BrNamed(_, name) => {
 327                     self.regions.insert(*name);
 328                 }
 329
 330                 ty::BoundRegion::BrAnon(var) => {
 331                     self.regions.insert(Symbol::intern(&format!("'^{}", var)));
 332                 }
 333
 334                 _ => (),
 335             },
 336
 337             _ => (),
 338         };
 339
 340         r.super_visit_with(self)
 341     }
 342 }
 343
 344 impl<'tcx> fmt::Display for traits::Goal<'tcx> {
 345     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 346         use crate::traits::GoalKind::*;
 347
 348         match self {
 349             Implies(hypotheses, goal) => {
 350                 write!(fmt, "if (")?;
 351                 for (index, hyp) in hypotheses.iter().enumerate() {
 352                     if index > 0 {
 353                         write!(fmt, ", ")?;
 354                     }
 355                     write!(fmt, "{}", hyp)?;
 356                 }
 357                 write!(fmt, ") {{ {} }}", goal)
 358             }
 359             And(goal1, goal2) => write!(fmt, "({} && {})", goal1, goal2),
 360             Not(goal) => write!(fmt, "not {{ {} }}", goal),
 361             DomainGoal(goal) => write!(fmt, "{}", goal),
 362             Quantified(qkind, goal) => {
 363                 let mut collector = BoundNamesCollector::new();
 364                 goal.skip_binder().visit_with(&mut collector);
 365
 366                 if !collector.is_empty() {
 367                     write!(fmt, "{}<", qkind)?;
 368                     collector.write_names(fmt)?;
 369                     write!(fmt, "> {{ ")?;
 370                 }
 371
 372                 write!(fmt, "{}", goal.skip_binder())?;
 373
 374                 if !collector.is_empty() {
 375                     write!(fmt, " }}")?;
 376                 }
 377
 378                 Ok(())
 379             }
 380             Subtype(a, b) => write!(fmt, "{} <: {}", a, b),
 381             CannotProve => write!(fmt, "CannotProve"),
 382         }
 383     }
 384 }
 385
 386 impl<'tcx> fmt::Display for traits::ProgramClause<'tcx> {
 387     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 388         let traits::ProgramClause { goal, hypotheses, .. } = self;
 389         write!(fmt, "{}", goal)?;
 390         if !hypotheses.is_empty() {
 391             write!(fmt, " :- ")?;
 392             for (index, condition) in hypotheses.iter().enumerate() {
 393                 if index > 0 {
 394                     write!(fmt, ", ")?;
 395                 }
 396                 write!(fmt, "{}", condition)?;
 397             }
 398         }
 399         write!(fmt, ".")
 400     }
 401 }
 402
 403 impl<'tcx> fmt::Display for traits::Clause<'tcx> {
 404     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 405         use crate::traits::Clause::*;
 406
 407         match self {
 408             Implies(clause) => write!(fmt, "{}", clause),
 409             ForAll(clause) => {
 410                 let mut collector = BoundNamesCollector::new();
 411                 clause.skip_binder().visit_with(&mut collector);
 412
 413                 if !collector.is_empty() {
 414                     write!(fmt, "forall<")?;
 415                     collector.write_names(fmt)?;
 416                     write!(fmt, "> {{ ")?;
 417                 }
 418
 419                 write!(fmt, "{}", clause.skip_binder())?;
 420
 421                 if !collector.is_empty() {
 422                     write!(fmt, " }}")?;
 423                 }
 424
 425                 Ok(())
 426             }
 427         }
 428     }
 429 }
 430
 431 ///////////////////////////////////////////////////////////////////////////
 432 // Lift implementations
 433
 434 impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
 435     type Lifted = traits::SelectionError<'tcx>;
 436     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 437         match *self {
 438             super::Unimplemented => Some(super::Unimplemented),
 439             super::OutputTypeParameterMismatch(a, b, ref err) => {
 440                 tcx.lift(&(a, b)).and_then(|(a, b)| {
 441                     tcx.lift(err).map(|err| super::OutputTypeParameterMismatch(a, b, err))
 442                 })
 443             }
 444             super::TraitNotObjectSafe(def_id) => Some(super::TraitNotObjectSafe(def_id)),
 445             super::ConstEvalFailure(err) => Some(super::ConstEvalFailure(err)),
 446             super::Overflow => Some(super::Overflow),
 447         }
 448     }
 449 }
 450
 451 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
 452     type Lifted = traits::ObligationCauseCode<'tcx>;
 453     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 454         match *self {
 455             super::ReturnNoExpression => Some(super::ReturnNoExpression),
 456             super::MiscObligation => Some(super::MiscObligation),
 457             super::SliceOrArrayElem => Some(super::SliceOrArrayElem),
 458             super::TupleElem => Some(super::TupleElem),
 459             super::ProjectionWf(proj) => tcx.lift(&proj).map(super::ProjectionWf),
 460             super::ItemObligation(def_id) => Some(super::ItemObligation(def_id)),
 461             super::BindingObligation(def_id, span) => Some(super::BindingObligation(def_id, span)),
 462             super::ReferenceOutlivesReferent(ty) => {
 463                 tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
 464             }
 465             super::ObjectTypeBound(ty, r) => tcx
 466                 .lift(&ty)
 467                 .and_then(|ty| tcx.lift(&r).and_then(|r| Some(super::ObjectTypeBound(ty, r)))),
 468             super::ObjectCastObligation(ty) => tcx.lift(&ty).map(super::ObjectCastObligation),
 469             super::Coercion { source, target } => {
 470                 Some(super::Coercion { source: tcx.lift(&source)?, target: tcx.lift(&target)? })
 471             }
 472             super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
 473             super::TupleInitializerSized => Some(super::TupleInitializerSized),
 474             super::StructInitializerSized => Some(super::StructInitializerSized),
 475             super::VariableType(id) => Some(super::VariableType(id)),
 476             super::ReturnValue(id) => Some(super::ReturnValue(id)),
 477             super::ReturnType => Some(super::ReturnType),
 478             super::SizedArgumentType => Some(super::SizedArgumentType),
 479             super::SizedReturnType => Some(super::SizedReturnType),
 480             super::SizedYieldType => Some(super::SizedYieldType),
 481             super::RepeatVec(suggest_flag) => Some(super::RepeatVec(suggest_flag)),
 482             super::FieldSized { adt_kind, last } => Some(super::FieldSized { adt_kind, last }),
 483             super::ConstSized => Some(super::ConstSized),
 484             super::ConstPatternStructural => Some(super::ConstPatternStructural),
 485             super::SharedStatic => Some(super::SharedStatic),
 486             super::BuiltinDerivedObligation(ref cause) => {
 487                 tcx.lift(cause).map(super::BuiltinDerivedObligation)
 488             }
 489             super::ImplDerivedObligation(ref cause) => {
 490                 tcx.lift(cause).map(super::ImplDerivedObligation)
 491             }
 492             super::CompareImplMethodObligation {
 493                 item_name,
 494                 impl_item_def_id,
 495                 trait_item_def_id,
 496             } => Some(super::CompareImplMethodObligation {
 497                 item_name,
 498                 impl_item_def_id,
 499                 trait_item_def_id,
 500             }),
 501             super::CompareImplTypeObligation { item_name, impl_item_def_id, trait_item_def_id } => {
 502                 Some(super::CompareImplTypeObligation {
 503                     item_name,
 504                     impl_item_def_id,
 505                     trait_item_def_id,
 506                 })
 507             }
 508             super::ExprAssignable => Some(super::ExprAssignable),
 509             super::MatchExpressionArm(box super::MatchExpressionArmCause {
 510                 arm_span,
 511                 source,
 512                 ref prior_arms,
 513                 last_ty,
 514                 scrut_hir_id,
 515             }) => tcx.lift(&last_ty).map(|last_ty| {
 516                 super::MatchExpressionArm(box super::MatchExpressionArmCause {
 517                     arm_span,
 518                     source,
 519                     prior_arms: prior_arms.clone(),
 520                     last_ty,
 521                     scrut_hir_id,
 522                 })
 523             }),
 524             super::Pattern { span, root_ty, origin_expr } => {
 525                 tcx.lift(&root_ty).map(|root_ty| super::Pattern { span, root_ty, origin_expr })
 526             }
 527             super::IfExpression(box super::IfExpressionCause { then, outer, semicolon }) => {
 528                 Some(super::IfExpression(box super::IfExpressionCause { then, outer, semicolon }))
 529             }
 530             super::IfExpressionWithNoElse => Some(super::IfExpressionWithNoElse),
 531             super::MainFunctionType => Some(super::MainFunctionType),
 532             super::StartFunctionType => Some(super::StartFunctionType),
 533             super::IntrinsicType => Some(super::IntrinsicType),
 534             super::MethodReceiver => Some(super::MethodReceiver),
 535             super::BlockTailExpression(id) => Some(super::BlockTailExpression(id)),
 536             super::TrivialBound => Some(super::TrivialBound),
 537             super::AssocTypeBound(ref data) => Some(super::AssocTypeBound(data.clone())),
 538         }
 539     }
 540 }
 541
 542 impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
 543     type Lifted = traits::DerivedObligationCause<'tcx>;
 544     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 545         tcx.lift(&self.parent_trait_ref).and_then(|trait_ref| {
 546             tcx.lift(&*self.parent_code).map(|code| traits::DerivedObligationCause {
 547                 parent_trait_ref: trait_ref,
 548                 parent_code: Rc::new(code),
 549             })
 550         })
 551     }
 552 }
 553
 554 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
 555     type Lifted = traits::ObligationCause<'tcx>;
 556     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 557         tcx.lift(&self.code).map(|code| traits::ObligationCause {
 558             span: self.span,
 559             body_id: self.body_id,
 560             code,
 561         })
 562     }
 563 }
 564
 565 // For codegen only.
 566 impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
 567     type Lifted = traits::Vtable<'tcx, ()>;
 568     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 569         match self.clone() {
 570             traits::VtableImpl(traits::VtableImplData { impl_def_id, substs, nested }) => {
 571                 tcx.lift(&substs).map(|substs| {
 572                     traits::VtableImpl(traits::VtableImplData { impl_def_id, substs, nested })
 573                 })
 574             }
 575             traits::VtableAutoImpl(t) => Some(traits::VtableAutoImpl(t)),
 576             traits::VtableGenerator(traits::VtableGeneratorData {
 577                 generator_def_id,
 578                 substs,
 579                 nested,
 580             }) => tcx.lift(&substs).map(|substs| {
 581                 traits::VtableGenerator(traits::VtableGeneratorData {
 582                     generator_def_id: generator_def_id,
 583                     substs: substs,
 584                     nested: nested,
 585                 })
 586             }),
 587             traits::VtableClosure(traits::VtableClosureData { closure_def_id, substs, nested }) => {
 588                 tcx.lift(&substs).map(|substs| {
 589                     traits::VtableClosure(traits::VtableClosureData {
 590                         closure_def_id,
 591                         substs,
 592                         nested,
 593                     })
 594                 })
 595             }
 596             traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested }) => {
 597                 tcx.lift(&fn_ty).map(|fn_ty| {
 598                     traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested })
 599                 })
 600             }
 601             traits::VtableParam(n) => Some(traits::VtableParam(n)),
 602             traits::VtableBuiltin(n) => Some(traits::VtableBuiltin(n)),
 603             traits::VtableObject(traits::VtableObjectData {
 604                 upcast_trait_ref,
 605                 vtable_base,
 606                 nested,
 607             }) => tcx.lift(&upcast_trait_ref).map(|trait_ref| {
 608                 traits::VtableObject(traits::VtableObjectData {
 609                     upcast_trait_ref: trait_ref,
 610                     vtable_base,
 611                     nested,
 612                 })
 613             }),
 614             traits::VtableTraitAlias(traits::VtableTraitAliasData {
 615                 alias_def_id,
 616                 substs,
 617                 nested,
 618             }) => tcx.lift(&substs).map(|substs| {
 619                 traits::VtableTraitAlias(traits::VtableTraitAliasData {
 620                     alias_def_id,
 621                     substs,
 622                     nested,
 623                 })
 624             }),
 625         }
 626     }
 627 }
 628
 629 impl<'a, 'tcx> Lift<'tcx> for traits::Environment<'a> {
 630     type Lifted = traits::Environment<'tcx>;
 631     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 632         tcx.lift(&self.clauses).map(|clauses| traits::Environment { clauses })
 633     }
 634 }
 635
 636 impl<'a, 'tcx, G: Lift<'tcx>> Lift<'tcx> for traits::InEnvironment<'a, G> {
 637     type Lifted = traits::InEnvironment<'tcx, G::Lifted>;
 638     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 639         tcx.lift(&self.environment).and_then(|environment| {
 640             tcx.lift(&self.goal).map(|goal| traits::InEnvironment { environment, goal })
 641         })
 642     }
 643 }
 644
 645 impl<'tcx, C> Lift<'tcx> for chalk_engine::ExClause<C>
 646 where
 647     C: chalk_engine::context::Context + Clone,
 648     C: traits::ChalkContextLift<'tcx>,
 649 {
 650     type Lifted = C::LiftedExClause;
 651
 652     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 653         <C as traits::ChalkContextLift>::lift_ex_clause_to_tcx(self, tcx)
 654     }
 655 }
 656
 657 impl<'tcx, C> Lift<'tcx> for chalk_engine::DelayedLiteral<C>
 658 where
 659     C: chalk_engine::context::Context + Clone,
 660     C: traits::ChalkContextLift<'tcx>,
 661 {
 662     type Lifted = C::LiftedDelayedLiteral;
 663
 664     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 665         <C as traits::ChalkContextLift>::lift_delayed_literal_to_tcx(self, tcx)
 666     }
 667 }
 668
 669 impl<'tcx, C> Lift<'tcx> for chalk_engine::Literal<C>
 670 where
 671     C: chalk_engine::context::Context + Clone,
 672     C: traits::ChalkContextLift<'tcx>,
 673 {
 674     type Lifted = C::LiftedLiteral;
 675
 676     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 677         <C as traits::ChalkContextLift>::lift_literal_to_tcx(self, tcx)
 678     }
 679 }
 680
 681 ///////////////////////////////////////////////////////////////////////////
 682 // TypeFoldable implementations.
 683
 684 impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> {
 685     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 686         traits::Obligation {
 687             cause: self.cause.clone(),
 688             recursion_depth: self.recursion_depth,
 689             predicate: self.predicate.fold_with(folder),
 690             param_env: self.param_env.fold_with(folder),
 691         }
 692     }
 693
 694     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 695         self.predicate.visit_with(visitor)
 696     }
 697 }
 698
 699 CloneTypeFoldableAndLiftImpls! {
 700     traits::QuantifierKind,
 701 }
 702
 703 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Goal<'tcx>> {
 704     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 705         let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
 706         folder.tcx().intern_goals(&v)
 707     }
 708
 709     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 710         self.iter().any(|t| t.visit_with(visitor))
 711     }
 712 }
 713
 714 impl<'tcx> TypeFoldable<'tcx> for traits::Goal<'tcx> {
 715     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 716         let v = (**self).fold_with(folder);
 717         folder.tcx().mk_goal(v)
 718     }
 719
 720     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 721         (**self).visit_with(visitor)
 722     }
 723 }
 724
 725 CloneTypeFoldableAndLiftImpls! {
 726     traits::ProgramClauseCategory,
 727 }
 728
 729 impl<'tcx> TypeFoldable<'tcx> for traits::Clauses<'tcx> {
 730     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 731         let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
 732         folder.tcx().intern_clauses(&v)
 733     }
 734
 735     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 736         self.iter().any(|t| t.visit_with(visitor))
 737     }
 738 }
 739
 740 impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::ExClause<C>
 741 where
 742     C: traits::ExClauseFold<'tcx>,
 743     C::Substitution: Clone,
 744     C::RegionConstraint: Clone,
 745 {
 746     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 747         <C as traits::ExClauseFold>::fold_ex_clause_with(self, folder)
 748     }
 749
 750     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 751         <C as traits::ExClauseFold>::visit_ex_clause_with(self, visitor)
 752     }
 753 }
 754
 755 EnumTypeFoldableImpl! {
 756     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::DelayedLiteral<C> {
 757         (chalk_engine::DelayedLiteral::CannotProve)(a),
 758         (chalk_engine::DelayedLiteral::Negative)(a),
 759         (chalk_engine::DelayedLiteral::Positive)(a, b),
 760     } where
 761         C: chalk_engine::context::Context<CanonicalConstrainedSubst: TypeFoldable<'tcx>> + Clone,
 762 }
 763
 764 EnumTypeFoldableImpl! {
 765     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::Literal<C> {
 766         (chalk_engine::Literal::Negative)(a),
 767         (chalk_engine::Literal::Positive)(a),
 768     } where
 769         C: chalk_engine::context::Context<GoalInEnvironment: Clone + TypeFoldable<'tcx>> + Clone,
 770 }
 771
 772 CloneTypeFoldableAndLiftImpls! {
 773     chalk_engine::TableIndex,
 774 }