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