src/tools/clippy/clippy_lints/src/implicit_hasher.rs

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