1// Safe iterator implementation -*- C++ -*-
2
3// Copyright (C) 2003-2026 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>
88 struct _BeforeBeginHelper
89 {
90 template<typename _Iterator, typename _Category>
91 static bool
92 _S_Is(const _Safe_iterator<_Iterator, _Sequence, _Category>&)
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>
103 struct _Sequence_traits
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
129 = typename std::iterator_traits<_Iterator>::iterator_category>
130 class _Safe_iterator
131 : private _Iterator,
132 public _Safe_iterator_base
133 {
134 typedef _Iterator _Iter_base;
135 typedef _Safe_iterator_base _Safe_base;
136
137 typedef std::iterator_traits<_Iterator> _Traits;
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(seq: __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(seq: __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
213 _Safe_iterator(_Safe_iterator&& __x) noexcept
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 const _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
240 _Safe_iterator(
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(seq: __x._M_sequence);
259 }
260
261 /**
262 * @brief Copy assignment.
263 */
264 _GLIBCXX20_CONSTEXPR
265 _Safe_iterator&
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 {
284 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
285 base() = __x.base();
286 _M_version = __x._M_sequence->_M_version;
287 } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
288 else
289 {
290 _M_detach();
291 base() = __x.base();
292 _M_attach(seq: __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
304 _Safe_iterator&
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 {
324 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
325 base() = __x.base();
326 _M_version = __x._M_sequence->_M_version;
327 } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
328 else
329 {
330 _M_detach();
331 base() = __x.base();
332 _M_attach(seq: __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
383 _Safe_iterator&
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 {
396 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
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
407 _Safe_iterator
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
425 _S_constant()
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
448 _M_attach(const _Safe_sequence_base* __seq)
449 { _Safe_base::_M_attach(__seq, _S_constant()); }
450
451 /** Likewise, but not thread-safe. */
452 void
453 _M_attach_single(const _Safe_sequence_base* __seq)
454 { _Safe_base::_M_attach_single(__seq, _S_constant()); }
455
456 /// Is the iterator dereferenceable?
457 bool
458 _M_dereferenceable() const
459 { return !this->_M_singular() && !_M_is_end() && !_M_is_before_begin(); }
460
461 /// Is the iterator before a dereferenceable one?
462 bool
463 _M_before_dereferenceable() const
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
475 _M_incrementable() const
476 { return !this->_M_singular() && !_M_is_end(); }
477
478 /// Is the iterator value-initialized?
479 bool
480 _M_value_initialized() const
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,
496 std::pair<difference_type, _Distance_precision>& __dist,
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 {
504 // Looks like not const-correct, but if _IsConstant the constness
505 // is restored when returning the sequence pointer and if not
506 // _IsConstant we are allowed to remove constness.
507 return static_cast<_Sequence*>
508 (const_cast<_Safe_sequence_base*>(_M_sequence));
509 }
510
511 // Get distance to __rhs.
512 typename _Distance_traits<_Iterator>::__type
513 _M_get_distance_to(const _Safe_iterator& __rhs) const;
514
515 // Get distance from sequence begin up to *this.
516 typename _Distance_traits<_Iterator>::__type
517 _M_get_distance_from_begin() const;
518
519 // Get distance from *this to sequence end.
520 typename _Distance_traits<_Iterator>::__type
521 _M_get_distance_to_end() const;
522
523 /// Is this iterator equal to the sequence's begin() iterator?
524 _GLIBCXX20_CONSTEXPR
525 bool
526 _M_is_begin() const
527 { return base() == _M_get_sequence()->_M_base().begin(); }
528
529 /// Is this iterator equal to the sequence's end() iterator?
530 bool
531 _M_is_end() const
532 { return base() == _M_get_sequence()->_M_base().end(); }
533
534 /// Is this iterator equal to the sequence's before_begin() iterator if
535 /// any?
536 bool
537 _M_is_before_begin() const
538 { return _BeforeBeginHelper<_Sequence>::_S_Is(*this); }
539
540 /// Is this iterator equal to the sequence's before_begin() iterator if
541 /// any or begin() otherwise?
542 bool
543 _M_is_beginnest() const
544 { return _BeforeBeginHelper<_Sequence>::_S_Is_Beginnest(*this); }
545
546 // ------ Operators ------
547
548 typedef _Safe_iterator<_Iterator, _Sequence, iterator_category> _Self;
549
550 _GLIBCXX_NODISCARD
551 _GLIBCXX20_CONSTEXPR
552 friend bool
553 operator==(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
554 {
555 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
556 return __lhs.base() == __rhs.base();
557 }
558
559 template<typename _IteR>
560 _GLIBCXX_NODISCARD
561 _GLIBCXX20_CONSTEXPR
562 friend bool
563 operator==(const _Self& __lhs,
564 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
565 _GLIBCXX_NOEXCEPT
566 {
567 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
568 return __lhs.base() == __rhs.base();
569 }
570
571#if ! __cpp_lib_three_way_comparison
572 _GLIBCXX_NODISCARD
573 friend bool
574 operator!=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
575 {
576 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
577 return __lhs.base() != __rhs.base();
578 }
579
580 template<typename _IteR>
581 _GLIBCXX_NODISCARD
582 friend bool
583 operator!=(const _Self& __lhs,
584 const _Safe_iterator<_IteR, _Sequence, iterator_category>& __rhs)
585 _GLIBCXX_NOEXCEPT
586 {
587 _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS(__lhs, __rhs);
588 return __lhs.base() != __rhs.base();
589 }
590#endif // three-way comparison
591 };
592
593 template<typename _Iterator, typename _Sequence>
594 class _Safe_iterator<_Iterator, _Sequence, std::bidirectional_iterator_tag>
595 : public _Safe_iterator<_Iterator, _Sequence, std::forward_iterator_tag>
596 {
597 typedef _Safe_iterator<_Iterator, _Sequence,
598 std::forward_iterator_tag> _Safe_base;
599
600 protected:
601 typedef typename _Safe_base::_OtherIterator _OtherIterator;
602
603 typedef typename _Safe_base::_Unchecked _Unchecked;
604
605 _GLIBCXX20_CONSTEXPR
606 _Safe_iterator(const _Safe_iterator& __x,
607 _Unchecked __unchecked) _GLIBCXX_NOEXCEPT
608 : _Safe_base(__x, __unchecked)
609 { }
610
611 public:
612 /// @post the iterator is singular and unattached
613 _GLIBCXX20_CONSTEXPR
614 _Safe_iterator() _GLIBCXX_NOEXCEPT { }
615
616 /**
617 * @brief Safe iterator construction from an unsafe iterator and
618 * its sequence.
619 *
620 * @pre @p seq is not NULL
621 * @post this is not singular
622 */
623 _GLIBCXX20_CONSTEXPR
624 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
625 _GLIBCXX_NOEXCEPT
626 : _Safe_base(__i, __seq)
627 { }
628
629 /**
630 * @brief Copy construction.
631 */
632 _GLIBCXX20_CONSTEXPR
633 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
634 : _Safe_base(__x)
635 { }
636
637#if __cplusplus >= 201103L
638 /** @brief Move construction. */
639 _GLIBCXX20_CONSTEXPR
640 _Safe_iterator(_Safe_iterator&&) = default;
641#endif
642
643 /**
644 * @brief Converting constructor from a mutable iterator to a
645 * constant iterator.
646 */
647 template<typename _MutableIterator>
648 _GLIBCXX20_CONSTEXPR
649 _Safe_iterator(
650 const _Safe_iterator<_MutableIterator, _Sequence,
651 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
652 std::__are_same<_MutableIterator, _OtherIterator>::__value,
653 std::bidirectional_iterator_tag>::__type>& __x)
654 _GLIBCXX_NOEXCEPT
655 : _Safe_base(__x)
656 { }
657
658#if __cplusplus >= 201103L
659 /** @brief Copy assignment. */
660 _Safe_iterator&
661 operator=(const _Safe_iterator&) = default;
662
663 /** @brief Move assignment. */
664 _Safe_iterator&
665 operator=(_Safe_iterator&&) = default;
666#else
667 /** @brief Copy assignment. */
668 _Safe_iterator&
669 operator=(const _Safe_iterator& __x)
670 {
671 _Safe_base::operator=(__x);
672 return *this;
673 }
674#endif
675
676 // ------ Input iterator requirements ------
677 /**
678 * @brief Iterator preincrement
679 * @pre iterator is incrementable
680 */
681 _GLIBCXX20_CONSTEXPR
682 _Safe_iterator&
683 operator++() _GLIBCXX_NOEXCEPT
684 {
685 _Safe_base::operator++();
686 return *this;
687 }
688
689 /**
690 * @brief Iterator postincrement
691 * @pre iterator is incrementable
692 */
693 _Safe_iterator
694 operator++(int) _GLIBCXX_NOEXCEPT
695 {
696 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
697 _M_message(__msg_bad_inc)
698 ._M_iterator(*this, "this"));
699 _Safe_iterator __ret(*this, _Unchecked());
700 ++*this;
701 return __ret;
702 }
703
704 // ------ Bidirectional iterator requirements ------
705 /**
706 * @brief Iterator predecrement
707 * @pre iterator is decrementable
708 */
709 _GLIBCXX20_CONSTEXPR
710 _Safe_iterator&
711 operator--() _GLIBCXX_NOEXCEPT
712 {
713 if (std::__is_constant_evaluated())
714 {
715 --this->base();
716 return *this;
717 }
718
719 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
720 _M_message(__msg_bad_dec)
721 ._M_iterator(*this, "this"));
722 _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
723 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
724 --this->base();
725 } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
726 return *this;
727 }
728
729 /**
730 * @brief Iterator postdecrement
731 * @pre iterator is decrementable
732 */
733 _Safe_iterator
734 operator--(int) _GLIBCXX_NOEXCEPT
735 {
736 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
737 _M_message(__msg_bad_dec)
738 ._M_iterator(*this, "this"));
739 _Safe_iterator __ret(*this, _Unchecked());
740 --*this;
741 return __ret;
742 }
743
744 // ------ Utilities ------
745
746 // Is the iterator decrementable?
747 bool
748 _M_decrementable() const
749 { return !this->_M_singular() && !this->_M_is_begin(); }
750 };
751
752 template<typename _Iterator, typename _Sequence>
753 class _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>
754 : public _Safe_iterator<_Iterator, _Sequence,
755 std::bidirectional_iterator_tag>
756 {
757 typedef _Safe_iterator<_Iterator, _Sequence,
758 std::bidirectional_iterator_tag> _Safe_base;
759 typedef typename _Safe_base::_OtherIterator _OtherIterator;
760
761 typedef typename _Safe_base::_Self _Self;
762 typedef _Safe_iterator<_OtherIterator, _Sequence,
763 std::random_access_iterator_tag> _OtherSelf;
764
765 typedef typename _Safe_base::_Unchecked _Unchecked;
766
767 _GLIBCXX20_CONSTEXPR
768 _Safe_iterator(const _Safe_iterator& __x,
769 _Unchecked __unchecked) _GLIBCXX_NOEXCEPT
770 : _Safe_base(__x, __unchecked)
771 { }
772
773 public:
774 typedef typename _Safe_base::difference_type difference_type;
775 typedef typename _Safe_base::reference reference;
776
777 /// @post the iterator is singular and unattached
778 _GLIBCXX20_CONSTEXPR
779 _Safe_iterator() _GLIBCXX_NOEXCEPT { }
780
781 /**
782 * @brief Safe iterator construction from an unsafe iterator and
783 * its sequence.
784 *
785 * @pre @p seq is not NULL
786 * @post this is not singular
787 */
788 _GLIBCXX20_CONSTEXPR
789 _Safe_iterator(_Iterator __i, const _Safe_sequence_base* __seq)
790 _GLIBCXX_NOEXCEPT
791 : _Safe_base(__i, __seq)
792 { }
793
794 /**
795 * @brief Copy construction.
796 */
797 _GLIBCXX20_CONSTEXPR
798 _Safe_iterator(const _Safe_iterator& __x) _GLIBCXX_NOEXCEPT
799 : _Safe_base(__x)
800 { }
801
802#if __cplusplus >= 201103L
803 /** @brief Move construction. */
804 _Safe_iterator(_Safe_iterator&&) = default;
805#endif
806
807 /**
808 * @brief Converting constructor from a mutable iterator to a
809 * constant iterator.
810 */
811 template<typename _MutableIterator>
812 _GLIBCXX20_CONSTEXPR
813 _Safe_iterator(
814 const _Safe_iterator<_MutableIterator, _Sequence,
815 typename __gnu_cxx::__enable_if<_Safe_base::_IsConstant::__value &&
816 std::__are_same<_MutableIterator, _OtherIterator>::__value,
817 std::random_access_iterator_tag>::__type>& __x)
818 _GLIBCXX_NOEXCEPT
819 : _Safe_base(__x)
820 { }
821
822#if __cplusplus >= 201103L
823 /** @brief Copy assignment. */
824 _Safe_iterator&
825 operator=(const _Safe_iterator&) = default;
826
827 /** @brief Move assignment. */
828 _Safe_iterator&
829 operator=(_Safe_iterator&&) = default;
830#else
831 /** @brief Copy assignment. */
832 _Safe_iterator&
833 operator=(const _Safe_iterator& __x)
834 {
835 _Safe_base::operator=(__x);
836 return *this;
837 }
838#endif
839
840 // Is the iterator range [*this, __rhs) valid?
841 bool
842 _M_valid_range(const _Safe_iterator& __rhs,
843 std::pair<difference_type,
844 _Distance_precision>& __dist) const;
845
846 // ------ Input iterator requirements ------
847 /**
848 * @brief Iterator preincrement
849 * @pre iterator is incrementable
850 */
851 _GLIBCXX20_CONSTEXPR
852 _Safe_iterator&
853 operator++() _GLIBCXX_NOEXCEPT
854 {
855 _Safe_base::operator++();
856 return *this;
857 }
858
859 /**
860 * @brief Iterator postincrement
861 * @pre iterator is incrementable
862 */
863 _GLIBCXX20_CONSTEXPR
864 _Safe_iterator
865 operator++(int) _GLIBCXX_NOEXCEPT
866 {
867 if (!std::__is_constant_evaluated())
868 {
869 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
870 _M_message(__msg_bad_inc)
871 ._M_iterator(*this, "this"));
872 }
873 _Safe_iterator __ret(*this, _Unchecked());
874 ++*this;
875 return __ret;
876 }
877
878 // ------ Bidirectional iterator requirements ------
879 /**
880 * @brief Iterator predecrement
881 * @pre iterator is decrementable
882 */
883 _GLIBCXX20_CONSTEXPR
884 _Safe_iterator&
885 operator--() _GLIBCXX_NOEXCEPT
886 {
887 _Safe_base::operator--();
888 return *this;
889 }
890
891 /**
892 * @brief Iterator postdecrement
893 * @pre iterator is decrementable
894 */
895 _GLIBCXX20_CONSTEXPR
896 _Safe_iterator
897 operator--(int) _GLIBCXX_NOEXCEPT
898 {
899 if (!std::__is_constant_evaluated())
900 {
901 _GLIBCXX_DEBUG_VERIFY(this->_M_decrementable(),
902 _M_message(__msg_bad_dec)
903 ._M_iterator(*this, "this"));
904 }
905 _Safe_iterator __ret(*this, _Unchecked());
906 --*this;
907 return __ret;
908 }
909
910 // ------ Random access iterator requirements ------
911 _GLIBCXX_NODISCARD
912 _GLIBCXX20_CONSTEXPR
913 reference
914 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
915 {
916 if (!std::__is_constant_evaluated())
917 {
918 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n)
919 && this->_M_can_advance(__n + 1),
920 _M_message(__msg_iter_subscript_oob)
921 ._M_iterator(*this)._M_integer(__n));
922 }
923 return this->base()[__n];
924 }
925
926 _GLIBCXX20_CONSTEXPR
927 _Safe_iterator&
928 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
929 {
930 if (std::__is_constant_evaluated())
931 {
932 this->base() += __n;
933 return *this;
934 }
935
936 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(__n),
937 _M_message(__msg_advance_oob)
938 ._M_iterator(*this)._M_integer(__n));
939 _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
940 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
941 this->base() += __n;
942 } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
943 return *this;
944 }
945
946 _GLIBCXX20_CONSTEXPR
947 _Safe_iterator&
948 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
949 {
950 if (std::__is_constant_evaluated())
951 {
952 this->base() -= __n;
953 return *this;
954 }
955
956 _GLIBCXX_DEBUG_VERIFY(this->_M_can_advance(-__n),
957 _M_message(__msg_retreat_oob)
958 ._M_iterator(*this)._M_integer(__n));
959 _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN {
960 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
961 this->base() -= __n;
962 } _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
963 return *this;
964 }
965
966#if __cpp_lib_three_way_comparison
967 [[nodiscard]]
968 _GLIBCXX20_CONSTEXPR
969 friend auto
970 operator<=>(const _Self& __lhs, const _Self& __rhs) noexcept
971 {
972 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
973 return __lhs.base() <=> __rhs.base();
974 }
975
976 [[nodiscard]]
977 _GLIBCXX20_CONSTEXPR
978 friend auto
979 operator<=>(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
980 {
981 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
982 return __lhs.base() <=> __rhs.base();
983 }
984#else
985 _GLIBCXX_NODISCARD
986 friend bool
987 operator<(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
988 {
989 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
990 return __lhs.base() < __rhs.base();
991 }
992
993 _GLIBCXX_NODISCARD
994 friend bool
995 operator<(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
996 {
997 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
998 return __lhs.base() < __rhs.base();
999 }
1000
1001 _GLIBCXX_NODISCARD
1002 friend bool
1003 operator<=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1004 {
1005 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1006 return __lhs.base() <= __rhs.base();
1007 }
1008
1009 _GLIBCXX_NODISCARD
1010 friend bool
1011 operator<=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1012 {
1013 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1014 return __lhs.base() <= __rhs.base();
1015 }
1016
1017 _GLIBCXX_NODISCARD
1018 friend bool
1019 operator>(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1020 {
1021 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1022 return __lhs.base() > __rhs.base();
1023 }
1024
1025 _GLIBCXX_NODISCARD
1026 friend bool
1027 operator>(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1028 {
1029 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1030 return __lhs.base() > __rhs.base();
1031 }
1032
1033 _GLIBCXX_NODISCARD
1034 friend bool
1035 operator>=(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1036 {
1037 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1038 return __lhs.base() >= __rhs.base();
1039 }
1040
1041 _GLIBCXX_NODISCARD
1042 friend bool
1043 operator>=(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1044 {
1045 _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS(__lhs, __rhs);
1046 return __lhs.base() >= __rhs.base();
1047 }
1048#endif // three-way comparison
1049
1050 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1051 // According to the resolution of DR179 not only the various comparison
1052 // operators but also operator- must accept mixed iterator/const_iterator
1053 // parameters.
1054 _GLIBCXX_NODISCARD
1055 _GLIBCXX20_CONSTEXPR
1056 friend difference_type
1057 operator-(const _Self& __lhs, const _OtherSelf& __rhs) _GLIBCXX_NOEXCEPT
1058 {
1059 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
1060 return __lhs.base() - __rhs.base();
1061 }
1062
1063 _GLIBCXX_NODISCARD
1064 _GLIBCXX20_CONSTEXPR
1065 friend difference_type
1066 operator-(const _Self& __lhs, const _Self& __rhs) _GLIBCXX_NOEXCEPT
1067 {
1068 _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS(__lhs, __rhs);
1069 return __lhs.base() - __rhs.base();
1070 }
1071
1072 _GLIBCXX_NODISCARD
1073 _GLIBCXX20_CONSTEXPR
1074 friend _Self
1075 operator+(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
1076 {
1077 if (!std::__is_constant_evaluated())
1078 {
1079 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
1080 _M_message(__msg_advance_oob)
1081 ._M_iterator(__x)._M_integer(__n));
1082 }
1083 return _Safe_iterator(__x.base() + __n, __x._M_sequence);
1084 }
1085
1086 _GLIBCXX_NODISCARD
1087 _GLIBCXX20_CONSTEXPR
1088 friend _Self
1089 operator+(difference_type __n, const _Self& __x) _GLIBCXX_NOEXCEPT
1090 {
1091 if (!std::__is_constant_evaluated())
1092 {
1093 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(__n),
1094 _M_message(__msg_advance_oob)
1095 ._M_iterator(__x)._M_integer(__n));
1096 }
1097 return _Safe_iterator(__n + __x.base(), __x._M_sequence);
1098 }
1099
1100 _GLIBCXX_NODISCARD
1101 _GLIBCXX20_CONSTEXPR
1102 friend _Self
1103 operator-(const _Self& __x, difference_type __n) _GLIBCXX_NOEXCEPT
1104 {
1105 if (!std::__is_constant_evaluated())
1106 {
1107 _GLIBCXX_DEBUG_VERIFY(__x._M_can_advance(-__n),
1108 _M_message(__msg_retreat_oob)
1109 ._M_iterator(__x)._M_integer(__n));
1110 }
1111 return _Safe_iterator(__x.base() - __n, __x._M_sequence);
1112 }
1113 };
1114
1115 /** Safe iterators know how to check if they form a valid range. */
1116 template<typename _Iterator, typename _Sequence, typename _Category>
1117 _GLIBCXX20_CONSTEXPR
1118 inline bool
1119 __valid_range(const _Safe_iterator<_Iterator, _Sequence,
1120 _Category>& __first,
1121 const _Safe_iterator<_Iterator, _Sequence,
1122 _Category>& __last,
1123 typename _Distance_traits<_Iterator>::__type& __dist)
1124 {
1125 if (std::__is_constant_evaluated())
1126 return true;
1127
1128 return __first._M_valid_range(__last, __dist);
1129 }
1130
1131 template<typename _Iterator, typename _Sequence, typename _Category>
1132 _GLIBCXX20_CONSTEXPR
1133 inline bool
1134 __valid_range(const _Safe_iterator<_Iterator, _Sequence,
1135 _Category>& __first,
1136 const _Safe_iterator<_Iterator, _Sequence,
1137 _Category>& __last)
1138 {
1139 if (std::__is_constant_evaluated())
1140 return true;
1141
1142 typename _Distance_traits<_Iterator>::__type __dist;
1143 return __first._M_valid_range(__last, __dist);
1144 }
1145
1146 template<typename _Iterator, typename _Sequence, typename _Category,
1147 typename _Size>
1148 _GLIBCXX20_CONSTEXPR
1149 inline bool
1150 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
1151 _Size __n)
1152 {
1153 if (std::__is_constant_evaluated())
1154 return true;
1155
1156 return __it._M_can_advance(__n);
1157 }
1158
1159 template<typename _Iterator, typename _Sequence, typename _Category,
1160 typename _Diff>
1161 _GLIBCXX20_CONSTEXPR
1162 inline bool
1163 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
1164 const std::pair<_Diff, _Distance_precision>& __dist,
1165 int __way)
1166 {
1167 if (std::__is_constant_evaluated())
1168 return true;
1169
1170 return __it._M_can_advance(__dist, __way);
1171 }
1172
1173 template<typename _Iterator, typename _Sequence>
1174 _GLIBCXX20_CONSTEXPR _Iterator
1175 __base(const _Safe_iterator<_Iterator, _Sequence,
1176 std::random_access_iterator_tag>& __it)
1177 { return __it.base(); }
1178
1179#if __cplusplus < 201103L
1180 template<typename _Iterator, typename _Sequence>
1181 struct _Unsafe_type<_Safe_iterator<_Iterator, _Sequence> >
1182 { typedef _Iterator _Type; };
1183#endif
1184
1185 template<typename _Iterator, typename _Sequence>
1186 inline _Iterator
1187 __unsafe(const _Safe_iterator<_Iterator, _Sequence>& __it)
1188 { return __it.base(); }
1189
1190} // namespace __gnu_debug
1191
1192#undef _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_END
1193#undef _GLIBCXX20_CONSTEXPR_NON_LITERAL_SCOPE_BEGIN
1194#undef _GLIBCXX_DEBUG_VERIFY_DIST_OPERANDS
1195#undef _GLIBCXX_DEBUG_VERIFY_REL_OPERANDS
1196#undef _GLIBCXX_DEBUG_VERIFY_EQ_OPERANDS
1197#undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
1198
1199#include <debug/safe_iterator.tcc>
1200
1201#endif
1202