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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2003-2015 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        *  @todo Make this correct w.r.t. iterators that return proxies
 278        */
 279       pointer
 280       operator->() const _GLIBCXX_NOEXCEPT
 281       {
 282         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 283                               _M_message(__msg_bad_deref)
 284                               ._M_iterator(*this, "this"));
 285         return std::__addressof(*base());
 286       }
 287
 288       // ------ Input iterator requirements ------
 289       /**
 290        *  @brief Iterator preincrement
 291        *  @pre iterator is incrementable
 292        */
 293       _Safe_iterator&
 294       operator++() _GLIBCXX_NOEXCEPT
 295       {
 296         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 297                               _M_message(__msg_bad_inc)
 298                               ._M_iterator(*this, "this"));
 299         __gnu_cxx::__scoped_lock(this->_M_get_mutex());
 300         ++base();
 301         return *this;
 302       }
 303
 304       /**
 305        *  @brief Iterator postincrement
 306        *  @pre iterator is incrementable
 307        */
 308       _Safe_iterator
 309       operator++(int) _GLIBCXX_NOEXCEPT
 310       {
 311         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 312                               _M_message(__msg_bad_inc)
 313                               ._M_iterator(*this, "this"));
 314         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 315         return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
 316       }
 317
 318       // ------ Bidirectional iterator requirements ------
 319       /**
 320        *  @brief Iterator predecrement
 321        *  @pre iterator is decrementable
 322        */
 323       _Safe_iterator&
 324       operator--() _GLIBCXX_NOEXCEPT
 325       {
 326         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 327                               _M_message(__msg_bad_dec)
 328                               ._M_iterator(*this, "this"));
 329         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 330         --base();
 331         return *this;
 332       }
 333
 334       /**
 335        *  @brief Iterator postdecrement
 336        *  @pre iterator is decrementable
 337        */
 338       _Safe_iterator
 339       operator--(int) _GLIBCXX_NOEXCEPT
 340       {
 341         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 342                               _M_message(__msg_bad_dec)
 343                               ._M_iterator(*this, "this"));
 344         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 345         return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
 346       }
 347
 348       // ------ Random access iterator requirements ------
 349       reference
 350       operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
 351       {
 352         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
 353                               && this->_M_can_advance(__n+1),
 354                               _M_message(__msg_iter_subscript_oob)
 355                               ._M_iterator(*this)._M_integer(__n));
 356         return base()[__n];
 357       }
 358
 359       _Safe_iterator&
 360       operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
 361       {
 362         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 363                               _M_message(__msg_advance_oob)
 364                               ._M_iterator(*this)._M_integer(__n));
 365         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 366         base() += __n;
 367         return *this;
 368       }
 369
 370       _Safe_iterator
 371       operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
 372       {
 373         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 374                               _M_message(__msg_advance_oob)
 375                               ._M_iterator(*this)._M_integer(__n));
 376         return _Safe_iterator(base() + __n, this->_M_sequence);
 377       }
 378
 379       _Safe_iterator&
 380       operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
 381       {
 382         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 383                               _M_message(__msg_retreat_oob)
 384                               ._M_iterator(*this)._M_integer(__n));
 385         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 386         base() -= __n;
 387         return *this;
 388       }
 389
 390       _Safe_iterator
 391       operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
 392       {
 393         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 394                               _M_message(__msg_retreat_oob)
 395                               ._M_iterator(*this)._M_integer(__n));
 396         return _Safe_iterator(base() - __n, this->_M_sequence);
 397       }
 398
 399       // ------ Utilities ------
 400       /**
 401        * @brief Return the underlying iterator
 402        */
 403       _Iterator&
 404       base() _GLIBCXX_NOEXCEPT { return *this; }
 405
 406       const _Iterator&
 407       base() const _GLIBCXX_NOEXCEPT { return *this; }
 408
 409       /**
 410        * @brief Conversion to underlying non-debug iterator to allow
 411        * better interaction with non-debug containers.
 412        */
 413       operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
 414
 415       /** Attach iterator to the given sequence. */
 416       void
 417       _M_attach(_Safe_sequence_base* __seq)
 418       { _Safe_base::_M_attach(__seq, _M_constant()); }
 419
 420       /** Likewise, but not thread-safe. */
 421       void
 422       _M_attach_single(_Safe_sequence_base* __seq)
 423       { _Safe_base::_M_attach_single(__seq, _M_constant()); }
 424
 425       /// Is the iterator dereferenceable?
 426       bool
 427       _M_dereferenceable() const
 428       { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
 429
 430       /// Is the iterator before a dereferenceable one?
 431       bool
 432       _M_before_dereferenceable() const
 433       {
 434         if (this->_M_incrementable())
 435         {
 436           _Iterator __base = base();
 437           return ++__base != _M_get_sequence()->_M_base().end();
 438         }
 439         return false;
 440       }
 441
 442       /// Is the iterator incrementable?
 443       bool
 444       _M_incrementable() const
 445       { return !this->_M_singular() && !_M_is_end(); }
 446
 447       // Is the iterator decrementable?
 448       bool
 449       _M_decrementable() const { return !_M_singular() && !_M_is_begin(); }
 450
 451       // Can we advance the iterator @p __n steps (@p __n may be negative)
 452       bool
 453       _M_can_advance(const difference_type& __n) const;
 454
 455       // Is the iterator range [*this, __rhs) valid?
 456       bool
 457       _M_valid_range(const _Safe_iterator& __rhs,
 458                      std::pair<difference_type, _Distance_precision>& __dist,
 459                      bool __check_dereferenceable = true) const;
 460
 461       // The sequence this iterator references.
 462       typename
 463       __gnu_cxx::__conditional_type<std::__are_same<_Const_iterator,
 464                                                     _Safe_iterator>::__value,
 465                                     const _Sequence*,
 466                                     _Sequence*>::__type
 467       _M_get_sequence() const
 468       { return static_cast<_Sequence*>(_M_sequence); }
 469
 470       /// Is this iterator equal to the sequence's begin() iterator?
 471       bool
 472       _M_is_begin() const
 473       { return base() == _M_get_sequence()->_M_base().begin(); }
 474
 475       /// Is this iterator equal to the sequence's end() iterator?
 476       bool
 477       _M_is_end() const
 478       { return base() == _M_get_sequence()->_M_base().end(); }
 479
 480       /// Is this iterator equal to the sequence's before_begin() iterator if
 481       /// any?
 482       bool
 483       _M_is_before_begin() const
 484       { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
 485
 486       /// Is this iterator equal to the sequence's before_begin() iterator if
 487       /// any or begin() otherwise?
 488       bool
 489       _M_is_beginnest() const
 490       { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
 491     };
 492
 493   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 494     inline bool
 495     operator==(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 496                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 497     _GLIBCXX_NOEXCEPT
 498     {
 499       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 500                             _M_message(__msg_iter_compare_bad)
 501                             ._M_iterator(__lhs, "lhs")
 502                             ._M_iterator(__rhs, "rhs"));
 503       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 504                             _M_message(__msg_compare_different)
 505                             ._M_iterator(__lhs, "lhs")
 506                             ._M_iterator(__rhs, "rhs"));
 507       return __lhs.base() == __rhs.base();
 508     }
 509
 510   template<typename _Iterator, typename _Sequence>
 511     inline bool
 512     operator==(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 513                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 514     _GLIBCXX_NOEXCEPT
 515     {
 516       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 517                             _M_message(__msg_iter_compare_bad)
 518                             ._M_iterator(__lhs, "lhs")
 519                             ._M_iterator(__rhs, "rhs"));
 520       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 521                             _M_message(__msg_compare_different)
 522                             ._M_iterator(__lhs, "lhs")
 523                             ._M_iterator(__rhs, "rhs"));
 524       return __lhs.base() == __rhs.base();
 525     }
 526
 527   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 528     inline bool
 529     operator!=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 530                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 531     _GLIBCXX_NOEXCEPT
 532     {
 533       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 534                             _M_message(__msg_iter_compare_bad)
 535                             ._M_iterator(__lhs, "lhs")
 536                             ._M_iterator(__rhs, "rhs"));
 537       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 538                             _M_message(__msg_compare_different)
 539                             ._M_iterator(__lhs, "lhs")
 540                             ._M_iterator(__rhs, "rhs"));
 541       return __lhs.base() != __rhs.base();
 542     }
 543
 544   template<typename _Iterator, typename _Sequence>
 545     inline bool
 546     operator!=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 547                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 548     _GLIBCXX_NOEXCEPT
 549     {
 550       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 551                             _M_message(__msg_iter_compare_bad)
 552                             ._M_iterator(__lhs, "lhs")
 553                             ._M_iterator(__rhs, "rhs"));
 554       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 555                             _M_message(__msg_compare_different)
 556                             ._M_iterator(__lhs, "lhs")
 557                             ._M_iterator(__rhs, "rhs"));
 558       return __lhs.base() != __rhs.base();
 559     }
 560
 561   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 562     inline bool
 563     operator<(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 564               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 565     _GLIBCXX_NOEXCEPT
 566     {
 567       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 568                             _M_message(__msg_iter_order_bad)
 569                             ._M_iterator(__lhs, "lhs")
 570                             ._M_iterator(__rhs, "rhs"));
 571       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 572                             _M_message(__msg_order_different)
 573                             ._M_iterator(__lhs, "lhs")
 574                             ._M_iterator(__rhs, "rhs"));
 575       return __lhs.base() < __rhs.base();
 576     }
 577
 578   template<typename _Iterator, typename _Sequence>
 579     inline bool
 580     operator<(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 581               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 582     _GLIBCXX_NOEXCEPT
 583     {
 584       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 585                             _M_message(__msg_iter_order_bad)
 586                             ._M_iterator(__lhs, "lhs")
 587                             ._M_iterator(__rhs, "rhs"));
 588       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 589                             _M_message(__msg_order_different)
 590                             ._M_iterator(__lhs, "lhs")
 591                             ._M_iterator(__rhs, "rhs"));
 592       return __lhs.base() < __rhs.base();
 593     }
 594
 595   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 596     inline bool
 597     operator<=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 598                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 599     _GLIBCXX_NOEXCEPT
 600     {
 601       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 602                             _M_message(__msg_iter_order_bad)
 603                             ._M_iterator(__lhs, "lhs")
 604                             ._M_iterator(__rhs, "rhs"));
 605       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 606                             _M_message(__msg_order_different)
 607                             ._M_iterator(__lhs, "lhs")
 608                             ._M_iterator(__rhs, "rhs"));
 609       return __lhs.base() <= __rhs.base();
 610     }
 611
 612   template<typename _Iterator, typename _Sequence>
 613     inline bool
 614     operator<=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 615                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 616     _GLIBCXX_NOEXCEPT
 617     {
 618       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 619                             _M_message(__msg_iter_order_bad)
 620                             ._M_iterator(__lhs, "lhs")
 621                             ._M_iterator(__rhs, "rhs"));
 622       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 623                             _M_message(__msg_order_different)
 624                             ._M_iterator(__lhs, "lhs")
 625                             ._M_iterator(__rhs, "rhs"));
 626       return __lhs.base() <= __rhs.base();
 627     }
 628
 629   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 630     inline bool
 631     operator>(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 632               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 633     _GLIBCXX_NOEXCEPT
 634     {
 635       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 636                             _M_message(__msg_iter_order_bad)
 637                             ._M_iterator(__lhs, "lhs")
 638                             ._M_iterator(__rhs, "rhs"));
 639       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 640                             _M_message(__msg_order_different)
 641                             ._M_iterator(__lhs, "lhs")
 642                             ._M_iterator(__rhs, "rhs"));
 643       return __lhs.base() > __rhs.base();
 644     }
 645
 646   template<typename _Iterator, typename _Sequence>
 647     inline bool
 648     operator>(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 649               const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 650     _GLIBCXX_NOEXCEPT
 651     {
 652       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 653                             _M_message(__msg_iter_order_bad)
 654                             ._M_iterator(__lhs, "lhs")
 655                             ._M_iterator(__rhs, "rhs"));
 656       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 657                             _M_message(__msg_order_different)
 658                             ._M_iterator(__lhs, "lhs")
 659                             ._M_iterator(__rhs, "rhs"));
 660       return __lhs.base() > __rhs.base();
 661     }
 662
 663   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 664     inline bool
 665     operator>=(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 666                const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 667     _GLIBCXX_NOEXCEPT
 668     {
 669       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 670                             _M_message(__msg_iter_order_bad)
 671                             ._M_iterator(__lhs, "lhs")
 672                             ._M_iterator(__rhs, "rhs"));
 673       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 674                             _M_message(__msg_order_different)
 675                             ._M_iterator(__lhs, "lhs")
 676                             ._M_iterator(__rhs, "rhs"));
 677       return __lhs.base() >= __rhs.base();
 678     }
 679
 680   template<typename _Iterator, typename _Sequence>
 681     inline bool
 682     operator>=(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 683                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 684     _GLIBCXX_NOEXCEPT
 685     {
 686       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 687                             _M_message(__msg_iter_order_bad)
 688                             ._M_iterator(__lhs, "lhs")
 689                             ._M_iterator(__rhs, "rhs"));
 690       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 691                             _M_message(__msg_order_different)
 692                             ._M_iterator(__lhs, "lhs")
 693                             ._M_iterator(__rhs, "rhs"));
 694       return __lhs.base() >= __rhs.base();
 695     }
 696
 697   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 698   // According to the resolution of DR179 not only the various comparison
 699   // operators but also operator- must accept mixed iterator/const_iterator
 700   // parameters.
 701   template<typename _IteratorL, typename _IteratorR, typename _Sequence>
 702     inline typename _Safe_iterator<_IteratorL, _Sequence>::difference_type
 703     operator-(const _Safe_iterator<_IteratorL, _Sequence>& __lhs,
 704               const _Safe_iterator<_IteratorR, _Sequence>& __rhs)
 705     _GLIBCXX_NOEXCEPT
 706     {
 707       _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 708                             _M_message(__msg_distance_bad)
 709                             ._M_iterator(__lhs, "lhs")
 710                             ._M_iterator(__rhs, "rhs"));
 711       _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 712                             _M_message(__msg_distance_different)
 713                             ._M_iterator(__lhs, "lhs")
 714                             ._M_iterator(__rhs, "rhs"));
 715       return __lhs.base() - __rhs.base();
 716     }
 717
 718    template<typename _Iterator, typename _Sequence>
 719      inline typename _Safe_iterator<_Iterator, _Sequence>::difference_type
 720      operator-(const _Safe_iterator<_Iterator, _Sequence>& __lhs,
 721                const _Safe_iterator<_Iterator, _Sequence>& __rhs)
 722     _GLIBCXX_NOEXCEPT
 723      {
 724        _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(),
 725                              _M_message(__msg_distance_bad)
 726                              ._M_iterator(__lhs, "lhs")
 727                              ._M_iterator(__rhs, "rhs"));
 728        _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs),
 729                              _M_message(__msg_distance_different)
 730                              ._M_iterator(__lhs, "lhs")
 731                              ._M_iterator(__rhs, "rhs"));
 732        return __lhs.base() - __rhs.base();
 733      }
 734
 735   template<typename _Iterator, typename _Sequence>
 736     inline _Safe_iterator<_Iterator, _Sequence>
 737     operator+(typename _Safe_iterator<_Iterator,_Sequence>::difference_type __n,
 738               const _Safe_iterator<_Iterator, _Sequence>& __i) _GLIBCXX_NOEXCEPT
 739     { return __i + __n; }
 740
 741   /** Safe iterators know if they are dereferenceable. */
 742   template<typename _Iterator, typename _Sequence>
 743     inline bool
 744     __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
 745     { return __x._M_dereferenceable(); }
 746
 747   /** Safe iterators know how to check if they form a valid range. */
 748   template<typename _Iterator, typename _Sequence>
 749     inline bool
 750     __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
 751                   const _Safe_iterator<_Iterator, _Sequence>& __last,
 752                   typename _Distance_traits<_Iterator>::__type& __dist)
 753     { return __first._M_valid_range(__last, __dist); }
 754
 755   /** Safe iterators can help to get better distance knowledge. */
 756   template<typename _Iterator, typename _Sequence>
 757     inline typename _Distance_traits<_Iterator>::__type
 758     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
 759                    const _Safe_iterator<_Iterator, _Sequence>& __last,
 760                    std::random_access_iterator_tag)
 761     { return std::make_pair(__last.base() - __first.base(), __dp_exact); }
 762
 763   template<typename _Iterator, typename _Sequence>
 764     inline typename _Distance_traits<_Iterator>::__type
 765     __get_distance(const _Safe_iterator<_Iterator, _Sequence>& __first,
 766                    const _Safe_iterator<_Iterator, _Sequence>& __last,
 767                    std::input_iterator_tag)
 768     {
 769       typedef typename _Distance_traits<_Iterator>::__type _Diff;
 770       typedef _Sequence_traits<_Sequence> _SeqTraits;
 771
 772       if (__first.base() == __last.base())
 773         return std::make_pair(0, __dp_exact);
 774
 775       if (__first._M_is_before_begin())
 776         {
 777           if (__last._M_is_begin())
 778             return std::make_pair(1, __dp_exact);
 779
 780           return std::make_pair(1, __dp_sign);
 781         }
 782
 783       if (__first._M_is_begin())
 784         {
 785           if (__last._M_is_before_begin())
 786             return std::make_pair(-1, __dp_exact);
 787
 788           if (__last._M_is_end())
 789             return _SeqTraits::_S_size(*__first._M_get_sequence());
 790
 791           return std::make_pair(1, __dp_sign);
 792         }
 793
 794       if (__first._M_is_end())
 795         {
 796           if (__last._M_is_before_begin())
 797             return std::make_pair(-1, __dp_exact);
 798
 799           if (__last._M_is_begin())
 800             {
 801               _Diff __diff = _SeqTraits::_S_size(*__first._M_get_sequence());
 802               return std::make_pair(-__diff.first, __diff.second);
 803             }
 804
 805           return std::make_pair(-1, __dp_sign);
 806         }
 807
 808       if (__last._M_is_before_begin() || __last._M_is_begin())
 809         return std::make_pair(-1, __dp_sign);
 810
 811       if (__last._M_is_end())
 812         return std::make_pair(1, __dp_sign);
 813
 814       return std::make_pair(1, __dp_equality);
 815     }
 816
 817   // Get distance from sequence begin to specified iterator.
 818   template<typename _Iterator, typename _Sequence>
 819     inline typename _Distance_traits<_Iterator>::__type
 820     __get_distance_from_begin(const _Safe_iterator<_Iterator, _Sequence>& __it)
 821     {
 822       typedef _Sequence_traits<_Sequence> _SeqTraits;
 823
 824       // No need to consider before_begin as this function is only used in
 825       // _M_can_advance which won't be used for forward_list iterators.
 826       if (__it._M_is_begin())
 827         return std::make_pair(0, __dp_exact);
 828
 829       if (__it._M_is_end())
 830         return _SeqTraits::_S_size(*__it._M_get_sequence());
 831
 832       typename _Distance_traits<_Iterator>::__type __res
 833         = __get_distance(__it._M_get_sequence()->_M_base().begin(), __it.base());
 834
 835       if (__res.second == __dp_equality)
 836         return std::make_pair(1, __dp_sign);
 837
 838       return __res;
 839     }
 840
 841   // Get distance from specified iterator to sequence end.
 842   template<typename _Iterator, typename _Sequence>
 843     inline typename _Distance_traits<_Iterator>::__type
 844     __get_distance_to_end(const _Safe_iterator<_Iterator, _Sequence>& __it)
 845     {
 846       typedef _Sequence_traits<_Sequence> _SeqTraits;
 847
 848       // No need to consider before_begin as this function is only used in
 849       // _M_can_advance which won't be used for forward_list iterators.
 850       if (__it._M_is_begin())
 851         return _SeqTraits::_S_size(*__it._M_get_sequence());
 852
 853       if (__it._M_is_end())
 854         return std::make_pair(0, __dp_exact);
 855
 856       typename _Distance_traits<_Iterator>::__type __res
 857         = __get_distance(__it.base(), __it._M_get_sequence()->_M_base().end());
 858
 859       if (__res.second == __dp_equality)
 860         return std::make_pair(1, __dp_sign);
 861
 862       return __res;
 863     }
 864
 865 #if __cplusplus < 201103L
 866   template<typename _Iterator, typename _Sequence>
 867     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
 868     : std::__are_same<std::random_access_iterator_tag,
 869                       typename std::iterator_traits<_Iterator>::
 870                       iterator_category>
 871     { };
 872 #else
 873   template<typename _Iterator, typename _Sequence>
 874     _Iterator
 875     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
 876            std::random_access_iterator_tag)
 877     { return __it.base(); }
 878
 879   template<typename _Iterator, typename _Sequence>
 880     const _Safe_iterator<_Iterator, _Sequence>&
 881     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
 882            std::input_iterator_tag)
 883     { return __it; }
 884
 885   template<typename _Iterator, typename _Sequence>
 886     auto
 887     __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
 888     -> decltype(__base(__it, std::__iterator_category(__it)))
 889     { return __base(__it, std::__iterator_category(__it)); }
 890 #endif
 891
 892 #if __cplusplus < 201103L
 893   template<typename _Iterator, typename _Sequence>
 894     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
 895     { typedef _Iterator _Type; };
 896 #endif
 897
 898   template<typename _Iterator, typename _Sequence>
 899     inline _Iterator
 900     __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
 901     { return __it.base(); }
 902
 903 } // namespace __gnu_debug
 904
 905 #include <debug/safe_iterator.tcc>
 906
 907 #endif