diff options
Diffstat (limited to 'clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp')
| -rw-r--r-- | clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp | 163 |
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 |