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