[clang-tidy] Add "emplace_back" detection in inefficient-vector-operation.

[malcolm.parsons]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

92 ↗

(On Diff #99044)

I'd use ignoringImplicit(VectorAppendCallExpr) to ignore ExprWithCleanups.

[alexfh]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

208 ↗

(On Diff #99044)

Diagnostic builder should be able to format NamedDecls directly, this ->getDeclName() is not necessary. The only difference is that it will likely add quotes around the name, which seems to be good anyway.

[hokein]

Adress review comments.

[hokein]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

92 ↗

(On Diff #99044)

Good to know. Thanks!

208 ↗

(On Diff #99044)

I tried it, but I found the behavior between using getDeclName() and not using getDeclName() is different when handling the template functions:

• diag(...) << VectorAppendCall->getMethodDecl() will print the function name with instantiated template arguments like "emplace_back<int&>";
• diag(...) << VectorAppendCall->getMethodDecl()->getDeclName() will just print the function name without template arguments, which is what we expect.

[alexfh]

clang-tidy/performance/InefficientVectorOperationCheck.cpp

50 ↗

(On Diff #99119)

nit: No need for the actual strings to be that long, since you're only using the corresponding constant names in the code. Even though there's no small string optimization used for bound AST nodes (they are stored in a std::map<std::string, ast_type_traits::DynTypedNode>), maps are frequently compared, which is less wasteful with shorter strings.

It would be interesting to see how large is the impact of longer or shorter string IDs, but until then we can still avoid overly long names.

208 ↗

(On Diff #99044)

Good to know.

test/clang-tidy/performance-inefficient-vector-operation.cpp

158 ↗

(On Diff #99119)

This pattern is ambiguous. I'd use unique variable name for each test to avoid patterns matching incorrect lines.

[alexfh]

LG once the comments are addressed.

[hokein]

Improve tests.

clang-tidy/performance/InefficientVectorOperationCheck.cpp

50 ↗

(On Diff #99119)

Acknowledged. Thanks for the detailed explanation ;)

test/clang-tidy/performance-inefficient-vector-operation.cpp

158 ↗

(On Diff #99119)

Sounds good. Also applied the change to the whole test file.

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

 // \endcode
 //
 // The matcher names are bound to following parts of the AST:
 //   - 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).
+//   - PushBackOrEmplaceBackCallName: '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 PushBackOrEmplaceBackCallName[] = "append_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",
void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
   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 =
+  const auto VectorAppendCallExpr =
       cxxMemberCallExpr(
-          callee(cxxMethodDecl(hasName("push_back"))), on(hasType(VectorDecl)),
+          callee(cxxMethodDecl(hasAnyName("push_back", "emplace_back"))),
+          on(hasType(VectorDecl)),
           onImplicitObjectArgument(declRefExpr(to(VectorVarDecl))))
-          .bind(PushBackCallName);
-  const auto PushBackCall =
-      expr(anyOf(PushBackCallExpr, exprWithCleanups(has(PushBackCallExpr))));
+          .bind(PushBackOrEmplaceBackCallName);
+  const auto VectorAppendCall = expr(ignoringImplicit(VectorAppendCallExpr));
   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));
+  // Matchers for the loop whose body has only 1 push_back/emplace_back calling
+  // statement.
+  const auto HasInterestingLoopBody =
+      hasBody(anyOf(compoundStmt(statementCountIs(1), has(VectorAppendCall)),
+                    VectorAppendCall));
   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(
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 *VectorAppendCall =
+      Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackOrEmplaceBackCallName);
   const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);
   const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);
 
   const Stmt *LoopStmt = ForLoop;
   if (!LoopStmt)
     LoopStmt = RangeLoop;
 
   llvm::SmallPtrSet<const DeclRefExpr *, 16> AllVectorVarRefs =
for (const auto *Ref : AllVectorVarRefs) {
     if (SM.isBeforeInTranslationUnit(Ref->getLocation(),
                                      LoopStmt->getLocStart())) {
       return;
     }
   }
 
   llvm::StringRef VectorVarName = Lexer::getSourceText(
       CharSourceRange::getTokenRange(
-          PushBackCall->getImplicitObjectArgument()->getSourceRange()),
+          VectorAppendCall->getImplicitObjectArgument()->getSourceRange()),
       SM, Context->getLangOpts());
 
   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");
+  auto Diag =
+      diag(VectorAppendCall->getLocStart(),
+           "%0 is called inside a loop; "
+           "consider pre-allocating the vector capacity before the loop")
+      << VectorAppendCall->getMethodDecl()->getDeclName();
 
   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``,
+``emplace_back``) that may cause unnecessary memory reallocations.
 
 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::deque``, ``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) {

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

public:
   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);
+
+  template <class... Args> void emplace_back(Args &&... args);
+
   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;

  public:
   Bar(int);
 };
 
 int Op(int);
 
 void f(std::vector<int>& t) {
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(10);
+    std::vector<int> v0;
+    // CHECK-FIXES: v0.reserve(10);
     for (int i = 0; i < 10; ++i)
-      v.push_back(i);
+      v0.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
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(10);
+    std::vector<int> v1;
+    // CHECK-FIXES: v1.reserve(10);
     for (int i = 0; i < 10; i++)
-      v.push_back(i);
+      v1.push_back(i);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(10);
+    std::vector<int> v2;
+    // CHECK-FIXES: v2.reserve(10);
     for (int i = 0; i < 10; ++i)
-      v.push_back(0);
+      v2.push_back(0);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(5);
+    std::vector<int> v3;
+    // CHECK-FIXES: v3.reserve(5);
     for (int i = 0; i < 5; ++i) {
-      v.push_back(i);
+      v3.push_back(i);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
     }
-    // CHECK-FIXES-NOT: v.reserve(10);
+    // CHECK-FIXES-NOT: v3.reserve(10);
     for (int i = 0; i < 10; ++i) {
       // No fix for this loop as we encounter the prior loops.
-      v.push_back(i);
+      v3.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    std::vector<int> v2;
-    v2.reserve(3);
-    // CHECK-FIXES: v.reserve(10);
+    std::vector<int> v4;
+    std::vector<int> v5;
+    v5.reserve(3);
+    // CHECK-FIXES: v4.reserve(10);
     for (int i = 0; i < 10; ++i)
-      v.push_back(i);
+      v4.push_back(i);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(t.size());
+    std::vector<int> v6;
+    // CHECK-FIXES: v6.reserve(t.size());
     for (std::size_t i = 0; i < t.size(); ++i) {
-      v.push_back(t[i]);
+      v6.push_back(t[i]);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
     }
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(t.size() - 1);
+    std::vector<int> v7;
+    // CHECK-FIXES: v7.reserve(t.size() - 1);
     for (std::size_t i = 0; i < t.size() - 1; ++i) {
-      v.push_back(t[i]);
+      v7.push_back(t[i]);
     } // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(t.size());
+    std::vector<int> v8;
+    // CHECK-FIXES: v8.reserve(t.size());
     for (const auto &e : t) {
-      v.push_back(e);
+      v8.push_back(e);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
     }
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES: v.reserve(t.size());
+    std::vector<int> v9;
+    // CHECK-FIXES: v9.reserve(t.size());
     for (const auto &e : t) {
-      v.push_back(Op(e));
+      v9.push_back(Op(e));
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
     }
   }
   {
-    std::vector<Foo> v;
-    // CHECK-FIXES: v.reserve(t.size());
+    std::vector<Foo> v10;
+    // CHECK-FIXES: v10.reserve(t.size());
     for (const auto &e : t) {
-      v.push_back(Foo(e));
+      v10.push_back(Foo(e));
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
     }
   }
   {
-    std::vector<Bar> v;
-    // CHECK-FIXES: v.reserve(t.size());
+    std::vector<Bar> v11;
+    // CHECK-FIXES: v11.reserve(t.size());
     for (const auto &e : t) {
-      v.push_back(e);
+      v11.push_back(e);
       // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called
     }
   }
+  {
+    std::vector<Foo> v12;
+    // CHECK-FIXES: v12.reserve(t.size());
+    for (const auto &e : t) {
+      v12.emplace_back(e);
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'emplace_back' is called
+    }
+  }
+
   // ---- Non-fixed Cases ----
   {
-    std::vector<int> v;
-    v.reserve(20);
-    // CHECK-FIXES-NOT: v.reserve(10);
+    std::vector<int> z0;
+    z0.reserve(20);
+    // CHECK-FIXES-NOT: z0.reserve(10);
     // There is a "reserve" call already.
     for (int i = 0; i < 10; ++i) {
-      v.push_back(i);
+      z0.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    v.reserve(5);
-    // CHECK-FIXES-NOT: v.reserve(10);
+    std::vector<int> z1;
+    z1.reserve(5);
+    // CHECK-FIXES-NOT: z1.reserve(10);
     // There is a "reserve" call already.
     for (int i = 0; i < 10; ++i) {
-      v.push_back(i);
+      z1.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    v.resize(5);
-    // CHECK-FIXES-NOT: v.reserve(10);
+    std::vector<int> z2;
+    z2.resize(5);
+    // CHECK-FIXES-NOT: z2.reserve(10);
     // There is a ref usage of v before the loop.
     for (int i = 0; i < 10; ++i) {
-      v.push_back(i);
+      z2.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    v.push_back(0);
-    // CHECK-FIXES-NOT: v.reserve(10);
+    std::vector<int> z3;
+    z3.push_back(0);
+    // CHECK-FIXES-NOT: z3.reserve(10);
     // There is a ref usage of v before the loop.
     for (int i = 0; i < 10; ++i) {
-      v.push_back(i);
+      z3.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    f(v);
-    // CHECK-FIXES-NOT: v.reserve(10);
-    // There is a ref usage of v before the loop.
+    std::vector<int> z4;
+    f(z4);
+    // CHECK-FIXES-NOT: z4.reserve(10);
+    // There is a ref usage of z4 before the loop.
     for (int i = 0; i < 10; ++i) {
-      v.push_back(i);
+      z4.push_back(i);
     }
   }
   {
-    std::vector<int> v(20);
-    // CHECK-FIXES-NOT: v.reserve(10);
-    // v is not constructed with default constructor.
+    std::vector<int> z5(20);
+    // CHECK-FIXES-NOT: z5.reserve(10);
+    // z5 is not constructed with default constructor.
     for (int i = 0; i < 10; ++i) {
-      v.push_back(i);
+      z5.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES-NOT: v.reserve(10);
+    std::vector<int> z6;
+    // CHECK-FIXES-NOT: z6.reserve(10);
     // For-loop is not started with 0.
     for (int i = 1; i < 10; ++i) {
-      v.push_back(i);
+      z6.push_back(i);
     }
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES-NOT: v.reserve(t.size());
-    // v isn't referenced in for-loop body.
+    std::vector<int> z7;
+    // CHECK-FIXES-NOT: z7.reserve(t.size());
+    // z7 isn't referenced in for-loop body.
     for (std::size_t i = 0; i < t.size(); ++i) {
       t.push_back(i);
     }
   }
   {
-    std::vector<int> v;
+    std::vector<int> z8;
     int k;
-    // CHECK-FIXES-NOT: v.reserve(10);
+    // CHECK-FIXES-NOT: z8.reserve(10);
     // For-loop isn't a fixable loop.
     for (std::size_t i = 0; k < 10; ++i) {
-      v.push_back(t[i]);
+      z8.push_back(t[i]);
     }
   }
   {
-    std::vector<int> v;
-    // CHECK-FIXES-NOT: v.reserve(i + 1);
+    std::vector<int> z9;
+    // CHECK-FIXES-NOT: z9.reserve(i + 1);
     // The loop end expression refers to the loop variable i.
     for (int i = 0; i < i + 1; i++)
-      v.push_back(i);
+      z9.push_back(i);
   }
   {
-    std::vector<int> v;
+    std::vector<int> z10;
     int k;
-    // CHECK-FIXES-NOT: v.reserve(10);
+    // CHECK-FIXES-NOT: z10.reserve(10);
     // For-loop isn't a fixable loop.
     for (std::size_t i = 0; i < 10; ++k) {
-      v.push_back(t[i]);
+      z10.push_back(t[i]);
     }
   }
   {
-    std::vector<int> v;
+    std::vector<int> z11;
     // initializer_list should not trigger the check.
     for (int e : {1, 2, 3, 4, 5}) {
-      v.push_back(e);
+      z11.push_back(e);
     }
   }
   {
-    std::vector<int> v;
-    std::vector<int>* v2 = &t;
+    std::vector<int> z12;
+    std::vector<int>* z13 = &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);
+    // Complex range init expressions like `*z13` is not supported.
+    for (const auto &e : *z13) {
+      z12.push_back(e);
     }
   }
 }