public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
From: Patrick Palka <ppalka@redhat.com>
To: gcc-patches@gcc.gnu.org
Cc: libstdc++@gcc.gnu.org, Patrick Palka <ppalka@redhat.com>
Subject: [PATCH 1/2] libstdc++: Implement ranges::zip_transform_view from P2321R2
Date: Thu, 25 Aug 2022 11:39:37 -0400	[thread overview]
Message-ID: <20220825153938.2249619-1-ppalka@redhat.com> (raw)

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

libstdc++-v3/ChangeLog:

	* include/std/ranges (zip_view::_Iterator): Befriend
	zip_transform_view.
	(__detail::__range_iter_cat): Define.
	(zip_transform_view): Define.
	(zip_transform_view::_Iterator): Define.
	(zip_transform_view::_Sentinel): Define.
	(views::__detail::__can_zip_transform_view): Define.
	(views::_ZipTransform): Define.
	(views::zip_transform): Define.
	* testsuite/std/ranges/zip_transform/1.cc: New test.
---
 libstdc++-v3/include/std/ranges               | 343 ++++++++++++++++++
 .../testsuite/std/ranges/zip_transform/1.cc   | 108 ++++++
 2 files changed, 451 insertions(+)
 create mode 100644 libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index fb815c48f99..d748cb73346 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -4502,6 +4502,12 @@ namespace views::__adaptor
 	return input_iterator_tag{};
     }
 
+    template<copy_constructible _Fp, input_range... _Ws>
+      requires (view<_Ws> && ...) && (sizeof...(_Ws) > 0) && is_object_v<_Fp>
+	&& regular_invocable<_Fp&, range_reference_t<_Ws>...>
+	&& std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Ws>...>>
+      friend class zip_transform_view;
+
   public:
     // iterator_category defined in __zip_view_iter_cat
     using iterator_concept = decltype(_S_iter_concept());
@@ -4781,6 +4787,343 @@ namespace views::__adaptor
 
     inline constexpr _Zip zip;
   }
