[libc++] Implement ranges::reverse

[philnik]

• Fix CI

[var-const]

In general looks really good, thanks! (just a few comments)

libcxx/include/__algorithm/ranges_reverse.h

41

Question: how is this loop more efficient than the non-random access iterator version?

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse.pass.cpp

13

Can you also check the complexity requirement?

35

Can you also check the permutable constraint?

48

Nit: decltype(auto).

63

Please also check an odd number of elements.

libcxx/test/support/almost_satisfies_types.h

142

Nit: make it a struct, so that it won't be necessary to specify public?

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_reverse.h

41

In the forward variant we have to check that __first != __end and __first != --__end. In the random-access version we can just check that __first < --__end, so we do half the comparisons.

libcxx/test/support/almost_satisfies_types.h

142

I made everything else in this file a class and then made it public. I'd rather keep it that way for consistency.

[var-const]

Thanks! Sorry about slow reviews.

libcxx/test/support/almost_satisfies_types.h

199

Nit: there's an extra blank line here.

libcxx/docs/Status/RangesAlgorithms.csv

 Write,partial_sort_copy,Not assigned,n/a,Not started
 Merge,merge,Not assigned,n/a,Not started
 Merge,set_difference,Not assigned,n/a,Not started
 Merge,set_intersection,Not assigned,n/a,Not started
 Merge,set_symmetric_difference,Not assigned,n/a,Not started
 Merge,set_union,Not assigned,n/a,Not started
 Permutation,remove,Not assigned,n/a,Not started
 Permutation,remove_if,Not assigned,n/a,Not started
-Permutation,reverse,Not assigned,n/a,Not started
+Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 Permutation,rotate,Not assigned,n/a,Not started
 Permutation,shuffle,Not assigned,n/a,Not started
 Permutation,unique,Not assigned,n/a,Not started
 Permutation,partition,Not assigned,n/a,Not started
 Permutation,stable_partition,Not assigned,n/a,Not started
 Permutation,sort,Not assigned,n/a,Not started
 Permutation,stable_sort,Not assigned,n/a,Not started
 Permutation,partial_sort,Not assigned,n/a,Not started

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_is_partitioned.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
+  __algorithm/ranges_reverse.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h
   __algorithm/replace_copy.h

libcxx/include/__algorithm/ranges_reverse.h

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_REVERSE_H
+#define _LIBCPP___ALGORITHM_RANGES_REVERSE_H
+
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/iter_swap.h>
+#include <__iterator/next.h>
+#include <__iterator/permutable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __reverse {
+struct __fn {
+
+  template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent>
+    requires permutable<_Iter>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Sent __last) const {
+    if constexpr (random_access_iterator<_Iter>) {
+      if (__first == __last)
+        return __first;
+
+      auto __end = ranges::next(__first, __last);
+      auto __ret = __end;
+
+      while (__first < --__end) {
+        ranges::iter_swap(__first, __end);
+        ++__first;
+      }
+      return __ret;
+    } else {
+      auto __end = ranges::next(__first, __last);
+      auto __ret = __end;
+
+      while (__first != __end) {
+        if (__first == --__end)
+          break;
+
+        ranges::iter_swap(__first, __end);
+        ++__first;
+      }
+      return __ret;
+    }
+  }
+
+  template <bidirectional_range _Range>
+    requires permutable<iterator_t<_Range>>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __range) const {
+    return (*this)(ranges::begin(__range), ranges::end(__range));
+  }
+
+};
+} // namespace __reverse
+
+inline namespace __cpo {
+  inline constexpr auto reverse = __reverse::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_REVERSE_H

libcxx/include/algorithm

template<input_range R, class Proj = identity,
   template<input_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_unary_predicate<projected<I, Proj>> Pred>
     constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});      // since C++20
 
   template<input_range R, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});                // since C++20
 
+
+  template<bidirectional_iterator I, sentinel_for<I> S>
+    requires permutable<I>
+    constexpr I ranges::reverse(I first, S last);                                           // since C++20
+
+  template<bidirectional_range R>
+    requires permutable<iterator_t<R>>
+    constexpr borrowed_iterator_t<R> ranges::reverse(R&& r);                                // since C++20
+
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
+#include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/replace.h>
 #include <__algorithm/replace_copy.h>

libcxx/include/module.modulemap

