From 9835e2ae736235810b4ea1c162ca5e65c547e770 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 18 May 2024 04:49:50 +0200 Subject: Merging upstream version 1.71.1+dfsg1. Signed-off-by: Daniel Baumann --- .../src/solve/assembly/mod.rs | 188 +++++++++++++++++++-- .../src/solve/assembly/structural_traits.rs | 11 +- 2 files changed, 179 insertions(+), 20 deletions(-) (limited to 'compiler/rustc_trait_selection/src/solve/assembly') diff --git a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs index 10d817f75..f32ff0442 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -2,12 +2,12 @@ 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; +use rustc_infer::traits::Reveal; use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult}; use rustc_middle::ty::fast_reject::TreatProjections; use rustc_middle::ty::TypeFoldable; @@ -51,7 +51,7 @@ pub(super) enum CandidateSource { BuiltinImpl, /// An assumption from the environment. /// - /// More precicely we've used the `n-th` assumption in the `param_env`. + /// More precisely we've used the `n-th` assumption in the `param_env`. /// /// ## Examples /// @@ -87,7 +87,9 @@ pub(super) enum CandidateSource { } /// Methods used to assemble candidates for either trait or projection goals. -pub(super) trait GoalKind<'tcx>: TypeFoldable> + Copy + Eq { +pub(super) trait GoalKind<'tcx>: + TypeFoldable> + Copy + Eq + std::fmt::Display +{ fn self_ty(self) -> Ty<'tcx>; fn trait_ref(self, tcx: TyCtxt<'tcx>) -> ty::TraitRef<'tcx>; @@ -96,6 +98,17 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable> + Copy + Eq { fn trait_def_id(self, tcx: TyCtxt<'tcx>) -> DefId; + // Try equating an assumption predicate against a goal's predicate. If it + // holds, then execute the `then` callback, which should do any additional + // work, then produce a response (typically by executing + // [`EvalCtxt::evaluate_added_goals_and_make_canonical_response`]). + fn probe_and_match_goal_against_assumption( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Predicate<'tcx>, + then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>, + ) -> QueryResult<'tcx>; + // Consider a clause, which consists of a "assumption" and some "requirements", // to satisfy a goal. If the requirements hold, then attempt to satisfy our // goal by equating it with the assumption. @@ -104,7 +117,26 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable> + Copy + Eq { goal: Goal<'tcx, Self>, assumption: ty::Predicate<'tcx>, requirements: impl IntoIterator>>, - ) -> QueryResult<'tcx>; + ) -> QueryResult<'tcx> { + Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { + ecx.add_goals(requirements); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } + + /// Consider a bound originating from the item bounds of an alias. For this we + /// require that the well-formed requirements of the self type of the goal + /// are "satisfied from the param-env". + /// See [`EvalCtxt::validate_alias_bound_self_from_param_env`]. + fn consider_alias_bound_candidate( + ecx: &mut EvalCtxt<'_, 'tcx>, + goal: Goal<'tcx, Self>, + assumption: ty::Predicate<'tcx>, + ) -> QueryResult<'tcx> { + Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { + ecx.validate_alias_bound_self_from_param_env(goal) + }) + } // Consider a clause specifically for a `dyn Trait` self type. This requires // additionally checking all of the supertraits and object bounds to hold, @@ -113,7 +145,25 @@ pub(super) trait GoalKind<'tcx>: TypeFoldable> + Copy + Eq { ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, assumption: ty::Predicate<'tcx>, - ) -> QueryResult<'tcx>; + ) -> QueryResult<'tcx> { + Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { + let tcx = ecx.tcx(); + let ty::Dynamic(bounds, _, _) = *goal.predicate.self_ty().kind() else { + bug!("expected object type in `consider_object_bound_candidate`"); + }; + ecx.add_goals( + structural_traits::predicates_for_object_candidate( + &ecx, + goal.param_env, + goal.predicate.trait_ref(tcx), + bounds, + ) + .into_iter() + .map(|pred| goal.with(tcx, pred)), + ); + ecx.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + }) + } fn consider_impl_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, @@ -241,7 +291,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // HACK: `_: Trait` is ambiguous, because it may be satisfied via a builtin rule, // object bound, alias bound, etc. We are unable to determine this until we can at - // least structually resolve the type one layer. + // least structurally resolve the type one layer. if goal.predicate.self_ty().is_ty_var() { return vec![Candidate { source: CandidateSource::BuiltinImpl, @@ -282,8 +332,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { candidates: &mut Vec>, ) { let tcx = self.tcx(); - // FIXME: We also have to normalize opaque types, not sure where to best fit that in. - let &ty::Alias(ty::Projection, projection_ty) = goal.predicate.self_ty().kind() else { + let &ty::Alias(_, projection_ty) = goal.predicate.self_ty().kind() else { return }; @@ -305,8 +354,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }), ); ecx.add_goal(normalizes_to_goal); - let _ = ecx.try_evaluate_added_goals()?; + let _ = ecx.try_evaluate_added_goals().inspect_err(|_| { + debug!("self type normalization failed"); + })?; let normalized_ty = ecx.resolve_vars_if_possible(normalized_ty); + debug!(?normalized_ty, "self type normalized"); // 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. @@ -455,15 +507,17 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Param(_) | ty::Placeholder(..) | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) + | ty::Alias(ty::Inherent, _) | ty::Error(_) => return, ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"), - ty::Alias(_, alias_ty) => alias_ty, + // Excluding IATs here as they don't have meaningful item bounds. + ty::Alias(ty::Projection | ty::Opaque, alias_ty) => alias_ty, }; for assumption in self.tcx().item_bounds(alias_ty.def_id).subst(self.tcx(), alias_ty.substs) { - match G::consider_implied_clause(self, goal, assumption, []) { + match G::consider_alias_bound_candidate(self, goal, assumption) { Ok(result) => { candidates.push(Candidate { source: CandidateSource::AliasBound, result }) } @@ -472,6 +526,105 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { } } + /// Check that we are allowed to use an alias bound originating from the self + /// type of this goal. This means something different depending on the self type's + /// alias kind. + /// + /// * Projection: Given a goal with a self type such as `::Assoc`, + /// we require that the bound `Ty: Trait` can be proven using either a nested alias + /// bound candidate, or a param-env candidate. + /// + /// * Opaque: The param-env must be in `Reveal::UserFacing` mode. Otherwise, + /// the goal should be proven by using the hidden type instead. + #[instrument(level = "debug", skip(self), ret)] + pub(super) fn validate_alias_bound_self_from_param_env>( + &mut self, + goal: Goal<'tcx, G>, + ) -> QueryResult<'tcx> { + match *goal.predicate.self_ty().kind() { + ty::Alias(ty::Projection, projection_ty) => { + let mut param_env_candidates = vec![]; + let self_trait_ref = projection_ty.trait_ref(self.tcx()); + + if self_trait_ref.self_ty().is_ty_var() { + return self + .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS); + } + + let trait_goal: Goal<'_, ty::TraitPredicate<'tcx>> = goal.with( + self.tcx(), + ty::TraitPredicate { + trait_ref: self_trait_ref, + constness: ty::BoundConstness::NotConst, + polarity: ty::ImplPolarity::Positive, + }, + ); + + self.assemble_param_env_candidates(trait_goal, &mut param_env_candidates); + // FIXME: We probably need some sort of recursion depth check here. + // Can't come up with an example yet, though, and the worst case + // we can have is a compiler stack overflow... + self.assemble_alias_bound_candidates(trait_goal, &mut param_env_candidates); + + // FIXME: We must also consider alias-bound candidates for a peculiar + // class of built-in candidates that I'll call "defaulted" built-ins. + // + // For example, we always know that `T: Pointee` is implemented, but + // we do not always know what `::Metadata` actually is, + // similar to if we had a user-defined impl with a `default type ...`. + // For these traits, since we're not able to always normalize their + // associated types to a concrete type, we must consider their alias bounds + // instead, so we can prove bounds such as `::Metadata: Copy`. + self.assemble_alias_bound_candidates_for_builtin_impl_default_items( + trait_goal, + &mut param_env_candidates, + ); + + self.merge_candidates(param_env_candidates) + } + ty::Alias(ty::Opaque, _opaque_ty) => match goal.param_env.reveal() { + Reveal::UserFacing => { + self.evaluate_added_goals_and_make_canonical_response(Certainty::Yes) + } + Reveal::All => return Err(NoSolution), + }, + _ => bug!("only expected to be called on alias tys"), + } + } + + /// Assemble a subset of builtin impl candidates for a class of candidates called + /// "defaulted" built-in traits. + /// + /// For example, we always know that `T: Pointee` is implemented, but we do not + /// always know what `::Metadata` actually is! See the comment in + /// [`EvalCtxt::validate_alias_bound_self_from_param_env`] for more detail. + #[instrument(level = "debug", skip_all)] + fn assemble_alias_bound_candidates_for_builtin_impl_default_items>( + &mut self, + goal: Goal<'tcx, G>, + candidates: &mut Vec>, + ) { + let lang_items = self.tcx().lang_items(); + let trait_def_id = goal.predicate.trait_def_id(self.tcx()); + + // You probably shouldn't add anything to this list unless you + // know what you're doing. + let result = if lang_items.pointee_trait() == Some(trait_def_id) { + G::consider_builtin_pointee_candidate(self, goal) + } else if lang_items.discriminant_kind_trait() == Some(trait_def_id) { + G::consider_builtin_discriminant_kind_candidate(self, goal) + } else { + Err(NoSolution) + }; + + match result { + Ok(result) => { + candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) + } + Err(NoSolution) => (), + } + } + #[instrument(level = "debug", skip_all)] fn assemble_object_bound_candidates>( &mut self, @@ -590,13 +743,18 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { SolverMode::Normal => { let param_env_responses = candidates .iter() - .filter(|c| matches!(c.source, CandidateSource::ParamEnv(_))) + .filter(|c| { + matches!( + c.source, + CandidateSource::ParamEnv(_) | CandidateSource::AliasBound + ) + }) .map(|c| c.result) .collect::>(); if let Some(result) = self.try_merge_responses(¶m_env_responses) { - if result.has_only_region_constraints() { - return Ok(result); - } + // We strongly prefer alias and param-env bounds here, even if they affect inference. + // See https://github.com/rust-lang/trait-system-refactor-initiative/issues/11. + return Ok(result); } } } diff --git a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs index 1a566e87d..0ede32c75 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -33,7 +33,7 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( ty::Dynamic(..) | ty::Param(..) | ty::Foreign(..) - | ty::Alias(ty::Projection, ..) + | ty::Alias(ty::Projection | ty::Inherent, ..) | ty::Placeholder(..) | ty::Bound(..) | ty::Infer(_) => { @@ -91,14 +91,15 @@ pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'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 ty = tcx.fold_regions(ty, |r, current_depth| match r.kind() { + ty::ReErased => { let br = ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) }; counter += 1; - r = tcx.mk_re_late_bound(current_depth, br); + tcx.mk_re_late_bound(current_depth, br) } - r + // All free regions should be erased here. + r => bug!("unexpected region: {r:?}"), }); let bound_vars = tcx.mk_bound_variable_kinds_from_iter( (0..counter).map(|_| ty::BoundVariableKind::Region(ty::BrAnon(None))), -- cgit v1.2.3