[clang-tidy] performance-inefficient-vector-operation: Support proto repeated field

[congliu]

Summary

Finds calls that add element to protobuf repeated field in a loop without calling Reserve() before the loop. Calling Reserve() first can avoid unnecessary memory reallocations.

A new option EnableProto is added to guard this feature.

[Eugene.Zelenko]

Please mention new option in Release Notes.

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

9

See other checks documentation as example of options descriptions.

[lebedev.ri]

I'm not sure this is the correct approach.
I'd think the check instead should be parametrized, so this patch should become just extending the config.

[congliu]

Updated option descriptions.

[congliu]

In D67135#1657034, @lebedev.ri wrote:

I'm not sure this is the correct approach.
I'd think the check instead should be parametrized, so this patch should become just extending the config.

Could you elaborate how the parameterized check will look like? By config did you mean the check options?

[congliu]

Uploaded the correct diff...

[hokein]

your patch doesn't have a full context, please upload the patch with full context (=U99999) or use Arcanist.

I'd think the check instead should be parametrized, so this patch should become just extending the config.

The AST for protobuf is quite different compared with normal vector, so I don't think there will be an easy and simple way to do it in a config way.

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

86

nit: remove static_cast?

227

nit: getName().drop_front(sizeof("add_")).

233

for repeated fields, there should be add_foo, mutable_foo methods in the proto generated code (https://developers.google.com/protocol-buffers/docs/reference/cpp-generated#repeatednumeric).

So I think we can remove this check here.

249

the heuristic is limited, and will fail the cases like below:

MyProto proto;
set_proto_xxx_size(&proto);
for (int i = 0; i < n; ++i) {
   proto.add_xxx(i);
}

In the vector case, we do a more strict check, maybe we do the same way as well (but it will make the check fail to spot some cases)...

[congliu]

Addressed Haojian's comments.

• Do not warn when there is reference to the proto variable between its declaration and the loop body.
• Exclude const methods.
• Update tests.

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

227

Used 'sizeof("add_")-1' since "add_" is const char [5].

233

I intended to rule out the corner cases when a proto field name is "add_xxx". But now I think checking whether there is a "mutable_xxx" method is not a effective way to rule out the corner case. A simpler way is just checking whether add_xxx is const... I have updated the matcher to exclude const methods.

249

Good point. Let's avoid those false positives.

[hokein]

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

15

the include (probably added by clangd) is for google internal style, I believe you are developing at google internal codebase (rather than the opensource LLVM codebase)?

192

nit: const CXXMemberCallExpr *AppendCall =VectorAppendCall? VectorAppendCall:ProtoAddFieldCall;

195

In theory, this case should not be happened -- the callback is only invoked when we find a match for the interesting vector/proto cases.

Just use assert(AppendCall) << "no append call expression".

227

how about?

llvm::StringRef FieldName =
        ProtoAddFieldCall->getMethodDecl()->getName();
FieldName.consume_front("add_");
std::string MutableFieldName = ...;

233

I wasn't aware of this corner case, could you add a comment describing the heuristic we use here (around the matcher)?

263

I think the container name doesn't provide much information in the diag message, maybe just use
%0 is called inside a loop; consider pre-allocating the container capacity before the loop?

[congliu]

Addressed Haojian's comments.

[hokein]

thanks, looks good.

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

315

looks like we miss (), the same below.

[congliu]

Addressed Haojian's comment.

[hokein]

feel free to commit the patch.

[congliu]

Could someone commit this for me? I failed to commit this change...

[hokein]

In D67135#1669836, @congliu wrote:

Could someone commit this for me? I failed to commit this change...

Committed in rL371963, just curious why you failed to commit? if you are using llvm git monorepo, ./llvm/utils/git-svn/git-llvm push should work.

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

 /// Finds possible inefficient `std::vector` operations (e.g. `push_back`) in
 /// for loops that may cause unnecessary memory reallocations.
 ///
+/// When EnableProto, also finds calls that add element to protobuf repeated
+/// field without calling Reserve() first.
+///
 /// For the user-facing documentation see:
 /// http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-vector-operation.html
 class InefficientVectorOperationCheck : public ClangTidyCheck {

   void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
 
 private:
+  void AddMatcher(const ast_matchers::DeclarationMatcher &TargetRecordDecl,
+                  StringRef VarDeclName, StringRef VarDeclStmtName,
+                  const ast_matchers::DeclarationMatcher &AppendMethodDecl,
+                  StringRef AppendCallName, ast_matchers::MatchFinder *Finder);
   const std::vector<std::string> VectorLikeClasses;
+
+  // If true, also check inefficient operations for proto repeated fields.
+  bool EnableProto;
 };
 
 } // namespace performance

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

 //   for (int i = 0; i < 10 + 1; ++i) {
 //     v.push_back(i);
 //   }
