re PR libstdc++/60519 (Debug mode should check comparators for irreflexivity)

2015-08-24  François Dumont  <fdumont@gcc.gnu.org>

	PR libstdc++/60519
	* include/debug/formatter.h (_Debug_msg_id::__msg_irreflexive_ordering):
	New enum entry.
	* include/debug/functions.h (_Irreflexive_checker): New.
	(__is_irreflexive, __is_irreflexive_pred): New.
	* include/debug/macros.h
	(__glibcxx_check_irreflexive, __glibcxx_check_irreflexive_pred): New
	macros.
	(__glibcxx_check_irreflexive2, __glibcxx_check_irreflexive_pred2): New
	macros limited to post-C++11 mode.
	* include/debug/debug.h
	(__glibcxx_requires_irreflexive, __glibcxx_requires_irreflexive_pred):
	New macros, use latter.
	(__glibcxx_requires_irreflexive2, __glibcxx_requires_irreflexive_pred2):
	Likewise.
	* include/bits/stl_algo.h
	(partial_sort_copy): Add irreflexive debug check.
	(partial_sort_copy): Likewise.
	(lower_bound): Likewise.
	(upper_bound): Likewise.
	(equal_range): Likewise.
	(binary_search): Likewise.
	(inplace_merge): Likewise.
	(includes): Likewise.
	(next_permutation): Likewise.
	(prev_permutation): Likewise.
	(is_sorted_until): Likewise.
	(minmax_element): Likewise.
	(partial_sort): Likewise.
	(nth_element): Likewise.
	(sort): Likewise.
	(merge): Likewise.
	(stable_sort): Likewise.
	(set_union): Likewise.
	(set_intersection): Likewise.
	(set_difference): Likewise.
	(set_symmetric_difference): Likewise.
	(min_element): Likewise.
	(max_element): Likewise.
	* include/bits/stl_algobase.h
	(lower_bound): Likewise.
	(lexicographical_compare): Likewise.
	* include/bits/stl_heap.h
	(push_heap): Likewise.
	(pop_heap): Likewise.
	(make_heap): Likewise.
	(sort_heap): Likewise.
	(is_heap_until): Likewise.
	* testsuite/25_algorithms/lexicographical_compare/debug/
	irreflexive_neg.cc: New.
	* testsuite/25_algorithms/lower_bound/debug/irreflexive.cc: New.
	* testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc:
	New.

From-SVN: r227189

4 files changed, 110 insertions, 21 deletions

diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index b6623e6..6b52b0a 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -77,41 +77,53 @@ namespace __gnu_debug
 # define __glibcxx_requires_string(_String)
 # define __glibcxx_requires_string_len(_String,_Len)
 # define __glibcxx_requires_subscript(_N)
+# define __glibcxx_requires_irreflexive(_First,_Last)
+# define __glibcxx_requires_irreflexive2(_First,_Last)
+# define __glibcxx_requires_irreflexive_pred(_First,_Last,_Pred)
+# define __glibcxx_requires_irreflexive_pred2(_First,_Last,_Pred)
 
 #else
 
 # include <debug/macros.h>
 
 # define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg)
-# define __glibcxx_requires_valid_range(_First,_Last) \
-     __glibcxx_check_valid_range(_First,_Last)
-# define __glibcxx_requires_non_empty_range(_First,_Last) \
-     __glibcxx_check_non_empty_range(_First,_Last)
-# define __glibcxx_requires_sorted(_First,_Last) \
-     __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_valid_range(_First,_Last)	\
+  __glibcxx_check_valid_range(_First,_Last)
+# define __glibcxx_requires_non_empty_range(_First,_Last)	\
+  __glibcxx_check_non_empty_range(_First,_Last)
+# define __glibcxx_requires_sorted(_First,_Last)	\
+  __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)
+  __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred)
 # define __glibcxx_requires_partitioned_lower(_First,_Last,_Value)	\
-     __glibcxx_check_partitioned_lower(_First,_Last,_Value)
+  __glibcxx_check_partitioned_lower(_First,_Last,_Value)
 # define __glibcxx_requires_partitioned_upper(_First,_Last,_Value)	\
-     __glibcxx_check_partitioned_upper(_First,_Last,_Value)
+  __glibcxx_check_partitioned_upper(_First,_Last,_Value)
 # define __glibcxx_requires_partitioned_lower_pred(_First,_Last,_Value,_Pred) \
-     __glibcxx_check_partitioned_lower_pred(_First,_Last,_Value,_Pred)
+  __glibcxx_check_partitioned_lower_pred(_First,_Last,_Value,_Pred)
 # define __glibcxx_requires_partitioned_upper_pred(_First,_Last,_Value,_Pred) \
-     __glibcxx_check_partitioned_upper_pred(_First,_Last,_Value,_Pred)
-# define __glibcxx_requires_heap(_First,_Last) \
-     __glibcxx_check_heap(_First,_Last)
-# define __glibcxx_requires_heap_pred(_First,_Last,_Pred) \
-     __glibcxx_check_heap_pred(_First,_Last,_Pred)
+  __glibcxx_check_partitioned_upper_pred(_First,_Last,_Value,_Pred)
+# define __glibcxx_requires_heap(_First,_Last)	\
+  __glibcxx_check_heap(_First,_Last)
+# define __glibcxx_requires_heap_pred(_First,_Last,_Pred)	\
+  __glibcxx_check_heap_pred(_First,_Last,_Pred)
 # define __glibcxx_requires_nonempty() __glibcxx_check_nonempty()
 # define __glibcxx_requires_string(_String) __glibcxx_check_string(_String)
 # define __glibcxx_requires_string_len(_String,_Len)	\
