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

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