[libc++][spaceship] Implement `operator<=>` for `queue`
Implements parts of P1614R2 `operator<=>` for `queue`
Reviewed By: #libc, Mordante
Differential Revision: https://reviews.llvm.org/D146066
GitOrigin-RevId: 172d990c0394c80549f36977ca7b2eae4dcc4185
diff --git a/docs/Status/SpaceshipProjects.csv b/docs/Status/SpaceshipProjects.csv
index 6dd14bd..e912983 100644
--- a/docs/Status/SpaceshipProjects.csv
+++ b/docs/Status/SpaceshipProjects.csv
@@ -45,7 +45,7 @@
| `multimap <https://reviews.llvm.org/D145976>`_",[expos.only.func],Hristo Hristov,|Complete|
| `[associative.set.syn] <https://wg21.link/associative.set.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| multiset
| set",[expos.only.func],Hristo Hristov,|In Progress|
-| `[queue.ops] <https://wg21.link/queue.ops>`_,| `queue <https://reviews.llvm.org/D146066>`_,None,Hristo Hristov,|In Progress|
+| `[queue.ops] <https://wg21.link/queue.ops>`_,| `queue <https://reviews.llvm.org/D146066>`_,None,Hristo Hristov,|Complete|
| `[stack.ops] <https://wg21.link/stack.ops>`_,| `stack <https://reviews.llvm.org/D146094>`_,None,Hristo Hristov,|In Progress|
| `[reverse.iter.cmp] <https://wg21.link/reverse.iter.cmp>`_,| `reverse_iterator <https://reviews.llvm.org/D113695>`_,None,Mikhail Maltsev,|Complete|
| `[move.iter.op.comp] <https://wg21.link/move.iter.op.comp>`_,| `move_iterator <https://reviews.llvm.org/D117656>`_,None,Arthur O'Dwyer,|Complete|
diff --git a/include/queue b/include/queue
index 89623d5..c1c3d29 100644
--- a/include/queue
+++ b/include/queue
@@ -116,6 +116,10 @@
template <class T, class Container>
bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);
+template<class T, three_way_comparable Container>
+ compare_three_way_result_t<Container>
+ operator<=>(const queue<T, Container>& x, const queue<T, Container>& y); // since C++20
+
template <class T, class Container>
void swap(queue<T, Container>& x, queue<T, Container>& y)
noexcept(noexcept(x.swap(y)));
@@ -550,6 +554,17 @@
return !(__y < __x);
}
+#if _LIBCPP_STD_VER >= 20
+
+template <class _Tp, three_way_comparable _Container>
+_LIBCPP_HIDE_FROM_ABI compare_three_way_result_t<_Container>
+operator<=>(const queue<_Tp, _Container>& __x, const queue<_Tp, _Container>& __y) {
+ // clang 16 bug: declaring `friend operator<=>` causes "use of overloaded operator '*' is ambiguous" errors
+ return __x.__get_container() <=> __y.__get_container();
+}
+
+#endif
+
template <class _Tp, class _Container>
inline _LIBCPP_INLINE_VISIBILITY
__enable_if_t<__is_swappable<_Container>::value, void>
diff --git a/test/std/containers/container.adaptors/queue/queue.ops/compare.three_way.pass.cpp b/test/std/containers/container.adaptors/queue/queue.ops/compare.three_way.pass.cpp
new file mode 100644
index 0000000..a9b0513
--- /dev/null
+++ b/test/std/containers/container.adaptors/queue/queue.ops/compare.three_way.pass.cpp
@@ -0,0 +1,30 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+
+// <queue>
+
+// template<class T, three_way_comparable Container>
+// compare_three_way_result_t<Container>
+// operator<=>(const queue<T, Container>& x, const queue<T, Container>& y);
+
+#include <cassert>
+#include <deque>
+#include <queue>
+#include <list>
+
+#include "nasty_containers.h"
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+ assert((test_sequence_container_adaptor_spaceship<std::queue, std::deque>()));
+ assert((test_sequence_container_adaptor_spaceship<std::queue, std::list>()));
+ assert((test_sequence_container_adaptor_spaceship<std::queue, nasty_list>()));
+ // `std::queue` is not constexpr, so no `static_assert` test here.
+ return 0;
+}
diff --git a/test/support/nasty_containers.h b/test/support/nasty_containers.h
index 2f4f04d..f616f73 100644
--- a/test/support/nasty_containers.h
+++ b/test/support/nasty_containers.h
@@ -138,6 +138,14 @@
template <class T>
bool operator==(const nasty_vector<T>& x, const nasty_vector<T>& y) { return x.v_ == y.v_; }
+
+#if TEST_STD_VER >= 20
+
+template <class T>
+auto operator<=>(const nasty_vector<T>& x, const nasty_vector<T>& y) { return x.v_ <=> y.v_; }
+
+#endif
+
template <class T>
class nasty_list
{
@@ -285,6 +293,13 @@
template <class T>
bool operator==(const nasty_list<T>& x, const nasty_list<T>& y) { return x.l_ == y.l_; }
+#if TEST_STD_VER >= 20
+
+template <class T>
+auto operator<=>(const nasty_list<T>& x, const nasty_list<T>& y) { return x.l_ <=> y.l_; }
+
+#endif
+
// Not really a mutex, but can play one in tests
class nasty_mutex
{
diff --git a/test/support/test_container_comparisons.h b/test/support/test_container_comparisons.h
index 8748f2d..67165dc 100644
--- a/test/support/test_container_comparisons.h
+++ b/test/support/test_container_comparisons.h
@@ -84,6 +84,96 @@
return true;
}
+// Implementation detail of `test_sequence_container_adaptor_spaceship`
+template <template <typename...> typename ContainerAdaptor,
+ template <typename...>
+ typename Container,
+ typename Elem,
+ typename Order>
+constexpr void test_sequence_container_adaptor_spaceship_with_type() {
+ // Empty containers
+ {
+ Container<Elem> l1;
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2;
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::equivalent));
+ }
+ // Identical contents
+ {
+ Container<Elem> l1{1, 1};
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2{1, 1};
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::equivalent));
+ }
+ // Less, due to contained values
+ {
+ Container<Elem> l1{1, 1};
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2{1, 2};
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::less));
+ }
+ // Greater, due to contained values
+ {
+ Container<Elem> l1{1, 3};
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2{1, 2};
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::greater));
+ }
+ // Shorter list
+ {
+ Container<Elem> l1{1};
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2{1, 2};
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::less));
+ }
+ // Longer list
+ {
+ Container<Elem> l1{1, 2};
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2{1};
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::greater));
+ }
+ // Unordered
+ if constexpr (std::is_same_v<Elem, PartialOrder>) {
+ Container<Elem> l1{1, std::numeric_limits<int>::min()};
+ ContainerAdaptor<Elem, Container<Elem>> ca1{l1};
+ Container<Elem> l2{1, 2};
+ ContainerAdaptor<Elem, Container<Elem>> ca2{l2};
+ assert(testOrder(ca1, ca2, Order::unordered));
+ }
+}
+
+// Tests the `operator<=>` on sequence container adaptors
+template <template <typename...> typename ContainerAdaptor, template <typename...> typename Container>
+constexpr bool test_sequence_container_adaptor_spaceship() {
+ // Thanks to SFINAE, the following is not a compiler error but returns `false`
+ struct NonComparable {};
+ static_assert(!std::three_way_comparable<ContainerAdaptor<NonComparable>>);
+
+ // The container should fulfill `std::three_way_comparable`
+ static_assert(std::three_way_comparable<ContainerAdaptor<int, Container<int>>>);
+
+ // Test different comparison categories
+ test_sequence_container_adaptor_spaceship_with_type<ContainerAdaptor, Container, int, std::strong_ordering>();
+ test_sequence_container_adaptor_spaceship_with_type<ContainerAdaptor, Container, StrongOrder, std::strong_ordering>();
+ test_sequence_container_adaptor_spaceship_with_type<ContainerAdaptor, Container, WeakOrder, std::weak_ordering>();
+ test_sequence_container_adaptor_spaceship_with_type<ContainerAdaptor,
+ Container,
+ PartialOrder,
+ std::partial_ordering>();
+
+ // `LessAndEqComp` does not have `operator<=>`. Ordering is synthesized based on `operator<`
+ test_sequence_container_adaptor_spaceship_with_type<ContainerAdaptor, Container, LessAndEqComp, std::weak_ordering>();
+
+ return true;
+}
+
// Implementation detail of `test_ordered_map_container_spaceship`
template <template <typename...> typename Container, typename Key, typename Val, typename Order, typename Compare>
constexpr void test_ordered_map_container_spaceship_with_type(Compare comp) {
