[PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4

[PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4

[Patrick Palka]

This also implements the proposed resolutions of the tentatively ready
LWG issues 3760 and 3761.

I'm not sure how/if we should implement the recommended practice of:

  difference_type should be the smallest signed-integer-like type that
  is sufficiently wide to store the product of the maximum sizes of all
  underlying ranges if such a type exists

because for e.g.

  extern std::vector<int> x, y;
  auto v = views::cartesian_product(x, y);

IIUC it'd mean difference_type should be __int128 or so, which seems
quite wasteful: in practice the size of the cartesian product probably
won't exceed the precision of say ptrdiff_t, and it's probably also not
worth adding logic for using less precision than that either.  So this
patch chooses defines difference_type as

  common_type_t<ptrdiff_t, range_difference_t<_First>, range_difference_t<_Vs>...>

which should mean it's least as large as the difference_type of each
underlying range, and at least as large as ptrdiff_t.  If overflow
occurs due to this choice of difference_type, this patch has debug mode
checks to catch this.

Tested on x86_64-pc-linux-gnu, does this look OK for trunk?

libstdc++-v3/ChangeLog:

	* include/std/ranges (__maybe_const_t): New alias for
	__detail::__maybe_const_t.
	(__detail::__cartesian_product_is_random_access): Define.
	(__detail::__cartesian_product_common_arg): Define.
	(__detail::__cartesian_product_is_bidirectional): Define.
	(__detail::__cartesian_product_is_common): Define.
	(__detail::__cartesian_product_is_sized): Define.
	(__detail::__cartesian_is_sized_sentinel): Define.
	(__detail::__cartesian_common_arg_end): Define.
	(cartesian_product_view): Define.
	(cartesian_product_view::_Iterator): Define.
	(views::__detail::__can_cartesian_product_view): Define.
	(views::_Cartesian_product, views::cartesian_product): Define.
	* testsuite/std/ranges/cartesian_product/1.cc: New test.
---
 libstdc++-v3/include/std/ranges               | 500 ++++++++++++++++++
 .../std/ranges/cartesian_product/1.cc         | 162 ++++++
 2 files changed, 662 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index a55e9e7f760..771da97ed6d 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -829,6 +829,9 @@ namespace __detail
 
 } // namespace __detail
 
+// Shorthand for __detail::__maybe_const_t.
+using __detail::__maybe_const_t;
+
 namespace views::__adaptor
 {
   // True if the range adaptor _Adaptor can be applied with _Args.
@@ -7973,6 +7976,503 @@ namespace views::__adaptor
 
     inline constexpr _Stride stride;
   }
+
+  namespace __detail
+  {
+    template<bool _Const, typename _First, typename... _Vs>
+      concept __cartesian_product_is_random_access
+	= (random_access_range<__maybe_const_t<_Const, _First>>
+	   && ...
+	   && (random_access_range<__maybe_const_t<_Const, _Vs>>
+	       && sized_range<__maybe_const_t<_Const, _Vs>>));
+
+    template<typename _Range>
+      concept __cartesian_product_common_arg = common_range<_Range>
+	|| (sized_range<_Range> && random_access_range<_Range>);
+
+    template<bool _Const, typename _First, typename... _Vs>
+      concept __cartesian_product_is_bidirectional
+	= (bidirectional_range<__maybe_const_t<_Const, _First>>
+	   && ...
+	   && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
+	       && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
+
+    template<typename _First, typename... _Vs>
+      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
+
+    template<typename... _Vs>
+      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
+
+    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
+      concept __cartesian_is_sized_sentinel
+      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
+			    iterator_t<__maybe_const_t<_Const, _First>>>
+	 && ...
+	 && (sized_range<__maybe_const_t<_Const, _Vs>>
+	     && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
+				   iterator_t<__maybe_const_t<_Const, _Vs>>>));
+
+    template<__cartesian_product_common_arg _Range>
+      constexpr auto
+      __cartesian_common_arg_end(_Range& __r)
+      {
+	if constexpr (common_range<_Range>)
+	  return ranges::end(__r);
+	else
+	  return ranges::begin(__r) + ranges::distance(__r);
+      }
+  } // namespace __detail
+
+  template<input_range _First, forward_range... _Vs>
+    requires (view<_First> && ... && view<_Vs>)
+  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
+  {
+    tuple<_First, _Vs...> _M_bases;
+
+    template<bool> class _Iterator;
+
+    static auto
+    _S_difference_type()
+    {
+      // TODO: Implement the recommended practice of using the smallest
+      // sufficiently wide type according to the maximum sizes of the
+      // underlying ranges?
+      return common_type_t<ptrdiff_t,
+			   range_difference_t<_First>,
+			   range_difference_t<_Vs>...>{};
+    }
+
+  public:
+    cartesian_product_view() = default;
+
+    constexpr explicit
+    cartesian_product_view(_First __first, _Vs... __rest)
+    : _M_bases(std::move(__first), std::move(__rest)...)
+    { }
+
+    constexpr _Iterator<false>
+    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
+    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
+
+    constexpr _Iterator<true>
+    begin() const requires (range<const _First> && ... && range<const _Vs>)
+    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
+
+    constexpr _Iterator<false>
+    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
+		    && __detail::__cartesian_product_is_common<_First, _Vs...>)
+    {
+      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
+	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
+      }(make_index_sequence<sizeof...(_Vs)>{});
+
+      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
+      if (!__empty_tail)
+	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
+      return _Iterator<false>{*this, std::move(__it)};
+    }
+
+    constexpr _Iterator<true>
+    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
+    {
+      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
+	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
+      }(make_index_sequence<sizeof...(_Vs)>{});
+
+      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
+      if (!__empty_tail)
+	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
+      return _Iterator<true>{*this, std::move(__it)};
+    }
+
+    constexpr default_sentinel_t
+    end() const noexcept
+    { return default_sentinel; }
+
+    constexpr auto
+    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
+    {
+      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+#ifdef _GLIBCXX_ASSERTIONS
+	_ST __sz = 1;
+	bool __overflow
+	  = (__builtin_mul_overflow(__sz,
+				    static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
+				    &__sz)
+	     || ...);
+	__glibcxx_assert(!__overflow);
+	return __sz;
+#else
+	return (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
+#endif
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+    constexpr auto
+    size() const requires __detail::__cartesian_product_is_sized<const _First, const _Vs...>
+    {
+      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+#ifdef _GLIBCXX_ASSERTIONS
+	_ST __sz = 1;
+	bool __overflow
+	  = (__builtin_mul_overflow(__sz,
+				    static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
+				    &__sz)
+	     || ...);
+	__glibcxx_assert(!__overflow);
+	return __sz;
+#else
+	return (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
+#endif
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+  };
+
+  template<typename... _Vs>
+    cartesian_product_view(_Vs&&...) -> cartesian_product_view<views::all_t<_Vs>...>;
+
+  template<input_range _First, forward_range... _Vs>
+    requires (view<_First> && ... && view<_Vs>)
+  template<bool _Const>
+  class cartesian_product_view<_First, _Vs...>::_Iterator
+  {
+    using _Parent = __maybe_const_t<_Const, cartesian_product_view>;
+    _Parent* _M_parent = nullptr;
+    __detail::__tuple_or_pair_t<iterator_t<__maybe_const_t<_Const, _First>>,
+				iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current;
+
+    template<size_t _Nm = sizeof...(_Vs)>
+    constexpr void
+    _M_next()
+    {
+      auto& __it = std::get<_Nm>(_M_current);
+      ++__it;
+      if constexpr (_Nm > 0)
+	if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases)))
+	  {
+	    __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases));
+	    _M_next<_Nm - 1>();
+	  }
+    }
+
+    template<size_t _Nm = sizeof...(_Vs)>
+    constexpr void
+    _M_prev()
+    {
+      auto& __it = std::get<_Nm>(_M_current);
+      if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases)))
+	{
+	  __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases));
+	  if constexpr (_Nm > 0)
+	    _M_prev<_Nm - 1>();
+	}
+      --__it;
+    }
+
+    constexpr
+    _Iterator(_Parent& __parent, decltype(_M_current) __current)
+    : _M_parent(std::__addressof(__parent)),
+      _M_current(std::move(__current))
+    { }
+
+    static auto
+    _S_iter_concept()
+    {
+      if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>)
+	return random_access_iterator_tag{};
+      else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>)
+	return bidirectional_iterator_tag{};
+      else if constexpr (forward_range<__maybe_const_t<_Const, _First>>)
+	return forward_iterator_tag{};
+      else
+	return input_iterator_tag{};
+    }
+
+    friend cartesian_product_view;
+
+  public:
+    using iterator_category = input_iterator_tag;
+    using iterator_concept = decltype(_S_iter_concept());
+    using value_type
+      = __detail::__tuple_or_pair_t<range_value_t<__maybe_const_t<_Const, _First>>,
+				    range_value_t<__maybe_const_t<_Const, _Vs>>...>;
+    using reference
+      = __detail::__tuple_or_pair_t<range_reference_t<__maybe_const_t<_Const, _First>>,
+				    range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
+    using difference_type = decltype(cartesian_product_view::_S_difference_type());
+
+    _Iterator() requires forward_range<__maybe_const_t<_Const, _First>> = default;
+
+    constexpr
+    _Iterator(_Iterator<!_Const> __i)
+      requires _Const
+	&& (convertible_to<iterator_t<_First>, iterator_t<const _First>>
+	    && ... && convertible_to<iterator_t<_Vs>, iterator_t<const _Vs>>)
+    : _M_parent(std::__addressof(__i._M_parent)),
+      _M_current(std::move(__i._M_current))
+    { }
+
+    constexpr auto
+    operator*() const
+    {
+      auto __f = [](auto& __i) -> decltype(auto) {
+	return *__i;
+      };
+      return __detail::__tuple_transform(__f, _M_current);
+    }
+
+    constexpr _Iterator&
+    operator++()
+    {
+      _M_next();
+      return *this;
+    }
+
+    constexpr void
+    operator++(int)
+    { ++*this; }
+
+    constexpr _Iterator
+    operator++(int) requires forward_range<__maybe_const_t<_Const, _First>>
+    {
+      auto __tmp = *this;
+      ++*this;
+      return __tmp;
+    }
+
+    constexpr _Iterator&
+    operator--()
+      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
+    {
+      _M_prev();
+      return *this;
+    }
+
+    constexpr _Iterator
+    operator--(int)
+      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
+    {
+      auto __tmp = *this;
+      --*this;
+      return __tmp;
+    }
+
+  private:
+    template<size_t _Nm = sizeof...(_Vs)>
+    constexpr void
+    _M_advance(difference_type __x)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    {
+      if (__x == 1)
+	_M_next<_Nm>();
+      else if (__x == -1)
+	_M_prev<_Nm>();
+      else if (__x != 0)
+	{
+	  // Constant time iterator addition.
+	  auto& __r = std::get<_Nm>(_M_parent->_M_bases);
+	  auto& __it = std::get<_Nm>(_M_current);
+	  if constexpr (_Nm == 0)
+	    {
+#ifdef _GLIBCXX_ASSERTIONS
+	      auto __size = ranges::ssize(__r);
+	      auto __begin = ranges::begin(__r);
+	      auto __offset = __it - __begin;
+	      __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size);
+#endif
+	      __it += __x;
+	    }
+	  else
+	    {
+	      auto __size = ranges::ssize(__r);
+	      auto __begin = ranges::begin(__r);
+	      auto __offset = __it - __begin;
+	      __offset += __x;
+	      __x = __offset / __size;
+	      __offset %= __size;
+	      if (__offset < 0)
+		{
+		  __offset = __size + __offset;
+		  --__x;
+		}
+	      __it = __begin + __offset;
+	      _M_advance<_Nm - 1>(__x);
+	    }
+	}
+    }
+
+  public:
+    constexpr _Iterator&
+    operator+=(difference_type __x)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    {
+      _M_advance(__x);
+      return *this;
+    }
+
+    constexpr _Iterator&
+    operator-=(difference_type __x)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return *this += -__x; }
+
+    constexpr reference
+    operator[](difference_type __n) const
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return *((*this) + __n); }
+
+    friend constexpr bool
+    operator==(const _Iterator& __x, const _Iterator& __y)
+      requires equality_comparable<iterator_t<__maybe_const_t<_Const, _First>>>
+    { return __x._M_current == __y._M_current; }
+
+    friend constexpr bool
+    operator==(const _Iterator& __x, default_sentinel_t)
+    {
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+	return ((std::get<_Is>(__x._M_current)
+		 == ranges::end(std::get<_Is>(__x._M_parent->_M_bases)))
+		|| ...);
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+    friend constexpr auto
+    operator<=>(const _Iterator& __x, const _Iterator& __y)
+      requires __detail::__all_random_access<_Const, _First, _Vs...>
+    { return __x._M_current <=> __y._M_current; }
+
+    friend constexpr _Iterator
+    operator+(_Iterator __x, difference_type __y)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return __x += __y; }
+
+    friend constexpr _Iterator
+    operator+(difference_type __x, const _Iterator& __y)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return __y + __x; }
+
+    friend constexpr _Iterator
+    operator-(_Iterator __x, difference_type __y)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return __x -= __y; }
+
+    friend constexpr difference_type
+    operator-(const _Iterator& __x, const _Iterator& __y)
+      requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...>
+    { return __x._M_distance_from(__y._M_current); }
+
+    friend constexpr difference_type
+    operator-(const _Iterator& __i, default_sentinel_t)
+      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
+    {
+      tuple __end_tuple = [&]<size_t... _Is>(index_sequence<_Is...>) {
+	return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)),
+		     ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...};
+      }(make_index_sequence<sizeof...(_Vs)>{});
+      return __i._M_distance_from(__end_tuple);
+    }
+
+    friend constexpr difference_type
+    operator-(default_sentinel_t, const _Iterator& __i)
+      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
+    { return -(__i - default_sentinel); }
+
+    friend constexpr auto
+    iter_move(const _Iterator& __i)
+    { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
+
+    friend constexpr void
+    iter_swap(const _Iterator& __l, const _Iterator& __r)
+      requires (indirectly_swappable<iterator_t<__maybe_const_t<_Const, _First>>>
+		&& ...
+		&& indirectly_swappable<iterator_t<__maybe_const_t<_Const, _Vs>>>)
+    {
+      [&]<size_t... _Is>(index_sequence<_Is...>) {
+	(ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+  private:
+    template<typename _Tuple>
+    constexpr difference_type
+    _M_distance_from(const _Tuple& __t) const
+    {
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+	difference_type __sum = static_cast<difference_type>(0);
+#ifdef _GLIBCXX_ASSERTIONS
+	bool __overflow
+	  = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t) &__sum)
+	     || ...);
+	__glibcxx_assert(!__overflow);
+#else
+	__sum = (_M_scaled_distance<_Is>(__t) + ...);
+#endif
+	return __sum;
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+    template<size_t _Nm, typename _Tuple>
+    constexpr difference_type
+    _M_scaled_distance(const _Tuple& __t) const
+    {
+      auto __dist = static_cast<difference_type>(std::get<_Nm>(_M_current)
+						 - std::get<_Nm>(__t));
+#ifdef _GLIBCXX_ASSERTIONS
+      bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist);
+      __glibcxx_assert(!__overflow);
+#else
+      __dist *= _M_scaled_size<_Nm+1>();
+#endif
+      return __dist;
+    }
+
+    template<size_t _Nm>
+    constexpr difference_type
+    _M_scaled_size() const
+    {
+      if constexpr (_Nm <= sizeof...(_Vs))
+	{
+	  auto __size = static_cast<difference_type>(ranges::size
+						     (std::get<_Nm>(_M_parent->_M_bases)));
+#ifdef _GLIBCXX_ASSERTIONS
+	  bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size);
+	  __glibcxx_assert(!__overflow);
+#else
+	  __size *= _M_scaled_size<_Nm+1>();
+#endif
+	  return __size;
+	}
+      else
+	return static_cast<difference_type>(1);
+    }
+  };
+
+  namespace views
+  {
+    namespace __detail
+    {
+      template<typename... _Ts>
+	concept __can_cartesian_product_view
+	  = requires { cartesian_product_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
+    }
+
+    struct _CartesianProduct
+    {
+      template<typename... _Ts>
+	requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>)
+	constexpr auto
+	operator() [[nodiscard]] (_Ts&&... __ts) const
+	{
+	  if constexpr (sizeof...(_Ts) == 0)
+	    return views::empty<tuple<>>;
+	  else
+	    return cartesian_product_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
+	}
+    };
+
+    inline constexpr _CartesianProduct cartesian_product;
+  }
 #endif // C++23
 } // namespace ranges
 
