diff options
6 files changed, 73 insertions, 163 deletions
diff --git a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs index 780feb9b827..dd9ccadf6cf 100644 --- a/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_next_trait_solver/src/solve/eval_ctxt/mod.rs @@ -3,7 +3,7 @@ use std::ops::ControlFlow; #[cfg(feature = "nightly")] use rustc_macros::HashStable_NoContext; -use rustc_type_ir::data_structures::{HashMap, HashSet, ensure_sufficient_stack}; +use rustc_type_ir::data_structures::{HashMap, HashSet}; use rustc_type_ir::fast_reject::DeepRejectCtxt; use rustc_type_ir::inherent::*; use rustc_type_ir::relate::Relate; @@ -336,13 +336,12 @@ where /// Creates a nested evaluation context that shares the same search graph as the /// one passed in. This is suitable for evaluation, granted that the search graph - /// has had the nested goal recorded on its stack ([`SearchGraph::with_new_goal`]), - /// but it's preferable to use other methods that call this one rather than this - /// method directly. + /// has had the nested goal recorded on its stack. This method only be used by + /// `search_graph::Delegate::compute_goal`. /// /// This function takes care of setting up the inference context, setting the anchor, /// and registering opaques from the canonicalized input. - fn enter_canonical<R>( + pub(super) fn enter_canonical<R>( cx: I, search_graph: &'a mut SearchGraph<D>, canonical_input: CanonicalInput<I>, @@ -398,56 +397,6 @@ where result } - /// The entry point of the solver. - /// - /// This function deals with (coinductive) cycles, overflow, and caching - /// and then calls [`EvalCtxt::compute_goal`] which contains the actual - /// logic of the solver. - /// - /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal] - /// if you're inside of the solver or [SolverDelegateEvalExt::evaluate_root_goal] if you're - /// outside of it. - #[instrument(level = "debug", skip(cx, search_graph, goal_evaluation), ret)] - fn evaluate_canonical_goal( - cx: I, - search_graph: &'a mut SearchGraph<D>, - canonical_input: CanonicalInput<I>, - step_kind_from_parent: PathKind, - goal_evaluation: &mut ProofTreeBuilder<D>, - ) -> QueryResult<I> { - let mut canonical_goal_evaluation = - goal_evaluation.new_canonical_goal_evaluation(canonical_input); - - // Deal with overflow, caching, and coinduction. - // - // The actual solver logic happens in `ecx.compute_goal`. - let result = ensure_sufficient_stack(|| { - search_graph.with_new_goal( - cx, - canonical_input, - step_kind_from_parent, - &mut canonical_goal_evaluation, - |search_graph, cx, canonical_input, canonical_goal_evaluation| { - EvalCtxt::enter_canonical( - cx, - search_graph, - canonical_input, - canonical_goal_evaluation, - |ecx, goal| { - let result = ecx.compute_goal(goal); - ecx.inspect.query_result(result); - result - }, - ) - }, - ) - }); - - canonical_goal_evaluation.query_result(result); - goal_evaluation.canonical_goal_evaluation(canonical_goal_evaluation); - result - } - /// Recursively evaluates `goal`, returning whether any inference vars have /// been constrained and the certainty of the result. fn evaluate_goal( @@ -501,18 +450,16 @@ where let (orig_values, canonical_goal) = self.canonicalize_goal(goal); let mut goal_evaluation = self.inspect.new_goal_evaluation(goal, &orig_values, goal_evaluation_kind); - let canonical_response = EvalCtxt::evaluate_canonical_goal( + let canonical_result = self.search_graph.evaluate_goal( self.cx(), - self.search_graph, canonical_goal, self.step_kind_for_source(source), &mut goal_evaluation, ); - let response = match canonical_response { - Err(e) => { - self.inspect.goal_evaluation(goal_evaluation); - return Err(e); - } + goal_evaluation.query_result(canonical_result); + self.inspect.goal_evaluation(goal_evaluation); + let response = match canonical_result { + Err(e) => return Err(e), Ok(response) => response, }; @@ -521,7 +468,6 @@ where let (normalization_nested_goals, certainty) = self.instantiate_and_apply_query_response(goal.param_env, &orig_values, response); - self.inspect.goal_evaluation(goal_evaluation); // FIXME: We previously had an assert here that checked that recomputing // a goal after applying its constraints did not change its response. @@ -582,7 +528,7 @@ where Ok((normalization_nested_goals, GoalEvaluation { certainty, has_changed, stalled_on })) } - fn compute_goal(&mut self, goal: Goal<I, I::Predicate>) -> QueryResult<I> { + pub(super) fn compute_goal(&mut self, goal: Goal<I, I::Predicate>) -> QueryResult<I> { let Goal { param_env, predicate } = goal; let kind = predicate.kind(); if let Some(kind) = kind.no_bound_vars() { diff --git a/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs b/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs index f22b275bc44..c8521624ebb 100644 --- a/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs +++ b/compiler/rustc_next_trait_solver/src/solve/inspect/build.rs @@ -13,8 +13,7 @@ use rustc_type_ir::{self as ty, Interner}; use crate::delegate::SolverDelegate; use crate::solve::eval_ctxt::canonical; use crate::solve::{ - CanonicalInput, Certainty, GenerateProofTree, Goal, GoalEvaluationKind, GoalSource, - QueryResult, inspect, + Certainty, GenerateProofTree, Goal, GoalEvaluationKind, GoalSource, QueryResult, inspect, }; /// The core data structure when building proof trees. @@ -54,7 +53,6 @@ where enum DebugSolver<I: Interner> { Root, GoalEvaluation(WipGoalEvaluation<I>), - CanonicalGoalEvaluation(WipCanonicalGoalEvaluation<I>), CanonicalGoalEvaluationStep(WipCanonicalGoalEvaluationStep<I>), } @@ -64,12 +62,6 @@ impl<I: Interner> From<WipGoalEvaluation<I>> for DebugSolver<I> { } } -impl<I: Interner> From<WipCanonicalGoalEvaluation<I>> for DebugSolver<I> { - fn from(g: WipCanonicalGoalEvaluation<I>) -> DebugSolver<I> { - DebugSolver::CanonicalGoalEvaluation(g) - } -} - impl<I: Interner> From<WipCanonicalGoalEvaluationStep<I>> for DebugSolver<I> { fn from(g: WipCanonicalGoalEvaluationStep<I>) -> DebugSolver<I> { DebugSolver::CanonicalGoalEvaluationStep(g) @@ -80,7 +72,10 @@ impl<I: Interner> From<WipCanonicalGoalEvaluationStep<I>> for DebugSolver<I> { struct WipGoalEvaluation<I: Interner> { pub uncanonicalized_goal: Goal<I, I::Predicate>, pub orig_values: Vec<I::GenericArg>, - pub evaluation: Option<WipCanonicalGoalEvaluation<I>>, + pub encountered_overflow: bool, + /// After we finished evaluating this is moved into `kind`. + pub final_revision: Option<WipCanonicalGoalEvaluationStep<I>>, + pub result: Option<QueryResult<I>>, } impl<I: Interner> WipGoalEvaluation<I> { @@ -88,31 +83,12 @@ impl<I: Interner> WipGoalEvaluation<I> { inspect::GoalEvaluation { uncanonicalized_goal: self.uncanonicalized_goal, orig_values: self.orig_values, - evaluation: self.evaluation.unwrap().finalize(), - } - } -} - -#[derive_where(PartialEq, Eq, Debug; I: Interner)] -struct WipCanonicalGoalEvaluation<I: Interner> { - goal: CanonicalInput<I>, - encountered_overflow: bool, - /// Only used for uncached goals. After we finished evaluating - /// the goal, this is interned and moved into `kind`. - final_revision: Option<WipCanonicalGoalEvaluationStep<I>>, - result: Option<QueryResult<I>>, -} - -impl<I: Interner> WipCanonicalGoalEvaluation<I> { - fn finalize(self) -> inspect::CanonicalGoalEvaluation<I> { - inspect::CanonicalGoalEvaluation { - goal: self.goal, kind: if self.encountered_overflow { assert!(self.final_revision.is_none()); - inspect::CanonicalGoalEvaluationKind::Overflow + inspect::GoalEvaluationKind::Overflow } else { let final_revision = self.final_revision.unwrap().finalize(); - inspect::CanonicalGoalEvaluationKind::Evaluation { final_revision } + inspect::GoalEvaluationKind::Evaluation { final_revision } }, result: self.result.unwrap(), } @@ -256,55 +232,27 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> ProofTreeBuilder<D> { pub(in crate::solve) fn new_goal_evaluation( &mut self, - goal: Goal<I, I::Predicate>, + uncanonicalized_goal: Goal<I, I::Predicate>, orig_values: &[I::GenericArg], kind: GoalEvaluationKind, ) -> ProofTreeBuilder<D> { self.opt_nested(|| match kind { GoalEvaluationKind::Root => Some(WipGoalEvaluation { - uncanonicalized_goal: goal, + uncanonicalized_goal, orig_values: orig_values.to_vec(), - evaluation: None, + encountered_overflow: false, + final_revision: None, + result: None, }), GoalEvaluationKind::Nested => None, }) } - pub(crate) fn new_canonical_goal_evaluation( - &mut self, - goal: CanonicalInput<I>, - ) -> ProofTreeBuilder<D> { - self.nested(|| WipCanonicalGoalEvaluation { - goal, - encountered_overflow: false, - final_revision: None, - result: None, - }) - } - - pub(crate) fn canonical_goal_evaluation( - &mut self, - canonical_goal_evaluation: ProofTreeBuilder<D>, - ) { - if let Some(this) = self.as_mut() { - match (this, *canonical_goal_evaluation.state.unwrap()) { - ( - DebugSolver::GoalEvaluation(goal_evaluation), - DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation), - ) => { - let prev = goal_evaluation.evaluation.replace(canonical_goal_evaluation); - assert_eq!(prev, None); - } - _ => unreachable!(), - } - } - } - pub(crate) fn canonical_goal_evaluation_overflow(&mut self) { if let Some(this) = self.as_mut() { match this { - DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => { - canonical_goal_evaluation.encountered_overflow = true; + DebugSolver::GoalEvaluation(goal_evaluation) => { + goal_evaluation.encountered_overflow = true; } _ => unreachable!(), }; @@ -343,10 +291,10 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> ProofTreeBuilder<D> { if let Some(this) = self.as_mut() { match (this, *goal_evaluation_step.state.unwrap()) { ( - DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluations), + DebugSolver::GoalEvaluation(goal_evaluation), DebugSolver::CanonicalGoalEvaluationStep(goal_evaluation_step), ) => { - canonical_goal_evaluations.final_revision = Some(goal_evaluation_step); + goal_evaluation.final_revision = Some(goal_evaluation_step); } _ => unreachable!(), } @@ -489,8 +437,8 @@ impl<D: SolverDelegate<Interner = I>, I: Interner> ProofTreeBuilder<D> { pub(crate) fn query_result(&mut self, result: QueryResult<I>) { if let Some(this) = self.as_mut() { match this { - DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => { - assert_eq!(canonical_goal_evaluation.result.replace(result), None); + DebugSolver::GoalEvaluation(goal_evaluation) => { + assert_eq!(goal_evaluation.result.replace(result), None); } DebugSolver::CanonicalGoalEvaluationStep(evaluation_step) => { assert_eq!( diff --git a/compiler/rustc_next_trait_solver/src/solve/search_graph.rs b/compiler/rustc_next_trait_solver/src/solve/search_graph.rs index ecffbbff7a2..12cbc7e8f91 100644 --- a/compiler/rustc_next_trait_solver/src/solve/search_graph.rs +++ b/compiler/rustc_next_trait_solver/src/solve/search_graph.rs @@ -1,13 +1,14 @@ use std::convert::Infallible; use std::marker::PhantomData; +use rustc_type_ir::data_structures::ensure_sufficient_stack; use rustc_type_ir::search_graph::{self, PathKind}; use rustc_type_ir::solve::{CanonicalInput, Certainty, NoSolution, QueryResult}; use rustc_type_ir::{Interner, TypingMode}; -use super::inspect::ProofTreeBuilder; -use super::{FIXPOINT_STEP_LIMIT, has_no_inference_or_external_constraints}; use crate::delegate::SolverDelegate; +use crate::solve::inspect::ProofTreeBuilder; +use crate::solve::{EvalCtxt, FIXPOINT_STEP_LIMIT, has_no_inference_or_external_constraints}; /// This type is never constructed. We only use it to implement `search_graph::Delegate` /// for all types which impl `SolverDelegate` and doing it directly fails in coherence. @@ -80,8 +81,8 @@ where fn on_stack_overflow( cx: I, - inspect: &mut ProofTreeBuilder<D>, input: CanonicalInput<I>, + inspect: &mut ProofTreeBuilder<D>, ) -> QueryResult<I> { inspect.canonical_goal_evaluation_overflow(); response_no_constraints(cx, input, Certainty::overflow(true)) @@ -106,6 +107,21 @@ where let certainty = from_result.unwrap().value.certainty; response_no_constraints(cx, for_input, certainty) } + + fn compute_goal( + search_graph: &mut SearchGraph<D>, + cx: I, + input: CanonicalInput<I>, + inspect: &mut Self::ProofTreeBuilder, + ) -> QueryResult<I> { + ensure_sufficient_stack(|| { + EvalCtxt::enter_canonical(cx, search_graph, input, inspect, |ecx, goal| { + let result = ecx.compute_goal(goal); + ecx.inspect.query_result(result); + result + }) + }) + } } fn response_no_constraints<I: Interner>( diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs index 80df0fab2d8..308486811e6 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs @@ -37,7 +37,7 @@ pub struct InspectGoal<'a, 'tcx> { orig_values: Vec<ty::GenericArg<'tcx>>, goal: Goal<'tcx, ty::Predicate<'tcx>>, result: Result<Certainty, NoSolution>, - evaluation_kind: inspect::CanonicalGoalEvaluationKind<TyCtxt<'tcx>>, + evaluation_kind: inspect::GoalEvaluationKind<TyCtxt<'tcx>>, normalizes_to_term_hack: Option<NormalizesToTermHack<'tcx>>, source: GoalSource, } @@ -393,8 +393,8 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { let mut candidates = vec![]; let last_eval_step = match &self.evaluation_kind { // An annoying edge case in case the recursion limit is 0. - inspect::CanonicalGoalEvaluationKind::Overflow => return vec![], - inspect::CanonicalGoalEvaluationKind::Evaluation { final_revision } => final_revision, + inspect::GoalEvaluationKind::Overflow => return vec![], + inspect::GoalEvaluationKind::Evaluation { final_revision } => final_revision, }; let mut nested_goals = vec![]; @@ -426,10 +426,10 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { ) -> Self { let infcx = <&SolverDelegate<'tcx>>::from(infcx); - let inspect::GoalEvaluation { uncanonicalized_goal, orig_values, evaluation } = root; + let inspect::GoalEvaluation { uncanonicalized_goal, orig_values, kind, result } = root; // If there's a normalizes-to goal, AND the evaluation result with the result of // constraining the normalizes-to RHS and computing the nested goals. - let result = evaluation.result.and_then(|ok| { + let result = result.and_then(|ok| { let nested_goals_certainty = term_hack_and_nested_certainty.map_or(Ok(Certainty::Yes), |(_, c)| c)?; Ok(ok.value.certainty.and(nested_goals_certainty)) @@ -441,7 +441,7 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { orig_values, goal: eager_resolve_vars(infcx, uncanonicalized_goal), result, - evaluation_kind: evaluation.kind, + evaluation_kind: kind, normalizes_to_term_hack: term_hack_and_nested_certainty.map(|(n, _)| n), source, } diff --git a/compiler/rustc_type_ir/src/search_graph/mod.rs b/compiler/rustc_type_ir/src/search_graph/mod.rs index a857da2fcd5..8941360d2d0 100644 --- a/compiler/rustc_type_ir/src/search_graph/mod.rs +++ b/compiler/rustc_type_ir/src/search_graph/mod.rs @@ -21,7 +21,7 @@ use std::marker::PhantomData; use derive_where::derive_where; #[cfg(feature = "nightly")] use rustc_macros::{Decodable_NoContext, Encodable_NoContext, HashStable_NoContext}; -use tracing::debug; +use tracing::{debug, instrument}; use crate::data_structures::HashMap; @@ -56,7 +56,7 @@ pub trait Cx: Copy { fn evaluation_is_concurrent(&self) -> bool; } -pub trait Delegate { +pub trait Delegate: Sized { type Cx: Cx; /// Whether to use the provisional cache. Set to `false` by a fuzzer when /// validating the search graph. @@ -94,8 +94,8 @@ pub trait Delegate { ) -> bool; fn on_stack_overflow( cx: Self::Cx, - inspect: &mut Self::ProofTreeBuilder, input: <Self::Cx as Cx>::Input, + inspect: &mut Self::ProofTreeBuilder, ) -> <Self::Cx as Cx>::Result; fn on_fixpoint_overflow( cx: Self::Cx, @@ -108,6 +108,13 @@ pub trait Delegate { for_input: <Self::Cx as Cx>::Input, from_result: <Self::Cx as Cx>::Result, ) -> <Self::Cx as Cx>::Result; + + fn compute_goal( + search_graph: &mut SearchGraph<Self>, + cx: Self::Cx, + input: <Self::Cx as Cx>::Input, + inspect: &mut Self::ProofTreeBuilder, + ) -> <Self::Cx as Cx>::Result; } /// In the initial iteration of a cycle, we do not yet have a provisional @@ -589,15 +596,15 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { /// Probably the most involved method of the whole solver. /// - /// Given some goal which is proven via the `prove_goal` closure, this - /// handles caching, overflow, and coinductive cycles. - pub fn with_new_goal( + /// While goals get computed via `D::compute_goal`, this function handles + /// caching, overflow, and cycles. + #[instrument(level = "debug", skip(self, cx, inspect), ret)] + pub fn evaluate_goal( &mut self, cx: X, input: X::Input, step_kind_from_parent: PathKind, inspect: &mut D::ProofTreeBuilder, - evaluate_goal: impl Fn(&mut Self, X, X::Input, &mut D::ProofTreeBuilder) -> X::Result + Copy, ) -> X::Result { let Some(available_depth) = AvailableDepth::allowed_depth_for_nested::<D>(self.root_depth, &self.stack) @@ -666,7 +673,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { // must not be added to the global cache. Notably, this is the case for // trait solver cycles participants. let (evaluation_result, dep_node) = - cx.with_cached_task(|| self.evaluate_goal_in_task(cx, input, inspect, evaluate_goal)); + cx.with_cached_task(|| self.evaluate_goal_in_task(cx, input, inspect)); // We've finished computing the goal and have popped it from the stack, // lazily update its parent goal. @@ -736,7 +743,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { } debug!("encountered stack overflow"); - D::on_stack_overflow(cx, inspect, input) + D::on_stack_overflow(cx, input, inspect) } /// When reevaluating a goal with a changed provisional result, all provisional cache entry @@ -1064,7 +1071,6 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { cx: X, input: X::Input, inspect: &mut D::ProofTreeBuilder, - evaluate_goal: impl Fn(&mut Self, X, X::Input, &mut D::ProofTreeBuilder) -> X::Result + Copy, ) -> EvaluationResult<X> { // We reset `encountered_overflow` each time we rerun this goal // but need to make sure we currently propagate it to the global @@ -1073,7 +1079,7 @@ impl<D: Delegate<Cx = X>, X: Cx> SearchGraph<D> { let mut encountered_overflow = false; let mut i = 0; loop { - let result = evaluate_goal(self, cx, input, inspect); + let result = D::compute_goal(self, cx, input, inspect); let stack_entry = self.stack.pop(); encountered_overflow |= stack_entry.encountered_overflow; debug_assert_eq!(stack_entry.input, input); diff --git a/compiler/rustc_type_ir/src/solve/inspect.rs b/compiler/rustc_type_ir/src/solve/inspect.rs index b10641b287d..089695d0475 100644 --- a/compiler/rustc_type_ir/src/solve/inspect.rs +++ b/compiler/rustc_type_ir/src/solve/inspect.rs @@ -23,7 +23,7 @@ use std::hash::Hash; use derive_where::derive_where; use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic}; -use crate::solve::{CandidateSource, CanonicalInput, Certainty, Goal, GoalSource, QueryResult}; +use crate::solve::{CandidateSource, Certainty, Goal, GoalSource, QueryResult}; use crate::{Canonical, CanonicalVarValues, Interner}; /// Some `data` together with information about how they relate to the input @@ -54,18 +54,12 @@ pub type CanonicalState<I, T> = Canonical<I, State<I, T>>; pub struct GoalEvaluation<I: Interner> { pub uncanonicalized_goal: Goal<I, I::Predicate>, pub orig_values: Vec<I::GenericArg>, - pub evaluation: CanonicalGoalEvaluation<I>, -} - -#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)] -pub struct CanonicalGoalEvaluation<I: Interner> { - pub goal: CanonicalInput<I>, - pub kind: CanonicalGoalEvaluationKind<I>, + pub kind: GoalEvaluationKind<I>, pub result: QueryResult<I>, } #[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)] -pub enum CanonicalGoalEvaluationKind<I: Interner> { +pub enum GoalEvaluationKind<I: Interner> { Overflow, Evaluation { /// This is always `ProbeKind::Root`. |