1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H
10#define _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H
11
12#include <__assert>
13#include <__config>
14#include <__type_traits/conjunction.h>
15#include <__type_traits/desugars_to.h>
16#include <__type_traits/enable_if.h>
17#include <__utility/default_three_way_comparator.h>
18
19#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
20# pragma GCC system_header
21#endif
22
23// This file implements a __lazy_synth_three_way_comparator, which tries to build an efficient three way comparison from
24// a binary comparator. That is done in multiple steps:
25// 1) Check whether the comparator desugars to a less-than operator
26// If that is the case, check whether there exists a specialization of `__default_three_way_comparator`, which
27// can be specialized to implement a three way comparator for the specific types.
28// 2) Fall back to doing a lazy less than/greater than comparison
29
30_LIBCPP_BEGIN_NAMESPACE_STD
31
32template <class _Comparator, class _LHS, class _RHS>
33struct __lazy_compare_result {
34 const _Comparator& __comp_;
35 const _LHS& __lhs_;
36 const _RHS& __rhs_;
37
38 _LIBCPP_HIDE_FROM_ABI
39 __lazy_compare_result(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp,
40 _LIBCPP_CTOR_LIFETIMEBOUND const _LHS& __lhs,
41 _LIBCPP_CTOR_LIFETIMEBOUND const _RHS& __rhs)
42 : __comp_(__comp), __lhs_(__lhs), __rhs_(__rhs) {}
43
44 _LIBCPP_HIDE_FROM_ABI bool __less() const {
45 bool __result = __comp_(__lhs_, __rhs_);
46 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__result ? !static_cast<bool>(__comp_(__rhs_, __lhs_)) : true,
47 "Comparator does not induce a strict weak ordering");
48 return __result;
49 }
50
51 _LIBCPP_HIDE_FROM_ABI bool __greater() const {
52 bool __result = __comp_(__rhs_, __lhs_);
53 _LIBCPP_ASSERT_SEMANTIC_REQUIREMENT(__result ? !static_cast<bool>(__comp_(__lhs_, __rhs_)) : true,
54 "Comparator does not induce a strict weak ordering");
55 return __result;
56 }
57};
58
59// This class provides three way comparison between _LHS and _RHS as efficiently as possible. This can be specialized if
60// a comparator only compares part of the object, potentially allowing an efficient three way comparison between the
61// subobjects. The specialization should use the __lazy_synth_three_way_comparator for the subobjects to achieve this.
62template <class _Comparator, class _LHS, class _RHS, class = void>
63struct __lazy_synth_three_way_comparator {
64 const _Comparator& __comp_;
65
66 _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator& __comp)
67 : __comp_(__comp) {}
68
69 _LIBCPP_HIDE_FROM_ABI __lazy_compare_result<_Comparator, _LHS, _RHS>
70 operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) const {
71 return __lazy_compare_result<_Comparator, _LHS, _RHS>(__comp_, __lhs, __rhs);
72 }
73};
74
75struct __eager_compare_result {
76 int __res_;
77
78 _LIBCPP_HIDE_FROM_ABI explicit __eager_compare_result(int __res) : __res_(__res) {}
79
80 _LIBCPP_HIDE_FROM_ABI bool __less() const { return __res_ < 0; }
81 _LIBCPP_HIDE_FROM_ABI bool __greater() const { return __res_ > 0; }
82};
83
84template <class _Comparator, class _LHS, class _RHS>
85struct __lazy_synth_three_way_comparator<_Comparator,
86 _LHS,
87 _RHS,
88 __enable_if_t<_And<__desugars_to<__less_tag, _Comparator, _LHS, _RHS>,
89 __has_default_three_way_comparator<_LHS, _RHS> >::value> > {
90 // This lifetimebound annotation is technically incorrect, but other specializations actually capture the lifetime of
91 // the comparator.
92 _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator&) {}
93
94 // Same comment as above.
95 _LIBCPP_HIDE_FROM_ABI static __eager_compare_result
96 operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) {
97 return __eager_compare_result(__default_three_way_comparator<_LHS, _RHS>()(__lhs, __rhs));
98 }
99};
100
101template <class _Comparator, class _LHS, class _RHS>
102struct __lazy_synth_three_way_comparator<_Comparator,
103 _LHS,
104 _RHS,
105 __enable_if_t<_And<__desugars_to<__greater_tag, _Comparator, _LHS, _RHS>,
106 __has_default_three_way_comparator<_LHS, _RHS> >::value> > {
107 // This lifetimebound annotation is technically incorrect, but other specializations actually capture the lifetime of
108 // the comparator.
109 _LIBCPP_HIDE_FROM_ABI __lazy_synth_three_way_comparator(_LIBCPP_CTOR_LIFETIMEBOUND const _Comparator&) {}
110
111 // Same comment as above.
112 _LIBCPP_HIDE_FROM_ABI static __eager_compare_result
113 operator()(_LIBCPP_LIFETIMEBOUND const _LHS& __lhs, _LIBCPP_LIFETIMEBOUND const _RHS& __rhs) {
114 return __eager_compare_result(-__default_three_way_comparator<_LHS, _RHS>()(__lhs, __rhs));
115 }
116};
117
118_LIBCPP_END_NAMESPACE_STD
119
120#endif // _LIBCPP___UTILITY_LAZY_SYNTH_THREE_WAY_COMPARATOR_H