Auto merge of #3363 - RalfJung:rustup, r=RalfJung

Rustup

This should finally work again :)

26 files changed, 548 insertions, 382 deletions

diff --git a/compiler/rustc_trait_selection/src/errors.rs b/compiler/rustc_trait_selection/src/errors.rs
index 95667de79a6..e37640d0689 100644
--- a/compiler/rustc_trait_selection/src/errors.rs
+++ b/compiler/rustc_trait_selection/src/errors.rs
@@ -1,7 +1,7 @@
 use crate::fluent_generated as fluent;
 use rustc_errors::{
     codes::*, AddToDiagnostic, Applicability, Diag, DiagCtxt, EmissionGuarantee, IntoDiagnostic,
-    Level, SubdiagnosticMessageOp,
+    Level, SubdiagMessageOp,
 };
 use rustc_macros::Diagnostic;
 use rustc_middle::ty::{self, ClosureKind, PolyTraitRef, Ty};
@@ -101,7 +101,7 @@ pub enum AdjustSignatureBorrow {
 }
 
 impl AddToDiagnostic for AdjustSignatureBorrow {
-    fn add_to_diagnostic_with<G: EmissionGuarantee, F: SubdiagnosticMessageOp<G>>(
+    fn add_to_diagnostic_with<G: EmissionGuarantee, F: SubdiagMessageOp<G>>(
         self,
         diag: &mut Diag<'_, G>,
         _f: F,
diff --git a/compiler/rustc_trait_selection/src/lib.rs b/compiler/rustc_trait_selection/src/lib.rs
index 00a2adccf64..fd3d62d1321 100644
--- a/compiler/rustc_trait_selection/src/lib.rs
+++ b/compiler/rustc_trait_selection/src/lib.rs
@@ -16,7 +16,9 @@
 #![allow(internal_features)]
 #![allow(rustc::diagnostic_outside_of_impl)]
 #![allow(rustc::untranslatable_diagnostic)]
+#![feature(assert_matches)]
 #![feature(associated_type_bounds)]
+#![feature(associated_type_defaults)]
 #![feature(box_patterns)]
 #![feature(control_flow_enum)]
 #![feature(extract_if)]
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
index afd9d95cb57..67657c81cf6 100644
--- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs
+++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
@@ -36,11 +36,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         let Goal { param_env, predicate: (lhs, rhs, direction) } = goal;
 
         let Some(lhs) = self.try_normalize_term(param_env, lhs)? else {
-            return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
+            return self
+                .evaluate_added_goals_and_make_canonical_response(Certainty::overflow(true));
         };
 
         let Some(rhs) = self.try_normalize_term(param_env, rhs)? else {
-            return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW);
+            return self
+                .evaluate_added_goals_and_make_canonical_response(Certainty::overflow(true));
         };
 
         let variance = match direction {
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 4c4cd2af779..3be53a6591d 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -394,10 +394,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
             ty::Infer(ty::FloatVar(_)) => {
                 // This causes a compiler error if any new float kinds are added.
-                let (ty::FloatTy::F32 | ty::FloatTy::F64);
+                let (ty::FloatTy::F16 | ty::FloatTy::F32 | ty::FloatTy::F64 | ty::FloatTy::F128);
                 let possible_floats = [
+                    SimplifiedType::Float(ty::FloatTy::F16),
                     SimplifiedType::Float(ty::FloatTy::F32),
                     SimplifiedType::Float(ty::FloatTy::F64),
+                    SimplifiedType::Float(ty::FloatTy::F128),
                 ];
 
                 for simp in possible_floats {
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
index ed428bb8e66..22f52c27362 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
@@ -7,6 +7,7 @@ use rustc_infer::infer::{
     BoundRegionConversionTime, DefineOpaqueTypes, InferCtxt, InferOk, TyCtxtInferExt,
 };
 use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::solve::MaybeCause;
 use rustc_infer::traits::ObligationCause;
 use rustc_middle::infer::canonical::CanonicalVarInfos;
 use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
@@ -29,7 +30,7 @@ use std::ops::ControlFlow;
 use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment};
 
 use super::inspect::ProofTreeBuilder;
-use super::{search_graph, GoalEvaluationKind};
+use super::{search_graph, GoalEvaluationKind, FIXPOINT_STEP_LIMIT};
 use super::{search_graph::SearchGraph, Goal};
 use super::{GoalSource, SolverMode};
 pub use select::InferCtxtSelectExt;
@@ -154,10 +155,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         self.search_graph.solver_mode()
     }
 
-    pub(super) fn local_overflow_limit(&self) -> usize {
-        self.search_graph.local_overflow_limit()
-    }
-
     /// Creates a root evaluation context and search graph. This should only be
     /// used from outside of any evaluation, and other methods should be preferred
     /// over using this manually (such as [`InferCtxtEvalExt::evaluate_root_goal`]).
@@ -167,7 +164,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> R,
     ) -> (R, Option<inspect::GoalEvaluation<'tcx>>) {
         let mode = if infcx.intercrate { SolverMode::Coherence } else { SolverMode::Normal };
-        let mut search_graph = search_graph::SearchGraph::new(infcx.tcx, mode);
+        let mut search_graph = search_graph::SearchGraph::new(mode);
 
         let mut ecx = EvalCtxt {
             search_graph: &mut search_graph,
@@ -388,16 +385,18 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
                 && source != GoalSource::ImplWhereBound
         };
 
-        if response.value.certainty == Certainty::OVERFLOW && !keep_overflow_constraints() {
-            (Certainty::OVERFLOW, false)
-        } else {
-            let has_changed = !response.value.var_values.is_identity_modulo_regions()
-                || !response.value.external_constraints.opaque_types.is_empty();
-
-            let certainty =
-                self.instantiate_and_apply_query_response(param_env, original_values, response);
-            (certainty, has_changed)
+        if let Certainty::Maybe(MaybeCause::Overflow { .. }) = response.value.certainty
+            && !keep_overflow_constraints()
+        {
+            return (response.value.certainty, false);
         }
+
+        let has_changed = !response.value.var_values.is_identity_modulo_regions()
+            || !response.value.external_constraints.opaque_types.is_empty();
+
+        let certainty =
+            self.instantiate_and_apply_query_response(param_env, original_values, response);
+        (certainty, has_changed)
     }
 
     fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> {
@@ -466,8 +465,8 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         let inspect = self.inspect.new_evaluate_added_goals();
         let inspect = core::mem::replace(&mut self.inspect, inspect);
 
-        let mut response = Ok(Certainty::OVERFLOW);
-        for _ in 0..self.local_overflow_limit() {
+        let mut response = Ok(Certainty::overflow(false));
+        for _ in 0..FIXPOINT_STEP_LIMIT {
             // FIXME: This match is a bit ugly, it might be nice to change the inspect
             // stuff to use a closure instead. which should hopefully simplify this a bit.
             match self.evaluate_added_goals_step() {
@@ -649,8 +648,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         }
 
         impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTermOrNotNameable<'_, 'tcx> {
-            type BreakTy = ();
-            fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+            type Result = ControlFlow<()>;
+            fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
                 match *t.kind() {
                     ty::Infer(ty::TyVar(vid)) => {
                         if let ty::TermKind::Ty(term) = self.term.unpack()
@@ -673,7 +672,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 }
             }
 
-            fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+            fn visit_const(&mut self, c: ty::Const<'tcx>) -> Self::Result {
                 match c.kind() {
                     ty::ConstKind::Infer(ty::InferConst::Var(vid)) => {
                         if let ty::TermKind::Const(term) = self.term.unpack()
@@ -874,7 +873,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
     pub(super) fn is_transmutable(
         &self,
         src_and_dst: rustc_transmute::Types<'tcx>,
-        scope: Ty<'tcx>,
         assume: rustc_transmute::Assume,
     ) -> Result<Certainty, NoSolution> {
         use rustc_transmute::Answer;
@@ -882,7 +880,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable(
             ObligationCause::dummy(),
             src_and_dst,
-            scope,
             assume,
         ) {
             Answer::Yes => Ok(Certainty::Yes),
@@ -906,7 +903,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             &ObligationCause::dummy(),
             param_env,
             hidden_ty,
-            true,
             &mut obligations,
         )?;
         self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into()));
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index c1b07765e50..3fa409eefff 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -24,7 +24,7 @@ use super::{Certainty, InferCtxtEvalExt};
 /// 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>>,
+    obligations: ObligationStorage<'tcx>,
 
     /// The snapshot in which this context was created. Using the context
     /// outside of this snapshot leads to subtle bugs if the snapshot
@@ -33,6 +33,57 @@ pub struct FulfillmentCtxt<'tcx> {
     usable_in_snapshot: usize,
 }
 
+#[derive(Default)]
+struct ObligationStorage<'tcx> {
+    /// Obligations which resulted in an overflow in fulfillment itself.
+    ///
+    /// We cannot eagerly return these as error so we instead store them here
+    /// to avoid recomputing them each time `select_where_possible` is called.
+    /// This also allows us to return the correct `FulfillmentError` for them.
+    overflowed: Vec<PredicateObligation<'tcx>>,
+    pending: Vec<PredicateObligation<'tcx>>,
+}
+
+impl<'tcx> ObligationStorage<'tcx> {
+    fn register(&mut self, obligation: PredicateObligation<'tcx>) {
+        self.pending.push(obligation);
+    }
+
+    fn clone_pending(&self) -> Vec<PredicateObligation<'tcx>> {
+        let mut obligations = self.pending.clone();
+        obligations.extend(self.overflowed.iter().cloned());
+        obligations
+    }
+
+    fn take_pending(&mut self) -> Vec<PredicateObligation<'tcx>> {
+        let mut obligations = mem::take(&mut self.pending);
+        obligations.append(&mut self.overflowed);
+        obligations
+    }
+
+    fn unstalled_for_select(&mut self) -> impl Iterator<Item = PredicateObligation<'tcx>> {
+        mem::take(&mut self.pending).into_iter()
+    }
+
+    fn on_fulfillment_overflow(&mut self, infcx: &InferCtxt<'tcx>) {
+        infcx.probe(|_| {
+            // IMPORTANT: we must not use solve any inference variables in the obligations
+            // as this is all happening inside of a probe. We use a probe to make sure
+            // we get all obligations involved in the overflow. We pretty much check: if
+            // we were to do another step of `select_where_possible`, which goals would
+            // change.
+            self.overflowed.extend(self.pending.extract_if(|o| {
+                let goal = o.clone().into();
+                let result = infcx.evaluate_root_goal(goal, GenerateProofTree::Never).0;
+                match result {
+                    Ok((has_changed, _)) => has_changed,
+                    _ => false,
+                }
+            }));
+        })
+    }
+}
+
 impl<'tcx> FulfillmentCtxt<'tcx> {
     pub fn new(infcx: &InferCtxt<'tcx>) -> FulfillmentCtxt<'tcx> {
         assert!(
@@ -40,7 +91,10 @@ impl<'tcx> FulfillmentCtxt<'tcx> {
             "new trait solver fulfillment context created when \
             infcx is set up for old trait solver"
         );
-        FulfillmentCtxt { obligations: Vec::new(), usable_in_snapshot: infcx.num_open_snapshots() }
+        FulfillmentCtxt {
+            obligations: Default::default(),
+            usable_in_snapshot: infcx.num_open_snapshots(),
+        }
     }
 
     fn inspect_evaluated_obligation(
@@ -67,40 +121,24 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
         obligation: PredicateObligation<'tcx>,
     ) {
         assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
-        self.obligations.push(obligation);
+        self.obligations.register(obligation);
     }
 
     fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
-        self.obligations
+        let mut errors: Vec<_> = self
+            .obligations
+            .pending
             .drain(..)
-            .map(|obligation| {
-                let code = infcx.probe(|_| {
-                    match infcx
-                        .evaluate_root_goal(obligation.clone().into(), GenerateProofTree::IfEnabled)
-                        .0
-                    {
-                        Ok((_, Certainty::Maybe(MaybeCause::Ambiguity))) => {
-                            FulfillmentErrorCode::Ambiguity { overflow: false }
-                        }
-                        Ok((_, Certainty::Maybe(MaybeCause::Overflow))) => {
-                            FulfillmentErrorCode::Ambiguity { overflow: true }
-                        }
-                        Ok((_, Certainty::Yes)) => {
-                            bug!("did not expect successful goal when collecting ambiguity errors")
-                        }
-                        Err(_) => {
-                            bug!("did not expect selection error when collecting ambiguity errors")
-                        }
-                    }
-                });
+            .map(|obligation| fulfillment_error_for_stalled(infcx, obligation))
+            .collect();
 
-                FulfillmentError {
-                    obligation: obligation.clone(),
-                    code,
-                    root_obligation: obligation,
-                }
-            })
-            .collect()
+        errors.extend(self.obligations.overflowed.drain(..).map(|obligation| FulfillmentError {
+            root_obligation: obligation.clone(),
+            code: FulfillmentErrorCode::Ambiguity { overflow: Some(true) },
+            obligation,
+        }));
+
+        errors
     }
 
     fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> {
@@ -108,79 +146,27 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
         let mut errors = Vec::new();
         for i in 0.. {
             if !infcx.tcx.recursion_limit().value_within_limit(i) {
-                // Only return true errors that we have accumulated while processing;
-                // keep ambiguities around, *including overflows*, because they shouldn't
-                // be considered true errors.
+                self.obligations.on_fulfillment_overflow(infcx);
+                // Only return true errors that we have accumulated while processing.
                 return errors;
             }
 
             let mut has_changed = false;
-            for obligation in mem::take(&mut self.obligations) {
+            for obligation in self.obligations.unstalled_for_select() {
                 let goal = obligation.clone().into();
                 let result = infcx.evaluate_root_goal(goal, GenerateProofTree::IfEnabled).0;
                 self.inspect_evaluated_obligation(infcx, &obligation, &result);
                 let (changed, certainty) = match result {
                     Ok(result) => result,
                     Err(NoSolution) => {
-                        errors.push(FulfillmentError {
-                            obligation: obligation.clone(),
-                            code: match goal.predicate.kind().skip_binder() {
-                                ty::PredicateKind::Clause(ty::ClauseKind::Projection(_)) => {
-                                    FulfillmentErrorCode::ProjectionError(
-                                        // FIXME: This could be a `Sorts` if the term is a type
-                                        MismatchedProjectionTypes { err: TypeError::Mismatch },
-                                    )
-                                }
-                                ty::PredicateKind::NormalizesTo(..) => {
-                                    FulfillmentErrorCode::ProjectionError(
-                                        MismatchedProjectionTypes { err: TypeError::Mismatch },
-                                    )
-                                }
-                                ty::PredicateKind::AliasRelate(_, _, _) => {
-                                    FulfillmentErrorCode::ProjectionError(
-                                        MismatchedProjectionTypes { err: TypeError::Mismatch },
-                                    )
-                                }
-                                ty::PredicateKind::Subtype(pred) => {
-                                    let (a, b) = infcx.enter_forall_and_leak_universe(
-                                        goal.predicate.kind().rebind((pred.a, pred.b)),
-                                    );
-                                    let expected_found = ExpectedFound::new(true, a, b);
-                                    FulfillmentErrorCode::SubtypeError(
-                                        expected_found,
-                                        TypeError::Sorts(expected_found),
-                                    )
-                                }
-                                ty::PredicateKind::Coerce(pred) => {
-                                    let (a, b) = infcx.enter_forall_and_leak_universe(
-                                        goal.predicate.kind().rebind((pred.a, pred.b)),
-                                    );
-                                    let expected_found = ExpectedFound::new(false, a, b);
-                                    FulfillmentErrorCode::SubtypeError(
-                                        expected_found,
-                                        TypeError::Sorts(expected_found),
-                                    )
-                                }
-                                ty::PredicateKind::Clause(_)
-                                | ty::PredicateKind::ObjectSafe(_)
-                                | ty::PredicateKind::Ambiguous => {
-                                    FulfillmentErrorCode::SelectionError(
-                                        SelectionError::Unimplemented,
-                                    )
-                                }
-                                ty::PredicateKind::ConstEquate(..) => {
-                                    bug!("unexpected goal: {goal:?}")
-                                }
-                            },
-                            root_obligation: obligation,
-                        });
+                        errors.push(fulfillment_error_for_no_solution(infcx, obligation));
                         continue;
                     }
                 };
                 has_changed |= changed;
                 match certainty {
                     Certainty::Yes => {}
-                    Certainty::Maybe(_) => self.obligations.push(obligation),
+                    Certainty::Maybe(_) => self.obligations.register(obligation),
                 }
             }
 
@@ -193,13 +179,84 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
     }
 
     fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> {
-        self.obligations.clone()
+        self.obligations.clone_pending()
     }
 
     fn drain_unstalled_obligations(
         &mut self,
         _: &InferCtxt<'tcx>,
     ) -> Vec<PredicateObligation<'tcx>> {
-        std::mem::take(&mut self.obligations)
+        self.obligations.take_pending()
     }
 }
+
+fn fulfillment_error_for_no_solution<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    obligation: PredicateObligation<'tcx>,
+) -> FulfillmentError<'tcx> {
+    let code = match obligation.predicate.kind().skip_binder() {
+        ty::PredicateKind::Clause(ty::ClauseKind::Projection(_)) => {
+            FulfillmentErrorCode::ProjectionError(
+                // FIXME: This could be a `Sorts` if the term is a type
+                MismatchedProjectionTypes { err: TypeError::Mismatch },
+            )
+        }
+        ty::PredicateKind::NormalizesTo(..) => {
+            FulfillmentErrorCode::ProjectionError(MismatchedProjectionTypes {
+                err: TypeError::Mismatch,
+            })
+        }
+        ty::PredicateKind::AliasRelate(_, _, _) => {
+            FulfillmentErrorCode::ProjectionError(MismatchedProjectionTypes {
+                err: TypeError::Mismatch,
+            })
+        }
+        ty::PredicateKind::Subtype(pred) => {
+            let (a, b) = infcx.enter_forall_and_leak_universe(
+                obligation.predicate.kind().rebind((pred.a, pred.b)),
+            );
+            let expected_found = ExpectedFound::new(true, a, b);
+            FulfillmentErrorCode::SubtypeError(expected_found, TypeError::Sorts(expected_found))
+        }
+        ty::PredicateKind::Coerce(pred) => {
+            let (a, b) = infcx.enter_forall_and_leak_universe(
+                obligation.predicate.kind().rebind((pred.a, pred.b)),
+            );
+            let expected_found = ExpectedFound::new(false, a, b);
+            FulfillmentErrorCode::SubtypeError(expected_found, TypeError::Sorts(expected_found))
+        }
+        ty::PredicateKind::Clause(_)
+        | ty::PredicateKind::ObjectSafe(_)
+        | ty::PredicateKind::Ambiguous => {
+            FulfillmentErrorCode::SelectionError(SelectionError::Unimplemented)
+        }
+        ty::PredicateKind::ConstEquate(..) => {
+            bug!("unexpected goal: {obligation:?}")
+        }
+    };
+    FulfillmentError { root_obligation: obligation.clone(), code, obligation }
+}
+
+fn fulfillment_error_for_stalled<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    obligation: PredicateObligation<'tcx>,
+) -> FulfillmentError<'tcx> {
+    let code = infcx.probe(|_| {
+        match infcx.evaluate_root_goal(obligation.clone().into(), GenerateProofTree::Never).0 {
+            Ok((_, Certainty::Maybe(MaybeCause::Ambiguity))) => {
+                FulfillmentErrorCode::Ambiguity { overflow: None }
+            }
+            Ok((_, Certainty::Maybe(MaybeCause::Overflow { suggest_increasing_limit }))) => {
+                FulfillmentErrorCode::Ambiguity { overflow: Some(suggest_increasing_limit) }
+            }
+            Ok((_, Certainty::Yes)) => {
+                bug!("did not expect successful goal when collecting ambiguity errors")
+            }
+            Err(_) => {
+                bug!("did not expect selection error when collecting ambiguity errors")
+            }
+        }
+    });
+
+    FulfillmentError { obligation: obligation.clone(), code, root_obligation: obligation }
+}
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 52b900af853..9e3e6a4676e 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -1,15 +1,16 @@
-/// An infrastructure to mechanically analyse proof trees.
-///
-/// It is unavoidable that this representation is somewhat
-/// lossy as it should hide quite a few semantically relevant things,
-/// e.g. canonicalization and the order of nested goals.
-///
-/// @lcnr: However, a lot of the weirdness here is not strictly necessary
-/// and could be improved in the future. This is mostly good enough for
-/// coherence right now and was annoying to implement, so I am leaving it
-/// as is until we start using it for something else.
-use std::ops::ControlFlow;
-
+//! An infrastructure to mechanically analyse proof trees.
+//!
+//! It is unavoidable that this representation is somewhat
+//! lossy as it should hide quite a few semantically relevant things,
+//! e.g. canonicalization and the order of nested goals.
+//!
+//! @lcnr: However, a lot of the weirdness here is not strictly necessary
+//! and could be improved in the future. This is mostly good enough for
+//! coherence right now and was annoying to implement, so I am leaving it
+//! as is until we start using it for something else.
+
+use rustc_ast_ir::try_visit;
+use rustc_ast_ir::visit::VisitorResult;
 use rustc_infer::infer::InferCtxt;
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{inspect, QueryResult};
@@ -53,10 +54,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
     /// to also use it to compute the most relevant goal
     /// for fulfillment errors. Will do that once we actually
     /// need it.
-    pub fn visit_nested<V: ProofTreeVisitor<'tcx>>(
-        &self,
-        visitor: &mut V,
-    ) -> ControlFlow<V::BreakTy> {
+    pub fn visit_nested<V: ProofTreeVisitor<'tcx>>(&self, visitor: &mut V) -> V::Result {
         // HACK: An arbitrary cutoff to avoid dealing with overflow and cycles.
         if self.goal.depth <= 10 {
             let infcx = self.goal.infcx;
@@ -75,17 +73,18 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                 for &goal in &instantiated_goals {
                     let (_, proof_tree) = infcx.evaluate_root_goal(goal, GenerateProofTree::Yes);
                     let proof_tree = proof_tree.unwrap();
-                    visitor.visit_goal(&InspectGoal::new(
+                    try_visit!(visitor.visit_goal(&InspectGoal::new(
                         infcx,
                         self.goal.depth + 1,
                         &proof_tree,
-                    ))?;
+                    )));
                 }
 
-                ControlFlow::Continue(())
-            })?;
+                V::Result::output()
+            })
+        } else {
+            V::Result::output()
         }
