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.
33class LifetimeIterator {
34 // The cache simply tracks addresses of the local variables.
35 class LifetimeCache {
36 std::set<const void*> cache_;
37
38 public:
39 bool contains(const void* ptr) const { return cache_.find(ptr) != cache_.end(); }
40
41 void insert(const void* ptr) {
42 assert(!contains(ptr));
43 cache_.insert(ptr);
44 }
45
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
57 Value() { lifetime_cache.insert(ptr: this); }
58 Value(int i) : i_(i) { lifetime_cache.insert(ptr: this); }
59 ~Value() { lifetime_cache.erase(ptr: this); }
60
61 Value(const Value& rhs) : i_(rhs.i_) {
62 assert(lifetime_cache.contains(&rhs));
63 assert(!rhs.moved_from_);
64
65 lifetime_cache.insert(ptr: this);
66 }
67
68 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(ptr: this);
76 }
77
78 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
88 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
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
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
120 Reference(Value& v) : v_(&v) {
121 lifetime_cache.insert(ptr: this);
122 }
123
124 ~Reference() {
125 lifetime_cache.erase(ptr: this);
126 }
127
128 Reference(const Reference& rhs) : v_(rhs.v_) {
129 assert(lifetime_cache.contains(&rhs));
130 assert(!rhs.moved_from_);
131
132 lifetime_cache.insert(ptr: this);
133 }
134
135 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(ptr: this);
142 }
143
144 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
154 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
166 operator Value() const {
167 assert(lifetime_cache.contains(this));
168 assert(!moved_from_);
169
170 return *v_;
171 }
172
173 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
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
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
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;
215 LifetimeIterator(Value* ptr) : ptr_(ptr) {}
216
217 LifetimeIterator(const LifetimeIterator& rhs) : ptr_(rhs.ptr_) {
218 assert(!rhs.moved_from_);
219 }
220
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
230 LifetimeIterator(LifetimeIterator&& rhs) noexcept : ptr_(rhs.ptr_) {
231 assert(!rhs.moved_from_);
232 rhs.moved_from_ = true;
233 rhs.ptr_ = nullptr;
234 }
235
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
247 Reference operator*() const {
248 assert(!moved_from_);
249 return Reference(*ptr_);
250 }
251
252 LifetimeIterator& operator++() {
253 assert(!moved_from_);
254
255 ++ptr_;
256 return *this;
257 }
258
259 LifetimeIterator operator++(int) {
260 assert(!moved_from_);
261
262 auto tmp = *this;
263 ++*this;
264 return tmp;
265 }
266
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 }
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
276 LifetimeIterator& operator--() {
277 assert(!moved_from_);
278
279 --ptr_;
280 return *this;
281 }
282
283 LifetimeIterator operator--(int) {
284 assert(!moved_from_);
285
286 auto tmp = *this;
287 --*this;
288 return tmp;
289 }
290
291 LifetimeIterator& operator+=(difference_type n) {
292 assert(!moved_from_);
293
294 ptr_ += n;
295 return *this;
296 }
297
298 LifetimeIterator& operator-=(difference_type n) {
299 assert(!moved_from_);
300
301 ptr_ -= n;
302 return *this;
303 }
304
305 Reference operator[](difference_type i) const {
306 assert(!moved_from_);
307 return Reference(*(ptr_ + i));
308 }
309
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
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
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
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
330 friend LifetimeIterator operator+(const LifetimeIterator& lhs, difference_type n) {
331 assert(!lhs.moved_from_);
332 return LifetimeIterator(lhs.ptr_ + n);
333 }
334
335 friend LifetimeIterator operator+(difference_type n, const LifetimeIterator& lhs) {
336 assert(!lhs.moved_from_);
337 return LifetimeIterator(n + lhs.ptr_);
338 }
339
340 friend LifetimeIterator operator-(const LifetimeIterator& lhs, difference_type n) {
341 assert(!lhs.moved_from_);
342 return LifetimeIterator(lhs.ptr_ - n);
343 }
344
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
353LifetimeIterator::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).
358class ConstexprIterator {
359 public:
360 struct Reference {
361 int* v_;
362 bool moved_from_ = false; // Check for double moves and reads after moving.
363
364 constexpr Reference(int& v) : v_(&v) { }
365
366 constexpr Reference(const Reference& rhs) = default;
367 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
375 constexpr Reference(Reference&& rhs) noexcept : v_(rhs.v_) {
376 assert(!rhs.moved_from_);
377 rhs.moved_from_ = true;
378 }
379
380 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
389 constexpr operator int() const {
390 assert(!moved_from_);
391 return *v_;
392 }
393
394 constexpr Reference& operator=(int v) {
395 *v_ = v;
396 moved_from_ = false;
397
398 return *this;
399 }
400
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
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
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;
427 constexpr ConstexprIterator(int* ptr) : ptr_(ptr) {}
428
429 constexpr ConstexprIterator(const ConstexprIterator& rhs) : ptr_(rhs.ptr_) {
430 assert(!rhs.moved_from_);
431 }
432
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
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
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
459 constexpr Reference operator*() const {
460 assert(!moved_from_);
461 return Reference(*ptr_);
462 }
463
464 constexpr ConstexprIterator& operator++() {
465 assert(!moved_from_);
466
467 ++ptr_;
468 return *this;
469 }
470
471 constexpr ConstexprIterator operator++(int) {
472 assert(!moved_from_);
473
474 auto tmp = *this;
475 ++*this;
476 return tmp;
477 }
478
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
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
489 constexpr ConstexprIterator& operator--() {
490 assert(!moved_from_);
491
492 --ptr_;
493 return *this;
494 }
495
496 constexpr ConstexprIterator operator--(int) {
497 assert(!moved_from_);
498
499 auto tmp = *this;
500 --*this;
501 return tmp;
502 }
503
504 constexpr ConstexprIterator& operator+=(difference_type n) {
505 assert(!moved_from_);
506
507 ptr_ += n;
508 return *this;
509 }
510
511 constexpr ConstexprIterator& operator-=(difference_type n) {
512 assert(!moved_from_);
513
514 ptr_ -= n;
515 return *this;
516 }
517
518 constexpr Reference operator[](difference_type i) const {
519 return Reference(*(ptr_ + i));
520 }
521
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
527 friend constexpr ConstexprIterator operator+(const ConstexprIterator& lhs, difference_type n) {
528 assert(!lhs.moved_from_);
529 return ConstexprIterator(lhs.ptr_ + n);
530 }
531
532 friend constexpr ConstexprIterator operator+(difference_type n, const ConstexprIterator& lhs) {
533 assert(!lhs.moved_from_);
534 return ConstexprIterator(n + lhs.ptr_);
535 }
536
537 friend constexpr ConstexprIterator operator-(const ConstexprIterator& lhs, difference_type n) {
538 assert(!lhs.moved_from_);
539 return ConstexprIterator(lhs.ptr_ - n);
540 }
541
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
550template <class T, std::size_t StorageSize = 32>
551class Input {
552 std::size_t size_ = 0;
553 T values_[StorageSize] = {};
554
555public:
556 template <std::size_t N>
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
564 TEST_CONSTEXPR_CXX20 T* begin() { return values_; }
565 TEST_CONSTEXPR_CXX20 T* end() { return values_ + size_; }
566 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.
574template <class Iter>
575TEST_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.
591template <class Iter>
592TEST_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).
609template <class Iter>
610TEST_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
625template <class Input, std::size_t N, class Func>
626TEST_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
632template <class Input, std::size_t N, class Func>
633TEST_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
639constexpr int to_int(int x) { return x; }
640int to_int(LifetimeIterator::Value x) { return x.i_; }
641
642std::mt19937 rand_gen() { return std::mt19937(); }
643
644template <class Iter>
645TEST_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
758void 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
765int main(int, char**) {
766 test_all();
767
768 return 0;
769}
770

source code of libcxx/test/std/algorithms/robust_against_proxy_iterators_lifetime_bugs.pass.cpp