1 // Debugging support implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2022 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 ! std::__is_constant_evaluated() 128 && __check_singular_aux(std::__addressof(__x)); 129 } 130 131 /** Non-NULL pointers are nonsingular. */ 132 template<typename _Tp> 133 _GLIBCXX_CONSTEXPR 134 inline bool 135 __check_singular(_Tp* const& __ptr) 136 { return __ptr == 0; } 137 138 /** We say that integral types for a valid range, and defer to other 139 * routines to realize what to do with integral types instead of 140 * iterators. 141 */ 142 template<typename _Integral> 143 _GLIBCXX_CONSTEXPR 144 inline bool 145 __valid_range_aux(_Integral, _Integral, std::__true_type) 146 { return true; } 147 148 template<typename _Integral> 149 _GLIBCXX20_CONSTEXPR 150 inline bool 151 __valid_range_aux(_Integral, _Integral, 152 typename _Distance_traits<_Integral>::__type& __dist, 153 std::__true_type) 154 { 155 __dist = std::make_pair(0, __dp_none); 156 return true; 157 } 158 159 template<typename _InputIterator> 160 _GLIBCXX_CONSTEXPR 161 inline bool 162 __valid_range_aux(_InputIterator __first, _InputIterator __last, 163 std::input_iterator_tag) 164 { 165 return __first == __last 166 || (!__check_singular(__first) && !__check_singular(__last)); 167 } 168 169 template<typename _InputIterator> 170 _GLIBCXX_CONSTEXPR 171 inline bool 172 __valid_range_aux(_InputIterator __first, _InputIterator __last, 173 std::random_access_iterator_tag) 174 { 175 return 176 __valid_range_aux(__first, __last, std::input_iterator_tag()) 177 && __first <= __last; 178 } 179 180 /** We have iterators, so figure out what kind of iterators they are 181 * to see if we can check the range ahead of time. 182 */ 183 template<typename _InputIterator> 184 _GLIBCXX_CONSTEXPR 185 inline bool 186 __valid_range_aux(_InputIterator __first, _InputIterator __last, 187 std::__false_type) 188 { 189 return __valid_range_aux(__first, __last, 190 std::__iterator_category(__first)); 191 } 192 193 template<typename _InputIterator> 194 _GLIBCXX20_CONSTEXPR 195 inline bool 196 __valid_range_aux(_InputIterator __first, _InputIterator __last, 197 typename _Distance_traits<_InputIterator>::__type& __dist, 198 std::__false_type) 199 { 200 if (!__valid_range_aux(__first, __last, std::input_iterator_tag())) 201 return false; 202 203 __dist = __get_distance(__first, __last); 204 switch (__dist.second) 205 { 206 case __dp_none: 207 break; 208 case __dp_equality: 209 if (__dist.first == 0) 210 return true; 211 break; 212 case __dp_sign: 213 case __dp_sign_max_size: 214 case __dp_exact: 215 return __dist.first >= 0; 216 } 217 218 // Can't tell so assume it is fine. 219 return true; 220 } 221 222 /** Don't know what these iterators are, or if they are even 223 * iterators (we may get an integral type for InputIterator), so 224 * see if they are integral and pass them on to the next phase 225 * otherwise. 226 */ 227 template<typename _InputIterator> 228 _GLIBCXX20_CONSTEXPR 229 inline bool 230 __valid_range(_InputIterator __first, _InputIterator __last, 231 typename _Distance_traits<_InputIterator>::__type& __dist) 232 { 233 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 234 return __valid_range_aux(__first, __last, __dist, _Integral()); 235 } 236 237 template<typename _Iterator, typename _Sequence, typename _Category> 238 bool 239 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 240 const _Safe_iterator<_Iterator, _Sequence, _Category>&, 241 typename _Distance_traits<_Iterator>::__type&); 242 243 #if __cplusplus >= 201103L 244 template<typename _Iterator,typename _Sequence> 245 bool 246 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&, 247 const _Safe_local_iterator<_Iterator, _Sequence>&, 248 typename _Distance_traits<_Iterator>::__type&); 249 #endif 250 251 template<typename _InputIterator> 252 _GLIBCXX14_CONSTEXPR 253 inline bool 254 __valid_range(_InputIterator __first, _InputIterator __last) 255 { 256 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 257 return __valid_range_aux(__first, __last, _Integral()); 258 } 259 260 template<typename _Iterator, typename _Sequence, typename _Category> 261 bool 262 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 263 const _Safe_iterator<_Iterator, _Sequence, _Category>&); 264 265 #if __cplusplus >= 201103L 266 template<typename _Iterator, typename _Sequence> 267 bool 268 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&, 269 const _Safe_local_iterator<_Iterator, _Sequence>&); 270 #endif 271 272 // Fallback method, always ok. 273 template<typename _InputIterator, typename _Size> 274 _GLIBCXX_CONSTEXPR 275 inline bool 276 __can_advance(_InputIterator, _Size) 277 { return true; } 278 279 template<typename _Iterator, typename _Sequence, typename _Category, 280 typename _Size> 281 bool 282 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 283 _Size); 284 285 template<typename _InputIterator, typename _Diff> 286 _GLIBCXX_CONSTEXPR 287 inline bool 288 __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int) 289 { return true; } 290 291 template<typename _Iterator, typename _Sequence, typename _Category, 292 typename _Diff> 293 bool 294 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 295 const std::pair<_Diff, _Distance_precision>&, int); 296 297 /** Helper function to extract base iterator of random access safe iterator 298 * in order to reduce performance impact of debug mode. Limited to random 299 * access iterator because it is the only category for which it is possible 300 * to check for correct iterators order in the __valid_range function 301 * thanks to the < operator. 302 */ 303 template<typename _Iterator> 304 _GLIBCXX_CONSTEXPR 305 inline _Iterator 306 __base(_Iterator __it) 307 { return __it; } 308 309 #if __cplusplus < 201103L 310 template<typename _Iterator> 311 struct _Unsafe_type 312 { typedef _Iterator _Type; }; 313 #endif 314 315 /* Remove debug mode safe iterator layer, if any. */ 316 template<typename _Iterator> 317 inline _Iterator 318 __unsafe(_Iterator __it) 319 { return __it; } 320 } 321 322 #endif 323