libstdc++
|
00001 // Debugging support implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2015 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 #if __cplusplus < 201103L 00256 typedef _Is_contiguous_sequence<_Sequence> __tag; 00257 #else 00258 using __lvalref = std::is_lvalue_reference< 00259 typename std::iterator_traits<_InputIterator>::reference>; 00260 using __contiguous = _Is_contiguous_sequence<_Sequence>; 00261 using __tag = typename std::conditional<__lvalref::value, __contiguous, 00262 std::__false_type>::type; 00263 #endif 00264 return __foreign_iterator_aux3(__it, __other, __other_end, __tag()); 00265 } 00266 00267 /* Handle the case where we aren't really inserting a range after all */ 00268 template<typename _Iterator, typename _Sequence, typename _Integral> 00269 inline bool 00270 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&, 00271 _Integral, _Integral, 00272 std::__true_type) 00273 { return true; } 00274 00275 /* Handle all iterators. */ 00276 template<typename _Iterator, typename _Sequence, 00277 typename _InputIterator> 00278 inline bool 00279 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it, 00280 _InputIterator __other, _InputIterator __other_end, 00281 std::__false_type) 00282 { 00283 return _Insert_range_from_self_is_safe<_Sequence>::__value 00284 || __foreign_iterator_aux2(__it, __other, __other_end); 00285 } 00286 00287 template<typename _Iterator, typename _Sequence, 00288 typename _InputIterator> 00289 inline bool 00290 __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it, 00291 _InputIterator __other, _InputIterator __other_end) 00292 { 00293 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00294 return __foreign_iterator_aux(__it, __other, __other_end, _Integral()); 00295 } 00296 00297 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 00298 template<typename _CharT, typename _Integer> 00299 inline const _CharT* 00300 __check_string(const _CharT* __s, 00301 const _Integer& __n __attribute__((__unused__))) 00302 { 00303 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00304 __glibcxx_assert(__s != 0 || __n == 0); 00305 #endif 00306 return __s; 00307 } 00308 00309 /** Checks that __s is non-NULL and then returns __s. */ 00310 template<typename _CharT> 00311 inline const _CharT* 00312 __check_string(const _CharT* __s) 00313 { 00314 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00315 __glibcxx_assert(__s != 0); 00316 #endif 00317 return __s; 00318 } 00319 00320 // Can't check if an input iterator sequence is sorted, because we 00321 // can't step through the sequence. 00322 template<typename _InputIterator> 00323 inline bool 00324 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00325 std::input_iterator_tag) 00326 { return true; } 00327 00328 // Can verify if a forward iterator sequence is in fact sorted using 00329 // std::__is_sorted 00330 template<typename _ForwardIterator> 00331 inline bool 00332 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00333 std::forward_iterator_tag) 00334 { 00335 if (__first == __last) 00336 return true; 00337 00338 _ForwardIterator __next = __first; 00339 for (++__next; __next != __last; __first = __next, ++__next) 00340 if (*__next < *__first) 00341 return false; 00342 00343 return true; 00344 } 00345 00346 // Can't check if an input iterator sequence is sorted, because we can't step 00347 // through the sequence. 00348 template<typename _InputIterator, typename _Predicate> 00349 inline bool 00350 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00351 _Predicate, std::input_iterator_tag) 00352 { return true; } 00353 00354 // Can verify if a forward iterator sequence is in fact sorted using 00355 // std::__is_sorted 00356 template<typename _ForwardIterator, typename _Predicate> 00357 inline bool 00358 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00359 _Predicate __pred, std::forward_iterator_tag) 00360 { 00361 if (__first == __last) 00362 return true; 00363 00364 _ForwardIterator __next = __first; 00365 for (++__next; __next != __last; __first = __next, ++__next) 00366 if (__pred(*__next, *__first)) 00367 return false; 00368 00369 return true; 00370 } 00371 00372 // Determine if a sequence is sorted. 00373 template<typename _InputIterator> 00374 inline bool 00375 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 00376 { 00377 // Verify that the < operator for elements in the sequence is a 00378 // StrictWeakOrdering by checking that it is irreflexive. 00379 __glibcxx_assert(__first == __last || !(*__first < *__first)); 00380 00381 return __check_sorted_aux(__first, __last, 00382 std::__iterator_category(__first)); 00383 } 00384 00385 template<typename _InputIterator, typename _Predicate> 00386 inline bool 00387 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 00388 _Predicate __pred) 00389 { 00390 // Verify that the predicate is StrictWeakOrdering by checking that it 00391 // is irreflexive. 00392 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 00393 00394 return __check_sorted_aux(__first, __last, __pred, 00395 std::__iterator_category(__first)); 00396 } 00397 00398 template<typename _InputIterator> 00399 inline bool 00400 __check_sorted_set_aux(const _InputIterator& __first, 00401 const _InputIterator& __last, 00402 std::__true_type) 00403 { return __check_sorted(__first, __last); } 00404 00405 template<typename _InputIterator> 00406 inline bool 00407 __check_sorted_set_aux(const _InputIterator&, 00408 const _InputIterator&, 00409 std::__false_type) 00410 { return true; } 00411 00412 template<typename _InputIterator, typename _Predicate> 00413 inline bool 00414 __check_sorted_set_aux(const _InputIterator& __first, 00415 const _InputIterator& __last, 00416 _Predicate __pred, std::__true_type) 00417 { return __check_sorted(__first, __last, __pred); } 00418 00419 template<typename _InputIterator, typename _Predicate> 00420 inline bool 00421 __check_sorted_set_aux(const _InputIterator&, 00422 const _InputIterator&, _Predicate, 00423 std::__false_type) 00424 { return true; } 00425 00426 // ... special variant used in std::merge, std::includes, std::set_*. 00427 template<typename _InputIterator1, typename _InputIterator2> 00428 inline bool 00429 __check_sorted_set(const _InputIterator1& __first, 00430 const _InputIterator1& __last, 00431 const _InputIterator2&) 00432 { 00433 typedef typename std::iterator_traits<_InputIterator1>::value_type 00434 _ValueType1; 00435 typedef typename std::iterator_traits<_InputIterator2>::value_type 00436 _ValueType2; 00437 00438 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00439 _SameType; 00440 return __check_sorted_set_aux(__first, __last, _SameType()); 00441 } 00442 00443 template<typename _InputIterator1, typename _InputIterator2, 00444 typename _Predicate> 00445 inline bool 00446 __check_sorted_set(const _InputIterator1& __first, 00447 const _InputIterator1& __last, 00448 const _InputIterator2&, _Predicate __pred) 00449 { 00450 typedef typename std::iterator_traits<_InputIterator1>::value_type 00451 _ValueType1; 00452 typedef typename std::iterator_traits<_InputIterator2>::value_type 00453 _ValueType2; 00454 00455 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00456 _SameType; 00457 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 00458 } 00459 00460 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00461 // 270. Binary search requirements overly strict 00462 // Determine if a sequence is partitioned w.r.t. this element. 00463 template<typename _ForwardIterator, typename _Tp> 00464 inline bool 00465 __check_partitioned_lower(_ForwardIterator __first, 00466 _ForwardIterator __last, const _Tp& __value) 00467 { 00468 while (__first != __last && *__first < __value) 00469 ++__first; 00470 if (__first != __last) 00471 { 00472 ++__first; 00473 while (__first != __last && !(*__first < __value)) 00474 ++__first; 00475 } 00476 return __first == __last; 00477 } 00478 00479 template<typename _ForwardIterator, typename _Tp> 00480 inline bool 00481 __check_partitioned_upper(_ForwardIterator __first, 00482 _ForwardIterator __last, const _Tp& __value) 00483 { 00484 while (__first != __last && !(__value < *__first)) 00485 ++__first; 00486 if (__first != __last) 00487 { 00488 ++__first; 00489 while (__first != __last && __value < *__first) 00490 ++__first; 00491 } 00492 return __first == __last; 00493 } 00494 00495 // Determine if a sequence is partitioned w.r.t. this element. 00496 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00497 inline bool 00498 __check_partitioned_lower(_ForwardIterator __first, 00499 _ForwardIterator __last, const _Tp& __value, 00500 _Pred __pred) 00501 { 00502 while (__first != __last && bool(__pred(*__first, __value))) 00503 ++__first; 00504 if (__first != __last) 00505 { 00506 ++__first; 00507 while (__first != __last && !bool(__pred(*__first, __value))) 00508 ++__first; 00509 } 00510 return __first == __last; 00511 } 00512 00513 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00514 inline bool 00515 __check_partitioned_upper(_ForwardIterator __first, 00516 _ForwardIterator __last, const _Tp& __value, 00517 _Pred __pred) 00518 { 00519 while (__first != __last && !bool(__pred(__value, *__first))) 00520 ++__first; 00521 if (__first != __last) 00522 { 00523 ++__first; 00524 while (__first != __last && bool(__pred(__value, *__first))) 00525 ++__first; 00526 } 00527 return __first == __last; 00528 } 00529 00530 // Helper struct to detect random access safe iterators. 00531 template<typename _Iterator> 00532 struct __is_safe_random_iterator 00533 { 00534 enum { __value = 0 }; 00535 typedef std::__false_type __type; 00536 }; 00537 00538 template<typename _Iterator, typename _Sequence> 00539 struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> > 00540 : std::__are_same<std::random_access_iterator_tag, 00541 typename std::iterator_traits<_Iterator>:: 00542 iterator_category> 00543 { }; 00544 00545 template<typename _Iterator> 00546 struct _Siter_base 00547 : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value> 00548 { }; 00549 00550 /** Helper function to extract base iterator of random access safe iterator 00551 in order to reduce performance impact of debug mode. Limited to random 00552 access iterator because it is the only category for which it is possible 00553 to check for correct iterators order in the __valid_range function 00554 thanks to the < operator. 00555 */ 00556 template<typename _Iterator> 00557 inline typename _Siter_base<_Iterator>::iterator_type 00558 __base(_Iterator __it) 00559 { return _Siter_base<_Iterator>::_S_base(__it); } 00560 } // namespace __gnu_debug 00561 00562 #endif