Auto merge of #115996 - lcnr:intercrate_ambiguity_causes-uwu, r=compiler-errors

implement `intercrate_ambiguity_causes` in the new solver

I added some comments but this is still somewhat of a mess. I think we should for the most part be able to treat all of this as a black box, so I can accept that this code isn't too great.

I also believe that some of the weirdness here is unavoidable, as proof trees - and their visitor - hide semantically relevant information, so they cannot perfectly represent the actual solver behavior.

There are some known bugs here when testing with `./x.py test tests/ui --bless -- --target-rustcflags -Ztrait-solver=next-coherence`. While I haven't diagnosed them all in detail I believe we are able to handle them all separately

- `structurally_normalize` currently does not normalize opaque types, resulting in divergence between the solver internal `trait_ref_is_knowable` and the one when computing intercrate ambiguity causes.
- we don't add an `intercrate_ambiguity_cause` for reserved impls
- we should `deeply_normalize` the trait ref before printing it, that requires a "best effort" version of `deeply_normalize`

r? `@compiler-errors`

2 files changed, 59 insertions, 9 deletions

diff --git a/compiler/rustc_middle/src/traits/solve/inspect.rs b/compiler/rustc_middle/src/traits/solve/inspect.rs
index c3ed40867cf..e7e40bee6b9 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect.rs
@@ -1,30 +1,70 @@
+//! Data structure used to inspect trait solver behavior.
+//!
+//! During trait solving we optionally build "proof trees", the root of
+//! which is a [GoalEvaluation] with [GoalEvaluationKind::Root]. These
+//! trees are used to improve the debug experience and are also used by
+//! the compiler itself to provide necessary context for error messages.
+//!
+//! Because each nested goal in the solver gets [canonicalized] separately
+//! and we discard inference progress via "probes", we cannot mechanically
+//! use proof trees without somehow "lifting up" data local to the current
+//! `InferCtxt`. Any data used mechanically is therefore canonicalized and
+//! stored as [CanonicalState]. As printing canonicalized data worsens the
+//! debugging dumps, we do not simply canonicalize everything.
+//!
+//! This means proof trees contain inference variables and placeholders
+//! local to a different `InferCtxt` which must not be used with the
+//! current one.
+//!
+//! [canonicalized]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html
+
 use super::{
-    CandidateSource, CanonicalInput, Certainty, Goal, IsNormalizesToHack, NoSolution, QueryInput,
-    QueryResult,
+    CandidateSource, Canonical, CanonicalInput, Certainty, Goal, IsNormalizesToHack, NoSolution,
+    QueryInput, QueryResult,
 };
-use crate::ty;
+use crate::{infer::canonical::CanonicalVarValues, ty};
 use format::ProofTreeFormatter;
 use std::fmt::{Debug, Write};
 
 mod format;
 
+/// Some `data` together with information about how they relate to the input
+/// of the canonical query.
+///
+/// This is only ever used as [CanonicalState]. Any type information in proof
+/// trees used mechanically has to be canonicalized as we otherwise leak
+/// inference variables from a nested `InferCtxt`.
+#[derive(Debug, Clone, Copy, Eq, PartialEq, TypeFoldable, TypeVisitable)]
+pub struct State<'tcx, T> {
+    pub var_values: CanonicalVarValues<'tcx>,
+    pub data: T,
+}
+
+pub type CanonicalState<'tcx, T> = Canonical<'tcx, State<'tcx, T>>;
+
 #[derive(Debug, Eq, PartialEq)]
 pub enum CacheHit {
     Provisional,
     Global,
 }
 
+/// When evaluating the root goals we also store the
+/// original values for the `CanonicalVarValues` of the
+/// canonicalized goal. We use this to map any [CanonicalState]
+/// from the local `InferCtxt` of the solver query to
+/// the `InferCtxt` of the caller.
 #[derive(Eq, PartialEq)]
-pub enum GoalEvaluationKind {
-    Root,
+pub enum GoalEvaluationKind<'tcx> {
+    Root { orig_values: Vec<ty::GenericArg<'tcx>> },
     Nested { is_normalizes_to_hack: IsNormalizesToHack },
 }
 
 #[derive(Eq, PartialEq)]
 pub struct GoalEvaluation<'tcx> {
     pub uncanonicalized_goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    pub kind: GoalEvaluationKind,
+    pub kind: GoalEvaluationKind<'tcx>,
     pub evaluation: CanonicalGoalEvaluation<'tcx>,
+    /// The nested goals from instantiating the query response.
     pub returned_goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
 }
 
@@ -66,6 +106,7 @@ pub struct GoalEvaluationStep<'tcx> {
 /// of a goal.
 #[derive(Eq, PartialEq)]
 pub struct Probe<'tcx> {
+    /// What happened inside of this probe in chronological order.
     pub steps: Vec<ProbeStep<'tcx>>,
     pub kind: ProbeKind<'tcx>,
 }
@@ -78,12 +119,21 @@ impl Debug for Probe<'_> {
 
 #[derive(Eq, PartialEq)]
 pub enum ProbeStep<'tcx> {
-    AddGoal(Goal<'tcx, ty::Predicate<'tcx>>),
+    /// We added a goal to the `EvalCtxt` which will get proven
+    /// the next time `EvalCtxt::try_evaluate_added_goals` is called.
+    AddGoal(CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>),
+    /// The inside of a `EvalCtxt::try_evaluate_added_goals` call.
     EvaluateGoals(AddedGoalsEvaluation<'tcx>),
+    /// A call to `probe` while proving the current goal. This is
+    /// used whenever there are multiple candidates to prove the
+    /// current goalby .
     NestedProbe(Probe<'tcx>),
 }
 
-#[derive(Debug, PartialEq, Eq)]
+/// What kind of probe we're in. In case the probe represents a candidate, or
+/// the final result of the current goal - via [ProbeKind::Root] - we also
+/// store the [QueryResult].
+#[derive(Debug, PartialEq, Eq, Clone, Copy)]
 pub enum ProbeKind<'tcx> {
     /// The root inference context while proving a goal.
     Root { result: QueryResult<'tcx> },
diff --git a/compiler/rustc_middle/src/traits/solve/inspect/format.rs b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
index d33e83ae1ed..5733be00adf 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect/format.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
@@ -41,7 +41,7 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
 
     pub(super) fn format_goal_evaluation(&mut self, eval: &GoalEvaluation<'_>) -> std::fmt::Result {
         let goal_text = match eval.kind {
-            GoalEvaluationKind::Root => "ROOT GOAL",
+            GoalEvaluationKind::Root { orig_values: _ } => "ROOT GOAL",
             GoalEvaluationKind::Nested { is_normalizes_to_hack } => match is_normalizes_to_hack {
                 IsNormalizesToHack::No => "GOAL",
                 IsNormalizesToHack::Yes => "NORMALIZES-TO HACK GOAL",