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