libstdc++
|
00001 // Debugging support implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2014 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file debug/functions.h 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H 00030 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1 00031 00032 #include <bits/c++config.h> 00033 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and 00034 // _Iter_base 00035 #include <bits/cpp_type_traits.h> // for __is_integer 00036 #include <bits/move.h> // for __addressof and addressof 00037 # include <bits/stl_function.h> // for less 00038 #if __cplusplus >= 201103L 00039 # include <type_traits> // for is_lvalue_reference and __and_ 00040 #endif 00041 #include <debug/formatter.h> 00042 00043 namespace __gnu_debug 00044 { 00045 template<typename _Iterator, typename _Sequence> 00046 class _Safe_iterator; 00047 00048 template<typename _Iterator, typename _Sequence> 00049 class _Safe_local_iterator; 00050 00051 template<typename _Sequence> 00052 struct _Insert_range_from_self_is_safe 00053 { enum { __value = 0 }; }; 00054 00055 template<typename _Sequence> 00056 struct _Is_contiguous_sequence : std::__false_type { }; 00057 00058 // An arbitrary iterator pointer is not singular. 00059 inline bool 00060 __check_singular_aux(const void*) { return false; } 00061 00062 // We may have an iterator that derives from _Safe_iterator_base but isn't 00063 // a _Safe_iterator. 00064 template<typename _Iterator> 00065 inline bool 00066 __check_singular(const _Iterator& __x) 00067 { return __check_singular_aux(&__x); } 00068 00069 /** Non-NULL pointers are nonsingular. */ 00070 template<typename _Tp> 00071 inline bool 00072 __check_singular(const _Tp* __ptr) 00073 { return __ptr == 0; } 00074 00075 /** Assume that some arbitrary iterator is dereferenceable, because we 00076 can't prove that it isn't. */ 00077 template<typename _Iterator> 00078 inline bool 00079 __check_dereferenceable(const _Iterator&) 00080 { return true; } 00081 00082 /** Non-NULL pointers are dereferenceable. */ 00083 template<typename _Tp> 00084 inline bool 00085 __check_dereferenceable(const _Tp* __ptr) 00086 { return __ptr; } 00087 00088 /** Safe iterators know if they are dereferenceable. */ 00089 template<typename _Iterator, typename _Sequence> 00090 inline bool 00091 __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x) 00092 { return __x._M_dereferenceable(); } 00093 00094 /** Safe local iterators know if they are dereferenceable. */ 00095 template<typename _Iterator, typename _Sequence> 00096 inline bool 00097 __check_dereferenceable(const _Safe_local_iterator<_Iterator, 00098 _Sequence>& __x) 00099 { return __x._M_dereferenceable(); } 00100 00101 /** If the distance between two random access iterators is 00102 * nonnegative, assume the range is valid. 00103 */ 00104 template<typename _RandomAccessIterator> 00105 inline bool 00106 __valid_range_aux2(const _RandomAccessIterator& __first, 00107 const _RandomAccessIterator& __last, 00108 std::random_access_iterator_tag) 00109 { return __last - __first >= 0; } 00110 00111 /** Can't test for a valid range with input iterators, because 00112 * iteration may be destructive. So we just assume that the range 00113 * is valid. 00114 */ 00115 template<typename _InputIterator> 00116 inline bool 00117 __valid_range_aux2(const _InputIterator&, const _InputIterator&, 00118 std::input_iterator_tag) 00119 { return true; } 00120 00121 /** We say that integral types for a valid range, and defer to other 00122 * routines to realize what to do with integral types instead of 00123 * iterators. 00124 */ 00125 template<typename _Integral> 00126 inline bool 00127 __valid_range_aux(const _Integral&, const _Integral&, std::__true_type) 00128 { return true; } 00129 00130 /** We have iterators, so figure out what kind of iterators that are 00131 * to see if we can check the range ahead of time. 00132 */ 00133 template<typename _InputIterator> 00134 inline bool 00135 __valid_range_aux(const _InputIterator& __first, 00136 const _InputIterator& __last, std::__false_type) 00137 { return __valid_range_aux2(__first, __last, 00138 std::__iterator_category(__first)); } 00139 00140 /** Don't know what these iterators are, or if they are even 00141 * iterators (we may get an integral type for InputIterator), so 00142 * see if they are integral and pass them on to the next phase 00143 * otherwise. 00144 */ 00145 template<typename _InputIterator> 00146 inline bool 00147 __valid_range(const _InputIterator& __first, const _InputIterator& __last) 00148 { 00149 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00150 return __valid_range_aux(__first, __last, _Integral()); 00151 } 00152 00153 /** Safe iterators know how to check if they form a valid range. */ 00154 template<typename _Iterator, typename _Sequence> 00155 inline bool 00156 __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first, 00157 const _Safe_iterator<_Iterator, _Sequence>& __last) 00158 { return __first._M_valid_range(__last); } 00159 00160 /** Safe local iterators know how to check if they form a valid range. */ 00161 template<typename _Iterator, typename _Sequence> 00162 inline bool 00163 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 00164 const _Safe_local_iterator<_Iterator, _Sequence>& __last) 00165 { return __first._M_valid_range(__last); } 00166 00167 /* Checks that [first, last) is a valid range, and then returns 00168 * __first. This routine is useful when we can't use a separate 00169 * assertion statement because, e.g., we are in a constructor. 00170 */ 00171 template<typename _InputIterator> 00172 inline _InputIterator 00173 __check_valid_range(const _InputIterator& __first, 00174 const _InputIterator& __last 00175 __attribute__((__unused__))) 00176 { 00177 __glibcxx_check_valid_range(__first, __last); 00178 return __first; 00179 } 00180 00181 /* Handle the case where __other is a pointer to _Sequence::value_type. */ 00182 template<typename _Iterator, typename _Sequence> 00183 inline bool 00184 __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it, 00185 const typename _Sequence::value_type* __other) 00186 { 00187 typedef const typename _Sequence::value_type* _PointerType; 00188 typedef std::less<_PointerType> _Less; 00189 #if __cplusplus >= 201103L 00190 constexpr _Less __l{}; 00191 #else 00192 const _Less __l = _Less(); 00193 #endif 00194 const _Sequence* __seq = __it._M_get_sequence(); 00195 const _PointerType __begin = std::__addressof(*__seq->_M_base().begin()); 00196 const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1)); 00197 00198 // Check whether __other points within the contiguous storage. 00199 return __l(__other, __begin) || __l(__end, __other); 00200 } 00201 00202 /* Fallback overload for when we can't tell, assume it is valid. */ 00203 template<typename _Iterator, typename _Sequence> 00204 inline bool 00205 __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...) 00206 { return true; } 00207 00208 /* Handle sequences with contiguous storage */ 00209 template<typename _Iterator, typename _Sequence, typename _InputIterator> 00210 inline bool 00211 __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, 00212 const _InputIterator& __other, 00213 const _InputIterator& __other_end, 00214 std::__true_type) 00215 { 00216 if (__other == __other_end) 00217 return true; // inserting nothing is safe even if not foreign iters 00218 if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end()) 00219 return true; // can't be self-inserting if self is empty 00220 return __foreign_iterator_aux4(__it, std::__addressof(*__other)); 00221 } 00222 00223 /* Handle non-contiguous containers, assume it is valid. */ 00224 template<typename _Iterator, typename _Sequence, typename _InputIterator> 00225 inline bool 00226 __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&, 00227 const _InputIterator&, const _InputIterator&, 00228 std::__false_type) 00229 { return true; } 00230 00231 /** Handle debug iterators from the same type of container. */ 00232 template<typename _Iterator, typename _Sequence, typename _OtherIterator> 00233 inline bool 00234 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 00235 const _Safe_iterator<_OtherIterator, _Sequence>& __other, 00236 const _Safe_iterator<_OtherIterator, _Sequence>&) 00237 { return __it._M_get_sequence() != __other._M_get_sequence(); } 00238 00239 /** Handle debug iterators from different types of container. */ 00240 template<typename _Iterator, typename _Sequence, typename _OtherIterator, 00241 typename _OtherSequence> 00242 inline bool 00243 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 00244 const _Safe_iterator<_OtherIterator, _OtherSequence>&, 00245 const _Safe_iterator<_OtherIterator, _OtherSequence>&) 00246 { return true; } 00247 00248 /* Handle non-debug iterators. */ 00249 template<typename _Iterator, typename _Sequence, typename _InputIterator> 00250 inline bool 00251 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 00252 const _InputIterator& __other, 00253 const _InputIterator& __other_end) 00254 { 00255 return __foreign_iterator_aux3(__it, __other, __other_end, 00256 _Is_contiguous_sequence<_Sequence>()); 00257 } 00258 00259 /* Handle the case where we aren't really inserting a range after all */ 00260 template<typename _Iterator, typename _Sequence, typename _Integral> 00261 inline bool 00262 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&, 00263 _Integral, _Integral, 00264 std::__true_type) 00265 { return true; } 00266 00267 /* Handle all iterators. */ 00268 template<typename _Iterator, typename _Sequence, 00269 typename _InputIterator> 00270 inline bool 00271 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it, 00272 _InputIterator __other, _InputIterator __other_end, 00273 std::__false_type) 00274 { 00275 return _Insert_range_from_self_is_safe<_Sequence>::__value 00276 || __foreign_iterator_aux2(__it, __other, __other_end); 00277 } 00278 00279 template<typename _Iterator, typename _Sequence, 00280 typename _InputIterator> 00281 inline bool 00282 __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it, 00283 _InputIterator __other, _InputIterator __other_end) 00284 { 00285 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00286 return __foreign_iterator_aux(__it, __other, __other_end, _Integral()); 00287 } 00288 00289 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 00290 template<typename _CharT, typename _Integer> 00291 inline const _CharT* 00292 __check_string(const _CharT* __s, 00293 const _Integer& __n __attribute__((__unused__))) 00294 { 00295 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00296 __glibcxx_assert(__s != 0 || __n == 0); 00297 #endif 00298 return __s; 00299 } 00300 00301 /** Checks that __s is non-NULL and then returns __s. */ 00302 template<typename _CharT> 00303 inline const _CharT* 00304 __check_string(const _CharT* __s) 00305 { 00306 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00307 __glibcxx_assert(__s != 0); 00308 #endif 00309 return __s; 00310 } 00311 00312 // Can't check if an input iterator sequence is sorted, because we 00313 // can't step through the sequence. 00314 template<typename _InputIterator> 00315 inline bool 00316 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00317 std::input_iterator_tag) 00318 { return true; } 00319 00320 // Can verify if a forward iterator sequence is in fact sorted using 00321 // std::__is_sorted 00322 template<typename _ForwardIterator> 00323 inline bool 00324 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00325 std::forward_iterator_tag) 00326 { 00327 if (__first == __last) 00328 return true; 00329 00330 _ForwardIterator __next = __first; 00331 for (++__next; __next != __last; __first = __next, ++__next) 00332 if (*__next < *__first) 00333 return false; 00334 00335 return true; 00336 } 00337 00338 // Can't check if an input iterator sequence is sorted, because we can't step 00339 // through the sequence. 00340 template<typename _InputIterator, typename _Predicate> 00341 inline bool 00342 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00343 _Predicate, std::input_iterator_tag) 00344 { return true; } 00345 00346 // Can verify if a forward iterator sequence is in fact sorted using 00347 // std::__is_sorted 00348 template<typename _ForwardIterator, typename _Predicate> 00349 inline bool 00350 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00351 _Predicate __pred, std::forward_iterator_tag) 00352 { 00353 if (__first == __last) 00354 return true; 00355 00356 _ForwardIterator __next = __first; 00357 for (++__next; __next != __last; __first = __next, ++__next) 00358 if (__pred(*__next, *__first)) 00359 return false; 00360 00361 return true; 00362 } 00363 00364 // Determine if a sequence is sorted. 00365 template<typename _InputIterator> 00366 inline bool 00367 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 00368 { 00369 // Verify that the < operator for elements in the sequence is a 00370 // StrictWeakOrdering by checking that it is irreflexive. 00371 __glibcxx_assert(__first == __last || !(*__first < *__first)); 00372 00373 return __check_sorted_aux(__first, __last, 00374 std::__iterator_category(__first)); 00375 } 00376 00377 template<typename _InputIterator, typename _Predicate> 00378 inline bool 00379 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 00380 _Predicate __pred) 00381 { 00382 // Verify that the predicate is StrictWeakOrdering by checking that it 00383 // is irreflexive. 00384 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 00385 00386 return __check_sorted_aux(__first, __last, __pred, 00387 std::__iterator_category(__first)); 00388 } 00389 00390 template<typename _InputIterator> 00391 inline bool 00392 __check_sorted_set_aux(const _InputIterator& __first, 00393 const _InputIterator& __last, 00394 std::__true_type) 00395 { return __check_sorted(__first, __last); } 00396 00397 template<typename _InputIterator> 00398 inline bool 00399 __check_sorted_set_aux(const _InputIterator&, 00400 const _InputIterator&, 00401 std::__false_type) 00402 { return true; } 00403 00404 template<typename _InputIterator, typename _Predicate> 00405 inline bool 00406 __check_sorted_set_aux(const _InputIterator& __first, 00407 const _InputIterator& __last, 00408 _Predicate __pred, std::__true_type) 00409 { return __check_sorted(__first, __last, __pred); } 00410 00411 template<typename _InputIterator, typename _Predicate> 00412 inline bool 00413 __check_sorted_set_aux(const _InputIterator&, 00414 const _InputIterator&, _Predicate, 00415 std::__false_type) 00416 { return true; } 00417 00418 // ... special variant used in std::merge, std::includes, std::set_*. 00419 template<typename _InputIterator1, typename _InputIterator2> 00420 inline bool 00421 __check_sorted_set(const _InputIterator1& __first, 00422 const _InputIterator1& __last, 00423 const _InputIterator2&) 00424 { 00425 typedef typename std::iterator_traits<_InputIterator1>::value_type 00426 _ValueType1; 00427 typedef typename std::iterator_traits<_InputIterator2>::value_type 00428 _ValueType2; 00429 00430 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00431 _SameType; 00432 return __check_sorted_set_aux(__first, __last, _SameType()); 00433 } 00434 00435 template<typename _InputIterator1, typename _InputIterator2, 00436 typename _Predicate> 00437 inline bool 00438 __check_sorted_set(const _InputIterator1& __first, 00439 const _InputIterator1& __last, 00440 const _InputIterator2&, _Predicate __pred) 00441 { 00442 typedef typename std::iterator_traits<_InputIterator1>::value_type 00443 _ValueType1; 00444 typedef typename std::iterator_traits<_InputIterator2>::value_type 00445 _ValueType2; 00446 00447 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00448 _SameType; 00449 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 00450 } 00451 00452 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00453 // 270. Binary search requirements overly strict 00454 // Determine if a sequence is partitioned w.r.t. this element. 00455 template<typename _ForwardIterator, typename _Tp> 00456 inline bool 00457 __check_partitioned_lower(_ForwardIterator __first, 00458 _ForwardIterator __last, const _Tp& __value) 00459 { 00460 while (__first != __last && *__first < __value) 00461 ++__first; 00462 if (__first != __last) 00463 { 00464 ++__first; 00465 while (__first != __last && !(*__first < __value)) 00466 ++__first; 00467 } 00468 return __first == __last; 00469 } 00470 00471 template<typename _ForwardIterator, typename _Tp> 00472 inline bool 00473 __check_partitioned_upper(_ForwardIterator __first, 00474 _ForwardIterator __last, const _Tp& __value) 00475 { 00476 while (__first != __last && !(__value < *__first)) 00477 ++__first; 00478 if (__first != __last) 00479 { 00480 ++__first; 00481 while (__first != __last && __value < *__first) 00482 ++__first; 00483 } 00484 return __first == __last; 00485 } 00486 00487 // Determine if a sequence is partitioned w.r.t. this element. 00488 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00489 inline bool 00490 __check_partitioned_lower(_ForwardIterator __first, 00491 _ForwardIterator __last, const _Tp& __value, 00492 _Pred __pred) 00493 { 00494 while (__first != __last && bool(__pred(*__first, __value))) 00495 ++__first; 00496 if (__first != __last) 00497 { 00498 ++__first; 00499 while (__first != __last && !bool(__pred(*__first, __value))) 00500 ++__first; 00501 } 00502 return __first == __last; 00503 } 00504 00505 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00506 inline bool 00507 __check_partitioned_upper(_ForwardIterator __first, 00508 _ForwardIterator __last, const _Tp& __value, 00509 _Pred __pred) 00510 { 00511 while (__first != __last && !bool(__pred(__value, *__first))) 00512 ++__first; 00513 if (__first != __last) 00514 { 00515 ++__first; 00516 while (__first != __last && bool(__pred(__value, *__first))) 00517 ++__first; 00518 } 00519 return __first == __last; 00520 } 00521 00522 // Helper struct to detect random access safe iterators. 00523 template<typename _Iterator> 00524 struct __is_safe_random_iterator 00525 { 00526 enum { __value = 0 }; 00527 typedef std::__false_type __type; 00528 }; 00529 00530 template<typename _Iterator, typename _Sequence> 00531 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > 00532 : std::__are_same<std::random_access_iterator_tag, 00533 typename std::iterator_traits<_Iterator>:: 00534 iterator_category> 00535 { }; 00536 00537 template<typename _Iterator> 00538 struct _Siter_base 00539 : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> 00540 { }; 00541 00542 /** Helper function to extract base iterator of random access safe iterator 00543 in order to reduce performance impact of debug mode. Limited to random 00544 access iterator because it is the only category for which it is possible 00545 to check for correct iterators order in the __valid_range function 00546 thanks to the < operator. 00547 */ 00548 template<typename _Iterator> 00549 inline typename _Siter_base<_Iterator>::iterator_type 00550 __base(_Iterator __it) 00551 { return _Siter_base<_Iterator>::_S_base(__it); } 00552 } // namespace __gnu_debug 00553 00554 #endif