libstdc++
|
00001 // Debugging support implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2016 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/move.h> // for __addressof 00033 #include <bits/stl_function.h> // for less 00034 #if __cplusplus >= 201103L 00035 # include <type_traits> // for is_lvalue_reference and 00036 // conditional. 00037 #endif 00038 00039 #include <debug/helper_functions.h> 00040 #include <debug/formatter.h> 00041 00042 namespace __gnu_debug 00043 { 00044 template<typename _Iterator, typename _Sequence> 00045 class _Safe_iterator; 00046 00047 template<typename _Sequence> 00048 struct _Insert_range_from_self_is_safe 00049 { enum { __value = 0 }; }; 00050 00051 template<typename _Sequence> 00052 struct _Is_contiguous_sequence : std::__false_type { }; 00053 00054 // An arbitrary iterator pointer is not singular. 00055 inline bool 00056 __check_singular_aux(const void*) { return false; } 00057 00058 // We may have an iterator that derives from _Safe_iterator_base but isn't 00059 // a _Safe_iterator. 00060 template<typename _Iterator> 00061 inline bool 00062 __check_singular(const _Iterator& __x) 00063 { return __check_singular_aux(std::__addressof(__x)); } 00064 00065 /** Non-NULL pointers are nonsingular. */ 00066 template<typename _Tp> 00067 inline bool 00068 __check_singular(const _Tp* __ptr) 00069 { return __ptr == 0; } 00070 00071 /** Assume that some arbitrary iterator is dereferenceable, because we 00072 can't prove that it isn't. */ 00073 template<typename _Iterator> 00074 inline bool 00075 __check_dereferenceable(const _Iterator&) 00076 { return true; } 00077 00078 /** Non-NULL pointers are dereferenceable. */ 00079 template<typename _Tp> 00080 inline bool 00081 __check_dereferenceable(const _Tp* __ptr) 00082 { return __ptr; } 00083 00084 /* Checks that [first, last) is a valid range, and then returns 00085 * __first. This routine is useful when we can't use a separate 00086 * assertion statement because, e.g., we are in a constructor. 00087 */ 00088 template<typename _InputIterator> 00089 inline _InputIterator 00090 __check_valid_range(const _InputIterator& __first, 00091 const _InputIterator& __last 00092 __attribute__((__unused__))) 00093 { 00094 __glibcxx_check_valid_range(__first, __last); 00095 return __first; 00096 } 00097 00098 /* Handle the case where __other is a pointer to _Sequence::value_type. */ 00099 template<typename _Iterator, typename _Sequence> 00100 inline bool 00101 __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it, 00102 const typename _Sequence::value_type* __other) 00103 { 00104 typedef const typename _Sequence::value_type* _PointerType; 00105 typedef std::less<_PointerType> _Less; 00106 #if __cplusplus >= 201103L 00107 constexpr _Less __l{}; 00108 #else 00109 const _Less __l = _Less(); 00110 #endif 00111 const _Sequence* __seq = __it._M_get_sequence(); 00112 const _PointerType __begin = std::__addressof(*__seq->_M_base().begin()); 00113 const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1)); 00114 00115 // Check whether __other points within the contiguous storage. 00116 return __l(__other, __begin) || __l(__end, __other); 00117 } 00118 00119 /* Fallback overload for when we can't tell, assume it is valid. */ 00120 template<typename _Iterator, typename _Sequence> 00121 inline bool 00122 __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...) 00123 { return true; } 00124 00125 /* Handle sequences with contiguous storage */ 00126 template<typename _Iterator, typename _Sequence, typename _InputIterator> 00127 inline bool 00128 __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it, 00129 const _InputIterator& __other, 00130 const _InputIterator& __other_end, 00131 std::__true_type) 00132 { 00133 if (__other == __other_end) 00134 return true; // inserting nothing is safe even if not foreign iters 00135 if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end()) 00136 return true; // can't be self-inserting if self is empty 00137 return __foreign_iterator_aux4(__it, std::__addressof(*__other)); 00138 } 00139 00140 /* Handle non-contiguous containers, assume it is valid. */ 00141 template<typename _Iterator, typename _Sequence, typename _InputIterator> 00142 inline bool 00143 __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&, 00144 const _InputIterator&, const _InputIterator&, 00145 std::__false_type) 00146 { return true; } 00147 00148 /** Handle debug iterators from the same type of container. */ 00149 template<typename _Iterator, typename _Sequence, typename _OtherIterator> 00150 inline bool 00151 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 00152 const _Safe_iterator<_OtherIterator, _Sequence>& __other, 00153 const _Safe_iterator<_OtherIterator, _Sequence>&) 00154 { return __it._M_get_sequence() != __other._M_get_sequence(); } 00155 00156 /** Handle debug iterators from different types of container. */ 00157 template<typename _Iterator, typename _Sequence, typename _OtherIterator, 00158 typename _OtherSequence> 00159 inline bool 00160 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 00161 const _Safe_iterator<_OtherIterator, _OtherSequence>&, 00162 const _Safe_iterator<_OtherIterator, _OtherSequence>&) 00163 { return true; } 00164 00165 /* Handle non-debug iterators. */ 00166 template<typename _Iterator, typename _Sequence, typename _InputIterator> 00167 inline bool 00168 __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it, 00169 const _InputIterator& __other, 00170 const _InputIterator& __other_end) 00171 { 00172 #if __cplusplus < 201103L 00173 typedef _Is_contiguous_sequence<_Sequence> __tag; 00174 #else 00175 using __lvalref = std::is_lvalue_reference< 00176 typename std::iterator_traits<_InputIterator>::reference>; 00177 using __contiguous = _Is_contiguous_sequence<_Sequence>; 00178 using __tag = typename std::conditional<__lvalref::value, __contiguous, 00179 std::__false_type>::type; 00180 #endif 00181 return __foreign_iterator_aux3(__it, __other, __other_end, __tag()); 00182 } 00183 00184 /* Handle the case where we aren't really inserting a range after all */ 00185 template<typename _Iterator, typename _Sequence, typename _Integral> 00186 inline bool 00187 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&, 00188 _Integral, _Integral, 00189 std::__true_type) 00190 { return true; } 00191 00192 /* Handle all iterators. */ 00193 template<typename _Iterator, typename _Sequence, 00194 typename _InputIterator> 00195 inline bool 00196 __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it, 00197 _InputIterator __other, _InputIterator __other_end, 00198 std::__false_type) 00199 { 00200 return _Insert_range_from_self_is_safe<_Sequence>::__value 00201 || __foreign_iterator_aux2(__it, std::__miter_base(__other), 00202 std::__miter_base(__other_end)); 00203 } 00204 00205 template<typename _Iterator, typename _Sequence, 00206 typename _InputIterator> 00207 inline bool 00208 __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it, 00209 _InputIterator __other, _InputIterator __other_end) 00210 { 00211 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 00212 return __foreign_iterator_aux(__it, __other, __other_end, _Integral()); 00213 } 00214 00215 /** Checks that __s is non-NULL or __n == 0, and then returns __s. */ 00216 template<typename _CharT, typename _Integer> 00217 inline const _CharT* 00218 __check_string(const _CharT* __s, 00219 const _Integer& __n __attribute__((__unused__))) 00220 { 00221 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00222 __glibcxx_assert(__s != 0 || __n == 0); 00223 #endif 00224 return __s; 00225 } 00226 00227 /** Checks that __s is non-NULL and then returns __s. */ 00228 template<typename _CharT> 00229 inline const _CharT* 00230 __check_string(const _CharT* __s) 00231 { 00232 #ifdef _GLIBCXX_DEBUG_PEDANTIC 00233 __glibcxx_assert(__s != 0); 00234 #endif 00235 return __s; 00236 } 00237 00238 // Can't check if an input iterator sequence is sorted, because we 00239 // can't step through the sequence. 00240 template<typename _InputIterator> 00241 inline bool 00242 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00243 std::input_iterator_tag) 00244 { return true; } 00245 00246 // Can verify if a forward iterator sequence is in fact sorted using 00247 // std::__is_sorted 00248 template<typename _ForwardIterator> 00249 inline bool 00250 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00251 std::forward_iterator_tag) 00252 { 00253 if (__first == __last) 00254 return true; 00255 00256 _ForwardIterator __next = __first; 00257 for (++__next; __next != __last; __first = __next, (void)++__next) 00258 if (*__next < *__first) 00259 return false; 00260 00261 return true; 00262 } 00263 00264 // Can't check if an input iterator sequence is sorted, because we can't step 00265 // through the sequence. 00266 template<typename _InputIterator, typename _Predicate> 00267 inline bool 00268 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 00269 _Predicate, std::input_iterator_tag) 00270 { return true; } 00271 00272 // Can verify if a forward iterator sequence is in fact sorted using 00273 // std::__is_sorted 00274 template<typename _ForwardIterator, typename _Predicate> 00275 inline bool 00276 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 00277 _Predicate __pred, std::forward_iterator_tag) 00278 { 00279 if (__first == __last) 00280 return true; 00281 00282 _ForwardIterator __next = __first; 00283 for (++__next; __next != __last; __first = __next, (void)++__next) 00284 if (__pred(*__next, *__first)) 00285 return false; 00286 00287 return true; 00288 } 00289 00290 // Determine if a sequence is sorted. 00291 template<typename _InputIterator> 00292 inline bool 00293 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 00294 { 00295 // Verify that the < operator for elements in the sequence is a 00296 // StrictWeakOrdering by checking that it is irreflexive. 00297 __glibcxx_assert(__first == __last || !(*__first < *__first)); 00298 00299 return __check_sorted_aux(__first, __last, 00300 std::__iterator_category(__first)); 00301 } 00302 00303 template<typename _InputIterator, typename _Predicate> 00304 inline bool 00305 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 00306 _Predicate __pred) 00307 { 00308 // Verify that the predicate is StrictWeakOrdering by checking that it 00309 // is irreflexive. 00310 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 00311 00312 return __check_sorted_aux(__first, __last, __pred, 00313 std::__iterator_category(__first)); 00314 } 00315 00316 template<typename _InputIterator> 00317 inline bool 00318 __check_sorted_set_aux(const _InputIterator& __first, 00319 const _InputIterator& __last, 00320 std::__true_type) 00321 { return __check_sorted(__first, __last); } 00322 00323 template<typename _InputIterator> 00324 inline bool 00325 __check_sorted_set_aux(const _InputIterator&, 00326 const _InputIterator&, 00327 std::__false_type) 00328 { return true; } 00329 00330 template<typename _InputIterator, typename _Predicate> 00331 inline bool 00332 __check_sorted_set_aux(const _InputIterator& __first, 00333 const _InputIterator& __last, 00334 _Predicate __pred, std::__true_type) 00335 { return __check_sorted(__first, __last, __pred); } 00336 00337 template<typename _InputIterator, typename _Predicate> 00338 inline bool 00339 __check_sorted_set_aux(const _InputIterator&, 00340 const _InputIterator&, _Predicate, 00341 std::__false_type) 00342 { return true; } 00343 00344 // ... special variant used in std::merge, std::includes, std::set_*. 00345 template<typename _InputIterator1, typename _InputIterator2> 00346 inline bool 00347 __check_sorted_set(const _InputIterator1& __first, 00348 const _InputIterator1& __last, 00349 const _InputIterator2&) 00350 { 00351 typedef typename std::iterator_traits<_InputIterator1>::value_type 00352 _ValueType1; 00353 typedef typename std::iterator_traits<_InputIterator2>::value_type 00354 _ValueType2; 00355 00356 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00357 _SameType; 00358 return __check_sorted_set_aux(__first, __last, _SameType()); 00359 } 00360 00361 template<typename _InputIterator1, typename _InputIterator2, 00362 typename _Predicate> 00363 inline bool 00364 __check_sorted_set(const _InputIterator1& __first, 00365 const _InputIterator1& __last, 00366 const _InputIterator2&, _Predicate __pred) 00367 { 00368 typedef typename std::iterator_traits<_InputIterator1>::value_type 00369 _ValueType1; 00370 typedef typename std::iterator_traits<_InputIterator2>::value_type 00371 _ValueType2; 00372 00373 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 00374 _SameType; 00375 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 00376 } 00377 00378 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00379 // 270. Binary search requirements overly strict 00380 // Determine if a sequence is partitioned w.r.t. this element. 00381 template<typename _ForwardIterator, typename _Tp> 00382 inline bool 00383 __check_partitioned_lower(_ForwardIterator __first, 00384 _ForwardIterator __last, const _Tp& __value) 00385 { 00386 while (__first != __last && *__first < __value) 00387 ++__first; 00388 if (__first != __last) 00389 { 00390 ++__first; 00391 while (__first != __last && !(*__first < __value)) 00392 ++__first; 00393 } 00394 return __first == __last; 00395 } 00396 00397 template<typename _ForwardIterator, typename _Tp> 00398 inline bool 00399 __check_partitioned_upper(_ForwardIterator __first, 00400 _ForwardIterator __last, const _Tp& __value) 00401 { 00402 while (__first != __last && !(__value < *__first)) 00403 ++__first; 00404 if (__first != __last) 00405 { 00406 ++__first; 00407 while (__first != __last && __value < *__first) 00408 ++__first; 00409 } 00410 return __first == __last; 00411 } 00412 00413 // Determine if a sequence is partitioned w.r.t. this element. 00414 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00415 inline bool 00416 __check_partitioned_lower(_ForwardIterator __first, 00417 _ForwardIterator __last, const _Tp& __value, 00418 _Pred __pred) 00419 { 00420 while (__first != __last && bool(__pred(*__first, __value))) 00421 ++__first; 00422 if (__first != __last) 00423 { 00424 ++__first; 00425 while (__first != __last && !bool(__pred(*__first, __value))) 00426 ++__first; 00427 } 00428 return __first == __last; 00429 } 00430 00431 template<typename _ForwardIterator, typename _Tp, typename _Pred> 00432 inline bool 00433 __check_partitioned_upper(_ForwardIterator __first, 00434 _ForwardIterator __last, const _Tp& __value, 00435 _Pred __pred) 00436 { 00437 while (__first != __last && !bool(__pred(__value, *__first))) 00438 ++__first; 00439 if (__first != __last) 00440 { 00441 ++__first; 00442 while (__first != __last && bool(__pred(__value, *__first))) 00443 ++__first; 00444 } 00445 return __first == __last; 00446 } 00447 00448 #if __cplusplus >= 201103L 00449 struct _Irreflexive_checker 00450 { 00451 template<typename _It> 00452 static typename std::iterator_traits<_It>::reference 00453 __deref(); 00454 00455 template<typename _It, 00456 typename = decltype(__deref<_It>() < __deref<_It>())> 00457 static bool 00458 _S_is_valid(_It __it) 00459 { return !(*__it < *__it); } 00460 00461 // Fallback method if operator doesn't exist. 00462 template<typename... _Args> 00463 static bool 00464 _S_is_valid(_Args...) 00465 { return true; } 00466 00467 template<typename _It, typename _Pred, typename 00468 = decltype(std::declval<_Pred>()(__deref<_It>(), __deref<_It>()))> 00469 static bool 00470 _S_is_valid_pred(_It __it, _Pred __pred) 00471 { return !__pred(*__it, *__it); } 00472 00473 // Fallback method if predicate can't be invoked. 00474 template<typename... _Args> 00475 static bool 00476 _S_is_valid_pred(_Args...) 00477 { return true; } 00478 }; 00479 00480 template<typename _Iterator> 00481 inline bool 00482 __is_irreflexive(_Iterator __it) 00483 { return _Irreflexive_checker::_S_is_valid(__it); } 00484 00485 template<typename _Iterator, typename _Pred> 00486 inline bool 00487 __is_irreflexive_pred(_Iterator __it, _Pred __pred) 00488 { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); } 00489 #endif 00490 00491 } // namespace __gnu_debug 00492 00493 #endif