From c70ef36f2cd7e505022a534a9a9bb9f472cf3610 Mon Sep 17 00:00:00 2001 From: lcnr Date: Tue, 10 Oct 2023 09:55:22 +0000 Subject: reorder files in solve --- .../rustc_trait_selection/src/solve/eval_ctxt.rs | 1001 -------------------- .../src/solve/eval_ctxt/mod.rs | 1001 ++++++++++++++++++++ .../src/solve/inherent_projection.rs | 50 - compiler/rustc_trait_selection/src/solve/mod.rs | 3 - .../rustc_trait_selection/src/solve/opaques.rs | 85 -- .../src/solve/project_goals.rs | 636 ------------- .../src/solve/project_goals/inherent_projection.rs | 50 + .../src/solve/project_goals/mod.rs | 640 +++++++++++++ .../src/solve/project_goals/opaques.rs | 85 ++ .../src/solve/project_goals/weak_types.rs | 34 + .../src/solve/search_graph.rs | 368 +++++++ .../src/solve/search_graph/mod.rs | 368 ------- .../rustc_trait_selection/src/solve/weak_types.rs | 34 - 13 files changed, 2178 insertions(+), 2177 deletions(-) delete mode 100644 compiler/rustc_trait_selection/src/solve/eval_ctxt.rs create mode 100644 compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs delete mode 100644 compiler/rustc_trait_selection/src/solve/inherent_projection.rs delete mode 100644 compiler/rustc_trait_selection/src/solve/opaques.rs delete mode 100644 compiler/rustc_trait_selection/src/solve/project_goals.rs create mode 100644 compiler/rustc_trait_selection/src/solve/project_goals/inherent_projection.rs create mode 100644 compiler/rustc_trait_selection/src/solve/project_goals/mod.rs create mode 100644 compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs create mode 100644 compiler/rustc_trait_selection/src/solve/project_goals/weak_types.rs create mode 100644 compiler/rustc_trait_selection/src/solve/search_graph.rs delete mode 100644 compiler/rustc_trait_selection/src/solve/search_graph/mod.rs delete mode 100644 compiler/rustc_trait_selection/src/solve/weak_types.rs (limited to 'compiler/rustc_trait_selection/src/solve') diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs deleted file mode 100644 index 066129d8e47..00000000000 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ /dev/null @@ -1,1001 +0,0 @@ -use rustc_data_structures::stack::ensure_sufficient_stack; -use rustc_hir::def_id::{DefId, LocalDefId}; -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, -}; -use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::ObligationCause; -use rustc_middle::infer::canonical::CanonicalVarInfos; -use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; -use rustc_middle::traits::solve::inspect; -use rustc_middle::traits::solve::{ - CanonicalInput, CanonicalResponse, Certainty, IsNormalizesToHack, PredefinedOpaques, - PredefinedOpaquesData, QueryResult, -}; -use rustc_middle::traits::{specialization_graph, DefiningAnchor}; -use rustc_middle::ty::{ - self, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, - TypeVisitableExt, TypeVisitor, -}; -use rustc_session::config::DumpSolverProofTree; -use rustc_span::DUMMY_SP; -use std::io::Write; -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}; -pub use select::InferCtxtSelectExt; - -mod canonical; -mod probe; -mod select; - -pub struct EvalCtxt<'a, 'tcx> { - /// The inference context that backs (mostly) inference and placeholder terms - /// instantiated while solving goals. - /// - /// NOTE: The `InferCtxt` that backs the `EvalCtxt` is intentionally private, - /// because the `InferCtxt` is much more general than `EvalCtxt`. Methods such - /// as `take_registered_region_obligations` can mess up query responses, - /// using `At::normalize` is totally wrong, calling `evaluate_root_goal` can - /// cause coinductive unsoundness, etc. - /// - /// Methods that are generally of use for trait solving are *intentionally* - /// re-declared through the `EvalCtxt` below, often with cleaner signatures - /// since we don't care about things like `ObligationCause`s and `Span`s here. - /// If some `InferCtxt` method is missing, please first think defensively about - /// the method's compatibility with this solver, or if an existing one does - /// the job already. - infcx: &'a InferCtxt<'tcx>, - - /// The variable info for the `var_values`, only used to make an ambiguous response - /// with no constraints. - variables: CanonicalVarInfos<'tcx>, - pub(super) var_values: CanonicalVarValues<'tcx>, - - predefined_opaques_in_body: PredefinedOpaques<'tcx>, - - /// The highest universe index nameable by the caller. - /// - /// When we enter a new binder inside of the query we create new universes - /// which the caller cannot name. We have to be careful with variables from - /// these new universes when creating the query response. - /// - /// Both because these new universes can prevent us from reaching a fixpoint - /// if we have a coinductive cycle and because that's the only way we can return - /// new placeholders to the caller. - pub(super) max_input_universe: ty::UniverseIndex, - - pub(super) search_graph: &'a mut SearchGraph<'tcx>, - - pub(super) nested_goals: NestedGoals<'tcx>, - - // Has this `EvalCtxt` errored out with `NoSolution` in `try_evaluate_added_goals`? - // - // If so, then it can no longer be used to make a canonical query response, - // since subsequent calls to `try_evaluate_added_goals` have possibly dropped - // ambiguous goals. Instead, a probe needs to be introduced somewhere in the - // evaluation code. - tainted: Result<(), NoSolution>, - - pub(super) inspect: ProofTreeBuilder<'tcx>, -} - -#[derive(Debug, Clone)] -pub(super) struct NestedGoals<'tcx> { - /// This normalizes-to goal that is treated specially during the evaluation - /// loop. In each iteration we take the RHS of the projection, replace it with - /// a fresh inference variable, and only after evaluating that goal do we - /// equate the fresh inference variable with the actual RHS of the predicate. - /// - /// This is both to improve caching, and to avoid using the RHS of the - /// projection predicate to influence the normalizes-to candidate we select. - /// - /// This is not a 'real' nested goal. We must not forget to replace the RHS - /// 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>>, - /// The rest of the goals which have not yet processed or remain ambiguous. - pub(super) goals: Vec>>, -} - -impl NestedGoals<'_> { - pub(super) fn new() -> Self { - Self { normalizes_to_hack_goal: None, goals: Vec::new() } - } - - pub(super) fn is_empty(&self) -> bool { - self.normalizes_to_hack_goal.is_none() && self.goals.is_empty() - } -} - -#[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] -pub enum GenerateProofTree { - Yes(UseGlobalCache), - IfEnabled, - Never, -} - -#[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] -pub enum UseGlobalCache { - Yes, - No, -} -impl UseGlobalCache { - pub fn from_bool(use_cache: bool) -> Self { - match use_cache { - true => UseGlobalCache::Yes, - false => UseGlobalCache::No, - } - } -} - -pub trait InferCtxtEvalExt<'tcx> { - /// Evaluates a goal from **outside** of the trait solver. - /// - /// Using this while inside of the solver is wrong as it uses a new - /// search graph which would break cycle detection. - fn evaluate_root_goal( - &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - generate_proof_tree: GenerateProofTree, - ) -> ( - Result<(bool, Certainty, Vec>>), NoSolution>, - Option>, - ); -} - -impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { - #[instrument(level = "debug", skip(self), ret)] - fn evaluate_root_goal( - &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - generate_proof_tree: GenerateProofTree, - ) -> ( - Result<(bool, Certainty, Vec>>), NoSolution>, - Option>, - ) { - EvalCtxt::enter_root(self, generate_proof_tree, |ecx| { - ecx.evaluate_goal(GoalEvaluationKind::Root, goal) - }) - } -} - -impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { - pub(super) fn solver_mode(&self) -> SolverMode { - 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`]). - fn enter_root( - infcx: &InferCtxt<'tcx>, - generate_proof_tree: GenerateProofTree, - f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> R, - ) -> (R, Option>) { - let mode = if infcx.intercrate { SolverMode::Coherence } else { SolverMode::Normal }; - let mut search_graph = search_graph::SearchGraph::new(infcx.tcx, mode); - - let mut ecx = EvalCtxt { - search_graph: &mut search_graph, - infcx, - nested_goals: NestedGoals::new(), - inspect: ProofTreeBuilder::new_maybe_root(infcx.tcx, generate_proof_tree), - - // Only relevant when canonicalizing the response, - // which we don't do within this evaluation context. - predefined_opaques_in_body: infcx - .tcx - .mk_predefined_opaques_in_body(PredefinedOpaquesData::default()), - max_input_universe: ty::UniverseIndex::ROOT, - variables: ty::List::empty(), - var_values: CanonicalVarValues::dummy(), - tainted: Ok(()), - }; - 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) - { - let mut lock = std::io::stdout().lock(); - let _ = lock.write_fmt(format_args!("{tree:?}\n")); - let _ = lock.flush(); - } - - assert!( - ecx.nested_goals.is_empty(), - "root `EvalCtxt` should not have any goals added to it" - ); - - assert!(search_graph.is_empty()); - (result, tree) - } - - /// 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. - /// - /// This function takes care of setting up the inference context, setting the anchor, - /// and registering opaques from the canonicalized input. - fn enter_canonical( - tcx: TyCtxt<'tcx>, - search_graph: &'a mut search_graph::SearchGraph<'tcx>, - canonical_input: CanonicalInput<'tcx>, - canonical_goal_evaluation: &mut ProofTreeBuilder<'tcx>, - f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>, Goal<'tcx, ty::Predicate<'tcx>>) -> R, - ) -> R { - let intercrate = match search_graph.solver_mode() { - SolverMode::Normal => false, - SolverMode::Coherence => true, - }; - let (ref infcx, input, var_values) = tcx - .infer_ctxt() - .intercrate(intercrate) - .with_next_trait_solver(true) - .with_opaque_type_inference(canonical_input.value.anchor) - .build_with_canonical(DUMMY_SP, &canonical_input); - - let mut ecx = EvalCtxt { - infcx, - variables: canonical_input.variables, - var_values, - predefined_opaques_in_body: input.predefined_opaques_in_body, - max_input_universe: canonical_input.max_universe, - search_graph, - nested_goals: NestedGoals::new(), - tainted: Ok(()), - inspect: canonical_goal_evaluation.new_goal_evaluation_step(input), - }; - - for &(key, ty) in &input.predefined_opaques_in_body.opaque_types { - ecx.insert_hidden_type(key, input.goal.param_env, ty) - .expect("failed to prepopulate opaque types"); - } - - if !ecx.nested_goals.is_empty() { - panic!("prepopulating opaque types shouldn't add goals: {:?}", ecx.nested_goals); - } - - let result = f(&mut ecx, input.goal); - - canonical_goal_evaluation.goal_evaluation_step(ecx.inspect); - - // When creating a query response we clone the opaque type constraints - // instead of taking them. This would cause an ICE here, since we have - // assertions against dropping an `InferCtxt` without taking opaques. - // FIXME: Once we remove support for the old impl we can remove this. - if input.anchor != DefiningAnchor::Error { - // This seems ok, but fragile. - let _ = infcx.take_opaque_types(); - } - - 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 [InferCtxtEvalExt::evaluate_root_goal] if you're - /// outside of it. - #[instrument(level = "debug", skip(tcx, search_graph, goal_evaluation), ret)] - fn evaluate_canonical_goal( - tcx: TyCtxt<'tcx>, - search_graph: &'a mut search_graph::SearchGraph<'tcx>, - canonical_input: CanonicalInput<'tcx>, - goal_evaluation: &mut ProofTreeBuilder<'tcx>, - ) -> QueryResult<'tcx> { - 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( - tcx, - canonical_input, - &mut canonical_goal_evaluation, - |search_graph, canonical_goal_evaluation| { - EvalCtxt::enter_canonical( - tcx, - 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( - &mut self, - goal_evaluation_kind: GoalEvaluationKind, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty, Vec>>), 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, - canonical_goal, - &mut goal_evaluation, - ); - let canonical_response = match canonical_response { - Err(e) => { - self.inspect.goal_evaluation(goal_evaluation); - return Err(e); - } - 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, - ) { - Err(e) => { - self.inspect.goal_evaluation(goal_evaluation); - return Err(e); - } - Ok(response) => response, - }; - goal_evaluation.returned_goals(&nested_goals); - self.inspect.goal_evaluation(goal_evaluation); - - if !has_changed && !nested_goals.is_empty() { - 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. - // - // If we have projection goals like `::Assoc == u32` we recursively - // call `exists ::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); - } - - Ok((has_changed, certainty, nested_goals)) - } - - fn check_evaluate_goal_stable_result( - &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(), - ); - - 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; - }}; - } - - 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") - } - } - - fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { - let Goal { param_env, predicate } = goal; - let kind = predicate.kind(); - if let Some(kind) = kind.no_bound_vars() { - match kind { - ty::PredicateKind::Clause(ty::ClauseKind::Trait(predicate)) => { - self.compute_trait_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::ClauseKind::Projection(predicate)) => { - self.compute_projection_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(predicate)) => { - self.compute_type_outlives_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(predicate)) => { - self.compute_region_outlives_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => { - self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) - } - ty::PredicateKind::Subtype(predicate) => { - self.compute_subtype_goal(Goal { param_env, predicate }) - } - 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) - } - ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => { - self.compute_well_formed_goal(Goal { param_env, predicate: arg }) - } - ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(ct)) => { - 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") - } - ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self - .compute_alias_relate_goal(Goal { - param_env, - predicate: (lhs, rhs, direction), - }), - ty::PredicateKind::Ambiguous => { - self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) - } - } - } 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.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } - } - - // Recursively evaluates all the goals added to this `EvalCtxt` to completion, returning - // the certainty of all the goals. - #[instrument(level = "debug", skip(self))] - pub(super) fn try_evaluate_added_goals(&mut self) -> Result { - 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() { - // 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() { - Ok(Some(cert)) => { - response = Ok(cert); - break; - } - Ok(None) => {} - Err(NoSolution) => { - response = Err(NoSolution); - break; - } - } - } - - self.inspect.eval_added_goals_result(response); - - if response.is_err() { - self.tainted = Err(NoSolution); - } - - let goal_evaluations = std::mem::replace(&mut self.inspect, inspect); - self.inspect.added_goals_evaluation(goal_evaluations); - - response - } - - /// Iterate over all added goals: returning `Ok(Some(_))` in case we can stop rerunning. - /// - /// Goals for the next step get directly added to the nested goals of the `EvalCtxt`. - fn evaluate_added_goals_step(&mut self) -> Result, NoSolution> { - let tcx = self.tcx(); - let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); - - self.inspect.evaluate_added_goals_loop_start(); - // 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() { - // Replace the goal with an unconstrained infer var, so the - // RHS does not affect projection candidate assembly. - 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, - }, - ); - - let (_, certainty, instantiate_goals) = self.evaluate_goal( - GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes }, - unconstrained_goal, - )?; - self.nested_goals.goals.extend(instantiate_goals); - - // Finally, equate the goal's RHS with the unconstrained var. - // We put the nested goals from this into goals instead of - // next_goals to avoid needing to process the loop one extra - // time if this goal returns something -- I don't think this - // 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); - - // 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) - { - unchanged_certainty = None; - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - // We need to resolve vars here so that we correctly - // deal with `has_changed` in the next iteration. - self.set_normalizes_to_hack_goal(self.resolve_vars_if_possible(goal)); - unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); - } - } - } - - for goal in goals.goals.drain(..) { - let (has_changed, certainty, instantiate_goals) = self.evaluate_goal( - GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::No }, - goal, - )?; - self.nested_goals.goals.extend(instantiate_goals); - if has_changed { - unchanged_certainty = None; - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - self.nested_goals.goals.push(goal); - unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); - } - } - } - - Ok(unchanged_certainty) - } -} - -impl<'tcx> EvalCtxt<'_, 'tcx> { - pub(super) fn tcx(&self) -> TyCtxt<'tcx> { - self.infcx.tcx - } - - pub(super) fn next_ty_infer(&self) -> Ty<'tcx> { - self.infcx.next_ty_var(TypeVariableOrigin { - kind: TypeVariableOriginKind::MiscVariable, - span: DUMMY_SP, - }) - } - - pub(super) fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> { - self.infcx.next_const_var( - ty, - ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span: DUMMY_SP }, - ) - } - - /// Returns a ty infer or a const infer depending on whether `kind` is a `Ty` or `Const`. - /// If `kind` is an integer inference variable this will still return a ty infer var. - pub(super) fn next_term_infer_of_kind(&self, kind: ty::Term<'tcx>) -> ty::Term<'tcx> { - match kind.unpack() { - ty::TermKind::Ty(_) => self.next_ty_infer().into(), - ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), - } - } - - /// Is the projection predicate is of the form `exists ::Assoc = T`. - /// - /// 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. - pub(super) fn term_is_fully_unconstrained( - &self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, - ) -> bool { - let term_is_infer = match goal.predicate.term.unpack() { - ty::TermKind::Ty(ty) => { - if let &ty::Infer(ty::TyVar(vid)) = ty.kind() { - match self.infcx.probe_ty_var(vid) { - Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), - Err(universe) => universe == self.infcx.universe(), - } - } else { - false - } - } - ty::TermKind::Const(ct) => { - if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() { - match self.infcx.probe_const_var(vid) { - Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), - Err(universe) => universe == self.infcx.universe(), - } - } else { - false - } - } - }; - - // Guard against `>::Assoc = ?0>`. - struct ContainsTerm<'a, 'tcx> { - term: ty::Term<'tcx>, - infcx: &'a InferCtxt<'tcx>, - } - impl<'tcx> TypeVisitor> for ContainsTerm<'_, 'tcx> { - type BreakTy = (); - fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow { - if let Some(vid) = t.ty_vid() - && let ty::TermKind::Ty(term) = self.term.unpack() - && let Some(term_vid) = term.ty_vid() - && self.infcx.root_var(vid) == self.infcx.root_var(term_vid) - { - ControlFlow::Break(()) - } else if t.has_non_region_infer() { - t.super_visit_with(self) - } else { - ControlFlow::Continue(()) - } - } - - fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow { - if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = c.kind() - && let ty::TermKind::Const(term) = self.term.unpack() - && let ty::ConstKind::Infer(ty::InferConst::Var(term_vid)) = term.kind() - && self.infcx.root_const_var(vid) == self.infcx.root_const_var(term_vid) - { - ControlFlow::Break(()) - } else if c.has_non_region_infer() { - c.super_visit_with(self) - } else { - ControlFlow::Continue(()) - } - } - } - - 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.param_env.visit_with(&mut visitor).is_continue() - } - - #[instrument(level = "debug", skip(self, param_env), ret)] - pub(super) fn eq>( - &mut self, - param_env: ty::ParamEnv<'tcx>, - lhs: T, - rhs: T, - ) -> Result<(), NoSolution> { - self.infcx - .at(&ObligationCause::dummy(), param_env) - .eq(DefineOpaqueTypes::No, lhs, rhs) - .map(|InferOk { value: (), obligations }| { - self.add_goals(obligations.into_iter().map(|o| o.into())); - }) - .map_err(|e| { - debug!(?e, "failed to equate"); - NoSolution - }) - } - - #[instrument(level = "debug", skip(self, param_env), ret)] - pub(super) fn sub>( - &mut self, - param_env: ty::ParamEnv<'tcx>, - sub: T, - sup: T, - ) -> Result<(), NoSolution> { - self.infcx - .at(&ObligationCause::dummy(), param_env) - .sub(DefineOpaqueTypes::No, sub, sup) - .map(|InferOk { value: (), obligations }| { - self.add_goals(obligations.into_iter().map(|o| o.into())); - }) - .map_err(|e| { - debug!(?e, "failed to subtype"); - NoSolution - }) - } - - /// Equates two values returning the nested goals without adding them - /// to the nested goals of the `EvalCtxt`. - /// - /// If possible, try using `eq` instead which automatically handles nested - /// goals correctly. - #[instrument(level = "trace", skip(self, param_env), ret)] - pub(super) fn eq_and_get_goals>( - &self, - param_env: ty::ParamEnv<'tcx>, - lhs: T, - rhs: T, - ) -> Result>>, NoSolution> { - self.infcx - .at(&ObligationCause::dummy(), param_env) - .eq(DefineOpaqueTypes::No, lhs, rhs) - .map(|InferOk { value: (), obligations }| { - obligations.into_iter().map(|o| o.into()).collect() - }) - .map_err(|e| { - debug!(?e, "failed to equate"); - NoSolution - }) - } - - pub(super) fn instantiate_binder_with_infer> + Copy>( - &self, - value: ty::Binder<'tcx, T>, - ) -> T { - self.infcx.instantiate_binder_with_fresh_vars( - DUMMY_SP, - LateBoundRegionConversionTime::HigherRankedType, - value, - ) - } - - pub(super) fn instantiate_binder_with_placeholders> + Copy>( - &self, - value: ty::Binder<'tcx, T>, - ) -> T { - self.infcx.instantiate_binder_with_placeholders(value) - } - - pub(super) fn resolve_vars_if_possible(&self, value: T) -> T - where - T: TypeFoldable>, - { - self.infcx.resolve_vars_if_possible(value) - } - - pub(super) fn fresh_args_for_item(&self, def_id: DefId) -> ty::GenericArgsRef<'tcx> { - self.infcx.fresh_args_for_item(DUMMY_SP, def_id) - } - - pub(super) fn translate_args( - &self, - param_env: ty::ParamEnv<'tcx>, - source_impl: DefId, - source_args: ty::GenericArgsRef<'tcx>, - target_node: specialization_graph::Node, - ) -> ty::GenericArgsRef<'tcx> { - crate::traits::translate_args(self.infcx, param_env, source_impl, source_args, target_node) - } - - pub(super) fn register_ty_outlives(&self, ty: Ty<'tcx>, lt: ty::Region<'tcx>) { - self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); - } - - pub(super) fn register_region_outlives(&self, a: ty::Region<'tcx>, b: ty::Region<'tcx>) { - // `b : a` ==> `a <= b` - // (inlined from `InferCtxt::region_outlives_predicate`) - self.infcx.sub_regions( - rustc_infer::infer::SubregionOrigin::RelateRegionParamBound(DUMMY_SP), - b, - a, - ); - } - - /// Computes the list of goals required for `arg` to be well-formed - pub(super) fn well_formed_goals( - &self, - param_env: ty::ParamEnv<'tcx>, - arg: ty::GenericArg<'tcx>, - ) -> Option>>> { - crate::traits::wf::unnormalized_obligations(self.infcx, param_env, arg) - .map(|obligations| obligations.into_iter().map(|obligation| obligation.into())) - } - - pub(super) fn is_transmutable( - &self, - src_and_dst: rustc_transmute::Types<'tcx>, - scope: Ty<'tcx>, - assume: rustc_transmute::Assume, - ) -> Result { - use rustc_transmute::Answer; - // FIXME(transmutability): This really should be returning nested goals for `Answer::If*` - match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable( - ObligationCause::dummy(), - src_and_dst, - scope, - assume, - ) { - Answer::Yes => Ok(Certainty::Yes), - Answer::No(_) | Answer::If(_) => Err(NoSolution), - } - } - - pub(super) fn can_define_opaque_ty(&self, def_id: LocalDefId) -> bool { - self.infcx.opaque_type_origin(def_id).is_some() - } - - pub(super) fn insert_hidden_type( - &mut self, - opaque_type_key: OpaqueTypeKey<'tcx>, - param_env: ty::ParamEnv<'tcx>, - hidden_ty: Ty<'tcx>, - ) -> Result<(), NoSolution> { - let mut obligations = Vec::new(); - self.infcx.insert_hidden_type( - opaque_type_key, - &ObligationCause::dummy(), - param_env, - hidden_ty, - true, - &mut obligations, - )?; - self.add_goals(obligations.into_iter().map(|o| o.into())); - Ok(()) - } - - pub(super) fn add_item_bounds_for_hidden_type( - &mut self, - opaque_def_id: DefId, - opaque_args: ty::GenericArgsRef<'tcx>, - param_env: ty::ParamEnv<'tcx>, - hidden_ty: Ty<'tcx>, - ) { - let mut obligations = Vec::new(); - self.infcx.add_item_bounds_for_hidden_type( - opaque_def_id, - opaque_args, - ObligationCause::dummy(), - param_env, - hidden_ty, - &mut obligations, - ); - self.add_goals(obligations.into_iter().map(|o| o.into())); - } - - // Do something for each opaque/hidden pair defined with `def_id` in the - // current inference context. - pub(super) fn unify_existing_opaque_tys( - &mut self, - param_env: ty::ParamEnv<'tcx>, - key: ty::OpaqueTypeKey<'tcx>, - ty: Ty<'tcx>, - ) -> Vec> { - // FIXME: Super inefficient to be cloning this... - let opaques = self.infcx.clone_opaque_types_for_query_response(); - - let mut values = vec![]; - for (candidate_key, candidate_ty) in opaques { - if candidate_key.def_id != key.def_id { - continue; - } - values.extend(self.probe_misc_candidate("opaque type storage").enter(|ecx| { - for (a, b) in std::iter::zip(candidate_key.args, key.args) { - ecx.eq(param_env, a, b)?; - } - ecx.eq(param_env, candidate_ty, ty)?; - ecx.add_item_bounds_for_hidden_type( - candidate_key.def_id.to_def_id(), - candidate_key.args, - param_env, - candidate_ty, - ); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - })); - } - values - } - - // Try to evaluate a const, or return `None` if the const is too generic. - // This doesn't mean the const isn't evaluatable, though, and should be treated - // as an ambiguity rather than no-solution. - pub(super) fn try_const_eval_resolve( - &self, - param_env: ty::ParamEnv<'tcx>, - unevaluated: ty::UnevaluatedConst<'tcx>, - ty: Ty<'tcx>, - ) -> Option> { - use rustc_middle::mir::interpret::ErrorHandled; - match self.infcx.try_const_eval_resolve(param_env, unevaluated, ty, None) { - Ok(ct) => Some(ct), - Err(ErrorHandled::Reported(e, _)) => { - Some(ty::Const::new_error(self.tcx(), e.into(), ty)) - } - Err(ErrorHandled::TooGeneric(_)) => None, - } - } - - /// Walk through the vtable of a principal trait ref, executing a `supertrait_visitor` - /// for every trait ref encountered (including the principal). Passes both the vtable - /// base and the (optional) vptr slot. - pub(super) fn walk_vtable( - &mut self, - principal: ty::PolyTraitRef<'tcx>, - mut supertrait_visitor: impl FnMut(&mut Self, ty::PolyTraitRef<'tcx>, usize, Option), - ) { - let tcx = self.tcx(); - let mut offset = 0; - prepare_vtable_segments::<()>(tcx, principal, |segment| { - match segment { - VtblSegment::MetadataDSA => { - offset += TyCtxt::COMMON_VTABLE_ENTRIES.len(); - } - VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => { - let own_vtable_entries = count_own_vtable_entries(tcx, trait_ref); - - supertrait_visitor( - self, - trait_ref, - offset, - emit_vptr.then(|| offset + own_vtable_entries), - ); - - offset += own_vtable_entries; - if emit_vptr { - offset += 1; - } - } - } - ControlFlow::Continue(()) - }); - } -} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs new file mode 100644 index 00000000000..066129d8e47 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/mod.rs @@ -0,0 +1,1001 @@ +use rustc_data_structures::stack::ensure_sufficient_stack; +use rustc_hir::def_id::{DefId, LocalDefId}; +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, +}; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::ObligationCause; +use rustc_middle::infer::canonical::CanonicalVarInfos; +use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; +use rustc_middle::traits::solve::inspect; +use rustc_middle::traits::solve::{ + CanonicalInput, CanonicalResponse, Certainty, IsNormalizesToHack, PredefinedOpaques, + PredefinedOpaquesData, QueryResult, +}; +use rustc_middle::traits::{specialization_graph, DefiningAnchor}; +use rustc_middle::ty::{ + self, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, + TypeVisitableExt, TypeVisitor, +}; +use rustc_session::config::DumpSolverProofTree; +use rustc_span::DUMMY_SP; +use std::io::Write; +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}; +pub use select::InferCtxtSelectExt; + +mod canonical; +mod probe; +mod select; + +pub struct EvalCtxt<'a, 'tcx> { + /// The inference context that backs (mostly) inference and placeholder terms + /// instantiated while solving goals. + /// + /// NOTE: The `InferCtxt` that backs the `EvalCtxt` is intentionally private, + /// because the `InferCtxt` is much more general than `EvalCtxt`. Methods such + /// as `take_registered_region_obligations` can mess up query responses, + /// using `At::normalize` is totally wrong, calling `evaluate_root_goal` can + /// cause coinductive unsoundness, etc. + /// + /// Methods that are generally of use for trait solving are *intentionally* + /// re-declared through the `EvalCtxt` below, often with cleaner signatures + /// since we don't care about things like `ObligationCause`s and `Span`s here. + /// If some `InferCtxt` method is missing, please first think defensively about + /// the method's compatibility with this solver, or if an existing one does + /// the job already. + infcx: &'a InferCtxt<'tcx>, + + /// The variable info for the `var_values`, only used to make an ambiguous response + /// with no constraints. + variables: CanonicalVarInfos<'tcx>, + pub(super) var_values: CanonicalVarValues<'tcx>, + + predefined_opaques_in_body: PredefinedOpaques<'tcx>, + + /// The highest universe index nameable by the caller. + /// + /// When we enter a new binder inside of the query we create new universes + /// which the caller cannot name. We have to be careful with variables from + /// these new universes when creating the query response. + /// + /// Both because these new universes can prevent us from reaching a fixpoint + /// if we have a coinductive cycle and because that's the only way we can return + /// new placeholders to the caller. + pub(super) max_input_universe: ty::UniverseIndex, + + pub(super) search_graph: &'a mut SearchGraph<'tcx>, + + pub(super) nested_goals: NestedGoals<'tcx>, + + // Has this `EvalCtxt` errored out with `NoSolution` in `try_evaluate_added_goals`? + // + // If so, then it can no longer be used to make a canonical query response, + // since subsequent calls to `try_evaluate_added_goals` have possibly dropped + // ambiguous goals. Instead, a probe needs to be introduced somewhere in the + // evaluation code. + tainted: Result<(), NoSolution>, + + pub(super) inspect: ProofTreeBuilder<'tcx>, +} + +#[derive(Debug, Clone)] +pub(super) struct NestedGoals<'tcx> { + /// This normalizes-to goal that is treated specially during the evaluation + /// loop. In each iteration we take the RHS of the projection, replace it with + /// a fresh inference variable, and only after evaluating that goal do we + /// equate the fresh inference variable with the actual RHS of the predicate. + /// + /// This is both to improve caching, and to avoid using the RHS of the + /// projection predicate to influence the normalizes-to candidate we select. + /// + /// This is not a 'real' nested goal. We must not forget to replace the RHS + /// 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>>, + /// The rest of the goals which have not yet processed or remain ambiguous. + pub(super) goals: Vec>>, +} + +impl NestedGoals<'_> { + pub(super) fn new() -> Self { + Self { normalizes_to_hack_goal: None, goals: Vec::new() } + } + + pub(super) fn is_empty(&self) -> bool { + self.normalizes_to_hack_goal.is_none() && self.goals.is_empty() + } +} + +#[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] +pub enum GenerateProofTree { + Yes(UseGlobalCache), + IfEnabled, + Never, +} + +#[derive(PartialEq, Eq, Debug, Hash, HashStable, Clone, Copy)] +pub enum UseGlobalCache { + Yes, + No, +} +impl UseGlobalCache { + pub fn from_bool(use_cache: bool) -> Self { + match use_cache { + true => UseGlobalCache::Yes, + false => UseGlobalCache::No, + } + } +} + +pub trait InferCtxtEvalExt<'tcx> { + /// Evaluates a goal from **outside** of the trait solver. + /// + /// Using this while inside of the solver is wrong as it uses a new + /// search graph which would break cycle detection. + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + generate_proof_tree: GenerateProofTree, + ) -> ( + Result<(bool, Certainty, Vec>>), NoSolution>, + Option>, + ); +} + +impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { + #[instrument(level = "debug", skip(self), ret)] + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + generate_proof_tree: GenerateProofTree, + ) -> ( + Result<(bool, Certainty, Vec>>), NoSolution>, + Option>, + ) { + EvalCtxt::enter_root(self, generate_proof_tree, |ecx| { + ecx.evaluate_goal(GoalEvaluationKind::Root, goal) + }) + } +} + +impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { + pub(super) fn solver_mode(&self) -> SolverMode { + 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`]). + fn enter_root( + infcx: &InferCtxt<'tcx>, + generate_proof_tree: GenerateProofTree, + f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> R, + ) -> (R, Option>) { + let mode = if infcx.intercrate { SolverMode::Coherence } else { SolverMode::Normal }; + let mut search_graph = search_graph::SearchGraph::new(infcx.tcx, mode); + + let mut ecx = EvalCtxt { + search_graph: &mut search_graph, + infcx, + nested_goals: NestedGoals::new(), + inspect: ProofTreeBuilder::new_maybe_root(infcx.tcx, generate_proof_tree), + + // Only relevant when canonicalizing the response, + // which we don't do within this evaluation context. + predefined_opaques_in_body: infcx + .tcx + .mk_predefined_opaques_in_body(PredefinedOpaquesData::default()), + max_input_universe: ty::UniverseIndex::ROOT, + variables: ty::List::empty(), + var_values: CanonicalVarValues::dummy(), + tainted: Ok(()), + }; + 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) + { + let mut lock = std::io::stdout().lock(); + let _ = lock.write_fmt(format_args!("{tree:?}\n")); + let _ = lock.flush(); + } + + assert!( + ecx.nested_goals.is_empty(), + "root `EvalCtxt` should not have any goals added to it" + ); + + assert!(search_graph.is_empty()); + (result, tree) + } + + /// 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. + /// + /// This function takes care of setting up the inference context, setting the anchor, + /// and registering opaques from the canonicalized input. + fn enter_canonical( + tcx: TyCtxt<'tcx>, + search_graph: &'a mut search_graph::SearchGraph<'tcx>, + canonical_input: CanonicalInput<'tcx>, + canonical_goal_evaluation: &mut ProofTreeBuilder<'tcx>, + f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>, Goal<'tcx, ty::Predicate<'tcx>>) -> R, + ) -> R { + let intercrate = match search_graph.solver_mode() { + SolverMode::Normal => false, + SolverMode::Coherence => true, + }; + let (ref infcx, input, var_values) = tcx + .infer_ctxt() + .intercrate(intercrate) + .with_next_trait_solver(true) + .with_opaque_type_inference(canonical_input.value.anchor) + .build_with_canonical(DUMMY_SP, &canonical_input); + + let mut ecx = EvalCtxt { + infcx, + variables: canonical_input.variables, + var_values, + predefined_opaques_in_body: input.predefined_opaques_in_body, + max_input_universe: canonical_input.max_universe, + search_graph, + nested_goals: NestedGoals::new(), + tainted: Ok(()), + inspect: canonical_goal_evaluation.new_goal_evaluation_step(input), + }; + + for &(key, ty) in &input.predefined_opaques_in_body.opaque_types { + ecx.insert_hidden_type(key, input.goal.param_env, ty) + .expect("failed to prepopulate opaque types"); + } + + if !ecx.nested_goals.is_empty() { + panic!("prepopulating opaque types shouldn't add goals: {:?}", ecx.nested_goals); + } + + let result = f(&mut ecx, input.goal); + + canonical_goal_evaluation.goal_evaluation_step(ecx.inspect); + + // When creating a query response we clone the opaque type constraints + // instead of taking them. This would cause an ICE here, since we have + // assertions against dropping an `InferCtxt` without taking opaques. + // FIXME: Once we remove support for the old impl we can remove this. + if input.anchor != DefiningAnchor::Error { + // This seems ok, but fragile. + let _ = infcx.take_opaque_types(); + } + + 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 [InferCtxtEvalExt::evaluate_root_goal] if you're + /// outside of it. + #[instrument(level = "debug", skip(tcx, search_graph, goal_evaluation), ret)] + fn evaluate_canonical_goal( + tcx: TyCtxt<'tcx>, + search_graph: &'a mut search_graph::SearchGraph<'tcx>, + canonical_input: CanonicalInput<'tcx>, + goal_evaluation: &mut ProofTreeBuilder<'tcx>, + ) -> QueryResult<'tcx> { + 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( + tcx, + canonical_input, + &mut canonical_goal_evaluation, + |search_graph, canonical_goal_evaluation| { + EvalCtxt::enter_canonical( + tcx, + 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( + &mut self, + goal_evaluation_kind: GoalEvaluationKind, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty, Vec>>), 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, + canonical_goal, + &mut goal_evaluation, + ); + let canonical_response = match canonical_response { + Err(e) => { + self.inspect.goal_evaluation(goal_evaluation); + return Err(e); + } + 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, + ) { + Err(e) => { + self.inspect.goal_evaluation(goal_evaluation); + return Err(e); + } + Ok(response) => response, + }; + goal_evaluation.returned_goals(&nested_goals); + self.inspect.goal_evaluation(goal_evaluation); + + if !has_changed && !nested_goals.is_empty() { + 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. + // + // If we have projection goals like `::Assoc == u32` we recursively + // call `exists ::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); + } + + Ok((has_changed, certainty, nested_goals)) + } + + fn check_evaluate_goal_stable_result( + &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(), + ); + + 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; + }}; + } + + 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") + } + } + + fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { + let Goal { param_env, predicate } = goal; + let kind = predicate.kind(); + if let Some(kind) = kind.no_bound_vars() { + match kind { + ty::PredicateKind::Clause(ty::ClauseKind::Trait(predicate)) => { + self.compute_trait_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::ClauseKind::Projection(predicate)) => { + self.compute_projection_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(predicate)) => { + self.compute_type_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(predicate)) => { + self.compute_region_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => { + self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) + } + ty::PredicateKind::Subtype(predicate) => { + self.compute_subtype_goal(Goal { param_env, predicate }) + } + 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) + } + ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => { + self.compute_well_formed_goal(Goal { param_env, predicate: arg }) + } + ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(ct)) => { + 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") + } + ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self + .compute_alias_relate_goal(Goal { + param_env, + predicate: (lhs, rhs, direction), + }), + ty::PredicateKind::Ambiguous => { + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + } + } + } 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.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + } + + // Recursively evaluates all the goals added to this `EvalCtxt` to completion, returning + // the certainty of all the goals. + #[instrument(level = "debug", skip(self))] + pub(super) fn try_evaluate_added_goals(&mut self) -> Result { + 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() { + // 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() { + Ok(Some(cert)) => { + response = Ok(cert); + break; + } + Ok(None) => {} + Err(NoSolution) => { + response = Err(NoSolution); + break; + } + } + } + + self.inspect.eval_added_goals_result(response); + + if response.is_err() { + self.tainted = Err(NoSolution); + } + + let goal_evaluations = std::mem::replace(&mut self.inspect, inspect); + self.inspect.added_goals_evaluation(goal_evaluations); + + response + } + + /// Iterate over all added goals: returning `Ok(Some(_))` in case we can stop rerunning. + /// + /// Goals for the next step get directly added to the nested goals of the `EvalCtxt`. + fn evaluate_added_goals_step(&mut self) -> Result, NoSolution> { + let tcx = self.tcx(); + let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); + + self.inspect.evaluate_added_goals_loop_start(); + // 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() { + // Replace the goal with an unconstrained infer var, so the + // RHS does not affect projection candidate assembly. + 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, + }, + ); + + let (_, certainty, instantiate_goals) = self.evaluate_goal( + GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::Yes }, + unconstrained_goal, + )?; + self.nested_goals.goals.extend(instantiate_goals); + + // Finally, equate the goal's RHS with the unconstrained var. + // We put the nested goals from this into goals instead of + // next_goals to avoid needing to process the loop one extra + // time if this goal returns something -- I don't think this + // 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); + + // 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) + { + unchanged_certainty = None; + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + // We need to resolve vars here so that we correctly + // deal with `has_changed` in the next iteration. + self.set_normalizes_to_hack_goal(self.resolve_vars_if_possible(goal)); + unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + } + } + } + + for goal in goals.goals.drain(..) { + let (has_changed, certainty, instantiate_goals) = self.evaluate_goal( + GoalEvaluationKind::Nested { is_normalizes_to_hack: IsNormalizesToHack::No }, + goal, + )?; + self.nested_goals.goals.extend(instantiate_goals); + if has_changed { + unchanged_certainty = None; + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + self.nested_goals.goals.push(goal); + unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); + } + } + } + + Ok(unchanged_certainty) + } +} + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn tcx(&self) -> TyCtxt<'tcx> { + self.infcx.tcx + } + + pub(super) fn next_ty_infer(&self) -> Ty<'tcx> { + self.infcx.next_ty_var(TypeVariableOrigin { + kind: TypeVariableOriginKind::MiscVariable, + span: DUMMY_SP, + }) + } + + pub(super) fn next_const_infer(&self, ty: Ty<'tcx>) -> ty::Const<'tcx> { + self.infcx.next_const_var( + ty, + ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span: DUMMY_SP }, + ) + } + + /// Returns a ty infer or a const infer depending on whether `kind` is a `Ty` or `Const`. + /// If `kind` is an integer inference variable this will still return a ty infer var. + pub(super) fn next_term_infer_of_kind(&self, kind: ty::Term<'tcx>) -> ty::Term<'tcx> { + match kind.unpack() { + ty::TermKind::Ty(_) => self.next_ty_infer().into(), + ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), + } + } + + /// Is the projection predicate is of the form `exists ::Assoc = T`. + /// + /// 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. + pub(super) fn term_is_fully_unconstrained( + &self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> bool { + let term_is_infer = match goal.predicate.term.unpack() { + ty::TermKind::Ty(ty) => { + if let &ty::Infer(ty::TyVar(vid)) = ty.kind() { + match self.infcx.probe_ty_var(vid) { + Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), + Err(universe) => universe == self.infcx.universe(), + } + } else { + false + } + } + ty::TermKind::Const(ct) => { + if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() { + match self.infcx.probe_const_var(vid) { + Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), + Err(universe) => universe == self.infcx.universe(), + } + } else { + false + } + } + }; + + // Guard against `>::Assoc = ?0>`. + struct ContainsTerm<'a, 'tcx> { + term: ty::Term<'tcx>, + infcx: &'a InferCtxt<'tcx>, + } + impl<'tcx> TypeVisitor> for ContainsTerm<'_, 'tcx> { + type BreakTy = (); + fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow { + if let Some(vid) = t.ty_vid() + && let ty::TermKind::Ty(term) = self.term.unpack() + && let Some(term_vid) = term.ty_vid() + && self.infcx.root_var(vid) == self.infcx.root_var(term_vid) + { + ControlFlow::Break(()) + } else if t.has_non_region_infer() { + t.super_visit_with(self) + } else { + ControlFlow::Continue(()) + } + } + + fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow { + if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = c.kind() + && let ty::TermKind::Const(term) = self.term.unpack() + && let ty::ConstKind::Infer(ty::InferConst::Var(term_vid)) = term.kind() + && self.infcx.root_const_var(vid) == self.infcx.root_const_var(term_vid) + { + ControlFlow::Break(()) + } else if c.has_non_region_infer() { + c.super_visit_with(self) + } else { + ControlFlow::Continue(()) + } + } + } + + 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.param_env.visit_with(&mut visitor).is_continue() + } + + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn eq>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + rhs: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .eq(DefineOpaqueTypes::No, lhs, rhs) + .map(|InferOk { value: (), obligations }| { + self.add_goals(obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to equate"); + NoSolution + }) + } + + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn sub>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + sub: T, + sup: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .sub(DefineOpaqueTypes::No, sub, sup) + .map(|InferOk { value: (), obligations }| { + self.add_goals(obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to subtype"); + NoSolution + }) + } + + /// Equates two values returning the nested goals without adding them + /// to the nested goals of the `EvalCtxt`. + /// + /// If possible, try using `eq` instead which automatically handles nested + /// goals correctly. + #[instrument(level = "trace", skip(self, param_env), ret)] + pub(super) fn eq_and_get_goals>( + &self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + rhs: T, + ) -> Result>>, NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .eq(DefineOpaqueTypes::No, lhs, rhs) + .map(|InferOk { value: (), obligations }| { + obligations.into_iter().map(|o| o.into()).collect() + }) + .map_err(|e| { + debug!(?e, "failed to equate"); + NoSolution + }) + } + + pub(super) fn instantiate_binder_with_infer> + Copy>( + &self, + value: ty::Binder<'tcx, T>, + ) -> T { + self.infcx.instantiate_binder_with_fresh_vars( + DUMMY_SP, + LateBoundRegionConversionTime::HigherRankedType, + value, + ) + } + + pub(super) fn instantiate_binder_with_placeholders> + Copy>( + &self, + value: ty::Binder<'tcx, T>, + ) -> T { + self.infcx.instantiate_binder_with_placeholders(value) + } + + pub(super) fn resolve_vars_if_possible(&self, value: T) -> T + where + T: TypeFoldable>, + { + self.infcx.resolve_vars_if_possible(value) + } + + pub(super) fn fresh_args_for_item(&self, def_id: DefId) -> ty::GenericArgsRef<'tcx> { + self.infcx.fresh_args_for_item(DUMMY_SP, def_id) + } + + pub(super) fn translate_args( + &self, + param_env: ty::ParamEnv<'tcx>, + source_impl: DefId, + source_args: ty::GenericArgsRef<'tcx>, + target_node: specialization_graph::Node, + ) -> ty::GenericArgsRef<'tcx> { + crate::traits::translate_args(self.infcx, param_env, source_impl, source_args, target_node) + } + + pub(super) fn register_ty_outlives(&self, ty: Ty<'tcx>, lt: ty::Region<'tcx>) { + self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); + } + + pub(super) fn register_region_outlives(&self, a: ty::Region<'tcx>, b: ty::Region<'tcx>) { + // `b : a` ==> `a <= b` + // (inlined from `InferCtxt::region_outlives_predicate`) + self.infcx.sub_regions( + rustc_infer::infer::SubregionOrigin::RelateRegionParamBound(DUMMY_SP), + b, + a, + ); + } + + /// Computes the list of goals required for `arg` to be well-formed + pub(super) fn well_formed_goals( + &self, + param_env: ty::ParamEnv<'tcx>, + arg: ty::GenericArg<'tcx>, + ) -> Option>>> { + crate::traits::wf::unnormalized_obligations(self.infcx, param_env, arg) + .map(|obligations| obligations.into_iter().map(|obligation| obligation.into())) + } + + pub(super) fn is_transmutable( + &self, + src_and_dst: rustc_transmute::Types<'tcx>, + scope: Ty<'tcx>, + assume: rustc_transmute::Assume, + ) -> Result { + use rustc_transmute::Answer; + // FIXME(transmutability): This really should be returning nested goals for `Answer::If*` + match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable( + ObligationCause::dummy(), + src_and_dst, + scope, + assume, + ) { + Answer::Yes => Ok(Certainty::Yes), + Answer::No(_) | Answer::If(_) => Err(NoSolution), + } + } + + pub(super) fn can_define_opaque_ty(&self, def_id: LocalDefId) -> bool { + self.infcx.opaque_type_origin(def_id).is_some() + } + + pub(super) fn insert_hidden_type( + &mut self, + opaque_type_key: OpaqueTypeKey<'tcx>, + param_env: ty::ParamEnv<'tcx>, + hidden_ty: Ty<'tcx>, + ) -> Result<(), NoSolution> { + let mut obligations = Vec::new(); + self.infcx.insert_hidden_type( + opaque_type_key, + &ObligationCause::dummy(), + param_env, + hidden_ty, + true, + &mut obligations, + )?; + self.add_goals(obligations.into_iter().map(|o| o.into())); + Ok(()) + } + + pub(super) fn add_item_bounds_for_hidden_type( + &mut self, + opaque_def_id: DefId, + opaque_args: ty::GenericArgsRef<'tcx>, + param_env: ty::ParamEnv<'tcx>, + hidden_ty: Ty<'tcx>, + ) { + let mut obligations = Vec::new(); + self.infcx.add_item_bounds_for_hidden_type( + opaque_def_id, + opaque_args, + ObligationCause::dummy(), + param_env, + hidden_ty, + &mut obligations, + ); + self.add_goals(obligations.into_iter().map(|o| o.into())); + } + + // Do something for each opaque/hidden pair defined with `def_id` in the + // current inference context. + pub(super) fn unify_existing_opaque_tys( + &mut self, + param_env: ty::ParamEnv<'tcx>, + key: ty::OpaqueTypeKey<'tcx>, + ty: Ty<'tcx>, + ) -> Vec> { + // FIXME: Super inefficient to be cloning this... + let opaques = self.infcx.clone_opaque_types_for_query_response(); + + let mut values = vec![]; + for (candidate_key, candidate_ty) in opaques { + if candidate_key.def_id != key.def_id { + continue; + } + values.extend(self.probe_misc_candidate("opaque type storage").enter(|ecx| { + for (a, b) in std::iter::zip(candidate_key.args, key.args) { + ecx.eq(param_env, a, b)?; + } + ecx.eq(param_env, candidate_ty, ty)?; + ecx.add_item_bounds_for_hidden_type( + candidate_key.def_id.to_def_id(), + candidate_key.args, + param_env, + candidate_ty, + ); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + })); + } + values + } + + // Try to evaluate a const, or return `None` if the const is too generic. + // This doesn't mean the const isn't evaluatable, though, and should be treated + // as an ambiguity rather than no-solution. + pub(super) fn try_const_eval_resolve( + &self, + param_env: ty::ParamEnv<'tcx>, + unevaluated: ty::UnevaluatedConst<'tcx>, + ty: Ty<'tcx>, + ) -> Option> { + use rustc_middle::mir::interpret::ErrorHandled; + match self.infcx.try_const_eval_resolve(param_env, unevaluated, ty, None) { + Ok(ct) => Some(ct), + Err(ErrorHandled::Reported(e, _)) => { + Some(ty::Const::new_error(self.tcx(), e.into(), ty)) + } + Err(ErrorHandled::TooGeneric(_)) => None, + } + } + + /// Walk through the vtable of a principal trait ref, executing a `supertrait_visitor` + /// for every trait ref encountered (including the principal). Passes both the vtable + /// base and the (optional) vptr slot. + pub(super) fn walk_vtable( + &mut self, + principal: ty::PolyTraitRef<'tcx>, + mut supertrait_visitor: impl FnMut(&mut Self, ty::PolyTraitRef<'tcx>, usize, Option), + ) { + let tcx = self.tcx(); + let mut offset = 0; + prepare_vtable_segments::<()>(tcx, principal, |segment| { + match segment { + VtblSegment::MetadataDSA => { + offset += TyCtxt::COMMON_VTABLE_ENTRIES.len(); + } + VtblSegment::TraitOwnEntries { trait_ref, emit_vptr } => { + let own_vtable_entries = count_own_vtable_entries(tcx, trait_ref); + + supertrait_visitor( + self, + trait_ref, + offset, + emit_vptr.then(|| offset + own_vtable_entries), + ); + + offset += own_vtable_entries; + if emit_vptr { + offset += 1; + } + } + } + ControlFlow::Continue(()) + }); + } +} diff --git a/compiler/rustc_trait_selection/src/solve/inherent_projection.rs b/compiler/rustc_trait_selection/src/solve/inherent_projection.rs deleted file mode 100644 index 28fe59b7f6a..00000000000 --- a/compiler/rustc_trait_selection/src/solve/inherent_projection.rs +++ /dev/null @@ -1,50 +0,0 @@ -//! Computes a normalizes-to (projection) goal for inherent associated types, -//! `#![feature(inherent_associated_type)]`. Since astconv already determines -//! which impl the IAT is being projected from, we just: -//! 1. instantiate substs, -//! 2. equate the self type, and -//! 3. instantiate and register where clauses. -use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; -use rustc_middle::ty; - -use super::EvalCtxt; - -impl<'tcx> EvalCtxt<'_, 'tcx> { - pub(super) fn normalize_inherent_associated_type( - &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, - ) -> QueryResult<'tcx> { - let tcx = self.tcx(); - let inherent = goal.predicate.projection_ty; - let expected = goal.predicate.term.ty().expect("inherent consts are treated separately"); - - let impl_def_id = tcx.parent(inherent.def_id); - let impl_substs = self.fresh_args_for_item(impl_def_id); - - // Equate impl header and add impl where clauses - self.eq( - goal.param_env, - inherent.self_ty(), - tcx.type_of(impl_def_id).instantiate(tcx, impl_substs), - )?; - - // Equate IAT with the RHS of the project goal - let inherent_substs = inherent.rebase_inherent_args_onto_impl(impl_substs, tcx); - self.eq( - goal.param_env, - expected, - tcx.type_of(inherent.def_id).instantiate(tcx, inherent_substs), - ) - .expect("expected goal term to be fully unconstrained"); - - // Check both where clauses on the impl and IAT - self.add_goals( - tcx.predicates_of(inherent.def_id) - .instantiate(tcx, inherent_substs) - .into_iter() - .map(|(pred, _)| goal.with(tcx, pred)), - ); - - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } -} diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 77a3b5e1284..d45fe102805 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -32,14 +32,11 @@ mod assembly; mod canonicalize; mod eval_ctxt; mod fulfill; -mod inherent_projection; pub mod inspect; mod normalize; -mod opaques; mod project_goals; mod search_graph; mod trait_goals; -mod weak_types; pub use eval_ctxt::{ EvalCtxt, GenerateProofTree, InferCtxtEvalExt, InferCtxtSelectExt, UseGlobalCache, diff --git a/compiler/rustc_trait_selection/src/solve/opaques.rs b/compiler/rustc_trait_selection/src/solve/opaques.rs deleted file mode 100644 index f08adc0208b..00000000000 --- a/compiler/rustc_trait_selection/src/solve/opaques.rs +++ /dev/null @@ -1,85 +0,0 @@ -//! Computes a normalizes-to (projection) goal for opaque types. This goal -//! behaves differently depending on the param-env's reveal mode and whether -//! the opaque is in a defining scope. -use rustc_middle::traits::query::NoSolution; -use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; -use rustc_middle::traits::Reveal; -use rustc_middle::ty; -use rustc_middle::ty::util::NotUniqueParam; - -use super::{EvalCtxt, SolverMode}; - -impl<'tcx> EvalCtxt<'_, 'tcx> { - pub(super) fn normalize_opaque_type( - &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, - ) -> QueryResult<'tcx> { - let tcx = self.tcx(); - let opaque_ty = goal.predicate.projection_ty; - let expected = goal.predicate.term.ty().expect("no such thing as an opaque const"); - - match (goal.param_env.reveal(), self.solver_mode()) { - (Reveal::UserFacing, SolverMode::Normal) => { - let Some(opaque_ty_def_id) = opaque_ty.def_id.as_local() else { - return Err(NoSolution); - }; - // FIXME: at some point we should call queries without defining - // new opaque types but having the existing opaque type definitions. - // This will require moving this below "Prefer opaques registered already". - if !self.can_define_opaque_ty(opaque_ty_def_id) { - return Err(NoSolution); - } - // FIXME: This may have issues when the args contain aliases... - match self.tcx().uses_unique_placeholders_ignoring_regions(opaque_ty.args) { - Err(NotUniqueParam::NotParam(param)) if param.is_non_region_infer() => { - return self.evaluate_added_goals_and_make_canonical_response( - Certainty::AMBIGUOUS, - ); - } - Err(_) => { - return Err(NoSolution); - } - Ok(()) => {} - } - // Prefer opaques registered already. - let opaque_type_key = - ty::OpaqueTypeKey { def_id: opaque_ty_def_id, args: opaque_ty.args }; - let matches = - self.unify_existing_opaque_tys(goal.param_env, opaque_type_key, expected); - if !matches.is_empty() { - if let Some(response) = self.try_merge_responses(&matches) { - return Ok(response); - } else { - return self.flounder(&matches); - } - } - // Otherwise, define a new opaque type - self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?; - self.add_item_bounds_for_hidden_type( - opaque_ty.def_id, - opaque_ty.args, - goal.param_env, - expected, - ); - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } - (Reveal::UserFacing, SolverMode::Coherence) => { - // An impossible opaque type bound is the only way this goal will fail - // e.g. assigning `impl Copy := NotCopy` - self.add_item_bounds_for_hidden_type( - opaque_ty.def_id, - opaque_ty.args, - goal.param_env, - expected, - ); - self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) - } - (Reveal::All, _) => { - // FIXME: Add an assertion that opaque type storage is empty. - let actual = tcx.type_of(opaque_ty.def_id).instantiate(tcx, opaque_ty.args); - self.eq(goal.param_env, expected, actual)?; - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } - } - } -} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs deleted file mode 100644 index 339a3e73846..00000000000 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ /dev/null @@ -1,636 +0,0 @@ -use crate::traits::{check_args_compatible, specialization_graph}; - -use super::assembly::{self, structural_traits}; -use super::EvalCtxt; -use rustc_hir::def::DefKind; -use rustc_hir::def_id::DefId; -use rustc_hir::LangItem; -use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::specialization_graph::LeafDef; -use rustc_infer::traits::Reveal; -use rustc_middle::traits::solve::{ - CandidateSource, CanonicalResponse, Certainty, Goal, QueryResult, -}; -use rustc_middle::traits::BuiltinImplSource; -use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; -use rustc_middle::ty::ProjectionPredicate; -use rustc_middle::ty::{self, Ty, TyCtxt}; -use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; -use rustc_span::{sym, ErrorGuaranteed, DUMMY_SP}; - -impl<'tcx> EvalCtxt<'_, 'tcx> { - #[instrument(level = "debug", skip(self), ret)] - pub(super) fn compute_projection_goal( - &mut self, - goal: Goal<'tcx, ProjectionPredicate<'tcx>>, - ) -> QueryResult<'tcx> { - let def_id = goal.predicate.def_id(); - match self.tcx().def_kind(def_id) { - DefKind::AssocTy | DefKind::AssocConst => { - // To only compute normalization once for each projection we only - // assemble normalization candidates if the expected term is an - // unconstrained inference variable. - // - // Why: For better cache hits, since if we have an unconstrained RHS then - // there are only as many cache keys as there are (canonicalized) alias - // types in each normalizes-to goal. This also weakens inference in a - // forwards-compatible way so we don't use the value of the RHS term to - // affect candidate assembly for projections. - // - // E.g. for `::Assoc == u32` we recursively compute the goal - // `exists ::Assoc == U` and then take the resulting type for - // `U` and equate it with `u32`. This means that we don't need a separate - // projection cache in the solver, since we're piggybacking off of regular - // goal caching. - if self.term_is_fully_unconstrained(goal) { - match self.tcx().associated_item(def_id).container { - ty::AssocItemContainer::TraitContainer => { - let candidates = self.assemble_and_evaluate_candidates(goal); - self.merge_candidates(candidates) - } - ty::AssocItemContainer::ImplContainer => { - self.normalize_inherent_associated_type(goal) - } - } - } else { - self.set_normalizes_to_hack_goal(goal); - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } - } - DefKind::AnonConst => self.normalize_anon_const(goal), - DefKind::OpaqueTy => self.normalize_opaque_type(goal), - DefKind::TyAlias => self.normalize_weak_type(goal), - kind => bug!("unknown DefKind {} in projection goal: {goal:#?}", kind.descr(def_id)), - } - } - - #[instrument(level = "debug", skip(self), ret)] - fn normalize_anon_const( - &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, - ) -> QueryResult<'tcx> { - if let Some(normalized_const) = self.try_const_eval_resolve( - goal.param_env, - ty::UnevaluatedConst::new( - goal.predicate.projection_ty.def_id, - goal.predicate.projection_ty.args, - ), - self.tcx() - .type_of(goal.predicate.projection_ty.def_id) - .no_bound_vars() - .expect("const ty should not rely on other generics"), - ) { - self.eq(goal.param_env, normalized_const, goal.predicate.term.ct().unwrap())?; - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } else { - self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) - } - } -} - -impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { - fn self_ty(self) -> Ty<'tcx> { - self.self_ty() - } - - fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> { - self.projection_ty.trait_ref(tcx) - } - - fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { - self.with_self_ty(tcx, self_ty) - } - - fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId { - self.trait_def_id(tcx) - } - - fn probe_and_match_goal_against_assumption( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - assumption: ty::Clause<'tcx>, - then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>, - ) -> QueryResult<'tcx> { - if let Some(projection_pred) = assumption.as_projection_clause() { - if projection_pred.projection_def_id() == goal.predicate.def_id() { - let tcx = ecx.tcx(); - ecx.probe_misc_candidate("assumption").enter(|ecx| { - let assumption_projection_pred = - ecx.instantiate_binder_with_infer(projection_pred); - ecx.eq( - goal.param_env, - goal.predicate.projection_ty, - assumption_projection_pred.projection_ty, - )?; - ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term) - .expect("expected goal term to be fully unconstrained"); - - // Add GAT where clauses from the trait's definition - ecx.add_goals( - tcx.predicates_of(goal.predicate.def_id()) - .instantiate_own(tcx, goal.predicate.projection_ty.args) - .map(|(pred, _)| goal.with(tcx, pred)), - ); - - then(ecx) - }) - } else { - Err(NoSolution) - } - } else { - Err(NoSolution) - } - } - - fn consider_impl_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, ProjectionPredicate<'tcx>>, - impl_def_id: DefId, - ) -> QueryResult<'tcx> { - let tcx = ecx.tcx(); - - let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); - let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); - let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; - if !drcx.args_refs_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) { - return Err(NoSolution); - } - - 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); - - ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; - - let where_clause_bounds = tcx - .predicates_of(impl_def_id) - .instantiate(tcx, impl_args) - .predicates - .into_iter() - .map(|pred| goal.with(tcx, pred)); - ecx.add_goals(where_clause_bounds); - - // Add GAT where clauses from the trait's definition - ecx.add_goals( - tcx.predicates_of(goal.predicate.def_id()) - .instantiate_own(tcx, goal.predicate.projection_ty.args) - .map(|(pred, _)| goal.with(tcx, pred)), - ); - - // In case the associated item is hidden due to specialization, we have to - // return ambiguity this would otherwise be incomplete, resulting in - // unsoundness during coherence (#105782). - let Some(assoc_def) = fetch_eligible_assoc_item_def( - ecx, - goal.param_env, - goal_trait_ref, - goal.predicate.def_id(), - impl_def_id, - )? - else { - return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); - }; - - let error_response = |ecx: &mut EvalCtxt<'_, 'tcx>, reason| { - let guar = tcx.sess.delay_span_bug(tcx.def_span(assoc_def.item.def_id), reason); - let error_term = match assoc_def.item.kind { - ty::AssocKind::Const => ty::Const::new_error( - tcx, - guar, - tcx.type_of(goal.predicate.def_id()) - .instantiate(tcx, goal.predicate.projection_ty.args), - ) - .into(), - ty::AssocKind::Type => Ty::new_error(tcx, guar).into(), - ty::AssocKind::Fn => unreachable!(), - }; - ecx.eq(goal.param_env, goal.predicate.term, error_term) - .expect("expected goal term to be fully unconstrained"); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }; - - if !assoc_def.item.defaultness(tcx).has_value() { - return error_response(ecx, "missing value for assoc item in impl"); - } - - // Getting the right args here is complex, e.g. given: - // - a goal ` as Trait>::Assoc` - // - the applicable impl `impl Trait for Vec` - // - and the impl which defines `Assoc` being `impl Trait for Vec` - // - // We first rebase the goal args onto the impl, going from `[Vec, i32, u64]` - // to `[u32, u64]`. - // - // And then map these args to the args of the defining impl of `Assoc`, going - // from `[u32, u64]` to `[u32, i32, u64]`. - let impl_args_with_gat = goal.predicate.projection_ty.args.rebase_onto( - tcx, - goal_trait_ref.def_id, - impl_args, - ); - let args = ecx.translate_args( - goal.param_env, - impl_def_id, - impl_args_with_gat, - assoc_def.defining_node, - ); - - if !check_args_compatible(tcx, assoc_def.item, args) { - return error_response( - ecx, - "associated item has mismatched generic item arguments", - ); - } - - // Finally we construct the actual value of the associated type. - let term = match assoc_def.item.kind { - ty::AssocKind::Type => tcx.type_of(assoc_def.item.def_id).map_bound(|ty| ty.into()), - ty::AssocKind::Const => { - if tcx.features().associated_const_equality { - bug!("associated const projection is not supported yet") - } else { - ty::EarlyBinder::bind( - ty::Const::new_error_with_message( - tcx, - tcx.type_of(assoc_def.item.def_id).instantiate_identity(), - DUMMY_SP, - "associated const projection is not supported yet", - ) - .into(), - ) - } - } - ty::AssocKind::Fn => unreachable!("we should never project to a fn"), - }; - - ecx.eq(goal.param_env, goal.predicate.term, term.instantiate(tcx, args)) - .expect("expected goal term to be fully unconstrained"); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }) - } - - /// Fail to normalize if the predicate contains an error, alternatively, we could normalize to `ty::Error` - /// and succeed. Can experiment with this to figure out what results in better error messages. - fn consider_error_guaranteed_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - _guar: ErrorGuaranteed, - ) -> QueryResult<'tcx> { - Err(NoSolution) - } - - fn consider_auto_trait_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - ecx.tcx().sess.delay_span_bug( - ecx.tcx().def_span(goal.predicate.def_id()), - "associated types not allowed on auto traits", - ); - Err(NoSolution) - } - - fn consider_trait_alias_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("trait aliases do not have associated types: {:?}", goal); - } - - fn consider_builtin_sized_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`Sized` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_copy_clone_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`Copy`/`Clone` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_pointer_like_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`PointerLike` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_fn_ptr_trait_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`FnPtr` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_fn_trait_candidates( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - goal_kind: ty::ClosureKind, - ) -> QueryResult<'tcx> { - let tcx = ecx.tcx(); - let tupled_inputs_and_output = - match structural_traits::extract_tupled_inputs_and_output_from_callable( - tcx, - goal.predicate.self_ty(), - goal_kind, - )? { - Some(tupled_inputs_and_output) => tupled_inputs_and_output, - None => { - return ecx - .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); - } - }; - let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| { - ty::TraitRef::from_lang_item(tcx, LangItem::Sized, DUMMY_SP, [output]) - }); - - let pred = tupled_inputs_and_output - .map_bound(|(inputs, output)| ty::ProjectionPredicate { - projection_ty: tcx - .mk_alias_ty(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]), - term: output.into(), - }) - .to_predicate(tcx); - - // A built-in `Fn` impl only holds if the output is sized. - // (FIXME: technically we only need to check this if the type is a fn ptr...) - Self::consider_implied_clause(ecx, goal, pred, [goal.with(tcx, output_is_sized_pred)]) - } - - fn consider_builtin_tuple_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`Tuple` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_pointee_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - let tcx = ecx.tcx(); - ecx.probe_misc_candidate("builtin pointee").enter(|ecx| { - let metadata_ty = match goal.predicate.self_ty().kind() { - ty::Bool - | ty::Char - | ty::Int(..) - | ty::Uint(..) - | ty::Float(..) - | ty::Array(..) - | ty::RawPtr(..) - | ty::Ref(..) - | ty::FnDef(..) - | ty::FnPtr(..) - | ty::Closure(..) - | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) - | ty::Generator(..) - | ty::GeneratorWitness(..) - | ty::Never - | ty::Foreign(..) => tcx.types.unit, - - ty::Error(e) => Ty::new_error(tcx, *e), - - ty::Str | ty::Slice(_) => tcx.types.usize, - - ty::Dynamic(_, _, _) => { - let dyn_metadata = tcx.require_lang_item(LangItem::DynMetadata, None); - tcx.type_of(dyn_metadata) - .instantiate(tcx, &[ty::GenericArg::from(goal.predicate.self_ty())]) - } - - ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { - // FIXME(ptr_metadata): It would also be possible to return a `Ok(Ambig)` with no constraints. - let sized_predicate = ty::TraitRef::from_lang_item( - tcx, - LangItem::Sized, - DUMMY_SP, - [ty::GenericArg::from(goal.predicate.self_ty())], - ); - ecx.add_goal(goal.with(tcx, sized_predicate)); - tcx.types.unit - } - - ty::Adt(def, args) if def.is_struct() => match def.non_enum_variant().tail_opt() { - None => tcx.types.unit, - Some(field_def) => { - let self_ty = field_def.ty(tcx, args); - ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); - return ecx - .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); - } - }, - ty::Adt(_, _) => tcx.types.unit, - - ty::Tuple(elements) => match elements.last() { - None => tcx.types.unit, - Some(&self_ty) => { - ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); - return ecx - .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); - } - }, - - ty::Infer( - ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_), - ) - | ty::Bound(..) => bug!( - "unexpected self ty `{:?}` when normalizing `::Metadata`", - goal.predicate.self_ty() - ), - }; - - ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into()) - .expect("expected goal term to be fully unconstrained"); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }) - } - - fn consider_builtin_future_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - let self_ty = goal.predicate.self_ty(); - let ty::Generator(def_id, args, _) = *self_ty.kind() else { - return Err(NoSolution); - }; - - // Generators are not futures unless they come from `async` desugaring - let tcx = ecx.tcx(); - if !tcx.generator_is_async(def_id) { - return Err(NoSolution); - } - - let term = args.as_generator().return_ty().into(); - - Self::consider_implied_clause( - ecx, - goal, - ty::ProjectionPredicate { - projection_ty: ecx.tcx().mk_alias_ty(goal.predicate.def_id(), [self_ty]), - term, - } - .to_predicate(tcx), - // Technically, we need to check that the future type is Sized, - // but that's already proven by the generator being WF. - [], - ) - } - - fn consider_builtin_generator_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - let self_ty = goal.predicate.self_ty(); - let ty::Generator(def_id, args, _) = *self_ty.kind() else { - return Err(NoSolution); - }; - - // `async`-desugared generators do not implement the generator trait - let tcx = ecx.tcx(); - if tcx.generator_is_async(def_id) { - return Err(NoSolution); - } - - let generator = args.as_generator(); - - let name = tcx.associated_item(goal.predicate.def_id()).name; - let term = if name == sym::Return { - generator.return_ty().into() - } else if name == sym::Yield { - generator.yield_ty().into() - } else { - bug!("unexpected associated item `<{self_ty} as Generator>::{name}`") - }; - - Self::consider_implied_clause( - ecx, - goal, - ty::ProjectionPredicate { - projection_ty: ecx - .tcx() - .mk_alias_ty(goal.predicate.def_id(), [self_ty, generator.resume_ty()]), - term, - } - .to_predicate(tcx), - // Technically, we need to check that the future type is Sized, - // but that's already proven by the generator being WF. - [], - ) - } - - fn consider_unsize_to_dyn_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`Unsize` does not have an associated type: {:?}", goal) - } - - fn consider_structural_builtin_unsize_candidates( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> { - bug!("`Unsize` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_discriminant_kind_candidate( - ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - let self_ty = goal.predicate.self_ty(); - let discriminant_ty = match *self_ty.kind() { - ty::Bool - | ty::Char - | ty::Int(..) - | ty::Uint(..) - | ty::Float(..) - | ty::Array(..) - | ty::RawPtr(..) - | ty::Ref(..) - | ty::FnDef(..) - | ty::FnPtr(..) - | ty::Closure(..) - | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) - | ty::Generator(..) - | ty::GeneratorWitness(..) - | ty::Never - | ty::Foreign(..) - | ty::Adt(_, _) - | ty::Str - | ty::Slice(_) - | ty::Dynamic(_, _, _) - | ty::Tuple(_) - | ty::Error(_) => self_ty.discriminant_ty(ecx.tcx()), - - // We do not call `Ty::discriminant_ty` on alias, param, or placeholder - // types, which return `::Discriminant` - // (or ICE in the case of placeholders). Projecting a type to itself - // is never really productive. - ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { - return Err(NoSolution); - } - - ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) - | ty::Bound(..) => bug!( - "unexpected self ty `{:?}` when normalizing `::Discriminant`", - goal.predicate.self_ty() - ), - }; - - ecx.probe_misc_candidate("builtin discriminant kind").enter(|ecx| { - ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into()) - .expect("expected goal term to be fully unconstrained"); - ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - }) - } - - fn consider_builtin_destruct_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`Destruct` does not have an associated type: {:?}", goal); - } - - fn consider_builtin_transmute_candidate( - _ecx: &mut EvalCtxt<'_, 'tcx>, - goal: Goal<'tcx, Self>, - ) -> QueryResult<'tcx> { - bug!("`BikeshedIntrinsicFrom` does not have an associated type: {:?}", goal) - } -} - -/// This behavior is also implemented in `rustc_ty_utils` and in the old `project` code. -/// -/// FIXME: We should merge these 3 implementations as it's likely that they otherwise -/// diverge. -#[instrument(level = "debug", skip(ecx, param_env), ret)] -fn fetch_eligible_assoc_item_def<'tcx>( - ecx: &EvalCtxt<'_, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - goal_trait_ref: ty::TraitRef<'tcx>, - trait_assoc_def_id: DefId, - impl_def_id: DefId, -) -> Result, NoSolution> { - let node_item = specialization_graph::assoc_def(ecx.tcx(), impl_def_id, trait_assoc_def_id) - .map_err(|ErrorGuaranteed { .. }| NoSolution)?; - - let eligible = if node_item.is_final() { - // Non-specializable items are always projectable. - true - } else { - // Only reveal a specializable default if we're past type-checking - // and the obligation is monomorphic, otherwise passes such as - // transmute checking and polymorphic MIR optimizations could - // get a result which isn't correct for all monomorphizations. - if param_env.reveal() == Reveal::All { - let poly_trait_ref = ecx.resolve_vars_if_possible(goal_trait_ref); - !poly_trait_ref.still_further_specializable() - } else { - debug!(?node_item.item.def_id, "not eligible due to default"); - false - } - }; - - if eligible { Ok(Some(node_item)) } else { Ok(None) } -} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/inherent_projection.rs b/compiler/rustc_trait_selection/src/solve/project_goals/inherent_projection.rs new file mode 100644 index 00000000000..28fe59b7f6a --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals/inherent_projection.rs @@ -0,0 +1,50 @@ +//! Computes a normalizes-to (projection) goal for inherent associated types, +//! `#![feature(inherent_associated_type)]`. Since astconv already determines +//! which impl the IAT is being projected from, we just: +//! 1. instantiate substs, +//! 2. equate the self type, and +//! 3. instantiate and register where clauses. +use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::ty; + +use super::EvalCtxt; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn normalize_inherent_associated_type( + &mut self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + let inherent = goal.predicate.projection_ty; + let expected = goal.predicate.term.ty().expect("inherent consts are treated separately"); + + let impl_def_id = tcx.parent(inherent.def_id); + let impl_substs = self.fresh_args_for_item(impl_def_id); + + // Equate impl header and add impl where clauses + self.eq( + goal.param_env, + inherent.self_ty(), + tcx.type_of(impl_def_id).instantiate(tcx, impl_substs), + )?; + + // Equate IAT with the RHS of the project goal + let inherent_substs = inherent.rebase_inherent_args_onto_impl(impl_substs, tcx); + self.eq( + goal.param_env, + expected, + tcx.type_of(inherent.def_id).instantiate(tcx, inherent_substs), + ) + .expect("expected goal term to be fully unconstrained"); + + // Check both where clauses on the impl and IAT + self.add_goals( + tcx.predicates_of(inherent.def_id) + .instantiate(tcx, inherent_substs) + .into_iter() + .map(|(pred, _)| goal.with(tcx, pred)), + ); + + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs b/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs new file mode 100644 index 00000000000..2c000293f26 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals/mod.rs @@ -0,0 +1,640 @@ +use crate::traits::{check_args_compatible, specialization_graph}; + +use super::assembly::{self, structural_traits}; +use super::EvalCtxt; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::DefId; +use rustc_hir::LangItem; +use rustc_infer::traits::query::NoSolution; +use rustc_infer::traits::specialization_graph::LeafDef; +use rustc_infer::traits::Reveal; +use rustc_middle::traits::solve::{ + CandidateSource, CanonicalResponse, Certainty, Goal, QueryResult, +}; +use rustc_middle::traits::BuiltinImplSource; +use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::ty::ProjectionPredicate; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; +use rustc_span::{sym, ErrorGuaranteed, DUMMY_SP}; + +mod inherent_projection; +mod opaques; +mod weak_types; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + #[instrument(level = "debug", skip(self), ret)] + pub(super) fn compute_projection_goal( + &mut self, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let def_id = goal.predicate.def_id(); + match self.tcx().def_kind(def_id) { + DefKind::AssocTy | DefKind::AssocConst => { + // To only compute normalization once for each projection we only + // assemble normalization candidates if the expected term is an + // unconstrained inference variable. + // + // Why: For better cache hits, since if we have an unconstrained RHS then + // there are only as many cache keys as there are (canonicalized) alias + // types in each normalizes-to goal. This also weakens inference in a + // forwards-compatible way so we don't use the value of the RHS term to + // affect candidate assembly for projections. + // + // E.g. for `::Assoc == u32` we recursively compute the goal + // `exists ::Assoc == U` and then take the resulting type for + // `U` and equate it with `u32`. This means that we don't need a separate + // projection cache in the solver, since we're piggybacking off of regular + // goal caching. + if self.term_is_fully_unconstrained(goal) { + match self.tcx().associated_item(def_id).container { + ty::AssocItemContainer::TraitContainer => { + let candidates = self.assemble_and_evaluate_candidates(goal); + self.merge_candidates(candidates) + } + ty::AssocItemContainer::ImplContainer => { + self.normalize_inherent_associated_type(goal) + } + } + } else { + self.set_normalizes_to_hack_goal(goal); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + } + DefKind::AnonConst => self.normalize_anon_const(goal), + DefKind::OpaqueTy => self.normalize_opaque_type(goal), + DefKind::TyAlias => self.normalize_weak_type(goal), + kind => bug!("unknown DefKind {} in projection goal: {goal:#?}", kind.descr(def_id)), + } + } + + #[instrument(level = "debug", skip(self), ret)] + fn normalize_anon_const( + &mut self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + if let Some(normalized_const) = self.try_const_eval_resolve( + goal.param_env, + ty::UnevaluatedConst::new( + goal.predicate.projection_ty.def_id, + goal.predicate.projection_ty.args, + ), + self.tcx() + .type_of(goal.predicate.projection_ty.def_id) + .no_bound_vars() + .expect("const ty should not rely on other generics"), + ) { + self.eq(goal.param_env, normalized_const, goal.predicate.term.ct().unwrap())?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } else { + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + } + } +} + +impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { + fn self_ty(self) -> Ty<'tcx> { + self.self_ty() + } + + fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> { + self.projection_ty.trait_ref(tcx) + } + + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { + self.with_self_ty(tcx, self_ty) + } + + fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId { + self.trait_def_id(tcx) + } + + fn probe_and_match_goal_against_assumption( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Clause<'tcx>, + then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>, + ) -> QueryResult<'tcx> { + if let Some(projection_pred) = assumption.as_projection_clause() { + if projection_pred.projection_def_id() == goal.predicate.def_id() { + let tcx = ecx.tcx(); + ecx.probe_misc_candidate("assumption").enter(|ecx| { + let assumption_projection_pred = + ecx.instantiate_binder_with_infer(projection_pred); + ecx.eq( + goal.param_env, + goal.predicate.projection_ty, + assumption_projection_pred.projection_ty, + )?; + ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term) + .expect("expected goal term to be fully unconstrained"); + + // Add GAT where clauses from the trait's definition + ecx.add_goals( + tcx.predicates_of(goal.predicate.def_id()) + .instantiate_own(tcx, goal.predicate.projection_ty.args) + .map(|(pred, _)| goal.with(tcx, pred)), + ); + + then(ecx) + }) + } else { + Err(NoSolution) + } + } else { + Err(NoSolution) + } + } + + fn consider_impl_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, ProjectionPredicate<'tcx>>, + impl_def_id: DefId, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + + let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); + let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); + let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; + if !drcx.args_refs_may_unify(goal_trait_ref.args, impl_trait_ref.skip_binder().args) { + return Err(NoSolution); + } + + 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); + + ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + + let where_clause_bounds = tcx + .predicates_of(impl_def_id) + .instantiate(tcx, impl_args) + .predicates + .into_iter() + .map(|pred| goal.with(tcx, pred)); + ecx.add_goals(where_clause_bounds); + + // Add GAT where clauses from the trait's definition + ecx.add_goals( + tcx.predicates_of(goal.predicate.def_id()) + .instantiate_own(tcx, goal.predicate.projection_ty.args) + .map(|(pred, _)| goal.with(tcx, pred)), + ); + + // In case the associated item is hidden due to specialization, we have to + // return ambiguity this would otherwise be incomplete, resulting in + // unsoundness during coherence (#105782). + let Some(assoc_def) = fetch_eligible_assoc_item_def( + ecx, + goal.param_env, + goal_trait_ref, + goal.predicate.def_id(), + impl_def_id, + )? + else { + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + }; + + let error_response = |ecx: &mut EvalCtxt<'_, 'tcx>, reason| { + let guar = tcx.sess.delay_span_bug(tcx.def_span(assoc_def.item.def_id), reason); + let error_term = match assoc_def.item.kind { + ty::AssocKind::Const => ty::Const::new_error( + tcx, + guar, + tcx.type_of(goal.predicate.def_id()) + .instantiate(tcx, goal.predicate.projection_ty.args), + ) + .into(), + ty::AssocKind::Type => Ty::new_error(tcx, guar).into(), + ty::AssocKind::Fn => unreachable!(), + }; + ecx.eq(goal.param_env, goal.predicate.term, error_term) + .expect("expected goal term to be fully unconstrained"); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }; + + if !assoc_def.item.defaultness(tcx).has_value() { + return error_response(ecx, "missing value for assoc item in impl"); + } + + // Getting the right args here is complex, e.g. given: + // - a goal ` as Trait>::Assoc` + // - the applicable impl `impl Trait for Vec` + // - and the impl which defines `Assoc` being `impl Trait for Vec` + // + // We first rebase the goal args onto the impl, going from `[Vec, i32, u64]` + // to `[u32, u64]`. + // + // And then map these args to the args of the defining impl of `Assoc`, going + // from `[u32, u64]` to `[u32, i32, u64]`. + let impl_args_with_gat = goal.predicate.projection_ty.args.rebase_onto( + tcx, + goal_trait_ref.def_id, + impl_args, + ); + let args = ecx.translate_args( + goal.param_env, + impl_def_id, + impl_args_with_gat, + assoc_def.defining_node, + ); + + if !check_args_compatible(tcx, assoc_def.item, args) { + return error_response( + ecx, + "associated item has mismatched generic item arguments", + ); + } + + // Finally we construct the actual value of the associated type. + let term = match assoc_def.item.kind { + ty::AssocKind::Type => tcx.type_of(assoc_def.item.def_id).map_bound(|ty| ty.into()), + ty::AssocKind::Const => { + if tcx.features().associated_const_equality { + bug!("associated const projection is not supported yet") + } else { + ty::EarlyBinder::bind( + ty::Const::new_error_with_message( + tcx, + tcx.type_of(assoc_def.item.def_id).instantiate_identity(), + DUMMY_SP, + "associated const projection is not supported yet", + ) + .into(), + ) + } + } + ty::AssocKind::Fn => unreachable!("we should never project to a fn"), + }; + + ecx.eq(goal.param_env, goal.predicate.term, term.instantiate(tcx, args)) + .expect("expected goal term to be fully unconstrained"); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + + /// Fail to normalize if the predicate contains an error, alternatively, we could normalize to `ty::Error` + /// and succeed. Can experiment with this to figure out what results in better error messages. + fn consider_error_guaranteed_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + _guar: ErrorGuaranteed, + ) -> QueryResult<'tcx> { + Err(NoSolution) + } + + fn consider_auto_trait_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + ecx.tcx().sess.delay_span_bug( + ecx.tcx().def_span(goal.predicate.def_id()), + "associated types not allowed on auto traits", + ); + Err(NoSolution) + } + + fn consider_trait_alias_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("trait aliases do not have associated types: {:?}", goal); + } + + fn consider_builtin_sized_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Sized` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_copy_clone_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Copy`/`Clone` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_pointer_like_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`PointerLike` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_fn_ptr_trait_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`FnPtr` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_fn_trait_candidates( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + goal_kind: ty::ClosureKind, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + let tupled_inputs_and_output = + match structural_traits::extract_tupled_inputs_and_output_from_callable( + tcx, + goal.predicate.self_ty(), + goal_kind, + )? { + Some(tupled_inputs_and_output) => tupled_inputs_and_output, + None => { + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } + }; + let output_is_sized_pred = tupled_inputs_and_output.map_bound(|(_, output)| { + ty::TraitRef::from_lang_item(tcx, LangItem::Sized, DUMMY_SP, [output]) + }); + + let pred = tupled_inputs_and_output + .map_bound(|(inputs, output)| ty::ProjectionPredicate { + projection_ty: tcx + .mk_alias_ty(goal.predicate.def_id(), [goal.predicate.self_ty(), inputs]), + term: output.into(), + }) + .to_predicate(tcx); + + // A built-in `Fn` impl only holds if the output is sized. + // (FIXME: technically we only need to check this if the type is a fn ptr...) + Self::consider_implied_clause(ecx, goal, pred, [goal.with(tcx, output_is_sized_pred)]) + } + + fn consider_builtin_tuple_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Tuple` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_pointee_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let tcx = ecx.tcx(); + ecx.probe_misc_candidate("builtin pointee").enter(|ecx| { + let metadata_ty = match goal.predicate.self_ty().kind() { + ty::Bool + | ty::Char + | ty::Int(..) + | ty::Uint(..) + | ty::Float(..) + | ty::Array(..) + | ty::RawPtr(..) + | ty::Ref(..) + | ty::FnDef(..) + | ty::FnPtr(..) + | ty::Closure(..) + | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::Never + | ty::Foreign(..) => tcx.types.unit, + + ty::Error(e) => Ty::new_error(tcx, *e), + + ty::Str | ty::Slice(_) => tcx.types.usize, + + ty::Dynamic(_, _, _) => { + let dyn_metadata = tcx.require_lang_item(LangItem::DynMetadata, None); + tcx.type_of(dyn_metadata) + .instantiate(tcx, &[ty::GenericArg::from(goal.predicate.self_ty())]) + } + + ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { + // FIXME(ptr_metadata): It would also be possible to return a `Ok(Ambig)` with no constraints. + let sized_predicate = ty::TraitRef::from_lang_item( + tcx, + LangItem::Sized, + DUMMY_SP, + [ty::GenericArg::from(goal.predicate.self_ty())], + ); + ecx.add_goal(goal.with(tcx, sized_predicate)); + tcx.types.unit + } + + ty::Adt(def, args) if def.is_struct() => match def.non_enum_variant().tail_opt() { + None => tcx.types.unit, + Some(field_def) => { + let self_ty = field_def.ty(tcx, args); + ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); + } + }, + ty::Adt(_, _) => tcx.types.unit, + + ty::Tuple(elements) => match elements.last() { + None => tcx.types.unit, + Some(&self_ty) => { + ecx.add_goal(goal.with(tcx, goal.predicate.with_self_ty(tcx, self_ty))); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); + } + }, + + ty::Infer( + ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_), + ) + | ty::Bound(..) => bug!( + "unexpected self ty `{:?}` when normalizing `::Metadata`", + goal.predicate.self_ty() + ), + }; + + ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into()) + .expect("expected goal term to be fully unconstrained"); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + + fn consider_builtin_future_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let ty::Generator(def_id, args, _) = *self_ty.kind() else { + return Err(NoSolution); + }; + + // Generators are not futures unless they come from `async` desugaring + let tcx = ecx.tcx(); + if !tcx.generator_is_async(def_id) { + return Err(NoSolution); + } + + let term = args.as_generator().return_ty().into(); + + Self::consider_implied_clause( + ecx, + goal, + ty::ProjectionPredicate { + projection_ty: ecx.tcx().mk_alias_ty(goal.predicate.def_id(), [self_ty]), + term, + } + .to_predicate(tcx), + // Technically, we need to check that the future type is Sized, + // but that's already proven by the generator being WF. + [], + ) + } + + fn consider_builtin_generator_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let ty::Generator(def_id, args, _) = *self_ty.kind() else { + return Err(NoSolution); + }; + + // `async`-desugared generators do not implement the generator trait + let tcx = ecx.tcx(); + if tcx.generator_is_async(def_id) { + return Err(NoSolution); + } + + let generator = args.as_generator(); + + let name = tcx.associated_item(goal.predicate.def_id()).name; + let term = if name == sym::Return { + generator.return_ty().into() + } else if name == sym::Yield { + generator.yield_ty().into() + } else { + bug!("unexpected associated item `<{self_ty} as Generator>::{name}`") + }; + + Self::consider_implied_clause( + ecx, + goal, + ty::ProjectionPredicate { + projection_ty: ecx + .tcx() + .mk_alias_ty(goal.predicate.def_id(), [self_ty, generator.resume_ty()]), + term, + } + .to_predicate(tcx), + // Technically, we need to check that the future type is Sized, + // but that's already proven by the generator being WF. + [], + ) + } + + fn consider_unsize_to_dyn_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Unsize` does not have an associated type: {:?}", goal) + } + + fn consider_structural_builtin_unsize_candidates( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> Vec<(CanonicalResponse<'tcx>, BuiltinImplSource)> { + bug!("`Unsize` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_discriminant_kind_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + let self_ty = goal.predicate.self_ty(); + let discriminant_ty = match *self_ty.kind() { + ty::Bool + | ty::Char + | ty::Int(..) + | ty::Uint(..) + | ty::Float(..) + | ty::Array(..) + | ty::RawPtr(..) + | ty::Ref(..) + | ty::FnDef(..) + | ty::FnPtr(..) + | ty::Closure(..) + | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::Never + | ty::Foreign(..) + | ty::Adt(_, _) + | ty::Str + | ty::Slice(_) + | ty::Dynamic(_, _, _) + | ty::Tuple(_) + | ty::Error(_) => self_ty.discriminant_ty(ecx.tcx()), + + // We do not call `Ty::discriminant_ty` on alias, param, or placeholder + // types, which return `::Discriminant` + // (or ICE in the case of placeholders). Projecting a type to itself + // is never really productive. + ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { + return Err(NoSolution); + } + + ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) + | ty::Bound(..) => bug!( + "unexpected self ty `{:?}` when normalizing `::Discriminant`", + goal.predicate.self_ty() + ), + }; + + ecx.probe_misc_candidate("builtin discriminant kind").enter(|ecx| { + ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into()) + .expect("expected goal term to be fully unconstrained"); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + + fn consider_builtin_destruct_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Destruct` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_transmute_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`BikeshedIntrinsicFrom` does not have an associated type: {:?}", goal) + } +} + +/// This behavior is also implemented in `rustc_ty_utils` and in the old `project` code. +/// +/// FIXME: We should merge these 3 implementations as it's likely that they otherwise +/// diverge. +#[instrument(level = "debug", skip(ecx, param_env), ret)] +fn fetch_eligible_assoc_item_def<'tcx>( + ecx: &EvalCtxt<'_, 'tcx>, + param_env: ty::ParamEnv<'tcx>, + goal_trait_ref: ty::TraitRef<'tcx>, + trait_assoc_def_id: DefId, + impl_def_id: DefId, +) -> Result, NoSolution> { + let node_item = specialization_graph::assoc_def(ecx.tcx(), impl_def_id, trait_assoc_def_id) + .map_err(|ErrorGuaranteed { .. }| NoSolution)?; + + let eligible = if node_item.is_final() { + // Non-specializable items are always projectable. + true + } else { + // Only reveal a specializable default if we're past type-checking + // and the obligation is monomorphic, otherwise passes such as + // transmute checking and polymorphic MIR optimizations could + // get a result which isn't correct for all monomorphizations. + if param_env.reveal() == Reveal::All { + let poly_trait_ref = ecx.resolve_vars_if_possible(goal_trait_ref); + !poly_trait_ref.still_further_specializable() + } else { + debug!(?node_item.item.def_id, "not eligible due to default"); + false + } + }; + + if eligible { Ok(Some(node_item)) } else { Ok(None) } +} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs b/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs new file mode 100644 index 00000000000..ebd129f32b9 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals/opaques.rs @@ -0,0 +1,85 @@ +//! Computes a normalizes-to (projection) goal for opaque types. This goal +//! behaves differently depending on the param-env's reveal mode and whether +//! the opaque is in a defining scope. +use rustc_middle::traits::query::NoSolution; +use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::traits::Reveal; +use rustc_middle::ty; +use rustc_middle::ty::util::NotUniqueParam; + +use crate::solve::{EvalCtxt, SolverMode}; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn normalize_opaque_type( + &mut self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + let opaque_ty = goal.predicate.projection_ty; + let expected = goal.predicate.term.ty().expect("no such thing as an opaque const"); + + match (goal.param_env.reveal(), self.solver_mode()) { + (Reveal::UserFacing, SolverMode::Normal) => { + let Some(opaque_ty_def_id) = opaque_ty.def_id.as_local() else { + return Err(NoSolution); + }; + // FIXME: at some point we should call queries without defining + // new opaque types but having the existing opaque type definitions. + // This will require moving this below "Prefer opaques registered already". + if !self.can_define_opaque_ty(opaque_ty_def_id) { + return Err(NoSolution); + } + // FIXME: This may have issues when the args contain aliases... + match self.tcx().uses_unique_placeholders_ignoring_regions(opaque_ty.args) { + Err(NotUniqueParam::NotParam(param)) if param.is_non_region_infer() => { + return self.evaluate_added_goals_and_make_canonical_response( + Certainty::AMBIGUOUS, + ); + } + Err(_) => { + return Err(NoSolution); + } + Ok(()) => {} + } + // Prefer opaques registered already. + let opaque_type_key = + ty::OpaqueTypeKey { def_id: opaque_ty_def_id, args: opaque_ty.args }; + let matches = + self.unify_existing_opaque_tys(goal.param_env, opaque_type_key, expected); + if !matches.is_empty() { + if let Some(response) = self.try_merge_responses(&matches) { + return Ok(response); + } else { + return self.flounder(&matches); + } + } + // Otherwise, define a new opaque type + self.insert_hidden_type(opaque_type_key, goal.param_env, expected)?; + self.add_item_bounds_for_hidden_type( + opaque_ty.def_id, + opaque_ty.args, + goal.param_env, + expected, + ); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + (Reveal::UserFacing, SolverMode::Coherence) => { + // An impossible opaque type bound is the only way this goal will fail + // e.g. assigning `impl Copy := NotCopy` + self.add_item_bounds_for_hidden_type( + opaque_ty.def_id, + opaque_ty.args, + goal.param_env, + expected, + ); + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + } + (Reveal::All, _) => { + // FIXME: Add an assertion that opaque type storage is empty. + let actual = tcx.type_of(opaque_ty.def_id).instantiate(tcx, opaque_ty.args); + self.eq(goal.param_env, expected, actual)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/project_goals/weak_types.rs b/compiler/rustc_trait_selection/src/solve/project_goals/weak_types.rs new file mode 100644 index 00000000000..54de32cf618 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/project_goals/weak_types.rs @@ -0,0 +1,34 @@ +//! Computes a normalizes-to (projection) goal for inherent associated types, +//! `#![feature(lazy_type_alias)]` and `#![feature(type_alias_impl_trait)]`. +//! +//! Since a weak alias is not ambiguous, this just computes the `type_of` of +//! the alias and registers the where-clauses of the type alias. +use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; +use rustc_middle::ty; + +use super::EvalCtxt; + +impl<'tcx> EvalCtxt<'_, 'tcx> { + pub(super) fn normalize_weak_type( + &mut self, + goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, + ) -> QueryResult<'tcx> { + let tcx = self.tcx(); + let weak_ty = goal.predicate.projection_ty; + let expected = goal.predicate.term.ty().expect("no such thing as a const alias"); + + let actual = tcx.type_of(weak_ty.def_id).instantiate(tcx, weak_ty.args); + self.eq(goal.param_env, expected, actual)?; + + // Check where clauses + self.add_goals( + tcx.predicates_of(weak_ty.def_id) + .instantiate(tcx, weak_ty.args) + .predicates + .into_iter() + .map(|pred| goal.with(tcx, pred)), + ); + + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/search_graph.rs b/compiler/rustc_trait_selection/src/solve/search_graph.rs new file mode 100644 index 00000000000..33513f6bd43 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/search_graph.rs @@ -0,0 +1,368 @@ +use super::inspect; +use super::inspect::ProofTreeBuilder; +use super::SolverMode; +use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::fx::FxHashSet; +use rustc_index::Idx; +use rustc_index::IndexVec; +use rustc_middle::dep_graph::dep_kinds; +use rustc_middle::traits::solve::inspect::CacheHit; +use rustc_middle::traits::solve::CacheData; +use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult}; +use rustc_middle::ty::TyCtxt; +use rustc_session::Limit; +use std::collections::hash_map::Entry; + +rustc_index::newtype_index! { + pub struct StackDepth {} +} + +#[derive(Debug)] +struct StackEntry<'tcx> { + input: CanonicalInput<'tcx>, + available_depth: Limit, + // The maximum depth reached by this stack entry, only up-to date + // for the top of the stack and lazily updated for the rest. + reached_depth: StackDepth, + // In case of a cycle, the depth of the root. + cycle_root_depth: StackDepth, + + encountered_overflow: bool, + has_been_used: bool, + /// Starts out as `None` and gets set when rerunning this + /// goal in case we encounter a cycle. + provisional_result: Option>, + + /// We put only the root goal of a coinductive cycle into the global cache. + /// + /// If we were to use that result when later trying to prove another cycle + /// participant, we can end up with unstable query results. + /// + /// See tests/ui/new-solver/coinduction/incompleteness-unstable-result.rs for + /// an example of where this is needed. + cycle_participants: FxHashSet>, +} + +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*. + stack: IndexVec>, + stack_entries: FxHashMap, StackDepth>, +} + +impl<'tcx> SearchGraph<'tcx> { + pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> { + Self { + mode, + local_overflow_limit: tcx.recursion_limit().0.checked_ilog2().unwrap_or(0) as usize, + stack: Default::default(), + stack_entries: Default::default(), + } + } + + pub(super) fn solver_mode(&self) -> SolverMode { + 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) { + let reached_depth = self.stack.next_index().plus(additional_depth); + if let Some(last) = self.stack.raw.last_mut() { + last.reached_depth = last.reached_depth.max(reached_depth); + last.encountered_overflow |= encountered_overflow; + } + } + + /// Pops the highest goal from the stack, lazily updating the + /// the next goal in the stack. + /// + /// Directly popping from the stack instead of using this method + /// would cause us to not track overflow and recursion depth correctly. + fn pop_stack(&mut self) -> StackEntry<'tcx> { + let elem = self.stack.pop().unwrap(); + assert!(self.stack_entries.remove(&elem.input).is_some()); + if let Some(last) = self.stack.raw.last_mut() { + last.reached_depth = last.reached_depth.max(elem.reached_depth); + last.encountered_overflow |= elem.encountered_overflow; + } + elem + } + + /// The trait solver behavior is different for coherence + /// so we use a separate cache. Alternatively we could use + /// a single cache and share it between coherence and ordinary + /// trait solving. + pub(super) fn global_cache(&self, tcx: TyCtxt<'tcx>) -> &'tcx EvaluationCache<'tcx> { + match self.mode { + SolverMode::Normal => &tcx.new_solver_evaluation_cache, + SolverMode::Coherence => &tcx.new_solver_coherence_evaluation_cache, + } + } + + pub(super) fn is_empty(&self) -> bool { + self.stack.is_empty() + } + + /// Whether we're currently in a cycle. This should only be used + /// for debug assertions. + pub(super) fn in_cycle(&self) -> bool { + if let Some(stack_depth) = self.stack.last_index() { + // Either the current goal on the stack is the root of a cycle + // or it depends on a goal with a lower depth. + self.stack[stack_depth].has_been_used + || self.stack[stack_depth].cycle_root_depth != stack_depth + } else { + false + } + } + + /// Fetches whether the current goal encountered overflow. + /// + /// This should only be used for the check in `evaluate_goal`. + pub(super) fn encountered_overflow(&self) -> bool { + if let Some(last) = self.stack.raw.last() { last.encountered_overflow } else { false } + } + + /// Resets `encountered_overflow` of the current goal. + /// + /// This should only be used for the check in `evaluate_goal`. + pub(super) fn reset_encountered_overflow(&mut self, encountered_overflow: bool) -> bool { + if let Some(last) = self.stack.raw.last_mut() { + let prev = last.encountered_overflow; + last.encountered_overflow = encountered_overflow; + prev + } else { + false + } + } + + /// Returns the remaining depth allowed for nested goals. + /// + /// This is generally simply one less than the current depth. + /// However, if we encountered overflow, we significantly reduce + /// the remaining depth of all nested goals to prevent hangs + /// in case there is exponential blowup. + fn allowed_depth_for_nested( + tcx: TyCtxt<'tcx>, + stack: &IndexVec>, + ) -> Option { + if let Some(last) = stack.raw.last() { + if last.available_depth.0 == 0 { + return None; + } + + Some(if last.encountered_overflow { + Limit(last.available_depth.0 / 4) + } else { + Limit(last.available_depth.0 - 1) + }) + } else { + Some(tcx.recursion_limit()) + } + } + + /// 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(super) fn with_new_goal( + &mut self, + tcx: TyCtxt<'tcx>, + input: CanonicalInput<'tcx>, + inspect: &mut ProofTreeBuilder<'tcx>, + mut prove_goal: impl FnMut(&mut Self, &mut ProofTreeBuilder<'tcx>) -> QueryResult<'tcx>, + ) -> QueryResult<'tcx> { + // Check for overflow. + let Some(available_depth) = Self::allowed_depth_for_nested(tcx, &self.stack) else { + if let Some(last) = self.stack.raw.last_mut() { + last.encountered_overflow = true; + } + + inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::Overflow); + return Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); + }; + + // Try to fetch the goal from the global cache. + if inspect.use_global_cache() { + if let Some(CacheData { result, reached_depth, encountered_overflow }) = + self.global_cache(tcx).get( + tcx, + input, + |cycle_participants| { + self.stack.iter().any(|entry| cycle_participants.contains(&entry.input)) + }, + available_depth, + ) + { + inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( + CacheHit::Global, + )); + self.on_cache_hit(reached_depth, encountered_overflow); + return result; + } + } + + // Check whether we're in a cycle. + match self.stack_entries.entry(input) { + // No entry, we push this goal on the stack and try to prove it. + Entry::Vacant(v) => { + let depth = self.stack.next_index(); + let entry = StackEntry { + input, + available_depth, + reached_depth: depth, + cycle_root_depth: depth, + encountered_overflow: false, + has_been_used: false, + provisional_result: None, + cycle_participants: Default::default(), + }; + assert_eq!(self.stack.push(entry), depth); + v.insert(depth); + } + // We have a nested goal which relies on a goal `root` deeper in the stack. + // + // We first store that we may have to reprove `root` in case the provisional + // response is not equal to the final response. We also update the depth of all + // goals which recursively depend on our current goal to depend on `root` + // instead. + // + // Finally we can return either the provisional response for that goal if we have a + // coinductive cycle or an ambiguous result if the cycle is inductive. + Entry::Occupied(entry) => { + inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( + CacheHit::Provisional, + )); + + let stack_depth = *entry.get(); + debug!("encountered cycle with depth {stack_depth:?}"); + // We start by updating the root depth of all cycle participants, and + // add all cycle participants to the root. + let root_depth = self.stack[stack_depth].cycle_root_depth; + let (prev, participants) = self.stack.raw.split_at_mut(stack_depth.as_usize() + 1); + let root = &mut prev[root_depth.as_usize()]; + for entry in participants { + debug_assert!(entry.cycle_root_depth >= root_depth); + entry.cycle_root_depth = root_depth; + root.cycle_participants.insert(entry.input); + // FIXME(@lcnr): I believe that this line is needed as we could + // otherwise access a cache entry for the root of a cycle while + // computing the result for a cycle participant. This can result + // in unstable results due to incompleteness. + // + // However, a test for this would be an even more complex version of + // tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs. + // I did not bother to write such a test and we have no regression test + // for this. It would be good to have such a test :) + #[allow(rustc::potential_query_instability)] + root.cycle_participants.extend(entry.cycle_participants.drain()); + } + + // If we're in a cycle, we have to retry proving the cycle head + // until we reach a fixpoint. It is not enough to simply retry the + // `root` goal of this cycle. + // + // See tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs + // for an example. + self.stack[stack_depth].has_been_used = true; + return if let Some(result) = self.stack[stack_depth].provisional_result { + result + } else { + // If we don't have a provisional result yet we're in the first iteration, + // so we start with no constraints. + let is_coinductive = self.stack.raw[stack_depth.index()..] + .iter() + .all(|entry| entry.input.value.goal.predicate.is_coinductive(tcx)); + if is_coinductive { + Self::response_no_constraints(tcx, input, Certainty::Yes) + } else { + Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) + } + }; + } + } + + // This is for global caching, so we properly track query dependencies. + // Everything that affects the `result` should be performed within this + // `with_anon_task` closure. + let ((final_entry, result), dep_node) = + tcx.dep_graph.with_anon_task(tcx, dep_kinds::TraitSelect, || { + // When we encounter a coinductive cycle, we have to fetch the + // result of that cycle while we are still computing it. Because + // 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() { + let result = prove_goal(self, inspect); + + // Check whether the current goal is the root of a cycle and whether + // we have to rerun because its provisional result differed from the + // final result. + let stack_entry = self.pop_stack(); + debug_assert_eq!(stack_entry.input, input); + if stack_entry.has_been_used + && stack_entry.provisional_result.map_or(true, |r| r != result) + { + // If so, update its provisional result and reevaluate it. + let depth = self.stack.push(StackEntry { + has_been_used: false, + provisional_result: Some(result), + ..stack_entry + }); + assert_eq!(self.stack_entries.insert(input, depth), None); + } else { + return (stack_entry, result); + } + } + + debug!("canonical cycle overflow"); + let current_entry = self.pop_stack(); + let result = Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); + (current_entry, result) + }); + + // We're now done with this goal. In case this goal is involved in a larger cycle + // do not remove it from the provisional cache and update its provisional result. + // We only add the root of cycles to the global cache. + // + // It is not possible for any nested goal to depend on something deeper on the + // stack, as this would have also updated the depth of the current goal. + if final_entry.cycle_root_depth == self.stack.next_index() { + // When encountering a cycle, both inductive and coinductive, we only + // move the root into the global cache. We also store all other cycle + // participants involved. + // + // We disable the global cache entry of the root goal if a cycle + // participant is on the stack. This is necessary to prevent unstable + // results. See the comment of `StackEntry::cycle_participants` for + // more details. + let reached_depth = final_entry.reached_depth.as_usize() - self.stack.len(); + self.global_cache(tcx).insert( + input, + reached_depth, + final_entry.encountered_overflow, + final_entry.cycle_participants, + dep_node, + result, + ) + } + + result + } + + fn response_no_constraints( + tcx: TyCtxt<'tcx>, + goal: CanonicalInput<'tcx>, + certainty: Certainty, + ) -> QueryResult<'tcx> { + Ok(super::response_no_constraints_raw(tcx, goal.max_universe, goal.variables, certainty)) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs deleted file mode 100644 index 33513f6bd43..00000000000 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ /dev/null @@ -1,368 +0,0 @@ -use super::inspect; -use super::inspect::ProofTreeBuilder; -use super::SolverMode; -use rustc_data_structures::fx::FxHashMap; -use rustc_data_structures::fx::FxHashSet; -use rustc_index::Idx; -use rustc_index::IndexVec; -use rustc_middle::dep_graph::dep_kinds; -use rustc_middle::traits::solve::inspect::CacheHit; -use rustc_middle::traits::solve::CacheData; -use rustc_middle::traits::solve::{CanonicalInput, Certainty, EvaluationCache, QueryResult}; -use rustc_middle::ty::TyCtxt; -use rustc_session::Limit; -use std::collections::hash_map::Entry; - -rustc_index::newtype_index! { - pub struct StackDepth {} -} - -#[derive(Debug)] -struct StackEntry<'tcx> { - input: CanonicalInput<'tcx>, - available_depth: Limit, - // The maximum depth reached by this stack entry, only up-to date - // for the top of the stack and lazily updated for the rest. - reached_depth: StackDepth, - // In case of a cycle, the depth of the root. - cycle_root_depth: StackDepth, - - encountered_overflow: bool, - has_been_used: bool, - /// Starts out as `None` and gets set when rerunning this - /// goal in case we encounter a cycle. - provisional_result: Option>, - - /// We put only the root goal of a coinductive cycle into the global cache. - /// - /// If we were to use that result when later trying to prove another cycle - /// participant, we can end up with unstable query results. - /// - /// See tests/ui/new-solver/coinduction/incompleteness-unstable-result.rs for - /// an example of where this is needed. - cycle_participants: FxHashSet>, -} - -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*. - stack: IndexVec>, - stack_entries: FxHashMap, StackDepth>, -} - -impl<'tcx> SearchGraph<'tcx> { - pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> { - Self { - mode, - local_overflow_limit: tcx.recursion_limit().0.checked_ilog2().unwrap_or(0) as usize, - stack: Default::default(), - stack_entries: Default::default(), - } - } - - pub(super) fn solver_mode(&self) -> SolverMode { - 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) { - let reached_depth = self.stack.next_index().plus(additional_depth); - if let Some(last) = self.stack.raw.last_mut() { - last.reached_depth = last.reached_depth.max(reached_depth); - last.encountered_overflow |= encountered_overflow; - } - } - - /// Pops the highest goal from the stack, lazily updating the - /// the next goal in the stack. - /// - /// Directly popping from the stack instead of using this method - /// would cause us to not track overflow and recursion depth correctly. - fn pop_stack(&mut self) -> StackEntry<'tcx> { - let elem = self.stack.pop().unwrap(); - assert!(self.stack_entries.remove(&elem.input).is_some()); - if let Some(last) = self.stack.raw.last_mut() { - last.reached_depth = last.reached_depth.max(elem.reached_depth); - last.encountered_overflow |= elem.encountered_overflow; - } - elem - } - - /// The trait solver behavior is different for coherence - /// so we use a separate cache. Alternatively we could use - /// a single cache and share it between coherence and ordinary - /// trait solving. - pub(super) fn global_cache(&self, tcx: TyCtxt<'tcx>) -> &'tcx EvaluationCache<'tcx> { - match self.mode { - SolverMode::Normal => &tcx.new_solver_evaluation_cache, - SolverMode::Coherence => &tcx.new_solver_coherence_evaluation_cache, - } - } - - pub(super) fn is_empty(&self) -> bool { - self.stack.is_empty() - } - - /// Whether we're currently in a cycle. This should only be used - /// for debug assertions. - pub(super) fn in_cycle(&self) -> bool { - if let Some(stack_depth) = self.stack.last_index() { - // Either the current goal on the stack is the root of a cycle - // or it depends on a goal with a lower depth. - self.stack[stack_depth].has_been_used - || self.stack[stack_depth].cycle_root_depth != stack_depth - } else { - false - } - } - - /// Fetches whether the current goal encountered overflow. - /// - /// This should only be used for the check in `evaluate_goal`. - pub(super) fn encountered_overflow(&self) -> bool { - if let Some(last) = self.stack.raw.last() { last.encountered_overflow } else { false } - } - - /// Resets `encountered_overflow` of the current goal. - /// - /// This should only be used for the check in `evaluate_goal`. - pub(super) fn reset_encountered_overflow(&mut self, encountered_overflow: bool) -> bool { - if let Some(last) = self.stack.raw.last_mut() { - let prev = last.encountered_overflow; - last.encountered_overflow = encountered_overflow; - prev - } else { - false - } - } - - /// Returns the remaining depth allowed for nested goals. - /// - /// This is generally simply one less than the current depth. - /// However, if we encountered overflow, we significantly reduce - /// the remaining depth of all nested goals to prevent hangs - /// in case there is exponential blowup. - fn allowed_depth_for_nested( - tcx: TyCtxt<'tcx>, - stack: &IndexVec>, - ) -> Option { - if let Some(last) = stack.raw.last() { - if last.available_depth.0 == 0 { - return None; - } - - Some(if last.encountered_overflow { - Limit(last.available_depth.0 / 4) - } else { - Limit(last.available_depth.0 - 1) - }) - } else { - Some(tcx.recursion_limit()) - } - } - - /// 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(super) fn with_new_goal( - &mut self, - tcx: TyCtxt<'tcx>, - input: CanonicalInput<'tcx>, - inspect: &mut ProofTreeBuilder<'tcx>, - mut prove_goal: impl FnMut(&mut Self, &mut ProofTreeBuilder<'tcx>) -> QueryResult<'tcx>, - ) -> QueryResult<'tcx> { - // Check for overflow. - let Some(available_depth) = Self::allowed_depth_for_nested(tcx, &self.stack) else { - if let Some(last) = self.stack.raw.last_mut() { - last.encountered_overflow = true; - } - - inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::Overflow); - return Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); - }; - - // Try to fetch the goal from the global cache. - if inspect.use_global_cache() { - if let Some(CacheData { result, reached_depth, encountered_overflow }) = - self.global_cache(tcx).get( - tcx, - input, - |cycle_participants| { - self.stack.iter().any(|entry| cycle_participants.contains(&entry.input)) - }, - available_depth, - ) - { - inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( - CacheHit::Global, - )); - self.on_cache_hit(reached_depth, encountered_overflow); - return result; - } - } - - // Check whether we're in a cycle. - match self.stack_entries.entry(input) { - // No entry, we push this goal on the stack and try to prove it. - Entry::Vacant(v) => { - let depth = self.stack.next_index(); - let entry = StackEntry { - input, - available_depth, - reached_depth: depth, - cycle_root_depth: depth, - encountered_overflow: false, - has_been_used: false, - provisional_result: None, - cycle_participants: Default::default(), - }; - assert_eq!(self.stack.push(entry), depth); - v.insert(depth); - } - // We have a nested goal which relies on a goal `root` deeper in the stack. - // - // We first store that we may have to reprove `root` in case the provisional - // response is not equal to the final response. We also update the depth of all - // goals which recursively depend on our current goal to depend on `root` - // instead. - // - // Finally we can return either the provisional response for that goal if we have a - // coinductive cycle or an ambiguous result if the cycle is inductive. - Entry::Occupied(entry) => { - inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( - CacheHit::Provisional, - )); - - let stack_depth = *entry.get(); - debug!("encountered cycle with depth {stack_depth:?}"); - // We start by updating the root depth of all cycle participants, and - // add all cycle participants to the root. - let root_depth = self.stack[stack_depth].cycle_root_depth; - let (prev, participants) = self.stack.raw.split_at_mut(stack_depth.as_usize() + 1); - let root = &mut prev[root_depth.as_usize()]; - for entry in participants { - debug_assert!(entry.cycle_root_depth >= root_depth); - entry.cycle_root_depth = root_depth; - root.cycle_participants.insert(entry.input); - // FIXME(@lcnr): I believe that this line is needed as we could - // otherwise access a cache entry for the root of a cycle while - // computing the result for a cycle participant. This can result - // in unstable results due to incompleteness. - // - // However, a test for this would be an even more complex version of - // tests/ui/traits/new-solver/coinduction/incompleteness-unstable-result.rs. - // I did not bother to write such a test and we have no regression test - // for this. It would be good to have such a test :) - #[allow(rustc::potential_query_instability)] - root.cycle_participants.extend(entry.cycle_participants.drain()); - } - - // If we're in a cycle, we have to retry proving the cycle head - // until we reach a fixpoint. It is not enough to simply retry the - // `root` goal of this cycle. - // - // See tests/ui/traits/new-solver/cycles/fixpoint-rerun-all-cycle-heads.rs - // for an example. - self.stack[stack_depth].has_been_used = true; - return if let Some(result) = self.stack[stack_depth].provisional_result { - result - } else { - // If we don't have a provisional result yet we're in the first iteration, - // so we start with no constraints. - let is_coinductive = self.stack.raw[stack_depth.index()..] - .iter() - .all(|entry| entry.input.value.goal.predicate.is_coinductive(tcx)); - if is_coinductive { - Self::response_no_constraints(tcx, input, Certainty::Yes) - } else { - Self::response_no_constraints(tcx, input, Certainty::OVERFLOW) - } - }; - } - } - - // This is for global caching, so we properly track query dependencies. - // Everything that affects the `result` should be performed within this - // `with_anon_task` closure. - let ((final_entry, result), dep_node) = - tcx.dep_graph.with_anon_task(tcx, dep_kinds::TraitSelect, || { - // When we encounter a coinductive cycle, we have to fetch the - // result of that cycle while we are still computing it. Because - // 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() { - let result = prove_goal(self, inspect); - - // Check whether the current goal is the root of a cycle and whether - // we have to rerun because its provisional result differed from the - // final result. - let stack_entry = self.pop_stack(); - debug_assert_eq!(stack_entry.input, input); - if stack_entry.has_been_used - && stack_entry.provisional_result.map_or(true, |r| r != result) - { - // If so, update its provisional result and reevaluate it. - let depth = self.stack.push(StackEntry { - has_been_used: false, - provisional_result: Some(result), - ..stack_entry - }); - assert_eq!(self.stack_entries.insert(input, depth), None); - } else { - return (stack_entry, result); - } - } - - debug!("canonical cycle overflow"); - let current_entry = self.pop_stack(); - let result = Self::response_no_constraints(tcx, input, Certainty::OVERFLOW); - (current_entry, result) - }); - - // We're now done with this goal. In case this goal is involved in a larger cycle - // do not remove it from the provisional cache and update its provisional result. - // We only add the root of cycles to the global cache. - // - // It is not possible for any nested goal to depend on something deeper on the - // stack, as this would have also updated the depth of the current goal. - if final_entry.cycle_root_depth == self.stack.next_index() { - // When encountering a cycle, both inductive and coinductive, we only - // move the root into the global cache. We also store all other cycle - // participants involved. - // - // We disable the global cache entry of the root goal if a cycle - // participant is on the stack. This is necessary to prevent unstable - // results. See the comment of `StackEntry::cycle_participants` for - // more details. - let reached_depth = final_entry.reached_depth.as_usize() - self.stack.len(); - self.global_cache(tcx).insert( - input, - reached_depth, - final_entry.encountered_overflow, - final_entry.cycle_participants, - dep_node, - result, - ) - } - - result - } - - fn response_no_constraints( - tcx: TyCtxt<'tcx>, - goal: CanonicalInput<'tcx>, - certainty: Certainty, - ) -> QueryResult<'tcx> { - Ok(super::response_no_constraints_raw(tcx, goal.max_universe, goal.variables, certainty)) - } -} diff --git a/compiler/rustc_trait_selection/src/solve/weak_types.rs b/compiler/rustc_trait_selection/src/solve/weak_types.rs deleted file mode 100644 index 54de32cf618..00000000000 --- a/compiler/rustc_trait_selection/src/solve/weak_types.rs +++ /dev/null @@ -1,34 +0,0 @@ -//! Computes a normalizes-to (projection) goal for inherent associated types, -//! `#![feature(lazy_type_alias)]` and `#![feature(type_alias_impl_trait)]`. -//! -//! Since a weak alias is not ambiguous, this just computes the `type_of` of -//! the alias and registers the where-clauses of the type alias. -use rustc_middle::traits::solve::{Certainty, Goal, QueryResult}; -use rustc_middle::ty; - -use super::EvalCtxt; - -impl<'tcx> EvalCtxt<'_, 'tcx> { - pub(super) fn normalize_weak_type( - &mut self, - goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>, - ) -> QueryResult<'tcx> { - let tcx = self.tcx(); - let weak_ty = goal.predicate.projection_ty; - let expected = goal.predicate.term.ty().expect("no such thing as a const alias"); - - let actual = tcx.type_of(weak_ty.def_id).instantiate(tcx, weak_ty.args); - self.eq(goal.param_env, expected, actual)?; - - // Check where clauses - self.add_goals( - tcx.predicates_of(weak_ty.def_id) - .instantiate(tcx, weak_ty.args) - .predicates - .into_iter() - .map(|pred| goal.with(tcx, pred)), - ); - - self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) - } -} -- cgit 1.4.1-3-g733a5