Merging upstream version 1.74.1+dfsg1.

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

2 files changed, 165 insertions, 90 deletions

diff --git a/compiler/rustc_middle/src/traits/solve/inspect.rs b/compiler/rustc_middle/src/traits/solve/inspect.rs
index 4e2af3816..e7e40bee6 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect.rs
@@ -1,32 +1,83 @@
+//! 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::{
-    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;
 
-#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
+/// 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,
 }
 
-#[derive(Eq, PartialEq, Hash, HashStable)]
+/// 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<'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 canonicalized_goal: CanonicalInput<'tcx>,
-
     pub kind: GoalEvaluationKind<'tcx>,
-    pub is_normalizes_to_hack: IsNormalizesToHack,
+    pub evaluation: CanonicalGoalEvaluation<'tcx>,
+    /// The nested goals from instantiating the query response.
     pub returned_goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>,
+}
 
+#[derive(Eq, PartialEq)]
+pub struct CanonicalGoalEvaluation<'tcx> {
+    pub goal: CanonicalInput<'tcx>,
+    pub kind: CanonicalGoalEvaluationKind<'tcx>,
     pub result: QueryResult<'tcx>,
 }
 
-#[derive(Eq, PartialEq, Hash, HashStable)]
-pub enum GoalEvaluationKind<'tcx> {
+#[derive(Eq, PartialEq)]
+pub enum CanonicalGoalEvaluationKind<'tcx> {
+    Overflow,
     CacheHit(CacheHit),
     Uncached { revisions: Vec<GoalEvaluationStep<'tcx>> },
 }
@@ -36,55 +87,69 @@ impl Debug for GoalEvaluation<'_> {
     }
 }
 
-#[derive(Eq, PartialEq, Hash, HashStable)]
+#[derive(Eq, PartialEq)]
 pub struct AddedGoalsEvaluation<'tcx> {
     pub evaluations: Vec<Vec<GoalEvaluation<'tcx>>>,
     pub result: Result<Certainty, NoSolution>,
 }
-impl Debug for AddedGoalsEvaluation<'_> {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter::new(f).format_nested_goal_evaluation(self)
-    }
-}
 
-#[derive(Eq, PartialEq, Hash, HashStable)]
+#[derive(Eq, PartialEq)]
 pub struct GoalEvaluationStep<'tcx> {
     pub instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>,
 
-    pub nested_goal_evaluations: Vec<AddedGoalsEvaluation<'tcx>>,
-    pub candidates: Vec<GoalCandidate<'tcx>>,
+    /// The actual evaluation of the goal, always `ProbeKind::Root`.
+    pub evaluation: Probe<'tcx>,
+}
 
-    pub result: QueryResult<'tcx>,
+/// A self-contained computation during trait solving. This either
+/// corresponds to a `EvalCtxt::probe(_X)` call or the root evaluation
+/// 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>,
 }
-impl Debug for GoalEvaluationStep<'_> {
+
+impl Debug for Probe<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter::new(f).format_evaluation_step(self)
+        ProofTreeFormatter::new(f).format_probe(self)
     }
 }
 
-#[derive(Eq, PartialEq, Hash, HashStable)]
-pub struct GoalCandidate<'tcx> {
-    pub nested_goal_evaluations: Vec<AddedGoalsEvaluation<'tcx>>,
-    pub candidates: Vec<GoalCandidate<'tcx>>,
-    pub kind: CandidateKind<'tcx>,
+#[derive(Eq, PartialEq)]
+pub enum ProbeStep<'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(Eq, PartialEq, Debug, Hash, HashStable)]
-pub enum CandidateKind<'tcx> {
+/// 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> },
     /// Probe entered when normalizing the self ty during candidate assembly
     NormalizedSelfTyAssembly,
