* [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
@ 2022-10-27 16:47 Patrick Palka
2022-10-27 18:47 ` Patrick Palka
0 siblings, 1 reply; 4+ messages in thread
From: Patrick Palka @ 2022-10-27 16:47 UTC (permalink / raw)
To: gcc-patches; +Cc: libstdc++, 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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
2022-10-27 16:47 [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4 Patrick Palka
@ 2022-10-27 18:47 ` Patrick Palka
2022-11-07 14:12 ` Patrick Palka
2022-11-07 17:41 ` Jonathan Wakely
0 siblings, 2 replies; 4+ messages in thread
From: Patrick Palka @ 2022-10-27 18:47 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
2022-10-27 18:47 ` Patrick Palka
@ 2022-11-07 14:12 ` Patrick Palka
2022-11-07 17:41 ` Jonathan Wakely
1 sibling, 0 replies; 4+ messages in thread
From: Patrick Palka @ 2022-11-07 14:12 UTC (permalink / raw)
To: Patrick Palka; +Cc: gcc-patches, libstdc++
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
>
>
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4
2022-10-27 18:47 ` Patrick Palka
2022-11-07 14:12 ` Patrick Palka
@ 2022-11-07 17:41 ` Jonathan Wakely
1 sibling, 0 replies; 4+ messages in thread
From: Jonathan Wakely @ 2022-11-07 17:41 UTC (permalink / raw)
To: Patrick Palka; +Cc: libstdc++, gcc-patches
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
>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2022-11-07 17:41 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-10-27 16:47 [PATCH] libstdc++: Implement ranges::cartesian_product_view from P2374R4 Patrick Palka
2022-10-27 18:47 ` Patrick Palka
2022-11-07 14:12 ` Patrick Palka
2022-11-07 17:41 ` Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).