1 // Debugging support implementation -*- C++ -*-
2
3 // Copyright (C) 2003-2023 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 {
115 return __gnu_debug::__get_distance(__lhs, __rhs,
116 std::__iterator_category(__lhs));
117 }
118
119 // An arbitrary iterator pointer is not singular.
120 inline bool
121 __check_singular_aux(const void*) { return false; }
122
123 // Defined in <debug/safe_base.h>
124 bool
125 __check_singular_aux(const class _Safe_iterator_base*);
126
127 // We may have an iterator that derives from _Safe_iterator_base but isn't
128 // a _Safe_iterator.
129 template<typename _Iterator>
130 _GLIBCXX_CONSTEXPR
131 inline bool
132 __check_singular(_Iterator const& __x)
133 {
134 return ! std::__is_constant_evaluated()
135 && __gnu_debug::__check_singular_aux(std::__addressof(__x));
136 }
137
138 /** Non-NULL pointers are nonsingular. */
139 template<typename _Tp>
140 _GLIBCXX_CONSTEXPR
141 inline bool
142 __check_singular(_Tp* const& __ptr)
143 { return __ptr == 0; }
144
145 /** We say that integral types for a valid range, and defer to other
146 * routines to realize what to do with integral types instead of
147 * iterators.
148 */
149 template<typename _Integral>
150 _GLIBCXX_CONSTEXPR
151 inline bool
152 __valid_range_aux(_Integral, _Integral, std::__true_type)
153 { return true; }
154
155 template<typename _Integral>
156 _GLIBCXX20_CONSTEXPR
157 inline bool
158 __valid_range_aux(_Integral, _Integral,
159 typename _Distance_traits<_Integral>::__type& __dist,
160 std::__true_type)
161 {
162 __dist = std::make_pair(0, __dp_none);
163 return true;
164 }
165
166 template<typename _InputIterator>
167 _GLIBCXX_CONSTEXPR
168 inline bool
169 __valid_range_aux(_InputIterator __first, _InputIterator __last,
170 std::input_iterator_tag)
171 {
172 return __first == __last
173 || (!__gnu_debug::__check_singular(__first)
174 && !__gnu_debug::__check_singular(__last));
175 }
176
177 template<typename _InputIterator>
178 _GLIBCXX_CONSTEXPR
179 inline bool
180 __valid_range_aux(_InputIterator __first, _InputIterator __last,
181 std::random_access_iterator_tag)
182 {
183 return __gnu_debug::__valid_range_aux(__first, __last,
184 std::input_iterator_tag())
185 && __first <= __last;
186 }
187
188 /** We have iterators, so figure out what kind of iterators they are
189 * to see if we can check the range ahead of time.
190 */
191 template<typename _InputIterator>
192 _GLIBCXX_CONSTEXPR
193 inline bool
194 __valid_range_aux(_InputIterator __first, _InputIterator __last,
195 std::__false_type)
196 {
197 return __gnu_debug::__valid_range_aux(__first, __last,
198 std::__iterator_category(__first));
199 }
200
201 template<typename _InputIterator>
202 _GLIBCXX20_CONSTEXPR
203 inline bool
204 __valid_range_aux(_InputIterator __first, _InputIterator __last,
205 typename _Distance_traits<_InputIterator>::__type& __dist,
206 std::__false_type)
207 {
208 if (!__gnu_debug::__valid_range_aux(__first, __last,
209 std::input_iterator_tag()))
210 return false;
211
212 __dist = __gnu_debug::__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 __gnu_debug::__valid_range_aux(__first, __last, __dist,
244 _Integral());
245 }
246
247 template<typename _Iterator, typename _Sequence, typename _Category>
248 bool
249 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
250 const _Safe_iterator<_Iterator, _Sequence, _Category>&,
251 typename _Distance_traits<_Iterator>::__type&);
252
253 #if __cplusplus >= 201103L
254 template<typename _Iterator,typename _Sequence>
255 bool
256 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
257 const _Safe_local_iterator<_Iterator, _Sequence>&,
258 typename _Distance_traits<_Iterator>::__type&);
259 #endif
260
261 template<typename _InputIterator>
262 _GLIBCXX14_CONSTEXPR
263 inline bool
264 __valid_range(_InputIterator __first, _InputIterator __last)
265 {
266 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
267 return __gnu_debug::__valid_range_aux(__first, __last, _Integral());
268 }
269
270 template<typename _Iterator, typename _Sequence, typename _Category>
271 bool
272 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
273 const _Safe_iterator<_Iterator, _Sequence, _Category>&);
274
275 #if __cplusplus >= 201103L
276 template<typename _Iterator, typename _Sequence>
277 bool
278 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
279 const _Safe_local_iterator<_Iterator, _Sequence>&);
280 #endif
281
282 // Fallback method, always ok.
283 template<typename _InputIterator, typename _Size>
284 _GLIBCXX_CONSTEXPR
285 inline bool
286 __can_advance(_InputIterator, _Size)
287 { return true; }
288
289 template<typename _Iterator, typename _Sequence, typename _Category,
290 typename _Size>
291 bool
292 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
293 _Size);
294
295 template<typename _InputIterator, typename _Diff>
296 _GLIBCXX_CONSTEXPR
297 inline bool
298 __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int)
299 { return true; }
300
301 template<typename _Iterator, typename _Sequence, typename _Category,
302 typename _Diff>
303 bool
304 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
305 const std::pair<_Diff, _Distance_precision>&, int);
306
307 /** Helper function to extract base iterator of random access safe iterator
308 * in order to reduce performance impact of debug mode. Limited to random
309 * access iterator because it is the only category for which it is possible
310 * to check for correct iterators order in the __valid_range function
311 * thanks to the < operator.
312 */
313 template<typename _Iterator>
314 _GLIBCXX_CONSTEXPR
315 inline _Iterator
316 __base(_Iterator __it)
317 { return __it; }
318
319 #if __cplusplus < 201103L
320 template<typename _Iterator>
321 struct _Unsafe_type
322 { typedef _Iterator _Type; };
323 #endif
324
325 /* Remove debug mode safe iterator layer, if any. */
326 template<typename _Iterator>
327 inline _Iterator
328 __unsafe(_Iterator __it)
329 { return __it; }
330 }
331
332 #endif