libstdc++-v3/include/debug/helper_functions.h

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