Rollup merge of #124418 - compiler-errors:better-cause, r=lcnr

Use a proof tree visitor to refine the `Obligation` for error reporting in new solver

With the magic of `ProofTreeVisitor`, we can close the gap that we have on `ObligationCause`s being not as descriptive in the new trait solver.

r? lcnr

Needs some work and obviously documentation.

9 files changed, 203 insertions, 40 deletions

diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs
index 4c34bf88c7f..3ad6b68d129 100644
--- a/compiler/rustc_middle/src/traits/solve.rs
+++ b/compiler/rustc_middle/src/traits/solve.rs
@@ -273,6 +273,8 @@ pub enum GoalSource {
     /// they are from an impl where-clause. This is necessary due to
     /// backwards compatability, cc trait-system-refactor-initiatitive#70.
     ImplWhereBound,
+    /// Instantiating a higher-ranked goal and re-proving it.
+    InstantiateHigherRanked,
 }
 
 /// Possible ways the given goal can be proven.
diff --git a/compiler/rustc_middle/src/traits/solve/inspect/format.rs b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
index 2d73be387fd..11aa0e10931 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect/format.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
@@ -127,6 +127,7 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
                         let source = match source {
                             GoalSource::Misc => "misc",
                             GoalSource::ImplWhereBound => "impl where-bound",
+                            GoalSource::InstantiateHigherRanked => "higher-ranked goal",
                         };
                         writeln!(this.f, "ADDED GOAL ({source}): {goal:?}")?
                     }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 280975f63bd..f2ca42a0be9 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -58,15 +58,15 @@ pub(super) trait GoalKind<'tcx>:
     /// goal by equating it with the assumption.
     fn probe_and_consider_implied_clause(
         ecx: &mut EvalCtxt<'_, 'tcx>,
-        source: CandidateSource,
+        parent_source: CandidateSource,
         goal: Goal<'tcx, Self>,
         assumption: ty::Clause<'tcx>,
-        requirements: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>,
+        requirements: impl IntoIterator<Item = (GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)>,
     ) -> Result<Candidate<'tcx>, NoSolution> {
-        Self::probe_and_match_goal_against_assumption(ecx, source, goal, assumption, |ecx| {
-            // FIXME(-Znext-solver=coinductive): check whether this should be
-            // `GoalSource::ImplWhereBound` for any caller.
-            ecx.add_goals(GoalSource::Misc, requirements);
+        Self::probe_and_match_goal_against_assumption(ecx, parent_source, goal, assumption, |ecx| {
+            for (nested_source, goal) in requirements {
+                ecx.add_goal(nested_source, goal);
+            }
             ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
         })
     }
@@ -85,9 +85,8 @@ pub(super) trait GoalKind<'tcx>:
             let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else {
                 bug!("expected object type in `probe_and_consider_object_bound_candidate`");
             };
-            // FIXME(-Znext-solver=coinductive): Should this be `GoalSource::ImplWhereBound`?
             ecx.add_goals(
-                GoalSource::Misc,
+                GoalSource::ImplWhereBound,
                 structural_traits::predicates_for_object_candidate(
                     ecx,
                     goal.param_env,
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
index 6722abd709c..d6bf2b596ef 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs
@@ -90,6 +90,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         &mut self,
         certainty: Certainty,
     ) -> QueryResult<'tcx> {
+        self.inspect.make_canonical_response(certainty);
+
         let goals_certainty = self.try_evaluate_added_goals()?;
         assert_eq!(
             self.tainted,
@@ -98,8 +100,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             previous call to `try_evaluate_added_goals!`"
         );
 
-        self.inspect.make_canonical_response(certainty);
-
         // When normalizing, we've replaced the expected term with an unconstrained
         // inference variable. This means that we dropped information which could
         // have been important. We handle this by instead returning the nested goals
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 1710746ae50..bae1c6b6011 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs
@@ -454,7 +454,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
         } else {
             self.infcx.enter_forall(kind, |kind| {
                 let goal = goal.with(self.tcx(), ty::Binder::dummy(kind));
-                self.add_goal(GoalSource::Misc, goal);
+                self.add_goal(GoalSource::InstantiateHigherRanked, goal);
                 self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             })
         }
diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs
index 3fa409eefff..796222129f1 100644
--- a/compiler/rustc_trait_selection/src/solve/fulfill.rs
+++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs
@@ -1,15 +1,19 @@
 use std::mem;
+use std::ops::ControlFlow;
 
 use rustc_infer::infer::InferCtxt;
-use rustc_infer::traits::solve::MaybeCause;
+use rustc_infer::traits::query::NoSolution;
+use rustc_infer::traits::solve::inspect::ProbeKind;
+use rustc_infer::traits::solve::{CandidateSource, GoalSource, MaybeCause};
 use rustc_infer::traits::{
-    query::NoSolution, FulfillmentError, FulfillmentErrorCode, MismatchedProjectionTypes,
-    PredicateObligation, SelectionError, TraitEngine,
+    self, FulfillmentError, FulfillmentErrorCode, MismatchedProjectionTypes, Obligation,
+    ObligationCause, PredicateObligation, SelectionError, TraitEngine,
 };
-use rustc_middle::ty;
 use rustc_middle::ty::error::{ExpectedFound, TypeError};
+use rustc_middle::ty::{self, TyCtxt};
 
 use super::eval_ctxt::GenerateProofTree;
+use super::inspect::{ProofTreeInferCtxtExt, ProofTreeVisitor};
 use super::{Certainty, InferCtxtEvalExt};
 
 /// A trait engine using the new trait solver.
@@ -133,9 +137,9 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
             .collect();
 
         errors.extend(self.obligations.overflowed.drain(..).map(|obligation| FulfillmentError {
-            root_obligation: obligation.clone(),
+            obligation: find_best_leaf_obligation(infcx, &obligation),
             code: FulfillmentErrorCode::Ambiguity { overflow: Some(true) },
-            obligation,
+            root_obligation: obligation,
         }));
 
         errors
@@ -192,8 +196,10 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> {
 
 fn fulfillment_error_for_no_solution<'tcx>(
     infcx: &InferCtxt<'tcx>,
-    obligation: PredicateObligation<'tcx>,
+    root_obligation: PredicateObligation<'tcx>,
 ) -> FulfillmentError<'tcx> {
+    let obligation = find_best_leaf_obligation(infcx, &root_obligation);
+
     let code = match obligation.predicate.kind().skip_binder() {
         ty::PredicateKind::Clause(ty::ClauseKind::Projection(_)) => {
             FulfillmentErrorCode::ProjectionError(
@@ -234,7 +240,8 @@ fn fulfillment_error_for_no_solution<'tcx>(
             bug!("unexpected goal: {obligation:?}")
         }
     };
-    FulfillmentError { root_obligation: obligation.clone(), code, obligation }
+
+    FulfillmentError { obligation, code, root_obligation }
 }
 
 fn fulfillment_error_for_stalled<'tcx>(
@@ -258,5 +265,136 @@ fn fulfillment_error_for_stalled<'tcx>(
         }
     });
 