diff --git a/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
new file mode 100644
index 00000000000..2e4d80b0399
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
@@ -0,0 +1,162 @@
+// { 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()
+{
+  int x[] = {1, 2, 3};
+  int y[] = {4, 5, 6};
+  int z[] = {7, 8};
+  int w[] = {9};
+
+  auto v0 = views::cartesian_product();
+  VERIFY( ranges::end(v0) - ranges::begin(v0) == 0 );
+  VERIFY( ranges::size(v0) == 0 );
+  VERIFY( ranges::empty(v0) );
+
+  auto v1 = views::cartesian_product(x);
+  VERIFY( ranges::end(v1) - ranges::begin(v1) == 3 );
+  VERIFY( ranges::size(v1) == 3 );
+  VERIFY( ranges::equal(v1 | views::keys, x) );
+  VERIFY( std::get<0>(v1[0]) == 1 );
+  VERIFY( std::get<0>(v1[1]) == 2 );
+  VERIFY( std::get<0>(v1[2]) == 3 );
+  VERIFY( ranges::equal(v1 | views::reverse | views::keys, x | views::reverse));
+
+  auto v2 = views::cartesian_product(x, y);
+  VERIFY( ranges::size(v2) == 9 );
+  VERIFY( ranges::end(v2) - ranges::begin(v2) == 9 );
+  VERIFY( ranges::equal(v2 | views::keys,   (int[]){1, 1, 1, 2, 2, 2, 3, 3, 3}));
+  VERIFY( ranges::equal(v2 | views::values, (int[]){4, 5, 6, 4, 5, 6, 4, 5, 6}));
+  VERIFY( ranges::equal(v2 | views::reverse | views::keys,   (int[]){3, 3, 3, 2, 2, 2, 1, 1, 1}) );
+  VERIFY( ranges::equal(v2 | views::reverse | views::values, (int[]){6, 5, 4, 6, 5, 4, 6, 5, 4}) );
+
+  auto v3 = views::cartesian_product(x, y, z);
+  VERIFY( ranges::size(v3) == 18 );
+  VERIFY( ranges::equal(v3, (std::tuple<int,int,int>[]){{1,4,7}, {1,4,8}, {1,5,7}, {1,5,8},
+							{1,6,7}, {1,6,8}, {2,4,7}, {2,4,8},
+							{2,5,7}, {2,5,8}, {2,6,7}, {2,6,8},
+							{3,4,7}, {3,4,8}, {3,5,7}, {3,5,8},
+							{3,6,7}, {3,6,8}}) );
+
+  auto v4 = views::cartesian_product(x, y, z, w);
+  VERIFY( ranges::size(v4) == 18 );
+  VERIFY( ranges::equal(v4 | views::elements<3>, views::repeat(9, 18)) );
+
+  auto i4 = v4.begin(), j4 = i4 + 1;
+  VERIFY( j4 > i4 );
+  VERIFY( i4[0] == std::tuple(1, 4, 7, 9) );
+  VERIFY( i4 + 18 == v4.end() );
+  i4 += 5;
+  VERIFY( i4 != v4.begin() );
+  VERIFY( i4 - 5 == v4.begin() );
+  VERIFY( *i4 == std::tuple(1, 6, 8, 9) );
+  VERIFY( i4 - 5 != i4 );
+  i4 -= 3;
+  VERIFY( *i4 == std::tuple(1, 5, 7, 9) );
+  VERIFY( j4 + 1 == i4 );
+  ranges::iter_swap(i4, j4);
+  VERIFY( *j4 == std::tuple(1, 5, 7, 9) );
+  VERIFY( *i4 == std::tuple(1, 4, 8, 9) );
+
+  return true;
+}
+
+void
+test02()
+{
+  int x[] = {1, 2};
+  __gnu_test::test_input_range<int> rx(x);
+  auto v = views::cartesian_product(rx, x);
+  auto i = v.begin();
+  std::default_sentinel_t s = v.end();
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 1 );
+  ++i;
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 2 );
+  ++i;
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 1 );
+  ++i;
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 2 );
+  ++i;
+  VERIFY( i == s );
+}
+
+void
+test03()
+{
+  int x[] = {1, 2};
+  __gnu_test::test_input_range<int> rx(x);
+  auto v = views::cartesian_product(views::counted(rx.begin(), 2), x);
+  VERIFY( v.size() == 4 );
+  VERIFY( std::as_const(v).size() == 4 );
+  auto i = v.begin();
+  std::default_sentinel_t s = v.end();
+  VERIFY( i - s == -4 );
+  VERIFY( s - i == 4 );
+  ++i;
+  VERIFY( i - s == -3 );
+  VERIFY( s - i == 3 );
+  ++i;
+  VERIFY( i - s == -2 );
+  VERIFY( s - i == 2 );
+  ++i;
+  VERIFY( i - s == -1 );
+  VERIFY( s - i == 1 );
+  ++i;
+  VERIFY( i - s == 0 );
+  VERIFY( s - i == 0 );
+}
+
+void
+test04()
+{
+  // Exhaustively verify correctness of our iterator addition implementation
+  // (which runs in constant time) for this 18-element cartesian_product_view.
+  int x[] = {1, 2, 3};
+  int y[] = {4, 5, 6};
+  int z[] = {7, 8};
+  int w[] = {9};
+  auto v = views::cartesian_product(x, y, z, w);
+
+  for (int i = 0; i <= ranges::ssize(v); i++)
+    for (int j = 0; i + j <= ranges::ssize(v); j++)
+      {
+	auto b1 = v.begin();
+	for (int k = 0; k < i + j; k++)
+	  ++b1;
+	VERIFY( b1 - v.begin() == i + j );
+	auto b2 = (v.begin() + i) + j;
+	auto b3 = v.begin() + (i + j);
+	VERIFY( b1 == b2 && b2 == b3 );
+
+	auto e1 = v.end();
+	for (int k = 0; k < i + j; k++)
+	  --e1;
+	VERIFY( v.end() - e1 == i + j );
+	auto e2 = (v.end() - i) - j;
+	auto e3 = v.end() - (i + j);
+	VERIFY( e1 == e2 && e2 == e3 );
+      }
+}
+
+int
+main()
+{
+  static_assert(test01());
+  test02();
+  test03();
+  test04();
+}
-- 
2.38.1.175.gdb29e6bbae

Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4

[Patrick Palka]

On Thu, 27 Oct 2022, Patrick Palka wrote:

> This also implements the proposed resolutions of the tentatively ready
> LWG issues 3760 and 3761.
> 
> I'm not sure how/if we should implement the recommended practice of:
> 
>   difference_type should be the smallest signed-integer-like type that
>   is sufficiently wide to store the product of the maximum sizes of all
>   underlying ranges if such a type exists
> 
> because for e.g.
> 
>   extern std::vector<int> x, y;
>   auto v = views::cartesian_product(x, y);
> 
> IIUC it'd mean difference_type should be __int128 or so, which seems
> quite wasteful: in practice the size of the cartesian product probably
> won't exceed the precision of say ptrdiff_t, and it's probably also not
> worth adding logic for using less precision than that either.  So this
> patch chooses defines difference_type as
> 
>   common_type_t<ptrdiff_t, range_difference_t<_First>, range_difference_t<_Vs>...>
> 
> which should mean it's least as large as the difference_type of each
> underlying range, and at least as large as ptrdiff_t.  If overflow
> occurs due to this choice of difference_type, this patch has debug mode
> checks to catch this.
> 
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> 
> libstdc++-v3/ChangeLog:
> 
> 	* include/std/ranges (__maybe_const_t): New alias for
> 	__detail::__maybe_const_t.
> 	(__detail::__cartesian_product_is_random_access): Define.
> 	(__detail::__cartesian_product_common_arg): Define.
> 	(__detail::__cartesian_product_is_bidirectional): Define.
> 	(__detail::__cartesian_product_is_common): Define.
> 	(__detail::__cartesian_product_is_sized): Define.
> 	(__detail::__cartesian_is_sized_sentinel): Define.
> 	(__detail::__cartesian_common_arg_end): Define.
> 	(cartesian_product_view): Define.
> 	(cartesian_product_view::_Iterator): Define.
> 	(views::__detail::__can_cartesian_product_view): Define.
> 	(views::_Cartesian_product, views::cartesian_product): Define.
> 	* testsuite/std/ranges/cartesian_product/1.cc: New test.
> ---
>  libstdc++-v3/include/std/ranges               | 500 ++++++++++++++++++
>  .../std/ranges/cartesian_product/1.cc         | 162 ++++++
>  2 files changed, 662 insertions(+)
>  create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> 
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index a55e9e7f760..771da97ed6d 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -829,6 +829,9 @@ namespace __detail
>  
>  } // namespace __detail
>  
> +// Shorthand for __detail::__maybe_const_t.
> +using __detail::__maybe_const_t;
> +
>  namespace views::__adaptor
>  {
>    // True if the range adaptor _Adaptor can be applied with _Args.
> @@ -7973,6 +7976,503 @@ namespace views::__adaptor
>  
>      inline constexpr _Stride stride;
>    }
> +
> +  namespace __detail
> +  {
> +    template<bool _Const, typename _First, typename... _Vs>
> +      concept __cartesian_product_is_random_access
> +	= (random_access_range<__maybe_const_t<_Const, _First>>
> +	   && ...
> +	   && (random_access_range<__maybe_const_t<_Const, _Vs>>
> +	       && sized_range<__maybe_const_t<_Const, _Vs>>));
> +
> +    template<typename _Range>
> +      concept __cartesian_product_common_arg = common_range<_Range>
> +	|| (sized_range<_Range> && random_access_range<_Range>);
> +
> +    template<bool _Const, typename _First, typename... _Vs>
> +      concept __cartesian_product_is_bidirectional
> +	= (bidirectional_range<__maybe_const_t<_Const, _First>>
> +	   && ...
> +	   && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> +	       && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
> +
> +    template<typename _First, typename... _Vs>
> +      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
> +
> +    template<typename... _Vs>
> +      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> +
> +    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
> +      concept __cartesian_is_sized_sentinel
> +      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
> +			    iterator_t<__maybe_const_t<_Const, _First>>>
> +	 && ...
> +	 && (sized_range<__maybe_const_t<_Const, _Vs>>
> +	     && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
> +				   iterator_t<__maybe_const_t<_Const, _Vs>>>));
> +
> +    template<__cartesian_product_common_arg _Range>
> +      constexpr auto
> +      __cartesian_common_arg_end(_Range& __r)
> +      {
> +	if constexpr (common_range<_Range>)
> +	  return ranges::end(__r);
> +	else
> +	  return ranges::begin(__r) + ranges::distance(__r);
> +      }
> +  } // namespace __detail
> +
> +  template<input_range _First, forward_range... _Vs>
> +    requires (view<_First> && ... && view<_Vs>)
> +  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
> +  {
> +    tuple<_First, _Vs...> _M_bases;
> +
> +    template<bool> class _Iterator;
> +
> +    static auto
> +    _S_difference_type()
> +    {
> +      // TODO: Implement the recommended practice of using the smallest
> +      // sufficiently wide type according to the maximum sizes of the
> +      // underlying ranges?
> +      return common_type_t<ptrdiff_t,
> +			   range_difference_t<_First>,
> +			   range_difference_t<_Vs>...>{};
> +    }
> +
> +  public:
> +    cartesian_product_view() = default;
> +
> +    constexpr explicit
> +    cartesian_product_view(_First __first, _Vs... __rest)
> +    : _M_bases(std::move(__first), std::move(__rest)...)
> +    { }
> +
> +    constexpr _Iterator<false>
> +    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> +    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> +
> +    constexpr _Iterator<true>
> +    begin() const requires (range<const _First> && ... && range<const _Vs>)
> +    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> +
> +    constexpr _Iterator<false>
> +    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> +		    && __detail::__cartesian_product_is_common<_First, _Vs...>)
> +    {
> +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> +	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +
> +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> +      if (!__empty_tail)
> +	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> +      return _Iterator<false>{*this, std::move(__it)};
> +    }
> +
> +    constexpr _Iterator<true>
> +    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
> +    {
> +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> +	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +
> +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> +      if (!__empty_tail)
> +	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> +      return _Iterator<true>{*this, std::move(__it)};
> +    }
> +
> +    constexpr default_sentinel_t
> +    end() const noexcept
> +    { return default_sentinel; }
> +
> +    constexpr auto
> +    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
> +    {
> +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +#ifdef _GLIBCXX_ASSERTIONS
> +	_ST __sz = 1;
> +	bool __overflow
> +	  = (__builtin_mul_overflow(__sz,
> +				    static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> +				    &__sz)
> +	     || ...);
> +	__glibcxx_assert(!__overflow);
> +	return __sz;

__builtin_add/mul_overflow can't handle integer-class types so these
debug-mode checks must be disabled for such types.  Here's v2 which
corrects and adds a test for the case where the difference type is
an integer-class type:

-- >8 --

Subject: [PATCH] libstdc++: Implement ranges::cartesian_product_view from
 P2374R4

libstdc++-v3/ChangeLog:

	* include/std/ranges (__maybe_const_t): New alias for
	__detail::__maybe_const_t.
	(__detail::__cartesian_product_is_random_access): Define.
	(__detail::__cartesian_product_common_arg): Define.
	(__detail::__cartesian_product_is_bidirectional): Define.
	(__detail::__cartesian_product_is_common): Define.
	(__detail::__cartesian_product_is_sized): Define.
	(__detail::__cartesian_is_sized_sentinel): Define.
	(__detail::__cartesian_common_arg_end): Define.
	(cartesian_product_view): Define.
	(cartesian_product_view::_Iterator): Define.
	(views::__detail::__can_cartesian_product_view): Define.
	(views::_Cartesian_product, views::cartesian_product): Define.
	* testsuite/std/ranges/cartesian_product/1.cc: New test.
---
 libstdc++-v3/include/std/ranges               | 515 ++++++++++++++++++
 .../std/ranges/cartesian_product/1.cc         | 178 ++++++
 2 files changed, 693 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index a55e9e7f760..92d15c81e51 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -829,6 +829,9 @@ namespace __detail
 
 } // namespace __detail
 
