[libc++] Add the std::views::reverse range adaptor

[• Quuxplusone]

libcxx/include/__ranges/reverse_view.h

129

s/!= subrange_kind::sized/== subrange_kind::unsized/
They're not likely to add any more than the existing two enumerator values to subrange_kind, but if they ever did, I wouldn't want to hazard a guess as to what their semantics would be.

166

Rather than the _UnwrappedSubrange parameter, maybe consider something like

noexcept(noexcept(__unwrap_subrange(_VSTD::forward<_Range>(__range))))
-> decltype(     (__unwrap_subrange(_VSTD::forward<_Range>(__range))))

with a static constexpr auto __unwrap_subrange(auto&& __range) defined appropriately. That wouldn't make the compiler's job any easier, but it would make these lines (155-157, 164-166) shorter and less repetitive.
Making _UnwrappedSubrange(~~~) sometimes come out to void(~~~) is a subtle trick.

libcxx/test/std/ranges/range.adaptors/range.reverse/adaptor.pass.cpp

54

Is BidirRange defined in "types.h"? I'd guess that std::ranges::iterator_t<BidirRange> should be bidirectional_iterator<int*> (or something: what is its value type?), from "test_iterators.h". If it is, maybe we could just say that.
We could even just say

using C = std::list<int>;
C lst = {1,2,3};
auto reversed = std::ranges::subrange(lst.rbegin(), lst.rend());
auto rereversed = std::views::reverse(reversed);
ASSERT_SAME_TYPE(decltype(rereversed), std::ranges::subrange<C::iterator, C::iterator>);

but that might be too lax.

61

Why is this not just

auto subrange = std::ranges::subrange(std::ranges::rbegin(view), std::ranges::rend(view), 3);

I think that'd be the same thing, and easier to read IMHO.

[ldionne]

Address review comments and fix bug on GCC.

libcxx/include/__ranges/reverse_view.h

166

I tried your suggestion but it merely shifts the repetition from one place to another (unless I misunderstood what you were thinking of). Whatever I do, I end up with something that's not much better than the patch as-is, cause the implementation of __unwrap_subrange needs to contain the duplication. Were you thinking about something else?

I did remove all those std::forward though, since they don't add anything and just double up the length of the line.

libcxx/test/std/ranges/range.adaptors/range.reverse/adaptor.pass.cpp

54

Changed to bidirectional_iterator<int*> instead of ranges::iterator_t, but I'll keep using BidirRange since it's more minimal than std::list.

61

You're right, but it seems like we haven't implemented ranges::rbegin and ranges::rend yet.

[• Quuxplusone]

libcxx/include/__ranges/reverse_view.h

166

I tried your suggestion but it merely shifts the repetition from one place to another (unless I misunderstood what you were thinking of).

I'm no longer sure myself, so, okay. :)
Re removing the forwards: I think that's OK, but it would be good to check with @tcanens or someone. My rule for coding with Ranges is "Always pass by forwarding reference, never forward," because forwarding can only ever turn lvalues back into rvalues, and Ranges hates rvalues. However, is it conceivable that the user could supply some evil kind of _Range where r.begin() and std::move(r).begin() do different things? or is that forbidden by the concept?

[tcanens]

libcxx/include/__ranges/reverse_view.h

166

ranges::begin only ever calls begin on lvalues nowadays.

[Mordante]

LGTM!

libcxx/include/__ranges/reverse_view.h

 #include <__iterator/concepts.h>
 #include <__iterator/next.h>
 #include <__iterator/reverse_iterator.h>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/concepts.h>
 #include <__ranges/enable_borrowed_range.h>
 #include <__ranges/non_propagating_cache.h>
+#include <__ranges/range_adaptor.h>
 #include <__ranges/size.h>
+#include <__ranges/subrange.h>
 #include <__ranges/view_interface.h>
+#include <__utility/forward.h>
 #include <__utility/move.h>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
public:
     }
   };
 
   template<class _Range>
   reverse_view(_Range&&) -> reverse_view<views::all_t<_Range>>;
 
   template<class _Tp>
   inline constexpr bool enable_borrowed_range<reverse_view<_Tp>> = enable_borrowed_range<_Tp>;
