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