diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve')
12 files changed, 1580 insertions, 944 deletions
diff --git a/compiler/rustc_trait_selection/src/solve/assembly.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index dec9f8016..10d817f75 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -1,16 +1,21 @@ //! Code shared by trait and projection goals for candidate assembly. -#[cfg(doc)] -use super::trait_goals::structural_traits::*; -use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, MaybeCause, QueryResult}; -use itertools::Itertools; +use super::search_graph::OverflowHandler; +use super::{EvalCtxt, SolverMode}; +use crate::solve::CanonicalResponseExt; +use crate::traits::coherence; +use rustc_data_structures::fx::FxIndexSet; use rustc_hir::def_id::DefId; use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::util::elaborate_predicates; +use rustc_infer::traits::util::elaborate; +use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult}; +use rustc_middle::ty::fast_reject::TreatProjections; use rustc_middle::ty::TypeFoldable; use rustc_middle::ty::{self, Ty, TyCtxt}; use std::fmt::Debug; +pub(super) mod structural_traits; + /// A candidate is a possible way to prove a goal. /// /// It consists of both the `source`, which describes how that goal would be proven, @@ -85,6 +90,8 @@ pub(super) enum CandidateSource { pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq { fn self_ty(self) -> Ty<'tcx>; + fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>; + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self; fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId; @@ -148,6 +155,12 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; + // A type is a `FnPtr` if it is of `FnPtr` type. + fn consider_builtin_fn_ptr_trait_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + // A callable type (a closure, fn def, or fn ptr) is known to implement the `Fn<A>` // family of traits where `A` is given by the signature of the type. fn consider_builtin_fn_trait_candidates( @@ -207,6 +220,16 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable<TyCtxt<'tcx>> + Copy + Eq { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx>; + + fn consider_builtin_destruct_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; + + fn consider_builtin_transmute_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx>; } impl<'tcx> EvalCtxt<'_, 'tcx> { @@ -222,7 +245,9 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if goal.predicate.self_ty().is_ty_var() { return vec![Candidate { source: CandidateSource::BuiltinImpl, - result: self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(), + result: self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + .unwrap(), }]; } @@ -240,14 +265,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.assemble_object_bound_candidates(goal, &mut candidates); + self.assemble_coherence_unknowable_candidates(goal, &mut candidates); + candidates } /// If the self type of a goal is a projection, computing the relevant candidates is difficult. /// /// To deal with this, we first try to normalize the self type and add the candidates for the normalized - /// self type to the list of candidates in case that succeeds. Note that we can't just eagerly return in - /// this case as projections as self types add ` + /// self type to the list of candidates in case that succeeds. We also have to consider candidates with the + /// projection as a self type as well + #[instrument(level = "debug", skip_all)] fn assemble_candidates_after_normalizing_self_ty<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -258,48 +286,52 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else { return }; - self.probe(|this| { - let normalized_ty = this.next_ty_infer(); - let normalizes_to_goal = goal.with( - tcx, - ty::Binder::dummy(ty::ProjectionPredicate { - projection_ty, - term: normalized_ty.into(), - }), - ); - let normalization_certainty = match this.evaluate_goal(normalizes_to_goal) { - Ok((_, certainty)) => certainty, - Err(NoSolution) => return, - }; - let normalized_ty = this.resolve_vars_if_possible(normalized_ty); - - // NOTE: Alternatively we could call `evaluate_goal` here and only have a `Normalized` candidate. - // This doesn't work as long as we use `CandidateSource` in winnowing. - let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); - let normalized_candidates = this.assemble_and_evaluate_candidates(goal); - for mut normalized_candidate in normalized_candidates { - normalized_candidate.result = - normalized_candidate.result.unchecked_map(|mut response| { - // FIXME: This currently hides overflow in the normalization step of the self type - // which is probably wrong. Maybe `unify_and` should actually keep overflow as - // we treat it as non-fatal anyways. - response.certainty = response.certainty.unify_and(normalization_certainty); - response - }); - candidates.push(normalized_candidate); - } - }) + + let normalized_self_candidates: Result<_, NoSolution> = self.probe(|ecx| { + ecx.with_incremented_depth( + |ecx| { + let result = ecx.evaluate_added_goals_and_make_canonical_response( + Certainty::Maybe(MaybeCause::Overflow), + )?; + Ok(vec![Candidate { source: CandidateSource::BuiltinImpl, result }]) + }, + |ecx| { + let normalized_ty = ecx.next_ty_infer(); + let normalizes_to_goal = goal.with( + tcx, + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty, + term: normalized_ty.into(), + }), + ); + ecx.add_goal(normalizes_to_goal); + let _ = ecx.try_evaluate_added_goals()?; + let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty); + // NOTE: Alternatively we could call `evaluate_goal` here and only + // have a `Normalized` candidate. This doesn't work as long as we + // use `CandidateSource` in winnowing. + let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); + Ok(ecx.assemble_and_evaluate_candidates(goal)) + }, + ) + }); + + if let Ok(normalized_self_candidates) = normalized_self_candidates { + candidates.extend(normalized_self_candidates); + } } + #[instrument(level = "debug", skip_all)] fn assemble_impl_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, candidates: &mut Vec<Candidate<'tcx>>, ) { let tcx = self.tcx(); - tcx.for_each_relevant_impl( + tcx.for_each_relevant_impl_treating_projections( goal.predicate.trait_def_id(tcx), goal.predicate.self_ty(), + TreatProjections::NextSolverLookup, |impl_def_id| match G::consider_impl_candidate(self, goal, impl_def_id) { Ok(result) => candidates .push(Candidate { source: CandidateSource::Impl(impl_def_id), result }), @@ -308,6 +340,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ); } + #[instrument(level = "debug", skip_all)] fn assemble_builtin_impl_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -315,6 +348,14 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) { let lang_items = self.tcx().lang_items(); let trait_def_id = goal.predicate.trait_def_id(self.tcx()); + + // N.B. When assembling built-in candidates for lang items that are also + // `auto` traits, then the auto trait candidate that is assembled in + // `consider_auto_trait_candidate` MUST be disqualified to remain sound. + // + // Instead of adding the logic here, it's a better idea to add it in + // `EvalCtxt::disqualify_auto_trait_candidate_due_to_possible_impl` in + // `solve::trait_goals` instead. let result = if self.tcx().trait_is_auto(trait_def_id) { G::consider_auto_trait_candidate(self, goal) } else if self.tcx().trait_is_alias(trait_def_id) { @@ -327,6 +368,8 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { G::consider_builtin_copy_clone_candidate(self, goal) } else if lang_items.pointer_like() == Some(trait_def_id) { G::consider_builtin_pointer_like_candidate(self, goal) + } else if lang_items.fn_ptr_trait() == Some(trait_def_id) { + G::consider_builtin_fn_ptr_trait_candidate(self, goal) } else if let Some(kind) = self.tcx().fn_trait_kind_from_def_id(trait_def_id) { G::consider_builtin_fn_trait_candidates(self, goal, kind) } else if lang_items.tuple_trait() == Some(trait_def_id) { @@ -341,6 +384,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { G::consider_builtin_unsize_candidate(self, goal) } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) { G::consider_builtin_discriminant_kind_candidate(self, goal) + } else if lang_items.destruct_trait() == Some(trait_def_id) { + G::consider_builtin_destruct_candidate(self, goal) + } else if lang_items.transmute_trait() == Some(trait_def_id) { + G::consider_builtin_transmute_candidate(self, goal) } else { Err(NoSolution) }; @@ -361,6 +408,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } + #[instrument(level = "debug", skip_all)] fn assemble_param_env_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -376,6 +424,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } + #[instrument(level = "debug", skip_all)] fn assemble_alias_bound_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -423,6 +472,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } + #[instrument(level = "debug", skip_all)] fn assemble_object_bound_candidates<G: GoalKind<'tcx>>( &mut self, goal: Goal<'tcx, G>, @@ -461,10 +511,25 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }; let tcx = self.tcx(); - for assumption in - elaborate_predicates(tcx, bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty))) + let own_bounds: FxIndexSet<_> = + bounds.iter().map(|bound| bound.with_self_ty(tcx, self_ty)).collect(); + for assumption in elaborate(tcx, own_bounds.iter().copied()) + // we only care about bounds that match the `Self` type + .filter_only_self() { - match G::consider_object_bound_candidate(self, goal, assumption.predicate) { + // FIXME: Predicates are fully elaborated in the object type's existential bounds + // list. We want to only consider these pre-elaborated projections, and not other + // projection predicates that we reach by elaborating the principal trait ref, + // since that'll cause ambiguity. + // + // We can remove this when we have implemented intersections in responses. + if assumption.to_opt_poly_projection_pred().is_some() + && !own_bounds.contains(&assumption) + { + continue; + } + + match G::consider_object_bound_candidate(self, goal, assumption) { Ok(result) => { candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) } @@ -473,78 +538,68 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } - #[instrument(level = "debug", skip(self), ret)] - pub(super) fn merge_candidates_and_discard_reservation_impls( + #[instrument(level = "debug", skip_all)] + fn assemble_coherence_unknowable_candidates<G: GoalKind<'tcx>>( &mut self, - mut candidates: Vec<Candidate<'tcx>>, - ) -> QueryResult<'tcx> { - match candidates.len() { - 0 => return Err(NoSolution), - 1 => return Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result), - _ => {} - } - - if candidates.len() > 1 { - let mut i = 0; - 'outer: while i < candidates.len() { - for j in (0..candidates.len()).filter(|&j| i != j) { - if self.trait_candidate_should_be_dropped_in_favor_of( - &candidates[i], - &candidates[j], - ) { - debug!(candidate = ?candidates[i], "Dropping candidate #{}/{}", i, candidates.len()); - candidates.swap_remove(i); - continue 'outer; - } + goal: Goal<'tcx, G>, + candidates: &mut Vec<Candidate<'tcx>>, + ) { + match self.solver_mode() { + SolverMode::Normal => return, + SolverMode::Coherence => { + let trait_ref = goal.predicate.trait_ref(self.tcx()); + match coherence::trait_ref_is_knowable(self.tcx(), trait_ref) { + Ok(()) => {} + Err(_) => match self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + { + Ok(result) => candidates + .push(Candidate { source: CandidateSource::BuiltinImpl, result }), + // FIXME: This will be reachable at some point if we're in + // `assemble_candidates_after_normalizing_self_ty` and we get a + // universe error. We'll deal with it at this point. + Err(NoSolution) => bug!("coherence candidate resulted in NoSolution"), + }, } - - debug!(candidate = ?candidates[i], "Retaining candidate #{}/{}", i, candidates.len()); - i += 1; - } - - // If there are *STILL* multiple candidates that have *different* response - // results, give up and report ambiguity. - if candidates.len() > 1 && !candidates.iter().map(|cand| cand.result).all_equal() { - let certainty = if candidates.iter().all(|x| { - matches!(x.result.value.certainty, Certainty::Maybe(MaybeCause::Overflow)) - }) { - Certainty::Maybe(MaybeCause::Overflow) - } else { - Certainty::AMBIGUOUS - }; - return self.make_canonical_response(certainty); } } - - // FIXME: What if there are >1 candidates left with the same response, and one is a reservation impl? - Ok(self.discard_reservation_impl(candidates.pop().unwrap()).result) } - fn trait_candidate_should_be_dropped_in_favor_of( - &self, - candidate: &Candidate<'tcx>, - other: &Candidate<'tcx>, - ) -> bool { - // FIXME: implement this - match (candidate.source, other.source) { - (CandidateSource::Impl(_), _) - | (CandidateSource::ParamEnv(_), _) - | (CandidateSource::AliasBound, _) - | (CandidateSource::BuiltinImpl, _) => false, + /// If there are multiple ways to prove a trait or projection goal, we have + /// to somehow try to merge the candidates into one. If that fails, we return + /// ambiguity. + #[instrument(level = "debug", skip(self), ret)] + pub(super) fn merge_candidates( + &mut self, + mut candidates: Vec<Candidate<'tcx>>, + ) -> QueryResult<'tcx> { + // First try merging all candidates. This is complete and fully sound. + let responses = candidates.iter().map(|c| c.result).collect::<Vec<_>>(); + if let Some(result) = self.try_merge_responses(&responses) { + return Ok(result); } - } - fn discard_reservation_impl(&self, mut candidate: Candidate<'tcx>) -> Candidate<'tcx> { - if let CandidateSource::Impl(def_id) = candidate.source { - if let ty::ImplPolarity::Reservation = self.tcx().impl_polarity(def_id) { - debug!("Selected reservation impl"); - // We assemble all candidates inside of a probe so by - // making a new canonical response here our result will - // have no constraints. - candidate.result = self.make_canonical_response(Certainty::AMBIGUOUS).unwrap(); + // We then check whether we should prioritize `ParamEnv` candidates. + // + // Doing so is incomplete and would therefore be unsound during coherence. + match self.solver_mode() { + SolverMode::Coherence => (), + // Prioritize `ParamEnv` candidates only if they do not guide inference. + // + // This is still incomplete as we may add incorrect region bounds. + SolverMode::Normal => { + let param_env_responses = candidates + .iter() + .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_))) + .map(|c| c.result) + .collect::<Vec<_>>(); + if let Some(result) = self.try_merge_responses(¶m_env_responses) { + if result.has_only_region_constraints() { + return Ok(result); + } + } } } - - candidate + self.flounder(&responses) } } diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs index d7d93377c..1a566e87d 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -1,7 +1,9 @@ use rustc_data_structures::fx::FxHashMap; use rustc_hir::{def_id::DefId, Movability, Mutability}; use rustc_infer::traits::query::NoSolution; -use rustc_middle::ty::{self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable}; +use rustc_middle::ty::{ + self, Ty, TyCtxt, TypeFoldable, TypeFolder, TypeSuperFoldable, TypeVisitableExt, +}; use crate::solve::EvalCtxt; @@ -9,7 +11,7 @@ use crate::solve::EvalCtxt; // // For types with an "existential" binder, i.e. generator witnesses, we also // instantiate the binder with placeholders eagerly. -pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( +pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { @@ -22,21 +24,19 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( | ty::FnDef(..) | ty::FnPtr(_) | ty::Error(_) - | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Never | ty::Char => Ok(vec![]), - // Treat this like `struct str([u8]);` + // Treat `str` like it's defined as `struct str([u8]);` ty::Str => Ok(vec![tcx.mk_slice(tcx.types.u8)]), ty::Dynamic(..) | ty::Param(..) | ty::Foreign(..) | ty::Alias(ty::Projection, ..) - | ty::Placeholder(..) => Err(NoSolution), - - ty::Bound(..) - | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { + | ty::Placeholder(..) + | ty::Bound(..) + | ty::Infer(_) => { bug!("unexpected type `{ty}`") } @@ -60,7 +60,16 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), - ty::GeneratorWitnessMIR(..) => todo!(), + ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx + .tcx() + .generator_hidden_types(def_id) + .map(|bty| { + ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars( + tcx, + bty.subst(tcx, substs), + )) + }) + .collect()), // For `PhantomData<T>`, we pass `T`. ty::Adt(def, substs) if def.is_phantom_data() => Ok(vec![substs.type_at(0)]), @@ -76,7 +85,28 @@ pub(super) fn instantiate_constituent_tys_for_auto_trait<'tcx>( } } -pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>( +pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, +) -> ty::Binder<'tcx, Ty<'tcx>> { + debug_assert!(!ty.has_late_bound_regions()); + let mut counter = 0; + let ty = tcx.fold_regions(ty, |mut r, current_depth| { + if let ty::ReErased = r.kind() { + let br = + ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) }; + counter += 1; + r = tcx.mk_re_late_bound(current_depth, br); + } + r + }); + let bound_vars = tcx.mk_bound_variable_kinds_from_iter( + (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))), + ); + ty::Binder::bind_with_vars(ty, bound_vars) +} + +pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { @@ -126,7 +156,7 @@ pub(super) fn instantiate_constituent_tys_for_sized_trait<'tcx>( } } -pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( +pub(in crate::solve) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, ty: Ty<'tcx>, ) -> Result<Vec<Ty<'tcx>>, NoSolution> { @@ -178,29 +208,65 @@ pub(super) fn instantiate_constituent_tys_for_copy_clone_trait<'tcx>( ty::GeneratorWitness(types) => Ok(ecx.instantiate_binder_with_placeholders(types).to_vec()), - ty::GeneratorWitnessMIR(..) => todo!(), + ty::GeneratorWitnessMIR(def_id, substs) => Ok(ecx + .tcx() + .generator_hidden_types(def_id) + .map(|bty| { + ecx.instantiate_binder_with_placeholders(replace_erased_lifetimes_with_bound_vars( + ecx.tcx(), + bty.subst(ecx.tcx(), substs), + )) + }) + .collect()), } } // Returns a binder of the tupled inputs types and output type from a builtin callable type. -pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( +pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>, goal_kind: ty::ClosureKind, ) -> Result<Option<ty::Binder<'tcx, (Ty<'tcx>, Ty<'tcx>)>>, NoSolution> { match *self_ty.kind() { - ty::FnDef(def_id, substs) => Ok(Some( - tcx.fn_sig(def_id) - .subst(tcx, substs) - .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), - )), - ty::FnPtr(sig) => Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))), + // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed. + ty::FnDef(def_id, substs) => { + let sig = tcx.fn_sig(def_id); + if sig.skip_binder().is_fn_trait_compatible() + && tcx.codegen_fn_attrs(def_id).target_features.is_empty() + { + Ok(Some( + sig.subst(tcx, substs) + .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), + )) + } else { + Err(NoSolution) + } + } + // keep this in sync with assemble_fn_pointer_candidates until the old solver is removed. + ty::FnPtr(sig) => { + if sig.is_fn_trait_compatible() { + Ok(Some(sig.map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())))) + } else { + Err(NoSolution) + } + } ty::Closure(_, substs) => { let closure_substs = substs.as_closure(); match closure_substs.kind_ty().to_opt_closure_kind() { - Some(closure_kind) if closure_kind.extends(goal_kind) => {} - None => return Ok(None), - _ => return Err(NoSolution), + // If the closure's kind doesn't extend the goal kind, + // then the closure doesn't implement the trait. + Some(closure_kind) => { + if !closure_kind.extends(goal_kind) { + return Err(NoSolution); + } + } + // Closure kind is not yet determined, so we return ambiguity unless + // the expected kind is `FnOnce` as that is always implemented. + None => { + if goal_kind != ty::ClosureKind::FnOnce { + return Ok(None); + } + } } Ok(Some(closure_substs.sig().map_bound(|sig| (sig.inputs()[0], sig.output())))) } @@ -269,7 +335,13 @@ pub(crate) fn extract_tupled_inputs_and_output_from_callable<'tcx>( /// additional step of eagerly folding the associated types in the where /// clauses of the impl. In this example, that means replacing /// `<Self as Foo>::Bar` with `Ty` in the first impl. -pub(crate) fn predicates_for_object_candidate<'tcx>( +/// +// FIXME: This is only necessary as `<Self as Trait>::Assoc: ItemBound` +// bounds in impls are trivially proven using the item bound candidates. +// This is unsound in general and once that is fixed, we don't need to +// normalize eagerly here. See https://github.com/lcnr/solver-woes/issues/9 +// for more details. +pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( ecx: &EvalCtxt<'_, 'tcx>, param_env: ty::ParamEnv<'tcx>, trait_ref: ty::TraitRef<'tcx>, @@ -333,7 +405,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for ReplaceProjectionWith<'_, 'tcx> { // FIXME: Technically this folder could be fallible? let nested = self .ecx - .eq(self.param_env, alias_ty, proj.projection_ty) + .eq_and_get_goals(self.param_env, alias_ty, proj.projection_ty) .expect("expected to be able to unify goal projection with dyn's projection"); // FIXME: Technically we could register these too.. assert!(nested.is_empty(), "did not expect unification to have any nested goals"); diff --git a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs b/compiler/rustc_trait_selection/src/solve/canonicalize.rs index c048d4a2a..976849696 100644 --- a/compiler/rustc_trait_selection/src/solve/canonical/canonicalize.rs +++ b/compiler/rustc_trait_selection/src/solve/canonicalize.rs @@ -13,7 +13,7 @@ use rustc_middle::ty::TypeVisitableExt; use rustc_middle::ty::{self, Ty}; use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable}; -/// Whether we're canonicalizing a query input or the query reponse. +/// Whether we're canonicalizing a query input or the query response. /// /// When canonicalizing an input we're in the context of the caller /// while canonicalizing the response happens in the context of the @@ -21,7 +21,7 @@ use rustc_middle::ty::{TypeFoldable, TypeFolder, TypeSuperFoldable}; #[derive(Debug, Clone, Copy)] pub enum CanonicalizeMode { Input, - /// FIXME: We currently return region constraints refering to + /// FIXME: We currently return region constraints referring to /// placeholders and inference variables from a binder instantiated /// inside of the query. /// @@ -125,8 +125,9 @@ impl<'a, 'tcx> Canonicalizer<'a, 'tcx> { // - var_infos: [E0, U1, E1, U1, E1, E6, U6], curr_compressed_uv: 1, next_orig_uv: 6 // - var_infos: [E0, U1, E1, U1, E1, E2, U2], curr_compressed_uv: 2, next_orig_uv: - // - // This algorithm runs in `O(n²)` where `n` is the number of different universe - // indices in the input. This should be fine as `n` is expected to be small. + // This algorithm runs in `O(nm)` where `n` is the number of different universe + // indices in the input and `m` is the number of canonical variables. + // This should be fine as both `n` and `m` are expected to be small. let mut curr_compressed_uv = ty::UniverseIndex::ROOT; let mut existential_in_new_uv = false; let mut next_orig_uv = Some(ty::UniverseIndex::ROOT); @@ -245,42 +246,49 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { ty::ReError(_) => return r, }; - let existing_bound_var = match self.canonicalize_mode { - CanonicalizeMode::Input => None, - CanonicalizeMode::Response { .. } => { - self.variables.iter().position(|&v| v == r.into()).map(ty::BoundVar::from) - } - }; - let var = existing_bound_var.unwrap_or_else(|| { - let var = ty::BoundVar::from(self.variables.len()); - self.variables.push(r.into()); - self.primitive_var_infos.push(CanonicalVarInfo { kind }); - var - }); - let br = ty::BoundRegion { var, kind: BrAnon(var.as_u32(), None) }; + let var = ty::BoundVar::from( + self.variables.iter().position(|&v| v == r.into()).unwrap_or_else(|| { + let var = self.variables.len(); + self.variables.push(r.into()); + self.primitive_var_infos.push(CanonicalVarInfo { kind }); + var + }), + ); + let br = ty::BoundRegion { var, kind: BrAnon(None) }; self.interner().mk_re_late_bound(self.binder_index, br) } - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + fn fold_ty(&mut self, mut t: Ty<'tcx>) -> Ty<'tcx> { let kind = match *t.kind() { - ty::Infer(ty::TyVar(vid)) => match self.infcx.probe_ty_var(vid) { - Ok(t) => return self.fold_ty(t), - Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), - }, - ty::Infer(ty::IntVar(_)) => { - let nt = self.infcx.shallow_resolve(t); + ty::Infer(ty::TyVar(mut vid)) => { + // We need to canonicalize the *root* of our ty var. + // This is so that our canonical response correctly reflects + // any equated inference vars correctly! + let root_vid = self.infcx.root_var(vid); + if root_vid != vid { + t = self.infcx.tcx.mk_ty_var(root_vid); + vid = root_vid; + } + + match self.infcx.probe_ty_var(vid) { + Ok(t) => return self.fold_ty(t), + Err(ui) => CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)), + } + } + ty::Infer(ty::IntVar(vid)) => { + let nt = self.infcx.opportunistic_resolve_int_var(vid); if nt != t { return self.fold_ty(nt); } else { CanonicalVarKind::Ty(CanonicalTyVarKind::Int) } } - ty::Infer(ty::FloatVar(_)) => { - let nt = self.infcx.shallow_resolve(t); + ty::Infer(ty::FloatVar(vid)) => { + let nt = self.infcx.opportunistic_resolve_float_var(vid); if nt != t { return self.fold_ty(nt); } else { - CanonicalVarKind::Ty(CanonicalTyVarKind::Int) + CanonicalVarKind::Ty(CanonicalTyVarKind::Float) } } ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { @@ -289,14 +297,20 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { ty::Placeholder(placeholder) => match self.canonicalize_mode { CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { universe: placeholder.universe, - name: BoundTyKind::Anon(self.variables.len() as u32), + bound: ty::BoundTy { + var: ty::BoundVar::from_usize(self.variables.len()), + kind: ty::BoundTyKind::Anon, + }, }), CanonicalizeMode::Response { .. } => CanonicalVarKind::PlaceholderTy(placeholder), }, ty::Param(_) => match self.canonicalize_mode { CanonicalizeMode::Input => CanonicalVarKind::PlaceholderTy(ty::Placeholder { universe: ty::UniverseIndex::ROOT, - name: ty::BoundTyKind::Anon(self.variables.len() as u32), + bound: ty::BoundTy { + var: ty::BoundVar::from_usize(self.variables.len()), + kind: ty::BoundTyKind::Anon, + }, }), CanonicalizeMode::Response { .. } => bug!("param ty in response: {t:?}"), }, @@ -334,17 +348,27 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { var }), ); - let bt = ty::BoundTy { var, kind: BoundTyKind::Anon(var.index() as u32) }; + let bt = ty::BoundTy { var, kind: BoundTyKind::Anon }; self.interner().mk_bound(self.binder_index, bt) } - fn fold_const(&mut self, c: ty::Const<'tcx>) -> ty::Const<'tcx> { + fn fold_const(&mut self, mut c: ty::Const<'tcx>) -> ty::Const<'tcx> { let kind = match c.kind() { - ty::ConstKind::Infer(ty::InferConst::Var(vid)) => match self.infcx.probe_const_var(vid) - { - Ok(c) => return self.fold_const(c), - Err(universe) => CanonicalVarKind::Const(universe, c.ty()), - }, + ty::ConstKind::Infer(ty::InferConst::Var(mut vid)) => { + // We need to canonicalize the *root* of our const var. + // This is so that our canonical response correctly reflects + // any equated inference vars correctly! + let root_vid = self.infcx.root_const_var(vid); + if root_vid != vid { + c = self.infcx.tcx.mk_const(ty::InferConst::Var(root_vid), c.ty()); + vid = root_vid; + } + + match self.infcx.probe_const_var(vid) { + Ok(c) => return self.fold_const(c), + Err(universe) => CanonicalVarKind::Const(universe, c.ty()), + } + } ty::ConstKind::Infer(ty::InferConst::Fresh(_)) => { bug!("fresh var during canonicalization: {c:?}") } @@ -352,7 +376,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( ty::Placeholder { universe: placeholder.universe, - name: ty::BoundVar::from(self.variables.len()), + bound: ty::BoundVar::from(self.variables.len()), }, c.ty(), ), @@ -364,7 +388,7 @@ impl<'tcx> TypeFolder<TyCtxt<'tcx>> for Canonicalizer<'_, 'tcx> { CanonicalizeMode::Input => CanonicalVarKind::PlaceholderConst( ty::Placeholder { universe: ty::UniverseIndex::ROOT, - name: ty::BoundVar::from(self.variables.len()), + bound: ty::BoundVar::from(self.variables.len()), }, c.ty(), ), diff --git a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs index 95612674e..c29b5b04e 100644 --- a/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt.rs @@ -2,10 +2,13 @@ use rustc_hir::def_id::DefId; use rustc_infer::infer::at::ToTrace; use rustc_infer::infer::canonical::CanonicalVarValues; use rustc_infer::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; -use rustc_infer::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; +use rustc_infer::infer::{ + DefineOpaqueTypes, InferCtxt, InferOk, LateBoundRegionConversionTime, TyCtxtInferExt, +}; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::ObligationCause; use rustc_middle::infer::unify_key::{ConstVariableOrigin, ConstVariableOriginKind}; +use rustc_middle::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult}; use rustc_middle::ty::{ self, Ty, TyCtxt, TypeFoldable, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor, @@ -13,12 +16,32 @@ use rustc_middle::ty::{ use rustc_span::DUMMY_SP; use std::ops::ControlFlow; -use super::search_graph::SearchGraph; -use super::Goal; +use crate::traits::specialization_graph; + +use super::search_graph::{self, OverflowHandler}; +use super::SolverMode; +use super::{search_graph::SearchGraph, Goal}; + +mod canonical; pub struct EvalCtxt<'a, 'tcx> { - // FIXME: should be private. - pub(super) infcx: &'a InferCtxt<'tcx>, + /// The inference context that backs (mostly) inference and placeholder terms + /// instantiated while solving goals. + /// + /// NOTE: The `InferCtxt` that backs the `EvalCtxt` is intentionally private, + /// because the `InferCtxt` is much more general than `EvalCtxt`. Methods such + /// as `take_registered_region_obligations` can mess up query responses, + /// using `At::normalize` is totally wrong, calling `evaluate_root_goal` can + /// cause coinductive unsoundness, etc. + /// + /// Methods that are generally of use for trait solving are *intentionally* + /// re-declared through the `EvalCtxt` below, often with cleaner signatures + /// since we don't care about things like `ObligationCause`s and `Span`s here. + /// If some `InferCtxt` method is missing, please first think defensively about + /// the method's compatibility with this solver, or if an existing one does + /// the job already. + infcx: &'a InferCtxt<'tcx>, + pub(super) var_values: CanonicalVarValues<'tcx>, /// The highest universe index nameable by the caller. /// @@ -33,14 +56,356 @@ pub struct EvalCtxt<'a, 'tcx> { pub(super) search_graph: &'a mut SearchGraph<'tcx>, - /// This field is used by a debug assertion in [`EvalCtxt::evaluate_goal`], - /// see the comment in that method for more details. - pub in_projection_eq_hack: bool, + pub(super) nested_goals: NestedGoals<'tcx>, +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub(super) enum IsNormalizesToHack { + Yes, + No, +} + +#[derive(Debug, Clone)] +pub(super) struct NestedGoals<'tcx> { + /// This normalizes-to goal that is treated specially during the evaluation + /// loop. In each iteration we take the RHS of the projection, replace it with + /// a fresh inference variable, and only after evaluating that goal do we + /// equate the fresh inference variable with the actual RHS of the predicate. + /// + /// This is both to improve caching, and to avoid using the RHS of the + /// projection predicate to influence the normalizes-to candidate we select. + /// + /// This is not a 'real' nested goal. We must not forget to replace the RHS + /// with a fresh inference variable when we evaluate this goal. That can result + /// in a trait solver cycle. This would currently result in overflow but can be + /// can be unsound with more powerful coinduction in the future. + pub(super) normalizes_to_hack_goal: Option<Goal<'tcx, ty::ProjectionPredicate<'tcx>>>, + /// The rest of the goals which have not yet processed or remain ambiguous. + pub(super) goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, +} + +impl NestedGoals<'_> { + pub(super) fn new() -> Self { + Self { normalizes_to_hack_goal: None, goals: Vec::new() } + } + + pub(super) fn is_empty(&self) -> bool { + self.normalizes_to_hack_goal.is_none() && self.goals.is_empty() + } +} + +pub trait InferCtxtEvalExt<'tcx> { + /// Evaluates a goal from **outside** of the trait solver. + /// + /// Using this while inside of the solver is wrong as it uses a new + /// search graph which would break cycle detection. + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution>; +} + +impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { + #[instrument(level = "debug", skip(self), ret)] + fn evaluate_root_goal( + &self, + goal: Goal<'tcx, ty::Predicate<'tcx>>, + ) -> Result<(bool, Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { + let mode = if self.intercrate { SolverMode::Coherence } else { SolverMode::Normal }; + let mut search_graph = search_graph::SearchGraph::new(self.tcx, mode); + + let mut ecx = EvalCtxt { + search_graph: &mut search_graph, + infcx: self, + // Only relevant when canonicalizing the response. + max_input_universe: ty::UniverseIndex::ROOT, + var_values: CanonicalVarValues::dummy(), + nested_goals: NestedGoals::new(), + }; + let result = ecx.evaluate_goal(IsNormalizesToHack::No, goal); + + assert!( + ecx.nested_goals.is_empty(), + "root `EvalCtxt` should not have any goals added to it" + ); + + assert!(search_graph.is_empty()); + result + } +} + +impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { + pub(super) fn solver_mode(&self) -> SolverMode { + self.search_graph.solver_mode() + } + + /// The entry point of the solver. + /// + /// This function deals with (coinductive) cycles, overflow, and caching + /// and then calls [`EvalCtxt::compute_goal`] which contains the actual + /// logic of the solver. + /// + /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal] + /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're + /// outside of it. + #[instrument(level = "debug", skip(tcx, search_graph), ret)] + fn evaluate_canonical_goal( + tcx: TyCtxt<'tcx>, + search_graph: &'a mut search_graph::SearchGraph<'tcx>, + canonical_goal: CanonicalGoal<'tcx>, + ) -> QueryResult<'tcx> { + // Deal with overflow, caching, and coinduction. + // + // The actual solver logic happens in `ecx.compute_goal`. + search_graph.with_new_goal(tcx, canonical_goal, |search_graph| { + let intercrate = match search_graph.solver_mode() { + SolverMode::Normal => false, + SolverMode::Coherence => true, + }; + let (ref infcx, goal, var_values) = tcx + .infer_ctxt() + .intercrate(intercrate) + .build_with_canonical(DUMMY_SP, &canonical_goal); + let mut ecx = EvalCtxt { + infcx, + var_values, + max_input_universe: canonical_goal.max_universe, + search_graph, + nested_goals: NestedGoals::new(), + }; + ecx.compute_goal(goal) + }) + } + + /// 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: 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 canonical_response = + EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; + + let has_changed = !canonical_response.value.var_values.is_identity(); + let (certainty, nested_goals) = self.instantiate_and_apply_query_response( + goal.param_env, + orig_values, + canonical_response, + )?; + + if !has_changed && !nested_goals.is_empty() { + bug!("an unchanged goal shouldn't have any side-effects on instantiation"); + } + + // Check that rerunning this query with its inference constraints applied + // doesn't result in new inference constraints and has the same result. + // + // If we have projection goals like `<T as Trait>::Assoc == u32` we recursively + // call `exists<U> <T as Trait>::Assoc == U` to enable better caching. This goal + // could constrain `U` to `u32` which would cause this check to result in a + // solver cycle. + if cfg!(debug_assertions) + && has_changed + && is_normalizes_to_hack == IsNormalizesToHack::No + && !self.search_graph.in_cycle() + { + debug!("rerunning goal to check result is stable"); + let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); + let canonical_response = + EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; + if !canonical_response.value.var_values.is_identity() { + bug!( + "unstable result: re-canonicalized goal={canonical_goal:#?} \ + response={canonical_response:#?}" + ); + } + if certainty != canonical_response.value.certainty { + bug!( + "unstable certainty: {certainty:#?} re-canonicalized goal={canonical_goal:#?} \ + response={canonical_response:#?}" + ); + } + } + + Ok((has_changed, certainty, nested_goals)) + } + + fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { + let Goal { param_env, predicate } = goal; + let kind = predicate.kind(); + if let Some(kind) = kind.no_bound_vars() { + match kind { + ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => { + self.compute_trait_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => { + self.compute_projection_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => { + self.compute_type_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => { + self.compute_region_outlives_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { + self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) + } + ty::PredicateKind::Subtype(predicate) => { + self.compute_subtype_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::Coerce(predicate) => { + self.compute_coerce_goal(Goal { param_env, predicate }) + } + ty::PredicateKind::ClosureKind(def_id, substs, kind) => self + .compute_closure_kind_goal(Goal { + param_env, + predicate: (def_id, substs, kind), + }), + ty::PredicateKind::ObjectSafe(trait_def_id) => { + self.compute_object_safe_goal(trait_def_id) + } + ty::PredicateKind::WellFormed(arg) => { + self.compute_well_formed_goal(Goal { param_env, predicate: arg }) + } + ty::PredicateKind::Ambiguous => { + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) + } + // FIXME: implement these predicates :) + ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => { + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + ty::PredicateKind::TypeWellFormedFromEnv(..) => { + bug!("TypeWellFormedFromEnv is only used for Chalk") + } + ty::PredicateKind::AliasRelate(lhs, rhs, direction) => self + .compute_alias_relate_goal(Goal { + param_env, + predicate: (lhs, rhs, direction), + }), + } + } else { + let kind = self.infcx.instantiate_binder_with_placeholders(kind); + let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); + self.add_goal(goal); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + } + + // Recursively evaluates all the goals added to this `EvalCtxt` to completion, returning + // the certainty of all the goals. + #[instrument(level = "debug", skip(self))] + pub(super) fn try_evaluate_added_goals(&mut self) -> Result<Certainty, NoSolution> { + let mut goals = core::mem::replace(&mut self.nested_goals, NestedGoals::new()); + let mut new_goals = NestedGoals::new(); + + let response = self.repeat_while_none( + |_| Ok(Certainty::Maybe(MaybeCause::Overflow)), + |this| { + let mut has_changed = Err(Certainty::Yes); + + if let Some(goal) = goals.normalizes_to_hack_goal.take() { + // Replace the goal with an unconstrained infer var, so the + // RHS does not affect projection candidate assembly. + let unconstrained_rhs = this.next_term_infer_of_kind(goal.predicate.term); + let unconstrained_goal = goal.with( + this.tcx(), + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty: goal.predicate.projection_ty, + term: unconstrained_rhs, + }), + ); + + let (_, certainty, instantiate_goals) = + match this.evaluate_goal(IsNormalizesToHack::Yes, unconstrained_goal) { + Ok(r) => r, + Err(NoSolution) => return Some(Err(NoSolution)), + }; + new_goals.goals.extend(instantiate_goals); + + // Finally, equate the goal's RHS with the unconstrained var. + // We put the nested goals from this into goals instead of + // next_goals to avoid needing to process the loop one extra + // time if this goal returns something -- I don't think this + // matters in practice, though. + match this.eq_and_get_goals( + goal.param_env, + goal.predicate.term, + unconstrained_rhs, + ) { + Ok(eq_goals) => { + goals.goals.extend(eq_goals); + } + Err(NoSolution) => return Some(Err(NoSolution)), + }; + + // We only look at the `projection_ty` part here rather than + // looking at the "has changed" return from evaluate_goal, + // because we expect the `unconstrained_rhs` part of the predicate + // to have changed -- that means we actually normalized successfully! + if goal.predicate.projection_ty + != this.resolve_vars_if_possible(goal.predicate.projection_ty) + { + has_changed = Ok(()) + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + // We need to resolve vars here so that we correctly + // deal with `has_changed` in the next iteration. + new_goals.normalizes_to_hack_goal = + Some(this.resolve_vars_if_possible(goal)); + has_changed = has_changed.map_err(|c| c.unify_with(certainty)); + } + } + } + + for goal in goals.goals.drain(..) { + let (changed, certainty, instantiate_goals) = + match this.evaluate_goal(IsNormalizesToHack::No, goal) { + Ok(result) => result, + Err(NoSolution) => return Some(Err(NoSolution)), + }; + new_goals.goals.extend(instantiate_goals); + + if changed { + has_changed = Ok(()); + } + + match certainty { + Certainty::Yes => {} + Certainty::Maybe(_) => { + new_goals.goals.push(goal); + has_changed = has_changed.map_err(|c| c.unify_with(certainty)); + } + } + } + + core::mem::swap(&mut new_goals, &mut goals); + match has_changed { + Ok(()) => None, + Err(certainty) => Some(Ok(certainty)), + } + }, + ); + + self.nested_goals = goals; + response + } } impl<'tcx> EvalCtxt<'_, 'tcx> { pub(super) fn probe<T>(&mut self, f: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> T) -> T { - self.infcx.probe(|_| f(self)) + let mut ecx = EvalCtxt { + infcx: self.infcx, + var_values: self.var_values, + max_input_universe: self.max_input_universe, + search_graph: self.search_graph, + nested_goals: self.nested_goals.clone(), + }; + self.infcx.probe(|_| f(&mut ecx)) } pub(super) fn tcx(&self) -> TyCtxt<'tcx> { @@ -61,6 +426,15 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) } + /// Returns a ty infer or a const infer depending on whether `kind` is a `Ty` or `Const`. + /// If `kind` is an integer inference variable this will still return a ty infer var. + pub(super) fn next_term_infer_of_kind(&self, kind: ty::Term<'tcx>) -> ty::Term<'tcx> { + match kind.unpack() { + ty::TermKind::Ty(_) => self.next_ty_infer().into(), + ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), + } + } + /// Is the projection predicate is of the form `exists<T> <Ty as Trait>::Assoc = T`. /// /// This is the case if the `term` is an inference variable in the innermost universe @@ -74,7 +448,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if let &ty::Infer(ty::TyVar(vid)) = ty.kind() { match self.infcx.probe_ty_var(vid) { Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), - Err(universe) => universe == self.universe(), + Err(universe) => universe == self.infcx.universe(), } } else { false @@ -84,7 +458,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = ct.kind() { match self.infcx.probe_const_var(vid) { Ok(value) => bug!("resolved var in query: {goal:?} {value:?}"), - Err(universe) => universe == self.universe(), + Err(universe) => universe == self.infcx.universe(), } } else { false @@ -93,37 +467,42 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }; // Guard against `<T as Trait<?0>>::Assoc = ?0>`. - struct ContainsTerm<'tcx> { + struct ContainsTerm<'a, 'tcx> { term: ty::Term<'tcx>, + infcx: &'a InferCtxt<'tcx>, } - impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTerm<'tcx> { + impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsTerm<'_, 'tcx> { type BreakTy = (); fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { - if t.needs_infer() { - if ty::Term::from(t) == self.term { - ControlFlow::Break(()) - } else { - t.super_visit_with(self) - } + if let Some(vid) = t.ty_vid() + && let ty::TermKind::Ty(term) = self.term.unpack() + && let Some(term_vid) = term.ty_vid() + && self.infcx.root_var(vid) == self.infcx.root_var(term_vid) + { + ControlFlow::Break(()) + } else if t.has_non_region_infer() { + t.super_visit_with(self) } else { ControlFlow::Continue(()) } } fn visit_const(&mut self, c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { - if c.needs_infer() { - if ty::Term::from(c) == self.term { - ControlFlow::Break(()) - } else { - c.super_visit_with(self) - } + if let ty::ConstKind::Infer(ty::InferConst::Var(vid)) = c.kind() + && let ty::TermKind::Const(term) = self.term.unpack() + && let ty::ConstKind::Infer(ty::InferConst::Var(term_vid)) = term.kind() + && self.infcx.root_const_var(vid) == self.infcx.root_const_var(term_vid) + { + ControlFlow::Break(()) + } else if c.has_non_region_infer() { + c.super_visit_with(self) } else { ControlFlow::Continue(()) } } } - let mut visitor = ContainsTerm { term: goal.predicate.term }; + let mut visitor = ContainsTerm { infcx: self.infcx, term: goal.predicate.term }; term_is_infer && goal.predicate.projection_ty.visit_with(&mut visitor).is_continue() @@ -132,6 +511,49 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { #[instrument(level = "debug", skip(self, param_env), ret)] pub(super) fn eq<T: ToTrace<'tcx>>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + lhs: T, + rhs: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .eq(DefineOpaqueTypes::No, lhs, rhs) + .map(|InferOk { value: (), obligations }| { + self.add_goals(obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to equate"); + NoSolution + }) + } + + #[instrument(level = "debug", skip(self, param_env), ret)] + pub(super) fn sub<T: ToTrace<'tcx>>( + &mut self, + param_env: ty::ParamEnv<'tcx>, + sub: T, + sup: T, + ) -> Result<(), NoSolution> { + self.infcx + .at(&ObligationCause::dummy(), param_env) + .sub(DefineOpaqueTypes::No, sub, sup) + .map(|InferOk { value: (), obligations }| { + self.add_goals(obligations.into_iter().map(|o| o.into())); + }) + .map_err(|e| { + debug!(?e, "failed to subtype"); + NoSolution + }) + } + + /// Equates two values returning the nested goals without adding them + /// to the nested goals of the `EvalCtxt`. + /// + /// If possible, try using `eq` instead which automatically handles nested + /// goals correctly. + #[instrument(level = "trace", skip(self, param_env), ret)] + pub(super) fn eq_and_get_goals<T: ToTrace<'tcx>>( &self, param_env: ty::ParamEnv<'tcx>, lhs: T, @@ -139,7 +561,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> { self.infcx .at(&ObligationCause::dummy(), param_env) - .eq(lhs, rhs) + .eq(DefineOpaqueTypes::No, lhs, rhs) .map(|InferOk { value: (), obligations }| { obligations.into_iter().map(|o| o.into()).collect() }) @@ -178,7 +600,64 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { self.infcx.fresh_substs_for_item(DUMMY_SP, def_id) } - pub(super) fn universe(&self) -> ty::UniverseIndex { - self.infcx.universe() + pub(super) fn translate_substs( + &self, + param_env: ty::ParamEnv<'tcx>, + source_impl: DefId, + source_substs: ty::SubstsRef<'tcx>, + target_node: specialization_graph::Node, + ) -> ty::SubstsRef<'tcx> { + crate::traits::translate_substs( + self.infcx, + param_env, + source_impl, + source_substs, + target_node, + ) + } + + pub(super) fn register_ty_outlives(&self, ty: Ty<'tcx>, lt: ty::Region<'tcx>) { + self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); + } + + pub(super) fn register_region_outlives(&self, a: ty::Region<'tcx>, b: ty::Region<'tcx>) { + // `b : a` ==> `a <= b` + // (inlined from `InferCtxt::region_outlives_predicate`) + self.infcx.sub_regions( + rustc_infer::infer::SubregionOrigin::RelateRegionParamBound(DUMMY_SP), + b, + a, + ); + } + + /// Computes the list of goals required for `arg` to be well-formed + pub(super) fn well_formed_goals( + &self, + param_env: ty::ParamEnv<'tcx>, + arg: ty::GenericArg<'tcx>, + ) -> Option<impl Iterator<Item = Goal<'tcx, ty::Predicate<'tcx>>>> { + crate::traits::wf::unnormalized_obligations(self.infcx, param_env, arg) + .map(|obligations| obligations.into_iter().map(|obligation| obligation.into())) + } + + pub(super) fn is_transmutable( + &self, + src_and_dst: rustc_transmute::Types<'tcx>, + scope: Ty<'tcx>, + assume: rustc_transmute::Assume, + ) -> Result<Certainty, NoSolution> { + // FIXME(transmutability): This really should be returning nested goals for `Answer::If*` + match rustc_transmute::TransmuteTypeEnv::new(self.infcx).is_transmutable( + ObligationCause::dummy(), + ty::Binder::dummy(src_and_dst), + scope, + assume, + ) { + rustc_transmute::Answer::Yes => Ok(Certainty::Yes), + rustc_transmute::Answer::No(_) + | rustc_transmute::Answer::IfTransmutable { .. } + | rustc_transmute::Answer::IfAll(_) + | rustc_transmute::Answer::IfAny(_) => Err(NoSolution), + } } } diff --git a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs index 8c3be8da1..ada868705 100644 --- a/compiler/rustc_trait_selection/src/solve/canonical/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/eval_ctxt/canonical.rs @@ -8,22 +8,19 @@ /// section of the [rustc-dev-guide][c]. /// /// [c]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html -use self::canonicalize::{CanonicalizeMode, Canonicalizer}; use super::{CanonicalGoal, Certainty, EvalCtxt, Goal}; -use super::{CanonicalResponse, ExternalConstraints, QueryResult, Response}; +use crate::solve::canonicalize::{CanonicalizeMode, Canonicalizer}; +use crate::solve::{CanonicalResponse, QueryResult, Response}; 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::traits::query::NoSolution; -use rustc_infer::traits::solve::ExternalConstraintsData; -use rustc_infer::traits::ObligationCause; +use rustc_middle::traits::query::NoSolution; +use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData}; use rustc_middle::ty::{self, GenericArgKind}; use rustc_span::DUMMY_SP; use std::iter; use std::ops::Deref; -mod canonicalize; - impl<'tcx> EvalCtxt<'_, 'tcx> { /// Canonicalizes the goal remembering the original values /// for each bound variable. @@ -45,10 +42,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { /// /// - `var_values`: a map from bound variables in the canonical goal to /// the values inferred while solving the instantiated goal. - /// - `external_constraints`: additional constraints which aren't expressable + /// - `external_constraints`: additional constraints which aren't expressible /// using simple unification of inference variables. #[instrument(level = "debug", skip(self))] - pub(super) fn make_canonical_response(&self, certainty: Certainty) -> QueryResult<'tcx> { + pub(in crate::solve) fn evaluate_added_goals_and_make_canonical_response( + &mut self, + certainty: Certainty, + ) -> QueryResult<'tcx> { + let goals_certainty = self.try_evaluate_added_goals()?; + let certainty = certainty.unify_with(goals_certainty); + let external_constraints = self.compute_external_query_constraints()?; let response = Response { var_values: self.var_values, external_constraints, certainty }; @@ -93,24 +96,24 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { param_env: ty::ParamEnv<'tcx>, original_values: Vec<ty::GenericArg<'tcx>>, response: CanonicalResponse<'tcx>, - ) -> Result<Certainty, NoSolution> { + ) -> Result<(Certainty, Vec<Goal<'tcx, ty::Predicate<'tcx>>>), NoSolution> { let substitution = self.compute_query_response_substitution(&original_values, &response); let Response { var_values, external_constraints, certainty } = response.substitute(self.tcx(), &substitution); - self.unify_query_var_values(param_env, &original_values, var_values)?; + let nested_goals = self.unify_query_var_values(param_env, &original_values, var_values)?; // FIXME: implement external constraints. let ExternalConstraintsData { region_constraints, opaque_types: _ } = external_constraints.deref(); self.register_region_constraints(region_constraints); - Ok(certainty) + Ok((certainty, nested_goals)) } /// This returns the substitutions to instantiate the bound variables of - /// the canonical reponse. This depends on the `original_values` for the + /// the canonical response. This depends on the `original_values` for the /// bound variables. fn compute_query_response_substitution( &self, @@ -185,7 +188,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } else { // For placeholders which were already part of the input, we simply map this // universal bound variable back the placeholder of the input. - original_values[info.expect_anon_placeholder() as usize] + original_values[info.expect_placeholder_index()] } }, )); @@ -199,35 +202,22 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { param_env: ty::ParamEnv<'tcx>, original_values: &[ty::GenericArg<'tcx>], var_values: CanonicalVarValues<'tcx>, - ) -> Result<(), NoSolution> { + ) -> Result<Vec<Goal<'tcx, ty::Predicate<'tcx>>>, NoSolution> { assert_eq!(original_values.len(), var_values.len()); + + let mut nested_goals = vec![]; for (&orig, response) in iter::zip(original_values, var_values.var_values) { - // This can fail due to the occurs check, see - // `tests/ui/typeck/lazy-norm/equating-projection-cyclically.rs` for an example - // where that can happen. - // - // FIXME: To deal with #105787 I also expect us to emit nested obligations here at - // some point. We can figure out how to deal with this once we actually have - // an ICE. - let nested_goals = self.eq(param_env, orig, response)?; - assert!(nested_goals.is_empty(), "{nested_goals:?}"); + nested_goals.extend(self.eq_and_get_goals(param_env, orig, response)?); } - Ok(()) + Ok(nested_goals) } fn register_region_constraints(&mut self, region_constraints: &QueryRegionConstraints<'tcx>) { for &(ty::OutlivesPredicate(lhs, rhs), _) in ®ion_constraints.outlives { match lhs.unpack() { - GenericArgKind::Lifetime(lhs) => self.infcx.region_outlives_predicate( - &ObligationCause::dummy(), - ty::Binder::dummy(ty::OutlivesPredicate(lhs, rhs)), - ), - GenericArgKind::Type(lhs) => self.infcx.register_region_obligation_with_cause( - lhs, - rhs, - &ObligationCause::dummy(), - ), + GenericArgKind::Lifetime(lhs) => self.register_region_outlives(lhs, rhs), + GenericArgKind::Type(lhs) => self.register_ty_outlives(lhs, rhs), GenericArgKind::Const(_) => bug!("const outlives: {lhs:?}: {rhs:?}"), } } diff --git a/compiler/rustc_trait_selection/src/solve/fulfill.rs b/compiler/rustc_trait_selection/src/solve/fulfill.rs index a55b984fd..32bd10f0b 100644 --- a/compiler/rustc_trait_selection/src/solve/fulfill.rs +++ b/compiler/rustc_trait_selection/src/solve/fulfill.rs @@ -1,6 +1,8 @@ use std::mem; use rustc_infer::infer::InferCtxt; +use rustc_infer::traits::solve::MaybeCause; +use rustc_infer::traits::Obligation; use rustc_infer::traits::{ query::NoSolution, FulfillmentError, FulfillmentErrorCode, MismatchedProjectionTypes, PredicateObligation, SelectionError, TraitEngine, @@ -40,13 +42,31 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { self.obligations.push(obligation); } - fn collect_remaining_errors(&mut self) -> Vec<FulfillmentError<'tcx>> { + fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { self.obligations .drain(..) - .map(|obligation| FulfillmentError { - obligation: obligation.clone(), - code: FulfillmentErrorCode::CodeAmbiguity, - root_obligation: obligation, + .map(|obligation| { + let code = + infcx.probe(|_| match infcx.evaluate_root_goal(obligation.clone().into()) { + Ok((_, Certainty::Maybe(MaybeCause::Ambiguity), _)) => { + FulfillmentErrorCode::CodeAmbiguity { overflow: false } + } + Ok((_, Certainty::Maybe(MaybeCause::Overflow), _)) => { + FulfillmentErrorCode::CodeAmbiguity { overflow: true } + } + Ok((_, Certainty::Yes, _)) => { + bug!("did not expect successful goal when collecting ambiguity errors") + } + Err(_) => { + bug!("did not expect selection error when collecting ambiguity errors") + } + }); + + FulfillmentError { + obligation: obligation.clone(), + code, + root_obligation: obligation, + } }) .collect() } @@ -61,7 +81,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { let mut has_changed = false; for obligation in mem::take(&mut self.obligations) { let goal = obligation.clone().into(); - let (changed, certainty) = match infcx.evaluate_root_goal(goal) { + let (changed, certainty, nested_goals) = match infcx.evaluate_root_goal(goal) { Ok(result) => result, Err(NoSolution) => { errors.push(FulfillmentError { @@ -73,7 +93,7 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { MismatchedProjectionTypes { err: TypeError::Mismatch }, ) } - ty::PredicateKind::AliasEq(_, _) => { + ty::PredicateKind::AliasRelate(_, _, _) => { FulfillmentErrorCode::CodeProjectionError( MismatchedProjectionTypes { err: TypeError::Mismatch }, ) @@ -125,7 +145,16 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { continue; } }; - + // Push any nested goals that we get from unifying our canonical response + // with our obligation onto the fulfillment context. + self.obligations.extend(nested_goals.into_iter().map(|goal| { + Obligation::new( + infcx.tcx, + obligation.cause.clone(), + goal.param_env, + goal.predicate, + ) + })); has_changed |= changed; match certainty { Certainty::Yes => {} @@ -149,6 +178,6 @@ impl<'tcx> TraitEngine<'tcx> for FulfillmentCtxt<'tcx> { &mut self, _: &InferCtxt<'tcx>, ) -> Vec<PredicateObligation<'tcx>> { - unimplemented!() + std::mem::take(&mut self.obligations) } } diff --git a/compiler/rustc_trait_selection/src/solve/mod.rs b/compiler/rustc_trait_selection/src/solve/mod.rs index 57b6a4527..19bcbd461 100644 --- a/compiler/rustc_trait_selection/src/solve/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/mod.rs @@ -9,81 +9,45 @@ //! FIXME(@lcnr): Write that section. If you read this before then ask me //! about it on zulip. -// FIXME: Instead of using `infcx.canonicalize_query` we have to add a new routine which -// preserves universes and creates a unique var (in the highest universe) for each -// appearance of a region. - -// FIXME: uses of `infcx.at` need to enable deferred projection equality once that's implemented. - -use std::mem; - use rustc_hir::def_id::DefId; use rustc_infer::infer::canonical::{Canonical, CanonicalVarValues}; -use rustc_infer::infer::{InferCtxt, InferOk, TyCtxtInferExt}; use rustc_infer::traits::query::NoSolution; -use rustc_infer::traits::Obligation; -use rustc_middle::traits::solve::{ExternalConstraints, ExternalConstraintsData}; +use rustc_middle::traits::solve::{ + CanonicalResponse, Certainty, ExternalConstraintsData, Goal, QueryResult, Response, +}; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{ - CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, ToPredicate, TypeOutlivesPredicate, + CoercePredicate, RegionOutlivesPredicate, SubtypePredicate, TypeOutlivesPredicate, }; -use rustc_span::DUMMY_SP; - -use crate::solve::search_graph::OverflowHandler; -use crate::traits::ObligationCause; mod assembly; -mod canonical; +mod canonicalize; mod eval_ctxt; mod fulfill; mod project_goals; mod search_graph; mod trait_goals; -pub use eval_ctxt::EvalCtxt; +pub use eval_ctxt::{EvalCtxt, InferCtxtEvalExt}; pub use fulfill::FulfillmentCtxt; -/// A goal is a statement, i.e. `predicate`, we want to prove -/// given some assumptions, i.e. `param_env`. -/// -/// Most of the time the `param_env` contains the `where`-bounds of the function -/// we're currently typechecking while the `predicate` is some trait bound. -#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] -pub struct Goal<'tcx, P> { - param_env: ty::ParamEnv<'tcx>, - predicate: P, -} - -impl<'tcx, P> Goal<'tcx, P> { - pub fn new( - tcx: TyCtxt<'tcx>, - param_env: ty::ParamEnv<'tcx>, - predicate: impl ToPredicate<'tcx, P>, - ) -> Goal<'tcx, P> { - Goal { param_env, predicate: predicate.to_predicate(tcx) } - } - - /// Updates the goal to one with a different `predicate` but the same `param_env`. - fn with<Q>(self, tcx: TyCtxt<'tcx>, predicate: impl ToPredicate<'tcx, Q>) -> Goal<'tcx, Q> { - Goal { param_env: self.param_env, predicate: predicate.to_predicate(tcx) } - } -} - -impl<'tcx, P> From<Obligation<'tcx, P>> for Goal<'tcx, P> { - fn from(obligation: Obligation<'tcx, P>) -> Goal<'tcx, P> { - Goal { param_env: obligation.param_env, predicate: obligation.predicate } - } -} -#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] -pub struct Response<'tcx> { - pub var_values: CanonicalVarValues<'tcx>, - /// Additional constraints returned by this query. - pub external_constraints: ExternalConstraints<'tcx>, - pub certainty: Certainty, +#[derive(Debug, Clone, Copy)] +enum SolverMode { + /// Ordinary trait solving, using everywhere except for coherence. + Normal, + /// Trait solving during coherence. There are a few notable differences + /// between coherence and ordinary trait solving. + /// + /// Most importantly, trait solving during coherence must not be incomplete, + /// i.e. return `Err(NoSolution)` for goals for which a solution exists. + /// This means that we must not make any guesses or arbitrary choices. + Coherence, } trait CanonicalResponseExt { fn has_no_inference_or_external_constraints(&self) -> bool; + + fn has_only_region_constraints(&self) -> bool; } impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { @@ -92,242 +56,35 @@ impl<'tcx> CanonicalResponseExt for Canonical<'tcx, Response<'tcx>> { && self.value.var_values.is_identity() && self.value.external_constraints.opaque_types.is_empty() } -} -#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] -pub enum Certainty { - Yes, - Maybe(MaybeCause), -} - -impl Certainty { - pub const AMBIGUOUS: Certainty = Certainty::Maybe(MaybeCause::Ambiguity); - - /// When proving multiple goals using **AND**, e.g. nested obligations for an impl, - /// use this function to unify the certainty of these goals - pub fn unify_and(self, other: Certainty) -> Certainty { - match (self, other) { - (Certainty::Yes, Certainty::Yes) => Certainty::Yes, - (Certainty::Yes, Certainty::Maybe(_)) => other, - (Certainty::Maybe(_), Certainty::Yes) => self, - (Certainty::Maybe(MaybeCause::Overflow), Certainty::Maybe(MaybeCause::Overflow)) => { - Certainty::Maybe(MaybeCause::Overflow) - } - // If at least one of the goals is ambiguous, hide the overflow as the ambiguous goal - // may still result in failure. - (Certainty::Maybe(MaybeCause::Ambiguity), Certainty::Maybe(_)) - | (Certainty::Maybe(_), Certainty::Maybe(MaybeCause::Ambiguity)) => { - Certainty::Maybe(MaybeCause::Ambiguity) - } - } - } -} - -/// Why we failed to evaluate a goal. -#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash, TypeFoldable, TypeVisitable)] -pub enum MaybeCause { - /// We failed due to ambiguity. This ambiguity can either - /// be a true ambiguity, i.e. there are multiple different answers, - /// or we hit a case where we just don't bother, e.g. `?x: Trait` goals. - Ambiguity, - /// We gave up due to an overflow, most often by hitting the recursion limit. - Overflow, -} - -type CanonicalGoal<'tcx, T = ty::Predicate<'tcx>> = Canonical<'tcx, Goal<'tcx, T>>; -type CanonicalResponse<'tcx> = Canonical<'tcx, Response<'tcx>>; -/// The result of evaluating a canonical query. -/// -/// FIXME: We use a different type than the existing canonical queries. This is because -/// we need to add a `Certainty` for `overflow` and may want to restructure this code without -/// having to worry about changes to currently used code. Once we've made progress on this -/// solver, merge the two responses again. -pub type QueryResult<'tcx> = Result<CanonicalResponse<'tcx>, NoSolution>; - -pub trait InferCtxtEvalExt<'tcx> { - /// Evaluates a goal from **outside** of the trait solver. - /// - /// Using this while inside of the solver is wrong as it uses a new - /// search graph which would break cycle detection. - fn evaluate_root_goal( - &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty), NoSolution>; -} - -impl<'tcx> InferCtxtEvalExt<'tcx> for InferCtxt<'tcx> { - fn evaluate_root_goal( - &self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty), NoSolution> { - let mut search_graph = search_graph::SearchGraph::new(self.tcx); - - let result = EvalCtxt { - search_graph: &mut search_graph, - infcx: self, - // Only relevant when canonicalizing the response. - max_input_universe: ty::UniverseIndex::ROOT, - var_values: CanonicalVarValues::dummy(), - in_projection_eq_hack: false, - } - .evaluate_goal(goal); - - assert!(search_graph.is_empty()); - result + fn has_only_region_constraints(&self) -> bool { + self.value.var_values.is_identity_modulo_regions() + && self.value.external_constraints.opaque_types.is_empty() } } impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { - /// The entry point of the solver. - /// - /// This function deals with (coinductive) cycles, overflow, and caching - /// and then calls [`EvalCtxt::compute_goal`] which contains the actual - /// logic of the solver. - /// - /// Instead of calling this function directly, use either [EvalCtxt::evaluate_goal] - /// if you're inside of the solver or [InferCtxtEvalExt::evaluate_root_goal] if you're - /// outside of it. - #[instrument(level = "debug", skip(tcx, search_graph), ret)] - fn evaluate_canonical_goal( - tcx: TyCtxt<'tcx>, - search_graph: &'a mut search_graph::SearchGraph<'tcx>, - canonical_goal: CanonicalGoal<'tcx>, - ) -> QueryResult<'tcx> { - // Deal with overflow, caching, and coinduction. - // - // The actual solver logic happens in `ecx.compute_goal`. - search_graph.with_new_goal(tcx, canonical_goal, |search_graph| { - let (ref infcx, goal, var_values) = - tcx.infer_ctxt().build_with_canonical(DUMMY_SP, &canonical_goal); - let mut ecx = EvalCtxt { - infcx, - var_values, - max_input_universe: canonical_goal.max_universe, - search_graph, - in_projection_eq_hack: false, - }; - ecx.compute_goal(goal) - }) - } - - /// Recursively evaluates `goal`, returning whether any inference vars have - /// been constrained and the certainty of the result. - fn evaluate_goal( - &mut self, - goal: Goal<'tcx, ty::Predicate<'tcx>>, - ) -> Result<(bool, Certainty), NoSolution> { - let (orig_values, canonical_goal) = self.canonicalize_goal(goal); - let canonical_response = - EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; - - let has_changed = !canonical_response.value.var_values.is_identity(); - let certainty = self.instantiate_and_apply_query_response( - goal.param_env, - orig_values, - canonical_response, - )?; - - // Check that rerunning this query with its inference constraints applied - // doesn't result in new inference constraints and has the same result. - // - // If we have projection goals like `<T as Trait>::Assoc == u32` we recursively - // call `exists<U> <T as Trait>::Assoc == U` to enable better caching. This goal - // could constrain `U` to `u32` which would cause this check to result in a - // solver cycle. - if cfg!(debug_assertions) - && has_changed - && !self.in_projection_eq_hack - && !self.search_graph.in_cycle() - { - let (_orig_values, canonical_goal) = self.canonicalize_goal(goal); - let canonical_response = - EvalCtxt::evaluate_canonical_goal(self.tcx(), self.search_graph, canonical_goal)?; - if !canonical_response.value.var_values.is_identity() { - bug!("unstable result: {goal:?} {canonical_goal:?} {canonical_response:?}"); - } - assert_eq!(certainty, canonical_response.value.certainty); - } - - Ok((has_changed, certainty)) - } - - fn compute_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) -> QueryResult<'tcx> { - let Goal { param_env, predicate } = goal; - let kind = predicate.kind(); - if let Some(kind) = kind.no_bound_vars() { - match kind { - ty::PredicateKind::Clause(ty::Clause::Trait(predicate)) => { - self.compute_trait_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::Projection(predicate)) => { - self.compute_projection_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::TypeOutlives(predicate)) => { - self.compute_type_outlives_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::RegionOutlives(predicate)) => { - self.compute_region_outlives_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { - self.compute_const_arg_has_type_goal(Goal { param_env, predicate: (ct, ty) }) - } - ty::PredicateKind::Subtype(predicate) => { - self.compute_subtype_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::Coerce(predicate) => { - self.compute_coerce_goal(Goal { param_env, predicate }) - } - ty::PredicateKind::ClosureKind(def_id, substs, kind) => self - .compute_closure_kind_goal(Goal { - param_env, - predicate: (def_id, substs, kind), - }), - ty::PredicateKind::ObjectSafe(trait_def_id) => { - self.compute_object_safe_goal(trait_def_id) - } - ty::PredicateKind::WellFormed(arg) => { - self.compute_well_formed_goal(Goal { param_env, predicate: arg }) - } - ty::PredicateKind::Ambiguous => self.make_canonical_response(Certainty::AMBIGUOUS), - // FIXME: implement these predicates :) - ty::PredicateKind::ConstEvaluatable(_) | ty::PredicateKind::ConstEquate(_, _) => { - self.make_canonical_response(Certainty::Yes) - } - ty::PredicateKind::TypeWellFormedFromEnv(..) => { - bug!("TypeWellFormedFromEnv is only used for Chalk") - } - ty::PredicateKind::AliasEq(lhs, rhs) => { - self.compute_alias_eq_goal(Goal { param_env, predicate: (lhs, rhs) }) - } - } - } else { - let kind = self.infcx.instantiate_binder_with_placeholders(kind); - let goal = goal.with(self.tcx(), ty::Binder::dummy(kind)); - let (_, certainty) = self.evaluate_goal(goal)?; - self.make_canonical_response(certainty) - } - } - + #[instrument(level = "debug", skip(self))] fn compute_type_outlives_goal( &mut self, goal: Goal<'tcx, TypeOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { let ty::OutlivesPredicate(ty, lt) = goal.predicate; - self.infcx.register_region_obligation_with_cause(ty, lt, &ObligationCause::dummy()); - self.make_canonical_response(Certainty::Yes) + self.register_ty_outlives(ty, lt); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } + #[instrument(level = "debug", skip(self))] fn compute_region_outlives_goal( &mut self, goal: Goal<'tcx, RegionOutlivesPredicate<'tcx>>, ) -> QueryResult<'tcx> { - self.infcx.region_outlives_predicate( - &ObligationCause::dummy(), - ty::Binder::dummy(goal.predicate), - ); - self.make_canonical_response(Certainty::Yes) + let ty::OutlivesPredicate(a, b) = goal.predicate; + self.register_region_outlives(a, b); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } + #[instrument(level = "debug", skip(self))] fn compute_coerce_goal( &mut self, goal: Goal<'tcx, CoercePredicate<'tcx>>, @@ -342,25 +99,20 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { }) } + #[instrument(level = "debug", skip(self))] fn compute_subtype_goal( &mut self, goal: Goal<'tcx, SubtypePredicate<'tcx>>, ) -> QueryResult<'tcx> { if goal.predicate.a.is_ty_var() && goal.predicate.b.is_ty_var() { - // FIXME: Do we want to register a subtype relation between these vars? - // That won't actually reflect in the query response, so it seems moot. - self.make_canonical_response(Certainty::AMBIGUOUS) + self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) } else { - let InferOk { value: (), obligations } = self - .infcx - .at(&ObligationCause::dummy(), goal.param_env) - .sub(goal.predicate.a, goal.predicate.b)?; - self.evaluate_all_and_make_canonical_response( - obligations.into_iter().map(|pred| pred.into()).collect(), - ) + self.sub(goal.param_env, goal.predicate.a, goal.predicate.b)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } + #[instrument(level = "debug", skip(self))] fn compute_closure_kind_goal( &mut self, goal: Goal<'tcx, (DefId, ty::SubstsRef<'tcx>, ty::ClosureKind)>, @@ -369,92 +121,154 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { let found_kind = substs.as_closure().kind_ty().to_opt_closure_kind(); let Some(found_kind) = found_kind else { - return self.make_canonical_response(Certainty::AMBIGUOUS); + return self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); }; if found_kind.extends(expected_kind) { - self.make_canonical_response(Certainty::Yes) + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } } + #[instrument(level = "debug", skip(self))] fn compute_object_safe_goal(&mut self, trait_def_id: DefId) -> QueryResult<'tcx> { if self.tcx().check_is_object_safe(trait_def_id) { - self.make_canonical_response(Certainty::Yes) + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } } + #[instrument(level = "debug", skip(self))] fn compute_well_formed_goal( &mut self, goal: Goal<'tcx, ty::GenericArg<'tcx>>, ) -> QueryResult<'tcx> { - match crate::traits::wf::unnormalized_obligations( - self.infcx, - goal.param_env, - goal.predicate, - ) { - Some(obligations) => self.evaluate_all_and_make_canonical_response( - obligations.into_iter().map(|o| o.into()).collect(), - ), - None => self.make_canonical_response(Certainty::AMBIGUOUS), + match self.well_formed_goals(goal.param_env, goal.predicate) { + Some(goals) => { + self.add_goals(goals); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + None => self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS), } } #[instrument(level = "debug", skip(self), ret)] - fn compute_alias_eq_goal( + fn compute_alias_relate_goal( &mut self, - goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>)>, + goal: Goal<'tcx, (ty::Term<'tcx>, ty::Term<'tcx>, ty::AliasRelationDirection)>, ) -> QueryResult<'tcx> { let tcx = self.tcx(); + // We may need to invert the alias relation direction if dealing an alias on the RHS. + #[derive(Debug)] + enum Invert { + No, + Yes, + } + let evaluate_normalizes_to = + |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other, direction, invert| { + let span = tracing::span!( + tracing::Level::DEBUG, + "compute_alias_relate_goal(evaluate_normalizes_to)", + ?alias, + ?other, + ?direction, + ?invert + ); + let _enter = span.enter(); + let result = ecx.probe(|ecx| { + let other = match direction { + // This is purely an optimization. + ty::AliasRelationDirection::Equate => other, + + ty::AliasRelationDirection::Subtype => { + let fresh = ecx.next_term_infer_of_kind(other); + let (sub, sup) = match invert { + Invert::No => (fresh, other), + Invert::Yes => (other, fresh), + }; + ecx.sub(goal.param_env, sub, sup)?; + fresh + } + }; + ecx.add_goal(goal.with( + tcx, + ty::Binder::dummy(ty::ProjectionPredicate { + projection_ty: alias, + term: other, + }), + )); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }); + debug!(?result); + result + }; - let evaluate_normalizes_to = |ecx: &mut EvalCtxt<'_, 'tcx>, alias, other| { - debug!("evaluate_normalizes_to(alias={:?}, other={:?})", alias, other); - let r = ecx.probe(|ecx| { - let (_, certainty) = ecx.evaluate_goal(goal.with( - tcx, - ty::Binder::dummy(ty::ProjectionPredicate { - projection_ty: alias, - term: other, - }), - ))?; - ecx.make_canonical_response(certainty) - }); - debug!("evaluate_normalizes_to(..) -> {:?}", r); - r - }; + let (lhs, rhs, direction) = goal.predicate; - if goal.predicate.0.is_infer() || goal.predicate.1.is_infer() { + if lhs.is_infer() || rhs.is_infer() { bug!( - "`AliasEq` goal with an infer var on lhs or rhs which should have been instantiated" + "`AliasRelate` goal with an infer var on lhs or rhs which should have been instantiated" ); } - match ( - goal.predicate.0.to_alias_term_no_opaque(tcx), - goal.predicate.1.to_alias_term_no_opaque(tcx), - ) { - (None, None) => bug!("`AliasEq` goal without an alias on either lhs or rhs"), - (Some(alias), None) => evaluate_normalizes_to(self, alias, goal.predicate.1), - (None, Some(alias)) => evaluate_normalizes_to(self, alias, goal.predicate.0), - (Some(alias_lhs), Some(alias_rhs)) => { - debug!("compute_alias_eq_goal: both sides are aliases"); + match (lhs.to_projection_term(tcx), rhs.to_projection_term(tcx)) { + (None, None) => bug!("`AliasRelate` goal without an alias on either lhs or rhs"), - let mut candidates = Vec::with_capacity(3); + // RHS is not a projection, only way this is true is if LHS normalizes-to RHS + (Some(alias_lhs), None) => { + evaluate_normalizes_to(self, alias_lhs, rhs, direction, Invert::No) + } + + // LHS is not a projection, only way this is true is if RHS normalizes-to LHS + (None, Some(alias_rhs)) => { + evaluate_normalizes_to(self, alias_rhs, lhs, direction, Invert::Yes) + } - // Evaluate all 3 potential candidates for the alias' being equal - candidates.push(evaluate_normalizes_to(self, alias_lhs, goal.predicate.1)); - candidates.push(evaluate_normalizes_to(self, alias_rhs, goal.predicate.0)); - candidates.push(self.probe(|this| { - debug!("compute_alias_eq_goal: alias defids are equal, equating substs"); - let nested_goals = this.eq(goal.param_env, alias_lhs, alias_rhs)?; - this.evaluate_all_and_make_canonical_response(nested_goals) - })); + (Some(alias_lhs), Some(alias_rhs)) => { + debug!("both sides are aliases"); + + let mut candidates = Vec::new(); + // LHS normalizes-to RHS + candidates.extend( + evaluate_normalizes_to(self, alias_lhs, rhs, direction, Invert::No).ok(), + ); + // RHS normalizes-to RHS + candidates.extend( + evaluate_normalizes_to(self, alias_rhs, lhs, direction, Invert::Yes).ok(), + ); + // Relate via substs + candidates.extend( + self.probe(|ecx| { + let span = tracing::span!( + tracing::Level::DEBUG, + "compute_alias_relate_goal(relate_via_substs)", + ?alias_lhs, + ?alias_rhs, + ?direction + ); + let _enter = span.enter(); + + match direction { + ty::AliasRelationDirection::Equate => { + ecx.eq(goal.param_env, alias_lhs, alias_rhs)?; + } + ty::AliasRelationDirection::Subtype => { + ecx.sub(goal.param_env, alias_lhs, alias_rhs)?; + } + } + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + .ok(), + ); debug!(?candidates); - self.try_merge_responses(candidates.into_iter()) + if let Some(merged) = self.try_merge_responses(&candidates) { + Ok(merged) + } else { + self.flounder(&candidates) + } } } } @@ -465,99 +279,78 @@ impl<'a, 'tcx> EvalCtxt<'a, 'tcx> { goal: Goal<'tcx, (ty::Const<'tcx>, Ty<'tcx>)>, ) -> QueryResult<'tcx> { let (ct, ty) = goal.predicate; - let nested_goals = self.eq(goal.param_env, ct.ty(), ty)?; - self.evaluate_all_and_make_canonical_response(nested_goals) + self.eq(goal.param_env, ct.ty(), ty)?; + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } impl<'tcx> EvalCtxt<'_, 'tcx> { - // Recursively evaluates a list of goals to completion, returning the certainty - // of all of the goals. - fn evaluate_all( - &mut self, - mut goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, - ) -> Result<Certainty, NoSolution> { - let mut new_goals = Vec::new(); - self.repeat_while_none( - |_| Ok(Certainty::Maybe(MaybeCause::Overflow)), - |this| { - let mut has_changed = Err(Certainty::Yes); - for goal in goals.drain(..) { - let (changed, certainty) = match this.evaluate_goal(goal) { - Ok(result) => result, - Err(NoSolution) => return Some(Err(NoSolution)), - }; - - if changed { - has_changed = Ok(()); - } - - match certainty { - Certainty::Yes => {} - Certainty::Maybe(_) => { - new_goals.push(goal); - has_changed = has_changed.map_err(|c| c.unify_and(certainty)); - } - } - } + #[instrument(level = "debug", skip(self))] + fn set_normalizes_to_hack_goal(&mut self, goal: Goal<'tcx, ty::ProjectionPredicate<'tcx>>) { + assert!( + self.nested_goals.normalizes_to_hack_goal.is_none(), + "attempted to set the projection eq hack goal when one already exists" + ); + self.nested_goals.normalizes_to_hack_goal = Some(goal); + } - match has_changed { - Ok(()) => { - mem::swap(&mut new_goals, &mut goals); - None - } - Err(certainty) => Some(Ok(certainty)), - } - }, - ) + #[instrument(level = "debug", skip(self))] + fn add_goal(&mut self, goal: Goal<'tcx, ty::Predicate<'tcx>>) { + self.nested_goals.goals.push(goal); } - // Recursively evaluates a list of goals to completion, making a query response. - // - // This is just a convenient way of calling [`EvalCtxt::evaluate_all`], - // then [`EvalCtxt::make_canonical_response`]. - fn evaluate_all_and_make_canonical_response( - &mut self, - goals: Vec<Goal<'tcx, ty::Predicate<'tcx>>>, - ) -> QueryResult<'tcx> { - self.evaluate_all(goals).and_then(|certainty| self.make_canonical_response(certainty)) + #[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..]); } + /// Try to merge multiple possible ways to prove a goal, if that is not possible returns `None`. + /// + /// In this case we tend to flounder and return ambiguity by calling `[EvalCtxt::flounder]`. + #[instrument(level = "debug", skip(self), ret)] fn try_merge_responses( &mut self, - responses: impl Iterator<Item = QueryResult<'tcx>>, - ) -> QueryResult<'tcx> { - let candidates = responses.into_iter().flatten().collect::<Box<[_]>>(); - - if candidates.is_empty() { - return Err(NoSolution); + responses: &[CanonicalResponse<'tcx>], + ) -> Option<CanonicalResponse<'tcx>> { + if responses.is_empty() { + return None; } - // FIXME(-Ztreat-solver=next): We should instead try to find a `Certainty::Yes` response with + // FIXME(-Ztrait-solver=next): We should instead try to find a `Certainty::Yes` response with // a subset of the constraints that all the other responses have. - let one = candidates[0]; - if candidates[1..].iter().all(|resp| resp == &one) { - return Ok(one); + let one = responses[0]; + if responses[1..].iter().all(|&resp| resp == one) { + return Some(one); } - if let Some(response) = candidates.iter().find(|response| { - response.value.certainty == Certainty::Yes - && response.has_no_inference_or_external_constraints() - }) { - return Ok(*response); - } + responses + .iter() + .find(|response| { + response.value.certainty == Certainty::Yes + && response.has_no_inference_or_external_constraints() + }) + .copied() + } - let certainty = candidates.iter().fold(Certainty::AMBIGUOUS, |certainty, response| { - certainty.unify_and(response.value.certainty) + /// If we fail to merge responses we flounder and return overflow or ambiguity. + #[instrument(level = "debug", skip(self), ret)] + fn flounder(&mut self, responses: &[CanonicalResponse<'tcx>]) -> QueryResult<'tcx> { + if responses.is_empty() { + return Err(NoSolution); + } + let certainty = responses.iter().fold(Certainty::AMBIGUOUS, |certainty, response| { + certainty.unify_with(response.value.certainty) }); - // FIXME(-Ztrait-solver=next): We should take the intersection of the constraints on all the - // responses and use that for the constraints of this ambiguous response. - let response = self.make_canonical_response(certainty); - if let Ok(response) = &response { + + let response = self.evaluate_added_goals_and_make_canonical_response(certainty); + if let Ok(response) = response { assert!(response.has_no_inference_or_external_constraints()); + Ok(response) + } else { + bug!("failed to make floundered response: {responses:?}"); } - - response } } diff --git a/compiler/rustc_trait_selection/src/solve/project_goals.rs b/compiler/rustc_trait_selection/src/solve/project_goals.rs index 33c66d072..14cb43b89 100644 --- a/compiler/rustc_trait_selection/src/solve/project_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/project_goals.rs @@ -1,24 +1,23 @@ -use crate::traits::{specialization_graph, translate_substs}; +use crate::traits::specialization_graph; -use super::assembly; -use super::trait_goals::structural_traits; -use super::{Certainty, EvalCtxt, Goal, QueryResult}; +use super::assembly::{self, structural_traits}; +use super::EvalCtxt; use rustc_errors::ErrorGuaranteed; use rustc_hir::def::DefKind; use rustc_hir::def_id::DefId; use rustc_hir::LangItem; -use rustc_infer::infer::InferCtxt; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::specialization_graph::LeafDef; use rustc_infer::traits::Reveal; +use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; use rustc_middle::ty::ProjectionPredicate; use rustc_middle::ty::{self, Ty, TyCtxt}; use rustc_middle::ty::{ToPredicate, TypeVisitableExt}; use rustc_span::{sym, DUMMY_SP}; -use std::iter; impl<'tcx> EvalCtxt<'_, 'tcx> { + #[instrument(level = "debug", skip(self), ret)] pub(super) fn compute_projection_goal( &mut self, goal: Goal<'tcx, ProjectionPredicate<'tcx>>, @@ -32,57 +31,12 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // projection cache in the solver. if self.term_is_fully_unconstrained(goal) { let candidates = self.assemble_and_evaluate_candidates(goal); - self.merge_candidates_and_discard_reservation_impls(candidates) + self.merge_candidates(candidates) } else { - let predicate = goal.predicate; - let unconstrained_rhs = match predicate.term.unpack() { - ty::TermKind::Ty(_) => self.next_ty_infer().into(), - ty::TermKind::Const(ct) => self.next_const_infer(ct.ty()).into(), - }; - let unconstrained_predicate = ty::Clause::Projection(ProjectionPredicate { - projection_ty: goal.predicate.projection_ty, - term: unconstrained_rhs, - }); - let (_has_changed, normalize_certainty) = self.in_projection_eq_hack(|this| { - this.evaluate_goal(goal.with(this.tcx(), unconstrained_predicate)) - })?; - - let nested_eq_goals = self.eq(goal.param_env, unconstrained_rhs, predicate.term)?; - let eval_certainty = self.evaluate_all(nested_eq_goals)?; - self.make_canonical_response(normalize_certainty.unify_and(eval_certainty)) + self.set_normalizes_to_hack_goal(goal); + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } } - - /// This sets a flag used by a debug assert in [`EvalCtxt::evaluate_goal`], - /// see the comment in that method for more details. - fn in_projection_eq_hack<T>(&mut self, f: impl FnOnce(&mut Self) -> T) -> T { - self.in_projection_eq_hack = true; - let result = f(self); - self.in_projection_eq_hack = false; - result - } - - /// After normalizing the projection to `normalized_alias` with the given - /// `normalization_certainty`, constrain the inference variable `term` to it - /// and return a query response. - fn eq_term_and_make_canonical_response( - &mut self, - goal: Goal<'tcx, ProjectionPredicate<'tcx>>, - normalization_certainty: Certainty, - normalized_alias: impl Into<ty::Term<'tcx>>, - ) -> QueryResult<'tcx> { - // The term of our goal should be fully unconstrained, so this should never fail. - // - // It can however be ambiguous when the `normalized_alias` contains a projection. - let nested_goals = self - .eq(goal.param_env, goal.predicate.term, normalized_alias.into()) - .expect("failed to unify with unconstrained term"); - - let unify_certainty = - self.evaluate_all(nested_goals).expect("failed to unify with unconstrained term"); - - self.make_canonical_response(normalization_certainty.unify_and(unify_certainty)) - } } impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { @@ -90,6 +44,10 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { self.self_ty() } + fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> { + self.projection_ty.trait_ref(tcx) + } + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { self.with_self_ty(tcx, self_ty) } @@ -110,19 +68,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ecx.probe(|ecx| { let assumption_projection_pred = ecx.instantiate_binder_with_infer(poly_projection_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.projection_ty, assumption_projection_pred.projection_ty, )?; - nested_goals.extend(requirements); - let subst_certainty = ecx.evaluate_all(nested_goals)?; - - ecx.eq_term_and_make_canonical_response( - goal, - subst_certainty, - assumption_projection_pred.term, - ) + ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?; + ecx.add_goals(requirements); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -138,21 +91,22 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { && poly_projection_pred.projection_def_id() == goal.predicate.def_id() { ecx.probe(|ecx| { + let tcx = ecx.tcx(); + let assumption_projection_pred = ecx.instantiate_binder_with_infer(poly_projection_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.projection_ty, assumption_projection_pred.projection_ty, )?; - let tcx = ecx.tcx(); let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { bug!("expected object type in `consider_object_bound_candidate`"); }; - nested_goals.extend( + ecx.add_goals( structural_traits::predicates_for_object_candidate( - ecx, + &ecx, goal.param_env, goal.predicate.projection_ty.trait_ref(tcx), bounds, @@ -160,14 +114,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { .into_iter() .map(|pred| goal.with(tcx, pred)), ); - - let subst_certainty = ecx.evaluate_all(nested_goals)?; - - ecx.eq_term_and_make_canonical_response( - goal, - subst_certainty, - assumption_projection_pred.term, - ) + ecx.eq(goal.param_env, goal.predicate.term, assumption_projection_pred.term)?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -183,10 +131,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { let goal_trait_ref = goal.predicate.projection_ty.trait_ref(tcx); let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); - let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder }; - if iter::zip(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs) - .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp)) - { + let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; + if !drcx.substs_refs_may_unify(goal_trait_ref.substs, impl_trait_ref.skip_binder().substs) { return Err(NoSolution); } @@ -194,28 +140,27 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { let impl_substs = ecx.fresh_substs_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); - let mut nested_goals = ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + ecx.eq(goal.param_env, goal_trait_ref, impl_trait_ref)?; + let where_clause_bounds = tcx .predicates_of(impl_def_id) .instantiate(tcx, impl_substs) .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); - - nested_goals.extend(where_clause_bounds); - let match_impl_certainty = ecx.evaluate_all(nested_goals)?; + ecx.add_goals(where_clause_bounds); // In case the associated item is hidden due to specialization, we have to // return ambiguity this would otherwise be incomplete, resulting in // unsoundness during coherence (#105782). let Some(assoc_def) = fetch_eligible_assoc_item_def( - ecx.infcx, + ecx, goal.param_env, goal_trait_ref, goal.predicate.def_id(), impl_def_id )? else { - return ecx.make_canonical_response(match_impl_certainty.unify_and(Certainty::AMBIGUOUS)); + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); }; if !assoc_def.item.defaultness(tcx).has_value() { @@ -240,8 +185,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { goal_trait_ref.def_id, impl_substs, ); - let substs = translate_substs( - ecx.infcx, + let substs = ecx.translate_substs( goal.param_env, impl_def_id, impl_substs_with_gat, @@ -262,7 +206,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty.map_bound(|ty| ty.into()) }; - ecx.eq_term_and_make_canonical_response(goal, match_impl_certainty, term.subst(tcx, substs)) + ecx.eq(goal.param_env, goal.predicate.term, term.subst(tcx, substs))?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -301,20 +246,31 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { bug!("`PointerLike` does not have an associated type: {:?}", goal); } + fn consider_builtin_fn_ptr_trait_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`FnPtr` does not have an associated type: {:?}", goal); + } + fn consider_builtin_fn_trait_candidates( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, goal_kind: ty::ClosureKind, ) -> QueryResult<'tcx> { let tcx = ecx.tcx(); - let Some(tupled_inputs_and_output) = - structural_traits::extract_tupled_inputs_and_output_from_callable( - tcx, - goal.predicate.self_ty(), - goal_kind, - )? else { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); - }; + let tupled_inputs_and_output = + match structural_traits::extract_tupled_inputs_and_output_from_callable( + tcx, + goal.predicate.self_ty(), + goal_kind, + )? { + Some(tupled_inputs_and_output) => tupled_inputs_and_output, + None => { + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } + }; let output_is_sized_pred = tupled_inputs_and_output .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output])); @@ -378,27 +334,21 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { LangItem::Sized, [ty::GenericArg::from(goal.predicate.self_ty())], )); - - let (_, is_sized_certainty) = - ecx.evaluate_goal(goal.with(tcx, sized_predicate))?; - return ecx.eq_term_and_make_canonical_response( - goal, - is_sized_certainty, - tcx.types.unit, - ); + ecx.add_goal(goal.with(tcx, sized_predicate)); + tcx.types.unit } ty::Adt(def, substs) if def.is_struct() => { - match def.non_enum_variant().fields.last() { + match def.non_enum_variant().fields.raw.last() { None => tcx.types.unit, Some(field_def) => { let self_ty = field_def.ty(tcx, substs); - let new_goal = goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), - ); - let (_, certainty) = ecx.evaluate_goal(new_goal)?; - return ecx.make_canonical_response(certainty); + )); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } } } @@ -407,12 +357,12 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ty::Tuple(elements) => match elements.last() { None => tcx.types.unit, Some(&self_ty) => { - let new_goal = goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy(goal.predicate.with_self_ty(tcx, self_ty)), - ); - let (_, certainty) = ecx.evaluate_goal(new_goal)?; - return ecx.make_canonical_response(certainty); + )); + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::Yes); } }, @@ -425,7 +375,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ), }; - ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, metadata_ty) + ecx.eq(goal.param_env, goal.predicate.term, metadata_ty.into())?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -512,7 +463,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { fn consider_builtin_dyn_upcast_candidates( _ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - ) -> Vec<super::CanonicalResponse<'tcx>> { + ) -> Vec<CanonicalResponse<'tcx>> { bug!("`Unsize` does not have an associated type: {:?}", goal); } @@ -520,8 +471,65 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - let discriminant = goal.predicate.self_ty().discriminant_ty(ecx.tcx()); - ecx.probe(|ecx| ecx.eq_term_and_make_canonical_response(goal, Certainty::Yes, discriminant)) + let self_ty = goal.predicate.self_ty(); + let discriminant_ty = match *self_ty.kind() { + ty::Bool + | ty::Char + | ty::Int(..) + | ty::Uint(..) + | ty::Float(..) + | ty::Array(..) + | ty::RawPtr(..) + | ty::Ref(..) + | ty::FnDef(..) + | ty::FnPtr(..) + | ty::Closure(..) + | ty::Infer(ty::IntVar(..) | ty::FloatVar(..)) + | ty::Generator(..) + | ty::GeneratorWitness(..) + | ty::GeneratorWitnessMIR(..) + | ty::Never + | ty::Foreign(..) + | ty::Adt(_, _) + | ty::Str + | ty::Slice(_) + | ty::Dynamic(_, _, _) + | ty::Tuple(_) + | ty::Error(_) => self_ty.discriminant_ty(ecx.tcx()), + + // We do not call `Ty::discriminant_ty` on alias, param, or placeholder + // types, which return `<self_ty as DiscriminantKind>::Discriminant` + // (or ICE in the case of placeholders). Projecting a type to itself + // is never really productive. + ty::Alias(_, _) | ty::Param(_) | ty::Placeholder(..) => { + return Err(NoSolution); + } + + ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) + | ty::Bound(..) => bug!( + "unexpected self ty `{:?}` when normalizing `<T as DiscriminantKind>::Discriminant`", + goal.predicate.self_ty() + ), + }; + + ecx.probe(|ecx| { + ecx.eq(goal.param_env, goal.predicate.term, discriminant_ty.into())?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + + fn consider_builtin_destruct_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`Destruct` does not have an associated type: {:?}", goal); + } + + fn consider_builtin_transmute_candidate( + _ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + bug!("`BikeshedIntrinsicFrom` does not have an associated type: {:?}", goal) } } @@ -529,15 +537,15 @@ impl<'tcx> assembly::GoalKind<'tcx> for ProjectionPredicate<'tcx> { /// /// FIXME: We should merge these 3 implementations as it's likely that they otherwise /// diverge. -#[instrument(level = "debug", skip(infcx, param_env), ret)] +#[instrument(level = "debug", skip(ecx, param_env), ret)] fn fetch_eligible_assoc_item_def<'tcx>( - infcx: &InferCtxt<'tcx>, + ecx: &EvalCtxt<'_, 'tcx>, param_env: ty::ParamEnv<'tcx>, goal_trait_ref: ty::TraitRef<'tcx>, trait_assoc_def_id: DefId, impl_def_id: DefId, ) -> Result<Option<LeafDef>, NoSolution> { - let node_item = specialization_graph::assoc_def(infcx.tcx, impl_def_id, trait_assoc_def_id) + let node_item = specialization_graph::assoc_def(ecx.tcx(), impl_def_id, trait_assoc_def_id) .map_err(|ErrorGuaranteed { .. }| NoSolution)?; let eligible = if node_item.is_final() { @@ -549,7 +557,7 @@ fn fetch_eligible_assoc_item_def<'tcx>( // transmute checking and polymorphic MIR optimizations could // get a result which isn't correct for all monomorphizations. if param_env.reveal() == Reveal::All { - let poly_trait_ref = infcx.resolve_vars_if_possible(goal_trait_ref); + let poly_trait_ref = ecx.resolve_vars_if_possible(goal_trait_ref); !poly_trait_ref.still_further_specializable() } else { debug!(?node_item.item.def_id, "not eligible due to default"); diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs index 86b13c05f..d1b4fa554 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/cache.rs @@ -8,12 +8,10 @@ //! //! 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::overflow::OverflowData; use super::StackDepth; -use crate::solve::{CanonicalGoal, QueryResult}; use rustc_data_structures::fx::FxHashMap; use rustc_index::vec::IndexVec; -use rustc_middle::ty::TyCtxt; +use rustc_middle::traits::solve::{CanonicalGoal, QueryResult}; rustc_index::newtype_index! { pub struct EntryIndex {} @@ -98,26 +96,3 @@ impl<'tcx> ProvisionalCache<'tcx> { self.entries[entry_index].response } } - -pub(super) fn try_move_finished_goal_to_global_cache<'tcx>( - tcx: TyCtxt<'tcx>, - overflow_data: &mut OverflowData, - stack: &IndexVec<super::StackDepth, super::StackElem<'tcx>>, - goal: CanonicalGoal<'tcx>, - response: QueryResult<'tcx>, -) { - // We move goals to the global cache if we either did not hit an overflow or if it's - // the root goal as that will now always hit the same overflow limit. - // - // NOTE: We cannot move any non-root goals to the global cache even if their final result - // isn't impacted by the overflow as that goal still has unstable query dependencies - // because it didn't go its full depth. - // - // FIXME(@lcnr): We could still cache subtrees which are not impacted by overflow though. - // Tracking that info correctly isn't trivial, so I haven't implemented it for now. - let should_cache_globally = !overflow_data.did_overflow() || stack.is_empty(); - if should_cache_globally { - // FIXME: move the provisional entry to the global cache. - let _ = (tcx, goal, 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 c7eb8de65..050269fa9 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/mod.rs @@ -1,15 +1,19 @@ mod cache; mod overflow; +pub(super) use overflow::OverflowHandler; + use self::cache::ProvisionalEntry; -use super::{CanonicalGoal, Certainty, MaybeCause, QueryResult}; -pub(super) use crate::solve::search_graph::overflow::OverflowHandler; use cache::ProvisionalCache; use overflow::OverflowData; use rustc_index::vec::IndexVec; +use rustc_middle::dep_graph::DepKind; +use rustc_middle::traits::solve::{CanonicalGoal, Certainty, MaybeCause, QueryResult}; use rustc_middle::ty::TyCtxt; use std::{collections::hash_map::Entry, mem}; +use super::SolverMode; + rustc_index::newtype_index! { pub struct StackDepth {} } @@ -20,6 +24,7 @@ struct StackElem<'tcx> { } pub(super) struct SearchGraph<'tcx> { + mode: SolverMode, /// The stack of goals currently being computed. /// /// An element is *deeper* in the stack if its index is *lower*. @@ -29,24 +34,43 @@ pub(super) struct SearchGraph<'tcx> { } impl<'tcx> SearchGraph<'tcx> { - pub(super) fn new(tcx: TyCtxt<'tcx>) -> SearchGraph<'tcx> { + pub(super) fn new(tcx: TyCtxt<'tcx>, mode: SolverMode) -> SearchGraph<'tcx> { Self { + mode, stack: Default::default(), overflow_data: OverflowData::new(tcx), provisional_cache: ProvisionalCache::empty(), } } + pub(super) fn solver_mode(&self) -> SolverMode { + self.mode + } + + /// We do not use the global cache during coherence. + /// + /// The trait solver behavior is different for coherence + /// so we would have to add the solver mode to the cache key. + /// This is probably not worth it as trait solving during + /// coherence tends to already be incredibly fast. + /// + /// We could add another global cache for coherence instead, + /// but that's effort so let's only do it if necessary. + pub(super) fn should_use_global_cache(&self) -> bool { + match self.mode { + SolverMode::Normal => true, + SolverMode::Coherence => false, + } + } + pub(super) fn is_empty(&self) -> bool { - self.stack.is_empty() - && self.provisional_cache.is_empty() - && !self.overflow_data.did_overflow() + self.stack.is_empty() && self.provisional_cache.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() { + 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; @@ -70,8 +94,6 @@ impl<'tcx> SearchGraph<'tcx> { tcx: TyCtxt<'tcx>, goal: CanonicalGoal<'tcx>, ) -> Result<(), QueryResult<'tcx>> { - // FIXME: start by checking the global cache - // Look at the provisional cache to check for cycles. let cache = &mut self.provisional_cache; match cache.lookup_table.entry(goal) { @@ -131,7 +153,7 @@ impl<'tcx> SearchGraph<'tcx> { /// coinductive cycles. /// /// When we encounter a coinductive cycle, we have to prove the final result of that cycle - /// while we are still computing that result. Because of this we continously recompute the + /// while we are still computing that result. 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. /// @@ -139,10 +161,9 @@ impl<'tcx> SearchGraph<'tcx> { /// updated the provisional cache and we have to recompute the current goal. /// /// FIXME: Refer to the rustc-dev-guide entry once it exists. - #[instrument(level = "debug", skip(self, tcx, actual_goal), ret)] + #[instrument(level = "debug", skip(self, actual_goal), ret)] fn try_finalize_goal( &mut self, - tcx: TyCtxt<'tcx>, actual_goal: CanonicalGoal<'tcx>, response: QueryResult<'tcx>, ) -> bool { @@ -176,72 +197,90 @@ impl<'tcx> SearchGraph<'tcx> { self.stack.push(StackElem { goal, has_been_used: false }); false } else { - self.try_move_finished_goal_to_global_cache(tcx, stack_elem); true } } - fn try_move_finished_goal_to_global_cache( + pub(super) fn with_new_goal( &mut self, tcx: TyCtxt<'tcx>, - stack_elem: StackElem<'tcx>, - ) { - let StackElem { goal, .. } = stack_elem; + canonical_goal: CanonicalGoal<'tcx>, + mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>, + ) -> QueryResult<'tcx> { + if self.should_use_global_cache() { + if let Some(result) = tcx.new_solver_evaluation_cache.get(&canonical_goal, tcx) { + debug!(?canonical_goal, ?result, "cache hit"); + return result; + } + } + + match self.try_push_stack(tcx, canonical_goal) { + Ok(()) => {} + // Our goal is already on the stack, eager return. + Err(response) => return response, + } + + // This is for global caching, so we properly track query dependencies. + // Everything that affects the `Result` should be performed within this + // `with_anon_task` closure. + let (result, dep_node) = tcx.dep_graph.with_anon_task(tcx, DepKind::TraitSelect, || { + self.repeat_while_none( + |this| { + let result = this.deal_with_overflow(tcx, canonical_goal); + let _ = this.stack.pop().unwrap(); + result + }, + |this| { + let result = loop_body(this); + this.try_finalize_goal(canonical_goal, result).then(|| result) + }, + ) + }); + let cache = &mut self.provisional_cache; - let provisional_entry_index = *cache.lookup_table.get(&goal).unwrap(); + let provisional_entry_index = *cache.lookup_table.get(&canonical_goal).unwrap(); let provisional_entry = &mut cache.entries[provisional_entry_index]; let depth = provisional_entry.depth; // If not, we're done with this goal. // // Check whether that this goal doesn't depend on a goal deeper on the stack - // and if so, move it and all nested goals to the global cache. + // and if so, move it to the global cache. // // Note that if any nested goal were to depend on something deeper on the stack, // this would have also updated the depth of the current goal. if depth == self.stack.next_index() { - for (i, entry) in cache.entries.drain_enumerated(provisional_entry_index.index()..) { + // If the current goal is the head of a cycle, we drop all other + // cycle participants without moving them to the global cache. + let other_cycle_participants = provisional_entry_index.index() + 1; + for (i, entry) in cache.entries.drain_enumerated(other_cycle_participants..) { let actual_index = cache.lookup_table.remove(&entry.goal); debug_assert_eq!(Some(i), actual_index); debug_assert!(entry.depth == depth); - cache::try_move_finished_goal_to_global_cache( - tcx, - &mut self.overflow_data, - &self.stack, - entry.goal, - entry.response, - ); } - } - } - pub(super) fn with_new_goal( - &mut self, - tcx: TyCtxt<'tcx>, - canonical_goal: CanonicalGoal<'tcx>, - mut loop_body: impl FnMut(&mut Self) -> QueryResult<'tcx>, - ) -> QueryResult<'tcx> { - match self.try_push_stack(tcx, canonical_goal) { - Ok(()) => {} - // Our goal is already on the stack, eager return. - Err(response) => return response, + let current_goal = cache.entries.pop().unwrap(); + let actual_index = cache.lookup_table.remove(¤t_goal.goal); + debug_assert_eq!(Some(provisional_entry_index), actual_index); + debug_assert!(current_goal.depth == depth); + + // We move the root goal to the global cache if we either did not hit an overflow or if it's + // the root goal as that will now always hit the same overflow limit. + // + // NOTE: We cannot move any non-root goals to the global cache. When replaying the root goal's + // dependencies, our non-root goal may no longer appear as child of the root goal. + // + // See https://github.com/rust-lang/rust/pull/108071 for some additional context. + let can_cache = !self.overflow_data.did_overflow() || self.stack.is_empty(); + if self.should_use_global_cache() && can_cache { + tcx.new_solver_evaluation_cache.insert( + current_goal.goal, + dep_node, + current_goal.response, + ); + } } - self.repeat_while_none( - |this| { - let result = this.deal_with_overflow(tcx, canonical_goal); - let stack_elem = this.stack.pop().unwrap(); - this.try_move_finished_goal_to_global_cache(tcx, stack_elem); - result - }, - |this| { - let result = loop_body(this); - if this.try_finalize_goal(tcx, canonical_goal, result) { - Some(result) - } else { - None - } - }, - ) + result } } diff --git a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs index 56409b060..e0a2e0c5c 100644 --- a/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs +++ b/compiler/rustc_trait_selection/src/solve/search_graph/overflow.rs @@ -1,10 +1,11 @@ use rustc_infer::infer::canonical::Canonical; use rustc_infer::traits::query::NoSolution; +use rustc_middle::traits::solve::{Certainty, MaybeCause, QueryResult}; use rustc_middle::ty::TyCtxt; use rustc_session::Limit; use super::SearchGraph; -use crate::solve::{response_no_constraints, Certainty, EvalCtxt, MaybeCause, QueryResult}; +use crate::solve::{response_no_constraints, EvalCtxt}; /// When detecting a solver overflow, we return ambiguity. Overflow can be /// *hidden* by either a fatal error in an **AND** or a trivial success in an **OR**. @@ -44,7 +45,7 @@ impl OverflowData { /// Updating the current limit when hitting overflow. fn deal_with_overflow(&mut self) { // When first hitting overflow we reduce the overflow limit - // for all future goals to prevent hangs if there's an exponental + // for all future goals to prevent hangs if there's an exponential // blowup. self.current_limit.0 = self.default_limit.0 / 8; } @@ -72,6 +73,27 @@ pub(in crate::solve) trait OverflowHandler<'tcx> { self.search_graph().overflow_data.deal_with_overflow(); on_overflow(self) } + + // Increment the `additional_depth` by one and evaluate `body`, or `on_overflow` + // if the depth is overflown. + fn with_incremented_depth<T>( + &mut self, + on_overflow: impl FnOnce(&mut Self) -> T, + body: impl FnOnce(&mut Self) -> T, + ) -> T { + let depth = self.search_graph().stack.len(); + self.search_graph().overflow_data.additional_depth += 1; + + let result = if self.search_graph().overflow_data.has_overflow(depth) { + self.search_graph().overflow_data.deal_with_overflow(); + on_overflow(self) + } else { + body(self) + }; + + self.search_graph().overflow_data.additional_depth -= 1; + result + } } impl<'tcx> OverflowHandler<'tcx> for EvalCtxt<'_, 'tcx> { diff --git a/compiler/rustc_trait_selection/src/solve/trait_goals.rs b/compiler/rustc_trait_selection/src/solve/trait_goals.rs index 5c499c36e..abd11a15a 100644 --- a/compiler/rustc_trait_selection/src/solve/trait_goals.rs +++ b/compiler/rustc_trait_selection/src/solve/trait_goals.rs @@ -1,25 +1,26 @@ //! Dealing with trait goals, i.e. `T: Trait<'a, U>`. -use std::iter; - -use super::assembly; -use super::{CanonicalResponse, Certainty, EvalCtxt, Goal, QueryResult}; +use super::assembly::{self, structural_traits}; +use super::{EvalCtxt, SolverMode}; use rustc_hir::def_id::DefId; -use rustc_hir::LangItem; +use rustc_hir::{LangItem, Movability}; use rustc_infer::traits::query::NoSolution; use rustc_infer::traits::util::supertraits; -use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; +use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, QueryResult}; +use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams, TreatProjections}; use rustc_middle::ty::{self, ToPredicate, Ty, TyCtxt}; use rustc_middle::ty::{TraitPredicate, TypeVisitableExt}; use rustc_span::DUMMY_SP; -pub mod structural_traits; - impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { fn self_ty(self) -> Ty<'tcx> { self.self_ty() } + fn trait_ref(self, _: TyCtxt<'tcx>) -> ty::TraitRef<'tcx> { + self.trait_ref + } + fn with_self_ty(self, tcx: TyCtxt<'tcx>, self_ty: Ty<'tcx>) -> Self { self.with_self_ty(tcx, self_ty) } @@ -36,27 +37,44 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let tcx = ecx.tcx(); let impl_trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); - let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsPlaceholder }; - if iter::zip(goal.predicate.trait_ref.substs, impl_trait_ref.skip_binder().substs) - .any(|(goal, imp)| !drcx.generic_args_may_unify(goal, imp)) - { + let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::ForLookup }; + if !drcx.substs_refs_may_unify( + goal.predicate.trait_ref.substs, + impl_trait_ref.skip_binder().substs, + ) { return Err(NoSolution); } + let impl_polarity = tcx.impl_polarity(impl_def_id); + // An upper bound of the certainty of this goal, used to lower the certainty + // of reservation impl to ambiguous during coherence. + let maximal_certainty = match impl_polarity { + ty::ImplPolarity::Positive | ty::ImplPolarity::Negative => { + match impl_polarity == goal.predicate.polarity { + true => Certainty::Yes, + false => return Err(NoSolution), + } + } + ty::ImplPolarity::Reservation => match ecx.solver_mode() { + SolverMode::Normal => return Err(NoSolution), + SolverMode::Coherence => Certainty::AMBIGUOUS, + }, + }; + ecx.probe(|ecx| { let impl_substs = ecx.fresh_substs_for_item(impl_def_id); let impl_trait_ref = impl_trait_ref.subst(tcx, impl_substs); - let mut nested_goals = - ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; + ecx.eq(goal.param_env, goal.predicate.trait_ref, impl_trait_ref)?; let where_clause_bounds = tcx .predicates_of(impl_def_id) .instantiate(tcx, impl_substs) .predicates .into_iter() .map(|pred| goal.with(tcx, pred)); - nested_goals.extend(where_clause_bounds); - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.add_goals(where_clause_bounds); + + ecx.evaluate_added_goals_and_make_canonical_response(maximal_certainty) }) } @@ -73,13 +91,13 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx.probe(|ecx| { let assumption_trait_pred = ecx.instantiate_binder_with_infer(poly_trait_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref, )?; - nested_goals.extend(requirements); - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.add_goals(requirements); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -98,7 +116,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx.probe(|ecx| { let assumption_trait_pred = ecx.instantiate_binder_with_infer(poly_trait_pred); - let mut nested_goals = ecx.eq( + ecx.eq( goal.param_env, goal.predicate.trait_ref, assumption_trait_pred.trait_ref, @@ -108,9 +126,9 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { bug!("expected object type in `consider_object_bound_candidate`"); }; - nested_goals.extend( + ecx.add_goals( structural_traits::predicates_for_object_candidate( - ecx, + &ecx, goal.param_env, goal.predicate.trait_ref, bounds, @@ -118,8 +136,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { .into_iter() .map(|pred| goal.with(tcx, pred)), ); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } else { Err(NoSolution) @@ -130,18 +147,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - // This differs from the current stable behavior and - // fixes #84857. Due to breakage found via crater, we - // currently instead lint patterns which can be used to - // exploit this unsoundness on stable, see #93367 for - // more details. - if let Some(def_id) = ecx.tcx().find_map_relevant_impl( - goal.predicate.def_id(), - goal.predicate.self_ty(), - Some, - ) { - debug!(?def_id, ?goal, "disqualified auto-trait implementation"); - return Err(NoSolution); + if let Some(result) = ecx.disqualify_auto_trait_candidate_due_to_possible_impl(goal) { + return result; } ecx.probe_and_evaluate_goal_for_constituent_tys( @@ -160,9 +167,8 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let nested_obligations = tcx .predicates_of(goal.predicate.def_id()) .instantiate(tcx, goal.predicate.trait_ref.substs); - ecx.evaluate_all_and_make_canonical_response( - nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p)).collect(), - ) + ecx.add_goals(nested_obligations.predicates.into_iter().map(|p| goal.with(tcx, p))); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } @@ -191,19 +197,28 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { if goal.predicate.self_ty().has_non_region_infer() { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); } let tcx = ecx.tcx(); let self_ty = tcx.erase_regions(goal.predicate.self_ty()); if let Ok(layout) = tcx.layout_of(goal.param_env.and(self_ty)) - && let usize_layout = tcx.layout_of(ty::ParamEnv::empty().and(tcx.types.usize)).unwrap().layout - && layout.layout.size() == usize_layout.size() - && layout.layout.align().abi == usize_layout.align().abi + && layout.layout.is_pointer_like(&tcx.data_layout) { // FIXME: We could make this faster by making a no-constraints response - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } else { + Err(NoSolution) + } + } + + fn consider_builtin_fn_ptr_trait_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + if let ty::FnPtr(..) = goal.predicate.self_ty().kind() { + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } @@ -215,14 +230,18 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal_kind: ty::ClosureKind, ) -> QueryResult<'tcx> { let tcx = ecx.tcx(); - let Some(tupled_inputs_and_output) = - structural_traits::extract_tupled_inputs_and_output_from_callable( + let tupled_inputs_and_output = + match structural_traits::extract_tupled_inputs_and_output_from_callable( tcx, goal.predicate.self_ty(), goal_kind, - )? else { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); - }; + )? { + Some(a) => a, + None => { + return ecx + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } + }; let output_is_sized_pred = tupled_inputs_and_output .map_bound(|(_, output)| tcx.at(DUMMY_SP).mk_trait_ref(LangItem::Sized, [output])); @@ -241,7 +260,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { if let ty::Tuple(..) = goal.predicate.self_ty().kind() { - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } else { Err(NoSolution) } @@ -251,7 +270,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { ecx: &mut EvalCtxt<'_, 'tcx>, _goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } fn consider_builtin_future_candidate( @@ -271,7 +290,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Async generator unconditionally implement `Future` // Technically, we need to check that the future output type is Sized, // but that's already proven by the generator being WF. - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } fn consider_builtin_generator_candidate( @@ -311,7 +330,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let a_ty = goal.predicate.self_ty(); let b_ty = goal.predicate.trait_ref.substs.type_at(1); if b_ty.is_ty_var() { - return ecx.make_canonical_response(Certainty::AMBIGUOUS); + return ecx.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); } ecx.probe(|ecx| { match (a_ty.kind(), b_ty.kind()) { @@ -320,7 +339,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Dyn upcasting is handled separately, since due to upcasting, // when there are two supertraits that differ by substs, we // may return more than one query response. - return Err(NoSolution); + Err(NoSolution) } // `T` -> `dyn Trait` unsizing (_, &ty::Dynamic(data, region, ty::Dyn)) => { @@ -335,29 +354,26 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let Some(sized_def_id) = tcx.lang_items().sized_trait() else { return Err(NoSolution); }; - let nested_goals: Vec<_> = data - .iter() - // Check that the type implements all of the predicates of the def-id. - // (i.e. the principal, all of the associated types match, and any auto traits) - .map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))) - .chain([ - // The type must be Sized to be unsized. - goal.with( - tcx, - ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty])), - ), - // The type must outlive the lifetime of the `dyn` we're unsizing into. - goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))), - ]) - .collect(); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + // Check that the type implements all of the predicates of the def-id. + // (i.e. the principal, all of the associated types match, and any auto traits) + ecx.add_goals( + data.iter().map(|pred| goal.with(tcx, pred.with_self_ty(tcx, a_ty))), + ); + // The type must be Sized to be unsized. + ecx.add_goal( + goal.with(tcx, ty::Binder::dummy(tcx.mk_trait_ref(sized_def_id, [a_ty]))), + ); + // The type must outlive the lifetime of the `dyn` we're unsizing into. + ecx.add_goal( + goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_ty, region))), + ); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } // `[T; n]` -> `[T]` unsizing (&ty::Array(a_elem_ty, ..), &ty::Slice(b_elem_ty)) => { // We just require that the element type stays the same - let nested_goals = ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?; - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.eq(goal.param_env, a_elem_ty, b_elem_ty)?; + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } // Struct unsizing `Struct<T>` -> `Struct<U>` where `T: Unsize<U>` (&ty::Adt(a_def, a_substs), &ty::Adt(b_def, b_substs)) @@ -373,6 +389,7 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let tail_field = a_def .non_enum_variant() .fields + .raw .last() .expect("expected unsized ADT to have a tail field"); let tail_field_ty = tcx.type_of(tail_field.did); @@ -391,15 +408,14 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Finally, we require that `TailA: Unsize<TailB>` for the tail field // types. - let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; - nested_goals.push(goal.with( + ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; + ecx.add_goal(goal.with( tcx, ty::Binder::dummy( tcx.mk_trait_ref(goal.predicate.def_id(), [a_tail_ty, b_tail_ty]), ), )); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } // Tuple unsizing `(.., T)` -> `(.., U)` where `T: Unsize<U>` (&ty::Tuple(a_tys), &ty::Tuple(b_tys)) @@ -411,17 +427,16 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { // Substitute just the tail field of B., and require that they're equal. let unsized_a_ty = tcx.mk_tup_from_iter(a_rest_tys.iter().chain([b_last_ty]).copied()); - let mut nested_goals = ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; + ecx.eq(goal.param_env, unsized_a_ty, b_ty)?; // Similar to ADTs, require that the rest of the fields are equal. - nested_goals.push(goal.with( + ecx.add_goal(goal.with( tcx, ty::Binder::dummy( tcx.mk_trait_ref(goal.predicate.def_id(), [*a_last_ty, *b_last_ty]), ), )); - - ecx.evaluate_all_and_make_canonical_response(nested_goals) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) } _ => Err(NoSolution), } @@ -471,12 +486,11 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { let new_a_ty = tcx.mk_dynamic(new_a_data, b_region, ty::Dyn); // We also require that A's lifetime outlives B's lifetime. - let mut nested_obligations = ecx.eq(goal.param_env, new_a_ty, b_ty)?; - nested_obligations.push( + ecx.eq(goal.param_env, new_a_ty, b_ty)?; + ecx.add_goal( goal.with(tcx, ty::Binder::dummy(ty::OutlivesPredicate(a_region, b_region))), ); - - ecx.evaluate_all_and_make_canonical_response(nested_obligations) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) }; @@ -510,11 +524,145 @@ impl<'tcx> assembly::GoalKind<'tcx> for TraitPredicate<'tcx> { _goal: Goal<'tcx, Self>, ) -> QueryResult<'tcx> { // `DiscriminantKind` is automatically implemented for every type. - ecx.make_canonical_response(Certainty::Yes) + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + + fn consider_builtin_destruct_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + if !goal.param_env.is_const() { + // `Destruct` is automatically implemented for every type in + // non-const environments. + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } else { + // FIXME(-Ztrait-solver=next): Implement this when we get const working in the new solver + Err(NoSolution) + } + } + + fn consider_builtin_transmute_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + ) -> QueryResult<'tcx> { + // `rustc_transmute` does not have support for type or const params + if goal.has_non_region_placeholders() { + return Err(NoSolution); + } + + // Erase regions because we compute layouts in `rustc_transmute`, + // which will ICE for region vars. + let substs = ecx.tcx().erase_regions(goal.predicate.trait_ref.substs); + + let Some(assume) = rustc_transmute::Assume::from_const( + ecx.tcx(), + goal.param_env, + substs.const_at(3), + ) else { + return Err(NoSolution); + }; + + let certainty = ecx.is_transmutable( + rustc_transmute::Types { dst: substs.type_at(0), src: substs.type_at(1) }, + substs.type_at(2), + assume, + )?; + ecx.evaluate_added_goals_and_make_canonical_response(certainty) } } impl<'tcx> EvalCtxt<'_, 'tcx> { + // Return `Some` if there is an impl (built-in or user provided) that may + // hold for the self type of the goal, which for coherence and soundness + // purposes must disqualify the built-in auto impl assembled by considering + // the type's constituent types. + fn disqualify_auto_trait_candidate_due_to_possible_impl( + &mut self, + goal: Goal<'tcx, TraitPredicate<'tcx>>, + ) -> Option<QueryResult<'tcx>> { + let self_ty = goal.predicate.self_ty(); + match *self_ty.kind() { + // Stall int and float vars until they are resolved to a concrete + // numerical type. That's because the check for impls below treats + // int vars as matching any impl. Even if we filtered such impls, + // we probably don't want to treat an `impl !AutoTrait for i32` as + // disqualifying the built-in auto impl for `i64: AutoTrait` either. + ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) => { + Some(self.evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS)) + } + + // These types cannot be structurally decomposed into constitutent + // types, and therefore have no built-in auto impl. + ty::Dynamic(..) + | ty::Param(..) + | ty::Foreign(..) + | ty::Alias(ty::Projection, ..) + | ty::Placeholder(..) => Some(Err(NoSolution)), + + ty::Infer(_) | ty::Bound(_, _) => bug!("unexpected type `{self_ty}`"), + + // Generators have one special built-in candidate, `Unpin`, which + // takes precedence over the structural auto trait candidate being + // assembled. + ty::Generator(_, _, movability) + if Some(goal.predicate.def_id()) == self.tcx().lang_items().unpin_trait() => + { + match movability { + Movability::Static => Some(Err(NoSolution)), + Movability::Movable => { + Some(self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes)) + } + } + } + + // For rigid types, any possible implementation that could apply to + // the type (even if after unification and processing nested goals + // it does not hold) will disqualify the built-in auto impl. + // + // This differs from the current stable behavior and fixes #84857. + // Due to breakage found via crater, we currently instead lint + // patterns which can be used to exploit this unsoundness on stable, + // see #93367 for more details. + ty::Bool + | ty::Char + | ty::Int(_) + | ty::Uint(_) + | ty::Float(_) + | ty::Str + | ty::Array(_, _) + | ty::Slice(_) + | ty::RawPtr(_) + | ty::Ref(_, _, _) + | ty::FnDef(_, _) + | ty::FnPtr(_) + | ty::Closure(_, _) + | ty::Generator(_, _, _) + | ty::GeneratorWitness(_) + | ty::GeneratorWitnessMIR(_, _) + | ty::Never + | ty::Tuple(_) + | ty::Adt(_, _) + // FIXME: Handling opaques here is kinda sus. Especially because we + // simplify them to PlaceholderSimplifiedType. + | ty::Alias(ty::Opaque, _) => { + if let Some(def_id) = self.tcx().find_map_relevant_impl( + goal.predicate.def_id(), + goal.predicate.self_ty(), + TreatProjections::NextSolverLookup, + Some, + ) { + debug!(?def_id, ?goal, "disqualified auto-trait implementation"); + // No need to actually consider the candidate here, + // since we do that in `consider_impl_candidate`. + return Some(Err(NoSolution)); + } else { + None + } + } + ty::Error(_) => None, + } + } + /// Convenience function for traits that are structural, i.e. that only /// have nested subgoals that only change the self type. Unlike other /// evaluate-like helpers, this does a probe, so it doesn't need to be @@ -524,26 +672,28 @@ 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(|this| { - this.evaluate_all_and_make_canonical_response( - constituent_tys(this, goal.predicate.self_ty())? + self.probe(|ecx| { + ecx.add_goals( + constituent_tys(ecx, goal.predicate.self_ty())? .into_iter() .map(|ty| { goal.with( - this.tcx(), - ty::Binder::dummy(goal.predicate.with_self_ty(this.tcx(), ty)), + ecx.tcx(), + ty::Binder::dummy(goal.predicate.with_self_ty(ecx.tcx(), ty)), ) }) - .collect(), - ) + .collect::<Vec<_>>(), + ); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) }) } + #[instrument(level = "debug", skip(self))] pub(super) fn compute_trait_goal( &mut self, goal: Goal<'tcx, TraitPredicate<'tcx>>, ) -> QueryResult<'tcx> { let candidates = self.assemble_and_evaluate_candidates(goal); - self.merge_candidates_and_discard_reservation_impls(candidates) + self.merge_candidates(candidates) } } |