-    FulfillmentError { obligation: obligation.clone(), code, root_obligation: obligation }
+    FulfillmentError {
+        obligation: find_best_leaf_obligation(infcx, &obligation),
+        code,
+        root_obligation: obligation,
+    }
+}
+
+fn find_best_leaf_obligation<'tcx>(
+    infcx: &InferCtxt<'tcx>,
+    obligation: &PredicateObligation<'tcx>,
+) -> PredicateObligation<'tcx> {
+    let obligation = infcx.resolve_vars_if_possible(obligation.clone());
+    infcx
+        .visit_proof_tree(
+            obligation.clone().into(),
+            &mut BestObligation { obligation: obligation.clone() },
+        )
+        .break_value()
+        .unwrap_or(obligation)
+}
+
+struct BestObligation<'tcx> {
+    obligation: PredicateObligation<'tcx>,
+}
+
+impl<'tcx> BestObligation<'tcx> {
+    fn with_derived_obligation(
+        &mut self,
+        derived_obligation: PredicateObligation<'tcx>,
+        and_then: impl FnOnce(&mut Self) -> <Self as ProofTreeVisitor<'tcx>>::Result,
+    ) -> <Self as ProofTreeVisitor<'tcx>>::Result {
+        let old_obligation = std::mem::replace(&mut self.obligation, derived_obligation);
+        let res = and_then(self);
+        self.obligation = old_obligation;
+        res
+    }
+}
+
+impl<'tcx> ProofTreeVisitor<'tcx> for BestObligation<'tcx> {
+    type Result = ControlFlow<PredicateObligation<'tcx>>;
+
+    fn span(&self) -> rustc_span::Span {
+        self.obligation.cause.span
+    }
+
+    fn visit_goal(&mut self, goal: &super::inspect::InspectGoal<'_, 'tcx>) -> Self::Result {
+        // FIXME: Throw out candidates that have no failing WC and >0 failing misc goal.
+        // This most likely means that the goal just didn't unify at all, e.g. a param
+        // candidate with an alias in it.
+        let candidates = goal.candidates();
+
+        let [candidate] = candidates.as_slice() else {
+            return ControlFlow::Break(self.obligation.clone());
+        };
+
+        // FIXME: Could we extract a trait ref from a projection here too?
+        // FIXME: Also, what about considering >1 layer up the stack? May be necessary
+        // for normalizes-to.
+        let Some(parent_trait_pred) = goal.goal().predicate.to_opt_poly_trait_pred() else {
+            return ControlFlow::Break(self.obligation.clone());
+        };
+
+        let tcx = goal.infcx().tcx;
+        let mut impl_where_bound_count = 0;
+        for nested_goal in candidate.instantiate_nested_goals(self.span()) {
+            let obligation;
+            match nested_goal.source() {
+                GoalSource::Misc => {
+                    continue;
+                }
+                GoalSource::ImplWhereBound => {
+                    obligation = Obligation {
+                        cause: derive_cause(
+                            tcx,
+                            candidate.kind(),
+                            self.obligation.cause.clone(),
+                            impl_where_bound_count,
+                            parent_trait_pred,
+                        ),
+                        param_env: nested_goal.goal().param_env,
+                        predicate: nested_goal.goal().predicate,
+                        recursion_depth: self.obligation.recursion_depth + 1,
+                    };
+                    impl_where_bound_count += 1;
+                }
+                GoalSource::InstantiateHigherRanked => {
+                    obligation = self.obligation.clone();
+                }
+            }
+
+            // Skip nested goals that hold.
+            //FIXME: We should change the max allowed certainty based on if we're
+            // visiting an ambiguity or error obligation.
+            if matches!(nested_goal.result(), Ok(Certainty::Yes)) {
+                continue;
+            }
+
+            self.with_derived_obligation(obligation, |this| nested_goal.visit_with(this))?;
+        }
+
+        ControlFlow::Break(self.obligation.clone())
+    }
+}
+
+fn derive_cause<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    candidate_kind: ProbeKind<'tcx>,
+    mut cause: ObligationCause<'tcx>,
+    idx: usize,
+    parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
+) -> ObligationCause<'tcx> {
+    match candidate_kind {
+        ProbeKind::TraitCandidate { source: CandidateSource::Impl(impl_def_id), result: _ } => {
+            if let Some((_, span)) =
+                tcx.predicates_of(impl_def_id).instantiate_identity(tcx).iter().nth(idx)
+            {
+                cause = cause.derived_cause(parent_trait_pred, |derived| {
+                    traits::ImplDerivedObligation(Box::new(traits::ImplDerivedObligationCause {
+                        derived,
+                        impl_or_alias_def_id: impl_def_id,
+                        impl_def_predicate_index: Some(idx),
+                        span,
+                    }))
+                })
+            }
+        }
+        ProbeKind::TraitCandidate { source: CandidateSource::BuiltinImpl(..), result: _ } => {
+            cause = cause.derived_cause(parent_trait_pred, traits::BuiltinDerivedObligation);
+        }
+        _ => {}
+    };
+    cause
 }
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
index 97de25295b8..4f79f1b2aaf 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs
@@ -41,6 +41,7 @@ pub struct InspectGoal<'a, 'tcx> {
     result: Result<Certainty, NoSolution>,
     evaluation_kind: inspect::CanonicalGoalEvaluationKind<'tcx>,
     normalizes_to_term_hack: Option<NormalizesToTermHack<'tcx>>,
+    source: GoalSource,
 }
 
 /// The expected term of a `NormalizesTo` goal gets replaced
