1// Debugging support implementation -*- C++ -*-
2
3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
4// Free Software Foundation, Inc.
5//
6// This file is part of the GNU ISO C++ Library.  This library is free
7// software; you can redistribute it and/or modify it under the
8// terms of the GNU General Public License as published by the
9// Free Software Foundation; either version 3, or (at your option)
10// any later version.
11
12// This library is distributed in the hope that it will be useful,
13// but WITHOUT ANY WARRANTY; without even the implied warranty of
14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15// GNU General Public License for more details.
16
17// Under Section 7 of GPL version 3, you are granted additional
18// permissions described in the GCC Runtime Library Exception, version
19// 3.1, as published by the Free Software Foundation.
20
21// You should have received a copy of the GNU General Public License and
22// a copy of the GCC Runtime Library Exception along with this program;
23// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24// <http://www.gnu.org/licenses/>.
25
26/** @file debug/functions.h
27 *  This file is a GNU debug extension to the Standard C++ Library.
28 */
29
30#ifndef _GLIBCXX_DEBUG_FUNCTIONS_H
31#define _GLIBCXX_DEBUG_FUNCTIONS_H 1
32
33#include <bits/c++config.h>
34#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories
35#include <bits/cpp_type_traits.h>         // for __is_integer
36#include <debug/formatter.h>
37
38namespace __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  {
122    typedef typename std::iterator_traits<_InputIterator>::iterator_category
123      _Category;
124    return __valid_range_aux2(__first, __last, _Category());
125  }
126
127  /** Don't know what these iterators are, or if they are even
128   *  iterators (we may get an integral type for InputIterator), so
129   *  see if they are integral and pass them on to the next phase
130   *  otherwise.
131  */
132  template<typename _InputIterator>
133    inline bool
134    __valid_range(const _InputIterator& __first, const _InputIterator& __last)
135    {
136      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
137      return __valid_range_aux(__first, __last, _Integral());
138    }
139
140  /** Safe iterators know how to check if they form a valid range. */
141  template<typename _Iterator, typename _Sequence>
142    inline bool
143    __valid_range(const _Safe_iterator<_Iterator, _Sequence>& __first,
144		  const _Safe_iterator<_Iterator, _Sequence>& __last)
145    { return __first._M_valid_range(__last); }
146
147  /** Safe local iterators know how to check if they form a valid range. */
148  template<typename _Iterator, typename _Sequence>
149    inline bool
150    __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first,
151		  const _Safe_local_iterator<_Iterator, _Sequence>& __last)
152    { return __first._M_valid_range(__last); }
153
154  /* Checks that [first, last) is a valid range, and then returns
155   * __first. This routine is useful when we can't use a separate
156   * assertion statement because, e.g., we are in a constructor.
157  */
158  template<typename _InputIterator>
159    inline _InputIterator
160    __check_valid_range(const _InputIterator& __first,
161			const _InputIterator& __last
162			__attribute__((__unused__)))
163    {
164      __glibcxx_check_valid_range(__first, __last);
165      return __first;
166    }
167
168  /** Checks that __s is non-NULL or __n == 0, and then returns __s. */
169  template<typename _CharT, typename _Integer>
170    inline const _CharT*
171    __check_string(const _CharT* __s,
172		   const _Integer& __n __attribute__((__unused__)))
173    {
174#ifdef _GLIBCXX_DEBUG_PEDANTIC
175      __glibcxx_assert(__s != 0 || __n == 0);
176#endif
177      return __s;
178    }
179
180  /** Checks that __s is non-NULL and then returns __s. */
181  template<typename _CharT>
182    inline const _CharT*
183    __check_string(const _CharT* __s)
184    {
185#ifdef _GLIBCXX_DEBUG_PEDANTIC
186      __glibcxx_assert(__s != 0);
187#endif
188      return __s;
189    }
190
191  // Can't check if an input iterator sequence is sorted, because we
192  // can't step through the sequence.
193  template<typename _InputIterator>
194    inline bool
195    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
196                       std::input_iterator_tag)
197    { return true; }
198
199  // Can verify if a forward iterator sequence is in fact sorted using
200  // std::__is_sorted
201  template<typename _ForwardIterator>
202    inline bool
203    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
204                       std::forward_iterator_tag)
205    {
206      if (__first == __last)
207        return true;
208
209      _ForwardIterator __next = __first;
210      for (++__next; __next != __last; __first = __next, ++__next)
211        if (*__next < *__first)
212          return false;
213
214      return true;
215    }
216
217  // Can't check if an input iterator sequence is sorted, because we can't step
218  // through the sequence.
219  template<typename _InputIterator, typename _Predicate>
220    inline bool
221    __check_sorted_aux(const _InputIterator&, const _InputIterator&,
222                       _Predicate, std::input_iterator_tag)
223    { return true; }
224
225  // Can verify if a forward iterator sequence is in fact sorted using
226  // std::__is_sorted
227  template<typename _ForwardIterator, typename _Predicate>
228    inline bool
229    __check_sorted_aux(_ForwardIterator __first, _ForwardIterator __last,
230                       _Predicate __pred, std::forward_iterator_tag)
231    {
232      if (__first == __last)
233        return true;
234
235      _ForwardIterator __next = __first;
236      for (++__next; __next != __last; __first = __next, ++__next)
237        if (__pred(*__next, *__first))
238          return false;
239
240      return true;
241    }
242
243  // Determine if a sequence is sorted.
244  template<typename _InputIterator>
245    inline bool
246    __check_sorted(const _InputIterator& __first, const _InputIterator& __last)
247    {
248      typedef typename std::iterator_traits<_InputIterator>::iterator_category
249        _Category;
250
251      // Verify that the < operator for elements in the sequence is a
252      // StrictWeakOrdering by checking that it is irreflexive.
253      __glibcxx_assert(__first == __last || !(*__first < *__first));
254
255      return __check_sorted_aux(__first, __last, _Category());
256    }
257
258  template<typename _InputIterator, typename _Predicate>
259    inline bool
260    __check_sorted(const _InputIterator& __first, const _InputIterator& __last,
261                   _Predicate __pred)
262    {
263      typedef typename std::iterator_traits<_InputIterator>::iterator_category
264        _Category;
265
266      // Verify that the predicate is StrictWeakOrdering by checking that it
267      // is irreflexive.
268      __glibcxx_assert(__first == __last || !__pred(*__first, *__first));
269
270      return __check_sorted_aux(__first, __last, __pred, _Category());
271    }
272
273  template<typename _InputIterator>
274    inline bool
275    __check_sorted_set_aux(const _InputIterator& __first,
276			   const _InputIterator& __last,
277			   std::__true_type)
278    { return __check_sorted(__first, __last); }
279
280  template<typename _InputIterator>
281    inline bool
282    __check_sorted_set_aux(const _InputIterator&,
283			   const _InputIterator&,
284			   std::__false_type)
285    { return true; }
286
287  template<typename _InputIterator, typename _Predicate>
288    inline bool
289    __check_sorted_set_aux(const _InputIterator& __first,
290			   const _InputIterator& __last,
291			   _Predicate __pred, std::__true_type)
292    { return __check_sorted(__first, __last, __pred); }
293
294  template<typename _InputIterator, typename _Predicate>
295    inline bool
296    __check_sorted_set_aux(const _InputIterator&,
297			   const _InputIterator&, _Predicate,
298			   std::__false_type)
299    { return true; }
300
301  // ... special variant used in std::merge, std::includes, std::set_*.
302  template<typename _InputIterator1, typename _InputIterator2>
303    inline bool
304    __check_sorted_set(const _InputIterator1& __first,
305		       const _InputIterator1& __last,
306		       const _InputIterator2&)
307    {
308      typedef typename std::iterator_traits<_InputIterator1>::value_type
309	_ValueType1;
310      typedef typename std::iterator_traits<_InputIterator2>::value_type
311	_ValueType2;
312
313      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
314	_SameType;
315      return __check_sorted_set_aux(__first, __last, _SameType());
316    }
317
318  template<typename _InputIterator1, typename _InputIterator2,
319	   typename _Predicate>
320    inline bool
321    __check_sorted_set(const _InputIterator1& __first,
322		       const _InputIterator1& __last,
323		       const _InputIterator2&, _Predicate __pred)
324    {
325      typedef typename std::iterator_traits<_InputIterator1>::value_type
326	_ValueType1;
327      typedef typename std::iterator_traits<_InputIterator2>::value_type
328	_ValueType2;
329
330      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
331	_SameType;
332      return __check_sorted_set_aux(__first, __last, __pred, _SameType());
333   }
334
335  // _GLIBCXX_RESOLVE_LIB_DEFECTS
336  // 270. Binary search requirements overly strict
337  // Determine if a sequence is partitioned w.r.t. this element.
338  template<typename _ForwardIterator, typename _Tp>
339    inline bool
340    __check_partitioned_lower(_ForwardIterator __first,
341			      _ForwardIterator __last, const _Tp& __value)
342    {
343      while (__first != __last && *__first < __value)
344	++__first;
345      while (__first != __last && !(*__first < __value))
346	++__first;
347      return __first == __last;
348    }
349
350  template<typename _ForwardIterator, typename _Tp>
351    inline bool
352    __check_partitioned_upper(_ForwardIterator __first,
353			      _ForwardIterator __last, const _Tp& __value)
354    {
355      while (__first != __last && !(__value < *__first))
356	++__first;
357      while (__first != __last && __value < *__first)
358	++__first;
359      return __first == __last;
360    }
361
362  // Determine if a sequence is partitioned w.r.t. this element.
363  template<typename _ForwardIterator, typename _Tp, typename _Pred>
364    inline bool
365    __check_partitioned_lower(_ForwardIterator __first,
366			      _ForwardIterator __last, const _Tp& __value,
367			      _Pred __pred)
368    {
369      while (__first != __last && bool(__pred(*__first, __value)))
370	++__first;
371      while (__first != __last && !bool(__pred(*__first, __value)))
372	++__first;
373      return __first == __last;
374    }
375
376  template<typename _ForwardIterator, typename _Tp, typename _Pred>
377    inline bool
378    __check_partitioned_upper(_ForwardIterator __first,
379			      _ForwardIterator __last, const _Tp& __value,
380			      _Pred __pred)
381    {
382      while (__first != __last && !bool(__pred(__value, *__first)))
383	++__first;
384      while (__first != __last && bool(__pred(__value, *__first)))
385	++__first;
386      return __first == __last;
387    }
388} // namespace __gnu_debug
389
390#endif
391