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
26template <int ID>
27struct MyType {
28 int value;
29 explicit MyType(int xvalue = 0) : value(xvalue) {}
30};
31
32template <int ID1, int ID2>
33bool operator<(MyType<ID1> const& LHS, MyType<ID2> const& RHS) {
34 return LHS.value < RHS.value;
35}
36
37struct CompareBase {
38 static int called;
39 static void reset() {
40 called = 0;
41 }
42};
43
44int CompareBase::called = 0;
45
46template <class ValueType>
47struct GoodComparator : public CompareBase {
48 bool operator()(ValueType const& lhs, ValueType const& rhs) const {
49 ++CompareBase::called;
50 return lhs < rhs;
51 }
52};
53
54template <class T1, class T2>
55struct 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
67template <class T1, class T2>
68struct OneWayHomoComparator : public CompareBase {
69 bool operator()(T1 const& lhs, T2 const& rhs) const {
70 ++CompareBase::called;
71 return lhs < rhs;
72 }
73};
74
75using std::__debug_less;
76
77typedef MyType<0> MT0;
78typedef MyType<1> MT1;
79
80void 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
133template <int>
134struct Tag {
135 explicit Tag(int v) : value(v) {}
136 int value;
137};
138
139template <class = void>
140struct FooImp {
141 explicit FooImp(int x) : x_(x) {}
142 int x_;
143};
144
145template <class T>
146inline bool operator<(FooImp<T> const& x, Tag<0> y) {
147 return x.x_ < y.value;
148}
149
150template <class T>
151inline 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
156template <class T>
157inline bool operator<(Tag<1> x, FooImp<T> const& y) {
158 return x.value < y.x_;
159}
160
161template <class T>
162inline 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
167typedef 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
173void 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
185struct NonConstArgCmp {
186 bool operator()(int& x, int &y) const {
187 return x < y;
188 }
189};
190
191void 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
207struct 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
223void 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
229void 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
241constexpr 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
250int 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

source code of libcxx/test/libcxx/algorithms/debug_less.pass.cpp