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;
MyTypeMyType29 explicit MyType(int xvalue = 0) : value(xvalue) {}
30 };
31
32 template <int ID1, int ID2>
operator <(MyType<ID1> const & LHS,MyType<ID2> const & RHS)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;
resetCompareBase39 static void reset() {
40 called = 0;
41 }
42 };
43
44 int CompareBase::called = 0;
45
46 template <class ValueType>
47 struct GoodComparator : public CompareBase {
operator ()GoodComparator48 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 {
operator ()TwoWayHomoComparator56 bool operator()(T1 const& lhs, T2 const& rhs) const {
57 ++CompareBase::called;
58 return lhs < rhs;
59 }
60
operator ()TwoWayHomoComparator61 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 {
operator ()OneWayHomoComparator69 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
test_passing()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 {
TagTag135 explicit Tag(int v) : value(v) {}
136 int value;
137 };
138
139 template <class = void>
140 struct FooImp {
FooImpFooImp141 explicit FooImp(int x) : x_(x) {}
142 int x_;
143 };
144
145 template <class T>
operator <(FooImp<T> const & x,Tag<0> y)146 inline bool operator<(FooImp<T> const& x, Tag<0> y) {
147 return x.x_ < y.value;
148 }
149
150 template <class T>
operator <(Tag<0>,FooImp<T> const &)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>
operator <(Tag<1> x,FooImp<T> const & y)157 inline bool operator<(Tag<1> x, FooImp<T> const& y) {
158 return x.value < y.x_;
159 }
160
161 template <class T>
operator <(FooImp<T> const &,Tag<1>)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
test_upper_and_lower_bound()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(std::begin(table), std::end(table), Tag<0>(3));
177 assert(iter == (table + 2));
178 }
179 {
180 Foo* iter = std::upper_bound(std::begin(table), std::end(table), Tag<1>(3));
181 assert(iter == (table + 3));
182 }
183 }
184
185 struct NonConstArgCmp {
operator ()NonConstArgCmp186 bool operator()(int& x, int &y) const {
187 return x < y;
188 }
189 };
190
test_non_const_arg_cmp()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(std::begin(arr), std::end(arr), 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
ValueIteratorValueIterator214 ValueIterator() { }
215
operator *ValueIterator216 reference operator*() { return 0; }
operator ++ValueIterator217 ValueIterator& operator++() { return *this; }
218
operator ==(ValueIterator,ValueIterator)219 friend bool operator==(ValueIterator, ValueIterator) { return true; }
operator !=(ValueIterator,ValueIterator)220 friend bool operator!=(ValueIterator, ValueIterator) { return false; }
221 };
222
test_value_iterator()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
test_value_categories()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
test_constexpr()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
main(int,char **)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