clang-tools-extra/clang-tidy/performance/InefficientAlgorithmCheck.cpp

   1 //===--- InefficientAlgorithmCheck.cpp - clang-tidy------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "InefficientAlgorithmCheck.h"
  10 #include "clang/AST/ASTContext.h"
  11 #include "clang/ASTMatchers/ASTMatchFinder.h"
  12 #include "clang/Lex/Lexer.h"
  13
  14 using namespace clang::ast_matchers;
  15
  16 namespace clang::tidy::performance {
  17
  18 static bool areTypesCompatible(QualType Left, QualType Right) {
  19   if (const auto *LeftRefType = Left->getAs<ReferenceType>())
  20     Left = LeftRefType->getPointeeType();
  21   if (const auto *RightRefType = Right->getAs<ReferenceType>())
  22     Right = RightRefType->getPointeeType();
  23   return Left->getCanonicalTypeUnqualified() ==
  24          Right->getCanonicalTypeUnqualified();
  25 }
  26
  27 void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) {
  28   const auto Algorithms =
  29       hasAnyName("::std::find", "::std::count", "::std::equal_range",
  30                  "::std::lower_bound", "::std::upper_bound");
  31   const auto ContainerMatcher = classTemplateSpecializationDecl(hasAnyName(
  32       "::std::set", "::std::map", "::std::multiset", "::std::multimap",
  33       "::std::unordered_set", "::std::unordered_map",
  34       "::std::unordered_multiset", "::std::unordered_multimap"));
  35
  36   const auto Matcher =
  37       callExpr(
  38           callee(functionDecl(Algorithms)),
  39           hasArgument(
  40               0, cxxMemberCallExpr(
  41                      callee(cxxMethodDecl(hasName("begin"))),
  42                      on(declRefExpr(
  43                             hasDeclaration(decl().bind("IneffContObj")),
  44                             anyOf(hasType(ContainerMatcher.bind("IneffCont")),
  45                                   hasType(pointsTo(
  46                                       ContainerMatcher.bind("IneffContPtr")))))
  47                             .bind("IneffContExpr")))),
  48           hasArgument(
  49               1, cxxMemberCallExpr(callee(cxxMethodDecl(hasName("end"))),
  50                                    on(declRefExpr(hasDeclaration(
  51                                        equalsBoundNode("IneffContObj")))))),
  52           hasArgument(2, expr().bind("AlgParam")))
  53           .bind("IneffAlg");
  54
  55   Finder->addMatcher(Matcher, this);
  56 }
  57
  58 void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) {
  59   const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>("IneffAlg");
  60   const auto *IneffCont =
  61       Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffCont");
  62   bool PtrToContainer = false;
  63   if (!IneffCont) {
  64     IneffCont =
  65         Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffContPtr");
  66     PtrToContainer = true;
  67   }
  68   const llvm::StringRef IneffContName = IneffCont->getName();
  69   const bool Unordered = IneffContName.contains("unordered");
  70   const bool Maplike = IneffContName.contains("map");
  71
  72   // Store if the key type of the container is compatible with the value
  73   // that is searched for.
  74   QualType ValueType = AlgCall->getArg(2)->getType();
  75   QualType KeyType =
  76       IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType();
  77   const bool CompatibleTypes = areTypesCompatible(KeyType, ValueType);
  78
  79   // Check if the comparison type for the algorithm and the container matches.
  80   if (AlgCall->getNumArgs() == 4 && !Unordered) {
  81     const Expr *Arg = AlgCall->getArg(3);
  82     const QualType AlgCmp =
  83         Arg->getType().getUnqualifiedType().getCanonicalType();
  84     const unsigned CmpPosition = IneffContName.contains("map") ? 2 : 1;
  85     const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition]
  86                                       .getAsType()
  87                                       .getUnqualifiedType()
  88                                       .getCanonicalType();
  89     if (AlgCmp != ContainerCmp) {
  90       diag(Arg->getBeginLoc(),
  91            "different comparers used in the algorithm and the container");
  92       return;
  93     }
  94   }
  95
  96   const auto *AlgDecl = AlgCall->getDirectCallee();
  97   if (!AlgDecl)
  98     return;
  99
 100   if (Unordered && AlgDecl->getName().contains("bound"))
 101     return;
 102
 103   const auto *AlgParam = Result.Nodes.getNodeAs<Expr>("AlgParam");
 104   const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr");
 105   FixItHint Hint;
 106
 107   SourceManager &SM = *Result.SourceManager;
 108   LangOptions LangOpts = getLangOpts();
 109
 110   CharSourceRange CallRange =
 111       CharSourceRange::getTokenRange(AlgCall->getSourceRange());
 112
 113   // FIXME: Create a common utility to extract a file range that the given token
 114   // sequence is exactly spelled at (without macro argument expansions etc.).
 115   // We can't use Lexer::makeFileCharRange here, because for
 116   //
 117   //   #define F(x) x
 118   //   x(a b c);
 119   //
 120   // it will return "x(a b c)", when given the range "a"-"c". It makes sense for
 121   // removals, but not for replacements.
 122   //
 123   // This code is over-simplified, but works for many real cases.
 124   if (SM.isMacroArgExpansion(CallRange.getBegin()) &&
 125       SM.isMacroArgExpansion(CallRange.getEnd())) {
 126     CallRange.setBegin(SM.getSpellingLoc(CallRange.getBegin()));
 127     CallRange.setEnd(SM.getSpellingLoc(CallRange.getEnd()));
 128   }
 129
 130   if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) {
 131     StringRef ContainerText = Lexer::getSourceText(
 132         CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM,
 133         LangOpts);
 134     StringRef ParamText = Lexer::getSourceText(
 135         CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM,
 136         LangOpts);
 137     std::string ReplacementText =
 138         (llvm::Twine(ContainerText) + (PtrToContainer ? "->" : ".") +
 139          AlgDecl->getName() + "(" + ParamText + ")")
 140             .str();
 141     Hint = FixItHint::CreateReplacement(CallRange, ReplacementText);
 142   }
 143
 144   diag(AlgCall->getBeginLoc(),
 145        "this STL algorithm call should be replaced with a container method")
 146       << Hint;
 147 }
 148
 149 } // namespace clang::tidy::performance