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

[H-G-Hristov]

Summary

Implements parts of P1614R2 operator<=> for queue

[H-G-Hristov]

• Added URL

[philnik]

libcxx/test/std/containers/container.adaptors/queue/compare.three_way.pass.cpp

25 ↗

(On Diff #505155)

We should also test with a custom container to make sure it actually calls operator<=> and not std::lexicographical_compare_three_way(x.begin(), x.end(), y.begin(), y.end()).

[Mordante]

Can you fix the CI and address the open review comments, I prefer to review with the CI results.

[H-G-Hristov]

• Fix CI

[H-G-Hristov]

Thank you for the review. I still need to add tests with a custom container.

[H-G-Hristov]

• Rebased & tweaks

[H-G-Hristov]

• Try to fix CI

[H-G-Hristov]

• Try to fix CI

[H-G-Hristov]

Rebased

[H-G-Hristov]

Rebased

[H-G-Hristov]

Rebased try to fix CI

[H-G-Hristov]

Rebased

[H-G-Hristov]

libcxx/test/std/containers/container.adaptors/queue/compare.three_way.pass.cpp

25 ↗

(On Diff #505155)

I added a "custom container" test I hope that it is custom enough.

[Mordante]

In general I'm happy, but I would like to see whether custom_container_iterator can be removed.

libcxx/test/support/test_container_comparisons.h

25

Would it be possible to use nasty_vector from "nasty_containers.h" instead?

You will need to add

#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

but that seems easier than to add a new class.

[H-G-Hristov]

Addressed review comments

[H-G-Hristov]

Addressed review comments

[H-G-Hristov]

libcxx/test/support/test_container_comparisons.h

25

Cool! I looked for off-the-shelf containers but couldn't find them.
FYI The queue supports lists. I guess the stack supports vectors. I'll use it there.

[H-G-Hristov]

Cleanup and rebase

[Mordante]

LGTM!

[Mordante]

As mentioned in D146094 these are the changes I applied locally to make friendship work. Can you test this too. If the CI fails please ping me on Discord then I will have another look.

libcxx/include/queue

401

486

[H-G-Hristov]

Re-applied suggested changes: friend operator<=>

[Mordante]

In D146066#4393805, @Mordante wrote:

As mentioned in D146094 these are the changes I applied locally to make friendship work. Can you test this too. If the CI fails please ping me on Discord then I will have another look.

It seems this solution fails in Clang 16 and works in Clang 15 and Clang 17. Please leave a comment in the body of the operator<=> to explain why you use the current approach.

[H-G-Hristov]

Rebased + fixed implementation

[H-G-Hristov]

@Mordante Thank you for looking into this.

libcxx/docs/Status/SpaceshipProjects.csv

 | `[deque.syn] <https://wg21.link/deque.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `deque <https://reviews.llvm.org/D144821>`_,[expos.only.func],Hristo Hristov,|Complete|
 | `[forward.list.syn] <https://wg21.link/forward.list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `forward_list <https://reviews.llvm.org/D145172>`_,[expos.only.func],Hristo Hristov,|Complete|
 | `[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 <https://reviews.llvm.org/D145976>`_
 | `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|
 | `[counted.iter.cmp] <https://wg21.link/counted.iter.cmp>`_,| `counted_iterator <https://reviews.llvm.org/D106205>`_,None,Zoe Carver,|Complete|
 | `[range.iota.iterator] <https://wg21.link/range.iota.iterator>`_,| `ranges::iota_view::iterator <https://reviews.llvm.org/D110774>`_,[concepts.cmp],Arthur O'Dwyer,|Complete|
 | `[range.transform.iterator] <https://wg21.link/range.transform.iterator>`_,| `ranges::transform_view::iterator <https://reviews.llvm.org/D110774>`_,[concepts.cmp],Arthur O'Dwyer,|Complete|
 | `[range.elements.iterator] <https://wg21.link/range.elements.iterator>`_,| ranges::elements_view::iterator,[concepts.cmp],Hui Xie,|Complete|
 | `[time.duration.comparisons] <https://wg21.link/time.duration.comparisons>`_, `chrono::duration <https://reviews.llvm.org/D145881>`_, None, Hristo Hristov, |Complete|

libcxx/include/queue

template <class T, class Container>
   bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
 
 template <class T, class Container>
   bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
 
 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)));
 
 template <class T, class Container = vector<T>,
           class Compare = less<typename Container::value_type>>
 class priority_queue
 {
#endif // _LIBCPP_CXX03_LANG
     bool
     operator==(const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 
     template <class _T1, class _C1>
     friend
     _LIBCPP_INLINE_VISIBILITY
     bool
     operator< (const queue<_T1, _C1>& __x,const queue<_T1, _C1>& __y);
 };
 
 #if _LIBCPP_STD_VER >= 17
 template<class _Container,
          class = enable_if_t<!__is_allocator<_Container>::value>
 >
 queue(_Container)
     -> queue<typename _Container::value_type, _Container>;
 

 template <class _Tp, class _Container>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator<=(const queue<_Tp, _Container>& __x,const queue<_Tp, _Container>& __y)
 {
     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) {
+    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>
 swap(queue<_Tp, _Container>& __x, queue<_Tp, _Container>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {
     __x.swap(__y);
 }

libcxx/test/std/containers/container.adaptors/queue/queue.ops/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
+
+// <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 "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, custom_sequence_container>()));
+  // `std::queue` 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 <compare>
 #include <functional>
+#include <list>
 #include <set>
 
 #include "test_comparisons.h"
 
+////////////////////////////////////////////////////////////////////////////////
+// Custom containers
+////////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+class custom_container_iterator : public std::list<T>::iterator {};
+
+template <typename T>
+class custom_container {
+public:
+  using value_type      = T;
+  using reference       = T&;
+  using const_reference = const T&;
+  using iterator        = custom_container_iterator<T>;
+  using const_iterator  = const custom_container_iterator<T>;
+  using difference_type = std::ptrdiff_t;
+  using size_type       = std::size_t;
+
+public:
+  custom_container()                                   = default;
+  custom_container(const custom_container&)            = default;
+  custom_container& operator=(const custom_container&) = default;
+  custom_container(custom_container&&)                 = default;
+  custom_container& operator=(custom_container&&)      = default;
+  ~custom_container()                                  = default;
+
+public:
+  custom_container(std::initializer_list<T> values) : data{values} {}
+
+public:
+  auto being() { return iterator{}; }
+  auto end() { return iterator{}; }
+
+  auto cbeing() { return const_iterator{}; }
+  auto cend() { return const_iterator{}; }
+
+public:
+  bool operator==(const custom_container& other) const = default;
+
+  auto operator<=>(const custom_container& other) const = default;
+
+public:
+  void swap(custom_container& other) noexcept { swap(this, other); }
+
+  auto size() const { return data.size(); }
+
+  auto max_size() const { return data.max_size(); }
+
+  auto empty() { return data.empty(); }
+
+  template <typename U>
+  friend void swap(custom_container<U>&, custom_container<U>&);
+
+protected:
+  std::list<T> data;
+};
+
+template <typename T>
+void swap(custom_container<T> lhs, custom_container<T> rhs) {
+  std::swap(lhs, rhs);
+}
+
+template <typename T>
+class custom_sequence_container : public custom_container<T> {
+public:
+  custom_sequence_container()                                            = default;
+  custom_sequence_container(const custom_sequence_container&)            = default;
+  custom_sequence_container& operator=(const custom_sequence_container&) = default;
+  custom_sequence_container(custom_sequence_container&&)                 = default;
+  custom_sequence_container& operator=(custom_sequence_container&&)      = default;
+  ~custom_sequence_container()                                           = default;
+
+public:
+  custom_sequence_container(std::initializer_list<T> values) : custom_sequence_container::custom_container{values} {}
+
+public:
+  template <class... Args>
+  auto emplace(typename custom_container<T>::const_iterator pos, Args&&... args) {
+    return this->data.emplace(pos, std::forward<T, Args>(args)...);
+  }
+
+  auto insert(T value) { return this->data.insert(value); }
+
+public:
+  auto back() { return this->data.back(); };
+  auto front() { return this->data.back(); }
+  void push_back(T data) { this->data.push_back(data); }
+  void pop_back() { this->data.pop_front(); };
+};
+
+////////////////////////////////////////////////////////////////////////////////
+// Test helpers
+////////////////////////////////////////////////////////////////////////////////
+
 // 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;
     Container<Elem> l2;
     assert(testOrder(l1, l2, Order::equivalent));
constexpr bool test_sequence_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>>);
 
   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) {
   // Empty containers
   {
     Container<Key, Val, Compare> l1{{}, comp};
     Container<Key, Val, Compare> l2{{}, comp};
     assert(testOrder(l1, l2, Order::equivalent));