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