https://gcc.gnu.org/g:76ad28b11266606fcc1571d0ef92d3f2ef402bfb
commit r16-6749-g76ad28b11266606fcc1571d0ef92d3f2ef402bfb Author: Tomasz Kamiński <[email protected]> Date: Tue Jan 13 16:29:42 2026 +0100 libstdc++: Fix handling iterators with proxy subscript in heap algorithms. This patch replaces uses of subscripts in heap algorithms, that where introduced in r16-4100-gaaeca77a79a9a8 with dereference of advanced iterators. The Cpp17RandomAccessIterator requirements, allows operator[] to return any type that is convertible to reference, however user-provided comparators are required only to accept result of dereferencing the iterator (i.e. reference directly). This is visible, when comparator defines operator() for which template arguments can be deduduced from reference (which will fail on proxy) or that accepts types convertible from reference (see included tests). For test we introduce a new proxy_random_access_iterator_wrapper iterator in testsuite_iterators.h, that returns a proxy type from subscript operator. This is separate type (instead of additional template argument and aliases), as it used for test that work with C++98. libstdc++-v3/ChangeLog: * include/bits/stl_heap.h (std::__is_heap_until, std::__push_heap) (std::__adjust_heap): Replace subscript with dereference of advanced iterator. * testsuite/util/testsuite_iterators.h (__gnu_test::subscript_proxy) (__gnu_test::proxy_random_access_iterator_wrapper): Define. * testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc: New test. Reviewed-by: Jonathan Wakely <[email protected]> Signed-off-by: Tomasz Kamiński <[email protected]> Diff: --- libstdc++-v3/include/bits/stl_heap.h | 8 +- .../sort_heap/check_proxy_brackets.cc | 67 +++++++ libstdc++-v3/testsuite/util/testsuite_iterators.h | 198 +++++++++++++++++++++ 3 files changed, 269 insertions(+), 4 deletions(-) diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h index c64553e25718..8c5c5df5266d 100644 --- a/libstdc++-v3/include/bits/stl_heap.h +++ b/libstdc++-v3/include/bits/stl_heap.h @@ -85,7 +85,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Distance __parent = 0; for (_Distance __child = 1; __child < __n; ++__child) { - if (__comp(__first[__parent], __first[__child])) + if (__comp(*(__first + __parent), *(__first + __child))) return __child; if ((__child & 1) == 0) ++__parent; @@ -143,7 +143,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION _Compare& __comp) { _Distance __parent = (__holeIndex - 1) / 2; - while (__holeIndex > __topIndex && __comp(__first[__parent], __value)) + while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) { *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __parent)); __holeIndex = __parent; @@ -233,8 +233,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION while (__secondChild < (__len - 1) / 2) { __secondChild = 2 * (__secondChild + 1); - if (__comp(__first[__secondChild], - __first[__secondChild - 1])) + if (__comp(*(__first + __secondChild), + *(__first + _Distance(__secondChild - 1)))) __secondChild--; *(__first + __holeIndex) = _GLIBCXX_MOVE(*(__first + __secondChild)); __holeIndex = __secondChild; diff --git a/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc b/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc new file mode 100644 index 000000000000..c556c26dfa8d --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/sort_heap/check_proxy_brackets.cc @@ -0,0 +1,67 @@ +// { dg-do run } + +#undef _GLIBCXX_CONCEPT_CHECKS + +#include <algorithm> +#include <testsuite_hooks.h> +#include <testsuite_iterators.h> +#include <utility> + +using __gnu_test::test_container; +using __gnu_test::proxy_random_access_iterator_wrapper; + +typedef std::pair<int, int> V; +typedef test_container<V, proxy_random_access_iterator_wrapper> Container; + +struct Deduced +{ + template<typename A, typename B> + bool operator()(const std::pair<A, B>& lhs, + const std::pair<A, B>& rhs) const + { return lhs.first < rhs.first; } +}; + +struct Conversion +{ + struct First + { + First(const V& p) : v(p.first) + {} + + int v; + }; + + bool operator()(First lhs, First rhs) const + { return lhs.v < rhs.v; } +}; + +template<typename Cmp> +void +test01(Cmp cmp) +{ + V s1[] = { V(0, 10), V(8, 18), V(6, 16), V(7, 17), V(9, 19), + V(5, 15), V(4, 14), V(3, 13), V(2, 12), V(1, 11) }; + const int N = sizeof(s1) / sizeof(V); + Container con(s1, s1 + N); + + std::make_heap(con.begin(), con.end() - std::ptrdiff_t(2), cmp); + std::push_heap(con.begin(), con.end() - std::ptrdiff_t(1), cmp); + std::push_heap(con.begin(), con.end(), cmp); +#if __cplusplus >= 201103L + (void)std::is_heap_until(con.begin(), con.end(), cmp); +#endif + std::sort_heap(con.begin(), con.end(), cmp); + for(int i = 0; i < N; ++i) + { + VERIFY( s1[i].first == i ); + VERIFY( s1[i].second == 10 + i ); + } +} + +int +main() +{ + test01(Deduced()); + test01(Conversion()); + return 0; +} diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h index 95589b2626d2..caede49e41b5 100644 --- a/libstdc++-v3/testsuite/util/testsuite_iterators.h +++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h @@ -664,6 +664,204 @@ namespace __gnu_test #endif + template<typename T> + struct subscript_proxy + { + _GLIBCXX_CONSTEXPR + operator T&() const + { return *ptr; } + + _GLIBCXX14_CONSTEXPR + subscript_proxy& operator=(const T& val) + { + *ptr = val; + return *this; + } + + T* ptr; + }; + + template<typename T> + struct subscript_proxy<const T> + { + _GLIBCXX_CONSTEXPR + operator const T&() const + { return *ptr; } + + const T* ptr; + }; + + /** + * @brief random_access_iterator wrapper for pointer, + * that returns proxy from subscript. + * + * This class takes a pointer and wraps it to provide exactly + * the requirements of a random_access_iterator. It should not be + * instantiated directly, but generated from a test_container + */ + template<class T> + struct proxy_random_access_iterator_wrapper + : public bidirectional_iterator_wrapper<T> + { + typedef BoundsContainer<T> ContainerType; + typedef std::random_access_iterator_tag iterator_category; + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper(T* _ptr, ContainerType* SharedInfo_in) + : bidirectional_iterator_wrapper<T>(_ptr, SharedInfo_in) + { } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper() + : bidirectional_iterator_wrapper<T>() + { } + +#if __cplusplus >= 201103L + proxy_random_access_iterator_wrapper( + const proxy_random_access_iterator_wrapper&) = default; + + proxy_random_access_iterator_wrapper& + operator=(const proxy_random_access_iterator_wrapper&) = default; +#endif + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper& + operator++() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr < this->SharedInfo->last); + this->ptr++; + return *this; + } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper + operator++(int) + { + proxy_random_access_iterator_wrapper<T> tmp = *this; + ++*this; + return tmp; + } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper& + operator--() + { + ITERATOR_VERIFY(this->SharedInfo && this->ptr > this->SharedInfo->first); + this->ptr--; + return *this; + } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper + operator--(int) + { + proxy_random_access_iterator_wrapper<T> tmp = *this; + --*this; + return tmp; + } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper& + operator+=(std::ptrdiff_t n) + { + if(n > 0) + { + ITERATOR_VERIFY(n <= this->SharedInfo->last - this->ptr); + this->ptr += n; + } + else + { + ITERATOR_VERIFY(-n <= this->ptr - this->SharedInfo->first); + this->ptr += n; + } + return *this; + } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper& + operator-=(std::ptrdiff_t n) + { return *this += -n; } + + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper + operator-(std::ptrdiff_t n) const + { + proxy_random_access_iterator_wrapper<T> tmp = *this; + return tmp -= n; + } + + _GLIBCXX14_CONSTEXPR + std::ptrdiff_t + operator-(const proxy_random_access_iterator_wrapper<T>& in) const + { + ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo); + return this->ptr - in.ptr; + } + + _GLIBCXX14_CONSTEXPR + subscript_proxy<T> + operator[](std::ptrdiff_t n) const + { + subscript_proxy<T> tmp = { *this + n }; + return tmp; + } + +#if __cplusplus >= 201103L + // Ensure that the iterator's difference_type is always used. + template<typename D> void operator+=(D) = delete; + template<typename D> void operator-=(D) = delete; + template<typename D> void operator[](D) const = delete; + template<typename D> + typename std::enable_if<std::is_integral<D>::value>::type + operator-(D) const = delete; +#endif + + _GLIBCXX14_CONSTEXPR + bool operator<(const proxy_random_access_iterator_wrapper<T>& in) const + { + ITERATOR_VERIFY(this->SharedInfo == in.SharedInfo); + return this->ptr < in.ptr; + } + + _GLIBCXX14_CONSTEXPR + bool operator>(const proxy_random_access_iterator_wrapper<T>& in) const + { + return in < *this; + } + + _GLIBCXX14_CONSTEXPR + bool operator>=(const proxy_random_access_iterator_wrapper<T>& in) const + { + return !(*this < in); + } + + _GLIBCXX14_CONSTEXPR + bool operator<=(const proxy_random_access_iterator_wrapper<T>& in) const + { + return !(*this > in); + } + }; + + template<typename T> + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper<T> + operator+(proxy_random_access_iterator_wrapper<T> it, std::ptrdiff_t n) + { return it += n; } + + template<typename T> + _GLIBCXX14_CONSTEXPR + proxy_random_access_iterator_wrapper<T> + operator+(std::ptrdiff_t n, proxy_random_access_iterator_wrapper<T> it) + { return it += n; } + +#if __cplusplus >= 201103L + // Ensure that the iterator's difference_type is always used. + template<typename T, typename D> + void operator+(proxy_random_access_iterator_wrapper<T>, D) = delete; + template<typename T, typename D> + void operator+(D, proxy_random_access_iterator_wrapper<T>) = delete; +#endif + /** * @brief A container-type class for holding iterator wrappers * test_container takes two parameters, a class T and an iterator
