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

   1 // Safe iterator implementation  -*- C++ -*-
   2
   3 // Copyright (C) 2011-2024 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file debug/safe_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._M_value_initialized()                 \
  37                             && _Rhs._M_value_initialized()),            \
  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 _Unchecked { };
  88
  89       _Safe_local_iterator(const _Safe_local_iterator& __x,
  90                            _Unchecked) noexcept
  91       : _Iter_base(__x.base())
  92       { _M_attach(__x._M_sequence); }
  93
  94     public:
  95       typedef _Iterator                                 iterator_type;
  96       typedef typename _Traits::iterator_category       iterator_category;
  97       typedef typename _Traits::value_type              value_type;
  98       typedef typename _Traits::difference_type         difference_type;
  99       typedef typename _Traits::reference               reference;
 100       typedef typename _Traits::pointer                 pointer;
 101
 102       /// @post the iterator is singular and unattached
 103       _Safe_local_iterator() noexcept : _Iter_base() { }
 104
 105       /**
 106        * @brief Safe iterator construction from an unsafe iterator and
 107        * its sequence.
 108        *
 109        * @pre @p seq is not NULL
 110        * @post this is not singular
 111        */
 112       _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
 113       : _Iter_base(__i), _Safe_base(__cont, _S_constant())
 114       { }
 115
 116       /**
 117        * @brief Copy construction.
 118        */
 119       _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
 120       : _Iter_base(__x.base())
 121       {
 122         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 123         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 124         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 125                               || __x._M_value_initialized(),
 126                               _M_message(__msg_init_copy_singular)
 127                               ._M_iterator(*this, "this")
 128                               ._M_iterator(__x, "other"));
 129         _M_attach(__x._M_sequence);
 130       }
 131
 132       /**
 133        * @brief Move construction.
 134        * @post __x is singular and unattached
 135        */
 136       _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
 137       : _Iter_base()
 138       {
 139         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 140                               || __x._M_value_initialized(),
 141                               _M_message(__msg_init_copy_singular)
 142                               ._M_iterator(*this, "this")
 143                               ._M_iterator(__x, "other"));
 144         auto __cont = __x._M_sequence;
 145         __x._M_detach();
 146         std::swap(base(), __x.base());
 147         _M_attach(__cont);
 148       }
 149
 150       /**
 151        *  @brief Converting constructor from a mutable iterator to a
 152        *  constant iterator.
 153       */
 154       template<typename _MutableIterator>
 155         _Safe_local_iterator(
 156           const _Safe_local_iterator<_MutableIterator,
 157           typename __gnu_cxx::__enable_if<_IsConstant::__value &&
 158             std::__are_same<_MutableIterator, _OtherIterator>::__value,
 159                                           _Sequence>::__type>& __x) noexcept
 160         : _Iter_base(__x.base())
 161         {
 162           // _GLIBCXX_RESOLVE_LIB_DEFECTS
 163           // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 164           _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 165                                 || __x._M_value_initialized(),
 166                                 _M_message(__msg_init_const_singular)
 167                                 ._M_iterator(*this, "this")
 168                                 ._M_iterator(__x, "other"));
 169           _M_attach(__x._M_sequence);
 170         }
 171
 172       /**
 173        * @brief Copy assignment.
 174        */
 175       _Safe_local_iterator&
 176       operator=(const _Safe_local_iterator& __x)
 177       {
 178         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 179         // DR 408. Is vector<reverse_iterator<char*> > forbidden?
 180         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 181                               || __x._M_value_initialized(),
 182                               _M_message(__msg_copy_singular)
 183                               ._M_iterator(*this, "this")
 184                               ._M_iterator(__x, "other"));
 185
 186         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 187           {
 188             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 189             base() = __x.base();
 190             _M_version = __x._M_sequence->_M_version;
 191           }
 192         else
 193           {
 194             _M_detach();
 195             base() = __x.base();
 196             _M_attach(__x._M_sequence);
 197           }
 198
 199         return *this;
 200       }
 201
 202       /**
 203        * @brief Move assignment.
 204        * @post __x is singular and unattached
 205        */
 206       _Safe_local_iterator&
 207       operator=(_Safe_local_iterator&& __x) noexcept
 208       {
 209         _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
 210                               || __x._M_value_initialized(),
 211                               _M_message(__msg_copy_singular)
 212                               ._M_iterator(*this, "this")
 213                               ._M_iterator(__x, "other"));
 214
 215         if (std::__addressof(__x) == this)
 216           return *this;
 217
 218         if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
 219           {
 220             __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 221             base() = __x.base();
 222             _M_version = __x._M_sequence->_M_version;
 223           }
 224         else
 225           {
 226             _M_detach();
 227             base() = __x.base();
 228             _M_attach(__x._M_sequence);
 229           }
 230
 231         __x._M_detach();
 232         __x.base() = _Iterator();
 233         return *this;
 234       }
 235
 236       /**
 237        *  @brief Iterator dereference.
 238        *  @pre iterator is dereferenceable
 239        */
 240       reference
 241       operator*() const
 242       {
 243         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 244                               _M_message(__msg_bad_deref)
 245                               ._M_iterator(*this, "this"));
 246         return *base();
 247       }
 248
 249       /**
 250        *  @brief Iterator dereference.
 251        *  @pre iterator is dereferenceable
 252        */
 253       pointer
 254       operator->() const
 255       {
 256         _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
 257                               _M_message(__msg_bad_deref)
 258                               ._M_iterator(*this, "this"));
 259         return base().operator->();
 260       }
 261
 262       // ------ Input iterator requirements ------
 263       /**
 264        *  @brief Iterator preincrement
 265        *  @pre iterator is incrementable
 266        */
 267       _Safe_local_iterator&
 268       operator++()
 269       {
 270         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 271                               _M_message(__msg_bad_inc)
 272                               ._M_iterator(*this, "this"));
 273         __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
 274         ++base();
 275         return *this;
 276       }
 277
 278       /**
 279        *  @brief Iterator postincrement
 280        *  @pre iterator is incrementable
 281        */
 282       _Safe_local_iterator
 283       operator++(int)
 284       {
 285         _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
 286                               _M_message(__msg_bad_inc)
 287                               ._M_iterator(*this, "this"));
 288         _Safe_local_iterator __ret(*this, _Unchecked{});
 289         ++*this;
 290         return __ret;
 291       }
 292
 293       // ------ Utilities ------
 294
 295       /// Determine if this is a constant iterator.
 296       static constexpr bool
 297       _S_constant()
 298       { return _IsConstant::__value; }
 299
 300       /**
 301        * @brief Return the underlying iterator
 302        */
 303       _Iterator&
 304       base() noexcept { return *this; }
 305
 306       const _Iterator&
 307       base() const noexcept { return *this; }
 308
 309       /**
 310        * @brief Return the bucket
 311        */
 312       size_type
 313       bucket() const { return base()._M_get_bucket(); }
 314
 315       /**
 316        * @brief Conversion to underlying non-debug iterator to allow
 317        * better interaction with non-debug containers.
 318        */
 319       operator _Iterator() const { return *this; }
 320
 321       /** Attach iterator to the given sequence. */
 322       void
 323       _M_attach(_Safe_sequence_base* __seq)
 324       { _Safe_base::_M_attach(__seq, _S_constant()); }
 325
 326       /** Likewise, but not thread-safe. */
 327       void
 328       _M_attach_single(_Safe_sequence_base* __seq)
 329       { _Safe_base::_M_attach_single(__seq, _S_constant()); }
 330
 331       /// Is the iterator dereferenceable?
 332       bool
 333       _M_dereferenceable() const
 334       { return !this->_M_singular() && !_M_is_end(); }
 335
 336       /// Is the iterator incrementable?
 337       bool
 338       _M_incrementable() const
 339       { return !this->_M_singular() && !_M_is_end(); }
 340
 341       /// Is the iterator value-initialized?
 342       bool
 343       _M_value_initialized() const
 344       { return _M_version == 0 && base() == _Iter_base{}; }
 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