diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/inspect/build.rs')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/inspect/build.rs | 226 |
1 files changed, 70 insertions, 156 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/inspect/build.rs b/compiler/rustc_trait_selection/src/solve/inspect/build.rs index 803300c5196..3c633362648 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect/build.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect/build.rs @@ -5,20 +5,17 @@ //! see the comment on [ProofTreeBuilder]. use std::mem; +use crate::solve::eval_ctxt::canonical; +use crate::solve::{self, inspect, GenerateProofTree}; use rustc_infer::infer::InferCtxt; use rustc_middle::bug; use rustc_middle::infer::canonical::CanonicalVarValues; -use rustc_middle::traits::query::NoSolution; use rustc_middle::ty::{self, TyCtxt}; use rustc_next_trait_solver::solve::{ CanonicalInput, Certainty, Goal, GoalSource, QueryInput, QueryResult, }; -use rustc_session::config::DumpSolverProofTree; use rustc_type_ir::Interner; -use crate::solve::eval_ctxt::canonical; -use crate::solve::{self, inspect, GenerateProofTree}; - /// The core data structure when building proof trees. /// /// In case the current evaluation does not generate a proof @@ -53,7 +50,7 @@ enum DebugSolver<I: Interner> { Root, GoalEvaluation(WipGoalEvaluation<I>), CanonicalGoalEvaluation(WipCanonicalGoalEvaluation<I>), - GoalEvaluationStep(WipGoalEvaluationStep<I>), + CanonicalGoalEvaluationStep(WipCanonicalGoalEvaluationStep<I>), } impl<I: Interner> From<WipGoalEvaluation<I>> for DebugSolver<I> { @@ -68,9 +65,9 @@ impl<I: Interner> From<WipCanonicalGoalEvaluation<I>> for DebugSolver<I> { } } -impl<I: Interner> From<WipGoalEvaluationStep<I>> for DebugSolver<I> { - fn from(g: WipGoalEvaluationStep<I>) -> DebugSolver<I> { - DebugSolver::GoalEvaluationStep(g) +impl<I: Interner> From<WipCanonicalGoalEvaluationStep<I>> for DebugSolver<I> { + fn from(g: WipCanonicalGoalEvaluationStep<I>) -> DebugSolver<I> { + DebugSolver::CanonicalGoalEvaluationStep(g) } } @@ -78,7 +75,7 @@ impl<I: Interner> From<WipGoalEvaluationStep<I>> for DebugSolver<I> { #[derivative(PartialEq(bound = ""), Eq(bound = ""), Debug(bound = ""))] struct WipGoalEvaluation<I: Interner> { pub uncanonicalized_goal: Goal<I, I::Predicate>, - pub kind: WipGoalEvaluationKind<I>, + pub orig_values: Vec<I::GenericArg>, pub evaluation: Option<WipCanonicalGoalEvaluation<I>>, } @@ -86,31 +83,19 @@ impl<I: Interner> WipGoalEvaluation<I> { fn finalize(self) -> inspect::GoalEvaluation<I> { inspect::GoalEvaluation { uncanonicalized_goal: self.uncanonicalized_goal, - kind: match self.kind { - WipGoalEvaluationKind::Root { orig_values } => { - inspect::GoalEvaluationKind::Root { orig_values } - } - WipGoalEvaluationKind::Nested => inspect::GoalEvaluationKind::Nested, - }, + orig_values: self.orig_values, evaluation: self.evaluation.unwrap().finalize(), } } } #[derive(derivative::Derivative)] -#[derivative(PartialEq(bound = ""), Eq(bound = ""), Debug(bound = ""))] -pub(in crate::solve) enum WipGoalEvaluationKind<I: Interner> { - Root { orig_values: Vec<I::GenericArg> }, - Nested, -} - -#[derive(derivative::Derivative)] #[derivative(PartialEq(bound = ""), Eq(bound = ""))] pub(in crate::solve) enum WipCanonicalGoalEvaluationKind<I: Interner> { Overflow, CycleInStack, ProvisionalCacheHit, - Interned { revisions: I::GoalEvaluationSteps }, + Interned { final_revision: I::CanonicalGoalEvaluationStepRef }, } impl<I: Interner> std::fmt::Debug for WipCanonicalGoalEvaluationKind<I> { @@ -119,7 +104,9 @@ impl<I: Interner> std::fmt::Debug for WipCanonicalGoalEvaluationKind<I> { Self::Overflow => write!(f, "Overflow"), Self::CycleInStack => write!(f, "CycleInStack"), Self::ProvisionalCacheHit => write!(f, "ProvisionalCacheHit"), - Self::Interned { revisions: _ } => f.debug_struct("Interned").finish_non_exhaustive(), + Self::Interned { final_revision: _ } => { + f.debug_struct("Interned").finish_non_exhaustive() + } } } } @@ -131,13 +118,15 @@ struct WipCanonicalGoalEvaluation<I: Interner> { kind: Option<WipCanonicalGoalEvaluationKind<I>>, /// Only used for uncached goals. After we finished evaluating /// the goal, this is interned and moved into `kind`. - revisions: Vec<WipGoalEvaluationStep<I>>, + final_revision: Option<WipCanonicalGoalEvaluationStep<I>>, result: Option<QueryResult<I>>, } impl<I: Interner> WipCanonicalGoalEvaluation<I> { fn finalize(self) -> inspect::CanonicalGoalEvaluation<I> { - assert!(self.revisions.is_empty()); + // We've already interned the final revision in + // `fn finalize_canonical_goal_evaluation`. + assert!(self.final_revision.is_none()); let kind = match self.kind.unwrap() { WipCanonicalGoalEvaluationKind::Overflow => { inspect::CanonicalGoalEvaluationKind::Overflow @@ -148,8 +137,8 @@ impl<I: Interner> WipCanonicalGoalEvaluation<I> { WipCanonicalGoalEvaluationKind::ProvisionalCacheHit => { inspect::CanonicalGoalEvaluationKind::ProvisionalCacheHit } - WipCanonicalGoalEvaluationKind::Interned { revisions } => { - inspect::CanonicalGoalEvaluationKind::Evaluation { revisions } + WipCanonicalGoalEvaluationKind::Interned { final_revision } => { + inspect::CanonicalGoalEvaluationKind::Evaluation { final_revision } } }; @@ -159,29 +148,7 @@ impl<I: Interner> WipCanonicalGoalEvaluation<I> { #[derive(derivative::Derivative)] #[derivative(PartialEq(bound = ""), Eq(bound = ""), Debug(bound = ""))] -struct WipAddedGoalsEvaluation<I: Interner> { - evaluations: Vec<Vec<WipGoalEvaluation<I>>>, - result: Option<Result<Certainty, NoSolution>>, -} - -impl<I: Interner> WipAddedGoalsEvaluation<I> { - fn finalize(self) -> inspect::AddedGoalsEvaluation<I> { - inspect::AddedGoalsEvaluation { - evaluations: self - .evaluations - .into_iter() - .map(|evaluations| { - evaluations.into_iter().map(WipGoalEvaluation::finalize).collect() - }) - .collect(), - result: self.result.unwrap(), - } - } -} - -#[derive(derivative::Derivative)] -#[derivative(PartialEq(bound = ""), Eq(bound = ""), Debug(bound = ""))] -struct WipGoalEvaluationStep<I: Interner> { +struct WipCanonicalGoalEvaluationStep<I: Interner> { /// Unlike `EvalCtxt::var_values`, we append a new /// generic arg here whenever we create a new inference /// variable. @@ -194,7 +161,7 @@ struct WipGoalEvaluationStep<I: Interner> { evaluation: WipProbe<I>, } -impl<I: Interner> WipGoalEvaluationStep<I> { +impl<I: Interner> WipCanonicalGoalEvaluationStep<I> { fn current_evaluation_scope(&mut self) -> &mut WipProbe<I> { let mut current = &mut self.evaluation; for _ in 0..self.probe_depth { @@ -206,24 +173,16 @@ impl<I: Interner> WipGoalEvaluationStep<I> { current } - fn added_goals_evaluation(&mut self) -> &mut WipAddedGoalsEvaluation<I> { - let mut current = &mut self.evaluation; - loop { - match current.steps.last_mut() { - Some(WipProbeStep::NestedProbe(p)) => current = p, - Some(WipProbeStep::EvaluateGoals(evaluation)) => return evaluation, - _ => bug!(), - } - } - } - - fn finalize(self) -> inspect::GoalEvaluationStep<I> { + fn finalize(self) -> inspect::CanonicalGoalEvaluationStep<I> { let evaluation = self.evaluation.finalize(); match evaluation.kind { inspect::ProbeKind::Root { .. } => (), _ => unreachable!("unexpected root evaluation: {evaluation:?}"), } - inspect::GoalEvaluationStep { instantiated_goal: self.instantiated_goal, evaluation } + inspect::CanonicalGoalEvaluationStep { + instantiated_goal: self.instantiated_goal, + evaluation, + } } } @@ -250,7 +209,6 @@ impl<I: Interner> WipProbe<I> { #[derivative(PartialEq(bound = ""), Eq(bound = ""), Debug(bound = ""))] enum WipProbeStep<I: Interner> { AddGoal(GoalSource, inspect::CanonicalState<I, Goal<I, I::Predicate>>), - EvaluateGoals(WipAddedGoalsEvaluation<I>), NestedProbe(WipProbe<I>), MakeCanonicalResponse { shallow_certainty: Certainty }, RecordImplArgs { impl_args: inspect::CanonicalState<I, I::GenericArgs> }, @@ -260,7 +218,6 @@ impl<I: Interner> WipProbeStep<I> { fn finalize(self) -> inspect::ProbeStep<I> { match self { WipProbeStep::AddGoal(source, goal) => inspect::ProbeStep::AddGoal(source, goal), - WipProbeStep::EvaluateGoals(eval) => inspect::ProbeStep::EvaluateGoals(eval.finalize()), WipProbeStep::NestedProbe(probe) => inspect::ProbeStep::NestedProbe(probe.finalize()), WipProbeStep::RecordImplArgs { impl_args } => { inspect::ProbeStep::RecordImplArgs { impl_args } @@ -278,6 +235,15 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { ProofTreeBuilder { state: Some(Box::new(state.into())) } } + fn opt_nested<T: Into<DebugSolver<TyCtxt<'tcx>>>>( + &self, + state: impl FnOnce() -> Option<T>, + ) -> Self { + ProofTreeBuilder { + state: self.state.as_ref().and_then(|_| Some(state()?.into())).map(Box::new), + } + } + fn nested<T: Into<DebugSolver<TyCtxt<'tcx>>>>(&self, state: impl FnOnce() -> T) -> Self { ProofTreeBuilder { state: self.state.as_ref().map(|_| Box::new(state().into())) } } @@ -302,22 +268,10 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { } pub fn new_maybe_root( - tcx: TyCtxt<'tcx>, generate_proof_tree: GenerateProofTree, ) -> ProofTreeBuilder<TyCtxt<'tcx>> { match generate_proof_tree { - GenerateProofTree::Never => ProofTreeBuilder::new_noop(), - GenerateProofTree::IfEnabled => { - let opts = &tcx.sess.opts.unstable_opts; - match opts.next_solver.map(|c| c.dump_tree).unwrap_or_default() { - DumpSolverProofTree::Always => ProofTreeBuilder::new_root(), - // `OnError` is handled by reevaluating goals in error - // reporting with `GenerateProofTree::Yes`. - DumpSolverProofTree::OnError | DumpSolverProofTree::Never => { - ProofTreeBuilder::new_noop() - } - } - } + GenerateProofTree::No => ProofTreeBuilder::new_noop(), GenerateProofTree::Yes => ProofTreeBuilder::new_root(), } } @@ -340,15 +294,13 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { orig_values: &[ty::GenericArg<'tcx>], kind: solve::GoalEvaluationKind, ) -> ProofTreeBuilder<TyCtxt<'tcx>> { - self.nested(|| WipGoalEvaluation { - uncanonicalized_goal: goal, - kind: match kind { - solve::GoalEvaluationKind::Root => { - WipGoalEvaluationKind::Root { orig_values: orig_values.to_vec() } - } - solve::GoalEvaluationKind::Nested => WipGoalEvaluationKind::Nested, - }, - evaluation: None, + self.opt_nested(|| match kind { + solve::GoalEvaluationKind::Root => Some(WipGoalEvaluation { + uncanonicalized_goal: goal, + orig_values: orig_values.to_vec(), + evaluation: None, + }), + solve::GoalEvaluationKind::Nested => None, }) } @@ -359,24 +311,22 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { self.nested(|| WipCanonicalGoalEvaluation { goal, kind: None, - revisions: vec![], + final_revision: None, result: None, }) } - pub fn finalize_evaluation( + pub fn finalize_canonical_goal_evaluation( &mut self, tcx: TyCtxt<'tcx>, - ) -> Option<&'tcx [inspect::GoalEvaluationStep<TyCtxt<'tcx>>]> { + ) -> Option<&'tcx inspect::CanonicalGoalEvaluationStep<TyCtxt<'tcx>>> { self.as_mut().map(|this| match this { DebugSolver::CanonicalGoalEvaluation(evaluation) => { - let revisions = mem::take(&mut evaluation.revisions) - .into_iter() - .map(WipGoalEvaluationStep::finalize); - let revisions = &*tcx.arena.alloc_from_iter(revisions); - let kind = WipCanonicalGoalEvaluationKind::Interned { revisions }; + let final_revision = mem::take(&mut evaluation.final_revision).unwrap(); + let final_revision = &*tcx.arena.alloc(final_revision.finalize()); + let kind = WipCanonicalGoalEvaluationKind::Interned { final_revision }; assert_eq!(evaluation.kind.replace(kind), None); - revisions + final_revision } _ => unreachable!(), }) @@ -400,7 +350,10 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { } } - pub fn goal_evaluation_kind(&mut self, kind: WipCanonicalGoalEvaluationKind<TyCtxt<'tcx>>) { + pub fn canonical_goal_evaluation_kind( + &mut self, + kind: WipCanonicalGoalEvaluationKind<TyCtxt<'tcx>>, + ) { if let Some(this) = self.as_mut() { match this { DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => { @@ -413,17 +366,11 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { pub fn goal_evaluation(&mut self, goal_evaluation: ProofTreeBuilder<TyCtxt<'tcx>>) { if let Some(this) = self.as_mut() { - match (this, *goal_evaluation.state.unwrap()) { - ( - DebugSolver::GoalEvaluationStep(state), - DebugSolver::GoalEvaluation(goal_evaluation), - ) => state - .added_goals_evaluation() - .evaluations - .last_mut() - .unwrap() - .push(goal_evaluation), - (this @ DebugSolver::Root, goal_evaluation) => *this = goal_evaluation, + match this { + DebugSolver::Root => *this = *goal_evaluation.state.unwrap(), + DebugSolver::CanonicalGoalEvaluationStep(_) => { + assert!(goal_evaluation.state.is_none()) + } _ => unreachable!(), } } @@ -434,7 +381,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { var_values: CanonicalVarValues<'tcx>, instantiated_goal: QueryInput<TyCtxt<'tcx>, ty::Predicate<'tcx>>, ) -> ProofTreeBuilder<TyCtxt<'tcx>> { - self.nested(|| WipGoalEvaluationStep { + self.nested(|| WipCanonicalGoalEvaluationStep { var_values: var_values.var_values.to_vec(), instantiated_goal, evaluation: WipProbe { @@ -452,9 +399,9 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { match (this, *goal_evaluation_step.state.unwrap()) { ( DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluations), - DebugSolver::GoalEvaluationStep(goal_evaluation_step), + DebugSolver::CanonicalGoalEvaluationStep(goal_evaluation_step), ) => { - canonical_goal_evaluations.revisions.push(goal_evaluation_step); + canonical_goal_evaluations.final_revision = Some(goal_evaluation_step); } _ => unreachable!(), } @@ -464,7 +411,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { pub fn add_var_value<T: Into<ty::GenericArg<'tcx>>>(&mut self, arg: T) { match self.as_mut() { None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { state.var_values.push(arg.into()); } Some(s) => bug!("tried to add var values to {s:?}"), @@ -474,7 +421,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { pub fn enter_probe(&mut self) { match self.as_mut() { None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { let initial_num_var_values = state.var_values.len(); state.current_evaluation_scope().steps.push(WipProbeStep::NestedProbe(WipProbe { initial_num_var_values, @@ -491,7 +438,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { pub fn probe_kind(&mut self, probe_kind: inspect::ProbeKind<TyCtxt<'tcx>>) { match self.as_mut() { None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { let prev = state.current_evaluation_scope().kind.replace(probe_kind); assert_eq!(prev, None); } @@ -506,7 +453,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { ) { match self.as_mut() { None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { let final_state = canonical::make_canonical_state( infcx, &state.var_values, @@ -543,7 +490,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { ) { match self.as_mut() { None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { let goal = canonical::make_canonical_state( infcx, &state.var_values, @@ -563,7 +510,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { impl_args: ty::GenericArgsRef<'tcx>, ) { match self.as_mut() { - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { let impl_args = canonical::make_canonical_state( infcx, &state.var_values, @@ -582,7 +529,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { pub fn make_canonical_response(&mut self, shallow_certainty: Certainty) { match self.as_mut() { - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { state .current_evaluation_scope() .steps @@ -596,7 +543,7 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { pub fn finish_probe(mut self) -> ProofTreeBuilder<TyCtxt<'tcx>> { match self.as_mut() { None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { + Some(DebugSolver::CanonicalGoalEvaluationStep(state)) => { assert_ne!(state.probe_depth, 0); let num_var_values = state.current_evaluation_scope().initial_num_var_values; state.var_values.truncate(num_var_values); @@ -608,46 +555,13 @@ impl<'tcx> ProofTreeBuilder<TyCtxt<'tcx>> { self } - pub fn start_evaluate_added_goals(&mut self) { - match self.as_mut() { - None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { - state.current_evaluation_scope().steps.push(WipProbeStep::EvaluateGoals( - WipAddedGoalsEvaluation { evaluations: vec![], result: None }, - )); - } - _ => bug!(), - } - } - - pub fn start_evaluate_added_goals_step(&mut self) { - match self.as_mut() { - None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { - state.added_goals_evaluation().evaluations.push(vec![]); - } - _ => bug!(), - } - } - - pub fn evaluate_added_goals_result(&mut self, result: Result<Certainty, NoSolution>) { - match self.as_mut() { - None => {} - Some(DebugSolver::GoalEvaluationStep(state)) => { - let prev = state.added_goals_evaluation().result.replace(result); - assert_eq!(prev, None); - } - _ => bug!(), - } - } - pub fn query_result(&mut self, result: QueryResult<TyCtxt<'tcx>>) { if let Some(this) = self.as_mut() { match this { DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => { assert_eq!(canonical_goal_evaluation.result.replace(result), None); } - DebugSolver::GoalEvaluationStep(evaluation_step) => { + DebugSolver::CanonicalGoalEvaluationStep(evaluation_step) => { assert_eq!( evaluation_step .evaluation |