-     __glibcxx_check_string_len(_String,_Len)
+  __glibcxx_check_string_len(_String,_Len)
 # define __glibcxx_requires_subscript(_N) __glibcxx_check_subscript(_N)
+# define __glibcxx_requires_irreflexive(_First,_Last)	\
+  __glibcxx_check_irreflexive(_First,_Last)
+# define __glibcxx_requires_irreflexive2(_First,_Last)	\
+  __glibcxx_check_irreflexive2(_First,_Last)
+# define __glibcxx_requires_irreflexive_pred(_First,_Last,_Pred)	\
+  __glibcxx_check_irreflexive_pred(_First,_Last,_Pred)
+# define __glibcxx_requires_irreflexive_pred2(_First,_Last,_Pred)	\
+  __glibcxx_check_irreflexive_pred2(_First,_Last,_Pred)
 
 # include <debug/functions.h>
 
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
index 56ee807..9fc23c8 100644
--- a/libstdc++-v3/include/debug/formatter.h
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -126,7 +126,8 @@ namespace __gnu_debug
     __msg_valid_load_factor,
     // others
     __msg_equal_allocs,
-    __msg_insert_range_from_self
+    __msg_insert_range_from_self,
+    __msg_irreflexive_ordering
   };
 
   class _Error_formatter
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index a9f234b..218092a 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -445,6 +445,49 @@ namespace __gnu_debug
       return __first == __last;
     }
 
+#if __cplusplus >= 201103L
+  struct _Irreflexive_checker
+  {
+    template<typename _It>
+      static typename std::iterator_traits<_It>::reference
+      __deref();
+
+    template<typename _It,
+	     typename = decltype(__deref<_It>() < __deref<_It>())>
+      static bool
+      _S_is_valid(_It __it)
+      { return !(*__it < *__it); }
+
+    // Fallback method if operator doesn't exist.
+    template<typename... _Args>
+      static bool
+      _S_is_valid(_Args...)
+      { return true; }
+
+    template<typename _It, typename _Pred, typename
+	= decltype(std::declval<_Pred>()(__deref<_It>(), __deref<_It>()))>
+      static bool
+      _S_is_valid_pred(_It __it, _Pred __pred)
+      { return !__pred(*__it, *__it); }
+
+    // Fallback method if predicate can't be invoked.
+    template<typename... _Args>
+      static bool
+      _S_is_valid_pred(_Args...)
+      { return true; }
+  };
+
+  template<typename _Iterator>
+    inline bool
+    __is_irreflexive(_Iterator __it)
+    { return _Irreflexive_checker::_S_is_valid(__it); }
+
+  template<typename _Iterator, typename _Pred>
+    inline bool
+    __is_irreflexive_pred(_Iterator __it, _Pred __pred)
+    { return _Irreflexive_checker::_S_is_valid_pred(__it, __pred); }
+#endif
+
 } // namespace __gnu_debug
 
 #endif
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index a4c2649..c636663 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -362,4 +362,37 @@ _GLIBCXX_DEBUG_VERIFY(_This.get_allocator() == _Other.get_allocator(),	\
 #define __glibcxx_check_string_len(_String,_Len) \
   _GLIBCXX_DEBUG_PEDASSERT(_String != 0 || _Len == 0)
 
+// Verify that a predicate is irreflexive
+#define __glibcxx_check_irreflexive(_First,_Last)			\
+  _GLIBCXX_DEBUG_VERIFY(_First == _Last || !(*_First < *_First),	\
+			_M_message(__gnu_debug::__msg_irreflexive_ordering) \
+			._M_iterator_value_type(_First, "< operator type"))
+
+#if __cplusplus >= 201103L
+# define __glibcxx_check_irreflexive2(_First,_Last)			\
+  _GLIBCXX_DEBUG_VERIFY(_First == _Last					\
+			|| __gnu_debug::__is_irreflexive(_First),	\
+			_M_message(__gnu_debug::__msg_irreflexive_ordering) \
+			._M_iterator_value_type(_First, "< operator type"))
+#else
+# define __glibcxx_check_irreflexive2(_First,_Last)
+#endif
+
+#define __glibcxx_check_irreflexive_pred(_First,_Last,_Pred)		\
+  _GLIBCXX_DEBUG_VERIFY(_First == _Last	|| !_Pred(*_First, *_First),		\
+			_M_message(__gnu_debug::__msg_irreflexive_ordering) \
+			._M_instance(_Pred, "functor")			\
+			._M_iterator_value_type(_First, "ordered type"))
+
+#if __cplusplus >= 201103L
+# define __glibcxx_check_irreflexive_pred2(_First,_Last,_Pred)		\
+  _GLIBCXX_DEBUG_VERIFY(_First == _Last					\
+			||__gnu_debug::__is_irreflexive_pred(_First, _Pred), \
+			_M_message(__gnu_debug::__msg_irreflexive_ordering) \
+			._M_instance(_Pred, "functor")			\
+			._M_iterator_value_type(_First, "ordered type"))
+#else
+# define __glibcxx_check_irreflexive_pred2(_First,_Last,_Pred)
+#endif
+
 #endif