From b65d735f1c4dbb0677884c97ff1b09d0c38d2cc5 Mon Sep 17 00:00:00 2001 From: Michael Goulet Date: Fri, 14 Jun 2024 13:59:45 -0400 Subject: Move InferCtxtSelectExt out of eval_ctxt module --- .../src/solve/eval_ctxt/mod.rs | 2 - .../src/solve/eval_ctxt/select.rs | 184 --------------------- compiler/rustc_trait_selection/src/solve/mod.rs | 4 +- compiler/rustc_trait_selection/src/solve/select.rs | 184 +++++++++++++++++++++ 4 files changed, 187 insertions(+), 187 deletions(-) delete mode 100644 compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs create mode 100644 compiler/rustc_trait_selection/src/solve/select.rs 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 6b8375b53e8..8dc6b31f8d1 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs @@ -29,11 +29,9 @@ use super::inspect::ProofTreeBuilder; use super::{search_graph, GoalEvaluationKind, FIXPOINT_STEP_LIMIT}; use super::{search_graph::SearchGraph, Goal}; use super::{GoalSource, SolverMode}; -pub use select::InferCtxtSelectExt; pub(super) mod canonical; mod probe; -mod select; pub struct EvalCtxt<'a, Infcx, I = ::Interner> where diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs deleted file mode 100644 index 257fd263b94..00000000000 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs +++ /dev/null @@ -1,184 +0,0 @@ -use std::ops::ControlFlow; - -use rustc_infer::infer::InferCtxt; -use rustc_infer::traits::solve::inspect::ProbeKind; -use rustc_infer::traits::solve::{CandidateSource, Certainty, Goal}; -use rustc_infer::traits::{ - BuiltinImplSource, ImplSource, ImplSourceUserDefinedData, Obligation, ObligationCause, - PolyTraitObligation, Selection, SelectionError, SelectionResult, -}; -use rustc_macros::extension; -use rustc_middle::{bug, span_bug}; -use rustc_span::Span; - -use crate::solve::inspect::{self, ProofTreeInferCtxtExt}; - -#[extension(pub trait InferCtxtSelectExt<'tcx>)] -impl<'tcx> InferCtxt<'tcx> { - fn select_in_new_trait_solver( - &self, - obligation: &PolyTraitObligation<'tcx>, - ) -> SelectionResult<'tcx, Selection<'tcx>> { - assert!(self.next_trait_solver()); - - self.visit_proof_tree( - Goal::new(self.tcx, obligation.param_env, obligation.predicate), - &mut Select { span: obligation.cause.span }, - ) - .break_value() - .unwrap() - } -} - -struct Select { - span: Span, -} - -impl<'tcx> inspect::ProofTreeVisitor<'tcx> for Select { - type Result = ControlFlow>>; - - fn span(&self) -> Span { - self.span - } - - fn visit_goal(&mut self, goal: &inspect::InspectGoal<'_, 'tcx>) -> Self::Result { - let mut candidates = goal.candidates(); - candidates.retain(|cand| cand.result().is_ok()); - - // No candidates -- not implemented. - if candidates.is_empty() { - return ControlFlow::Break(Err(SelectionError::Unimplemented)); - } - - // One candidate, no need to winnow. - if candidates.len() == 1 { - return ControlFlow::Break(Ok(to_selection( - self.span, - candidates.into_iter().next().unwrap(), - ))); - } - - // Don't winnow until `Certainty::Yes` -- we don't need to winnow until - // codegen, and only on the good path. - if matches!(goal.result().unwrap(), Certainty::Maybe(..)) { - return ControlFlow::Break(Ok(None)); - } - - // We need to winnow. See comments on `candidate_should_be_dropped_in_favor_of`. - let mut i = 0; - while i < candidates.len() { - let should_drop_i = (0..candidates.len()) - .filter(|&j| i != j) - .any(|j| candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j])); - if should_drop_i { - candidates.swap_remove(i); - } else { - i += 1; - if i > 1 { - return ControlFlow::Break(Ok(None)); - } - } - } - - ControlFlow::Break(Ok(to_selection(self.span, candidates.into_iter().next().unwrap()))) - } -} - -/// This is a lot more limited than the old solver's equivalent method. This may lead to more `Ok(None)` -/// results when selecting traits in polymorphic contexts, but we should never rely on the lack of ambiguity, -/// and should always just gracefully fail here. We shouldn't rely on this incompleteness. -fn candidate_should_be_dropped_in_favor_of<'tcx>( - victim: &inspect::InspectCandidate<'_, 'tcx>, - other: &inspect::InspectCandidate<'_, 'tcx>, -) -> bool { - // Don't winnow until `Certainty::Yes` -- we don't need to winnow until - // codegen, and only on the good path. - if matches!(other.result().unwrap(), Certainty::Maybe(..)) { - return false; - } - - let inspect::ProbeKind::TraitCandidate { source: victim_source, result: _ } = victim.kind() - else { - return false; - }; - let inspect::ProbeKind::TraitCandidate { source: other_source, result: _ } = other.kind() - else { - return false; - }; - - match (victim_source, other_source) { - (_, CandidateSource::CoherenceUnknowable) | (CandidateSource::CoherenceUnknowable, _) => { - bug!("should not have assembled a CoherenceUnknowable candidate") - } - - // In the old trait solver, we arbitrarily choose lower vtable candidates - // over higher ones. - ( - CandidateSource::BuiltinImpl(BuiltinImplSource::Object(a)), - CandidateSource::BuiltinImpl(BuiltinImplSource::Object(b)), - ) => a >= b, - // Prefer dyn candidates over non-dyn candidates. This is necessary to - // handle the unsoundness between `impl Any for T` and `dyn Any: Any`. - ( - CandidateSource::Impl(_) | CandidateSource::ParamEnv(_) | CandidateSource::AliasBound, - CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }), - ) => true, - - // Prefer specializing candidates over specialized candidates. - (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => { - victim.goal().infcx().tcx.specializes((other_def_id, victim_def_id)) - } - - _ => false, - } -} - -fn to_selection<'tcx>( - span: Span, - cand: inspect::InspectCandidate<'_, 'tcx>, -) -> Option> { - if let Certainty::Maybe(..) = cand.shallow_certainty() { - return None; - } - - let (nested, impl_args) = cand.instantiate_nested_goals_and_opt_impl_args(span); - let nested = nested - .into_iter() - .map(|nested| { - Obligation::new( - nested.infcx().tcx, - ObligationCause::dummy_with_span(span), - nested.goal().param_env, - nested.goal().predicate, - ) - }) - .collect(); - - Some(match cand.kind() { - ProbeKind::TraitCandidate { source, result: _ } => match source { - CandidateSource::Impl(impl_def_id) => { - // FIXME: Remove this in favor of storing this in the tree - // For impl candidates, we do the rematch manually to compute the args. - ImplSource::UserDefined(ImplSourceUserDefinedData { - impl_def_id, - args: impl_args.expect("expected recorded impl args for impl candidate"), - nested, - }) - } - CandidateSource::BuiltinImpl(builtin) => ImplSource::Builtin(builtin, nested), - CandidateSource::ParamEnv(_) | CandidateSource::AliasBound => ImplSource::Param(nested), - CandidateSource::CoherenceUnknowable => { - span_bug!(span, "didn't expect to select an unknowable candidate") - } - }, - ProbeKind::TryNormalizeNonRigid { result: _ } - | ProbeKind::NormalizedSelfTyAssembly - | ProbeKind::UnsizeAssembly - | ProbeKind::UpcastProjectionCompatibility - | ProbeKind::OpaqueTypeStorageLookup { result: _ } - | ProbeKind::Root { result: _ } - | ProbeKind::ShadowedEnvProbing => { - span_bug!(span, "didn't expect to assemble trait candidate from {:#?}", cand.kind()) - } - }) -} diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index fdcf4ff11e4..4f1be5cbc85 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -37,12 +37,14 @@ mod normalize; mod normalizes_to; mod project_goals; mod search_graph; +mod select; mod trait_goals; -pub use eval_ctxt::{EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt}; +pub use eval_ctxt::{EvalCtxt, GenerateProofTree, InferCtxtEvalExt}; pub use fulfill::{FulfillmentCtxt, NextSolverError}; pub(crate) use normalize::deeply_normalize_for_diagnostics; pub use normalize::{deeply_normalize, deeply_normalize_with_skipped_universes}; +pub use select::InferCtxtSelectExt; /// How many fixpoint iterations we should attempt inside of the solver before bailing /// with overflow. diff --git a/compiler/rustc_trait_selection/src/solve/select.rs b/compiler/rustc_trait_selection/src/solve/select.rs new file mode 100644 index 00000000000..257fd263b94 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/select.rs @@ -0,0 +1,184 @@ +use std::ops::ControlFlow; + +use rustc_infer::infer::InferCtxt; +use rustc_infer::traits::solve::inspect::ProbeKind; +use rustc_infer::traits::solve::{CandidateSource, Certainty, Goal}; +use rustc_infer::traits::{ + BuiltinImplSource, ImplSource, ImplSourceUserDefinedData, Obligation, ObligationCause, + PolyTraitObligation, Selection, SelectionError, SelectionResult, +}; +use rustc_macros::extension; +use rustc_middle::{bug, span_bug}; +use rustc_span::Span; + +use crate::solve::inspect::{self, ProofTreeInferCtxtExt}; + +#[extension(pub trait InferCtxtSelectExt<'tcx>)] +impl<'tcx> InferCtxt<'tcx> { + fn select_in_new_trait_solver( + &self, + obligation: &PolyTraitObligation<'tcx>, + ) -> SelectionResult<'tcx, Selection<'tcx>> { + assert!(self.next_trait_solver()); + + self.visit_proof_tree( + Goal::new(self.tcx, obligation.param_env, obligation.predicate), + &mut Select { span: obligation.cause.span }, + ) + .break_value() + .unwrap() + } +} + +struct Select { + span: Span, +} + +impl<'tcx> inspect::ProofTreeVisitor<'tcx> for Select { + type Result = ControlFlow>>; + + fn span(&self) -> Span { + self.span + } + + fn visit_goal(&mut self, goal: &inspect::InspectGoal<'_, 'tcx>) -> Self::Result { + let mut candidates = goal.candidates(); + candidates.retain(|cand| cand.result().is_ok()); + + // No candidates -- not implemented. + if candidates.is_empty() { + return ControlFlow::Break(Err(SelectionError::Unimplemented)); + } + + // One candidate, no need to winnow. + if candidates.len() == 1 { + return ControlFlow::Break(Ok(to_selection( + self.span, + candidates.into_iter().next().unwrap(), + ))); + } + + // Don't winnow until `Certainty::Yes` -- we don't need to winnow until + // codegen, and only on the good path. + if matches!(goal.result().unwrap(), Certainty::Maybe(..)) { + return ControlFlow::Break(Ok(None)); + } + + // We need to winnow. See comments on `candidate_should_be_dropped_in_favor_of`. + let mut i = 0; + while i < candidates.len() { + let should_drop_i = (0..candidates.len()) + .filter(|&j| i != j) + .any(|j| candidate_should_be_dropped_in_favor_of(&candidates[i], &candidates[j])); + if should_drop_i { + candidates.swap_remove(i); + } else { + i += 1; + if i > 1 { + return ControlFlow::Break(Ok(None)); + } + } + } + + ControlFlow::Break(Ok(to_selection(self.span, candidates.into_iter().next().unwrap()))) + } +} + +/// This is a lot more limited than the old solver's equivalent method. This may lead to more `Ok(None)` +/// results when selecting traits in polymorphic contexts, but we should never rely on the lack of ambiguity, +/// and should always just gracefully fail here. We shouldn't rely on this incompleteness. +fn candidate_should_be_dropped_in_favor_of<'tcx>( + victim: &inspect::InspectCandidate<'_, 'tcx>, + other: &inspect::InspectCandidate<'_, 'tcx>, +) -> bool { + // Don't winnow until `Certainty::Yes` -- we don't need to winnow until + // codegen, and only on the good path. + if matches!(other.result().unwrap(), Certainty::Maybe(..)) { + return false; + } + + let inspect::ProbeKind::TraitCandidate { source: victim_source, result: _ } = victim.kind() + else { + return false; + }; + let inspect::ProbeKind::TraitCandidate { source: other_source, result: _ } = other.kind() + else { + return false; + }; + + match (victim_source, other_source) { + (_, CandidateSource::CoherenceUnknowable) | (CandidateSource::CoherenceUnknowable, _) => { + bug!("should not have assembled a CoherenceUnknowable candidate") + } + + // In the old trait solver, we arbitrarily choose lower vtable candidates + // over higher ones. + ( + CandidateSource::BuiltinImpl(BuiltinImplSource::Object(a)), + CandidateSource::BuiltinImpl(BuiltinImplSource::Object(b)), + ) => a >= b, + // Prefer dyn candidates over non-dyn candidates. This is necessary to + // handle the unsoundness between `impl Any for T` and `dyn Any: Any`. + ( + CandidateSource::Impl(_) | CandidateSource::ParamEnv(_) | CandidateSource::AliasBound, + CandidateSource::BuiltinImpl(BuiltinImplSource::Object { .. }), + ) => true, + + // Prefer specializing candidates over specialized candidates. + (CandidateSource::Impl(victim_def_id), CandidateSource::Impl(other_def_id)) => { + victim.goal().infcx().tcx.specializes((other_def_id, victim_def_id)) + } + + _ => false, + } +} + +fn to_selection<'tcx>( + span: Span, + cand: inspect::InspectCandidate<'_, 'tcx>, +) -> Option> { + if let Certainty::Maybe(..) = cand.shallow_certainty() { + return None; + } + + let (nested, impl_args) = cand.instantiate_nested_goals_and_opt_impl_args(span); + let nested = nested + .into_iter() + .map(|nested| { + Obligation::new( + nested.infcx().tcx, + ObligationCause::dummy_with_span(span), + nested.goal().param_env, + nested.goal().predicate, + ) + }) + .collect(); + + Some(match cand.kind() { + ProbeKind::TraitCandidate { source, result: _ } => match source { + CandidateSource::Impl(impl_def_id) => { + // FIXME: Remove this in favor of storing this in the tree + // For impl candidates, we do the rematch manually to compute the args. + ImplSource::UserDefined(ImplSourceUserDefinedData { + impl_def_id, + args: impl_args.expect("expected recorded impl args for impl candidate"), + nested, + }) + } + CandidateSource::BuiltinImpl(builtin) => ImplSource::Builtin(builtin, nested), + CandidateSource::ParamEnv(_) | CandidateSource::AliasBound => ImplSource::Param(nested), + CandidateSource::CoherenceUnknowable => { + span_bug!(span, "didn't expect to select an unknowable candidate") + } + }, + ProbeKind::TryNormalizeNonRigid { result: _ } + | ProbeKind::NormalizedSelfTyAssembly + | ProbeKind::UnsizeAssembly + | ProbeKind::UpcastProjectionCompatibility + | ProbeKind::OpaqueTypeStorageLookup { result: _ } + | ProbeKind::Root { result: _ } + | ProbeKind::ShadowedEnvProbing => { + span_bug!(span, "didn't expect to assemble trait candidate from {:#?}", cand.kind()) + } + }) +} -- cgit 1.4.1-3-g733a5