-        ControlFlow::Continue(())
     }
 }
 
@@ -202,9 +201,9 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
 
 /// The public API to interact with proof trees.
 pub trait ProofTreeVisitor<'tcx> {
-    type BreakTy;
+    type Result: VisitorResult = ();
 
-    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> ControlFlow<Self::BreakTy>;
+    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> Self::Result;
 }
 
 #[extension(pub trait ProofTreeInferCtxtExt<'tcx>)]
@@ -213,7 +212,7 @@ impl<'tcx> InferCtxt<'tcx> {
         &self,
         goal: Goal<'tcx, ty::Predicate<'tcx>>,
         visitor: &mut V,
-    ) -> ControlFlow<V::BreakTy> {
+    ) -> V::Result {
         self.probe(|_| {
             let (_, proof_tree) = self.evaluate_root_goal(goal, GenerateProofTree::Yes);
             let proof_tree = proof_tree.unwrap();
diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs
index 51094b781c0..0bf28f520a4 100644
--- a/compiler/rustc_trait_selection/src/solve/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/mod.rs
@@ -42,6 +42,17 @@ pub use fulfill::FulfillmentCtxt;
 pub(crate) use normalize::deeply_normalize_for_diagnostics;
 pub use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes};
 
+/// How many fixpoint iterations we should attempt inside of the solver before bailing
+/// with overflow.
+///
+/// We previously used  `tcx.recursion_limit().0.checked_ilog2().unwrap_or(0)` for this.
+/// However, it feels unlikely that uncreasing the recursion limit by a power of two
+/// to get one more itereation is every useful or desirable. We now instead used a constant
+/// here. If there ever ends up some use-cases where a bigger number of fixpoint iterations
+/// is required, we can add a new attribute for that or revert this to be dependant on the
+/// recursion limit again. However, this feels very unlikely.
+const FIXPOINT_STEP_LIMIT: usize = 8;
+
 #[derive(Debug, Clone, Copy)]
 enum SolverMode {
     /// Ordinary trait solving, using everywhere except for coherence.
diff --git a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
index 3aba5c85abc..248985715c2 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
@@ -162,15 +162,28 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> {
         let tcx = ecx.tcx();
 
         let goal_trait_ref = goal.predicate.alias.trait_ref(tcx);
-        let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
+        let impl_trait_header = tcx.impl_trait_header(impl_def_id).unwrap();
         let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup };
-        if !drcx.args_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) {
+        if !drcx.args_may_unify(
+            goal.predicate.trait_ref(tcx).args,
+            impl_trait_header.skip_binder().trait_ref.args,
+        ) {
             return Err(NoSolution);
         }
 
+        // We have to ignore negative impls when projecting.
+        let impl_polarity = impl_trait_header.skip_binder().polarity;
+        match impl_polarity {
+            ty::ImplPolarity::Negative => return Err(NoSolution),
+            ty::ImplPolarity::Reservation => {
+                unimplemented!("reservation impl for trait with assoc item: {:?}", goal)
+            }
+            ty::ImplPolarity::Positive => {}
+        };
+
         ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| {
             let impl_args = ecx.fresh_args_for_item(impl_def_id);
-            let impl_trait_ref = impl_trait_ref.instantiate(tcx, impl_args);
+            let impl_trait_ref = impl_trait_header.instantiate(tcx, impl_args).trait_ref;
 
             ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?;
 
diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs
index bede94a2e43..07a8aca85a0 100644
--- a/compiler/rustc_trait_selection/src/solve/search_graph.rs
+++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs
@@ -1,3 +1,5 @@
+use crate::solve::FIXPOINT_STEP_LIMIT;
+
 use super::inspect;
 use super::inspect::ProofTreeBuilder;
 use super::SolverMode;
@@ -99,7 +101,6 @@ impl<'tcx> ProvisionalCacheEntry<'tcx> {
 
 pub(super) struct SearchGraph<'tcx> {
     mode: SolverMode,
-    local_overflow_limit: usize,
     /// The stack of goals currently being computed.
     ///
     /// An element is *deeper* in the stack if its index is *lower*.
@@ -116,10 +117,9 @@ pub(super) struct SearchGraph<'tcx> {
 }
 
 impl<'tcx> SearchGraph<'tcx> {
-    pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> {
+    pub(super) fn new(mode: SolverMode) -> SearchGraph<'tcx> {
         Self {
             mode,
-            local_overflow_limit: tcx.recursion_limit().0.checked_ilog2().unwrap_or(0) as usize,
             stack: Default::default(),
             provisional_cache: Default::default(),
             cycle_participants: Default::default(),
@@ -130,10 +130,6 @@ impl<'tcx> SearchGraph<'tcx> {
         self.mode
     }
 
-    pub(super) fn local_overflow_limit(&self) -> usize {
-        self.local_overflow_limit
-    }
-
     /// Update the stack and reached depths on cache hits.
     #[instrument(level = "debug", skip(self))]
     fn on_cache_hit(&mut self, additional_depth: usize, encountered_overflow: bool) {
@@ -277,7 +273,7 @@ impl<'tcx> SearchGraph<'tcx> {
             }
 
             inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::Overflow);
-            return Self::response_no_constraints(tcx, input, Certainty::OVERFLOW);
+            return Self::response_no_constraints(tcx, input, Certainty::overflow(true));
         };
 
         // Try to fetch the goal from the global cache.
@@ -370,7 +366,7 @@ impl<'tcx> SearchGraph<'tcx> {
             } else if is_coinductive_cycle {
                 Self::response_no_constraints(tcx, input, Certainty::Yes)
             } else {
-                Self::response_no_constraints(tcx, input, Certainty::OVERFLOW)
+                Self::response_no_constraints(tcx, input, Certainty::overflow(false))
             };
         } else {
             // No entry, we push this goal on the stack and try to prove it.
@@ -398,7 +394,7 @@ impl<'tcx> SearchGraph<'tcx> {
                 // of this we continuously recompute the cycle until the result
                 // of the previous iteration is equal to the final result, at which
                 // point we are done.
-                for _ in 0..self.local_overflow_limit() {
+                for _ in 0..FIXPOINT_STEP_LIMIT {
                     let result = prove_goal(self, inspect);
                     let stack_entry = self.pop_stack();
                     debug_assert_eq!(stack_entry.input, input);
@@ -431,7 +427,8 @@ impl<'tcx> SearchGraph<'tcx> {
                     } else if stack_entry.has_been_used == HasBeenUsed::COINDUCTIVE_CYCLE {
                         Self::response_no_constraints(tcx, input, Certainty::Yes) == result
                     } else if stack_entry.has_been_used == HasBeenUsed::INDUCTIVE_CYCLE {
-                        Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) == result
+                        Self::response_no_constraints(tcx, input, Certainty::overflow(false))
+                            == result
                     } else {
                         false
                     };
@@ -452,7 +449,7 @@ impl<'tcx> SearchGraph<'tcx> {
                 debug!("canonical cycle overflow");
                 let current_entry = self.pop_stack();
                 debug_assert!(current_entry.has_been_used.is_empty());
-                let result = Self::response_no_constraints(tcx, input, Certainty::OVERFLOW);
+                let result = Self::response_no_constraints(tcx, input, Certainty::overflow(false));
                 (current_entry, result)
             });
 
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index eba6ba3f7b0..80198ba39f9 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -549,14 +549,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         let args = ecx.tcx().erase_regions(goal.predicate.trait_ref.args);
 
         let Some(assume) =
-            rustc_transmute::Assume::from_const(ecx.tcx(), goal.param_env, args.const_at(3))
+            rustc_transmute::Assume::from_const(ecx.tcx(), goal.param_env, args.const_at(2))
         else {
             return Err(NoSolution);
         };
 
         let certainty = ecx.is_transmutable(
             rustc_transmute::Types { dst: args.type_at(0), src: args.type_at(1) },
-            args.type_at(2),
             assume,
         )?;
         ecx.evaluate_added_goals_and_make_canonical_response(certainty)
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index 6778cb7b7a9..2712ba19451 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -22,11 +22,10 @@ use rustc_errors::{Diag, EmissionGuarantee};
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, TyCtxtInferExt};
-use rustc_infer::traits::{util, TraitEngine, TraitEngineExt};
+use rustc_infer::traits::{util, FulfillmentErrorCode, TraitEngine, TraitEngineExt};
 use rustc_middle::traits::query::NoSolution;
 use rustc_middle::traits::solve::{CandidateSource, Certainty, Goal};
 use rustc_middle::traits::specialization_graph::OverlapMode;
-use rustc_middle::traits::DefiningAnchor;
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt};
 use rustc_middle::ty::{self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitor};
@@ -35,6 +34,8 @@ use rustc_span::DUMMY_SP;
 use std::fmt::Debug;
 use std::ops::ControlFlow;
 
+use super::error_reporting::suggest_new_overflow_limit;
+
 /// Whether we do the orphan check relative to this crate or
 /// to some remote crate.
 #[derive(Copy, Clone, Debug)]
@@ -56,6 +57,9 @@ pub struct OverlapResult<'tcx> {
     /// `true` if the overlap might've been permitted before the shift
     /// to universes.
     pub involves_placeholder: bool,
+
+    /// Used in the new solver to suggest increasing the recursion limit.
+    pub overflowing_predicates: Vec<ty::Predicate<'tcx>>,
 }
 
 pub fn add_placeholder_note<G: EmissionGuarantee>(err: &mut Diag<'_, G>) {
@@ -65,6 +69,18 @@ pub fn add_placeholder_note<G: EmissionGuarantee>(err: &mut Diag<'_, G>) {
     );
 }
 
+pub fn suggest_increasing_recursion_limit<'tcx, G: EmissionGuarantee>(
+    tcx: TyCtxt<'tcx>,
+    err: &mut Diag<'_, G>,
+    overflowing_predicates: &[ty::Predicate<'tcx>],
+) {
+    for pred in overflowing_predicates {
+        err.note(format!("overflow evaluating the requirement `{}`", pred));
+    }
+
+    suggest_new_overflow_limit(tcx, err);
+}
+
 #[derive(Debug, Clone, Copy)]
 enum TrackAmbiguityCauses {
     Yes,
@@ -190,7 +206,6 @@ fn overlap<'tcx>(
 
     let infcx = tcx
         .infer_ctxt()
-        .with_opaque_type_inference(DefiningAnchor::Bubble)
         .skip_leak_check(skip_leak_check.is_yes())
         .intercrate(true)
         .with_next_trait_solver(tcx.next_trait_solver_in_coherence())
@@ -221,11 +236,13 @@ fn overlap<'tcx>(
         ),
     );
 
+    let mut overflowing_predicates = Vec::new();
     if overlap_mode.use_implicit_negative() {
-        if let Some(_failing_obligation) =
-            impl_intersection_has_impossible_obligation(selcx, &obligations)
-        {
-            return None;
+        match impl_intersection_has_impossible_obligation(selcx, &obligations) {
+            IntersectionHasImpossibleObligations::Yes => return None,
+            IntersectionHasImpossibleObligations::No { overflowing_predicates: p } => {
+                overflowing_predicates = p
+            }
         }
     }
 
@@ -261,7 +278,12 @@ fn overlap<'tcx>(
         impl_header = deeply_normalize_for_diagnostics(&infcx, param_env, impl_header);
     }
 
-    Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder })
+    Some(OverlapResult {
+        impl_header,
+        intercrate_ambiguity_causes,
+        involves_placeholder,
+        overflowing_predicates,
+    })
 }
 
 #[instrument(level = "debug", skip(infcx), ret)]
