2 use std::collections::BTreeMap;
4 use rustc_errors::DiagnosticBuilder;
6 use rustc_hir::intravisit::{walk_body, walk_expr, walk_inf, 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;
17 use if_chain::if_chain;
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;
24 declare_clippy_lint! {
26 /// Checks for public `impl` or `fn` missing generalization
27 /// over different hashers and implicitly defaulting to the default hashing
28 /// algorithm (`SipHash`).
30 /// ### Why is this bad?
31 /// `HashMap` or `HashSet` with custom hashers cannot be
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.
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> { }
46 /// pub fn foo(map: &mut HashMap<i32, i32>) { }
48 /// could be rewritten as
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> { }
55 /// pub fn foo<S: BuildHasher>(map: &mut HashMap<i32, i32, S>) { }
59 "missing generalization over different hashers"
62 declare_lint_pass!(ImplicitHasher => [IMPLICIT_HASHER]);
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;
70 cx: &LateContext<'tcx>,
71 diag: &mut DiagnosticBuilder<'_>,
73 generics_suggestion_span: Span,
74 target: &ImplicitHasherType<'_>,
75 vis: ImplicitHasherConstructorVisitor<'_, '_, '_>,
77 let generics_snip = snippet(cx, generics_span, "");
79 let generics_snip = if generics_snip.is_empty() {
82 &generics_snip[1..generics_snip.len() - 1]
87 "consider adding a type parameter",
90 generics_suggestion_span,
92 "<{}{}S: ::std::hash::BuildHasher{}>",
94 if generics_snip.is_empty() { "" } else { ", " },
95 if vis.suggestions.is_empty() {
98 // request users to add `Default` bound so that generic constructors can be used
105 format!("{}<{}, S>", target.type_name(), target.type_arguments(),),
110 if !vis.suggestions.is_empty() {
111 multispan_sugg(diag, "...and use generic constructor", vis.suggestions);
115 if !cx.access_levels.is_exported(item.def_id) {
120 ItemKind::Impl(ref impl_) => {
121 let mut vis = ImplicitHasherTypeVisitor::new(cx);
122 vis.visit_ty(impl_.self_ty);
124 for target in &vis.found {
125 if differing_macro_contexts(item.span, target.span()) {
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())
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);
149 "impl for `{}` should be generalized over different hashers",
153 suggestion(cx, diag, impl_.generics.span, generics_suggestion_span, target, ctr_vis);
158 ItemKind::Fn(ref sig, ref generics, body_id) => {
159 let body = cx.tcx.hir().body(body_id);
161 for ty in sig.decl.inputs {
162 let mut vis = ImplicitHasherTypeVisitor::new(cx);
165 for target in &vis.found {
166 if in_external_macro(cx.sess(), generics.span) {
169 let generics_suggestion_span = generics.span.substitute_dummy({
170 let pos = snippet_opt(cx, item.span.until(body.params[0].pat.span))
172 let i = snip.find("fn")?;
173 Some(item.span.lo() + BytePos((i + (&snip[i..]).find('(')?) as u32))
175 .expect("failed to create span for type parameters");
176 Span::new(pos, pos, item.span.ctxt(), item.span.parent())
179 let mut ctr_vis = ImplicitHasherConstructorVisitor::new(cx, target);
180 ctr_vis.visit_body(body);
187 "parameter of type `{}` should be generalized over different hashers",
191 suggestion(cx, diag, generics.span, generics_suggestion_span, target, ctr_vis);
202 enum ImplicitHasherType<'tcx> {
203 HashMap(Span, Ty<'tcx>, Cow<'static, str>, Cow<'static, str>),
204 HashSet(Span, Ty<'tcx>, Cow<'static, str>),
207 impl<'tcx> ImplicitHasherType<'tcx> {
208 /// Checks that `ty` is a target type without a `BuildHasher`.
209 fn new(cx: &LateContext<'tcx>, hir_ty: &hir::Ty<'_>) -> Option<Self> {
210 if let TyKind::Path(QPath::Resolved(None, path)) = hir_ty.kind {
211 let params: Vec<_> = path
219 .filter_map(|arg| match arg {
220 GenericArg::Type(ty) => Some(ty),
224 let params_len = params.len();
226 let ty = hir_ty_to_ty(cx.tcx, hir_ty);
228 if is_type_diagnostic_item(cx, ty, sym::HashMap) && params_len == 2 {
229 Some(ImplicitHasherType::HashMap(
232 snippet(cx, params[0].span, "K"),
233 snippet(cx, params[1].span, "V"),
235 } else if is_type_diagnostic_item(cx, ty, sym::HashSet) && params_len == 1 {
236 Some(ImplicitHasherType::HashSet(
239 snippet(cx, params[0].span, "T"),
249 fn type_name(&self) -> &'static str {
251 ImplicitHasherType::HashMap(..) => "HashMap",
252 ImplicitHasherType::HashSet(..) => "HashSet",
256 fn type_arguments(&self) -> String {
258 ImplicitHasherType::HashMap(.., ref k, ref v) => format!("{}, {}", k, v),
259 ImplicitHasherType::HashSet(.., ref t) => format!("{}", t),
263 fn ty(&self) -> Ty<'tcx> {
265 ImplicitHasherType::HashMap(_, ty, ..) | ImplicitHasherType::HashSet(_, ty, ..) => ty,
269 fn span(&self) -> Span {
271 ImplicitHasherType::HashMap(span, ..) | ImplicitHasherType::HashSet(span, ..) => span,
276 struct ImplicitHasherTypeVisitor<'a, 'tcx> {
277 cx: &'a LateContext<'tcx>,
278 found: Vec<ImplicitHasherType<'tcx>>,
281 impl<'a, 'tcx> ImplicitHasherTypeVisitor<'a, 'tcx> {
282 fn new(cx: &'a LateContext<'tcx>) -> Self {
283 Self { cx, found: vec![] }
287 impl<'a, 'tcx> Visitor<'tcx> for ImplicitHasherTypeVisitor<'a, 'tcx> {
288 type Map = Map<'tcx>;
290 fn visit_ty(&mut self, t: &'tcx hir::Ty<'_>) {
291 if let Some(target) = ImplicitHasherType::new(self.cx, t) {
292 self.found.push(target);
298 fn visit_infer(&mut self, inf: &'tcx hir::InferArg) {
299 if let Some(target) = ImplicitHasherType::new(self.cx, &inf.to_ty()) {
300 self.found.push(target);
306 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
307 NestedVisitorMap::None
311 /// Looks for default-hasher-dependent constructors like `HashMap::new`.
312 struct ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
313 cx: &'a LateContext<'tcx>,
314 maybe_typeck_results: Option<&'tcx TypeckResults<'tcx>>,
315 target: &'b ImplicitHasherType<'tcx>,
316 suggestions: BTreeMap<Span, String>,
319 impl<'a, 'b, 'tcx> ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
320 fn new(cx: &'a LateContext<'tcx>, target: &'b ImplicitHasherType<'tcx>) -> Self {
323 maybe_typeck_results: cx.maybe_typeck_results(),
325 suggestions: BTreeMap::new(),
330 impl<'a, 'b, 'tcx> Visitor<'tcx> for ImplicitHasherConstructorVisitor<'a, 'b, 'tcx> {
331 type Map = Map<'tcx>;
333 fn visit_body(&mut self, body: &'tcx Body<'_>) {
334 let old_maybe_typeck_results = self.maybe_typeck_results.replace(self.cx.tcx.typeck_body(body.id()));
335 walk_body(self, body);
336 self.maybe_typeck_results = old_maybe_typeck_results;
339 fn visit_expr(&mut self, e: &'tcx Expr<'_>) {
341 if let ExprKind::Call(fun, args) = e.kind;
342 if let ExprKind::Path(QPath::TypeRelative(ty, method)) = fun.kind;
343 if let TyKind::Path(QPath::Resolved(None, ty_path)) = ty.kind;
344 if let Some(ty_did) = ty_path.res.opt_def_id();
346 if !TyS::same_type(self.target.ty(), self.maybe_typeck_results.unwrap().expr_ty(e)) {
350 if self.cx.tcx.is_diagnostic_item(sym::HashMap, ty_did) {
351 if method.ident.name == sym::new {
353 .insert(e.span, "HashMap::default()".to_string());
354 } else if method.ident.name == sym!(with_capacity) {
355 self.suggestions.insert(
358 "HashMap::with_capacity_and_hasher({}, Default::default())",
359 snippet(self.cx, args[0].span, "capacity"),
363 } else if self.cx.tcx.is_diagnostic_item(sym::HashSet, ty_did) {
364 if method.ident.name == sym::new {
366 .insert(e.span, "HashSet::default()".to_string());
367 } else if method.ident.name == sym!(with_capacity) {
368 self.suggestions.insert(
371 "HashSet::with_capacity_and_hasher({}, Default::default())",
372 snippet(self.cx, args[0].span, "capacity"),
383 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
384 NestedVisitorMap::OnlyBodies(self.cx.tcx.hir())