[clang-tidy] Add `readability-container-contains` check

[avogelsgesang]

Summary

This commit introduces a new check readability-container-contains
which finds usages of container.count() which should be replaced
by a call to the container.contains() method introduced in C++ 20.

For containers which permit multiple entries per key (multimap,
multiset, ...), contains is more efficient than count because
count has to do unnecessary additional work.

While this this performance difference does not exist for containers
with only a single entry per key (map, unordered_map, ...),
contains still conveys the intent better.

[whisperity]

Why readability-, if the intent is to make users move to a newer API?

@xazax.hun I think you did something similar wrt. empty(), right? Could you take a look at this?

clang-tools-extra/docs/clang-tidy/checks/list.rst

346–348

These are unrelated changes coming from a lack of rebase or a too eager diff.

clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst

16

The indentation looks offset for the 2nd column here.

[avogelsgesang]

Why readability-, if the intent is to make users move to a newer API?

My line of thinking was:

1. The very similar readability-container-size-empty pass is also a readability pass.
2. The main reason why I want people to use contains over count is because of readability. For this rule, I want to use modern C++20, not because my intent is to "modernize" per se, but because my intent is to make the C++ code more readable afterwards

That being said, I don't care strongly about readability- vs. modernize- and if you prefer, I can move the check to modernize.

[avogelsgesang]

clang-tools-extra/docs/clang-tidy/checks/list.rst

346–348

those changes were added by add_new_check.py.
I guess add_new_check.py recreates the complete list.rst file, and the previously checked in list.rst was not in sync with the remaining files...

Do you want me to remove those changes from this commit?

[avogelsgesang]

Fix formatting; remove unrelated changes

[avogelsgesang]

clang-tools-extra/docs/clang-tidy/checks/list.rst

346–348

I removed the other changes from this commit

[xazax.hun]

In D112646#3092619, @whisperity wrote:

@xazax.hun I think you did something similar wrt. empty(), right? Could you take a look at this?

The idea looks good to me. The module also sounds right. If we want to follow container-size-empty's convention, we should include the replaced method in the name. But I am not insisting on anything.

[avogelsgesang]

[...] If we want to follow container-size-empty's convention, we should include the replaced method in the name [...]

Note that this commit is slightly different from container-size-empty: it doesn't only replace count(...) by contains(...) but also replaces find() == end() by contains. So I guess the name would have to be container-count-begin-end-contains or similar... which would be a bit much in my opinion

[avogelsgesang]

gentle ping

[avogelsgesang]

Update docs to also mention container.find() != container.end()

[avogelsgesang]

@xazax.hun / @whisperity could you review this change for me, please :)
Or, alternatively: can you direct me to somebody who could review?

[aaron.ballman]

In D112646#3132141, @avogelsgesang wrote:

@xazax.hun / @whisperity could you review this change for me, please :)
Or, alternatively: can you direct me to somebody who could review?

I've added a few more folks to the reviewer list just in case they're able to get to this before I am. FWIW, I was initially surprised that this is not in modernize- but the explanation about why the author wants it in readability- was compelling enough for me to think it's fine there. I haven't had the chance to give this a thorough review yet, but I like the general direction and appreciate the new check!

[whisperity]

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp

50

Same comment about "membership" or "element" instead of "containment" here.

74

Same comment about "membership" or "element" instead of "containment" here.

94

104

111

I'm not sure if these comments are useful, though. The business logic flow of the implementation is straightforward.

114

This might be a bit nitpicking, but containment sounds off here: it usually comes up with regards to superset/subset relationships. Perhaps phrasing in membership or element somehow would ease this.

114

