1 // Debugging support implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2019 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/functions.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H 30 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1 31 32 #include <bits/move.h> // for __addressof 33 #include <bits/stl_function.h> // for less 34 35 #if __cplusplus >= 201103L 36 # include <bits/stl_iterator.h> // for __miter_base 37 # include <type_traits> // for is_lvalue_reference and conditional. 38 #endif 39 40 #include <debug/helper_functions.h> 41 #include <debug/formatter.h> 42 43 namespace __gnu_debug 44 { 45 template<typename _Sequence> 46 struct _Insert_range_from_self_is_safe 47 { enum { __value = 0 }; }; 48 49 template<typename _Sequence> 50 struct _Is_contiguous_sequence : std::__false_type { }; 51 52 // An arbitrary iterator pointer is not singular. 53 inline bool __check_singular_aux(const void *)54 __check_singular_aux(const void*) { return false; } 55 56 // We may have an iterator that derives from _Safe_iterator_base but isn't 57 // a _Safe_iterator. 58 template<typename _Iterator> 59 inline bool __check_singular(const _Iterator & __x)60 __check_singular(const _Iterator& __x) 61 { return __check_singular_aux(std::__addressof(__x)); } 62 63 /** Non-NULL pointers are nonsingular. */ 64 template<typename _Tp> 65 inline bool __check_singular(const _Tp * __ptr)66 __check_singular(const _Tp* __ptr) 67 { return __ptr == 0; } 68 69 /* Checks that [first, last) is a valid range, and then returns 70 * __first. This routine is useful when we can't use a separate 71 * assertion statement because, e.g., we are in a constructor. 72 */ 73 template<typename _InputIterator> 74 inline _InputIterator __check_valid_range(const _InputIterator & __first,const _InputIterator & __last,const char * __file,unsigned int __line,const char * __function)75 __check_valid_range(const _InputIterator& __first, 76 const _InputIterator& __last, 77 const char* __file, 78 unsigned int __line, 79 const char* __function) 80 { 81 __glibcxx_check_valid_range_at(__first, __last, 82 __file, __line, __function); 83 return __first; 84 } 85 86 /* Handle the case where __other is a pointer to _Sequence::value_type. */ 87 template<typename _Iterator, typename _Sequence, typename _Category> 88 inline bool __foreign_iterator_aux4(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,const typename _Sequence::value_type * __other)89 __foreign_iterator_aux4( 90 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 91 const typename _Sequence::value_type* __other) 92 { 93 typedef const typename _Sequence::value_type* _PointerType; 94 typedef std::less<_PointerType> _Less; 95 #if __cplusplus >= 201103L 96 constexpr _Less __l{}; 97 #else 98 const _Less __l = _Less(); 99 #endif 100 const _Sequence* __seq = __it._M_get_sequence(); 101 const _PointerType __begin = std::__addressof(*__seq->_M_base().begin()); 102 const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1)); 103 104 // Check whether __other points within the contiguous storage. 105 return __l(__other, __begin) || __l(__end, __other); 106 } 107 108 /* Fallback overload for when we can't tell, assume it is valid. */ 109 template<typename _Iterator, typename _Sequence, typename _Category> 110 inline bool __foreign_iterator_aux4(const _Safe_iterator<_Iterator,_Sequence,_Category> &,...)111 __foreign_iterator_aux4( 112 const _Safe_iterator<_Iterator, _Sequence, _Category>&, ...) 113 { return true; } 114 115 /* Handle sequences with contiguous storage */ 116 template<typename _Iterator, typename _Sequence, typename _Category, 117 typename _InputIterator> 118 inline bool __foreign_iterator_aux3(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,const _InputIterator & __other,const _InputIterator & __other_end,std::__true_type)119 __foreign_iterator_aux3( 120 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 121 const _InputIterator& __other, const _InputIterator& __other_end, 122 std::__true_type) 123 { 124 if (__other == __other_end) 125 return true; // inserting nothing is safe even if not foreign iters 126 if (__it._M_get_sequence()->empty()) 127 return true; // can't be self-inserting if self is empty 128 return __foreign_iterator_aux4(__it, std::__addressof(*__other)); 129 } 130 131 /* Handle non-contiguous containers, assume it is valid. */ 132 template<typename _Iterator, typename _Sequence, typename _Category, 133 typename _InputIterator> 134 inline bool __foreign_iterator_aux3(const _Safe_iterator<_Iterator,_Sequence,_Category> &,const _InputIterator &,const _InputIterator &,std::__false_type)135 __foreign_iterator_aux3( 136 const _Safe_iterator<_Iterator, _Sequence, _Category>&, 137 const _InputIterator&, const _InputIterator&, 138 std::__false_type) 139 { return true; } 140 141 /** Handle debug iterators from the same type of container. */ 142 template<typename _Iterator, typename _Sequence, typename _Category, 143 typename _OtherIterator> 144 inline bool __foreign_iterator_aux2(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,const _Safe_iterator<_OtherIterator,_Sequence,_Category> & __other,const _Safe_iterator<_OtherIterator,_Sequence,_Category> &)145 __foreign_iterator_aux2( 146 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 147 const _Safe_iterator<_OtherIterator, _Sequence, _Category>& __other, 148 const _Safe_iterator<_OtherIterator, _Sequence, _Category>&) 149 { return __it._M_get_sequence() != __other._M_get_sequence(); } 150 151 /** Handle debug iterators from different types of container. */ 152 template<typename _Iterator, typename _Sequence, typename _Category, 153 typename _OtherIterator, typename _OtherSequence, 154 typename _OtherCategory> 155 inline bool __foreign_iterator_aux2(const _Safe_iterator<_Iterator,_Sequence,_Category> &,const _Safe_iterator<_OtherIterator,_OtherSequence,_OtherCategory> &,const _Safe_iterator<_OtherIterator,_OtherSequence,_OtherCategory> &)156 __foreign_iterator_aux2( 157 const _Safe_iterator<_Iterator, _Sequence, _Category>&, 158 const _Safe_iterator<_OtherIterator, _OtherSequence, 159 _OtherCategory>&, 160 const _Safe_iterator<_OtherIterator, _OtherSequence, 161 _OtherCategory>&) 162 { return true; } 163 164 /* Handle non-debug iterators. */ 165 template<typename _Iterator, typename _Sequence, typename _Category, 166 typename _InputIterator> 167 inline bool __foreign_iterator_aux2(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,const _InputIterator & __other,const _InputIterator & __other_end)168 __foreign_iterator_aux2( 169 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 170 const _InputIterator& __other, 171 const _InputIterator& __other_end) 172 { 173 #if __cplusplus < 201103L 174 typedef _Is_contiguous_sequence<_Sequence> __tag; 175 #else 176 using __lvalref = std::is_lvalue_reference< 177 typename std::iterator_traits<_InputIterator>::reference>; 178 using __contiguous = _Is_contiguous_sequence<_Sequence>; 179 using __tag = typename std::conditional<__lvalref::value, __contiguous, 180 std::__false_type>::type; 181 #endif 182 return __foreign_iterator_aux3(__it, __other, __other_end, __tag()); 183 } 184 185 /* Handle the case where we aren't really inserting a range after all */ 186 template<typename _Iterator, typename _Sequence, typename _Category, 187 typename _Integral> 188 inline bool __foreign_iterator_aux(const _Safe_iterator<_Iterator,_Sequence,_Category> &,_Integral,_Integral,std::__true_type)189 __foreign_iterator_aux( 190 const _Safe_iterator<_Iterator, _Sequence, _Category>&, 191 _Integral, _Integral, std::__true_type) 192 { return true; } 193 194 /* Handle all iterators. */ 195 template<typename _Iterator, typename _Sequence, typename _Category, 196 typename _InputIterator> 197 inline bool __foreign_iterator_aux(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,_InputIterator __other,_InputIterator __other_end,std::__false_type)198 __foreign_iterator_aux( 199 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 200 _InputIterator __other, _InputIterator __other_end, 201 std::__false_type) 202 { 203 return _Insert_range_from_self_is_safe<_Sequence>::__value 204 || __foreign_iterator_aux2(__it, std::__miter_base(__other), 205 std::__miter_base(__other_end)); 206 } 207 208 template<typename _Iterator, typename _Sequence, typename _Category, 209 typename _InputIterator> 210 inline bool __foreign_iterator(const _Safe_iterator<_Iterator,_Sequence,_Category> & __it,_InputIterator __other,_InputIterator __other_end)211 __foreign_iterator( 212 const _Safe_iterator<_Iterator, _Sequence, _Category>& __it, 213 _InputIterator __other, _InputIterator __other_end) 214 { 215 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 216 return __foreign_iterator_aux(__it, __other, __other_end, _Integral()); 217 } 218 219 // Can't check if an input iterator sequence is sorted, because we 220 // can't step through the sequence. 221 template<typename _InputIterator> 222 inline bool __check_sorted_aux(const _InputIterator &,const _InputIterator &,std::input_iterator_tag)223 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 224 std::input_iterator_tag) 225 { return true; } 226 227 // Can verify if a forward iterator sequence is in fact sorted using 228 // std::__is_sorted 229 template<typename _ForwardIterator> 230 inline bool __check_sorted_aux(_ForwardIterator __first,_ForwardIterator __last,std::forward_iterator_tag)231 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 232 std::forward_iterator_tag) 233 { 234 if (__first == __last) 235 return true; 236 237 _ForwardIterator __next = __first; 238 for (++__next; __next != __last; __first = __next, (void)++__next) 239 if (*__next < *__first) 240 return false; 241 242 return true; 243 } 244 245 // Can't check if an input iterator sequence is sorted, because we can't step 246 // through the sequence. 247 template<typename _InputIterator, typename _Predicate> 248 inline bool __check_sorted_aux(const _InputIterator &,const _InputIterator &,_Predicate,std::input_iterator_tag)249 __check_sorted_aux(const _InputIterator&, const _InputIterator&, 250 _Predicate, std::input_iterator_tag) 251 { return true; } 252 253 // Can verify if a forward iterator sequence is in fact sorted using 254 // std::__is_sorted 255 template<typename _ForwardIterator, typename _Predicate> 256 inline bool __check_sorted_aux(_ForwardIterator __first,_ForwardIterator __last,_Predicate __pred,std::forward_iterator_tag)257 __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last, 258 _Predicate __pred, std::forward_iterator_tag) 259 { 260 if (__first == __last) 261 return true; 262 263 _ForwardIterator __next = __first; 264 for (++__next; __next != __last; __first = __next, (void)++__next) 265 if (__pred(*__next, *__first)) 266 return false; 267 268 return true; 269 } 270 271 // Determine if a sequence is sorted. 272 template<typename _InputIterator> 273 inline bool __check_sorted(const _InputIterator & __first,const _InputIterator & __last)274 __check_sorted(const _InputIterator& __first, const _InputIterator& __last) 275 { 276 // Verify that the < operator for elements in the sequence is a 277 // StrictWeakOrdering by checking that it is irreflexive. 278 __glibcxx_assert(__first == __last || !(*__first < *__first)); 279 280 return __check_sorted_aux(__first, __last, 281 std::__iterator_category(__first)); 282 } 283 284 template<typename _InputIterator, typename _Predicate> 285 inline bool __check_sorted(const _InputIterator & __first,const _InputIterator & __last,_Predicate __pred)286 __check_sorted(const _InputIterator& __first, const _InputIterator& __last, 287 _Predicate __pred) 288 { 289 // Verify that the predicate is StrictWeakOrdering by checking that it 290 // is irreflexive. 291 __glibcxx_assert(__first == __last || !__pred(*__first, *__first)); 292 293 return __check_sorted_aux(__first, __last, __pred, 294 std::__iterator_category(__first)); 295 } 296 297 template<typename _InputIterator> 298 inline bool __check_sorted_set_aux(const _InputIterator & __first,const _InputIterator & __last,std::__true_type)299 __check_sorted_set_aux(const _InputIterator& __first, 300 const _InputIterator& __last, 301 std::__true_type) 302 { return __check_sorted(__first, __last); } 303 304 template<typename _InputIterator> 305 inline bool __check_sorted_set_aux(const _InputIterator &,const _InputIterator &,std::__false_type)306 __check_sorted_set_aux(const _InputIterator&, 307 const _InputIterator&, 308 std::__false_type) 309 { return true; } 310 311 template<typename _InputIterator, typename _Predicate> 312 inline bool __check_sorted_set_aux(const _InputIterator & __first,const _InputIterator & __last,_Predicate __pred,std::__true_type)313 __check_sorted_set_aux(const _InputIterator& __first, 314 const _InputIterator& __last, 315 _Predicate __pred, std::__true_type) 316 { return __check_sorted(__first, __last, __pred); } 317 318 template<typename _InputIterator, typename _Predicate> 319 inline bool __check_sorted_set_aux(const _InputIterator &,const _InputIterator &,_Predicate,std::__false_type)320 __check_sorted_set_aux(const _InputIterator&, 321 const _InputIterator&, _Predicate, 322 std::__false_type) 323 { return true; } 324 325 // ... special variant used in std::merge, std::includes, std::set_*. 326 template<typename _InputIterator1, typename _InputIterator2> 327 inline bool __check_sorted_set(const _InputIterator1 & __first,const _InputIterator1 & __last,const _InputIterator2 &)328 __check_sorted_set(const _InputIterator1& __first, 329 const _InputIterator1& __last, 330 const _InputIterator2&) 331 { 332 typedef typename std::iterator_traits<_InputIterator1>::value_type 333 _ValueType1; 334 typedef typename std::iterator_traits<_InputIterator2>::value_type 335 _ValueType2; 336 337 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 338 _SameType; 339 return __check_sorted_set_aux(__first, __last, _SameType()); 340 } 341 342 template<typename _InputIterator1, typename _InputIterator2, 343 typename _Predicate> 344 inline bool __check_sorted_set(const _InputIterator1 & __first,const _InputIterator1 & __last,const _InputIterator2 &,_Predicate __pred)345 __check_sorted_set(const _InputIterator1& __first, 346 const _InputIterator1& __last, 347 const _InputIterator2&, _Predicate __pred) 348 { 349 typedef typename std::iterator_traits<_InputIterator1>::value_type 350 _ValueType1; 351 typedef typename std::iterator_traits<_InputIterator2>::value_type 352 _ValueType2; 353 354 typedef typename std::__are_same<_ValueType1, _ValueType2>::__type 355 _SameType; 356 return __check_sorted_set_aux(__first, __last, __pred, _SameType()); 357 } 358 359 // _GLIBCXX_RESOLVE_LIB_DEFECTS 360 // 270. Binary search requirements overly strict 361 // Determine if a sequence is partitioned w.r.t. this element. 362 template<typename _ForwardIterator, typename _Tp> 363 inline bool __check_partitioned_lower(_ForwardIterator __first,_ForwardIterator __last,const _Tp & __value)364 __check_partitioned_lower(_ForwardIterator __first, 365 _ForwardIterator __last, const _Tp& __value) 366 { 367 while (__first != __last && *__first < __value) 368 ++__first; 369 if (__first != __last) 370 { 371 ++__first; 372 while (__first != __last && !(*__first < __value)) 373 ++__first; 374 } 375 return __first == __last; 376 } 377 378 template<typename _ForwardIterator, typename _Tp> 379 inline bool __check_partitioned_upper(_ForwardIterator __first,_ForwardIterator __last,const _Tp & __value)380 __check_partitioned_upper(_ForwardIterator __first, 381 _ForwardIterator __last, const _Tp& __value) 382 { 383 while (__first != __last && !(__value < *__first)) 384 ++__first; 385 if (__first != __last) 386 { 387 ++__first; 388 while (__first != __last && __value < *__first) 389 ++__first; 390 } 391 return __first == __last; 392 } 393 394 // Determine if a sequence is partitioned w.r.t. this element. 395 template<typename _ForwardIterator, typename _Tp, typename _Pred> 396 inline bool __check_partitioned_lower(_ForwardIterator __first,_ForwardIterator __last,const _Tp & __value,_Pred __pred)397 __check_partitioned_lower(_ForwardIterator __first, 398 _ForwardIterator __last, const _Tp& __value, 399 _Pred __pred) 400 { 401 while (__first != __last && bool(__pred(*__first, __value))) 402 ++__first; 403 if (__first != __last) 404 { 405 ++__first; 406 while (__first != __last && !bool(__pred(*__first, __value))) 407 ++__first; 408 } 409 return __first == __last; 410 } 411 412 template<typename _ForwardIterator, typename _Tp, typename _Pred> 413 inline bool __check_partitioned_upper(_ForwardIterator __first,_ForwardIterator __last,const _Tp & __value,_Pred __pred)414 __check_partitioned_upper(_ForwardIterator __first, 415 _ForwardIterator __last, const _Tp& __value, 416 _Pred __pred) 417 { 418 while (__first != __last && !bool(__pred(__value, *__first))) 419 ++__first; 420 if (__first != __last) 421 { 422 ++__first; 423 while (__first != __last && bool(__pred(__value, *__first))) 424 ++__first; 425 } 426 return __first == __last; 427 } 428 429 #if __cplusplus >= 201103L 430 struct _Irreflexive_checker 431 { 432 template<typename _It> 433 static typename std::iterator_traits<_It>::reference 434 __deref(); 435 436 template<typename _It, 437 typename = decltype(__deref<_It>() < __deref<_It>())> 438 static bool _S_is_valid_Irreflexive_checker439 _S_is_valid(_It __it) 440 { return !(*__it < *__it); } 441 442 // Fallback method if operator doesn't exist. 443 template<typename... _Args> 444 static bool _S_is_valid_Irreflexive_checker445 _S_is_valid(_Args...) 446 { return true; } 447 448 template<typename _It, typename _Pred, typename 449 = decltype(std::declval<_Pred>()(__deref<_It>(), __deref<_It>()))> 450 static bool _S_is_valid_pred_Irreflexive_checker451 _S_is_valid_pred(_It __it, _Pred __pred) 452 { return !__pred(*__it, *__it); } 453 454 // Fallback method if predicate can't be invoked. 455 template<typename... _Args> 456 static bool _S_is_valid_pred_Irreflexive_checker457 _S_is_valid_pred(_Args...) 458 { return true; } 459 }; 460 461 template<typename _Iterator> 462 inline bool __is_irreflexive(_Iterator __it)463 __is_irreflexive(_Iterator __it) 464 { return _Irreflexive_checker::_S_is_valid(__it); } 465 466 template<typename _Iterator, typename _Pred> 467 inline bool __is_irreflexive_pred(_Iterator __it,_Pred __pred)468 __is_irreflexive_pred(_Iterator __it, _Pred __pred) 469 { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); } 470 #endif 471 472 } // namespace __gnu_debug 473 474 #endif 475