[libc++][spaceship] Implement `operator<=>` for `multiset` and `set`

[H-G-Hristov]

Summary

Implements parts of P1614R2

Implemented operator<=> for multiset and set

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

Run CI

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

• Fixed CI

[H-G-Hristov]

• Rebased

[H-G-Hristov]

I assume this passed the CI checks, so I'd like to put it for review/discussion as is.

NOTE: Unlike any other container (including std::multisite) "unorderable" values are not added to std::set. I couldn't find an explanation for that, so I hope for a feedback. I think libstdc++'s std::set behaves in the same way.

[Mordante]

Thanks for working on this. Some comments.

libcxx/include/set

1044

libcxx/test/std/containers/associative/multiset/multiset.nonmember/compare.three_way.pass.cpp

25

Does this also test containers where Compare != std::less ?

libcxx/test/support/test_container_comparisons.h

233

Does this work with a set?

[H-G-Hristov]

Rebased

[H-G-Hristov]

@Mordante Thank you for the comments. Sorry about answering your question with questions though.

libcxx/include/set

1044

@Mordante Could you please elaborate why I need to remove inline? I am asking because operator<=> for map, list, forward_list, deque are also inline as well as the remaining operators?
If I need to remove inline here, do I need to also update the other containers for consistency?

libcxx/test/std/containers/associative/multiset/multiset.nonmember/compare.three_way.pass.cpp

25

No. I didn't consider the other cases. What other cases would you like me to add?
For consistency, I will also need to update the tests for map in that case.

libcxx/test/support/test_container_comparisons.h

233

To reduce code duplication I selected the values to work for set and multiset. I did the same for map and multimap before.
Or am I missing something?

[Mordante]

libcxx/include/set

1044

You can keep it if you want, but templates are implicitly inline. Sometimes we forget to point it out in reviews.

libcxx/test/std/containers/associative/multiset/multiset.nonmember/compare.three_way.pass.cpp

25

For the generic comparison it would be good to make sure the Compare does not matter. We probably should also test that maps with different Compare or Alloc can't be compared.

[H-G-Hristov]

• Addressed comments

[H-G-Hristov]

Addressed comments

[H-G-Hristov]

@Mordante Thank you for the review.

libcxx/test/std/containers/associative/multiset/multiset.nonmember/compare.three_way.pass.cpp

25

I think I need a start To-Do list. Thank you for suggesting!

[Mordante]

LGTM modulo one nit.

libcxx/test/support/test_comparisons.h

258–259 ↗

