diff options
Diffstat (limited to '')
| -rw-r--r-- | compiler/rustc_trait_selection/src/traits/project.rs | 301 |
1 files changed, 276 insertions, 25 deletions
diff --git a/compiler/rustc_trait_selection/src/traits/project.rs b/compiler/rustc_trait_selection/src/traits/project.rs index c4e80e1ba..e4284b9d3 100644 --- a/compiler/rustc_trait_selection/src/traits/project.rs +++ b/compiler/rustc_trait_selection/src/traits/project.rs @@ -18,7 +18,7 @@ use super::{Normalized, NormalizedTy, ProjectionCacheEntry, ProjectionCacheKey}; use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; use crate::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; -use crate::traits::error_reporting::InferCtxtExt as _; +use crate::traits::error_reporting::TypeErrCtxtExt as _; use crate::traits::query::evaluate_obligation::InferCtxtExt as _; use crate::traits::select::ProjectionMatchesProjection; use rustc_data_structures::sso::SsoHashSet; @@ -30,8 +30,8 @@ use rustc_hir::lang_items::LangItem; use rustc_infer::infer::resolve::OpportunisticRegionResolver; use rustc_middle::traits::select::OverflowError; use rustc_middle::ty::fold::{TypeFoldable, TypeFolder, TypeSuperFoldable}; -use rustc_middle::ty::subst::Subst; use rustc_middle::ty::visit::{MaxUniverse, TypeVisitable}; +use rustc_middle::ty::DefIdTree; use rustc_middle::ty::{self, Term, ToPredicate, Ty, TyCtxt}; use rustc_span::symbol::sym; @@ -62,7 +62,8 @@ enum ProjectionCandidate<'tcx> { /// From a where-clause in the env or object type ParamEnv(ty::PolyProjectionPredicate<'tcx>), - /// From the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C + /// From the definition of `Trait` when you have something like + /// `<<A as Trait>::B as Trait2>::C`. TraitDef(ty::PolyProjectionPredicate<'tcx>), /// Bounds specified on an object type @@ -70,6 +71,16 @@ enum ProjectionCandidate<'tcx> { /// From an "impl" (or a "pseudo-impl" returned by select) Select(Selection<'tcx>), + + ImplTraitInTrait(ImplTraitInTraitCandidate<'tcx>), +} + +#[derive(PartialEq, Eq, Debug)] +enum ImplTraitInTraitCandidate<'tcx> { + // The `impl Trait` from a trait function's default body + Trait, + // A concrete type provided from a trait's `impl Trait` from an impl + Impl(ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>), } enum ProjectionCandidateSet<'tcx> { @@ -231,7 +242,7 @@ pub(super) fn poly_project_and_unify_type<'cx, 'tcx>( /// If successful, this may result in additional obligations. /// /// See [poly_project_and_unify_type] for an explanation of the return value. -#[tracing::instrument(level = "debug", skip(selcx))] +#[instrument(level = "debug", skip(selcx))] fn project_and_unify_type<'cx, 'tcx>( selcx: &mut SelectionContext<'cx, 'tcx>, obligation: &ProjectionObligation<'tcx>, @@ -253,7 +264,7 @@ fn project_and_unify_type<'cx, 'tcx>( }; debug!(?normalized, ?obligations, "project_and_unify_type result"); let actual = obligation.predicate.term; - // For an example where this is neccessary see src/test/ui/impl-trait/nested-return-type2.rs + // For an example where this is necessary see src/test/ui/impl-trait/nested-return-type2.rs // This allows users to omit re-mentioning all bounds on an associated type and just use an // `impl Trait` for the assoc type to add more bounds. let InferOk { value: actual, obligations: new } = @@ -511,7 +522,7 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { self.param_env, ty, ); - self.selcx.infcx().report_overflow_error(&obligation, true); + self.selcx.infcx().err_ctxt().report_overflow_error(&obligation, true); } let substs = substs.fold_with(self); @@ -552,7 +563,7 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { ) .ok() .flatten() - .unwrap_or_else(|| ty::Term::Ty(ty.super_fold_with(self))) + .unwrap_or_else(|| ty.super_fold_with(self).into()) }; debug!( ?self.depth, @@ -620,19 +631,33 @@ impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { #[instrument(skip(self), level = "debug")] fn fold_const(&mut self, constant: ty::Const<'tcx>) -> ty::Const<'tcx> { - if self.selcx.tcx().lazy_normalization() || !self.eager_inference_replacement { + let tcx = self.selcx.tcx(); + if tcx.lazy_normalization() { constant } else { let constant = constant.super_fold_with(self); - debug!(?constant); - debug!("self.param_env: {:?}", self.param_env); - constant.eval(self.selcx.tcx(), self.param_env) + debug!(?constant, ?self.param_env); + with_replaced_escaping_bound_vars( + self.selcx.infcx(), + &mut self.universes, + constant, + |constant| constant.eval(tcx, self.param_env), + ) + } + } + + #[inline] + fn fold_predicate(&mut self, p: ty::Predicate<'tcx>) -> ty::Predicate<'tcx> { + if p.allow_normalization() && needs_normalization(&p, self.param_env.reveal()) { + p.super_fold_with(self) + } else { + p } } } pub struct BoundVarReplacer<'me, 'tcx> { - infcx: &'me InferCtxt<'me, 'tcx>, + infcx: &'me InferCtxt<'tcx>, // These three maps track the bound variable that were replaced by placeholders. It might be // nice to remove these since we already have the `kind` in the placeholder; we really just need // the `var` (but we *could* bring that into scope if we were to track them as we pass them). @@ -647,11 +672,46 @@ pub struct BoundVarReplacer<'me, 'tcx> { universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, } +/// Executes `f` on `value` after replacing all escaping bound variables with placeholders +/// and then replaces these placeholders with the original bound variables in the result. +/// +/// In most places, bound variables should be replaced right when entering a binder, making +/// this function unnecessary. However, normalization currently does not do that, so we have +/// to do this lazily. +/// +/// You should not add any additional uses of this function, at least not without first +/// discussing it with t-types. +/// +/// FIXME(@lcnr): We may even consider experimenting with eagerly replacing bound vars during +/// normalization as well, at which point this function will be unnecessary and can be removed. +pub fn with_replaced_escaping_bound_vars<'a, 'tcx, T: TypeFoldable<'tcx>, R: TypeFoldable<'tcx>>( + infcx: &'a InferCtxt<'tcx>, + universe_indices: &'a mut Vec<Option<ty::UniverseIndex>>, + value: T, + f: impl FnOnce(T) -> R, +) -> R { + if value.has_escaping_bound_vars() { + let (value, mapped_regions, mapped_types, mapped_consts) = + BoundVarReplacer::replace_bound_vars(infcx, universe_indices, value); + let result = f(value); + PlaceholderReplacer::replace_placeholders( + infcx, + mapped_regions, + mapped_types, + mapped_consts, + universe_indices, + result, + ) + } else { + f(value) + } +} + impl<'me, 'tcx> BoundVarReplacer<'me, 'tcx> { /// Returns `Some` if we *were* able to replace bound vars. If there are any bound vars that /// use a binding level above `universe_indices.len()`, we fail. pub fn replace_bound_vars<T: TypeFoldable<'tcx>>( - infcx: &'me InferCtxt<'me, 'tcx>, + infcx: &'me InferCtxt<'tcx>, universe_indices: &'me mut Vec<Option<ty::UniverseIndex>>, value: T, ) -> ( @@ -771,7 +831,7 @@ impl<'tcx> TypeFolder<'tcx> for BoundVarReplacer<'_, 'tcx> { // The inverse of `BoundVarReplacer`: replaces placeholders with the bound vars from which they came. pub struct PlaceholderReplacer<'me, 'tcx> { - infcx: &'me InferCtxt<'me, 'tcx>, + infcx: &'me InferCtxt<'tcx>, mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, @@ -781,7 +841,7 @@ pub struct PlaceholderReplacer<'me, 'tcx> { impl<'me, 'tcx> PlaceholderReplacer<'me, 'tcx> { pub fn replace_placeholders<T: TypeFoldable<'tcx>>( - infcx: &'me InferCtxt<'me, 'tcx>, + infcx: &'me InferCtxt<'tcx>, mapped_regions: BTreeMap<ty::PlaceholderRegion, ty::BoundRegion>, mapped_types: BTreeMap<ty::PlaceholderType, ty::BoundTy>, mapped_consts: BTreeMap<ty::PlaceholderConst<'tcx>, ty::BoundVar>, @@ -1182,7 +1242,7 @@ impl<'tcx> Progress<'tcx> { /// /// IMPORTANT: /// - `obligation` must be fully normalized -#[tracing::instrument(level = "info", skip(selcx))] +#[instrument(level = "info", skip(selcx))] fn project<'cx, 'tcx>( selcx: &mut SelectionContext<'cx, 'tcx>, obligation: &ProjectionTyObligation<'tcx>, @@ -1201,6 +1261,8 @@ fn project<'cx, 'tcx>( let mut candidates = ProjectionCandidateSet::None; + assemble_candidate_for_impl_trait_in_trait(selcx, obligation, &mut candidates); + // Make sure that the following procedures are kept in order. ParamEnv // needs to be first because it has highest priority, and Select checks // the return value of push_candidate which assumes it's ran at last. @@ -1239,6 +1301,63 @@ fn project<'cx, 'tcx>( } } +/// If the predicate's item is an `ImplTraitPlaceholder`, we do a select on the +/// corresponding trait ref. If this yields an `impl`, then we're able to project +/// to a concrete type, since we have an `impl`'s method to provide the RPITIT. +fn assemble_candidate_for_impl_trait_in_trait<'cx, 'tcx>( + selcx: &mut SelectionContext<'cx, 'tcx>, + obligation: &ProjectionTyObligation<'tcx>, + candidate_set: &mut ProjectionCandidateSet<'tcx>, +) { + let tcx = selcx.tcx(); + if tcx.def_kind(obligation.predicate.item_def_id) == DefKind::ImplTraitPlaceholder { + let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.item_def_id); + // If we are trying to project an RPITIT with trait's default `Self` parameter, + // then we must be within a default trait body. + if obligation.predicate.self_ty() + == ty::InternalSubsts::identity_for_item(tcx, obligation.predicate.item_def_id) + .type_at(0) + && tcx.associated_item(trait_fn_def_id).defaultness(tcx).has_value() + { + candidate_set.push_candidate(ProjectionCandidate::ImplTraitInTrait( + ImplTraitInTraitCandidate::Trait, + )); + return; + } + + let trait_def_id = tcx.parent(trait_fn_def_id); + let trait_substs = + obligation.predicate.substs.truncate_to(tcx, tcx.generics_of(trait_def_id)); + // FIXME(named-returns): Binders + let trait_predicate = + ty::Binder::dummy(ty::TraitRef { def_id: trait_def_id, substs: trait_substs }) + .to_poly_trait_predicate(); + + let _ = + selcx.infcx().commit_if_ok(|_| match selcx.select(&obligation.with(trait_predicate)) { + Ok(Some(super::ImplSource::UserDefined(data))) => { + candidate_set.push_candidate(ProjectionCandidate::ImplTraitInTrait( + ImplTraitInTraitCandidate::Impl(data), + )); + Ok(()) + } + Ok(None) => { + candidate_set.mark_ambiguous(); + return Err(()); + } + Ok(Some(_)) => { + // Don't know enough about the impl to provide a useful signature + return Err(()); + } + Err(e) => { + debug!(error = ?e, "selection error"); + candidate_set.mark_error(e); + return Err(()); + } + }); + } +} + /// The first thing we have to do is scan through the parameter /// environment to see whether there are any projection predicates /// there that can answer this question. @@ -1257,7 +1376,7 @@ fn assemble_candidates_from_param_env<'cx, 'tcx>( ); } -/// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find +/// In the case of a nested projection like `<<A as Foo>::FooT as Bar>::BarT`, we may find /// that the definition of `Foo` has some clues: /// /// ```ignore (illustrative) @@ -1344,7 +1463,7 @@ fn assemble_candidates_from_object_ty<'cx, 'tcx>( ); } -#[tracing::instrument( +#[instrument( level = "debug", skip(selcx, candidate_set, ctor, env_predicates, potentially_unnormalized_candidates) )] @@ -1378,7 +1497,7 @@ fn assemble_candidates_from_predicates<'cx, 'tcx>( candidate_set.push_candidate(ctor(data)); if potentially_unnormalized_candidates - && !obligation.predicate.has_infer_types_or_consts() + && !obligation.predicate.has_non_region_infer() { // HACK: Pick the first trait def candidate for a fully // inferred predicate. This is to allow duplicates that @@ -1395,12 +1514,17 @@ fn assemble_candidates_from_predicates<'cx, 'tcx>( } } -#[tracing::instrument(level = "debug", skip(selcx, obligation, candidate_set))] +#[instrument(level = "debug", skip(selcx, obligation, candidate_set))] fn assemble_candidates_from_impls<'cx, 'tcx>( selcx: &mut SelectionContext<'cx, 'tcx>, obligation: &ProjectionTyObligation<'tcx>, candidate_set: &mut ProjectionCandidateSet<'tcx>, ) { + // Can't assemble candidate from impl for RPITIT + if selcx.tcx().def_kind(obligation.predicate.item_def_id) == DefKind::ImplTraitPlaceholder { + return; + } + // If we are resolving `<T as TraitRef<...>>::Item == Type`, // start out by selecting the predicate `T as TraitRef<...>`: let poly_trait_ref = ty::Binder::dummy(obligation.predicate.trait_ref(selcx.tcx())); @@ -1676,6 +1800,18 @@ fn confirm_candidate<'cx, 'tcx>( ProjectionCandidate::Select(impl_source) => { confirm_select_candidate(selcx, obligation, impl_source) } + ProjectionCandidate::ImplTraitInTrait(ImplTraitInTraitCandidate::Impl(data)) => { + confirm_impl_trait_in_trait_candidate(selcx, obligation, data) + } + // If we're projecting an RPITIT for a default trait body, that's just + // the same def-id, but as an opaque type (with regular RPIT semantics). + ProjectionCandidate::ImplTraitInTrait(ImplTraitInTraitCandidate::Trait) => Progress { + term: selcx + .tcx() + .mk_opaque(obligation.predicate.item_def_id, obligation.predicate.substs) + .into(), + obligations: vec![], + }, }; // When checking for cycle during evaluation, we compare predicates with @@ -2021,15 +2157,15 @@ fn confirm_impl_candidate<'cx, 'tcx>( let identity_substs = crate::traits::InternalSubsts::identity_for_item(tcx, assoc_ty.item.def_id); let did = ty::WithOptConstParam::unknown(assoc_ty.item.def_id); - let kind = ty::ConstKind::Unevaluated(ty::Unevaluated::new(did, identity_substs)); + let kind = ty::ConstKind::Unevaluated(ty::UnevaluatedConst::new(did, identity_substs)); ty.map_bound(|ty| tcx.mk_const(ty::ConstS { ty, kind }).into()) } else { ty.map_bound(|ty| ty.into()) }; - if substs.len() != tcx.generics_of(assoc_ty.item.def_id).count() { + if !check_substs_compatible(tcx, &assoc_ty.item, substs) { let err = tcx.ty_error_with_message( obligation.cause.span, - "impl item and trait item have different parameter counts", + "impl item and trait item have different parameters", ); Progress { term: err.into(), obligations: nested } } else { @@ -2038,10 +2174,125 @@ fn confirm_impl_candidate<'cx, 'tcx>( } } +// Verify that the trait item and its implementation have compatible substs lists +fn check_substs_compatible<'tcx>( + tcx: TyCtxt<'tcx>, + assoc_ty: &ty::AssocItem, + substs: ty::SubstsRef<'tcx>, +) -> bool { + fn check_substs_compatible_inner<'tcx>( + tcx: TyCtxt<'tcx>, + generics: &'tcx ty::Generics, + args: &'tcx [ty::GenericArg<'tcx>], + ) -> bool { + if generics.count() != args.len() { + return false; + } + + let (parent_args, own_args) = args.split_at(generics.parent_count); + + if let Some(parent) = generics.parent + && let parent_generics = tcx.generics_of(parent) + && !check_substs_compatible_inner(tcx, parent_generics, parent_args) { + return false; + } + + for (param, arg) in std::iter::zip(&generics.params, own_args) { + match (¶m.kind, arg.unpack()) { + (ty::GenericParamDefKind::Type { .. }, ty::GenericArgKind::Type(_)) + | (ty::GenericParamDefKind::Lifetime, ty::GenericArgKind::Lifetime(_)) + | (ty::GenericParamDefKind::Const { .. }, ty::GenericArgKind::Const(_)) => {} + _ => return false, + } + } + + true + } + + check_substs_compatible_inner(tcx, tcx.generics_of(assoc_ty.def_id), substs.as_slice()) +} + +fn confirm_impl_trait_in_trait_candidate<'tcx>( + selcx: &mut SelectionContext<'_, 'tcx>, + obligation: &ProjectionTyObligation<'tcx>, + data: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>, +) -> Progress<'tcx> { + let tcx = selcx.tcx(); + let mut obligations = data.nested; + + let trait_fn_def_id = tcx.impl_trait_in_trait_parent(obligation.predicate.item_def_id); + let Ok(leaf_def) = assoc_def(selcx, data.impl_def_id, trait_fn_def_id) else { + return Progress { term: tcx.ty_error().into(), obligations }; + }; + if !leaf_def.item.defaultness(tcx).has_value() { + return Progress { term: tcx.ty_error().into(), obligations }; + } + + // Use the default `impl Trait` for the trait, e.g., for a default trait body + if leaf_def.item.container == ty::AssocItemContainer::TraitContainer { + return Progress { + term: tcx + .mk_opaque(obligation.predicate.item_def_id, obligation.predicate.substs) + .into(), + obligations, + }; + } + + let impl_fn_def_id = leaf_def.item.def_id; + // Rebase from {trait}::{fn}::{opaque} to {impl}::{fn}::{opaque}, + // since `data.substs` are the impl substs. + let impl_fn_substs = + obligation.predicate.substs.rebase_onto(tcx, tcx.parent(trait_fn_def_id), data.substs); + + let cause = ObligationCause::new( + obligation.cause.span, + obligation.cause.body_id, + super::ItemObligation(impl_fn_def_id), + ); + let predicates = normalize_with_depth_to( + selcx, + obligation.param_env, + cause.clone(), + obligation.recursion_depth + 1, + tcx.predicates_of(impl_fn_def_id).instantiate(tcx, impl_fn_substs), + &mut obligations, + ); + obligations.extend(std::iter::zip(predicates.predicates, predicates.spans).map( + |(pred, span)| { + Obligation::with_depth( + ObligationCause::new( + obligation.cause.span, + obligation.cause.body_id, + if span.is_dummy() { + super::ItemObligation(impl_fn_def_id) + } else { + super::BindingObligation(impl_fn_def_id, span) + }, + ), + obligation.recursion_depth + 1, + obligation.param_env, + pred, + ) + }, + )); + + let ty = super::normalize_to( + selcx, + obligation.param_env, + cause.clone(), + tcx.bound_trait_impl_trait_tys(impl_fn_def_id) + .map_bound(|tys| { + tys.map_or_else(|_| tcx.ty_error(), |tys| tys[&obligation.predicate.item_def_id]) + }) + .subst(tcx, impl_fn_substs), + &mut obligations, + ); + + Progress { term: ty.into(), obligations } +} + // Get obligations corresponding to the predicates from the where-clause of the // associated type itself. -// Note: `feature(generic_associated_types)` is required to write such -// predicates, even for non-generic associated types. fn assoc_ty_own_obligations<'cx, 'tcx>( selcx: &mut SelectionContext<'cx, 'tcx>, obligation: &ProjectionTyObligation<'tcx>, |