introduce a separate set of types for finalized proof trees

7 files changed, 335 insertions, 188 deletions

diff --git a/compiler/rustc_middle/src/traits/solve/inspect.rs b/compiler/rustc_middle/src/traits/solve/inspect.rs
index 6060e8f3546..0379833d503 100644
--- a/compiler/rustc_middle/src/traits/solve/inspect.rs
+++ b/compiler/rustc_middle/src/traits/solve/inspect.rs
@@ -2,7 +2,7 @@ use super::{CanonicalInput, Certainty, Goal, NoSolution, QueryInput, QueryResult
 use crate::ty;
 use std::fmt::{Debug, Write};
 
-#[derive(Eq, PartialEq, Hash, HashStable)]
+#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
 pub enum CacheHit {
     Provisional,
     Global,
@@ -11,16 +11,16 @@ pub enum CacheHit {
 #[derive(Eq, PartialEq, Hash, HashStable)]
 pub struct GoalEvaluation<'tcx> {
     pub uncanonicalized_goal: Goal<'tcx, ty::Predicate<'tcx>>,
-    pub canonicalized_goal: Option<CanonicalInput<'tcx>>,
-
-    /// To handle coinductive cycles we can end up re-evaluating a goal
-    /// multiple times with different results for a nested goal. Each rerun
-    /// is represented as an entry in this vec.
-    pub evaluation_steps: Vec<GoalEvaluationStep<'tcx>>,
+    pub canonicalized_goal: CanonicalInput<'tcx>,
 
-    pub cache_hit: Option<CacheHit>,
+    pub kind: GoalEvaluationKind<'tcx>,
 
-    pub result: Option<QueryResult<'tcx>>,
+    pub result: QueryResult<'tcx>,
+}
+#[derive(Eq, PartialEq, Hash, HashStable)]
+pub enum GoalEvaluationKind<'tcx> {
+    CacheHit(CacheHit),
+    Uncached { revisions: Vec<GoalEvaluationStep<'tcx>> },
 }
 impl Debug for GoalEvaluation<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -31,7 +31,7 @@ impl Debug for GoalEvaluation<'_> {
 #[derive(Eq, PartialEq, Hash, HashStable)]
 pub struct AddedGoalsEvaluation<'tcx> {
     pub evaluations: Vec<Vec<GoalEvaluation<'tcx>>>,
-    pub result: Option<Result<Certainty, NoSolution>>,
+    pub result: Result<Certainty, NoSolution>,
 }
 impl Debug for AddedGoalsEvaluation<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -46,7 +46,7 @@ pub struct GoalEvaluationStep<'tcx> {
     pub nested_goal_evaluations: Vec<AddedGoalsEvaluation<'tcx>>,
     pub candidates: Vec<GoalCandidate<'tcx>>,
 
-    pub result: Option<QueryResult<'tcx>>,
+    pub result: QueryResult<'tcx>,
 }
 impl Debug for GoalEvaluationStep<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -58,9 +58,14 @@ impl Debug for GoalEvaluationStep<'_> {
 pub struct GoalCandidate<'tcx> {
     pub nested_goal_evaluations: Vec<AddedGoalsEvaluation<'tcx>>,
     pub candidates: Vec<GoalCandidate<'tcx>>,
-
-    pub name: Option<String>,
-    pub result: Option<QueryResult<'tcx>>,
+    pub kind: CandidateKind<'tcx>,
+}
+#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
+pub enum CandidateKind<'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> },
 }
 impl Debug for GoalCandidate<'_> {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
