diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
5 files changed, 187 insertions, 121 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs index afd9d95cb57..67657c81cf6 100644 --- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs +++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs @@ -36,11 +36,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let Goal { param_env, predicate: (lhs, rhs, direction) } = goal; let Some(lhs) = self.try_normalize_term(param_env, lhs)? else { - return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); + return self + .evaluate_added_goals_and_make_canonical_response(Certainty::overflow(true)); }; let Some(rhs) = self.try_normalize_term(param_env, rhs)? else { - return self.evaluate_added_goals_and_make_canonical_response(Certainty::OVERFLOW); + return self + .evaluate_added_goals_and_make_canonical_response(Certainty::overflow(true)); }; let variance = match direction { diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs index 4a86f708632..98d28f10a54 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs @@ -7,6 +7,7 @@ use rustc_infer::infer::{ BoundRegionConversionTime, DefineOpaqueTypes, InferCtxt, InferOk, TyCtxtInferExt, }; use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::solve::MaybeCause; use rustc_infer::traits::ObligationCause; use rustc_middle::infer::canonical::CanonicalVarInfos; use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; @@ -29,7 +30,7 @@ use std::ops::ControlFlow; use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; use super::inspect::ProofTreeBuilder; -use super::{search_graph, GoalEvaluationKind}; +use super::{search_graph, GoalEvaluationKind, FIXPOINT_STEP_LIMIT}; use super::{search_graph::SearchGraph, Goal}; use super::{GoalSource, SolverMode}; pub use select::InferCtxtSelectExt; @@ -154,10 +155,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { self.search_graph.solver_mode() } - pub(super) fn local_overflow_limit(&self) -> usize { - self.search_graph.local_overflow_limit() - } - /// Creates a root evaluation context and search graph. This should only be /// used from outside of any evaluation, and other methods should be preferred /// over using this manually (such as [`InferCtxtEvalExt::evaluate_root_goal`]). @@ -167,7 +164,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> R, ) -> (R, Option<inspect::GoalEvaluation<'tcx>>) { let mode = if infcx.intercrate { SolverMode::Coherence } else { SolverMode::Normal }; - let mut search_graph = search_graph::SearchGraph::new(infcx.tcx, mode); + let mut search_graph = search_graph::SearchGraph::new(mode); let mut ecx = EvalCtxt { search_graph: &mut search_graph, @@ -388,16 +385,18 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { && source != GoalSource::ImplWhereBound }; - if response.value.certainty == Certainty::OVERFLOW && !keep_overflow_constraints() { - (Certainty::OVERFLOW, false) - } else { - let has_changed = !response.value.var_values.is_identity_modulo_regions() - || !response.value.external_constraints.opaque_types.is_empty(); - - let certainty = - self.instantiate_and_apply_query_response(param_env, original_values, response); - (certainty, has_changed) + if let Certainty::Maybe(MaybeCause::Overflow { .. }) = response.value.certainty + && !keep_overflow_constraints() + { + return (response.value.certainty, false); } + + let has_changed = !response.value.var_values.is_identity_modulo_regions() + || !response.value.external_constraints.opaque_types.is_empty(); + + let certainty = + self.instantiate_and_apply_query_response(param_env, original_values, response); + (certainty, has_changed) } fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { @@ -466,8 +465,8 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let inspect = self.inspect.new_evaluate_added_goals(); let inspect = core::mem::replace(&mut self.inspect, inspect); - let mut response = Ok(Certainty::OVERFLOW); - for _ in 0..self.local_overflow_limit() { + let mut response = Ok(Certainty::overflow(false)); + for _ in 0..FIXPOINT_STEP_LIMIT { // FIXME: This match is a bit ugly, it might be nice to change the inspect // stuff to use a closure instead. which should hopefully simplify this a bit. match self.evaluate_added_goals_step() { diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index c1b07765e50..bc2bae9da61 100644 --- a/compiler/rustc_trait_selection/src/solve/fulfill.rs +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -24,7 +24,7 @@ use super::{Certainty, InferCtxtEvalExt}; /// It is also likely that we want to use slightly different datastructures /// here as this will have to deal with far more root goals than `evaluate_all`. pub struct FulfillmentCtxt<'tcx> { - obligations: Vec<PredicateObligation<'tcx>>, + obligations: ObligationStorage<'tcx>, /// The snapshot in which this context was created. Using the context /// outside of this snapshot leads to subtle bugs if the snapshot @@ -33,6 +33,57 @@ pub struct FulfillmentCtxt<'tcx> { usable_in_snapshot: usize, } +#[derive(Default)] +struct ObligationStorage<'tcx> { + /// Obligations which resulted in an overflow in fulfillment itself. + /// + /// We cannot eagerly return these as error so we instead store them here + /// to avoid recomputing them each time `select_where_possible` is called. + /// This also allows us to return the correct `FulfillmentError` for them. + overflowed: Vec<PredicateObligation<'tcx>>, + pending: Vec<PredicateObligation<'tcx>>, +} + +impl<'tcx> ObligationStorage<'tcx> { + fn register(&mut self, obligation: PredicateObligation<'tcx>) { + self.pending.push(obligation); + } + + fn clone_pending(&self) -> Vec<PredicateObligation<'tcx>> { + let mut obligations = self.pending.clone(); + obligations.extend(self.overflowed.iter().cloned()); + obligations + } + + fn take_pending(&mut self) -> Vec<PredicateObligation<'tcx>> { + let mut obligations = mem::take(&mut self.pending); + obligations.extend(self.overflowed.drain(..)); + obligations + } + + fn unstalled_for_select(&mut self) -> impl Iterator<Item = PredicateObligation<'tcx>> { + mem::take(&mut self.pending).into_iter() + } + + fn on_fulfillment_overflow(&mut self, infcx: &InferCtxt<'tcx>) { + infcx.probe(|_| { + // IMPORTANT: we must not use solve any inference variables in the obligations + // as this is all happening inside of a probe. We use a probe to make sure + // we get all obligations involved in the overflow. We pretty much check: if + // we were to do another step of `select_where_possible`, which goals would + // change. + self.overflowed.extend(self.pending.extract_if(|o| { + let goal = o.clone().into(); + let result = infcx.evaluate_root_goal(goal, GenerateProofTree::Never).0; + match result { + Ok((has_changed, _)) => has_changed, + _ => false, + } + })); + }) + } +} + impl<'tcx> FulfillmentCtxt<'tcx> { pub fn new(infcx: &InferCtxt<'tcx>) -> FulfillmentCtxt<'tcx> { assert!( @@ -40,7 +91,10 @@ impl<'tcx> FulfillmentCtxt<'tcx> { "new trait solver fulfillment context created when \ infcx is set up for old trait solver" ); - FulfillmentCtxt { obligations: Vec::new(), usable_in_snapshot: infcx.num_open_snapshots() } + FulfillmentCtxt { + obligations: Default::default(), + usable_in_snapshot: infcx.num_open_snapshots(), + } } fn inspect_evaluated_obligation( @@ -67,40 +121,24 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { obligation: PredicateObligation<'tcx>, ) { assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots()); - self.obligations.push(obligation); + self.obligations.register(obligation); } fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { - self.obligations + let mut errors: Vec<_> = self + .obligations + .pending .drain(..) - .map(|obligation| { - let code = infcx.probe(|_| { - match infcx - .evaluate_root_goal(obligation.clone().into(), GenerateProofTree::IfEnabled) - .0 - { - Ok((_, Certainty::Maybe(MaybeCause::Ambiguity))) => { - FulfillmentErrorCode::Ambiguity { overflow: false } - } - Ok((_, Certainty::Maybe(MaybeCause::Overflow))) => { - FulfillmentErrorCode::Ambiguity { overflow: true } - } - Ok((_, Certainty::Yes)) => { - bug!("did not expect successful goal when collecting ambiguity errors") - } - Err(_) => { - bug!("did not expect selection error when collecting ambiguity errors") - } - } - }); + .map(|obligation| fulfillment_error_for_stalled(infcx, obligation)) + .collect(); - FulfillmentError { - obligation: obligation.clone(), - code, - root_obligation: obligation, - } - }) - .collect() + errors.extend(self.obligations.overflowed.drain(..).map(|obligation| FulfillmentError { + root_obligation: obligation.clone(), + code: FulfillmentErrorCode::Ambiguity { overflow: Some(true) }, + obligation, + })); + + errors } fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { @@ -108,79 +146,27 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { let mut errors = Vec::new(); for i in 0.. { if !infcx.tcx.recursion_limit().value_within_limit(i) { - // Only return true errors that we have accumulated while processing; - // keep ambiguities around, *including overflows*, because they shouldn't - // be considered true errors. + self.obligations.on_fulfillment_overflow(infcx); + // Only return true errors that we have accumulated while processing. return errors; } let mut has_changed = false; - for obligation in mem::take(&mut self.obligations) { + for obligation in self.obligations.unstalled_for_select() { let goal = obligation.clone().into(); let result = infcx.evaluate_root_goal(goal, GenerateProofTree::IfEnabled).0; self.inspect_evaluated_obligation(infcx, &obligation, &result); let (changed, certainty) = match result { Ok(result) => result, Err(NoSolution) => { - errors.push(FulfillmentError { - obligation: obligation.clone(), - code: match goal.predicate.kind().skip_binder() { - ty::PredicateKind::Clause(ty::ClauseKind::Projection(_)) => { - FulfillmentErrorCode::ProjectionError( - // FIXME: This could be a `Sorts` if the term is a type - MismatchedProjectionTypes { err: TypeError::Mismatch }, - ) - } - ty::PredicateKind::NormalizesTo(..) => { - FulfillmentErrorCode::ProjectionError( - MismatchedProjectionTypes { err: TypeError::Mismatch }, - ) - } - ty::PredicateKind::AliasRelate(_, _, _) => { - FulfillmentErrorCode::ProjectionError( - MismatchedProjectionTypes { err: TypeError::Mismatch }, - ) - } - ty::PredicateKind::Subtype(pred) => { - let (a, b) = infcx.enter_forall_and_leak_universe( - goal.predicate.kind().rebind((pred.a, pred.b)), - ); - let expected_found = ExpectedFound::new(true, a, b); - FulfillmentErrorCode::SubtypeError( - expected_found, - TypeError::Sorts(expected_found), - ) - } - ty::PredicateKind::Coerce(pred) => { - let (a, b) = infcx.enter_forall_and_leak_universe( - goal.predicate.kind().rebind((pred.a, pred.b)), - ); - let expected_found = ExpectedFound::new(false, a, b); - FulfillmentErrorCode::SubtypeError( - expected_found, - TypeError::Sorts(expected_found), - ) - } - ty::PredicateKind::Clause(_) - | ty::PredicateKind::ObjectSafe(_) - | ty::PredicateKind::Ambiguous => { - FulfillmentErrorCode::SelectionError( - SelectionError::Unimplemented, - ) - } - ty::PredicateKind::ConstEquate(..) => { - bug!("unexpected goal: {goal:?}") - } - }, - root_obligation: obligation, - }); + errors.push(fulfillment_error_for_no_solution(infcx, obligation)); continue; } }; has_changed |= changed; match certainty { Certainty::Yes => {} - Certainty::Maybe(_) => self.obligations.push(obligation), + Certainty::Maybe(_) => self.obligations.register(obligation), } } @@ -193,13 +179,84 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { } fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> { - self.obligations.clone() + self.obligations.clone_pending() } fn drain_unstalled_obligations( &mut self, _: &InferCtxt<'tcx>, ) -> Vec<PredicateObligation<'tcx>> { - std::mem::take(&mut self.obligations) + self.obligations.take_pending() } } + +fn fulfillment_error_for_no_solution<'tcx>( + infcx: &InferCtxt<'tcx>, + obligation: PredicateObligation<'tcx>, +) -> FulfillmentError<'tcx> { + let code = match obligation.predicate.kind().skip_binder() { + ty::PredicateKind::Clause(ty::ClauseKind::Projection(_)) => { + FulfillmentErrorCode::ProjectionError( + // FIXME: This could be a `Sorts` if the term is a type + MismatchedProjectionTypes { err: TypeError::Mismatch }, + ) + } + ty::PredicateKind::NormalizesTo(..) => { + FulfillmentErrorCode::ProjectionError(MismatchedProjectionTypes { + err: TypeError::Mismatch, + }) + } + ty::PredicateKind::AliasRelate(_, _, _) => { + FulfillmentErrorCode::ProjectionError(MismatchedProjectionTypes { + err: TypeError::Mismatch, + }) + } + ty::PredicateKind::Subtype(pred) => { + let (a, b) = infcx.enter_forall_and_leak_universe( + obligation.predicate.kind().rebind((pred.a, pred.b)), + ); + let expected_found = ExpectedFound::new(true, a, b); + FulfillmentErrorCode::SubtypeError(expected_found, TypeError::Sorts(expected_found)) + } + ty::PredicateKind::Coerce(pred) => { + let (a, b) = infcx.enter_forall_and_leak_universe( + obligation.predicate.kind().rebind((pred.a, pred.b)), + ); + let expected_found = ExpectedFound::new(false, a, b); + FulfillmentErrorCode::SubtypeError(expected_found, TypeError::Sorts(expected_found)) + } + ty::PredicateKind::Clause(_) + | ty::PredicateKind::ObjectSafe(_) + | ty::PredicateKind::Ambiguous => { + FulfillmentErrorCode::SelectionError(SelectionError::Unimplemented) + } + ty::PredicateKind::ConstEquate(..) => { + bug!("unexpected goal: {obligation:?}") + } + }; + FulfillmentError { root_obligation: obligation.clone(), code, obligation } +} + +fn fulfillment_error_for_stalled<'tcx>( + infcx: &InferCtxt<'tcx>, + obligation: PredicateObligation<'tcx>, +) -> FulfillmentError<'tcx> { + let code = infcx.probe(|_| { + match infcx.evaluate_root_goal(obligation.clone().into(), GenerateProofTree::Never).0 { + Ok((_, Certainty::Maybe(MaybeCause::Ambiguity))) => { + FulfillmentErrorCode::Ambiguity { overflow: None } + } + Ok((_, Certainty::Maybe(MaybeCause::Overflow { suggest_increasing_limit }))) => { + FulfillmentErrorCode::Ambiguity { overflow: Some(suggest_increasing_limit) } + } + Ok((_, Certainty::Yes)) => { + bug!("did not expect successful goal when collecting ambiguity errors") + } + Err(_) => { + bug!("did not expect selection error when collecting ambiguity errors") + } + } + }); + + FulfillmentError { obligation: obligation.clone(), code, root_obligation: obligation } +} diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 51094b781c0..0bf28f520a4 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -42,6 +42,17 @@ pub use fulfill::FulfillmentCtxt; pub(crate) use normalize::deeply_normalize_for_diagnostics; pub use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes}; +/// How many fixpoint iterations we should attempt inside of the solver before bailing +/// with overflow. +/// +/// We previously used `tcx.recursion_limit().0.checked_ilog2().unwrap_or(0)` for this. +/// However, it feels unlikely that uncreasing the recursion limit by a power of two +/// to get one more itereation is every useful or desirable. We now instead used a constant +/// here. If there ever ends up some use-cases where a bigger number of fixpoint iterations +/// is required, we can add a new attribute for that or revert this to be dependant on the +/// recursion limit again. However, this feels very unlikely. +const FIXPOINT_STEP_LIMIT: usize = 8; + #[derive(Debug, Clone, Copy)] enum SolverMode { /// Ordinary trait solving, using everywhere except for coherence. diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs index bede94a2e43..07a8aca85a0 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs @@ -1,3 +1,5 @@ +use crate::solve::FIXPOINT_STEP_LIMIT; + use super::inspect; use super::inspect::ProofTreeBuilder; use super::SolverMode; @@ -99,7 +101,6 @@ impl<'tcx> ProvisionalCacheEntry<'tcx> { pub(super) struct SearchGraph<'tcx> { mode: SolverMode, - local_overflow_limit: usize, /// The stack of goals currently being computed. /// /// An element is *deeper* in the stack if its index is *lower*. @@ -116,10 +117,9 @@ pub(super) struct SearchGraph<'tcx> { } impl<'tcx> SearchGraph<'tcx> { - pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> { + pub(super) fn new(mode: SolverMode) -> SearchGraph<'tcx> { Self { mode, - local_overflow_limit: tcx.recursion_limit().0.checked_ilog2().unwrap_or(0) as usize, stack: Default::default(), provisional_cache: Default::default(), cycle_participants: Default::default(), @@ -130,10 +130,6 @@ impl<'tcx> SearchGraph<'tcx> { self.mode } - pub(super) fn local_overflow_limit(&self) -> usize { - self.local_overflow_limit - } - /// Update the stack and reached depths on cache hits. #[instrument(level = "debug", skip(self))] fn on_cache_hit(&mut self, additional_depth: usize, encountered_overflow: bool) { @@ -277,7 +273,7 @@ impl<'tcx> SearchGraph<'tcx> { } inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::Overflow); - return Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); + return Self::response_no_constraints(tcx, input, Certainty::overflow(true)); }; // Try to fetch the goal from the global cache. @@ -370,7 +366,7 @@ impl<'tcx> SearchGraph<'tcx> { } else if is_coinductive_cycle { Self::response_no_constraints(tcx, input, Certainty::Yes) } else { - Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) + Self::response_no_constraints(tcx, input, Certainty::overflow(false)) }; } else { // No entry, we push this goal on the stack and try to prove it. @@ -398,7 +394,7 @@ impl<'tcx> SearchGraph<'tcx> { // of this we continuously recompute the cycle until the result // of the previous iteration is equal to the final result, at which // point we are done. - for _ in 0..self.local_overflow_limit() { + for _ in 0..FIXPOINT_STEP_LIMIT { let result = prove_goal(self, inspect); let stack_entry = self.pop_stack(); debug_assert_eq!(stack_entry.input, input); @@ -431,7 +427,8 @@ impl<'tcx> SearchGraph<'tcx> { } else if stack_entry.has_been_used == HasBeenUsed::COINDUCTIVE_CYCLE { Self::response_no_constraints(tcx, input, Certainty::Yes) == result } else if stack_entry.has_been_used == HasBeenUsed::INDUCTIVE_CYCLE { - Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) == result + Self::response_no_constraints(tcx, input, Certainty::overflow(false)) + == result } else { false }; @@ -452,7 +449,7 @@ impl<'tcx> SearchGraph<'tcx> { debug!("canonical cycle overflow"); let current_entry = self.pop_stack(); debug_assert!(current_entry.has_been_used.is_empty()); - let result = Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); + let result = Self::response_no_constraints(tcx, input, Certainty::overflow(false)); (current_entry, result) }); |