Merging upstream version 1.74.1+dfsg1.

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

6 files changed, 258 insertions, 125 deletions

diff --git a/compiler/rustc_middle/src/traits/mod.rs b/compiler/rustc_middle/src/traits/mod.rs
index 3465759b9..99b750c9a 100644
--- a/compiler/rustc_middle/src/traits/mod.rs
+++ b/compiler/rustc_middle/src/traits/mod.rs
@@ -13,7 +13,7 @@ use crate::infer::canonical::Canonical;
 use crate::mir::ConstraintCategory;
 use crate::ty::abstract_const::NotConstEvaluatable;
 use crate::ty::GenericArgsRef;
-use crate::ty::{self, AdtKind, Ty, TyCtxt};
+use crate::ty::{self, AdtKind, Ty};
 
 use rustc_data_structures::sync::Lrc;
 use rustc_errors::{Applicability, Diagnostic};
@@ -86,7 +86,7 @@ pub enum Reveal {
 ///
 /// We do not want to intern this as there are a lot of obligation causes which
 /// only live for a short period of time.
-#[derive(Clone, Debug, PartialEq, Eq, Lift, HashStable, TyEncodable, TyDecodable)]
+#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 #[derive(TypeVisitable, TypeFoldable)]
 pub struct ObligationCause<'tcx> {
     pub span: Span,
@@ -194,7 +194,7 @@ impl<'tcx> ObligationCause<'tcx> {
     }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Lift, HashStable, TyEncodable, TyDecodable)]
+#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 #[derive(TypeVisitable, TypeFoldable)]
 pub struct UnifyReceiverContext<'tcx> {
     pub assoc_item: ty::AssocItem,
@@ -202,7 +202,7 @@ pub struct UnifyReceiverContext<'tcx> {
     pub args: GenericArgsRef<'tcx>,
 }
 
-#[derive(Clone, PartialEq, Eq, Lift, Default, HashStable)]
+#[derive(Clone, PartialEq, Eq, Default, HashStable)]
 #[derive(TypeVisitable, TypeFoldable, TyEncodable, TyDecodable)]
 pub struct InternedObligationCauseCode<'tcx> {
     /// `None` for `ObligationCauseCode::MiscObligation` (a common case, occurs ~60% of
@@ -238,7 +238,7 @@ impl<'tcx> std::ops::Deref for InternedObligationCauseCode<'tcx> {
     }
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Lift, HashStable, TyEncodable, TyDecodable)]
+#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 #[derive(TypeVisitable, TypeFoldable)]
 pub enum ObligationCauseCode<'tcx> {
     /// Not well classified or should be obvious from the span.
@@ -299,6 +299,10 @@ pub enum ObligationCauseCode<'tcx> {
     SizedYieldType,
     /// Inline asm operand type must be `Sized`.
     InlineAsmSized,
+    /// Captured closure type must be `Sized`.
+    SizedClosureCapture(LocalDefId),
+    /// Types live across generator yields must be `Sized`.
+    SizedGeneratorInterior(LocalDefId),
     /// `[expr; N]` requires `type_of(expr): Copy`.
     RepeatElementCopy {
         /// If element is a `const fn` we display a help message suggesting to move the
@@ -378,6 +382,9 @@ pub enum ObligationCauseCode<'tcx> {
     /// `start` has wrong type
     StartFunctionType,
 
+    /// language function has wrong type
+    LangFunctionType(Symbol),
+
     /// Intrinsic has wrong type
     IntrinsicType,
 
@@ -470,7 +477,7 @@ pub enum WellFormedLoc {
     },
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Lift, HashStable, TyEncodable, TyDecodable)]
+#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 #[derive(TypeVisitable, TypeFoldable)]
 pub struct ImplDerivedObligationCause<'tcx> {
     pub derived: DerivedObligationCause<'tcx>,
@@ -524,14 +531,7 @@ pub enum StatementAsExpression {
     NeedsBoxing,
 }
 
-impl<'tcx> ty::Lift<'tcx> for StatementAsExpression {
-    type Lifted = StatementAsExpression;
-    fn lift_to_tcx(self, _tcx: TyCtxt<'tcx>) -> Option<StatementAsExpression> {
-        Some(self)
-    }
-}
-
-#[derive(Clone, Debug, PartialEq, Eq, Lift, HashStable, TyEncodable, TyDecodable)]
+#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 #[derive(TypeVisitable, TypeFoldable)]
 pub struct MatchExpressionArmCause<'tcx> {
     pub arm_block_id: Option<hir::HirId>,
@@ -547,7 +547,7 @@ pub struct MatchExpressionArmCause<'tcx> {
 }
 
 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
-#[derive(Lift, TypeFoldable, TypeVisitable, HashStable, TyEncodable, TyDecodable)]
+#[derive(TypeFoldable, TypeVisitable, HashStable, TyEncodable, TyDecodable)]
 pub struct IfExpressionCause<'tcx> {
     pub then_id: hir::HirId,
     pub else_id: hir::HirId,
