libstdc++
functions.h
Go to the documentation of this file.
00001 // Debugging support implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2016 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/move.h>                          // for __addressof
00033 #include <bits/stl_function.h>                  // for less
00034 #if __cplusplus >= 201103L
00035 # include <type_traits>                         // for is_lvalue_reference and
00036                                                 // conditional.
00037 #endif
00038 
00039 #include <debug/helper_functions.h>
00040 #include <debug/formatter.h>
00041 
00042 namespace __gnu_debug
00043 {
00044   template<typename _Iterator, typename _Sequence>
00045     class _Safe_iterator;
00046 
00047   template<typename _Sequence>
00048     struct _Insert_range_from_self_is_safe
00049     { enum { __value = 0 }; };
00050 
00051   template<typename _Sequence>
00052     struct _Is_contiguous_sequence : std::__false_type { };
00053 
00054   // An arbitrary iterator pointer is not singular.
00055   inline bool
00056   __check_singular_aux(const void*) { return false; }
00057 
00058   // We may have an iterator that derives from _Safe_iterator_base but isn't
00059   // a _Safe_iterator.
00060   template<typename _Iterator>
00061     inline bool
00062     __check_singular(const _Iterator& __x)
00063     { return __check_singular_aux(std::__addressof(__x)); }
00064 
00065   /** Non-NULL pointers are nonsingular. */
00066   template<typename _Tp>
00067     inline bool
00068     __check_singular(const _Tp* __ptr)
00069     { return __ptr == 0; }
00070 
00071   /** Assume that some arbitrary iterator is dereferenceable, because we
00072       can't prove that it isn't. */
00073   template<typename _Iterator>
00074     inline bool
00075     __check_dereferenceable(const _Iterator&)
00076     { return true; }
00077 
00078   /** Non-NULL pointers are dereferenceable. */
00079   template<typename _Tp>
00080     inline bool
00081     __check_dereferenceable(const _Tp* __ptr)
00082     { return __ptr; }
00083 
00084   /* Checks that [first, last) is a valid range, and then returns
00085    * __first. This routine is useful when we can't use a separate
00086    * assertion statement because, e.g., we are in a constructor.
00087   */
00088   template<typename _InputIterator>
00089     inline _InputIterator
00090     __check_valid_range(const _InputIterator& __first,
00091                         const _InputIterator& __last
00092                         __attribute__((__unused__)))
00093     {
00094       __glibcxx_check_valid_range(__first, __last);
00095       return __first;
00096     }
00097 
00098   /* Handle the case where __other is a pointer to _Sequence::value_type. */
00099   template<typename _Iterator, typename _Sequence>
00100     inline bool
00101     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
00102                             const typename _Sequence::value_type* __other)
00103     {
00104       typedef const typename _Sequence::value_type* _PointerType;
00105       typedef std::less<_PointerType> _Less;
00106 #if __cplusplus >= 201103L
00107       constexpr _Less __l{};
00108 #else
00109       const _Less __l = _Less();
00110 #endif
00111       const _Sequence* __seq = __it._M_get_sequence();
00112       const _PointerType __begin = std::__addressof(*__seq->_M_base().begin());
00113       const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1));
00114 
00115       // Check whether __other points within the contiguous storage.
00116       return __l(__other, __begin) || __l(__end, __other);
00117     }
00118 
00119   /* Fallback overload for when we can't tell, assume it is valid. */
00120   template<typename _Iterator, typename _Sequence>
00121     inline bool
00122     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
00123     { return true; }
00124 
00125   /* Handle sequences with contiguous storage */
00126   template<typename _Iterator, typename _Sequence, typename _InputIterator>
00127     inline bool
00128     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
00129                             const _InputIterator& __other,
00130                             const _InputIterator& __other_end,
00131                             std::__true_type)
00132     {
00133       if (__other == __other_end)
00134         return true;  // inserting nothing is safe even if not foreign iters
00135       if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end())
00136         return true;  // can't be self-inserting if self is empty
00137       return __foreign_iterator_aux4(__it, std::__addressof(*__other));
00138     }
00139 
00140   /* Handle non-contiguous containers, assume it is valid. */
00141   template<typename _Iterator, typename _Sequence, typename _InputIterator>
00142     inline bool
00143     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
00144                             const _InputIterator&, const _InputIterator&,
00145                             std::__false_type)
00146     { return true; }
00147 
00148   /** Handle debug iterators from the same type of container. */
00149   template<typename _Iterator, typename _Sequence, typename _OtherIterator>
00150     inline bool
00151     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
00152                 const _Safe_iterator<_OtherIterator, _Sequence>& __other,
00153                 const _Safe_iterator<_OtherIterator, _Sequence>&)
00154     { return __it._M_get_sequence() != __other._M_get_sequence(); }
00155 
00156   /** Handle debug iterators from different types of container. */
00157   template<typename _Iterator, typename _Sequence, typename _OtherIterator,
00158            typename _OtherSequence>
00159     inline bool
00160     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
00161                 const _Safe_iterator<_OtherIterator, _OtherSequence>&,
00162                 const _Safe_iterator<_OtherIterator, _OtherSequence>&)
00163     { return true; }
00164 
00165   /* Handle non-debug iterators. */
00166   template<typename _Iterator, typename _Sequence, typename _InputIterator>
00167     inline bool
00168     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
00169                             const _InputIterator& __other,
00170                             const _InputIterator& __other_end)
00171     {
00172 #if __cplusplus < 201103L
00173       typedef _Is_contiguous_sequence<_Sequence> __tag;
00174 #else
00175       using __lvalref = std::is_lvalue_reference<
00176         typename std::iterator_traits<_InputIterator>::reference>;
00177       using __contiguous = _Is_contiguous_sequence<_Sequence>;
00178       using __tag = typename std::conditional<__lvalref::value, __contiguous,
00179                                               std::__false_type>::type;
00180 #endif
00181       return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
00182     }
00183 
00184   /* Handle the case where we aren't really inserting a range after all */
00185   template<typename _Iterator, typename _Sequence, typename _Integral>
00186     inline bool
00187     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
00188                            _Integral, _Integral,
00189                            std::__true_type)
00190     { return true; }
00191 
00192   /* Handle all iterators. */
00193   template<typename _Iterator, typename _Sequence,
00194            typename _InputIterator>
00195     inline bool
00196     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
00197                            _InputIterator __other, _InputIterator __other_end,
00198                            std::__false_type)
00199     {
00200       return _Insert_range_from_self_is_safe<_Sequence>::__value
00201         || __foreign_iterator_aux2(__it, std::__miter_base(__other),
00202                                    std::__miter_base(__other_end));
00203     }
00204 
00205   template<typename _Iterator, typename _Sequence,
00206            typename _InputIterator>
00207     inline bool
00208     __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
00209                        _InputIterator __other, _InputIterator __other_end)
00210     {
00211       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00212       return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
00213     }
00214 
00215   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
00216   template<typename _CharT, typename _Integer>
00217     inline const _CharT*
00218     __check_string(const _CharT* __s,
00219                    const _Integer& __n __attribute__((__unused__)))
00220     {
00221 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00222       __glibcxx_assert(__s != 0 || __n == 0);
00223 #endif
00224       return __s;
00225     }
00226 
00227   /** Checks that __s is non-NULL and then returns __s. */
00228   template<typename _CharT>
00229     inline const _CharT*
00230     __check_string(const _CharT* __s)
00231     {
00232 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00233       __glibcxx_assert(__s != 0);
00234 #endif
00235       return __s;
00236     }
00237 
00238   // Can't check if an input iterator sequence is sorted, because we
00239   // can't step through the sequence.
00240   template<typename _InputIterator>
00241     inline bool
00242     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00243                        std::input_iterator_tag)
00244     { return true; }
00245 
00246   // Can verify if a forward iterator sequence is in fact sorted using
00247   // std::__is_sorted
00248   template<typename _ForwardIterator>
00249     inline bool
00250     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00251                        std::forward_iterator_tag)
00252     {
00253       if (__first == __last)
00254         return true;
00255 
00256       _ForwardIterator __next = __first;
00257       for (++__next; __next != __last; __first = __next, (void)++__next)
00258         if (*__next < *__first)
00259           return false;
00260 
00261       return true;
00262     }
00263 
00264   // Can't check if an input iterator sequence is sorted, because we can't step
00265   // through the sequence.
00266   template<typename _InputIterator, typename _Predicate>
00267     inline bool
00268     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00269                        _Predicate, std::input_iterator_tag)
00270     { return true; }
00271 
00272   // Can verify if a forward iterator sequence is in fact sorted using
00273   // std::__is_sorted
00274   template<typename _ForwardIterator, typename _Predicate>
00275     inline bool
00276     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00277                        _Predicate __pred, std::forward_iterator_tag)
00278     {
00279       if (__first == __last)
00280         return true;
00281 
00282       _ForwardIterator __next = __first;
00283       for (++__next; __next != __last; __first = __next, (void)++__next)
00284         if (__pred(*__next, *__first))
00285           return false;
00286 
00287       return true;
00288     }
00289 
00290   // Determine if a sequence is sorted.
00291   template<typename _InputIterator>
00292     inline bool
00293     __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
00294     {
00295       // Verify that the < operator for elements in the sequence is a
00296       // StrictWeakOrdering by checking that it is irreflexive.
00297       __glibcxx_assert(__first == __last || !(*__first < *__first));
00298 
00299       return __check_sorted_aux(__first, __last,
00300                                 std::__iterator_category(__first));
00301     }
00302 
00303   template<typename _InputIterator, typename _Predicate>
00304     inline bool
00305     __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
00306                    _Predicate __pred)
00307     {
00308       // Verify that the predicate is StrictWeakOrdering by checking that it
00309       // is irreflexive.
00310       __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
00311 
00312       return __check_sorted_aux(__first, __last, __pred,
00313                                 std::__iterator_category(__first));
00314     }
00315 
00316   template<typename _InputIterator>
00317     inline bool
00318     __check_sorted_set_aux(const _InputIterator& __first,
00319                            const _InputIterator& __last,
00320                            std::__true_type)
00321     { return __check_sorted(__first, __last); }
00322 
00323   template<typename _InputIterator>
00324     inline bool
00325     __check_sorted_set_aux(const _InputIterator&,
00326                            const _InputIterator&,
00327                            std::__false_type)
00328     { return true; }
00329 
00330   template<typename _InputIterator, typename _Predicate>
00331     inline bool
00332     __check_sorted_set_aux(const _InputIterator& __first,
00333                            const _InputIterator& __last,
00334                            _Predicate __pred, std::__true_type)
00335     { return __check_sorted(__first, __last, __pred); }
00336 
00337   template<typename _InputIterator, typename _Predicate>
00338     inline bool
00339     __check_sorted_set_aux(const _InputIterator&,
00340                            const _InputIterator&, _Predicate,
00341                            std::__false_type)
00342     { return true; }
00343 
00344   // ... special variant used in std::merge, std::includes, std::set_*.
00345   template<typename _InputIterator1, typename _InputIterator2>
00346     inline bool
00347     __check_sorted_set(const _InputIterator1& __first,
00348                        const _InputIterator1& __last,
00349                        const _InputIterator2&)
00350     {
00351       typedef typename std::iterator_traits<_InputIterator1>::value_type
00352         _ValueType1;
00353       typedef typename std::iterator_traits<_InputIterator2>::value_type
00354         _ValueType2;
00355 
00356       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00357         _SameType;
00358       return __check_sorted_set_aux(__first, __last, _SameType());
00359     }
00360 
00361   template<typename _InputIterator1, typename _InputIterator2,
00362            typename _Predicate>
00363     inline bool
00364     __check_sorted_set(const _InputIterator1& __first,
00365                        const _InputIterator1& __last,
00366                        const _InputIterator2&, _Predicate __pred)
00367     {
00368       typedef typename std::iterator_traits<_InputIterator1>::value_type
00369         _ValueType1;
00370       typedef typename std::iterator_traits<_InputIterator2>::value_type
00371         _ValueType2;
00372 
00373       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00374         _SameType;
00375       return __check_sorted_set_aux(__first, __last, __pred, _SameType());
00376    }
00377 
00378   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00379   // 270. Binary search requirements overly strict
00380   // Determine if a sequence is partitioned w.r.t. this element.
00381   template<typename _ForwardIterator, typename _Tp>
00382     inline bool
00383     __check_partitioned_lower(_ForwardIterator __first,
00384                               _ForwardIterator __last, const _Tp& __value)
00385     {
00386       while (__first != __last && *__first < __value)
00387         ++__first;
00388       if (__first != __last)
00389         {
00390           ++__first;
00391           while (__first != __last && !(*__first < __value))
00392             ++__first;
00393         }
00394       return __first == __last;
00395     }
00396 
00397   template<typename _ForwardIterator, typename _Tp>
00398     inline bool
00399     __check_partitioned_upper(_ForwardIterator __first,
00400                               _ForwardIterator __last, const _Tp& __value)
00401     {
00402       while (__first != __last && !(__value < *__first))
00403         ++__first;
00404       if (__first != __last)
00405         {
00406           ++__first;
00407           while (__first != __last && __value < *__first)
00408             ++__first;
00409         }
00410       return __first == __last;
00411     }
00412 
00413   // Determine if a sequence is partitioned w.r.t. this element.
00414   template<typename _ForwardIterator, typename _Tp, typename _Pred>
00415     inline bool
00416     __check_partitioned_lower(_ForwardIterator __first,
00417                               _ForwardIterator __last, const _Tp& __value,
00418                               _Pred __pred)
00419     {
00420       while (__first != __last && bool(__pred(*__first, __value)))
00421         ++__first;
00422       if (__first != __last)
00423         {
00424           ++__first;
00425           while (__first != __last && !bool(__pred(*__first, __value)))
00426             ++__first;
00427         }
00428       return __first == __last;
00429     }
00430 
00431   template<typename _ForwardIterator, typename _Tp, typename _Pred>
00432     inline bool
00433     __check_partitioned_upper(_ForwardIterator __first,
00434                               _ForwardIterator __last, const _Tp& __value,
00435                               _Pred __pred)
00436     {
00437       while (__first != __last && !bool(__pred(__value, *__first)))
00438         ++__first;
00439       if (__first != __last)
00440         {
00441           ++__first;
00442           while (__first != __last && bool(__pred(__value, *__first)))
00443             ++__first;
00444         }
00445       return __first == __last;
00446     }
00447 
00448 #if __cplusplus >= 201103L
00449   struct _Irreflexive_checker
00450   {
00451     template<typename _It>
00452       static typename std::iterator_traits<_It>::reference
00453       __deref();
00454 
00455     template<typename _It,
00456              typename = decltype(__deref<_It>() < __deref<_It>())>
00457       static bool
00458       _S_is_valid(_It __it)
00459       { return !(*__it < *__it); }
00460 
00461     // Fallback method if operator doesn't exist.
00462     template<typename... _Args>
00463       static bool
00464       _S_is_valid(_Args...)
00465       { return true; }
00466 
00467     template<typename _It, typename _Pred, typename
00468         = decltype(std::declval<_Pred>()(__deref<_It>(), __deref<_It>()))>
00469       static bool
00470       _S_is_valid_pred(_It __it, _Pred __pred)
00471       { return !__pred(*__it, *__it); }
00472 
00473     // Fallback method if predicate can't be invoked.
00474     template<typename... _Args>
00475       static bool
00476       _S_is_valid_pred(_Args...)
00477       { return true; }
00478   };
00479 
00480   template<typename _Iterator>
00481     inline bool
00482     __is_irreflexive(_Iterator __it)
00483     { return _Irreflexive_checker::_S_is_valid(__it); }
00484 
00485   template<typename _Iterator, typename _Pred>
00486     inline bool
00487     __is_irreflexive_pred(_Iterator __it, _Pred __pred)
00488     { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); }
00489 #endif
00490 
00491 } // namespace __gnu_debug
00492 
00493 #endif