clang-tools  16.0.0git
InefficientAlgorithmCheck.cpp
Go to the documentation of this file.
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 
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, 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, cxxMemberCallExpr(callee(cxxMethodDecl(hasName("end"))),
52  on(declRefExpr(hasDeclaration(
53  equalsBoundNode("IneffContObj")))))),
54  hasArgument(2, expr().bind("AlgParam")))
55  .bind("IneffAlg");
56 
57  Finder->addMatcher(Matcher, this);
58 }
59 
60 void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) {
61  const auto *AlgCall = Result.Nodes.getNodeAs<CallExpr>("IneffAlg");
62  const auto *IneffCont =
63  Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffCont");
64  bool PtrToContainer = false;
65  if (!IneffCont) {
66  IneffCont =
67  Result.Nodes.getNodeAs<ClassTemplateSpecializationDecl>("IneffContPtr");
68  PtrToContainer = true;
69  }
70  const llvm::StringRef IneffContName = IneffCont->getName();
71  const bool Unordered = IneffContName.contains("unordered");
72  const bool Maplike = IneffContName.contains("map");
73 
74  // Store if the key type of the container is compatible with the value
75  // that is searched for.
76  QualType ValueType = AlgCall->getArg(2)->getType();
77  QualType KeyType =
78  IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType();
79  const bool CompatibleTypes = areTypesCompatible(KeyType, ValueType);
80 
81  // Check if the comparison type for the algorithm and the container matches.
82  if (AlgCall->getNumArgs() == 4 && !Unordered) {
83  const Expr *Arg = AlgCall->getArg(3);
84  const QualType AlgCmp =
85  Arg->getType().getUnqualifiedType().getCanonicalType();
86  const unsigned CmpPosition = IneffContName.contains("map") ? 2 : 1;
87  const QualType ContainerCmp = IneffCont->getTemplateArgs()[CmpPosition]
88  .getAsType()
89  .getUnqualifiedType()
90  .getCanonicalType();
91  if (AlgCmp != ContainerCmp) {
92  diag(Arg->getBeginLoc(),
93  "different comparers used in the algorithm and the container");
94  return;
95  }
96  }
97 
98  const auto *AlgDecl = AlgCall->getDirectCallee();
99  if (!AlgDecl)
100  return;
101 
102  if (Unordered && AlgDecl->getName().find("bound") != llvm::StringRef::npos)
103  return;
104 
105  const auto *AlgParam = Result.Nodes.getNodeAs<Expr>("AlgParam");
106  const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr");
107  FixItHint Hint;
108 
109  SourceManager &SM = *Result.SourceManager;
110  LangOptions LangOpts = getLangOpts();
111 
112  CharSourceRange CallRange =
113  CharSourceRange::getTokenRange(AlgCall->getSourceRange());
114 
115  // FIXME: Create a common utility to extract a file range that the given token
116  // sequence is exactly spelled at (without macro argument expansions etc.).
117  // We can't use Lexer::makeFileCharRange here, because for
118  //
119  // #define F(x) x
120  // x(a b c);
121  //
122  // it will return "x(a b c)", when given the range "a"-"c". It makes sense for
123  // removals, but not for replacements.
124  //
125  // This code is over-simplified, but works for many real cases.
126  if (SM.isMacroArgExpansion(CallRange.getBegin()) &&
127  SM.isMacroArgExpansion(CallRange.getEnd())) {
128  CallRange.setBegin(SM.getSpellingLoc(CallRange.getBegin()));
129  CallRange.setEnd(SM.getSpellingLoc(CallRange.getEnd()));
130  }
131 
132  if (!CallRange.getBegin().isMacroID() && !Maplike && CompatibleTypes) {
133  StringRef ContainerText = Lexer::getSourceText(
134  CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), SM,
135  LangOpts);
136  StringRef ParamText = Lexer::getSourceText(
137  CharSourceRange::getTokenRange(AlgParam->getSourceRange()), SM,
138  LangOpts);
139  std::string ReplacementText =
140  (llvm::Twine(ContainerText) + (PtrToContainer ? "->" : ".") +
141  AlgDecl->getName() + "(" + ParamText + ")")
142  .str();
143  Hint = FixItHint::CreateReplacement(CallRange, ReplacementText);
144  }
145 
146  diag(AlgCall->getBeginLoc(),
147  "this STL algorithm call should be replaced with a container method")
148  << Hint;
149 }
150 
151 } // namespace performance
152 } // namespace tidy
153 } // namespace clang
clang::tidy::cppcoreguidelines::getSourceText
static std::string getSourceText(const CXXDestructorDecl &Destructor)
Definition: VirtualClassDestructorCheck.cpp:115
clang::ast_matchers
Definition: AbseilMatcher.h:14
InefficientAlgorithmCheck.h
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::clangd::check
bool check(llvm::StringRef File, const ThreadsafeFS &TFS, const ClangdLSPServer::Options &Opts)
Definition: Check.cpp:415
LangOpts
const LangOptions * LangOpts
Definition: ExtractFunction.cpp:375
clang::tidy::performance::areTypesCompatible
static bool areTypesCompatible(QualType Left, QualType Right)
Definition: InefficientAlgorithmCheck.cpp:20