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