diff options
Diffstat (limited to 'compiler/rustc_trait_selection/src/solve/trait_goals.rs')
| -rw-r--r-- | compiler/rustc_trait_selection/src/solve/trait_goals.rs | 338 |
1 files changed, 244 insertions, 94 deletions
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) } } |