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 use crate::errors::UnusedGenericParams;
27 /// Provide implementations of queries relating to polymorphization analysis.
28 pub fn provide(providers: &mut Providers) {
29 providers.unused_generic_params = unused_generic_params;
32 /// Determine which generic parameters are used by the instance.
34 /// Returns a bitset where bits representing unused parameters are set (`is_empty` indicates all
35 /// parameters are used).
36 #[instrument(level = "debug", skip(tcx))]
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
175 | DefKind::LifetimeParam
178 for param in &generics.params {
179 debug!(?param, "(other)");
180 if let ty::GenericParamDefKind::Lifetime = param.kind {
181 unused_parameters.clear(param.index);
187 if let Some(parent) = generics.parent {
188 mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
192 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
193 /// parameter which was unused.
194 #[instrument(level = "debug", skip(tcx, generics))]
195 fn emit_unused_generic_params_error<'tcx>(
198 generics: &'tcx ty::Generics,
199 unused_parameters: &FiniteBitSet<u32>,
201 let base_def_id = tcx.typeck_root_def_id(def_id);
202 if !tcx.has_attr(base_def_id, sym::rustc_polymorphize_error) {
206 let fn_span = match tcx.opt_item_ident(def_id) {
207 Some(ident) => ident.span,
208 _ => tcx.def_span(def_id),
211 let mut param_spans = Vec::new();
212 let mut param_names = Vec::new();
213 let mut next_generics = Some(generics);
214 while let Some(generics) = next_generics {
215 for param in &generics.params {
216 if unused_parameters.contains(param.index).unwrap_or(false) {
218 let def_span = tcx.def_span(param.def_id);
219 param_spans.push(def_span);
220 param_names.push(param.name.to_string());
224 next_generics = generics.parent.map(|did| tcx.generics_of(did));
227 tcx.sess.emit_err(UnusedGenericParams { span: fn_span, param_spans, param_names });
230 /// Visitor used to aggregate generic parameter uses.
231 struct MarkUsedGenericParams<'a, 'tcx> {
234 unused_parameters: &'a mut FiniteBitSet<u32>,
237 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
238 /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
239 /// a closure, generator or constant).
240 #[instrument(level = "debug", skip(self, def_id, substs))]
241 fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
242 let instance = ty::InstanceDef::Item(ty::WithOptConstParam::unknown(def_id));
243 let unused = self.tcx.unused_generic_params(instance);
244 debug!(?self.unused_parameters, ?unused);
245 for (i, arg) in substs.iter().enumerate() {
246 let i = i.try_into().unwrap();
247 if !unused.contains(i).unwrap_or(false) {
248 arg.visit_with(self);
251 debug!(?self.unused_parameters);
255 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
256 #[instrument(level = "debug", skip(self, local))]
257 fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
258 if local == Local::from_usize(1) {
259 let def_kind = self.tcx.def_kind(self.def_id);
260 if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
261 // Skip visiting the closure/generator that is currently being processed. This only
262 // happens because the first argument to the closure is a reference to itself and
263 // that will call `visit_substs`, resulting in each generic parameter captured being
264 // considered used by default.
265 debug!("skipping closure substs");
270 self.super_local_decl(local, local_decl);
273 fn visit_const(&mut self, c: Const<'tcx>, _: Location) {
277 fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
282 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
283 #[instrument(level = "debug", skip(self))]
284 fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
285 if !c.has_param_types_or_consts() {
286 return ControlFlow::CONTINUE;
290 ty::ConstKind::Param(param) => {
292 self.unused_parameters.clear(param.index);
293 ControlFlow::CONTINUE
295 ty::ConstKind::Unevaluated(ty::Unevaluated { def, substs: _, promoted: Some(p)})
296 // Avoid considering `T` unused when constants are of the form:
297 // `<Self as Foo<T>>::foo::promoted[p]`
298 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
300 // If there is a promoted, don't look at the substs - since it will always contain
301 // the generic parameters, instead, traverse the promoted MIR.
302 let promoted = self.tcx.promoted_mir(def.did);
303 self.visit_body(&promoted[p]);
304 ControlFlow::CONTINUE
306 ty::ConstKind::Unevaluated(uv)
307 if matches!(self.tcx.def_kind(uv.def.did), DefKind::AnonConst | DefKind::InlineConst) =>
309 self.visit_child_body(uv.def.did, uv.substs);
310 ControlFlow::CONTINUE
312 _ => c.super_visit_with(self),
316 #[instrument(level = "debug", skip(self))]
317 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
318 if !ty.has_param_types_or_consts() {
319 return ControlFlow::CONTINUE;
323 ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
325 // Avoid cycle errors with generators.
326 if def_id == self.def_id {
327 return ControlFlow::CONTINUE;
330 // Consider any generic parameters used by any closures/generators as used in the
332 self.visit_child_body(def_id, substs);
333 ControlFlow::CONTINUE
335 ty::Param(param) => {
337 self.unused_parameters.clear(param.index);
338 ControlFlow::CONTINUE
340 _ => ty.super_visit_with(self),
345 /// Visitor used to check if a generic parameter is used.
346 struct HasUsedGenericParams<'a> {
347 unused_parameters: &'a FiniteBitSet<u32>,
350 impl<'a, 'tcx> TypeVisitor<'tcx> for HasUsedGenericParams<'a> {
353 #[instrument(level = "debug", skip(self))]
354 fn visit_const(&mut self, c: Const<'tcx>) -> ControlFlow<Self::BreakTy> {
355 if !c.has_param_types_or_consts() {
356 return ControlFlow::CONTINUE;
360 ty::ConstKind::Param(param) => {
361 if self.unused_parameters.contains(param.index).unwrap_or(false) {
362 ControlFlow::CONTINUE
367 _ => c.super_visit_with(self),
371 #[instrument(level = "debug", skip(self))]
372 fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
373 if !ty.has_param_types_or_consts() {
374 return ControlFlow::CONTINUE;
378 ty::Param(param) => {
379 if self.unused_parameters.contains(param.index).unwrap_or(false) {
380 ControlFlow::CONTINUE
385 _ => ty.super_visit_with(self),