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 // UNSUPPORTED: no-exceptions
10
11 // <algorithm>
12
13 // template <class _Compare> struct __debug_less
14
15 // __debug_less checks that a comparator actually provides a strict-weak ordering.
16
17 struct DebugException {};
18
19 #define _LIBCPP_DEBUG 0
20 #define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : throw ::DebugException())
21
22 #include <algorithm>
23 #include <iterator>
24 #include <cassert>
25
26 #include "test_macros.h"
27
28 template <int ID>
29 struct MyType {
30 int value;
MyTypeMyType31 explicit MyType(int xvalue = 0) : value(xvalue) {}
32 };
33
34 template <int ID1, int ID2>
operator <(MyType<ID1> const & LHS,MyType<ID2> const & RHS)35 bool operator<(MyType<ID1> const& LHS, MyType<ID2> const& RHS) {
36 return LHS.value < RHS.value;
37 }
38
39 struct CompareBase {
40 static int called;
resetCompareBase41 static void reset() {
42 called = 0;
43 }
44 };
45
46 int CompareBase::called = 0;
47
48 template <class ValueType>
49 struct GoodComparator : public CompareBase {
operator ()GoodComparator50 bool operator()(ValueType const& lhs, ValueType const& rhs) const {
51 ++CompareBase::called;
52 return lhs < rhs;
53 }
54 };
55
56 template <class ValueType>
57 struct BadComparator : public CompareBase {
operator ()BadComparator58 bool operator()(ValueType const&, ValueType const&) const {
59 ++CompareBase::called;
60 return true;
61 }
62 };
63
64 template <class T1, class T2>
65 struct TwoWayHomoComparator : public CompareBase {
operator ()TwoWayHomoComparator66 bool operator()(T1 const& lhs, T2 const& rhs) const {
67 ++CompareBase::called;
68 return lhs < rhs;
69 }
70
operator ()TwoWayHomoComparator71 bool operator()(T2 const& lhs, T1 const& rhs) const {
72 ++CompareBase::called;
73 return lhs < rhs;
74 }
75 };
76
77 template <class T1, class T2>
78 struct OneWayHomoComparator : public CompareBase {
operator ()OneWayHomoComparator79 bool operator()(T1 const& lhs, T2 const& rhs) const {
80 ++CompareBase::called;
81 return lhs < rhs;
82 }
83 };
84
85 using std::__debug_less;
86
87 typedef MyType<0> MT0;
88 typedef MyType<1> MT1;
89
test_passing()90 void test_passing() {
91 int& called = CompareBase::called;
92 called = 0;
93 MT0 one(1);
94 MT0 two(2);
95 MT1 three(3);
96 MT1 four(4);
97
98 {
99 typedef GoodComparator<MT0> C;
100 typedef __debug_less<C> D;
101
102 C c;
103 D d(c);
104
105 assert(d(one, two) == true);
106 assert(called == 2);
107 called = 0;
108
109 assert(d(one, one) == false);
110 assert(called == 1);
111 called = 0;
112
113 assert(d(two, one) == false);
114 assert(called == 1);
115 called = 0;
116 }
117 {
118 typedef TwoWayHomoComparator<MT0, MT1> C;
119 typedef __debug_less<C> D;
120 C c;
121 D d(c);
122
123 assert(d(one, three) == true);
124 assert(called == 2);
125 called = 0;
126
127 assert(d(three, one) == false);
128 assert(called == 1);
129 called = 0;
130 }
131 {
132 typedef OneWayHomoComparator<MT0, MT1> C;
133 typedef __debug_less<C> D;
134 C c;
135 D d(c);
136
137 assert(d(one, three) == true);
138 assert(called == 1);
139 called = 0;
140 }
141 }
142
test_failing()143 void test_failing() {
144 int& called = CompareBase::called;
145 called = 0;
146 MT0 one(1);
147 MT0 two(2);
148
149 {
150 typedef BadComparator<MT0> C;
151 typedef __debug_less<C> D;
152 C c;
153 D d(c);
154
155 try {
156 d(one, two);
157 assert(false);
158 } catch (DebugException const&) {
159 }
160
161 assert(called == 2);
162 called = 0;
163 }
164 }
165
166 template <int>
167 struct Tag {
TagTag168 explicit Tag(int v) : value(v) {}
169 int value;
170 };
171
172 template <class = void>
173 struct FooImp {
FooImpFooImp174 explicit FooImp(int x) : x_(x) {}
175 int x_;
176 };
177
178 template <class T>
operator <(FooImp<T> const & x,Tag<0> y)179 inline bool operator<(FooImp<T> const& x, Tag<0> y) {
180 return x.x_ < y.value;
181 }
182
183 template <class T>
operator <(Tag<0>,FooImp<T> const &)184 inline bool operator<(Tag<0>, FooImp<T> const&) {
185 static_assert(sizeof(FooImp<T>) != sizeof(FooImp<T>), "should not be instantiated");
186 return false;
187 }
188
189 template <class T>
operator <(Tag<1> x,FooImp<T> const & y)190 inline bool operator<(Tag<1> x, FooImp<T> const& y) {
191 return x.value < y.x_;
192 }
193
194 template <class T>
operator <(FooImp<T> const &,Tag<1>)195 inline bool operator<(FooImp<T> const&, Tag<1>) {
196 static_assert(sizeof(FooImp<T>) != sizeof(FooImp<T>), "should not be instantiated");
197 return false;
198 }
199
200 typedef FooImp<> Foo;
201
202 // Test that we don't attempt to call the comparator with the arguments reversed
203 // for upper_bound and lower_bound since the comparator or type is not required
204 // to support it, nor does it require the range to have a strict weak ordering.
205 // See llvm.org/PR39458
test_upper_and_lower_bound()206 void test_upper_and_lower_bound() {
207 Foo table[] = {Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)};
208 {
209 Foo* iter = std::lower_bound(std::begin(table), std::end(table), Tag<0>(3));
210 assert(iter == (table + 2));
211 }
212 {
213 Foo* iter = std::upper_bound(std::begin(table), std::end(table), Tag<1>(3));
214 assert(iter == (table + 3));
215 }
216 }
217
218 struct NonConstArgCmp {
operator ()NonConstArgCmp219 bool operator()(int& x, int &y) const {
220 return x < y;
221 }
222 };
223
test_non_const_arg_cmp()224 void test_non_const_arg_cmp() {
225 {
226 NonConstArgCmp cmp;
227 __debug_less<NonConstArgCmp> dcmp(cmp);
228 int x = 0, y = 1;
229 assert(dcmp(x, y));
230 assert(!dcmp(y, x));
231 }
232 {
233 NonConstArgCmp cmp;
234 int arr[] = {5, 4, 3, 2, 1};
235 std::sort(std::begin(arr), std::end(arr), cmp);
236 assert(std::is_sorted(std::begin(arr), std::end(arr)));
237 }
238 }
239
240 struct ValueIterator {
241 typedef std::input_iterator_tag iterator_category;
242 typedef size_t value_type;
243 typedef ptrdiff_t difference_type;
244 typedef size_t reference;
245 typedef size_t* pointer;
246
ValueIteratorValueIterator247 ValueIterator() { }
248
operator *ValueIterator249 reference operator*() { return 0; }
operator ++ValueIterator250 ValueIterator& operator++() { return *this; }
251
operator ==(ValueIterator,ValueIterator)252 friend bool operator==(ValueIterator, ValueIterator) { return true; }
operator !=(ValueIterator,ValueIterator)253 friend bool operator!=(ValueIterator, ValueIterator) { return false; }
254 };
255
test_value_iterator()256 void test_value_iterator() {
257 // Ensure no build failures when iterators return values, not references.
258 assert(0 == std::lexicographical_compare(ValueIterator(), ValueIterator(),
259 ValueIterator(), ValueIterator()));
260 }
261
test_value_categories()262 void test_value_categories() {
263 std::less<int> l;
264 std::__debug_less<std::less<int> > dl(l);
265 int lvalue = 42;
266 const int const_lvalue = 101;
267
268 assert(dl(lvalue, const_lvalue));
269 assert(dl(/*rvalue*/1, lvalue));
270 assert(dl(static_cast<int&&>(1), static_cast<const int&&>(2)));
271 }
272
273 #if TEST_STD_VER > 17
test_constexpr()274 constexpr bool test_constexpr() {
275 std::less<> cmp{};
276 __debug_less<std::less<> > dcmp(cmp);
277 assert(dcmp(1, 2));
278 assert(!dcmp(1, 1));
279 return true;
280 }
281 #endif
282
main(int,char **)283 int main(int, char**) {
284 test_passing();
285 test_failing();
286 test_upper_and_lower_bound();
287 test_non_const_arg_cmp();
288 test_value_iterator();
289 test_value_categories();
290 #if TEST_STD_VER > 17
291 static_assert(test_constexpr(), "");
292 #endif
293 return 0;
294 }
295