We use single apostrophe (') instead of backtick (`) in the diagnostics for symbol names.

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.h

20

clang-tools-extra/docs/ReleaseNotes.rst

105–106

Due to RST specifics, the code examples to be rendered as such, double backticks have to be used... Single backtick renders in a different font with emphasis (see example, blue), while double backtick is a proper monospace inline code snippet (see example, red).

106

clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst

7

Same comment about the backtick count and how you would like the rendering to be. Please build the documentation locally and verify visually, as both ways most likely compile without warnings or errors.

7

clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp

34–36

Tests are to guard our future selves from breaking the system, so perhaps two tests that involve having std:: typed out, and also using a different container that's not std::whatever would be useful.

---

Do you think it would be worthwhile to add matching any user-defined object which has a count() and a contains() method (with the appropriate number of parameters) later? So match not only the few standard containers, but more stuff?

It doesn't have to be done now, but having a test for MyContainer not in std:: being marked // NO-WARNING. or something could indicate that we purposefully don't want to go down that road just yet.

112

Similarly, the test file could use at least some negative examples. Things like count(X) >= 2 and such, to ensure that the matchers aren't inadvertently broken by someone which would result in a lot of false positives in production.

[whisperity]

In D112646#3104236, @avogelsgesang wrote:

So I guess the name would have to be container-count-begin-end-contains or similar... which would be a bit much in my opinion

Yeah, that would be too much indeed.

However, consider readability-container-use-contains. It indicates a bit more that we want people to write terse code that is clear about its intentions.

[whisperity]

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp

106–109

Comparison instead of Check? These should be matching the binaryOperator, right?

[avogelsgesang]

Address review comments by @whisperity:

• "containment" -> "membership"
• "C++ 20" -> "C++20"
• double-backticks in rst files
• additonal test cases (both positive and negative)

Also:

• use hasUnqualifiedDesugaredType -> handle typedefs better

[avogelsgesang]

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp

106–109

In most cases, they match the binaryOperator. For the first pattern they match the implicitCastExpr, though

Given this is not always a binaryOperator, should I still rename it to Comparison?

111

Agree, not sure how much value they provide.
Let me know if I should delete them, or if we want to keep them for the structure they introduce...

114

but containment sounds off here

Agree. Thanks for catching this!

clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst

7

Please build the documentation locally [...]

How do I actually do that?

clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp

34–36

so perhaps two tests that involve having std:: typed out

rewrote the tests, such that most of them use fully-qualified types. Also added a few test cases involving type defs and namespace aliases (this actually uncovered a mistake in the matcher)

Do you think it would be worthwhile to add matching any user-defined object which has a count() and a contains() method (with the appropriate number of parameters) later?

Not sure. At least not for the code base I wrote this check for...

having a test for MyContainer not in std:: being marked // NO-WARNING. or something could indicate that we purposefully don't want to go down that road just yet

added such a test case and commented it as "not currently supported"

112

Added a couple of negative test cases. Please let me know if you have additional additional test cases in mind which I should also add

[avogelsgesang]

Fix test case

[whisperity]

Thank you, this is getting much better!

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp

106–109

Comparison is okay. Just Check, Positive and Negative seem a bit ambiguous at first glance.

clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst

7

You need to install [[ http://pypi.org/project/Sphinx | Sphinx]]. The easiest is to install it with pip, the Python package manager. Then, you tell LLVM CMake to create the build targets for the docs, and run it:

~$ python3 -m venv sphinx-venv
~$ source ~/sphinx-venv/bin/activate
(sphinx-venv) ~$ pip install sphinx
(sphinx-venv) ~$ cd LLVM_BUILD_DIR
(sphinx-venv) LLVM_BUILD_DIR/$ cmake . -DLLVM_BUILD_DOCS=ON -DLLVM_ENABLE_SPHINX=ON
# configuration re-run
(sphinx-venv) LLVM_BUILD_DIR/$ cmake --build . -- docs-clang-tools-html
(sphinx-venv) LLVM_BUILD_DIR/$ cd ~
(sphinx-venv) ~$ deactivate
~$     # you are now back in HOME without the virtual env being active

The docs will be available starting from ${LLVM_BUILD_DIR}/tools/clang/tools/extra/docs/html/clang-tidy/index.html.

clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp

34–36

In D112646#3135409, @avogelsgesang wrote:

added such a test case and commented it as "not currently supported"

Thank you! It will be enough for now, I believe.

115

Make sure to format it against 80-line, and also, we conventionally write full sentences in comments.

129

174

189

If a fix is not generated, why is this line here?

[avogelsgesang]

Address review comments

clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp

189

I added this test expectation to make sure that the line is kept unchanged.

I followed https://clang.llvm.org/extra/clang-tidy/Contributing.html#testing-checks:

In particular, CHECK-FIXES: can be used to check that code was not modified by fix-its, by checking that it is present unchanged in the fixed code.

Based on this, I thought it is best practice to also check that places which I expect to stay unmodified are actually left unmodified. But I am not sure what the expectations in the clang-tidy code base are and whether those "the code stays unmodified" checks are actually encouraged or discouraged.
So just say the word and I am happy to remove this test expectation...

[avogelsgesang]

Fix build error in documentation and update wording

[avogelsgesang]

Thanks for the instructions on how to build the documentation!
I fixed a build issue in the docs (incorrect length of the table footer) and updated the wording slightly

I am not planning any additional changes. If there is anything else you would want me to change, please let me know.
Otherwise, in case you approve this change, can you please also merge it on my behalf? I do not have commit access

[avogelsgesang]

gentle ping

[avogelsgesang]

Happy new year! - and a gentle ping ;)

Afaict, there are only two smaller issues remaining (see non-closed inline comments):

• do we want a test expectation to check for unmodified code
• should we remove a couple of comments from the code

Personally, I have no real opinion on those questions. Would be happy to get some guidance here, @whisperity, so we can wrap this review up

[avogelsgesang]

@aaron.ballman @xazax.hun Could I ask one of you to finish the review here? :)

[xazax.hun]

Hi!

Overall the check looks good to me, I have only one problem. We usually try to avoid emitting fixes when some parts of the replaced text is from a macro, e.g.:

#define MYMACRO(X) count(X)

if (myCont.MYMACRO(X))
 ...

In the above code snippet, we want to avoid modifying the source inside the definition of MYMACRO, because that could render the code incorrect if MYMACRO is used in another context, e.g. with a custom container as well. I think most tidy checks are explicitly guarding the replacements to avoid these situations.

Once this is fixed and a test is added, the rest looks good to me.

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp

113

Should we have an assert to express that only one of PositiveComparison and NegativeComparison expected to be not-null?

[avogelsgesang]

Properly support macros as requested by @xazax.hun

Added test cases for
+#define COUNT_ONES(SET) SET.count(1)
+ CHECK-FIXES: #define COUNT_ONES(SET) SET.count(1)
+ Rewriting the macro would break the code
+ if (COUNT_ONES(MySet)) {
+ return COUNT_ONES(MySet);
+ }
+#undef COUNT_ONES
+#define COUNT_ONES count(1)
+ CHECK-FIXES: #define COUNT_ONES count(1)
+ Rewriting the macro would break the code
+ if (MySet.COUNT_ONES) {
+ return MySet.COUNT_ONES;
+ }
+#undef COUNT_ONES
+#define MY_SET MySet
+ CHECK-FIXES: #define MY_SET MySet
+ We still want to rewrite one of the two calls to count
+ if (MY_SET.count(1)) {
+ CHECK-MESSAGES: :[[@LINE-1]]:14: warning: use 'contains' to check for membership [readability-container-contains]
+ CHECK-FIXES: if (MY_SET.contains(1)) {
+ return MY_SET.count(1);
+ }

Please let me know if I missed any cases

[xazax.hun]

LGTM! Thanks!

[xazax.hun]

Oh wait, I think if the call is coming from a macro we still want to warn, we just want to skip the FIXIT part and leave it to the user.

[avogelsgesang]

Still warn for issues in macros even if not offering a fix-it

[avogelsgesang]

@xazax.hun Can you please merge this to main on my behalf? (I don't have commit rights)

[avogelsgesang]

@xazax.hun ping re merging this to main. Would be amazing to get this in still in time for clang 14.

In case it makes merging easier for you, there is a copy of this commit on https://github.com/vogelsgesang/llvm-project/commits/avogelsgesang-tidy-readability-container-contains

[xazax.hun]

In D112646#3264010, @avogelsgesang wrote:

@xazax.hun ping re merging this to main. Would be amazing to get this in still in time for clang 14.

Sorry for the delay. I'm on vacation at the moment and will not be able to commit it in the next couple of weeks. But I asked @whisperity to take a final look and commit it if there is nothing else that needs to be changed and he kindly agreed.

[whisperity]

In D112646#3251025, @avogelsgesang wrote:

@xazax.hun Can you please merge this to main on my behalf? (I don't have commit rights)

Hey! Sorry for my absence, I'm terribly busy with doing stuffs 😦 I'll check the patch now, generally looks good. Please specify what name and e-mail address you'd like to have the Git commit author attributed with!

[whisperity]

In D112646#3265670, @whisperity wrote:

Please specify what name and e-mail address you'd like to have the Git commit author attributed with!

Nevermind, I forgot that you commented this:

In D112646#3264010, @avogelsgesang wrote:

there is a copy of this commit on https://github.com/vogelsgesang/llvm-project/commits/avogelsgesang-tidy-readability-container-contains

---

LGTM. Committing in a moment. 😉 (I applied a fix to a typo in a comment in the test, time begin -> time being.)

[avogelsgesang]

Thanks, @xazax.hun and @whisperity for helping me to get this over the finish line! :)

clang-tools-extra/clang-tidy/readability/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   FrontendOpenMP
   Support
   )
 
 add_clang_library(clangTidyReadabilityModule
   AvoidConstParamsInDecls.cpp
   BracesAroundStatementsCheck.cpp
   ConstReturnTypeCheck.cpp
+  ContainerContainsCheck.cpp
   ContainerDataPointerCheck.cpp
   ContainerSizeEmptyCheck.cpp
   ConvertMemberFunctionsToStatic.cpp
   DeleteNullPointerCheck.cpp
   ElseAfterReturnCheck.cpp
   FunctionCognitiveComplexityCheck.cpp
   FunctionSizeCheck.cpp
   IdentifierLengthCheck.cpp

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.h

+//===--- ContainerContainsCheck.h - clang-tidy ------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_CONTAINERCONTAINSCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_CONTAINERCONTAINSCHECK_H
+
+#include "../ClangTidyCheck.h"
+
+namespace clang {
+namespace tidy {
+namespace readability {
+
+/// Finds usages of `container.count()` and `find() == end()` which should be
+/// replaced by a call to the `container.contains()` method introduced in C++20.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/readability-container-contains.html
+class ContainerContainsCheck : public ClangTidyCheck {
+public:
+  ContainerContainsCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) final;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) final;
+
+protected:
+  bool isLanguageVersionSupported(const LangOptions &LO) const final {
+    return LO.CPlusPlus20;
+  }
+};
+
+} // namespace readability
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_CONTAINERCONTAINSCHECK_H

clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp

+//===--- ContainerContainsCheck.cpp - clang-tidy --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "ContainerContainsCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace readability {
+
+void ContainerContainsCheck::registerMatchers(MatchFinder *Finder) {
+  const auto SupportedContainers = hasType(
+      hasUnqualifiedDesugaredType(recordType(hasDeclaration(cxxRecordDecl(
+          hasAnyName("::std::set", "::std::unordered_set", "::std::map",
+                     "::std::unordered_map", "::std::multiset",
+                     "::std::unordered_multiset", "::std::multimap",
+                     "::std::unordered_multimap"))))));
+
+  const auto CountCall =
+      cxxMemberCallExpr(on(SupportedContainers),
+                        callee(cxxMethodDecl(hasName("count"))),
+                        argumentCountIs(1))
+          .bind("call");
+
+  const auto FindCall =
+      cxxMemberCallExpr(on(SupportedContainers),
+                        callee(cxxMethodDecl(hasName("find"))),
+                        argumentCountIs(1))
+          .bind("call");
+
+  const auto EndCall = cxxMemberCallExpr(on(SupportedContainers),
+                                         callee(cxxMethodDecl(hasName("end"))),
+                                         argumentCountIs(0));
+
+  const auto Literal0 = integerLiteral(equals(0));
+  const auto Literal1 = integerLiteral(equals(1));
+
+  auto AddSimpleMatcher = [&](auto Matcher) {
+    Finder->addMatcher(
+        traverse(TK_IgnoreUnlessSpelledInSource, std::move(Matcher)), this);
+  };
+
+  // Find membership tests which use `count()`.
+  Finder->addMatcher(implicitCastExpr(hasImplicitDestinationType(booleanType()),
+                                      hasSourceExpression(CountCall))
+                         .bind("positive"),
+                     this);
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(CountCall), hasOperatorName("!="), hasRHS(Literal0))
+          .bind("positive"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(Literal0), hasOperatorName("!="), hasRHS(CountCall))
+          .bind("positive"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(CountCall), hasOperatorName(">"), hasRHS(Literal0))
+          .bind("positive"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(Literal0), hasOperatorName("<"), hasRHS(CountCall))
+          .bind("positive"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(CountCall), hasOperatorName(">="), hasRHS(Literal1))
+          .bind("positive"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(Literal1), hasOperatorName("<="), hasRHS(CountCall))
+          .bind("positive"));
+
+  // Find inverted membership tests which use `count()`.
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(CountCall), hasOperatorName("=="), hasRHS(Literal0))
+          .bind("negative"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(Literal0), hasOperatorName("=="), hasRHS(CountCall))
+          .bind("negative"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(CountCall), hasOperatorName("<="), hasRHS(Literal0))
+          .bind("negative"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(Literal0), hasOperatorName(">="), hasRHS(CountCall))
+          .bind("negative"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(CountCall), hasOperatorName("<"), hasRHS(Literal1))
+          .bind("negative"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(Literal1), hasOperatorName(">"), hasRHS(CountCall))
+          .bind("negative"));
+
+  // Find membership tests based on `find() == end()`.
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(FindCall), hasOperatorName("!="), hasRHS(EndCall))
+          .bind("positive"));
+  AddSimpleMatcher(
+      binaryOperator(hasLHS(FindCall), hasOperatorName("=="), hasRHS(EndCall))
+          .bind("negative"));
+}
+
+void ContainerContainsCheck::check(const MatchFinder::MatchResult &Result) {
+  // Extract the information about the match
+  const auto *Call = Result.Nodes.getNodeAs<CXXMemberCallExpr>("call");
+  const auto *PositiveCheck = Result.Nodes.getNodeAs<Expr>("positive");
+  const auto *NegativeCheck = Result.Nodes.getNodeAs<Expr>("negative");
+  bool Negated = NegativeCheck != nullptr;
+  const auto *Check = Negated ? NegativeCheck : PositiveCheck;
+
+  // Diagnose the issue.
+  auto Diag =
+      diag(Call->getExprLoc(), "use 'contains' to check for membership");
+
+  // Create the fix it.
+  const auto *Member = cast<MemberExpr>(Call->getCallee());
+  Diag << FixItHint::CreateReplacement(
+      Member->getMemberNameInfo().getSourceRange(), "contains");
+  SourceLocation CheckBegin = Check->getSourceRange().getBegin();
+  SourceLocation CheckEnd = Check->getSourceRange().getEnd();
+  SourceLocation CallBegin = Call->getSourceRange().getBegin();
+  SourceLocation CallEnd = Call->getSourceRange().getEnd();
+  Diag << FixItHint::CreateReplacement(
+      CharSourceRange::getCharRange(CheckBegin, CallBegin), Negated ? "!" : "");
+  Diag << FixItHint::CreateRemoval(CharSourceRange::getCharRange(
+      CallEnd.getLocWithOffset(1), CheckEnd.getLocWithOffset(1)));
+}
+
+} // namespace readability
+} // namespace tidy
+} // namespace clang

