On Mon, 30 Jun 2025 at 22:16, Patrick Palka <ppa...@redhat.com> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
>
> Btw, any thoughts on PR105611 which reports std::shift_left/right's use
> of the three-parameter version of ranges::next (on legacy iterators) is
> sketchy? Should we define a three-parameter std::__next analog for
> legacy iterators and use that instead?
I suppose we could do, but I find it hard to care about the corner
cases where ranges::next isn't optimal.
This patch for the ranges shift algos is OK for trunk (two comments
below, but they aren't asking for changes).
>
> -- >8 --
>
> The implementation is essentially a copy of std::shift_left/right
> (defined directly above) with the following changes:
>
> - check bidirectional_iterator instead of iterator_category
> - for shift_left, return {__first, X} instead of X
> - for shift_right, return {X, ranges::next(__first, __last)} instead of X
> - use the Ranges versions of move_backward, move and iter_swap
> - don't bother std::move'ing any iterators, it's unnecessary since all
> iterators are forward, makes the code less readable, and introduces
> subtle use-after-move bugs in some code paths
>
> In passing guard the std::shift_left/right implementations with
> __glibcxx_shift as well.
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h (shift_left, shift_right): Guard
> with __glibcxx_shift >= 201806L.
> (ranges::__shift_left_fn, ranges::shift_left): Define for C++23.
> (ranges::__shift_right_fn, ranges::shift_right): Likewise.
> * include/bits/version.def (shift): Update for C++23.
> * include/bits/version.h: Regenerate.
> * testsuite/25_algorithms/shift_left/constrained.cc: New test,
> based off of 1.cc.
> * testsuite/25_algorithms/shift_right/constrained.cc: New test,
> based off of 1.cc.
> ---
> libstdc++-v3/include/bits/ranges_algo.h | 121 ++++++++++++++++++
> libstdc++-v3/include/bits/version.def | 4 +
> libstdc++-v3/include/bits/version.h | 7 +-
> .../25_algorithms/shift_left/constrained.cc | 105 +++++++++++++++
> .../25_algorithms/shift_right/constrained.cc | 104 +++++++++++++++
> 5 files changed, 340 insertions(+), 1 deletion(-)
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
> create mode 100644
> libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> b/libstdc++-v3/include/bits/ranges_algo.h
> index 5aca6e8d864d..9bb84332d8e1 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -4261,6 +4261,7 @@ namespace ranges
> #endif // __glibcxx_ranges_fold
> } // namespace ranges
>
> +#if __glibcxx_shift >= 201806L // C++ >= 20
> template<typename _ForwardIterator>
> constexpr _ForwardIterator
> shift_left(_ForwardIterator __first, _ForwardIterator __last,
> @@ -4351,6 +4352,126 @@ namespace ranges
> }
> }
> }
> +#endif
> +
> +namespace ranges
> +{
> +#if __glibcxx_shift >= 202202L // C++ >= 23
> + struct __shift_left_fn
> + {
> + template<permutable _Iter, sentinel_for<_Iter> _Sent>
> + constexpr subrange<_Iter>
> + operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n)
> const
> + {
> + __glibcxx_assert(__n >= 0);
> + if (__n == 0)
> + return {__first, ranges::next(__first, __last)};
> +
> + auto __mid = ranges::next(__first, __n, __last);
> + if (__mid == __last)
> + return {__first, __first};
> + return {__first, ranges::move(__mid, __last, __first).out};
> + }
> +
> + template<forward_range _Range>
> + requires permutable<iterator_t<_Range>>
> + constexpr borrowed_subrange_t<_Range>
> + operator()(_Range&& __r, range_difference_t<_Range> __n) const
> + { return (*this)(ranges::begin(__r), ranges::end(__r), __n); }
> + };
> +
> + inline constexpr __shift_left_fn shift_left{};
> +
> + struct __shift_right_fn
> + {
> + template<permutable _Iter, sentinel_for<_Iter> _Sent>
> + constexpr subrange<_Iter>
> + operator()(_Iter __first, _Sent __last, iter_difference_t<_Iter> __n)
> const
> + {
> + _Iter __lasti = ranges::next(__first, __last);
> + return {_S_impl(__first, __lasti, __n), __lasti};
> + }
> +
> + template<typename _Iter>
> + static constexpr _Iter
> + _S_impl(_Iter __first, _Iter __last, iter_difference_t<_Iter> __n)
> + {
> + __glibcxx_assert(__n >= 0);
> + if (__n == 0)
> + return __first;
> +
> + if constexpr (bidirectional_iterator<_Iter>)
> + {
> + auto __mid = ranges::next(__last, -__n, __first);
I wondered if using ranges::prev(__last, __n, __first) would avoid
possible overflow for n == numeric_limits::min() but we just do -n in
ranges::prev too so it's identical anyway.
> + if (__mid == __first)
> + return __last;
> +
> + return ranges::move_backward(__first, __mid, __last).out;
> + }
> + else
> + {
> + auto __result = ranges::next(__first, __n, __last);
> + if (__result == __last)
> + return __last;
> +
> + auto __dest_head = __first, __dest_tail = __result;
> + while (__dest_head != __result)
> + {
> + if (__dest_tail == __last)
> + {
> + // If we get here, then we must have
> + // 2*n >= distance(__first, __last)
> + // i.e. we are shifting out at least half of the range.
> In
> + // this case we can safely perform the shift with a single
> + // move.
> + ranges::move(__first, __dest_head, __result);
> + return __result;
> + }
> + ++__dest_head;
> + ++__dest_tail;
> + }
> +
> + for (;;)
> + {
> + // At the start of each iteration of this outer loop, the
> range
> + // [__first, __result) contains those elements that after
> shifting
> + // the whole range right by __n, should end up in
> + // [__dest_head, __dest_tail) in order.
> +
> + // The below inner loop swaps the elements of [__first,
> __result)
> + // and [__dest_head, __dest_tail), while simultaneously
> shifting
> + // the latter range by __n.
> + auto __cursor = __first;
> + while (__cursor != __result)
> + {
> + if (__dest_tail == __last)
> + {
> + // At this point the ranges [__first, result) and
> + // [__dest_head, dest_tail) are disjoint, so we can
> safely
> + // move the remaining elements.
> + __dest_head = ranges::move(__cursor, __result,
> __dest_head).out;
> + ranges::move(__first, __cursor, __dest_head);
> + return __result;
> + }
> + ranges::iter_swap(__cursor, __dest_head);
> + ++__dest_head;
> + ++__dest_tail;
> + ++__cursor;
> + }
> + }
> + }
> + }
> +
> + template<forward_range _Range>
> + requires permutable<iterator_t<_Range>>
> + constexpr borrowed_subrange_t<_Range>
> + operator()(_Range&& __r, range_difference_t<_Range> __n) const
> + { return (*this)(ranges::begin(__r), ranges::end(__r), __n); }
> + };
> +
> + inline constexpr __shift_right_fn shift_right{};
> +#endif // C++23
> +} // namespace ranges
>
> _GLIBCXX_END_NAMESPACE_VERSION
> } // namespace std
> diff --git a/libstdc++-v3/include/bits/version.def
> b/libstdc++-v3/include/bits/version.def
> index 880586e91260..917806e9a9a8 100644
> --- a/libstdc++-v3/include/bits/version.def
> +++ b/libstdc++-v3/include/bits/version.def
> @@ -1091,6 +1091,10 @@ ftms = {
>
> ftms = {
> name = shift;
> + values = {
> + v = 202202;
> + cxxmin = 23;
> + };
> values = {
> v = 201806;
> cxxmin = 20;
> diff --git a/libstdc++-v3/include/bits/version.h
> b/libstdc++-v3/include/bits/version.h
> index 4300adb22762..ca3b062dfc61 100644
> --- a/libstdc++-v3/include/bits/version.h
> +++ b/libstdc++-v3/include/bits/version.h
> @@ -1224,7 +1224,12 @@
> #undef __glibcxx_want_constexpr_utility
>
> #if !defined(__cpp_lib_shift)
> -# if (__cplusplus >= 202002L)
> +# if (__cplusplus >= 202100L)
> +# define __glibcxx_shift 202202L
> +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_shift)
> +# define __cpp_lib_shift 202202L
> +# endif
> +# elif (__cplusplus >= 202002L)
> # define __glibcxx_shift 201806L
> # if defined(__glibcxx_want_all) || defined(__glibcxx_want_shift)
> # define __cpp_lib_shift 201806L
> diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
> b/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
> new file mode 100644
> index 000000000000..73d061439885
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/shift_left/constrained.cc
> @@ -0,0 +1,105 @@
> +// Copyright (C) 2020-2025 Free Software Foundation, Inc.
The new tests are based on existing ones, so the copyright notice is correct.
> +//
> +// This file is part of the GNU ISO C++ Library. This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> +// GNU General Public License for more details.
> +
> +// You should have received a copy of the GNU General Public License along
> +// with this library; see the file COPYING3. If not see
> +// <http://www.gnu.org/licenses/>.
> +
> +// { dg-do run { target c++23 } }
> +// This test is based on shift_left/1.cc.
> +
> +#include <algorithm>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +using __gnu_test::test_range;
> +using __gnu_test::forward_iterator_wrapper;
> +using __gnu_test::bidirectional_iterator_wrapper;
> +using __gnu_test::random_access_iterator_wrapper;
> +
> +struct X
> +{
> + int a = -1;
> + bool moved_from = false;
> +
> + X() = default;
> +
> + X(int a)
> + : a(a)
> + { }
> +
> + X(const X&) = delete;
> + X& operator=(const X&) = delete;
> +
> + X(X&& other)
> + {
> + if (this != &other)
> + *this = std::move(other);
> + }
> +
> + X&
> + operator=(X&& other)
> + {
> + a = other.a;
> + other.moved_from = true;
> + moved_from = false;
> + return *this;
> + }
> +};
> +
> +template<int N, template<typename> typename Wrapper>
> +void
> +test01()
> +{
> + for (int n = 0; n < N+5; n++)
> + {
> + X x[N];
> + for (int i = 0; i < N; i++)
> + x[i] = X{i};
> + test_range<X, Wrapper> rx(x);
> + auto [first,out] = std::ranges::shift_left(rx.begin(), rx.end(), n);
> + VERIFY( first == rx.begin() );
> + if (n < N)
> + {
> + VERIFY( out.ptr == x+(N-n) );
> + for (int i = 0; i < N-n; i++)
> + {
> + VERIFY( x[i].a == n+i );
> + VERIFY( !x[i].moved_from );
> + }
> + for (int i = std::max(n, N-n); i < N; i++)
> + VERIFY( x[i].moved_from );
> + }
> + else
> + {
> + VERIFY( out.ptr == x );
> + for (int i = 0; i < N; i++)
> + {
> + VERIFY( x[i].a == i );
> + VERIFY( !x[i].moved_from );
> + }
> + }
> + }
> +}
> +
> +int
> +main()
> +{
> + test01<23, forward_iterator_wrapper>();
> + test01<23, bidirectional_iterator_wrapper>();
> + test01<23, random_access_iterator_wrapper>();
> +
> + test01<24, forward_iterator_wrapper>();
> + test01<24, bidirectional_iterator_wrapper>();
> + test01<24, random_access_iterator_wrapper>();
> +}
> diff --git a/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
> b/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
> new file mode 100644
> index 000000000000..0d53707237e4
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/25_algorithms/shift_right/constrained.cc
> @@ -0,0 +1,104 @@
> +// Copyright (C) 2020-2025 Free Software Foundation, Inc.
> +//
> +// This file is part of the GNU ISO C++ Library. This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> +// GNU General Public License for more details.
> +
> +// You should have received a copy of the GNU General Public License along
> +// with this library; see the file COPYING3. If not see
> +// <http://www.gnu.org/licenses/>.
> +
> +// { dg-do run { target c++23 } }
> +// This test is based on shift_right/1.cc.
> +
> +#include <algorithm>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +using __gnu_test::test_range;
> +using __gnu_test::forward_iterator_wrapper;
> +using __gnu_test::bidirectional_iterator_wrapper;
> +using __gnu_test::random_access_iterator_wrapper;
> +
> +struct X
> +{
> + int a = -1;
> + bool moved_from = false;
> +
> + X() = default;
> +
> + X(int a)
> + : a(a)
> + { }
> +
> + X(const X&) = delete;
> + X& operator=(const X&) = delete;
> +
> + X(X&& other)
> + {
> + if (this != &other)
> + *this = std::move(other);
> + }
> +
> + X&
> + operator=(X&& other)
> + {
> + a = other.a;
> + other.moved_from = true;
> + moved_from = false;
> + return *this;
> + }
> +};
> +
> +template<int N, template<typename> typename Wrapper>
> +void
> +test01()
> +{
> + for (int n = 0; n < N+5; n++)
> + {
> + X x[N];
> + for (int i = 0; i < N; i++)
> + x[i] = X(i);
> + test_range<X, Wrapper> rx(x);
> + auto [out,last] = std::ranges::shift_right(rx.begin(), rx.end(), n);
> + VERIFY( last == rx.end() );
> + if (n < N)
> + {
> + VERIFY( out.ptr == x+n );
> + for (int i = n; i < N; i++)
> + VERIFY( x[i].a == i-n );
> + for (int i = 0; i < std::min(n, N-n); i++)
> + VERIFY( x[i].moved_from );
> + for (int i = std::min(n, N-n); i < std::max(n, N-n); i++)
> + VERIFY( !x[i].moved_from );
> + }
> + else
> + {
> + VERIFY( out.ptr == x+N );
> + for (int i = 0; i < N; i++)
> + {
> + VERIFY( x[i].a == i );
> + VERIFY( !x[i].moved_from );
> + }
> + }
> + }
> +}
> +
> +int
> +main()
> +{
> + test01<23, forward_iterator_wrapper>();
> + test01<23, bidirectional_iterator_wrapper>();
> + test01<23, random_access_iterator_wrapper>();
> +
> + test01<24, forward_iterator_wrapper>();
> + test01<24, bidirectional_iterator_wrapper>();
> + test01<24, random_access_iterator_wrapper>();
> +}
> --
> 2.50.0.131.gcf6f63ea6b
>
