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
::ty
::subst
::{GenericArg, InternalSubsts, SubstsRef}
;
77 use rustc_middle
::ty
::trait_def
::TraitSpecializationKind
;
78 use rustc_middle
::ty
::{self, InstantiatedPredicates, TyCtxt, TypeFoldable}
;
80 use rustc_trait_selection
::traits
::{self, translate_substs, wf}
;
82 pub(super) fn check_min_specialization(tcx
: TyCtxt
<'_
>, impl_def_id
: DefId
, span
: Span
) {
83 if let Some(node
) = parent_specialization_node(tcx
, impl_def_id
) {
84 tcx
.infer_ctxt().enter(|infcx
| {
85 check_always_applicable(&infcx
, impl_def_id
, node
, span
);
90 fn parent_specialization_node(tcx
: TyCtxt
<'_
>, impl1_def_id
: DefId
) -> Option
<Node
> {
91 let trait_ref
= tcx
.impl_trait_ref(impl1_def_id
)?
;
92 let trait_def
= tcx
.trait_def(trait_ref
.def_id
);
94 let impl2_node
= trait_def
.ancestors(tcx
, impl1_def_id
).ok()?
.nth(1)?
;
96 let always_applicable_trait
=
97 matches
!(trait_def
.specialization_kind
, TraitSpecializationKind
::AlwaysApplicable
);
98 if impl2_node
.is_from_trait() && !always_applicable_trait
{
99 // Implementing a normal trait isn't a specialization.
105 /// Check that `impl1` is a sound specialization
106 fn check_always_applicable(
107 infcx
: &InferCtxt
<'_
, '_
>,
112 if let Some((impl1_substs
, impl2_substs
)) =
113 get_impl_substs(infcx
, impl1_def_id
, impl2_node
, span
)
115 let impl2_def_id
= impl2_node
.def_id();
117 "check_always_applicable(\nimpl1_def_id={:?},\nimpl2_def_id={:?},\nimpl2_substs={:?}\n)",
118 impl1_def_id
, impl2_def_id
, impl2_substs
123 let parent_substs
= if impl2_node
.is_from_trait() {
124 impl2_substs
.to_vec()
126 unconstrained_parent_impl_substs(tcx
, impl2_def_id
, impl2_substs
)
129 check_static_lifetimes(tcx
, &parent_substs
, span
);
130 check_duplicate_params(tcx
, impl1_substs
, &parent_substs
, span
);
134 impl1_def_id
.expect_local(),
143 /// Given a specializing impl `impl1`, and the base impl `impl2`, returns two
144 /// substitutions `(S1, S2)` that equate their trait references. The returned
145 /// types are expressed in terms of the generics of `impl1`.
149 /// impl<A, B> Foo<A> for B { /* impl2 */ }
150 /// impl<C> Foo<Vec<C>> for C { /* impl1 */ }
152 /// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`.
153 fn get_impl_substs
<'tcx
>(
154 infcx
: &InferCtxt
<'_
, 'tcx
>,
158 ) -> Option
<(SubstsRef
<'tcx
>, SubstsRef
<'tcx
>)> {
160 let param_env
= tcx
.param_env(impl1_def_id
);
162 let impl1_substs
= InternalSubsts
::identity_for_item(tcx
, impl1_def_id
);
163 let impl2_substs
= translate_substs(infcx
, param_env
, impl1_def_id
, impl1_substs
, impl2_node
);
165 // Conservatively use an empty `ParamEnv`.
166 let outlives_env
= OutlivesEnvironment
::new(ty
::ParamEnv
::empty());
167 infcx
.resolve_regions_and_report_errors(impl1_def_id
, &outlives_env
, RegionckMode
::default());
168 let impl2_substs
= match infcx
.fully_resolve(&impl2_substs
) {
171 tcx
.sess
.struct_span_err(span
, "could not resolve substs on overridden impl").emit();
175 Some((impl1_substs
, impl2_substs
))
178 /// Returns a list of all of the unconstrained subst of the given impl.
180 /// For example given the impl:
182 /// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T>
184 /// This would return the substs corresponding to `['a, I]`, because knowing
185 /// `'a` and `I` determines the value of `T`.
186 fn unconstrained_parent_impl_substs
<'tcx
>(
189 impl_substs
: SubstsRef
<'tcx
>,
190 ) -> Vec
<GenericArg
<'tcx
>> {
191 let impl_generic_predicates
= tcx
.predicates_of(impl_def_id
);
192 let mut unconstrained_parameters
= FxHashSet
::default();
193 let mut constrained_params
= FxHashSet
::default();
194 let impl_trait_ref
= tcx
.impl_trait_ref(impl_def_id
);
196 // Unfortunately the functions in `constrained_generic_parameters` don't do
197 // what we want here. We want only a list of constrained parameters while
198 // the functions in `cgp` add the constrained parameters to a list of
199 // unconstrained parameters.
200 for (predicate
, _
) in impl_generic_predicates
.predicates
.iter() {
201 if let ty
::PredicateAtom
::Projection(proj
) = predicate
.skip_binders() {
202 let projection_ty
= proj
.projection_ty
;
203 let projected_ty
= proj
.ty
;
205 let unbound_trait_ref
= projection_ty
.trait_ref(tcx
);
206 if Some(unbound_trait_ref
) == impl_trait_ref
{
210 unconstrained_parameters
.extend(cgp
::parameters_for(&projection_ty
, true));
212 for param
in cgp
::parameters_for(&projected_ty
, false) {
213 if !unconstrained_parameters
.contains(¶m
) {
214 constrained_params
.insert(param
.0);
218 unconstrained_parameters
.extend(cgp
::parameters_for(&projected_ty
, true));
225 .filter(|&(idx
, _
)| !constrained_params
.contains(&(idx
as u32)))
230 /// Check that parameters of the derived impl don't occur more than once in the
231 /// equated substs of the base impl.
233 /// For example forbid the following:
235 /// impl<A> Tr for A { }
236 /// impl<B> Tr for (B, B) { }
238 /// Note that only consider the unconstrained parameters of the base impl:
240 /// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { }
241 /// impl<T> Tr<T> for Vec<T> { }
243 /// The substs for the parent impl here are `[T, Vec<T>]`, which repeats `T`,
244 /// but `S` is constrained in the parent impl, so `parent_substs` is only
245 /// `[Vec<T>]`. This means we allow this impl.
246 fn check_duplicate_params
<'tcx
>(
248 impl1_substs
: SubstsRef
<'tcx
>,
249 parent_substs
: &Vec
<GenericArg
<'tcx
>>,
252 let mut base_params
= cgp
::parameters_for(parent_substs
, true);
253 base_params
.sort_by_key(|param
| param
.0);
254 if let (_
, [duplicate
, ..]) = base_params
.partition_dedup() {
255 let param
= impl1_substs
[duplicate
.0 as usize];
257 .struct_span_err(span
, &format
!("specializing impl repeats parameter `{}`", param
))
262 /// Check that `'static` lifetimes are not introduced by the specializing impl.
264 /// For example forbid the following:
266 /// impl<A> Tr for A { }
267 /// impl Tr for &'static i32 { }
268 fn check_static_lifetimes
<'tcx
>(
270 parent_substs
: &Vec
<GenericArg
<'tcx
>>,
273 if tcx
.any_free_region_meets(parent_substs
, |r
| *r
== ty
::ReStatic
) {
274 tcx
.sess
.struct_span_err(span
, "cannot specialize on `'static` lifetime").emit();
278 /// Check whether predicates on the specializing impl (`impl1`) are allowed.
280 /// Each predicate `P` must be:
282 /// * global (not reference any parameters)
283 /// * `T: Tr` predicate where `Tr` is an always-applicable trait
284 /// * on the base `impl impl2`
285 /// * Currently this check is done using syntactic equality, which is
286 /// conservative but generally sufficient.
287 /// * a well-formed predicate of a type argument of the trait being implemented,
288 /// including the `Self`-type.
289 fn check_predicates
<'tcx
>(
290 infcx
: &InferCtxt
<'_
, 'tcx
>,
291 impl1_def_id
: LocalDefId
,
292 impl1_substs
: SubstsRef
<'tcx
>,
294 impl2_substs
: SubstsRef
<'tcx
>,
298 let impl1_predicates
= tcx
.predicates_of(impl1_def_id
).instantiate(tcx
, impl1_substs
);
299 let mut impl2_predicates
= if impl2_node
.is_from_trait() {
300 // Always applicable traits have to be always applicable without any
302 InstantiatedPredicates
::empty()
304 tcx
.predicates_of(impl2_node
.def_id()).instantiate(tcx
, impl2_substs
)
307 "check_always_applicable(\nimpl1_predicates={:?},\nimpl2_predicates={:?}\n)",
308 impl1_predicates
, impl2_predicates
,
311 // Since impls of always applicable traits don't get to assume anything, we
312 // can also assume their supertraits apply.
314 // For example, we allow:
316 // #[rustc_specialization_trait]
317 // trait AlwaysApplicable: Debug { }
319 // impl<T> Tr for T { }
320 // impl<T: AlwaysApplicable> Tr for T { }
322 // Specializing on `AlwaysApplicable` allows also specializing on `Debug`
323 // which is sound because we forbid impls like the following
325 // impl<D: Debug> AlwaysApplicable for D { }
326 let always_applicable_traits
=
327 impl1_predicates
.predicates
.iter().copied().filter(|&predicate
| {
329 trait_predicate_kind(tcx
, predicate
),
330 Some(TraitSpecializationKind
::AlwaysApplicable
)
334 // Include the well-formed predicates of the type parameters of the impl.
335 for arg
in tcx
.impl_trait_ref(impl1_def_id
).unwrap().substs
{
336 if let Some(obligations
) = wf
::obligations(
338 tcx
.param_env(impl1_def_id
),
339 tcx
.hir().local_def_id_to_hir_id(impl1_def_id
),
345 .extend(obligations
.into_iter().map(|obligation
| obligation
.predicate
))
348 impl2_predicates
.predicates
.extend(
349 traits
::elaborate_predicates(tcx
, always_applicable_traits
)
350 .map(|obligation
| obligation
.predicate
),
353 for predicate
in impl1_predicates
.predicates
{
354 if !impl2_predicates
.predicates
.contains(&predicate
) {
355 check_specialization_on(tcx
, predicate
, span
)
360 fn check_specialization_on
<'tcx
>(tcx
: TyCtxt
<'tcx
>, predicate
: ty
::Predicate
<'tcx
>, span
: Span
) {
361 debug
!("can_specialize_on(predicate = {:?})", predicate
);
362 match predicate
.skip_binders() {
363 // Global predicates are either always true or always false, so we
364 // are fine to specialize on.
365 _
if predicate
.is_global() => (),
366 // We allow specializing on explicitly marked traits with no associated
368 ty
::PredicateAtom
::Trait(pred
, hir
::Constness
::NotConst
) => {
370 trait_predicate_kind(tcx
, predicate
),
371 Some(TraitSpecializationKind
::Marker
)
377 "cannot specialize on trait `{}`",
378 tcx
.def_path_str(pred
.def_id()),
386 .struct_span_err(span
, &format
!("cannot specialize on `{:?}`", predicate
))
391 fn trait_predicate_kind
<'tcx
>(
393 predicate
: ty
::Predicate
<'tcx
>,
394 ) -> Option
<TraitSpecializationKind
> {
395 match predicate
.skip_binders() {
396 ty
::PredicateAtom
::Trait(pred
, hir
::Constness
::NotConst
) => {
397 Some(tcx
.trait_def(pred
.def_id()).specialization_kind
)
399 ty
::PredicateAtom
::Trait(_
, hir
::Constness
::Const
)
400 | ty
::PredicateAtom
::RegionOutlives(_
)
401 | ty
::PredicateAtom
::TypeOutlives(_
)
402 | ty
::PredicateAtom
::Projection(_
)
403 | ty
::PredicateAtom
::WellFormed(_
)
404 | ty
::PredicateAtom
::Subtype(_
)
405 | ty
::PredicateAtom
::ObjectSafe(_
)
406 | ty
::PredicateAtom
::ClosureKind(..)
407 | ty
::PredicateAtom
::ConstEvaluatable(..)
408 | ty
::PredicateAtom
::ConstEquate(..) => None
,