diff mbox

Add irreflexive comparison debug check

Message ID 55B932A7.2090806@gmail.com
State New
Headers show

Commit Message

François Dumont July 29, 2015, 8:08 p.m. UTC 
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

Comments

Jonathan Wakely July 30, 2015, 10:30 a.m. UTC | #1 
On 29/07/15 22:08 +0200, François Dumont wrote:
>Hi
>
>    Here is a patch to add irreflexive debug check.

Awesome!

You can add PR libstdc++/60519 to the changelog.


>    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.

Surely if someone calls an algorithm that requires a
StrictWeakOrdering then we know that it's valid to compare the value
types using the comparison implied by that particular call (either
operator< or the supplied predicate), and we should only be adding
this assertion to algorithms that require a StrictWeakOrdering.

Am I missing something?

Assuming those validity checks are needed ...

>+  struct _Irreflexive_checker
>+  {
>+#if __cplusplus >= 201103L
>+    template<typename _It>
>+      using __it_ref_t = typename std::iterator_traits<_It>::reference;

I'd just call this __ref_t, because where you use it the "it" part is
already implied by the template argument: __ref_t<_It>

Or you could add:

  template<typename _It>
    static typename std::iterator_traits<_It>::reference
    __deref();

and replace every std::declval<__it_ref_t<_It>>() with __deref<_It>()
which is much shorter.

>+    template<typename _It,
>+	     typename = decltype(
>+	std::declval<__it_ref_t<_It> >() < std::declval<__it_ref_t<_It> >())>

N.B. as this is only for C++11 and later there's no need for the
spaces before the closing >
François Dumont July 31, 2015, 7:49 p.m. UTC | #2 
On 30/07/2015 12:30, Jonathan Wakely wrote:
> On 29/07/15 22:08 +0200, François Dumont wrote:
>> Hi
>>
>>    Here is a patch to add irreflexive debug check.
>
> Awesome!
>
> You can add PR libstdc++/60519 to the changelog.
Sure.
>
>
>>    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.
>
> Surely if someone calls an algorithm that requires a
> StrictWeakOrdering then we know that it's valid to compare the value
> types using the comparison implied by that particular call (either
> operator< or the supplied predicate), and we should only be adding
> this assertion to algorithms that require a StrictWeakOrdering.
>
> Am I missing something?
    If you consider for instance lower_bound signature:

  template<typename _ForwardIterator, typename _Tp>
    inline _ForwardIterator
    lower_bound(_ForwardIterator __first, _ForwardIterator __last,
        const _Tp& __val)

    This algo require expressions *__first < __val or __val < *__first
to be well defined. But what the check is doing is *__first < *__first
that might not exist as the algo won't need it. The range [__first,
__last[ might have been sorted using another functor that we don't know
at the time of the call to lower_bound.

    There might be situations where the check will be useless but I
prefer to keep this debug check simple and so always go through the check.
>
> Assuming those validity checks are needed ...
>
>> +  struct _Irreflexive_checker
>> +  {
>> +#if __cplusplus >= 201103L
>> +    template<typename _It>
>> +      using __it_ref_t = typename std::iterator_traits<_It>::reference;
>
> I'd just call this __ref_t, because where you use it the "it" part is
> already implied by the template argument: __ref_t<_It>
>
> Or you could add:
>
>  template<typename _It>
>    static typename std::iterator_traits<_It>::reference
>    __deref();
>
> and replace every std::declval<__it_ref_t<_It>>() with __deref<_It>()
> which is much shorter.

Nice, I will use that.

>
>> +    template<typename _It,
>> +         typename = decltype(
>> +    std::declval<__it_ref_t<_It> >() < std::declval<__it_ref_t<_It>
>> >())>
>
> N.B. as this is only for C++11 and later there's no need for the
> spaces before the closing >

You read my mind on this one, thanks.

François
Jonathan Wakely Aug. 1, 2015, 12:25 a.m. UTC | #3 
On 31 July 2015 at 20:49, François Dumont wrote:
> On 30/07/2015 12:30, Jonathan Wakely wrote:
>> On 29/07/15 22:08 +0200, François Dumont wrote:
>>>    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.
>>
>> Surely if someone calls an algorithm that requires a
>> StrictWeakOrdering then we know that it's valid to compare the value
>> types using the comparison implied by that particular call (either
>> operator< or the supplied predicate), and we should only be adding
>> this assertion to algorithms that require a StrictWeakOrdering.
>>
>> Am I missing something?
>     If you consider for instance lower_bound signature:
>
>   template<typename _ForwardIterator, typename _Tp>
>     inline _ForwardIterator
>     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
>         const _Tp& __val)
>
>     This algo require expressions *__first < __val or __val < *__first
> to be well defined. But what the check is doing is *__first < *__first
> that might not exist as the algo won't need it. The range [__first,
> __last[ might have been sorted using another functor that we don't know
> at the time of the call to lower_bound.
>
>     There might be situations where the check will be useless but I
> prefer to keep this debug check simple and so always go through the check.

OK, but that is only true for some algos, it's not a problem for many
of them, e.g. std::sort we know that we only ever do homogeneous
comparisons, so we don't need the SFINAE tricks to detect if the
comparison is valid, and so could check for irreflexivity in C++03
mode.

So I think ideally we would be able to check for irreflexivity for
most algos in C++03, and for some (such as lower_bound) we would only
be able to check for C++11 and later.
diff mbox

Patch

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;
+}