@@ -287,6 +309,19 @@ fn equate_impl_headers<'tcx>(
     result.map(|infer_ok| infer_ok.obligations).ok()
 }
 
+/// The result of [fn impl_intersection_has_impossible_obligation].
+enum IntersectionHasImpossibleObligations<'tcx> {
+    Yes,
+    No {
+        /// With `-Znext-solver=coherence`, some obligations may
+        /// fail if only the user increased the recursion limit.
+        ///
+        /// We return those obligations here and mention them in the
+        /// error message.
+        overflowing_predicates: Vec<ty::Predicate<'tcx>>,
+    },
+}
+
 /// Check if both impls can be satisfied by a common type by considering whether
 /// any of either impl's obligations is not known to hold.
 ///
@@ -308,7 +343,7 @@ fn equate_impl_headers<'tcx>(
 fn impl_intersection_has_impossible_obligation<'a, 'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     obligations: &'a [PredicateObligation<'tcx>],
-) -> Option<PredicateObligation<'tcx>> {
+) -> IntersectionHasImpossibleObligations<'tcx> {
     let infcx = selcx.infcx;
 
     if infcx.next_trait_solver() {
@@ -317,28 +352,42 @@ fn impl_intersection_has_impossible_obligation<'a, 'cx, 'tcx>(
 
         // We only care about the obligations that are *definitely* true errors.
         // Ambiguities do not prove the disjointness of two impls.
-        let mut errors = fulfill_cx.select_where_possible(infcx);
-        errors.pop().map(|err| err.obligation)
+        let errors = fulfill_cx.select_where_possible(infcx);
+        if errors.is_empty() {
+            let overflow_errors = fulfill_cx.collect_remaining_errors(infcx);
+            let overflowing_predicates = overflow_errors
+                .into_iter()
+                .filter(|e| match e.code {
+                    FulfillmentErrorCode::Ambiguity { overflow: Some(true) } => true,
+                    _ => false,
+                })
+                .map(|e| infcx.resolve_vars_if_possible(e.obligation.predicate))
+                .collect();
+            IntersectionHasImpossibleObligations::No { overflowing_predicates }
+        } else {
+            IntersectionHasImpossibleObligations::Yes
+        }
     } else {
-        obligations
-            .iter()
-            .find(|obligation| {
-                // We use `evaluate_root_obligation` to correctly track intercrate
-                // ambiguity clauses. We cannot use this in the new solver.
-                let evaluation_result = selcx.evaluate_root_obligation(obligation);
-
-                match evaluation_result {
-                    Ok(result) => !result.may_apply(),
-                    // If overflow occurs, we need to conservatively treat the goal as possibly holding,
-                    // since there can be instantiations of this goal that don't overflow and result in
-                    // success. This isn't much of a problem in the old solver, since we treat overflow
-                    // fatally (this still can be encountered: <https://github.com/rust-lang/rust/issues/105231>),
-                    // but in the new solver, this is very important for correctness, since overflow
-                    // *must* be treated as ambiguity for completeness.
-                    Err(_overflow) => false,
+        for obligation in obligations {
+            // We use `evaluate_root_obligation` to correctly track intercrate
+            // ambiguity clauses.
+            let evaluation_result = selcx.evaluate_root_obligation(obligation);
+
+            match evaluation_result {
+                Ok(result) => {
+                    if !result.may_apply() {
+                        return IntersectionHasImpossibleObligations::Yes;
+                    }
                 }
-            })
-            .cloned()
+                // If overflow occurs, we need to conservatively treat the goal as possibly holding,
+                // since there can be instantiations of this goal that don't overflow and result in
+                // success. While this isn't much of a problem in the old solver, since we treat overflow
+                // fatally, this still can be encountered: <https://github.com/rust-lang/rust/issues/105231>.
+                Err(_overflow) => {}
+            }
+        }
+
+        IntersectionHasImpossibleObligations::No { overflowing_predicates: Vec::new() }
     }
 }
 
