Index: clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.h =================================================================== --- clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.h +++ clang-tools-extra/trunk/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 VectorLikeClasses; }; } // namespace performance Index: clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.cpp =================================================================== --- clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.cpp +++ clang-tools-extra/trunk/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 v;' statement (as @@ -46,14 +47,34 @@ 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 supportedContainerTypesMatcher() { + return hasType(cxxRecordDecl(hasAnyName( + "::std::vector", "::std::set", "::std::unordered_set", "::std::map", + "::std::unordered_map", "::std::array", "::std::dequeue"))); +} + } // 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( + VectorLikeClasses.begin(), VectorLikeClasses.end()))); const auto VectorDefaultConstructorCall = cxxConstructExpr( hasType(VectorDecl), hasDeclaration(cxxConstructorDecl(isDefaultConstructor()))); @@ -77,6 +98,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 HasInterestingLoopBody = hasBody(anyOf( + compoundStmt(statementCountIs(1), has(PushBackCall)), PushBackCall)); + const auto InInterestingCompoundStmt = + hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName)); + // Match counter-based for loops: // for (int i = 0; i < n; ++i) { v.push_back(...); } // @@ -90,11 +117,20 @@ .bind(LoopEndExprName)))), hasIncrement(unaryOperator(hasOperatorName("++"), hasUnaryOperand(RefersToLoopVar))), - hasBody(anyOf(compoundStmt(statementCountIs(1), has(PushBackCall)), - PushBackCall)), - hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName))) + HasInterestingLoopBody, InInterestingCompoundStmt) .bind(LoopCounterName), this); + + // Match for-range loops: + // for (const auto& E : data) { v.push_back(...); } + // + // FIXME: Support more complex range-expressions. + Finder->addMatcher( + cxxForRangeStmt( + hasRangeInit(declRefExpr(supportedContainerTypesMatcher())), + HasInterestingLoopBody, InInterestingCompoundStmt) + .bind(RangeLoopName), + this); } void InefficientVectorOperationCheck::check( @@ -104,13 +140,19 @@ return; const SourceManager &SM = *Result.SourceManager; + const auto *VectorVarDecl = + Result.Nodes.getNodeAs(VectorVarDeclName); const auto *ForLoop = Result.Nodes.getNodeAs(LoopCounterName); + const auto *RangeLoop = + Result.Nodes.getNodeAs(RangeLoopName); const auto *PushBackCall = Result.Nodes.getNodeAs(PushBackCallName); const auto *LoopEndExpr = Result.Nodes.getNodeAs(LoopEndExprName); const auto *LoopParent = Result.Nodes.getNodeAs(LoopParentName); - const auto *VectorVarDecl = - Result.Nodes.getNodeAs(VectorVarDeclName); + + const Stmt *LoopStmt = ForLoop; + if (!LoopStmt) + LoopStmt = RangeLoop; llvm::SmallPtrSet AllVectorVarRefs = utils::decl_ref_expr::allDeclRefExprs(*VectorVarDecl, *LoopParent, @@ -124,25 +166,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)`. + StringRef RangeInitExpName = 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. + 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 Index: clang-tools-extra/trunk/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst =================================================================== --- clang-tools-extra/trunk/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst +++ clang-tools-extra/trunk/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 data; + std::vector 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-tools-extra/trunk/test/clang-tidy/performance-inefficient-vector-operation.cpp =================================================================== --- clang-tools-extra/trunk/test/clang-tidy/performance-inefficient-vector-operation.cpp +++ clang-tools-extra/trunk/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 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 const E* begin(initializer_list il); +template const E* end(initializer_list il); + template 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& t) { { std::vector v; @@ -85,7 +118,38 @@ v.push_back(t[i]); } // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called } - + { + std::vector 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 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 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 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 v; @@ -181,4 +245,21 @@ v.push_back(t[i]); } } + { + std::vector v; + // initializer_list should not trigger the check. + for (int e : {1, 2, 3, 4, 5}) { + v.push_back(e); + } + } + { + std::vector v; + std::vector* 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); + } + } }