Move rustc::traits datatypes to module traits::types.

3 files changed, 691 insertions, 681 deletions

diff --git a/src/librustc/traits/auto_trait.rs b/src/librustc/traits/auto_trait.rs
index fdb6432f7c9..d775393a808 100644
--- a/src/librustc/traits/auto_trait.rs
+++ b/src/librustc/traits/auto_trait.rs
@@ -9,6 +9,7 @@ use crate::ty::fold::TypeFolder;
 use crate::ty::{Region, RegionVid};
 
 use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use syntax::ast;
 
 use std::collections::hash_map::Entry;
 use std::collections::VecDeque;
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index b1b3d44044e..0eed762c000 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -19,31 +19,25 @@ mod select;
 mod specialize;
 mod structural_impls;
 mod structural_match;
+mod types;
 mod util;
 pub mod wf;
 
 use crate::infer::outlives::env::OutlivesEnvironment;
 use crate::infer::{InferCtxt, SuppressRegionErrors};
 use crate::middle::region;
-use crate::mir::interpret::ErrorHandled;
 use crate::ty::error::{ExpectedFound, TypeError};
-use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
+use crate::ty::fold::TypeFoldable;
 use crate::ty::subst::{InternalSubsts, SubstsRef};
-use crate::ty::{self, AdtKind, GenericParamDefKind, List, ToPredicate, Ty, TyCtxt, WithConstness};
+use crate::ty::{self, GenericParamDefKind, ToPredicate, Ty, TyCtxt, WithConstness};
 use crate::util::common::ErrorReported;
 use rustc_hir as hir;
 use rustc_hir::def_id::DefId;
-use rustc_macros::HashStable;
 use rustc_span::{Span, DUMMY_SP};
-use syntax::ast;
 
 use std::fmt::Debug;
-use std::rc::Rc;
 
 pub use self::FulfillmentErrorCode::*;
-pub use self::ObligationCauseCode::*;
-pub use self::SelectionError::*;
-pub use self::Vtable::*;
 
 pub use self::coherence::{add_placeholder_note, orphan_check, overlapping_impls};
 pub use self::coherence::{OrphanCheckErr, OverlapResult};
@@ -81,10 +75,7 @@ pub use self::chalk_fulfill::{
     CanonicalGoal as ChalkCanonicalGoal, FulfillmentContext as ChalkFulfillmentContext,
 };
 
-pub use self::FulfillmentErrorCode::*;
-pub use self::ObligationCauseCode::*;
-pub use self::SelectionError::*;
-pub use self::Vtable::*;
+pub use self::types::*;
 
 /// Whether to enable bug compatibility with issue #43355.
 #[derive(Copy, Clone, PartialEq, Eq, Debug)]
