[libc++][spaceship] Implement `operator<=>` for `list`

[avogelsgesang]

Summary

Implements part of P1614R2 "The Mothership has Landed"

[avogelsgesang]

update review link

[mumbleskates]

One thing I have thought about in our march towards finishing the lexically ordered containers is that we should be able to write a test utils header with one or more templated test functions that will work for most or all of these containers. We can possibly even add (in another header?) some helpful types like weakly ordered ints, types that compare with user orderings, etc. so we don't have to keep writing them over and over. This feels fairly sane to me but I don't know what the general vibe is on how DRY is too DRY for our test suite, and maybe it's better to just copy-paste those parts of the code each time.

libcxx/test/std/containers/sequences/list/compare.pass.cpp

47

I recommend simply adding another file, such as compare.three_way.pass.cpp, that marks standard versions before 20 as unsupported, then simply does the test. Adding the parts of the test you want to conditionally execute with dozens of conditional directives is honestly too much noise with no real benefit.

Don't forget the SFINAE tests! They should be pretty easy to do here as well. We should be able to test ordering behavior and SFINAE for all of the following:

1. strongly ordered types
2. partially ordered types
3. weakly ordered types
4. synth-ordered types (weak_ordering)
5. custom user-ordering types (also causes synthesized weak_ordering)
6. unordered types (SFINAE should cause the operator to not participate)

All of these should be trivially reusable or easily copyable to the other container types.

[jloser]

In D132312#3737824, @mumbleskates wrote:

One thing I have thought about in our march towards finishing the lexically ordered containers is that we should be able to write a test utils header with one or more templated test functions that will work for most or all of these containers. We can possibly even add (in another header?) some helpful types like weakly ordered ints, types that compare with user orderings, etc. so we don't have to keep writing them over and over. This feels fairly sane to me but I don't know what the general vibe is on how DRY is too DRY for our test suite, and maybe it's better to just copy-paste those parts of the code each time.

I'm very +1 for that direction of having a reusable header with common types and functions for this.

[huixie90]

I think I also agree on the comments with regard to the tests

libcxx/include/list

2341

_LIBCPP_HIDE_FROM_ABI

2341

perhaps I missed something but have you included the header that defines __synth_three_way_result

[avogelsgesang]

libcxx/include/list

2341

the complete <compare> header is a standard-mandated include. See line 226

[Mordante]

libcxx/test/std/containers/sequences/list/compare.pass.cpp

47

I like the general idea! How about instead add a generic header file and make it possible to use the functions in there for the tests? Like we do in the test_comparisons.h header. That way the tests are at the expected location.

WDYT?

[avogelsgesang]

Introduce reusable test function

libcxx/test/std/containers/sequences/list/compare.pass.cpp

47

Good idea. I introduced test_container_comparisons.h to contain those test helpers. In the future, we should also add a similar utility to test containers like std::map, std::set.

The test functions are already written with std::vector in mind, i.e. they are constexpr and return true, so they can be used to test the constexpr-ness of std::vector.

custom user-ordering types (also causes synthesized weak_ordering)

How do I write such a user-ordering?

[avogelsgesang]

add inline

[Mordante]

libcxx/test/std/containers/sequences/list/compare.three_way.pass.cpp

21 ↗

