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::{
12 visit::{TyContext, Visitor},
13 Constant, ConstantKind, Local, LocalDecl, Location,
15 use rustc_middle::ty::{
19 visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor},
22 use rustc_span::symbol::sym;
23 use std::convert::TryInto;
24 use std::ops::ControlFlow;
26 use crate::errors::UnusedGenericParams;
28 /// Provide implementations of queries relating to polymorphization analysis.
29 pub fn provide(providers: &mut Providers) {
30 providers.unused_generic_params = unused_generic_params;
33 /// Determine which generic parameters are used by the instance.
35 /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
36 /// parameters are used).
37 fn unused_generic_params<'tcx>(
39 instance: ty::InstanceDef<'tcx>,
40 ) -> FiniteBitSet<u32> {
41 if !tcx.sess.opts.unstable_opts.polymorphize {
42 // If polymorphization disabled, then all parameters are used.
43 return FiniteBitSet::new_empty();
46 let def_id = instance.def_id();
47 // Exit early if this instance should not be polymorphized.
48 if !should_polymorphize(tcx, def_id, instance) {
49 return FiniteBitSet::new_empty();
52 let generics = tcx.generics_of(def_id);
55 // Exit early when there are no parameters to be unused.
56 if generics.count() == 0 {
57 return FiniteBitSet::new_empty();
60 // Create a bitset with N rightmost ones for each parameter.
61 let generics_count: u32 =
62 generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
63 let mut unused_parameters = FiniteBitSet::<u32>::new_empty();
64 unused_parameters.set_range(0..generics_count);
65 debug!(?unused_parameters, "(start)");
67 mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
68 debug!(?unused_parameters, "(after default)");
70 // Visit MIR and accumulate used generic parameters.
71 let body = match tcx.hir().body_const_context(def_id.expect_local()) {
72 // Const functions are actually called and should thus be considered for polymorphization
73 // via their runtime MIR.
74 Some(ConstContext::ConstFn) | None => tcx.optimized_mir(def_id),
75 Some(_) => tcx.mir_for_ctfe(def_id),
77 let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
79 debug!(?unused_parameters, "(end)");
81 // Emit errors for debugging and testing if enabled.
82 if !unused_parameters.is_empty() {
83 emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters);
89 /// Returns `true` if the instance should be polymorphized.
90 fn should_polymorphize<'tcx>(
93 instance: ty::InstanceDef<'tcx>,
95 // If an instance's MIR body is not polymorphic then the modified substitutions that are
96 // derived from polymorphization's result won't make any difference.
97 if !instance.has_polymorphic_mir_body() {
101 // Don't polymorphize intrinsics or virtual calls - calling `instance_mir` will panic.
102 if matches!(instance, ty::InstanceDef::Intrinsic(..) | ty::InstanceDef::Virtual(..)) {
106 // Polymorphization results are stored in cross-crate metadata only when there are unused
107 // parameters, so assume that non-local items must have only used parameters (else this query
108 // would not be invoked, and the cross-crate metadata used instead).
109 if !def_id.is_local() {
113 // Foreign items have no bodies to analyze.
114 if tcx.is_foreign_item(def_id) {
118 // Make sure there is MIR available.
119 match tcx.hir().body_const_context(def_id.expect_local()) {
120 Some(ConstContext::ConstFn) | None if !tcx.is_mir_available(def_id) => {
121 debug!("no mir available");
124 Some(_) if !tcx.is_ctfe_mir_available(def_id) => {
125 debug!("no ctfe mir available");
132 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
133 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
134 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
135 #[instrument(level = "debug", skip(tcx, def_id, generics, unused_parameters))]
136 fn mark_used_by_default_parameters<'tcx>(
139 generics: &'tcx ty::Generics,
140 unused_parameters: &mut FiniteBitSet<u32>,
142 match tcx.def_kind(def_id) {
143 DefKind::Closure | DefKind::Generator => {
144 for param in &generics.params {
145 debug!(?param, "(closure/gen)");
146 unused_parameters.clear(param.index);
157 | DefKind::TraitAlias
162 | DefKind::ConstParam
164 | DefKind::Ctor(_, _)
166 | DefKind::AssocConst
168 | DefKind::ExternCrate
170 | DefKind::ForeignMod
172 | DefKind::InlineConst
174 | DefKind::ImplTraitPlaceholder
176 | DefKind::LifetimeParam
179 for param in &generics.params {
180 debug!(?param, "(other)");
181 if let ty::GenericParamDefKind::Lifetime = param.kind {
182 unused_parameters.clear(param.index);
188 if let Some(parent) = generics.parent {
189 mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
193 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
194 /// parameter which was unused.
195 #[instrument(level = "debug", skip(tcx, generics))]
196 fn emit_unused_generic_params_error<'tcx>(
199 generics: &'tcx ty::Generics,
200 unused_parameters: &FiniteBitSet<u32>,
202 let base_def_id = tcx.typeck_root_def_id(def_id);
203 if !tcx.has_attr(base_def_id, sym::rustc_polymorphize_error) {
207 let fn_span = match tcx.opt_item_ident(def_id) {
208 Some(ident) => ident.span,
209 _ => tcx.def_span(def_id),
212 let mut param_spans = Vec::new();
213 let mut param_names = Vec::new();
214 let mut next_generics = Some(generics);
215 while let Some(generics) = next_generics {
216 for param in &generics.params {
217 if unused_parameters.contains(param.index).unwrap_or(false) {
219 let def_span = tcx.def_span(param.def_id);
220 param_spans.push(def_span);
221 param_names.push(param.name.to_string());
225 next_generics = generics.parent.map(|did| tcx.generics_of(did));
228 tcx.sess.emit_err(UnusedGenericParams { span: fn_span, param_spans, param_names });
231 /// Visitor used to aggregate generic parameter uses.
232 struct MarkUsedGenericParams<'a, 'tcx> {
235 unused_parameters: &'a mut FiniteBitSet<u32>,
238 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
239 /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
240 /// a closure, generator or constant).
241 #[instrument(level = "debug", skip(self, def_id, substs))]
242 fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
243 let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
244 let unused = self.tcx.unused_generic_params(instance);
245 debug!(?self.unused_parameters, ?unused);
246 for (i, arg) in substs.iter().enumerate() {
247 let i = i.try_into().unwrap();
248 if !unused.contains(i).unwrap_or(false) {
249 arg.visit_with(self);
252 debug!(?self.unused_parameters);
256 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
257 #[instrument(level = "debug", skip(self, local))]
258 fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
259 if local == Local::from_usize(1) {
260 let def_kind = self.tcx.def_kind(self.def_id);
261 if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
262 // Skip visiting the closure/generator that is currently being processed. This only
263 // happens because the first argument to the closure is a reference to itself and
264 // that will call `visit_substs`, resulting in each generic parameter captured being
265 // considered used by default.
266 debug!("skipping closure substs");
271 self.super_local_decl(local, local_decl);
274 fn visit_constant(&mut self, ct: &Constant<'tcx>, location: Location) {
276 ConstantKind::Ty(c) => {
279 ConstantKind::Val(_, ty) | ConstantKind::Unevaluated(_, ty) => {
280 Visitor::visit_ty(self, ty, TyContext::Location(location))
285 fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
290 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
291 #[instrument(level = "debug", skip(self))]
292 fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
293 if !c.has_non_region_param() {
294 return ControlFlow::CONTINUE;
298 ty::ConstKind::Param(param) => {
300 self.unused_parameters.clear(param.index);
301 ControlFlow::CONTINUE
303 ty::ConstKind::Unevaluated(ty::UnevaluatedConst { def, substs })
304 if matches!(self.tcx.def_kind(def.did), DefKind::AnonConst) =>
306 self.visit_child_body(def.did, substs);
307 ControlFlow::CONTINUE
309 _ => c.super_visit_with(self),
313 fn visit_mir_const(&mut self, constant: ConstantKind<'tcx>) -> ControlFlow<Self::BreakTy> {
314 if !constant.has_non_region_param() {
315 return ControlFlow::CONTINUE;
319 ConstantKind::Ty(ct) => ct.visit_with(self),
320 ConstantKind::Unevaluated(mir::UnevaluatedConst { def, substs: _, promoted: Some(p) }, _)
321 // Avoid considering `T` unused when constants are of the form:
322 // `<Self as Foo<T>>::foo::promoted[p]`
323 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
325 // If there is a promoted, don't look at the substs - since it will always contain
326 // the generic parameters, instead, traverse the promoted MIR.
327 let promoted = self.tcx.promoted_mir(def.did);
328 self.visit_body(&promoted[p]);
329 ControlFlow::CONTINUE
331 ConstantKind::Val(..) | ConstantKind::Unevaluated(..) => {
332 constant.super_visit_with(self)
337 #[instrument(level = "debug", skip(self))]
338 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
339 if !ty.has_non_region_param() {
340 return ControlFlow::CONTINUE;
344 ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
346 // Avoid cycle errors with generators.
347 if def_id == self.def_id {
348 return ControlFlow::CONTINUE;
351 // Consider any generic parameters used by any closures/generators as used in the
353 self.visit_child_body(def_id, substs);
354 ControlFlow::CONTINUE
356 ty::Param(param) => {
358 self.unused_parameters.clear(param.index);
359 ControlFlow::CONTINUE
361 _ => ty.super_visit_with(self),
366 /// Visitor used to check if a generic parameter is used.
367 struct HasUsedGenericParams<'a> {
368 unused_parameters: &'a FiniteBitSet<u32>,
371 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> {
374 #[instrument(level = "debug", skip(self))]
375 fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
376 if !c.has_non_region_param() {
377 return ControlFlow::CONTINUE;
381 ty::ConstKind::Param(param) => {
382 if self.unused_parameters.contains(param.index).unwrap_or(false) {
383 ControlFlow::CONTINUE
388 _ => c.super_visit_with(self),
392 #[instrument(level = "debug", skip(self))]
393 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
394 if !ty.has_non_region_param() {
395 return ControlFlow::CONTINUE;
399 ty::Param(param) => {
400 if self.unused_parameters.contains(param.index).unwrap_or(false) {
401 ControlFlow::CONTINUE
406 _ => ty.super_visit_with(self),