Hi Alex,
Thank you for the review.I have removed the redundant checks you mentioned. I
did run it on the LLVM code base and did not found any match. I think there is
two reason: the code has exceptional quality and LLVM has it's own set of data
structures. I will apply for commit access :)
http://reviews.llvm.org/D7246
Files:
clang-tidy/misc/CMakeLists.txt
clang-tidy/misc/InefficientAlgorithmCheck.cpp
clang-tidy/misc/InefficientAlgorithmCheck.h
clang-tidy/misc/MiscTidyModule.cpp
test/clang-tidy/misc-inefficient-algorithm.cpp
EMAIL PREFERENCES
http://reviews.llvm.org/settings/panel/emailpreferences/
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.cpp
===================================================================
--- clang-tidy/misc/InefficientAlgorithmCheck.cpp
+++ 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
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/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<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>(
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,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);{{$}}
+}
_______________________________________________
cfe-commits mailing list
[email protected]
http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
