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 
9 #include "InefficientVectorOperationCheck.h"
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 
supportedContainerTypesMatcher()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 
AST_MATCHER(Expr,hasSideEffects)71 AST_MATCHER(Expr, hasSideEffects) {
72   return Node.HasSideEffects(Finder->getASTContext());
73 }
74 
75 } // namespace
76 
InefficientVectorOperationCheck(StringRef Name,ClangTidyContext * Context)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 
storeOptions(ClangTidyOptions::OptionMap & Opts)84 void InefficientVectorOperationCheck::storeOptions(
85     ClangTidyOptions::OptionMap &Opts) {
86   Options.store(Opts, "VectorLikeClasses",
87                 utils::options::serializeStringList(VectorLikeClasses));
88   Options.store(Opts, "EnableProto", EnableProto);
89 }
90 
addMatcher(const DeclarationMatcher & TargetRecordDecl,StringRef VarDeclName,StringRef VarDeclStmtName,const DeclarationMatcher & AppendMethodDecl,StringRef AppendCallName,MatchFinder * Finder)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 
registerMatchers(MatchFinder * Finder)161 void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
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 
check(const MatchFinder::MatchResult & Result)182 void InefficientVectorOperationCheck::check(
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
279