+// Shorthand for __detail::__maybe_const_t.
+using __detail::__maybe_const_t;
+
 namespace views::__adaptor
 {
   // True if the range adaptor _Adaptor can be applied with _Args.
@@ -7973,6 +7976,518 @@ namespace views::__adaptor
 
     inline constexpr _Stride stride;
   }
+
+  namespace __detail
+  {
+    template<bool _Const, typename _First, typename... _Vs>
+      concept __cartesian_product_is_random_access
+	= (random_access_range<__maybe_const_t<_Const, _First>>
+	   && ...
+	   && (random_access_range<__maybe_const_t<_Const, _Vs>>
+	       && sized_range<__maybe_const_t<_Const, _Vs>>));
+
+    template<typename _Range>
+      concept __cartesian_product_common_arg = common_range<_Range>
+	|| (sized_range<_Range> && random_access_range<_Range>);
+
+    template<bool _Const, typename _First, typename... _Vs>
+      concept __cartesian_product_is_bidirectional
+	= (bidirectional_range<__maybe_const_t<_Const, _First>>
+	   && ...
+	   && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
+	       && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
+
+    template<typename _First, typename... _Vs>
+      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
+
+    template<typename... _Vs>
+      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
+
+    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
+      concept __cartesian_is_sized_sentinel
+      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
+			    iterator_t<__maybe_const_t<_Const, _First>>>
+	 && ...
+	 && (sized_range<__maybe_const_t<_Const, _Vs>>
+	     && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
+				   iterator_t<__maybe_const_t<_Const, _Vs>>>));
+
+    template<__cartesian_product_common_arg _Range>
+      constexpr auto
+      __cartesian_common_arg_end(_Range& __r)
+      {
+	if constexpr (common_range<_Range>)
+	  return ranges::end(__r);
+	else
+	  return ranges::begin(__r) + ranges::distance(__r);
+      }
+  } // namespace __detail
+
+  template<input_range _First, forward_range... _Vs>
+    requires (view<_First> && ... && view<_Vs>)
+  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
+  {
+    tuple<_First, _Vs...> _M_bases;
+
+    template<bool> class _Iterator;
+
+    static auto
+    _S_difference_type()
+    {
+      // TODO: Implement the recommended practice of using the smallest
+      // sufficiently wide type according to the maximum sizes of the
+      // underlying ranges?
+      return common_type_t<ptrdiff_t,
+			   range_difference_t<_First>,
+			   range_difference_t<_Vs>...>{};
+    }
+
+  public:
+    cartesian_product_view() = default;
+
+    constexpr explicit
+    cartesian_product_view(_First __first, _Vs... __rest)
+    : _M_bases(std::move(__first), std::move(__rest)...)
+    { }
+
+    constexpr _Iterator<false>
+    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
+    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
+
+    constexpr _Iterator<true>
+    begin() const requires (range<const _First> && ... && range<const _Vs>)
+    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
+
+    constexpr _Iterator<false>
+    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
+		    && __detail::__cartesian_product_is_common<_First, _Vs...>)
+    {
+      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
+	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
+      }(make_index_sequence<sizeof...(_Vs)>{});
+
+      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
+      if (!__empty_tail)
+	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
+      return _Iterator<false>{*this, std::move(__it)};
+    }
+
+    constexpr _Iterator<true>
+    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
+    {
+      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
+	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
+      }(make_index_sequence<sizeof...(_Vs)>{});
+
+      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
+      if (!__empty_tail)
+	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
+      return _Iterator<true>{*this, std::move(__it)};
+    }
+
+    constexpr default_sentinel_t
+    end() const noexcept
+    { return default_sentinel; }
+
+    constexpr auto
+    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
+    {
+      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+	auto __size = static_cast<_ST>(1);
+#ifdef _GLIBCXX_ASSERTIONS
+	if constexpr (integral<_ST>)
+	  {
+	    bool __overflow
+	      = (__builtin_mul_overflow(__size,
+					static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
+					&__size)
+		 || ...);
+	    __glibcxx_assert(!__overflow);
+	  }
+	else
+#endif
+	  __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
+	return __size;
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+    constexpr auto
+    size() const requires __detail::__cartesian_product_is_sized<const _First, const _Vs...>
+    {
+      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+	auto __size = static_cast<_ST>(1);
+#ifdef _GLIBCXX_ASSERTIONS
+	if constexpr (integral<_ST>)
+	  {
+	    bool __overflow
+	      = (__builtin_mul_overflow(__size,
+					static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
+					&__size)
+		 || ...);
+	    __glibcxx_assert(!__overflow);
+	  }
+	else
+#endif
+	  __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
+	return __size;
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+  };
+
+  template<typename... _Vs>
+    cartesian_product_view(_Vs&&...) -> cartesian_product_view<views::all_t<_Vs>...>;
+
+  template<input_range _First, forward_range... _Vs>
+    requires (view<_First> && ... && view<_Vs>)
+  template<bool _Const>
+  class cartesian_product_view<_First, _Vs...>::_Iterator
+  {
+    using _Parent = __maybe_const_t<_Const, cartesian_product_view>;
+    _Parent* _M_parent = nullptr;
+    __detail::__tuple_or_pair_t<iterator_t<__maybe_const_t<_Const, _First>>,
+				iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current;
+
+    template<size_t _Nm = sizeof...(_Vs)>
+    constexpr void
+    _M_next()
+    {
+      auto& __it = std::get<_Nm>(_M_current);
+      ++__it;
+      if constexpr (_Nm > 0)
+	if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases)))
+	  {
+	    __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases));
+	    _M_next<_Nm - 1>();
+	  }
+    }
+
+    template<size_t _Nm = sizeof...(_Vs)>
+    constexpr void
+    _M_prev()
+    {
+      auto& __it = std::get<_Nm>(_M_current);
+      if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases)))
+	{
+	  __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases));
+	  if constexpr (_Nm > 0)
+	    _M_prev<_Nm - 1>();
+	}
+      --__it;
+    }
+
+    constexpr
+    _Iterator(_Parent& __parent, decltype(_M_current) __current)
+    : _M_parent(std::__addressof(__parent)),
+      _M_current(std::move(__current))
+    { }
+
+    static auto
+    _S_iter_concept()
+    {
+      if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>)
+	return random_access_iterator_tag{};
+      else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>)
+	return bidirectional_iterator_tag{};
+      else if constexpr (forward_range<__maybe_const_t<_Const, _First>>)
+	return forward_iterator_tag{};
+      else
+	return input_iterator_tag{};
+    }
+
+    friend cartesian_product_view;
+
+  public:
+    using iterator_category = input_iterator_tag;
+    using iterator_concept = decltype(_S_iter_concept());
+    using value_type
+      = __detail::__tuple_or_pair_t<range_value_t<__maybe_const_t<_Const, _First>>,
+				    range_value_t<__maybe_const_t<_Const, _Vs>>...>;
+    using reference
+      = __detail::__tuple_or_pair_t<range_reference_t<__maybe_const_t<_Const, _First>>,
+				    range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
+    using difference_type = decltype(cartesian_product_view::_S_difference_type());
+
+    _Iterator() requires forward_range<__maybe_const_t<_Const, _First>> = default;
+
+    constexpr
+    _Iterator(_Iterator<!_Const> __i)
+      requires _Const
+	&& (convertible_to<iterator_t<_First>, iterator_t<const _First>>
+	    && ... && convertible_to<iterator_t<_Vs>, iterator_t<const _Vs>>)
+    : _M_parent(std::__addressof(__i._M_parent)),
+      _M_current(std::move(__i._M_current))
+    { }
+
+    constexpr auto
+    operator*() const
+    {
+      auto __f = [](auto& __i) -> decltype(auto) {
+	return *__i;
+      };
+      return __detail::__tuple_transform(__f, _M_current);
+    }
+
+    constexpr _Iterator&
+    operator++()
+    {
+      _M_next();
+      return *this;
+    }
+
+    constexpr void
+    operator++(int)
+    { ++*this; }
+
+    constexpr _Iterator
+    operator++(int) requires forward_range<__maybe_const_t<_Const, _First>>
+    {
+      auto __tmp = *this;
+      ++*this;
+      return __tmp;
+    }
+
+    constexpr _Iterator&
+    operator--()
+      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
+    {
+      _M_prev();
+      return *this;
+    }
+
+    constexpr _Iterator
+    operator--(int)
+      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
+    {
+      auto __tmp = *this;
+      --*this;
+      return __tmp;
+    }
+
+  private:
+    template<size_t _Nm = sizeof...(_Vs)>
+    constexpr void
+    _M_advance(difference_type __x)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    {
+      if (__x == 1)
+	_M_next<_Nm>();
+      else if (__x == -1)
+	_M_prev<_Nm>();
+      else if (__x != 0)
+	{
+	  // Constant time iterator addition.
+	  auto& __r = std::get<_Nm>(_M_parent->_M_bases);
+	  auto& __it = std::get<_Nm>(_M_current);
+	  if constexpr (_Nm == 0)
+	    {
+#ifdef _GLIBCXX_ASSERTIONS
+	      auto __size = ranges::ssize(__r);
+	      auto __begin = ranges::begin(__r);
+	      auto __offset = __it - __begin;
+	      __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size);
+#endif
+	      __it += __x;
+	    }
+	  else
+	    {
+	      auto __size = ranges::ssize(__r);
+	      auto __begin = ranges::begin(__r);
+	      auto __offset = __it - __begin;
+	      __offset += __x;
+	      __x = __offset / __size;
+	      __offset %= __size;
+	      if (__offset < 0)
+		{
+		  __offset = __size + __offset;
+		  --__x;
+		}
+	      __it = __begin + __offset;
+	      _M_advance<_Nm - 1>(__x);
+	    }
+	}
+    }
+
+  public:
+    constexpr _Iterator&
+    operator+=(difference_type __x)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    {
+      _M_advance(__x);
+      return *this;
+    }
+
+    constexpr _Iterator&
+    operator-=(difference_type __x)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return *this += -__x; }
+
+    constexpr reference
+    operator[](difference_type __n) const
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return *((*this) + __n); }
+
+    friend constexpr bool
+    operator==(const _Iterator& __x, const _Iterator& __y)
+      requires equality_comparable<iterator_t<__maybe_const_t<_Const, _First>>>
+    { return __x._M_current == __y._M_current; }
+
+    friend constexpr bool
+    operator==(const _Iterator& __x, default_sentinel_t)
+    {
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+	return ((std::get<_Is>(__x._M_current)
+		 == ranges::end(std::get<_Is>(__x._M_parent->_M_bases)))
+		|| ...);
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+    friend constexpr auto
+    operator<=>(const _Iterator& __x, const _Iterator& __y)
+      requires __detail::__all_random_access<_Const, _First, _Vs...>
+    { return __x._M_current <=> __y._M_current; }
+
+    friend constexpr _Iterator
+    operator+(_Iterator __x, difference_type __y)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return __x += __y; }
+
+    friend constexpr _Iterator
+    operator+(difference_type __x, const _Iterator& __y)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return __y + __x; }
+
+    friend constexpr _Iterator
+    operator-(_Iterator __x, difference_type __y)
+      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
+    { return __x -= __y; }
+
+    friend constexpr difference_type
+    operator-(const _Iterator& __x, const _Iterator& __y)
+      requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...>
+    { return __x._M_distance_from(__y._M_current); }
+
+    friend constexpr difference_type
+    operator-(const _Iterator& __i, default_sentinel_t)
+      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
+    {
+      tuple __end_tuple = [&]<size_t... _Is>(index_sequence<_Is...>) {
+	return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)),
+		     ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...};
+      }(make_index_sequence<sizeof...(_Vs)>{});
+      return __i._M_distance_from(__end_tuple);
+    }
+
+    friend constexpr difference_type
+    operator-(default_sentinel_t, const _Iterator& __i)
+      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
+    { return -(__i - default_sentinel); }
+
+    friend constexpr auto
+    iter_move(const _Iterator& __i)
+    { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
+
+    friend constexpr void
+    iter_swap(const _Iterator& __l, const _Iterator& __r)
+      requires (indirectly_swappable<iterator_t<__maybe_const_t<_Const, _First>>>
+		&& ...
+		&& indirectly_swappable<iterator_t<__maybe_const_t<_Const, _Vs>>>)
+    {
+      [&]<size_t... _Is>(index_sequence<_Is...>) {
+	(ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+  private:
+    template<typename _Tuple>
+    constexpr difference_type
+    _M_distance_from(const _Tuple& __t) const
+    {
+      return [&]<size_t... _Is>(index_sequence<_Is...>) {
+	auto __sum = static_cast<difference_type>(0);
+#ifdef _GLIBCXX_ASSERTIONS
+	if constexpr (integral<difference_type>)
+	  {
+	    bool __overflow
+	      = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t), &__sum)
+		 || ...);
+	    __glibcxx_assert(!__overflow);
+	  }
+	else
+#endif
+	  __sum = (_M_scaled_distance<_Is>(__t) + ...);
+	return __sum;
+      }(make_index_sequence<1 + sizeof...(_Vs)>{});
+    }
+
+    template<size_t _Nm, typename _Tuple>
+    constexpr difference_type
+    _M_scaled_distance(const _Tuple& __t) const
+    {
+      auto __dist = static_cast<difference_type>(std::get<_Nm>(_M_current)
+						 - std::get<_Nm>(__t));
+#ifdef _GLIBCXX_ASSERTIONS
+      if constexpr (integral<difference_type>)
+	{
+	  bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist);
+	  __glibcxx_assert(!__overflow);
+	}
+      else
+#endif
+	__dist *= _M_scaled_size<_Nm+1>();
+      return __dist;
+    }
+
+    template<size_t _Nm>
+    constexpr difference_type
+    _M_scaled_size() const
+    {
+      if constexpr (_Nm <= sizeof...(_Vs))
+	{
+	  auto __size = static_cast<difference_type>(ranges::size
+						     (std::get<_Nm>(_M_parent->_M_bases)));
+#ifdef _GLIBCXX_ASSERTIONS
+	  if constexpr (integral<difference_type>)
+	    {
+	      bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size);
+	      __glibcxx_assert(!__overflow);
+	    }
+	  else
+#endif
+	    __size *= _M_scaled_size<_Nm+1>();
+	  return __size;
+	}
+      else
+	return static_cast<difference_type>(1);
+    }
+  };
+
+  namespace views
+  {
+    namespace __detail
+    {
+      template<typename... _Ts>
+	concept __can_cartesian_product_view
+	  = requires { cartesian_product_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
+    }
+
+    struct _CartesianProduct
+    {
+      template<typename... _Ts>
+	requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>)
+	constexpr auto
+	operator() [[nodiscard]] (_Ts&&... __ts) const
+	{
+	  if constexpr (sizeof...(_Ts) == 0)
+	    return views::empty<tuple<>>;
+	  else
+	    return cartesian_product_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
+	}
+    };
+
+    inline constexpr _CartesianProduct cartesian_product;
+  }
 #endif // C++23
 } // namespace ranges
 
