1 use clippy_utils::higher;
3 can_move_expr_to_closure_no_visit,
4 diagnostics::span_lint_and_sugg,
5 is_expr_final_block_expr, is_expr_used_or_unified, match_def_path, paths, peel_hir_expr_while,
6 source::{reindent_multiline, snippet_indent, snippet_with_applicability, snippet_with_context},
10 use rustc_errors::Applicability;
13 intravisit::{walk_expr, Visitor},
14 Block, Expr, ExprKind, Guard, HirId, Let, Pat, Stmt, StmtKind, UnOp,
16 use rustc_lint::{LateContext, LateLintPass};
17 use rustc_session::{declare_lint_pass, declare_tool_lint};
18 use rustc_span::{Span, SyntaxContext, DUMMY_SP};
20 declare_clippy_lint! {
22 /// Checks for uses of `contains_key` + `insert` on `HashMap`
25 /// ### Why is this bad?
26 /// Using `entry` is more efficient.
28 /// ### Known problems
29 /// The suggestion may have type inference errors in some cases. e.g.
31 /// let mut map = std::collections::HashMap::new();
32 /// let _ = if !map.contains_key(&0) {
41 /// # use std::collections::HashMap;
42 /// # let mut map = HashMap::new();
45 /// if !map.contains_key(&k) {
51 /// # use std::collections::HashMap;
52 /// # let mut map = HashMap::new();
55 /// map.entry(k).or_insert(v);
57 #[clippy::version = "pre 1.29.0"]
60 "use of `contains_key` followed by `insert` on a `HashMap` or `BTreeMap`"
63 declare_lint_pass!(HashMapPass => [MAP_ENTRY]);
65 impl<'tcx> LateLintPass<'tcx> for HashMapPass {
66 #[expect(clippy::too_many_lines)]
67 fn check_expr(&mut self, cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) {
68 let Some(higher::If { cond: cond_expr, then: then_expr, r#else: else_expr }) = higher::If::hir(expr) else {
72 let Some((map_ty, contains_expr)) = try_parse_contains(cx, cond_expr) else {
76 let Some(then_search) = find_insert_calls(cx, &contains_expr, then_expr) else {
80 let mut app = Applicability::MachineApplicable;
81 let map_str = snippet_with_context(cx, contains_expr.map.span, contains_expr.call_ctxt, "..", &mut app).0;
82 let key_str = snippet_with_context(cx, contains_expr.key.span, contains_expr.call_ctxt, "..", &mut app).0;
83 let sugg = if let Some(else_expr) = else_expr {
84 let Some(else_search) = find_insert_calls(cx, &contains_expr, else_expr) else {
88 if then_search.edits.is_empty() && else_search.edits.is_empty() {
91 } else if then_search.edits.is_empty() || else_search.edits.is_empty() {
92 // if .. { insert } else { .. } or if .. { .. } else { insert }
93 let ((then_str, entry_kind), else_str) = match (else_search.edits.is_empty(), contains_expr.negated) {
95 then_search.snippet_vacant(cx, then_expr.span, &mut app),
96 snippet_with_applicability(cx, else_expr.span, "{ .. }", &mut app),
99 then_search.snippet_occupied(cx, then_expr.span, &mut app),
100 snippet_with_applicability(cx, else_expr.span, "{ .. }", &mut app),
103 else_search.snippet_occupied(cx, else_expr.span, &mut app),
104 snippet_with_applicability(cx, then_expr.span, "{ .. }", &mut app),
107 else_search.snippet_vacant(cx, else_expr.span, &mut app),
108 snippet_with_applicability(cx, then_expr.span, "{ .. }", &mut app),
112 "if let {}::{entry_kind} = {map_str}.entry({key_str}) {then_str} else {else_str}",
116 // if .. { insert } else { insert }
117 let ((then_str, then_entry), (else_str, else_entry)) = if contains_expr.negated {
119 then_search.snippet_vacant(cx, then_expr.span, &mut app),
120 else_search.snippet_occupied(cx, else_expr.span, &mut app),
124 then_search.snippet_occupied(cx, then_expr.span, &mut app),
125 else_search.snippet_vacant(cx, else_expr.span, &mut app),
128 let indent_str = snippet_indent(cx, expr.span);
129 let indent_str = indent_str.as_deref().unwrap_or("");
131 "match {map_str}.entry({key_str}) {{\n{indent_str} {entry}::{then_entry} => {}\n\
132 {indent_str} {entry}::{else_entry} => {}\n{indent_str}}}",
133 reindent_multiline(then_str.into(), true, Some(4 + indent_str.len())),
134 reindent_multiline(else_str.into(), true, Some(4 + indent_str.len())),
135 entry = map_ty.entry_path(),
139 if then_search.edits.is_empty() {
145 if !then_search.allow_insert_closure {
146 let (body_str, entry_kind) = if contains_expr.negated {
147 then_search.snippet_vacant(cx, then_expr.span, &mut app)
149 then_search.snippet_occupied(cx, then_expr.span, &mut app)
152 "if let {}::{entry_kind} = {map_str}.entry({key_str}) {body_str}",
155 } else if let Some(insertion) = then_search.as_single_insertion() {
156 let value_str = snippet_with_context(cx, insertion.value.span, then_expr.span.ctxt(), "..", &mut app).0;
157 if contains_expr.negated {
158 if insertion.value.can_have_side_effects() {
159 format!("{map_str}.entry({key_str}).or_insert_with(|| {value_str});")
161 format!("{map_str}.entry({key_str}).or_insert({value_str});")
164 // TODO: suggest using `if let Some(v) = map.get_mut(k) { .. }` here.
165 // This would need to be a different lint.
169 let block_str = then_search.snippet_closure(cx, then_expr.span, &mut app);
170 if contains_expr.negated {
171 format!("{map_str}.entry({key_str}).or_insert_with(|| {block_str});")
173 // TODO: suggest using `if let Some(v) = map.get_mut(k) { .. }` here.
174 // This would need to be a different lint.
184 &format!("usage of `contains_key` followed by `insert` on a `{}`", map_ty.name()),
192 #[derive(Clone, Copy)]
198 fn name(self) -> &'static str {
200 Self::Hash => "HashMap",
201 Self::BTree => "BTreeMap",
204 fn entry_path(self) -> &'static str {
206 Self::Hash => "std::collections::hash_map::Entry",
207 Self::BTree => "std::collections::btree_map::Entry",
212 struct ContainsExpr<'tcx> {
214 map: &'tcx Expr<'tcx>,
215 key: &'tcx Expr<'tcx>,
216 call_ctxt: SyntaxContext,
218 fn try_parse_contains<'tcx>(cx: &LateContext<'_>, expr: &'tcx Expr<'_>) -> Option<(MapType, ContainsExpr<'tcx>)> {
219 let mut negated = false;
220 let expr = peel_hir_expr_while(expr, |e| match e.kind {
221 ExprKind::Unary(UnOp::Not, e) => {
228 ExprKind::MethodCall(
233 kind: ExprKind::AddrOf(_, _, key),
239 ) if key_span.ctxt() == expr.span.ctxt() => {
240 let id = cx.typeck_results().type_dependent_def_id(expr.hir_id)?;
241 let expr = ContainsExpr {
245 call_ctxt: expr.span.ctxt(),
247 if match_def_path(cx, id, &paths::BTREEMAP_CONTAINS_KEY) {
248 Some((MapType::BTree, expr))
249 } else if match_def_path(cx, id, &paths::HASHMAP_CONTAINS_KEY) {
250 Some((MapType::Hash, expr))
259 struct InsertExpr<'tcx> {
260 map: &'tcx Expr<'tcx>,
261 key: &'tcx Expr<'tcx>,
262 value: &'tcx Expr<'tcx>,
264 fn try_parse_insert<'tcx>(cx: &LateContext<'tcx>, expr: &'tcx Expr<'_>) -> Option<InsertExpr<'tcx>> {
265 if let ExprKind::MethodCall(_, map, [key, value], _) = expr.kind {
266 let id = cx.typeck_results().type_dependent_def_id(expr.hir_id)?;
267 if match_def_path(cx, id, &paths::BTREEMAP_INSERT) || match_def_path(cx, id, &paths::HASHMAP_INSERT) {
268 Some(InsertExpr { map, key, value })
277 /// An edit that will need to be made to move the expression to use the entry api
278 #[derive(Clone, Copy)]
280 /// A semicolon that needs to be removed. Used to create a closure for `insert_with`.
282 /// An insertion into the map.
283 Insertion(Insertion<'tcx>),
285 impl<'tcx> Edit<'tcx> {
286 fn as_insertion(self) -> Option<Insertion<'tcx>> {
287 if let Self::Insertion(i) = self { Some(i) } else { None }
290 #[derive(Clone, Copy)]
291 struct Insertion<'tcx> {
292 call: &'tcx Expr<'tcx>,
293 value: &'tcx Expr<'tcx>,
296 /// This visitor needs to do a multiple things:
297 /// * Find all usages of the map. An insertion can only be made before any other usages of the map.
298 /// * Determine if there's an insertion using the same key. There's no need for the entry api
300 /// * Determine if the final statement executed is an insertion. This is needed to use
301 /// `or_insert_with`.
302 /// * Determine if there's any sub-expression that can't be placed in a closure.
303 /// * Determine if there's only a single insert statement. `or_insert` can be used in this case.
304 #[expect(clippy::struct_excessive_bools)]
305 struct InsertSearcher<'cx, 'tcx> {
306 cx: &'cx LateContext<'tcx>,
307 /// The map expression used in the contains call.
308 map: &'tcx Expr<'tcx>,
309 /// The key expression used in the contains call.
310 key: &'tcx Expr<'tcx>,
311 /// The context of the top level block. All insert calls must be in the same context.
313 /// Whether this expression can be safely moved into a closure.
314 allow_insert_closure: bool,
315 /// Whether this expression can use the entry api.
317 /// Whether this expression is the final expression in this code path. This may be a statement.
319 // Is this expression a single insert. A slightly better suggestion can be made in this case.
320 is_single_insert: bool,
321 /// If the visitor has seen the map being used.
323 /// The locations where changes need to be made for the suggestion.
324 edits: Vec<Edit<'tcx>>,
325 /// A stack of loops the visitor is currently in.
327 /// Local variables created in the expression. These don't need to be captured.
330 impl<'tcx> InsertSearcher<'_, 'tcx> {
331 /// Visit the expression as a branch in control flow. Multiple insert calls can be used, but
332 /// only if they are on separate code paths. This will return whether the map was used in the
333 /// given expression.
334 fn visit_cond_arm(&mut self, e: &'tcx Expr<'_>) -> bool {
335 let is_map_used = self.is_map_used;
336 let in_tail_pos = self.in_tail_pos;
338 let res = self.is_map_used;
339 self.is_map_used = is_map_used;
340 self.in_tail_pos = in_tail_pos;
344 /// Visits an expression which is not itself in a tail position, but other sibling expressions
345 /// may be. e.g. if conditions
346 fn visit_non_tail_expr(&mut self, e: &'tcx Expr<'_>) {
347 let in_tail_pos = self.in_tail_pos;
348 self.in_tail_pos = false;
350 self.in_tail_pos = in_tail_pos;
353 impl<'tcx> Visitor<'tcx> for InsertSearcher<'_, 'tcx> {
354 fn visit_stmt(&mut self, stmt: &'tcx Stmt<'_>) {
356 StmtKind::Semi(e) => {
359 if self.in_tail_pos && self.allow_insert_closure {
360 // The spans are used to slice the top level expression into multiple parts. This requires that
361 // they all come from the same part of the source code.
362 if stmt.span.ctxt() == self.ctxt && e.span.ctxt() == self.ctxt {
364 .push(Edit::RemoveSemi(stmt.span.trim_start(e.span).unwrap_or(DUMMY_SP)));
366 self.allow_insert_closure = false;
370 StmtKind::Expr(e) => self.visit_expr(e),
371 StmtKind::Local(l) => {
372 self.visit_pat(l.pat);
373 if let Some(e) = l.init {
374 self.allow_insert_closure &= !self.in_tail_pos;
375 self.in_tail_pos = false;
376 self.is_single_insert = false;
380 StmtKind::Item(_) => {
381 self.allow_insert_closure &= !self.in_tail_pos;
382 self.is_single_insert = false;
387 fn visit_block(&mut self, block: &'tcx Block<'_>) {
388 // If the block is in a tail position, then the last expression (possibly a statement) is in the
389 // tail position. The rest, however, are not.
390 match (block.stmts, block.expr) {
392 self.allow_insert_closure &= !self.in_tail_pos;
394 ([], Some(expr)) => self.visit_expr(expr),
395 (stmts, Some(expr)) => {
396 let in_tail_pos = self.in_tail_pos;
397 self.in_tail_pos = false;
399 self.visit_stmt(stmt);
401 self.in_tail_pos = in_tail_pos;
402 self.visit_expr(expr);
404 ([stmts @ .., stmt], None) => {
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_stmt(stmt);
416 fn visit_expr(&mut self, expr: &'tcx Expr<'_>) {
417 if !self.can_use_entry {
421 match try_parse_insert(self.cx, expr) {
422 Some(insert_expr) if SpanlessEq::new(self.cx).eq_expr(self.map, insert_expr.map) => {
423 // Multiple inserts, inserts with a different key, and inserts from a macro can't use the entry api.
425 || !SpanlessEq::new(self.cx).eq_expr(self.key, insert_expr.key)
426 || expr.span.ctxt() != self.ctxt
428 self.can_use_entry = false;
432 self.edits.push(Edit::Insertion(Insertion {
434 value: insert_expr.value,
436 self.is_map_used = true;
437 self.allow_insert_closure &= self.in_tail_pos;
439 // The value doesn't affect whether there is only a single insert expression.
440 let is_single_insert = self.is_single_insert;
441 self.visit_non_tail_expr(insert_expr.value);
442 self.is_single_insert = is_single_insert;
444 _ if SpanlessEq::new(self.cx).eq_expr(self.map, expr) => {
445 self.is_map_used = true;
447 _ => match expr.kind {
448 ExprKind::If(cond_expr, then_expr, Some(else_expr)) => {
449 self.is_single_insert = false;
450 self.visit_non_tail_expr(cond_expr);
451 // Each branch may contain it's own insert expression.
452 let mut is_map_used = self.visit_cond_arm(then_expr);
453 is_map_used |= self.visit_cond_arm(else_expr);
454 self.is_map_used = is_map_used;
456 ExprKind::Match(scrutinee_expr, arms, _) => {
457 self.is_single_insert = false;
458 self.visit_non_tail_expr(scrutinee_expr);
459 // Each branch may contain it's own insert expression.
460 let mut is_map_used = self.is_map_used;
462 self.visit_pat(arm.pat);
463 if let Some(Guard::If(guard) | Guard::IfLet(&Let { init: guard, .. })) = arm.guard {
464 self.visit_non_tail_expr(guard);
466 is_map_used |= self.visit_cond_arm(arm.body);
468 self.is_map_used = is_map_used;
470 ExprKind::Loop(block, ..) => {
471 self.loops.push(expr.hir_id);
472 self.is_single_insert = false;
473 self.allow_insert_closure &= !self.in_tail_pos;
474 // Don't allow insertions inside of a loop.
475 let edit_len = self.edits.len();
476 self.visit_block(block);
477 if self.edits.len() != edit_len {
478 self.can_use_entry = false;
482 ExprKind::Block(block, _) => self.visit_block(block),
483 ExprKind::InlineAsm(_) => {
484 self.can_use_entry = false;
487 self.allow_insert_closure &= !self.in_tail_pos;
488 self.allow_insert_closure &=
489 can_move_expr_to_closure_no_visit(self.cx, expr, &self.loops, &self.locals);
490 // Sub expressions are no longer in the tail position.
491 self.is_single_insert = false;
492 self.in_tail_pos = false;
493 walk_expr(self, expr);
499 fn visit_pat(&mut self, p: &'tcx Pat<'tcx>) {
500 p.each_binding_or_first(&mut |_, id, _, _| {
501 self.locals.insert(id);
506 struct InsertSearchResults<'tcx> {
507 edits: Vec<Edit<'tcx>>,
508 allow_insert_closure: bool,
509 is_single_insert: bool,
511 impl<'tcx> InsertSearchResults<'tcx> {
512 fn as_single_insertion(&self) -> Option<Insertion<'tcx>> {
513 self.is_single_insert.then(|| self.edits[0].as_insertion().unwrap())
518 cx: &LateContext<'_>,
520 app: &mut Applicability,
521 write_wrapped: impl Fn(&mut String, Insertion<'_>, SyntaxContext, &mut Applicability),
523 let ctxt = span.ctxt();
524 let mut res = String::new();
525 for insertion in self.edits.iter().filter_map(|e| e.as_insertion()) {
526 res.push_str(&snippet_with_applicability(
528 span.until(insertion.call.span),
532 if is_expr_used_or_unified(cx.tcx, insertion.call) {
533 write_wrapped(&mut res, insertion, ctxt, app);
538 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0
541 span = span.trim_start(insertion.call.span).unwrap_or(DUMMY_SP);
543 res.push_str(&snippet_with_applicability(cx, span, "..", app));
547 fn snippet_occupied(&self, cx: &LateContext<'_>, span: Span, app: &mut Applicability) -> (String, &'static str) {
549 self.snippet(cx, span, app, |res, insertion, ctxt, app| {
550 // Insertion into a map would return `Some(&mut value)`, but the entry returns `&mut value`
553 "Some(e.insert({}))",
554 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0
561 fn snippet_vacant(&self, cx: &LateContext<'_>, span: Span, app: &mut Applicability) -> (String, &'static str) {
563 self.snippet(cx, span, app, |res, insertion, ctxt, app| {
564 // Insertion into a map would return `None`, but the entry returns a mutable reference.
565 let _ = if is_expr_final_block_expr(cx.tcx, insertion.call) {
568 "e.insert({});\n{}None",
569 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0,
570 snippet_indent(cx, insertion.call.span).as_deref().unwrap_or(""),
575 "{{ e.insert({}); None }}",
576 snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0,
584 fn snippet_closure(&self, cx: &LateContext<'_>, mut span: Span, app: &mut Applicability) -> String {
585 let ctxt = span.ctxt();
586 let mut res = String::new();
587 for edit in &self.edits {
589 Edit::Insertion(insertion) => {
590 // Cut out the value from `map.insert(key, value)`
591 res.push_str(&snippet_with_applicability(
593 span.until(insertion.call.span),
597 res.push_str(&snippet_with_context(cx, insertion.value.span, ctxt, "..", app).0);
598 span = span.trim_start(insertion.call.span).unwrap_or(DUMMY_SP);
600 Edit::RemoveSemi(semi_span) => {
601 // Cut out the semicolon. This allows the value to be returned from the closure.
602 res.push_str(&snippet_with_applicability(cx, span.until(semi_span), "..", app));
603 span = span.trim_start(semi_span).unwrap_or(DUMMY_SP);
607 res.push_str(&snippet_with_applicability(cx, span, "..", app));
612 fn find_insert_calls<'tcx>(
613 cx: &LateContext<'tcx>,
614 contains_expr: &ContainsExpr<'tcx>,
615 expr: &'tcx Expr<'_>,
616 ) -> Option<InsertSearchResults<'tcx>> {
617 let mut s = InsertSearcher {
619 map: contains_expr.map,
620 key: contains_expr.key,
621 ctxt: expr.span.ctxt(),
624 allow_insert_closure: true,
627 is_single_insert: true,
629 locals: HirIdSet::default(),
632 let allow_insert_closure = s.allow_insert_closure;
633 let is_single_insert = s.is_single_insert;
635 s.can_use_entry.then_some(InsertSearchResults {
637 allow_insert_closure,