diff --git a/clang-tools-extra/clang-tidy/readability/CMakeLists.txt b/clang-tools-extra/clang-tidy/readability/CMakeLists.txt --- a/clang-tools-extra/clang-tidy/readability/CMakeLists.txt +++ b/clang-tools-extra/clang-tidy/readability/CMakeLists.txt @@ -7,6 +7,7 @@ AvoidConstParamsInDecls.cpp BracesAroundStatementsCheck.cpp ConstReturnTypeCheck.cpp + ContainerContainsCheck.cpp ContainerDataPointerCheck.cpp ContainerSizeEmptyCheck.cpp ConvertMemberFunctionsToStatic.cpp diff --git a/clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.h b/clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.h new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.h @@ -0,0 +1,40 @@ +//===--- 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 diff --git a/clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp b/clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/readability/ContainerContainsCheck.cpp @@ -0,0 +1,143 @@ +//===--- 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("positiveComparison"), + this); + AddSimpleMatcher( + binaryOperator(hasLHS(CountCall), hasOperatorName("!="), hasRHS(Literal0)) + .bind("positiveComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(Literal0), hasOperatorName("!="), hasRHS(CountCall)) + .bind("positiveComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(CountCall), hasOperatorName(">"), hasRHS(Literal0)) + .bind("positiveComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(Literal0), hasOperatorName("<"), hasRHS(CountCall)) + .bind("positiveComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(CountCall), hasOperatorName(">="), hasRHS(Literal1)) + .bind("positiveComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(Literal1), hasOperatorName("<="), hasRHS(CountCall)) + .bind("positiveComparison")); + + // Find inverted membership tests which use `count()`. + AddSimpleMatcher( + binaryOperator(hasLHS(CountCall), hasOperatorName("=="), hasRHS(Literal0)) + .bind("negativeComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(Literal0), hasOperatorName("=="), hasRHS(CountCall)) + .bind("negativeComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(CountCall), hasOperatorName("<="), hasRHS(Literal0)) + .bind("negativeComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(Literal0), hasOperatorName(">="), hasRHS(CountCall)) + .bind("negativeComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(CountCall), hasOperatorName("<"), hasRHS(Literal1)) + .bind("negativeComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(Literal1), hasOperatorName(">"), hasRHS(CountCall)) + .bind("negativeComparison")); + + // Find membership tests based on `find() == end()`. + AddSimpleMatcher( + binaryOperator(hasLHS(FindCall), hasOperatorName("!="), hasRHS(EndCall)) + .bind("positiveComparison")); + AddSimpleMatcher( + binaryOperator(hasLHS(FindCall), hasOperatorName("=="), hasRHS(EndCall)) + .bind("negativeComparison")); +} + +void ContainerContainsCheck::check(const MatchFinder::MatchResult &Result) { + // Extract the information about the match + const auto *Call = Result.Nodes.getNodeAs("call"); + const auto *PositiveComparison = + Result.Nodes.getNodeAs("positiveComparison"); + const auto *NegativeComparison = + Result.Nodes.getNodeAs("negativeComparison"); + assert( + !PositiveComparison || + !NegativeComparison && + "only one of PositiveComparison or NegativeComparison should be set"); + bool Negated = NegativeComparison != nullptr; + const auto *Comparison = Negated ? NegativeComparison : PositiveComparison; + + SourceLocation FuncCallLoc = Comparison->getEndLoc(); + if (!FuncCallLoc.isValid() || FuncCallLoc.isMacroID()) + return; + + // Diagnose the issue. + auto Diag = + diag(Call->getExprLoc(), "use 'contains' to check for membership"); + + // Create the fix it. + const auto *Member = cast(Call->getCallee()); + Diag << FixItHint::CreateReplacement( + Member->getMemberNameInfo().getSourceRange(), "contains"); + SourceLocation ComparisonBegin = Comparison->getSourceRange().getBegin(); + SourceLocation ComparisonEnd = Comparison->getSourceRange().getEnd(); + SourceLocation CallBegin = Call->getSourceRange().getBegin(); + SourceLocation CallEnd = Call->getSourceRange().getEnd(); + Diag << FixItHint::CreateReplacement( + CharSourceRange::getCharRange(ComparisonBegin, CallBegin), + Negated ? "!" : ""); + Diag << FixItHint::CreateRemoval(CharSourceRange::getCharRange( + CallEnd.getLocWithOffset(1), ComparisonEnd.getLocWithOffset(1))); +} + +} // namespace readability +} // namespace tidy +} // namespace clang diff --git a/clang-tools-extra/clang-tidy/readability/ReadabilityTidyModule.cpp b/clang-tools-extra/clang-tidy/readability/ReadabilityTidyModule.cpp --- a/clang-tools-extra/clang-tidy/readability/ReadabilityTidyModule.cpp +++ b/clang-tools-extra/clang-tidy/readability/ReadabilityTidyModule.cpp @@ -12,6 +12,7 @@ #include "AvoidConstParamsInDecls.h" #include "BracesAroundStatementsCheck.h" #include "ConstReturnTypeCheck.h" +#include "ContainerContainsCheck.h" #include "ContainerDataPointerCheck.h" #include "ContainerSizeEmptyCheck.h" #include "ConvertMemberFunctionsToStatic.h" @@ -63,6 +64,8 @@ "readability-braces-around-statements"); CheckFactories.registerCheck( "readability-const-return-type"); + CheckFactories.registerCheck( + "readability-container-contains"); CheckFactories.registerCheck( "readability-container-data-pointer"); CheckFactories.registerCheck( diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -115,6 +115,12 @@ Reports identifier with unicode right-to-left characters. +- New :doc:`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 ` check. diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst --- a/clang-tools-extra/docs/clang-tidy/checks/list.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst @@ -290,6 +290,7 @@ `readability-avoid-const-params-in-decls `_, "Yes" `readability-braces-around-statements `_, "Yes" `readability-const-return-type `_, "Yes" + `readability-container-contains `_, "Yes" `readability-container-data-pointer `_, "Yes" `readability-container-size-empty `_, "Yes" `readability-convert-member-functions-to-static `_, "Yes" diff --git a/clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst b/clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst new file mode 100644 --- /dev/null +++ b/clang-tools-extra/docs/clang-tidy/checks/readability-container-contains.rst @@ -0,0 +1,25 @@ +.. 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`` because ``contains`` conveys the intent more clearly. Furthermore, for containers which permit multiple entries per key (``multimap``, ``multiset``, ...), ``contains`` is more efficient than ``count`` because ``count`` has to do unnecessary additional work. + +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. diff --git a/clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp b/clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/readability-container-contains.cpp @@ -0,0 +1,223 @@ +// RUN: %check_clang_tidy -std=c++20 %s readability-container-contains %t + +// Some *very* simplified versions of `map` etc. +namespace std { + +template +struct map { + unsigned count(const Key &K) const; + bool contains(const Key &K) const; + void *find(const Key &K); + void *end(); +}; + +template +struct set { + unsigned count(const Key &K) const; + bool contains(const Key &K) const; +}; + +template +struct unordered_set { + unsigned count(const Key &K) const; + bool contains(const Key &K) const; +}; + +template +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 &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(MyMap.count(1)); + // CHECK-MESSAGES: :[[@LINE-1]]:37: warning: use 'contains' to check for membership [readability-container-contains] + // CHECK-FIXES: auto C2 = static_cast(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 &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 &M, std::unordered_set &US, std::set &S, std::multimap &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 ValueM, std::map &RefM, const std::map &ConstRefM, std::map &&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 implicitly casted +// to `bool`. +bool returnContains(std::map &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 &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 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 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 &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 time 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; +} + +// We don't want to rewrite if the `contains` call is from a macro expansion +int testMacroExpansion(std::unordered_set &MySet) { +#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); + } +#undef MY_SET +} + +// The following map has the same interface like `std::map`. +template +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 &MyMap) { + if (MyMap.count(0)) + // NO-WARNING. + // CHECK-FIXES: if (MyMap.count(0)) + return nullptr; + return MyMap.find(2); +}