diff --git a/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
new file mode 100644
index 00000000000..5f1610d6458
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
@@ -0,0 +1,178 @@
+// { 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()
+{
+  int x[] = {1, 2, 3};
+  int y[] = {4, 5, 6};
+  int z[] = {7, 8};
+  int w[] = {9};
+
+  auto v0 = views::cartesian_product();
+  VERIFY( ranges::end(v0) - ranges::begin(v0) == 0 );
+  VERIFY( ranges::size(v0) == 0 );
+  VERIFY( ranges::empty(v0) );
+
+  auto v1 = views::cartesian_product(x);
+  VERIFY( ranges::end(v1) - ranges::begin(v1) == 3 );
+  VERIFY( ranges::size(v1) == 3 );
+  VERIFY( ranges::equal(v1 | views::keys, x) );
+  VERIFY( std::get<0>(v1[0]) == 1 );
+  VERIFY( std::get<0>(v1[1]) == 2 );
+  VERIFY( std::get<0>(v1[2]) == 3 );
+  VERIFY( ranges::equal(v1 | views::reverse | views::keys, x | views::reverse));
+
+  auto v2 = views::cartesian_product(x, y);
+  VERIFY( ranges::size(v2) == 9 );
+  VERIFY( ranges::end(v2) - ranges::begin(v2) == 9 );
+  VERIFY( ranges::equal(v2 | views::keys,   (int[]){1, 1, 1, 2, 2, 2, 3, 3, 3}));
+  VERIFY( ranges::equal(v2 | views::values, (int[]){4, 5, 6, 4, 5, 6, 4, 5, 6}));
+  VERIFY( ranges::equal(v2 | views::reverse | views::keys,   (int[]){3, 3, 3, 2, 2, 2, 1, 1, 1}) );
+  VERIFY( ranges::equal(v2 | views::reverse | views::values, (int[]){6, 5, 4, 6, 5, 4, 6, 5, 4}) );
+
+  auto v3 = views::cartesian_product(x, y, z);
+  VERIFY( ranges::size(v3) == 18 );
+  VERIFY( ranges::equal(v3, (std::tuple<int,int,int>[]){{1,4,7}, {1,4,8}, {1,5,7}, {1,5,8},
+							{1,6,7}, {1,6,8}, {2,4,7}, {2,4,8},
+							{2,5,7}, {2,5,8}, {2,6,7}, {2,6,8},
+							{3,4,7}, {3,4,8}, {3,5,7}, {3,5,8},
+							{3,6,7}, {3,6,8}}) );
+
+  auto v4 = views::cartesian_product(x, y, z, w);
+  VERIFY( ranges::size(v4) == 18 );
+  VERIFY( ranges::equal(v4 | views::elements<3>, views::repeat(9, 18)) );
+
+  auto i4 = v4.begin(), j4 = i4 + 1;
+  VERIFY( j4 > i4 );
+  VERIFY( i4[0] == std::tuple(1, 4, 7, 9) );
+  VERIFY( i4 + 18 == v4.end() );
+  i4 += 5;
+  VERIFY( i4 != v4.begin() );
+  VERIFY( i4 - 5 == v4.begin() );
+  VERIFY( *i4 == std::tuple(1, 6, 8, 9) );
+  VERIFY( i4 - 5 != i4 );
+  i4 -= 3;
+  VERIFY( *i4 == std::tuple(1, 5, 7, 9) );
+  VERIFY( j4 + 1 == i4 );
+  ranges::iter_swap(i4, j4);
+  VERIFY( *j4 == std::tuple(1, 5, 7, 9) );
+  VERIFY( *i4 == std::tuple(1, 4, 8, 9) );
+
+  return true;
+}
+
+void
+test02()
+{
+  int x[] = {1, 2};
+  __gnu_test::test_input_range<int> rx(x);
+  auto v = views::cartesian_product(rx, x);
+  auto i = v.begin();
+  std::default_sentinel_t s = v.end();
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 1 );
+  ++i;
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 2 );
+  ++i;
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 1 );
+  ++i;
+  VERIFY( i != s );
+  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 2 );
+  ++i;
+  VERIFY( i == s );
+}
+
+void
+test03()
+{
+  int x[] = {1, 2};
+  __gnu_test::test_input_range<int> rx(x);
+  auto v = views::cartesian_product(views::counted(rx.begin(), 2), x);
+  VERIFY( v.size() == 4 );
+  VERIFY( std::as_const(v).size() == 4 );
+  auto i = v.begin();
+  std::default_sentinel_t s = v.end();
+  VERIFY( i - s == -4 );
+  VERIFY( s - i == 4 );
+  ++i;
+  VERIFY( i - s == -3 );
+  VERIFY( s - i == 3 );
+  ++i;
+  VERIFY( i - s == -2 );
+  VERIFY( s - i == 2 );
+  ++i;
+  VERIFY( i - s == -1 );
+  VERIFY( s - i == 1 );
+  ++i;
+  VERIFY( i - s == 0 );
+  VERIFY( s - i == 0 );
+}
+
+void
+test04()
+{
+  // Exhaustively verify correctness of our iterator addition implementation
+  // (which runs in constant time) for this 18-element cartesian_product_view.
+  int x[] = {1, 2, 3};
+  int y[] = {4, 5, 6};
+  int z[] = {7, 8};
+  int w[] = {9};
+  auto v = views::cartesian_product(x, y, z, w);
+
+  for (int i = 0; i <= ranges::ssize(v); i++)
+    for (int j = 0; i + j <= ranges::ssize(v); j++)
+      {
+	auto b1 = v.begin();
+	for (int k = 0; k < i + j; k++)
+	  ++b1;
+	VERIFY( b1 - v.begin() == i + j );
+	auto b2 = (v.begin() + i) + j;
+	auto b3 = v.begin() + (i + j);
+	VERIFY( b1 == b2 && b2 == b3 );
+
+	auto e1 = v.end();
+	for (int k = 0; k < i + j; k++)
+	  --e1;
+	VERIFY( v.end() - e1 == i + j );
+	auto e2 = (v.end() - i) - j;
+	auto e3 = v.end() - (i + j);
+	VERIFY( e1 == e2 && e2 == e3 );
+      }
+}
+
+void
+test05()
+{
+#if __SIZEOF_INT128__
+  auto r = views::iota(__int128(0), __int128(5));
+#else
+  auto r = views::iota(0ll, 5ll);
+#endif
+  auto v = views::cartesian_product(r, r);
+  VERIFY( ranges::size(v) == 25 );
+  VERIFY( ranges::size(std::as_const(v)) == 25 );
+  VERIFY( v.end() - v.begin() == 25 );
+  VERIFY( v.begin() + ranges::size(v) - v.begin() == 25 );
+}
+
+int
+main()
+{
+  static_assert(test01());
+  test02();
+  test03();
+  test04();
+  test05();
+}
-- 
2.38.1.175.gdb29e6bbae

Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4

[Patrick Palka]

On Thu, 27 Oct 2022, Patrick Palka wrote:

