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_hir_analysis::hir_ty_to_ty;
   9 use rustc_lint::{LateContext, LateLintPass, LintContext};
  10 use rustc_middle::hir::nested_filter;
  11 use rustc_middle::lint::in_external_macro;
  12 use rustc_middle::ty::{Ty, TypeckResults};
  13 use rustc_session::{declare_lint_pass, declare_tool_lint};
  14 use rustc_span::source_map::Span;
  15 use rustc_span::symbol::sym;
  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     #[expect(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(
  70             cx: &LateContext<'_>,
  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                             "<{generics_snip}{}S: ::std::hash::BuildHasher{}>",
  93                             if generics_snip.is_empty() { "" } else { ", " },
  94                             if vis.suggestions.is_empty() {
  95                                 ""
  96                             } else {
  97                                 // request users to add `Default` bound so that generic constructors can be used
  98                                 " + Default"
  99                             },
 100                         ),
 101                     ),
 102                     (
 103                         target.span(),
 104                         format!("{}<{}, S>", target.type_name(), target.type_arguments(),),
 105                     ),
 106                 ],
 107             );
 108
 109             if !vis.suggestions.is_empty() {
 110                 multispan_sugg(diag, "...and use generic constructor", vis.suggestions);
 111             }
 112         }
 113
 114         if !cx.effective_visibilities.is_exported(item.owner_id.def_id) {
 115             return;
 116         }
 117
 118         match item.kind {
 119             ItemKind::Impl(impl_) => {
 120                 let mut vis = ImplicitHasherTypeVisitor::new(cx);
 121                 vis.visit_ty(impl_.self_ty);
 122
 123                 for target in &vis.found {
 124                     if item.span.ctxt() != target.span().ctxt() {
 125                         return;
 126                     }
 127
 128                     let generics_suggestion_span = impl_.generics.span.substitute_dummy({
 129                         let pos = snippet_opt(cx, item.span.until(target.span()))
 130                             .and_then(|snip| Some(item.span.lo() + BytePos(snip.find("impl")? as u32 + 4)));
 131                         if let Some(pos) = pos {
 132                             Span::new(pos, pos, item.span.ctxt(), item.span.parent())
 133                         } else {
 134                             return;
 135                         }
 136                     });
 137
 138                     let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
 139                     for item in impl_.items.iter().map(|item| cx.tcx.hir().impl_item(item.id)) {
 140                         ctr_vis.visit_impl_item(item);
 141                     }
 142
 143                     span_lint_and_then(
 144                         cx,
 145                         IMPLICIT_HASHER,
 146                         target.span(),
 147                         &format!(
 148                             "impl for `{}` should be generalized over different hashers",
 149                             target.type_name()
 150                         ),
 151                         move |diag| {
 152                             suggestion(cx, diag, impl_.generics.span, generics_suggestion_span, target, ctr_vis);
 153                         },
 154                     );
 155                 }
 156             },
 157             ItemKind::Fn(ref sig, generics, body_id) => {
 158                 let body = cx.tcx.hir().body(body_id);
 159
 160                 for ty in sig.decl.inputs {
 161                     let mut vis = ImplicitHasherTypeVisitor::new(cx);
 162                     vis.visit_ty(ty);
 163
 164                     for target in &vis.found {
 165                         if in_external_macro(cx.sess(), generics.span) {
 166                             continue;
 167                         }
 168                         let generics_suggestion_span = generics.span.substitute_dummy({
 169                             let pos = snippet_opt(
 170                                 cx,
 171                                 Span::new(
 172                                     item.span.lo(),
 173                                     body.params[0].pat.span.lo(),
 174                                     item.span.ctxt(),
 175                                     item.span.parent(),
 176                                 ),
 177                             )
 178                             .and_then(|snip| {
 179                                 let i = snip.find("fn")?;
 180                                 Some(item.span.lo() + BytePos((i + snip[i..].find('(')?) as u32))
 181                             })
 182                             .expect("failed to create span for type parameters");
 183                             Span::new(pos, pos, item.span.ctxt(), item.span.parent())
 184                         });
 185
 186                         let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
 187                         ctr_vis.visit_body(body);
 188
 189                         span_lint_and_then(
 190                             cx,
 191                             IMPLICIT_HASHER,
 192                             target.span(),
 193                             &format!(
 194                                 "parameter of type `{}` should be generalized over different hashers",
 195                                 target.type_name()
 196                             ),
 197                             move |diag| {
 198                                 suggestion(cx, diag, generics.span, generics_suggestion_span, target, ctr_vis);
 199                             },
 200                         );
 201                     }
 202                 }
 203             },
 204             _ => {},
 205         }
 206     }
 207 }
 208
 209 enum ImplicitHasherType<'tcx> {
 210     HashMap(Span, Ty<'tcx>, Cow<'static, str>, Cow<'static, str>),
 211     HashSet(Span, Ty<'tcx>, Cow<'static, str>),
 212 }
 213
 214 impl<'tcx> ImplicitHasherType<'tcx> {
 215     /// Checks that `ty` is a target type without a `BuildHasher`.
 216     fn new(cx: &LateContext<'tcx>, hir_ty: &hir::Ty<'_>) -> Option<Self> {
 217         if let TyKind::Path(QPath::Resolved(None, path)) = hir_ty.kind {
 218             let params: Vec<_> = path
 219                 .segments
 220                 .last()
 221                 .as_ref()?
 222                 .args
 223                 .as_ref()?
 224                 .args
 225                 .iter()
 226                 .filter_map(|arg| match arg {
 227                     GenericArg::Type(ty) => Some(ty),
 228                     _ => None,
 229                 })
 230                 .collect();
 231             let params_len = params.len();
 232
 233             let ty = hir_ty_to_ty(cx.tcx, hir_ty);
 234
 235             if is_type_diagnostic_item(cx, ty, sym::HashMap) && params_len == 2 {
 236                 Some(ImplicitHasherType::HashMap(
 237                     hir_ty.span,
 238                     ty,
 239                     snippet(cx, params[0].span, "K"),
 240                     snippet(cx, params[1].span, "V"),
 241                 ))
 242             } else if is_type_diagnostic_item(cx, ty, sym::HashSet) && params_len == 1 {
 243                 Some(ImplicitHasherType::HashSet(
 244                     hir_ty.span,
 245                     ty,
 246                     snippet(cx, params[0].span, "T"),
 247                 ))
 248             } else {
 249                 None
 250             }
 251         } else {
 252             None
 253         }
 254     }
 255
 256     fn type_name(&self) -> &'static str {
 257         match *self {
 258             ImplicitHasherType::HashMap(..) => "HashMap",
 259             ImplicitHasherType::HashSet(..) => "HashSet",
 260         }
 261     }
 262
 263     fn type_arguments(&self) -> String {
 264         match *self {
 265             ImplicitHasherType::HashMap(.., ref k, ref v) => format!("{k}, {v}"),
 266             ImplicitHasherType::HashSet(.., ref t) => format!("{t}"),
 267         }
 268     }
 269
 270     fn ty(&self) -> Ty<'tcx> {
 271         match *self {
 272             ImplicitHasherType::HashMap(_, ty, ..) | ImplicitHasherType::HashSet(_, ty, ..) => ty,
 273         }
 274     }
 275
 276     fn span(&self) -> Span {
 277         match *self {
 278             ImplicitHasherType::HashMap(span, ..) | ImplicitHasherType::HashSet(span, ..) => span,
 279         }
 280     }
 281 }
 282
 283 struct ImplicitHasherTypeVisitor<'a, 'tcx> {
 284     cx: &'a LateContext<'tcx>,
 285     found: Vec<ImplicitHasherType<'tcx>>,
 286 }
 287
 288 impl<'a, 'tcx> ImplicitHasherTypeVisitor<'a, 'tcx> {
 289     fn new(cx: &'a LateContext<'tcx>) -> Self {
 290         Self { cx, found: vec![] }
 291     }
 292 }
 293
 294 impl<'a, 'tcx> Visitor<'tcx> for ImplicitHasherTypeVisitor<'a, 'tcx> {
 295     fn visit_ty(&mut self, t: &'tcx hir::Ty<'_>) {
 296         if let Some(target) = ImplicitHasherType::new(self.cx, t) {
 297             self.found.push(target);
 298         }
 299
 300         walk_ty(self, t);
 301     }
 302
 303     fn visit_infer(&mut self, inf: &'tcx hir::InferArg) {
 304         if let Some(target) = ImplicitHasherType::new(self.cx, &inf.to_ty()) {
 305             self.found.push(target);
 306         }
 307
 308         walk_inf(self, inf);
 309     }
 310 }
 311
 312 /// Looks for default-hasher-dependent constructors like `HashMap::new`.
 313 struct ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
 314     cx: &'a LateContext<'tcx>,
 315     maybe_typeck_results: Option<&'tcx TypeckResults<'tcx>>,
 316     target: &'b ImplicitHasherType<'tcx>,
 317     suggestions: BTreeMap<Span, String>,
 318 }
 319
 320 impl<'a, 'b, 'tcx> ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
 321     fn new(cx: &'a LateContext<'tcx>, target: &'b ImplicitHasherType<'tcx>) -> Self {
 322         Self {
 323             cx,
 324             maybe_typeck_results: cx.maybe_typeck_results(),
 325             target,
 326             suggestions: BTreeMap::new(),
 327         }
 328     }
 329 }
 330
 331 impl<'a, 'b, 'tcx> Visitor<'tcx> for ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
 332     type NestedFilter = nested_filter::OnlyBodies;
 333
 334     fn visit_body(&mut self, body: &'tcx Body<'_>) {
 335         let old_maybe_typeck_results = self.maybe_typeck_results.replace(self.cx.tcx.typeck_body(body.id()));
 336         walk_body(self, body);
 337         self.maybe_typeck_results = old_maybe_typeck_results;
 338     }
 339
 340     fn visit_expr(&mut self, e: &'tcx Expr<'_>) {
 341         if_chain! {
 342             if let ExprKind::Call(fun, args) = e.kind;
 343             if let ExprKind::Path(QPath::TypeRelative(ty, method)) = fun.kind;
 344             if let TyKind::Path(QPath::Resolved(None, ty_path)) = ty.kind;
 345             if let Some(ty_did) = ty_path.res.opt_def_id();
 346             then {
 347                 if self.target.ty() != self.maybe_typeck_results.unwrap().expr_ty(e) {
 348                     return;
 349                 }
 350
 351                 if self.cx.tcx.is_diagnostic_item(sym::HashMap, ty_did) {
 352                     if method.ident.name == sym::new {
 353                         self.suggestions
 354                             .insert(e.span, "HashMap::default()".to_string());
 355                     } else if method.ident.name == sym!(with_capacity) {
 356                         self.suggestions.insert(
 357                             e.span,
 358                             format!(
 359                                 "HashMap::with_capacity_and_hasher({}, Default::default())",
 360                                 snippet(self.cx, args[0].span, "capacity"),
 361                             ),
 362                         );
 363                     }
 364                 } else if self.cx.tcx.is_diagnostic_item(sym::HashSet, ty_did) {
 365                     if method.ident.name == sym::new {
 366                         self.suggestions
 367                             .insert(e.span, "HashSet::default()".to_string());
 368                     } else if method.ident.name == sym!(with_capacity) {
 369                         self.suggestions.insert(
 370                             e.span,
 371                             format!(
 372                                 "HashSet::with_capacity_and_hasher({}, Default::default())",
 373                                 snippet(self.cx, args[0].span, "capacity"),
 374                             ),
 375                         );
 376                     }
 377                 }
 378             }
 379         }
 380
 381         walk_expr(self, e);
 382     }
 383
 384     fn nested_visit_map(&mut self) -> Self::Map {
 385         self.cx.tcx.hir()
 386     }
 387 }