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