src/librustc/traits/structural_impls.rs

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