@@ -90,7 +91,7 @@ impl<'tcx> NormalizesToTermHack<'tcx> {
 pub struct InspectCandidate<'a, 'tcx> {
     goal: &'a InspectGoal<'a, 'tcx>,
     kind: inspect::ProbeKind<'tcx>,
-    nested_goals: Vec<inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>>,
+    nested_goals: Vec<(GoalSource, inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>)>,
     final_state: inspect::CanonicalState<'tcx, ()>,
     result: QueryResult<'tcx>,
     shallow_certainty: Certainty,
@@ -125,10 +126,8 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
     /// back their inference constraints. This function modifies
     /// the state of the `infcx`.
     pub fn visit_nested_no_probe<V: ProofTreeVisitor<'tcx>>(&self, visitor: &mut V) -> V::Result {
-        if self.goal.depth < visitor.config().max_depth {
-            for goal in self.instantiate_nested_goals(visitor.span()) {
-                try_visit!(visitor.visit_goal(&goal));
-            }
+        for goal in self.instantiate_nested_goals(visitor.span()) {
+            try_visit!(goal.visit_with(visitor));
         }
 
         V::Result::output()
@@ -143,13 +142,16 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
         let instantiated_goals: Vec<_> = self
             .nested_goals
             .iter()
-            .map(|goal| {
-                canonical::instantiate_canonical_state(
-                    infcx,
-                    span,
-                    param_env,
-                    &mut orig_values,
-                    *goal,
+            .map(|(source, goal)| {
+                (
+                    *source,
+                    canonical::instantiate_canonical_state(
+                        infcx,
+                        span,
+                        param_env,
+                        &mut orig_values,
+                        *goal,
+                    ),
                 )
             })
             .collect();
@@ -171,7 +173,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
 
         instantiated_goals
             .into_iter()
-            .map(|goal| match goal.predicate.kind().no_bound_vars() {
+            .map(|(source, goal)| match goal.predicate.kind().no_bound_vars() {
                 Some(ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term })) => {
                     let unconstrained_term = match term.unpack() {
                         ty::TermKind::Ty(_) => infcx
@@ -195,6 +197,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                         self.goal.depth + 1,
                         proof_tree.unwrap(),
                         Some(NormalizesToTermHack { term, unconstrained_term }),
+                        source,
                     )
                 }
                 _ => InspectGoal::new(
@@ -202,6 +205,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> {
                     self.goal.depth + 1,
                     infcx.evaluate_root_goal(goal, GenerateProofTree::Yes).1.unwrap(),
                     None,
+                    source,
                 ),
             })
             .collect()
@@ -227,16 +231,23 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
         self.result
     }
 
+    pub fn source(&self) -> GoalSource {
+        self.source
+    }
+
     fn candidates_recur(
         &'a self,
         candidates: &mut Vec<InspectCandidate<'a, 'tcx>>,
-        nested_goals: &mut Vec<inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>>,
+        nested_goals: &mut Vec<(
+            GoalSource,
+            inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>,
+        )>,
         probe: &inspect::Probe<'tcx>,
     ) {
         let mut shallow_certainty = None;
         for step in &probe.steps {
             match step {
-                &inspect::ProbeStep::AddGoal(_source, goal) => nested_goals.push(goal),
+                &inspect::ProbeStep::AddGoal(source, goal) => nested_goals.push((source, goal)),
                 inspect::ProbeStep::NestedProbe(ref probe) => {
                     // Nested probes have to prove goals added in their parent
                     // but do not leak them, so we truncate the added goals
@@ -319,6 +330,7 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
         depth: usize,
         root: inspect::GoalEvaluation<'tcx>,
         normalizes_to_term_hack: Option<NormalizesToTermHack<'tcx>>,
+        source: GoalSource,
     ) -> Self {
         let inspect::GoalEvaluation { uncanonicalized_goal, kind, evaluation } = root;
         let inspect::GoalEvaluationKind::Root { orig_values } = kind else { unreachable!() };
@@ -341,8 +353,17 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> {
             result,
             evaluation_kind: evaluation.kind,
             normalizes_to_term_hack,
+            source,
         }
     }
+
+    pub(crate) fn visit_with<V: ProofTreeVisitor<'tcx>>(&self, visitor: &mut V) -> V::Result {
+        if self.depth < visitor.config().max_depth {
+            try_visit!(visitor.visit_goal(self));
+        }
+
+        V::Result::output()
+    }
 }
 
 /// The public API to interact with proof trees.
@@ -367,6 +388,6 @@ impl<'tcx> InferCtxt<'tcx> {
     ) -> V::Result {
         let (_, proof_tree) = self.evaluate_root_goal(goal, GenerateProofTree::Yes);
         let proof_tree = proof_tree.unwrap();
-        visitor.visit_goal(&InspectGoal::new(self, 0, proof_tree, None))
+        visitor.visit_goal(&InspectGoal::new(self, 0, proof_tree, None, GoalSource::Misc))
     }
 }
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 dab87fffe46..f886c588650 100644
--- a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs
@@ -389,7 +389,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> {
             CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
             goal,
             pred,
-            [goal.with(tcx, output_is_sized_pred)],
+            [(GoalSource::ImplWhereBound, goal.with(tcx, output_is_sized_pred))],
         )
     }
 
@@ -473,7 +473,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> {
             pred,
             [goal.with(tcx, output_is_sized_pred)]
                 .into_iter()
-                .chain(nested_preds.into_iter().map(|pred| goal.with(tcx, pred))),
+                .chain(nested_preds.into_iter().map(|pred| goal.with(tcx, pred)))
+                .map(|goal| (GoalSource::ImplWhereBound, goal)),
         )
     }
 
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index c8cb14abb55..d2b893d6383 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -321,7 +321,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             CandidateSource::BuiltinImpl(BuiltinImplSource::Misc),
             goal,
             pred,
-            [goal.with(tcx, output_is_sized_pred)],
+            [(GoalSource::ImplWhereBound, goal.with(tcx, output_is_sized_pred))],
         )
     }
 
@@ -367,7 +367,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             pred,
             [goal.with(tcx, output_is_sized_pred)]
                 .into_iter()
-                .chain(nested_preds.into_iter().map(|pred| goal.with(tcx, pred))),
+                .chain(nested_preds.into_iter().map(|pred| goal.with(tcx, pred)))
+                .map(|goal| (GoalSource::ImplWhereBound, goal)),
         )
     }