libstdc++
functions.h
Go to the documentation of this file.
1 // Debugging support implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2015 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/functions.h
26  * This file is a GNU debug extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
30 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
31 
32 #include <bits/c++config.h>
33 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and
34  // _Iter_base
35 #include <bits/cpp_type_traits.h> // for __is_integer
36 #include <bits/move.h> // for __addressof and addressof
37 #include <bits/stl_function.h> // for less
38 #if __cplusplus >= 201103L
39 # include <type_traits> // for is_lvalue_reference and __and_
40 #endif
41 #include <debug/formatter.h>
42 
43 namespace __gnu_debug
44 {
45  template<typename _Iterator, typename _Sequence>
46  class _Safe_iterator;
47 
48  template<typename _Iterator, typename _Sequence>
49  class _Safe_local_iterator;
50 
51  template<typename _Sequence>
52  struct _Insert_range_from_self_is_safe
53  { enum { __value = 0 }; };
54 
55  template<typename _Sequence>
56  struct _Is_contiguous_sequence : std::__false_type { };
57 
58  // An arbitrary iterator pointer is not singular.
59  inline bool
60  __check_singular_aux(const void*) { return false; }
61 
62  // We may have an iterator that derives from _Safe_iterator_base but isn't
63  // a _Safe_iterator.
64  template<typename _Iterator>
65  inline bool
66  __check_singular(const _Iterator& __x)
67  { return __check_singular_aux(&__x); }
68 
69  /** Non-NULL pointers are nonsingular. */
70  template<typename _Tp>
71  inline bool
72  __check_singular(const _Tp* __ptr)
73  { return __ptr == 0; }
74 
75  /** Assume that some arbitrary iterator is dereferenceable, because we
76  can't prove that it isn't. */
77  template<typename _Iterator>
78  inline bool
79  __check_dereferenceable(const _Iterator&)
80  { return true; }
81 
82  /** Non-NULL pointers are dereferenceable. */
83  template<typename _Tp>
84  inline bool
85  __check_dereferenceable(const _Tp* __ptr)
86  { return __ptr; }
87 
88  /** Safe iterators know if they are dereferenceable. */
89  template<typename _Iterator, typename _Sequence>
90  inline bool
92  { return __x._M_dereferenceable(); }
93 
94  /** Safe local iterators know if they are dereferenceable. */
95  template<typename _Iterator, typename _Sequence>
96  inline bool
98  _Sequence>& __x)
99  { return __x._M_dereferenceable(); }
100 
101  /** If the distance between two random access iterators is
102  * nonnegative, assume the range is valid.
103  */
104  template<typename _RandomAccessIterator>
105  inline bool
106  __valid_range_aux2(const _RandomAccessIterator& __first,
107  const _RandomAccessIterator& __last,
109  { return __last - __first >= 0; }
110 
111  /** Can't test for a valid range with input iterators, because
112  * iteration may be destructive. So we just assume that the range
113  * is valid.
114  */
115  template<typename _InputIterator>
116  inline bool
117  __valid_range_aux2(const _InputIterator&, const _InputIterator&,
119  { return true; }
120 
121  /** We say that integral types for a valid range, and defer to other
122  * routines to realize what to do with integral types instead of
123  * iterators.
124  */
125  template<typename _Integral>
126  inline bool
127  __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
128  { return true; }
129 
130  /** We have iterators, so figure out what kind of iterators that are
131  * to see if we can check the range ahead of time.
132  */
133  template<typename _InputIterator>
134  inline bool
135  __valid_range_aux(const _InputIterator& __first,
136  const _InputIterator& __last, std::__false_type)
137  { return __valid_range_aux2(__first, __last,
138  std::__iterator_category(__first)); }
139 
140  /** Don't know what these iterators are, or if they are even
141  * iterators (we may get an integral type for InputIterator), so
142  * see if they are integral and pass them on to the next phase
143  * otherwise.
144  */
145  template<typename _InputIterator>
146  inline bool
147  __valid_range(const _InputIterator& __first, const _InputIterator& __last)
148  {
149  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
150  return __valid_range_aux(__first, __last, _Integral());
151  }
152 
153  /** Safe iterators know how to check if they form a valid range. */
154  template<typename _Iterator, typename _Sequence>
155  inline bool
158  { return __first._M_valid_range(__last); }
159 
160  /** Safe local iterators know how to check if they form a valid range. */
161  template<typename _Iterator, typename _Sequence>
162  inline bool
165  { return __first._M_valid_range(__last); }
166 
167  /* Checks that [first, last) is a valid range, and then returns
168  * __first. This routine is useful when we can't use a separate
169  * assertion statement because, e.g., we are in a constructor.
170  */
171  template<typename _InputIterator>
172  inline _InputIterator
173  __check_valid_range(const _InputIterator& __first,
174  const _InputIterator& __last
175  __attribute__((__unused__)))
176  {
177  __glibcxx_check_valid_range(__first, __last);
178  return __first;
179  }
180 
181  /* Handle the case where __other is a pointer to _Sequence::value_type. */
182  template<typename _Iterator, typename _Sequence>
183  inline bool
184  __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
185  const typename _Sequence::value_type* __other)
186  {
187  typedef const typename _Sequence::value_type* _PointerType;
188  typedef std::less<_PointerType> _Less;
189 #if __cplusplus >= 201103L
190  constexpr _Less __l{};
191 #else
192  const _Less __l = _Less();
193 #endif
194  const _Sequence* __seq = __it._M_get_sequence();
195  const _PointerType __begin = std::__addressof(*__seq->_M_base().begin());
196  const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1));
197 
198  // Check whether __other points within the contiguous storage.
199  return __l(__other, __begin) || __l(__end, __other);
200  }
201 
202  /* Fallback overload for when we can't tell, assume it is valid. */
203  template<typename _Iterator, typename _Sequence>
204  inline bool
205  __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
206  { return true; }
207 
208  /* Handle sequences with contiguous storage */
209  template<typename _Iterator, typename _Sequence, typename _InputIterator>
210  inline bool
211  __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
212  const _InputIterator& __other,
213  const _InputIterator& __other_end,
214  std::__true_type)
215  {
216  if (__other == __other_end)
217  return true; // inserting nothing is safe even if not foreign iters
218  if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end())
219  return true; // can't be self-inserting if self is empty
220  return __foreign_iterator_aux4(__it, std::__addressof(*__other));
221  }
222 
223  /* Handle non-contiguous containers, assume it is valid. */
224  template<typename _Iterator, typename _Sequence, typename _InputIterator>
225  inline bool
226  __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
227  const _InputIterator&, const _InputIterator&,
228  std::__false_type)
229  { return true; }
230 
231  /** Handle debug iterators from the same type of container. */
232  template<typename _Iterator, typename _Sequence, typename _OtherIterator>
233  inline bool
237  { return __it._M_get_sequence() != __other._M_get_sequence(); }
238 
239  /** Handle debug iterators from different types of container. */
240  template<typename _Iterator, typename _Sequence, typename _OtherIterator,
241  typename _OtherSequence>
242  inline bool
246  { return true; }
247 
248  /* Handle non-debug iterators. */
249  template<typename _Iterator, typename _Sequence, typename _InputIterator>
250  inline bool
252  const _InputIterator& __other,
253  const _InputIterator& __other_end)
254  {
255 #if __cplusplus < 201103L
256  typedef _Is_contiguous_sequence<_Sequence> __tag;
257 #else
258  using __lvalref = std::is_lvalue_reference<
259  typename std::iterator_traits<_InputIterator>::reference>;
260  using __contiguous = _Is_contiguous_sequence<_Sequence>;
261  using __tag = typename std::conditional<__lvalref::value, __contiguous,
262  std::__false_type>::type;
263 #endif
264  return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
265  }
266 
267  /* Handle the case where we aren't really inserting a range after all */
268  template<typename _Iterator, typename _Sequence, typename _Integral>
269  inline bool
270  __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
271  _Integral, _Integral,
272  std::__true_type)
273  { return true; }
274 
275  /* Handle all iterators. */
276  template<typename _Iterator, typename _Sequence,
277  typename _InputIterator>
278  inline bool
279  __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
280  _InputIterator __other, _InputIterator __other_end,
281  std::__false_type)
282  {
283  return _Insert_range_from_self_is_safe<_Sequence>::__value
284  || __foreign_iterator_aux2(__it, __other, __other_end);
285  }
286 
287  template<typename _Iterator, typename _Sequence,
288  typename _InputIterator>
289  inline bool
290  __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
291  _InputIterator __other, _InputIterator __other_end)
292  {
293  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
294  return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
295  }
296 
297  /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
298  template<typename _CharT, typename _Integer>
299  inline const _CharT*
300  __check_string(const _CharT* __s,
301  const _Integer& __n __attribute__((__unused__)))
302  {
303 #ifdef _GLIBCXX_DEBUG_PEDANTIC
304  __glibcxx_assert(__s != 0 || __n == 0);
305 #endif
306  return __s;
307  }
308 
309  /** Checks that __s is non-NULL and then returns __s. */
310  template<typename _CharT>
311  inline const _CharT*
312  __check_string(const _CharT* __s)
313  {
314 #ifdef _GLIBCXX_DEBUG_PEDANTIC
315  __glibcxx_assert(__s != 0);
316 #endif
317  return __s;
318  }
319 
320  // Can't check if an input iterator sequence is sorted, because we
321  // can't step through the sequence.
322  template<typename _InputIterator>
323  inline bool
324  __check_sorted_aux(const _InputIterator&, const _InputIterator&,
326  { return true; }
327 
328  // Can verify if a forward iterator sequence is in fact sorted using
329  // std::__is_sorted
330  template<typename _ForwardIterator>
331  inline bool
332  __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
334  {
335  if (__first == __last)
336  return true;
337 
338  _ForwardIterator __next = __first;
339  for (++__next; __next != __last; __first = __next, ++__next)
340  if (*__next < *__first)
341  return false;
342 
343  return true;
344  }
345 
346  // Can't check if an input iterator sequence is sorted, because we can't step
347  // through the sequence.
348  template<typename _InputIterator, typename _Predicate>
349  inline bool
350  __check_sorted_aux(const _InputIterator&, const _InputIterator&,
351  _Predicate, std::input_iterator_tag)
352  { return true; }
353 
354  // Can verify if a forward iterator sequence is in fact sorted using
355  // std::__is_sorted
356  template<typename _ForwardIterator, typename _Predicate>
357  inline bool
358  __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
359  _Predicate __pred, std::forward_iterator_tag)
360  {
361  if (__first == __last)
362  return true;
363 
364  _ForwardIterator __next = __first;
365  for (++__next; __next != __last; __first = __next, ++__next)
366  if (__pred(*__next, *__first))
367  return false;
368 
369  return true;
370  }
371 
372  // Determine if a sequence is sorted.
373  template<typename _InputIterator>
374  inline bool
375  __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
376  {
377  // Verify that the < operator for elements in the sequence is a
378  // StrictWeakOrdering by checking that it is irreflexive.
379  __glibcxx_assert(__first == __last || !(*__first < *__first));
380 
381  return __check_sorted_aux(__first, __last,
382  std::__iterator_category(__first));
383  }
384 
385  template<typename _InputIterator, typename _Predicate>
386  inline bool
387  __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
388  _Predicate __pred)
389  {
390  // Verify that the predicate is StrictWeakOrdering by checking that it
391  // is irreflexive.
392  __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
393 
394  return __check_sorted_aux(__first, __last, __pred,
395  std::__iterator_category(__first));
396  }
397 
398  template<typename _InputIterator>
399  inline bool
400  __check_sorted_set_aux(const _InputIterator& __first,
401  const _InputIterator& __last,
402  std::__true_type)
403  { return __check_sorted(__first, __last); }
404 
405  template<typename _InputIterator>
406  inline bool
407  __check_sorted_set_aux(const _InputIterator&,
408  const _InputIterator&,
409  std::__false_type)
410  { return true; }
411 
412  template<typename _InputIterator, typename _Predicate>
413  inline bool
414  __check_sorted_set_aux(const _InputIterator& __first,
415  const _InputIterator& __last,
416  _Predicate __pred, std::__true_type)
417  { return __check_sorted(__first, __last, __pred); }
418 
419  template<typename _InputIterator, typename _Predicate>
420  inline bool
421  __check_sorted_set_aux(const _InputIterator&,
422  const _InputIterator&, _Predicate,
423  std::__false_type)
424  { return true; }
425 
426  // ... special variant used in std::merge, std::includes, std::set_*.
427  template<typename _InputIterator1, typename _InputIterator2>
428  inline bool
429  __check_sorted_set(const _InputIterator1& __first,
430  const _InputIterator1& __last,
431  const _InputIterator2&)
432  {
433  typedef typename std::iterator_traits<_InputIterator1>::value_type
434  _ValueType1;
435  typedef typename std::iterator_traits<_InputIterator2>::value_type
436  _ValueType2;
437 
438  typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
439  _SameType;
440  return __check_sorted_set_aux(__first, __last, _SameType());
441  }
442 
443  template<typename _InputIterator1, typename _InputIterator2,
444  typename _Predicate>
445  inline bool
446  __check_sorted_set(const _InputIterator1& __first,
447  const _InputIterator1& __last,
448  const _InputIterator2&, _Predicate __pred)
449  {
450  typedef typename std::iterator_traits<_InputIterator1>::value_type
451  _ValueType1;
452  typedef typename std::iterator_traits<_InputIterator2>::value_type
453  _ValueType2;
454 
455  typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
456  _SameType;
457  return __check_sorted_set_aux(__first, __last, __pred, _SameType());
458  }
459 
460  // _GLIBCXX_RESOLVE_LIB_DEFECTS
461  // 270. Binary search requirements overly strict
462  // Determine if a sequence is partitioned w.r.t. this element.
463  template<typename _ForwardIterator, typename _Tp>
464  inline bool
465  __check_partitioned_lower(_ForwardIterator __first,
466  _ForwardIterator __last, const _Tp& __value)
467  {
468  while (__first != __last && *__first < __value)
469  ++__first;
470  if (__first != __last)
471  {
472  ++__first;
473  while (__first != __last && !(*__first < __value))
474  ++__first;
475  }
476  return __first == __last;
477  }
478 
479  template<typename _ForwardIterator, typename _Tp>
480  inline bool
481  __check_partitioned_upper(_ForwardIterator __first,
482  _ForwardIterator __last, const _Tp& __value)
483  {
484  while (__first != __last && !(__value < *__first))
485  ++__first;
486  if (__first != __last)
487  {
488  ++__first;
489  while (__first != __last && __value < *__first)
490  ++__first;
491  }
492  return __first == __last;
493  }
494 
495  // Determine if a sequence is partitioned w.r.t. this element.
496  template<typename _ForwardIterator, typename _Tp, typename _Pred>
497  inline bool
498  __check_partitioned_lower(_ForwardIterator __first,
499  _ForwardIterator __last, const _Tp& __value,
500  _Pred __pred)
501  {
502  while (__first != __last && bool(__pred(*__first, __value)))
503  ++__first;
504  if (__first != __last)
505  {
506  ++__first;
507  while (__first != __last && !bool(__pred(*__first, __value)))
508  ++__first;
509  }
510  return __first == __last;
511  }
512 
513  template<typename _ForwardIterator, typename _Tp, typename _Pred>
514  inline bool
515  __check_partitioned_upper(_ForwardIterator __first,
516  _ForwardIterator __last, const _Tp& __value,
517  _Pred __pred)
518  {
519  while (__first != __last && !bool(__pred(__value, *__first)))
520  ++__first;
521  if (__first != __last)
522  {
523  ++__first;
524  while (__first != __last && bool(__pred(__value, *__first)))
525  ++__first;
526  }
527  return __first == __last;
528  }
529 
530  // Helper struct to detect random access safe iterators.
531  template<typename _Iterator>
532  struct __is_safe_random_iterator
533  {
534  enum { __value = 0 };
535  typedef std::__false_type __type;
536  };
537 
538  template<typename _Iterator, typename _Sequence>
539  struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
540  : std::__are_same<std::random_access_iterator_tag,
541  typename std::iterator_traits<_Iterator>::
542  iterator_category>
543  { };
544 
545  template<typename _Iterator>
546  struct _Siter_base
547  : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
548  { };
549 
550  /** Helper function to extract base iterator of random access safe iterator
551  in order to reduce performance impact of debug mode. Limited to random
552  access iterator because it is the only category for which it is possible
553  to check for correct iterators order in the __valid_range function
554  thanks to the < operator.
555  */
556  template<typename _Iterator>
557  inline typename _Siter_base<_Iterator>::iterator_type
558  __base(_Iterator __it)
559  { return _Siter_base<_Iterator>::_S_base(__it); }
560 } // namespace __gnu_debug
561 
562 #endif
is_lvalue_reference
Definition: type_traits:350
Safe iterator wrapper.
Definition: formatter.h:49
Marking input iterators.
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
bool __foreign_iterator_aux2(const _Safe_iterator< _Iterator, _Sequence > &__it, const _Safe_iterator< _OtherIterator, _Sequence > &__other, const _Safe_iterator< _OtherIterator, _Sequence > &)
Definition: functions.h:234
bool _M_dereferenceable() const
Is the iterator dereferenceable?
bool __valid_range_aux(const _Integral &, const _Integral &, std::__true_type)
Definition: functions.h:127
bool __valid_range_aux2(const _RandomAccessIterator &__first, const _RandomAccessIterator &__last, std::random_access_iterator_tag)
Definition: functions.h:106
bool __valid_range(const _InputIterator &__first, const _InputIterator &__last)
Definition: functions.h:147
bool __check_dereferenceable(const _Iterator &)
Definition: functions.h:79
const _CharT * __check_string(const _CharT *__s, const _Integer &__n __attribute__((__unused__)))
Definition: functions.h:300
GNU debug classes for public use.
One of the comparison functors.
Definition: stl_function.h:341
Random-access iterators support a superset of bidirectional iterator operations.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
Definition: functions.h:558
Safe iterator wrapper.
Definition: formatter.h:46
Forward iterators support a superset of input iterator operations.