From c23a457e72abe608715ac76f076f47dc42af07a5 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 30 May 2024 20:31:44 +0200 Subject: Merging upstream version 1.74.1+dfsg1. Signed-off-by: Daniel Baumann --- compiler/rustc_middle/src/traits/solve/inspect.rs | 137 +++++++++++++++------ .../src/traits/solve/inspect/format.rs | 118 ++++++++++-------- 2 files changed, 165 insertions(+), 90 deletions(-) (limited to 'compiler/rustc_middle/src/traits/solve') 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> }, + 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>>, +} +#[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> }, } @@ -36,55 +87,69 @@ impl Debug for GoalEvaluation<'_> { } } -#[derive(Eq, PartialEq, Hash, HashStable)] +#[derive(Eq, PartialEq)] pub struct AddedGoalsEvaluation<'tcx> { pub evaluations: Vec>>, pub result: Result, } -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>, - pub candidates: Vec>, + /// 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>, + 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>, - pub candidates: Vec>, - 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(()) -- cgit v1.2.3