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

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