diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
9 files changed, 233 insertions, 157 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/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 4c4cd2af779..3be53a6591d 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -394,10 +394,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ty::Infer(ty::FloatVar(_)) => { // This causes a compiler error if any new float kinds are added. - let (ty::FloatTy::F32 | ty::FloatTy::F64); + let (ty::FloatTy::F16 | ty::FloatTy::F32 | ty::FloatTy::F64 | ty::FloatTy::F128); let possible_floats = [ + SimplifiedType::Float(ty::FloatTy::F16), SimplifiedType::Float(ty::FloatTy::F32), SimplifiedType::Float(ty::FloatTy::F64), + SimplifiedType::Float(ty::FloatTy::F128), ]; for simp in possible_floats { 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 ed428bb8e66..22f52c27362 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() { @@ -649,8 +648,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTermOrNotNameable<'_, 'tcx> { - type BreakTy = (); - fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { + type Result = ControlFlow<()>; + fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result { match *t.kind() { ty::Infer(ty::TyVar(vid)) => { if let ty::TermKind::Ty(term) = self.term.unpack() @@ -673,7 +672,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { + fn visit_const(&mut self, c: ty::Const<'tcx>) -> Self::Result { match c.kind() { ty::ConstKind::Infer(ty::InferConst::Var(vid)) => { if let ty::TermKind::Const(term) = self.term.unpack() @@ -874,7 +873,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn is_transmutable( &self, src_and_dst: rustc_transmute::Types<'tcx>, - scope: Ty<'tcx>, assume: rustc_transmute::Assume, ) -> Result<Certainty, NoSolution> { use rustc_transmute::Answer; @@ -882,7 +880,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable( ObligationCause::dummy(), src_and_dst, - scope, assume, ) { Answer::Yes => Ok(Certainty::Yes), @@ -906,7 +903,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { &ObligationCause::dummy(), param_env, hidden_ty, - true, &mut obligations, )?; self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index c1b07765e50..3fa409eefff 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.append(&mut self.overflowed); + 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/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs index 52b900af853..9e3e6a4676e 100644 --- a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs +++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs @@ -1,15 +1,16 @@ -/// An infrastructure to mechanically analyse proof trees. -/// -/// It is unavoidable that this representation is somewhat -/// lossy as it should hide quite a few semantically relevant things, -/// e.g. canonicalization and the order of nested goals. -/// -/// @lcnr: However, a lot of the weirdness here is not strictly necessary -/// and could be improved in the future. This is mostly good enough for -/// coherence right now and was annoying to implement, so I am leaving it -/// as is until we start using it for something else. -use std::ops::ControlFlow; - +//! An infrastructure to mechanically analyse proof trees. +//! +//! It is unavoidable that this representation is somewhat +//! lossy as it should hide quite a few semantically relevant things, +//! e.g. canonicalization and the order of nested goals. +//! +//! @lcnr: However, a lot of the weirdness here is not strictly necessary +//! and could be improved in the future. This is mostly good enough for +//! coherence right now and was annoying to implement, so I am leaving it +//! as is until we start using it for something else. + +use rustc_ast_ir::try_visit; +use rustc_ast_ir::visit::VisitorResult; use rustc_infer::infer::InferCtxt; use rustc_middle::traits::query::NoSolution; use rustc_middle::traits::solve::{inspect, QueryResult}; @@ -53,10 +54,7 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> { /// to also use it to compute the most relevant goal /// for fulfillment errors. Will do that once we actually /// need it. - pub fn visit_nested<V: ProofTreeVisitor<'tcx>>( - &self, - visitor: &mut V, - ) -> ControlFlow<V::BreakTy> { + pub fn visit_nested<V: ProofTreeVisitor<'tcx>>(&self, visitor: &mut V) -> V::Result { // HACK: An arbitrary cutoff to avoid dealing with overflow and cycles. if self.goal.depth <= 10 { let infcx = self.goal.infcx; @@ -75,17 +73,18 @@ impl<'a, 'tcx> InspectCandidate<'a, 'tcx> { for &goal in &instantiated_goals { let (_, proof_tree) = infcx.evaluate_root_goal(goal, GenerateProofTree::Yes); let proof_tree = proof_tree.unwrap(); - visitor.visit_goal(&InspectGoal::new( + try_visit!(visitor.visit_goal(&InspectGoal::new( infcx, self.goal.depth + 1, &proof_tree, - ))?; + ))); } - ControlFlow::Continue(()) - })?; + V::Result::output() + }) + } else { + V::Result::output() } - ControlFlow::Continue(()) } } @@ -202,9 +201,9 @@ impl<'a, 'tcx> InspectGoal<'a, 'tcx> { /// The public API to interact with proof trees. pub trait ProofTreeVisitor<'tcx> { - type BreakTy; + type Result: VisitorResult = (); - fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> ControlFlow<Self::BreakTy>; + fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> Self::Result; } #[extension(pub trait ProofTreeInferCtxtExt<'tcx>)] @@ -213,7 +212,7 @@ impl<'tcx> InferCtxt<'tcx> { &self, goal: Goal<'tcx, ty::Predicate<'tcx>>, visitor: &mut V, - ) -> ControlFlow<V::BreakTy> { + ) -> V::Result { self.probe(|_| { let (_, proof_tree) = self.evaluate_root_goal(goal, GenerateProofTree::Yes); let proof_tree = proof_tree.unwrap(); 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/normalizes_to/mod.rs b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs index 3aba5c85abc..248985715c2 100644 --- a/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/normalizes_to/mod.rs @@ -162,15 +162,28 @@ impl<'tcx> assembly::GoalKind<'tcx> for NormalizesTo<'tcx> { let tcx = ecx.tcx(); let goal_trait_ref = goal.predicate.alias.trait_ref(tcx); - let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let impl_trait_header = tcx.impl_trait_header(impl_def_id).unwrap(); let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; - if !drcx.args_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) { + if !drcx.args_may_unify( + goal.predicate.trait_ref(tcx).args, + impl_trait_header.skip_binder().trait_ref.args, + ) { return Err(NoSolution); } + // We have to ignore negative impls when projecting. + let impl_polarity = impl_trait_header.skip_binder().polarity; + match impl_polarity { + ty::ImplPolarity::Negative => return Err(NoSolution), + ty::ImplPolarity::Reservation => { + unimplemented!("reservation impl for trait with assoc item: {:?}", goal) + } + ty::ImplPolarity::Positive => {} + }; + ecx.probe_trait_candidate(CandidateSource::Impl(impl_def_id)).enter(|ecx| { let impl_args = ecx.fresh_args_for_item(impl_def_id); - let impl_trait_ref = impl_trait_ref.instantiate(tcx, impl_args); + let impl_trait_ref = impl_trait_header.instantiate(tcx, impl_args).trait_ref; ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; 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) }); diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index eba6ba3f7b0..80198ba39f9 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -549,14 +549,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let args = ecx.tcx().erase_regions(goal.predicate.trait_ref.args); let Some(assume) = - rustc_transmute::Assume::from_const(ecx.tcx(), goal.param_env, args.const_at(3)) + rustc_transmute::Assume::from_const(ecx.tcx(), goal.param_env, args.const_at(2)) else { return Err(NoSolution); }; let certainty = ecx.is_transmutable( rustc_transmute::Types { dst: args.type_at(0), src: args.type_at(1) }, - args.type_at(2), assume, )?; ecx.evaluate_added_goals_and_make_canonical_response(certainty) |