re PR libstdc++/34730 (Legal program doesn't compile with -D_GLIBCXX_DEBUG)

2008-01-12  Paolo Carlini  <pcarlini@suse.de>

	PR libstdc++/34730
	* include/debug/functions.h (__check_sorted_set,
	__check_sorted_set_aux): Add.
	(__check_sorted): Check StrictWeakOrdering.
	* include/debug/macros.h (__glibcxx_check_strict_weak_ordering,
	__glibcxx_check_strict_weak_ordering_pred): Remove.
	(__glibcxx_check_sorted, __glibcxx_check_sorted_pred): Adjust.
	(__glibcxx_check_sorted_set, __glibcxx_check_sorted_set_pred): Add.
	* include/debug/debug.h (__glibcxx_requires_sorted_set,
	__glibcxx_requires_sorted_set_pred): Add.
	* include/bits/stl_algo.h (merge, includes, set_union,
	set_intersection, set_difference, set_symmetric_difference):
	Adjust, use __glibcxx_requires_sorted_set* instead. 
	* testsuite/25_algorithms/set_intersection/34730.cc: New.

From-SVN: r131500

4 files changed, 137 insertions, 50 deletions

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index b81a4a3..4c65e11 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -3034,15 +3034,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       while (__last - __first >= __two_step)
 	{
 	  __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size,
-				__first + __step_size, __first + __two_step,
-				__result);
+					   __first + __step_size,
+					   __first + __two_step,
+					   __result);
 	  __first += __two_step;
 	}
 
       __step_size = std::min(_Distance(__last - __first), __step_size);
       _GLIBCXX_STD_P::merge(__first, __first + __step_size, 
 			    __first + __step_size, __last,
-		 __result);
+			    __result);
     }
 
   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
@@ -3291,8 +3292,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __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 +3329,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	   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 +3344,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 				  _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 +5031,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
       __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 +5094,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5239,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5307,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5369,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5427,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5482,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5544,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5601,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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 +5669,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _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))
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index 32f96a3..97d6824 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -1,6 +1,6 @@
 // Debugging support implementation -*- C++ -*-
 
-// Copyright (C) 2003, 2004, 2005, 2006, 2007
+// 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
@@ -63,6 +63,8 @@ namespace __gnu_debug
 # 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 @@ namespace std
      __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)	\
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index 15c2154..7e7562a 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -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
@@ -205,10 +205,9 @@ namespace __gnu_debug
         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 @@ namespace __gnu_debug
         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;
     }
@@ -247,6 +245,11 @@ namespace __gnu_debug
     {
       typedef typename std::iterator_traits<_InputIterator>::iterator_category
         _Category;
+
+      // Verify that the < operator for elements in the sequence is a
+      // StrictWeakOrdering by checking that it is irreflexive.
+      _GLIBCXX_DEBUG_ASSERT(__first == __last || !(*__first < *__first));
+
       return __check_sorted_aux(__first, __last, _Category());
     }
 
@@ -257,10 +260,80 @@ namespace __gnu_debug
     {
       typedef typename std::iterator_traits<_InputIterator>::iterator_category
         _Category;
-      return __check_sorted_aux(__first, __last, __pred,
-					     _Category());
+
+      // Verify that the predicate is StrictWeakOrdering by checking that it
+      // is irreflexive.
+      _GLIBCXX_DEBUG_ASSERT(__first == __last || !__pred(*__first, *__first));
+
+      return __check_sorted_aux(__first, __last, __pred, _Category());
+    }
+
+  template<typename _InputIterator1, typename _InputIterator2>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1& __first,
+			   const _InputIterator1& __last,
+			   const _InputIterator2&, std::__true_type)
+    { return __check_sorted(__first, __last); }
+
+  template<typename _InputIterator1, typename _InputIterator2>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1&,
+			   const _InputIterator1&,
+			   const _InputIterator2&, std::__false_type)
+    { return true; }
+
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _Predicate>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1& __first,
+			   const _InputIterator1& __last,
+			   const _InputIterator2&, _Predicate __pred,
+			   std::__true_type)
+    { return __check_sorted(__first, __last, __pred); }
+
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _Predicate>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1&,
+			   const _InputIterator1&,
+			   const _InputIterator2&, _Predicate,
+			   std::__false_type)
+    { return true; }
+
+  // ... special variant used in std::merge, std::includes, std::set_*.
+  template<typename _InputIterator1, typename _InputIterator2>
+    inline bool
+    __check_sorted_set(const _InputIterator1& __first,
+		       const _InputIterator1& __last,
+		       const _InputIterator2&)
+    {
+      typedef typename std::iterator_traits<_InputIterator1>::value_type
+	_ValueType1;
+      typedef typename std::iterator_traits<_InputIterator2>::value_type
+	_ValueType2;
+
+      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
+	_SameType;
+      return __check_sorted_set_aux(__first, __last, _SameType());
     }
 
+  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>::value_type
+	_ValueType1;
+      typedef typename std::iterator_traits<_InputIterator2>::value_type
+	_ValueType2;
+
+      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
+	_SameType;
+      return __check_sorted_set_aux(__first, __last, __pred, _SameType());
+   }
+
   // _GLIBCXX_RESOLVE_LIB_DEFECTS
   // 270. Binary search requirements overly strict
   // Determine if a sequence is partitioned w.r.t. this element.
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index 4f4a0cc..6b7b2b2 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -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
@@ -140,21 +140,9 @@ _GLIBCXX_DEBUG_VERIFY(! this->empty(),					\
 		      _M_message(__gnu_debug::__msg_empty)	        \
                       ._M_sequence(*this, "this"))
 
-// Verify that the < operator for elements in the sequence is a
-// StrictWeakOrdering by checking that it is irreflexive.
-#define __glibcxx_check_strict_weak_ordering(_First,_Last)	\
-_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First))
-
-// Verify that the predicate is StrictWeakOrdering by checking that it
-// is irreflexive.
-#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred)	\
-_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First))
-
-
 // Verify that the iterator range [_First, _Last) is sorted
 #define __glibcxx_check_sorted(_First,_Last)				\
 __glibcxx_check_valid_range(_First,_Last);				\
-__glibcxx_check_strict_weak_ordering(_First,_Last);			\
 _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last),	\
 		      _M_message(__gnu_debug::__msg_unsorted)	        \
                       ._M_iterator(_First, #_First)			\
@@ -164,13 +152,31 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last),	\
     predicate _Pred. */
 #define __glibcxx_check_sorted_pred(_First,_Last,_Pred)			\
 __glibcxx_check_valid_range(_First,_Last);				\
-__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred);	        \
 _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last, _Pred), \
 		      _M_message(__gnu_debug::__msg_unsorted_pred)      \
                       ._M_iterator(_First, #_First)			\
 		      ._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)		\