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