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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2021 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_local_iterator.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
  30 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
  31
  32 #include <debug/safe_unordered_base.h>
  33
  34 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \
  35   _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular()      \
  36                         || (_Lhs.base() == _Iterator{}                  \
  37                             && _Rhs.base() == _Iterator{}),             \
  38                         _M_message(__msg_iter_compare_bad)              \
  39                         ._M_iterator(_Lhs, "lhs")                       \
  40                         ._M_iterator(_Rhs, "rhs"));                     \
  41   _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs),                      \
  42                         _M_message(__msg_compare_different)             \
  43                         ._M_iterator(_Lhs, "lhs")                       \
  44                         ._M_iterator(_Rhs, "rhs"));                     \
  45   _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs),                   \
  46                         _M_message(__msg_local_iter_compare_bad)        \
  47                         ._M_iterator(_Lhs, "lhs")                       \
  48                         ._M_iterator(_Rhs, "rhs"))
  49
  50 namespace __gnu_debug
  51 {
  52   /** \brief Safe iterator wrapper.
  53    *
  54    *  The class template %_Safe_local_iterator is a wrapper around an
  55    *  iterator that tracks the iterator's movement among sequences and
  56    *  checks that operations performed on the "safe" iterator are
  57    *  legal. In additional to the basic iterator operations (which are
  58    *  validated, and then passed to the underlying iterator),
  59    *  %_Safe_local_iterator has member functions for iterator invalidation,
  60    *  attaching/detaching the iterator from sequences, and querying
  61    *  the iterator's state.
  62    */
  63   template<typename _Iterator, typename _Sequence>
  64     class _Safe_local_iterator
  65     : private _Iterator
  66     , public _Safe_local_iterator_base
  67     {
  68       typedef _Iterator _Iter_base;
  69       typedef _Safe_local_iterator_base _Safe_base;
  70
  71       typedef typename _Sequence::size_type size_type;
  72
  73       typedef std::iterator_traits<_Iterator> _Traits;
  74
  75       typedef std::__are_same<
  76         typename _Sequence::_Base::const_local_iterator,
  77         _Iterator> _IsConstant;
  78
  79       typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value,
  80         typename _Sequence::_Base::local_iterator,
  81         typename _Sequence::_Base::const_local_iterator>::__type
  82       _OtherIterator;
  83
  84       typedef _Safe_local_iterator _Self;
  85       typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf;
  86
  87       struct _Attach_single
  88       { };
  89
  90       _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont,
  91                            _Attach_single) noexcept
  92       : _Iter_base(__i)
  93       { _M_attach_single(__cont); }
  94
  95     public:
  96       typedef _Iterator                                 iterator_type;
  97       typedef typename _Traits::iterator_category       iterator_category;
  98       typedef typename _Traits::value_type              value_type;
  99       typedef typename _Traits::difference_type         difference_type;
 100       typedef typename _Traits::reference               reference;
 101       typedef typename _Traits::pointer                 pointer;
 102
 103       /// @post the iterator is singular and unattached
 104       _Safe_local_iterator() noexcept : _Iter_base() { }
 105
 106       /**
 107        * @brief Safe iterator construction from an unsafe iterator and
 108        * its sequence.
 109        *
 110        * @pre @p seq is not NULL
 111        * @post this is not singular
 112        */
 113       _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
 114       : _Iter_base(__i), _Safe_base(__cont, _S_constant())
 115       {
 116         _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
 117                               _M_message(__msg_init_singular)
 118                               ._M_iterator(*this, "this"));
 119       }
 120
 121       /**
 122        * @brief Copy construction.
 123        */
 124       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
 125       : _Iter_base(__x.base())
 126       {
 127         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 128         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 129         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 130                               || __x.base() == _Iterator(),
 131                               _M_message(__msg_init_copy_singular)
 132                               ._M_iterator(*this, "this")
 133                               ._M_iterator(__x, "other"));
 134         _M_attach(__x._M_sequence);
 135       }
 136
 137       /**
 138        * @brief Move construction.
 139        * @post __x is singular and unattached
 140        */
 141       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
 142       : _Iter_base()
 143       {
 144         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 145                               || __x.base() == _Iterator(),
 146                               _M_message(__msg_init_copy_singular)
 147                               ._M_iterator(*this, "this")
 148                               ._M_iterator(__x, "other"));
 149         auto __cont = __x._M_sequence;
 150         __x._M_detach();
 151         std::swap(base(), __x.base());
 152         _M_attach(__cont);
 153       }
 154
 155       /**
 156        *  @brief Converting constructor from a mutable iterator to a
 157        *  constant iterator.
 158       */
 159       template<typename _MutableIterator>
 160         _Safe_local_iterator(
 161           const _Safe_local_iterator<_MutableIterator,
 162           typename __gnu_cxx::__enable_if<_IsConstant::__value &&
 163             std::__are_same<_MutableIterator, _OtherIterator>::__value,
 164                                           _Sequence>::__type>& __x) noexcept
 165         : _Iter_base(__x.base())
 166         {
 167           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 168           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 169           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 170                                 || __x.base() == _MutableIterator(),
 171                                 _M_message(__msg_init_const_singular)
 172                                 ._M_iterator(*this, "this")
 173                                 ._M_iterator(__x, "other"));
 174           _M_attach(__x._M_sequence);
 175         }
 176
 177       /**
 178        * @brief Copy assignment.
 179        */
 180       _Safe_local_iterator&
 181       operator=(const _Safe_local_iterator& __x)
 182       {
 183         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 184         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 185         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 186                               || __x.base() == _Iterator(),
 187                               _M_message(__msg_copy_singular)
 188                               ._M_iterator(*this, "this")
 189                               ._M_iterator(__x, "other"));
 190
 191         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 192           {
 193             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 194             base() = __x.base();
 195             _M_version = __x._M_sequence->_M_version;
 196           }
 197         else
 198           {
 199             _M_detach();
 200             base() = __x.base();
 201             _M_attach(__x._M_sequence);
 202           }
 203
 204         return *this;
 205       }
 206
 207       /**
 208        * @brief Move assignment.
 209        * @post __x is singular and unattached
 210        */
 211       _Safe_local_iterator&
 212       operator=(_Safe_local_iterator&& __x) noexcept
 213       {
 214         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 215                               || __x.base() == _Iterator(),
 216                               _M_message(__msg_copy_singular)
 217                               ._M_iterator(*this, "this")
 218                               ._M_iterator(__x, "other"));
 219
 220         if (std::__addressof(__x) == this)
 221           return *this;
 222
 223         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 224           {
 225             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 226             base() = __x.base();
 227             _M_version = __x._M_sequence->_M_version;
 228           }
 229         else
 230           {
 231             _M_detach();
 232             base() = __x.base();
 233             _M_attach(__x._M_sequence);
 234           }
 235
 236         __x._M_detach();
 237         __x.base() = _Iterator();
 238         return *this;
 239       }
 240
 241       /**
 242        *  @brief Iterator dereference.
 243        *  @pre iterator is dereferenceable
 244        */
 245       reference
 246       operator*() const
 247       {
 248         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 249                               _M_message(__msg_bad_deref)
 250                               ._M_iterator(*this, "this"));
 251         return *base();
 252       }
 253
 254       /**
 255        *  @brief Iterator dereference.
 256        *  @pre iterator is dereferenceable
 257        */
 258       pointer
 259       operator->() const
 260       {
 261         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 262                               _M_message(__msg_bad_deref)
 263                               ._M_iterator(*this, "this"));
 264         return base().operator->();
 265       }
 266
 267       // ------ Input iterator requirements ------
 268       /**
 269        *  @brief Iterator preincrement
 270        *  @pre iterator is incrementable
 271        */
 272       _Safe_local_iterator&
 273       operator++()
 274       {
 275         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 276                               _M_message(__msg_bad_inc)
 277                               ._M_iterator(*this, "this"));
 278         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 279         ++base();
 280         return *this;
 281       }
 282
 283       /**
 284        *  @brief Iterator postincrement
 285        *  @pre iterator is incrementable
 286        */
 287       _Safe_local_iterator
 288       operator++(int)
 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         return _Safe_local_iterator(base()++, this->_M_sequence,
 295                                     _Attach_single());
 296       }
 297
 298       // ------ Utilities ------
 299
 300       /// Determine if this is a constant iterator.
 301       static constexpr bool
 302       _S_constant()
 303       { return _IsConstant::__value; }
 304
 305       /**
 306        * @brief Return the underlying iterator
 307        */
 308       _Iterator&
 309       base() noexcept { return *this; }
 310
 311       const _Iterator&
 312       base() const noexcept { return *this; }
 313
 314       /**
 315        * @brief Return the bucket
 316        */
 317       size_type
 318       bucket() const { return base()._M_get_bucket(); }
 319
 320       /**
 321        * @brief Conversion to underlying non-debug iterator to allow
 322        * better interaction with non-debug containers.
 323        */
 324       operator _Iterator() const { return *this; }
 325
 326       /** Attach iterator to the given sequence. */
 327       void
 328       _M_attach(_Safe_sequence_base* __seq)
 329       { _Safe_base::_M_attach(__seq, _S_constant()); }
 330
 331       /** Likewise, but not thread-safe. */
 332       void
 333       _M_attach_single(_Safe_sequence_base* __seq)
 334       { _Safe_base::_M_attach_single(__seq, _S_constant()); }
 335
 336       /// Is the iterator dereferenceable?
 337       bool
 338       _M_dereferenceable() const
 339       { return !this->_M_singular() && !_M_is_end(); }
 340
 341       /// Is the iterator incrementable?
 342       bool
 343       _M_incrementable() const
 344       { return !this->_M_singular() && !_M_is_end(); }
 345
 346       // Is the iterator range [*this, __rhs) valid?
 347       bool
 348       _M_valid_range(const _Safe_local_iterator& __rhs,
 349                      std::pair<difference_type,
 350                                _Distance_precision>& __dist_info) const;
 351
 352       // Get distance to __rhs.
 353       typename _Distance_traits<_Iterator>::__type
 354       _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
 355
 356       // The sequence this iterator references.
 357       typename __gnu_cxx::__conditional_type<
 358         _IsConstant::__value, const _Sequence*, _Sequence*>::__type
 359       _M_get_sequence() const
 360       { return static_cast<_Sequence*>(_M_sequence); }
 361
 362       /// Is this iterator equal to the sequence's begin(bucket) iterator?
 363       bool _M_is_begin() const
 364       { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
 365
 366       /// Is this iterator equal to the sequence's end(bucket) iterator?
 367       bool _M_is_end() const
 368       { return base() == _M_get_sequence()->_M_base().end(bucket()); }
 369
 370       /// Is this iterator part of the same bucket as the other one?
 371       template<typename _Other>
 372         bool
 373         _M_in_same_bucket(const _Safe_local_iterator<_Other,
 374                                                      _Sequence>& __other) const
 375         { return bucket() == __other.bucket(); }
 376
 377       friend inline bool
 378       operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
 379       {
 380         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
 381         return __lhs.base() == __rhs.base();
 382       }
 383
 384       friend inline bool
 385       operator==(const _Self& __lhs, const _Self& __rhs) noexcept
 386       {
 387         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
 388         return __lhs.base() == __rhs.base();
 389       }
 390
 391       friend inline bool
 392       operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
 393       {
 394         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
 395         return __lhs.base() != __rhs.base();
 396       }
 397
 398       friend inline bool
 399       operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
 400       {
 401         _GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
 402         return __lhs.base() != __rhs.base();
 403       }
 404     };
 405
 406   /** Safe local iterators know how to check if they form a valid range. */
 407   template<typename _Iterator, typename _Sequence>
 408     inline bool
 409     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 410                   const _Safe_local_iterator<_Iterator, _Sequence>& __last,
 411                   typename _Distance_traits<_Iterator>::__type& __dist_info)
 412     { return __first._M_valid_range(__last, __dist_info); }
 413
 414   template<typename _Iterator, typename _Sequence>
 415     inline bool
 416     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 417                   const _Safe_local_iterator<_Iterator, _Sequence>& __last)
 418     {
 419       typename _Distance_traits<_Iterator>::__type __dist_info;
 420       return __first._M_valid_range(__last, __dist_info);
 421     }
 422
 423 #if __cplusplus < 201103L
 424   template<typename _Iterator, typename _Sequence>
 425     struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
 426     { typedef _Iterator _Type; };
 427 #endif
 428
 429   template<typename _Iterator, typename _Sequence>
 430     inline _Iterator
 431     __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
 432     { return __it.base(); }
 433
 434 } // namespace __gnu_debug
 435
 436 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
 437
 438 #include <debug/safe_local_iterator.tcc>
 439
 440 #endif