From patchwork Wed Apr 13 05:44:59 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paul Pluzhnikov X-Patchwork-Id: 90945 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 9B42EB6F35 for ; Wed, 13 Apr 2011 15:45:20 +1000 (EST) Received: (qmail 24338 invoked by alias); 13 Apr 2011 05:45:16 -0000 Received: (qmail 24305 invoked by uid 22791); 13 Apr 2011 05:45:13 -0000 X-SWARE-Spam-Status: No, hits=-2.0 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, SPF_HELO_PASS, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from smtp-out.google.com (HELO smtp-out.google.com) (74.125.121.67) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 13 Apr 2011 05:45:04 +0000 Received: from wpaz33.hot.corp.google.com (wpaz33.hot.corp.google.com [172.24.198.97]) by smtp-out.google.com with ESMTP id p3D5j1QS010926; Tue, 12 Apr 2011 22:45:02 -0700 Received: from elbrus2.mtv.corp.google.com (elbrus2.mtv.corp.google.com [172.18.116.96]) by wpaz33.hot.corp.google.com with ESMTP id p3D5j06g004648; Tue, 12 Apr 2011 22:45:00 -0700 Received: by elbrus2.mtv.corp.google.com (Postfix, from userid 74925) id D431D190950; Tue, 12 Apr 2011 22:44:59 -0700 (PDT) To: reply@codereview.appspotmail.com, gcc-patches@gcc.gnu.org Subject: [google/integration] Enable lightweight debug checks (issue4408041) Message-Id: <20110413054459.D431D190950@elbrus2.mtv.corp.google.com> Date: Tue, 12 Apr 2011 22:44:59 -0700 (PDT) From: ppluzhnikov@google.com (Paul Pluzhnikov) X-System-Of-Record: true Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 * 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. --- This patch is available for review at http://codereview.appspot.com/4408041 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 + struct _CheckedCompare { + _Compare _M_compare; + + _CheckedCompare(const _Compare & __comp): _M_compare(__comp) { } + + template + 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 + 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 minmax(const _Tp& __a, const _Tp& __b, _Compare __comp) { - return __comp(__b, __a) ? pair(__b, __a) - : pair(__a, __b); + return __CheckedCompare(__comp)(__b, __a) + ? pair(__b, __a) + : pair(__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 + 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 + 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&