[clang-tidy] Move checks from misc- to performance-

Summary:
rename_check.py misc-move-constructor-init performance-move-constructor-init
rename_check.py misc-inefficient-algorithm performance-inefficient-algorithm

Reviewers: hokein, aaron.ballman

Reviewed By: hokein, aaron.ballman

Subscribers: aaron.ballman, mgorny, xazax.hun, cfe-commits

Differential Revision: https://reviews.llvm.org/D40487

llvm-svn: 319023

1 files changed, 163 insertions, 0 deletions

diff --git a/clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp b/clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp
new file mode 100644
index 0000000..4471d07
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp
@@ -0,0 +1,163 @@
+//===--- 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 performance {
+
+static bool areTypesCompatible(QualType Left, QualType Right) {
+  if (const auto *LeftRefType = Left->getAs<ReferenceType>())
+    Left = LeftRefType->getPointeeType();
+  if (const auto *RightRefType = Right->getAs<ReferenceType>())
+    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 auto Algorithms =
+      hasAnyName("::std::find", "::std::count", "::std::equal_range",
+                 "::std::lower_bound", "::std::upper_bound");
+  const auto ContainerMatcher = classTemplateSpecializationDecl(hasAnyName(
+      "::std::set", "::std::map", "::std::multiset", "::std::multimap",
+      "::std::unordered_set", "::std::unordered_map",
+      "::std::unordered_multiset", "::std::unordered_multimap"));
+
+  const auto Matcher =
+      callExpr(
+          callee(functionDecl(Algorithms)),
+          hasArgument(
+              0, cxxConstructExpr(has(ignoringParenImpCasts(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(ignoringParenImpCasts(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<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;
+  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<Expr>("AlgParam");
+  const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr");
+  FixItHint Hint;
+
+  SourceManager &SM = *Result.SourceManager;
+  LangOptions LangOpts = 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 performance
+} // namespace tidy
+} // namespace clang