Index: clang-tidy/misc/CMakeLists.txt =================================================================== --- clang-tidy/misc/CMakeLists.txt +++ clang-tidy/misc/CMakeLists.txt @@ -7,7 +7,6 @@ BoolPointerImplicitConversionCheck.cpp DefinitionsInHeadersCheck.cpp InaccurateEraseCheck.cpp - InefficientAlgorithmCheck.cpp MacroParenthesesCheck.cpp MacroRepeatedSideEffectsCheck.cpp MiscTidyModule.cpp Index: clang-tidy/misc/InefficientAlgorithmCheck.h =================================================================== --- clang-tidy/misc/InefficientAlgorithmCheck.h +++ clang-tidy/misc/InefficientAlgorithmCheck.h @@ -1,36 +0,0 @@ -//===--- InefficientAlgorithmCheck.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_MISC_INEFFICIENTALGORITHMCHECK_H -#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENTALGORITHMCHECK_H - -#include "../ClangTidy.h" - -namespace clang { -namespace tidy { -namespace misc { - -/// Warns on inefficient use of STL algorithms on associative containers. -/// -/// Associative containers implements some of the algorithms as methods which -/// should be preferred to the algorithms in the algorithm header. The methods -/// can take advanatage of the order of the elements. -class InefficientAlgorithmCheck : public ClangTidyCheck { -public: - InefficientAlgorithmCheck(StringRef Name, ClangTidyContext *Context) - : ClangTidyCheck(Name, Context) {} - void registerMatchers(ast_matchers::MatchFinder *Finder) override; - void check(const ast_matchers::MatchFinder::MatchResult &Result) override; -}; - -} // namespace misc -} // namespace tidy -} // namespace clang - -#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENTALGORITHMCHECK_H Index: clang-tidy/misc/InefficientAlgorithmCheck.cpp =================================================================== --- clang-tidy/misc/InefficientAlgorithmCheck.cpp +++ clang-tidy/misc/InefficientAlgorithmCheck.cpp @@ -1,158 +0,0 @@ -//===--- InefficientAlgorithmCheck.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 "InefficientAlgorithmCheck.h" -#include "clang/AST/ASTContext.h" -#include "clang/ASTMatchers/ASTMatchFinder.h" -#include "clang/Lex/Lexer.h" - -using namespace clang::ast_matchers; - -namespace clang { -namespace tidy { -namespace misc { - -static bool areTypesCompatible(QualType Left, QualType Right) { - if (const auto *LeftRefType = Left->getAs()) - Left = LeftRefType->getPointeeType(); - if (const auto *RightRefType = Right->getAs()) - Right = RightRefType->getPointeeType(); - return Left->getCanonicalTypeUnqualified() == - Right->getCanonicalTypeUnqualified(); -} - -void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) { - // Only register the matchers for C++; the functionality currently does not - // provide any benefit to other languages, despite being benign. - if (!getLangOpts().CPlusPlus) - return; - - const std::string Algorithms = - "^::std::(find|count|equal_range|lower_bound|upper_bound)$"; - const auto ContainerMatcher = classTemplateSpecializationDecl( - matchesName("^::std::(unordered_)?(multi)?(set|map)$")); - const auto Matcher = - callExpr( - callee(functionDecl(matchesName(Algorithms))), - hasArgument( - 0, cxxConstructExpr(has(cxxMemberCallExpr( - callee(cxxMethodDecl(hasName("begin"))), - on(declRefExpr( - hasDeclaration(decl().bind("IneffContObj")), - anyOf(hasType(ContainerMatcher.bind("IneffCont")), - hasType(pointsTo( - ContainerMatcher.bind("IneffContPtr"))))) - .bind("IneffContExpr")))))), - hasArgument(1, cxxConstructExpr(has(cxxMemberCallExpr( - callee(cxxMethodDecl(hasName("end"))), - on(declRefExpr(hasDeclaration( - equalsBoundNode("IneffContObj")))))))), - hasArgument(2, expr().bind("AlgParam")), - unless(isInTemplateInstantiation())) - .bind("IneffAlg"); - - Finder->addMatcher(Matcher, this); -} - -void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) { - const auto *AlgCall = Result.Nodes.getNodeAs("IneffAlg"); - const auto *IneffCont = - Result.Nodes.getNodeAs("IneffCont"); - bool PtrToContainer = false; - if (!IneffCont) { - IneffCont = - Result.Nodes.getNodeAs("IneffContPtr"); - PtrToContainer = true; - } - const llvm::StringRef IneffContName = IneffCont->getName(); - const bool Unordered = - IneffContName.find("unordered") != llvm::StringRef::npos; - const bool Maplike = IneffContName.find("map") != llvm::StringRef::npos; - - // Store if the key type of the container is compatible with the value - // that is searched for. - QualType ValueType = AlgCall->getArg(2)->getType(); - QualType KeyType = - IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType(); - const bool CompatibleTypes = areTypesCompatible(KeyType, ValueType); - - // Check if the comparison type for the algorithm and the container matches. - if (AlgCall->getNumArgs() == 4 && !Unordered) { - const Expr *Arg = AlgCall->getArg(3); - const QualType AlgCmp = - Arg->getType().getUnqualifiedType().getCanonicalType(); - const unsigned CmpPosition = - (IneffContName.find("map") == llvm::StringRef::npos) ? 1 : 2; - const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition] - .getAsType() - .getUnqualifiedType() - .getCanonicalType(); - if (AlgCmp != ContainerCmp) { - diag(Arg->getLocStart(), - "different comparers used in the algorithm and the container"); - return; - } - } - - const auto *AlgDecl = AlgCall->getDirectCallee(); - if (!AlgDecl) - return; - - if (Unordered && AlgDecl->getName().find("bound") != llvm::StringRef::npos) - return; - - const auto *AlgParam = Result.Nodes.getNodeAs("AlgParam"); - const auto *IneffContExpr = Result.Nodes.getNodeAs("IneffContExpr"); - FixItHint Hint; - - SourceManager &SM = *Result.SourceManager; - LangOptions LangOpts = Result.Context->getLangOpts(); - - CharSourceRange CallRange = - CharSourceRange::getTokenRange(AlgCall->getSourceRange()); - - // FIXME: Create a common utility to extract a file range that the given token - // sequence is exactly spelled at (without macro argument expansions etc.). - // We can't use Lexer::makeFileCharRange here, because for - // - // #define F(x) x - // x(a b c); - // - // it will return "x(a b c)", when given the range "a"-"c". It makes sense for - // removals, but not for replacements. - // - // This code is over-simplified, but works for many real cases. - if (SM.isMacroArgExpansion(CallRange.getBegin()) && - SM.isMacroArgExpansion(CallRange.getEnd())) { - CallRange.setBegin(SM.getSpellingLoc(CallRange.getBegin())); - CallRange.setEnd(SM.getSpellingLoc(CallRange.getEnd())); - } - - if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) { - StringRef ContainerText = Lexer::getSourceText( - CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM, - LangOpts); - StringRef ParamText = Lexer::getSourceText( - CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM, - LangOpts); - std::string ReplacementText = - (llvm::Twine(ContainerText) + (PtrToContainer ? "->" : ".") + - AlgDecl->getName() + "(" + ParamText + ")") - .str(); - Hint = FixItHint::CreateReplacement(CallRange, ReplacementText); - } - - diag(AlgCall->getLocStart(), - "this STL algorithm call should be replaced with a container method") - << Hint; -} - -} // namespace misc -} // namespace tidy -} // namespace clang Index: clang-tidy/misc/MiscTidyModule.cpp =================================================================== --- clang-tidy/misc/MiscTidyModule.cpp +++ clang-tidy/misc/MiscTidyModule.cpp @@ -16,7 +16,6 @@ #include "BoolPointerImplicitConversionCheck.h" #include "DefinitionsInHeadersCheck.h" #include "InaccurateEraseCheck.h" -#include "InefficientAlgorithmCheck.h" #include "MacroParenthesesCheck.h" #include "MacroRepeatedSideEffectsCheck.h" #include "MoveConstantArgumentCheck.h" @@ -54,8 +53,6 @@ "misc-definitions-in-headers"); CheckFactories.registerCheck( "misc-inaccurate-erase"); - CheckFactories.registerCheck( - "misc-inefficient-algorithm"); CheckFactories.registerCheck( "misc-macro-parentheses"); CheckFactories.registerCheck( Index: clang-tidy/performance/CMakeLists.txt =================================================================== --- clang-tidy/performance/CMakeLists.txt +++ clang-tidy/performance/CMakeLists.txt @@ -1,6 +1,7 @@ set(LLVM_LINK_COMPONENTS support) add_clang_library(clangTidyPerformanceModule + InefficientAlgorithmCheck.cpp PerformanceTidyModule.cpp UnnecessaryCopyInitialization.cpp Index: clang-tidy/performance/InefficientAlgorithmCheck.h =================================================================== --- clang-tidy/performance/InefficientAlgorithmCheck.h +++ clang-tidy/performance/InefficientAlgorithmCheck.h @@ -7,14 +7,14 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENTALGORITHMCHECK_H -#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENTALGORITHMCHECK_H +#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTALGORITHMCHECK_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTALGORITHMCHECK_H #include "../ClangTidy.h" namespace clang { namespace tidy { -namespace misc { +namespace performance { /// Warns on inefficient use of STL algorithms on associative containers. /// @@ -29,8 +29,8 @@ void check(const ast_matchers::MatchFinder::MatchResult &Result) override; }; -} // namespace misc +} // namespace performance } // namespace tidy } // namespace clang -#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENTALGORITHMCHECK_H +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENTALGORITHMCHECK_H Index: clang-tidy/performance/InefficientAlgorithmCheck.cpp =================================================================== --- clang-tidy/performance/InefficientAlgorithmCheck.cpp +++ clang-tidy/performance/InefficientAlgorithmCheck.cpp @@ -16,7 +16,7 @@ namespace clang { namespace tidy { -namespace misc { +namespace performance { static bool areTypesCompatible(QualType Left, QualType Right) { if (const auto *LeftRefType = Left->getAs()) @@ -153,6 +153,6 @@ << Hint; } -} // namespace misc +} // namespace performance } // namespace tidy } // namespace clang Index: clang-tidy/performance/PerformanceTidyModule.cpp =================================================================== --- clang-tidy/performance/PerformanceTidyModule.cpp +++ clang-tidy/performance/PerformanceTidyModule.cpp @@ -10,7 +10,7 @@ #include "../ClangTidy.h" #include "../ClangTidyModule.h" #include "../ClangTidyModuleRegistry.h" - +#include "InefficientAlgorithmCheck.h" #include "UnnecessaryCopyInitialization.h" namespace clang { @@ -20,6 +20,8 @@ class PerformanceModule : public ClangTidyModule { public: void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override { + CheckFactories.registerCheck( + "performance-inefficient-algorithm"); CheckFactories.registerCheck( "performance-unnecessary-copy-initialization"); } Index: docs/clang-tidy/checks/list.rst =================================================================== --- docs/clang-tidy/checks/list.rst +++ docs/clang-tidy/checks/list.rst @@ -48,7 +48,6 @@ misc-bool-pointer-implicit-conversion misc-definitions-in-headers misc-inaccurate-erase - misc-inefficient-algorithm misc-macro-parentheses misc-macro-repeated-side-effects misc-move-constructor-init @@ -76,6 +75,7 @@ modernize-use-default modernize-use-nullptr modernize-use-override + performance-inefficient-algorithm readability-braces-around-statements readability-container-size-empty readability-else-after-return Index: docs/clang-tidy/checks/misc-inefficient-algorithm.rst =================================================================== --- docs/clang-tidy/checks/misc-inefficient-algorithm.rst +++ docs/clang-tidy/checks/misc-inefficient-algorithm.rst @@ -1,11 +1,7 @@ -.. title:: clang-tidy - misc-inefficient-algorithm +:orphan: -misc-inefficient-algorithm -========================== +.. meta:: + :http-equiv=refresh: 5;URL=performance-inefficient-algorithm.html - -Warns on inefficient use of STL algorithms on associative containers. - -Associative containers implements some of the algorithms as methods which -should be preferred to the algorithms in the algorithm header. The methods -can take advanatage of the order of the elements. +The misc-inefficient-algorithm check was renamed, please see +`performance-inefficient-algorithm `_ for more information. Index: docs/clang-tidy/checks/performance-inefficient-algorithm.rst =================================================================== --- docs/clang-tidy/checks/performance-inefficient-algorithm.rst +++ docs/clang-tidy/checks/performance-inefficient-algorithm.rst @@ -1,6 +1,6 @@ -.. title:: clang-tidy - misc-inefficient-algorithm +.. title:: clang-tidy - performance-inefficient-algorithm -misc-inefficient-algorithm +performance-inefficient-algorithm ========================== Index: test/clang-tidy/misc-inefficient-algorithm.cpp =================================================================== --- test/clang-tidy/misc-inefficient-algorithm.cpp +++ test/clang-tidy/misc-inefficient-algorithm.cpp @@ -1,138 +0,0 @@ -// RUN: %check_clang_tidy %s misc-inefficient-algorithm %t - -namespace std { -template struct less { - bool operator()(const T &lhs, const T &rhs) { return lhs < rhs; } -}; - -template struct greater { - bool operator()(const T &lhs, const T &rhs) { return lhs > rhs; } -}; - -struct iterator_type {}; - -template > struct set { - typedef iterator_type iterator; - iterator find(const K &k); - unsigned count(const K &k); - - iterator begin(); - iterator end(); - iterator begin() const; - iterator end() const; -}; - -struct other_iterator_type {}; - -template > struct map { - typedef other_iterator_type iterator; - iterator find(const K &k); - unsigned count(const K &k); - - iterator begin(); - iterator end(); - iterator begin() const; - iterator end() const; -}; - -template struct unordered_set : set {}; - -template > struct multiset : set {}; - -template FwIt find(FwIt, FwIt, const K &); - -template -FwIt find(FwIt, FwIt, const K &, Cmp); - -template FwIt find_if(FwIt, FwIt, Pred); - -template FwIt count(FwIt, FwIt, const K &); - -template FwIt lower_bound(FwIt, FwIt, const K &); - -template -FwIt lower_bound(FwIt, FwIt, const K &, Ord); -} - -#define FIND_IN_SET(x) find(x.begin(), x.end(), 10) -// CHECK-FIXES: #define FIND_IN_SET(x) find(x.begin(), x.end(), 10) - -template void f(const T &t) { - std::set s; - find(s.begin(), s.end(), 46); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}s.find(46);{{$}} - - find(t.begin(), t.end(), 46); - // CHECK-FIXES: {{^ }}find(t.begin(), t.end(), 46);{{$}} -} - -int main() { - std::set s; - auto it = std::find(s.begin(), s.end(), 43); - // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: this STL algorithm call should be replaced with a container method [misc-inefficient-algorithm] - // CHECK-FIXES: {{^ }}auto it = s.find(43);{{$}} - auto c = count(s.begin(), s.end(), 43); - // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}auto c = s.count(43);{{$}} - -#define SECOND(x, y, z) y - SECOND(q,std::count(s.begin(), s.end(), 22),w); - // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}SECOND(q,s.count(22),w);{{$}} - - it = find_if(s.begin(), s.end(), [](int) { return false; }); - - std::multiset ms; - find(ms.begin(), ms.end(), 46); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}ms.find(46);{{$}} - - const std::multiset &msref = ms; - find(msref.begin(), msref.end(), 46); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}msref.find(46);{{$}} - - std::multiset *msptr = &ms; - find(msptr->begin(), msptr->end(), 46); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}msptr->find(46);{{$}} - - it = std::find(s.begin(), s.end(), 43, std::greater()); - // CHECK-MESSAGES: :[[@LINE-1]]:42: warning: different comparers used in the algorithm and the container [misc-inefficient-algorithm] - - FIND_IN_SET(s); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}FIND_IN_SET(s);{{$}} - - f(s); - - std::unordered_set us; - lower_bound(us.begin(), us.end(), 10); - // CHECK-FIXES: {{^ }}lower_bound(us.begin(), us.end(), 10);{{$}} - find(us.begin(), us.end(), 10); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}us.find(10);{{$}} - - std::map intmap; - find(intmap.begin(), intmap.end(), 46); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}find(intmap.begin(), intmap.end(), 46);{{$}} -} - -struct Value { - int value; -}; - -struct Ordering { - bool operator()(const Value &lhs, const Value &rhs) const { - return lhs.value < rhs.value; - } - bool operator()(int lhs, const Value &rhs) const { return lhs < rhs.value; } -}; - -void g(std::set container, int value) { - lower_bound(container.begin(), container.end(), value, Ordering()); - // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be - // CHECK-FIXES: {{^ }}lower_bound(container.begin(), container.end(), value, Ordering());{{$}} -} Index: test/clang-tidy/performance-inefficient-algorithm.cpp =================================================================== --- test/clang-tidy/performance-inefficient-algorithm.cpp +++ test/clang-tidy/performance-inefficient-algorithm.cpp @@ -1,4 +1,4 @@ -// RUN: %check_clang_tidy %s misc-inefficient-algorithm %t +// RUN: %check_clang_tidy %s performance-inefficient-algorithm %t namespace std { template struct less { @@ -70,7 +70,7 @@ int main() { std::set s; auto it = std::find(s.begin(), s.end(), 43); - // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: this STL algorithm call should be replaced with a container method [misc-inefficient-algorithm] + // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: this STL algorithm call should be replaced with a container method [performance-inefficient-algorithm] // CHECK-FIXES: {{^ }}auto it = s.find(43);{{$}} auto c = count(s.begin(), s.end(), 43); // CHECK-MESSAGES: :[[@LINE-1]]:12: warning: this STL algorithm call should be @@ -99,7 +99,7 @@ // CHECK-FIXES: {{^ }}msptr->find(46);{{$}} it = std::find(s.begin(), s.end(), 43, std::greater()); - // CHECK-MESSAGES: :[[@LINE-1]]:42: warning: different comparers used in the algorithm and the container [misc-inefficient-algorithm] + // CHECK-MESSAGES: :[[@LINE-1]]:42: warning: different comparers used in the algorithm and the container [performance-inefficient-algorithm] FIND_IN_SET(s); // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be