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

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