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

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