1 // Debugging support implementation -*- C++ -*-
3 // Copyright (C) 2003-2019 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
35 #if __cplusplus >= 201103L
36 # include <bits/stl_iterator.h> // for __miter_base
37 # include <type_traits> // for is_lvalue_reference and conditional.
40 #include <debug/helper_functions.h>
41 #include <debug/formatter.h>
45 template<typename _Sequence
>
46 struct _Insert_range_from_self_is_safe
47 { enum { __value
= 0 }; };
49 template<typename _Sequence
>
50 struct _Is_contiguous_sequence
: std::__false_type
{ };
52 // An arbitrary iterator pointer is not singular.
54 __check_singular_aux(const void*) { return false; }
56 // We may have an iterator that derives from _Safe_iterator_base but isn't
58 template<typename _Iterator
>
60 __check_singular(const _Iterator
& __x
)
61 { return __check_singular_aux(std::__addressof(__x
)); }
63 /** Non-NULL pointers are nonsingular. */
64 template<typename _Tp
>
66 __check_singular(const _Tp
* __ptr
)
67 { return __ptr
== 0; }
69 /* Checks that [first, last) is a valid range, and then returns
70 * __first. This routine is useful when we can't use a separate
71 * assertion statement because, e.g., we are in a constructor.
73 template<typename _InputIterator
>
75 __check_valid_range(const _InputIterator
& __first
,
76 const _InputIterator
& __last
,
79 const char* __function
)
81 __glibcxx_check_valid_range_at(__first
, __last
,
82 __file
, __line
, __function
);
86 /* Handle the case where __other is a pointer to _Sequence::value_type. */
87 template<typename _Iterator
, typename _Sequence
, typename _Category
>
89 __foreign_iterator_aux4(
90 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
91 const typename
_Sequence::value_type
* __other
)
93 typedef const typename
_Sequence::value_type
* _PointerType
;
94 typedef std::less
<_PointerType
> _Less
;
95 #if __cplusplus >= 201103L
96 constexpr _Less __l
{};
98 const _Less __l
= _Less();
100 const _Sequence
* __seq
= __it
._M_get_sequence();
101 const _PointerType __begin
= std::__addressof(*__seq
->_M_base().begin());
102 const _PointerType __end
= std::__addressof(*(__seq
->_M_base().end()-1));
104 // Check whether __other points within the contiguous storage.
105 return __l(__other
, __begin
) || __l(__end
, __other
);
108 /* Fallback overload for when we can't tell, assume it is valid. */
109 template<typename _Iterator
, typename _Sequence
, typename _Category
>
111 __foreign_iterator_aux4(
112 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&, ...)
115 /* Handle sequences with contiguous storage */
116 template<typename _Iterator
, typename _Sequence
, typename _Category
,
117 typename _InputIterator
>
119 __foreign_iterator_aux3(
120 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
121 const _InputIterator
& __other
, const _InputIterator
& __other_end
,
124 if (__other
== __other_end
)
125 return true; // inserting nothing is safe even if not foreign iters
126 if (__it
._M_get_sequence()->empty())
127 return true; // can't be self-inserting if self is empty
128 return __foreign_iterator_aux4(__it
, std::__addressof(*__other
));
131 /* Handle non-contiguous containers, assume it is valid. */
132 template<typename _Iterator
, typename _Sequence
, typename _Category
,
133 typename _InputIterator
>
135 __foreign_iterator_aux3(
136 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&,
137 const _InputIterator
&, const _InputIterator
&,
141 /** Handle debug iterators from the same type of container. */
142 template<typename _Iterator
, typename _Sequence
, typename _Category
,
143 typename _OtherIterator
>
145 __foreign_iterator_aux2(
146 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
147 const _Safe_iterator
<_OtherIterator
, _Sequence
, _Category
>& __other
,
148 const _Safe_iterator
<_OtherIterator
, _Sequence
, _Category
>&)
149 { return __it
._M_get_sequence() != __other
._M_get_sequence(); }
151 /** Handle debug iterators from different types of container. */
152 template<typename _Iterator
, typename _Sequence
, typename _Category
,
153 typename _OtherIterator
, typename _OtherSequence
,
154 typename _OtherCategory
>
156 __foreign_iterator_aux2(
157 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&,
158 const _Safe_iterator
<_OtherIterator
, _OtherSequence
,
160 const _Safe_iterator
<_OtherIterator
, _OtherSequence
,
164 /* Handle non-debug iterators. */
165 template<typename _Iterator
, typename _Sequence
, typename _Category
,
166 typename _InputIterator
>
168 __foreign_iterator_aux2(
169 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
170 const _InputIterator
& __other
,
171 const _InputIterator
& __other_end
)
173 #if __cplusplus < 201103L
174 typedef _Is_contiguous_sequence
<_Sequence
> __tag
;
176 using __lvalref
= std::is_lvalue_reference
<
177 typename
std::iterator_traits
<_InputIterator
>::reference
>;
178 using __contiguous
= _Is_contiguous_sequence
<_Sequence
>;
179 using __tag
= typename
std::conditional
<__lvalref::value
, __contiguous
,
180 std::__false_type
>::type
;
182 return __foreign_iterator_aux3(__it
, __other
, __other_end
, __tag());
185 /* Handle the case where we aren't really inserting a range after all */
186 template<typename _Iterator
, typename _Sequence
, typename _Category
,
189 __foreign_iterator_aux(
190 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>&,
191 _Integral
, _Integral
, std::__true_type
)
194 /* Handle all iterators. */
195 template<typename _Iterator
, typename _Sequence
, typename _Category
,
196 typename _InputIterator
>
198 __foreign_iterator_aux(
199 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
200 _InputIterator __other
, _InputIterator __other_end
,
203 return _Insert_range_from_self_is_safe
<_Sequence
>::__value
204 || __foreign_iterator_aux2(__it
, std::__miter_base(__other
),
205 std::__miter_base(__other_end
));
208 template<typename _Iterator
, typename _Sequence
, typename _Category
,
209 typename _InputIterator
>
212 const _Safe_iterator
<_Iterator
, _Sequence
, _Category
>& __it
,
213 _InputIterator __other
, _InputIterator __other_end
)
215 typedef typename
std::__is_integer
<_InputIterator
>::__type _Integral
;
216 return __foreign_iterator_aux(__it
, __other
, __other_end
, _Integral());
219 // Can't check if an input iterator sequence is sorted, because we
220 // can't step through the sequence.
221 template<typename _InputIterator
>
223 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
224 std::input_iterator_tag
)
227 // Can verify if a forward iterator sequence is in fact sorted using
229 template<typename _ForwardIterator
>
231 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
232 std::forward_iterator_tag
)
234 if (__first
== __last
)
237 _ForwardIterator __next
= __first
;
238 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
239 if (*__next
< *__first
)
245 // Can't check if an input iterator sequence is sorted, because we can't step
246 // through the sequence.
247 template<typename _InputIterator
, typename _Predicate
>
249 __check_sorted_aux(const _InputIterator
&, const _InputIterator
&,
250 _Predicate
, std::input_iterator_tag
)
253 // Can verify if a forward iterator sequence is in fact sorted using
255 template<typename _ForwardIterator
, typename _Predicate
>
257 __check_sorted_aux(_ForwardIterator __first
, _ForwardIterator __last
,
258 _Predicate __pred
, std::forward_iterator_tag
)
260 if (__first
== __last
)
263 _ForwardIterator __next
= __first
;
264 for (++__next
; __next
!= __last
; __first
= __next
, (void)++__next
)
265 if (__pred(*__next
, *__first
))
271 // Determine if a sequence is sorted.
272 template<typename _InputIterator
>
274 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
)
276 // Verify that the < operator for elements in the sequence is a
277 // StrictWeakOrdering by checking that it is irreflexive.
278 __glibcxx_assert(__first
== __last
|| !(*__first
< *__first
));
280 return __check_sorted_aux(__first
, __last
,
281 std::__iterator_category(__first
));
284 template<typename _InputIterator
, typename _Predicate
>
286 __check_sorted(const _InputIterator
& __first
, const _InputIterator
& __last
,
289 // Verify that the predicate is StrictWeakOrdering by checking that it
291 __glibcxx_assert(__first
== __last
|| !__pred(*__first
, *__first
));
293 return __check_sorted_aux(__first
, __last
, __pred
,
294 std::__iterator_category(__first
));
297 template<typename _InputIterator
>
299 __check_sorted_set_aux(const _InputIterator
& __first
,
300 const _InputIterator
& __last
,
302 { return __check_sorted(__first
, __last
); }
304 template<typename _InputIterator
>
306 __check_sorted_set_aux(const _InputIterator
&,
307 const _InputIterator
&,
311 template<typename _InputIterator
, typename _Predicate
>
313 __check_sorted_set_aux(const _InputIterator
& __first
,
314 const _InputIterator
& __last
,
315 _Predicate __pred
, std::__true_type
)
316 { return __check_sorted(__first
, __last
, __pred
); }
318 template<typename _InputIterator
, typename _Predicate
>
320 __check_sorted_set_aux(const _InputIterator
&,
321 const _InputIterator
&, _Predicate
,
325 // ... special variant used in std::merge, std::includes, std::set_*.
326 template<typename _InputIterator1
, typename _InputIterator2
>
328 __check_sorted_set(const _InputIterator1
& __first
,
329 const _InputIterator1
& __last
,
330 const _InputIterator2
&)
332 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
334 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
337 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
339 return __check_sorted_set_aux(__first
, __last
, _SameType());
342 template<typename _InputIterator1
, typename _InputIterator2
,
345 __check_sorted_set(const _InputIterator1
& __first
,
346 const _InputIterator1
& __last
,
347 const _InputIterator2
&, _Predicate __pred
)
349 typedef typename
std::iterator_traits
<_InputIterator1
>::value_type
351 typedef typename
std::iterator_traits
<_InputIterator2
>::value_type
354 typedef typename
std::__are_same
<_ValueType1
, _ValueType2
>::__type
356 return __check_sorted_set_aux(__first
, __last
, __pred
, _SameType());
359 // _GLIBCXX_RESOLVE_LIB_DEFECTS
360 // 270. Binary search requirements overly strict
361 // Determine if a sequence is partitioned w.r.t. this element.
362 template<typename _ForwardIterator
, typename _Tp
>
364 __check_partitioned_lower(_ForwardIterator __first
,
365 _ForwardIterator __last
, const _Tp
& __value
)
367 while (__first
!= __last
&& *__first
< __value
)
369 if (__first
!= __last
)
372 while (__first
!= __last
&& !(*__first
< __value
))
375 return __first
== __last
;
378 template<typename _ForwardIterator
, typename _Tp
>
380 __check_partitioned_upper(_ForwardIterator __first
,
381 _ForwardIterator __last
, const _Tp
& __value
)
383 while (__first
!= __last
&& !(__value
< *__first
))
385 if (__first
!= __last
)
388 while (__first
!= __last
&& __value
< *__first
)
391 return __first
== __last
;
394 // Determine if a sequence is partitioned w.r.t. this element.
395 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
397 __check_partitioned_lower(_ForwardIterator __first
,
398 _ForwardIterator __last
, const _Tp
& __value
,
401 while (__first
!= __last
&& bool(__pred(*__first
, __value
)))
403 if (__first
!= __last
)
406 while (__first
!= __last
&& !bool(__pred(*__first
, __value
)))
409 return __first
== __last
;
412 template<typename _ForwardIterator
, typename _Tp
, typename _Pred
>
414 __check_partitioned_upper(_ForwardIterator __first
,
415 _ForwardIterator __last
, const _Tp
& __value
,
418 while (__first
!= __last
&& !bool(__pred(__value
, *__first
)))
420 if (__first
!= __last
)
423 while (__first
!= __last
&& bool(__pred(__value
, *__first
)))
426 return __first
== __last
;
429 #if __cplusplus >= 201103L
430 struct _Irreflexive_checker
432 template<typename _It
>
433 static typename
std::iterator_traits
<_It
>::reference
436 template<typename _It
,
437 typename
= decltype(__deref
<_It
>() < __deref
<_It
>())>
439 _S_is_valid(_It __it
)
440 { return !(*__it
< *__it
); }
442 // Fallback method if operator doesn't exist.
443 template<typename
... _Args
>
445 _S_is_valid(_Args
...)
448 template<typename _It
, typename _Pred
, typename
449 = decltype(std::declval
<_Pred
>()(__deref
<_It
>(), __deref
<_It
>()))>
451 _S_is_valid_pred(_It __it
, _Pred __pred
)
452 { return !__pred(*__it
, *__it
); }
454 // Fallback method if predicate can't be invoked.
455 template<typename
... _Args
>
457 _S_is_valid_pred(_Args
...)
461 template<typename _Iterator
>
463 __is_irreflexive(_Iterator __it
)
464 { return _Irreflexive_checker::_S_is_valid(__it
); }
466 template<typename _Iterator
, typename _Pred
>
468 __is_irreflexive_pred(_Iterator __it
, _Pred __pred
)
469 { return _Irreflexive_checker::_S_is_valid_pred(__it
, __pred
); }
472 } // namespace __gnu_debug