diff options
5 files changed, 240 insertions, 0 deletions
diff --git a/clang-tools-extra/clang-tidy/misc/CMakeLists.txt b/clang-tools-extra/clang-tidy/misc/CMakeLists.txt index f9da3a6b9a1..500a6dbed8a 100644 --- a/clang-tools-extra/clang-tidy/misc/CMakeLists.txt +++ b/clang-tools-extra/clang-tidy/misc/CMakeLists.txt @@ -3,6 +3,7 @@ set(LLVM_LINK_COMPONENTS support) add_clang_library(clangTidyMiscModule ArgumentCommentCheck.cpp BoolPointerImplicitConversion.cpp + InefficientAlgorithmCheck.cpp MiscTidyModule.cpp SwappedArgumentsCheck.cpp UndelegatedConstructor.cpp diff --git a/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp b/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp new file mode 100644 index 00000000000..763d3765e0b --- /dev/null +++ b/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp @@ -0,0 +1,110 @@ +//===--- 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::(unordered_)?(multi)?(set|map)")); + const auto Matcher = + callExpr( + callee(functionDecl(matchesName(Algorithms))), + hasArgument( + 0, constructExpr(has(memberCallExpr( + callee(methodDecl(hasName("begin"))), + on(declRefExpr( + hasDeclaration(decl().bind("IneffContObj")), + anyOf(hasType(ContainerMatcher.bind("IneffCont")), + hasType(pointsTo( + ContainerMatcher.bind("IneffContPtr"))))) + .bind("IneffContExpr")))))), + hasArgument(1, constructExpr(has(memberCallExpr( + callee(methodDecl(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<CallExpr>("IneffAlg"); + const auto *IneffCont = + Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffCont"); + bool PtrToContainer = false; + if (!IneffCont) { + IneffCont = + Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffContPtr"); + PtrToContainer = true; + } + const llvm::StringRef IneffContName = IneffCont->getName(); + const bool Unordered = + IneffContName.find("unordered") != llvm::StringRef::npos; + + // 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<Expr>("AlgParam"); + const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr"); + FixItHint Hint; + + if (!AlgCall->getLocStart().isMacroID()) { + std::string ReplacementText = + (llvm::Twine(Lexer::getSourceText( + CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), + *Result.SourceManager, Result.Context->getLangOpts())) + + (PtrToContainer ? "->" : ".") + AlgDecl->getName() + "(" + + Lexer::getSourceText( + CharSourceRange::getTokenRange(AlgParam->getSourceRange()), + *Result.SourceManager, Result.Context->getLangOpts()) + + ")").str(); + 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 diff --git a/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.h b/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.h new file mode 100644 index 00000000000..f55297f0378 --- /dev/null +++ b/clang-tools-extra/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 diff --git a/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp b/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp index fe56017247b..f28140da67c 100644 --- a/clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp +++ b/clang-tools-extra/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 @@ public: CheckFactories.registerCheck<ArgumentCommentCheck>("misc-argument-comment"); CheckFactories.registerCheck<BoolPointerImplicitConversion>( "misc-bool-pointer-implicit-conversion"); + CheckFactories.registerCheck<InefficientAlgorithmCheck>( + "misc-inefficient-algorithm"); CheckFactories.registerCheck<SwappedArgumentsCheck>( "misc-swapped-arguments"); CheckFactories.registerCheck<UndelegatedConstructorCheck>( diff --git a/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp b/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp new file mode 100644 index 00000000000..46a5b2a9456 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp @@ -0,0 +1,92 @@ +// RUN: $(dirname %s)/check_clang_tidy.sh %s misc-inefficient-algorithm %t +// REQUIRES: shell + +namespace std { +template <typename T> struct less { + bool operator()(const T &lhs, const T &rhs) { return lhs < rhs; } +}; + +template <typename T> struct greater { + bool operator()(const T &lhs, const T &rhs) { return lhs > rhs; } +}; + +struct iterator_type {}; + +template <typename K, typename Cmp = less<K>> 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 <typename K> struct unordered_set : set<K> {}; + +template <typename K, typename Cmp = less<K>> struct multiset : set<K, Cmp> {}; + +template <typename FwIt, typename K> FwIt find(FwIt, FwIt, const K &); + +template <typename FwIt, typename K, typename Cmp> +FwIt find(FwIt, FwIt, const K &, Cmp); + +template <typename FwIt, typename K> FwIt count(FwIt, FwIt, const K &); + +template <typename FwIt, typename K> FwIt lower_bound(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 <typename T> void f(const T &t) { + std::set<int> 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<int> 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<int> 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<int> &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<int> *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<int>()); + // 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<int> 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);{{$}} +} |
