diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
17 files changed, 1097 insertions, 791 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/alias_relate.rs b/compiler/rustc_trait_selection/src/solve/alias_relate.rs index 6b839d64b..f7031c5f4 100644 --- a/compiler/rustc_trait_selection/src/solve/alias_relate.rs +++ b/compiler/rustc_trait_selection/src/solve/alias_relate.rs @@ -125,7 +125,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { direction: ty::AliasRelationDirection, invert: Invert, ) -> QueryResult<'tcx> { - self.probe_candidate("normalizes-to").enter(|ecx| { + self.probe_misc_candidate("normalizes-to").enter(|ecx| { ecx.normalizes_to_inner(param_env, alias, other, direction, invert)?; ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) @@ -175,7 +175,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { alias_rhs: ty::AliasTy<'tcx>, direction: ty::AliasRelationDirection, ) -> QueryResult<'tcx> { - self.probe_candidate("args relate").enter(|ecx| { + self.probe_misc_candidate("args relate").enter(|ecx| { match direction { ty::AliasRelationDirection::Equate => { ecx.eq(param_env, alias_lhs, alias_rhs)?; @@ -196,7 +196,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { rhs: ty::Term<'tcx>, direction: ty::AliasRelationDirection, ) -> QueryResult<'tcx> { - self.probe_candidate("bidir normalizes-to").enter(|ecx| { + self.probe_misc_candidate("bidir normalizes-to").enter(|ecx| { ecx.normalizes_to_inner( param_env, lhs.to_alias_ty(ecx.tcx()).unwrap(), diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 36194f973..23d2c0c4e 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -5,8 +5,10 @@ use crate::traits::coherence; use rustc_hir::def_id::DefId; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::Reveal; -use rustc_middle::traits::solve::inspect::CandidateKind; -use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; +use rustc_middle::traits::solve::inspect::ProbeKind; +use rustc_middle::traits::solve::{ + CandidateSource, CanonicalResponse, Certainty, Goal, QueryResult, +}; use rustc_middle::traits::BuiltinImplSource; use rustc_middle::ty::fast_reject::{SimplifiedType, TreatParams}; use rustc_middle::ty::{self, Ty, TyCtxt}; @@ -27,66 +29,6 @@ pub(super) struct Candidate<'tcx> { pub(super) result: CanonicalResponse<'tcx>, } -/// Possible ways the given goal can be proven. -#[derive(Debug, Clone, Copy)] -pub(super) enum CandidateSource { - /// A user written impl. - /// - /// ## Examples - /// - /// ```rust - /// fn main() { - /// let x: Vec<u32> = Vec::new(); - /// // This uses the impl from the standard library to prove `Vec<T>: Clone`. - /// let y = x.clone(); - /// } - /// ``` - Impl(DefId), - /// A builtin impl generated by the compiler. When adding a new special - /// trait, try to use actual impls whenever possible. Builtin impls should - /// only be used in cases where the impl cannot be manually be written. - /// - /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`. - /// For a list of all traits with builtin impls, check out the - /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not - BuiltinImpl(BuiltinImplSource), - /// An assumption from the environment. - /// - /// More precisely we've used the `n-th` assumption in the `param_env`. - /// - /// ## Examples - /// - /// ```rust - /// fn is_clone<T: Clone>(x: T) -> (T, T) { - /// // This uses the assumption `T: Clone` from the `where`-bounds - /// // to prove `T: Clone`. - /// (x.clone(), x) - /// } - /// ``` - ParamEnv(usize), - /// If the self type is an alias type, e.g. an opaque type or a projection, - /// we know the bounds on that alias to hold even without knowing its concrete - /// underlying type. - /// - /// More precisely this candidate is using the `n-th` bound in the `item_bounds` of - /// the self type. - /// - /// ## Examples - /// - /// ```rust - /// trait Trait { - /// type Assoc: Clone; - /// } - /// - /// fn foo<T: Trait>(x: <T as Trait>::Assoc) { - /// // We prove `<T as Trait>::Assoc` by looking at the bounds on `Assoc` in - /// // in the trait definition. - /// let _y = x.clone(); - /// } - /// ``` - AliasBound, -} - /// Methods used to assemble candidates for either trait or projection goals. pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq + std::fmt::Display @@ -399,7 +341,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let tcx = self.tcx(); let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else { return }; - candidates.extend(self.probe(|_| CandidateKind::NormalizedSelfTyAssembly).enter(|ecx| { + candidates.extend(self.probe(|_| ProbeKind::NormalizedSelfTyAssembly).enter(|ecx| { if num_steps < ecx.local_overflow_limit() { let normalized_ty = ecx.next_ty_infer(); let normalizes_to_goal = goal.with( @@ -527,7 +469,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // FIXME: These should ideally not exist as a self type. It would be nice for // the builtin auto trait impls of generators to instead directly recurse // into the witness. - ty::GeneratorWitness(_) | ty::GeneratorWitnessMIR(_, _) => (), + ty::GeneratorWitness(..) => (), // These variants should not exist as a self type. ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) @@ -679,8 +621,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Dynamic(..) | ty::Closure(..) | ty::Generator(..) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) + | ty::GeneratorWitness(..) | ty::Never | ty::Tuple(_) | ty::Param(_) @@ -836,8 +777,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Alias(..) | ty::Closure(..) | ty::Generator(..) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) + | ty::GeneratorWitness(..) | ty::Never | ty::Tuple(_) | ty::Param(_) @@ -910,7 +850,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { SolverMode::Coherence => {} }; - let result = self.probe_candidate("coherence unknowable").enter(|ecx| { + let result = self.probe_misc_candidate("coherence unknowable").enter(|ecx| { let trait_ref = goal.predicate.trait_ref(tcx); #[derive(Debug)] diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs index c47767101..16f288045 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -14,6 +14,7 @@ use crate::solve::EvalCtxt; // // For types with an "existential" binder, i.e. generator witnesses, we also // instantiate the binder with placeholders eagerly. +#[instrument(level = "debug", skip(ecx), ret)] pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, @@ -61,9 +62,7 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( Ok(vec![generator_args.tupled_upvars_ty(), generator_args.witness()]) } - ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), - - ty::GeneratorWitnessMIR(def_id, args) => Ok(ecx + ty::GeneratorWitness(def_id, args) => Ok(ecx .tcx() .generator_hidden_types(def_id) .map(|bty| { @@ -96,8 +95,7 @@ pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>( let mut counter = 0; let ty = tcx.fold_regions(ty, |r, current_depth| match r.kind() { ty::ReErased => { - let br = - ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) }; + let br = ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon }; counter += 1; ty::Region::new_late_bound(tcx, current_depth, br) } @@ -105,11 +103,12 @@ pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>( r => bug!("unexpected region: {r:?}"), }); let bound_vars = tcx.mk_bound_variable_kinds_from_iter( - (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))), + (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon)), ); ty::Binder::bind_with_vars(ty, bound_vars) } +#[instrument(level = "debug", skip(ecx), ret)] pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, @@ -127,7 +126,6 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( | ty::Ref(..) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Array(..) | ty::Closure(..) | ty::Never @@ -156,6 +154,7 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( } } +#[instrument(level = "debug", skip(ecx), ret)] pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, @@ -204,9 +203,7 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( } } - ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), - - ty::GeneratorWitnessMIR(def_id, args) => Ok(ecx + ty::GeneratorWitness(def_id, args) => Ok(ecx .tcx() .generator_hidden_types(def_id) .map(|bty| { @@ -282,8 +279,7 @@ pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( | ty::Ref(_, _, _) | ty::Dynamic(_, _, _) | ty::Generator(_, _, _) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) + | ty::GeneratorWitness(..) | ty::Never | ty::Tuple(_) | ty::Alias(_, _) @@ -354,6 +350,12 @@ pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( // FIXME(associated_const_equality): Also add associated consts to // the requirements here. if item.kind == ty::AssocKind::Type { + // associated types that require `Self: Sized` do not show up in the built-in + // implementation of `Trait for dyn Trait`, and can be dropped here. + if tcx.generics_require_sized_self(item.def_id) { + continue; + } + requirements .extend(tcx.item_bounds(item.def_id).iter_instantiated(tcx, trait_ref.args)); } diff --git a/compiler/rustc_trait_selection/src/solve/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs index a9d182abf..aa92b924e 100644 --- a/compiler/rustc_trait_selection/src/solve/canonicalize.rs +++ b/compiler/rustc_trait_selection/src/solve/canonicalize.rs @@ -269,7 +269,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { self.primitive_var_infos.push(CanonicalVarInfo { kind }); var }); - let br = ty::BoundRegion { var, kind: BrAnon(None) }; + let br = ty::BoundRegion { var, kind: BrAnon }; ty::Region::new_late_bound(self.interner(), self.binder_index, br) } @@ -330,8 +330,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { | ty::Dynamic(_, _, _) | ty::Closure(_, _) | ty::Generator(_, _, _) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) + | ty::GeneratorWitness(..) | ty::Never | ty::Tuple(_) | ty::Alias(_, _) @@ -365,6 +364,17 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { // FIXME: we should fold this ty eventually CanonicalVarKind::Const(ui, c.ty()) } + ty::ConstKind::Infer(ty::InferConst::EffectVar(vid)) => { + assert_eq!( + self.infcx.root_effect_var(vid), + vid, + "effect var should have been resolved" + ); + let None = self.infcx.probe_effect_var(vid) else { + bug!("effect var should have been resolved"); + }; + CanonicalVarKind::Effect + } ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { bug!("fresh var during canonicalization: {c:?}") } diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs index 5c2cbe399..066129d8e 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -28,8 +28,8 @@ use std::ops::ControlFlow; use crate::traits::vtable::{count_own_vtable_entries, prepare_vtable_segments, VtblSegment}; use super::inspect::ProofTreeBuilder; -use super::search_graph; use super::SolverMode; +use super::{search_graph, GoalEvaluationKind}; use super::{search_graph::SearchGraph, Goal}; pub use select::InferCtxtSelectExt; @@ -85,7 +85,7 @@ pub struct EvalCtxt<'a, 'tcx> { // evaluation code. tainted: Result<(), NoSolution>, - inspect: ProofTreeBuilder<'tcx>, + pub(super) inspect: ProofTreeBuilder<'tcx>, } #[derive(Debug, Clone)] @@ -164,7 +164,7 @@ impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { Option<inspect::GoalEvaluation<'tcx>>, ) { EvalCtxt::enter_root(self, generate_proof_tree, |ecx| { - ecx.evaluate_goal(IsNormalizesToHack::No, goal) + ecx.evaluate_goal(GoalEvaluationKind::Root, goal) }) } } @@ -237,7 +237,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { tcx: TyCtxt<'tcx>, search_graph: &'a mut search_graph::SearchGraph<'tcx>, canonical_input: CanonicalInput<'tcx>, - goal_evaluation: &mut ProofTreeBuilder<'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() { @@ -260,7 +260,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { search_graph, nested_goals: NestedGoals::new(), tainted: Ok(()), - inspect: goal_evaluation.new_goal_evaluation_step(input), + inspect: canonical_goal_evaluation.new_goal_evaluation_step(input), }; for &(key, ty) in &input.predefined_opaques_in_body.opaque_types { @@ -274,7 +274,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let result = f(&mut ecx, input.goal); - goal_evaluation.goal_evaluation_step(ecx.inspect); + 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 @@ -302,24 +302,25 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { tcx: TyCtxt<'tcx>, search_graph: &'a mut search_graph::SearchGraph<'tcx>, canonical_input: CanonicalInput<'tcx>, - mut goal_evaluation: &mut ProofTreeBuilder<'tcx>, + goal_evaluation: &mut ProofTreeBuilder<'tcx>, ) -> QueryResult<'tcx> { - goal_evaluation.canonicalized_goal(canonical_input); + 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`. - ensure_sufficient_stack(|| { + let result = ensure_sufficient_stack(|| { search_graph.with_new_goal( tcx, canonical_input, - goal_evaluation, - |search_graph, goal_evaluation| { + &mut canonical_goal_evaluation, + |search_graph, canonical_goal_evaluation| { EvalCtxt::enter_canonical( tcx, search_graph, canonical_input, - goal_evaluation, + canonical_goal_evaluation, |ecx, goal| { let result = ecx.compute_goal(goal); ecx.inspect.query_result(result); @@ -328,18 +329,23 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { ) }, ) - }) + }); + + 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, - is_normalizes_to_hack: IsNormalizesToHack, + goal_evaluation_kind: GoalEvaluationKind, goal: Goal<'tcx, ty::Predicate<'tcx>>, ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { let (orig_values, canonical_goal) = self.canonicalize_goal(goal); - let mut goal_evaluation = self.inspect.new_goal_evaluation(goal, is_normalizes_to_hack); + 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(), @@ -347,7 +353,6 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { canonical_goal, &mut goal_evaluation, ); - goal_evaluation.query_result(canonical_response); let canonical_response = match canonical_response { Err(e) => { self.inspect.goal_evaluation(goal_evaluation); @@ -385,7 +390,10 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { // solver cycle. if cfg!(debug_assertions) && has_changed - && is_normalizes_to_hack == IsNormalizesToHack::No + && !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 @@ -537,7 +545,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { /// Iterate over all added goals: returning `Ok(Some(_))` in case we can stop rerunning. /// - /// Goals for the next step get directly added the the nested goals of the `EvalCtxt`. + /// Goals for the next step get directly added to the nested goals of the `EvalCtxt`. fn evaluate_added_goals_step(&mut self) -> Result<Option<Certainty>, NoSolution> { let tcx = self.tcx(); let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); @@ -557,9 +565,11 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { }, ); - let (_, certainty, instantiate_goals) = - self.evaluate_goal(IsNormalizesToHack::Yes, unconstrained_goal)?; - self.add_goals(instantiate_goals); + 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 @@ -592,9 +602,11 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { } for goal in goals.goals.drain(..) { - let (has_changed, certainty, instantiate_goals) = - self.evaluate_goal(IsNormalizesToHack::No, goal)?; - self.add_goals(instantiate_goals); + 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; } @@ -602,7 +614,7 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { match certainty { Certainty::Yes => {} Certainty::Maybe(_) => { - self.add_goal(goal); + self.nested_goals.goals.push(goal); unchanged_certainty = unchanged_certainty.map(|c| c.unify_with(certainty)); } } @@ -916,7 +928,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if candidate_key.def_id != key.def_id { continue; } - values.extend(self.probe_candidate("opaque type storage").enter(|ecx| { + 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)?; } @@ -945,8 +957,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { 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, + Err(ErrorHandled::Reported(e, _)) => { + Some(ty::Const::new_error(self.tcx(), e.into(), ty)) + } + Err(ErrorHandled::TooGeneric(_)) => None, } } diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs index 523841951..b3f9218d7 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs @@ -10,17 +10,21 @@ //! [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html use super::{CanonicalInput, Certainty, EvalCtxt, Goal}; use crate::solve::canonicalize::{CanonicalizeMode, Canonicalizer}; -use crate::solve::{response_no_constraints_raw, CanonicalResponse, QueryResult, Response}; +use crate::solve::{ + inspect, response_no_constraints_raw, CanonicalResponse, QueryResult, Response, +}; use rustc_data_structures::fx::FxHashSet; use rustc_index::IndexVec; use rustc_infer::infer::canonical::query_response::make_query_region_constraints; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::canonical::{CanonicalExt, QueryRegionConstraints}; -use rustc_infer::infer::InferCtxt; +use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, InferOk}; +use rustc_middle::infer::canonical::Canonical; use rustc_middle::traits::query::NoSolution; use rustc_middle::traits::solve::{ ExternalConstraintsData, MaybeCause, PredefinedOpaquesData, QueryInput, }; +use rustc_middle::traits::ObligationCause; use rustc_middle::ty::{ self, BoundVar, GenericArgKind, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, @@ -29,6 +33,22 @@ use rustc_span::DUMMY_SP; use std::iter; use std::ops::Deref; +trait ResponseT<'tcx> { + fn var_values(&self) -> CanonicalVarValues<'tcx>; +} + +impl<'tcx> ResponseT<'tcx> for Response<'tcx> { + fn var_values(&self) -> CanonicalVarValues<'tcx> { + self.var_values + } +} + +impl<'tcx, T> ResponseT<'tcx> for inspect::State<'tcx, T> { + fn var_values(&self) -> CanonicalVarValues<'tcx> { + self.var_values + } +} + impl<'tcx> EvalCtxt<'_, 'tcx> { /// Canonicalizes the goal remembering the original values /// for each bound variable. @@ -188,12 +208,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { original_values: Vec<ty::GenericArg<'tcx>>, response: CanonicalResponse<'tcx>, ) -> Result<(Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { - let substitution = self.compute_query_response_substitution(&original_values, &response); + let substitution = + Self::compute_query_response_substitution(self.infcx, &original_values, &response); let Response { var_values, external_constraints, certainty } = response.substitute(self.tcx(), &substitution); - let nested_goals = self.unify_query_var_values(param_env, &original_values, var_values)?; + let nested_goals = + Self::unify_query_var_values(self.infcx, param_env, &original_values, var_values)?; let ExternalConstraintsData { region_constraints, opaque_types } = external_constraints.deref(); @@ -206,21 +228,21 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { /// This returns the substitutions to instantiate the bound variables of /// the canonical response. This depends on the `original_values` for the /// bound variables. - fn compute_query_response_substitution( - &self, + fn compute_query_response_substitution<T: ResponseT<'tcx>>( + infcx: &InferCtxt<'tcx>, original_values: &[ty::GenericArg<'tcx>], - response: &CanonicalResponse<'tcx>, + response: &Canonical<'tcx, T>, ) -> CanonicalVarValues<'tcx> { // FIXME: Longterm canonical queries should deal with all placeholders // created inside of the query directly instead of returning them to the // caller. - let prev_universe = self.infcx.universe(); + let prev_universe = infcx.universe(); let universes_created_in_query = response.max_universe.index(); for _ in 0..universes_created_in_query { - self.infcx.create_next_universe(); + infcx.create_next_universe(); } - let var_values = response.value.var_values; + let var_values = response.value.var_values(); assert_eq!(original_values.len(), var_values.len()); // If the query did not make progress with constraining inference variables, @@ -254,13 +276,13 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - let var_values = self.tcx().mk_args_from_iter(response.variables.iter().enumerate().map( + let var_values = infcx.tcx.mk_args_from_iter(response.variables.iter().enumerate().map( |(index, info)| { if info.universe() != ty::UniverseIndex::ROOT { // A variable from inside a binder of the query. While ideally these shouldn't // exist at all (see the FIXME at the start of this method), we have to deal with // them for now. - self.infcx.instantiate_canonical_var(DUMMY_SP, info, |idx| { + infcx.instantiate_canonical_var(DUMMY_SP, info, |idx| { ty::UniverseIndex::from(prev_universe.index() + idx.index()) }) } else if info.is_existential() { @@ -274,7 +296,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if let Some(v) = opt_values[BoundVar::from_usize(index)] { v } else { - self.infcx.instantiate_canonical_var(DUMMY_SP, info, |_| prev_universe) + infcx.instantiate_canonical_var(DUMMY_SP, info, |_| prev_universe) } } else { // For placeholders which were already part of the input, we simply map this @@ -287,9 +309,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { CanonicalVarValues { var_values } } - #[instrument(level = "debug", skip(self, param_env), ret)] + #[instrument(level = "debug", skip(infcx, param_env), ret)] fn unify_query_var_values( - &self, + infcx: &InferCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, original_values: &[ty::GenericArg<'tcx>], var_values: CanonicalVarValues<'tcx>, @@ -298,7 +320,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let mut nested_goals = vec![]; for (&orig, response) in iter::zip(original_values, var_values.var_values) { - nested_goals.extend(self.eq_and_get_goals(param_env, orig, response)?); + nested_goals.extend( + infcx + .at(&ObligationCause::dummy(), param_env) + .eq(DefineOpaqueTypes::No, orig, response) + .map(|InferOk { value: (), obligations }| { + obligations.into_iter().map(|o| Goal::from(o)) + }) + .map_err(|e| { + debug!(?e, "failed to equate"); + NoSolution + })?, + ); } Ok(nested_goals) @@ -382,6 +415,17 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for EagerResolver<'_, 'tcx> { } } } + ty::ConstKind::Infer(ty::InferConst::EffectVar(vid)) => { + debug_assert_eq!(c.ty(), self.infcx.tcx.types.bool); + match self.infcx.probe_effect_var(vid) { + Some(c) => c.as_const(self.infcx.tcx), + None => ty::Const::new_infer( + self.infcx.tcx, + ty::InferConst::EffectVar(self.infcx.root_effect_var(vid)), + self.infcx.tcx.types.bool, + ), + } + } _ => { if c.has_infer() { c.super_fold_with(self) @@ -392,3 +436,35 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for EagerResolver<'_, 'tcx> { } } } + +impl<'tcx> inspect::ProofTreeBuilder<'tcx> { + pub fn make_canonical_state<T: TypeFoldable<TyCtxt<'tcx>>>( + ecx: &EvalCtxt<'_, 'tcx>, + data: T, + ) -> inspect::CanonicalState<'tcx, T> { + let state = inspect::State { var_values: ecx.var_values, data }; + let state = state.fold_with(&mut EagerResolver { infcx: ecx.infcx }); + Canonicalizer::canonicalize( + ecx.infcx, + CanonicalizeMode::Response { max_input_universe: ecx.max_input_universe }, + &mut vec![], + state, + ) + } + + pub fn instantiate_canonical_state<T: TypeFoldable<TyCtxt<'tcx>>>( + infcx: &InferCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &[ty::GenericArg<'tcx>], + state: inspect::CanonicalState<'tcx, T>, + ) -> Result<(Vec<Goal<'tcx, ty::Predicate<'tcx>>>, T), NoSolution> { + let substitution = + EvalCtxt::compute_query_response_substitution(infcx, original_values, &state); + + let inspect::State { var_values, data } = state.substitute(infcx.tcx, &substitution); + + let nested_goals = + EvalCtxt::unify_query_var_values(infcx, param_env, original_values, var_values)?; + Ok((nested_goals, data)) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs index 317c43baf..6087b9167 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/probe.rs @@ -1,5 +1,5 @@ use super::EvalCtxt; -use rustc_middle::traits::solve::{inspect, QueryResult}; +use rustc_middle::traits::solve::{inspect, CandidateSource, QueryResult}; use std::marker::PhantomData; pub(in crate::solve) struct ProbeCtxt<'me, 'a, 'tcx, F, T> { @@ -10,7 +10,7 @@ pub(in crate::solve) struct ProbeCtxt<'me, 'a, 'tcx, F, T> { impl<'tcx, F, T> ProbeCtxt<'_, '_, 'tcx, F, T> where - F: FnOnce(&T) -> inspect::CandidateKind<'tcx>, + F: FnOnce(&T) -> inspect::ProbeKind<'tcx>, { pub(in crate::solve) fn enter(self, f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T) -> T { let ProbeCtxt { ecx: outer_ecx, probe_kind, _result } = self; @@ -24,13 +24,13 @@ where search_graph: outer_ecx.search_graph, nested_goals: outer_ecx.nested_goals.clone(), tainted: outer_ecx.tainted, - inspect: outer_ecx.inspect.new_goal_candidate(), + inspect: outer_ecx.inspect.new_probe(), }; let r = nested_ecx.infcx.probe(|_| f(&mut nested_ecx)); if !outer_ecx.inspect.is_noop() { - let cand_kind = probe_kind(&r); - nested_ecx.inspect.candidate_kind(cand_kind); - outer_ecx.inspect.goal_candidate(nested_ecx.inspect); + let probe_kind = probe_kind(&r); + nested_ecx.inspect.probe_kind(probe_kind); + outer_ecx.inspect.finish_probe(nested_ecx.inspect); } r } @@ -41,25 +41,45 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { /// as expensive as necessary to output the desired information. pub(in crate::solve) fn probe<F, T>(&mut self, probe_kind: F) -> ProbeCtxt<'_, 'a, 'tcx, F, T> where - F: FnOnce(&T) -> inspect::CandidateKind<'tcx>, + F: FnOnce(&T) -> inspect::ProbeKind<'tcx>, { ProbeCtxt { ecx: self, probe_kind, _result: PhantomData } } - pub(in crate::solve) fn probe_candidate( + pub(in crate::solve) fn probe_misc_candidate( &mut self, name: &'static str, ) -> ProbeCtxt< '_, 'a, 'tcx, - impl FnOnce(&QueryResult<'tcx>) -> inspect::CandidateKind<'tcx>, + impl FnOnce(&QueryResult<'tcx>) -> inspect::ProbeKind<'tcx>, QueryResult<'tcx>, > { ProbeCtxt { ecx: self, - probe_kind: move |result: &QueryResult<'tcx>| inspect::CandidateKind::Candidate { - name: name.to_string(), + probe_kind: move |result: &QueryResult<'tcx>| inspect::ProbeKind::MiscCandidate { + name, + result: *result, + }, + _result: PhantomData, + } + } + + pub(in crate::solve) fn probe_trait_candidate( + &mut self, + source: CandidateSource, + ) -> ProbeCtxt< + '_, + 'a, + 'tcx, + impl FnOnce(&QueryResult<'tcx>) -> inspect::ProbeKind<'tcx>, + QueryResult<'tcx>, + > { + ProbeCtxt { + ecx: self, + probe_kind: move |result: &QueryResult<'tcx>| inspect::ProbeKind::TraitCandidate { + source, result: *result, }, _result: PhantomData, diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs index 42d7a587c..315df06be 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/select.rs @@ -4,14 +4,14 @@ use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt}; use rustc_infer::traits::{ Obligation, PolyTraitObligation, PredicateObligation, Selection, SelectionResult, TraitEngine, }; -use rustc_middle::traits::solve::{CanonicalInput, Certainty, Goal}; +use rustc_middle::traits::solve::{CandidateSource, CanonicalInput, Certainty, Goal}; use rustc_middle::traits::{ BuiltinImplSource, ImplSource, ImplSourceUserDefinedData, ObligationCause, SelectionError, }; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_span::DUMMY_SP; -use crate::solve::assembly::{Candidate, CandidateSource}; +use crate::solve::assembly::Candidate; use crate::solve::eval_ctxt::{EvalCtxt, GenerateProofTree}; use crate::solve::inspect::ProofTreeBuilder; use crate::traits::StructurallyNormalizeExt; diff --git a/compiler/rustc_trait_selection/src/solve/inspect.rs b/compiler/rustc_trait_selection/src/solve/inspect.rs deleted file mode 100644 index cda683963..000000000 --- a/compiler/rustc_trait_selection/src/solve/inspect.rs +++ /dev/null @@ -1,428 +0,0 @@ -use rustc_middle::traits::query::NoSolution; -use rustc_middle::traits::solve::inspect::{self, CacheHit, CandidateKind}; -use rustc_middle::traits::solve::{ - CanonicalInput, Certainty, Goal, IsNormalizesToHack, QueryInput, QueryResult, -}; -use rustc_middle::ty::{self, TyCtxt}; -use rustc_session::config::DumpSolverProofTree; - -use super::eval_ctxt::UseGlobalCache; -use super::GenerateProofTree; - -#[derive(Eq, PartialEq, Debug, Hash, HashStable)] -pub struct WipGoalEvaluation<'tcx> { - pub uncanonicalized_goal: Goal<'tcx, ty::Predicate<'tcx>>, - pub canonicalized_goal: Option<CanonicalInput<'tcx>>, - - pub evaluation_steps: Vec<WipGoalEvaluationStep<'tcx>>, - - pub cache_hit: Option<CacheHit>, - pub is_normalizes_to_hack: IsNormalizesToHack, - pub returned_goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, - - pub result: Option<QueryResult<'tcx>>, -} - -impl<'tcx> WipGoalEvaluation<'tcx> { - pub fn finalize(self) -> inspect::GoalEvaluation<'tcx> { - inspect::GoalEvaluation { - uncanonicalized_goal: self.uncanonicalized_goal, - canonicalized_goal: self.canonicalized_goal.unwrap(), - kind: match self.cache_hit { - Some(hit) => inspect::GoalEvaluationKind::CacheHit(hit), - None => inspect::GoalEvaluationKind::Uncached { - revisions: self - .evaluation_steps - .into_iter() - .map(WipGoalEvaluationStep::finalize) - .collect(), - }, - }, - is_normalizes_to_hack: self.is_normalizes_to_hack, - returned_goals: self.returned_goals, - result: self.result.unwrap(), - } - } -} - -#[derive(Eq, PartialEq, Debug, Hash, HashStable)] -pub struct WipAddedGoalsEvaluation<'tcx> { - pub evaluations: Vec<Vec<WipGoalEvaluation<'tcx>>>, - pub result: Option<Result<Certainty, NoSolution>>, -} - -impl<'tcx> WipAddedGoalsEvaluation<'tcx> { - pub fn finalize(self) -> inspect::AddedGoalsEvaluation<'tcx> { - inspect::AddedGoalsEvaluation { - evaluations: self - .evaluations - .into_iter() - .map(|evaluations| { - evaluations.into_iter().map(WipGoalEvaluation::finalize).collect() - }) - .collect(), - result: self.result.unwrap(), - } - } -} - -#[derive(Eq, PartialEq, Debug, Hash, HashStable)] -pub struct WipGoalEvaluationStep<'tcx> { - pub instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>, - - pub nested_goal_evaluations: Vec<WipAddedGoalsEvaluation<'tcx>>, - pub candidates: Vec<WipGoalCandidate<'tcx>>, - - pub result: Option<QueryResult<'tcx>>, -} - -impl<'tcx> WipGoalEvaluationStep<'tcx> { - pub fn finalize(self) -> inspect::GoalEvaluationStep<'tcx> { - inspect::GoalEvaluationStep { - instantiated_goal: self.instantiated_goal, - nested_goal_evaluations: self - .nested_goal_evaluations - .into_iter() - .map(WipAddedGoalsEvaluation::finalize) - .collect(), - candidates: self.candidates.into_iter().map(WipGoalCandidate::finalize).collect(), - result: self.result.unwrap(), - } - } -} - -#[derive(Eq, PartialEq, Debug, Hash, HashStable)] -pub struct WipGoalCandidate<'tcx> { - pub nested_goal_evaluations: Vec<WipAddedGoalsEvaluation<'tcx>>, - pub candidates: Vec<WipGoalCandidate<'tcx>>, - pub kind: Option<CandidateKind<'tcx>>, -} - -impl<'tcx> WipGoalCandidate<'tcx> { - pub fn finalize(self) -> inspect::GoalCandidate<'tcx> { - inspect::GoalCandidate { - nested_goal_evaluations: self - .nested_goal_evaluations - .into_iter() - .map(WipAddedGoalsEvaluation::finalize) - .collect(), - candidates: self.candidates.into_iter().map(WipGoalCandidate::finalize).collect(), - kind: self.kind.unwrap(), - } - } -} - -#[derive(Debug)] -pub enum DebugSolver<'tcx> { - Root, - GoalEvaluation(WipGoalEvaluation<'tcx>), - AddedGoalsEvaluation(WipAddedGoalsEvaluation<'tcx>), - GoalEvaluationStep(WipGoalEvaluationStep<'tcx>), - GoalCandidate(WipGoalCandidate<'tcx>), -} - -impl<'tcx> From<WipGoalEvaluation<'tcx>> for DebugSolver<'tcx> { - fn from(g: WipGoalEvaluation<'tcx>) -> DebugSolver<'tcx> { - DebugSolver::GoalEvaluation(g) - } -} - -impl<'tcx> From<WipAddedGoalsEvaluation<'tcx>> for DebugSolver<'tcx> { - fn from(g: WipAddedGoalsEvaluation<'tcx>) -> DebugSolver<'tcx> { - DebugSolver::AddedGoalsEvaluation(g) - } -} - -impl<'tcx> From<WipGoalEvaluationStep<'tcx>> for DebugSolver<'tcx> { - fn from(g: WipGoalEvaluationStep<'tcx>) -> DebugSolver<'tcx> { - DebugSolver::GoalEvaluationStep(g) - } -} - -impl<'tcx> From<WipGoalCandidate<'tcx>> for DebugSolver<'tcx> { - fn from(g: WipGoalCandidate<'tcx>) -> DebugSolver<'tcx> { - DebugSolver::GoalCandidate(g) - } -} - -pub struct ProofTreeBuilder<'tcx> { - state: Option<Box<BuilderData<'tcx>>>, -} - -struct BuilderData<'tcx> { - tree: DebugSolver<'tcx>, - use_global_cache: UseGlobalCache, -} - -impl<'tcx> ProofTreeBuilder<'tcx> { - fn new( - state: impl Into<DebugSolver<'tcx>>, - use_global_cache: UseGlobalCache, - ) -> ProofTreeBuilder<'tcx> { - ProofTreeBuilder { - state: Some(Box::new(BuilderData { tree: state.into(), use_global_cache })), - } - } - - fn nested(&self, state: impl Into<DebugSolver<'tcx>>) -> Self { - match &self.state { - Some(prev_state) => Self { - state: Some(Box::new(BuilderData { - tree: state.into(), - use_global_cache: prev_state.use_global_cache, - })), - }, - None => Self { state: None }, - } - } - - fn as_mut(&mut self) -> Option<&mut DebugSolver<'tcx>> { - self.state.as_mut().map(|boxed| &mut boxed.tree) - } - - pub fn finalize(self) -> Option<inspect::GoalEvaluation<'tcx>> { - match self.state?.tree { - DebugSolver::GoalEvaluation(wip_goal_evaluation) => { - Some(wip_goal_evaluation.finalize()) - } - root => unreachable!("unexpected proof tree builder root node: {:?}", root), - } - } - - pub fn use_global_cache(&self) -> bool { - self.state - .as_ref() - .map(|state| matches!(state.use_global_cache, UseGlobalCache::Yes)) - .unwrap_or(true) - } - - pub fn new_maybe_root( - tcx: TyCtxt<'tcx>, - generate_proof_tree: GenerateProofTree, - ) -> ProofTreeBuilder<'tcx> { - match generate_proof_tree { - GenerateProofTree::Never => ProofTreeBuilder::new_noop(), - GenerateProofTree::IfEnabled => { - let opts = &tcx.sess.opts.unstable_opts; - match opts.dump_solver_proof_tree { - DumpSolverProofTree::Always => { - let use_cache = opts.dump_solver_proof_tree_use_cache.unwrap_or(true); - ProofTreeBuilder::new_root(UseGlobalCache::from_bool(use_cache)) - } - // `OnError` is handled by reevaluating goals in error - // reporting with `GenerateProofTree::Yes`. - DumpSolverProofTree::OnError | DumpSolverProofTree::Never => { - ProofTreeBuilder::new_noop() - } - } - } - GenerateProofTree::Yes(use_cache) => ProofTreeBuilder::new_root(use_cache), - } - } - - pub fn new_root(use_global_cache: UseGlobalCache) -> ProofTreeBuilder<'tcx> { - ProofTreeBuilder::new(DebugSolver::Root, use_global_cache) - } - - pub fn new_noop() -> ProofTreeBuilder<'tcx> { - ProofTreeBuilder { state: None } - } - - pub fn is_noop(&self) -> bool { - self.state.is_none() - } - - pub fn new_goal_evaluation( - &mut self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - is_normalizes_to_hack: IsNormalizesToHack, - ) -> ProofTreeBuilder<'tcx> { - if self.state.is_none() { - return ProofTreeBuilder { state: None }; - } - - self.nested(WipGoalEvaluation { - uncanonicalized_goal: goal, - canonicalized_goal: None, - evaluation_steps: vec![], - is_normalizes_to_hack, - cache_hit: None, - returned_goals: vec![], - result: None, - }) - } - - pub fn canonicalized_goal(&mut self, canonical_goal: CanonicalInput<'tcx>) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::GoalEvaluation(goal_evaluation) => { - assert_eq!(goal_evaluation.canonicalized_goal.replace(canonical_goal), None); - } - _ => unreachable!(), - } - } - } - - pub fn cache_hit(&mut self, cache_hit: CacheHit) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::GoalEvaluation(goal_evaluation) => { - assert_eq!(goal_evaluation.cache_hit.replace(cache_hit), None); - } - _ => unreachable!(), - }; - } - } - - pub fn returned_goals(&mut self, goals: &[Goal<'tcx, ty::Predicate<'tcx>>]) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::GoalEvaluation(evaluation) => { - assert!(evaluation.returned_goals.is_empty()); - evaluation.returned_goals.extend(goals); - } - _ => unreachable!(), - } - } - } - pub fn goal_evaluation(&mut self, goal_evaluation: ProofTreeBuilder<'tcx>) { - if let Some(this) = self.as_mut() { - match (this, goal_evaluation.state.unwrap().tree) { - ( - DebugSolver::AddedGoalsEvaluation(WipAddedGoalsEvaluation { - evaluations, .. - }), - DebugSolver::GoalEvaluation(goal_evaluation), - ) => evaluations.last_mut().unwrap().push(goal_evaluation), - (this @ DebugSolver::Root, goal_evaluation) => *this = goal_evaluation, - _ => unreachable!(), - } - } - } - - pub fn new_goal_evaluation_step( - &mut self, - instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>, - ) -> ProofTreeBuilder<'tcx> { - if self.state.is_none() { - return ProofTreeBuilder { state: None }; - } - - self.nested(WipGoalEvaluationStep { - instantiated_goal, - nested_goal_evaluations: vec![], - candidates: vec![], - result: None, - }) - } - pub fn goal_evaluation_step(&mut self, goal_eval_step: ProofTreeBuilder<'tcx>) { - if let Some(this) = self.as_mut() { - match (this, goal_eval_step.state.unwrap().tree) { - (DebugSolver::GoalEvaluation(goal_eval), DebugSolver::GoalEvaluationStep(step)) => { - goal_eval.evaluation_steps.push(step); - } - _ => unreachable!(), - } - } - } - - pub fn new_goal_candidate(&mut self) -> ProofTreeBuilder<'tcx> { - if self.state.is_none() { - return ProofTreeBuilder { state: None }; - } - - self.nested(WipGoalCandidate { - nested_goal_evaluations: vec![], - candidates: vec![], - kind: None, - }) - } - - pub fn candidate_kind(&mut self, candidate_kind: CandidateKind<'tcx>) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::GoalCandidate(this) => { - assert_eq!(this.kind.replace(candidate_kind), None) - } - _ => unreachable!(), - } - } - } - - pub fn goal_candidate(&mut self, candidate: ProofTreeBuilder<'tcx>) { - if let Some(this) = self.as_mut() { - match (this, candidate.state.unwrap().tree) { - ( - DebugSolver::GoalCandidate(WipGoalCandidate { candidates, .. }) - | DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { candidates, .. }), - DebugSolver::GoalCandidate(candidate), - ) => candidates.push(candidate), - _ => unreachable!(), - } - } - } - - pub fn new_evaluate_added_goals(&mut self) -> ProofTreeBuilder<'tcx> { - if self.state.is_none() { - return ProofTreeBuilder { state: None }; - } - - self.nested(WipAddedGoalsEvaluation { evaluations: vec![], result: None }) - } - - pub fn evaluate_added_goals_loop_start(&mut self) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::AddedGoalsEvaluation(this) => { - this.evaluations.push(vec![]); - } - _ => unreachable!(), - } - } - } - - pub fn eval_added_goals_result(&mut self, result: Result<Certainty, NoSolution>) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::AddedGoalsEvaluation(this) => { - assert_eq!(this.result.replace(result), None); - } - _ => unreachable!(), - } - } - } - - pub fn added_goals_evaluation(&mut self, goals_evaluation: ProofTreeBuilder<'tcx>) { - if let Some(this) = self.as_mut() { - match (this, goals_evaluation.state.unwrap().tree) { - ( - DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { - nested_goal_evaluations, - .. - }) - | DebugSolver::GoalCandidate(WipGoalCandidate { - nested_goal_evaluations, .. - }), - DebugSolver::AddedGoalsEvaluation(added_goals_evaluation), - ) => nested_goal_evaluations.push(added_goals_evaluation), - _ => unreachable!(), - } - } - } - - pub fn query_result(&mut self, result: QueryResult<'tcx>) { - if let Some(this) = self.as_mut() { - match this { - DebugSolver::GoalEvaluation(goal_evaluation) => { - assert_eq!(goal_evaluation.result.replace(result), None); - } - DebugSolver::GoalEvaluationStep(evaluation_step) => { - assert_eq!(evaluation_step.result.replace(result), None); - } - DebugSolver::Root - | DebugSolver::AddedGoalsEvaluation(_) - | DebugSolver::GoalCandidate(_) => unreachable!(), - } - } - } -} diff --git a/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs new file mode 100644 index 000000000..15c8d9e5b --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/inspect/analyse.rs @@ -0,0 +1,235 @@ +/// An infrastructure to mechanically analyse proof trees. +/// +/// It is unavoidable that this representation is somewhat +/// lossy as it should hide quite a few semantically relevant things, +/// e.g. canonicalization and the order of nested goals. +/// +/// @lcnr: However, a lot of the weirdness here is not strictly necessary +/// and could be improved in the future. This is mostly good enough for +/// coherence right now and was annoying to implement, so I am leaving it +/// as is until we start using it for something else. +use std::ops::ControlFlow; + +use rustc_infer::infer::InferCtxt; +use rustc_middle::traits::query::NoSolution; +use rustc_middle::traits::solve::{inspect, QueryResult}; +use rustc_middle::traits::solve::{Certainty, Goal}; +use rustc_middle::ty; + +use crate::solve::inspect::ProofTreeBuilder; +use crate::solve::{GenerateProofTree, InferCtxtEvalExt, UseGlobalCache}; + +pub struct InspectGoal<'a, 'tcx> { + infcx: &'a InferCtxt<'tcx>, + depth: usize, + orig_values: &'a [ty::GenericArg<'tcx>], + goal: Goal<'tcx, ty::Predicate<'tcx>>, + evaluation: &'a inspect::GoalEvaluation<'tcx>, +} + +pub struct InspectCandidate<'a, 'tcx> { + goal: &'a InspectGoal<'a, 'tcx>, + kind: inspect::ProbeKind<'tcx>, + nested_goals: Vec<inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>>, + result: QueryResult<'tcx>, +} + +impl<'a, 'tcx> InspectCandidate<'a, 'tcx> { + pub fn infcx(&self) -> &'a InferCtxt<'tcx> { + self.goal.infcx + } + + pub fn kind(&self) -> inspect::ProbeKind<'tcx> { + self.kind + } + + pub fn result(&self) -> Result<Certainty, NoSolution> { + self.result.map(|c| c.value.certainty) + } + + /// Visit the nested goals of this candidate. + /// + /// FIXME(@lcnr): we have to slightly adapt this API + /// to also use it to compute the most relevant goal + /// for fulfillment errors. Will do that once we actually + /// need it. + pub fn visit_nested<V: ProofTreeVisitor<'tcx>>( + &self, + visitor: &mut V, + ) -> ControlFlow<V::BreakTy> { + // HACK: An arbitrary cutoff to avoid dealing with overflow and cycles. + if self.goal.depth >= 10 { + let infcx = self.goal.infcx; + infcx.probe(|_| { + let mut instantiated_goals = vec![]; + for goal in &self.nested_goals { + let goal = match ProofTreeBuilder::instantiate_canonical_state( + infcx, + self.goal.goal.param_env, + self.goal.orig_values, + *goal, + ) { + Ok((_goals, goal)) => goal, + Err(NoSolution) => { + warn!( + "unexpected failure when instantiating {:?}: {:?}", + goal, self.nested_goals + ); + return ControlFlow::Continue(()); + } + }; + instantiated_goals.push(goal); + } + + for &goal in &instantiated_goals { + let (_, proof_tree) = + infcx.evaluate_root_goal(goal, GenerateProofTree::Yes(UseGlobalCache::No)); + let proof_tree = proof_tree.unwrap(); + visitor.visit_goal(&InspectGoal::new( + infcx, + self.goal.depth + 1, + &proof_tree, + ))?; + } + + ControlFlow::Continue(()) + })?; + } + ControlFlow::Continue(()) + } +} + +impl<'a, 'tcx> InspectGoal<'a, 'tcx> { + pub fn infcx(&self) -> &'a InferCtxt<'tcx> { + self.infcx + } + + pub fn goal(&self) -> Goal<'tcx, ty::Predicate<'tcx>> { + self.goal + } + + pub fn result(&self) -> Result<Certainty, NoSolution> { + self.evaluation.evaluation.result.map(|c| c.value.certainty) + } + + fn candidates_recur( + &'a self, + candidates: &mut Vec<InspectCandidate<'a, 'tcx>>, + nested_goals: &mut Vec<inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>>, + probe: &inspect::Probe<'tcx>, + ) { + for step in &probe.steps { + match step { + &inspect::ProbeStep::AddGoal(goal) => nested_goals.push(goal), + inspect::ProbeStep::EvaluateGoals(_) => (), + inspect::ProbeStep::NestedProbe(ref probe) => { + // Nested probes have to prove goals added in their parent + // but do not leak them, so we truncate the added goals + // afterwards. + let num_goals = nested_goals.len(); + self.candidates_recur(candidates, nested_goals, probe); + nested_goals.truncate(num_goals); + } + } + } + + match probe.kind { + inspect::ProbeKind::NormalizedSelfTyAssembly + | inspect::ProbeKind::UnsizeAssembly + | inspect::ProbeKind::UpcastProjectionCompatibility => (), + // We add a candidate for the root evaluation if there + // is only one way to prove a given goal, e.g. for `WellFormed`. + // + // FIXME: This is currently wrong if we don't even try any + // candidates, e.g. for a trait goal, as in this case `candidates` is + // actually supposed to be empty. + inspect::ProbeKind::Root { result } => { + if candidates.is_empty() { + candidates.push(InspectCandidate { + goal: self, + kind: probe.kind, + nested_goals: nested_goals.clone(), + result, + }); + } + } + inspect::ProbeKind::MiscCandidate { name: _, result } + | inspect::ProbeKind::TraitCandidate { source: _, result } => { + candidates.push(InspectCandidate { + goal: self, + kind: probe.kind, + nested_goals: nested_goals.clone(), + result, + }); + } + } + } + + pub fn candidates(&'a self) -> Vec<InspectCandidate<'a, 'tcx>> { + let mut candidates = vec![]; + let last_eval_step = match self.evaluation.evaluation.kind { + inspect::CanonicalGoalEvaluationKind::Overflow + | inspect::CanonicalGoalEvaluationKind::CacheHit(_) => { + warn!("unexpected root evaluation: {:?}", self.evaluation); + return vec![]; + } + inspect::CanonicalGoalEvaluationKind::Uncached { ref revisions } => { + if let Some(last) = revisions.last() { + last + } else { + return vec![]; + } + } + }; + + let mut nested_goals = vec![]; + self.candidates_recur(&mut candidates, &mut nested_goals, &last_eval_step.evaluation); + + candidates + } + + fn new( + infcx: &'a InferCtxt<'tcx>, + depth: usize, + root: &'a inspect::GoalEvaluation<'tcx>, + ) -> Self { + match root.kind { + inspect::GoalEvaluationKind::Root { ref orig_values } => InspectGoal { + infcx, + depth, + orig_values, + goal: infcx.resolve_vars_if_possible(root.uncanonicalized_goal), + evaluation: root, + }, + inspect::GoalEvaluationKind::Nested { .. } => unreachable!(), + } + } +} + +/// The public API to interact with proof trees. +pub trait ProofTreeVisitor<'tcx> { + type BreakTy; + + fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> ControlFlow<Self::BreakTy>; +} + +pub trait ProofTreeInferCtxtExt<'tcx> { + fn visit_proof_tree<V: ProofTreeVisitor<'tcx>>( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + visitor: &mut V, + ) -> ControlFlow<V::BreakTy>; +} + +impl<'tcx> ProofTreeInferCtxtExt<'tcx> for InferCtxt<'tcx> { + fn visit_proof_tree<V: ProofTreeVisitor<'tcx>>( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + visitor: &mut V, + ) -> ControlFlow<V::BreakTy> { + let (_, proof_tree) = + self.evaluate_root_goal(goal, GenerateProofTree::Yes(UseGlobalCache::No)); + let proof_tree = proof_tree.unwrap(); + visitor.visit_goal(&InspectGoal::new(self, 0, &proof_tree)) + } +} diff --git a/compiler/rustc_trait_selection/src/solve/inspect/build.rs b/compiler/rustc_trait_selection/src/solve/inspect/build.rs new file mode 100644 index 000000000..2eba98b02 --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/inspect/build.rs @@ -0,0 +1,522 @@ +//! Building proof trees incrementally during trait solving. +//! +//! This code is *a bit* of a mess and can hopefully be +//! mostly ignored. For a general overview of how it works, +//! see the comment on [ProofTreeBuilder]. +use rustc_middle::traits::query::NoSolution; +use rustc_middle::traits::solve::{ + CanonicalInput, Certainty, Goal, IsNormalizesToHack, QueryInput, QueryResult, +}; +use rustc_middle::ty::{self, TyCtxt}; +use rustc_session::config::DumpSolverProofTree; + +use crate::solve::eval_ctxt::UseGlobalCache; +use crate::solve::{self, inspect, EvalCtxt, GenerateProofTree}; + +/// The core data structure when building proof trees. +/// +/// In case the current evaluation does not generate a proof +/// tree, `state` is simply `None` and we avoid any work. +/// +/// The possible states of the solver are represented via +/// variants of [DebugSolver]. For any nested computation we call +/// `ProofTreeBuilder::new_nested_computation_kind` which +/// creates a new `ProofTreeBuilder` to temporarily replace the +/// current one. Once that nested computation is done, +/// `ProofTreeBuilder::nested_computation_kind` is called +/// to add the finished nested evaluation to the parent. +/// +/// We provide additional information to the current state +/// by calling methods such as `ProofTreeBuilder::probe_kind`. +/// +/// The actual structure closely mirrors the finished proof +/// trees. At the end of trait solving `ProofTreeBuilder::finalize` +/// is called to recursively convert the whole structure to a +/// finished proof tree. +pub(in crate::solve) struct ProofTreeBuilder<'tcx> { + state: Option<Box<BuilderData<'tcx>>>, +} + +struct BuilderData<'tcx> { + tree: DebugSolver<'tcx>, + use_global_cache: UseGlobalCache, +} + +/// The current state of the proof tree builder, at most places +/// in the code, only one or two variants are actually possible. +/// +/// We simply ICE in case that assumption is broken. +#[derive(Debug)] +enum DebugSolver<'tcx> { + Root, + GoalEvaluation(WipGoalEvaluation<'tcx>), + CanonicalGoalEvaluation(WipCanonicalGoalEvaluation<'tcx>), + AddedGoalsEvaluation(WipAddedGoalsEvaluation<'tcx>), + GoalEvaluationStep(WipGoalEvaluationStep<'tcx>), + Probe(WipProbe<'tcx>), +} + +impl<'tcx> From<WipGoalEvaluation<'tcx>> for DebugSolver<'tcx> { + fn from(g: WipGoalEvaluation<'tcx>) -> DebugSolver<'tcx> { + DebugSolver::GoalEvaluation(g) + } +} + +impl<'tcx> From<WipCanonicalGoalEvaluation<'tcx>> for DebugSolver<'tcx> { + fn from(g: WipCanonicalGoalEvaluation<'tcx>) -> DebugSolver<'tcx> { + DebugSolver::CanonicalGoalEvaluation(g) + } +} + +impl<'tcx> From<WipAddedGoalsEvaluation<'tcx>> for DebugSolver<'tcx> { + fn from(g: WipAddedGoalsEvaluation<'tcx>) -> DebugSolver<'tcx> { + DebugSolver::AddedGoalsEvaluation(g) + } +} + +impl<'tcx> From<WipGoalEvaluationStep<'tcx>> for DebugSolver<'tcx> { + fn from(g: WipGoalEvaluationStep<'tcx>) -> DebugSolver<'tcx> { + DebugSolver::GoalEvaluationStep(g) + } +} + +impl<'tcx> From<WipProbe<'tcx>> for DebugSolver<'tcx> { + fn from(p: WipProbe<'tcx>) -> DebugSolver<'tcx> { + DebugSolver::Probe(p) + } +} + +#[derive(Eq, PartialEq, Debug)] +struct WipGoalEvaluation<'tcx> { + pub uncanonicalized_goal: Goal<'tcx, ty::Predicate<'tcx>>, + pub kind: WipGoalEvaluationKind<'tcx>, + pub evaluation: Option<WipCanonicalGoalEvaluation<'tcx>>, + pub returned_goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, +} + +impl<'tcx> WipGoalEvaluation<'tcx> { + fn finalize(self) -> inspect::GoalEvaluation<'tcx> { + inspect::GoalEvaluation { + uncanonicalized_goal: self.uncanonicalized_goal, + kind: match self.kind { + WipGoalEvaluationKind::Root { orig_values } => { + inspect::GoalEvaluationKind::Root { orig_values } + } + WipGoalEvaluationKind::Nested { is_normalizes_to_hack } => { + inspect::GoalEvaluationKind::Nested { is_normalizes_to_hack } + } + }, + evaluation: self.evaluation.unwrap().finalize(), + returned_goals: self.returned_goals, + } + } +} + +#[derive(Eq, PartialEq, Debug)] +pub(in crate::solve) enum WipGoalEvaluationKind<'tcx> { + Root { orig_values: Vec<ty::GenericArg<'tcx>> }, + Nested { is_normalizes_to_hack: IsNormalizesToHack }, +} + +#[derive(Eq, PartialEq, Debug)] +pub(in crate::solve) enum WipCanonicalGoalEvaluationKind { + Overflow, + CacheHit(inspect::CacheHit), +} + +#[derive(Eq, PartialEq, Debug)] +struct WipCanonicalGoalEvaluation<'tcx> { + goal: CanonicalInput<'tcx>, + kind: Option<WipCanonicalGoalEvaluationKind>, + revisions: Vec<WipGoalEvaluationStep<'tcx>>, + result: Option<QueryResult<'tcx>>, +} + +impl<'tcx> WipCanonicalGoalEvaluation<'tcx> { + fn finalize(self) -> inspect::CanonicalGoalEvaluation<'tcx> { + let kind = match self.kind { + Some(WipCanonicalGoalEvaluationKind::Overflow) => { + inspect::CanonicalGoalEvaluationKind::Overflow + } + Some(WipCanonicalGoalEvaluationKind::CacheHit(hit)) => { + inspect::CanonicalGoalEvaluationKind::CacheHit(hit) + } + None => inspect::CanonicalGoalEvaluationKind::Uncached { + revisions: self + .revisions + .into_iter() + .map(WipGoalEvaluationStep::finalize) + .collect(), + }, + }; + + inspect::CanonicalGoalEvaluation { goal: self.goal, kind, result: self.result.unwrap() } + } +} + +#[derive(Eq, PartialEq, Debug)] +struct WipAddedGoalsEvaluation<'tcx> { + evaluations: Vec<Vec<WipGoalEvaluation<'tcx>>>, + result: Option<Result<Certainty, NoSolution>>, +} + +impl<'tcx> WipAddedGoalsEvaluation<'tcx> { + fn finalize(self) -> inspect::AddedGoalsEvaluation<'tcx> { + inspect::AddedGoalsEvaluation { + evaluations: self + .evaluations + .into_iter() + .map(|evaluations| { + evaluations.into_iter().map(WipGoalEvaluation::finalize).collect() + }) + .collect(), + result: self.result.unwrap(), + } + } +} + +#[derive(Eq, PartialEq, Debug)] +struct WipGoalEvaluationStep<'tcx> { + instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>, + + evaluation: WipProbe<'tcx>, +} + +impl<'tcx> WipGoalEvaluationStep<'tcx> { + fn finalize(self) -> inspect::GoalEvaluationStep<'tcx> { + let evaluation = self.evaluation.finalize(); + match evaluation.kind { + inspect::ProbeKind::Root { .. } => (), + _ => unreachable!("unexpected root evaluation: {evaluation:?}"), + } + inspect::GoalEvaluationStep { instantiated_goal: self.instantiated_goal, evaluation } + } +} + +#[derive(Eq, PartialEq, Debug)] +struct WipProbe<'tcx> { + pub steps: Vec<WipProbeStep<'tcx>>, + pub kind: Option<inspect::ProbeKind<'tcx>>, +} + +impl<'tcx> WipProbe<'tcx> { + fn finalize(self) -> inspect::Probe<'tcx> { + inspect::Probe { + steps: self.steps.into_iter().map(WipProbeStep::finalize).collect(), + kind: self.kind.unwrap(), + } + } +} + +#[derive(Eq, PartialEq, Debug)] +enum WipProbeStep<'tcx> { + AddGoal(inspect::CanonicalState<'tcx, Goal<'tcx, ty::Predicate<'tcx>>>), + EvaluateGoals(WipAddedGoalsEvaluation<'tcx>), + NestedProbe(WipProbe<'tcx>), +} + +impl<'tcx> WipProbeStep<'tcx> { + fn finalize(self) -> inspect::ProbeStep<'tcx> { + match self { + WipProbeStep::AddGoal(goal) => inspect::ProbeStep::AddGoal(goal), + WipProbeStep::EvaluateGoals(eval) => inspect::ProbeStep::EvaluateGoals(eval.finalize()), + WipProbeStep::NestedProbe(probe) => inspect::ProbeStep::NestedProbe(probe.finalize()), + } + } +} + +impl<'tcx> ProofTreeBuilder<'tcx> { + fn new( + state: impl Into<DebugSolver<'tcx>>, + use_global_cache: UseGlobalCache, + ) -> ProofTreeBuilder<'tcx> { + ProofTreeBuilder { + state: Some(Box::new(BuilderData { tree: state.into(), use_global_cache })), + } + } + + fn nested<T: Into<DebugSolver<'tcx>>>(&self, state: impl FnOnce() -> T) -> Self { + match &self.state { + Some(prev_state) => Self { + state: Some(Box::new(BuilderData { + tree: state().into(), + use_global_cache: prev_state.use_global_cache, + })), + }, + None => Self { state: None }, + } + } + + fn as_mut(&mut self) -> Option<&mut DebugSolver<'tcx>> { + self.state.as_mut().map(|boxed| &mut boxed.tree) + } + + pub fn finalize(self) -> Option<inspect::GoalEvaluation<'tcx>> { + match self.state?.tree { + DebugSolver::GoalEvaluation(wip_goal_evaluation) => { + Some(wip_goal_evaluation.finalize()) + } + root => unreachable!("unexpected proof tree builder root node: {:?}", root), + } + } + + pub fn use_global_cache(&self) -> bool { + self.state + .as_ref() + .map(|state| matches!(state.use_global_cache, UseGlobalCache::Yes)) + .unwrap_or(true) + } + + pub fn new_maybe_root( + tcx: TyCtxt<'tcx>, + generate_proof_tree: GenerateProofTree, + ) -> ProofTreeBuilder<'tcx> { + match generate_proof_tree { + GenerateProofTree::Never => ProofTreeBuilder::new_noop(), + GenerateProofTree::IfEnabled => { + let opts = &tcx.sess.opts.unstable_opts; + match opts.dump_solver_proof_tree { + DumpSolverProofTree::Always => { + let use_cache = opts.dump_solver_proof_tree_use_cache.unwrap_or(true); + ProofTreeBuilder::new_root(UseGlobalCache::from_bool(use_cache)) + } + // `OnError` is handled by reevaluating goals in error + // reporting with `GenerateProofTree::Yes`. + DumpSolverProofTree::OnError | DumpSolverProofTree::Never => { + ProofTreeBuilder::new_noop() + } + } + } + GenerateProofTree::Yes(use_cache) => ProofTreeBuilder::new_root(use_cache), + } + } + + pub fn new_root(use_global_cache: UseGlobalCache) -> ProofTreeBuilder<'tcx> { + ProofTreeBuilder::new(DebugSolver::Root, use_global_cache) + } + + pub fn new_noop() -> ProofTreeBuilder<'tcx> { + ProofTreeBuilder { state: None } + } + + pub fn is_noop(&self) -> bool { + self.state.is_none() + } + + pub(in crate::solve) fn new_goal_evaluation( + &mut self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + orig_values: &[ty::GenericArg<'tcx>], + kind: solve::GoalEvaluationKind, + ) -> ProofTreeBuilder<'tcx> { + self.nested(|| WipGoalEvaluation { + uncanonicalized_goal: goal, + kind: match kind { + solve::GoalEvaluationKind::Root => { + WipGoalEvaluationKind::Root { orig_values: orig_values.to_vec() } + } + solve::GoalEvaluationKind::Nested { is_normalizes_to_hack } => { + WipGoalEvaluationKind::Nested { is_normalizes_to_hack } + } + }, + evaluation: None, + returned_goals: vec![], + }) + } + + pub fn new_canonical_goal_evaluation( + &mut self, + goal: CanonicalInput<'tcx>, + ) -> ProofTreeBuilder<'tcx> { + self.nested(|| WipCanonicalGoalEvaluation { + goal, + kind: None, + revisions: vec![], + result: None, + }) + } + + pub fn canonical_goal_evaluation(&mut self, canonical_goal_evaluation: ProofTreeBuilder<'tcx>) { + if let Some(this) = self.as_mut() { + match (this, canonical_goal_evaluation.state.unwrap().tree) { + ( + DebugSolver::GoalEvaluation(goal_evaluation), + DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation), + ) => goal_evaluation.evaluation = Some(canonical_goal_evaluation), + _ => unreachable!(), + } + } + } + + pub fn goal_evaluation_kind(&mut self, kind: WipCanonicalGoalEvaluationKind) { + if let Some(this) = self.as_mut() { + match this { + DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => { + assert_eq!(canonical_goal_evaluation.kind.replace(kind), None); + } + _ => unreachable!(), + }; + } + } + + pub fn returned_goals(&mut self, goals: &[Goal<'tcx, ty::Predicate<'tcx>>]) { + if let Some(this) = self.as_mut() { + match this { + DebugSolver::GoalEvaluation(evaluation) => { + assert!(evaluation.returned_goals.is_empty()); + evaluation.returned_goals.extend(goals); + } + _ => unreachable!(), + } + } + } + pub fn goal_evaluation(&mut self, goal_evaluation: ProofTreeBuilder<'tcx>) { + if let Some(this) = self.as_mut() { + match (this, goal_evaluation.state.unwrap().tree) { + ( + DebugSolver::AddedGoalsEvaluation(WipAddedGoalsEvaluation { + evaluations, .. + }), + DebugSolver::GoalEvaluation(goal_evaluation), + ) => evaluations.last_mut().unwrap().push(goal_evaluation), + (this @ DebugSolver::Root, goal_evaluation) => *this = goal_evaluation, + _ => unreachable!(), + } + } + } + + pub fn new_goal_evaluation_step( + &mut self, + instantiated_goal: QueryInput<'tcx, ty::Predicate<'tcx>>, + ) -> ProofTreeBuilder<'tcx> { + self.nested(|| WipGoalEvaluationStep { + instantiated_goal, + evaluation: WipProbe { steps: vec![], kind: None }, + }) + } + pub fn goal_evaluation_step(&mut self, goal_evaluation_step: ProofTreeBuilder<'tcx>) { + if let Some(this) = self.as_mut() { + match (this, goal_evaluation_step.state.unwrap().tree) { + ( + DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluations), + DebugSolver::GoalEvaluationStep(goal_evaluation_step), + ) => { + canonical_goal_evaluations.revisions.push(goal_evaluation_step); + } + _ => unreachable!(), + } + } + } + + pub fn new_probe(&mut self) -> ProofTreeBuilder<'tcx> { + self.nested(|| WipProbe { steps: vec![], kind: None }) + } + + pub fn probe_kind(&mut self, probe_kind: inspect::ProbeKind<'tcx>) { + if let Some(this) = self.as_mut() { + match this { + DebugSolver::Probe(this) => { + assert_eq!(this.kind.replace(probe_kind), None) + } + _ => unreachable!(), + } + } + } + + pub fn add_goal(ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, ty::Predicate<'tcx>>) { + // Can't use `if let Some(this) = ecx.inspect.as_mut()` here because + // we have to immutably use the `EvalCtxt` for `make_canonical_state`. + if ecx.inspect.is_noop() { + return; + } + + let goal = Self::make_canonical_state(ecx, goal); + + match ecx.inspect.as_mut().unwrap() { + DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { + evaluation: WipProbe { steps, .. }, + .. + }) + | DebugSolver::Probe(WipProbe { steps, .. }) => steps.push(WipProbeStep::AddGoal(goal)), + s => unreachable!("tried to add {goal:?} to {s:?}"), + } + } + + pub fn finish_probe(&mut self, probe: ProofTreeBuilder<'tcx>) { + if let Some(this) = self.as_mut() { + match (this, probe.state.unwrap().tree) { + ( + DebugSolver::Probe(WipProbe { steps, .. }) + | DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { + evaluation: WipProbe { steps, .. }, + .. + }), + DebugSolver::Probe(probe), + ) => steps.push(WipProbeStep::NestedProbe(probe)), + _ => unreachable!(), + } + } + } + + pub fn new_evaluate_added_goals(&mut self) -> ProofTreeBuilder<'tcx> { + self.nested(|| WipAddedGoalsEvaluation { evaluations: vec![], result: None }) + } + + pub fn evaluate_added_goals_loop_start(&mut self) { + if let Some(this) = self.as_mut() { + match this { + DebugSolver::AddedGoalsEvaluation(this) => { + this.evaluations.push(vec![]); + } + _ => unreachable!(), + } + } + } + + pub fn eval_added_goals_result(&mut self, result: Result<Certainty, NoSolution>) { + if let Some(this) = self.as_mut() { + match this { + DebugSolver::AddedGoalsEvaluation(this) => { + assert_eq!(this.result.replace(result), None); + } + _ => unreachable!(), + } + } + } + + pub fn added_goals_evaluation(&mut self, added_goals_evaluation: ProofTreeBuilder<'tcx>) { + if let Some(this) = self.as_mut() { + match (this, added_goals_evaluation.state.unwrap().tree) { + ( + DebugSolver::GoalEvaluationStep(WipGoalEvaluationStep { + evaluation: WipProbe { steps, .. }, + .. + }) + | DebugSolver::Probe(WipProbe { steps, .. }), + DebugSolver::AddedGoalsEvaluation(added_goals_evaluation), + ) => steps.push(WipProbeStep::EvaluateGoals(added_goals_evaluation)), + _ => unreachable!(), + } + } + } + + pub fn query_result(&mut self, result: QueryResult<'tcx>) { + if let Some(this) = self.as_mut() { + match this { + DebugSolver::CanonicalGoalEvaluation(canonical_goal_evaluation) => { + assert_eq!(canonical_goal_evaluation.result.replace(result), None); + } + DebugSolver::GoalEvaluationStep(evaluation_step) => { + assert_eq!( + evaluation_step + .evaluation + .kind + .replace(inspect::ProbeKind::Root { result }), + None + ); + } + _ => unreachable!(), + } + } + } +} diff --git a/compiler/rustc_trait_selection/src/solve/inspect/mod.rs b/compiler/rustc_trait_selection/src/solve/inspect/mod.rs new file mode 100644 index 000000000..60d52305a --- /dev/null +++ b/compiler/rustc_trait_selection/src/solve/inspect/mod.rs @@ -0,0 +1,7 @@ +pub use rustc_middle::traits::solve::inspect::*; + +mod build; +pub(in crate::solve) use build::*; + +mod analyse; +pub use analyse::*; diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 75a99f799..77a3b5e12 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -19,7 +19,8 @@ use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; use rustc_infer::traits::query::NoSolution; use rustc_middle::infer::canonical::CanonicalVarInfos; use rustc_middle::traits::solve::{ - CanonicalResponse, Certainty, ExternalConstraintsData, Goal, QueryResult, Response, + CanonicalResponse, Certainty, ExternalConstraintsData, Goal, IsNormalizesToHack, QueryResult, + Response, }; use rustc_middle::ty::{self, Ty, TyCtxt, UniverseIndex}; use rustc_middle::ty::{ @@ -59,6 +60,12 @@ enum SolverMode { Coherence, } +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +enum GoalEvaluationKind { + Root, + Nested { is_normalizes_to_hack: IsNormalizesToHack }, +} + trait CanonicalResponseExt { fn has_no_inference_or_external_constraints(&self) -> bool; @@ -228,14 +235,15 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self))] fn add_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) { + inspect::ProofTreeBuilder::add_goal(self, goal); self.nested_goals.goals.push(goal); } #[instrument(level = "debug", skip(self, goals))] fn add_goals(&mut self, goals: impl IntoIterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>) { - let current_len = self.nested_goals.goals.len(); - self.nested_goals.goals.extend(goals); - debug!("added_goals={:?}", &self.nested_goals.goals[current_len..]); + for goal in goals { + self.add_goal(goal); + } } /// Try to merge multiple possible ways to prove a goal, if that is not possible returns `None`. diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs index e47e22877..0f9d36342 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -8,8 +8,9 @@ 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::inspect::CandidateKind; -use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; +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; @@ -58,7 +59,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } DefKind::AnonConst => self.normalize_anon_const(goal), DefKind::OpaqueTy => self.normalize_opaque_type(goal), - DefKind::TyAlias { .. } => self.normalize_weak_type(goal), + DefKind::TyAlias => self.normalize_weak_type(goal), kind => bug!("unknown DefKind {} in projection goal: {goal:#?}", kind.descr(def_id)), } } @@ -113,7 +114,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'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_candidate("assumption").enter(|ecx| { + ecx.probe_misc_candidate("assumption").enter(|ecx| { let assumption_projection_pred = ecx.instantiate_binder_with_infer(projection_pred); ecx.eq( @@ -155,7 +156,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { return Err(NoSolution); } - ecx.probe(|r| CandidateKind::Candidate { name: "impl".into(), result: *r }).enter(|ecx| { + 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); @@ -244,7 +245,21 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { // 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 => bug!("associated const projection is not supported yet"), + 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"), }; @@ -331,13 +346,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty::TraitRef::from_lang_item(tcx, LangItem::Sized, DUMMY_SP, [output]) }); - let pred = tupled_inputs_and_output - .map_bound(|(inputs, output)| ty::ProjectionPredicate { + let pred = ty::Clause::from_projection_clause( + tcx, + 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)]) @@ -355,7 +372,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { let tcx = ecx.tcx(); - ecx.probe_candidate("builtin pointee").enter(|ecx| { + ecx.probe_misc_candidate("builtin pointee").enter(|ecx| { let metadata_ty = match goal.predicate.self_ty().kind() { ty::Bool | ty::Char @@ -371,7 +388,6 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Foreign(..) => tcx.types.unit, @@ -539,7 +555,6 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Foreign(..) | ty::Adt(_, _) @@ -564,7 +579,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ), }; - ecx.probe_candidate("builtin discriminant kind").enter(|ecx| { + 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) diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs deleted file mode 100644 index be48447e2..000000000 --- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs +++ /dev/null @@ -1,102 +0,0 @@ -//! This module both handles the global cache which stores "finished" goals, -//! and the provisional cache which contains partially computed goals. -//! -//! The provisional cache is necessary when dealing with coinductive cycles. -//! -//! For more information about the provisional cache and coinduction in general, -//! check out the relevant section of the rustc-dev-guide. -//! -//! FIXME(@lcnr): Write that section, feel free to ping me if you need help here -//! before then or if I still haven't done that before January 2023. -use super::StackDepth; -use rustc_data_structures::fx::FxHashMap; -use rustc_index::IndexVec; -use rustc_middle::traits::solve::{CanonicalInput, QueryResult}; - -rustc_index::newtype_index! { - pub struct EntryIndex {} -} - -#[derive(Debug, Clone)] -pub(super) struct ProvisionalEntry<'tcx> { - /// In case we have a coinductive cycle, this is the - /// the current provisional result of this goal. - /// - /// This starts out as `None` for all goals and gets to some - /// when the goal gets popped from the stack or we rerun evaluation - /// for this goal to reach a fixpoint. - pub(super) response: Option<QueryResult<'tcx>>, - /// In case of a cycle, the position of deepest stack entry involved - /// in that cycle. This is monotonically decreasing in the stack as all - /// elements between the current stack element in the deepest stack entry - /// involved have to also be involved in that cycle. - /// - /// We can only move entries to the global cache once we're complete done - /// with the cycle. If this entry has not been involved in a cycle, - /// this is just its own depth. - pub(super) depth: StackDepth, - - /// The goal for this entry. Should always be equal to the corresponding goal - /// in the lookup table. - pub(super) input: CanonicalInput<'tcx>, -} - -pub(super) struct ProvisionalCache<'tcx> { - pub(super) entries: IndexVec<EntryIndex, ProvisionalEntry<'tcx>>, - // FIXME: This is only used to quickly check whether a given goal - // is in the cache. We should experiment with using something like - // `SsoHashSet` here because in most cases there are only a few entries. - pub(super) lookup_table: FxHashMap<CanonicalInput<'tcx>, EntryIndex>, -} - -impl<'tcx> ProvisionalCache<'tcx> { - pub(super) fn empty() -> ProvisionalCache<'tcx> { - ProvisionalCache { entries: Default::default(), lookup_table: Default::default() } - } - - pub(super) fn is_empty(&self) -> bool { - self.entries.is_empty() && self.lookup_table.is_empty() - } - - /// Adds a dependency from the current leaf to `target` in the cache - /// to prevent us from moving any goals which depend on the current leaf - /// to the global cache while we're still computing `target`. - /// - /// Its important to note that `target` may already be part of a different cycle. - /// In this case we have to ensure that we also depend on all other goals - /// in the existing cycle in addition to the potentially direct cycle with `target`. - pub(super) fn add_dependency_of_leaf_on(&mut self, target: EntryIndex) { - let depth = self.entries[target].depth; - for provisional_entry in &mut self.entries.raw[target.index()..] { - // The depth of `target` is the position of the deepest goal in the stack - // on which `target` depends. That goal is the `root` of this cycle. - // - // Any entry which was added after `target` is either on the stack itself - // at which point its depth is definitely at least as high as the depth of - // `root`. If it's not on the stack itself it has to depend on a goal - // between `root` and `leaf`. If it were to depend on a goal deeper in the - // stack than `root`, then `root` would also depend on that goal, at which - // point `root` wouldn't be the root anymore. - debug_assert!(provisional_entry.depth >= depth); - provisional_entry.depth = depth; - } - - // We only update entries which were added after `target` as no other - // entry should have a higher depth. - // - // Any entry which previously had a higher depth than target has to - // be between `target` and `root`. Because of this we would have updated - // its depth when calling `add_dependency_of_leaf_on(root)` for `target`. - if cfg!(debug_assertions) { - self.entries.iter().all(|e| e.depth <= depth); - } - } - - pub(super) fn depth(&self, entry_index: EntryIndex) -> StackDepth { - self.entries[entry_index].depth - } - - pub(super) fn provisional_result(&self, entry_index: EntryIndex) -> Option<QueryResult<'tcx>> { - self.entries[entry_index].response - } -} diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs index 49ebfa4e6..33513f6bd 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -1,13 +1,11 @@ -mod cache; - -use self::cache::ProvisionalEntry; +use super::inspect; use super::inspect::ProofTreeBuilder; use super::SolverMode; -use cache::ProvisionalCache; +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::DepKind; +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}; @@ -26,8 +24,14 @@ struct StackEntry<'tcx> { // 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<QueryResult<'tcx>>, /// We put only the root goal of a coinductive cycle into the global cache. /// @@ -46,16 +50,16 @@ pub(super) struct SearchGraph<'tcx> { /// /// An element is *deeper* in the stack if its index is *lower*. stack: IndexVec<StackDepth, StackEntry<'tcx>>, - provisional_cache: ProvisionalCache<'tcx>, + stack_entries: FxHashMap<CanonicalInput<'tcx>, 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.ilog2() as usize, + local_overflow_limit: tcx.recursion_limit().0.checked_ilog2().unwrap_or(0) as usize, stack: Default::default(), - provisional_cache: ProvisionalCache::empty(), + stack_entries: Default::default(), } } @@ -84,6 +88,7 @@ impl<'tcx> SearchGraph<'tcx> { /// 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; @@ -103,22 +108,17 @@ impl<'tcx> SearchGraph<'tcx> { } pub(super) fn is_empty(&self) -> bool { - self.stack.is_empty() && self.provisional_cache.is_empty() + 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... - if self.stack[stack_depth].has_been_used { - return true; - } - - // ...or it depends on a goal with a lower depth. - let current_goal = self.stack[stack_depth].input; - let entry_index = self.provisional_cache.lookup_table[¤t_goal]; - self.provisional_cache.entries[entry_index].depth != stack_depth + // 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 } @@ -185,6 +185,8 @@ impl<'tcx> SearchGraph<'tcx> { 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); }; @@ -200,14 +202,16 @@ impl<'tcx> SearchGraph<'tcx> { available_depth, ) { + inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( + CacheHit::Global, + )); self.on_cache_hit(reached_depth, encountered_overflow); return result; } } - // Look at the provisional cache to detect cycles. - let cache = &mut self.provisional_cache; - match cache.lookup_table.entry(input) { + // 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(); @@ -215,14 +219,14 @@ impl<'tcx> SearchGraph<'tcx> { 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); - let entry_index = - cache.entries.push(ProvisionalEntry { response: None, depth, input }); - v.insert(entry_index); + v.insert(depth); } // We have a nested goal which relies on a goal `root` deeper in the stack. // @@ -233,39 +237,50 @@ impl<'tcx> SearchGraph<'tcx> { // // 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_index) => { - inspect.cache_hit(CacheHit::Provisional); + Entry::Occupied(entry) => { + inspect.goal_evaluation_kind(inspect::WipCanonicalGoalEvaluationKind::CacheHit( + CacheHit::Provisional, + )); - let entry_index = *entry_index.get(); - let stack_depth = cache.depth(entry_index); + let stack_depth = *entry.get(); debug!("encountered cycle with depth {stack_depth:?}"); - - cache.add_dependency_of_leaf_on(entry_index); - let mut iter = self.stack.iter_mut(); - let root = iter.nth(stack_depth.as_usize()).unwrap(); - for e in iter { - root.cycle_participants.insert(e.input); + // 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 current goal - // until we reach a fixpoint. + // 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) = cache.provisional_result(entry_index) { + return if let Some(result) = self.stack[stack_depth].provisional_result { result } else { - // If we don't have a provisional result yet, the goal has to - // still be on the stack. - let mut goal_on_stack = false; - let mut is_coinductive = true; - for entry in self.stack.raw[stack_depth.index()..] + // 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() - .skip_while(|entry| entry.input != input) - { - goal_on_stack = true; - is_coinductive &= entry.input.value.goal.predicate.is_coinductive(tcx); - } - debug_assert!(goal_on_stack); - + .all(|entry| entry.input.value.goal.predicate.is_coinductive(tcx)); if is_coinductive { Self::response_no_constraints(tcx, input, Certainty::Yes) } else { @@ -279,47 +294,32 @@ impl<'tcx> SearchGraph<'tcx> { // 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, DepKind::TraitSelect, || { + 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 response = prove_goal(self, inspect); + 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. - // - // Also update the response for this goal stored in the provisional - // cache. let stack_entry = self.pop_stack(); debug_assert_eq!(stack_entry.input, input); - let cache = &mut self.provisional_cache; - let provisional_entry_index = - *cache.lookup_table.get(&stack_entry.input).unwrap(); - let provisional_entry = &mut cache.entries[provisional_entry_index]; if stack_entry.has_been_used - && provisional_entry.response.map_or(true, |r| r != response) + && stack_entry.provisional_result.map_or(true, |r| r != result) { - // If so, update the provisional result for this goal and remove - // all entries whose result depends on this goal from the provisional - // cache... - // - // That's not completely correct, as a nested goal can also only - // depend on a goal which is lower in the stack so it doesn't - // actually depend on the current goal. This should be fairly - // rare and is hopefully not relevant for performance. - provisional_entry.response = Some(response); - #[allow(rustc::potential_query_instability)] - cache.lookup_table.retain(|_key, index| *index <= provisional_entry_index); - cache.entries.truncate(provisional_entry_index.index() + 1); - - // ...and finally push our goal back on the stack and reevaluate it. - self.stack.push(StackEntry { has_been_used: false, ..stack_entry }); + // 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, response); + return (stack_entry, result); } } @@ -335,17 +335,7 @@ impl<'tcx> SearchGraph<'tcx> { // // 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. - let cache = &mut self.provisional_cache; - let provisional_entry_index = *cache.lookup_table.get(&input).unwrap(); - let provisional_entry = &mut cache.entries[provisional_entry_index]; - let depth = provisional_entry.depth; - if depth == self.stack.next_index() { - for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) { - let actual_index = cache.lookup_table.remove(&entry.input); - debug_assert_eq!(Some(i), actual_index); - debug_assert!(entry.depth == depth); - } - + 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. @@ -363,8 +353,6 @@ impl<'tcx> SearchGraph<'tcx> { dep_node, result, ) - } else { - provisional_entry.response = Some(result); } result diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index 8685f3100..8055c63b9 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -5,7 +5,7 @@ use super::{EvalCtxt, SolverMode}; use rustc_hir::def_id::DefId; use rustc_hir::{LangItem, Movability}; use rustc_infer::traits::query::NoSolution; -use rustc_middle::traits::solve::inspect::CandidateKind; +use rustc_middle::traits::solve::inspect::ProbeKind; use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; use rustc_middle::traits::{BuiltinImplSource, Reveal}; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections}; @@ -61,7 +61,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { }, }; - ecx.probe_candidate("impl").enter(|ecx| { + ecx.probe_misc_candidate("impl").enter(|ecx| { let impl_args = ecx.fresh_args_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.instantiate(tcx, impl_args); @@ -96,7 +96,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { && trait_clause.polarity() == goal.predicate.polarity { // FIXME: Constness - ecx.probe_candidate("assumption").enter(|ecx| { + ecx.probe_misc_candidate("assumption").enter(|ecx| { let assumption_trait_pred = ecx.instantiate_binder_with_infer(trait_clause); ecx.eq( goal.param_env, @@ -167,7 +167,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let tcx = ecx.tcx(); - ecx.probe_candidate("trait alias").enter(|ecx| { + ecx.probe_misc_candidate("trait alias").enter(|ecx| { let nested_obligations = tcx .predicates_of(goal.predicate.def_id()) .instantiate(tcx, goal.predicate.trait_ref.args); @@ -427,7 +427,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - ecx.probe(|_| CandidateKind::UnsizeAssembly).enter(|ecx| { + ecx.probe(|_| ProbeKind::UnsizeAssembly).enter(|ecx| { let a_ty = goal.predicate.self_ty(); // We need to normalize the b_ty since it's destructured as a `dyn Trait`. let Some(b_ty) = @@ -491,7 +491,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { Err(NoSolution) => vec![], }; - ecx.probe(|_| CandidateKind::UnsizeAssembly).enter(|ecx| { + ecx.probe(|_| ProbeKind::UnsizeAssembly).enter(|ecx| { let a_ty = goal.predicate.self_ty(); // We need to normalize the b_ty since it's matched structurally // in the other functions below. @@ -597,7 +597,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.walk_vtable( a_principal.with_self_ty(tcx, a_ty), |ecx, new_a_principal, _, vtable_vptr_slot| { - if let Ok(resp) = ecx.probe_candidate("dyn upcast").enter(|ecx| { + if let Ok(resp) = ecx.probe_misc_candidate("dyn upcast").enter(|ecx| { ecx.consider_builtin_upcast_to_principal( goal, a_data, @@ -640,7 +640,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { target_projection: ty::PolyExistentialProjection<'tcx>| { source_projection.item_def_id() == target_projection.item_def_id() && ecx - .probe(|_| CandidateKind::UpcastProbe) + .probe(|_| ProbeKind::UpcastProjectionCompatibility) .enter(|ecx| -> Result<(), NoSolution> { ecx.eq(param_env, source_projection, target_projection)?; let _ = ecx.try_evaluate_added_goals()?; @@ -879,8 +879,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::FnPtr(_) | ty::Closure(_, _) | ty::Generator(_, _, _) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(_, _) + | ty::GeneratorWitness(..) | ty::Never | ty::Tuple(_) | ty::Adt(_, _) @@ -918,7 +917,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, TraitPredicate<'tcx>>, constituent_tys: impl Fn(&EvalCtxt<'_, 'tcx>, Ty<'tcx>) -> Result<Vec<Ty<'tcx>>, NoSolution>, ) -> QueryResult<'tcx> { - self.probe_candidate("constituent tys").enter(|ecx| { + self.probe_misc_candidate("constituent tys").enter(|ecx| { ecx.add_goals( constituent_tys(ecx, goal.predicate.self_ty())? .into_iter() |