This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Patch preview: libstdc++/34730
- From: Paolo Carlini <pcarlini at suse dot de>
- To: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Fri, 11 Jan 2008 03:44:37 +0100
- Subject: Patch preview: libstdc++/34730
Hi,
I'm working on this interesting issue, and I'm under the impression
that, overall, we cannot have an optimal result - in terms of strictness
of the testing while not breaking conforming code (probably concepts
would be, in some areas). My best idea so far, is limiting the testing
to when the two involved input iterator types have the same value_type,
per the below, which I'm finishing testing (and maybe cleaning a bit
more). Are there any better suggestions? Otherwise, I will just go ahead
like this, at least for 4.3.
Thanks,
Paolo.
//////////////////
Index: include/debug/functions.h
===================================================================
--- include/debug/functions.h (revision 131447)
+++ include/debug/functions.h (working copy)
@@ -1,6 +1,6 @@
// Debugging support implementation -*- C++ -*-
-// Copyright (C) 2003, 2005, 2006
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
// Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
@@ -38,7 +38,7 @@
#include <bits/c++config.h>
#include <cstddef> // for ptrdiff_t
#include <bits/stl_iterator_base_types.h> // for iterator_traits, categories
-#include <bits/cpp_type_traits.h> // for __is_integer
+#include <ext/type_traits.h> // for __conditional_type, __is_integer
namespace __gnu_debug
{
@@ -205,10 +205,9 @@
return true;
_ForwardIterator __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
+ for (++__next; __next != __last; __first = __next, ++__next)
if (*__next < *__first)
return false;
- }
return true;
}
@@ -232,10 +231,9 @@
return true;
_ForwardIterator __next = __first;
- for (++__next; __next != __last; __first = __next, ++__next) {
+ for (++__next; __next != __last; __first = __next, ++__next)
if (__pred(*__next, *__first))
return false;
- }
return true;
}
@@ -257,10 +255,50 @@
{
typedef typename std::iterator_traits<_InputIterator>::iterator_category
_Category;
- return __check_sorted_aux(__first, __last, __pred,
- _Category());
+ return __check_sorted_aux(__first, __last, __pred, _Category());
}
+ template<typename _InputIterator1, typename _InputIterator2>
+ inline bool
+ __check_sorted_set(const _InputIterator1& __first,
+ const _InputIterator1& __last,
+ const _InputIterator2&)
+ {
+ typedef typename std::iterator_traits<_InputIterator1>::iterator_category
+ _Category;
+ typedef typename std::iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename std::iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
+ typedef typename __gnu_cxx::__conditional_type<
+ std::__are_same<_ValueType1, _ValueType2>::__value, _Category,
+ std::input_iterator_tag>::__type _Tag;
+
+ return __check_sorted_aux(__first, __last, _Tag());
+ }
+
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _Predicate>
+ inline bool
+ __check_sorted_set(const _InputIterator1& __first,
+ const _InputIterator1& __last,
+ const _InputIterator2&, _Predicate __pred)
+ {
+ typedef typename std::iterator_traits<_InputIterator1>::iterator_category
+ _Category;
+ typedef typename std::iterator_traits<_InputIterator1>::value_type
+ _ValueType1;
+ typedef typename std::iterator_traits<_InputIterator2>::value_type
+ _ValueType2;
+
+ typedef typename __gnu_cxx::__conditional_type<
+ std::__are_same<_ValueType1, _ValueType2>::__value, _Category,
+ std::input_iterator_tag>::__type _Tag;
+
+ return __check_sorted_aux(__first, __last, __pred, _Tag());
+ }
+
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 270. Binary search requirements overly strict
// Determine if a sequence is partitioned w.r.t. this element.
Index: include/debug/macros.h
===================================================================
--- include/debug/macros.h (revision 131452)
+++ include/debug/macros.h (working copy)
@@ -171,6 +171,25 @@
._M_iterator(_Last, #_Last) \
._M_string(#_Pred))
+// Special variant for std::merge, std::includes, std::set_*
+#define __glibcxx_check_sorted_set(_First1,_Last1,_First2) \
+__glibcxx_check_valid_range(_First1,_Last1); \
+_GLIBCXX_DEBUG_VERIFY( \
+ __gnu_debug::__check_sorted_set(_First1, _Last1, _First2), \
+ _M_message(__gnu_debug::__msg_unsorted) \
+ ._M_iterator(_First1, #_First1) \
+ ._M_iterator(_Last1, #_Last1))
+
+// Likewise with a _Pred.
+#define __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred) \
+__glibcxx_check_valid_range(_First1,_Last1); \
+_GLIBCXX_DEBUG_VERIFY( \
+ __gnu_debug::__check_sorted_set(_First1, _Last1, _First2, _Pred), \
+ _M_message(__gnu_debug::__msg_unsorted_pred) \
+ ._M_iterator(_First1, #_First1) \
+ ._M_iterator(_Last1, #_Last1) \
+ ._M_string(#_Pred))
+
/** Verify that the iterator range [_First, _Last) is partitioned
w.r.t. the value _Value. */
#define __glibcxx_check_partitioned_lower(_First,_Last,_Value) \
Index: include/debug/debug.h
===================================================================
--- include/debug/debug.h (revision 131452)
+++ include/debug/debug.h (working copy)
@@ -63,6 +63,8 @@
# define __glibcxx_requires_valid_range(_First,_Last)
# define __glibcxx_requires_sorted(_First,_Last)
# define __glibcxx_requires_sorted_pred(_First,_Last,_Pred)
+# define __glibcxx_requires_sorted_set(_First1,_Last1,_First2)
+# define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_Pred)
# define __glibcxx_requires_partitioned_lower(_First,_Last,_Value)
# define __glibcxx_requires_partitioned_upper(_First,_Last,_Value)
# define __glibcxx_requires_partitioned_lower_pred(_First,_Last,_Value,_Pred)
@@ -119,6 +121,10 @@
__glibcxx_check_sorted(_First,_Last)
# define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \
__glibcxx_check_sorted_pred(_First,_Last,_Pred)
+# define __glibcxx_requires_sorted_set(_First1,_Last1,_First2) \
+ __glibcxx_check_sorted_set(_First1,_Last1,_First2)
+# define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_Pred) \
+ __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred)
# define __glibcxx_requires_partitioned_lower(_First,_Last,_Value) \
__glibcxx_check_partitioned_lower(_First,_Last,_Value)
# define __glibcxx_requires_partitioned_upper(_First,_Last,_Value) \
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 131452)
+++ include/bits/stl_algo.h (working copy)
@@ -3291,8 +3291,8 @@
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted(__first1, __last1);
- __glibcxx_requires_sorted(__first2, __last2);
+ __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+ __glibcxx_requires_sorted_set(__first2, __last2, __first1);
while (__first1 != __last1 && __first2 != __last2)
if (*__first2 < *__first1)
@@ -3328,7 +3328,8 @@
typename _Compare>
bool
includes(_InputIterator1 __first1, _InputIterator1 __last1,
- _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _Compare __comp)
{
typedef typename iterator_traits<_InputIterator1>::value_type
_ValueType1;
@@ -3342,8 +3343,8 @@
_ValueType1, _ValueType2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
- __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first2, *__first1))
@@ -5029,8 +5030,8 @@
__glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
_ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted(__first1, __last1);
- __glibcxx_requires_sorted(__first2, __last2);
+ __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+ __glibcxx_requires_sorted_set(__first2, __last2, __first1);
while (__first1 != __last1 && __first2 != __last2)
{
@@ -5092,8 +5093,8 @@
_ValueType2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
- __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
{
@@ -5237,8 +5238,8 @@
_ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted(__first1, __last1);
- __glibcxx_requires_sorted(__first2, __last2);
+ __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+ __glibcxx_requires_sorted_set(__first2, __last2, __first1);
while (__first1 != __last1 && __first2 != __last2)
{
@@ -5305,8 +5306,8 @@
_ValueType1, _ValueType2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
- __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
{
@@ -5367,8 +5368,8 @@
_ValueType1>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted(__first1, __last1);
- __glibcxx_requires_sorted(__first2, __last2);
+ __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+ __glibcxx_requires_sorted_set(__first2, __last2, __first1);
while (__first1 != __last1 && __first2 != __last2)
if (*__first1 < *__first2)
@@ -5425,8 +5426,8 @@
_ValueType1, _ValueType2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
- __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2))
@@ -5480,8 +5481,8 @@
_ValueType1>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted(__first1, __last1);
- __glibcxx_requires_sorted(__first2, __last2);
+ __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+ __glibcxx_requires_sorted_set(__first2, __last2, __first1);
while (__first1 != __last1 && __first2 != __last2)
if (*__first1 < *__first2)
@@ -5542,8 +5543,8 @@
_ValueType1, _ValueType2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
- __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2))
@@ -5599,8 +5600,8 @@
_ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted(__first1, __last1);
- __glibcxx_requires_sorted(__first2, __last2);
+ __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+ __glibcxx_requires_sorted_set(__first2, __last2, __first1);
while (__first1 != __last1 && __first2 != __last2)
if (*__first1 < *__first2)
@@ -5667,8 +5668,8 @@
_ValueType1, _ValueType2>)
__glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
_ValueType2, _ValueType1>)
- __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
- __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+ __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first1, *__first2))