(On Diff #521984)

Unlike constexpr functions constexpr variable are not inline.

265 ↗

(On Diff #521984)

I actually feel std::numeric_limits<int>::min() is more readable. Especially since the name kind of indicates it's not a plain std::numeric_limits<int>::min(). So I really like this part reverted and use the numeric_limits directly.

[H-G-Hristov]

• Addressed comments

[H-G-Hristov]

@Mordante Thank you for the review. I reverted the change as you recommended.

[H-G-Hristov]

libcxx/test/support/test_comparisons.h

265 ↗

(On Diff #521984)

Removed both variables from above.

[H-G-Hristov]

• Addressed comments

[H-G-Hristov]

Updated // expected-error tests in *.verify.cpp according the review comments in D151205

[H-G-Hristov]

@Mordante I made a slight adjustments to the tests after your approval, if you don't mind I'll wait for a few days and I'll land it.

[Mordante]

libcxx/test/std/containers/associative/set/set.nonmember/compare.three_way.verify.cpp

44–45 ↗

(On Diff #525198)

Mainly for your information, for short lines you can use this too.
Since our CI has some issues at the moment feel free to land it as is.

libcxx/include/set

 template <class Key, class Compare, class Allocator>
 bool
 operator==(const set<Key, Compare, Allocator>& x,
            const set<Key, Compare, Allocator>& y);
 
 template <class Key, class Compare, class Allocator>
 bool
 operator< (const set<Key, Compare, Allocator>& x,
-           const set<Key, Compare, Allocator>& y);
+           const set<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator!=(const set<Key, Compare, Allocator>& x,
-           const set<Key, Compare, Allocator>& y);
+           const set<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator> (const set<Key, Compare, Allocator>& x,
-           const set<Key, Compare, Allocator>& y);
+           const set<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator>=(const set<Key, Compare, Allocator>& x,
-           const set<Key, Compare, Allocator>& y);
+           const set<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator<=(const set<Key, Compare, Allocator>& x,
-           const set<Key, Compare, Allocator>& y);
+           const set<Key, Compare, Allocator>& y);                                // removed in C++20
+
+template<class Key, class Compare, class Allocator>
+  synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
+                                          const set<Key, Compare, Allocator>& y); // since C++20
 
 // specialized algorithms:
 template <class Key, class Compare, class Allocator>
 void
 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 template <class Key, class Compare, class Allocator, class Predicate>

 template <class Key, class Compare, class Allocator>
 bool
 operator==(const multiset<Key, Compare, Allocator>& x,
            const multiset<Key, Compare, Allocator>& y);
 
 template <class Key, class Compare, class Allocator>
 bool
 operator< (const multiset<Key, Compare, Allocator>& x,
-           const multiset<Key, Compare, Allocator>& y);
+           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator!=(const multiset<Key, Compare, Allocator>& x,
-           const multiset<Key, Compare, Allocator>& y);
+           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator> (const multiset<Key, Compare, Allocator>& x,
-           const multiset<Key, Compare, Allocator>& y);
+           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator>=(const multiset<Key, Compare, Allocator>& x,
-           const multiset<Key, Compare, Allocator>& y);
+           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
 
 template <class Key, class Compare, class Allocator>
 bool
 operator<=(const multiset<Key, Compare, Allocator>& x,
-           const multiset<Key, Compare, Allocator>& y);
+           const multiset<Key, Compare, Allocator>& y);                                // removed in C++20
+
+template<class Key, class Compare, class Allocator>
+  synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
+                                          const multiset<Key, Compare, Allocator>& y); // since C++20
 
 // specialized algorithms:
 template <class Key, class Compare, class Allocator>
 void
 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 template <class Key, class Compare, class Allocator, class Predicate>
 typename multiset<Key, Compare, Allocator>::size_type
 erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred);  // C++20
 
 }  // std
 
 */
 
 #include <__algorithm/equal.h>
 #include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/lexicographical_compare_three_way.h>
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__config>
 #include <__functional/is_transparent.h>
 #include <__functional/operations.h>
 #include <__iterator/erase_if_container.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/reverse_iterator.h>
 #include <__memory/allocator.h>

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

 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator<=(const set<_Key, _Compare, _Allocator>& __x,
            const set<_Key, _Compare, _Allocator>& __y)
 {
     return !(__y < __x);
 }
 
+#else // _LIBCPP_STD_VER <= 17
+
+template <class _Key, class _Allocator>
+inline _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
+operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
+    return std::lexicographical_compare_three_way(
+        __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>);
+}
+
+#endif // _LIBCPP_STD_VER <= 17
+
 // specialized algorithms:
 template <class _Key, class _Compare, class _Allocator>
 inline _LIBCPP_INLINE_VISIBILITY
 void
 swap(set<_Key, _Compare, _Allocator>& __x,
      set<_Key, _Compare, _Allocator>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {

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

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

libcxx/test/std/containers/associative/multiset/multiset.nonmember/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
+
+// <set>
+
+// class multiset
+
+// template<class Key, class Compare, class Allocator>
+//   synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
+//                                           const multiset<Key, Compare, Allocator>& y);
+
+#include <cassert>
+#include <set>
+
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+  assert(test_ordered_set_container_spaceship<std::multiset>());
+  // `std::multiset` is not constexpr, so no `static_assert` test here.
+  return 0;
+}

libcxx/test/std/containers/associative/set/set.nonmember/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
+
+// <set>
+
+// class set
+
+// template<class Key, class Compare, class Allocator>
+//   synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
+//                                           const set<Key, Compare, Allocator>& y);
+
+#include <cassert>
+#include <set>
+
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+  assert((test_ordered_set_container_spaceship<std::set>()));
+  // `std::set` 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 <set>
+
 #include "test_comparisons.h"
 
 // Implementation detail of `test_sequence_container_spaceship`
 template <template <typename...> typename Container, typename Elem, typename Order>
 constexpr void test_sequence_container_spaceship_with_type() {
   // Empty containers
   {
     Container<Elem> l1;
if constexpr (std::is_same_v<Val, PartialOrder>) {
     Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 3}};
     assert(testOrder(l1, l2, Order::unordered));
     Container<Key, Val> l3{{1, 1}, {2, std::numeric_limits<int>::min()}, {2, 3}};
     Container<Key, Val> l4{{2, 3}, {2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::unordered));
   }
 }
 
