1// Safe iterator implementation  -*- C++ -*-
2
3// Copyright (C) 2011-2022 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_local_iterator.h
26 *  This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H
30#define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1
31
32#include <debug/safe_unordered_base.h>
33
34#define _GLIBCXX_DEBUG_VERIFY_OPERANDS(_Lhs, _Rhs) \
35  _GLIBCXX_DEBUG_VERIFY(!_Lhs._M_singular() && !_Rhs._M_singular()	\
36			|| (_Lhs.base() == _Iterator{}			\
37			    && _Rhs.base() == _Iterator{}),		\
38			_M_message(__msg_iter_compare_bad)		\
39			._M_iterator(_Lhs, "lhs")			\
40			._M_iterator(_Rhs, "rhs"));			\
41  _GLIBCXX_DEBUG_VERIFY(_Lhs._M_can_compare(_Rhs),			\
42			_M_message(__msg_compare_different)		\
43			._M_iterator(_Lhs, "lhs")			\
44			._M_iterator(_Rhs, "rhs"));			\
45  _GLIBCXX_DEBUG_VERIFY(_Lhs._M_in_same_bucket(_Rhs),			\
46			_M_message(__msg_local_iter_compare_bad)	\
47			._M_iterator(_Lhs, "lhs")			\
48			._M_iterator(_Rhs, "rhs"))
49
50namespace __gnu_debug
51{
52  /** \brief Safe iterator wrapper.
53   *
54   *  The class template %_Safe_local_iterator is a wrapper around an
55   *  iterator that tracks the iterator's movement among sequences and
56   *  checks that operations performed on the "safe" iterator are
57   *  legal. In additional to the basic iterator operations (which are
58   *  validated, and then passed to the underlying iterator),
59   *  %_Safe_local_iterator has member functions for iterator invalidation,
60   *  attaching/detaching the iterator from sequences, and querying
61   *  the iterator's state.
62   */
63  template<typename _Iterator, typename _Sequence>
64    class _Safe_local_iterator
65    : private _Iterator
66    , public _Safe_local_iterator_base
67    {
68      typedef _Iterator _Iter_base;
69      typedef _Safe_local_iterator_base _Safe_base;
70
71      typedef typename _Sequence::size_type size_type;
72
73      typedef std::iterator_traits<_Iterator> _Traits;
74
75      typedef std::__are_same<
76	typename _Sequence::_Base::const_local_iterator,
77	_Iterator> _IsConstant;
78
79      typedef typename __gnu_cxx::__conditional_type<_IsConstant::__value,
80	typename _Sequence::_Base::local_iterator,
81	typename _Sequence::_Base::const_local_iterator>::__type
82      _OtherIterator;
83
84      typedef _Safe_local_iterator _Self;
85      typedef _Safe_local_iterator<_OtherIterator, _Sequence> _OtherSelf;
86
87      struct _Attach_single
88      { };
89
90      _Safe_local_iterator(_Iterator __i, _Safe_sequence_base* __cont,
91			   _Attach_single) noexcept
92      : _Iter_base(__i)
93      { _M_attach_single(__cont); }
94
95    public:
96      typedef _Iterator					iterator_type;
97      typedef typename _Traits::iterator_category	iterator_category;
98      typedef typename _Traits::value_type		value_type;
99      typedef typename _Traits::difference_type		difference_type;
100      typedef typename _Traits::reference		reference;
101      typedef typename _Traits::pointer			pointer;
102
103      /// @post the iterator is singular and unattached
104      _Safe_local_iterator() noexcept : _Iter_base() { }
105
106      /**
107       * @brief Safe iterator construction from an unsafe iterator and
108       * its sequence.
109       *
110       * @pre @p seq is not NULL
111       * @post this is not singular
112       */
113      _Safe_local_iterator(_Iterator __i, const _Safe_sequence_base* __cont)
114      : _Iter_base(__i), _Safe_base(__cont, _S_constant())
115      {
116	_GLIBCXX_DEBUG_VERIFY(!this->_M_singular(),
117			      _M_message(__msg_init_singular)
118			      ._M_iterator(*this, "this"));
119      }
120
121      /**
122       * @brief Copy construction.
123       */
124      _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept
125      : _Iter_base(__x.base())
126      {
127	// _GLIBCXX_RESOLVE_LIB_DEFECTS
128	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
129	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
130			      || __x.base() == _Iterator(),
131			      _M_message(__msg_init_copy_singular)
132			      ._M_iterator(*this, "this")
133			      ._M_iterator(__x, "other"));
134	_M_attach(__x._M_sequence);
135      }
136
137      /**
138       * @brief Move construction.
139       * @post __x is singular and unattached
140       */
141      _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept
142      : _Iter_base()
143      {
144	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
145			      || __x.base() == _Iterator(),
146			      _M_message(__msg_init_copy_singular)
147			      ._M_iterator(*this, "this")
148			      ._M_iterator(__x, "other"));
149	auto __cont = __x._M_sequence;
150	__x._M_detach();
151	std::swap(base(), __x.base());
152	_M_attach(__cont);
153      }
154
155      /**
156       *  @brief Converting constructor from a mutable iterator to a
157       *  constant iterator.
158      */
159      template<typename _MutableIterator>
160	_Safe_local_iterator(
161	  const _Safe_local_iterator<_MutableIterator,
162	  typename __gnu_cxx::__enable_if<_IsConstant::__value &&
163	    std::__are_same<_MutableIterator, _OtherIterator>::__value,
164					  _Sequence>::__type>& __x) noexcept
165	: _Iter_base(__x.base())
166	{
167	  // _GLIBCXX_RESOLVE_LIB_DEFECTS
168	  // DR 408. Is vector<reverse_iterator<char*> > forbidden?
169	  _GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
170				|| __x.base() == _MutableIterator(),
171				_M_message(__msg_init_const_singular)
172				._M_iterator(*this, "this")
173				._M_iterator(__x, "other"));
174	  _M_attach(__x._M_sequence);
175	}
176
177      /**
178       * @brief Copy assignment.
179       */
180      _Safe_local_iterator&
181      operator=(const _Safe_local_iterator& __x)
182      {
183	// _GLIBCXX_RESOLVE_LIB_DEFECTS
184	// DR 408. Is vector<reverse_iterator<char*> > forbidden?
185	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
186			      || __x.base() == _Iterator(),
187			      _M_message(__msg_copy_singular)
188			      ._M_iterator(*this, "this")
189			      ._M_iterator(__x, "other"));
190
191	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
192	  {
193	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
194	    base() = __x.base();
195	    _M_version = __x._M_sequence->_M_version;
196	  }
197	else
198	  {
199	    _M_detach();
200	    base() = __x.base();
201	    _M_attach(__x._M_sequence);
202	  }
203
204	return *this;
205      }
206
207      /**
208       * @brief Move assignment.
209       * @post __x is singular and unattached
210       */
211      _Safe_local_iterator&
212      operator=(_Safe_local_iterator&& __x) noexcept
213      {
214	_GLIBCXX_DEBUG_VERIFY(!__x._M_singular()
215			      || __x.base() == _Iterator(),
216			      _M_message(__msg_copy_singular)
217			      ._M_iterator(*this, "this")
218			      ._M_iterator(__x, "other"));
219
220	if (std::__addressof(__x) == this)
221	  return *this;
222
223	if (this->_M_sequence && this->_M_sequence == __x._M_sequence)
224	  {
225	    __gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
226	    base() = __x.base();
227	    _M_version = __x._M_sequence->_M_version;
228	  }
229	else
230	  {
231	    _M_detach();
232	    base() = __x.base();
233	    _M_attach(__x._M_sequence);
234	  }
235
236	__x._M_detach();
237	__x.base() = _Iterator();
238	return *this;
239      }
240
241      /**
242       *  @brief Iterator dereference.
243       *  @pre iterator is dereferenceable
244       */
245      reference
246      operator*() const
247      {
248	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
249			      _M_message(__msg_bad_deref)
250			      ._M_iterator(*this, "this"));
251	return *base();
252      }
253
254      /**
255       *  @brief Iterator dereference.
256       *  @pre iterator is dereferenceable
257       */
258      pointer
259      operator->() const
260      {
261	_GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(),
262			      _M_message(__msg_bad_deref)
263			      ._M_iterator(*this, "this"));
264	return base().operator->();
265      }
266
267      // ------ Input iterator requirements ------
268      /**
269       *  @brief Iterator preincrement
270       *  @pre iterator is incrementable
271       */
272      _Safe_local_iterator&
273      operator++()
274      {
275	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
276			      _M_message(__msg_bad_inc)
277			      ._M_iterator(*this, "this"));
278	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
279	++base();
280	return *this;
281      }
282
283      /**
284       *  @brief Iterator postincrement
285       *  @pre iterator is incrementable
286       */
287      _Safe_local_iterator
288      operator++(int)
289      {
290	_GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(),
291			      _M_message(__msg_bad_inc)
292			      ._M_iterator(*this, "this"));
293	__gnu_cxx::__scoped_lock __l(this->_M_get_mutex());
294	return _Safe_local_iterator(base()++, this->_M_sequence,
295				    _Attach_single());
296      }
297
298      // ------ Utilities ------
299
300      /// Determine if this is a constant iterator.
301      static constexpr bool
302      _S_constant()
303      { return _IsConstant::__value; }
304
305      /**
306       * @brief Return the underlying iterator
307       */
308      _Iterator&
309      base() noexcept { return *this; }
310
311      const _Iterator&
312      base() const noexcept { return *this; }
313
314      /**
315       * @brief Return the bucket
316       */
317      size_type
318      bucket() const { return base()._M_get_bucket(); }
319
320      /**
321       * @brief Conversion to underlying non-debug iterator to allow
322       * better interaction with non-debug containers.
323       */
324      operator _Iterator() const { return *this; }
325
326      /** Attach iterator to the given sequence. */
327      void
328      _M_attach(_Safe_sequence_base* __seq)
329      { _Safe_base::_M_attach(__seq, _S_constant()); }
330
331      /** Likewise, but not thread-safe. */
332      void
333      _M_attach_single(_Safe_sequence_base* __seq)
334      { _Safe_base::_M_attach_single(__seq, _S_constant()); }
335
336      /// Is the iterator dereferenceable?
337      bool
338      _M_dereferenceable() const
339      { return !this->_M_singular() && !_M_is_end(); }
340
341      /// Is the iterator incrementable?
342      bool
343      _M_incrementable() const
344      { return !this->_M_singular() && !_M_is_end(); }
345
346      // Is the iterator range [*this, __rhs) valid?
347      bool
348      _M_valid_range(const _Safe_local_iterator& __rhs,
349		     std::pair<difference_type,
350			       _Distance_precision>& __dist_info) const;
351
352      // Get distance to __rhs.
353      typename _Distance_traits<_Iterator>::__type
354      _M_get_distance_to(const _Safe_local_iterator& __rhs) const;
355
356      // The sequence this iterator references.
357      typename __gnu_cxx::__conditional_type<
358	_IsConstant::__value, const _Sequence*, _Sequence*>::__type
359      _M_get_sequence() const
360      { return static_cast<_Sequence*>(_M_sequence); }
361
362      /// Is this iterator equal to the sequence's begin(bucket) iterator?
363      bool _M_is_begin() const
364      { return base() == _M_get_sequence()->_M_base().begin(bucket()); }
365
366      /// Is this iterator equal to the sequence's end(bucket) iterator?
367      bool _M_is_end() const
368      { return base() == _M_get_sequence()->_M_base().end(bucket()); }
369
370      /// Is this iterator part of the same bucket as the other one?
371      template<typename _Other>
372	bool
373	_M_in_same_bucket(const _Safe_local_iterator<_Other,
374						     _Sequence>& __other) const
375	{ return bucket() == __other.bucket(); }
376
377      friend inline bool
378      operator==(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
379      {
380	_GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
381	return __lhs.base() == __rhs.base();
382      }
383
384      friend inline bool
385      operator==(const _Self& __lhs, const _Self& __rhs) noexcept
386      {
387	_GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
388	return __lhs.base() == __rhs.base();
389      }
390
391      friend inline bool
392      operator!=(const _Self& __lhs, const _OtherSelf& __rhs) noexcept
393      {
394	_GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
395	return __lhs.base() != __rhs.base();
396      }
397
398      friend inline bool
399      operator!=(const _Self& __lhs, const _Self& __rhs) noexcept
400      {
401	_GLIBCXX_DEBUG_VERIFY_OPERANDS(__lhs, __rhs);
402	return __lhs.base() != __rhs.base();
403      }
404    };
405
406  /** Safe local iterators know how to check if they form a valid range. */
407  template<typename _Iterator, typename _Sequence>
408    inline bool
409    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
410		  const _Safe_local_iterator<_Iterator, _Sequence>& __last,
411		  typename _Distance_traits<_Iterator>::__type& __dist_info)
412    { return __first._M_valid_range(__last, __dist_info); }
413
414  template<typename _Iterator, typename _Sequence>
415    inline bool
416    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
417		  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
418    {
419      typename _Distance_traits<_Iterator>::__type __dist_info;
420      return __first._M_valid_range(__last, __dist_info);
421    }
422
423#if __cplusplus < 201103L
424  template<typename _Iterator, typename _Sequence>
425    struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> >
426    { typedef _Iterator _Type; };
427#endif
428
429  template<typename _Iterator, typename _Sequence>
430    inline _Iterator
431    __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it)
432    { return __it.base(); }
433
434} // namespace __gnu_debug
435
436#undef _GLIBCXX_DEBUG_VERIFY_OPERANDS
437
438#include <debug/safe_local_iterator.tcc>
439
440#endif
441