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