]>
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 | ||
8 | use rustc_hir::{def::DefKind, def_id::DefId}; | |
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; | |
23 | ||
24 | /// Provide implementations of queries relating to polymorphization analysis. | |
25 | pub fn provide(providers: &mut Providers) { | |
26 | providers.unused_generic_params = unused_generic_params; | |
27 | } | |
28 | ||
29 | /// Determine which generic parameters are used by the function/method/closure represented by | |
30 | /// `def_id`. Returns a bitset where bits representing unused parameters are set (`is_empty` | |
31 | /// indicates all parameters are used). | |
32 | fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> { | |
33 | debug!("unused_generic_params({:?})", def_id); | |
34 | ||
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); | |
48 | debug!("unused_generic_params: generics={:?}", generics); | |
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. | |
56 | if !tcx.is_mir_available(def_id) { | |
57 | debug!("unused_generic_params: (no mir available) def_id={:?}", def_id); | |
58 | return FiniteBitSet::new_empty(); | |
59 | } | |
60 | ||
61 | // Create a bitset with N rightmost ones for each parameter. | |
62 | let generics_count: u32 = | |
63 | generics.count().try_into().expect("more generic parameters than can fit into a `u32`"); | |
64 | let mut unused_parameters = FiniteBitSet::<u32>::new_empty(); | |
65 | unused_parameters.set_range(0..generics_count); | |
66 | debug!("unused_generic_params: (start) unused_parameters={:?}", unused_parameters); | |
67 | mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters); | |
68 | debug!("unused_generic_params: (after default) unused_parameters={:?}", unused_parameters); | |
69 | ||
70 | // Visit MIR and accumululate used generic parameters. | |
71 | let body = tcx.optimized_mir(def_id); | |
72 | let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters }; | |
73 | vis.visit_body(body); | |
74 | debug!("unused_generic_params: (after visitor) unused_parameters={:?}", unused_parameters); | |
75 | ||
76 | mark_used_by_predicates(tcx, def_id, &mut unused_parameters); | |
77 | debug!("unused_generic_params: (end) unused_parameters={:?}", unused_parameters); | |
78 | ||
79 | // Emit errors for debugging and testing if enabled. | |
80 | if !unused_parameters.is_empty() { | |
81 | emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters); | |
82 | } | |
83 | ||
84 | unused_parameters | |
85 | } | |
86 | ||
87 | /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy | |
88 | /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should | |
89 | /// be `true` if the item that `unused_generic_params` was invoked on is a closure. | |
90 | fn mark_used_by_default_parameters<'tcx>( | |
91 | tcx: TyCtxt<'tcx>, | |
92 | def_id: DefId, | |
93 | generics: &'tcx ty::Generics, | |
94 | unused_parameters: &mut FiniteBitSet<u32>, | |
95 | ) { | |
96 | if !tcx.is_trait(def_id) && (tcx.is_closure(def_id) || tcx.type_of(def_id).is_generator()) { | |
97 | for param in &generics.params { | |
98 | debug!("mark_used_by_default_parameters: (closure/gen) param={:?}", param); | |
99 | unused_parameters.clear(param.index); | |
100 | } | |
101 | } else { | |
102 | for param in &generics.params { | |
103 | debug!("mark_used_by_default_parameters: (other) param={:?}", param); | |
104 | if let ty::GenericParamDefKind::Lifetime = param.kind { | |
105 | unused_parameters.clear(param.index); | |
106 | } | |
107 | } | |
108 | } | |
109 | ||
110 | if let Some(parent) = generics.parent { | |
111 | mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters); | |
112 | } | |
113 | } | |
114 | ||
115 | /// Search the predicates on used generic parameters for any unused generic parameters, and mark | |
116 | /// those as used. | |
117 | fn mark_used_by_predicates<'tcx>( | |
118 | tcx: TyCtxt<'tcx>, | |
119 | def_id: DefId, | |
120 | unused_parameters: &mut FiniteBitSet<u32>, | |
121 | ) { | |
122 | let def_id = tcx.closure_base_def_id(def_id); | |
123 | let predicates = tcx.explicit_predicates_of(def_id); | |
124 | debug!("mark_used_by_predicates: predicates_of={:?}", predicates); | |
125 | ||
126 | let mut current_unused_parameters = FiniteBitSet::new_empty(); | |
127 | // Run to a fixed point to support `where T: Trait<U>, U: Trait<V>`, starting with an empty | |
128 | // bit set so that this is skipped if all parameters are already used. | |
129 | while current_unused_parameters != *unused_parameters { | |
130 | debug!( | |
131 | "mark_used_by_predicates: current_unused_parameters={:?} = unused_parameters={:?}", | |
132 | current_unused_parameters, unused_parameters | |
133 | ); | |
134 | current_unused_parameters = *unused_parameters; | |
135 | ||
136 | for (predicate, _) in predicates.predicates { | |
137 | // Consider all generic params in a predicate as used if any other parameter in the | |
138 | // predicate is used. | |
139 | let any_param_used = { | |
140 | let mut vis = HasUsedGenericParams { unused_parameters }; | |
141 | predicate.visit_with(&mut vis) | |
142 | }; | |
143 | ||
144 | if any_param_used { | |
145 | let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters }; | |
146 | predicate.visit_with(&mut vis); | |
147 | } | |
148 | } | |
149 | } | |
150 | ||
151 | if let Some(parent) = predicates.parent { | |
152 | mark_used_by_predicates(tcx, parent, unused_parameters); | |
153 | } | |
154 | } | |
155 | ||
156 | /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic | |
157 | /// parameter which was unused. | |
158 | fn emit_unused_generic_params_error<'tcx>( | |
159 | tcx: TyCtxt<'tcx>, | |
160 | def_id: DefId, | |
161 | generics: &'tcx ty::Generics, | |
162 | unused_parameters: &FiniteBitSet<u32>, | |
163 | ) { | |
164 | debug!("emit_unused_generic_params_error: def_id={:?}", def_id); | |
165 | let base_def_id = tcx.closure_base_def_id(def_id); | |
166 | if !tcx | |
167 | .get_attrs(base_def_id) | |
168 | .iter() | |
169 | .any(|a| tcx.sess.check_name(a, sym::rustc_polymorphize_error)) | |
170 | { | |
171 | return; | |
172 | } | |
173 | ||
174 | debug!("emit_unused_generic_params_error: unused_parameters={:?}", unused_parameters); | |
175 | let fn_span = match tcx.opt_item_name(def_id) { | |
176 | Some(ident) => ident.span, | |
177 | _ => tcx.def_span(def_id), | |
178 | }; | |
179 | ||
180 | let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters"); | |
181 | ||
182 | let mut next_generics = Some(generics); | |
183 | while let Some(generics) = next_generics { | |
184 | for param in &generics.params { | |
185 | if unused_parameters.contains(param.index).unwrap_or(false) { | |
186 | debug!("emit_unused_generic_params_error: param={:?}", param); | |
187 | let def_span = tcx.def_span(param.def_id); | |
188 | err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name)); | |
189 | } | |
190 | } | |
191 | ||
192 | next_generics = generics.parent.map(|did| tcx.generics_of(did)); | |
193 | } | |
194 | ||
195 | err.emit(); | |
196 | } | |
197 | ||
198 | /// Visitor used to aggregate generic parameter uses. | |
199 | struct MarkUsedGenericParams<'a, 'tcx> { | |
200 | tcx: TyCtxt<'tcx>, | |
201 | def_id: DefId, | |
202 | unused_parameters: &'a mut FiniteBitSet<u32>, | |
203 | } | |
204 | ||
205 | impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> { | |
206 | /// Invoke `unused_generic_params` on a body contained within the current item (e.g. | |
207 | /// a closure, generator or constant). | |
208 | fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) { | |
209 | let unused = self.tcx.unused_generic_params(def_id); | |
210 | debug!( | |
211 | "visit_child_body: unused_parameters={:?} unused={:?}", | |
212 | self.unused_parameters, unused | |
213 | ); | |
214 | for (i, arg) in substs.iter().enumerate() { | |
215 | let i = i.try_into().unwrap(); | |
216 | if !unused.contains(i).unwrap_or(false) { | |
217 | arg.visit_with(self); | |
218 | } | |
219 | } | |
220 | debug!("visit_child_body: unused_parameters={:?}", self.unused_parameters); | |
221 | } | |
222 | } | |
223 | ||
224 | impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { | |
225 | fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) { | |
226 | debug!("visit_local_decl: local_decl={:?}", local_decl); | |
227 | if local == Local::from_usize(1) { | |
228 | let def_kind = self.tcx.def_kind(self.def_id); | |
229 | if matches!(def_kind, DefKind::Closure | DefKind::Generator) { | |
230 | // Skip visiting the closure/generator that is currently being processed. This only | |
231 | // happens because the first argument to the closure is a reference to itself and | |
232 | // that will call `visit_substs`, resulting in each generic parameter captured being | |
233 | // considered used by default. | |
234 | debug!("visit_local_decl: skipping closure substs"); | |
235 | return; | |
236 | } | |
237 | } | |
238 | ||
239 | self.super_local_decl(local, local_decl); | |
240 | } | |
241 | ||
242 | fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) { | |
243 | c.visit_with(self); | |
244 | } | |
245 | ||
246 | fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) { | |
247 | ty.visit_with(self); | |
248 | } | |
249 | } | |
250 | ||
251 | impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> { | |
252 | fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool { | |
253 | debug!("visit_const: c={:?}", c); | |
254 | if !c.has_param_types_or_consts() { | |
255 | return false; | |
256 | } | |
257 | ||
258 | match c.val { | |
259 | ty::ConstKind::Param(param) => { | |
260 | debug!("visit_const: param={:?}", param); | |
261 | self.unused_parameters.clear(param.index); | |
262 | false | |
263 | } | |
264 | ty::ConstKind::Unevaluated(def, _, Some(p)) | |
265 | // Avoid considering `T` unused when constants are of the form: | |
266 | // `<Self as Foo<T>>::foo::promoted[p]` | |
267 | if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self => | |
268 | { | |
269 | // If there is a promoted, don't look at the substs - since it will always contain | |
270 | // the generic parameters, instead, traverse the promoted MIR. | |
271 | let promoted = self.tcx.promoted_mir(def.did); | |
272 | self.visit_body(&promoted[p]); | |
273 | false | |
274 | } | |
275 | ty::ConstKind::Unevaluated(def, unevaluated_substs, None) | |
276 | if self.tcx.def_kind(def.did) == DefKind::AnonConst => | |
277 | { | |
278 | self.visit_child_body(def.did, unevaluated_substs); | |
279 | false | |
280 | } | |
281 | _ => c.super_visit_with(self), | |
282 | } | |
283 | } | |
284 | ||
285 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool { | |
286 | debug!("visit_ty: ty={:?}", ty); | |
287 | if !ty.has_param_types_or_consts() { | |
288 | return false; | |
289 | } | |
290 | ||
291 | match ty.kind { | |
292 | ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => { | |
293 | debug!("visit_ty: def_id={:?}", def_id); | |
294 | // Avoid cycle errors with generators. | |
295 | if def_id == self.def_id { | |
296 | return false; | |
297 | } | |
298 | ||
299 | // Consider any generic parameters used by any closures/generators as used in the | |
300 | // parent. | |
301 | self.visit_child_body(def_id, substs); | |
302 | false | |
303 | } | |
304 | ty::Param(param) => { | |
305 | debug!("visit_ty: param={:?}", param); | |
306 | self.unused_parameters.clear(param.index); | |
307 | false | |
308 | } | |
309 | _ => ty.super_visit_with(self), | |
310 | } | |
311 | } | |
312 | } | |
313 | ||
314 | /// Visitor used to check if a generic parameter is used. | |
315 | struct HasUsedGenericParams<'a> { | |
316 | unused_parameters: &'a FiniteBitSet<u32>, | |
317 | } | |
318 | ||
319 | impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> { | |
320 | fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool { | |
321 | debug!("visit_const: c={:?}", c); | |
322 | if !c.has_param_types_or_consts() { | |
323 | return false; | |
324 | } | |
325 | ||
326 | match c.val { | |
327 | ty::ConstKind::Param(param) => { | |
328 | !self.unused_parameters.contains(param.index).unwrap_or(false) | |
329 | } | |
330 | _ => c.super_visit_with(self), | |
331 | } | |
332 | } | |
333 | ||
334 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool { | |
335 | debug!("visit_ty: ty={:?}", ty); | |
336 | if !ty.has_param_types_or_consts() { | |
337 | return false; | |
338 | } | |
339 | ||
340 | match ty.kind { | |
341 | ty::Param(param) => !self.unused_parameters.contains(param.index).unwrap_or(false), | |
342 | _ => ty.super_visit_with(self), | |
343 | } | |
344 | } | |
345 | } |