1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef SUPPORT_TEST_ITERATORS_H 10 #define SUPPORT_TEST_ITERATORS_H 11 12 #include <cassert> 13 #include <concepts> 14 #include <iterator> 15 #include <ranges> 16 #include <stdexcept> 17 #include <type_traits> 18 #include <utility> 19 20 #include "test_macros.h" 21 22 23 // This iterator meets C++20's Cpp17OutputIterator requirements, as described 24 // in Table 90 ([output.iterators]). 25 template <class It> 26 class cpp17_output_iterator 27 { 28 It it_; 29 30 template <class U> friend class cpp17_output_iterator; 31 public: 32 typedef std::output_iterator_tag iterator_category; 33 typedef void value_type; 34 typedef typename std::iterator_traits<It>::difference_type difference_type; 35 typedef It pointer; 36 typedef typename std::iterator_traits<It>::reference reference; 37 38 TEST_CONSTEXPR explicit cpp17_output_iterator(It it) : it_(std::move(it)) {} 39 40 template <class U> 41 TEST_CONSTEXPR cpp17_output_iterator(const cpp17_output_iterator<U>& u) : it_(u.it_) {} 42 43 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 44 TEST_CONSTEXPR_CXX14 cpp17_output_iterator(cpp17_output_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); } 45 46 TEST_CONSTEXPR reference operator*() const {return *it_;} 47 48 TEST_CONSTEXPR_CXX14 cpp17_output_iterator& operator++() {++it_; return *this;} 49 TEST_CONSTEXPR_CXX14 cpp17_output_iterator operator++(int) {return cpp17_output_iterator(it_++);} 50 51 friend TEST_CONSTEXPR It base(const cpp17_output_iterator& i) { return i.it_; } 52 53 template <class T> 54 void operator,(T const &) = delete; 55 }; 56 #if _LIBCPP_STD_VER > 17 57 static_assert(std::output_iterator<cpp17_output_iterator<int*>, int>); 58 #endif 59 60 // This iterator meets C++20's Cpp17InputIterator requirements, as described 61 // in Table 89 ([input.iterators]). 62 template <class It, class ItTraits = It> 63 class cpp17_input_iterator 64 { 65 typedef std::iterator_traits<ItTraits> Traits; 66 It it_; 67 68 template <class U, class T> friend class cpp17_input_iterator; 69 public: 70 typedef std::input_iterator_tag iterator_category; 71 typedef typename Traits::value_type value_type; 72 typedef typename Traits::difference_type difference_type; 73 typedef It pointer; 74 typedef typename Traits::reference reference; 75 76 TEST_CONSTEXPR explicit cpp17_input_iterator(It it) : it_(it) {} 77 78 template <class U, class T> 79 TEST_CONSTEXPR cpp17_input_iterator(const cpp17_input_iterator<U, T>& u) : it_(u.it_) {} 80 81 template <class U, class T, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 82 TEST_CONSTEXPR_CXX14 cpp17_input_iterator(cpp17_input_iterator<U, T>&& u) : it_(u.it_) { u.it_ = U(); } 83 84 TEST_CONSTEXPR reference operator*() const {return *it_;} 85 86 TEST_CONSTEXPR_CXX14 cpp17_input_iterator& operator++() {++it_; return *this;} 87 TEST_CONSTEXPR_CXX14 cpp17_input_iterator operator++(int) {return cpp17_input_iterator(it_++);} 88 89 friend TEST_CONSTEXPR bool operator==(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ == y.it_;} 90 friend TEST_CONSTEXPR bool operator!=(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ != y.it_;} 91 92 friend TEST_CONSTEXPR It base(const cpp17_input_iterator& i) { return i.it_; } 93 94 template <class T> 95 void operator,(T const &) = delete; 96 }; 97 #if _LIBCPP_STD_VER > 17 98 static_assert(std::input_iterator<cpp17_input_iterator<int*>>); 99 #endif 100 101 template <class It> 102 class forward_iterator 103 { 104 It it_; 105 106 template <class U> friend class forward_iterator; 107 public: 108 typedef std::forward_iterator_tag iterator_category; 109 typedef typename std::iterator_traits<It>::value_type value_type; 110 typedef typename std::iterator_traits<It>::difference_type difference_type; 111 typedef It pointer; 112 typedef typename std::iterator_traits<It>::reference reference; 113 114 TEST_CONSTEXPR forward_iterator() : it_() {} 115 TEST_CONSTEXPR explicit forward_iterator(It it) : it_(it) {} 116 117 template <class U> 118 TEST_CONSTEXPR forward_iterator(const forward_iterator<U>& u) : it_(u.it_) {} 119 120 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 121 TEST_CONSTEXPR_CXX14 forward_iterator(forward_iterator<U>&& other) : it_(other.it_) { other.it_ = U(); } 122 123 TEST_CONSTEXPR reference operator*() const {return *it_;} 124 125 TEST_CONSTEXPR_CXX14 forward_iterator& operator++() {++it_; return *this;} 126 TEST_CONSTEXPR_CXX14 forward_iterator operator++(int) {return forward_iterator(it_++);} 127 128 friend TEST_CONSTEXPR bool operator==(const forward_iterator& x, const forward_iterator& y) {return x.it_ == y.it_;} 129 friend TEST_CONSTEXPR bool operator!=(const forward_iterator& x, const forward_iterator& y) {return x.it_ != y.it_;} 130 131 friend TEST_CONSTEXPR It base(const forward_iterator& i) { return i.it_; } 132 133 template <class T> 134 void operator,(T const &) = delete; 135 }; 136 137 template <class It> 138 class bidirectional_iterator 139 { 140 It it_; 141 142 template <class U> friend class bidirectional_iterator; 143 public: 144 typedef std::bidirectional_iterator_tag iterator_category; 145 typedef typename std::iterator_traits<It>::value_type value_type; 146 typedef typename std::iterator_traits<It>::difference_type difference_type; 147 typedef It pointer; 148 typedef typename std::iterator_traits<It>::reference reference; 149 150 TEST_CONSTEXPR bidirectional_iterator() : it_() {} 151 TEST_CONSTEXPR explicit bidirectional_iterator(It it) : it_(it) {} 152 153 template <class U> 154 TEST_CONSTEXPR bidirectional_iterator(const bidirectional_iterator<U>& u) : it_(u.it_) {} 155 156 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 157 TEST_CONSTEXPR_CXX14 bidirectional_iterator(bidirectional_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); } 158 159 TEST_CONSTEXPR reference operator*() const {return *it_;} 160 161 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator++() {++it_; return *this;} 162 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator--() {--it_; return *this;} 163 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator++(int) {return bidirectional_iterator(it_++);} 164 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator--(int) {return bidirectional_iterator(it_--);} 165 166 friend TEST_CONSTEXPR bool operator==(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ == y.it_;} 167 friend TEST_CONSTEXPR bool operator!=(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ != y.it_;} 168 169 friend TEST_CONSTEXPR It base(const bidirectional_iterator& i) { return i.it_; } 170 171 template <class T> 172 void operator,(T const &) = delete; 173 }; 174 175 template <class It> 176 class random_access_iterator 177 { 178 It it_; 179 180 template <class U> friend class random_access_iterator; 181 public: 182 typedef std::random_access_iterator_tag iterator_category; 183 typedef typename std::iterator_traits<It>::value_type value_type; 184 typedef typename std::iterator_traits<It>::difference_type difference_type; 185 typedef It pointer; 186 typedef typename std::iterator_traits<It>::reference reference; 187 188 TEST_CONSTEXPR random_access_iterator() : it_() {} 189 TEST_CONSTEXPR explicit random_access_iterator(It it) : it_(it) {} 190 191 template <class U> 192 TEST_CONSTEXPR random_access_iterator(const random_access_iterator<U>& u) : it_(u.it_) {} 193 194 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 195 TEST_CONSTEXPR_CXX14 random_access_iterator(random_access_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); } 196 197 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;} 198 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];} 199 200 TEST_CONSTEXPR_CXX14 random_access_iterator& operator++() {++it_; return *this;} 201 TEST_CONSTEXPR_CXX14 random_access_iterator& operator--() {--it_; return *this;} 202 TEST_CONSTEXPR_CXX14 random_access_iterator operator++(int) {return random_access_iterator(it_++);} 203 TEST_CONSTEXPR_CXX14 random_access_iterator operator--(int) {return random_access_iterator(it_--);} 204 205 TEST_CONSTEXPR_CXX14 random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;} 206 TEST_CONSTEXPR_CXX14 random_access_iterator& operator-=(difference_type n) {it_ -= n; return *this;} 207 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(random_access_iterator x, difference_type n) {x += n; return x;} 208 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(difference_type n, random_access_iterator x) {x += n; return x;} 209 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator-(random_access_iterator x, difference_type n) {x -= n; return x;} 210 friend TEST_CONSTEXPR difference_type operator-(random_access_iterator x, random_access_iterator y) {return x.it_ - y.it_;} 211 212 friend TEST_CONSTEXPR bool operator==(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ == y.it_;} 213 friend TEST_CONSTEXPR bool operator!=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ != y.it_;} 214 friend TEST_CONSTEXPR bool operator< (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ < y.it_;} 215 friend TEST_CONSTEXPR bool operator<=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ <= y.it_;} 216 friend TEST_CONSTEXPR bool operator> (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ > y.it_;} 217 friend TEST_CONSTEXPR bool operator>=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ >= y.it_;} 218 219 friend TEST_CONSTEXPR It base(const random_access_iterator& i) { return i.it_; } 220 221 template <class T> 222 void operator,(T const &) = delete; 223 }; 224 225 #if TEST_STD_VER > 17 226 template <class It> 227 class contiguous_iterator 228 { 229 static_assert(std::is_pointer_v<It>, "Things probably break in this case"); 230 231 It it_; 232 233 template <class U> friend class contiguous_iterator; 234 public: 235 typedef std::contiguous_iterator_tag iterator_category; 236 typedef typename std::iterator_traits<It>::value_type value_type; 237 typedef typename std::iterator_traits<It>::difference_type difference_type; 238 typedef It pointer; 239 typedef typename std::iterator_traits<It>::reference reference; 240 typedef typename std::remove_pointer<It>::type element_type; 241 242 TEST_CONSTEXPR_CXX14 It base() const {return it_;} 243 244 TEST_CONSTEXPR_CXX14 contiguous_iterator() : it_() {} 245 TEST_CONSTEXPR_CXX14 explicit contiguous_iterator(It it) : it_(it) {} 246 247 template <class U> 248 TEST_CONSTEXPR_CXX14 contiguous_iterator(const contiguous_iterator<U>& u) : it_(u.it_) {} 249 250 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 251 constexpr contiguous_iterator(contiguous_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); } 252 253 TEST_CONSTEXPR reference operator*() const {return *it_;} 254 TEST_CONSTEXPR pointer operator->() const {return it_;} 255 TEST_CONSTEXPR reference operator[](difference_type n) const {return it_[n];} 256 257 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator++() {++it_; return *this;} 258 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator--() {--it_; return *this;} 259 TEST_CONSTEXPR_CXX14 contiguous_iterator operator++(int) {return contiguous_iterator(it_++);} 260 TEST_CONSTEXPR_CXX14 contiguous_iterator operator--(int) {return contiguous_iterator(it_--);} 261 262 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;} 263 TEST_CONSTEXPR_CXX14 contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;} 264 friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(contiguous_iterator x, difference_type n) {x += n; return x;} 265 friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator+(difference_type n, contiguous_iterator x) {x += n; return x;} 266 friend TEST_CONSTEXPR_CXX14 contiguous_iterator operator-(contiguous_iterator x, difference_type n) {x -= n; return x;} 267 friend TEST_CONSTEXPR difference_type operator-(contiguous_iterator x, contiguous_iterator y) {return x.it_ - y.it_;} 268 269 friend TEST_CONSTEXPR bool operator==(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ == y.it_;} 270 friend TEST_CONSTEXPR bool operator!=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ != y.it_;} 271 friend TEST_CONSTEXPR bool operator< (const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ < y.it_;} 272 friend TEST_CONSTEXPR bool operator<=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ <= y.it_;} 273 friend TEST_CONSTEXPR bool operator> (const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ > y.it_;} 274 friend TEST_CONSTEXPR bool operator>=(const contiguous_iterator& x, const contiguous_iterator& y) {return x.it_ >= y.it_;} 275 276 friend TEST_CONSTEXPR It base(const contiguous_iterator& i) { return i.it_; } 277 278 template <class T> 279 void operator,(T const &) = delete; 280 }; 281 282 template <class It> 283 class three_way_contiguous_iterator 284 { 285 static_assert(std::is_pointer_v<It>, "Things probably break in this case"); 286 287 It it_; 288 289 template <class U> friend class three_way_contiguous_iterator; 290 public: 291 typedef std::contiguous_iterator_tag iterator_category; 292 typedef typename std::iterator_traits<It>::value_type value_type; 293 typedef typename std::iterator_traits<It>::difference_type difference_type; 294 typedef It pointer; 295 typedef typename std::iterator_traits<It>::reference reference; 296 typedef typename std::remove_pointer<It>::type element_type; 297 298 constexpr It base() const {return it_;} 299 300 constexpr three_way_contiguous_iterator() : it_() {} 301 constexpr explicit three_way_contiguous_iterator(It it) : it_(it) {} 302 303 template <class U> 304 constexpr three_way_contiguous_iterator(const three_way_contiguous_iterator<U>& u) : it_(u.it_) {} 305 306 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type> 307 constexpr three_way_contiguous_iterator(three_way_contiguous_iterator<U>&& u) : it_(u.it_) { u.it_ = U(); } 308 309 constexpr reference operator*() const {return *it_;} 310 constexpr pointer operator->() const {return it_;} 311 constexpr reference operator[](difference_type n) const {return it_[n];} 312 313 constexpr three_way_contiguous_iterator& operator++() {++it_; return *this;} 314 constexpr three_way_contiguous_iterator& operator--() {--it_; return *this;} 315 constexpr three_way_contiguous_iterator operator++(int) {return three_way_contiguous_iterator(it_++);} 316 constexpr three_way_contiguous_iterator operator--(int) {return three_way_contiguous_iterator(it_--);} 317 318 constexpr three_way_contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;} 319 constexpr three_way_contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;} 320 friend constexpr three_way_contiguous_iterator operator+(three_way_contiguous_iterator x, difference_type n) {x += n; return x;} 321 friend constexpr three_way_contiguous_iterator operator+(difference_type n, three_way_contiguous_iterator x) {x += n; return x;} 322 friend constexpr three_way_contiguous_iterator operator-(three_way_contiguous_iterator x, difference_type n) {x -= n; return x;} 323 friend constexpr difference_type operator-(three_way_contiguous_iterator x, three_way_contiguous_iterator y) {return x.it_ - y.it_;} 324 325 friend constexpr auto operator<=>(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ <=> y.it_;} 326 friend constexpr bool operator==(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ == y.it_;} 327 328 template <class T> 329 void operator,(T const &) = delete; 330 }; 331 #endif // TEST_STD_VER > 17 332 333 template <class Iter> // ADL base() for everything else (including pointers) 334 TEST_CONSTEXPR Iter base(Iter i) { return i; } 335 336 template <typename T> 337 struct ThrowingIterator { 338 typedef std::bidirectional_iterator_tag iterator_category; 339 typedef ptrdiff_t difference_type; 340 typedef const T value_type; 341 typedef const T * pointer; 342 typedef const T & reference; 343 344 enum ThrowingAction { TAIncrement, TADecrement, TADereference, TAAssignment, TAComparison }; 345 346 TEST_CONSTEXPR ThrowingIterator() 347 : begin_(nullptr), end_(nullptr), current_(nullptr), action_(TADereference), index_(0) {} 348 TEST_CONSTEXPR explicit ThrowingIterator(const T* first, const T* last, int index = 0, 349 ThrowingAction action = TADereference) 350 : begin_(first), end_(last), current_(first), action_(action), index_(index) {} 351 TEST_CONSTEXPR ThrowingIterator(const ThrowingIterator &rhs) 352 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_), action_(rhs.action_), index_(rhs.index_) {} 353 354 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator=(const ThrowingIterator& rhs) { 355 if (action_ == TAAssignment && --index_ < 0) { 356 #ifndef TEST_HAS_NO_EXCEPTIONS 357 throw std::runtime_error("throw from iterator assignment"); 358 #else 359 assert(false); 360 #endif 361 } 362 begin_ = rhs.begin_; 363 end_ = rhs.end_; 364 current_ = rhs.current_; 365 action_ = rhs.action_; 366 index_ = rhs.index_; 367 return *this; 368 } 369 370 TEST_CONSTEXPR_CXX14 reference operator*() const { 371 if (action_ == TADereference && --index_ < 0) { 372 #ifndef TEST_HAS_NO_EXCEPTIONS 373 throw std::runtime_error("throw from iterator dereference"); 374 #else 375 assert(false); 376 #endif 377 } 378 return *current_; 379 } 380 381 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator++() { 382 if (action_ == TAIncrement && --index_ < 0) { 383 #ifndef TEST_HAS_NO_EXCEPTIONS 384 throw std::runtime_error("throw from iterator increment"); 385 #else 386 assert(false); 387 #endif 388 } 389 ++current_; 390 return *this; 391 } 392 393 TEST_CONSTEXPR_CXX14 ThrowingIterator operator++(int) { 394 ThrowingIterator temp = *this; 395 ++(*this); 396 return temp; 397 } 398 399 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator--() { 400 if (action_ == TADecrement && --index_ < 0) { 401 #ifndef TEST_HAS_NO_EXCEPTIONS 402 throw std::runtime_error("throw from iterator decrement"); 403 #else 404 assert(false); 405 #endif 406 } 407 --current_; 408 return *this; 409 } 410 411 TEST_CONSTEXPR_CXX14 ThrowingIterator operator--(int) { 412 ThrowingIterator temp = *this; 413 --(*this); 414 return temp; 415 } 416 417 TEST_CONSTEXPR_CXX14 friend bool operator==(const ThrowingIterator& a, const ThrowingIterator& b) { 418 if (a.action_ == TAComparison && --a.index_ < 0) { 419 #ifndef TEST_HAS_NO_EXCEPTIONS 420 throw std::runtime_error("throw from iterator comparison"); 421 #else 422 assert(false); 423 #endif 424 } 425 bool atEndL = a.current_ == a.end_; 426 bool atEndR = b.current_ == b.end_; 427 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not. 428 if (atEndL) return true; // both are at the end (or empty) 429 return a.current_ == b.current_; 430 } 431 432 TEST_CONSTEXPR friend bool operator!=(const ThrowingIterator& a, const ThrowingIterator& b) { 433 return !(a == b); 434 } 435 436 template <class T2> 437 void operator,(T2 const &) = delete; 438 439 private: 440 const T* begin_; 441 const T* end_; 442 const T* current_; 443 ThrowingAction action_; 444 mutable int index_; 445 }; 446 447 template <typename T> 448 struct NonThrowingIterator { 449 typedef std::bidirectional_iterator_tag iterator_category; 450 typedef ptrdiff_t difference_type; 451 typedef const T value_type; 452 typedef const T * pointer; 453 typedef const T & reference; 454 455 NonThrowingIterator() 456 : begin_(nullptr), end_(nullptr), current_(nullptr) {} 457 explicit NonThrowingIterator(const T *first, const T *last) 458 : begin_(first), end_(last), current_(first) {} 459 NonThrowingIterator(const NonThrowingIterator& rhs) 460 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_) {} 461 462 NonThrowingIterator& operator=(const NonThrowingIterator& rhs) TEST_NOEXCEPT { 463 begin_ = rhs.begin_; 464 end_ = rhs.end_; 465 current_ = rhs.current_; 466 return *this; 467 } 468 469 reference operator*() const TEST_NOEXCEPT { 470 return *current_; 471 } 472 473 NonThrowingIterator& operator++() TEST_NOEXCEPT { 474 ++current_; 475 return *this; 476 } 477 478 NonThrowingIterator operator++(int) TEST_NOEXCEPT { 479 NonThrowingIterator temp = *this; 480 ++(*this); 481 return temp; 482 } 483 484 NonThrowingIterator & operator--() TEST_NOEXCEPT { 485 --current_; 486 return *this; 487 } 488 489 NonThrowingIterator operator--(int) TEST_NOEXCEPT { 490 NonThrowingIterator temp = *this; 491 --(*this); 492 return temp; 493 } 494 495 friend bool operator==(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT { 496 bool atEndL = a.current_ == a.end_; 497 bool atEndR = b.current_ == b.end_; 498 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not. 499 if (atEndL) return true; // both are at the end (or empty) 500 return a.current_ == b.current_; 501 } 502 503 friend bool operator!=(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT { 504 return !(a == b); 505 } 506 507 template <class T2> 508 void operator,(T2 const &) = delete; 509 510 private: 511 const T *begin_; 512 const T *end_; 513 const T *current_; 514 }; 515 516 #if TEST_STD_VER > 17 517 518 template <class It> 519 class cpp20_input_iterator 520 { 521 It it_; 522 523 public: 524 using value_type = std::iter_value_t<It>; 525 using difference_type = std::iter_difference_t<It>; 526 using iterator_concept = std::input_iterator_tag; 527 528 constexpr explicit cpp20_input_iterator(It it) : it_(it) {} 529 cpp20_input_iterator(cpp20_input_iterator&&) = default; 530 cpp20_input_iterator& operator=(cpp20_input_iterator&&) = default; 531 constexpr decltype(auto) operator*() const { return *it_; } 532 constexpr cpp20_input_iterator& operator++() { ++it_; return *this; } 533 constexpr void operator++(int) { ++it_; } 534 535 friend constexpr It base(const cpp20_input_iterator& i) { return i.it_; } 536 537 template <class T> 538 void operator,(T const &) = delete; 539 }; 540 static_assert(std::input_iterator<cpp20_input_iterator<int*>>); 541 542 template<std::input_or_output_iterator> 543 struct iter_value_or_void { using type = void; }; 544 545 template<std::input_iterator I> 546 struct iter_value_or_void<I> { 547 using type = std::iter_value_t<I>; 548 }; 549 550 template <class It> 551 class cpp20_output_iterator { 552 It it_; 553 554 public: 555 using difference_type = std::iter_difference_t<It>; 556 557 constexpr explicit cpp20_output_iterator(It it) : it_(it) {} 558 cpp20_output_iterator(cpp20_output_iterator&&) = default; 559 cpp20_output_iterator& operator=(cpp20_output_iterator&&) = default; 560 561 constexpr decltype(auto) operator*() const { return *it_; } 562 constexpr cpp20_output_iterator& operator++() { 563 ++it_; 564 return *this; 565 } 566 constexpr cpp20_output_iterator operator++(int) { return cpp20_output_iterator(it_++); } 567 568 friend constexpr It base(const cpp20_output_iterator& i) { return i.it_; } 569 570 template <class T> 571 void operator,(T const&) = delete; 572 }; 573 574 static_assert(std::output_iterator<cpp20_output_iterator<int*>, int>); 575 576 // Iterator adaptor that counts the number of times the iterator has had a successor/predecessor 577 // operation called. Has two recorders: 578 // * `stride_count`, which records the total number of calls to an op++, op--, op+=, or op-=. 579 // * `stride_displacement`, which records the displacement of the calls. This means that both 580 // op++/op+= will increase the displacement counter by 1, and op--/op-= will decrease the 581 // displacement counter by 1. 582 template <class It> 583 class stride_counting_iterator { 584 public: 585 using value_type = typename iter_value_or_void<It>::type; 586 using difference_type = std::iter_difference_t<It>; 587 using iterator_concept = 588 std::conditional_t<std::contiguous_iterator<It>, std::contiguous_iterator_tag, 589 std::conditional_t<std::random_access_iterator<It>, std::random_access_iterator_tag, 590 std::conditional_t<std::bidirectional_iterator<It>, std::bidirectional_iterator_tag, 591 std::conditional_t<std::forward_iterator<It>, std::forward_iterator_tag, 592 std::conditional_t<std::input_iterator<It>, std::input_iterator_tag, 593 /* else */ std::output_iterator_tag 594 >>>>>; 595 596 stride_counting_iterator() requires std::default_initializable<It> = default; 597 598 constexpr explicit stride_counting_iterator(It const& it) : base_(base(it)) { } 599 600 friend constexpr It base(stride_counting_iterator const& it) { return It(it.base_); } 601 602 constexpr difference_type stride_count() const { return stride_count_; } 603 604 constexpr difference_type stride_displacement() const { return stride_displacement_; } 605 606 constexpr decltype(auto) operator*() const { return *It(base_); } 607 608 constexpr decltype(auto) operator[](difference_type n) const { return It(base_)[n]; } 609 610 constexpr stride_counting_iterator& operator++() { 611 It tmp(base_); 612 base_ = base(++tmp); 613 ++stride_count_; 614 ++stride_displacement_; 615 return *this; 616 } 617 618 constexpr void operator++(int) { ++*this; } 619 620 constexpr stride_counting_iterator operator++(int) 621 requires std::forward_iterator<It> 622 { 623 auto temp = *this; 624 ++*this; 625 return temp; 626 } 627 628 constexpr stride_counting_iterator& operator--() 629 requires std::bidirectional_iterator<It> 630 { 631 It tmp(base_); 632 base_ = base(--tmp); 633 ++stride_count_; 634 --stride_displacement_; 635 return *this; 636 } 637 638 constexpr stride_counting_iterator operator--(int) 639 requires std::bidirectional_iterator<It> 640 { 641 auto temp = *this; 642 --*this; 643 return temp; 644 } 645 646 constexpr stride_counting_iterator& operator+=(difference_type const n) 647 requires std::random_access_iterator<It> 648 { 649 It tmp(base_); 650 base_ = base(tmp += n); 651 ++stride_count_; 652 ++stride_displacement_; 653 return *this; 654 } 655 656 constexpr stride_counting_iterator& operator-=(difference_type const n) 657 requires std::random_access_iterator<It> 658 { 659 It tmp(base_); 660 base_ = base(tmp -= n); 661 ++stride_count_; 662 --stride_displacement_; 663 return *this; 664 } 665 666 friend constexpr stride_counting_iterator operator+(stride_counting_iterator it, difference_type n) 667 requires std::random_access_iterator<It> 668 { 669 return it += n; 670 } 671 672 friend constexpr stride_counting_iterator operator+(difference_type n, stride_counting_iterator it) 673 requires std::random_access_iterator<It> 674 { 675 return it += n; 676 } 677 678 friend constexpr stride_counting_iterator operator-(stride_counting_iterator it, difference_type n) 679 requires std::random_access_iterator<It> 680 { 681 return it -= n; 682 } 683 684 friend constexpr difference_type operator-(stride_counting_iterator const& x, stride_counting_iterator const& y) 685 requires std::sized_sentinel_for<It, It> 686 { 687 return base(x) - base(y); 688 } 689 690 constexpr bool operator==(stride_counting_iterator const& other) const 691 requires std::sentinel_for<It, It> 692 { 693 return It(base_) == It(other.base_); 694 } 695 696 friend constexpr bool operator<(stride_counting_iterator const& x, stride_counting_iterator const& y) 697 requires std::random_access_iterator<It> 698 { 699 return It(x.base_) < It(y.base_); 700 } 701 702 friend constexpr bool operator>(stride_counting_iterator const& x, stride_counting_iterator const& y) 703 requires std::random_access_iterator<It> 704 { 705 return It(x.base_) > It(y.base_); 706 } 707 708 friend constexpr bool operator<=(stride_counting_iterator const& x, stride_counting_iterator const& y) 709 requires std::random_access_iterator<It> 710 { 711 return It(x.base_) <= It(y.base_); 712 } 713 714 friend constexpr bool operator>=(stride_counting_iterator const& x, stride_counting_iterator const& y) 715 requires std::random_access_iterator<It> 716 { 717 return It(x.base_) >= It(y.base_); 718 } 719 720 template <class T> 721 void operator,(T const &) = delete; 722 723 private: 724 decltype(base(std::declval<It>())) base_; 725 difference_type stride_count_ = 0; 726 difference_type stride_displacement_ = 0; 727 }; 728 729 #endif // TEST_STD_VER > 17 730 731 #if TEST_STD_VER > 17 732 template <class It> 733 class sentinel_wrapper { 734 public: 735 explicit sentinel_wrapper() = default; 736 constexpr explicit sentinel_wrapper(const It& it) : base_(base(it)) {} 737 constexpr bool operator==(const It& other) const { return base_ == base(other); } 738 friend constexpr It base(const sentinel_wrapper& s) { return It(s.base_); } 739 private: 740 decltype(base(std::declval<It>())) base_; 741 }; 742 743 template <class It> 744 class sized_sentinel { 745 public: 746 explicit sized_sentinel() = default; 747 constexpr explicit sized_sentinel(const It& it) : base_(base(it)) {} 748 constexpr bool operator==(const It& other) const { return base_ == base(other); } 749 friend constexpr auto operator-(const sized_sentinel& s, const It& i) { return s.base_ - base(i); } 750 friend constexpr auto operator-(const It& i, const sized_sentinel& s) { return base(i) - s.base_; } 751 friend constexpr It base(const sized_sentinel& s) { return It(s.base_); } 752 private: 753 decltype(base(std::declval<It>())) base_; 754 }; 755 756 namespace adl { 757 758 class Iterator { 759 public: 760 using value_type = int; 761 using difference_type = ptrdiff_t; 762 763 private: 764 value_type* ptr_ = nullptr; 765 int* iter_moves_ = nullptr; 766 int* iter_swaps_ = nullptr; 767 768 constexpr Iterator(int* p, int* iter_moves, int* iter_swaps) 769 : ptr_(p) 770 , iter_moves_(iter_moves) 771 , iter_swaps_(iter_swaps) {} 772 773 public: 774 constexpr Iterator() = default; 775 static constexpr Iterator TrackMoves(int* p, int& iter_moves) { 776 return Iterator(p, &iter_moves, /*iter_swaps=*/nullptr); 777 } 778 static constexpr Iterator TrackSwaps(int& iter_swaps) { 779 return Iterator(/*p=*/nullptr, /*iter_moves=*/nullptr, &iter_swaps); 780 } 781 static constexpr Iterator TrackSwaps(int* p, int& iter_swaps) { 782 return Iterator(p, /*iter_moves=*/nullptr, &iter_swaps); 783 } 784 785 constexpr int iter_moves() const { assert(iter_moves_); return *iter_moves_; } 786 constexpr int iter_swaps() const { assert(iter_swaps_); return *iter_swaps_; } 787 788 constexpr value_type& operator*() const { return *ptr_; } 789 790 constexpr Iterator operator+(difference_type n) const { 791 return Iterator(ptr_ + n, iter_moves_, iter_swaps_); 792 } 793 794 constexpr Iterator& operator++() { ++ptr_; return *this; } 795 constexpr Iterator operator++(int) { 796 Iterator prev = *this; 797 ++ptr_; 798 return prev; 799 } 800 801 constexpr Iterator& operator--() { --ptr_; return *this; } 802 constexpr Iterator operator--(int) { 803 Iterator prev = *this; 804 --ptr_; 805 return prev; 806 } 807 808 constexpr friend void iter_swap(Iterator a, Iterator) { 809 if (a.iter_swaps_) { 810 ++(*a.iter_swaps_); 811 } 812 } 813 814 constexpr friend value_type&& iter_move(Iterator iter) { 815 if (iter.iter_moves_) { 816 ++(*iter.iter_moves_); 817 } 818 return std::move(*iter); 819 } 820 821 constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) { return lhs.ptr_ == rhs.ptr_; } 822 }; 823 824 } // namespace adl 825 826 // Proxy 827 // ====================================================================== 828 // Proxy that can wrap a value or a reference. It simulates C++23's tuple 829 // but simplified to just hold one argument. 830 // Note that unlike tuple, this class deliberately doesn't have special handling 831 // of swap to cause a compilation error if it's used in an algorithm that relies 832 // on plain swap instead of ranges::iter_swap. 833 // This class is useful for testing that if algorithms support proxy iterator 834 // properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of 835 // plain swap and std::move 836 template <class T> 837 struct Proxy; 838 839 template <class T> 840 inline constexpr bool IsProxy = false; 841 842 template <class T> 843 inline constexpr bool IsProxy<Proxy<T>> = true; 844 845 template <class T> 846 struct Proxy { 847 T data; 848 849 constexpr T& getData() & { return data; } 850 851 constexpr const T& getData() const& { return data; } 852 853 constexpr T&& getData() && { return static_cast<T&&>(data); } 854 855 constexpr const T&& getData() const&& { return static_cast<const T&&>(data); } 856 857 template <class U> 858 requires std::constructible_from<T, U&&> 859 constexpr Proxy(U&& u) : data{std::forward<U>(u)} {} 860 861 // This constructor covers conversion from cvref of Proxy<U>, including non-const/const versions of copy/move constructor 862 template <class Other> 863 requires(IsProxy<std::decay_t<Other>> && std::constructible_from<T, decltype(std::declval<Other>().getData())>) 864 constexpr Proxy(Other&& other) : data{std::forward<Other>(other).getData()} {} 865 866 template <class Other> 867 requires(IsProxy<std::decay_t<Other>> && std::assignable_from<T&, decltype(std::declval<Other>().getData())>) 868 constexpr Proxy& operator=(Other&& other) { 869 data = std::forward<Other>(other).getData(); 870 return *this; 871 } 872 873 // const assignment required to make ProxyIterator model std::indirectly_writable 874 template <class Other> 875 requires(IsProxy<std::decay_t<Other>> && std::assignable_from<const T&, decltype(std::declval<Other>().getData())>) 876 constexpr const Proxy& operator=(Other&& other) const { 877 data = std::forward<Other>(other).getData(); 878 return *this; 879 } 880 881 // If `T` is a reference type, the implicitly-generated assignment operator will be deleted (and would take precedence 882 // over the templated `operator=` above because it's a better match). 883 constexpr Proxy& operator=(const Proxy& rhs) { 884 data = rhs.data; 885 return *this; 886 } 887 888 // no specialised swap function that takes const Proxy& and no specialised const member swap 889 // Calling swap(Proxy<T>{}, Proxy<T>{}) would fail (pass prvalues) 890 891 // Compare operators are defined for the convenience of the tests 892 friend constexpr bool operator==(const Proxy&, const Proxy&) 893 requires (std::equality_comparable<T> && !std::is_reference_v<T>) 894 = default; 895 896 // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default equality comparison operator is deleted 897 // when `T` is a reference type. 898 template <class U> 899 friend constexpr bool operator==(const Proxy& lhs, const Proxy<U>& rhs) 900 requires std::equality_comparable_with<std::decay_t<T>, std::decay_t<U>> { 901 return lhs.data == rhs.data; 902 } 903 904 friend constexpr auto operator<=>(const Proxy&, const Proxy&) 905 requires (std::three_way_comparable<T> && !std::is_reference_v<T>) 906 = default; 907 908 // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default 3-way comparison operator is deleted when 909 // `T` is a reference type. 910 template <class U> 911 friend constexpr auto operator<=>(const Proxy& lhs, const Proxy<U>& rhs) 912 requires std::three_way_comparable_with<std::decay_t<T>, std::decay_t<U>> { 913 return lhs.data <=> rhs.data; 914 } 915 }; 916 917 // This is to make ProxyIterator model `std::indirectly_readable` 918 template <class T, class U, template <class> class TQual, template <class> class UQual> 919 requires requires { typename std::common_reference_t<TQual<T>, UQual<U>>; } 920 struct std::basic_common_reference<Proxy<T>, Proxy<U>, TQual, UQual> { 921 using type = Proxy<std::common_reference_t<TQual<T>, UQual<U>>>; 922 }; 923 924 template <class T, class U> 925 requires requires { typename std::common_type_t<T, U>; } 926 struct std::common_type<Proxy<T>, Proxy<U>> { 927 using type = Proxy<std::common_type_t<T, U>>; 928 }; 929 930 // ProxyIterator 931 // ====================================================================== 932 // It wraps `Base` iterator and when dereferenced it returns a Proxy<ref> 933 // It simulates C++23's zip_view::iterator but simplified to just wrap 934 // one base iterator. 935 // Note it forwards value_type, iter_move, iter_swap. e.g if the base 936 // iterator is int*, 937 // operator* -> Proxy<int&> 938 // iter_value_t -> Proxy<int> 939 // iter_move -> Proxy<int&&> 940 template <class Base> 941 struct ProxyIteratorBase {}; 942 943 template <class Base> 944 requires std::derived_from< 945 typename std::iterator_traits<Base>::iterator_category, 946 std::input_iterator_tag> 947 struct ProxyIteratorBase<Base> { 948 using iterator_category = std::input_iterator_tag; 949 }; 950 951 template <std::input_iterator Base> 952 consteval auto get_iterator_concept() { 953 if constexpr (std::random_access_iterator<Base>) { 954 return std::random_access_iterator_tag{}; 955 } else if constexpr (std::bidirectional_iterator<Base>) { 956 return std::bidirectional_iterator_tag{}; 957 } else if constexpr (std::forward_iterator<Base>) { 958 return std::forward_iterator_tag{}; 959 } else { 960 return std::input_iterator_tag{}; 961 } 962 } 963 964 template <std::input_iterator Base> 965 struct ProxyIterator : ProxyIteratorBase<Base> { 966 Base base_; 967 968 using iterator_concept = decltype(get_iterator_concept<Base>()); 969 using value_type = Proxy<std::iter_value_t<Base>>; 970 using difference_type = std::iter_difference_t<Base>; 971 972 ProxyIterator() 973 requires std::default_initializable<Base> 974 = default; 975 976 constexpr ProxyIterator(Base base) : base_{std::move(base)} {} 977 978 template <class T> 979 requires std::constructible_from<Base, T&&> 980 constexpr ProxyIterator(T&& t) : base_{std::forward<T>(t)} {} 981 982 friend constexpr decltype(auto) base(const ProxyIterator& p) { return base(p.base_); } 983 984 // Specialization of iter_move 985 // If operator* returns Proxy<Foo&>, iter_move will return Proxy<Foo&&> 986 // Note std::move(*it) returns Proxy<Foo&>&&, which is not what we want as 987 // it will likely result in a copy rather than a move 988 friend constexpr Proxy<std::iter_rvalue_reference_t<Base>> iter_move(const ProxyIterator& p) noexcept { 989 return {std::ranges::iter_move(p.base_)}; 990 } 991 992 // Specialization of iter_swap 993 // Note std::swap(*x, *y) would fail to compile as operator* returns prvalues 994 // and std::swap takes non-const lvalue references 995 friend constexpr void iter_swap(const ProxyIterator& x, const ProxyIterator& y) noexcept { 996 std::ranges::iter_swap(x.base_, y.base_); 997 } 998 999 // to satisfy input_iterator 1000 constexpr Proxy<std::iter_reference_t<Base>> operator*() const { return {*base_}; } 1001 1002 constexpr ProxyIterator& operator++() { 1003 ++base_; 1004 return *this; 1005 } 1006 1007 constexpr void operator++(int) { ++*this; } 1008 1009 friend constexpr bool operator==(const ProxyIterator& x, const ProxyIterator& y) 1010 requires std::equality_comparable<Base> { 1011 return x.base_ == y.base_; 1012 } 1013 1014 // to satisfy forward_iterator 1015 constexpr ProxyIterator operator++(int) 1016 requires std::forward_iterator<Base> { 1017 auto tmp = *this; 1018 ++*this; 1019 return tmp; 1020 } 1021 1022 // to satisfy bidirectional_iterator 1023 constexpr ProxyIterator& operator--() 1024 requires std::bidirectional_iterator<Base> { 1025 --base_; 1026 return *this; 1027 } 1028 1029 constexpr ProxyIterator operator--(int) 1030 requires std::bidirectional_iterator<Base> { 1031 auto tmp = *this; 1032 --*this; 1033 return tmp; 1034 } 1035 1036 // to satisfy random_access_iterator 1037 constexpr ProxyIterator& operator+=(difference_type n) 1038 requires std::random_access_iterator<Base> { 1039 base_ += n; 1040 return *this; 1041 } 1042 1043 constexpr ProxyIterator& operator-=(difference_type n) 1044 requires std::random_access_iterator<Base> { 1045 base_ -= n; 1046 return *this; 1047 } 1048 1049 constexpr Proxy<std::iter_reference_t<Base>> operator[](difference_type n) const 1050 requires std::random_access_iterator<Base> { 1051 return {base_[n]}; 1052 } 1053 1054 friend constexpr bool operator<(const ProxyIterator& x, const ProxyIterator& y) 1055 requires std::random_access_iterator<Base> { 1056 return x.base_ < y.base_; 1057 } 1058 1059 friend constexpr bool operator>(const ProxyIterator& x, const ProxyIterator& y) 1060 requires std::random_access_iterator<Base> { 1061 return x.base_ > y.base_; 1062 } 1063 1064 friend constexpr bool operator<=(const ProxyIterator& x, const ProxyIterator& y) 1065 requires std::random_access_iterator<Base> { 1066 return x.base_ <= y.base_; 1067 } 1068 1069 friend constexpr bool operator>=(const ProxyIterator& x, const ProxyIterator& y) 1070 requires std::random_access_iterator<Base> { 1071 return x.base_ >= y.base_; 1072 } 1073 1074 friend constexpr auto operator<=>(const ProxyIterator& x, const ProxyIterator& y) 1075 requires(std::random_access_iterator<Base> && std::three_way_comparable<Base>) { 1076 return x.base_ <=> y.base_; 1077 } 1078 1079 friend constexpr ProxyIterator operator+(const ProxyIterator& x, difference_type n) 1080 requires std::random_access_iterator<Base> { 1081 return ProxyIterator{x.base_ + n}; 1082 } 1083 1084 friend constexpr ProxyIterator operator+(difference_type n, const ProxyIterator& x) 1085 requires std::random_access_iterator<Base> { 1086 return ProxyIterator{n + x.base_}; 1087 } 1088 1089 friend constexpr ProxyIterator operator-(const ProxyIterator& x, difference_type n) 1090 requires std::random_access_iterator<Base> { 1091 return ProxyIterator{x.base_ - n}; 1092 } 1093 1094 friend constexpr difference_type operator-(const ProxyIterator& x, const ProxyIterator& y) 1095 requires std::random_access_iterator<Base> { 1096 return x.base_ - y.base_; 1097 } 1098 }; 1099 1100 static_assert(std::indirectly_readable<ProxyIterator<int*>>); 1101 static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int>>); 1102 static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int&>>); 1103 1104 template <class BaseSent> 1105 struct ProxySentinel { 1106 BaseSent base_; 1107 1108 ProxySentinel() = default; 1109 constexpr ProxySentinel(BaseSent base) : base_{std::move(base)} {} 1110 1111 template <class Base> 1112 requires std::equality_comparable_with<Base, BaseSent> 1113 friend constexpr bool operator==(const ProxyIterator<Base>& p, const ProxySentinel& sent) { 1114 return p.base_ == sent.base_; 1115 } 1116 }; 1117 1118 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 1119 template <std::ranges::input_range Base> 1120 requires std::ranges::view<Base> 1121 struct ProxyRange { 1122 Base base_; 1123 1124 constexpr auto begin() { return ProxyIterator{std::ranges::begin(base_)}; } 1125 1126 constexpr auto end() { return ProxySentinel{std::ranges::end(base_)}; } 1127 1128 constexpr auto begin() const 1129 requires std::ranges::input_range<const Base> { 1130 return ProxyIterator{std::ranges::begin(base_)}; 1131 } 1132 1133 constexpr auto end() const 1134 requires std::ranges::input_range<const Base> { 1135 return ProxySentinel{std::ranges::end(base_)}; 1136 } 1137 }; 1138 1139 template <std::ranges::input_range R> 1140 requires std::ranges::viewable_range<R&&> 1141 ProxyRange(R&&) -> ProxyRange<std::views::all_t<R&&>>; 1142 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) 1143 1144 #endif // TEST_STD_VER > 17 1145 1146 #endif // SUPPORT_TEST_ITERATORS_H 1147