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