public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320]
@ 2022-09-12 16:45 Patrick Palka
  2022-09-12 16:45 ` [PATCH 2/4] libstdc++: Implement LWG 3569 changes to join_view::_Iterator Patrick Palka
                   ` (3 more replies)
  0 siblings, 4 replies; 8+ messages in thread
From: Patrick Palka @ 2022-09-12 16:45 UTC (permalink / raw)
  To: gcc-patches; +Cc: libstdc++, Patrick Palka

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?

	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

* [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

* [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

* [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

* 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

* 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

* Re: [PATCH 4/4] libstdc++: Implement ranges::slide_view from P2442R1
  2022-09-12 16:45 ` [PATCH 4/4] libstdc++: Implement ranges::slide_view " Patrick Palka
@ 2022-09-13 11:12   ` Jonathan Wakely
  0 siblings, 0 replies; 8+ messages in thread
From: Jonathan Wakely @ 2022-09-13 11:12 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 3711 and 3712 changes to slide_view.

OK, thanks.


^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2022-09-13 11:12 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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-13 10:57   ` Jonathan Wakely
2022-09-12 16:45 ` [PATCH 3/4] libstdc++: Implement ranges::chunk_view from P2442R1 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-13 11:12   ` Jonathan Wakely
2022-09-12 18:30 ` [PATCH 1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] Jonathan Wakely

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).