[libcxx] Implement three-way comparison for std::reverse_iterator

[miyuki]

Summary

This patch implements operator<=> for std::reverse_iterator and
also adds a test that checks that three-way comparison of different
instantiations of std::reverse_iterator works as expected (related to
D113417).

[jloser]

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.pass.cpp

59

Nit: we can drop the second argument here to static_assert if you'd like.

[• Quuxplusone]

Looks acceptable as-is, but if we can convince you to scope-creep it to adding C++20 constraints on the comparison operators, that'd be cool. :)

libcxx/include/__iterator/reverse_iterator.h

194

C++20 also adds constraints to all six of these operators, e.g.:

Constraints: x.base() == y.base() is well-formed and convertible to bool.

Scope-creep: shall we add these constraints right now? E.g.

template <class _Iter1, class _Iter2>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
bool
operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
    requires is_convertible_v<decltype(x.base() >= y.base()), bool>
#endif
{
    return __x.base() >= __y.base();
}

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.pass.cpp

32

The only reason to template this on ItL and ItR is if you're going to test different iterator types. Specifically, let's test one where its comparison category is partial_ordering, to make sure that that comes through OK. (I wonder if iota_view<float>::iterator exists and if so what its comparison category is.)

[miyuki]

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.pass.cpp

32

The only reason to template this on ItL and ItR is if you're going to test different iterator types.

Yes, in this case, char * and const char *.

Specifically, let's test one where its comparison category is partial_ordering

OK, I will add such a test.

[miyuki]

Added std::partial_ordering test

[• Quuxplusone]

LGTM mod comments. Guess I failed to nerdsnipe you into adding the constraints to the other six relational operators, huh?

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.pass.cpp

46

https://quuxplusone.github.io/blog/2021/07/14/an-iterator-is-not-a-const-iterator/
All you're trying to do here is create a conversion

ConstIter(Iter it): m_value(it.m_value) {}

right? Just write that one line. :)

Note that if these were real iterators, in C++20, inheritance would totally not work, because you'd have signatures like ConstIter& Iter::operator++() which wouldn't satisfy the iterator concepts. Inheritance and value-semantic types really do not mix.

56–58

Style nit: Both operator== and operator<=> should be hidden friends of ConstIter.
operator== can be defaulted.

UB nit: Your operator== is not consistent with your operator<=>. I suggest just declaring double m_value, and defaulting both == and <=>. Then you can use ConstIter(std::numeric_limits<double>::quiet_NaN()) as your "unordered" iterator value. (And I recommend pulling out a variable double nan = std::numeric_limits<double>::quiet_NaN(); in main for readability.)

[miyuki]

Updated the test.

[miyuki]

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.pass.cpp

46

https://quuxplusone.github.io/blog/2021/07/14/an-iterator-is-not-a-const-iterator/
std::vector<int>::iterator b;
std::vector<int>::const_iterator& rb = b; // 1

Thanks, now I finally got it.

[miyuki]

Guess I failed to nerdsnipe you into adding the constraints to the other six relational operators, huh?

I'll submit a separate patch

[miyuki]

Added missing constexpr

[• Quuxplusone]

LGTM! Please wait for second libc++ approval before landing.

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.pass.cpp

35

Add a blank line between lines 34 and 35.

88

This is a known bug in GCC constexpr evaluation. You can just change this from Iter(nan), Iter(6) to Iter(nan), Iter(nan) and that should make GCC happy.

[ldionne]

libcxx/include/__iterator/reverse_iterator.h

198

[miyuki]

Addressed comments.

[miyuki]

The CI failure looks unrelated.

[ldionne]

In D113695#3154227, @miyuki wrote:

The CI failure looks unrelated.

Nope, I disagree. It's just really unhelpful, but I think you are missing some includes.

[ldionne]

In D113695#3154229, @ldionne wrote:

In D113695#3154227, @miyuki wrote:

The CI failure looks unrelated.

Nope, I disagree. It's just really unhelpful, but I think you are missing some includes.

Note that D114010 will make that error useful again, but it's blocked on a couple things.

[miyuki]

Added missing #include-s

[ldionne]

🚢 it!