@@ -423,7 +472,7 @@ fn plug_infer_with_placeholders<'tcx>(
     }
 
     impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for PlugInferWithPlaceholder<'_, 'tcx> {
-        fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_ty(&mut self, ty: Ty<'tcx>) {
             let ty = self.infcx.shallow_resolve(ty);
             if ty.is_ty_var() {
                 let Ok(InferOk { value: (), obligations }) =
@@ -445,13 +494,12 @@ fn plug_infer_with_placeholders<'tcx>(
                     bug!("we always expect to be able to plug an infer var with placeholder")
                 };
                 assert_eq!(obligations, &[]);
-                ControlFlow::Continue(())
             } else {
-                ty.super_visit_with(self)
+                ty.super_visit_with(self);
             }
         }
 
-        fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_const(&mut self, ct: ty::Const<'tcx>) {
             let ct = self.infcx.shallow_resolve(ct);
             if ct.is_ct_infer() {
                 let Ok(InferOk { value: (), obligations }) =
@@ -468,13 +516,12 @@ fn plug_infer_with_placeholders<'tcx>(
                     bug!("we always expect to be able to plug an infer var with placeholder")
                 };
                 assert_eq!(obligations, &[]);
-                ControlFlow::Continue(())
             } else {
-                ct.super_visit_with(self)
+                ct.super_visit_with(self);
             }
         }
 
-        fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_region(&mut self, r: ty::Region<'tcx>) {
             if let ty::ReVar(vid) = *r {
                 let r = self
                     .infcx
@@ -504,7 +551,6 @@ fn plug_infer_with_placeholders<'tcx>(
                     assert_eq!(obligations, &[]);
                 }
             }
-            ControlFlow::Continue(())
         }
     }
 
