1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2022 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/safe_iterator.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_H 30 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_H 1 31 32 #include <debug/assertions.h> 33 #include <debug/macros.h> 34 #include <debug/functions.h> 35 #include <debug/safe_base.h> 36 #include <bits/stl_pair.h> 37 #include <ext/type_traits.h> 38 #if __cplusplus > 201703L 39 # include <compare> 40 #endif 41 42 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, _BadMsgId, _DiffMsgId) \ 43 _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular() \ 44 || (_Lhs.base() == _Iterator() \ 45 && _Rhs.base() == _Iterator()), \ 46 _M_message(_BadMsgId) \ 47 ._M_iterator(_Lhs, #_Lhs) \ 48 ._M_iterator(_Rhs, #_Rhs)); \ 49 _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \ 50 _M_message(_DiffMsgId) \ 51 ._M_iterator(_Lhs, #_Lhs) \ 52 ._M_iterator(_Rhs, #_Rhs)) 53 54 #define _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(_Lhs, _Rhs) \ 55 _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_compare_bad, \ 56 __msg_compare_different) 57 58 #define _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(_Lhs, _Rhs) \ 59 _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_order_bad, \ 60 __msg_order_different) 61 62 #define _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(_Lhs, _Rhs) \ 63 _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_distance_bad, \ 64 __msg_distance_different) 65 66 namespace __gnu_debug 67 { 68 /** Helper struct to deal with sequence offering a before_begin 69 * iterator. 70 **/ 71 template<typename _Sequence> 72 struct _BeforeBeginHelper 73 { 74 template<typename _Iterator, typename _Category> 75 static bool _S_Is_BeforeBeginHelper76 _S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&) 77 { return false; } 78 79 template<typename _Iterator, typename _Category> 80 static bool _S_Is_Beginnest_BeforeBeginHelper81 _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it) 82 { return __it.base() == __it._M_get_sequence()->_M_base().begin(); } 83 }; 84 85 /** Sequence traits giving the size of a container if possible. */ 86 template<typename _Sequence> 87 struct _Sequence_traits 88 { 89 typedef _Distance_traits<typename _Sequence::iterator> _DistTraits; 90 91 static typename _DistTraits::__type _S_size_Sequence_traits92 _S_size(const _Sequence& __seq) 93 { return std::make_pair(__seq.size(), __dp_exact); } 94 }; 95 96 /** \brief Safe iterator wrapper. 97 * 98 * The class template %_Safe_iterator is a wrapper around an 99 * iterator that tracks the iterator's movement among sequences and 100 * checks that operations performed on the "safe" iterator are 101 * legal. In additional to the basic iterator operations (which are 102 * validated, and then passed to the underlying iterator), 103 * %_Safe_iterator has member functions for iterator invalidation, 104 * attaching/detaching the iterator from sequences, and querying 105 * the iterator's state. 106 * 107 * Note that _Iterator must be the first base class so that it gets 108 * initialized before the iterator is being attached to the container's list 109 * of iterators and it is being detached before _Iterator get 110 * destroyed. Otherwise it would result in a data race. 111 */ 112 template<typename _Iterator, typename _Sequence, typename _Category 113 = typename std::iterator_traits<_Iterator>::iterator_category> 114 class _Safe_iterator 115 : private _Iterator, 116 public _Safe_iterator_base 117 { 118 typedef _Iterator _Iter_base; 119 typedef _Safe_iterator_base _Safe_base; 120 121 typedef std::iterator_traits<_Iterator> _Traits; 122 123 protected: 124 typedef std::__are_same<typename _Sequence::_Base::const_iterator, 125 _Iterator> _IsConstant; 126 127 typedef typename __gnu_cxx::__conditional_type< 128 _IsConstant::__value, 129 typename _Sequence::_Base::iterator, 130 typename _Sequence::_Base::const_iterator>::__type _OtherIterator; 131 132 struct _Attach_single 133 { }; 134 _Safe_iterator(_Iterator __i,_Safe_sequence_base * __seq,_Attach_single)135 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 136 _GLIBCXX_NOEXCEPT 137 : _Iter_base(__i) 138 { _M_attach_single(__seq); } 139 140 public: 141 typedef _Iterator iterator_type; 142 typedef typename _Traits::iterator_category iterator_category; 143 typedef typename _Traits::value_type value_type; 144 typedef typename _Traits::difference_type difference_type; 145 typedef typename _Traits::reference reference; 146 typedef typename _Traits::pointer pointer; 147 148 #if __cplusplus > 201703L && __cpp_lib_concepts 149 using iterator_concept = std::__detail::__iter_concept<_Iterator>; 150 #endif 151 152 /// @post the iterator is singular and unattached _Safe_iterator()153 _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { } 154 155 /** 156 * @brief Safe iterator construction from an unsafe iterator and 157 * its sequence. 158 * 159 * @pre @p seq is not NULL 160 * @post this is not singular 161 */ _Safe_iterator(_Iterator __i,const _Safe_sequence_base * __seq)162 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 163 _GLIBCXX_NOEXCEPT 164 : _Iter_base(__i), _Safe_base(__seq, _S_constant()) 165 { 166 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 167 _M_message(__msg_init_singular) 168 ._M_iterator(*this, "this")); 169 } 170 171 /** 172 * @brief Copy construction. 173 */ _Safe_iterator(const _Safe_iterator & __x)174 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 175 : _Iter_base(__x.base()), _Safe_base() 176 { 177 // _GLIBCXX_RESOLVE_LIB_DEFECTS 178 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 179 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 180 || __x.base() == _Iterator(), 181 _M_message(__msg_init_copy_singular) 182 ._M_iterator(*this, "this") 183 ._M_iterator(__x, "other")); 184 _M_attach(__x._M_sequence); 185 } 186 187 #if __cplusplus >= 201103L 188 /** 189 * @brief Move construction. 190 * @post __x is singular and unattached 191 */ _Safe_iterator(_Safe_iterator && __x)192 _Safe_iterator(_Safe_iterator&& __x) noexcept 193 : _Iter_base() 194 { 195 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 196 || __x.base() == _Iterator(), 197 _M_message(__msg_init_copy_singular) 198 ._M_iterator(*this, "this") 199 ._M_iterator(__x, "other")); 200 _Safe_sequence_base* __seq = __x._M_sequence; 201 __x._M_detach(); 202 std::swap(base(), __x.base()); 203 _M_attach(__seq); 204 } 205 #endif 206 207 /** 208 * @brief Converting constructor from a mutable iterator to a 209 * constant iterator. 210 */ 211 template<typename _MutableIterator> _Safe_iterator(const _Safe_iterator<_MutableIterator,_Sequence,typename __gnu_cxx::__enable_if<_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,_Category>::__type> & __x)212 _Safe_iterator( 213 const _Safe_iterator<_MutableIterator, _Sequence, 214 typename __gnu_cxx::__enable_if<_IsConstant::__value && 215 std::__are_same<_MutableIterator, _OtherIterator>::__value, 216 _Category>::__type>& __x) 217 _GLIBCXX_NOEXCEPT 218 : _Iter_base(__x.base()) 219 { 220 // _GLIBCXX_RESOLVE_LIB_DEFECTS 221 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 222 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 223 || __x.base() == _MutableIterator(), 224 _M_message(__msg_init_const_singular) 225 ._M_iterator(*this, "this") 226 ._M_iterator(__x, "other")); 227 _M_attach(__x._M_sequence); 228 } 229 230 /** 231 * @brief Copy assignment. 232 */ 233 _Safe_iterator& 234 operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 235 { 236 // _GLIBCXX_RESOLVE_LIB_DEFECTS 237 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 238 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 239 || __x.base() == _Iterator(), 240 _M_message(__msg_copy_singular) 241 ._M_iterator(*this, "this") 242 ._M_iterator(__x, "other")); 243 244 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 245 { 246 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 247 base() = __x.base(); 248 _M_version = __x._M_sequence->_M_version; 249 } 250 else 251 { 252 _M_detach(); 253 base() = __x.base(); 254 _M_attach(__x._M_sequence); 255 } 256 257 return *this; 258 } 259 260 #if __cplusplus >= 201103L 261 /** 262 * @brief Move assignment. 263 * @post __x is singular and unattached 264 */ 265 _Safe_iterator& 266 operator=(_Safe_iterator&& __x) noexcept 267 { 268 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 269 || __x.base() == _Iterator(), 270 _M_message(__msg_copy_singular) 271 ._M_iterator(*this, "this") 272 ._M_iterator(__x, "other")); 273 274 if (std::__addressof(__x) == this) 275 return *this; 276 277 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 278 { 279 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 280 base() = __x.base(); 281 _M_version = __x._M_sequence->_M_version; 282 } 283 else 284 { 285 _M_detach(); 286 base() = __x.base(); 287 _M_attach(__x._M_sequence); 288 } 289 290 __x._M_detach(); 291 __x.base() = _Iterator(); 292 return *this; 293 } 294 #endif 295 296 /** 297 * @brief Iterator dereference. 298 * @pre iterator is dereferenceable 299 */ 300 _GLIBCXX_NODISCARD 301 reference 302 operator*() const _GLIBCXX_NOEXCEPT 303 { 304 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 305 _M_message(__msg_bad_deref) 306 ._M_iterator(*this, "this")); 307 return *base(); 308 } 309 310 /** 311 * @brief Iterator dereference. 312 * @pre iterator is dereferenceable 313 */ 314 _GLIBCXX_NODISCARD 315 pointer 316 operator->() const _GLIBCXX_NOEXCEPT 317 { 318 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 319 _M_message(__msg_bad_deref) 320 ._M_iterator(*this, "this")); 321 return base().operator->(); 322 } 323 324 // ------ Input iterator requirements ------ 325 /** 326 * @brief Iterator preincrement 327 * @pre iterator is incrementable 328 */ 329 _Safe_iterator& 330 operator++() _GLIBCXX_NOEXCEPT 331 { 332 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 333 _M_message(__msg_bad_inc) 334 ._M_iterator(*this, "this")); 335 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 336 ++base(); 337 return *this; 338 } 339 340 /** 341 * @brief Iterator postincrement 342 * @pre iterator is incrementable 343 */ 344 _Safe_iterator 345 operator++(int) _GLIBCXX_NOEXCEPT 346 { 347 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 348 _M_message(__msg_bad_inc) 349 ._M_iterator(*this, "this")); 350 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 351 return _Safe_iterator(base()++, this->_M_sequence, _Attach_single()); 352 } 353 354 // ------ Utilities ------ 355 356 /// Determine if this is a constant iterator. 357 static _GLIBCXX_CONSTEXPR bool _S_constant()358 _S_constant() 359 { return _IsConstant::__value; } 360 361 /** 362 * @brief Return the underlying iterator 363 */ 364 _Iterator& base()365 base() _GLIBCXX_NOEXCEPT { return *this; } 366 367 const _Iterator& base()368 base() const _GLIBCXX_NOEXCEPT { return *this; } 369 370 /** 371 * @brief Conversion to underlying non-debug iterator to allow 372 * better interaction with non-debug containers. 373 */ _Iterator()374 operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; } 375 376 /** Attach iterator to the given sequence. */ 377 void _M_attach(_Safe_sequence_base * __seq)378 _M_attach(_Safe_sequence_base* __seq) 379 { _Safe_base::_M_attach(__seq, _S_constant()); } 380 381 /** Likewise, but not thread-safe. */ 382 void _M_attach_single(_Safe_sequence_base * __seq)383 _M_attach_single(_Safe_sequence_base* __seq) 384 { _Safe_base::_M_attach_single(__seq, _S_constant()); } 385 386 /// Is the iterator dereferenceable? 387 bool _M_dereferenceable()388 _M_dereferenceable() const 389 { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); } 390 391 /// Is the iterator before a dereferenceable one? 392 bool _M_before_dereferenceable()393 _M_before_dereferenceable() const 394 { 395 if (this->_M_incrementable()) 396 { 397 _Iterator __base = base(); 398 return ++__base != _M_get_sequence()->_M_base().end(); 399 } 400 return false; 401 } 402 403 /// Is the iterator incrementable? 404 bool _M_incrementable()405 _M_incrementable() const 406 { return !this->_M_singular() && !_M_is_end(); } 407 408 // Can we advance the iterator @p __n steps (@p __n may be negative) 409 bool 410 _M_can_advance(difference_type __n, bool __strict = false) const; 411 412 // Can we advance the iterator using @p __dist in @p __way direction. 413 template<typename _Diff> 414 bool 415 _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist, 416 int __way) const; 417 418 // Is the iterator range [*this, __rhs) valid? 419 bool 420 _M_valid_range(const _Safe_iterator& __rhs, 421 std::pair<difference_type, _Distance_precision>& __dist, 422 bool __check_dereferenceable = true) const; 423 424 // The sequence this iterator references. 425 typename __gnu_cxx::__conditional_type< 426 _IsConstant::__value, const _Sequence*, _Sequence*>::__type _M_get_sequence()427 _M_get_sequence() const 428 { return static_cast<_Sequence*>(_M_sequence); } 429 430 // Get distance to __rhs. 431 typename _Distance_traits<_Iterator>::__type 432 _M_get_distance_to(const _Safe_iterator& __rhs) const; 433 434 // Get distance from sequence begin up to *this. 435 typename _Distance_traits<_Iterator>::__type 436 _M_get_distance_from_begin() const; 437 438 // Get distance from *this to sequence end. 439 typename _Distance_traits<_Iterator>::__type 440 _M_get_distance_to_end() const; 441 442 /// Is this iterator equal to the sequence's begin() iterator? 443 bool _M_is_begin()444 _M_is_begin() const 445 { return base() == _M_get_sequence()->_M_base().begin(); } 446 447 /// Is this iterator equal to the sequence's end() iterator? 448 bool _M_is_end()449 _M_is_end() const 450 { return base() == _M_get_sequence()->_M_base().end(); } 451 452 /// Is this iterator equal to the sequence's before_begin() iterator if 453 /// any? 454 bool _M_is_before_begin()455 _M_is_before_begin() const 456 { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); } 457 458 /// Is this iterator equal to the sequence's before_begin() iterator if 459 /// any or begin() otherwise? 460 bool _M_is_beginnest()461 _M_is_beginnest() const 462 { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); } 463 464 // ------ Operators ------ 465 466 typedef _Safe_iterator<_Iterator, _Sequence, iterator_category> _Self; 467 468 _GLIBCXX_NODISCARD 469 friend bool 470 operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 471 { 472 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 473 return __lhs.base() == __rhs.base(); 474 } 475 476 template<typename _IteR> 477 _GLIBCXX_NODISCARD 478 friend bool 479 operator==(const _Self& __lhs, 480 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs) 481 _GLIBCXX_NOEXCEPT 482 { 483 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 484 return __lhs.base() == __rhs.base(); 485 } 486 487 #if ! __cpp_lib_three_way_comparison 488 _GLIBCXX_NODISCARD 489 friend bool 490 operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 491 { 492 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 493 return __lhs.base() != __rhs.base(); 494 } 495 496 template<typename _IteR> 497 _GLIBCXX_NODISCARD 498 friend bool 499 operator!=(const _Self& __lhs, 500 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs) 501 _GLIBCXX_NOEXCEPT 502 { 503 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs); 504 return __lhs.base() != __rhs.base(); 505 } 506 #endif // three-way comparison 507 }; 508 509 template<typename _Iterator, typename _Sequence> 510 class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag> 511 : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag> 512 { 513 typedef _Safe_iterator<_Iterator, _Sequence, 514 std::forward_iterator_tag> _Safe_base; 515 516 protected: 517 typedef typename _Safe_base::_OtherIterator _OtherIterator; 518 typedef typename _Safe_base::_Attach_single _Attach_single; 519 _Safe_iterator(_Iterator __i,_Safe_sequence_base * __seq,_Attach_single)520 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 521 _GLIBCXX_NOEXCEPT 522 : _Safe_base(__i, __seq, _Attach_single()) 523 { } 524 525 public: 526 /// @post the iterator is singular and unattached _Safe_iterator()527 _Safe_iterator() _GLIBCXX_NOEXCEPT { } 528 529 /** 530 * @brief Safe iterator construction from an unsafe iterator and 531 * its sequence. 532 * 533 * @pre @p seq is not NULL 534 * @post this is not singular 535 */ _Safe_iterator(_Iterator __i,const _Safe_sequence_base * __seq)536 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 537 _GLIBCXX_NOEXCEPT 538 : _Safe_base(__i, __seq) 539 { } 540 541 /** 542 * @brief Copy construction. 543 */ _Safe_iterator(const _Safe_iterator & __x)544 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 545 : _Safe_base(__x) 546 { } 547 548 #if __cplusplus >= 201103L 549 /** @brief Move construction. */ 550 _Safe_iterator(_Safe_iterator&&) = default; 551 #endif 552 553 /** 554 * @brief Converting constructor from a mutable iterator to a 555 * constant iterator. 556 */ 557 template<typename _MutableIterator> _Safe_iterator(const _Safe_iterator<_MutableIterator,_Sequence,typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,std::bidirectional_iterator_tag>::__type> & __x)558 _Safe_iterator( 559 const _Safe_iterator<_MutableIterator, _Sequence, 560 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && 561 std::__are_same<_MutableIterator, _OtherIterator>::__value, 562 std::bidirectional_iterator_tag>::__type>& __x) 563 _GLIBCXX_NOEXCEPT 564 : _Safe_base(__x) 565 { } 566 567 #if __cplusplus >= 201103L 568 /** @brief Copy assignment. */ 569 _Safe_iterator& 570 operator=(const _Safe_iterator&) = default; 571 572 /** @brief Move assignment. */ 573 _Safe_iterator& 574 operator=(_Safe_iterator&&) = default; 575 #else 576 /** @brief Copy assignment. */ 577 _Safe_iterator& 578 operator=(const _Safe_iterator& __x) 579 { 580 _Safe_base::operator=(__x); 581 return *this; 582 } 583 #endif 584 585 // ------ Input iterator requirements ------ 586 /** 587 * @brief Iterator preincrement 588 * @pre iterator is incrementable 589 */ 590 _Safe_iterator& 591 operator++() _GLIBCXX_NOEXCEPT 592 { 593 _Safe_base::operator++(); 594 return *this; 595 } 596 597 /** 598 * @brief Iterator postincrement 599 * @pre iterator is incrementable 600 */ 601 _Safe_iterator 602 operator++(int) _GLIBCXX_NOEXCEPT 603 { 604 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 605 _M_message(__msg_bad_inc) 606 ._M_iterator(*this, "this")); 607 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 608 return _Safe_iterator(this->base()++, this->_M_sequence, 609 _Attach_single()); 610 } 611 612 // ------ Bidirectional iterator requirements ------ 613 /** 614 * @brief Iterator predecrement 615 * @pre iterator is decrementable 616 */ 617 _Safe_iterator& 618 operator--() _GLIBCXX_NOEXCEPT 619 { 620 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 621 _M_message(__msg_bad_dec) 622 ._M_iterator(*this, "this")); 623 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 624 --this->base(); 625 return *this; 626 } 627 628 /** 629 * @brief Iterator postdecrement 630 * @pre iterator is decrementable 631 */ 632 _Safe_iterator 633 operator--(int) _GLIBCXX_NOEXCEPT 634 { 635 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 636 _M_message(__msg_bad_dec) 637 ._M_iterator(*this, "this")); 638 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 639 return _Safe_iterator(this->base()--, this->_M_sequence, 640 _Attach_single()); 641 } 642 643 // ------ Utilities ------ 644 645 // Is the iterator decrementable? 646 bool _M_decrementable()647 _M_decrementable() const 648 { return !this->_M_singular() && !this->_M_is_begin(); } 649 }; 650 651 template<typename _Iterator, typename _Sequence> 652 class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag> 653 : public _Safe_iterator<_Iterator, _Sequence, 654 std::bidirectional_iterator_tag> 655 { 656 typedef _Safe_iterator<_Iterator, _Sequence, 657 std::bidirectional_iterator_tag> _Safe_base; 658 typedef typename _Safe_base::_OtherIterator _OtherIterator; 659 660 typedef typename _Safe_base::_Self _Self; 661 typedef _Safe_iterator<_OtherIterator, _Sequence, 662 std::random_access_iterator_tag> _OtherSelf; 663 664 typedef typename _Safe_base::_Attach_single _Attach_single; 665 _Safe_iterator(_Iterator __i,_Safe_sequence_base * __seq,_Attach_single)666 _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single) 667 _GLIBCXX_NOEXCEPT 668 : _Safe_base(__i, __seq, _Attach_single()) 669 { } 670 671 public: 672 typedef typename _Safe_base::difference_type difference_type; 673 typedef typename _Safe_base::reference reference; 674 675 /// @post the iterator is singular and unattached _Safe_iterator()676 _Safe_iterator() _GLIBCXX_NOEXCEPT { } 677 678 /** 679 * @brief Safe iterator construction from an unsafe iterator and 680 * its sequence. 681 * 682 * @pre @p seq is not NULL 683 * @post this is not singular 684 */ _Safe_iterator(_Iterator __i,const _Safe_sequence_base * __seq)685 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq) 686 _GLIBCXX_NOEXCEPT 687 : _Safe_base(__i, __seq) 688 { } 689 690 /** 691 * @brief Copy construction. 692 */ _Safe_iterator(const _Safe_iterator & __x)693 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT 694 : _Safe_base(__x) 695 { } 696 697 #if __cplusplus >= 201103L 698 /** @brief Move construction. */ 699 _Safe_iterator(_Safe_iterator&&) = default; 700 #endif 701 702 /** 703 * @brief Converting constructor from a mutable iterator to a 704 * constant iterator. 705 */ 706 template<typename _MutableIterator> _Safe_iterator(const _Safe_iterator<_MutableIterator,_Sequence,typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && std::__are_same<_MutableIterator,_OtherIterator>::__value,std::random_access_iterator_tag>::__type> & __x)707 _Safe_iterator( 708 const _Safe_iterator<_MutableIterator, _Sequence, 709 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value && 710 std::__are_same<_MutableIterator, _OtherIterator>::__value, 711 std::random_access_iterator_tag>::__type>& __x) 712 _GLIBCXX_NOEXCEPT 713 : _Safe_base(__x) 714 { } 715 716 #if __cplusplus >= 201103L 717 /** @brief Copy assignment. */ 718 _Safe_iterator& 719 operator=(const _Safe_iterator&) = default; 720 721 /** @brief Move assignment. */ 722 _Safe_iterator& 723 operator=(_Safe_iterator&&) = default; 724 #else 725 /** @brief Copy assignment. */ 726 _Safe_iterator& 727 operator=(const _Safe_iterator& __x) 728 { 729 _Safe_base::operator=(__x); 730 return *this; 731 } 732 #endif 733 734 // Is the iterator range [*this, __rhs) valid? 735 bool 736 _M_valid_range(const _Safe_iterator& __rhs, 737 std::pair<difference_type, 738 _Distance_precision>& __dist) const; 739 740 // ------ Input iterator requirements ------ 741 /** 742 * @brief Iterator preincrement 743 * @pre iterator is incrementable 744 */ 745 _Safe_iterator& 746 operator++() _GLIBCXX_NOEXCEPT 747 { 748 _Safe_base::operator++(); 749 return *this; 750 } 751 752 /** 753 * @brief Iterator postincrement 754 * @pre iterator is incrementable 755 */ 756 _Safe_iterator 757 operator++(int) _GLIBCXX_NOEXCEPT 758 { 759 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 760 _M_message(__msg_bad_inc) 761 ._M_iterator(*this, "this")); 762 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 763 return _Safe_iterator(this->base()++, this->_M_sequence, 764 _Attach_single()); 765 } 766 767 // ------ Bidirectional iterator requirements ------ 768 /** 769 * @brief Iterator predecrement 770 * @pre iterator is decrementable 771 */ 772 _Safe_iterator& 773 operator--() _GLIBCXX_NOEXCEPT 774 { 775 _Safe_base::operator--(); 776 return *this; 777 } 778 779 /** 780 * @brief Iterator postdecrement 781 * @pre iterator is decrementable 782 */ 783 _Safe_iterator 784 operator--(int) _GLIBCXX_NOEXCEPT 785 { 786 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(), 787 _M_message(__msg_bad_dec) 788 ._M_iterator(*this, "this")); 789 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 790 return _Safe_iterator(this->base()--, this->_M_sequence, 791 _Attach_single()); 792 } 793 794 // ------ Random access iterator requirements ------ 795 _GLIBCXX_NODISCARD 796 reference 797 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT 798 { 799 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n) 800 && this->_M_can_advance(__n + 1), 801 _M_message(__msg_iter_subscript_oob) 802 ._M_iterator(*this)._M_integer(__n)); 803 return this->base()[__n]; 804 } 805 806 _Safe_iterator& 807 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 808 { 809 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n), 810 _M_message(__msg_advance_oob) 811 ._M_iterator(*this)._M_integer(__n)); 812 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 813 this->base() += __n; 814 return *this; 815 } 816 817 _Safe_iterator& 818 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT 819 { 820 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n), 821 _M_message(__msg_retreat_oob) 822 ._M_iterator(*this)._M_integer(__n)); 823 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 824 this->base() -= __n; 825 return *this; 826 } 827 828 #if __cpp_lib_three_way_comparison 829 [[nodiscard]] 830 friend auto 831 operator<=>(const _Self& __lhs, const _Self& __rhs) noexcept 832 { 833 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 834 return __lhs.base() <=> __rhs.base(); 835 } 836 837 [[nodiscard]] 838 friend auto 839 operator<=>(const _Self& __lhs, const _OtherSelf& __rhs) noexcept 840 { 841 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 842 return __lhs.base() <=> __rhs.base(); 843 } 844 #else 845 _GLIBCXX_NODISCARD 846 friend bool 847 operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 848 { 849 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 850 return __lhs.base() < __rhs.base(); 851 } 852 853 _GLIBCXX_NODISCARD 854 friend bool 855 operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 856 { 857 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 858 return __lhs.base() < __rhs.base(); 859 } 860 861 _GLIBCXX_NODISCARD 862 friend bool 863 operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 864 { 865 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 866 return __lhs.base() <= __rhs.base(); 867 } 868 869 _GLIBCXX_NODISCARD 870 friend bool 871 operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 872 { 873 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 874 return __lhs.base() <= __rhs.base(); 875 } 876 877 _GLIBCXX_NODISCARD 878 friend bool 879 operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 880 { 881 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 882 return __lhs.base() > __rhs.base(); 883 } 884 885 _GLIBCXX_NODISCARD 886 friend bool 887 operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 888 { 889 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 890 return __lhs.base() > __rhs.base(); 891 } 892 893 _GLIBCXX_NODISCARD 894 friend bool 895 operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 896 { 897 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 898 return __lhs.base() >= __rhs.base(); 899 } 900 901 _GLIBCXX_NODISCARD 902 friend bool 903 operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 904 { 905 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs); 906 return __lhs.base() >= __rhs.base(); 907 } 908 #endif // three-way comparison 909 910 // _GLIBCXX_RESOLVE_LIB_DEFECTS 911 // According to the resolution of DR179 not only the various comparison 912 // operators but also operator- must accept mixed iterator/const_iterator 913 // parameters. 914 _GLIBCXX_NODISCARD 915 friend difference_type 916 operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT 917 { 918 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs); 919 return __lhs.base() - __rhs.base(); 920 } 921 922 _GLIBCXX_NODISCARD 923 friend difference_type 924 operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT 925 { 926 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs); 927 return __lhs.base() - __rhs.base(); 928 } 929 930 _GLIBCXX_NODISCARD 931 friend _Self 932 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT 933 { 934 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n), 935 _M_message(__msg_advance_oob) 936 ._M_iterator(__x)._M_integer(__n)); 937 return _Safe_iterator(__x.base() + __n, __x._M_sequence); 938 } 939 940 _GLIBCXX_NODISCARD 941 friend _Self 942 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT 943 { 944 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n), 945 _M_message(__msg_advance_oob) 946 ._M_iterator(__x)._M_integer(__n)); 947 return _Safe_iterator(__n + __x.base(), __x._M_sequence); 948 } 949 950 _GLIBCXX_NODISCARD 951 friend _Self 952 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT 953 { 954 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n), 955 _M_message(__msg_retreat_oob) 956 ._M_iterator(__x)._M_integer(__n)); 957 return _Safe_iterator(__x.base() - __n, __x._M_sequence); 958 } 959 }; 960 961 /** Safe iterators know how to check if they form a valid range. */ 962 template<typename _Iterator, typename _Sequence, typename _Category> 963 inline bool __valid_range(const _Safe_iterator<_Iterator,_Sequence,_Category> & __first,const _Safe_iterator<_Iterator,_Sequence,_Category> & __last,typename _Distance_traits<_Iterator>::__type & __dist)964 __valid_range(const _Safe_iterator<_Iterator, _Sequence, 965 _Category>& __first, 966 const _Safe_iterator<_Iterator, _Sequence, 967 _Category>& __last, 968 typename _Distance_traits<_Iterator>::__type& __dist) 969 { return __first._M_valid_range(__last, __dist); } 970 971 template<typename _Iterator, typename _Sequence, typename _Category> 972 inline bool __valid_range(const _Safe_iterator<_Iterator,_Sequence,_Category> & __first,const _Safe_iterator<_Iterator,_Sequence,_Category> & __last)973 __valid_range(const _Safe_iterator<_Iterator, _Sequence, 974 _Category>& __first, 975 const _Safe_iterator<_Iterator, _Sequence, 976 _Category>& __last) 977 { 978 typename _Distance_traits<_Iterator>::__type __dist; 979 return __first._M_valid_range(__last, __dist); 980 } 981 982 template<typename _Iterator, typename _Sequence, typename _Category, 983 typename _Size> 984 inline bool __can_advance(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,_Size __n)985 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 986 _Size __n) 987 { return __it._M_can_advance(__n); } 988 989 template<typename _Iterator, typename _Sequence, typename _Category, 990 typename _Diff> 991 inline bool __can_advance(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,const std::pair<_Diff,_Distance_precision> & __dist,int __way)992 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 993 const std::pair<_Diff, _Distance_precision>& __dist, 994 int __way) 995 { return __it._M_can_advance(__dist, __way); } 996 997 template<typename _Iterator, typename _Sequence> 998 _Iterator __base(const _Safe_iterator<_Iterator,_Sequence,std::random_access_iterator_tag> & __it)999 __base(const _Safe_iterator<_Iterator, _Sequence, 1000 std::random_access_iterator_tag>& __it) 1001 { return __it.base(); } 1002 1003 #if __cplusplus < 201103L 1004 template<typename _Iterator, typename _Sequence> 1005 struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> > 1006 { typedef _Iterator _Type; }; 1007 #endif 1008 1009 template<typename _Iterator, typename _Sequence> 1010 inline _Iterator 1011 __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it) 1012 { return __it.base(); } 1013 1014 } // namespace __gnu_debug 1015 1016 #if __cplusplus >= 201103L && __cplusplus <= 201703L 1017 namespace std _GLIBCXX_VISIBILITY(default) 1018 { 1019 _GLIBCXX_BEGIN_NAMESPACE_VERSION 1020 1021 template<typename _Iterator, typename _Container, typename _Sequence> 1022 constexpr auto 1023 __to_address(const __gnu_debug::_Safe_iterator< 1024 __gnu_cxx::__normal_iterator<_Iterator, _Container>, 1025 _Sequence>& __it) noexcept 1026 -> decltype(std::__to_address(__it.base().base())) 1027 { return std::__to_address(__it.base().base()); } 1028 1029 _GLIBCXX_END_NAMESPACE_VERSION 1030 } 1031 #endif 1032 1033 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS 1034 #undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS 1035 #undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS 1036 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS 1037 1038 #include <debug/safe_iterator.tcc> 1039 1040 #endif 1041