1 // Debugging support implementation -*- C++ -*-
3 // Copyright (C) 2003-2023 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/stl_function.h> // for less
34 #if __cplusplus >= 201103L
35 # include <bits/stl_iterator.h> // for __miter_base
36 # include <type_traits> // for is_lvalue_reference and __conditional_t.
39 #include <debug/helper_functions.h>
40 #include <debug/formatter.h>
44 template<typename _Sequence
>
45 struct _Insert_range_from_self_is_safe
46 { enum { __value
= 0 }; };
48 template<typename _Sequence
>
49 struct _Is_contiguous_sequence
: std::__false_type
{ };
51 /* Checks that [first, last) is a valid range, and then returns
52 * __first. This routine is useful when we can't use a separate
53 * assertion statement because, e.g., we are in a constructor.
55 template<typename _InputIterator
>
57 __check_valid_range(const _InputIterator
& __first
,
58 const _InputIterator
& __last
,
61 const char* __function
)
63 __glibcxx_check_valid_range_at(__first
, __last
,
64 __file
, __line
, __function
);
68 /* Handle the case where __other is a pointer to _Sequence::value_type. */
69 template<typename _Iterator
, typename _Sequence
, typename _Category
>
71 __foreign_iterator_aux4(
72 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
73 const typename
_Sequence::value_type
* __other
)
75 typedef const typename
_Sequence::value_type
* _PointerType
;
76 typedef std::less
<_PointerType
> _Less
;
77 #if __cplusplus >= 201103L
78 constexpr _Less __l
{};
80 const _Less __l
= _Less();
82 const _Sequence
* __seq
= __it
._M_get_sequence();
83 const _PointerType __begin
= std::__addressof(*__seq
->_M_base().begin());
84 const _PointerType __end
= std::__addressof(*(__seq
->_M_base().end()-1));
86 // Check whether __other points within the contiguous storage.
87 return __l(__other
, __begin
) || __l(__end
, __other
);
90 /* Fallback overload for when we can't tell, assume it is valid. */
91 template<typename _Iterator
, typename _Sequence
, typename _Category
>
93 __foreign_iterator_aux4(
94 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&, ...)
97 /* Handle sequences with contiguous storage */
98 template<typename _Iterator
, typename _Sequence
, typename _Category
,
99 typename _InputIterator
>
101 __foreign_iterator_aux3(
102 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
103 const _InputIterator
& __other
, const _InputIterator
& __other_end
,
106 if (__other
== __other_end
)
107 return true; // inserting nothing is safe even if not foreign iters
108 if (__it
._M_get_sequence()->empty())
109 return true; // can't be self-inserting if self is empty
110 return __foreign_iterator_aux4(__it
, std::__addressof(*__other
));
113 /* Handle non-contiguous containers, assume it is valid. */
114 template<typename _Iterator
, typename _Sequence
, typename _Category
,
115 typename _InputIterator
>
117 __foreign_iterator_aux3(
118 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&,
119 const _InputIterator
&, const _InputIterator
&,
123 /** Handle debug iterators from the same type of container. */
124 template<typename _Iterator
, typename _Sequence
, typename _Category
,
125 typename _OtherIterator
>
127 __foreign_iterator_aux2(
128 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
129 const _Safe_iterator
<_OtherIterator
, _Sequence
, _Category
>& __other
,
130 const _Safe_iterator
<_OtherIterator
, _Sequence
, _Category
>&)
131 { return __it
._M_get_sequence() != __other
._M_get_sequence(); }
133 /** Handle debug iterators from different types of container. */
134 template<typename _Iterator
, typename _Sequence
, typename _Category
,
135 typename _OtherIterator
, typename _OtherSequence
,
136 typename _OtherCategory
>
138 __foreign_iterator_aux2(
139 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&,
140 const _Safe_iterator
<_OtherIterator
, _OtherSequence
,
142 const _Safe_iterator
<_OtherIterator
, _OtherSequence
,
146 /* Handle non-debug iterators. */
147 template<typename _Iterator
, typename _Sequence
, typename _Category
,
148 typename _InputIterator
>
150 __foreign_iterator_aux2(
151 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
152 const _InputIterator
& __other
,
153 const _InputIterator
& __other_end
)
155 #if __cplusplus < 201103L
156 typedef _Is_contiguous_sequence
<_Sequence
> __tag
;
158 using __lvalref
= std::is_lvalue_reference
<
159 typename
std::iterator_traits
<_InputIterator
>::reference
>;
160 using __contiguous
= _Is_contiguous_sequence
<_Sequence
>;
161 using __tag
= std::__conditional_t
<__lvalref::value
, __contiguous
,
164 return __foreign_iterator_aux3(__it
, __other
, __other_end
, __tag());
167 /* Handle the case where we aren't really inserting a range after all */
168 template<typename _Iterator
, typename _Sequence
, typename _Category
,
171 __foreign_iterator_aux(
172 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&,
173 _Integral
, _Integral
, std::__true_type
)
176 /* Handle all iterators. */
177 template<typename _Iterator
, typename _Sequence
, typename _Category
,
178 typename _InputIterator
>
180 __foreign_iterator_aux(
181 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
182 _InputIterator __other
, _InputIterator __other_end
,
185 return _Insert_range_from_self_is_safe
<_Sequence
>::__value
186 || __foreign_iterator_aux2(__it
, std::__miter_base(__other
),
187 std::__miter_base(__other_end
));
190 template<typename _Iterator
, typename _Sequence
, typename _Category
,
191 typename _InputIterator
>
194 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
195 _InputIterator __other
, _InputIterator __other_end
)
197 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
198 return __foreign_iterator_aux(__it
, __other
, __other_end
, _Integral());
201 // Can't check if an input iterator sequence is sorted, because we
202 // can't step through the sequence.
203 template<typename _InputIterator
>
206 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
207 std::input_iterator_tag
)
210 // Can verify if a forward iterator sequence is in fact sorted using
212 template<typename _ForwardIterator
>
215 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
216 std::forward_iterator_tag
)
218 if (__first
== __last
)
221 _ForwardIterator __next
= __first
;
222 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
223 if (*__next
< *__first
)
229 // Can't check if an input iterator sequence is sorted, because we can't step
230 // through the sequence.
231 template<typename _InputIterator
, typename _Predicate
>
234 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
235 _Predicate
, std::input_iterator_tag
)
238 // Can verify if a forward iterator sequence is in fact sorted using
240 template<typename _ForwardIterator
, typename _Predicate
>
243 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
244 _Predicate __pred
, std::forward_iterator_tag
)
246 if (__first
== __last
)
249 _ForwardIterator __next
= __first
;
250 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
251 if (__pred(*__next
, *__first
))
257 // Determine if a sequence is sorted.
258 template<typename _InputIterator
>
261 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
)
263 return __check_sorted_aux(__first
, __last
,
264 std::__iterator_category(__first
));
267 template<typename _InputIterator
, typename _Predicate
>
270 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
,
273 return __check_sorted_aux(__first
, __last
, __pred
,
274 std::__iterator_category(__first
));
277 template<typename _InputIterator
>
280 __check_sorted_set_aux(const _InputIterator
& __first
,
281 const _InputIterator
& __last
,
283 { return __check_sorted(__first
, __last
); }
285 template<typename _InputIterator
>
288 __check_sorted_set_aux(const _InputIterator
&,
289 const _InputIterator
&,
293 template<typename _InputIterator
, typename _Predicate
>
296 __check_sorted_set_aux(const _InputIterator
& __first
,
297 const _InputIterator
& __last
,
298 _Predicate __pred
, std::__true_type
)
299 { return __check_sorted(__first
, __last
, __pred
); }
301 template<typename _InputIterator
, typename _Predicate
>
304 __check_sorted_set_aux(const _InputIterator
&,
305 const _InputIterator
&, _Predicate
,
309 // ... special variant used in std::merge, std::includes, std::set_*.
310 template<typename _InputIterator1
, typename _InputIterator2
>
313 __check_sorted_set(const _InputIterator1
& __first
,
314 const _InputIterator1
& __last
,
315 const _InputIterator2
&)
317 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
319 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
322 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
324 return __check_sorted_set_aux(__first
, __last
, _SameType());
327 template<typename _InputIterator1
, typename _InputIterator2
,
331 __check_sorted_set(const _InputIterator1
& __first
,
332 const _InputIterator1
& __last
,
333 const _InputIterator2
&, _Predicate __pred
)
335 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
337 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
340 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
342 return __check_sorted_set_aux(__first
, __last
, __pred
, _SameType());
345 // _GLIBCXX_RESOLVE_LIB_DEFECTS
346 // 270. Binary search requirements overly strict
347 // Determine if a sequence is partitioned w.r.t. this element.
348 template<typename _ForwardIterator
, typename _Tp
>
351 __check_partitioned_lower(_ForwardIterator __first
,
352 _ForwardIterator __last
, const _Tp
& __value
)
354 while (__first
!= __last
&& *__first
< __value
)
356 if (__first
!= __last
)
359 while (__first
!= __last
&& !(*__first
< __value
))
362 return __first
== __last
;
365 template<typename _ForwardIterator
, typename _Tp
>
368 __check_partitioned_upper(_ForwardIterator __first
,
369 _ForwardIterator __last
, const _Tp
& __value
)
371 while (__first
!= __last
&& !(__value
< *__first
))
373 if (__first
!= __last
)
376 while (__first
!= __last
&& __value
< *__first
)
379 return __first
== __last
;
382 // Determine if a sequence is partitioned w.r.t. this element.
383 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
386 __check_partitioned_lower(_ForwardIterator __first
,
387 _ForwardIterator __last
, const _Tp
& __value
,
390 while (__first
!= __last
&& bool(__pred(*__first
, __value
)))
392 if (__first
!= __last
)
395 while (__first
!= __last
&& !bool(__pred(*__first
, __value
)))
398 return __first
== __last
;
401 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
404 __check_partitioned_upper(_ForwardIterator __first
,
405 _ForwardIterator __last
, const _Tp
& __value
,
408 while (__first
!= __last
&& !bool(__pred(__value
, *__first
)))
410 if (__first
!= __last
)
413 while (__first
!= __last
&& bool(__pred(__value
, *__first
)))
416 return __first
== __last
;
419 #if __cplusplus >= 201103L
420 struct _Irreflexive_checker
422 template<typename _It
>
423 static typename
std::iterator_traits
<_It
>::reference
426 template<typename _It
,
427 typename
= decltype(__ref
<_It
>() < __ref
<_It
>())>
430 _S_is_valid(_It __it
)
431 { return !(*__it
< *__it
); }
433 // Fallback method if operator doesn't exist.
434 template<typename
... _Args
>
437 _S_is_valid(_Args
...)
440 template<typename _It
, typename _Pred
, typename
441 = decltype(std::declval
<_Pred
>()(__ref
<_It
>(), __ref
<_It
>()))>
444 _S_is_valid_pred(_It __it
, _Pred __pred
)
445 { return !__pred(*__it
, *__it
); }
447 // Fallback method if predicate can't be invoked.
448 template<typename
... _Args
>
451 _S_is_valid_pred(_Args
...)
455 template<typename _Iterator
>
458 __is_irreflexive(_Iterator __it
)
459 { return _Irreflexive_checker::_S_is_valid(__it
); }
461 template<typename _Iterator
, typename _Pred
>
464 __is_irreflexive_pred(_Iterator __it
, _Pred __pred
)
465 { return _Irreflexive_checker::_S_is_valid_pred(__it
, __pred
); }
468 } // namespace __gnu_debug