clang-tools-extra/clang-tidy/readability/ReadabilityTidyModule.cpp

 //===--- ReadabilityTidyModule.cpp - clang-tidy ---------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "AvoidConstParamsInDecls.h"
 #include "BracesAroundStatementsCheck.h"
 #include "ConstReturnTypeCheck.h"
+#include "ContainerContainsCheck.h"
 #include "ContainerDataPointerCheck.h"
 #include "ContainerSizeEmptyCheck.h"
 #include "ConvertMemberFunctionsToStatic.h"
 #include "DeleteNullPointerCheck.h"
 #include "ElseAfterReturnCheck.h"
 #include "FunctionCognitiveComplexityCheck.h"
 #include "FunctionSizeCheck.h"
 #include "IdentifierLengthCheck.h"

 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<AvoidConstParamsInDecls>(
         "readability-avoid-const-params-in-decls");
     CheckFactories.registerCheck<BracesAroundStatementsCheck>(
         "readability-braces-around-statements");
     CheckFactories.registerCheck<ConstReturnTypeCheck>(
         "readability-const-return-type");
+    CheckFactories.registerCheck<ContainerContainsCheck>(
+        "readability-container-contains");
     CheckFactories.registerCheck<ContainerDataPointerCheck>(
         "readability-container-data-pointer");
     CheckFactories.registerCheck<ContainerSizeEmptyCheck>(
         "readability-container-size-empty");
     CheckFactories.registerCheck<ConvertMemberFunctionsToStatic>(
         "readability-convert-member-functions-to-static");
     CheckFactories.registerCheck<DeleteNullPointerCheck>(
         "readability-delete-null-pointer");

