libstdc++-v3/include/debug/functions.h

   1 // Debugging support implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2015 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/functions.h
  26  *  This file is a GNU debug extension to the Standard C++ Library.
  27  */
  28
  29 #ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
  30 #define _GLIBCXX_DEBUG_FUNCTIONS_H 1
  31
  32 #include <bits/c++config.h>
  33 #include <bits/stl_iterator_base_types.h>       // for iterator_traits,
  34                                                 // categories and _Iter_base
  35 #include <bits/cpp_type_traits.h>               // for __is_integer
  36
  37 #include <bits/move.h>                          // for __addressof
  38 #include <bits/stl_function.h>                  // for less
  39 #if __cplusplus >= 201103L
  40 # include <type_traits>                         // for is_lvalue_reference and
  41                                                 // conditional.
  42 #endif
  43
  44 #include <debug/formatter.h>
  45
  46 namespace __gnu_debug
  47 {
  48   template<typename _Iterator, typename _Sequence>
  49     class _Safe_iterator;
  50
  51   template<typename _Sequence>
  52     struct _Insert_range_from_self_is_safe
  53     { enum { __value = 0 }; };
  54
  55   template<typename _Sequence>
  56     struct _Is_contiguous_sequence : std::__false_type { };
  57
  58   // An arbitrary iterator pointer is not singular.
  59   inline bool
  60   __check_singular_aux(const void*) { return false; }
  61
  62   // We may have an iterator that derives from _Safe_iterator_base but isn't
  63   // a _Safe_iterator.
  64   template<typename _Iterator>
  65     inline bool
  66     __check_singular(const _Iterator& __x)
  67     { return __check_singular_aux(std::__addressof(__x)); }
  68
  69   /** Non-NULL pointers are nonsingular. */
  70   template<typename _Tp>
  71     inline bool
  72     __check_singular(const _Tp* __ptr)
  73     { return __ptr == 0; }
  74
  75   /** Assume that some arbitrary iterator is dereferenceable, because we
  76       can't prove that it isn't. */
  77   template<typename _Iterator>
  78     inline bool
  79     __check_dereferenceable(const _Iterator&)
  80     { return true; }
  81
  82   /** Non-NULL pointers are dereferenceable. */
  83   template<typename _Tp>
  84     inline bool
  85     __check_dereferenceable(const _Tp* __ptr)
  86     { return __ptr; }
  87
  88   /** If the distance between two random access iterators is
  89    *  nonnegative, assume the range is valid.
  90   */
  91   template<typename _RandomAccessIterator>
  92     inline bool
  93     __valid_range_aux2(const _RandomAccessIterator& __first,
  94                        const _RandomAccessIterator& __last,
  95                        std::random_access_iterator_tag)
  96     { return __last - __first >= 0; }
  97
  98   /** Can't test for a valid range with input iterators, because
  99    *  iteration may be destructive. So we just assume that the range
 100    *  is valid.
 101   */
 102   template<typename _InputIterator>
 103     inline bool
 104     __valid_range_aux2(const _InputIterator&, const _InputIterator&,
 105                        std::input_iterator_tag)
 106     { return true; }
 107
 108   /** We say that integral types for a valid range, and defer to other
 109    *  routines to realize what to do with integral types instead of
 110    *  iterators.
 111   */
 112   template<typename _Integral>
 113     inline bool
 114     __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
 115     { return true; }
 116
 117   /** We have iterators, so figure out what kind of iterators that are
 118    *  to see if we can check the range ahead of time.
 119   */
 120   template<typename _InputIterator>
 121     inline bool
 122     __valid_range_aux(const _InputIterator& __first,
 123                       const _InputIterator& __last, std::__false_type)
 124     { return __valid_range_aux2(__first, __last,
 125                                 std::__iterator_category(__first)); }
 126
 127   /** Don't know what these iterators are, or if they are even
 128    *  iterators (we may get an integral type for InputIterator), so
 129    *  see if they are integral and pass them on to the next phase
 130    *  otherwise.
 131   */
 132   template<typename _InputIterator>
 133     inline bool
 134     __valid_range(const _InputIterator& __first, const _InputIterator& __last)
 135     {
 136       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 137       return __valid_range_aux(__first, __last, _Integral());
 138     }
 139
 140   /* Checks that [first, last) is a valid range, and then returns
 141    * __first. This routine is useful when we can't use a separate
 142    * assertion statement because, e.g., we are in a constructor.
 143   */
 144   template<typename _InputIterator>
 145     inline _InputIterator
 146     __check_valid_range(const _InputIterator& __first,
 147                         const _InputIterator& __last
 148                         __attribute__((__unused__)))
 149     {
 150       __glibcxx_check_valid_range(__first, __last);
 151       return __first;
 152     }
 153
 154   /* Handle the case where __other is a pointer to _Sequence::value_type. */
 155   template<typename _Iterator, typename _Sequence>
 156     inline bool
 157     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
 158                             const typename _Sequence::value_type* __other)
 159     {
 160       typedef const typename _Sequence::value_type* _PointerType;
 161       typedef std::less<_PointerType> _Less;
 162 #if __cplusplus >= 201103L
 163       constexpr _Less __l{};
 164 #else
 165       const _Less __l = _Less();
 166 #endif
 167       const _Sequence* __seq = __it._M_get_sequence();
 168       const _PointerType __begin = std::__addressof(*__seq->_M_base().begin());
 169       const _PointerType __end = std::__addressof(*(__seq->_M_base().end()-1));
 170
 171       // Check whether __other points within the contiguous storage.
 172       return __l(__other, __begin) || __l(__end, __other);
 173     }
 174
 175   /* Fallback overload for when we can't tell, assume it is valid. */
 176   template<typename _Iterator, typename _Sequence>
 177     inline bool
 178     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&, ...)
 179     { return true; }
 180
 181   /* Handle sequences with contiguous storage */
 182   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 183     inline bool
 184     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
 185                             const _InputIterator& __other,
 186                             const _InputIterator& __other_end,
 187                             std::__true_type)
 188     {
 189       if (__other == __other_end)
 190         return true;  // inserting nothing is safe even if not foreign iters
 191       if (__it._M_get_sequence()->begin() == __it._M_get_sequence()->end())
 192         return true;  // can't be self-inserting if self is empty
 193       return __foreign_iterator_aux4(__it, std::__addressof(*__other));
 194     }
 195
 196   /* Handle non-contiguous containers, assume it is valid. */
 197   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 198     inline bool
 199     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>&,
 200                             const _InputIterator&, const _InputIterator&,
 201                             std::__false_type)
 202     { return true; }
 203
 204   /** Handle debug iterators from the same type of container. */
 205   template<typename _Iterator, typename _Sequence, typename _OtherIterator>
 206     inline bool
 207     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
 208                 const _Safe_iterator<_OtherIterator, _Sequence>& __other,
 209                 const _Safe_iterator<_OtherIterator, _Sequence>&)
 210     { return __it._M_get_sequence() != __other._M_get_sequence(); }
 211
 212   /** Handle debug iterators from different types of container. */
 213   template<typename _Iterator, typename _Sequence, typename _OtherIterator,
 214            typename _OtherSequence>
 215     inline bool
 216     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
 217                 const _Safe_iterator<_OtherIterator, _OtherSequence>&,
 218                 const _Safe_iterator<_OtherIterator, _OtherSequence>&)
 219     { return true; }
 220
 221   /* Handle non-debug iterators. */
 222   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 223     inline bool
 224     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
 225                             const _InputIterator& __other,
 226                             const _InputIterator& __other_end)
 227     {
 228 #if __cplusplus < 201103L
 229       typedef _Is_contiguous_sequence<_Sequence> __tag;
 230 #else
 231       using __lvalref = std::is_lvalue_reference<
 232         typename std::iterator_traits<_InputIterator>::reference>;
 233       using __contiguous = _Is_contiguous_sequence<_Sequence>;
 234       using __tag = typename std::conditional<__lvalref::value, __contiguous,
 235                                               std::__false_type>::type;
 236 #endif
 237       return __foreign_iterator_aux3(__it, __other, __other_end, __tag());
 238     }
 239
 240   /* Handle the case where we aren't really inserting a range after all */
 241   template<typename _Iterator, typename _Sequence, typename _Integral>
 242     inline bool
 243     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
 244                            _Integral, _Integral,
 245                            std::__true_type)
 246     { return true; }
 247
 248   /* Handle all iterators. */
 249   template<typename _Iterator, typename _Sequence,
 250            typename _InputIterator>
 251     inline bool
 252     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
 253                            _InputIterator __other, _InputIterator __other_end,
 254                            std::__false_type)
 255     {
 256       return _Insert_range_from_self_is_safe<_Sequence>::__value
 257              || __foreign_iterator_aux2(__it, __other, __other_end);
 258     }
 259
 260   template<typename _Iterator, typename _Sequence,
 261            typename _InputIterator>
 262     inline bool
 263     __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
 264                        _InputIterator __other, _InputIterator __other_end)
 265     {
 266       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 267       return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
 268     }
 269
 270   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
 271   template<typename _CharT, typename _Integer>
 272     inline const _CharT*
 273     __check_string(const _CharT* __s,
 274                    const _Integer& __n __attribute__((__unused__)))
 275     {
 276 #ifdef _GLIBCXX_DEBUG_PEDANTIC
 277       __glibcxx_assert(__s != 0 || __n == 0);
 278 #endif
 279       return __s;
 280     }
 281
 282   /** Checks that __s is non-NULL and then returns __s. */
 283   template<typename _CharT>
 284     inline const _CharT*
 285     __check_string(const _CharT* __s)
 286     {
 287 #ifdef _GLIBCXX_DEBUG_PEDANTIC
 288       __glibcxx_assert(__s != 0);
 289 #endif
 290       return __s;
 291     }
 292
 293   // Can't check if an input iterator sequence is sorted, because we
 294   // can't step through the sequence.
 295   template<typename _InputIterator>
 296     inline bool
 297     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
 298                        std::input_iterator_tag)
 299     { return true; }
 300
 301   // Can verify if a forward iterator sequence is in fact sorted using
 302   // std::__is_sorted
 303   template<typename _ForwardIterator>
 304     inline bool
 305     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
 306                        std::forward_iterator_tag)
 307     {
 308       if (__first == __last)
 309         return true;
 310
 311       _ForwardIterator __next = __first;
 312       for (++__next; __next != __last; __first = __next, (void)++__next)
 313         if (*__next < *__first)
 314           return false;
 315
 316       return true;
 317     }
 318
 319   // Can't check if an input iterator sequence is sorted, because we can't step
 320   // through the sequence.
 321   template<typename _InputIterator, typename _Predicate>
 322     inline bool
 323     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
 324                        _Predicate, std::input_iterator_tag)
 325     { return true; }
 326
 327   // Can verify if a forward iterator sequence is in fact sorted using
 328   // std::__is_sorted
 329   template<typename _ForwardIterator, typename _Predicate>
 330     inline bool
 331     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
 332                        _Predicate __pred, std::forward_iterator_tag)
 333     {
 334       if (__first == __last)
 335         return true;
 336
 337       _ForwardIterator __next = __first;
 338       for (++__next; __next != __last; __first = __next, (void)++__next)
 339         if (__pred(*__next, *__first))
 340           return false;
 341
 342       return true;
 343     }
 344
 345   // Determine if a sequence is sorted.
 346   template<typename _InputIterator>
 347     inline bool
 348     __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
 349     {
 350       // Verify that the < operator for elements in the sequence is a
 351       // StrictWeakOrdering by checking that it is irreflexive.
 352       __glibcxx_assert(__first == __last || !(*__first < *__first));
 353
 354       return __check_sorted_aux(__first, __last,
 355                                 std::__iterator_category(__first));
 356     }
 357
 358   template<typename _InputIterator, typename _Predicate>
 359     inline bool
 360     __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
 361                    _Predicate __pred)
 362     {
 363       // Verify that the predicate is StrictWeakOrdering by checking that it
 364       // is irreflexive.
 365       __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
 366
 367       return __check_sorted_aux(__first, __last, __pred,
 368                                 std::__iterator_category(__first));
 369     }
 370
 371   template<typename _InputIterator>
 372     inline bool
 373     __check_sorted_set_aux(const _InputIterator& __first,
 374                            const _InputIterator& __last,
 375                            std::__true_type)
 376     { return __check_sorted(__first, __last); }
 377
 378   template<typename _InputIterator>
 379     inline bool
 380     __check_sorted_set_aux(const _InputIterator&,
 381                            const _InputIterator&,
 382                            std::__false_type)
 383     { return true; }
 384
 385   template<typename _InputIterator, typename _Predicate>
 386     inline bool
 387     __check_sorted_set_aux(const _InputIterator& __first,
 388                            const _InputIterator& __last,
 389                            _Predicate __pred, std::__true_type)
 390     { return __check_sorted(__first, __last, __pred); }
 391
 392   template<typename _InputIterator, typename _Predicate>
 393     inline bool
 394     __check_sorted_set_aux(const _InputIterator&,
 395                            const _InputIterator&, _Predicate,
 396                            std::__false_type)
 397     { return true; }
 398
 399   // ... special variant used in std::merge, std::includes, std::set_*.
 400   template<typename _InputIterator1, typename _InputIterator2>
 401     inline bool
 402     __check_sorted_set(const _InputIterator1& __first,
 403                        const _InputIterator1& __last,
 404                        const _InputIterator2&)
 405     {
 406       typedef typename std::iterator_traits<_InputIterator1>::value_type
 407         _ValueType1;
 408       typedef typename std::iterator_traits<_InputIterator2>::value_type
 409         _ValueType2;
 410
 411       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
 412         _SameType;
 413       return __check_sorted_set_aux(__first, __last, _SameType());
 414     }
 415
 416   template<typename _InputIterator1, typename _InputIterator2,
 417            typename _Predicate>
 418     inline bool
 419     __check_sorted_set(const _InputIterator1& __first,
 420                        const _InputIterator1& __last,
 421                        const _InputIterator2&, _Predicate __pred)
 422     {
 423       typedef typename std::iterator_traits<_InputIterator1>::value_type
 424         _ValueType1;
 425       typedef typename std::iterator_traits<_InputIterator2>::value_type
 426         _ValueType2;
 427
 428       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
 429         _SameType;
 430       return __check_sorted_set_aux(__first, __last, __pred, _SameType());
 431    }
 432
 433   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 434   // 270. Binary search requirements overly strict
 435   // Determine if a sequence is partitioned w.r.t. this element.
 436   template<typename _ForwardIterator, typename _Tp>
 437     inline bool
 438     __check_partitioned_lower(_ForwardIterator __first,
 439                               _ForwardIterator __last, const _Tp& __value)
 440     {
 441       while (__first != __last && *__first < __value)
 442         ++__first;
 443       if (__first != __last)
 444         {
 445           ++__first;
 446           while (__first != __last && !(*__first < __value))
 447             ++__first;
 448         }
 449       return __first == __last;
 450     }
 451
 452   template<typename _ForwardIterator, typename _Tp>
 453     inline bool
 454     __check_partitioned_upper(_ForwardIterator __first,
 455                               _ForwardIterator __last, const _Tp& __value)
 456     {
 457       while (__first != __last && !(__value < *__first))
 458         ++__first;
 459       if (__first != __last)
 460         {
 461           ++__first;
 462           while (__first != __last && __value < *__first)
 463             ++__first;
 464         }
 465       return __first == __last;
 466     }
 467
 468   // Determine if a sequence is partitioned w.r.t. this element.
 469   template<typename _ForwardIterator, typename _Tp, typename _Pred>
 470     inline bool
 471     __check_partitioned_lower(_ForwardIterator __first,
 472                               _ForwardIterator __last, const _Tp& __value,
 473                               _Pred __pred)
 474     {
 475       while (__first != __last && bool(__pred(*__first, __value)))
 476         ++__first;
 477       if (__first != __last)
 478         {
 479           ++__first;
 480           while (__first != __last && !bool(__pred(*__first, __value)))
 481             ++__first;
 482         }
 483       return __first == __last;
 484     }
 485
 486   template<typename _ForwardIterator, typename _Tp, typename _Pred>
 487     inline bool
 488     __check_partitioned_upper(_ForwardIterator __first,
 489                               _ForwardIterator __last, const _Tp& __value,
 490                               _Pred __pred)
 491     {
 492       while (__first != __last && !bool(__pred(__value, *__first)))
 493         ++__first;
 494       if (__first != __last)
 495         {
 496           ++__first;
 497           while (__first != __last && bool(__pred(__value, *__first)))
 498             ++__first;
 499         }
 500       return __first == __last;
 501     }
 502
 503   // Helper struct to detect random access safe iterators.
 504   template<typename _Iterator>
 505     struct __is_safe_random_iterator
 506     {
 507       enum { __value = 0 };
 508       typedef std::__false_type __type;
 509     };
 510
 511   template<typename _Iterator>
 512     struct _Siter_base
 513     : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
 514     { };
 515
 516   /** Helper function to extract base iterator of random access safe iterator
 517       in order to reduce performance impact of debug mode.  Limited to random
 518       access iterator because it is the only category for which it is possible
 519       to check for correct iterators order in the __valid_range function
 520       thanks to the < operator.
 521   */
 522   template<typename _Iterator>
 523     inline typename _Siter_base<_Iterator>::iterator_type
 524     __base(_Iterator __it)
 525     { return _Siter_base<_Iterator>::_S_base(__it); }
 526 } // namespace __gnu_debug
 527
 528 #endif