Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

7 files changed, 2416 insertions, 0 deletions

diff --git a/compiler/rustc_middle/src/traits/chalk.rs b/compiler/rustc_middle/src/traits/chalk.rs
new file mode 100644
index 000000000..6d4af8bea
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/chalk.rs
@@ -0,0 +1,403 @@
+//! Types required for Chalk-related queries
+//!
+//! The primary purpose of this file is defining an implementation for the
+//! `chalk_ir::interner::Interner` trait. The primary purpose of this trait, as
+//! its name suggest, is to provide an abstraction boundary for creating
+//! interned Chalk types.
+
+use rustc_middle::ty::{self, AdtDef, TyCtxt};
+
+use rustc_hir::def_id::DefId;
+use rustc_target::spec::abi::Abi;
+
+use std::cmp::Ordering;
+use std::fmt;
+use std::hash::{Hash, Hasher};
+
+#[derive(Copy, Clone)]
+pub struct RustInterner<'tcx> {
+    pub tcx: TyCtxt<'tcx>,
+}
+
+/// We don't ever actually need this. It's only required for derives.
+impl<'tcx> Hash for RustInterner<'tcx> {
+    fn hash<H: Hasher>(&self, _state: &mut H) {}
+}
+
+/// We don't ever actually need this. It's only required for derives.
+impl<'tcx> Ord for RustInterner<'tcx> {
+    fn cmp(&self, _other: &Self) -> Ordering {
+        Ordering::Equal
+    }
+}
+
+/// We don't ever actually need this. It's only required for derives.
+impl<'tcx> PartialOrd for RustInterner<'tcx> {
+    fn partial_cmp(&self, _other: &Self) -> Option<Ordering> {
+        None
+    }
+}
+
+/// We don't ever actually need this. It's only required for derives.
+impl<'tcx> PartialEq for RustInterner<'tcx> {
+    fn eq(&self, _other: &Self) -> bool {
+        false
+    }
+}
+
+/// We don't ever actually need this. It's only required for derives.
+impl<'tcx> Eq for RustInterner<'tcx> {}
+
+impl fmt::Debug for RustInterner<'_> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "RustInterner")
+    }
+}
+
+// Right now, there is no interning at all. I was running into problems with
+// adding interning in `ty/context.rs` for Chalk types with
+// `parallel-compiler = true`. -jackh726
+impl<'tcx> chalk_ir::interner::Interner for RustInterner<'tcx> {
+    type InternedType = Box<chalk_ir::TyData<Self>>;
+    type InternedLifetime = Box<chalk_ir::LifetimeData<Self>>;
+    type InternedConst = Box<chalk_ir::ConstData<Self>>;
+    type InternedConcreteConst = ty::ValTree<'tcx>;
+    type InternedGenericArg = Box<chalk_ir::GenericArgData<Self>>;
+    type InternedGoal = Box<chalk_ir::GoalData<Self>>;
+    type InternedGoals = Vec<chalk_ir::Goal<Self>>;
+    type InternedSubstitution = Vec<chalk_ir::GenericArg<Self>>;
+    type InternedProgramClause = Box<chalk_ir::ProgramClauseData<Self>>;
+    type InternedProgramClauses = Vec<chalk_ir::ProgramClause<Self>>;
+    type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
+    type InternedVariableKinds = Vec<chalk_ir::VariableKind<Self>>;
+    type InternedCanonicalVarKinds = Vec<chalk_ir::CanonicalVarKind<Self>>;
+    type InternedVariances = Vec<chalk_ir::Variance>;
+    type InternedConstraints = Vec<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>>;
+    type DefId = DefId;
+    type InternedAdtId = AdtDef<'tcx>;
+    type Identifier = ();
+    type FnAbi = Abi;
+
+    fn debug_program_clause_implication(
+        pci: &chalk_ir::ProgramClauseImplication<Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        let mut write = || {
+            write!(fmt, "{:?}", pci.consequence)?;
+
+            let conditions = pci.conditions.interned();
+            let constraints = pci.constraints.interned();
+
+            let conds = conditions.len();
+            let consts = constraints.len();
+            if conds == 0 && consts == 0 {
+                return Ok(());
+            }
+
+            write!(fmt, " :- ")?;
+
+            if conds != 0 {
+                for cond in &conditions[..conds - 1] {
+                    write!(fmt, "{:?}, ", cond)?;
+                }
+                write!(fmt, "{:?}", conditions[conds - 1])?;
+            }
+
+            if conds != 0 && consts != 0 {
+                write!(fmt, " ; ")?;
+            }
+
+            if consts != 0 {
+                for constraint in &constraints[..consts - 1] {
+                    write!(fmt, "{:?}, ", constraint)?;
+                }
+                write!(fmt, "{:?}", constraints[consts - 1])?;
+            }
+
+            Ok(())
+        };
+        Some(write())
+    }
+
+    fn debug_substitution(
+        substitution: &chalk_ir::Substitution<Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        Some(write!(fmt, "{:?}", substitution.interned()))
+    }
+
+    fn debug_separator_trait_ref(
+        separator_trait_ref: &chalk_ir::SeparatorTraitRef<'_, Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        let substitution = &separator_trait_ref.trait_ref.substitution;
+        let parameters = substitution.interned();
+        Some(write!(
+            fmt,
+            "{:?}{}{:?}{:?}",
+            parameters[0],
+            separator_trait_ref.separator,
+            separator_trait_ref.trait_ref.trait_id,
+            chalk_ir::debug::Angle(&parameters[1..])
+        ))
+    }
+
+    fn debug_quantified_where_clauses(
+        clauses: &chalk_ir::QuantifiedWhereClauses<Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        Some(write!(fmt, "{:?}", clauses.interned()))
+    }
+
+    fn debug_ty(ty: &chalk_ir::Ty<Self>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
+        match &ty.interned().kind {
+            chalk_ir::TyKind::Ref(chalk_ir::Mutability::Not, lifetime, ty) => {
+                Some(write!(fmt, "(&{:?} {:?})", lifetime, ty))
+            }
+            chalk_ir::TyKind::Ref(chalk_ir::Mutability::Mut, lifetime, ty) => {
+                Some(write!(fmt, "(&{:?} mut {:?})", lifetime, ty))
+            }
+            chalk_ir::TyKind::Array(ty, len) => Some(write!(fmt, "[{:?}; {:?}]", ty, len)),
+            chalk_ir::TyKind::Slice(ty) => Some(write!(fmt, "[{:?}]", ty)),
+            chalk_ir::TyKind::Tuple(len, substs) => Some((|| {
+                write!(fmt, "(")?;
+                for (idx, substitution) in substs.interned().iter().enumerate() {
+                    if idx == *len && *len != 1 {
+                        // Don't add a trailing comma if the tuple has more than one element
+                        write!(fmt, "{:?}", substitution)?;
+                    } else {
+                        write!(fmt, "{:?},", substitution)?;
+                    }
+                }
+                write!(fmt, ")")
+            })()),
+            _ => None,
+        }
+    }
+
+    fn debug_alias(
+        alias_ty: &chalk_ir::AliasTy<Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        match alias_ty {
+            chalk_ir::AliasTy::Projection(projection_ty) => {
+                Self::debug_projection_ty(projection_ty, fmt)
+            }
+            chalk_ir::AliasTy::Opaque(opaque_ty) => Self::debug_opaque_ty(opaque_ty, fmt),
+        }
+    }
+
+    fn debug_projection_ty(
+        projection_ty: &chalk_ir::ProjectionTy<Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        Some(write!(
+            fmt,
+            "projection: {:?} {:?}",
+            projection_ty.associated_ty_id, projection_ty.substitution,
+        ))
+    }
+
+    fn debug_opaque_ty(
+        opaque_ty: &chalk_ir::OpaqueTy<Self>,
+        fmt: &mut fmt::Formatter<'_>,
+    ) -> Option<fmt::Result> {
+        Some(write!(fmt, "{:?}", opaque_ty.opaque_ty_id))
+    }
+
+    fn intern_ty(self, ty: chalk_ir::TyKind<Self>) -> Self::InternedType {
+        let flags = ty.compute_flags(self);
+        Box::new(chalk_ir::TyData { kind: ty, flags: flags })
+    }
+
+    fn ty_data<'a>(self, ty: &'a Self::InternedType) -> &'a chalk_ir::TyData<Self> {
+        ty
+    }
+
+    fn intern_lifetime(self, lifetime: chalk_ir::LifetimeData<Self>) -> Self::InternedLifetime {
+        Box::new(lifetime)
+    }
+
+    fn lifetime_data<'a>(
+        self,
+        lifetime: &'a Self::InternedLifetime,
+    ) -> &'a chalk_ir::LifetimeData<Self> {
+        &lifetime
+    }
+
+    fn intern_const(self, constant: chalk_ir::ConstData<Self>) -> Self::InternedConst {
+        Box::new(constant)
+    }
+
+    fn const_data<'a>(self, constant: &'a Self::InternedConst) -> &'a chalk_ir::ConstData<Self> {
+        &constant
+    }
+
+    fn const_eq(
+        self,
+        _ty: &Self::InternedType,
+        c1: &Self::InternedConcreteConst,
+        c2: &Self::InternedConcreteConst,
+    ) -> bool {
+        c1 == c2
+    }
+
+    fn intern_generic_arg(self, data: chalk_ir::GenericArgData<Self>) -> Self::InternedGenericArg {
+        Box::new(data)
+    }
+
+    fn generic_arg_data<'a>(
+        self,
+        data: &'a Self::InternedGenericArg,
+    ) -> &'a chalk_ir::GenericArgData<Self> {
+        &data
+    }
+
+    fn intern_goal(self, goal: chalk_ir::GoalData<Self>) -> Self::InternedGoal {
+        Box::new(goal)
+    }
+
+    fn goal_data<'a>(self, goal: &'a Self::InternedGoal) -> &'a chalk_ir::GoalData<Self> {
+        &goal
+    }
+
+    fn intern_goals<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::Goal<Self>, E>>,
+    ) -> Result<Self::InternedGoals, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn goals_data<'a>(self, goals: &'a Self::InternedGoals) -> &'a [chalk_ir::Goal<Self>] {
+        goals
+    }
+
+    fn intern_substitution<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::GenericArg<Self>, E>>,
+    ) -> Result<Self::InternedSubstitution, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn substitution_data<'a>(
+        self,
+        substitution: &'a Self::InternedSubstitution,
+    ) -> &'a [chalk_ir::GenericArg<Self>] {
+        substitution
+    }
+
+    fn intern_program_clause(
+        self,
+        data: chalk_ir::ProgramClauseData<Self>,
+    ) -> Self::InternedProgramClause {
+        Box::new(data)
+    }
+
+    fn program_clause_data<'a>(
+        self,
+        clause: &'a Self::InternedProgramClause,
+    ) -> &'a chalk_ir::ProgramClauseData<Self> {
+        &clause
+    }
+
+    fn intern_program_clauses<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::ProgramClause<Self>, E>>,
+    ) -> Result<Self::InternedProgramClauses, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn program_clauses_data<'a>(
+        self,
+        clauses: &'a Self::InternedProgramClauses,
+    ) -> &'a [chalk_ir::ProgramClause<Self>] {
+        clauses
+    }
+
+    fn intern_quantified_where_clauses<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::QuantifiedWhereClause<Self>, E>>,
+    ) -> Result<Self::InternedQuantifiedWhereClauses, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn quantified_where_clauses_data<'a>(
+        self,
+        clauses: &'a Self::InternedQuantifiedWhereClauses,
+    ) -> &'a [chalk_ir::QuantifiedWhereClause<Self>] {
+        clauses
+    }
+
+    fn intern_generic_arg_kinds<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::VariableKind<Self>, E>>,
+    ) -> Result<Self::InternedVariableKinds, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn variable_kinds_data<'a>(
+        self,
+        parameter_kinds: &'a Self::InternedVariableKinds,
+    ) -> &'a [chalk_ir::VariableKind<Self>] {
+        parameter_kinds
+    }
+
+    fn intern_canonical_var_kinds<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::CanonicalVarKind<Self>, E>>,
+    ) -> Result<Self::InternedCanonicalVarKinds, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn canonical_var_kinds_data<'a>(
+        self,
+        canonical_var_kinds: &'a Self::InternedCanonicalVarKinds,
+    ) -> &'a [chalk_ir::CanonicalVarKind<Self>] {
+        canonical_var_kinds
+    }
+
+    fn intern_constraints<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>, E>>,
+    ) -> Result<Self::InternedConstraints, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn constraints_data<'a>(
+        self,
+        constraints: &'a Self::InternedConstraints,
+    ) -> &'a [chalk_ir::InEnvironment<chalk_ir::Constraint<Self>>] {
+        constraints
+    }
+
+    fn intern_variances<E>(
+        self,
+        data: impl IntoIterator<Item = Result<chalk_ir::Variance, E>>,
+    ) -> Result<Self::InternedVariances, E> {
+        data.into_iter().collect::<Result<Vec<_>, _>>()
+    }
+
+    fn variances_data<'a>(
+        self,
+        variances: &'a Self::InternedVariances,
+    ) -> &'a [chalk_ir::Variance] {
+        variances
+    }
+}
+
+impl<'tcx> chalk_ir::interner::HasInterner for RustInterner<'tcx> {
+    type Interner = Self;
+}
+
+/// A chalk environment and goal.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable, TypeFoldable, TypeVisitable)]
+pub struct ChalkEnvironmentAndGoal<'tcx> {
+    pub environment: &'tcx ty::List<ty::Predicate<'tcx>>,
+    pub goal: ty::Predicate<'tcx>,
+}
+
+impl<'tcx> fmt::Display for ChalkEnvironmentAndGoal<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "environment: {:?}, goal: {}", self.environment, self.goal)
+    }
+}
diff --git a/compiler/rustc_middle/src/traits/mod.rs b/compiler/rustc_middle/src/traits/mod.rs
new file mode 100644
index 000000000..72b848c3e
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/mod.rs
@@ -0,0 +1,1026 @@
+//! Trait Resolution. See the [rustc dev guide] for more information on how this works.
+//!
+//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html
+
+mod chalk;
+pub mod query;
+pub mod select;
+pub mod specialization_graph;
+mod structural_impls;
+pub mod util;
+
+use crate::infer::canonical::Canonical;
+use crate::ty::abstract_const::NotConstEvaluatable;
+use crate::ty::subst::SubstsRef;
+use crate::ty::{self, AdtKind, Predicate, Ty, TyCtxt};
+
+use rustc_data_structures::sync::Lrc;
+use rustc_errors::{Applicability, Diagnostic};
+use rustc_hir as hir;
+use rustc_hir::def_id::{DefId, LocalDefId};
+use rustc_span::symbol::Symbol;
+use rustc_span::{Span, DUMMY_SP};
+use smallvec::SmallVec;
+
+use std::borrow::Cow;
+use std::hash::{Hash, Hasher};
+
+pub use self::select::{EvaluationCache, EvaluationResult, OverflowError, SelectionCache};
+
+pub type CanonicalChalkEnvironmentAndGoal<'tcx> = Canonical<'tcx, ChalkEnvironmentAndGoal<'tcx>>;
+
+pub use self::ObligationCauseCode::*;
+
+pub use self::chalk::{ChalkEnvironmentAndGoal, RustInterner as ChalkRustInterner};
+
+/// Depending on the stage of compilation, we want projection to be
+/// more or less conservative.
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, HashStable)]
+pub enum Reveal {
+    /// At type-checking time, we refuse to project any associated
+    /// type that is marked `default`. Non-`default` ("final") types
+    /// are always projected. This is necessary in general for
+    /// soundness of specialization. However, we *could* allow
+    /// projections in fully-monomorphic cases. We choose not to,
+    /// because we prefer for `default type` to force the type
+    /// definition to be treated abstractly by any consumers of the
+    /// impl. Concretely, that means that the following example will
+    /// fail to compile:
+    ///
+    /// ```compile_fail,E0308
+    /// #![feature(specialization)]
+    /// trait Assoc {
+    ///     type Output;
+    /// }
+    ///
+    /// impl<T> Assoc for T {
+    ///     default type Output = bool;
+    /// }
+    ///
+    /// fn main() {
+    ///     let x: <() as Assoc>::Output = true;
+    /// }
+    /// ```
+    ///
+    /// We also do not reveal the hidden type of opaque types during
+    /// type-checking.
+    UserFacing,
+
+    /// At codegen time, all monomorphic projections will succeed.
+    /// Also, `impl Trait` is normalized to the concrete type,
+    /// which has to be already collected by type-checking.
+    ///
+    /// NOTE: as `impl Trait`'s concrete type should *never*
+    /// be observable directly by the user, `Reveal::All`
+    /// should not be used by checks which may expose
+    /// type equality or type contents to the user.
+    /// There are some exceptions, e.g., around auto traits and
+    /// transmute-checking, which expose some details, but
+    /// not the whole concrete type of the `impl Trait`.
+    All,
+}
+
+/// The reason why we incurred this obligation; used for error reporting.
+///
+/// Non-misc `ObligationCauseCode`s are stored on the heap. This gives the
+/// best trade-off between keeping the type small (which makes copies cheaper)
+/// while not doing too many heap allocations.
+///
+/// We do not want to intern this as there are a lot of obligation causes which
+/// only live for a short period of time.
+#[derive(Clone, Debug, PartialEq, Eq, Lift)]
+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,
+
+    code: InternedObligationCauseCode<'tcx>,
+}
+
+// This custom hash function speeds up hashing for `Obligation` deduplication
+// greatly by skipping the `code` field, which can be large and complex. That
+// shouldn't affect hash quality much since there are several other fields in
+// `Obligation` which should be unique enough, especially the predicate itself
+// which is hashed as an interned pointer. See #90996.
+impl Hash for ObligationCause<'_> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.body_id.hash(state);
+        self.span.hash(state);
+    }
+}
+
+impl<'tcx> ObligationCause<'tcx> {
+    #[inline]
+    pub fn new(
+        span: Span,
+        body_id: hir::HirId,
+        code: ObligationCauseCode<'tcx>,
+    ) -> ObligationCause<'tcx> {
+        ObligationCause { span, body_id, code: code.into() }
+    }
+
+    pub fn misc(span: Span, body_id: hir::HirId) -> ObligationCause<'tcx> {
+        ObligationCause::new(span, body_id, MiscObligation)
+    }
+
+    #[inline(always)]
+    pub fn dummy() -> ObligationCause<'tcx> {
+        ObligationCause::dummy_with_span(DUMMY_SP)
+    }
+
+    #[inline(always)]
+    pub fn dummy_with_span(span: Span) -> ObligationCause<'tcx> {
+        ObligationCause { span, body_id: hir::CRATE_HIR_ID, code: Default::default() }
+    }
+
+    pub fn span(&self) -> Span {
+        match *self.code() {
+            ObligationCauseCode::MatchExpressionArm(box MatchExpressionArmCause {
+                arm_span,
+                ..
+            }) => arm_span,
+            _ => self.span,
+        }
+    }
+
+    #[inline]
+    pub fn code(&self) -> &ObligationCauseCode<'tcx> {
+        &self.code
+    }
+
+    pub fn map_code(
+        &mut self,
+        f: impl FnOnce(InternedObligationCauseCode<'tcx>) -> ObligationCauseCode<'tcx>,
+    ) {
+        self.code = f(std::mem::take(&mut self.code)).into();
+    }
+
+    pub fn derived_cause(
+        mut self,
+        parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+        variant: impl FnOnce(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>,
+    ) -> ObligationCause<'tcx> {
+        /*!
+         * Creates a cause for obligations that are derived from
+         * `obligation` by a recursive search (e.g., for a builtin
+         * bound, or eventually a `auto trait Foo`). If `obligation`
+         * is itself a derived obligation, this is just a clone, but
+         * otherwise we create a "derived obligation" cause so as to
+         * keep track of the original root obligation for error
+         * reporting.
+         */
+
+        // NOTE(flaper87): As of now, it keeps track of the whole error
+        // chain. Ideally, we should have a way to configure this either
+        // by using -Z verbose or just a CLI argument.
+        self.code =
+            variant(DerivedObligationCause { parent_trait_pred, parent_code: self.code }).into();
+        self
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
+pub struct UnifyReceiverContext<'tcx> {
+    pub assoc_item: ty::AssocItem,
+    pub param_env: ty::ParamEnv<'tcx>,
+    pub substs: SubstsRef<'tcx>,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift, Default)]
+pub struct InternedObligationCauseCode<'tcx> {
+    /// `None` for `ObligationCauseCode::MiscObligation` (a common case, occurs ~60% of
+    /// the time). `Some` otherwise.
+    code: Option<Lrc<ObligationCauseCode<'tcx>>>,
+}
+
+impl<'tcx> ObligationCauseCode<'tcx> {
+    #[inline(always)]
+    fn into(self) -> InternedObligationCauseCode<'tcx> {
+        InternedObligationCauseCode {
+            code: if let ObligationCauseCode::MiscObligation = self {
+                None
+            } else {
+                Some(Lrc::new(self))
+            },
+        }
+    }
+}
+
+impl<'tcx> std::ops::Deref for InternedObligationCauseCode<'tcx> {
+    type Target = ObligationCauseCode<'tcx>;
+
+    fn deref(&self) -> &Self::Target {
+        self.code.as_deref().unwrap_or(&ObligationCauseCode::MiscObligation)
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
+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(/* Concrete type */ Ty<'tcx>, /* 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(Option<Span>),
+    /// Return type must be `Sized`.
+    SizedReturnType,
+    /// Yield type must be `Sized`.
+    SizedYieldType,
+    /// Box expression result type must be `Sized`.
+    SizedBoxType,
+    /// Inline asm operand type must be `Sized`.
+    InlineAsmSized,
+    /// `[expr; N]` requires `type_of(expr): Copy`.
+    RepeatElementCopy {
+        /// If element is a `const fn` we display a help message suggesting to move the
+        /// function call to a new `const` item while saying that `T` doesn't implement `Copy`.
+        is_const_fn: bool,
+    },
+
+    /// Types of fields (other than the last, except for packed structs) in a struct must be sized.
+    FieldSized {
+        adt_kind: AdtKind,
+        span: Span,
+        last: bool,
+    },
+
+    /// Constant expressions must be sized.
+    ConstSized,
+
+    /// `static` items must have `Sync` type.
+    SharedStatic,
+
+    BuiltinDerivedObligation(DerivedObligationCause<'tcx>),
+
+    ImplDerivedObligation(Box<ImplDerivedObligationCause<'tcx>>),
+
+    DerivedObligation(DerivedObligationCause<'tcx>),
+
+    FunctionArgumentObligation {
+        /// The node of the relevant argument in the function call.
+        arg_hir_id: hir::HirId,
+        /// The node of the function call.
+        call_hir_id: hir::HirId,
+        /// The obligation introduced by this argument.
+        parent_code: InternedObligationCauseCode<'tcx>,
+    },
+
+    /// Error derived when matching traits/impls; see ObligationCause for more details
+    CompareImplItemObligation {
+        impl_item_def_id: LocalDefId,
+        trait_item_def_id: DefId,
+        kind: ty::AssocKind,
+    },
+
+    /// Checking that the bounds of a trait's associated type hold for a given impl
+    CheckAssociatedTypeBounds {
+        impl_item_def_id: LocalDefId,
+        trait_item_def_id: DefId,
+    },
+
+    /// Checking that this expression can be assigned to its target.
+    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<'tcx>>),
+
+    /// 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,
+
+    /// A let else block does not diverge
+    LetElse,
+
+    /// Method receiver
+    MethodReceiver,
+
+    UnifyReceiver(Box<UnifyReceiverContext<'tcx>>),
+
+    /// `return` with no expression
+    ReturnNoExpression,
+
+    /// `return` with an expression
+    ReturnValue(hir::HirId),
+
+    /// Return type of this function
+    ReturnType,
+
+    /// Opaque return type of this function
+    OpaqueReturnType(Option<(Ty<'tcx>, Span)>),
+
+    /// Block implicit return
+    BlockTailExpression(hir::HirId),
+
+    /// #[feature(trivial_bounds)] is not enabled
+    TrivialBound,
+
+    /// If `X` is the concrete type of an opaque type `impl Y`, then `X` must implement `Y`
+    OpaqueType,
+
+    AwaitableExpr(Option<hir::HirId>),
+
+    ForLoopIterator,
+
+    QuestionMark,
+
+    /// Well-formed checking. If a `WellFormedLoc` is provided,
+    /// then it will be used to perform HIR-based wf checking
+    /// after an error occurs, in order to generate a more precise error span.
+    /// This is purely for diagnostic purposes - it is always
+    /// correct to use `MiscObligation` instead, or to specify
+    /// `WellFormed(None)`
+    WellFormed(Option<WellFormedLoc>),
+
+    /// From `match_impl`. The cause for us having to match an impl, and the DefId we are matching against.
+    MatchImpl(ObligationCause<'tcx>, DefId),
+
+    BinOp {
+        rhs_span: Option<Span>,
+        is_lit: bool,
+        output_pred: Option<Predicate<'tcx>>,
+    },
+}
+
+/// The 'location' at which we try to perform HIR-based wf checking.
+/// This information is used to obtain an `hir::Ty`, which
+/// we can walk in order to obtain precise spans for any
+/// 'nested' types (e.g. `Foo` in `Option<Foo>`).
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, HashStable)]
+pub enum WellFormedLoc {
+    /// Use the type of the provided definition.
+    Ty(LocalDefId),
+    /// Use the type of the parameter of the provided function.
+    /// We cannot use `hir::Param`, since the function may
+    /// not have a body (e.g. a trait method definition)
+    Param {
+        /// The function to lookup the parameter in
+        function: LocalDefId,
+        /// The index of the parameter to use.
+        /// Parameters are indexed from 0, with the return type
+        /// being the last 'parameter'
+        param_idx: u16,
+    },
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
+pub struct ImplDerivedObligationCause<'tcx> {
+    pub derived: DerivedObligationCause<'tcx>,
+    pub impl_def_id: DefId,
+    pub span: Span,
+}
+
+impl<'tcx> ObligationCauseCode<'tcx> {
+    // Return the base obligation, ignoring derived obligations.
+    pub fn peel_derives(&self) -> &Self {
+        let mut base_cause = self;
+        while let Some((parent_code, _)) = base_cause.parent() {
+            base_cause = parent_code;
+        }
+        base_cause
+    }
+
+    pub fn parent(&self) -> Option<(&Self, Option<ty::PolyTraitPredicate<'tcx>>)> {
+        match self {
+            FunctionArgumentObligation { parent_code, .. } => Some((parent_code, None)),
+            BuiltinDerivedObligation(derived)
+            | DerivedObligation(derived)
+            | ImplDerivedObligation(box ImplDerivedObligationCause { derived, .. }) => {
+                Some((&derived.parent_code, Some(derived.parent_trait_pred)))
+            }
+            _ => None,
+        }
+    }
+}
+
+// `ObligationCauseCode` is used a lot. Make sure it doesn't unintentionally get bigger.
+#[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
+static_assert_size!(ObligationCauseCode<'_>, 48);
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+pub enum StatementAsExpression {
+    CorrectType,
+    NeedsBoxing,
+}
+
+impl<'tcx> ty::Lift<'tcx> for StatementAsExpression {
+    type Lifted = StatementAsExpression;
+    fn lift_to_tcx(self, _tcx: TyCtxt<'tcx>) -> Option<StatementAsExpression> {
+        Some(self)
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
+pub struct MatchExpressionArmCause<'tcx> {
+    pub arm_block_id: Option<hir::HirId>,
+    pub arm_ty: Ty<'tcx>,
+    pub arm_span: Span,
+    pub prior_arm_block_id: Option<hir::HirId>,
+    pub prior_arm_ty: Ty<'tcx>,
+    pub prior_arm_span: Span,
+    pub scrut_span: Span,
+    pub source: hir::MatchSource,
+    pub prior_arms: Vec<Span>,
+    pub scrut_hir_id: hir::HirId,
+    pub opt_suggest_box_span: Option<Span>,
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Lift, TypeFoldable, TypeVisitable)]
+pub struct IfExpressionCause<'tcx> {
+    pub then_id: hir::HirId,
+    pub else_id: hir::HirId,
+    pub then_ty: Ty<'tcx>,
+    pub else_ty: Ty<'tcx>,
+    pub outer_span: Option<Span>,
+    pub opt_suggest_box_span: Option<Span>,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, Lift)]
+pub struct DerivedObligationCause<'tcx> {
+    /// The trait predicate 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 predicate here
+    /// directly.
+    pub parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+
+    /// The parent trait had this cause.
+    pub parent_code: InternedObligationCauseCode<'tcx>,
+}
+
+#[derive(Clone, Debug, TypeFoldable, TypeVisitable, Lift)]
+pub enum SelectionError<'tcx> {
+    /// The trait is not implemented.
+    Unimplemented,
+    /// After a closure impl has selected, its "outputs" were evaluated
+    /// (which for closures includes the "input" type params) and they
+    /// didn't resolve. See `confirm_poly_trait_refs` for more.
+    OutputTypeParameterMismatch(
+        ty::PolyTraitRef<'tcx>,
+        ty::PolyTraitRef<'tcx>,
+        ty::error::TypeError<'tcx>,
+    ),
+    /// The trait pointed by `DefId` is not object safe.
+    TraitNotObjectSafe(DefId),
+    /// A given constant couldn't be evaluated.
+    NotConstEvaluatable(NotConstEvaluatable),
+    /// Exceeded the recursion depth during type projection.
+    Overflow(OverflowError),
+    /// Signaling that an error has already been emitted, to avoid
+    /// multiple errors being shown.
+    ErrorReporting,
+    /// Multiple applicable `impl`s where found. The `DefId`s correspond to
+    /// all the `impl`s' Items.
+    Ambiguous(Vec<DefId>),
+}
+
+/// 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 `ImplSource`
+/// indicates where the impl comes from.
+///
+/// For example, the obligation may be satisfied by a specific impl (case A),
+/// or it may be relative to some bound that is in scope (case B).
+///
+/// ```ignore (illustrative)
+/// impl<T:Clone> Clone<T> for Option<T> { ... } // Impl_1
+/// impl<T:Clone> Clone<T> for Box<T> { ... }    // Impl_2
+/// impl Clone for i32 { ... }                   // Impl_3
+///
+/// fn foo<T: Clone>(concrete: Option<Box<i32>>, param: T, mixed: Option<T>) {
+///     // Case A: ImplSource points at a specific impl. Only possible when
+///     // type is concretely known. If the impl itself has bounded
+///     // type parameters, ImplSource will carry resolutions for those as well:
+///     concrete.clone(); // ImplSource(Impl_1, [ImplSource(Impl_2, [ImplSource(Impl_3)])])
+///
+///     // Case A: ImplSource points at a specific impl. Only possible when
+///     // type is concretely known. If the impl itself has bounded
+///     // type parameters, ImplSource will carry resolutions for those as well:
+///     concrete.clone(); // ImplSource(Impl_1, [ImplSource(Impl_2, [ImplSource(Impl_3)])])
+///
+///     // Case B: ImplSource must be provided by caller. This applies when
+///     // type is a type parameter.
+///     param.clone();    // ImplSource::Param
+///
+///     // Case C: A mix of cases A and B.
+///     mixed.clone();    // ImplSource(Impl_1, [ImplSource::Param])
+/// }
+/// ```
+///
+/// ### The type parameter `N`
+///
+/// See explanation on `ImplSourceUserDefinedData`.
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub enum ImplSource<'tcx, N> {
+    /// ImplSource identifying a particular impl.
+    UserDefined(ImplSourceUserDefinedData<'tcx, N>),
+
+    /// ImplSource 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.
+    AutoImpl(ImplSourceAutoImplData<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).
+    Param(Vec<N>, ty::BoundConstness),
+
+    /// Virtual calls through an object.
+    Object(ImplSourceObjectData<'tcx, N>),
+
+    /// Successful resolution for a builtin trait.
+    Builtin(ImplSourceBuiltinData<N>),
+
+    /// ImplSource for trait upcasting coercion
+    TraitUpcasting(ImplSourceTraitUpcastingData<'tcx, N>),
+
+    /// ImplSource automatically generated for a closure. The `DefId` is the ID
+    /// of the closure expression. This is an `ImplSource::UserDefined` in spirit, but the
+    /// impl is generated by the compiler and does not appear in the source.
+    Closure(ImplSourceClosureData<'tcx, N>),
+
+    /// Same as above, but for a function pointer type with the given signature.
+    FnPointer(ImplSourceFnPointerData<'tcx, N>),
+
+    /// ImplSource for a builtin `DeterminantKind` trait implementation.
+    DiscriminantKind(ImplSourceDiscriminantKindData),
+
+    /// ImplSource for a builtin `Pointee` trait implementation.
+    Pointee(ImplSourcePointeeData),
+
+    /// ImplSource automatically generated for a generator.
+    Generator(ImplSourceGeneratorData<'tcx, N>),
+
+    /// ImplSource for a trait alias.
+    TraitAlias(ImplSourceTraitAliasData<'tcx, N>),
+
+    /// ImplSource for a `const Drop` implementation.
+    ConstDestruct(ImplSourceConstDestructData<N>),
+}
+
+impl<'tcx, N> ImplSource<'tcx, N> {
+    pub fn nested_obligations(self) -> Vec<N> {
+        match self {
+            ImplSource::UserDefined(i) => i.nested,
+            ImplSource::Param(n, _) => n,
+            ImplSource::Builtin(i) => i.nested,
+            ImplSource::AutoImpl(d) => d.nested,
+            ImplSource::Closure(c) => c.nested,
+            ImplSource::Generator(c) => c.nested,
+            ImplSource::Object(d) => d.nested,
+            ImplSource::FnPointer(d) => d.nested,
+            ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData)
+            | ImplSource::Pointee(ImplSourcePointeeData) => Vec::new(),
+            ImplSource::TraitAlias(d) => d.nested,
+            ImplSource::TraitUpcasting(d) => d.nested,
+            ImplSource::ConstDestruct(i) => i.nested,
+        }
+    }
+
+    pub fn borrow_nested_obligations(&self) -> &[N] {
+        match &self {
+            ImplSource::UserDefined(i) => &i.nested[..],
+            ImplSource::Param(n, _) => &n,
+            ImplSource::Builtin(i) => &i.nested,
+            ImplSource::AutoImpl(d) => &d.nested,
+            ImplSource::Closure(c) => &c.nested,
+            ImplSource::Generator(c) => &c.nested,
+            ImplSource::Object(d) => &d.nested,
+            ImplSource::FnPointer(d) => &d.nested,
+            ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData)
+            | ImplSource::Pointee(ImplSourcePointeeData) => &[],
+            ImplSource::TraitAlias(d) => &d.nested,
+            ImplSource::TraitUpcasting(d) => &d.nested,
+            ImplSource::ConstDestruct(i) => &i.nested,
+        }
+    }
+
+    pub fn map<M, F>(self, f: F) -> ImplSource<'tcx, M>
+    where
+        F: FnMut(N) -> M,
+    {
+        match self {
+            ImplSource::UserDefined(i) => ImplSource::UserDefined(ImplSourceUserDefinedData {
+                impl_def_id: i.impl_def_id,
+                substs: i.substs,
+                nested: i.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::Param(n, ct) => ImplSource::Param(n.into_iter().map(f).collect(), ct),
+            ImplSource::Builtin(i) => ImplSource::Builtin(ImplSourceBuiltinData {
+                nested: i.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::Object(o) => ImplSource::Object(ImplSourceObjectData {
+                upcast_trait_ref: o.upcast_trait_ref,
+                vtable_base: o.vtable_base,
+                nested: o.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::AutoImpl(d) => ImplSource::AutoImpl(ImplSourceAutoImplData {
+                trait_def_id: d.trait_def_id,
+                nested: d.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::Closure(c) => ImplSource::Closure(ImplSourceClosureData {
+                closure_def_id: c.closure_def_id,
+                substs: c.substs,
+                nested: c.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::Generator(c) => ImplSource::Generator(ImplSourceGeneratorData {
+                generator_def_id: c.generator_def_id,
+                substs: c.substs,
+                nested: c.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::FnPointer(p) => ImplSource::FnPointer(ImplSourceFnPointerData {
+                fn_ty: p.fn_ty,
+                nested: p.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData) => {
+                ImplSource::DiscriminantKind(ImplSourceDiscriminantKindData)
+            }
+            ImplSource::Pointee(ImplSourcePointeeData) => {
+                ImplSource::Pointee(ImplSourcePointeeData)
+            }
+            ImplSource::TraitAlias(d) => ImplSource::TraitAlias(ImplSourceTraitAliasData {
+                alias_def_id: d.alias_def_id,
+                substs: d.substs,
+                nested: d.nested.into_iter().map(f).collect(),
+            }),
+            ImplSource::TraitUpcasting(d) => {
+                ImplSource::TraitUpcasting(ImplSourceTraitUpcastingData {
+                    upcast_trait_ref: d.upcast_trait_ref,
+                    vtable_vptr_slot: d.vtable_vptr_slot,
+                    nested: d.nested.into_iter().map(f).collect(),
+                })
+            }
+            ImplSource::ConstDestruct(i) => {
+                ImplSource::ConstDestruct(ImplSourceConstDestructData {
+                    nested: i.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, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceUserDefinedData<'tcx, N> {
+    pub impl_def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceGeneratorData<'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, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceClosureData<'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, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceAutoImplData<N> {
+    pub trait_def_id: DefId,
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceTraitUpcastingData<'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, pointers to supertrait vtable will
+    /// be provided when necessary; this is the position of `upcast_trait_ref`'s vtable
+    /// within that vtable.
+    pub vtable_vptr_slot: Option<usize>,
+
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceBuiltinData<N> {
+    pub nested: Vec<N>,
+}
+
+#[derive(PartialEq, Eq, Clone, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceObjectData<'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, pointers to supertrait vtable will
+    /// be provided when necessary; 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, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceFnPointerData<'tcx, N> {
+    pub fn_ty: Ty<'tcx>,
+    pub nested: Vec<N>,
+}
+
+// FIXME(@lcnr): This should be  refactored and merged with other builtin vtables.
+#[derive(Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
+pub struct ImplSourceDiscriminantKindData;
+
+#[derive(Clone, Debug, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
+pub struct ImplSourcePointeeData;
+
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceConstDestructData<N> {
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(TypeFoldable, TypeVisitable)]
+pub struct ImplSourceTraitAliasData<'tcx, N> {
+    pub alias_def_id: DefId,
+    pub substs: SubstsRef<'tcx>,
+    pub nested: Vec<N>,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)]
+pub enum ObjectSafetyViolation {
+    /// `Self: Sized` declared on the trait.
+    SizedSelf(SmallVec<[Span; 1]>),
+
+    /// Supertrait reference references `Self` an in illegal location
+    /// (e.g., `trait Foo : Bar<Self>`).
+    SupertraitSelf(SmallVec<[Span; 1]>),
+
+    /// Method has something illegal.
+    Method(Symbol, MethodViolationCode, Span),
+
+    /// Associated const.
+    AssocConst(Symbol, Span),
+
+    /// GAT
+    GAT(Symbol, Span),
+}
+
+impl ObjectSafetyViolation {
+    pub fn error_msg(&self) -> Cow<'static, str> {
+        match self {
+            ObjectSafetyViolation::SizedSelf(_) => "it requires `Self: Sized`".into(),
+            ObjectSafetyViolation::SupertraitSelf(ref spans) => {
+                if spans.iter().any(|sp| *sp != DUMMY_SP) {
+                    "it uses `Self` as a type parameter".into()
+                } else {
+                    "it cannot use `Self` as a type parameter in a supertrait or `where`-clause"
+                        .into()
+                }
+            }
+            ObjectSafetyViolation::Method(name, MethodViolationCode::StaticMethod(_), _) => {
+                format!("associated function `{}` has no `self` parameter", name).into()
+            }
+            ObjectSafetyViolation::Method(
+                name,
+                MethodViolationCode::ReferencesSelfInput(_),
+                DUMMY_SP,
+            ) => format!("method `{}` references the `Self` type in its parameters", name).into(),
+            ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelfInput(_), _) => {
+                format!("method `{}` references the `Self` type in this parameter", name).into()
+            }
+            ObjectSafetyViolation::Method(name, MethodViolationCode::ReferencesSelfOutput, _) => {
+                format!("method `{}` references the `Self` type in its return type", name).into()
+            }
+            ObjectSafetyViolation::Method(
+                name,
+                MethodViolationCode::WhereClauseReferencesSelf,
+                _,
+            ) => {
+                format!("method `{}` references the `Self` type in its `where` clause", name).into()
+            }
+            ObjectSafetyViolation::Method(name, MethodViolationCode::Generic, _) => {
+                format!("method `{}` has generic type parameters", name).into()
+            }
+            ObjectSafetyViolation::Method(
+                name,
+                MethodViolationCode::UndispatchableReceiver(_),
+                _,
+            ) => format!("method `{}`'s `self` parameter cannot be dispatched on", name).into(),
+            ObjectSafetyViolation::AssocConst(name, DUMMY_SP) => {
+                format!("it contains associated `const` `{}`", name).into()
+            }
+            ObjectSafetyViolation::AssocConst(..) => "it contains this associated `const`".into(),
+            ObjectSafetyViolation::GAT(name, _) => {
+                format!("it contains the generic associated type `{}`", name).into()
+            }
+        }
+    }
+
+    pub fn solution(&self, err: &mut Diagnostic) {
+        match self {
+            ObjectSafetyViolation::SizedSelf(_) | ObjectSafetyViolation::SupertraitSelf(_) => {}
+            ObjectSafetyViolation::Method(
+                name,
+                MethodViolationCode::StaticMethod(Some((add_self_sugg, make_sized_sugg))),
+                _,
+            ) => {
+                err.span_suggestion(
+                    add_self_sugg.1,
+                    format!(
+                        "consider turning `{}` into a method by giving it a `&self` argument",
+                        name
+                    ),
+                    add_self_sugg.0.to_string(),
+                    Applicability::MaybeIncorrect,
+                );
+                err.span_suggestion(
+                    make_sized_sugg.1,
+                    format!(
+                        "alternatively, consider constraining `{}` so it does not apply to \
+                             trait objects",
+                        name
+                    ),
+                    make_sized_sugg.0.to_string(),
+                    Applicability::MaybeIncorrect,
+                );
+            }
+            ObjectSafetyViolation::Method(
+                name,
+                MethodViolationCode::UndispatchableReceiver(Some(span)),
+                _,
+            ) => {
+                err.span_suggestion(
+                    *span,
+                    &format!(
+                        "consider changing method `{}`'s `self` parameter to be `&self`",
+                        name
+                    ),
+                    "&Self",
+                    Applicability::MachineApplicable,
+                );
+            }
+            ObjectSafetyViolation::AssocConst(name, _)
+            | ObjectSafetyViolation::GAT(name, _)
+            | ObjectSafetyViolation::Method(name, ..) => {
+                err.help(&format!("consider moving `{}` to another trait", name));
+            }
+        }
+    }
+
+    pub fn spans(&self) -> SmallVec<[Span; 1]> {
+        // When `span` comes from a separate crate, it'll be `DUMMY_SP`. Treat it as `None` so
+        // diagnostics use a `note` instead of a `span_label`.
+        match self {
+            ObjectSafetyViolation::SupertraitSelf(spans)
+            | ObjectSafetyViolation::SizedSelf(spans) => spans.clone(),
+            ObjectSafetyViolation::AssocConst(_, span)
+            | ObjectSafetyViolation::GAT(_, span)
+            | ObjectSafetyViolation::Method(_, _, span)
+                if *span != DUMMY_SP =>
+            {
+                smallvec![*span]
+            }
+            _ => smallvec![],
+        }
+    }
+}
+
+/// Reasons a method might not be object-safe.
+#[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)]
+pub enum MethodViolationCode {
+    /// e.g., `fn foo()`
+    StaticMethod(Option<(/* add &self */ (String, Span), /* add Self: Sized */ (String, Span))>),
+
+    /// e.g., `fn foo(&self, x: Self)`
+    ReferencesSelfInput(Option<Span>),
+
+    /// e.g., `fn foo(&self) -> Self`
+    ReferencesSelfOutput,
+
+    /// e.g., `fn foo(&self) where Self: Clone`
+    WhereClauseReferencesSelf,
+
+    /// e.g., `fn foo<A>()`
+    Generic,
+
+    /// the method's receiver (`self` argument) can't be dispatched on
+    UndispatchableReceiver(Option<Span>),
+}
+
+/// These are the error cases for `codegen_fulfill_obligation`.
+#[derive(Copy, Clone, Debug, Hash, HashStable, Encodable, Decodable)]
+pub enum CodegenObligationError {
+    /// Ambiguity can happen when monomorphizing during trans
+    /// expands to some humongous type that never occurred
+    /// statically -- this humongous type can then overflow,
+    /// leading to an ambiguous result. So report this as an
+    /// overflow bug, since I believe this is the only case
+    /// where ambiguity can result.
+    Ambiguity,
+    /// This can trigger when we probe for the source of a `'static` lifetime requirement
+    /// on a trait object: `impl Foo for dyn Trait {}` has an implicit `'static` bound.
+    /// This can also trigger when we have a global bound that is not actually satisfied,
+    /// but was included during typeck due to the trivial_bounds feature.
+    Unimplemented,
+    FulfillmentError,
+}
diff --git a/compiler/rustc_middle/src/traits/query.rs b/compiler/rustc_middle/src/traits/query.rs
new file mode 100644
index 000000000..1f9b474ad
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/query.rs
@@ -0,0 +1,230 @@
+//! Experimental types for the trait query interface. The methods
+//! defined in this module are all based on **canonicalization**,
+//! which makes a canonical query by replacing unbound inference
+//! variables and regions, so that results can be reused more broadly.
+//! The providers for the queries defined here can be found in
+//! `rustc_traits`.
+
+use crate::infer::canonical::{Canonical, QueryResponse};
+use crate::ty::error::TypeError;
+use crate::ty::subst::GenericArg;
+use crate::ty::{self, Ty, TyCtxt};
+use rustc_errors::struct_span_err;
+use rustc_span::source_map::Span;
+use std::iter::FromIterator;
+
+pub mod type_op {
+    use crate::ty::fold::TypeFoldable;
+    use crate::ty::subst::UserSubsts;
+    use crate::ty::{Predicate, Ty};
+    use rustc_hir::def_id::DefId;
+    use std::fmt;
+
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
+    #[derive(TypeFoldable, TypeVisitable)]
+    pub struct AscribeUserType<'tcx> {
+        pub mir_ty: Ty<'tcx>,
+        pub def_id: DefId,
+        pub user_substs: UserSubsts<'tcx>,
+    }
+
+    impl<'tcx> AscribeUserType<'tcx> {
+        pub fn new(mir_ty: Ty<'tcx>, def_id: DefId, user_substs: UserSubsts<'tcx>) -> Self {
+            Self { mir_ty, def_id, user_substs }
+        }
+    }
+
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
+    #[derive(TypeFoldable, TypeVisitable)]
+    pub struct Eq<'tcx> {
+        pub a: Ty<'tcx>,
+        pub b: Ty<'tcx>,
+    }
+
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
+    #[derive(TypeFoldable, TypeVisitable)]
+    pub struct Subtype<'tcx> {
+        pub sub: Ty<'tcx>,
+        pub sup: Ty<'tcx>,
+    }
+
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
+    #[derive(TypeFoldable, TypeVisitable)]
+    pub struct ProvePredicate<'tcx> {
+        pub predicate: Predicate<'tcx>,
+    }
+
+    impl<'tcx> ProvePredicate<'tcx> {
+        pub fn new(predicate: Predicate<'tcx>) -> Self {
+            ProvePredicate { predicate }
+        }
+    }
+
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
+    #[derive(TypeFoldable, TypeVisitable)]
+    pub struct Normalize<T> {
+        pub value: T,
+    }
+
+    impl<'tcx, T> Normalize<T>
+    where
+        T: fmt::Debug + TypeFoldable<'tcx>,
+    {
+        pub fn new(value: T) -> Self {
+            Self { value }
+        }
+    }
+}
+
+pub type CanonicalProjectionGoal<'tcx> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>>>;
+
+pub type CanonicalTyGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Ty<'tcx>>>;
+
+pub type CanonicalPredicateGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>>;
+
+pub type CanonicalTypeOpAscribeUserTypeGoal<'tcx> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::AscribeUserType<'tcx>>>;
+
+pub type CanonicalTypeOpEqGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Eq<'tcx>>>;
+
+pub type CanonicalTypeOpSubtypeGoal<'tcx> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Subtype<'tcx>>>;
+
+pub type CanonicalTypeOpProvePredicateGoal<'tcx> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::ProvePredicate<'tcx>>>;
+
+pub type CanonicalTypeOpNormalizeGoal<'tcx, T> =
+    Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::Normalize<T>>>;
+
+#[derive(Copy, Clone, Debug, HashStable)]
+pub struct NoSolution;
+
+pub type Fallible<T> = Result<T, NoSolution>;
+
+impl<'tcx> From<TypeError<'tcx>> for NoSolution {
+    fn from(_: TypeError<'tcx>) -> NoSolution {
+        NoSolution
+    }
+}
+
+#[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable, Lift)]
+pub struct DropckOutlivesResult<'tcx> {
+    pub kinds: Vec<GenericArg<'tcx>>,
+    pub overflows: Vec<Ty<'tcx>>,
+}
+
+impl<'tcx> DropckOutlivesResult<'tcx> {
+    pub fn report_overflows(&self, tcx: TyCtxt<'tcx>, span: Span, ty: Ty<'tcx>) {
+        if let Some(overflow_ty) = self.overflows.get(0) {
+            let mut err = struct_span_err!(
+                tcx.sess,
+                span,
+                E0320,
+                "overflow while adding drop-check rules for {}",
+                ty,
+            );
+            err.note(&format!("overflowed on {}", overflow_ty));
+            err.emit();
+        }
+    }
+
+    pub fn into_kinds_reporting_overflows(
+        self,
+        tcx: TyCtxt<'tcx>,
+        span: Span,
+        ty: Ty<'tcx>,
+    ) -> Vec<GenericArg<'tcx>> {
+        self.report_overflows(tcx, span, ty);
+        let DropckOutlivesResult { kinds, overflows: _ } = self;
+        kinds
+    }
+}
+
+/// A set of constraints that need to be satisfied in order for
+/// a type to be valid for destruction.
+#[derive(Clone, Debug, HashStable)]
+pub struct DropckConstraint<'tcx> {
+    /// Types that are required to be alive in order for this
+    /// type to be valid for destruction.
+    pub outlives: Vec<ty::subst::GenericArg<'tcx>>,
+
+    /// Types that could not be resolved: projections and params.
+    pub dtorck_types: Vec<Ty<'tcx>>,
+
+    /// If, during the computation of the dtorck constraint, we
+    /// overflow, that gets recorded here. The caller is expected to
+    /// report an error.
+    pub overflows: Vec<Ty<'tcx>>,
+}
+
+impl<'tcx> DropckConstraint<'tcx> {
+    pub fn empty() -> DropckConstraint<'tcx> {
+        DropckConstraint { outlives: vec![], dtorck_types: vec![], overflows: vec![] }
+    }
+}
+
+impl<'tcx> FromIterator<DropckConstraint<'tcx>> for DropckConstraint<'tcx> {
+    fn from_iter<I: IntoIterator<Item = DropckConstraint<'tcx>>>(iter: I) -> Self {
+        let mut result = Self::empty();
+
+        for DropckConstraint { outlives, dtorck_types, overflows } in iter {
+            result.outlives.extend(outlives);
+            result.dtorck_types.extend(dtorck_types);
+            result.overflows.extend(overflows);
+        }
+
+        result
+    }
+}
+
+#[derive(Debug, HashStable)]
+pub struct CandidateStep<'tcx> {
+    pub self_ty: Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>,
+    pub autoderefs: usize,
+    /// `true` if the type results from a dereference of a raw pointer.
+    /// when assembling candidates, we include these steps, but not when
+    /// picking methods. This so that if we have `foo: *const Foo` and `Foo` has methods
+    /// `fn by_raw_ptr(self: *const Self)` and `fn by_ref(&self)`, then
+    /// `foo.by_raw_ptr()` will work and `foo.by_ref()` won't.
+    pub from_unsafe_deref: bool,
+    pub unsize: bool,
+}
+
+#[derive(Copy, Clone, Debug, HashStable)]
+pub struct MethodAutoderefStepsResult<'tcx> {
+    /// The valid autoderef steps that could be find.
+    pub steps: &'tcx [CandidateStep<'tcx>],
+    /// If Some(T), a type autoderef reported an error on.
+    pub opt_bad_ty: Option<&'tcx MethodAutoderefBadTy<'tcx>>,
+    /// If `true`, `steps` has been truncated due to reaching the
+    /// recursion limit.
+    pub reached_recursion_limit: bool,
+}
+
+#[derive(Debug, HashStable)]
+pub struct MethodAutoderefBadTy<'tcx> {
+    pub reached_raw_pointer: bool,
+    pub ty: Canonical<'tcx, QueryResponse<'tcx, Ty<'tcx>>>,
+}
+
+/// Result from the `normalize_projection_ty` query.
+#[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)]
+pub struct NormalizationResult<'tcx> {
+    /// Result of normalization.
+    pub normalized_ty: Ty<'tcx>,
+}
+
+/// Outlives bounds are relationships between generic parameters,
+/// whether they both be regions (`'a: 'b`) or whether types are
+/// involved (`T: 'a`). These relationships can be extracted from the
+/// full set of predicates we understand or also from types (in which
+/// case they are called implied bounds). They are fed to the
+/// `OutlivesEnv` which in turn is supplied to the region checker and
+/// other parts of the inference system.
+#[derive(Clone, Debug, TypeFoldable, TypeVisitable, Lift, HashStable)]
+pub enum OutlivesBound<'tcx> {
+    RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
+    RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
+    RegionSubProjection(ty::Region<'tcx>, ty::ProjectionTy<'tcx>),
+}
diff --git a/compiler/rustc_middle/src/traits/select.rs b/compiler/rustc_middle/src/traits/select.rs
new file mode 100644
index 000000000..e836ba47e
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/select.rs
@@ -0,0 +1,312 @@
+//! Candidate selection. See the [rustc dev guide] for more information on how this works.
+//!
+//! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection
+
+use self::EvaluationResult::*;
+
+use super::{SelectionError, SelectionResult};
+use rustc_errors::ErrorGuaranteed;
+
+use crate::ty;
+
+use rustc_hir::def_id::DefId;
+use rustc_query_system::cache::Cache;
+
+pub type SelectionCache<'tcx> = Cache<
+    // This cache does not use `ParamEnvAnd` in its keys because `ParamEnv::and` can replace
+    // caller bounds with an empty list if the `TraitPredicate` looks global, which may happen
+    // after erasing lifetimes from the predicate.
+    (ty::ParamEnv<'tcx>, ty::TraitPredicate<'tcx>),
+    SelectionResult<'tcx, SelectionCandidate<'tcx>>,
+>;
+
+pub type EvaluationCache<'tcx> = Cache<
+    // See above: this cache does not use `ParamEnvAnd` in its keys due to sometimes incorrectly
+    // caching with the wrong `ParamEnv`.
+    (ty::ParamEnv<'tcx>, ty::PolyTraitPredicate<'tcx>),
+    EvaluationResult,
+>;
+
+/// The selection process begins by considering all impls, where
+/// clauses, and so forth that might resolve an obligation. Sometimes
+/// we'll be able to say definitively that (e.g.) an impl does not
+/// apply to the obligation: perhaps it is defined for `usize` but the
+/// obligation is for `i32`. In that case, we drop the impl out of the
+/// list. But the other cases are considered *candidates*.
+///
+/// For selection to succeed, there must be exactly one matching
+/// candidate. If the obligation is fully known, this is guaranteed
+/// by coherence. However, if the obligation contains type parameters
+/// or variables, there may be multiple such impls.
+///
+/// It is not a real problem if multiple matching impls exist because
+/// of type variables - it just means the obligation isn't sufficiently
+/// elaborated. In that case we report an ambiguity, and the caller can
+/// try again after more type information has been gathered or report a
+/// "type annotations needed" error.
+///
+/// However, with type parameters, this can be a real problem - type
+/// parameters don't unify with regular types, but they *can* unify
+/// with variables from blanket impls, and (unless we know its bounds
+/// will always be satisfied) picking the blanket impl will be wrong
+/// for at least *some* substitutions. To make this concrete, if we have
+///
+/// ```rust, ignore
+/// trait AsDebug { type Out: fmt::Debug; fn debug(self) -> Self::Out; }
+/// impl<T: fmt::Debug> AsDebug for T {
+///     type Out = T;
+///     fn debug(self) -> fmt::Debug { self }
+/// }
+/// fn foo<T: AsDebug>(t: T) { println!("{:?}", <T as AsDebug>::debug(t)); }
+/// ```
+///
+/// we can't just use the impl to resolve the `<T as AsDebug>` obligation
+/// -- a type from another crate (that doesn't implement `fmt::Debug`) could
+/// implement `AsDebug`.
+///
+/// Because where-clauses match the type exactly, multiple clauses can
+/// only match if there are unresolved variables, and we can mostly just
+/// report this ambiguity in that case. This is still a problem - we can't
+/// *do anything* with ambiguities that involve only regions. This is issue
+/// #21974.
+///
+/// If a single where-clause matches and there are no inference
+/// variables left, then it definitely matches and we can just select
+/// it.
+///
+/// In fact, we even select the where-clause when the obligation contains
+/// inference variables. The can lead to inference making "leaps of logic",
+/// for example in this situation:
+///
+/// ```rust, ignore
+/// pub trait Foo<T> { fn foo(&self) -> T; }
+/// impl<T> Foo<()> for T { fn foo(&self) { } }
+/// impl Foo<bool> for bool { fn foo(&self) -> bool { *self } }
+///
+/// pub fn foo<T>(t: T) where T: Foo<bool> {
+///     println!("{:?}", <T as Foo<_>>::foo(&t));
+/// }
+/// fn main() { foo(false); }
+/// ```
+///
+/// Here the obligation `<T as Foo<$0>>` can be matched by both the blanket
+/// impl and the where-clause. We select the where-clause and unify `$0=bool`,
+/// so the program prints "false". However, if the where-clause is omitted,
+/// the blanket impl is selected, we unify `$0=()`, and the program prints
+/// "()".
+///
+/// Exactly the same issues apply to projection and object candidates, except
+/// that we can have both a projection candidate and a where-clause candidate
+/// for the same obligation. In that case either would do (except that
+/// different "leaps of logic" would occur if inference variables are
+/// present), and we just pick the where-clause. This is, for example,
+/// required for associated types to work in default impls, as the bounds
+/// are visible both as projection bounds and as where-clauses from the
+/// parameter environment.
+#[derive(PartialEq, Eq, Debug, Clone, TypeFoldable, TypeVisitable)]
+pub enum SelectionCandidate<'tcx> {
+    BuiltinCandidate {
+        /// `false` if there are no *further* obligations.
+        has_nested: bool,
+    },
+
+    /// Implementation of transmutability trait.
+    TransmutabilityCandidate,
+
+    ParamCandidate(ty::PolyTraitPredicate<'tcx>),
+    ImplCandidate(DefId),
+    AutoImplCandidate(DefId),
+
+    /// This is a trait matching with a projected type as `Self`, and we found
+    /// an applicable bound in the trait definition. The `usize` is an index
+    /// into the list returned by `tcx.item_bounds`.
+    ProjectionCandidate(usize),
+
+    /// Implementation of a `Fn`-family trait by one of the anonymous types
+    /// generated for an `||` expression.
+    ClosureCandidate,
+
+    /// Implementation of a `Generator` trait by one of the anonymous types
+    /// generated for a generator.
+    GeneratorCandidate,
+
+    /// Implementation of a `Fn`-family trait by one of the anonymous
+    /// types generated for a fn pointer type (e.g., `fn(int) -> int`)
+    FnPointerCandidate {
+        is_const: bool,
+    },
+
+    /// Builtin implementation of `DiscriminantKind`.
+    DiscriminantKindCandidate,
+
+    /// Builtin implementation of `Pointee`.
+    PointeeCandidate,
+
+    TraitAliasCandidate(DefId),
+
+    /// Matching `dyn Trait` with a supertrait of `Trait`. The index is the
+    /// position in the iterator returned by
+    /// `rustc_infer::traits::util::supertraits`.
+    ObjectCandidate(usize),
+
+    /// Perform trait upcasting coercion of `dyn Trait` to a supertrait of `Trait`.
+    /// The index is the position in the iterator returned by
+    /// `rustc_infer::traits::util::supertraits`.
+    TraitUpcastingUnsizeCandidate(usize),
+
+    BuiltinObjectCandidate,
+
+    BuiltinUnsizeCandidate,
+
+    /// Implementation of `const Destruct`, optionally from a custom `impl const Drop`.
+    ConstDestructCandidate(Option<DefId>),
+}
+
+/// The result of trait evaluation. The order is important
+/// here as the evaluation of a list is the maximum of the
+/// evaluations.
+///
+/// The evaluation results are ordered:
+///     - `EvaluatedToOk` implies `EvaluatedToOkModuloRegions`
+///       implies `EvaluatedToAmbig` implies `EvaluatedToUnknown`
+///     - `EvaluatedToErr` implies `EvaluatedToRecur`
+///     - the "union" of evaluation results is equal to their maximum -
+///     all the "potential success" candidates can potentially succeed,
+///     so they are noops when unioned with a definite error, and within
+///     the categories it's easy to see that the unions are correct.
+#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq, HashStable)]
+pub enum EvaluationResult {
+    /// Evaluation successful.
+    EvaluatedToOk,
+    /// Evaluation successful, but there were unevaluated region obligations.
+    EvaluatedToOkModuloRegions,
+    /// Evaluation successful, but need to rerun because opaque types got
+    /// hidden types assigned without it being known whether the opaque types
+    /// are within their defining scope
+    EvaluatedToOkModuloOpaqueTypes,
+    /// Evaluation is known to be ambiguous -- it *might* hold for some
+    /// assignment of inference variables, but it might not.
+    ///
+    /// While this has the same meaning as `EvaluatedToUnknown` -- we can't
+    /// know whether this obligation holds or not -- it is the result we
+    /// would get with an empty stack, and therefore is cacheable.
+    EvaluatedToAmbig,
+    /// Evaluation failed because of recursion involving inference
+    /// variables. We are somewhat imprecise there, so we don't actually
+    /// know the real result.
+    ///
+    /// This can't be trivially cached for the same reason as `EvaluatedToRecur`.
+    EvaluatedToUnknown,
+    /// Evaluation failed because we encountered an obligation we are already
+    /// trying to prove on this branch.
+    ///
+    /// We know this branch can't be a part of a minimal proof-tree for
+    /// the "root" of our cycle, because then we could cut out the recursion
+    /// and maintain a valid proof tree. However, this does not mean
+    /// that all the obligations on this branch do not hold -- it's possible
+    /// that we entered this branch "speculatively", and that there
+    /// might be some other way to prove this obligation that does not
+    /// go through this cycle -- so we can't cache this as a failure.
+    ///
+    /// For example, suppose we have this:
+    ///
+    /// ```rust,ignore (pseudo-Rust)
+    /// pub trait Trait { fn xyz(); }
+    /// // This impl is "useless", but we can still have
+    /// // an `impl Trait for SomeUnsizedType` somewhere.
+    /// impl<T: Trait + Sized> Trait for T { fn xyz() {} }
+    ///
+    /// pub fn foo<T: Trait + ?Sized>() {
+    ///     <T as Trait>::xyz();
+    /// }
+    /// ```
+    ///
+    /// When checking `foo`, we have to prove `T: Trait`. This basically
+    /// translates into this:
+    ///
+    /// ```plain,ignore
+    /// (T: Trait + Sized →_\impl T: Trait), T: Trait ⊢ T: Trait
+    /// ```
+    ///
+    /// When we try to prove it, we first go the first option, which
+    /// recurses. This shows us that the impl is "useless" -- it won't
+    /// tell us that `T: Trait` unless it already implemented `Trait`
+    /// by some other means. However, that does not prevent `T: Trait`
+    /// does not hold, because of the bound (which can indeed be satisfied
+    /// by `SomeUnsizedType` from another crate).
+    //
+    // FIXME: when an `EvaluatedToRecur` goes past its parent root, we
+    // ought to convert it to an `EvaluatedToErr`, because we know
+    // there definitely isn't a proof tree for that obligation. Not
+    // doing so is still sound -- there isn't any proof tree, so the
+    // branch still can't be a part of a minimal one -- but does not re-enable caching.
+    EvaluatedToRecur,
+    /// Evaluation failed.
+    EvaluatedToErr,
+}
+
+impl EvaluationResult {
+    /// Returns `true` if this evaluation result is known to apply, even
+    /// considering outlives constraints.
+    pub fn must_apply_considering_regions(self) -> bool {
+        self == EvaluatedToOk
+    }
+
+    /// Returns `true` if this evaluation result is known to apply, ignoring
+    /// outlives constraints.
+    pub fn must_apply_modulo_regions(self) -> bool {
+        self <= EvaluatedToOkModuloRegions
+    }
+
+    pub fn may_apply(self) -> bool {
+        match self {
+            EvaluatedToOkModuloOpaqueTypes
+            | EvaluatedToOk
+            | EvaluatedToOkModuloRegions
+            | EvaluatedToAmbig
+            | EvaluatedToUnknown => true,
+
+            EvaluatedToErr | EvaluatedToRecur => false,
+        }
+    }
+
+    pub fn is_stack_dependent(self) -> bool {
+        match self {
+            EvaluatedToUnknown | EvaluatedToRecur => true,
+
+            EvaluatedToOkModuloOpaqueTypes
+            | EvaluatedToOk
+            | EvaluatedToOkModuloRegions
+            | EvaluatedToAmbig
+            | EvaluatedToErr => false,
+        }
+    }
+}
+
+/// Indicates that trait evaluation caused overflow and in which pass.
+#[derive(Copy, Clone, Debug, PartialEq, Eq, HashStable)]
+pub enum OverflowError {
+    Error(ErrorGuaranteed),
+    Canonical,
+    ErrorReporting,
+}
+
+impl From<ErrorGuaranteed> for OverflowError {
+    fn from(e: ErrorGuaranteed) -> OverflowError {
+        OverflowError::Error(e)
+    }
+}
+
+TrivialTypeTraversalAndLiftImpls! {
+    OverflowError,
+}
+
+impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
+    fn from(overflow_error: OverflowError) -> SelectionError<'tcx> {
+        match overflow_error {
+            OverflowError::Error(e) => SelectionError::Overflow(OverflowError::Error(e)),
+            OverflowError::Canonical => SelectionError::Overflow(OverflowError::Canonical),
+            OverflowError::ErrorReporting => SelectionError::ErrorReporting,
+        }
+    }
+}
diff --git a/compiler/rustc_middle/src/traits/specialization_graph.rs b/compiler/rustc_middle/src/traits/specialization_graph.rs
new file mode 100644
index 000000000..2465f8e25
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/specialization_graph.rs
@@ -0,0 +1,261 @@
+use crate::ty::fast_reject::SimplifiedType;
+use crate::ty::visit::TypeVisitable;
+use crate::ty::{self, TyCtxt};
+use rustc_data_structures::fx::FxIndexMap;
+use rustc_errors::ErrorGuaranteed;
+use rustc_hir::def_id::{DefId, DefIdMap};
+use rustc_span::symbol::sym;
+
+/// A per-trait graph of impls in specialization order. At the moment, this
+/// graph forms a tree rooted with the trait itself, with all other nodes
+/// representing impls, and parent-child relationships representing
+/// specializations.
+///
+/// The graph provides two key services:
+///
+/// - Construction. This implicitly checks for overlapping impls (i.e., impls
+///   that overlap but where neither specializes the other -- an artifact of the
+///   simple "chain" rule.
+///
+/// - Parent extraction. In particular, the graph can give you the *immediate*
+///   parents of a given specializing impl, which is needed for extracting
+///   default items amongst other things. In the simple "chain" rule, every impl
+///   has at most one parent.
+#[derive(TyEncodable, TyDecodable, HashStable, Debug)]
+pub struct Graph {
+    /// All impls have a parent; the "root" impls have as their parent the `def_id`
+    /// of the trait.
+    pub parent: DefIdMap<DefId>,
+
+    /// The "root" impls are found by looking up the trait's def_id.
+    pub children: DefIdMap<Children>,
+
+    /// Whether an error was emitted while constructing the graph.
+    pub has_errored: Option<ErrorGuaranteed>,
+}
+
+impl Graph {
+    pub fn new() -> Graph {
+        Graph { parent: Default::default(), children: Default::default(), has_errored: None }
+    }
+
+    /// The parent of a given impl, which is the `DefId` of the trait when the
+    /// impl is a "specialization root".
+    pub fn parent(&self, child: DefId) -> DefId {
+        *self.parent.get(&child).unwrap_or_else(|| panic!("Failed to get parent for {:?}", child))
+    }
+}
+
+/// What kind of overlap check are we doing -- this exists just for testing and feature-gating
+/// purposes.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, HashStable, Debug, TyEncodable, TyDecodable)]
+pub enum OverlapMode {
+    /// The 1.0 rules (either types fail to unify, or where clauses are not implemented for crate-local types)
+    Stable,
+    /// Feature-gated test: Stable, *or* there is an explicit negative impl that rules out one of the where-clauses.
+    WithNegative,
+    /// Just check for negative impls, not for "where clause not implemented": used for testing.
+    Strict,
+}
+
+impl OverlapMode {
+    pub fn get<'tcx>(tcx: TyCtxt<'tcx>, trait_id: DefId) -> OverlapMode {
+        let with_negative_coherence = tcx.features().with_negative_coherence;
+        let strict_coherence = tcx.has_attr(trait_id, sym::rustc_strict_coherence);
+
+        if with_negative_coherence {
+            if strict_coherence { OverlapMode::Strict } else { OverlapMode::WithNegative }
+        } else if strict_coherence {
+            bug!("To use strict_coherence you need to set with_negative_coherence feature flag");
+        } else {
+            OverlapMode::Stable
+        }
+    }
+
+    pub fn use_negative_impl(&self) -> bool {
+        *self == OverlapMode::Strict || *self == OverlapMode::WithNegative
+    }
+
+    pub fn use_implicit_negative(&self) -> bool {
+        *self == OverlapMode::Stable || *self == OverlapMode::WithNegative
+    }
+}
+
+/// Children of a given impl, grouped into blanket/non-blanket varieties as is
+/// done in `TraitDef`.
+#[derive(Default, TyEncodable, TyDecodable, Debug, HashStable)]
+pub struct Children {
+    // Impls of a trait (or specializations of a given impl). To allow for
+    // quicker lookup, the impls are indexed by a simplified version of their
+    // `Self` type: impls with a simplifiable `Self` are stored in
+    // `non_blanket_impls` keyed by it, while all other impls are stored in
+    // `blanket_impls`.
+    //
+    // A similar division is used within `TraitDef`, but the lists there collect
+    // together *all* the impls for a trait, and are populated prior to building
+    // the specialization graph.
+    /// Impls of the trait.
+    pub non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>,
+
+    /// Blanket impls associated with the trait.
+    pub blanket_impls: Vec<DefId>,
+}
+
+/// A node in the specialization graph is either an impl or a trait
+/// definition; either can serve as a source of item definitions.
+/// There is always exactly one trait definition node: the root.
+#[derive(Debug, Copy, Clone)]
+pub enum Node {
+    Impl(DefId),
+    Trait(DefId),
+}
+
+impl Node {
+    pub fn is_from_trait(&self) -> bool {
+        matches!(self, Node::Trait(..))
+    }
+
+    /// Trys to find the associated item that implements `trait_item_def_id`
+    /// defined in this node.
+    ///
+    /// If this returns `None`, the item can potentially still be found in
+    /// parents of this node.
+    pub fn item<'tcx>(
+        &self,
+        tcx: TyCtxt<'tcx>,
+        trait_item_def_id: DefId,
+    ) -> Option<&'tcx ty::AssocItem> {
+        match *self {
+            Node::Trait(_) => Some(tcx.associated_item(trait_item_def_id)),
+            Node::Impl(impl_def_id) => {
+                let id = tcx.impl_item_implementor_ids(impl_def_id).get(&trait_item_def_id)?;
+                Some(tcx.associated_item(*id))
+            }
+        }
+    }
+
+    pub fn def_id(&self) -> DefId {
+        match *self {
+            Node::Impl(did) => did,
+            Node::Trait(did) => did,
+        }
+    }
+}
+
+#[derive(Copy, Clone)]
+pub struct Ancestors<'tcx> {
+    trait_def_id: DefId,
+    specialization_graph: &'tcx Graph,
+    current_source: Option<Node>,
+}
+
+impl Iterator for Ancestors<'_> {
+    type Item = Node;
+    fn next(&mut self) -> Option<Node> {
+        let cur = self.current_source.take();
+        if let Some(Node::Impl(cur_impl)) = cur {
+            let parent = self.specialization_graph.parent(cur_impl);
+
+            self.current_source = if parent == self.trait_def_id {
+                Some(Node::Trait(parent))
+            } else {
+                Some(Node::Impl(parent))
+            };
+        }
+        cur
+    }
+}
+
+/// Information about the most specialized definition of an associated item.
+pub struct LeafDef {
+    /// The associated item described by this `LeafDef`.
+    pub item: ty::AssocItem,
+
+    /// The node in the specialization graph containing the definition of `item`.
+    pub defining_node: Node,
+
+    /// The "top-most" (ie. least specialized) specialization graph node that finalized the
+    /// definition of `item`.
+    ///
+    /// Example:
+    ///
+    /// ```
+    /// #![feature(specialization)]
+    /// trait Tr {
+    ///     fn assoc(&self);
+    /// }
+    ///
+    /// impl<T> Tr for T {
+    ///     default fn assoc(&self) {}
+    /// }
+    ///
+    /// impl Tr for u8 {}
+    /// ```
+    ///
+    /// If we start the leaf definition search at `impl Tr for u8`, that impl will be the
+    /// `finalizing_node`, while `defining_node` will be the generic impl.
+    ///
+    /// If the leaf definition search is started at the generic impl, `finalizing_node` will be
+    /// `None`, since the most specialized impl we found still allows overriding the method
+    /// (doesn't finalize it).
+    pub finalizing_node: Option<Node>,
+}
+
+impl LeafDef {
+    /// Returns whether this definition is known to not be further specializable.
+    pub fn is_final(&self) -> bool {
+        self.finalizing_node.is_some()
+    }
+}
+
+impl<'tcx> Ancestors<'tcx> {
+    /// Finds the bottom-most (ie. most specialized) definition of an associated
+    /// item.
+    pub fn leaf_def(mut self, tcx: TyCtxt<'tcx>, trait_item_def_id: DefId) -> Option<LeafDef> {
+        let mut finalizing_node = None;
+
+        self.find_map(|node| {
+            if let Some(item) = node.item(tcx, trait_item_def_id) {
+                if finalizing_node.is_none() {
+                    let is_specializable = item.defaultness(tcx).is_default()
+                        || tcx.impl_defaultness(node.def_id()).is_default();
+
+                    if !is_specializable {
+                        finalizing_node = Some(node);
+                    }
+                }
+
+                Some(LeafDef { item: *item, defining_node: node, finalizing_node })
+            } else {
+                // Item not mentioned. This "finalizes" any defaulted item provided by an ancestor.
+                finalizing_node = Some(node);
+                None
+            }
+        })
+    }
+}
+
+/// Walk up the specialization ancestors of a given impl, starting with that
+/// impl itself.
+///
+/// Returns `Err` if an error was reported while building the specialization
+/// graph.
+pub fn ancestors<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    trait_def_id: DefId,
+    start_from_impl: DefId,
+) -> Result<Ancestors<'tcx>, ErrorGuaranteed> {
+    let specialization_graph = tcx.specialization_graph_of(trait_def_id);
+
+    if let Some(reported) = specialization_graph.has_errored {
+        Err(reported)
+    } else if let Some(reported) = tcx.type_of(start_from_impl).error_reported() {
+        Err(reported)
+    } else {
+        Ok(Ancestors {
+            trait_def_id,
+            specialization_graph,
+            current_source: Some(Node::Impl(start_from_impl)),
+        })
+    }
+}
diff --git a/compiler/rustc_middle/src/traits/structural_impls.rs b/compiler/rustc_middle/src/traits/structural_impls.rs
new file mode 100644
index 000000000..7fbd57ac7
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/structural_impls.rs
@@ -0,0 +1,135 @@
+use crate::traits;
+
+use std::fmt;
+
+// Structural impls for the structs in `traits`.
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSource<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match *self {
+            super::ImplSource::UserDefined(ref v) => write!(f, "{:?}", v),
+
+            super::ImplSource::AutoImpl(ref t) => write!(f, "{:?}", t),
+
+            super::ImplSource::Closure(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::Generator(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::FnPointer(ref d) => write!(f, "({:?})", d),
+
+            super::ImplSource::DiscriminantKind(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::Pointee(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::Object(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::Param(ref n, ct) => {
+                write!(f, "ImplSourceParamData({:?}, {:?})", n, ct)
+            }
+
+            super::ImplSource::Builtin(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::TraitAlias(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::TraitUpcasting(ref d) => write!(f, "{:?}", d),
+
+            super::ImplSource::ConstDestruct(ref d) => write!(f, "{:?}", d),
+        }
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceUserDefinedData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceUserDefinedData(impl_def_id={:?}, substs={:?}, nested={:?})",
+            self.impl_def_id, self.substs, self.nested
+        )
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceGeneratorData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceGeneratorData(generator_def_id={:?}, substs={:?}, nested={:?})",
+            self.generator_def_id, self.substs, self.nested
+        )
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceClosureData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceClosureData(closure_def_id={:?}, substs={:?}, nested={:?})",
+            self.closure_def_id, self.substs, self.nested
+        )
+    }
+}
+
+impl<N: fmt::Debug> fmt::Debug for traits::ImplSourceBuiltinData<N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "ImplSourceBuiltinData(nested={:?})", self.nested)
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceTraitUpcastingData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceTraitUpcastingData(upcast={:?}, vtable_vptr_slot={:?}, nested={:?})",
+            self.upcast_trait_ref, self.vtable_vptr_slot, self.nested
+        )
+    }
+}
+
+impl<N: fmt::Debug> fmt::Debug for traits::ImplSourceAutoImplData<N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceAutoImplData(trait_def_id={:?}, nested={:?})",
+            self.trait_def_id, self.nested
+        )
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceObjectData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceObjectData(upcast={:?}, vtable_base={}, nested={:?})",
+            self.upcast_trait_ref, self.vtable_base, self.nested
+        )
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceFnPointerData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "ImplSourceFnPointerData(fn_ty={:?}, nested={:?})", self.fn_ty, self.nested)
+    }
+}
+
+impl<'tcx, N: fmt::Debug> fmt::Debug for traits::ImplSourceTraitAliasData<'tcx, N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(
+            f,
+            "ImplSourceTraitAliasData(alias_def_id={:?}, substs={:?}, nested={:?})",
+            self.alias_def_id, self.substs, self.nested
+        )
+    }
+}
+
+impl<N: fmt::Debug> fmt::Debug for traits::ImplSourceConstDestructData<N> {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        write!(f, "ImplSourceConstDestructData(nested={:?})", self.nested)
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////
+// Lift implementations
+
+TrivialTypeTraversalAndLiftImpls! {
+    super::ImplSourceDiscriminantKindData,
+    super::ImplSourcePointeeData,
+}
diff --git a/compiler/rustc_middle/src/traits/util.rs b/compiler/rustc_middle/src/traits/util.rs
new file mode 100644
index 000000000..d54b8c599
--- /dev/null
+++ b/compiler/rustc_middle/src/traits/util.rs
@@ -0,0 +1,49 @@
+use rustc_data_structures::fx::FxHashSet;
+
+use crate::ty::{PolyTraitRef, TyCtxt};
+
+/// Given a PolyTraitRef, get the PolyTraitRefs of the trait's (transitive) supertraits.
+///
+/// A simplified version of the same function at `rustc_infer::traits::util::supertraits`.
+pub fn supertraits<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    trait_ref: PolyTraitRef<'tcx>,
+) -> impl Iterator<Item = PolyTraitRef<'tcx>> {
+    Elaborator { tcx, visited: FxHashSet::from_iter([trait_ref]), stack: vec![trait_ref] }
+}
+
+struct Elaborator<'tcx> {
+    tcx: TyCtxt<'tcx>,
+    visited: FxHashSet<PolyTraitRef<'tcx>>,
+    stack: Vec<PolyTraitRef<'tcx>>,
+}
+
+impl<'tcx> Elaborator<'tcx> {
+    fn elaborate(&mut self, trait_ref: PolyTraitRef<'tcx>) {
+        let supertrait_refs = self
+            .tcx
+            .super_predicates_of(trait_ref.def_id())
+            .predicates
+            .into_iter()
+            .flat_map(|(pred, _)| {
+                pred.subst_supertrait(self.tcx, &trait_ref).to_opt_poly_trait_pred()
+            })
+            .map(|t| t.map_bound(|pred| pred.trait_ref))
+            .filter(|supertrait_ref| self.visited.insert(*supertrait_ref));
+
+        self.stack.extend(supertrait_refs);
+    }
+}
+
+impl<'tcx> Iterator for Elaborator<'tcx> {
+    type Item = PolyTraitRef<'tcx>;
+
+    fn next(&mut self) -> Option<PolyTraitRef<'tcx>> {
+        if let Some(trait_ref) = self.stack.pop() {
+            self.elaborate(trait_ref);
+            Some(trait_ref)
+        } else {
+            None
+        }
+    }
+}