]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
1 | //! Polymorphization Analysis |
2 | //! ========================= | |
3 | //! | |
4 | //! This module implements an analysis of functions, methods and closures to determine which | |
5 | //! generic parameters are unused (and eventually, in what ways generic parameters are used - only | |
6 | //! for their size, offset of a field, etc.). | |
7 | ||
5869c6ff | 8 | use rustc_hir::{def::DefKind, def_id::DefId, ConstContext}; |
3dfed10e XL |
9 | use rustc_index::bit_set::FiniteBitSet; |
10 | use rustc_middle::mir::{ | |
11 | visit::{TyContext, Visitor}, | |
12 | Local, LocalDecl, Location, | |
13 | }; | |
14 | use rustc_middle::ty::{ | |
15 | self, | |
16 | fold::{TypeFoldable, TypeVisitor}, | |
17 | query::Providers, | |
18 | subst::SubstsRef, | |
19 | Const, Ty, TyCtxt, | |
20 | }; | |
21 | use rustc_span::symbol::sym; | |
22 | use std::convert::TryInto; | |
29967ef6 | 23 | use std::ops::ControlFlow; |
3dfed10e XL |
24 | |
25 | /// Provide implementations of queries relating to polymorphization analysis. | |
26 | pub fn provide(providers: &mut Providers) { | |
27 | providers.unused_generic_params = unused_generic_params; | |
28 | } | |
29 | ||
30 | /// Determine which generic parameters are used by the function/method/closure represented by | |
31 | /// `def_id`. Returns a bitset where bits representing unused parameters are set (`is_empty` | |
32 | /// indicates all parameters are used). | |
6a06907d | 33 | #[instrument(skip(tcx))] |
3dfed10e | 34 | fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> { |
3dfed10e XL |
35 | if !tcx.sess.opts.debugging_opts.polymorphize { |
36 | // If polymorphization disabled, then all parameters are used. | |
37 | return FiniteBitSet::new_empty(); | |
38 | } | |
39 | ||
40 | // Polymorphization results are stored in cross-crate metadata only when there are unused | |
41 | // parameters, so assume that non-local items must have only used parameters (else this query | |
42 | // would not be invoked, and the cross-crate metadata used instead). | |
43 | if !def_id.is_local() { | |
44 | return FiniteBitSet::new_empty(); | |
45 | } | |
46 | ||
47 | let generics = tcx.generics_of(def_id); | |
6a06907d | 48 | debug!(?generics); |
3dfed10e XL |
49 | |
50 | // Exit early when there are no parameters to be unused. | |
51 | if generics.count() == 0 { | |
52 | return FiniteBitSet::new_empty(); | |
53 | } | |
54 | ||
55 | // Exit early when there is no MIR available. | |
5869c6ff XL |
56 | let context = tcx.hir().body_const_context(def_id.expect_local()); |
57 | match context { | |
58 | Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => { | |
6a06907d | 59 | debug!("no mir available"); |
5869c6ff XL |
60 | return FiniteBitSet::new_empty(); |
61 | } | |
62 | Some(_) if !tcx.is_ctfe_mir_available(def_id) => { | |
6a06907d | 63 | debug!("no ctfe mir available"); |
5869c6ff XL |
64 | return FiniteBitSet::new_empty(); |
65 | } | |
66 | _ => {} | |
3dfed10e XL |
67 | } |
68 | ||
69 | // Create a bitset with N rightmost ones for each parameter. | |
70 | let generics_count: u32 = | |
71 | generics.count().try_into().expect("more generic parameters than can fit into a `u32`"); | |
72 | let mut unused_parameters = FiniteBitSet::<u32>::new_empty(); | |
73 | unused_parameters.set_range(0..generics_count); | |
6a06907d | 74 | debug!(?unused_parameters, "(start)"); |
3dfed10e | 75 | mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters); |
6a06907d | 76 | debug!(?unused_parameters, "(after default)"); |
3dfed10e XL |
77 | |
78 | // Visit MIR and accumululate used generic parameters. | |
5869c6ff XL |
79 | let body = match context { |
80 | // Const functions are actually called and should thus be considered for polymorphization | |
81 | // via their runtime MIR | |
82 | Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id), | |
83 | Some(_) => tcx.mir_for_ctfe(def_id), | |
84 | }; | |
3dfed10e XL |
85 | let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters }; |
86 | vis.visit_body(body); | |
6a06907d | 87 | debug!(?unused_parameters, "(after visitor)"); |
3dfed10e XL |
88 | |
89 | mark_used_by_predicates(tcx, def_id, &mut unused_parameters); | |
6a06907d | 90 | debug!(?unused_parameters, "(end)"); |
3dfed10e XL |
91 | |
92 | // Emit errors for debugging and testing if enabled. | |
93 | if !unused_parameters.is_empty() { | |
94 | emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters); | |
95 | } | |
96 | ||
97 | unused_parameters | |
98 | } | |
99 | ||
100 | /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy | |
101 | /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should | |
102 | /// be `true` if the item that `unused_generic_params` was invoked on is a closure. | |
6a06907d | 103 | #[instrument(skip(tcx, def_id, generics, unused_parameters))] |
3dfed10e XL |
104 | fn mark_used_by_default_parameters<'tcx>( |
105 | tcx: TyCtxt<'tcx>, | |
106 | def_id: DefId, | |
107 | generics: &'tcx ty::Generics, | |
108 | unused_parameters: &mut FiniteBitSet<u32>, | |
109 | ) { | |
6a06907d XL |
110 | match tcx.def_kind(def_id) { |
111 | DefKind::Closure | DefKind::Generator => { | |
112 | for param in &generics.params { | |
113 | debug!(?param, "(closure/gen)"); | |
3dfed10e XL |
114 | unused_parameters.clear(param.index); |
115 | } | |
116 | } | |
6a06907d XL |
117 | DefKind::Mod |
118 | | DefKind::Struct | |
119 | | DefKind::Union | |
120 | | DefKind::Enum | |
121 | | DefKind::Variant | |
122 | | DefKind::Trait | |
123 | | DefKind::TyAlias | |
124 | | DefKind::ForeignTy | |
125 | | DefKind::TraitAlias | |
126 | | DefKind::AssocTy | |
127 | | DefKind::TyParam | |
128 | | DefKind::Fn | |
129 | | DefKind::Const | |
130 | | DefKind::ConstParam | |
131 | | DefKind::Static | |
132 | | DefKind::Ctor(_, _) | |
133 | | DefKind::AssocFn | |
134 | | DefKind::AssocConst | |
135 | | DefKind::Macro(_) | |
136 | | DefKind::ExternCrate | |
137 | | DefKind::Use | |
138 | | DefKind::ForeignMod | |
139 | | DefKind::AnonConst | |
140 | | DefKind::OpaqueTy | |
141 | | DefKind::Field | |
142 | | DefKind::LifetimeParam | |
143 | | DefKind::GlobalAsm | |
144 | | DefKind::Impl => { | |
145 | for param in &generics.params { | |
146 | debug!(?param, "(other)"); | |
147 | if let ty::GenericParamDefKind::Lifetime = param.kind { | |
148 | unused_parameters.clear(param.index); | |
149 | } | |
150 | } | |
151 | } | |
3dfed10e XL |
152 | } |
153 | ||
154 | if let Some(parent) = generics.parent { | |
155 | mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters); | |
156 | } | |
157 | } | |
158 | ||
159 | /// Search the predicates on used generic parameters for any unused generic parameters, and mark | |
160 | /// those as used. | |
6a06907d | 161 | #[instrument(skip(tcx, def_id))] |
3dfed10e XL |
162 | fn mark_used_by_predicates<'tcx>( |
163 | tcx: TyCtxt<'tcx>, | |
164 | def_id: DefId, | |
165 | unused_parameters: &mut FiniteBitSet<u32>, | |
166 | ) { | |
167 | let def_id = tcx.closure_base_def_id(def_id); | |
168 | let predicates = tcx.explicit_predicates_of(def_id); | |
3dfed10e XL |
169 | |
170 | let mut current_unused_parameters = FiniteBitSet::new_empty(); | |
171 | // Run to a fixed point to support `where T: Trait<U>, U: Trait<V>`, starting with an empty | |
172 | // bit set so that this is skipped if all parameters are already used. | |
173 | while current_unused_parameters != *unused_parameters { | |
6a06907d | 174 | debug!(?current_unused_parameters, ?unused_parameters); |
3dfed10e XL |
175 | current_unused_parameters = *unused_parameters; |
176 | ||
177 | for (predicate, _) in predicates.predicates { | |
178 | // Consider all generic params in a predicate as used if any other parameter in the | |
179 | // predicate is used. | |
180 | let any_param_used = { | |
181 | let mut vis = HasUsedGenericParams { unused_parameters }; | |
29967ef6 | 182 | predicate.visit_with(&mut vis).is_break() |
3dfed10e XL |
183 | }; |
184 | ||
185 | if any_param_used { | |
186 | let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters }; | |
187 | predicate.visit_with(&mut vis); | |
188 | } | |
189 | } | |
190 | } | |
191 | ||
192 | if let Some(parent) = predicates.parent { | |
193 | mark_used_by_predicates(tcx, parent, unused_parameters); | |
194 | } | |
195 | } | |
196 | ||
197 | /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic | |
198 | /// parameter which was unused. | |
6a06907d | 199 | #[instrument(skip(tcx, generics))] |
3dfed10e XL |
200 | fn emit_unused_generic_params_error<'tcx>( |
201 | tcx: TyCtxt<'tcx>, | |
202 | def_id: DefId, | |
203 | generics: &'tcx ty::Generics, | |
204 | unused_parameters: &FiniteBitSet<u32>, | |
205 | ) { | |
3dfed10e XL |
206 | let base_def_id = tcx.closure_base_def_id(def_id); |
207 | if !tcx | |
208 | .get_attrs(base_def_id) | |
209 | .iter() | |
210 | .any(|a| tcx.sess.check_name(a, sym::rustc_polymorphize_error)) | |
211 | { | |
212 | return; | |
213 | } | |
214 | ||
3dfed10e XL |
215 | let fn_span = match tcx.opt_item_name(def_id) { |
216 | Some(ident) => ident.span, | |
217 | _ => tcx.def_span(def_id), | |
218 | }; | |
219 | ||
220 | let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters"); | |
221 | ||
222 | let mut next_generics = Some(generics); | |
223 | while let Some(generics) = next_generics { | |
224 | for param in &generics.params { | |
225 | if unused_parameters.contains(param.index).unwrap_or(false) { | |
6a06907d | 226 | debug!(?param); |
3dfed10e XL |
227 | let def_span = tcx.def_span(param.def_id); |
228 | err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name)); | |
229 | } | |
230 | } | |
231 | ||
232 | next_generics = generics.parent.map(|did| tcx.generics_of(did)); | |
233 | } | |
234 | ||
235 | err.emit(); | |
236 | } | |
237 | ||
238 | /// Visitor used to aggregate generic parameter uses. | |
239 | struct MarkUsedGenericParams<'a, 'tcx> { | |
240 | tcx: TyCtxt<'tcx>, | |
241 | def_id: DefId, | |
242 | unused_parameters: &'a mut FiniteBitSet<u32>, | |
243 | } | |
244 | ||
245 | impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> { | |
246 | /// Invoke `unused_generic_params` on a body contained within the current item (e.g. | |
247 | /// a closure, generator or constant). | |
6a06907d | 248 | #[instrument(skip(self, def_id, substs))] |
3dfed10e XL |
249 | fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) { |
250 | let unused = self.tcx.unused_generic_params(def_id); | |
6a06907d | 251 | debug!(?self.unused_parameters, ?unused); |
3dfed10e XL |
252 | for (i, arg) in substs.iter().enumerate() { |
253 | let i = i.try_into().unwrap(); | |
254 | if !unused.contains(i).unwrap_or(false) { | |
255 | arg.visit_with(self); | |
256 | } | |
257 | } | |
6a06907d | 258 | debug!(?self.unused_parameters); |
3dfed10e XL |
259 | } |
260 | } | |
261 | ||
262 | impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { | |
6a06907d | 263 | #[instrument(skip(self, local))] |
3dfed10e | 264 | fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) { |
3dfed10e XL |
265 | if local == Local::from_usize(1) { |
266 | let def_kind = self.tcx.def_kind(self.def_id); | |
267 | if matches!(def_kind, DefKind::Closure | DefKind::Generator) { | |
268 | // Skip visiting the closure/generator that is currently being processed. This only | |
269 | // happens because the first argument to the closure is a reference to itself and | |
270 | // that will call `visit_substs`, resulting in each generic parameter captured being | |
271 | // considered used by default. | |
6a06907d | 272 | debug!("skipping closure substs"); |
3dfed10e XL |
273 | return; |
274 | } | |
275 | } | |
276 | ||
277 | self.super_local_decl(local, local_decl); | |
278 | } | |
279 | ||
280 | fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) { | |
281 | c.visit_with(self); | |
282 | } | |
283 | ||
284 | fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) { | |
285 | ty.visit_with(self); | |
286 | } | |
287 | } | |
288 | ||
289 | impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { | |
6a06907d | 290 | #[instrument(skip(self))] |
fc512014 | 291 | fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
3dfed10e | 292 | if !c.has_param_types_or_consts() { |
29967ef6 | 293 | return ControlFlow::CONTINUE; |
3dfed10e XL |
294 | } |
295 | ||
296 | match c.val { | |
297 | ty::ConstKind::Param(param) => { | |
6a06907d | 298 | debug!(?param); |
3dfed10e | 299 | self.unused_parameters.clear(param.index); |
29967ef6 | 300 | ControlFlow::CONTINUE |
3dfed10e XL |
301 | } |
302 | ty::ConstKind::Unevaluated(def, _, Some(p)) | |
303 | // Avoid considering `T` unused when constants are of the form: | |
304 | // `<Self as Foo<T>>::foo::promoted[p]` | |
305 | if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self => | |
306 | { | |
307 | // If there is a promoted, don't look at the substs - since it will always contain | |
308 | // the generic parameters, instead, traverse the promoted MIR. | |
309 | let promoted = self.tcx.promoted_mir(def.did); | |
310 | self.visit_body(&promoted[p]); | |
29967ef6 | 311 | ControlFlow::CONTINUE |
3dfed10e XL |
312 | } |
313 | ty::ConstKind::Unevaluated(def, unevaluated_substs, None) | |
314 | if self.tcx.def_kind(def.did) == DefKind::AnonConst => | |
315 | { | |
316 | self.visit_child_body(def.did, unevaluated_substs); | |
29967ef6 | 317 | ControlFlow::CONTINUE |
3dfed10e XL |
318 | } |
319 | _ => c.super_visit_with(self), | |
320 | } | |
321 | } | |
322 | ||
6a06907d | 323 | #[instrument(skip(self))] |
fc512014 | 324 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
3dfed10e | 325 | if !ty.has_param_types_or_consts() { |
29967ef6 | 326 | return ControlFlow::CONTINUE; |
3dfed10e XL |
327 | } |
328 | ||
1b1a35ee | 329 | match *ty.kind() { |
3dfed10e | 330 | ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => { |
6a06907d | 331 | debug!(?def_id); |
3dfed10e XL |
332 | // Avoid cycle errors with generators. |
333 | if def_id == self.def_id { | |
29967ef6 | 334 | return ControlFlow::CONTINUE; |
3dfed10e XL |
335 | } |
336 | ||
337 | // Consider any generic parameters used by any closures/generators as used in the | |
338 | // parent. | |
339 | self.visit_child_body(def_id, substs); | |
29967ef6 | 340 | ControlFlow::CONTINUE |
3dfed10e XL |
341 | } |
342 | ty::Param(param) => { | |
6a06907d | 343 | debug!(?param); |
3dfed10e | 344 | self.unused_parameters.clear(param.index); |
29967ef6 | 345 | ControlFlow::CONTINUE |
3dfed10e XL |
346 | } |
347 | _ => ty.super_visit_with(self), | |
348 | } | |
349 | } | |
350 | } | |
351 | ||
352 | /// Visitor used to check if a generic parameter is used. | |
353 | struct HasUsedGenericParams<'a> { | |
354 | unused_parameters: &'a FiniteBitSet<u32>, | |
355 | } | |
356 | ||
357 | impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> { | |
fc512014 XL |
358 | type BreakTy = (); |
359 | ||
6a06907d | 360 | #[instrument(skip(self))] |
fc512014 | 361 | fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
3dfed10e | 362 | if !c.has_param_types_or_consts() { |
29967ef6 | 363 | return ControlFlow::CONTINUE; |
3dfed10e XL |
364 | } |
365 | ||
366 | match c.val { | |
367 | ty::ConstKind::Param(param) => { | |
29967ef6 XL |
368 | if self.unused_parameters.contains(param.index).unwrap_or(false) { |
369 | ControlFlow::CONTINUE | |
370 | } else { | |
371 | ControlFlow::BREAK | |
372 | } | |
3dfed10e XL |
373 | } |
374 | _ => c.super_visit_with(self), | |
375 | } | |
376 | } | |
377 | ||
6a06907d | 378 | #[instrument(skip(self))] |
fc512014 | 379 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
3dfed10e | 380 | if !ty.has_param_types_or_consts() { |
29967ef6 | 381 | return ControlFlow::CONTINUE; |
3dfed10e XL |
382 | } |
383 | ||
1b1a35ee | 384 | match ty.kind() { |
29967ef6 XL |
385 | ty::Param(param) => { |
386 | if self.unused_parameters.contains(param.index).unwrap_or(false) { | |
387 | ControlFlow::CONTINUE | |
388 | } else { | |
389 | ControlFlow::BREAK | |
390 | } | |
391 | } | |
3dfed10e XL |
392 | _ => ty.super_visit_with(self), |
393 | } | |
394 | } | |
395 | } |