-    /// A normal candidate for proving a goal
-    Candidate { name: String, result: QueryResult<'tcx> },
+    /// Some candidate to prove the current goal.
+    ///
+    /// FIXME: Remove this in favor of always using more strongly typed variants.
+    MiscCandidate { name: &'static str, result: QueryResult<'tcx> },
+    /// A candidate for proving a trait or alias-relate goal.
+    TraitCandidate { source: CandidateSource, result: QueryResult<'tcx> },
     /// Used in the probe that wraps normalizing the non-self type for the unsize
     /// trait, which is also structurally matched on.
     UnsizeAssembly,
     /// During upcasting from some source object to target object type, used to
     /// do a probe to find out what projection type(s) may be used to prove that
     /// the source type upholds all of the target type's object bounds.
-    UpcastProbe,
-}
-impl Debug for GoalCandidate<'_> {
-    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
-        ProofTreeFormatter::new(f).format_candidate(self)
-    }
+    UpcastProjectionCompatibility,
 }
diff --git a/compiler/rustc_middle/src/traits/solve/inspect/format.rs b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
index 8759fecb0..5733be00a 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect/format.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect/format.rs
@@ -39,44 +39,55 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
         func(&mut ProofTreeFormatter { f: &mut Indentor { f: self.f, on_newline: true } })
     }
 
