|
|
Created:
13 years ago by ppluzhnikov Modified:
13 years ago Reviewers:
Diego Novillo CC:
gcc-patches_gcc.gnu.org Base URL:
svn+ssh://gcc.gnu.org/svn/gcc/branches/google/integration/ Visibility:
Public. |
Descriptionr172380 committed.
Patch Set 1 #
MessagesTotal messages: 2
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 <ppluzhnikov@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
Sign in to reply to this message.
On Wed, Apr 13, 2011 at 01:44, Paul Pluzhnikov <ppluzhnikov@google.com> wrote: > 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 <ppluzhnikov@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. OK. Diego.
Sign in to reply to this message.
|