From 94a0819fe3a0d679c3042a77bfe6a2afc505daea Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:11:28 +0200 Subject: Adding upstream version 1.66.0+dfsg1. Signed-off-by: Daniel Baumann --- .../src/impl_wf_check/min_specialization.rs | 439 --------------------- 1 file changed, 439 deletions(-) delete mode 100644 compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs (limited to 'compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs') diff --git a/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs b/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs deleted file mode 100644 index 74abb71a1..000000000 --- a/compiler/rustc_typeck/src/impl_wf_check/min_specialization.rs +++ /dev/null @@ -1,439 +0,0 @@ -//! # Minimal Specialization -//! -//! This module contains the checks for sound specialization used when the -//! `min_specialization` feature is enabled. This requires that the impl is -//! *always applicable*. -//! -//! If `impl1` specializes `impl2` then `impl1` is always applicable if we know -//! that all the bounds of `impl2` are satisfied, and all of the bounds of -//! `impl1` are satisfied for some choice of lifetimes then we know that -//! `impl1` applies for any choice of lifetimes. -//! -//! ## Basic approach -//! -//! To enforce this requirement on specializations we take the following -//! approach: -//! -//! 1. Match up the substs for `impl2` so that the implemented trait and -//! self-type match those for `impl1`. -//! 2. Check for any direct use of `'static` in the substs of `impl2`. -//! 3. Check that all of the generic parameters of `impl1` occur at most once -//! in the *unconstrained* substs for `impl2`. A parameter is constrained if -//! its value is completely determined by an associated type projection -//! predicate. -//! 4. Check that all predicates on `impl1` either exist on `impl2` (after -//! matching substs), or are well-formed predicates for the trait's type -//! arguments. -//! -//! ## Example -//! -//! Suppose we have the following always applicable impl: -//! -//! ```ignore (illustrative) -//! impl SpecExtend for std::vec::IntoIter { /* specialized impl */ } -//! impl> SpecExtend for I { /* default impl */ } -//! ``` -//! -//! We get that the subst for `impl2` are `[T, std::vec::IntoIter]`. `T` is -//! constrained to be `::Item`, so we check only -//! `std::vec::IntoIter` for repeated parameters, which it doesn't have. The -//! predicates of `impl1` are only `T: Sized`, which is also a predicate of -//! `impl2`. So this specialization is sound. -//! -//! ## Extensions -//! -//! Unfortunately not all specializations in the standard library are allowed -//! by this. So there are two extensions to these rules that allow specializing -//! on some traits: that is, using them as bounds on the specializing impl, -//! even when they don't occur in the base impl. -//! -//! ### rustc_specialization_trait -//! -//! If a trait is always applicable, then it's sound to specialize on it. We -//! check trait is always applicable in the same way as impls, except that step -//! 4 is now "all predicates on `impl1` are always applicable". We require that -//! `specialization` or `min_specialization` is enabled to implement these -//! traits. -//! -//! ### rustc_unsafe_specialization_marker -//! -//! There are also some specialization on traits with no methods, including the -//! stable `FusedIterator` trait. We allow marking marker traits with an -//! unstable attribute that means we ignore them in point 3 of the checks -//! above. This is unsound, in the sense that the specialized impl may be used -//! when it doesn't apply, but we allow it in the short term since it can't -//! cause use after frees with purely safe code in the same way as specializing -//! on traits with methods can. - -use crate::check::regionck::OutlivesEnvironmentExt; -use crate::check::wfcheck::impl_implied_bounds; -use crate::constrained_generic_params as cgp; -use crate::errors::SubstsOnOverriddenImpl; - -use rustc_data_structures::fx::FxHashSet; -use rustc_hir::def_id::{DefId, LocalDefId}; -use rustc_infer::infer::outlives::env::OutlivesEnvironment; -use rustc_infer::infer::{InferCtxt, TyCtxtInferExt}; -use rustc_infer::traits::specialization_graph::Node; -use rustc_middle::ty::subst::{GenericArg, InternalSubsts, SubstsRef}; -use rustc_middle::ty::trait_def::TraitSpecializationKind; -use rustc_middle::ty::{self, TyCtxt, TypeVisitable}; -use rustc_span::Span; -use rustc_trait_selection::traits::{self, translate_substs, wf}; - -pub(super) fn check_min_specialization(tcx: TyCtxt<'_>, impl_def_id: LocalDefId) { - if let Some(node) = parent_specialization_node(tcx, impl_def_id) { - tcx.infer_ctxt().enter(|infcx| { - check_always_applicable(&infcx, impl_def_id, node); - }); - } -} - -fn parent_specialization_node(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId) -> Option { - let trait_ref = tcx.impl_trait_ref(impl1_def_id)?; - let trait_def = tcx.trait_def(trait_ref.def_id); - - let impl2_node = trait_def.ancestors(tcx, impl1_def_id.to_def_id()).ok()?.nth(1)?; - - let always_applicable_trait = - matches!(trait_def.specialization_kind, TraitSpecializationKind::AlwaysApplicable); - if impl2_node.is_from_trait() && !always_applicable_trait { - // Implementing a normal trait isn't a specialization. - return None; - } - Some(impl2_node) -} - -/// Check that `impl1` is a sound specialization -fn check_always_applicable(infcx: &InferCtxt<'_, '_>, impl1_def_id: LocalDefId, impl2_node: Node) { - if let Some((impl1_substs, impl2_substs)) = get_impl_substs(infcx, impl1_def_id, impl2_node) { - let impl2_def_id = impl2_node.def_id(); - debug!( - "check_always_applicable(\nimpl1_def_id={:?},\nimpl2_def_id={:?},\nimpl2_substs={:?}\n)", - impl1_def_id, impl2_def_id, impl2_substs - ); - - let tcx = infcx.tcx; - - let parent_substs = if impl2_node.is_from_trait() { - impl2_substs.to_vec() - } else { - unconstrained_parent_impl_substs(tcx, impl2_def_id, impl2_substs) - }; - - let span = tcx.def_span(impl1_def_id); - check_static_lifetimes(tcx, &parent_substs, span); - check_duplicate_params(tcx, impl1_substs, &parent_substs, span); - check_predicates(infcx, impl1_def_id, impl1_substs, impl2_node, impl2_substs, span); - } -} - -/// Given a specializing impl `impl1`, and the base impl `impl2`, returns two -/// substitutions `(S1, S2)` that equate their trait references. The returned -/// types are expressed in terms of the generics of `impl1`. -/// -/// Example -/// -/// impl Foo for B { /* impl2 */ } -/// impl Foo> for C { /* impl1 */ } -/// -/// Would return `S1 = [C]` and `S2 = [Vec, C]`. -fn get_impl_substs<'tcx>( - infcx: &InferCtxt<'_, 'tcx>, - impl1_def_id: LocalDefId, - impl2_node: Node, -) -> Option<(SubstsRef<'tcx>, SubstsRef<'tcx>)> { - let tcx = infcx.tcx; - let param_env = tcx.param_env(impl1_def_id); - - let impl1_substs = InternalSubsts::identity_for_item(tcx, impl1_def_id.to_def_id()); - let impl2_substs = - translate_substs(infcx, param_env, impl1_def_id.to_def_id(), impl1_substs, impl2_node); - - let mut outlives_env = OutlivesEnvironment::new(param_env); - let implied_bounds = - impl_implied_bounds(infcx.tcx, param_env, impl1_def_id, tcx.def_span(impl1_def_id)); - outlives_env.add_implied_bounds( - infcx, - implied_bounds, - tcx.hir().local_def_id_to_hir_id(impl1_def_id), - ); - infcx.check_region_obligations_and_report_errors(impl1_def_id, &outlives_env); - let Ok(impl2_substs) = infcx.fully_resolve(impl2_substs) else { - let span = tcx.def_span(impl1_def_id); - tcx.sess.emit_err(SubstsOnOverriddenImpl { span }); - return None; - }; - Some((impl1_substs, impl2_substs)) -} - -/// Returns a list of all of the unconstrained subst of the given impl. -/// -/// For example given the impl: -/// -/// impl<'a, T, I> ... where &'a I: IntoIterator -/// -/// This would return the substs corresponding to `['a, I]`, because knowing -/// `'a` and `I` determines the value of `T`. -fn unconstrained_parent_impl_substs<'tcx>( - tcx: TyCtxt<'tcx>, - impl_def_id: DefId, - impl_substs: SubstsRef<'tcx>, -) -> Vec> { - let impl_generic_predicates = tcx.predicates_of(impl_def_id); - let mut unconstrained_parameters = FxHashSet::default(); - let mut constrained_params = FxHashSet::default(); - let impl_trait_ref = tcx.impl_trait_ref(impl_def_id); - - // Unfortunately the functions in `constrained_generic_parameters` don't do - // what we want here. We want only a list of constrained parameters while - // the functions in `cgp` add the constrained parameters to a list of - // unconstrained parameters. - for (predicate, _) in impl_generic_predicates.predicates.iter() { - if let ty::PredicateKind::Projection(proj) = predicate.kind().skip_binder() { - let projection_ty = proj.projection_ty; - let projected_ty = proj.term; - - let unbound_trait_ref = projection_ty.trait_ref(tcx); - if Some(unbound_trait_ref) == impl_trait_ref { - continue; - } - - unconstrained_parameters.extend(cgp::parameters_for(&projection_ty, true)); - - for param in cgp::parameters_for(&projected_ty, false) { - if !unconstrained_parameters.contains(¶m) { - constrained_params.insert(param.0); - } - } - - unconstrained_parameters.extend(cgp::parameters_for(&projected_ty, true)); - } - } - - impl_substs - .iter() - .enumerate() - .filter(|&(idx, _)| !constrained_params.contains(&(idx as u32))) - .map(|(_, arg)| arg) - .collect() -} - -/// Check that parameters of the derived impl don't occur more than once in the -/// equated substs of the base impl. -/// -/// For example forbid the following: -/// -/// impl Tr for A { } -/// impl Tr for (B, B) { } -/// -/// Note that only consider the unconstrained parameters of the base impl: -/// -/// impl> Tr for I { } -/// impl Tr for Vec { } -/// -/// The substs for the parent impl here are `[T, Vec]`, which repeats `T`, -/// but `S` is constrained in the parent impl, so `parent_substs` is only -/// `[Vec]`. This means we allow this impl. -fn check_duplicate_params<'tcx>( - tcx: TyCtxt<'tcx>, - impl1_substs: SubstsRef<'tcx>, - parent_substs: &Vec>, - span: Span, -) { - let mut base_params = cgp::parameters_for(parent_substs, true); - base_params.sort_by_key(|param| param.0); - if let (_, [duplicate, ..]) = base_params.partition_dedup() { - let param = impl1_substs[duplicate.0 as usize]; - tcx.sess - .struct_span_err(span, &format!("specializing impl repeats parameter `{}`", param)) - .emit(); - } -} - -/// Check that `'static` lifetimes are not introduced by the specializing impl. -/// -/// For example forbid the following: -/// -/// impl Tr for A { } -/// impl Tr for &'static i32 { } -fn check_static_lifetimes<'tcx>( - tcx: TyCtxt<'tcx>, - parent_substs: &Vec>, - span: Span, -) { - if tcx.any_free_region_meets(parent_substs, |r| r.is_static()) { - tcx.sess.struct_span_err(span, "cannot specialize on `'static` lifetime").emit(); - } -} - -/// Check whether predicates on the specializing impl (`impl1`) are allowed. -/// -/// Each predicate `P` must be: -/// -/// * global (not reference any parameters) -/// * `T: Tr` predicate where `Tr` is an always-applicable trait -/// * on the base `impl impl2` -/// * Currently this check is done using syntactic equality, which is -/// conservative but generally sufficient. -/// * a well-formed predicate of a type argument of the trait being implemented, -/// including the `Self`-type. -fn check_predicates<'tcx>( - infcx: &InferCtxt<'_, 'tcx>, - impl1_def_id: LocalDefId, - impl1_substs: SubstsRef<'tcx>, - impl2_node: Node, - impl2_substs: SubstsRef<'tcx>, - span: Span, -) { - let tcx = infcx.tcx; - let instantiated = tcx.predicates_of(impl1_def_id).instantiate(tcx, impl1_substs); - let impl1_predicates: Vec<_> = traits::elaborate_predicates_with_span( - tcx, - std::iter::zip( - instantiated.predicates, - // Don't drop predicates (unsound!) because `spans` is too short - instantiated.spans.into_iter().chain(std::iter::repeat(span)), - ), - ) - .map(|obligation| (obligation.predicate, obligation.cause.span)) - .collect(); - - let mut impl2_predicates = if impl2_node.is_from_trait() { - // Always applicable traits have to be always applicable without any - // assumptions. - Vec::new() - } else { - traits::elaborate_predicates( - tcx, - tcx.predicates_of(impl2_node.def_id()) - .instantiate(tcx, impl2_substs) - .predicates - .into_iter(), - ) - .map(|obligation| obligation.predicate) - .collect() - }; - debug!( - "check_always_applicable(\nimpl1_predicates={:?},\nimpl2_predicates={:?}\n)", - impl1_predicates, impl2_predicates, - ); - - // Since impls of always applicable traits don't get to assume anything, we - // can also assume their supertraits apply. - // - // For example, we allow: - // - // #[rustc_specialization_trait] - // trait AlwaysApplicable: Debug { } - // - // impl Tr for T { } - // impl Tr for T { } - // - // Specializing on `AlwaysApplicable` allows also specializing on `Debug` - // which is sound because we forbid impls like the following - // - // impl AlwaysApplicable for D { } - let always_applicable_traits = impl1_predicates.iter().copied().filter(|&(predicate, _)| { - matches!( - trait_predicate_kind(tcx, predicate), - Some(TraitSpecializationKind::AlwaysApplicable) - ) - }); - - // Include the well-formed predicates of the type parameters of the impl. - for arg in tcx.impl_trait_ref(impl1_def_id).unwrap().substs { - if let Some(obligations) = wf::obligations( - infcx, - tcx.param_env(impl1_def_id), - tcx.hir().local_def_id_to_hir_id(impl1_def_id), - 0, - arg, - span, - ) { - impl2_predicates.extend( - traits::elaborate_obligations(tcx, obligations) - .map(|obligation| obligation.predicate), - ) - } - } - impl2_predicates.extend( - traits::elaborate_predicates_with_span(tcx, always_applicable_traits) - .map(|obligation| obligation.predicate), - ); - - for (predicate, span) in impl1_predicates { - if !impl2_predicates.contains(&predicate) { - check_specialization_on(tcx, predicate, span) - } - } -} - -fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, predicate: ty::Predicate<'tcx>, span: Span) { - debug!("can_specialize_on(predicate = {:?})", predicate); - match predicate.kind().skip_binder() { - // Global predicates are either always true or always false, so we - // are fine to specialize on. - _ if predicate.is_global() => (), - // We allow specializing on explicitly marked traits with no associated - // items. - ty::PredicateKind::Trait(ty::TraitPredicate { - trait_ref, - constness: ty::BoundConstness::NotConst, - polarity: _, - }) => { - if !matches!( - trait_predicate_kind(tcx, predicate), - Some(TraitSpecializationKind::Marker) - ) { - tcx.sess - .struct_span_err( - span, - &format!( - "cannot specialize on trait `{}`", - tcx.def_path_str(trait_ref.def_id), - ), - ) - .emit(); - } - } - ty::PredicateKind::Projection(ty::ProjectionPredicate { projection_ty, term }) => { - tcx.sess - .struct_span_err( - span, - &format!("cannot specialize on associated type `{projection_ty} == {term}`",), - ) - .emit(); - } - _ => { - tcx.sess - .struct_span_err(span, &format!("cannot specialize on predicate `{}`", predicate)) - .emit(); - } - } -} - -fn trait_predicate_kind<'tcx>( - tcx: TyCtxt<'tcx>, - predicate: ty::Predicate<'tcx>, -) -> Option { - match predicate.kind().skip_binder() { - ty::PredicateKind::Trait(ty::TraitPredicate { - trait_ref, - constness: ty::BoundConstness::NotConst, - polarity: _, - }) => Some(tcx.trait_def(trait_ref.def_id).specialization_kind), - ty::PredicateKind::Trait(_) - | ty::PredicateKind::RegionOutlives(_) - | ty::PredicateKind::TypeOutlives(_) - | ty::PredicateKind::Projection(_) - | ty::PredicateKind::WellFormed(_) - | ty::PredicateKind::Subtype(_) - | ty::PredicateKind::Coerce(_) - | ty::PredicateKind::ObjectSafe(_) - | ty::PredicateKind::ClosureKind(..) - | ty::PredicateKind::ConstEvaluatable(..) - | ty::PredicateKind::ConstEquate(..) - | ty::PredicateKind::TypeWellFormedFromEnv(..) => None, - } -} -- cgit v1.2.3