diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs | 214 |
1 files changed, 115 insertions, 99 deletions
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 70235b710..76c50a111 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs @@ -4,7 +4,7 @@ use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; use rustc_infer::infer::{ - DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt, + BoundRegionConversionTime, DefineOpaqueTypes, InferCtxt, InferOk, TyCtxtInferExt, }; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::ObligationCause; @@ -23,17 +23,19 @@ use rustc_middle::ty::{ use rustc_session::config::DumpSolverProofTree; use rustc_span::DUMMY_SP; use std::io::Write; +use std::iter; use std::ops::ControlFlow; use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; use super::inspect::ProofTreeBuilder; -use super::SolverMode; use super::{search_graph, GoalEvaluationKind}; use super::{search_graph::SearchGraph, Goal}; +use super::{GoalSource, SolverMode}; pub use select::InferCtxtSelectExt; mod canonical; +mod commit_if_ok; mod probe; mod select; @@ -102,12 +104,12 @@ pub(super) struct NestedGoals<'tcx> { /// with a fresh inference variable when we evaluate this goal. That can result /// in a trait solver cycle. This would currently result in overflow but can be /// can be unsound with more powerful coinduction in the future. - pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::ProjectionPredicate<'tcx>>>, + pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::NormalizesTo<'tcx>>>, /// The rest of the goals which have not yet processed or remain ambiguous. - pub(super) goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, + pub(super) goals: Vec<(GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)>, } -impl NestedGoals<'_> { +impl<'tcx> NestedGoals<'tcx> { pub(super) fn new() -> Self { Self { normalizes_to_hack_goal: None, goals: Vec::new() } } @@ -115,6 +117,11 @@ impl NestedGoals<'_> { pub(super) fn is_empty(&self) -> bool { self.normalizes_to_hack_goal.is_none() && self.goals.is_empty() } + + pub(super) fn extend(&mut self, other: NestedGoals<'tcx>) { + assert_eq!(other.normalizes_to_hack_goal, None); + self.goals.extend(other.goals) + } } #[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] @@ -140,7 +147,7 @@ pub trait InferCtxtEvalExt<'tcx> { } impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { - #[instrument(level = "debug", skip(self), ret)] + #[instrument(level = "debug", skip(self))] fn evaluate_root_goal( &self, goal: Goal<'tcx, ty::Predicate<'tcx>>, @@ -150,7 +157,7 @@ impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { Option<inspect::GoalEvaluation<'tcx>>, ) { EvalCtxt::enter_root(self, generate_proof_tree, |ecx| { - ecx.evaluate_goal(GoalEvaluationKind::Root, goal) + ecx.evaluate_goal(GoalEvaluationKind::Root, GoalSource::Misc, goal) }) } } @@ -194,9 +201,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let result = f(&mut ecx); let tree = ecx.inspect.finalize(); - if let (Some(tree), DumpSolverProofTree::Always) = - (&tree, infcx.tcx.sess.opts.unstable_opts.dump_solver_proof_tree) - { + if let (Some(tree), DumpSolverProofTree::Always) = ( + &tree, + infcx.tcx.sess.opts.unstable_opts.next_solver.map(|c| c.dump_tree).unwrap_or_default(), + ) { let mut lock = std::io::stdout().lock(); let _ = lock.write_fmt(format_args!("{tree:?}\n")); let _ = lock.flush(); @@ -327,12 +335,12 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { fn evaluate_goal( &mut self, goal_evaluation_kind: GoalEvaluationKind, + source: GoalSource, goal: Goal<'tcx, ty::Predicate<'tcx>>, ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { 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 encountered_overflow = self.search_graph.encountered_overflow(); let canonical_response = EvalCtxt::evaluate_canonical_goal( self.tcx(), self.search_graph, @@ -347,13 +355,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { Ok(response) => response, }; - let has_changed = !canonical_response.value.var_values.is_identity_modulo_regions() - || !canonical_response.value.external_constraints.opaque_types.is_empty(); - let (certainty, nested_goals) = match self.instantiate_and_apply_query_response( - goal.param_env, - orig_values, - canonical_response, - ) { + let (certainty, has_changed, nested_goals) = match self + .instantiate_response_discarding_overflow( + goal.param_env, + source, + orig_values, + canonical_response, + ) { Err(e) => { self.inspect.goal_evaluation(goal_evaluation); return Err(e); @@ -367,72 +375,54 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { bug!("an unchanged goal shouldn't have any side-effects on instantiation"); } - // Check that rerunning this query with its inference constraints applied - // doesn't result in new inference constraints and has the same result. + // FIXME: We previously had an assert here that checked that recomputing + // a goal after applying its constraints did not change its response. // - // If we have projection goals like `<T as Trait>::Assoc == u32` we recursively - // call `exists<U> <T as Trait>::Assoc == U` to enable better caching. This goal - // could constrain `U` to `u32` which would cause this check to result in a - // solver cycle. - if cfg!(debug_assertions) - && has_changed - && !matches!( - goal_evaluation_kind, - GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes } - ) - && !self.search_graph.in_cycle() - { - // The nested evaluation has to happen with the original state - // of `encountered_overflow`. - let from_original_evaluation = - self.search_graph.reset_encountered_overflow(encountered_overflow); - self.check_evaluate_goal_stable_result(goal, canonical_goal, canonical_response); - // In case the evaluation was unstable, we manually make sure that this - // debug check does not influence the result of the parent goal. - self.search_graph.reset_encountered_overflow(from_original_evaluation); - } + // This assert was removed as it did not hold for goals constraining + // an inference variable to a recursive alias, e.g. in + // tests/ui/traits/next-solver/overflow/recursive-self-normalization.rs. + // + // Once we have decided on how to handle trait-system-refactor-initiative#75, + // we should re-add an assert here. Ok((has_changed, certainty, nested_goals)) } - fn check_evaluate_goal_stable_result( + fn instantiate_response_discarding_overflow( &mut self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - original_input: CanonicalInput<'tcx>, - original_result: CanonicalResponse<'tcx>, - ) { - let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); - let result = EvalCtxt::evaluate_canonical_goal( - self.tcx(), - self.search_graph, - canonical_goal, - // FIXME(-Ztrait-solver=next): we do not track what happens in `evaluate_canonical_goal` - &mut ProofTreeBuilder::new_noop(), - ); + param_env: ty::ParamEnv<'tcx>, + source: GoalSource, + original_values: Vec<ty::GenericArg<'tcx>>, + response: CanonicalResponse<'tcx>, + ) -> Result<(Certainty, bool, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { + // The old solver did not evaluate nested goals when normalizing. + // It returned the selection constraints allowing a `Projection` + // obligation to not hold in coherence while avoiding the fatal error + // from overflow. + // + // We match this behavior here by considering all constraints + // from nested goals which are not from where-bounds. We will already + // need to track which nested goals are required by impl where-bounds + // for coinductive cycles, so we simply reuse that here. + // + // While we could consider overflow constraints in more cases, this should + // not be necessary for backcompat and results in better perf. It also + // avoids a potential inconsistency which would otherwise require some + // tracking for root goals as well. See #119071 for an example. + let keep_overflow_constraints = || { + self.search_graph.current_goal_is_normalizes_to() + && source != GoalSource::ImplWhereBound + }; - macro_rules! fail { - ($msg:expr) => {{ - let msg = $msg; - warn!( - "unstable result: {msg}\n\ - original goal: {original_input:?},\n\ - original result: {original_result:?}\n\ - re-canonicalized goal: {canonical_goal:?}\n\ - second response: {result:?}" - ); - return; - }}; - } + if response.value.certainty == Certainty::OVERFLOW && !keep_overflow_constraints() { + Ok((Certainty::OVERFLOW, false, Vec::new())) + } else { + let has_changed = !response.value.var_values.is_identity_modulo_regions() + || !response.value.external_constraints.opaque_types.is_empty(); - let Ok(new_canonical_response) = result else { fail!("second response was error") }; - // We only check for modulo regions as we convert all regions in - // the input to new existentials, even if they're expected to be - // `'static` or a placeholder region. - if !new_canonical_response.value.var_values.is_identity_modulo_regions() { - fail!("additional constraints from second response") - } - if original_result.value.certainty != new_canonical_response.value.certainty { - fail!("unstable certainty") + let (certainty, nested_goals) = + self.instantiate_and_apply_query_response(param_env, original_values, response)?; + Ok((certainty, has_changed, nested_goals)) } } @@ -462,8 +452,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { ty::PredicateKind::Coerce(predicate) => { self.compute_coerce_goal(Goal { param_env, predicate }) } - ty::PredicateKind::ClosureKind(def_id, args, kind) => self - .compute_closure_kind_goal(Goal { param_env, predicate: (def_id, args, kind) }), ty::PredicateKind::ObjectSafe(trait_def_id) => { self.compute_object_safe_goal(trait_def_id) } @@ -474,7 +462,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { self.compute_const_evaluatable_goal(Goal { param_env, predicate: ct }) } ty::PredicateKind::ConstEquate(_, _) => { - bug!("ConstEquate should not be emitted when `-Ztrait-solver=next` is active") + bug!("ConstEquate should not be emitted when `-Znext-solver` is active") + } + ty::PredicateKind::NormalizesTo(predicate) => { + self.compute_normalizes_to_goal(Goal { param_env, predicate }) } ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self .compute_alias_relate_goal(Goal { @@ -488,7 +479,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { } else { let kind = self.infcx.instantiate_binder_with_placeholders(kind); let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); - self.add_goal(goal); + self.add_goal(GoalSource::Misc, goal); self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } @@ -537,6 +528,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); self.inspect.evaluate_added_goals_loop_start(); + + fn with_misc_source<'tcx>( + it: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>, + ) -> impl Iterator<Item = (GoalSource, Goal<'tcx, ty::Predicate<'tcx>>)> { + iter::zip(iter::repeat(GoalSource::Misc), it) + } + // If this loop did not result in any progress, what's our final certainty. let mut unchanged_certainty = Some(Certainty::Yes); if let Some(goal) = goals.normalizes_to_hack_goal.take() { @@ -545,17 +543,15 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let unconstrained_rhs = self.next_term_infer_of_kind(goal.predicate.term); let unconstrained_goal = goal.with( tcx, - ty::ProjectionPredicate { - projection_ty: goal.predicate.projection_ty, - term: unconstrained_rhs, - }, + ty::NormalizesTo { alias: goal.predicate.alias, term: unconstrained_rhs }, ); let (_, certainty, instantiate_goals) = self.evaluate_goal( GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes }, + GoalSource::Misc, unconstrained_goal, )?; - self.nested_goals.goals.extend(instantiate_goals); + self.nested_goals.goals.extend(with_misc_source(instantiate_goals)); // Finally, equate the goal's RHS with the unconstrained var. // We put the nested goals from this into goals instead of @@ -564,15 +560,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { // matters in practice, though. let eq_goals = self.eq_and_get_goals(goal.param_env, goal.predicate.term, unconstrained_rhs)?; - goals.goals.extend(eq_goals); + goals.goals.extend(with_misc_source(eq_goals)); // We only look at the `projection_ty` part here rather than // looking at the "has changed" return from evaluate_goal, // because we expect the `unconstrained_rhs` part of the predicate // to have changed -- that means we actually normalized successfully! - if goal.predicate.projection_ty - != self.resolve_vars_if_possible(goal.predicate.projection_ty) - { + if goal.predicate.alias != self.resolve_vars_if_possible(goal.predicate.alias) { unchanged_certainty = None; } @@ -587,12 +581,13 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { } } - for goal in goals.goals.drain(..) { + for (source, goal) in goals.goals.drain(..) { let (has_changed, certainty, instantiate_goals) = self.evaluate_goal( GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::No }, + source, goal, )?; - self.nested_goals.goals.extend(instantiate_goals); + self.nested_goals.goals.extend(with_misc_source(instantiate_goals)); if has_changed { unchanged_certainty = None; } @@ -600,7 +595,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { match certainty { Certainty::Yes => {} Certainty::Maybe(_) => { - self.nested_goals.goals.push(goal); + self.nested_goals.goals.push((source, goal)); unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); } } @@ -642,9 +637,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { /// /// This is the case if the `term` is an inference variable in the innermost universe /// and does not occur in any other part of the predicate. + #[instrument(level = "debug", skip(self), ret)] pub(super) fn term_is_fully_unconstrained( &self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + goal: Goal<'tcx, ty::NormalizesTo<'tcx>>, ) -> bool { let term_is_infer = match goal.predicate.term.unpack() { ty::TermKind::Ty(ty) => { @@ -708,7 +704,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let mut visitor = ContainsTerm { infcx: self.infcx, term: goal.predicate.term }; term_is_infer - && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue() + && goal.predicate.alias.visit_with(&mut visitor).is_continue() && goal.param_env.visit_with(&mut visitor).is_continue() } @@ -723,7 +719,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { .at(&ObligationCause::dummy(), param_env) .eq(DefineOpaqueTypes::No, lhs, rhs) .map(|InferOk { value: (), obligations }| { - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); }) .map_err(|e| { debug!(?e, "failed to equate"); @@ -742,7 +738,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { .at(&ObligationCause::dummy(), param_env) .sub(DefineOpaqueTypes::No, sub, sup) .map(|InferOk { value: (), obligations }| { - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); }) .map_err(|e| { debug!(?e, "failed to subtype"); @@ -750,6 +746,26 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }) } + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn relate<T: ToTrace<'tcx>>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + variance: ty::Variance, + rhs: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .relate(DefineOpaqueTypes::No, lhs, variance, rhs) + .map(|InferOk { value: (), obligations }| { + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to relate"); + NoSolution + }) + } + /// Equates two values returning the nested goals without adding them /// to the nested goals of the `EvalCtxt`. /// @@ -780,7 +796,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> T { self.infcx.instantiate_binder_with_fresh_vars( DUMMY_SP, - LateBoundRegionConversionTime::HigherRankedType, + BoundRegionConversionTime::HigherRankedType, value, ) } @@ -875,7 +891,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { true, &mut obligations, )?; - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); Ok(()) } @@ -895,7 +911,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { hidden_ty, &mut obligations, ); - self.add_goals(obligations.into_iter().map(|o| o.into())); + self.add_goals(GoalSource::Misc, obligations.into_iter().map(|o| o.into())); } // Do something for each opaque/hidden pair defined with `def_id` in the |