libstdc++: Implement ranges::adjacent_transform_view from P2321R2

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_transform): Define.
	* testsuite/std/ranges/adaptors/adjacent_transform/1.cc: New test.

2 files changed, 447 insertions, 0 deletions

diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges
index 39822b7..dad1e4c 100644
--- a/libstdc++-v3/include/std/ranges
+++ b/libstdc++-v3/include/std/ranges
@@ -5156,6 +5156,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 is callable with 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>
@@ -5203,6 +5217,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());
@@ -5437,6 +5458,326 @@ 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>
+	  constexpr auto
+	  operator() [[nodiscard]] (_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 0000000..07f20b7
--- /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());
+}