+
+  namespace __detail
+  {
+    template<typename _Range, bool _Const>
+      using __range_iter_cat
+	= typename iterator_traits<iterator_t<__maybe_const_t<_Const, _Range>>>::iterator_category;
+  }
+
+  template<copy_constructible _Fp, input_range... _Vs>
+    requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
+      && regular_invocable<_Fp&, range_reference_t<_Vs>...>
+      && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
+  class zip_transform_view : public view_interface<zip_transform_view<_Fp, _Vs...>>
+  {
+    [[no_unique_address]] __detail::__box<_Fp> _M_fun;
+    zip_view<_Vs...> _M_zip;
+
+    using _InnerView = zip_view<_Vs...>;
+
+    template<bool _Const>
+      using __ziperator = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>;
+
+    template<bool _Const>
+      using __zentinel = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>;
+
+    template<bool _Const>
+      using _Base = __detail::__maybe_const_t<_Const, _InnerView>;
+
+    template<bool _Const>
+      struct __iter_cat
+      { };
+
+    template<bool _Const>
+      requires forward_range<_Base<_Const>>
+      struct __iter_cat<_Const>
+      {
+      private:
+	static auto
+	_S_iter_cat()
+	{
+	  using __detail::__maybe_const_t;
+	  using __detail::__range_iter_cat;
+	  using _Res = invoke_result_t<__maybe_const_t<_Const, _Fp>&,
+				       range_reference_t<__maybe_const_t<_Const, _Vs>>...>;
+	  if constexpr (!is_lvalue_reference_v<_Res>)
+	    return input_iterator_tag{};
+	  else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>,
+					   random_access_iterator_tag> && ...))
+	    return random_access_iterator_tag{};
+	  else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>,
+					   bidirectional_iterator_tag> && ...))
+	    return bidirectional_iterator_tag{};
+	  else if constexpr ((derived_from<__range_iter_cat<_Vs, _Const>,
+					   forward_iterator_tag> && ...))
+	    return forward_iterator_tag{};
+	  else
+	    return input_iterator_tag{};
+	}
+      public:
+	using iterator_category = decltype(_S_iter_cat());
+      };
+
+    template<bool> class _Iterator;
+    template<bool> class _Sentinel;
+
+  public:
+    zip_transform_view() = default;
+
+    constexpr explicit
+    zip_transform_view(_Fp __fun, _Vs... __views)
+      : _M_fun(std::move(__fun)), _M_zip(std::move(__views)...)
+    { }
+
+    constexpr auto
+    begin()
+    { return _Iterator<false>(*this, _M_zip.begin()); }
+
+    constexpr auto
+    begin() const
+      requires range<const _InnerView>
+	&& regular_invocable<const _Fp&, range_reference_t<const _Vs>...>
+    { return _Iterator<true>(*this, _M_zip.begin()); }
+
+    constexpr auto
+    end()
+    {
+      if constexpr (common_range<_InnerView>)
+	return _Iterator<false>(*this, _M_zip.end());
+      else
+	return _Sentinel<false>(_M_zip.end());
+    }
+
+    constexpr auto
+    end() const
+      requires range<const _InnerView>
+	&& regular_invocable<const _Fp&, range_reference_t<const _Vs>...>
+    {
+      if constexpr (common_range<const _InnerView>)
+	return _Iterator<true>(*this, _M_zip.end());
+      else
+	return _Sentinel<true>(_M_zip.end());
+    }
+
+    constexpr auto
+    size() requires sized_range<_InnerView>
+    { return _M_zip.size(); }
+
+    constexpr auto
+    size() const requires sized_range<const _InnerView>
+    { return _M_zip.size(); }
+  };
+
+  template<class _Fp, class... Rs>
+    zip_transform_view(_Fp, Rs&&...) -> zip_transform_view<_Fp, views::all_t<Rs>...>;
+
+  template<copy_constructible _Fp, input_range... _Vs>
+    requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
+      && regular_invocable<_Fp&, range_reference_t<_Vs>...>
+      && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
+  template<bool _Const>
+  class zip_transform_view<_Fp, _Vs...>::_Iterator : public __iter_cat<_Const>
+  {
+    using _Parent = __detail::__maybe_const_t<_Const, zip_transform_view>;
+
+    _Parent* _M_parent = nullptr;
+    __ziperator<_Const> _M_inner;
+
+    constexpr
+    _Iterator(_Parent& __parent, __ziperator<_Const> __inner)
+      : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner))
+    { }
+
+    friend class zip_transform_view;
+
+  public:
+    // iterator_category defined in zip_transform_view::__iter_cat
+    using iterator_concept = typename __ziperator<_Const>::iterator_concept;
+    using value_type
+      = remove_cvref_t<invoke_result_t<__detail::__maybe_const_t<_Const, _Fp>&,
+				       range_reference_t<__detail::__maybe_const_t<_Const, _Vs>>...>>;
+    using difference_type = range_difference_t<_Base<_Const>>;
+
+    _Iterator() = default;
+
+    constexpr
+    _Iterator(_Iterator<!_Const> __i)
+      requires _Const && convertible_to<__ziperator<false>, __ziperator<_Const>>
+      : _M_parent(__i._M_parent), _M_inner(std::move(__i._M_inner))
+    { }
+
+    constexpr decltype(auto)
+    operator*() const
+    {
+      return std::apply([&](const auto&... __iters) -> decltype(auto) {
+        return std::__invoke(*_M_parent->_M_fun, *__iters...);
+      }, _M_inner._M_current);
+    }
+
+    constexpr _Iterator&
+    operator++()
+    {
+      ++_M_inner;
+      return *this;
+    }
+
+    constexpr void
+    operator++(int)
+    {
+      ++*this;
+    }
+
+    constexpr _Iterator
+    operator++(int) requires forward_range<_Base<_Const>>
+    {
+      auto __tmp = *this;
+      ++*this;
+      return __tmp;
+    }
+
+    constexpr _Iterator&
+    operator--() requires bidirectional_range<_Base<_Const>>
+    {
+      --_M_inner;
+      return *this;
+    }
+
+    constexpr _Iterator
+    operator--(int) requires bidirectional_range<_Base<_Const>>
+    {
+      auto __tmp = *this;
+      --*this;
+      return __tmp;
+    }
+
+    constexpr _Iterator&
+    operator+=(difference_type __x) requires random_access_range<_Base<_Const>>
+    {
+      _M_inner += __x;
+      return *this;
+    }
+
+    constexpr _Iterator&
+    operator-=(difference_type __x) requires random_access_range<_Base<_Const>>
+    {
+      _M_inner -= __x;
+      return *this;
+    }
+
+    constexpr decltype(auto)
+    operator[](difference_type __n) const requires random_access_range<_Base<_Const>>
+    {
+      return std::apply([&]<typename... _Is>(const _Is&... __iters) -> decltype(auto) {
+        return std::__invoke(*_M_parent->_M_fun, __iters[iter_difference_t<_Is>(__n)]...);
+      }, _M_inner._M_current);
+    }
+
+    friend constexpr bool
+    operator==(const _Iterator& __x, const _Iterator& __y)
+      requires equality_comparable<__ziperator<_Const>>
+    { return __x._M_inner == __y._M_inner; }
+
+    friend constexpr bool
+    operator<(const _Iterator& __x, const _Iterator& __y)
+      requires random_access_range<_Base<_Const>>
+    { return __x._M_inner < __y._M_inner; }
+
+    friend constexpr bool
+    operator>(const _Iterator& __x, const _Iterator& __y)
+      requires random_access_range<_Base<_Const>>
+    { return __x._M_inner > __y._M_inner; }
+
+    friend constexpr bool
+    operator<=(const _Iterator& __x, const _Iterator& __y)
+      requires random_access_range<_Base<_Const>>
+    { return __x._M_inner <= __y._M_inner; }
+
+    friend constexpr bool
+    operator>=(const _Iterator& __x, const _Iterator& __y)
+      requires random_access_range<_Base<_Const>>
+    { return __x._M_inner >= __y._M_inner; }
+
+    friend constexpr auto
+    operator<=>(const _Iterator& __x, const _Iterator& __y)
+      requires random_access_range<_Base<_Const>> && three_way_comparable<__ziperator<_Const>>
+    { return __x._M_inner <=> __y._M_inner; }
+
+    friend constexpr _Iterator
+    operator+(const _Iterator& __i, difference_type __n)
+      requires random_access_range<_Base<_Const>>
+    { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
+
+    friend constexpr _Iterator
+    operator+(difference_type __n, const _Iterator& __i)
+      requires random_access_range<_Base<_Const>>
+    { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
+
+    friend constexpr _Iterator
+    operator-(const _Iterator& __i, difference_type __n)
+      requires random_access_range<_Base<_Const>>
+    { return _Iterator(*__i._M_parent, __i._M_inner - __n); }
+
+    friend constexpr difference_type
+    operator-(const _Iterator& __x, const _Iterator& __y)
+      requires sized_sentinel_for<__ziperator<_Const>, __ziperator<_Const>>
+    { return __x._M_inner - __y._M_inner; }
+  };
+
+  template<copy_constructible _Fp, input_range... _Vs>
+    requires (view<_Vs> && ...) && (sizeof...(_Vs) > 0) && is_object_v<_Fp>
+      && regular_invocable<_Fp&, range_reference_t<_Vs>...>
+      && std::__detail::__can_reference<invoke_result_t<_Fp&, range_reference_t<_Vs>...>>
+  template<bool _Const>
+  class zip_transform_view<_Fp, _Vs...>::_Sentinel
+  {
+    __zentinel<_Const> _M_inner;
+
+    constexpr explicit
+    _Sentinel(__zentinel<_Const> __inner)
+      : _M_inner(__inner)
+    { }
+
+    friend class zip_transform_view;
+
+  public:
+    _Sentinel() = default;
+
+    constexpr
+    _Sentinel(_Sentinel<!_Const> __i)
+      requires _Const && convertible_to<__zentinel<false>, __zentinel<_Const>>
+      : _M_inner(std::move(__i._M_inner))
+    { }
+
+    template<bool OtherConst>
+      requires sentinel_for<__zentinel<_Const>, __ziperator<OtherConst>>
+    friend constexpr bool
+    operator==(const _Iterator<OtherConst>& __x, const _Sentinel& __y)
+    { return __x._M_inner == __y._M_inner; }
+
+    template<bool OtherConst>
+      requires sized_sentinel_for<__zentinel<_Const>, __ziperator<OtherConst>>
+    friend constexpr range_difference_t<__detail::__maybe_const_t<OtherConst, _InnerView>>
+    operator-(const _Iterator<OtherConst>& __x, const _Sentinel& __y)
+    { return __x._M_inner - __y._M_inner; }
+
+    template<bool OtherConst>
+      requires sized_sentinel_for<__zentinel<_Const>, __ziperator<OtherConst>>
+    friend constexpr range_difference_t<__detail::__maybe_const_t<OtherConst, _InnerView>>
+    operator-(const _Sentinel& __x, const _Iterator<OtherConst>& __y)
+    { return __x._M_inner - __y._M_inner; }
+  };
+
+  namespace views
+  {
+    namespace __detail
+    {
+      template<typename _Fp, typename... _Ts>
+	concept __can_zip_transform_view
+	  = requires { zip_transform_view(std::declval<_Fp>(), std::declval<_Ts>()...); };
+    }
+
+    struct _ZipTransform
+    {
+      template<typename _Fp, typename... _Ts>
+	requires (sizeof...(_Ts) == 0) || __detail::__can_zip_transform_view<_Fp, _Ts...>
+	[[nodiscard]]
+	constexpr auto
+	operator()(_Fp&& __f, _Ts&&... __ts) const
+	{
+	  if constexpr (sizeof...(_Ts) == 0)
+	    return views::empty<decay_t<invoke_result_t<_Fp>>>;
+	  else
+	    return zip_transform_view(std::forward<_Fp>(__f), std::forward<_Ts>(__ts)...);
+	}
+    };
+
+    inline constexpr _ZipTransform zip_transform;
+  }
 #endif // C++23
 } // namespace ranges
 
