src/librustc/traits/structural_impls.rs

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