diff --git a/clang-tools-extra/clang-tidy/performance/CMakeLists.txt b/clang-tools-extra/clang-tidy/performance/CMakeLists.txt --- a/clang-tools-extra/clang-tidy/performance/CMakeLists.txt +++ b/clang-tools-extra/clang-tidy/performance/CMakeLists.txt @@ -4,6 +4,7 @@ ) add_clang_library(clangTidyPerformanceModule + ExpensiveFlatContainerOperationCheck.cpp FasterStringFindCheck.cpp ForRangeCopyCheck.cpp ImplicitConversionInLoopCheck.cpp diff --git a/clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h b/clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.h @@ -0,0 +1,44 @@ +//===--- ExpensiveFlatContainerOperationCheck.h - clang-tidy ----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H + +#include "../ClangTidyCheck.h" + +#include + +namespace clang { +namespace tidy { +namespace performance { + +/// Warns when calling an O(N) operation on a flat container. +/// +/// For the user-facing documentation see: +/// http://clang.llvm.org/extra/clang-tidy/checks/performance/expensive-flat-container-operation.html +class ExpensiveFlatContainerOperationCheck : public ClangTidyCheck { +public: + ExpensiveFlatContainerOperationCheck(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; + bool isLanguageVersionSupported(const LangOptions &LangOpts) const override { + return LangOpts.CPlusPlus; + } + +private: + const bool WarnOutsideLoops; + const std::vector FlatContainers; +}; + +} // namespace performance +} // namespace tidy +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_PERFORMANCE_EXPENSIVEFLATCONTAINEROPERATIONCHECK_H diff --git a/clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp b/clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/performance/ExpensiveFlatContainerOperationCheck.cpp @@ -0,0 +1,102 @@ +//===--- ExpensiveFlatContainerOperationCheck.cpp - clang-tidy ------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "ExpensiveFlatContainerOperationCheck.h" + +#include "../utils/OptionsUtils.h" + +using namespace clang::ast_matchers; + +namespace { +const auto DefaultFlatContainers = + "::folly::sorted_vector_set; ::folly::sorted_vector_map;" + "::boost::container::flat_set; ::boost::container::flat_map;"; +} // namespace + +namespace clang { +namespace tidy { +namespace performance { + +ExpensiveFlatContainerOperationCheck::ExpensiveFlatContainerOperationCheck( + StringRef Name, ClangTidyContext *Context) + : ClangTidyCheck(Name, Context), + WarnOutsideLoops(Options.get("WarnOutsideLoops", false)), + FlatContainers(utils::options::parseStringList( + Options.get("FlatContainers", DefaultFlatContainers))) {} + +void ExpensiveFlatContainerOperationCheck::registerMatchers( + MatchFinder *Finder) { + const auto SoughtContainerDecl = cxxRecordDecl( + hasAnyName(FlatContainers), + has(typedefNameDecl( + hasName("value_type"), + hasType(hasUnqualifiedDesugaredType(type().bind("value_type")))))); + + const auto HasSoughtArrowMemberExpr = has(memberExpr( + isArrow(), hasObjectExpression( + hasType(pointerType(pointee(hasUnqualifiedDesugaredType( + recordType(hasDeclaration(SoughtContainerDecl))))))))); + + // We don't need to make sure the MemberExpr is not an arrow call, if it was + // the code wouldn't compile anyway. + const auto HasSoughtPeriodMemberExpr = + has(memberExpr(hasObjectExpression(hasType(hasUnqualifiedDesugaredType( + recordType(hasDeclaration(SoughtContainerDecl))))))); + + const auto HasEmplaceCall = callee(cxxMethodDecl(matchesName("emplace"))); + + const auto HasInsertCallWithValueTypeArgument = + cxxMemberCallExpr(callee(cxxMethodDecl(matchesName("insert"))), + hasAnyArgument(expr(hasType(hasUnqualifiedDesugaredType( + type(equalsBoundNode("value_type"))))))); + + const auto HasEraseCallWithOneArgument = cxxMemberCallExpr( + callee(cxxMethodDecl(matchesName("erase"))), argumentCountIs(1)); + + const auto SoughtFlatContainerOperation = + cxxMemberCallExpr( + anyOf(HasSoughtArrowMemberExpr, HasSoughtPeriodMemberExpr), + anyOf(HasEmplaceCall, HasInsertCallWithValueTypeArgument, + HasEraseCallWithOneArgument)) + .bind("call"); + + if (!WarnOutsideLoops) { + const auto IsWithinLoop = cxxMemberCallExpr( + hasAncestor( + stmt(anyOf(forStmt(), whileStmt(), doStmt(), cxxForRangeStmt())) + .bind("loop")), + // An easy false positive case: the variable is declared in the loop. + unless(onImplicitObjectArgument(declRefExpr(hasDeclaration( + decl(hasAncestor(stmt(equalsBoundNode("loop"))))))))); + + Finder->addMatcher( + cxxMemberCallExpr(SoughtFlatContainerOperation, IsWithinLoop), this); + } else { + Finder->addMatcher(SoughtFlatContainerOperation, this); + } +} + +void ExpensiveFlatContainerOperationCheck::check( + const MatchFinder::MatchResult &Result) { + const auto *Call = Result.Nodes.getNodeAs("call"); + + diag(Call->getExprLoc(), + "Single element operations are expensive for flat containers. " + "Consider using available bulk operations instead."); +} + +void ExpensiveFlatContainerOperationCheck::storeOptions( + ClangTidyOptions::OptionMap &Opts) { + Options.store(Opts, "WarnOutsideLoops", WarnOutsideLoops); + Options.store(Opts, "FlatContainers", + utils::options::serializeStringList(FlatContainers)); +} + +} // namespace performance +} // namespace tidy +} // namespace clang diff --git a/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp b/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp --- a/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp +++ b/clang-tools-extra/clang-tidy/performance/PerformanceTidyModule.cpp @@ -9,6 +9,7 @@ #include "../ClangTidy.h" #include "../ClangTidyModule.h" #include "../ClangTidyModuleRegistry.h" +#include "ExpensiveFlatContainerOperationCheck.h" #include "FasterStringFindCheck.h" #include "ForRangeCopyCheck.h" #include "ImplicitConversionInLoopCheck.h" @@ -32,6 +33,8 @@ class PerformanceModule : public ClangTidyModule { public: void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override { + CheckFactories.registerCheck( + "performance-expensive-flat-container-operation"); CheckFactories.registerCheck( "performance-faster-string-find"); CheckFactories.registerCheck( 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 @@ -104,6 +104,11 @@ Warns when a struct or class uses const or reference (lvalue or rvalue) data members. +- New :doc:`performance-expensive-flat-container-operation + ` check. + + Warns when calling an O(N) operation on a flat container. + New check aliases ^^^^^^^^^^^^^^^^^ diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst --- a/clang-tools-extra/docs/clang-tidy/checks/list.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst @@ -302,6 +302,7 @@ `objc-super-self `_, "Yes" `openmp-exception-escape `_, `openmp-use-default-none `_, + `performance-expensive-flat-container-operation `_, `performance-faster-string-find `_, "Yes" `performance-for-range-copy `_, "Yes" `performance-implicit-conversion-in-loop `_, diff --git a/clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst b/clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst new file mode 100644 --- /dev/null +++ b/clang-tools-extra/docs/clang-tidy/checks/performance/expensive-flat-container-operation.rst @@ -0,0 +1,70 @@ +.. title:: clang-tidy - performance-expensive-flat-container-operation + +performance-expensive-flat-container-operation +============================================== + +Warns when calling an O(N) operation on a flat container. + +This check operates on vector-based flat containers such as +``boost::container::flat_(map|set)`` and ``folly::sorted_vector_(map|set)``. +While these containers' behavior is identical to usual maps/sets, the insert and +erase operations are O(N). This check flags such operations, which are a common +bad pattern, notably in loops. + +Below is an example of a typical bad pattern: inserting some values one by one +into a flat container. This is O(N^2), as the container will need to shift +elements right after each insertion. + +.. code-block:: c++ + + std::random_device generator; + std::uniform_int_distribution distribution; + + boost::container::flat_set set; + for (auto i = 0; i < N; ++i) { + set.insert(distribution(generator)); + } + +The code above can be improved using a temporary vector, later inserting all +values at once into the ``flat_set``. + +.. code-block:: c++ + + std::vector temporary; + for (auto i = 0; i < N; ++i) { + temporary.push_back(distribution(generator)); + } + boost::container::flat_set set(temporary.begin(), temporary.end()); + +For expensive-to-copy objects, ``std::move_iterator`` should be used. It is also +possible to move the temporary vector and use it directly as the underlying +container when using folly's ``sorted_vector_(map|set)``. + +Other solutions exist, including notably using a different map such as +``std::unordered_map`` when order is not important, bulk insertion with +iterators, ``boost::transform_iterator`` and ``erase_if``. + +This check is not capable of flagging insertions into a map via ``operator[]``, +as it is not possible at compile-time to know whether this will trigger an +insertion. These cases will have to be detected via dynamic profiling. + +Options +------- + +.. option:: WarnOutsideLoops + + When disabled, the check will only warn when the single element operation is + directly enclosed by a loop, hence directly actionable. At the very least, + these cases can be improved using some temporary container. + + When enabled, all insert and erase operations will be flagged. + + Default is `false`. + +.. option:: FlatContainers + + A semicolon-separated list of flat containers, with ``insert``, ``emplace`` + and/or ``erase`` operations. + + Default includes ``boost::container::flat_(map|set)`` and + ``folly::sorted_vector_(map|set)``. diff --git a/clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-warn-outside-loops.cpp b/clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-warn-outside-loops.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation-warn-outside-loops.cpp @@ -0,0 +1,383 @@ +// RUN: %check_clang_tidy %s performance-expensive-flat-container-operation %t -- \ +// RUN: -config="{CheckOptions: \ +// RUN: [{key: performance-expensive-flat-container-operation.WarnOutsideLoops, \ +// RUN: value: true}] \ +// RUN: }" + +namespace std { +template +struct pair { + pair(T1, T2); +}; + +template +struct initializer_list { + initializer_list(); +}; + +template struct remove_reference { typedef T type; }; +template struct remove_reference { typedef T type; }; +template struct remove_reference { typedef T type; }; + +template +typename std::remove_reference::type&& move(T&&) noexcept; +} // namespace std + +// Copied from boost/container/flat_map.hpp and boost/container/flat_set.hpp and simplified. +namespace boost { +namespace container { +struct ordered_unique_range_t {}; + +template +struct flat_map { + typedef Key key_type; + typedef T mapped_type; + typedef std::pair value_type; + + typedef int size_type; + typedef struct {} iterator; + typedef struct {} const_iterator; + + const_iterator begin() const noexcept; + const_iterator end() const noexcept; + + template std::pair emplace(Args&&...); + + template iterator emplace_hint(const_iterator, Args&&...); + + template std::pair try_emplace(const key_type&, Args&&...); + template iterator try_emplace(const_iterator, const key_type&, Args&&...); + template std::pair try_emplace(key_type&&, Args&&...); + template iterator try_emplace(const_iterator, key_type&&, Args&&...); + + std::pair insert(const value_type&); + std::pair insert(value_type&&); + iterator insert(const_iterator, const value_type&); + iterator insert(const_iterator, value_type&&); + template void insert(InputIterator, InputIterator); + template void insert(ordered_unique_range_t, InputIterator, InputIterator); + void insert(std::initializer_list); + void insert(ordered_unique_range_t, std::initializer_list); + + iterator erase(const_iterator); + size_type erase(const key_type&); + iterator erase(const_iterator, const_iterator); +}; + +template +struct flat_set { + typedef Key key_type; + typedef Key value_type; + + typedef int size_type; + typedef struct {} iterator; + typedef struct {} const_iterator; + + const_iterator begin() const noexcept; + const_iterator end() const noexcept; + + template std::pair emplace(Args&&...); + + template iterator emplace_hint(const_iterator, Args&&...); + + std::pair insert(const value_type&); + std::pair insert(value_type&&); + iterator insert(const_iterator, const value_type&); + iterator insert(const_iterator, value_type&&); + template void insert(InputIterator, InputIterator); + template void insert(ordered_unique_range_t, InputIterator, InputIterator); + void insert(std::initializer_list); + void insert(ordered_unique_range_t, std::initializer_list); + + iterator erase(const_iterator); + size_type erase(const key_type&); + iterator erase(const_iterator, const_iterator); +}; +} // namespace container +} // namespace boost + +// Copied from folly/sorted_vector_types.h and simplified. +namespace folly { +template struct sorted_vector_map { + typedef Key key_type; + typedef Value mapped_type; + typedef std::pair value_type; + + typedef int size_type; + typedef struct {} iterator; + typedef struct {} const_iterator; + + const_iterator begin() const; + const_iterator end() const; + + std::pair insert(const value_type&); + std::pair insert(value_type&&); + iterator insert(const_iterator, const value_type&); + iterator insert(const_iterator, value_type&&); + template void insert(InputIterator, InputIterator); + void insert(std::initializer_list); + + template std::pair emplace(Args&&...); + std::pair emplace(const value_type&); + std::pair emplace(value_type&&); + + template iterator emplace_hint(const_iterator, Args&&...); + iterator emplace_hint(const_iterator, const value_type&); + iterator emplace_hint(const_iterator, value_type&&); + + size_type erase(const key_type&); + iterator erase(const_iterator); + iterator erase(const_iterator, const_iterator); +}; + +template struct sorted_vector_set { + typedef T value_type; + typedef T key_type; + + typedef int size_type; + typedef struct {} iterator; + typedef struct {} const_iterator; + + const_iterator begin() const; + const_iterator end() const; + + std::pair insert(const value_type&); + std::pair insert(value_type&&); + iterator insert(const_iterator, const value_type&); + iterator insert(const_iterator, value_type&&); + template void insert(InputIterator, InputIterator); + void insert(std::initializer_list); + + template std::pair emplace(Args&&...); + std::pair emplace(const value_type&); + std::pair emplace(value_type&&); + + template iterator emplace_hint(const_iterator, Args&&...); + iterator emplace_hint(const_iterator, const value_type&); + iterator emplace_hint(const_iterator, value_type&&); + + size_type erase(const key_type&); + iterator erase(const_iterator); + iterator erase(const_iterator, const_iterator); +}; +} // namespace folly + +struct Foo { + Foo() {} + Foo(const Foo&) = default; + Foo(Foo&&) = default; +}; + +void TestBoostFlapMap() { + boost::container::flat_map bfm; + std::pair foo(Foo(), 13); + boost::container::ordered_unique_range_t bar; + + bfm.emplace(Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.emplace_hint(bfm.begin(), Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.try_emplace(Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.try_emplace(bfm.begin(), Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.try_emplace(Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.try_emplace(bfm.begin(), Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.insert(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.insert(std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.insert(bfm.begin(), foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.insert(bfm.begin(), std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.insert(bfm.begin(), bfm.end()); + bfm.insert(bar, bfm.begin(), bfm.end()); + bfm.insert(std::initializer_list>()); + bfm.insert(bar, std::initializer_list>()); + + bfm.erase(Foo()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.erase(bfm.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfm.erase(bfm.begin(), bfm.end()); +} + +void TestBoostFlatSet() { + boost::container::flat_set bfs; + Foo foo; + boost::container::ordered_unique_range_t bar; + + bfs.emplace(); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.emplace_hint(bfs.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.insert(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.insert(std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.insert(bfs.begin(), foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.insert(bfs.begin(), std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.insert(bfs.begin(), bfs.end()); + bfs.insert(bar, bfs.begin(), bfs.end()); + bfs.insert(std::initializer_list()); + bfs.insert(bar, std::initializer_list()); + + bfs.erase(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.erase(bfs.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + bfs.erase(bfs.begin(), bfs.end()); +} + +void TestFollySortedVectorMap() { + folly::sorted_vector_map fsvm; + std::pair foo(Foo(), 13); + + fsvm.insert(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.insert(std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.insert(fsvm.begin(), foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.insert(fsvm.begin(), std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.insert(fsvm.begin(), fsvm.end()); + fsvm.insert(std::initializer_list>()); + + fsvm.emplace(Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.emplace(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.emplace(std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.emplace_hint(fsvm.begin(), Foo(), 13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.emplace_hint(fsvm.begin(), foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.emplace_hint(fsvm.begin(), std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.erase(Foo()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.erase(fsvm.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvm.erase(fsvm.begin(), fsvm.end()); +} + +void TestFollySortedVectorSet() { + folly::sorted_vector_set fsvs; + Foo foo; + + fsvs.insert(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.insert(std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.insert(fsvs.begin(), foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.insert(fsvs.begin(), std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.insert(fsvs.begin(), fsvs.end()); + fsvs.insert(std::initializer_list()); + + fsvs.emplace(); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.emplace(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.emplace(std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.emplace_hint(fsvs.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.emplace_hint(fsvs.begin(), foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.emplace_hint(fsvs.begin(), std::move(foo)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.erase(foo); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.erase(fsvs.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + fsvs.erase(fsvs.begin(), fsvs.end()); +} + +struct A {}; +struct B : A {}; + +static int key = 13; +static int value = 31; + +void TestPossibleFalseNegatives() { + folly::sorted_vector_set fsvs; + fsvs.insert(5); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + folly::sorted_vector_set fsvs2; + fsvs2.insert(B()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + folly::sorted_vector_set> fsvs3; + fsvs3.insert(std::pair(13, 31)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + using CustomSortedVectorMapType = folly::sorted_vector_map; + CustomSortedVectorMapType map; + map.insert(std::pair(5, 5)); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + folly::sorted_vector_map* fsvmp = new folly::sorted_vector_map; + fsvmp->emplace(std::move(key), value); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + (&(*fsvmp))->emplace(std::move(key), value); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + auto& fsvmr = *fsvmp; + fsvmr.emplace(key, value); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. +} diff --git a/clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp b/clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/performance/expensive-flat-container-operation.cpp @@ -0,0 +1,106 @@ +// RUN: %check_clang_tidy %s performance-expensive-flat-container-operation %t -- \ +// RUN: -config="{CheckOptions: \ +// RUN: [{key: performance-expensive-flat-container-operation.WarnOutsideLoops, \ +// RUN: value: false}] \ +// RUN: }" + +namespace std { +template +struct pair { + pair(T1, T2); +}; + +template +struct initializer_list { + initializer_list(); +}; +} // namespace std + +// Copied from boost/container/flat_map.hpp and simplified. +namespace boost { +namespace container { +struct ordered_unique_range_t {}; + +template +struct flat_set { + typedef Key key_type; + typedef Key value_type; + + typedef int size_type; + typedef struct {} iterator; + typedef struct {} const_iterator; + + const_iterator begin() const noexcept; + const_iterator end() const noexcept; + + template std::pair emplace(Args&&...); + + template iterator emplace_hint(const_iterator, Args&&...); + + std::pair insert(const value_type&); + std::pair insert(value_type&&); + iterator insert(const_iterator, const value_type&); + iterator insert(const_iterator, value_type&&); + template void insert(InputIterator, InputIterator); + template void insert(ordered_unique_range_t, InputIterator, InputIterator); + void insert(std::initializer_list); + void insert(ordered_unique_range_t, std::initializer_list); + + iterator erase(const_iterator); + size_type erase(const key_type&); + iterator erase(const_iterator, const_iterator); +}; +} // namespace container +} // namespace boost + +static boost::container::flat_set gbfs; +boost::container::flat_set& getGlobalSetRef() { + return gbfs; +}; + +void TestCheckWithLoops() { + boost::container::flat_set bfs; + bfs.insert(13); + bfs.erase(13); + + for (int i = 0; i < 10; ++i) { + bfs.insert(i); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + if (i % 2 == 0) { + bfs.erase(i); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + } + } + + while (true) { + bfs.erase(bfs.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + } + + do { + (&bfs)->emplace(13); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + } while (false); + + for (int i = 0; i < 10; ++i) { + boost::container::flat_set bfs; + if (i % 2 == 0) { + bfs.insert(i); + + gbfs.insert(i); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + getGlobalSetRef().insert(i); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + + (gbfs).insert(i); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + } + + for (int j = 0; j < i; ++j) { + bfs.insert(2 * j); + // CHECK-MESSAGES: :[[@LINE-1]]:{{[0-9]+}}: warning: Single element operations are expensive for flat containers. + } + } +}