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