2 can_move_expr_to_closure_no_visit,
3 diagnostics::span_lint_and_sugg,
4 is_expr_final_block_expr, is_expr_used_or_unified, match_def_path, paths, peel_hir_expr_while,
5 source::{reindent_multiline, snippet_indent, snippet_with_applicability, snippet_with_context},
8 use rustc_errors::Applicability;
10 intravisit::{walk_expr, ErasedMap, NestedVisitorMap, Visitor},
11 Block, Expr, ExprKind, Guard, HirId, Local, Stmt, StmtKind, UnOp,
13 use rustc_lint::{LateContext, LateLintPass};
14 use rustc_session::{declare_lint_pass, declare_tool_lint};
15 use rustc_span::{Span, SyntaxContext, DUMMY_SP};
18 declare_clippy_lint! {
19 /// **What it does:** Checks for uses of `contains_key` + `insert` on `HashMap`
22 /// **Why is this bad?** Using `entry` is more efficient.
24 /// **Known problems:** The suggestion may have type inference errors in some cases. e.g.
26 /// let mut map = std::collections::HashMap::new();
27 /// let _ = if !map.contains_key(&0) {
36 /// # use std::collections::HashMap;
37 /// # let mut map = HashMap::new();
40 /// if !map.contains_key(&k) {
44 /// can both be rewritten as:
46 /// # use std::collections::HashMap;
47 /// # let mut map = HashMap::new();
50 /// map.entry(k).or_insert(v);
54 "use of `contains_key` followed by `insert` on a `HashMap` or `BTreeMap`"
57 declare_lint_pass!(HashMapPass => [MAP_ENTRY]);
59 impl<'tcx> LateLintPass<'tcx> for HashMapPass {
60 #[allow(clippy::too_many_lines)]
61 fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
62 let (cond_expr, then_expr, else_expr) = match expr.kind {
63 ExprKind::If(c, t, e) => (c, t, e),
66 let (map_ty, contains_expr) = match try_parse_contains(cx, cond_expr) {
71 let then_search = match find_insert_calls(cx, &contains_expr, then_expr) {
76 let mut app = Applicability::MachineApplicable;
77 let map_str = snippet_with_context(cx, contains_expr.map.span, contains_expr.call_ctxt, "..", &mut app).0;
78 let key_str = snippet_with_context(cx, contains_expr.key.span, contains_expr.call_ctxt, "..", &mut app).0;
79 let sugg = if let Some(else_expr) = else_expr {
80 let else_search = match find_insert_calls(cx, &contains_expr, else_expr) {
81 Some(search) => search,
85 if then_search.edits.is_empty() && else_search.edits.is_empty() {
88 } else if then_search.edits.is_empty() || else_search.edits.is_empty() {
89 // if .. { insert } else { .. } or if .. { .. } else { insert }
90 let ((then_str, entry_kind), else_str) = match (else_search.edits.is_empty(), contains_expr.negated) {
92 then_search.snippet_vacant(cx, then_expr.span, &mut app),
93 snippet_with_applicability(cx, else_expr.span, "{ .. }", &mut app),
96 then_search.snippet_occupied(cx, then_expr.span, &mut app),
97 snippet_with_applicability(cx, else_expr.span, "{ .. }", &mut app),
100 else_search.snippet_occupied(cx, else_expr.span, &mut app),
101 snippet_with_applicability(cx, then_expr.span, "{ .. }", &mut app),
104 else_search.snippet_vacant(cx, else_expr.span, &mut app),
105 snippet_with_applicability(cx, then_expr.span, "{ .. }", &mut app),
109 "if let {}::{} = {}.entry({}) {} else {}",
118 // if .. { insert } else { insert }
119 let ((then_str, then_entry), (else_str, else_entry)) = if contains_expr.negated {
121 then_search.snippet_vacant(cx, then_expr.span, &mut app),
122 else_search.snippet_occupied(cx, else_expr.span, &mut app),
126 then_search.snippet_occupied(cx, then_expr.span, &mut app),
127 else_search.snippet_vacant(cx, else_expr.span, &mut app),
130 let indent_str = snippet_indent(cx, expr.span);
131 let indent_str = indent_str.as_deref().unwrap_or("");
133 "match {}.entry({}) {{\n{indent} {entry}::{} => {}\n\
134 {indent} {entry}::{} => {}\n{indent}}}",
138 reindent_multiline(then_str.into(), true, Some(4 + indent_str.len())),
140 reindent_multiline(else_str.into(), true, Some(4 + indent_str.len())),
141 entry = map_ty.entry_path(),
146 if then_search.edits.is_empty() {
152 if !then_search.allow_insert_closure {
153 let (body_str, entry_kind) = if contains_expr.negated {
154 then_search.snippet_vacant(cx, then_expr.span, &mut app)
156 then_search.snippet_occupied(cx, then_expr.span, &mut app)
159 "if let {}::{} = {}.entry({}) {}",
166 } else if let Some(insertion) = then_search.as_single_insertion() {
167 let value_str = snippet_with_context(cx, insertion.value.span, then_expr.span.ctxt(), "..", &mut app).0;
168 if contains_expr.negated {
169 if insertion.value.can_have_side_effects() {
170 format!("{}.entry({}).or_insert_with(|| {});", map_str, key_str, value_str)
172 format!("{}.entry({}).or_insert({});", map_str, key_str, value_str)
175 // TODO: suggest using `if let Some(v) = map.get_mut(k) { .. }` here.
176 // This would need to be a different lint.
180 let block_str = then_search.snippet_closure(cx, then_expr.span, &mut app);
181 if contains_expr.negated {
182 format!("{}.entry({}).or_insert_with(|| {});", map_str, key_str, block_str)
184 // TODO: suggest using `if let Some(v) = map.get_mut(k) { .. }` here.
185 // This would need to be a different lint.
195 &format!("usage of `contains_key` followed by `insert` on a `{}`", map_ty.name()),
203 #[derive(Clone, Copy)]
209 fn name(self) -> &'static str {
211 Self::Hash => "HashMap",
212 Self::BTree => "BTreeMap",
215 fn entry_path(self) -> &'static str {
217 Self::Hash => "std::collections::hash_map::Entry",
218 Self::BTree => "std::collections::btree_map::Entry",
223 struct ContainsExpr<'tcx> {
225 map: &'tcx Expr<'tcx>,
226 key: &'tcx Expr<'tcx>,
227 call_ctxt: SyntaxContext,
229 fn try_parse_contains(cx: &LateContext<'_>, expr: &'tcx Expr<'_>) -> Option<(MapType, ContainsExpr<'tcx>)> {
230 let mut negated = false;
231 let expr = peel_hir_expr_while(expr, |e| match e.kind {
232 ExprKind::Unary(UnOp::Not, e) => {
239 ExprKind::MethodCall(
243 kind: ExprKind::AddrOf(_, _, key),
248 ) if key_span.ctxt() == expr.span.ctxt() => {
249 let id = cx.typeck_results().type_dependent_def_id(expr.hir_id)?;
250 let expr = ContainsExpr {
254 call_ctxt: expr.span.ctxt(),
256 if match_def_path(cx, id, &paths::BTREEMAP_CONTAINS_KEY) {
257 Some((MapType::BTree, expr))
258 } else if match_def_path(cx, id, &paths::HASHMAP_CONTAINS_KEY) {
259 Some((MapType::Hash, expr))
268 struct InsertExpr<'tcx> {
269 map: &'tcx Expr<'tcx>,
270 key: &'tcx Expr<'tcx>,
271 value: &'tcx Expr<'tcx>,
273 fn try_parse_insert(cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) -> Option<InsertExpr<'tcx>> {
274 if let ExprKind::MethodCall(_, _, [map, key, value], _) = expr.kind {
275 let id = cx.typeck_results().type_dependent_def_id(expr.hir_id)?;
276 if match_def_path(cx, id, &paths::BTREEMAP_INSERT) || match_def_path(cx, id, &paths::HASHMAP_INSERT) {
277 Some(InsertExpr { map, key, value })
286 /// An edit that will need to be made to move the expression to use the entry api
287 #[derive(Clone, Copy)]
289 /// A semicolon that needs to be removed. Used to create a closure for `insert_with`.
291 /// An insertion into the map.
292 Insertion(Insertion<'tcx>),
295 fn as_insertion(self) -> Option<Insertion<'tcx>> {
296 if let Self::Insertion(i) = self { Some(i) } else { None }
299 #[derive(Clone, Copy)]
300 struct Insertion<'tcx> {
301 call: &'tcx Expr<'tcx>,
302 value: &'tcx Expr<'tcx>,
305 /// This visitor needs to do a multiple things:
306 /// * Find all usages of the map. An insertion can only be made before any other usages of the map.
307 /// * Determine if there's an insertion using the same key. There's no need for the entry api
309 /// * Determine if the final statement executed is an insertion. This is needed to use
310 /// `or_insert_with`.
311 /// * Determine if there's any sub-expression that can't be placed in a closure.
312 /// * Determine if there's only a single insert statement. `or_insert` can be used in this case.
313 #[allow(clippy::struct_excessive_bools)]
314 struct InsertSearcher<'cx, 'tcx> {
315 cx: &'cx LateContext<'tcx>,
316 /// The map expression used in the contains call.
317 map: &'tcx Expr<'tcx>,
318 /// The key expression used in the contains call.
319 key: &'tcx Expr<'tcx>,
320 /// The context of the top level block. All insert calls must be in the same context.
322 /// Whether this expression can be safely moved into a closure.
323 allow_insert_closure: bool,
324 /// Whether this expression can use the entry api.
326 /// Whether this expression is the final expression in this code path. This may be a statement.
328 // Is this expression a single insert. A slightly better suggestion can be made in this case.
329 is_single_insert: bool,
330 /// If the visitor has seen the map being used.
332 /// The locations where changes need to be made for the suggestion.
333 edits: Vec<Edit<'tcx>>,
334 /// A stack of loops the visitor is currently in.
337 impl<'tcx> InsertSearcher<'_, 'tcx> {
338 /// Visit the expression as a branch in control flow. Multiple insert calls can be used, but
339 /// only if they are on separate code paths. This will return whether the map was used in the
340 /// given expression.
341 fn visit_cond_arm(&mut self, e: &'tcx Expr<'_>) -> bool {
342 let is_map_used = self.is_map_used;
343 let in_tail_pos = self.in_tail_pos;
345 let res = self.is_map_used;
346 self.is_map_used = is_map_used;
347 self.in_tail_pos = in_tail_pos;
351 /// Visits an expression which is not itself in a tail position, but other sibling expressions
352 /// may be. e.g. if conditions
353 fn visit_non_tail_expr(&mut self, e: &'tcx Expr<'_>) {
354 let in_tail_pos = self.in_tail_pos;
355 self.in_tail_pos = false;
357 self.in_tail_pos = in_tail_pos;
360 impl<'tcx> Visitor<'tcx> for InsertSearcher<'_, 'tcx> {
361 type Map = ErasedMap<'tcx>;
362 fn nested_visit_map(&mut self) -> NestedVisitorMap<Self::Map> {
363 NestedVisitorMap::None
366 fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
368 StmtKind::Semi(e) => {
371 if self.in_tail_pos && self.allow_insert_closure {
372 // The spans are used to slice the top level expression into multiple parts. This requires that
373 // they all come from the same part of the source code.
374 if stmt.span.ctxt() == self.ctxt && e.span.ctxt() == self.ctxt {
376 .push(Edit::RemoveSemi(stmt.span.trim_start(e.span).unwrap_or(DUMMY_SP)));
378 self.allow_insert_closure = false;
382 StmtKind::Expr(e) => self.visit_expr(e),
383 StmtKind::Local(Local { init: Some(e), .. }) => {
384 self.allow_insert_closure &= !self.in_tail_pos;
385 self.in_tail_pos = false;
386 self.is_single_insert = false;
390 self.allow_insert_closure &= !self.in_tail_pos;
391 self.is_single_insert = false;
396 fn visit_block(&mut self, block: &'tcx Block<'_>) {
397 // If the block is in a tail position, then the last expression (possibly a statement) is in the
398 // tail position. The rest, however, are not.
399 match (block.stmts, block.expr) {
401 self.allow_insert_closure &= !self.in_tail_pos;
403 ([], Some(expr)) => self.visit_expr(expr),
404 (stmts, Some(expr)) => {
405 let in_tail_pos = self.in_tail_pos;
406 self.in_tail_pos = false;
408 self.visit_stmt(stmt);
410 self.in_tail_pos = in_tail_pos;
411 self.visit_expr(expr);
413 ([stmts @ .., stmt], None) => {
414 let in_tail_pos = self.in_tail_pos;
415 self.in_tail_pos = false;
417 self.visit_stmt(stmt);
419 self.in_tail_pos = in_tail_pos;
420 self.visit_stmt(stmt);
425 fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
426 if !self.can_use_entry {
430 match try_parse_insert(self.cx, expr) {
431 Some(insert_expr) if SpanlessEq::new(self.cx).eq_expr(self.map, insert_expr.map) => {
432 // Multiple inserts, inserts with a different key, and inserts from a macro can't use the entry api.
434 || !SpanlessEq::new(self.cx).eq_expr(self.key, insert_expr.key)
435 || expr.span.ctxt() != self.ctxt
437 self.can_use_entry = false;
441 self.edits.push(Edit::Insertion(Insertion {
443 value: insert_expr.value,
445 self.is_map_used = true;
446 self.allow_insert_closure &= self.in_tail_pos;
448 // The value doesn't affect whether there is only a single insert expression.
449 let is_single_insert = self.is_single_insert;
450 self.visit_non_tail_expr(insert_expr.value);
451 self.is_single_insert = is_single_insert;
453 _ if SpanlessEq::new(self.cx).eq_expr(self.map, expr) => {
454 self.is_map_used = true;
456 _ => match expr.kind {
457 ExprKind::If(cond_expr, then_expr, Some(else_expr)) => {
458 self.is_single_insert = false;
459 self.visit_non_tail_expr(cond_expr);
460 // Each branch may contain it's own insert expression.
461 let mut is_map_used = self.visit_cond_arm(then_expr);
462 is_map_used |= self.visit_cond_arm(else_expr);
463 self.is_map_used = is_map_used;
465 ExprKind::Match(scrutinee_expr, arms, _) => {
466 self.is_single_insert = false;
467 self.visit_non_tail_expr(scrutinee_expr);
468 // Each branch may contain it's own insert expression.
469 let mut is_map_used = self.is_map_used;
471 if let Some(Guard::If(guard) | Guard::IfLet(_, guard)) = arm.guard {
472 self.visit_non_tail_expr(guard)
474 is_map_used |= self.visit_cond_arm(arm.body);
476 self.is_map_used = is_map_used;
478 ExprKind::Loop(block, ..) => {
479 self.loops.push(expr.hir_id);
480 self.is_single_insert = false;
481 self.allow_insert_closure &= !self.in_tail_pos;
482 // Don't allow insertions inside of a loop.
483 let edit_len = self.edits.len();
484 self.visit_block(block);
485 if self.edits.len() != edit_len {
486 self.can_use_entry = false;
490 ExprKind::Block(block, _) => self.visit_block(block),
491 ExprKind::InlineAsm(_) | ExprKind::LlvmInlineAsm(_) => {
492 self.can_use_entry = false;
495 self.allow_insert_closure &= !self.in_tail_pos;
496 self.allow_insert_closure &= can_move_expr_to_closure_no_visit(self.cx, expr, &self.loops);
497 // Sub expressions are no longer in the tail position.
498 self.is_single_insert = false;
499 self.in_tail_pos = false;
500 walk_expr(self, expr);
507 struct InsertSearchResults<'tcx> {
508 edits: Vec<Edit<'tcx>>,
509 allow_insert_closure: bool,
510 is_single_insert: bool,
512 impl InsertSearchResults<'tcx> {
513 fn as_single_insertion(&self) -> Option<Insertion<'tcx>> {
514 self.is_single_insert.then(|| self.edits[0].as_insertion().unwrap())
519 cx: &LateContext<'_>,
521 app: &mut Applicability,
522 write_wrapped: impl Fn(&mut String, Insertion<'_>, SyntaxContext, &mut Applicability),
524 let ctxt = span.ctxt();
525 let mut res = String::new();
526 for insertion in self.edits.iter().filter_map(|e| e.as_insertion()) {
527 res.push_str(&snippet_with_applicability(
529 span.until(insertion.call.span),
533 if is_expr_used_or_unified(cx.tcx, insertion.call) {
534 write_wrapped(&mut res, insertion, ctxt, app);
539 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0
542 span = span.trim_start(insertion.call.span).unwrap_or(DUMMY_SP);
544 res.push_str(&snippet_with_applicability(cx, span, "..", app));
548 fn snippet_occupied(&self, cx: &LateContext<'_>, span: Span, app: &mut Applicability) -> (String, &'static str) {
550 self.snippet(cx, span, app, |res, insertion, ctxt, app| {
551 // Insertion into a map would return `Some(&mut value)`, but the entry returns `&mut value`
554 "Some(e.insert({}))",
555 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0
562 fn snippet_vacant(&self, cx: &LateContext<'_>, span: Span, app: &mut Applicability) -> (String, &'static str) {
564 self.snippet(cx, span, app, |res, insertion, ctxt, app| {
565 // Insertion into a map would return `None`, but the entry returns a mutable reference.
566 let _ = if is_expr_final_block_expr(cx.tcx, insertion.call) {
569 "e.insert({});\n{}None",
570 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0,
571 snippet_indent(cx, insertion.call.span).as_deref().unwrap_or(""),
576 "{{ e.insert({}); None }}",
577 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0,
585 fn snippet_closure(&self, cx: &LateContext<'_>, mut span: Span, app: &mut Applicability) -> String {
586 let ctxt = span.ctxt();
587 let mut res = String::new();
588 for edit in &self.edits {
590 Edit::Insertion(insertion) => {
591 // Cut out the value from `map.insert(key, value)`
592 res.push_str(&snippet_with_applicability(
594 span.until(insertion.call.span),
598 res.push_str(&snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0);
599 span = span.trim_start(insertion.call.span).unwrap_or(DUMMY_SP);
601 Edit::RemoveSemi(semi_span) => {
602 // Cut out the semicolon. This allows the value to be returned from the closure.
603 res.push_str(&snippet_with_applicability(cx, span.until(semi_span), "..", app));
604 span = span.trim_start(semi_span).unwrap_or(DUMMY_SP);
608 res.push_str(&snippet_with_applicability(cx, span, "..", app));
613 fn find_insert_calls(
614 cx: &LateContext<'tcx>,
615 contains_expr: &ContainsExpr<'tcx>,
616 expr: &'tcx Expr<'_>,
617 ) -> Option<InsertSearchResults<'tcx>> {
618 let mut s = InsertSearcher {
620 map: contains_expr.map,
621 key: contains_expr.key,
622 ctxt: expr.span.ctxt(),
625 allow_insert_closure: true,
628 is_single_insert: true,
632 let allow_insert_closure = s.allow_insert_closure;
633 let is_single_insert = s.is_single_insert;
635 s.can_use_entry.then(|| InsertSearchResults {
637 allow_insert_closure,