Index: clang-tidy/misc/CMakeLists.txt =================================================================== --- clang-tidy/misc/CMakeLists.txt +++ clang-tidy/misc/CMakeLists.txt @@ -3,6 +3,7 @@ add_clang_library(clangTidyMiscModule ArgumentCommentCheck.cpp BoolPointerImplicitConversion.cpp + InefficientAlgorithmCheck.cpp MiscTidyModule.cpp SwappedArgumentsCheck.cpp UndelegatedConstructor.cpp Index: clang-tidy/misc/InefficientAlgorithmCheck.h =================================================================== --- clang-tidy/misc/InefficientAlgorithmCheck.h +++ clang-tidy/misc/InefficientAlgorithmCheck.h @@ -0,0 +1,34 @@ +//===--- 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_INEFFICIENT_ALGORITHM_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENT_ALGORITHM_H + +#include "../ClangTidy.h" + +namespace clang { +namespace tidy { + +/// \brief 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 tidy +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_INEFFICIENT_ALGORITHM_H Index: clang-tidy/misc/InefficientAlgorithmCheck.cpp =================================================================== --- clang-tidy/misc/InefficientAlgorithmCheck.cpp +++ clang-tidy/misc/InefficientAlgorithmCheck.cpp @@ -0,0 +1,101 @@ +//===--- 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 { + +void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) { + const std::string Algorithms = + "std::(find|count|equal_range|lower_blound|upper_bound)"; + const auto ContainerMatcher = classTemplateSpecializationDecl( + matchesName("std::(set|multiset|map|multimap)")); + const auto Matcher = + callExpr( + callee(functionDecl(matchesName(Algorithms))), + hasArgument( + 0, constructExpr(has(memberCallExpr( + callee(methodDecl(hasName("begin"))), + on(expr(anyOf(hasType(ContainerMatcher.bind("IneffCont")), + hasType(pointsTo( + ContainerMatcher.bind("IneffContPtr"))))) + .bind("IneffContObj")))))), + hasArgument(1, constructExpr(has(memberCallExpr( + callee(methodDecl(hasName("end"))), + on(anyOf(hasType(ContainerMatcher), + hasType(pointsTo(ContainerMatcher)))))))), + 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; + } + + // Check if the comparison type for the algorithm and the container matches. + if (AlgCall->getNumArgs() == 4) { + const Expr *Arg = AlgCall->getArg(3); + const QualType AlgCmp = + Arg->getType().getUnqualifiedType().getCanonicalType(); + const unsigned CmpPosition = + (IneffCont->getName().find("map") == llvm::StringRef::npos) ? 1 : 2; + const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition] + .getAsType() + .getUnqualifiedType() + .getCanonicalType(); + if (AlgCmp != ContainerCmp) { + diag(Arg->getLocStart(), "incompatible compare with the container."); + return; + } + } + + const auto *AlgDecl = AlgCall->getDirectCallee(); + if (!AlgDecl) + return; + + const auto *AlgParam = Result.Nodes.getNodeAs("AlgParam"); + const auto *IneffContObj = Result.Nodes.getNodeAs("IneffContObj"); + FixItHint Hint; + + if (!AlgCall->getLocStart().isMacroID()) { + std::string ReplacementText = Lexer::getSourceText( + CharSourceRange::getTokenRange(IneffContObj->getSourceRange()), + *Result.SourceManager, Result.Context->getLangOpts()); + ReplacementText += PtrToContainer ? "->" : "."; + ReplacementText += AlgDecl->getName().str() + "("; + ReplacementText += Lexer::getSourceText( + CharSourceRange::getTokenRange(AlgParam->getSourceRange()), + *Result.SourceManager, Result.Context->getLangOpts()); + ReplacementText += ")"; + Hint = FixItHint::CreateReplacement(AlgCall->getSourceRange(), + ReplacementText); + } + + diag(AlgCall->getLocStart(), + "this STL algorithm call should be replaced with a container method.") + << Hint; +} + +} // namespace tidy +} // namespace clang Index: clang-tidy/misc/MiscTidyModule.cpp =================================================================== --- clang-tidy/misc/MiscTidyModule.cpp +++ clang-tidy/misc/MiscTidyModule.cpp @@ -12,6 +12,7 @@ #include "../ClangTidyModuleRegistry.h" #include "ArgumentCommentCheck.h" #include "BoolPointerImplicitConversion.h" +#include "InefficientAlgorithmCheck.h" #include "SwappedArgumentsCheck.h" #include "UndelegatedConstructor.h" #include "UniqueptrResetRelease.h" @@ -27,6 +28,8 @@ CheckFactories.registerCheck("misc-argument-comment"); CheckFactories.registerCheck( "misc-bool-pointer-implicit-conversion"); + CheckFactories.registerCheck( + "misc-inefficient-algorithm"); CheckFactories.registerCheck( "misc-swapped-arguments"); CheckFactories.registerCheck( Index: test/clang-tidy/misc-inefficient-algorithm.cpp =================================================================== --- test/clang-tidy/misc-inefficient-algorithm.cpp +++ test/clang-tidy/misc-inefficient-algorithm.cpp @@ -0,0 +1,81 @@ +// RUN: $(dirname %s)/check_clang_tidy.sh %s misc-inefficient-algorithm %t +// REQUIRES: shell + +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; +}; + +template > struct multiset : set {}; + +template FwIt find(FwIt, FwIt, const K &); + +template +FwIt find(FwIt, FwIt, const K &, Cmp); + +template FwIt count(FwIt, FwIt, const K &); +} + +#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);{{$}} + + 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: incompatible compare with 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); +}