hokein updated this revision to Diff 96516.
hokein marked an inline comment as done.
hokein added a comment.
Fix doc.
https://reviews.llvm.org/D32436
Files:
clang-tidy/performance/InefficientVectorOperationCheck.cpp
clang-tidy/performance/InefficientVectorOperationCheck.h
docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
test/clang-tidy/performance-inefficient-vector-operation.cpp
Index: test/clang-tidy/performance-inefficient-vector-operation.cpp
===================================================================
--- test/clang-tidy/performance-inefficient-vector-operation.cpp
+++ test/clang-tidy/performance-inefficient-vector-operation.cpp
@@ -1,9 +1,27 @@
-// RUN: %check_clang_tidy %s performance-inefficient-vector-operation %t -- -format-style=llvm --
+// RUN: %check_clang_tidy %s performance-inefficient-vector-operation %t -- -format-style=llvm -- --std=c++11
namespace std {
typedef int size_t;
+template<class E> class initializer_list {
+public:
+ using value_type = E;
+ using reference = E&;
+ using const_reference = const E&;
+ using size_type = size_t;
+ using iterator = const E*;
+ using const_iterator = const E*;
+ initializer_list();
+ size_t size() const; // number of elements
+ const E* begin() const; // first element
+ const E* end() const; // one past the last element
+};
+
+// initializer list range access
+template<class E> const E* begin(initializer_list<E> il);
+template<class E> const E* end(initializer_list<E> il);
+
template <class T>
class vector {
public:
@@ -23,9 +41,24 @@
size_t size();
const_reference operator[] (size_type) const;
reference operator[] (size_type);
+
+ const_iterator begin() const;
+ const_iterator end() const;
};
} // namespace std
+class Foo {
+ public:
+ explicit Foo(int);
+};
+
+class Bar {
+ public:
+ Bar(int);
+};
+
+int Op(int);
+
void f(std::vector<int>& t) {
{
std::vector<int> v;
@@ -85,7 +118,38 @@
v.push_back(t[i]);
} // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
}
-
+ {
+ std::vector<int> v;
+ // CHECK-FIXES: v.reserve(t.size());
+ for (const auto &e : t) {
+ v.push_back(e);
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
+ }
+ }
+ {
+ std::vector<int> v;
+ // CHECK-FIXES: v.reserve(t.size());
+ for (const auto &e : t) {
+ v.push_back(Op(e));
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
+ }
+ }
+ {
+ std::vector<Foo> v;
+ // CHECK-FIXES: v.reserve(t.size());
+ for (const auto &e : t) {
+ v.push_back(Foo(e));
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
+ }
+ }
+ {
+ std::vector<Bar> v;
+ // CHECK-FIXES: v.reserve(t.size());
+ for (const auto &e : t) {
+ v.push_back(e);
+ // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
+ }
+ }
// ---- Non-fixed Cases ----
{
std::vector<int> v;
@@ -181,4 +245,21 @@
v.push_back(t[i]);
}
}
+ {
+ std::vector<int> v;
+ // initializer_list should not trigger the check.
+ for (int e : {1, 2, 3, 4, 5}) {
+ v.push_back(e);
+ }
+ }
+ {
+ std::vector<int> v;
+ std::vector<int>* v2 = &t;
+ // We only support detecting the range init expression which references
+ // container directly.
+ // Complex range init expressions like `*v2` is not supported.
+ for (const auto &e : *v2) {
+ v.push_back(e);
+ }
+ }
}
Index: docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
===================================================================
--- docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
+++ docs/clang-tidy/checks/performance-inefficient-vector-operation.rst
@@ -3,11 +3,13 @@
performance-inefficient-vector-operation
========================================
-Finds possible inefficient `std::vector` operations (e.g. `push_back`) that may
-cause unnecessary memory reallocations.
+Finds possible inefficient ``std::vector`` operations (e.g. ``push_back``) that
+may cause unnecessary memory reallocations.
-Currently, the check only detects a typical counter-based for loop with a single
-statement in it, see below:
+Currently, the check only detects following kinds of loops with a single
+statement body:
+
+* Counter-based for loops start with 0:
.. code-block:: c++
@@ -18,3 +20,30 @@
// memory reallocations in v. This can be avoid by inserting a 'reserve(n)'
// statment before the for statment.
}
+
+
+* For-range loops like ``for (range-declaration : range_expression)``, the type
+ of ``range_expression`` can be ``std::vector``, ``std::array``,
+ ``std::dequeue``, ``std::set``, ``std::unordered_set``, ``std::map``,
+ ``std::unordered_set``:
+
+.. code-block:: c++
+
+ std::vector<int> data;
+ std::vector<int> v;
+
+ for (auto element : data) {
+ v.push_back(element);
+ // This will trigger the warning since the 'push_back' may cause multiple
+ // memory reallocations in v. This can be avoid by inserting a
+ // 'reserve(data.size())' statment before the for statment.
+ }
+
+
+Options
+-------
+
+.. option:: VectorLikeClasses
+
+ Semicolon-separated list of names of vector-like classes. By default only
+ ``::std::vector`` is considered.
Index: clang-tidy/performance/InefficientVectorOperationCheck.h
===================================================================
--- clang-tidy/performance/InefficientVectorOperationCheck.h
+++ clang-tidy/performance/InefficientVectorOperationCheck.h
@@ -23,10 +23,13 @@
/// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-vector-operation.html
class InefficientVectorOperationCheck : public ClangTidyCheck {
public:
- InefficientVectorOperationCheck(StringRef Name, ClangTidyContext *Context)
- : ClangTidyCheck(Name, Context) {}
+ InefficientVectorOperationCheck(StringRef Name, ClangTidyContext *Context);
void registerMatchers(ast_matchers::MatchFinder *Finder) override;
void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+ void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+
+private:
+ const std::vector<std::string> VectorLikeClasses;
};
} // namespace performance
Index: clang-tidy/performance/InefficientVectorOperationCheck.cpp
===================================================================
--- clang-tidy/performance/InefficientVectorOperationCheck.cpp
+++ clang-tidy/performance/InefficientVectorOperationCheck.cpp
@@ -12,6 +12,7 @@
#include "clang/ASTMatchers/ASTMatchFinder.h"
#include "clang/Lex/Lexer.h"
#include "../utils/DeclRefExprUtils.h"
+#include "../utils/OptionsUtils.h"
using namespace clang::ast_matchers;
@@ -33,7 +34,7 @@
// \endcode
//
// The matcher names are bound to following parts of the AST:
-// - LoopName: The entire for loop (as ForStmt).
+// - LoopCounterName: The entire for loop (as ForStmt).
// - LoopParentName: The body of function f (as CompoundStmt).
// - VectorVarDeclName: 'v' in (as VarDecl).
// - VectorVarDeclStmatName: The entire 'std::vector<T> v;' statement (as
@@ -46,14 +47,35 @@
static const char VectorVarDeclName[] = "vector_var_decl";
static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt";
static const char PushBackCallName[] = "push_back_call";
-
static const char LoopInitVarName[] = "loop_init_var";
static const char LoopEndExprName[] = "loop_end_expr";
+static const char RangeLoopName[] = "for_range_loop";
+
+ast_matchers::internal::Matcher<Expr> supportedContainerTypesMatcher() {
+ const auto types = cxxRecordDecl(hasAnyName(
+ "::std::vector", "::std::set", "::std::unordered_set", "::std::map",
+ "::std::unordered_map", "::std::array", "::std::dequeue"));
+ return hasType(types);
+}
+
} // namespace
+InefficientVectorOperationCheck::InefficientVectorOperationCheck(
+ StringRef Name, ClangTidyContext *Context)
+ : ClangTidyCheck(Name, Context),
+ VectorLikeClasses(utils::options::parseStringList(
+ Options.get("VectorLikeClasses", "::std::vector"))) {}
+
+void InefficientVectorOperationCheck::storeOptions(
+ ClangTidyOptions::OptionMap &Opts) {
+ Options.store(Opts, "VectorLikeClasses",
+ utils::options::serializeStringList(VectorLikeClasses));
+}
+
void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
- const auto VectorDecl = cxxRecordDecl(hasName("::std::vector"));
+ const auto VectorDecl = cxxRecordDecl(hasAnyName(SmallVector<StringRef, 5>(
+ VectorLikeClasses.begin(), VectorLikeClasses.end())));
const auto VectorDefaultConstructorCall = cxxConstructExpr(
hasType(VectorDecl),
hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
@@ -77,6 +99,12 @@
const auto RefersToLoopVar = ignoringParenImpCasts(
declRefExpr(to(varDecl(equalsBoundNode(LoopInitVarName)))));
+ // Matchers for the loop whose body has only 1 push_back calling statement.
+ const auto HasInterestedLoopBody = hasBody(anyOf(
+ compoundStmt(statementCountIs(1), has(PushBackCall)), PushBackCall));
+ const auto InInterestedCompoundStmt =
+ hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName));
+
// Match counter-based for loops:
// for (int i = 0; i < n; ++i) { v.push_back(...); }
//
@@ -90,11 +118,18 @@
.bind(LoopEndExprName)))),
hasIncrement(unaryOperator(hasOperatorName("++"),
hasUnaryOperand(RefersToLoopVar))),
- hasBody(anyOf(compoundStmt(statementCountIs(1), has(PushBackCall)),
- PushBackCall)),
- hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName)))
+ HasInterestedLoopBody, InInterestedCompoundStmt)
.bind(LoopCounterName),
this);
+
+ // Match for-range loops:
+ // for (const auto& E : data) { v.push_back(...); }
+ Finder->addMatcher(
+ cxxForRangeStmt(
+ hasRangeInit(declRefExpr(supportedContainerTypesMatcher())),
+ HasInterestedLoopBody, InInterestedCompoundStmt)
+ .bind(RangeLoopName),
+ this);
}
void InefficientVectorOperationCheck::check(
@@ -104,13 +139,21 @@
return;
const SourceManager &SM = *Result.SourceManager;
+ const auto *VectorVarDecl =
+ Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName);
const auto *ForLoop = Result.Nodes.getNodeAs<ForStmt>(LoopCounterName);
+ const auto *RangeLoop =
+ Result.Nodes.getNodeAs<CXXForRangeStmt>(RangeLoopName);
const auto *PushBackCall =
Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackCallName);
const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);
const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);
- const auto *VectorVarDecl =
- Result.Nodes.getNodeAs<VarDecl>(VectorVarDeclName);
+
+ const Stmt * LoopStmt = nullptr;
+ if (ForLoop)
+ LoopStmt = ForLoop;
+ else
+ LoopStmt = RangeLoop;
llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVectorVarRefs =
utils::decl_ref_expr::allDeclRefExprs(*VectorVarDecl, *LoopParent,
@@ -124,25 +167,43 @@
// FIXME: make it more intelligent to identify the pre-allocating operations
// before the for loop.
if (SM.isBeforeInTranslationUnit(Ref->getLocation(),
- ForLoop->getLocStart())) {
+ LoopStmt->getLocStart())) {
return;
}
}
- llvm::StringRef LoopEndSource = Lexer::getSourceText(
- CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,
- Context->getLangOpts());
llvm::StringRef VectorVarName = Lexer::getSourceText(
CharSourceRange::getTokenRange(
PushBackCall->getImplicitObjectArgument()->getSourceRange()),
SM, Context->getLangOpts());
- std::string ReserveStmt =
- (VectorVarName + ".reserve(" + LoopEndSource + ");\n").str();
- diag(PushBackCall->getLocStart(),
+ std::string ReserveStmt;
+ // Handle for-range loop cases.
+ if (RangeLoop) {
+ // Get the range-expression in a for-range statement represented as
+ // `for (range-declarator: range-expression)`.
+ llvm::StringRef RangeInitExpName = clang::Lexer::getSourceText(
+ CharSourceRange::getTokenRange(
+ RangeLoop->getRangeInit()->getSourceRange()),
+ SM, Context->getLangOpts());
+
+ ReserveStmt =
+ (VectorVarName + ".reserve(" + RangeInitExpName + ".size()" + ");\n")
+ .str();
+ } else if (ForLoop) {
+ // Handle counter-based loop cases.
+ llvm::StringRef LoopEndSource = Lexer::getSourceText(
+ CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM,
+ Context->getLangOpts());
+ ReserveStmt = (VectorVarName + ".reserve(" + LoopEndSource + ");\n").str();
+ }
+
+ auto Diag = diag(PushBackCall->getLocStart(),
"'push_back' is called inside a loop; "
- "consider pre-allocating the vector capacity before the loop")
- << FixItHint::CreateInsertion(ForLoop->getLocStart(), ReserveStmt);
+ "consider pre-allocating the vector capacity before the loop");
+
+ if (!ReserveStmt.empty())
+ Diag << FixItHint::CreateInsertion(LoopStmt->getLocStart(), ReserveStmt);
}
} // namespace performance
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
