src/librustc_mir/monomorphize/polymorphize.rs

   1 //! Polymorphization Analysis
   2 //! =========================
   3 //!
   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.).
   7
   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,
  13 };
  14 use rustc_middle::ty::{
  15     self,
  16     fold::{TypeFoldable, TypeVisitor},
  17     query::Providers,
  18     Const, Ty, TyCtxt,
  19 };
  20 use rustc_span::symbol::sym;
  21 use std::convert::TryInto;
  22
  23 /// Provide implementations of queries relating to polymorphization analysis.
  24 pub fn provide(providers: &mut Providers) {
  25     providers.unused_generic_params = unused_generic_params;
  26 }
  27
  28 /// Determine which generic parameters are used by the function/method/closure represented by
  29 /// `def_id`. Returns a bitset where bits representing unused parameters are set (`is_empty`
  30 /// indicates all parameters are used).
  31 fn unused_generic_params(tcx: TyCtxt<'_>, def_id: DefId) -> FiniteBitSet<u32> {
  32     debug!("unused_generic_params({:?})", def_id);
  33
  34     if !tcx.sess.opts.debugging_opts.polymorphize {
  35         // If polymorphization disabled, then all parameters are used.
  36         return FiniteBitSet::new_empty();
  37     }
  38
  39     let generics = tcx.generics_of(def_id);
  40     debug!("unused_generic_params: generics={:?}", generics);
  41
  42     // Exit early when there are no parameters to be unused.
  43     if generics.count() == 0 {
  44         return FiniteBitSet::new_empty();
  45     }
  46
  47     // Exit early when there is no MIR available.
  48     if !tcx.is_mir_available(def_id) {
  49         debug!("unused_generic_params: (no mir available) def_id={:?}", def_id);
  50         return FiniteBitSet::new_empty();
  51     }
  52
  53     // Create a bitset with N rightmost ones for each parameter.
  54     let generics_count: u32 =
  55         generics.count().try_into().expect("more generic parameters than can fit into a `u32`");
  56     let mut unused_parameters = FiniteBitSet::<u32>::new_empty();
  57     unused_parameters.set_range(0..generics_count);
  58     debug!("unused_generic_params: (start) unused_parameters={:?}", unused_parameters);
  59     mark_used_by_default_parameters(tcx, def_id, generics, &mut unused_parameters);
  60     debug!("unused_generic_params: (after default) unused_parameters={:?}", unused_parameters);
  61
  62     // Visit MIR and accumululate used generic parameters.
  63     let body = tcx.optimized_mir(def_id);
  64     let mut vis =
  65         UsedGenericParametersVisitor { tcx, def_id, unused_parameters: &mut unused_parameters };
  66     vis.visit_body(body);
  67     debug!("unused_generic_params: (after visitor) unused_parameters={:?}", unused_parameters);
  68
  69     mark_used_by_predicates(tcx, def_id, &mut unused_parameters);
  70     debug!("unused_generic_params: (end) unused_parameters={:?}", unused_parameters);
  71
  72     // Emit errors for debugging and testing if enabled.
  73     if !unused_parameters.is_empty() {
  74         emit_unused_generic_params_error(tcx, def_id, generics, &unused_parameters);
  75     }
  76
  77     unused_parameters
  78 }
  79
  80 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
  81 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
  82 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
  83 fn mark_used_by_default_parameters<'tcx>(
  84     tcx: TyCtxt<'tcx>,
  85     def_id: DefId,
  86     generics: &'tcx ty::Generics,
  87     unused_parameters: &mut FiniteBitSet<u32>,
  88 ) {
  89     if !tcx.is_trait(def_id) && (tcx.is_closure(def_id) || tcx.type_of(def_id).is_generator()) {
  90         for param in &generics.params {
  91             debug!("mark_used_by_default_parameters: (closure/gen) param={:?}", param);
  92             unused_parameters.clear(param.index);
  93         }
  94     } else {
  95         for param in &generics.params {
  96             debug!("mark_used_by_default_parameters: (other) param={:?}", param);
  97             if let ty::GenericParamDefKind::Lifetime = param.kind {
  98                 unused_parameters.clear(param.index);
  99             }
 100         }
 101     }
 102
 103     if let Some(parent) = generics.parent {
 104         mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
 105     }
 106 }
 107
 108 /// Search the predicates on used generic parameters for any unused generic parameters, and mark
 109 /// those as used.
 110 fn mark_used_by_predicates<'tcx>(
 111     tcx: TyCtxt<'tcx>,
 112     def_id: DefId,
 113     unused_parameters: &mut FiniteBitSet<u32>,
 114 ) {
 115     let def_id = tcx.closure_base_def_id(def_id);
 116
 117     let is_self_ty_used = |unused_parameters: &mut FiniteBitSet<u32>, self_ty: Ty<'tcx>| {
 118         debug!("unused_generic_params: self_ty={:?}", self_ty);
 119         if let ty::Param(param) = self_ty.kind {
 120             !unused_parameters.contains(param.index).unwrap_or(false)
 121         } else {
 122             false
 123         }
 124     };
 125
 126     let mark_ty = |unused_parameters: &mut FiniteBitSet<u32>, ty: Ty<'tcx>| {
 127         let mut vis = UsedGenericParametersVisitor { tcx, def_id, unused_parameters };
 128         ty.visit_with(&mut vis);
 129     };
 130
 131     let predicates = tcx.explicit_predicates_of(def_id);
 132     debug!("mark_parameters_used_in_predicates: predicates_of={:?}", predicates);
 133     for (predicate, _) in predicates.predicates {
 134         match predicate.skip_binders() {
 135             ty::PredicateAtom::Trait(predicate, ..) => {
 136                 let trait_ref = predicate.trait_ref;
 137                 if is_self_ty_used(unused_parameters, trait_ref.self_ty()) {
 138                     for ty in trait_ref.substs.types() {
 139                         debug!("unused_generic_params: (trait) ty={:?}", ty);
 140                         mark_ty(unused_parameters, ty);
 141                     }
 142                 }
 143             }
 144             ty::PredicateAtom::Projection(proj, ..) => {
 145                 let self_ty = proj.projection_ty.self_ty();
 146                 if is_self_ty_used(unused_parameters, self_ty) {
 147                     debug!("unused_generic_params: (projection ty={:?}", proj.ty);
 148                     mark_ty(unused_parameters, proj.ty);
 149                 }
 150             }
 151             _ => (),
 152         }
 153     }
 154 }
 155
 156 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 157 /// parameter which was unused.
 158 fn emit_unused_generic_params_error<'tcx>(
 159     tcx: TyCtxt<'tcx>,
 160     def_id: DefId,
 161     generics: &'tcx ty::Generics,
 162     unused_parameters: &FiniteBitSet<u32>,
 163 ) {
 164     debug!("emit_unused_generic_params_error: def_id={:?}", def_id);
 165     let base_def_id = tcx.closure_base_def_id(def_id);
 166     if !tcx.get_attrs(base_def_id).iter().any(|a| a.check_name(sym::rustc_polymorphize_error)) {
 167         return;
 168     }
 169
 170     debug!("emit_unused_generic_params_error: unused_parameters={:?}", unused_parameters);
 171     let fn_span = match tcx.opt_item_name(def_id) {
 172         Some(ident) => ident.span,
 173         _ => tcx.def_span(def_id),
 174     };
 175
 176     let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
 177
 178     let mut next_generics = Some(generics);
 179     while let Some(generics) = next_generics {
 180         for param in &generics.params {
 181             if unused_parameters.contains(param.index).unwrap_or(false) {
 182                 debug!("emit_unused_generic_params_error: param={:?}", param);
 183                 let def_span = tcx.def_span(param.def_id);
 184                 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
 185             }
 186         }
 187
 188         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 189     }
 190
 191     err.emit();
 192 }
 193
 194 /// Visitor used to aggregate generic parameter uses.
 195 struct UsedGenericParametersVisitor<'a, 'tcx> {
 196     tcx: TyCtxt<'tcx>,
 197     def_id: DefId,
 198     unused_parameters: &'a mut FiniteBitSet<u32>,
 199 }
 200
 201 impl<'a, 'tcx> Visitor<'tcx> for UsedGenericParametersVisitor<'a, 'tcx> {
 202     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 203         debug!("visit_local_decl: local_decl={:?}", local_decl);
 204         if local == Local::from_usize(1) {
 205             let def_kind = self.tcx.def_kind(self.def_id);
 206             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 207                 // Skip visiting the closure/generator that is currently being processed. This only
 208                 // happens because the first argument to the closure is a reference to itself and
 209                 // that will call `visit_substs`, resulting in each generic parameter captured being
 210                 // considered used by default.
 211                 debug!("visit_local_decl: skipping closure substs");
 212                 return;
 213             }
 214         }
 215
 216         self.super_local_decl(local, local_decl);
 217     }
 218
 219     fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
 220         c.visit_with(self);
 221     }
 222
 223     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 224         ty.visit_with(self);
 225     }
 226 }
 227
 228 impl<'a, 'tcx> TypeVisitor<'tcx> for UsedGenericParametersVisitor<'a, 'tcx> {
 229     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool {
 230         debug!("visit_const: c={:?}", c);
 231         if !c.has_param_types_or_consts() {
 232             return false;
 233         }
 234
 235         match c.val {
 236             ty::ConstKind::Param(param) => {
 237                 debug!("visit_const: param={:?}", param);
 238                 self.unused_parameters.clear(param.index);
 239                 false
 240             }
 241             _ => c.super_visit_with(self),
 242         }
 243     }
 244
 245     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 246         debug!("visit_ty: ty={:?}", ty);
 247         if !ty.has_param_types_or_consts() {
 248             return false;
 249         }
 250
 251         match ty.kind {
 252             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 253                 debug!("visit_ty: def_id={:?}", def_id);
 254                 // Avoid cycle errors with generators.
 255                 if def_id == self.def_id {
 256                     return false;
 257                 }
 258
 259                 // Consider any generic parameters used by any closures/generators as used in the
 260                 // parent.
 261                 let unused = self.tcx.unused_generic_params(def_id);
 262                 debug!(
 263                     "visit_ty: unused_parameters={:?} unused={:?}",
 264                     self.unused_parameters, unused
 265                 );
 266                 for (i, arg) in substs.iter().enumerate() {
 267                     let i = i.try_into().unwrap();
 268                     if !unused.contains(i).unwrap_or(false) {
 269                         arg.visit_with(self);
 270                     }
 271                 }
 272                 debug!("visit_ty: unused_parameters={:?}", self.unused_parameters);
 273
 274                 false
 275             }
 276             ty::Param(param) => {
 277                 debug!("visit_ty: param={:?}", param);
 278                 self.unused_parameters.clear(param.index);
 279                 false
 280             }
 281             _ => ty.super_visit_with(self),
 282         }
 283     }
 284 }