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 = MarkUsedGenericParams { tcx, def_id, unused_parameters: &mut unused_parameters };
  73     vis.visit_body(body);
  74     debug!("unused_generic_params: (after visitor) unused_parameters={:?}", unused_parameters);
  75
  76     mark_used_by_predicates(tcx, def_id, &mut unused_parameters);
  77     debug!("unused_generic_params: (end) unused_parameters={:?}", unused_parameters);
  78
  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);
  82     }
  83
  84     unused_parameters
  85 }
  86
  87 /// Some parameters are considered used-by-default, such as non-generic parameters and the dummy
  88 /// generic parameters from closures, this function marks them as used. `leaf_is_closure` should
  89 /// be `true` if the item that `unused_generic_params` was invoked on is a closure.
  90 fn mark_used_by_default_parameters<'tcx>(
  91     tcx: TyCtxt<'tcx>,
  92     def_id: DefId,
  93     generics: &'tcx ty::Generics,
  94     unused_parameters: &mut FiniteBitSet<u32>,
  95 ) {
  96     if !tcx.is_trait(def_id) && (tcx.is_closure(def_id) || tcx.type_of(def_id).is_generator()) {
  97         for param in &generics.params {
  98             debug!("mark_used_by_default_parameters: (closure/gen) param={:?}", param);
  99             unused_parameters.clear(param.index);
 100         }
 101     } else {
 102         for param in &generics.params {
 103             debug!("mark_used_by_default_parameters: (other) param={:?}", param);
 104             if let ty::GenericParamDefKind::Lifetime = param.kind {
 105                 unused_parameters.clear(param.index);
 106             }
 107         }
 108     }
 109
 110     if let Some(parent) = generics.parent {
 111         mark_used_by_default_parameters(tcx, parent, tcx.generics_of(parent), unused_parameters);
 112     }
 113 }
 114
 115 /// Search the predicates on used generic parameters for any unused generic parameters, and mark
 116 /// those as used.
 117 fn mark_used_by_predicates<'tcx>(
 118     tcx: TyCtxt<'tcx>,
 119     def_id: DefId,
 120     unused_parameters: &mut FiniteBitSet<u32>,
 121 ) {
 122     let is_ty_used = |unused_parameters: &FiniteBitSet<u32>, ty: Ty<'tcx>| -> bool {
 123         let mut vis = IsUsedGenericParams { unused_parameters };
 124         ty.visit_with(&mut vis)
 125     };
 126
 127     let mark_ty = |unused_parameters: &mut FiniteBitSet<u32>, ty: Ty<'tcx>| {
 128         let mut vis = MarkUsedGenericParams { tcx, def_id, unused_parameters };
 129         ty.visit_with(&mut vis);
 130     };
 131
 132     let def_id = tcx.closure_base_def_id(def_id);
 133     let predicates = tcx.explicit_predicates_of(def_id);
 134     debug!("mark_used_by_predicates: predicates_of={:?}", predicates);
 135
 136     let mut current_unused_parameters = FiniteBitSet::new_empty();
 137     // Run to a fixed point to support `where T: Trait<U>, U: Trait<V>`, starting with an empty
 138     // bit set so that this is skipped if all parameters are already used.
 139     while current_unused_parameters != *unused_parameters {
 140         debug!(
 141             "mark_used_by_predicates: current_unused_parameters={:?} = unused_parameters={:?}",
 142             current_unused_parameters, unused_parameters
 143         );
 144         current_unused_parameters = *unused_parameters;
 145
 146         for (predicate, _) in predicates.predicates {
 147             match predicate.skip_binders() {
 148                 ty::PredicateAtom::Trait(predicate, ..) => {
 149                     let trait_ref = predicate.trait_ref;
 150                     debug!("mark_used_by_predicates: (trait) trait_ref={:?}", trait_ref);
 151
 152                     // Consider `T` used if `I` is used in predicates of the form
 153                     // `I: Iterator<Item = T>`
 154                     debug!("mark_used_by_predicates: checking self");
 155                     if is_ty_used(unused_parameters, trait_ref.self_ty()) {
 156                         debug!("mark_used_by_predicates: used!");
 157                         for ty in trait_ref.substs.types() {
 158                             mark_ty(unused_parameters, ty);
 159                         }
 160
 161                         // No need to check for a type being used in the substs if `self_ty` was
 162                         // used.
 163                         continue;
 164                     }
 165
 166                     // Consider `I` used if `T` is used in predicates of the form
 167                     // `I: Iterator<Item = &'a (T, E)>` (see rust-lang/rust#75326)
 168                     debug!("mark_used_by_predicates: checking substs");
 169                     for ty in trait_ref.substs.types() {
 170                         if is_ty_used(unused_parameters, ty) {
 171                             debug!("mark_used_by_predicates: used!");
 172                             mark_ty(unused_parameters, trait_ref.self_ty());
 173                         }
 174                     }
 175                 }
 176                 ty::PredicateAtom::Projection(proj, ..) => {
 177                     let self_ty = proj.projection_ty.self_ty();
 178                     debug!(
 179                         "mark_used_by_predicates: (projection) self_ty={:?} proj.ty={:?}",
 180                         self_ty, proj.ty
 181                     );
 182
 183                     // Consider `T` used if `I` is used in predicates of the form
 184                     // `<I as Iterator>::Item = T`
 185                     debug!("mark_used_by_predicates: checking self");
 186                     if is_ty_used(unused_parameters, self_ty) {
 187                         debug!("mark_used_by_predicates: used!");
 188                         mark_ty(unused_parameters, proj.ty);
 189
 190                         // No need to check for projection type being used if `self_ty` was used.
 191                         continue;
 192                     }
 193
 194                     // Consider `I` used if `T` is used in predicates of the form
 195                     // `<I as Iterator>::Item = &'a (T, E)` (see rust-lang/rust#75326)
 196                     debug!("mark_used_by_predicates: checking projection ty");
 197                     if is_ty_used(unused_parameters, proj.ty) {
 198                         debug!("mark_used_by_predicates: used!");
 199                         mark_ty(unused_parameters, self_ty);
 200                     }
 201                 }
 202                 ty::PredicateAtom::RegionOutlives(..)
 203                 | ty::PredicateAtom::TypeOutlives(..)
 204                 | ty::PredicateAtom::WellFormed(..)
 205                 | ty::PredicateAtom::ObjectSafe(..)
 206                 | ty::PredicateAtom::ClosureKind(..)
 207                 | ty::PredicateAtom::Subtype(..)
 208                 | ty::PredicateAtom::ConstEvaluatable(..)
 209                 | ty::PredicateAtom::ConstEquate(..) => (),
 210             }
 211         }
 212     }
 213
 214     if let Some(parent) = predicates.parent {
 215         mark_used_by_predicates(tcx, parent, unused_parameters);
 216     }
 217 }
 218
 219 /// Emit errors for the function annotated by `#[rustc_polymorphize_error]`, labelling each generic
 220 /// parameter which was unused.
 221 fn emit_unused_generic_params_error<'tcx>(
 222     tcx: TyCtxt<'tcx>,
 223     def_id: DefId,
 224     generics: &'tcx ty::Generics,
 225     unused_parameters: &FiniteBitSet<u32>,
 226 ) {
 227     debug!("emit_unused_generic_params_error: def_id={:?}", def_id);
 228     let base_def_id = tcx.closure_base_def_id(def_id);
 229     if !tcx
 230         .get_attrs(base_def_id)
 231         .iter()
 232         .any(|a| tcx.sess.check_name(a, sym::rustc_polymorphize_error))
 233     {
 234         return;
 235     }
 236
 237     debug!("emit_unused_generic_params_error: unused_parameters={:?}", unused_parameters);
 238     let fn_span = match tcx.opt_item_name(def_id) {
 239         Some(ident) => ident.span,
 240         _ => tcx.def_span(def_id),
 241     };
 242
 243     let mut err = tcx.sess.struct_span_err(fn_span, "item has unused generic parameters");
 244
 245     let mut next_generics = Some(generics);
 246     while let Some(generics) = next_generics {
 247         for param in &generics.params {
 248             if unused_parameters.contains(param.index).unwrap_or(false) {
 249                 debug!("emit_unused_generic_params_error: param={:?}", param);
 250                 let def_span = tcx.def_span(param.def_id);
 251                 err.span_label(def_span, &format!("generic parameter `{}` is unused", param.name));
 252             }
 253         }
 254
 255         next_generics = generics.parent.map(|did| tcx.generics_of(did));
 256     }
 257
 258     err.emit();
 259 }
 260
 261 /// Visitor used to aggregate generic parameter uses.
 262 struct MarkUsedGenericParams<'a, 'tcx> {
 263     tcx: TyCtxt<'tcx>,
 264     def_id: DefId,
 265     unused_parameters: &'a mut FiniteBitSet<u32>,
 266 }
 267
 268 impl<'a, 'tcx> MarkUsedGenericParams<'a, 'tcx> {
 269     /// Invoke `unused_generic_params` on a body contained within the current item (e.g.
 270     /// a closure, generator or constant).
 271     fn visit_child_body(&mut self, def_id: DefId, substs: SubstsRef<'tcx>) {
 272         let unused = self.tcx.unused_generic_params(def_id);
 273         debug!(
 274             "visit_child_body: unused_parameters={:?} unused={:?}",
 275             self.unused_parameters, unused
 276         );
 277         for (i, arg) in substs.iter().enumerate() {
 278             let i = i.try_into().unwrap();
 279             if !unused.contains(i).unwrap_or(false) {
 280                 arg.visit_with(self);
 281             }
 282         }
 283         debug!("visit_child_body: unused_parameters={:?}", self.unused_parameters);
 284     }
 285 }
 286
 287 impl<'a, 'tcx> Visitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 288     fn visit_local_decl(&mut self, local: Local, local_decl: &LocalDecl<'tcx>) {
 289         debug!("visit_local_decl: local_decl={:?}", local_decl);
 290         if local == Local::from_usize(1) {
 291             let def_kind = self.tcx.def_kind(self.def_id);
 292             if matches!(def_kind, DefKind::Closure | DefKind::Generator) {
 293                 // Skip visiting the closure/generator that is currently being processed. This only
 294                 // happens because the first argument to the closure is a reference to itself and
 295                 // that will call `visit_substs`, resulting in each generic parameter captured being
 296                 // considered used by default.
 297                 debug!("visit_local_decl: skipping closure substs");
 298                 return;
 299             }
 300         }
 301
 302         self.super_local_decl(local, local_decl);
 303     }
 304
 305     fn visit_const(&mut self, c: &&'tcx Const<'tcx>, _: Location) {
 306         c.visit_with(self);
 307     }
 308
 309     fn visit_ty(&mut self, ty: Ty<'tcx>, _: TyContext) {
 310         ty.visit_with(self);
 311     }
 312 }
 313
 314 impl<'a, 'tcx> TypeVisitor<'tcx> for MarkUsedGenericParams<'a, 'tcx> {
 315     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool {
 316         debug!("visit_const: c={:?}", c);
 317         if !c.has_param_types_or_consts() {
 318             return false;
 319         }
 320
 321         match c.val {
 322             ty::ConstKind::Param(param) => {
 323                 debug!("visit_const: param={:?}", param);
 324                 self.unused_parameters.clear(param.index);
 325                 false
 326             }
 327             ty::ConstKind::Unevaluated(def, _, Some(p))
 328                 // Avoid considering `T` unused when constants are of the form:
 329                 //   `<Self as Foo<T>>::foo::promoted[p]`
 330                 if self.def_id == def.did && !self.tcx.generics_of(def.did).has_self =>
 331             {
 332                 // If there is a promoted, don't look at the substs - since it will always contain
 333                 // the generic parameters, instead, traverse the promoted MIR.
 334                 let promoted = self.tcx.promoted_mir(def.did);
 335                 self.visit_body(&promoted[p]);
 336                 false
 337             }
 338             ty::ConstKind::Unevaluated(def, unevaluated_substs, None)
 339                 if self.tcx.def_kind(def.did) == DefKind::AnonConst =>
 340             {
 341                 self.visit_child_body(def.did, unevaluated_substs);
 342                 false
 343             }
 344             _ => c.super_visit_with(self),
 345         }
 346     }
 347
 348     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 349         debug!("visit_ty: ty={:?}", ty);
 350         if !ty.has_param_types_or_consts() {
 351             return false;
 352         }
 353
 354         match ty.kind {
 355             ty::Closure(def_id, substs) | ty::Generator(def_id, substs, ..) => {
 356                 debug!("visit_ty: def_id={:?}", def_id);
 357                 // Avoid cycle errors with generators.
 358                 if def_id == self.def_id {
 359                     return false;
 360                 }
 361
 362                 // Consider any generic parameters used by any closures/generators as used in the
 363                 // parent.
 364                 self.visit_child_body(def_id, substs);
 365                 false
 366             }
 367             ty::Param(param) => {
 368                 debug!("visit_ty: param={:?}", param);
 369                 self.unused_parameters.clear(param.index);
 370                 false
 371             }
 372             _ => ty.super_visit_with(self),
 373         }
 374     }
 375 }
 376
 377 /// Visitor used to check if a generic parameter is used.
 378 struct IsUsedGenericParams<'a> {
 379     unused_parameters: &'a FiniteBitSet<u32>,
 380 }
 381
 382 impl<'a, 'tcx> TypeVisitor<'tcx> for IsUsedGenericParams<'a> {
 383     fn visit_const(&mut self, c: &'tcx Const<'tcx>) -> bool {
 384         debug!("visit_const: c={:?}", c);
 385         if !c.has_param_types_or_consts() {
 386             return false;
 387         }
 388
 389         match c.val {
 390             ty::ConstKind::Param(param) => {
 391                 !self.unused_parameters.contains(param.index).unwrap_or(false)
 392             }
 393             _ => c.super_visit_with(self),
 394         }
 395     }
 396
 397     fn visit_ty(&mut self, ty: Ty<'tcx>) -> bool {
 398         debug!("visit_ty: ty={:?}", ty);
 399         if !ty.has_param_types_or_consts() {
 400             return false;
 401         }
 402
 403         match ty.kind {
 404             ty::Param(param) => !self.unused_parameters.contains(param.index).unwrap_or(false),
 405             _ => ty.super_visit_with(self),
 406         }
 407     }
 408 }