src/librustc/traits/mod.rs

   1 //! Trait Resolution. See the [rustc guide] for more information on how this works.
   2 //!
   3 //! [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/resolution.html
   4
   5 pub mod query;
   6 pub mod select;
   7 pub mod specialization_graph;
   8 mod structural_impls;
   9
  10 use crate::infer::canonical::Canonical;
  11 use crate::mir::interpret::ErrorHandled;
  12 use crate::ty::fold::{TypeFolder, TypeVisitor};
  13 use crate::ty::subst::SubstsRef;
  14 use crate::ty::{self, AdtKind, List, Ty, TyCtxt};
  15
  16 use rustc_hir as hir;
  17 use rustc_hir::def_id::DefId;
  18 use rustc_span::{Span, DUMMY_SP};
  19 use syntax::ast;
  20
  21 use std::fmt::Debug;
  22 use std::rc::Rc;
  23
  24 pub use self::select::{EvaluationCache, EvaluationResult, OverflowError, SelectionCache};
  25
  26 pub type ChalkCanonicalGoal<'tcx> = Canonical<'tcx, InEnvironment<'tcx, ty::Predicate<'tcx>>>;
  27
  28 pub use self::ObligationCauseCode::*;
  29 pub use self::SelectionError::*;
  30 pub use self::Vtable::*;
  31
  32 /// Depending on the stage of compilation, we want projection to be
  33 /// more or less conservative.
  34 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, HashStable)]
  35 pub enum Reveal {
  36     /// At type-checking time, we refuse to project any associated
  37     /// type that is marked `default`. Non-`default` ("final") types
  38     /// are always projected. This is necessary in general for
  39     /// soundness of specialization. However, we *could* allow
  40     /// projections in fully-monomorphic cases. We choose not to,
  41     /// because we prefer for `default type` to force the type
  42     /// definition to be treated abstractly by any consumers of the
  43     /// impl. Concretely, that means that the following example will
  44     /// fail to compile:
  45     ///
  46     /// ```
  47     /// trait Assoc {
  48     ///     type Output;
  49     /// }
  50     ///
  51     /// impl<T> Assoc for T {
  52     ///     default type Output = bool;
  53     /// }
  54     ///
  55     /// fn main() {
  56     ///     let <() as Assoc>::Output = true;
  57     /// }
  58     /// ```
  59     UserFacing,
  60
  61     /// At codegen time, all monomorphic projections will succeed.
  62     /// Also, `impl Trait` is normalized to the concrete type,
  63     /// which has to be already collected by type-checking.
  64     ///
  65     /// NOTE: as `impl Trait`'s concrete type should *never*
  66     /// be observable directly by the user, `Reveal::All`
  67     /// should not be used by checks which may expose
  68     /// type equality or type contents to the user.
  69     /// There are some exceptions, e.g., around OIBITS and
  70     /// transmute-checking, which expose some details, but
  71     /// not the whole concrete type of the `impl Trait`.
  72     All,
  73 }
  74
  75 /// The reason why we incurred this obligation; used for error reporting.
  76 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
  77 pub struct ObligationCause<'tcx> {
  78     pub span: Span,
  79
  80     /// The ID of the fn body that triggered this obligation. This is
  81     /// used for region obligations to determine the precise
  82     /// environment in which the region obligation should be evaluated
  83     /// (in particular, closures can add new assumptions). See the
  84     /// field `region_obligations` of the `FulfillmentContext` for more
  85     /// information.
  86     pub body_id: hir::HirId,
  87
  88     pub code: ObligationCauseCode<'tcx>,
  89 }
  90
  91 impl<'tcx> ObligationCause<'tcx> {
  92     #[inline]
  93     pub fn new(
  94         span: Span,
  95         body_id: hir::HirId,
  96         code: ObligationCauseCode<'tcx>,
  97     ) -> ObligationCause<'tcx> {
  98         ObligationCause { span, body_id, code }
  99     }
 100
 101     pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> {
 102         ObligationCause { span, body_id, code: MiscObligation }
 103     }
 104
 105     pub fn dummy() -> ObligationCause<'tcx> {
 106         ObligationCause { span: DUMMY_SP, body_id: hir::CRATE_HIR_ID, code: MiscObligation }
 107     }
 108
 109     pub fn span(&self, tcx: TyCtxt<'tcx>) -> Span {
 110         match self.code {
 111             ObligationCauseCode::CompareImplMethodObligation { .. }
 112             | ObligationCauseCode::MainFunctionType
 113             | ObligationCauseCode::StartFunctionType => tcx.sess.source_map().def_span(self.span),
 114             ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause {
 115                 arm_span,
 116                 ..
 117             }) => arm_span,
 118             _ => self.span,
 119         }
 120     }
 121 }
 122
 123 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 124 pub enum ObligationCauseCode<'tcx> {
 125     /// Not well classified or should be obvious from the span.
 126     MiscObligation,
 127
 128     /// A slice or array is WF only if `T: Sized`.
 129     SliceOrArrayElem,
 130
 131     /// A tuple is WF only if its middle elements are `Sized`.
 132     TupleElem,
 133
 134     /// This is the trait reference from the given projection.
 135     ProjectionWf(ty::ProjectionTy<'tcx>),
 136
 137     /// In an impl of trait `X` for type `Y`, type `Y` must
 138     /// also implement all supertraits of `X`.
 139     ItemObligation(DefId),
 140
 141     /// Like `ItemObligation`, but with extra detail on the source of the obligation.
 142     BindingObligation(DefId, Span),
 143
 144     /// A type like `&'a T` is WF only if `T: 'a`.
 145     ReferenceOutlivesReferent(Ty<'tcx>),
 146
 147     /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
 148     ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
 149
 150     /// Obligation incurred due to an object cast.
 151     ObjectCastObligation(/* Object type */ Ty<'tcx>),
 152
 153     /// Obligation incurred due to a coercion.
 154     Coercion {
 155         source: Ty<'tcx>,
 156         target: Ty<'tcx>,
 157     },
 158
 159     /// Various cases where expressions must be `Sized` / `Copy` / etc.
 160     /// `L = X` implies that `L` is `Sized`.
 161     AssignmentLhsSized,
 162     /// `(x1, .., xn)` must be `Sized`.
 163     TupleInitializerSized,
 164     /// `S { ... }` must be `Sized`.
 165     StructInitializerSized,
 166     /// Type of each variable must be `Sized`.
 167     VariableType(hir::HirId),
 168     /// Argument type must be `Sized`.
 169     SizedArgumentType,
 170     /// Return type must be `Sized`.
 171     SizedReturnType,
 172     /// Yield type must be `Sized`.
 173     SizedYieldType,
 174     /// `[T, ..n]` implies that `T` must be `Copy`.
 175     /// If `true`, suggest `const_in_array_repeat_expressions` feature flag.
 176     RepeatVec(bool),
 177
 178     /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
 179     FieldSized {
 180         adt_kind: AdtKind,
 181         last: bool,
 182     },
 183
 184     /// Constant expressions must be sized.
 185     ConstSized,
 186
 187     /// `static` items must have `Sync` type.
 188     SharedStatic,
 189
 190     BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
 191
 192     ImplDerivedObligation(DerivedObligationCause<'tcx>),
 193
 194     /// Error derived when matching traits/impls; see ObligationCause for more details
 195     CompareImplMethodObligation {
 196         item_name: ast::Name,
 197         impl_item_def_id: DefId,
 198         trait_item_def_id: DefId,
 199     },
 200
 201     /// Error derived when matching traits/impls; see ObligationCause for more details
 202     CompareImplTypeObligation {
 203         item_name: ast::Name,
 204         impl_item_def_id: DefId,
 205         trait_item_def_id: DefId,
 206     },
 207
 208     /// Checking that this expression can be assigned where it needs to be
 209     // FIXME(eddyb) #11161 is the original Expr required?
 210     ExprAssignable,
 211
 212     /// Computing common supertype in the arms of a match expression
 213     MatchExpressionArm(Box<MatchExpressionArmCause<'tcx>>),
 214
 215     /// Type error arising from type checking a pattern against an expected type.
 216     Pattern {
 217         /// The span of the scrutinee or type expression which caused the `root_ty` type.
 218         span: Option<Span>,
 219         /// The root expected type induced by a scrutinee or type expression.
 220         root_ty: Ty<'tcx>,
 221         /// Whether the `Span` came from an expression or a type expression.
 222         origin_expr: bool,
 223     },
 224
 225     /// Constants in patterns must have `Structural` type.
 226     ConstPatternStructural,
 227
 228     /// Computing common supertype in an if expression
 229     IfExpression(Box<IfExpressionCause>),
 230
 231     /// Computing common supertype of an if expression with no else counter-part
 232     IfExpressionWithNoElse,
 233
 234     /// `main` has wrong type
 235     MainFunctionType,
 236
 237     /// `start` has wrong type
 238     StartFunctionType,
 239
 240     /// Intrinsic has wrong type
 241     IntrinsicType,
 242
 243     /// Method receiver
 244     MethodReceiver,
 245
 246     /// `return` with no expression
 247     ReturnNoExpression,
 248
 249     /// `return` with an expression
 250     ReturnValue(hir::HirId),
 251
 252     /// Return type of this function
 253     ReturnType,
 254
 255     /// Block implicit return
 256     BlockTailExpression(hir::HirId),
 257
 258     /// #[feature(trivial_bounds)] is not enabled
 259     TrivialBound,
 260
 261     AssocTypeBound(Box<AssocTypeBoundData>),
 262 }
 263
 264 impl ObligationCauseCode<'_> {
 265     // Return the base obligation, ignoring derived obligations.
 266     pub fn peel_derives(&self) -> &Self {
 267         let mut base_cause = self;
 268         while let BuiltinDerivedObligation(cause) | ImplDerivedObligation(cause) = base_cause {
 269             base_cause = &cause.parent_code;
 270         }
 271         base_cause
 272     }
 273 }
 274
 275 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 276 pub struct AssocTypeBoundData {
 277     pub impl_span: Option<Span>,
 278     pub original: Span,
 279     pub bounds: Vec<Span>,
 280 }
 281
 282 // `ObligationCauseCode` is used a lot. Make sure it doesn't unintentionally get bigger.
 283 #[cfg(target_arch = "x86_64")]
 284 static_assert_size!(ObligationCauseCode<'_>, 32);
 285
 286 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 287 pub struct MatchExpressionArmCause<'tcx> {
 288     pub arm_span: Span,
 289     pub source: hir::MatchSource,
 290     pub prior_arms: Vec<Span>,
 291     pub last_ty: Ty<'tcx>,
 292     pub scrut_hir_id: hir::HirId,
 293 }
 294
 295 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 296 pub struct IfExpressionCause {
 297     pub then: Span,
 298     pub outer: Option<Span>,
 299     pub semicolon: Option<Span>,
 300 }
 301
 302 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
 303 pub struct DerivedObligationCause<'tcx> {
 304     /// The trait reference of the parent obligation that led to the
 305     /// current obligation. Note that only trait obligations lead to
 306     /// derived obligations, so we just store the trait reference here
 307     /// directly.
 308     pub parent_trait_ref: ty::PolyTraitRef<'tcx>,
 309
 310     /// The parent trait had this cause.
 311     pub parent_code: Rc<ObligationCauseCode<'tcx>>,
 312 }
 313
 314 /// The following types:
 315 /// * `WhereClause`,
 316 /// * `WellFormed`,
 317 /// * `FromEnv`,
 318 /// * `DomainGoal`,
 319 /// * `Goal`,
 320 /// * `Clause`,
 321 /// * `Environment`,
 322 /// * `InEnvironment`,
 323 /// are used for representing the trait system in the form of
 324 /// logic programming clauses. They are part of the interface
 325 /// for the chalk SLG solver.
 326 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
 327 pub enum WhereClause<'tcx> {
 328     Implemented(ty::TraitPredicate<'tcx>),
 329     ProjectionEq(ty::ProjectionPredicate<'tcx>),
 330     RegionOutlives(ty::RegionOutlivesPredicate<'tcx>),
 331     TypeOutlives(ty::TypeOutlivesPredicate<'tcx>),
 332 }
 333
 334 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
 335 pub enum WellFormed<'tcx> {
 336     Trait(ty::TraitPredicate<'tcx>),
 337     Ty(Ty<'tcx>),
 338 }
 339
 340 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
 341 pub enum FromEnv<'tcx> {
 342     Trait(ty::TraitPredicate<'tcx>),
 343     Ty(Ty<'tcx>),
 344 }
 345
 346 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
 347 pub enum DomainGoal<'tcx> {
 348     Holds(WhereClause<'tcx>),
 349     WellFormed(WellFormed<'tcx>),
 350     FromEnv(FromEnv<'tcx>),
 351     Normalize(ty::ProjectionPredicate<'tcx>),
 352 }
 353
 354 pub type PolyDomainGoal<'tcx> = ty::Binder<DomainGoal<'tcx>>;
 355
 356 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 357 pub enum QuantifierKind {
 358     Universal,
 359     Existential,
 360 }
 361
 362 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
 363 pub enum GoalKind<'tcx> {
 364     Implies(Clauses<'tcx>, Goal<'tcx>),
 365     And(Goal<'tcx>, Goal<'tcx>),
 366     Not(Goal<'tcx>),
 367     DomainGoal(DomainGoal<'tcx>),
 368     Quantified(QuantifierKind, ty::Binder<Goal<'tcx>>),
 369     Subtype(Ty<'tcx>, Ty<'tcx>),
 370     CannotProve,
 371 }
 372
 373 pub type Goal<'tcx> = &'tcx GoalKind<'tcx>;
 374
 375 pub type Goals<'tcx> = &'tcx List<Goal<'tcx>>;
 376
 377 impl<'tcx> DomainGoal<'tcx> {
 378     pub fn into_goal(self) -> GoalKind<'tcx> {
 379         GoalKind::DomainGoal(self)
 380     }
 381
 382     pub fn into_program_clause(self) -> ProgramClause<'tcx> {
 383         ProgramClause {
 384             goal: self,
 385             hypotheses: ty::List::empty(),
 386             category: ProgramClauseCategory::Other,
 387         }
 388     }
 389 }
 390
 391 impl<'tcx> GoalKind<'tcx> {
 392     pub fn from_poly_domain_goal(
 393         domain_goal: PolyDomainGoal<'tcx>,
 394         tcx: TyCtxt<'tcx>,
 395     ) -> GoalKind<'tcx> {
 396         match domain_goal.no_bound_vars() {
 397             Some(p) => p.into_goal(),
 398             None => GoalKind::Quantified(
 399                 QuantifierKind::Universal,
 400                 domain_goal.map_bound(|p| tcx.mk_goal(p.into_goal())),
 401             ),
 402         }
 403     }
 404 }
 405
 406 /// This matches the definition from Page 7 of "A Proof Procedure for the Logic of Hereditary
 407 /// Harrop Formulas".
 408 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
 409 pub enum Clause<'tcx> {
 410     Implies(ProgramClause<'tcx>),
 411     ForAll(ty::Binder<ProgramClause<'tcx>>),
 412 }
 413
 414 impl Clause<'tcx> {
 415     pub fn category(self) -> ProgramClauseCategory {
 416         match self {
 417             Clause::Implies(clause) => clause.category,
 418             Clause::ForAll(clause) => clause.skip_binder().category,
 419         }
 420     }
 421 }
 422
 423 /// Multiple clauses.
 424 pub type Clauses<'tcx> = &'tcx List<Clause<'tcx>>;
 425
 426 /// A "program clause" has the form `D :- G1, ..., Gn`. It is saying
 427 /// that the domain goal `D` is true if `G1...Gn` are provable. This
 428 /// is equivalent to the implication `G1..Gn => D`; we usually write
 429 /// it with the reverse implication operator `:-` to emphasize the way
 430 /// that programs are actually solved (via backchaining, which starts
 431 /// with the goal to solve and proceeds from there).
 432 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
 433 pub struct ProgramClause<'tcx> {
 434     /// This goal will be considered true ...
 435     pub goal: DomainGoal<'tcx>,
 436
 437     /// ... if we can prove these hypotheses (there may be no hypotheses at all):
 438     pub hypotheses: Goals<'tcx>,
 439
 440     /// Useful for filtering clauses.
 441     pub category: ProgramClauseCategory,
 442 }
 443
 444 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
 445 pub enum ProgramClauseCategory {
 446     ImpliedBound,
 447     WellFormed,
 448     Other,
 449 }
 450
 451 /// A set of clauses that we assume to be true.
 452 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
 453 pub struct Environment<'tcx> {
 454     pub clauses: Clauses<'tcx>,
 455 }
 456
 457 impl Environment<'tcx> {
 458     pub fn with<G>(self, goal: G) -> InEnvironment<'tcx, G> {
 459         InEnvironment { environment: self, goal }
 460     }
 461 }
 462
 463 /// Something (usually a goal), along with an environment.
 464 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
 465 pub struct InEnvironment<'tcx, G> {
 466     pub environment: Environment<'tcx>,
 467     pub goal: G,
 468 }
 469
 470 #[derive(Clone, Debug, TypeFoldable)]
 471 pub enum SelectionError<'tcx> {
 472     Unimplemented,
 473     OutputTypeParameterMismatch(
 474         ty::PolyTraitRef<'tcx>,
 475         ty::PolyTraitRef<'tcx>,
 476         ty::error::TypeError<'tcx>,
 477     ),
 478     TraitNotObjectSafe(DefId),
 479     ConstEvalFailure(ErrorHandled),
 480     Overflow,
 481 }
 482
 483 /// When performing resolution, it is typically the case that there
 484 /// can be one of three outcomes:
 485 ///
 486 /// - `Ok(Some(r))`: success occurred with result `r`
 487 /// - `Ok(None)`: could not definitely determine anything, usually due
 488 ///   to inconclusive type inference.
 489 /// - `Err(e)`: error `e` occurred
 490 pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 491
 492 /// Given the successful resolution of an obligation, the `Vtable`
 493 /// indicates where the vtable comes from. Note that while we call this
 494 /// a "vtable", it does not necessarily indicate dynamic dispatch at
 495 /// runtime. `Vtable` instances just tell the compiler where to find
 496 /// methods, but in generic code those methods are typically statically
 497 /// dispatched -- only when an object is constructed is a `Vtable`
 498 /// instance reified into an actual vtable.
 499 ///
 500 /// For example, the vtable may be tied to a specific impl (case A),
 501 /// or it may be relative to some bound that is in scope (case B).
 502 ///
 503 /// ```
 504 /// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
 505 /// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
 506 /// impl Clone for int { ... }             // Impl_3
 507 ///
 508 /// fn foo<T:Clone>(concrete: Option<Box<int>>,
 509 ///                 param: T,
 510 ///                 mixed: Option<T>) {
 511 ///
 512 ///    // Case A: Vtable points at a specific impl. Only possible when
 513 ///    // type is concretely known. If the impl itself has bounded
 514 ///    // type parameters, Vtable will carry resolutions for those as well:
 515 ///    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
 516 ///
 517 ///    // Case B: Vtable must be provided by caller. This applies when
 518 ///    // type is a type parameter.
 519 ///    param.clone();    // VtableParam
 520 ///
 521 ///    // Case C: A mix of cases A and B.
 522 ///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
 523 /// }
 524 /// ```
 525 ///
 526 /// ### The type parameter `N`
 527 ///
 528 /// See explanation on `VtableImplData`.
 529 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 530 pub enum Vtable<'tcx, N> {
 531     /// Vtable identifying a particular impl.
 532     VtableImpl(VtableImplData<'tcx, N>),
 533
 534     /// Vtable for auto trait implementations.
 535     /// This carries the information and nested obligations with regards
 536     /// to an auto implementation for a trait `Trait`. The nested obligations
 537     /// ensure the trait implementation holds for all the constituent types.
 538     VtableAutoImpl(VtableAutoImplData<N>),
 539
 540     /// Successful resolution to an obligation provided by the caller
 541     /// for some type parameter. The `Vec<N>` represents the
 542     /// obligations incurred from normalizing the where-clause (if
 543     /// any).
 544     VtableParam(Vec<N>),
 545
 546     /// Virtual calls through an object.
 547     VtableObject(VtableObjectData<'tcx, N>),
 548
 549     /// Successful resolution for a builtin trait.
 550     VtableBuiltin(VtableBuiltinData<N>),
 551
 552     /// Vtable automatically generated for a closure. The `DefId` is the ID
 553     /// of the closure expression. This is a `VtableImpl` in spirit, but the
 554     /// impl is generated by the compiler and does not appear in the source.
 555     VtableClosure(VtableClosureData<'tcx, N>),
 556
 557     /// Same as above, but for a function pointer type with the given signature.
 558     VtableFnPointer(VtableFnPointerData<'tcx, N>),
 559
 560     /// Vtable automatically generated for a generator.
 561     VtableGenerator(VtableGeneratorData<'tcx, N>),
 562
 563     /// Vtable for a trait alias.
 564     VtableTraitAlias(VtableTraitAliasData<'tcx, N>),
 565 }
 566
 567 impl<'tcx, N> Vtable<'tcx, N> {
 568     pub fn nested_obligations(self) -> Vec<N> {
 569         match self {
 570             VtableImpl(i) => i.nested,
 571             VtableParam(n) => n,
 572             VtableBuiltin(i) => i.nested,
 573             VtableAutoImpl(d) => d.nested,
 574             VtableClosure(c) => c.nested,
 575             VtableGenerator(c) => c.nested,
 576             VtableObject(d) => d.nested,
 577             VtableFnPointer(d) => d.nested,
 578             VtableTraitAlias(d) => d.nested,
 579         }
 580     }
 581
 582     pub fn map<M, F>(self, f: F) -> Vtable<'tcx, M>
 583     where
 584         F: FnMut(N) -> M,
 585     {
 586         match self {
 587             VtableImpl(i) => VtableImpl(VtableImplData {
 588                 impl_def_id: i.impl_def_id,
 589                 substs: i.substs,
 590                 nested: i.nested.into_iter().map(f).collect(),
 591             }),
 592             VtableParam(n) => VtableParam(n.into_iter().map(f).collect()),
 593             VtableBuiltin(i) => {
 594                 VtableBuiltin(VtableBuiltinData { nested: i.nested.into_iter().map(f).collect() })
 595             }
 596             VtableObject(o) => VtableObject(VtableObjectData {
 597                 upcast_trait_ref: o.upcast_trait_ref,
 598                 vtable_base: o.vtable_base,
 599                 nested: o.nested.into_iter().map(f).collect(),
 600             }),
 601             VtableAutoImpl(d) => VtableAutoImpl(VtableAutoImplData {
 602                 trait_def_id: d.trait_def_id,
 603                 nested: d.nested.into_iter().map(f).collect(),
 604             }),
 605             VtableClosure(c) => VtableClosure(VtableClosureData {
 606                 closure_def_id: c.closure_def_id,
 607                 substs: c.substs,
 608                 nested: c.nested.into_iter().map(f).collect(),
 609             }),
 610             VtableGenerator(c) => VtableGenerator(VtableGeneratorData {
 611                 generator_def_id: c.generator_def_id,
 612                 substs: c.substs,
 613                 nested: c.nested.into_iter().map(f).collect(),
 614             }),
 615             VtableFnPointer(p) => VtableFnPointer(VtableFnPointerData {
 616                 fn_ty: p.fn_ty,
 617                 nested: p.nested.into_iter().map(f).collect(),
 618             }),
 619             VtableTraitAlias(d) => VtableTraitAlias(VtableTraitAliasData {
 620                 alias_def_id: d.alias_def_id,
 621                 substs: d.substs,
 622                 nested: d.nested.into_iter().map(f).collect(),
 623             }),
 624         }
 625     }
 626 }
 627
 628 /// Identifies a particular impl in the source, along with a set of
 629 /// substitutions from the impl's type/lifetime parameters. The
 630 /// `nested` vector corresponds to the nested obligations attached to
 631 /// the impl's type parameters.
 632 ///
 633 /// The type parameter `N` indicates the type used for "nested
 634 /// obligations" that are required by the impl. During type-check, this
 635 /// is `Obligation`, as one might expect. During codegen, however, this
 636 /// is `()`, because codegen only requires a shallow resolution of an
 637 /// impl, and nested obligations are satisfied later.
 638 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 639 pub struct VtableImplData<'tcx, N> {
 640     pub impl_def_id: DefId,
 641     pub substs: SubstsRef<'tcx>,
 642     pub nested: Vec<N>,
 643 }
 644
 645 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 646 pub struct VtableGeneratorData<'tcx, N> {
 647     pub generator_def_id: DefId,
 648     pub substs: SubstsRef<'tcx>,
 649     /// Nested obligations. This can be non-empty if the generator
 650     /// signature contains associated types.
 651     pub nested: Vec<N>,
 652 }
 653
 654 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 655 pub struct VtableClosureData<'tcx, N> {
 656     pub closure_def_id: DefId,
 657     pub substs: SubstsRef<'tcx>,
 658     /// Nested obligations. This can be non-empty if the closure
 659     /// signature contains associated types.
 660     pub nested: Vec<N>,
 661 }
 662
 663 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 664 pub struct VtableAutoImplData<N> {
 665     pub trait_def_id: DefId,
 666     pub nested: Vec<N>,
 667 }
 668
 669 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 670 pub struct VtableBuiltinData<N> {
 671     pub nested: Vec<N>,
 672 }
 673
 674 /// A vtable for some object-safe trait `Foo` automatically derived
 675 /// for the object type `Foo`.
 676 #[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 677 pub struct VtableObjectData<'tcx, N> {
 678     /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
 679     pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
 680
 681     /// The vtable is formed by concatenating together the method lists of
 682     /// the base object trait and all supertraits; this is the start of
 683     /// `upcast_trait_ref`'s methods in that vtable.
 684     pub vtable_base: usize,
 685
 686     pub nested: Vec<N>,
 687 }
 688
 689 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 690 pub struct VtableFnPointerData<'tcx, N> {
 691     pub fn_ty: Ty<'tcx>,
 692     pub nested: Vec<N>,
 693 }
 694
 695 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 696 pub struct VtableTraitAliasData<'tcx, N> {
 697     pub alias_def_id: DefId,
 698     pub substs: SubstsRef<'tcx>,
 699     pub nested: Vec<N>,
 700 }
 701
 702 pub trait ExClauseFold<'tcx>
 703 where
 704     Self: chalk_engine::context::Context + Clone,
 705 {
 706     fn fold_ex_clause_with<F: TypeFolder<'tcx>>(
 707         ex_clause: &chalk_engine::ExClause<Self>,
 708         folder: &mut F,
 709     ) -> chalk_engine::ExClause<Self>;
 710
 711     fn visit_ex_clause_with<V: TypeVisitor<'tcx>>(
 712         ex_clause: &chalk_engine::ExClause<Self>,
 713         visitor: &mut V,
 714     ) -> bool;
 715 }
 716
 717 pub trait ChalkContextLift<'tcx>
 718 where
 719     Self: chalk_engine::context::Context + Clone,
 720 {
 721     type LiftedExClause: Debug + 'tcx;
 722     type LiftedDelayedLiteral: Debug + 'tcx;
 723     type LiftedLiteral: Debug + 'tcx;
 724
 725     fn lift_ex_clause_to_tcx(
 726         ex_clause: &chalk_engine::ExClause<Self>,
 727         tcx: TyCtxt<'tcx>,
 728     ) -> Option<Self::LiftedExClause>;
 729
 730     fn lift_delayed_literal_to_tcx(
 731         ex_clause: &chalk_engine::DelayedLiteral<Self>,
 732         tcx: TyCtxt<'tcx>,
 733     ) -> Option<Self::LiftedDelayedLiteral>;
 734
 735     fn lift_literal_to_tcx(
 736         ex_clause: &chalk_engine::Literal<Self>,
 737         tcx: TyCtxt<'tcx>,
 738     ) -> Option<Self::LiftedLiteral>;
 739 }