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