diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src')
39 files changed, 1848 insertions, 1238 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() diff --git a/compiler/rustc_trait_selection/src/traits/auto_trait.rs b/compiler/rustc_trait_selection/src/traits/auto_trait.rs index ba5000da6..8096d7969 100644 --- a/compiler/rustc_trait_selection/src/traits/auto_trait.rs +++ b/compiler/rustc_trait_selection/src/traits/auto_trait.rs @@ -793,7 +793,7 @@ impl<'tcx> AutoTraitFinder<'tcx> { span: tcx.def_span(unevaluated.def), unevaluated: unevaluated, }); - Err(ErrorHandled::Reported(reported.into())) + Err(ErrorHandled::Reported(reported.into(), tcx.def_span(unevaluated.def))) } Err(err) => Err(err), } diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs index 5746781ae..acab4498a 100644 --- a/compiler/rustc_trait_selection/src/traits/coherence.rs +++ b/compiler/rustc_trait_selection/src/traits/coherence.rs @@ -6,9 +6,15 @@ use crate::infer::outlives::env::OutlivesEnvironment; use crate::infer::InferOk; +use crate::solve::inspect; +use crate::solve::inspect::{InspectGoal, ProofTreeInferCtxtExt, ProofTreeVisitor}; +use crate::traits::engine::TraitEngineExt; use crate::traits::outlives_bounds::InferCtxtExt as _; +use crate::traits::query::evaluate_obligation::InferCtxtExt; use crate::traits::select::{IntercrateAmbiguityCause, TreatInductiveCycleAs}; +use crate::traits::structural_normalize::StructurallyNormalizeExt; use crate::traits::util::impl_subject_and_oblig; +use crate::traits::NormalizeExt; use crate::traits::SkipLeakCheck; use crate::traits::{ self, Obligation, ObligationCause, ObligationCtxt, PredicateObligation, PredicateObligations, @@ -18,10 +24,13 @@ use rustc_data_structures::fx::FxIndexSet; use rustc_errors::Diagnostic; use rustc_hir::def_id::{DefId, CRATE_DEF_ID, LOCAL_CRATE}; use rustc_infer::infer::{DefineOpaqueTypes, InferCtxt, TyCtxtInferExt}; -use rustc_infer::traits::util; +use rustc_infer::traits::{util, TraitEngine}; +use rustc_middle::traits::query::NoSolution; +use rustc_middle::traits::solve::{Certainty, Goal}; use rustc_middle::traits::specialization_graph::OverlapMode; use rustc_middle::traits::DefiningAnchor; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::ty::print::with_no_trimmed_paths; use rustc_middle::ty::visit::{TypeVisitable, TypeVisitableExt}; use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitor}; use rustc_session::lint::builtin::COINDUCTIVE_OVERLAP_IN_COHERENCE; @@ -31,9 +40,6 @@ use std::fmt::Debug; use std::iter; use std::ops::ControlFlow; -use super::query::evaluate_obligation::InferCtxtExt; -use super::NormalizeExt; - /// Whether we do the orphan check relative to this crate or /// to some remote crate. #[derive(Copy, Clone, Debug)] @@ -152,16 +158,14 @@ fn with_fresh_ty_vars<'cx, 'tcx>( .predicates_of(impl_def_id) .instantiate(tcx, impl_args) .iter() - .map(|(c, s)| (c.as_predicate(), s)) + .map(|(c, _)| c.as_predicate()) .collect(), }; - let InferOk { value: mut header, obligations } = selcx - .infcx - .at(&ObligationCause::dummy_with_span(tcx.def_span(impl_def_id)), param_env) - .normalize(header); + let InferOk { value: mut header, obligations } = + selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(header); - header.predicates.extend(obligations.into_iter().map(|o| (o.predicate, o.cause.span))); + header.predicates.extend(obligations.into_iter().map(|o| o.predicate)); header } @@ -207,19 +211,19 @@ fn overlap<'tcx>( // Equate the headers to find their intersection (the general type, with infer vars, // that may apply both impls). - let equate_obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?; + let mut obligations = equate_impl_headers(selcx.infcx, &impl1_header, &impl2_header)?; debug!("overlap: unification check succeeded"); + obligations.extend( + [&impl1_header.predicates, &impl2_header.predicates].into_iter().flatten().map( + |&predicate| Obligation::new(infcx.tcx, ObligationCause::dummy(), param_env, predicate), + ), + ); + if overlap_mode.use_implicit_negative() { for mode in [TreatInductiveCycleAs::Ambig, TreatInductiveCycleAs::Recur] { if let Some(failing_obligation) = selcx.with_treat_inductive_cycle_as(mode, |selcx| { - impl_intersection_has_impossible_obligation( - selcx, - param_env, - &impl1_header, - &impl2_header, - &equate_obligations, - ) + impl_intersection_has_impossible_obligation(selcx, &obligations) }) { if matches!(mode, TreatInductiveCycleAs::Recur) { let first_local_impl = impl1_header @@ -261,17 +265,11 @@ fn overlap<'tcx>( infcx.tcx.def_span(impl2_header.impl_def_id), "the second impl is here", ); - if !failing_obligation.cause.span.is_dummy() { - lint.span_label( - failing_obligation.cause.span, - format!( - "`{}` may be considered to hold in future releases, \ - causing the impls to overlap", - infcx - .resolve_vars_if_possible(failing_obligation.predicate) - ), - ); - } + lint.note(format!( + "`{}` may be considered to hold in future releases, \ + causing the impls to overlap", + infcx.resolve_vars_if_possible(failing_obligation.predicate) + )); lint }, ); @@ -289,7 +287,14 @@ fn overlap<'tcx>( return None; } - let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes(); + let intercrate_ambiguity_causes = if !overlap_mode.use_implicit_negative() { + Default::default() + } else if infcx.next_trait_solver() { + compute_intercrate_ambiguity_causes(&infcx, &obligations) + } else { + selcx.take_intercrate_ambiguity_causes() + }; + debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes); let involves_placeholder = infcx .inner @@ -343,34 +348,24 @@ fn equate_impl_headers<'tcx>( /// of the two impls above to be empty. /// /// Importantly, this works even if there isn't a `impl !Error for MyLocalType`. -fn impl_intersection_has_impossible_obligation<'cx, 'tcx>( +fn impl_intersection_has_impossible_obligation<'a, 'cx, 'tcx>( selcx: &mut SelectionContext<'cx, 'tcx>, - param_env: ty::ParamEnv<'tcx>, - impl1_header: &ty::ImplHeader<'tcx>, - impl2_header: &ty::ImplHeader<'tcx>, - obligations: &PredicateObligations<'tcx>, -) -> Option<PredicateObligation<'tcx>> { + obligations: &'a [PredicateObligation<'tcx>], +) -> Option<&'a PredicateObligation<'tcx>> { let infcx = selcx.infcx; - [&impl1_header.predicates, &impl2_header.predicates] - .into_iter() - .flatten() - .map(|&(predicate, span)| { - Obligation::new(infcx.tcx, ObligationCause::dummy_with_span(span), param_env, predicate) - }) - .chain(obligations.into_iter().cloned()) - .find(|obligation: &PredicateObligation<'tcx>| { - if infcx.next_trait_solver() { - infcx.evaluate_obligation(obligation).map_or(false, |result| !result.may_apply()) - } else { - // We use `evaluate_root_obligation` to correctly track intercrate - // ambiguity clauses. We cannot use this in the new solver. - selcx.evaluate_root_obligation(obligation).map_or( - false, // Overflow has occurred, and treat the obligation as possibly holding. - |result| !result.may_apply(), - ) - } - }) + obligations.iter().find(|obligation| { + if infcx.next_trait_solver() { + infcx.evaluate_obligation(obligation).map_or(false, |result| !result.may_apply()) + } else { + // We use `evaluate_root_obligation` to correctly track intercrate + // ambiguity clauses. We cannot use this in the new solver. + selcx.evaluate_root_obligation(obligation).map_or( + false, // Overflow has occurred, and treat the obligation as possibly holding. + |result| !result.may_apply(), + ) + } + }) } /// Check if both impls can be satisfied by a common type by considering whether @@ -832,9 +827,7 @@ where // This should only be created when checking whether we have to check whether some // auto trait impl applies. There will never be multiple impls, so we can just // act as if it were a local type here. - ty::GeneratorWitness(_) | ty::GeneratorWitnessMIR(..) => { - ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) - } + ty::GeneratorWitness(..) => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), ty::Alias(ty::Opaque, ..) => { // This merits some explanation. // Normally, opaque types are not involved when performing @@ -890,3 +883,144 @@ where ControlFlow::Continue(()) } } + +/// Compute the `intercrate_ambiguity_causes` for the new solver using +/// "proof trees". +/// +/// This is a bit scuffed but seems to be good enough, at least +/// when looking at UI tests. Given that it is only used to improve +/// diagnostics this is good enough. We can always improve it once there +/// are test cases where it is currently not enough. +fn compute_intercrate_ambiguity_causes<'tcx>( + infcx: &InferCtxt<'tcx>, + obligations: &[PredicateObligation<'tcx>], +) -> FxIndexSet<IntercrateAmbiguityCause> { + let mut causes: FxIndexSet<IntercrateAmbiguityCause> = Default::default(); + + for obligation in obligations { + search_ambiguity_causes(infcx, obligation.clone().into(), &mut causes); + } + + causes +} + +struct AmbiguityCausesVisitor<'a> { + causes: &'a mut FxIndexSet<IntercrateAmbiguityCause>, +} + +impl<'a, 'tcx> ProofTreeVisitor<'tcx> for AmbiguityCausesVisitor<'a> { + type BreakTy = !; + fn visit_goal(&mut self, goal: &InspectGoal<'_, 'tcx>) -> ControlFlow<Self::BreakTy> { + let infcx = goal.infcx(); + for cand in goal.candidates() { + cand.visit_nested(self)?; + } + // When searching for intercrate ambiguity causes, we only need to look + // at ambiguous goals, as for others the coherence unknowable candidate + // was irrelevant. + match goal.result() { + Ok(Certainty::Maybe(_)) => {} + Ok(Certainty::Yes) | Err(NoSolution) => return ControlFlow::Continue(()), + } + + let Goal { param_env, predicate } = goal.goal(); + + // For bound predicates we simply call `infcx.replace_bound_vars_with_placeholders` + // and then prove the resulting predicate as a nested goal. + let trait_ref = match predicate.kind().no_bound_vars() { + Some(ty::PredicateKind::Clause(ty::ClauseKind::Trait(tr))) => tr.trait_ref, + Some(ty::PredicateKind::Clause(ty::ClauseKind::Projection(proj))) => { + proj.projection_ty.trait_ref(infcx.tcx) + } + _ => return ControlFlow::Continue(()), + }; + + let mut ambiguity_cause = None; + for cand in goal.candidates() { + // FIXME: boiiii, using string comparisions here sure is scuffed. + if let inspect::ProbeKind::MiscCandidate { name: "coherence unknowable", result: _ } = + cand.kind() + { + let lazily_normalize_ty = |ty: Ty<'tcx>| { + let mut fulfill_cx = <dyn TraitEngine<'tcx>>::new(infcx); + if matches!(ty.kind(), ty::Alias(..)) { + // FIXME(-Ztrait-solver=next-coherence): we currently don't + // normalize opaque types here, resulting in diverging behavior + // for TAITs. + match infcx + .at(&ObligationCause::dummy(), param_env) + .structurally_normalize(ty, &mut *fulfill_cx) + { + Ok(ty) => Ok(ty), + Err(_errs) => Err(()), + } + } else { + Ok(ty) + } + }; + + infcx.probe(|_| { + match trait_ref_is_knowable(infcx.tcx, trait_ref, lazily_normalize_ty) { + Err(()) => {} + Ok(Ok(())) => warn!("expected an unknowable trait ref: {trait_ref:?}"), + Ok(Err(conflict)) => { + if !trait_ref.references_error() { + let self_ty = trait_ref.self_ty(); + let (trait_desc, self_desc) = with_no_trimmed_paths!({ + let trait_desc = trait_ref.print_only_trait_path().to_string(); + let self_desc = self_ty + .has_concrete_skeleton() + .then(|| self_ty.to_string()); + (trait_desc, self_desc) + }); + ambiguity_cause = Some(match conflict { + Conflict::Upstream => { + IntercrateAmbiguityCause::UpstreamCrateUpdate { + trait_desc, + self_desc, + } + } + Conflict::Downstream => { + IntercrateAmbiguityCause::DownstreamCrate { + trait_desc, + self_desc, + } + } + }); + } + } + } + }) + } else { + match cand.result() { + // We only add an ambiguity cause if the goal would otherwise + // result in an error. + // + // FIXME: While this matches the behavior of the + // old solver, it is not the only way in which the unknowable + // candidates *weaken* coherence, they can also force otherwise + // sucessful normalization to be ambiguous. + Ok(Certainty::Maybe(_) | Certainty::Yes) => { + ambiguity_cause = None; + break; + } + Err(NoSolution) => continue, + } + } + } + + if let Some(ambiguity_cause) = ambiguity_cause { + self.causes.insert(ambiguity_cause); + } + + ControlFlow::Continue(()) + } +} + +fn search_ambiguity_causes<'tcx>( + infcx: &InferCtxt<'tcx>, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + causes: &mut FxIndexSet<IntercrateAmbiguityCause>, +) { + infcx.visit_proof_tree(goal, &mut AmbiguityCausesVisitor { causes }); +} diff --git a/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs b/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs index 3d0d3812d..62ab1e104 100644 --- a/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs +++ b/compiler/rustc_trait_selection/src/traits/const_evaluatable.rs @@ -73,13 +73,13 @@ pub fn is_const_evaluatable<'tcx>( ty::ConstKind::Unevaluated(uv) => { let concrete = infcx.const_eval_resolve(param_env, uv, Some(span)); match concrete { - Err(ErrorHandled::TooGeneric) => { + Err(ErrorHandled::TooGeneric(_)) => { Err(NotConstEvaluatable::Error(infcx.tcx.sess.delay_span_bug( span, "Missing value for constant, but no error reported?", ))) } - Err(ErrorHandled::Reported(e)) => Err(NotConstEvaluatable::Error(e.into())), + Err(ErrorHandled::Reported(e, _)) => Err(NotConstEvaluatable::Error(e.into())), Ok(_) => Ok(()), } } @@ -132,7 +132,7 @@ pub fn is_const_evaluatable<'tcx>( .emit() } - Err(ErrorHandled::TooGeneric) => { + Err(ErrorHandled::TooGeneric(_)) => { let err = if uv.has_non_region_infer() { NotConstEvaluatable::MentionsInfer } else if uv.has_non_region_param() { @@ -147,7 +147,7 @@ pub fn is_const_evaluatable<'tcx>( Err(err) } - Err(ErrorHandled::Reported(e)) => Err(NotConstEvaluatable::Error(e.into())), + Err(ErrorHandled::Reported(e, _)) => Err(NotConstEvaluatable::Error(e.into())), Ok(_) => Ok(()), } } diff --git a/compiler/rustc_trait_selection/src/traits/engine.rs b/compiler/rustc_trait_selection/src/traits/engine.rs index 820973dc0..015e38b2a 100644 --- a/compiler/rustc_trait_selection/src/traits/engine.rs +++ b/compiler/rustc_trait_selection/src/traits/engine.rs @@ -23,6 +23,7 @@ use rustc_middle::traits::query::NoSolution; use rustc_middle::ty::error::TypeError; use rustc_middle::ty::ToPredicate; use rustc_middle::ty::TypeFoldable; +use rustc_middle::ty::Variance; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_session::config::TraitSolver; @@ -156,6 +157,20 @@ impl<'a, 'tcx> ObligationCtxt<'a, 'tcx> { .map(|infer_ok| self.register_infer_ok_obligations(infer_ok)) } + pub fn relate<T: ToTrace<'tcx>>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + variance: Variance, + expected: T, + actual: T, + ) -> Result<(), TypeError<'tcx>> { + self.infcx + .at(cause, param_env) + .relate(DefineOpaqueTypes::Yes, expected, variance, actual) + .map(|infer_ok| self.register_infer_ok_obligations(infer_ok)) + } + /// Checks whether `expected` is a supertype of `actual`: `expected :> actual`. pub fn sup<T: ToTrace<'tcx>>( &self, diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs index 457d5420c..2a586f810 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/mod.rs @@ -986,6 +986,9 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } } + self.explain_hrtb_projection(&mut err, trait_predicate, obligation.param_env, &obligation.cause); + self.suggest_desugaring_async_fn_in_trait(&mut err, trait_ref); + // Return early if the trait is Debug or Display and the invocation // originates within a standard library macro, because the output // is otherwise overwhelming and unhelpful (see #85844 for an @@ -1844,7 +1847,6 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ty::Generator(..) => Some(18), ty::Foreign(..) => Some(19), ty::GeneratorWitness(..) => Some(20), - ty::GeneratorWitnessMIR(..) => Some(21), ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) | ty::Error(_) => None, } } @@ -2054,7 +2056,7 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { tcx: self.tcx, ty_op: |ty| ty, lt_op: |lt| lt, - ct_op: |ct| ct.eval(self.tcx, ty::ParamEnv::empty()), + ct_op: |ct| ct.normalize(self.tcx, ty::ParamEnv::empty()), }); cand }) @@ -2920,6 +2922,16 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { rustc_transmute::Reason::DstIsTooBig => { format!("The size of `{src}` is smaller than the size of `{dst}`") } + rustc_transmute::Reason::SrcSizeOverflow => { + format!( + "values of the type `{src}` are too big for the current architecture" + ) + } + rustc_transmute::Reason::DstSizeOverflow => { + format!( + "values of the type `{dst}` are too big for the current architecture" + ) + } rustc_transmute::Reason::DstHasStricterAlignment { src_min_align, dst_min_align, @@ -2999,10 +3011,10 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { // Try to report a help message if is_fn_trait && let Ok((implemented_kind, params)) = self.type_implements_fn_trait( - obligation.param_env, - trait_ref.self_ty(), - trait_predicate.skip_binder().polarity, - ) + obligation.param_env, + trait_ref.self_ty(), + trait_predicate.skip_binder().polarity, + ) { self.add_help_message_for_fn_trait(trait_ref, err, implemented_kind, params); } else if !trait_ref.has_non_region_infer() @@ -3021,6 +3033,15 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { None, obligation.cause.body_id, ); + } else if trait_ref.def_id().is_local() + && self.tcx.trait_impls_of(trait_ref.def_id()).is_empty() + && !self.tcx.trait_is_auto(trait_ref.def_id()) + && !self.tcx.trait_is_alias(trait_ref.def_id()) + { + err.span_help( + self.tcx.def_span(trait_ref.def_id()), + crate::fluent_generated::trait_selection_trait_has_no_impls, + ); } else if !suggested && !unsatisfied_const { // Can't show anything else useful, try to find similar impls. let impl_candidates = self.find_similar_impl_candidates(*trait_predicate); @@ -3031,7 +3052,12 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { err, true, ) { - self.report_similar_impl_candidates_for_root_obligation(&obligation, *trait_predicate, body_def_id, err); + self.report_similar_impl_candidates_for_root_obligation( + &obligation, + *trait_predicate, + body_def_id, + err, + ); } self.suggest_convert_to_slice( @@ -3185,7 +3211,7 @@ impl<'tcx> InferCtxtPrivExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ) -> DiagnosticBuilder<'tcx, ErrorGuaranteed> { let name = match self.tcx.opaque_type_origin(def_id.expect_local()) { hir::OpaqueTyOrigin::FnReturn(_) | hir::OpaqueTyOrigin::AsyncFn(_) => { - format!("opaque type") + "opaque type".to_string() } hir::OpaqueTyOrigin::TyAlias { .. } => { format!("`{}`", self.tcx.def_path_debug_str(def_id)) diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs index 0e73bad19..d645dc033 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/on_unimplemented.rs @@ -9,6 +9,7 @@ use rustc_hir::def_id::DefId; use rustc_middle::ty::GenericArgsRef; use rustc_middle::ty::{self, GenericParamDefKind, TyCtxt}; use rustc_parse_format::{ParseMode, Parser, Piece, Position}; +use rustc_session::lint::builtin::UNKNOWN_OR_MALFORMED_DIAGNOSTIC_ATTRIBUTES; use rustc_span::symbol::{kw, sym, Symbol}; use rustc_span::{Span, DUMMY_SP}; use std::iter; @@ -103,7 +104,9 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { hir::Node::Item(hir::Item { kind: hir::ItemKind::Fn(sig, _, body_id), .. }) => { self.describe_generator(*body_id).or_else(|| { Some(match sig.header { - hir::FnHeader { asyncness: hir::IsAsync::Async, .. } => "an async function", + hir::FnHeader { asyncness: hir::IsAsync::Async(_), .. } => { + "an async function" + } _ => "a function", }) }) @@ -117,7 +120,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { .. }) => self.describe_generator(*body_id).or_else(|| { Some(match sig.header { - hir::FnHeader { asyncness: hir::IsAsync::Async, .. } => "an async method", + hir::FnHeader { asyncness: hir::IsAsync::Async(_), .. } => "an async method", _ => "a method", }) }), @@ -257,7 +260,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { // Arrays give us `[]`, `[{ty}; _]` and `[{ty}; N]` if let ty::Array(aty, len) = self_ty.kind() { flags.push((sym::_Self, Some("[]".to_string()))); - let len = len.try_to_value().and_then(|v| v.try_to_target_usize(self.tcx)); + let len = len.try_to_valtree().and_then(|v| v.try_to_target_usize(self.tcx)); flags.push((sym::_Self, Some(format!("[{aty}; _]")))); if let Some(n) = len { flags.push((sym::_Self, Some(format!("[{aty}; {n}]")))); @@ -336,6 +339,10 @@ pub enum AppendConstMessage { Custom(Symbol), } +#[derive(LintDiagnostic)] +#[diag(trait_selection_malformed_on_unimplemented_attr)] +pub struct NoValueInOnUnimplementedLint; + impl<'tcx> OnUnimplementedDirective { fn parse( tcx: TyCtxt<'tcx>, @@ -343,7 +350,8 @@ impl<'tcx> OnUnimplementedDirective { items: &[NestedMetaItem], span: Span, is_root: bool, - ) -> Result<Self, ErrorGuaranteed> { + is_diagnostic_namespace_variant: bool, + ) -> Result<Option<Self>, ErrorGuaranteed> { let mut errored = None; let mut item_iter = items.iter(); @@ -391,7 +399,10 @@ impl<'tcx> OnUnimplementedDirective { note = parse_value(note_)?; continue; } - } else if item.has_name(sym::parent_label) && parent_label.is_none() { + } else if item.has_name(sym::parent_label) + && parent_label.is_none() + && !is_diagnostic_namespace_variant + { if let Some(parent_label_) = item.value_str() { parent_label = parse_value(parent_label_)?; continue; @@ -401,15 +412,30 @@ impl<'tcx> OnUnimplementedDirective { && message.is_none() && label.is_none() && note.is_none() + && !is_diagnostic_namespace_variant + // FIXME(diagnostic_namespace): disallow filters for now { if let Some(items) = item.meta_item_list() { - match Self::parse(tcx, item_def_id, &items, item.span(), false) { - Ok(subcommand) => subcommands.push(subcommand), + match Self::parse( + tcx, + item_def_id, + &items, + item.span(), + false, + is_diagnostic_namespace_variant, + ) { + Ok(Some(subcommand)) => subcommands.push(subcommand), + Ok(None) => bug!( + "This cannot happen for now as we only reach that if `is_diagnostic_namespace_variant` is false" + ), Err(reported) => errored = Some(reported), }; continue; } - } else if item.has_name(sym::append_const_msg) && append_const_msg.is_none() { + } else if item.has_name(sym::append_const_msg) + && append_const_msg.is_none() + && !is_diagnostic_namespace_variant + { if let Some(msg) = item.value_str() { append_const_msg = Some(AppendConstMessage::Custom(msg)); continue; @@ -419,14 +445,23 @@ impl<'tcx> OnUnimplementedDirective { } } - // nothing found - tcx.sess.emit_err(NoValueInOnUnimplemented { span: item.span() }); + if is_diagnostic_namespace_variant { + tcx.emit_spanned_lint( + UNKNOWN_OR_MALFORMED_DIAGNOSTIC_ATTRIBUTES, + tcx.hir().local_def_id_to_hir_id(item_def_id.expect_local()), + vec![item.span()], + NoValueInOnUnimplementedLint, + ); + } else { + // nothing found + tcx.sess.emit_err(NoValueInOnUnimplemented { span: item.span() }); + } } if let Some(reported) = errored { - Err(reported) + if is_diagnostic_namespace_variant { Ok(None) } else { Err(reported) } } else { - Ok(OnUnimplementedDirective { + Ok(Some(OnUnimplementedDirective { condition, subcommands, message, @@ -434,32 +469,58 @@ impl<'tcx> OnUnimplementedDirective { note, parent_label, append_const_msg, - }) + })) } } pub fn of_item(tcx: TyCtxt<'tcx>, item_def_id: DefId) -> Result<Option<Self>, ErrorGuaranteed> { - let Some(attr) = tcx.get_attr(item_def_id, sym::rustc_on_unimplemented) else { + let mut is_diagnostic_namespace_variant = false; + let Some(attr) = tcx.get_attr(item_def_id, sym::rustc_on_unimplemented).or_else(|| { + if tcx.features().diagnostic_namespace { + is_diagnostic_namespace_variant = true; + tcx.get_attrs_by_path(item_def_id, &[sym::diagnostic, sym::on_unimplemented]).next() + } else { + None + } + }) else { return Ok(None); }; let result = if let Some(items) = attr.meta_item_list() { - Self::parse(tcx, item_def_id, &items, attr.span, true).map(Some) + Self::parse(tcx, item_def_id, &items, attr.span, true, is_diagnostic_namespace_variant) } else if let Some(value) = attr.value_str() { - Ok(Some(OnUnimplementedDirective { - condition: None, - message: None, - subcommands: vec![], - label: Some(OnUnimplementedFormatString::try_parse( - tcx, - item_def_id, - value, + if !is_diagnostic_namespace_variant { + Ok(Some(OnUnimplementedDirective { + condition: None, + message: None, + subcommands: vec![], + label: Some(OnUnimplementedFormatString::try_parse( + tcx, + item_def_id, + value, + attr.span, + )?), + note: None, + parent_label: None, + append_const_msg: None, + })) + } else { + tcx.emit_spanned_lint( + UNKNOWN_OR_MALFORMED_DIAGNOSTIC_ATTRIBUTES, + tcx.hir().local_def_id_to_hir_id(item_def_id.expect_local()), attr.span, - )?), - note: None, - parent_label: None, - append_const_msg: None, - })) + NoValueInOnUnimplementedLint, + ); + Ok(None) + } + } else if is_diagnostic_namespace_variant { + tcx.emit_spanned_lint( + UNKNOWN_OR_MALFORMED_DIAGNOSTIC_ATTRIBUTES, + tcx.hir().local_def_id_to_hir_id(item_def_id.expect_local()), + attr.span, + NoValueInOnUnimplementedLint, + ); + Ok(None) } else { let reported = tcx.sess.delay_span_bug(DUMMY_SP, "of_item: neither meta_item_list nor value_str"); diff --git a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs index 611ec6b00..15f2ba809 100644 --- a/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs +++ b/compiler/rustc_trait_selection/src/traits/error_reporting/suggestions.rs @@ -30,10 +30,9 @@ use rustc_infer::infer::{DefineOpaqueTypes, InferOk, LateBoundRegionConversionTi use rustc_middle::hir::map; use rustc_middle::ty::error::TypeError::{self, Sorts}; use rustc_middle::ty::{ - self, suggest_arbitrary_trait_bound, suggest_constraining_type_param, AdtKind, - GeneratorDiagnosticData, GeneratorInteriorTypeCause, GenericArgs, InferTy, IsSuggestable, - ToPredicate, Ty, TyCtxt, TypeAndMut, TypeFoldable, TypeFolder, TypeSuperFoldable, - TypeVisitableExt, TypeckResults, + self, suggest_arbitrary_trait_bound, suggest_constraining_type_param, AdtKind, GenericArgs, + InferTy, IsSuggestable, ToPredicate, Ty, TyCtxt, TypeAndMut, TypeFoldable, TypeFolder, + TypeSuperFoldable, TypeVisitableExt, TypeckResults, }; use rustc_span::def_id::LocalDefId; use rustc_span::symbol::{sym, Ident, Symbol}; @@ -50,7 +49,7 @@ use rustc_middle::ty::print::{with_forced_trimmed_paths, with_no_trimmed_paths}; #[derive(Debug)] pub enum GeneratorInteriorOrUpvar { // span of interior type - Interior(Span, Option<(Option<Span>, Span, Option<hir::HirId>, Option<Span>)>), + Interior(Span, Option<(Span, Option<Span>)>), // span of upvar Upvar(Span), } @@ -58,15 +57,12 @@ pub enum GeneratorInteriorOrUpvar { // This type provides a uniform interface to retrieve data on generators, whether it originated from // the local crate being compiled or from a foreign crate. #[derive(Debug)] -pub enum GeneratorData<'tcx, 'a> { - Local(&'a TypeckResults<'tcx>), - Foreign(&'tcx GeneratorDiagnosticData<'tcx>), -} +struct GeneratorData<'tcx, 'a>(&'a TypeckResults<'tcx>); impl<'tcx, 'a> GeneratorData<'tcx, 'a> { - // Try to get information about variables captured by the generator that matches a type we are - // looking for with `ty_matches` function. We uses it to find upvar which causes a failure to - // meet an obligation + /// Try to get information about variables captured by the generator that matches a type we are + /// looking for with `ty_matches` function. We uses it to find upvar which causes a failure to + /// meet an obligation fn try_get_upvar_span<F>( &self, infer_context: &InferCtxt<'tcx>, @@ -76,27 +72,21 @@ impl<'tcx, 'a> GeneratorData<'tcx, 'a> { where F: Fn(ty::Binder<'tcx, Ty<'tcx>>) -> bool, { - match self { - GeneratorData::Local(typeck_results) => { - infer_context.tcx.upvars_mentioned(generator_did).and_then(|upvars| { - upvars.iter().find_map(|(upvar_id, upvar)| { - let upvar_ty = typeck_results.node_type(*upvar_id); - let upvar_ty = infer_context.resolve_vars_if_possible(upvar_ty); - ty_matches(ty::Binder::dummy(upvar_ty)) - .then(|| GeneratorInteriorOrUpvar::Upvar(upvar.span)) - }) - }) - } - GeneratorData::Foreign(_) => None, - } + infer_context.tcx.upvars_mentioned(generator_did).and_then(|upvars| { + upvars.iter().find_map(|(upvar_id, upvar)| { + let upvar_ty = self.0.node_type(*upvar_id); + let upvar_ty = infer_context.resolve_vars_if_possible(upvar_ty); + ty_matches(ty::Binder::dummy(upvar_ty)) + .then(|| GeneratorInteriorOrUpvar::Upvar(upvar.span)) + }) + }) } - // Try to get the span of a type being awaited on that matches the type we are looking with the - // `ty_matches` function. We uses it to find awaited type which causes a failure to meet an - // obligation + /// Try to get the span of a type being awaited on that matches the type we are looking with the + /// `ty_matches` function. We uses it to find awaited type which causes a failure to meet an + /// obligation fn get_from_await_ty<F>( &self, - tcx: TyCtxt<'tcx>, visitor: AwaitsVisitor, hir: map::Map<'tcx>, ty_matches: F, @@ -104,69 +94,12 @@ impl<'tcx, 'a> GeneratorData<'tcx, 'a> { where F: Fn(ty::Binder<'tcx, Ty<'tcx>>) -> bool, { - match self { - GeneratorData::Local(typeck_results) => visitor - .awaits - .into_iter() - .map(|id| hir.expect_expr(id)) - .find(|await_expr| { - ty_matches(ty::Binder::dummy(typeck_results.expr_ty_adjusted(&await_expr))) - }) - .map(|expr| expr.span), - GeneratorData::Foreign(generator_diagnostic_data) => visitor - .awaits - .into_iter() - .map(|id| hir.expect_expr(id)) - .find(|await_expr| { - ty_matches(ty::Binder::dummy( - generator_diagnostic_data - .adjustments - .get(&await_expr.hir_id.local_id) - .map_or::<&[ty::adjustment::Adjustment<'tcx>], _>(&[], |a| &a[..]) - .last() - .map_or_else::<Ty<'tcx>, _, _>( - || { - generator_diagnostic_data - .nodes_types - .get(&await_expr.hir_id.local_id) - .cloned() - .unwrap_or_else(|| { - bug!( - "node_type: no type for node {}", - tcx.hir().node_to_string(await_expr.hir_id) - ) - }) - }, - |adj| adj.target, - ), - )) - }) - .map(|expr| expr.span), - } - } - - /// Get the type, expression, span and optional scope span of all types - /// that are live across the yield of this generator - fn get_generator_interior_types( - &self, - ) -> ty::Binder<'tcx, &[GeneratorInteriorTypeCause<'tcx>]> { - match self { - GeneratorData::Local(typeck_result) => { - typeck_result.generator_interior_types.as_deref() - } - GeneratorData::Foreign(generator_diagnostic_data) => { - generator_diagnostic_data.generator_interior_types.as_deref() - } - } - } - - // Used to get the source of the data, note we don't have as much information for generators - // originated from foreign crates - fn is_foreign(&self) -> bool { - match self { - GeneratorData::Local(_) => false, - GeneratorData::Foreign(_) => true, - } + visitor + .awaits + .into_iter() + .map(|id| hir.expect_expr(id)) + .find(|await_expr| ty_matches(ty::Binder::dummy(self.0.expr_ty_adjusted(&await_expr)))) + .map(|expr| expr.span) } } @@ -316,7 +249,6 @@ pub trait TypeErrCtxtExt<'tcx> { outer_generator: Option<DefId>, trait_pred: ty::TraitPredicate<'tcx>, target_ty: Ty<'tcx>, - typeck_results: Option<&ty::TypeckResults<'tcx>>, obligation: &PredicateObligation<'tcx>, next_code: Option<&ObligationCauseCode<'tcx>>, ); @@ -406,6 +338,20 @@ pub trait TypeErrCtxtExt<'tcx> { candidate_impls: &[ImplCandidate<'tcx>], span: Span, ); + + fn explain_hrtb_projection( + &self, + diag: &mut Diagnostic, + pred: ty::PolyTraitPredicate<'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: &ObligationCause<'tcx>, + ); + + fn suggest_desugaring_async_fn_in_trait( + &self, + err: &mut Diagnostic, + trait_ref: ty::PolyTraitRef<'tcx>, + ); } fn predicate_constraint(generics: &hir::Generics<'_>, pred: ty::Predicate<'_>) -> (Span, String) { @@ -838,7 +784,20 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { obligation.param_env, real_trait_pred_and_base_ty, ); - if self.predicate_may_hold(&obligation) { + let sized_obligation = Obligation::new( + self.tcx, + obligation.cause.clone(), + obligation.param_env, + ty::TraitRef::from_lang_item( + self.tcx, + hir::LangItem::Sized, + obligation.cause.span, + [base_ty], + ), + ); + if self.predicate_may_hold(&obligation) + && self.predicate_must_hold_modulo_regions(&sized_obligation) + { let call_node = self.tcx.hir().get(*call_hir_id); let msg = "consider dereferencing here"; let is_receiver = matches!( @@ -1792,7 +1751,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); } else { err.note(format!( - "`{}` is implemented for `{:?}`, but not for `{:?}`", + "`{}` is implemented for `{}`, but not for `{}`", trait_pred.print_modifiers_and_trait_path(), suggested_ty, trait_pred.skip_binder().self_ty(), @@ -2213,11 +2172,10 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); match *ty.kind() { - ty::Generator(did, ..) | ty::GeneratorWitnessMIR(did, _) => { + ty::Generator(did, ..) | ty::GeneratorWitness(did, _) => { generator = generator.or(Some(did)); outer_generator = Some(did); } - ty::GeneratorWitness(..) => {} ty::Tuple(_) if !seen_upvar_tys_infer_tuple => { // By introducing a tuple of upvar types into the chain of obligations // of a generator, the first non-generator item is now the tuple itself, @@ -2243,11 +2201,10 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); match *ty.kind() { - ty::Generator(did, ..) | ty::GeneratorWitnessMIR(did, ..) => { + ty::Generator(did, ..) | ty::GeneratorWitness(did, ..) => { generator = generator.or(Some(did)); outer_generator = Some(did); } - ty::GeneratorWitness(..) => {} ty::Tuple(_) if !seen_upvar_tys_infer_tuple => { // By introducing a tuple of upvar types into the chain of obligations // of a generator, the first non-generator item is now the tuple itself, @@ -2324,12 +2281,9 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { // cycles. If we can't use resolved types because the generator comes from another crate, // we still provide a targeted error but without all the relevant spans. let generator_data = match &self.typeck_results { - Some(t) if t.hir_owner.to_def_id() == generator_did_root => GeneratorData::Local(&t), + Some(t) if t.hir_owner.to_def_id() == generator_did_root => GeneratorData(&t), _ if generator_did.is_local() => { - GeneratorData::Local(self.tcx.typeck(generator_did.expect_local())) - } - _ if let Some(generator_diag_data) = self.tcx.generator_diagnostic_data(generator_did) => { - GeneratorData::Foreign(generator_diag_data) + GeneratorData(self.tcx.typeck(generator_did.expect_local())) } _ => return false, }; @@ -2341,30 +2295,11 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { let mut interior_or_upvar_span = None; - let from_awaited_ty = generator_data.get_from_await_ty(self.tcx, visitor, hir, ty_matches); + let from_awaited_ty = generator_data.get_from_await_ty(visitor, hir, ty_matches); debug!(?from_awaited_ty); - // The generator interior types share the same binders - if let Some(cause) = - generator_data.get_generator_interior_types().skip_binder().iter().find( - |ty::GeneratorInteriorTypeCause { ty, .. }| { - ty_matches(generator_data.get_generator_interior_types().rebind(*ty)) - }, - ) - { - let ty::GeneratorInteriorTypeCause { span, scope_span, yield_span, expr, .. } = cause; - - interior_or_upvar_span = Some(GeneratorInteriorOrUpvar::Interior( - *span, - Some((*scope_span, *yield_span, *expr, from_awaited_ty)), - )); - - if interior_or_upvar_span.is_none() && generator_data.is_foreign() { - interior_or_upvar_span = Some(GeneratorInteriorOrUpvar::Interior(*span, None)); - } - } else if self.tcx.sess.opts.unstable_opts.drop_tracking_mir - // Avoid disclosing internal information to downstream crates. - && generator_did.is_local() + // Avoid disclosing internal information to downstream crates. + if generator_did.is_local() // Try to avoid cycles. && !generator_within_in_progress_typeck && let Some(generator_info) = self.tcx.mir_generator_witnesses(generator_did) @@ -2380,7 +2315,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { if ty_matches(ty::Binder::dummy(decl.ty)) && !decl.ignore_for_traits { interior_or_upvar_span = Some(GeneratorInteriorOrUpvar::Interior( decl.source_info.span, - Some((None, source_info.span, None, from_awaited_ty)), + Some((source_info.span, from_awaited_ty)), )); break 'find_source; } @@ -2393,17 +2328,13 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { generator_data.try_get_upvar_span(&self, generator_did, ty_matches); } - if interior_or_upvar_span.is_none() && generator_data.is_foreign() { + if interior_or_upvar_span.is_none() && !generator_did.is_local() { interior_or_upvar_span = Some(GeneratorInteriorOrUpvar::Interior(span, None)); } debug!(?interior_or_upvar_span); if let Some(interior_or_upvar_span) = interior_or_upvar_span { let is_async = self.tcx.generator_is_async(generator_did); - let typeck_results = match generator_data { - GeneratorData::Local(typeck_results) => Some(typeck_results), - GeneratorData::Foreign(_) => None, - }; self.note_obligation_cause_for_async_await( err, interior_or_upvar_span, @@ -2411,7 +2342,6 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { outer_generator, trait_ref, target_ty, - typeck_results, obligation, next_code, ); @@ -2432,7 +2362,6 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { outer_generator: Option<DefId>, trait_pred: ty::TraitPredicate<'tcx>, target_ty: Ty<'tcx>, - typeck_results: Option<&ty::TypeckResults<'tcx>>, obligation: &PredicateObligation<'tcx>, next_code: Option<&ObligationCauseCode<'tcx>>, ) { @@ -2490,9 +2419,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { format!("does not implement `{}`", trait_pred.print_modifiers_and_trait_path()) }; - let mut explain_yield = |interior_span: Span, - yield_span: Span, - scope_span: Option<Span>| { + let mut explain_yield = |interior_span: Span, yield_span: Span| { let mut span = MultiSpan::from_span(yield_span); let snippet = match source_map.span_to_snippet(interior_span) { // #70935: If snippet contains newlines, display "the value" instead @@ -2524,22 +2451,14 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { interior_span, format!("has type `{target_ty}` which {trait_explanation}"), ); - if let Some(scope_span) = scope_span { - let scope_span = source_map.end_point(scope_span); - - let msg = format!("{snippet} is later dropped here"); - span.push_span_label(scope_span, msg); - } err.span_note( - span, - format!( - "{future_or_generator} {trait_explanation} as this value is used across {an_await_or_yield}" - ), - ); + span, + format!("{future_or_generator} {trait_explanation} as this value is used across {an_await_or_yield}"), + ); }; match interior_or_upvar_span { GeneratorInteriorOrUpvar::Interior(interior_span, interior_extra_info) => { - if let Some((scope_span, yield_span, expr, from_awaited_ty)) = interior_extra_info { + if let Some((yield_span, from_awaited_ty)) = interior_extra_info { if let Some(await_span) = from_awaited_ty { // The type causing this obligation is one being awaited at await_span. let mut span = MultiSpan::from_span(await_span); @@ -2557,62 +2476,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ); } else { // Look at the last interior type to get a span for the `.await`. - debug!( - generator_interior_types = ?format_args!( - "{:#?}", typeck_results.as_ref().map(|t| &t.generator_interior_types) - ), - ); - explain_yield(interior_span, yield_span, scope_span); - } - - if let Some(expr_id) = expr { - let expr = hir.expect_expr(expr_id); - debug!("target_ty evaluated from {:?}", expr); - - let parent = hir.parent_id(expr_id); - if let Some(hir::Node::Expr(e)) = hir.find(parent) { - let parent_span = hir.span(parent); - let parent_did = parent.owner.to_def_id(); - // ```rust - // impl T { - // fn foo(&self) -> i32 {} - // } - // T.foo(); - // ^^^^^^^ a temporary `&T` created inside this method call due to `&self` - // ``` - // - let is_region_borrow = if let Some(typeck_results) = typeck_results { - typeck_results - .expr_adjustments(expr) - .iter() - .any(|adj| adj.is_region_borrow()) - } else { - false - }; - - // ```rust - // struct Foo(*const u8); - // bar(Foo(std::ptr::null())).await; - // ^^^^^^^^^^^^^^^^^^^^^ raw-ptr `*T` created inside this struct ctor. - // ``` - debug!(parent_def_kind = ?self.tcx.def_kind(parent_did)); - let is_raw_borrow_inside_fn_like_call = - match self.tcx.def_kind(parent_did) { - DefKind::Fn | DefKind::Ctor(..) => target_ty.is_unsafe_ptr(), - _ => false, - }; - if let Some(typeck_results) = typeck_results { - if (typeck_results.is_method_call(e) && is_region_borrow) - || is_raw_borrow_inside_fn_like_call - { - err.span_help( - parent_span, - "consider moving this into a `let` \ - binding to create a shorter lived borrow", - ); - } - } - } + explain_yield(interior_span, yield_span); } } } @@ -2690,6 +2554,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { | ObligationCauseCode::IfExpressionWithNoElse | ObligationCauseCode::MainFunctionType | ObligationCauseCode::StartFunctionType + | ObligationCauseCode::LangFunctionType(_) | ObligationCauseCode::IntrinsicType | ObligationCauseCode::MethodReceiver | ObligationCauseCode::ReturnNoExpression @@ -2979,6 +2844,24 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { ObligationCauseCode::InlineAsmSized => { err.note("all inline asm arguments must have a statically known size"); } + ObligationCauseCode::SizedClosureCapture(closure_def_id) => { + err.note("all values captured by value by a closure must have a statically known size"); + let hir::ExprKind::Closure(closure) = self.tcx.hir().get_by_def_id(closure_def_id).expect_expr().kind else { + bug!("expected closure in SizedClosureCapture obligation"); + }; + if let hir::CaptureBy::Value = closure.capture_clause + && let Some(span) = closure.fn_arg_span + { + err.span_label(span, "this closure captures all values by move"); + } + } + ObligationCauseCode::SizedGeneratorInterior(generator_def_id) => { + let what = match self.tcx.generator_kind(generator_def_id) { + None | Some(hir::GeneratorKind::Gen) => "yield", + Some(hir::GeneratorKind::Async(..)) => "await", + }; + err.note(format!("all values live across `{what}` must have a statically known size")); + } ObligationCauseCode::ConstPatternStructural => { err.note("constants used for pattern-matching must derive `PartialEq` and `Eq`"); } @@ -3044,20 +2927,7 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } err.span_note(self.tcx.def_span(def_id), msg) } - ty::GeneratorWitness(bound_tys) => { - use std::fmt::Write; - - // FIXME: this is kind of an unusual format for rustc, can we make it more clear? - // Maybe we should just remove this note altogether? - // FIXME: only print types which don't meet the trait requirement - let mut msg = - "required because it captures the following types: ".to_owned(); - for ty in bound_tys.skip_binder() { - with_forced_trimmed_paths!(write!(msg, "`{ty}`, ").unwrap()); - } - err.note(msg.trim_end_matches(", ").to_string()) - } - ty::GeneratorWitnessMIR(def_id, args) => { + ty::GeneratorWitness(def_id, args) => { use std::fmt::Write; // FIXME: this is kind of an unusual format for rustc, can we make it more clear? @@ -4014,6 +3884,201 @@ impl<'tcx> TypeErrCtxtExt<'tcx> for TypeErrCtxt<'_, 'tcx> { } } } + + fn explain_hrtb_projection( + &self, + diag: &mut Diagnostic, + pred: ty::PolyTraitPredicate<'tcx>, + param_env: ty::ParamEnv<'tcx>, + cause: &ObligationCause<'tcx>, + ) { + if pred.skip_binder().has_escaping_bound_vars() && pred.skip_binder().has_non_region_infer() + { + self.probe(|_| { + let ocx = ObligationCtxt::new(self); + let pred = self.instantiate_binder_with_placeholders(pred); + let pred = ocx.normalize(&ObligationCause::dummy(), param_env, pred); + ocx.register_obligation(Obligation::new( + self.tcx, + ObligationCause::dummy(), + param_env, + pred, + )); + if !ocx.select_where_possible().is_empty() { + // encountered errors. + return; + } + + if let ObligationCauseCode::FunctionArgumentObligation { + call_hir_id, + arg_hir_id, + parent_code: _, + } = cause.code() + { + let arg_span = self.tcx.hir().span(*arg_hir_id); + let mut sp: MultiSpan = arg_span.into(); + + sp.push_span_label( + arg_span, + "the trait solver is unable to infer the \ + generic types that should be inferred from this argument", + ); + sp.push_span_label( + self.tcx.hir().span(*call_hir_id), + "add turbofish arguments to this call to \ + specify the types manually, even if it's redundant", + ); + diag.span_note( + sp, + "this is a known limitation of the trait solver that \ + will be lifted in the future", + ); + } else { + let mut sp: MultiSpan = cause.span.into(); + sp.push_span_label( + cause.span, + "try adding turbofish arguments to this expression to \ + specify the types manually, even if it's redundant", + ); + diag.span_note( + sp, + "this is a known limitation of the trait solver that \ + will be lifted in the future", + ); + } + }); + } + } + + fn suggest_desugaring_async_fn_in_trait( + &self, + err: &mut Diagnostic, + trait_ref: ty::PolyTraitRef<'tcx>, + ) { + // Don't suggest if RTN is active -- we should prefer a where-clause bound instead. + if self.tcx.features().return_type_notation { + return; + } + + let trait_def_id = trait_ref.def_id(); + + // Only suggest specifying auto traits + if !self.tcx.trait_is_auto(trait_def_id) { + return; + } + + // Look for an RPITIT + let ty::Alias(ty::Projection, alias_ty) = trait_ref.self_ty().skip_binder().kind() else { + return; + }; + let Some(ty::ImplTraitInTraitData::Trait { fn_def_id, opaque_def_id }) = + self.tcx.opt_rpitit_info(alias_ty.def_id) + else { + return; + }; + + let auto_trait = self.tcx.def_path_str(trait_def_id); + // ... which is a local function + let Some(fn_def_id) = fn_def_id.as_local() else { + // If it's not local, we can at least mention that the method is async, if it is. + if self.tcx.asyncness(fn_def_id).is_async() { + err.span_note( + self.tcx.def_span(fn_def_id), + format!( + "`{}::{}` is an `async fn` in trait, which does not \ + automatically imply that its future is `{auto_trait}`", + alias_ty.trait_ref(self.tcx), + self.tcx.item_name(fn_def_id) + ), + ); + } + return; + }; + let Some(hir::Node::TraitItem(item)) = self.tcx.hir().find_by_def_id(fn_def_id) else { + return; + }; + + // ... whose signature is `async` (i.e. this is an AFIT) + let (sig, body) = item.expect_fn(); + let hir::IsAsync::Async(async_span) = sig.header.asyncness else { + return; + }; + let Ok(async_span) = + self.tcx.sess.source_map().span_extend_while(async_span, |c| c.is_whitespace()) + else { + return; + }; + let hir::FnRetTy::Return(hir::Ty { kind: hir::TyKind::OpaqueDef(def, ..), .. }) = + sig.decl.output + else { + // This should never happen, but let's not ICE. + return; + }; + + // Check that this is *not* a nested `impl Future` RPIT in an async fn + // (i.e. `async fn foo() -> impl Future`) + if def.owner_id.to_def_id() != opaque_def_id { + return; + } + + let future = self.tcx.hir().item(*def).expect_opaque_ty(); + let Some(hir::GenericBound::LangItemTrait(_, _, _, generics)) = future.bounds.get(0) else { + // `async fn` should always lower to a lang item bound... but don't ICE. + return; + }; + let Some(hir::TypeBindingKind::Equality { term: hir::Term::Ty(future_output_ty) }) = + generics.bindings.get(0).map(|binding| binding.kind) + else { + // Also should never happen. + return; + }; + + let function_name = self.tcx.def_path_str(fn_def_id); + + let mut sugg = if future_output_ty.span.is_empty() { + vec![ + (async_span, String::new()), + ( + future_output_ty.span, + format!(" -> impl std::future::Future<Output = ()> + {auto_trait}"), + ), + ] + } else { + vec![ + ( + future_output_ty.span.shrink_to_lo(), + "impl std::future::Future<Output = ".to_owned(), + ), + (future_output_ty.span.shrink_to_hi(), format!("> + {auto_trait}")), + (async_span, String::new()), + ] + }; + + // If there's a body, we also need to wrap it in `async {}` + if let hir::TraitFn::Provided(body) = body { + let body = self.tcx.hir().body(*body); + let body_span = body.value.span; + let body_span_without_braces = + body_span.with_lo(body_span.lo() + BytePos(1)).with_hi(body_span.hi() - BytePos(1)); + if body_span_without_braces.is_empty() { + sugg.push((body_span_without_braces, " async {} ".to_owned())); + } else { + sugg.extend([ + (body_span_without_braces.shrink_to_lo(), "async {".to_owned()), + (body_span_without_braces.shrink_to_hi(), "} ".to_owned()), + ]); + } + } + + err.multipart_suggestion( + format!( + "`{auto_trait}` can be made part of the associated future's \ + guarantees for all implementations of `{function_name}`" + ), + sugg, + Applicability::MachineApplicable, + ); + } } /// Add a hint to add a missing borrow or remove an unnecessary one. diff --git a/compiler/rustc_trait_selection/src/traits/fulfill.rs b/compiler/rustc_trait_selection/src/traits/fulfill.rs index 3ebf1246a..55b5604b1 100644 --- a/compiler/rustc_trait_selection/src/traits/fulfill.rs +++ b/compiler/rustc_trait_selection/src/traits/fulfill.rs @@ -559,30 +559,31 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { let stalled_on = &mut pending_obligation.stalled_on; - let mut evaluate = - |c: Const<'tcx>| { - if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() { - match self.selcx.infcx.try_const_eval_resolve( - obligation.param_env, - unevaluated, - c.ty(), - Some(obligation.cause.span), - ) { - Ok(val) => Ok(val), - Err(e) => match e { - ErrorHandled::TooGeneric => { + let mut evaluate = |c: Const<'tcx>| { + if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() { + match self.selcx.infcx.try_const_eval_resolve( + obligation.param_env, + unevaluated, + c.ty(), + Some(obligation.cause.span), + ) { + Ok(val) => Ok(val), + Err(e) => { + match e { + ErrorHandled::TooGeneric(..) => { stalled_on.extend(unevaluated.args.iter().filter_map( TyOrConstInferVar::maybe_from_generic_arg, )); - Err(ErrorHandled::TooGeneric) } - _ => Err(e), - }, + _ => {} + } + Err(e) } - } else { - Ok(c) } - }; + } else { + Ok(c) + } + }; match (evaluate(c1), evaluate(c2)) { (Ok(c1), Ok(c2)) => { @@ -602,13 +603,14 @@ impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { ), } } - (Err(ErrorHandled::Reported(reported)), _) - | (_, Err(ErrorHandled::Reported(reported))) => ProcessResult::Error( + (Err(ErrorHandled::Reported(reported, _)), _) + | (_, Err(ErrorHandled::Reported(reported, _))) => ProcessResult::Error( CodeSelectionError(SelectionError::NotConstEvaluatable( NotConstEvaluatable::Error(reported.into()), )), ), - (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => { + (Err(ErrorHandled::TooGeneric(_)), _) + | (_, Err(ErrorHandled::TooGeneric(_))) => { if c1.has_non_region_infer() || c2.has_non_region_infer() { ProcessResult::Unchanged } else { diff --git a/compiler/rustc_trait_selection/src/traits/mod.rs b/compiler/rustc_trait_selection/src/traits/mod.rs index d2210c6d5..956f8e047 100644 --- a/compiler/rustc_trait_selection/src/traits/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/mod.rs @@ -288,7 +288,7 @@ pub fn normalize_param_env_or_error<'tcx>( // should actually be okay since without `feature(generic_const_exprs)` the only // const arguments that have a non-empty param env are array repeat counts. These // do not appear in the type system though. - c.eval(self.0, ty::ParamEnv::empty()) + c.normalize(self.0, ty::ParamEnv::empty()) } } diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index 06a1027e5..f7b4794db 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -659,6 +659,18 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx normalized_ty } ty::Weak => { + let recursion_limit = self.interner().recursion_limit(); + if !recursion_limit.value_within_limit(self.depth) { + self.selcx.infcx.err_ctxt().report_overflow_error( + &ty, + self.cause.span, + false, + |diag| { + diag.note(crate::fluent_generated::trait_selection_ty_alias_overflow); + }, + ); + } + let infcx = self.selcx.infcx; self.obligations.extend( infcx.tcx.predicates_of(data.def_id).instantiate_own(infcx.tcx, data.args).map( @@ -678,7 +690,14 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx }, ), ); - infcx.tcx.type_of(data.def_id).instantiate(infcx.tcx, data.args).fold_with(self) + self.depth += 1; + let res = infcx + .tcx + .type_of(data.def_id) + .instantiate(infcx.tcx, data.args) + .fold_with(self); + self.depth -= 1; + res } ty::Inherent if !data.has_escaping_bound_vars() => { @@ -742,7 +761,7 @@ impl<'a, 'b, 'tcx> TypeFolder<TyCtxt<'tcx>> for AssocTypeNormalizer<'a, 'b, 'tcx self.selcx.infcx, &mut self.universes, constant, - |constant| constant.eval(tcx, self.param_env), + |constant| constant.normalize(tcx, self.param_env), ) } } @@ -1214,7 +1233,7 @@ fn opt_normalize_projection_type<'a, 'b, 'tcx>( let projected_term = selcx.infcx.resolve_vars_if_possible(projected_term); - let result = if projected_term.has_projections() { + let mut result = if projected_term.has_projections() { let mut normalizer = AssocTypeNormalizer::new( selcx, param_env, @@ -1224,14 +1243,14 @@ fn opt_normalize_projection_type<'a, 'b, 'tcx>( ); let normalized_ty = normalizer.fold(projected_term); - let mut deduped = SsoHashSet::with_capacity(projected_obligations.len()); - projected_obligations.retain(|obligation| deduped.insert(obligation.clone())); - Normalized { value: normalized_ty, obligations: projected_obligations } } else { Normalized { value: projected_term, obligations: projected_obligations } }; + let mut deduped = SsoHashSet::with_capacity(result.obligations.len()); + result.obligations.retain(|obligation| deduped.insert(obligation.clone())); + if use_cache { infcx.inner.borrow_mut().projection_cache().insert_term(cache_key, result.clone()); } @@ -1625,7 +1644,7 @@ fn assemble_candidates_from_object_ty<'cx, 'tcx>( let env_predicates = data .projection_bounds() .filter(|bound| bound.item_def_id() == obligation.predicate.def_id) - .map(|p| p.with_self_ty(tcx, object_ty).to_predicate(tcx)); + .map(|p| ty::Clause::from_projection_clause(tcx, p.with_self_ty(tcx, object_ty))); assemble_candidates_from_predicates( selcx, @@ -1794,7 +1813,6 @@ fn assemble_candidates_from_impls<'cx, 'tcx>( | ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Tuple(..) // Integers and floats always have `u8` as their discriminant. @@ -1844,7 +1862,6 @@ fn assemble_candidates_from_impls<'cx, 'tcx>( | ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Never // Extern types have unit metadata, according to RFC 2850 | ty::Foreign(_) diff --git a/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs b/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs index 9484a50e3..620b992ee 100644 --- a/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs +++ b/compiler/rustc_trait_selection/src/traits/query/dropck_outlives.rs @@ -36,7 +36,6 @@ pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> bool { | ty::FnPtr(_) | ty::Char | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::RawPtr(_) | ty::Ref(..) | ty::Str @@ -134,7 +133,7 @@ pub fn compute_dropck_outlives_inner<'tcx>( result.overflows.len(), ty_stack.len() ); - dtorck_constraint_for_ty_inner(tcx, DUMMY_SP, for_ty, depth, ty, &mut constraints)?; + dtorck_constraint_for_ty_inner(tcx, param_env, DUMMY_SP, depth, ty, &mut constraints)?; // "outlives" represent types/regions that may be touched // by a destructor. @@ -186,16 +185,15 @@ pub fn compute_dropck_outlives_inner<'tcx>( /// Returns a set of constraints that needs to be satisfied in /// order for `ty` to be valid for destruction. +#[instrument(level = "debug", skip(tcx, param_env, span, constraints))] pub fn dtorck_constraint_for_ty_inner<'tcx>( tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, span: Span, - for_ty: Ty<'tcx>, depth: usize, ty: Ty<'tcx>, constraints: &mut DropckConstraint<'tcx>, ) -> Result<(), NoSolution> { - debug!("dtorck_constraint_for_ty_inner({:?}, {:?}, {:?}, {:?})", span, for_ty, depth, ty); - if !tcx.recursion_limit().value_within_limit(depth) { constraints.overflows.push(ty); return Ok(()); @@ -218,21 +216,20 @@ pub fn dtorck_constraint_for_ty_inner<'tcx>( | ty::Ref(..) | ty::FnDef(..) | ty::FnPtr(_) - | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) => { + | ty::GeneratorWitness(..) => { // these types never have a destructor } ty::Array(ety, _) | ty::Slice(ety) => { // single-element containers, behave like their element rustc_data_structures::stack::ensure_sufficient_stack(|| { - dtorck_constraint_for_ty_inner(tcx, span, for_ty, depth + 1, *ety, constraints) + dtorck_constraint_for_ty_inner(tcx, param_env, span, depth + 1, *ety, constraints) })?; } ty::Tuple(tys) => rustc_data_structures::stack::ensure_sufficient_stack(|| { for ty in tys.iter() { - dtorck_constraint_for_ty_inner(tcx, span, for_ty, depth + 1, ty, constraints)?; + dtorck_constraint_for_ty_inner(tcx, param_env, span, depth + 1, ty, constraints)?; } Ok::<_, NoSolution>(()) })?, @@ -251,7 +248,14 @@ pub fn dtorck_constraint_for_ty_inner<'tcx>( rustc_data_structures::stack::ensure_sufficient_stack(|| { for ty in args.as_closure().upvar_tys() { - dtorck_constraint_for_ty_inner(tcx, span, for_ty, depth + 1, ty, constraints)?; + dtorck_constraint_for_ty_inner( + tcx, + param_env, + span, + depth + 1, + ty, + constraints, + )?; } Ok::<_, NoSolution>(()) })? @@ -280,8 +284,8 @@ pub fn dtorck_constraint_for_ty_inner<'tcx>( // only take place through references with lifetimes // derived from lifetimes attached to the upvars and resume // argument, and we *do* incorporate those here. - - if !args.as_generator().is_valid() { + let args = args.as_generator(); + if !args.is_valid() { // By the time this code runs, all type variables ought to // be fully resolved. tcx.sess.delay_span_bug( @@ -291,10 +295,13 @@ pub fn dtorck_constraint_for_ty_inner<'tcx>( return Err(NoSolution); } - constraints - .outlives - .extend(args.as_generator().upvar_tys().iter().map(ty::GenericArg::from)); - constraints.outlives.push(args.as_generator().resume_ty().into()); + // While we conservatively assume that all coroutines require drop + // to avoid query cycles during MIR building, we can check the actual + // witness during borrowck to avoid unnecessary liveness constraints. + if args.witness().needs_drop(tcx, tcx.erase_regions(param_env)) { + constraints.outlives.extend(args.upvar_tys().iter().map(ty::GenericArg::from)); + constraints.outlives.push(args.resume_ty().into()); + } } ty::Adt(def, args) => { diff --git a/compiler/rustc_trait_selection/src/traits/query/normalize.rs b/compiler/rustc_trait_selection/src/traits/query/normalize.rs index 87beaddc6..f785211c5 100644 --- a/compiler/rustc_trait_selection/src/traits/query/normalize.rs +++ b/compiler/rustc_trait_selection/src/traits/query/normalize.rs @@ -358,7 +358,7 @@ impl<'cx, 'tcx> FallibleTypeFolder<TyCtxt<'tcx>> for QueryNormalizer<'cx, 'tcx> self.infcx, &mut self.universes, constant, - |constant| constant.eval(self.infcx.tcx, self.param_env), + |constant| constant.normalize(self.infcx.tcx, self.param_env), )) } diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs index 979498fb6..e415d7047 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/implied_outlives_bounds.rs @@ -13,7 +13,7 @@ use rustc_span::def_id::CRATE_DEF_ID; use rustc_span::source_map::DUMMY_SP; use smallvec::{smallvec, SmallVec}; -#[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)] +#[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable)] pub struct ImpliedOutlivesBounds<'tcx> { pub ty: Ty<'tcx>, } diff --git a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs index 59f4a22ac..f2c1243f9 100644 --- a/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs +++ b/compiler/rustc_trait_selection/src/traits/query/type_op/outlives.rs @@ -6,7 +6,7 @@ use crate::traits::ObligationCtxt; use rustc_middle::traits::query::{DropckOutlivesResult, NoSolution}; use rustc_middle::ty::{ParamEnvAnd, Ty, TyCtxt}; -#[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable, Lift)] +#[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable)] pub struct DropckOutlives<'tcx> { dropped_ty: Ty<'tcx>, } diff --git a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs index e3da87a22..bead8758a 100644 --- a/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs +++ b/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs @@ -436,8 +436,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | ty::Ref(_, _, _) | ty::Closure(_, _) | ty::Generator(_, _, _) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(_, _) + | ty::GeneratorWitness(..) | ty::Never | ty::Tuple(_) | ty::Error(_) => return true, @@ -569,8 +568,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | ty::Generator(..) | ty::Never | ty::Tuple(_) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) => { + | ty::GeneratorWitness(..) => { // Only consider auto impls if there are no manual impls for the root of `self_ty`. // // For example, we only consider auto candidates for `&i32: Auto` if no explicit impl @@ -946,8 +944,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | ty::Closure(..) | ty::Generator(..) | ty::Tuple(_) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) => { + | ty::GeneratorWitness(..) => { // These are built-in, and cannot have a custom `impl const Destruct`. candidates.vec.push(ConstDestructCandidate(None)); } @@ -1020,8 +1017,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | ty::Dynamic(_, _, _) | ty::Closure(_, _) | ty::Generator(_, _, _) - | ty::GeneratorWitness(_) - | ty::GeneratorWitnessMIR(..) + | ty::GeneratorWitness(..) | ty::Never | ty::Alias(..) | ty::Param(_) @@ -1083,7 +1079,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Tuple(..) | ty::Alias(..) diff --git a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs index 88d030033..08ee9c73b 100644 --- a/compiler/rustc_trait_selection/src/traits/select/confirmation.rs +++ b/compiler/rustc_trait_selection/src/traits/select/confirmation.rs @@ -535,6 +535,9 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let assoc_types: Vec<_> = tcx .associated_items(trait_predicate.def_id()) .in_definition_order() + // 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. + .filter(|item| !tcx.generics_require_sized_self(item.def_id)) .filter_map( |item| if item.kind == ty::AssocKind::Type { Some(item.def_id) } else { None }, ) @@ -548,7 +551,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { obligation.cause.span, "GATs in trait object shouldn't have been considered", ); - return Err(SelectionError::Unimplemented); + return Err(SelectionError::TraitNotObjectSafe(trait_predicate.trait_ref.def_id)); } // This maybe belongs in wf, but that can't (doesn't) handle @@ -1235,10 +1238,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let generator = args.as_generator(); stack.extend([generator.tupled_upvars_ty(), generator.witness()]); } - ty::GeneratorWitness(tys) => { - stack.extend(tcx.erase_late_bound_regions(tys).to_vec()); - } - ty::GeneratorWitnessMIR(def_id, args) => { + ty::GeneratorWitness(def_id, args) => { let tcx = self.tcx(); stack.extend(tcx.generator_hidden_types(def_id).map(|bty| { let ty = bty.instantiate(tcx, args); diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs index 19385e2d7..ec46a6769 100644 --- a/compiler/rustc_trait_selection/src/traits/select/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs @@ -35,7 +35,8 @@ use rustc_hir::def_id::DefId; use rustc_infer::infer::DefineOpaqueTypes; use rustc_infer::infer::LateBoundRegionConversionTime; use rustc_infer::traits::TraitObligation; -use rustc_middle::dep_graph::{DepKind, DepNodeIndex}; +use rustc_middle::dep_graph::dep_kinds; +use rustc_middle::dep_graph::DepNodeIndex; use rustc_middle::mir::interpret::ErrorHandled; use rustc_middle::ty::abstract_const::NotConstEvaluatable; use rustc_middle::ty::fold::BottomUpFolder; @@ -988,9 +989,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { Err(_) => Ok(EvaluatedToErr), } } - (Err(ErrorHandled::Reported(_)), _) - | (_, Err(ErrorHandled::Reported(_))) => Ok(EvaluatedToErr), - (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => { + (Err(ErrorHandled::Reported(..)), _) + | (_, Err(ErrorHandled::Reported(..))) => Ok(EvaluatedToErr), + (Err(ErrorHandled::TooGeneric(..)), _) + | (_, Err(ErrorHandled::TooGeneric(..))) => { if c1.has_non_region_infer() || c2.has_non_region_infer() { Ok(EvaluatedToAmbig) } else { @@ -1415,7 +1417,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { OP: FnOnce(&mut Self) -> R, { let (result, dep_node) = - self.tcx().dep_graph.with_anon_task(self.tcx(), DepKind::TraitSelect, || op(self)); + self.tcx().dep_graph.with_anon_task(self.tcx(), dep_kinds::TraitSelect, || op(self)); self.tcx().dep_graph.read_index(dep_node); (result, dep_node) } @@ -2110,7 +2112,6 @@ impl<'tcx> SelectionContext<'_, 'tcx> { | ty::Ref(..) | ty::Generator(..) | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Array(..) | ty::Closure(..) | ty::Never @@ -2209,22 +2210,7 @@ impl<'tcx> SelectionContext<'_, 'tcx> { } } - ty::GeneratorWitness(binder) => { - let witness_tys = binder.skip_binder(); - for witness_ty in witness_tys.iter() { - let resolved = self.infcx.shallow_resolve(witness_ty); - if resolved.is_ty_var() { - return Ambiguous; - } - } - // (*) binder moved here - let all_vars = self.tcx().mk_bound_variable_kinds_from_iter( - obligation.predicate.bound_vars().iter().chain(binder.bound_vars().iter()), - ); - Where(ty::Binder::bind_with_vars(witness_tys.to_vec(), all_vars)) - } - - ty::GeneratorWitnessMIR(def_id, ref args) => { + ty::GeneratorWitness(def_id, ref args) => { let hidden_types = bind_generator_hidden_types_above( self.infcx, def_id, @@ -2329,12 +2315,7 @@ impl<'tcx> SelectionContext<'_, 'tcx> { t.rebind([ty].into_iter().chain(iter::once(witness)).collect()) } - ty::GeneratorWitness(types) => { - debug_assert!(!types.has_escaping_bound_vars()); - types.map_bound(|types| types.to_vec()) - } - - ty::GeneratorWitnessMIR(def_id, ref args) => { + ty::GeneratorWitness(def_id, ref args) => { bind_generator_hidden_types_above(self.infcx, def_id, args, t.bound_vars()) } @@ -2346,14 +2327,15 @@ impl<'tcx> SelectionContext<'_, 'tcx> { } ty::Alias(ty::Opaque, ty::AliasTy { def_id, args, .. }) => { - let ty = self.tcx().type_of(def_id); - if ty.skip_binder().references_error() { - return Err(SelectionError::OpaqueTypeAutoTraitLeakageUnknown(def_id)); - } // We can resolve the `impl Trait` to its concrete type, // which enforces a DAG between the functions requiring // the auto trait bounds in question. - t.rebind(vec![ty.instantiate(self.tcx(), args)]) + match self.tcx().type_of_opaque(def_id) { + Ok(ty) => t.rebind(vec![ty.instantiate(self.tcx(), args)]), + Err(_) => { + return Err(SelectionError::OpaqueTypeAutoTraitLeakageUnknown(def_id)); + } + } } }) } @@ -3093,32 +3075,33 @@ fn bind_generator_hidden_types_above<'tcx>( .generator_hidden_types(def_id) // Deduplicate tys to avoid repeated work. .filter(|bty| seen_tys.insert(*bty)) - .map(|bty| { - let mut ty = bty.instantiate(tcx, args); - + .map(|mut bty| { // Only remap erased regions if we use them. if considering_regions { - 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), - }; - counter += 1; - ty::Region::new_late_bound(tcx, current_depth, br) - } - r => bug!("unexpected region: {r:?}"), + bty = bty.map_bound(|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, + }; + counter += 1; + ty::Region::new_late_bound(tcx, current_depth, br) + } + r => bug!("unexpected region: {r:?}"), + }) }) } - ty + bty.instantiate(tcx, args) }) .collect(); if considering_regions { debug_assert!(!hidden_types.has_erased_regions()); } - let bound_vars = tcx.mk_bound_variable_kinds_from_iter(bound_vars.iter().chain( - (num_bound_variables..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))), - )); + let bound_vars = + tcx.mk_bound_variable_kinds_from_iter(bound_vars.iter().chain( + (num_bound_variables..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon)), + )); ty::Binder::bind_with_vars(hidden_types, bound_vars) } diff --git a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs index 729cf2f33..efab29743 100644 --- a/compiler/rustc_trait_selection/src/traits/specialize/mod.rs +++ b/compiler/rustc_trait_selection/src/traits/specialize/mod.rs @@ -472,17 +472,11 @@ pub(crate) fn to_pretty_impl_header(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Opti let mut types_without_default_bounds = FxIndexSet::default(); let sized_trait = tcx.lang_items().sized_trait(); - if !args.is_empty() { + let arg_names = args.iter().map(|k| k.to_string()).filter(|k| k != "'_").collect::<Vec<_>>(); + if !arg_names.is_empty() { types_without_default_bounds.extend(args.types()); w.push('<'); - w.push_str( - &args - .iter() - .map(|k| k.to_string()) - .filter(|k| k != "'_") - .collect::<Vec<_>>() - .join(", "), - ); + w.push_str(&arg_names.join(", ")); w.push('>'); } diff --git a/compiler/rustc_trait_selection/src/traits/structural_match.rs b/compiler/rustc_trait_selection/src/traits/structural_match.rs index 0864e4dc8..fc9b42436 100644 --- a/compiler/rustc_trait_selection/src/traits/structural_match.rs +++ b/compiler/rustc_trait_selection/src/traits/structural_match.rs @@ -79,7 +79,7 @@ impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for Search<'tcx> { ty::Closure(..) => { return ControlFlow::Break(ty); } - ty::Generator(..) | ty::GeneratorWitness(..) | ty::GeneratorWitnessMIR(..) => { + ty::Generator(..) | ty::GeneratorWitness(..) => { return ControlFlow::Break(ty); } ty::FnDef(..) => { diff --git a/compiler/rustc_trait_selection/src/traits/structural_normalize.rs b/compiler/rustc_trait_selection/src/traits/structural_normalize.rs index d3c4dc459..9d6be7689 100644 --- a/compiler/rustc_trait_selection/src/traits/structural_normalize.rs +++ b/compiler/rustc_trait_selection/src/traits/structural_normalize.rs @@ -22,9 +22,14 @@ impl<'tcx> StructurallyNormalizeExt<'tcx> for At<'_, 'tcx> { assert!(!ty.is_ty_var(), "should have resolved vars before calling"); if self.infcx.next_trait_solver() { - while let ty::Alias(ty::Projection | ty::Inherent | ty::Weak, projection_ty) = - *ty.kind() - { + // FIXME(-Ztrait-solver=next): correctly handle + // overflow here. + for _ in 0..256 { + let ty::Alias(ty::Projection | ty::Inherent | ty::Weak, projection_ty) = *ty.kind() + else { + break; + }; + let new_infer_ty = self.infcx.next_ty_var(TypeVariableOrigin { kind: TypeVariableOriginKind::NormalizeProjectionType, span: self.cause.span, @@ -49,6 +54,7 @@ impl<'tcx> StructurallyNormalizeExt<'tcx> for At<'_, 'tcx> { break; } } + Ok(ty) } else { Ok(self.normalize(ty).into_value_registering_obligations(self.infcx, fulfill_cx)) diff --git a/compiler/rustc_trait_selection/src/traits/vtable.rs b/compiler/rustc_trait_selection/src/traits/vtable.rs index 427ac3684..e41073937 100644 --- a/compiler/rustc_trait_selection/src/traits/vtable.rs +++ b/compiler/rustc_trait_selection/src/traits/vtable.rs @@ -152,7 +152,7 @@ fn prepare_vtable_segments_inner<'tcx, T>( while let Some((inner_most_trait_ref, emit_vptr, mut siblings)) = stack.pop() { segment_visitor(VtblSegment::TraitOwnEntries { trait_ref: inner_most_trait_ref, - emit_vptr, + emit_vptr: emit_vptr && !tcx.sess.opts.unstable_opts.no_trait_vptr, })?; // If we've emitted (fed to `segment_visitor`) a trait that has methods present in the vtable, diff --git a/compiler/rustc_trait_selection/src/traits/wf.rs b/compiler/rustc_trait_selection/src/traits/wf.rs index f26310665..b04008d9e 100644 --- a/compiler/rustc_trait_selection/src/traits/wf.rs +++ b/compiler/rustc_trait_selection/src/traits/wf.rs @@ -609,7 +609,6 @@ impl<'a, 'tcx> WfPredicates<'a, 'tcx> { | ty::Error(_) | ty::Str | ty::GeneratorWitness(..) - | ty::GeneratorWitnessMIR(..) | ty::Never | ty::Param(_) | ty::Bound(..) |