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
82namespace __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,
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())
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"));
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"));
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();
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();
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
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
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
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
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
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
1165namespace 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 _Iterator & base() noexcept
Return the underlying iterator.
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 _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)
constexpr _Safe_iterator & operator++() noexcept
Iterator preincrement.
bool _M_before_dereferenceable() const
Is the iterator before a dereferenceable one?
constexpr _Safe_iterator & operator=(_Safe_iterator &&__x) noexcept
Move assignment.
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
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?
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.
constexpr _Safe_iterator & operator=(const _Safe_iterator &__x) noexcept
Copy assignment.
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
__gnu_cxx::__mutex & _M_get_mutex()
void _M_attach_single(_Safe_sequence_base *__seq, bool __constant)
void _M_attach(_Safe_sequence_base *__seq, bool __constant)
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.