> On Thu, 27 Oct 2022, Patrick Palka wrote:
> 
> > This also implements the proposed resolutions of the tentatively ready
> > LWG issues 3760 and 3761.
> > 
> > I'm not sure how/if we should implement the recommended practice of:
> > 
> >   difference_type should be the smallest signed-integer-like type that
> >   is sufficiently wide to store the product of the maximum sizes of all
> >   underlying ranges if such a type exists
> > 
> > because for e.g.
> > 
> >   extern std::vector<int> x, y;
> >   auto v = views::cartesian_product(x, y);
> > 
> > IIUC it'd mean difference_type should be __int128 or so, which seems
> > quite wasteful: in practice the size of the cartesian product probably
> > won't exceed the precision of say ptrdiff_t, and it's probably also not
> > worth adding logic for using less precision than that either.  So this
> > patch chooses defines difference_type as
> > 
> >   common_type_t<ptrdiff_t, range_difference_t<_First>, range_difference_t<_Vs>...>
> > 
> > which should mean it's least as large as the difference_type of each
> > underlying range, and at least as large as ptrdiff_t.  If overflow
> > occurs due to this choice of difference_type, this patch has debug mode
> > checks to catch this.
> > 
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> > 
> > libstdc++-v3/ChangeLog:
> > 
> > 	* include/std/ranges (__maybe_const_t): New alias for
> > 	__detail::__maybe_const_t.
> > 	(__detail::__cartesian_product_is_random_access): Define.
> > 	(__detail::__cartesian_product_common_arg): Define.
> > 	(__detail::__cartesian_product_is_bidirectional): Define.
> > 	(__detail::__cartesian_product_is_common): Define.
> > 	(__detail::__cartesian_product_is_sized): Define.
> > 	(__detail::__cartesian_is_sized_sentinel): Define.
> > 	(__detail::__cartesian_common_arg_end): Define.
> > 	(cartesian_product_view): Define.
> > 	(cartesian_product_view::_Iterator): Define.
> > 	(views::__detail::__can_cartesian_product_view): Define.
> > 	(views::_Cartesian_product, views::cartesian_product): Define.
> > 	* testsuite/std/ranges/cartesian_product/1.cc: New test.
> > ---
> >  libstdc++-v3/include/std/ranges               | 500 ++++++++++++++++++
> >  .../std/ranges/cartesian_product/1.cc         | 162 ++++++
> >  2 files changed, 662 insertions(+)
> >  create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> > 
> > diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> > index a55e9e7f760..771da97ed6d 100644
> > --- a/libstdc++-v3/include/std/ranges
> > +++ b/libstdc++-v3/include/std/ranges
> > @@ -829,6 +829,9 @@ namespace __detail
> >  
> >  } // namespace __detail
> >  
> > +// Shorthand for __detail::__maybe_const_t.
> > +using __detail::__maybe_const_t;
> > +
> >  namespace views::__adaptor
> >  {
> >    // True if the range adaptor _Adaptor can be applied with _Args.
> > @@ -7973,6 +7976,503 @@ namespace views::__adaptor
> >  
> >      inline constexpr _Stride stride;
> >    }
> > +
> > +  namespace __detail
> > +  {
> > +    template<bool _Const, typename _First, typename... _Vs>
> > +      concept __cartesian_product_is_random_access
> > +	= (random_access_range<__maybe_const_t<_Const, _First>>
> > +	   && ...
> > +	   && (random_access_range<__maybe_const_t<_Const, _Vs>>
> > +	       && sized_range<__maybe_const_t<_Const, _Vs>>));
> > +
> > +    template<typename _Range>
> > +      concept __cartesian_product_common_arg = common_range<_Range>
> > +	|| (sized_range<_Range> && random_access_range<_Range>);
> > +
> > +    template<bool _Const, typename _First, typename... _Vs>
> > +      concept __cartesian_product_is_bidirectional
> > +	= (bidirectional_range<__maybe_const_t<_Const, _First>>
> > +	   && ...
> > +	   && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> > +	       && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
> > +
> > +    template<typename _First, typename... _Vs>
> > +      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
> > +
> > +    template<typename... _Vs>
> > +      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> > +
> > +    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
> > +      concept __cartesian_is_sized_sentinel
> > +      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
> > +			    iterator_t<__maybe_const_t<_Const, _First>>>
> > +	 && ...
> > +	 && (sized_range<__maybe_const_t<_Const, _Vs>>
> > +	     && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
> > +				   iterator_t<__maybe_const_t<_Const, _Vs>>>));
> > +
> > +    template<__cartesian_product_common_arg _Range>
> > +      constexpr auto
> > +      __cartesian_common_arg_end(_Range& __r)
> > +      {
> > +	if constexpr (common_range<_Range>)
> > +	  return ranges::end(__r);
> > +	else
> > +	  return ranges::begin(__r) + ranges::distance(__r);
> > +      }
> > +  } // namespace __detail
> > +
> > +  template<input_range _First, forward_range... _Vs>
> > +    requires (view<_First> && ... && view<_Vs>)
> > +  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
> > +  {
> > +    tuple<_First, _Vs...> _M_bases;
> > +
> > +    template<bool> class _Iterator;
> > +
> > +    static auto
> > +    _S_difference_type()
> > +    {
> > +      // TODO: Implement the recommended practice of using the smallest
> > +      // sufficiently wide type according to the maximum sizes of the
> > +      // underlying ranges?
> > +      return common_type_t<ptrdiff_t,
> > +			   range_difference_t<_First>,
> > +			   range_difference_t<_Vs>...>{};
> > +    }
> > +
> > +  public:
> > +    cartesian_product_view() = default;
> > +
> > +    constexpr explicit
> > +    cartesian_product_view(_First __first, _Vs... __rest)
> > +    : _M_bases(std::move(__first), std::move(__rest)...)
> > +    { }
> > +
> > +    constexpr _Iterator<false>
> > +    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> > +    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> > +
> > +    constexpr _Iterator<true>
> > +    begin() const requires (range<const _First> && ... && range<const _Vs>)
> > +    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> > +
> > +    constexpr _Iterator<false>
> > +    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> > +		    && __detail::__cartesian_product_is_common<_First, _Vs...>)
> > +    {
> > +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> > +	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> > +      }(make_index_sequence<sizeof...(_Vs)>{});
> > +
> > +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> > +      if (!__empty_tail)
> > +	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> > +      return _Iterator<false>{*this, std::move(__it)};
> > +    }
> > +
> > +    constexpr _Iterator<true>
> > +    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
> > +    {
> > +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> > +	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> > +      }(make_index_sequence<sizeof...(_Vs)>{});
> > +
> > +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> > +      if (!__empty_tail)
> > +	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> > +      return _Iterator<true>{*this, std::move(__it)};
> > +    }
> > +
> > +    constexpr default_sentinel_t
> > +    end() const noexcept
> > +    { return default_sentinel; }
> > +
> > +    constexpr auto
> > +    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
> > +    {
> > +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> > +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> > +#ifdef _GLIBCXX_ASSERTIONS
> > +	_ST __sz = 1;
> > +	bool __overflow
> > +	  = (__builtin_mul_overflow(__sz,
> > +				    static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> > +				    &__sz)
> > +	     || ...);
> > +	__glibcxx_assert(!__overflow);
> > +	return __sz;
> 
> __builtin_add/mul_overflow can't handle integer-class types so these
> debug-mode checks must be disabled for such types.  Here's v2 which
> corrects and adds a test for the case where the difference type is
> an integer-class type:

Ping.

> 
> -- >8 --
> 
> Subject: [PATCH] libstdc++: Implement ranges::cartesian_product_view from
>  P2374R4
> 
> libstdc++-v3/ChangeLog:
> 
> 	* include/std/ranges (__maybe_const_t): New alias for
> 	__detail::__maybe_const_t.
> 	(__detail::__cartesian_product_is_random_access): Define.
> 	(__detail::__cartesian_product_common_arg): Define.
> 	(__detail::__cartesian_product_is_bidirectional): Define.
> 	(__detail::__cartesian_product_is_common): Define.
> 	(__detail::__cartesian_product_is_sized): Define.
> 	(__detail::__cartesian_is_sized_sentinel): Define.
> 	(__detail::__cartesian_common_arg_end): Define.
> 	(cartesian_product_view): Define.
> 	(cartesian_product_view::_Iterator): Define.
> 	(views::__detail::__can_cartesian_product_view): Define.
> 	(views::_Cartesian_product, views::cartesian_product): Define.
> 	* testsuite/std/ranges/cartesian_product/1.cc: New test.
> ---
>  libstdc++-v3/include/std/ranges               | 515 ++++++++++++++++++
>  .../std/ranges/cartesian_product/1.cc         | 178 ++++++
>  2 files changed, 693 insertions(+)
>  create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> 
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index a55e9e7f760..92d15c81e51 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -829,6 +829,9 @@ namespace __detail
>  
>  } // namespace __detail
>  
> +// Shorthand for __detail::__maybe_const_t.
> +using __detail::__maybe_const_t;
> +
>  namespace views::__adaptor
>  {
>    // True if the range adaptor _Adaptor can be applied with _Args.
> @@ -7973,6 +7976,518 @@ namespace views::__adaptor
>  
>      inline constexpr _Stride stride;
>    }
> +
> +  namespace __detail
> +  {
> +    template<bool _Const, typename _First, typename... _Vs>
> +      concept __cartesian_product_is_random_access
> +	= (random_access_range<__maybe_const_t<_Const, _First>>
> +	   && ...
> +	   && (random_access_range<__maybe_const_t<_Const, _Vs>>
> +	       && sized_range<__maybe_const_t<_Const, _Vs>>));
> +
> +    template<typename _Range>
> +      concept __cartesian_product_common_arg = common_range<_Range>
> +	|| (sized_range<_Range> && random_access_range<_Range>);
> +
> +    template<bool _Const, typename _First, typename... _Vs>
> +      concept __cartesian_product_is_bidirectional
> +	= (bidirectional_range<__maybe_const_t<_Const, _First>>
> +	   && ...
> +	   && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> +	       && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
> +
> +    template<typename _First, typename... _Vs>
> +      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
> +
> +    template<typename... _Vs>
> +      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> +
> +    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
> +      concept __cartesian_is_sized_sentinel
> +      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
> +			    iterator_t<__maybe_const_t<_Const, _First>>>
> +	 && ...
> +	 && (sized_range<__maybe_const_t<_Const, _Vs>>
> +	     && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
> +				   iterator_t<__maybe_const_t<_Const, _Vs>>>));
> +
> +    template<__cartesian_product_common_arg _Range>
> +      constexpr auto
> +      __cartesian_common_arg_end(_Range& __r)
> +      {
> +	if constexpr (common_range<_Range>)
> +	  return ranges::end(__r);
> +	else
> +	  return ranges::begin(__r) + ranges::distance(__r);
> +      }
> +  } // namespace __detail
> +
> +  template<input_range _First, forward_range... _Vs>
> +    requires (view<_First> && ... && view<_Vs>)
> +  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
> +  {
> +    tuple<_First, _Vs...> _M_bases;
> +
> +    template<bool> class _Iterator;
> +
> +    static auto
> +    _S_difference_type()
> +    {
> +      // TODO: Implement the recommended practice of using the smallest
> +      // sufficiently wide type according to the maximum sizes of the
> +      // underlying ranges?
> +      return common_type_t<ptrdiff_t,
> +			   range_difference_t<_First>,
> +			   range_difference_t<_Vs>...>{};
> +    }
> +
> +  public:
> +    cartesian_product_view() = default;
> +
> +    constexpr explicit
> +    cartesian_product_view(_First __first, _Vs... __rest)
> +    : _M_bases(std::move(__first), std::move(__rest)...)
> +    { }
> +
> +    constexpr _Iterator<false>
> +    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> +    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> +
> +    constexpr _Iterator<true>
> +    begin() const requires (range<const _First> && ... && range<const _Vs>)
> +    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> +
> +    constexpr _Iterator<false>
> +    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> +		    && __detail::__cartesian_product_is_common<_First, _Vs...>)
> +    {
> +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> +	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +
> +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> +      if (!__empty_tail)
> +	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> +      return _Iterator<false>{*this, std::move(__it)};
> +    }
> +
> +    constexpr _Iterator<true>
> +    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
> +    {
> +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> +	return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +
> +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> +      if (!__empty_tail)
> +	std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> +      return _Iterator<true>{*this, std::move(__it)};
> +    }
> +
> +    constexpr default_sentinel_t
> +    end() const noexcept
> +    { return default_sentinel; }
> +
> +    constexpr auto
> +    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
> +    {
> +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +	auto __size = static_cast<_ST>(1);
> +#ifdef _GLIBCXX_ASSERTIONS
> +	if constexpr (integral<_ST>)
> +	  {
> +	    bool __overflow
> +	      = (__builtin_mul_overflow(__size,
> +					static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> +					&__size)
> +		 || ...);
> +	    __glibcxx_assert(!__overflow);
> +	  }
> +	else
> +#endif
> +	  __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
> +	return __size;
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +    constexpr auto
> +    size() const requires __detail::__cartesian_product_is_sized<const _First, const _Vs...>
> +    {
> +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +	auto __size = static_cast<_ST>(1);
> +#ifdef _GLIBCXX_ASSERTIONS
> +	if constexpr (integral<_ST>)
> +	  {
> +	    bool __overflow
> +	      = (__builtin_mul_overflow(__size,
> +					static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> +					&__size)
> +		 || ...);
> +	    __glibcxx_assert(!__overflow);
> +	  }
> +	else
> +#endif
> +	  __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
> +	return __size;
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +  };
> +
> +  template<typename... _Vs>
> +    cartesian_product_view(_Vs&&...) -> cartesian_product_view<views::all_t<_Vs>...>;
> +
> +  template<input_range _First, forward_range... _Vs>
> +    requires (view<_First> && ... && view<_Vs>)
> +  template<bool _Const>
> +  class cartesian_product_view<_First, _Vs...>::_Iterator
> +  {
> +    using _Parent = __maybe_const_t<_Const, cartesian_product_view>;
> +    _Parent* _M_parent = nullptr;
> +    __detail::__tuple_or_pair_t<iterator_t<__maybe_const_t<_Const, _First>>,
> +				iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current;
> +
> +    template<size_t _Nm = sizeof...(_Vs)>
> +    constexpr void
> +    _M_next()
> +    {
> +      auto& __it = std::get<_Nm>(_M_current);
> +      ++__it;
> +      if constexpr (_Nm > 0)
> +	if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases)))
> +	  {
> +	    __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases));
> +	    _M_next<_Nm - 1>();
> +	  }
> +    }
> +
> +    template<size_t _Nm = sizeof...(_Vs)>
> +    constexpr void
> +    _M_prev()
> +    {
> +      auto& __it = std::get<_Nm>(_M_current);
> +      if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases)))
> +	{
> +	  __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases));
> +	  if constexpr (_Nm > 0)
> +	    _M_prev<_Nm - 1>();
> +	}
> +      --__it;
> +    }
> +
> +    constexpr
> +    _Iterator(_Parent& __parent, decltype(_M_current) __current)
> +    : _M_parent(std::__addressof(__parent)),
> +      _M_current(std::move(__current))
> +    { }
> +
> +    static auto
> +    _S_iter_concept()
> +    {
> +      if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>)
> +	return random_access_iterator_tag{};
> +      else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>)
> +	return bidirectional_iterator_tag{};
> +      else if constexpr (forward_range<__maybe_const_t<_Const, _First>>)
> +	return forward_iterator_tag{};
> +      else
> +	return input_iterator_tag{};
> +    }
> +
> +    friend cartesian_product_view;
> +
> +  public:
> +    using iterator_category = input_iterator_tag;
> +    using iterator_concept = decltype(_S_iter_concept());
> +    using value_type
> +      = __detail::__tuple_or_pair_t<range_value_t<__maybe_const_t<_Const, _First>>,
> +				    range_value_t<__maybe_const_t<_Const, _Vs>>...>;
> +    using reference
> +      = __detail::__tuple_or_pair_t<range_reference_t<__maybe_const_t<_Const, _First>>,
> +				    range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
> +    using difference_type = decltype(cartesian_product_view::_S_difference_type());
> +
> +    _Iterator() requires forward_range<__maybe_const_t<_Const, _First>> = default;
> +
> +    constexpr
> +    _Iterator(_Iterator<!_Const> __i)
> +      requires _Const
> +	&& (convertible_to<iterator_t<_First>, iterator_t<const _First>>
> +	    && ... && convertible_to<iterator_t<_Vs>, iterator_t<const _Vs>>)
> +    : _M_parent(std::__addressof(__i._M_parent)),
> +      _M_current(std::move(__i._M_current))
> +    { }
> +
> +    constexpr auto
> +    operator*() const
> +    {
> +      auto __f = [](auto& __i) -> decltype(auto) {
> +	return *__i;
> +      };
> +      return __detail::__tuple_transform(__f, _M_current);
> +    }
> +
> +    constexpr _Iterator&
> +    operator++()
> +    {
> +      _M_next();
> +      return *this;
> +    }
> +
> +    constexpr void
> +    operator++(int)
> +    { ++*this; }
> +
> +    constexpr _Iterator
> +    operator++(int) requires forward_range<__maybe_const_t<_Const, _First>>
> +    {
> +      auto __tmp = *this;
> +      ++*this;
> +      return __tmp;
> +    }
> +
> +    constexpr _Iterator&
> +    operator--()
> +      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
> +    {
> +      _M_prev();
> +      return *this;
> +    }
> +
> +    constexpr _Iterator
> +    operator--(int)
> +      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
> +    {
> +      auto __tmp = *this;
> +      --*this;
> +      return __tmp;
> +    }
> +
> +  private:
> +    template<size_t _Nm = sizeof...(_Vs)>
> +    constexpr void
> +    _M_advance(difference_type __x)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    {
> +      if (__x == 1)
> +	_M_next<_Nm>();
> +      else if (__x == -1)
> +	_M_prev<_Nm>();
> +      else if (__x != 0)
> +	{
> +	  // Constant time iterator addition.
> +	  auto& __r = std::get<_Nm>(_M_parent->_M_bases);
> +	  auto& __it = std::get<_Nm>(_M_current);
> +	  if constexpr (_Nm == 0)
> +	    {
> +#ifdef _GLIBCXX_ASSERTIONS
> +	      auto __size = ranges::ssize(__r);
> +	      auto __begin = ranges::begin(__r);
> +	      auto __offset = __it - __begin;
> +	      __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size);
> +#endif
> +	      __it += __x;
> +	    }
> +	  else
> +	    {
> +	      auto __size = ranges::ssize(__r);
> +	      auto __begin = ranges::begin(__r);
> +	      auto __offset = __it - __begin;
> +	      __offset += __x;
> +	      __x = __offset / __size;
> +	      __offset %= __size;
> +	      if (__offset < 0)
> +		{
> +		  __offset = __size + __offset;
> +		  --__x;
> +		}
> +	      __it = __begin + __offset;
> +	      _M_advance<_Nm - 1>(__x);
> +	    }
> +	}
> +    }
> +
> +  public:
> +    constexpr _Iterator&
> +    operator+=(difference_type __x)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    {
> +      _M_advance(__x);
> +      return *this;
> +    }
> +
> +    constexpr _Iterator&
> +    operator-=(difference_type __x)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return *this += -__x; }
> +
> +    constexpr reference
> +    operator[](difference_type __n) const
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return *((*this) + __n); }
> +
> +    friend constexpr bool
> +    operator==(const _Iterator& __x, const _Iterator& __y)
> +      requires equality_comparable<iterator_t<__maybe_const_t<_Const, _First>>>
> +    { return __x._M_current == __y._M_current; }
> +
> +    friend constexpr bool
> +    operator==(const _Iterator& __x, default_sentinel_t)
> +    {
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +	return ((std::get<_Is>(__x._M_current)
> +		 == ranges::end(std::get<_Is>(__x._M_parent->_M_bases)))
> +		|| ...);
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +    friend constexpr auto
> +    operator<=>(const _Iterator& __x, const _Iterator& __y)
> +      requires __detail::__all_random_access<_Const, _First, _Vs...>
> +    { return __x._M_current <=> __y._M_current; }
> +
> +    friend constexpr _Iterator
> +    operator+(_Iterator __x, difference_type __y)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return __x += __y; }
> +
> +    friend constexpr _Iterator
> +    operator+(difference_type __x, const _Iterator& __y)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return __y + __x; }
> +
> +    friend constexpr _Iterator
> +    operator-(_Iterator __x, difference_type __y)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return __x -= __y; }
> +
> +    friend constexpr difference_type
> +    operator-(const _Iterator& __x, const _Iterator& __y)
> +      requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...>
> +    { return __x._M_distance_from(__y._M_current); }
> +
> +    friend constexpr difference_type
> +    operator-(const _Iterator& __i, default_sentinel_t)
> +      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
> +    {
> +      tuple __end_tuple = [&]<size_t... _Is>(index_sequence<_Is...>) {
> +	return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)),
> +		     ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...};
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +      return __i._M_distance_from(__end_tuple);
> +    }
> +
> +    friend constexpr difference_type
> +    operator-(default_sentinel_t, const _Iterator& __i)
> +      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
> +    { return -(__i - default_sentinel); }
> +
> +    friend constexpr auto
> +    iter_move(const _Iterator& __i)
> +    { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
> +
> +    friend constexpr void
> +    iter_swap(const _Iterator& __l, const _Iterator& __r)
> +      requires (indirectly_swappable<iterator_t<__maybe_const_t<_Const, _First>>>
> +		&& ...
> +		&& indirectly_swappable<iterator_t<__maybe_const_t<_Const, _Vs>>>)
> +    {
> +      [&]<size_t... _Is>(index_sequence<_Is...>) {
> +	(ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +  private:
> +    template<typename _Tuple>
> +    constexpr difference_type
> +    _M_distance_from(const _Tuple& __t) const
> +    {
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +	auto __sum = static_cast<difference_type>(0);
> +#ifdef _GLIBCXX_ASSERTIONS
> +	if constexpr (integral<difference_type>)
> +	  {
> +	    bool __overflow
> +	      = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t), &__sum)
> +		 || ...);
> +	    __glibcxx_assert(!__overflow);
> +	  }
> +	else
> +#endif
> +	  __sum = (_M_scaled_distance<_Is>(__t) + ...);
> +	return __sum;
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +    template<size_t _Nm, typename _Tuple>
> +    constexpr difference_type
> +    _M_scaled_distance(const _Tuple& __t) const
> +    {
> +      auto __dist = static_cast<difference_type>(std::get<_Nm>(_M_current)
> +						 - std::get<_Nm>(__t));
> +#ifdef _GLIBCXX_ASSERTIONS
> +      if constexpr (integral<difference_type>)
> +	{
> +	  bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist);
> +	  __glibcxx_assert(!__overflow);
> +	}
> +      else
> +#endif
> +	__dist *= _M_scaled_size<_Nm+1>();
> +      return __dist;
> +    }
> +
> +    template<size_t _Nm>
> +    constexpr difference_type
> +    _M_scaled_size() const
> +    {
> +      if constexpr (_Nm <= sizeof...(_Vs))
> +	{
> +	  auto __size = static_cast<difference_type>(ranges::size
> +						     (std::get<_Nm>(_M_parent->_M_bases)));
> +#ifdef _GLIBCXX_ASSERTIONS
> +	  if constexpr (integral<difference_type>)
> +	    {
> +	      bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size);
> +	      __glibcxx_assert(!__overflow);
> +	    }
> +	  else
> +#endif
> +	    __size *= _M_scaled_size<_Nm+1>();
> +	  return __size;
> +	}
> +      else
> +	return static_cast<difference_type>(1);
> +    }
> +  };
> +
> +  namespace views
> +  {
> +    namespace __detail
> +    {
> +      template<typename... _Ts>
> +	concept __can_cartesian_product_view
> +	  = requires { cartesian_product_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
> +    }
> +
> +    struct _CartesianProduct
> +    {
> +      template<typename... _Ts>
> +	requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>)
> +	constexpr auto
> +	operator() [[nodiscard]] (_Ts&&... __ts) const
> +	{
> +	  if constexpr (sizeof...(_Ts) == 0)
> +	    return views::empty<tuple<>>;
> +	  else
> +	    return cartesian_product_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
> +	}
> +    };
> +
> +    inline constexpr _CartesianProduct cartesian_product;
> +  }
>  #endif // C++23
>  } // namespace ranges
>  
> diff --git a/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> new file mode 100644
> index 00000000000..5f1610d6458
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> @@ -0,0 +1,178 @@
> +// { 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()
> +{
> +  int x[] = {1, 2, 3};
> +  int y[] = {4, 5, 6};
> +  int z[] = {7, 8};
> +  int w[] = {9};
> +
> +  auto v0 = views::cartesian_product();
> +  VERIFY( ranges::end(v0) - ranges::begin(v0) == 0 );
> +  VERIFY( ranges::size(v0) == 0 );
> +  VERIFY( ranges::empty(v0) );
> +
> +  auto v1 = views::cartesian_product(x);
> +  VERIFY( ranges::end(v1) - ranges::begin(v1) == 3 );
> +  VERIFY( ranges::size(v1) == 3 );
> +  VERIFY( ranges::equal(v1 | views::keys, x) );
> +  VERIFY( std::get<0>(v1[0]) == 1 );
> +  VERIFY( std::get<0>(v1[1]) == 2 );
> +  VERIFY( std::get<0>(v1[2]) == 3 );
> +  VERIFY( ranges::equal(v1 | views::reverse | views::keys, x | views::reverse));
> +
> +  auto v2 = views::cartesian_product(x, y);
> +  VERIFY( ranges::size(v2) == 9 );
> +  VERIFY( ranges::end(v2) - ranges::begin(v2) == 9 );
> +  VERIFY( ranges::equal(v2 | views::keys,   (int[]){1, 1, 1, 2, 2, 2, 3, 3, 3}));
> +  VERIFY( ranges::equal(v2 | views::values, (int[]){4, 5, 6, 4, 5, 6, 4, 5, 6}));
> +  VERIFY( ranges::equal(v2 | views::reverse | views::keys,   (int[]){3, 3, 3, 2, 2, 2, 1, 1, 1}) );
> +  VERIFY( ranges::equal(v2 | views::reverse | views::values, (int[]){6, 5, 4, 6, 5, 4, 6, 5, 4}) );
> +
> +  auto v3 = views::cartesian_product(x, y, z);
> +  VERIFY( ranges::size(v3) == 18 );
> +  VERIFY( ranges::equal(v3, (std::tuple<int,int,int>[]){{1,4,7}, {1,4,8}, {1,5,7}, {1,5,8},
> +							{1,6,7}, {1,6,8}, {2,4,7}, {2,4,8},
> +							{2,5,7}, {2,5,8}, {2,6,7}, {2,6,8},
> +							{3,4,7}, {3,4,8}, {3,5,7}, {3,5,8},
> +							{3,6,7}, {3,6,8}}) );
> +
> +  auto v4 = views::cartesian_product(x, y, z, w);
> +  VERIFY( ranges::size(v4) == 18 );
> +  VERIFY( ranges::equal(v4 | views::elements<3>, views::repeat(9, 18)) );
> +
> +  auto i4 = v4.begin(), j4 = i4 + 1;
> +  VERIFY( j4 > i4 );
> +  VERIFY( i4[0] == std::tuple(1, 4, 7, 9) );
> +  VERIFY( i4 + 18 == v4.end() );
> +  i4 += 5;
> +  VERIFY( i4 != v4.begin() );
> +  VERIFY( i4 - 5 == v4.begin() );
> +  VERIFY( *i4 == std::tuple(1, 6, 8, 9) );
> +  VERIFY( i4 - 5 != i4 );
> +  i4 -= 3;
> +  VERIFY( *i4 == std::tuple(1, 5, 7, 9) );
> +  VERIFY( j4 + 1 == i4 );
> +  ranges::iter_swap(i4, j4);
> +  VERIFY( *j4 == std::tuple(1, 5, 7, 9) );
> +  VERIFY( *i4 == std::tuple(1, 4, 8, 9) );
> +
> +  return true;
> +}
> +
> +void
> +test02()
> +{
> +  int x[] = {1, 2};
> +  __gnu_test::test_input_range<int> rx(x);
> +  auto v = views::cartesian_product(rx, x);
> +  auto i = v.begin();
> +  std::default_sentinel_t s = v.end();
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 1 );
> +  ++i;
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 2 );
> +  ++i;
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 1 );
> +  ++i;
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 2 );
> +  ++i;
> +  VERIFY( i == s );
> +}
> +
> +void
> +test03()
> +{
> +  int x[] = {1, 2};
> +  __gnu_test::test_input_range<int> rx(x);
> +  auto v = views::cartesian_product(views::counted(rx.begin(), 2), x);
> +  VERIFY( v.size() == 4 );
> +  VERIFY( std::as_const(v).size() == 4 );
> +  auto i = v.begin();
> +  std::default_sentinel_t s = v.end();
> +  VERIFY( i - s == -4 );
> +  VERIFY( s - i == 4 );
> +  ++i;
> +  VERIFY( i - s == -3 );
> +  VERIFY( s - i == 3 );
> +  ++i;
> +  VERIFY( i - s == -2 );
> +  VERIFY( s - i == 2 );
> +  ++i;
> +  VERIFY( i - s == -1 );
> +  VERIFY( s - i == 1 );
> +  ++i;
> +  VERIFY( i - s == 0 );
> +  VERIFY( s - i == 0 );
> +}
> +
> +void
> +test04()
> +{
> +  // Exhaustively verify correctness of our iterator addition implementation
> +  // (which runs in constant time) for this 18-element cartesian_product_view.
> +  int x[] = {1, 2, 3};
> +  int y[] = {4, 5, 6};
> +  int z[] = {7, 8};
> +  int w[] = {9};
> +  auto v = views::cartesian_product(x, y, z, w);
> +
> +  for (int i = 0; i <= ranges::ssize(v); i++)
> +    for (int j = 0; i + j <= ranges::ssize(v); j++)
> +      {
> +	auto b1 = v.begin();
> +	for (int k = 0; k < i + j; k++)
> +	  ++b1;
> +	VERIFY( b1 - v.begin() == i + j );
> +	auto b2 = (v.begin() + i) + j;
> +	auto b3 = v.begin() + (i + j);
> +	VERIFY( b1 == b2 && b2 == b3 );
> +
> +	auto e1 = v.end();
> +	for (int k = 0; k < i + j; k++)
> +	  --e1;
> +	VERIFY( v.end() - e1 == i + j );
> +	auto e2 = (v.end() - i) - j;
> +	auto e3 = v.end() - (i + j);
> +	VERIFY( e1 == e2 && e2 == e3 );
> +      }
> +}
> +
> +void
> +test05()
> +{
> +#if __SIZEOF_INT128__
> +  auto r = views::iota(__int128(0), __int128(5));
> +#else
> +  auto r = views::iota(0ll, 5ll);
> +#endif
> +  auto v = views::cartesian_product(r, r);
> +  VERIFY( ranges::size(v) == 25 );
> +  VERIFY( ranges::size(std::as_const(v)) == 25 );
> +  VERIFY( v.end() - v.begin() == 25 );
> +  VERIFY( v.begin() + ranges::size(v) - v.begin() == 25 );
> +}
> +
> +int
> +main()
> +{
> +  static_assert(test01());
> +  test02();
> +  test03();
> +  test04();
> +  test05();
> +}
> -- 
> 2.38.1.175.gdb29e6bbae
> 
> 

Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4

