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 EnumLiftImpl! {
 654     impl<'a, 'tcx> Lift<'tcx> for traits::WhereClause<'a> {
 655         type Lifted = traits::WhereClause<'tcx>;
 656         (traits::WhereClause::Implemented)(trait_ref),
 657         (traits::WhereClause::ProjectionEq)(projection),
 658         (traits::WhereClause::TypeOutlives)(ty_outlives),
 659         (traits::WhereClause::RegionOutlives)(region_outlives),
 660     }
 661 }
 662
 663 EnumLiftImpl! {
 664     impl<'a, 'tcx> Lift<'tcx> for traits::WellFormed<'a> {
 665         type Lifted = traits::WellFormed<'tcx>;
 666         (traits::WellFormed::Trait)(trait_ref),
 667         (traits::WellFormed::Ty)(ty),
 668     }
 669 }
 670
 671 EnumLiftImpl! {
 672     impl<'a, 'tcx> Lift<'tcx> for traits::FromEnv<'a> {
 673         type Lifted = traits::FromEnv<'tcx>;
 674         (traits::FromEnv::Trait)(trait_ref),
 675         (traits::FromEnv::Ty)(ty),
 676     }
 677 }
 678
 679 EnumLiftImpl! {
 680     impl<'a, 'tcx> Lift<'tcx> for traits::DomainGoal<'a> {
 681         type Lifted = traits::DomainGoal<'tcx>;
 682         (traits::DomainGoal::Holds)(wc),
 683         (traits::DomainGoal::WellFormed)(wf),
 684         (traits::DomainGoal::FromEnv)(from_env),
 685         (traits::DomainGoal::Normalize)(projection),
 686     }
 687 }
 688
 689 EnumLiftImpl! {
 690     impl<'a, 'tcx> Lift<'tcx> for traits::GoalKind<'a> {
 691         type Lifted = traits::GoalKind<'tcx>;
 692         (traits::GoalKind::Implies)(hypotheses, goal),
 693         (traits::GoalKind::And)(goal1, goal2),
 694         (traits::GoalKind::Not)(goal),
 695         (traits::GoalKind::DomainGoal)(domain_goal),
 696         (traits::GoalKind::Quantified)(kind, goal),
 697         (traits::GoalKind::Subtype)(a, b),
 698         (traits::GoalKind::CannotProve),
 699     }
 700 }
 701
 702 impl<'a, 'tcx> Lift<'tcx> for traits::Environment<'a> {
 703     type Lifted = traits::Environment<'tcx>;
 704     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 705         tcx.lift(&self.clauses).map(|clauses| {
 706             traits::Environment {
 707                 clauses,
 708             }
 709         })
 710     }
 711 }
 712
 713 impl<'a, 'tcx, G: Lift<'tcx>> Lift<'tcx> for traits::InEnvironment<'a, G> {
 714     type Lifted = traits::InEnvironment<'tcx, G::Lifted>;
 715     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 716         tcx.lift(&self.environment).and_then(|environment| {
 717             tcx.lift(&self.goal).map(|goal| {
 718                 traits::InEnvironment {
 719                     environment,
 720                     goal,
 721                 }
 722             })
 723         })
 724     }
 725 }
 726
 727 impl<'tcx, C> Lift<'tcx> for chalk_engine::ExClause<C>
 728 where
 729     C: chalk_engine::context::Context + Clone,
 730     C: traits::ChalkContextLift<'tcx>,
 731 {
 732     type Lifted = C::LiftedExClause;
 733
 734     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 735         <C as traits::ChalkContextLift>::lift_ex_clause_to_tcx(self, tcx)
 736     }
 737 }
 738
 739 impl<'tcx, C> Lift<'tcx> for chalk_engine::DelayedLiteral<C>
 740 where
 741     C: chalk_engine::context::Context + Clone,
 742     C: traits::ChalkContextLift<'tcx>,
 743 {
 744     type Lifted = C::LiftedDelayedLiteral;
 745
 746     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 747         <C as traits::ChalkContextLift>::lift_delayed_literal_to_tcx(self, tcx)
 748     }
 749 }
 750
 751 impl<'tcx, C> Lift<'tcx> for chalk_engine::Literal<C>
 752 where
 753     C: chalk_engine::context::Context + Clone,
 754     C: traits::ChalkContextLift<'tcx>,
 755 {
 756     type Lifted = C::LiftedLiteral;
 757
 758     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 759         <C as traits::ChalkContextLift>::lift_literal_to_tcx(self, tcx)
 760     }
 761 }
 762
 763 ///////////////////////////////////////////////////////////////////////////
 764 // TypeFoldable implementations.
 765
 766 impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> {
 767     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 768         traits::Obligation {
 769             cause: self.cause.clone(),
 770             recursion_depth: self.recursion_depth,
 771             predicate: self.predicate.fold_with(folder),
 772             param_env: self.param_env.fold_with(folder),
 773         }
 774     }
 775
 776     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 777         self.predicate.visit_with(visitor)
 778     }
 779 }
 780
 781 BraceStructTypeFoldableImpl! {
 782     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableImplData<'tcx, N> {
 783         impl_def_id, substs, nested
 784     } where N: TypeFoldable<'tcx>
 785 }
 786
 787 BraceStructTypeFoldableImpl! {
 788     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableGeneratorData<'tcx, N> {
 789         generator_def_id, substs, nested
 790     } where N: TypeFoldable<'tcx>
 791 }
 792
 793 BraceStructTypeFoldableImpl! {
 794     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableClosureData<'tcx, N> {
 795         closure_def_id, substs, nested
 796     } where N: TypeFoldable<'tcx>
 797 }
 798
 799 BraceStructTypeFoldableImpl! {
 800     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableAutoImplData<N> {
 801         trait_def_id, nested
 802     } where N: TypeFoldable<'tcx>
 803 }
 804
 805 BraceStructTypeFoldableImpl! {
 806     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableBuiltinData<N> {
 807         nested
 808     } where N: TypeFoldable<'tcx>
 809 }
 810
 811 BraceStructTypeFoldableImpl! {
 812     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableObjectData<'tcx, N> {
 813         upcast_trait_ref, vtable_base, nested
 814     } where N: TypeFoldable<'tcx>
 815 }
 816
 817 BraceStructTypeFoldableImpl! {
 818     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableFnPointerData<'tcx, N> {
 819         fn_ty,
 820         nested
 821     } where N: TypeFoldable<'tcx>
 822 }
 823
 824 BraceStructTypeFoldableImpl! {
 825     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableTraitAliasData<'tcx, N> {
 826         alias_def_id, substs, nested
 827     } where N: TypeFoldable<'tcx>
 828 }
 829
 830 EnumTypeFoldableImpl! {
 831     impl<'tcx, N> TypeFoldable<'tcx> for traits::Vtable<'tcx, N> {
 832         (traits::VtableImpl)(a),
 833         (traits::VtableAutoImpl)(a),
 834         (traits::VtableGenerator)(a),
 835         (traits::VtableClosure)(a),
 836         (traits::VtableFnPointer)(a),
 837         (traits::VtableParam)(a),
 838         (traits::VtableBuiltin)(a),
 839         (traits::VtableObject)(a),
 840         (traits::VtableTraitAlias)(a),
 841     } where N: TypeFoldable<'tcx>
 842 }
 843
 844 BraceStructTypeFoldableImpl! {
 845     impl<'tcx, T> TypeFoldable<'tcx> for Normalized<'tcx, T> {
 846         value,
 847         obligations
 848     } where T: TypeFoldable<'tcx>
 849 }
 850
 851 EnumTypeFoldableImpl! {
 852     impl<'tcx> TypeFoldable<'tcx> for traits::WhereClause<'tcx> {
 853         (traits::WhereClause::Implemented)(trait_ref),
 854         (traits::WhereClause::ProjectionEq)(projection),
 855         (traits::WhereClause::TypeOutlives)(ty_outlives),
 856         (traits::WhereClause::RegionOutlives)(region_outlives),
 857     }
 858 }
 859
 860 EnumTypeFoldableImpl! {
 861     impl<'tcx> TypeFoldable<'tcx> for traits::WellFormed<'tcx> {
 862         (traits::WellFormed::Trait)(trait_ref),
 863         (traits::WellFormed::Ty)(ty),
 864     }
 865 }
 866
 867 EnumTypeFoldableImpl! {
 868     impl<'tcx> TypeFoldable<'tcx> for traits::FromEnv<'tcx> {
 869         (traits::FromEnv::Trait)(trait_ref),
 870         (traits::FromEnv::Ty)(ty),
 871     }
 872 }
 873
 874 EnumTypeFoldableImpl! {
 875     impl<'tcx> TypeFoldable<'tcx> for traits::DomainGoal<'tcx> {
 876         (traits::DomainGoal::Holds)(wc),
 877         (traits::DomainGoal::WellFormed)(wf),
 878         (traits::DomainGoal::FromEnv)(from_env),
 879         (traits::DomainGoal::Normalize)(projection),
 880     }
 881 }
 882
 883 CloneTypeFoldableAndLiftImpls! {
 884     traits::QuantifierKind,
 885 }
 886
 887 EnumTypeFoldableImpl! {
 888     impl<'tcx> TypeFoldable<'tcx> for traits::GoalKind<'tcx> {
 889         (traits::GoalKind::Implies)(hypotheses, goal),
 890         (traits::GoalKind::And)(goal1, goal2),
 891         (traits::GoalKind::Not)(goal),
 892         (traits::GoalKind::DomainGoal)(domain_goal),
 893         (traits::GoalKind::Quantified)(qkind, goal),
 894         (traits::GoalKind::Subtype)(a, b),
 895         (traits::GoalKind::CannotProve),
 896     }
 897 }
 898
 899 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Goal<'tcx>> {
 900     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 901         let v = self.iter()
 902             .map(|t| t.fold_with(folder))
 903             .collect::<SmallVec<[_; 8]>>();
 904         folder.tcx().intern_goals(&v)
 905     }
 906
 907     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 908         self.iter().any(|t| t.visit_with(visitor))
 909     }
 910 }
 911
 912 impl<'tcx> TypeFoldable<'tcx> for traits::Goal<'tcx> {
 913     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 914         let v = (**self).fold_with(folder);
 915         folder.tcx().mk_goal(v)
 916     }
 917
 918     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 919         (**self).visit_with(visitor)
 920     }
 921 }
 922
 923 BraceStructTypeFoldableImpl! {
 924     impl<'tcx> TypeFoldable<'tcx> for traits::ProgramClause<'tcx> {
 925         goal,
 926         hypotheses,
 927         category,
 928     }
 929 }
 930
 931 CloneTypeFoldableAndLiftImpls! {
 932     traits::ProgramClauseCategory,
 933 }
 934
 935 EnumTypeFoldableImpl! {
 936     impl<'tcx> TypeFoldable<'tcx> for traits::Clause<'tcx> {
 937         (traits::Clause::Implies)(clause),
 938         (traits::Clause::ForAll)(clause),
 939     }
 940 }
 941
 942 BraceStructTypeFoldableImpl! {
 943     impl<'tcx> TypeFoldable<'tcx> for traits::Environment<'tcx> { clauses }
 944 }
 945
 946 BraceStructTypeFoldableImpl! {
 947     impl<'tcx, G> TypeFoldable<'tcx> for traits::InEnvironment<'tcx, G> {
 948         environment,
 949         goal
 950     } where G: TypeFoldable<'tcx>
 951 }
 952
 953 impl<'tcx> TypeFoldable<'tcx> for traits::Clauses<'tcx> {
 954     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 955         let v = self.iter()
 956             .map(|t| t.fold_with(folder))
 957             .collect::<SmallVec<[_; 8]>>();
 958         folder.tcx().intern_clauses(&v)
 959     }
 960
 961     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 962         self.iter().any(|t| t.visit_with(visitor))
 963     }
 964 }
 965
 966 impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::ExClause<C>
 967 where
 968     C: traits::ExClauseFold<'tcx>,
 969     C::Substitution: Clone,
 970     C::RegionConstraint: Clone,
 971 {
 972     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 973         <C as traits::ExClauseFold>::fold_ex_clause_with(
 974             self,
 975             folder,
 976         )
 977     }
 978
 979     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 980         <C as traits::ExClauseFold>::visit_ex_clause_with(
 981             self,
 982             visitor,
 983         )
 984     }
 985 }
 986
 987 EnumTypeFoldableImpl! {
 988     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::DelayedLiteral<C> {
 989         (chalk_engine::DelayedLiteral::CannotProve)(a),
 990         (chalk_engine::DelayedLiteral::Negative)(a),
 991         (chalk_engine::DelayedLiteral::Positive)(a, b),
 992     } where
 993         C: chalk_engine::context::Context<CanonicalConstrainedSubst: TypeFoldable<'tcx>> + Clone,
 994 }
 995
 996 EnumTypeFoldableImpl! {
 997     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::Literal<C> {
 998         (chalk_engine::Literal::Negative)(a),
 999         (chalk_engine::Literal::Positive)(a),
1000     } where
1001         C: chalk_engine::context::Context<GoalInEnvironment: Clone + TypeFoldable<'tcx>> + Clone,
1002 }
1003
1004 CloneTypeFoldableAndLiftImpls! {
1005     chalk_engine::TableIndex,
1006 }