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
;
71 use rustc_hir
::def_id
::{DefId, LocalDefId}
;
72 use rustc_infer
::infer
::outlives
::env
::OutlivesEnvironment
;
73 use rustc_infer
::infer
::{InferCtxt, RegionckMode, TyCtxtInferExt}
;
74 use rustc_infer
::traits
::specialization_graph
::Node
;
75 use rustc_middle
::ty
::subst
::{GenericArg, InternalSubsts, SubstsRef}
;
76 use rustc_middle
::ty
::trait_def
::TraitSpecializationKind
;
77 use rustc_middle
::ty
::{self, TyCtxt, TypeFoldable}
;
79 use rustc_trait_selection
::traits
::{self, translate_substs, wf}
;
81 pub(super) fn check_min_specialization(tcx
: TyCtxt
<'_
>, impl_def_id
: DefId
, span
: Span
) {
82 if let Some(node
) = parent_specialization_node(tcx
, impl_def_id
) {
83 tcx
.infer_ctxt().enter(|infcx
| {
84 check_always_applicable(&infcx
, impl_def_id
, node
, span
);
89 fn parent_specialization_node(tcx
: TyCtxt
<'_
>, impl1_def_id
: DefId
) -> Option
<Node
> {
90 let trait_ref
= tcx
.impl_trait_ref(impl1_def_id
)?
;
91 let trait_def
= tcx
.trait_def(trait_ref
.def_id
);
93 let impl2_node
= trait_def
.ancestors(tcx
, impl1_def_id
).ok()?
.nth(1)?
;
95 let always_applicable_trait
=
96 matches
!(trait_def
.specialization_kind
, TraitSpecializationKind
::AlwaysApplicable
);
97 if impl2_node
.is_from_trait() && !always_applicable_trait
{
98 // Implementing a normal trait isn't a specialization.
104 /// Check that `impl1` is a sound specialization
105 fn check_always_applicable(
106 infcx
: &InferCtxt
<'_
, '_
>,
111 if let Some((impl1_substs
, impl2_substs
)) =
112 get_impl_substs(infcx
, impl1_def_id
, impl2_node
, span
)
114 let impl2_def_id
= impl2_node
.def_id();
116 "check_always_applicable(\nimpl1_def_id={:?},\nimpl2_def_id={:?},\nimpl2_substs={:?}\n)",
117 impl1_def_id
, impl2_def_id
, impl2_substs
122 let parent_substs
= if impl2_node
.is_from_trait() {
123 impl2_substs
.to_vec()
125 unconstrained_parent_impl_substs(tcx
, impl2_def_id
, impl2_substs
)
128 check_static_lifetimes(tcx
, &parent_substs
, span
);
129 check_duplicate_params(tcx
, impl1_substs
, &parent_substs
, span
);
133 impl1_def_id
.expect_local(),
142 /// Given a specializing impl `impl1`, and the base impl `impl2`, returns two
143 /// substitutions `(S1, S2)` that equate their trait references. The returned
144 /// types are expressed in terms of the generics of `impl1`.
148 /// impl<A, B> Foo<A> for B { /* impl2 */ }
149 /// impl<C> Foo<Vec<C>> for C { /* impl1 */ }
151 /// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`.
152 fn get_impl_substs
<'tcx
>(
153 infcx
: &InferCtxt
<'_
, 'tcx
>,
157 ) -> Option
<(SubstsRef
<'tcx
>, SubstsRef
<'tcx
>)> {
159 let param_env
= tcx
.param_env(impl1_def_id
);
161 let impl1_substs
= InternalSubsts
::identity_for_item(tcx
, impl1_def_id
);
162 let impl2_substs
= translate_substs(infcx
, param_env
, impl1_def_id
, impl1_substs
, impl2_node
);
164 // Conservatively use an empty `ParamEnv`.
165 let outlives_env
= OutlivesEnvironment
::new(ty
::ParamEnv
::empty());
166 infcx
.resolve_regions_and_report_errors(impl1_def_id
, &outlives_env
, RegionckMode
::default());
167 let Ok(impl2_substs
) = infcx
.fully_resolve(impl2_substs
) else {
168 tcx
.sess
.struct_span_err(span
, "could not resolve substs on overridden impl").emit();
171 Some((impl1_substs
, impl2_substs
))
174 /// Returns a list of all of the unconstrained subst of the given impl.
176 /// For example given the impl:
178 /// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T>
180 /// This would return the substs corresponding to `['a, I]`, because knowing
181 /// `'a` and `I` determines the value of `T`.
182 fn unconstrained_parent_impl_substs
<'tcx
>(
185 impl_substs
: SubstsRef
<'tcx
>,
186 ) -> Vec
<GenericArg
<'tcx
>> {
187 let impl_generic_predicates
= tcx
.predicates_of(impl_def_id
);
188 let mut unconstrained_parameters
= FxHashSet
::default();
189 let mut constrained_params
= FxHashSet
::default();
190 let impl_trait_ref
= tcx
.impl_trait_ref(impl_def_id
);
192 // Unfortunately the functions in `constrained_generic_parameters` don't do
193 // what we want here. We want only a list of constrained parameters while
194 // the functions in `cgp` add the constrained parameters to a list of
195 // unconstrained parameters.
196 for (predicate
, _
) in impl_generic_predicates
.predicates
.iter() {
197 if let ty
::PredicateKind
::Projection(proj
) = predicate
.kind().skip_binder() {
198 let projection_ty
= proj
.projection_ty
;
199 let projected_ty
= proj
.term
;
201 let unbound_trait_ref
= projection_ty
.trait_ref(tcx
);
202 if Some(unbound_trait_ref
) == impl_trait_ref
{
206 unconstrained_parameters
.extend(cgp
::parameters_for(&projection_ty
, true));
208 for param
in cgp
::parameters_for(&projected_ty
, false) {
209 if !unconstrained_parameters
.contains(¶m
) {
210 constrained_params
.insert(param
.0);
214 unconstrained_parameters
.extend(cgp
::parameters_for(&projected_ty
, true));
221 .filter(|&(idx
, _
)| !constrained_params
.contains(&(idx
as u32)))
226 /// Check that parameters of the derived impl don't occur more than once in the
227 /// equated substs of the base impl.
229 /// For example forbid the following:
231 /// impl<A> Tr for A { }
232 /// impl<B> Tr for (B, B) { }
234 /// Note that only consider the unconstrained parameters of the base impl:
236 /// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { }
237 /// impl<T> Tr<T> for Vec<T> { }
239 /// The substs for the parent impl here are `[T, Vec<T>]`, which repeats `T`,
240 /// but `S` is constrained in the parent impl, so `parent_substs` is only
241 /// `[Vec<T>]`. This means we allow this impl.
242 fn check_duplicate_params
<'tcx
>(
244 impl1_substs
: SubstsRef
<'tcx
>,
245 parent_substs
: &Vec
<GenericArg
<'tcx
>>,
248 let mut base_params
= cgp
::parameters_for(parent_substs
, true);
249 base_params
.sort_by_key(|param
| param
.0);
250 if let (_
, [duplicate
, ..]) = base_params
.partition_dedup() {
251 let param
= impl1_substs
[duplicate
.0 as usize];
253 .struct_span_err(span
, &format
!("specializing impl repeats parameter `{}`", param
))
258 /// Check that `'static` lifetimes are not introduced by the specializing impl.
260 /// For example forbid the following:
262 /// impl<A> Tr for A { }
263 /// impl Tr for &'static i32 { }
264 fn check_static_lifetimes
<'tcx
>(
266 parent_substs
: &Vec
<GenericArg
<'tcx
>>,
269 if tcx
.any_free_region_meets(parent_substs
, |r
| r
.is_static()) {
270 tcx
.sess
.struct_span_err(span
, "cannot specialize on `'static` lifetime").emit();
274 /// Check whether predicates on the specializing impl (`impl1`) are allowed.
276 /// Each predicate `P` must be:
278 /// * global (not reference any parameters)
279 /// * `T: Tr` predicate where `Tr` is an always-applicable trait
280 /// * on the base `impl impl2`
281 /// * Currently this check is done using syntactic equality, which is
282 /// conservative but generally sufficient.
283 /// * a well-formed predicate of a type argument of the trait being implemented,
284 /// including the `Self`-type.
285 fn check_predicates
<'tcx
>(
286 infcx
: &InferCtxt
<'_
, 'tcx
>,
287 impl1_def_id
: LocalDefId
,
288 impl1_substs
: SubstsRef
<'tcx
>,
290 impl2_substs
: SubstsRef
<'tcx
>,
294 let impl1_predicates
: Vec
<_
> = traits
::elaborate_predicates(
296 tcx
.predicates_of(impl1_def_id
).instantiate(tcx
, impl1_substs
).predicates
.into_iter(),
298 .map(|obligation
| obligation
.predicate
)
301 let mut impl2_predicates
= if impl2_node
.is_from_trait() {
302 // Always applicable traits have to be always applicable without any
306 traits
::elaborate_predicates(
308 tcx
.predicates_of(impl2_node
.def_id())
309 .instantiate(tcx
, impl2_substs
)
313 .map(|obligation
| obligation
.predicate
)
317 "check_always_applicable(\nimpl1_predicates={:?},\nimpl2_predicates={:?}\n)",
318 impl1_predicates
, impl2_predicates
,
321 // Since impls of always applicable traits don't get to assume anything, we
322 // can also assume their supertraits apply.
324 // For example, we allow:
326 // #[rustc_specialization_trait]
327 // trait AlwaysApplicable: Debug { }
329 // impl<T> Tr for T { }
330 // impl<T: AlwaysApplicable> Tr for T { }
332 // Specializing on `AlwaysApplicable` allows also specializing on `Debug`
333 // which is sound because we forbid impls like the following
335 // impl<D: Debug> AlwaysApplicable for D { }
336 let always_applicable_traits
= impl1_predicates
.iter().copied().filter(|&predicate
| {
338 trait_predicate_kind(tcx
, predicate
),
339 Some(TraitSpecializationKind
::AlwaysApplicable
)
343 // Include the well-formed predicates of the type parameters of the impl.
344 for arg
in tcx
.impl_trait_ref(impl1_def_id
).unwrap().substs
{
345 if let Some(obligations
) = wf
::obligations(
347 tcx
.param_env(impl1_def_id
),
348 tcx
.hir().local_def_id_to_hir_id(impl1_def_id
),
353 impl2_predicates
.extend(
354 traits
::elaborate_obligations(tcx
, obligations
)
355 .map(|obligation
| obligation
.predicate
),
359 impl2_predicates
.extend(
360 traits
::elaborate_predicates(tcx
, always_applicable_traits
)
361 .map(|obligation
| obligation
.predicate
),
364 for predicate
in impl1_predicates
{
365 if !impl2_predicates
.contains(&predicate
) {
366 check_specialization_on(tcx
, predicate
, span
)
371 fn check_specialization_on
<'tcx
>(tcx
: TyCtxt
<'tcx
>, predicate
: ty
::Predicate
<'tcx
>, span
: Span
) {
372 debug
!("can_specialize_on(predicate = {:?})", predicate
);
373 match predicate
.kind().skip_binder() {
374 // Global predicates are either always true or always false, so we
375 // are fine to specialize on.
376 _
if predicate
.is_global() => (),
377 // We allow specializing on explicitly marked traits with no associated
379 ty
::PredicateKind
::Trait(ty
::TraitPredicate
{
381 constness
: ty
::BoundConstness
::NotConst
,
385 trait_predicate_kind(tcx
, predicate
),
386 Some(TraitSpecializationKind
::Marker
)
392 "cannot specialize on trait `{}`",
393 tcx
.def_path_str(trait_ref
.def_id
),
401 .struct_span_err(span
, &format
!("cannot specialize on `{:?}`", predicate
))
407 fn trait_predicate_kind
<'tcx
>(
409 predicate
: ty
::Predicate
<'tcx
>,
410 ) -> Option
<TraitSpecializationKind
> {
411 match predicate
.kind().skip_binder() {
412 ty
::PredicateKind
::Trait(ty
::TraitPredicate
{
414 constness
: ty
::BoundConstness
::NotConst
,
416 }) => Some(tcx
.trait_def(trait_ref
.def_id
).specialization_kind
),
417 ty
::PredicateKind
::Trait(_
)
418 | ty
::PredicateKind
::RegionOutlives(_
)
419 | ty
::PredicateKind
::TypeOutlives(_
)
420 | ty
::PredicateKind
::Projection(_
)
421 | ty
::PredicateKind
::WellFormed(_
)
422 | ty
::PredicateKind
::Subtype(_
)
423 | ty
::PredicateKind
::Coerce(_
)
424 | ty
::PredicateKind
::ObjectSafe(_
)
425 | ty
::PredicateKind
::ClosureKind(..)
426 | ty
::PredicateKind
::ConstEvaluatable(..)
427 | ty
::PredicateKind
::ConstEquate(..)
428 | ty
::PredicateKind
::TypeWellFormedFromEnv(..) => None
,