Re: [PATCH 1/2] libstdc++: Implement ranges::zip_transform_view from P2321R2

[Jonathan Wakely <jwakely@redhat.com>]

On Thu, 25 Aug 2022 at 16:40, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?

OK, thanks.

>
> 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
>