[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 ↗

(On Diff #454251)

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 ↗

(On Diff #454251)

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 ↗

(On Diff #454251)

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

22

libcxx/test/support/test_container_comparisons.h

11

Please add include guards.

15

62

79

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

79

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

79

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 <https://reviews.llvm.org/D132265>`_,[expos.only.func],Adrian Vogelsgesang,|In Progress|
 | `[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 <https://reviews.llvm.org/D132268>`_,[expos.only.func],Adrian Vogelsgesang,|In Progress|
 | `[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>
+inline _LIBCPP_HIDE_FROM_ABI
+__synth_three_way_result<_Tp>
+operator<=>(const list<_Tp, _Allocator>& __x, const list<_Tp, _Allocator>& __y)
+{
+    return std::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.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
+
+// <list>
+
+// template <class T, class Allocator> constexpr
+//   synth-three-way-result<T>
+//     operator<=>(const list<T, Allocator>& x, const list<T, Allocator>& y);
+
+#include <list>
+#include <cassert>
+
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+  assert(test_ordered_container_spaceship<std::list>());
+  // `std::list` is not constexpr, so no `static_assert` test here.
+  return 0;
+}

libcxx/test/support/test_container_comparisons.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
+//
+//===----------------------------------------------------------------------===//
+//  Utility functions to test comparisons on containers.
+
+#ifndef TEST_CONTAINER_COMPARISONS
+#define TEST_CONTAINER_COMPARISONS
+
+#include "test_comparisons.h"
+
+// Implementation detail of `test_ordered_container_spaceship`
+template <template <typename...> typename Container, typename Elem, typename Order>
+constexpr void test_ordered_container_spaceship_with_type() {
+  // Empty containers
+  {
+    Container<Elem> l1;
+    Container<Elem> l2;
+    assert(testOrder(l1, l2, Order::equivalent));
+  }
+  // Identical contents
+  {
+    Container<Elem> l1{1, 1};
+    Container<Elem> l2{1, 1};
+    assert(testOrder(l1, l2, Order::equivalent));
+  }
+  // Less, due to contained values
+  {
+    Container<Elem> l1{1, 1};
+    Container<Elem> l2{1, 2};
+    assert(testOrder(l1, l2, Order::less));
+  }
+  // Greater, due to contained values
+  {
+    Container<Elem> l1{1, 3};
+    Container<Elem> l2{1, 2};
+    assert(testOrder(l1, l2, Order::greater));
+  }
+  // Shorter list
+  {
+    Container<Elem> l1{1};
+    Container<Elem> l2{1, 2};
+    assert(testOrder(l1, l2, Order::less));
+  }
+  // Longer list
+  {
+    Container<Elem> l1{1, 2};
+    Container<Elem> l2{1};
+    assert(testOrder(l1, l2, Order::greater));
+  }
+  // Unordered
+  if constexpr (std::is_same_v<Elem, PartialOrder>) {
+    Container<Elem> l1{1, std::numeric_limits<int>::min()};
+    Container<Elem> l2{1, 2};
+    assert(testOrder(l1, l2, Order::unordered));
+  }
+}
+
+// Tests the `operator<=>` on ordered containers
+template <template <typename...> typename Container>
+constexpr bool test_ordered_container_spaceship() {
+  // The container should fulfil `std::three_way_comparable`
+  static_assert(std::three_way_comparable<Container<int>>);
+
+  // Test different comparison categories
+  test_ordered_container_spaceship_with_type<Container, int, std::strong_ordering>();
+  test_ordered_container_spaceship_with_type<Container, StrongOrder, std::strong_ordering>();
+  test_ordered_container_spaceship_with_type<Container, WeakOrder, std::weak_ordering>();
+  test_ordered_container_spaceship_with_type<Container, PartialOrder, std::partial_ordering>();
+
+  // `LessAndEqComp` does not have `operator<=>`. ordering is sythesized based on `operator<`
+  test_ordered_container_spaceship_with_type<Container, LessAndEqComp, std::weak_ordering>();
+
+  // Thanks to SFINAE, the following is not a compiler error but returns `false`
+  struct NonComparable {};
+  static_assert(!std::three_way_comparable<Container<NonComparable>>);
+
+  return true;
+}
+
+#endif