@@ -97,19 +102,23 @@ impl ProofTreeFormatter<'_, '_> {
         writeln!(f, "GOAL: {:?}", goal.uncanonicalized_goal)?;
         writeln!(f, "CANONICALIZED: {:?}", goal.canonicalized_goal)?;
 
-        match goal.cache_hit {
-            Some(CacheHit::Global) => writeln!(f, "GLOBAL CACHE HIT: {:?}", goal.result),
-            Some(CacheHit::Provisional) => writeln!(f, "PROVISIONAL CACHE HIT: {:?}", goal.result),
-            None => {
-                for (n, step) in goal.evaluation_steps.iter().enumerate() {
+        match &goal.kind {
+            GoalEvaluationKind::CacheHit(CacheHit::Global) => {
+                writeln!(f, "GLOBAL CACHE HIT: {:?}", goal.result)
+            }
+            GoalEvaluationKind::CacheHit(CacheHit::Provisional) => {
+                writeln!(f, "PROVISIONAL CACHE HIT: {:?}", goal.result)
+            }
+            GoalEvaluationKind::Uncached { revisions } => {
+                for (n, step) in revisions.iter().enumerate() {
                     let f = &mut *self.f;
-                    writeln!(f, "REVISION {n}: {:?}", step.result.unwrap())?;
+                    writeln!(f, "REVISION {n}: {:?}", step.result)?;
                     let mut f = self.nested();
                     f.format_evaluation_step(step)?;
                 }
 
                 let f = &mut *self.f;
-                writeln!(f, "RESULT: {:?}", goal.result.unwrap())
+                writeln!(f, "RESULT: {:?}", goal.result)
             }
         }
     }
@@ -136,12 +145,14 @@ impl ProofTreeFormatter<'_, '_> {
     fn format_candidate(&mut self, candidate: &GoalCandidate<'_>) -> std::fmt::Result {
         let f = &mut *self.f;
 
-        match (candidate.name.as_ref(), candidate.result) {
-            (Some(name), Some(result)) => writeln!(f, "CANDIDATE {}: {:?}", name, result,)?,
-            (None, None) => writeln!(f, "MISC PROBE")?,
-            (None, Some(_)) => unreachable!("unexpected probe with no name but a result"),
-            (Some(_), None) => unreachable!("unexpected probe with a name but no candidate"),
-        };
+        match &candidate.kind {
+            CandidateKind::NormalizedSelfTyAssembly => {
+                writeln!(f, "NORMALIZING SELF TY FOR ASSEMBLY:")
+            }
+            CandidateKind::Candidate { name, result } => {
+                writeln!(f, "CANDIDATE {}: {:?}", name, result)
+            }
+        }?;
 
         let mut f = self.nested();
         for candidate in &candidate.candidates {
@@ -159,7 +170,7 @@ impl ProofTreeFormatter<'_, '_> {
         nested_goal_evaluation: &AddedGoalsEvaluation<'_>,
     ) -> std::fmt::Result {
         let f = &mut *self.f;
-        writeln!(f, "TRY_EVALUATE_ADDED_GOALS: {:?}", nested_goal_evaluation.result.unwrap())?;
+        writeln!(f, "TRY_EVALUATE_ADDED_GOALS: {:?}", nested_goal_evaluation.result)?;
 
         for (n, revision) in nested_goal_evaluation.evaluations.iter().enumerate() {
             let f = &mut *self.f;
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
index 8d096c88a15..1ceb77e9193 100644
--- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs
+++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs
@@ -1,5 +1,6 @@
 use super::{EvalCtxt, SolverMode};
 use rustc_infer::traits::query::NoSolution;
+use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{Certainty, Goal, QueryResult};
 use rustc_middle::ty;
 
@@ -109,12 +110,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         direction: ty::AliasRelationDirection,
         invert: Invert,
     ) -> QueryResult<'tcx> {
-        self.probe_candidate(
+        self.probe(
             |ecx| {
                 ecx.normalizes_to_inner(param_env, alias, other, direction, invert)?;
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "normalizes-to".into(),
+            |r| CandidateKind::Candidate { name: "normalizes-to".into(), result: *r },
         )
     }
 
@@ -156,7 +157,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         alias_rhs: ty::AliasTy<'tcx>,
         direction: ty::AliasRelationDirection,
     ) -> QueryResult<'tcx> {
-        self.probe_candidate(
+        self.probe(
             |ecx| {
                 match direction {
                     ty::AliasRelationDirection::Equate => {
@@ -169,7 +170,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
 
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "substs relate".into(),
+            |r| CandidateKind::Candidate { name: "substs relate".into(), result: *r },
         )
     }
 
@@ -180,7 +181,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         rhs: ty::Term<'tcx>,
         direction: ty::AliasRelationDirection,
     ) -> QueryResult<'tcx> {
-        self.probe_candidate(
+        self.probe(
             |ecx| {
                 ecx.normalizes_to_inner(
                     param_env,
@@ -198,7 +199,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 )?;
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "bidir normalizes-to".into(),
+            |r| CandidateKind::Candidate { name: "bidir normalizes-to".into(), result: *r },
         )
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
index 543611daae8..d9bc8d3b1eb 100644
--- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs
@@ -8,6 +8,7 @@ use rustc_hir::def_id::DefId;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::util::elaborate;
 use rustc_infer::traits::Reveal;
+use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult};
 use rustc_middle::ty::fast_reject::TreatProjections;
 use rustc_middle::ty::TypeFoldable;
@@ -336,37 +337,40 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             return
         };
 
-        let normalized_self_candidates: Result<_, NoSolution> = self.probe(|ecx| {
-            ecx.with_incremented_depth(
-                |ecx| {
-                    let result = ecx.evaluate_added_goals_and_make_canonical_response(
-                        Certainty::Maybe(MaybeCause::Overflow),
-                    )?;
-                    Ok(vec![Candidate { source: CandidateSource::BuiltinImpl, result }])
-                },
-                |ecx| {
-                    let normalized_ty = ecx.next_ty_infer();
-                    let normalizes_to_goal = goal.with(
-                        tcx,
-                        ty::Binder::dummy(ty::ProjectionPredicate {
-                            projection_ty,
-                            term: normalized_ty.into(),
-                        }),
-                    );
-                    ecx.add_goal(normalizes_to_goal);
-                    let _ = ecx.try_evaluate_added_goals().inspect_err(|_| {
-                        debug!("self type normalization failed");
-                    })?;
-                    let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty);
-                    debug!(?normalized_ty, "self type normalized");
-                    // NOTE: Alternatively we could call `evaluate_goal` here and only
-                    // have a `Normalized` candidate. This doesn't work as long as we
-                    // use `CandidateSource` in winnowing.
-                    let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
-                    Ok(ecx.assemble_and_evaluate_candidates(goal))
-                },
-            )
-        });
+        let normalized_self_candidates: Result<_, NoSolution> = self.probe(
+            |ecx| {
+                ecx.with_incremented_depth(
+                    |ecx| {
+                        let result = ecx.evaluate_added_goals_and_make_canonical_response(
+                            Certainty::Maybe(MaybeCause::Overflow),
+                        )?;
+                        Ok(vec![Candidate { source: CandidateSource::BuiltinImpl, result }])
+                    },
+                    |ecx| {
+                        let normalized_ty = ecx.next_ty_infer();
+                        let normalizes_to_goal = goal.with(
+                            tcx,
+                            ty::Binder::dummy(ty::ProjectionPredicate {
+                                projection_ty,
+                                term: normalized_ty.into(),
+                            }),
+                        );
+                        ecx.add_goal(normalizes_to_goal);
+                        let _ = ecx.try_evaluate_added_goals().inspect_err(|_| {
+                            debug!("self type normalization failed");
+                        })?;
+                        let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty);
+                        debug!(?normalized_ty, "self type normalized");
+                        // NOTE: Alternatively we could call `evaluate_goal` here and only
+                        // have a `Normalized` candidate. This doesn't work as long as we
+                        // use `CandidateSource` in winnowing.
+                        let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty));
+                        Ok(ecx.assemble_and_evaluate_candidates(goal))
+                    },
+                )
+            },
+            |_| CandidateKind::NormalizedSelfTyAssembly,
+        );
 
         if let Ok(normalized_self_candidates) = normalized_self_candidates {
             candidates.extend(normalized_self_candidates);
diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
index d06450820ce..c9d531f27ab 100644
--- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
+++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs
@@ -9,6 +9,7 @@ use rustc_infer::infer::{
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::ObligationCause;
 use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind};
+use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{
     CanonicalInput, CanonicalResponse, Certainty, MaybeCause, PredefinedOpaques,
     PredefinedOpaquesData, QueryResult,
@@ -78,7 +79,7 @@ pub struct EvalCtxt<'a, 'tcx> {
     inspect: ProofTreeBuilder<'tcx>,
 }
 
-#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, HashStable)]
 pub(super) enum IsNormalizesToHack {
     Yes,
     No,
@@ -157,7 +158,7 @@ impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> {
         };
         let result = ecx.evaluate_goal(IsNormalizesToHack::No, goal);
 
-        if let Some(tree) = ecx.inspect.into_proof_tree() {
+        if let Some(tree) = ecx.inspect.finalize() {
             println!("{:?}", tree);
         }
 
@@ -509,7 +510,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> {
 }
 
 impl<'tcx> EvalCtxt<'_, 'tcx> {
-    pub(super) fn probe<T>(&mut self, f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T) -> T {
+    /// `probe_kind` is only called when proof tree building is enabled so it can be
+    /// as expensive as necessary to output the desired information.
+    pub(super) fn probe<T>(
+        &mut self,
+        f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T,
+        probe_kind: impl FnOnce(&T) -> CandidateKind<'tcx>,
+    ) -> T {
         let mut ecx = EvalCtxt {
             infcx: self.infcx,
             var_values: self.var_values,
@@ -521,23 +528,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
             inspect: self.inspect.new_goal_candidate(),
         };
         let r = self.infcx.probe(|_| f(&mut ecx));
-        self.inspect.goal_candidate(ecx.inspect);
+        if !self.inspect.is_noop() {
+            let cand_kind = probe_kind(&r);
+            ecx.inspect.candidate_kind(cand_kind);
+            self.inspect.goal_candidate(ecx.inspect);
+        }
         r
     }
 
-    pub(super) fn probe_candidate(
-        &mut self,
-        f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>,
-        mut name: impl FnMut() -> String,
-    ) -> QueryResult<'tcx> {
-        self.probe(|ecx| {
-            let result = f(ecx);
-            ecx.inspect.candidate_name(&mut name);
-            ecx.inspect.query_result(result);
-            result
-        })
-    }
-
     pub(super) fn tcx(&self) -> TyCtxt<'tcx> {
         self.infcx.tcx
     }
@@ -858,7 +856,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                     ecx.add_item_bounds_for_hidden_type(candidate_key, param_env, candidate_ty);
                     ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
                 },
-                || "opaque type storage".into(),
+                |r| CandidateKind::Candidate { name: "opaque type storage".into(), result: *r },
             ));
         }
         values
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/mod.rs b/compiler/rustc_trait_selection/src/solve/inspect.rs
index 20d77f86ca8..00c4e631b88 100644
--- a/compiler/rustc_trait_selection/src/solve/inspect/mod.rs
+++ b/compiler/rustc_trait_selection/src/solve/inspect.rs
@@ -1,25 +1,129 @@
 use rustc_middle::{
     traits::{
         query::NoSolution,
-        solve::{inspect::*, CanonicalInput, Certainty, Goal, QueryInput, QueryResult},
+        solve::{
+            inspect::{self, CacheHit, CandidateKind},
+            CanonicalInput, Certainty, Goal, QueryInput, QueryResult,
+        },
     },
     ty,
 };
 
+#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
+pub struct WipGoalEvaluation<'tcx> {
+    pub uncanonicalized_goal: Goal<'tcx, ty::Predicate<'tcx>>,
+    pub canonicalized_goal: Option<CanonicalInput<'tcx>>,
+
+    pub evaluation_steps: Vec<WipGoalEvaluationStep<'tcx>>,
+
+    pub cache_hit: Option<CacheHit>,
+
+    pub result: Option<QueryResult<'tcx>>,
+}
+impl<'tcx> WipGoalEvaluation<'tcx> {
+    pub fn finalize(self) -> inspect::GoalEvaluation<'tcx> {
+        inspect::GoalEvaluation {
+            uncanonicalized_goal: self.uncanonicalized_goal,
+            canonicalized_goal: self.canonicalized_goal.unwrap(),
+            kind: match self.cache_hit {
+                Some(hit) => inspect::GoalEvaluationKind::CacheHit(hit),
+                None => inspect::GoalEvaluationKind::Uncached {
+                    revisions: self
+                        .evaluation_steps
+                        .into_iter()
+                        .map(WipGoalEvaluationStep::finalize)
+                        .collect(),
+                },
+            },
+            result: self.result.unwrap(),
+        }
+    }
+}
+
+#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
+pub struct WipAddedGoalsEvaluation<'tcx> {
+    pub evaluations: Vec<Vec<WipGoalEvaluation<'tcx>>>,
+    pub result: Option<Result<Certainty, NoSolution>>,
+}
+impl<'tcx> WipAddedGoalsEvaluation<'tcx> {
+    pub fn finalize(self) -> inspect::AddedGoalsEvaluation<'tcx> {
+        inspect::AddedGoalsEvaluation {
+            evaluations: self
+                .evaluations
+                .into_iter()
+                .map(|evaluations| {
+                    evaluations.into_iter().map(WipGoalEvaluation::finalize).collect()
+                })
+                .collect(),
+            result: self.result.unwrap(),
+        }
+    }
+}
+
+#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
+pub struct WipGoalEvaluationStep<'tcx> {
+    pub instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>,
+
+    pub nested_goal_evaluations: Vec<WipAddedGoalsEvaluation<'tcx>>,
+    pub candidates: Vec<WipGoalCandidate<'tcx>>,
+
+    pub result: Option<QueryResult<'tcx>>,
+}
+impl<'tcx> WipGoalEvaluationStep<'tcx> {
+    pub fn finalize(self) -> inspect::GoalEvaluationStep<'tcx> {
+        inspect::GoalEvaluationStep {
+            instantiated_goal: self.instantiated_goal,
+            nested_goal_evaluations: self
+                .nested_goal_evaluations
+                .into_iter()
+                .map(WipAddedGoalsEvaluation::finalize)
+                .collect(),
+            candidates: self.candidates.into_iter().map(WipGoalCandidate::finalize).collect(),
+            result: self.result.unwrap(),
+        }
+    }
+}
+
+#[derive(Eq, PartialEq, Debug, Hash, HashStable)]
+pub struct WipGoalCandidate<'tcx> {
+    pub nested_goal_evaluations: Vec<WipAddedGoalsEvaluation<'tcx>>,
+    pub candidates: Vec<WipGoalCandidate<'tcx>>,
+    pub kind: Option<CandidateKind<'tcx>>,
+}
+impl<'tcx> WipGoalCandidate<'tcx> {
+    pub fn finalize(self) -> inspect::GoalCandidate<'tcx> {
+        inspect::GoalCandidate {
+            nested_goal_evaluations: self
+                .nested_goal_evaluations
+                .into_iter()
+                .map(WipAddedGoalsEvaluation::finalize)
+                .collect(),
+            candidates: self.candidates.into_iter().map(WipGoalCandidate::finalize).collect(),
+            kind: self.kind.unwrap(),
+        }
+    }
+}
+
 #[derive(Debug)]
 pub enum DebugSolver<'tcx> {
     Root,