-    pub(super) fn format_goal_evaluation(&mut self, goal: &GoalEvaluation<'_>) -> std::fmt::Result {
-        let goal_text = match goal.is_normalizes_to_hack {
-            IsNormalizesToHack::Yes => "NORMALIZES-TO HACK GOAL",
-            IsNormalizesToHack::No => "GOAL",
+    pub(super) fn format_goal_evaluation(&mut self, eval: &GoalEvaluation<'_>) -> std::fmt::Result {
+        let goal_text = match eval.kind {
+            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",
+            },
         };
-
-        writeln!(self.f, "{}: {:?}", goal_text, goal.uncanonicalized_goal)?;
-        writeln!(self.f, "CANONICALIZED: {:?}", goal.canonicalized_goal)?;
-
-        match &goal.kind {
-            GoalEvaluationKind::CacheHit(CacheHit::Global) => {
-                writeln!(self.f, "GLOBAL CACHE HIT: {:?}", goal.result)
-            }
-            GoalEvaluationKind::CacheHit(CacheHit::Provisional) => {
-                writeln!(self.f, "PROVISIONAL CACHE HIT: {:?}", goal.result)
-            }
-            GoalEvaluationKind::Uncached { revisions } => {
-                for (n, step) in revisions.iter().enumerate() {
-                    writeln!(self.f, "REVISION {n}: {:?}", step.result)?;
-                    self.nested(|this| this.format_evaluation_step(step))?;
-                }
-                writeln!(self.f, "RESULT: {:?}", goal.result)
-            }
-        }?;
-
-        if goal.returned_goals.len() > 0 {
+        writeln!(self.f, "{}: {:?}", goal_text, eval.uncanonicalized_goal)?;
+        self.nested(|this| this.format_canonical_goal_evaluation(&eval.evaluation))?;
+        if eval.returned_goals.len() > 0 {
             writeln!(self.f, "NESTED GOALS ADDED TO CALLER: [")?;
             self.nested(|this| {
-                for goal in goal.returned_goals.iter() {
+                for goal in eval.returned_goals.iter() {
                     writeln!(this.f, "ADDED GOAL: {goal:?},")?;
                 }
                 Ok(())
             })?;
 
-            writeln!(self.f, "]")?;
+            writeln!(self.f, "]")
+        } else {
+            Ok(())
         }
+    }
 
-        Ok(())
+    pub(super) fn format_canonical_goal_evaluation(
+        &mut self,
+        eval: &CanonicalGoalEvaluation<'_>,
+    ) -> std::fmt::Result {
+        writeln!(self.f, "GOAL: {:?}", eval.goal)?;
+
+        match &eval.kind {
+            CanonicalGoalEvaluationKind::Overflow => {
+                writeln!(self.f, "OVERFLOW: {:?}", eval.result)
+            }
+            CanonicalGoalEvaluationKind::CacheHit(CacheHit::Global) => {
+                writeln!(self.f, "GLOBAL CACHE HIT: {:?}", eval.result)
+            }
+            CanonicalGoalEvaluationKind::CacheHit(CacheHit::Provisional) => {
+                writeln!(self.f, "PROVISIONAL CACHE HIT: {:?}", eval.result)
+            }
+            CanonicalGoalEvaluationKind::Uncached { revisions } => {
+                for (n, step) in revisions.iter().enumerate() {
+                    writeln!(self.f, "REVISION {n}")?;
+                    self.nested(|this| this.format_evaluation_step(step))?;
+                }
+                writeln!(self.f, "RESULT: {:?}", eval.result)
+            }
+        }
     }
 
     pub(super) fn format_evaluation_step(
@@ -84,54 +95,53 @@ impl<'a, 'b> ProofTreeFormatter<'a, 'b> {
         evaluation_step: &GoalEvaluationStep<'_>,
     ) -> std::fmt::Result {
         writeln!(self.f, "INSTANTIATED: {:?}", evaluation_step.instantiated_goal)?;
-
-        for candidate in &evaluation_step.candidates {
-            self.nested(|this| this.format_candidate(candidate))?;
-        }
-        for nested in &evaluation_step.nested_goal_evaluations {
-            self.nested(|this| this.format_nested_goal_evaluation(nested))?;
-        }
-
-        Ok(())
+        self.format_probe(&evaluation_step.evaluation)
     }
 
-    pub(super) fn format_candidate(&mut self, candidate: &GoalCandidate<'_>) -> std::fmt::Result {
-        match &candidate.kind {
-            CandidateKind::NormalizedSelfTyAssembly => {
+    pub(super) fn format_probe(&mut self, probe: &Probe<'_>) -> std::fmt::Result {
+        match &probe.kind {
+            ProbeKind::Root { result } => {
+                writeln!(self.f, "ROOT RESULT: {result:?}")
+            }
+            ProbeKind::NormalizedSelfTyAssembly => {
                 writeln!(self.f, "NORMALIZING SELF TY FOR ASSEMBLY:")
             }
-            CandidateKind::UnsizeAssembly => {
+            ProbeKind::UnsizeAssembly => {
                 writeln!(self.f, "ASSEMBLING CANDIDATES FOR UNSIZING:")
             }
-            CandidateKind::UpcastProbe => {
+            ProbeKind::UpcastProjectionCompatibility => {
                 writeln!(self.f, "PROBING FOR PROJECTION COMPATIBILITY FOR UPCASTING:")
             }
-            CandidateKind::Candidate { name, result } => {
+            ProbeKind::MiscCandidate { name, result } => {
                 writeln!(self.f, "CANDIDATE {name}: {result:?}")
             }
+            ProbeKind::TraitCandidate { source, result } => {
+                writeln!(self.f, "CANDIDATE {source:?}: {result:?}")
+            }
         }?;
 
         self.nested(|this| {
-            for candidate in &candidate.candidates {
-                this.format_candidate(candidate)?;
-            }
-            for nested in &candidate.nested_goal_evaluations {
-                this.format_nested_goal_evaluation(nested)?;
+            for step in &probe.steps {
+                match step {
+                    ProbeStep::AddGoal(goal) => writeln!(this.f, "ADDED GOAL: {goal:?}")?,
+                    ProbeStep::EvaluateGoals(eval) => this.format_added_goals_evaluation(eval)?,
+                    ProbeStep::NestedProbe(probe) => this.format_probe(probe)?,
+                }
             }
             Ok(())
         })
     }
 
-    pub(super) fn format_nested_goal_evaluation(
+    pub(super) fn format_added_goals_evaluation(
         &mut self,
-        nested_goal_evaluation: &AddedGoalsEvaluation<'_>,
+        added_goals_evaluation: &AddedGoalsEvaluation<'_>,
     ) -> std::fmt::Result {
-        writeln!(self.f, "TRY_EVALUATE_ADDED_GOALS: {:?}", nested_goal_evaluation.result)?;
+        writeln!(self.f, "TRY_EVALUATE_ADDED_GOALS: {:?}", added_goals_evaluation.result)?;
 
-        for (n, revision) in nested_goal_evaluation.evaluations.iter().enumerate() {
-            writeln!(self.f, "REVISION {n}")?;
+        for (n, iterations) in added_goals_evaluation.evaluations.iter().enumerate() {
+            writeln!(self.f, "ITERATION {n}")?;
             self.nested(|this| {
-                for goal_evaluation in revision {
+                for goal_evaluation in iterations {
                     this.format_goal_evaluation(goal_evaluation)?;
                 }
                 Ok(())