libstdc++
helper_functions.h
Go to the documentation of this file.
1 // Debugging support implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2024 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  */
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
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:
82  };
83 
84  template<typename _Integral>
85  struct _Distance_traits<_Integral, std::__true_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,
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,
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,
171  {
172  // FIXME: The checks for singular iterators fail during constant eval
173  // due to PR c++/85944. e.g. PR libstdc++/109517 and PR libstdc++/109976.
174  if (std::__is_constant_evaluated())
175  return true;
176 
177  return __first == __last
178  || (!__gnu_debug::__check_singular(__first)
179  && !__gnu_debug::__check_singular(__last));
180  }
181 
182  template<typename _InputIterator>
183  _GLIBCXX_CONSTEXPR
184  inline bool
185  __valid_range_aux(_InputIterator __first, _InputIterator __last,
187  {
188  return __gnu_debug::__valid_range_aux(__first, __last,
190  && __first <= __last;
191  }
192 
193  /** We have iterators, so figure out what kind of iterators they are
194  * to see if we can check the range ahead of time.
195  */
196  template<typename _InputIterator>
197  _GLIBCXX_CONSTEXPR
198  inline bool
199  __valid_range_aux(_InputIterator __first, _InputIterator __last,
200  std::__false_type)
201  {
202  return __gnu_debug::__valid_range_aux(__first, __last,
203  std::__iterator_category(__first));
204  }
205 
206  template<typename _InputIterator>
207  _GLIBCXX20_CONSTEXPR
208  inline bool
209  __valid_range_aux(_InputIterator __first, _InputIterator __last,
210  typename _Distance_traits<_InputIterator>::__type& __dist,
211  std::__false_type)
212  {
213  if (!__gnu_debug::__valid_range_aux(__first, __last,
215  return false;
216 
217  __dist = __gnu_debug::__get_distance(__first, __last);
218  switch (__dist.second)
219  {
220  case __dp_none:
221  break;
222  case __dp_equality:
223  if (__dist.first == 0)
224  return true;
225  break;
226  case __dp_sign:
227  case __dp_sign_max_size:
228  case __dp_exact:
229  return __dist.first >= 0;
230  }
231 
232  // Can't tell so assume it is fine.
233  return true;
234  }
235 
236  /** Don't know what these iterators are, or if they are even
237  * iterators (we may get an integral type for InputIterator), so
238  * see if they are integral and pass them on to the next phase
239  * otherwise.
240  */
241  template<typename _InputIterator>
242  _GLIBCXX20_CONSTEXPR
243  inline bool
244  __valid_range(_InputIterator __first, _InputIterator __last,
246  {
247  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
248  return __gnu_debug::__valid_range_aux(__first, __last, __dist,
249  _Integral());
250  }
251 
252  template<typename _Iterator, typename _Sequence, typename _Category>
253  bool
254  __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
255  const _Safe_iterator<_Iterator, _Sequence, _Category>&,
256  typename _Distance_traits<_Iterator>::__type&);
257 
258 #if __cplusplus >= 201103L
259  template<typename _Iterator,typename _Sequence>
260  bool
261  __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
262  const _Safe_local_iterator<_Iterator, _Sequence>&,
263  typename _Distance_traits<_Iterator>::__type&);
264 #endif
265 
266  template<typename _InputIterator>
267  _GLIBCXX14_CONSTEXPR
268  inline bool
269  __valid_range(_InputIterator __first, _InputIterator __last)
270  {
271  typedef typename std::__is_integer<_InputIterator>::__type _Integral;
272  return __gnu_debug::__valid_range_aux(__first, __last, _Integral());
273  }
274 
275  template<typename _Iterator, typename _Sequence, typename _Category>
276  bool
277  __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
278  const _Safe_iterator<_Iterator, _Sequence, _Category>&);
279 
280 #if __cplusplus >= 201103L
281  template<typename _Iterator, typename _Sequence>
282  bool
283  __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
284  const _Safe_local_iterator<_Iterator, _Sequence>&);
285 #endif
286 
287  // Fallback method, always ok.
288  template<typename _InputIterator, typename _Size>
289  _GLIBCXX_CONSTEXPR
290  inline bool
291  __can_advance(_InputIterator, _Size)
292  { return true; }
293 
294  template<typename _Iterator, typename _Sequence, typename _Category,
295  typename _Size>
296  bool
297  __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
298  _Size);
299 
300  template<typename _InputIterator, typename _Diff>
301  _GLIBCXX_CONSTEXPR
302  inline bool
303  __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int)
304  { return true; }
305 
306  template<typename _Iterator, typename _Sequence, typename _Category,
307  typename _Diff>
308  bool
309  __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
311 
312  /** Helper function to extract base iterator of random access safe iterator
313  * in order to reduce performance impact of debug mode. Limited to random
314  * access iterator because it is the only category for which it is possible
315  * to check for correct iterators order in the __valid_range function
316  * thanks to the < operator.
317  */
318  template<typename _Iterator>
319  _GLIBCXX_CONSTEXPR
320  inline _Iterator
321  __base(_Iterator __it)
322  { return __it; }
323 
324 #if __cplusplus < 201103L
325  template<typename _Iterator>
326  struct _Unsafe_type
327  { typedef _Iterator _Type; };
328 #endif
329 
330  /* Remove debug mode safe iterator layer, if any. */
331  template<typename _Iterator>
332  _GLIBCXX_CONSTEXPR
333  inline _Iterator
334  __unsafe(_Iterator __it)
335  { return __it; }
336 }
337 
338 #endif
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition: move.h:51
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
GNU debug classes for public use.
constexpr _Distance_traits< _Iterator >::__type __get_distance(_Iterator __lhs, _Iterator __rhs, std::random_access_iterator_tag)
constexpr bool __valid_range_aux(_Integral, _Integral, std::__true_type)
constexpr bool __valid_range(_InputIterator __first, _InputIterator __last, typename _Distance_traits< _InputIterator >::__type &__dist)
constexpr _Iterator __base(_Iterator __it)
Traits class for iterators.
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:286
Marking input iterators.
Random-access iterators support a superset of bidirectional iterator operations.