]>
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; | |
71 | use rustc_hir as hir; | |
f9f354fc | 72 | use rustc_hir::def_id::{DefId, LocalDefId}; |
ba9703b0 XL |
73 | use rustc_infer::infer::outlives::env::OutlivesEnvironment; |
74 | use rustc_infer::infer::{InferCtxt, RegionckMode, TyCtxtInferExt}; | |
75 | use rustc_infer::traits::specialization_graph::Node; | |
ba9703b0 XL |
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}; | |
79 | use rustc_span::Span; | |
80 | use rustc_trait_selection::traits::{self, translate_substs, wf}; | |
81 | ||
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); | |
86 | }); | |
87 | } | |
88 | } | |
89 | ||
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); | |
93 | ||
94 | let impl2_node = trait_def.ancestors(tcx, impl1_def_id).ok()?.nth(1)?; | |
95 | ||
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. | |
100 | return None; | |
101 | } | |
102 | Some(impl2_node) | |
103 | } | |
104 | ||
105 | /// Check that `impl1` is a sound specialization | |
106 | fn check_always_applicable( | |
107 | infcx: &InferCtxt<'_, '_>, | |
108 | impl1_def_id: DefId, | |
109 | impl2_node: Node, | |
110 | span: Span, | |
111 | ) { | |
112 | if let Some((impl1_substs, impl2_substs)) = | |
113 | get_impl_substs(infcx, impl1_def_id, impl2_node, span) | |
114 | { | |
115 | let impl2_def_id = impl2_node.def_id(); | |
116 | debug!( | |
117 | "check_always_applicable(\nimpl1_def_id={:?},\nimpl2_def_id={:?},\nimpl2_substs={:?}\n)", | |
118 | impl1_def_id, impl2_def_id, impl2_substs | |
119 | ); | |
120 | ||
121 | let tcx = infcx.tcx; | |
122 | ||
123 | let parent_substs = if impl2_node.is_from_trait() { | |
124 | impl2_substs.to_vec() | |
125 | } else { | |
126 | unconstrained_parent_impl_substs(tcx, impl2_def_id, impl2_substs) | |
127 | }; | |
128 | ||
129 | check_static_lifetimes(tcx, &parent_substs, span); | |
130 | check_duplicate_params(tcx, impl1_substs, &parent_substs, span); | |
131 | ||
f9f354fc XL |
132 | check_predicates( |
133 | infcx, | |
134 | impl1_def_id.expect_local(), | |
135 | impl1_substs, | |
136 | impl2_node, | |
137 | impl2_substs, | |
138 | span, | |
139 | ); | |
ba9703b0 XL |
140 | } |
141 | } | |
142 | ||
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`. | |
146 | /// | |
147 | /// Example | |
148 | /// | |
149 | /// impl<A, B> Foo<A> for B { /* impl2 */ } | |
150 | /// impl<C> Foo<Vec<C>> for C { /* impl1 */ } | |
151 | /// | |
152 | /// Would return `S1 = [C]` and `S2 = [Vec<C>, C]`. | |
153 | fn get_impl_substs<'tcx>( | |
154 | infcx: &InferCtxt<'_, 'tcx>, | |
155 | impl1_def_id: DefId, | |
156 | impl2_node: Node, | |
157 | span: Span, | |
158 | ) -> Option<(SubstsRef<'tcx>, SubstsRef<'tcx>)> { | |
159 | let tcx = infcx.tcx; | |
160 | let param_env = tcx.param_env(impl1_def_id); | |
161 | ||
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); | |
164 | ||
165 | // Conservatively use an empty `ParamEnv`. | |
166 | let outlives_env = OutlivesEnvironment::new(ty::ParamEnv::empty()); | |
f9f354fc | 167 | infcx.resolve_regions_and_report_errors(impl1_def_id, &outlives_env, RegionckMode::default()); |
fc512014 | 168 | let impl2_substs = match infcx.fully_resolve(impl2_substs) { |
ba9703b0 XL |
169 | Ok(s) => s, |
170 | Err(_) => { | |
171 | tcx.sess.struct_span_err(span, "could not resolve substs on overridden impl").emit(); | |
172 | return None; | |
173 | } | |
174 | }; | |
175 | Some((impl1_substs, impl2_substs)) | |
176 | } | |
177 | ||
178 | /// Returns a list of all of the unconstrained subst of the given impl. | |
179 | /// | |
180 | /// For example given the impl: | |
181 | /// | |
182 | /// impl<'a, T, I> ... where &'a I: IntoIterator<Item=&'a T> | |
183 | /// | |
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>( | |
187 | tcx: TyCtxt<'tcx>, | |
188 | impl_def_id: DefId, | |
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); | |
195 | ||
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() { | |
3dfed10e XL |
201 | if let ty::PredicateAtom::Projection(proj) = predicate.skip_binders() { |
202 | let projection_ty = proj.projection_ty; | |
203 | let projected_ty = proj.ty; | |
ba9703b0 XL |
204 | |
205 | let unbound_trait_ref = projection_ty.trait_ref(tcx); | |
206 | if Some(unbound_trait_ref) == impl_trait_ref { | |
207 | continue; | |
208 | } | |
209 | ||
210 | unconstrained_parameters.extend(cgp::parameters_for(&projection_ty, true)); | |
211 | ||
212 | for param in cgp::parameters_for(&projected_ty, false) { | |
213 | if !unconstrained_parameters.contains(¶m) { | |
214 | constrained_params.insert(param.0); | |
215 | } | |
216 | } | |
217 | ||
218 | unconstrained_parameters.extend(cgp::parameters_for(&projected_ty, true)); | |
219 | } | |
220 | } | |
221 | ||
222 | impl_substs | |
223 | .iter() | |
224 | .enumerate() | |
225 | .filter(|&(idx, _)| !constrained_params.contains(&(idx as u32))) | |
f9f354fc | 226 | .map(|(_, arg)| arg) |
ba9703b0 XL |
227 | .collect() |
228 | } | |
229 | ||
230 | /// Check that parameters of the derived impl don't occur more than once in the | |
231 | /// equated substs of the base impl. | |
232 | /// | |
233 | /// For example forbid the following: | |
234 | /// | |
235 | /// impl<A> Tr for A { } | |
236 | /// impl<B> Tr for (B, B) { } | |
237 | /// | |
238 | /// Note that only consider the unconstrained parameters of the base impl: | |
239 | /// | |
240 | /// impl<S, I: IntoIterator<Item = S>> Tr<S> for I { } | |
241 | /// impl<T> Tr<T> for Vec<T> { } | |
242 | /// | |
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>( | |
247 | tcx: TyCtxt<'tcx>, | |
248 | impl1_substs: SubstsRef<'tcx>, | |
249 | parent_substs: &Vec<GenericArg<'tcx>>, | |
250 | span: Span, | |
251 | ) { | |
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]; | |
256 | tcx.sess | |
257 | .struct_span_err(span, &format!("specializing impl repeats parameter `{}`", param)) | |
258 | .emit(); | |
259 | } | |
260 | } | |
261 | ||
262 | /// Check that `'static` lifetimes are not introduced by the specializing impl. | |
263 | /// | |
264 | /// For example forbid the following: | |
265 | /// | |
266 | /// impl<A> Tr for A { } | |
267 | /// impl Tr for &'static i32 { } | |
268 | fn check_static_lifetimes<'tcx>( | |
269 | tcx: TyCtxt<'tcx>, | |
270 | parent_substs: &Vec<GenericArg<'tcx>>, | |
271 | span: Span, | |
272 | ) { | |
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(); | |
275 | } | |
276 | } | |
277 | ||
278 | /// Check whether predicates on the specializing impl (`impl1`) are allowed. | |
279 | /// | |
280 | /// Each predicate `P` must be: | |
281 | /// | |
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>, | |
f9f354fc | 291 | impl1_def_id: LocalDefId, |
ba9703b0 XL |
292 | impl1_substs: SubstsRef<'tcx>, |
293 | impl2_node: Node, | |
294 | impl2_substs: SubstsRef<'tcx>, | |
295 | span: Span, | |
296 | ) { | |
297 | let tcx = infcx.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 | |
301 | // assumptions. | |
302 | InstantiatedPredicates::empty() | |
303 | } else { | |
304 | tcx.predicates_of(impl2_node.def_id()).instantiate(tcx, impl2_substs) | |
305 | }; | |
306 | debug!( | |
307 | "check_always_applicable(\nimpl1_predicates={:?},\nimpl2_predicates={:?}\n)", | |
308 | impl1_predicates, impl2_predicates, | |
309 | ); | |
310 | ||
311 | // Since impls of always applicable traits don't get to assume anything, we | |
312 | // can also assume their supertraits apply. | |
313 | // | |
314 | // For example, we allow: | |
315 | // | |
316 | // #[rustc_specialization_trait] | |
317 | // trait AlwaysApplicable: Debug { } | |
318 | // | |
319 | // impl<T> Tr for T { } | |
320 | // impl<T: AlwaysApplicable> Tr for T { } | |
321 | // | |
322 | // Specializing on `AlwaysApplicable` allows also specializing on `Debug` | |
323 | // which is sound because we forbid impls like the following | |
324 | // | |
325 | // impl<D: Debug> AlwaysApplicable for D { } | |
f9f354fc XL |
326 | let always_applicable_traits = |
327 | impl1_predicates.predicates.iter().copied().filter(|&predicate| { | |
ba9703b0 XL |
328 | matches!( |
329 | trait_predicate_kind(tcx, predicate), | |
330 | Some(TraitSpecializationKind::AlwaysApplicable) | |
331 | ) | |
f9f354fc | 332 | }); |
ba9703b0 XL |
333 | |
334 | // Include the well-formed predicates of the type parameters of the impl. | |
f035d41b | 335 | for arg in tcx.impl_trait_ref(impl1_def_id).unwrap().substs { |
ba9703b0 XL |
336 | if let Some(obligations) = wf::obligations( |
337 | infcx, | |
338 | tcx.param_env(impl1_def_id), | |
3dfed10e | 339 | tcx.hir().local_def_id_to_hir_id(impl1_def_id), |
29967ef6 | 340 | 0, |
f035d41b | 341 | arg, |
ba9703b0 XL |
342 | span, |
343 | ) { | |
344 | impl2_predicates | |
345 | .predicates | |
346 | .extend(obligations.into_iter().map(|obligation| obligation.predicate)) | |
347 | } | |
348 | } | |
349 | impl2_predicates.predicates.extend( | |
350 | traits::elaborate_predicates(tcx, always_applicable_traits) | |
351 | .map(|obligation| obligation.predicate), | |
352 | ); | |
353 | ||
354 | for predicate in impl1_predicates.predicates { | |
355 | if !impl2_predicates.predicates.contains(&predicate) { | |
f9f354fc | 356 | check_specialization_on(tcx, predicate, span) |
ba9703b0 XL |
357 | } |
358 | } | |
359 | } | |
360 | ||
f9f354fc | 361 | fn check_specialization_on<'tcx>(tcx: TyCtxt<'tcx>, predicate: ty::Predicate<'tcx>, span: Span) { |
ba9703b0 | 362 | debug!("can_specialize_on(predicate = {:?})", predicate); |
3dfed10e | 363 | match predicate.skip_binders() { |
ba9703b0 XL |
364 | // Global predicates are either always true or always false, so we |
365 | // are fine to specialize on. | |
366 | _ if predicate.is_global() => (), | |
367 | // We allow specializing on explicitly marked traits with no associated | |
368 | // items. | |
3dfed10e | 369 | ty::PredicateAtom::Trait(pred, hir::Constness::NotConst) => { |
ba9703b0 XL |
370 | if !matches!( |
371 | trait_predicate_kind(tcx, predicate), | |
372 | Some(TraitSpecializationKind::Marker) | |
373 | ) { | |
374 | tcx.sess | |
375 | .struct_span_err( | |
376 | span, | |
377 | &format!( | |
378 | "cannot specialize on trait `{}`", | |
379 | tcx.def_path_str(pred.def_id()), | |
380 | ), | |
381 | ) | |
382 | .emit() | |
383 | } | |
384 | } | |
385 | _ => tcx | |
386 | .sess | |
387 | .struct_span_err(span, &format!("cannot specialize on `{:?}`", predicate)) | |
388 | .emit(), | |
389 | } | |
390 | } | |
391 | ||
392 | fn trait_predicate_kind<'tcx>( | |
393 | tcx: TyCtxt<'tcx>, | |
f9f354fc | 394 | predicate: ty::Predicate<'tcx>, |
ba9703b0 | 395 | ) -> Option<TraitSpecializationKind> { |
3dfed10e XL |
396 | match predicate.skip_binders() { |
397 | ty::PredicateAtom::Trait(pred, hir::Constness::NotConst) => { | |
ba9703b0 XL |
398 | Some(tcx.trait_def(pred.def_id()).specialization_kind) |
399 | } | |
3dfed10e XL |
400 | ty::PredicateAtom::Trait(_, hir::Constness::Const) |
401 | | ty::PredicateAtom::RegionOutlives(_) | |
402 | | ty::PredicateAtom::TypeOutlives(_) | |
403 | | ty::PredicateAtom::Projection(_) | |
404 | | ty::PredicateAtom::WellFormed(_) | |
405 | | ty::PredicateAtom::Subtype(_) | |
406 | | ty::PredicateAtom::ObjectSafe(_) | |
407 | | ty::PredicateAtom::ClosureKind(..) | |
408 | | ty::PredicateAtom::ConstEvaluatable(..) | |
1b1a35ee XL |
409 | | ty::PredicateAtom::ConstEquate(..) |
410 | | ty::PredicateAtom::TypeWellFormedFromEnv(..) => None, | |
ba9703b0 XL |
411 | } |
412 | } |