@@ -557,7 +557,7 @@ pub struct IfExpressionCause<'tcx> {
     pub opt_suggest_box_span: Option<Span>,
 }
 
-#[derive(Clone, Debug, PartialEq, Eq, Lift, HashStable, TyEncodable, TyDecodable)]
+#[derive(Clone, Debug, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 #[derive(TypeVisitable, TypeFoldable)]
 pub struct DerivedObligationCause<'tcx> {
     /// The trait predicate of the parent obligation that led to the
@@ -570,7 +570,7 @@ pub struct DerivedObligationCause<'tcx> {
     pub parent_code: InternedObligationCauseCode<'tcx>,
 }
 
-#[derive(Clone, Debug, TypeVisitable, Lift)]
+#[derive(Clone, Debug, TypeVisitable)]
 pub enum SelectionError<'tcx> {
     /// The trait is not implemented.
     Unimplemented,
@@ -593,7 +593,7 @@ pub enum SelectionError<'tcx> {
     OpaqueTypeAutoTraitLeakageUnknown(DefId),
 }
 
-#[derive(Clone, Debug, TypeVisitable, Lift)]
+#[derive(Clone, Debug, TypeVisitable)]
 pub struct SelectionOutputTypeParameterMismatch<'tcx> {
     pub found_trait_ref: ty::PolyTraitRef<'tcx>,
     pub expected_trait_ref: ty::PolyTraitRef<'tcx>,
@@ -638,7 +638,7 @@ pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 /// ### The type parameter `N`
 ///
 /// See explanation on `ImplSourceUserDefinedData`.
-#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
 #[derive(TypeFoldable, TypeVisitable)]
 pub enum ImplSource<'tcx, N> {
     /// ImplSource identifying a particular impl.
@@ -704,7 +704,7 @@ impl<'tcx, N> ImplSource<'tcx, N> {
 /// is `Obligation`, as one might expect. During codegen, however, this
 /// is `()`, because codegen only requires a shallow resolution of an
 /// impl, and nested obligations are satisfied later.
-#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable, Lift)]
+#[derive(Clone, PartialEq, Eq, TyEncodable, TyDecodable, HashStable)]
 #[derive(TypeFoldable, TypeVisitable)]
 pub struct ImplSourceUserDefinedData<'tcx, N> {
     pub impl_def_id: DefId,
@@ -736,7 +736,7 @@ pub enum BuiltinImplSource {
     TupleUnsizing,
 }
 
-TrivialTypeTraversalAndLiftImpls! { BuiltinImplSource }
+TrivialTypeTraversalImpls! { BuiltinImplSource }
 
 #[derive(Clone, Debug, PartialEq, Eq, Hash, HashStable, PartialOrd, Ord)]
 pub enum ObjectSafetyViolation {
diff --git a/compiler/rustc_middle/src/traits/query.rs b/compiler/rustc_middle/src/traits/query.rs
index 950a59e96..975e3e3ac 100644
--- a/compiler/rustc_middle/src/traits/query.rs
+++ b/compiler/rustc_middle/src/traits/query.rs
@@ -17,8 +17,7 @@ pub mod type_op {
     use crate::ty::{Predicate, Ty, TyCtxt, UserType};
     use std::fmt;
 
-    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
-    #[derive(TypeFoldable, TypeVisitable)]
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, TypeVisitable)]
     pub struct AscribeUserType<'tcx> {
         pub mir_ty: Ty<'tcx>,
         pub user_ty: UserType<'tcx>,
@@ -30,22 +29,19 @@ pub mod type_op {
         }
     }
 
-    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
-    #[derive(TypeFoldable, TypeVisitable)]
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, TypeVisitable)]
     pub struct Eq<'tcx> {
         pub a: Ty<'tcx>,
         pub b: Ty<'tcx>,
     }
 
-    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
-    #[derive(TypeFoldable, TypeVisitable)]
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, TypeVisitable)]
     pub struct Subtype<'tcx> {
         pub sub: Ty<'tcx>,
         pub sup: Ty<'tcx>,
     }
 
-    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
-    #[derive(TypeFoldable, TypeVisitable)]
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, TypeVisitable)]
     pub struct ProvePredicate<'tcx> {
         pub predicate: Predicate<'tcx>,
     }
@@ -56,8 +52,7 @@ pub mod type_op {
         }
     }
 
-    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, Lift)]
-    #[derive(TypeFoldable, TypeVisitable)]
+    #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, HashStable, TypeFoldable, TypeVisitable)]
     pub struct Normalize<T> {
         pub value: T,
     }
@@ -101,7 +96,7 @@ impl<'tcx> From<TypeError<'tcx>> for NoSolution {
     }
 }
 