[Jonathan Wakely]

On Thu, 27 Oct 2022 at 19:48, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> On Thu, 27 Oct 2022, Patrick Palka wrote:
>
> > This also implements the proposed resolutions of the tentatively ready
> > LWG issues 3760 and 3761.
> >
> > I'm not sure how/if we should implement the recommended practice of:
> >
> >   difference_type should be the smallest signed-integer-like type that
> >   is sufficiently wide to store the product of the maximum sizes of all
> >   underlying ranges if such a type exists
> >
> > because for e.g.
> >
> >   extern std::vector<int> x, y;
> >   auto v = views::cartesian_product(x, y);
> >
> > IIUC it'd mean difference_type should be __int128 or so, which seems
> > quite wasteful: in practice the size of the cartesian product probably
> > won't exceed the precision of say ptrdiff_t, and it's probably also not
> > worth adding logic for using less precision than that either.  So this
> > patch chooses defines difference_type as
> >
> >   common_type_t<ptrdiff_t, range_difference_t<_First>, range_difference_t<_Vs>...>
> >
> > which should mean it's least as large as the difference_type of each
> > underlying range, and at least as large as ptrdiff_t.  If overflow
> > occurs due to this choice of difference_type, this patch has debug mode


s/debug mode/assertions/ here I think, as _GLIBCXX_ASSERTIONS works
without the rest of debug mode.

Otherwise, the v2 patch looks good. OK for trunk, thanks!