module __algorithm {
       module ranges_is_partitioned    { private header "__algorithm/ranges_is_partitioned.h" }
       module ranges_max               { private header "__algorithm/ranges_max.h" }
       module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min               { private header "__algorithm/ranges_min.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax            { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element    { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch          { private header "__algorithm/ranges_mismatch.h" }
+      module ranges_reverse           { private header "__algorithm/ranges_reverse.h" }
       module ranges_swap_ranges       { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform         { private header "__algorithm/ranges_transform.h" }
       module remove                   { private header "__algorithm/remove.h" }
       module remove_copy              { private header "__algorithm/remove_copy.h" }
       module remove_copy_if           { private header "__algorithm/remove_copy_if.h" }
       module remove_if                { private header "__algorithm/remove_if.h" }
       module replace                  { private header "__algorithm/replace.h" }
       module replace_copy             { private header "__algorithm/replace_copy.h" }

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}}
 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
+#include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}
 #include <__algorithm/remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_if.h'}}
 #include <__algorithm/replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace.h'}}
 #include <__algorithm/replace_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace_copy.h'}}

libcxx/test/std/algorithms/alg.modifying.operations/alg.reverse/ranges.reverse.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-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<bidirectional_iterator I, sentinel_for<I> S>
+//   requires permutable<I>
+//   constexpr I ranges::reverse(I first, S last);
+// template<bidirectional_range R>
+//   requires permutable<iterator_t<R>>
+//   constexpr borrowed_iterator_t<R> ranges::reverse(R&& r);
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>>
+concept HasReverseIt = requires (Iter first, Sent last) { std::ranges::reverse(first, last); };
+
+static_assert(HasReverseIt<int*>);
+static_assert(!HasReverseIt<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!HasReverseIt<BidirectionalIteratorNotDecrementable>);
+static_assert(!HasReverseIt<PermutableNotForwardIterator>);
+static_assert(!HasReverseIt<PermutableNotSwappable>);
+
+
+template <class Range>
+concept HasReverseR = requires (Range range) { std::ranges::reverse(range); };
+
+static_assert(HasReverseR<UncheckedRange<int*>>);
+static_assert(!HasReverseR<BidirectionalRangeNotDerivedFrom>);
+static_assert(!HasReverseR<BidirectionalRangeNotDecrementable>);
+static_assert(!HasReverseR<PermutableRangeNotForwardIterator>);
+static_assert(!HasReverseR<PermutableRangeNotSwappable>);
+
+template <class Iter, class Sent, size_t N>
+constexpr void test(std::array<int, N> value, std::array<int, N> expected) {
+  {
+    auto val = value;
+    std::same_as<Iter> decltype(auto) ret = std::ranges::reverse(Iter(val.data()), Sent(Iter(val.data() + val.size())));
+    assert(val == expected);
+    assert(base(ret) == val.data() + val.size());
+  }
+  {
+    auto val = value;
+    auto range = std::ranges::subrange(Iter(val.data()), Sent(Iter(val.data() + val.size())));
+    std::same_as<Iter> decltype(auto) ret = std::ranges::reverse(range);
+    assert(val == expected);
+    assert(base(ret) == val.data() + val.size());
+  }
+}
+
+template <class Iter, class Sent = Iter>
+constexpr void test_iterators() {
+  // simple test
+  test<Iter, Sent, 4>({1, 2, 3, 4}, {4, 3, 2, 1});
+  // check that an odd number of elements works
+  test<Iter, Sent, 7>({1, 2, 3, 4, 5, 6, 7}, {7, 6, 5, 4, 3, 2, 1});
+  // check that an empty range works
+  test<Iter, Sent, 0>({}, {});
+  // check that a single element works
+  test<Iter, Sent, 1>({5}, {5});
+}
+
+struct SwapCounter {
+  int* counter;
+  constexpr SwapCounter(int* counter_) : counter(counter_) {}
+  friend constexpr void swap(SwapCounter& lhs, SwapCounter&) { ++*lhs.counter; }
+};
+
+constexpr bool test() {
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<bidirectional_iterator<int*>, sentinel_wrapper<bidirectional_iterator<int*>>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();
+  test_iterators<contiguous_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>>();
+  test_iterators<int*>();
+
+  // check that std::ranges::dangling is returned
+  {
+    [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = std::ranges::reverse(std::array {1, 2, 3, 4});
+  }
+
+  {
+    {
+      int counter = 0;
+      SwapCounter a[] = {&counter, &counter, &counter, &counter};
+      std::ranges::reverse(a);
+      assert(counter == 2);
+    }
+    {
+      int counter = 0;
+      SwapCounter a[] = {&counter, &counter, &counter, &counter};
+      std::ranges::reverse(a, a + 4);
+      assert(counter == 2);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 //static_assert(test(std::ranges::remove, a, 42));
 //static_assert(test(std::ranges::remove_copy, a, a, 42));
 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));
 //static_assert(test(std::ranges::remove_if, a, odd));
 //static_assert(test(std::ranges::replace, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy, a, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43));
 //static_assert(test(std::ranges::replace_if, a, odd, 43));
-//static_assert(test(std::ranges::reverse, a));
+static_assert(test(std::ranges::reverse, a));
 //static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 //static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
 //static_assert(test(std::ranges::search, a, a));
 //static_assert(test(std::ranges::search_n, a, 10, 42));
 //static_assert(test(std::ranges::set_difference, a, a, a));
 //static_assert(test(std::ranges::set_intersection, a, a, a));

libcxx/test/support/almost_satisfies_types.h

public:
   WeaklyIncrementableNotMovable& operator++();
   void operator++(int);
   WeaklyIncrementableNotMovable(const WeaklyIncrementableNotMovable&) = delete;
 };
 
 static_assert(!std::movable<WeaklyIncrementableNotMovable>);
 static_assert(!std::weakly_incrementable<WeaklyIncrementableNotMovable>);
 
+class BidirectionalIteratorNotDerivedFrom {
+public:
+  using difference_type = long;
+  using value_type = int;
+  using iterator_category = std::forward_iterator_tag;
+
+  BidirectionalIteratorNotDerivedFrom& operator++();
+  BidirectionalIteratorNotDerivedFrom operator++(int);
+  BidirectionalIteratorNotDerivedFrom& operator--();
+  BidirectionalIteratorNotDerivedFrom operator--(int);
+  int& operator*() const;
+
+  bool operator==(const BidirectionalIteratorNotDerivedFrom&) const = default;
+};
+
+using BidirectionalRangeNotDerivedFrom = UncheckedRange<BidirectionalIteratorNotDerivedFrom>;
+
+static_assert(std::forward_iterator<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!std::bidirectional_iterator<BidirectionalIteratorNotDerivedFrom>);
+static_assert(!std::ranges::bidirectional_range<BidirectionalRangeNotDerivedFrom>);
+
+class BidirectionalIteratorNotDecrementable {
+public:
+  using difference_type = long;
+  using value_type = int;
+  using iterator_category = std::bidirectional_iterator_tag;
+
+  BidirectionalIteratorNotDecrementable& operator++();
+  BidirectionalIteratorNotDecrementable operator++(int);
+  int& operator*() const;
+
+  bool operator==(const BidirectionalIteratorNotDecrementable&) const = default;
+};
+
+using BidirectionalRangeNotDecrementable = UncheckedRange<BidirectionalIteratorNotDecrementable>;
+
+static_assert(std::forward_iterator<BidirectionalIteratorNotDecrementable>);
+static_assert(!std::bidirectional_iterator<BidirectionalIteratorNotDecrementable>);
+static_assert(!std::ranges::bidirectional_range<BidirectionalRangeNotDecrementable>);
+
+class PermutableNotForwardIterator {
+public:
+  using difference_type = long;
+  using value_type = int;
+  using iterator_category = std::input_iterator_tag;
+
+  PermutableNotForwardIterator& operator++();
+  void operator++(int);
+  int& operator*() const;
+};
+
+using PermutableRangeNotForwardIterator = UncheckedRange<PermutableNotForwardIterator>;
+
+static_assert(std::input_iterator<PermutableNotForwardIterator>);
+static_assert(!std::forward_iterator<PermutableNotForwardIterator>);
+static_assert(!std::permutable<PermutableNotForwardIterator>);
+
+class PermutableNotSwappable {
+public:
+  class NotSwappable {
+    NotSwappable(NotSwappable&&) = delete;
+  };
+
+  using difference_type = long;
+  using value_type = NotSwappable;
+  using iterator_category = std::contiguous_iterator_tag;
+
+  PermutableNotSwappable& operator++();
+  PermutableNotSwappable operator++(int);
+  NotSwappable& operator*() const;
+
+  bool operator==(const PermutableNotSwappable&) const = default;
+};
+
+using PermutableRangeNotSwappable = UncheckedRange<PermutableNotSwappable>;
+
+static_assert(std::input_iterator<PermutableNotSwappable>);
+static_assert(std::forward_iterator<PermutableNotSwappable>);
+static_assert(!std::permutable<PermutableNotSwappable>);
+static_assert(!std::indirectly_swappable<PermutableNotSwappable>);
+
 #endif // ALMOST_SATISFIES_TYPES_H