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

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