This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Add irreflexive comparison debug check


Hi

    Here is a patch to add irreflexive debug check.

    Standard algos signatures are such that there is no guaranty that
the operator < or predicate to compare the iterator value type will
exist. So I had to check if the call is valid using C++11 features
declval and decltype.

    * 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.
    * include/debug/debug.h (__glibcxx_requires_irreflexive,
    __glibcxx_requires_irreflexive_pred): New macros, use latter.
    * 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.

Ok to commit ?

FranÃois

diff --git libstdc++-v3/include/bits/stl_algo.h libstdc++-v3/include/bits/stl_algo.h
index 93e834a..89f5d36 100644
--- libstdc++-v3/include/bits/stl_algo.h
+++ libstdc++-v3/include/bits/stl_algo.h
@@ -1750,6 +1750,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				                     _OutputValueType>)
       __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
       __glibcxx_requires_valid_range(__result_first, __result_last);
 
       return std::__partial_sort_copy(__first, __last,
@@ -1803,6 +1804,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _OutputValueType, _OutputValueType>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
       __glibcxx_requires_valid_range(__result_first, __result_last);
 
       return std::__partial_sort_copy(__first, __last,
@@ -2027,6 +2029,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				  _ValueType, _Tp>)
       __glibcxx_requires_partitioned_lower_pred(__first, __last,
 						__val, __comp);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__lower_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_comp_val(__comp));
@@ -2082,6 +2085,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
       __glibcxx_requires_partitioned_upper(__first, __last, __val);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__upper_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__val_less_iter());
@@ -2116,6 +2120,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 				  _Tp, _ValueType>)
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__upper_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__val_comp_iter(__comp));
@@ -2189,7 +2194,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
       __glibcxx_requires_partitioned_lower(__first, __last, __val);
