1 //===--- InefficientVectorOperationCheck.cpp - clang-tidy------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "InefficientVectorOperationCheck.h"
11 #include "clang/AST/ASTContext.h"
12 #include "clang/ASTMatchers/ASTMatchFinder.h"
13 #include "clang/Lex/Lexer.h"
14 #include "../utils/DeclRefExprUtils.h"
15 #include "../utils/OptionsUtils.h"
16 
17 using namespace clang::ast_matchers;
18 
19 namespace clang {
20 namespace tidy {
21 namespace performance {
22 
23 namespace {
24 
25 // Matcher names. Given the code:
26 //
27 // \code
28 // void f() {
29 //   vector<T> v;
30 //   for (int i = 0; i < 10 + 1; ++i) {
31 //     v.push_back(i);
32 //   }
33 // }
34 // \endcode
35 //
36 // The matcher names are bound to following parts of the AST:
37 //   - LoopCounterName: The entire for loop (as ForStmt).
38 //   - LoopParentName: The body of function f (as CompoundStmt).
39 //   - VectorVarDeclName: 'v' in  (as VarDecl).
40 //   - VectorVarDeclStmatName: The entire 'std::vector<T> v;' statement (as
41 //     DeclStmt).
42 //   - PushBackOrEmplaceBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr).
43 //   - LoopInitVarName: 'i' (as VarDecl).
44 //   - LoopEndExpr: '10+1' (as Expr).
45 static const char LoopCounterName[] = "for_loop_counter";
46 static const char LoopParentName[] = "loop_parent";
47 static const char VectorVarDeclName[] = "vector_var_decl";
48 static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt";
49 static const char PushBackOrEmplaceBackCallName[] = "append_call";
50 static const char LoopInitVarName[] = "loop_init_var";
51 static const char LoopEndExprName[] = "loop_end_expr";
52 
53 static const char RangeLoopName[] = "for_range_loop";
54 
55 ast_matchers::internal::Matcher<Expr> supportedContainerTypesMatcher() {
56   return hasType(cxxRecordDecl(hasAnyName(
57       "::std::vector", "::std::set", "::std::unordered_set", "::std::map",
58       "::std::unordered_map", "::std::array", "::std::deque")));
59 }
60 
61 } // namespace
62 
63 InefficientVectorOperationCheck::InefficientVectorOperationCheck(
64     StringRef Name, ClangTidyContext *Context)
65     : ClangTidyCheck(Name, Context),
66       VectorLikeClasses(utils::options::parseStringList(
67           Options.get("VectorLikeClasses", "::std::vector"))) {}
68 
69 void InefficientVectorOperationCheck::storeOptions(
70     ClangTidyOptions::OptionMap &Opts) {
71   Options.store(Opts, "VectorLikeClasses",
72                 utils::options::serializeStringList(VectorLikeClasses));
73 }
74 
75 void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
76   const auto VectorDecl = cxxRecordDecl(hasAnyName(SmallVector<StringRef, 5>(
77       VectorLikeClasses.begin(), VectorLikeClasses.end())));
78   const auto VectorDefaultConstructorCall = cxxConstructExpr(
79       hasType(VectorDecl),
80       hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
81   const auto VectorVarDecl =
82       varDecl(hasInitializer(VectorDefaultConstructorCall))
83           .bind(VectorVarDeclName);
84   const auto VectorAppendCallExpr =
85       cxxMemberCallExpr(
86           callee(cxxMethodDecl(hasAnyName("push_back", "emplace_back"))),
87           on(hasType(VectorDecl)),
88           onImplicitObjectArgument(declRefExpr(to(VectorVarDecl))))
89           .bind(PushBackOrEmplaceBackCallName);
90   const auto VectorAppendCall = expr(ignoringImplicit(VectorAppendCallExpr));
91   const auto VectorVarDefStmt =
92       declStmt(hasSingleDecl(equalsBoundNode(VectorVarDeclName)))
93           .bind(VectorVarDeclStmtName);
94 
95   const auto LoopVarInit =
96       declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
97                                  .bind(LoopInitVarName)));
98   const auto RefersToLoopVar = ignoringParenImpCasts(
99       declRefExpr(to(varDecl(equalsBoundNode(LoopInitVarName)))));
100 
101   // Matchers for the loop whose body has only 1 push_back/emplace_back calling
102   // statement.
103   const auto HasInterestingLoopBody =
104       hasBody(anyOf(compoundStmt(statementCountIs(1), has(VectorAppendCall)),
105                     VectorAppendCall));
106   const auto InInterestingCompoundStmt =
107       hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName));
108 
109   // Match counter-based for loops:
110   //  for (int i = 0; i < n; ++i) { v.push_back(...); }
111   //
112   // FIXME: Support more types of counter-based loops like decrement loops.
113   Finder->addMatcher(
114       forStmt(
115           hasLoopInit(LoopVarInit),
116           hasCondition(binaryOperator(
117               hasOperatorName("<"), hasLHS(RefersToLoopVar),
118               hasRHS(expr(unless(hasDescendant(expr(RefersToLoopVar))))
119                          .bind(LoopEndExprName)))),
120           hasIncrement(unaryOperator(hasOperatorName("++"),
121                                      hasUnaryOperand(RefersToLoopVar))),
122           HasInterestingLoopBody, InInterestingCompoundStmt)
123           .bind(LoopCounterName),
124       this);
125 
126   // Match for-range loops:
127   //   for (const auto& E : data) { v.push_back(...); }
128   //
129   // FIXME: Support more complex range-expressions.
130   Finder->addMatcher(
131       cxxForRangeStmt(
132           hasRangeInit(declRefExpr(supportedContainerTypesMatcher())),
133           HasInterestingLoopBody, InInterestingCompoundStmt)
134           .bind(RangeLoopName),
135       this);
136 }
137 
138 void InefficientVectorOperationCheck::check(
139     const MatchFinder::MatchResult &Result) {
140   auto* Context = Result.Context;
141   if (Context->getDiagnostics().hasUncompilableErrorOccurred())
142     return;
143 
144   const SourceManager &SM = *Result.SourceManager;
145   const auto *VectorVarDecl =
146       Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName);
147   const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>(LoopCounterName);
148   const auto *RangeLoop =
149       Result.Nodes.getNodeAs<CXXForRangeStmt>(RangeLoopName);
150   const auto *VectorAppendCall =
151       Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackOrEmplaceBackCallName);
152   const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);
153   const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);
154 
155   const Stmt *LoopStmt = ForLoop;
156   if (!LoopStmt)
157     LoopStmt = RangeLoop;
158 
159   llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVectorVarRefs =
160       utils::decl_ref_expr::allDeclRefExprs(*VectorVarDecl, *LoopParent,
161                                             *Context);
162   for (const auto *Ref : AllVectorVarRefs) {
163     // Skip cases where there are usages (defined as DeclRefExpr that refers to
164     // "v") of vector variable `v` before the for loop. We consider these usages
165     // are operations causing memory preallocation (e.g. "v.resize(n)",
166     // "v.reserve(n)").
167     //
168     // FIXME: make it more intelligent to identify the pre-allocating operations
169     // before the for loop.
170     if (SM.isBeforeInTranslationUnit(Ref->getLocation(),
171                                      LoopStmt->getLocStart())) {
172       return;
173     }
174   }
175 
176   llvm::StringRef VectorVarName = Lexer::getSourceText(
177       CharSourceRange::getTokenRange(
178           VectorAppendCall->getImplicitObjectArgument()->getSourceRange()),
179       SM, Context->getLangOpts());
180 
181   std::string ReserveStmt;
182   // Handle for-range loop cases.
183   if (RangeLoop) {
184     // Get the range-expression in a for-range statement represented as
185     // `for (range-declarator: range-expression)`.
186     StringRef RangeInitExpName = Lexer::getSourceText(
187         CharSourceRange::getTokenRange(
188             RangeLoop->getRangeInit()->getSourceRange()),
189         SM, Context->getLangOpts());
190 
191     ReserveStmt =
192         (VectorVarName + ".reserve(" + RangeInitExpName + ".size()" + ");\n")
193             .str();
194   } else if (ForLoop) {
195     // Handle counter-based loop cases.
196     StringRef LoopEndSource = Lexer::getSourceText(
197         CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,
198         Context->getLangOpts());
199     ReserveStmt = (VectorVarName + ".reserve(" + LoopEndSource + ");\n").str();
200   }
201 
202   auto Diag =
203       diag(VectorAppendCall->getLocStart(),
204            "%0 is called inside a loop; "
205            "consider pre-allocating the vector capacity before the loop")
206       << VectorAppendCall->getMethodDecl()->getDeclName();
207 
208   if (!ReserveStmt.empty())
209     Diag << FixItHint::CreateInsertion(LoopStmt->getLocStart(), ReserveStmt);
210 }
211 
212 } // namespace performance
213 } // namespace tidy
214 } // namespace clang
215