+
+  namespace views {
+  namespace __reverse {
+    template<class _Tp>
+    constexpr bool __is_reverse_view = false;
+
+    template<class _Tp>
+    constexpr bool __is_reverse_view<reverse_view<_Tp>> = true;
+
+    template<class _Tp>
+    constexpr bool __is_sized_reverse_subrange = false;
+
+    template<class _Iter>
+    constexpr bool __is_sized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, subrange_kind::sized>> = true;
+
+    template<class _Tp>
+    constexpr bool __is_unsized_reverse_subrange = false;
+
+    template<class _Iter, subrange_kind _Kind>
+    constexpr bool __is_unsized_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> = _Kind == subrange_kind::unsized;
+
+    template<class _Tp>
+    struct __unwrapped_reverse_subrange {
+      using type = void; // avoid SFINAE-ing out the overload below -- let the concept requirements do it for better diagnostics
+    };
+
+    template<class _Iter, subrange_kind _Kind>
+    struct __unwrapped_reverse_subrange<subrange<reverse_iterator<_Iter>, reverse_iterator<_Iter>, _Kind>> {
+      using type = subrange<_Iter, _Iter, _Kind>;
+    };
+
+    struct __fn : __range_adaptor_closure<__fn> {
+      template<class _Range>
+        requires __is_reverse_view<remove_cvref_t<_Range>>
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Range&& __range) const
+        noexcept(noexcept(_VSTD::forward<_Range>(__range).base()))
+        -> decltype(      _VSTD::forward<_Range>(__range).base())
+        { return          _VSTD::forward<_Range>(__range).base(); }
+
+      template<class _Range,
+               class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type>
+        requires __is_sized_reverse_subrange<remove_cvref_t<_Range>>
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Range&& __range) const
+        noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size())))
+        -> decltype(      _UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size()))
+        { return          _UnwrappedSubrange(__range.end().base(), __range.begin().base(), __range.size()); }
+
+      template<class _Range,
+               class _UnwrappedSubrange = typename __unwrapped_reverse_subrange<remove_cvref_t<_Range>>::type>
+        requires __is_unsized_reverse_subrange<remove_cvref_t<_Range>>
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Range&& __range) const
+        noexcept(noexcept(_UnwrappedSubrange(__range.end().base(), __range.begin().base())))
+        -> decltype(      _UnwrappedSubrange(__range.end().base(), __range.begin().base()))
+        { return          _UnwrappedSubrange(__range.end().base(), __range.begin().base()); }
+
+      template<class _Range>
+        requires (!__is_reverse_view<remove_cvref_t<_Range>> &&
+                  !__is_sized_reverse_subrange<remove_cvref_t<_Range>> &&
+                  !__is_unsized_reverse_subrange<remove_cvref_t<_Range>>)
+      [[nodiscard]] _LIBCPP_HIDE_FROM_ABI
+      constexpr auto operator()(_Range&& __range) const
+        noexcept(noexcept(reverse_view{_VSTD::forward<_Range>(__range)}))
+        -> decltype(      reverse_view{_VSTD::forward<_Range>(__range)})
+        { return          reverse_view{_VSTD::forward<_Range>(__range)}; }
+    };
+  }
+
+  inline namespace __cpo {
+    inline constexpr auto reverse = __reverse::__fn{};
+  }
+  } // namespace views
 } // namespace ranges
 
 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___RANGES_REVERSE_VIEW_H