+//
+//   SomeProto p;
+//   for (int i = 0; i < 10 + 1; ++i) {
+//     p.add_xxx(i);
+//   }
 // }
 // \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).
+//   - VectorVarDeclName: 'v' (as VarDecl).
 //   - VectorVarDeclStmatName: The entire 'std::vector<T> v;' statement (as
 //     DeclStmt).
 //   - PushBackOrEmplaceBackCallName: 'v.push_back(i)' (as cxxMemberCallExpr).
 //   - LoopInitVarName: 'i' (as VarDecl).
 //   - LoopEndExpr: '10+1' (as Expr).
+// If EnableProto, the proto related names are bound to the following parts:
+//   - ProtoRecordDeclName: 'SomeProto'.
+//   - ProtoVarDeclName: 'p' (as VarDecl).
+//   - ProtoVarDeclStmtName: The entire 'SomeProto p;' statement (as DeclStmt).
+//   - ProtoAddFieldCallName: 'p.add_xxx(i)' (as cxxMemberCallExpr).
 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 PushBackOrEmplaceBackCallName[] = "append_call";
+static const char ProtoRecordDeclName[] = "proto_record_decl";
+static const char ProtoVarDeclName[] = "proto_var_decl";
+static const char ProtoVarDeclStmtName[] = "proto_var_decl_stmt";
+static const char ProtoAddFieldCallName[] = "proto_add_field";
 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() {

     StringRef Name, ClangTidyContext *Context)
     : ClangTidyCheck(Name, Context),
       VectorLikeClasses(utils::options::parseStringList(
-          Options.get("VectorLikeClasses", "::std::vector"))) {}
+          Options.get("VectorLikeClasses", "::std::vector"))),
+      EnableProto(Options.getLocalOrGlobal("EnableProto", false)) {}
 
 void InefficientVectorOperationCheck::storeOptions(
     ClangTidyOptions::OptionMap &Opts) {
   Options.store(Opts, "VectorLikeClasses",
                 utils::options::serializeStringList(VectorLikeClasses));
+  Options.store(Opts, "EnableProto", static_cast<int64_t>(EnableProto));
 }
 
