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 // _GLIBCXX_RESOLVE_LIB_DEFECTS 349 // 270. Binary search requirements overly strict 350 // Determine if a sequence is partitioned w.r.t. this element. 351 template<typename _ForwardIterator, typename _Tp> 352 inline bool 353 __check_partitioned_lower(_ForwardIterator __first, 354 _ForwardIterator __last, const _Tp& __value) 355 { 356 while (__first != __last && *__first < __value) 357 ++__first; 358 if (__first != __last) 359 { 360 ++__first; 361 while (__first != __last && !(*__first < __value)) 362 ++__first; 363 } 364 return __first == __last; 365 } 366 367 template<typename _ForwardIterator, typename _Tp> 368 inline bool 369 __check_partitioned_upper(_ForwardIterator __first, 370 _ForwardIterator __last, const _Tp& __value) 371 { 372 while (__first != __last && !(__value < *__first)) 373 ++__first; 374 if (__first != __last) 375 { 376 ++__first; 377 while (__first != __last && __value < *__first) 378 ++__first; 379 } 380 return __first == __last; 381 } 382 383 // Determine if a sequence is partitioned w.r.t. this element. 384 template<typename _ForwardIterator, typename _Tp, typename _Pred> 385 inline bool 386 __check_partitioned_lower(_ForwardIterator __first, 387 _ForwardIterator __last, const _Tp& __value, 388 _Pred __pred) 389 { 390 while (__first != __last && bool(__pred(*__first, __value))) 391 ++__first; 392 if (__first != __last) 393 { 394 ++__first; 395 while (__first != __last && !bool(__pred(*__first, __value))) 396 ++__first; 397 } 398 return __first == __last; 399 } 400 401 template<typename _ForwardIterator, typename _Tp, typename _Pred> 402 inline bool 403 __check_partitioned_upper(_ForwardIterator __first, 404 _ForwardIterator __last, const _Tp& __value, 405 _Pred __pred) 406 { 407 while (__first != __last && !bool(__pred(__value, *__first))) 408 ++__first; 409 if (__first != __last) 410 { 411 ++__first; 412 while (__first != __last && bool(__pred(__value, *__first))) 413 ++__first; 414 } 415 return __first == __last; 416 } 417 418 // Helper struct to detect random access safe iterators. 419 template<typename _Iterator> 420 struct __is_safe_random_iterator 421 { 422 enum { __value = 0 }; 423 typedef std::__false_type __type; 424 }; 425 426 template<typename _Iterator, typename _Sequence> 427 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > 428 : std::__are_same<std::random_access_iterator_tag, 429 typename std::iterator_traits<_Iterator>:: 430 iterator_category> 431 { }; 432 433 template<typename _Iterator> 434 struct _Siter_base 435 : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> 436 { }; 437 438 /** Helper function to extract base iterator of random access safe iterator 439 in order to reduce performance impact of debug mode. Limited to random 440 access iterator because it is the only category for which it is possible 441 to check for correct iterators order in the __valid_range function 442 thanks to the < operator. 443 */ 444 template<typename _Iterator> 445 inline typename _Siter_base<_Iterator>::iterator_type 446 __base(_Iterator __it) 447 { return _Siter_base<_Iterator>::_S_base(__it); } 448 } // namespace __gnu_debug 449 450 #endif 451