1 //! Polymorphization Analysis
2 //! =========================
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.).
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,
14 use rustc_middle::ty::{
16 fold::{TypeFoldable, TypeVisitor},
21 use rustc_span::symbol::sym;
22 use std::convert::TryInto;
24 /// Provide implementations of queries relating to polymorphization analysis.
25 pub fn provide(providers: &mut Providers) {
26 providers.unused_generic_params = unused_generic_params;
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);
35 if !tcx.sess.opts.debugging_opts.polymorphize {
36 // If polymorphization disabled, then all parameters are used.
37 return FiniteBitSet::new_empty();
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();
47 let generics = tcx.generics_of(def_id);
48 debug!("unused_generic_params: generics={:?}", generics);
50 // Exit early when there are no parameters to be unused.
51 if generics.count() == 0 {
52 return FiniteBitSet::new_empty();
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();
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);
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 };
74 debug!("unused_generic_params: (after visitor) unused_parameters={:?}", unused_parameters);
76 mark_used_by_predicates(tcx, def_id, &mut unused_parameters);
77 debug!("unused_generic_params: (end) unused_parameters={:?}", unused_parameters);
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);
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>(
93 generics: &'tcx ty::Generics,
94 unused_parameters: &mut FiniteBitSet<u32>,
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);
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);
110 if let Some(parent) = generics.parent {
111 mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
115 /// Search the predicates on used generic parameters for any unused generic parameters, and mark
117 fn mark_used_by_predicates<'tcx>(
120 unused_parameters: &mut FiniteBitSet<u32>,
122 let is_ty_used = |unused_parameters: &FiniteBitSet<u32>, ty: Ty<'tcx>| -> bool {
123 let mut vis = IsUsedGenericParams { unused_parameters };
124 ty.visit_with(&mut vis)
127 let mark_ty = |unused_parameters: &mut FiniteBitSet<u32>, ty: Ty<'tcx>| {
128 let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters };
129 ty.visit_with(&mut vis);
132 let def_id = tcx.closure_base_def_id(def_id);
133 let predicates = tcx.explicit_predicates_of(def_id);
134 debug!("mark_used_by_predicates: predicates_of={:?}", predicates);
136 let mut current_unused_parameters = FiniteBitSet::new_empty();
137 // Run to a fixed point to support `where T: Trait<U>, U: Trait<V>`, starting with an empty
138 // bit set so that this is skipped if all parameters are already used.
139 while current_unused_parameters != *unused_parameters {
141 "mark_used_by_predicates: current_unused_parameters={:?} = unused_parameters={:?}",
142 current_unused_parameters, unused_parameters
144 current_unused_parameters = *unused_parameters;
146 for (predicate, _) in predicates.predicates {
147 match predicate.skip_binders() {
148 ty::PredicateAtom::Trait(predicate, ..) => {
149 let trait_ref = predicate.trait_ref;
150 debug!("mark_used_by_predicates: (trait) trait_ref={:?}", trait_ref);
152 // Consider `T` used if `I` is used in predicates of the form
153 // `I: Iterator<Item = T>`
154 debug!("mark_used_by_predicates: checking self");
155 if is_ty_used(unused_parameters, trait_ref.self_ty()) {
156 debug!("mark_used_by_predicates: used!");
157 for ty in trait_ref.substs.types() {
158 mark_ty(unused_parameters, ty);
161 // No need to check for a type being used in the substs if `self_ty` was
166 // Consider `I` used if `T` is used in predicates of the form
167 // `I: Iterator<Item = &'a (T, E)>` (see rust-lang/rust#75326)
168 debug!("mark_used_by_predicates: checking substs");
169 for ty in trait_ref.substs.types() {
170 if is_ty_used(unused_parameters, ty) {
171 debug!("mark_used_by_predicates: used!");
172 mark_ty(unused_parameters, trait_ref.self_ty());
176 ty::PredicateAtom::Projection(proj, ..) => {
177 let self_ty = proj.projection_ty.self_ty();
179 "mark_used_by_predicates: (projection) self_ty={:?} proj.ty={:?}",
183 // Consider `T` used if `I` is used in predicates of the form
184 // `<I as Iterator>::Item = T`
185 debug!("mark_used_by_predicates: checking self");
186 if is_ty_used(unused_parameters, self_ty) {
187 debug!("mark_used_by_predicates: used!");
188 mark_ty(unused_parameters, proj.ty);
190 // No need to check for projection type being used if `self_ty` was used.
194 // Consider `I` used if `T` is used in predicates of the form
195 // `<I as Iterator>::Item = &'a (T, E)` (see rust-lang/rust#75326)
196 debug!("mark_used_by_predicates: checking projection ty");
197 if is_ty_used(unused_parameters, proj.ty) {
198 debug!("mark_used_by_predicates: used!");
199 mark_ty(unused_parameters, self_ty);
202 ty::PredicateAtom::RegionOutlives(..)
203 | ty::PredicateAtom::TypeOutlives(..)
204 | ty::PredicateAtom::WellFormed(..)
205 | ty::PredicateAtom::ObjectSafe(..)
206 | ty::PredicateAtom::ClosureKind(..)
207 | ty::PredicateAtom::Subtype(..)
208 | ty::PredicateAtom::ConstEvaluatable(..)
209 | ty::PredicateAtom::ConstEquate(..) => (),
214 if let Some(parent) = predicates.parent {
215 mark_used_by_predicates(tcx, parent, unused_parameters);
219 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
220 /// parameter which was unused.
221 fn emit_unused_generic_params_error<'tcx>(
224 generics: &'tcx ty::Generics,
225 unused_parameters: &FiniteBitSet<u32>,
227 debug!("emit_unused_generic_params_error: def_id={:?}", def_id);
228 let base_def_id = tcx.closure_base_def_id(def_id);
230 .get_attrs(base_def_id)
232 .any(|a| tcx.sess.check_name(a, sym::rustc_polymorphize_error))
237 debug!("emit_unused_generic_params_error: unused_parameters={:?}", unused_parameters);
238 let fn_span = match tcx.opt_item_name(def_id) {
239 Some(ident) => ident.span,
240 _ => tcx.def_span(def_id),
243 let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
245 let mut next_generics = Some(generics);
246 while let Some(generics) = next_generics {
247 for param in &generics.params {
248 if unused_parameters.contains(param.index).unwrap_or(false) {
249 debug!("emit_unused_generic_params_error: param={:?}", param);
250 let def_span = tcx.def_span(param.def_id);
251 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
255 next_generics = generics.parent.map(|did| tcx.generics_of(did));
261 /// Visitor used to aggregate generic parameter uses.
262 struct MarkUsedGenericParams<'a, 'tcx> {
265 unused_parameters: &'a mut FiniteBitSet<u32>,
268 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
269 /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
270 /// a closure, generator or constant).
271 fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
272 let unused = self.tcx.unused_generic_params(def_id);
274 "visit_child_body: unused_parameters={:?} unused={:?}",
275 self.unused_parameters, unused
277 for (i, arg) in substs.iter().enumerate() {
278 let i = i.try_into().unwrap();
279 if !unused.contains(i).unwrap_or(false) {
280 arg.visit_with(self);
283 debug!("visit_child_body: unused_parameters={:?}", self.unused_parameters);
287 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
288 fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
289 debug!("visit_local_decl: local_decl={:?}", local_decl);
290 if local == Local::from_usize(1) {
291 let def_kind = self.tcx.def_kind(self.def_id);
292 if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
293 // Skip visiting the closure/generator that is currently being processed. This only
294 // happens because the first argument to the closure is a reference to itself and
295 // that will call `visit_substs`, resulting in each generic parameter captured being
296 // considered used by default.
297 debug!("visit_local_decl: skipping closure substs");
302 self.super_local_decl(local, local_decl);
305 fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
309 fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
314 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
315 fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool {
316 debug!("visit_const: c={:?}", c);
317 if !c.has_param_types_or_consts() {
322 ty::ConstKind::Param(param) => {
323 debug!("visit_const: param={:?}", param);
324 self.unused_parameters.clear(param.index);
327 ty::ConstKind::Unevaluated(def, _, Some(p))
328 // Avoid considering `T` unused when constants are of the form:
329 // `<Self as Foo<T>>::foo::promoted[p]`
330 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
332 // If there is a promoted, don't look at the substs - since it will always contain
333 // the generic parameters, instead, traverse the promoted MIR.
334 let promoted = self.tcx.promoted_mir(def.did);
335 self.visit_body(&promoted[p]);
338 ty::ConstKind::Unevaluated(def, unevaluated_substs, None)
339 if self.tcx.def_kind(def.did) == DefKind::AnonConst =>
341 self.visit_child_body(def.did, unevaluated_substs);
344 _ => c.super_visit_with(self),
348 fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
349 debug!("visit_ty: ty={:?}", ty);
350 if !ty.has_param_types_or_consts() {
355 ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
356 debug!("visit_ty: def_id={:?}", def_id);
357 // Avoid cycle errors with generators.
358 if def_id == self.def_id {
362 // Consider any generic parameters used by any closures/generators as used in the
364 self.visit_child_body(def_id, substs);
367 ty::Param(param) => {
368 debug!("visit_ty: param={:?}", param);
369 self.unused_parameters.clear(param.index);
372 _ => ty.super_visit_with(self),
377 /// Visitor used to check if a generic parameter is used.
378 struct IsUsedGenericParams<'a> {
379 unused_parameters: &'a FiniteBitSet<u32>,
382 impl<'a, 'tcx> TypeVisitor<'tcx> for IsUsedGenericParams<'a> {
383 fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool {
384 debug!("visit_const: c={:?}", c);
385 if !c.has_param_types_or_consts() {
390 ty::ConstKind::Param(param) => {
391 !self.unused_parameters.contains(param.index).unwrap_or(false)
393 _ => c.super_visit_with(self),
397 fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
398 debug!("visit_ty: ty={:?}", ty);
399 if !ty.has_param_types_or_consts() {
404 ty::Param(param) => !self.unused_parameters.contains(param.index).unwrap_or(false),
405 _ => ty.super_visit_with(self),