1 // Debugging support implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2021 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/helper_functions.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H 30 #define _GLIBCXX_DEBUG_HELPER_FUNCTIONS_H 1 31 32 #include <bits/move.h> // for __addressof 33 #include <bits/stl_iterator_base_types.h> // for iterator_traits, 34 // categories and _Iter_base 35 #include <bits/cpp_type_traits.h> // for __is_integer 36 37 #include <bits/stl_pair.h> // for pair 38 39 namespace __gnu_debug 40 { 41 template<typename _Iterator, typename _Sequence, typename _Category> 42 class _Safe_iterator; 43 44 #if __cplusplus >= 201103L 45 template<typename _Iterator, typename _Sequence> 46 class _Safe_local_iterator; 47 #endif 48 49 /** The precision to which we can calculate the distance between 50 * two iterators. 51 */ 52 enum _Distance_precision 53 { 54 __dp_none, // Not even an iterator type 55 __dp_equality, //< Can compare iterator equality, only 56 __dp_sign, //< Can determine equality and ordering 57 __dp_sign_max_size, //< __dp_sign and gives max range size 58 __dp_exact //< Can determine distance precisely 59 }; 60 61 template<typename _Iterator, 62 typename = typename std::__is_integer<_Iterator>::__type> 63 struct _Distance_traits 64 { 65 private: 66 typedef 67 typename std::iterator_traits<_Iterator>::difference_type _ItDiffType; 68 69 template<typename _DiffType, 70 typename = typename std::__is_void<_DiffType>::__type> 71 struct _DiffTraits 72 { typedef _DiffType __type; }; 73 74 template<typename _DiffType> 75 struct _DiffTraits<_DiffType, std::__true_type> 76 { typedef std::ptrdiff_t __type; }; 77 78 typedef typename _DiffTraits<_ItDiffType>::__type _DiffType; 79 80 public: 81 typedef std::pair<_DiffType, _Distance_precision> __type; 82 }; 83 84 template<typename _Integral> 85 struct _Distance_traits<_Integral, std::__true_type> 86 { typedef std::pair<std::ptrdiff_t, _Distance_precision> __type; }; 87 88 /** Determine the distance between two iterators with some known 89 * precision. 90 */ 91 template<typename _Iterator> 92 _GLIBCXX_CONSTEXPR 93 inline typename _Distance_traits<_Iterator>::__type 94 __get_distance(_Iterator __lhs, _Iterator __rhs, 95 std::random_access_iterator_tag) 96 { return std::make_pair(__rhs - __lhs, __dp_exact); } 97 98 template<typename _Iterator> 99 _GLIBCXX14_CONSTEXPR 100 inline typename _Distance_traits<_Iterator>::__type 101 __get_distance(_Iterator __lhs, _Iterator __rhs, 102 std::input_iterator_tag) 103 { 104 if (__lhs == __rhs) 105 return std::make_pair(0, __dp_exact); 106 107 return std::make_pair(1, __dp_equality); 108 } 109 110 template<typename _Iterator> 111 _GLIBCXX_CONSTEXPR 112 inline typename _Distance_traits<_Iterator>::__type 113 __get_distance(_Iterator __lhs, _Iterator __rhs) 114 { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); } 115 116 // An arbitrary iterator pointer is not singular. 117 inline bool 118 __check_singular_aux(const void*) { return false; } 119 120 // We may have an iterator that derives from _Safe_iterator_base but isn't 121 // a _Safe_iterator. 122 template<typename _Iterator> 123 _GLIBCXX_CONSTEXPR 124 inline bool 125 __check_singular(_Iterator const& __x) 126 { 127 return 128 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED 129 __builtin_is_constant_evaluated() ? false : 130 #endif 131 __check_singular_aux(std::__addressof(__x)); 132 } 133 134 /** Non-NULL pointers are nonsingular. */ 135 template<typename _Tp> 136 _GLIBCXX_CONSTEXPR 137 inline bool 138 __check_singular(_Tp* const& __ptr) 139 { 140 return 141 #ifdef _GLIBCXX_HAVE_BUILTIN_IS_CONSTANT_EVALUATED 142 __builtin_is_constant_evaluated() ? false : 143 #endif 144 __ptr == 0; 145 } 146 147 /** We say that integral types for a valid range, and defer to other 148 * routines to realize what to do with integral types instead of 149 * iterators. 150 */ 151 template<typename _Integral> 152 _GLIBCXX_CONSTEXPR 153 inline bool 154 __valid_range_aux(_Integral, _Integral, std::__true_type) 155 { return true; } 156 157 template<typename _Integral> 158 _GLIBCXX20_CONSTEXPR 159 inline bool 160 __valid_range_aux(_Integral, _Integral, 161 typename _Distance_traits<_Integral>::__type& __dist, 162 std::__true_type) 163 { 164 __dist = std::make_pair(0, __dp_none); 165 return true; 166 } 167 168 template<typename _InputIterator> 169 _GLIBCXX_CONSTEXPR 170 inline bool 171 __valid_range_aux(_InputIterator __first, _InputIterator __last, 172 std::input_iterator_tag) 173 { 174 return __first == __last 175 || (!__check_singular(__first) && !__check_singular(__last)); 176 } 177 178 template<typename _InputIterator> 179 _GLIBCXX_CONSTEXPR 180 inline bool 181 __valid_range_aux(_InputIterator __first, _InputIterator __last, 182 std::random_access_iterator_tag) 183 { 184 return 185 __valid_range_aux(__first, __last, std::input_iterator_tag()) 186 && __first <= __last; 187 } 188 189 /** We have iterators, so figure out what kind of iterators they are 190 * to see if we can check the range ahead of time. 191 */ 192 template<typename _InputIterator> 193 _GLIBCXX_CONSTEXPR 194 inline bool 195 __valid_range_aux(_InputIterator __first, _InputIterator __last, 196 std::__false_type) 197 { 198 return __valid_range_aux(__first, __last, 199 std::__iterator_category(__first)); 200 } 201 202 template<typename _InputIterator> 203 _GLIBCXX20_CONSTEXPR 204 inline bool 205 __valid_range_aux(_InputIterator __first, _InputIterator __last, 206 typename _Distance_traits<_InputIterator>::__type& __dist, 207 std::__false_type) 208 { 209 if (!__valid_range_aux(__first, __last, std::input_iterator_tag())) 210 return false; 211 212 __dist = __get_distance(__first, __last); 213 switch (__dist.second) 214 { 215 case __dp_none: 216 break; 217 case __dp_equality: 218 if (__dist.first == 0) 219 return true; 220 break; 221 case __dp_sign: 222 case __dp_sign_max_size: 223 case __dp_exact: 224 return __dist.first >= 0; 225 } 226 227 // Can't tell so assume it is fine. 228 return true; 229 } 230 231 /** Don't know what these iterators are, or if they are even 232 * iterators (we may get an integral type for InputIterator), so 233 * see if they are integral and pass them on to the next phase 234 * otherwise. 235 */ 236 template<typename _InputIterator> 237 _GLIBCXX20_CONSTEXPR 238 inline bool 239 __valid_range(_InputIterator __first, _InputIterator __last, 240 typename _Distance_traits<_InputIterator>::__type& __dist) 241 { 242 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 243 return __valid_range_aux(__first, __last, __dist, _Integral()); 244 } 245 246 template<typename _Iterator, typename _Sequence, typename _Category> 247 bool 248 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 249 const _Safe_iterator<_Iterator, _Sequence, _Category>&, 250 typename _Distance_traits<_Iterator>::__type&); 251 252 #if __cplusplus >= 201103L 253 template<typename _Iterator,typename _Sequence> 254 bool 255 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&, 256 const _Safe_local_iterator<_Iterator, _Sequence>&, 257 typename _Distance_traits<_Iterator>::__type&); 258 #endif 259 260 template<typename _InputIterator> 261 _GLIBCXX14_CONSTEXPR 262 inline bool 263 __valid_range(_InputIterator __first, _InputIterator __last) 264 { 265 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 266 return __valid_range_aux(__first, __last, _Integral()); 267 } 268 269 template<typename _Iterator, typename _Sequence, typename _Category> 270 bool 271 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 272 const _Safe_iterator<_Iterator, _Sequence, _Category>&); 273 274 #if __cplusplus >= 201103L 275 template<typename _Iterator, typename _Sequence> 276 bool 277 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&, 278 const _Safe_local_iterator<_Iterator, _Sequence>&); 279 #endif 280 281 // Fallback method, always ok. 282 template<typename _InputIterator, typename _Size> 283 _GLIBCXX_CONSTEXPR 284 inline bool 285 __can_advance(_InputIterator, _Size) 286 { return true; } 287 288 template<typename _Iterator, typename _Sequence, typename _Category, 289 typename _Size> 290 bool 291 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 292 _Size); 293 294 template<typename _InputIterator, typename _Diff> 295 _GLIBCXX_CONSTEXPR 296 inline bool 297 __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int) 298 { return true; } 299 300 template<typename _Iterator, typename _Sequence, typename _Category, 301 typename _Diff> 302 bool 303 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 304 const std::pair<_Diff, _Distance_precision>&, int); 305 306 /** Helper function to extract base iterator of random access safe iterator 307 * in order to reduce performance impact of debug mode. Limited to random 308 * access iterator because it is the only category for which it is possible 309 * to check for correct iterators order in the __valid_range function 310 * thanks to the < operator. 311 */ 312 template<typename _Iterator> 313 _GLIBCXX_CONSTEXPR 314 inline _Iterator 315 __base(_Iterator __it) 316 { return __it; } 317 318 #if __cplusplus < 201103L 319 template<typename _Iterator> 320 struct _Unsafe_type 321 { typedef _Iterator _Type; }; 322 #endif 323 324 /* Remove debug mode safe iterator layer, if any. */ 325 template<typename _Iterator> 326 inline _Iterator 327 __unsafe(_Iterator __it) 328 { return __it; } 329 } 330 331 #endif 332