-      __glibcxx_requires_partitioned_upper(__first, __last, __val);      
+      __glibcxx_requires_partitioned_upper(__first, __last, __val);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__equal_range(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_less_val(),
@@ -2231,6 +2237,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 						__val, __comp);
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__equal_range(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_comp_val(__comp),
@@ -2262,6 +2269,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
       __glibcxx_requires_partitioned_lower(__first, __last, __val);
       __glibcxx_requires_partitioned_upper(__first, __last, __val);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       _ForwardIterator __i
 	= std::__lower_bound(__first, __last, __val,
@@ -2300,6 +2308,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 						__val, __comp);
       __glibcxx_requires_partitioned_upper_pred(__first, __last,
 						__val, __comp);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       _ForwardIterator __i
 	= std::__lower_bound(__first, __last, __val,
@@ -2594,6 +2603,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_sorted(__first, __middle);
       __glibcxx_requires_sorted(__middle, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       std::__inplace_merge(__first, __middle, __last,
 			   __gnu_cxx::__ops::__iter_less_iter());
@@ -2636,6 +2646,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_sorted_pred(__first, __middle, __comp);
       __glibcxx_requires_sorted_pred(__middle, __last, __comp);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       std::__inplace_merge(__first, __middle, __last,
 			   __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -2847,6 +2858,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return std::__includes(__first1, __last1, __first2, __last2,
 			     __gnu_cxx::__ops::__iter_less_iter());
@@ -2891,6 +2904,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return std::__includes(__first1, __last1, __first2, __last2,
 			     __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -2966,6 +2981,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__next_permutation
 	(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
@@ -2998,6 +3014,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_BidirectionalIterator>::value_type,
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__next_permutation
 	(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -3064,6 +3081,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__prev_permutation(__first, __last,
 				     __gnu_cxx::__ops::__iter_less_iter());
@@ -3096,6 +3114,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_BidirectionalIterator>::value_type,
 	    typename iterator_traits<_BidirectionalIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__prev_permutation(__first, __last,
 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -3258,6 +3277,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__is_sorted_until(__first, __last,
 				    __gnu_cxx::__ops::__iter_less_iter());
@@ -3283,6 +3303,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_ForwardIterator>::value_type,
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__is_sorted_until(__first, __last,
 				    __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -3407,6 +3428,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__minmax_element(__first, __last,
 				   __gnu_cxx::__ops::__iter_less_iter());
@@ -3436,6 +3458,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    typename iterator_traits<_ForwardIterator>::value_type,
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return std::__minmax_element(__first, __last,
 				   __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -4556,6 +4579,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       std::__partial_sort(__first, __middle, __last,
 			  __gnu_cxx::__ops::__iter_less_iter());
@@ -4595,6 +4619,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       std::__partial_sort(__first, __middle, __last,
 			  __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -4627,6 +4652,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __nth);
       __glibcxx_requires_valid_range(__nth, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       if (__first == __last || __nth == __last)
 	return;
@@ -4666,6 +4692,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __nth);
       __glibcxx_requires_valid_range(__nth, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       if (__first == __last || __nth == __last)
 	return;
@@ -4699,6 +4726,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
     }
@@ -4730,6 +4758,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_RandomAccessIterator>::value_type,
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
     }
@@ -4797,6 +4826,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)	
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return _GLIBCXX_STD_A::__merge(__first1, __last1,
 				     __first2, __last2, __result,
@@ -4845,6 +4876,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return _GLIBCXX_STD_A::__merge(__first1, __last1,
 				__first2, __last2, __result,
@@ -4898,6 +4931,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       _GLIBCXX_STD_A::__stable_sort(__first, __last,
 				    __gnu_cxx::__ops::__iter_less_iter());
@@ -4933,6 +4967,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_RandomAccessIterator>::value_type,
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       _GLIBCXX_STD_A::__stable_sort(__first, __last,
 				    __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -5010,6 +5045,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
 				__first2, __last2, __result,
@@ -5057,6 +5094,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return _GLIBCXX_STD_A::__set_union(__first1, __last1,
 				__first2, __last2, __result,
@@ -5123,6 +5162,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
 				     __first2, __last2, __result,
@@ -5169,6 +5210,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
 				__first2, __last2, __result,
@@ -5239,6 +5282,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)	
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
 				   __first2, __last2, __result,
@@ -5287,6 +5332,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
 				   __first2, __last2, __result,
@@ -5365,6 +5412,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)	
       __glibcxx_requires_sorted_set(__first1, __last1, __first2);
       __glibcxx_requires_sorted_set(__first2, __last2, __first1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
 					__first2, __last2, __result,
@@ -5414,6 +5463,8 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_InputIterator1>::value_type>)
       __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
       __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
 				__first2, __last2, __result,
@@ -5452,6 +5503,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return _GLIBCXX_STD_A::__min_element(__first, __last,
 				__gnu_cxx::__ops::__iter_less_iter());
@@ -5478,6 +5530,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_ForwardIterator>::value_type,
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return _GLIBCXX_STD_A::__min_element(__first, __last,
 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -5514,6 +5567,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return _GLIBCXX_STD_A::__max_element(__first, __last,
 				__gnu_cxx::__ops::__iter_less_iter());
@@ -5540,6 +5594,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	    typename iterator_traits<_ForwardIterator>::value_type,
 	    typename iterator_traits<_ForwardIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return _GLIBCXX_STD_A::__max_element(__first, __last,
 				__gnu_cxx::__ops::__iter_comp_iter(__comp));
diff --git libstdc++-v3/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
index 75a1516..9c03e85 100644
--- libstdc++-v3/include/bits/stl_algobase.h
+++ libstdc++-v3/include/bits/stl_algobase.h
@@ -985,6 +985,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanOpConcept<
 	    typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
       __glibcxx_requires_partitioned_lower(__first, __last, __val);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return std::__lower_bound(__first, __last, __val,
 				__gnu_cxx::__ops::__iter_less_val());
@@ -1209,7 +1210,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
       __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_irreflexive(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
+      __glibcxx_requires_irreflexive(__first2, __last2);
 
       return std::__lexicographical_compare_aux(std::__niter_base(__first1),
 						std::__niter_base(__last1),
@@ -1239,7 +1242,9 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_function_requires(_InputIteratorConcept<_II1>)
       __glibcxx_function_requires(_InputIteratorConcept<_II2>)
       __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_irreflexive_pred(__first1, __last1, __comp);
       __glibcxx_requires_valid_range(__first2, __last2);
+      __glibcxx_requires_irreflexive_pred(__first2, __last2, __comp);
 
       return std::__lexicographical_compare_impl
 	(__first1, __last1, __first2, __last2,
diff --git libstdc++-v3/include/bits/stl_heap.h libstdc++-v3/include/bits/stl_heap.h
index 3ab37c7..e13b6be 100644
--- libstdc++-v3/include/bits/stl_heap.h
+++ libstdc++-v3/include/bits/stl_heap.h
@@ -159,6 +159,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _RandomAccessIterator>)
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
       __glibcxx_requires_heap(__first, __last - 1);
 
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
@@ -193,6 +194,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
       __glibcxx_requires_heap_pred(__first, __last - 1, __comp);
 
       _ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
@@ -271,6 +273,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
       __glibcxx_requires_non_empty_range(__first, __last);
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
       __glibcxx_requires_heap(__first, __last);
 
       if (__last - __first > 1)
@@ -301,6 +304,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
       __glibcxx_requires_non_empty_range(__first, __last);
       __glibcxx_requires_heap_pred(__first, __last, __comp);
 
@@ -356,6 +360,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       std::__make_heap(__first, __last,
 		       __gnu_cxx::__ops::__iter_less_iter());
@@ -380,6 +385,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       std::__make_heap(__first, __last,
 		       __gnu_cxx::__ops::__iter_comp_iter(__comp));
@@ -415,6 +421,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
       __glibcxx_requires_heap(__first, __last);
 
       std::__sort_heap(__first, __last,
@@ -440,6 +447,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
       __glibcxx_requires_heap_pred(__first, __last, __comp);
 
       std::__sort_heap(__first, __last,
@@ -467,6 +475,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_LessThanComparableConcept<
 	    typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive(__first, __last);
 
       return __first + 
 	std::__is_heap_until(__first, std::distance(__first, __last),
@@ -493,6 +502,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_function_requires(_RandomAccessIteratorConcept<
 	    _RandomAccessIterator>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       return __first
 	+ std::__is_heap_until(__first, std::distance(__first, __last),
diff --git libstdc++-v3/include/debug/debug.h libstdc++-v3/include/debug/debug.h
index b6623e6..64ae1ac 100644
--- libstdc++-v3/include/debug/debug.h
+++ libstdc++-v3/include/debug/debug.h
@@ -77,41 +77,47 @@ 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_irreflexive_pred(_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_irreflexive_pred(_First,_Last,_Pred)	\
+  __glibcxx_check_irreflexive_pred(_First,_Last,_Pred)
 
 # include <debug/functions.h>
 
diff --git libstdc++-v3/include/debug/formatter.h libstdc++-v3/include/debug/formatter.h
index 56ee807..9fc23c8 100644
--- libstdc++-v3/include/debug/formatter.h
+++ 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 libstdc++-v3/include/debug/functions.h libstdc++-v3/include/debug/functions.h
index a9f234b..023758f 100644
--- libstdc++-v3/include/debug/functions.h
+++ libstdc++-v3/include/debug/functions.h
@@ -445,6 +445,61 @@ namespace __gnu_debug
       return __first == __last;
     }
 
+  struct _Irreflexive_checker
+  {
+#if __cplusplus >= 201103L
+    template<typename _It>
+      using __it_ref_t = typename std::iterator_traits<_It>::reference;
+
+    template<typename _It,
+	     typename = decltype(
+	std::declval<__it_ref_t<_It> >() < std::declval<__it_ref_t<_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>()(
+	std::declval<__it_ref_t<_It> >(), std::declval<__it_ref_t<_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; }
+#else
+    // Can't check if operator is available so just consider it is valid.
+    template<typename _It>
+      static bool
+      _S_is_valid(_It)
+      { return true; }
+
+    // Likewise for predicate.
+    template<typename _It, typename _Pred>
+      static bool
+      _S_is_valid_pred(_It, _Pred)
+      { return true; }
+#endif
+  };
+
+  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); }
 } // namespace __gnu_debug
 
 #endif
diff --git libstdc++-v3/include/debug/macros.h libstdc++-v3/include/debug/macros.h
index a4c2649..39cb0d6 100644
--- libstdc++-v3/include/debug/macros.h
+++ libstdc++-v3/include/debug/macros.h
@@ -362,4 +362,18 @@ _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					\
+			|| __gnu_debug::__is_irreflexive(_First),	\
+			_M_message(__gnu_debug::__msg_irreflexive_ordering) \
+			._M_iterator_value_type(_First, "< operator type"))
+
+#define __glibcxx_check_irreflexive_pred(_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"))
+
 #endif
diff --git libstdc++-v3/src/c++11/debug.cc libstdc++-v3/src/c++11/debug.cc
index f60e31f..61acf21 100644
--- libstdc++-v3/src/c++11/debug.cc
+++ libstdc++-v3/src/c++11/debug.cc
@@ -185,7 +185,8 @@ namespace __gnu_debug
     "load factor shall be positive",
     "allocators must be equal",
     "attempt to insert with an iterator range [%1.name;, %2.name;) from this"
-    " container"
+    " container",
+    "comparison doesn't meet irreflexive requirements, assert(!(a < a))"
   };
 
   void
diff --git libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc
new file mode 100644
index 0000000..8a5e71e
--- /dev/null
+++ libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc
@@ -0,0 +1,70 @@
+// Copyright (C) 2010-2015 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+//
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+//
+// { dg-options "-std=gnu++11" }
+// { dg-require-debug-mode "" }
+// { dg-do run { xfail *-*-* } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  int _i;
+};
+
+bool
+operator<(A a, int i)
+{ return a._i < i; }
+
+bool
+operator<(int i, A a)
+{ return i < a._i; }
+
+void test01()
+{
+  bool test __attribute__((unused)) = true;
+
+  A as[] { 0, 1, 2, 3 };
+  int is[] { 0, 1, 2, 3 };
+  VERIFY( !std::lexicographical_compare(as, as + 4, is, is + 4) );
+}
+
+bool
+bad_lower(int lhs, int rhs)
+{
+  if (lhs == 0)
+    return true;
+
+  return lhs < rhs;
+}
+
+void test02()
+{
+  int is[] { 0, 1, 2, 3 };
+  std::lexicographical_compare(is, is + 4, is, is + 4, bad_lower);
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
+}

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]