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