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

Implements parts of **P1614R2**: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1614r2.html

- Implemented `operator<=>` for `optional`
- Updated "optional synopsis" to match the current draft https://eel.is/c++draft/optional closer
- Implemented https://cplusplus.github.io/LWG/issue3566
- Implemented https://cplusplus.github.io/LWG/issue3746

Reviewed By: #libc, philnik, ldionne

Differential Revision: https://reviews.llvm.org/D146392

1 files changed, 139 insertions, 76 deletions

diff --git a/libcxx/include/optional b/libcxx/include/optional
index a387de473f30..8895ed152dc8 100644
--- a/libcxx/include/optional
+++ b/libcxx/include/optional
@@ -16,107 +16,126 @@
 // C++1z
 
 namespace std {
-  // 23.6.3, optional for object types
-  template <class T> class optional;
+  // [optional.optional], class template optional
+  template <class T>
+    class optional;
 
-  // 23.6.4, no-value state indicator
+  template<class T>
+    concept is-derived-from-optional = requires(const T& t) {       // exposition only
+      []<class U>(const optional<U>&){ }(t);
+    };
+
+  // [optional.nullopt], no-value state indicator
   struct nullopt_t{see below };
   inline constexpr nullopt_t nullopt(unspecified );
 
-  // 23.6.5, class bad_optional_access
+  // [optional.bad.access], class bad_optional_access
   class bad_optional_access;
 
-  // 23.6.6, relational operators
+  // [optional.relops], relational operators
   template <class T, class U>
-  constexpr bool operator==(const optional<T>&, const optional<U>&);
+    constexpr bool operator==(const optional<T>&, const optional<U>&);
   template <class T, class U>
-  constexpr bool operator!=(const optional<T>&, const optional<U>&);
+    constexpr bool operator!=(const optional<T>&, const optional<U>&);
   template <class T, class U>
-  constexpr bool operator<(const optional<T>&, const optional<U>&);
+    constexpr bool operator<(const optional<T>&, const optional<U>&);
   template <class T, class U>
-  constexpr bool operator>(const optional<T>&, const optional<U>&);
+    constexpr bool operator>(const optional<T>&, const optional<U>&);
   template <class T, class U>
-  constexpr bool operator<=(const optional<T>&, const optional<U>&);
+    constexpr bool operator<=(const optional<T>&, const optional<U>&);
   template <class T, class U>
-  constexpr bool operator>=(const optional<T>&, const optional<U>&);
-
-  // 23.6.7 comparison with nullopt
-  template <class T> constexpr bool operator==(const optional<T>&, nullopt_t) noexcept;
-  template <class T> constexpr bool operator==(nullopt_t, const optional<T>&) noexcept;
-  template <class T> constexpr bool operator!=(const optional<T>&, nullopt_t) noexcept;
-  template <class T> constexpr bool operator!=(nullopt_t, const optional<T>&) noexcept;
-  template <class T> constexpr bool operator<(const optional<T>&, nullopt_t) noexcept;
-  template <class T> constexpr bool operator<(nullopt_t, const optional<T>&) noexcept;
-  template <class T> constexpr bool operator<=(const optional<T>&, nullopt_t) noexcept;
-  template <class T> constexpr bool operator<=(nullopt_t, const optional<T>&) noexcept;
-  template <class T> constexpr bool operator>(const optional<T>&, nullopt_t) noexcept;
-  template <class T> constexpr bool operator>(nullopt_t, const optional<T>&) noexcept;
-  template <class T> constexpr bool operator>=(const optional<T>&, nullopt_t) noexcept;
-  template <class T> constexpr bool operator>=(nullopt_t, const optional<T>&) noexcept;
-
-  // 23.6.8, comparison with T
-  template <class T, class U> constexpr bool operator==(const optional<T>&, const U&);
-  template <class T, class U> constexpr bool operator==(const T&, const optional<U>&);
-  template <class T, class U> constexpr bool operator!=(const optional<T>&, const U&);
-  template <class T, class U> constexpr bool operator!=(const T&, const optional<U>&);
-  template <class T, class U> constexpr bool operator<(const optional<T>&, const U&);
-  template <class T, class U> constexpr bool operator<(const T&, const optional<U>&);
-  template <class T, class U> constexpr bool operator<=(const optional<T>&, const U&);
-  template <class T, class U> constexpr bool operator<=(const T&, const optional<U>&);
-  template <class T, class U> constexpr bool operator>(const optional<T>&, const U&);
-  template <class T, class U> constexpr bool operator>(const T&, const optional<U>&);
-  template <class T, class U> constexpr bool operator>=(const optional<T>&, const U&);
-  template <class T, class U> constexpr bool operator>=(const T&, const optional<U>&);
-
-  // 23.6.9, specialized algorithms
-  template <class T> void swap(optional<T>&, optional<T>&) noexcept(see below ); // constexpr in C++20
-  template <class T> constexpr optional<see below > make_optional(T&&);
-  template <class T, class... Args>
+    constexpr bool operator>=(const optional<T>&, const optional<U>&);
+  template<class T, three_way_comparable_with<T> U>
+    constexpr compare_three_way_result_t<T, U>
+      operator<=>(const optional<T>&, const optional<U>&); // since C++20
+
+  // [optional.nullops], comparison with nullopt
+  template<class T> constexpr bool operator==(const optional<T>&, nullopt_t) noexcept;
+  template<class T> constexpr bool operator==(nullopt_t, const optional<T>&) noexcept; // until C++17
+  template<class T> constexpr bool operator!=(const optional<T>&, nullopt_t) noexcept; // until C++17
+  template<class T> constexpr bool operator!=(nullopt_t, const optional<T>&) noexcept; // until C++17
+  template<class T> constexpr bool operator<(const optional<T>&, nullopt_t) noexcept;  // until C++17
+  template<class T> constexpr bool operator<(nullopt_t, const optional<T>&) noexcept;  // until C++17
+  template<class T> constexpr bool operator<=(const optional<T>&, nullopt_t) noexcept; // until C++17
+  template<class T> constexpr bool operator<=(nullopt_t, const optional<T>&) noexcept; // until C++17
+  template<class T> constexpr bool operator>(const optional<T>&, nullopt_t) noexcept;  // until C++17
+  template<class T> constexpr bool operator>(nullopt_t, const optional<T>&) noexcept;  // until C++17
+  template<class T> constexpr bool operator>=(const optional<T>&, nullopt_t) noexcept; // until C++17
+  template<class T> constexpr bool operator>=(nullopt_t, const optional<T>&) noexcept; // until C++17
+  template<class T>
+    constexpr strong_ordering operator<=>(const optional<T>&, nullopt_t) noexcept;     // since C++20
+
+  // [optional.comp.with.t], comparison with T
+  template<class T, class U> constexpr bool operator==(const optional<T>&, const U&);
+  template<class T, class U> constexpr bool operator==(const T&, const optional<U>&);
+  template<class T, class U> constexpr bool operator!=(const optional<T>&, const U&);
+  template<class T, class U> constexpr bool operator!=(const T&, const optional<U>&);
+  template<class T, class U> constexpr bool operator<(const optional<T>&, const U&);
+  template<class T, class U> constexpr bool operator<(const T&, const optional<U>&);
+  template<class T, class U> constexpr bool operator<=(const optional<T>&, const U&);
+  template<class T, class U> constexpr bool operator<=(const T&, const optional<U>&);
+  template<class T, class U> constexpr bool operator>(const optional<T>&, const U&);
+  template<class T, class U> constexpr bool operator>(const T&, const optional<U>&);
+  template<class T, class U> constexpr bool operator>=(const optional<T>&, const U&);
+  template<class T, class U> constexpr bool operator>=(const T&, const optional<U>&);
+  template<class T, class U>
+      requires (!is-derived-from-optional<U>) && three_way_comparable_with<T, U>
+    constexpr compare_three_way_result_t<T, U>
+      operator<=>(const optional<T>&, const U&);                                       // since C++20
+
+  // [optional.specalg], specialized algorithms
+  template<class T>
+    void swap(optional<T>&, optional<T>&) noexcept(see below ); // constexpr in C++20
+
+  template<class T>
+    constexpr optional<see below > make_optional(T&&);
+  template<class T, class... Args>
     constexpr optional<T> make_optional(Args&&... args);
-  template <class T, class U, class... Args>
+  template<class T, class U, class... Args>
     constexpr optional<T> make_optional(initializer_list<U> il, Args&&... args);
 
-  // 23.6.10, hash support
-  template <class T> struct hash;
-  template <class T> struct hash<optional<T>>;
+  // [optional.hash], hash support
+  template<class T> struct hash;
+  template<class T> struct hash<optional<T>>;
 
-  template <class T> class optional {
+  template<class T>
+  class optional {
   public:
     using value_type = T;
 
-    // 23.6.3.1, constructors
+    // [optional.ctor], constructors
     constexpr optional() noexcept;
     constexpr optional(nullopt_t) noexcept;
     constexpr optional(const optional &);
     constexpr optional(optional &&) noexcept(see below);
-    template <class... Args> constexpr explicit optional(in_place_t, Args &&...);
-    template <class U, class... Args>
+    template<class... Args>
+      constexpr explicit optional(in_place_t, Args &&...);
+    template<class U, class... Args>
       constexpr explicit optional(in_place_t, initializer_list<U>, Args &&...);
-    template <class U = T>
+    template<class U = T>
       constexpr explicit(see-below) optional(U &&);
-    template <class U>
-      explicit(see-below) optional(const optional<U> &);         // constexpr in C++20
-    template <class U>
-      explicit(see-below) optional(optional<U> &&);              // constexpr in C++20
+    template<class U>
+      explicit(see-below) optional(const optional<U> &);                          // constexpr in C++20
+    template<class U>
+      explicit(see-below) optional(optional<U> &&);                               // constexpr in C++20
 
-    // 23.6.3.2, destructor
+    // [optional.dtor], destructor
     ~optional(); // constexpr in C++20
 
-    // 23.6.3.3, assignment
-    optional &operator=(nullopt_t) noexcept;                     // constexpr in C++20
+    // [optional.assign], assignment
+    optional &operator=(nullopt_t) noexcept;                                      // constexpr in C++20
     constexpr optional &operator=(const optional &);
     constexpr optional &operator=(optional &&) noexcept(see below);
-    template <class U = T> optional &operator=(U &&);            // constexpr in C++20
-    template <class U> optional &operator=(const optional<U> &); // constexpr in C++20
-    template <class U> optional &operator=(optional<U> &&);      // constexpr in C++20
-    template <class... Args> T& emplace(Args &&...);             // constexpr in C++20
-    template <class U, class... Args>
-      T& emplace(initializer_list<U>, Args &&...);               // constexpr in C++20
-
-    // 23.6.3.4, swap
+    template<class U = T> optional &operator=(U &&);                              // constexpr in C++20
+    template<class U> optional &operator=(const optional<U> &);                   // constexpr in C++20
+    template<class U> optional &operator=(optional<U> &&);                        // constexpr in C++20
+    template<class... Args> T& emplace(Args &&...);                               // constexpr in C++20
+    template<class U, class... Args> T& emplace(initializer_list<U>, Args &&...); // constexpr in C++20
+
+    // [optional.swap], swap
     void swap(optional &) noexcept(see below ); // constexpr in C++20
 
-    // 23.6.3.5, observers
+    // [optional.observe], observers
     constexpr T const *operator->() const;
     constexpr T *operator->();
     constexpr T const &operator*() const &;
@@ -129,8 +148,8 @@ namespace std {
     constexpr T &value() &;
     constexpr T &&value() &&;
     constexpr const T &&value() const &&;
-    template <class U> constexpr T value_or(U &&) const &;
-    template <class U> constexpr T value_or(U &&) &&;
+    template<class U> constexpr T value_or(U &&) const &;
+    template<class U> constexpr T value_or(U &&) &&;
 
     // [optional.monadic], monadic operations
     template<class F> constexpr auto and_then(F&& f) &;         // since C++23
@@ -144,15 +163,15 @@ namespace std {
     template<class F> constexpr optional or_else(F&& f) &&;     // since C++23
     template<class F> constexpr optional or_else(F&& f) const&; // since C++23
 
-    // 23.6.3.6, modifiers
-    void reset() noexcept; // constexpr in C++20
+    // [optional.mod], modifiers
+    void reset() noexcept;                                      // constexpr in C++20
 
   private:
-    T *val; // exposition only
+    T *val;         // exposition only
   };
 
-template<class T>
-  optional(T) -> optional<T>;
+  template<class T>
+    optional(T) -> optional<T>;
 
 } // namespace std
 
@@ -160,6 +179,8 @@ template<class T>
 
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__availability>
+#include <__compare/compare_three_way_result.h>
+#include <__compare/three_way_comparable.h>
 #include <__concepts/invocable.h>
 #include <__config>
 #include <__functional/hash.h>
@@ -633,6 +654,14 @@ using __optional_sfinae_assign_base_t = __sfinae_assign_base<
 
 template<class _Tp>
 class optional;
+
+#if _LIBCPP_STD_VER >= 20
+
+template <class _Tp>
+concept __is_derived_from_optional = requires(const _Tp& __t) { []<class __Up>(const optional<__Up>&) {}(__t); };
+
+#  endif // _LIBCPP_STD_VER >= 20
+
 template <class _Tp>
 struct __is_std_optional : false_type {};
 template <class _Tp> struct __is_std_optional<optional<_Tp>> : true_type {};
@@ -1288,6 +1317,18 @@ operator>=(const optional<_Tp>& __x, const optional<_Up>& __y)
     return *__x >= *__y;
 }
 
+#if _LIBCPP_STD_VER >= 20
+
+template <class _Tp, three_way_comparable_with<_Tp> _Up>
+_LIBCPP_HIDE_FROM_ABI constexpr compare_three_way_result_t<_Tp, _Up>
+operator<=>(const optional<_Tp>& __x, const optional<_Up>& __y) {
+    if (__x && __y)
+        return *__x <=> *__y;
+    return __x.has_value() <=> __y.has_value();
+}
+
+#endif // _LIBCPP_STD_VER >= 20
+
 // Comparisons with nullopt
 template <class _Tp>
 _LIBCPP_INLINE_VISIBILITY constexpr
@@ -1297,6 +1338,8 @@ operator==(const optional<_Tp>& __x, nullopt_t) noexcept
     return !static_cast<bool>(__x);
 }
 
+#if _LIBCPP_STD_VER <= 17
+
 template <class _Tp>
 _LIBCPP_INLINE_VISIBILITY constexpr
 bool
@@ -1385,6 +1428,15 @@ operator>=(nullopt_t, const optional<_Tp>& __x) noexcept
     return !static_cast<bool>(__x);
 }
 
+#else // _LIBCPP_STD_VER <= 17
+
+template <class _Tp>
+_LIBCPP_HIDE_FROM_ABI constexpr strong_ordering operator<=>(const optional<_Tp>& __x, nullopt_t) noexcept {
+    return __x.has_value() <=> false;
+}
+
+#endif // _LIBCPP_STD_VER <= 17
+
 // Comparisons with T
 template <class _Tp, class _Up>
 _LIBCPP_INLINE_VISIBILITY constexpr
@@ -1530,6 +1582,17 @@ operator>=(const _Tp& __v, const optional<_Up>& __x)
     return static_cast<bool>(__x) ? __v >= *__x : true;
 }
 
+#if _LIBCPP_STD_VER >= 20
+
+template <class _Tp, class _Up>
+  requires(!__is_derived_from_optional<_Up>) && three_way_comparable_with<_Tp, _Up>
+_LIBCPP_HIDE_FROM_ABI constexpr compare_three_way_result_t<_Tp, _Up>
+operator<=>(const optional<_Tp>& __x, const _Up& __v) {
+    return __x.has_value() ? *__x <=> __v : strong_ordering::less;
+}
+
+#endif // _LIBCPP_STD_VER >= 20
+
 
 template <class _Tp>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20