-void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
-  const auto VectorDecl = cxxRecordDecl(hasAnyName(SmallVector<StringRef, 5>(
-      VectorLikeClasses.begin(), VectorLikeClasses.end())));
-  const auto VectorDefaultConstructorCall = cxxConstructExpr(
-      hasType(VectorDecl),
+void InefficientVectorOperationCheck::AddMatcher(
+    const DeclarationMatcher &TargetRecordDecl, StringRef VarDeclName,
+    StringRef VarDeclStmtName, const DeclarationMatcher &AppendMethodDecl,
+    StringRef AppendCallName, MatchFinder *Finder) {
+  const auto DefaultConstructorCall = cxxConstructExpr(
+      hasType(TargetRecordDecl),
       hasDeclaration(cxxConstructorDecl(isDefaultConstructor())));
-  const auto VectorVarDecl =
-      varDecl(hasInitializer(VectorDefaultConstructorCall))
-          .bind(VectorVarDeclName);
-  const auto VectorAppendCallExpr =
-      cxxMemberCallExpr(
-          callee(cxxMethodDecl(hasAnyName("push_back", "emplace_back"))),
-          on(hasType(VectorDecl)),
-          onImplicitObjectArgument(declRefExpr(to(VectorVarDecl))))
-          .bind(PushBackOrEmplaceBackCallName);
-  const auto VectorAppendCall = expr(ignoringImplicit(VectorAppendCallExpr));
-  const auto VectorVarDefStmt =
-      declStmt(hasSingleDecl(equalsBoundNode(VectorVarDeclName)))
-          .bind(VectorVarDeclStmtName);
+  const auto TargetVarDecl =
+      varDecl(hasInitializer(DefaultConstructorCall)).bind(VarDeclName);
+  const auto TargetVarDefStmt = declStmt(hasSingleDecl(equalsBoundNode(VarDeclName)))
+                              .bind(VarDeclStmtName);
 
+  const auto AppendCallExpr =
+      cxxMemberCallExpr(
+          callee(AppendMethodDecl), on(hasType(TargetRecordDecl)),
+          onImplicitObjectArgument(declRefExpr(to(TargetVarDecl))))
+          .bind(AppendCallName);
+  const auto AppendCall = expr(ignoringImplicit(AppendCallExpr));
   const auto LoopVarInit =
       declStmt(hasSingleDecl(varDecl(hasInitializer(integerLiteral(equals(0))))
                                  .bind(LoopInitVarName)));

 
   // 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 HasInterestingLoopBody = hasBody(
+      anyOf(compoundStmt(statementCountIs(1), has(AppendCall)), AppendCall));
   const auto InInterestingCompoundStmt =
-      hasParent(compoundStmt(has(VectorVarDefStmt)).bind(LoopParentName));
+      hasParent(compoundStmt(has(TargetVarDefStmt)).bind(LoopParentName));
 
   // Match counter-based for loops:
-  //  for (int i = 0; i < n; ++i) { v.push_back(...); }
+  //  for (int i = 0; i < n; ++i) {
+  //    v.push_back(...);
+  //    // Or: proto.add_xxx(...);
+  //  }
   //
   // FIXME: Support more types of counter-based loops like decrement loops.
   Finder->addMatcher(

       this);
 
   // Match for-range loops:
-  //   for (const auto& E : data) { v.push_back(...); }
+  //   for (const auto& E : data) {
+  //     v.push_back(...);
+  //     // Or: proto.add_xxx(...);
+  //   }
   //
   // FIXME: Support more complex range-expressions.
   Finder->addMatcher(

       this);
 }
 
