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#ifndef SUPPORT_TEST_ITERATORS_H
10#define SUPPORT_TEST_ITERATORS_H
11
12#include <cassert>
13#include <concepts>
14#include <cstdint>
15#include <iterator>
16#include <ranges>
17#include <stdexcept>
18#include <type_traits>
19#include <utility>
20
21#include "test_macros.h"
22#include "type_algorithms.h"
23
24
25// This iterator meets C++20's Cpp17OutputIterator requirements, as described
26// in Table 90 ([output.iterators]).
27template <class It>
28class cpp17_output_iterator
29{
30 It it_;
31
32 template <class U> friend class cpp17_output_iterator;
33public:
34 typedef std::output_iterator_tag iterator_category;
35 typedef void value_type;
36 typedef typename std::iterator_traits<It>::difference_type difference_type;
37 typedef It pointer;
38 typedef typename std::iterator_traits<It>::reference reference;
39
40 TEST_CONSTEXPR explicit cpp17_output_iterator(It it) : it_(std::move(it)) {}
41
42 template <class U>
43 TEST_CONSTEXPR cpp17_output_iterator(const cpp17_output_iterator<U>& u) : it_(u.it_) {}
44
45 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
46 TEST_CONSTEXPR_CXX14 cpp17_output_iterator(cpp17_output_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); }
47
48 TEST_CONSTEXPR reference operator*() const {return *it_;}
49
50 TEST_CONSTEXPR_CXX14 cpp17_output_iterator& operator++() {++it_; return *this;}
51 TEST_CONSTEXPR_CXX14 cpp17_output_iterator operator++(int) {return cpp17_output_iterator(it_++);}
52
53 friend TEST_CONSTEXPR It base(const cpp17_output_iterator& i) { return i.it_; }
54
55 template <class T>
56 void operator,(T const &) = delete;
57};
58#if TEST_STD_VER > 14
59template <class It>
60cpp17_output_iterator(It) -> cpp17_output_iterator<It>;
61#endif
62
63#if TEST_STD_VER > 17
64 static_assert(std::output_iterator<cpp17_output_iterator<int*>, int>);
65#endif
66
67// This iterator meets C++20's Cpp17InputIterator requirements, as described
68// in Table 89 ([input.iterators]).
69template <class It, class ItTraits = It>
70class cpp17_input_iterator
71{
72 typedef std::iterator_traits<ItTraits> Traits;
73 It it_;
74
75 template <class U, class T> friend class cpp17_input_iterator;
76public:
77 typedef std::input_iterator_tag iterator_category;
78 typedef typename Traits::value_type value_type;
79 typedef typename Traits::difference_type difference_type;
80 typedef It pointer;
81 typedef typename Traits::reference reference;
82
83 TEST_CONSTEXPR explicit cpp17_input_iterator(It it) : it_(it) {}
84
85 template <class U, class T>
86 TEST_CONSTEXPR cpp17_input_iterator(const cpp17_input_iterator<U, T>& u) : it_(u.it_) {}
87
88 template <class U, class T, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
89 TEST_CONSTEXPR_CXX14 cpp17_input_iterator(cpp17_input_iterator<U, T>&& u) : it_(u.it_) { u.it_ = U(); }
90
91 TEST_CONSTEXPR reference operator*() const {return *it_;}
92
93 TEST_CONSTEXPR_CXX14 cpp17_input_iterator& operator++() {++it_; return *this;}
94 TEST_CONSTEXPR_CXX14 cpp17_input_iterator operator++(int) {return cpp17_input_iterator(it_++);}
95
96 friend TEST_CONSTEXPR bool operator==(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ == y.it_;}
97 friend TEST_CONSTEXPR bool operator!=(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ != y.it_;}
98
99 friend TEST_CONSTEXPR It base(const cpp17_input_iterator& i) { return i.it_; }
100
101 template <class T>
102 void operator,(T const &) = delete;
103};
104#if TEST_STD_VER > 14
105template <class It>
106cpp17_input_iterator(It) -> cpp17_input_iterator<It>;
107#endif
108
109#if TEST_STD_VER > 17
110 static_assert(std::input_iterator<cpp17_input_iterator<int*>>);
111#endif
112
113template <class It>
114class forward_iterator
115{
116 It it_;
117
118 template <class U> friend class forward_iterator;
119public:
120 typedef std::forward_iterator_tag iterator_category;
121 typedef typename std::iterator_traits<It>::value_type value_type;
122 typedef typename std::iterator_traits<It>::difference_type difference_type;
123 typedef It pointer;
124 typedef typename std::iterator_traits<It>::reference reference;
125
126 TEST_CONSTEXPR forward_iterator() : it_() {}
127 TEST_CONSTEXPR explicit forward_iterator(It it) : it_(it) {}
128
129 template <class U>
130 TEST_CONSTEXPR forward_iterator(const forward_iterator<U>& u) : it_(u.it_) {}
131
132 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
133 TEST_CONSTEXPR_CXX14 forward_iterator(forward_iterator<U>&& other) : it_(other.it_) { other.it_ = U(); }
134
135 TEST_CONSTEXPR reference operator*() const {return *it_;}
136
137 TEST_CONSTEXPR_CXX14 forward_iterator& operator++() {++it_; return *this;}
138 TEST_CONSTEXPR_CXX14 forward_iterator operator++(int) {return forward_iterator(it_++);}
139
140 friend TEST_CONSTEXPR bool operator==(const forward_iterator& x, const forward_iterator& y) {return x.it_ == y.it_;}
141 friend TEST_CONSTEXPR bool operator!=(const forward_iterator& x, const forward_iterator& y) {return x.it_ != y.it_;}
142
143 friend TEST_CONSTEXPR It base(const forward_iterator& i) { return i.it_; }
144
145 template <class T>
146 void operator,(T const &) = delete;
147};
148#if TEST_STD_VER > 14
149template <class It>
150forward_iterator(It) -> forward_iterator<It>;
151#endif
152
153template <class It>
154class bidirectional_iterator
155{
156 It it_;
157
158 template <class U> friend class bidirectional_iterator;
159public:
160 typedef std::bidirectional_iterator_tag iterator_category;
161 typedef typename std::iterator_traits<It>::value_type value_type;
162 typedef typename std::iterator_traits<It>::difference_type difference_type;
163 typedef It pointer;
164 typedef typename std::iterator_traits<It>::reference reference;
165
166 TEST_CONSTEXPR bidirectional_iterator() : it_() {}
167 TEST_CONSTEXPR explicit bidirectional_iterator(It it) : it_(it) {}
168
169 template <class U>
170 TEST_CONSTEXPR bidirectional_iterator(const bidirectional_iterator<U>& u) : it_(u.it_) {}
171
172 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
173 TEST_CONSTEXPR_CXX14 bidirectional_iterator(bidirectional_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); }
174
175 TEST_CONSTEXPR reference operator*() const {return *it_;}
176
177 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator++() {++it_; return *this;}
178 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator--() {--it_; return *this;}
179 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator++(int) {return bidirectional_iterator(it_++);}
180 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator--(int) {return bidirectional_iterator(it_--);}
181
182 friend TEST_CONSTEXPR bool operator==(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ == y.it_;}
183 friend TEST_CONSTEXPR bool operator!=(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ != y.it_;}
184
185 friend TEST_CONSTEXPR It base(const bidirectional_iterator& i) { return i.it_; }
186
187 template <class T>
188 void operator,(T const &) = delete;
189};
190#if TEST_STD_VER > 14
191template <class It>
192bidirectional_iterator(It) -> bidirectional_iterator<It>;
193#endif
194
195template <class It>
196class random_access_iterator
197{
198 It it_;
199
200 template <class U> friend class random_access_iterator;
201public:
202 typedef std::random_access_iterator_tag iterator_category;
203 typedef typename std::iterator_traits<It>::value_type value_type;
204 typedef typename std::iterator_traits<It>::difference_type difference_type;
205 typedef It pointer;
206 typedef typename std::iterator_traits<It>::reference reference;
207
208 TEST_CONSTEXPR random_access_iterator() : it_() {}
209 TEST_CONSTEXPR explicit random_access_iterator(It it) : it_(it) {}
210
211 template <class U>
212 TEST_CONSTEXPR random_access_iterator(const random_access_iterator<U>& u) : it_(u.it_) {}
213
214 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
215 TEST_CONSTEXPR_CXX14 random_access_iterator(random_access_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); }
216
217 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
218 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];}
219
220 TEST_CONSTEXPR_CXX14 random_access_iterator& operator++() {++it_; return *this;}
221 TEST_CONSTEXPR_CXX14 random_access_iterator& operator--() {--it_; return *this;}
222 TEST_CONSTEXPR_CXX14 random_access_iterator operator++(int) {return random_access_iterator(it_++);}
223 TEST_CONSTEXPR_CXX14 random_access_iterator operator--(int) {return random_access_iterator(it_--);}
224
225 TEST_CONSTEXPR_CXX14 random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;}
226 TEST_CONSTEXPR_CXX14 random_access_iterator& operator-=(difference_type n) {it_ -= n; return *this;}
227 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(random_access_iterator x, difference_type n) {x += n; return x;}
228 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(difference_type n, random_access_iterator x) {x += n; return x;}
229 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator-(random_access_iterator x, difference_type n) {x -= n; return x;}
230 friend TEST_CONSTEXPR difference_type operator-(random_access_iterator x, random_access_iterator y) {return x.it_ - y.it_;}
231
232 friend TEST_CONSTEXPR bool operator==(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ == y.it_;}
233 friend TEST_CONSTEXPR bool operator!=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ != y.it_;}
234 friend TEST_CONSTEXPR bool operator< (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ < y.it_;}
235 friend TEST_CONSTEXPR bool operator<=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ <= y.it_;}
236 friend TEST_CONSTEXPR bool operator> (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ > y.it_;}
237 friend TEST_CONSTEXPR bool operator>=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ >= y.it_;}
238
239 friend TEST_CONSTEXPR It base(const random_access_iterator& i) { return i.it_; }
240
241 template <class T>
242 void operator,(T const &) = delete;
243};
244#if TEST_STD_VER > 14
245template <class It>
246random_access_iterator(It) -> random_access_iterator<It>;
247#endif
248
249#if TEST_STD_VER > 17
250
251template <std::random_access_iterator It>
252class cpp20_random_access_iterator {
253 It it_;
254
255 template <std::random_access_iterator>
256 friend class cpp20_random_access_iterator;
257
258public:
259 using iterator_category = std::input_iterator_tag;
260 using iterator_concept = std::random_access_iterator_tag;
261 using value_type = typename std::iterator_traits<It>::value_type;
262 using difference_type = typename std::iterator_traits<It>::difference_type;
263
264 constexpr cpp20_random_access_iterator() : it_() {}
265 constexpr explicit cpp20_random_access_iterator(It it) : it_(it) {}
266
267 template <class U>
268 constexpr cpp20_random_access_iterator(const cpp20_random_access_iterator<U>& u) : it_(u.it_) {}
269
270 template <class U>
271 constexpr cpp20_random_access_iterator(cpp20_random_access_iterator<U>&& u) : it_(u.it_) {
272 u.it_ = U();
273 }
274
275 constexpr decltype(auto) operator*() const { return *it_; }
276 constexpr decltype(auto) operator[](difference_type n) const { return it_[n]; }
277
278 constexpr cpp20_random_access_iterator& operator++() {
279 ++it_;
280 return *this;
281 }
282 constexpr cpp20_random_access_iterator& operator--() {
283 --it_;
284 return *this;
285 }
286 constexpr cpp20_random_access_iterator operator++(int) { return cpp20_random_access_iterator(it_++); }
287 constexpr cpp20_random_access_iterator operator--(int) { return cpp20_random_access_iterator(it_--); }
288
289 constexpr cpp20_random_access_iterator& operator+=(difference_type n) {
290 it_ += n;
291 return *this;
292 }
293 constexpr cpp20_random_access_iterator& operator-=(difference_type n) {
294 it_ -= n;
295 return *this;
296 }
297 friend constexpr cpp20_random_access_iterator operator+(cpp20_random_access_iterator x, difference_type n) {
298 x += n;
299 return x;
300 }
301 friend constexpr cpp20_random_access_iterator operator+(difference_type n, cpp20_random_access_iterator x) {
302 x += n;
303 return x;
304 }
305 friend constexpr cpp20_random_access_iterator operator-(cpp20_random_access_iterator x, difference_type n) {
306 x -= n;
307 return x;
308 }
309 friend constexpr difference_type operator-(cpp20_random_access_iterator x, cpp20_random_access_iterator y) {
310 return x.it_ - y.it_;
311 }
312
313 friend constexpr bool operator==(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {
314 return x.it_ == y.it_;
315 }
316 friend constexpr bool operator!=(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {
317 return x.it_ != y.it_;
318 }
319 friend constexpr bool operator<(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {
320 return x.it_ < y.it_;
321 }
322 friend constexpr bool operator<=(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {
323 return x.it_ <= y.it_;
324 }
325 friend constexpr bool operator>(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {
326 return x.it_ > y.it_;
327 }
328 friend constexpr bool operator>=(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {
329 return x.it_ >= y.it_;
330 }
331
332 friend constexpr It base(const cpp20_random_access_iterator& i) { return i.it_; }
333
334 template <class T>
335 void operator,(T const&) = delete;
336};
337template <class It>
338cpp20_random_access_iterator(It) -> cpp20_random_access_iterator<It>;
339
340static_assert(std::random_access_iterator<cpp20_random_access_iterator<int*>>);
341
342template <class It>
343class contiguous_iterator
344{
345 static_assert(std::is_pointer_v<It>, "Things probably break in this case");
346
347 It it_;
348
349 template <class U> friend class contiguous_iterator;
350public:
351 typedef std::contiguous_iterator_tag iterator_category;
352 typedef typename std::iterator_traits<It>::value_type value_type;
353 typedef typename std::iterator_traits<It>::difference_type difference_type;
354 typedef It pointer;
355 typedef typename std::iterator_traits<It>::reference reference;
356 typedef typename std::remove_pointer<It>::type element_type;
357
358 TEST_CONSTEXPR_CXX14 It base() const {return it_;}
359
360 TEST_CONSTEXPR_CXX14 contiguous_iterator() : it_() {}
361 TEST_CONSTEXPR_CXX14 explicit contiguous_iterator(It it) : it_(it) {}
362
363 template <class U>
364 TEST_CONSTEXPR_CXX14 contiguous_iterator(const contiguous_iterator<U>& u) : it_(u.it_) {}
365
366 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
367 constexpr contiguous_iterator(contiguous_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); }
368
369 TEST_CONSTEXPR reference operator*() const {return *it_;}
370 TEST_CONSTEXPR pointer operator->() const {return it_;}
371 TEST_CONSTEXPR reference operator[](difference_type n) const {return it_[n];}
372
373 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator++() {++it_; return *this;}
374 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator--() {--it_; return *this;}
375 TEST_CONSTEXPR_CXX14 contiguous_iterator operator++(int) {return contiguous_iterator(it_++);}
376 TEST_CONSTEXPR_CXX14 contiguous_iterator operator--(int) {return contiguous_iterator(it_--);}
377
378 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;}
379 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;}
380 friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(contiguous_iterator x, difference_type n) {x += n; return x;}
381 friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(difference_type n, contiguous_iterator x) {x += n; return x;}
382 friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator-(contiguous_iterator x, difference_type n) {x -= n; return x;}
383 friend TEST_CONSTEXPR difference_type operator-(contiguous_iterator x, contiguous_iterator y) {return x.it_ - y.it_;}
384
385 friend TEST_CONSTEXPR bool operator==(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ == y.it_;}
386 friend TEST_CONSTEXPR bool operator!=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ != y.it_;}
387 friend TEST_CONSTEXPR bool operator< (const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ < y.it_;}
388 friend TEST_CONSTEXPR bool operator<=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ <= y.it_;}
389 friend TEST_CONSTEXPR bool operator> (const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ > y.it_;}
390 friend TEST_CONSTEXPR bool operator>=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ >= y.it_;}
391
392 // Note no operator<=>, use three_way_contiguous_iterator for testing operator<=>
393
394 friend TEST_CONSTEXPR It base(const contiguous_iterator& i) { return i.it_; }
395
396 template <class T>
397 void operator,(T const &) = delete;
398};
399template <class It>
400contiguous_iterator(It) -> contiguous_iterator<It>;
401
402template <class It>
403class three_way_contiguous_iterator
404{
405 static_assert(std::is_pointer_v<It>, "Things probably break in this case");
406
407 It it_;
408
409 template <class U> friend class three_way_contiguous_iterator;
410public:
411 typedef std::contiguous_iterator_tag iterator_category;
412 typedef typename std::iterator_traits<It>::value_type value_type;
413 typedef typename std::iterator_traits<It>::difference_type difference_type;
414 typedef It pointer;
415 typedef typename std::iterator_traits<It>::reference reference;
416 typedef typename std::remove_pointer<It>::type element_type;
417
418 constexpr It base() const {return it_;}
419
420 constexpr three_way_contiguous_iterator() : it_() {}
421 constexpr explicit three_way_contiguous_iterator(It it) : it_(it) {}
422
423 template <class U>
424 constexpr three_way_contiguous_iterator(const three_way_contiguous_iterator<U>& u) : it_(u.it_) {}
425
426 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>
427 constexpr three_way_contiguous_iterator(three_way_contiguous_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); }
428
429 constexpr reference operator*() const {return *it_;}
430 constexpr pointer operator->() const {return it_;}
431 constexpr reference operator[](difference_type n) const {return it_[n];}
432
433 constexpr three_way_contiguous_iterator& operator++() {++it_; return *this;}
434 constexpr three_way_contiguous_iterator& operator--() {--it_; return *this;}
435 constexpr three_way_contiguous_iterator operator++(int) {return three_way_contiguous_iterator(it_++);}
436 constexpr three_way_contiguous_iterator operator--(int) {return three_way_contiguous_iterator(it_--);}
437
438 constexpr three_way_contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;}
439 constexpr three_way_contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;}
440 friend constexpr three_way_contiguous_iterator operator+(three_way_contiguous_iterator x, difference_type n) {x += n; return x;}
441 friend constexpr three_way_contiguous_iterator operator+(difference_type n, three_way_contiguous_iterator x) {x += n; return x;}
442 friend constexpr three_way_contiguous_iterator operator-(three_way_contiguous_iterator x, difference_type n) {x -= n; return x;}
443 friend constexpr difference_type operator-(three_way_contiguous_iterator x, three_way_contiguous_iterator y) {return x.it_ - y.it_;}
444
445 friend constexpr auto operator<=>(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ <=> y.it_;}
446 friend constexpr bool operator==(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ == y.it_;}
447
448 template <class T>
449 void operator,(T const &) = delete;
450};
451template <class It>
452three_way_contiguous_iterator(It) -> three_way_contiguous_iterator<It>;
453#endif // TEST_STD_VER > 17
454
455template <class Iter> // ADL base() for everything else (including pointers)
456TEST_CONSTEXPR Iter base(Iter i) { return i; }
457
458template <typename T>
459struct ThrowingIterator {
460 typedef std::bidirectional_iterator_tag iterator_category;
461 typedef std::ptrdiff_t difference_type;
462 typedef const T value_type;
463 typedef const T * pointer;
464 typedef const T & reference;
465
466 enum ThrowingAction { TAIncrement, TADecrement, TADereference, TAAssignment, TAComparison };
467
468 TEST_CONSTEXPR ThrowingIterator()
469 : begin_(nullptr), end_(nullptr), current_(nullptr), action_(TADereference), index_(0) {}
470 TEST_CONSTEXPR explicit ThrowingIterator(const T* first, const T* last, int index = 0,
471 ThrowingAction action = TADereference)
472 : begin_(first), end_(last), current_(first), action_(action), index_(index) {}
473 TEST_CONSTEXPR ThrowingIterator(const ThrowingIterator &rhs)
474 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_), action_(rhs.action_), index_(rhs.index_) {}
475
476 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator=(const ThrowingIterator& rhs) {
477 if (action_ == TAAssignment && --index_ < 0) {
478#ifndef TEST_HAS_NO_EXCEPTIONS
479 throw std::runtime_error("throw from iterator assignment");
480#else
481 assert(false);
482#endif
483 }
484 begin_ = rhs.begin_;
485 end_ = rhs.end_;
486 current_ = rhs.current_;
487 action_ = rhs.action_;
488 index_ = rhs.index_;
489 return *this;
490 }
491
492 TEST_CONSTEXPR_CXX14 reference operator*() const {
493 if (action_ == TADereference && --index_ < 0) {
494#ifndef TEST_HAS_NO_EXCEPTIONS
495 throw std::runtime_error("throw from iterator dereference");
496#else
497 assert(false);
498#endif
499 }
500 return *current_;
501 }
502
503 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator++() {
504 if (action_ == TAIncrement && --index_ < 0) {
505#ifndef TEST_HAS_NO_EXCEPTIONS
506 throw std::runtime_error("throw from iterator increment");
507#else
508 assert(false);
509#endif
510 }
511 ++current_;
512 return *this;
513 }
514
515 TEST_CONSTEXPR_CXX14 ThrowingIterator operator++(int) {
516 ThrowingIterator temp = *this;
517 ++(*this);
518 return temp;
519 }
520
521 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator--() {
522 if (action_ == TADecrement && --index_ < 0) {
523#ifndef TEST_HAS_NO_EXCEPTIONS
524 throw std::runtime_error("throw from iterator decrement");
525#else
526 assert(false);
527#endif
528 }
529 --current_;
530 return *this;
531 }
532
533 TEST_CONSTEXPR_CXX14 ThrowingIterator operator--(int) {
534 ThrowingIterator temp = *this;
535 --(*this);
536 return temp;
537 }
538
539 TEST_CONSTEXPR_CXX14 friend bool operator==(const ThrowingIterator& a, const ThrowingIterator& b) {
540 if (a.action_ == TAComparison && --a.index_ < 0) {
541#ifndef TEST_HAS_NO_EXCEPTIONS
542 throw std::runtime_error("throw from iterator comparison");
543#else
544 assert(false);
545#endif
546 }
547 bool atEndL = a.current_ == a.end_;
548 bool atEndR = b.current_ == b.end_;
549 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not.
550 if (atEndL) return true; // both are at the end (or empty)
551 return a.current_ == b.current_;
552 }
553
554 TEST_CONSTEXPR friend bool operator!=(const ThrowingIterator& a, const ThrowingIterator& b) {
555 return !(a == b);
556 }
557
558 template <class T2>
559 void operator,(T2 const &) = delete;
560
561private:
562 const T* begin_;
563 const T* end_;
564 const T* current_;
565 ThrowingAction action_;
566 mutable int index_;
567};
568
569template <typename T>
570struct NonThrowingIterator {
571 typedef std::bidirectional_iterator_tag iterator_category;
572 typedef std::ptrdiff_t difference_type;
573 typedef const T value_type;
574 typedef const T * pointer;
575 typedef const T & reference;
576
577 NonThrowingIterator()
578 : begin_(nullptr), end_(nullptr), current_(nullptr) {}
579 explicit NonThrowingIterator(const T *first, const T *last)
580 : begin_(first), end_(last), current_(first) {}
581 NonThrowingIterator(const NonThrowingIterator& rhs)
582 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_) {}
583
584 NonThrowingIterator& operator=(const NonThrowingIterator& rhs) TEST_NOEXCEPT {
585 begin_ = rhs.begin_;
586 end_ = rhs.end_;
587 current_ = rhs.current_;
588 return *this;
589 }
590
591 reference operator*() const TEST_NOEXCEPT {
592 return *current_;
593 }
594
595 NonThrowingIterator& operator++() TEST_NOEXCEPT {
596 ++current_;
597 return *this;
598 }
599
600 NonThrowingIterator operator++(int) TEST_NOEXCEPT {
601 NonThrowingIterator temp = *this;
602 ++(*this);
603 return temp;
604 }
605
606 NonThrowingIterator & operator--() TEST_NOEXCEPT {
607 --current_;
608 return *this;
609 }
610
611 NonThrowingIterator operator--(int) TEST_NOEXCEPT {
612 NonThrowingIterator temp = *this;
613 --(*this);
614 return temp;
615 }
616
617 friend bool operator==(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT {
618 bool atEndL = a.current_ == a.end_;
619 bool atEndR = b.current_ == b.end_;
620 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not.
621 if (atEndL) return true; // both are at the end (or empty)
622 return a.current_ == b.current_;
623 }
624
625 friend bool operator!=(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT {
626 return !(a == b);
627 }
628
629 template <class T2>
630 void operator,(T2 const &) = delete;
631
632private:
633 const T *begin_;
634 const T *end_;
635 const T *current_;
636};
637
638#if TEST_STD_VER > 17
639
640template <class It>
641class cpp20_input_iterator
642{
643 It it_;
644
645public:
646 using value_type = std::iter_value_t<It>;
647 using difference_type = std::iter_difference_t<It>;
648 using iterator_concept = std::input_iterator_tag;
649
650 constexpr explicit cpp20_input_iterator(It it) : it_(it) {}
651 cpp20_input_iterator(cpp20_input_iterator&&) = default;
652 cpp20_input_iterator& operator=(cpp20_input_iterator&&) = default;
653 constexpr decltype(auto) operator*() const { return *it_; }
654 constexpr cpp20_input_iterator& operator++() { ++it_; return *this; }
655 constexpr void operator++(int) { ++it_; }
656
657 friend constexpr It base(const cpp20_input_iterator& i) { return i.it_; }
658
659 template <class T>
660 void operator,(T const &) = delete;
661};
662template <class It>
663cpp20_input_iterator(It) -> cpp20_input_iterator<It>;
664
665static_assert(std::input_iterator<cpp20_input_iterator<int*>>);
666
667template<std::input_or_output_iterator>
668struct iter_value_or_void { using type = void; };
669
670template<std::input_iterator I>
671struct iter_value_or_void<I> {
672 using type = std::iter_value_t<I>;
673};
674
675template <class It>
676class cpp20_output_iterator {
677 It it_;
678
679public:
680 using difference_type = std::iter_difference_t<It>;
681
682 constexpr explicit cpp20_output_iterator(It it) : it_(it) {}
683 cpp20_output_iterator(cpp20_output_iterator&&) = default;
684 cpp20_output_iterator& operator=(cpp20_output_iterator&&) = default;
685
686 constexpr decltype(auto) operator*() const { return *it_; }
687 constexpr cpp20_output_iterator& operator++() {
688 ++it_;
689 return *this;
690 }
691 constexpr cpp20_output_iterator operator++(int) { return cpp20_output_iterator(it_++); }
692
693 friend constexpr It base(const cpp20_output_iterator& i) { return i.it_; }
694
695 template <class T>
696 void operator,(T const&) = delete;
697};
698template <class It>
699cpp20_output_iterator(It) -> cpp20_output_iterator<It>;
700
701static_assert(std::output_iterator<cpp20_output_iterator<int*>, int>);
702
703# if TEST_STD_VER >= 20
704
705// An `input_iterator` that can be used in a `std::ranges::common_range`
706template <class Base>
707struct common_input_iterator {
708 Base it_;
709
710 using value_type = std::iter_value_t<Base>;
711 using difference_type = std::intptr_t;
712 using iterator_concept = std::input_iterator_tag;
713
714 constexpr common_input_iterator() = default;
715 constexpr explicit common_input_iterator(Base it) : it_(it) {}
716
717 constexpr common_input_iterator& operator++() {
718 ++it_;
719 return *this;
720 }
721 constexpr void operator++(int) { ++it_; }
722
723 constexpr decltype(auto) operator*() const { return *it_; }
724
725 friend constexpr bool operator==(common_input_iterator const&, common_input_iterator const&) = default;
726};
727
728# endif // TEST_STD_VER >= 20
729
730struct IteratorOpCounts {
731 std::size_t increments = 0; ///< Number of times the iterator moved forward (++it, it++, it+=positive, it-=negative).
732 std::size_t decrements = 0; ///< Number of times the iterator moved backward (--it, it--, it-=positive, it+=negative).
733 std::size_t zero_moves = 0; ///< Number of times a call was made to move the iterator by 0 positions (it+=0, it-=0).
734 std::size_t equal_cmps = 0; ///< Total number of calls to op== or op!=. If compared against a sentinel object, that
735 /// sentinel object must call the `record_equality_comparison` function so that the
736 /// comparison is counted correctly.
737};
738
739// Iterator adaptor that records its operation counts in a IteratorOpCounts
740template <class It>
741class operation_counting_iterator {
742public:
743 using value_type = typename iter_value_or_void<It>::type;
744 using difference_type = std::iter_difference_t<It>;
745 using iterator_concept =
746 std::conditional_t<std::contiguous_iterator<It>, std::contiguous_iterator_tag,
747 std::conditional_t<std::random_access_iterator<It>, std::random_access_iterator_tag,
748 std::conditional_t<std::bidirectional_iterator<It>, std::bidirectional_iterator_tag,
749 std::conditional_t<std::forward_iterator<It>, std::forward_iterator_tag,
750 std::conditional_t<std::input_iterator<It>, std::input_iterator_tag,
751 /* else */ std::output_iterator_tag
752 >>>>>;
753 using iterator_category = iterator_concept;
754
755 operation_counting_iterator()
756 requires std::default_initializable<It>
757 = default;
758
759 constexpr explicit operation_counting_iterator(It const& it, IteratorOpCounts* counts = nullptr)
760 : base_(base(it)), counts_(counts) {}
761
762 constexpr operation_counting_iterator(const operation_counting_iterator& o) { *this = o; }
763 constexpr operation_counting_iterator(operation_counting_iterator&& o) { *this = o; }
764
765 constexpr operation_counting_iterator& operator=(const operation_counting_iterator& o) = default;
766 constexpr operation_counting_iterator& operator=(operation_counting_iterator&& o) { return *this = o; }
767
768 friend constexpr It base(operation_counting_iterator const& it) { return It(it.base_); }
769
770 constexpr decltype(auto) operator*() const { return *It(base_); }
771
772 constexpr decltype(auto) operator[](difference_type n) const { return It(base_)[n]; }
773
774 constexpr operation_counting_iterator& operator++() {
775 It tmp(base_);
776 base_ = base(++tmp);
777 moved_by(1);
778 return *this;
779 }
780
781 constexpr void operator++(int) { ++*this; }
782
783 constexpr operation_counting_iterator operator++(int)
784 requires std::forward_iterator<It>
785 {
786 auto temp = *this;
787 ++*this;
788 return temp;
789 }
790
791 constexpr operation_counting_iterator& operator--()
792 requires std::bidirectional_iterator<It>
793 {
794 It tmp(base_);
795 base_ = base(--tmp);
796 moved_by(-1);
797 return *this;
798 }
799
800 constexpr operation_counting_iterator operator--(int)
801 requires std::bidirectional_iterator<It>
802 {
803 auto temp = *this;
804 --*this;
805 return temp;
806 }
807
808 constexpr operation_counting_iterator& operator+=(difference_type const n)
809 requires std::random_access_iterator<It>
810 {
811 It tmp(base_);
812 base_ = base(tmp += n);
813 moved_by(n);
814 return *this;
815 }
816
817 constexpr operation_counting_iterator& operator-=(difference_type const n)
818 requires std::random_access_iterator<It>
819 {
820 It tmp(base_);
821 base_ = base(tmp -= n);
822 moved_by(-n);
823 return *this;
824 }
825
826 friend constexpr operation_counting_iterator operator+(operation_counting_iterator it, difference_type n)
827 requires std::random_access_iterator<It>
828 {
829 return it += n;
830 }
831
832 friend constexpr operation_counting_iterator operator+(difference_type n, operation_counting_iterator it)
833 requires std::random_access_iterator<It>
834 {
835 return it += n;
836 }
837
838 friend constexpr operation_counting_iterator operator-(operation_counting_iterator it, difference_type n)
839 requires std::random_access_iterator<It>
840 {
841 return it -= n;
842 }
843
844 friend constexpr difference_type
845 operator-(operation_counting_iterator const& x, operation_counting_iterator const& y)
846 requires std::sized_sentinel_for<It, It>
847 {
848 return base(x) - base(y);
849 }
850
851 constexpr void record_equality_comparison() const {
852 if (counts_ != nullptr)
853 ++counts_->equal_cmps;
854 }
855
856 constexpr bool operator==(operation_counting_iterator const& other) const
857 requires std::sentinel_for<It, It>
858 {
859 record_equality_comparison();
860 return It(base_) == It(other.base_);
861 }
862
863 friend constexpr bool operator<(operation_counting_iterator const& x, operation_counting_iterator const& y)
864 requires std::random_access_iterator<It>
865 {
866 return It(x.base_) < It(y.base_);
867 }
868
869 friend constexpr bool operator>(operation_counting_iterator const& x, operation_counting_iterator const& y)
870 requires std::random_access_iterator<It>
871 {
872 return It(x.base_) > It(y.base_);
873 }
874
875 friend constexpr bool operator<=(operation_counting_iterator const& x, operation_counting_iterator const& y)
876 requires std::random_access_iterator<It>
877 {
878 return It(x.base_) <= It(y.base_);
879 }
880
881 friend constexpr bool operator>=(operation_counting_iterator const& x, operation_counting_iterator const& y)
882 requires std::random_access_iterator<It>
883 {
884 return It(x.base_) >= It(y.base_);
885 }
886
887 template <class T>
888 void operator,(T const &) = delete;
889
890private:
891 constexpr void moved_by(difference_type n) {
892 if (counts_ == nullptr)
893 return;
894 if (n > 0)
895 ++counts_->increments;
896 else if (n < 0)
897 ++counts_->decrements;
898 else
899 ++counts_->zero_moves;
900 }
901
902 decltype(base(std::declval<It>())) base_;
903 IteratorOpCounts* counts_ = nullptr;
904};
905template <class It>
906operation_counting_iterator(It) -> operation_counting_iterator<It>;
907
908#endif // TEST_STD_VER > 17
909
910#if TEST_STD_VER > 17
911template <class It>
912class sentinel_wrapper {
913public:
914 explicit sentinel_wrapper() = default;
915 constexpr explicit sentinel_wrapper(const It& it) : base_(base(it)) {}
916 constexpr bool operator==(const It& other) const {
917 // If supported, record statistics about the equality operator call
918 // inside `other`.
919 if constexpr (requires { other.record_equality_comparison(); }) {
920 other.record_equality_comparison();
921 }
922 return base_ == base(other);
923 }
924 friend constexpr It base(const sentinel_wrapper& s) { return It(s.base_); }
925private:
926 decltype(base(std::declval<It>())) base_;
927};
928template <class It>
929sentinel_wrapper(It) -> sentinel_wrapper<It>;
930
931template <class It>
932class sized_sentinel {
933public:
934 explicit sized_sentinel() = default;
935 constexpr explicit sized_sentinel(const It& it) : base_(base(it)) {}
936 constexpr bool operator==(const It& other) const { return base_ == base(other); }
937 friend constexpr auto operator-(const sized_sentinel& s, const It& i) { return s.base_ - base(i); }
938 friend constexpr auto operator-(const It& i, const sized_sentinel& s) { return base(i) - s.base_; }
939 friend constexpr It base(const sized_sentinel& s) { return It(s.base_); }
940private:
941 decltype(base(std::declval<It>())) base_;
942};
943template <class It>
944sized_sentinel(It) -> sized_sentinel<It>;
945
946namespace adl {
947
948class Iterator {
949 public:
950 using value_type = int;
951 using reference = int&;
952 using difference_type = std::ptrdiff_t;
953
954 private:
955 value_type* ptr_ = nullptr;
956 int* iter_moves_ = nullptr;
957 int* iter_swaps_ = nullptr;
958
959 constexpr Iterator(int* p, int* iter_moves, int* iter_swaps)
960 : ptr_(p)
961 , iter_moves_(iter_moves)
962 , iter_swaps_(iter_swaps) {}
963
964 public:
965 constexpr Iterator() = default;
966 static constexpr Iterator TrackMoves(int* p, int& iter_moves) {
967 return Iterator(p, &iter_moves, /*iter_swaps=*/nullptr);
968 }
969 static constexpr Iterator TrackSwaps(int& iter_swaps) {
970 return Iterator(/*p=*/nullptr, /*iter_moves=*/nullptr, &iter_swaps);
971 }
972 static constexpr Iterator TrackSwaps(int* p, int& iter_swaps) {
973 return Iterator(p, /*iter_moves=*/nullptr, &iter_swaps);
974 }
975
976 constexpr int iter_moves() const { assert(iter_moves_); return *iter_moves_; }
977 constexpr int iter_swaps() const { assert(iter_swaps_); return *iter_swaps_; }
978
979 constexpr value_type& operator*() const { return *ptr_; }
980 constexpr reference operator[](difference_type n) const { return ptr_[n]; }
981
982 friend constexpr Iterator operator+(Iterator i, difference_type n) {
983 return Iterator(i.ptr_ + n, i.iter_moves_, i.iter_swaps_);
984 }
985 friend constexpr Iterator operator+(difference_type n, Iterator i) {
986 return i + n;
987 }
988 constexpr Iterator operator-(difference_type n) const {
989 return Iterator(ptr_ - n, iter_moves_, iter_swaps_);
990 }
991 constexpr difference_type operator-(Iterator rhs) const {
992 return ptr_ - rhs.ptr_;
993 }
994 constexpr Iterator& operator+=(difference_type n) {
995 ptr_ += n;
996 return *this;
997 }
998 constexpr Iterator& operator-=(difference_type n) {
999 ptr_ -= n;
1000 return *this;
1001 }
1002
1003 constexpr Iterator& operator++() { ++ptr_; return *this; }
1004 constexpr Iterator operator++(int) {
1005 Iterator prev = *this;
1006 ++ptr_;
1007 return prev;
1008 }
1009
1010 constexpr Iterator& operator--() { --ptr_; return *this; }
1011 constexpr Iterator operator--(int) {
1012 Iterator prev = *this;
1013 --ptr_;
1014 return prev;
1015 }
1016
1017 constexpr friend void iter_swap(Iterator a, Iterator b) {
1018 std::swap(a.ptr_, b.ptr_);
1019 if (a.iter_swaps_) {
1020 ++(*a.iter_swaps_);
1021 }
1022 }
1023
1024 constexpr friend value_type&& iter_move(Iterator iter) {
1025 if (iter.iter_moves_) {
1026 ++(*iter.iter_moves_);
1027 }
1028 return std::move(*iter);
1029 }
1030
1031 constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
1032 return lhs.ptr_ == rhs.ptr_;
1033 }
1034 constexpr friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {
1035 return lhs.ptr_ <=> rhs.ptr_;
1036 }
1037};
1038
1039} // namespace adl
1040
1041template <class T>
1042class rvalue_iterator {
1043public:
1044 using iterator_category = std::input_iterator_tag;
1045 using iterator_concept = std::random_access_iterator_tag;
1046 using difference_type = std::ptrdiff_t;
1047 using reference = T&&;
1048 using value_type = T;
1049
1050 rvalue_iterator() = default;
1051 constexpr rvalue_iterator(T* it) : it_(it) {}
1052
1053 constexpr reference operator*() const { return std::move(*it_); }
1054
1055 constexpr rvalue_iterator& operator++() {
1056 ++it_;
1057 return *this;
1058 }
1059
1060 constexpr rvalue_iterator operator++(int) {
1061 auto tmp = *this;
1062 ++it_;
1063 return tmp;
1064 }
1065
1066 constexpr rvalue_iterator& operator--() {
1067 --it_;
1068 return *this;
1069 }
1070
1071 constexpr rvalue_iterator operator--(int) {
1072 auto tmp = *this;
1073 --it_;
1074 return tmp;
1075 }
1076
1077 constexpr rvalue_iterator operator+(difference_type n) const {
1078 auto tmp = *this;
1079 tmp.it += n;
1080 return tmp;
1081 }
1082
1083 constexpr friend rvalue_iterator operator+(difference_type n, rvalue_iterator iter) {
1084 iter += n;
1085 return iter;
1086 }
1087
1088 constexpr rvalue_iterator operator-(difference_type n) const {
1089 auto tmp = *this;
1090 tmp.it -= n;
1091 return tmp;
1092 }
1093
1094 constexpr difference_type operator-(const rvalue_iterator& other) const { return it_ - other.it_; }
1095
1096 constexpr rvalue_iterator& operator+=(difference_type n) {
1097 it_ += n;
1098 return *this;
1099 }
1100
1101 constexpr rvalue_iterator& operator-=(difference_type n) {
1102 it_ -= n;
1103 return *this;
1104 }
1105
1106 constexpr reference operator[](difference_type n) const { return std::move(it_[n]); }
1107
1108 auto operator<=>(const rvalue_iterator&) const noexcept = default;
1109
1110private:
1111 T* it_;
1112};
1113
1114template <class T>
1115rvalue_iterator(T*) -> rvalue_iterator<T>;
1116
1117static_assert(std::random_access_iterator<rvalue_iterator<int*>>);
1118
1119// Proxy
1120// ======================================================================
1121// Proxy that can wrap a value or a reference. It simulates C++23's tuple
1122// but simplified to just hold one argument.
1123// Note that unlike tuple, this class deliberately doesn't have special handling
1124// of swap to cause a compilation error if it's used in an algorithm that relies
1125// on plain swap instead of ranges::iter_swap.
1126// This class is useful for testing that if algorithms support proxy iterator
1127// properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of
1128// plain swap and std::move.
1129template <class T>
1130struct Proxy;
1131
1132template <class T>
1133inline constexpr bool IsProxy = false;
1134
1135template <class T>
1136inline constexpr bool IsProxy<Proxy<T>> = true;
1137
1138template <class T>
1139struct Proxy {
1140 T data;
1141
1142 constexpr T& getData() & { return data; }
1143
1144 constexpr const T& getData() const& { return data; }
1145
1146 constexpr T&& getData() && { return static_cast<T&&>(data); }
1147
1148 constexpr const T&& getData() const&& { return static_cast<const T&&>(data); }
1149
1150 template <class U>
1151 requires std::constructible_from<T, U&&>
1152 constexpr Proxy(U&& u) : data{std::forward<U>(u)} {}
1153
1154 // This constructor covers conversion from cvref of Proxy<U>, including non-const/const versions of copy/move constructor
1155 template <class Other>
1156 requires(IsProxy<std::decay_t<Other>> && std::constructible_from<T, decltype(std::declval<Other>().getData())>)
1157 constexpr Proxy(Other&& other) : data{std::forward<Other>(other).getData()} {}
1158
1159 template <class Other>
1160 requires(IsProxy<std::decay_t<Other>> && std::assignable_from<T&, decltype(std::declval<Other>().getData())>)
1161 constexpr Proxy& operator=(Other&& other) {
1162 data = std::forward<Other>(other).getData();
1163 return *this;
1164 }
1165
1166 // const assignment required to make ProxyIterator model std::indirectly_writable
1167 template <class Other>
1168 requires(IsProxy<std::decay_t<Other>> && std::assignable_from<const T&, decltype(std::declval<Other>().getData())>)
1169 constexpr const Proxy& operator=(Other&& other) const {
1170 data = std::forward<Other>(other).getData();
1171 return *this;
1172 }
1173
1174 // If `T` is a reference type, the implicitly-generated assignment operator will be deleted (and would take precedence
1175 // over the templated `operator=` above because it's a better match).
1176 constexpr Proxy& operator=(const Proxy& rhs) {
1177 data = rhs.data;
1178 return *this;
1179 }
1180
1181 // no specialised swap function that takes const Proxy& and no specialised const member swap
1182 // Calling swap(Proxy<T>{}, Proxy<T>{}) would fail (pass prvalues)
1183
1184 // Compare operators are defined for the convenience of the tests
1185 friend constexpr bool operator==(const Proxy&, const Proxy&)
1186 requires (std::equality_comparable<T> && !std::is_reference_v<T>)
1187 = default;
1188
1189 // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default equality comparison operator is deleted
1190 // when `T` is a reference type.
1191 template <class U>
1192 friend constexpr bool operator==(const Proxy& lhs, const Proxy<U>& rhs)
1193 requires std::equality_comparable_with<std::decay_t<T>, std::decay_t<U>> {
1194 return lhs.data == rhs.data;
1195 }
1196
1197 friend constexpr auto operator<=>(const Proxy&, const Proxy&)
1198 requires (std::three_way_comparable<T> && !std::is_reference_v<T>)
1199 = default;
1200
1201 // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default 3-way comparison operator is deleted when
1202 // `T` is a reference type.
1203 template <class U>
1204 friend constexpr auto operator<=>(const Proxy& lhs, const Proxy<U>& rhs)
1205 requires std::three_way_comparable_with<std::decay_t<T>, std::decay_t<U>> {
1206 return lhs.data <=> rhs.data;
1207 }
1208};
1209
1210// This is to make ProxyIterator model `std::indirectly_readable`
1211template <class T, class U, template <class> class TQual, template <class> class UQual>
1212 requires requires { typename std::common_reference_t<TQual<T>, UQual<U>>; }
1213struct std::basic_common_reference<Proxy<T>, Proxy<U>, TQual, UQual> {
1214 using type = Proxy<std::common_reference_t<TQual<T>, UQual<U>>>;
1215};
1216
1217template <class T, class U>
1218 requires requires { typename std::common_type_t<T, U>; }
1219struct std::common_type<Proxy<T>, Proxy<U>> {
1220 using type = Proxy<std::common_type_t<T, U>>;
1221};
1222
1223// ProxyIterator
1224// ======================================================================
1225// It wraps `Base` iterator and when dereferenced it returns a Proxy<ref>
1226// It simulates C++23's zip_view::iterator but simplified to just wrap
1227// one base iterator.
1228// Note it forwards value_type, iter_move, iter_swap. e.g if the base
1229// iterator is int*,
1230// operator* -> Proxy<int&>
1231// iter_value_t -> Proxy<int>
1232// iter_move -> Proxy<int&&>
1233template <class Base>
1234struct ProxyIteratorBase {};
1235
1236template <class Base>
1237 requires std::derived_from<
1238 typename std::iterator_traits<Base>::iterator_category,
1239 std::input_iterator_tag>
1240struct ProxyIteratorBase<Base> {
1241 using iterator_category = std::input_iterator_tag;
1242};
1243
1244template <std::input_iterator Base>
1245consteval auto get_iterator_concept() {
1246 if constexpr (std::random_access_iterator<Base>) {
1247 return std::random_access_iterator_tag{};
1248 } else if constexpr (std::bidirectional_iterator<Base>) {
1249 return std::bidirectional_iterator_tag{};
1250 } else if constexpr (std::forward_iterator<Base>) {
1251 return std::forward_iterator_tag{};
1252 } else {
1253 return std::input_iterator_tag{};
1254 }
1255}
1256
1257template <std::input_iterator Base>
1258struct ProxyIterator : ProxyIteratorBase<Base> {
1259 Base base_;
1260
1261 using iterator_concept = decltype(get_iterator_concept<Base>());
1262 using value_type = Proxy<std::iter_value_t<Base>>;
1263 using difference_type = std::iter_difference_t<Base>;
1264
1265 ProxyIterator()
1266 requires std::default_initializable<Base>
1267 = default;
1268
1269 constexpr ProxyIterator(Base base) : base_{std::move(base)} {}
1270
1271 template <class T>
1272 requires std::constructible_from<Base, T&&>
1273 constexpr ProxyIterator(T&& t) : base_{std::forward<T>(t)} {}
1274
1275 friend constexpr decltype(auto) base(const ProxyIterator& p) { return base(p.base_); }
1276
1277 // Specialization of iter_move
1278 // If operator* returns Proxy<Foo&>, iter_move will return Proxy<Foo&&>
1279 // Note std::move(*it) returns Proxy<Foo&>&&, which is not what we want as
1280 // it will likely result in a copy rather than a move
1281 friend constexpr Proxy<std::iter_rvalue_reference_t<Base>> iter_move(const ProxyIterator& p) noexcept {
1282 return {std::ranges::iter_move(p.base_)};
1283 }
1284
1285 // Specialization of iter_swap
1286 // Note std::swap(*x, *y) would fail to compile as operator* returns prvalues
1287 // and std::swap takes non-const lvalue references
1288 friend constexpr void iter_swap(const ProxyIterator& x, const ProxyIterator& y) noexcept {
1289 std::ranges::iter_swap(x.base_, y.base_);
1290 }
1291
1292 // to satisfy input_iterator
1293 constexpr Proxy<std::iter_reference_t<Base>> operator*() const { return {*base_}; }
1294
1295 constexpr ProxyIterator& operator++() {
1296 ++base_;
1297 return *this;
1298 }
1299
1300 constexpr void operator++(int) { ++*this; }
1301
1302 friend constexpr bool operator==(const ProxyIterator& x, const ProxyIterator& y)
1303 requires std::equality_comparable<Base> {
1304 return x.base_ == y.base_;
1305 }
1306
1307 // to satisfy forward_iterator
1308 constexpr ProxyIterator operator++(int)
1309 requires std::forward_iterator<Base> {
1310 auto tmp = *this;
1311 ++*this;
1312 return tmp;
1313 }
1314
1315 // to satisfy bidirectional_iterator
1316 constexpr ProxyIterator& operator--()
1317 requires std::bidirectional_iterator<Base> {
1318 --base_;
1319 return *this;
1320 }
1321
1322 constexpr ProxyIterator operator--(int)
1323 requires std::bidirectional_iterator<Base> {
1324 auto tmp = *this;
1325 --*this;
1326 return tmp;
1327 }
1328
1329 // to satisfy random_access_iterator
1330 constexpr ProxyIterator& operator+=(difference_type n)
1331 requires std::random_access_iterator<Base> {
1332 base_ += n;
1333 return *this;
1334 }
1335
1336 constexpr ProxyIterator& operator-=(difference_type n)
1337 requires std::random_access_iterator<Base> {
1338 base_ -= n;
1339 return *this;
1340 }
1341
1342 constexpr Proxy<std::iter_reference_t<Base>> operator[](difference_type n) const
1343 requires std::random_access_iterator<Base> {
1344 return {base_[n]};
1345 }
1346
1347 friend constexpr bool operator<(const ProxyIterator& x, const ProxyIterator& y)
1348 requires std::random_access_iterator<Base> {
1349 return x.base_ < y.base_;
1350 }
1351
1352 friend constexpr bool operator>(const ProxyIterator& x, const ProxyIterator& y)
1353 requires std::random_access_iterator<Base> {
1354 return x.base_ > y.base_;
1355 }
1356
1357 friend constexpr bool operator<=(const ProxyIterator& x, const ProxyIterator& y)
1358 requires std::random_access_iterator<Base> {
1359 return x.base_ <= y.base_;
1360 }
1361
1362 friend constexpr bool operator>=(const ProxyIterator& x, const ProxyIterator& y)
1363 requires std::random_access_iterator<Base> {
1364 return x.base_ >= y.base_;
1365 }
1366
1367 friend constexpr auto operator<=>(const ProxyIterator& x, const ProxyIterator& y)
1368 requires(std::random_access_iterator<Base> && std::three_way_comparable<Base>) {
1369 return x.base_ <=> y.base_;
1370 }
1371
1372 friend constexpr ProxyIterator operator+(const ProxyIterator& x, difference_type n)
1373 requires std::random_access_iterator<Base> {
1374 return ProxyIterator{x.base_ + n};
1375 }
1376
1377 friend constexpr ProxyIterator operator+(difference_type n, const ProxyIterator& x)
1378 requires std::random_access_iterator<Base> {
1379 return ProxyIterator{n + x.base_};
1380 }
1381
1382 friend constexpr ProxyIterator operator-(const ProxyIterator& x, difference_type n)
1383 requires std::random_access_iterator<Base> {
1384 return ProxyIterator{x.base_ - n};
1385 }
1386
1387 friend constexpr difference_type operator-(const ProxyIterator& x, const ProxyIterator& y)
1388 requires std::random_access_iterator<Base> {
1389 return x.base_ - y.base_;
1390 }
1391};
1392template <class Base>
1393ProxyIterator(Base) -> ProxyIterator<Base>;
1394
1395static_assert(std::indirectly_readable<ProxyIterator<int*>>);
1396static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int>>);
1397static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int&>>);
1398
1399template <class Iter>
1400using Cpp20InputProxyIterator = ProxyIterator<cpp20_input_iterator<Iter>>;
1401
1402template <class Iter>
1403using ForwardProxyIterator = ProxyIterator<forward_iterator<Iter>>;
1404
1405template <class Iter>
1406using BidirectionalProxyIterator = ProxyIterator<bidirectional_iterator<Iter>>;
1407
1408template <class Iter>
1409using RandomAccessProxyIterator = ProxyIterator<random_access_iterator<Iter>>;
1410
1411template <class Iter>
1412using ContiguousProxyIterator = ProxyIterator<contiguous_iterator<Iter>>;
1413
1414template <class BaseSent>
1415struct ProxySentinel {
1416 BaseSent base_;
1417
1418 ProxySentinel() = default;
1419 constexpr ProxySentinel(BaseSent base) : base_{std::move(base)} {}
1420
1421 template <class Base>
1422 requires std::equality_comparable_with<Base, BaseSent>
1423 friend constexpr bool operator==(const ProxyIterator<Base>& p, const ProxySentinel& sent) {
1424 return p.base_ == sent.base_;
1425 }
1426};
1427template <class BaseSent>
1428ProxySentinel(BaseSent) -> ProxySentinel<BaseSent>;
1429
1430template <std::ranges::input_range Base>
1431 requires std::ranges::view<Base>
1432struct ProxyRange {
1433 Base base_;
1434
1435 constexpr auto begin() { return ProxyIterator{std::ranges::begin(base_)}; }
1436
1437 constexpr auto end() { return ProxySentinel{std::ranges::end(base_)}; }
1438
1439 constexpr auto begin() const
1440 requires std::ranges::input_range<const Base> {
1441 return ProxyIterator{std::ranges::begin(base_)};
1442 }
1443
1444 constexpr auto end() const
1445 requires std::ranges::input_range<const Base> {
1446 return ProxySentinel{std::ranges::end(base_)};
1447 }
1448};
1449
1450template <std::ranges::input_range R>
1451 requires std::ranges::viewable_range<R&&>
1452ProxyRange(R&&) -> ProxyRange<std::views::all_t<R&&>>;
1453
1454#endif // TEST_STD_VER > 17
1455
1456#if TEST_STD_VER >= 17
1457
1458namespace util {
1459template <class Derived, class Iter>
1460class iterator_wrapper {
1461 Iter iter_;
1462
1463 using iter_traits = std::iterator_traits<Iter>;
1464
1465public:
1466 using iterator_category = typename iter_traits::iterator_category;
1467 using value_type = typename iter_traits::value_type;
1468 using difference_type = typename iter_traits::difference_type;
1469 using pointer = typename iter_traits::pointer;
1470 using reference = typename iter_traits::reference;
1471
1472 constexpr iterator_wrapper() : iter_() {}
1473 constexpr explicit iterator_wrapper(Iter iter) : iter_(iter) {}
1474
1475 decltype(*iter_) operator*() { return *iter_; }
1476 decltype(*iter_) operator*() const { return *iter_; }
1477
1478 decltype(iter_[0]) operator[](difference_type v) const {
1479 return iter_[v];
1480 }
1481
1482 Derived& operator++() {
1483 ++iter_;
1484 return static_cast<Derived&>(*this);
1485 }
1486
1487 Derived operator++(int) {
1488 auto tmp = static_cast<Derived&>(*this);
1489 ++(*this);
1490 return tmp;
1491 }
1492
1493 Derived& operator--() {
1494 --iter_;
1495 return static_cast<Derived&>(*this);
1496 }
1497
1498 Derived operator--(int) {
1499 auto tmp = static_cast<Derived&>(*this);
1500 --(*this);
1501 return tmp;
1502 }
1503
1504 Derived& operator+=(difference_type i) {
1505 iter_ += i;
1506 return static_cast<Derived&>(*this);
1507 }
1508
1509 Derived& operator-=(difference_type i) {
1510 iter_ -= i;
1511 return static_cast<Derived&>(*this);
1512 }
1513
1514 friend decltype(iter_ - iter_) operator-(const iterator_wrapper& lhs, const iterator_wrapper& rhs) {
1515 return lhs.iter_ - rhs.iter_;
1516 }
1517
1518 friend Derived operator-(Derived iter, difference_type i) {
1519 iter.iter_ -= i;
1520 return iter;
1521 }
1522
1523 friend Derived operator+(Derived iter, difference_type i) {
1524 iter.iter_ += i;
1525 return iter;
1526 }
1527
1528 friend Derived operator+(difference_type i, Derived iter) { return iter + i; }
1529
1530 friend bool operator==(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ == rhs.iter_; }
1531 friend bool operator!=(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ != rhs.iter_; }
1532
1533 friend bool operator>(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ > rhs.iter_; }
1534 friend bool operator<(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ < rhs.iter_; }
1535 friend bool operator<=(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ <= rhs.iter_; }
1536 friend bool operator>=(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ >= rhs.iter_; }
1537};
1538
1539class iterator_error : std::runtime_error {
1540public:
1541 iterator_error(const char* what) : std::runtime_error(what) {}
1542};
1543
1544#ifndef TEST_HAS_NO_EXCEPTIONS
1545template <class Iter>
1546class throw_on_move_iterator : public iterator_wrapper<throw_on_move_iterator<Iter>, Iter> {
1547 using base = iterator_wrapper<throw_on_move_iterator<Iter>, Iter>;
1548
1549 int moves_until_throw_ = 0;
1550
1551public:
1552 using difference_type = typename base::difference_type;
1553 using value_type = typename base::value_type;
1554 using iterator_category = typename base::iterator_category;
1555
1556 throw_on_move_iterator() = default;
1557 throw_on_move_iterator(Iter iter, int moves_until_throw)
1558 : base(std::move(iter)), moves_until_throw_(moves_until_throw) {}
1559
1560 throw_on_move_iterator(const throw_on_move_iterator& other) : base(other) {}
1561 throw_on_move_iterator& operator=(const throw_on_move_iterator& other) {
1562 static_cast<base&>(*this) = other;
1563 return *this;
1564 }
1565
1566 throw_on_move_iterator(throw_on_move_iterator&& other)
1567 : base(std::move(other)), moves_until_throw_(other.moves_until_throw_ - 1) {
1568 if (moves_until_throw_ == -1)
1569 throw iterator_error("throw_on_move_iterator");
1570 }
1571
1572 throw_on_move_iterator& operator=(throw_on_move_iterator&& other) {
1573 moves_until_throw_ = other.moves_until_throw_ - 1;
1574 if (moves_until_throw_ == -1)
1575 throw iterator_error("throw_on_move_iterator");
1576 return *this;
1577 }
1578};
1579
1580template <class Iter>
1581throw_on_move_iterator(Iter) -> throw_on_move_iterator<Iter>;
1582#endif // TEST_HAS_NO_EXCEPTIONS
1583} // namespace util
1584
1585#endif // TEST_STD_VER >= 17
1586
1587namespace types {
1588template <class Ptr>
1589using random_access_iterator_list =
1590 type_list<Ptr,
1591#if TEST_STD_VER >= 20
1592 contiguous_iterator<Ptr>,
1593#endif
1594 random_access_iterator<Ptr> >;
1595
1596template <class Ptr>
1597using bidirectional_iterator_list =
1598 concatenate_t<random_access_iterator_list<Ptr>, type_list<bidirectional_iterator<Ptr> > >;
1599
1600template <class Ptr>
1601using forward_iterator_list = concatenate_t<bidirectional_iterator_list<Ptr>, type_list<forward_iterator<Ptr> > >;
1602
1603template <class Ptr>
1604using cpp17_input_iterator_list = concatenate_t<forward_iterator_list<Ptr>, type_list<cpp17_input_iterator<Ptr> > >;
1605
1606#if TEST_STD_VER >= 20
1607template <class Ptr>
1608using cpp20_input_iterator_list =
1609 concatenate_t<forward_iterator_list<Ptr>, type_list<cpp20_input_iterator<Ptr>, cpp17_input_iterator<Ptr>>>;
1610#endif
1611} // namespace types
1612
1613
1614#endif // SUPPORT_TEST_ITERATORS_H
1615