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 <stdexcept>
  16 #include <utility>
  17
  18 #include "test_macros.h"
  19
  20 // This iterator meets C++20's Cpp17OutputIterator requirements, as described
  21 // in Table 90 ([output.iterators]).
  22 template <class It>
  23 class cpp17_output_iterator
  24 {
  25     It it_;
  26
  27     template <class U> friend class cpp17_output_iterator;
  28 public:
  29     typedef          std::output_iterator_tag                  iterator_category;
  30     typedef void                                               value_type;
  31     typedef typename std::iterator_traits<It>::difference_type difference_type;
  32     typedef It                                                 pointer;
  33     typedef typename std::iterator_traits<It>::reference       reference;
  34
  35     TEST_CONSTEXPR explicit cpp17_output_iterator(It it) : it_(std::move(it)) {}
  36     template <class U>
  37         TEST_CONSTEXPR cpp17_output_iterator(const cpp17_output_iterator<U>& u) :it_(u.it_) {}
  38
  39     TEST_CONSTEXPR reference operator*() const {return *it_;}
  40
  41     TEST_CONSTEXPR_CXX14 cpp17_output_iterator& operator++() {++it_; return *this;}
  42     TEST_CONSTEXPR_CXX14 cpp17_output_iterator operator++(int) {return cpp17_output_iterator(it_++);}
  43
  44     friend TEST_CONSTEXPR It base(const cpp17_output_iterator& i) { return i.it_; }
  45
  46     template <class T>
  47     void operator,(T const &) = delete;
  48 };
  49 #if _LIBCPP_STD_VER > 17
  50    static_assert(std::output_iterator<cpp17_output_iterator<int*>, int>);
  51 #endif
  52
  53 // This iterator meets C++20's Cpp17InputIterator requirements, as described
  54 // in Table 89 ([input.iterators]).
  55 template <class It, class ItTraits = It>
  56 class cpp17_input_iterator
  57 {
  58     typedef std::iterator_traits<ItTraits> Traits;
  59     It it_;
  60
  61     template <class U, class T> friend class cpp17_input_iterator;
  62 public:
  63     typedef          std::input_iterator_tag                   iterator_category;
  64     typedef typename Traits::value_type                        value_type;
  65     typedef typename Traits::difference_type                   difference_type;
  66     typedef It                                                 pointer;
  67     typedef typename Traits::reference                         reference;
  68
  69     TEST_CONSTEXPR explicit cpp17_input_iterator(It it) : it_(it) {}
  70     template <class U, class T>
  71         TEST_CONSTEXPR cpp17_input_iterator(const cpp17_input_iterator<U, T>& u) : it_(u.it_) {}
  72
  73     TEST_CONSTEXPR reference operator*() const {return *it_;}
  74
  75     TEST_CONSTEXPR_CXX14 cpp17_input_iterator& operator++() {++it_; return *this;}
  76     TEST_CONSTEXPR_CXX14 cpp17_input_iterator operator++(int) {return cpp17_input_iterator(it_++);}
  77
  78     friend TEST_CONSTEXPR bool operator==(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ == y.it_;}
  79     friend TEST_CONSTEXPR bool operator!=(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ != y.it_;}
  80
  81     friend TEST_CONSTEXPR It base(const cpp17_input_iterator& i) { return i.it_; }
  82
  83     template <class T>
  84     void operator,(T const &) = delete;
  85 };
  86 #if _LIBCPP_STD_VER > 17
  87    static_assert(std::input_iterator<cpp17_input_iterator<int*>>);
  88 #endif
  89
  90 template <class It>
  91 class forward_iterator
  92 {
  93     It it_;
  94
  95     template <class U> friend class forward_iterator;
  96 public:
  97     typedef          std::forward_iterator_tag                 iterator_category;
  98     typedef typename std::iterator_traits<It>::value_type      value_type;
  99     typedef typename std::iterator_traits<It>::difference_type difference_type;
 100     typedef It                                                 pointer;
 101     typedef typename std::iterator_traits<It>::reference       reference;
 102
 103     TEST_CONSTEXPR forward_iterator() : it_() {}
 104     TEST_CONSTEXPR explicit forward_iterator(It it) : it_(it) {}
 105     template <class U>
 106         TEST_CONSTEXPR forward_iterator(const forward_iterator<U>& u) : it_(u.it_) {}
 107
 108     TEST_CONSTEXPR reference operator*() const {return *it_;}
 109
 110     TEST_CONSTEXPR_CXX14 forward_iterator& operator++() {++it_; return *this;}
 111     TEST_CONSTEXPR_CXX14 forward_iterator operator++(int) {return forward_iterator(it_++);}
 112
 113     friend TEST_CONSTEXPR bool operator==(const forward_iterator& x, const forward_iterator& y) {return x.it_ == y.it_;}
 114     friend TEST_CONSTEXPR bool operator!=(const forward_iterator& x, const forward_iterator& y) {return x.it_ != y.it_;}
 115
 116     friend TEST_CONSTEXPR It base(const forward_iterator& i) { return i.it_; }
 117
 118     template <class T>
 119     void operator,(T const &) = delete;
 120 };
 121
 122 template <class It>
 123 class bidirectional_iterator
 124 {
 125     It it_;
 126
 127     template <class U> friend class bidirectional_iterator;
 128 public:
 129     typedef          std::bidirectional_iterator_tag           iterator_category;
 130     typedef typename std::iterator_traits<It>::value_type      value_type;
 131     typedef typename std::iterator_traits<It>::difference_type difference_type;
 132     typedef It                                                 pointer;
 133     typedef typename std::iterator_traits<It>::reference       reference;
 134
 135     TEST_CONSTEXPR bidirectional_iterator() : it_() {}
 136     TEST_CONSTEXPR explicit bidirectional_iterator(It it) : it_(it) {}
 137     template <class U>
 138         TEST_CONSTEXPR bidirectional_iterator(const bidirectional_iterator<U>& u) : it_(u.it_) {}
 139
 140     TEST_CONSTEXPR reference operator*() const {return *it_;}
 141
 142     TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator++() {++it_; return *this;}
 143     TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator--() {--it_; return *this;}
 144     TEST_CONSTEXPR_CXX14 bidirectional_iterator operator++(int) {return bidirectional_iterator(it_++);}
 145     TEST_CONSTEXPR_CXX14 bidirectional_iterator operator--(int) {return bidirectional_iterator(it_--);}
 146
 147     friend TEST_CONSTEXPR bool operator==(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ == y.it_;}
 148     friend TEST_CONSTEXPR bool operator!=(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ != y.it_;}
 149
 150     friend TEST_CONSTEXPR It base(const bidirectional_iterator& i) { return i.it_; }
 151
 152     template <class T>
 153     void operator,(T const &) = delete;
 154 };
 155
 156 template <class It>
 157 class random_access_iterator
 158 {
 159     It it_;
 160
 161     template <class U> friend class random_access_iterator;
 162 public:
 163     typedef          std::random_access_iterator_tag           iterator_category;
 164     typedef typename std::iterator_traits<It>::value_type      value_type;
 165     typedef typename std::iterator_traits<It>::difference_type difference_type;
 166     typedef It                                                 pointer;
 167     typedef typename std::iterator_traits<It>::reference       reference;
 168
 169     TEST_CONSTEXPR random_access_iterator() : it_() {}
 170     TEST_CONSTEXPR explicit random_access_iterator(It it) : it_(it) {}
 171     template <class U>
 172         TEST_CONSTEXPR random_access_iterator(const random_access_iterator<U>& u) : it_(u.it_) {}
 173
 174     TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}
 175     TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];}
 176
 177     TEST_CONSTEXPR_CXX14 random_access_iterator& operator++() {++it_; return *this;}
 178     TEST_CONSTEXPR_CXX14 random_access_iterator& operator--() {--it_; return *this;}
 179     TEST_CONSTEXPR_CXX14 random_access_iterator operator++(int) {return random_access_iterator(it_++);}
 180     TEST_CONSTEXPR_CXX14 random_access_iterator operator--(int) {return random_access_iterator(it_--);}
 181
 182     TEST_CONSTEXPR_CXX14 random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;}
 183     TEST_CONSTEXPR_CXX14 random_access_iterator& operator-=(difference_type n) {it_ -= n; return *this;}
 184     friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(random_access_iterator x, difference_type n) {x += n; return x;}
 185     friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(difference_type n, random_access_iterator x) {x += n; return x;}
 186     friend TEST_CONSTEXPR_CXX14 random_access_iterator operator-(random_access_iterator x, difference_type n) {x -= n; return x;}
 187     friend TEST_CONSTEXPR difference_type operator-(random_access_iterator x, random_access_iterator y) {return x.it_ - y.it_;}
 188
 189     friend TEST_CONSTEXPR bool operator==(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ == y.it_;}
 190     friend TEST_CONSTEXPR bool operator!=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ != y.it_;}
 191     friend TEST_CONSTEXPR bool operator< (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ <  y.it_;}
 192     friend TEST_CONSTEXPR bool operator<=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ <= y.it_;}
 193     friend TEST_CONSTEXPR bool operator> (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ >  y.it_;}
 194     friend TEST_CONSTEXPR bool operator>=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ >= y.it_;}
 195
 196     friend TEST_CONSTEXPR It base(const random_access_iterator& i) { return i.it_; }
 197
 198     template <class T>
 199     void operator,(T const &) = delete;
 200 };
 201
 202 #if TEST_STD_VER > 17
 203 template <class It>
 204 class contiguous_iterator
 205 {
 206     static_assert(std::is_pointer_v<It>, "Things probably break in this case");
 207
 208     It it_;
 209
 210     template <class U> friend class contiguous_iterator;
 211 public:
 212     typedef          std::contiguous_iterator_tag              iterator_category;
 213     typedef typename std::iterator_traits<It>::value_type      value_type;
 214     typedef typename std::iterator_traits<It>::difference_type difference_type;
 215     typedef It                                                 pointer;
 216     typedef typename std::iterator_traits<It>::reference       reference;
 217     typedef typename std::remove_pointer<It>::type             element_type;
 218
 219     TEST_CONSTEXPR_CXX14 It base() const {return it_;}
 220
 221     TEST_CONSTEXPR_CXX14 contiguous_iterator() : it_() {}
 222     TEST_CONSTEXPR_CXX14 explicit contiguous_iterator(It it) : it_(it) {}
 223     template <class U>
 224         TEST_CONSTEXPR_CXX14 contiguous_iterator(const contiguous_iterator<U>& u) : it_(u.it_) {}
 225
 226     TEST_CONSTEXPR reference operator*() const {return *it_;}
 227     TEST_CONSTEXPR pointer operator->() const {return it_;}
 228     TEST_CONSTEXPR reference operator[](difference_type n) const {return it_[n];}
 229
 230     TEST_CONSTEXPR_CXX14 contiguous_iterator& operator++() {++it_; return *this;}
 231     TEST_CONSTEXPR_CXX14 contiguous_iterator& operator--() {--it_; return *this;}
 232     TEST_CONSTEXPR_CXX14 contiguous_iterator operator++(int) {return contiguous_iterator(it_++);}
 233     TEST_CONSTEXPR_CXX14 contiguous_iterator operator--(int) {return contiguous_iterator(it_--);}
 234
 235     TEST_CONSTEXPR_CXX14 contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;}
 236     TEST_CONSTEXPR_CXX14 contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;}
 237     friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(contiguous_iterator x, difference_type n) {x += n; return x;}
 238     friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(difference_type n, contiguous_iterator x) {x += n; return x;}
 239     friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator-(contiguous_iterator x, difference_type n) {x -= n; return x;}
 240     friend TEST_CONSTEXPR difference_type operator-(contiguous_iterator x, contiguous_iterator y) {return x.it_ - y.it_;}
 241
 242     friend TEST_CONSTEXPR bool operator==(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ == y.it_;}
 243     friend TEST_CONSTEXPR bool operator!=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ != y.it_;}
 244     friend TEST_CONSTEXPR bool operator< (const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ <  y.it_;}
 245     friend TEST_CONSTEXPR bool operator<=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ <= y.it_;}
 246     friend TEST_CONSTEXPR bool operator> (const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ >  y.it_;}
 247     friend TEST_CONSTEXPR bool operator>=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ >= y.it_;}
 248
 249     friend TEST_CONSTEXPR It base(const contiguous_iterator& i) { return i.it_; }
 250
 251     template <class T>
 252     void operator,(T const &) = delete;
 253 };
 254
 255 template <class It>
 256 class three_way_contiguous_iterator
 257 {
 258     static_assert(std::is_pointer_v<It>, "Things probably break in this case");
 259
 260     It it_;
 261
 262     template <class U> friend class three_way_contiguous_iterator;
 263 public:
 264     typedef          std::contiguous_iterator_tag              iterator_category;
 265     typedef typename std::iterator_traits<It>::value_type      value_type;
 266     typedef typename std::iterator_traits<It>::difference_type difference_type;
 267     typedef It                                                 pointer;
 268     typedef typename std::iterator_traits<It>::reference       reference;
 269     typedef typename std::remove_pointer<It>::type             element_type;
 270
 271     constexpr It base() const {return it_;}
 272
 273     constexpr three_way_contiguous_iterator() : it_() {}
 274     constexpr explicit three_way_contiguous_iterator(It it) : it_(it) {}
 275     template <class U>
 276     constexpr three_way_contiguous_iterator(const three_way_contiguous_iterator<U>& u) : it_(u.it_) {}
 277
 278     constexpr reference operator*() const {return *it_;}
 279     constexpr pointer operator->() const {return it_;}
 280     constexpr reference operator[](difference_type n) const {return it_[n];}
 281
 282     constexpr three_way_contiguous_iterator& operator++() {++it_; return *this;}
 283     constexpr three_way_contiguous_iterator& operator--() {--it_; return *this;}
 284     constexpr three_way_contiguous_iterator operator++(int) {return three_way_contiguous_iterator(it_++);}
 285     constexpr three_way_contiguous_iterator operator--(int) {return three_way_contiguous_iterator(it_--);}
 286
 287     constexpr three_way_contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;}
 288     constexpr three_way_contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;}
 289     friend constexpr three_way_contiguous_iterator operator+(three_way_contiguous_iterator x, difference_type n) {x += n; return x;}
 290     friend constexpr three_way_contiguous_iterator operator+(difference_type n, three_way_contiguous_iterator x) {x += n; return x;}
 291     friend constexpr three_way_contiguous_iterator operator-(three_way_contiguous_iterator x, difference_type n) {x -= n; return x;}
 292     friend constexpr difference_type operator-(three_way_contiguous_iterator x, three_way_contiguous_iterator y) {return x.it_ - y.it_;}
 293
 294     friend constexpr auto operator<=>(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ <=> y.it_;}
 295     friend constexpr bool operator==(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ == y.it_;}
 296
 297     template <class T>
 298     void operator,(T const &) = delete;
 299 };
 300 #endif // TEST_STD_VER > 17
 301
 302 template <class Iter> // ADL base() for everything else (including pointers)
 303 TEST_CONSTEXPR Iter base(Iter i) { return i; }
 304
 305 template <typename T>
 306 struct ThrowingIterator {
 307     typedef std::bidirectional_iterator_tag iterator_category;
 308     typedef ptrdiff_t                       difference_type;
 309     typedef const T                         value_type;
 310     typedef const T *                       pointer;
 311     typedef const T &                       reference;
 312
 313     enum ThrowingAction { TAIncrement, TADecrement, TADereference, TAAssignment, TAComparison };
 314
 315     TEST_CONSTEXPR ThrowingIterator()
 316         : begin_(nullptr), end_(nullptr), current_(nullptr), action_(TADereference), index_(0) {}
 317     TEST_CONSTEXPR explicit ThrowingIterator(const T* first, const T* last, int index = 0,
 318                                                    ThrowingAction action = TADereference)
 319         : begin_(first), end_(last), current_(first), action_(action), index_(index) {}
 320     TEST_CONSTEXPR ThrowingIterator(const ThrowingIterator &rhs)
 321         : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_), action_(rhs.action_), index_(rhs.index_) {}
 322
 323     TEST_CONSTEXPR_CXX14 ThrowingIterator& operator=(const ThrowingIterator& rhs) {
 324         if (action_ == TAAssignment && --index_ < 0) {
 325 #ifndef TEST_HAS_NO_EXCEPTIONS
 326             throw std::runtime_error("throw from iterator assignment");
 327 #else
 328             assert(false);
 329 #endif
 330         }
 331         begin_ = rhs.begin_;
 332         end_ = rhs.end_;
 333         current_ = rhs.current_;
 334         action_ = rhs.action_;
 335         index_ = rhs.index_;
 336         return *this;
 337     }
 338
 339     TEST_CONSTEXPR_CXX14 reference operator*() const {
 340         if (action_ == TADereference && --index_ < 0) {
 341 #ifndef TEST_HAS_NO_EXCEPTIONS
 342             throw std::runtime_error("throw from iterator dereference");
 343 #else
 344             assert(false);
 345 #endif
 346         }
 347         return *current_;
 348     }
 349
 350     TEST_CONSTEXPR_CXX14 ThrowingIterator& operator++() {
 351         if (action_ == TAIncrement && --index_ < 0) {
 352 #ifndef TEST_HAS_NO_EXCEPTIONS
 353             throw std::runtime_error("throw from iterator increment");
 354 #else
 355             assert(false);
 356 #endif
 357         }
 358         ++current_;
 359         return *this;
 360     }
 361
 362     TEST_CONSTEXPR_CXX14 ThrowingIterator operator++(int) {
 363         ThrowingIterator temp = *this;
 364         ++(*this);
 365         return temp;
 366     }
 367
 368     TEST_CONSTEXPR_CXX14 ThrowingIterator& operator--() {
 369         if (action_ == TADecrement && --index_ < 0) {
 370 #ifndef TEST_HAS_NO_EXCEPTIONS
 371             throw std::runtime_error("throw from iterator decrement");
 372 #else
 373             assert(false);
 374 #endif
 375         }
 376         --current_;
 377         return *this;
 378     }
 379
 380     TEST_CONSTEXPR_CXX14 ThrowingIterator operator--(int) {
 381         ThrowingIterator temp = *this;
 382         --(*this);
 383         return temp;
 384     }
 385
 386     TEST_CONSTEXPR_CXX14 friend bool operator==(const ThrowingIterator& a, const ThrowingIterator& b) {
 387         if (a.action_ == TAComparison && --a.index_ < 0) {
 388 #ifndef TEST_HAS_NO_EXCEPTIONS
 389             throw std::runtime_error("throw from iterator comparison");
 390 #else
 391             assert(false);
 392 #endif
 393         }
 394         bool atEndL = a.current_ == a.end_;
 395         bool atEndR = b.current_ == b.end_;
 396         if (atEndL != atEndR) return false;  // one is at the end (or empty), the other is not.
 397         if (atEndL) return true;             // both are at the end (or empty)
 398         return a.current_ == b.current_;
 399     }
 400
 401     TEST_CONSTEXPR friend bool operator!=(const ThrowingIterator& a, const ThrowingIterator& b) {
 402         return !(a == b);
 403     }
 404
 405     template <class T2>
 406     void operator,(T2 const &) = delete;
 407
 408 private:
 409     const T* begin_;
 410     const T* end_;
 411     const T* current_;
 412     ThrowingAction action_;
 413     mutable int index_;
 414 };
 415
 416 template <typename T>
 417 struct NonThrowingIterator {
 418     typedef std::bidirectional_iterator_tag iterator_category;
 419     typedef ptrdiff_t                       difference_type;
 420     typedef const T                         value_type;
 421     typedef const T *                       pointer;
 422     typedef const T &                       reference;
 423
 424     NonThrowingIterator()
 425         : begin_(nullptr), end_(nullptr), current_(nullptr) {}
 426     explicit NonThrowingIterator(const T *first, const T *last)
 427         : begin_(first), end_(last), current_(first) {}
 428     NonThrowingIterator(const NonThrowingIterator& rhs)
 429         : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_) {}
 430
 431     NonThrowingIterator& operator=(const NonThrowingIterator& rhs) TEST_NOEXCEPT {
 432         begin_ = rhs.begin_;
 433         end_ = rhs.end_;
 434         current_ = rhs.current_;
 435         return *this;
 436     }
 437
 438     reference operator*() const TEST_NOEXCEPT {
 439         return *current_;
 440     }
 441
 442     NonThrowingIterator& operator++() TEST_NOEXCEPT {
 443         ++current_;
 444         return *this;
 445     }
 446
 447     NonThrowingIterator operator++(int) TEST_NOEXCEPT {
 448         NonThrowingIterator temp = *this;
 449         ++(*this);
 450         return temp;
 451     }
 452
 453     NonThrowingIterator & operator--() TEST_NOEXCEPT {
 454         --current_;
 455         return *this;
 456     }
 457
 458     NonThrowingIterator operator--(int) TEST_NOEXCEPT {
 459         NonThrowingIterator temp = *this;
 460         --(*this);
 461         return temp;
 462     }
 463
 464     friend bool operator==(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT {
 465         bool atEndL = a.current_ == a.end_;
 466         bool atEndR = b.current_ == b.end_;
 467         if (atEndL != atEndR) return false;  // one is at the end (or empty), the other is not.
 468         if (atEndL) return true;             // both are at the end (or empty)
 469         return a.current_ == b.current_;
 470     }
 471
 472     friend bool operator!=(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT {
 473         return !(a == b);
 474     }
 475
 476     template <class T2>
 477     void operator,(T2 const &) = delete;
 478
 479 private:
 480     const T *begin_;
 481     const T *end_;
 482     const T *current_;
 483 };
 484
 485 #if TEST_STD_VER > 17
 486
 487 template <class It>
 488 class cpp20_input_iterator
 489 {
 490     It it_;
 491
 492 public:
 493     using value_type = std::iter_value_t<It>;
 494     using difference_type = std::iter_difference_t<It>;
 495     using iterator_concept = std::input_iterator_tag;
 496
 497     constexpr explicit cpp20_input_iterator(It it) : it_(it) {}
 498     cpp20_input_iterator(cpp20_input_iterator&&) = default;
 499     cpp20_input_iterator& operator=(cpp20_input_iterator&&) = default;
 500     constexpr decltype(auto) operator*() const { return *it_; }
 501     constexpr cpp20_input_iterator& operator++() { ++it_; return *this; }
 502     constexpr void operator++(int) { ++it_; }
 503
 504     friend constexpr It base(const cpp20_input_iterator& i) { return i.it_; }
 505
 506     template <class T>
 507     void operator,(T const &) = delete;
 508 };
 509
 510 template<std::input_or_output_iterator>
 511 struct iter_value_or_void { using type = void; };
 512
 513 template<std::input_iterator I>
 514 struct iter_value_or_void<I> {
 515     using type = std::iter_value_t<I>;
 516 };
 517
 518 // Iterator adaptor that counts the number of times the iterator has had a successor/predecessor
 519 // operation called. Has two recorders:
 520 // * `stride_count`, which records the total number of calls to an op++, op--, op+=, or op-=.
 521 // * `stride_displacement`, which records the displacement of the calls. This means that both
 522 //   op++/op+= will increase the displacement counter by 1, and op--/op-= will decrease the
 523 //   displacement counter by 1.
 524 template <class It>
 525 class stride_counting_iterator {
 526 public:
 527     using value_type = typename iter_value_or_void<It>::type;
 528     using difference_type = std::iter_difference_t<It>;
 529     using iterator_concept =
 530         std::conditional_t<std::contiguous_iterator<It>,    std::contiguous_iterator_tag,
 531         std::conditional_t<std::random_access_iterator<It>, std::random_access_iterator_tag,
 532         std::conditional_t<std::bidirectional_iterator<It>, std::bidirectional_iterator_tag,
 533         std::conditional_t<std::forward_iterator<It>,       std::forward_iterator_tag,
 534         std::conditional_t<std::input_iterator<It>,         std::input_iterator_tag,
 535         /* else */                                          std::output_iterator_tag
 536     >>>>>;
 537
 538     stride_counting_iterator() requires std::default_initializable<It> = default;
 539
 540     constexpr explicit stride_counting_iterator(It const& it) : base_(base(it)) { }
 541
 542     friend constexpr It base(stride_counting_iterator const& it) { return It(it.base_); }
 543
 544     constexpr difference_type stride_count() const { return stride_count_; }
 545
 546     constexpr difference_type stride_displacement() const { return stride_displacement_; }
 547
 548     constexpr decltype(auto) operator*() const { return *It(base_); }
 549
 550     constexpr decltype(auto) operator[](difference_type n) const { return It(base_)[n]; }
 551
 552     constexpr stride_counting_iterator& operator++() {
 553         It tmp(base_);
 554         base_ = base(++tmp);
 555         ++stride_count_;
 556         ++stride_displacement_;
 557         return *this;
 558     }
 559
 560     constexpr void operator++(int) { ++*this; }
 561
 562     constexpr stride_counting_iterator operator++(int)
 563         requires std::forward_iterator<It>
 564     {
 565         auto temp = *this;
 566         ++*this;
 567         return temp;
 568     }
 569
 570     constexpr stride_counting_iterator& operator--()
 571         requires std::bidirectional_iterator<It>
 572     {
 573         It tmp(base_);
 574         base_ = base(--tmp);
 575         ++stride_count_;
 576         --stride_displacement_;
 577         return *this;
 578     }
 579
 580     constexpr stride_counting_iterator operator--(int)
 581         requires std::bidirectional_iterator<It>
 582     {
 583         auto temp = *this;
 584         --*this;
 585         return temp;
 586     }
 587
 588     constexpr stride_counting_iterator& operator+=(difference_type const n)
 589         requires std::random_access_iterator<It>
 590     {
 591         It tmp(base_);
 592         base_ = base(tmp += n);
 593         ++stride_count_;
 594         ++stride_displacement_;
 595         return *this;
 596     }
 597
 598     constexpr stride_counting_iterator& operator-=(difference_type const n)
 599         requires std::random_access_iterator<It>
 600     {
 601         It tmp(base_);
 602         base_ = base(tmp -= n);
 603         ++stride_count_;
 604         --stride_displacement_;
 605         return *this;
 606     }
 607
 608     friend constexpr stride_counting_iterator operator+(stride_counting_iterator it, difference_type n)
 609         requires std::random_access_iterator<It>
 610     {
 611         return it += n;
 612     }
 613
 614     friend constexpr stride_counting_iterator operator+(difference_type n, stride_counting_iterator it)
 615         requires std::random_access_iterator<It>
 616     {
 617         return it += n;
 618     }
 619
 620     friend constexpr stride_counting_iterator operator-(stride_counting_iterator it, difference_type n)
 621         requires std::random_access_iterator<It>
 622     {
 623         return it -= n;
 624     }
 625
 626     friend constexpr difference_type operator-(stride_counting_iterator const& x, stride_counting_iterator const& y)
 627         requires std::sized_sentinel_for<It, It>
 628     {
 629         return base(x) - base(y);
 630     }
 631
 632     constexpr bool operator==(stride_counting_iterator const& other) const
 633         requires std::sentinel_for<It, It>
 634     {
 635         return It(base_) == It(other.base_);
 636     }
 637
 638     friend constexpr bool operator<(stride_counting_iterator const& x, stride_counting_iterator const& y)
 639         requires std::random_access_iterator<It>
 640     {
 641         return It(x.base_) < It(y.base_);
 642     }
 643
 644     friend constexpr bool operator>(stride_counting_iterator const& x, stride_counting_iterator const& y)
 645         requires std::random_access_iterator<It>
 646     {
 647         return It(x.base_) > It(y.base_);
 648     }
 649
 650     friend constexpr bool operator<=(stride_counting_iterator const& x, stride_counting_iterator const& y)
 651         requires std::random_access_iterator<It>
 652     {
 653         return It(x.base_) <= It(y.base_);
 654     }
 655
 656     friend constexpr bool operator>=(stride_counting_iterator const& x, stride_counting_iterator const& y)
 657         requires std::random_access_iterator<It>
 658     {
 659         return It(x.base_) >= It(y.base_);
 660     }
 661
 662     template <class T>
 663     void operator,(T const &) = delete;
 664
 665 private:
 666     decltype(base(std::declval<It>())) base_;
 667     difference_type stride_count_ = 0;
 668     difference_type stride_displacement_ = 0;
 669 };
 670
 671 #endif // TEST_STD_VER > 17
 672
 673 #if TEST_STD_VER > 17
 674 template <class It>
 675 class sentinel_wrapper {
 676 public:
 677     explicit sentinel_wrapper() = default;
 678     constexpr explicit sentinel_wrapper(const It& it) : base_(base(it)) {}
 679     constexpr bool operator==(const It& other) const { return base_ == base(other); }
 680     friend constexpr It base(const sentinel_wrapper& s) { return It(s.base_); }
 681 private:
 682     decltype(base(std::declval<It>())) base_;
 683 };
 684
 685 template <class It>
 686 class sized_sentinel {
 687 public:
 688     explicit sized_sentinel() = default;
 689     constexpr explicit sized_sentinel(const It& it) : base_(base(it)) {}
 690     constexpr bool operator==(const It& other) const { return base_ == base(other); }
 691     friend constexpr auto operator-(const sized_sentinel& s, const It& i) { return s.base_ - base(i); }
 692     friend constexpr auto operator-(const It& i, const sized_sentinel& s) { return base(i) - s.base_; }
 693     friend constexpr It base(const sized_sentinel& s) { return It(s.base_); }
 694 private:
 695     decltype(base(std::declval<It>())) base_;
 696 };
 697 #endif // TEST_STD_VER > 17
 698
 699 #endif // SUPPORT_TEST_ITERATORS_H