@@ -817,12 +863,12 @@ impl<'tcx, F, E> TypeVisitor<TyCtxt<'tcx>> for OrphanChecker<'tcx, F>
 where
     F: FnMut(Ty<'tcx>) -> Result<Ty<'tcx>, E>,
 {
-    type BreakTy = OrphanCheckEarlyExit<'tcx, E>;
-    fn visit_region(&mut self, _r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+    type Result = ControlFlow<OrphanCheckEarlyExit<'tcx, E>>;
+    fn visit_region(&mut self, _r: ty::Region<'tcx>) -> Self::Result {
         ControlFlow::Continue(())
     }
 
-    fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
         // Need to lazily normalize here in with `-Znext-solver=coherence`.
         let ty = match (self.lazily_normalize_ty)(ty) {
             Ok(ty) => ty,
@@ -945,7 +991,7 @@ where
     /// As these should be quite rare as const arguments and especially rare as impl
     /// parameters, allowing uncovered const parameters in impls seems more useful
     /// than allowing `impl<T> Trait<local_fn_ptr, T> for i32` to compile.
-    fn visit_const(&mut self, _c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_const(&mut self, _c: ty::Const<'tcx>) -> Self::Result {
         ControlFlow::Continue(())
     }
 }
@@ -975,18 +1021,17 @@ struct AmbiguityCausesVisitor<'a, 'tcx> {
 }
 
 impl<'a, 'tcx> ProofTreeVisitor<'tcx> for AmbiguityCausesVisitor<'a, 'tcx> {
-    type BreakTy = !;
-    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) {
         let infcx = goal.infcx();
         for cand in goal.candidates() {
-            cand.visit_nested(self)?;
+            cand.visit_nested(self);
         }
         // When searching for intercrate ambiguity causes, we only need to look
         // at ambiguous goals, as for others the coherence unknowable candidate
         // was irrelevant.
         match goal.result() {
             Ok(Certainty::Maybe(_)) => {}
-            Ok(Certainty::Yes) | Err(NoSolution) => return ControlFlow::Continue(()),
+            Ok(Certainty::Yes) | Err(NoSolution) => return,
         }
 
         let Goal { param_env, predicate } = goal.goal();
@@ -1003,7 +1048,7 @@ impl<'a, 'tcx> ProofTreeVisitor<'tcx> for AmbiguityCausesVisitor<'a, 'tcx> {
             {
                 proj.projection_ty.trait_ref(infcx.tcx)
             }
-            _ => return ControlFlow::Continue(()),
+            _ => return,
         };
 
         // Add ambiguity causes for reservation impls.
@@ -1103,8 +1148,6 @@ impl<'a, 'tcx> ProofTreeVisitor<'tcx> for AmbiguityCausesVisitor<'a, 'tcx> {
         if let Some(ambiguity_cause) = ambiguity_cause {
             self.causes.insert(ambiguity_cause);
         }
-
-        ControlFlow::Continue(())
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs b/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs
index 189e1ba54bc..7f0f9a12d6a 100644
--- a/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs
+++ b/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs
@@ -17,7 +17,6 @@ use rustc_middle::ty::abstract_const::NotConstEvaluatable;
 use rustc_middle::ty::{self, TyCtxt, TypeVisitable, TypeVisitableExt, TypeVisitor};
 
 use rustc_span::Span;
-use std::ops::ControlFlow;
 
 use crate::traits::ObligationCtxt;
 
@@ -170,8 +169,7 @@ fn satisfied_from_param_env<'tcx>(
     }
 
     impl<'a, 'tcx> TypeVisitor<TyCtxt<'tcx>> for Visitor<'a, 'tcx> {
-        type BreakTy = ();
-        fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_const(&mut self, c: ty::Const<'tcx>) {
             debug!("is_const_evaluatable: candidate={:?}", c);
             if self.infcx.probe(|_| {
                 let ocx = ObligationCtxt::new(self.infcx);
@@ -187,7 +185,7 @@ fn satisfied_from_param_env<'tcx>(
             }
 
             if let ty::ConstKind::Expr(e) = c.kind() {
-                e.visit_with(self)
+                e.visit_with(self);
             } else {
                 // FIXME(generic_const_exprs): This doesn't recurse into `<T as Trait<U>>::ASSOC`'s args.
                 // This is currently unobservable as `<T as Trait<{ U + 1 }>>::ASSOC` creates an anon const
@@ -196,7 +194,6 @@ fn satisfied_from_param_env<'tcx>(
                 // If we start allowing directly writing `ConstKind::Expr` without an intermediate anon const
                 // this will be incorrect. It might be worth investigating making `predicates_of` elaborate
                 // all of the `ConstEvaluatable` bounds rather than having a visitor here.
-                ControlFlow::Continue(())
             }
         }
     }
diff --git a/compiler/rustc_trait_selection/src/traits/engine.rs b/compiler/rustc_trait_selection/src/traits/engine.rs
index e789e9c2b6e..9fbec174ce8 100644
--- a/compiler/rustc_trait_selection/src/traits/engine.rs
+++ b/compiler/rustc_trait_selection/src/traits/engine.rs
@@ -116,24 +116,6 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> {
         self.infcx.at(cause, param_env).deeply_normalize(value, &mut **self.engine.borrow_mut())
     }
 
-    /// Makes `expected <: actual`.
-    pub fn eq_exp<T>(
-        &self,
-        cause: &ObligationCause<'tcx>,
-        param_env: ty::ParamEnv<'tcx>,
-        a_is_expected: bool,
-        a: T,
-        b: T,
-    ) -> Result<(), TypeError<'tcx>>
-    where
-        T: ToTrace<'tcx>,
-    {
-        self.infcx
-            .at(cause, param_env)
-            .eq_exp(DefineOpaqueTypes::Yes, a_is_expected, a, b)
-            .map(|infer_ok| self.register_infer_ok_obligations(infer_ok))
-    }
-
     pub fn eq<T: ToTrace<'tcx>>(
         &self,
         cause: &ObligationCause<'tcx>,
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
index 0796cb57d97..0515b09ae46 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs
@@ -152,9 +152,9 @@ impl ArgKind {
 struct HasNumericInferVisitor;
 
 impl<'tcx> ty::TypeVisitor<TyCtxt<'tcx>> for HasNumericInferVisitor {
-    type BreakTy = ();
+    type Result = ControlFlow<()>;
 
-    fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
         if matches!(ty.kind(), ty::Infer(ty::FloatVar(_) | ty::IntVar(_))) {
             ControlFlow::Break(())
         } else {
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
index 4ba2da95fb3..126bc0c9ec0 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs
@@ -16,6 +16,7 @@ use rustc_session::lint::builtin::UNKNOWN_OR_MALFORMED_DIAGNOSTIC_ATTRIBUTES;
 use rustc_span::symbol::{kw, sym, Symbol};
 use rustc_span::Span;
 use std::iter;
+use std::path::PathBuf;
 
 use crate::errors::{
     EmptyOnClauseInOnUnimplemented, InvalidOnClauseInOnUnimplemented, NoValueInOnUnimplemented,
@@ -110,6 +111,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         &self,
         trait_ref: ty::PolyTraitRef<'tcx>,
         obligation: &PredicateObligation<'tcx>,
+        long_ty_file: &mut Option<PathBuf>,
     ) -> OnUnimplementedNote {
         let (def_id, args) = self
             .impl_similar_to(trait_ref, obligation)
@@ -265,7 +267,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         }));
 
         if let Ok(Some(command)) = OnUnimplementedDirective::of_item(self.tcx, def_id) {
-            command.evaluate(self.tcx, trait_ref, &flags)
+            command.evaluate(self.tcx, trait_ref, &flags, long_ty_file)
         } else {
             OnUnimplementedNote::default()
         }
@@ -657,6 +659,7 @@ impl<'tcx> OnUnimplementedDirective {
         tcx: TyCtxt<'tcx>,
         trait_ref: ty::TraitRef<'tcx>,
         options: &[(Symbol, Option<String>)],
+        long_ty_file: &mut Option<PathBuf>,
     ) -> OnUnimplementedNote {
         let mut message = None;
         let mut label = None;
@@ -669,6 +672,7 @@ impl<'tcx> OnUnimplementedDirective {
             options.iter().filter_map(|(k, v)| v.clone().map(|v| (*k, v))).collect();
 
         for command in self.subcommands.iter().chain(Some(self)).rev() {
+            debug!(?command);
             if let Some(ref condition) = command.condition
                 && !attr::eval_condition(condition, &tcx.sess, Some(tcx.features()), &mut |cfg| {
                     let value = cfg.value.map(|v| {
@@ -680,7 +684,12 @@ impl<'tcx> OnUnimplementedDirective {
                                 span: cfg.span,
                                 is_diagnostic_namespace_variant: false
                             }
-                            .format(tcx, trait_ref, &options_map)
+                            .format(
+                                tcx,
+                                trait_ref,
+                                &options_map,
+                                long_ty_file
+                            )
                         )
                     });
 
@@ -709,10 +718,14 @@ impl<'tcx> OnUnimplementedDirective {
         }
 
         OnUnimplementedNote {
-            label: label.map(|l| l.format(tcx, trait_ref, &options_map)),
-            message: message.map(|m| m.format(tcx, trait_ref, &options_map)),
-            notes: notes.into_iter().map(|n| n.format(tcx, trait_ref, &options_map)).collect(),
-            parent_label: parent_label.map(|e_s| e_s.format(tcx, trait_ref, &options_map)),
+            label: label.map(|l| l.format(tcx, trait_ref, &options_map, long_ty_file)),
+            message: message.map(|m| m.format(tcx, trait_ref, &options_map, long_ty_file)),
+            notes: notes
+                .into_iter()
+                .map(|n| n.format(tcx, trait_ref, &options_map, long_ty_file))
+                .collect(),
+            parent_label: parent_label
+                .map(|e_s| e_s.format(tcx, trait_ref, &options_map, long_ty_file)),
             append_const_msg,
         }
     }
@@ -814,6 +827,7 @@ impl<'tcx> OnUnimplementedFormatString {
         tcx: TyCtxt<'tcx>,
         trait_ref: ty::TraitRef<'tcx>,
         options: &FxHashMap<Symbol, String>,
+        long_ty_file: &mut Option<PathBuf>,
     ) -> String {
         let name = tcx.item_name(trait_ref.def_id);
         let trait_str = tcx.def_path_str(trait_ref.def_id);
@@ -824,7 +838,11 @@ impl<'tcx> OnUnimplementedFormatString {
             .filter_map(|param| {
                 let value = match param.kind {
                     GenericParamDefKind::Type { .. } | GenericParamDefKind::Const { .. } => {
-                        trait_ref.args[param.index as usize].to_string()
+                        if let Some(ty) = trait_ref.args[param.index as usize].as_type() {
+                            tcx.short_ty_string(ty, long_ty_file)
+                        } else {
+                            trait_ref.args[param.index as usize].to_string()
+                        }
                     }
                     GenericParamDefKind::Lifetime => return None,
                 };
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
index bca7b232749..1241227a5af 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs
@@ -38,6 +38,7 @@ use rustc_span::def_id::LocalDefId;
 use rustc_span::symbol::{kw, sym, Ident, Symbol};
 use rustc_span::{BytePos, DesugaringKind, ExpnKind, MacroKind, Span, DUMMY_SP};
 use rustc_target::spec::abi;
+use std::assert_matches::debug_assert_matches;
 use std::borrow::Cow;
 use std::iter;
 
@@ -1265,8 +1266,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                     if has_custom_message {
                         err.note(msg);
                     } else {
-                        err.messages =
-                            vec![(rustc_errors::DiagnosticMessage::from(msg), Style::NoStyle)];
+                        err.messages = vec![(rustc_errors::DiagMessage::from(msg), Style::NoStyle)];
                     }
                     let mut file = None;
                     err.span_label(
@@ -2671,6 +2671,8 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
     ) where
         T: ToPredicate<'tcx>,
     {
+        let mut long_ty_file = None;
+
         let tcx = self.tcx;
         let predicate = predicate.to_predicate(tcx);
         match *cause_code {
@@ -2853,21 +2855,13 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                 }
             }
             ObligationCauseCode::Coercion { source, target } => {
-                let mut file = None;
-                let source = tcx.short_ty_string(self.resolve_vars_if_possible(source), &mut file);
-                let target = tcx.short_ty_string(self.resolve_vars_if_possible(target), &mut file);
+                let source =
+                    tcx.short_ty_string(self.resolve_vars_if_possible(source), &mut long_ty_file);
+                let target =
+                    tcx.short_ty_string(self.resolve_vars_if_possible(target), &mut long_ty_file);
                 err.note(with_forced_trimmed_paths!(format!(
                     "required for the cast from `{source}` to `{target}`",
                 )));
-                if let Some(file) = file {
-                    err.note(format!(
-                        "the full name for the type has been written to '{}'",
-                        file.display(),
-                    ));
-                    err.note(
-                        "consider using `--verbose` to print the full type name to the console",
-                    );
-                }
             }
             ObligationCauseCode::RepeatElementCopy {
                 is_constable,
@@ -3170,8 +3164,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                 // Don't print the tuple of capture types
                 'print: {
                     if !is_upvar_tys_infer_tuple {
-                        let mut file = None;
-                        let ty_str = tcx.short_ty_string(ty, &mut file);
+                        let ty_str = tcx.short_ty_string(ty, &mut long_ty_file);
                         let msg = format!("required because it appears within the type `{ty_str}`");
                         match ty.kind() {
                             ty::Adt(def, _) => match tcx.opt_item_ident(def.did()) {
@@ -3269,9 +3262,8 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                 let mut parent_trait_pred =
                     self.resolve_vars_if_possible(data.derived.parent_trait_pred);
                 let parent_def_id = parent_trait_pred.def_id();
-                let mut file = None;
-                let self_ty_str =
-                    tcx.short_ty_string(parent_trait_pred.skip_binder().self_ty(), &mut file);
+                let self_ty_str = tcx
+                    .short_ty_string(parent_trait_pred.skip_binder().self_ty(), &mut long_ty_file);
                 let trait_name = parent_trait_pred.print_modifiers_and_trait_path().to_string();
                 let msg = format!("required for `{self_ty_str}` to implement `{trait_name}`");
                 let mut is_auto_trait = false;
@@ -3329,15 +3321,6 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                     }
                 };
 
-                if let Some(file) = file {
-                    err.note(format!(
-                        "the full type name has been written to '{}'",
-                        file.display(),
-                    ));
-                    err.note(
-                        "consider using `--verbose` to print the full type name to the console",
-                    );
-                }
                 let mut parent_predicate = parent_trait_pred;
                 let mut data = &data.derived;
                 let mut count = 0;
@@ -3378,22 +3361,14 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                         count,
                         pluralize!(count)
                     ));
-                    let mut file = None;
-                    let self_ty =
-                        tcx.short_ty_string(parent_trait_pred.skip_binder().self_ty(), &mut file);
+                    let self_ty = tcx.short_ty_string(
+                        parent_trait_pred.skip_binder().self_ty(),
+                        &mut long_ty_file,
+                    );
                     err.note(format!(
                         "required for `{self_ty}` to implement `{}`",
                         parent_trait_pred.print_modifiers_and_trait_path()
                     ));
-                    if let Some(file) = file {
-                        err.note(format!(
-                            "the full type name has been written to '{}'",
-                            file.display(),
-                        ));
-                        err.note(
-                            "consider using `--verbose` to print the full type name to the console",
-                        );
-                    }
                 }
                 // #74711: avoid a stack overflow
                 ensure_sufficient_stack(|| {
@@ -3502,7 +3477,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
             }
             ObligationCauseCode::OpaqueReturnType(expr_info) => {
                 if let Some((expr_ty, expr_span)) = expr_info {
-                    let expr_ty = with_forced_trimmed_paths!(self.ty_to_string(expr_ty));
+                    let expr_ty = self.tcx.short_ty_string(expr_ty, &mut long_ty_file);
                     err.span_label(
                         expr_span,
                         with_forced_trimmed_paths!(format!(
@@ -3512,6 +3487,14 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                 }
             }
         }
+
+        if let Some(file) = long_ty_file {
+            err.note(format!(
+                "the full name for the type has been written to '{}'",
+                file.display(),
+            ));
+            err.note("consider using `--verbose` to print the full type name to the console");
+        }
     }
 
     #[instrument(
@@ -4236,30 +4219,25 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
             };
 
             let origin = TypeVariableOrigin { kind: TypeVariableOriginKind::TypeInference, span };
-            let trait_def_id = proj.trait_def_id(self.tcx);
             // Make `Self` be equivalent to the type of the call chain
             // expression we're looking at now, so that we can tell what
             // for example `Iterator::Item` is at this point in the chain.
-            let args = GenericArgs::for_item(self.tcx, trait_def_id, |param, _| {
-                match param.kind {
-                    ty::GenericParamDefKind::Type { .. } => {
-                        if param.index == 0 {
-                            return prev_ty.into();
-                        }
-                    }
-                    ty::GenericParamDefKind::Lifetime | ty::GenericParamDefKind::Const { .. } => {}
+            let args = GenericArgs::for_item(self.tcx, proj.def_id, |param, _| {
+                if param.index == 0 {
+                    debug_assert_matches!(param.kind, ty::GenericParamDefKind::Type { .. });
+                    return prev_ty.into();
                 }
                 self.var_for_def(span, param)
             });
             // This will hold the resolved type of the associated type, if the
             // current expression implements the trait that associated type is
             // in. For example, this would be what `Iterator::Item` is here.
-            let ty_var = self.infcx.next_ty_var(origin);
+            let ty = self.infcx.next_ty_var(origin);
             // This corresponds to `<ExprTy as Iterator>::Item = _`.
             let projection = ty::Binder::dummy(ty::PredicateKind::Clause(
                 ty::ClauseKind::Projection(ty::ProjectionPredicate {
                     projection_ty: ty::AliasTy::new(self.tcx, proj.def_id, args),
-                    term: ty_var.into(),
+                    term: ty.into(),
                 }),
             ));
             let body_def_id = self.tcx.hir().enclosing_body_owner(body_id);
@@ -4271,14 +4249,15 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                 param_env,
                 projection,
             ));
-            if ocx.select_where_possible().is_empty() {
-                // `ty_var` now holds the type that `Item` is for `ExprTy`.
-                let ty_var = self.resolve_vars_if_possible(ty_var);
-                assocs_in_this_method.push(Some((span, (proj.def_id, ty_var))));
+            if ocx.select_where_possible().is_empty()
+                && let ty = self.resolve_vars_if_possible(ty)
+                && !ty.is_ty_var()
+            {
+                assocs_in_this_method.push(Some((span, (proj.def_id, ty))));
             } else {
                 // `<ExprTy as Iterator>` didn't select, so likely we've
                 // reached the end of the iterator chain, like the originating
-                // `Vec<_>`.
+                // `Vec<_>` or the `ty` couldn't be determined.
                 // Keep the space consistent for later zipping.
                 assocs_in_this_method.push(None);
             }
@@ -4769,20 +4748,21 @@ pub(super) fn get_explanation_based_on_obligation<'tcx>(
         } else {
             String::new()
         };
-        match ty_desc {
-            Some(desc) => format!(
-                "{}the trait `{}` is not implemented for {} `{}`{post}",
-                pre_message,
-                trait_predicate.print_modifiers_and_trait_path(),
-                desc,
-                tcx.short_ty_string(trait_ref.skip_binder().self_ty(), &mut None),
-            ),
-            None => format!(
-                "{}the trait `{}` is not implemented for `{}`{post}",
-                pre_message,
+        let desc = match ty_desc {
+            Some(desc) => format!(" {desc}"),
+            None => String::new(),
+        };
+        if let ty::ImplPolarity::Positive = trait_predicate.polarity() {
+            format!(
+                "{pre_message}the trait `{}` is not implemented for{desc} `{}`{post}",
                 trait_predicate.print_modifiers_and_trait_path(),
                 tcx.short_ty_string(trait_ref.skip_binder().self_ty(), &mut None),
-            ),
+            )
+        } else {
+            // "the trait bound `T: !Send` is not satisfied" reads better than "`!Send` is
+            // not implemented for `T`".
+            // FIXME: add note explaining explicit negative trait bounds.
+            format!("{pre_message}the trait bound `{trait_predicate}` is not satisfied{post}")
         }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
index d9e49f1eb0a..7a930937255 100644
--- a/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
+++ b/compiler/rustc_trait_selection/src/traits/error_reporting/type_err_ctxt_ext.rs
@@ -20,10 +20,9 @@ use crate::traits::{
     SelectionError, SignatureMismatch, TraitNotObjectSafe,
 };
 use rustc_data_structures::fx::{FxHashMap, FxIndexMap};
-use rustc_errors::{
-    codes::*, pluralize, struct_span_code_err, Applicability, Diag, ErrorGuaranteed, FatalError,
-    MultiSpan, StashKey, StringPart,
-};
+use rustc_errors::codes::*;
+use rustc_errors::{pluralize, struct_span_code_err, Applicability, MultiSpan, StringPart};
+use rustc_errors::{Diag, EmissionGuarantee, ErrorGuaranteed, FatalError, StashKey};
 use rustc_hir as hir;
 use rustc_hir::def::{DefKind, Namespace, Res};
 use rustc_hir::def_id::{DefId, LocalDefId};
@@ -62,6 +61,22 @@ pub enum OverflowCause<'tcx> {
     TraitSolver(ty::Predicate<'tcx>),
 }
 
+pub fn suggest_new_overflow_limit<'tcx, G: EmissionGuarantee>(
+    tcx: TyCtxt<'tcx>,
+    err: &mut Diag<'_, G>,
+) {
+    let suggested_limit = match tcx.recursion_limit() {
+        Limit(0) => Limit(2),
+        limit => limit * 2,
+    };
+    err.help(format!(
+        "consider increasing the recursion limit by adding a \
+         `#![recursion_limit = \"{}\"]` attribute to your crate (`{}`)",
+        suggested_limit,
+        tcx.crate_name(LOCAL_CRATE),
+    ));
+}
+
 #[extension(pub trait TypeErrCtxtExt<'tcx>)]
 impl<'tcx> TypeErrCtxt<'_, 'tcx> {
     fn report_fulfillment_errors(
@@ -263,7 +278,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         };
 
         if suggest_increasing_limit {
-            self.suggest_new_overflow_limit(&mut err);
+            suggest_new_overflow_limit(self.tcx, &mut err);
         }
 
         err
@@ -303,19 +318,6 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         );
     }
 
-    fn suggest_new_overflow_limit(&self, err: &mut Diag<'_>) {
-        let suggested_limit = match self.tcx.recursion_limit() {
-            Limit(0) => Limit(2),
-            limit => limit * 2,
-        };
-        err.help(format!(
-            "consider increasing the recursion limit by adding a \
-             `#![recursion_limit = \"{}\"]` attribute to your crate (`{}`)",
-            suggested_limit,
-            self.tcx.crate_name(LOCAL_CRATE),
-        ));
-    }
-
     /// Reports that a cycle was detected which led to overflow and halts
     /// compilation. This is equivalent to `report_overflow_obligation` except
     /// that we can give a more helpful error message (and, in particular,
@@ -335,12 +337,16 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         );
     }
 
-    fn report_overflow_no_abort(&self, obligation: PredicateObligation<'tcx>) -> ErrorGuaranteed {
+    fn report_overflow_no_abort(
+        &self,
+        obligation: PredicateObligation<'tcx>,
+        suggest_increasing_limit: bool,
+    ) -> ErrorGuaranteed {
         let obligation = self.resolve_vars_if_possible(obligation);
         let mut err = self.build_overflow_error(
             OverflowCause::TraitSolver(obligation.predicate),
             obligation.cause.span,
-            true,
+            suggest_increasing_limit,
         );
         self.note_obligation_cause(&mut err, &obligation);
         self.point_at_returns_when_relevant(&mut err, &obligation);
@@ -389,6 +395,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                     kind: _,
                 } = *obligation.cause.code()
                 {
+                    debug!("ObligationCauseCode::CompareImplItemObligation");
                     return self.report_extra_impl_obligation(
                         span,
                         impl_item_def_id,
@@ -409,9 +416,59 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                     ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_predicate)) => {
                         let trait_predicate = bound_predicate.rebind(trait_predicate);
                         let trait_predicate = self.resolve_vars_if_possible(trait_predicate);
-                        let trait_ref = trait_predicate.to_poly_trait_ref();
 
-                        if let Some(guar) = self.emit_specialized_closure_kind_error(&obligation, trait_ref) {
+                        // Let's use the root obligation as the main message, when we care about the
+                        // most general case ("X doesn't implement Pattern<'_>") over the case that
+                        // happened to fail ("char doesn't implement Fn(&mut char)").
+                        //
+                        // We rely on a few heuristics to identify cases where this root
+                        // obligation is more important than the leaf obligation:
+                        let (main_trait_predicate, o) = if let ty::PredicateKind::Clause(
+                            ty::ClauseKind::Trait(root_pred)
+                        ) = root_obligation.predicate.kind().skip_binder()
+                            && !trait_predicate.self_ty().skip_binder().has_escaping_bound_vars()
+                            && !root_pred.self_ty().has_escaping_bound_vars()
+                            // The type of the leaf predicate is (roughly) the same as the type
+                            // from the root predicate, as a proxy for "we care about the root"
+                            // FIXME: this doesn't account for trivial derefs, but works as a first
+                            // approximation.
+                            && (
+                                // `T: Trait` && `&&T: OtherTrait`, we want `OtherTrait`
+                                self.can_eq(
+                                    obligation.param_env,
+                                    trait_predicate.self_ty().skip_binder(),
+                                    root_pred.self_ty().peel_refs(),
+                                )
+                                // `&str: Iterator` && `&str: IntoIterator`, we want `IntoIterator`
+                                || self.can_eq(
+                                    obligation.param_env,
+                                    trait_predicate.self_ty().skip_binder(),
+                                    root_pred.self_ty(),
+                                )
+                            )
+                            // The leaf trait and the root trait are different, so as to avoid
+                            // talking about `&mut T: Trait` and instead remain talking about
+                            // `T: Trait` instead
+                            && trait_predicate.def_id() != root_pred.def_id()
+                            // The root trait is not `Unsize`, as to avoid talking about it in
+                            // `tests/ui/coercion/coerce-issue-49593-box-never.rs`.
+                            && Some(root_pred.def_id()) != self.tcx.lang_items().unsize_trait()
+                        {
+                            (
+                                self.resolve_vars_if_possible(
+                                    root_obligation.predicate.kind().rebind(root_pred),
+                                ),
+                                root_obligation,
+                            )
+                        } else {
+                            (trait_predicate, &obligation)
+                        };
+                        let trait_ref = main_trait_predicate.to_poly_trait_ref();
+
+                        if let Some(guar) = self.emit_specialized_closure_kind_error(
+                            &obligation,
+                            trait_ref,
+                        ) {
                             return guar;
                         }
 
@@ -439,18 +496,20 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                                 )
                             })
                             .unwrap_or_default();
-                        let file_note = file.map(|file| format!(
+                        let file_note = file.as_ref().map(|file| format!(
                             "the full trait has been written to '{}'",
                             file.display(),
                         ));
 
+                        let mut long_ty_file = None;
+
                         let OnUnimplementedNote {
                             message,
                             label,
                             notes,
                             parent_label,
                             append_const_msg,
-                        } = self.on_unimplemented_note(trait_ref, &obligation);
+                        } = self.on_unimplemented_note(trait_ref, o, &mut long_ty_file);
                         let have_alt_message = message.is_some() || label.is_some();
                         let is_try_conversion = self.is_try_conversion(span, trait_ref.def_id());
                         let is_unsize =
@@ -473,7 +532,7 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                         };
 
                         let err_msg = self.get_standard_error_message(
-                            &trait_predicate,
+                            &main_trait_predicate,
                             message,
                             predicate_is_const,
                             append_const_msg,
@@ -505,6 +564,13 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
 
                         let mut err = struct_span_code_err!(self.dcx(), span, E0277, "{}", err_msg);
 
+                        if let Some(long_ty_file) = long_ty_file {
+                            err.note(format!(
+                                "the full name for the type has been written to '{}'",
+                                long_ty_file.display(),
+                            ));
+                            err.note("consider using `--verbose` to print the full type name to the console");
+                        }
                         let mut suggested = false;
                         if is_try_conversion {
                             suggested = self.try_conversion_context(&obligation, trait_ref.skip_binder(), &mut err);
@@ -752,6 +818,8 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                             return err.emit();
                         }
 
+
+
                         err
                     }
 
@@ -1422,11 +1490,11 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
             FulfillmentErrorCode::ProjectionError(ref e) => {
                 self.report_projection_error(&error.obligation, e)
             }
-            FulfillmentErrorCode::Ambiguity { overflow: false } => {
+            FulfillmentErrorCode::Ambiguity { overflow: None } => {
                 self.maybe_report_ambiguity(&error.obligation)
             }
-            FulfillmentErrorCode::Ambiguity { overflow: true } => {
-                self.report_overflow_no_abort(error.obligation.clone())
+            FulfillmentErrorCode::Ambiguity { overflow: Some(suggest_increasing_limit) } => {
+                self.report_overflow_no_abort(error.obligation.clone(), suggest_increasing_limit)
             }
             FulfillmentErrorCode::SubtypeError(ref expected_found, ref err) => self
                 .report_mismatched_types(
@@ -1528,6 +1596,12 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                         | ObligationCauseCode::Coercion { .. }
                 );
 
+                let (expected, actual) = if is_normalized_term_expected {
+                    (normalized_term, data.term)
+                } else {
+                    (data.term, normalized_term)
+                };
+
                 // constrain inference variables a bit more to nested obligations from normalize so
                 // we can have more helpful errors.
                 //
@@ -1535,13 +1609,9 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                 // since the normalization is just done to improve the error message.
                 let _ = ocx.select_where_possible();
 
-                if let Err(new_err) = ocx.eq_exp(
-                    &obligation.cause,
-                    obligation.param_env,
-                    is_normalized_term_expected,
-                    normalized_term,
-                    data.term,
-                ) {
+                if let Err(new_err) =
+                    ocx.eq(&obligation.cause, obligation.param_env, expected, actual)
+                {
                     (Some((data, is_normalized_term_expected, normalized_term, data.term)), new_err)
                 } else {
                     (None, error.err)
@@ -1908,6 +1978,9 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                             ct_op: |ct| ct.normalize(self.tcx, ty::ParamEnv::empty()),
                         },
                     );
+                    if cand.references_error() {
+                        return false;
+                    }
                     err.highlighted_help(vec![
                         StringPart::normal(format!("the trait `{}` ", cand.print_trait_sugared())),
                         StringPart::highlighted("is"),
@@ -1932,7 +2005,8 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         }
 
         let other = if other { "other " } else { "" };
-        let report = |candidates: Vec<TraitRef<'tcx>>, err: &mut Diag<'_>| {
+        let report = |mut candidates: Vec<TraitRef<'tcx>>, err: &mut Diag<'_>| {
+            candidates.retain(|tr| !tr.references_error());
             if candidates.is_empty() {
                 return false;
             }
@@ -2960,11 +3034,10 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
             dst: trait_ref.args.type_at(0),
             src: trait_ref.args.type_at(1),
         };
-        let scope = trait_ref.args.type_at(2);
         let Some(assume) = rustc_transmute::Assume::from_const(
             self.infcx.tcx,
             obligation.param_env,
-            trait_ref.args.const_at(3),
+            trait_ref.args.const_at(2),
         ) else {
             self.dcx().span_delayed_bug(
                 span,
@@ -2976,15 +3049,12 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
         match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable(
             obligation.cause,
             src_and_dst,
-            scope,
             assume,
         ) {
             Answer::No(reason) => {
                 let dst = trait_ref.args.type_at(0);
                 let src = trait_ref.args.type_at(1);
-                let err_msg = format!(
-                    "`{src}` cannot be safely transmuted into `{dst}` in the defining scope of `{scope}`"
-                );
+                let err_msg = format!("`{src}` cannot be safely transmuted into `{dst}`");
                 let safe_transmute_explanation = match reason {
                     rustc_transmute::Reason::SrcIsUnspecified => {
                         format!("`{src}` does not have a well-specified layout")
@@ -2998,9 +3068,9 @@ impl<'tcx> TypeErrCtxt<'_, 'tcx> {
                         format!("At least one value of `{src}` isn't a bit-valid value of `{dst}`")
                     }
 
-                    rustc_transmute::Reason::DstIsPrivate => format!(
-                        "`{dst}` is or contains a type or field that is not visible in that scope"
-                    ),
+                    rustc_transmute::Reason::DstMayHaveSafetyInvariants => {
+                        format!("`{dst}` may carry safety invariants")
+                    }
                     rustc_transmute::Reason::DstIsTooBig => {
                         format!("The size of `{src}` is smaller than the size of `{dst}`")
                     }
diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs
index b91698af942..2fd64f474d5 100644
--- a/compiler/rustc_trait_selection/src/traits/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs
@@ -138,7 +138,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> {
         _infcx: &InferCtxt<'tcx>,
     ) -> Vec<FulfillmentError<'tcx>> {
         self.predicates
-            .to_errors(FulfillmentErrorCode::Ambiguity { overflow: false })
+            .to_errors(FulfillmentErrorCode::Ambiguity { overflow: None })
             .into_iter()
             .map(to_fulfillment_error)
             .collect()
diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs
index 32447aca390..cc8b8f72cf3 100644
--- a/compiler/rustc_trait_selection/src/traits/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/mod.rs
@@ -435,8 +435,8 @@ fn is_impossible_associated_item(
         trait_item_def_id: DefId,
     }
     impl<'tcx> ty::TypeVisitor<TyCtxt<'tcx>> for ReferencesOnlyParentGenerics<'tcx> {
-        type BreakTy = ();
-        fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        type Result = ControlFlow<()>;
+        fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
             // If this is a parameter from the trait item's own generics, then bail
             if let ty::Param(param) = t.kind()
                 && let param_def_id = self.generics.type_param(param, self.tcx).def_id
@@ -446,7 +446,7 @@ fn is_impossible_associated_item(
             }
             t.super_visit_with(self)
         }
-        fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_region(&mut self, r: ty::Region<'tcx>) -> Self::Result {
             if let ty::ReEarlyParam(param) = r.kind()
                 && let param_def_id = self.generics.region_param(&param, self.tcx).def_id
                 && self.tcx.parent(param_def_id) == self.trait_item_def_id
@@ -455,7 +455,7 @@ fn is_impossible_associated_item(
             }
             ControlFlow::Continue(())
         }
-        fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_const(&mut self, ct: ty::Const<'tcx>) -> Self::Result {
             if let ty::ConstKind::Param(param) = ct.kind()
                 && let param_def_id = self.generics.const_param(&param, self.tcx).def_id
                 && self.tcx.parent(param_def_id) == self.trait_item_def_id
diff --git a/compiler/rustc_trait_selection/src/traits/object_safety.rs b/compiler/rustc_trait_selection/src/traits/object_safety.rs
index 7b715984c2b..1816b98a636 100644
--- a/compiler/rustc_trait_selection/src/traits/object_safety.rs
+++ b/compiler/rustc_trait_selection/src/traits/object_safety.rs
@@ -834,9 +834,9 @@ fn contains_illegal_self_type_reference<'tcx, T: TypeVisitable<TyCtxt<'tcx>>>(
     }
 
     impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for IllegalSelfTypeVisitor<'tcx> {
-        type BreakTy = ();
+        type Result = ControlFlow<()>;
 
-        fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
             match t.kind() {
                 ty::Param(_) => {
                     if t == self.tcx.types.self_param {
@@ -887,7 +887,7 @@ fn contains_illegal_self_type_reference<'tcx, T: TypeVisitable<TyCtxt<'tcx>>>(
             }
         }
 
-        fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+        fn visit_const(&mut self, ct: ty::Const<'tcx>) -> Self::Result {
             // Constants can only influence object safety if they are generic and reference `Self`.
             // This is only possible for unevaluated constants, so we walk these here.
             self.tcx.expand_abstract_consts(ct).super_visit_with(self)
diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
index e5f8e336860..c520e699bf5 100644
--- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs
+++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs
@@ -18,8 +18,6 @@ use rustc_middle::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitableEx
 use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor};
 use rustc_span::DUMMY_SP;
 
-use std::ops::ControlFlow;
-
 use super::NoSolution;
 
 pub use rustc_middle::traits::query::NormalizationResult;
@@ -123,28 +121,23 @@ struct MaxEscapingBoundVarVisitor {
 }
 
 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor {
-    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
-        &mut self,
-        t: &ty::Binder<'tcx, T>,
-    ) -> ControlFlow<Self::BreakTy> {
+    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, t: &ty::Binder<'tcx, T>) {
         self.outer_index.shift_in(1);
-        let result = t.super_visit_with(self);
+        t.super_visit_with(self);
         self.outer_index.shift_out(1);
-        result
     }
 
     #[inline]
-    fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_ty(&mut self, t: Ty<'tcx>) {
         if t.outer_exclusive_binder() > self.outer_index {
             self.escaping = self
                 .escaping
                 .max(t.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
         }
-        ControlFlow::Continue(())
     }
 
     #[inline]
-    fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_region(&mut self, r: ty::Region<'tcx>) {
         match *r {
             ty::ReBound(debruijn, _) if debruijn > self.outer_index => {
                 self.escaping =
@@ -152,16 +145,14 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for MaxEscapingBoundVarVisitor {
             }
             _ => {}
         }
-        ControlFlow::Continue(())
     }
 
-    fn visit_const(&mut self, ct: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_const(&mut self, ct: ty::Const<'tcx>) {
         if ct.outer_exclusive_binder() > self.outer_index {
             self.escaping = self
                 .escaping
                 .max(ct.outer_exclusive_binder().as_usize() - self.outer_index.as_usize());
         }
-        ControlFlow::Continue(())
     }
 }
 
diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
index b8733bab27b..70f6b240ab7 100644
--- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs
@@ -310,8 +310,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     .collect(),
                 Condition::IfTransmutable { src, dst } => {
                     let trait_def_id = obligation.predicate.def_id();
-                    let scope = predicate.trait_ref.args.type_at(2);
-                    let assume_const = predicate.trait_ref.args.const_at(3);
+                    let assume_const = predicate.trait_ref.args.const_at(2);
                     let make_obl = |from_ty, to_ty| {
                         let trait_ref1 = ty::TraitRef::new(
                             tcx,
@@ -319,7 +318,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             [
                                 ty::GenericArg::from(to_ty),
                                 ty::GenericArg::from(from_ty),
-                                ty::GenericArg::from(scope),
                                 ty::GenericArg::from(assume_const),
                             ],
                         );
@@ -355,7 +353,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let Some(assume) = rustc_transmute::Assume::from_const(
             self.infcx.tcx,
             obligation.param_env,
-            predicate.trait_ref.args.const_at(3),
+            predicate.trait_ref.args.const_at(2),
         ) else {
             return Err(Unimplemented);
         };
@@ -367,7 +365,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         let maybe_transmutable = transmute_env.is_transmutable(
             obligation.cause.clone(),
             rustc_transmute::Types { dst, src },
-            predicate.trait_ref.args.type_at(2),
             assume,
         );
 
diff --git a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs
index b329739609c..f5bc6c3ad2c 100644
--- a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs
@@ -39,6 +39,7 @@ pub struct OverlapError<'tcx> {
     pub self_ty: Option<Ty<'tcx>>,
     pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause<'tcx>>,
     pub involves_placeholder: bool,
+    pub overflowing_predicates: Vec<ty::Predicate<'tcx>>,
 }
 
 /// Given the generic parameters for the requested impl, translate it to the generic parameters
@@ -435,6 +436,14 @@ fn report_conflicting_impls<'tcx>(
         if overlap.involves_placeholder {
             coherence::add_placeholder_note(err);
         }
+
+        if !overlap.overflowing_predicates.is_empty() {
+            coherence::suggest_increasing_recursion_limit(
+                tcx,
+                err,
+                &overlap.overflowing_predicates,
+            );
+        }
     }
 
     let msg = DelayDm(|| {
diff --git a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
index f3b77d68922..95db9e2092f 100644
--- a/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
+++ b/compiler/rustc_trait_selection/src/traits/specialize/specialization_graph.rs
@@ -103,6 +103,7 @@ impl<'tcx> Children {
                     self_ty: self_ty.has_concrete_skeleton().then_some(self_ty),
                     intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
                     involves_placeholder: overlap.involves_placeholder,
+                    overflowing_predicates: overlap.overflowing_predicates,
                 }
             };
 
diff --git a/compiler/rustc_trait_selection/src/traits/structural_match.rs b/compiler/rustc_trait_selection/src/traits/structural_match.rs
index e6b42f15d51..b89406ca023 100644
--- a/compiler/rustc_trait_selection/src/traits/structural_match.rs
+++ b/compiler/rustc_trait_selection/src/traits/structural_match.rs
@@ -53,9 +53,9 @@ impl<'tcx> Search<'tcx> {
 }
 
 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for Search<'tcx> {
-    type BreakTy = Ty<'tcx>;
+    type Result = ControlFlow<Ty<'tcx>>;
 
-    fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
+    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
         debug!("Search visiting ty: {:?}", ty);
 
         let (adt_def, args) = match *ty.kind() {