-// Tests the `operator<=>` on ordered containers
+// Tests the `operator<=>` on ordered map containers
 template <template <typename...> typename Container>
 constexpr bool test_ordered_map_container_spaceship() {
   // The container should fulfill `std::three_way_comparable`
   static_assert(std::three_way_comparable<Container<int, int>>);
 
   // Test different comparison categories
   test_ordered_map_container_spaceship_with_type<Container, int, int, std::strong_ordering>();
   test_ordered_map_container_spaceship_with_type<Container, int, StrongOrder, std::strong_ordering>();
   test_ordered_map_container_spaceship_with_type<Container, int, WeakOrder, std::weak_ordering>();
   test_ordered_map_container_spaceship_with_type<Container, int, PartialOrder, std::partial_ordering>();
 
   // `LessAndEqComp` does not have `operator<=>`. Ordering is synthesized based on `operator<`
   test_ordered_map_container_spaceship_with_type<Container, int, 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<int, NonComparable>>);
 
   return true;
 }
 
+// Implementation detail of `test_ordered_set_container_spaceship`
+template <template <typename...> typename Container, typename Elem, typename Order>
+constexpr void test_ordered_set_spaceship_with_type() {
+  // Empty containers
+  {
+    Container<Elem> l1;
+    Container<Elem> l2;
+    assert(testOrder(l1, l2, Order::equivalent));
+  }
+  // Identical contents
+  {
+    Container<Elem> l1{1, 1, 2};
+    Container<Elem> l2{1, 1, 2};
+    assert(testOrder(l1, l2, Order::equivalent));
+  }
+  // Less, due to contained values
+  {
+    Container<Elem> l1{1, 1, 2, 3};
+    Container<Elem> l2{1, 2, 2, 4};
+    assert(testOrder(l1, l2, Order::less));
+  }
+  // Greater, due to contained values
+  {
+    Container<Elem> l1{1, 2, 2, 4};
+    Container<Elem> l2{1, 1, 2, 3};
+    assert(testOrder(l1, l2, Order::greater));
+  }
+  // Shorter list
+  {
+    Container<Elem> l1{1, 1, 2, 2};
+    Container<Elem> l2{1, 1, 2, 2, 3};
+    assert(testOrder(l1, l2, Order::less));
+  }
+  // Longer list
+  {
+    Container<Elem> l1{1, 1, 2, 2, 3};
+    Container<Elem> l2{1, 1, 2, 2};
+    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 set containers
+template <template <typename...> typename Container>
+constexpr bool test_ordered_set_container_spaceship() {
+  // Thanks to SFINAE, the following is not a compiler error but returns `false`
+  struct NonComparable {};
+  static_assert(!std::three_way_comparable<Container<NonComparable>>);
+
+  // The container should fulfill `std::three_way_comparable`
+  static_assert(std::three_way_comparable<Container<int>>);
+
+  // Test different comparison categories
+  test_ordered_set_spaceship_with_type<Container, int, std::strong_ordering>();
+  test_ordered_set_spaceship_with_type<Container, StrongOrder, std::strong_ordering>();
+  test_ordered_set_spaceship_with_type<Container, WeakOrder, std::weak_ordering>();
+  // `set` doesn't support `std::partial_ordering`
+  if constexpr (!std::is_same_v<Container<PartialOrder>, std::set<PartialOrder>>) {
+    test_ordered_set_spaceship_with_type<Container, PartialOrder, std::partial_ordering>();
+  }
+
+  // `LessAndEqComp` does not have `operator<=>`. Ordering is synthesized based on `operator<`
+  test_ordered_set_spaceship_with_type<Container, LessAndEqComp, std::weak_ordering>();
+
+  return true;
+}
+
 #endif