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::{
18 visit::{TypeSuperVisitable, TypeVisitable, 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.unstable_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 accumulate 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
170 | DefKind::InlineConst
173 | DefKind::LifetimeParam
176 for param in &generics.params {
177 debug!(?param, "(other)");
178 if let ty::GenericParamDefKind::Lifetime = param.kind {
179 unused_parameters.clear(param.index);
185 if let Some(parent) = generics.parent {
186 mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
190 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
191 /// parameter which was unused.
192 #[instrument(level = "debug", skip(tcx, generics))]
193 fn emit_unused_generic_params_error<'tcx>(
196 generics: &'tcx ty::Generics,
197 unused_parameters: &FiniteBitSet<u32>,
199 let base_def_id = tcx.typeck_root_def_id(def_id);
200 if !tcx.has_attr(base_def_id, sym::rustc_polymorphize_error) {
204 let fn_span = match tcx.opt_item_ident(def_id) {
205 Some(ident) => ident.span,
206 _ => tcx.def_span(def_id),
209 let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
211 let mut next_generics = Some(generics);
212 while let Some(generics) = next_generics {
213 for param in &generics.params {
214 if unused_parameters.contains(param.index).unwrap_or(false) {
216 let def_span = tcx.def_span(param.def_id);
217 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
221 next_generics = generics.parent.map(|did| tcx.generics_of(did));
227 /// Visitor used to aggregate generic parameter uses.
228 struct MarkUsedGenericParams<'a, 'tcx> {
231 unused_parameters: &'a mut FiniteBitSet<u32>,
234 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
235 /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
236 /// a closure, generator or constant).
237 #[instrument(level = "debug", skip(self, def_id, substs))]
238 fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
239 let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
240 let unused = self.tcx.unused_generic_params(instance);
241 debug!(?self.unused_parameters, ?unused);
242 for (i, arg) in substs.iter().enumerate() {
243 let i = i.try_into().unwrap();
244 if !unused.contains(i).unwrap_or(false) {
245 arg.visit_with(self);
248 debug!(?self.unused_parameters);
252 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
253 #[instrument(level = "debug", skip(self, local))]
254 fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
255 if local == Local::from_usize(1) {
256 let def_kind = self.tcx.def_kind(self.def_id);
257 if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
258 // Skip visiting the closure/generator that is currently being processed. This only
259 // happens because the first argument to the closure is a reference to itself and
260 // that will call `visit_substs`, resulting in each generic parameter captured being
261 // considered used by default.
262 debug!("skipping closure substs");
267 self.super_local_decl(local, local_decl);
270 fn visit_const(&mut self, c: Const<'tcx>, _: Location) {
274 fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
279 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
280 #[instrument(level = "debug", skip(self))]
281 fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
282 if !c.has_param_types_or_consts() {
283 return ControlFlow::CONTINUE;
287 ty::ConstKind::Param(param) => {
289 self.unused_parameters.clear(param.index);
290 ControlFlow::CONTINUE
292 ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs: _, promoted: Some(p)})
293 // Avoid considering `T` unused when constants are of the form:
294 // `<Self as Foo<T>>::foo::promoted[p]`
295 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
297 // If there is a promoted, don't look at the substs - since it will always contain
298 // the generic parameters, instead, traverse the promoted MIR.
299 let promoted = self.tcx.promoted_mir(def.did);
300 self.visit_body(&promoted[p]);
301 ControlFlow::CONTINUE
303 ty::ConstKind::Unevaluated(uv)
304 if matches!(self.tcx.def_kind(uv.def.did), DefKind::AnonConst | DefKind::InlineConst) =>
306 self.visit_child_body(uv.def.did, uv.substs);
307 ControlFlow::CONTINUE
309 _ => c.super_visit_with(self),
313 #[instrument(level = "debug", skip(self))]
314 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
315 if !ty.has_param_types_or_consts() {
316 return ControlFlow::CONTINUE;
320 ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
322 // Avoid cycle errors with generators.
323 if def_id == self.def_id {
324 return ControlFlow::CONTINUE;
327 // Consider any generic parameters used by any closures/generators as used in the
329 self.visit_child_body(def_id, substs);
330 ControlFlow::CONTINUE
332 ty::Param(param) => {
334 self.unused_parameters.clear(param.index);
335 ControlFlow::CONTINUE
337 _ => ty.super_visit_with(self),
342 /// Visitor used to check if a generic parameter is used.
343 struct HasUsedGenericParams<'a> {
344 unused_parameters: &'a FiniteBitSet<u32>,
347 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> {
350 #[instrument(level = "debug", skip(self))]
351 fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
352 if !c.has_param_types_or_consts() {
353 return ControlFlow::CONTINUE;
357 ty::ConstKind::Param(param) => {
358 if self.unused_parameters.contains(param.index).unwrap_or(false) {
359 ControlFlow::CONTINUE
364 _ => c.super_visit_with(self),
368 #[instrument(level = "debug", skip(self))]
369 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
370 if !ty.has_param_types_or_consts() {
371 return ControlFlow::CONTINUE;
375 ty::Param(param) => {
376 if self.unused_parameters.contains(param.index).unwrap_or(false) {
377 ControlFlow::CONTINUE
382 _ => ty.super_visit_with(self),