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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2003-2020 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
  39 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, _BadMsgId, _DiffMsgId) \
  40   _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular(),     \
  41                         _M_message(_BadMsgId)                           \
  42                         ._M_iterator(_Lhs, #_Lhs)                       \
  43                         ._M_iterator(_Rhs, #_Rhs));                     \
  44   _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs),                      \
  45                         _M_message(_DiffMsgId)                          \
  46                         ._M_iterator(_Lhs, #_Lhs)                       \
  47                         ._M_iterator(_Rhs, #_Rhs))
  48
  49 #define _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(_Lhs, _Rhs)                   \
  50   _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_compare_bad,    \
  51                                  __msg_compare_different)
  52
  53 #define _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(_Lhs, _Rhs)          \
  54   _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_order_bad,      \
  55                                  __msg_order_different)
  56
  57 #define _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(_Lhs, _Rhs)                 \
  58   _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_distance_bad,        \
  59                                  __msg_distance_different)
  60
  61 namespace __gnu_debug
  62 {
  63   /** Helper struct to deal with sequence offering a before_begin
  64    *  iterator.
  65    **/
  66   template<typename _Sequence>
  67     struct _BeforeBeginHelper
  68     {
  69       template<typename _Iterator, typename _Category>
  70         static bool
  71         _S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&)
  72         { return false; }
  73
  74       template<typename _Iterator, typename _Category>
  75         static bool
  76         _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it)
  77         { return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
  78     };
  79
  80   /** Sequence traits giving the size of a container if possible. */
  81   template<typename _Sequence>
  82     struct _Sequence_traits
  83     {
  84       typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;
  85
  86       static typename _DistTraits::__type
  87       _S_size(const _Sequence& __seq)
  88       { return std::make_pair(__seq.size(), __dp_exact); }
  89     };
  90
  91   /** \brief Safe iterator wrapper.
  92    *
  93    *  The class template %_Safe_iterator is a wrapper around an
  94    *  iterator that tracks the iterator's movement among sequences and
  95    *  checks that operations performed on the "safe" iterator are
  96    *  legal. In additional to the basic iterator operations (which are
  97    *  validated, and then passed to the underlying iterator),
  98    *  %_Safe_iterator has member functions for iterator invalidation,
  99    *  attaching/detaching the iterator from sequences, and querying
 100    *  the iterator's state.
 101    *
 102    *  Note that _Iterator must be the first base class so that it gets
 103    *  initialized before the iterator is being attached to the container's list
 104    *  of iterators and it is being detached before _Iterator get
 105    *  destroyed. Otherwise it would result in a data race.
 106    */
 107   template<typename _Iterator, typename _Sequence, typename _Category
 108            = typename std::iterator_traits<_Iterator>::iterator_category>
 109     class _Safe_iterator
 110     : private _Iterator,
 111       public _Safe_iterator_base
 112     {
 113       typedef _Iterator _Iter_base;
 114       typedef _Safe_iterator_base _Safe_base;
 115
 116       typedef std::iterator_traits<_Iterator> _Traits;
 117
 118     protected:
 119       typedef std::__are_same<typename _Sequence::_Base::const_iterator,
 120                               _Iterator> _IsConstant;
 121
 122       typedef typename __gnu_cxx::__conditional_type<
 123         _IsConstant::__value,
 124         typename _Sequence::_Base::iterator,
 125         typename _Sequence::_Base::const_iterator>::__type _OtherIterator;
 126
 127       struct _Attach_single
 128       { };
 129
 130       _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
 131       _GLIBCXX_NOEXCEPT
 132       : _Iter_base(__i)
 133       { _M_attach_single(__seq); }
 134
 135     public:
 136       typedef _Iterator                                 iterator_type;
 137       typedef typename _Traits::iterator_category       iterator_category;
 138       typedef typename _Traits::value_type              value_type;
 139       typedef typename _Traits::difference_type         difference_type;
 140       typedef typename _Traits::reference               reference;
 141       typedef typename _Traits::pointer                 pointer;
 142
 143 #if __cplusplus > 201703L && __cpp_lib_concepts
 144       using iterator_concept = std::__detail::__iter_concept<_Iterator>;
 145 #endif
 146
 147       /// @post the iterator is singular and unattached
 148       _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
 149
 150       /**
 151        * @brief Safe iterator construction from an unsafe iterator and
 152        * its sequence.
 153        *
 154        * @pre @p seq is not NULL
 155        * @post this is not singular
 156        */
 157       _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
 158       _GLIBCXX_NOEXCEPT
 159       : _Iter_base(__i), _Safe_base(__seq, _S_constant())
 160       {
 161         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 162                               _M_message(__msg_init_singular)
 163                               ._M_iterator(*this, "this"));
 164       }
 165
 166       /**
 167        * @brief Copy construction.
 168        */
 169       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 170       : _Iter_base(__x.base())
 171       {
 172         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 173         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 174         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 175                               || __x.base() == _Iterator(),
 176                               _M_message(__msg_init_copy_singular)
 177                               ._M_iterator(*this, "this")
 178                               ._M_iterator(__x, "other"));
 179         _M_attach(__x._M_sequence);
 180       }
 181
 182 #if __cplusplus >= 201103L
 183       /**
 184        * @brief Move construction.
 185        * @post __x is singular and unattached
 186        */
 187       _Safe_iterator(_Safe_iterator&& __x) noexcept
 188       : _Iter_base()
 189       {
 190         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 191                               || __x.base() == _Iterator(),
 192                               _M_message(__msg_init_copy_singular)
 193                               ._M_iterator(*this, "this")
 194                               ._M_iterator(__x, "other"));
 195         _Safe_sequence_base* __seq = __x._M_sequence;
 196         __x._M_detach();
 197         std::swap(base(), __x.base());
 198         _M_attach(__seq);
 199       }
 200 #endif
 201
 202       /**
 203        *  @brief Converting constructor from a mutable iterator to a
 204        *  constant iterator.
 205       */
 206       template<typename _MutableIterator>
 207         _Safe_iterator(
 208           const _Safe_iterator<_MutableIterator, _Sequence,
 209             typename __gnu_cxx::__enable_if<_IsConstant::__value &&
 210               std::__are_same<_MutableIterator, _OtherIterator>::__value,
 211                                _Category>::__type>& __x)
 212         _GLIBCXX_NOEXCEPT
 213         : _Iter_base(__x.base())
 214         {
 215           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 216           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 217           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 218                                 || __x.base() == _MutableIterator(),
 219                                 _M_message(__msg_init_const_singular)
 220                                 ._M_iterator(*this, "this")
 221                                 ._M_iterator(__x, "other"));
 222           _M_attach(__x._M_sequence);
 223         }
 224
 225       /**
 226        * @brief Copy assignment.
 227        */
 228       _Safe_iterator&
 229       operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 230       {
 231         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 232         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 233         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 234                               || __x.base() == _Iterator(),
 235                               _M_message(__msg_copy_singular)
 236                               ._M_iterator(*this, "this")
 237                               ._M_iterator(__x, "other"));
 238
 239         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 240           {
 241             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 242             base() = __x.base();
 243             _M_version = __x._M_sequence->_M_version;
 244           }
 245         else
 246           {
 247             _M_detach();
 248             base() = __x.base();
 249             _M_attach(__x._M_sequence);
 250           }
 251
 252         return *this;
 253       }
 254
 255 #if __cplusplus >= 201103L
 256       /**
 257        * @brief Move assignment.
 258        * @post __x is singular and unattached
 259        */
 260       _Safe_iterator&
 261       operator=(_Safe_iterator&& __x) noexcept
 262       {
 263         _GLIBCXX_DEBUG_VERIFY(this != &__x,
 264                               _M_message(__msg_self_move_assign)
 265                               ._M_iterator(*this, "this"));
 266         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 267                               || __x.base() == _Iterator(),
 268                               _M_message(__msg_copy_singular)
 269                               ._M_iterator(*this, "this")
 270                               ._M_iterator(__x, "other"));
 271
 272         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 273           {
 274             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 275             base() = __x.base();
 276             _M_version = __x._M_sequence->_M_version;
 277           }
 278         else
 279           {
 280             _M_detach();
 281             base() = __x.base();
 282             _M_attach(__x._M_sequence);
 283           }
 284
 285         __x._M_detach();
 286         __x.base() = _Iterator();
 287         return *this;
 288       }
 289 #endif
 290
 291       /**
 292        *  @brief Iterator dereference.
 293        *  @pre iterator is dereferenceable
 294        */
 295       reference
 296       operator*() const _GLIBCXX_NOEXCEPT
 297       {
 298         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 299                               _M_message(__msg_bad_deref)
 300                               ._M_iterator(*this, "this"));
 301         return *base();
 302       }
 303
 304       /**
 305        *  @brief Iterator dereference.
 306        *  @pre iterator is dereferenceable
 307        */
 308       pointer
 309       operator->() const _GLIBCXX_NOEXCEPT
 310       {
 311         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 312                               _M_message(__msg_bad_deref)
 313                               ._M_iterator(*this, "this"));
 314         return base().operator->();
 315       }
 316
 317       // ------ Input iterator requirements ------
 318       /**
 319        *  @brief Iterator preincrement
 320        *  @pre iterator is incrementable
 321        */
 322       _Safe_iterator&
 323       operator++() _GLIBCXX_NOEXCEPT
 324       {
 325         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 326                               _M_message(__msg_bad_inc)
 327                               ._M_iterator(*this, "this"));
 328         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 329         ++base();
 330         return *this;
 331       }
 332
 333       /**
 334        *  @brief Iterator postincrement
 335        *  @pre iterator is incrementable
 336        */
 337       _Safe_iterator
 338       operator++(int) _GLIBCXX_NOEXCEPT
 339       {
 340         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 341                               _M_message(__msg_bad_inc)
 342                               ._M_iterator(*this, "this"));
 343         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 344         return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
 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       // Can we advance the iterator @p __n steps (@p __n may be negative)
 402       bool
 403       _M_can_advance(difference_type __n, bool __strict = false) const;
 404
 405       // Is the iterator range [*this, __rhs) valid?
 406       bool
 407       _M_valid_range(const _Safe_iterator& __rhs,
 408                      std::pair<difference_type, _Distance_precision>& __dist,
 409                      bool __check_dereferenceable = true) const;
 410
 411       // The sequence this iterator references.
 412       typename __gnu_cxx::__conditional_type<
 413         _IsConstant::__value, const _Sequence*, _Sequence*>::__type
 414       _M_get_sequence() const
 415       { return static_cast<_Sequence*>(_M_sequence); }
 416
 417       // Get distance to __rhs.
 418       typename _Distance_traits<_Iterator>::__type
 419       _M_get_distance_to(const _Safe_iterator& __rhs) const;
 420
 421       // Get distance from sequence begin up to *this.
 422       typename _Distance_traits<_Iterator>::__type
 423       _M_get_distance_from_begin() const;
 424
 425       // Get distance from *this to sequence end.
 426       typename _Distance_traits<_Iterator>::__type
 427       _M_get_distance_to_end() const;
 428
 429       /// Is this iterator equal to the sequence's begin() iterator?
 430       bool
 431       _M_is_begin() const
 432       { return base() == _M_get_sequence()->_M_base().begin(); }
 433
 434       /// Is this iterator equal to the sequence's end() iterator?
 435       bool
 436       _M_is_end() const
 437       { return base() == _M_get_sequence()->_M_base().end(); }
 438
 439       /// Is this iterator equal to the sequence's before_begin() iterator if
 440       /// any?
 441       bool
 442       _M_is_before_begin() const
 443       { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
 444
 445       /// Is this iterator equal to the sequence's before_begin() iterator if
 446       /// any or begin() otherwise?
 447       bool
 448       _M_is_beginnest() const
 449       { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
 450
 451       // ------ Operators ------
 452
 453       typedef _Safe_iterator<_Iterator, _Sequence, iterator_category> _Self;
 454
 455       friend bool
 456       operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 457       {
 458         _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 459         return __lhs.base() == __rhs.base();
 460       }
 461
 462       template<typename _IteR>
 463         friend bool
 464         operator==(const _Self& __lhs,
 465           const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
 466         _GLIBCXX_NOEXCEPT
 467         {
 468           _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 469           return __lhs.base() == __rhs.base();
 470         }
 471
 472       friend bool
 473       operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 474       {
 475         _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 476         return __lhs.base() != __rhs.base();
 477       }
 478
 479       template<typename _IteR>
 480         friend bool
 481         operator!=(const _Self& __lhs,
 482           const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
 483         _GLIBCXX_NOEXCEPT
 484         {
 485           _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
 486           return __lhs.base() != __rhs.base();
 487         }
 488     };
 489
 490   template<typename _Iterator, typename _Sequence>
 491     class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag>
 492     : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag>
 493     {
 494       typedef _Safe_iterator<_Iterator, _Sequence,
 495                              std::forward_iterator_tag> _Safe_base;
 496
 497     protected:
 498       typedef typename _Safe_base::_OtherIterator _OtherIterator;
 499       typedef typename _Safe_base::_Attach_single _Attach_single;
 500
 501       _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
 502       _GLIBCXX_NOEXCEPT
 503       : _Safe_base(__i, __seq, _Attach_single())
 504       { }
 505
 506     public:
 507       /// @post the iterator is singular and unattached
 508       _Safe_iterator() _GLIBCXX_NOEXCEPT { }
 509
 510       /**
 511        * @brief Safe iterator construction from an unsafe iterator and
 512        * its sequence.
 513        *
 514        * @pre @p seq is not NULL
 515        * @post this is not singular
 516        */
 517       _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
 518       _GLIBCXX_NOEXCEPT
 519       : _Safe_base(__i, __seq)
 520       { }
 521
 522       /**
 523        * @brief Copy construction.
 524        */
 525       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 526       : _Safe_base(__x)
 527       { }
 528
 529 #if __cplusplus >= 201103L
 530       /** @brief Move construction. */
 531       _Safe_iterator(_Safe_iterator&&) = default;
 532 #endif
 533
 534       /**
 535        *  @brief Converting constructor from a mutable iterator to a
 536        *  constant iterator.
 537       */
 538       template<typename _MutableIterator>
 539         _Safe_iterator(
 540           const _Safe_iterator<_MutableIterator, _Sequence,
 541             typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
 542               std::__are_same<_MutableIterator, _OtherIterator>::__value,
 543                                std::bidirectional_iterator_tag>::__type>& __x)
 544         _GLIBCXX_NOEXCEPT
 545         : _Safe_base(__x)
 546         { }
 547
 548 #if __cplusplus >= 201103L
 549       /** @brief Copy assignment. */
 550       _Safe_iterator&
 551       operator=(const _Safe_iterator&) = default;
 552
 553       /** @brief Move assignment. */
 554       _Safe_iterator&
 555       operator=(_Safe_iterator&&) = default;
 556 #else
 557       /** @brief Copy assignment. */
 558       _Safe_iterator&
 559       operator=(const _Safe_iterator& __x)
 560       {
 561         _Safe_base::operator=(__x);
 562         return *this;
 563       }
 564 #endif
 565
 566       // ------ Input iterator requirements ------
 567       /**
 568        *  @brief Iterator preincrement
 569        *  @pre iterator is incrementable
 570        */
 571       _Safe_iterator&
 572       operator++() _GLIBCXX_NOEXCEPT
 573       {
 574         _Safe_base::operator++();
 575         return *this;
 576       }
 577
 578       /**
 579        *  @brief Iterator postincrement
 580        *  @pre iterator is incrementable
 581        */
 582       _Safe_iterator
 583       operator++(int) _GLIBCXX_NOEXCEPT
 584       {
 585         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 586                               _M_message(__msg_bad_inc)
 587                               ._M_iterator(*this, "this"));
 588         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 589         return _Safe_iterator(this->base()++, this->_M_sequence,
 590                               _Attach_single());
 591       }
 592
 593       // ------ Bidirectional iterator requirements ------
 594       /**
 595        *  @brief Iterator predecrement
 596        *  @pre iterator is decrementable
 597        */
 598       _Safe_iterator&
 599       operator--() _GLIBCXX_NOEXCEPT
 600       {
 601         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 602                               _M_message(__msg_bad_dec)
 603                               ._M_iterator(*this, "this"));
 604         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 605         --this->base();
 606         return *this;
 607       }
 608
 609       /**
 610        *  @brief Iterator postdecrement
 611        *  @pre iterator is decrementable
 612        */
 613       _Safe_iterator
 614       operator--(int) _GLIBCXX_NOEXCEPT
 615       {
 616         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 617                               _M_message(__msg_bad_dec)
 618                               ._M_iterator(*this, "this"));
 619         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 620         return _Safe_iterator(this->base()--, this->_M_sequence,
 621                               _Attach_single());
 622       }
 623
 624       // ------ Utilities ------
 625
 626       // Is the iterator decrementable?
 627       bool
 628       _M_decrementable() const
 629       { return !this->_M_singular() && !this->_M_is_begin(); }
 630     };
 631
 632   template<typename _Iterator, typename _Sequence>
 633     class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>
 634     : public _Safe_iterator<_Iterator, _Sequence,
 635                             std::bidirectional_iterator_tag>
 636     {
 637       typedef _Safe_iterator<_Iterator, _Sequence,
 638                              std::bidirectional_iterator_tag> _Safe_base;
 639       typedef typename _Safe_base::_OtherIterator _OtherIterator;
 640
 641       typedef typename _Safe_base::_Self _Self;
 642       typedef _Safe_iterator<_OtherIterator, _Sequence,
 643                              std::random_access_iterator_tag> _OtherSelf;
 644
 645       typedef typename _Safe_base::_Attach_single _Attach_single;
 646
 647       _Safe_iterator(_Iterator __i, _Safe_sequence_base* __seq, _Attach_single)
 648       _GLIBCXX_NOEXCEPT
 649       : _Safe_base(__i, __seq, _Attach_single())
 650       { }
 651
 652     public:
 653       typedef typename _Safe_base::difference_type      difference_type;
 654       typedef typename _Safe_base::reference            reference;
 655
 656       /// @post the iterator is singular and unattached
 657       _Safe_iterator() _GLIBCXX_NOEXCEPT { }
 658
 659       /**
 660        * @brief Safe iterator construction from an unsafe iterator and
 661        * its sequence.
 662        *
 663        * @pre @p seq is not NULL
 664        * @post this is not singular
 665        */
 666       _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
 667       _GLIBCXX_NOEXCEPT
 668       : _Safe_base(__i, __seq)
 669       { }
 670
 671       /**
 672        * @brief Copy construction.
 673        */
 674       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 675       : _Safe_base(__x)
 676       { }
 677
 678 #if __cplusplus >= 201103L
 679       /** @brief Move construction. */
 680       _Safe_iterator(_Safe_iterator&&) = default;
 681 #endif
 682
 683       /**
 684        *  @brief Converting constructor from a mutable iterator to a
 685        *  constant iterator.
 686       */
 687       template<typename _MutableIterator>
 688         _Safe_iterator(
 689           const _Safe_iterator<_MutableIterator, _Sequence,
 690             typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
 691               std::__are_same<_MutableIterator, _OtherIterator>::__value,
 692                                std::random_access_iterator_tag>::__type>& __x)
 693         _GLIBCXX_NOEXCEPT
 694         : _Safe_base(__x)
 695         { }
 696
 697 #if __cplusplus >= 201103L
 698       /** @brief Copy assignment. */
 699       _Safe_iterator&
 700       operator=(const _Safe_iterator&) = default;
 701
 702       /** @brief Move assignment. */
 703       _Safe_iterator&
 704       operator=(_Safe_iterator&&) = default;
 705 #else
 706       /** @brief Copy assignment. */
 707       _Safe_iterator&
 708       operator=(const _Safe_iterator& __x)
 709       {
 710         _Safe_base::operator=(__x);
 711         return *this;
 712       }
 713 #endif
 714
 715       // Is the iterator range [*this, __rhs) valid?
 716       bool
 717       _M_valid_range(const _Safe_iterator& __rhs,
 718                      std::pair<difference_type,
 719                                _Distance_precision>& __dist) const;
 720
 721       // ------ Input iterator requirements ------
 722       /**
 723        *  @brief Iterator preincrement
 724        *  @pre iterator is incrementable
 725        */
 726       _Safe_iterator&
 727       operator++() _GLIBCXX_NOEXCEPT
 728       {
 729         _Safe_base::operator++();
 730         return *this;
 731       }
 732
 733       /**
 734        *  @brief Iterator postincrement
 735        *  @pre iterator is incrementable
 736        */
 737       _Safe_iterator
 738       operator++(int) _GLIBCXX_NOEXCEPT
 739       {
 740         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 741                               _M_message(__msg_bad_inc)
 742                               ._M_iterator(*this, "this"));
 743         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 744         return _Safe_iterator(this->base()++, this->_M_sequence,
 745                               _Attach_single());
 746       }
 747
 748       // ------ Bidirectional iterator requirements ------
 749       /**
 750        *  @brief Iterator predecrement
 751        *  @pre iterator is decrementable
 752        */
 753       _Safe_iterator&
 754       operator--() _GLIBCXX_NOEXCEPT
 755       {
 756         _Safe_base::operator--();
 757         return *this;
 758       }
 759
 760       /**
 761        *  @brief Iterator postdecrement
 762        *  @pre iterator is decrementable
 763        */
 764       _Safe_iterator
 765       operator--(int) _GLIBCXX_NOEXCEPT
 766       {
 767         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 768                               _M_message(__msg_bad_dec)
 769                               ._M_iterator(*this, "this"));
 770         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 771         return _Safe_iterator(this->base()--, this->_M_sequence,
 772                               _Attach_single());
 773       }
 774
 775       // ------ Random access iterator requirements ------
 776       reference
 777       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
 778       {
 779         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
 780                               && this->_M_can_advance(__n + 1),
 781                               _M_message(__msg_iter_subscript_oob)
 782                               ._M_iterator(*this)._M_integer(__n));
 783         return this->base()[__n];
 784       }
 785
 786       _Safe_iterator&
 787       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
 788       {
 789         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 790                               _M_message(__msg_advance_oob)
 791                               ._M_iterator(*this)._M_integer(__n));
 792         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 793         this->base() += __n;
 794         return *this;
 795       }
 796
 797       _Safe_iterator&
 798       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
 799       {
 800         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 801                               _M_message(__msg_retreat_oob)
 802                               ._M_iterator(*this)._M_integer(__n));
 803         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 804         this->base() -= __n;
 805         return *this;
 806       }
 807
 808       friend bool
 809       operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 810       {
 811         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 812         return __lhs.base() < __rhs.base();
 813       }
 814
 815       friend bool
 816       operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 817       {
 818         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 819         return __lhs.base() < __rhs.base();
 820       }
 821
 822       friend bool
 823       operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 824       {
 825         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 826         return __lhs.base() <= __rhs.base();
 827       }
 828
 829       friend bool
 830       operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 831       {
 832         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 833         return __lhs.base() <= __rhs.base();
 834       }
 835
 836       friend bool
 837       operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 838       {
 839         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 840         return __lhs.base() > __rhs.base();
 841       }
 842
 843       friend bool
 844       operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 845       {
 846         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 847         return __lhs.base() > __rhs.base();
 848       }
 849
 850       friend bool
 851       operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 852       {
 853         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 854         return __lhs.base() >= __rhs.base();
 855       }
 856
 857       friend bool
 858       operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 859       {
 860         _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
 861         return __lhs.base() >= __rhs.base();
 862       }
 863
 864       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 865       // According to the resolution of DR179 not only the various comparison
 866       // operators but also operator- must accept mixed iterator/const_iterator
 867       // parameters.
 868       friend difference_type
 869       operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
 870       {
 871         _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
 872         return __lhs.base() - __rhs.base();
 873       }
 874
 875       friend difference_type
 876       operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
 877       {
 878         _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
 879         return __lhs.base() - __rhs.base();
 880       }
 881
 882       friend _Self
 883       operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
 884       {
 885         _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
 886                               _M_message(__msg_advance_oob)
 887                               ._M_iterator(__x)._M_integer(__n));
 888         return _Safe_iterator(__x.base() + __n, __x._M_sequence);
 889       }
 890
 891       friend _Self
 892       operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
 893       {
 894         _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
 895                               _M_message(__msg_advance_oob)
 896                               ._M_iterator(__x)._M_integer(__n));
 897         return _Safe_iterator(__n + __x.base(), __x._M_sequence);
 898       }
 899
 900       friend _Self
 901       operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
 902       {
 903         _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n),
 904                               _M_message(__msg_retreat_oob)
 905                               ._M_iterator(__x)._M_integer(__n));
 906         return _Safe_iterator(__x.base() - __n, __x._M_sequence);
 907       }
 908     };
 909
 910   /** Safe iterators know how to check if they form a valid range. */
 911   template<typename _Iterator, typename _Sequence, typename _Category>
 912     inline bool
 913     __valid_range(const _Safe_iterator<_Iterator, _Sequence,
 914                                        _Category>& __first,
 915                   const _Safe_iterator<_Iterator, _Sequence,
 916                                        _Category>& __last,
 917                   typename _Distance_traits<_Iterator>::__type& __dist)
 918     { return __first._M_valid_range(__last, __dist); }
 919
 920   template<typename _Iterator, typename _Sequence, typename _Category>
 921     inline bool
 922     __valid_range(const _Safe_iterator<_Iterator, _Sequence,
 923                                        _Category>& __first,
 924                   const _Safe_iterator<_Iterator, _Sequence,
 925                                        _Category>& __last)
 926     {
 927       typename _Distance_traits<_Iterator>::__type __dist;
 928       return __first._M_valid_range(__last, __dist);
 929     }
 930
 931   template<typename _Iterator, typename _Sequence, typename _Category,
 932            typename _Size>
 933     inline bool
 934     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
 935                   _Size __n)
 936     { return __it._M_can_advance(__n); }
 937
 938   template<typename _Iterator, typename _Sequence>
 939     _Iterator
 940     __base(const _Safe_iterator<_Iterator, _Sequence,
 941                                 std::random_access_iterator_tag>& __it)
 942     { return __it.base(); }
 943
 944 #if __cplusplus < 201103L
 945   template<typename _Iterator, typename _Sequence>
 946     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
 947     { typedef _Iterator _Type; };
 948 #endif
 949
 950   template<typename _Iterator, typename _Sequence>
 951     inline _Iterator
 952     __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
 953     { return __it.base(); }
 954
 955 } // namespace __gnu_debug
 956
 957 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS
 958 #undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS
 959 #undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS
 960 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
 961
 962 #include <debug/safe_iterator.tcc>
 963
 964 #endif