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