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"
20 namespace performance {
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";
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")));
72 return Node.HasSideEffects(Finder->getASTContext());
77 InefficientVectorOperationCheck::InefficientVectorOperationCheck(
81 Options.get(
"VectorLikeClasses",
"::std::vector"))),
82 EnableProto(Options.getLocalOrGlobal(
"EnableProto", false)) {}
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);
104 const auto AppendCallExpr =
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)))));
118 const auto HasInterestingLoopBody = hasBody(
119 anyOf(compoundStmt(statementCountIs(1), has(AppendCall)), AppendCall));
120 const auto InInterestingCompoundStmt =
121 hasParent(compoundStmt(has(TargetVarDefStmt)).bind(LoopParentName));
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),
153 anyOf(declRefExpr(supportedContainerTypesMatcher()),
154 memberExpr(hasObjectExpression(unless(hasSideEffects())),
155 supportedContainerTypesMatcher()))),
156 HasInterestingLoopBody, InInterestingCompoundStmt)
157 .bind(RangeLoopName),
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);
169 const auto ProtoDecl =
170 cxxRecordDecl(isDerivedFrom(
"::proto2::MessageLite"));
175 const auto AddFieldMethodDecl =
176 cxxMethodDecl(matchesName(
"::add_"), unless(isConst()));
177 addMatcher(ProtoDecl, ProtoVarDeclName, ProtoVarDeclStmtName,
178 AddFieldMethodDecl, ProtoAddFieldCallName, Finder);
183 const MatchFinder::MatchResult &Result) {
184 auto* Context = Result.Context;
185 if (Context->getDiagnostics().hasUncompilableErrorOccurred())
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);
202 const CXXMemberCallExpr *AppendCall =
203 VectorAppendCall ? VectorAppendCall : ProtoAddFieldCall;
204 assert(AppendCall &&
"no append call expression");
206 const Stmt *LoopStmt = ForLoop;
208 LoopStmt = RangeLoop;
210 const auto *TargetVarDecl = VectorVarDecl;
212 TargetVarDecl = ProtoVarDecl;
214 llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVarRefs =
217 for (
const auto *Ref : AllVarRefs) {
225 if (SM.isBeforeInTranslationUnit(Ref->getLocation(),
226 LoopStmt->getBeginLoc())) {
231 std::string PartialReserveStmt;
232 if (VectorAppendCall !=
nullptr) {
233 PartialReserveStmt =
".reserve";
235 llvm::StringRef FieldName = ProtoAddFieldCall->getMethodDecl()->getName();
236 FieldName.consume_front(
"add_");
237 std::string MutableFieldName = (
"mutable_" + FieldName).str();
238 PartialReserveStmt =
"." + MutableFieldName +
243 CharSourceRange::getTokenRange(
244 AppendCall->getImplicitObjectArgument()->getSourceRange()),
245 SM, Context->getLangOpts());
247 std::string ReserveSize;
252 StringRef RangeInitExpName =
254 RangeLoop->getRangeInit()->getSourceRange()),
255 SM, Context->getLangOpts());
256 ReserveSize = (RangeInitExpName +
".size()").str();
257 }
else if (ForLoop) {
260 CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,
261 Context->getLangOpts());
262 ReserveSize = std::string(LoopEndSource);
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);