clang-tools  15.0.0git
InefficientVectorOperationCheck.cpp
Go to the documentation of this file.
1 //===--- InefficientVectorOperationCheck.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 "../utils/DeclRefExprUtils.h"
11 #include "../utils/OptionsUtils.h"
12 #include "clang/AST/ASTContext.h"
13 #include "clang/ASTMatchers/ASTMatchFinder.h"
14 #include "clang/Lex/Lexer.h"
15 
16 using namespace clang::ast_matchers;
17 
18 namespace clang {
19 namespace tidy {
20 namespace performance {
21 
22 namespace {
23 
24 // Matcher names. Given the code:
25 //
26 // \code
27 // void f() {
28 // vector<T> v;
29 // for (int i = 0; i < 10 + 1; ++i) {
30 // v.push_back(i);
31 // }
32 //
33 // SomeProto p;
34 // for (int i = 0; i < 10 + 1; ++i) {
35 // p.add_xxx(i);
36 // }
37 // }
38 // \endcode
39 //
40 // The matcher names are bound to following parts of the AST:
41 // - LoopCounterName: The entire for loop (as ForStmt).
42 // - LoopParentName: The body of function f (as CompoundStmt).
43 // - VectorVarDeclName: 'v' (as VarDecl).
44 // - VectorVarDeclStmatName: The entire 'std::vector<T> v;' statement (as
45 // DeclStmt).
46 // - PushBackOrEmplaceBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr).
47 // - LoopInitVarName: 'i' (as VarDecl).
48 // - LoopEndExpr: '10+1' (as Expr).
49 // If EnableProto, the proto related names are bound to the following parts:
50 // - ProtoVarDeclName: 'p' (as VarDecl).
51 // - ProtoVarDeclStmtName: The entire 'SomeProto p;' statement (as DeclStmt).
52 // - ProtoAddFieldCallName: 'p.add_xxx(i)' (as cxxMemberCallExpr).
53 static const char LoopCounterName[] = "for_loop_counter";
54 static const char LoopParentName[] = "loop_parent";
55 static const char VectorVarDeclName[] = "vector_var_decl";
56 static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt";
57 static const char PushBackOrEmplaceBackCallName[] = "append_call";
58 static const char ProtoVarDeclName[] = "proto_var_decl";
59 static const char ProtoVarDeclStmtName[] = "proto_var_decl_stmt";
60 static const char ProtoAddFieldCallName[] = "proto_add_field";
61 static const char LoopInitVarName[] = "loop_init_var";
62 static const char LoopEndExprName[] = "loop_end_expr";
63 static const char RangeLoopName[] = "for_range_loop";
64 
65 ast_matchers::internal::Matcher<Expr> supportedContainerTypesMatcher() {
66  return hasType(cxxRecordDecl(hasAnyName(
67  "::std::vector", "::std::set", "::std::unordered_set", "::std::map",
68  "::std::unordered_map", "::std::array", "::std::deque")));
69 }
70 
71 AST_MATCHER(Expr, hasSideEffects) {
72  return Node.HasSideEffects(Finder->getASTContext());
73 }
74 
75 } // namespace
76 
77 InefficientVectorOperationCheck::InefficientVectorOperationCheck(
78  StringRef Name, ClangTidyContext *Context)
79  : ClangTidyCheck(Name, Context),
80  VectorLikeClasses(utils::options::parseStringList(
81  Options.get("VectorLikeClasses", "::std::vector"))),
82  EnableProto(Options.getLocalOrGlobal("EnableProto", false)) {}
83 
86  Options.store(Opts, "VectorLikeClasses",
87  utils::options::serializeStringList(VectorLikeClasses));
88  Options.store(Opts, "EnableProto", EnableProto);
89 }
90 
91 void InefficientVectorOperationCheck::addMatcher(
92  const DeclarationMatcher &TargetRecordDecl, StringRef VarDeclName,
93  StringRef VarDeclStmtName, const DeclarationMatcher &AppendMethodDecl,
94  StringRef AppendCallName, MatchFinder *Finder) {
95  const auto DefaultConstructorCall = cxxConstructExpr(
96  hasType(TargetRecordDecl),
97  hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
98  const auto TargetVarDecl =
99  varDecl(hasInitializer(DefaultConstructorCall)).bind(VarDeclName);
100  const auto TargetVarDefStmt =
101  declStmt(hasSingleDecl(equalsBoundNode(std::string(VarDeclName))))
102  .bind(VarDeclStmtName);
103 
104  const auto AppendCallExpr =
105  cxxMemberCallExpr(
106  callee(AppendMethodDecl), on(hasType(TargetRecordDecl)),
107  onImplicitObjectArgument(declRefExpr(to(TargetVarDecl))))
108  .bind(AppendCallName);
109  const auto AppendCall = expr(ignoringImplicit(AppendCallExpr));
110  const auto LoopVarInit =
111  declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
112  .bind(LoopInitVarName)));
113  const auto RefersToLoopVar = ignoringParenImpCasts(
114  declRefExpr(to(varDecl(equalsBoundNode(LoopInitVarName)))));
115 
116  // Matchers for the loop whose body has only 1 push_back/emplace_back calling
117  // statement.
118  const auto HasInterestingLoopBody = hasBody(
119  anyOf(compoundStmt(statementCountIs(1), has(AppendCall)), AppendCall));
120  const auto InInterestingCompoundStmt =
121  hasParent(compoundStmt(has(TargetVarDefStmt)).bind(LoopParentName));
122 
123  // Match counter-based for loops:
124  // for (int i = 0; i < n; ++i) {
125  // v.push_back(...);
126  // // Or: proto.add_xxx(...);
127  // }
128  //
129  // FIXME: Support more types of counter-based loops like decrement loops.
130  Finder->addMatcher(
131  forStmt(
132  hasLoopInit(LoopVarInit),
133  hasCondition(binaryOperator(
134  hasOperatorName("<"), hasLHS(RefersToLoopVar),
135  hasRHS(expr(unless(hasDescendant(expr(RefersToLoopVar))))
136  .bind(LoopEndExprName)))),
137  hasIncrement(unaryOperator(hasOperatorName("++"),
138  hasUnaryOperand(RefersToLoopVar))),
139  HasInterestingLoopBody, InInterestingCompoundStmt)
140  .bind(LoopCounterName),
141  this);
142 
143  // Match for-range loops:
144  // for (const auto& E : data) {
145  // v.push_back(...);
146  // // Or: proto.add_xxx(...);
147  // }
148  //
149  // FIXME: Support more complex range-expressions.
150  Finder->addMatcher(
151  cxxForRangeStmt(
152  hasRangeInit(
153  anyOf(declRefExpr(supportedContainerTypesMatcher()),
154  memberExpr(hasObjectExpression(unless(hasSideEffects())),
155  supportedContainerTypesMatcher()))),
156  HasInterestingLoopBody, InInterestingCompoundStmt)
157  .bind(RangeLoopName),
158  this);
159 }
160 
162  const auto VectorDecl = cxxRecordDecl(hasAnyName(VectorLikeClasses));
163  const auto AppendMethodDecl =
164  cxxMethodDecl(hasAnyName("push_back", "emplace_back"));
165  addMatcher(VectorDecl, VectorVarDeclName, VectorVarDeclStmtName,
166  AppendMethodDecl, PushBackOrEmplaceBackCallName, Finder);
167 
168  if (EnableProto) {
169  const auto ProtoDecl =
170  cxxRecordDecl(isDerivedFrom("::proto2::MessageLite"));
171 
172  // A method's name starts with "add_" might not mean it's an add field
173  // call; it could be the getter for a proto field of which the name starts
174  // with "add_". So we exclude const methods.
175  const auto AddFieldMethodDecl =
176  cxxMethodDecl(matchesName("::add_"), unless(isConst()));
177  addMatcher(ProtoDecl, ProtoVarDeclName, ProtoVarDeclStmtName,
178  AddFieldMethodDecl, ProtoAddFieldCallName, Finder);
179  }
180 }
181 
183  const MatchFinder::MatchResult &Result) {
184  auto* Context = Result.Context;
185  if (Context->getDiagnostics().hasUncompilableErrorOccurred())
186  return;
187 
188  const SourceManager &SM = *Result.SourceManager;
189  const auto *VectorVarDecl =
190  Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName);
191  const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>(LoopCounterName);
192  const auto *RangeLoop =
193  Result.Nodes.getNodeAs<CXXForRangeStmt>(RangeLoopName);
194  const auto *VectorAppendCall =
195  Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackOrEmplaceBackCallName);
196  const auto *ProtoVarDecl = Result.Nodes.getNodeAs<VarDecl>(ProtoVarDeclName);
197  const auto *ProtoAddFieldCall =
198  Result.Nodes.getNodeAs<CXXMemberCallExpr>(ProtoAddFieldCallName);
199  const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);
200  const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);
201 
202  const CXXMemberCallExpr *AppendCall =
203  VectorAppendCall ? VectorAppendCall : ProtoAddFieldCall;
204  assert(AppendCall && "no append call expression");
205 
206  const Stmt *LoopStmt = ForLoop;
207  if (!LoopStmt)
208  LoopStmt = RangeLoop;
209 
210  const auto *TargetVarDecl = VectorVarDecl;
211  if (!TargetVarDecl)
212  TargetVarDecl = ProtoVarDecl;
213 
214  llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVarRefs =
215  utils::decl_ref_expr::allDeclRefExprs(*TargetVarDecl, *LoopParent,
216  *Context);
217  for (const auto *Ref : AllVarRefs) {
218  // Skip cases where there are usages (defined as DeclRefExpr that refers
219  // to "v") of vector variable / proto variable `v` before the for loop. We
220  // consider these usages are operations causing memory preallocation (e.g.
221  // "v.resize(n)", "v.reserve(n)").
222  //
223  // FIXME: make it more intelligent to identify the pre-allocating
224  // operations before the for loop.
225  if (SM.isBeforeInTranslationUnit(Ref->getLocation(),
226  LoopStmt->getBeginLoc())) {
227  return;
228  }
229  }
230 
231  std::string PartialReserveStmt;
232  if (VectorAppendCall != nullptr) {
233  PartialReserveStmt = ".reserve";
234  } else {
235  llvm::StringRef FieldName = ProtoAddFieldCall->getMethodDecl()->getName();
236  FieldName.consume_front("add_");
237  std::string MutableFieldName = ("mutable_" + FieldName).str();
238  PartialReserveStmt = "." + MutableFieldName +
239  "()->Reserve"; // e.g., ".mutable_xxx()->Reserve"
240  }
241 
242  llvm::StringRef VarName = Lexer::getSourceText(
243  CharSourceRange::getTokenRange(
244  AppendCall->getImplicitObjectArgument()->getSourceRange()),
245  SM, Context->getLangOpts());
246 
247  std::string ReserveSize;
248  // Handle for-range loop cases.
249  if (RangeLoop) {
250  // Get the range-expression in a for-range statement represented as
251  // `for (range-declarator: range-expression)`.
252  StringRef RangeInitExpName =
253  Lexer::getSourceText(CharSourceRange::getTokenRange(
254  RangeLoop->getRangeInit()->getSourceRange()),
255  SM, Context->getLangOpts());
256  ReserveSize = (RangeInitExpName + ".size()").str();
257  } else if (ForLoop) {
258  // Handle counter-based loop cases.
259  StringRef LoopEndSource = Lexer::getSourceText(
260  CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,
261  Context->getLangOpts());
262  ReserveSize = std::string(LoopEndSource);
263  }
264 
265  auto Diag = diag(AppendCall->getBeginLoc(),
266  "%0 is called inside a loop; consider pre-allocating the "
267  "container capacity before the loop")
268  << AppendCall->getMethodDecl()->getDeclName();
269  if (!ReserveSize.empty()) {
270  std::string ReserveStmt =
271  (VarName + PartialReserveStmt + "(" + ReserveSize + ");\n").str();
272  Diag << FixItHint::CreateInsertion(LoopStmt->getBeginLoc(), ReserveStmt);
273  }
274 }
275 
276 } // namespace performance
277 } // namespace tidy
278 } // namespace clang
clang::tidy::utils::decl_ref_expr::allDeclRefExprs
SmallPtrSet< const DeclRefExpr *, 16 > allDeclRefExprs(const VarDecl &VarDecl, const Stmt &Stmt, ASTContext &Context)
Returns set of all DeclRefExprs to VarDecl within Stmt.
Definition: DeclRefExprUtils.cpp:101
InefficientVectorOperationCheck.h
clang::tidy::ClangTidyOptions::OptionMap
llvm::StringMap< ClangTidyValue > OptionMap
Definition: ClangTidyOptions.h:115
clang::tidy::cppcoreguidelines::getSourceText
static std::string getSourceText(const CXXDestructorDecl &Destructor)
Definition: VirtualClassDestructorCheck.cpp:112
clang::tidy::ClangTidyCheck
Base class for all clang-tidy checks.
Definition: ClangTidyCheck.h:53
clang::tidy::performance::InefficientVectorOperationCheck::check
void check(const ast_matchers::MatchFinder::MatchResult &Result) override
ClangTidyChecks that register ASTMatchers should do the actual work in here.
Definition: InefficientVectorOperationCheck.cpp:182
clang::tidy::performance::InefficientVectorOperationCheck::registerMatchers
void registerMatchers(ast_matchers::MatchFinder *Finder) override
Override this to register AST matchers with Finder.
Definition: InefficientVectorOperationCheck.cpp:161
clang::ast_matchers
Definition: AbseilMatcher.h:14
clang::tidy::ClangTidyCheck::Options
OptionsView Options
Definition: ClangTidyCheck.h:415
clang::tidy::ClangTidyContext
Every ClangTidyCheck reports errors through a DiagnosticsEngine provided by this context.
Definition: ClangTidyDiagnosticConsumer.h:66
clang::tidy::ClangTidyCheck::diag
DiagnosticBuilder diag(SourceLocation Loc, StringRef Description, DiagnosticIDs::Level Level=DiagnosticIDs::Warning)
Add a diagnostic with the check's name.
Definition: ClangTidyCheck.cpp:25
Name
Token Name
Definition: MacroToEnumCheck.cpp:89
clang::ast_matchers::AST_MATCHER
AST_MATCHER(Expr, isMacroID)
Definition: PreferIsaOrDynCastInConditionalsCheck.cpp:19
clang::tidy::utils::options::serializeStringList
std::string serializeStringList(ArrayRef< StringRef > Strings)
Serialize a sequence of names that can be parsed by parseStringList.
Definition: OptionsUtils.cpp:62
clang
===– Representation.cpp - ClangDoc Representation --------—*- C++ -*-===//
Definition: ApplyReplacements.h:27
clang::tidy::utils::options::parseStringList
std::vector< StringRef > parseStringList(StringRef Option)
Parse a semicolon separated list of strings.
Definition: OptionsUtils.cpp:19
clang::tidy::ClangTidyCheck::OptionsView::store
void store(ClangTidyOptions::OptionMap &Options, StringRef LocalName, StringRef Value) const
Stores an option with the check-local name LocalName with string value Value to Options.
Definition: ClangTidyCheck.cpp:120
clang::tidy::performance::InefficientVectorOperationCheck::storeOptions
void storeOptions(ClangTidyOptions::OptionMap &Opts) override
Should store all options supported by this check with their current values or default values for opti...
Definition: InefficientVectorOperationCheck.cpp:84