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::InternedString;
   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<InternedString>,
 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, InternedString>,
 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.sty {
 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                             InternedString::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(InternedString::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::ReferenceOutlivesReferent(ty) => {
 476                 tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
 477             }
 478             super::ObjectTypeBound(ty, r) => tcx.lift(&ty).and_then(|ty|
 479                 tcx.lift(&r)
 480                    .and_then(|r| Some(super::ObjectTypeBound(ty, r)))
 481             ),
 482             super::ObjectCastObligation(ty) => tcx.lift(&ty).map(super::ObjectCastObligation),
 483             super::AssignmentLhsSized => Some(super::AssignmentLhsSized),
 484             super::TupleInitializerSized => Some(super::TupleInitializerSized),
 485             super::StructInitializerSized => Some(super::StructInitializerSized),
 486             super::VariableType(id) => Some(super::VariableType(id)),
 487             super::ReturnType(id) => Some(super::ReturnType(id)),
 488             super::SizedArgumentType => Some(super::SizedArgumentType),
 489             super::SizedReturnType => Some(super::SizedReturnType),
 490             super::SizedYieldType => Some(super::SizedYieldType),
 491             super::RepeatVec => Some(super::RepeatVec),
 492             super::FieldSized { adt_kind, last } => Some(super::FieldSized { adt_kind, last }),
 493             super::ConstSized => Some(super::ConstSized),
 494             super::SharedStatic => Some(super::SharedStatic),
 495             super::BuiltinDerivedObligation(ref cause) => {
 496                 tcx.lift(cause).map(super::BuiltinDerivedObligation)
 497             }
 498             super::ImplDerivedObligation(ref cause) => {
 499                 tcx.lift(cause).map(super::ImplDerivedObligation)
 500             }
 501             super::CompareImplMethodObligation {
 502                 item_name,
 503                 impl_item_def_id,
 504                 trait_item_def_id,
 505             } => Some(super::CompareImplMethodObligation {
 506                 item_name,
 507                 impl_item_def_id,
 508                 trait_item_def_id,
 509             }),
 510             super::ExprAssignable => Some(super::ExprAssignable),
 511             super::MatchExpressionArm {
 512                 arm_span,
 513                 source,
 514                 ref prior_arms,
 515                 last_ty,
 516                 discrim_hir_id,
 517             } => {
 518                 tcx.lift(&last_ty).map(|last_ty| {
 519                     super::MatchExpressionArm {
 520                         arm_span,
 521                         source,
 522                         prior_arms: prior_arms.clone(),
 523                         last_ty,
 524                         discrim_hir_id,
 525                     }
 526                 })
 527             }
 528             super::MatchExpressionArmPattern { span, ty } => {
 529                 tcx.lift(&ty).map(|ty| super::MatchExpressionArmPattern { span, ty })
 530             }
 531             super::IfExpression { then, outer, semicolon } => Some(super::IfExpression {
 532                 then,
 533                 outer,
 534                 semicolon,
 535             }),
 536             super::IfExpressionWithNoElse => Some(super::IfExpressionWithNoElse),
 537             super::MainFunctionType => Some(super::MainFunctionType),
 538             super::StartFunctionType => Some(super::StartFunctionType),
 539             super::IntrinsicType => Some(super::IntrinsicType),
 540             super::MethodReceiver => Some(super::MethodReceiver),
 541             super::BlockTailExpression(id) => Some(super::BlockTailExpression(id)),
 542             super::TrivialBound => Some(super::TrivialBound),
 543         }
 544     }
 545 }
 546
 547 impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
 548     type Lifted = traits::DerivedObligationCause<'tcx>;
 549     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 550         tcx.lift(&self.parent_trait_ref).and_then(|trait_ref|
 551             tcx.lift(&*self.parent_code)
 552                .map(|code| traits::DerivedObligationCause {
 553                    parent_trait_ref: trait_ref,
 554                    parent_code: Rc::new(code),
 555                })
 556         )
 557     }
 558 }
 559
 560 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
 561     type Lifted = traits::ObligationCause<'tcx>;
 562     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 563         tcx.lift(&self.code).map(|code| traits::ObligationCause {
 564             span: self.span,
 565             body_id: self.body_id,
 566             code,
 567         })
 568     }
 569 }
 570
 571 // For codegen only.
 572 impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
 573     type Lifted = traits::Vtable<'tcx, ()>;
 574     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 575         match self.clone() {
 576             traits::VtableImpl(traits::VtableImplData {
 577                 impl_def_id,
 578                 substs,
 579                 nested,
 580             }) => tcx.lift(&substs).map(|substs|
 581                 traits::VtableImpl(traits::VtableImplData {
 582                     impl_def_id,
 583                     substs,
 584                     nested,
 585                 })
 586             ),
 587             traits::VtableAutoImpl(t) => Some(traits::VtableAutoImpl(t)),
 588             traits::VtableGenerator(traits::VtableGeneratorData {
 589                 generator_def_id,
 590                 substs,
 591                 nested,
 592             }) => tcx.lift(&substs).map(|substs|
 593                 traits::VtableGenerator(traits::VtableGeneratorData {
 594                     generator_def_id: generator_def_id,
 595                     substs: substs,
 596                     nested: nested,
 597                 })
 598             ),
 599             traits::VtableClosure(traits::VtableClosureData {
 600                 closure_def_id,
 601                 substs,
 602                 nested,
 603             }) => tcx.lift(&substs).map(|substs|
 604                 traits::VtableClosure(traits::VtableClosureData {
 605                     closure_def_id,
 606                     substs,
 607                     nested,
 608                 })
 609             ),
 610             traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested }) => {
 611                 tcx.lift(&fn_ty).map(|fn_ty|
 612                     traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested })
 613                 )
 614             }
 615             traits::VtableParam(n) => Some(traits::VtableParam(n)),
 616             traits::VtableBuiltin(n) => Some(traits::VtableBuiltin(n)),
 617             traits::VtableObject(traits::VtableObjectData {
 618                 upcast_trait_ref,
 619                 vtable_base,
 620                 nested,
 621             }) => tcx.lift(&upcast_trait_ref).map(|trait_ref|
 622                 traits::VtableObject(traits::VtableObjectData {
 623                     upcast_trait_ref: trait_ref,
 624                     vtable_base,
 625                     nested,
 626                 })
 627             ),
 628             traits::VtableTraitAlias(traits::VtableTraitAliasData {
 629                 alias_def_id,
 630                 substs,
 631                 nested,
 632             }) => tcx.lift(&substs).map(|substs|
 633                 traits::VtableTraitAlias(traits::VtableTraitAliasData {
 634                     alias_def_id,
 635                     substs,
 636                     nested,
 637                 })
 638             ),
 639         }
 640     }
 641 }
 642
 643 EnumLiftImpl! {
 644     impl<'a, 'tcx> Lift<'tcx> for traits::WhereClause<'a> {
 645         type Lifted = traits::WhereClause<'tcx>;
 646         (traits::WhereClause::Implemented)(trait_ref),
 647         (traits::WhereClause::ProjectionEq)(projection),
 648         (traits::WhereClause::TypeOutlives)(ty_outlives),
 649         (traits::WhereClause::RegionOutlives)(region_outlives),
 650     }
 651 }
 652
 653 EnumLiftImpl! {
 654     impl<'a, 'tcx> Lift<'tcx> for traits::WellFormed<'a> {
 655         type Lifted = traits::WellFormed<'tcx>;
 656         (traits::WellFormed::Trait)(trait_ref),
 657         (traits::WellFormed::Ty)(ty),
 658     }
 659 }
 660
 661 EnumLiftImpl! {
 662     impl<'a, 'tcx> Lift<'tcx> for traits::FromEnv<'a> {
 663         type Lifted = traits::FromEnv<'tcx>;
 664         (traits::FromEnv::Trait)(trait_ref),
 665         (traits::FromEnv::Ty)(ty),
 666     }
 667 }
 668
 669 EnumLiftImpl! {
 670     impl<'a, 'tcx> Lift<'tcx> for traits::DomainGoal<'a> {
 671         type Lifted = traits::DomainGoal<'tcx>;
 672         (traits::DomainGoal::Holds)(wc),
 673         (traits::DomainGoal::WellFormed)(wf),
 674         (traits::DomainGoal::FromEnv)(from_env),
 675         (traits::DomainGoal::Normalize)(projection),
 676     }
 677 }
 678
 679 EnumLiftImpl! {
 680     impl<'a, 'tcx> Lift<'tcx> for traits::GoalKind<'a> {
 681         type Lifted = traits::GoalKind<'tcx>;
 682         (traits::GoalKind::Implies)(hypotheses, goal),
 683         (traits::GoalKind::And)(goal1, goal2),
 684         (traits::GoalKind::Not)(goal),
 685         (traits::GoalKind::DomainGoal)(domain_goal),
 686         (traits::GoalKind::Quantified)(kind, goal),
 687         (traits::GoalKind::Subtype)(a, b),
 688         (traits::GoalKind::CannotProve),
 689     }
 690 }
 691
 692 impl<'a, 'tcx> Lift<'tcx> for traits::Environment<'a> {
 693     type Lifted = traits::Environment<'tcx>;
 694     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 695         tcx.lift(&self.clauses).map(|clauses| {
 696             traits::Environment {
 697                 clauses,
 698             }
 699         })
 700     }
 701 }
 702
 703 impl<'a, 'tcx, G: Lift<'tcx>> Lift<'tcx> for traits::InEnvironment<'a, G> {
 704     type Lifted = traits::InEnvironment<'tcx, G::Lifted>;
 705     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 706         tcx.lift(&self.environment).and_then(|environment| {
 707             tcx.lift(&self.goal).map(|goal| {
 708                 traits::InEnvironment {
 709                     environment,
 710                     goal,
 711                 }
 712             })
 713         })
 714     }
 715 }
 716
 717 impl<'tcx, C> Lift<'tcx> for chalk_engine::ExClause<C>
 718 where
 719     C: chalk_engine::context::Context + Clone,
 720     C: traits::ChalkContextLift<'tcx>,
 721 {
 722     type Lifted = C::LiftedExClause;
 723
 724     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 725         <C as traits::ChalkContextLift>::lift_ex_clause_to_tcx(self, tcx)
 726     }
 727 }
 728
 729 impl<'tcx, C> Lift<'tcx> for chalk_engine::DelayedLiteral<C>
 730 where
 731     C: chalk_engine::context::Context + Clone,
 732     C: traits::ChalkContextLift<'tcx>,
 733 {
 734     type Lifted = C::LiftedDelayedLiteral;
 735
 736     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 737         <C as traits::ChalkContextLift>::lift_delayed_literal_to_tcx(self, tcx)
 738     }
 739 }
 740
 741 impl<'tcx, C> Lift<'tcx> for chalk_engine::Literal<C>
 742 where
 743     C: chalk_engine::context::Context + Clone,
 744     C: traits::ChalkContextLift<'tcx>,
 745 {
 746     type Lifted = C::LiftedLiteral;
 747
 748     fn lift_to_tcx(&self, tcx: TyCtxt<'tcx>) -> Option<Self::Lifted> {
 749         <C as traits::ChalkContextLift>::lift_literal_to_tcx(self, tcx)
 750     }
 751 }
 752
 753 ///////////////////////////////////////////////////////////////////////////
 754 // TypeFoldable implementations.
 755
 756 impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> {
 757     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 758         traits::Obligation {
 759             cause: self.cause.clone(),
 760             recursion_depth: self.recursion_depth,
 761             predicate: self.predicate.fold_with(folder),
 762             param_env: self.param_env.fold_with(folder),
 763         }
 764     }
 765
 766     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 767         self.predicate.visit_with(visitor)
 768     }
 769 }
 770
 771 BraceStructTypeFoldableImpl! {
 772     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableImplData<'tcx, N> {
 773         impl_def_id, substs, nested
 774     } where N: TypeFoldable<'tcx>
 775 }
 776
 777 BraceStructTypeFoldableImpl! {
 778     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableGeneratorData<'tcx, N> {
 779         generator_def_id, substs, nested
 780     } where N: TypeFoldable<'tcx>
 781 }
 782
 783 BraceStructTypeFoldableImpl! {
 784     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableClosureData<'tcx, N> {
 785         closure_def_id, substs, nested
 786     } where N: TypeFoldable<'tcx>
 787 }
 788
 789 BraceStructTypeFoldableImpl! {
 790     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableAutoImplData<N> {
 791         trait_def_id, nested
 792     } where N: TypeFoldable<'tcx>
 793 }
 794
 795 BraceStructTypeFoldableImpl! {
 796     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableBuiltinData<N> {
 797         nested
 798     } where N: TypeFoldable<'tcx>
 799 }
 800
 801 BraceStructTypeFoldableImpl! {
 802     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableObjectData<'tcx, N> {
 803         upcast_trait_ref, vtable_base, nested
 804     } where N: TypeFoldable<'tcx>
 805 }
 806
 807 BraceStructTypeFoldableImpl! {
 808     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableFnPointerData<'tcx, N> {
 809         fn_ty,
 810         nested
 811     } where N: TypeFoldable<'tcx>
 812 }
 813
 814 BraceStructTypeFoldableImpl! {
 815     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableTraitAliasData<'tcx, N> {
 816         alias_def_id, substs, nested
 817     } where N: TypeFoldable<'tcx>
 818 }
 819
 820 EnumTypeFoldableImpl! {
 821     impl<'tcx, N> TypeFoldable<'tcx> for traits::Vtable<'tcx, N> {
 822         (traits::VtableImpl)(a),
 823         (traits::VtableAutoImpl)(a),
 824         (traits::VtableGenerator)(a),
 825         (traits::VtableClosure)(a),
 826         (traits::VtableFnPointer)(a),
 827         (traits::VtableParam)(a),
 828         (traits::VtableBuiltin)(a),
 829         (traits::VtableObject)(a),
 830         (traits::VtableTraitAlias)(a),
 831     } where N: TypeFoldable<'tcx>
 832 }
 833
 834 BraceStructTypeFoldableImpl! {
 835     impl<'tcx, T> TypeFoldable<'tcx> for Normalized<'tcx, T> {
 836         value,
 837         obligations
 838     } where T: TypeFoldable<'tcx>
 839 }
 840
 841 EnumTypeFoldableImpl! {
 842     impl<'tcx> TypeFoldable<'tcx> for traits::WhereClause<'tcx> {
 843         (traits::WhereClause::Implemented)(trait_ref),
 844         (traits::WhereClause::ProjectionEq)(projection),
 845         (traits::WhereClause::TypeOutlives)(ty_outlives),
 846         (traits::WhereClause::RegionOutlives)(region_outlives),
 847     }
 848 }
 849
 850 EnumTypeFoldableImpl! {
 851     impl<'tcx> TypeFoldable<'tcx> for traits::WellFormed<'tcx> {
 852         (traits::WellFormed::Trait)(trait_ref),
 853         (traits::WellFormed::Ty)(ty),
 854     }
 855 }
 856
 857 EnumTypeFoldableImpl! {
 858     impl<'tcx> TypeFoldable<'tcx> for traits::FromEnv<'tcx> {
 859         (traits::FromEnv::Trait)(trait_ref),
 860         (traits::FromEnv::Ty)(ty),
 861     }
 862 }
 863
 864 EnumTypeFoldableImpl! {
 865     impl<'tcx> TypeFoldable<'tcx> for traits::DomainGoal<'tcx> {
 866         (traits::DomainGoal::Holds)(wc),
 867         (traits::DomainGoal::WellFormed)(wf),
 868         (traits::DomainGoal::FromEnv)(from_env),
 869         (traits::DomainGoal::Normalize)(projection),
 870     }
 871 }
 872
 873 CloneTypeFoldableAndLiftImpls! {
 874     traits::QuantifierKind,
 875 }
 876
 877 EnumTypeFoldableImpl! {
 878     impl<'tcx> TypeFoldable<'tcx> for traits::GoalKind<'tcx> {
 879         (traits::GoalKind::Implies)(hypotheses, goal),
 880         (traits::GoalKind::And)(goal1, goal2),
 881         (traits::GoalKind::Not)(goal),
 882         (traits::GoalKind::DomainGoal)(domain_goal),
 883         (traits::GoalKind::Quantified)(qkind, goal),
 884         (traits::GoalKind::Subtype)(a, b),
 885         (traits::GoalKind::CannotProve),
 886     }
 887 }
 888
 889 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Goal<'tcx>> {
 890     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 891         let v = self.iter()
 892             .map(|t| t.fold_with(folder))
 893             .collect::<SmallVec<[_; 8]>>();
 894         folder.tcx().intern_goals(&v)
 895     }
 896
 897     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 898         self.iter().any(|t| t.visit_with(visitor))
 899     }
 900 }
 901
 902 impl<'tcx> TypeFoldable<'tcx> for traits::Goal<'tcx> {
 903     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 904         let v = (**self).fold_with(folder);
 905         folder.tcx().mk_goal(v)
 906     }
 907
 908     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 909         (**self).visit_with(visitor)
 910     }
 911 }
 912
 913 BraceStructTypeFoldableImpl! {
 914     impl<'tcx> TypeFoldable<'tcx> for traits::ProgramClause<'tcx> {
 915         goal,
 916         hypotheses,
 917         category,
 918     }
 919 }
 920
 921 CloneTypeFoldableAndLiftImpls! {
 922     traits::ProgramClauseCategory,
 923 }
 924
 925 EnumTypeFoldableImpl! {
 926     impl<'tcx> TypeFoldable<'tcx> for traits::Clause<'tcx> {
 927         (traits::Clause::Implies)(clause),
 928         (traits::Clause::ForAll)(clause),
 929     }
 930 }
 931
 932 BraceStructTypeFoldableImpl! {
 933     impl<'tcx> TypeFoldable<'tcx> for traits::Environment<'tcx> { clauses }
 934 }
 935
 936 BraceStructTypeFoldableImpl! {
 937     impl<'tcx, G> TypeFoldable<'tcx> for traits::InEnvironment<'tcx, G> {
 938         environment,
 939         goal
 940     } where G: TypeFoldable<'tcx>
 941 }
 942
 943 impl<'tcx> TypeFoldable<'tcx> for traits::Clauses<'tcx> {
 944     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 945         let v = self.iter()
 946             .map(|t| t.fold_with(folder))
 947             .collect::<SmallVec<[_; 8]>>();
 948         folder.tcx().intern_clauses(&v)
 949     }
 950
 951     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 952         self.iter().any(|t| t.visit_with(visitor))
 953     }
 954 }
 955
 956 impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::ExClause<C>
 957 where
 958     C: traits::ExClauseFold<'tcx>,
 959     C::Substitution: Clone,
 960     C::RegionConstraint: Clone,
 961 {
 962     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
 963         <C as traits::ExClauseFold>::fold_ex_clause_with(
 964             self,
 965             folder,
 966         )
 967     }
 968
 969     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 970         <C as traits::ExClauseFold>::visit_ex_clause_with(
 971             self,
 972             visitor,
 973         )
 974     }
 975 }
 976
 977 EnumTypeFoldableImpl! {
 978     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::DelayedLiteral<C> {
 979         (chalk_engine::DelayedLiteral::CannotProve)(a),
 980         (chalk_engine::DelayedLiteral::Negative)(a),
 981         (chalk_engine::DelayedLiteral::Positive)(a, b),
 982     } where
 983         C: chalk_engine::context::Context + Clone,
 984         C::CanonicalConstrainedSubst: TypeFoldable<'tcx>,
 985 }
 986
 987 EnumTypeFoldableImpl! {
 988     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::Literal<C> {
 989         (chalk_engine::Literal::Negative)(a),
 990         (chalk_engine::Literal::Positive)(a),
 991     } where
 992         C: chalk_engine::context::Context + Clone,
 993         C::GoalInEnvironment: Clone + TypeFoldable<'tcx>,
 994 }
 995
 996 CloneTypeFoldableAndLiftImpls! {
 997     chalk_engine::TableIndex,
 998 }