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

[Jonathan Wakely <jwakely@redhat.com>]

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

OK


>
> libstdc++-v3/ChangeLog:
>
>         * include/std/ranges (__detail::__unarize): Define.
>         (adjacent_view::_Iterator): Befriend adjacent_transform_view.
>         (adjacent_transform_view): Define.
>         (adjacent_transform_view::_Iterator): Define.
>         (adjacent_transform_view::_Sentinel): Define.
>         (views::__detail::__can_adjacent_transform_view): Define.
>         (views::_AdjacentTransform): Define.
>         (views::adjacent_transform): Define.
>         (views::pairwise): Define.
>         * testsuite/std/ranges/adaptors/adjacent_transform/1.cc: New test.
> ---
>  libstdc++-v3/include/std/ranges               | 342 ++++++++++++++++++
>  .../ranges/adaptors/adjacent_transform/1.cc   | 106 ++++++
>  2 files changed, 448 insertions(+)
>  create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc
>
> diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
> index 4fb879a088c..3a7f0545030 100644
> --- a/libstdc++-v3/include/std/ranges
> +++ b/libstdc++-v3/include/std/ranges
> @@ -5158,6 +5158,20 @@ namespace views::__adaptor
>      // Yields tuple<_Tp, ..., _Tp> with _Nm elements.
>      template<typename _Tp, size_t _Nm>
>        using __repeated_tuple = decltype(std::tuple_cat(std::declval<array<_Tp, _Nm>>()));
> +
> +    // For a functor F that takes N arguments, the expression declval<__unarize<F, N>>(x)
> +    // is equivalent to declval<F>(x, ..., x).
> +    template<typename _Fp, size_t _Nm>
> +      struct __unarize
> +      {
> +       template<typename... _Ts>
> +         static invoke_result_t<_Fp, _Ts...>
> +         __tuple_apply(const tuple<_Ts...>&); // not defined
> +
> +       template<typename _Tp>
> +         decltype(__tuple_apply(std::declval<__repeated_tuple<_Tp, _Nm>>()))
> +         operator()(_Tp&&); // not defined
> +      };
>    }
>
>    template<forward_range _Vp, size_t _Nm>
> @@ -5205,6 +5219,13 @@ namespace views::__adaptor
>
>      friend class adjacent_view;
>
> +    template<forward_range _Wp, copy_constructible _Fp, size_t _Mm>
> +      requires view<_Wp> && (_Mm > 0) && is_object_v<_Fp>
> +        && regular_invocable<__detail::__unarize<_Fp&, _Mm>, range_reference_t<_Wp>>
> +        && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Mm>,
> +                                                        range_reference_t<_Wp>>>
> +      friend class adjacent_transform_view;
> +
>    public:
>      using iterator_category = input_iterator_tag;
>      using iterator_concept = decltype(_S_iter_concept());
> @@ -5440,6 +5461,327 @@ namespace views::__adaptor
>
>      inline constexpr auto pairwise = adjacent<2>;
>    }
> +
> +  template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
> +   requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
> +     && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
> +     && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
> +                                                      range_reference_t<_Vp>>>
> +  class adjacent_transform_view : public view_interface<adjacent_transform_view<_Vp, _Fp, _Nm>>
> +  {
> +    [[no_unique_address]] __detail::__box<_Fp> _M_fun;
> +    adjacent_view<_Vp, _Nm> _M_inner;
> +
> +    using _InnerView = adjacent_view<_Vp, _Nm>;
> +
> +    template<bool _Const>
> +      using _InnerIter = iterator_t<__detail::__maybe_const_t<_Const, _InnerView>>;
> +
> +    template<bool _Const>
> +      using _InnerSent = sentinel_t<__detail::__maybe_const_t<_Const, _InnerView>>;
> +
> +    template<bool> class _Iterator;
> +    template<bool> class _Sentinel;
> +
> +  public:
> +    adjacent_transform_view() = default;
> +
> +    constexpr explicit
> +    adjacent_transform_view(_Vp __base, _Fp __fun)
> +      : _M_fun(std::move(__fun)), _M_inner(std::move(__base))
> +    { }
> +
> +    constexpr auto
> +    begin()
> +    { return _Iterator<false>(*this, _M_inner.begin()); }
> +
> +    constexpr auto
> +    begin() const
> +      requires range<const _InnerView>
> +       && regular_invocable<__detail::__unarize<const _Fp&, _Nm>,
> +                            range_reference_t<const _Vp>>
> +    { return _Iterator<true>(*this, _M_inner.begin()); }
> +
> +    constexpr auto
> +    end()
> +    {
> +      if constexpr (common_range<_InnerView>)
> +        return _Iterator<false>(*this, _M_inner.end());
> +      else
> +        return _Sentinel<false>(_M_inner.end());
> +    }
> +
> +    constexpr auto
> +    end() const
> +      requires range<const _InnerView>
> +       && regular_invocable<__detail::__unarize<const _Fp&, _Nm>,
> +                            range_reference_t<const _Vp>>
> +    {
> +      if constexpr (common_range<const _InnerView>)
> +        return _Iterator<true>(*this, _M_inner.end());
> +      else
> +        return _Sentinel<true>(_M_inner.end());
> +    }
> +
> +    constexpr auto
> +    size() requires sized_range<_InnerView>
> +    { return _M_inner.size(); }
> +
> +    constexpr auto
> +    size() const requires sized_range<const _InnerView>
> +    { return _M_inner.size(); }
> +  };
> +
> +  template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
> +   requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
> +     && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
> +     && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
> +                                                      range_reference_t<_Vp>>>
> +  template<bool _Const>
> +  class adjacent_transform_view<_Vp, _Fp, _Nm>::_Iterator
> +  {
> +    using _Parent = __detail::__maybe_const_t<_Const, adjacent_transform_view>;
> +    using _Base = __detail::__maybe_const_t<_Const, _Vp>;
> +
> +    _Parent* _M_parent = nullptr;
> +    _InnerIter<_Const> _M_inner;
> +
> +    constexpr
> +    _Iterator(_Parent& __parent, _InnerIter<_Const> __inner)
> +      : _M_parent(std::__addressof(__parent)), _M_inner(std::move(__inner))
> +    { }
> +
> +    static auto
> +    _S_iter_cat()
> +    {
> +      using __detail::__maybe_const_t;
> +      using __detail::__unarize;
> +      using _Res = invoke_result_t<__unarize<__maybe_const_t<_Const, _Fp>&, _Nm>,
> +                                  range_reference_t<_Base>>;
> +      using _Cat = iterator_traits<iterator_t<_Base>>::iterator_category;
> +      if constexpr (!is_lvalue_reference_v<_Res>)
> +       return input_iterator_tag{};
> +      else if constexpr (derived_from<_Cat, random_access_iterator_tag>)
> +       return random_access_iterator_tag{};
> +      else if constexpr (derived_from<_Cat, bidirectional_iterator_tag>)
> +       return bidirectional_iterator_tag{};
> +      else if constexpr (derived_from<_Cat, forward_iterator_tag>)
> +       return forward_iterator_tag{};
> +      else
> +       return input_iterator_tag{};
> +    }
> +
> +    friend class adjacent_transform_view;
> +
> +  public:
> +    using iterator_category = decltype(_S_iter_cat());
> +    using iterator_concept = typename _InnerIter<_Const>::iterator_concept;
> +    using value_type
> +      = remove_cvref_t<invoke_result_t
> +                      <__detail::__unarize<__detail::__maybe_const_t<_Const, _Fp>&, _Nm>,
> +                       range_reference_t<_Base>>>;
> +    using difference_type = range_difference_t<_Base>;
> +
> +    _Iterator() = default;
> +
> +    constexpr
> +    _Iterator(_Iterator<!_Const> __i)
> +      requires _Const && convertible_to<_InnerIter<false>, _InnerIter<_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 _Iterator
> +    operator++(int)
> +    {
> +      auto __tmp = *this;
> +      ++*this;
> +      return __tmp;
> +    }
> +
> +    constexpr _Iterator&
> +    operator--() requires bidirectional_range<_Base>
> +    {
> +      --_M_inner;
> +      return *this;
> +    }
> +
> +    constexpr _Iterator
> +    operator--(int) requires bidirectional_range<_Base>
> +    {
> +      auto __tmp = *this;
> +      --*this;
> +      return __tmp;
> +    }
> +
> +    constexpr _Iterator&
> +    operator+=(difference_type __x) requires random_access_range<_Base>
> +    {
> +      _M_inner += __x;
> +      return *this;
> +    }
> +
> +    constexpr _Iterator&
> +    operator-=(difference_type __x) requires random_access_range<_Base>
> +    {
> +      _M_inner -= __x;
> +      return *this;
> +    }
> +
> +    constexpr decltype(auto)
> +    operator[](difference_type __n) const requires random_access_range<_Base>
> +    {
> +      return std::apply([&](const auto&... __iters) -> decltype(auto) {
> +        return std::__invoke(*_M_parent->_M_fun, __iters[__n]...);
> +      }, _M_inner._M_current);
> +    }
> +
> +    friend constexpr bool
> +    operator==(const _Iterator& __x, const _Iterator& __y)
> +    { return __x._M_inner == __y._M_inner; }
> +
> +    friend constexpr bool
> +    operator<(const _Iterator& __x, const _Iterator& __y)
> +      requires random_access_range<_Base>
> +    { return __x._M_inner < __y._M_inner; }
> +
> +    friend constexpr bool
> +    operator>(const _Iterator& __x, const _Iterator& __y)
> +      requires random_access_range<_Base>
> +    { return __x._M_inner > __y._M_inner; }
> +
> +    friend constexpr bool
> +    operator<=(const _Iterator& __x, const _Iterator& __y)
> +      requires random_access_range<_Base>
> +    { return __x._M_inner <= __y._M_inner; }
> +
> +    friend constexpr bool
> +    operator>=(const _Iterator& __x, const _Iterator& __y)
> +      requires random_access_range<_Base>
> +    { return __x._M_inner >= __y._M_inner; }
> +
> +    friend constexpr auto
> +    operator<=>(const _Iterator& __x, const _Iterator& __y)
> +      requires random_access_range<_Base> &&
> +      three_way_comparable<_InnerIter<_Const>>
> +    { return __x._M_inner <=> __y._M_inner; }
> +
> +    friend constexpr _Iterator
> +    operator+(const _Iterator& __i, difference_type __n)
> +      requires random_access_range<_Base>
> +    { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
> +
> +    friend constexpr _Iterator
> +    operator+(difference_type __n, const _Iterator& __i)
> +      requires random_access_range<_Base>
> +    { return _Iterator(*__i._M_parent, __i._M_inner + __n); }
> +
> +    friend constexpr _Iterator
> +    operator-(const _Iterator& __i, difference_type __n)
> +      requires random_access_range<_Base>
> +    { return _Iterator(*__i._M_parent, __i._M_inner - __n); }
> +
> +    friend constexpr difference_type
> +    operator-(const _Iterator& __x, const _Iterator& __y)
> +      requires sized_sentinel_for<_InnerIter<_Const>, _InnerIter<_Const>>
> +    { return __x._M_inner - __y._M_inner; }
> +  };
> +
> +  template<forward_range _Vp, copy_constructible _Fp, size_t _Nm>
> +   requires view<_Vp> && (_Nm > 0) && is_object_v<_Fp>
> +     && regular_invocable<__detail::__unarize<_Fp&, _Nm>, range_reference_t<_Vp>>
> +     && std::__detail::__can_reference<invoke_result_t<__detail::__unarize<_Fp&, _Nm>,
> +                                                      range_reference_t<_Vp>>>
> +  template<bool _Const>
> +  class adjacent_transform_view<_Vp, _Fp, _Nm>::_Sentinel
> +  {
> +    _InnerSent<_Const> _M_inner;
> +
> +    constexpr explicit
> +    _Sentinel(_InnerSent<_Const> __inner)
> +      : _M_inner(__inner)
> +    { }
> +
> +    friend class adjacent_transform_view;
> +
> +  public:
> +    _Sentinel() = default;
> +
> +    constexpr
> +    _Sentinel(_Sentinel<!_Const> __i)
> +      requires _Const && convertible_to<_InnerSent<false>, _InnerSent<_Const>>
> +      : _M_inner(std::move(__i._M_inner))
> +    { }
> +
> +    template<bool _OtherConst>
> +      requires sentinel_for<_InnerSent<_Const>, _InnerIter<_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<_InnerSent<_Const>, _InnerIter<_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<_InnerSent<_Const>, _InnerIter<_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<size_t _Nm, typename _Range, typename _Fp>
> +       concept __can_adjacent_transform_view
> +         = requires { adjacent_transform_view<all_t<_Range>, decay_t<_Fp>, _Nm>
> +                        (std::declval<_Range>(), std::declval<_Fp>()); };
> +    }
> +
> +    template<size_t _Nm>
> +      struct _AdjacentTransform : __adaptor::_RangeAdaptor<_AdjacentTransform<_Nm>>
> +      {
> +       template<viewable_range _Range, typename _Fp>
> +         requires (_Nm == 0) || __detail::__can_adjacent_transform_view<_Nm, _Range, _Fp>
> +         [[nodiscard]]
> +         constexpr auto
> +         operator()(_Range&& __r, _Fp&& __f) const
> +         {
> +           if constexpr (_Nm == 0)
> +             return views::empty<tuple<>>;
> +           else
> +             return adjacent_transform_view<all_t<_Range>, decay_t<_Fp>, _Nm>
> +               (std::forward<_Range>(__r), std::forward<_Fp>(__f));
> +         }
> +
> +       using __adaptor::_RangeAdaptor<_AdjacentTransform>::operator();
> +       static constexpr int _S_arity = 2;
> +       static constexpr bool _S_has_simple_extra_args = true;
> +      };
> +
> +    template<size_t _Nm>
> +      inline constexpr _AdjacentTransform<_Nm> adjacent_transform;
> +
> +    inline constexpr auto pairwise_transform = adjacent_transform<2>;
> +  }
>  #endif // C++23
>  } // namespace ranges
>
> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc
> new file mode 100644
> index 00000000000..07f20b702dd
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/adjacent_transform/1.cc
> @@ -0,0 +1,106 @@
> +// { 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()
> +{
> +  auto v1 = std::array{1, 2, 3} | views::adjacent_transform<1>(std::identity{});
> +  VERIFY( ranges::equal(v1, (int[]){1, 2, 3}) );
> +  const auto i0 = v1.begin(), i1 = v1.begin() + 1;
> +  VERIFY( i0 + 1 - 1 == i0 );
> +  VERIFY( i0 < i1 );
> +  VERIFY( i1 < v1.end() );
> +  VERIFY( i1 - i0 == 1 );
> +  VERIFY( i0 - i1 == -1 );
> +  VERIFY( v1.end() - i1 == 2 );
> +  VERIFY( i1 - v1.end() == -2 );
> +  ranges::iter_swap(i0, i1);
> +  VERIFY( ranges::equal(std::move(v1), (int[]){2, 1, 3}) );
> +
> +  auto v2 = std::array{1, -1, 2, -2} | views::pairwise_transform(std::multiplies{});
> +  auto i2 = v2.begin();
> +  i2 += 1;
> +  i2 -= -2;
> +  VERIFY( i2 == v2.end() );
> +  VERIFY( ranges::size(v2) == 3 );
> +  VERIFY( ranges::size(std::as_const(v2)) == 3 );
> +  VERIFY( ranges::equal(v2, (int[]){-1, -2, -4}) );
> +
> +  int y[] = {1, 2, 3, 4, 5, 6};
> +  auto v3 = y | views::adjacent_transform<3>([](auto... xs) { return ranges::max({xs...}); });
> +  VERIFY( ranges::size(v3) == 4 );
> +  VERIFY( ranges::equal(v3, (int[]){3, 4, 5, 6}) );
> +
> +  const auto v6 = y | views::adjacent_transform<6>([](auto...) { return 0; });
> +  VERIFY( ranges::equal(v6, (int[]){0}) );
> +
> +  const auto v7 = y | views::adjacent_transform<7>([](auto...) { return 0; });
> +  VERIFY( ranges::empty(v7) );
> +
> +  const auto v0 = y | views::adjacent_transform<0>([] { return 0; });
> +  VERIFY( ranges::empty(v0) );
> +
> +  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::adjacent_transform_view<views::all_t<test_forward_range<int>>,
> +                                             std::plus<>, 2>;
> +  static_assert(ranges::forward_range<ty1>);
> +  static_assert(!ranges::bidirectional_range<ty1>);
> +  static_assert(!ranges::sized_range<ty1>);
> +
> +  using ty2 = ranges::adjacent_transform_view<views::all_t<test_random_access_range<int>>,
> +                                             decltype([](int, int, int) { return 0;}), 3>;
> +  static_assert(ranges::random_access_range<ty2>);
> +  static_assert(ranges::sized_range<ty2>);
> +
> +  return true;
> +}
> +
> +constexpr bool
> +test03()
> +{
> +  auto v = views::iota(0, 4)
> +    | views::filter([](auto) { return true; })
> +    | views::pairwise_transform(std::plus{});
> +  using ty = decltype(v);
> +  static_assert(ranges::forward_range<ty>);
> +  static_assert(ranges::common_range<ty>);
> +  static_assert(!ranges::sized_range<ty>);
> +  VERIFY( v.begin() == v.begin() );
> +  VERIFY( v.begin() != v.end() );
> +  VERIFY( ranges::next(v.begin(), 3) == v.end() );
> +  auto it = v.begin();
> +  ++it;
> +  it++;
> +  VERIFY( ranges::next(it) == v.end() );
> +  it--;
> +  --it;
> +  VERIFY( it == v.begin() );
> +
> +  return true;
> +}
> +
> +int
> +main()
> +{
> +  static_assert(test01());
> +  static_assert(test02());
> +  static_assert(test03());
> +}
> --
> 2.37.2.490.g6c8e4ee870
>