https://github.com/lucasly-ba updated https://github.com/llvm/llvm-project/pull/210555
>From 0ebdbfc6cc69b41da77521d788bdf4777fd0015f Mon Sep 17 00:00:00 2001 From: Lucas Ly Ba <[email protected]> Date: Sat, 18 Jul 2026 23:48:58 +0200 Subject: [PATCH] [clang-tidy] Add `bugprone-unordered-equal-compare` check The iteration order of an unordered container is unspecified, so comparing the ranges of two of them with std::equal is order-dependent and can report equal containers as different. Flag such comparisons; operator== should be used instead. Fixes #173108 --- .../bugprone/BugproneTidyModule.cpp | 3 + .../clang-tidy/bugprone/CMakeLists.txt | 1 + .../bugprone/UnorderedEqualCompareCheck.cpp | 51 +++++++++ .../bugprone/UnorderedEqualCompareCheck.h | 41 +++++++ clang-tools-extra/docs/ReleaseNotes.rst | 7 ++ .../bugprone/unordered-equal-compare.rst | 31 ++++++ .../docs/clang-tidy/checks/list.rst | 1 + .../unordered-equal-compare-custom.cpp | 32 ++++++ .../bugprone/unordered-equal-compare.cpp | 102 ++++++++++++++++++ 9 files changed, 269 insertions(+) create mode 100644 clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.cpp create mode 100644 clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.h create mode 100644 clang-tools-extra/docs/clang-tidy/checks/bugprone/unordered-equal-compare.rst create mode 100644 clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare-custom.cpp create mode 100644 clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare.cpp diff --git a/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp b/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp index 3aa39d10ceb5d..12307f7a83629 100644 --- a/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp +++ b/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp @@ -110,6 +110,7 @@ #include "UnhandledSelfAssignmentCheck.h" #include "UnintendedCharOstreamOutputCheck.h" #include "UniquePtrArrayMismatchCheck.h" +#include "UnorderedEqualCompareCheck.h" #include "UnsafeFunctionsCheck.h" #include "UnsafeToAllowExceptionsCheck.h" #include "UnusedLocalNonTrivialVariableCheck.h" @@ -321,6 +322,8 @@ class BugproneModule : public ClangTidyModule { "bugprone-unique-ptr-array-mismatch"); CheckFactories.registerCheck<CrtpConstructorAccessibilityCheck>( "bugprone-crtp-constructor-accessibility"); + CheckFactories.registerCheck<UnorderedEqualCompareCheck>( + "bugprone-unordered-equal-compare"); CheckFactories.registerCheck<UnsafeFunctionsCheck>( "bugprone-unsafe-functions"); CheckFactories.registerCheck<UnsafeToAllowExceptionsCheck>( diff --git a/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt b/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt index 43e85b1407f21..9996486596fcf 100644 --- a/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt +++ b/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt @@ -112,6 +112,7 @@ add_clang_library(clangTidyBugproneModule STATIC UnhandledExceptionAtNewCheck.cpp UnhandledSelfAssignmentCheck.cpp UniquePtrArrayMismatchCheck.cpp + UnorderedEqualCompareCheck.cpp UnsafeFunctionsCheck.cpp UnsafeToAllowExceptionsCheck.cpp UnusedLocalNonTrivialVariableCheck.cpp diff --git a/clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.cpp b/clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.cpp new file mode 100644 index 0000000000000..b4b652742d9f7 --- /dev/null +++ b/clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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 "UnorderedEqualCompareCheck.h" +#include "../utils/OptionsUtils.h" +#include "clang/ASTMatchers/ASTMatchFinder.h" + +using namespace clang::ast_matchers; + +namespace clang::tidy::bugprone { + +UnorderedEqualCompareCheck::UnorderedEqualCompareCheck( + StringRef Name, ClangTidyContext *Context) + : ClangTidyCheck(Name, Context), + ContainerNames(utils::options::parseStringList(Options.get( + "Containers", "::std::unordered_set;::std::unordered_multiset;" + "::std::unordered_map;::std::unordered_multimap"))) {} + +void UnorderedEqualCompareCheck::storeOptions( + ClangTidyOptions::OptionMap &Opts) { + Options.store(Opts, "Containers", + utils::options::serializeStringList(ContainerNames)); +} + +void UnorderedEqualCompareCheck::registerMatchers(MatchFinder *Finder) { + auto UnorderedContainer = hasType(hasUnqualifiedDesugaredType( + recordType(hasDeclaration(cxxRecordDecl(hasAnyName(ContainerNames)))))); + + // An iterator obtained from an unordered container, e.g. c.begin(). + auto IteratorFromUnordered = cxxMemberCallExpr( + callee(cxxMethodDecl(hasAnyName("begin", "end", "cbegin", "cend"))), + on(expr(UnorderedContainer))); + + Finder->addMatcher(callExpr(callee(functionDecl(hasName("::std::equal"))), + hasAnyArgument(IteratorFromUnordered)) + .bind("call"), + this); +} + +void UnorderedEqualCompareCheck::check(const MatchFinder::MatchResult &Result) { + const auto *Call = Result.Nodes.getNodeAs<CallExpr>("call"); + diag(Call->getBeginLoc(), + "comparing an unordered container with 'std::equal' is order-dependent"); +} + +} // namespace clang::tidy::bugprone diff --git a/clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.h b/clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.h new file mode 100644 index 0000000000000..18b814315c80c --- /dev/null +++ b/clang-tools-extra/clang-tidy/bugprone/UnorderedEqualCompareCheck.h @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// 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_BUGPRONE_UNORDEREDEQUALCOMPARECHECK_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_UNORDEREDEQUALCOMPARECHECK_H + +#include "../ClangTidyCheck.h" + +namespace clang::tidy::bugprone { + +/// Flags uses of 'std::equal' to compare the ranges of two unordered +/// containers. The iteration order of unordered containers is unspecified, so +/// such a comparison is order-dependent; 'operator==' should be used instead. +/// +/// For the user-facing documentation see: +/// https://clang.llvm.org/extra/clang-tidy/checks/bugprone/unordered-equal-compare.html +class UnorderedEqualCompareCheck : public ClangTidyCheck { +public: + UnorderedEqualCompareCheck(StringRef Name, ClangTidyContext *Context); + void storeOptions(ClangTidyOptions::OptionMap &Opts) override; + void registerMatchers(ast_matchers::MatchFinder *Finder) override; + void check(const ast_matchers::MatchFinder::MatchResult &Result) override; + bool isLanguageVersionSupported(const LangOptions &LangOpts) const override { + return LangOpts.CPlusPlus; + } + std::optional<TraversalKind> getCheckTraversalKind() const override { + return TK_IgnoreUnlessSpelledInSource; + } + +private: + const std::vector<StringRef> ContainerNames; +}; + +} // namespace clang::tidy::bugprone + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_UNORDEREDEQUALCOMPARECHECK_H diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst index 69c3bcf67b8db..42d2fef07ef16 100644 --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -97,6 +97,13 @@ Improvements to clang-tidy New checks ^^^^^^^^^^ +- New :doc:`bugprone-unordered-equal-compare + <clang-tidy/checks/bugprone/unordered-equal-compare>` check. + + Flags uses of ``std::equal`` to compare the ranges of two unordered + containers (``std::unordered_set``, ``std::unordered_multiset``, + ``std::unordered_map`` and ``std::unordered_multimap``). + New check aliases ^^^^^^^^^^^^^^^^^ diff --git a/clang-tools-extra/docs/clang-tidy/checks/bugprone/unordered-equal-compare.rst b/clang-tools-extra/docs/clang-tidy/checks/bugprone/unordered-equal-compare.rst new file mode 100644 index 0000000000000..6cc8ecc51f56e --- /dev/null +++ b/clang-tools-extra/docs/clang-tidy/checks/bugprone/unordered-equal-compare.rst @@ -0,0 +1,31 @@ +.. title:: clang-tidy - bugprone-unordered-equal-compare + +bugprone-unordered-equal-compare +================================ + +Flags uses of ``std::equal`` to compare the ranges of two unordered containers +(``std::unordered_set``, ``std::unordered_multiset``, ``std::unordered_map`` and +``std::unordered_multimap``). + +The iteration order of an unordered container is unspecified, so two containers +holding the same elements may iterate them in a different order. Comparing their +ranges element by element with ``std::equal`` is therefore order-dependent and +can report equal containers as different. Use ``operator==`` instead, which +compares the containers as sets. + +.. code-block:: c++ + + std::unordered_set<int> a, b; + + bool wrong = std::equal(a.begin(), a.end(), b.begin()); // warning + bool ok = (a == b); + +Options +------- + +.. option:: Containers + + A semicolon-separated list of the fully-qualified names of the unordered + container class templates to flag. This allows out-of-tree containers such as + the Boost ones to be added. Defaults to + ``::std::unordered_set;::std::unordered_multiset;::std::unordered_map;::std::unordered_multimap``. diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst index 2a44dc78fbc89..0aec1bcf83de5 100644 --- a/clang-tools-extra/docs/clang-tidy/checks/list.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst @@ -179,6 +179,7 @@ Clang-Tidy Checks :doc:`bugprone-unhandled-self-assignment <bugprone/unhandled-self-assignment>`, :doc:`bugprone-unintended-char-ostream-output <bugprone/unintended-char-ostream-output>`, "Yes" :doc:`bugprone-unique-ptr-array-mismatch <bugprone/unique-ptr-array-mismatch>`, "Yes" + :doc:`bugprone-unordered-equal-compare <bugprone/unordered-equal-compare>`, :doc:`bugprone-unsafe-functions <bugprone/unsafe-functions>`, :doc:`bugprone-unsafe-to-allow-exceptions <bugprone/unsafe-to-allow-exceptions>`, :doc:`bugprone-unused-local-non-trivial-variable <bugprone/unused-local-non-trivial-variable>`, diff --git a/clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare-custom.cpp b/clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare-custom.cpp new file mode 100644 index 0000000000000..47395330ae65e --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare-custom.cpp @@ -0,0 +1,32 @@ +// RUN: %check_clang_tidy %s bugprone-unordered-equal-compare %t -- \ +// RUN: -config="{CheckOptions: {bugprone-unordered-equal-compare.Containers: '::boost::unordered_set'}}" + +namespace std { +template <class InputIt1, class InputIt2> +bool equal(InputIt1, InputIt1, InputIt2); + +template <class T> struct unordered_set { + struct iterator {}; + iterator begin() const; + iterator end() const; +}; +} // namespace std + +namespace boost { +template <class T> struct unordered_set { + struct iterator {}; + iterator begin() const; + iterator end() const; +}; +} // namespace boost + +// The custom container from the 'Containers' option is flagged. +void bad_boost(boost::unordered_set<int> &a, boost::unordered_set<int> &b) { + std::equal(a.begin(), a.end(), b.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +// The default std container is not in the configured list, so it is ignored. +void ok_std(std::unordered_set<int> &a, std::unordered_set<int> &b) { + std::equal(a.begin(), a.end(), b.begin()); +} diff --git a/clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare.cpp b/clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare.cpp new file mode 100644 index 0000000000000..070539681d472 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/bugprone/unordered-equal-compare.cpp @@ -0,0 +1,102 @@ +// RUN: %check_clang_tidy %s bugprone-unordered-equal-compare %t + +namespace std { +template <class InputIt1, class InputIt2> +bool equal(InputIt1, InputIt1, InputIt2); +template <class InputIt1, class InputIt2> +bool equal(InputIt1, InputIt1, InputIt2, InputIt2); + +template <class T> struct set { + struct iterator {}; + iterator begin() const; + iterator end() const; +}; +template <class T> struct unordered_set { + struct iterator {}; + iterator begin() const; + iterator end() const; + iterator cbegin() const; + iterator cend() const; +}; +template <class T> struct unordered_multiset { + struct iterator {}; + iterator begin() const; + iterator end() const; +}; +template <class K, class V> struct unordered_map { + struct iterator {}; + iterator begin() const; + iterator end() const; +}; +template <class K, class V> struct unordered_multimap { + struct iterator {}; + iterator begin() const; + iterator end() const; +}; +} // namespace std + +void bad_set(std::unordered_set<int> &a, std::unordered_set<int> &b) { + std::equal(a.begin(), a.end(), b.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +void bad_multiset(std::unordered_multiset<int> &a, + std::unordered_multiset<int> &b) { + std::equal(a.begin(), a.end(), b.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +void bad_map(std::unordered_map<int, int> &a, std::unordered_map<int, int> &b) { + std::equal(a.begin(), a.end(), b.begin(), b.end()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +void bad_multimap(std::unordered_multimap<int, int> &a, + std::unordered_multimap<int, int> &b) { + std::equal(a.begin(), a.end(), b.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +// The const iterator accessors are matched too. +void bad_cbegin(std::unordered_set<int> &a, std::unordered_set<int> &b) { + std::equal(a.cbegin(), a.cend(), b.cbegin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +// Only one argument has to come from an unordered container. +void bad_one_side(std::unordered_set<int> &a, std::set<int>::iterator first, + std::set<int>::iterator last) { + std::equal(first, last, a.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +// A concrete call inside a template still fires, and the explicit instantiation +// must not report it a second time. +template <class T> +bool in_template(std::unordered_set<int> &a, std::unordered_set<int> &b) { + return std::equal(a.begin(), a.end(), b.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:10: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} +template bool in_template<int>(std::unordered_set<int> &, + std::unordered_set<int> &); + +// A dependent container type isn't matched as written, so nothing is reported +// even once the template is instantiated with an unordered container. +template <class C> +bool dependent(C &a, C &b) { + return std::equal(a.begin(), a.end(), b.begin()); +} +void use_dependent(std::unordered_set<int> &a, std::unordered_set<int> &b) { + dependent(a, b); +} + +// The warning still fires through a macro, pointing at the expansion. +#define EQUAL_BEGIN(a, b) std::equal(a.begin(), a.end(), b.begin()) +void via_macro(std::unordered_set<int> &a, std::unordered_set<int> &b) { + EQUAL_BEGIN(a, b); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: comparing an unordered container with 'std::equal' is order-dependent [bugprone-unordered-equal-compare] +} + +void ok_ordered(std::set<int> &a, std::set<int> &b) { + std::equal(a.begin(), a.end(), b.begin()); +} _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