+void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) {
+  const auto VectorDecl = cxxRecordDecl(hasAnyName(SmallVector<StringRef, 5>(
+      VectorLikeClasses.begin(), VectorLikeClasses.end())));
+  const auto AppendMethodDecl =
+      cxxMethodDecl(hasAnyName("push_back", "emplace_back"));
+  AddMatcher(VectorDecl, VectorVarDeclName, VectorVarDeclStmtName,
+             AppendMethodDecl, PushBackOrEmplaceBackCallName, Finder);
+
+  if (EnableProto) {
+    const auto ProtoDecl = cxxRecordDecl(isDerivedFrom("::proto2::MessageLite"))
+                               .bind(ProtoRecordDeclName);
+    const auto AddFieldMethodDecl = cxxMethodDecl(matchesName("::add_"));
+    AddMatcher(ProtoDecl, ProtoVarDeclName, ProtoVarDeclStmtName,
+               AddFieldMethodDecl, ProtoAddFieldCallName, Finder);
+  }
+}
+
 void InefficientVectorOperationCheck::check(
     const MatchFinder::MatchResult &Result) {
   auto* Context = Result.Context;

       Result.Nodes.getNodeAs<CXXForRangeStmt>(RangeLoopName);
   const auto *VectorAppendCall =
       Result.Nodes.getNodeAs<CXXMemberCallExpr>(PushBackOrEmplaceBackCallName);
+  const auto *ProtoRecordDecl =
+      Result.Nodes.getNodeAs<CXXRecordDecl>(ProtoRecordDeclName);
+  const auto *ProtoVarDecl = Result.Nodes.getNodeAs<VarDecl>(ProtoVarDeclName);
+  const auto *ProtoAddFieldCall =
+      Result.Nodes.getNodeAs<CXXMemberCallExpr>(ProtoAddFieldCallName);
   const auto *LoopEndExpr = Result.Nodes.getNodeAs<Expr>(LoopEndExprName);
   const auto *LoopParent = Result.Nodes.getNodeAs<CompoundStmt>(LoopParentName);
 
+  const CXXMemberCallExpr *AppendCall = VectorAppendCall;
+  if (!AppendCall)
+    AppendCall = ProtoAddFieldCall;
+  if (!AppendCall)
+    return;
+
   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(),
-                                     LoopStmt->getBeginLoc())) {
-      return;
+  std::string PartialReserveStmt;
+  if (VectorAppendCall != nullptr) {
+    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(),
+                                       LoopStmt->getBeginLoc())) {
+        return;
+      }
+    }
+    PartialReserveStmt = ".reserve";
+  } else  {
+    std::string AddFieldName =
+        ProtoAddFieldCall->getMethodDecl()->getNameAsString();
+    std::string MutableFieldName =
+        ("mutable_" + ProtoAddFieldCall->getMethodDecl()->getName().substr(4))
+            .str();
+    {
+      auto Matches = match(cxxRecordDecl(hasMethod(hasName(MutableFieldName))),
+                           *ProtoRecordDecl, *Context);
+      if (Matches.empty()) {
+        // There is no method with name "mutable_xxx".
+        return;
+      }
     }
+
+    {
+      const auto MutableFieldCallExpr = cxxMemberCallExpr(
+          callee(cxxMethodDecl(hasAnyName({MutableFieldName, AddFieldName}))),
+          onImplicitObjectArgument(
+              declRefExpr(to(varDecl(equalsNode(ProtoVarDecl))))));
+      auto matches =
+          match(findAll(MutableFieldCallExpr.bind("maybe_reallocation")),
+                *LoopParent, *Context);
+      for (const auto &match : matches) {
+        const auto call =
+            match.getNodeAs<CXXMemberCallExpr>("maybe_reallocation");
+        // Skip cases where "mutable_xxx" or "add_xxx" is called before the
+        // loop.
+        if (SM.isBeforeInTranslationUnit(call->getEndLoc(),
+                                         LoopStmt->getBeginLoc())) {
+          return;
+        }
+      }
+    }
+    PartialReserveStmt = "." + MutableFieldName +
+                         "()->Reserve";  // e.g., ".mutable_xxx()->Reserve"
   }
 
-  llvm::StringRef VectorVarName = Lexer::getSourceText(
+  llvm::StringRef VarName = Lexer::getSourceText(
       CharSourceRange::getTokenRange(
-          VectorAppendCall->getImplicitObjectArgument()->getSourceRange()),
+          AppendCall->getImplicitObjectArgument()->getSourceRange()),
       SM, Context->getLangOpts());
 
-  std::string ReserveStmt;
+  std::string ReserveSize;
   // 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(
+    StringRef RangeInitExpName =
+        Lexer::getSourceText(CharSourceRange::getTokenRange(
                                  RangeLoop->getRangeInit()->getSourceRange()),
                              SM, Context->getLangOpts());
-
-    ReserveStmt =
-        (VectorVarName + ".reserve(" + RangeInitExpName + ".size()" + ");\n")
-            .str();
+    ReserveSize = (RangeInitExpName + ".size()").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();
+    ReserveSize = LoopEndSource;
   }
 
