1// -*- C++ -*- operator<=> three-way comparison support.
2
3// Copyright (C) 2019-2025 Free Software Foundation, Inc.
4//
5// This file is part of GCC.
6//
7// GCC is free software; you can redistribute it and/or modify
8// it under the terms of the GNU General Public License as published by
9// the Free Software Foundation; either version 3, or (at your option)
10// any later version.
11//
12// GCC is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15// GNU General Public License for more details.
16//
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file compare
27 * This is a Standard C++ Library header.
28 */
29
30#ifndef _COMPARE
31#define _COMPARE
32
33#ifdef _GLIBCXX_SYSHDR
34#pragma GCC system_header
35#endif
36
37#define __glibcxx_want_three_way_comparison
38#include <bits/version.h>
39
40#if __cplusplus > 201703L && __cpp_impl_three_way_comparison >= 201907L
41
42#include <concepts>
43
44#pragma GCC diagnostic push
45#pragma GCC diagnostic ignored "-Wpedantic" // __int128
46#pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
47
48namespace std _GLIBCXX_VISIBILITY(default)
49{
50 // [cmp.categories], comparison category types
51
52 namespace __cmp_cat
53 {
54 using type = signed char;
55
56 enum class _Ord : type { equivalent = 0, less = -1, greater = 1 };
57
58 enum class _Ncmp : type { _Unordered = 2 };
59
60 struct __unspec
61 {
62 consteval __unspec(__unspec*) noexcept { }
63 };
64 }
65
66 class partial_ordering
67 {
68 // less=0xff, equiv=0x00, greater=0x01, unordered=0x02
69 __cmp_cat::type _M_value;
70
71 constexpr explicit
72 partial_ordering(__cmp_cat::_Ord __v) noexcept
73 : _M_value(__cmp_cat::type(__v))
74 { }
75
76 constexpr explicit
77 partial_ordering(__cmp_cat::_Ncmp __v) noexcept
78 : _M_value(__cmp_cat::type(__v))
79 { }
80
81 friend class weak_ordering;
82 friend class strong_ordering;
83
84 public:
85 // valid values
86 static const partial_ordering less;
87 static const partial_ordering equivalent;
88 static const partial_ordering greater;
89 static const partial_ordering unordered;
90
91 // comparisons
92 [[nodiscard]]
93 friend constexpr bool
94 operator==(partial_ordering __v, __cmp_cat::__unspec) noexcept
95 { return __v._M_value == 0; }
96
97 [[nodiscard]]
98 friend constexpr bool
99 operator==(partial_ordering, partial_ordering) noexcept = default;
100
101 [[nodiscard]]
102 friend constexpr bool
103 operator< (partial_ordering __v, __cmp_cat::__unspec) noexcept
104 { return __v._M_value == -1; }
105
106 [[nodiscard]]
107 friend constexpr bool
108 operator> (partial_ordering __v, __cmp_cat::__unspec) noexcept
109 { return __v._M_value == 1; }
110
111 [[nodiscard]]
112 friend constexpr bool
113 operator<=(partial_ordering __v, __cmp_cat::__unspec) noexcept
114 { return __v._M_value <= 0; }
115
116 [[nodiscard]]
117 friend constexpr bool
118 operator>=(partial_ordering __v, __cmp_cat::__unspec) noexcept
119 { return __cmp_cat::type(__v._M_value & 1) == __v._M_value; }
120
121 [[nodiscard]]
122 friend constexpr bool
123 operator< (__cmp_cat::__unspec, partial_ordering __v) noexcept
124 { return __v._M_value == 1; }
125
126 [[nodiscard]]
127 friend constexpr bool
128 operator> (__cmp_cat::__unspec, partial_ordering __v) noexcept
129 { return __v._M_value == -1; }
130
131 [[nodiscard]]
132 friend constexpr bool
133 operator<=(__cmp_cat::__unspec, partial_ordering __v) noexcept
134 { return __cmp_cat::type(__v._M_value & 1) == __v._M_value; }
135
136 [[nodiscard]]
137 friend constexpr bool
138 operator>=(__cmp_cat::__unspec, partial_ordering __v) noexcept
139 { return 0 >= __v._M_value; }
140
141 [[nodiscard]]
142 friend constexpr partial_ordering
143 operator<=>(partial_ordering __v, __cmp_cat::__unspec) noexcept
144 { return __v; }
145
146 [[nodiscard]]
147 friend constexpr partial_ordering
148 operator<=>(__cmp_cat::__unspec, partial_ordering __v) noexcept
149 {
150 if (__v._M_value & 1)
151 return partial_ordering(__cmp_cat::_Ord(-__v._M_value));
152 else
153 return __v;
154 }
155 };
156
157 // valid values' definitions
158 inline constexpr partial_ordering
159 partial_ordering::less(__cmp_cat::_Ord::less);
160
161 inline constexpr partial_ordering
162 partial_ordering::equivalent(__cmp_cat::_Ord::equivalent);
163
164 inline constexpr partial_ordering
165 partial_ordering::greater(__cmp_cat::_Ord::greater);
166
167 inline constexpr partial_ordering
168 partial_ordering::unordered(__cmp_cat::_Ncmp::_Unordered);
169
170 class weak_ordering
171 {
172 __cmp_cat::type _M_value;
173
174 constexpr explicit
175 weak_ordering(__cmp_cat::_Ord __v) noexcept : _M_value(__cmp_cat::type(__v))
176 { }
177
178 friend class strong_ordering;
179
180 public:
181 // valid values
182 static const weak_ordering less;
183 static const weak_ordering equivalent;
184 static const weak_ordering greater;
185
186 [[nodiscard]]
187 constexpr operator partial_ordering() const noexcept
188 { return partial_ordering(__cmp_cat::_Ord(_M_value)); }
189
190 // comparisons
191 [[nodiscard]]
192 friend constexpr bool
193 operator==(weak_ordering __v, __cmp_cat::__unspec) noexcept
194 { return __v._M_value == 0; }
195
196 [[nodiscard]]
197 friend constexpr bool
198 operator==(weak_ordering, weak_ordering) noexcept = default;
199
200 [[nodiscard]]
201 friend constexpr bool
202 operator< (weak_ordering __v, __cmp_cat::__unspec) noexcept
203 { return __v._M_value < 0; }
204
205 [[nodiscard]]
206 friend constexpr bool
207 operator> (weak_ordering __v, __cmp_cat::__unspec) noexcept
208 { return __v._M_value > 0; }
209
210 [[nodiscard]]
211 friend constexpr bool
212 operator<=(weak_ordering __v, __cmp_cat::__unspec) noexcept
213 { return __v._M_value <= 0; }
214
215 [[nodiscard]]
216 friend constexpr bool
217 operator>=(weak_ordering __v, __cmp_cat::__unspec) noexcept
218 { return __v._M_value >= 0; }
219
220 [[nodiscard]]
221 friend constexpr bool
222 operator< (__cmp_cat::__unspec, weak_ordering __v) noexcept
223 { return 0 < __v._M_value; }
224
225 [[nodiscard]]
226 friend constexpr bool
227 operator> (__cmp_cat::__unspec, weak_ordering __v) noexcept
228 { return 0 > __v._M_value; }
229
230 [[nodiscard]]
231 friend constexpr bool
232 operator<=(__cmp_cat::__unspec, weak_ordering __v) noexcept
233 { return 0 <= __v._M_value; }
234
235 [[nodiscard]]
236 friend constexpr bool
237 operator>=(__cmp_cat::__unspec, weak_ordering __v) noexcept
238 { return 0 >= __v._M_value; }
239
240 [[nodiscard]]
241 friend constexpr weak_ordering
242 operator<=>(weak_ordering __v, __cmp_cat::__unspec) noexcept
243 { return __v; }
244
245 [[nodiscard]]
246 friend constexpr weak_ordering
247 operator<=>(__cmp_cat::__unspec, weak_ordering __v) noexcept
248 { return weak_ordering(__cmp_cat::_Ord(-__v._M_value)); }
249 };
250
251 // valid values' definitions
252 inline constexpr weak_ordering
253 weak_ordering::less(__cmp_cat::_Ord::less);
254
255 inline constexpr weak_ordering
256 weak_ordering::equivalent(__cmp_cat::_Ord::equivalent);
257
258 inline constexpr weak_ordering
259 weak_ordering::greater(__cmp_cat::_Ord::greater);
260
261 class strong_ordering
262 {
263 __cmp_cat::type _M_value;
264
265 constexpr explicit
266 strong_ordering(__cmp_cat::_Ord __v) noexcept
267 : _M_value(__cmp_cat::type(__v))
268 { }
269
270 public:
271 // valid values
272 static const strong_ordering less;
273 static const strong_ordering equal;
274 static const strong_ordering equivalent;
275 static const strong_ordering greater;
276
277 [[nodiscard]]
278 constexpr operator partial_ordering() const noexcept
279 { return partial_ordering(__cmp_cat::_Ord(_M_value)); }
280
281 [[nodiscard]]
282 constexpr operator weak_ordering() const noexcept
283 { return weak_ordering(__cmp_cat::_Ord(_M_value)); }
284
285 // comparisons
286 [[nodiscard]]
287 friend constexpr bool
288 operator==(strong_ordering __v, __cmp_cat::__unspec) noexcept
289 { return __v._M_value == 0; }
290
291 [[nodiscard]]
292 friend constexpr bool
293 operator==(strong_ordering, strong_ordering) noexcept = default;
294
295 [[nodiscard]]
296 friend constexpr bool
297 operator< (strong_ordering __v, __cmp_cat::__unspec) noexcept
298 { return __v._M_value < 0; }
299
300 [[nodiscard]]
301 friend constexpr bool
302 operator> (strong_ordering __v, __cmp_cat::__unspec) noexcept
303 { return __v._M_value > 0; }
304
305 [[nodiscard]]
306 friend constexpr bool
307 operator<=(strong_ordering __v, __cmp_cat::__unspec) noexcept
308 { return __v._M_value <= 0; }
309
310 [[nodiscard]]
311 friend constexpr bool
312 operator>=(strong_ordering __v, __cmp_cat::__unspec) noexcept
313 { return __v._M_value >= 0; }
314
315 [[nodiscard]]
316 friend constexpr bool
317 operator< (__cmp_cat::__unspec, strong_ordering __v) noexcept
318 { return 0 < __v._M_value; }
319
320 [[nodiscard]]
321 friend constexpr bool
322 operator> (__cmp_cat::__unspec, strong_ordering __v) noexcept
323 { return 0 > __v._M_value; }
324
325 [[nodiscard]]
326 friend constexpr bool
327 operator<=(__cmp_cat::__unspec, strong_ordering __v) noexcept
328 { return 0 <= __v._M_value; }
329
330 [[nodiscard]]
331 friend constexpr bool
332 operator>=(__cmp_cat::__unspec, strong_ordering __v) noexcept
333 { return 0 >= __v._M_value; }
334
335 [[nodiscard]]
336 friend constexpr strong_ordering
337 operator<=>(strong_ordering __v, __cmp_cat::__unspec) noexcept
338 { return __v; }
339
340 [[nodiscard]]
341 friend constexpr strong_ordering
342 operator<=>(__cmp_cat::__unspec, strong_ordering __v) noexcept
343 { return strong_ordering(__cmp_cat::_Ord(-__v._M_value)); }
344 };
345
346 // valid values' definitions
347 inline constexpr strong_ordering
348 strong_ordering::less(__cmp_cat::_Ord::less);
349
350 inline constexpr strong_ordering
351 strong_ordering::equal(__cmp_cat::_Ord::equivalent);
352
353 inline constexpr strong_ordering
354 strong_ordering::equivalent(__cmp_cat::_Ord::equivalent);
355
356 inline constexpr strong_ordering
357 strong_ordering::greater(__cmp_cat::_Ord::greater);
358
359
360 // named comparison functions
361 [[nodiscard]]
362 constexpr bool
363 is_eq(partial_ordering __cmp) noexcept
364 { return __cmp == 0; }
365
366 [[nodiscard]]
367 constexpr bool
368 is_neq(partial_ordering __cmp) noexcept
369 { return __cmp != 0; }
370
371 [[nodiscard]]
372 constexpr bool
373 is_lt (partial_ordering __cmp) noexcept
374 { return __cmp < 0; }
375
376 [[nodiscard]]
377 constexpr bool
378 is_lteq(partial_ordering __cmp) noexcept
379 { return __cmp <= 0; }
380
381 [[nodiscard]]
382 constexpr bool
383 is_gt (partial_ordering __cmp) noexcept
384 { return __cmp > 0; }
385
386 [[nodiscard]]
387 constexpr bool
388 is_gteq(partial_ordering __cmp) noexcept
389 { return __cmp >= 0; }
390
391 namespace __detail
392 {
393 template<typename _Tp>
394 inline constexpr unsigned __cmp_cat_id = 1;
395 template<>
396 inline constexpr unsigned __cmp_cat_id<partial_ordering> = 2;
397 template<>
398 inline constexpr unsigned __cmp_cat_id<weak_ordering> = 4;
399 template<>
400 inline constexpr unsigned __cmp_cat_id<strong_ordering> = 8;
401
402 template<typename... _Ts>
403 constexpr auto __common_cmp_cat()
404 {
405 constexpr unsigned __cats = (__cmp_cat_id<_Ts> | ...);
406 // If any Ti is not a comparison category type, U is void.
407 if constexpr (__cats & 1)
408 return;
409 // Otherwise, if at least one Ti is std::partial_ordering,
410 // U is std::partial_ordering.
411 else if constexpr (bool(__cats & __cmp_cat_id<partial_ordering>))
412 return partial_ordering::equivalent;
413 // Otherwise, if at least one Ti is std::weak_ordering,
414 // U is std::weak_ordering.
415 else if constexpr (bool(__cats & __cmp_cat_id<weak_ordering>))
416 return weak_ordering::equivalent;
417 // Otherwise, U is std::strong_ordering.
418 else
419 return strong_ordering::equivalent;
420 }
421 } // namespace __detail
422
423 // [cmp.common], common comparison category type
424 template<typename... _Ts>
425 struct common_comparison_category
426 {
427 using type = decltype(__detail::__common_cmp_cat<_Ts...>());
428 };
429
430 // Partial specializations for one and zero argument cases.
431
432 template<typename _Tp>
433 struct common_comparison_category<_Tp>
434 { using type = void; };
435
436 template<>
437 struct common_comparison_category<partial_ordering>
438 { using type = partial_ordering; };
439
440 template<>
441 struct common_comparison_category<weak_ordering>
442 { using type = weak_ordering; };
443
444 template<>
445 struct common_comparison_category<strong_ordering>
446 { using type = strong_ordering; };
447
448 template<>
449 struct common_comparison_category<>
450 { using type = strong_ordering; };
451
452 template<typename... _Ts>
453 using common_comparison_category_t
454 = typename common_comparison_category<_Ts...>::type;
455
456#if __cpp_lib_three_way_comparison >= 201907L
457 // C++ >= 20 && impl_3way_comparison >= 201907 && lib_concepts
458 namespace __detail
459 {
460 template<typename _Tp, typename _Cat>
461 concept __compares_as
462 = same_as<common_comparison_category_t<_Tp, _Cat>, _Cat>;
463 } // namespace __detail
464
465 // [cmp.concept], concept three_way_comparable
466 template<typename _Tp, typename _Cat = partial_ordering>
467 concept three_way_comparable
468 = __detail::__weakly_eq_cmp_with<_Tp, _Tp>
469 && __detail::__partially_ordered_with<_Tp, _Tp>
470 && requires(const remove_reference_t<_Tp>& __a,
471 const remove_reference_t<_Tp>& __b)
472 {
473 { __a <=> __b } -> __detail::__compares_as<_Cat>;
474 };
475
476 template<typename _Tp, typename _Up, typename _Cat = partial_ordering>
477 concept three_way_comparable_with
478 = three_way_comparable<_Tp, _Cat>
479 && three_way_comparable<_Up, _Cat>
480 && common_reference_with<const remove_reference_t<_Tp>&,
481 const remove_reference_t<_Up>&>
482 && three_way_comparable<
483 common_reference_t<const remove_reference_t<_Tp>&,
484 const remove_reference_t<_Up>&>, _Cat>
485 && __detail::__weakly_eq_cmp_with<_Tp, _Up>
486 && __detail::__partially_ordered_with<_Tp, _Up>
487 && requires(const remove_reference_t<_Tp>& __t,
488 const remove_reference_t<_Up>& __u)
489 {
490 { __t <=> __u } -> __detail::__compares_as<_Cat>;
491 { __u <=> __t } -> __detail::__compares_as<_Cat>;
492 };
493
494 namespace __detail
495 {
496 template<typename _Tp, typename _Up>
497 using __cmp3way_res_t
498 = decltype(std::declval<_Tp>() <=> std::declval<_Up>());
499
500 // Implementation of std::compare_three_way_result.
501 // It is undefined for a program to add specializations of
502 // std::compare_three_way_result, so the std::compare_three_way_result_t
503 // alias ignores std::compare_three_way_result and uses
504 // __detail::__cmp3way_res_impl directly instead.
505 template<typename _Tp, typename _Up>
506 struct __cmp3way_res_impl
507 { };
508
509 template<typename _Tp, typename _Up>
510 requires requires { typename __cmp3way_res_t<__cref<_Tp>, __cref<_Up>>; }
511 struct __cmp3way_res_impl<_Tp, _Up>
512 {
513 using type = __cmp3way_res_t<__cref<_Tp>, __cref<_Up>>;
514 };
515 } // namespace __detail
516
517 /// [cmp.result], result of three-way comparison
518 template<typename _Tp, typename _Up = _Tp>
519 struct compare_three_way_result
520 : __detail::__cmp3way_res_impl<_Tp, _Up>
521 { };
522
523 /// [cmp.result], result of three-way comparison
524 template<typename _Tp, typename _Up = _Tp>
525 using compare_three_way_result_t
526 = typename __detail::__cmp3way_res_impl<_Tp, _Up>::type;
527
528 namespace __detail
529 {
530 // BUILTIN-PTR-THREE-WAY(T, U)
531 // This determines whether t <=> u results in a call to a built-in
532 // operator<=> comparing pointers. It doesn't work for function pointers
533 // (PR 93628).
534 template<typename _Tp, typename _Up>
535 concept __3way_builtin_ptr_cmp
536 = requires(_Tp&& __t, _Up&& __u)
537 { static_cast<_Tp&&>(__t) <=> static_cast<_Up&&>(__u); }
538 && convertible_to<_Tp, const volatile void*>
539 && convertible_to<_Up, const volatile void*>
540 && __not_overloaded_spaceship<_Tp, _Up>;
541 } // namespace __detail
542
543 // _GLIBCXX_RESOLVE_LIB_DEFECTS
544 // 3530 BUILTIN-PTR-MEOW should not opt the type out of syntactic checks
545
546 // [cmp.object], typename compare_three_way
547 struct compare_three_way
548 {
549 template<typename _Tp, typename _Up>
550 requires three_way_comparable_with<_Tp, _Up>
551 constexpr auto
552 operator() [[nodiscard]] (_Tp&& __t, _Up&& __u) const
553 noexcept(noexcept(std::declval<_Tp>() <=> std::declval<_Up>()))
554 {
555 if constexpr (__detail::__3way_builtin_ptr_cmp<_Tp, _Up>)
556 {
557 auto __pt = static_cast<const volatile void*>(__t);
558 auto __pu = static_cast<const volatile void*>(__u);
559 if (std::__is_constant_evaluated())
560 return __pt <=> __pu;
561 auto __it = reinterpret_cast<__UINTPTR_TYPE__>(__pt);
562 auto __iu = reinterpret_cast<__UINTPTR_TYPE__>(__pu);
563 return __it <=> __iu;
564 }
565 else
566 return static_cast<_Tp&&>(__t) <=> static_cast<_Up&&>(__u);
567 }
568
569 using is_transparent = void;
570 };
571
572 /// @cond undocumented
573 // Namespace for helpers for the <compare> customization points.
574 namespace __compare
575 {
576 template<floating_point _Tp>
577 constexpr weak_ordering
578 __fp_weak_ordering(_Tp __e, _Tp __f)
579 {
580 // Returns an integer with the same sign as the argument, and magnitude
581 // indicating the classification: zero=1 subnorm=2 norm=3 inf=4 nan=5
582 auto __cat = [](_Tp __fp) -> int {
583 const int __sign = __builtin_signbit(__fp) ? -1 : 1;
584 if (__builtin_isnormal(__fp))
585 return (__fp == 0 ? 1 : 3) * __sign;
586 if (__builtin_isnan(__fp))
587 return 5 * __sign;
588 if (int __inf = __builtin_isinf_sign(__fp))
589 return 4 * __inf;
590 return 2 * __sign;
591 };
592
593 auto __po = __e <=> __f;
594 if (is_lt(__po))
595 return weak_ordering::less;
596 else if (is_gt(__po))
597 return weak_ordering::greater;
598 else if (__po == partial_ordering::equivalent)
599 return weak_ordering::equivalent;
600 else // unordered, at least one argument is NaN
601 {
602 // return -1 for negative nan, +1 for positive nan, 0 otherwise.
603 auto __isnan_sign = [](_Tp __fp) -> int {
604 return __builtin_isnan(__fp)
605 ? __builtin_signbit(__fp) ? -1 : 1
606 : 0;
607 };
608 auto __ord = __isnan_sign(__e) <=> __isnan_sign(__f);
609 if (is_eq(__ord))
610 return weak_ordering::equivalent;
611 else if (is_lt(__ord))
612 return weak_ordering::less;
613 else
614 return weak_ordering::greater;
615 }
616 }
617
618 void strong_order() = delete;
619
620 template<typename _Tp, typename _Up>
621 concept __adl_strong = requires(_Tp&& __t, _Up&& __u)
622 {
623 strong_ordering(strong_order(static_cast<_Tp&&>(__t),
624 static_cast<_Up&&>(__u)));
625 };
626
627 void weak_order() = delete;
628
629 template<typename _Tp, typename _Up>
630 concept __adl_weak = requires(_Tp&& __t, _Up&& __u)
631 {
632 weak_ordering(weak_order(static_cast<_Tp&&>(__t),
633 static_cast<_Up&&>(__u)));
634 };
635
636 void partial_order() = delete;
637
638 template<typename _Tp, typename _Up>
639 concept __adl_partial = requires(_Tp&& __t, _Up&& __u)
640 {
641 partial_ordering(partial_order(static_cast<_Tp&&>(__t),
642 static_cast<_Up&&>(__u)));
643 };
644
645 template<typename _Ord, typename _Tp, typename _Up>
646 concept __cmp3way = requires(_Tp&& __t, _Up&& __u, compare_three_way __c)
647 {
648 _Ord(__c(static_cast<_Tp&&>(__t), static_cast<_Up&&>(__u)));
649 };
650
651 template<typename _Tp, typename _Up>
652 concept __strongly_ordered
653 = __adl_strong<_Tp, _Up>
654 || floating_point<remove_reference_t<_Tp>>
655 || __cmp3way<strong_ordering, _Tp, _Up>;
656
657 template<typename _Tp, typename _Up>
658 concept __decayed_same_as = same_as<decay_t<_Tp>, decay_t<_Up>>;
659
660 class _Strong_order
661 {
662 template<typename _Tp, typename _Up>
663 static constexpr bool
664 _S_noexcept()
665 {
666 if constexpr (floating_point<decay_t<_Tp>>)
667 return true;
668 else if constexpr (__adl_strong<_Tp, _Up>)
669 return noexcept(strong_ordering(strong_order(std::declval<_Tp>(),
670 std::declval<_Up>())));
671 else if constexpr (__cmp3way<strong_ordering, _Tp, _Up>)
672 return noexcept(compare_three_way()(std::declval<_Tp>(),
673 std::declval<_Up>()));
674 }
675
676 friend class _Weak_order;
677 friend class _Strong_fallback;
678
679 // Names for the supported floating-point representations.
680 enum class _Fp_fmt
681 {
682 _Binary16, _Binary32, _Binary64, _Binary128, // IEEE
683 _X86_80bit, // x86 80-bit extended precision
684 _M68k_80bit, // m68k 80-bit extended precision
685 _Dbldbl, // IBM 128-bit double-double
686 _Bfloat16, // std::bfloat16_t
687 };
688
689#ifndef __cpp_using_enum
690 // XXX Remove these once 'using enum' support is ubiquitous.
691 static constexpr _Fp_fmt _Binary16 = _Fp_fmt::_Binary16;
692 static constexpr _Fp_fmt _Binary32 = _Fp_fmt::_Binary32;
693 static constexpr _Fp_fmt _Binary64 = _Fp_fmt::_Binary64;
694 static constexpr _Fp_fmt _Binary128 = _Fp_fmt::_Binary128;
695 static constexpr _Fp_fmt _X86_80bit = _Fp_fmt::_X86_80bit;
696 static constexpr _Fp_fmt _M68k_80bit = _Fp_fmt::_M68k_80bit;
697 static constexpr _Fp_fmt _Dbldbl = _Fp_fmt::_Dbldbl;
698 static constexpr _Fp_fmt _Bfloat16 = _Fp_fmt::_Bfloat16;
699#endif
700
701 // Identify the format used by a floating-point type.
702 template<typename _Tp>
703 static consteval _Fp_fmt
704 _S_fp_fmt() noexcept
705 {
706#ifdef __cpp_using_enum
707 using enum _Fp_fmt;
708#endif
709
710 // Identify these formats first, then assume anything else is IEEE.
711 // N.B. ARM __fp16 alternative format can be handled as binary16.
712
713#ifdef __LONG_DOUBLE_IBM128__
714 if constexpr (__is_same(_Tp, long double))
715 return _Dbldbl;
716#elif defined __LONG_DOUBLE_IEEE128__ && defined __SIZEOF_IBM128__
717 if constexpr (__is_same(_Tp, __ibm128))
718 return _Dbldbl;
719#endif
720
721#if __LDBL_MANT_DIG__ == 64
722 if constexpr (__is_same(_Tp, long double))
723 return __LDBL_MIN_EXP__ == -16381 ? _X86_80bit : _M68k_80bit;
724#endif
725#ifdef __SIZEOF_FLOAT80__
726 if constexpr (__is_same(_Tp, __float80))
727 return _X86_80bit;
728#endif
729#ifdef __STDCPP_BFLOAT16_T__
730 if constexpr (__is_same(_Tp, decltype(0.0bf16)))
731 return _Bfloat16;
732#endif
733
734 constexpr int __width = sizeof(_Tp) * __CHAR_BIT__;
735
736 if constexpr (__width == 16) // IEEE binary16 (or ARM fp16).
737 return _Binary16;
738 else if constexpr (__width == 32) // IEEE binary32
739 return _Binary32;
740 else if constexpr (__width == 64) // IEEE binary64
741 return _Binary64;
742 else if constexpr (__width == 128) // IEEE binary128
743 return _Binary128;
744 }
745
746 // So we don't need to include <stdint.h> and pollute the namespace.
747 using int64_t = __INT64_TYPE__;
748 using int32_t = __INT32_TYPE__;
749 using int16_t = __INT16_TYPE__;
750 using uint64_t = __UINT64_TYPE__;
751 using uint16_t = __UINT16_TYPE__;
752
753 // Used to unpack floating-point types that do not fit into an integer.
754 template<typename _Tp>
755 struct _Int
756 {
757#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
758 uint64_t _M_lo;
759 _Tp _M_hi;
760#else
761 _Tp _M_hi;
762 uint64_t _M_lo;
763#endif
764
765 constexpr explicit
766 _Int(_Tp __hi, uint64_t __lo) noexcept : _M_hi(__hi)
767 { _M_lo = __lo; }
768
769 constexpr explicit
770 _Int(uint64_t __lo) noexcept : _M_hi(0)
771 { _M_lo = __lo; }
772
773 constexpr bool operator==(const _Int&) const = default;
774
775#if defined __hppa__ || (defined __mips__ && !defined __mips_nan2008)
776 consteval _Int
777 operator<<(int __n) const noexcept
778 {
779 // XXX this assumes n >= 64, which is true for the use below.
780 return _Int(static_cast<_Tp>(_M_lo << (__n - 64)), 0);
781 }
782#endif
783
784 constexpr _Int&
785 operator^=(const _Int& __rhs) noexcept
786 {
787 _M_hi ^= __rhs._M_hi;
788 _M_lo ^= __rhs._M_lo;
789 return *this;
790 }
791
792 constexpr strong_ordering
793 operator<=>(const _Int& __rhs) const noexcept
794 {
795 strong_ordering __cmp = _M_hi <=> __rhs._M_hi;
796 if (__cmp != strong_ordering::equal)
797 return __cmp;
798 return _M_lo <=> __rhs._M_lo;
799 }
800 };
801
802 template<typename _Tp>
803 static constexpr _Tp
804 _S_compl(_Tp __t) noexcept
805 {
806 constexpr int __width = sizeof(_Tp) * __CHAR_BIT__;
807 // Sign extend to get all ones or all zeros.
808 make_unsigned_t<_Tp> __sign = __t >> (__width - 1);
809 // If the sign bit was set, this flips all bits below it.
810 // This converts ones' complement to two's complement.
811 return __t ^ (__sign >> 1);
812 }
813
814 // As above but works on both parts of _Int<T>.
815 template<typename _Tp>
816 static constexpr _Int<_Tp>
817 _S_compl(_Int<_Tp> __t) noexcept
818 {
819 constexpr int __width = sizeof(_Tp) * __CHAR_BIT__;
820 make_unsigned_t<_Tp> __sign = __t._M_hi >> (__width - 1);
821 __t._M_hi ^= (__sign >> 1 );
822 uint64_t __sign64 = (_Tp)__sign;
823 __t._M_lo ^= __sign64;
824 return __t;
825 }
826
827 // Bit-cast a floating-point value to an unsigned integer.
828 template<typename _Tp>
829 constexpr static auto
830 _S_fp_bits(_Tp __val) noexcept
831 {
832 if constexpr (sizeof(_Tp) == sizeof(int64_t))
833 return __builtin_bit_cast(int64_t, __val);
834 else if constexpr (sizeof(_Tp) == sizeof(int32_t))
835 return __builtin_bit_cast(int32_t, __val);
836 else if constexpr (sizeof(_Tp) == sizeof(int16_t))
837 return __builtin_bit_cast(int16_t, __val);
838 else
839 {
840#ifdef __cpp_using_enum
841 using enum _Fp_fmt;
842#endif
843 constexpr auto __fmt = _S_fp_fmt<_Tp>();
844 if constexpr (__fmt == _X86_80bit)
845 {
846 if constexpr (sizeof(_Tp) == 3 * sizeof(int32_t))
847 {
848 auto __ival = __builtin_bit_cast(_Int<int32_t>, __val);
849 return _Int<int16_t>(__ival._M_hi, __ival._M_lo);
850 }
851 else
852 {
853 auto __ival = __builtin_bit_cast(_Int<int64_t>, __val);
854 return _Int<int16_t>(__ival._M_hi, __ival._M_lo);
855 }
856 }
857 else if constexpr (__fmt == _M68k_80bit)
858 {
859 auto __ival = __builtin_bit_cast(_Int<int32_t>, __val);
860 return _Int<int16_t>(__ival._M_hi >> 16, __ival._M_lo);
861 }
862 else if constexpr (sizeof(_Tp) == 2 * sizeof(int64_t))
863 {
864#if __SIZEOF_INT128__
865 return __builtin_bit_cast(__int128, __val);
866#else
867 return __builtin_bit_cast(_Int<int64_t>, __val);
868#endif
869 }
870 else
871 static_assert(sizeof(_Tp) == sizeof(int64_t),
872 "unsupported floating-point type");
873 }
874 }
875
876 template<typename _Tp>
877 static constexpr strong_ordering
878 _S_fp_cmp(_Tp __x, _Tp __y) noexcept
879 {
880#ifdef __vax__
881 if (__builtin_isnan(__x) || __builtin_isnan(__y))
882 {
883 int __ix = (bool) __builtin_isnan(__x);
884 int __iy = (bool) __builtin_isnan(__y);
885 __ix *= __builtin_signbit(__x) ? -1 : 1;
886 __iy *= __builtin_signbit(__y) ? -1 : 1;
887 return __ix <=> __iy;
888 }
889 else
890 return __builtin_bit_cast(strong_ordering, __x <=> __y);
891#endif
892
893 auto __ix = _S_fp_bits(__x);
894 auto __iy = _S_fp_bits(__y);
895
896 if (__ix == __iy)
897 return strong_ordering::equal; // All bits are equal, we're done.
898
899#ifdef __cpp_using_enum
900 using enum _Fp_fmt;
901#endif
902 constexpr auto __fmt = _S_fp_fmt<_Tp>();
903
904 if constexpr (__fmt == _Dbldbl) // double-double
905 {
906 // Unpack the double-double into two parts.
907 // We never inspect the low double as a double, cast to integer.
908 struct _Unpacked { double _M_hi; int64_t _M_lo; };
909 auto __x2 = __builtin_bit_cast(_Unpacked, __x);
910 auto __y2 = __builtin_bit_cast(_Unpacked, __y);
911
912 // Compare the high doubles first and use result if unequal.
913 auto __cmp = _S_fp_cmp(__x2._M_hi, __y2._M_hi);
914 if (__cmp != strong_ordering::equal)
915 return __cmp;
916
917 // For NaN the low double is unused, so if the high doubles
918 // are the same NaN, we don't need to compare the low doubles.
919 if (__builtin_isnan(__x2._M_hi))
920 return strong_ordering::equal;
921 // Similarly, if the low doubles are +zero or -zero (which is
922 // true for all infinities and some other values), we're done.
923 if (((__x2._M_lo | __y2._M_lo) & 0x7fffffffffffffffULL) == 0)
924 return strong_ordering::equal;
925
926 // Otherwise, compare the low parts.
927 return _S_compl(__x2._M_lo) <=> _S_compl(__y2._M_lo);
928 }
929 else
930 {
931 if constexpr (__fmt == _M68k_80bit)
932 {
933 // For m68k the MSB of the significand is ignored for the
934 // greatest exponent, so either 0 or 1 is valid there.
935 // Set it before comparing, so that we never have 0 there.
936 constexpr uint16_t __maxexp = 0x7fff;
937 if ((__ix._M_hi & __maxexp) == __maxexp)
938 __ix._M_lo |= 1ull << 63;
939 if ((__iy._M_hi & __maxexp) == __maxexp)
940 __iy._M_lo |= 1ull << 63;
941 }
942 else
943 {
944#if defined __hppa__ || (defined __mips__ && !defined __mips_nan2008)
945 // IEEE 754-1985 allowed the meaning of the quiet/signaling
946 // bit to be reversed. Flip that to give desired ordering.
947 if (__builtin_isnan(__x) && __builtin_isnan(__y))
948 {
949 using _Int = decltype(__ix);
950
951 constexpr int __nantype = __fmt == _Binary32 ? 22
952 : __fmt == _Binary64 ? 51
953 : __fmt == _Binary128 ? 111
954 : -1;
955 constexpr _Int __bit = _Int(1) << __nantype;
956 __ix ^= __bit;
957 __iy ^= __bit;
958 }
959#endif
960 }
961 return _S_compl(__ix) <=> _S_compl(__iy);
962 }
963 }
964
965 public:
966 template<typename _Tp, __decayed_same_as<_Tp> _Up>
967 requires __strongly_ordered<_Tp, _Up>
968 constexpr strong_ordering
969 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
970 noexcept(_S_noexcept<_Tp, _Up>())
971 {
972 if constexpr (floating_point<decay_t<_Tp>>)
973 return _S_fp_cmp(__e, __f);
974 else if constexpr (__adl_strong<_Tp, _Up>)
975 return strong_ordering(strong_order(static_cast<_Tp&&>(__e),
976 static_cast<_Up&&>(__f)));
977 else if constexpr (__cmp3way<strong_ordering, _Tp, _Up>)
978 return compare_three_way()(static_cast<_Tp&&>(__e),
979 static_cast<_Up&&>(__f));
980 }
981 };
982
983 template<typename _Tp, typename _Up>
984 concept __weakly_ordered
985 = floating_point<remove_reference_t<_Tp>>
986 || __adl_weak<_Tp, _Up>
987 || __cmp3way<weak_ordering, _Tp, _Up>
988 || __strongly_ordered<_Tp, _Up>;
989
990 class _Weak_order
991 {
992 template<typename _Tp, typename _Up>
993 static constexpr bool
994 _S_noexcept()
995 {
996 if constexpr (floating_point<decay_t<_Tp>>)
997 return true;
998 else if constexpr (__adl_weak<_Tp, _Up>)
999 return noexcept(weak_ordering(weak_order(std::declval<_Tp>(),
1000 std::declval<_Up>())));
1001 else if constexpr (__cmp3way<weak_ordering, _Tp, _Up>)
1002 return noexcept(compare_three_way()(std::declval<_Tp>(),
1003 std::declval<_Up>()));
1004 else if constexpr (__strongly_ordered<_Tp, _Up>)
1005 return _Strong_order::_S_noexcept<_Tp, _Up>();
1006 }
1007
1008 friend class _Partial_order;
1009 friend class _Weak_fallback;
1010
1011 public:
1012 template<typename _Tp, __decayed_same_as<_Tp> _Up>
1013 requires __weakly_ordered<_Tp, _Up>
1014 constexpr weak_ordering
1015 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1016 noexcept(_S_noexcept<_Tp, _Up>())
1017 {
1018 if constexpr (floating_point<decay_t<_Tp>>)
1019 return __compare::__fp_weak_ordering(__e, __f);
1020 else if constexpr (__adl_weak<_Tp, _Up>)
1021 return weak_ordering(weak_order(static_cast<_Tp&&>(__e),
1022 static_cast<_Up&&>(__f)));
1023 else if constexpr (__cmp3way<weak_ordering, _Tp, _Up>)
1024 return compare_three_way()(static_cast<_Tp&&>(__e),
1025 static_cast<_Up&&>(__f));
1026 else if constexpr (__strongly_ordered<_Tp, _Up>)
1027 return _Strong_order{}(static_cast<_Tp&&>(__e),
1028 static_cast<_Up&&>(__f));
1029 }
1030 };
1031
1032 template<typename _Tp, typename _Up>
1033 concept __partially_ordered
1034 = __adl_partial<_Tp, _Up>
1035 || __cmp3way<partial_ordering, _Tp, _Up>
1036 || __weakly_ordered<_Tp, _Up>;
1037
1038 class _Partial_order
1039 {
1040 template<typename _Tp, typename _Up>
1041 static constexpr bool
1042 _S_noexcept()
1043 {
1044 if constexpr (__adl_partial<_Tp, _Up>)
1045 return noexcept(partial_ordering(partial_order(std::declval<_Tp>(),
1046 std::declval<_Up>())));
1047 else if constexpr (__cmp3way<partial_ordering, _Tp, _Up>)
1048 return noexcept(compare_three_way()(std::declval<_Tp>(),
1049 std::declval<_Up>()));
1050 else if constexpr (__weakly_ordered<_Tp, _Up>)
1051 return _Weak_order::_S_noexcept<_Tp, _Up>();
1052 }
1053
1054 friend class _Partial_fallback;
1055
1056 public:
1057 template<typename _Tp, __decayed_same_as<_Tp> _Up>
1058 requires __partially_ordered<_Tp, _Up>
1059 constexpr partial_ordering
1060 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1061 noexcept(_S_noexcept<_Tp, _Up>())
1062 {
1063 if constexpr (__adl_partial<_Tp, _Up>)
1064 return partial_ordering(partial_order(static_cast<_Tp&&>(__e),
1065 static_cast<_Up&&>(__f)));
1066 else if constexpr (__cmp3way<partial_ordering, _Tp, _Up>)
1067 return compare_three_way()(static_cast<_Tp&&>(__e),
1068 static_cast<_Up&&>(__f));
1069 else if constexpr (__weakly_ordered<_Tp, _Up>)
1070 return _Weak_order{}(static_cast<_Tp&&>(__e),
1071 static_cast<_Up&&>(__f));
1072 }
1073 };
1074
1075 template<typename _Tp, typename _Up>
1076 concept __op_eq_lt = requires(_Tp&& __t, _Up&& __u)
1077 {
1078 { static_cast<_Tp&&>(__t) == static_cast<_Up&&>(__u) }
1079 -> convertible_to<bool>;
1080 { static_cast<_Tp&&>(__t) < static_cast<_Up&&>(__u) }
1081 -> convertible_to<bool>;
1082 };
1083
1084 class _Strong_fallback
1085 {
1086 template<typename _Tp, typename _Up>
1087 static constexpr bool
1088 _S_noexcept()
1089 {
1090 if constexpr (__strongly_ordered<_Tp, _Up>)
1091 return _Strong_order::_S_noexcept<_Tp, _Up>();
1092 else
1093 return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1094 && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1095 }
1096
1097 public:
1098 template<typename _Tp, __decayed_same_as<_Tp> _Up>
1099 requires __strongly_ordered<_Tp, _Up> || __op_eq_lt<_Tp, _Up>
1100 constexpr strong_ordering
1101 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1102 noexcept(_S_noexcept<_Tp, _Up>())
1103 {
1104 if constexpr (__strongly_ordered<_Tp, _Up>)
1105 return _Strong_order{}(static_cast<_Tp&&>(__e),
1106 static_cast<_Up&&>(__f));
1107 else // __op_eq_lt<_Tp, _Up>
1108 return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1109 ? strong_ordering::equal
1110 : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1111 ? strong_ordering::less
1112 : strong_ordering::greater;
1113 }
1114 };
1115
1116 class _Weak_fallback
1117 {
1118 template<typename _Tp, typename _Up>
1119 static constexpr bool
1120 _S_noexcept()
1121 {
1122 if constexpr (__weakly_ordered<_Tp, _Up>)
1123 return _Weak_order::_S_noexcept<_Tp, _Up>();
1124 else
1125 return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1126 && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1127 }
1128
1129 public:
1130 template<typename _Tp, __decayed_same_as<_Tp> _Up>
1131 requires __weakly_ordered<_Tp, _Up> || __op_eq_lt<_Tp, _Up>
1132 constexpr weak_ordering
1133 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1134 noexcept(_S_noexcept<_Tp, _Up>())
1135 {
1136 if constexpr (__weakly_ordered<_Tp, _Up>)
1137 return _Weak_order{}(static_cast<_Tp&&>(__e),
1138 static_cast<_Up&&>(__f));
1139 else // __op_eq_lt<_Tp, _Up>
1140 return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1141 ? weak_ordering::equivalent
1142 : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1143 ? weak_ordering::less
1144 : weak_ordering::greater;
1145 }
1146 };
1147
1148 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1149 // 3465. compare_partial_order_fallback requires F < E
1150 template<typename _Tp, typename _Up>
1151 concept __op_eq_lt_lt = __op_eq_lt<_Tp, _Up>
1152 && requires(_Tp&& __t, _Up&& __u)
1153 {
1154 { static_cast<_Up&&>(__u) < static_cast<_Tp&&>(__t) }
1155 -> convertible_to<bool>;
1156 };
1157
1158 class _Partial_fallback
1159 {
1160 template<typename _Tp, typename _Up>
1161 static constexpr bool
1162 _S_noexcept()
1163 {
1164 if constexpr (__partially_ordered<_Tp, _Up>)
1165 return _Partial_order::_S_noexcept<_Tp, _Up>();
1166 else
1167 return noexcept(bool(std::declval<_Tp>() == std::declval<_Up>()))
1168 && noexcept(bool(std::declval<_Tp>() < std::declval<_Up>()));
1169 }
1170
1171 public:
1172 template<typename _Tp, __decayed_same_as<_Tp> _Up>
1173 requires __partially_ordered<_Tp, _Up> || __op_eq_lt_lt<_Tp, _Up>
1174 constexpr partial_ordering
1175 operator() [[nodiscard]] (_Tp&& __e, _Up&& __f) const
1176 noexcept(_S_noexcept<_Tp, _Up>())
1177 {
1178 if constexpr (__partially_ordered<_Tp, _Up>)
1179 return _Partial_order{}(static_cast<_Tp&&>(__e),
1180 static_cast<_Up&&>(__f));
1181 else // __op_eq_lt_lt<_Tp, _Up>
1182 return static_cast<_Tp&&>(__e) == static_cast<_Up&&>(__f)
1183 ? partial_ordering::equivalent
1184 : static_cast<_Tp&&>(__e) < static_cast<_Up&&>(__f)
1185 ? partial_ordering::less
1186 : static_cast<_Up&&>(__f) < static_cast<_Tp&&>(__e)
1187 ? partial_ordering::greater
1188 : partial_ordering::unordered;
1189 }
1190 };
1191 } // namespace @endcond
1192
1193 // [cmp.alg], comparison algorithms
1194
1195 inline namespace _Cpo
1196 {
1197 inline constexpr __compare::_Strong_order strong_order{};
1198
1199 inline constexpr __compare::_Weak_order weak_order{};
1200
1201 inline constexpr __compare::_Partial_order partial_order{};
1202
1203 inline constexpr __compare::_Strong_fallback
1204 compare_strong_order_fallback{};
1205
1206 inline constexpr __compare::_Weak_fallback
1207 compare_weak_order_fallback{};
1208
1209 inline constexpr __compare::_Partial_fallback
1210 compare_partial_order_fallback{};
1211 }
1212
1213 /// @cond undocumented
1214 namespace __detail
1215 {
1216 // [expos.only.func] synth-three-way
1217 inline constexpr struct _Synth3way
1218 {
1219 template<typename _Tp, typename _Up>
1220 static constexpr bool
1221 _S_noexcept(const _Tp* __t = nullptr, const _Up* __u = nullptr)
1222 {
1223 if constexpr (three_way_comparable_with<_Tp, _Up>)
1224 return noexcept(*__t <=> *__u);
1225 else
1226 return noexcept(*__t < *__u) && noexcept(*__u < *__t);
1227 }
1228
1229 template<typename _Tp, typename _Up>
1230 [[nodiscard]]
1231 constexpr auto
1232 operator()(const _Tp& __t, const _Up& __u) const
1233 noexcept(_S_noexcept<_Tp, _Up>())
1234 requires requires
1235 {
1236 { __t < __u } -> __boolean_testable;
1237 { __u < __t } -> __boolean_testable;
1238 }
1239 {
1240 if constexpr (three_way_comparable_with<_Tp, _Up>)
1241 return __t <=> __u;
1242 else
1243 {
1244 if (__t < __u)
1245 return weak_ordering::less;
1246 else if (__u < __t)
1247 return weak_ordering::greater;
1248 else
1249 return weak_ordering::equivalent;
1250 }
1251 }
1252 } __synth3way = {};
1253
1254 // [expos.only.func] synth-three-way-result
1255 template<typename _Tp, typename _Up = _Tp>
1256 using __synth3way_t
1257 = decltype(__detail::__synth3way(std::declval<_Tp&>(),
1258 std::declval<_Up&>()));
1259 } // namespace __detail
1260 /// @endcond
1261#endif // __cpp_lib_three_way_comparison >= 201907L
1262} // namespace std
1263
1264#pragma GCC diagnostic pop
1265
1266#endif // C++20
1267
1268#endif // _COMPARE
1269