clang-tools-extra/docs/ReleaseNotes.rst

- New :doc:`cppcoreguidelines-virtual-class-destructor
 
   Finds virtual classes whose destructor is neither public and virtual nor
   protected and non-virtual.
 
 - New :doc:`misc-misleading-identifier <clang-tidy/checks/misc-misleading-identifier>` check.
 
   Reports identifier with unicode right-to-left characters.
 
+- New :doc:`readability-container-contains
+  <clang-tidy/checks/readability-container-contains>` check.
+
+  Finds usages of ``container.count()`` and ``container.find() == container.end()`` which should
+  be replaced by a call to the ``container.contains()`` method introduced in C++20.
+
 - New :doc:`readability-container-data-pointer
   <clang-tidy/checks/readability-container-data-pointer>` check.
 
   Finds cases where code could use ``data()`` rather than the address of the
   element at index 0 in a container.
 
 - New :doc:`readability-identifier-length
   <clang-tidy/checks/readability-identifier-length>` check.

clang-tools-extra/docs/clang-tidy/checks/list.rst

.. csv-table::
    `performance-type-promotion-in-math-fn <performance-type-promotion-in-math-fn.html>`_, "Yes"
    `performance-unnecessary-copy-initialization <performance-unnecessary-copy-initialization.html>`_,
    `performance-unnecessary-value-param <performance-unnecessary-value-param.html>`_, "Yes"
    `portability-restrict-system-includes <portability-restrict-system-includes.html>`_, "Yes"
    `portability-simd-intrinsics <portability-simd-intrinsics.html>`_,
    `readability-avoid-const-params-in-decls <readability-avoid-const-params-in-decls.html>`_,
    `readability-braces-around-statements <readability-braces-around-statements.html>`_, "Yes"
    `readability-const-return-type <readability-const-return-type.html>`_, "Yes"
+   `readability-container-contains <readability-container-contains.html>`_, "Yes"
    `readability-container-data-pointer <readability-container-data-pointer.html>`_, "Yes"
    `readability-container-size-empty <readability-container-size-empty.html>`_, "Yes"
    `readability-convert-member-functions-to-static <readability-convert-member-functions-to-static.html>`_,
    `readability-delete-null-pointer <readability-delete-null-pointer.html>`_, "Yes"
    `readability-else-after-return <readability-else-after-return.html>`_, "Yes"
    `readability-function-cognitive-complexity <readability-function-cognitive-complexity.html>`_,
    `readability-function-size <readability-function-size.html>`_,
    `readability-identifier-length <readability-identifier-length.html>`_,
.. csv-table:: Aliases..
    `cert-dcl16-c <cert-dcl16-c.html>`_, `readability-uppercase-literal-suffix <readability-uppercase-literal-suffix.html>`_, "Yes"
    `cert-dcl37-c <cert-dcl37-c.html>`_, `bugprone-reserved-identifier <bugprone-reserved-identifier.html>`_, "Yes"
    `cert-err33-c <cert-err33-c.html>`_, `bugprone-unused-return-value <bugprone-unused-return-value.html>`_,
    `cert-dcl51-cpp <cert-dcl51-cpp.html>`_, `bugprone-reserved-identifier <bugprone-reserved-identifier.html>`_, "Yes"
    `cert-dcl54-cpp <cert-dcl54-cpp.html>`_, `misc-new-delete-overloads <misc-new-delete-overloads.html>`_,
    `cert-dcl59-cpp <cert-dcl59-cpp.html>`_, `google-build-namespaces <google-build-namespaces.html>`_,
    `cert-err09-cpp <cert-err09-cpp.html>`_, `misc-throw-by-value-catch-by-reference <misc-throw-by-value-catch-by-reference.html>`_,
    `cert-err61-cpp <cert-err61-cpp.html>`_, `misc-throw-by-value-catch-by-reference <misc-throw-by-value-catch-by-reference.html>`_,
    `cert-fio38-c <cert-fio38-c.html>`_, `misc-non-copyable-objects <misc-non-copyable-objects.html>`_,
    `cert-msc30-c <cert-msc30-c.html>`_, `cert-msc50-cpp <cert-msc50-cpp.html>`_,
    `cert-msc32-c <cert-msc32-c.html>`_, `cert-msc51-cpp <cert-msc51-cpp.html>`_,
    `cert-oop11-cpp <cert-oop11-cpp.html>`_, `performance-move-constructor-init <performance-move-constructor-init.html>`_,
    `cert-oop54-cpp <cert-oop54-cpp.html>`_, `bugprone-unhandled-self-assignment <bugprone-unhandled-self-assignment.html>`_,
    `cert-pos44-c <cert-pos44-c.html>`_, `bugprone-bad-signal-to-kill-thread <bugprone-bad-signal-to-kill-thread.html>`_,
    `cert-pos47-c <cert-pos47-c.html>`_, `concurrency-thread-canceltype-asynchronous <concurrency-thread-canceltype-asynchronous.html>`_,
    `cert-sig30-c <cert-sig30-c.html>`_, `bugprone-signal-handler <bugprone-signal-handler.html>`_,
    `cert-str34-c <cert-str34-c.html>`_, `bugprone-signed-char-misuse <bugprone-signed-char-misuse.html>`_,
    `clang-analyzer-core.CallAndMessage <clang-analyzer-core.CallAndMessage.html>`_, `Clang Static Analyzer <https://clang.llvm.org/docs/analyzer/checkers.html>`_,
    `clang-analyzer-core.DivideZero <clang-analyzer-core.DivideZero.html>`_, `Clang Static Analyzer <https://clang.llvm.org/docs/analyzer/checkers.html>`_,

clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst

+.. title:: clang-tidy - readability-container-contains
+
+readability-container-contains
+==============================
+
+Finds usages of ``container.count()`` and ``container.find() == container.end()`` which should be replaced by a call to the ``container.contains()`` method introduced in C++ 20.
+
+Whether an element is contained inside a container should be checked with ``contains`` instead of ``count``/``find``. For containers which permit multiple entries per key (``multimap``, ``multiset``, ...), ``contains`` is more efficient than ``count`` because ``count`` has to do unnecessary additional work. While this this performance difference does not exist for containes with only a single entry per key (``map``, ``unordered_map``, ...), ``contains`` still conveys the intent better.
+
+Examples:
+
+===========================================  ==============================
+Initial expression                           Result
+-------------------------------------------  ------------------------------
+``myMap.find(x) == myMap.end()``             ``!myMap.contains(x)``
+``myMap.find(x) != myMap.end()``             ``myMap.contains(x)``
+``if (myMap.count(x))``                      ``if (myMap.contains(x))``
+``bool exists = myMap.count(x)``             ``bool exists = myMap.contains(x)``
+``bool exists = myMap.count(x) > 0``         ``bool exists = myMap.contains(x)``
+``bool exists = myMap.count(x) >= 1``        ``bool exists = myMap.contains(x)``
+``bool missing = myMap.count(x) == 0``       ``bool missing = !myMap.contains(x)``
+===========================================  ================
+
+This check applies to ``std::set``, ``std::unordered_set``, ``std::map``, ``std::unordered_map`` and the corresponding multi-key variants.
+It is only active for C++20 and later, as the ``contains`` method was only added in C++20.

clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp

+// RUN: %check_clang_tidy -std=c++20 %s readability-container-contains %t
+
+// Some *very* simplified versions of `map` etc.
+namespace std {
+
+template <class Key, class T>
+struct map {
+  unsigned count(const Key &K) const;
+  bool contains(const Key &K) const;
+  void *find(const Key &K);
+  void *end();
+};
+
+template <class Key>
+struct set {
+  unsigned count(const Key &K) const;
+  bool contains(const Key &K) const;
+};
+
+template <class Key>
+struct unordered_set {
+  unsigned count(const Key &K) const;
+  bool contains(const Key &K) const;
+};
+
+template <class Key, class T>
+struct multimap {
+  unsigned count(const Key &K) const;
+  bool contains(const Key &K) const;
+};
+
+} // namespace std
+
+// Check that we detect various common ways to check for membership
+int testDifferentCheckTypes(std::map<int, int> &MyMap) {
+  if (MyMap.count(0))
+    // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: use 'contains' to check for membership [readability-container-contains]
+    // CHECK-FIXES: if (MyMap.contains(0))
+    return 1;
+  bool C1 = MyMap.count(1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C1 = MyMap.contains(1);
+  auto C2 = static_cast<bool>(MyMap.count(1));
+  // CHECK-MESSAGES: :[[@LINE-1]]:37: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C2 = static_cast<bool>(MyMap.contains(1));
+  auto C3 = MyMap.count(2) != 0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C3 = MyMap.contains(2);
+  auto C4 = MyMap.count(3) > 0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C4 = MyMap.contains(3);
+  auto C5 = MyMap.count(4) >= 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C5 = MyMap.contains(4);
+  auto C6 = MyMap.find(5) != MyMap.end();
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C6 = MyMap.contains(5);
+  return C1 + C2 + C3 + C4 + C5 + C6;
+}
+
+// Check that we detect various common ways to check for non-membership
+int testNegativeChecks(std::map<int, int> &MyMap) {
+  bool C1 = !MyMap.count(-1);
+  // CHECK-MESSAGES: :[[@LINE-1]]:20: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C1 = !MyMap.contains(-1);
+  auto C2 = MyMap.count(-2) == 0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C2 = !MyMap.contains(-2);
+  auto C3 = MyMap.count(-3) <= 0;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C3 = !MyMap.contains(-3);
+  auto C4 = MyMap.count(-4) < 1;
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C4 = !MyMap.contains(-4);
+  auto C5 = MyMap.find(-5) == MyMap.end();
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: auto C5 = !MyMap.contains(-5);
+  return C1 + C2 + C3 + C4 + C5;
+}
+
+// Check for various types
+int testDifferentTypes(std::map<int, int> &M, std::unordered_set<int> &US, std::set<int> &S, std::multimap<int, int> &MM) {
+  bool C1 = M.count(1001);
+  // CHECK-MESSAGES: :[[@LINE-1]]:15: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C1 = M.contains(1001);
+  bool C2 = US.count(1002);
+  // CHECK-MESSAGES: :[[@LINE-1]]:16: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C2 = US.contains(1002);
+  bool C3 = S.count(1003);
+  // CHECK-MESSAGES: :[[@LINE-1]]:15: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C3 = S.contains(1003);
+  bool C4 = MM.count(1004);
+  // CHECK-MESSAGES: :[[@LINE-1]]:16: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C4 = MM.contains(1004);
+  return C1 + C2 + C3 + C4;
+}
+
+// The check detects all kind of `const`, reference, rvalue-reference and value types.
+int testQualifiedTypes(std::map<int, int> ValueM, std::map<int, int> &RefM, const std::map<int, int> &ConstRefM, std::map<int, int> &&RValueM) {
+  bool C1 = ValueM.count(2001);
+  // CHECK-MESSAGES: :[[@LINE-1]]:20: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C1 = ValueM.contains(2001);
+  bool C2 = RefM.count(2002);
+  // CHECK-MESSAGES: :[[@LINE-1]]:18: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C2 = RefM.contains(2002);
+  bool C3 = ConstRefM.count(2003);
+  // CHECK-MESSAGES: :[[@LINE-1]]:23: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C3 = ConstRefM.contains(2003);
+  bool C4 = RValueM.count(2004);
+  // CHECK-MESSAGES: :[[@LINE-1]]:21: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C4 = RValueM.contains(2004);
+  return C1 + C2 + C3 + C4;
+}
+
+// This is effectively a membership check, as the result is implicitely casted to `bool`
+bool returnContains(std::map<int, int> &M) {
+  return M.count(42);
+  // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: return M.contains(42);
+}
+
+// This returns the actual count and should not be rewritten
+int actualCount(std::multimap<int, int> &M) {
+  return M.count(21);
+  // NO-WARNING.
+  // CHECK-FIXES: return M.count(21);
+}
+
+// Check that we are not confused by aliases
+namespace s2 = std;
+using MyMapT = s2::map<int, int>;
+int typeAliases(MyMapT &MyMap) {
+  bool C1 = MyMap.count(99);
+  // CHECK-MESSAGES: :[[@LINE-1]]:19: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: bool C1 = MyMap.contains(99);
+  return C1;
+}
+
+/// Check that the tests also trigger for a local variable and not only for function arguments
+bool localVar() {
+  using namespace std;
+  map<int, int> LocalM;
+  return LocalM.count(42);
+  // CHECK-MESSAGES: :[[@LINE-1]]:17: warning: use 'contains' to check for membership [readability-container-contains]
+  // CHECK-FIXES: return LocalM.contains(42);
+}
+
+// Check various usages of an actual `count` which isn't rewritten
+int nonRewrittenCount(std::multimap<int, int> &MyMap) {
+  // This is an actual test if we have at least 2 usages. Shouldn't be rewritten.
+  bool C1 = MyMap.count(1) >= 2;
+  // NO-WARNING.
+  // CHECK-FIXES: bool C1 = MyMap.count(1) >= 2;
+
+  // "< 0" makes little sense and is always `false`. Still, let's ensure we don't accidentally rewrite it to 'contains'
+  bool C2 = MyMap.count(2) < 0;
+  // NO-WARNING.
+  // CHECK-FIXES: bool C2 = MyMap.count(2) < 0;
+
+  // The `count` is used in some more complicated formula
+  bool C3 = MyMap.count(1) + MyMap.count(2) * 2 + MyMap.count(3) / 3 >= 20;
+  // NO-WARNING.
+  // CHECK-FIXES: bool C3 = MyMap.count(1) + MyMap.count(2) * 2 + MyMap.count(3) / 3 >= 20;
+
+  // This could theoretically be rewritten into a 'contains' after removig the `4` on both sides of the comparison.
+  // For the tiime begin, we don't detect this case.
+  bool C4 = MyMap.count(1) + 4 > 4;
+  // NO-WARNING.
+  // CHECK-FIXES: bool C4 = MyMap.count(1) + 4 > 4;
+
+  return C1 + C2 + C3 + C4;
+}
+
+// The following map has the same interface like `std::map`
+template <class Key, class T>
+struct CustomMap {
+  unsigned count(const Key &K) const;
+  bool contains(const Key &K) const;
+  void *find(const Key &K);
+  void *end();
+};
+
+// The clang-tidy check is currently hard-coded against the `std::` containers and
+// hence won't annotate the following instance. We might change this in the future
+// and also detect the following case.
+void *testDifferentCheckTypes(CustomMap<int, int> &MyMap) {
+  if (MyMap.count(0))
+    // NO-WARNING.
+    // CHECK-FIXES: if (MyMap.count(0))
+    return nullptr;
+  return MyMap.find(2);
+}