On Thu, Jun 12, 2025 at 7:33 PM Patrick Palka <ppa...@redhat.com> wrote:
> On Thu, 12 Jun 2025, Patrick Palka wrote: > > > Changes in v4: > > * Don't pass a projection function throughout the helpers, instead > > create a pass a composite predicate via __make_comp_proj. > LGTM. > > > > -- >8 -- > > > > As with the previous patch, this patch reimplements ranges::sort > > directly instead of incorrectly forwarding to std::sort. In addition to > > the compatibility changes listed in the previous patch we also: > > > > - use ranges::iter_swap instead of std::iter_swap > > - use ranges::move_backward instead of std::move_backward > > - use __bit_width and __to_unsigned_like instead of __lg > > > > PR libstdc++/100795 > > PR libstdc++/118209 > > > > libstdc++-v3/ChangeLog: > > > > * include/bits/max_size_type.h (__bit_width): New explicit > > specialization for __max_size_type. > > * include/bits/ranges_algo.h (__detail::__move_median_to_first): > > New, based on the stl_algo.h implementation. > > (__detail::__unguarded_liner_insert): Likewise. > > (__detail::__insertion_sort): Likewise. > > (__detail::__sort_threshold): Likewise. > > (__detail::__unguarded_insertion_sort): Likewise. > > (__detail::__final_insertion_sort): Likewise. > > (__detail::__unguarded_partition): Likewise. > > (__detail::__unguarded_partition_pivot): Likewise. > > (__detail::__heap_select): Likewise. > > (__detail::__partial_sort): Likewise. > > (__detail::__introsort_loop): Likewise. > > (__sort_fn::operator()): Reimplement in terms of the above. > > * libstdc++-v3/testsuite/25_algorithms/sort/118209.cc: New test. > > * libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc > > (test03): New test. > > --- > > libstdc++-v3/include/bits/max_size_type.h | 11 ++ > > libstdc++-v3/include/bits/ranges_algo.h | 167 +++++++++++++++++- > > .../testsuite/25_algorithms/sort/118209.cc | 23 +++ > > .../25_algorithms/sort/constrained.cc | 31 ++++ > > 4 files changed, 228 insertions(+), 4 deletions(-) > > create mode 100644 libstdc++-v3/testsuite/25_algorithms/sort/118209.cc > > > > diff --git a/libstdc++-v3/include/bits/max_size_type.h > b/libstdc++-v3/include/bits/max_size_type.h > > index e602b1b4bee5..73a6d141d5bc 100644 > > --- a/libstdc++-v3/include/bits/max_size_type.h > > +++ b/libstdc++-v3/include/bits/max_size_type.h > > @@ -36,6 +36,7 @@ > > > > #if __cplusplus > 201703L && __cpp_lib_concepts > > #include <ext/numeric_traits.h> > > +#include <bit> // __bit_width > > #include <numbers> > > > > // This header implements unsigned and signed integer-class types (as > per > > @@ -818,6 +819,16 @@ namespace ranges > > { return min(); } > > }; > > > > + template<> > > + inline constexpr int > > + __bit_width(ranges::__detail::__max_size_type __x) noexcept > > + { > > + if (__x._M_msb) > > + return numeric_limits<ranges::__detail::__max_size_type>::digits; > > + else > > + return std::__bit_width(__x._M_val); > > + } > > + > > _GLIBCXX_END_NAMESPACE_VERSION > > } // namespace > > > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h > b/libstdc++-v3/include/bits/ranges_algo.h > > index 4f10501956a7..9f94c6b1d57e 100644 > > --- a/libstdc++-v3/include/bits/ranges_algo.h > > +++ b/libstdc++-v3/include/bits/ranges_algo.h > > @@ -32,6 +32,7 @@ > > > > #if __cplusplus > 201703L > > > > +#include <bit> // __bit_width > > #if __cplusplus > 202002L > > #include <optional> > > #endif > > @@ -2169,6 +2170,153 @@ namespace ranges > > > > inline constexpr __is_heap_fn is_heap{}; > > > > + namespace __detail > > + { > > + template<typename _Iter, typename _Comp> > > + constexpr void > > + __move_median_to_first(_Iter __result, _Iter __a, _Iter __b, > _Iter __c, > > + _Comp __comp) > > + { > > + if (std::__invoke(__comp, *__a, *__b)) > > Similarly, these __invoke calls throughout are unnecessary too. > Fixed below. > > -- >8 -- > > PR libstdc++/100795 > PR libstdc++/118209 > > libstdc++-v3/ChangeLog: > > * include/bits/max_size_type.h (__bit_width): New explicit > specializatino for __max_size_type. > * include/bits/ranges_algo.h (__detail::__move_median_to_first): > New, based on the stl_algo.h implementation. > (__detail::__unguarded_liner_insert): Likewise. > (__detail::__insertion_sort): Likewise. > (__detail::__sort_threshold): Likewise. > (__detail::__unguarded_insertion_sort): Likewise. > (__detail::__final_insertion_sort): Likewise. > (__detail::__unguarded_partition): Likewise. > (__detail::__unguarded_partition_pivot): Likewise. > (__detail::__heap_select): Likewise. > (__detail::__partial_sort): Likewise. > (__detail::__introsort_loop): Likewise. > (__sort_fn::operator()): Reimplement in terms of the above. > * libstdc++-v3/testsuite/25_algorithms/sort/118209.cc: New test. > * libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc > (test03): New test. > --- > libstdc++-v3/include/bits/max_size_type.h | 11 ++ > libstdc++-v3/include/bits/ranges_algo.h | 167 +++++++++++++++++- > .../testsuite/25_algorithms/sort/118209.cc | 23 +++ > .../25_algorithms/sort/constrained.cc | 31 ++++ > 4 files changed, 228 insertions(+), 4 deletions(-) > create mode 100644 libstdc++-v3/testsuite/25_algorithms/sort/118209.cc > > diff --git a/libstdc++-v3/include/bits/max_size_type.h > b/libstdc++-v3/include/bits/max_size_type.h > index e602b1b4bee5..73a6d141d5bc 100644 > --- a/libstdc++-v3/include/bits/max_size_type.h > +++ b/libstdc++-v3/include/bits/max_size_type.h > @@ -36,6 +36,7 @@ > > #if __cplusplus > 201703L && __cpp_lib_concepts > #include <ext/numeric_traits.h> > +#include <bit> // __bit_width > #include <numbers> > > // This header implements unsigned and signed integer-class types (as per > @@ -818,6 +819,16 @@ namespace ranges > { return min(); } > }; > > + template<> > + inline constexpr int > + __bit_width(ranges::__detail::__max_size_type __x) noexcept > + { > + if (__x._M_msb) > + return numeric_limits<ranges::__detail::__max_size_type>::digits; > + else > + return std::__bit_width(__x._M_val); > + } > + > _GLIBCXX_END_NAMESPACE_VERSION > } // namespace > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h > b/libstdc++-v3/include/bits/ranges_algo.h > index 735142a6c702..cc182d110b30 100644 > --- a/libstdc++-v3/include/bits/ranges_algo.h > +++ b/libstdc++-v3/include/bits/ranges_algo.h > @@ -32,6 +32,7 @@ > > #if __cplusplus > 201703L > > +#include <bit> // __bit_width > #if __cplusplus > 202002L > #include <optional> > #endif > @@ -2168,6 +2169,153 @@ namespace ranges > > inline constexpr __is_heap_fn is_heap{}; > > + namespace __detail > + { > + template<typename _Iter, typename _Comp> > + constexpr void > + __move_median_to_first(_Iter __result, _Iter __a, _Iter __b, _Iter > __c, > + _Comp __comp) > + { > + if (__comp(*__a, *__b)) > + { > + if (__comp(*__b, *__c)) > + ranges::iter_swap(__result, __b); > + else if (__comp(*__a, *__c)) > + ranges::iter_swap(__result, __c); > + else > + ranges::iter_swap(__result, __a); > + } > + else if (__comp(*__a, *__c)) > + ranges::iter_swap(__result, __a); > + else if (__comp(*__b, *__c)) > + ranges::iter_swap(__result, __c); > + else > + ranges::iter_swap(__result, __b); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __unguarded_linear_insert(_Iter __last, _Comp __comp) > + { > + iter_value_t<_Iter> __val = ranges::iter_move(__last); > + _Iter __next = __last; > + --__next; > + while (__comp(__val, *__next)) > + { > + *__last = ranges::iter_move(__next); > + __last = __next; > + --__next; > + } > + *__last = std::move(__val); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __insertion_sort(_Iter __first, _Iter __last, _Comp __comp) > + { > + if (__first == __last) return; > + > + for (_Iter __i = __first + 1; __i != __last; ++__i) > + { > + if (__comp(*__i, *__first)) > + { > + iter_value_t<_Iter> __val = ranges::iter_move(__i); > + ranges::move_backward(__first, __i, __i + 1); > + *__first = std::move(__val); > + } > + else > + __detail::__unguarded_linear_insert(__i, __comp); > + } > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __unguarded_insertion_sort(_Iter __first, _Iter __last, _Comp > __comp) > + { > + for (_Iter __i = __first; __i != __last; ++__i) > + __detail::__unguarded_linear_insert(__i, __comp); > + } > + > + inline constexpr int __sort_threshold = 16; > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __final_insertion_sort(_Iter __first, _Iter __last, _Comp __comp) > + { > + if (__last - __first > __sort_threshold) > + { > + __detail::__insertion_sort(__first, __first + > __sort_threshold, __comp); > + __detail::__unguarded_insertion_sort(__first + > __sort_threshold, __last, > + __comp); > + } > + else > + __detail::__insertion_sort(__first, __last, __comp); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr _Iter > + __unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot, > _Comp __comp) > + { > + while (true) > + { > + while (__comp(*__first, *__pivot)) > + ++__first; > + --__last; > + while (__comp(*__pivot, *__last)) > + --__last; > + if (!(__first < __last)) > + return __first; > + ranges::iter_swap(__first, __last); > + ++__first; > + } > + } > + > + template<typename _Iter, typename _Comp> > + constexpr _Iter > + __unguarded_partition_pivot(_Iter __first, _Iter __last, _Comp > __comp) > + { > + _Iter __mid = __first + (__last - __first) / 2; > + __detail::__move_median_to_first(__first, __first + 1, __mid, > __last - 1, __comp); > + return __detail::__unguarded_partition(__first + 1, __last, > __first, __comp); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __heap_select(_Iter __first, _Iter __middle, _Iter __last, _Comp > __comp) > + { > + ranges::make_heap(__first, __middle, __comp); > + for (_Iter __i = __middle; __i < __last; ++__i) > + if (__comp(*__i, *__first)) > + __detail::__pop_heap(__first, __middle, __i, __comp); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __partial_sort(_Iter __first, _Iter __middle, _Iter __last, _Comp > __comp) > + { > + __detail::__heap_select(__first, __middle, __last, __comp); > + ranges::sort_heap(__first, __middle, __comp); > + } > + > + template<typename _Iter, typename _Comp> > + constexpr void > + __introsort_loop(_Iter __first, _Iter __last, unsigned > __depth_limit, _Comp __comp) > + { > + while (__last - __first > __sort_threshold) > + { > + if (__depth_limit == 0) > + { > + __detail::__partial_sort(__first, __last, __last, __comp); > + return; > + } > + --__depth_limit; > + _Iter __cut = __detail::__unguarded_partition_pivot(__first, > __last, __comp); > + __detail::__introsort_loop(__cut, __last, __depth_limit, > __comp); > + __last = __cut; > + } > + } > + } // namespace __detail > + > struct __sort_fn > { > template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent, > @@ -2177,10 +2325,21 @@ namespace ranges > operator()(_Iter __first, _Sent __last, > _Comp __comp = {}, _Proj __proj = {}) const > { > - auto __lasti = ranges::next(__first, __last); > - _GLIBCXX_STD_A::sort(std::move(__first), __lasti, > - __detail::__make_comp_proj(__comp, __proj)); > - return __lasti; > + if constexpr (!same_as<_Iter, _Sent>) > + return (*this)(__first, ranges::next(__first, __last), > + std::move(__comp), std::move(__proj)); > + else > + { > + if (__first != __last) > + { > + auto __comp_proj = __detail::__make_comp_proj(__comp, > __proj); > + auto __n = __detail::__to_unsigned_like(__last - __first); > + unsigned __depth_limit = (std::__bit_width(__n) - 1) * 2; > + __detail::__introsort_loop(__first, __last, __depth_limit, > __comp_proj); > + __detail::__final_insertion_sort(__first, __last, > __comp_proj); > + } > + return __last; > + } > } > > template<random_access_range _Range, > diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc > b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc > new file mode 100644 > index 000000000000..6dedbde75173 > --- /dev/null > +++ b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc > @@ -0,0 +1,23 @@ > +// PR libstdc++ - ranges::sort doesn't use iter_move, cannot sort zip of > move-only type > +// { dg-do compile { target c++23 } } > + > +#include <algorithm> > +#include <ranges> > +#include <vector> > + > +struct F { > + int a = -1; > + explicit F(int d) : a(d) { } > + F(const F&) = delete; > + F(F&& o) : a(o.a) { } > + void operator=(const F&) = delete; > + F& operator=(F&& o) { return *this; } > + auto operator<=>(const F&) const = default; > +}; > + > +int main () { > + int a[] = {3,2,1}; > + std::vector<F> v(a, a+3); > + std::ranges::sort(v); // OK > + std::ranges::sort(std::views::zip(v)); // didn't compile > +} > diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc > b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc > index 82754af96430..930dbd77a376 100644 > --- a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc > +++ b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc > @@ -20,6 +20,7 @@ > > #include <algorithm> > #include <random> > +#include <ranges> > #include <vector> > #include <testsuite_hooks.h> > #include <testsuite_iterators.h> > @@ -72,9 +73,39 @@ test02() > && ranges::equal(x, y, {}, &X::i, &X::i)); > } > > +constexpr bool > +test03() > +{ > + // PR libstdc++/100795 - ranges::sort should not use std::sort directly > +#if __SIZEOF_INT128__ > + auto v = std::views::iota(__int128(0), __int128(20)); > +#else > + auto v = std::views::iota(0ll, 20ll); > +#endif > + > + int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17}; > + auto w = v | std::views::transform([&](auto i) -> int& { return > storage[i]; }); > + using type = decltype(w); > + using cat = > std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category; > + static_assert( std::same_as<cat, std::output_iterator_tag> ); > + static_assert( std::ranges::random_access_range<type> ); > + > + ranges::sort(w); > + VERIFY( ranges::equal(w, v) ); > + > + ranges::sort(w, std::ranges::greater{}); > + VERIFY( ranges::equal(w, v | std::views::reverse) ); > + > + ranges::sort(w, std::ranges::greater{}, std::negate{}); > + VERIFY( ranges::equal(w, v) ); > + > + return true; > +} > + > int > main() > { > test01(); > static_assert(test02()); > + static_assert(test03()); > } > -- > 2.50.0.rc2 > >