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, 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<'tcx, 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<'tcx, 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 ppaux because it does not print out anonymous regions.
 169         fn write_region_name<'tcx>(
 170             r: ty::Region<'tcx>,
 171             fmt: &mut fmt::Formatter<'_>
 172         ) -> fmt::Result {
 173             match r {
 174                 ty::ReLateBound(index, br) => match br {
 175                     ty::BoundRegion::BrNamed(_, name) => write!(fmt, "{}", name),
 176                     ty::BoundRegion::BrAnon(var) => {
 177                         if *index == ty::INNERMOST {
 178                             write!(fmt, "'^{}", var)
 179                         } else {
 180                             write!(fmt, "'^{}_{}", index.index(), var)
 181                         }
 182                     }
 183                     _ => write!(fmt, "'_"),
 184                 }
 185
 186                 _ => write!(fmt, "{}", r),
 187             }
 188         }
 189
 190         match self {
 191             Implemented(trait_ref) => write!(fmt, "Implemented({})", trait_ref),
 192             ProjectionEq(projection) => write!(fmt, "ProjectionEq({})", projection),
 193             RegionOutlives(predicate) => {
 194                 write!(fmt, "RegionOutlives({}: ", predicate.0)?;
 195                 write_region_name(predicate.1, fmt)?;
 196                 write!(fmt, ")")
 197             }
 198             TypeOutlives(predicate) => {
 199                 write!(fmt, "TypeOutlives({}: ", predicate.0)?;
 200                 write_region_name(predicate.1, fmt)?;
 201                 write!(fmt, ")")
 202             }
 203         }
 204     }
 205 }
 206
 207 impl<'tcx> fmt::Display for traits::WellFormed<'tcx> {
 208     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 209         use crate::traits::WellFormed::*;
 210
 211         match self {
 212             Trait(trait_ref) => write!(fmt, "WellFormed({})", trait_ref),
 213             Ty(ty) => write!(fmt, "WellFormed({})", ty),
 214         }
 215     }
 216 }
 217
 218 impl<'tcx> fmt::Display for traits::FromEnv<'tcx> {
 219     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 220         use crate::traits::FromEnv::*;
 221
 222         match self {
 223             Trait(trait_ref) => write!(fmt, "FromEnv({})", trait_ref),
 224             Ty(ty) => write!(fmt, "FromEnv({})", ty),
 225         }
 226     }
 227 }
 228
 229 impl<'tcx> fmt::Display for traits::DomainGoal<'tcx> {
 230     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 231         use crate::traits::DomainGoal::*;
 232
 233         match self {
 234             Holds(wc) => write!(fmt, "{}", wc),
 235             WellFormed(wf) => write!(fmt, "{}", wf),
 236             FromEnv(from_env) => write!(fmt, "{}", from_env),
 237             Normalize(projection) => write!(
 238                 fmt,
 239                 "Normalize({} -> {})",
 240                 projection.projection_ty,
 241                 projection.ty
 242             ),
 243         }
 244     }
 245 }
 246
 247 impl fmt::Display for traits::QuantifierKind {
 248     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 249         use crate::traits::QuantifierKind::*;
 250
 251         match self {
 252             Universal => write!(fmt, "forall"),
 253             Existential => write!(fmt, "exists"),
 254         }
 255     }
 256 }
 257
 258 /// Collect names for regions / types bound by a quantified goal / clause.
 259 /// This collector does not try to do anything clever like in ppaux, it's just used
 260 /// for debug output in tests anyway.
 261 struct BoundNamesCollector {
 262     // Just sort by name because `BoundRegion::BrNamed` does not have a `BoundVar` index anyway.
 263     regions: BTreeSet<InternedString>,
 264
 265     // Sort by `BoundVar` index, so usually this should be equivalent to the order given
 266     // by the list of type parameters.
 267     types: BTreeMap<u32, InternedString>,
 268
 269     binder_index: ty::DebruijnIndex,
 270 }
 271
 272 impl BoundNamesCollector {
 273     fn new() -> Self {
 274         BoundNamesCollector {
 275             regions: BTreeSet::new(),
 276             types: BTreeMap::new(),
 277             binder_index: ty::INNERMOST,
 278         }
 279     }
 280
 281     fn is_empty(&self) -> bool {
 282         self.regions.is_empty() && self.types.is_empty()
 283     }
 284
 285     fn write_names(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 286         let mut start = true;
 287         for r in &self.regions {
 288             if !start {
 289                 write!(fmt, ", ")?;
 290             }
 291             start = false;
 292             write!(fmt, "{}", r)?;
 293         }
 294         for (_, t) in &self.types {
 295             if !start {
 296                 write!(fmt, ", ")?;
 297             }
 298             start = false;
 299             write!(fmt, "{}", t)?;
 300         }
 301         Ok(())
 302     }
 303 }
 304
 305 impl<'tcx> TypeVisitor<'tcx> for BoundNamesCollector {
 306     fn visit_binder<T: TypeFoldable<'tcx>>(&mut self, t: &ty::Binder<T>) -> bool {
 307         self.binder_index.shift_in(1);
 308         let result = t.super_visit_with(self);
 309         self.binder_index.shift_out(1);
 310         result
 311     }
 312
 313     fn visit_ty(&mut self, t: ty::Ty<'tcx>) -> bool {
 314         use syntax::symbol::Symbol;
 315
 316         match t.sty {
 317             ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => {
 318                 self.types.insert(
 319                     bound_ty.var.as_u32(),
 320                     match bound_ty.kind {
 321                         ty::BoundTyKind::Param(name) => name,
 322                         ty::BoundTyKind::Anon => Symbol::intern(
 323                             &format!("^{}", bound_ty.var.as_u32())
 324                         ).as_interned_str(),
 325                     }
 326                 );
 327             }
 328
 329             _ => (),
 330         };
 331
 332         t.super_visit_with(self)
 333     }
 334
 335     fn visit_region(&mut self, r: ty::Region<'tcx>) -> bool {
 336         use syntax::symbol::Symbol;
 337
 338         match r {
 339             ty::ReLateBound(index, br) if *index == self.binder_index => {
 340                 match br {
 341                     ty::BoundRegion::BrNamed(_, name) => {
 342                         self.regions.insert(*name);
 343                     }
 344
 345                     ty::BoundRegion::BrAnon(var) => {
 346                         self.regions.insert(Symbol::intern(
 347                             &format!("'^{}", var)
 348                         ).as_interned_str());
 349                     }
 350
 351                     _ => (),
 352                 }
 353             }
 354
 355             _ => (),
 356         };
 357
 358         r.super_visit_with(self)
 359     }
 360 }
 361
 362 impl<'tcx> fmt::Display for traits::Goal<'tcx> {
 363     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 364         use crate::traits::GoalKind::*;
 365
 366         match self {
 367             Implies(hypotheses, goal) => {
 368                 write!(fmt, "if (")?;
 369                 for (index, hyp) in hypotheses.iter().enumerate() {
 370                     if index > 0 {
 371                         write!(fmt, ", ")?;
 372                     }
 373                     write!(fmt, "{}", hyp)?;
 374                 }
 375                 write!(fmt, ") {{ {} }}", goal)
 376             }
 377             And(goal1, goal2) => write!(fmt, "({} && {})", goal1, goal2),
 378             Not(goal) => write!(fmt, "not {{ {} }}", goal),
 379             DomainGoal(goal) => write!(fmt, "{}", goal),
 380             Quantified(qkind, goal) => {
 381                 let mut collector = BoundNamesCollector::new();
 382                 goal.skip_binder().visit_with(&mut collector);
 383
 384                 if !collector.is_empty() {
 385                     write!(fmt, "{}<", qkind)?;
 386                     collector.write_names(fmt)?;
 387                     write!(fmt, "> {{ ")?;
 388                 }
 389
 390                 write!(fmt, "{}", goal.skip_binder())?;
 391
 392                 if !collector.is_empty() {
 393                     write!(fmt, " }}")?;
 394                 }
 395
 396                 Ok(())
 397             }
 398             Subtype(a, b) => write!(fmt, "{} <: {}", a, b),
 399             CannotProve => write!(fmt, "CannotProve"),
 400         }
 401     }
 402 }
 403
 404 impl<'tcx> fmt::Display for traits::ProgramClause<'tcx> {
 405     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 406         let traits::ProgramClause { goal, hypotheses, .. } = self;
 407         write!(fmt, "{}", goal)?;
 408         if !hypotheses.is_empty() {
 409             write!(fmt, " :- ")?;
 410             for (index, condition) in hypotheses.iter().enumerate() {
 411                 if index > 0 {
 412                     write!(fmt, ", ")?;
 413                 }
 414                 write!(fmt, "{}", condition)?;
 415             }
 416         }
 417         write!(fmt, ".")
 418     }
 419 }
 420
 421 impl<'tcx> fmt::Display for traits::Clause<'tcx> {
 422     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 423         use crate::traits::Clause::*;
 424
 425         match self {
 426             Implies(clause) => write!(fmt, "{}", clause),
 427             ForAll(clause) => {
 428                 let mut collector = BoundNamesCollector::new();
 429                 clause.skip_binder().visit_with(&mut collector);
 430
 431                 if !collector.is_empty() {
 432                     write!(fmt, "forall<")?;
 433                     collector.write_names(fmt)?;
 434                     write!(fmt, "> {{ ")?;
 435                 }
 436
 437                 write!(fmt, "{}", clause.skip_binder())?;
 438
 439                 if !collector.is_empty() {
 440                     write!(fmt, " }}")?;
 441                 }
 442
 443                 Ok(())
 444             }
 445         }
 446     }
 447 }
 448
 449 ///////////////////////////////////////////////////////////////////////////
 450 // Lift implementations
 451
 452 impl<'a, 'tcx> Lift<'tcx> for traits::SelectionError<'a> {
 453     type Lifted = traits::SelectionError<'tcx>;
 454     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 455         match *self {
 456             super::Unimplemented => Some(super::Unimplemented),
 457             super::OutputTypeParameterMismatch(a, b, ref err) => {
 458                 tcx.lift(&(a, b)).and_then(|(a, b)|
 459                     tcx.lift(err)
 460                         .map(|err| super::OutputTypeParameterMismatch(a, b, err))
 461                 )
 462             }
 463             super::TraitNotObjectSafe(def_id) => Some(super::TraitNotObjectSafe(def_id)),
 464             super::ConstEvalFailure(err) => Some(super::ConstEvalFailure(err)),
 465             super::Overflow => Some(super::Overflow),
 466         }
 467     }
 468 }
 469
 470 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCauseCode<'a> {
 471     type Lifted = traits::ObligationCauseCode<'tcx>;
 472     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 473         match *self {
 474             super::ReturnNoExpression => Some(super::ReturnNoExpression),
 475             super::MiscObligation => Some(super::MiscObligation),
 476             super::SliceOrArrayElem => Some(super::SliceOrArrayElem),
 477             super::TupleElem => Some(super::TupleElem),
 478             super::ProjectionWf(proj) => tcx.lift(&proj).map(super::ProjectionWf),
 479             super::ItemObligation(def_id) => Some(super::ItemObligation(def_id)),
 480             super::ReferenceOutlivesReferent(ty) => {
 481                 tcx.lift(&ty).map(super::ReferenceOutlivesReferent)
 482             }
 483             super::ObjectTypeBound(ty, r) => tcx.lift(&ty).and_then(|ty|
 484                 tcx.lift(&r)
 485                    .and_then(|r| Some(super::ObjectTypeBound(ty, r)))
 486             ),
 487             super::ObjectCastObligation(ty) => tcx.lift(&ty).map(super::ObjectCastObligation),
 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::ReturnType(id) => Some(super::ReturnType(id)),
 493             super::SizedArgumentType => Some(super::SizedArgumentType),
 494             super::SizedReturnType => Some(super::SizedReturnType),
 495             super::SizedYieldType => Some(super::SizedYieldType),
 496             super::RepeatVec => Some(super::RepeatVec),
 497             super::FieldSized { adt_kind, last } => Some(super::FieldSized { adt_kind, last }),
 498             super::ConstSized => Some(super::ConstSized),
 499             super::SharedStatic => Some(super::SharedStatic),
 500             super::BuiltinDerivedObligation(ref cause) => {
 501                 tcx.lift(cause).map(super::BuiltinDerivedObligation)
 502             }
 503             super::ImplDerivedObligation(ref cause) => {
 504                 tcx.lift(cause).map(super::ImplDerivedObligation)
 505             }
 506             super::CompareImplMethodObligation {
 507                 item_name,
 508                 impl_item_def_id,
 509                 trait_item_def_id,
 510             } => Some(super::CompareImplMethodObligation {
 511                 item_name,
 512                 impl_item_def_id,
 513                 trait_item_def_id,
 514             }),
 515             super::ExprAssignable => Some(super::ExprAssignable),
 516             super::MatchExpressionArm {
 517                 arm_span,
 518                 source,
 519                 ref prior_arms,
 520                 last_ty,
 521             } => {
 522                 tcx.lift(&last_ty).map(|last_ty| {
 523                     super::MatchExpressionArm {
 524                         arm_span,
 525                         source,
 526                         prior_arms: prior_arms.clone(),
 527                         last_ty,
 528                     }
 529                 })
 530             }
 531             super::MatchExpressionArmPattern { span, ty } => {
 532                 tcx.lift(&ty).map(|ty| super::MatchExpressionArmPattern { span, ty })
 533             }
 534             super::IfExpression { then, outer, semicolon } => Some(super::IfExpression {
 535                 then,
 536                 outer,
 537                 semicolon,
 538             }),
 539             super::IfExpressionWithNoElse => Some(super::IfExpressionWithNoElse),
 540             super::MainFunctionType => Some(super::MainFunctionType),
 541             super::StartFunctionType => Some(super::StartFunctionType),
 542             super::IntrinsicType => Some(super::IntrinsicType),
 543             super::MethodReceiver => Some(super::MethodReceiver),
 544             super::BlockTailExpression(id) => Some(super::BlockTailExpression(id)),
 545             super::TrivialBound => Some(super::TrivialBound),
 546         }
 547     }
 548 }
 549
 550 impl<'a, 'tcx> Lift<'tcx> for traits::DerivedObligationCause<'a> {
 551     type Lifted = traits::DerivedObligationCause<'tcx>;
 552     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 553         tcx.lift(&self.parent_trait_ref).and_then(|trait_ref|
 554             tcx.lift(&*self.parent_code)
 555                .map(|code| traits::DerivedObligationCause {
 556                    parent_trait_ref: trait_ref,
 557                    parent_code: Rc::new(code),
 558                })
 559         )
 560     }
 561 }
 562
 563 impl<'a, 'tcx> Lift<'tcx> for traits::ObligationCause<'a> {
 564     type Lifted = traits::ObligationCause<'tcx>;
 565     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 566         tcx.lift(&self.code).map(|code| traits::ObligationCause {
 567             span: self.span,
 568             body_id: self.body_id,
 569             code,
 570         })
 571     }
 572 }
 573
 574 // For codegen only.
 575 impl<'a, 'tcx> Lift<'tcx> for traits::Vtable<'a, ()> {
 576     type Lifted = traits::Vtable<'tcx, ()>;
 577     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 578         match self.clone() {
 579             traits::VtableImpl(traits::VtableImplData {
 580                 impl_def_id,
 581                 substs,
 582                 nested,
 583             }) => tcx.lift(&substs).map(|substs|
 584                 traits::VtableImpl(traits::VtableImplData {
 585                     impl_def_id,
 586                     substs,
 587                     nested,
 588                 })
 589             ),
 590             traits::VtableAutoImpl(t) => Some(traits::VtableAutoImpl(t)),
 591             traits::VtableGenerator(traits::VtableGeneratorData {
 592                 generator_def_id,
 593                 substs,
 594                 nested,
 595             }) => tcx.lift(&substs).map(|substs|
 596                 traits::VtableGenerator(traits::VtableGeneratorData {
 597                     generator_def_id: generator_def_id,
 598                     substs: substs,
 599                     nested: nested,
 600                 })
 601             ),
 602             traits::VtableClosure(traits::VtableClosureData {
 603                 closure_def_id,
 604                 substs,
 605                 nested,
 606             }) => tcx.lift(&substs).map(|substs|
 607                 traits::VtableClosure(traits::VtableClosureData {
 608                     closure_def_id,
 609                     substs,
 610                     nested,
 611                 })
 612             ),
 613             traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested }) => {
 614                 tcx.lift(&fn_ty).map(|fn_ty|
 615                     traits::VtableFnPointer(traits::VtableFnPointerData { fn_ty, nested })
 616                 )
 617             }
 618             traits::VtableParam(n) => Some(traits::VtableParam(n)),
 619             traits::VtableBuiltin(n) => Some(traits::VtableBuiltin(n)),
 620             traits::VtableObject(traits::VtableObjectData {
 621                 upcast_trait_ref,
 622                 vtable_base,
 623                 nested,
 624             }) => tcx.lift(&upcast_trait_ref).map(|trait_ref|
 625                 traits::VtableObject(traits::VtableObjectData {
 626                     upcast_trait_ref: trait_ref,
 627                     vtable_base,
 628                     nested,
 629                 })
 630             ),
 631             traits::VtableTraitAlias(traits::VtableTraitAliasData {
 632                 alias_def_id,
 633                 substs,
 634                 nested,
 635             }) => tcx.lift(&substs).map(|substs|
 636                 traits::VtableTraitAlias(traits::VtableTraitAliasData {
 637                     alias_def_id,
 638                     substs,
 639                     nested,
 640                 })
 641             ),
 642         }
 643     }
 644 }
 645
 646 EnumLiftImpl! {
 647     impl<'a, 'tcx> Lift<'tcx> for traits::WhereClause<'a> {
 648         type Lifted = traits::WhereClause<'tcx>;
 649         (traits::WhereClause::Implemented)(trait_ref),
 650         (traits::WhereClause::ProjectionEq)(projection),
 651         (traits::WhereClause::TypeOutlives)(ty_outlives),
 652         (traits::WhereClause::RegionOutlives)(region_outlives),
 653     }
 654 }
 655
 656 EnumLiftImpl! {
 657     impl<'a, 'tcx> Lift<'tcx> for traits::WellFormed<'a> {
 658         type Lifted = traits::WellFormed<'tcx>;
 659         (traits::WellFormed::Trait)(trait_ref),
 660         (traits::WellFormed::Ty)(ty),
 661     }
 662 }
 663
 664 EnumLiftImpl! {
 665     impl<'a, 'tcx> Lift<'tcx> for traits::FromEnv<'a> {
 666         type Lifted = traits::FromEnv<'tcx>;
 667         (traits::FromEnv::Trait)(trait_ref),
 668         (traits::FromEnv::Ty)(ty),
 669     }
 670 }
 671
 672 EnumLiftImpl! {
 673     impl<'a, 'tcx> Lift<'tcx> for traits::DomainGoal<'a> {
 674         type Lifted = traits::DomainGoal<'tcx>;
 675         (traits::DomainGoal::Holds)(wc),
 676         (traits::DomainGoal::WellFormed)(wf),
 677         (traits::DomainGoal::FromEnv)(from_env),
 678         (traits::DomainGoal::Normalize)(projection),
 679     }
 680 }
 681
 682 EnumLiftImpl! {
 683     impl<'a, 'tcx> Lift<'tcx> for traits::GoalKind<'a> {
 684         type Lifted = traits::GoalKind<'tcx>;
 685         (traits::GoalKind::Implies)(hypotheses, goal),
 686         (traits::GoalKind::And)(goal1, goal2),
 687         (traits::GoalKind::Not)(goal),
 688         (traits::GoalKind::DomainGoal)(domain_goal),
 689         (traits::GoalKind::Quantified)(kind, goal),
 690         (traits::GoalKind::Subtype)(a, b),
 691         (traits::GoalKind::CannotProve),
 692     }
 693 }
 694
 695 impl<'a, 'tcx> Lift<'tcx> for traits::Environment<'a> {
 696     type Lifted = traits::Environment<'tcx>;
 697     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 698         tcx.lift(&self.clauses).map(|clauses| {
 699             traits::Environment {
 700                 clauses,
 701             }
 702         })
 703     }
 704 }
 705
 706 impl<'a, 'tcx, G: Lift<'tcx>> Lift<'tcx> for traits::InEnvironment<'a, G> {
 707     type Lifted = traits::InEnvironment<'tcx, G::Lifted>;
 708     fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 709         tcx.lift(&self.environment).and_then(|environment| {
 710             tcx.lift(&self.goal).map(|goal| {
 711                 traits::InEnvironment {
 712                     environment,
 713                     goal,
 714                 }
 715             })
 716         })
 717     }
 718 }
 719
 720 impl<'tcx, C> Lift<'tcx> for chalk_engine::ExClause<C>
 721 where
 722     C: chalk_engine::context::Context + Clone,
 723     C: traits::ChalkContextLift<'tcx>,
 724 {
 725     type Lifted = C::LiftedExClause;
 726
 727     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 728         <C as traits::ChalkContextLift>::lift_ex_clause_to_tcx(self, tcx)
 729     }
 730 }
 731
 732 impl<'tcx, C> Lift<'tcx> for chalk_engine::DelayedLiteral<C>
 733 where
 734     C: chalk_engine::context::Context + Clone,
 735     C: traits::ChalkContextLift<'tcx>,
 736 {
 737     type Lifted = C::LiftedDelayedLiteral;
 738
 739     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 740         <C as traits::ChalkContextLift>::lift_delayed_literal_to_tcx(self, tcx)
 741     }
 742 }
 743
 744 impl<'tcx, C> Lift<'tcx> for chalk_engine::Literal<C>
 745 where
 746     C: chalk_engine::context::Context + Clone,
 747     C: traits::ChalkContextLift<'tcx>,
 748 {
 749     type Lifted = C::LiftedLiteral;
 750
 751     fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted> {
 752         <C as traits::ChalkContextLift>::lift_literal_to_tcx(self, tcx)
 753     }
 754 }
 755
 756 ///////////////////////////////////////////////////////////////////////////
 757 // TypeFoldable implementations.
 758
 759 impl<'tcx, O: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Obligation<'tcx, O> {
 760     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 761         traits::Obligation {
 762             cause: self.cause.clone(),
 763             recursion_depth: self.recursion_depth,
 764             predicate: self.predicate.fold_with(folder),
 765             param_env: self.param_env.fold_with(folder),
 766         }
 767     }
 768
 769     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 770         self.predicate.visit_with(visitor)
 771     }
 772 }
 773
 774 BraceStructTypeFoldableImpl! {
 775     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableImplData<'tcx, N> {
 776         impl_def_id, substs, nested
 777     } where N: TypeFoldable<'tcx>
 778 }
 779
 780 BraceStructTypeFoldableImpl! {
 781     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableGeneratorData<'tcx, N> {
 782         generator_def_id, substs, nested
 783     } where N: TypeFoldable<'tcx>
 784 }
 785
 786 BraceStructTypeFoldableImpl! {
 787     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableClosureData<'tcx, N> {
 788         closure_def_id, substs, nested
 789     } where N: TypeFoldable<'tcx>
 790 }
 791
 792 BraceStructTypeFoldableImpl! {
 793     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableAutoImplData<N> {
 794         trait_def_id, nested
 795     } where N: TypeFoldable<'tcx>
 796 }
 797
 798 BraceStructTypeFoldableImpl! {
 799     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableBuiltinData<N> {
 800         nested
 801     } where N: TypeFoldable<'tcx>
 802 }
 803
 804 BraceStructTypeFoldableImpl! {
 805     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableObjectData<'tcx, N> {
 806         upcast_trait_ref, vtable_base, nested
 807     } where N: TypeFoldable<'tcx>
 808 }
 809
 810 BraceStructTypeFoldableImpl! {
 811     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableFnPointerData<'tcx, N> {
 812         fn_ty,
 813         nested
 814     } where N: TypeFoldable<'tcx>
 815 }
 816
 817 BraceStructTypeFoldableImpl! {
 818     impl<'tcx, N> TypeFoldable<'tcx> for traits::VtableTraitAliasData<'tcx, N> {
 819         alias_def_id, substs, nested
 820     } where N: TypeFoldable<'tcx>
 821 }
 822
 823 EnumTypeFoldableImpl! {
 824     impl<'tcx, N> TypeFoldable<'tcx> for traits::Vtable<'tcx, N> {
 825         (traits::VtableImpl)(a),
 826         (traits::VtableAutoImpl)(a),
 827         (traits::VtableGenerator)(a),
 828         (traits::VtableClosure)(a),
 829         (traits::VtableFnPointer)(a),
 830         (traits::VtableParam)(a),
 831         (traits::VtableBuiltin)(a),
 832         (traits::VtableObject)(a),
 833         (traits::VtableTraitAlias)(a),
 834     } where N: TypeFoldable<'tcx>
 835 }
 836
 837 BraceStructTypeFoldableImpl! {
 838     impl<'tcx, T> TypeFoldable<'tcx> for Normalized<'tcx, T> {
 839         value,
 840         obligations
 841     } where T: TypeFoldable<'tcx>
 842 }
 843
 844 EnumTypeFoldableImpl! {
 845     impl<'tcx> TypeFoldable<'tcx> for traits::WhereClause<'tcx> {
 846         (traits::WhereClause::Implemented)(trait_ref),
 847         (traits::WhereClause::ProjectionEq)(projection),
 848         (traits::WhereClause::TypeOutlives)(ty_outlives),
 849         (traits::WhereClause::RegionOutlives)(region_outlives),
 850     }
 851 }
 852
 853 EnumTypeFoldableImpl! {
 854     impl<'tcx> TypeFoldable<'tcx> for traits::WellFormed<'tcx> {
 855         (traits::WellFormed::Trait)(trait_ref),
 856         (traits::WellFormed::Ty)(ty),
 857     }
 858 }
 859
 860 EnumTypeFoldableImpl! {
 861     impl<'tcx> TypeFoldable<'tcx> for traits::FromEnv<'tcx> {
 862         (traits::FromEnv::Trait)(trait_ref),
 863         (traits::FromEnv::Ty)(ty),
 864     }
 865 }
 866
 867 EnumTypeFoldableImpl! {
 868     impl<'tcx> TypeFoldable<'tcx> for traits::DomainGoal<'tcx> {
 869         (traits::DomainGoal::Holds)(wc),
 870         (traits::DomainGoal::WellFormed)(wf),
 871         (traits::DomainGoal::FromEnv)(from_env),
 872         (traits::DomainGoal::Normalize)(projection),
 873     }
 874 }
 875
 876 CloneTypeFoldableAndLiftImpls! {
 877     traits::QuantifierKind,
 878 }
 879
 880 EnumTypeFoldableImpl! {
 881     impl<'tcx> TypeFoldable<'tcx> for traits::GoalKind<'tcx> {
 882         (traits::GoalKind::Implies)(hypotheses, goal),
 883         (traits::GoalKind::And)(goal1, goal2),
 884         (traits::GoalKind::Not)(goal),
 885         (traits::GoalKind::DomainGoal)(domain_goal),
 886         (traits::GoalKind::Quantified)(qkind, goal),
 887         (traits::GoalKind::Subtype)(a, b),
 888         (traits::GoalKind::CannotProve),
 889     }
 890 }
 891
 892 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<traits::Goal<'tcx>> {
 893     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 894         let v = self.iter()
 895             .map(|t| t.fold_with(folder))
 896             .collect::<SmallVec<[_; 8]>>();
 897         folder.tcx().intern_goals(&v)
 898     }
 899
 900     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 901         self.iter().any(|t| t.visit_with(visitor))
 902     }
 903 }
 904
 905 impl<'tcx> TypeFoldable<'tcx> for traits::Goal<'tcx> {
 906     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 907         let v = (**self).fold_with(folder);
 908         folder.tcx().mk_goal(v)
 909     }
 910
 911     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 912         (**self).visit_with(visitor)
 913     }
 914 }
 915
 916 BraceStructTypeFoldableImpl! {
 917     impl<'tcx> TypeFoldable<'tcx> for traits::ProgramClause<'tcx> {
 918         goal,
 919         hypotheses,
 920         category,
 921     }
 922 }
 923
 924 CloneTypeFoldableAndLiftImpls! {
 925     traits::ProgramClauseCategory,
 926 }
 927
 928 EnumTypeFoldableImpl! {
 929     impl<'tcx> TypeFoldable<'tcx> for traits::Clause<'tcx> {
 930         (traits::Clause::Implies)(clause),
 931         (traits::Clause::ForAll)(clause),
 932     }
 933 }
 934
 935 BraceStructTypeFoldableImpl! {
 936     impl<'tcx> TypeFoldable<'tcx> for traits::Environment<'tcx> { clauses }
 937 }
 938
 939 BraceStructTypeFoldableImpl! {
 940     impl<'tcx, G> TypeFoldable<'tcx> for traits::InEnvironment<'tcx, G> {
 941         environment,
 942         goal
 943     } where G: TypeFoldable<'tcx>
 944 }
 945
 946 impl<'tcx> TypeFoldable<'tcx> for traits::Clauses<'tcx> {
 947     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 948         let v = self.iter()
 949             .map(|t| t.fold_with(folder))
 950             .collect::<SmallVec<[_; 8]>>();
 951         folder.tcx().intern_clauses(&v)
 952     }
 953
 954     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 955         self.iter().any(|t| t.visit_with(visitor))
 956     }
 957 }
 958
 959 impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::ExClause<C>
 960 where
 961     C: traits::ExClauseFold<'tcx>,
 962     C::Substitution: Clone,
 963     C::RegionConstraint: Clone,
 964 {
 965     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
 966         <C as traits::ExClauseFold>::fold_ex_clause_with(
 967             self,
 968             folder,
 969         )
 970     }
 971
 972     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
 973         <C as traits::ExClauseFold>::visit_ex_clause_with(
 974             self,
 975             visitor,
 976         )
 977     }
 978 }
 979
 980 EnumTypeFoldableImpl! {
 981     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::DelayedLiteral<C> {
 982         (chalk_engine::DelayedLiteral::CannotProve)(a),
 983         (chalk_engine::DelayedLiteral::Negative)(a),
 984         (chalk_engine::DelayedLiteral::Positive)(a, b),
 985     } where
 986         C: chalk_engine::context::Context + Clone,
 987         C::CanonicalConstrainedSubst: TypeFoldable<'tcx>,
 988 }
 989
 990 EnumTypeFoldableImpl! {
 991     impl<'tcx, C> TypeFoldable<'tcx> for chalk_engine::Literal<C> {
 992         (chalk_engine::Literal::Negative)(a),
 993         (chalk_engine::Literal::Positive)(a),
 994     } where
 995         C: chalk_engine::context::Context + Clone,
 996         C::GoalInEnvironment: Clone + TypeFoldable<'tcx>,
 997 }
 998
 999 CloneTypeFoldableAndLiftImpls! {
1000     chalk_engine::TableIndex,
1001 }