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

   1 // Debugging support implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2022 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 ! std::__is_constant_evaluated()
 128                && __check_singular_aux(std::__addressof(__x));
 129     }
 130
 131   /** Non-NULL pointers are nonsingular. */
 132   template<typename _Tp>
 133     _GLIBCXX_CONSTEXPR
 134     inline bool
 135     __check_singular(_Tp* const& __ptr)
 136     { return __ptr == 0; }
 137
 138   /** We say that integral types for a valid range, and defer to other
 139    *  routines to realize what to do with integral types instead of
 140    *  iterators.
 141   */
 142   template<typename _Integral>
 143     _GLIBCXX_CONSTEXPR
 144     inline bool
 145     __valid_range_aux(_Integral, _Integral, std::__true_type)
 146     { return true; }
 147
 148   template<typename _Integral>
 149     _GLIBCXX20_CONSTEXPR
 150     inline bool
 151     __valid_range_aux(_Integral, _Integral,
 152                       typename _Distance_traits<_Integral>::__type& __dist,
 153                       std::__true_type)
 154     {
 155       __dist = std::make_pair(0, __dp_none);
 156       return true;
 157     }
 158
 159   template<typename _InputIterator>
 160     _GLIBCXX_CONSTEXPR
 161     inline bool
 162     __valid_range_aux(_InputIterator __first, _InputIterator __last,
 163                       std::input_iterator_tag)
 164     {
 165       return __first == __last
 166         || (!__check_singular(__first) && !__check_singular(__last));
 167     }
 168
 169   template<typename _InputIterator>
 170     _GLIBCXX_CONSTEXPR
 171     inline bool
 172     __valid_range_aux(_InputIterator __first, _InputIterator __last,
 173                       std::random_access_iterator_tag)
 174     {
 175       return
 176         __valid_range_aux(__first, __last, std::input_iterator_tag())
 177         && __first <= __last;
 178     }
 179
 180   /** We have iterators, so figure out what kind of iterators they are
 181    *  to see if we can check the range ahead of time.
 182   */
 183   template<typename _InputIterator>
 184     _GLIBCXX_CONSTEXPR
 185     inline bool
 186     __valid_range_aux(_InputIterator __first, _InputIterator __last,
 187                       std::__false_type)
 188     {
 189       return __valid_range_aux(__first, __last,
 190                                std::__iterator_category(__first));
 191     }
 192
 193   template<typename _InputIterator>
 194     _GLIBCXX20_CONSTEXPR
 195     inline bool
 196     __valid_range_aux(_InputIterator __first, _InputIterator __last,
 197                       typename _Distance_traits<_InputIterator>::__type& __dist,
 198                       std::__false_type)
 199     {
 200       if (!__valid_range_aux(__first, __last, std::input_iterator_tag()))
 201         return false;
 202
 203       __dist = __get_distance(__first, __last);
 204       switch (__dist.second)
 205         {
 206         case __dp_none:
 207           break;
 208         case __dp_equality:
 209           if (__dist.first == 0)
 210             return true;
 211           break;
 212         case __dp_sign:
 213         case __dp_sign_max_size:
 214         case __dp_exact:
 215           return __dist.first >= 0;
 216         }
 217
 218       // Can't tell so assume it is fine.
 219       return true;
 220     }
 221
 222   /** Don't know what these iterators are, or if they are even
 223    *  iterators (we may get an integral type for InputIterator), so
 224    *  see if they are integral and pass them on to the next phase
 225    *  otherwise.
 226   */
 227   template<typename _InputIterator>
 228     _GLIBCXX20_CONSTEXPR
 229     inline bool
 230     __valid_range(_InputIterator __first, _InputIterator __last,
 231                   typename _Distance_traits<_InputIterator>::__type& __dist)
 232     {
 233       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 234       return __valid_range_aux(__first, __last, __dist, _Integral());
 235     }
 236
 237   template<typename _Iterator, typename _Sequence, typename _Category>
 238     bool
 239     __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
 240                   const _Safe_iterator<_Iterator, _Sequence, _Category>&,
 241                   typename _Distance_traits<_Iterator>::__type&);
 242
 243 #if __cplusplus >= 201103L
 244   template<typename _Iterator,typename _Sequence>
 245     bool
 246     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
 247                   const _Safe_local_iterator<_Iterator, _Sequence>&,
 248                   typename _Distance_traits<_Iterator>::__type&);
 249 #endif
 250
 251   template<typename _InputIterator>
 252     _GLIBCXX14_CONSTEXPR
 253     inline bool
 254     __valid_range(_InputIterator __first, _InputIterator __last)
 255     {
 256       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 257       return __valid_range_aux(__first, __last, _Integral());
 258     }
 259
 260   template<typename _Iterator, typename _Sequence, typename _Category>
 261     bool
 262     __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
 263                   const _Safe_iterator<_Iterator, _Sequence, _Category>&);
 264
 265 #if __cplusplus >= 201103L
 266   template<typename _Iterator, typename _Sequence>
 267     bool
 268     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&,
 269                   const _Safe_local_iterator<_Iterator, _Sequence>&);
 270 #endif
 271
 272   // Fallback method, always ok.
 273   template<typename _InputIterator, typename _Size>
 274     _GLIBCXX_CONSTEXPR
 275     inline bool
 276     __can_advance(_InputIterator, _Size)
 277     { return true; }
 278
 279   template<typename _Iterator, typename _Sequence, typename _Category,
 280            typename _Size>
 281     bool
 282     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
 283                   _Size);
 284
 285   template<typename _InputIterator, typename _Diff>
 286     _GLIBCXX_CONSTEXPR
 287     inline bool
 288     __can_advance(_InputIterator, const std::pair<_Diff, _Distance_precision>&, int)
 289     { return true; }
 290
 291   template<typename _Iterator, typename _Sequence, typename _Category,
 292            typename _Diff>
 293     bool
 294     __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&,
 295                   const std::pair<_Diff, _Distance_precision>&, int);
 296
 297   /** Helper function to extract base iterator of random access safe iterator
 298    *  in order to reduce performance impact of debug mode.  Limited to random
 299    *  access iterator because it is the only category for which it is possible
 300    *  to check for correct iterators order in the __valid_range function
 301    *  thanks to the < operator.
 302    */
 303   template<typename _Iterator>
 304     _GLIBCXX_CONSTEXPR
 305     inline _Iterator
 306     __base(_Iterator __it)
 307     { return __it; }
 308
 309 #if __cplusplus < 201103L
 310   template<typename _Iterator>
 311     struct _Unsafe_type
 312     { typedef _Iterator _Type; };
 313 #endif
 314
 315   /* Remove debug mode safe iterator layer, if any. */
 316   template<typename _Iterator>
 317     inline _Iterator
 318     __unsafe(_Iterator __it)
 319     { return __it; }
 320 }
 321
 322 #endif