-#[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable, Lift)]
+#[derive(Clone, Debug, Default, HashStable, TypeFoldable, TypeVisitable)]
 pub struct DropckOutlivesResult<'tcx> {
     pub kinds: Vec<GenericArg<'tcx>>,
     pub overflows: Vec<Ty<'tcx>>,
@@ -194,7 +189,7 @@ pub struct MethodAutoderefBadTy<'tcx> {
 }
 
 /// Result from the `normalize_projection_ty` query.
-#[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)]
+#[derive(Clone, Debug, HashStable, TypeFoldable, TypeVisitable)]
 pub struct NormalizationResult<'tcx> {
     /// Result of normalization.
     pub normalized_ty: Ty<'tcx>,
@@ -207,7 +202,7 @@ pub struct NormalizationResult<'tcx> {
 /// case they are called implied bounds). They are fed to the
 /// `OutlivesEnv` which in turn is supplied to the region checker and
 /// other parts of the inference system.
-#[derive(Clone, Debug, TypeFoldable, TypeVisitable, Lift, HashStable)]
+#[derive(Clone, Debug, TypeFoldable, TypeVisitable, HashStable)]
 pub enum OutlivesBound<'tcx> {
     RegionSubRegion(ty::Region<'tcx>, ty::Region<'tcx>),
     RegionSubParam(ty::Region<'tcx>, ty::ParamTy),
diff --git a/compiler/rustc_middle/src/traits/select.rs b/compiler/rustc_middle/src/traits/select.rs
index ffae35798..90bc5dd8f 100644
--- a/compiler/rustc_middle/src/traits/select.rs
+++ b/compiler/rustc_middle/src/traits/select.rs
@@ -305,7 +305,7 @@ impl From<ErrorGuaranteed> for OverflowError {
     }
 }
 
-TrivialTypeTraversalAndLiftImpls! { OverflowError }
+TrivialTypeTraversalImpls! { OverflowError }
 
 impl<'tcx> From<OverflowError> for SelectionError<'tcx> {
     fn from(overflow_error: OverflowError) -> SelectionError<'tcx> {
diff --git a/compiler/rustc_middle/src/traits/solve.rs b/compiler/rustc_middle/src/traits/solve.rs
index 9d63d2918..27a1e64a7 100644
--- a/compiler/rustc_middle/src/traits/solve.rs
+++ b/compiler/rustc_middle/src/traits/solve.rs
@@ -9,6 +9,9 @@ use crate::ty::{
     self, FallibleTypeFolder, ToPredicate, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeVisitable,
     TypeVisitor,
 };
+use rustc_span::def_id::DefId;
+
+use super::BuiltinImplSource;
 
 mod cache;
 pub mod inspect;
@@ -235,3 +238,63 @@ pub enum IsNormalizesToHack {
     Yes,
     No,
 }
+
+/// Possible ways the given goal can be proven.
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+pub enum CandidateSource {
+    /// A user written impl.
+    ///
+    /// ## Examples
+    ///
+    /// ```rust
+    /// fn main() {
+    ///     let x: Vec<u32> = Vec::new();
+    ///     // This uses the impl from the standard library to prove `Vec<T>: Clone`.
+    ///     let y = x.clone();
+    /// }
+    /// ```
+    Impl(DefId),
+    /// A builtin impl generated by the compiler. When adding a new special
+    /// trait, try to use actual impls whenever possible. Builtin impls should
+    /// only be used in cases where the impl cannot be manually be written.
+    ///
+    /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`.
+    /// For a list of all traits with builtin impls, check out the
+    /// `EvalCtxt::assemble_builtin_impl_candidates` method.
+    BuiltinImpl(BuiltinImplSource),
+    /// An assumption from the environment.
+    ///
+    /// More precisely we've used the `n-th` assumption in the `param_env`.
+    ///
+    /// ## Examples
+    ///
+    /// ```rust
+    /// fn is_clone<T: Clone>(x: T) -> (T, T) {
+    ///     // This uses the assumption `T: Clone` from the `where`-bounds
+    ///     // to prove `T: Clone`.
+    ///     (x.clone(), x)
+    /// }
+    /// ```
+    ParamEnv(usize),
+    /// If the self type is an alias type, e.g. an opaque type or a projection,
+    /// we know the bounds on that alias to hold even without knowing its concrete
+    /// underlying type.
+    ///
+    /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of
+    /// the self type.
+    ///
+    /// ## Examples
+    ///
+    /// ```rust
+    /// trait Trait {
+    ///     type Assoc: Clone;
+    /// }
+    ///
+    /// fn foo<T: Trait>(x: <T as Trait>::Assoc) {
+    ///     // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in
+    ///     // in the trait definition.
+    ///     let _y = x.clone();
+    /// }
+    /// ```
+    AliasBound,
+}
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(())