From dc0db358abe19481e475e10c32149b53370f1a1c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 30 May 2024 05:57:31 +0200 Subject: Merging upstream version 1.72.1+dfsg1. Signed-off-by: Daniel Baumann --- .../src/solve/assembly/mod.rs | 153 +++++++++++++-------- .../src/solve/assembly/structural_traits.rs | 20 ++- 2 files changed, 102 insertions(+), 71 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 f32ff0442..28138054a 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/mod.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/mod.rs @@ -8,6 +8,7 @@ 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::inspect::CandidateKind; use rustc_middle::traits::solve::{CanonicalResponse, Certainty, Goal, MaybeCause, QueryResult}; use rustc_middle::ty::fast_reject::TreatProjections; use rustc_middle::ty::TypeFoldable; @@ -48,7 +49,7 @@ pub(super) enum CandidateSource { /// Notable examples are auto traits, `Sized`, and `DiscriminantKind`. /// For a list of all traits with builtin impls, check out the /// [`EvalCtxt::assemble_builtin_impl_candidates`] method. Not - BuiltinImpl, + BuiltinImpl(BuiltinImplSource), /// An assumption from the environment. /// /// More precisely we've used the `n-th` assumption in the `param_env`. @@ -86,6 +87,16 @@ pub(super) enum CandidateSource { AliasBound, } +/// Records additional information about what kind of built-in impl this is. +/// This should only be used by selection. +#[derive(Debug, Clone, Copy)] +pub(super) enum BuiltinImplSource { + TraitUpcasting, + Object, + Misc, + Ambiguity, +} + /// Methods used to assemble candidates for either trait or projection goals. pub(super) trait GoalKind<'tcx>: TypeFoldable> + Copy + Eq + std::fmt::Display @@ -105,7 +116,7 @@ pub(super) trait GoalKind<'tcx>: fn probe_and_match_goal_against_assumption( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - assumption: ty::Predicate<'tcx>, + assumption: ty::Clause<'tcx>, then: impl FnOnce(&mut EvalCtxt<'_, 'tcx>) -> QueryResult<'tcx>, ) -> QueryResult<'tcx>; @@ -115,7 +126,7 @@ pub(super) trait GoalKind<'tcx>: fn consider_implied_clause( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - assumption: ty::Predicate<'tcx>, + assumption: ty::Clause<'tcx>, requirements: impl IntoIterator>>, ) -> QueryResult<'tcx> { Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { @@ -131,7 +142,7 @@ pub(super) trait GoalKind<'tcx>: fn consider_alias_bound_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - assumption: ty::Predicate<'tcx>, + assumption: ty::Clause<'tcx>, ) -> QueryResult<'tcx> { Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { ecx.validate_alias_bound_self_from_param_env(goal) @@ -144,7 +155,7 @@ pub(super) trait GoalKind<'tcx>: fn consider_object_bound_candidate( ecx: &mut EvalCtxt<'_, 'tcx>, goal: Goal<'tcx, Self>, - assumption: ty::Predicate<'tcx>, + assumption: ty::Clause<'tcx>, ) -> QueryResult<'tcx> { Self::probe_and_match_goal_against_assumption(ecx, goal, assumption, |ecx| { let tcx = ecx.tcx(); @@ -294,7 +305,7 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // least structurally resolve the type one layer. if goal.predicate.self_ty().is_ty_var() { return vec![Candidate { - source: CandidateSource::BuiltinImpl, + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), result: self .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) .unwrap(), @@ -320,11 +331,20 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { candidates } - /// If the self type of a goal is a projection, computing the relevant candidates is difficult. + /// If the self type of a goal is an alias we first try to normalize the self type + /// and compute the candidates for the normalized self type in case that succeeds. + /// + /// These candidates are used in addition to the ones with the alias as a self type. + /// We do this to simplify both builtin candidates and for better performance. + /// + /// We generate the builtin candidates on the fly by looking at the self type, e.g. + /// add `FnPtr` candidates if the self type is a function pointer. Handling builtin + /// candidates while the self type is still an alias seems difficult. This is similar + /// to `try_structurally_resolve_type` during hir typeck (FIXME once implemented). /// - /// 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. We also have to consider candidates with the - /// projection as a self type as well + /// Looking at all impls for some trait goal is prohibitively expensive. We therefore + /// only look at implementations with a matching self type. Because of this function, + /// we can avoid looking at all existing impls if the self type is an alias. #[instrument(level = "debug", skip_all)] fn assemble_candidates_after_normalizing_self_ty>( &mut self, @@ -336,37 +356,41 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { return }; - 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().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. - let goal = goal.with(tcx, goal.predicate.with_self_ty(tcx, normalized_ty)); - Ok(ecx.assemble_and_evaluate_candidates(goal)) - }, - ) - }); + let normalized_self_candidates: Result<_, NoSolution> = + self.probe(|_| CandidateKind::NormalizedSelfTyAssembly).enter(|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(BuiltinImplSource::Ambiguity), + 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().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. + 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); @@ -445,9 +469,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }; match result { - Ok(result) => { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) - } + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), Err(NoSolution) => (), } @@ -455,7 +480,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // `trait Foo: Bar + Bar` and `dyn Foo: Unsize>` if lang_items.unsize_trait() == Some(trait_def_id) { for result in G::consider_builtin_dyn_upcast_candidates(self, goal) { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }); + candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::TraitUpcasting), + result, + }); } } } @@ -508,10 +536,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { | ty::Placeholder(..) | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) | ty::Alias(ty::Inherent, _) + | ty::Alias(ty::Weak, _) | ty::Error(_) => return, ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) | ty::Bound(..) => bug!("unexpected self type for `{goal:?}`"), - // Excluding IATs here as they don't have meaningful item bounds. + // Excluding IATs and type aliases here as they don't have meaningful item bounds. ty::Alias(ty::Projection | ty::Opaque, alias_ty) => alias_ty, }; @@ -618,9 +647,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { }; match result { - Ok(result) => { - candidates.push(Candidate { source: CandidateSource::BuiltinImpl, result }) - } + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Misc), + result, + }), Err(NoSolution) => (), } } @@ -631,6 +661,11 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { goal: Goal<'tcx, G>, candidates: &mut Vec>, ) { + let tcx = self.tcx(); + if !tcx.trait_def(goal.predicate.trait_def_id(tcx)).implement_via_object { + return; + } + let self_ty = goal.predicate.self_ty(); let bounds = match *self_ty.kind() { ty::Bool @@ -663,7 +698,6 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { ty::Dynamic(bounds, ..) => bounds, }; - let tcx = self.tcx(); 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()) @@ -675,17 +709,16 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { // 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) - { + // We can remove this when we have implemented lifetime intersections in responses. + if assumption.as_projection_clause().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 }) - } + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Object), + result, + }), Err(NoSolution) => (), } } @@ -706,8 +739,10 @@ impl<'tcx> EvalCtxt<'_, 'tcx> { Err(_) => match self .evaluate_added_goals_and_make_canonical_response(Certainty::AMBIGUOUS) { - Ok(result) => candidates - .push(Candidate { source: CandidateSource::BuiltinImpl, result }), + Ok(result) => candidates.push(Candidate { + source: CandidateSource::BuiltinImpl(BuiltinImplSource::Ambiguity), + 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. 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 0ede32c75..3bb8cad15 100644 --- a/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs +++ b/compiler/rustc_trait_selection/src/solve/assembly/structural_traits.rs @@ -28,12 +28,12 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_auto_trait<'tcx>( | ty::Char => Ok(vec![]), // Treat `str` like it's defined as `struct str([u8]);` - ty::Str => Ok(vec![tcx.mk_slice(tcx.types.u8)]), + ty::Str => Ok(vec![Ty::new_slice(tcx, tcx.types.u8)]), ty::Dynamic(..) | ty::Param(..) | ty::Foreign(..) - | ty::Alias(ty::Projection | ty::Inherent, ..) + | ty::Alias(ty::Projection | ty::Inherent | ty::Weak, ..) | ty::Placeholder(..) | ty::Bound(..) | ty::Infer(_) => { @@ -96,7 +96,7 @@ pub(in crate::solve) fn replace_erased_lifetimes_with_bound_vars<'tcx>( let br = ty::BoundRegion { var: ty::BoundVar::from_u32(counter), kind: ty::BrAnon(None) }; counter += 1; - tcx.mk_re_late_bound(current_depth, br) + ty::Region::new_late_bound(tcx, current_depth, br) } // All free regions should be erased here. r => bug!("unexpected region: {r:?}"), @@ -148,11 +148,7 @@ pub(in crate::solve) fn instantiate_constituent_tys_for_sized_trait<'tcx>( ty::Adt(def, substs) => { let sized_crit = def.sized_constraint(ecx.tcx()); - Ok(sized_crit - .0 - .iter() - .map(|ty| sized_crit.rebind(*ty).subst(ecx.tcx(), substs)) - .collect()) + Ok(sized_crit.subst_iter_copied(ecx.tcx(), substs).collect()) } } } @@ -237,7 +233,7 @@ pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( { Ok(Some( sig.subst(tcx, substs) - .map_bound(|sig| (tcx.mk_tup(sig.inputs()), sig.output())), + .map_bound(|sig| (Ty::new_tup(tcx, sig.inputs()), sig.output())), )) } else { Err(NoSolution) @@ -246,7 +242,7 @@ pub(in crate::solve) fn extract_tupled_inputs_and_output_from_callable<'tcx>( // 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())))) + Ok(Some(sig.map_bound(|sig| (Ty::new_tup(tcx, sig.inputs()), sig.output())))) } else { Err(NoSolution) } @@ -347,7 +343,7 @@ pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( param_env: ty::ParamEnv<'tcx>, trait_ref: ty::TraitRef<'tcx>, object_bound: &'tcx ty::List>, -) -> Vec> { +) -> Vec> { let tcx = ecx.tcx(); let mut requirements = vec![]; requirements.extend( @@ -357,7 +353,7 @@ pub(in crate::solve) fn predicates_for_object_candidate<'tcx>( // FIXME(associated_const_equality): Also add associated consts to // the requirements here. if item.kind == ty::AssocKind::Type { - requirements.extend(tcx.item_bounds(item.def_id).subst(tcx, trait_ref.substs)); + requirements.extend(tcx.item_bounds(item.def_id).subst_iter(tcx, trait_ref.substs)); } } -- cgit v1.2.3