[gcc r13-7161] libstdc++: Implement ranges::enumerate_view from P2164R9

[gcc r13-7161] libstdc++: Implement ranges::enumerate_view from P2164R9

[Patrick Palka]

https://gcc.gnu.org/g:0f3b4d38d4bad8994150fe7a1e5428055d29a4bf

commit r13-7161-g0f3b4d38d4bad8994150fe7a1e5428055d29a4bf
Author: Patrick Palka <ppalka@redhat.com>
Date:   Wed Apr 12 13:24:37 2023 -0400

    libstdc++: Implement ranges::enumerate_view from P2164R9
    
    libstdc++-v3/ChangeLog:
    
            * include/std/ranges (__cpp_lib_ranges_enumerate): Define
            for C++23.
            (__detail::__range_with_movable_reference): Likewise.
            (enumerate_view): Likewise.
            (enumerate_view::_Iterator): Likewise.
            (enumerate_view::_Sentinel): Likewise.
            (views::__detail::__can_enumerate_view): Likewise.
            (views::_Enumerate, views::enumerate): Likewise.
            * include/std/version (__cpp_lib_ranges_enumerate): Likewise.
            * testsuite/std/ranges/version_c++23.cc: Verify value of
            __cpp_lib_ranges_enumerate.
            * testsuite/std/ranges/adaptors/enumerate/1.cc: New test.

Diff:
---
 libstdc++-v3/include/std/ranges                    | 303 +++++++++++++++++++++
 libstdc++-v3/include/std/version                   |   1 +
 .../testsuite/std/ranges/adaptors/enumerate/1.cc   | 102 +++++++
 libstdc++-v3/testsuite/std/ranges/version_c++23.cc |   4 +
 4 files changed, 410 insertions(+)

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index c21528138e5..3f6ff505617 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -8626,6 +8626,309 @@ namespace views::__adaptor
 
     inline constexpr _AsRvalue as_rvalue;
   }
