libstdc++-v3/include/debug/safe_iterator.h

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2003-2023 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._M_value_initialized()                 \
  45                             && _Rhs._M_value_initialized()),            \
  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
  76         _S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&)
  77         { return false; }
  78
  79       template<typename _Iterator, typename _Category>
  80         static bool
  81         _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
  92       _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     public:
 133       typedef _Iterator                                 iterator_type;
 134       typedef typename _Traits::iterator_category       iterator_category;
 135       typedef typename _Traits::value_type              value_type;
 136       typedef typename _Traits::difference_type         difference_type;
 137       typedef typename _Traits::reference               reference;
 138       typedef typename _Traits::pointer                 pointer;
 139
 140 #if __cplusplus > 201703L && __cpp_lib_concepts
 141       using iterator_concept = std::__detail::__iter_concept<_Iterator>;
 142 #endif
 143
 144       /// @post the iterator is singular and unattached
 145       _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
 146
 147       /**
 148        * @brief Safe iterator construction from an unsafe iterator and
 149        * its sequence.
 150        *
 151        * @pre @p seq is not NULL
 152        * @post this is not singular
 153        */
 154       _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
 155       _GLIBCXX_NOEXCEPT
 156       : _Iter_base(__i), _Safe_base(__seq, _S_constant())
 157       {
 158         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 159                               _M_message(__msg_init_singular)
 160                               ._M_iterator(*this, "this"));
 161       }
 162
 163       /**
 164        * @brief Copy construction.
 165        */
 166       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 167       : _Iter_base(__x.base()), _Safe_base()
 168       {
 169         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 170         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 171         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 172                               || __x._M_value_initialized(),
 173                               _M_message(__msg_init_copy_singular)
 174                               ._M_iterator(*this, "this")
 175                               ._M_iterator(__x, "other"));
 176         _M_attach(__x._M_sequence);
 177       }
 178
 179 #if __cplusplus >= 201103L
 180       /**
 181        * @brief Move construction.
 182        * @post __x is singular and unattached
 183        */
 184       _Safe_iterator(_Safe_iterator&& __x) noexcept
 185       : _Iter_base()
 186       {
 187         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 188                               || __x._M_value_initialized(),
 189                               _M_message(__msg_init_copy_singular)
 190                               ._M_iterator(*this, "this")
 191                               ._M_iterator(__x, "other"));
 192         _Safe_sequence_base* __seq = __x._M_sequence;
 193         __x._M_detach();
 194         std::swap(base(), __x.base());
 195         _M_attach(__seq);
 196       }
 197 #endif
 198
 199       /**
 200        *  @brief Converting constructor from a mutable iterator to a
 201        *  constant iterator.
 202       */
 203       template<typename _MutableIterator>
 204         _Safe_iterator(
 205           const _Safe_iterator<_MutableIterator, _Sequence,
 206             typename __gnu_cxx::__enable_if<_IsConstant::__value &&
 207               std::__are_same<_MutableIterator, _OtherIterator>::__value,
 208                                _Category>::__type>& __x)
 209         _GLIBCXX_NOEXCEPT
 210         : _Iter_base(__x.base())
 211         {
 212           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 213           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 214           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 215                                 || __x._M_value_initialized(),
 216                                 _M_message(__msg_init_const_singular)
 217                                 ._M_iterator(*this, "this")
 218                                 ._M_iterator(__x, "other"));
 219           _M_attach(__x._M_sequence);
 220         }
 221
 222       /**
 223        * @brief Copy assignment.
 224        */
 225       _Safe_iterator&
 226       operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 227       {
 228         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 229         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 230         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 231                               || __x._M_value_initialized(),
 232                               _M_message(__msg_copy_singular)
 233                               ._M_iterator(*this, "this")
 234                               ._M_iterator(__x, "other"));
 235
 236         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 237           {
 238             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 239             base() = __x.base();
 240             _M_version = __x._M_sequence->_M_version;
 241           }
 242         else
 243           {
 244             _M_detach();
 245             base() = __x.base();
 246             _M_attach(__x._M_sequence);
 247           }
 248
 249         return *this;
 250       }
 251
 252 #if __cplusplus >= 201103L
 253       /**
 254        * @brief Move assignment.
 255        * @post __x is singular and unattached
 256        */
 257       _Safe_iterator&
 258       operator=(_Safe_iterator&& __x) noexcept
 259       {
 260         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 261                               || __x._M_value_initialized(),
 262                               _M_message(__msg_copy_singular)
 263                               ._M_iterator(*this, "this")
 264                               ._M_iterator(__x, "other"));
 265
 266         if (std::__addressof(__x) == this)
 267           return *this;
 268
 269         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 270           {
 271             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 272             base() = __x.base();
 273             _M_version = __x._M_sequence->_M_version;
 274           }
 275         else
 276           {
 277             _M_detach();
 278             base() = __x.base();
 279             _M_attach(__x._M_sequence);
 280           }
 281
 282         __x._M_detach();
 283         __x.base() = _Iterator();
 284         return *this;
 285       }
 286 #endif
 287
 288       /**
 289        *  @brief Iterator dereference.
 290        *  @pre iterator is dereferenceable
 291        */
 292       _GLIBCXX_NODISCARD
 293       reference
 294       operator*() const _GLIBCXX_NOEXCEPT
 295       {
 296         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 297                               _M_message(__msg_bad_deref)
 298                               ._M_iterator(*this, "this"));
 299         return *base();
 300       }
 301
 302       /**
 303        *  @brief Iterator dereference.
 304        *  @pre iterator is dereferenceable
 305        */
 306       _GLIBCXX_NODISCARD
 307       pointer
 308       operator->() const _GLIBCXX_NOEXCEPT
 309       {
 310         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 311                               _M_message(__msg_bad_deref)
 312                               ._M_iterator(*this, "this"));
 313         return base().operator->();
 314       }
 315
 316       // ------ Input iterator requirements ------
 317       /**
 318        *  @brief Iterator preincrement
 319        *  @pre iterator is incrementable
 320        */
 321       _Safe_iterator&
 322       operator++() _GLIBCXX_NOEXCEPT
 323       {
 324         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 325                               _M_message(__msg_bad_inc)
 326                               ._M_iterator(*this, "this"));
 327         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 328         ++base();
 329         return *this;
 330       }
 331
 332       /**
 333        *  @brief Iterator postincrement
 334        *  @pre iterator is incrementable
 335        */
 336       _Safe_iterator
 337       operator++(int) _GLIBCXX_NOEXCEPT
 338       {
 339         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 340                               _M_message(__msg_bad_inc)
 341                               ._M_iterator(*this, "this"));
 342         _Safe_iterator __ret = *this;
 343         ++*this;
 344         return __ret;
 345       }
 346
 347       // ------ Utilities ------
 348
 349       /// Determine if this is a constant iterator.
 350       static _GLIBCXX_CONSTEXPR bool
 351       _S_constant()
 352       { return _IsConstant::__value; }
 353
 354       /**
 355        * @brief Return the underlying iterator
 356        */
 357       _Iterator&
 358       base() _GLIBCXX_NOEXCEPT { return *this; }
 359
 360       const _Iterator&
 361       base() const _GLIBCXX_NOEXCEPT { return *this; }
 362
 363       /**
 364        * @brief Conversion to underlying non-debug iterator to allow
 365        * better interaction with non-debug containers.
 366        */
 367       operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
 368
 369       /** Attach iterator to the given sequence. */
 370       void
 371       _M_attach(_Safe_sequence_base* __seq)
 372       { _Safe_base::_M_attach(__seq, _S_constant()); }
 373
 374       /** Likewise, but not thread-safe. */
 375       void
 376       _M_attach_single(_Safe_sequence_base* __seq)
 377       { _Safe_base::_M_attach_single(__seq, _S_constant()); }
 378
 379       /// Is the iterator dereferenceable?
 380       bool
 381       _M_dereferenceable() const
 382       { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
 383
 384       /// Is the iterator before a dereferenceable one?
 385       bool
 386       _M_before_dereferenceable() const
 387       {
 388         if (this->_M_incrementable())
 389         {
 390           _Iterator __base = base();
 391           return ++__base != _M_get_sequence()->_M_base().end();
 392         }
 393         return false;
 394       }
 395
 396       /// Is the iterator incrementable?
 397       bool
 398       _M_incrementable() const
 399       { return !this->_M_singular() && !_M_is_end(); }
 400
 401       /// Is the iterator value-initialized?
 402       bool
 403       _M_value_initialized() const
 404       { return _M_version == 0 && base() == _Iter_base(); }
 405
 406       // Can we advance the iterator @p __n steps (@p __n may be negative)
 407       bool
 408       _M_can_advance(difference_type __n, bool __strict = false) const;
 409
 410       // Can we advance the iterator using @p __dist in @p __way direction.
 411       template<typename _Diff>
 412         bool
 413         _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist,
 414                        int __way) const;
 415
 416       // Is the iterator range [*this, __rhs) valid?
 417       bool
 418       _M_valid_range(const _Safe_iterator& __rhs,
 419                      std::pair<difference_type, _Distance_precision>& __dist,
 420                      bool __check_dereferenceable = true) const;
 421
 422       // The sequence this iterator references.
 423       typename __gnu_cxx::__conditional_type<
 424         _IsConstant::__value, const _Sequence*, _Sequence*>::__type
 425       _M_get_sequence() const
 426       { return static_cast<_Sequence*>(_M_sequence); }
 427
 428       // Get distance to __rhs.
 429       typename _Distance_traits<_Iterator>::__type
 430       _M_get_distance_to(const _Safe_iterator& __rhs) const;
 431
 432       // Get distance from sequence begin up to *this.
 433       typename _Distance_traits<_Iterator>::__type
 434       _M_get_distance_from_begin() const;
 435
 436       // Get distance from *this to sequence end.
 437       typename _Distance_traits<_Iterator>::__type
 438       _M_get_distance_to_end() const;
 439
 440       /// Is this iterator equal to the sequence's begin() iterator?
 441       bool
 442       _M_is_begin() const
 443       { return base() == _M_get_sequence()->_M_base().begin(); }
 444
 445       /// Is this iterator equal to the sequence's end() iterator?
 446       bool
 447       _M_is_end() const
 448       { return base() == _M_get_sequence()->_M_base().end(); }
 449
 450       /// Is this iterator equal to the sequence's before_begin() iterator if
 451       /// any?
 452       bool
 453       _M_is_before_begin() const
 454       { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
 455
 456       /// Is this iterator equal to the sequence's before_begin() iterator if
 457       /// any or begin() otherwise?
 458       bool
 459       _M_is_beginnest() const
 460       { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
 461
 462       // ------ Operators ------
 463
 464       typedef _Safe_iterator<_Iterator, _Sequence, iterator_category> _Self;
 465
 466       _GLIBCXX_NODISCARD
 467       friend bool
 468       operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 469       {
 470         _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 471         return __lhs.base() == __rhs.base();
 472       }
 473
 474       template<typename _IteR>
 475         _GLIBCXX_NODISCARD
 476         friend bool
 477         operator==(const _Self& __lhs,
 478           const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
 479         _GLIBCXX_NOEXCEPT
 480         {
 481           _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 482           return __lhs.base() == __rhs.base();
 483         }
 484
 485 #if ! __cpp_lib_three_way_comparison
 486       _GLIBCXX_NODISCARD
 487       friend bool
 488       operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 489       {
 490         _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 491         return __lhs.base() != __rhs.base();
 492       }
 493
 494       template<typename _IteR>
 495         _GLIBCXX_NODISCARD
 496         friend bool
 497         operator!=(const _Self& __lhs,
 498           const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
 499         _GLIBCXX_NOEXCEPT
 500         {
 501           _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 502           return __lhs.base() != __rhs.base();
 503         }
 504 #endif // three-way comparison
 505     };
 506
 507   template<typename _Iterator, typename _Sequence>
 508     class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag>
 509     : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag>
 510     {
 511       typedef _Safe_iterator<_Iterator, _Sequence,
 512                              std::forward_iterator_tag> _Safe_base;
 513
 514     protected:
 515       typedef typename _Safe_base::_OtherIterator _OtherIterator;
 516
 517     public:
 518       /// @post the iterator is singular and unattached
 519       _Safe_iterator() _GLIBCXX_NOEXCEPT { }
 520
 521       /**
 522        * @brief Safe iterator construction from an unsafe iterator and
 523        * its sequence.
 524        *
 525        * @pre @p seq is not NULL
 526        * @post this is not singular
 527        */
 528       _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
 529       _GLIBCXX_NOEXCEPT
 530       : _Safe_base(__i, __seq)
 531       { }
 532
 533       /**
 534        * @brief Copy construction.
 535        */
 536       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 537       : _Safe_base(__x)
 538       { }
 539
 540 #if __cplusplus >= 201103L
 541       /** @brief Move construction. */
 542       _Safe_iterator(_Safe_iterator&&) = default;
 543 #endif
 544
 545       /**
 546        *  @brief Converting constructor from a mutable iterator to a
 547        *  constant iterator.
 548       */
 549       template<typename _MutableIterator>
 550         _Safe_iterator(
 551           const _Safe_iterator<_MutableIterator, _Sequence,
 552             typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
 553               std::__are_same<_MutableIterator, _OtherIterator>::__value,
 554                                std::bidirectional_iterator_tag>::__type>& __x)
 555         _GLIBCXX_NOEXCEPT
 556         : _Safe_base(__x)
 557         { }
 558
 559 #if __cplusplus >= 201103L
 560       /** @brief Copy assignment. */
 561       _Safe_iterator&
 562       operator=(const _Safe_iterator&) = default;
 563
 564       /** @brief Move assignment. */
 565       _Safe_iterator&
 566       operator=(_Safe_iterator&&) = default;
 567 #else
 568       /** @brief Copy assignment. */
 569       _Safe_iterator&
 570       operator=(const _Safe_iterator& __x)
 571       {
 572         _Safe_base::operator=(__x);
 573         return *this;
 574       }
 575 #endif
 576
 577       // ------ Input iterator requirements ------
 578       /**
 579        *  @brief Iterator preincrement
 580        *  @pre iterator is incrementable
 581        */
 582       _Safe_iterator&
 583       operator++() _GLIBCXX_NOEXCEPT
 584       {
 585         _Safe_base::operator++();
 586         return *this;
 587       }
 588
 589       /**
 590        *  @brief Iterator postincrement
 591        *  @pre iterator is incrementable
 592        */
 593       _Safe_iterator
 594       operator++(int) _GLIBCXX_NOEXCEPT
 595       {
 596         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 597                               _M_message(__msg_bad_inc)
 598                               ._M_iterator(*this, "this"));
 599         _Safe_iterator __ret = *this;
 600         ++*this;
 601         return __ret;
 602       }
 603
 604       // ------ Bidirectional iterator requirements ------
 605       /**
 606        *  @brief Iterator predecrement
 607        *  @pre iterator is decrementable
 608        */
 609       _Safe_iterator&
 610       operator--() _GLIBCXX_NOEXCEPT
 611       {
 612         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 613                               _M_message(__msg_bad_dec)
 614                               ._M_iterator(*this, "this"));
 615         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 616         --this->base();
 617         return *this;
 618       }
 619
 620       /**
 621        *  @brief Iterator postdecrement
 622        *  @pre iterator is decrementable
 623        */
 624       _Safe_iterator
 625       operator--(int) _GLIBCXX_NOEXCEPT
 626       {
 627         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 628                               _M_message(__msg_bad_dec)
 629                               ._M_iterator(*this, "this"));
 630         _Safe_iterator __ret = *this;
 631         --*this;
 632         return __ret;
 633       }
 634
 635       // ------ Utilities ------
 636
 637       // Is the iterator decrementable?
 638       bool
 639       _M_decrementable() const
 640       { return !this->_M_singular() && !this->_M_is_begin(); }
 641     };
 642
 643   template<typename _Iterator, typename _Sequence>
 644     class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>
 645     : public _Safe_iterator<_Iterator, _Sequence,
 646                             std::bidirectional_iterator_tag>
 647     {
 648       typedef _Safe_iterator<_Iterator, _Sequence,
 649                              std::bidirectional_iterator_tag> _Safe_base;
 650       typedef typename _Safe_base::_OtherIterator _OtherIterator;
 651
 652       typedef typename _Safe_base::_Self _Self;
 653       typedef _Safe_iterator<_OtherIterator, _Sequence,
 654                              std::random_access_iterator_tag> _OtherSelf;
 655
 656     public:
 657       typedef typename _Safe_base::difference_type      difference_type;
 658       typedef typename _Safe_base::reference            reference;
 659
 660       /// @post the iterator is singular and unattached
 661       _Safe_iterator() _GLIBCXX_NOEXCEPT { }
 662
 663       /**
 664        * @brief Safe iterator construction from an unsafe iterator and
 665        * its sequence.
 666        *
 667        * @pre @p seq is not NULL
 668        * @post this is not singular
 669        */
 670       _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
 671       _GLIBCXX_NOEXCEPT
 672       : _Safe_base(__i, __seq)
 673       { }
 674
 675       /**
 676        * @brief Copy construction.
 677        */
 678       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 679       : _Safe_base(__x)
 680       { }
 681
 682 #if __cplusplus >= 201103L
 683       /** @brief Move construction. */
 684       _Safe_iterator(_Safe_iterator&&) = default;
 685 #endif
 686
 687       /**
 688        *  @brief Converting constructor from a mutable iterator to a
 689        *  constant iterator.
 690       */
 691       template<typename _MutableIterator>
 692         _Safe_iterator(
 693           const _Safe_iterator<_MutableIterator, _Sequence,
 694             typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
 695               std::__are_same<_MutableIterator, _OtherIterator>::__value,
 696                                std::random_access_iterator_tag>::__type>& __x)
 697         _GLIBCXX_NOEXCEPT
 698         : _Safe_base(__x)
 699         { }
 700
 701 #if __cplusplus >= 201103L
 702       /** @brief Copy assignment. */
 703       _Safe_iterator&
 704       operator=(const _Safe_iterator&) = default;
 705
 706       /** @brief Move assignment. */
 707       _Safe_iterator&
 708       operator=(_Safe_iterator&&) = default;
 709 #else
 710       /** @brief Copy assignment. */
 711       _Safe_iterator&
 712       operator=(const _Safe_iterator& __x)
 713       {
 714         _Safe_base::operator=(__x);
 715         return *this;
 716       }
 717 #endif
 718
 719       // Is the iterator range [*this, __rhs) valid?
 720       bool
 721       _M_valid_range(const _Safe_iterator& __rhs,
 722                      std::pair<difference_type,
 723                                _Distance_precision>& __dist) const;
 724
 725       // ------ Input iterator requirements ------
 726       /**
 727        *  @brief Iterator preincrement
 728        *  @pre iterator is incrementable
 729        */
 730       _Safe_iterator&
 731       operator++() _GLIBCXX_NOEXCEPT
 732       {
 733         _Safe_base::operator++();
 734         return *this;
 735       }
 736
 737       /**
 738        *  @brief Iterator postincrement
 739        *  @pre iterator is incrementable
 740        */
 741       _Safe_iterator
 742       operator++(int) _GLIBCXX_NOEXCEPT
 743       {
 744         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 745                               _M_message(__msg_bad_inc)
 746                               ._M_iterator(*this, "this"));
 747         _Safe_iterator __ret = *this;
 748         ++*this;
 749         return __ret;
 750       }
 751
 752       // ------ Bidirectional iterator requirements ------
 753       /**
 754        *  @brief Iterator predecrement
 755        *  @pre iterator is decrementable
 756        */
 757       _Safe_iterator&
 758       operator--() _GLIBCXX_NOEXCEPT
 759       {
 760         _Safe_base::operator--();
 761         return *this;
 762       }
 763
 764       /**
 765        *  @brief Iterator postdecrement
 766        *  @pre iterator is decrementable
 767        */
 768       _Safe_iterator
 769       operator--(int) _GLIBCXX_NOEXCEPT
 770       {
 771         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 772                               _M_message(__msg_bad_dec)
 773                               ._M_iterator(*this, "this"));
 774         _Safe_iterator __ret = *this;
 775         --*this;
 776         return __ret;
 777       }
 778
 779       // ------ Random access iterator requirements ------
 780       _GLIBCXX_NODISCARD
 781       reference
 782       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
 783       {
 784         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
 785                               && this->_M_can_advance(__n + 1),
 786                               _M_message(__msg_iter_subscript_oob)
 787                               ._M_iterator(*this)._M_integer(__n));
 788         return this->base()[__n];
 789       }
 790
 791       _Safe_iterator&
 792       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
 793       {
 794         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 795                               _M_message(__msg_advance_oob)
 796                               ._M_iterator(*this)._M_integer(__n));
 797         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 798         this->base() += __n;
 799         return *this;
 800       }
 801
 802       _Safe_iterator&
 803       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
 804       {
 805         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 806                               _M_message(__msg_retreat_oob)
 807                               ._M_iterator(*this)._M_integer(__n));
 808         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 809         this->base() -= __n;
 810         return *this;
 811       }
 812
 813 #if __cpp_lib_three_way_comparison
 814       [[nodiscard]]
 815       friend auto
 816       operator<=>(const _Self& __lhs, const _Self& __rhs) noexcept
 817       {
 818         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 819         return __lhs.base() <=> __rhs.base();
 820       }
 821
 822       [[nodiscard]]
 823       friend auto
 824       operator<=>(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
 825       {
 826         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 827         return __lhs.base() <=> __rhs.base();
 828       }
 829 #else
 830       _GLIBCXX_NODISCARD
 831       friend bool
 832       operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 833       {
 834         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 835         return __lhs.base() < __rhs.base();
 836       }
 837
 838       _GLIBCXX_NODISCARD
 839       friend bool
 840       operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 841       {
 842         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 843         return __lhs.base() < __rhs.base();
 844       }
 845
 846       _GLIBCXX_NODISCARD
 847       friend bool
 848       operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 849       {
 850         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 851         return __lhs.base() <= __rhs.base();
 852       }
 853
 854       _GLIBCXX_NODISCARD
 855       friend bool
 856       operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 857       {
 858         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 859         return __lhs.base() <= __rhs.base();
 860       }
 861
 862       _GLIBCXX_NODISCARD
 863       friend bool
 864       operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 865       {
 866         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 867         return __lhs.base() > __rhs.base();
 868       }
 869
 870       _GLIBCXX_NODISCARD
 871       friend bool
 872       operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 873       {
 874         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 875         return __lhs.base() > __rhs.base();
 876       }
 877
 878       _GLIBCXX_NODISCARD
 879       friend bool
 880       operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 881       {
 882         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 883         return __lhs.base() >= __rhs.base();
 884       }
 885
 886       _GLIBCXX_NODISCARD
 887       friend bool
 888       operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 889       {
 890         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 891         return __lhs.base() >= __rhs.base();
 892       }
 893 #endif // three-way comparison
 894
 895       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 896       // According to the resolution of DR179 not only the various comparison
 897       // operators but also operator- must accept mixed iterator/const_iterator
 898       // parameters.
 899       _GLIBCXX_NODISCARD
 900       friend difference_type
 901       operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 902       {
 903         _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
 904         return __lhs.base() - __rhs.base();
 905       }
 906
 907       _GLIBCXX_NODISCARD
 908       friend difference_type
 909       operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 910       {
 911         _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
 912         return __lhs.base() - __rhs.base();
 913       }
 914
 915       _GLIBCXX_NODISCARD
 916       friend _Self
 917       operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
 918       {
 919         _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
 920                               _M_message(__msg_advance_oob)
 921                               ._M_iterator(__x)._M_integer(__n));
 922         return _Safe_iterator(__x.base() + __n, __x._M_sequence);
 923       }
 924
 925       _GLIBCXX_NODISCARD
 926       friend _Self
 927       operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
 928       {
 929         _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
 930                               _M_message(__msg_advance_oob)
 931                               ._M_iterator(__x)._M_integer(__n));
 932         return _Safe_iterator(__n + __x.base(), __x._M_sequence);
 933       }
 934
 935       _GLIBCXX_NODISCARD
 936       friend _Self
 937       operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
 938       {
 939         _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n),
 940                               _M_message(__msg_retreat_oob)
 941                               ._M_iterator(__x)._M_integer(__n));
 942         return _Safe_iterator(__x.base() - __n, __x._M_sequence);
 943       }
 944     };
 945
 946   /** Safe iterators know how to check if they form a valid range. */
 947   template<typename _Iterator, typename _Sequence, typename _Category>
 948     inline bool
 949     __valid_range(const _Safe_iterator<_Iterator, _Sequence,
 950                                        _Category>& __first,
 951                   const _Safe_iterator<_Iterator, _Sequence,
 952                                        _Category>& __last,
 953                   typename _Distance_traits<_Iterator>::__type& __dist)
 954     { return __first._M_valid_range(__last, __dist); }
 955
 956   template<typename _Iterator, typename _Sequence, typename _Category>
 957     inline bool
 958     __valid_range(const _Safe_iterator<_Iterator, _Sequence,
 959                                        _Category>& __first,
 960                   const _Safe_iterator<_Iterator, _Sequence,
 961                                        _Category>& __last)
 962     {
 963       typename _Distance_traits<_Iterator>::__type __dist;
 964       return __first._M_valid_range(__last, __dist);
 965     }
 966
 967   template<typename _Iterator, typename _Sequence, typename _Category,
 968            typename _Size>
 969     inline bool
 970     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 971                   _Size __n)
 972     { return __it._M_can_advance(__n); }
 973
 974   template<typename _Iterator, typename _Sequence, typename _Category,
 975            typename _Diff>
 976     inline bool
 977     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 978                   const std::pair<_Diff, _Distance_precision>& __dist,
 979                   int __way)
 980     { return __it._M_can_advance(__dist, __way); }
 981
 982   template<typename _Iterator, typename _Sequence>
 983     _Iterator
 984     __base(const _Safe_iterator<_Iterator, _Sequence,
 985                                 std::random_access_iterator_tag>& __it)
 986     { return __it.base(); }
 987
 988 #if __cplusplus < 201103L
 989   template<typename _Iterator, typename _Sequence>
 990     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
 991     { typedef _Iterator _Type; };
 992 #endif
 993
 994   template<typename _Iterator, typename _Sequence>
 995     inline _Iterator
 996     __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
 997     { return __it.base(); }
 998
 999 } // namespace __gnu_debug
1000
1001 #if __cplusplus >= 201103L && __cplusplus <= 201703L
1002 namespace std _GLIBCXX_VISIBILITY(default)
1003 {
1004 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1005
1006   template<typename _Iterator, typename _Container, typename _Sequence>
1007     constexpr auto
1008     __to_address(const __gnu_debug::_Safe_iterator<
1009                  __gnu_cxx::__normal_iterator<_Iterator, _Container>,
1010                  _Sequence>& __it) noexcept
1011     -> decltype(std::__to_address(__it.base().base()))
1012     { return std::__to_address(__it.base().base()); }
1013
1014 _GLIBCXX_END_NAMESPACE_VERSION
1015 }
1016 #endif
1017
1018 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS
1019 #undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS
1020 #undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS
1021 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
1022
1023 #include <debug/safe_iterator.tcc>
1024
1025 #endif