-    GoalEvaluation(GoalEvaluation<'tcx>),
-    AddedGoalsEvaluation(AddedGoalsEvaluation<'tcx>),
-    GoalEvaluationStep(GoalEvaluationStep<'tcx>),
-    GoalCandidate(GoalCandidate<'tcx>),
+    GoalEvaluation(WipGoalEvaluation<'tcx>),
+    AddedGoalsEvaluation(WipAddedGoalsEvaluation<'tcx>),
+    GoalEvaluationStep(WipGoalEvaluationStep<'tcx>),
+    GoalCandidate(WipGoalCandidate<'tcx>),
 }
 
 pub struct ProofTreeBuilder<'tcx>(Option<Box<DebugSolver<'tcx>>>);
-
 impl<'tcx> ProofTreeBuilder<'tcx> {
-    pub fn into_proof_tree(self) -> Option<DebugSolver<'tcx>> {
-        self.0.map(|tree| *tree)
+    pub fn finalize(self) -> Option<inspect::GoalEvaluation<'tcx>> {
+        let wip_tree = *(self.0?);
+
+        match wip_tree {
+            DebugSolver::GoalEvaluation(wip_goal_evaluation) => {
+                Some(wip_goal_evaluation.finalize())
+            }
+            _ => unreachable!(),
+        }
     }
 
     pub fn new_root() -> ProofTreeBuilder<'tcx> {
@@ -30,6 +134,10 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         Self(None)
     }
 
+    pub fn is_noop(&self) -> bool {
+        self.0.is_none()
+    }
+
     pub fn new_goal_evaluation(
         &mut self,
         goal: Goal<'tcx, ty::Predicate<'tcx>>,
@@ -38,7 +146,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
             return ProofTreeBuilder(None);
         }
 
-        Self(Some(Box::new(DebugSolver::GoalEvaluation(GoalEvaluation {
+        Self(Some(Box::new(DebugSolver::GoalEvaluation(WipGoalEvaluation {
             uncanonicalized_goal: goal,
             canonicalized_goal: None,
             evaluation_steps: vec![],
@@ -81,7 +189,7 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
 
         match (this, *goal_evaluation.0.unwrap()) {
             (
-                DebugSolver::AddedGoalsEvaluation(AddedGoalsEvaluation { evaluations, .. }),
+                DebugSolver::AddedGoalsEvaluation(WipAddedGoalsEvaluation { evaluations, .. }),
                 DebugSolver::GoalEvaluation(goal_evaluation),
             ) => evaluations.last_mut().unwrap().push(goal_evaluation),
             (this @ DebugSolver::Root, goal_evaluation) => *this = goal_evaluation,
@@ -93,7 +201,11 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
         &mut self,
         instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>,
     ) -> ProofTreeBuilder<'tcx> {
-        Self(Some(Box::new(DebugSolver::GoalEvaluationStep(GoalEvaluationStep {
+        if self.0.is_none() {
+            return Self(None);
+        }
+
+        Self(Some(Box::new(DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep {
             instantiated_goal,
             nested_goal_evaluations: vec![],
             candidates: vec![],
@@ -115,24 +227,25 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
     }
 
     pub fn new_goal_candidate(&mut self) -> ProofTreeBuilder<'tcx> {
-        Self(Some(Box::new(DebugSolver::GoalCandidate(GoalCandidate {
+        if self.0.is_none() {
+            return Self(None);
+        }
+
+        Self(Some(Box::new(DebugSolver::GoalCandidate(WipGoalCandidate {
             nested_goal_evaluations: vec![],
             candidates: vec![],
-            name: None,
-            result: None,
+            kind: None,
         }))))
     }
-    pub fn candidate_name(&mut self, f: &mut dyn FnMut() -> String) {
+    pub fn candidate_kind(&mut self, kind: CandidateKind<'tcx>) {
         let this = match self.0.as_mut() {
             None => return,
             Some(this) => &mut **this,
         };
 
         match this {
-            DebugSolver::GoalCandidate(goal_candidate) => {
-                let name = f();
-                assert!(goal_candidate.name.is_none());
-                goal_candidate.name = Some(name);
+            DebugSolver::GoalCandidate(WipGoalCandidate { kind: old_kind @ None, .. }) => {
+                *old_kind = Some(kind)
             }
             _ => unreachable!(),
         }
@@ -145,8 +258,8 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
 
         match (this, *candidate.0.unwrap()) {
             (
-                DebugSolver::GoalCandidate(GoalCandidate { candidates, .. })
-                | DebugSolver::GoalEvaluationStep(GoalEvaluationStep { candidates, .. }),
+                DebugSolver::GoalCandidate(WipGoalCandidate { candidates, .. })
+                | DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { candidates, .. }),
                 DebugSolver::GoalCandidate(candidate),
             ) => candidates.push(candidate),
             _ => unreachable!(),
@@ -154,7 +267,11 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
     }
 
     pub fn new_evaluate_added_goals(&mut self) -> ProofTreeBuilder<'tcx> {
-        Self(Some(Box::new(DebugSolver::AddedGoalsEvaluation(AddedGoalsEvaluation {
+        if self.0.is_none() {
+            return Self(None);
+        }
+
+        Self(Some(Box::new(DebugSolver::AddedGoalsEvaluation(WipAddedGoalsEvaluation {
             evaluations: vec![],
             result: None,
         }))))
@@ -194,10 +311,11 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
 
         match (this, *goals_evaluation.0.unwrap()) {
             (
-                DebugSolver::GoalEvaluationStep(GoalEvaluationStep {
-                    nested_goal_evaluations, ..
+                DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep {
+                    nested_goal_evaluations,
+                    ..
                 })
-                | DebugSolver::GoalCandidate(GoalCandidate { nested_goal_evaluations, .. }),
+                | DebugSolver::GoalCandidate(WipGoalCandidate { nested_goal_evaluations, .. }),
                 DebugSolver::AddedGoalsEvaluation(added_goals_evaluation),
             ) => nested_goal_evaluations.push(added_goals_evaluation),
             _ => unreachable!(),
@@ -215,15 +333,13 @@ impl<'tcx> ProofTreeBuilder<'tcx> {
                 assert!(goal_evaluation.result.is_none());
                 goal_evaluation.result = Some(result);
             }
-            DebugSolver::Root | DebugSolver::AddedGoalsEvaluation(_) => unreachable!(),
+            DebugSolver::Root
+            | DebugSolver::AddedGoalsEvaluation(_)
+            | DebugSolver::GoalCandidate(_) => unreachable!(),
             DebugSolver::GoalEvaluationStep(evaluation_step) => {
                 assert!(evaluation_step.result.is_none());
                 evaluation_step.result = Some(result);
             }
-            DebugSolver::GoalCandidate(candidate) => {
-                assert!(candidate.result.is_none());
-                candidate.result = Some(result);
-            }
         }
     }
 }
diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs
index 09fd6fa4b1f..b99c3927862 100644
--- a/compiler/rustc_trait_selection/src/solve/project_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs
@@ -9,6 +9,7 @@ use rustc_hir::LangItem;
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::specialization_graph::LeafDef;
 use rustc_infer::traits::Reveal;
+use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams};
 use rustc_middle::ty::ProjectionPredicate;
@@ -109,21 +110,30 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         assumption: ty::Binder<'tcx, ty::Clause<'tcx>>,
         then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>,
     ) -> QueryResult<'tcx> {
-        if let Some(projection_pred) = assumption.as_projection_clause()
-            && projection_pred.projection_def_id() == goal.predicate.def_id()
-        {
-            ecx.probe_candidate(|ecx| {
-                let assumption_projection_pred =
-                    ecx.instantiate_binder_with_infer(projection_pred);
-                ecx.eq(
-                    goal.param_env,
-                    goal.predicate.projection_ty,
-                    assumption_projection_pred.projection_ty,
-                )?;
-                ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)
-                    .expect("expected goal term to be fully unconstrained");
-                then(ecx)
-            }, || "assumption".into())
+        if let Some(projection_pred) = assumption.as_projection_clause() {
+            if projection_pred.projection_def_id() == goal.predicate.def_id() {
+                ecx.probe(
+                    |ecx| {
+                        let assumption_projection_pred =
+                            ecx.instantiate_binder_with_infer(projection_pred);
+                        ecx.eq(
+                            goal.param_env,
+                            goal.predicate.projection_ty,
+                            assumption_projection_pred.projection_ty,
+                        )?;
+                        ecx.eq(
+                            goal.param_env,
+                            goal.predicate.term,
+                            assumption_projection_pred.term,
+                        )
+                        .expect("expected goal term to be fully unconstrained");
+                        then(ecx)
+                    },
+                    |r| CandidateKind::Candidate { name: "assumption".into(), result: *r },
+                )
+            } else {
+                Err(NoSolution)
+            }
         } else {
             Err(NoSolution)
         }
@@ -143,7 +153,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             return Err(NoSolution);
         }
 
-        ecx.probe_candidate(
+        ecx.probe(
             |ecx| {
                 let impl_substs = ecx.fresh_substs_for_item(impl_def_id);
                 let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
@@ -225,7 +235,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                     .expect("expected goal term to be fully unconstrained");
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "impl".into(),
+            |r| CandidateKind::Candidate { name: "impl".into(), result: *r },
         )
     }
 
@@ -321,7 +331,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
         goal: Goal<'tcx, Self>,
     ) -> QueryResult<'tcx> {
         let tcx = ecx.tcx();
-        ecx.probe_candidate(
+        ecx.probe(
             |ecx| {
                 let metadata_ty = match goal.predicate.self_ty().kind() {
                     ty::Bool
@@ -406,7 +416,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
                     .expect("expected goal term to be fully unconstrained");
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "builtin pointee".into(),
+            |r| CandidateKind::Candidate { name: "builtin pointee".into(), result: *r },
         )
     }
 
@@ -542,13 +552,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> {
             ),
         };
 
-        ecx.probe_candidate(
+        ecx.probe(
             |ecx| {
                 ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into())
                     .expect("expected goal term to be fully unconstrained");
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "builtin discriminant kind".into(),
+            |r| CandidateKind::Candidate { name: "builtin discriminant kind".into(), result: *r },
         )
     }
 
diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
index b5cd8760b2a..d9f24455a81 100644
--- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs
+++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs
@@ -6,6 +6,7 @@ use rustc_hir::def_id::DefId;
 use rustc_hir::{LangItem, Movability};
 use rustc_infer::traits::query::NoSolution;
 use rustc_infer::traits::util::supertraits;
+use rustc_middle::traits::solve::inspect::CandidateKind;
 use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult};
 use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections};
 use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt};
@@ -61,7 +62,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             },
         };
 
-        ecx.probe_candidate(
+        ecx.probe(
             |ecx| {
                 let impl_substs = ecx.fresh_substs_for_item(impl_def_id);
                 let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs);
@@ -77,7 +78,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
 
                 ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty)
             },
-            || "impl".into(),
+            |r| CandidateKind::Candidate { name: "impl".into(), result: *r },
         )
     }
 
@@ -87,21 +88,26 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         assumption: ty::Binder<'tcx, ty::Clause<'tcx>>,
         then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>,
     ) -> QueryResult<'tcx> {
-        if let Some(trait_clause) = assumption.as_trait_clause()
-            && trait_clause.def_id() == goal.predicate.def_id()
-            && trait_clause.polarity() == goal.predicate.polarity
-        {
-            // FIXME: Constness
-            ecx.probe_candidate(|ecx| {
-                let assumption_trait_pred =
-                    ecx.instantiate_binder_with_infer(trait_clause);
-                ecx.eq(
-                    goal.param_env,
-                    goal.predicate.trait_ref,
-                    assumption_trait_pred.trait_ref,
-                )?;
-                then(ecx)
-            }, || "assumption".into())
+        if let Some(trait_clause) = assumption.as_trait_clause() {
+            if trait_clause.def_id() == goal.predicate.def_id()
+                && trait_clause.polarity() == goal.predicate.polarity
+            {
+                // FIXME: Constness
+                ecx.probe(
+                    |ecx| {
+                        let assumption_trait_pred = ecx.instantiate_binder_with_infer(trait_clause);
+                        ecx.eq(
+                            goal.param_env,
+                            goal.predicate.trait_ref,
+                            assumption_trait_pred.trait_ref,
+                        )?;
+                        then(ecx)
+                    },
+                    |r| CandidateKind::Candidate { name: "assumption".into(), result: *r },
+                )
+            } else {
+                Err(NoSolution)
+            }
         } else {
             Err(NoSolution)
         }
@@ -135,7 +141,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
 
         let tcx = ecx.tcx();
 
-        ecx.probe_candidate(
+        ecx.probe(
             |ecx| {
                 let nested_obligations = tcx
                     .predicates_of(goal.predicate.def_id())
@@ -143,7 +149,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                 ecx.add_goals(nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)));
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "trait alias".into(),
+            |r| CandidateKind::Candidate { name: "trait alias".into(), result: *r },
         )
     }
 
@@ -350,7 +356,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
         if b_ty.is_ty_var() {
             return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS);
         }
-        ecx.probe_candidate(
+        ecx.probe(
             |ecx| {
                 match (a_ty.kind(), b_ty.kind()) {
                     // Trait upcasting, or `dyn Trait + Auto + 'a` -> `dyn Trait + 'b`
@@ -458,7 +464,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
                     _ => Err(NoSolution),
                 }
             },
-            || "builtin unsize".into(),
+            |r| CandidateKind::Candidate { name: "builtin unsize".into(), result: *r },
         )
     }
 
@@ -488,39 +494,40 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> {
             return vec![];
         }
 
-        let mut unsize_dyn_to_principal =
-            |principal: Option<ty::PolyExistentialTraitRef<'tcx>>| {
-                ecx.probe_candidate(
-                    |ecx| -> Result<_, NoSolution> {
-                        // Require that all of the trait predicates from A match B, except for
-                        // the auto traits. We do this by constructing a new A type with B's
-                        // auto traits, and equating these types.
-                        let new_a_data = principal
-                            .into_iter()
-                            .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait))
-                            .chain(a_data.iter().filter(|a| {
-                                matches!(a.skip_binder(), ty::ExistentialPredicate::Projection(_))
-                            }))
-                            .chain(
-                                b_data
-                                    .auto_traits()
-                                    .map(ty::ExistentialPredicate::AutoTrait)
-                                    .map(ty::Binder::dummy),
-                            );
-                        let new_a_data = tcx.mk_poly_existential_predicates_from_iter(new_a_data);
-                        let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn);
-
-                        // We also require that A's lifetime outlives B's lifetime.
-                        ecx.eq(goal.param_env, new_a_ty, b_ty)?;
-                        ecx.add_goal(goal.with(
+        let mut unsize_dyn_to_principal = |principal: Option<ty::PolyExistentialTraitRef<'tcx>>| {
+            ecx.probe(
+                |ecx| -> Result<_, NoSolution> {
+                    // Require that all of the trait predicates from A match B, except for
+                    // the auto traits. We do this by constructing a new A type with B's
+                    // auto traits, and equating these types.
+                    let new_a_data = principal
+                        .into_iter()
+                        .map(|trait_ref| trait_ref.map_bound(ty::ExistentialPredicate::Trait))
+                        .chain(a_data.iter().filter(|a| {
+                            matches!(a.skip_binder(), ty::ExistentialPredicate::Projection(_))
+                        }))
+                        .chain(
+                            b_data
+                                .auto_traits()
+                                .map(ty::ExistentialPredicate::AutoTrait)
+                                .map(ty::Binder::dummy),
+                        );
+                    let new_a_data = tcx.mk_poly_existential_predicates_from_iter(new_a_data);
+                    let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn);
+
+                    // We also require that A's lifetime outlives B's lifetime.
+                    ecx.eq(goal.param_env, new_a_ty, b_ty)?;
+                    ecx.add_goal(
+                        goal.with(
                             tcx,
                             ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region)),
-                        ));
-                        ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
-                    },
-                    || "upcast dyn to principle".into(),
-                )
-            };
+                        ),
+                    );
+                    ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
+                },
+                |r| CandidateKind::Candidate { name: "upcast dyn to principle".into(), result: *r },
+            )
+        };
 
         let mut responses = vec![];
         // If the principal def ids match (or are both none), then we're not doing
@@ -716,7 +723,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
         goal: Goal<'tcx, TraitPredicate<'tcx>>,
         constituent_tys: impl Fn(&EvalCtxt<'_, 'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>,
     ) -> QueryResult<'tcx> {
-        self.probe_candidate(
+        self.probe(
             |ecx| {
                 ecx.add_goals(
                     constituent_tys(ecx, goal.predicate.self_ty())?
@@ -731,7 +738,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> {
                 );
                 ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)
             },
-            || "constituent tys".into(),
+            |r| CandidateKind::Candidate { name: "constituent tys".into(), result: *r },
         )
     }