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 _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   // An arbitrary iterator pointer is not singular.
  56   inline bool
  57   __check_singular_aux(const void*) { return false; }
  58
  59   // We may have an iterator that derives from _Safe_iterator_base but isn't
  60   // a _Safe_iterator.
  61   template<typename _Iterator>
  62     inline bool
  63     __check_singular(const _Iterator& __x)
  64     { return __check_singular_aux(&__x); }
  65
  66   /** Non-NULL pointers are nonsingular. */
  67   template<typename _Tp>
  68     inline bool
  69     __check_singular(const _Tp* __ptr)
  70     { return __ptr == 0; }
  71
  72   /** Assume that some arbitrary iterator is dereferenceable, because we
  73       can't prove that it isn't. */
  74   template<typename _Iterator>
  75     inline bool
  76     __check_dereferenceable(const _Iterator&)
  77     { return true; }
  78
  79   /** Non-NULL pointers are dereferenceable. */
  80   template<typename _Tp>
  81     inline bool
  82     __check_dereferenceable(const _Tp* __ptr)
  83     { return __ptr; }
  84
  85   /** Safe iterators know if they are dereferenceable. */
  86   template<typename _Iterator, typename _Sequence>
  87     inline bool
  88     __check_dereferenceable(const _Safe_iterator<_Iterator, _Sequence>& __x)
  89     { return __x._M_dereferenceable(); }
  90
  91   /** Safe local iterators know if they are dereferenceable. */
  92   template<typename _Iterator, typename _Sequence>
  93     inline bool
  94     __check_dereferenceable(const _Safe_local_iterator<_Iterator,
  95                                                        _Sequence>& __x)
  96     { return __x._M_dereferenceable(); }
  97
  98   /** If the distance between two random access iterators is
  99    *  nonnegative, assume the range is valid.
 100   */
 101   template<typename _RandomAccessIterator>
 102     inline bool
 103     __valid_range_aux2(const _RandomAccessIterator& __first,
 104                        const _RandomAccessIterator& __last,
 105                        std::random_access_iterator_tag)
 106     { return __last - __first >= 0; }
 107
 108   /** Can't test for a valid range with input iterators, because
 109    *  iteration may be destructive. So we just assume that the range
 110    *  is valid.
 111   */
 112   template<typename _InputIterator>
 113     inline bool
 114     __valid_range_aux2(const _InputIterator&, const _InputIterator&,
 115                        std::input_iterator_tag)
 116     { return true; }
 117
 118   /** We say that integral types for a valid range, and defer to other
 119    *  routines to realize what to do with integral types instead of
 120    *  iterators.
 121   */
 122   template<typename _Integral>
 123     inline bool
 124     __valid_range_aux(const _Integral&, const _Integral&, std::__true_type)
 125     { return true; }
 126
 127   /** We have iterators, so figure out what kind of iterators that are
 128    *  to see if we can check the range ahead of time.
 129   */
 130   template<typename _InputIterator>
 131     inline bool
 132     __valid_range_aux(const _InputIterator& __first,
 133                       const _InputIterator& __last, std::__false_type)
 134     { return __valid_range_aux2(__first, __last,
 135                                 std::__iterator_category(__first)); }
 136
 137   /** Don't know what these iterators are, or if they are even
 138    *  iterators (we may get an integral type for InputIterator), so
 139    *  see if they are integral and pass them on to the next phase
 140    *  otherwise.
 141   */
 142   template<typename _InputIterator>
 143     inline bool
 144     __valid_range(const _InputIterator& __first, const _InputIterator& __last)
 145     {
 146       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 147       return __valid_range_aux(__first, __last, _Integral());
 148     }
 149
 150   /** Safe iterators know how to check if they form a valid range. */
 151   template<typename _Iterator, typename _Sequence>
 152     inline bool
 153     __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
 154                   const _Safe_iterator<_Iterator, _Sequence>& __last)
 155     { return __first._M_valid_range(__last); }
 156
 157   /** Safe local iterators know how to check if they form a valid range. */
 158   template<typename _Iterator, typename _Sequence>
 159     inline bool
 160     __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
 161                   const _Safe_local_iterator<_Iterator, _Sequence>& __last)
 162     { return __first._M_valid_range(__last); }
 163
 164   /* Checks that [first, last) is a valid range, and then returns
 165    * __first. This routine is useful when we can't use a separate
 166    * assertion statement because, e.g., we are in a constructor.
 167   */
 168   template<typename _InputIterator>
 169     inline _InputIterator
 170     __check_valid_range(const _InputIterator& __first,
 171                         const _InputIterator& __last
 172                         __attribute__((__unused__)))
 173     {
 174       __glibcxx_check_valid_range(__first, __last);
 175       return __first;
 176     }
 177
 178 #if __cplusplus >= 201103L
 179   // Default implementation.
 180   template<typename _Iterator, typename _Sequence>
 181     inline bool
 182     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>& __it,
 183                             typename _Sequence::const_pointer __begin,
 184                             typename _Sequence::const_pointer __other)
 185     {
 186       typedef typename _Sequence::const_pointer _PointerType;
 187       constexpr std::less<_PointerType> __l{};
 188
 189       return (__l(__other, __begin)
 190               || __l(std::addressof(*(__it._M_get_sequence()->_M_base().end()
 191                                       - 1)), __other));
 192     }
 193
 194   // Fallback when address type cannot be implicitely casted to sequence
 195   // const_pointer.
 196   template<typename _Iterator, typename _Sequence,
 197            typename _InputIterator>
 198     inline bool
 199     __foreign_iterator_aux4(const _Safe_iterator<_Iterator, _Sequence>&,
 200                             _InputIterator, ...)
 201     { return true; }
 202
 203   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 204     inline bool
 205     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
 206                             _InputIterator __other,
 207                             std::true_type)
 208     {
 209       // Only containers with all elements in contiguous memory can have their
 210       // elements passed through pointers.
 211       // Arithmetics is here just to make sure we are not dereferencing
 212       // past-the-end iterator.
 213       if (__it._M_get_sequence()->_M_base().begin()
 214           != __it._M_get_sequence()->_M_base().end())
 215         if (std::addressof(*(__it._M_get_sequence()->_M_base().end() - 1))
 216             - std::addressof(*(__it._M_get_sequence()->_M_base().begin()))
 217             == __it._M_get_sequence()->size() - 1)
 218           return (__foreign_iterator_aux4
 219                   (__it,
 220                    std::addressof(*(__it._M_get_sequence()->_M_base().begin())),
 221                    std::addressof(*__other)));
 222       return true;
 223     }
 224
 225   /* Fallback overload for which we can't say, assume it is valid. */
 226   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 227     inline bool
 228     __foreign_iterator_aux3(const _Safe_iterator<_Iterator, _Sequence>& __it,
 229                             _InputIterator __other,
 230                             std::false_type)
 231     { return true; }
 232 #endif
 233
 234   /** Checks that iterators do not belong to the same sequence. */
 235   template<typename _Iterator, typename _Sequence, typename _OtherIterator>
 236     inline bool
 237     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
 238                 const _Safe_iterator<_OtherIterator, _Sequence>& __other,
 239                 std::input_iterator_tag)
 240     { return __it._M_get_sequence() != __other._M_get_sequence(); }
 241
 242 #if __cplusplus >= 201103L
 243   /* This overload detects when passing pointers to the contained elements
 244      rather than using iterators.
 245    */
 246   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 247     inline bool
 248     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>& __it,
 249                             _InputIterator __other,
 250                             std::random_access_iterator_tag)
 251     {
 252       typedef typename _Sequence::const_iterator _ItType;
 253       typedef typename std::iterator_traits<_ItType>::reference _Ref;
 254       return __foreign_iterator_aux3(__it, __other,
 255                                      std::is_lvalue_reference<_Ref>());
 256     }
 257 #endif
 258
 259   /* Fallback overload for which we can't say, assume it is valid. */
 260   template<typename _Iterator, typename _Sequence, typename _InputIterator>
 261     inline bool
 262     __foreign_iterator_aux2(const _Safe_iterator<_Iterator, _Sequence>&,
 263                            _InputIterator,
 264                            std::input_iterator_tag)
 265     { return true; }
 266
 267   template<typename _Iterator, typename _Sequence,
 268            typename _Integral>
 269     inline bool
 270     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
 271                            _Integral __other,
 272                            std::__true_type)
 273     { return true; }
 274
 275   template<typename _Iterator, typename _Sequence,
 276            typename _InputIterator>
 277     inline bool
 278     __foreign_iterator_aux(const _Safe_iterator<_Iterator, _Sequence>& __it,
 279                            _InputIterator __other,
 280                            std::__false_type)
 281     {
 282       return (_Insert_range_from_self_is_safe<_Sequence>::__value
 283               || __foreign_iterator_aux2(__it, __other,
 284                                          std::__iterator_category(__it)));
 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)
 292     {
 293       typedef typename std::__is_integer<_InputIterator>::__type _Integral;
 294       return __foreign_iterator_aux(__it, __other, _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