> > checks to catch this.
> >
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
> >
> > libstdc++-v3/ChangeLog:
> >
> >       * include/std/ranges (__maybe_const_t): New alias for
> >       __detail::__maybe_const_t.
> >       (__detail::__cartesian_product_is_random_access): Define.
> >       (__detail::__cartesian_product_common_arg): Define.
> >       (__detail::__cartesian_product_is_bidirectional): Define.
> >       (__detail::__cartesian_product_is_common): Define.
> >       (__detail::__cartesian_product_is_sized): Define.
> >       (__detail::__cartesian_is_sized_sentinel): Define.
> >       (__detail::__cartesian_common_arg_end): Define.
> >       (cartesian_product_view): Define.
> >       (cartesian_product_view::_Iterator): Define.
> >       (views::__detail::__can_cartesian_product_view): Define.
> >       (views::_Cartesian_product, views::cartesian_product): Define.
> >       * testsuite/std/ranges/cartesian_product/1.cc: New test.
> > ---
> >  libstdc++-v3/include/std/ranges               | 500 ++++++++++++++++++
> >  .../std/ranges/cartesian_product/1.cc         | 162 ++++++
> >  2 files changed, 662 insertions(+)
> >  create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> >
> > diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> > index a55e9e7f760..771da97ed6d 100644
> > --- a/libstdc++-v3/include/std/ranges
> > +++ b/libstdc++-v3/include/std/ranges
> > @@ -829,6 +829,9 @@ namespace __detail
> >
> >  } // namespace __detail
> >
> > +// Shorthand for __detail::__maybe_const_t.
> > +using __detail::__maybe_const_t;
> > +
> >  namespace views::__adaptor
> >  {
> >    // True if the range adaptor _Adaptor can be applied with _Args.
> > @@ -7973,6 +7976,503 @@ namespace views::__adaptor
> >
> >      inline constexpr _Stride stride;
> >    }
> > +
> > +  namespace __detail
> > +  {
> > +    template<bool _Const, typename _First, typename... _Vs>
> > +      concept __cartesian_product_is_random_access
> > +     = (random_access_range<__maybe_const_t<_Const, _First>>
> > +        && ...
> > +        && (random_access_range<__maybe_const_t<_Const, _Vs>>
> > +            && sized_range<__maybe_const_t<_Const, _Vs>>));
> > +
> > +    template<typename _Range>
> > +      concept __cartesian_product_common_arg = common_range<_Range>
> > +     || (sized_range<_Range> && random_access_range<_Range>);
> > +
> > +    template<bool _Const, typename _First, typename... _Vs>
> > +      concept __cartesian_product_is_bidirectional
> > +     = (bidirectional_range<__maybe_const_t<_Const, _First>>
> > +        && ...
> > +        && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> > +            && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
> > +
> > +    template<typename _First, typename... _Vs>
> > +      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
> > +
> > +    template<typename... _Vs>
> > +      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> > +
> > +    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
> > +      concept __cartesian_is_sized_sentinel
> > +      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
> > +                         iterator_t<__maybe_const_t<_Const, _First>>>
> > +      && ...
> > +      && (sized_range<__maybe_const_t<_Const, _Vs>>
> > +          && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
> > +                                iterator_t<__maybe_const_t<_Const, _Vs>>>));
> > +
> > +    template<__cartesian_product_common_arg _Range>
> > +      constexpr auto
> > +      __cartesian_common_arg_end(_Range& __r)
> > +      {
> > +     if constexpr (common_range<_Range>)
> > +       return ranges::end(__r);
> > +     else
> > +       return ranges::begin(__r) + ranges::distance(__r);
> > +      }
> > +  } // namespace __detail
> > +
> > +  template<input_range _First, forward_range... _Vs>
> > +    requires (view<_First> && ... && view<_Vs>)
> > +  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
> > +  {
> > +    tuple<_First, _Vs...> _M_bases;
> > +
> > +    template<bool> class _Iterator;
> > +
> > +    static auto
> > +    _S_difference_type()
> > +    {
> > +      // TODO: Implement the recommended practice of using the smallest
> > +      // sufficiently wide type according to the maximum sizes of the
> > +      // underlying ranges?
> > +      return common_type_t<ptrdiff_t,
> > +                        range_difference_t<_First>,
> > +                        range_difference_t<_Vs>...>{};
> > +    }
> > +
> > +  public:
> > +    cartesian_product_view() = default;
> > +
> > +    constexpr explicit
> > +    cartesian_product_view(_First __first, _Vs... __rest)
> > +    : _M_bases(std::move(__first), std::move(__rest)...)
> > +    { }
> > +
> > +    constexpr _Iterator<false>
> > +    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> > +    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> > +
> > +    constexpr _Iterator<true>
> > +    begin() const requires (range<const _First> && ... && range<const _Vs>)
> > +    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> > +
> > +    constexpr _Iterator<false>
> > +    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> > +                 && __detail::__cartesian_product_is_common<_First, _Vs...>)
> > +    {
> > +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> > +     return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> > +      }(make_index_sequence<sizeof...(_Vs)>{});
> > +
> > +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> > +      if (!__empty_tail)
> > +     std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> > +      return _Iterator<false>{*this, std::move(__it)};
> > +    }
> > +
> > +    constexpr _Iterator<true>
> > +    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
> > +    {
> > +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> > +     return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> > +      }(make_index_sequence<sizeof...(_Vs)>{});
> > +
> > +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> > +      if (!__empty_tail)
> > +     std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> > +      return _Iterator<true>{*this, std::move(__it)};
> > +    }
> > +
> > +    constexpr default_sentinel_t
> > +    end() const noexcept
> > +    { return default_sentinel; }
> > +
> > +    constexpr auto
> > +    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
> > +    {
> > +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> > +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> > +#ifdef _GLIBCXX_ASSERTIONS
> > +     _ST __sz = 1;
> > +     bool __overflow
> > +       = (__builtin_mul_overflow(__sz,
> > +                                 static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> > +                                 &__sz)
> > +          || ...);
> > +     __glibcxx_assert(!__overflow);
> > +     return __sz;
>
> __builtin_add/mul_overflow can't handle integer-class types so these
> debug-mode checks must be disabled for such types.  Here's v2 which
> corrects and adds a test for the case where the difference type is
> an integer-class type:
>
> -- >8 --
>
> Subject: [PATCH] libstdc++: Implement ranges::cartesian_product_view from
>  P2374R4
>
> libstdc++-v3/ChangeLog:
>
>         * include/std/ranges (__maybe_const_t): New alias for
>         __detail::__maybe_const_t.
>         (__detail::__cartesian_product_is_random_access): Define.
>         (__detail::__cartesian_product_common_arg): Define.
>         (__detail::__cartesian_product_is_bidirectional): Define.
>         (__detail::__cartesian_product_is_common): Define.
>         (__detail::__cartesian_product_is_sized): Define.
>         (__detail::__cartesian_is_sized_sentinel): Define.
>         (__detail::__cartesian_common_arg_end): Define.
>         (cartesian_product_view): Define.
>         (cartesian_product_view::_Iterator): Define.
>         (views::__detail::__can_cartesian_product_view): Define.
>         (views::_Cartesian_product, views::cartesian_product): Define.
>         * testsuite/std/ranges/cartesian_product/1.cc: New test.
> ---
>  libstdc++-v3/include/std/ranges               | 515 ++++++++++++++++++
>  .../std/ranges/cartesian_product/1.cc         | 178 ++++++
>  2 files changed, 693 insertions(+)
>  create mode 100644 libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
>
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index a55e9e7f760..92d15c81e51 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -829,6 +829,9 @@ namespace __detail
>
>  } // namespace __detail
>
> +// Shorthand for __detail::__maybe_const_t.
> +using __detail::__maybe_const_t;
> +
>  namespace views::__adaptor
>  {
>    // True if the range adaptor _Adaptor can be applied with _Args.
> @@ -7973,6 +7976,518 @@ namespace views::__adaptor
>
>      inline constexpr _Stride stride;
>    }
> +
> +  namespace __detail
> +  {
> +    template<bool _Const, typename _First, typename... _Vs>
> +      concept __cartesian_product_is_random_access
> +       = (random_access_range<__maybe_const_t<_Const, _First>>
> +          && ...
> +          && (random_access_range<__maybe_const_t<_Const, _Vs>>
> +              && sized_range<__maybe_const_t<_Const, _Vs>>));
> +
> +    template<typename _Range>
> +      concept __cartesian_product_common_arg = common_range<_Range>
> +       || (sized_range<_Range> && random_access_range<_Range>);
> +
> +    template<bool _Const, typename _First, typename... _Vs>
> +      concept __cartesian_product_is_bidirectional
> +       = (bidirectional_range<__maybe_const_t<_Const, _First>>
> +          && ...
> +          && (bidirectional_range<__maybe_const_t<_Const, _Vs>>
> +              && __cartesian_product_common_arg<__maybe_const_t<_Const, _Vs>>));
> +
> +    template<typename _First, typename... _Vs>
> +      concept __cartesian_product_is_common = __cartesian_product_common_arg<_First>;
> +
> +    template<typename... _Vs>
> +      concept __cartesian_product_is_sized = (sized_range<_Vs> && ...);
> +
> +    template<bool _Const, template<typename> class FirstSent, typename _First, typename... _Vs>
> +      concept __cartesian_is_sized_sentinel
> +      = (sized_sentinel_for<FirstSent<__maybe_const_t<_Const, _First>>,
> +                           iterator_t<__maybe_const_t<_Const, _First>>>
> +        && ...
> +        && (sized_range<__maybe_const_t<_Const, _Vs>>
> +            && sized_sentinel_for<iterator_t<__maybe_const_t<_Const, _Vs>>,
> +                                  iterator_t<__maybe_const_t<_Const, _Vs>>>));
> +
> +    template<__cartesian_product_common_arg _Range>
> +      constexpr auto
> +      __cartesian_common_arg_end(_Range& __r)
> +      {
> +       if constexpr (common_range<_Range>)
> +         return ranges::end(__r);
> +       else
> +         return ranges::begin(__r) + ranges::distance(__r);
> +      }
> +  } // namespace __detail
> +
> +  template<input_range _First, forward_range... _Vs>
> +    requires (view<_First> && ... && view<_Vs>)
> +  class cartesian_product_view : public view_interface<cartesian_product_view<_First, _Vs...>>
> +  {
> +    tuple<_First, _Vs...> _M_bases;
> +
> +    template<bool> class _Iterator;
> +
> +    static auto
> +    _S_difference_type()
> +    {
> +      // TODO: Implement the recommended practice of using the smallest
> +      // sufficiently wide type according to the maximum sizes of the
> +      // underlying ranges?
> +      return common_type_t<ptrdiff_t,
> +                          range_difference_t<_First>,
> +                          range_difference_t<_Vs>...>{};
> +    }
> +
> +  public:
> +    cartesian_product_view() = default;
> +
> +    constexpr explicit
> +    cartesian_product_view(_First __first, _Vs... __rest)
> +    : _M_bases(std::move(__first), std::move(__rest)...)
> +    { }
> +
> +    constexpr _Iterator<false>
> +    begin() requires (!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> +    { return _Iterator<false>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> +
> +    constexpr _Iterator<true>
> +    begin() const requires (range<const _First> && ... && range<const _Vs>)
> +    { return _Iterator<true>(*this, __detail::__tuple_transform(ranges::begin, _M_bases)); }
> +
> +    constexpr _Iterator<false>
> +    end() requires ((!__detail::__simple_view<_First> || ... || !__detail::__simple_view<_Vs>)
> +                   && __detail::__cartesian_product_is_common<_First, _Vs...>)
> +    {
> +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> +       return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +
> +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> +      if (!__empty_tail)
> +       std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> +      return _Iterator<false>{*this, std::move(__it)};
> +    }
> +
> +    constexpr _Iterator<true>
> +    end() const requires __detail::__cartesian_product_is_common<const _First, const _Vs...>
> +    {
> +      bool __empty_tail = [this]<size_t... _Is>(index_sequence<_Is...>) {
> +       return (ranges::empty(std::get<1 + _Is>(_M_bases)) || ...);
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +
> +      auto __it = __detail::__tuple_transform(ranges::begin, _M_bases);
> +      if (!__empty_tail)
> +       std::get<0>(__it) = __detail::__cartesian_common_arg_end(std::get<0>(_M_bases));
> +      return _Iterator<true>{*this, std::move(__it)};
> +    }
> +
> +    constexpr default_sentinel_t
> +    end() const noexcept
> +    { return default_sentinel; }
> +
> +    constexpr auto
> +    size() requires __detail::__cartesian_product_is_sized<_First, _Vs...>
> +    {
> +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +       auto __size = static_cast<_ST>(1);
> +#ifdef _GLIBCXX_ASSERTIONS
> +       if constexpr (integral<_ST>)
> +         {
> +           bool __overflow
> +             = (__builtin_mul_overflow(__size,
> +                                       static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> +                                       &__size)
> +                || ...);
> +           __glibcxx_assert(!__overflow);
> +         }
> +       else
> +#endif
> +         __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
> +       return __size;
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +    constexpr auto
> +    size() const requires __detail::__cartesian_product_is_sized<const _First, const _Vs...>
> +    {
> +      using _ST = __detail::__make_unsigned_like_t<decltype(_S_difference_type())>;
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +       auto __size = static_cast<_ST>(1);
> +#ifdef _GLIBCXX_ASSERTIONS
> +       if constexpr (integral<_ST>)
> +         {
> +           bool __overflow
> +             = (__builtin_mul_overflow(__size,
> +                                       static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))),
> +                                       &__size)
> +                || ...);
> +           __glibcxx_assert(!__overflow);
> +         }
> +       else
> +#endif
> +         __size = (static_cast<_ST>(ranges::size(std::get<_Is>(_M_bases))) * ...);
> +       return __size;
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +  };
> +
> +  template<typename... _Vs>
> +    cartesian_product_view(_Vs&&...) -> cartesian_product_view<views::all_t<_Vs>...>;
> +
> +  template<input_range _First, forward_range... _Vs>
> +    requires (view<_First> && ... && view<_Vs>)
> +  template<bool _Const>
> +  class cartesian_product_view<_First, _Vs...>::_Iterator
> +  {
> +    using _Parent = __maybe_const_t<_Const, cartesian_product_view>;
> +    _Parent* _M_parent = nullptr;
> +    __detail::__tuple_or_pair_t<iterator_t<__maybe_const_t<_Const, _First>>,
> +                               iterator_t<__maybe_const_t<_Const, _Vs>>...> _M_current;
> +
> +    template<size_t _Nm = sizeof...(_Vs)>
> +    constexpr void
> +    _M_next()
> +    {
> +      auto& __it = std::get<_Nm>(_M_current);
> +      ++__it;
> +      if constexpr (_Nm > 0)
> +       if (__it == ranges::end(std::get<_Nm>(_M_parent->_M_bases)))
> +         {
> +           __it = ranges::begin(std::get<_Nm>(_M_parent->_M_bases));
> +           _M_next<_Nm - 1>();
> +         }
> +    }
> +
> +    template<size_t _Nm = sizeof...(_Vs)>
> +    constexpr void
> +    _M_prev()
> +    {
> +      auto& __it = std::get<_Nm>(_M_current);
> +      if (__it == ranges::begin(std::get<_Nm>(_M_parent->_M_bases)))
> +       {
> +         __it = __detail::__cartesian_common_arg_end(std::get<_Nm>(_M_parent->_M_bases));
> +         if constexpr (_Nm > 0)
> +           _M_prev<_Nm - 1>();
> +       }
> +      --__it;
> +    }
> +
> +    constexpr
> +    _Iterator(_Parent& __parent, decltype(_M_current) __current)
> +    : _M_parent(std::__addressof(__parent)),
> +      _M_current(std::move(__current))
> +    { }
> +
> +    static auto
> +    _S_iter_concept()
> +    {
> +      if constexpr (__detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>)
> +       return random_access_iterator_tag{};
> +      else if constexpr (__detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>)
> +       return bidirectional_iterator_tag{};
> +      else if constexpr (forward_range<__maybe_const_t<_Const, _First>>)
> +       return forward_iterator_tag{};
> +      else
> +       return input_iterator_tag{};
> +    }
> +
> +    friend cartesian_product_view;
> +
> +  public:
> +    using iterator_category = input_iterator_tag;
> +    using iterator_concept = decltype(_S_iter_concept());
> +    using value_type
> +      = __detail::__tuple_or_pair_t<range_value_t<__maybe_const_t<_Const, _First>>,
> +                                   range_value_t<__maybe_const_t<_Const, _Vs>>...>;
> +    using reference
> +      = __detail::__tuple_or_pair_t<range_reference_t<__maybe_const_t<_Const, _First>>,
> +                                   range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
> +    using difference_type = decltype(cartesian_product_view::_S_difference_type());
> +
> +    _Iterator() requires forward_range<__maybe_const_t<_Const, _First>> = default;
> +
> +    constexpr
> +    _Iterator(_Iterator<!_Const> __i)
> +      requires _Const
> +       && (convertible_to<iterator_t<_First>, iterator_t<const _First>>
> +           && ... && convertible_to<iterator_t<_Vs>, iterator_t<const _Vs>>)
> +    : _M_parent(std::__addressof(__i._M_parent)),
> +      _M_current(std::move(__i._M_current))
> +    { }
> +
> +    constexpr auto
> +    operator*() const
> +    {
> +      auto __f = [](auto& __i) -> decltype(auto) {
> +       return *__i;
> +      };
> +      return __detail::__tuple_transform(__f, _M_current);
> +    }
> +
> +    constexpr _Iterator&
> +    operator++()
> +    {
> +      _M_next();
> +      return *this;
> +    }
> +
> +    constexpr void
> +    operator++(int)
> +    { ++*this; }
> +
> +    constexpr _Iterator
> +    operator++(int) requires forward_range<__maybe_const_t<_Const, _First>>
> +    {
> +      auto __tmp = *this;
> +      ++*this;
> +      return __tmp;
> +    }
> +
> +    constexpr _Iterator&
> +    operator--()
> +      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
> +    {
> +      _M_prev();
> +      return *this;
> +    }
> +
> +    constexpr _Iterator
> +    operator--(int)
> +      requires __detail::__cartesian_product_is_bidirectional<_Const, _First, _Vs...>
> +    {
> +      auto __tmp = *this;
> +      --*this;
> +      return __tmp;
> +    }
> +
> +  private:
> +    template<size_t _Nm = sizeof...(_Vs)>
> +    constexpr void
> +    _M_advance(difference_type __x)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    {
> +      if (__x == 1)
> +       _M_next<_Nm>();
> +      else if (__x == -1)
> +       _M_prev<_Nm>();
> +      else if (__x != 0)
> +       {
> +         // Constant time iterator addition.
> +         auto& __r = std::get<_Nm>(_M_parent->_M_bases);
> +         auto& __it = std::get<_Nm>(_M_current);
> +         if constexpr (_Nm == 0)
> +           {
> +#ifdef _GLIBCXX_ASSERTIONS
> +             auto __size = ranges::ssize(__r);
> +             auto __begin = ranges::begin(__r);
> +             auto __offset = __it - __begin;
> +             __glibcxx_assert(__offset + __x >= 0 && __offset + __x <= __size);
> +#endif
> +             __it += __x;
> +           }
> +         else
> +           {
> +             auto __size = ranges::ssize(__r);
> +             auto __begin = ranges::begin(__r);
> +             auto __offset = __it - __begin;
> +             __offset += __x;
> +             __x = __offset / __size;
> +             __offset %= __size;
> +             if (__offset < 0)
> +               {
> +                 __offset = __size + __offset;
> +                 --__x;
> +               }
> +             __it = __begin + __offset;
> +             _M_advance<_Nm - 1>(__x);
> +           }
> +       }
> +    }
> +
> +  public:
> +    constexpr _Iterator&
> +    operator+=(difference_type __x)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    {
> +      _M_advance(__x);
> +      return *this;
> +    }
> +
> +    constexpr _Iterator&
> +    operator-=(difference_type __x)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return *this += -__x; }
> +
> +    constexpr reference
> +    operator[](difference_type __n) const
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return *((*this) + __n); }
> +
> +    friend constexpr bool
> +    operator==(const _Iterator& __x, const _Iterator& __y)
> +      requires equality_comparable<iterator_t<__maybe_const_t<_Const, _First>>>
> +    { return __x._M_current == __y._M_current; }
> +
> +    friend constexpr bool
> +    operator==(const _Iterator& __x, default_sentinel_t)
> +    {
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +       return ((std::get<_Is>(__x._M_current)
> +                == ranges::end(std::get<_Is>(__x._M_parent->_M_bases)))
> +               || ...);
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +    friend constexpr auto
> +    operator<=>(const _Iterator& __x, const _Iterator& __y)
> +      requires __detail::__all_random_access<_Const, _First, _Vs...>
> +    { return __x._M_current <=> __y._M_current; }
> +
> +    friend constexpr _Iterator
> +    operator+(_Iterator __x, difference_type __y)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return __x += __y; }
> +
> +    friend constexpr _Iterator
> +    operator+(difference_type __x, const _Iterator& __y)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return __y + __x; }
> +
> +    friend constexpr _Iterator
> +    operator-(_Iterator __x, difference_type __y)
> +      requires __detail::__cartesian_product_is_random_access<_Const, _First, _Vs...>
> +    { return __x -= __y; }
> +
> +    friend constexpr difference_type
> +    operator-(const _Iterator& __x, const _Iterator& __y)
> +      requires __detail::__cartesian_is_sized_sentinel<_Const, iterator_t, _First, _Vs...>
> +    { return __x._M_distance_from(__y._M_current); }
> +
> +    friend constexpr difference_type
> +    operator-(const _Iterator& __i, default_sentinel_t)
> +      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
> +    {
> +      tuple __end_tuple = [&]<size_t... _Is>(index_sequence<_Is...>) {
> +       return tuple{ranges::end(std::get<0>(__i._M_parent->_M_bases)),
> +                    ranges::begin(std::get<1 + _Is>(__i._M_parent->_M_bases))...};
> +      }(make_index_sequence<sizeof...(_Vs)>{});
> +      return __i._M_distance_from(__end_tuple);
> +    }
> +
> +    friend constexpr difference_type
> +    operator-(default_sentinel_t, const _Iterator& __i)
> +      requires __detail::__cartesian_is_sized_sentinel<_Const, sentinel_t, _First, _Vs...>
> +    { return -(__i - default_sentinel); }
> +
> +    friend constexpr auto
> +    iter_move(const _Iterator& __i)
> +    { return __detail::__tuple_transform(ranges::iter_move, __i._M_current); }
> +
> +    friend constexpr void
> +    iter_swap(const _Iterator& __l, const _Iterator& __r)
> +      requires (indirectly_swappable<iterator_t<__maybe_const_t<_Const, _First>>>
> +               && ...
> +               && indirectly_swappable<iterator_t<__maybe_const_t<_Const, _Vs>>>)
> +    {
> +      [&]<size_t... _Is>(index_sequence<_Is...>) {
> +       (ranges::iter_swap(std::get<_Is>(__l._M_current), std::get<_Is>(__r._M_current)), ...);
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +  private:
> +    template<typename _Tuple>
> +    constexpr difference_type
> +    _M_distance_from(const _Tuple& __t) const
> +    {
> +      return [&]<size_t... _Is>(index_sequence<_Is...>) {
> +       auto __sum = static_cast<difference_type>(0);
> +#ifdef _GLIBCXX_ASSERTIONS
> +       if constexpr (integral<difference_type>)
> +         {
> +           bool __overflow
> +             = (__builtin_add_overflow(__sum, _M_scaled_distance<_Is>(__t), &__sum)
> +                || ...);
> +           __glibcxx_assert(!__overflow);
> +         }
> +       else
> +#endif
> +         __sum = (_M_scaled_distance<_Is>(__t) + ...);
> +       return __sum;
> +      }(make_index_sequence<1 + sizeof...(_Vs)>{});
> +    }
> +
> +    template<size_t _Nm, typename _Tuple>
> +    constexpr difference_type
> +    _M_scaled_distance(const _Tuple& __t) const
> +    {
> +      auto __dist = static_cast<difference_type>(std::get<_Nm>(_M_current)
> +                                                - std::get<_Nm>(__t));
> +#ifdef _GLIBCXX_ASSERTIONS
> +      if constexpr (integral<difference_type>)
> +       {
> +         bool __overflow = __builtin_mul_overflow(__dist, _M_scaled_size<_Nm+1>(), &__dist);
> +         __glibcxx_assert(!__overflow);
> +       }
> +      else
> +#endif
> +       __dist *= _M_scaled_size<_Nm+1>();
> +      return __dist;
> +    }
> +
> +    template<size_t _Nm>
> +    constexpr difference_type
> +    _M_scaled_size() const
> +    {
> +      if constexpr (_Nm <= sizeof...(_Vs))
> +       {
> +         auto __size = static_cast<difference_type>(ranges::size
> +                                                    (std::get<_Nm>(_M_parent->_M_bases)));
> +#ifdef _GLIBCXX_ASSERTIONS
> +         if constexpr (integral<difference_type>)
> +           {
> +             bool __overflow = __builtin_mul_overflow(__size, _M_scaled_size<_Nm+1>(), &__size);
> +             __glibcxx_assert(!__overflow);
> +           }
> +         else
> +#endif
> +           __size *= _M_scaled_size<_Nm+1>();
> +         return __size;
> +       }
> +      else
> +       return static_cast<difference_type>(1);
> +    }
> +  };
> +
> +  namespace views
> +  {
> +    namespace __detail
> +    {
> +      template<typename... _Ts>
> +       concept __can_cartesian_product_view
> +         = requires { cartesian_product_view<all_t<_Ts>...>(std::declval<_Ts>()...); };
> +    }
> +
> +    struct _CartesianProduct
> +    {
> +      template<typename... _Ts>
> +       requires (sizeof...(_Ts) == 0 || __detail::__can_cartesian_product_view<_Ts...>)
> +       constexpr auto
> +       operator() [[nodiscard]] (_Ts&&... __ts) const
> +       {
> +         if constexpr (sizeof...(_Ts) == 0)
> +           return views::empty<tuple<>>;
> +         else
> +           return cartesian_product_view<all_t<_Ts>...>(std::forward<_Ts>(__ts)...);
> +       }
> +    };
> +
> +    inline constexpr _CartesianProduct cartesian_product;
> +  }
>  #endif // C++23
>  } // namespace ranges
>
> diff --git a/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> new file mode 100644
> index 00000000000..5f1610d6458
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/ranges/cartesian_product/1.cc
> @@ -0,0 +1,178 @@
> +// { 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()
> +{
> +  int x[] = {1, 2, 3};
> +  int y[] = {4, 5, 6};
> +  int z[] = {7, 8};
> +  int w[] = {9};
> +
> +  auto v0 = views::cartesian_product();
> +  VERIFY( ranges::end(v0) - ranges::begin(v0) == 0 );
> +  VERIFY( ranges::size(v0) == 0 );
> +  VERIFY( ranges::empty(v0) );
> +
> +  auto v1 = views::cartesian_product(x);
> +  VERIFY( ranges::end(v1) - ranges::begin(v1) == 3 );
> +  VERIFY( ranges::size(v1) == 3 );
> +  VERIFY( ranges::equal(v1 | views::keys, x) );
> +  VERIFY( std::get<0>(v1[0]) == 1 );
> +  VERIFY( std::get<0>(v1[1]) == 2 );
> +  VERIFY( std::get<0>(v1[2]) == 3 );
> +  VERIFY( ranges::equal(v1 | views::reverse | views::keys, x | views::reverse));
> +
> +  auto v2 = views::cartesian_product(x, y);
> +  VERIFY( ranges::size(v2) == 9 );
> +  VERIFY( ranges::end(v2) - ranges::begin(v2) == 9 );
> +  VERIFY( ranges::equal(v2 | views::keys,   (int[]){1, 1, 1, 2, 2, 2, 3, 3, 3}));
> +  VERIFY( ranges::equal(v2 | views::values, (int[]){4, 5, 6, 4, 5, 6, 4, 5, 6}));
> +  VERIFY( ranges::equal(v2 | views::reverse | views::keys,   (int[]){3, 3, 3, 2, 2, 2, 1, 1, 1}) );
> +  VERIFY( ranges::equal(v2 | views::reverse | views::values, (int[]){6, 5, 4, 6, 5, 4, 6, 5, 4}) );
> +
> +  auto v3 = views::cartesian_product(x, y, z);
> +  VERIFY( ranges::size(v3) == 18 );
> +  VERIFY( ranges::equal(v3, (std::tuple<int,int,int>[]){{1,4,7}, {1,4,8}, {1,5,7}, {1,5,8},
> +                                                       {1,6,7}, {1,6,8}, {2,4,7}, {2,4,8},
> +                                                       {2,5,7}, {2,5,8}, {2,6,7}, {2,6,8},
> +                                                       {3,4,7}, {3,4,8}, {3,5,7}, {3,5,8},
> +                                                       {3,6,7}, {3,6,8}}) );
> +
> +  auto v4 = views::cartesian_product(x, y, z, w);
> +  VERIFY( ranges::size(v4) == 18 );
> +  VERIFY( ranges::equal(v4 | views::elements<3>, views::repeat(9, 18)) );
> +
> +  auto i4 = v4.begin(), j4 = i4 + 1;
> +  VERIFY( j4 > i4 );
> +  VERIFY( i4[0] == std::tuple(1, 4, 7, 9) );
> +  VERIFY( i4 + 18 == v4.end() );
> +  i4 += 5;
> +  VERIFY( i4 != v4.begin() );
> +  VERIFY( i4 - 5 == v4.begin() );
> +  VERIFY( *i4 == std::tuple(1, 6, 8, 9) );
> +  VERIFY( i4 - 5 != i4 );
> +  i4 -= 3;
> +  VERIFY( *i4 == std::tuple(1, 5, 7, 9) );
> +  VERIFY( j4 + 1 == i4 );
> +  ranges::iter_swap(i4, j4);
> +  VERIFY( *j4 == std::tuple(1, 5, 7, 9) );
> +  VERIFY( *i4 == std::tuple(1, 4, 8, 9) );
> +
> +  return true;
> +}
> +
> +void
> +test02()
> +{
> +  int x[] = {1, 2};
> +  __gnu_test::test_input_range<int> rx(x);
> +  auto v = views::cartesian_product(rx, x);
> +  auto i = v.begin();
> +  std::default_sentinel_t s = v.end();
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 1 );
> +  ++i;
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 1 && std::get<1>(*i) == 2 );
> +  ++i;
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 1 );
> +  ++i;
> +  VERIFY( i != s );
> +  VERIFY( std::get<0>(*i) == 2 && std::get<1>(*i) == 2 );
> +  ++i;
> +  VERIFY( i == s );
> +}
> +
> +void
> +test03()
> +{
> +  int x[] = {1, 2};
> +  __gnu_test::test_input_range<int> rx(x);
> +  auto v = views::cartesian_product(views::counted(rx.begin(), 2), x);
> +  VERIFY( v.size() == 4 );
> +  VERIFY( std::as_const(v).size() == 4 );
> +  auto i = v.begin();
> +  std::default_sentinel_t s = v.end();
> +  VERIFY( i - s == -4 );
> +  VERIFY( s - i == 4 );
> +  ++i;
> +  VERIFY( i - s == -3 );
> +  VERIFY( s - i == 3 );
> +  ++i;
> +  VERIFY( i - s == -2 );
> +  VERIFY( s - i == 2 );
> +  ++i;
> +  VERIFY( i - s == -1 );
> +  VERIFY( s - i == 1 );
> +  ++i;
> +  VERIFY( i - s == 0 );
> +  VERIFY( s - i == 0 );
> +}
> +
> +void
> +test04()
> +{
> +  // Exhaustively verify correctness of our iterator addition implementation
> +  // (which runs in constant time) for this 18-element cartesian_product_view.
> +  int x[] = {1, 2, 3};
> +  int y[] = {4, 5, 6};
> +  int z[] = {7, 8};
> +  int w[] = {9};
> +  auto v = views::cartesian_product(x, y, z, w);
> +
> +  for (int i = 0; i <= ranges::ssize(v); i++)
> +    for (int j = 0; i + j <= ranges::ssize(v); j++)
> +      {
> +       auto b1 = v.begin();
> +       for (int k = 0; k < i + j; k++)
> +         ++b1;
> +       VERIFY( b1 - v.begin() == i + j );
> +       auto b2 = (v.begin() + i) + j;
> +       auto b3 = v.begin() + (i + j);
> +       VERIFY( b1 == b2 && b2 == b3 );
> +
> +       auto e1 = v.end();
> +       for (int k = 0; k < i + j; k++)
> +         --e1;
> +       VERIFY( v.end() - e1 == i + j );
> +       auto e2 = (v.end() - i) - j;
> +       auto e3 = v.end() - (i + j);
> +       VERIFY( e1 == e2 && e2 == e3 );
> +      }
> +}
> +
> +void
> +test05()
> +{
> +#if __SIZEOF_INT128__
> +  auto r = views::iota(__int128(0), __int128(5));
> +#else
> +  auto r = views::iota(0ll, 5ll);
> +#endif
> +  auto v = views::cartesian_product(r, r);
> +  VERIFY( ranges::size(v) == 25 );
> +  VERIFY( ranges::size(std::as_const(v)) == 25 );
> +  VERIFY( v.end() - v.begin() == 25 );
> +  VERIFY( v.begin() + ranges::size(v) - v.begin() == 25 );
> +}
> +
> +int
> +main()
> +{
> +  static_assert(test01());
> +  test02();
> +  test03();
> +  test04();
> +  test05();
> +}
> --
> 2.38.1.175.gdb29e6bbae
>