libcxx/test/support/test_iterators.h

   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
  39     TEST_CONSTEXPR explicit cpp17_output_iterator(It it) : it_(std::move(it)) {}
  40
  41     template <class 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>
  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
  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
  82     TEST_CONSTEXPR explicit cpp17_input_iterator(It it) : it_(it) {}
  83
  84     template <class U, class T>
  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>
  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
  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
 125     TEST_CONSTEXPR forward_iterator() : it_() {}
 126     TEST_CONSTEXPR explicit forward_iterator(It it) : it_(it) {}
 127
 128     template <class 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>
 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
 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
 165     TEST_CONSTEXPR bidirectional_iterator() : it_() {}
 166     TEST_CONSTEXPR explicit bidirectional_iterator(It it) : it_(it) {}
 167
 168     template <class 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>
 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
 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
 207     TEST_CONSTEXPR random_access_iterator() : it_() {}
 208     TEST_CONSTEXPR explicit random_access_iterator(It it) : it_(it) {}
 209
 210     template <class 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>
 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
 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
 263   constexpr cpp20_random_access_iterator() : it_() {}
 264   constexpr explicit cpp20_random_access_iterator(It it) : it_(it) {}
 265
 266   template <class U>
 267   constexpr cpp20_random_access_iterator(const cpp20_random_access_iterator<U>& u) : it_(u.it_) {}
 268
 269   template <class U>
 270   constexpr cpp20_random_access_iterator(cpp20_random_access_iterator<U>&& u) : it_(u.it_) {
 271     u.it_ = U();
 272   }
 273
 274   constexpr decltype(auto) operator*() const { return *it_; }
 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
 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
 357     TEST_CONSTEXPR_CXX14 It base() const {return it_;}
 358
 359     TEST_CONSTEXPR_CXX14 contiguous_iterator() : it_() {}
 360     TEST_CONSTEXPR_CXX14 explicit contiguous_iterator(It it) : it_(it) {}
 361
 362     template <class 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>
 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
 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
 415     constexpr It base() const {return it_;}
 416
 417     constexpr three_way_contiguous_iterator() : it_() {}
 418     constexpr explicit three_way_contiguous_iterator(It it) : it_(it) {}
 419
 420     template <class 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>
 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)
 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
 465     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)
 469         : begin_(first), end_(last), current_(first), action_(action), index_(index) {}
 470     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
 574     NonThrowingIterator()
 575         : begin_(nullptr), end_(nullptr), current_(nullptr) {}
 576     explicit NonThrowingIterator(const T *first, const T *last)
 577         : begin_(first), end_(last), current_(first) {}
 578     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
 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;
 650     constexpr decltype(auto) operator*() const { return *it_; }
 651     constexpr cpp20_input_iterator& operator++() { ++it_; return *this; }
 652     constexpr void operator++(int) { ++it_; }
 653
 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