diff --git a/libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc b/libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc
new file mode 100644
index 00000000000..5ea24c578a8
--- /dev/null
+++ b/libstdc++-v3/testsuite/std/ranges/zip_transform/1.cc
@@ -0,0 +1,108 @@
+// { 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()
+{
+  static_assert(ranges::empty(views::zip_transform([] { return 0; })));
+
+  auto z1 = views::zip_transform(std::identity{},
+				 std::array{1, 2, 3});
+  VERIFY( ranges::equal(z1, (int[]){1, 2, 3}) );
+  const auto i0 = z1.begin(), i1 = z1.begin() + 1;
+  VERIFY( i0 + 1 - 1 == i0 );
+  VERIFY( i0 < i1 );
+  VERIFY( i1 < z1.end() );
+  VERIFY( i1 - i0 == 1 );
+  VERIFY( i0 - i1 == -1 );
+  VERIFY( z1.end() - i1 == 2 );
+  VERIFY( i1 - z1.end() == -2 );
+  ranges::iter_swap(i0, i1);
+  VERIFY( ranges::equal(std::move(z1), (int[]){2, 1, 3}) );
+
+  auto z2 = views::zip_transform(std::multiplies{},
+				 std::array{-1, 2},
+				 std::array{3, 4, 5});
+  auto i2 = z2.begin();
+  i2 += 1;
+  i2 -= -1;
+  VERIFY( i2 == z2.end() );
+  VERIFY( ranges::size(z2) == 2 );
+  VERIFY( ranges::size(std::as_const(z2)) == 2 );
+  VERIFY( ranges::equal(z2, (int[]){-3, 8}) );
+
+  auto z3 = views::zip_transform([] (auto... xs) { return ranges::max({xs...}); },
+				 std::array{1, 6, 7, 0, 0},
+				 std::array{2, 5, 9},
+				 std::array{3, 4, 8, 0});
+  VERIFY( ranges::size(z3) == 3 );
+  VERIFY( ranges::equal(z3, (int[]){3, 6, 9}) );
+
+  return true;
+}
+
+constexpr bool
+test02()
+{
+  using __gnu_test::test_input_range;
+  using __gnu_test::test_forward_range;
+  using __gnu_test::test_random_access_range;
+
+  using ty1 = ranges::zip_transform_view<std::plus<>,
+					 views::all_t<test_forward_range<int>>,
+					 views::all_t<test_random_access_range<int>>>;
+  static_assert(ranges::forward_range<ty1>);
+  static_assert(!ranges::random_access_range<ty1>);
+  static_assert(!ranges::sized_range<ty1>);
+
+  using ty2 = ranges::zip_transform_view<decltype([](int, int, int) { return 0; }),
+					 views::all_t<test_forward_range<int>>,
+					 views::all_t<test_input_range<int>>,
+					 views::all_t<test_forward_range<int>>>;
+  static_assert(ranges::input_range<ty2>);
+  static_assert(!ranges::forward_range<ty2>);
+  static_assert(!ranges::sized_range<ty2>);
+
+  return true;
+}
+
+constexpr bool
+test03()
+{
+  int u[] = {1, 2, 3, 4}, v[] = {4, 5, 6};
+  auto z = views::zip_transform(std::plus{},
+				u | views::filter([](auto) { return true; }),
+				v);
+  using ty = decltype(z);
+  static_assert(ranges::forward_range<ty>);
+  static_assert(!ranges::common_range<ty>);
+  static_assert(!ranges::sized_range<ty>);
+  VERIFY( z.begin() == z.begin() );
+  VERIFY( z.begin() != z.end() );
+  VERIFY( ranges::next(z.begin(), 3) == z.end() );
+  auto it = z.begin();
+  ++it;
+  it++;
+  it--;
+  --it;
+  VERIFY( it == z.begin() );
+
+  return true;
+}
+
+int
+main()
+{
+  static_assert(test01());
+  static_assert(test02());
+  static_assert(test03());
+}
-- 
2.37.2.382.g795ea8776b


             reply	other threads:[~2022-08-25 15:40 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-08-25 15:39 Patrick Palka [this message]
2022-08-25 15:39 ` [PATCH 2/2] libstdc++: Implement LWG 3692/3702 changes to zip_/zip_transform_view Patrick Palka
2022-08-26 19:58   ` Jonathan Wakely
2022-08-26 19:58 ` [PATCH 1/2] libstdc++: Implement ranges::zip_transform_view from P2321R2 Jonathan Wakely

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20220825153938.2249619-1-ppalka@redhat.com \
    --to=ppalka@redhat.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=libstdc++@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).