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