[clang-tidy] New check bugprone-map-subscript-operator-lookup

[khuttun]

Summary

Warns on std::map and std::unordered_map lookups done with operator[]. Inserting values with operator[] is still allowed.

[khuttun]

This checker is inspired by Louis Brandy's excellent CppCon 2017 talk (https://www.youtube.com/watch?v=lkgszkPnV8g) where he describes the side-effects of std::map::operator[] as being one of the most common source of bugs in Facebook's C++ code. In the talk he mentions that banning the usage of the operator was discussed at Facebook. This checker bans reading the map with it, writing is still allowed.

The documentation is intentionally still missing from the commit. If the reviewers feel that this sort of checker would be useful for clang-tidy, I'll add the documentation and more tests.

[lebedev.ri]

clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.cpp

25

I would imagine it might be best to make this configurable from the start.

[Eugene.Zelenko]

clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.cpp

36

Will be good idea to use actual container type.

docs/ReleaseNotes.rst

63

Please add short description and place with other new checks in alphabetical order.

docs/clang-tidy/checks/bugprone-map-subscript-operator-lookup.rst

6

Please add description and examples.

[aaron.ballman]

I am generally in favor of this but would be curious to see how the check reacts to real world code bases. Facebook's usage experience is compelling, but I'm also wondering how bad the false-positive rate is on existing code. Can you try running the check over LLVM itself (perhaps after adding the option to add custom data types to the list and adding DenseMap and friends) and report back on what you find?

clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.cpp

21

No need to register the matchers unless in C++ mode.

clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.h

19

Should fix up the description.

docs/clang-tidy/checks/list.rst

96

This change looks unrelated (but reasonable -- you can commit this change without review).

[khuttun]

Abandoning this. The false positive rate would be too high for this checker.

[lebedev.ri]

IMHO we should proceed with this patch.
There's been several patches recently that seem to not care about false-positive rate,
and in this case the cost of true-positive can be humongous, as i/we've been finding
lots of bugs exactly like this in openmp optimization pass, attributor framework :/

[mgehre]

test/clang-tidy/bugprone-map-subscript-operator-lookup.cpp

60

We often have code like

auto &V = Map[Idx];
if (!V) {
  V = init();
}
use(V);

Would that be flagged by this check? Could you add a test for it (possibly with FIXME)?

[aaron.ballman]

In D46317#1988261, @lebedev.ri wrote:

IMHO we should proceed with this patch.
There's been several patches recently that seem to not care about false-positive rate,

I don't think that's accurate. We still care about false-positive rates and ask people to report on them when we think there's going to be an issue. That's not to say that we shouldn't proceed with this patch.

[khuttun]

In D46317#1988261, @lebedev.ri wrote:

IMHO we should proceed with this patch.
There's been several patches recently that seem to not care about false-positive rate,
and in this case the cost of true-positive can be humongous, as i/we've been finding
lots of bugs exactly like this in openmp optimization pass, attributor framework :/

When developing this checker I tested it on LLVM code base, and there was hundreds of warnings. Looking at my notes from then, the ones that I analyzed fell in to couple of different categories:

• The program logic is such that it's known that the key is found in the map (in some of these cases count() is asserted before the lookup)
• The code does find() vs. end() comparison before the lookup

From these the at least the first category could be considered false positives.

I also think that this checker could bring value, though. For example when enabled on a new project from the start. I should have time to finish it if reviewers feel that we should reconsider it. Also, go ahead and share if you have any ideas on how to make the checker more accurate.

test/clang-tidy/bugprone-map-subscript-operator-lookup.cpp

60

This would not be flagged, as the reference is non-const

[• Quuxplusone]

test/clang-tidy/bugprone-map-subscript-operator-lookup.cpp

48

Besides mgehre's request for auto& test cases, I'd like to see some test cases involving these member functions. I assume that's why these lines of code are here (but no tests use them yet).

[khuttun]

The patch is now updated to be based on the monorepo. I also fixed all the comments from the previous review.

[khuttun]

I ran the check for LLVM code using configuration key: bugprone-map-subscript-operator-lookup.MapTypes, value: "::std::map;::std::unordered_map;::llvm::DenseMapBase;::llvm::MapVector;::llvm::StringMap". It gave 1212 warnings (see the attachment).

warnings.txt172 KBDownload

[khuttun]

Documented the MapTypes check option.

[Eugene.Zelenko]

clang-tools-extra/clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.cpp

31 ↗

