libstdc++
functions.h
Go to the documentation of this file.
00001 // Debugging support implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2014 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/functions.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
00030 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
00031 
00032 #include <bits/c++config.h>
00033 #include <bits/stl_iterator_base_types.h> // for iterator_traits, categories and
00034                       // _Iter_base
00035 #include <bits/cpp_type_traits.h>     // for __is_integer
00036 #include <bits/move.h>                    // for __addressof and addressof
00037 # include <bits/stl_function.h>       // for less
00038 #if __cplusplus >= 201103L
00039 # include <type_traits>           // for is_lvalue_reference and __and_
00040 #endif
00041 #include <debug/formatter.h>
00042 
00043 namespace __gnu_debug
00044 {
00045   template<typename _Iterator, typename _Sequence>
00046     class _Safe_iterator;
00047 
00048   template<typename _Iterator, typename _Sequence>
00049     class _Safe_local_iterator;
00050 
00051   template<typename _Sequence>
00052     struct _Insert_range_from_self_is_safe
00053     { enum { __value = 0 }; };
00054 
00055   template<typename _Sequence>
00056     struct _Is_contiguous_sequence : std::__false_type { };
00057 
00058   // An arbitrary iterator pointer is not singular.
00059   inline bool
00060   __check_singular_aux(const void*) { return false; }
00061 
00062   // We may have an iterator that derives from _Safe_iterator_base but isn't
00063   // a _Safe_iterator.
00064   template<typename _Iterator>
00065     inline bool
00066     __check_singular(const _Iterator& __x)
00067     { return __check_singular_aux(&__x); }
00068 
00069   /** Non-NULL pointers are nonsingular. */
00070   template<typename _Tp>
00071     inline bool
00072     __check_singular(const _Tp* __ptr)
00073     { return __ptr == 0; }
00074 
00075   /** Assume that some arbitrary iterator is dereferenceable, because we
00076       can't prove that it isn't. */
00077   template<typename _Iterator>
00078     inline bool
00079     __check_dereferenceable(const _Iterator&)
00080     { return true; }
00081 
00082   /** Non-NULL pointers are dereferenceable. */
00083   template<typename _Tp>
00084     inline bool
00085     __check_dereferenceable(const _Tp* __ptr)
00086     { return __ptr; }
00087 
00088   /** Safe iterators know if they are dereferenceable. */
00089   template<typename _Iterator, typename _Sequence>
00090     inline bool
00091     __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
00092     { return __x._M_dereferenceable(); }
00093 
00094   /** Safe local iterators know if they are dereferenceable. */
00095   template<typename _Iterator, typename _Sequence>
00096     inline bool
00097     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
00098                                _Sequence>& __x)
00099     { return __x._M_dereferenceable(); }
00100 
00101   /** If the distance between two random access iterators is
00102    *  nonnegative, assume the range is valid.
00103   */
00104   template<typename _RandomAccessIterator>
00105     inline bool
00106     __valid_range_aux2(const _RandomAccessIterator& __first,
00107                const _RandomAccessIterator& __last,
00108                std::random_access_iterator_tag)
00109     { return __last - __first >= 0; }
00110 
00111   /** Can't test for a valid range with input iterators, because
00112    *  iteration may be destructive. So we just assume that the range
00113    *  is valid.
00114   */
00115   template<typename _InputIterator>
00116     inline bool
00117     __valid_range_aux2(const _InputIterator&, const _InputIterator&,
00118                std::input_iterator_tag)
00119     { return true; }
00120 
00121   /** We say that integral types for a valid range, and defer to other
00122    *  routines to realize what to do with integral types instead of
00123    *  iterators.
00124   */
00125   template<typename _Integral>
00126     inline bool
00127     __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
00128     { return true; }
00129 
00130   /** We have iterators, so figure out what kind of iterators that are
00131    *  to see if we can check the range ahead of time.
00132   */
00133   template<typename _InputIterator>
00134     inline bool
00135     __valid_range_aux(const _InputIterator& __first,
00136               const _InputIterator& __last, std::__false_type)
00137     { return __valid_range_aux2(__first, __last,
00138                 std::__iterator_category(__first)); }
00139 
00140   /** Don't know what these iterators are, or if they are even
00141    *  iterators (we may get an integral type for InputIterator), so
00142    *  see if they are integral and pass them on to the next phase
00143    *  otherwise.
00144   */
00145   template<typename _InputIterator>
00146     inline bool
00147     __valid_range(const _InputIterator& __first, const _InputIterator& __last)
00148     {
00149       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00150       return __valid_range_aux(__first, __last, _Integral());
00151     }
00152 
00153   /** Safe iterators know how to check if they form a valid range. */
00154   template<typename _Iterator, typename _Sequence>
00155     inline bool
00156     __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
00157           const _Safe_iterator<_Iterator, _Sequence>& __last)
00158     { return __first._M_valid_range(__last); }
00159 
00160   /** Safe local iterators know how to check if they form a valid range. */
00161   template<typename _Iterator, typename _Sequence>
00162     inline bool
00163     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
00164           const _Safe_local_iterator<_Iterator, _Sequence>& __last)
00165     { return __first._M_valid_range(__last); }
00166 
00167   /* Checks that [first, last) is a valid range, and then returns
00168    * __first. This routine is useful when we can't use a separate
00169    * assertion statement because, e.g., we are in a constructor.
00170   */
00171   template<typename _InputIterator>
00172     inline _InputIterator
00173     __check_valid_range(const _InputIterator& __first,
00174             const _InputIterator& __last
00175             __attribute__((__unused__)))
00176     {
00177       __glibcxx_check_valid_range(__first, __last);
00178       return __first;
00179     }
00180 
00181   /* Handle the case where __other is a pointer to _Sequence::value_type. */
00182   template<typename _Iterator, typename _Sequence>
00183     inline bool
00184     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
00185                 const typename _Sequence::value_type* __other)
00186     {
00187       typedef const typename _Sequence::value_type* _PointerType;
00188       typedef std::less<_PointerType> _Less;
00189 #if __cplusplus >= 201103L
00190       constexpr _Less __l{};
00191 #else
00192       const _Less __l = _Less();
00193 #endif
00194       const _Sequence* __seq = __it._M_get_sequence();
00195       const _PointerType __begin = std::__addressof(*__seq->_M_base().begin());
00196       const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1));
00197 
00198       // Check whether __other points within the contiguous storage.
00199       return __l(__other, __begin) || __l(__end, __other);
00200     }
00201 
00202   /* Fallback overload for when we can't tell, assume it is valid. */
00203   template<typename _Iterator, typename _Sequence>
00204     inline bool
00205     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
00206     { return true; }
00207 
00208   /* Handle sequences with contiguous storage */
00209   template<typename _Iterator, typename _Sequence, typename _InputIterator>
00210     inline bool
00211     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
00212                 const _InputIterator& __other,
00213                 const _InputIterator& __other_end,
00214                 std::__true_type)
00215     {
00216       if (__other == __other_end)
00217     return true;  // inserting nothing is safe even if not foreign iters
00218       if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end())
00219     return true;  // can't be self-inserting if self is empty
00220       return __foreign_iterator_aux4(__it, std::__addressof(*__other));
00221     }
00222 
00223   /* Handle non-contiguous containers, assume it is valid. */
00224   template<typename _Iterator, typename _Sequence, typename _InputIterator>
00225     inline bool
00226     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
00227                 const _InputIterator&, const _InputIterator&,
00228                 std::__false_type)
00229     { return true; }
00230 
00231   /** Handle debug iterators from the same type of container. */
00232   template<typename _Iterator, typename _Sequence, typename _OtherIterator>
00233     inline bool
00234     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
00235         const _Safe_iterator<_OtherIterator, _Sequence>& __other,
00236         const _Safe_iterator<_OtherIterator, _Sequence>&)
00237     { return __it._M_get_sequence() != __other._M_get_sequence(); }
00238 
00239   /** Handle debug iterators from different types of container. */
00240   template<typename _Iterator, typename _Sequence, typename _OtherIterator,
00241        typename _OtherSequence>
00242     inline bool
00243     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
00244         const _Safe_iterator<_OtherIterator, _OtherSequence>&,
00245         const _Safe_iterator<_OtherIterator, _OtherSequence>&)
00246     { return true; }
00247 
00248   /* Handle non-debug iterators. */
00249   template<typename _Iterator, typename _Sequence, typename _InputIterator>
00250     inline bool
00251     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
00252                 const _InputIterator& __other,
00253                 const _InputIterator& __other_end)
00254     {
00255       return __foreign_iterator_aux3(__it, __other, __other_end,
00256                      _Is_contiguous_sequence<_Sequence>());
00257     }
00258 
00259   /* Handle the case where we aren't really inserting a range after all */
00260   template<typename _Iterator, typename _Sequence, typename _Integral>
00261     inline bool
00262     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
00263                _Integral, _Integral,
00264                std::__true_type)
00265     { return true; }
00266 
00267   /* Handle all iterators. */
00268   template<typename _Iterator, typename _Sequence,
00269        typename _InputIterator>
00270     inline bool
00271     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
00272                _InputIterator __other, _InputIterator __other_end,
00273                std::__false_type)
00274     {
00275       return _Insert_range_from_self_is_safe<_Sequence>::__value
00276          || __foreign_iterator_aux2(__it, __other, __other_end);
00277     }
00278 
00279   template<typename _Iterator, typename _Sequence,
00280        typename _InputIterator>
00281     inline bool
00282     __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
00283                _InputIterator __other, _InputIterator __other_end)
00284     {
00285       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00286       return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
00287     }
00288 
00289   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
00290   template<typename _CharT, typename _Integer>
00291     inline const _CharT*
00292     __check_string(const _CharT* __s,
00293            const _Integer& __n __attribute__((__unused__)))
00294     {
00295 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00296       __glibcxx_assert(__s != 0 || __n == 0);
00297 #endif
00298       return __s;
00299     }
00300 
00301   /** Checks that __s is non-NULL and then returns __s. */
00302   template<typename _CharT>
00303     inline const _CharT*
00304     __check_string(const _CharT* __s)
00305     {
00306 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00307       __glibcxx_assert(__s != 0);
00308 #endif
00309       return __s;
00310     }
00311 
00312   // Can't check if an input iterator sequence is sorted, because we
00313   // can't step through the sequence.
00314   template<typename _InputIterator>
00315     inline bool
00316     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00317                        std::input_iterator_tag)
00318     { return true; }
00319 
00320   // Can verify if a forward iterator sequence is in fact sorted using
00321   // std::__is_sorted
00322   template<typename _ForwardIterator>
00323     inline bool
00324     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00325                        std::forward_iterator_tag)
00326     {
00327       if (__first == __last)
00328         return true;
00329 
00330       _ForwardIterator __next = __first;
00331       for (++__next; __next != __last; __first = __next, ++__next)
00332         if (*__next < *__first)
00333           return false;
00334 
00335       return true;
00336     }
00337 
00338   // Can't check if an input iterator sequence is sorted, because we can't step
00339   // through the sequence.
00340   template<typename _InputIterator, typename _Predicate>
00341     inline bool
00342     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00343                        _Predicate, std::input_iterator_tag)
00344     { return true; }
00345 
00346   // Can verify if a forward iterator sequence is in fact sorted using
00347   // std::__is_sorted
00348   template<typename _ForwardIterator, typename _Predicate>
00349     inline bool
00350     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00351                        _Predicate __pred, std::forward_iterator_tag)
00352     {
00353       if (__first == __last)
00354         return true;
00355 
00356       _ForwardIterator __next = __first;
00357       for (++__next; __next != __last; __first = __next, ++__next)
00358         if (__pred(*__next, *__first))
00359           return false;
00360 
00361       return true;
00362     }
00363 
00364   // Determine if a sequence is sorted.
00365   template<typename _InputIterator>
00366     inline bool
00367     __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
00368     {
00369       // Verify that the < operator for elements in the sequence is a
00370       // StrictWeakOrdering by checking that it is irreflexive.
00371       __glibcxx_assert(__first == __last || !(*__first < *__first));
00372 
00373       return __check_sorted_aux(__first, __last,
00374                 std::__iterator_category(__first));
00375     }
00376 
00377   template<typename _InputIterator, typename _Predicate>
00378     inline bool
00379     __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
00380                    _Predicate __pred)
00381     {
00382       // Verify that the predicate is StrictWeakOrdering by checking that it
00383       // is irreflexive.
00384       __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
00385 
00386       return __check_sorted_aux(__first, __last, __pred,
00387                 std::__iterator_category(__first));
00388     }
00389 
00390   template<typename _InputIterator>
00391     inline bool
00392     __check_sorted_set_aux(const _InputIterator& __first,
00393                const _InputIterator& __last,
00394                std::__true_type)
00395     { return __check_sorted(__first, __last); }
00396 
00397   template<typename _InputIterator>
00398     inline bool
00399     __check_sorted_set_aux(const _InputIterator&,
00400                const _InputIterator&,
00401                std::__false_type)
00402     { return true; }
00403 
00404   template<typename _InputIterator, typename _Predicate>
00405     inline bool
00406     __check_sorted_set_aux(const _InputIterator& __first,
00407                const _InputIterator& __last,
00408                _Predicate __pred, std::__true_type)
00409     { return __check_sorted(__first, __last, __pred); }
00410 
00411   template<typename _InputIterator, typename _Predicate>
00412     inline bool
00413     __check_sorted_set_aux(const _InputIterator&,
00414                const _InputIterator&, _Predicate,
00415                std::__false_type)
00416     { return true; }
00417 
00418   // ... special variant used in std::merge, std::includes, std::set_*.
00419   template<typename _InputIterator1, typename _InputIterator2>
00420     inline bool
00421     __check_sorted_set(const _InputIterator1& __first,
00422                const _InputIterator1& __last,
00423                const _InputIterator2&)
00424     {
00425       typedef typename std::iterator_traits<_InputIterator1>::value_type
00426     _ValueType1;
00427       typedef typename std::iterator_traits<_InputIterator2>::value_type
00428     _ValueType2;
00429 
00430       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00431     _SameType;
00432       return __check_sorted_set_aux(__first, __last, _SameType());
00433     }
00434 
00435   template<typename _InputIterator1, typename _InputIterator2,
00436        typename _Predicate>
00437     inline bool
00438     __check_sorted_set(const _InputIterator1& __first,
00439                const _InputIterator1& __last,
00440                const _InputIterator2&, _Predicate __pred)
00441     {
00442       typedef typename std::iterator_traits<_InputIterator1>::value_type
00443     _ValueType1;
00444       typedef typename std::iterator_traits<_InputIterator2>::value_type
00445     _ValueType2;
00446 
00447       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00448     _SameType;
00449       return __check_sorted_set_aux(__first, __last, __pred, _SameType());
00450    }
00451 
00452   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00453   // 270. Binary search requirements overly strict
00454   // Determine if a sequence is partitioned w.r.t. this element.
00455   template<typename _ForwardIterator, typename _Tp>
00456     inline bool
00457     __check_partitioned_lower(_ForwardIterator __first,
00458                   _ForwardIterator __last, const _Tp& __value)
00459     {
00460       while (__first != __last && *__first < __value)
00461     ++__first;
00462       if (__first != __last)
00463     {
00464       ++__first;
00465       while (__first != __last && !(*__first < __value))
00466         ++__first;
00467     }
00468       return __first == __last;
00469     }
00470 
00471   template<typename _ForwardIterator, typename _Tp>
00472     inline bool
00473     __check_partitioned_upper(_ForwardIterator __first,
00474                   _ForwardIterator __last, const _Tp& __value)
00475     {
00476       while (__first != __last && !(__value < *__first))
00477     ++__first;
00478       if (__first != __last)
00479     {
00480       ++__first;
00481       while (__first != __last && __value < *__first)
00482         ++__first;
00483     }
00484       return __first == __last;
00485     }
00486 
00487   // Determine if a sequence is partitioned w.r.t. this element.
00488   template<typename _ForwardIterator, typename _Tp, typename _Pred>
00489     inline bool
00490     __check_partitioned_lower(_ForwardIterator __first,
00491                   _ForwardIterator __last, const _Tp& __value,
00492                   _Pred __pred)
00493     {
00494       while (__first != __last && bool(__pred(*__first, __value)))
00495     ++__first;
00496       if (__first != __last)
00497     {
00498       ++__first;
00499       while (__first != __last && !bool(__pred(*__first, __value)))
00500         ++__first;
00501     }
00502       return __first == __last;
00503     }
00504 
00505   template<typename _ForwardIterator, typename _Tp, typename _Pred>
00506     inline bool
00507     __check_partitioned_upper(_ForwardIterator __first,
00508                   _ForwardIterator __last, const _Tp& __value,
00509                   _Pred __pred)
00510     {
00511       while (__first != __last && !bool(__pred(__value, *__first)))
00512     ++__first;
00513       if (__first != __last)
00514     {
00515       ++__first;
00516       while (__first != __last && bool(__pred(__value, *__first)))
00517         ++__first;
00518     }
00519       return __first == __last;
00520     }
00521 
00522   // Helper struct to detect random access safe iterators.
00523   template<typename _Iterator>
00524     struct __is_safe_random_iterator
00525     {
00526       enum { __value = 0 };
00527       typedef std::__false_type __type;
00528     };
00529 
00530   template<typename _Iterator, typename _Sequence>
00531     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
00532     : std::__are_same<std::random_access_iterator_tag,
00533                       typename std::iterator_traits<_Iterator>::
00534               iterator_category>
00535     { };
00536 
00537   template<typename _Iterator>
00538     struct _Siter_base
00539     : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
00540     { };
00541 
00542   /** Helper function to extract base iterator of random access safe iterator
00543       in order to reduce performance impact of debug mode.  Limited to random
00544       access iterator because it is the only category for which it is possible
00545       to check for correct iterators order in the __valid_range function
00546       thanks to the < operator.
00547   */
00548   template<typename _Iterator>
00549     inline typename _Siter_base<_Iterator>::iterator_type
00550     __base(_Iterator __it)
00551     { return _Siter_base<_Iterator>::_S_base(__it); }
00552 } // namespace __gnu_debug
00553 
00554 #endif