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