clippy_lints/src/implicit_hasher.rs

   1 use std::borrow::Cow;
   2 use std::collections::BTreeMap;
   3
   4 use rustc_errors::DiagnosticBuilder;
   5 use rustc_hir as hir;
   6 use rustc_hir::intravisit::{walk_body, walk_expr, walk_ty, NestedVisitorMap, Visitor};
   7 use rustc_hir::{Body, Expr, ExprKind, GenericArg, Item, ItemKind, QPath, TyKind};
   8 use rustc_lint::{LateContext, LateLintPass, LintContext};
   9 use rustc_middle::hir::map::Map;
  10 use rustc_middle::lint::in_external_macro;
  11 use rustc_middle::ty::{Ty, TyS, TypeckResults};
  12 use rustc_session::{declare_lint_pass, declare_tool_lint};
  13 use rustc_span::source_map::Span;
  14 use rustc_span::symbol::sym;
  15 use rustc_typeck::hir_ty_to_ty;
  16
  17 use if_chain::if_chain;
  18
  19 use clippy_utils::diagnostics::{multispan_sugg, span_lint_and_then};
  20 use clippy_utils::paths;
  21 use clippy_utils::source::{snippet, snippet_opt};
  22 use clippy_utils::ty::is_type_diagnostic_item;
  23 use clippy_utils::{differing_macro_contexts, match_def_path};
  24
  25 declare_clippy_lint! {
  26     /// **What it does:** Checks for public `impl` or `fn` missing generalization
  27     /// over different hashers and implicitly defaulting to the default hashing
  28     /// algorithm (`SipHash`).
  29     ///
  30     /// **Why is this bad?** `HashMap` or `HashSet` with custom hashers cannot be
  31     /// used with them.
  32     ///
  33     /// **Known problems:** Suggestions for replacing constructors can contain
  34     /// false-positives. Also applying suggestions can require modification of other
  35     /// pieces of code, possibly including external crates.
  36     ///
  37     /// **Example:**
  38     /// ```rust
  39     /// # use std::collections::HashMap;
  40     /// # use std::hash::{Hash, BuildHasher};
  41     /// # trait Serialize {};
  42     /// impl<K: Hash + Eq, V> Serialize for HashMap<K, V> { }
  43     ///
  44     /// pub fn foo(map: &mut HashMap<i32, i32>) { }
  45     /// ```
  46     /// could be rewritten as
  47     /// ```rust
  48     /// # use std::collections::HashMap;
  49     /// # use std::hash::{Hash, BuildHasher};
  50     /// # trait Serialize {};
  51     /// impl<K: Hash + Eq, V, S: BuildHasher> Serialize for HashMap<K, V, S> { }
  52     ///
  53     /// pub fn foo<S: BuildHasher>(map: &mut HashMap<i32, i32, S>) { }
  54     /// ```
  55     pub IMPLICIT_HASHER,
  56     pedantic,
  57     "missing generalization over different hashers"
  58 }
  59
  60 declare_lint_pass!(ImplicitHasher => [IMPLICIT_HASHER]);
  61
  62 impl<'tcx> LateLintPass<'tcx> for ImplicitHasher {
  63     #[allow(clippy::cast_possible_truncation, clippy::too_many_lines)]
  64     fn check_item(&mut self, cx: &LateContext<'tcx>, item: &'tcx Item<'_>) {
  65         use rustc_span::BytePos;
  66
  67         fn suggestion<'tcx>(
  68             cx: &LateContext<'tcx>,
  69             diag: &mut DiagnosticBuilder<'_>,
  70             generics_span: Span,
  71             generics_suggestion_span: Span,
  72             target: &ImplicitHasherType<'_>,
  73             vis: ImplicitHasherConstructorVisitor<'_, '_, '_>,
  74         ) {
  75             let generics_snip = snippet(cx, generics_span, "");
  76             // trim `<` `>`
  77             let generics_snip = if generics_snip.is_empty() {
  78                 ""
  79             } else {
  80                 &generics_snip[1..generics_snip.len() - 1]
  81             };
  82
  83             multispan_sugg(
  84                 diag,
  85                 "consider adding a type parameter",
  86                 vec![
  87                     (
  88                         generics_suggestion_span,
  89                         format!(
  90                             "<{}{}S: ::std::hash::BuildHasher{}>",
  91                             generics_snip,
  92                             if generics_snip.is_empty() { "" } else { ", " },
  93                             if vis.suggestions.is_empty() {
  94                                 ""
  95                             } else {
  96                                 // request users to add `Default` bound so that generic constructors can be used
  97                                 " + Default"
  98                             },
  99                         ),
 100                     ),
 101                     (
 102                         target.span(),
 103                         format!("{}<{}, S>", target.type_name(), target.type_arguments(),),
 104                     ),
 105                 ],
 106             );
 107
 108             if !vis.suggestions.is_empty() {
 109                 multispan_sugg(diag, "...and use generic constructor", vis.suggestions);
 110             }
 111         }
 112
 113         if !cx.access_levels.is_exported(item.hir_id()) {
 114             return;
 115         }
 116
 117         match item.kind {
 118             ItemKind::Impl(ref impl_) => {
 119                 let mut vis = ImplicitHasherTypeVisitor::new(cx);
 120                 vis.visit_ty(impl_.self_ty);
 121
 122                 for target in &vis.found {
 123                     if differing_macro_contexts(item.span, target.span()) {
 124                         return;
 125                     }
 126
 127                     let generics_suggestion_span = impl_.generics.span.substitute_dummy({
 128                         let pos = snippet_opt(cx, item.span.until(target.span()))
 129                             .and_then(|snip| Some(item.span.lo() + BytePos(snip.find("impl")? as u32 + 4)));
 130                         if let Some(pos) = pos {
 131                             Span::new(pos, pos, item.span.data().ctxt)
 132                         } else {
 133                             return;
 134                         }
 135                     });
 136
 137                     let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
 138                     for item in impl_.items.iter().map(|item| cx.tcx.hir().impl_item(item.id)) {
 139                         ctr_vis.visit_impl_item(item);
 140                     }
 141
 142                     span_lint_and_then(
 143                         cx,
 144                         IMPLICIT_HASHER,
 145                         target.span(),
 146                         &format!(
 147                             "impl for `{}` should be generalized over different hashers",
 148                             target.type_name()
 149                         ),
 150                         move |diag| {
 151                             suggestion(cx, diag, impl_.generics.span, generics_suggestion_span, target, ctr_vis);
 152                         },
 153                     );
 154                 }
 155             },
 156             ItemKind::Fn(ref sig, ref generics, body_id) => {
 157                 let body = cx.tcx.hir().body(body_id);
 158
 159                 for ty in sig.decl.inputs {
 160                     let mut vis = ImplicitHasherTypeVisitor::new(cx);
 161                     vis.visit_ty(ty);
 162
 163                     for target in &vis.found {
 164                         if in_external_macro(cx.sess(), generics.span) {
 165                             continue;
 166                         }
 167                         let generics_suggestion_span = generics.span.substitute_dummy({
 168                             let pos = snippet_opt(cx, item.span.until(body.params[0].pat.span))
 169                                 .and_then(|snip| {
 170                                     let i = snip.find("fn")?;
 171                                     Some(item.span.lo() + BytePos((i + (&snip[i..]).find('(')?) as u32))
 172                                 })
 173                                 .expect("failed to create span for type parameters");
 174                             Span::new(pos, pos, item.span.data().ctxt)
 175                         });
 176
 177                         let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
 178                         ctr_vis.visit_body(body);
 179
 180                         span_lint_and_then(
 181                             cx,
 182                             IMPLICIT_HASHER,
 183                             target.span(),
 184                             &format!(
 185                                 "parameter of type `{}` should be generalized over different hashers",
 186                                 target.type_name()
 187                             ),
 188                             move |diag| {
 189                                 suggestion(cx, diag, generics.span, generics_suggestion_span, target, ctr_vis);
 190                             },
 191                         );
 192                     }
 193                 }
 194             },
 195             _ => {},
 196         }
 197     }
 198 }
 199
 200 enum ImplicitHasherType<'tcx> {
 201     HashMap(Span, Ty<'tcx>, Cow<'static, str>, Cow<'static, str>),
 202     HashSet(Span, Ty<'tcx>, Cow<'static, str>),
 203 }
 204
 205 impl<'tcx> ImplicitHasherType<'tcx> {
 206     /// Checks that `ty` is a target type without a `BuildHasher`.
 207     fn new(cx: &LateContext<'tcx>, hir_ty: &hir::Ty<'_>) -> Option<Self> {
 208         if let TyKind::Path(QPath::Resolved(None, path)) = hir_ty.kind {
 209             let params: Vec<_> = path
 210                 .segments
 211                 .last()
 212                 .as_ref()?
 213                 .args
 214                 .as_ref()?
 215                 .args
 216                 .iter()
 217                 .filter_map(|arg| match arg {
 218                     GenericArg::Type(ty) => Some(ty),
 219                     _ => None,
 220                 })
 221                 .collect();
 222             let params_len = params.len();
 223
 224             let ty = hir_ty_to_ty(cx.tcx, hir_ty);
 225
 226             if is_type_diagnostic_item(cx, ty, sym::hashmap_type) && params_len == 2 {
 227                 Some(ImplicitHasherType::HashMap(
 228                     hir_ty.span,
 229                     ty,
 230                     snippet(cx, params[0].span, "K"),
 231                     snippet(cx, params[1].span, "V"),
 232                 ))
 233             } else if is_type_diagnostic_item(cx, ty, sym::hashset_type) && params_len == 1 {
 234                 Some(ImplicitHasherType::HashSet(
 235                     hir_ty.span,
 236                     ty,
 237                     snippet(cx, params[0].span, "T"),
 238                 ))
 239             } else {
 240                 None
 241             }
 242         } else {
 243             None
 244         }
 245     }
 246
 247     fn type_name(&self) -> &'static str {
 248         match *self {
 249             ImplicitHasherType::HashMap(..) => "HashMap",
 250             ImplicitHasherType::HashSet(..) => "HashSet",
 251         }
 252     }
 253
 254     fn type_arguments(&self) -> String {
 255         match *self {
 256             ImplicitHasherType::HashMap(.., ref k, ref v) => format!("{}, {}", k, v),
 257             ImplicitHasherType::HashSet(.., ref t) => format!("{}", t),
 258         }
 259     }
 260
 261     fn ty(&self) -> Ty<'tcx> {
 262         match *self {
 263             ImplicitHasherType::HashMap(_, ty, ..) | ImplicitHasherType::HashSet(_, ty, ..) => ty,
 264         }
 265     }
 266
 267     fn span(&self) -> Span {
 268         match *self {
 269             ImplicitHasherType::HashMap(span, ..) | ImplicitHasherType::HashSet(span, ..) => span,
 270         }
 271     }
 272 }
 273
 274 struct ImplicitHasherTypeVisitor<'a, 'tcx> {
 275     cx: &'a LateContext<'tcx>,
 276     found: Vec<ImplicitHasherType<'tcx>>,
 277 }
 278
 279 impl<'a, 'tcx> ImplicitHasherTypeVisitor<'a, 'tcx> {
 280     fn new(cx: &'a LateContext<'tcx>) -> Self {
 281         Self { cx, found: vec![] }
 282     }
 283 }
 284
 285 impl<'a, 'tcx> Visitor<'tcx> for ImplicitHasherTypeVisitor<'a, 'tcx> {
 286     type Map = Map<'tcx>;
 287
 288     fn visit_ty(&mut self, t: &'tcx hir::Ty<'_>) {
 289         if let Some(target) = ImplicitHasherType::new(self.cx, t) {
 290             self.found.push(target);
 291         }
 292
 293         walk_ty(self, t);
 294     }
 295
 296     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 297         NestedVisitorMap::None
 298     }
 299 }
 300
 301 /// Looks for default-hasher-dependent constructors like `HashMap::new`.
 302 struct ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
 303     cx: &'a LateContext<'tcx>,
 304     maybe_typeck_results: Option<&'tcx TypeckResults<'tcx>>,
 305     target: &'b ImplicitHasherType<'tcx>,
 306     suggestions: BTreeMap<Span, String>,
 307 }
 308
 309 impl<'a, 'b, 'tcx> ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
 310     fn new(cx: &'a LateContext<'tcx>, target: &'b ImplicitHasherType<'tcx>) -> Self {
 311         Self {
 312             cx,
 313             maybe_typeck_results: cx.maybe_typeck_results(),
 314             target,
 315             suggestions: BTreeMap::new(),
 316         }
 317     }
 318 }
 319
 320 impl<'a, 'b, 'tcx> Visitor<'tcx> for ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
 321     type Map = Map<'tcx>;
 322
 323     fn visit_body(&mut self, body: &'tcx Body<'_>) {
 324         let old_maybe_typeck_results = self.maybe_typeck_results.replace(self.cx.tcx.typeck_body(body.id()));
 325         walk_body(self, body);
 326         self.maybe_typeck_results = old_maybe_typeck_results;
 327     }
 328
 329     fn visit_expr(&mut self, e: &'tcx Expr<'_>) {
 330         if_chain! {
 331             if let ExprKind::Call(fun, args) = e.kind;
 332             if let ExprKind::Path(QPath::TypeRelative(ty, method)) = fun.kind;
 333             if let TyKind::Path(QPath::Resolved(None, ty_path)) = ty.kind;
 334             if let Some(ty_did) = ty_path.res.opt_def_id();
 335             then {
 336                 if !TyS::same_type(self.target.ty(), self.maybe_typeck_results.unwrap().expr_ty(e)) {
 337                     return;
 338                 }
 339
 340                 if match_def_path(self.cx, ty_did, &paths::HASHMAP) {
 341                     if method.ident.name == sym::new {
 342                         self.suggestions
 343                             .insert(e.span, "HashMap::default()".to_string());
 344                     } else if method.ident.name == sym!(with_capacity) {
 345                         self.suggestions.insert(
 346                             e.span,
 347                             format!(
 348                                 "HashMap::with_capacity_and_hasher({}, Default::default())",
 349                                 snippet(self.cx, args[0].span, "capacity"),
 350                             ),
 351                         );
 352                     }
 353                 } else if match_def_path(self.cx, ty_did, &paths::HASHSET) {
 354                     if method.ident.name == sym::new {
 355                         self.suggestions
 356                             .insert(e.span, "HashSet::default()".to_string());
 357                     } else if method.ident.name == sym!(with_capacity) {
 358                         self.suggestions.insert(
 359                             e.span,
 360                             format!(
 361                                 "HashSet::with_capacity_and_hasher({}, Default::default())",
 362                                 snippet(self.cx, args[0].span, "capacity"),
 363                             ),
 364                         );
 365                     }
 366                 }
 367             }
 368         }
 369
 370         walk_expr(self, e);
 371     }
 372
 373     fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
 374         NestedVisitorMap::OnlyBodies(self.cx.tcx.hir())
 375     }
 376 }