@@ -138,392 +129,12 @@ pub type TraitObligation<'tcx> = Obligation<'tcx, ty::PolyTraitPredicate<'tcx>>;
 #[cfg(target_arch = "x86_64")]
 static_assert_size!(PredicateObligation<'_>, 112);
 
-/// The reason why we incurred this obligation; used for error reporting.
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct ObligationCause<'tcx> {
-    pub span: Span,
-
-    /// The ID of the fn body that triggered this obligation. This is
-    /// used for region obligations to determine the precise
-    /// environment in which the region obligation should be evaluated
-    /// (in particular, closures can add new assumptions). See the
-    /// field `region_obligations` of the `FulfillmentContext` for more
-    /// information.
-    pub body_id: hir::HirId,
-
-    pub code: ObligationCauseCode<'tcx>,
-}
-
-impl ObligationCause<'_> {
-    pub fn span(&self, tcx: TyCtxt<'_>) -> Span {
-        match self.code {
-            ObligationCauseCode::CompareImplMethodObligation { .. }
-            | ObligationCauseCode::MainFunctionType
-            | ObligationCauseCode::StartFunctionType => tcx.sess.source_map().def_span(self.span),
-            ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause {
-                arm_span,
-                ..
-            }) => arm_span,
-            _ => self.span,
-        }
-    }
-}
-
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub enum ObligationCauseCode<'tcx> {
-    /// Not well classified or should be obvious from the span.
-    MiscObligation,
-
-    /// A slice or array is WF only if `T: Sized`.
-    SliceOrArrayElem,
-
-    /// A tuple is WF only if its middle elements are `Sized`.
-    TupleElem,
-
-    /// This is the trait reference from the given projection.
-    ProjectionWf(ty::ProjectionTy<'tcx>),
-
-    /// In an impl of trait `X` for type `Y`, type `Y` must
-    /// also implement all supertraits of `X`.
-    ItemObligation(DefId),
-
-    /// Like `ItemObligation`, but with extra detail on the source of the obligation.
-    BindingObligation(DefId, Span),
-
-    /// A type like `&'a T` is WF only if `T: 'a`.
-    ReferenceOutlivesReferent(Ty<'tcx>),
-
-    /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
-    ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
-
-    /// Obligation incurred due to an object cast.
-    ObjectCastObligation(/* Object type */ Ty<'tcx>),
-
-    /// Obligation incurred due to a coercion.
-    Coercion {
-        source: Ty<'tcx>,
-        target: Ty<'tcx>,
-    },
-
-    /// Various cases where expressions must be `Sized` / `Copy` / etc.
-    /// `L = X` implies that `L` is `Sized`.
-    AssignmentLhsSized,
-    /// `(x1, .., xn)` must be `Sized`.
-    TupleInitializerSized,
-    /// `S { ... }` must be `Sized`.
-    StructInitializerSized,
-    /// Type of each variable must be `Sized`.
-    VariableType(hir::HirId),
-    /// Argument type must be `Sized`.
-    SizedArgumentType,
-    /// Return type must be `Sized`.
-    SizedReturnType,
-    /// Yield type must be `Sized`.
-    SizedYieldType,
-    /// `[T, ..n]` implies that `T` must be `Copy`.
-    /// If `true`, suggest `const_in_array_repeat_expressions` feature flag.
-    RepeatVec(bool),
-
-    /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
-    FieldSized {
-        adt_kind: AdtKind,
-        last: bool,
-    },
-
-    /// Constant expressions must be sized.
-    ConstSized,
-
-    /// `static` items must have `Sync` type.
-    SharedStatic,
-
-    BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
-
-    ImplDerivedObligation(DerivedObligationCause<'tcx>),
-
-    /// Error derived when matching traits/impls; see ObligationCause for more details
-    CompareImplMethodObligation {
-        item_name: ast::Name,
-        impl_item_def_id: DefId,
-        trait_item_def_id: DefId,
-    },
-
-    /// Error derived when matching traits/impls; see ObligationCause for more details
-    CompareImplTypeObligation {
-        item_name: ast::Name,
-        impl_item_def_id: DefId,
-        trait_item_def_id: DefId,
-    },
-
-    /// Checking that this expression can be assigned where it needs to be
-    // FIXME(eddyb) #11161 is the original Expr required?
-    ExprAssignable,
-
-    /// Computing common supertype in the arms of a match expression
-    MatchExpressionArm(Box<MatchExpressionArmCause<'tcx>>),
-
-    /// Type error arising from type checking a pattern against an expected type.
-    Pattern {
-        /// The span of the scrutinee or type expression which caused the `root_ty` type.
-        span: Option<Span>,
-        /// The root expected type induced by a scrutinee or type expression.
-        root_ty: Ty<'tcx>,
-        /// Whether the `Span` came from an expression or a type expression.
-        origin_expr: bool,
-    },
-
-    /// Constants in patterns must have `Structural` type.
-    ConstPatternStructural,
-
-    /// Computing common supertype in an if expression
-    IfExpression(Box<IfExpressionCause>),
-
-    /// Computing common supertype of an if expression with no else counter-part
-    IfExpressionWithNoElse,
-
-    /// `main` has wrong type
-    MainFunctionType,
-
-    /// `start` has wrong type
-    StartFunctionType,
-
-    /// Intrinsic has wrong type
-    IntrinsicType,
-
-    /// Method receiver
-    MethodReceiver,
-
-    /// `return` with no expression
-    ReturnNoExpression,
-
-    /// `return` with an expression
-    ReturnValue(hir::HirId),
-
-    /// Return type of this function
-    ReturnType,
-
-    /// Block implicit return
-    BlockTailExpression(hir::HirId),
-
-    /// #[feature(trivial_bounds)] is not enabled
-    TrivialBound,
-
-    AssocTypeBound(Box<AssocTypeBoundData>),
-}
-
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct AssocTypeBoundData {
-    pub impl_span: Option<Span>,
-    pub original: Span,
-    pub bounds: Vec<Span>,
-}
-
-// `ObligationCauseCode` is used a lot. Make sure it doesn't unintentionally get bigger.
-#[cfg(target_arch = "x86_64")]
-static_assert_size!(ObligationCauseCode<'_>, 32);
-
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct MatchExpressionArmCause<'tcx> {
-    pub arm_span: Span,
-    pub source: hir::MatchSource,
-    pub prior_arms: Vec<Span>,
-    pub last_ty: Ty<'tcx>,
-    pub scrut_hir_id: hir::HirId,
-}
-
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct IfExpressionCause {
-    pub then: Span,
-    pub outer: Option<Span>,
-    pub semicolon: Option<Span>,
-}
-
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
-pub struct DerivedObligationCause<'tcx> {
-    /// The trait reference of the parent obligation that led to the
-    /// current obligation. Note that only trait obligations lead to
-    /// derived obligations, so we just store the trait reference here
-    /// directly.
-    parent_trait_ref: ty::PolyTraitRef<'tcx>,
-
-    /// The parent trait had this cause.
-    parent_code: Rc<ObligationCauseCode<'tcx>>,
-}
-
 pub type Obligations<'tcx, O> = Vec<Obligation<'tcx, O>>;
 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
 pub type TraitObligations<'tcx> = Vec<TraitObligation<'tcx>>;
 
-/// The following types:
-/// * `WhereClause`,
-/// * `WellFormed`,
-/// * `FromEnv`,
-/// * `DomainGoal`,
-/// * `Goal`,
-/// * `Clause`,
-/// * `Environment`,
-/// * `InEnvironment`,
-/// are used for representing the trait system in the form of
-/// logic programming clauses. They are part of the interface
-/// for the chalk SLG solver.
-#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
-pub enum WhereClause<'tcx> {
-    Implemented(ty::TraitPredicate<'tcx>),
-    ProjectionEq(ty::ProjectionPredicate<'tcx>),
-    RegionOutlives(ty::RegionOutlivesPredicate<'tcx>),
-    TypeOutlives(ty::TypeOutlivesPredicate<'tcx>),
-}
-
-#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
-pub enum WellFormed<'tcx> {
-    Trait(ty::TraitPredicate<'tcx>),
-    Ty(Ty<'tcx>),
-}
-
-#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
-pub enum FromEnv<'tcx> {
-    Trait(ty::TraitPredicate<'tcx>),
-    Ty(Ty<'tcx>),
-}
-
-#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
-pub enum DomainGoal<'tcx> {
-    Holds(WhereClause<'tcx>),
-    WellFormed(WellFormed<'tcx>),
-    FromEnv(FromEnv<'tcx>),
-    Normalize(ty::ProjectionPredicate<'tcx>),
-}
-
-pub type PolyDomainGoal<'tcx> = ty::Binder<DomainGoal<'tcx>>;
-
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
-pub enum QuantifierKind {
-    Universal,
-    Existential,
-}
-
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
-pub enum GoalKind<'tcx> {
-    Implies(Clauses<'tcx>, Goal<'tcx>),
-    And(Goal<'tcx>, Goal<'tcx>),
-    Not(Goal<'tcx>),
-    DomainGoal(DomainGoal<'tcx>),
-    Quantified(QuantifierKind, ty::Binder<Goal<'tcx>>),
-    Subtype(Ty<'tcx>, Ty<'tcx>),
-    CannotProve,
-}
-
-pub type Goal<'tcx> = &'tcx GoalKind<'tcx>;
-
-pub type Goals<'tcx> = &'tcx List<Goal<'tcx>>;
-
-impl<'tcx> DomainGoal<'tcx> {
-    pub fn into_goal(self) -> GoalKind<'tcx> {
-        GoalKind::DomainGoal(self)
-    }
-
-    pub fn into_program_clause(self) -> ProgramClause<'tcx> {
-        ProgramClause {
-            goal: self,
-            hypotheses: ty::List::empty(),
-            category: ProgramClauseCategory::Other,
-        }
-    }
-}
-
-impl<'tcx> GoalKind<'tcx> {
-    pub fn from_poly_domain_goal(
-        domain_goal: PolyDomainGoal<'tcx>,
-        tcx: TyCtxt<'tcx>,
-    ) -> GoalKind<'tcx> {
-        match domain_goal.no_bound_vars() {
-            Some(p) => p.into_goal(),
-            None => GoalKind::Quantified(
-                QuantifierKind::Universal,
-                domain_goal.map_bound(|p| tcx.mk_goal(p.into_goal())),
-            ),
-        }
-    }
-}
-
-/// This matches the definition from Page 7 of "A Proof Procedure for the Logic of Hereditary
-/// Harrop Formulas".
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
-pub enum Clause<'tcx> {
-    Implies(ProgramClause<'tcx>),
-    ForAll(ty::Binder<ProgramClause<'tcx>>),
-}
-
-impl Clause<'tcx> {
-    pub fn category(self) -> ProgramClauseCategory {
-        match self {
-            Clause::Implies(clause) => clause.category,
-            Clause::ForAll(clause) => clause.skip_binder().category,
-        }
-    }
-}
-
-/// Multiple clauses.
-pub type Clauses<'tcx> = &'tcx List<Clause<'tcx>>;
-
-/// A "program clause" has the form `D :- G1, ..., Gn`. It is saying
-/// that the domain goal `D` is true if `G1...Gn` are provable. This
-/// is equivalent to the implication `G1..Gn => D`; we usually write
-/// it with the reverse implication operator `:-` to emphasize the way
-/// that programs are actually solved (via backchaining, which starts
-/// with the goal to solve and proceeds from there).
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
-pub struct ProgramClause<'tcx> {
-    /// This goal will be considered true ...
-    pub goal: DomainGoal<'tcx>,
-
-    /// ... if we can prove these hypotheses (there may be no hypotheses at all):
-    pub hypotheses: Goals<'tcx>,
-
-    /// Useful for filtering clauses.
-    pub category: ProgramClauseCategory,
-}
-
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
-pub enum ProgramClauseCategory {
-    ImpliedBound,
-    WellFormed,
-    Other,
-}
-
-/// A set of clauses that we assume to be true.
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
-pub struct Environment<'tcx> {
-    pub clauses: Clauses<'tcx>,
-}
-
-impl Environment<'tcx> {
-    pub fn with<G>(self, goal: G) -> InEnvironment<'tcx, G> {
-        InEnvironment { environment: self, goal }
-    }
-}
-
-/// Something (usually a goal), along with an environment.
-#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
-pub struct InEnvironment<'tcx, G> {
-    pub environment: Environment<'tcx>,
-    pub goal: G,
-}
-
 pub type Selection<'tcx> = Vtable<'tcx, PredicateObligation<'tcx>>;
 
-#[derive(Clone, Debug, TypeFoldable)]
-pub enum SelectionError<'tcx> {
-    Unimplemented,
-    OutputTypeParameterMismatch(
-        ty::PolyTraitRef<'tcx>,
-        ty::PolyTraitRef<'tcx>,
-        ty::error::TypeError<'tcx>,
-    ),
-    TraitNotObjectSafe(DefId),
-    ConstEvalFailure(ErrorHandled),
-    Overflow,
-}
-
 pub struct FulfillmentError<'tcx> {
     pub obligation: PredicateObligation<'tcx>,
     pub code: FulfillmentErrorCode<'tcx>,
@@ -541,164 +152,6 @@ pub enum FulfillmentErrorCode<'tcx> {
     CodeAmbiguity,
 }
 
-/// When performing resolution, it is typically the case that there
-/// can be one of three outcomes:
-///
-/// - `Ok(Some(r))`: success occurred with result `r`
-/// - `Ok(None)`: could not definitely determine anything, usually due
-///   to inconclusive type inference.
-/// - `Err(e)`: error `e` occurred
-pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
-
-/// Given the successful resolution of an obligation, the `Vtable`
-/// indicates where the vtable comes from. Note that while we call this
-/// a "vtable", it does not necessarily indicate dynamic dispatch at
-/// runtime. `Vtable` instances just tell the compiler where to find
-/// methods, but in generic code those methods are typically statically
-/// dispatched -- only when an object is constructed is a `Vtable`
-/// instance reified into an actual vtable.
-///
-/// For example, the vtable may be tied to a specific impl (case A),
-/// or it may be relative to some bound that is in scope (case B).
-///
-/// ```
-/// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
-/// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
-/// impl Clone for int { ... }             // Impl_3
-///
-/// fn foo<T:Clone>(concrete: Option<Box<int>>,
-///                 param: T,
-///                 mixed: Option<T>) {
-///
-///    // Case A: Vtable points at a specific impl. Only possible when
-///    // type is concretely known. If the impl itself has bounded
-///    // type parameters, Vtable will carry resolutions for those as well:
-///    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
-///
-///    // Case B: Vtable must be provided by caller. This applies when
-///    // type is a type parameter.
-///    param.clone();    // VtableParam
-///
-///    // Case C: A mix of cases A and B.
-///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
-/// }
-/// ```
-///
-/// ### The type parameter `N`
-///
-/// See explanation on `VtableImplData`.
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub enum Vtable<'tcx, N> {
-    /// Vtable identifying a particular impl.
-    VtableImpl(VtableImplData<'tcx, N>),
-
-    /// Vtable for auto trait implementations.
-    /// This carries the information and nested obligations with regards
-    /// to an auto implementation for a trait `Trait`. The nested obligations
-    /// ensure the trait implementation holds for all the constituent types.
-    VtableAutoImpl(VtableAutoImplData<N>),
-
-    /// Successful resolution to an obligation provided by the caller
-    /// for some type parameter. The `Vec<N>` represents the
-    /// obligations incurred from normalizing the where-clause (if
-    /// any).
-    VtableParam(Vec<N>),
-
-    /// Virtual calls through an object.
-    VtableObject(VtableObjectData<'tcx, N>),
-
-    /// Successful resolution for a builtin trait.
-    VtableBuiltin(VtableBuiltinData<N>),
-
-    /// Vtable automatically generated for a closure. The `DefId` is the ID
-    /// of the closure expression. This is a `VtableImpl` in spirit, but the
-    /// impl is generated by the compiler and does not appear in the source.
-    VtableClosure(VtableClosureData<'tcx, N>),
-
-    /// Same as above, but for a function pointer type with the given signature.
-    VtableFnPointer(VtableFnPointerData<'tcx, N>),
-
-    /// Vtable automatically generated for a generator.
-    VtableGenerator(VtableGeneratorData<'tcx, N>),
-
-    /// Vtable for a trait alias.
-    VtableTraitAlias(VtableTraitAliasData<'tcx, N>),
-}
-
-/// Identifies a particular impl in the source, along with a set of
-/// substitutions from the impl's type/lifetime parameters. The
-/// `nested` vector corresponds to the nested obligations attached to
-/// the impl's type parameters.
-///
-/// The type parameter `N` indicates the type used for "nested
-/// obligations" that are required by the impl. During type-check, this
-/// is `Obligation`, as one might expect. During codegen, however, this
-/// is `()`, because codegen only requires a shallow resolution of an
-/// impl, and nested obligations are satisfied later.
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableImplData<'tcx, N> {
-    pub impl_def_id: DefId,
-    pub substs: SubstsRef<'tcx>,
-    pub nested: Vec<N>,
-}
-
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableGeneratorData<'tcx, N> {
-    pub generator_def_id: DefId,
-    pub substs: SubstsRef<'tcx>,
-    /// Nested obligations. This can be non-empty if the generator
-    /// signature contains associated types.
-    pub nested: Vec<N>,
-}
-
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableClosureData<'tcx, N> {
-    pub closure_def_id: DefId,
-    pub substs: SubstsRef<'tcx>,
-    /// Nested obligations. This can be non-empty if the closure
-    /// signature contains associated types.
-    pub nested: Vec<N>,
-}
-
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableAutoImplData<N> {
-    pub trait_def_id: DefId,
-    pub nested: Vec<N>,
-}
-
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableBuiltinData<N> {
-    pub nested: Vec<N>,
-}
-
-/// A vtable for some object-safe trait `Foo` automatically derived
-/// for the object type `Foo`.
-#[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableObjectData<'tcx, N> {
-    /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
-    pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
-
-    /// The vtable is formed by concatenating together the method lists of
-    /// the base object trait and all supertraits; this is the start of
-    /// `upcast_trait_ref`'s methods in that vtable.
-    pub vtable_base: usize,
-
-    pub nested: Vec<N>,
-}
-
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableFnPointerData<'tcx, N> {
-    pub fn_ty: Ty<'tcx>,
-    pub nested: Vec<N>,
-}
-
-#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
-pub struct VtableTraitAliasData<'tcx, N> {
-    pub alias_def_id: DefId,
-    pub substs: SubstsRef<'tcx>,
-    pub nested: Vec<N>,
-}
-
 /// Creates predicate obligations from the generic bounds.
 pub fn predicates_for_generics<'tcx>(
     cause: ObligationCause<'tcx>,
@@ -1147,97 +600,6 @@ impl<'tcx, O> Obligation<'tcx, O> {
     }
 }
 
-impl<'tcx> ObligationCause<'tcx> {
-    #[inline]
-    pub fn new(
-        span: Span,
-        body_id: hir::HirId,
-        code: ObligationCauseCode<'tcx>,
-    ) -> ObligationCause<'tcx> {
-        ObligationCause { span, body_id, code }
-    }
-
-    pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> {
-        ObligationCause { span, body_id, code: MiscObligation }
-    }
-
-    pub fn dummy() -> ObligationCause<'tcx> {
-        ObligationCause { span: DUMMY_SP, body_id: hir::CRATE_HIR_ID, code: MiscObligation }
-    }
-}
-
-impl ObligationCauseCode<'_> {
-    // Return the base obligation, ignoring derived obligations.
-    pub fn peel_derives(&self) -> &Self {
-        let mut base_cause = self;
-        while let BuiltinDerivedObligation(cause) | ImplDerivedObligation(cause) = base_cause {
-            base_cause = &cause.parent_code;
-        }
-        base_cause
-    }
-}
-
-impl<'tcx, N> Vtable<'tcx, N> {
-    pub fn nested_obligations(self) -> Vec<N> {
-        match self {
-            VtableImpl(i) => i.nested,
-            VtableParam(n) => n,
-            VtableBuiltin(i) => i.nested,
-            VtableAutoImpl(d) => d.nested,
-            VtableClosure(c) => c.nested,
-            VtableGenerator(c) => c.nested,
-            VtableObject(d) => d.nested,
-            VtableFnPointer(d) => d.nested,
-            VtableTraitAlias(d) => d.nested,
-        }
-    }
-
-    pub fn map<M, F>(self, f: F) -> Vtable<'tcx, M>
-    where
-        F: FnMut(N) -> M,
-    {
-        match self {
-            VtableImpl(i) => VtableImpl(VtableImplData {
-                impl_def_id: i.impl_def_id,
-                substs: i.substs,
-                nested: i.nested.into_iter().map(f).collect(),
-            }),
-            VtableParam(n) => VtableParam(n.into_iter().map(f).collect()),
-            VtableBuiltin(i) => {
-                VtableBuiltin(VtableBuiltinData { nested: i.nested.into_iter().map(f).collect() })
-            }
-            VtableObject(o) => VtableObject(VtableObjectData {
-                upcast_trait_ref: o.upcast_trait_ref,
-                vtable_base: o.vtable_base,
-                nested: o.nested.into_iter().map(f).collect(),
-            }),
-            VtableAutoImpl(d) => VtableAutoImpl(VtableAutoImplData {
-                trait_def_id: d.trait_def_id,
-                nested: d.nested.into_iter().map(f).collect(),
-            }),
-            VtableClosure(c) => VtableClosure(VtableClosureData {
-                closure_def_id: c.closure_def_id,
-                substs: c.substs,
-                nested: c.nested.into_iter().map(f).collect(),
-            }),
-            VtableGenerator(c) => VtableGenerator(VtableGeneratorData {
-                generator_def_id: c.generator_def_id,
-                substs: c.substs,
-                nested: c.nested.into_iter().map(f).collect(),
-            }),
-            VtableFnPointer(p) => VtableFnPointer(VtableFnPointerData {
-                fn_ty: p.fn_ty,
-                nested: p.nested.into_iter().map(f).collect(),
-            }),
-            VtableTraitAlias(d) => VtableTraitAlias(VtableTraitAliasData {
-                alias_def_id: d.alias_def_id,
-                substs: d.substs,
-                nested: d.nested.into_iter().map(f).collect(),
-            }),
-        }
-    }
-}
-
 impl<'tcx> FulfillmentError<'tcx> {
     fn new(
         obligation: PredicateObligation<'tcx>,
@@ -1265,42 +627,3 @@ pub fn provide(providers: &mut ty::query::Providers<'_>) {
         ..*providers
     };
 }
-
-pub trait ExClauseFold<'tcx>
-where
-    Self: chalk_engine::context::Context + Clone,
-{
-    fn fold_ex_clause_with<F: TypeFolder<'tcx>>(
-        ex_clause: &chalk_engine::ExClause<Self>,
-        folder: &mut F,
-    ) -> chalk_engine::ExClause<Self>;
-
-    fn visit_ex_clause_with<V: TypeVisitor<'tcx>>(
-        ex_clause: &chalk_engine::ExClause<Self>,
-        visitor: &mut V,
-    ) -> bool;
-}
-
-pub trait ChalkContextLift<'tcx>
-where
-    Self: chalk_engine::context::Context + Clone,
-{
-    type LiftedExClause: Debug + 'tcx;
-    type LiftedDelayedLiteral: Debug + 'tcx;
-    type LiftedLiteral: Debug + 'tcx;
-
-    fn lift_ex_clause_to_tcx(
-        ex_clause: &chalk_engine::ExClause<Self>,
-        tcx: TyCtxt<'tcx>,
-    ) -> Option<Self::LiftedExClause>;
-
-    fn lift_delayed_literal_to_tcx(
-        ex_clause: &chalk_engine::DelayedLiteral<Self>,
-        tcx: TyCtxt<'tcx>,
-    ) -> Option<Self::LiftedDelayedLiteral>;
-
-    fn lift_literal_to_tcx(
-        ex_clause: &chalk_engine::Literal<Self>,
-        tcx: TyCtxt<'tcx>,
-    ) -> Option<Self::LiftedLiteral>;
-}
diff --git a/src/librustc/traits/types/mod.rs b/src/librustc/traits/types/mod.rs
new file mode 100644
index 00000000000..c4a066d5ec0
--- /dev/null
+++ b/src/librustc/traits/types/mod.rs
@@ -0,0 +1,686 @@
+//! Trait Resolution. See the [rustc guide] for more information on how this works.
+//!
+//! [rustc guide]: https://rust-lang.github.io/rustc-guide/traits/resolution.html
+
+use crate::mir::interpret::ErrorHandled;
+use crate::ty::fold::{TypeFolder, TypeVisitor};
+use crate::ty::subst::SubstsRef;
+use crate::ty::{self, AdtKind, List, Ty, TyCtxt};
+
+use rustc_hir as hir;
+use rustc_hir::def_id::DefId;
+use rustc_span::{Span, DUMMY_SP};
+use syntax::ast;
+
+use std::fmt::Debug;
+use std::rc::Rc;
+
+pub use self::ObligationCauseCode::*;
+pub use self::SelectionError::*;
+pub use self::Vtable::*;
+
+/// The reason why we incurred this obligation; used for error reporting.
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct ObligationCause<'tcx> {
+    pub span: Span,
+
+    /// The ID of the fn body that triggered this obligation. This is
+    /// used for region obligations to determine the precise
+    /// environment in which the region obligation should be evaluated
+    /// (in particular, closures can add new assumptions). See the
+    /// field `region_obligations` of the `FulfillmentContext` for more
+    /// information.
+    pub body_id: hir::HirId,
+
+    pub code: ObligationCauseCode<'tcx>,
+}
+
+impl<'tcx> ObligationCause<'tcx> {
+    #[inline]
+    pub fn new(
+        span: Span,
+        body_id: hir::HirId,
+        code: ObligationCauseCode<'tcx>,
+    ) -> ObligationCause<'tcx> {
+        ObligationCause { span, body_id, code }
+    }
+
+    pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> {
+        ObligationCause { span, body_id, code: MiscObligation }
+    }
+
+    pub fn dummy() -> ObligationCause<'tcx> {
+        ObligationCause { span: DUMMY_SP, body_id: hir::CRATE_HIR_ID, code: MiscObligation }
+    }
+
+    pub fn span(&self, tcx: TyCtxt<'tcx>) -> Span {
+        match self.code {
+            ObligationCauseCode::CompareImplMethodObligation { .. }
+            | ObligationCauseCode::MainFunctionType
+            | ObligationCauseCode::StartFunctionType => tcx.sess.source_map().def_span(self.span),
+            ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause {
+                arm_span,
+                ..
+            }) => arm_span,
+            _ => self.span,
+        }
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub enum ObligationCauseCode<'tcx> {
+    /// Not well classified or should be obvious from the span.
+    MiscObligation,
+
+    /// A slice or array is WF only if `T: Sized`.
+    SliceOrArrayElem,
+
+    /// A tuple is WF only if its middle elements are `Sized`.
+    TupleElem,
+
+    /// This is the trait reference from the given projection.
+    ProjectionWf(ty::ProjectionTy<'tcx>),
+
+    /// In an impl of trait `X` for type `Y`, type `Y` must
+    /// also implement all supertraits of `X`.
+    ItemObligation(DefId),
+
+    /// Like `ItemObligation`, but with extra detail on the source of the obligation.
+    BindingObligation(DefId, Span),
+
+    /// A type like `&'a T` is WF only if `T: 'a`.
+    ReferenceOutlivesReferent(Ty<'tcx>),
+
+    /// A type like `Box<Foo<'a> + 'b>` is WF only if `'b: 'a`.
+    ObjectTypeBound(Ty<'tcx>, ty::Region<'tcx>),
+
+    /// Obligation incurred due to an object cast.
+    ObjectCastObligation(/* Object type */ Ty<'tcx>),
+
+    /// Obligation incurred due to a coercion.
+    Coercion {
+        source: Ty<'tcx>,
+        target: Ty<'tcx>,
+    },
+
+    /// Various cases where expressions must be `Sized` / `Copy` / etc.
+    /// `L = X` implies that `L` is `Sized`.
+    AssignmentLhsSized,
+    /// `(x1, .., xn)` must be `Sized`.
+    TupleInitializerSized,
+    /// `S { ... }` must be `Sized`.
+    StructInitializerSized,
+    /// Type of each variable must be `Sized`.
+    VariableType(hir::HirId),
+    /// Argument type must be `Sized`.
+    SizedArgumentType,
+    /// Return type must be `Sized`.
+    SizedReturnType,
+    /// Yield type must be `Sized`.
+    SizedYieldType,
+    /// `[T, ..n]` implies that `T` must be `Copy`.
+    /// If `true`, suggest `const_in_array_repeat_expressions` feature flag.
+    RepeatVec(bool),
+
+    /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
+    FieldSized {
+        adt_kind: AdtKind,
+        last: bool,
+    },
+
+    /// Constant expressions must be sized.
+    ConstSized,
+
+    /// `static` items must have `Sync` type.
+    SharedStatic,
+
+    BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
+
+    ImplDerivedObligation(DerivedObligationCause<'tcx>),
+
+    /// Error derived when matching traits/impls; see ObligationCause for more details
+    CompareImplMethodObligation {
+        item_name: ast::Name,
+        impl_item_def_id: DefId,
+        trait_item_def_id: DefId,
+    },
+
+    /// Error derived when matching traits/impls; see ObligationCause for more details
+    CompareImplTypeObligation {
+        item_name: ast::Name,
+        impl_item_def_id: DefId,
+        trait_item_def_id: DefId,
+    },
+
+    /// Checking that this expression can be assigned where it needs to be
+    // FIXME(eddyb) #11161 is the original Expr required?
+    ExprAssignable,
+
+    /// Computing common supertype in the arms of a match expression
+    MatchExpressionArm(Box<MatchExpressionArmCause<'tcx>>),
+
+    /// Type error arising from type checking a pattern against an expected type.
+    Pattern {
+        /// The span of the scrutinee or type expression which caused the `root_ty` type.
+        span: Option<Span>,
+        /// The root expected type induced by a scrutinee or type expression.
+        root_ty: Ty<'tcx>,
+        /// Whether the `Span` came from an expression or a type expression.
+        origin_expr: bool,
+    },
+
+    /// Constants in patterns must have `Structural` type.
+    ConstPatternStructural,
+
+    /// Computing common supertype in an if expression
+    IfExpression(Box<IfExpressionCause>),
+
+    /// Computing common supertype of an if expression with no else counter-part
+    IfExpressionWithNoElse,
+
+    /// `main` has wrong type
+    MainFunctionType,
+
+    /// `start` has wrong type
+    StartFunctionType,
+
+    /// Intrinsic has wrong type
+    IntrinsicType,
+
+    /// Method receiver
+    MethodReceiver,
+
+    /// `return` with no expression
+    ReturnNoExpression,
+
+    /// `return` with an expression
+    ReturnValue(hir::HirId),
+
+    /// Return type of this function
+    ReturnType,
+
+    /// Block implicit return
+    BlockTailExpression(hir::HirId),
+
+    /// #[feature(trivial_bounds)] is not enabled
+    TrivialBound,
+
+    AssocTypeBound(Box<AssocTypeBoundData>),
+}
+
+impl ObligationCauseCode<'_> {
+    // Return the base obligation, ignoring derived obligations.
+    pub fn peel_derives(&self) -> &Self {
+        let mut base_cause = self;
+        while let BuiltinDerivedObligation(cause) | ImplDerivedObligation(cause) = base_cause {
+            base_cause = &cause.parent_code;
+        }
+        base_cause
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct AssocTypeBoundData {
+    pub impl_span: Option<Span>,
+    pub original: Span,
+    pub bounds: Vec<Span>,
+}
+
+// `ObligationCauseCode` is used a lot. Make sure it doesn't unintentionally get bigger.
+#[cfg(target_arch = "x86_64")]
+static_assert_size!(ObligationCauseCode<'_>, 32);
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct MatchExpressionArmCause<'tcx> {
+    pub arm_span: Span,
+    pub source: hir::MatchSource,
+    pub prior_arms: Vec<Span>,
+    pub last_ty: Ty<'tcx>,
+    pub scrut_hir_id: hir::HirId,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct IfExpressionCause {
+    pub then: Span,
+    pub outer: Option<Span>,
+    pub semicolon: Option<Span>,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct DerivedObligationCause<'tcx> {
+    /// The trait reference of the parent obligation that led to the
+    /// current obligation. Note that only trait obligations lead to
+    /// derived obligations, so we just store the trait reference here
+    /// directly.
+    pub parent_trait_ref: ty::PolyTraitRef<'tcx>,
+
+    /// The parent trait had this cause.
+    pub parent_code: Rc<ObligationCauseCode<'tcx>>,
+}
+
+/// The following types:
+/// * `WhereClause`,
+/// * `WellFormed`,
+/// * `FromEnv`,
+/// * `DomainGoal`,
+/// * `Goal`,
+/// * `Clause`,
+/// * `Environment`,
+/// * `InEnvironment`,
+/// are used for representing the trait system in the form of
+/// logic programming clauses. They are part of the interface
+/// for the chalk SLG solver.
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
+pub enum WhereClause<'tcx> {
+    Implemented(ty::TraitPredicate<'tcx>),
+    ProjectionEq(ty::ProjectionPredicate<'tcx>),
+    RegionOutlives(ty::RegionOutlivesPredicate<'tcx>),
+    TypeOutlives(ty::TypeOutlivesPredicate<'tcx>),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
+pub enum WellFormed<'tcx> {
+    Trait(ty::TraitPredicate<'tcx>),
+    Ty(Ty<'tcx>),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
+pub enum FromEnv<'tcx> {
+    Trait(ty::TraitPredicate<'tcx>),
+    Ty(Ty<'tcx>),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
+pub enum DomainGoal<'tcx> {
+    Holds(WhereClause<'tcx>),
+    WellFormed(WellFormed<'tcx>),
+    FromEnv(FromEnv<'tcx>),
+    Normalize(ty::ProjectionPredicate<'tcx>),
+}
+
+pub type PolyDomainGoal<'tcx> = ty::Binder<DomainGoal<'tcx>>;
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
+pub enum QuantifierKind {
+    Universal,
+    Existential,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, Lift)]
+pub enum GoalKind<'tcx> {
+    Implies(Clauses<'tcx>, Goal<'tcx>),
+    And(Goal<'tcx>, Goal<'tcx>),
+    Not(Goal<'tcx>),
+    DomainGoal(DomainGoal<'tcx>),
+    Quantified(QuantifierKind, ty::Binder<Goal<'tcx>>),
+    Subtype(Ty<'tcx>, Ty<'tcx>),
+    CannotProve,
+}
+
+pub type Goal<'tcx> = &'tcx GoalKind<'tcx>;
+
+pub type Goals<'tcx> = &'tcx List<Goal<'tcx>>;
+
+impl<'tcx> DomainGoal<'tcx> {
+    pub fn into_goal(self) -> GoalKind<'tcx> {
+        GoalKind::DomainGoal(self)
+    }
+
+    pub fn into_program_clause(self) -> ProgramClause<'tcx> {
+        ProgramClause {
+            goal: self,
+            hypotheses: ty::List::empty(),
+            category: ProgramClauseCategory::Other,
+        }
+    }
+}
+
+impl<'tcx> GoalKind<'tcx> {
+    pub fn from_poly_domain_goal(
+        domain_goal: PolyDomainGoal<'tcx>,
+        tcx: TyCtxt<'tcx>,
+    ) -> GoalKind<'tcx> {
+        match domain_goal.no_bound_vars() {
+            Some(p) => p.into_goal(),
+            None => GoalKind::Quantified(
+                QuantifierKind::Universal,
+                domain_goal.map_bound(|p| tcx.mk_goal(p.into_goal())),
+            ),
+        }
+    }
+}
+
+/// This matches the definition from Page 7 of "A Proof Procedure for the Logic of Hereditary
+/// Harrop Formulas".
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
+pub enum Clause<'tcx> {
+    Implies(ProgramClause<'tcx>),
+    ForAll(ty::Binder<ProgramClause<'tcx>>),
+}
+
+impl Clause<'tcx> {
+    pub fn category(self) -> ProgramClauseCategory {
+        match self {
+            Clause::Implies(clause) => clause.category,
+            Clause::ForAll(clause) => clause.skip_binder().category,
+        }
+    }
+}
+
+/// Multiple clauses.
+pub type Clauses<'tcx> = &'tcx List<Clause<'tcx>>;
+
+/// A "program clause" has the form `D :- G1, ..., Gn`. It is saying
+/// that the domain goal `D` is true if `G1...Gn` are provable. This
+/// is equivalent to the implication `G1..Gn => D`; we usually write
+/// it with the reverse implication operator `:-` to emphasize the way
+/// that programs are actually solved (via backchaining, which starts
+/// with the goal to solve and proceeds from there).
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
+pub struct ProgramClause<'tcx> {
+    /// This goal will be considered true ...
+    pub goal: DomainGoal<'tcx>,
+
+    /// ... if we can prove these hypotheses (there may be no hypotheses at all):
+    pub hypotheses: Goals<'tcx>,
+
+    /// Useful for filtering clauses.
+    pub category: ProgramClauseCategory,
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable)]
+pub enum ProgramClauseCategory {
+    ImpliedBound,
+    WellFormed,
+    Other,
+}
+
+/// A set of clauses that we assume to be true.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
+pub struct Environment<'tcx> {
+    pub clauses: Clauses<'tcx>,
+}
+
+impl Environment<'tcx> {
+    pub fn with<G>(self, goal: G) -> InEnvironment<'tcx, G> {
+        InEnvironment { environment: self, goal }
+    }
+}
+
+/// Something (usually a goal), along with an environment.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable)]
+pub struct InEnvironment<'tcx, G> {
+    pub environment: Environment<'tcx>,
+    pub goal: G,
+}
+
+#[derive(Clone, Debug, TypeFoldable)]
+pub enum SelectionError<'tcx> {
+    Unimplemented,
+    OutputTypeParameterMismatch(
+        ty::PolyTraitRef<'tcx>,
+        ty::PolyTraitRef<'tcx>,
+        ty::error::TypeError<'tcx>,
+    ),
+    TraitNotObjectSafe(DefId),
+    ConstEvalFailure(ErrorHandled),
+    Overflow,
+}
+
+/// When performing resolution, it is typically the case that there
+/// can be one of three outcomes:
+///
+/// - `Ok(Some(r))`: success occurred with result `r`
+/// - `Ok(None)`: could not definitely determine anything, usually due
+///   to inconclusive type inference.
+/// - `Err(e)`: error `e` occurred
+pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
+
+/// Given the successful resolution of an obligation, the `Vtable`
+/// indicates where the vtable comes from. Note that while we call this
+/// a "vtable", it does not necessarily indicate dynamic dispatch at
+/// runtime. `Vtable` instances just tell the compiler where to find
+/// methods, but in generic code those methods are typically statically
+/// dispatched -- only when an object is constructed is a `Vtable`
+/// instance reified into an actual vtable.
+///
+/// For example, the vtable may be tied to a specific impl (case A),
+/// or it may be relative to some bound that is in scope (case B).
+///
+/// ```
+/// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
+/// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
+/// impl Clone for int { ... }             // Impl_3
+///
+/// fn foo<T:Clone>(concrete: Option<Box<int>>,
+///                 param: T,
+///                 mixed: Option<T>) {
+///
+///    // Case A: Vtable points at a specific impl. Only possible when
+///    // type is concretely known. If the impl itself has bounded
+///    // type parameters, Vtable will carry resolutions for those as well:
+///    concrete.clone(); // Vtable(Impl_1, [Vtable(Impl_2, [Vtable(Impl_3)])])
+///
+///    // Case B: Vtable must be provided by caller. This applies when
+///    // type is a type parameter.
+///    param.clone();    // VtableParam
+///
+///    // Case C: A mix of cases A and B.
+///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
+/// }
+/// ```
+///
+/// ### The type parameter `N`
+///
+/// See explanation on `VtableImplData`.
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub enum Vtable<'tcx, N> {
+    /// Vtable identifying a particular impl.
+    VtableImpl(VtableImplData<'tcx, N>),
+
+    /// Vtable for auto trait implementations.
+    /// This carries the information and nested obligations with regards
+    /// to an auto implementation for a trait `Trait`. The nested obligations
+    /// ensure the trait implementation holds for all the constituent types.
+    VtableAutoImpl(VtableAutoImplData<N>),
+
+    /// Successful resolution to an obligation provided by the caller
+    /// for some type parameter. The `Vec<N>` represents the
+    /// obligations incurred from normalizing the where-clause (if
+    /// any).
+    VtableParam(Vec<N>),
+
+    /// Virtual calls through an object.
+    VtableObject(VtableObjectData<'tcx, N>),
+
+    /// Successful resolution for a builtin trait.
+    VtableBuiltin(VtableBuiltinData<N>),
+
+    /// Vtable automatically generated for a closure. The `DefId` is the ID
+    /// of the closure expression. This is a `VtableImpl` in spirit, but the
+    /// impl is generated by the compiler and does not appear in the source.
+    VtableClosure(VtableClosureData<'tcx, N>),
+
+    /// Same as above, but for a function pointer type with the given signature.
+    VtableFnPointer(VtableFnPointerData<'tcx, N>),
+
+    /// Vtable automatically generated for a generator.
+    VtableGenerator(VtableGeneratorData<'tcx, N>),
+
+    /// Vtable for a trait alias.
+    VtableTraitAlias(VtableTraitAliasData<'tcx, N>),
+}
+
+impl<'tcx, N> Vtable<'tcx, N> {
+    pub fn nested_obligations(self) -> Vec<N> {
+        match self {
+            VtableImpl(i) => i.nested,
+            VtableParam(n) => n,
+            VtableBuiltin(i) => i.nested,
+            VtableAutoImpl(d) => d.nested,
+            VtableClosure(c) => c.nested,
+            VtableGenerator(c) => c.nested,
+            VtableObject(d) => d.nested,
+            VtableFnPointer(d) => d.nested,
+            VtableTraitAlias(d) => d.nested,
+        }
+    }
+
+    pub fn map<M, F>(self, f: F) -> Vtable<'tcx, M>
+    where
+        F: FnMut(N) -> M,
+    {
+        match self {
+            VtableImpl(i) => VtableImpl(VtableImplData {
+                impl_def_id: i.impl_def_id,
+                substs: i.substs,
+                nested: i.nested.into_iter().map(f).collect(),
+            }),
+            VtableParam(n) => VtableParam(n.into_iter().map(f).collect()),
+            VtableBuiltin(i) => {
+                VtableBuiltin(VtableBuiltinData { nested: i.nested.into_iter().map(f).collect() })
+            }
+            VtableObject(o) => VtableObject(VtableObjectData {
+                upcast_trait_ref: o.upcast_trait_ref,
+                vtable_base: o.vtable_base,
+                nested: o.nested.into_iter().map(f).collect(),
+            }),
+            VtableAutoImpl(d) => VtableAutoImpl(VtableAutoImplData {
+                trait_def_id: d.trait_def_id,
+                nested: d.nested.into_iter().map(f).collect(),
+            }),
+            VtableClosure(c) => VtableClosure(VtableClosureData {
+                closure_def_id: c.closure_def_id,
+                substs: c.substs,
+                nested: c.nested.into_iter().map(f).collect(),
+            }),
+            VtableGenerator(c) => VtableGenerator(VtableGeneratorData {
+                generator_def_id: c.generator_def_id,
+                substs: c.substs,
+                nested: c.nested.into_iter().map(f).collect(),
+            }),
+            VtableFnPointer(p) => VtableFnPointer(VtableFnPointerData {
+                fn_ty: p.fn_ty,
+                nested: p.nested.into_iter().map(f).collect(),
+            }),
+            VtableTraitAlias(d) => VtableTraitAlias(VtableTraitAliasData {
+                alias_def_id: d.alias_def_id,
+                substs: d.substs,
+                nested: d.nested.into_iter().map(f).collect(),
+            }),
+        }
+    }
+}
+
+/// Identifies a particular impl in the source, along with a set of
+/// substitutions from the impl's type/lifetime parameters. The
+/// `nested` vector corresponds to the nested obligations attached to
+/// the impl's type parameters.
+///
+/// The type parameter `N` indicates the type used for "nested
+/// obligations" that are required by the impl. During type-check, this
+/// is `Obligation`, as one might expect. During codegen, however, this
+/// is `()`, because codegen only requires a shallow resolution of an
+/// impl, and nested obligations are satisfied later.
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableImplData<'tcx, N> {
+    pub impl_def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableGeneratorData<'tcx, N> {
+    pub generator_def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+    /// Nested obligations. This can be non-empty if the generator
+    /// signature contains associated types.
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableClosureData<'tcx, N> {
+    pub closure_def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+    /// Nested obligations. This can be non-empty if the closure
+    /// signature contains associated types.
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableAutoImplData<N> {
+    pub trait_def_id: DefId,
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableBuiltinData<N> {
+    pub nested: Vec<N>,
+}
+
+/// A vtable for some object-safe trait `Foo` automatically derived
+/// for the object type `Foo`.
+#[derive(PartialEq, Eq, Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableObjectData<'tcx, N> {
+    /// `Foo` upcast to the obligation trait. This will be some supertrait of `Foo`.
+    pub upcast_trait_ref: ty::PolyTraitRef<'tcx>,
+
+    /// The vtable is formed by concatenating together the method lists of
+    /// the base object trait and all supertraits; this is the start of
+    /// `upcast_trait_ref`'s methods in that vtable.
+    pub vtable_base: usize,
+
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableFnPointerData<'tcx, N> {
+    pub fn_ty: Ty<'tcx>,
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
+pub struct VtableTraitAliasData<'tcx, N> {
+    pub alias_def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+    pub nested: Vec<N>,
+}
+
+pub trait ExClauseFold<'tcx>
+where
+    Self: chalk_engine::context::Context + Clone,
+{
+    fn fold_ex_clause_with<F: TypeFolder<'tcx>>(
+        ex_clause: &chalk_engine::ExClause<Self>,
+        folder: &mut F,
+    ) -> chalk_engine::ExClause<Self>;
+
+    fn visit_ex_clause_with<V: TypeVisitor<'tcx>>(
+        ex_clause: &chalk_engine::ExClause<Self>,
+        visitor: &mut V,
+    ) -> bool;
+}
+
+pub trait ChalkContextLift<'tcx>
+where
+    Self: chalk_engine::context::Context + Clone,
+{
+    type LiftedExClause: Debug + 'tcx;
+    type LiftedDelayedLiteral: Debug + 'tcx;
+    type LiftedLiteral: Debug + 'tcx;
+
+    fn lift_ex_clause_to_tcx(
+        ex_clause: &chalk_engine::ExClause<Self>,
+        tcx: TyCtxt<'tcx>,
+    ) -> Option<Self::LiftedExClause>;
+
+    fn lift_delayed_literal_to_tcx(
+        ex_clause: &chalk_engine::DelayedLiteral<Self>,
+        tcx: TyCtxt<'tcx>,
+    ) -> Option<Self::LiftedDelayedLiteral>;
+
+    fn lift_literal_to_tcx(
+        ex_clause: &chalk_engine::Literal<Self>,
+        tcx: TyCtxt<'tcx>,
+    ) -> Option<Self::LiftedLiteral>;
+}