| 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
|
|---|
