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