libcxx/include/__iterator/reverse_iterator.h

 }
 
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 bool
 operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 {
     return __x.base() >= __y.base();
 }
 
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_SPACESHIP_OPERATOR) && !defined(_LIBCPP_HAS_NO_CONCEPTS)
+template <class _Iter1, three_way_comparable_with<_Iter1> _Iter2>
+inline _LIBCPP_INLINE_VISIBILITY constexpr
+compare_three_way_result_t<_Iter1, _Iter2>
+operator<=>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
+{
+    return __y.base() <=> __x.base();
+}
+#endif
+
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Iter1, class _Iter2>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 auto
 operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 -> decltype(__y.base() - __x.base())
 {
     return __y.base() - __x.base();

libcxx/test/std/iterators/predef.iterators/reverse.iterators/reverse.iter.cmp/three-way.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
+
+// <iterator>
+
+// reverse_iterator
+
+// template<class Iterator1, three_way_comparable_with<Iterator1> Iterator2>
+//   constexpr compare_three_way_result_t<Iterator1, Iterator2>
+//    operator<=>(const reverse_iterator<Iterator1>& x,
+//                const reverse_iterator<Iterator2>& y);
+
+#include <iterator>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class ItL, class ItR, class Ord>
+constexpr void test(ItL l, ItR r, Ord x) {
+    const std::reverse_iterator<ItL> l1(l);
+    const std::reverse_iterator<ItR> r1(r);
+    ASSERT_SAME_TYPE(decltype(l1 <=> r1), Ord);
+    assert((l1 <=> r1) == x);
+}
+
+struct ConstIter {
+    using iterator_category = std::bidirectional_iterator_tag;
+    using pointer = const char*;
+    using reference = const char&;
+    using value_type = const char;
+    using difference_type = int;
+
+    constexpr ConstIter(unsigned value): m_value(value) {}
+    unsigned m_value;
+};
+
+struct Iter : ConstIter {
+    using iterator_category = std::bidirectional_iterator_tag;
+    using pointer = char*;
+    using reference = char&;
+    using value_type = char;
+    using difference_type = int;
+
+    constexpr Iter(unsigned value): ConstIter(value) {}
+};
+
+constexpr bool operator==(const ConstIter& l, const ConstIter& r) {
+    return l.m_value == r.m_value;
+}
+
+constexpr std::partial_ordering operator<=>(const ConstIter& l,
+                                            const ConstIter& r) {
+    // Order: {0, 1} < {2, 3} < {4, 5}, ...
+    // 0 and 1, 2 and 3, etc. are unordered
+    if ((l.m_value / 2) == (r.m_value / 2) && l.m_value != r.m_value)
+        return std::partial_ordering::unordered;
+    return l.m_value <=> r.m_value;
+}
+
+constexpr bool tests() {
+    char s[] = "1234567890";
+    test(three_way_contiguous_iterator<const char*>(s),
+         three_way_contiguous_iterator<const char*>(s),
+         std::strong_ordering::equal);
+    test(three_way_contiguous_iterator<const char*>(s),
+         three_way_contiguous_iterator<const char*>(s+1),
+         std::strong_ordering::greater);
+    test(three_way_contiguous_iterator<const char*>(s+1),
+         three_way_contiguous_iterator<const char*>(s),
+         std::strong_ordering::less);
+
+    test(s, s, std::strong_ordering::equal);
+    test(s, s+1, std::strong_ordering::greater);
+    test(s+1, s, std::strong_ordering::less);
+
+    const char* cs = s;
+    test(cs, s, std::strong_ordering::equal);
+    test(cs, s+1, std::strong_ordering::greater);
+    test(cs+1, s, std::strong_ordering::less);
+
+    test(Iter(0), ConstIter(1), std::partial_ordering::unordered);
+    test(Iter(7), Iter(6), std::partial_ordering::unordered);
+    test(ConstIter(0), Iter(4), std::partial_ordering::greater);
+    test(ConstIter(4), Iter(1), std::partial_ordering::less);
+    test(ConstIter(7), Iter(7), std::partial_ordering::equivalent);
+
+    return true;
+}
+
+int main(int, char**) {
+    tests();
+    static_assert(tests());
+    return 0;
+}