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, ConstContext};
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;
23 use std::ops::ControlFlow;
25 /// Provide implementations of queries relating to polymorphization analysis.
26 pub fn provide(providers: &mut Providers) {
27 providers.unused_generic_params = unused_generic_params;
30 /// Determine which generic parameters are used by the instance.
32 /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
33 /// parameters are used).
34 #[instrument(level = "debug", skip(tcx))]
35 fn unused_generic_params<'tcx>(
37 instance: ty::InstanceDef<'tcx>,
38 ) -> FiniteBitSet<u32> {
39 if !tcx.sess.opts.debugging_opts.polymorphize {
40 // If polymorphization disabled, then all parameters are used.
41 return FiniteBitSet::new_empty();
44 let def_id = instance.def_id();
45 // Exit early if this instance should not be polymorphized.
46 if !should_polymorphize(tcx, def_id, instance) {
47 return FiniteBitSet::new_empty();
50 let generics = tcx.generics_of(def_id);
53 // Exit early when there are no parameters to be unused.
54 if generics.count() == 0 {
55 return FiniteBitSet::new_empty();
58 // Create a bitset with N rightmost ones for each parameter.
59 let generics_count: u32 =
60 generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
61 let mut unused_parameters = FiniteBitSet::<u32>::new_empty();
62 unused_parameters.set_range(0..generics_count);
63 debug!(?unused_parameters, "(start)");
65 mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
66 debug!(?unused_parameters, "(after default)");
68 // Visit MIR and accumululate used generic parameters.
69 let body = match tcx.hir().body_const_context(def_id.expect_local()) {
70 // Const functions are actually called and should thus be considered for polymorphization
71 // via their runtime MIR.
72 Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id),
73 Some(_) => tcx.mir_for_ctfe(def_id),
75 let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
77 debug!(?unused_parameters, "(end)");
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 /// Returns `true` if the instance should be polymorphized.
88 fn should_polymorphize<'tcx>(
91 instance: ty::InstanceDef<'tcx>,
93 // If an instance's MIR body is not polymorphic then the modified substitutions that are
94 // derived from polymorphization's result won't make any difference.
95 if !instance.has_polymorphic_mir_body() {
99 // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic.
100 if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) {
104 // Polymorphization results are stored in cross-crate metadata only when there are unused
105 // parameters, so assume that non-local items must have only used parameters (else this query
106 // would not be invoked, and the cross-crate metadata used instead).
107 if !def_id.is_local() {
111 // Foreign items have no bodies to analyze.
112 if tcx.is_foreign_item(def_id) {
116 // Make sure there is MIR available.
117 match tcx.hir().body_const_context(def_id.expect_local()) {
118 Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
119 debug!("no mir available");
122 Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
123 debug!("no ctfe mir available");
130 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
131 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
132 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
133 #[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))]
134 fn mark_used_by_default_parameters<'tcx>(
137 generics: &'tcx ty::Generics,
138 unused_parameters: &mut FiniteBitSet<u32>,
140 match tcx.def_kind(def_id) {
141 DefKind::Closure | DefKind::Generator => {
142 for param in &generics.params {
143 debug!(?param, "(closure/gen)");
144 unused_parameters.clear(param.index);
155 | DefKind::TraitAlias
160 | DefKind::ConstParam
162 | DefKind::Ctor(_, _)
164 | DefKind::AssocConst
166 | DefKind::ExternCrate
168 | DefKind::ForeignMod
172 | DefKind::LifetimeParam
175 for param in &generics.params {
176 debug!(?param, "(other)");
177 if let ty::GenericParamDefKind::Lifetime = param.kind {
178 unused_parameters.clear(param.index);
184 if let Some(parent) = generics.parent {
185 mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
189 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
190 /// parameter which was unused.
191 #[instrument(level = "debug", skip(tcx, generics))]
192 fn emit_unused_generic_params_error<'tcx>(
195 generics: &'tcx ty::Generics,
196 unused_parameters: &FiniteBitSet<u32>,
198 let base_def_id = tcx.closure_base_def_id(def_id);
199 if !tcx.get_attrs(base_def_id).iter().any(|a| a.has_name(sym::rustc_polymorphize_error)) {
203 let fn_span = match tcx.opt_item_name(def_id) {
204 Some(ident) => ident.span,
205 _ => tcx.def_span(def_id),
208 let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
210 let mut next_generics = Some(generics);
211 while let Some(generics) = next_generics {
212 for param in &generics.params {
213 if unused_parameters.contains(param.index).unwrap_or(false) {
215 let def_span = tcx.def_span(param.def_id);
216 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
220 next_generics = generics.parent.map(|did| tcx.generics_of(did));
226 /// Visitor used to aggregate generic parameter uses.
227 struct MarkUsedGenericParams<'a, 'tcx> {
230 unused_parameters: &'a mut FiniteBitSet<u32>,
233 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
234 /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
235 /// a closure, generator or constant).
236 #[instrument(level = "debug", skip(self, def_id, substs))]
237 fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
238 let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
239 let unused = self.tcx.unused_generic_params(instance);
240 debug!(?self.unused_parameters, ?unused);
241 for (i, arg) in substs.iter().enumerate() {
242 let i = i.try_into().unwrap();
243 if !unused.contains(i).unwrap_or(false) {
244 arg.visit_with(self);
247 debug!(?self.unused_parameters);
251 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
252 #[instrument(level = "debug", skip(self, local))]
253 fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
254 if local == Local::from_usize(1) {
255 let def_kind = self.tcx.def_kind(self.def_id);
256 if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
257 // Skip visiting the closure/generator that is currently being processed. This only
258 // happens because the first argument to the closure is a reference to itself and
259 // that will call `visit_substs`, resulting in each generic parameter captured being
260 // considered used by default.
261 debug!("skipping closure substs");
266 self.super_local_decl(local, local_decl);
269 fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
273 fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
278 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
279 fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
282 #[instrument(level = "debug", skip(self))]
283 fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
284 if !c.potentially_has_param_types_or_consts() {
285 return ControlFlow::CONTINUE;
289 ty::ConstKind::Param(param) => {
291 self.unused_parameters.clear(param.index);
292 ControlFlow::CONTINUE
294 ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs_: _, promoted: Some(p)})
295 // Avoid considering `T` unused when constants are of the form:
296 // `<Self as Foo<T>>::foo::promoted[p]`
297 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
299 // If there is a promoted, don't look at the substs - since it will always contain
300 // the generic parameters, instead, traverse the promoted MIR.
301 let promoted = self.tcx.promoted_mir(def.did);
302 self.visit_body(&promoted[p]);
303 ControlFlow::CONTINUE
305 ty::ConstKind::Unevaluated(uv)
306 if self.tcx.def_kind(uv.def.did) == DefKind::AnonConst =>
308 self.visit_child_body(uv.def.did, uv.substs(self.tcx));
309 ControlFlow::CONTINUE
311 _ => c.super_visit_with(self),
315 #[instrument(level = "debug", skip(self))]
316 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
317 if !ty.potentially_has_param_types_or_consts() {
318 return ControlFlow::CONTINUE;
322 ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
324 // Avoid cycle errors with generators.
325 if def_id == self.def_id {
326 return ControlFlow::CONTINUE;
329 // Consider any generic parameters used by any closures/generators as used in the
331 self.visit_child_body(def_id, substs);
332 ControlFlow::CONTINUE
334 ty::Param(param) => {
336 self.unused_parameters.clear(param.index);
337 ControlFlow::CONTINUE
339 _ => ty.super_visit_with(self),
344 /// Visitor used to check if a generic parameter is used.
345 struct HasUsedGenericParams<'a, 'tcx> {
347 unused_parameters: &'a FiniteBitSet<u32>,
350 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a, 'tcx> {
353 fn tcx_for_anon_const_substs(&self) -> Option<TyCtxt<'tcx>> {
357 #[instrument(level = "debug", skip(self))]
358 fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> ControlFlow<Self::BreakTy> {
359 if !c.potentially_has_param_types_or_consts() {
360 return ControlFlow::CONTINUE;
364 ty::ConstKind::Param(param) => {
365 if self.unused_parameters.contains(param.index).unwrap_or(false) {
366 ControlFlow::CONTINUE
371 _ => c.super_visit_with(self),
375 #[instrument(level = "debug", skip(self))]
376 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
377 if !ty.potentially_has_param_types_or_consts() {
378 return ControlFlow::CONTINUE;
382 ty::Param(param) => {
383 if self.unused_parameters.contains(param.index).unwrap_or(false) {
384 ControlFlow::CONTINUE
389 _ => ty.super_visit_with(self),