1 //! # Minimal Specialization
3 //! This module contains the checks for sound specialization used when the
4 //! `min_specialization` feature is enabled. This requires that the impl is
5 //! *always applicable*.
7 //! If `impl1` specializes `impl2` then `impl1` is always applicable if we know
8 //! that all the bounds of `impl2` are satisfied, and all of the bounds of
9 //! `impl1` are satisfied for some choice of lifetimes then we know that
10 //! `impl1` applies for any choice of lifetimes.
14 //! To enforce this requirement on specializations we take the following
17 //! 1. Match up the substs for `impl2` so that the implemented trait and
18 //! self-type match those for `impl1`.
19 //! 2. Check for any direct use of `'static` in the substs of `impl2`.
20 //! 3. Check that all of the generic parameters of `impl1` occur at most once
21 //! in the *unconstrained* substs for `impl2`. A parameter is constrained if
22 //! its value is completely determined by an associated type projection
24 //! 4. Check that all predicates on `impl1` either exist on `impl2` (after
25 //! matching substs), or are well-formed predicates for the trait's type
30 //! Suppose we have the following always applicable impl:
33 //! impl<T> SpecExtend<T> for std::vec::IntoIter<T> { /* specialized impl */ }
34 //! impl<T, I: Iterator<Item=T>> SpecExtend<T> for I { /* default impl */ }
37 //! We get that the subst for `impl2` are `[T, std::vec::IntoIter<T>]`. `T` is
38 //! constrained to be `<I as Iterator>::Item`, so we check only
39 //! `std::vec::IntoIter<T>` for repeated parameters, which it doesn't have. The
40 //! predicates of `impl1` are only `T: Sized`, which is also a predicate of
41 //! `impl2`. So this specialization is sound.
45 //! Unfortunately not all specializations in the standard library are allowed
46 //! by this. So there are two extensions to these rules that allow specializing
47 //! on some traits: that is, using them as bounds on the specializing impl,
48 //! even when they don't occur in the base impl.
50 //! ### rustc_specialization_trait
52 //! If a trait is always applicable, then it's sound to specialize on it. We
53 //! check trait is always applicable in the same way as impls, except that step
54 //! 4 is now "all predicates on `impl1` are always applicable". We require that
55 //! `specialization` or `min_specialization` is enabled to implement these
58 //! ### rustc_unsafe_specialization_marker
60 //! There are also some specialization on traits with no methods, including the
61 //! stable `FusedIterator` trait. We allow marking marker traits with an
62 //! unstable attribute that means we ignore them in point 3 of the checks
63 //! above. This is unsound, in the sense that the specialized impl may be used
64 //! when it doesn't apply, but we allow it in the short term since it can't
65 //! cause use after frees with purely safe code in the same way as specializing
66 //! on traits with methods can.
68 use crate::constrained_generic_params as cgp;
70 use rustc_data_structures::fx::FxHashSet;
72 use rustc_hir::def_id::{DefId, LocalDefId};
73 use rustc_infer::infer::outlives::env::OutlivesEnvironment;
74 use rustc_infer::infer::{InferCtxt, RegionckMode, TyCtxtInferExt};
75 use rustc_infer::traits::specialization_graph::Node;
76 use rustc_middle::middle::region::ScopeTree;
77 use rustc_middle::ty::subst::{GenericArg, InternalSubsts, SubstsRef};
78 use rustc_middle::ty::trait_def::TraitSpecializationKind;
79 use rustc_middle::ty::{self, InstantiatedPredicates, TyCtxt, TypeFoldable};
81 use rustc_trait_selection::traits::{self, translate_substs, wf};
83 pub(super) fn check_min_specialization(tcx: TyCtxt<'_>, impl_def_id: DefId, span: Span) {
84 if let Some(node) = parent_specialization_node(tcx, impl_def_id) {
85 tcx.infer_ctxt().enter(|infcx| {
86 check_always_applicable(&infcx, impl_def_id, node, span);
91 fn parent_specialization_node(tcx: TyCtxt<'_>, impl1_def_id: DefId) -> Option<Node> {
92 let trait_ref = tcx.impl_trait_ref(impl1_def_id)?;
93 let trait_def = tcx.trait_def(trait_ref.def_id);
95 let impl2_node = trait_def.ancestors(tcx, impl1_def_id).ok()?.nth(1)?;
97 let always_applicable_trait =
98 matches!(trait_def.specialization_kind, TraitSpecializationKind::AlwaysApplicable);
99 if impl2_node.is_from_trait() && !always_applicable_trait {
100 // Implementing a normal trait isn't a specialization.
106 /// Check that `impl1` is a sound specialization
107 fn check_always_applicable(
108 infcx: &InferCtxt<'_, '_>,
113 if let Some((impl1_substs, impl2_substs)) =
114 get_impl_substs(infcx, impl1_def_id, impl2_node, span)
116 let impl2_def_id = impl2_node.def_id();
118 "check_always_applicable(\nimpl1_def_id={:?},\nimpl2_def_id={:?},\nimpl2_substs={:?}\n)",
119 impl1_def_id, impl2_def_id, impl2_substs
124 let parent_substs = if impl2_node.is_from_trait() {
125 impl2_substs.to_vec()
127 unconstrained_parent_impl_substs(tcx, impl2_def_id, impl2_substs)
130 check_static_lifetimes(tcx, &parent_substs, span);
131 check_duplicate_params(tcx, impl1_substs, &parent_substs, span);
135 impl1_def_id.expect_local(),
144 /// Given a specializing impl `impl1`, and the base impl `impl2`, returns two
145 /// substitutions `(S1, S2)` that equate their trait references. The returned
146 /// types are expressed in terms of the generics of `impl1`.
150 /// impl<A, B> Foo<A> for B { /* impl2 */ }
151 /// impl<C> Foo<Vec<C>> for C { /* impl1 */ }
153 /// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`.
154 fn get_impl_substs<'tcx>(
155 infcx: &InferCtxt<'_, 'tcx>,
159 ) -> Option<(SubstsRef<'tcx>, SubstsRef<'tcx>)> {
161 let param_env = tcx.param_env(impl1_def_id);
163 let impl1_substs = InternalSubsts::identity_for_item(tcx, impl1_def_id);
164 let impl2_substs = translate_substs(infcx, param_env, impl1_def_id, impl1_substs, impl2_node);
166 // Conservatively use an empty `ParamEnv`.
167 let outlives_env = OutlivesEnvironment::new(ty::ParamEnv::empty());
168 infcx.resolve_regions_and_report_errors(
170 &ScopeTree::default(),
172 RegionckMode::default(),
174 let impl2_substs = match infcx.fully_resolve(&impl2_substs) {
177 tcx.sess.struct_span_err(span, "could not resolve substs on overridden impl").emit();
181 Some((impl1_substs, impl2_substs))
184 /// Returns a list of all of the unconstrained subst of the given impl.
186 /// For example given the impl:
188 /// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T>
190 /// This would return the substs corresponding to `['a, I]`, because knowing
191 /// `'a` and `I` determines the value of `T`.
192 fn unconstrained_parent_impl_substs<'tcx>(
195 impl_substs: SubstsRef<'tcx>,
196 ) -> Vec<GenericArg<'tcx>> {
197 let impl_generic_predicates = tcx.predicates_of(impl_def_id);
198 let mut unconstrained_parameters = FxHashSet::default();
199 let mut constrained_params = FxHashSet::default();
200 let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
202 // Unfortunately the functions in `constrained_generic_parameters` don't do
203 // what we want here. We want only a list of constrained parameters while
204 // the functions in `cgp` add the constrained parameters to a list of
205 // unconstrained parameters.
206 for (predicate, _) in impl_generic_predicates.predicates.iter() {
207 if let ty::PredicateKind::Projection(proj) = predicate.kind() {
208 let projection_ty = proj.skip_binder().projection_ty;
209 let projected_ty = proj.skip_binder().ty;
211 let unbound_trait_ref = projection_ty.trait_ref(tcx);
212 if Some(unbound_trait_ref) == impl_trait_ref {
216 unconstrained_parameters.extend(cgp::parameters_for(&projection_ty, true));
218 for param in cgp::parameters_for(&projected_ty, false) {
219 if !unconstrained_parameters.contains(¶m) {
220 constrained_params.insert(param.0);
224 unconstrained_parameters.extend(cgp::parameters_for(&projected_ty, true));
231 .filter(|&(idx, _)| !constrained_params.contains(&(idx as u32)))
232 .map(|(_, arg)| *arg)
236 /// Check that parameters of the derived impl don't occur more than once in the
237 /// equated substs of the base impl.
239 /// For example forbid the following:
241 /// impl<A> Tr for A { }
242 /// impl<B> Tr for (B, B) { }
244 /// Note that only consider the unconstrained parameters of the base impl:
246 /// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { }
247 /// impl<T> Tr<T> for Vec<T> { }
249 /// The substs for the parent impl here are `[T, Vec<T>]`, which repeats `T`,
250 /// but `S` is constrained in the parent impl, so `parent_substs` is only
251 /// `[Vec<T>]`. This means we allow this impl.
252 fn check_duplicate_params<'tcx>(
254 impl1_substs: SubstsRef<'tcx>,
255 parent_substs: &Vec<GenericArg<'tcx>>,
258 let mut base_params = cgp::parameters_for(parent_substs, true);
259 base_params.sort_by_key(|param| param.0);
260 if let (_, [duplicate, ..]) = base_params.partition_dedup() {
261 let param = impl1_substs[duplicate.0 as usize];
263 .struct_span_err(span, &format!("specializing impl repeats parameter `{}`", param))
268 /// Check that `'static` lifetimes are not introduced by the specializing impl.
270 /// For example forbid the following:
272 /// impl<A> Tr for A { }
273 /// impl Tr for &'static i32 { }
274 fn check_static_lifetimes<'tcx>(
276 parent_substs: &Vec<GenericArg<'tcx>>,
279 if tcx.any_free_region_meets(parent_substs, |r| *r == ty::ReStatic) {
280 tcx.sess.struct_span_err(span, "cannot specialize on `'static` lifetime").emit();
284 /// Check whether predicates on the specializing impl (`impl1`) are allowed.
286 /// Each predicate `P` must be:
288 /// * global (not reference any parameters)
289 /// * `T: Tr` predicate where `Tr` is an always-applicable trait
290 /// * on the base `impl impl2`
291 /// * Currently this check is done using syntactic equality, which is
292 /// conservative but generally sufficient.
293 /// * a well-formed predicate of a type argument of the trait being implemented,
294 /// including the `Self`-type.
295 fn check_predicates<'tcx>(
296 infcx: &InferCtxt<'_, 'tcx>,
297 impl1_def_id: LocalDefId,
298 impl1_substs: SubstsRef<'tcx>,
300 impl2_substs: SubstsRef<'tcx>,
304 let impl1_predicates = tcx.predicates_of(impl1_def_id).instantiate(tcx, impl1_substs);
305 let mut impl2_predicates = if impl2_node.is_from_trait() {
306 // Always applicable traits have to be always applicable without any
308 InstantiatedPredicates::empty()
310 tcx.predicates_of(impl2_node.def_id()).instantiate(tcx, impl2_substs)
313 "check_always_applicable(\nimpl1_predicates={:?},\nimpl2_predicates={:?}\n)",
314 impl1_predicates, impl2_predicates,
317 // Since impls of always applicable traits don't get to assume anything, we
318 // can also assume their supertraits apply.
320 // For example, we allow:
322 // #[rustc_specialization_trait]
323 // trait AlwaysApplicable: Debug { }
325 // impl<T> Tr for T { }
326 // impl<T: AlwaysApplicable> Tr for T { }
328 // Specializing on `AlwaysApplicable` allows also specializing on `Debug`
329 // which is sound because we forbid impls like the following
331 // impl<D: Debug> AlwaysApplicable for D { }
332 let always_applicable_traits = impl1_predicates
335 .filter(|predicate| {
337 trait_predicate_kind(tcx, predicate),
338 Some(TraitSpecializationKind::AlwaysApplicable)
343 // Include the well-formed predicates of the type parameters of the impl.
344 for ty in tcx.impl_trait_ref(impl1_def_id).unwrap().substs.types() {
345 if let Some(obligations) = wf::obligations(
347 tcx.param_env(impl1_def_id),
348 tcx.hir().as_local_hir_id(impl1_def_id),
354 .extend(obligations.into_iter().map(|obligation| obligation.predicate))
357 impl2_predicates.predicates.extend(
358 traits::elaborate_predicates(tcx, always_applicable_traits)
359 .map(|obligation| obligation.predicate),
362 for predicate in impl1_predicates.predicates {
363 if !impl2_predicates.predicates.contains(&predicate) {
364 check_specialization_on(tcx, &predicate, span)
369 fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, predicate: &ty::Predicate<'tcx>, span: Span) {
370 debug!("can_specialize_on(predicate = {:?})", predicate);
371 match predicate.kind() {
372 // Global predicates are either always true or always false, so we
373 // are fine to specialize on.
374 _ if predicate.is_global() => (),
375 // We allow specializing on explicitly marked traits with no associated
377 ty::PredicateKind::Trait(pred, hir::Constness::NotConst) => {
379 trait_predicate_kind(tcx, predicate),
380 Some(TraitSpecializationKind::Marker)
386 "cannot specialize on trait `{}`",
387 tcx.def_path_str(pred.def_id()),
395 .struct_span_err(span, &format!("cannot specialize on `{:?}`", predicate))
400 fn trait_predicate_kind<'tcx>(
402 predicate: &ty::Predicate<'tcx>,
403 ) -> Option<TraitSpecializationKind> {
404 match predicate.kind() {
405 ty::PredicateKind::Trait(pred, hir::Constness::NotConst) => {
406 Some(tcx.trait_def(pred.def_id()).specialization_kind)
408 ty::PredicateKind::Trait(_, hir::Constness::Const)
409 | ty::PredicateKind::RegionOutlives(_)
410 | ty::PredicateKind::TypeOutlives(_)
411 | ty::PredicateKind::Projection(_)
412 | ty::PredicateKind::WellFormed(_)
413 | ty::PredicateKind::Subtype(_)
414 | ty::PredicateKind::ObjectSafe(_)
415 | ty::PredicateKind::ClosureKind(..)
416 | ty::PredicateKind::ConstEvaluatable(..)
417 | ty::PredicateKind::ConstEquate(..) => None,