[4/4] libstdc++: Implement ranges::slide_view from P2442R1

Message ID 20220912164531.1742034-4-ppalka@redhat.com
State New, archived
Headers
Series [1/4] libstdc++: Add already-accepted <ranges> testcase [PR106320] |

Commit Message

Patrick Palka Sept. 12, 2022, 4:45 p.m. UTC
  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
  

Comments

Jonathan Wakely Sept. 13, 2022, 11:12 a.m. UTC | #1
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.
  

Patch

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());
+}