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

   1 // Debugging support implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2014 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       return __foreign_iterator_aux3(__it, __other, __other_end,
 256                                      _Is_contiguous_sequence<_Sequence>());
 257     }
 258
 259   /* Handle the case where we aren't really inserting a range after all */
 260   template<typename _Iterator, typename _Sequence, typename _Integral>
 261     inline bool
 262     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>&,
 263                            _Integral, _Integral,
 264                            std::__true_type)
 265     { return true; }
 266
 267   /* Handle all iterators. */
 268   template<typename _Iterator, typename _Sequence,
 269            typename _InputIterator>
 270     inline bool
 271     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
 272                            _InputIterator __other, _InputIterator __other_end,
 273                            std::__false_type)
 274     {
 275       return _Insert_range_from_self_is_safe<_Sequence>::__value
 276              || __foreign_iterator_aux2(__it, __other, __other_end);
 277     }
 278
 279   template<typename _Iterator, typename _Sequence,
 280            typename _InputIterator>
 281     inline bool
 282     __foreign_iterator(const _Safe_iterator<_Iterator, _Sequence>& __it,
 283                        _InputIterator __other, _InputIterator __other_end)
 284     {
 285       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 286       return __foreign_iterator_aux(__it, __other, __other_end, _Integral());
 287     }
 288
 289   /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
 290   template<typename _CharT, typename _Integer>
 291     inline const _CharT*
 292     __check_string(const _CharT* __s,
 293                    const _Integer& __n __attribute__((__unused__)))
 294     {
 295 #ifdef _GLIBCXX_DEBUG_PEDANTIC
 296       __glibcxx_assert(__s != 0 || __n == 0);
 297 #endif
 298       return __s;
 299     }
 300
 301   /** Checks that __s is non-NULL and then returns __s. */
 302   template<typename _CharT>
 303     inline const _CharT*
 304     __check_string(const _CharT* __s)
 305     {
 306 #ifdef _GLIBCXX_DEBUG_PEDANTIC
 307       __glibcxx_assert(__s != 0);
 308 #endif
 309       return __s;
 310     }
 311
 312   // Can't check if an input iterator sequence is sorted, because we
 313   // can't step through the sequence.
 314   template<typename _InputIterator>
 315     inline bool
 316     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
 317                        std::input_iterator_tag)
 318     { return true; }
 319
 320   // Can verify if a forward iterator sequence is in fact sorted using
 321   // std::__is_sorted
 322   template<typename _ForwardIterator>
 323     inline bool
 324     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
 325                        std::forward_iterator_tag)
 326     {
 327       if (__first == __last)
 328         return true;
 329
 330       _ForwardIterator __next = __first;
 331       for (++__next; __next != __last; __first = __next, ++__next)
 332         if (*__next < *__first)
 333           return false;
 334
 335       return true;
 336     }
 337
 338   // Can't check if an input iterator sequence is sorted, because we can't step
 339   // through the sequence.
 340   template<typename _InputIterator, typename _Predicate>
 341     inline bool
 342     __check_sorted_aux(const _InputIterator&, const _InputIterator&,
 343                        _Predicate, std::input_iterator_tag)
 344     { return true; }
 345
 346   // Can verify if a forward iterator sequence is in fact sorted using
 347   // std::__is_sorted
 348   template<typename _ForwardIterator, typename _Predicate>
 349     inline bool
 350     __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
 351                        _Predicate __pred, std::forward_iterator_tag)
 352     {
 353       if (__first == __last)
 354         return true;
 355
 356       _ForwardIterator __next = __first;
 357       for (++__next; __next != __last; __first = __next, ++__next)
 358         if (__pred(*__next, *__first))
 359           return false;
 360
 361       return true;
 362     }
 363
 364   // Determine if a sequence is sorted.
 365   template<typename _InputIterator>
 366     inline bool
 367     __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
 368     {
 369       // Verify that the < operator for elements in the sequence is a
 370       // StrictWeakOrdering by checking that it is irreflexive.
 371       __glibcxx_assert(__first == __last || !(*__first < *__first));
 372
 373       return __check_sorted_aux(__first, __last,
 374                                 std::__iterator_category(__first));
 375     }
 376
 377   template<typename _InputIterator, typename _Predicate>
 378     inline bool
 379     __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
 380                    _Predicate __pred)
 381     {
 382       // Verify that the predicate is StrictWeakOrdering by checking that it
 383       // is irreflexive.
 384       __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
 385
 386       return __check_sorted_aux(__first, __last, __pred,
 387                                 std::__iterator_category(__first));
 388     }
 389
 390   template<typename _InputIterator>
 391     inline bool
 392     __check_sorted_set_aux(const _InputIterator& __first,
 393                            const _InputIterator& __last,
 394                            std::__true_type)
 395     { return __check_sorted(__first, __last); }
 396
 397   template<typename _InputIterator>
 398     inline bool
 399     __check_sorted_set_aux(const _InputIterator&,
 400                            const _InputIterator&,
 401                            std::__false_type)
 402     { return true; }
 403
 404   template<typename _InputIterator, typename _Predicate>
 405     inline bool
 406     __check_sorted_set_aux(const _InputIterator& __first,
 407                            const _InputIterator& __last,
 408                            _Predicate __pred, std::__true_type)
 409     { return __check_sorted(__first, __last, __pred); }
 410
 411   template<typename _InputIterator, typename _Predicate>
 412     inline bool
 413     __check_sorted_set_aux(const _InputIterator&,
 414                            const _InputIterator&, _Predicate,
 415                            std::__false_type)
 416     { return true; }
 417
 418   // ... special variant used in std::merge, std::includes, std::set_*.
 419   template<typename _InputIterator1, typename _InputIterator2>
 420     inline bool
 421     __check_sorted_set(const _InputIterator1& __first,
 422                        const _InputIterator1& __last,
 423                        const _InputIterator2&)
 424     {
 425       typedef typename std::iterator_traits<_InputIterator1>::value_type
 426         _ValueType1;
 427       typedef typename std::iterator_traits<_InputIterator2>::value_type
 428         _ValueType2;
 429
 430       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
 431         _SameType;
 432       return __check_sorted_set_aux(__first, __last, _SameType());
 433     }
 434
 435   template<typename _InputIterator1, typename _InputIterator2,
 436            typename _Predicate>
 437     inline bool
 438     __check_sorted_set(const _InputIterator1& __first,
 439                        const _InputIterator1& __last,
 440                        const _InputIterator2&, _Predicate __pred)
 441     {
 442       typedef typename std::iterator_traits<_InputIterator1>::value_type
 443         _ValueType1;
 444       typedef typename std::iterator_traits<_InputIterator2>::value_type
 445         _ValueType2;
 446
 447       typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
 448         _SameType;
 449       return __check_sorted_set_aux(__first, __last, __pred, _SameType());
 450    }
 451
 452   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 453   // 270. Binary search requirements overly strict
 454   // Determine if a sequence is partitioned w.r.t. this element.
 455   template<typename _ForwardIterator, typename _Tp>
 456     inline bool
 457     __check_partitioned_lower(_ForwardIterator __first,
 458                               _ForwardIterator __last, const _Tp& __value)
 459     {
 460       while (__first != __last && *__first < __value)
 461         ++__first;
 462       if (__first != __last)
 463         {
 464           ++__first;
 465           while (__first != __last && !(*__first < __value))
 466             ++__first;
 467         }
 468       return __first == __last;
 469     }
 470
 471   template<typename _ForwardIterator, typename _Tp>
 472     inline bool
 473     __check_partitioned_upper(_ForwardIterator __first,
 474                               _ForwardIterator __last, const _Tp& __value)
 475     {
 476       while (__first != __last && !(__value < *__first))
 477         ++__first;
 478       if (__first != __last)
 479         {
 480           ++__first;
 481           while (__first != __last && __value < *__first)
 482             ++__first;
 483         }
 484       return __first == __last;
 485     }
 486
 487   // Determine if a sequence is partitioned w.r.t. this element.
 488   template<typename _ForwardIterator, typename _Tp, typename _Pred>
 489     inline bool
 490     __check_partitioned_lower(_ForwardIterator __first,
 491                               _ForwardIterator __last, const _Tp& __value,
 492                               _Pred __pred)
 493     {
 494       while (__first != __last && bool(__pred(*__first, __value)))
 495         ++__first;
 496       if (__first != __last)
 497         {
 498           ++__first;
 499           while (__first != __last && !bool(__pred(*__first, __value)))
 500             ++__first;
 501         }
 502       return __first == __last;
 503     }
 504
 505   template<typename _ForwardIterator, typename _Tp, typename _Pred>
 506     inline bool
 507     __check_partitioned_upper(_ForwardIterator __first,
 508                               _ForwardIterator __last, const _Tp& __value,
 509                               _Pred __pred)
 510     {
 511       while (__first != __last && !bool(__pred(__value, *__first)))
 512         ++__first;
 513       if (__first != __last)
 514         {
 515           ++__first;
 516           while (__first != __last && bool(__pred(__value, *__first)))
 517             ++__first;
 518         }
 519       return __first == __last;
 520     }
 521
 522   // Helper struct to detect random access safe iterators.
 523   template<typename _Iterator>
 524     struct __is_safe_random_iterator
 525     {
 526       enum { __value = 0 };
 527       typedef std::__false_type __type;
 528     };
 529
 530   template<typename _Iterator, typename _Sequence>
 531     struct __is_safe_random_iterator<_Safe_iterator<_Iterator, _Sequence> >
 532     : std::__are_same<std::random_access_iterator_tag,
 533                       typename std::iterator_traits<_Iterator>::
 534                       iterator_category>
 535     { };
 536
 537   template<typename _Iterator>
 538     struct _Siter_base
 539     : std::_Iter_base<_Iterator, __is_safe_random_iterator<_Iterator>::__value>
 540     { };
 541
 542   /** Helper function to extract base iterator of random access safe iterator
 543       in order to reduce performance impact of debug mode.  Limited to random
 544       access iterator because it is the only category for which it is possible
 545       to check for correct iterators order in the __valid_range function
 546       thanks to the < operator.
 547   */
 548   template<typename _Iterator>
 549     inline typename _Siter_base<_Iterator>::iterator_type
 550     __base(_Iterator __it)
 551     { return _Siter_base<_Iterator>::_S_base(__it); }
 552 } // namespace __gnu_debug
 553
 554 #endif