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