-  auto Diag =
-      diag(VectorAppendCall->getBeginLoc(),
-           "%0 is called inside a loop; "
-           "consider pre-allocating the vector capacity before the loop")
-      << VectorAppendCall->getMethodDecl()->getDeclName();
-
-  if (!ReserveStmt.empty())
+  auto Diag = diag(AppendCall->getBeginLoc(),
+                   "%0 is called inside a loop; consider pre-allocating the %1 "
+                   "capacity before the loop")
+              << AppendCall->getMethodDecl()->getDeclName()
+              << (VectorAppendCall != nullptr ? "vector" : "repeated field");
+  if (!ReserveSize.empty()) {
+    std::string ReserveStmt =
+        (VarName + PartialReserveStmt + "(" + ReserveSize + ");\n").str();
     Diag << FixItHint::CreateInsertion(LoopStmt->getBeginLoc(), ReserveStmt);
+  }
 }
 
 } // namespace performance

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

 Finds possible inefficient ``std::vector`` operations (e.g. ``push_back``,
 ``emplace_back``) that may cause unnecessary memory reallocations.
 
+When EnableProto, also finds calls that add element to protobuf repeated field
+in a loop without calling Reserve() before the loop. Calling Reserve() first
+can avoid unnecessary memory reallocations.
+
 Currently, the check only detects following kinds of loops with a single
 statement body:
 

     // statement before the for statement.
   }
 
+  SomeProto p;
+  for (int i = 0; i < n; ++i) {
+    p.add_xxx(n);
+    // This will trigger the warning since the add_xxx may cause multiple memory
+    // relloacations. This can be avoid by inserting a
+    // 'p.mutable_xxx().Reserve(n)' statement before the for statement.
+  }
 
 * For-range loops like ``for (range-declaration : range_expression)``, the type
   of ``range_expression`` can be ``std::vector``, ``std::array``,

clang-tools-extra/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 -- \
+// RUN: -format-style=llvm \
+// RUN: -config='{CheckOptions: \
+// RUN:  [{key: performance-inefficient-vector-operation.EnableProto, value: 1}]}'
 
 namespace std {
 

 
 int Op(int);
 
+namespace proto2 {
+class MessageLite {};
+class Message : public MessageLite {};
+} // namespace proto2
+
+class FooProto : public proto2::Message {
+public:
+  int *add_x();
+  void add_x(int x);
+  void mutable_x();
+  void mutable_y();
+};
+
+class BarProto : public proto2::Message {
+public:
+  int *add_x();
+  void add_x(int x);
+  void mutable_x();
+  void mutable_y();
+};
+
 void f(std::vector<int>& t) {
   {
     std::vector<int> v0;

     }
   }
 
+  {
+    FooProto foo;
+    // CHECK-FIXES: foo.mutable_x()->Reserve(5);
+    for (int i = 0; i < 5; i++) {
+      foo.add_x(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'add_x' is called inside a loop; consider pre-allocating the repeated field capacity before the loop
+    }
+  }
+  {
+    FooProto foo;
+    foo.mutable_y();
+    // CHECK-FIXES: foo.mutable_x()->Reserve(5);
+    for (int i = 0; i < 5; i++) {
+      foo.add_x(i);
+      // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'add_x' is called inside a loop
+    }
+  }
+
   // ---- Non-fixed Cases ----
   {
     std::vector<int> z0;

       z12.push_back(e);
     }
   }
+
+  {
+    FooProto foo;
+    foo.mutable_x();
+    // CHECK-FIXES-NOT: foo.mutable_x->Reserve(5);
+    for (int i = 0; i < 5; i++) {
+      foo.add_x(i);
+    }
+  }
+  {
+    FooProto foo;
+    // CHECK-FIXES-NOT: foo.mutable_x->Reserve(5);
+    for (int i = 0; i < 5; i++) {
+      foo.add_x(i);
+      foo.add_x(i);
+    }
+  }
+  {
+    FooProto foo;
+    // CHECK-FIXES-NOT: foo.mutable_x->Reserve(5);
+    foo.add_x(-1);
+    for (int i = 0; i < 5; i++) {
+      foo.add_x(i);
+    }
+  }
+  {
+    FooProto foo;
+    BarProto bar;
+    bar.mutable_x();
+    // CHECK-FIXES-NOT: foo.mutable_x->Reserve(5);
+    for (int i = 0; i < 5; i++) {
+      foo.add_x();
+      bar.add_x();
+    }
+  }
 }