1 // Debugging support implementation -*- C++ -*- 2 3 // Copyright (C) 2003 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 2, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // You should have received a copy of the GNU General Public License along 18 // with this library; see the file COPYING. If not, write to the Free 19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 20 // USA. 21 22 // As a special exception, you may use this file as part of a free software 23 // library without restriction. Specifically, if other files instantiate 24 // templates or use macros or inline functions from this file, or you compile 25 // this file and link it with other files to produce an executable, this 26 // file does not by itself cause the resulting executable to be covered by 27 // the GNU General Public License. This exception does not however 28 // invalidate any other reasons why the executable file might be covered by 29 // the GNU General Public License. 30 31 #ifndef _GLIBCXX_DEBUG_DEBUG_H 32 #define _GLIBCXX_DEBUG_DEBUG_H 1 33 34 /** 35 * Macros used by the implementation to verify certain 36 * properties. These macros may only be used directly by the debug 37 * wrappers. Note that these are macros (instead of the more obviously 38 * "correct" choice of making them functions) because we need line and 39 * file information at the call site, to minimize the distance between 40 * the user error and where the error is reported. 41 * 42 */ 43 #define _GLIBCXX_DEBUG_VERIFY(_Condition,_ErrorMessage) \ 44 do { \ 45 if (! (_Condition)) \ 46 ::__gnu_debug::_Error_formatter::_M_at(__FILE__, __LINE__) \ 47 ._ErrorMessage._M_error(); \ 48 } while (false) 49 50 // Verify that [_First, _Last) forms a valid iterator range. 51 #define __glibcxx_check_valid_range(_First,_Last) \ 52 _GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__valid_range(_First, _Last), \ 53 _M_message(::__gnu_debug::__msg_valid_range) \ 54 ._M_iterator(_First, #_First) \ 55 ._M_iterator(_Last, #_Last)) 56 57 /** Verify that we can insert into *this with the iterator _Position. 58 * Insertion into a container at a specific position requires that 59 * the iterator be nonsingular (i.e., either dereferenceable or 60 * past-the-end) and that it reference the sequence we are inserting 61 * into. Note that this macro is only valid when the container is a 62 * _Safe_sequence and the iterator is a _Safe_iterator. 63 */ 64 #define __glibcxx_check_insert(_Position) \ 65 _GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(), \ 66 _M_message(::__gnu_debug::__msg_insert_singular) \ 67 ._M_sequence(*this, "this") \ 68 ._M_iterator(_Position, #_Position)); \ 69 _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ 70 _M_message(::__gnu_debug::__msg_insert_different) \ 71 ._M_sequence(*this, "this") \ 72 ._M_iterator(_Position, #_Position)) 73 74 /** Verify that we can insert the values in the iterator range 75 * [_First, _Last) into *this with the iterator _Position. Insertion 76 * into a container at a specific position requires that the iterator 77 * be nonsingular (i.e., either dereferenceable or past-the-end), 78 * that it reference the sequence we are inserting into, and that the 79 * iterator range [_First, Last) is a valid (possibly empty) 80 * range. Note that this macro is only valid when the container is a 81 * _Safe_sequence and the iterator is a _Safe_iterator. 82 * 83 * @tbd We would like to be able to check for noninterference of 84 * _Position and the range [_First, _Last), but that can't (in 85 * general) be done. 86 */ 87 #define __glibcxx_check_insert_range(_Position,_First,_Last) \ 88 __glibcxx_check_valid_range(_First,_Last); \ 89 _GLIBCXX_DEBUG_VERIFY(!_Position._M_singular(), \ 90 _M_message(::__gnu_debug::__msg_insert_singular) \ 91 ._M_sequence(*this, "this") \ 92 ._M_iterator(_Position, #_Position)); \ 93 _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ 94 _M_message(::__gnu_debug::__msg_insert_different) \ 95 ._M_sequence(*this, "this") \ 96 ._M_iterator(_Position, #_Position)) 97 98 /** Verify that we can erase the element referenced by the iterator 99 * _Position. We can erase the element if the _Position iterator is 100 * dereferenceable and references this sequence. 101 */ 102 #define __glibcxx_check_erase(_Position) \ 103 _GLIBCXX_DEBUG_VERIFY(_Position._M_dereferenceable(), \ 104 _M_message(::__gnu_debug::__msg_erase_bad) \ 105 ._M_sequence(*this, "this") \ 106 ._M_iterator(_Position, #_Position)); \ 107 _GLIBCXX_DEBUG_VERIFY(_Position._M_attached_to(this), \ 108 _M_message(::__gnu_debug::__msg_erase_different) \ 109 ._M_sequence(*this, "this") \ 110 ._M_iterator(_Position, #_Position)) 111 112 /** Verify that we can erase the elements in the iterator range 113 * [_First, _Last). We can erase the elements if [_First, _Last) is a 114 * valid iterator range within this sequence. 115 */ 116 #define __glibcxx_check_erase_range(_First,_Last) \ 117 __glibcxx_check_valid_range(_First,_Last); \ 118 _GLIBCXX_DEBUG_VERIFY(_First._M_attached_to(this), \ 119 _M_message(::__gnu_debug::__msg_erase_different) \ 120 ._M_sequence(*this, "this") \ 121 ._M_iterator(_First, #_First) \ 122 ._M_iterator(_Last, #_Last)) 123 124 // Verify that the subscript _N is less than the container's size. 125 #define __glibcxx_check_subscript(_N) \ 126 _GLIBCXX_DEBUG_VERIFY(_N < this->size(), \ 127 _M_message(::__gnu_debug::__msg_subscript_oob) \ 128 ._M_sequence(*this, "this") \ 129 ._M_integer(_N, #_N) \ 130 ._M_integer(this->size(), "size")) 131 132 // Verify that the container is nonempty 133 #define __glibcxx_check_nonempty() \ 134 _GLIBCXX_DEBUG_VERIFY(! this->empty(), \ 135 _M_message(::__gnu_debug::__msg_empty) \ 136 ._M_sequence(*this, "this")) 137 138 // Verify that the < operator for elements in the sequence is a 139 // StrictWeakOrdering by checking that it is irreflexive. 140 #define __glibcxx_check_strict_weak_ordering(_First,_Last) \ 141 _GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First)) 142 143 // Verify that the predicate is StrictWeakOrdering by checking that it 144 // is irreflexive. 145 #define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred) \ 146 _GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First)) 147 148 149 // Verify that the iterator range [_First, _Last) is sorted 150 #define __glibcxx_check_sorted(_First,_Last) \ 151 __glibcxx_check_valid_range(_First,_Last); \ 152 __glibcxx_check_strict_weak_ordering(_First,_Last); \ 153 _GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last), \ 154 _M_message(::__gnu_debug::__msg_unsorted) \ 155 ._M_iterator(_First, #_First) \ 156 ._M_iterator(_Last, #_Last)) 157 158 /** Verify that the iterator range [_First, _Last) is sorted by the 159 predicate _Pred. */ 160 #define __glibcxx_check_sorted_pred(_First,_Last,_Pred) \ 161 __glibcxx_check_valid_range(_First,_Last); \ 162 __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred); \ 163 _GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_sorted(_First, _Last, _Pred), \ 164 _M_message(::__gnu_debug::__msg_unsorted_pred) \ 165 ._M_iterator(_First, #_First) \ 166 ._M_iterator(_Last, #_Last) \ 167 ._M_string(#_Pred)) 168 169 /** Verify that the iterator range [_First, _Last) is partitioned 170 w.r.t. the value _Value. */ 171 #define __glibcxx_check_partitioned(_First,_Last,_Value) \ 172 __glibcxx_check_valid_range(_First,_Last); \ 173 _GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last, \ 174 _Value), \ 175 _M_message(::__gnu_debug::__msg_unpartitioned) \ 176 ._M_iterator(_First, #_First) \ 177 ._M_iterator(_Last, #_Last) \ 178 ._M_string(#_Value)) 179 180 /** Verify that the iterator range [_First, _Last) is partitioned 181 w.r.t. the value _Value and predicate _Pred. */ 182 #define __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred) \ 183 __glibcxx_check_valid_range(_First,_Last); \ 184 _GLIBCXX_DEBUG_VERIFY(::__gnu_debug::__check_partitioned(_First, _Last, \ 185 _Value, _Pred), \ 186 _M_message(::__gnu_debug::__msg_unpartitioned_pred) \ 187 ._M_iterator(_First, #_First) \ 188 ._M_iterator(_Last, #_Last) \ 189 ._M_string(#_Pred) \ 190 ._M_string(#_Value)) 191 192 // Verify that the iterator range [_First, _Last) is a heap 193 #define __glibcxx_check_heap(_First,_Last) \ 194 __glibcxx_check_valid_range(_First,_Last); \ 195 _GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last), \ 196 _M_message(::__gnu_debug::__msg_not_heap) \ 197 ._M_iterator(_First, #_First) \ 198 ._M_iterator(_Last, #_Last)) 199 200 /** Verify that the iterator range [_First, _Last) is a heap 201 w.r.t. the predicate _Pred. */ 202 #define __glibcxx_check_heap_pred(_First,_Last,_Pred) \ 203 __glibcxx_check_valid_range(_First,_Last); \ 204 _GLIBCXX_DEBUG_VERIFY(::std::__is_heap(_First, _Last, _Pred), \ 205 _M_message(::__gnu_debug::__msg_not_heap_pred) \ 206 ._M_iterator(_First, #_First) \ 207 ._M_iterator(_Last, #_Last) \ 208 ._M_string(#_Pred)) 209 210 #ifdef _GLIBCXX_DEBUG_PEDANTIC 211 # define __glibcxx_check_string(_String) _GLIBCXX_DEBUG_ASSERT(_String != 0) 212 # define __glibcxx_check_string_len(_String,_Len) \ 213 _GLIBCXX_DEBUG_ASSERT(_String != 0 || _Len == 0) 214 #else 215 # define __glibcxx_check_string(_String) 216 # define __glibcxx_check_string_len(_String,_Len) 217 #endif 218 219 /** Macros used by the implementation outside of debug wrappers to 220 * verify certain properties. The __glibcxx_requires_xxx macros are 221 * merely wrappers around the __glibcxx_check_xxx wrappers when we 222 * are compiling with debug mode, but disappear when we are in 223 * release mode so that there is no checking performed in, e.g., the 224 * standard library algorithms. 225 */ 226 #ifdef _GLIBCXX_DEBUG 227 # define _GLIBCXX_DEBUG_ASSERT(_Condition) assert(_Condition) 228 229 # ifdef _GLIBXX_DEBUG_PEDANTIC 230 # define _GLIBCXX_DEBUG_PEDASSERT(_Condition) assert(_Condition) 231 # else 232 # define _GLIBCXX_DEBUG_PEDASSERT(_Condition) 233 # endif 234 235 # define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg) 236 # define __glibcxx_requires_valid_range(_First,_Last) \ 237 __glibcxx_check_valid_range(_First,_Last) 238 # define __glibcxx_requires_sorted(_First,_Last) \ 239 __glibcxx_check_sorted(_First,_Last) 240 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \ 241 __glibcxx_check_sorted_pred(_First,_Last,_Pred) 242 # define __glibcxx_requires_partitioned(_First,_Last,_Value) \ 243 __glibcxx_check_partitioned(_First,_Last,_Value) 244 # define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred) \ 245 __glibcxx_check_partitioned_pred(_First,_Last,_Value,_Pred) 246 # define __glibcxx_requires_heap(_First,_Last) \ 247 __glibcxx_check_heap(_First,_Last) 248 # define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \ 249 __glibcxx_check_heap_pred(_First,_Last,_Pred) 250 # define __glibcxx_requires_nonempty() __glibcxx_check_nonempty() 251 # define __glibcxx_requires_string(_String) __glibcxx_check_string(_String) 252 # define __glibcxx_requires_string_len(_String,_Len) \ 253 __glibcxx_check_string_len(_String,_Len) 254 # define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N) 255 #else 256 # define _GLIBCXX_DEBUG_ASSERT(_Condition) 257 # define _GLIBCXX_DEBUG_PEDASSERT(_Condition) 258 # define __glibcxx_requires_cond(_Cond,_Msg) 259 # define __glibcxx_requires_valid_range(_First,_Last) 260 # define __glibcxx_requires_sorted(_First,_Last) 261 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) 262 # define __glibcxx_requires_partitioned(_First,_Last,_Value) 263 # define __glibcxx_requires_partitioned_pred(_First,_Last,_Value,_Pred) 264 # define __glibcxx_requires_heap(_First,_Last) 265 # define __glibcxx_requires_heap_pred(_First,_Last,_Pred) 266 # define __glibcxx_requires_nonempty() 267 # define __glibcxx_requires_string(_String) 268 # define __glibcxx_requires_string_len(_String,_Len) 269 # define __glibcxx_requires_subscript(_N) 270 #endif 271 272 #include <cassert> // TBD: temporary 273 274 #include <stddef.h> // for ptrdiff_t 275 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories 276 #include <bits/type_traits.h> // for _Is_integer 277 278 namespace __gnu_debug 279 { 280 template<typename _Iterator, typename _Sequence> 281 class _Safe_iterator; 282 283 // An arbitrary iterator pointer is not singular. 284 inline bool 285 __check_singular_aux(const void*) { return false; } 286 287 // We may have an iterator that derives from _Safe_iterator_base but isn't 288 // a _Safe_iterator. 289 template<typename _Iterator> 290 inline bool 291 __check_singular(_Iterator& __x) 292 { return __gnu_debug::__check_singular_aux(&__x); } 293 294 /** Non-NULL pointers are nonsingular. */ 295 template<typename _Tp> 296 inline bool 297 __check_singular(const _Tp* __ptr) 298 { return __ptr == 0; } 299 300 /** Safe iterators know if they are singular. */ 301 template<typename _Iterator, typename _Sequence> 302 inline bool 303 __check_singular(const _Safe_iterator<_Iterator, _Sequence>& __x) 304 { return __x._M_singular(); } 305 306 /** Assume that some arbitrary iterator is dereferenceable, because we 307 can't prove that it isn't. */ 308 template<typename _Iterator> 309 inline bool 310 __check_dereferenceable(_Iterator&) 311 { return true; } 312 313 /** Non-NULL pointers are dereferenceable. */ 314 template<typename _Tp> 315 inline bool 316 __check_dereferenceable(const _Tp* __ptr) 317 { return __ptr; } 318 319 /** Safe iterators know if they are singular. */ 320 template<typename _Iterator, typename _Sequence> 321 inline bool 322 __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) 323 { return __x._M_dereferenceable(); } 324 325 /** If the distance between two random access iterators is 326 * nonnegative, assume the range is valid. 327 */ 328 template<typename _RandomAccessIterator> 329 inline bool 330 __valid_range_aux2(const _RandomAccessIterator& __first, 331 const _RandomAccessIterator& __last, 332 std::random_access_iterator_tag) 333 { return __last - __first >= 0; } 334 335 /** Can't test for a valid range with input iterators, because 336 * iteration may be destructive. So we just assume that the range 337 * is valid. 338 */ 339 template<typename _InputIterator> 340 inline bool 341 __valid_range_aux2(const _InputIterator&, const _InputIterator&, 342 std::input_iterator_tag) 343 { return true; } 344 345 /** We say that integral types for a valid range, and defer to other 346 * routines to realize what to do with integral types instead of 347 * iterators. 348 */ 349 template<typename _Integral> 350 inline bool 351 __valid_range_aux(const _Integral&, const _Integral&, __true_type) 352 { return true; } 353 354 /** We have iterators, so figure out what kind of iterators that are 355 * to see if we can check the range ahead of time. 356 */ 357 template<typename _InputIterator> 358 inline bool 359 __valid_range_aux(const _InputIterator& __first, 360 const _InputIterator& __last, __false_type) 361 { 362 typedef typename std::iterator_traits<_InputIterator>::iterator_category 363 _Category; 364 return __gnu_debug::__valid_range_aux2(__first, __last, _Category()); 365 } 366 367 /** Don't know what these iterators are, or if they are even 368 * iterators (we may get an integral type for InputIterator), so 369 * see if they are integral and pass them on to the next phase 370 * otherwise. 371 */ 372 template<typename _InputIterator> 373 inline bool 374 __valid_range(const _InputIterator& __first, const _InputIterator& __last) 375 { 376 typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 377 return __gnu_debug::__valid_range_aux(__first, __last, _Integral()); 378 } 379 380 /** Safe iterators know how to check if they form a valid range. */ 381 template<typename _Iterator, typename _Sequence> 382 inline bool 383 __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, 384 const _Safe_iterator<_Iterator, _Sequence>& __last) 385 { return __first._M_valid_range(__last); } 386 387 /* Checks that [first, last) is a valid range, and then returns 388 * __first. This routine is useful when we can't use a separate 389 * assertion statement because, e.g., we are in a constructor. 390 */ 391 template<typename _InputIterator> 392 inline _InputIterator 393 __check_valid_range(const _InputIterator& __first, 394 const _InputIterator& __last) 395 { 396 _GLIBCXX_DEBUG_ASSERT(__gnu_debug::__valid_range(__first, __last)); 397 return __first; 398 } 399 400 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 401 template<typename _CharT, typename _Integer> 402 inline const _CharT* 403 __check_string(const _CharT* __s, const _Integer& __n) 404 { 405 #ifdef _GLIBCXX_DEBUG_PEDANTIC 406 _GLIBCXX_DEBUG_ASSERT(__s != 0 || __n == 0); 407 #endif 408 return __s; 409 } 410 411 /** Checks that __s is non-NULL and then returns __s. */ 412 template<typename _CharT> 413 inline const _CharT* 414 __check_string(const _CharT* __s) 415 { 416 #ifdef _GLIBCXX_DEBUG_PEDANTIC 417 _GLIBCXX_DEBUG_ASSERT(__s != 0); 418 #endif 419 return __s; 420 } 421 422 // Can't check if an input iterator sequence is sorted, because we 423 // can't step through the sequence. 424 template<typename _InputIterator> 425 inline bool 426 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 427 std::input_iterator_tag) 428 { return true; } 429 430 // Can verify if a forward iterator sequence is in fact sorted using 431 // std::__is_sorted 432 template<typename _ForwardIterator> 433 inline bool 434 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 435 std::forward_iterator_tag) 436 { 437 if (__first == __last) 438 return true; 439 440 _ForwardIterator __next = __first; 441 for (++__next; __next != __last; __first = __next, ++__next) { 442 if (*__next < *__first) 443 return false; 444 } 445 446 return true; 447 } 448 449 // Can't check if an input iterator sequence is sorted, because we can't step 450 // through the sequence. 451 template<typename _InputIterator, typename _Predicate> 452 inline bool 453 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 454 _Predicate, std::input_iterator_tag) 455 { return true; } 456 457 // Can verify if a forward iterator sequence is in fact sorted using 458 // std::__is_sorted 459 template<typename _ForwardIterator, typename _Predicate> 460 inline bool 461 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 462 _Predicate __pred, std::forward_iterator_tag) 463 { 464 if (__first == __last) 465 return true; 466 467 _ForwardIterator __next = __first; 468 for (++__next; __next != __last; __first = __next, ++__next) { 469 if (__pred(*__next, *__first)) 470 return false; 471 } 472 473 return true; 474 } 475 476 // Determine if a sequence is sorted. 477 template<typename _InputIterator> 478 inline bool 479 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 480 { 481 typedef typename std::iterator_traits<_InputIterator>::iterator_category 482 _Category; 483 return __gnu_debug::__check_sorted_aux(__first, __last, _Category()); 484 } 485 486 template<typename _InputIterator, typename _Predicate> 487 inline bool 488 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 489 _Predicate __pred) 490 { 491 typedef typename std::iterator_traits<_InputIterator>::iterator_category 492 _Category; 493 return __gnu_debug::__check_sorted_aux(__first, __last, __pred, 494 _Category()); 495 } 496 497 // _GLIBCXX_RESOLVE_LIB_DEFECTS 498 // 270. Binary search requirements overly strict 499 // Determine if a sequence is partitioned w.r.t. this element. 500 template<typename _ForwardIterator, typename _Tp> 501 inline bool 502 __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, 503 const _Tp& __value) 504 { 505 while (__first != __last && *__first < __value) 506 ++__first; 507 while (__first != __last && !(*__first < __value)) 508 ++__first; 509 return __first == __last; 510 } 511 512 // Determine if a sequence is partitioned w.r.t. this element. 513 template<typename _ForwardIterator, typename _Tp, typename _Pred> 514 inline bool 515 __check_partitioned(_ForwardIterator __first, _ForwardIterator __last, 516 const _Tp& __value, _Pred __pred) 517 { 518 while (__first != __last && __pred(*__first, __value)) 519 ++__first; 520 while (__first != __last && !__pred(*__first, __value)) 521 ++__first; 522 return __first == __last; 523 } 524 } // namespace __gnu_debug 525 526 #ifdef _GLIBCXX_DEBUG 527 // We need the error formatter 528 # include <debug/formatter.h> 529 #endif 530 531 #endif 532