libstdc++
functions.h
Go to the documentation of this file.
00001 // Debugging support implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2015 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 #if __cplusplus < 201103L
00256       typedef _Is_contiguous_sequence<_Sequence> __tag;
00257 #else
00258       using __lvalref = std::is_lvalue_reference<
00259         typename std::iterator_traits<_InputIterator>::reference>;
00260       using __contiguous = _Is_contiguous_sequence<_Sequence>;
00261       using __tag = typename std::conditional<__lvalref::value, __contiguous,
00262                                               std::__false_type>::type;
00263 #endif
00264       return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
00265     }
00266 
00267   /* Handle the case where we aren't really inserting a range after all */
00268   template<typename _Iterator, typename _Sequence, typename _Integral>
00269     inline bool
00270     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
00271                            _Integral, _Integral,
00272                            std::__true_type)
00273     { return true; }
00274 
00275   /* Handle all iterators. */
00276   template<typename _Iterator, typename _Sequence,
00277            typename _InputIterator>
00278     inline bool
00279     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
00280                            _InputIterator __other, _InputIterator __other_end,
00281                            std::__false_type)
00282     {
00283       return _Insert_range_from_self_is_safe<_Sequence>::__value
00284              || __foreign_iterator_aux2(__it, __other, __other_end);
00285     }
00286 
00287   template<typename _Iterator, typename _Sequence,
00288            typename _InputIterator>
00289     inline bool
00290     __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
00291                        _InputIterator __other, _InputIterator __other_end)
00292     {
00293       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
00294       return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
00295     }
00296 
00297   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
00298   template<typename _CharT, typename _Integer>
00299     inline const _CharT*
00300     __check_string(const _CharT* __s,
00301                    const _Integer& __n __attribute__((__unused__)))
00302     {
00303 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00304       __glibcxx_assert(__s != 0 || __n == 0);
00305 #endif
00306       return __s;
00307     }
00308 
00309   /** Checks that __s is non-NULL and then returns __s. */
00310   template<typename _CharT>
00311     inline const _CharT*
00312     __check_string(const _CharT* __s)
00313     {
00314 #ifdef _GLIBCXX_DEBUG_PEDANTIC
00315       __glibcxx_assert(__s != 0);
00316 #endif
00317       return __s;
00318     }
00319 
00320   // Can't check if an input iterator sequence is sorted, because we
00321   // can't step through the sequence.
00322   template<typename _InputIterator>
00323     inline bool
00324     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00325                        std::input_iterator_tag)
00326     { return true; }
00327 
00328   // Can verify if a forward iterator sequence is in fact sorted using
00329   // std::__is_sorted
00330   template<typename _ForwardIterator>
00331     inline bool
00332     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00333                        std::forward_iterator_tag)
00334     {
00335       if (__first == __last)
00336         return true;
00337 
00338       _ForwardIterator __next = __first;
00339       for (++__next; __next != __last; __first = __next, ++__next)
00340         if (*__next < *__first)
00341           return false;
00342 
00343       return true;
00344     }
00345 
00346   // Can't check if an input iterator sequence is sorted, because we can't step
00347   // through the sequence.
00348   template<typename _InputIterator, typename _Predicate>
00349     inline bool
00350     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
00351                        _Predicate, std::input_iterator_tag)
00352     { return true; }
00353 
00354   // Can verify if a forward iterator sequence is in fact sorted using
00355   // std::__is_sorted
00356   template<typename _ForwardIterator, typename _Predicate>
00357     inline bool
00358     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
00359                        _Predicate __pred, std::forward_iterator_tag)
00360     {
00361       if (__first == __last)
00362         return true;
00363 
00364       _ForwardIterator __next = __first;
00365       for (++__next; __next != __last; __first = __next, ++__next)
00366         if (__pred(*__next, *__first))
00367           return false;
00368 
00369       return true;
00370     }
00371 
00372   // Determine if a sequence is sorted.
00373   template<typename _InputIterator>
00374     inline bool
00375     __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
00376     {
00377       // Verify that the < operator for elements in the sequence is a
00378       // StrictWeakOrdering by checking that it is irreflexive.
00379       __glibcxx_assert(__first == __last || !(*__first < *__first));
00380 
00381       return __check_sorted_aux(__first, __last,
00382                                 std::__iterator_category(__first));
00383     }
00384 
00385   template<typename _InputIterator, typename _Predicate>
00386     inline bool
00387     __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
00388                    _Predicate __pred)
00389     {
00390       // Verify that the predicate is StrictWeakOrdering by checking that it
00391       // is irreflexive.
00392       __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
00393 
00394       return __check_sorted_aux(__first, __last, __pred,
00395                                 std::__iterator_category(__first));
00396     }
00397 
00398   template<typename _InputIterator>
00399     inline bool
00400     __check_sorted_set_aux(const _InputIterator& __first,
00401                            const _InputIterator& __last,
00402                            std::__true_type)
00403     { return __check_sorted(__first, __last); }
00404 
00405   template<typename _InputIterator>
00406     inline bool
00407     __check_sorted_set_aux(const _InputIterator&,
00408                            const _InputIterator&,
00409                            std::__false_type)
00410     { return true; }
00411 
00412   template<typename _InputIterator, typename _Predicate>
00413     inline bool
00414     __check_sorted_set_aux(const _InputIterator& __first,
00415                            const _InputIterator& __last,
00416                            _Predicate __pred, std::__true_type)
00417     { return __check_sorted(__first, __last, __pred); }
00418 
00419   template<typename _InputIterator, typename _Predicate>
00420     inline bool
00421     __check_sorted_set_aux(const _InputIterator&,
00422                            const _InputIterator&, _Predicate,
00423                            std::__false_type)
00424     { return true; }
00425 
00426   // ... special variant used in std::merge, std::includes, std::set_*.
00427   template<typename _InputIterator1, typename _InputIterator2>
00428     inline bool
00429     __check_sorted_set(const _InputIterator1& __first,
00430                        const _InputIterator1& __last,
00431                        const _InputIterator2&)
00432     {
00433       typedef typename std::iterator_traits<_InputIterator1>::value_type
00434         _ValueType1;
00435       typedef typename std::iterator_traits<_InputIterator2>::value_type
00436         _ValueType2;
00437 
00438       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00439         _SameType;
00440       return __check_sorted_set_aux(__first, __last, _SameType());
00441     }
00442 
00443   template<typename _InputIterator1, typename _InputIterator2,
00444            typename _Predicate>
00445     inline bool
00446     __check_sorted_set(const _InputIterator1& __first,
00447                        const _InputIterator1& __last,
00448                        const _InputIterator2&, _Predicate __pred)
00449     {
00450       typedef typename std::iterator_traits<_InputIterator1>::value_type
00451         _ValueType1;
00452       typedef typename std::iterator_traits<_InputIterator2>::value_type
00453         _ValueType2;
00454 
00455       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
00456         _SameType;
00457       return __check_sorted_set_aux(__first, __last, __pred, _SameType());
00458    }
00459 
00460   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00461   // 270. Binary search requirements overly strict
00462   // Determine if a sequence is partitioned w.r.t. this element.
00463   template<typename _ForwardIterator, typename _Tp>
00464     inline bool
00465     __check_partitioned_lower(_ForwardIterator __first,
00466                               _ForwardIterator __last, const _Tp& __value)
00467     {
00468       while (__first != __last && *__first < __value)
00469         ++__first;
00470       if (__first != __last)
00471         {
00472           ++__first;
00473           while (__first != __last && !(*__first < __value))
00474             ++__first;
00475         }
00476       return __first == __last;
00477     }
00478 
00479   template<typename _ForwardIterator, typename _Tp>
00480     inline bool
00481     __check_partitioned_upper(_ForwardIterator __first,
00482                               _ForwardIterator __last, const _Tp& __value)
00483     {
00484       while (__first != __last && !(__value < *__first))
00485         ++__first;
00486       if (__first != __last)
00487         {
00488           ++__first;
00489           while (__first != __last && __value < *__first)
00490             ++__first;
00491         }
00492       return __first == __last;
00493     }
00494 
00495   // Determine if a sequence is partitioned w.r.t. this element.
00496   template<typename _ForwardIterator, typename _Tp, typename _Pred>
00497     inline bool
00498     __check_partitioned_lower(_ForwardIterator __first,
00499                               _ForwardIterator __last, const _Tp& __value,
00500                               _Pred __pred)
00501     {
00502       while (__first != __last && bool(__pred(*__first, __value)))
00503         ++__first;
00504       if (__first != __last)
00505         {
00506           ++__first;
00507           while (__first != __last && !bool(__pred(*__first, __value)))
00508             ++__first;
00509         }
00510       return __first == __last;
00511     }
00512 
00513   template<typename _ForwardIterator, typename _Tp, typename _Pred>
00514     inline bool
00515     __check_partitioned_upper(_ForwardIterator __first,
00516                               _ForwardIterator __last, const _Tp& __value,
00517                               _Pred __pred)
00518     {
00519       while (__first != __last && !bool(__pred(__value, *__first)))
00520         ++__first;
00521       if (__first != __last)
00522         {
00523           ++__first;
00524           while (__first != __last && bool(__pred(__value, *__first)))
00525             ++__first;
00526         }
00527       return __first == __last;
00528     }
00529 
00530   // Helper struct to detect random access safe iterators.
00531   template<typename _Iterator>
00532     struct __is_safe_random_iterator
00533     {
00534       enum { __value = 0 };
00535       typedef std::__false_type __type;
00536     };
00537 
00538   template<typename _Iterator, typename _Sequence>
00539     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
00540     : std::__are_same<std::random_access_iterator_tag,
00541                       typename std::iterator_traits<_Iterator>::
00542                       iterator_category>
00543     { };
00544 
00545   template<typename _Iterator>
00546     struct _Siter_base
00547     : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
00548     { };
00549 
00550   /** Helper function to extract base iterator of random access safe iterator
00551       in order to reduce performance impact of debug mode.  Limited to random
00552       access iterator because it is the only category for which it is possible
00553       to check for correct iterators order in the __valid_range function
00554       thanks to the < operator.
00555   */
00556   template<typename _Iterator>
00557     inline typename _Siter_base<_Iterator>::iterator_type
00558     __base(_Iterator __it)
00559     { return _Siter_base<_Iterator>::_S_base(__it); }
00560 } // namespace __gnu_debug
00561 
00562 #endif