1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // UNSUPPORTED: libcpp-no-exceptions
11
12 // <algorithm>
13
14 // template <class _Compare> struct __debug_less
15
16 // __debug_less checks that a comparator actually provides a strict-weak ordering.
17
18 struct DebugException {};
19
20 #define _LIBCPP_DEBUG 0
21 #define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : throw ::DebugException())
22
23 #include <algorithm>
24 #include <cassert>
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 ValueType>
55 struct BadComparator : public CompareBase {
operator ()BadComparator56 bool operator()(ValueType const&, ValueType const&) const {
57 ++CompareBase::called;
58 return true;
59 }
60 };
61
62 template <class T1, class T2>
63 struct TwoWayHomoComparator : public CompareBase {
operator ()TwoWayHomoComparator64 bool operator()(T1 const& lhs, T2 const& rhs) const {
65 ++CompareBase::called;
66 return lhs < rhs;
67 }
68
operator ()TwoWayHomoComparator69 bool operator()(T2 const& lhs, T1 const& rhs) const {
70 ++CompareBase::called;
71 return lhs < rhs;
72 }
73 };
74
75 template <class T1, class T2>
76 struct OneWayHomoComparator : public CompareBase {
operator ()OneWayHomoComparator77 bool operator()(T1 const& lhs, T2 const& rhs) const {
78 ++CompareBase::called;
79 return lhs < rhs;
80 }
81 };
82
83 using std::__debug_less;
84
85 typedef MyType<0> MT0;
86 typedef MyType<1> MT1;
87
test_passing()88 void test_passing() {
89 int& called = CompareBase::called;
90 called = 0;
91 MT0 one(1);
92 MT0 two(2);
93 MT1 three(3);
94 MT1 four(4);
95
96 {
97 typedef GoodComparator<MT0> C;
98 typedef __debug_less<C> D;
99
100 C c;
101 D d(c);
102
103 assert(d(one, two) == true);
104 assert(called == 2);
105 called = 0;
106
107 assert(d(one, one) == false);
108 assert(called == 1);
109 called = 0;
110
111 assert(d(two, one) == false);
112 assert(called == 1);
113 called = 0;
114 }
115 {
116 typedef TwoWayHomoComparator<MT0, MT1> C;
117 typedef __debug_less<C> D;
118 C c;
119 D d(c);
120
121 assert(d(one, three) == true);
122 assert(called == 2);
123 called = 0;
124
125 assert(d(three, one) == false);
126 assert(called == 1);
127 called = 0;
128 }
129 {
130 typedef OneWayHomoComparator<MT0, MT1> C;
131 typedef __debug_less<C> D;
132 C c;
133 D d(c);
134
135 assert(d(one, three) == true);
136 assert(called == 1);
137 called = 0;
138 }
139 }
140
test_failing()141 void test_failing() {
142 int& called = CompareBase::called;
143 called = 0;
144 MT0 one(1);
145 MT0 two(2);
146
147 {
148 typedef BadComparator<MT0> C;
149 typedef __debug_less<C> D;
150 C c;
151 D d(c);
152
153 try {
154 d(one, two);
155 assert(false);
156 } catch (DebugException const&) {
157 }
158
159 assert(called == 2);
160 called = 0;
161 }
162 }
163
164 template <int>
165 struct Tag {
TagTag166 explicit Tag(int v) : value(v) {}
167 int value;
168 };
169
170 template <class = void>
171 struct FooImp {
FooImpFooImp172 explicit FooImp(int x) : x_(x) {}
173 int x_;
174 };
175
176 template <class T>
operator <(FooImp<T> const & x,Tag<0> y)177 inline bool operator<(FooImp<T> const& x, Tag<0> y) {
178 return x.x_ < y.value;
179 }
180
181 template <class T>
operator <(Tag<0>,FooImp<T> const &)182 inline bool operator<(Tag<0>, FooImp<T> const&) {
183 static_assert(sizeof(FooImp<T>) != sizeof(FooImp<T>), "should not be instantiated");
184 }
185
186 template <class T>
operator <(Tag<1> x,FooImp<T> const & y)187 inline bool operator<(Tag<1> x, FooImp<T> const& y) {
188 return x.value < y.x_;
189 }
190
191 template <class T>
operator <(FooImp<T> const &,Tag<1>)192 inline bool operator<(FooImp<T> const&, Tag<1>) {
193 static_assert(sizeof(FooImp<T>) != sizeof(FooImp<T>), "should not be instantiated");
194 }
195
196 typedef FooImp<> Foo;
197
198 // Test that we don't attempt to call the comparator with the arguments reversed
199 // for upper_bound and lower_bound since the comparator or type is not required
200 // to support it, nor does it require the range to have a strict weak ordering.
201 // See llvm.org/PR39458
test_upper_and_lower_bound()202 void test_upper_and_lower_bound() {
203 Foo table[] = {Foo(1), Foo(2), Foo(3), Foo(4), Foo(5)};
204 {
205 Foo* iter = std::lower_bound(std::begin(table), std::end(table), Tag<0>(3));
206 assert(iter == (table + 2));
207 }
208 {
209 Foo* iter = std::upper_bound(std::begin(table), std::end(table), Tag<1>(3));
210 assert(iter == (table + 3));
211 }
212 }
213
main()214 int main() {
215 test_passing();
216 test_failing();
217 test_upper_and_lower_bound();
218 }
219