]>
Commit | Line | Data |
---|---|---|
ba9703b0 XL |
1 | //! # Minimal Specialization |
2 | //! | |
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*. | |
6 | //! | |
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. | |
11 | //! | |
12 | //! ## Basic approach | |
13 | //! | |
14 | //! To enforce this requirement on specializations we take the following | |
15 | //! approach: | |
16 | //! | |
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 | |
23 | //! predicate. | |
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 | |
26 | //! arguments. | |
27 | //! | |
28 | //! ## Example | |
29 | //! | |
30 | //! Suppose we have the following always applicable impl: | |
31 | //! | |
32 | //! ```rust | |
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 */ } | |
35 | //! ``` | |
36 | //! | |
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. | |
42 | //! | |
43 | //! ## Extensions | |
44 | //! | |
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. | |
49 | //! | |
50 | //! ### rustc_specialization_trait | |
51 | //! | |
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 | |
56 | //! traits. | |
57 | //! | |
58 | //! ### rustc_unsafe_specialization_marker | |
59 | //! | |
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. | |
67 | ||
68 | use crate::constrained_generic_params as cgp; | |
69 | ||
70 | use rustc_data_structures::fx::FxHashSet; | |
f9f354fc | 71 | use rustc_hir::def_id::{DefId, LocalDefId}; |
ba9703b0 XL |
72 | use rustc_infer::infer::outlives::env::OutlivesEnvironment; |
73 | use rustc_infer::infer::{InferCtxt, RegionckMode, TyCtxtInferExt}; | |
74 | use rustc_infer::traits::specialization_graph::Node; | |
ba9703b0 XL |
75 | use rustc_middle::ty::subst::{GenericArg, InternalSubsts, SubstsRef}; |
76 | use rustc_middle::ty::trait_def::TraitSpecializationKind; | |
77 | use rustc_middle::ty::{self, InstantiatedPredicates, TyCtxt, TypeFoldable}; | |
78 | use rustc_span::Span; | |
79 | use rustc_trait_selection::traits::{self, translate_substs, wf}; | |
80 | ||
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); | |
85 | }); | |
86 | } | |
87 | } | |
88 | ||
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); | |
92 | ||
93 | let impl2_node = trait_def.ancestors(tcx, impl1_def_id).ok()?.nth(1)?; | |
94 | ||
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. | |
99 | return None; | |
100 | } | |
101 | Some(impl2_node) | |
102 | } | |
103 | ||
104 | /// Check that `impl1` is a sound specialization | |
105 | fn check_always_applicable( | |
106 | infcx: &InferCtxt<'_, '_>, | |
107 | impl1_def_id: DefId, | |
108 | impl2_node: Node, | |
109 | span: Span, | |
110 | ) { | |
111 | if let Some((impl1_substs, impl2_substs)) = | |
112 | get_impl_substs(infcx, impl1_def_id, impl2_node, span) | |
113 | { | |
114 | let impl2_def_id = impl2_node.def_id(); | |
115 | debug!( | |
116 | "check_always_applicable(\nimpl1_def_id={:?},\nimpl2_def_id={:?},\nimpl2_substs={:?}\n)", | |
117 | impl1_def_id, impl2_def_id, impl2_substs | |
118 | ); | |
119 | ||
120 | let tcx = infcx.tcx; | |
121 | ||
122 | let parent_substs = if impl2_node.is_from_trait() { | |
123 | impl2_substs.to_vec() | |
124 | } else { | |
125 | unconstrained_parent_impl_substs(tcx, impl2_def_id, impl2_substs) | |
126 | }; | |
127 | ||
128 | check_static_lifetimes(tcx, &parent_substs, span); | |
129 | check_duplicate_params(tcx, impl1_substs, &parent_substs, span); | |
130 | ||
f9f354fc XL |
131 | check_predicates( |
132 | infcx, | |
133 | impl1_def_id.expect_local(), | |
134 | impl1_substs, | |
135 | impl2_node, | |
136 | impl2_substs, | |
137 | span, | |
138 | ); | |
ba9703b0 XL |
139 | } |
140 | } | |
141 | ||
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`. | |
145 | /// | |
146 | /// Example | |
147 | /// | |
148 | /// impl<A, B> Foo<A> for B { /* impl2 */ } | |
149 | /// impl<C> Foo<Vec<C>> for C { /* impl1 */ } | |
150 | /// | |
151 | /// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`. | |
152 | fn get_impl_substs<'tcx>( | |
153 | infcx: &InferCtxt<'_, 'tcx>, | |
154 | impl1_def_id: DefId, | |
155 | impl2_node: Node, | |
156 | span: Span, | |
157 | ) -> Option<(SubstsRef<'tcx>, SubstsRef<'tcx>)> { | |
158 | let tcx = infcx.tcx; | |
159 | let param_env = tcx.param_env(impl1_def_id); | |
160 | ||
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); | |
163 | ||
164 | // Conservatively use an empty `ParamEnv`. | |
165 | let outlives_env = OutlivesEnvironment::new(ty::ParamEnv::empty()); | |
f9f354fc | 166 | infcx.resolve_regions_and_report_errors(impl1_def_id, &outlives_env, RegionckMode::default()); |
fc512014 | 167 | let impl2_substs = match infcx.fully_resolve(impl2_substs) { |
ba9703b0 XL |
168 | Ok(s) => s, |
169 | Err(_) => { | |
170 | tcx.sess.struct_span_err(span, "could not resolve substs on overridden impl").emit(); | |
171 | return None; | |
172 | } | |
173 | }; | |
174 | Some((impl1_substs, impl2_substs)) | |
175 | } | |
176 | ||
177 | /// Returns a list of all of the unconstrained subst of the given impl. | |
178 | /// | |
179 | /// For example given the impl: | |
180 | /// | |
181 | /// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T> | |
182 | /// | |
183 | /// This would return the substs corresponding to `['a, I]`, because knowing | |
184 | /// `'a` and `I` determines the value of `T`. | |
185 | fn unconstrained_parent_impl_substs<'tcx>( | |
186 | tcx: TyCtxt<'tcx>, | |
187 | impl_def_id: DefId, | |
188 | impl_substs: SubstsRef<'tcx>, | |
189 | ) -> Vec<GenericArg<'tcx>> { | |
190 | let impl_generic_predicates = tcx.predicates_of(impl_def_id); | |
191 | let mut unconstrained_parameters = FxHashSet::default(); | |
192 | let mut constrained_params = FxHashSet::default(); | |
193 | let impl_trait_ref = tcx.impl_trait_ref(impl_def_id); | |
194 | ||
195 | // Unfortunately the functions in `constrained_generic_parameters` don't do | |
196 | // what we want here. We want only a list of constrained parameters while | |
197 | // the functions in `cgp` add the constrained parameters to a list of | |
198 | // unconstrained parameters. | |
199 | for (predicate, _) in impl_generic_predicates.predicates.iter() { | |
5869c6ff | 200 | if let ty::PredicateKind::Projection(proj) = predicate.kind().skip_binder() { |
3dfed10e XL |
201 | let projection_ty = proj.projection_ty; |
202 | let projected_ty = proj.ty; | |
ba9703b0 XL |
203 | |
204 | let unbound_trait_ref = projection_ty.trait_ref(tcx); | |
205 | if Some(unbound_trait_ref) == impl_trait_ref { | |
206 | continue; | |
207 | } | |
208 | ||
94222f64 | 209 | unconstrained_parameters.extend(cgp::parameters_for(tcx, &projection_ty, true)); |
ba9703b0 | 210 | |
94222f64 | 211 | for param in cgp::parameters_for(tcx, &projected_ty, false) { |
ba9703b0 XL |
212 | if !unconstrained_parameters.contains(¶m) { |
213 | constrained_params.insert(param.0); | |
214 | } | |
215 | } | |
216 | ||
94222f64 | 217 | unconstrained_parameters.extend(cgp::parameters_for(tcx, &projected_ty, true)); |
ba9703b0 XL |
218 | } |
219 | } | |
220 | ||
221 | impl_substs | |
222 | .iter() | |
223 | .enumerate() | |
224 | .filter(|&(idx, _)| !constrained_params.contains(&(idx as u32))) | |
f9f354fc | 225 | .map(|(_, arg)| arg) |
ba9703b0 XL |
226 | .collect() |
227 | } | |
228 | ||
229 | /// Check that parameters of the derived impl don't occur more than once in the | |
230 | /// equated substs of the base impl. | |
231 | /// | |
232 | /// For example forbid the following: | |
233 | /// | |
234 | /// impl<A> Tr for A { } | |
235 | /// impl<B> Tr for (B, B) { } | |
236 | /// | |
237 | /// Note that only consider the unconstrained parameters of the base impl: | |
238 | /// | |
239 | /// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { } | |
240 | /// impl<T> Tr<T> for Vec<T> { } | |
241 | /// | |
242 | /// The substs for the parent impl here are `[T, Vec<T>]`, which repeats `T`, | |
243 | /// but `S` is constrained in the parent impl, so `parent_substs` is only | |
244 | /// `[Vec<T>]`. This means we allow this impl. | |
245 | fn check_duplicate_params<'tcx>( | |
246 | tcx: TyCtxt<'tcx>, | |
247 | impl1_substs: SubstsRef<'tcx>, | |
248 | parent_substs: &Vec<GenericArg<'tcx>>, | |
249 | span: Span, | |
250 | ) { | |
94222f64 | 251 | let mut base_params = cgp::parameters_for(tcx, parent_substs, true); |
ba9703b0 XL |
252 | base_params.sort_by_key(|param| param.0); |
253 | if let (_, [duplicate, ..]) = base_params.partition_dedup() { | |
254 | let param = impl1_substs[duplicate.0 as usize]; | |
255 | tcx.sess | |
256 | .struct_span_err(span, &format!("specializing impl repeats parameter `{}`", param)) | |
257 | .emit(); | |
258 | } | |
259 | } | |
260 | ||
261 | /// Check that `'static` lifetimes are not introduced by the specializing impl. | |
262 | /// | |
263 | /// For example forbid the following: | |
264 | /// | |
265 | /// impl<A> Tr for A { } | |
266 | /// impl Tr for &'static i32 { } | |
267 | fn check_static_lifetimes<'tcx>( | |
268 | tcx: TyCtxt<'tcx>, | |
269 | parent_substs: &Vec<GenericArg<'tcx>>, | |
270 | span: Span, | |
271 | ) { | |
272 | if tcx.any_free_region_meets(parent_substs, |r| *r == ty::ReStatic) { | |
273 | tcx.sess.struct_span_err(span, "cannot specialize on `'static` lifetime").emit(); | |
274 | } | |
275 | } | |
276 | ||
277 | /// Check whether predicates on the specializing impl (`impl1`) are allowed. | |
278 | /// | |
279 | /// Each predicate `P` must be: | |
280 | /// | |
281 | /// * global (not reference any parameters) | |
282 | /// * `T: Tr` predicate where `Tr` is an always-applicable trait | |
283 | /// * on the base `impl impl2` | |
284 | /// * Currently this check is done using syntactic equality, which is | |
285 | /// conservative but generally sufficient. | |
286 | /// * a well-formed predicate of a type argument of the trait being implemented, | |
287 | /// including the `Self`-type. | |
288 | fn check_predicates<'tcx>( | |
289 | infcx: &InferCtxt<'_, 'tcx>, | |
f9f354fc | 290 | impl1_def_id: LocalDefId, |
ba9703b0 XL |
291 | impl1_substs: SubstsRef<'tcx>, |
292 | impl2_node: Node, | |
293 | impl2_substs: SubstsRef<'tcx>, | |
294 | span: Span, | |
295 | ) { | |
296 | let tcx = infcx.tcx; | |
297 | let impl1_predicates = tcx.predicates_of(impl1_def_id).instantiate(tcx, impl1_substs); | |
298 | let mut impl2_predicates = if impl2_node.is_from_trait() { | |
299 | // Always applicable traits have to be always applicable without any | |
300 | // assumptions. | |
301 | InstantiatedPredicates::empty() | |
302 | } else { | |
303 | tcx.predicates_of(impl2_node.def_id()).instantiate(tcx, impl2_substs) | |
304 | }; | |
305 | debug!( | |
306 | "check_always_applicable(\nimpl1_predicates={:?},\nimpl2_predicates={:?}\n)", | |
307 | impl1_predicates, impl2_predicates, | |
308 | ); | |
309 | ||
310 | // Since impls of always applicable traits don't get to assume anything, we | |
311 | // can also assume their supertraits apply. | |
312 | // | |
313 | // For example, we allow: | |
314 | // | |
315 | // #[rustc_specialization_trait] | |
316 | // trait AlwaysApplicable: Debug { } | |
317 | // | |
318 | // impl<T> Tr for T { } | |
319 | // impl<T: AlwaysApplicable> Tr for T { } | |
320 | // | |
321 | // Specializing on `AlwaysApplicable` allows also specializing on `Debug` | |
322 | // which is sound because we forbid impls like the following | |
323 | // | |
324 | // impl<D: Debug> AlwaysApplicable for D { } | |
f9f354fc XL |
325 | let always_applicable_traits = |
326 | impl1_predicates.predicates.iter().copied().filter(|&predicate| { | |
ba9703b0 XL |
327 | matches!( |
328 | trait_predicate_kind(tcx, predicate), | |
329 | Some(TraitSpecializationKind::AlwaysApplicable) | |
330 | ) | |
f9f354fc | 331 | }); |
ba9703b0 XL |
332 | |
333 | // Include the well-formed predicates of the type parameters of the impl. | |
f035d41b | 334 | for arg in tcx.impl_trait_ref(impl1_def_id).unwrap().substs { |
ba9703b0 XL |
335 | if let Some(obligations) = wf::obligations( |
336 | infcx, | |
337 | tcx.param_env(impl1_def_id), | |
3dfed10e | 338 | tcx.hir().local_def_id_to_hir_id(impl1_def_id), |
29967ef6 | 339 | 0, |
f035d41b | 340 | arg, |
ba9703b0 XL |
341 | span, |
342 | ) { | |
343 | impl2_predicates | |
344 | .predicates | |
345 | .extend(obligations.into_iter().map(|obligation| obligation.predicate)) | |
346 | } | |
347 | } | |
348 | impl2_predicates.predicates.extend( | |
349 | traits::elaborate_predicates(tcx, always_applicable_traits) | |
350 | .map(|obligation| obligation.predicate), | |
351 | ); | |
352 | ||
353 | for predicate in impl1_predicates.predicates { | |
354 | if !impl2_predicates.predicates.contains(&predicate) { | |
f9f354fc | 355 | check_specialization_on(tcx, predicate, span) |
ba9703b0 XL |
356 | } |
357 | } | |
358 | } | |
359 | ||
f9f354fc | 360 | fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, predicate: ty::Predicate<'tcx>, span: Span) { |
ba9703b0 | 361 | debug!("can_specialize_on(predicate = {:?})", predicate); |
5869c6ff | 362 | match predicate.kind().skip_binder() { |
ba9703b0 XL |
363 | // Global predicates are either always true or always false, so we |
364 | // are fine to specialize on. | |
94222f64 | 365 | _ if predicate.is_global(tcx) => (), |
ba9703b0 XL |
366 | // We allow specializing on explicitly marked traits with no associated |
367 | // items. | |
94222f64 XL |
368 | ty::PredicateKind::Trait(ty::TraitPredicate { |
369 | trait_ref, | |
370 | constness: ty::BoundConstness::NotConst, | |
371 | }) => { | |
ba9703b0 XL |
372 | if !matches!( |
373 | trait_predicate_kind(tcx, predicate), | |
374 | Some(TraitSpecializationKind::Marker) | |
375 | ) { | |
376 | tcx.sess | |
377 | .struct_span_err( | |
378 | span, | |
379 | &format!( | |
380 | "cannot specialize on trait `{}`", | |
94222f64 | 381 | tcx.def_path_str(trait_ref.def_id), |
ba9703b0 XL |
382 | ), |
383 | ) | |
384 | .emit() | |
385 | } | |
386 | } | |
387 | _ => tcx | |
388 | .sess | |
389 | .struct_span_err(span, &format!("cannot specialize on `{:?}`", predicate)) | |
390 | .emit(), | |
391 | } | |
392 | } | |
393 | ||
394 | fn trait_predicate_kind<'tcx>( | |
395 | tcx: TyCtxt<'tcx>, | |
f9f354fc | 396 | predicate: ty::Predicate<'tcx>, |
ba9703b0 | 397 | ) -> Option<TraitSpecializationKind> { |
5869c6ff | 398 | match predicate.kind().skip_binder() { |
94222f64 XL |
399 | ty::PredicateKind::Trait(ty::TraitPredicate { |
400 | trait_ref, | |
401 | constness: ty::BoundConstness::NotConst, | |
402 | }) => Some(tcx.trait_def(trait_ref.def_id).specialization_kind), | |
403 | ty::PredicateKind::Trait(_) | |
5869c6ff XL |
404 | | ty::PredicateKind::RegionOutlives(_) |
405 | | ty::PredicateKind::TypeOutlives(_) | |
406 | | ty::PredicateKind::Projection(_) | |
407 | | ty::PredicateKind::WellFormed(_) | |
408 | | ty::PredicateKind::Subtype(_) | |
94222f64 | 409 | | ty::PredicateKind::Coerce(_) |
5869c6ff XL |
410 | | ty::PredicateKind::ObjectSafe(_) |
411 | | ty::PredicateKind::ClosureKind(..) | |
412 | | ty::PredicateKind::ConstEvaluatable(..) | |
413 | | ty::PredicateKind::ConstEquate(..) | |
414 | | ty::PredicateKind::TypeWellFormedFromEnv(..) => None, | |
ba9703b0 XL |
415 | } |
416 | } |