https://github.com/steakhal updated https://github.com/llvm/llvm-project/pull/202580
From 82161c448dddaf34dc5dd35cc33305820320e654 Mon Sep 17 00:00:00 2001 From: Balazs Benics <[email protected]> Date: Tue, 9 Jun 2026 11:50:22 +0100 Subject: [PATCH 1/2] [llvm][ADT] Make ImmutableList conform the fwd iterator concept We missed post increment and a couple of typedefs. This would enable llvm algorithms like filter_range, etc. --- .../BlockInCriticalSectionChecker.cpp | 13 ----- llvm/include/llvm/ADT/ImmutableList.h | 13 +++++ llvm/unittests/ADT/ImmutableListTest.cpp | 56 +++++++++++++++++++ 3 files changed, 69 insertions(+), 13 deletions(-) diff --git a/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp index 354d4c99b2fbe..03c576270797b 100644 --- a/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/BlockInCriticalSectionChecker.cpp @@ -282,19 +282,6 @@ class BlockInCriticalSectionChecker : public Checker<check::PostCall> { REGISTER_LIST_WITH_PROGRAMSTATE(ActiveCritSections, CritSectionMarker) -// Iterator traits for ImmutableList data structure -// that enable the use of STL algorithms. -// TODO: Move these to llvm::ImmutableList when overhauling immutable data -// structures for proper iterator concept support. -template <> -struct std::iterator_traits<llvm::ImmutableList<CritSectionMarker>::iterator> { - using iterator_category = std::forward_iterator_tag; - using value_type = CritSectionMarker; - using difference_type = std::ptrdiff_t; - using reference = CritSectionMarker &; - using pointer = CritSectionMarker *; -}; - std::optional<MutexDescriptor> BlockInCriticalSectionChecker::checkDescriptorMatch(const CallEvent &Call, CheckerContext &C, diff --git a/llvm/include/llvm/ADT/ImmutableList.h b/llvm/include/llvm/ADT/ImmutableList.h index bbf0a96464e58..24a4b732cd090 100644 --- a/llvm/include/llvm/ADT/ImmutableList.h +++ b/llvm/include/llvm/ADT/ImmutableList.h @@ -17,7 +17,9 @@ #include "llvm/ADT/FoldingSet.h" #include "llvm/Support/Allocator.h" #include <cassert> +#include <cstddef> #include <cstdint> +#include <iterator> #include <new> namespace llvm { @@ -86,10 +88,21 @@ class ImmutableList { const ImmutableListImpl<T>* L = nullptr; public: + using iterator_category = std::forward_iterator_tag; + using value_type = std::remove_reference_t<T>; + using difference_type = std::ptrdiff_t; + using pointer = const value_type *; + using reference = const value_type &; + iterator() = default; iterator(ImmutableList l) : L(l.getInternalPointer()) {} iterator& operator++() { L = L->getTail(); return *this; } + iterator operator++(int) { + iterator Tmp = *this; + ++*this; + return Tmp; + } bool operator==(const iterator& I) const { return L == I.L; } bool operator!=(const iterator& I) const { return L != I.L; } const value_type& operator*() const { return L->getHead(); } diff --git a/llvm/unittests/ADT/ImmutableListTest.cpp b/llvm/unittests/ADT/ImmutableListTest.cpp index 2da0ca65d1a4f..970c3d6cd998d 100644 --- a/llvm/unittests/ADT/ImmutableListTest.cpp +++ b/llvm/unittests/ADT/ImmutableListTest.cpp @@ -7,7 +7,11 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/ImmutableList.h" +#include "llvm/ADT/STLExtras.h" +#include "gmock/gmock.h" #include "gtest/gtest.h" +#include <algorithm> +#include <vector> using namespace llvm; @@ -269,4 +273,56 @@ TEST_F(ImmutableListTest, LongListOrderingTest) { static_assert(std::is_trivially_copyable_v<ImmutableList<Wrapper<long>>>, "trivially copyable"); +// Verify ImmutableList<T>::iterator satisfies the std::iterator_traits +// contract: +using IntListIter = ImmutableList<Wrapper<int>>::iterator; +static_assert( + std::is_same_v<std::iterator_traits<IntListIter>::iterator_category, + std::forward_iterator_tag>); +static_assert(std::is_same_v<std::iterator_traits<IntListIter>::value_type, + Wrapper<int>>); +static_assert(std::is_same_v<std::iterator_traits<IntListIter>::difference_type, + std::ptrdiff_t>); +static_assert(std::is_same_v<std::iterator_traits<IntListIter>::pointer, + const Wrapper<int> *>); +static_assert(std::is_same_v<std::iterator_traits<IntListIter>::reference, + const Wrapper<int> &>); + +using RefListIter = ImmutableList<const Unmodifiable &>::iterator; +static_assert( + std::is_same_v<std::iterator_traits<RefListIter>::iterator_category, + std::forward_iterator_tag>); +static_assert(std::is_same_v<std::iterator_traits<RefListIter>::value_type, + const Unmodifiable>); +static_assert(std::is_same_v<std::iterator_traits<RefListIter>::pointer, + const Unmodifiable *>); +static_assert(std::is_same_v<std::iterator_traits<RefListIter>::reference, + const Unmodifiable &>); + +TEST_F(ImmutableListTest, IteratorPostIncrementTest) { + ImmutableList<Wrapper<int>>::Factory f; + ImmutableList<Wrapper<int>> L = + f.add(5, f.add(4, f.add(3, f.getEmptyList()))); + + auto It = L.begin(); + EXPECT_EQ(5, *It); + + auto Old = It++; + EXPECT_EQ(5, *Old); + EXPECT_EQ(4, *It); + EXPECT_TRUE(Old != It); +} + +TEST_F(ImmutableListTest, IteratorPostIncrementInLoopTest) { + ImmutableList<Wrapper<int>>::Factory f; + ImmutableList<Wrapper<int>> L = + f.add(5, f.add(4, f.add(3, f.getEmptyList()))); + + std::vector<int> Values; + for (auto I = L.begin(), E = L.end(); I != E; I++) + Values.push_back(*I); + + EXPECT_THAT(Values, testing::ElementsAre(5, 4, 3)); +} + } // namespace From 4f01e411a6c7466759494cf43bb9f81344ea9351 Mon Sep 17 00:00:00 2001 From: Balazs Benics <[email protected]> Date: Wed, 10 Jun 2026 09:11:44 +0100 Subject: [PATCH 2/2] Add filter_range test --- llvm/unittests/ADT/ImmutableListTest.cpp | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/llvm/unittests/ADT/ImmutableListTest.cpp b/llvm/unittests/ADT/ImmutableListTest.cpp index 970c3d6cd998d..3046c5da54651 100644 --- a/llvm/unittests/ADT/ImmutableListTest.cpp +++ b/llvm/unittests/ADT/ImmutableListTest.cpp @@ -325,4 +325,14 @@ TEST_F(ImmutableListTest, IteratorPostIncrementInLoopTest) { EXPECT_THAT(Values, testing::ElementsAre(5, 4, 3)); } +TEST_F(ImmutableListTest, FilterRangeCompat) { + ImmutableList<Wrapper<int>>::Factory f; + ImmutableList<Wrapper<int>> L = + f.add(5, f.add(4, f.add(3, f.getEmptyList()))); + + auto IsOdd = [](int Val) { return Val % 2; }; + auto OddElements = llvm::make_filter_range(L, IsOdd); + EXPECT_THAT(OddElements, testing::ElementsAre(5, 3)); +} + } // namespace _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