(On Diff #476785)

libcxx/test/support/test_container_comparisons.h

10 ↗

(On Diff #476785)

Please add include guards.

14 ↗

(On Diff #476785)

61 ↗

(On Diff #476785)

78 ↗

(On Diff #476785)

I think these tests can be extended a bit, it feels like they now use a small number of types. I also miss tests for <= to be true/false for certain values.

[avogelsgesang]

Address review comments

libcxx/test/support/test_container_comparisons.h

78 ↗

(On Diff #476785)

I am not sure I understand what you are asking for here

use a small number of types

which additional types would you like to see? Afaict, the test case covers enough types such that we have all comparison categories covered?

I also miss tests for <= to be true/false for certain values.

testOrder calls testComparisonsComplete which also covers <=. Or am I misunderstanding your request for additional test coverage

[Mordante]

LGTM after the CI is green.

libcxx/test/support/test_container_comparisons.h

78 ↗

(On Diff #476785)

I missed the types where <=> is synthesized, but it's there too.

[ldionne]

LGTM w/ green CI. Thanks!

libcxx/include/list

2345

This should fix your CI issue with clang-tidy.

[avogelsgesang]

Fix CI

[avogelsgesang]

libcxx/include/list

2345

yes, I think so, too. Happy we have the ADL test cases nowadays!

libcxx/docs/Status/SpaceshipProjects.csv

 | `[charconv.syn] <https://wg21.link/charconv.syn>`_,| `from_chars_result <https://reviews.llvm.org/D112366>`_,None,Mark de Wever,|Complete|
 | `[stacktrace.entry.cmp] <https://wg21.link/stacktrace.entry.cmp>`_,| stacktrace_entry,None,Unassigned,|Not Started|
 | `[stacktrace.basic.cmp] <https://wg21.link/stacktrace.basic.cmp>`_,| basic_stacktrace,[alg.three.way],Unassigned,|Not Started|
 | `[string.cmp] <https://wg21.link/string.cmp>`_,| `basic_string <https://reviews.llvm.org/D131421>`_,None,Mark de Wever,|Complete|
 | `[string.view.comparison] <https://wg21.link/string.view.comparison>`_,| `basic_string_view <https://reviews.llvm.org/D130295>`_,None,Mark de Wever,|Complete|
 | `[array.syn] <https://wg21.link/array.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| array,[expos.only.func],Unassigned,|Not Started|
 | `[deque.syn] <https://wg21.link/deque.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| deque,[expos.only.func],Unassigned,|Not Started|
 | `[forward.list.syn] <https://wg21.link/forward.list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| forward_list,[expos.only.func],Unassigned,|Not Started|
-| `[list.syn] <https://wg21.link/list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| list,[expos.only.func],Unassigned,|Not Started|
+| `[list.syn] <https://wg21.link/list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `list <https://reviews.llvm.org/D132312>`_,[expos.only.func],Adrian Vogelsgesang,|Complete|
 | `[vector.syn] <https://wg21.link/vector.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| vector,[expos.only.func],Unassigned,|Not Started|
 | `[associative.map.syn] <https://wg21.link/associative.map.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| map
 | multimap",[expos.only.func],Unassigned,|Not Started|
 | `[associative.set.syn] <https://wg21.link/associative.set.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| multiset
 | set",[expos.only.func],Unassigned,|Not Started|
 | `[queue.ops] <https://wg21.link/queue.ops>`_,| queue,None,Unassigned,|Not Started|
 | `[stack.ops] <https://wg21.link/stack.ops>`_,| stack,None,Unassigned,|Not Started|
 | `[reverse.iter.cmp] <https://wg21.link/reverse.iter.cmp>`_,| `reverse_iterator <https://reviews.llvm.org/D113695>`_,None,Mikhail Maltsev,|Complete|

libcxx/include/list

 
 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
     list(InputIterator, InputIterator, Allocator = Allocator())
     -> list<typename iterator_traits<InputIterator>::value_type, Allocator>;  // C++17
 
 template <class T, class Alloc>
     bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
 template <class T, class Alloc>
-    bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
+    bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 template <class T, class Alloc>
-    bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
+    bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 template <class T, class Alloc>
-    bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
+    bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 template <class T, class Alloc>
-    bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
+    bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
 template <class T, class Alloc>
-    bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
+    bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);     // removed in C++20
+template<class T, class Allocator>
+  synth-three-way-result<T> operator<=>(const list<T, Allocator>& x,
+                                        const list<T, Allocator>& y);    // since C++20
 
 template <class T, class Alloc>
     void swap(list<T,Alloc>& x, list<T,Alloc>& y)
          noexcept(noexcept(x.swap(y)));
 
 template <class T, class Allocator, class U>
     typename list<T, Allocator>::size_type
-    erase(list<T, Allocator>& c, const U& value);       // C++20
+    erase(list<T, Allocator>& c, const U& value);       // since C++20
 template <class T, class Allocator, class Predicate>
     typename list<T, Allocator>::size_type
-    erase_if(list<T, Allocator>& c, Predicate pred);    // C++20
+    erase_if(list<T, Allocator>& c, Predicate pred);    // since C++20
 
 }  // std
 
 */
 
 #include <__algorithm/comp.h>
 #include <__algorithm/equal.h>
 #include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/lexicographical_compare_three_way.h>
 #include <__algorithm/min.h>
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__config>
 #include <__debug>
 #include <__format/enable_insertable.h>
 #include <__iterator/distance.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/move_iterator.h>

 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
 {
     return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
 }
 
+#if _LIBCPP_STD_VER <= 17
+
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
 {
     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 }
 

 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
 {
     return !(__y < __x);
 }
 
+#else // _LIBCPP_STD_VER <= 17
+
+template<class _Tp, class _Allocator>
+__synth_three_way_result<_Tp>
+operator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y)
+{
+    return lexicographical_compare_three_way(
+        __x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
+}
+
+#endif // _LIBCPP_STD_VER <= 17
+
 template <class _Tp, class _Alloc>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {
     __x.swap(__y);
 }

libcxx/test/std/containers/sequences/list/compare.pass.cpp

 // template< class T, class Alloc >
 // bool operator>( const std::list<T,Alloc>& lhs,
 //                 const std::list<T,Alloc>& rhs );
 
 // template< class T, class Alloc >
 // bool operator>=( const std::list<T,Alloc>& lhs,
 //                  const std::list<T,Alloc>& rhs );
 
+// template <class T, class Allocator> constexpr
+//   synth-three-way-result<T>
+//     operator<=>(const vector<T, Allocator>& x, const vector<T, Allocator>& y);
+
 #include <list>
 #include <cassert>
 
 #include "test_comparisons.h"
 
-int main(int, char**) {
-    {
-        const std::list<int> l1, l2;
-        assert(testComparisons(l1, l2, true, false));
-    }
-    {
-        const std::list<int> l1(1, 1), l2(1, 1);
-        assert(testComparisons(l1, l2, true, false));
-    }
-    {
-        int items[3] = {1, 2, 3};
-        const std::list<int> l1(items, items + 3);
-        const std::list<int> l2(items, items + 3);
-        assert(testComparisons(l1, l2, true, false));
-    }
-    {
-        const std::list<int> l1(1, 1), l2;
-        assert(testComparisons(l1, l2, false, false));
-    }
-    {
-        const std::list<int> l1(1, 1), l2(1, 2);
-        assert(testComparisons(l1, l2, false, true));
-    }
-    {
-        int items1[2] = {1, 2};
-        int items2[2] = {1, 3};
-        const std::list<int> l1(items1, items1 + 2);
-        const std::list<int> l2(items2, items2 + 2);
-        assert(testComparisons(l1, l2, false, true));
-    }
-    {
-        int items1[2] = {2, 2};
-        int items2[2] = {1, 3};
-        const std::list<int> l1(items1, items1 + 2);
-        const std::list<int> l2(items2, items2 + 2);
-        assert(testComparisons(l1, l2, false, false));
-    }
-    {
-        const std::list<LessAndEqComp> l1, l2;
-        assert(testComparisons(l1, l2, true, false));
-    }
-    {
-        const std::list<LessAndEqComp> l1(1, LessAndEqComp(1));
-        const std::list<LessAndEqComp> l2(1, LessAndEqComp(1));
-        assert(testComparisons(l1, l2, true, false));
-    }
-    {
-        LessAndEqComp items[3] = {LessAndEqComp(1), LessAndEqComp(2), LessAndEqComp(3)};
-        const std::list<LessAndEqComp> l1(items, items + 3);
-        const std::list<LessAndEqComp> l2(items, items + 3);
-        assert(testComparisons(l1, l2, true, false));
-    }
-    {
-        const std::list<LessAndEqComp> l1(1, LessAndEqComp(1));
-        const std::list<LessAndEqComp> l2;
-        assert(testComparisons(l1, l2, false, false));
-    }
-    {
-        const std::list<LessAndEqComp> l1(1, LessAndEqComp(1));
-        const std::list<LessAndEqComp> l2(1, LessAndEqComp(2));
-        assert(testComparisons(l1, l2, false, true));
-    }
-    {
-        LessAndEqComp items1[2] = {LessAndEqComp(1), LessAndEqComp(2)};
-        LessAndEqComp items2[2] = {LessAndEqComp(1), LessAndEqComp(3)};
-        const std::list<LessAndEqComp> l1(items1, items1 + 2);
-        const std::list<LessAndEqComp> l2(items2, items2 + 2);
-        assert(testComparisons(l1, l2, false, true));
-    }
-    {
-        LessAndEqComp items1[2] = {LessAndEqComp(2), LessAndEqComp(2)};
-        LessAndEqComp items2[2] = {LessAndEqComp(1), LessAndEqComp(3)};
-        const std::list<LessAndEqComp> l1(items1, items1 + 2);
-        const std::list<LessAndEqComp> l2(items2, items2 + 2);
-        assert(testComparisons(l1, l2, false, false));
-    }
-    return 0;
+template <typename ElemT, typename Order>
+void test_with_type() {
+  AssertComparisonsReturnBool<std::vector<ElemT> >();
+#if TEST_STD_VER >= 20
+  AssertOrderReturn<Order, std::vector<ElemT>>();
+#endif
+    const std::list<ElemT> l1, l2;
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::equal));
+#endif
+    const std::list<ElemT> l1(1, 1), l2(1, 1);
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::equal));
+#endif
+    ElemT items[3] = {1, 2, 3};
+    const std::list<ElemT> l1(items, items + 3);
+    const std::list<ElemT> l2(items, items + 3);
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::equal));
+#endif
+    const std::list<ElemT> l1(1, 1), l2;
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::greater));
+#endif
+    const std::list<ElemT> l1(1, 1), l2(1, 2);
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::less));
+#endif
+    ElemT items1[2] = {1, 2};
+    ElemT items2[2] = {1, 3};
+    const std::list<ElemT> l1(items1, items1 + 2);
+    const std::list<ElemT> l2(items2, items2 + 2);
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::less));
+#endif
+    ElemT items1[2] = {2, 2};
+    ElemT items2[2] = {1, 3};
+    const std::list<ElemT> l1(items1, items1 + 2);
+    const std::list<ElemT> l2(items2, items2 + 2);
+#if TEST_STD_VER >= 20
+    assert(testOrder(l1, l2, Order::greater));
+#endif
+
+int main(int, char**) {
+#if TEST_STD_VER >= 20
+  using strong_ordering_since_cxx20 = std::strong_ordering;
+  using weak_ordering_since_cxx20   = std::weak_ordering;
+#else
+  typedef void strong_ordering_since_cxx20;
+  typedef void weak_ordering_since_cxx20;
+#endif
+  test_with_type<int, strong_ordering_since_cxx20>();
+  test_with_type<LessAndEqComp, weak_ordering_since_cxx20>();
+#if TEST_STD_VER >= 20
+  test_with_type<WeakComp, std::weak_ordering>();
+  test_with_type<PartialComp, std::partial_ordering>();
+#endif
+
 }