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 // Making this test file support C++03 is difficult; the lack of support for initializer lists is a major issue.
10 // UNSUPPORTED: c++03
11
12 // <algorithm>
13
14 #include <algorithm>
15 #include <array>
16 #include <cassert>
17 #include <random>
18 #include <set>
19
20 #include "test_macros.h"
21
22 // This file contains checks for lifetime issues across all the classic algorithms. It uses two complementary
23 // approaches:
24 // - runtime checks using a proxy iterator that tracks the lifetime of itself and its objects to catch potential
25 // lifetime issues;
26 // - `constexpr` checks using a `constexpr`-friendly proxy iterator that catch undefined behavior.
27
28 // A random-access proxy iterator that tracks the lifetime of itself and its `value_type` and `reference` objects to
29 // prevent potential lifetime issues in algorithms.
30 //
31 // This class cannot be `constexpr` because its cache is a static variable. The cache cannot be provided as
32 // a constructor parameter because `LifetimeIterator` has to be default-constructible.
33 class LifetimeIterator {
34 // The cache simply tracks addresses of the local variables.
35 class LifetimeCache {
36 std::set<const void*> cache_;
37
38 public:
contains(const void * ptr) const39 bool contains(const void* ptr) const { return cache_.find(ptr) != cache_.end(); }
40
insert(const void * ptr)41 void insert(const void* ptr) {
42 assert(!contains(ptr));
43 cache_.insert(ptr);
44 }
45
erase(const void * ptr)46 void erase(const void* ptr) {
47 assert(contains(ptr));
48 cache_.erase(ptr);
49 }
50 };
51
52 public:
53 struct Value {
54 int i_;
55 bool moved_from_ = false; // Check for double moves and reads after moving.
56
ValueLifetimeIterator::Value57 Value() { lifetime_cache.insert(this); }
ValueLifetimeIterator::Value58 Value(int i) : i_(i) { lifetime_cache.insert(this); }
~ValueLifetimeIterator::Value59 ~Value() { lifetime_cache.erase(this); }
60
ValueLifetimeIterator::Value61 Value(const Value& rhs) : i_(rhs.i_) {
62 assert(lifetime_cache.contains(&rhs));
63 assert(!rhs.moved_from_);
64
65 lifetime_cache.insert(this);
66 }
67
ValueLifetimeIterator::Value68 Value(Value&& rhs) noexcept : i_(rhs.i_) {
69 assert(lifetime_cache.contains(&rhs));
70
71 assert(!rhs.moved_from_);
72 rhs.moved_from_ = true;
73
74 // It's ok if it throws -- since it's a test, terminating the program is acceptable.
75 lifetime_cache.insert(this);
76 }
77
operator =LifetimeIterator::Value78 Value& operator=(const Value& rhs) {
79 assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
80 assert(!rhs.moved_from_);
81
82 i_ = rhs.i_;
83 moved_from_ = false;
84
85 return *this;
86 }
87
operator =LifetimeIterator::Value88 Value& operator=(Value&& rhs) noexcept {
89 assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
90
91 assert(!rhs.moved_from_);
92 rhs.moved_from_ = true;
93
94 i_ = rhs.i_;
95 moved_from_ = false;
96
97 return *this;
98 }
99
operator <(const Value & lhs,const Value & rhs)100 friend bool operator<(const Value& lhs, const Value& rhs) {
101 assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
102 assert(!lhs.moved_from_ && !rhs.moved_from_);
103
104 return lhs.i_ < rhs.i_;
105 }
106
operator ==(const Value & lhs,const Value & rhs)107 friend bool operator==(const Value& lhs, const Value& rhs) {
108 assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
109 assert(!lhs.moved_from_ && !rhs.moved_from_);
110
111 return lhs.i_ == rhs.i_;
112 }
113
114 };
115
116 struct Reference {
117 Value* v_;
118 bool moved_from_ = false; // Check for double moves and reads after moving.
119
ReferenceLifetimeIterator::Reference120 Reference(Value& v) : v_(&v) {
121 lifetime_cache.insert(this);
122 }
123
~ReferenceLifetimeIterator::Reference124 ~Reference() {
125 lifetime_cache.erase(this);
126 }
127
ReferenceLifetimeIterator::Reference128 Reference(const Reference& rhs) : v_(rhs.v_) {
129 assert(lifetime_cache.contains(&rhs));
130 assert(!rhs.moved_from_);
131
132 lifetime_cache.insert(this);
133 }
134
ReferenceLifetimeIterator::Reference135 Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
136 assert(lifetime_cache.contains(&rhs));
137
138 assert(!rhs.moved_from_);
139 rhs.moved_from_ = true;
140
141 lifetime_cache.insert(this);
142 }
143
operator =LifetimeIterator::Reference144 Reference& operator=(const Reference& rhs) {
145 assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
146 assert(!rhs.moved_from_);
147
148 *v_ = *rhs.v_;
149 moved_from_ = false;
150
151 return *this;
152 }
153
operator =LifetimeIterator::Reference154 Reference& operator=(Reference&& rhs) noexcept {
155 assert(lifetime_cache.contains(this) && lifetime_cache.contains(&rhs));
156
157 assert(!rhs.moved_from_);
158 rhs.moved_from_ = true;
159
160 *v_ = *rhs.v_;
161 moved_from_ = false;
162
163 return *this;
164 }
165
operator ValueLifetimeIterator::Reference166 operator Value() const {
167 assert(lifetime_cache.contains(this));
168 assert(!moved_from_);
169
170 return *v_;
171 }
172
operator =LifetimeIterator::Reference173 Reference& operator=(Value v) {
174 assert(lifetime_cache.contains(this));
175 assert(!moved_from_);
176
177 *v_ = v;
178 moved_from_ = false;
179
180 return *this;
181 }
182
operator <(const Reference & lhs,const Reference & rhs)183 friend bool operator<(const Reference& lhs, const Reference& rhs) {
184 assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
185 assert(!lhs.moved_from_ && !rhs.moved_from_);
186
187 return *lhs.v_ < *rhs.v_;
188 }
189
operator ==(const Reference & lhs,const Reference & rhs)190 friend bool operator==(const Reference& lhs, const Reference& rhs) {
191 assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
192 assert(!lhs.moved_from_ && !rhs.moved_from_);
193
194 return *lhs.v_ == *rhs.v_;
195 }
196
swap(Reference lhs,Reference rhs)197 friend void swap(Reference lhs, Reference rhs) {
198 assert(lifetime_cache.contains(&lhs) && lifetime_cache.contains(&rhs));
199 assert(!lhs.moved_from_ && !rhs.moved_from_);
200
201 std::swap(*(lhs.v_), *(rhs.v_));
202 }
203 };
204
205 using difference_type = int;
206 using value_type = Value;
207 using reference = Reference;
208 using pointer = void;
209 using iterator_category = std::random_access_iterator_tag;
210
211 Value* ptr_ = nullptr;
212 bool moved_from_ = false; // Check for double moves and reads after moving.
213
214 LifetimeIterator() = default;
LifetimeIterator(Value * ptr)215 LifetimeIterator(Value* ptr) : ptr_(ptr) {}
216
LifetimeIterator(const LifetimeIterator & rhs)217 LifetimeIterator(const LifetimeIterator& rhs) : ptr_(rhs.ptr_) {
218 assert(!rhs.moved_from_);
219 }
220
operator =(const LifetimeIterator & rhs)221 LifetimeIterator& operator=(const LifetimeIterator& rhs) {
222 assert(!rhs.moved_from_);
223
224 ptr_ = rhs.ptr_;
225 moved_from_ = false;
226
227 return *this;
228 }
229
LifetimeIterator(LifetimeIterator && rhs)230 LifetimeIterator(LifetimeIterator&& rhs) noexcept : ptr_(rhs.ptr_) {
231 assert(!rhs.moved_from_);
232 rhs.moved_from_ = true;
233 rhs.ptr_ = nullptr;
234 }
235
operator =(LifetimeIterator && rhs)236 LifetimeIterator& operator=(LifetimeIterator&& rhs) noexcept {
237 assert(!rhs.moved_from_);
238 rhs.moved_from_ = true;
239 moved_from_ = false;
240
241 ptr_ = rhs.ptr_;
242 rhs.ptr_ = nullptr;
243
244 return *this;
245 }
246
operator *() const247 Reference operator*() const {
248 assert(!moved_from_);
249 return Reference(*ptr_);
250 }
251
operator ++()252 LifetimeIterator& operator++() {
253 assert(!moved_from_);
254
255 ++ptr_;
256 return *this;
257 }
258
operator ++(int)259 LifetimeIterator operator++(int) {
260 assert(!moved_from_);
261
262 auto tmp = *this;
263 ++*this;
264 return tmp;
265 }
266
operator ==(const LifetimeIterator & lhs,const LifetimeIterator & rhs)267 friend bool operator==(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
268 assert(!lhs.moved_from_ && !rhs.moved_from_);
269 return lhs.ptr_ == rhs.ptr_;
270 }
operator !=(const LifetimeIterator & lhs,const LifetimeIterator & rhs)271 friend bool operator!=(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
272 assert(!lhs.moved_from_ && !rhs.moved_from_);
273 return lhs.ptr_ != rhs.ptr_;
274 }
275
operator --()276 LifetimeIterator& operator--() {
277 assert(!moved_from_);
278
279 --ptr_;
280 return *this;
281 }
282
operator --(int)283 LifetimeIterator operator--(int) {
284 assert(!moved_from_);
285
286 auto tmp = *this;
287 --*this;
288 return tmp;
289 }
290
operator +=(difference_type n)291 LifetimeIterator& operator+=(difference_type n) {
292 assert(!moved_from_);
293
294 ptr_ += n;
295 return *this;
296 }
297
operator -=(difference_type n)298 LifetimeIterator& operator-=(difference_type n) {
299 assert(!moved_from_);
300
301 ptr_ -= n;
302 return *this;
303 }
304
operator [](difference_type i) const305 Reference operator[](difference_type i) const {
306 assert(!moved_from_);
307 return Reference(*(ptr_ + i));
308 }
309
operator <(const LifetimeIterator & lhs,const LifetimeIterator & rhs)310 friend bool operator<(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
311 assert(!lhs.moved_from_ && !rhs.moved_from_);
312 return lhs.ptr_ < rhs.ptr_;
313 }
314
operator >(const LifetimeIterator & lhs,const LifetimeIterator & rhs)315 friend bool operator>(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
316 assert(!lhs.moved_from_ && !rhs.moved_from_);
317 return lhs.ptr_ > rhs.ptr_;
318 }
319
operator <=(const LifetimeIterator & lhs,const LifetimeIterator & rhs)320 friend bool operator<=(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
321 assert(!lhs.moved_from_ && !rhs.moved_from_);
322 return lhs.ptr_ <= rhs.ptr_;
323 }
324
operator >=(const LifetimeIterator & lhs,const LifetimeIterator & rhs)325 friend bool operator>=(const LifetimeIterator& lhs, const LifetimeIterator& rhs) {
326 assert(!lhs.moved_from_ && !rhs.moved_from_);
327 return lhs.ptr_ >= rhs.ptr_;
328 }
329
operator +(const LifetimeIterator & lhs,difference_type n)330 friend LifetimeIterator operator+(const LifetimeIterator& lhs, difference_type n) {
331 assert(!lhs.moved_from_);
332 return LifetimeIterator(lhs.ptr_ + n);
333 }
334
operator +(difference_type n,const LifetimeIterator & lhs)335 friend LifetimeIterator operator+(difference_type n, const LifetimeIterator& lhs) {
336 assert(!lhs.moved_from_);
337 return LifetimeIterator(n + lhs.ptr_);
338 }
339
operator -(const LifetimeIterator & lhs,difference_type n)340 friend LifetimeIterator operator-(const LifetimeIterator& lhs, difference_type n) {
341 assert(!lhs.moved_from_);
342 return LifetimeIterator(lhs.ptr_ - n);
343 }
344
operator -(LifetimeIterator lhs,LifetimeIterator rhs)345 friend difference_type operator-(LifetimeIterator lhs, LifetimeIterator rhs) {
346 assert(!lhs.moved_from_ && !rhs.moved_from_);
347 return static_cast<int>(lhs.ptr_ - rhs.ptr_);
348 }
349
350 static LifetimeCache lifetime_cache;
351 };
352
353 LifetimeIterator::LifetimeCache LifetimeIterator::lifetime_cache;
354
355 #if TEST_STD_VER > 17
356 // A constexpr-friendly proxy iterator to check for undefined behavior in algorithms (since undefined behavior is
357 // statically caught in `constexpr` context).
358 class ConstexprIterator {
359 public:
360 struct Reference {
361 int* v_;
362 bool moved_from_ = false; // Check for double moves and reads after moving.
363
ReferenceConstexprIterator::Reference364 constexpr Reference(int& v) : v_(&v) { }
365
366 constexpr Reference(const Reference& rhs) = default;
operator =ConstexprIterator::Reference367 constexpr Reference& operator=(const Reference& rhs) {
368 assert(!rhs.moved_from_);
369 v_ = rhs.v_;
370 moved_from_ = false;
371
372 return *this;
373 }
374
ReferenceConstexprIterator::Reference375 constexpr Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
376 assert(!rhs.moved_from_);
377 rhs.moved_from_ = true;
378 }
379
operator =ConstexprIterator::Reference380 constexpr Reference& operator=(Reference&& rhs) noexcept {
381 assert(!rhs.moved_from_);
382 rhs.moved_from_ = true;
383 moved_from_ = false;
384
385 v_ = rhs.v_;
386 return *this;
387 }
388
operator intConstexprIterator::Reference389 constexpr operator int() const {
390 assert(!moved_from_);
391 return *v_;
392 }
393
operator =ConstexprIterator::Reference394 constexpr Reference& operator=(int v) {
395 *v_ = v;
396 moved_from_ = false;
397
398 return *this;
399 }
400
operator <(const Reference & lhs,const Reference & rhs)401 friend constexpr bool operator<(const Reference& lhs, const Reference& rhs) {
402 assert(!lhs.moved_from_ && !rhs.moved_from_);
403 return *lhs.v_ < *rhs.v_;
404 }
405
operator ==(const Reference & lhs,const Reference & rhs)406 friend constexpr bool operator==(const Reference& lhs, const Reference& rhs) {
407 assert(!lhs.moved_from_ && !rhs.moved_from_);
408 return *lhs.v_ == *rhs.v_;
409 }
410
swap(Reference lhs,Reference rhs)411 friend constexpr void swap(Reference lhs, Reference rhs) {
412 assert(!lhs.moved_from_ && !rhs.moved_from_);
413 std::swap(*(lhs.v_), *(rhs.v_));
414 }
415 };
416
417 using difference_type = int;
418 using value_type = int;
419 using reference = Reference;
420 using pointer = void;
421 using iterator_category = std::random_access_iterator_tag;
422
423 int* ptr_ = nullptr;
424 bool moved_from_ = false; // Check for double moves and reads after moving.
425
426 constexpr ConstexprIterator() = default;
ConstexprIterator(int * ptr)427 constexpr ConstexprIterator(int* ptr) : ptr_(ptr) {}
428
ConstexprIterator(const ConstexprIterator & rhs)429 constexpr ConstexprIterator(const ConstexprIterator& rhs) : ptr_(rhs.ptr_) {
430 assert(!rhs.moved_from_);
431 }
432
operator =(const ConstexprIterator & rhs)433 constexpr ConstexprIterator& operator=(const ConstexprIterator& rhs) {
434 assert(!rhs.moved_from_);
435
436 ptr_ = rhs.ptr_;
437 moved_from_ = false;
438
439 return *this;
440 }
441
ConstexprIterator(ConstexprIterator && rhs)442 constexpr ConstexprIterator(ConstexprIterator&& rhs) noexcept : ptr_(rhs.ptr_) {
443 assert(!rhs.moved_from_);
444 rhs.moved_from_ = true;
445 rhs.ptr_ = nullptr;
446 }
447
operator =(ConstexprIterator && rhs)448 constexpr ConstexprIterator& operator=(ConstexprIterator&& rhs) noexcept {
449 assert(!rhs.moved_from_);
450 rhs.moved_from_ = true;
451 moved_from_ = false;
452
453 ptr_ = rhs.ptr_;
454 rhs.ptr_ = nullptr;
455
456 return *this;
457 }
458
operator *() const459 constexpr Reference operator*() const {
460 assert(!moved_from_);
461 return Reference(*ptr_);
462 }
463
operator ++()464 constexpr ConstexprIterator& operator++() {
465 assert(!moved_from_);
466
467 ++ptr_;
468 return *this;
469 }
470
operator ++(int)471 constexpr ConstexprIterator operator++(int) {
472 assert(!moved_from_);
473
474 auto tmp = *this;
475 ++*this;
476 return tmp;
477 }
478
operator ==(const ConstexprIterator & lhs,const ConstexprIterator & rhs)479 friend constexpr bool operator==(const ConstexprIterator& lhs, const ConstexprIterator& rhs) {
480 assert(!lhs.moved_from_ && !rhs.moved_from_);
481 return lhs.ptr_ == rhs.ptr_;
482 }
483
operator !=(const ConstexprIterator & lhs,const ConstexprIterator & rhs)484 friend constexpr bool operator!=(const ConstexprIterator& lhs, const ConstexprIterator& rhs) {
485 assert(!lhs.moved_from_ && !rhs.moved_from_);
486 return lhs.ptr_ != rhs.ptr_;
487 }
488
operator --()489 constexpr ConstexprIterator& operator--() {
490 assert(!moved_from_);
491
492 --ptr_;
493 return *this;
494 }
495
operator --(int)496 constexpr ConstexprIterator operator--(int) {
497 assert(!moved_from_);
498
499 auto tmp = *this;
500 --*this;
501 return tmp;
502 }
503
operator +=(difference_type n)504 constexpr ConstexprIterator& operator+=(difference_type n) {
505 assert(!moved_from_);
506
507 ptr_ += n;
508 return *this;
509 }
510
operator -=(difference_type n)511 constexpr ConstexprIterator& operator-=(difference_type n) {
512 assert(!moved_from_);
513
514 ptr_ -= n;
515 return *this;
516 }
517
operator [](difference_type i) const518 constexpr Reference operator[](difference_type i) const {
519 return Reference(*(ptr_ + i));
520 }
521
operator <=>(const ConstexprIterator & lhs,const ConstexprIterator & rhs)522 friend constexpr auto operator<=>(const ConstexprIterator& lhs, const ConstexprIterator& rhs) {
523 assert(!lhs.moved_from_ && !rhs.moved_from_);
524 return lhs.ptr_ <=> rhs.ptr_;
525 }
526
operator +(const ConstexprIterator & lhs,difference_type n)527 friend constexpr ConstexprIterator operator+(const ConstexprIterator& lhs, difference_type n) {
528 assert(!lhs.moved_from_);
529 return ConstexprIterator(lhs.ptr_ + n);
530 }
531
operator +(difference_type n,const ConstexprIterator & lhs)532 friend constexpr ConstexprIterator operator+(difference_type n, const ConstexprIterator& lhs) {
533 assert(!lhs.moved_from_);
534 return ConstexprIterator(n + lhs.ptr_);
535 }
536
operator -(const ConstexprIterator & lhs,difference_type n)537 friend constexpr ConstexprIterator operator-(const ConstexprIterator& lhs, difference_type n) {
538 assert(!lhs.moved_from_);
539 return ConstexprIterator(lhs.ptr_ - n);
540 }
541
operator -(ConstexprIterator lhs,ConstexprIterator rhs)542 friend constexpr difference_type operator-(ConstexprIterator lhs, ConstexprIterator rhs) {
543 assert(!lhs.moved_from_ && !rhs.moved_from_);
544 return static_cast<int>(lhs.ptr_ - rhs.ptr_);
545 }
546 };
547
548 #endif // TEST_STD_VER > 17
549
550 template <class T, std::size_t StorageSize = 32>
551 class Input {
552 std::size_t size_ = 0;
553 T values_[StorageSize] = {};
554
555 public:
556 template <std::size_t N>
Input(std::array<T,N> from)557 TEST_CONSTEXPR_CXX20 Input(std::array<T, N> from) {
558 static_assert(N <= StorageSize, "");
559
560 std::copy(from.begin(), from.end(), begin());
561 size_ = N;
562 }
563
begin()564 TEST_CONSTEXPR_CXX20 T* begin() { return values_; }
end()565 TEST_CONSTEXPR_CXX20 T* end() { return values_ + size_; }
size() const566 TEST_CONSTEXPR_CXX20 std::size_t size() const { return size_; }
567 };
568
569 // TODO: extend `Value` and `Reference` so that it's possible to pass plain integers to all the algorithms.
570
571 // Several generic inputs that are useful for many algorithms. Provides two unsorted sequences with and without
572 // duplicates, with positive and negative values; and a few corner cases, like an empty sequence, a sequence of all
573 // duplicates, and so on.
574 template <class Iter>
get_simple_in()575 TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_simple_in() {
576 using T = typename Iter::value_type;
577 std::array<Input<T>, 8> result = {
578 Input<T>({std::array<T, 0>{ }}),
579 Input<T>({std::array<T, 1>{ T{1} }}),
580 Input<T>({std::array<T, 1>{ T{-1} }}),
581 Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
582 Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
583 Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
584 Input<T>({std::array<T, 9>{ T{-8}, {6}, {3}, {2}, {1}, {5}, {-4}, {-9}, {3} }}),
585 Input<T>({std::array<T, 9>{ T{-8}, {3}, {3}, {2}, {5}, {-4}, {-4}, {-4}, {1} }}),
586 };
587 return result;
588 }
589
590 // Sorted inputs of varying lengths.
591 template <class Iter>
get_sorted_in()592 TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_sorted_in() {
593 using T = typename Iter::value_type;
594 std::array<Input<T>, 8> result = {
595 Input<T>({std::array<T, 0>{ }}),
596 Input<T>({std::array<T, 1>{ T{1} }}),
597 Input<T>({std::array<T, 1>{ T{-1} }}),
598 Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
599 Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
600 Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
601 Input<T>({std::array<T, 8>{ T{-8}, {-5}, {-3}, {-1}, {1}, {4}, {5}, {9} }}),
602 Input<T>({std::array<T, 11>{ T{-8}, {-5}, {-3}, {-3}, {-1}, {1}, {4}, {5}, {5}, {9}, {9} }}),
603 };
604 return result;
605 }
606
607 // Inputs for testing `std::sort`. These have been manually verified to exercise all internal functions in `std::sort`
608 // except the branchless sort ones (which can't be triggered with proxy arrays).
609 template <class Iter>
get_sort_test_in()610 TEST_CONSTEXPR_CXX20 std::array<Input<typename Iter::value_type>, 8> get_sort_test_in() {
611 using T = typename Iter::value_type;
612 std::array<Input<T>, 8> result = {
613 Input<T>({std::array<T, 0>{ }}),
614 Input<T>({std::array<T, 1>{ T{1} }}),
615 Input<T>({std::array<T, 1>{ T{-1} }}),
616 Input<T>({std::array<T, 2>{ T{-1}, {1} }}),
617 Input<T>({std::array<T, 3>{ T{1}, {1}, {1} }}),
618 Input<T>({std::array<T, 3>{ T{-1}, {-1}, {-1} }}),
619 Input<T>({std::array<T, 8>{ T{-8}, {-5}, {-3}, {-1}, {1}, {4}, {5}, {9} }}),
620 Input<T>({std::array<T, 11>{ T{-8}, {-5}, {-3}, {-3}, {-1}, {1}, {4}, {5}, {5}, {9}, {9} }}),
621 };
622 return result;
623 }
624
625 template <class Input, std::size_t N, class Func>
test(std::array<Input,N> inputs,Func func)626 TEST_CONSTEXPR_CXX20 void test(std::array<Input, N> inputs, Func func) {
627 for (auto&& in : inputs) {
628 func(in.begin(), in.end());
629 }
630 }
631
632 template <class Input, std::size_t N, class Func>
test_n(std::array<Input,N> inputs,Func func)633 TEST_CONSTEXPR_CXX20 void test_n(std::array<Input, N> inputs, Func func) {
634 for (auto&& in : inputs) {
635 func(in.begin(), in.size());
636 }
637 }
638
to_int(int x)639 constexpr int to_int(int x) { return x; }
to_int(LifetimeIterator::Value x)640 int to_int(LifetimeIterator::Value x) { return x.i_; }
641
rand_gen()642 std::mt19937 rand_gen() { return std::mt19937(); }
643
644 template <class Iter>
test()645 TEST_CONSTEXPR_CXX20 bool test() {
646 using T = typename Iter::value_type;
647
648 auto is_neg = [](const T& val) { return to_int(val) < 0; };
649 auto gen = [] { return T{42}; };
650 auto identity = [] (T val) -> T { return val; };
651
652 constexpr int N = 32;
653 std::array<T, N> output;
654 auto out = output.begin();
655 T x{1};
656 T y{3};
657
658 auto simple_in = get_simple_in<Iter>();
659 auto sorted_in = get_sorted_in<Iter>();
660 auto sort_test_in = get_sort_test_in<Iter>();
661
662 using I = Iter;
663
664 test(simple_in, [&](I b, I e) { (void) std::any_of(b, e, is_neg); });
665 test(simple_in, [&](I b, I e) { (void) std::all_of(b, e, is_neg); });
666 test(simple_in, [&](I b, I e) { (void) std::none_of(b, e, is_neg); });
667 test(simple_in, [&](I b, I e) { (void) std::find(b, e, T{1}); });
668 test(simple_in, [&](I b, I e) { (void) std::find_if(b, e, is_neg); });
669 test(simple_in, [&](I b, I e) { (void) std::find_if_not(b, e, is_neg); });
670 // TODO: find_first_of
671 test(simple_in, [&](I b, I e) { (void) std::adjacent_find(b, e); });
672 // TODO: mismatch
673 // TODO: equal
674 // TODO: lexicographical_compare
675 // TODO: partition_point
676 test(sorted_in, [&](I b, I e) { (void) std::lower_bound(b, e, x); });
677 test(sorted_in, [&](I b, I e) { (void) std::upper_bound(b, e, x); });
678 test(sorted_in, [&](I b, I e) { (void) std::equal_range(b, e, x); });
679 test(sorted_in, [&](I b, I e) { (void) std::binary_search(b, e, x); });
680 // `min`, `max` and `minmax` don't use iterators.
681 test(simple_in, [&](I b, I e) { (void) std::min_element(b, e); });
682 test(simple_in, [&](I b, I e) { (void) std::max_element(b, e); });
683 test(simple_in, [&](I b, I e) { (void) std::minmax_element(b, e); });
684 test(simple_in, [&](I b, I e) { (void) std::count(b, e, x); });
685 test(simple_in, [&](I b, I e) { (void) std::count_if(b, e, is_neg); });
686 // TODO: search
687 // TODO: search_n
688 // TODO: find_end
689 // TODO: is_partitioned
690 // TODO: is_sorted
691 // TODO: is_sorted_until
692 // TODO: includes
693 // TODO: is_heap
694 // TODO: is_heap_until
695 // `clamp` doesn't use iterators.
696 // TODO: is_permutation
697 test(simple_in, [&](I b, I e) { (void) std::for_each(b, e, is_neg); });
698 #if TEST_STD_VER > 14
699 test_n(simple_in, [&](I b, std::size_t n) { (void) std::for_each_n(b, n, is_neg); });
700 #endif
701 test(simple_in, [&](I b, I e) { (void) std::copy(b, e, out); });
702 test_n(simple_in, [&](I b, std::size_t n) { (void) std::copy_n(b, n, out); });
703 test(simple_in, [&](I b, I e) { (void) std::copy_backward(b, e, out + N); });
704 test(simple_in, [&](I b, I e) { (void) std::copy_if(b, e, out, is_neg); });
705 test(simple_in, [&](I b, I e) { (void) std::move(b, e, out); });
706 test(simple_in, [&](I b, I e) { (void) std::move_backward(b, e, out + N); });
707 test(simple_in, [&](I b, I e) { (void) std::transform(b, e, out, identity); });
708 test(simple_in, [&](I b, I e) { (void) std::generate(b, e, gen); });
709 test_n(simple_in, [&](I b, std::size_t n) { (void) std::generate_n(b, n, gen); });
710 test(simple_in, [&](I b, I e) { (void) std::remove_copy(b, e, out, x); });
711 test(simple_in, [&](I b, I e) { (void) std::remove_copy_if(b, e, out, is_neg); });
712 test(simple_in, [&](I b, I e) { (void) std::replace(b, e, x, y); });
713 test(simple_in, [&](I b, I e) { (void) std::replace_if(b, e, is_neg, y); });
714 test(simple_in, [&](I b, I e) { (void) std::replace_copy(b, e, out, x, y); });
715 test(simple_in, [&](I b, I e) { (void) std::replace_copy_if(b, e, out, is_neg, y); });
716 // TODO: swap_ranges
717 test(simple_in, [&](I b, I e) { (void) std::reverse_copy(b, e, out); });
718 // TODO: rotate_copy
719 // TODO: sample
720 // TODO: unique_copy
721 // TODO: partition_copy
722 // TODO: partial_sort_copy
723 // TODO: merge
724 // TODO: set_difference
725 // TODO: set_intersection
726 // TODO: set_symmetric_difference
727 // TODO: set_union
728 test(simple_in, [&](I b, I e) { (void) std::remove(b, e, x); });
729 test(simple_in, [&](I b, I e) { (void) std::remove_if(b, e, is_neg); });
730 test(simple_in, [&](I b, I e) { (void) std::reverse(b, e); });
731 // TODO: rotate
732 if (!TEST_IS_CONSTANT_EVALUATED)
733 test(simple_in, [&](I b, I e) { (void) std::shuffle(b, e, rand_gen()); });
734 // TODO: unique
735 test(simple_in, [&](I b, I e) { (void) std::partition(b, e, is_neg); });
736 if (!TEST_IS_CONSTANT_EVALUATED)
737 test(simple_in, [&](I b, I e) { (void) std::stable_partition(b, e, is_neg); });
738 if (!TEST_IS_CONSTANT_EVALUATED)
739 test(sort_test_in, [&](I b, I e) { (void) std::sort(b, e); });
740 if (!TEST_IS_CONSTANT_EVALUATED)
741 test(sort_test_in, [&](I b, I e) { (void) std::stable_sort(b, e); });
742 // TODO: partial_sort
743 // TODO: nth_element
744 // TODO: inplace_merge
745 test(simple_in, [&](I b, I e) { (void) std::make_heap(b, e); });
746 // TODO: push_heap
747 // TODO: pop_heap
748 // TODO: sort_heap
749 test(simple_in, [&](I b, I e) { (void) std::prev_permutation(b, e); });
750 test(simple_in, [&](I b, I e) { (void) std::next_permutation(b, e); });
751
752 // TODO: algorithms in `<numeric>`
753 // TODO: algorithms in `<memory>`
754
755 return true;
756 }
757
test_all()758 void test_all() {
759 test<LifetimeIterator>();
760 #if TEST_STD_VER > 17 // Most algorithms are only `constexpr` starting from C++20.
761 static_assert(test<ConstexprIterator>());
762 #endif
763 }
764
main(int,char **)765 int main(int, char**) {
766 test_all();
767
768 return 0;
769 }
770