This patch adds lightweight debug checks (if enabled by macros).
To be applied only to google/integration branch.
Tested by bootstrapping and running "make check".
2011-04-12 Paul Pluzhnikov <ppluzhni...@google.com>
* libstdc++-v3/include/bits/stl_algo.h: Add comparator debug checks
when __google_stl_debug_compare is 1.
* libstdc++-v3/include/bits/stl_tree.h: Add comparator debug checks
when __google_stl_debug_rbtree is 1.
Index: libstdc++-v3/include/bits/stl_algo.h
===================================================================
--- libstdc++-v3/include/bits/stl_algo.h (revision 172360)
+++ libstdc++-v3/include/bits/stl_algo.h (working copy)
@@ -318,6 +318,39 @@
// count_if
// search
+// Local modification: if __google_stl_debug_compare is defined to
+// non-zero value, check sort predicate for strict weak ordering.
+// Google ref b/1731200.
+#if __google_stl_debug_compare
+ template<typename _Compare>
+ struct _CheckedCompare {
+ _Compare _M_compare;
+
+ _CheckedCompare(const _Compare & __comp): _M_compare(__comp) { }
+
+ template <typename _Tp>
+ bool operator()(const _Tp& __x, const _Tp& __y) {
+ if (_M_compare(__x, __x))
+ __throw_runtime_error("strict weak ordering: (__x LT __x) != false");
+ if (_M_compare(__y, __y))
+ __throw_runtime_error("strict weak ordering: (__y LT __y) != false");
+ bool lt = _M_compare(__x, __y);
+ if (lt && _M_compare(__y, __x))
+ __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y LT
__x)) != false");
+ return lt;
+ }
+
+ // Different types; can't perform any checks.
+ template <typename _Tp1, typename _Tp2>
+ bool operator()(const _Tp1& __x, const _Tp2& __y) {
+ return _M_compare(__x, __y);
+ }
+ };
+# define __CheckedCompare(__comp) _CheckedCompare<__typeof__(__comp)>(__comp)
+#else
+# define __CheckedCompare(__comp) __comp
+#endif
+
/**
* This is an uglified
* search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&)
@@ -2041,18 +2074,20 @@
++__result_real_last;
++__first;
}
- std::make_heap(__result_first, __result_real_last, __comp);
+ std::make_heap(__result_first, __result_real_last,
+ __CheckedCompare(__comp));
while (__first != __last)
{
- if (__comp(*__first, *__result_first))
+ if (__CheckedCompare(__comp)(*__first, *__result_first))
std::__adjust_heap(__result_first, _DistanceType(0),
_DistanceType(__result_real_last
- __result_first),
_InputValueType(*__first),
- __comp);
+ __CheckedCompare(__comp));
++__first;
}
- std::sort_heap(__result_first, __result_real_last, __comp);
+ std::sort_heap(__result_first, __result_real_last,
+ __CheckedCompare(__comp));
return __result_real_last;
}
@@ -2413,7 +2448,7 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (__comp(*__middle, __val))
+ if (__CheckedCompare(__comp)(*__middle, __val))
{
__first = __middle;
++__first;
@@ -2509,7 +2544,7 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (__comp(__val, *__middle))
+ if (__CheckedCompare(__comp)(__val, *__middle))
__len = __half;
else
{
@@ -2628,13 +2663,13 @@
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
- if (__comp(*__middle, __val))
+ if (__CheckedCompare(__comp)(*__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
- else if (__comp(__val, *__middle))
+ else if (__CheckedCompare(__comp)(__val, *__middle))
__len = __half;
else
{
@@ -2711,7 +2746,7 @@
__val, __comp);
_ForwardIterator __i = std::lower_bound(__first, __last, __val, __comp);
- return __i != __last && !bool(__comp(__val, *__i));
+ return __i != __last && !bool(__CheckedCompare(__comp)(__val, *__i));
}
// merge
@@ -3180,11 +3215,11 @@
__last);
if (__buf.begin() == 0)
std::__merge_without_buffer(__first, __middle, __last, __len1,
- __len2, __comp);
+ __len2, __CheckedCompare(__comp));
else
std::__merge_adaptive(__first, __middle, __last, __len1, __len2,
__buf.begin(), _DistanceType(__buf.size()),
- __comp);
+ __CheckedCompare(__comp));
}
template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
@@ -3505,9 +3540,9 @@
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first2, *__first1))
+ if (__CheckedCompare(__comp)(*__first2, *__first1))
return false;
- else if(__comp(*__first1, *__first2))
+ else if(__CheckedCompare(__comp)(*__first1, *__first2))
++__first1;
else
++__first1, ++__first2;
@@ -3620,10 +3655,10 @@
{
_BidirectionalIterator __ii = __i;
--__i;
- if (__comp(*__i, *__ii))
+ if (__CheckedCompare(__comp)(*__i, *__ii))
{
_BidirectionalIterator __j = __last;
- while (!bool(__comp(*__i, *--__j)))
+ while (!bool(__CheckedCompare(__comp)(*__i, *--__j)))
{}
std::iter_swap(__i, __j);
std::reverse(__ii, __last);
@@ -3733,10 +3768,10 @@
{
_BidirectionalIterator __ii = __i;
--__i;
- if (__comp(*__ii, *__i))
+ if (__CheckedCompare(__comp)(*__ii, *__i))
{
_BidirectionalIterator __j = __last;
- while (!bool(__comp(*--__j, *__i)))
+ while (!bool(__CheckedCompare(__comp)(*--__j, *__i)))
{}
std::iter_swap(__i, __j);
std::reverse(__ii, __last);
@@ -3909,7 +3944,7 @@
_ForwardIterator __next = __first;
for (++__next; __next != __last; __first = __next, ++__next)
- if (__comp(*__next, *__first))
+ if (__CheckedCompare(__comp)(*__next, *__first))
return __next;
return __next;
}
@@ -3944,8 +3979,9 @@
inline pair<const _Tp&, const _Tp&>
minmax(const _Tp& __a, const _Tp& __b, _Compare __comp)
{
- return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a)
- : pair<const _Tp&, const _Tp&>(__a, __b);
+ return __CheckedCompare(__comp)(__b, __a)
+ ? pair<const _Tp&, const _Tp&>(__b, __a)
+ : pair<const _Tp&, const _Tp&>(__a, __b);
}
/**
@@ -4053,7 +4089,7 @@
return std::make_pair(__first, __first);
_ForwardIterator __min, __max;
- if (__comp(*__next, *__first))
+ if (__CheckedCompare(__comp)(*__next, *__first))
{
__min = __next;
__max = __first;
@@ -4072,25 +4108,25 @@
__next = __first;
if (++__next == __last)
{
- if (__comp(*__first, *__min))
+ if (__CheckedCompare(__comp)(*__first, *__min))
__min = __first;
- else if (!__comp(*__first, *__max))
+ else if (!__CheckedCompare(__comp)(*__first, *__max))
__max = __first;
break;
}
- if (__comp(*__next, *__first))
+ if (__CheckedCompare(__comp)(*__next, *__first))
{
- if (__comp(*__next, *__min))
+ if (__CheckedCompare(__comp)(*__next, *__min))
__min = __next;
- if (!__comp(*__first, *__max))
+ if (!__CheckedCompare(__comp)(*__first, *__max))
__max = __first;
}
else
{
- if (__comp(*__first, *__min))
+ if (__CheckedCompare(__comp)(*__first, *__min))
__min = __first;
- if (!__comp(*__next, *__max))
+ if (!__CheckedCompare(__comp)(*__next, *__max))
__max = __next;
}
@@ -5215,8 +5251,8 @@
__glibcxx_requires_valid_range(__first, __middle);
__glibcxx_requires_valid_range(__middle, __last);
- std::__heap_select(__first, __middle, __last, __comp);
- std::sort_heap(__first, __middle, __comp);
+ std::__heap_select(__first, __middle, __last, __CheckedCompare(__comp));
+ std::sort_heap(__first, __middle, __CheckedCompare(__comp));
}
/**
@@ -5294,7 +5330,8 @@
return;
std::__introselect(__first, __nth, __last,
- std::__lg(__last - __first) * 2, __comp);
+ std::__lg(__last - __first) * 2,
+ __CheckedCompare(__comp));
}
@@ -5366,8 +5403,10 @@
if (__first != __last)
{
std::__introsort_loop(__first, __last,
- std::__lg(__last - __first) * 2, __comp);
- std::__final_insertion_sort(__first, __last, __comp);
+ std::__lg(__last - __first) * 2,
+ __CheckedCompare(__comp));
+ std::__final_insertion_sort(__first, __last,
+ __CheckedCompare(__comp));
}
}
@@ -5478,7 +5517,7 @@
while (__first1 != __last1 && __first2 != __last2)
{
- if (__comp(*__first2, *__first1))
+ if (__CheckedCompare(__comp)(*__first2, *__first1))
{
*__result = *__first2;
++__first2;
@@ -5575,10 +5614,11 @@
_Temporary_buffer<_RandomAccessIterator, _ValueType> __buf(__first,
__last);
if (__buf.begin() == 0)
- std::__inplace_stable_sort(__first, __last, __comp);
+ std::__inplace_stable_sort(__first, __last, __CheckedCompare(__comp));
else
std::__stable_sort_adaptive(__first, __last, __buf.begin(),
- _DistanceType(__buf.size()), __comp);
+ _DistanceType(__buf.size()),
+ __CheckedCompare(__comp));
}
@@ -5695,12 +5735,12 @@
while (__first1 != __last1 && __first2 != __last2)
{
- if (__comp(*__first1, *__first2))
+ if (__CheckedCompare(__comp)(*__first1, *__first2))
{
*__result = *__first1;
++__first1;
}
- else if (__comp(*__first2, *__first1))
+ else if (__CheckedCompare(__comp)(*__first2, *__first1))
{
*__result = *__first2;
++__first2;
@@ -5816,9 +5856,9 @@
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
+ if (__CheckedCompare(__comp)(*__first1, *__first2))
++__first1;
- else if (__comp(*__first2, *__first1))
+ else if (__CheckedCompare(__comp)(*__first2, *__first1))
++__first2;
else
{
@@ -5935,13 +5975,13 @@
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
+ if (__CheckedCompare(__comp)(*__first1, *__first2))
{
*__result = *__first1;
++__first1;
++__result;
}
- else if (__comp(*__first2, *__first1))
+ else if (__CheckedCompare(__comp)(*__first2, *__first1))
++__first2;
else
{
@@ -6062,13 +6102,13 @@
__glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
while (__first1 != __last1 && __first2 != __last2)
- if (__comp(*__first1, *__first2))
+ if (__CheckedCompare(__comp)(*__first1, *__first2))
{
*__result = *__first1;
++__first1;
++__result;
}
- else if (__comp(*__first2, *__first1))
+ else if (__CheckedCompare(__comp)(*__first2, *__first1))
{
*__result = *__first2;
++__first2;
@@ -6135,7 +6175,7 @@
return __first;
_ForwardIterator __result = __first;
while (++__first != __last)
- if (__comp(*__first, *__result))
+ if (__CheckedCompare(__comp)(*__first, *__result))
__result = __first;
return __result;
}
@@ -6190,11 +6230,13 @@
if (__first == __last) return __first;
_ForwardIterator __result = __first;
while (++__first != __last)
- if (__comp(*__result, *__first))
+ if (__CheckedCompare(__comp)(*__result, *__first))
__result = __first;
return __result;
}
+#undef __CheckedCompare
+
_GLIBCXX_END_NAMESPACE_ALGO
} // namespace std
Index: libstdc++-v3/include/bits/stl_tree.h
===================================================================
--- libstdc++-v3/include/bits/stl_tree.h (revision 172360)
+++ libstdc++-v3/include/bits/stl_tree.h (working copy)
@@ -461,7 +461,47 @@
}
};
+ // Local modification: if __google_stl_debug_rbtree is defined to
+ // non-zero value, check sort predicate for strict weak ordering.
+ // Google ref b/1731200.
+#if __google_stl_debug_rbtree
+ template<typename _KeyCompare>
+ struct _CheckedCompare {
+ _KeyCompare _M_key_compare;
+
+ _CheckedCompare(): _M_key_compare() { }
+ _CheckedCompare(const _KeyCompare & __comp): _M_key_compare(__comp) { }
+
+ // Template arg required to avoid duplicating code in the two op()
+ // operators below. User-provided _M_key_compare may not be const,
+ // but needs to be callable from our const op().
+ // Google ref. b/1731200.
+ template <typename _KeyCompareT>
+ static bool _M_compare_with(_KeyCompareT& __comp, const _Key& __x,
const _Key& __y) {
+ if (__comp(__x, __x))
+ __throw_runtime_error("strict weak ordering: (__x LT __x) !=
false");
+ if (__comp(__y, __y))
+ __throw_runtime_error("strict weak ordering: (__y LT __y) !=
false");
+ bool lt = __comp(__x, __y);
+ if (lt && __comp(__y, __x))
+ __throw_runtime_error("strict weak ordering: ((__x LT __y) && (__y
LT __x)) != false");
+ return lt;
+ }
+ bool operator()(const _Key& __x, const _Key& __y) const {
+ return _M_compare_with(_M_key_compare, __x, __y);
+ }
+
+ bool operator()(const _Key& __x, const _Key& __y) {
+ return _M_compare_with(_M_key_compare, __x, __y);
+ }
+
+ operator _KeyCompare() const { return _M_key_compare; }
+ };
+
+ _Rb_tree_impl<_CheckedCompare<_Compare> > _M_impl;
+#else
_Rb_tree_impl<_Compare> _M_impl;
+#endif
protected:
_Base_ptr&
--
This patch is available for review at http://codereview.appspot.com/4408041
