libstdc++
safe_iterator.h
Go to the documentation of this file.
1 // Safe iterator implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-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_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 #if __cplusplus > 201703L
39 # include <compare>
40 #endif
41 
42 #define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, _BadMsgId, _DiffMsgId) \
43  if (!std::__is_constant_evaluated()) { \
44  _GLIBCXX_DEBUG_VERIFY((!_Lhs._M_singular() && !_Rhs._M_singular()) \
45  || (_Lhs._M_value_initialized() \
46  && _Rhs._M_value_initialized()), \
47  _M_message(_BadMsgId) \
48  ._M_iterator(_Lhs, #_Lhs) \
49  ._M_iterator(_Rhs, #_Rhs)); \
50  _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs), \
51  _M_message(_DiffMsgId) \
52  ._M_iterator(_Lhs, #_Lhs) \
53  ._M_iterator(_Rhs, #_Rhs)); \
54  }
55 
56 #define _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(_Lhs, _Rhs) \
57  _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_compare_bad, \
58  __msg_compare_different)
59 
60 #define _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(_Lhs, _Rhs) \
61  _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_iter_order_bad, \
62  __msg_order_different)
63 
64 #define _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(_Lhs, _Rhs) \
65  _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs, __msg_distance_bad, \
66  __msg_distance_different)
67 
68 // This pair of macros helps with writing valid C++20 constexpr functions that
69 // contain a non-constexpr code path that defines a non-literal variable, which
70 // was otherwise disallowed until P2242R3 for C++23. We use them below around
71 // __gnu_cxx::__scoped_lock variables so that the containing functions are still
72 // considered valid C++20 constexpr functions.
73 
74 #if __cplusplus >= 202002L && __cpp_constexpr < 202110L
75 # define _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN [&]() -> void
76 # define _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END ();
77 #else
78 # define _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN
79 # define _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
80 #endif
81 
82 namespace __gnu_debug
83 {
84  /** Helper struct to deal with sequence offering a before_begin
85  * iterator.
86  **/
87  template<typename _Sequence>
89  {
90  template<typename _Iterator, typename _Category>
91  static bool
93  { return false; }
94 
95  template<typename _Iterator, typename _Category>
96  static bool
97  _S_Is_Beginnest(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it)
98  { return __it.base() == __it._M_get_sequence()->_M_base().begin(); }
99  };
100 
101  /** Sequence traits giving the size of a container if possible. */
102  template<typename _Sequence>
104  {
105  typedef _Distance_traits<typename _Sequence::iterator> _DistTraits;
106 
107  static typename _DistTraits::__type
108  _S_size(const _Sequence& __seq)
109  { return std::make_pair(__seq.size(), __dp_exact); }
110  };
111 
112  /** \brief Safe iterator wrapper.
113  *
114  * The class template %_Safe_iterator is a wrapper around an
115  * iterator that tracks the iterator's movement among sequences and
116  * checks that operations performed on the "safe" iterator are
117  * legal. In additional to the basic iterator operations (which are
118  * validated, and then passed to the underlying iterator),
119  * %_Safe_iterator has member functions for iterator invalidation,
120  * attaching/detaching the iterator from sequences, and querying
121  * the iterator's state.
122  *
123  * Note that _Iterator must be the first base class so that it gets
124  * initialized before the iterator is being attached to the container's list
125  * of iterators and it is being detached before _Iterator get
126  * destroyed. Otherwise it would result in a data race.
127  */
128  template<typename _Iterator, typename _Sequence, typename _Category
131  : private _Iterator,
132  public _Safe_iterator_base
133  {
134  typedef _Iterator _Iter_base;
136 
138 
139  protected:
140  typedef std::__are_same<typename _Sequence::_Base::const_iterator,
141  _Iterator> _IsConstant;
142 
143  typedef typename __gnu_cxx::__conditional_type<
144  _IsConstant::__value,
145  typename _Sequence::_Base::iterator,
146  typename _Sequence::_Base::const_iterator>::__type _OtherIterator;
147 
148  struct _Unchecked { };
149 
150  _GLIBCXX20_CONSTEXPR
151  _Safe_iterator(const _Safe_iterator& __x, _Unchecked) _GLIBCXX_NOEXCEPT
152  : _Iter_base(__x.base()), _Safe_base()
153  {
154  if (!std::__is_constant_evaluated())
155  _M_attach(__x._M_sequence);
156  }
157 
158  public:
159  typedef _Iterator iterator_type;
160  typedef typename _Traits::iterator_category iterator_category;
161  typedef typename _Traits::value_type value_type;
162  typedef typename _Traits::difference_type difference_type;
163  typedef typename _Traits::reference reference;
164  typedef typename _Traits::pointer pointer;
165 
166 #if __cplusplus > 201703L && __cpp_lib_concepts
167  using iterator_concept = std::__detail::__iter_concept<_Iterator>;
168 #endif
169 
170  /// @post the iterator is singular and unattached
171  _GLIBCXX20_CONSTEXPR
172  _Safe_iterator() _GLIBCXX_NOEXCEPT : _Iter_base() { }
173 
174  /**
175  * @brief Safe iterator construction from an unsafe iterator and
176  * its sequence.
177  *
178  * @pre @p seq is not NULL
179  * @post this is not singular
180  */
181  _GLIBCXX20_CONSTEXPR
182  _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
183  _GLIBCXX_NOEXCEPT
184  : _Iter_base(__i), _Safe_base(__seq, _S_constant())
185  { }
186 
187  /**
188  * @brief Copy construction.
189  */
190  _GLIBCXX20_CONSTEXPR
191  _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
192  : _Iter_base(__x.base()), _Safe_base()
193  {
194  if (std::__is_constant_evaluated())
195  return;
196 
197  // _GLIBCXX_RESOLVE_LIB_DEFECTS
198  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
199  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
200  || __x._M_value_initialized(),
201  _M_message(__msg_init_copy_singular)
202  ._M_iterator(*this, "this")
203  ._M_iterator(__x, "other"));
204  _M_attach(__x._M_sequence);
205  }
206 
207 #if __cplusplus >= 201103L
208  /**
209  * @brief Move construction.
210  * @post __x is singular and unattached
211  */
212  _GLIBCXX20_CONSTEXPR
214  : _Iter_base()
215  {
216  if (std::__is_constant_evaluated())
217  {
218  base() = __x.base();
219  return;
220  }
221 
222  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
223  || __x._M_value_initialized(),
224  _M_message(__msg_init_copy_singular)
225  ._M_iterator(*this, "this")
226  ._M_iterator(__x, "other"));
227  _Safe_sequence_base* __seq = __x._M_sequence;
228  __x._M_detach();
229  std::swap(base(), __x.base());
230  _M_attach(__seq);
231  }
232 #endif
233 
234  /**
235  * @brief Converting constructor from a mutable iterator to a
236  * constant iterator.
237  */
238  template<typename _MutableIterator>
239  _GLIBCXX20_CONSTEXPR
241  const _Safe_iterator<_MutableIterator, _Sequence,
242  typename __gnu_cxx::__enable_if<_IsConstant::__value &&
243  std::__are_same<_MutableIterator, _OtherIterator>::__value,
244  _Category>::__type>& __x)
245  _GLIBCXX_NOEXCEPT
246  : _Iter_base(__x.base())
247  {
248  if (std::__is_constant_evaluated())
249  return;
250 
251  // _GLIBCXX_RESOLVE_LIB_DEFECTS
252  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
253  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
254  || __x._M_value_initialized(),
255  _M_message(__msg_init_const_singular)
256  ._M_iterator(*this, "this")
257  ._M_iterator(__x, "other"));
258  _M_attach(__x._M_sequence);
259  }
260 
261  /**
262  * @brief Copy assignment.
263  */
264  _GLIBCXX20_CONSTEXPR
266  operator=(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
267  {
268  if (std::__is_constant_evaluated())
269  {
270  base() = __x.base();
271  return *this;
272  }
273 
274  // _GLIBCXX_RESOLVE_LIB_DEFECTS
275  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
276  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
277  || __x._M_value_initialized(),
278  _M_message(__msg_copy_singular)
279  ._M_iterator(*this, "this")
280  ._M_iterator(__x, "other"));
281 
282  if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
283  _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
285  base() = __x.base();
287  } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
288  else
289  {
290  _M_detach();
291  base() = __x.base();
292  _M_attach(__x._M_sequence);
293  }
294 
295  return *this;
296  }
297 
298 #if __cplusplus >= 201103L
299  /**
300  * @brief Move assignment.
301  * @post __x is singular and unattached
302  */
303  _GLIBCXX20_CONSTEXPR
305  operator=(_Safe_iterator&& __x) noexcept
306  {
307  if (std::__is_constant_evaluated())
308  {
309  base() = __x.base();
310  return *this;
311  }
312 
313  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
314  || __x._M_value_initialized(),
315  _M_message(__msg_copy_singular)
316  ._M_iterator(*this, "this")
317  ._M_iterator(__x, "other"));
318 
319  if (std::__addressof(__x) == this)
320  return *this;
321 
322  if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
323  _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
325  base() = __x.base();
327  } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
328  else
329  {
330  _M_detach();
331  base() = __x.base();
332  _M_attach(__x._M_sequence);
333  }
334 
335  __x._M_detach();
336  __x.base() = _Iterator();
337  return *this;
338  }
339 #endif
340 
341  /**
342  * @brief Iterator dereference.
343  * @pre iterator is dereferenceable
344  */
345  _GLIBCXX_NODISCARD
346  _GLIBCXX20_CONSTEXPR
347  reference
348  operator*() const _GLIBCXX_NOEXCEPT
349  {
350  if (!std::__is_constant_evaluated())
351  {
352  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
353  _M_message(__msg_bad_deref)
354  ._M_iterator(*this, "this"));
355  }
356  return *base();
357  }
358 
359  /**
360  * @brief Iterator dereference.
361  * @pre iterator is dereferenceable
362  */
363  _GLIBCXX_NODISCARD
364  _GLIBCXX20_CONSTEXPR
365  pointer
366  operator->() const _GLIBCXX_NOEXCEPT
367  {
368  if (!std::__is_constant_evaluated())
369  {
370  _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
371  _M_message(__msg_bad_deref)
372  ._M_iterator(*this, "this"));
373  }
374  return base().operator->();
375  }
376 
377  // ------ Input iterator requirements ------
378  /**
379  * @brief Iterator preincrement
380  * @pre iterator is incrementable
381  */
382  _GLIBCXX20_CONSTEXPR
384  operator++() _GLIBCXX_NOEXCEPT
385  {
386  if (std::__is_constant_evaluated())
387  {
388  ++base();
389  return *this;
390  }
391 
392  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
393  _M_message(__msg_bad_inc)
394  ._M_iterator(*this, "this"));
395  _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
397  ++base();
398  } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
399  return *this;
400  }
401 
402  /**
403  * @brief Iterator postincrement
404  * @pre iterator is incrementable
405  */
406  _GLIBCXX20_CONSTEXPR
408  operator++(int) _GLIBCXX_NOEXCEPT
409  {
410  if (!std::__is_constant_evaluated())
411  {
412  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
413  _M_message(__msg_bad_inc)
414  ._M_iterator(*this, "this"));
415  }
416  _Safe_iterator __ret(*this, _Unchecked());
417  ++*this;
418  return __ret;
419  }
420 
421  // ------ Utilities ------
422 
423  /// Determine if this is a constant iterator.
424  static _GLIBCXX_CONSTEXPR bool
426  { return _IsConstant::__value; }
427 
428  /**
429  * @brief Return the underlying iterator
430  */
431  _GLIBCXX20_CONSTEXPR
432  _Iterator&
433  base() _GLIBCXX_NOEXCEPT { return *this; }
434 
435  _GLIBCXX20_CONSTEXPR
436  const _Iterator&
437  base() const _GLIBCXX_NOEXCEPT { return *this; }
438 
439  /**
440  * @brief Conversion to underlying non-debug iterator to allow
441  * better interaction with non-debug containers.
442  */
443  _GLIBCXX20_CONSTEXPR
444  operator _Iterator() const _GLIBCXX_NOEXCEPT { return *this; }
445 
446  /** Attach iterator to the given sequence. */
447  void
449  { _Safe_base::_M_attach(__seq, _S_constant()); }
450 
451  /** Likewise, but not thread-safe. */
452  void
455 
456  /// Is the iterator dereferenceable?
457  bool
459  { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
460 
461  /// Is the iterator before a dereferenceable one?
462  bool
464  {
465  if (this->_M_incrementable())
466  {
467  _Iterator __base = base();
468  return ++__base != _M_get_sequence()->_M_base().end();
469  }
470  return false;
471  }
472 
473  /// Is the iterator incrementable?
474  bool
476  { return !this->_M_singular() && !_M_is_end(); }
477 
478  /// Is the iterator value-initialized?
479  bool
481  { return _M_version == 0 && base() == _Iter_base(); }
482 
483  // Can we advance the iterator @p __n steps (@p __n may be negative)
484  bool
485  _M_can_advance(difference_type __n, bool __strict = false) const;
486 
487  // Can we advance the iterator using @p __dist in @p __way direction.
488  template<typename _Diff>
489  bool
490  _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist,
491  int __way) const;
492 
493  // Is the iterator range [*this, __rhs) valid?
494  bool
495  _M_valid_range(const _Safe_iterator& __rhs,
497  bool __check_dereferenceable = true) const;
498 
499  // The sequence this iterator references.
500  typename __gnu_cxx::__conditional_type<
501  _IsConstant::__value, const _Sequence*, _Sequence*>::__type
502  _M_get_sequence() const
503  { return static_cast<_Sequence*>(_M_sequence); }
504 
505  // Get distance to __rhs.
506  typename _Distance_traits<_Iterator>::__type
507  _M_get_distance_to(const _Safe_iterator& __rhs) const;
508 
509  // Get distance from sequence begin up to *this.
510  typename _Distance_traits<_Iterator>::__type
511  _M_get_distance_from_begin() const;
512 
513  // Get distance from *this to sequence end.
514  typename _Distance_traits<_Iterator>::__type
515  _M_get_distance_to_end() const;
516 
517  /// Is this iterator equal to the sequence's begin() iterator?
518  _GLIBCXX20_CONSTEXPR
519  bool
520  _M_is_begin() const
521  { return base() == _M_get_sequence()->_M_base().begin(); }
522 
523  /// Is this iterator equal to the sequence's end() iterator?
524  bool
525  _M_is_end() const
526  { return base() == _M_get_sequence()->_M_base().end(); }
527 
528  /// Is this iterator equal to the sequence's before_begin() iterator if
529  /// any?
530  bool
532  { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
533 
534  /// Is this iterator equal to the sequence's before_begin() iterator if
535  /// any or begin() otherwise?
536  bool
539 
540  // ------ Operators ------
541 
543 
544  _GLIBCXX_NODISCARD
545  _GLIBCXX20_CONSTEXPR
546  friend bool
547  operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
548  {
549  _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
550  return __lhs.base() == __rhs.base();
551  }
552 
553  template<typename _IteR>
554  _GLIBCXX_NODISCARD
555  _GLIBCXX20_CONSTEXPR
556  friend bool
557  operator==(const _Self& __lhs,
558  const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
559  _GLIBCXX_NOEXCEPT
560  {
561  _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
562  return __lhs.base() == __rhs.base();
563  }
564 
565 #if ! __cpp_lib_three_way_comparison
566  _GLIBCXX_NODISCARD
567  friend bool
568  operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
569  {
570  _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
571  return __lhs.base() != __rhs.base();
572  }
573 
574  template<typename _IteR>
575  _GLIBCXX_NODISCARD
576  friend bool
577  operator!=(const _Self& __lhs,
578  const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
579  _GLIBCXX_NOEXCEPT
580  {
581  _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
582  return __lhs.base() != __rhs.base();
583  }
584 #endif // three-way comparison
585  };
586 
587  template<typename _Iterator, typename _Sequence>
588  class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag>
589  : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag>
590  {
591  typedef _Safe_iterator<_Iterator, _Sequence,
592  std::forward_iterator_tag> _Safe_base;
593 
594  protected:
595  typedef typename _Safe_base::_OtherIterator _OtherIterator;
596 
597  typedef typename _Safe_base::_Unchecked _Unchecked;
598 
599  _GLIBCXX20_CONSTEXPR
600  _Safe_iterator(const _Safe_iterator& __x,
601  _Unchecked __unchecked) _GLIBCXX_NOEXCEPT
602  : _Safe_base(__x, __unchecked)
603  { }
604 
605  public:
606  /// @post the iterator is singular and unattached
607  _GLIBCXX20_CONSTEXPR
608  _Safe_iterator() _GLIBCXX_NOEXCEPT { }
609 
610  /**
611  * @brief Safe iterator construction from an unsafe iterator and
612  * its sequence.
613  *
614  * @pre @p seq is not NULL
615  * @post this is not singular
616  */
617  _GLIBCXX20_CONSTEXPR
618  _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
619  _GLIBCXX_NOEXCEPT
620  : _Safe_base(__i, __seq)
621  { }
622 
623  /**
624  * @brief Copy construction.
625  */
626  _GLIBCXX20_CONSTEXPR
627  _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
628  : _Safe_base(__x)
629  { }
630 
631 #if __cplusplus >= 201103L
632  /** @brief Move construction. */
633  _GLIBCXX20_CONSTEXPR
634  _Safe_iterator(_Safe_iterator&&) = default;
635 #endif
636 
637  /**
638  * @brief Converting constructor from a mutable iterator to a
639  * constant iterator.
640  */
641  template<typename _MutableIterator>
642  _GLIBCXX20_CONSTEXPR
644  const _Safe_iterator<_MutableIterator, _Sequence,
645  typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
646  std::__are_same<_MutableIterator, _OtherIterator>::__value,
647  std::bidirectional_iterator_tag>::__type>& __x)
648  _GLIBCXX_NOEXCEPT
649  : _Safe_base(__x)
650  { }
651 
652 #if __cplusplus >= 201103L
653  /** @brief Copy assignment. */
655  operator=(const _Safe_iterator&) = default;
656 
657  /** @brief Move assignment. */
659  operator=(_Safe_iterator&&) = default;
660 #else
661  /** @brief Copy assignment. */
663  operator=(const _Safe_iterator& __x)
664  {
665  _Safe_base::operator=(__x);
666  return *this;
667  }
668 #endif
669 
670  // ------ Input iterator requirements ------
671  /**
672  * @brief Iterator preincrement
673  * @pre iterator is incrementable
674  */
675  _GLIBCXX20_CONSTEXPR
677  operator++() _GLIBCXX_NOEXCEPT
678  {
679  _Safe_base::operator++();
680  return *this;
681  }
682 
683  /**
684  * @brief Iterator postincrement
685  * @pre iterator is incrementable
686  */
688  operator++(int) _GLIBCXX_NOEXCEPT
689  {
690  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
691  _M_message(__msg_bad_inc)
692  ._M_iterator(*this, "this"));
693  _Safe_iterator __ret(*this, _Unchecked());
694  ++*this;
695  return __ret;
696  }
697 
698  // ------ Bidirectional iterator requirements ------
699  /**
700  * @brief Iterator predecrement
701  * @pre iterator is decrementable
702  */
703  _GLIBCXX20_CONSTEXPR
705  operator--() _GLIBCXX_NOEXCEPT
706  {
707  if (std::__is_constant_evaluated())
708  {
709  --this->base();
710  return *this;
711  }
712 
713  _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
714  _M_message(__msg_bad_dec)
715  ._M_iterator(*this, "this"));
716  _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
718  --this->base();
719  } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
720  return *this;
721  }
722 
723  /**
724  * @brief Iterator postdecrement
725  * @pre iterator is decrementable
726  */
728  operator--(int) _GLIBCXX_NOEXCEPT
729  {
730  _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
731  _M_message(__msg_bad_dec)
732  ._M_iterator(*this, "this"));
733  _Safe_iterator __ret(*this, _Unchecked());
734  --*this;
735  return __ret;
736  }
737 
738  // ------ Utilities ------
739 
740  // Is the iterator decrementable?
741  bool
742  _M_decrementable() const
743  { return !this->_M_singular() && !this->_M_is_begin(); }
744  };
745 
746  template<typename _Iterator, typename _Sequence>
747  class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>
748  : public _Safe_iterator<_Iterator, _Sequence,
749  std::bidirectional_iterator_tag>
750  {
751  typedef _Safe_iterator<_Iterator, _Sequence,
753  typedef typename _Safe_base::_OtherIterator _OtherIterator;
754 
755  typedef typename _Safe_base::_Self _Self;
756  typedef _Safe_iterator<_OtherIterator, _Sequence,
758 
759  typedef typename _Safe_base::_Unchecked _Unchecked;
760 
761  _GLIBCXX20_CONSTEXPR
762  _Safe_iterator(const _Safe_iterator& __x,
763  _Unchecked __unchecked) _GLIBCXX_NOEXCEPT
764  : _Safe_base(__x, __unchecked)
765  { }
766 
767  public:
768  typedef typename _Safe_base::difference_type difference_type;
769  typedef typename _Safe_base::reference reference;
770 
771  /// @post the iterator is singular and unattached
772  _GLIBCXX20_CONSTEXPR
773  _Safe_iterator() _GLIBCXX_NOEXCEPT { }
774 
775  /**
776  * @brief Safe iterator construction from an unsafe iterator and
777  * its sequence.
778  *
779  * @pre @p seq is not NULL
780  * @post this is not singular
781  */
782  _GLIBCXX20_CONSTEXPR
783  _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
784  _GLIBCXX_NOEXCEPT
785  : _Safe_base(__i, __seq)
786  { }
787 
788  /**
789  * @brief Copy construction.
790  */
791  _GLIBCXX20_CONSTEXPR
792  _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
793  : _Safe_base(__x)
794  { }
795 
796 #if __cplusplus >= 201103L
797  /** @brief Move construction. */
798  _Safe_iterator(_Safe_iterator&&) = default;
799 #endif
800 
801  /**
802  * @brief Converting constructor from a mutable iterator to a
803  * constant iterator.
804  */
805  template<typename _MutableIterator>
806  _GLIBCXX20_CONSTEXPR
808  const _Safe_iterator<_MutableIterator, _Sequence,
809  typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
810  std::__are_same<_MutableIterator, _OtherIterator>::__value,
811  std::random_access_iterator_tag>::__type>& __x)
812  _GLIBCXX_NOEXCEPT
813  : _Safe_base(__x)
814  { }
815 
816 #if __cplusplus >= 201103L
817  /** @brief Copy assignment. */
819  operator=(const _Safe_iterator&) = default;
820 
821  /** @brief Move assignment. */
823  operator=(_Safe_iterator&&) = default;
824 #else
825  /** @brief Copy assignment. */
827  operator=(const _Safe_iterator& __x)
828  {
829  _Safe_base::operator=(__x);
830  return *this;
831  }
832 #endif
833 
834  // Is the iterator range [*this, __rhs) valid?
835  bool
836  _M_valid_range(const _Safe_iterator& __rhs,
837  std::pair<difference_type,
838  _Distance_precision>& __dist) const;
839 
840  // ------ Input iterator requirements ------
841  /**
842  * @brief Iterator preincrement
843  * @pre iterator is incrementable
844  */
845  _GLIBCXX20_CONSTEXPR
847  operator++() _GLIBCXX_NOEXCEPT
848  {
849  _Safe_base::operator++();
850  return *this;
851  }
852 
853  /**
854  * @brief Iterator postincrement
855  * @pre iterator is incrementable
856  */
857  _GLIBCXX20_CONSTEXPR
859  operator++(int) _GLIBCXX_NOEXCEPT
860  {
861  if (!std::__is_constant_evaluated())
862  {
863  _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
864  _M_message(__msg_bad_inc)
865  ._M_iterator(*this, "this"));
866  }
867  _Safe_iterator __ret(*this, _Unchecked());
868  ++*this;
869  return __ret;
870  }
871 
872  // ------ Bidirectional iterator requirements ------
873  /**
874  * @brief Iterator predecrement
875  * @pre iterator is decrementable
876  */
877  _GLIBCXX20_CONSTEXPR
879  operator--() _GLIBCXX_NOEXCEPT
880  {
881  _Safe_base::operator--();
882  return *this;
883  }
884 
885  /**
886  * @brief Iterator postdecrement
887  * @pre iterator is decrementable
888  */
889  _GLIBCXX20_CONSTEXPR
891  operator--(int) _GLIBCXX_NOEXCEPT
892  {
893  if (!std::__is_constant_evaluated())
894  {
895  _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
896  _M_message(__msg_bad_dec)
897  ._M_iterator(*this, "this"));
898  }
899  _Safe_iterator __ret(*this, _Unchecked());
900  --*this;
901  return __ret;
902  }
903 
904  // ------ Random access iterator requirements ------
905  _GLIBCXX_NODISCARD
906  _GLIBCXX20_CONSTEXPR
907  reference
908  operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
909  {
910  if (!std::__is_constant_evaluated())
911  {
912  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
913  && this->_M_can_advance(__n + 1),
914  _M_message(__msg_iter_subscript_oob)
915  ._M_iterator(*this)._M_integer(__n));
916  }
917  return this->base()[__n];
918  }
919 
920  _GLIBCXX20_CONSTEXPR
922  operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
923  {
924  if (std::__is_constant_evaluated())
925  {
926  this->base() += __n;
927  return *this;
928  }
929 
930  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
931  _M_message(__msg_advance_oob)
932  ._M_iterator(*this)._M_integer(__n));
933  _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
935  this->base() += __n;
936  } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
937  return *this;
938  }
939 
940  _GLIBCXX20_CONSTEXPR
942  operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
943  {
944  if (std::__is_constant_evaluated())
945  {
946  this->base() -= __n;
947  return *this;
948  }
949 
950  _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
951  _M_message(__msg_retreat_oob)
952  ._M_iterator(*this)._M_integer(__n));
953  _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
955  this->base() -= __n;
956  } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
957  return *this;
958  }
959 
960 #if __cpp_lib_three_way_comparison
961  [[nodiscard]]
962  _GLIBCXX20_CONSTEXPR
963  friend auto
964  operator<=>(const _Self& __lhs, const _Self& __rhs) noexcept
965  {
966  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
967  return __lhs.base() <=> __rhs.base();
968  }
969 
970  [[nodiscard]]
971  _GLIBCXX20_CONSTEXPR
972  friend auto
973  operator<=>(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
974  {
975  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
976  return __lhs.base() <=> __rhs.base();
977  }
978 #else
979  _GLIBCXX_NODISCARD
980  friend bool
981  operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
982  {
983  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
984  return __lhs.base() < __rhs.base();
985  }
986 
987  _GLIBCXX_NODISCARD
988  friend bool
989  operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
990  {
991  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
992  return __lhs.base() < __rhs.base();
993  }
994 
995  _GLIBCXX_NODISCARD
996  friend bool
997  operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
998  {
999  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1000  return __lhs.base() <= __rhs.base();
1001  }
1002 
1003  _GLIBCXX_NODISCARD
1004  friend bool
1005  operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1006  {
1007  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1008  return __lhs.base() <= __rhs.base();
1009  }
1010 
1011  _GLIBCXX_NODISCARD
1012  friend bool
1013  operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1014  {
1015  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1016  return __lhs.base() > __rhs.base();
1017  }
1018 
1019  _GLIBCXX_NODISCARD
1020  friend bool
1021  operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1022  {
1023  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1024  return __lhs.base() > __rhs.base();
1025  }
1026 
1027  _GLIBCXX_NODISCARD
1028  friend bool
1029  operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1030  {
1031  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1032  return __lhs.base() >= __rhs.base();
1033  }
1034 
1035  _GLIBCXX_NODISCARD
1036  friend bool
1037  operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1038  {
1039  _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1040  return __lhs.base() >= __rhs.base();
1041  }
1042 #endif // three-way comparison
1043 
1044  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1045  // According to the resolution of DR179 not only the various comparison
1046  // operators but also operator- must accept mixed iterator/const_iterator
1047  // parameters.
1048  _GLIBCXX_NODISCARD
1049  _GLIBCXX20_CONSTEXPR
1050  friend difference_type
1051  operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1052  {
1053  _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
1054  return __lhs.base() - __rhs.base();
1055  }
1056 
1057  _GLIBCXX_NODISCARD
1058  _GLIBCXX20_CONSTEXPR
1059  friend difference_type
1060  operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1061  {
1062  _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
1063  return __lhs.base() - __rhs.base();
1064  }
1065 
1066  _GLIBCXX_NODISCARD
1067  _GLIBCXX20_CONSTEXPR
1068  friend _Self
1069  operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
1070  {
1071  if (!std::__is_constant_evaluated())
1072  {
1073  _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
1074  _M_message(__msg_advance_oob)
1075  ._M_iterator(__x)._M_integer(__n));
1076  }
1077  return _Safe_iterator(__x.base() + __n, __x._M_sequence);
1078  }
1079 
1080  _GLIBCXX_NODISCARD
1081  _GLIBCXX20_CONSTEXPR
1082  friend _Self
1083  operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
1084  {
1085  if (!std::__is_constant_evaluated())
1086  {
1087  _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
1088  _M_message(__msg_advance_oob)
1089  ._M_iterator(__x)._M_integer(__n));
1090  }
1091  return _Safe_iterator(__n + __x.base(), __x._M_sequence);
1092  }
1093 
1094  _GLIBCXX_NODISCARD
1095  _GLIBCXX20_CONSTEXPR
1096  friend _Self
1097  operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
1098  {
1099  if (!std::__is_constant_evaluated())
1100  {
1101  _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n),
1102  _M_message(__msg_retreat_oob)
1103  ._M_iterator(__x)._M_integer(__n));
1104  }
1105  return _Safe_iterator(__x.base() - __n, __x._M_sequence);
1106  }
1107  };
1108 
1109  /** Safe iterators know how to check if they form a valid range. */
1110  template<typename _Iterator, typename _Sequence, typename _Category>
1111  inline bool
1112  __valid_range(const _Safe_iterator<_Iterator, _Sequence,
1113  _Category>& __first,
1114  const _Safe_iterator<_Iterator, _Sequence,
1115  _Category>& __last,
1116  typename _Distance_traits<_Iterator>::__type& __dist)
1117  { return __first._M_valid_range(__last, __dist); }
1118 
1119  template<typename _Iterator, typename _Sequence, typename _Category>
1120  inline bool
1121  __valid_range(const _Safe_iterator<_Iterator, _Sequence,
1122  _Category>& __first,
1123  const _Safe_iterator<_Iterator, _Sequence,
1124  _Category>& __last)
1125  {
1126  typename _Distance_traits<_Iterator>::__type __dist;
1127  return __first._M_valid_range(__last, __dist);
1128  }
1129 
1130  template<typename _Iterator, typename _Sequence, typename _Category,
1131  typename _Size>
1132  inline bool
1133  __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
1134  _Size __n)
1135  { return __it._M_can_advance(__n); }
1136 
1137  template<typename _Iterator, typename _Sequence, typename _Category,
1138  typename _Diff>
1139  inline bool
1140  __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
1142  int __way)
1143  { return __it._M_can_advance(__dist, __way); }
1144 
1145  template<typename _Iterator, typename _Sequence>
1146  _Iterator
1147  __base(const _Safe_iterator<_Iterator, _Sequence,
1149  { return __it.base(); }
1150 
1151 #if __cplusplus < 201103L
1152  template<typename _Iterator, typename _Sequence>
1153  struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
1154  { typedef _Iterator _Type; };
1155 #endif
1156 
1157  template<typename _Iterator, typename _Sequence>
1158  inline _Iterator
1159  __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
1160  { return __it.base(); }
1161 
1162 } // namespace __gnu_debug
1163 
1164 #if __cplusplus >= 201103L && __cplusplus <= 201703L
1165 namespace std _GLIBCXX_VISIBILITY(default)
1166 {
1167 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1168 
1169  template<typename _Iterator, typename _Container, typename _Sequence>
1170  constexpr auto
1171  __to_address(const __gnu_debug::_Safe_iterator<
1172  __gnu_cxx::__normal_iterator<_Iterator, _Container>,
1173  _Sequence>& __it) noexcept
1174  -> decltype(std::__to_address(__it.base().base()))
1175  { return std::__to_address(__it.base().base()); }
1176 
1177 _GLIBCXX_END_NAMESPACE_VERSION
1178 }
1179 #endif
1180 
1181 #undef _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
1182 #undef _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN
1183 #undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS
1184 #undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS
1185 #undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS
1186 #undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
1187 
1188 #include <debug/safe_iterator.tcc>
1189 
1190 #endif
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:855
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:869
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:822
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition: chrono.h:862
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition: complex:370
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition: complex:340
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:51
ISO C++ entities toplevel namespace is std.
GNU debug classes for public use.
constexpr bool __valid_range(_InputIterator __first, _InputIterator __last, typename _Distance_traits< _InputIterator >::__type &__dist)
constexpr _Iterator __base(_Iterator __it)
Safe iterator wrapper.
bool _M_incrementable() const
Is the iterator incrementable?
constexpr _Safe_iterator & operator=(_Safe_iterator &&__x) noexcept
Move assignment.
bool _M_dereferenceable() const
Is the iterator dereferenceable?
constexpr bool _M_is_begin() const
Is this iterator equal to the sequence's begin() iterator?
constexpr _Iterator & base() noexcept
Return the underlying iterator.
constexpr _Safe_iterator(const _Safe_iterator< _MutableIterator, _Sequence, typename __gnu_cxx::__enable_if< _IsConstant::__value &&std::__are_same< _MutableIterator, _OtherIterator >::__value, _Category >::__type > &__x) noexcept
Converting constructor from a mutable iterator to a constant iterator.
void _M_attach_single(_Safe_sequence_base *__seq)
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
constexpr _Safe_iterator(_Iterator __i, const _Safe_sequence_base *__seq) noexcept
Safe iterator construction from an unsafe iterator and its sequence.
constexpr pointer operator->() const noexcept
Iterator dereference.
constexpr _Safe_iterator(const _Safe_iterator &__x) noexcept
Copy construction.
constexpr reference operator*() const noexcept
Iterator dereference.
constexpr _Safe_iterator() noexcept
constexpr _Safe_iterator & operator=(const _Safe_iterator &__x) noexcept
Copy assignment.
bool _M_is_beginnest() const
Is this iterator equal to the sequence's before_begin() iterator if any or begin() otherwise?
bool _M_value_initialized() const
Is the iterator value-initialized?
constexpr _Safe_iterator & operator++() noexcept
Iterator preincrement.
bool _M_is_end() const
Is this iterator equal to the sequence's end() iterator?
constexpr _Safe_iterator operator++(int) noexcept
Iterator postincrement.
void _M_attach(_Safe_sequence_base *__seq)
bool _M_is_before_begin() const
Is this iterator equal to the sequence's before_begin() iterator if any?
constexpr _Safe_iterator(_Safe_iterator &&__x) noexcept
Move construction.
static constexpr bool _S_constant()
Determine if this is a constant iterator.
Traits class for iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:286
Forward iterators support a superset of input iterator operations.
Bidirectional iterators support a superset of forward iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Basic functionality for a safe iterator.
Definition: safe_base.h:51
_Safe_sequence_base * _M_sequence
Definition: safe_base.h:57
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
__gnu_cxx::__mutex & _M_get_mutex()
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:203
unsigned int _M_version
The container version number. This number may never be 0.
Definition: safe_base.h:214
Scoped lock idiom.
Definition: concurrence.h:229