libcxx/test/std/ranges/range.adaptors/range.reverse/adaptor.nodiscard.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+// REQUIRES: libc++
+
+// Test the libc++ extension that std::views::reverse is marked as [[nodiscard]] to avoid
+// the potential for user mistakenly thinking they're calling an algorithm.
+
+#include <ranges>
+
+void test() {
+  int range[] = {1, 2, 3};
+
+  std::views::reverse(range); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+  range | std::views::reverse; // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+  std::views::reverse | std::views::reverse; // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+}

libcxx/test/std/ranges/range.adaptors/range.reverse/adaptor.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// std::views::reverse
+
+#include <ranges>
+
+#include <cassert>
+#include <concepts>
+#include <iterator>
+#include <utility>
+
+#include "types.h"
+
+template <class View, class T>
+concept CanBePiped = requires (View&& view, T&& t) {
+  { std::forward<View>(view) | std::forward<T>(t) };
+};
+
+constexpr bool test() {
+  int buf[] = {1, 2, 3};
+
+  // views::reverse(x) is equivalent to x.base() if x is a reverse_view
+  {
+    {
+      BidirRange view(buf, buf + 3);
+      std::ranges::reverse_view<BidirRange> reversed(view);
+      std::same_as<BidirRange> auto result = std::views::reverse(reversed);
+      assert(result.begin_ == buf);
+      assert(result.end_ == buf + 3);
+    }
+    {
+      // Common use case is worth testing
+      BidirRange view(buf, buf + 3);
+      std::same_as<BidirRange> auto result = std::views::reverse(std::views::reverse(view));
+      assert(result.begin_ == buf);
+      assert(result.end_ == buf + 3);
+    }
+  }
+
+  // views::reverse(x) is equivalent to subrange{end, begin, size} if x is a
+  // sized subrange over reverse iterators
+  {
+    using It = bidirectional_iterator<int*>;
+    using Subrange = std::ranges::subrange<It, It, std::ranges::subrange_kind::sized>;
+
+    using ReverseIt = std::reverse_iterator<It>;
+    using ReverseSubrange = std::ranges::subrange<ReverseIt, ReverseIt, std::ranges::subrange_kind::sized>;
+
+    {
+      BidirRange view(buf, buf + 3);
+      ReverseSubrange subrange(ReverseIt(std::ranges::end(view)), ReverseIt(std::ranges::begin(view)), /* size */3);
+      std::same_as<Subrange> auto result = std::views::reverse(subrange);
+      assert(result.begin().base() == buf);
+      assert(result.end().base() == buf + 3);
+    }
+    {
+      // std::move into views::reverse
+      BidirRange view(buf, buf + 3);
+      ReverseSubrange subrange(ReverseIt(std::ranges::end(view)), ReverseIt(std::ranges::begin(view)), /* size */3);
+      std::same_as<Subrange> auto result = std::views::reverse(std::move(subrange));
+      assert(result.begin().base() == buf);
+      assert(result.end().base() == buf + 3);
+    }
+    {
+      // with a const subrange
+      BidirRange view(buf, buf + 3);
+      ReverseSubrange const subrange(ReverseIt(std::ranges::end(view)), ReverseIt(std::ranges::begin(view)), /* size */3);
+      std::same_as<Subrange> auto result = std::views::reverse(subrange);
+      assert(result.begin().base() == buf);
+      assert(result.end().base() == buf + 3);
+    }
+  }
+
+  // views::reverse(x) is equivalent to subrange{end, begin} if x is an
+  // unsized subrange over reverse iterators
+  {
+    using It = bidirectional_iterator<int*>;
+    using Subrange = std::ranges::subrange<It, It, std::ranges::subrange_kind::unsized>;
+
+    using ReverseIt = std::reverse_iterator<It>;
+    using ReverseSubrange = std::ranges::subrange<ReverseIt, ReverseIt, std::ranges::subrange_kind::unsized>;
+
+    {
+      BidirRange view(buf, buf + 3);
+      ReverseSubrange subrange(ReverseIt(std::ranges::end(view)), ReverseIt(std::ranges::begin(view)));
+      std::same_as<Subrange> auto result = std::views::reverse(subrange);
+      assert(result.begin().base() == buf);
+      assert(result.end().base() == buf + 3);
+    }
+    {
+      // std::move into views::reverse
+      BidirRange view(buf, buf + 3);
+      ReverseSubrange subrange(ReverseIt(std::ranges::end(view)), ReverseIt(std::ranges::begin(view)));
+      std::same_as<Subrange> auto result = std::views::reverse(std::move(subrange));
+      assert(result.begin().base() == buf);
+      assert(result.end().base() == buf + 3);
+    }
+    {
+      // with a const subrange
+      BidirRange view(buf, buf + 3);
+      ReverseSubrange const subrange(ReverseIt(std::ranges::end(view)), ReverseIt(std::ranges::begin(view)));
+      std::same_as<Subrange> auto result = std::views::reverse(subrange);
+      assert(result.begin().base() == buf);
+      assert(result.end().base() == buf + 3);
+    }
+  }
+
+  // Otherwise, views::reverse(x) is equivalent to ranges::reverse_view{x}
+  {
+    BidirRange view(buf, buf + 3);
+    std::same_as<std::ranges::reverse_view<BidirRange>> auto result = std::views::reverse(view);
+    assert(result.begin().base().base() == buf + 3);
+    assert(result.end().base().base() == buf);
+  }
+
+  // Test that std::views::reverse is a range adaptor
+  {
+    // Test `v | views::reverse`
+    {
+      BidirRange view(buf, buf + 3);
+      std::same_as<std::ranges::reverse_view<BidirRange>> auto result = view | std::views::reverse;
+      assert(result.begin().base().base() == buf + 3);
+      assert(result.end().base().base() == buf);
+    }
+
+    // Test `adaptor | views::reverse`
+    {
+      BidirRange view(buf, buf + 3);
+      auto f = [](int i) { return i; };
+      auto const partial = std::views::transform(f) | std::views::reverse;
+      using Result = std::ranges::reverse_view<std::ranges::transform_view<BidirRange, decltype(f)>>;
+      std::same_as<Result> auto result = partial(view);
+      assert(result.begin().base().base().base() == buf + 3);
+      assert(result.end().base().base().base() == buf);
+    }
+
+    // Test `views::reverse | adaptor`
+    {
+      BidirRange view(buf, buf + 3);
+      auto f = [](int i) { return i; };
+      auto const partial = std::views::reverse | std::views::transform(f);
+      using Result = std::ranges::transform_view<std::ranges::reverse_view<BidirRange>, decltype(f)>;
+      std::same_as<Result> auto result = partial(view);
+      assert(result.begin().base().base().base() == buf + 3);
+      assert(result.end().base().base().base() == buf);
+    }
+
+    // Check SFINAE friendliness
+    {
+      struct NotABidirRange { };
+      static_assert(!std::is_invocable_v<decltype(std::views::reverse)>);
+      static_assert(!std::is_invocable_v<decltype(std::views::reverse), NotABidirRange>);
+      static_assert( CanBePiped<BidirRange,     decltype(std::views::reverse)>);
+      static_assert( CanBePiped<BidirRange&,    decltype(std::views::reverse)>);
+      static_assert(!CanBePiped<NotABidirRange, decltype(std::views::reverse)>);
+    }
+  }
+
+  {
+    static_assert(std::same_as<decltype(std::views::reverse), decltype(std::ranges::views::reverse)>);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}