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:
32 //! ```ignore (illustrative)
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;
69 use crate::errors::SubstsOnOverriddenImpl;
71 use rustc_data_structures::fx::FxHashSet;
73 use rustc_hir::def_id::{DefId, LocalDefId};
74 use rustc_infer::infer::outlives::env::OutlivesEnvironment;
75 use rustc_infer::infer::TyCtxtInferExt;
76 use rustc_infer::traits::specialization_graph::Node;
77 use rustc_middle::ty::subst::{GenericArg, InternalSubsts, SubstsRef};
78 use rustc_middle::ty::trait_def::TraitSpecializationKind;
79 use rustc_middle::ty::{self, TyCtxt, TypeVisitable};
81 use rustc_trait_selection::traits::error_reporting::TypeErrCtxtExt;
82 use rustc_trait_selection::traits::outlives_bounds::InferCtxtExt as _;
83 use rustc_trait_selection::traits::{self, translate_substs, wf, ObligationCtxt};
85 pub(super) fn check_min_specialization(tcx: TyCtxt<'_>, impl_def_id: LocalDefId) {
86 if let Some(node) = parent_specialization_node(tcx, impl_def_id) {
87 check_always_applicable(tcx, impl_def_id, node);
91 fn parent_specialization_node(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId) -> 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.to_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 #[instrument(level = "debug", skip(tcx))]
108 fn check_always_applicable(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId, impl2_node: Node) {
109 if let Some((impl1_substs, impl2_substs)) = get_impl_substs(tcx, impl1_def_id, impl2_node) {
110 let impl2_def_id = impl2_node.def_id();
111 debug!(?impl2_def_id, ?impl2_substs);
113 let parent_substs = if impl2_node.is_from_trait() {
114 impl2_substs.to_vec()
116 unconstrained_parent_impl_substs(tcx, impl2_def_id, impl2_substs)
119 let span = tcx.def_span(impl1_def_id);
120 check_constness(tcx, impl1_def_id, impl2_node, span);
121 check_static_lifetimes(tcx, &parent_substs, span);
122 check_duplicate_params(tcx, impl1_substs, &parent_substs, span);
123 check_predicates(tcx, impl1_def_id, impl1_substs, impl2_node, impl2_substs, span);
127 /// Check that the specializing impl `impl1` is at least as const as the base
129 fn check_constness(tcx: TyCtxt<'_>, impl1_def_id: LocalDefId, impl2_node: Node, span: Span) {
130 if impl2_node.is_from_trait() {
131 // This isn't a specialization
135 let impl1_constness = tcx.constness(impl1_def_id.to_def_id());
136 let impl2_constness = tcx.constness(impl2_node.def_id());
138 if let hir::Constness::Const = impl2_constness {
139 if let hir::Constness::NotConst = impl1_constness {
141 .struct_span_err(span, "cannot specialize on const impl with non-const impl")
147 /// Given a specializing impl `impl1`, and the base impl `impl2`, returns two
148 /// substitutions `(S1, S2)` that equate their trait references. The returned
149 /// types are expressed in terms of the generics of `impl1`.
153 /// ```ignore (illustrative)
154 /// impl<A, B> Foo<A> for B { /* impl2 */ }
155 /// impl<C> Foo<Vec<C>> for C { /* impl1 */ }
158 /// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`.
161 impl1_def_id: LocalDefId,
163 ) -> Option<(SubstsRef<'_>, SubstsRef<'_>)> {
164 let infcx = &tcx.infer_ctxt().build();
165 let ocx = ObligationCtxt::new(infcx);
166 let param_env = tcx.param_env(impl1_def_id);
167 let impl1_hir_id = tcx.hir().local_def_id_to_hir_id(impl1_def_id);
169 let assumed_wf_types =
170 ocx.assumed_wf_types(param_env, tcx.def_span(impl1_def_id), impl1_def_id);
172 let impl1_substs = InternalSubsts::identity_for_item(tcx, impl1_def_id.to_def_id());
174 translate_substs(infcx, param_env, impl1_def_id.to_def_id(), impl1_substs, impl2_node);
176 let errors = ocx.select_all_or_error();
177 if !errors.is_empty() {
178 ocx.infcx.err_ctxt().report_fulfillment_errors(&errors, None);
182 let implied_bounds = infcx.implied_bounds_tys(param_env, impl1_hir_id, assumed_wf_types);
183 let outlives_env = OutlivesEnvironment::with_bounds(param_env, Some(infcx), implied_bounds);
184 let _ = infcx.check_region_obligations_and_report_errors(impl1_def_id, &outlives_env);
185 let Ok(impl2_substs) = infcx.fully_resolve(impl2_substs) else {
186 let span = tcx.def_span(impl1_def_id);
187 tcx.sess.emit_err(SubstsOnOverriddenImpl { span });
190 Some((impl1_substs, impl2_substs))
193 /// Returns a list of all of the unconstrained subst of the given impl.
195 /// For example given the impl:
197 /// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T>
199 /// This would return the substs corresponding to `['a, I]`, because knowing
200 /// `'a` and `I` determines the value of `T`.
201 fn unconstrained_parent_impl_substs<'tcx>(
204 impl_substs: SubstsRef<'tcx>,
205 ) -> Vec<GenericArg<'tcx>> {
206 let impl_generic_predicates = tcx.predicates_of(impl_def_id);
207 let mut unconstrained_parameters = FxHashSet::default();
208 let mut constrained_params = FxHashSet::default();
209 let impl_trait_ref = tcx.impl_trait_ref(impl_def_id);
211 // Unfortunately the functions in `constrained_generic_parameters` don't do
212 // what we want here. We want only a list of constrained parameters while
213 // the functions in `cgp` add the constrained parameters to a list of
214 // unconstrained parameters.
215 for (predicate, _) in impl_generic_predicates.predicates.iter() {
216 if let ty::PredicateKind::Clause(ty::Clause::Projection(proj)) =
217 predicate.kind().skip_binder()
219 let projection_ty = proj.projection_ty;
220 let projected_ty = proj.term;
222 let unbound_trait_ref = projection_ty.trait_ref(tcx);
223 if Some(unbound_trait_ref) == impl_trait_ref {
227 unconstrained_parameters.extend(cgp::parameters_for(&projection_ty, true));
229 for param in cgp::parameters_for(&projected_ty, false) {
230 if !unconstrained_parameters.contains(¶m) {
231 constrained_params.insert(param.0);
235 unconstrained_parameters.extend(cgp::parameters_for(&projected_ty, true));
242 .filter(|&(idx, _)| !constrained_params.contains(&(idx as u32)))
247 /// Check that parameters of the derived impl don't occur more than once in the
248 /// equated substs of the base impl.
250 /// For example forbid the following:
252 /// ```ignore (illustrative)
253 /// impl<A> Tr for A { }
254 /// impl<B> Tr for (B, B) { }
257 /// Note that only consider the unconstrained parameters of the base impl:
259 /// ```ignore (illustrative)
260 /// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { }
261 /// impl<T> Tr<T> for Vec<T> { }
264 /// The substs for the parent impl here are `[T, Vec<T>]`, which repeats `T`,
265 /// but `S` is constrained in the parent impl, so `parent_substs` is only
266 /// `[Vec<T>]`. This means we allow this impl.
267 fn check_duplicate_params<'tcx>(
269 impl1_substs: SubstsRef<'tcx>,
270 parent_substs: &Vec<GenericArg<'tcx>>,
273 let mut base_params = cgp::parameters_for(parent_substs, true);
274 base_params.sort_by_key(|param| param.0);
275 if let (_, [duplicate, ..]) = base_params.partition_dedup() {
276 let param = impl1_substs[duplicate.0 as usize];
278 .struct_span_err(span, &format!("specializing impl repeats parameter `{}`", param))
283 /// Check that `'static` lifetimes are not introduced by the specializing impl.
285 /// For example forbid the following:
287 /// ```ignore (illustrative)
288 /// impl<A> Tr for A { }
289 /// impl Tr for &'static i32 { }
291 fn check_static_lifetimes<'tcx>(
293 parent_substs: &Vec<GenericArg<'tcx>>,
296 if tcx.any_free_region_meets(parent_substs, |r| r.is_static()) {
297 tcx.sess.struct_span_err(span, "cannot specialize on `'static` lifetime").emit();
301 /// Check whether predicates on the specializing impl (`impl1`) are allowed.
303 /// Each predicate `P` must be one of:
305 /// * Global (not reference any parameters).
306 /// * A `T: Tr` predicate where `Tr` is an always-applicable trait.
307 /// * Present on the base impl `impl2`.
308 /// * This check is done using the `trait_predicates_eq` function below.
309 /// * A well-formed predicate of a type argument of the trait being implemented,
310 /// including the `Self`-type.
311 #[instrument(level = "debug", skip(tcx))]
312 fn check_predicates<'tcx>(
314 impl1_def_id: LocalDefId,
315 impl1_substs: SubstsRef<'tcx>,
317 impl2_substs: SubstsRef<'tcx>,
320 let instantiated = tcx.predicates_of(impl1_def_id).instantiate(tcx, impl1_substs);
321 let impl1_predicates: Vec<_> = traits::elaborate_predicates_with_span(
324 instantiated.predicates,
325 // Don't drop predicates (unsound!) because `spans` is too short
326 instantiated.spans.into_iter().chain(std::iter::repeat(span)),
329 .map(|obligation| (obligation.predicate, obligation.cause.span))
332 let mut impl2_predicates = if impl2_node.is_from_trait() {
333 // Always applicable traits have to be always applicable without any
337 traits::elaborate_predicates(
339 tcx.predicates_of(impl2_node.def_id())
340 .instantiate(tcx, impl2_substs)
344 .map(|obligation| obligation.predicate)
347 debug!(?impl1_predicates, ?impl2_predicates);
349 // Since impls of always applicable traits don't get to assume anything, we
350 // can also assume their supertraits apply.
352 // For example, we allow:
354 // #[rustc_specialization_trait]
355 // trait AlwaysApplicable: Debug { }
357 // impl<T> Tr for T { }
358 // impl<T: AlwaysApplicable> Tr for T { }
360 // Specializing on `AlwaysApplicable` allows also specializing on `Debug`
361 // which is sound because we forbid impls like the following
363 // impl<D: Debug> AlwaysApplicable for D { }
364 let always_applicable_traits = impl1_predicates.iter().copied().filter(|&(predicate, _)| {
366 trait_predicate_kind(tcx, predicate),
367 Some(TraitSpecializationKind::AlwaysApplicable)
371 // Include the well-formed predicates of the type parameters of the impl.
372 for arg in tcx.impl_trait_ref(impl1_def_id).unwrap().substs {
373 let infcx = &tcx.infer_ctxt().build();
374 let obligations = wf::obligations(
376 tcx.param_env(impl1_def_id),
377 tcx.hir().local_def_id_to_hir_id(impl1_def_id),
384 assert!(!obligations.needs_infer());
385 impl2_predicates.extend(
386 traits::elaborate_obligations(tcx, obligations).map(|obligation| obligation.predicate),
389 impl2_predicates.extend(
390 traits::elaborate_predicates_with_span(tcx, always_applicable_traits)
391 .map(|obligation| obligation.predicate),
394 for (predicate, span) in impl1_predicates {
395 if !impl2_predicates.iter().any(|pred2| trait_predicates_eq(tcx, predicate, *pred2, span)) {
396 check_specialization_on(tcx, predicate, span)
401 /// Checks if some predicate on the specializing impl (`predicate1`) is the same
402 /// as some predicate on the base impl (`predicate2`).
404 /// This basically just checks syntactic equivalence, but is a little more
405 /// forgiving since we want to equate `T: Tr` with `T: ~const Tr` so this can work:
407 /// ```ignore (illustrative)
408 /// #[rustc_specialization_trait]
409 /// trait Specialize { }
411 /// impl<T: Bound> Tr for T { }
412 /// impl<T: ~const Bound + Specialize> const Tr for T { }
415 /// However, we *don't* want to allow the reverse, i.e., when the bound on the
416 /// specializing impl is not as const as the bound on the base impl:
418 /// ```ignore (illustrative)
419 /// impl<T: ~const Bound> const Tr for T { }
420 /// impl<T: Bound + Specialize> const Tr for T { } // should be T: ~const Bound
423 /// So we make that check in this function and try to raise a helpful error message.
424 fn trait_predicates_eq<'tcx>(
426 predicate1: ty::Predicate<'tcx>,
427 predicate2: ty::Predicate<'tcx>,
430 let pred1_kind = predicate1.kind().skip_binder();
431 let pred2_kind = predicate2.kind().skip_binder();
432 let (trait_pred1, trait_pred2) = match (pred1_kind, pred2_kind) {
434 ty::PredicateKind::Clause(ty::Clause::Trait(pred1)),
435 ty::PredicateKind::Clause(ty::Clause::Trait(pred2)),
437 // Just use plain syntactic equivalence if either of the predicates aren't
438 // trait predicates or have bound vars.
439 _ => return predicate1 == predicate2,
442 let predicates_equal_modulo_constness = {
443 let pred1_unconsted =
444 ty::TraitPredicate { constness: ty::BoundConstness::NotConst, ..trait_pred1 };
445 let pred2_unconsted =
446 ty::TraitPredicate { constness: ty::BoundConstness::NotConst, ..trait_pred2 };
447 pred1_unconsted == pred2_unconsted
450 if !predicates_equal_modulo_constness {
454 // Check that the predicate on the specializing impl is at least as const as
455 // the one on the base.
456 match (trait_pred2.constness, trait_pred1.constness) {
457 (ty::BoundConstness::ConstIfConst, ty::BoundConstness::NotConst) => {
458 tcx.sess.struct_span_err(span, "missing `~const` qualifier for specialization").emit();
466 #[instrument(level = "debug", skip(tcx))]
467 fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, predicate: ty::Predicate<'tcx>, span: Span) {
468 match predicate.kind().skip_binder() {
469 // Global predicates are either always true or always false, so we
470 // are fine to specialize on.
471 _ if predicate.is_global() => (),
472 // We allow specializing on explicitly marked traits with no associated
474 ty::PredicateKind::Clause(ty::Clause::Trait(ty::TraitPredicate {
480 trait_predicate_kind(tcx, predicate),
481 Some(TraitSpecializationKind::Marker)
487 "cannot specialize on trait `{}`",
488 tcx.def_path_str(trait_ref.def_id),
494 ty::PredicateKind::Clause(ty::Clause::Projection(ty::ProjectionPredicate {
501 &format!("cannot specialize on associated type `{projection_ty} == {term}`",),
507 .struct_span_err(span, &format!("cannot specialize on predicate `{}`", predicate))
513 fn trait_predicate_kind<'tcx>(
515 predicate: ty::Predicate<'tcx>,
516 ) -> Option<TraitSpecializationKind> {
517 match predicate.kind().skip_binder() {
518 ty::PredicateKind::Clause(ty::Clause::Trait(ty::TraitPredicate {
522 })) => Some(tcx.trait_def(trait_ref.def_id).specialization_kind),
523 ty::PredicateKind::Clause(ty::Clause::RegionOutlives(_))
524 | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(_))
525 | ty::PredicateKind::Clause(ty::Clause::Projection(_))
526 | ty::PredicateKind::WellFormed(_)
527 | ty::PredicateKind::Subtype(_)
528 | ty::PredicateKind::Coerce(_)
529 | ty::PredicateKind::ObjectSafe(_)
530 | ty::PredicateKind::ClosureKind(..)
531 | ty::PredicateKind::ConstEvaluatable(..)
532 | ty::PredicateKind::ConstEquate(..)
533 | ty::PredicateKind::Ambiguous
534 | ty::PredicateKind::TypeWellFormedFromEnv(..) => None,