libstdc++
functions.h
Go to the documentation of this file.
1// Debugging support implementation -*- C++ -*-
2
3// Copyright (C) 2003-2019 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/move.h> // for __addressof
33#include <bits/stl_function.h> // for less
34
35#if __cplusplus >= 201103L
36# include <bits/stl_iterator.h> // for __miter_base
37# include <type_traits> // for is_lvalue_reference and conditional.
38#endif
39
41#include <debug/formatter.h>
42
43namespace __gnu_debug
44{
45 template<typename _Sequence>
46 struct _Insert_range_from_self_is_safe
47 { enum { __value = 0 }; };
48
49 template<typename _Sequence>
50 struct _Is_contiguous_sequence : std::__false_type { };
51
52 // An arbitrary iterator pointer is not singular.
53 inline bool
54 __check_singular_aux(const void*) { return false; }
55
56 // We may have an iterator that derives from _Safe_iterator_base but isn't
57 // a _Safe_iterator.
58 template<typename _Iterator>
59 inline bool
60 __check_singular(const _Iterator& __x)
61 { return __check_singular_aux(std::__addressof(__x)); }
62
63 /** Non-NULL pointers are nonsingular. */
64 template<typename _Tp>
65 inline bool
66 __check_singular(const _Tp* __ptr)
67 { return __ptr == 0; }
68
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.
72 */
73 template<typename _InputIterator>
74 inline _InputIterator
75 __check_valid_range(const _InputIterator& __first,
76 const _InputIterator& __last,
77 const char* __file,
78 unsigned int __line,
79 const char* __function)
80 {
81 __glibcxx_check_valid_range_at(__first, __last,
82 __file, __line, __function);
83 return __first;
84 }
85
86 /* Handle the case where __other is a pointer to _Sequence::value_type. */
87 template<typename _Iterator, typename _Sequence, typename _Category>
88 inline bool
89 __foreign_iterator_aux4(
90 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
91 const typename _Sequence::value_type* __other)
92 {
93 typedef const typename _Sequence::value_type* _PointerType;
94 typedef std::less<_PointerType> _Less;
95#if __cplusplus >= 201103L
96 constexpr _Less __l{};
97#else
98 const _Less __l = _Less();
99#endif
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));
103
104 // Check whether __other points within the contiguous storage.
105 return __l(__other, __begin) || __l(__end, __other);
106 }
107
108 /* Fallback overload for when we can't tell, assume it is valid. */
109 template<typename _Iterator, typename _Sequence, typename _Category>
110 inline bool
111 __foreign_iterator_aux4(
112 const _Safe_iterator<_Iterator, _Sequence, _Category>&, ...)
113 { return true; }
114
115 /* Handle sequences with contiguous storage */
116 template<typename _Iterator, typename _Sequence, typename _Category,
117 typename _InputIterator>
118 inline bool
119 __foreign_iterator_aux3(
120 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
121 const _InputIterator& __other, const _InputIterator& __other_end,
122 std::__true_type)
123 {
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));
129 }
130
131 /* Handle non-contiguous containers, assume it is valid. */
132 template<typename _Iterator, typename _Sequence, typename _Category,
133 typename _InputIterator>
134 inline bool
135 __foreign_iterator_aux3(
136 const _Safe_iterator<_Iterator, _Sequence, _Category>&,
137 const _InputIterator&, const _InputIterator&,
138 std::__false_type)
139 { return true; }
140
141 /** Handle debug iterators from the same type of container. */
142 template<typename _Iterator, typename _Sequence, typename _Category,
143 typename _OtherIterator>
144 inline bool
149 { return __it._M_get_sequence() != __other._M_get_sequence(); }
150
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>
155 inline bool
158 const _Safe_iterator<_OtherIterator, _OtherSequence,
159 _OtherCategory>&,
160 const _Safe_iterator<_OtherIterator, _OtherSequence,
161 _OtherCategory>&)
162 { return true; }
163
164 /* Handle non-debug iterators. */
165 template<typename _Iterator, typename _Sequence, typename _Category,
166 typename _InputIterator>
167 inline bool
169 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
170 const _InputIterator& __other,
171 const _InputIterator& __other_end)
172 {
173#if __cplusplus < 201103L
174 typedef _Is_contiguous_sequence<_Sequence> __tag;
175#else
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;
181#endif
182 return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
183 }
184
185 /* Handle the case where we aren't really inserting a range after all */
186 template<typename _Iterator, typename _Sequence, typename _Category,
187 typename _Integral>
188 inline bool
189 __foreign_iterator_aux(
190 const _Safe_iterator<_Iterator, _Sequence, _Category>&,
191 _Integral, _Integral, std::__true_type)
192 { return true; }
193
194 /* Handle all iterators. */
195 template<typename _Iterator, typename _Sequence, typename _Category,
196 typename _InputIterator>
197 inline bool
198 __foreign_iterator_aux(
199 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
200 _InputIterator __other, _InputIterator __other_end,
201 std::__false_type)
202 {
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));
206 }
207
208 template<typename _Iterator, typename _Sequence, typename _Category,
209 typename _InputIterator>
210 inline bool
211 __foreign_iterator(
212 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it,
213 _InputIterator __other, _InputIterator __other_end)
214 {
215 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
216 return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
217 }
218
219 // Can't check if an input iterator sequence is sorted, because we
220 // can't step through the sequence.
221 template<typename _InputIterator>
222 inline bool
223 __check_sorted_aux(const _InputIterator&, const _InputIterator&,
225 { return true; }
226
227 // Can verify if a forward iterator sequence is in fact sorted using
228 // std::__is_sorted
229 template<typename _ForwardIterator>
230 inline bool
231 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
233 {
234 if (__first == __last)
235 return true;
236
237 _ForwardIterator __next = __first;
238 for (++__next; __next != __last; __first = __next, (void)++__next)
239 if (*__next < *__first)
240 return false;
241
242 return true;
243 }
244
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>
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 inline bool
257 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
258 _Predicate __pred, std::forward_iterator_tag)
259 {
260 if (__first == __last)
261 return true;
262
263 _ForwardIterator __next = __first;
264 for (++__next; __next != __last; __first = __next, (void)++__next)
265 if (__pred(*__next, *__first))
266 return false;
267
268 return true;
269 }
270
271 // Determine if a sequence is sorted.
272 template<typename _InputIterator>
273 inline bool
274 __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
275 {
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));
279
280 return __check_sorted_aux(__first, __last,
281 std::__iterator_category(__first));
282 }
283
284 template<typename _InputIterator, typename _Predicate>
285 inline bool
286 __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
287 _Predicate __pred)
288 {
289 // Verify that the predicate is StrictWeakOrdering by checking that it
290 // is irreflexive.
291 __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
292
293 return __check_sorted_aux(__first, __last, __pred,
294 std::__iterator_category(__first));
295 }
296
297 template<typename _InputIterator>
298 inline bool
299 __check_sorted_set_aux(const _InputIterator& __first,
300 const _InputIterator& __last,
301 std::__true_type)
302 { return __check_sorted(__first, __last); }
303
304 template<typename _InputIterator>
305 inline bool
306 __check_sorted_set_aux(const _InputIterator&,
307 const _InputIterator&,
308 std::__false_type)
309 { return true; }
310
311 template<typename _InputIterator, typename _Predicate>
312 inline bool
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); }
317
318 template<typename _InputIterator, typename _Predicate>
319 inline bool
320 __check_sorted_set_aux(const _InputIterator&,
321 const _InputIterator&, _Predicate,
322 std::__false_type)
323 { return true; }
324
325 // ... special variant used in std::merge, std::includes, std::set_*.
326 template<typename _InputIterator1, typename _InputIterator2>
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 inline bool
345 __check_sorted_set(const _InputIterator1& __first,
346 const _InputIterator1& __last,
347 const _InputIterator2&, _Predicate __pred)
348 {
349 typedef typename std::iterator_traits<_InputIterator1>::value_type
350 _ValueType1;
351 typedef typename std::iterator_traits<_InputIterator2>::value_type
352 _ValueType2;
353
354 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
355 _SameType;
356 return __check_sorted_set_aux(__first, __last, __pred, _SameType());
357 }
358
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>
363 inline bool
364 __check_partitioned_lower(_ForwardIterator __first,
365 _ForwardIterator __last, const _Tp& __value)
366 {
367 while (__first != __last && *__first < __value)
368 ++__first;
369 if (__first != __last)
370 {
371 ++__first;
372 while (__first != __last && !(*__first < __value))
373 ++__first;
374 }
375 return __first == __last;
376 }
377
378 template<typename _ForwardIterator, typename _Tp>
379 inline bool
380 __check_partitioned_upper(_ForwardIterator __first,
381 _ForwardIterator __last, const _Tp& __value)
382 {
383 while (__first != __last && !(__value < *__first))
384 ++__first;
385 if (__first != __last)
386 {
387 ++__first;
388 while (__first != __last && __value < *__first)
389 ++__first;
390 }
391 return __first == __last;
392 }
393
394 // Determine if a sequence is partitioned w.r.t. this element.
395 template<typename _ForwardIterator, typename _Tp, typename _Pred>
396 inline bool
397 __check_partitioned_lower(_ForwardIterator __first,
398 _ForwardIterator __last, const _Tp& __value,
399 _Pred __pred)
400 {
401 while (__first != __last && bool(__pred(*__first, __value)))
402 ++__first;
403 if (__first != __last)
404 {
405 ++__first;
406 while (__first != __last && !bool(__pred(*__first, __value)))
407 ++__first;
408 }
409 return __first == __last;
410 }
411
412 template<typename _ForwardIterator, typename _Tp, typename _Pred>
413 inline bool
414 __check_partitioned_upper(_ForwardIterator __first,
415 _ForwardIterator __last, const _Tp& __value,
416 _Pred __pred)
417 {
418 while (__first != __last && !bool(__pred(__value, *__first)))
419 ++__first;
420 if (__first != __last)
421 {
422 ++__first;
423 while (__first != __last && bool(__pred(__value, *__first)))
424 ++__first;
425 }
426 return __first == __last;
427 }
428
429#if __cplusplus >= 201103L
430 struct _Irreflexive_checker
431 {
432 template<typename _It>
433 static typename std::iterator_traits<_It>::reference
434 __ref();
435
436 template<typename _It,
437 typename = decltype(__ref<_It>() < __ref<_It>())>
438 static bool
439 _S_is_valid(_It __it)
440 { return !(*__it < *__it); }
441
442 // Fallback method if operator doesn't exist.
443 template<typename... _Args>
444 static bool
445 _S_is_valid(_Args...)
446 { return true; }
447
448 template<typename _It, typename _Pred, typename
449 = decltype(std::declval<_Pred>()(__ref<_It>(), __ref<_It>()))>
450 static bool
451 _S_is_valid_pred(_It __it, _Pred __pred)
452 { return !__pred(*__it, *__it); }
453
454 // Fallback method if predicate can't be invoked.
455 template<typename... _Args>
456 static bool
457 _S_is_valid_pred(_Args...)
458 { return true; }
459 };
460
461 template<typename _Iterator>
462 inline bool
463 __is_irreflexive(_Iterator __it)
464 { return _Irreflexive_checker::_S_is_valid(__it); }
465
466 template<typename _Iterator, typename _Pred>
467 inline bool
468 __is_irreflexive_pred(_Iterator __it, _Pred __pred)
469 { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); }
470#endif
471
472} // namespace __gnu_debug
473
474#endif
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:47
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
GNU debug classes for public use.
bool __foreign_iterator_aux2(const _Safe_iterator< _Iterator, _Sequence, _Category > &__it, const _Safe_iterator< _OtherIterator, _Sequence, _Category > &__other, const _Safe_iterator< _OtherIterator, _Sequence, _Category > &)
Definition: functions.h:145
Define a member typedef type to one of two argument types.
Definition: type_traits:2054
is_lvalue_reference
Definition: type_traits:386
One of the comparison functors.
Definition: stl_function.h:382
Marking input iterators.
Forward iterators support a superset of input iterator operations.
Safe iterator wrapper.