1 // Debugging support implementation -*- C++ -*-
3 // Copyright (C) 2003-2018 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 conditional.
38 #include <debug/helper_functions.h>
39 #include <debug/formatter.h>
43 template<typename _Iterator
, typename _Sequence
>
46 template<typename _Sequence
>
47 struct _Insert_range_from_self_is_safe
48 { enum { __value
= 0 }; };
50 template<typename _Sequence
>
51 struct _Is_contiguous_sequence
: std::__false_type
{ };
53 // An arbitrary iterator pointer is not singular.
55 __check_singular_aux(const void*) { return false; }
57 // We may have an iterator that derives from _Safe_iterator_base but isn't
59 template<typename _Iterator
>
61 __check_singular(const _Iterator
& __x
)
62 { return __check_singular_aux(std::__addressof(__x
)); }
64 /** Non-NULL pointers are nonsingular. */
65 template<typename _Tp
>
67 __check_singular(const _Tp
* __ptr
)
68 { return __ptr
== 0; }
70 /** Assume that some arbitrary iterator is dereferenceable, because we
71 can't prove that it isn't. */
72 template<typename _Iterator
>
74 __check_dereferenceable(const _Iterator
&)
77 /** Non-NULL pointers are dereferenceable. */
78 template<typename _Tp
>
80 __check_dereferenceable(const _Tp
* __ptr
)
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.
87 template<typename _InputIterator
>
89 __check_valid_range(const _InputIterator
& __first
,
90 const _InputIterator
& __last
91 __attribute__((__unused__
)))
93 __glibcxx_check_valid_range(__first
, __last
);
97 /* Handle the case where __other is a pointer to _Sequence::value_type. */
98 template<typename _Iterator
, typename _Sequence
>
100 __foreign_iterator_aux4(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
101 const typename
_Sequence::value_type
* __other
)
103 typedef const typename
_Sequence::value_type
* _PointerType
;
104 typedef std::less
<_PointerType
> _Less
;
105 #if __cplusplus >= 201103L
106 constexpr _Less __l
{};
108 const _Less __l
= _Less();
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));
114 // Check whether __other points within the contiguous storage.
115 return __l(__other
, __begin
) || __l(__end
, __other
);
118 /* Fallback overload for when we can't tell, assume it is valid. */
119 template<typename _Iterator
, typename _Sequence
>
121 __foreign_iterator_aux4(const _Safe_iterator
<_Iterator
, _Sequence
>&, ...)
124 /* Handle sequences with contiguous storage */
125 template<typename _Iterator
, typename _Sequence
, typename _InputIterator
>
127 __foreign_iterator_aux3(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
128 const _InputIterator
& __other
,
129 const _InputIterator
& __other_end
,
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
));
139 /* Handle non-contiguous containers, assume it is valid. */
140 template<typename _Iterator
, typename _Sequence
, typename _InputIterator
>
142 __foreign_iterator_aux3(const _Safe_iterator
<_Iterator
, _Sequence
>&,
143 const _InputIterator
&, const _InputIterator
&,
147 /** Handle debug iterators from the same type of container. */
148 template<typename _Iterator
, typename _Sequence
, typename _OtherIterator
>
150 __foreign_iterator_aux2(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
151 const _Safe_iterator
<_OtherIterator
, _Sequence
>& __other
,
152 const _Safe_iterator
<_OtherIterator
, _Sequence
>&)
153 { return __it
._M_get_sequence() != __other
._M_get_sequence(); }
155 /** Handle debug iterators from different types of container. */
156 template<typename _Iterator
, typename _Sequence
, typename _OtherIterator
,
157 typename _OtherSequence
>
159 __foreign_iterator_aux2(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
160 const _Safe_iterator
<_OtherIterator
, _OtherSequence
>&,
161 const _Safe_iterator
<_OtherIterator
, _OtherSequence
>&)
164 /* Handle non-debug iterators. */
165 template<typename _Iterator
, typename _Sequence
, typename _InputIterator
>
167 __foreign_iterator_aux2(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
168 const _InputIterator
& __other
,
169 const _InputIterator
& __other_end
)
171 #if __cplusplus < 201103L
172 typedef _Is_contiguous_sequence
<_Sequence
> __tag
;
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
;
180 return __foreign_iterator_aux3(__it
, __other
, __other_end
, __tag());
183 /* Handle the case where we aren't really inserting a range after all */
184 template<typename _Iterator
, typename _Sequence
, typename _Integral
>
186 __foreign_iterator_aux(const _Safe_iterator
<_Iterator
, _Sequence
>&,
187 _Integral
, _Integral
,
191 /* Handle all iterators. */
192 template<typename _Iterator
, typename _Sequence
,
193 typename _InputIterator
>
195 __foreign_iterator_aux(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
196 _InputIterator __other
, _InputIterator __other_end
,
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
));
204 template<typename _Iterator
, typename _Sequence
,
205 typename _InputIterator
>
207 __foreign_iterator(const _Safe_iterator
<_Iterator
, _Sequence
>& __it
,
208 _InputIterator __other
, _InputIterator __other_end
)
210 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
211 return __foreign_iterator_aux(__it
, __other
, __other_end
, _Integral());
214 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
215 template<typename _CharT
, typename _Integer
>
217 __check_string(const _CharT
* __s
,
218 const _Integer
& __n
__attribute__((__unused__
)))
220 #ifdef _GLIBCXX_DEBUG_PEDANTIC
221 __glibcxx_assert(__s
!= 0 || __n
== 0);
226 /** Checks that __s is non-NULL and then returns __s. */
227 template<typename _CharT
>
229 __check_string(const _CharT
* __s
)
231 #ifdef _GLIBCXX_DEBUG_PEDANTIC
232 __glibcxx_assert(__s
!= 0);
237 // Can't check if an input iterator sequence is sorted, because we
238 // can't step through the sequence.
239 template<typename _InputIterator
>
241 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
242 std::input_iterator_tag
)
245 // Can verify if a forward iterator sequence is in fact sorted using
247 template<typename _ForwardIterator
>
249 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
250 std::forward_iterator_tag
)
252 if (__first
== __last
)
255 _ForwardIterator __next
= __first
;
256 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
257 if (*__next
< *__first
)
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
>
267 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
268 _Predicate
, std::input_iterator_tag
)
271 // Can verify if a forward iterator sequence is in fact sorted using
273 template<typename _ForwardIterator
, typename _Predicate
>
275 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
276 _Predicate __pred
, std::forward_iterator_tag
)
278 if (__first
== __last
)
281 _ForwardIterator __next
= __first
;
282 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
283 if (__pred(*__next
, *__first
))
289 // Determine if a sequence is sorted.
290 template<typename _InputIterator
>
292 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
)
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
));
298 return __check_sorted_aux(__first
, __last
,
299 std::__iterator_category(__first
));
302 template<typename _InputIterator
, typename _Predicate
>
304 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
,
307 // Verify that the predicate is StrictWeakOrdering by checking that it
309 __glibcxx_assert(__first
== __last
|| !__pred(*__first
, *__first
));
311 return __check_sorted_aux(__first
, __last
, __pred
,
312 std::__iterator_category(__first
));
315 template<typename _InputIterator
>
317 __check_sorted_set_aux(const _InputIterator
& __first
,
318 const _InputIterator
& __last
,
320 { return __check_sorted(__first
, __last
); }
322 template<typename _InputIterator
>
324 __check_sorted_set_aux(const _InputIterator
&,
325 const _InputIterator
&,
329 template<typename _InputIterator
, typename _Predicate
>
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
); }
336 template<typename _InputIterator
, typename _Predicate
>
338 __check_sorted_set_aux(const _InputIterator
&,
339 const _InputIterator
&, _Predicate
,
343 // ... special variant used in std::merge, std::includes, std::set_*.
344 template<typename _InputIterator1
, typename _InputIterator2
>
346 __check_sorted_set(const _InputIterator1
& __first
,
347 const _InputIterator1
& __last
,
348 const _InputIterator2
&)
350 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
352 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
355 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
357 return __check_sorted_set_aux(__first
, __last
, _SameType());
360 template<typename _InputIterator1
, typename _InputIterator2
,
363 __check_sorted_set(const _InputIterator1
& __first
,
364 const _InputIterator1
& __last
,
365 const _InputIterator2
&, _Predicate __pred
)
367 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
369 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
372 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
374 return __check_sorted_set_aux(__first
, __last
, __pred
, _SameType());
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
>
382 __check_partitioned_lower(_ForwardIterator __first
,
383 _ForwardIterator __last
, const _Tp
& __value
)
385 while (__first
!= __last
&& *__first
< __value
)
387 if (__first
!= __last
)
390 while (__first
!= __last
&& !(*__first
< __value
))
393 return __first
== __last
;
396 template<typename _ForwardIterator
, typename _Tp
>
398 __check_partitioned_upper(_ForwardIterator __first
,
399 _ForwardIterator __last
, const _Tp
& __value
)
401 while (__first
!= __last
&& !(__value
< *__first
))
403 if (__first
!= __last
)
406 while (__first
!= __last
&& __value
< *__first
)
409 return __first
== __last
;
412 // Determine if a sequence is partitioned w.r.t. this element.
413 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
415 __check_partitioned_lower(_ForwardIterator __first
,
416 _ForwardIterator __last
, const _Tp
& __value
,
419 while (__first
!= __last
&& bool(__pred(*__first
, __value
)))
421 if (__first
!= __last
)
424 while (__first
!= __last
&& !bool(__pred(*__first
, __value
)))
427 return __first
== __last
;
430 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
432 __check_partitioned_upper(_ForwardIterator __first
,
433 _ForwardIterator __last
, const _Tp
& __value
,
436 while (__first
!= __last
&& !bool(__pred(__value
, *__first
)))
438 if (__first
!= __last
)
441 while (__first
!= __last
&& bool(__pred(__value
, *__first
)))
444 return __first
== __last
;
447 #if __cplusplus >= 201103L
448 struct _Irreflexive_checker
450 template<typename _It
>
451 static typename
std::iterator_traits
<_It
>::reference
454 template<typename _It
,
455 typename
= decltype(__deref
<_It
>() < __deref
<_It
>())>
457 _S_is_valid(_It __it
)
458 { return !(*__it
< *__it
); }
460 // Fallback method if operator doesn't exist.
461 template<typename
... _Args
>
463 _S_is_valid(_Args
...)
466 template<typename _It
, typename _Pred
, typename
467 = decltype(std::declval
<_Pred
>()(__deref
<_It
>(), __deref
<_It
>()))>
469 _S_is_valid_pred(_It __it
, _Pred __pred
)
470 { return !__pred(*__it
, *__it
); }
472 // Fallback method if predicate can't be invoked.
473 template<typename
... _Args
>
475 _S_is_valid_pred(_Args
...)
479 template<typename _Iterator
>
481 __is_irreflexive(_Iterator __it
)
482 { return _Irreflexive_checker::_S_is_valid(__it
); }
484 template<typename _Iterator
, typename _Pred
>
486 __is_irreflexive_pred(_Iterator __it
, _Pred __pred
)
487 { return _Irreflexive_checker::_S_is_valid_pred(__it
, __pred
); }
490 } // namespace __gnu_debug