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