[clang-tidy] Support detecting for-range loop in inefficient-vector-operation check.

[hokein]

Summary

Also add an option "VectorLikeClasses" allowing user specify customized
vectors.

[Eugene.Zelenko]

docs/clang-tidy/checks/performance-inefficient-vector-operation.rst

6 ↗

(On Diff #96402)

Please use `` to highlight language elements. Same below.

[hokein]

Fix doc.

[alexfh]

Cool! A few nits.

clang-tidy/performance/InefficientVectorOperationCheck.cpp

56 ↗

(On Diff #96516)

I'd just inline the expression and remove the local variable, since it doesn't seem to bring any benefits.

103 ↗

(On Diff #96516)

s/Interested/Interesting/

129 ↗

(On Diff #96516)

It might be valuable to support more complex expressions here, though it would require more involved fixes, e.g.

for (const auto& e : *source)
  v.push_back(e);

->

v.reserve(source->size());
for (const auto& e : *source)
  v.push_back(e);

or even like this:

for (const auto& e : *some(complex)->container().expression())
  v.push_back(e);

->

const auto& source_container = *some(complex)->container().expression();
v.reserve(source_container.size());
for (const auto& e : source_container)
  v.push_back(e);

Maybe leave a FIXME for this?

152 ↗

(On Diff #96516)

const Stmt *LoopStmt = ForLoop ? ForLoop : RangeLoop;

185 ↗

(On Diff #96516)

No need to qualify StringRef and Lexer. Here and a couple of other instances in this function.

198 ↗

(On Diff #96516)

Does the check handle destination vector not being empty before the push_back loop? We'd need to reserve destination.size() + source.size() items in this case.

If this is not handled yet, please add a FIXME.

[hokein]

Address review comments.

[hokein]

Thanks for the comments!

clang-tidy/performance/InefficientVectorOperationCheck.cpp

129 ↗

(On Diff #96516)

Nice brainstorm, added a FIXME.

152 ↗

(On Diff #96516)

We can't do it because ForLoop and RangeLoop are different types.

198 ↗

(On Diff #96516)

This case should not happen, because we only find the push_back loop before which there are no usages (defined as DeclRefExpr that refers to vector`v`) of the vector v.

[alexfh]

LG

clang-tidy/performance/InefficientVectorOperationCheck.cpp

153 ↗

(On Diff #96738)

nit: Please remove the extra space after the asterisk.

152 ↗

(On Diff #96516)

Yup, static_cast<Stmt*> would be more ugly. This could still be shortened a bit:

const Stmt *LoopStmt = ForLoop;
if (!LoopStmt)
  LoopStmt = RangeLoop;

Not that it makes too much difference though. Up to you.

[hokein]

Address remaining nits.

clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.h

 
 /// Finds possible inefficient `std::vector` operations (e.g. `push_back`) in
 /// for loops that may cause unnecessary memory reallocations.
 ///
 /// For the user-facing documentation see:
 /// 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
 } // namespace tidy
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_INEFFICIENT_VECTOR_OPERATION_H

clang-tools-extra/trunk/clang-tidy/performance/InefficientVectorOperationCheck.cpp

 //===--- InefficientVectorOperationCheck.cpp - clang-tidy------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InefficientVectorOperationCheck.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Lex/Lexer.h"
 #include "../utils/DeclRefExprUtils.h"
+#include "../utils/OptionsUtils.h"
 
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {
 namespace performance {
 
 namespace {
 
 // Matcher names. Given the code:
 //
 // \code
 // void f() {
 //   vector<T> v;
 //   for (int i = 0; i < 10 + 1; ++i) {
 //     v.push_back(i);
 //   }
 // }
 // \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
 //     DeclStmt).
 //   - PushBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr).
 //   - LoopInitVarName: 'i' (as VarDecl).
 //   - LoopEndExpr: '10+1' (as Expr).
 static const char LoopCounterName[] = "for_loop_counter";
 static const char LoopParentName[] = "loop_parent";
 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() {
+  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<StringRef, 5>(
+      VectorLikeClasses.begin(), VectorLikeClasses.end())));
   const auto VectorDefaultConstructorCall = cxxConstructExpr(
       hasType(VectorDecl),
       hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
   const auto VectorVarDecl =
       varDecl(hasInitializer(VectorDefaultConstructorCall))
           .bind(VectorVarDeclName);
   const auto PushBackCallExpr =
       cxxMemberCallExpr(
           callee(cxxMethodDecl(hasName("push_back"))), on(hasType(VectorDecl)),
           onImplicitObjectArgument(declRefExpr(to(VectorVarDecl))))
           .bind(PushBackCallName);
   const auto PushBackCall =
       expr(anyOf(PushBackCallExpr, exprWithCleanups(has(PushBackCallExpr))));
   const auto VectorVarDefStmt =
       declStmt(hasSingleDecl(equalsBoundNode(VectorVarDeclName)))
           .bind(VectorVarDeclStmtName);
 
   const auto LoopVarInit =
       declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
                                  .bind(LoopInitVarName)));
   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(...); }
   //
   // FIXME: Support more types of counter-based loops like decrement loops.
   Finder->addMatcher(
       forStmt(
           hasLoopInit(LoopVarInit),
           hasCondition(binaryOperator(
               hasOperatorName("<"), hasLHS(RefersToLoopVar),
               hasRHS(expr(unless(hasDescendant(expr(RefersToLoopVar))))
                          .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(
     const MatchFinder::MatchResult &Result) {
   auto* Context = Result.Context;
   if (Context->getDiagnostics().hasUncompilableErrorOccurred())
     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 = ForLoop;
+  if (!LoopStmt)
+    LoopStmt = RangeLoop;
 
   llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVectorVarRefs =
       utils::decl_ref_expr::allDeclRefExprs(*VectorVarDecl, *LoopParent,
                                             *Context);
   for (const auto *Ref : AllVectorVarRefs) {
     // Skip cases where there are usages (defined as DeclRefExpr that refers to
     // "v") of vector variable `v` before the for loop. We consider these usages
     // are operations causing memory preallocation (e.g. "v.resize(n)",
     // "v.reserve(n)").
     //
     // 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
 } // namespace tidy
 } // namespace clang

clang-tools-extra/trunk/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst

 .. title:: clang-tidy - performance-inefficient-vector-operation
 
 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++
 
   std::vector<int> v;
   for (int i = 0; i < n; ++i) {
     v.push_back(n);
     // This will trigger the warning since the push_back may cause multiple
     // 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.

clang-tools-extra/trunk/test/clang-tidy/performance-inefficient-vector-operation.cpp

-// 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:
   typedef T* iterator;
   typedef const T* const_iterator;
   typedef T& reference;
   typedef const T& const_reference;
   typedef size_t size_type;
 
   explicit vector();
   explicit vector(size_type n);
 
   void push_back(const T& val);
   void reserve(size_t n);
   void resize(size_t n);
 
   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;
     // CHECK-FIXES: v.reserve(10);
     for (int i = 0; i < 10; ++i)
       v.push_back(i);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called inside a loop; consider pre-allocating the vector capacity before the loop
   }
void f(std::vector<int>& t) {
   }
   {
     std::vector<int> v;
     // CHECK-FIXES: v.reserve(t.size() - 1);
     for (std::size_t i = 0; i < t.size() - 1; ++i) {
       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;
     v.reserve(20);
     // CHECK-FIXES-NOT: v.reserve(10);
     // There is a "reserve" call already.
     for (int i = 0; i < 10; ++i) {
       v.push_back(i);
// ---- Non-fixed Cases ----
     std::vector<int> v;
     int k;
     // CHECK-FIXES-NOT: v.reserve(10);
     // For-loop isn't a fixable loop.
     for (std::size_t i = 0; i < 10; ++k) {
       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);
+    }
+  }
 }