1 // Debugging support implementation -*- C++ -*-
3 // Copyright (C) 2003-2015 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25 /** @file debug/functions.h
26 * This file is a GNU debug extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
30 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
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
39 #include <debug/helper_functions.h>
40 #include <debug/formatter.h>
44 template<typename _Iterator
, typename _Sequence
>
47 template<typename _Sequence
>
48 struct _Insert_range_from_self_is_safe
49 { enum { __value
= 0 }; };
51 template<typename _Sequence
>
52 struct _Is_contiguous_sequence
: std::__false_type
{ };
54 // An arbitrary iterator pointer is not singular.
56 __check_singular_aux(const void*) { return false; }
58 // We may have an iterator that derives from _Safe_iterator_base but isn't
60 template<typename _Iterator
>
62 __check_singular(const _Iterator
& __x
)
63 { return __check_singular_aux(std::__addressof(__x
)); }
65 /** Non-NULL pointers are nonsingular. */
66 template<typename _Tp
>
68 __check_singular(const _Tp
* __ptr
)
69 { return __ptr
== 0; }
71 /** Assume that some arbitrary iterator is dereferenceable, because we
72 can't prove that it isn't. */
73 template<typename _Iterator
>
75 __check_dereferenceable(const _Iterator
&)
78 /** Non-NULL pointers are dereferenceable. */
79 template<typename _Tp
>
81 __check_dereferenceable(const _Tp
* __ptr
)
84 /* Checks that [first, last) is a valid range, and then returns
85 * __first. This routine is useful when we can't use a separate
86 * assertion statement because, e.g., we are in a constructor.
88 template<typename _InputIterator
>
90 __check_valid_range(const _InputIterator
& __first
,
91 const _InputIterator
& __last
92 __attribute__((__unused__
)))
94 __glibcxx_check_valid_range(__first
, __last
);
98 /* Handle the case where __other is a pointer to _Sequence::value_type. */
99 template<typename _Iterator
, typename _Sequence
>
101 __foreign_iterator_aux4(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
102 const typename
_Sequence::value_type
* __other
)
104 typedef const typename
_Sequence::value_type
* _PointerType
;
105 typedef std::less
<_PointerType
> _Less
;
106 #if __cplusplus >= 201103L
107 constexpr _Less __l
{};
109 const _Less __l
= _Less();
111 const _Sequence
* __seq
= __it
._M_get_sequence();
112 const _PointerType __begin
= std::__addressof(*__seq
->_M_base().begin());
113 const _PointerType __end
= std::__addressof(*(__seq
->_M_base().end()-1));
115 // Check whether __other points within the contiguous storage.
116 return __l(__other
, __begin
) || __l(__end
, __other
);
119 /* Fallback overload for when we can't tell, assume it is valid. */
120 template<typename _Iterator
, typename _Sequence
>
122 __foreign_iterator_aux4(const _Safe_iterator
<_Iterator
, _Sequence
>&, ...)
125 /* Handle sequences with contiguous storage */
126 template<typename _Iterator
, typename _Sequence
, typename _InputIterator
>
128 __foreign_iterator_aux3(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
129 const _InputIterator
& __other
,
130 const _InputIterator
& __other_end
,
133 if (__other
== __other_end
)
134 return true; // inserting nothing is safe even if not foreign iters
135 if (__it
._M_get_sequence()->begin() == __it
._M_get_sequence()->end())
136 return true; // can't be self-inserting if self is empty
137 return __foreign_iterator_aux4(__it
, std::__addressof(*__other
));
140 /* Handle non-contiguous containers, assume it is valid. */
141 template<typename _Iterator
, typename _Sequence
, typename _InputIterator
>
143 __foreign_iterator_aux3(const _Safe_iterator
<_Iterator
, _Sequence
>&,
144 const _InputIterator
&, const _InputIterator
&,
148 /** Handle debug iterators from the same type of container. */
149 template<typename _Iterator
, typename _Sequence
, typename _OtherIterator
>
151 __foreign_iterator_aux2(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
152 const _Safe_iterator
<_OtherIterator
, _Sequence
>& __other
,
153 const _Safe_iterator
<_OtherIterator
, _Sequence
>&)
154 { return __it
._M_get_sequence() != __other
._M_get_sequence(); }
156 /** Handle debug iterators from different types of container. */
157 template<typename _Iterator
, typename _Sequence
, typename _OtherIterator
,
158 typename _OtherSequence
>
160 __foreign_iterator_aux2(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
161 const _Safe_iterator
<_OtherIterator
, _OtherSequence
>&,
162 const _Safe_iterator
<_OtherIterator
, _OtherSequence
>&)
165 /* Handle non-debug iterators. */
166 template<typename _Iterator
, typename _Sequence
, typename _InputIterator
>
168 __foreign_iterator_aux2(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
169 const _InputIterator
& __other
,
170 const _InputIterator
& __other_end
)
172 #if __cplusplus < 201103L
173 typedef _Is_contiguous_sequence
<_Sequence
> __tag
;
175 using __lvalref
= std::is_lvalue_reference
<
176 typename
std::iterator_traits
<_InputIterator
>::reference
>;
177 using __contiguous
= _Is_contiguous_sequence
<_Sequence
>;
178 using __tag
= typename
std::conditional
<__lvalref::value
, __contiguous
,
179 std::__false_type
>::type
;
181 return __foreign_iterator_aux3(__it
, __other
, __other_end
, __tag());
184 /* Handle the case where we aren't really inserting a range after all */
185 template<typename _Iterator
, typename _Sequence
, typename _Integral
>
187 __foreign_iterator_aux(const _Safe_iterator
<_Iterator
, _Sequence
>&,
188 _Integral
, _Integral
,
192 /* Handle all iterators. */
193 template<typename _Iterator
, typename _Sequence
,
194 typename _InputIterator
>
196 __foreign_iterator_aux(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
197 _InputIterator __other
, _InputIterator __other_end
,
200 return _Insert_range_from_self_is_safe
<_Sequence
>::__value
201 || __foreign_iterator_aux2(__it
, std::__miter_base(__other
),
202 std::__miter_base(__other_end
));
205 template<typename _Iterator
, typename _Sequence
,
206 typename _InputIterator
>
208 __foreign_iterator(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
209 _InputIterator __other
, _InputIterator __other_end
)
211 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
212 return __foreign_iterator_aux(__it
, __other
, __other_end
, _Integral());
215 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
216 template<typename _CharT
, typename _Integer
>
218 __check_string(const _CharT
* __s
,
219 const _Integer
& __n
__attribute__((__unused__
)))
221 #ifdef _GLIBCXX_DEBUG_PEDANTIC
222 __glibcxx_assert(__s
!= 0 || __n
== 0);
227 /** Checks that __s is non-NULL and then returns __s. */
228 template<typename _CharT
>
230 __check_string(const _CharT
* __s
)
232 #ifdef _GLIBCXX_DEBUG_PEDANTIC
233 __glibcxx_assert(__s
!= 0);
238 // Can't check if an input iterator sequence is sorted, because we
239 // can't step through the sequence.
240 template<typename _InputIterator
>
242 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
243 std::input_iterator_tag
)
246 // Can verify if a forward iterator sequence is in fact sorted using
248 template<typename _ForwardIterator
>
250 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
251 std::forward_iterator_tag
)
253 if (__first
== __last
)
256 _ForwardIterator __next
= __first
;
257 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
258 if (*__next
< *__first
)
264 // Can't check if an input iterator sequence is sorted, because we can't step
265 // through the sequence.
266 template<typename _InputIterator
, typename _Predicate
>
268 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
269 _Predicate
, std::input_iterator_tag
)
272 // Can verify if a forward iterator sequence is in fact sorted using
274 template<typename _ForwardIterator
, typename _Predicate
>
276 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
277 _Predicate __pred
, std::forward_iterator_tag
)
279 if (__first
== __last
)
282 _ForwardIterator __next
= __first
;
283 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
284 if (__pred(*__next
, *__first
))
290 // Determine if a sequence is sorted.
291 template<typename _InputIterator
>
293 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
)
295 // Verify that the < operator for elements in the sequence is a
296 // StrictWeakOrdering by checking that it is irreflexive.
297 __glibcxx_assert(__first
== __last
|| !(*__first
< *__first
));
299 return __check_sorted_aux(__first
, __last
,
300 std::__iterator_category(__first
));
303 template<typename _InputIterator
, typename _Predicate
>
305 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
,
308 // Verify that the predicate is StrictWeakOrdering by checking that it
310 __glibcxx_assert(__first
== __last
|| !__pred(*__first
, *__first
));
312 return __check_sorted_aux(__first
, __last
, __pred
,
313 std::__iterator_category(__first
));
316 template<typename _InputIterator
>
318 __check_sorted_set_aux(const _InputIterator
& __first
,
319 const _InputIterator
& __last
,
321 { return __check_sorted(__first
, __last
); }
323 template<typename _InputIterator
>
325 __check_sorted_set_aux(const _InputIterator
&,
326 const _InputIterator
&,
330 template<typename _InputIterator
, typename _Predicate
>
332 __check_sorted_set_aux(const _InputIterator
& __first
,
333 const _InputIterator
& __last
,
334 _Predicate __pred
, std::__true_type
)
335 { return __check_sorted(__first
, __last
, __pred
); }
337 template<typename _InputIterator
, typename _Predicate
>
339 __check_sorted_set_aux(const _InputIterator
&,
340 const _InputIterator
&, _Predicate
,
344 // ... special variant used in std::merge, std::includes, std::set_*.
345 template<typename _InputIterator1
, typename _InputIterator2
>
347 __check_sorted_set(const _InputIterator1
& __first
,
348 const _InputIterator1
& __last
,
349 const _InputIterator2
&)
351 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
353 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
356 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
358 return __check_sorted_set_aux(__first
, __last
, _SameType());
361 template<typename _InputIterator1
, typename _InputIterator2
,
364 __check_sorted_set(const _InputIterator1
& __first
,
365 const _InputIterator1
& __last
,
366 const _InputIterator2
&, _Predicate __pred
)
368 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
370 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
373 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
375 return __check_sorted_set_aux(__first
, __last
, __pred
, _SameType());
378 // _GLIBCXX_RESOLVE_LIB_DEFECTS
379 // 270. Binary search requirements overly strict
380 // Determine if a sequence is partitioned w.r.t. this element.
381 template<typename _ForwardIterator
, typename _Tp
>
383 __check_partitioned_lower(_ForwardIterator __first
,
384 _ForwardIterator __last
, const _Tp
& __value
)
386 while (__first
!= __last
&& *__first
< __value
)
388 if (__first
!= __last
)
391 while (__first
!= __last
&& !(*__first
< __value
))
394 return __first
== __last
;
397 template<typename _ForwardIterator
, typename _Tp
>
399 __check_partitioned_upper(_ForwardIterator __first
,
400 _ForwardIterator __last
, const _Tp
& __value
)
402 while (__first
!= __last
&& !(__value
< *__first
))
404 if (__first
!= __last
)
407 while (__first
!= __last
&& __value
< *__first
)
410 return __first
== __last
;
413 // Determine if a sequence is partitioned w.r.t. this element.
414 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
416 __check_partitioned_lower(_ForwardIterator __first
,
417 _ForwardIterator __last
, const _Tp
& __value
,
420 while (__first
!= __last
&& bool(__pred(*__first
, __value
)))
422 if (__first
!= __last
)
425 while (__first
!= __last
&& !bool(__pred(*__first
, __value
)))
428 return __first
== __last
;
431 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
433 __check_partitioned_upper(_ForwardIterator __first
,
434 _ForwardIterator __last
, const _Tp
& __value
,
437 while (__first
!= __last
&& !bool(__pred(__value
, *__first
)))
439 if (__first
!= __last
)
442 while (__first
!= __last
&& bool(__pred(__value
, *__first
)))
445 return __first
== __last
;
448 #if __cplusplus >= 201103L
449 struct _Irreflexive_checker
451 template<typename _It
>
452 static typename
std::iterator_traits
<_It
>::reference
455 template<typename _It
,
456 typename
= decltype(__deref
<_It
>() < __deref
<_It
>())>
458 _S_is_valid(_It __it
)
459 { return !(*__it
< *__it
); }
461 // Fallback method if operator doesn't exist.
462 template<typename
... _Args
>
464 _S_is_valid(_Args
...)
467 template<typename _It
, typename _Pred
, typename
468 = decltype(std::declval
<_Pred
>()(__deref
<_It
>(), __deref
<_It
>()))>
470 _S_is_valid_pred(_It __it
, _Pred __pred
)
471 { return !__pred(*__it
, *__it
); }
473 // Fallback method if predicate can't be invoked.
474 template<typename
... _Args
>
476 _S_is_valid_pred(_Args
...)
480 template<typename _Iterator
>
482 __is_irreflexive(_Iterator __it
)
483 { return _Irreflexive_checker::_S_is_valid(__it
); }
485 template<typename _Iterator
, typename _Pred
>
487 __is_irreflexive_pred(_Iterator __it
, _Pred __pred
)
488 { return _Irreflexive_checker::_S_is_valid_pred(__it
, __pred
); }
491 } // namespace __gnu_debug