libstdc++
functions.h
Go to the documentation of this file.
1 // Debugging support implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2018 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/move.h> // for __addressof
33 #include <bits/stl_function.h> // for less
34 #if __cplusplus >= 201103L
35 # include <type_traits> // for is_lvalue_reference and conditional.
36 #endif
37 
38 #include <debug/helper_functions.h>
39 #include <debug/formatter.h>
40 
41 namespace __gnu_debug
42 {
43  template<typename _Iterator, typename _Sequence>
44  class _Safe_iterator;
45 
46  template<typename _Sequence>
47  struct _Insert_range_from_self_is_safe
48  { enum { __value = 0 }; };
49 
50  template<typename _Sequence>
51  struct _Is_contiguous_sequence : std::__false_type { };
52 
53  // An arbitrary iterator pointer is not singular.
54  inline bool
55  __check_singular_aux(const void*) { return false; }
56 
57  // We may have an iterator that derives from _Safe_iterator_base but isn't
58  // a _Safe_iterator.
59  template<typename _Iterator>
60  inline bool
61  __check_singular(const _Iterator& __x)
62  { return __check_singular_aux(std::__addressof(__x)); }
63 
64  /** Non-NULL pointers are nonsingular. */
65  template<typename _Tp>
66  inline bool
67  __check_singular(const _Tp* __ptr)
68  { return __ptr == 0; }
69 
70  /** Assume that some arbitrary iterator is dereferenceable, because we
71  can't prove that it isn't. */
72  template<typename _Iterator>
73  inline bool
74  __check_dereferenceable(const _Iterator&)
75  { return true; }
76 
77  /** Non-NULL pointers are dereferenceable. */
78  template<typename _Tp>
79  inline bool
80  __check_dereferenceable(const _Tp* __ptr)
81  { return __ptr; }
82 
83  /* Checks that [first, last) is a valid range, and then returns
84  * __first. This routine is useful when we can't use a separate
85  * assertion statement because, e.g., we are in a constructor.
86  */
87  template<typename _InputIterator>
88  inline _InputIterator
89  __check_valid_range(const _InputIterator& __first,
90  const _InputIterator& __last
91  __attribute__((__unused__)))
92  {
93  __glibcxx_check_valid_range(__first, __last);
94  return __first;
95  }
96 
97  /* Handle the case where __other is a pointer to _Sequence::value_type. */
98  template<typename _Iterator, typename _Sequence>
99  inline bool
100  __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
101  const typename _Sequence::value_type* __other)
102  {
103  typedef const typename _Sequence::value_type* _PointerType;
104  typedef std::less<_PointerType> _Less;
105 #if __cplusplus >= 201103L
106  constexpr _Less __l{};
107 #else
108  const _Less __l = _Less();
109 #endif
110  const _Sequence* __seq = __it._M_get_sequence();
111  const _PointerType __begin = std::__addressof(*__seq->_M_base().begin());
112  const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1));
113 
114  // Check whether __other points within the contiguous storage.
115  return __l(__other, __begin) || __l(__end, __other);
116  }
117 
118  /* Fallback overload for when we can't tell, assume it is valid. */
119  template<typename _Iterator, typename _Sequence>
120  inline bool
121  __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
122  { return true; }
123 
124  /* Handle sequences with contiguous storage */
125  template<typename _Iterator, typename _Sequence, typename _InputIterator>
126  inline bool
127  __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
128  const _InputIterator& __other,
129  const _InputIterator& __other_end,
130  std::__true_type)
131  {
132  if (__other == __other_end)
133  return true; // inserting nothing is safe even if not foreign iters
134  if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end())
135  return true; // can't be self-inserting if self is empty
136  return __foreign_iterator_aux4(__it, std::__addressof(*__other));
137  }
138 
139  /* Handle non-contiguous containers, assume it is valid. */
140  template<typename _Iterator, typename _Sequence, typename _InputIterator>
141  inline bool
142  __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
143  const _InputIterator&, const _InputIterator&,
144  std::__false_type)
145  { return true; }
146 
147  /** Handle debug iterators from the same type of container. */
148  template<typename _Iterator, typename _Sequence, typename _OtherIterator>
149  inline bool
153  { return __it._M_get_sequence() != __other._M_get_sequence(); }
154 
155  /** Handle debug iterators from different types of container. */
156  template<typename _Iterator, typename _Sequence, typename _OtherIterator,
157  typename _OtherSequence>
158  inline bool
162  { return true; }
163 
164  /* Handle non-debug iterators. */
165  template<typename _Iterator, typename _Sequence, typename _InputIterator>
166  inline bool
167  __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
168  const _InputIterator& __other,
169  const _InputIterator& __other_end)
170  {
171 #if __cplusplus < 201103L
172  typedef _Is_contiguous_sequence<_Sequence> __tag;
173 #else
174  using __lvalref = std::is_lvalue_reference<
175  typename std::iterator_traits<_InputIterator>::reference>;
176  using __contiguous = _Is_contiguous_sequence<_Sequence>;
177  using __tag = typename std::conditional<__lvalref::value, __contiguous,
178  std::__false_type>::type;
179 #endif
180  return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
181  }
182 
183  /* Handle the case where we aren't really inserting a range after all */
184  template<typename _Iterator, typename _Sequence, typename _Integral>
185  inline bool
186  __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
187  _Integral, _Integral,
188  std::__true_type)
189  { return true; }
190 
191  /* Handle all iterators. */
192  template<typename _Iterator, typename _Sequence,
193  typename _InputIterator>
194  inline bool
195  __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
196  _InputIterator __other, _InputIterator __other_end,
197  std::__false_type)
198  {
199  return _Insert_range_from_self_is_safe<_Sequence>::__value
200  || __foreign_iterator_aux2(__it, std::__miter_base(__other),
201  std::__miter_base(__other_end));
202  }
203 
204  template<typename _Iterator, typename _Sequence,
205  typename _InputIterator>
206  inline bool
207  __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
208  _InputIterator __other, _InputIterator __other_end)
209  {
210  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
211  return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
212  }
213 
214  /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
215  template<typename _CharT, typename _Integer>
216  inline const _CharT*
217  __check_string(const _CharT* __s,
218  const _Integer& __n __attribute__((__unused__)))
219  {
220 #ifdef _GLIBCXX_DEBUG_PEDANTIC
221  __glibcxx_assert(__s != 0 || __n == 0);
222 #endif
223  return __s;
224  }
225 
226  /** Checks that __s is non-NULL and then returns __s. */
227  template<typename _CharT>
228  inline const _CharT*
229  __check_string(const _CharT* __s)
230  {
231 #ifdef _GLIBCXX_DEBUG_PEDANTIC
232  __glibcxx_assert(__s != 0);
233 #endif
234  return __s;
235  }
236 
237  // Can't check if an input iterator sequence is sorted, because we
238  // can't step through the sequence.
239  template<typename _InputIterator>
240  inline bool
241  __check_sorted_aux(const _InputIterator&, const _InputIterator&,
243  { return true; }
244 
245  // Can verify if a forward iterator sequence is in fact sorted using
246  // std::__is_sorted
247  template<typename _ForwardIterator>
248  inline bool
249  __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
251  {
252  if (__first == __last)
253  return true;
254 
255  _ForwardIterator __next = __first;
256  for (++__next; __next != __last; __first = __next, (void)++__next)
257  if (*__next < *__first)
258  return false;
259 
260  return true;
261  }
262 
263  // Can't check if an input iterator sequence is sorted, because we can't step
264  // through the sequence.
265  template<typename _InputIterator, typename _Predicate>
266  inline bool
267  __check_sorted_aux(const _InputIterator&, const _InputIterator&,
268  _Predicate, std::input_iterator_tag)
269  { return true; }
270 
271  // Can verify if a forward iterator sequence is in fact sorted using
272  // std::__is_sorted
273  template<typename _ForwardIterator, typename _Predicate>
274  inline bool
275  __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
276  _Predicate __pred, std::forward_iterator_tag)
277  {
278  if (__first == __last)
279  return true;
280 
281  _ForwardIterator __next = __first;
282  for (++__next; __next != __last; __first = __next, (void)++__next)
283  if (__pred(*__next, *__first))
284  return false;
285 
286  return true;
287  }
288 
289  // Determine if a sequence is sorted.
290  template<typename _InputIterator>
291  inline bool
292  __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
293  {
294  // Verify that the < operator for elements in the sequence is a
295  // StrictWeakOrdering by checking that it is irreflexive.
296  __glibcxx_assert(__first == __last || !(*__first < *__first));
297 
298  return __check_sorted_aux(__first, __last,
299  std::__iterator_category(__first));
300  }
301 
302  template<typename _InputIterator, typename _Predicate>
303  inline bool
304  __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
305  _Predicate __pred)
306  {
307  // Verify that the predicate is StrictWeakOrdering by checking that it
308  // is irreflexive.
309  __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
310 
311  return __check_sorted_aux(__first, __last, __pred,
312  std::__iterator_category(__first));
313  }
314 
315  template<typename _InputIterator>
316  inline bool
317  __check_sorted_set_aux(const _InputIterator& __first,
318  const _InputIterator& __last,
319  std::__true_type)
320  { return __check_sorted(__first, __last); }
321 
322  template<typename _InputIterator>
323  inline bool
324  __check_sorted_set_aux(const _InputIterator&,
325  const _InputIterator&,
326  std::__false_type)
327  { return true; }
328 
329  template<typename _InputIterator, typename _Predicate>
330  inline bool
331  __check_sorted_set_aux(const _InputIterator& __first,
332  const _InputIterator& __last,
333  _Predicate __pred, std::__true_type)
334  { return __check_sorted(__first, __last, __pred); }
335 
336  template<typename _InputIterator, typename _Predicate>
337  inline bool
338  __check_sorted_set_aux(const _InputIterator&,
339  const _InputIterator&, _Predicate,
340  std::__false_type)
341  { return true; }
342 
343  // ... special variant used in std::merge, std::includes, std::set_*.
344  template<typename _InputIterator1, typename _InputIterator2>
345  inline bool
346  __check_sorted_set(const _InputIterator1& __first,
347  const _InputIterator1& __last,
348  const _InputIterator2&)
349  {
350  typedef typename std::iterator_traits<_InputIterator1>::value_type
351  _ValueType1;
352  typedef typename std::iterator_traits<_InputIterator2>::value_type
353  _ValueType2;
354 
355  typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
356  _SameType;
357  return __check_sorted_set_aux(__first, __last, _SameType());
358  }
359 
360  template<typename _InputIterator1, typename _InputIterator2,
361  typename _Predicate>
362  inline bool
363  __check_sorted_set(const _InputIterator1& __first,
364  const _InputIterator1& __last,
365  const _InputIterator2&, _Predicate __pred)
366  {
367  typedef typename std::iterator_traits<_InputIterator1>::value_type
368  _ValueType1;
369  typedef typename std::iterator_traits<_InputIterator2>::value_type
370  _ValueType2;
371 
372  typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
373  _SameType;
374  return __check_sorted_set_aux(__first, __last, __pred, _SameType());
375  }
376 
377  // _GLIBCXX_RESOLVE_LIB_DEFECTS
378  // 270. Binary search requirements overly strict
379  // Determine if a sequence is partitioned w.r.t. this element.
380  template<typename _ForwardIterator, typename _Tp>
381  inline bool
382  __check_partitioned_lower(_ForwardIterator __first,
383  _ForwardIterator __last, const _Tp& __value)
384  {
385  while (__first != __last && *__first < __value)
386  ++__first;
387  if (__first != __last)
388  {
389  ++__first;
390  while (__first != __last && !(*__first < __value))
391  ++__first;
392  }
393  return __first == __last;
394  }
395 
396  template<typename _ForwardIterator, typename _Tp>
397  inline bool
398  __check_partitioned_upper(_ForwardIterator __first,
399  _ForwardIterator __last, const _Tp& __value)
400  {
401  while (__first != __last && !(__value < *__first))
402  ++__first;
403  if (__first != __last)
404  {
405  ++__first;
406  while (__first != __last && __value < *__first)
407  ++__first;
408  }
409  return __first == __last;
410  }
411 
412  // Determine if a sequence is partitioned w.r.t. this element.
413  template<typename _ForwardIterator, typename _Tp, typename _Pred>
414  inline bool
415  __check_partitioned_lower(_ForwardIterator __first,
416  _ForwardIterator __last, const _Tp& __value,
417  _Pred __pred)
418  {
419  while (__first != __last && bool(__pred(*__first, __value)))
420  ++__first;
421  if (__first != __last)
422  {
423  ++__first;
424  while (__first != __last && !bool(__pred(*__first, __value)))
425  ++__first;
426  }
427  return __first == __last;
428  }
429 
430  template<typename _ForwardIterator, typename _Tp, typename _Pred>
431  inline bool
432  __check_partitioned_upper(_ForwardIterator __first,
433  _ForwardIterator __last, const _Tp& __value,
434  _Pred __pred)
435  {
436  while (__first != __last && !bool(__pred(__value, *__first)))
437  ++__first;
438  if (__first != __last)
439  {
440  ++__first;
441  while (__first != __last && bool(__pred(__value, *__first)))
442  ++__first;
443  }
444  return __first == __last;
445  }
446 
447 #if __cplusplus >= 201103L
448  struct _Irreflexive_checker
449  {
450  template<typename _It>
451  static typename std::iterator_traits<_It>::reference
452  __deref();
453 
454  template<typename _It,
455  typename = decltype(__deref<_It>() < __deref<_It>())>
456  static bool
457  _S_is_valid(_It __it)
458  { return !(*__it < *__it); }
459 
460  // Fallback method if operator doesn't exist.
461  template<typename... _Args>
462  static bool
463  _S_is_valid(_Args...)
464  { return true; }
465 
466  template<typename _It, typename _Pred, typename
467  = decltype(std::declval<_Pred>()(__deref<_It>(), __deref<_It>()))>
468  static bool
469  _S_is_valid_pred(_It __it, _Pred __pred)
470  { return !__pred(*__it, *__it); }
471 
472  // Fallback method if predicate can't be invoked.
473  template<typename... _Args>
474  static bool
475  _S_is_valid_pred(_Args...)
476  { return true; }
477  };
478 
479  template<typename _Iterator>
480  inline bool
481  __is_irreflexive(_Iterator __it)
482  { return _Irreflexive_checker::_S_is_valid(__it); }
483 
484  template<typename _Iterator, typename _Pred>
485  inline bool
486  __is_irreflexive_pred(_Iterator __it, _Pred __pred)
487  { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); }
488 #endif
489 
490 } // namespace __gnu_debug
491 
492 #endif
One of the comparison functors.
Definition: stl_function.h:340
Marking input iterators.
GNU debug classes for public use.
Safe iterator wrapper.
Definition: formatter.h:56
Forward iterators support a superset of input iterator operations.
Define a member typedef type to one of two argument types.
Definition: type_traits:92
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
bool __check_dereferenceable(const _Iterator &)
Definition: functions.h:74
const _CharT * __check_string(const _CharT *__s, const _Integer &__n __attribute__((__unused__)))
Definition: functions.h:217
is_lvalue_reference
Definition: type_traits:374
bool __foreign_iterator_aux2(const _Safe_iterator< _Iterator, _Sequence > &__it, const _Safe_iterator< _OtherIterator, _Sequence > &__other, const _Safe_iterator< _OtherIterator, _Sequence > &)
Definition: functions.h:150