(On Diff #259843)

Should be in isLanguageVersionSupported() method.

clang-tools-extra/docs/ReleaseNotes.rst

78 ↗

(On Diff #259843)

Please separate with empty line.

81 ↗

(On Diff #259843)

Please synchronize with first statement in documentation.

[khuttun]

Fixed @Eugene.Zelenko's comments

[khuttun]

Accidentally removed the options documentation in the previous patch... Now added it back.

[khuttun]

Any comments on this? Is this checker something that could be part of clang-tidy?

[aaron.ballman]

In D46317#2023406, @khuttun wrote:

Any comments on this? Is this checker something that could be part of clang-tidy?

Thank you for posting some of the diagnostics found by the check, that was really helpful information! I spot-checked ~10 of the issues it reported and all of them were false positives. Were you able to find any true positives from that list? I think 1200 reports without any true positives indicates that the check may be too chatty to include (it may also suggest that bugprone is the wrong place for the check).

[khuttun]

In D46317#2027071, @aaron.ballman wrote:

In D46317#2023406, @khuttun wrote:

Any comments on this? Is this checker something that could be part of clang-tidy?

Thank you for posting some of the diagnostics found by the check, that was really helpful information! I spot-checked ~10 of the issues it reported and all of them were false positives. Were you able to find any true positives from that list? I think 1200 reports without any true positives indicates that the check may be too chatty to include (it may also suggest that bugprone is the wrong place for the check).

It's difficult to spot actual functionality bugs without knowing the code better, but there's plenty of unnecessary double-lookups (count()/find() + operator[]) reported, for example:

clang-tools-extra/clang-reorder-fields/ReorderFieldsAction.cpp:75:30
clang-tools-extra/clang-tidy/bugprone/ForwardDeclarationNamespaceCheck.cpp:157:33
clang-tools-extra/clang-tidy/modernize/DeprecatedHeadersCheck.cpp:106:29

[aaron.ballman]

In D46317#2027330, @khuttun wrote:

In D46317#2027071, @aaron.ballman wrote:

In D46317#2023406, @khuttun wrote:

Any comments on this? Is this checker something that could be part of clang-tidy?

Thank you for posting some of the diagnostics found by the check, that was really helpful information! I spot-checked ~10 of the issues it reported and all of them were false positives. Were you able to find any true positives from that list? I think 1200 reports without any true positives indicates that the check may be too chatty to include (it may also suggest that bugprone is the wrong place for the check).

It's difficult to spot actual functionality bugs without knowing the code better, but there's plenty of unnecessary double-lookups (count()/find() + operator[]) reported, for example:

Definitely agreed that it's labor-intensive. :-)

clang-tools-extra/clang-reorder-fields/ReorderFieldsAction.cpp:75:30
clang-tools-extra/clang-tidy/bugprone/ForwardDeclarationNamespaceCheck.cpp:157:33
clang-tools-extra/clang-tidy/modernize/DeprecatedHeadersCheck.cpp:106:29

I hadn't spot checked those, but did see at least one similar case with what I checked. However, I consider those false positives because none of these are cases where the code gives wrong results. It is possible they are performance concerns (though I'd be curious whether these patterns optimize well or not), so if the check was specific to finding that scenario, that would be pretty useful (though it likely requires codeflow analysis).

[lbrandy]

Someone pointed this patch/thread out to me so I wanted to give some background on what prompted the mention of this in my talk.

I think this particular bug is a _huge_ and _recurring_ problem (we've had yet more examples recently, internally) but I also believe that the legitimate uses of map::operator[] far outnumber the problematic cases. Data would sway me but my guess is that the false positive rate of this check would make it exceptionally difficult to ever enable this in anger. I don't think this is something we (facebook) could or would turn on, by default, in our codebase. I mentioned we'd had people seriously discuss banning it but none of those arguments actually turned into a consensus to act. I'd be super curious if anyone had experience actually trying to use a rule like this in their codebase. I just didn't want ya'll to have the impression that internal FB guidance and/or rules enforce this successfuly. We don't. And the reason we don't is the same reasons expressed above: that the signal-to-noise ratio seems way, way off. Obviously that doesn't mean a rule like this for clang-tidy wouldn't be useful, maybe it is, but it's a tough rule for me to believe would be a good idea to have enabled by default.

clang-tidy/bugprone/BugproneTidyModule.cpp

 #include "ForwardDeclarationNamespaceCheck.h"
 #include "ForwardingReferenceOverloadCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "IncorrectRoundingsCheck.h"
 #include "IntegerDivisionCheck.h"
 #include "LambdaFunctionNameCheck.h"
 #include "MacroParenthesesCheck.h"
 #include "MacroRepeatedSideEffectsCheck.h"
+#include "MapSubscriptOperatorLookupCheck.h"
 #include "MisplacedOperatorInStrlenInAllocCheck.h"
 #include "MisplacedWideningCastCheck.h"
 #include "MoveForwardingReferenceCheck.h"
 #include "MultipleStatementMacroCheck.h"
 #include "ParentVirtualCallCheck.h"
 #include "SizeofContainerCheck.h"
 #include "SizeofExpressionCheck.h"
 #include "StringConstructorCheck.h"
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<IntegerDivisionCheck>(
         "bugprone-integer-division");
     CheckFactories.registerCheck<LambdaFunctionNameCheck>(
         "bugprone-lambda-function-name");
     CheckFactories.registerCheck<MacroParenthesesCheck>(
         "bugprone-macro-parentheses");
     CheckFactories.registerCheck<MacroRepeatedSideEffectsCheck>(
         "bugprone-macro-repeated-side-effects");
+    CheckFactories.registerCheck<MapSubscriptOperatorLookupCheck>(
+        "bugprone-map-subscript-operator-lookup");
     CheckFactories.registerCheck<MisplacedOperatorInStrlenInAllocCheck>(
         "bugprone-misplaced-operator-in-strlen-in-alloc");
     CheckFactories.registerCheck<MisplacedWideningCastCheck>(
         "bugprone-misplaced-widening-cast");
     CheckFactories.registerCheck<MoveForwardingReferenceCheck>(
         "bugprone-move-forwarding-reference");
     CheckFactories.registerCheck<MultipleStatementMacroCheck>(
         "bugprone-multiple-statement-macro");

clang-tidy/bugprone/CMakeLists.txt

add_clang_library(clangTidyBugproneModule
   ForwardDeclarationNamespaceCheck.cpp
   ForwardingReferenceOverloadCheck.cpp
   InaccurateEraseCheck.cpp
   IncorrectRoundingsCheck.cpp
   IntegerDivisionCheck.cpp
   LambdaFunctionNameCheck.cpp
   MacroParenthesesCheck.cpp
   MacroRepeatedSideEffectsCheck.cpp
+  MapSubscriptOperatorLookupCheck.cpp
   MisplacedOperatorInStrlenInAllocCheck.cpp
   MisplacedWideningCastCheck.cpp
   MoveForwardingReferenceCheck.cpp
   MultipleStatementMacroCheck.cpp
   ParentVirtualCallCheck.cpp
   SizeofContainerCheck.cpp
   SizeofExpressionCheck.cpp
   StringConstructorCheck.cpp

clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.h

+//===--- MapSubscriptOperatorLookupCheck.h - clang-tidy----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_MAPSUBSCRIPTOPERATORLOOKUPCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_MAPSUBSCRIPTOPERATORLOOKUPCHECK_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+/// FIXME: Write a short description.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/bugprone-map-subscript-operator-lookup.html
+class MapSubscriptOperatorLookupCheck : public ClangTidyCheck {
+public:
+  MapSubscriptOperatorLookupCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+};
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_MAPSUBSCRIPTOPERATORLOOKUPCHECK_H

clang-tidy/bugprone/MapSubscriptOperatorLookupCheck.cpp

+//===--- MapSubscriptOperatorLookupCheck.cpp - clang-tidy------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "MapSubscriptOperatorLookupCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace bugprone {
+
+void MapSubscriptOperatorLookupCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(
+      cxxOperatorCallExpr(
+          callee(cxxMethodDecl(
+              hasName("operator[]"),
+              ofClass(hasAnyName("::std::map", "::std::unordered_map")))),
+          hasParent(implicitCastExpr(
+              anyOf(hasImplicitDestinationType(isConstQualified()),
+                    hasCastKind(CK_LValueToRValue)))))
+          .bind("match"),
+      this);
+}
+
+void MapSubscriptOperatorLookupCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  if (const auto *Matched = Result.Nodes.getNodeAs<CallExpr>("match")) {
+    diag(Matched->getLocStart(), "do not use operator[] for map lookup")
+        << Matched->getSourceRange();
+    diag(Matched->getLocStart(), "consider using find() instead",
+         DiagnosticIDs::Note);
+  }
+}
+
+} // namespace bugprone
+} // namespace tidy
+} // namespace clang

