* [PATCH 2/4] libstdc++: Implement LWG 3569 changes to join_view::_Iterator
2022-09-12 16:45 [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Patrick Palka
@ 2022-09-12 16:45 ` Patrick Palka
2022-09-13 10:57 ` Jonathan Wakely
2022-09-12 16:45 ` [PATCH 3/4] libstdc++: Implement ranges::chunk_view from P2442R1 Patrick Palka
` (2 subsequent siblings)
3 siblings, 1 reply; 8+ messages in thread
From: Patrick Palka @ 2022-09-12 16:45 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, Patrick Palka
Tested on x86_64-pc-linux-gnu, does this look OK for trunk only?
libstdc++-v3/ChangeLog:
* include/std/ranges (join_view::_Iterator::_M_satisfy):
Adjust resetting _M_inner as per LWG 3569.
(join_view::_Iterator::_M_inner): Wrap in std::optional
as per LWG 3569.
(join_view::_Iterator::_Iterator): Relax constraints as
per LWG 3569.
(join_view::_Iterator::operator*): Adjust as per LWG 3569.
(join_view::_Iterator::operator->): Likewise.
(join_view::_Iterator::operator++): Likewise.
(join_view::_Iterator::operator--): Likewise.
(join_view::_Iterator::iter_move): Likewise.
(join_view::_Iterator::iter_swap): Likewise.
* testsuite/std/ranges/adaptor/join.cc (test14): New test.
---
libstdc++-v3/include/std/ranges | 28 +++++++++----------
.../testsuite/std/ranges/adaptors/join.cc | 17 +++++++++++
2 files changed, 30 insertions(+), 15 deletions(-)
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 20eb4e82ac8..6297ce7cee3 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -2746,7 +2746,7 @@ namespace views::__adaptor
}
if constexpr (_S_ref_is_glvalue)
- _M_inner = _Inner_iter();
+ _M_inner.reset();
}
static constexpr auto
@@ -2769,7 +2769,7 @@ namespace views::__adaptor
using _Inner_iter = join_view::_Inner_iter<_Const>;
_Outer_iter _M_outer = _Outer_iter();
- _Inner_iter _M_inner = _Inner_iter();
+ optional<_Inner_iter> _M_inner;
_Parent* _M_parent = nullptr;
public:
@@ -2780,9 +2780,7 @@ namespace views::__adaptor
= common_type_t<range_difference_t<_Base>,
range_difference_t<range_reference_t<_Base>>>;
- _Iterator() requires (default_initializable<_Outer_iter>
- && default_initializable<_Inner_iter>)
- = default;
+ _Iterator() requires default_initializable<_Outer_iter> = default;
constexpr
_Iterator(_Parent* __parent, _Outer_iter __outer)
@@ -2801,7 +2799,7 @@ namespace views::__adaptor
constexpr decltype(auto)
operator*() const
- { return *_M_inner; }
+ { return **_M_inner; }
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3500. join_view::iterator::operator->() is bogus
@@ -2809,7 +2807,7 @@ namespace views::__adaptor
operator->() const
requires __detail::__has_arrow<_Inner_iter>
&& copyable<_Inner_iter>
- { return _M_inner; }
+ { return *_M_inner; }
constexpr _Iterator&
operator++()
@@ -2820,7 +2818,7 @@ namespace views::__adaptor
else
return *_M_parent->_M_inner;
}();
- if (++_M_inner == ranges::end(__inner_range))
+ if (++*_M_inner == ranges::end(__inner_range))
{
++_M_outer;
_M_satisfy();
@@ -2850,9 +2848,9 @@ namespace views::__adaptor
{
if (_M_outer == ranges::end(_M_parent->_M_base))
_M_inner = ranges::end(*--_M_outer);
- while (_M_inner == ranges::begin(*_M_outer))
- _M_inner = ranges::end(*--_M_outer);
- --_M_inner;
+ while (*_M_inner == ranges::begin(*_M_outer))
+ *_M_inner = ranges::end(*--_M_outer);
+ --*_M_inner;
return *this;
}
@@ -2879,14 +2877,14 @@ namespace views::__adaptor
friend constexpr decltype(auto)
iter_move(const _Iterator& __i)
- noexcept(noexcept(ranges::iter_move(__i._M_inner)))
- { return ranges::iter_move(__i._M_inner); }
+ noexcept(noexcept(ranges::iter_move(*__i._M_inner)))
+ { return ranges::iter_move(*__i._M_inner); }
friend constexpr void
iter_swap(const _Iterator& __x, const _Iterator& __y)
- noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
+ noexcept(noexcept(ranges::iter_swap(*__x._M_inner, *__y._M_inner)))
requires indirectly_swappable<_Inner_iter>
- { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
+ { return ranges::iter_swap(*__x._M_inner, *__y._M_inner); }
friend _Iterator<!_Const>;
template<bool> friend struct _Sentinel;
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
index 530ab6663b5..afc11d4bd7a 100644
--- a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
@@ -21,6 +21,7 @@
#include <algorithm>
#include <array>
#include <ranges>
+#include <sstream>
#include <string>
#include <string_view>
#include <vector>
@@ -217,6 +218,21 @@ test13()
std::vector<std::vector<int>> v{{5, 6, 7}};
v | l | std::views::join;
}
+
+void
+test14()
+{
+ // LWG 3569: join_view fails to support ranges of ranges with
+ // non-default_initializable iterators
+ auto ss = std::istringstream{"1 2 3"};
+ auto v = views::single(views::istream<int>(ss));
+ using inner = ranges::range_reference_t<decltype(v)>;
+ static_assert(ranges::input_range<inner>
+ && !ranges::forward_range<inner>
+ && !std::default_initializable<ranges::iterator_t<inner>>);
+ VERIFY( ranges::equal(v | views::join, (int[]){1, 2, 3}) );
+}
+
int
main()
{
@@ -233,4 +249,5 @@ main()
test11();
test12();
test13();
+ test14();
}
--
2.37.3.542.gdd3f6c4cae
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH 2/4] libstdc++: Implement LWG 3569 changes to join_view::_Iterator
2022-09-12 16:45 ` [PATCH 2/4] libstdc++: Implement LWG 3569 changes to join_view::_Iterator Patrick Palka
@ 2022-09-13 10:57 ` Jonathan Wakely
0 siblings, 0 replies; 8+ messages in thread
From: Jonathan Wakely @ 2022-09-13 10:57 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
On Mon, 12 Sept 2022 at 17:46, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk only?
I briefly wondered whether we could just use a union there and provide
the special members to init/copy/destroy it properly, but we already
use <optional> in <ranges> so it's probably not worth it.
OK for trunk.
>
> libstdc++-v3/ChangeLog:
>
> * include/std/ranges (join_view::_Iterator::_M_satisfy):
> Adjust resetting _M_inner as per LWG 3569.
> (join_view::_Iterator::_M_inner): Wrap in std::optional
> as per LWG 3569.
> (join_view::_Iterator::_Iterator): Relax constraints as
> per LWG 3569.
> (join_view::_Iterator::operator*): Adjust as per LWG 3569.
> (join_view::_Iterator::operator->): Likewise.
> (join_view::_Iterator::operator++): Likewise.
> (join_view::_Iterator::operator--): Likewise.
> (join_view::_Iterator::iter_move): Likewise.
> (join_view::_Iterator::iter_swap): Likewise.
> * testsuite/std/ranges/adaptor/join.cc (test14): New test.
> ---
> libstdc++-v3/include/std/ranges | 28 +++++++++----------
> .../testsuite/std/ranges/adaptors/join.cc | 17 +++++++++++
> 2 files changed, 30 insertions(+), 15 deletions(-)
>
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index 20eb4e82ac8..6297ce7cee3 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -2746,7 +2746,7 @@ namespace views::__adaptor
> }
>
> if constexpr (_S_ref_is_glvalue)
> - _M_inner = _Inner_iter();
> + _M_inner.reset();
> }
>
> static constexpr auto
> @@ -2769,7 +2769,7 @@ namespace views::__adaptor
> using _Inner_iter = join_view::_Inner_iter<_Const>;
>
> _Outer_iter _M_outer = _Outer_iter();
> - _Inner_iter _M_inner = _Inner_iter();
> + optional<_Inner_iter> _M_inner;
> _Parent* _M_parent = nullptr;
>
> public:
> @@ -2780,9 +2780,7 @@ namespace views::__adaptor
> = common_type_t<range_difference_t<_Base>,
> range_difference_t<range_reference_t<_Base>>>;
>
> - _Iterator() requires (default_initializable<_Outer_iter>
> - && default_initializable<_Inner_iter>)
> - = default;
> + _Iterator() requires default_initializable<_Outer_iter> = default;
>
> constexpr
> _Iterator(_Parent* __parent, _Outer_iter __outer)
> @@ -2801,7 +2799,7 @@ namespace views::__adaptor
>
> constexpr decltype(auto)
> operator*() const
> - { return *_M_inner; }
> + { return **_M_inner; }
>
> // _GLIBCXX_RESOLVE_LIB_DEFECTS
> // 3500. join_view::iterator::operator->() is bogus
> @@ -2809,7 +2807,7 @@ namespace views::__adaptor
> operator->() const
> requires __detail::__has_arrow<_Inner_iter>
> && copyable<_Inner_iter>
> - { return _M_inner; }
> + { return *_M_inner; }
>
> constexpr _Iterator&
> operator++()
> @@ -2820,7 +2818,7 @@ namespace views::__adaptor
> else
> return *_M_parent->_M_inner;
> }();
> - if (++_M_inner == ranges::end(__inner_range))
> + if (++*_M_inner == ranges::end(__inner_range))
> {
> ++_M_outer;
> _M_satisfy();
> @@ -2850,9 +2848,9 @@ namespace views::__adaptor
> {
> if (_M_outer == ranges::end(_M_parent->_M_base))
> _M_inner = ranges::end(*--_M_outer);
> - while (_M_inner == ranges::begin(*_M_outer))
> - _M_inner = ranges::end(*--_M_outer);
> - --_M_inner;
> + while (*_M_inner == ranges::begin(*_M_outer))
> + *_M_inner = ranges::end(*--_M_outer);
> + --*_M_inner;
> return *this;
> }
>
> @@ -2879,14 +2877,14 @@ namespace views::__adaptor
>
> friend constexpr decltype(auto)
> iter_move(const _Iterator& __i)
> - noexcept(noexcept(ranges::iter_move(__i._M_inner)))
> - { return ranges::iter_move(__i._M_inner); }
> + noexcept(noexcept(ranges::iter_move(*__i._M_inner)))
> + { return ranges::iter_move(*__i._M_inner); }
>
> friend constexpr void
> iter_swap(const _Iterator& __x, const _Iterator& __y)
> - noexcept(noexcept(ranges::iter_swap(__x._M_inner, __y._M_inner)))
> + noexcept(noexcept(ranges::iter_swap(*__x._M_inner, *__y._M_inner)))
> requires indirectly_swappable<_Inner_iter>
> - { return ranges::iter_swap(__x._M_inner, __y._M_inner); }
> + { return ranges::iter_swap(*__x._M_inner, *__y._M_inner); }
>
> friend _Iterator<!_Const>;
> template<bool> friend struct _Sentinel;
> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> index 530ab6663b5..afc11d4bd7a 100644
> --- a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> @@ -21,6 +21,7 @@
> #include <algorithm>
> #include <array>
> #include <ranges>
> +#include <sstream>
> #include <string>
> #include <string_view>
> #include <vector>
> @@ -217,6 +218,21 @@ test13()
> std::vector<std::vector<int>> v{{5, 6, 7}};
> v | l | std::views::join;
> }
> +
> +void
> +test14()
> +{
> + // LWG 3569: join_view fails to support ranges of ranges with
> + // non-default_initializable iterators
> + auto ss = std::istringstream{"1 2 3"};
> + auto v = views::single(views::istream<int>(ss));
> + using inner = ranges::range_reference_t<decltype(v)>;
> + static_assert(ranges::input_range<inner>
> + && !ranges::forward_range<inner>
> + && !std::default_initializable<ranges::iterator_t<inner>>);
> + VERIFY( ranges::equal(v | views::join, (int[]){1, 2, 3}) );
> +}
> +
> int
> main()
> {
> @@ -233,4 +249,5 @@ main()
> test11();
> test12();
> test13();
> + test14();
> }
> --
> 2.37.3.542.gdd3f6c4cae
>
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 3/4] libstdc++: Implement ranges::chunk_view from P2442R1
2022-09-12 16:45 [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Patrick Palka
2022-09-12 16:45 ` [PATCH 2/4] libstdc++: Implement LWG 3569 changes to join_view::_Iterator Patrick Palka
@ 2022-09-12 16:45 ` Patrick Palka
2022-09-13 11:10 ` Jonathan Wakely
2022-09-12 16:45 ` [PATCH 4/4] libstdc++: Implement ranges::slide_view " Patrick Palka
2022-09-12 18:30 ` [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Jonathan Wakely
3 siblings, 1 reply; 8+ messages in thread
From: Patrick Palka @ 2022-09-12 16:45 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, Patrick Palka
This also implements the LWG 3707, 3710 and 3712 changes to chunk_view.
libstdc++-v3/ChangeLog:
* include/std/ranges (__detail::__div_ceil): Define.
(chunk_view): Define.
(chunk_view::_OuterIter): Define.
(chunk_view::_OuterIter::value_type): Define.
(chunk_view::_InnerIter): Define.
(chunk_view<_Vp>): Define partial specialization for forward
ranges.
(enable_borrowed_range<chunk_view>): Define.
(chunk_view<_Vp>::_Iterator): Define.
(views::__detail::__can_chunk_view): Define.
(views::_Chunk, views::chunk): Define.
* testsuite/std/ranges/adaptors/chunk/1.cc: New test.
---
libstdc++-v3/include/std/ranges | 538 ++++++++++++++++++
.../testsuite/std/ranges/adaptors/chunk/1.cc | 80 +++
2 files changed, 618 insertions(+)
create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/chunk/1.cc
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 6297ce7cee3..7533b60c1d6 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -5776,6 +5776,544 @@ namespace views::__adaptor
inline constexpr auto pairwise_transform = adjacent_transform<2>;
}
+
+ namespace __detail
+ {
+ template<typename _Tp>
+ constexpr _Tp __div_ceil(_Tp __num, _Tp __denom)
+ {
+ _Tp __r = __num / __denom;
+ if (__num % __denom)
+ ++__r;
+ return __r;
+ }
+ }
+
+ template<view _Vp>
+ requires input_range<_Vp>
+ class chunk_view : public view_interface<chunk_view<_Vp>>
+ {
+ _Vp _M_base;
+ range_difference_t<_Vp> _M_n;
+ range_difference_t<_Vp> _M_remainder = 0;
+ __detail::__non_propagating_cache<iterator_t<_Vp>> _M_current;
+
+ class _OuterIter;
+ class _InnerIter;
+
+ public:
+ constexpr explicit
+ chunk_view(_Vp __base, range_difference_t<_Vp> __n)
+ : _M_base(std::move(__base)), _M_n(__n)
+ { __glibcxx_assert(__n >= 0); }
+
+ constexpr _Vp
+ base() const & requires copy_constructible<_Vp>
+ { return _M_base; }
+
+ constexpr _Vp
+ base() &&
+ { return std::move(_M_base); }
+
+ constexpr _OuterIter
+ begin()
+ {
+ _M_current = ranges::begin(_M_base);
+ _M_remainder = _M_n;
+ return _OuterIter(*this);
+ }
+
+ constexpr default_sentinel_t
+ end() const noexcept
+ { return default_sentinel; }
+
+ constexpr auto
+ size() requires sized_range<_Vp>
+ {
+ return __detail::__to_unsigned_like(__detail::__div_ceil
+ (ranges::distance(_M_base), _M_n));
+ }
+
+ constexpr auto
+ size() const requires sized_range<const _Vp>
+ {
+ return __detail::__to_unsigned_like(__detail::__div_ceil
+ (ranges::distance(_M_base), _M_n));
+ }
+ };
+
+ template<typename _Range>
+ chunk_view(_Range&&, range_difference_t<_Range>) -> chunk_view<views::all_t<_Range>>;
+
+ template<view _Vp>
+ requires input_range<_Vp>
+ class chunk_view<_Vp>::_OuterIter
+ {
+ chunk_view* _M_parent;
+
+ constexpr explicit
+ _OuterIter(chunk_view& __parent)
+ : _M_parent(std::__addressof(__parent))
+ { }
+
+ friend chunk_view;
+
+ public:
+ using iterator_concept = input_iterator_tag;
+ using difference_type = range_difference_t<_Vp>;
+
+ struct value_type;
+
+ _OuterIter(_OuterIter&&) = default;
+ _OuterIter& operator=(_OuterIter&&) = default;
+
+ constexpr value_type
+ operator*() const
+ {
+ __glibcxx_assert(*this != default_sentinel);
+ return value_type(*_M_parent);
+ }
+
+ constexpr _OuterIter&
+ operator++()
+ {
+ __glibcxx_assert(*this != default_sentinel);
+ ranges::advance(*_M_parent->_M_current, _M_parent->_M_remainder,
+ ranges::end(_M_parent->_M_base));
+ _M_parent->_M_remainder = _M_parent->_M_n;
+ return *this;
+ }
+
+ constexpr void
+ operator++(int)
+ { ++*this; }
+
+ friend constexpr bool
+ operator==(const _OuterIter& __x, default_sentinel_t)
+ {
+ return *__x._M_parent->_M_current == ranges::end(__x._M_parent->_M_base)
+ && __x._M_parent->_M_remainder != 0;
+ }
+
+ friend constexpr difference_type
+ operator-(default_sentinel_t, const _OuterIter& __x)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ {
+ const auto __dist = ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current;
+
+ if (__dist < __x._M_parent->_M_remainder)
+ return __dist == 0 ? 0 : 1;
+
+ return 1 + __detail::__div_ceil(__dist - __x._M_parent->_M_remainder,
+ __x._M_parent->_M_n);
+ }
+
+ friend constexpr difference_type
+ operator-(const _OuterIter& __x, default_sentinel_t __y)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return -(__y - __x); }
+ };
+
+ template<view _Vp>
+ requires input_range<_Vp>
+ struct chunk_view<_Vp>::_OuterIter::value_type : view_interface<value_type>
+ {
+ private:
+ chunk_view* _M_parent;
+
+ constexpr explicit
+ value_type(chunk_view& __parent)
+ : _M_parent(std::__addressof(__parent))
+ { }
+
+ friend _OuterIter;
+
+ public:
+ constexpr _InnerIter
+ begin() const noexcept
+ { return _InnerIter(*_M_parent); }
+
+ constexpr default_sentinel_t
+ end() const noexcept
+ { return default_sentinel; }
+
+ constexpr auto
+ size() const
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ {
+ return __detail::__to_unsigned_like
+ (ranges::min(_M_parent->_M_remainder,
+ ranges::end(_M_parent->_M_base) - *_M_parent->_M_current));
+ }
+ };
+
+ template<view _Vp>
+ requires input_range<_Vp>
+ class chunk_view<_Vp>::_InnerIter
+ {
+ chunk_view* _M_parent;
+
+ constexpr explicit
+ _InnerIter(chunk_view& __parent) noexcept
+ : _M_parent(std::__addressof(__parent))
+ { }
+
+ friend _OuterIter::value_type;
+
+ public:
+ using iterator_concept = input_iterator_tag;
+ using difference_type = range_difference_t<_Vp>;
+ using value_type = range_value_t<_Vp>;
+
+ _InnerIter(_InnerIter&&) = default;
+ _InnerIter& operator=(_InnerIter&&) = default;
+
+ constexpr const iterator_t<_Vp>&
+ base() const &
+ { return *_M_parent->_M_current; }
+
+ constexpr range_reference_t<_Vp>
+ operator*() const
+ {
+ __glibcxx_assert(*this != default_sentinel);
+ return **_M_parent->_M_current;
+ }
+
+ constexpr _InnerIter&
+ operator++()
+ {
+ __glibcxx_assert(*this != default_sentinel);
+ ++*_M_parent->_M_current;
+ if (*_M_parent->_M_current == ranges::end(_M_parent->_M_base))
+ _M_parent->_M_remainder = 0;
+ else
+ --_M_parent->_M_remainder;
+ return *this;
+ }
+
+ constexpr void
+ operator++(int)
+ { ++*this; }
+
+ friend constexpr bool
+ operator==(const _InnerIter& __x, default_sentinel_t)
+ { return __x._M_parent->_M_remainder == 0; }
+
+ friend constexpr difference_type
+ operator-(default_sentinel_t, const _InnerIter& __x)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ {
+ return ranges::min(__x._M_parent->_M_remainder,
+ ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current);
+ }
+
+ friend constexpr difference_type
+ operator-(const _InnerIter& __x, default_sentinel_t __y)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return -(__y - __x); }
+ };
+
+ template<view _Vp>
+ requires forward_range<_Vp>
+ class chunk_view<_Vp> : public view_interface<chunk_view<_Vp>>
+ {
+ _Vp _M_base;
+ range_difference_t<_Vp> _M_n;
+ template<bool> class _Iterator;
+
+ public:
+ constexpr explicit
+ chunk_view(_Vp __base, range_difference_t<_Vp> __n)
+ : _M_base(std::move(__base)), _M_n(__n)
+ { __glibcxx_assert(__n > 0); }
+
+ constexpr _Vp
+ base() const & requires copy_constructible<_Vp>
+ { return _M_base; }
+
+ constexpr _Vp
+ base() &&
+ { return std::move(_M_base); }
+
+ constexpr auto
+ begin() requires (!__detail::__simple_view<_Vp>)
+ { return _Iterator<false>(this, ranges::begin(_M_base)); }
+
+ constexpr auto
+ begin() const requires forward_range<const _Vp>
+ { return _Iterator<true>(this, ranges::begin(_M_base)); }
+
+ constexpr auto
+ end() requires (!__detail::__simple_view<_Vp>)
+ {
+ if constexpr (common_range<_Vp> && sized_range<_Vp>)
+ {
+ auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n;
+ return _Iterator<false>(this, ranges::end(_M_base), __missing);
+ }
+ else if constexpr (common_range<_Vp> && !bidirectional_range<_Vp>)
+ return _Iterator<false>(this, ranges::end(_M_base));
+ else
+ return default_sentinel;
+ }
+
+ constexpr auto
+ end() const requires forward_range<const _Vp>
+ {
+ if constexpr (common_range<const _Vp> && sized_range<const _Vp>)
+ {
+ auto __missing = (_M_n - ranges::distance(_M_base) % _M_n) % _M_n;
+ return _Iterator<true>(this, ranges::end(_M_base), __missing);
+ }
+ else if constexpr (common_range<const _Vp> && !bidirectional_range<const _Vp>)
+ return _Iterator<true>(this, ranges::end(_M_base));
+ else
+ return default_sentinel;
+ }
+
+ constexpr auto
+ size() requires sized_range<_Vp>
+ {
+ return __detail::__to_unsigned_like(__detail::__div_ceil
+ (ranges::distance(_M_base), _M_n));
+ }
+
+ constexpr auto
+ size() const requires sized_range<const _Vp>
+ {
+ return __detail::__to_unsigned_like(__detail::__div_ceil
+ (ranges::distance(_M_base), _M_n));
+ }
+ };
+
+ template<typename _Vp>
+ inline constexpr bool enable_borrowed_range<chunk_view<_Vp>>
+ = forward_range<_Vp> && enable_borrowed_range<_Vp>;
+
+ template<view _Vp>
+ requires forward_range<_Vp>
+ template<bool _Const>
+ class chunk_view<_Vp>::_Iterator
+ {
+ using _Parent = __detail::__maybe_const_t<_Const, chunk_view>;
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+
+ iterator_t<_Base> _M_current = iterator_t<_Base>();
+ sentinel_t<_Base> _M_end = sentinel_t<_Base>();
+ range_difference_t<_Base> _M_n = 0;
+ range_difference_t<_Base> _M_missing = 0;
+
+ constexpr
+ _Iterator(_Parent* __parent, iterator_t<_Base> __current,
+ range_difference_t<_Base> __missing = 0)
+ : _M_current(__current), _M_end(ranges::end(__parent->_M_base)),
+ _M_n(__parent->_M_n), _M_missing(__missing)
+ { }
+
+ static auto
+ _S_iter_cat()
+ {
+ if constexpr (random_access_range<_Base>)
+ return random_access_iterator_tag{};
+ else if constexpr (bidirectional_range<_Base>)
+ return bidirectional_iterator_tag{};
+ else
+ return forward_iterator_tag{};
+ }
+
+ friend chunk_view;
+
+ public:
+ using iterator_category = input_iterator_tag;
+ using iterator_concept = decltype(_S_iter_cat());
+ using value_type = decltype(views::take(subrange(_M_current, _M_end), _M_n));
+ using difference_type = range_difference_t<_Base>;
+
+ _Iterator() = default;
+
+ constexpr _Iterator(_Iterator<!_Const> __i)
+ requires _Const
+ && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
+ && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
+ : _M_current(std::move(__i._M_current)), _M_end(std::move(__i._M_end)),
+ _M_n(__i._M_n), _M_missing(__i._M_missing)
+ { }
+
+ constexpr iterator_t<_Base>
+ base() const
+ { return _M_current; }
+
+ constexpr value_type
+ operator*() const
+ {
+ __glibcxx_assert(_M_current != _M_end);
+ return views::take(subrange(_M_current, _M_end), _M_n);
+ }
+
+ constexpr _Iterator&
+ operator++()
+ {
+ __glibcxx_assert(_M_current != _M_end);
+ _M_missing = ranges::advance(_M_current, _M_n, _M_end);
+ return *this;
+ }
+
+ constexpr _Iterator
+ operator++(int)
+ {
+ auto __tmp = *this;
+ ++*this;
+ return __tmp;
+ }
+
+ constexpr _Iterator&
+ operator--() requires bidirectional_range<_Base>
+ {
+ ranges::advance(_M_current, _M_missing - _M_n);
+ _M_missing = 0;
+ return *this;
+ }
+
+ constexpr _Iterator
+ operator--(int) requires bidirectional_range<_Base>
+ {
+ auto __tmp = *this;
+ --*this;
+ return __tmp;
+ }
+
+ constexpr _Iterator&
+ operator+=(difference_type __x)
+ requires random_access_range<_Base>
+ {
+ if (__x > 0)
+ {
+ __glibcxx_assert(ranges::distance(_M_current, _M_end) > _M_n * (__x - 1));
+ _M_missing = ranges::advance(_M_current, _M_n * __x, _M_end);
+ }
+ else if (__x < 0)
+ {
+ ranges::advance(_M_current, _M_n * __x + _M_missing);
+ _M_missing = 0;
+ }
+ return *this;
+ }
+
+ constexpr _Iterator&
+ operator-=(difference_type __x)
+ requires random_access_range<_Base>
+ { return *this += -__x; }
+
+ constexpr value_type
+ operator[](difference_type __n) const
+ requires random_access_range<_Base>
+ { return *(*this + __n); }
+
+ friend constexpr bool
+ operator==(const _Iterator& __x, const _Iterator& __y)
+ { return __x._M_current == __y._M_current; }
+
+ friend constexpr bool
+ operator==(const _Iterator& __x, default_sentinel_t)
+ { return __x._M_current == __x._M_end; }
+
+ friend constexpr bool
+ operator<(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return __x._M_current > __y._M_current; }
+
+ friend constexpr bool
+ operator>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return __y < __x; }
+
+ friend constexpr bool
+ operator<=(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return !(__y < __x); }
+
+ friend constexpr bool
+ operator>=(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return !(__x < __y); }
+
+ friend constexpr auto
+ operator<=>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ && three_way_comparable<iterator_t<_Base>>
+ { return __x._M_current <=> __y._M_current; }
+
+ friend constexpr _Iterator
+ operator+(const _Iterator& __i, difference_type __n)
+ requires random_access_range<_Base>
+ {
+ auto __r = __i;
+ __r += __n;
+ return __r;
+ }
+
+ friend constexpr _Iterator
+ operator+(difference_type __n, const _Iterator& __i)
+ requires random_access_range<_Base>
+ {
+ auto __r = __i;
+ __r += __n;
+ return __r;
+ }
+
+ friend constexpr _Iterator
+ operator-(const _Iterator& __i, difference_type __n)
+ requires random_access_range<_Base>
+ {
+ auto __r = __i;
+ __r -= __n;
+ return __r;
+ }
+
+ friend constexpr difference_type
+ operator-(const _Iterator& __x, const _Iterator& __y)
+ requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
+ {
+ return (__x._M_current - __y._M_current
+ + __x._M_missing - __y._M_missing) / __x._M_n;
+ }
+
+ friend constexpr difference_type
+ operator-(default_sentinel_t __y, const _Iterator& __x)
+ requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
+ { return __detail::__div_ceil(__x._M_end - __x._M_current, __x._M_n); }
+
+ friend constexpr difference_type
+ operator-(const _Iterator& __x, default_sentinel_t __y)
+ requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<_Base>>
+ { return -(__y - __x); }
+ };
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Dp>
+ concept __can_chunk_view
+ = requires { chunk_view(std::declval<_Range>(), std::declval<_Dp>()); };
+ }
+
+ struct _Chunk : __adaptor::_RangeAdaptor<_Chunk>
+ {
+ template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
+ requires __detail::__can_chunk_view<_Range, _Dp>
+ constexpr auto
+ operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
+ { return chunk_view(std::forward<_Range>(__r), __n); }
+
+ using __adaptor::_RangeAdaptor<_Chunk>::operator();
+ static constexpr int _S_arity = 2;
+ static constexpr bool _S_has_simple_extra_args = true;
+ };
+
+ inline constexpr _Chunk chunk;
+ }
+
#endif // C++23
} // namespace ranges
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/chunk/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/chunk/1.cc
new file mode 100644
index 00000000000..125c88ef853
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/chunk/1.cc
@@ -0,0 +1,80 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <ranges>
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ int x[] = {1, 2, 3, 4, 5};
+
+ auto v2 = x | views::chunk(2);
+ const auto i0 = v2.begin(), i1 = v2.begin() + 1;
+ VERIFY( i0 + 1 - 1 == i0 );
+ VERIFY( i0 < i1 );
+ VERIFY( i1 < v2.end() );
+ VERIFY( i1 - i0 == 1 );
+ VERIFY( i0 - i1 == -1 );
+ VERIFY( v2.end() - i1 == 2 );
+ VERIFY( i1 - v2.end() == -2 );
+ auto i2 = v2.begin();
+ i2 += 2;
+ i2 -= -1;
+ VERIFY( i2 == v2.end() );
+ VERIFY( ranges::size(v2) == 3 );
+ VERIFY( ranges::equal(v2, (std::initializer_list<int>[]){{1, 2}, {3, 4}, {5}},
+ ranges::equal) );
+
+ auto v1 = x | views::chunk(1);
+ VERIFY( ranges::size(v1) == ranges::size(x) );
+ for (auto [r, n] : views::zip(v1, x))
+ {
+ VERIFY( ranges::size(r) == 1 );
+ VERIFY( *r.begin() == n );
+ }
+
+ auto v5 = x | views::chunk(5);
+ VERIFY( ranges::size(v5) == 1 );
+ VERIFY( ranges::equal(v5[0], (int[]){1, 2, 3, 4, 5}) );
+
+ auto v10 = x | views::chunk(10);
+ VERIFY( ranges::size(v10) == 1 );
+ VERIFY( ranges::equal(v10[0], (int[]){1, 2, 3, 4, 5}) );
+
+ return true;
+}
+
+template<class wrapper>
+void
+test02()
+{
+ int x[] = {1, 2, 3, 4, 5, 6, 7, 8};
+ wrapper rx(x);
+ auto v = rx | views::chunk(3);
+ auto i = ranges::begin(v);
+ VERIFY( ranges::equal(*i, (int[]){1, 2, 3}) );
+ ++i;
+ VERIFY( ranges::equal(*i, (int[]){4, 5, 6}) );
+ ++i;
+ VERIFY( ranges::equal(*i, (int[]){7, 8}) );
+ i++;
+ VERIFY( i == ranges::end(v) );
+
+ for (int i = 1; i <= 10; ++i)
+ VERIFY( ranges::equal(wrapper(x) | views::chunk(i) | views::join, x) );
+}
+
+int
+main()
+{
+ static_assert(test01());
+ test02<__gnu_test::test_input_range<int>>();
+ test02<__gnu_test::test_forward_range<int>>();
+}
--
2.37.3.542.gdd3f6c4cae
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH 3/4] libstdc++: Implement ranges::chunk_view from P2442R1
2022-09-12 16:45 ` [PATCH 3/4] libstdc++: Implement ranges::chunk_view from P2442R1 Patrick Palka
@ 2022-09-13 11:10 ` Jonathan Wakely
0 siblings, 0 replies; 8+ messages in thread
From: Jonathan Wakely @ 2022-09-13 11:10 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
On Mon, 12 Sept 2022 at 17:48, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> This also implements the LWG 3707, 3710 and 3712 changes to chunk_view.
> +
> + template<view _Vp>
> + requires input_range<_Vp>
> + class chunk_view<_Vp>::_OuterIter
> + {
> + chunk_view* _M_parent;
> +
> + constexpr explicit
> + _OuterIter(chunk_view& __parent)
This can be noexcept.
> + : _M_parent(std::__addressof(__parent))
> + { }
> +
> + friend chunk_view;
> +
> + public:
> + using iterator_concept = input_iterator_tag;
> + using difference_type = range_difference_t<_Vp>;
> +
> + struct value_type;
> +
> + _OuterIter(_OuterIter&&) = default;
> + _OuterIter& operator=(_OuterIter&&) = default;
> +
> + constexpr value_type
> + operator*() const
> + {
> + __glibcxx_assert(*this != default_sentinel);
> + return value_type(*_M_parent);
> + }
> +
> + constexpr _OuterIter&
> + operator++()
> + {
> + __glibcxx_assert(*this != default_sentinel);
> + ranges::advance(*_M_parent->_M_current, _M_parent->_M_remainder,
> + ranges::end(_M_parent->_M_base));
> + _M_parent->_M_remainder = _M_parent->_M_n;
> + return *this;
> + }
> +
> + constexpr void
> + operator++(int)
> + { ++*this; }
> +
> + friend constexpr bool
> + operator==(const _OuterIter& __x, default_sentinel_t)
> + {
> + return *__x._M_parent->_M_current == ranges::end(__x._M_parent->_M_base)
> + && __x._M_parent->_M_remainder != 0;
> + }
> +
> + friend constexpr difference_type
> + operator-(default_sentinel_t, const _OuterIter& __x)
> + requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
> + {
> + const auto __dist = ranges::end(__x._M_parent->_M_base) - *__x._M_parent->_M_current;
> +
> + if (__dist < __x._M_parent->_M_remainder)
> + return __dist == 0 ? 0 : 1;
> +
> + return 1 + __detail::__div_ceil(__dist - __x._M_parent->_M_remainder,
> + __x._M_parent->_M_n);
> + }
> +
> + friend constexpr difference_type
> + operator-(const _OuterIter& __x, default_sentinel_t __y)
> + requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
> + { return -(__y - __x); }
> + };
> +
> + template<view _Vp>
> + requires input_range<_Vp>
> + struct chunk_view<_Vp>::_OuterIter::value_type : view_interface<value_type>
> + {
> + private:
> + chunk_view* _M_parent;
> +
> + constexpr explicit
> + value_type(chunk_view& __parent)
And this.
> + : _M_parent(std::__addressof(__parent))
> + { }
> +
> + friend _OuterIter;
> +
> + template<view _Vp>
> + requires input_range<_Vp>
> + class chunk_view<_Vp>::_InnerIter
> + {
> + chunk_view* _M_parent;
> +
> + constexpr explicit
> + _InnerIter(chunk_view& __parent) noexcept
And this already is, so that's nice.
> + : _M_parent(std::__addressof(__parent))
> + { }
> +
> + friend _OuterIter::value_type;
> +
> + public:
> + using iterator_concept = input_iterator_tag;
> + using difference_type = range_difference_t<_Vp>;
> + using value_type = range_value_t<_Vp>;
> +
> + _InnerIter(_InnerIter&&) = default;
> + _InnerIter& operator=(_InnerIter&&) = default;
> +
> + constexpr const iterator_t<_Vp>&
> + base() const &
> + { return *_M_parent->_M_current; }
> +
> + constexpr range_reference_t<_Vp>
> + operator*() const
> + {
> + __glibcxx_assert(*this != default_sentinel);
> + return **_M_parent->_M_current;
> + }
> +
> + constexpr _InnerIter&
> + operator++()
> + {
> + __glibcxx_assert(*this != default_sentinel);
> + ++*_M_parent->_M_current;
> + if (*_M_parent->_M_current == ranges::end(_M_parent->_M_base))
> + _M_parent->_M_remainder = 0;
> + else
> + --_M_parent->_M_remainder;
> + return *this;
> + }
> +
> + constexpr void
> + operator++(int)
> + { ++*this; }
> +
> + friend constexpr bool
> + operator==(const _InnerIter& __x, default_sentinel_t)
noexcept
OK with those tweaks.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH 4/4] libstdc++: Implement ranges::slide_view from P2442R1
2022-09-12 16:45 [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Patrick Palka
2022-09-12 16:45 ` [PATCH 2/4] libstdc++: Implement LWG 3569 changes to join_view::_Iterator Patrick Palka
2022-09-12 16:45 ` [PATCH 3/4] libstdc++: Implement ranges::chunk_view from P2442R1 Patrick Palka
@ 2022-09-12 16:45 ` Patrick Palka
2022-09-13 11:12 ` Jonathan Wakely
2022-09-12 18:30 ` [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Jonathan Wakely
3 siblings, 1 reply; 8+ messages in thread
From: Patrick Palka @ 2022-09-12 16:45 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, Patrick Palka
This also implements the LWG 3711 and 3712 changes to slide_view.
libstdc++-v3/ChangeLog:
* include/std/ranges (__detail::__slide_caches_nothing): Define.
(__detail::__slide_caches_last): Define.
(__detail::__slide_caches_first): Define.
(slide_view): Define.
(enable_borrowed_range<slide_view>): Define.
(slide_view::_Iterator): Define.
(slide_view::_Sentinel): Define.
(views::__detail::__can_slide_view): Define.
(views::_Slide, views::slide): Define.
* testsuite/std/ranges/adaptors/slide/1.cc: New test.
---
libstdc++-v3/include/std/ranges | 364 ++++++++++++++++++
.../testsuite/std/ranges/adaptors/slide/1.cc | 105 +++++
2 files changed, 469 insertions(+)
create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc
diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 7533b60c1d6..bbe4fa278d2 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -6314,6 +6314,370 @@ namespace views::__adaptor
inline constexpr _Chunk chunk;
}
+ namespace __detail
+ {
+ template<typename _Vp>
+ concept __slide_caches_nothing = random_access_range<_Vp> && sized_range<_Vp>;
+
+ template<typename _Vp>
+ concept __slide_caches_last
+ = !__slide_caches_nothing<_Vp> && bidirectional_range<_Vp> && common_range<_Vp>;
+
+ template<typename _Vp>
+ concept __slide_caches_first
+ = !__slide_caches_nothing<_Vp> && !__slide_caches_last<_Vp>;
+ }
+
+ template<forward_range _Vp>
+ requires view<_Vp>
+ class slide_view : public view_interface<slide_view<_Vp>>
+ {
+ _Vp _M_base;
+ range_difference_t<_Vp> _M_n;
+ [[no_unique_address]]
+ __detail::__maybe_present_t<__detail::__slide_caches_first<_Vp>,
+ __detail::_CachedPosition<_Vp>> _M_cached_begin;
+ [[no_unique_address]]
+ __detail::__maybe_present_t<__detail::__slide_caches_last<_Vp>,
+ __detail::_CachedPosition<_Vp>> _M_cached_end;
+
+ template<bool> class _Iterator;
+ class _Sentinel;
+
+ public:
+ constexpr explicit
+ slide_view(_Vp __base, range_difference_t<_Vp> __n)
+ : _M_base(std::move(__base)), _M_n(__n)
+ { __glibcxx_assert(__n > 0); }
+
+ constexpr auto
+ begin() requires (!(__detail::__simple_view<_Vp>
+ && __detail::__slide_caches_nothing<const _Vp>))
+ {
+ if constexpr (__detail::__slide_caches_first<_Vp>)
+ {
+ iterator_t<_Vp> __it;
+ if (_M_cached_begin._M_has_value())
+ __it = _M_cached_begin._M_get(_M_base);
+ else
+ {
+ __it = ranges::next(ranges::begin(_M_base), _M_n - 1, ranges::end(_M_base));
+ _M_cached_begin._M_set(_M_base, __it);
+ }
+ return _Iterator<false>(ranges::begin(_M_base), std::move(__it), _M_n);
+ }
+ else
+ return _Iterator<false>(ranges::begin(_M_base), _M_n);
+ }
+
+ constexpr auto
+ begin() const requires __detail::__slide_caches_nothing<const _Vp>
+ { return _Iterator<true>(ranges::begin(_M_base), _M_n); }
+
+ constexpr auto
+ end() requires (!(__detail::__simple_view<_Vp>
+ && __detail::__slide_caches_nothing<const _Vp>))
+ {
+ if constexpr (__detail::__slide_caches_nothing<_Vp>)
+ return _Iterator<false>(ranges::begin(_M_base) + range_difference_t<_Vp>(size()),
+ _M_n);
+ else if constexpr (__detail::__slide_caches_last<_Vp>)
+ {
+ iterator_t<_Vp> __it;
+ if (_M_cached_end._M_has_value())
+ __it = _M_cached_end._M_get(_M_base);
+ else
+ {
+ __it = ranges::prev(ranges::end(_M_base), _M_n - 1,
+ ranges::begin(_M_base));
+ _M_cached_end._M_set(_M_base, __it);
+ }
+ return _Iterator<false>(std::move(__it), _M_n);
+ }
+ else if constexpr (common_range<_Vp>)
+ return _Iterator<false>(ranges::end(_M_base), ranges::end(_M_base), _M_n);
+ else
+ return _Sentinel(ranges::end(_M_base));
+ }
+
+ constexpr auto
+ end() const requires __detail::__slide_caches_nothing<const _Vp>
+ { return begin() + range_difference_t<const _Vp>(size()); }
+
+ constexpr auto
+ size() requires sized_range<_Vp>
+ {
+ auto __sz = ranges::distance(_M_base) - _M_n + 1;
+ if (__sz < 0)
+ __sz = 0;
+ return __detail::__to_unsigned_like(__sz);
+ }
+
+ constexpr auto
+ size() const requires sized_range<const _Vp>
+ {
+ auto __sz = ranges::distance(_M_base) - _M_n + 1;
+ if (__sz < 0)
+ __sz = 0;
+ return __detail::__to_unsigned_like(__sz);
+ }
+ };
+
+ template<typename _Range>
+ slide_view(_Range&&, range_difference_t<_Range>) -> slide_view<views::all_t<_Range>>;
+
+ template<typename _Vp>
+ inline constexpr bool enable_borrowed_range<slide_view<_Vp>>
+ = enable_borrowed_range<_Vp>;
+
+ template<forward_range _Vp>
+ requires view<_Vp>
+ template<bool _Const>
+ class slide_view<_Vp>::_Iterator
+ {
+ using _Base = __detail::__maybe_const_t<_Const, _Vp>;
+ static constexpr bool _S_last_elt_present
+ = __detail::__slide_caches_first<_Base>;
+
+ iterator_t<_Base> _M_current = iterator_t<_Base>();
+ [[no_unique_address]]
+ __detail::__maybe_present_t<_S_last_elt_present, iterator_t<_Base>>
+ _M_last_elt = decltype(_M_last_elt)();
+ range_difference_t<_Base> _M_n = 0;
+
+ constexpr
+ _Iterator(iterator_t<_Base> __current, range_difference_t<_Base> __n)
+ requires (!_S_last_elt_present)
+ : _M_current(__current), _M_n(__n)
+ { }
+
+ constexpr
+ _Iterator(iterator_t<_Base> __current, iterator_t<_Base> __last_elt,
+ range_difference_t<_Base> __n)
+ requires _S_last_elt_present
+ : _M_current(__current), _M_last_elt(__last_elt), _M_n(__n)
+ { }
+
+ static auto
+ _S_iter_concept()
+ {
+ if constexpr (random_access_range<_Base>)
+ return random_access_iterator_tag{};
+ else if constexpr (bidirectional_range<_Base>)
+ return bidirectional_iterator_tag{};
+ else
+ return forward_iterator_tag{};
+ }
+
+ friend slide_view;
+ friend slide_view::_Sentinel;
+
+ public:
+ using iterator_category = input_iterator_tag;
+ using iterator_concept = decltype(_S_iter_concept());
+ using value_type = decltype(views::counted(_M_current, _M_n));
+ using difference_type = range_difference_t<_Base>;
+
+ _Iterator() = default;
+
+ constexpr
+ _Iterator(_Iterator<!_Const> __i)
+ requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
+ : _M_current(std::move(__i._M_current)), _M_n(__i._M_n)
+ { }
+
+ constexpr auto
+ operator*() const
+ { return views::counted(_M_current, _M_n); }
+
+ constexpr _Iterator&
+ operator++()
+ {
+ ++_M_current;
+ if constexpr (_S_last_elt_present)
+ ++_M_last_elt;
+ return *this;
+ }
+
+ constexpr _Iterator
+ operator++(int)
+ {
+ auto __tmp = *this;
+ ++*this;
+ return __tmp;
+ }
+
+ constexpr _Iterator&
+ operator--() requires bidirectional_range<_Base>
+ {
+ --_M_current;
+ if constexpr (_S_last_elt_present)
+ --_M_last_elt;
+ return *this;
+ }
+
+ constexpr _Iterator
+ operator--(int) requires bidirectional_range<_Base>
+ {
+ auto __tmp = *this;
+ --*this;
+ return __tmp;
+ }
+
+ constexpr _Iterator&
+ operator+=(difference_type __x)
+ requires random_access_range<_Base>
+ {
+ _M_current += __x;
+ if constexpr (_S_last_elt_present)
+ _M_last_elt += __x;
+ return *this;
+ }
+
+ constexpr _Iterator&
+ operator-=(difference_type __x)
+ requires random_access_range<_Base>
+ {
+ _M_current -= __x;
+ if constexpr (_S_last_elt_present)
+ _M_last_elt -= __x;
+ return *this;
+ }
+
+ constexpr auto
+ operator[](difference_type __n) const
+ requires random_access_range<_Base>
+ { return views::counted(_M_current + __n, _M_n); }
+
+ friend constexpr bool
+ operator==(const _Iterator& __x, const _Iterator& __y)
+ {
+ if constexpr (_S_last_elt_present)
+ return __x._M_last_elt == __y._M_last_elt;
+ else
+ return __x._M_current == __y._M_current;
+ }
+
+ friend constexpr bool
+ operator<(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return __x._M_current < __y._M_current; }
+
+ friend constexpr bool
+ operator>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return __y < __x; }
+
+ friend constexpr bool
+ operator<=(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return !(__y < __x); }
+
+ friend constexpr bool
+ operator>=(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ { return !(__x < __y); }
+
+ friend constexpr auto
+ operator<=>(const _Iterator& __x, const _Iterator& __y)
+ requires random_access_range<_Base>
+ && three_way_comparable<iterator_t<_Base>>
+ { return __x._M_current <=> __y._M_current; }
+
+ friend constexpr _Iterator
+ operator+(const _Iterator& __i, difference_type __n)
+ requires random_access_range<_Base>
+ {
+ auto __r = __i;
+ __r += __n;
+ return __r;
+ }
+
+ friend constexpr _Iterator
+ operator+(difference_type __n, const _Iterator& __i)
+ requires random_access_range<_Base>
+ {
+ auto __r = __i;
+ __r += __n;
+ return __r;
+ }
+
+ friend constexpr _Iterator
+ operator-(const _Iterator& __i, difference_type __n)
+ requires random_access_range<_Base>
+ {
+ auto __r = __i;
+ __r -= __n;
+ return __r;
+ }
+
+ friend constexpr difference_type
+ operator-(const _Iterator& __x, const _Iterator& __y)
+ requires sized_sentinel_for<iterator_t<_Base>, iterator_t<_Base>>
+ {
+ if constexpr (_S_last_elt_present)
+ return __x._M_last_elt - __y._M_last_elt;
+ else
+ return __x._M_current - __y._M_current;
+ }
+ };
+
+ template<forward_range _Vp>
+ requires view<_Vp>
+ class slide_view<_Vp>::_Sentinel
+ {
+ sentinel_t<_Vp> _M_end = sentinel_t<_Vp>();
+
+ constexpr explicit
+ _Sentinel(sentinel_t<_Vp> __end)
+ : _M_end(__end)
+ { }
+
+ friend slide_view;
+
+ public:
+ _Sentinel() = default;
+
+ friend constexpr bool
+ operator==(const _Iterator<false>& __x, const _Sentinel& __y)
+ { return __x._M_last_elt == __y._M_end; }
+
+ friend constexpr range_difference_t<_Vp>
+ operator-(const _Iterator<false>& __x, const _Sentinel& __y)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return __x._M_last_elt - __y._M_end; }
+
+ friend constexpr range_difference_t<_Vp>
+ operator-(const _Sentinel& __y, const _Iterator<false>& __x)
+ requires sized_sentinel_for<sentinel_t<_Vp>, iterator_t<_Vp>>
+ { return __y._M_end -__x._M_last_elt; }
+ };
+
+ namespace views
+ {
+ namespace __detail
+ {
+ template<typename _Range, typename _Dp>
+ concept __can_slide_view
+ = requires { slide_view(std::declval<_Range>(), std::declval<_Dp>()); };
+ }
+
+ struct _Slide : __adaptor::_RangeAdaptor<_Slide>
+ {
+ template<viewable_range _Range, typename _Dp = range_difference_t<_Range>>
+ requires __detail::__can_slide_view<_Range, _Dp>
+ constexpr auto
+ operator() [[nodiscard]] (_Range&& __r, type_identity_t<_Dp> __n) const
+ { return slide_view(std::forward<_Range>(__r), __n); }
+
+ using __adaptor::_RangeAdaptor<_Slide>::operator();
+ static constexpr int _S_arity = 2;
+ static constexpr bool _S_has_simple_extra_args = true;
+ };
+
+ inline constexpr _Slide slide;
+ }
+
#endif // C++23
} // namespace ranges
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc
new file mode 100644
index 00000000000..98560420810
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/slide/1.cc
@@ -0,0 +1,105 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <ranges>
+#include <algorithm>
+#include <utility>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+constexpr bool
+test01()
+{
+ auto v1 = std::array{1, 2} | views::slide(1);
+ const auto i0 = v1.begin(), i1 = v1.begin() + 1;
+ VERIFY( i0 + 1 - 1 == i0 );
+ VERIFY( i0 < i1 );
+ VERIFY( i1 < v1.end() );
+ VERIFY( i1 - i0 == 1 );
+ VERIFY( i0 - i1 == -1 );
+ VERIFY( v1.end() - i1 == 1 );
+ VERIFY( i1 - v1.end() == -1 );
+ VERIFY( ranges::equal(std::move(v1) | views::join, (int[]){1, 2}) );
+
+ int x[] = {1, 2, 3, 4};
+ auto v2 = x | views::slide(2);
+ auto i2 = v2.begin();
+ i2 += 2;
+ i2 -= -1;
+ VERIFY( i2 == v2.end() );
+ VERIFY( ranges::size(v2) == 3 );
+ VERIFY( ranges::size(std::as_const(v2)) == 3 );
+ VERIFY( ranges::equal(v2, (std::initializer_list<int>[]){{1, 2}, {2, 3}, {3, 4}},
+ ranges::equal) );
+
+ int y[] = {1, 2, 3, 4, 5};
+ const auto v3 = y | views::slide(3);
+ VERIFY( ranges::size(v3) == 3 );
+ for (unsigned i = 0; i < ranges::size(x); i++)
+ {
+ VERIFY( &v3[i][0] == &y[i] + 0 );
+ VERIFY( &v3[i][1] == &y[i] + 1 );
+ VERIFY( &v3[i][2] == &y[i] + 2 );
+ }
+
+ const auto v5 = y | views::slide(5);
+ VERIFY( ranges::size(v5) == 1 );
+ VERIFY( ranges::equal(v5 | views::join, y) );
+
+ const auto v6 = y | views::slide(6);
+ VERIFY( ranges::empty(v6) );
+
+ return true;
+}
+
+constexpr bool
+test02()
+{
+ using __gnu_test::test_input_range;
+ using __gnu_test::test_forward_range;
+ using __gnu_test::test_random_access_range;
+
+ using ty1 = ranges::slide_view<views::all_t<test_forward_range<int>>>;
+ static_assert(ranges::forward_range<ty1>);
+ static_assert(!ranges::bidirectional_range<ty1>);
+ static_assert(!ranges::sized_range<ty1>);
+
+ using ty2 = ranges::slide_view<views::all_t<test_random_access_range<int>>>;
+ static_assert(ranges::random_access_range<ty2>);
+ static_assert(ranges::sized_range<ty2>);
+
+ return true;
+}
+
+constexpr bool
+test03()
+{
+ auto v = views::iota(0, 4) | views::filter([](auto) { return true; }) | views::slide(2);
+ using ty = decltype(v);
+ static_assert(ranges::forward_range<ty>);
+ static_assert(ranges::common_range<ty>);
+ static_assert(!ranges::sized_range<ty>);
+ VERIFY( v.begin() == v.begin() );
+ VERIFY( v.begin() != v.end() );
+ VERIFY( ranges::next(v.begin(), 3) == v.end() );
+ auto it = v.begin();
+ ++it;
+ it++;
+ VERIFY( ranges::next(it) == v.end() );
+ it--;
+ --it;
+ VERIFY( it == v.begin() );
+
+ return true;
+}
+
+int
+main()
+{
+ static_assert(test01());
+ static_assert(test02());
+ static_assert(test03());
+}
--
2.37.3.542.gdd3f6c4cae
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320]
2022-09-12 16:45 [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Patrick Palka
` (2 preceding siblings ...)
2022-09-12 16:45 ` [PATCH 4/4] libstdc++: Implement ranges::slide_view " Patrick Palka
@ 2022-09-12 18:30 ` Jonathan Wakely
3 siblings, 0 replies; 8+ messages in thread
From: Jonathan Wakely @ 2022-09-12 18:30 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
[-- Attachment #1: Type: text/plain, Size: 1420 bytes --]
On Mon, 12 Sep 2022, 17:46 Patrick Palka via Libstdc++, <
libstdc++@gcc.gnu.org> wrote:
> Although PR106320 only affected the 10 and 11 branches, and the testcase
> from there was already correctly accepted on trunk and the 12 branch, we
> should also add the testcase to 12/trunk for inter-branch consistency.
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk/12?
>
Yes, good idea to add this.
> PR libstdc++/106320
>
> libstdc++-v3/ChangeLog:
>
> * testsuite/std/ranges/adaptors/join.cc (test13): New test.
> ---
> libstdc++-v3/testsuite/std/ranges/adaptors/join.cc | 13 +++++++++++++
> 1 file changed, 13 insertions(+)
>
> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> index 8986f718229..530ab6663b5 100644
> --- a/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/join.cc
> @@ -205,6 +205,18 @@ test12()
> }();
> }
>
> +void
> +test13()
> +{
> + // PR libstdc++/106320
> + auto l = std::views::transform([](auto x) {
> + return x | std::views::transform([i=0](auto y) {
> + return y;
> + });
> + });
> + std::vector<std::vector<int>> v{{5, 6, 7}};
> + v | l | std::views::join;
> +}
> int
> main()
> {
> @@ -220,4 +232,5 @@ main()
> test10();
> test11();
> test12();
> + test13();
> }
> --
> 2.37.3.542.gdd3f6c4cae
>
>
^ permalink raw reply [flat|nested] 8+ messages in thread