[clang-tidy] Checker for inefficient use of algorithms on associative containers

[xazax.hun]

Summary

Associative containers implements some of the algorithms as methods which
should be preferred to the algorithms in the algorithm header. The methods
can take advantage of the order of the elements.

[alexfh]

clang-tidy/misc/InefficientAlgorithmCheck.cpp

25

What about unordered_(multi)?(set|map)?

38

Maybe something along the lines of on(equalsBoundNode("IneffContObj"))?

69

I'm not a native speaker, but the message seems a bit unclear. How about "different comparers used in the algorithm and the container"?

Also, please remove the trailing period.

83

A Twine can be used here instead.

97

Please remove the trailing period.

[xazax.hun]

Thanks for the review.

• I have added support for unordered containers. There is no comparator check for the unordered containers and there is no lower or upper bound member functions. Code to deal with these cases was added.
• I made the matcher more strict with equalBoundNodes as you suggested.
• The warning messages was modified as you requested. Unfortunately I do not have a native speaker coworker to check these messages.
• Replaced the string concatenations with twine operations.

[alexfh]

One nit, otherwise looks good. Please address the issue and I can commit the patch for you.

BTW, I think that it makes sense for you to apply for a commit access (http://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access).

Also, could you run the check on LLVM/Clang to see whether it finds something?

clang-tidy/misc/InefficientAlgorithmCheck.cpp

43

Do you need to check this in addition to the equalsBoundNode above?

[xazax.hun]

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 :)

[alexfh]

Looks good!

Thank you for the contribution!

[alexfh]

clang-tidy/misc/InefficientAlgorithmCheck.cpp

22

This turns out to match std::count_if/std::find_if as well. Could you surround the regex with ^$ and add a test? Same applies to the ContainerMatcher below.

[xazax.hun]

Thank you for pointing this issue out. It should be fixed in r228945.

[alexfh]

Thanks!

[alexfh]

I found two more issues with this check:

1. the fixes for map-like containers are wrong. The .begin() and .end() allow to iterate over values of the map, and .find() accepts a key. I don't know if there is a good fix for all cases where std::find-like algorithms are used on a map. Maybe just leave a warning without a fix?
2. the check can produce incompilable fixes if an algorithm receives a value of a different type than the type of the container's elements. See http://pastebin.com/5pkMLrZb for an example.

Would be nice if you could fix the issues.

Thanks!

[xazax.hun]

Thank you for the feedback. I think I should have seen the first problem in advance. I find the second one more subtle. Both should be fixed in r229552. I am not absolutely happy with the solution: checking for type equality modulo references. It would be better to check if appropriate type conversions exists, but I did not find a nice way to do it. What is your opinion?

[alexfh]

In D7246#124990, @xazax.hun wrote:

Thank you for the feedback. I think I should have seen the first problem in advance. I find the second one more subtle. Both should be fixed in r229552. I am not absolutely happy with the solution: checking for type equality modulo references. It would be better to check if appropriate type conversions exists, but I did not find a nice way to do it. What is your opinion?

I don't know if a better solution exists. The fix looks fine. Thanks!

clang-tidy/misc/CMakeLists.txt

 add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   BoolPointerImplicitConversion.cpp
+  InefficientAlgorithmCheck.cpp
   MiscTidyModule.cpp
   SwappedArgumentsCheck.cpp
   UndelegatedConstructor.cpp

clang-tidy/misc/InefficientAlgorithmCheck.h

+//===--- 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

clang-tidy/misc/InefficientAlgorithmCheck.cpp

+//===--- 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

clang-tidy/misc/MiscTidyModule.cpp

 #include "../ClangTidyModuleRegistry.h"
 #include "ArgumentCommentCheck.h"
 #include "BoolPointerImplicitConversion.h"
+#include "InefficientAlgorithmCheck.h"
 #include "SwappedArgumentsCheck.h"
 #include "UndelegatedConstructor.h"
 #include "UniqueptrResetRelease.h"

     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>(

test/clang-tidy/misc-inefficient-algorithm.cpp

+// 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);{{$}}
+}