This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
New antisymmetrical debug check
- From: FranÃois Dumont <frs dot dumont at gmail dot com>
- To: "libstdc++ at gcc dot gnu dot org" <libstdc++ at gcc dot gnu dot org>
- Date: Thu, 22 Oct 2015 21:18:44 +0200
- Subject: New antisymmetrical debug check
- Authentication-results: sourceware.org; auth=none
Hi
I leveraged on predefined operators to inject a new debug check for
strict weak ordering operators. It checks that for a given functor f if
f(a, b) then !f(b, a). In terms of < operator: if (a < b) assert(!(b < a)).
I had to replace the generic functors like _Iter_comp_iter by more
explicit _Iter_less_iter where this check can take place. As algos can
be used with different iterator types those checks are only performed in
C++11 and after to make sure that b < a is a valid expression.
2015-10-30 FranÃois Dumont <fdumont@gcc.gnu.org>
* include/bits/predefined_ops.h
(_Iter_less_iter): Add antisymmetrical check.
(_Iter_less_val): Likewise.
(_Val_less_iter): Likewise.
(_Iter_less_iter_comp): New.
(_Iter_comp_val): Delete.
(_Iter_comp_iter): Delete.
(_Iter_equal_to_iter_comp): New..
(_Iter_equal_to_val_comp): New.
(_Iter_less_val_comp): New.
(_Val_comp_iter): Delete.
(_Val_less_iter_comp): New.
(_Iter_comp_iter): Delete.
(_Iter_equals_to_comp): New.
(__iter_less_iter): New.
(__iter_comp_val): Delete.
(__iter_less_val): New.
(__val_comp_iter): Delete.
(__val_less_iter): New.
(__iter_equal_to_val()): Delete.
(__iter_comp_val): Delete.
(__iter_equal_to_val(_Iter_equal_to_iter)): New.
(__iter_comp_iter): Delete.
(__iter_equal_to_iter): New.
(__iter_comp_val): Delete.
(__iter_equal_to_val): New.
(__iter_less_val): New.
(__val_comp_iter): Delete.
(__val_less_iter): New.
(__iter_comp_iter): Delete.
(__iter_equals_iter): New.
(__iter_comp_val): Delete.
(__iter_equals_val): New.
(__iter_comp_iter): Delete.
(__iter_equals_iter): New.
* include/bits/stl_algo.h: Adapt.
* include/bits/stl_algobase.h: Adapt.
* include/bits/stl_heap.h: Adapt.
* include/debug/formatter.h (_Debug_msg_id): Add
__msg_antisymmetrical_ordering.
* src/c++11/debug.cc (_S_debug_messages): Add
__msg_antisymmetrical_ordering message.
* testsuite/25_algorithms/lower_bound/33613.cc: Add -std=gnu++11.
* testsuite/25_algorithms/lower_bound/
invalid_strict_weak_ordering_neg.cc: New.
Tested under Linux x86_64.
Ok to commit ?
FranÃois
diff --git a/libstdc++-v3/include/bits/predefined_ops.h b/libstdc++-v3/include/bits/predefined_ops.h
index 7178567..c283315 100644
--- a/libstdc++-v3/include/bits/predefined_ops.h
+++ b/libstdc++-v3/include/bits/predefined_ops.h
@@ -30,37 +30,174 @@
#ifndef _GLIBCXX_PREDEFINED_OPS_H
#define _GLIBCXX_PREDEFINED_OPS_H 1
+#if defined (_GLIBCXX_DEBUG) && (__cplusplus >= 201103L)
+# include <type_traits> // For declval
+# include <bits/stl_iterator_base_types.h>
+#endif
+
namespace __gnu_cxx
{
namespace __ops
{
+#if defined (_GLIBCXX_DEBUG) && (__cplusplus >= 201103L)
+ template<typename _It>
+ typename std::iterator_traits<_It>::reference
+ __deref();
+#endif
+
struct _Iter_less_iter
{
template<typename _Iterator1, typename _Iterator2>
_GLIBCXX14_CONSTEXPR
bool
operator()(_Iterator1 __it1, _Iterator2 __it2) const
- { return *__it1 < *__it2; }
+ {
+ if (*__it1 < *__it2)
+ {
+ __glibcxx_requires_cond(_M_reverse_check(__it1, __it2),
+ _M_message(__gnu_debug::__msg_antisymmetrical_ordering)
+ ._M_iterator_value_type(__it1, "lhs")
+ ._M_iterator_value_type(__it2, "rhs"));
+ return true;
+ }
+
+ return false;
+ }
+
+#if defined (_GLIBCXX_DEBUG)
+ private:
+# if __cplusplus >= 201103L
+ template<typename _It1, typename _It2,
+ typename = decltype(__deref<_It2>() < __deref<_It1>())>
+ _GLIBCXX14_CONSTEXPR
+ bool
+ _M_reverse_check(_It1 __it1, _It2 __it2) const
+ { return !(*__it2 < *__it1); }
+
+ template<typename... _Args>
+ _GLIBCXX14_CONSTEXPR
+ bool
+ _M_reverse_check(_Args...) const
+ { return true; }
+# else
+ template<typename _It1, typename _It2>
+ _GLIBCXX14_CONSTEXPR
+ bool
+ _M_reverse_check(_It1, _It2) const
+ { return true; }
+# endif
+#endif
};
+
_GLIBCXX14_CONSTEXPR
inline _Iter_less_iter
__iter_less_iter()
{ return _Iter_less_iter(); }
+ template<typename _Compare>
+ struct _Iter_less_iter_comp
+ {
+ _Compare _M_comp;
+
+ _GLIBCXX14_CONSTEXPR
+ _Iter_less_iter_comp(_Compare __comp)
+ : _M_comp(__comp)
+ { }
+
+ template<typename _Iterator1, typename _Iterator2>
+ _GLIBCXX14_CONSTEXPR
+ bool
+ operator()(_Iterator1 __it1, _Iterator2 __it2)
+ {
+ if (_M_comp(*__it1, *__it2))
+ {
+ __glibcxx_requires_cond(!_M_comp(*__it2, *__it1),
+ _M_message(__gnu_debug::__msg_antisymmetrical_ordering)
+ ._M_instance(_M_comp, "functor")
+ ._M_iterator_value_type(__it1, "lhs")
+ ._M_iterator_value_type(__it2, "rhs"));
+ return true;
+ }
+
+ return false;
+ }
+
+#if defined (_GLIBCXX_DEBUG)
+ private:
+# if __cplusplus >= 201103L
+ template<typename _It1, typename _It2, typename = decltype(
+ std::declval<_Compare>()(__deref<_It2>(), __deref<_It1>()))>
+ _GLIBCXX14_CONSTEXPR
+ bool
+ _M_reverse_check(_It1 __it1, _It2 __it2)
+ { return !_M_comp(*__it2, *__it1); }
+
+ template<typename... _Args>
+ _GLIBCXX14_CONSTEXPR
+ bool
+ _M_reverse_check(_Args...)
+ { return true; }
+# else
+ template<typename _It1, typename _It2>
+ bool
+ _M_reverse_check(_It1, _It2)
+ { return true; }
+# endif
+#endif
+ };
+
+ template<typename _Compare>
+ _GLIBCXX14_CONSTEXPR
+ inline _Iter_less_iter_comp<_Compare>
+ __iter_less_iter(_Compare __comp)
+ { return _Iter_less_iter_comp<_Compare>(__comp); }
+
struct _Iter_less_val
{
template<typename _Iterator, typename _Value>
bool
operator()(_Iterator __it, _Value& __val) const
- { return *__it < __val; }
- };
+ {
+ if (*__it < __val)
+ {
+ __glibcxx_requires_cond(_M_reverse_check(__it, __val),
+ _M_message(__gnu_debug::__msg_antisymmetrical_ordering)
+ ._M_iterator_value_type(__it, "lhs")
+ ._M_instance(__val, "rhs"));
+ return true;
+ }
+
+ return false;
+ }
+
+#if defined (_GLIBCXX_DEBUG)
+ private:
+# if __cplusplus >= 201103L
+ template<typename _It1, typename _Val1,
+ typename = decltype(std::declval<_Val1>() < __deref<_It1>())>
+ bool
+ _M_reverse_check(_It1 __it1, _Val1& __val1) const
+ { return !(__val1 < *__it1); }
+
+ template<typename... _Args>
+ bool
+ _M_reverse_check(_Args...) const
+ { return true; }
+# else
+ template<typename _It1, typename _Val1>
+ bool
+ _M_reverse_check(_It1, _Val1&) const
+ { return true; }
+# endif
+#endif
+ };
inline _Iter_less_val
__iter_less_val()
{ return _Iter_less_val(); }
inline _Iter_less_val
- __iter_comp_val(_Iter_less_iter)
+ __iter_less_val(_Iter_less_iter)
{ return _Iter_less_val(); }
struct _Val_less_iter
@@ -68,15 +205,47 @@ namespace __ops
template<typename _Value, typename _Iterator>
bool
operator()(_Value& __val, _Iterator __it) const
- { return __val < *__it; }
- };
+ {
+ if (__val < *__it)
+ {
+ __glibcxx_requires_cond(_M_reverse_check(__val, __it),
+ _M_message(__gnu_debug::__msg_antisymmetrical_ordering)
+ ._M_instance(__val, "lhs")
+ ._M_iterator_value_type(__it, "rhs"));
+ return true;
+ }
+
+ return false;
+ }
+
+#if defined (_GLIBCXX_DEBUG)
+ private:
+# if __cplusplus >= 201103L
+ template<typename _Val, typename _It,
+ typename = decltype(__deref<_It>() < std::declval<_Val>())>
+ bool
+ _M_reverse_check(_Val& __val, _It __it) const
+ { return !(*__it < __val); }
+
+ template<typename... _Args>
+ bool
+ _M_reverse_check(_Args...) const
+ { return true; }
+#else
+ template<typename _Val, typename _It>
+ bool
+ _M_reverse_check(_Val&, _It) const
+ { return true; }
+# endif
+#endif
+ };
inline _Val_less_iter
__val_less_iter()
{ return _Val_less_iter(); }
inline _Val_less_iter
- __val_comp_iter(_Iter_less_iter)
+ __val_less_iter(_Iter_less_iter)
{ return _Val_less_iter(); }
struct _Iter_equal_to_iter
@@ -100,41 +269,38 @@ namespace __ops
};
inline _Iter_equal_to_val
- __iter_equal_to_val()
- { return _Iter_equal_to_val(); }
-
- inline _Iter_equal_to_val
- __iter_comp_val(_Iter_equal_to_iter)
+ __iter_equal_to_val(_Iter_equal_to_iter)
{ return _Iter_equal_to_val(); }
template<typename _Compare>
- struct _Iter_comp_iter
+ struct _Iter_equal_to_iter_comp
{
_Compare _M_comp;
+
_GLIBCXX14_CONSTEXPR
- _Iter_comp_iter(_Compare __comp)
+ _Iter_equal_to_iter_comp(_Compare __comp)
: _M_comp(__comp)
{ }
template<typename _Iterator1, typename _Iterator2>
- _GLIBCXX14_CONSTEXPR
- bool
- operator()(_Iterator1 __it1, _Iterator2 __it2)
- { return bool(_M_comp(*__it1, *__it2)); }
+ _GLIBCXX14_CONSTEXPR
+ bool
+ operator()(_Iterator1 __it1, _Iterator2 __it2)
+ { return bool(_M_comp(*__it1, *__it2)); }
};
template<typename _Compare>
_GLIBCXX14_CONSTEXPR
- inline _Iter_comp_iter<_Compare>
- __iter_comp_iter(_Compare __comp)
- { return _Iter_comp_iter<_Compare>(__comp); }
+ inline _Iter_equal_to_iter_comp<_Compare>
+ __iter_equal_to_iter(_Compare __comp)
+ { return _Iter_equal_to_iter_comp<_Compare>(__comp); }
template<typename _Compare>
- struct _Iter_comp_val
+ struct _Iter_equal_to_val_comp
{
_Compare _M_comp;
- _Iter_comp_val(_Compare __comp)
+ _Iter_equal_to_val_comp(_Compare __comp)
: _M_comp(__comp)
{ }
@@ -145,39 +311,129 @@ namespace __ops
};
template<typename _Compare>
- inline _Iter_comp_val<_Compare>
- __iter_comp_val(_Compare __comp)
- { return _Iter_comp_val<_Compare>(__comp); }
+ inline _Iter_equal_to_val_comp<_Compare>
+ __iter_equal_to_val(_Iter_equal_to_iter_comp<_Compare> __comp)
+ { return _Iter_equal_to_val_comp<_Compare>(__comp._M_comp); }
+
+ template<typename _Compare>
+ struct _Iter_less_val_comp
+ {
+ _Compare _M_comp;
+
+ _Iter_less_val_comp(_Compare __comp)
+ : _M_comp(__comp)
+ { }
+
+ template<typename _Iterator, typename _Value>
+ bool _GLIBCXX14_CONSTEXPR
+ operator()(_Iterator __it, _Value& __val)
+ {
+ if (bool(_M_comp(*__it, __val)))
+ {
+ __glibcxx_requires_cond(
+ _M_reverse_check(__it, __val),
+ _M_message(__gnu_debug::__msg_antisymmetrical_ordering)
+ ._M_instance(_M_comp, "functor")
+ ._M_iterator_value_type(__it, "lhs")
+ ._M_instance(__val, "rhs"));
+ return true;
+ }
+
+ return false;
+ }
+
+#if defined (_GLIBCXX_DEBUG)
+ private:
+# if __cplusplus >= 201103L
+ template<typename _It, typename _Val,
+ typename = decltype(std::declval<_Compare>()(
+ std::declval<_Val>(), __deref<_It>()))>
+ bool
+ _M_reverse_check(_It __it, _Val& __val)
+ { return !bool(_M_comp(__val, *__it)); }
+
+ template<typename... _Args>
+ bool
+ _M_reverse_check(_Args...)
+ { return true; }
+# else
+ template<typename _It, typename _Val>
+ bool
+ _M_reverse_check(_It __it, _Val& __val)
+ { return true; }
+# endif
+#endif
+ };
+
+ template<typename _Compare>
+ inline _Iter_less_val_comp<_Compare>
+ __iter_less_val(_Compare __comp)
+ { return _Iter_less_val_comp<_Compare>(__comp); }
template<typename _Compare>
- inline _Iter_comp_val<_Compare>
- __iter_comp_val(_Iter_comp_iter<_Compare> __comp)
- { return _Iter_comp_val<_Compare>(__comp._M_comp); }
+ inline _Iter_less_val_comp<_Compare>
+ __iter_less_val(_Iter_less_iter_comp<_Compare> __comp)
+ { return _Iter_less_val_comp<_Compare>(__comp._M_comp); }
template<typename _Compare>
- struct _Val_comp_iter
+ struct _Val_less_iter_comp
{
_Compare _M_comp;
- _Val_comp_iter(_Compare __comp)
+ _Val_less_iter_comp(_Compare __comp)
: _M_comp(__comp)
{ }
template<typename _Value, typename _Iterator>
- bool
+ bool _GLIBCXX14_CONSTEXPR
operator()(_Value& __val, _Iterator __it)
- { return bool(_M_comp(__val, *__it)); }
+ {
+ if (bool(_M_comp(__val, *__it)))
+ {
+ __glibcxx_requires_cond(
+ _M_reverse_check(__val, __it),
+ _M_message(__gnu_debug::__msg_antisymmetrical_ordering)
+ ._M_instance(_M_comp, "functor")
+ ._M_instance(__val, "lhs")
+ ._M_iterator_value_type(__it, "rhs"));
+ return true;
+ }
+
+ return false;
+ }
+
+#if defined (_GLIBCXX_DEBUG)
+ private:
+# if __cplusplus >= 201103L
+ template<typename _Val, typename _It,
+ typename = decltype(std::declval<_Compare>()(
+ __deref<_It>(), std::declval<_Val>()))>
+ bool
+ _M_reverse_check(_Val& __val, _It __it)
+ { return !bool(_M_comp(*__it, __val)); }
+
+ template<typename... _Args>
+ bool
+ _M_reverse_check(_Args...)
+ { return true; }
+# else
+ template<typename _Val, typename _It>
+ bool
+ _M_reverse_check(_Val& __val, _It __it)
+ { return true; }
+# endif
+#endif
};
template<typename _Compare>
- inline _Val_comp_iter<_Compare>
- __val_comp_iter(_Compare __comp)
- { return _Val_comp_iter<_Compare>(__comp); }
+ inline _Val_less_iter_comp<_Compare>
+ __val_less_iter(_Compare __comp)
+ { return _Val_less_iter_comp<_Compare>(__comp); }
template<typename _Compare>
- inline _Val_comp_iter<_Compare>
- __val_comp_iter(_Iter_comp_iter<_Compare> __comp)
- { return _Val_comp_iter<_Compare>(__comp._M_comp); }
+ inline _Val_less_iter_comp<_Compare>
+ __val_less_iter(_Iter_less_iter_comp<_Compare> __comp)
+ { return _Val_less_iter_comp<_Compare>(__comp._M_comp); }
template<typename _Value>
struct _Iter_equals_val
@@ -216,7 +472,7 @@ namespace __ops
template<typename _Iterator>
inline _Iter_equals_iter<_Iterator>
- __iter_comp_iter(_Iter_equal_to_iter, _Iterator __it)
+ __iter_equals_iter(_Iter_equal_to_iter, _Iterator __it)
{ return _Iter_equals_iter<_Iterator>(__it); }
template<typename _Predicate>
@@ -240,12 +496,12 @@ namespace __ops
{ return _Iter_pred<_Predicate>(__pred); }
template<typename _Compare, typename _Value>
- struct _Iter_comp_to_val
+ struct _Iter_equals_val_comp
{
_Compare _M_comp;
_Value& _M_value;
- _Iter_comp_to_val(_Compare __comp, _Value& __value)
+ _Iter_equals_val_comp(_Compare __comp, _Value& __value)
: _M_comp(__comp), _M_value(__value)
{ }
@@ -256,17 +512,17 @@ namespace __ops
};
template<typename _Compare, typename _Value>
- _Iter_comp_to_val<_Compare, _Value>
- __iter_comp_val(_Compare __comp, _Value &__val)
- { return _Iter_comp_to_val<_Compare, _Value>(__comp, __val); }
+ _Iter_equals_val_comp<_Compare, _Value>
+ __iter_equals_val(_Compare __comp, _Value &__val)
+ { return _Iter_equals_val_comp<_Compare, _Value>(__comp, __val); }
template<typename _Compare, typename _Iterator1>
- struct _Iter_comp_to_iter
+ struct _Iter_equals_iter_comp
{
_Compare _M_comp;
typename std::iterator_traits<_Iterator1>::reference _M_ref;
- _Iter_comp_to_iter(_Compare __comp, _Iterator1 __it1)
+ _Iter_equals_iter_comp(_Compare __comp, _Iterator1 __it1)
: _M_comp(__comp), _M_ref(*__it1)
{ }
@@ -277,9 +533,12 @@ namespace __ops
};
template<typename _Compare, typename _Iterator>
- inline _Iter_comp_to_iter<_Compare, _Iterator>
- __iter_comp_iter(_Iter_comp_iter<_Compare> __comp, _Iterator __it)
- { return _Iter_comp_to_iter<_Compare, _Iterator>(__comp._M_comp, __it); }
+ inline _Iter_equals_iter_comp<_Compare, _Iterator>
+ __iter_equals_iter(_Iter_equal_to_iter_comp<_Compare> __comp,
+ _Iterator __it)
+ {
+ return _Iter_equals_iter_comp<_Compare, _Iterator>(__comp._M_comp, __it);
+ }
template<typename _Predicate>
struct _Iter_negate
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index f7f3e84..c90f479 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -214,7 +214,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_ForwardIterator2 __p1(__first2);
if (++__p1 == __last2)
return std::__find_if(__first1, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+ __gnu_cxx::__ops::__iter_equals_iter(__predicate, __first2));
// General case.
_ForwardIterator2 __p;
@@ -224,7 +224,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__first1 =
std::__find_if(__first1, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));
+ __gnu_cxx::__ops::__iter_equals_iter(__predicate, __first2));
if (__first1 == __last1)
return __last1;
@@ -487,7 +487,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::__find_end(__first1, __last1, __first2, __last2,
std::__iterator_category(__first1),
std::__iterator_category(__first2),
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__comp));
}
#if __cplusplus >= 201103L
@@ -1031,7 +1031,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first, __last);
return std::__unique(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__binary_pred));
}
/**
@@ -1082,9 +1082,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename iterator_traits<_InputIterator>::value_type>)
typename iterator_traits<_InputIterator>::value_type __value = *__first;
- __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
+ __decltype(__gnu_cxx::__ops::__iter_equal_to_val(__binary_pred))
__rebound_pred
- = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
+ = __gnu_cxx::__ops::__iter_equal_to_val(__binary_pred);
*__result = __value;
while (++__first != __last)
if (!__rebound_pred(__first, __value))
@@ -1809,7 +1809,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::__partial_sort_copy(__first, __last,
__result_first, __result_last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
/// This is a helper function for the sort routine.
@@ -1850,7 +1850,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
else
std::__unguarded_linear_insert(__i,
- __gnu_cxx::__ops::__val_comp_iter(__comp));
+ __gnu_cxx::__ops::__val_less_iter(__comp));
}
}
@@ -1862,7 +1862,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
std::__unguarded_linear_insert(__i,
- __gnu_cxx::__ops::__val_comp_iter(__comp));
+ __gnu_cxx::__ops::__val_less_iter(__comp));
}
/**
@@ -2032,7 +2032,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
return std::__lower_bound(__first, __last, __val,
- __gnu_cxx::__ops::__iter_comp_val(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp));
}
template<typename _ForwardIterator, typename _Tp, typename _Compare>
@@ -2123,7 +2123,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
return std::__upper_bound(__first, __last, __val,
- __gnu_cxx::__ops::__val_comp_iter(__comp));
+ __gnu_cxx::__ops::__val_less_iter(__comp));
}
template<typename _ForwardIterator, typename _Tp,
@@ -2240,8 +2240,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
return std::__equal_range(__first, __last, __val,
- __gnu_cxx::__ops::__iter_comp_val(__comp),
- __gnu_cxx::__ops::__val_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp),
+ __gnu_cxx::__ops::__val_less_iter(__comp));
}
/**
@@ -2312,7 +2312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_ForwardIterator __i
= std::__lower_bound(__first, __last, __val,
- __gnu_cxx::__ops::__iter_comp_val(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp));
return __i != __last && !bool(__comp(__val, *__i));
}
@@ -2464,7 +2464,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::advance(__first_cut, __len11);
__second_cut
= std::__lower_bound(__middle, __last, *__first_cut,
- __gnu_cxx::__ops::__iter_comp_val(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp));
__len22 = std::distance(__middle, __second_cut);
}
else
@@ -2473,7 +2473,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::advance(__second_cut, __len22);
__first_cut
= std::__upper_bound(__first, __middle, *__second_cut,
- __gnu_cxx::__ops::__val_comp_iter(__comp));
+ __gnu_cxx::__ops::__val_less_iter(__comp));
__len11 = std::distance(__first, __first_cut);
}
@@ -2520,7 +2520,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::advance(__first_cut, __len11);
__second_cut
= std::__lower_bound(__middle, __last, *__first_cut,
- __gnu_cxx::__ops::__iter_comp_val(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp));
__len22 = std::distance(__middle, __second_cut);
}
else
@@ -2529,7 +2529,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::advance(__second_cut, __len22);
__first_cut
= std::__upper_bound(__first, __middle, *__second_cut,
- __gnu_cxx::__ops::__val_comp_iter(__comp));
+ __gnu_cxx::__ops::__val_less_iter(__comp));
__len11 = std::distance(__first, __first_cut);
}
@@ -2649,7 +2649,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
std::__inplace_merge(__first, __middle, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
@@ -2908,7 +2908,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
return std::__includes(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
// nth_element
@@ -3017,7 +3017,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
return std::__next_permutation
- (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ (__first, __last, __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _BidirectionalIterator, typename _Compare>
@@ -3117,7 +3117,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
return std::__prev_permutation(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
// replace
@@ -3306,7 +3306,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
return std::__is_sorted_until(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
/**
@@ -3461,7 +3461,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
return std::__minmax_element(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
// N2722 + DR 915.
@@ -3531,15 +3531,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
{
if (__scan != std::__find_if(__first1, __scan,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
+ __gnu_cxx::__ops::__iter_equals_iter(__pred, __scan)))
continue; // We've seen this one before.
auto __matches
= std::__count_if(__first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
+ __gnu_cxx::__ops::__iter_equals_iter(__pred, __scan));
if (0 == __matches ||
std::__count_if(__scan, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+ __gnu_cxx::__ops::__iter_equals_iter(__pred, __scan))
!= __matches)
return false;
}
@@ -3604,7 +3604,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first1, __last1);
return std::__is_permutation(__first1, __last1, __first2,
- __gnu_cxx::__ops::__iter_comp_iter(__pred));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__pred));
}
#if __cplusplus > 201103L
@@ -3655,14 +3655,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
{
if (__scan != std::__find_if(__first1, __scan,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
+ __gnu_cxx::__ops::__iter_equals_iter(__pred, __scan)))
continue; // We've seen this one before.
auto __matches = std::__count_if(__first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
+ __gnu_cxx::__ops::__iter_equals_iter(__pred, __scan));
if (0 == __matches
|| std::__count_if(__scan, __last1,
- __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+ __gnu_cxx::__ops::__iter_equals_iter(__pred, __scan))
!= __matches)
return false;
}
@@ -3720,7 +3720,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_valid_range(__first2, __last2);
return std::__is_permutation(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__pred));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__pred));
}
#endif
@@ -3968,7 +3968,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first, __last);
return std::__adjacent_find(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__binary_pred));
}
/**
@@ -4099,7 +4099,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first2, __last2);
return std::__search(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__predicate));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__predicate));
}
/**
@@ -4164,7 +4164,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first, __last);
return std::__search_n(__first, __last, __count,
- __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
+ __gnu_cxx::__ops::__iter_equals_val(__binary_pred, __val));
}
@@ -4441,7 +4441,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
if (__first == __last)
return __result;
return std::__unique_copy(__first, __last, __result,
- __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
+ __gnu_cxx::__ops::__iter_equal_to_iter(__binary_pred),
std::__iterator_category(__first),
std::__iterator_category(__result));
}
@@ -4622,7 +4622,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
std::__partial_sort(__first, __middle, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
/**
@@ -4699,7 +4699,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
std::__introselect(__first, __nth, __last,
std::__lg(__last - __first) * 2,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
/**
@@ -4760,7 +4760,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
- std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _InputIterator1, typename _InputIterator2,
@@ -4881,7 +4881,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return _GLIBCXX_STD_A::__merge(__first1, __last1,
__first2, __last2, __result,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _RandomAccessIterator, typename _Compare>
@@ -4970,7 +4970,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
_GLIBCXX_STD_A::__stable_sort(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _InputIterator1, typename _InputIterator2,
@@ -5099,7 +5099,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return _GLIBCXX_STD_A::__set_union(__first1, __last1,
__first2, __last2, __result,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _InputIterator1, typename _InputIterator2,
@@ -5215,7 +5215,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
__first2, __last2, __result,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _InputIterator1, typename _InputIterator2,
@@ -5337,7 +5337,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
__first2, __last2, __result,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _InputIterator1, typename _InputIterator2,
@@ -5468,7 +5468,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
__first2, __last2, __result,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _ForwardIterator, typename _Compare>
@@ -5533,7 +5533,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
return _GLIBCXX_STD_A::__min_element(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _ForwardIterator, typename _Compare>
@@ -5597,7 +5597,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
return _GLIBCXX_STD_A::__max_element(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
_GLIBCXX_END_NAMESPACE_ALGO
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 99f3cc4c..0567a36 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1248,7 +1248,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return std::__lexicographical_compare_impl
(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _InputIterator1, typename _InputIterator2,
@@ -1323,7 +1323,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first1, __last1);
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2,
- __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__binary_pred));
}
#if __cplusplus > 201103L
@@ -1407,7 +1407,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_requires_valid_range(__first2, __last2);
return _GLIBCXX_STD_A::__mismatch(__first1, __last1, __first2, __last2,
- __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
+ __gnu_cxx::__ops::__iter_equal_to_iter(__binary_pred));
}
#endif
diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index e13b6be..f5e0ed3 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -101,7 +101,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
{
return std::__is_heap_until(__first, __n,
- __gnu_cxx::__ops::__iter_comp_iter(__comp)) == __n;
+ __gnu_cxx::__ops::__iter_less_iter(__comp)) == __n;
}
template<typename _RandomAccessIterator>
@@ -200,7 +200,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
std::__push_heap(__first, _DistanceType((__last - __first) - 1),
_DistanceType(0), _GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::__iter_comp_val(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp));
}
template<typename _RandomAccessIterator, typename _Distance,
@@ -229,7 +229,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
std::__push_heap(__first, __holeIndex, __topIndex,
_GLIBCXX_MOVE(__value),
- __gnu_cxx::__ops::__iter_comp_val(__comp));
+ __gnu_cxx::__ops::__iter_less_val(__comp));
}
template<typename _RandomAccessIterator, typename _Compare>
@@ -312,7 +312,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
--__last;
std::__pop_heap(__first, __last, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
}
@@ -388,7 +388,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_irreflexive_pred(__first, __last, __comp);
std::__make_heap(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
template<typename _RandomAccessIterator, typename _Compare>
@@ -451,7 +451,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_requires_heap_pred(__first, __last, __comp);
std::__sort_heap(__first, __last,
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
#if __cplusplus >= 201103L
@@ -506,7 +506,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return __first
+ std::__is_heap_until(__first, std::distance(__first, __last),
- __gnu_cxx::__ops::__iter_comp_iter(__comp));
+ __gnu_cxx::__ops::__iter_less_iter(__comp));
}
/**
diff --git a/libstdc++-v3/include/debug/formatter.h b/libstdc++-v3/include/debug/formatter.h
index 72735bb..6e56c8f 100644
--- a/libstdc++-v3/include/debug/formatter.h
+++ b/libstdc++-v3/include/debug/formatter.h
@@ -127,7 +127,8 @@ namespace __gnu_debug
// others
__msg_equal_allocs,
__msg_insert_range_from_self,
- __msg_irreflexive_ordering
+ __msg_irreflexive_ordering,
+ __msg_antisymmetrical_ordering
};
class _Error_formatter
diff --git a/libstdc++-v3/src/c++11/debug.cc b/libstdc++-v3/src/c++11/debug.cc
index d8ffc6d..804d88c 100644
--- a/libstdc++-v3/src/c++11/debug.cc
+++ b/libstdc++-v3/src/c++11/debug.cc
@@ -188,7 +188,9 @@ namespace __gnu_debug
"allocators must be equal",
"attempt to insert with an iterator range [%1.name;, %2.name;) from this"
" container",
- "comparison doesn't meet irreflexive requirements, assert(!(a < a))"
+ "comparison doesn't meet irreflexive requirements, assert(!(a < a))",
+ "comparison doesn't meet antisymmetrical requirements,"
+ " if a < b then assert(!(b < a))"
};
void
diff --git a/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc b/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc
index b69e76b..b7c7c37 100644
--- a/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/lower_bound/33613.cc
@@ -20,6 +20,7 @@
// NB: This issue affected only debug-mode.
// { dg-do compile }
+// { dg-options "-std=gnu++11" }
// libstdc++/33613
diff --git a/libstdc++-v3/testsuite/25_algorithms/lower_bound/invalid_strict_weak_ordering_neg.cc b/libstdc++-v3/testsuite/25_algorithms/lower_bound/invalid_strict_weak_ordering_neg.cc
new file mode 100644
index 0000000..02b9c76
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lower_bound/invalid_strict_weak_ordering_neg.cc
@@ -0,0 +1,62 @@
+// Copyright (C) 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/>.
+
+// 25.3.3.1 [lib.lower.bound]
+
+// { dg-require-debug-mode "" }
+// { dg-do run { xfail *-*-* } }
+// { dg-options "-std=gnu++11" }
+
+#include <vector>
+#include <algorithm>
+
+#include <testsuite_hooks.h>
+
+namespace
+{
+ struct InvalidStrictWeakOrdering
+ {
+ InvalidStrictWeakOrdering(int val)
+ : _M_val(val) { }
+
+ bool
+ operator<(const InvalidStrictWeakOrdering& other) const
+ { return _M_val <= other._M_val; }
+
+ private:
+ int _M_val;
+ };
+}
+
+void
+test1()
+{
+ typedef std::vector<InvalidStrictWeakOrdering> data_t;
+ data_t datas;
+ for (int i = 0; i != 10; ++i)
+ datas.push_back(i);
+
+ data_t::iterator it = std::lower_bound(datas.begin(), datas.end(),
+ InvalidStrictWeakOrdering(5));
+ VERIFY( it != datas.end() );
+}
+
+int
+main()
+{
+ test1();
+}