Debian Codegraph @

llvm-project/llvm/unittests/ADT/STLExtrasTest.cpp

raw
1 //===- STLExtrasTest.cpp - Unit tests for STL extras ----------------------===//
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 #include "llvm/ADT/STLExtras.h"
10 #include "gmock/gmock.h"
11 #include "gtest/gtest.h"
12
13 #include <climits>
14 #include <list>
15 #include <vector>
16
17 using namespace llvm;
18
19 using testing::ElementsAre;
20
21 namespace {
22
23 int f(rank<0>) { return 0; }
24 int f(rank<1>) { return 1; }
25 int f(rank<2>) { return 2; }
26 int f(rank<4>) { return 4; }
27
28 TEST(STLExtrasTest, Rank) {
29 // We shouldn't get ambiguities and should select the overload of the same
30 // rank as the argument.
31 EXPECT_EQ(0, f(rank<0>()));
32 EXPECT_EQ(1, f(rank<1>()));
33 EXPECT_EQ(2, f(rank<2>()));
34
35 // This overload is missing so we end up back at 2.
36 EXPECT_EQ(2, f(rank<3>()));
37
38 // But going past 3 should work fine.
39 EXPECT_EQ(4, f(rank<4>()));
40
41 // And we can even go higher and just fall back to the last overload.
42 EXPECT_EQ(4, f(rank<5>()));
43 EXPECT_EQ(4, f(rank<6>()));
44 }
45
46 TEST(STLExtrasTest, EnumerateLValue) {
47 // Test that a simple LValue can be enumerated and gives correct results with
48 // multiple types, including the empty container.
49 std::vector<char> foo = {'a', 'b', 'c'};
50 typedef std::pair<std::size_t, char> CharPairType;
51 std::vector<CharPairType> CharResults;
52
53 for (auto [index, value] : llvm::enumerate(foo)) {
54 CharResults.emplace_back(index, value);
55 }
56
57 EXPECT_THAT(CharResults,
58 ElementsAre(CharPairType(0u, 'a'), CharPairType(1u, 'b'),
59 CharPairType(2u, 'c')));
60
61 // Test a const range of a different type.
62 typedef std::pair<std::size_t, int> IntPairType;
63 std::vector<IntPairType> IntResults;
64 const std::vector<int> bar = {1, 2, 3};
65 for (auto [index, value] : llvm::enumerate(bar)) {
66 IntResults.emplace_back(index, value);
67 }
68 EXPECT_THAT(IntResults, ElementsAre(IntPairType(0u, 1), IntPairType(1u, 2),
69 IntPairType(2u, 3)));
70
71 // Test an empty range.
72 IntResults.clear();
73 const std::vector<int> baz{};
74 for (auto [index, value] : llvm::enumerate(baz)) {
75 IntResults.emplace_back(index, value);
76 }
77 EXPECT_TRUE(IntResults.empty());
78 }
79
80 TEST(STLExtrasTest, EnumerateModifyLValue) {
81 // Test that you can modify the underlying entries of an lvalue range through
82 // the enumeration iterator.
83 std::vector<char> foo = {'a', 'b', 'c'};
84
85 for (auto X : llvm::enumerate(foo)) {
86 ++X.value();
87 }
88 EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));
89
90 // Also test if this works with structured bindings.
91 foo = {'a', 'b', 'c'};
92
93 for (auto [index, value] : llvm::enumerate(foo)) {
94 ++value;
95 }
96 EXPECT_THAT(foo, ElementsAre('b', 'c', 'd'));
97 }
98
99 TEST(STLExtrasTest, EnumerateRValueRef) {
100 // Test that an rvalue can be enumerated.
101 typedef std::pair<std::size_t, int> PairType;
102 std::vector<PairType> Results;
103
104 auto Enumerator = llvm::enumerate(std::vector<int>{1, 2, 3});
105
106 for (auto X : llvm::enumerate(std::vector<int>{1, 2, 3})) {
107 Results.emplace_back(X.index(), X.value());
108 }
109
110 EXPECT_THAT(Results,
111 ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));
112
113 // Also test if this works with structured bindings.
114 Results.clear();
115
116 for (auto [index, value] : llvm::enumerate(std::vector<int>{1, 2, 3})) {
117 Results.emplace_back(index, value);
118 }
119
120 EXPECT_THAT(Results,
121 ElementsAre(PairType(0u, 1), PairType(1u, 2), PairType(2u, 3)));
122 }
123
124 TEST(STLExtrasTest, EnumerateModifyRValue) {
125 // Test that when enumerating an rvalue, modification still works (even if
126 // this isn't terribly useful, it at least shows that we haven't snuck an
127 // extra const in there somewhere.
128 typedef std::pair<std::size_t, char> PairType;
129 std::vector<PairType> Results;
130
131 for (auto X : llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
132 ++X.value();
133 Results.emplace_back(X.index(), X.value());
134 }
135
136 EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
137 PairType(2u, '4')));
138
139 // Also test if this works with structured bindings.
140 Results.clear();
141
142 for (auto [index, value] :
143 llvm::enumerate(std::vector<char>{'1', '2', '3'})) {
144 ++value;
145 Results.emplace_back(index, value);
146 }
147
148 EXPECT_THAT(Results, ElementsAre(PairType(0u, '2'), PairType(1u, '3'),
149 PairType(2u, '4')));
150 }
151
152 template <bool B> struct CanMove {};
153 template <> struct CanMove<false> {
154 CanMove(CanMove &&) = delete;
155
156 CanMove() = default;
157 CanMove(const CanMove &) = default;
158 };
159
160 template <bool B> struct CanCopy {};
161 template <> struct CanCopy<false> {
162 CanCopy(const CanCopy &) = delete;
163
164 CanCopy() = default;
165 CanCopy(CanCopy &&) = default;
166 };
167
168 template <bool Moveable, bool Copyable>
169 class Counted : CanMove<Moveable>, CanCopy<Copyable> {
170 int &C;
171 int &M;
172 int &D;
173
174 public:
175 explicit Counted(int &C, int &M, int &D) : C(C), M(M), D(D) {}
176 Counted(const Counted &O) : CanCopy<Copyable>(O), C(O.C), M(O.M), D(O.D) {
177 ++C;
178 }
179 Counted(Counted &&O)
180 : CanMove<Moveable>(std::move(O)), C(O.C), M(O.M), D(O.D) {
181 ++M;
182 }
183 ~Counted() { ++D; }
184 };
185
186 template <bool Moveable, bool Copyable>
187 struct Range : Counted<Moveable, Copyable> {
188 using Counted<Moveable, Copyable>::Counted;
189 int *begin() { return nullptr; }
190 int *end() { return nullptr; }
191 };
192
193 TEST(STLExtrasTest, EnumerateLifetimeSemanticsPRValue) {
194 int Copies = 0;
195 int Moves = 0;
196 int Destructors = 0;
197 {
198 auto E = enumerate(Range<true, false>(Copies, Moves, Destructors));
199 (void)E;
200 // Doesn't compile. rvalue ranges must be moveable.
201 // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
202 EXPECT_EQ(0, Copies);
203 EXPECT_EQ(1, Moves);
204 EXPECT_EQ(1, Destructors);
205 }
206 EXPECT_EQ(0, Copies);
207 EXPECT_EQ(1, Moves);
208 EXPECT_EQ(2, Destructors);
209 }
210
211 TEST(STLExtrasTest, EnumerateLifetimeSemanticsRValue) {
212 // With an rvalue, it should not be destroyed until the end of the scope.
213 int Copies = 0;
214 int Moves = 0;
215 int Destructors = 0;
216 {
217 Range<true, false> R(Copies, Moves, Destructors);
218 {
219 auto E = enumerate(std::move(R));
220 (void)E;
221 // Doesn't compile. rvalue ranges must be moveable.
222 // auto E2 = enumerate(Range<false, true>(Copies, Moves, Destructors));
223 EXPECT_EQ(0, Copies);
224 EXPECT_EQ(1, Moves);
225 EXPECT_EQ(0, Destructors);
226 }
227 EXPECT_EQ(0, Copies);
228 EXPECT_EQ(1, Moves);
229 EXPECT_EQ(1, Destructors);
230 }
231 EXPECT_EQ(0, Copies);
232 EXPECT_EQ(1, Moves);
233 EXPECT_EQ(2, Destructors);
234 }
235
236 TEST(STLExtrasTest, EnumerateLifetimeSemanticsLValue) {
237 // With an lvalue, it should not be destroyed even after the end of the scope.
238 // lvalue ranges need be neither copyable nor moveable.
239 int Copies = 0;
240 int Moves = 0;
241 int Destructors = 0;
242 {
243 Range<false, false> R(Copies, Moves, Destructors);
244 {
245 auto E = enumerate(R);
246 (void)E;
247 EXPECT_EQ(0, Copies);
248 EXPECT_EQ(0, Moves);
249 EXPECT_EQ(0, Destructors);
250 }
251 EXPECT_EQ(0, Copies);
252 EXPECT_EQ(0, Moves);
253 EXPECT_EQ(0, Destructors);
254 }
255 EXPECT_EQ(0, Copies);
256 EXPECT_EQ(0, Moves);
257 EXPECT_EQ(1, Destructors);
258 }
259
260 TEST(STLExtrasTest, CountAdaptor) {
261 std::vector<int> v;
262
263 v.push_back(1);
264 v.push_back(2);
265 v.push_back(1);
266 v.push_back(4);
267 v.push_back(3);
268 v.push_back(2);
269 v.push_back(1);
270
271 EXPECT_EQ(3, count(v, 1));
272 EXPECT_EQ(2, count(v, 2));
273 EXPECT_EQ(1, count(v, 3));
274 EXPECT_EQ(1, count(v, 4));
275 }
276
277 TEST(STLExtrasTest, for_each) {
278 std::vector<int> v{0, 1, 2, 3, 4};
279 int count = 0;
280
281 llvm::for_each(v, [&count](int) { ++count; });
282 EXPECT_EQ(5, count);
283 }
284
285 TEST(STLExtrasTest, ToVector) {
286 std::vector<char> v = {'a', 'b', 'c'};
287 auto Enumerated = to_vector<4>(enumerate(v));
288 ASSERT_EQ(3u, Enumerated.size());
289 for (size_t I = 0; I < v.size(); ++I) {
290 EXPECT_EQ(I, Enumerated[I].index());
291 EXPECT_EQ(v[I], Enumerated[I].value());
292 }
293
294 auto EnumeratedImplicitSize = to_vector(enumerate(v));
295 ASSERT_EQ(3u, EnumeratedImplicitSize.size());
296 for (size_t I = 0; I < v.size(); ++I) {
297 EXPECT_EQ(I, EnumeratedImplicitSize[I].index());
298 EXPECT_EQ(v[I], EnumeratedImplicitSize[I].value());
299 }
300 }
301
302 TEST(STLExtrasTest, ConcatRange) {
303 std::vector<int> Expected = {1, 2, 3, 4, 5, 6, 7, 8};
304 std::vector<int> Test;
305
306 std::vector<int> V1234 = {1, 2, 3, 4};
307 std::list<int> L56 = {5, 6};
308 SmallVector<int, 2> SV78 = {7, 8};
309
310 // Use concat across different sized ranges of different types with different
311 // iterators.
312 for (int &i : concat<int>(V1234, L56, SV78))
313 Test.push_back(i);
314 EXPECT_EQ(Expected, Test);
315
316 // Use concat between a temporary, an L-value, and an R-value to make sure
317 // complex lifetimes work well.
318 Test.clear();
319 for (int &i : concat<int>(std::vector<int>(V1234), L56, std::move(SV78)))
320 Test.push_back(i);
321 EXPECT_EQ(Expected, Test);
322 }
323
324 TEST(STLExtrasTest, PartitionAdaptor) {
325 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
326
327 auto I = partition(V, [](int i) { return i % 2 == 0; });
328 ASSERT_EQ(V.begin() + 4, I);
329
330 // Sort the two halves as partition may have messed with the order.
331 llvm::sort(V.begin(), I);
332 llvm::sort(I, V.end());
333
334 EXPECT_EQ(2, V[0]);
335 EXPECT_EQ(4, V[1]);
336 EXPECT_EQ(6, V[2]);
337 EXPECT_EQ(8, V[3]);
338 EXPECT_EQ(1, V[4]);
339 EXPECT_EQ(3, V[5]);
340 EXPECT_EQ(5, V[6]);
341 EXPECT_EQ(7, V[7]);
342 }
343
344 TEST(STLExtrasTest, EraseIf) {
345 std::vector<int> V = {1, 2, 3, 4, 5, 6, 7, 8};
346
347 erase_if(V, [](int i) { return i % 2 == 0; });
348 EXPECT_EQ(4u, V.size());
349 EXPECT_EQ(1, V[0]);
350 EXPECT_EQ(3, V[1]);
351 EXPECT_EQ(5, V[2]);
352 EXPECT_EQ(7, V[3]);
353 }
354
355 TEST(STLExtrasTest, AppendRange) {
356 auto AppendVals = {3};
357 std::vector<int> V = {1, 2};
358 append_range(V, AppendVals);
359 EXPECT_EQ(1, V[0]);
360 EXPECT_EQ(2, V[1]);
361 EXPECT_EQ(3, V[2]);
362 }
363
364 namespace some_namespace {
365 struct some_struct {
366 std::vector<int> data;
367 std::string swap_val;
368 };
369
370 std::vector<int>::const_iterator begin(const some_struct &s) {
371 return s.data.begin();
372 }
373
374 std::vector<int>::const_iterator end(const some_struct &s) {
375 return s.data.end();
376 }
377
378 void swap(some_struct &lhs, some_struct &rhs) {
379 // make swap visible as non-adl swap would even seem to
380 // work with std::swap which defaults to moving
381 lhs.swap_val = "lhs";
382 rhs.swap_val = "rhs";
383 }
384 } // namespace some_namespace
385
386 TEST(STLExtrasTest, ADLTest) {
387 some_namespace::some_struct s{{1, 2, 3, 4, 5}, ""};
388 some_namespace::some_struct s2{{2, 4, 6, 8, 10}, ""};
389
390 EXPECT_EQ(*adl_begin(s), 1);
391 EXPECT_EQ(*(adl_end(s) - 1), 5);
392
393 adl_swap(s, s2);
394 EXPECT_EQ(s.swap_val, "lhs");
395 EXPECT_EQ(s2.swap_val, "rhs");
396
397 int count = 0;
398 llvm::for_each(s, [&count](int) { ++count; });
399 EXPECT_EQ(5, count);
400 }
401
402 TEST(STLExtrasTest, DropBeginTest) {
403 SmallVector<int, 5> vec{0, 1, 2, 3, 4};
404
405 for (int n = 0; n < 5; ++n) {
406 int i = n;
407 for (auto &v : drop_begin(vec, n)) {
408 EXPECT_EQ(v, i);
409 i += 1;
410 }
411 EXPECT_EQ(i, 5);
412 }
413 }
414
415 TEST(STLExtrasTest, DropBeginDefaultTest) {
416 SmallVector<int, 5> vec{0, 1, 2, 3, 4};
417
418 int i = 1;
419 for (auto &v : drop_begin(vec)) {
420 EXPECT_EQ(v, i);
421 i += 1;
422 }
423 EXPECT_EQ(i, 5);
424 }
425
426 TEST(STLExtrasTest, DropEndTest) {
427 SmallVector<int, 5> vec{0, 1, 2, 3, 4};
428
429 for (int n = 0; n < 5; ++n) {
430 int i = 0;
431 for (auto &v : drop_end(vec, n)) {
432 EXPECT_EQ(v, i);
433 i += 1;
434 }
435 EXPECT_EQ(i, 5 - n);
436 }
437 }
438
439 TEST(STLExtrasTest, DropEndDefaultTest) {
440 SmallVector<int, 5> vec{0, 1, 2, 3, 4};
441
442 int i = 0;
443 for (auto &v : drop_end(vec)) {
444 EXPECT_EQ(v, i);
445 i += 1;
446 }
447 EXPECT_EQ(i, 4);
448 }
449
450 TEST(STLExtrasTest, EarlyIncrementTest) {
451 std::list<int> L = {1, 2, 3, 4};
452
453 auto EIR = make_early_inc_range(L);
454
455 auto I = EIR.begin();
456 auto EI = EIR.end();
457 EXPECT_NE(I, EI);
458
459 EXPECT_EQ(1, *I);
460 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
461 #ifndef NDEBUG
462 // Repeated dereferences are not allowed.
463 EXPECT_DEATH(*I, "Cannot dereference");
464 // Comparison after dereference is not allowed.
465 EXPECT_DEATH((void)(I == EI), "Cannot compare");
466 EXPECT_DEATH((void)(I != EI), "Cannot compare");
467 #endif
468 #endif
469
470 ++I;
471 EXPECT_NE(I, EI);
472 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
473 #ifndef NDEBUG
474 // You cannot increment prior to dereference.
475 EXPECT_DEATH(++I, "Cannot increment");
476 #endif
477 #endif
478 EXPECT_EQ(2, *I);
479 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
480 #ifndef NDEBUG
481 // Repeated dereferences are not allowed.
482 EXPECT_DEATH(*I, "Cannot dereference");
483 #endif
484 #endif
485
486 // Inserting shouldn't break anything. We should be able to keep dereferencing
487 // the currrent iterator and increment. The increment to go to the "next"
488 // iterator from before we inserted.
489 L.insert(std::next(L.begin(), 2), -1);
490 ++I;
491 EXPECT_EQ(3, *I);
492
493 // Erasing the front including the current doesn't break incrementing.
494 L.erase(L.begin(), std::prev(L.end()));
495 ++I;
496 EXPECT_EQ(4, *I);
497 ++I;
498 EXPECT_EQ(EIR.end(), I);
499 }
500
501 // A custom iterator that returns a pointer when dereferenced. This is used to
502 // test make_early_inc_range with iterators that do not return a reference on
503 // dereferencing.
504 struct CustomPointerIterator
505 : public iterator_adaptor_base<CustomPointerIterator,
506 std::list<int>::iterator,
507 std::forward_iterator_tag> {
508 using base_type =
509 iterator_adaptor_base<CustomPointerIterator, std::list<int>::iterator,
510 std::forward_iterator_tag>;
511
512 explicit CustomPointerIterator(std::list<int>::iterator I) : base_type(I) {}
513
514 // Retrieve a pointer to the current int.
515 int *operator*() const { return &*base_type::wrapped(); }
516 };
517
518 // Make sure make_early_inc_range works with iterators that do not return a
519 // reference on dereferencing. The test is similar to EarlyIncrementTest, but
520 // uses CustomPointerIterator.
521 TEST(STLExtrasTest, EarlyIncrementTestCustomPointerIterator) {
522 std::list<int> L = {1, 2, 3, 4};
523
524 auto CustomRange = make_range(CustomPointerIterator(L.begin()),
525 CustomPointerIterator(L.end()));
526 auto EIR = make_early_inc_range(CustomRange);
527
528 auto I = EIR.begin();
529 auto EI = EIR.end();
530 EXPECT_NE(I, EI);
531
532 EXPECT_EQ(&*L.begin(), *I);
533 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
534 #ifndef NDEBUG
535 // Repeated dereferences are not allowed.
536 EXPECT_DEATH(*I, "Cannot dereference");
537 // Comparison after dereference is not allowed.
538 EXPECT_DEATH((void)(I == EI), "Cannot compare");
539 EXPECT_DEATH((void)(I != EI), "Cannot compare");
540 #endif
541 #endif
542
543 ++I;
544 EXPECT_NE(I, EI);
545 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
546 #ifndef NDEBUG
547 // You cannot increment prior to dereference.
548 EXPECT_DEATH(++I, "Cannot increment");
549 #endif
550 #endif
551 EXPECT_EQ(&*std::next(L.begin()), *I);
552 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
553 #ifndef NDEBUG
554 // Repeated dereferences are not allowed.
555 EXPECT_DEATH(*I, "Cannot dereference");
556 #endif
557 #endif
558
559 // Inserting shouldn't break anything. We should be able to keep dereferencing
560 // the currrent iterator and increment. The increment to go to the "next"
561 // iterator from before we inserted.
562 L.insert(std::next(L.begin(), 2), -1);
563 ++I;
564 EXPECT_EQ(&*std::next(L.begin(), 3), *I);
565
566 // Erasing the front including the current doesn't break incrementing.
567 L.erase(L.begin(), std::prev(L.end()));
568 ++I;
569 EXPECT_EQ(&*L.begin(), *I);
570 ++I;
571 EXPECT_EQ(EIR.end(), I);
572 }
573
574 TEST(STLExtrasTest, AllEqual) {
575 std::vector<int> V;
576 EXPECT_TRUE(all_equal(V));
577
578 V.push_back(1);
579 EXPECT_TRUE(all_equal(V));
580
581 V.push_back(1);
582 V.push_back(1);
583 EXPECT_TRUE(all_equal(V));
584
585 V.push_back(2);
586 EXPECT_FALSE(all_equal(V));
587 }
588
589 TEST(STLExtrasTest, AllEqualInitializerList) {
590 EXPECT_TRUE(all_equal({1}));
591 EXPECT_TRUE(all_equal({1, 1}));
592 EXPECT_FALSE(all_equal({1, 2}));
593 EXPECT_FALSE(all_equal({2, 1}));
594 EXPECT_TRUE(all_equal({1, 1, 1}));
595 }
596
597 TEST(STLExtrasTest, to_address) {
598 int *V1 = new int;
599 EXPECT_EQ(V1, to_address(V1));
600
601 // Check fancy pointer overload for unique_ptr
602 std::unique_ptr<int> V2 = std::make_unique<int>(0);
603 EXPECT_EQ(V2.get(), llvm::to_address(V2));
604
605 V2.reset(V1);
606 EXPECT_EQ(V1, llvm::to_address(V2));
607 V2.release();
608
609 // Check fancy pointer overload for shared_ptr
610 std::shared_ptr<int> V3 = std::make_shared<int>(0);
611 std::shared_ptr<int> V4 = V3;
612 EXPECT_EQ(V3.get(), V4.get());
613 EXPECT_EQ(V3.get(), llvm::to_address(V3));
614 EXPECT_EQ(V4.get(), llvm::to_address(V4));
615
616 V3.reset(V1);
617 EXPECT_EQ(V1, llvm::to_address(V3));
618 }
619
620 TEST(STLExtrasTest, partition_point) {
621 std::vector<int> V = {1, 3, 5, 7, 9};
622
623 // Range version.
624 EXPECT_EQ(V.begin() + 3,
625 partition_point(V, [](unsigned X) { return X < 7; }));
626 EXPECT_EQ(V.begin(), partition_point(V, [](unsigned X) { return X < 1; }));
627 EXPECT_EQ(V.end(), partition_point(V, [](unsigned X) { return X < 50; }));
628 }
629
630 TEST(STLExtrasTest, hasSingleElement) {
631 const std::vector<int> V0 = {}, V1 = {1}, V2 = {1, 2};
632 const std::vector<int> V10(10);
633
634 EXPECT_EQ(hasSingleElement(V0), false);
635 EXPECT_EQ(hasSingleElement(V1), true);
636 EXPECT_EQ(hasSingleElement(V2), false);
637 EXPECT_EQ(hasSingleElement(V10), false);
638 }
639
640 TEST(STLExtrasTest, hasNItems) {
641 const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};
642 const std::list<int> V3 = {1, 3, 5};
643
644 EXPECT_TRUE(hasNItems(V0, 0));
645 EXPECT_FALSE(hasNItems(V0, 2));
646 EXPECT_TRUE(hasNItems(V1, 1));
647 EXPECT_FALSE(hasNItems(V1, 2));
648
649 EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 3, [](int x) { return x < 10; }));
650 EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 0, [](int x) { return x > 10; }));
651 EXPECT_TRUE(hasNItems(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));
652 }
653
654 TEST(STLExtras, hasNItemsOrMore) {
655 const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};
656 const std::list<int> V3 = {1, 3, 5};
657
658 EXPECT_TRUE(hasNItemsOrMore(V1, 1));
659 EXPECT_FALSE(hasNItemsOrMore(V1, 2));
660
661 EXPECT_TRUE(hasNItemsOrMore(V2, 1));
662 EXPECT_TRUE(hasNItemsOrMore(V2, 2));
663 EXPECT_FALSE(hasNItemsOrMore(V2, 3));
664
665 EXPECT_TRUE(hasNItemsOrMore(V3, 3));
666 EXPECT_FALSE(hasNItemsOrMore(V3, 4));
667
668 EXPECT_TRUE(
669 hasNItemsOrMore(V3.begin(), V3.end(), 3, [](int x) { return x < 10; }));
670 EXPECT_FALSE(
671 hasNItemsOrMore(V3.begin(), V3.end(), 3, [](int x) { return x > 10; }));
672 EXPECT_TRUE(
673 hasNItemsOrMore(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));
674 }
675
676 TEST(STLExtras, hasNItemsOrLess) {
677 const std::list<int> V0 = {}, V1 = {1}, V2 = {1, 2};
678 const std::list<int> V3 = {1, 3, 5};
679
680 EXPECT_TRUE(hasNItemsOrLess(V0, 0));
681 EXPECT_TRUE(hasNItemsOrLess(V0, 1));
682 EXPECT_TRUE(hasNItemsOrLess(V0, 2));
683
684 EXPECT_FALSE(hasNItemsOrLess(V1, 0));
685 EXPECT_TRUE(hasNItemsOrLess(V1, 1));
686 EXPECT_TRUE(hasNItemsOrLess(V1, 2));
687
688 EXPECT_FALSE(hasNItemsOrLess(V2, 0));
689 EXPECT_FALSE(hasNItemsOrLess(V2, 1));
690 EXPECT_TRUE(hasNItemsOrLess(V2, 2));
691 EXPECT_TRUE(hasNItemsOrLess(V2, 3));
692
693 EXPECT_FALSE(hasNItemsOrLess(V3, 0));
694 EXPECT_FALSE(hasNItemsOrLess(V3, 1));
695 EXPECT_FALSE(hasNItemsOrLess(V3, 2));
696 EXPECT_TRUE(hasNItemsOrLess(V3, 3));
697 EXPECT_TRUE(hasNItemsOrLess(V3, 4));
698
699 EXPECT_TRUE(
700 hasNItemsOrLess(V3.begin(), V3.end(), 1, [](int x) { return x == 1; }));
701 EXPECT_TRUE(
702 hasNItemsOrLess(V3.begin(), V3.end(), 2, [](int x) { return x < 5; }));
703 EXPECT_TRUE(
704 hasNItemsOrLess(V3.begin(), V3.end(), 5, [](int x) { return x < 5; }));
705 EXPECT_FALSE(
706 hasNItemsOrLess(V3.begin(), V3.end(), 2, [](int x) { return x < 10; }));
707 }
708
709 TEST(STLExtras, MoveRange) {
710 class Foo {
711 bool A;
712
713 public:
714 Foo() : A(true) {}
715 Foo(const Foo &) = delete;
716 Foo(Foo &&Other) : A(Other.A) { Other.A = false; }
717 Foo &operator=(const Foo &) = delete;
718 Foo &operator=(Foo &&Other) {
719 if (this != &Other) {
720 A = Other.A;
721 Other.A = false;
722 }
723 return *this;
724 }
725 operator bool() const { return A; }
726 };
727 SmallVector<Foo, 4U> V1, V2, V3, V4;
728 auto HasVal = [](const Foo &Item) { return static_cast<bool>(Item); };
729 auto Build = [&] {
730 SmallVector<Foo, 4U> Foos;
731 Foos.resize(4U);
732 return Foos;
733 };
734
735 V1.resize(4U);
736 EXPECT_TRUE(llvm::all_of(V1, HasVal));
737
738 llvm::move(V1, std::back_inserter(V2));
739
740 // Ensure input container is same size, but its contents were moved out.
741 EXPECT_EQ(V1.size(), 4U);
742 EXPECT_TRUE(llvm::none_of(V1, HasVal));
743
744 // Ensure output container has the contents of the input container.
745 EXPECT_EQ(V2.size(), 4U);
746 EXPECT_TRUE(llvm::all_of(V2, HasVal));
747
748 llvm::move(std::move(V2), std::back_inserter(V3));
749
750 EXPECT_TRUE(llvm::none_of(V2, HasVal));
751 EXPECT_EQ(V3.size(), 4U);
752 EXPECT_TRUE(llvm::all_of(V3, HasVal));
753
754 llvm::move(Build(), std::back_inserter(V4));
755 EXPECT_EQ(V4.size(), 4U);
756 EXPECT_TRUE(llvm::all_of(V4, HasVal));
757 }
758
759 TEST(STLExtras, Unique) {
760 std::vector<int> V = {1, 5, 5, 4, 3, 3, 3};
761
762 auto I = llvm::unique(V, [](int a, int b) { return a == b; });
763
764 EXPECT_EQ(I, V.begin() + 4);
765
766 EXPECT_EQ(1, V[0]);
767 EXPECT_EQ(5, V[1]);
768 EXPECT_EQ(4, V[2]);
769 EXPECT_EQ(3, V[3]);
770 }
771
772 TEST(STLExtrasTest, MakeVisitorOneCallable) {
773 auto IdentityLambda = [](auto X) { return X; };
774 auto IdentityVisitor = makeVisitor(IdentityLambda);
775 EXPECT_EQ(IdentityLambda(1), IdentityVisitor(1));
776 EXPECT_EQ(IdentityLambda(2.0f), IdentityVisitor(2.0f));
777 EXPECT_TRUE((std::is_same<decltype(IdentityLambda(IdentityLambda)),
778 decltype(IdentityLambda)>::value));
779 EXPECT_TRUE((std::is_same<decltype(IdentityVisitor(IdentityVisitor)),
780 decltype(IdentityVisitor)>::value));
781 }
782
783 TEST(STLExtrasTest, MakeVisitorTwoCallables) {
784 auto Visitor =
785 makeVisitor([](int) { return 0; }, [](std::string) { return 1; });
786 EXPECT_EQ(Visitor(42), 0);
787 EXPECT_EQ(Visitor("foo"), 1);
788 }
789
790 TEST(STLExtrasTest, MakeVisitorCallableMultipleOperands) {
791 auto Second = makeVisitor([](int I, float F) { return F; },
792 [](float F, int I) { return I; });
793 EXPECT_EQ(Second(1.f, 1), 1);
794 EXPECT_EQ(Second(1, 1.f), 1.f);
795 }
796
797 TEST(STLExtrasTest, MakeVisitorDefaultCase) {
798 {
799 auto Visitor = makeVisitor([](int I) { return I + 100; },
800 [](float F) { return F * 2; },
801 [](auto) { return -1; });
802 EXPECT_EQ(Visitor(24), 124);
803 EXPECT_EQ(Visitor(2.f), 4.f);
804 EXPECT_EQ(Visitor(2.), -1);
805 EXPECT_EQ(Visitor(Visitor), -1);
806 }
807 {
808 auto Visitor = makeVisitor([](auto) { return -1; },
809 [](int I) { return I + 100; },
810 [](float F) { return F * 2; });
811 EXPECT_EQ(Visitor(24), 124);
812 EXPECT_EQ(Visitor(2.f), 4.f);
813 EXPECT_EQ(Visitor(2.), -1);
814 EXPECT_EQ(Visitor(Visitor), -1);
815 }
816 }
817
818 template <bool Moveable, bool Copyable>
819 struct Functor : Counted<Moveable, Copyable> {
820 using Counted<Moveable, Copyable>::Counted;
821 void operator()() {}
822 };
823
824 TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsPRValue) {
825 int Copies = 0;
826 int Moves = 0;
827 int Destructors = 0;
828 {
829 auto V = makeVisitor(Functor<true, false>(Copies, Moves, Destructors));
830 (void)V;
831 EXPECT_EQ(0, Copies);
832 EXPECT_EQ(1, Moves);
833 EXPECT_EQ(1, Destructors);
834 }
835 EXPECT_EQ(0, Copies);
836 EXPECT_EQ(1, Moves);
837 EXPECT_EQ(2, Destructors);
838 }
839
840 TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsRValue) {
841 int Copies = 0;
842 int Moves = 0;
843 int Destructors = 0;
844 {
845 Functor<true, false> F(Copies, Moves, Destructors);
846 {
847 auto V = makeVisitor(std::move(F));
848 (void)V;
849 EXPECT_EQ(0, Copies);
850 EXPECT_EQ(1, Moves);
851 EXPECT_EQ(0, Destructors);
852 }
853 EXPECT_EQ(0, Copies);
854 EXPECT_EQ(1, Moves);
855 EXPECT_EQ(1, Destructors);
856 }
857 EXPECT_EQ(0, Copies);
858 EXPECT_EQ(1, Moves);
859 EXPECT_EQ(2, Destructors);
860 }
861
862 TEST(STLExtrasTest, MakeVisitorLifetimeSemanticsLValue) {
863 int Copies = 0;
864 int Moves = 0;
865 int Destructors = 0;
866 {
867 Functor<true, true> F(Copies, Moves, Destructors);
868 {
869 auto V = makeVisitor(F);
870 (void)V;
871 EXPECT_EQ(1, Copies);
872 EXPECT_EQ(0, Moves);
873 EXPECT_EQ(0, Destructors);
874 }
875 EXPECT_EQ(1, Copies);
876 EXPECT_EQ(0, Moves);
877 EXPECT_EQ(1, Destructors);
878 }
879 EXPECT_EQ(1, Copies);
880 EXPECT_EQ(0, Moves);
881 EXPECT_EQ(2, Destructors);
882 }
883
884 TEST(STLExtrasTest, AllOfZip) {
885 std::vector<int> v1 = {0, 4, 2, 1};
886 std::vector<int> v2 = {1, 4, 3, 6};
887 EXPECT_TRUE(all_of_zip(v1, v2, [](int v1, int v2) { return v1 <= v2; }));
888 EXPECT_FALSE(all_of_zip(v1, v2, [](int L, int R) { return L < R; }));
889
890 // Triple vectors
891 std::vector<int> v3 = {1, 6, 5, 7};
892 EXPECT_EQ(true, all_of_zip(v1, v2, v3, [](int a, int b, int c) {
893 return a <= b && b <= c;
894 }));
895 EXPECT_EQ(false, all_of_zip(v1, v2, v3, [](int a, int b, int c) {
896 return a < b && b < c;
897 }));
898
899 // Shorter vector should fail even with an always-true predicate.
900 std::vector<int> v_short = {1, 4};
901 EXPECT_EQ(false, all_of_zip(v1, v_short, [](int, int) { return true; }));
902 EXPECT_EQ(false,
903 all_of_zip(v1, v2, v_short, [](int, int, int) { return true; }));
904 }
905
906 TEST(STLExtrasTest, TypesAreDistinct) {
907 EXPECT_TRUE((llvm::TypesAreDistinct<>::value));
908 EXPECT_TRUE((llvm::TypesAreDistinct<int>::value));
909 EXPECT_FALSE((llvm::TypesAreDistinct<int, int>::value));
910 EXPECT_TRUE((llvm::TypesAreDistinct<int, float>::value));
911 EXPECT_FALSE((llvm::TypesAreDistinct<int, float, int>::value));
912 EXPECT_TRUE((llvm::TypesAreDistinct<int, float, double>::value));
913 EXPECT_FALSE((llvm::TypesAreDistinct<int, float, double, float>::value));
914 EXPECT_TRUE((llvm::TypesAreDistinct<int, int *>::value));
915 EXPECT_TRUE((llvm::TypesAreDistinct<int, int &>::value));
916 EXPECT_TRUE((llvm::TypesAreDistinct<int, int &&>::value));
917 EXPECT_TRUE((llvm::TypesAreDistinct<int, const int>::value));
918 }
919
920 TEST(STLExtrasTest, FirstIndexOfType) {
921 EXPECT_EQ((llvm::FirstIndexOfType<int, int>::value), 0u);
922 EXPECT_EQ((llvm::FirstIndexOfType<int, int, int>::value), 0u);
923 EXPECT_EQ((llvm::FirstIndexOfType<int, float, int>::value), 1u);
924 EXPECT_EQ((llvm::FirstIndexOfType<int const *, float, int, int const *,
925 const int>::value),
926 2u);
927 }
928
929 TEST(STLExtrasTest, TypeAtIndex) {
930 EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int>>::value));
931 EXPECT_TRUE((std::is_same<int, llvm::TypeAtIndex<0, int, float>>::value));
932 EXPECT_TRUE((std::is_same<float, llvm::TypeAtIndex<1, int, float>>::value));
933 EXPECT_TRUE(
934 (std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));
935 EXPECT_TRUE(
936 (std::is_same<float, llvm::TypeAtIndex<1, int, float, double>>::value));
937 EXPECT_TRUE(
938 (std::is_same<double, llvm::TypeAtIndex<2, int, float, double>>::value));
939 }
940
941 enum Doggos {
942 Floofer,
943 Woofer,
944 SubWoofer,
945 Pupper,
946 Pupperino,
947 Longboi,
948 };
949
950 TEST(STLExtrasTest, IsContainedInitializerList) {
951 EXPECT_TRUE(is_contained({Woofer, SubWoofer}, Woofer));
952 EXPECT_TRUE(is_contained({Woofer, SubWoofer}, SubWoofer));
953 EXPECT_FALSE(is_contained({Woofer, SubWoofer}, Pupper));
954 EXPECT_FALSE(is_contained({}, Longboi));
955
956 static_assert(is_contained({Woofer, SubWoofer}, SubWoofer), "SubWoofer!");
957 static_assert(!is_contained({Woofer, SubWoofer}, Pupper), "Missing Pupper!");
958
959 EXPECT_TRUE(is_contained({1, 2, 3, 4}, 3));
960 EXPECT_FALSE(is_contained({1, 2, 3, 4}, 5));
961
962 static_assert(is_contained({1, 2, 3, 4}, 3), "It's there!");
963 static_assert(!is_contained({1, 2, 3, 4}, 5), "It's not there :(");
964 }
965
966 TEST(STLExtrasTest, addEnumValues) {
967 enum A { Zero = 0, One = 1 };
968 enum B { IntMax = INT_MAX, ULongLongMax = ULLONG_MAX };
969 enum class C : unsigned { Two = 2 };
970
971 // Non-fixed underlying types, with same underlying types
972 static_assert(addEnumValues(Zero, One) == 1,
973 "addEnumValues(Zero, One) failed.");
974 static_assert(addEnumValues(IntMax, ULongLongMax) ==
975 INT_MAX + static_cast<unsigned long long>(ULLONG_MAX),
976 "addEnumValues(IntMax, ULongLongMax) failed.");
977 // Non-fixed underlying types, with different underlying types
978 static_assert(addEnumValues(Zero, IntMax) == INT_MAX,
979 "addEnumValues(Zero, IntMax) failed.");
980 static_assert(addEnumValues(One, ULongLongMax) ==
981 1 + static_cast<unsigned long long>(ULLONG_MAX),
982 "addEnumValues(One, ULongLongMax) failed.");
983 // Non-fixed underlying type enum and fixed underlying type enum, with same
984 // underlying types
985 static_assert(addEnumValues(One, C::Two) == 3,
986 "addEnumValues(One, C::Two) failed.");
987 // Non-fixed underlying type enum and fixed underlying type enum, with
988 // different underlying types
989 static_assert(addEnumValues(ULongLongMax, C::Two) ==
990 static_cast<unsigned long long>(ULLONG_MAX) + 2,
991 "addEnumValues(ULongLongMax, C::Two) failed.");
992 }
993
994 } // namespace