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