Merging upstream version 1.68.2+dfsg1.

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

10 files changed, 2301 insertions, 0 deletions

diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly.rs
new file mode 100644
index 000000000..31c1bc9ec
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/assembly.rs
@@ -0,0 +1,387 @@
+//! Code shared by trait and projection goals for candidate assembly.
+
+use super::infcx_ext::InferCtxtExt;
+use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, MaybeCause, QueryResult};
+use rustc_hir::def_id::DefId;
+use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::util::elaborate_predicates;
+use rustc_middle::ty::TypeFoldable;
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use std::fmt::Debug;
+
+/// A candidate is a possible way to prove a goal.
+///
+/// It consists of both the `source`, which describes how that goal would be proven,
+/// and the `result` when using the given `source`.
+#[derive(Debug, Clone)]
+pub(super) struct Candidate<'tcx> {
+    pub(super) source: CandidateSource,
+    pub(super) result: CanonicalResponse<'tcx>,
+}
+
+/// Possible ways the given goal can be proven.
+#[derive(Debug, Clone, Copy)]
+pub(super) enum CandidateSource {
+    /// A user written impl.
+    ///
+    /// ## Examples
+    ///
+    /// ```rust
+    /// fn main() {
+    ///     let x: Vec<u32> = Vec::new();
+    ///     // This uses the impl from the standard library to prove `Vec<T>: Clone`.
+    ///     let y = x.clone();
+    /// }
+    /// ```
+    Impl(DefId),
+    /// A builtin impl generated by the compiler. When adding a new special
+    /// trait, try to use actual impls whenever possible. Builtin impls should
+    /// only be used in cases where the impl cannot be manually be written.
+    ///
+    /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`.
+    /// For a list of all traits with builtin impls, check out the
+    /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not
+    BuiltinImpl,
+    /// An assumption from the environment.
+    ///
+    /// More precicely we've used the `n-th` assumption in the `param_env`.
+    ///
+    /// ## Examples
+    ///
+    /// ```rust
+    /// fn is_clone<T: Clone>(x: T) -> (T, T) {
+    ///     // This uses the assumption `T: Clone` from the `where`-bounds
+    ///     // to prove `T: Clone`.
+    ///     (x.clone(), x)
+    /// }
+    /// ```
+    ParamEnv(usize),
+    /// If the self type is an alias type, e.g. an opaque type or a projection,
+    /// we know the bounds on that alias to hold even without knowing its concrete
+    /// underlying type.
+    ///
+    /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
+    /// the self type.
+    ///
+    /// ## Examples
+    ///
+    /// ```rust
+    /// trait Trait {
+    ///     type Assoc: Clone;
+    /// }
+    ///
+    /// fn foo<T: Trait>(x: <T as Trait>::Assoc) {
+    ///     // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in
+    ///     // in the trait definition.
+    ///     let _y = x.clone();
+    /// }
+    /// ```
+    AliasBound(usize),
+}
+
+pub(super) trait GoalKind<'tcx>: TypeFoldable<'tcx> + Copy + Eq {
+    fn self_ty(self) -> Ty<'tcx>;
+
+    fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self;
+
+    fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId;
+
+    fn consider_impl_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        impl_def_id: DefId,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_assumption(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_auto_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_trait_alias_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_sized_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_copy_clone_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_pointer_sized_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_fn_trait_candidates(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        kind: ty::ClosureKind,
+    ) -> QueryResult<'tcx>;
+
+    fn consider_builtin_tuple_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx>;
+}
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    pub(super) fn assemble_and_evaluate_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+    ) -> Vec<Candidate<'tcx>> {
+        debug_assert_eq!(goal, self.infcx.resolve_vars_if_possible(goal));
+
+        // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule,
+        // object bound, alias bound, etc. We are unable to determine this until we can at
+        // least structually resolve the type one layer.
+        if goal.predicate.self_ty().is_ty_var() {
+            return vec![Candidate {
+                source: CandidateSource::BuiltinImpl,
+                result: self
+                    .make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity))
+                    .unwrap(),
+            }];
+        }
+
+        let mut candidates = Vec::new();
+
+        self.assemble_candidates_after_normalizing_self_ty(goal, &mut candidates);
+
+        self.assemble_impl_candidates(goal, &mut candidates);
+
+        self.assemble_builtin_impl_candidates(goal, &mut candidates);
+
+        self.assemble_param_env_candidates(goal, &mut candidates);
+
+        self.assemble_alias_bound_candidates(goal, &mut candidates);
+
+        self.assemble_object_bound_candidates(goal, &mut candidates);
+
+        candidates
+    }
+
+    /// If the self type of a goal is a projection, computing the relevant candidates is difficult.
+    ///
+    /// To deal with this, we first try to normalize the self type and add the candidates for the normalized
+    /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in
+    /// this case as projections as self types add `
+    fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let tcx = self.tcx();
+        // FIXME: We also have to normalize opaque types, not sure where to best fit that in.
+        let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else {
+            return
+        };
+        self.infcx.probe(|_| {
+            let normalized_ty = self.infcx.next_ty_infer();
+            let normalizes_to_goal = goal.with(
+                tcx,
+                ty::Binder::dummy(ty::ProjectionPredicate {
+                    projection_ty,
+                    term: normalized_ty.into(),
+                }),
+            );
+            let normalization_certainty = match self.evaluate_goal(normalizes_to_goal) {
+                Ok((_, certainty)) => certainty,
+                Err(NoSolution) => return,
+            };
+            let normalized_ty = self.infcx.resolve_vars_if_possible(normalized_ty);
+
+            // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate.
+            // This doesn't work as long as we use `CandidateSource` in winnowing.
+            let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
+            // FIXME: This is broken if we care about the `usize` of `AliasBound` because the self type
+            // could be normalized to yet another projection with different item bounds.
+            let normalized_candidates = self.assemble_and_evaluate_candidates(goal);
+            for mut normalized_candidate in normalized_candidates {
+                normalized_candidate.result =
+                    normalized_candidate.result.unchecked_map(|mut response| {
+                        // FIXME: This currently hides overflow in the normalization step of the self type
+                        // which is probably wrong. Maybe `unify_and` should actually keep overflow as
+                        // we treat it as non-fatal anyways.
+                        response.certainty = response.certainty.unify_and(normalization_certainty);
+                        response
+                    });
+                candidates.push(normalized_candidate);
+            }
+        })
+    }
+
+    fn assemble_impl_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let tcx = self.tcx();
+        tcx.for_each_relevant_impl(
+            goal.predicate.trait_def_id(tcx),
+            goal.predicate.self_ty(),
+            |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) {
+                Ok(result) => candidates
+                    .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }),
+                Err(NoSolution) => (),
+            },
+        );
+    }
+
+    fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let lang_items = self.tcx().lang_items();
+        let trait_def_id = goal.predicate.trait_def_id(self.tcx());
+        let result = if self.tcx().trait_is_auto(trait_def_id) {
+            G::consider_auto_trait_candidate(self, goal)
+        } else if self.tcx().trait_is_alias(trait_def_id) {
+            G::consider_trait_alias_candidate(self, goal)
+        } else if lang_items.sized_trait() == Some(trait_def_id) {
+            G::consider_builtin_sized_candidate(self, goal)
+        } else if lang_items.copy_trait() == Some(trait_def_id)
+            || lang_items.clone_trait() == Some(trait_def_id)
+        {
+            G::consider_builtin_copy_clone_candidate(self, goal)
+        } else if lang_items.pointer_sized() == Some(trait_def_id) {
+            G::consider_builtin_pointer_sized_candidate(self, goal)
+        } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) {
+            G::consider_builtin_fn_trait_candidates(self, goal, kind)
+        } else if lang_items.tuple_trait() == Some(trait_def_id) {
+            G::consider_builtin_tuple_candidate(self, goal)
+        } else {
+            Err(NoSolution)
+        };
+
+        match result {
+            Ok(result) => {
+                candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
+            }
+            Err(NoSolution) => (),
+        }
+    }
+
+    fn assemble_param_env_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        for (i, assumption) in goal.param_env.caller_bounds().iter().enumerate() {
+            match G::consider_assumption(self, goal, assumption) {
+                Ok(result) => {
+                    candidates.push(Candidate { source: CandidateSource::ParamEnv(i), result })
+                }
+                Err(NoSolution) => (),
+            }
+        }
+    }
+
+    fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let alias_ty = match goal.predicate.self_ty().kind() {
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Uint(_)
+            | ty::Float(_)
+            | ty::Adt(_, _)
+            | ty::Foreign(_)
+            | ty::Str
+            | ty::Array(_, _)
+            | ty::Slice(_)
+            | ty::RawPtr(_)
+            | ty::Ref(_, _, _)
+            | ty::FnDef(_, _)
+            | ty::FnPtr(_)
+            | ty::Dynamic(..)
+            | ty::Closure(..)
+            | ty::Generator(..)
+            | ty::GeneratorWitness(_)
+            | ty::Never
+            | ty::Tuple(_)
+            | ty::Param(_)
+            | ty::Placeholder(..)
+            | ty::Infer(_)
+            | ty::Error(_) => return,
+            ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
+            ty::Alias(_, alias_ty) => alias_ty,
+        };
+
+        for (i, (assumption, _)) in self
+            .tcx()
+            .bound_explicit_item_bounds(alias_ty.def_id)
+            .subst_iter_copied(self.tcx(), alias_ty.substs)
+            .enumerate()
+        {
+            match G::consider_assumption(self, goal, assumption) {
+                Ok(result) => {
+                    candidates.push(Candidate { source: CandidateSource::AliasBound(i), result })
+                }
+                Err(NoSolution) => (),
+            }
+        }
+    }
+
+    fn assemble_object_bound_candidates<G: GoalKind<'tcx>>(
+        &mut self,
+        goal: Goal<'tcx, G>,
+        candidates: &mut Vec<Candidate<'tcx>>,
+    ) {
+        let self_ty = goal.predicate.self_ty();
+        let bounds = match *self_ty.kind() {
+            ty::Bool
+            | ty::Char
+            | ty::Int(_)
+            | ty::Uint(_)
+            | ty::Float(_)
+            | ty::Adt(_, _)
+            | ty::Foreign(_)
+            | ty::Str
+            | ty::Array(_, _)
+            | ty::Slice(_)
+            | ty::RawPtr(_)
+            | ty::Ref(_, _, _)
+            | ty::FnDef(_, _)
+            | ty::FnPtr(_)
+            | ty::Alias(..)
+            | ty::Closure(..)
+            | ty::Generator(..)
+            | ty::GeneratorWitness(_)
+            | ty::Never
+            | ty::Tuple(_)
+            | ty::Param(_)
+            | ty::Placeholder(..)
+            | ty::Infer(_)
+            | ty::Error(_) => return,
+            ty::Bound(..) => bug!("unexpected bound type: {goal:?}"),
+            ty::Dynamic(bounds, ..) => bounds,
+        };
+
+        let tcx = self.tcx();
+        for assumption in
+            elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)))
+        {
+            match G::consider_assumption(self, goal, assumption.predicate) {
+                Ok(result) => {
+                    candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result })
+                }
+                Err(NoSolution) => (),
+            }
+        }
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
new file mode 100644
index 000000000..a6240666e
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -0,0 +1,109 @@
+use std::mem;
+
+use rustc_data_structures::fx::FxHashMap;
+use rustc_infer::{
+    infer::InferCtxt,
+    traits::{
+        query::NoSolution, FulfillmentError, FulfillmentErrorCode, PredicateObligation,
+        SelectionError, TraitEngine,
+    },
+};
+use rustc_middle::ty;
+
+use super::{search_graph, Certainty, EvalCtxt};
+
+/// A trait engine using the new trait solver.
+///
+/// This is mostly identical to how `evaluate_all` works inside of the
+/// solver, except that the requirements are slightly different.
+///
+/// Unlike `evaluate_all` it is possible to add new obligations later on
+/// and we also have to track diagnostics information by using `Obligation`
+/// instead of `Goal`.
+///
+/// It is also likely that we want to use slightly different datastructures
+/// here as this will have to deal with far more root goals than `evaluate_all`.
+pub struct FulfillmentCtxt<'tcx> {
+    obligations: Vec<PredicateObligation<'tcx>>,
+}
+
+impl<'tcx> FulfillmentCtxt<'tcx> {
+    pub fn new() -> FulfillmentCtxt<'tcx> {
+        FulfillmentCtxt { obligations: Vec::new() }
+    }
+}
+
+impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
+    fn register_predicate_obligation(
+        &mut self,
+        _infcx: &InferCtxt<'tcx>,
+        obligation: PredicateObligation<'tcx>,
+    ) {
+        self.obligations.push(obligation);
+    }
+
+    fn select_all_or_error(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
+        let errors = self.select_where_possible(infcx);
+        if !errors.is_empty() {
+            return errors;
+        }
+
+        self.obligations
+            .drain(..)
+            .map(|obligation| FulfillmentError {
+                obligation: obligation.clone(),
+                code: FulfillmentErrorCode::CodeAmbiguity,
+                root_obligation: obligation,
+            })
+            .collect()
+    }
+
+    fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
+        let mut errors = Vec::new();
+        for i in 0.. {
+            if !infcx.tcx.recursion_limit().value_within_limit(i) {
+                unimplemented!("overflowed on pending obligations: {:?}", self.obligations);
+            }
+
+            let mut has_changed = false;
+            for obligation in mem::take(&mut self.obligations) {
+                let goal = obligation.clone().into();
+                let search_graph = &mut search_graph::SearchGraph::new(infcx.tcx);
+                let mut ecx = EvalCtxt::new_outside_solver(infcx, search_graph);
+                let (changed, certainty) = match ecx.evaluate_goal(goal) {
+                    Ok(result) => result,
+                    Err(NoSolution) => {
+                        errors.push(FulfillmentError {
+                            obligation: obligation.clone(),
+                            code: FulfillmentErrorCode::CodeSelectionError(
+                                SelectionError::Unimplemented,
+                            ),
+                            root_obligation: obligation,
+                        });
+                        continue;
+                    }
+                };
+
+                has_changed |= changed;
+                match certainty {
+                    Certainty::Yes => {}
+                    Certainty::Maybe(_) => self.obligations.push(obligation),
+                }
+            }
+
+            if !has_changed {
+                break;
+            }
+        }
+
+        errors
+    }
+
+    fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
+        self.obligations.clone()
+    }
+
+    fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> {
+        unimplemented!("Should be moved out of `TraitEngine`")
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/infcx_ext.rs b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs
new file mode 100644
index 000000000..42f597c78
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/infcx_ext.rs
@@ -0,0 +1,78 @@
+use rustc_infer::infer::at::ToTrace;
+use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind};
+use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime};
+use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::ObligationCause;
+use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
+use rustc_middle::ty::{self, Ty, TypeFoldable};
+use rustc_span::DUMMY_SP;
+
+use super::Goal;
+
+/// Methods used inside of the canonical queries of the solver.
+///
+/// Most notably these do not care about diagnostics information.
+/// If you find this while looking for methods to use outside of the
+/// solver, you may look at the implementation of these method for
+/// help.
+pub(super) trait InferCtxtExt<'tcx> {
+    fn next_ty_infer(&self) -> Ty<'tcx>;
+    fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx>;
+
+    fn eq<T: ToTrace<'tcx>>(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        lhs: T,
+        rhs: T,
+    ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution>;
+
+    fn instantiate_bound_vars_with_infer<T: TypeFoldable<'tcx> + Copy>(
+        &self,
+        value: ty::Binder<'tcx, T>,
+    ) -> T;
+}
+
+impl<'tcx> InferCtxtExt<'tcx> for InferCtxt<'tcx> {
+    fn next_ty_infer(&self) -> Ty<'tcx> {
+        self.next_ty_var(TypeVariableOrigin {
+            kind: TypeVariableOriginKind::MiscVariable,
+            span: DUMMY_SP,
+        })
+    }
+    fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> {
+        self.next_const_var(
+            ty,
+            ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span: DUMMY_SP },
+        )
+    }
+
+    #[instrument(level = "debug", skip(self, param_env), ret)]
+    fn eq<T: ToTrace<'tcx>>(
+        &self,
+        param_env: ty::ParamEnv<'tcx>,
+        lhs: T,
+        rhs: T,
+    ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> {
+        self.at(&ObligationCause::dummy(), param_env)
+            .define_opaque_types(false)
+            .eq(lhs, rhs)
+            .map(|InferOk { value: (), obligations }| {
+                obligations.into_iter().map(|o| o.into()).collect()
+            })
+            .map_err(|e| {
+                debug!(?e, "failed to equate");
+                NoSolution
+            })
+    }
+
+    fn instantiate_bound_vars_with_infer<T: TypeFoldable<'tcx> + Copy>(
+        &self,
+        value: ty::Binder<'tcx, T>,
+    ) -> T {
+        self.replace_bound_vars_with_fresh_vars(
+            DUMMY_SP,
+            LateBoundRegionConversionTime::HigherRankedType,
+            value,
+        )
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
new file mode 100644
index 000000000..32eb84635
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -0,0 +1,400 @@
+//! The new trait solver, currently still WIP.
+//!
+//! As a user of the trait system, you can use `TyCtxt::evaluate_goal` to
+//! interact with this solver.
+//!
+//! For a high-level overview of how this solver works, check out the relevant
+//! section of the rustc-dev-guide.
+//!
+//! FIXME(@lcnr): Write that section. If you read this before then ask me
+//! about it on zulip.
+
+// FIXME: Instead of using `infcx.canonicalize_query` we have to add a new routine which
+// preserves universes and creates a unique var (in the highest universe) for each
+// appearance of a region.
+
+// FIXME: `CanonicalVarValues` should be interned and `Copy`.
+
+// FIXME: uses of `infcx.at` need to enable deferred projection equality once that's implemented.
+
+use std::mem;
+
+use rustc_infer::infer::canonical::{Canonical, CanonicalVarKind, CanonicalVarValues};
+use rustc_infer::infer::canonical::{OriginalQueryValues, QueryRegionConstraints, QueryResponse};
+use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt};
+use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::Obligation;
+use rustc_middle::infer::canonical::Certainty as OldCertainty;
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{RegionOutlivesPredicate, ToPredicate, TypeOutlivesPredicate};
+use rustc_span::DUMMY_SP;
+
+use crate::traits::ObligationCause;
+
+mod assembly;
+mod fulfill;
+mod infcx_ext;
+mod project_goals;
+mod search_graph;
+mod trait_goals;
+
+pub use fulfill::FulfillmentCtxt;
+
+/// A goal is a statement, i.e. `predicate`, we want to prove
+/// given some assumptions, i.e. `param_env`.
+///
+/// Most of the time the `param_env` contains the `where`-bounds of the function
+/// we're currently typechecking while the `predicate` is some trait bound.
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub struct Goal<'tcx, P> {
+    param_env: ty::ParamEnv<'tcx>,
+    predicate: P,
+}
+
+impl<'tcx, P> Goal<'tcx, P> {
+    pub fn new(
+        tcx: TyCtxt<'tcx>,
+        param_env: ty::ParamEnv<'tcx>,
+        predicate: impl ToPredicate<'tcx, P>,
+    ) -> Goal<'tcx, P> {
+        Goal { param_env, predicate: predicate.to_predicate(tcx) }
+    }
+
+    /// Updates the goal to one with a different `predicate` but the same `param_env`.
+    fn with<Q>(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> {
+        Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) }
+    }
+}
+
+impl<'tcx, P> From<Obligation<'tcx, P>> for Goal<'tcx, P> {
+    fn from(obligation: Obligation<'tcx, P>) -> Goal<'tcx, P> {
+        Goal { param_env: obligation.param_env, predicate: obligation.predicate }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable)]
+pub struct Response<'tcx> {
+    pub var_values: CanonicalVarValues<'tcx>,
+    /// Additional constraints returned by this query.
+    pub external_constraints: ExternalConstraints<'tcx>,
+    pub certainty: Certainty,
+}
+
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub enum Certainty {
+    Yes,
+    Maybe(MaybeCause),
+}
+
+impl Certainty {
+    /// When proving multiple goals using **AND**, e.g. nested obligations for an impl,
+    /// use this function to unify the certainty of these goals
+    pub fn unify_and(self, other: Certainty) -> Certainty {
+        match (self, other) {
+            (Certainty::Yes, Certainty::Yes) => Certainty::Yes,
+            (Certainty::Yes, Certainty::Maybe(_)) => other,
+            (Certainty::Maybe(_), Certainty::Yes) => self,
+            (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => {
+                Certainty::Maybe(MaybeCause::Overflow)
+            }
+            // If at least one of the goals is ambiguous, hide the overflow as the ambiguous goal
+            // may still result in failure.
+            (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(_))
+            | (Certainty::Maybe(_), Certainty::Maybe(MaybeCause::Ambiguity)) => {
+                Certainty::Maybe(MaybeCause::Ambiguity)
+            }
+        }
+    }
+}
+
+/// Why we failed to evaluate a goal.
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)]
+pub enum MaybeCause {
+    /// We failed due to ambiguity. This ambiguity can either
+    /// be a true ambiguity, i.e. there are multiple different answers,
+    /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals.
+    Ambiguity,
+    /// We gave up due to an overflow, most often by hitting the recursion limit.
+    Overflow,
+}
+
+/// Additional constraints returned on success.
+#[derive(Debug, PartialEq, Eq, Clone, Hash, TypeFoldable, TypeVisitable, Default)]
+pub struct ExternalConstraints<'tcx> {
+    // FIXME: implement this.
+    regions: (),
+    opaque_types: Vec<(Ty<'tcx>, Ty<'tcx>)>,
+}
+
+type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>;
+type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>;
+/// The result of evaluating a canonical query.
+///
+/// FIXME: We use a different type than the existing canonical queries. This is because
+/// we need to add a `Certainty` for `overflow` and may want to restructure this code without
+/// having to worry about changes to currently used code. Once we've made progress on this
+/// solver, merge the two responses again.
+pub type QueryResult<'tcx> = Result<CanonicalResponse<'tcx>, NoSolution>;
+
+pub trait TyCtxtExt<'tcx> {
+    fn evaluate_goal(self, goal: CanonicalGoal<'tcx>) -> QueryResult<'tcx>;
+}
+
+impl<'tcx> TyCtxtExt<'tcx> for TyCtxt<'tcx> {
+    fn evaluate_goal(self, goal: CanonicalGoal<'tcx>) -> QueryResult<'tcx> {
+        let mut search_graph = search_graph::SearchGraph::new(self);
+        EvalCtxt::evaluate_canonical_goal(self, &mut search_graph, goal)
+    }
+}
+
+struct EvalCtxt<'a, 'tcx> {
+    infcx: &'a InferCtxt<'tcx>,
+    var_values: CanonicalVarValues<'tcx>,
+
+    search_graph: &'a mut search_graph::SearchGraph<'tcx>,
+}
+
+impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
+    fn tcx(&self) -> TyCtxt<'tcx> {
+        self.infcx.tcx
+    }
+
+    /// Creates a new evaluation context outside of the trait solver.
+    ///
+    /// With this solver making a canonical response doesn't make much sense.
+    /// The `search_graph` for this solver has to be completely empty.
+    fn new_outside_solver(
+        infcx: &'a InferCtxt<'tcx>,
+        search_graph: &'a mut search_graph::SearchGraph<'tcx>,
+    ) -> EvalCtxt<'a, 'tcx> {
+        assert!(search_graph.is_empty());
+        EvalCtxt { infcx, var_values: CanonicalVarValues::dummy(), search_graph }
+    }
+
+    #[instrument(level = "debug", skip(tcx, search_graph), ret)]
+    fn evaluate_canonical_goal(
+        tcx: TyCtxt<'tcx>,
+        search_graph: &'a mut search_graph::SearchGraph<'tcx>,
+        canonical_goal: CanonicalGoal<'tcx>,
+    ) -> QueryResult<'tcx> {
+        match search_graph.try_push_stack(tcx, canonical_goal) {
+            Ok(()) => {}
+            // Our goal is already on the stack, eager return.
+            Err(response) => return response,
+        }
+
+        // We may have to repeatedly recompute the goal in case of coinductive cycles,
+        // check out the `cache` module for more information.
+        //
+        // FIXME: Similar to `evaluate_all`, this has to check for overflow.
+        loop {
+            let (ref infcx, goal, var_values) =
+                tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal);
+            let mut ecx = EvalCtxt { infcx, var_values, search_graph };
+            let result = ecx.compute_goal(goal);
+
+            // FIXME: `Response` should be `Copy`
+            if search_graph.try_finalize_goal(tcx, canonical_goal, result.clone()) {
+                return result;
+            }
+        }
+    }
+
+    fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> {
+        let external_constraints = take_external_constraints(self.infcx)?;
+
+        Ok(self.infcx.canonicalize_response(Response {
+            var_values: self.var_values.clone(),
+            external_constraints,
+            certainty,
+        }))
+    }
+
+    /// Recursively evaluates `goal`, returning whether any inference vars have
+    /// been constrained and the certainty of the result.
+    fn evaluate_goal(
+        &mut self,
+        goal: Goal<'tcx, ty::Predicate<'tcx>>,
+    ) -> Result<(bool, Certainty), NoSolution> {
+        let mut orig_values = OriginalQueryValues::default();
+        let canonical_goal = self.infcx.canonicalize_query(goal, &mut orig_values);
+        let canonical_response =
+            EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?;
+        Ok((
+            !canonical_response.value.var_values.is_identity(),
+            instantiate_canonical_query_response(self.infcx, &orig_values, canonical_response),
+        ))
+    }
+
+    fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> {
+        let Goal { param_env, predicate } = goal;
+        let kind = predicate.kind();
+        if let Some(kind) = kind.no_bound_vars() {
+            match kind {
+                ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => {
+                    self.compute_trait_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => {
+                    self.compute_projection_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => {
+                    self.compute_type_outlives_goal(Goal { param_env, predicate })
+                }
+                ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => {
+                    self.compute_region_outlives_goal(Goal { param_env, predicate })
+                }
+                // FIXME: implement these predicates :)
+                ty::PredicateKind::WellFormed(_)
+                | ty::PredicateKind::ObjectSafe(_)
+                | ty::PredicateKind::ClosureKind(_, _, _)
+                | ty::PredicateKind::Subtype(_)
+                | ty::PredicateKind::Coerce(_)
+                | ty::PredicateKind::ConstEvaluatable(_)
+                | ty::PredicateKind::ConstEquate(_, _)
+                | ty::PredicateKind::TypeWellFormedFromEnv(_)
+                | ty::PredicateKind::Ambiguous => self.make_canonical_response(Certainty::Yes),
+            }
+        } else {
+            let kind = self.infcx.replace_bound_vars_with_placeholders(kind);
+            let goal = goal.with(self.tcx(), ty::Binder::dummy(kind));
+            let (_, certainty) = self.evaluate_goal(goal)?;
+            self.make_canonical_response(certainty)
+        }
+    }
+
+    fn compute_type_outlives_goal(
+        &mut self,
+        _goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        self.make_canonical_response(Certainty::Yes)
+    }
+
+    fn compute_region_outlives_goal(
+        &mut self,
+        _goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        self.make_canonical_response(Certainty::Yes)
+    }
+}
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    fn evaluate_all(
+        &mut self,
+        mut goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
+    ) -> Result<Certainty, NoSolution> {
+        let mut new_goals = Vec::new();
+        self.repeat_while_none(|this| {
+            let mut has_changed = Err(Certainty::Yes);
+            for goal in goals.drain(..) {
+                let (changed, certainty) = match this.evaluate_goal(goal) {
+                    Ok(result) => result,
+                    Err(NoSolution) => return Some(Err(NoSolution)),
+                };
+
+                if changed {
+                    has_changed = Ok(());
+                }
+
+                match certainty {
+                    Certainty::Yes => {}
+                    Certainty::Maybe(_) => {
+                        new_goals.push(goal);
+                        has_changed = has_changed.map_err(|c| c.unify_and(certainty));
+                    }
+                }
+            }
+
+            match has_changed {
+                Ok(()) => {
+                    mem::swap(&mut new_goals, &mut goals);
+                    None
+                }
+                Err(certainty) => Some(Ok(certainty)),
+            }
+        })
+    }
+
+    fn evaluate_all_and_make_canonical_response(
+        &mut self,
+        goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
+    ) -> QueryResult<'tcx> {
+        self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty))
+    }
+}
+
+#[instrument(level = "debug", skip(infcx), ret)]
+fn take_external_constraints<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+) -> Result<ExternalConstraints<'tcx>, NoSolution> {
+    let region_obligations = infcx.take_registered_region_obligations();
+    let opaque_types = infcx.take_opaque_types_for_query_response();
+    Ok(ExternalConstraints {
+        // FIXME: Now that's definitely wrong :)
+        //
+        // Should also do the leak check here I think
+        regions: drop(region_obligations),
+        opaque_types,
+    })
+}
+
+fn instantiate_canonical_query_response<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    original_values: &OriginalQueryValues<'tcx>,
+    response: CanonicalResponse<'tcx>,
+) -> Certainty {
+    let Ok(InferOk { value, obligations }) = infcx
+        .instantiate_query_response_and_region_obligations(
+            &ObligationCause::dummy(),
+            ty::ParamEnv::empty(),
+            original_values,
+            &response.unchecked_map(|resp| QueryResponse {
+                var_values: resp.var_values,
+                region_constraints: QueryRegionConstraints::default(),
+                certainty: match resp.certainty {
+                    Certainty::Yes => OldCertainty::Proven,
+                    Certainty::Maybe(_) => OldCertainty::Ambiguous,
+                },
+                opaque_types: resp.external_constraints.opaque_types,
+                value: resp.certainty,
+            }),
+        ) else { bug!(); };
+    assert!(obligations.is_empty());
+    value
+}
+
+pub(super) fn response_no_constraints<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    goal: Canonical<'tcx, impl Sized>,
+    certainty: Certainty,
+) -> QueryResult<'tcx> {
+    let var_values = goal
+        .variables
+        .iter()
+        .enumerate()
+        .map(|(i, info)| match info.kind {
+            CanonicalVarKind::Ty(_) | CanonicalVarKind::PlaceholderTy(_) => {
+                tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i).into())).into()
+            }
+            CanonicalVarKind::Region(_) | CanonicalVarKind::PlaceholderRegion(_) => {
+                let br = ty::BoundRegion {
+                    var: ty::BoundVar::from_usize(i),
+                    kind: ty::BrAnon(i as u32, None),
+                };
+                tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
+            }
+            CanonicalVarKind::Const(_, ty) | CanonicalVarKind::PlaceholderConst(_, ty) => tcx
+                .mk_const(ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_usize(i)), ty)
+                .into(),
+        })
+        .collect();
+
+    Ok(Canonical {
+        max_universe: goal.max_universe,
+        variables: goal.variables,
+        value: Response {
+            var_values: CanonicalVarValues { var_values },
+            external_constraints: Default::default(),
+            certainty,
+        },
+    })
+}
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
new file mode 100644
index 000000000..e39fa0533
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -0,0 +1,430 @@
+use crate::traits::{specialization_graph, translate_substs};
+
+use super::assembly::{self, Candidate, CandidateSource};
+use super::infcx_ext::InferCtxtExt;
+use super::trait_goals::structural_traits;
+use super::{Certainty, EvalCtxt, Goal, MaybeCause, QueryResult};
+use rustc_errors::ErrorGuaranteed;
+use rustc_hir::def::DefKind;
+use rustc_hir::def_id::DefId;
+use rustc_infer::infer::InferCtxt;
+use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::specialization_graph::LeafDef;
+use rustc_infer::traits::Reveal;
+use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
+use rustc_middle::ty::{self, Ty, TyCtxt};
+use rustc_middle::ty::{ProjectionPredicate, TypeSuperVisitable, TypeVisitor};
+use rustc_middle::ty::{ToPredicate, TypeVisitable};
+use rustc_span::DUMMY_SP;
+use std::iter;
+use std::ops::ControlFlow;
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    pub(super) fn compute_projection_goal(
+        &mut self,
+        goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        // To only compute normalization once for each projection we only
+        // normalize if the expected term is an unconstrained inference variable.
+        //
+        // E.g. for `<T as Trait>::Assoc = u32` we recursively compute the goal
+        // `exists<U> <T as Trait>::Assoc = U` and then take the resulting type for
+        // `U` and equate it with `u32`. This means that we don't need a separate
+        // projection cache in the solver.
+        if self.term_is_fully_unconstrained(goal) {
+            let candidates = self.assemble_and_evaluate_candidates(goal);
+            self.merge_project_candidates(candidates)
+        } else {
+            let predicate = goal.predicate;
+            let unconstrained_rhs = match predicate.term.unpack() {
+                ty::TermKind::Ty(_) => self.infcx.next_ty_infer().into(),
+                ty::TermKind::Const(ct) => self.infcx.next_const_infer(ct.ty()).into(),
+            };
+            let unconstrained_predicate = ty::Clause::Projection(ProjectionPredicate {
+                projection_ty: goal.predicate.projection_ty,
+                term: unconstrained_rhs,
+            });
+            let (_has_changed, normalize_certainty) =
+                self.evaluate_goal(goal.with(self.tcx(), unconstrained_predicate))?;
+
+            let nested_eq_goals =
+                self.infcx.eq(goal.param_env, unconstrained_rhs, predicate.term)?;
+            let eval_certainty = self.evaluate_all(nested_eq_goals)?;
+            self.make_canonical_response(normalize_certainty.unify_and(eval_certainty))
+        }
+    }
+
+    /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`.
+    ///
+    /// This is the case if the `term` is an inference variable in the innermost universe
+    /// and does not occur in any other part of the predicate.
+    fn term_is_fully_unconstrained(&self, goal: Goal<'tcx, ProjectionPredicate<'tcx>>) -> bool {
+        let infcx = self.infcx;
+        let term_is_infer = match goal.predicate.term.unpack() {
+            ty::TermKind::Ty(ty) => {
+                if let &ty::Infer(ty::TyVar(vid)) = ty.kind() {
+                    match infcx.probe_ty_var(vid) {
+                        Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"),
+                        Err(universe) => universe == infcx.universe(),
+                    }
+                } else {
+                    false
+                }
+            }
+            ty::TermKind::Const(ct) => {
+                if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() {
+                    match self.infcx.probe_const_var(vid) {
+                        Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"),
+                        Err(universe) => universe == infcx.universe(),
+                    }
+                } else {
+                    false
+                }
+            }
+        };
+
+        // Guard against `<T as Trait<?0>>::Assoc = ?0>`.
+        struct ContainsTerm<'tcx> {
+            term: ty::Term<'tcx>,
+        }
+        impl<'tcx> TypeVisitor<'tcx> for ContainsTerm<'tcx> {
+            type BreakTy = ();
+            fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+                if t.needs_infer() {
+                    if ty::Term::from(t) == self.term {
+                        ControlFlow::BREAK
+                    } else {
+                        t.super_visit_with(self)
+                    }
+                } else {
+                    ControlFlow::CONTINUE
+                }
+            }
+
+            fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+                if c.needs_infer() {
+                    if ty::Term::from(c) == self.term {
+                        ControlFlow::BREAK
+                    } else {
+                        c.super_visit_with(self)
+                    }
+                } else {
+                    ControlFlow::CONTINUE
+                }
+            }
+        }
+
+        let mut visitor = ContainsTerm { term: goal.predicate.term };
+
+        term_is_infer
+            && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue()
+            && goal.param_env.visit_with(&mut visitor).is_continue()
+    }
+
+    fn merge_project_candidates(
+        &mut self,
+        mut candidates: Vec<Candidate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        match candidates.len() {
+            0 => return Err(NoSolution),
+            1 => return Ok(candidates.pop().unwrap().result),
+            _ => {}
+        }
+
+        if candidates.len() > 1 {
+            let mut i = 0;
+            'outer: while i < candidates.len() {
+                for j in (0..candidates.len()).filter(|&j| i != j) {
+                    if self.project_candidate_should_be_dropped_in_favor_of(
+                        &candidates[i],
+                        &candidates[j],
+                    ) {
+                        debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
+                        candidates.swap_remove(i);
+                        continue 'outer;
+                    }
+                }
+
+                debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
+                // If there are *STILL* multiple candidates, give up
+                // and report ambiguity.
+                i += 1;
+                if i > 1 {
+                    debug!("multiple matches, ambig");
+                    // FIXME: return overflow if all candidates overflow, otherwise return ambiguity.
+                    unimplemented!();
+                }
+            }
+        }
+
+        Ok(candidates.pop().unwrap().result)
+    }
+
+    fn project_candidate_should_be_dropped_in_favor_of(
+        &self,
+        candidate: &Candidate<'tcx>,
+        other: &Candidate<'tcx>,
+    ) -> bool {
+        // FIXME: implement this
+        match (candidate.source, other.source) {
+            (CandidateSource::Impl(_), _)
+            | (CandidateSource::ParamEnv(_), _)
+            | (CandidateSource::BuiltinImpl, _)
+            | (CandidateSource::AliasBound(_), _) => unimplemented!(),
+        }
+    }
+}
+
+impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
+    fn self_ty(self) -> Ty<'tcx> {
+        self.self_ty()
+    }
+
+    fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
+        self.with_self_ty(tcx, self_ty)
+    }
+
+    fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId {
+        self.trait_def_id(tcx)
+    }
+
+    fn consider_impl_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, ProjectionPredicate<'tcx>>,
+        impl_def_id: DefId,
+    ) -> QueryResult<'tcx> {
+        let tcx = ecx.tcx();
+
+        let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx);
+        let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
+        let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
+        if iter::zip(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs)
+            .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp))
+        {
+            return Err(NoSolution);
+        }
+
+        ecx.infcx.probe(|_| {
+            let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id);
+            let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
+
+            let mut nested_goals = ecx.infcx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?;
+            let where_clause_bounds = tcx
+                .predicates_of(impl_def_id)
+                .instantiate(tcx, impl_substs)
+                .predicates
+                .into_iter()
+                .map(|pred| goal.with(tcx, pred));
+
+            nested_goals.extend(where_clause_bounds);
+            let trait_ref_certainty = ecx.evaluate_all(nested_goals)?;
+
+            // In case the associated item is hidden due to specialization, we have to
+            // return ambiguity this would otherwise be incomplete, resulting in
+            // unsoundness during coherence (#105782).
+            let Some(assoc_def) = fetch_eligible_assoc_item_def(
+                ecx.infcx,
+                goal.param_env,
+                goal_trait_ref,
+                goal.predicate.def_id(),
+                impl_def_id
+            )? else {
+                let certainty = Certainty::Maybe(MaybeCause::Ambiguity);
+                return ecx.make_canonical_response(trait_ref_certainty.unify_and(certainty));
+            };
+
+            if !assoc_def.item.defaultness(tcx).has_value() {
+                tcx.sess.delay_span_bug(
+                    tcx.def_span(assoc_def.item.def_id),
+                    "missing value for assoc item in impl",
+                );
+            }
+
+            // Getting the right substitutions here is complex, e.g. given:
+            // - a goal `<Vec<u32> as Trait<i32>>::Assoc<u64>`
+            // - the applicable impl `impl<T> Trait<i32> for Vec<T>`
+            // - and the impl which defines `Assoc` being `impl<T, U> Trait<U> for Vec<T>`
+            //
+            // We first rebase the goal substs onto the impl, going from `[Vec<u32>, i32, u64]`
+            // to `[u32, u64]`.
+            //
+            // And then map these substs to the substs of the defining impl of `Assoc`, going
+            // from `[u32, u64]` to `[u32, i32, u64]`.
+            let impl_substs_with_gat = goal.predicate.projection_ty.substs.rebase_onto(
+                tcx,
+                goal_trait_ref.def_id,
+                impl_substs,
+            );
+            let substs = translate_substs(
+                ecx.infcx,
+                goal.param_env,
+                impl_def_id,
+                impl_substs_with_gat,
+                assoc_def.defining_node,
+            );
+
+            // Finally we construct the actual value of the associated type.
+            let is_const = matches!(tcx.def_kind(assoc_def.item.def_id), DefKind::AssocConst);
+            let ty = tcx.bound_type_of(assoc_def.item.def_id);
+            let term: ty::EarlyBinder<ty::Term<'tcx>> = if is_const {
+                let identity_substs =
+                    ty::InternalSubsts::identity_for_item(tcx, assoc_def.item.def_id);
+                let did = ty::WithOptConstParam::unknown(assoc_def.item.def_id);
+                let kind =
+                    ty::ConstKind::Unevaluated(ty::UnevaluatedConst::new(did, identity_substs));
+                ty.map_bound(|ty| tcx.mk_const(kind, ty).into())
+            } else {
+                ty.map_bound(|ty| ty.into())
+            };
+
+            // The term of our goal should be fully unconstrained, so this should never fail.
+            //
+            // It can however be ambiguous when the resolved type is a projection.
+            let nested_goals = ecx
+                .infcx
+                .eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs))
+                .expect("failed to unify with unconstrained term");
+            let rhs_certainty =
+                ecx.evaluate_all(nested_goals).expect("failed to unify with unconstrained term");
+
+            ecx.make_canonical_response(trait_ref_certainty.unify_and(rhs_certainty))
+        })
+    }
+
+    fn consider_assumption(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx> {
+        if let Some(poly_projection_pred) = assumption.to_opt_poly_projection_pred() {
+            ecx.infcx.probe(|_| {
+                let assumption_projection_pred =
+                    ecx.infcx.instantiate_bound_vars_with_infer(poly_projection_pred);
+                let nested_goals = ecx.infcx.eq(
+                    goal.param_env,
+                    goal.predicate.projection_ty,
+                    assumption_projection_pred.projection_ty,
+                )?;
+                let subst_certainty = ecx.evaluate_all(nested_goals)?;
+
+                // The term of our goal should be fully unconstrained, so this should never fail.
+                //
+                // It can however be ambiguous when the resolved type is a projection.
+                let nested_goals = ecx
+                    .infcx
+                    .eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)
+                    .expect("failed to unify with unconstrained term");
+                let rhs_certainty = ecx
+                    .evaluate_all(nested_goals)
+                    .expect("failed to unify with unconstrained term");
+
+                ecx.make_canonical_response(subst_certainty.unify_and(rhs_certainty))
+            })
+        } else {
+            Err(NoSolution)
+        }
+    }
+
+    fn consider_auto_trait_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("auto traits do not have associated types: {:?}", goal);
+    }
+
+    fn consider_trait_alias_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("trait aliases do not have associated types: {:?}", goal);
+    }
+
+    fn consider_builtin_sized_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`Sized` does not have an associated type: {:?}", goal);
+    }
+
+    fn consider_builtin_copy_clone_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`Copy`/`Clone` does not have an associated type: {:?}", goal);
+    }
+
+    fn consider_builtin_pointer_sized_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`PointerSized` does not have an associated type: {:?}", goal);
+    }
+
+    fn consider_builtin_fn_trait_candidates(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        goal_kind: ty::ClosureKind,
+    ) -> QueryResult<'tcx> {
+        if let Some(tupled_inputs_and_output) =
+            structural_traits::extract_tupled_inputs_and_output_from_callable(
+                ecx.tcx(),
+                goal.predicate.self_ty(),
+                goal_kind,
+            )?
+        {
+            let pred = tupled_inputs_and_output
+                .map_bound(|(inputs, output)| ty::ProjectionPredicate {
+                    projection_ty: ecx
+                        .tcx()
+                        .mk_alias_ty(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]),
+                    term: output.into(),
+                })
+                .to_predicate(ecx.tcx());
+            Self::consider_assumption(ecx, goal, pred)
+        } else {
+            ecx.make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity))
+        }
+    }
+
+    fn consider_builtin_tuple_candidate(
+        _ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        bug!("`Tuple` does not have an associated type: {:?}", goal);
+    }
+}
+
+/// This behavior is also implemented in `rustc_ty_utils` and in the old `project` code.
+///
+/// FIXME: We should merge these 3 implementations as it's likely that they otherwise
+/// diverge.
+#[instrument(level = "debug", skip(infcx, param_env), ret)]
+fn fetch_eligible_assoc_item_def<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    goal_trait_ref: ty::TraitRef<'tcx>,
+    trait_assoc_def_id: DefId,
+    impl_def_id: DefId,
+) -> Result<Option<LeafDef>, NoSolution> {
+    let node_item = specialization_graph::assoc_def(infcx.tcx, impl_def_id, trait_assoc_def_id)
+        .map_err(|ErrorGuaranteed { .. }| NoSolution)?;
+
+    let eligible = if node_item.is_final() {
+        // Non-specializable items are always projectable.
+        true
+    } else {
+        // Only reveal a specializable default if we're past type-checking
+        // and the obligation is monomorphic, otherwise passes such as
+        // transmute checking and polymorphic MIR optimizations could
+        // get a result which isn't correct for all monomorphizations.
+        if param_env.reveal() == Reveal::All {
+            let poly_trait_ref = infcx.resolve_vars_if_possible(goal_trait_ref);
+            !poly_trait_ref.still_further_specializable()
+        } else {
+            debug!(?node_item.item.def_id, "not eligible due to default");
+            false
+        }
+    };
+
+    if eligible { Ok(Some(node_item)) } else { Ok(None) }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
new file mode 100644
index 000000000..730a8e612
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs
@@ -0,0 +1,123 @@
+//! This module both handles the global cache which stores "finished" goals,
+//! and the provisional cache which contains partially computed goals.
+//!
+//! The provisional cache is necessary when dealing with coinductive cycles.
+//!
+//! For more information about the provisional cache and coinduction in general,
+//! check out the relevant section of the rustc-dev-guide.
+//!
+//! FIXME(@lcnr): Write that section, feel free to ping me if you need help here
+//! before then or if I still haven't done that before January 2023.
+use super::overflow::OverflowData;
+use super::StackDepth;
+use crate::solve::{CanonicalGoal, QueryResult};
+use rustc_data_structures::fx::FxHashMap;
+use rustc_index::vec::IndexVec;
+use rustc_middle::ty::TyCtxt;
+
+rustc_index::newtype_index! {
+    pub struct EntryIndex {}
+}
+
+#[derive(Debug, Clone)]
+pub(super) struct ProvisionalEntry<'tcx> {
+    // In case we have a coinductive cycle, this is the
+    // the currently least restrictive result of this goal.
+    pub(super) response: QueryResult<'tcx>,
+    // In case of a cycle, the position of deepest stack entry involved
+    // in that cycle. This is monotonically decreasing in the stack as all
+    // elements between the current stack element in the deepest stack entry
+    // involved have to also be involved in that cycle.
+    //
+    // We can only move entries to the global cache once we're complete done
+    // with the cycle. If this entry has not been involved in a cycle,
+    // this is just its own depth.
+    pub(super) depth: StackDepth,
+
+    // The goal for this entry. Should always be equal to the corresponding goal
+    // in the lookup table.
+    pub(super) goal: CanonicalGoal<'tcx>,
+}
+
+pub(super) struct ProvisionalCache<'tcx> {
+    pub(super) entries: IndexVec<EntryIndex, ProvisionalEntry<'tcx>>,
+    // FIXME: This is only used to quickly check whether a given goal
+    // is in the cache. We should experiment with using something like
+    // `SsoHashSet` here because in most cases there are only a few entries.
+    pub(super) lookup_table: FxHashMap<CanonicalGoal<'tcx>, EntryIndex>,
+}
+
+impl<'tcx> ProvisionalCache<'tcx> {
+    pub(super) fn empty() -> ProvisionalCache<'tcx> {
+        ProvisionalCache { entries: Default::default(), lookup_table: Default::default() }
+    }
+
+    pub(super) fn is_empty(&self) -> bool {
+        self.entries.is_empty() && self.lookup_table.is_empty()
+    }
+
+    /// Adds a dependency from the current leaf to `target` in the cache
+    /// to prevent us from moving any goals which depend on the current leaf
+    /// to the global cache while we're still computing `target`.
+    ///
+    /// Its important to note that `target` may already be part of a different cycle.
+    /// In this case we have to ensure that we also depend on all other goals
+    /// in the existing cycle in addition to the potentially direct cycle with `target`.
+    pub(super) fn add_dependency_of_leaf_on(&mut self, target: EntryIndex) {
+        let depth = self.entries[target].depth;
+        for provisional_entry in &mut self.entries.raw[target.index()..] {
+            // The depth of `target` is the position of the deepest goal in the stack
+            // on which `target` depends. That goal is the `root` of this cycle.
+            //
+            // Any entry which was added after `target` is either on the stack itself
+            // at which point its depth is definitely at least as high as the depth of
+            // `root`. If it's not on the stack itself it has to depend on a goal
+            // between `root` and `leaf`. If it were to depend on a goal deeper in the
+            // stack than `root`, then `root` would also depend on that goal, at which
+            // point `root` wouldn't be the root anymore.
+            debug_assert!(provisional_entry.depth >= depth);
+            provisional_entry.depth = depth;
+        }
+
+        // We only update entries which were added after `target` as no other
+        // entry should have a higher depth.
+        //
+        // Any entry which previously had a higher depth than target has to
+        // be between `target` and `root`. Because of this we would have updated
+        // its depth when calling `add_dependency_of_leaf_on(root)` for `target`.
+        if cfg!(debug_assertions) {
+            self.entries.iter().all(|e| e.depth <= depth);
+        }
+    }
+
+    pub(super) fn depth(&self, entry_index: EntryIndex) -> StackDepth {
+        self.entries[entry_index].depth
+    }
+
+    pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> QueryResult<'tcx> {
+        self.entries[entry_index].response.clone()
+    }
+}
+
+pub(super) fn try_move_finished_goal_to_global_cache<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    overflow_data: &mut OverflowData,
+    stack: &IndexVec<super::StackDepth, super::StackElem<'tcx>>,
+    goal: CanonicalGoal<'tcx>,
+    response: QueryResult<'tcx>,
+) {
+    // We move goals to the global cache if we either did not hit an overflow or if it's
+    // the root goal as that will now always hit the same overflow limit.
+    //
+    // NOTE: We cannot move any non-root goals to the global cache even if their final result
+    // isn't impacted by the overflow as that goal still has unstable query dependencies
+    // because it didn't go its full depth.
+    //
+    // FIXME(@lcnr): We could still cache subtrees which are not impacted by overflow though.
+    // Tracking that info correctly isn't trivial, so I haven't implemented it for now.
+    let should_cache_globally = !overflow_data.did_overflow() || stack.is_empty();
+    if should_cache_globally {
+        // FIXME: move the provisional entry to the global cache.
+        let _ = (tcx, goal, response);
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
new file mode 100644
index 000000000..0030e9aa3
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs
@@ -0,0 +1,178 @@
+mod cache;
+mod overflow;
+
+use self::cache::ProvisionalEntry;
+use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult};
+use cache::ProvisionalCache;
+use overflow::OverflowData;
+use rustc_index::vec::IndexVec;
+use rustc_middle::ty::TyCtxt;
+use std::collections::hash_map::Entry;
+
+rustc_index::newtype_index! {
+    pub struct StackDepth {}
+}
+
+struct StackElem<'tcx> {
+    goal: CanonicalGoal<'tcx>,
+    has_been_used: bool,
+}
+
+pub(super) struct SearchGraph<'tcx> {
+    /// The stack of goals currently being computed.
+    ///
+    /// An element is *deeper* in the stack if its index is *lower*.
+    stack: IndexVec<StackDepth, StackElem<'tcx>>,
+    overflow_data: OverflowData,
+    provisional_cache: ProvisionalCache<'tcx>,
+}
+
+impl<'tcx> SearchGraph<'tcx> {
+    pub(super) fn new(tcx: TyCtxt<'tcx>) -> SearchGraph<'tcx> {
+        Self {
+            stack: Default::default(),
+            overflow_data: OverflowData::new(tcx),
+            provisional_cache: ProvisionalCache::empty(),
+        }
+    }
+
+    pub(super) fn is_empty(&self) -> bool {
+        self.stack.is_empty()
+            && self.provisional_cache.is_empty()
+            && !self.overflow_data.did_overflow()
+    }
+
+    /// Tries putting the new goal on the stack, returning an error if it is already cached.
+    ///
+    /// This correctly updates the provisional cache if there is a cycle.
+    pub(super) fn try_push_stack(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        goal: CanonicalGoal<'tcx>,
+    ) -> Result<(), QueryResult<'tcx>> {
+        // FIXME: start by checking the global cache
+
+        // Look at the provisional cache to check for cycles.
+        let cache = &mut self.provisional_cache;
+        match cache.lookup_table.entry(goal) {
+            // No entry, simply push this goal on the stack after dealing with overflow.
+            Entry::Vacant(v) => {
+                if self.overflow_data.has_overflow(self.stack.len()) {
+                    return Err(self.deal_with_overflow(tcx, goal));
+                }
+
+                let depth = self.stack.push(StackElem { goal, has_been_used: false });
+                let response = super::response_no_constraints(tcx, goal, Certainty::Yes);
+                let entry_index = cache.entries.push(ProvisionalEntry { response, depth, goal });
+                v.insert(entry_index);
+                Ok(())
+            }
+            // We have a nested goal which relies on a goal `root` deeper in the stack.
+            //
+            // We first store that we may have to rerun `evaluate_goal` for `root` in case the
+            // provisional response is not equal to the final response. We also update the depth
+            // of all goals which recursively depend on our current goal to depend on `root`
+            // instead.
+            //
+            // Finally we can return either the provisional response for that goal if we have a
+            // coinductive cycle or an ambiguous result if the cycle is inductive.
+            Entry::Occupied(entry_index) => {
+                let entry_index = *entry_index.get();
+
+                cache.add_dependency_of_leaf_on(entry_index);
+                let stack_depth = cache.depth(entry_index);
+
+                self.stack[stack_depth].has_been_used = true;
+                // NOTE: The goals on the stack aren't the only goals involved in this cycle.
+                // We can also depend on goals which aren't part of the stack but coinductively
+                // depend on the stack themselves. We already checked whether all the goals
+                // between these goals and their root on the stack. This means that as long as
+                // each goal in a cycle is checked for coinductivity by itself, simply checking
+                // the stack is enough.
+                if self.stack.raw[stack_depth.index()..]
+                    .iter()
+                    .all(|g| g.goal.value.predicate.is_coinductive(tcx))
+                {
+                    Err(cache.provisional_result(entry_index))
+                } else {
+                    Err(super::response_no_constraints(
+                        tcx,
+                        goal,
+                        Certainty::Maybe(MaybeCause::Overflow),
+                    ))
+                }
+            }
+        }
+    }
+
+    /// We cannot simply store the result of [super::EvalCtxt::compute_goal] as we have to deal with
+    /// coinductive cycles.
+    ///
+    /// When we encounter a coinductive cycle, we have to prove the final result of that cycle
+    /// while we are still computing that result. Because of this we continously recompute the
+    /// cycle until the result of the previous iteration is equal to the final result, at which
+    /// point we are done.
+    ///
+    /// This function returns `true` if we were able to finalize the goal and `false` if it has
+    /// updated the provisional cache and we have to recompute the current goal.
+    ///
+    /// FIXME: Refer to the rustc-dev-guide entry once it exists.
+    pub(super) fn try_finalize_goal(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        actual_goal: CanonicalGoal<'tcx>,
+        response: QueryResult<'tcx>,
+    ) -> bool {
+        let StackElem { goal, has_been_used } = self.stack.pop().unwrap();
+        assert_eq!(goal, actual_goal);
+
+        let cache = &mut self.provisional_cache;
+        let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap();
+        let provisional_entry = &mut cache.entries[provisional_entry_index];
+        let depth = provisional_entry.depth;
+        // Was the current goal the root of a cycle and was the provisional response
+        // different from the final one.
+        if has_been_used && provisional_entry.response != response {
+            // If so, update the provisional reponse for this goal...
+            provisional_entry.response = response;
+            // ...remove all entries whose result depends on this goal
+            // from the provisional cache...
+            //
+            // That's not completely correct, as a nested goal can also
+            // depend on a goal which is lower in the stack so it doesn't
+            // actually depend on the current goal. This should be fairly
+            // rare and is hopefully not relevant for performance.
+            #[allow(rustc::potential_query_instability)]
+            cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index);
+            cache.entries.truncate(provisional_entry_index.index() + 1);
+
+            // ...and finally push our goal back on the stack and reevaluate it.
+            self.stack.push(StackElem { goal, has_been_used: false });
+            false
+        } else {
+            // If not, we're done with this goal.
+            //
+            // Check whether that this goal doesn't depend on a goal deeper on the stack
+            // and if so, move it and all nested goals to the global cache.
+            //
+            // Note that if any nested goal were to depend on something deeper on the stack,
+            // this would have also updated the depth of the current goal.
+            if depth == self.stack.next_index() {
+                for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..)
+                {
+                    let actual_index = cache.lookup_table.remove(&entry.goal);
+                    debug_assert_eq!(Some(i), actual_index);
+                    debug_assert!(entry.depth == depth);
+                    cache::try_move_finished_goal_to_global_cache(
+                        tcx,
+                        &mut self.overflow_data,
+                        &self.stack,
+                        entry.goal,
+                        entry.response,
+                    );
+                }
+            }
+            true
+        }
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
new file mode 100644
index 000000000..1dd3894c9
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs
@@ -0,0 +1,84 @@
+use rustc_infer::infer::canonical::Canonical;
+use rustc_infer::traits::query::NoSolution;
+use rustc_middle::ty::TyCtxt;
+use rustc_session::Limit;
+
+use super::SearchGraph;
+use crate::solve::{response_no_constraints, Certainty, EvalCtxt, MaybeCause, QueryResult};
+
+/// When detecting a solver overflow, we return ambiguity. Overflow can be
+/// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**.
+///
+/// This is in issue in case of exponential blowup, e.g. if each goal on the stack
+/// has multiple nested (overflowing) candidates. To deal with this, we reduce the limit
+/// used by the solver when hitting the default limit for the first time.
+///
+/// FIXME: Get tests where always using the `default_limit` results in a hang and refer
+/// to them here. We can also improve the overflow strategy if necessary.
+pub(super) struct OverflowData {
+    default_limit: Limit,
+    current_limit: Limit,
+    /// When proving an **AND** we have to repeatedly iterate over the yet unproven goals.
+    ///
+    /// Because of this each iteration also increases the depth in addition to the stack
+    /// depth.
+    additional_depth: usize,
+}
+
+impl OverflowData {
+    pub(super) fn new(tcx: TyCtxt<'_>) -> OverflowData {
+        let default_limit = tcx.recursion_limit();
+        OverflowData { default_limit, current_limit: default_limit, additional_depth: 0 }
+    }
+
+    #[inline]
+    pub(super) fn did_overflow(&self) -> bool {
+        self.default_limit.0 != self.current_limit.0
+    }
+
+    #[inline]
+    pub(super) fn has_overflow(&self, depth: usize) -> bool {
+        !self.current_limit.value_within_limit(depth + self.additional_depth)
+    }
+
+    /// Updating the current limit when hitting overflow.
+    fn deal_with_overflow(&mut self) {
+        // When first hitting overflow we reduce the overflow limit
+        // for all future goals to prevent hangs if there's an exponental
+        // blowup.
+        self.current_limit.0 = self.default_limit.0 / 8;
+    }
+}
+
+impl<'tcx> SearchGraph<'tcx> {
+    pub fn deal_with_overflow(
+        &mut self,
+        tcx: TyCtxt<'tcx>,
+        goal: Canonical<'tcx, impl Sized>,
+    ) -> QueryResult<'tcx> {
+        self.overflow_data.deal_with_overflow();
+        response_no_constraints(tcx, goal, Certainty::Maybe(MaybeCause::Overflow))
+    }
+}
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    /// A `while`-loop which tracks overflow.
+    pub fn repeat_while_none(
+        &mut self,
+        mut loop_body: impl FnMut(&mut Self) -> Option<Result<Certainty, NoSolution>>,
+    ) -> Result<Certainty, NoSolution> {
+        let start_depth = self.search_graph.overflow_data.additional_depth;
+        let depth = self.search_graph.stack.len();
+        while !self.search_graph.overflow_data.has_overflow(depth) {
+            if let Some(result) = loop_body(self) {
+                self.search_graph.overflow_data.additional_depth = start_depth;
+                return result;
+            }
+
+            self.search_graph.overflow_data.additional_depth += 1;
+        }
+        self.search_graph.overflow_data.additional_depth = start_depth;
+        self.search_graph.overflow_data.deal_with_overflow();
+        Ok(Certainty::Maybe(MaybeCause::Overflow))
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
new file mode 100644
index 000000000..9985d7181
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -0,0 +1,289 @@
+//! Dealing with trait goals, i.e. `T: Trait<'a, U>`.
+
+use std::iter;
+
+use super::assembly::{self, Candidate, CandidateSource};
+use super::infcx_ext::InferCtxtExt;
+use super::{Certainty, EvalCtxt, Goal, MaybeCause, QueryResult};
+use rustc_hir::def_id::DefId;
+use rustc_infer::infer::InferCtxt;
+use rustc_infer::traits::query::NoSolution;
+use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
+use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
+use rustc_middle::ty::{TraitPredicate, TypeVisitable};
+use rustc_span::DUMMY_SP;
+
+pub mod structural_traits;
+
+impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
+    fn self_ty(self) -> Ty<'tcx> {
+        self.self_ty()
+    }
+
+    fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self {
+        self.with_self_ty(tcx, self_ty)
+    }
+
+    fn trait_def_id(self, _: TyCtxt<'tcx>) -> DefId {
+        self.def_id()
+    }
+
+    fn consider_impl_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, TraitPredicate<'tcx>>,
+        impl_def_id: DefId,
+    ) -> QueryResult<'tcx> {
+        let tcx = ecx.tcx();
+
+        let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
+        let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder };
+        if iter::zip(goal.predicate.trait_ref.substs, impl_trait_ref.skip_binder().substs)
+            .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp))
+        {
+            return Err(NoSolution);
+        }
+
+        ecx.infcx.probe(|_| {
+            let impl_substs = ecx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id);
+            let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
+
+            let mut nested_goals =
+                ecx.infcx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?;
+            let where_clause_bounds = tcx
+                .predicates_of(impl_def_id)
+                .instantiate(tcx, impl_substs)
+                .predicates
+                .into_iter()
+                .map(|pred| goal.with(tcx, pred));
+            nested_goals.extend(where_clause_bounds);
+            ecx.evaluate_all_and_make_canonical_response(nested_goals)
+        })
+    }
+
+    fn consider_assumption(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        assumption: ty::Predicate<'tcx>,
+    ) -> QueryResult<'tcx> {
+        if let Some(poly_trait_pred) = assumption.to_opt_poly_trait_pred() {
+            // FIXME: Constness and polarity
+            ecx.infcx.probe(|_| {
+                let assumption_trait_pred =
+                    ecx.infcx.instantiate_bound_vars_with_infer(poly_trait_pred);
+                let nested_goals = ecx.infcx.eq(
+                    goal.param_env,
+                    goal.predicate.trait_ref,
+                    assumption_trait_pred.trait_ref,
+                )?;
+                ecx.evaluate_all_and_make_canonical_response(nested_goals)
+            })
+        } else {
+            Err(NoSolution)
+        }
+    }
+
+    fn consider_auto_trait_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            goal,
+            structural_traits::instantiate_constituent_tys_for_auto_trait,
+        )
+    }
+
+    fn consider_trait_alias_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        let tcx = ecx.tcx();
+
+        ecx.infcx.probe(|_| {
+            let nested_obligations = tcx
+                .predicates_of(goal.predicate.def_id())
+                .instantiate(tcx, goal.predicate.trait_ref.substs);
+            ecx.evaluate_all_and_make_canonical_response(
+                nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(),
+            )
+        })
+    }
+
+    fn consider_builtin_sized_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            goal,
+            structural_traits::instantiate_constituent_tys_for_sized_trait,
+        )
+    }
+
+    fn consider_builtin_copy_clone_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        ecx.probe_and_evaluate_goal_for_constituent_tys(
+            goal,
+            structural_traits::instantiate_constituent_tys_for_copy_clone_trait,
+        )
+    }
+
+    fn consider_builtin_pointer_sized_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        if goal.predicate.self_ty().has_non_region_infer() {
+            return ecx.make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity));
+        }
+
+        let tcx = ecx.tcx();
+        let self_ty = tcx.erase_regions(goal.predicate.self_ty());
+
+        if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty))
+            &&  let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout
+            && layout.layout.size() == usize_layout.size()
+            && layout.layout.align().abi == usize_layout.align().abi
+        {
+            // FIXME: We could make this faster by making a no-constraints response
+            ecx.make_canonical_response(Certainty::Yes)
+        } else {
+            Err(NoSolution)
+        }
+    }
+
+    fn consider_builtin_fn_trait_candidates(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+        goal_kind: ty::ClosureKind,
+    ) -> QueryResult<'tcx> {
+        if let Some(tupled_inputs_and_output) =
+            structural_traits::extract_tupled_inputs_and_output_from_callable(
+                ecx.tcx(),
+                goal.predicate.self_ty(),
+                goal_kind,
+            )?
+        {
+            let pred = tupled_inputs_and_output
+                .map_bound(|(inputs, _)| {
+                    ecx.tcx()
+                        .mk_trait_ref(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs])
+                })
+                .to_predicate(ecx.tcx());
+            Self::consider_assumption(ecx, goal, pred)
+        } else {
+            ecx.make_canonical_response(Certainty::Maybe(MaybeCause::Ambiguity))
+        }
+    }
+
+    fn consider_builtin_tuple_candidate(
+        ecx: &mut EvalCtxt<'_, 'tcx>,
+        goal: Goal<'tcx, Self>,
+    ) -> QueryResult<'tcx> {
+        if let ty::Tuple(..) = goal.predicate.self_ty().kind() {
+            ecx.make_canonical_response(Certainty::Yes)
+        } else {
+            Err(NoSolution)
+        }
+    }
+}
+
+impl<'tcx> EvalCtxt<'_, 'tcx> {
+    /// Convenience function for traits that are structural, i.e. that only
+    /// have nested subgoals that only change the self type. Unlike other
+    /// evaluate-like helpers, this does a probe, so it doesn't need to be
+    /// wrapped in one.
+    fn probe_and_evaluate_goal_for_constituent_tys(
+        &mut self,
+        goal: Goal<'tcx, TraitPredicate<'tcx>>,
+        constituent_tys: impl Fn(&InferCtxt<'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
+    ) -> QueryResult<'tcx> {
+        self.infcx.probe(|_| {
+            self.evaluate_all_and_make_canonical_response(
+                constituent_tys(self.infcx, goal.predicate.self_ty())?
+                    .into_iter()
+                    .map(|ty| {
+                        goal.with(
+                            self.tcx(),
+                            ty::Binder::dummy(goal.predicate.with_self_ty(self.tcx(), ty)),
+                        )
+                    })
+                    .collect(),
+            )
+        })
+    }
+
+    pub(super) fn compute_trait_goal(
+        &mut self,
+        goal: Goal<'tcx, TraitPredicate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        let candidates = self.assemble_and_evaluate_candidates(goal);
+        self.merge_trait_candidates_discard_reservation_impls(candidates)
+    }
+
+    #[instrument(level = "debug", skip(self), ret)]
+    pub(super) fn merge_trait_candidates_discard_reservation_impls(
+        &mut self,
+        mut candidates: Vec<Candidate<'tcx>>,
+    ) -> QueryResult<'tcx> {
+        match candidates.len() {
+            0 => return Err(NoSolution),
+            1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result),
+            _ => {}
+        }
+
+        if candidates.len() > 1 {
+            let mut i = 0;
+            'outer: while i < candidates.len() {
+                for j in (0..candidates.len()).filter(|&j| i != j) {
+                    if self.trait_candidate_should_be_dropped_in_favor_of(
+                        &candidates[i],
+                        &candidates[j],
+                    ) {
+                        debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len());
+                        candidates.swap_remove(i);
+                        continue 'outer;
+                    }
+                }
+
+                debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len());
+                // If there are *STILL* multiple candidates, give up
+                // and report ambiguity.
+                i += 1;
+                if i > 1 {
+                    debug!("multiple matches, ambig");
+                    // FIXME: return overflow if all candidates overflow, otherwise return ambiguity.
+                    unimplemented!();
+                }
+            }
+        }
+
+        Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result)
+    }
+
+    fn trait_candidate_should_be_dropped_in_favor_of(
+        &self,
+        candidate: &Candidate<'tcx>,
+        other: &Candidate<'tcx>,
+    ) -> bool {
+        // FIXME: implement this
+        match (candidate.source, other.source) {
+            (CandidateSource::Impl(_), _)
+            | (CandidateSource::ParamEnv(_), _)
+            | (CandidateSource::AliasBound(_), _)
+            | (CandidateSource::BuiltinImpl, _) => unimplemented!(),
+        }
+    }
+
+    fn discard_reservation_impl(&self, candidate: Candidate<'tcx>) -> Candidate<'tcx> {
+        if let CandidateSource::Impl(def_id) = candidate.source {
+            if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) {
+                debug!("Selected reservation impl");
+                // FIXME: reduce candidate to ambiguous
+                // FIXME: replace `var_values` with identity, yeet external constraints.
+                unimplemented!()
+            }
+        }
+
+        candidate
+    }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
new file mode 100644
index 000000000..a11cd13cb
--- /dev/null
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs
@@ -0,0 +1,223 @@
+use rustc_hir::{Movability, Mutability};
+use rustc_infer::{infer::InferCtxt, traits::query::NoSolution};
+use rustc_middle::ty::{self, Ty, TyCtxt};
+
+// Calculates the constituent types of a type for `auto trait` purposes.
+//
+// For types with an "existential" binder, i.e. generator witnesses, we also
+// instantiate the binder with placeholders eagerly.
+pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<Ty<'tcx>>, NoSolution> {
+    let tcx = infcx.tcx;
+    match *ty.kind() {
+        ty::Uint(_)
+        | ty::Int(_)
+        | ty::Bool
+        | ty::Float(_)
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::Str
+        | ty::Error(_)
+        | ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+        | ty::Never
+        | ty::Char => Ok(vec![]),
+
+        ty::Placeholder(..)
+        | ty::Dynamic(..)
+        | ty::Param(..)
+        | ty::Foreign(..)
+        | ty::Alias(ty::Projection, ..)
+        | ty::Bound(..)
+        | ty::Infer(ty::TyVar(_)) => Err(NoSolution),
+
+        ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(),
+
+        ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => {
+            Ok(vec![element_ty])
+        }
+
+        ty::Array(element_ty, _) | ty::Slice(element_ty) => Ok(vec![element_ty]),
+
+        ty::Tuple(ref tys) => {
+            // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
+            Ok(tys.iter().collect())
+        }
+
+        ty::Closure(_, ref substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]),
+
+        ty::Generator(_, ref substs, _) => {
+            let generator_substs = substs.as_generator();
+            Ok(vec![generator_substs.tupled_upvars_ty(), generator_substs.witness()])
+        }
+
+        ty::GeneratorWitness(types) => {
+            Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec())
+        }
+
+        // For `PhantomData<T>`, we pass `T`.
+        ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]),
+
+        ty::Adt(def, substs) => Ok(def.all_fields().map(|f| f.ty(tcx, substs)).collect()),
+
+        ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) => {
+            // We can resolve the `impl Trait` to its concrete type,
+            // which enforces a DAG between the functions requiring
+            // the auto trait bounds in question.
+            Ok(vec![tcx.bound_type_of(def_id).subst(tcx, substs)])
+        }
+    }
+}
+
+pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<Ty<'tcx>>, NoSolution> {
+    match *ty.kind() {
+        ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+        | ty::Uint(_)
+        | ty::Int(_)
+        | ty::Bool
+        | ty::Float(_)
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::RawPtr(..)
+        | ty::Char
+        | ty::Ref(..)
+        | ty::Generator(..)
+        | ty::GeneratorWitness(..)
+        | ty::Array(..)
+        | ty::Closure(..)
+        | ty::Never
+        | ty::Dynamic(_, _, ty::DynStar)
+        | ty::Error(_) => Ok(vec![]),
+
+        ty::Str
+        | ty::Slice(_)
+        | ty::Dynamic(..)
+        | ty::Foreign(..)
+        | ty::Alias(..)
+        | ty::Param(_)
+        | ty::Infer(ty::TyVar(_)) => Err(NoSolution),
+
+        ty::Placeholder(..)
+        | ty::Bound(..)
+        | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(),
+
+        ty::Tuple(tys) => Ok(tys.to_vec()),
+
+        ty::Adt(def, substs) => {
+            let sized_crit = def.sized_constraint(infcx.tcx);
+            Ok(sized_crit
+                .0
+                .iter()
+                .map(|ty| sized_crit.rebind(*ty).subst(infcx.tcx, substs))
+                .collect())
+        }
+    }
+}
+
+pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    ty: Ty<'tcx>,
+) -> Result<Vec<Ty<'tcx>>, NoSolution> {
+    match *ty.kind() {
+        ty::Infer(ty::IntVar(_) | ty::FloatVar(_))
+        | ty::FnDef(..)
+        | ty::FnPtr(_)
+        | ty::Error(_) => Ok(vec![]),
+
+        // Implementations are provided in core
+        ty::Uint(_)
+        | ty::Int(_)
+        | ty::Bool
+        | ty::Float(_)
+        | ty::Char
+        | ty::RawPtr(..)
+        | ty::Never
+        | ty::Ref(_, _, Mutability::Not)
+        | ty::Array(..) => Err(NoSolution),
+
+        ty::Dynamic(..)
+        | ty::Str
+        | ty::Slice(_)
+        | ty::Generator(_, _, Movability::Static)
+        | ty::Foreign(..)
+        | ty::Ref(_, _, Mutability::Mut)
+        | ty::Adt(_, _)
+        | ty::Alias(_, _)
+        | ty::Param(_)
+        | ty::Infer(ty::TyVar(_)) => Err(NoSolution),
+
+        ty::Placeholder(..)
+        | ty::Bound(..)
+        | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => bug!(),
+
+        ty::Tuple(tys) => Ok(tys.to_vec()),
+
+        ty::Closure(_, substs) => Ok(vec![substs.as_closure().tupled_upvars_ty()]),
+
+        ty::Generator(_, substs, Movability::Movable) => {
+            if infcx.tcx.features().generator_clone {
+                let generator = substs.as_generator();
+                Ok(vec![generator.tupled_upvars_ty(), generator.witness()])
+            } else {
+                Err(NoSolution)
+            }
+        }
+
+        ty::GeneratorWitness(types) => {
+            Ok(infcx.replace_bound_vars_with_placeholders(types).to_vec())
+        }
+    }
+}
+
+pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    self_ty: Ty<'tcx>,
+    goal_kind: ty::ClosureKind,
+) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> {
+    match *self_ty.kind() {
+        ty::FnDef(def_id, substs) => Ok(Some(
+            tcx.bound_fn_sig(def_id)
+                .subst(tcx, substs)
+                .map_bound(|sig| (tcx.mk_tup(sig.inputs().iter()), sig.output())),
+        )),
+        ty::FnPtr(sig) => {
+            Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs().iter()), sig.output()))))
+        }
+        ty::Closure(_, substs) => {
+            let closure_substs = substs.as_closure();
+            match closure_substs.kind_ty().to_opt_closure_kind() {
+                Some(closure_kind) if closure_kind.extends(goal_kind) => {}
+                None => return Ok(None),
+                _ => return Err(NoSolution),
+            }
+            Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output()))))
+        }
+        ty::Bool
+        | ty::Char
+        | ty::Int(_)
+        | ty::Uint(_)
+        | ty::Float(_)
+        | ty::Adt(_, _)
+        | ty::Foreign(_)
+        | ty::Str
+        | ty::Array(_, _)
+        | ty::Slice(_)
+        | ty::RawPtr(_)
+        | ty::Ref(_, _, _)
+        | ty::Dynamic(_, _, _)
+        | ty::Generator(_, _, _)
+        | ty::GeneratorWitness(_)
+        | ty::Never
+        | ty::Tuple(_)
+        | ty::Alias(_, _)
+        | ty::Param(_)
+        | ty::Placeholder(_)
+        | ty::Bound(_, _)
+        | ty::Infer(_)
+        | ty::Error(_) => Err(NoSolution),
+    }
+}