+
+#define __cpp_lib_ranges_enumerate 202302L
+
+  namespace __detail
+  {
+    template<typename _Range>
+      concept __range_with_movable_reference = input_range<_Range>
+	&& move_constructible<range_reference_t<_Range>>
+	&& move_constructible<range_rvalue_reference_t<_Range>>;
+  }
+
+  template<view _Vp>
+    requires __detail::__range_with_movable_reference<_Vp>
+  class enumerate_view : public view_interface<enumerate_view<_Vp>>
+  {
+    _Vp _M_base = _Vp();
+
+    template<bool _Const> class _Iterator;
+    template<bool _Const> class _Sentinel;
+
+  public:
+    enumerate_view() requires default_initializable<_Vp> = default;
+
+    constexpr explicit
+    enumerate_view(_Vp __base)
+    : _M_base(std::move(__base))
+    { }
+
+    constexpr auto
+    begin() requires (!__detail::__simple_view<_Vp>)
+    { return _Iterator<false>(ranges::begin(_M_base), 0); }
+
+    constexpr auto
+    begin() const requires __detail::__range_with_movable_reference<const _Vp>
+    { return _Iterator<true>(ranges::begin(_M_base), 0); }
+
+    constexpr auto
+    end() requires (!__detail::__simple_view<_Vp>)
+    {
+      if constexpr (common_range<_Vp> && sized_range<_Vp>)
+	return _Iterator<false>(ranges::end(_M_base), ranges::distance(_M_base));
+      else
+	return _Sentinel<false>(ranges::end(_M_base));
+    }
+
+    constexpr auto
+    end() const requires __detail::__range_with_movable_reference<const _Vp>
+    {
+      if constexpr (common_range<const _Vp> && sized_range<const _Vp>)
+	return _Iterator<true>(ranges::end(_M_base), ranges::distance(_M_base));
+      else
+	return _Sentinel<true>(ranges::end(_M_base));
+    }
+
+    constexpr auto
+    size() requires sized_range<_Vp>
+    { return ranges::size(_M_base); }
+
+    constexpr auto
+    size() const requires sized_range<const _Vp>
+    { return ranges::size(_M_base); }
+
+    constexpr _Vp
+    base() const & requires copy_constructible<_Vp>
+    { return _M_base; }
+
+    constexpr _Vp
+    base() &&
+    { return std::move(_M_base); }
+  };
+
+  template<typename _Range>
+    enumerate_view(_Range&&) -> enumerate_view<views::all_t<_Range>>;
+
+  template<typename _Tp>
+    inline constexpr bool enable_borrowed_range<enumerate_view<_Tp>>
+      = enable_borrowed_range<_Tp>;
+
+  template<view _Vp>
+  requires __detail::__range_with_movable_reference<_Vp>
+  template<bool _Const>
+  class enumerate_view<_Vp>::_Iterator
+  {
+    using _Base = __maybe_const_t<_Const, _Vp>;
+
+    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 if constexpr (forward_range<_Base>)
+	return forward_iterator_tag{};
+      else
+	return input_iterator_tag{};
+    }
+
+    friend enumerate_view;
+
+  public:
+    using iterator_category = input_iterator_tag;
+    using iterator_concept = decltype(_S_iter_concept());
+    using difference_type = range_difference_t<_Base>;
+    using value_type = tuple<difference_type, range_value_t<_Base>>;
+
+  private:
+    using __reference_type = tuple<difference_type, range_reference_t<_Base>>;
+
+    iterator_t<_Base> _M_current = iterator_t<_Base>();
+    difference_type _M_pos = 0;
+
+    constexpr explicit
+    _Iterator(iterator_t<_Base> __current, difference_type __pos)
+    : _M_current(std::move(__current)), _M_pos(__pos)
+    { }
+
+  public:
+    _Iterator() requires default_initializable<iterator_t<_Base>> = default;
+
+    constexpr
+    _Iterator(_Iterator<!_Const> __i)
+    requires _Const && convertible_to<iterator_t<_Vp>, iterator_t<_Base>>
+    : _M_current(std::move(__i._M_current)), _M_pos(__i._M_pos)
+    { }
+
+    constexpr const iterator_t<_Base> &
+    base() const & noexcept
+    { return _M_current; }
+
+    constexpr iterator_t<_Base>
+    base() &&
+    { return std::move(_M_current); }
+
+    constexpr difference_type
+    index() const noexcept
+    { return _M_pos; }
+
+    constexpr auto
+    operator*() const
+    { return __reference_type(_M_pos, *_M_current); }
+
+    constexpr _Iterator&
+    operator++()
+    {
+      ++_M_current;
+      ++_M_pos;
+      return *this;
+    }
+
+    constexpr void
+    operator++(int)
+    { ++*this; }
+
+    constexpr _Iterator
+    operator++(int) requires forward_range<_Base>
+    {
+      auto __tmp = *this;
+      ++*this;
+      return __tmp;
+    }
+
+    constexpr _Iterator&
+    operator--() requires bidirectional_range<_Base>
+    {
+      --_M_current;
+      --_M_pos;
+      return *this;
+    }
+
+    constexpr _Iterator
+    operator--(int) requires bidirectional_range<_Base>
+    {
+      auto __tmp = *this;
+      --*this;
+      return __tmp;
+    }
+
+    constexpr _Iterator&
+    operator+=(difference_type __n) requires random_access_range<_Base>
+    {
+      _M_current += __n;
+      _M_pos += __n;
+      return *this;
+    }
+
+    constexpr _Iterator&
+    operator-=(difference_type __n) requires random_access_range<_Base>
+    {
+      _M_current -= __n;
+      _M_pos -= __n;
+      return *this;
+    }
+
+    constexpr auto
+    operator[](difference_type __n) const requires random_access_range<_Base>
+    { return __reference_type(_M_pos + __n, _M_current[__n]); }
+
+    friend constexpr bool
+    operator==(const _Iterator& __x, const _Iterator& __y) noexcept
+    { return __x._M_pos == __y._M_pos; }
+
+    friend constexpr strong_ordering
+    operator<=>(const _Iterator& __x, const _Iterator& __y) noexcept
+    { return __x._M_pos <=> __y._M_pos; }
+
+    friend constexpr _Iterator
+    operator+(const _Iterator& __x, difference_type __y)
+    requires random_access_range<_Base>
+    { return (auto(__x) += __y); }
+
+    friend constexpr _Iterator
+    operator+(difference_type __x, const _Iterator& __y)
+    requires random_access_range<_Base>
+    { return auto(__y) += __x; }
+
+    friend constexpr _Iterator
+    operator-(const _Iterator& __x, difference_type __y)
+    requires random_access_range<_Base>
+    { return auto(__x) -= __y; }
+
+    friend constexpr difference_type
+    operator-(const _Iterator& __x, const _Iterator& __y)
+    { return __x._M_pos - __y._M_pos; }
+
+    friend constexpr auto
+    iter_move(const _Iterator& __i)
+    noexcept(noexcept(ranges::iter_move(__i._M_current))
+	     && is_nothrow_move_constructible_v<range_rvalue_reference_t<_Base>>)
+    {
+      return tuple<difference_type, range_rvalue_reference_t<_Base>>
+	(__i._M_pos, ranges::iter_move(__i._M_current));
+    }
+  };
+
+  template<view _Vp>
+  requires __detail::__range_with_movable_reference<_Vp>
+  template<bool _Const>
+  class enumerate_view<_Vp>::_Sentinel
+  {
+    using _Base = __maybe_const_t<_Const, _Vp>;
+
+    sentinel_t<_Base> _M_end = sentinel_t<_Base>();
+
+    constexpr explicit
+    _Sentinel(sentinel_t<_Base> __end)
+    : _M_end(std::move(__end))
+    { }
+
+    friend enumerate_view;
+
+  public:
+    _Sentinel() = default;
+
+    constexpr
+    _Sentinel(_Sentinel<!_Const> __other)
+    requires _Const && convertible_to<sentinel_t<_Vp>, sentinel_t<_Base>>
+    : _M_end(std::move(__other._M_end))
+    { }
+
+    constexpr sentinel_t<_Base>
+    base() const
+    { return _M_end; }
+
+    template<bool _OtherConst>
+    requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const_t<_OtherConst, _Vp>>>
+    friend constexpr bool
+    operator==(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
+    { return __x._M_current == __y._M_end; }
+
+    template<bool _OtherConst>
+    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const_t<_OtherConst, _Vp>>>
+    friend constexpr range_difference_t<__maybe_const_t<_OtherConst, _Vp>>
+    operator-(const _Iterator<_OtherConst>& __x, const _Sentinel& __y)
+    { return __x._M_current - __y._M_end; }
+
+    template<bool _OtherConst>
+    requires sized_sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const_t<_OtherConst, _Vp>>>
+    friend constexpr range_difference_t<__maybe_const_t<_OtherConst, _Vp>>
+    operator-(const _Sentinel& __x, const _Iterator<_OtherConst>& __y)
+    { return __x._M_end - __y._M_current; }
+  };
+
+  namespace views
+  {
+    namespace __detail
+    {
+      template<typename _Tp>
+	concept __can_enumerate_view
+	  = requires { enumerate_view<all_t<_Tp>>(std::declval<_Tp>()); };
+    }
+
+    struct _Enumerate : __adaptor::_RangeAdaptorClosure
+    {
+      template<viewable_range _Range>
+	requires __detail::__can_enumerate_view<_Range>
+	constexpr auto
+	operator() [[nodiscard]] (_Range&& __r) const
+	{ return enumerate_view<all_t<_Range>>(std::forward<_Range>(__r)); }
+    };
+
+    inline constexpr _Enumerate enumerate;
+  }
 #endif // C++23
 } // namespace ranges
 
diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
index 1069bc6c9f6..b35435c2669 100644
--- a/libstdc++-v3/include/std/version
+++ b/libstdc++-v3/include/std/version
@@ -339,6 +339,7 @@
 #define __cpp_lib_ranges_stride 202207L
 #define __cpp_lib_ranges_cartesian_product 202207L
 #define __cpp_lib_ranges_as_rvalue 202207L
+#define __cpp_lib_ranges_enumerate 202302L
 #if __cpp_constexpr_dynamic_alloc
 # if _GLIBCXX_HOSTED
 #  define __cpp_lib_constexpr_bitset 202202L
diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/enumerate/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/enumerate/1.cc
new file mode 100644
index 00000000000..445d9854c8c
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/adaptors/enumerate/1.cc
@@ -0,0 +1,102 @@
+// { dg-options "-std=gnu++23" }
+// { dg-do run { target c++23 } }
+
+#include <ranges>
+#include <algorithm>
+#include <memory>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+#if __cpp_lib_ranges_enumerate != 202302L
+# error "Feature-test macro __cpp_lib_ranges_enumerate has wrong value in <ranges>"
+#endif
+
+namespace ranges = std::ranges;
+namespace views = std::views;
+
+using __gnu_test::test_input_range;
+using __gnu_test::test_forward_range;
+using __gnu_test::test_bidirectional_range;
+using __gnu_test::test_random_access_range;
+
+constexpr bool
+test01()
+{
+  int x[] = {1, 2, 3};
+  auto v = x | views::enumerate;
+
+  VERIFY( ranges::equal(v | views::keys, (int[]){0, 1, 2}) );
+  VERIFY( ranges::equal(v | views::values, (int[]){1, 2, 3}) );
+
+  auto it = v.begin();
+  VERIFY( it == it );
+  VERIFY( it != it + 1 );
+  VERIFY( it != v.end() );
+
+  VERIFY( it.index() == 0 );
+  VERIFY( (++it).index() == 1 );
+  VERIFY( (++it).index() == 2 );
+
+  return true;
+}
+
+template<template<class> class Container>
+void
+test02()
+{
+  int x[] = {1, 2, 3};
+  Container<int> rx (x);
+  auto v = rx | views::enumerate;
+
+  int j = 0;
+  for (auto [i, y] : v)
+    {
+      VERIFY (&y == &x[j]);
+      VERIFY (j == i);
+      ++j;
+    }
+  VERIFY (j == ranges::size(x));
+
+  if constexpr (ranges::bidirectional_range<decltype(rx)>)
+    {
+      static_assert(ranges::bidirectional_range<decltype(v)>);
+      for (auto [i, y] : v | views::reverse)
+	{
+	  --j;
+	  VERIFY (&y == &x[j]);
+	  VERIFY (j == i);
+	}
+      VERIFY (j == 0);
+    }
+
+  if constexpr (ranges::random_access_range<decltype(rx)>)
+    {
+      static_assert(ranges::random_access_range<decltype(v)>);
+      for (j = 0; j < ranges::ssize(x); ++j)
+	{
+	  VERIFY (std::get<0>(v[j]) == j);
+	  VERIFY (&std::get<1>(v[j]) == &x[j]);
+	  VERIFY (*(v.begin() + j) == v[j]);
+	  VERIFY (*(v.begin() + (ranges::size(x) - 1) - j) == v[ranges::size(x) - 1 - j]);
+	  VERIFY (v.begin() + j + 1 > v.begin() + j );
+	  VERIFY (v.begin() + j < v.begin() + j + 1 );
+	  VERIFY (v.begin() + j >= v.begin() );
+	  VERIFY (v.begin() <= v.begin() + j );
+	  VERIFY( v.begin() + j != v.end() );
+	  VERIFY( v.begin() + j - v.begin() == j );
+	  VERIFY( v.end() - (v.begin() + j) == ranges::ssize(x) - j );
+	}
+      VERIFY( v.begin() + j == v.end() );
+    }
+}
+
+int
+main()
+{
+  static_assert(test01());
+
+  test02<test_input_range>();
+  test02<test_forward_range>();
+  test02<test_bidirectional_range>();
+  test02<test_random_access_range>();
+}
diff --git a/libstdc++-v3/testsuite/std/ranges/version_c++23.cc b/libstdc++-v3/testsuite/std/ranges/version_c++23.cc
index 9970301cb5f..fa010bf166b 100644
--- a/libstdc++-v3/testsuite/std/ranges/version_c++23.cc
+++ b/libstdc++-v3/testsuite/std/ranges/version_c++23.cc
@@ -44,3 +44,7 @@
 #if __cpp_lib_ranges_as_rvalue != 202207L
 # error "Feature-test macro __cpp_lib_ranges_as_rvalue has wrong value in <version>"
 #endif
+
+#if __cpp_lib_ranges_enumerate != 202302L
+# error "Feature-test macro __cpp_lib_ranges_enumerate has wrong value in <version>"
+#endif