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

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