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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2003-2018 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       typedef std::iterator_traits<_Iterator> _Traits;
  95
  96       struct _Attach_single
  97       { };
  98
  99       _Safe_iterator(const _Iterator& __i, _Safe_sequence_base* __seq,
 100                      _Attach_single)
 101       _GLIBCXX_NOEXCEPT
 102       : _Iter_base(__i)
 103       { _M_attach_single(__seq); }
 104
 105     public:
 106       typedef _Iterator                                 iterator_type;
 107       typedef typename _Traits::iterator_category       iterator_category;
 108       typedef typename _Traits::value_type              value_type;
 109       typedef typename _Traits::difference_type         difference_type;
 110       typedef typename _Traits::reference               reference;
 111       typedef typename _Traits::pointer                 pointer;
 112
 113       /// @post the iterator is singular and unattached
 114       _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
 115
 116       /**
 117        * @brief Safe iterator construction from an unsafe iterator and
 118        * its sequence.
 119        *
 120        * @pre @p seq is not NULL
 121        * @post this is not singular
 122        */
 123       _Safe_iterator(const _Iterator& __i, const _Safe_sequence_base* __seq)
 124       _GLIBCXX_NOEXCEPT
 125       : _Iter_base(__i), _Safe_base(__seq, _S_constant())
 126       {
 127         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 128                               _M_message(__msg_init_singular)
 129                               ._M_iterator(*this, "this"));
 130       }
 131
 132       /**
 133        * @brief Copy construction.
 134        */
 135       _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 136       : _Iter_base(__x.base())
 137       {
 138         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 139         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 140         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 141                               || __x.base() == _Iterator(),
 142                               _M_message(__msg_init_copy_singular)
 143                               ._M_iterator(*this, "this")
 144                               ._M_iterator(__x, "other"));
 145         _M_attach(__x._M_sequence);
 146       }
 147
 148 #if __cplusplus >= 201103L
 149       /**
 150        * @brief Move construction.
 151        * @post __x is singular and unattached
 152        */
 153       _Safe_iterator(_Safe_iterator&& __x) noexcept
 154       : _Iter_base()
 155       {
 156         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 157                               || __x.base() == _Iterator(),
 158                               _M_message(__msg_init_copy_singular)
 159                               ._M_iterator(*this, "this")
 160                               ._M_iterator(__x, "other"));
 161         _Safe_sequence_base* __seq = __x._M_sequence;
 162         __x._M_detach();
 163         std::swap(base(), __x.base());
 164         _M_attach(__seq);
 165       }
 166 #endif
 167
 168       /**
 169        *  @brief Converting constructor from a mutable iterator to a
 170        *  constant iterator.
 171       */
 172       template<typename _MutableIterator>
 173         _Safe_iterator(
 174           const _Safe_iterator<_MutableIterator,
 175           typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator,
 176                       typename _Sequence::iterator::iterator_type>::__value),
 177                    _Sequence>::__type>& __x) _GLIBCXX_NOEXCEPT
 178         : _Iter_base(__x.base())
 179         {
 180           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 181           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 182           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 183                                 || __x.base() == _MutableIterator(),
 184                                 _M_message(__msg_init_const_singular)
 185                                 ._M_iterator(*this, "this")
 186                                 ._M_iterator(__x, "other"));
 187           _M_attach(__x._M_sequence);
 188         }
 189
 190       /**
 191        * @brief Copy assignment.
 192        */
 193       _Safe_iterator&
 194       operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
 195       {
 196         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 197         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 198         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 199                               || __x.base() == _Iterator(),
 200                               _M_message(__msg_copy_singular)
 201                               ._M_iterator(*this, "this")
 202                               ._M_iterator(__x, "other"));
 203
 204         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 205           {
 206             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 207             base() = __x.base();
 208             _M_version = __x._M_sequence->_M_version;
 209           }
 210         else
 211           {
 212             _M_detach();
 213             base() = __x.base();
 214             _M_attach(__x._M_sequence);
 215           }
 216
 217         return *this;
 218       }
 219
 220 #if __cplusplus >= 201103L
 221       /**
 222        * @brief Move assignment.
 223        * @post __x is singular and unattached
 224        */
 225       _Safe_iterator&
 226       operator=(_Safe_iterator&& __x) noexcept
 227       {
 228         _GLIBCXX_DEBUG_VERIFY(this != &__x,
 229                               _M_message(__msg_self_move_assign)
 230                               ._M_iterator(*this, "this"));
 231         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 232                               || __x.base() == _Iterator(),
 233                               _M_message(__msg_copy_singular)
 234                               ._M_iterator(*this, "this")
 235                               ._M_iterator(__x, "other"));
 236
 237         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 238           {
 239             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 240             base() = __x.base();
 241             _M_version = __x._M_sequence->_M_version;
 242           }
 243         else
 244           {
 245             _M_detach();
 246             base() = __x.base();
 247             _M_attach(__x._M_sequence);
 248           }
 249
 250         __x._M_detach();
 251         __x.base() = _Iterator();
 252         return *this;
 253       }
 254 #endif
 255
 256       /**
 257        *  @brief Iterator dereference.
 258        *  @pre iterator is dereferenceable
 259        */
 260       reference
 261       operator*() const _GLIBCXX_NOEXCEPT
 262       {
 263         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 264                               _M_message(__msg_bad_deref)
 265                               ._M_iterator(*this, "this"));
 266         return *base();
 267       }
 268
 269       /**
 270        *  @brief Iterator dereference.
 271        *  @pre iterator is dereferenceable
 272        */
 273       pointer
 274       operator->() const _GLIBCXX_NOEXCEPT
 275       {
 276         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 277                               _M_message(__msg_bad_deref)
 278                               ._M_iterator(*this, "this"));
 279         return base().operator->();
 280       }
 281
 282       // ------ Input iterator requirements ------
 283       /**
 284        *  @brief Iterator preincrement
 285        *  @pre iterator is incrementable
 286        */
 287       _Safe_iterator&
 288       operator++() _GLIBCXX_NOEXCEPT
 289       {
 290         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 291                               _M_message(__msg_bad_inc)
 292                               ._M_iterator(*this, "this"));
 293         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 294         ++base();
 295         return *this;
 296       }
 297
 298       /**
 299        *  @brief Iterator postincrement
 300        *  @pre iterator is incrementable
 301        */
 302       _Safe_iterator
 303       operator++(int) _GLIBCXX_NOEXCEPT
 304       {
 305         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 306                               _M_message(__msg_bad_inc)
 307                               ._M_iterator(*this, "this"));
 308         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 309         return _Safe_iterator(base()++, this->_M_sequence, _Attach_single());
 310       }
 311
 312       // ------ Bidirectional iterator requirements ------
 313       /**
 314        *  @brief Iterator predecrement
 315        *  @pre iterator is decrementable
 316        */
 317       _Safe_iterator&
 318       operator--() _GLIBCXX_NOEXCEPT
 319       {
 320         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 321                               _M_message(__msg_bad_dec)
 322                               ._M_iterator(*this, "this"));
 323         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 324         --base();
 325         return *this;
 326       }
 327
 328       /**
 329        *  @brief Iterator postdecrement
 330        *  @pre iterator is decrementable
 331        */
 332       _Safe_iterator
 333       operator--(int) _GLIBCXX_NOEXCEPT
 334       {
 335         _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
 336                               _M_message(__msg_bad_dec)
 337                               ._M_iterator(*this, "this"));
 338         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 339         return _Safe_iterator(base()--, this->_M_sequence, _Attach_single());
 340       }
 341
 342       // ------ Random access iterator requirements ------
 343       reference
 344       operator[](const difference_type& __n) const _GLIBCXX_NOEXCEPT
 345       {
 346         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
 347                               && this->_M_can_advance(__n+1),
 348                               _M_message(__msg_iter_subscript_oob)
 349                               ._M_iterator(*this)._M_integer(__n));
 350         return base()[__n];
 351       }
 352
 353       _Safe_iterator&
 354       operator+=(const difference_type& __n) _GLIBCXX_NOEXCEPT
 355       {
 356         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 357                               _M_message(__msg_advance_oob)
 358                               ._M_iterator(*this)._M_integer(__n));
 359         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 360         base() += __n;
 361         return *this;
 362       }
 363
 364       _Safe_iterator
 365       operator+(const difference_type& __n) const _GLIBCXX_NOEXCEPT
 366       {
 367         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
 368                               _M_message(__msg_advance_oob)
 369                               ._M_iterator(*this)._M_integer(__n));
 370         return _Safe_iterator(base() + __n, this->_M_sequence);
 371       }
 372
 373       _Safe_iterator&
 374       operator-=(const difference_type& __n) _GLIBCXX_NOEXCEPT
 375       {
 376         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 377                               _M_message(__msg_retreat_oob)
 378                               ._M_iterator(*this)._M_integer(__n));
 379         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 380         base() -= __n;
 381         return *this;
 382       }
 383
 384       _Safe_iterator
 385       operator-(const difference_type& __n) const _GLIBCXX_NOEXCEPT
 386       {
 387         _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
 388                               _M_message(__msg_retreat_oob)
 389                               ._M_iterator(*this)._M_integer(__n));
 390         return _Safe_iterator(base() - __n, this->_M_sequence);
 391       }
 392
 393       // ------ Utilities ------
 394
 395       /// Determine if this is a constant iterator.
 396       static bool
 397       _S_constant()
 398       { return std::__are_same<_Const_iterator, _Safe_iterator>::__value; }
 399
 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, _S_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, _S_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   template<typename _Iterator, typename _Sequence, typename _Size>
 866     inline bool
 867     __can_advance(const _Safe_iterator<_Iterator, _Sequence>& __it, _Size __n)
 868     { return __it._M_can_advance(__n); }
 869
 870 #if __cplusplus < 201103L
 871   template<typename _Iterator, typename _Sequence>
 872     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
 873     : std::__are_same<std::random_access_iterator_tag,
 874                       typename std::iterator_traits<_Iterator>::
 875                       iterator_category>
 876     { };
 877 #else
 878   template<typename _Iterator, typename _Sequence>
 879     _Iterator
 880     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
 881            std::random_access_iterator_tag)
 882     { return __it.base(); }
 883
 884   template<typename _Iterator, typename _Sequence>
 885     const _Safe_iterator<_Iterator, _Sequence>&
 886     __base(const _Safe_iterator<_Iterator, _Sequence>& __it,
 887            std::input_iterator_tag)
 888     { return __it; }
 889
 890   template<typename _Iterator, typename _Sequence>
 891     auto
 892     __base(const _Safe_iterator<_Iterator, _Sequence>& __it)
 893     -> decltype(__base(__it, std::__iterator_category(__it)))
 894     { return __base(__it, std::__iterator_category(__it)); }
 895 #endif
 896
 897 #if __cplusplus < 201103L
 898   template<typename _Iterator, typename _Sequence>
 899     struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
 900     { typedef _Iterator _Type; };
 901 #endif
 902
 903   template<typename _Iterator, typename _Sequence>
 904     inline _Iterator
 905     __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
 906     { return __it.base(); }
 907
 908 } // namespace __gnu_debug
 909
 910 #include <debug/safe_iterator.tcc>
 911
 912 #endif