docs/ReleaseNotes.rst

 Improvements to clang-rename
 ----------------------------
 
 The improvements are...
 
 Improvements to clang-tidy
 --------------------------
 
+- New :doc:`bugprone-map-subscript-operator-lookup
+  <clang-tidy/checks/bugprone-map-subscript-operator-lookup>` check
+
+  FIXME: add release notes.
+
 - New module `abseil` for checks related to the `Abseil <https://abseil.io>`_
   library.
 
 - New module ``portability``.
 
 - New module ``zircon`` for checks related to Fuchsia's Zircon kernel.
 
 - New :doc:`android-comparison-in-temp-failure-retry

docs/clang-tidy/checks/bugprone-map-subscript-operator-lookup.rst

+.. title:: clang-tidy - bugprone-map-subscript-operator-lookup
+
+bugprone-map-subscript-operator-lookup
+======================================
+
+FIXME: Describe what patterns does the check detect and why. Give examples.

docs/clang-tidy/checks/list.rst

.. toctree::
    bugprone-forward-declaration-namespace
    bugprone-forwarding-reference-overload
    bugprone-inaccurate-erase
    bugprone-incorrect-roundings
    bugprone-integer-division
    bugprone-lambda-function-name
    bugprone-macro-parentheses
    bugprone-macro-repeated-side-effects
+   bugprone-map-subscript-operator-lookup
    bugprone-misplaced-operator-in-strlen-in-alloc
    bugprone-misplaced-widening-cast
    bugprone-move-forwarding-reference
    bugprone-multiple-statement-macro
    bugprone-parent-virtual-call
    bugprone-sizeof-container
    bugprone-sizeof-expression
    bugprone-string-constructor
.. toctree::
    cppcoreguidelines-pro-type-cstyle-cast
    cppcoreguidelines-pro-type-member-init
    cppcoreguidelines-pro-type-reinterpret-cast
    cppcoreguidelines-pro-type-static-cast-downcast
    cppcoreguidelines-pro-type-union-access
    cppcoreguidelines-pro-type-vararg
    cppcoreguidelines-slicing
    cppcoreguidelines-special-member-functions
-   fuchsia-header-anon-namespaces (redirects to google-build-namespaces) <fuchsia-header-anon-namespaces>
    fuchsia-default-arguments
+   fuchsia-header-anon-namespaces (redirects to google-build-namespaces) <fuchsia-header-anon-namespaces>
    fuchsia-multiple-inheritance
    fuchsia-overloaded-operator
    fuchsia-statically-constructed-objects
    fuchsia-trailing-return
    fuchsia-virtual-inheritance
    google-build-explicit-make-pair
    google-build-namespaces
    google-build-using-namespace

test/clang-tidy/bugprone-map-subscript-operator-lookup.cpp

+// RUN: %check_clang_tidy %s bugprone-map-subscript-operator-lookup %t
+
+namespace std {
+
+template <typename T>
+struct allocator {};
+
+template <typename T>
+struct equal_to {};
+
+template <typename T>
+struct hash {};
+
+template <typename T>
+struct less {};
+
+template <typename T, typename U>
+struct pair {};
+
+template <typename Key,
+          typename T,
+          typename Compare = std::less<Key>,
+          typename Allocator = std::allocator<std::pair<const Key, T>>>
+struct map {
+  T &operator[](const Key &);
+  T &operator[](Key &&);
+};
+
+// the check should be able to match std lib calls even if the functions are
+// declared inside inline namespaces
+inline namespace v1 {
+
+template <typename Key,
+          typename T,
+          typename Hash = std::hash<Key>,
+          typename KeyEqual = std::equal_to<Key>,
+          typename Allocator = std::allocator<std::pair<const Key, T>>>
+struct unordered_map {
+  T &operator[](const Key &);
+  T &operator[](Key &&);
+};
+
+} // namespace v1
+} // namespace std
+
+struct Foo {
+  int getter() const;
+  void setter(int);
+};
+
+void warning() {
+  std::map<int, Foo> Map;
+  auto Foo1 = Map[42];
+  // CHECK-MESSAGES: [[@LINE-1]]:15: warning: do not use operator[] for map lookup [bugprone-map-subscript-operator-lookup]
+
+  std::unordered_map<int, Foo> UMap;
+  auto Foo2 = UMap[42];
+  // CHECK-MESSAGES: [[@LINE-1]]:15: warning: do not use operator[] for map lookup [bugprone-map-subscript-operator-lookup]
+}
+
+void noWarning() {
+  std::map<int, Foo> MapOk;
+  MapOk[42] = Foo{};
+
+  std::unordered_map<int, Foo> UMapOk;
+  UMapOk[42] = Foo{};
+}