1 // Debugging support implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2019 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/stl_iterator_base_types.h> // for iterator_traits, 33 // categories and _Iter_base 34 #include <bits/cpp_type_traits.h> // for __is_integer 35 36 #include <bits/stl_pair.h> // for pair 37 38 namespace __gnu_debug 39 { 40 template<typename _Iterator, typename _Sequence, typename _Category> 41 class _Safe_iterator; 42 43 #if __cplusplus >= 201103L 44 template<typename _Iterator, typename _Sequence> 45 class _Safe_local_iterator; 46 #endif 47 48 /** The precision to which we can calculate the distance between 49 * two iterators. 50 */ 51 enum _Distance_precision 52 { 53 __dp_none, // Not even an iterator type 54 __dp_equality, //< Can compare iterator equality, only 55 __dp_sign, //< Can determine equality and ordering 56 __dp_exact //< Can determine distance precisely 57 }; 58 59 template<typename _Iterator, 60 typename = typename std::__is_integer<_Iterator>::__type> 61 struct _Distance_traits 62 { 63 private: 64 typedef 65 typename std::iterator_traits<_Iterator>::difference_type _ItDiffType; 66 67 template<typename _DiffType, 68 typename = typename std::__is_void<_DiffType>::__type> 69 struct _DiffTraits 70 { typedef _DiffType __type; }; 71 72 template<typename _DiffType> 73 struct _DiffTraits<_DiffType, std::__true_type> 74 { typedef std::ptrdiff_t __type; }; 75 76 typedef typename _DiffTraits<_ItDiffType>::__type _DiffType; 77 78 public: 79 typedef std::pair<_DiffType, _Distance_precision> __type; 80 }; 81 82 template<typename _Integral> 83 struct _Distance_traits<_Integral, std::__true_type> 84 { typedef std::pair<std::ptrdiff_t, _Distance_precision> __type; }; 85 86 /** Determine the distance between two iterators with some known 87 * precision. 88 */ 89 template<typename _Iterator> 90 inline typename _Distance_traits<_Iterator>::__type 91 __get_distance(_Iterator __lhs, _Iterator __rhs, 92 std::random_access_iterator_tag) 93 { return std::make_pair(__rhs - __lhs, __dp_exact); } 94 95 template<typename _Iterator> 96 inline typename _Distance_traits<_Iterator>::__type 97 __get_distance(_Iterator __lhs, _Iterator __rhs, 98 std::input_iterator_tag) 99 { 100 if (__lhs == __rhs) 101 return std::make_pair(0, __dp_exact); 102 103 return std::make_pair(1, __dp_equality); 104 } 105 106 template<typename _Iterator> 107 inline typename _Distance_traits<_Iterator>::__type 108 __get_distance(_Iterator __lhs, _Iterator __rhs) 109 { return __get_distance(__lhs, __rhs, std::__iterator_category(__lhs)); } 110 111 /** We say that integral types for a valid range, and defer to other 112 * routines to realize what to do with integral types instead of 113 * iterators. 114 */ 115 template<typename _Integral> 116 inline bool 117 __valid_range_aux(_Integral, _Integral, 118 typename _Distance_traits<_Integral>::__type& __dist, 119 std::__true_type) 120 { 121 __dist = std::make_pair(0, __dp_none); 122 return true; 123 } 124 125 /** We have iterators, so figure out what kind of iterators they are 126 * to see if we can check the range ahead of time. 127 */ 128 template<typename _InputIterator> 129 inline bool 130 __valid_range_aux(_InputIterator __first, _InputIterator __last, 131 typename _Distance_traits<_InputIterator>::__type& __dist, 132 std::__false_type) 133 { 134 __dist = __get_distance(__first, __last); 135 switch (__dist.second) 136 { 137 case __dp_none: 138 break; 139 case __dp_equality: 140 if (__dist.first == 0) 141 return true; 142 break; 143 case __dp_sign: 144 case __dp_exact: 145 return __dist.first >= 0; 146 } 147 148 // Can't tell so assume it is fine. 149 return true; 150 } 151 152 /** Don't know what these iterators are, or if they are even 153 * iterators (we may get an integral type for InputIterator), so 154 * see if they are integral and pass them on to the next phase 155 * otherwise. 156 */ 157 template<typename _InputIterator> 158 inline bool 159 __valid_range(_InputIterator __first, _InputIterator __last, 160 typename _Distance_traits<_InputIterator>::__type& __dist) 161 { 162 typedef typename std::__is_integer<_InputIterator>::__type _Integral; 163 return __valid_range_aux(__first, __last, __dist, _Integral()); 164 } 165 166 template<typename _Iterator, typename _Sequence, typename _Category> 167 bool 168 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 169 const _Safe_iterator<_Iterator, _Sequence, _Category>&, 170 typename _Distance_traits<_Iterator>::__type&); 171 172 #if __cplusplus >= 201103L 173 template<typename _Iterator,typename _Sequence> 174 bool 175 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&, 176 const _Safe_local_iterator<_Iterator, _Sequence>&, 177 typename _Distance_traits<_Iterator>::__type&); 178 #endif 179 180 template<typename _InputIterator> 181 inline bool 182 __valid_range(_InputIterator __first, _InputIterator __last) 183 { 184 typename _Distance_traits<_InputIterator>::__type __dist; 185 return __valid_range(__first, __last, __dist); 186 } 187 188 template<typename _Iterator, typename _Sequence, typename _Category> 189 bool 190 __valid_range(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 191 const _Safe_iterator<_Iterator, _Sequence, _Category>&); 192 193 #if __cplusplus >= 201103L 194 template<typename _Iterator, typename _Sequence> 195 bool 196 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>&, 197 const _Safe_local_iterator<_Iterator, _Sequence>&); 198 #endif 199 200 // Fallback method, always ok. 201 template<typename _InputIterator, typename _Size> 202 inline bool 203 __can_advance(_InputIterator, _Size) 204 { return true; } 205 206 template<typename _Iterator, typename _Sequence, typename _Category, 207 typename _Size> 208 bool 209 __can_advance(const _Safe_iterator<_Iterator, _Sequence, _Category>&, 210 _Size); 211 212 /** Helper function to extract base iterator of random access safe iterator 213 * in order to reduce performance impact of debug mode. Limited to random 214 * access iterator because it is the only category for which it is possible 215 * to check for correct iterators order in the __valid_range function 216 * thanks to the < operator. 217 */ 218 template<typename _Iterator> 219 inline _Iterator 220 __base(_Iterator __it) 221 { return __it; } 222 223 #if __cplusplus < 201103L 224 template<typename _Iterator> 225 struct _Unsafe_type 226 { typedef _Iterator _Type; }; 227 #endif 228 229 /* Remove debug mode safe iterator layer, if any. */ 230 template<typename _Iterator> 231 inline _Iterator 232 __unsafe(_Iterator __it) 233 { return __it; } 234 } 235 236 #endif 237