1 // Debugging support implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2014 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/c++config.h> 33 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and 34 // _Iter_base 35 #include <bits/cpp_type_traits.h> // for __is_integer 36 #include <bits/move.h> // for __addressof and addressof 37 # include <bits/stl_function.h> // for less 38 #if __cplusplus >= 201103L 39 # include <type_traits> // for is_lvalue_reference and __and_ 40 #endif 41 #include <debug/formatter.h> 42 43 namespace __gnu_debug 44 { 45 template<typename _Iterator, typename _Sequence> 46 class _Safe_iterator; 47 48 template<typename _Iterator, typename _Sequence> 49 class _Safe_local_iterator; 50 51 template<typename _Sequence> 52 struct _Insert_range_from_self_is_safe 53 { enum { __value = 0 }; }; 54 55 template<typename _Sequence> 56 struct _Is_contiguous_sequence : std::__false_type { }; 57 58 // An arbitrary iterator pointer is not singular. 59 inline bool 60 __check_singular_aux(const void*) { return false; } 61 62 // We may have an iterator that derives from _Safe_iterator_base but isn't 63 // a _Safe_iterator. 64 template<typename _Iterator> 65 inline bool 66 __check_singular(const _Iterator& __x) 67 { return __check_singular_aux(&__x); } 68 69 /** Non-NULL pointers are nonsingular. */ 70 template<typename _Tp> 71 inline bool 72 __check_singular(const _Tp* __ptr) 73 { return __ptr == 0; } 74 75 /** Assume that some arbitrary iterator is dereferenceable, because we 76 can't prove that it isn't. */ 77 template<typename _Iterator> 78 inline bool 79 __check_dereferenceable(const _Iterator&) 80 { return true; } 81 82 /** Non-NULL pointers are dereferenceable. */ 83 template<typename _Tp> 84 inline bool 85 __check_dereferenceable(const _Tp* __ptr) 86 { return __ptr; } 87 88 /** Safe iterators know if they are dereferenceable. */ 89 template<typename _Iterator, typename _Sequence> 90 inline bool 91 __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) 92 { return __x._M_dereferenceable(); } 93 94 /** Safe local iterators know if they are dereferenceable. */ 95 template<typename _Iterator, typename _Sequence> 96 inline bool 97 __check_dereferenceable(const _Safe_local_iterator<_Iterator, 98 _Sequence>& __x) 99 { return __x._M_dereferenceable(); } 100 101 /** If the distance between two random access iterators is 102 * nonnegative, assume the range is valid. 103 */ 104 template<typename _RandomAccessIterator> 105 inline bool 106 __valid_range_aux2(const _RandomAccessIterator& __first, 107 const _RandomAccessIterator& __last, 108 std::random_access_iterator_tag) 109 { return __last - __first >= 0; } 110 111 /** Can't test for a valid range with input iterators, because 112 * iteration may be destructive. So we just assume that the range 113 * is valid. 114 */ 115 template<typename _InputIterator> 116 inline bool 117 __valid_range_aux2(const _InputIterator&, const _InputIterator&, 118 std::input_iterator_tag) 119 { return true; } 120 121 /** We say that integral types for a valid range, and defer to other 122 * routines to realize what to do with integral types instead of 123 * iterators. 124 */ 125 template<typename _Integral> 126 inline bool 127 __valid_range_aux(const _Integral&, const _Integral&, std::__true_type) 128 { return true; } 129 130 /** We have iterators, so figure out what kind of iterators that are 131 * to see if we can check the range ahead of time. 132 */ 133 template<typename _InputIterator> 134 inline bool 135 __valid_range_aux(const _InputIterator& __first, 136 const _InputIterator& __last, std::__false_type) 137 { return __valid_range_aux2(__first, __last, 138 std::__iterator_category(__first)); } 139 140 /** Don't know what these iterators are, or if they are even 141 * iterators (we may get an integral type for InputIterator), so 142 * see if they are integral and pass them on to the next phase 143 * otherwise. 144 */ 145 template<typename _InputIterator> 146 inline bool 147 __valid_range(const _InputIterator& __first, const _InputIterator& __last) 148 { 149 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 150 return __valid_range_aux(__first, __last, _Integral()); 151 } 152 153 /** Safe iterators know how to check if they form a valid range. */ 154 template<typename _Iterator, typename _Sequence> 155 inline bool 156 __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, 157 const _Safe_iterator<_Iterator, _Sequence>& __last) 158 { return __first._M_valid_range(__last); } 159 160 /** Safe local iterators know how to check if they form a valid range. */ 161 template<typename _Iterator, typename _Sequence> 162 inline bool 163 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 164 const _Safe_local_iterator<_Iterator, _Sequence>& __last) 165 { return __first._M_valid_range(__last); } 166 167 /* Checks that [first, last) is a valid range, and then returns 168 * __first. This routine is useful when we can't use a separate 169 * assertion statement because, e.g., we are in a constructor. 170 */ 171 template<typename _InputIterator> 172 inline _InputIterator 173 __check_valid_range(const _InputIterator& __first, 174 const _InputIterator& __last 175 __attribute__((__unused__))) 176 { 177 __glibcxx_check_valid_range(__first, __last); 178 return __first; 179 } 180 181 /* Handle the case where __other is a pointer to _Sequence::value_type. */ 182 template<typename _Iterator, typename _Sequence> 183 inline bool 184 __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it, 185 const typename _Sequence::value_type* __other) 186 { 187 typedef const typename _Sequence::value_type* _PointerType; 188 typedef std::less<_PointerType> _Less; 189 #if __cplusplus >= 201103L 190 constexpr _Less __l{}; 191 #else 192 const _Less __l = _Less(); 193 #endif 194 const _Sequence* __seq = __it._M_get_sequence(); 195 const _PointerType __begin = std::__addressof(*__seq->_M_base().begin()); 196 const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1)); 197 198 // Check whether __other points within the contiguous storage. 199 return __l(__other, __begin) || __l(__end, __other); 200 } 201 202 /* Fallback overload for when we can't tell, assume it is valid. */ 203 template<typename _Iterator, typename _Sequence> 204 inline bool 205 __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...) 206 { return true; } 207 208 /* Handle sequences with contiguous storage */ 209 template<typename _Iterator, typename _Sequence, typename _InputIterator> 210 inline bool 211 __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, 212 const _InputIterator& __other, 213 const _InputIterator& __other_end, 214 std::__true_type) 215 { 216 if (__other == __other_end) 217 return true; // inserting nothing is safe even if not foreign iters 218 if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end()) 219 return true; // can't be self-inserting if self is empty 220 return __foreign_iterator_aux4(__it, std::__addressof(*__other)); 221 } 222 223 /* Handle non-contiguous containers, assume it is valid. */ 224 template<typename _Iterator, typename _Sequence, typename _InputIterator> 225 inline bool 226 __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&, 227 const _InputIterator&, const _InputIterator&, 228 std::__false_type) 229 { return true; } 230 231 /** Handle debug iterators from the same type of container. */ 232 template<typename _Iterator, typename _Sequence, typename _OtherIterator> 233 inline bool 234 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 235 const _Safe_iterator<_OtherIterator, _Sequence>& __other, 236 const _Safe_iterator<_OtherIterator, _Sequence>&) 237 { return __it._M_get_sequence() != __other._M_get_sequence(); } 238 239 /** Handle debug iterators from different types of container. */ 240 template<typename _Iterator, typename _Sequence, typename _OtherIterator, 241 typename _OtherSequence> 242 inline bool 243 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 244 const _Safe_iterator<_OtherIterator, _OtherSequence>&, 245 const _Safe_iterator<_OtherIterator, _OtherSequence>&) 246 { return true; } 247 248 /* Handle non-debug iterators. */ 249 template<typename _Iterator, typename _Sequence, typename _InputIterator> 250 inline bool 251 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 252 const _InputIterator& __other, 253 const _InputIterator& __other_end) 254 { 255 return __foreign_iterator_aux3(__it, __other, __other_end, 256 _Is_contiguous_sequence<_Sequence>()); 257 } 258 259 /* Handle the case where we aren't really inserting a range after all */ 260 template<typename _Iterator, typename _Sequence, typename _Integral> 261 inline bool 262 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&, 263 _Integral, _Integral, 264 std::__true_type) 265 { return true; } 266 267 /* Handle all iterators. */ 268 template<typename _Iterator, typename _Sequence, 269 typename _InputIterator> 270 inline bool 271 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it, 272 _InputIterator __other, _InputIterator __other_end, 273 std::__false_type) 274 { 275 return _Insert_range_from_self_is_safe<_Sequence>::__value 276 || __foreign_iterator_aux2(__it, __other, __other_end); 277 } 278 279 template<typename _Iterator, typename _Sequence, 280 typename _InputIterator> 281 inline bool 282 __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it, 283 _InputIterator __other, _InputIterator __other_end) 284 { 285 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 286 return __foreign_iterator_aux(__it, __other, __other_end, _Integral()); 287 } 288 289 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 290 template<typename _CharT, typename _Integer> 291 inline const _CharT* 292 __check_string(const _CharT* __s, 293 const _Integer& __n __attribute__((__unused__))) 294 { 295 #ifdef _GLIBCXX_DEBUG_PEDANTIC 296 __glibcxx_assert(__s != 0 || __n == 0); 297 #endif 298 return __s; 299 } 300 301 /** Checks that __s is non-NULL and then returns __s. */ 302 template<typename _CharT> 303 inline const _CharT* 304 __check_string(const _CharT* __s) 305 { 306 #ifdef _GLIBCXX_DEBUG_PEDANTIC 307 __glibcxx_assert(__s != 0); 308 #endif 309 return __s; 310 } 311 312 // Can't check if an input iterator sequence is sorted, because we 313 // can't step through the sequence. 314 template<typename _InputIterator> 315 inline bool 316 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 317 std::input_iterator_tag) 318 { return true; } 319 320 // Can verify if a forward iterator sequence is in fact sorted using 321 // std::__is_sorted 322 template<typename _ForwardIterator> 323 inline bool 324 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 325 std::forward_iterator_tag) 326 { 327 if (__first == __last) 328 return true; 329 330 _ForwardIterator __next = __first; 331 for (++__next; __next != __last; __first = __next, ++__next) 332 if (*__next < *__first) 333 return false; 334 335 return true; 336 } 337 338 // Can't check if an input iterator sequence is sorted, because we can't step 339 // through the sequence. 340 template<typename _InputIterator, typename _Predicate> 341 inline bool 342 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 343 _Predicate, std::input_iterator_tag) 344 { return true; } 345 346 // Can verify if a forward iterator sequence is in fact sorted using 347 // std::__is_sorted 348 template<typename _ForwardIterator, typename _Predicate> 349 inline bool 350 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 351 _Predicate __pred, std::forward_iterator_tag) 352 { 353 if (__first == __last) 354 return true; 355 356 _ForwardIterator __next = __first; 357 for (++__next; __next != __last; __first = __next, ++__next) 358 if (__pred(*__next, *__first)) 359 return false; 360 361 return true; 362 } 363 364 // Determine if a sequence is sorted. 365 template<typename _InputIterator> 366 inline bool 367 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 368 { 369 // Verify that the < operator for elements in the sequence is a 370 // StrictWeakOrdering by checking that it is irreflexive. 371 __glibcxx_assert(__first == __last || !(*__first < *__first)); 372 373 return __check_sorted_aux(__first, __last, 374 std::__iterator_category(__first)); 375 } 376 377 template<typename _InputIterator, typename _Predicate> 378 inline bool 379 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 380 _Predicate __pred) 381 { 382 // Verify that the predicate is StrictWeakOrdering by checking that it 383 // is irreflexive. 384 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 385 386 return __check_sorted_aux(__first, __last, __pred, 387 std::__iterator_category(__first)); 388 } 389 390 template<typename _InputIterator> 391 inline bool 392 __check_sorted_set_aux(const _InputIterator& __first, 393 const _InputIterator& __last, 394 std::__true_type) 395 { return __check_sorted(__first, __last); } 396 397 template<typename _InputIterator> 398 inline bool 399 __check_sorted_set_aux(const _InputIterator&, 400 const _InputIterator&, 401 std::__false_type) 402 { return true; } 403 404 template<typename _InputIterator, typename _Predicate> 405 inline bool 406 __check_sorted_set_aux(const _InputIterator& __first, 407 const _InputIterator& __last, 408 _Predicate __pred, std::__true_type) 409 { return __check_sorted(__first, __last, __pred); } 410 411 template<typename _InputIterator, typename _Predicate> 412 inline bool 413 __check_sorted_set_aux(const _InputIterator&, 414 const _InputIterator&, _Predicate, 415 std::__false_type) 416 { return true; } 417 418 // ... special variant used in std::merge, std::includes, std::set_*. 419 template<typename _InputIterator1, typename _InputIterator2> 420 inline bool 421 __check_sorted_set(const _InputIterator1& __first, 422 const _InputIterator1& __last, 423 const _InputIterator2&) 424 { 425 typedef typename std::iterator_traits<_InputIterator1>::value_type 426 _ValueType1; 427 typedef typename std::iterator_traits<_InputIterator2>::value_type 428 _ValueType2; 429 430 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 431 _SameType; 432 return __check_sorted_set_aux(__first, __last, _SameType()); 433 } 434 435 template<typename _InputIterator1, typename _InputIterator2, 436 typename _Predicate> 437 inline bool 438 __check_sorted_set(const _InputIterator1& __first, 439 const _InputIterator1& __last, 440 const _InputIterator2&, _Predicate __pred) 441 { 442 typedef typename std::iterator_traits<_InputIterator1>::value_type 443 _ValueType1; 444 typedef typename std::iterator_traits<_InputIterator2>::value_type 445 _ValueType2; 446 447 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 448 _SameType; 449 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 450 } 451 452 // _GLIBCXX_RESOLVE_LIB_DEFECTS 453 // 270. Binary search requirements overly strict 454 // Determine if a sequence is partitioned w.r.t. this element. 455 template<typename _ForwardIterator, typename _Tp> 456 inline bool 457 __check_partitioned_lower(_ForwardIterator __first, 458 _ForwardIterator __last, const _Tp& __value) 459 { 460 while (__first != __last && *__first < __value) 461 ++__first; 462 if (__first != __last) 463 { 464 ++__first; 465 while (__first != __last && !(*__first < __value)) 466 ++__first; 467 } 468 return __first == __last; 469 } 470 471 template<typename _ForwardIterator, typename _Tp> 472 inline bool 473 __check_partitioned_upper(_ForwardIterator __first, 474 _ForwardIterator __last, const _Tp& __value) 475 { 476 while (__first != __last && !(__value < *__first)) 477 ++__first; 478 if (__first != __last) 479 { 480 ++__first; 481 while (__first != __last && __value < *__first) 482 ++__first; 483 } 484 return __first == __last; 485 } 486 487 // Determine if a sequence is partitioned w.r.t. this element. 488 template<typename _ForwardIterator, typename _Tp, typename _Pred> 489 inline bool 490 __check_partitioned_lower(_ForwardIterator __first, 491 _ForwardIterator __last, const _Tp& __value, 492 _Pred __pred) 493 { 494 while (__first != __last && bool(__pred(*__first, __value))) 495 ++__first; 496 if (__first != __last) 497 { 498 ++__first; 499 while (__first != __last && !bool(__pred(*__first, __value))) 500 ++__first; 501 } 502 return __first == __last; 503 } 504 505 template<typename _ForwardIterator, typename _Tp, typename _Pred> 506 inline bool 507 __check_partitioned_upper(_ForwardIterator __first, 508 _ForwardIterator __last, const _Tp& __value, 509 _Pred __pred) 510 { 511 while (__first != __last && !bool(__pred(__value, *__first))) 512 ++__first; 513 if (__first != __last) 514 { 515 ++__first; 516 while (__first != __last && bool(__pred(__value, *__first))) 517 ++__first; 518 } 519 return __first == __last; 520 } 521 522 // Helper struct to detect random access safe iterators. 523 template<typename _Iterator> 524 struct __is_safe_random_iterator 525 { 526 enum { __value = 0 }; 527 typedef std::__false_type __type; 528 }; 529 530 template<typename _Iterator, typename _Sequence> 531 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > 532 : std::__are_same<std::random_access_iterator_tag, 533 typename std::iterator_traits<_Iterator>:: 534 iterator_category> 535 { }; 536 537 template<typename _Iterator> 538 struct _Siter_base 539 : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> 540 { }; 541 542 /** Helper function to extract base iterator of random access safe iterator 543 in order to reduce performance impact of debug mode. Limited to random 544 access iterator because it is the only category for which it is possible 545 to check for correct iterators order in the __valid_range function 546 thanks to the < operator. 547 */ 548 template<typename _Iterator> 549 inline typename _Siter_base<_Iterator>::iterator_type 550 __base(_Iterator __it) 551 { return _Siter_base<_Iterator>::_S_base(__it); } 552 } // namespace __gnu_debug 553 554 #endif 555
