diff --git a/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.h b/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.h --- a/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.h +++ b/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.h @@ -35,7 +35,11 @@ StringRef VarDeclName, StringRef VarDeclStmtName, const ast_matchers::DeclarationMatcher &AppendMethodDecl, StringRef AppendCallName, ast_matchers::MatchFinder *Finder); - const std::vector VectorLikeClasses; + const std::string VectorLikeClasses; + const std::string AppendNames; + const std::string ReserveNames; + const std::string SupportedRanges; + const std::string SizeNames; // If true, also check inefficient operations for proto repeated fields. bool EnableProto; diff --git a/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.cpp b/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.cpp --- a/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.cpp +++ b/clang-tools-extra/clang-tidy/performance/InefficientVectorOperationCheck.cpp @@ -7,11 +7,13 @@ //===----------------------------------------------------------------------===// #include "InefficientVectorOperationCheck.h" + +#include "../utils/DeclRefExprUtils.h" +#include "../utils/OptionsUtils.h" #include "clang/AST/ASTContext.h" #include "clang/ASTMatchers/ASTMatchFinder.h" #include "clang/Lex/Lexer.h" -#include "../utils/DeclRefExprUtils.h" -#include "../utils/OptionsUtils.h" +#include "llvm/Support/raw_ostream.h" using namespace clang::ast_matchers; @@ -54,6 +56,7 @@ static const char LoopParentName[] = "loop_parent"; static const char VectorVarDeclName[] = "vector_var_decl"; static const char VectorVarDeclStmtName[] = "vector_var_decl_stmt"; +static const char VectorReserveName[] = "vector_reserve_name"; static const char PushBackOrEmplaceBackCallName[] = "append_call"; static const char ProtoVarDeclName[] = "proto_var_decl"; static const char ProtoVarDeclStmtName[] = "proto_var_decl_stmt"; @@ -61,26 +64,58 @@ static const char LoopInitVarName[] = "loop_init_var"; static const char LoopEndExprName[] = "loop_end_expr"; static const char RangeLoopName[] = "for_range_loop"; +static const char RangeLoopArrayName[] = "for_range_array_loop"; +static const char RangeLoopSizeMethod[] = "for_range_size_name"; +static const char SupportedDefaultRanges[] = "::std::vector;" + "::std::set;" + "::std::unordered_set;" + "::std::map;" + "::std::unordered_map;" + "::std::array;" + "::std::deque"; + +static ast_matchers::internal::Matcher +hasAnyNameStdString(std::vector Names) { + return ast_matchers::internal::Matcher( + new ast_matchers::internal::HasNameMatcher(std::move(Names))); +} -ast_matchers::internal::Matcher supportedContainerTypesMatcher() { - return hasType(cxxRecordDecl(hasAnyName( - "::std::vector", "::std::set", "::std::unordered_set", "::std::map", - "::std::unordered_map", "::std::array", "::std::deque"))); +static std::vector parseStringListPair(StringRef LHS, + StringRef RHS) { + if (LHS.empty()) { + if (RHS.empty()) + return {}; + return utils::options::parseStringList(RHS); + } + if (RHS.empty()) + return utils::options::parseStringList(LHS); + llvm::SmallString<512> Buffer; + return utils::options::parseStringList((LHS + ";" + RHS).toStringRef(Buffer)); } +static ast_matchers::internal::Matcher +hasAnyNameListPair(StringRef LHS, StringRef RHS) { + return hasAnyNameStdString(parseStringListPair(LHS, RHS)); +} } // namespace InefficientVectorOperationCheck::InefficientVectorOperationCheck( StringRef Name, ClangTidyContext *Context) : ClangTidyCheck(Name, Context), - VectorLikeClasses(utils::options::parseStringList( - Options.get("VectorLikeClasses", "::std::vector"))), + VectorLikeClasses(Options.get("VectorLikeClasses", "")), + AppendNames(Options.get("AppendNames", "")), + ReserveNames(Options.get("ReserveNames", "")), + SupportedRanges(Options.get("SupportedRanges", "")), + SizeNames(Options.get("SizeNames", "")), EnableProto(Options.getLocalOrGlobal("EnableProto", false)) {} void InefficientVectorOperationCheck::storeOptions( ClangTidyOptions::OptionMap &Opts) { - Options.store(Opts, "VectorLikeClasses", - utils::options::serializeStringList(VectorLikeClasses)); + Options.store(Opts, "VectorLikeClasses", VectorLikeClasses); + Options.store(Opts, "AppendNames", AppendNames); + Options.store(Opts, "ReserveNames", ReserveNames); + Options.store(Opts, "SupportedRanges", SupportedRanges); + Options.store(Opts, "SizeNames", SizeNames); Options.store(Opts, "EnableProto", EnableProto); } @@ -143,19 +178,47 @@ // } // // FIXME: Support more complex range-expressions. + + auto RangeMatcher = [&](bool CheckConst) { + return cxxForRangeStmt( + hasRangeInit(declRefExpr( + (CheckConst ? expr(hasType(isConstQualified())) + : expr(unless(hasType(isConstQualified())))), + hasType(cxxRecordDecl( + hasAnyNameListPair(SupportedDefaultRanges, + SupportedRanges), + hasMethod( + cxxMethodDecl(hasAnyNameListPair("size", SizeNames), + parameterCountIs(0), isPublic(), + (CheckConst ? isConst() : anything()), + returns(isInteger())) + .bind(RangeLoopSizeMethod)))))), + HasInterestingLoopBody, InInterestingCompoundStmt) + .bind(RangeLoopName); + }; + Finder->addMatcher(RangeMatcher(true), this); + Finder->addMatcher(RangeMatcher(false), this); Finder->addMatcher( - cxxForRangeStmt( - hasRangeInit(declRefExpr(supportedContainerTypesMatcher())), - HasInterestingLoopBody, InInterestingCompoundStmt) - .bind(RangeLoopName), + cxxForRangeStmt(hasRangeInit(declRefExpr(hasType(arrayType()))), + unless(isInTemplateInstantiation()), + HasInterestingLoopBody, InInterestingCompoundStmt) + .bind(RangeLoopArrayName), this); } void InefficientVectorOperationCheck::registerMatchers(MatchFinder *Finder) { - const auto VectorDecl = cxxRecordDecl(hasAnyName(SmallVector( - VectorLikeClasses.begin(), VectorLikeClasses.end()))); + + if (!getLangOpts().CPlusPlus) + return; + + const auto VectorDecl = cxxRecordDecl( + hasAnyNameListPair("::std::vector", VectorLikeClasses), + hasMethod(cxxMethodDecl(hasAnyNameListPair("reserve", ReserveNames), + isPublic(), parameterCountIs(1), + hasParameter(0, hasType(isInteger()))) + .bind(VectorReserveName))); const auto AppendMethodDecl = - cxxMethodDecl(hasAnyName("push_back", "emplace_back")); + cxxMethodDecl(hasAnyNameListPair("push_back;emplace_back", AppendNames)); AddMatcher(VectorDecl, VectorVarDeclName, VectorVarDeclStmtName, AppendMethodDecl, PushBackOrEmplaceBackCallName, Finder); @@ -185,6 +248,8 @@ const auto *ForLoop = Result.Nodes.getNodeAs(LoopCounterName); const auto *RangeLoop = Result.Nodes.getNodeAs(RangeLoopName); + const auto *RangeLoopArray = + Result.Nodes.getNodeAs(RangeLoopArrayName); const auto *VectorAppendCall = Result.Nodes.getNodeAs(PushBackOrEmplaceBackCallName); const auto *ProtoVarDecl = Result.Nodes.getNodeAs(ProtoVarDeclName); @@ -200,6 +265,8 @@ const Stmt *LoopStmt = ForLoop; if (!LoopStmt) LoopStmt = RangeLoop; + if (!LoopStmt) + LoopStmt = RangeLoopArray; const auto *TargetVarDecl = VectorVarDecl; if (!TargetVarDecl) @@ -222,23 +289,33 @@ } } - std::string PartialReserveStmt; + SmallString<64> Buffer; + llvm::raw_svector_ostream FixIt(Buffer); + + // Add the name to the FixIt insertion + FixIt << Lexer::getSourceText( + CharSourceRange::getTokenRange( + AppendCall->getImplicitObjectArgument()->getSourceRange()), + SM, Context->getLangOpts()); + + // Add the start of the reserve to the FixIt insertion + // .reserve( if (VectorAppendCall != nullptr) { - PartialReserveStmt = ".reserve"; + const auto *ReserveMethod = + Result.Nodes.getNodeAs(VectorReserveName); + assert(ReserveMethod && "Reserve Method should not be null"); + FixIt << '.' << ReserveMethod->getName() << '('; } else { llvm::StringRef FieldName = ProtoAddFieldCall->getMethodDecl()->getName(); + assert(FieldName.startswith("add_") && + "Method call didn't start with 'add_'"); FieldName.consume_front("add_"); - std::string MutableFieldName = ("mutable_" + FieldName).str(); - PartialReserveStmt = "." + MutableFieldName + - "()->Reserve"; // e.g., ".mutable_xxx()->Reserve" + FixIt << ".mutable_" << FieldName + << "()->Reserve("; // e.g., ".mutable_xxx()->Reserve(" } - llvm::StringRef VarName = Lexer::getSourceText( - CharSourceRange::getTokenRange( - AppendCall->getImplicitObjectArgument()->getSourceRange()), - SM, Context->getLangOpts()); - - std::string ReserveSize; + // Add the Reserve size expression to the FixIt + // AmountToReserve // Handle for-range loop cases. if (RangeLoop) { // Get the range-expression in a for-range statement represented as @@ -247,24 +324,57 @@ Lexer::getSourceText(CharSourceRange::getTokenRange( RangeLoop->getRangeInit()->getSourceRange()), SM, Context->getLangOpts()); - ReserveSize = (RangeInitExpName + ".size()").str(); + const auto *SizeMethod = + Result.Nodes.getNodeAs(RangeLoopSizeMethod); + assert(SizeMethod && + "SizeMethod should be valid in a matched RangeForLoop"); + FixIt << RangeInitExpName << '.' << SizeMethod->getName() << "()"; } else if (ForLoop) { // Handle counter-based loop cases. StringRef LoopEndSource = Lexer::getSourceText( CharSourceRange::getTokenRange(LoopEndExpr->getSourceRange()), SM, Context->getLangOpts()); - ReserveSize = std::string(LoopEndSource); - } + FixIt << LoopEndSource; + } else if (RangeLoopArray) { + const auto *Array = dyn_cast( + RangeLoopArray->getRangeInit()->getType().getTypePtr()); + assert(Array && "Array should not be null in a RangeLoopArray"); + if (const auto *CArray = dyn_cast(Array)) + FixIt << CArray->getSize(); + else if (const auto *DArray = dyn_cast(Array)) + FixIt << Lexer::getSourceText( + CharSourceRange::getTokenRange( + DArray->getSizeExpr()->getSourceRange()), + SM, Context->getLangOpts()); + else if (const auto *VArray = dyn_cast(Array)) { + const Expr *SizeExpr = VArray->getSizeExpr(); + if (SizeExpr->HasSideEffects(*Context)) { + StringRef RangeInitExpName = Lexer::getSourceText( + CharSourceRange::getTokenRange( + RangeLoopArray->getRangeInit()->getSourceRange()), + SM, Context->getLangOpts()); + FixIt << "sizeof(" << RangeInitExpName << ") / sizeof(" + << RangeInitExpName << "[0])"; + } else { + FixIt << Lexer::getSourceText( + CharSourceRange::getTokenRange( + VArray->getSizeExpr()->getSourceRange()), + SM, Context->getLangOpts()); + } + } else + // IncompleteArrayType can't get the size + return; + } else + llvm_unreachable("Unknown loop"); - auto Diag = diag(AppendCall->getBeginLoc(), - "%0 is called inside a loop; consider pre-allocating the " - "container capacity before the loop") - << AppendCall->getMethodDecl()->getDeclName(); - if (!ReserveSize.empty()) { - std::string ReserveStmt = - (VarName + PartialReserveStmt + "(" + ReserveSize + ");\n").str(); - Diag << FixItHint::CreateInsertion(LoopStmt->getBeginLoc(), ReserveStmt); - } + FixIt << ");\n" << Lexer::getIndentationForLine(LoopStmt->getBeginLoc(), SM); + + auto Diag = + diag(AppendCall->getBeginLoc(), + "%0 is called inside a loop; consider pre-allocating the " + "container capacity before the loop") + << AppendCall->getMethodDecl()->getDeclName() + << FixItHint::CreateInsertion(LoopStmt->getBeginLoc(), FixIt.str()); } } // namespace performance diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -114,6 +114,10 @@ Changes in existing checks ^^^^^^^^^^^^^^^^^^^^^^^^^^ +- Improved :doc:`performance-inefficient-vector-operation + ` check now has + extra options for custom containers. + - Improved :doc:`readability-qualified-auto ` check now supports a `AddConstToQualified` to enable adding ``const`` qualifiers to variables diff --git a/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst b/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst --- a/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/performance-inefficient-vector-operation.rst @@ -34,9 +34,7 @@ } * For-range loops like ``for (range-declaration : range_expression)``, the type - of ``range_expression`` can be ``std::vector``, ``std::array``, - ``std::deque``, ``std::set``, ``std::unordered_set``, ``std::map``, - ``std::unordered_set``: + of ``range_expression`` are specified in :option:`SupportedRanges`: .. code-block:: c++ @@ -59,6 +57,32 @@ Semicolon-separated list of names of vector-like classes. By default only ``::std::vector`` is considered. +.. option:: AppendNames + + Semicolon-separated list of names of append methods in :option:`VectorLikeClasses`. + By default only ``push_back`` and ``emplace_back`` are considered. + +.. option:: ReserveNames + + Semicolon-separated list of names of reserve methods in :option:`VectorLikeClasses`. + By default only ``reserve`` is considered. + + Note the method must have `1` parameter that is of integral type. + +.. option:: SupportedRanges + + Semicolon-separated list of names of Range types for for-range expressions. + By default only ``std::vector``, ``std::array``, ``std::deque``, + ``std::set``, ``std::unordered_set``, ``std::map`` and ``std::unordered_set`` + are considered. + +.. option:: SizeNames + + Semicolon-separated list of names of size methods :option:`SupportedRanges`. + By default only ``size`` is considered. + + Note the method must have `0` parameters and return an integral type. + .. option:: EnableProto When non-zero, the check will also warn on inefficient operations for proto diff --git a/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-vector-operation.cpp b/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-vector-operation.cpp --- a/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-vector-operation.cpp +++ b/clang-tools-extra/test/clang-tidy/checkers/performance-inefficient-vector-operation.cpp @@ -1,7 +1,11 @@ // 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}]}' +// RUN: [{key: performance-inefficient-vector-operation.EnableProto, value: 1}, \ +// RUN: {key: performance-inefficient-vector-operation.VectorLikeClasses, value : MyContainer}, \ +// RUN: {key: performance-inefficient-vector-operation.SupportedRanges, value : MyContainer}, \ +// RUN: {key: performance-inefficient-vector-operation.ReserveNames, value : Reserve}, \ +// RUN: {key: performance-inefficient-vector-operation.AppendNames, value : PushBack}, \ +// RUN: {key: performance-inefficient-vector-operation.SizeNames, value : Size}, ]}' namespace std { @@ -359,3 +363,254 @@ } } } + +namespace OptionsValidMatchDefault { +template +class MyContainer { +public: + unsigned size() const; + T *begin() const; + T *end() const; + void push_back(const T &); + void reserve(unsigned); +}; + +void foo(const MyContainer &C) { + MyContainer CC1; + // CHECK-FIXES: {{^}} CC1.reserve(C.size()); + for (auto I : C) { + CC1.push_back(I); + // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace OptionsValidMatchDefault + +namespace OptionsValidMatchDifferentMethods { +template +class MyContainer { +public: + unsigned Size() const; + T *begin() const; + T *end() const; + void PushBack(const T &); + void Reserve(unsigned); +}; + +void foo(const MyContainer &C) { + MyContainer CC2; + // CHECK-FIXES: {{^}} CC2.Reserve(C.Size()); + for (auto I : C) { + CC2.PushBack(I); + // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: 'PushBack' is called + } +} +} // namespace OptionsValidMatchDifferentMethods + +namespace UnknownContainer { +template +class MyUContainer { +public: + unsigned size() const; + T *begin() const; + T *end() const; + void push_back(const T &); + void reserve(unsigned); +}; + +void foo(const MyUContainer &C) { + // MyUContainer isn't specified as a VectorLikeClass in the Config Options + MyUContainer CC3; + // CHECK-FIXES-NOT: {{^}} CC3.reserve(C.size()); + for (auto I : C) { + CC3.push_back(I); + // CHECK-MESSAGES-NOT: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace UnknownContainer + +namespace PrivateMethods { +namespace Size { +template +class MyContainer { + unsigned size() const; + +public: + T *begin() const; + T *end() const; + void push_back(const T &); + void reserve(unsigned); +}; + +void foo(const MyContainer &C) { + // MyContainer::size is private, so calling it will be invalid + MyContainer CC4; + // CHECK-FIXES-NOT: {{^}} CC4.reserve(C.size()); + for (auto I : C) { + CC4.push_back(I); + // CHECK-MESSAGES-NOT: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace Size +namespace Reserve { +template +class MyContainer { +public: + unsigned size() const; + T *begin() const; + T *end() const; + void push_back(const T &); + +private: + void reserve(unsigned); +}; + +void foo(const MyContainer &C) { + // MyContainer::reserve is private, so calling it will be invalid + MyContainer CC5; + // CHECK-FIXES-NOT: {{^}} CC5.reserve(C.size()); + for (auto I : C) { + CC5.push_back(I); + // CHECK-MESSAGES-NOT: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace Reserve +} // namespace PrivateMethods + +namespace BadSignatures { +namespace Size { +template +class MyContainer { +public: + char *size() const; + T *begin() const; + T *end() const; + void push_back(const T &); + void reserve(unsigned); +}; + +void foo(const MyContainer &C) { + // MyContainer::size doesn't return an integral type(char *), so ignore this class + MyContainer CC6; + // CHECK-FIXES-NOT: {{^}} CC6.reserve(C.size()); + for (auto I : C) { + CC6.push_back(I); + // CHECK-MESSAGES-NOT: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace Size +namespace Reserve { +template +class MyContainer { +public: + unsigned size() const; + T *begin() const; + T *end() const; + void push_back(const T &); + void reserve(); +}; + +void foo(const MyContainer &C) { + // MyContainer::reserve doesn't take a single integral argument, so ignore this class + MyContainer CC7; + // CHECK-FIXES-NOT: {{^}} CC7.reserve(C.size()); + for (auto I : C) { + CC7.push_back(I); + // CHECK-MESSAGES-NOT: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace Reserve +} // namespace BadSignatures + +namespace NonConstSizeMethod { +template +class MyContainer { +public: + unsigned size(); + T *begin() const; + T *end() const; + void push_back(const T &); + void reserve(unsigned); +}; + +void foo(const MyContainer &C) { + // MyContainer::size() isn't const, therefore we cant call C.size() as + // C is passed by const ref. + MyContainer CC8; + // CHECK-FIXES-NOT: {{^}} CC8.reserve(C.size()); + for (auto I : C) { + CC8.push_back(I); + // CHECK-MESSAGES-NOT: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} + +void bar(MyContainer &C) { + // MyContainer::size() isn't const, but C is passed by non-const ref so + // we can still call it. + MyContainer CC9; + // CHECK-FIXES: {{^}} CC9.reserve(C.size()); + for (auto I : C) { + CC9.push_back(I); + // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} +} // namespace NonConstSizeMethod + +namespace ArrayForRange { +int getSize(); +void foo() { + { + std::vector A1; + int Arr[] = {1, 2, 3}; + // CHECK-FIXES: {{^}} A1.reserve(3); + for (auto X : Arr) { + A1.push_back(X); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + } + { + std::vector A2; + int Arr[3]; + // CHECK-FIXES: {{^}} A2.reserve(3); + for (auto X : Arr) { + A2.push_back(X); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + } +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wvla-extension" + { + std::vector A3; + int Size = getSize(); + int Arr[Size]; + // CHECK-FIXES: {{^}} A3.reserve(Size); + for (auto X : Arr) { + A3.push_back(X); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + } + { + std::vector A4; + int Arr[getSize()]; + // CHECK-FIXES: {{^}} A4.reserve(sizeof(Arr) / sizeof(Arr[0])); + for (auto X : Arr) { + A4.push_back(X); + // CHECK-MESSAGES: :[[@LINE-1]]:7: warning: 'push_back' is called + } + } +#pragma clang diagnostic pop +} + +template +void foo() { + std::vector A5; + int TArr[N]; + // CHECK-FIXES: {{^}} A5.reserve(N); + // FIXME for (auto x : TArr) doesn't get resolved as a call to push_back + for (int x : TArr) { + A5.push_back(x); + // CHECK-MESSAGES: :[[@LINE-1]]:5: warning: 'push_back' is called + } +} + +void b() { foo<4>(); } // Ensure this doesn't try to insert A2.reserve(4) in template definition +} // namespace ArrayForRange \ No newline at end of file