From 38d68cf0f5dae47c558e2ea2a9bf652788a19eeb Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Tue, 18 Apr 2017 12:08:00 +0100 Subject: [PATCH] Fix incorrect results from std::boyer_moore_searcher * include/std/functional (default_searcher, __boyer_moore_array_base) (__is_std_equal_to, __boyer_moore_base_t, boyer_moore_searcher) (boyer_moore_horspool_searcher): Remove redundant namespace qualification. (default_searcher::operator()): Construct return value early and advance second member in-place. (boyer_moore_horspool_searcher::operator()): Increment random access iterator directly instead of using std::next. (boyer_moore_searcher::operator()): Fix return value. * testsuite/20_util/function_objects/searchers.cc: Check both parts of return values. From-SVN: r246964 --- libstdc++-v3/ChangeLog | 14 ++++++ libstdc++-v3/include/std/functional | 49 ++++++++++--------- .../20_util/function_objects/searchers.cc | 45 +++++++++++++++-- 3 files changed, 81 insertions(+), 27 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 3f836d2c673..503f2341102 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,17 @@ +2017-04-18 Jonathan Wakely + + * include/std/functional (default_searcher, __boyer_moore_array_base) + (__is_std_equal_to, __boyer_moore_base_t, boyer_moore_searcher) + (boyer_moore_horspool_searcher): Remove redundant namespace + qualification. + (default_searcher::operator()): Construct return value early and + advance second member in-place. + (boyer_moore_horspool_searcher::operator()): Increment random access + iterator directly instead of using std::next. + (boyer_moore_searcher::operator()): Fix return value. + * testsuite/20_util/function_objects/searchers.cc: Check both parts + of return values. + 2017-04-12 Gerald Pfeifer * doc/xml/faq.xml: Update reference link to C++ ABI for Itanium. diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional index 06612537c43..e4a82ee346f 100644 --- a/libstdc++-v3/include/std/functional +++ b/libstdc++-v3/include/std/functional @@ -969,17 +969,17 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const { _ForwardIterator2 __first_ret = - std::search(__first, __last, - std::get<0>(_M_m), std::get<1>(_M_m), + std::search(__first, __last, std::get<0>(_M_m), std::get<1>(_M_m), std::get<2>(_M_m)); - _ForwardIterator2 __second_ret = __first_ret == __last ? - __last : std::next(__first_ret, std::distance(std::get<0>(_M_m), - std::get<1>(_M_m))); - return std::make_pair(__first_ret, __second_ret); + auto __ret = std::make_pair(__first_ret, __first_ret); + if (__ret.first != __last) + std::advance(__ret.second, std::distance(std::get<0>(_M_m), + std::get<1>(_M_m))); + return __ret; } private: - std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; + tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m; }; template @@ -1025,7 +1025,7 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) for (__diff_type __i = 0; __i < __patlen - 1; ++__i) { auto __ch = __pat[__i]; - using _UCh = std::make_unsigned_t; + using _UCh = make_unsigned_t; auto __uch = static_cast<_UCh>(__ch); std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i; } @@ -1037,7 +1037,7 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) __diff_type _M_lookup(_Key __key, __diff_type __not_found) const { - auto __ukey = static_cast>(__key); + auto __ukey = static_cast>(__key); if (__ukey >= _Len) return __not_found; return std::get<0>(_M_bad_char)[__ukey]; @@ -1046,14 +1046,14 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) const _Pred& _M_pred() const { return std::get<1>(_M_bad_char); } - std::tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char; + tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char; }; template - struct __is_std_equal_to : std::false_type { }; + struct __is_std_equal_to : false_type { }; template<> - struct __is_std_equal_to> : std::true_type { }; + struct __is_std_equal_to> : true_type { }; // Use __boyer_moore_array_base when pattern consists of narrow characters // and uses std::equal_to as the predicate. @@ -1061,14 +1061,14 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) typename _Val = typename iterator_traits<_RAIter>::value_type, typename _Diff = typename iterator_traits<_RAIter>::difference_type> using __boyer_moore_base_t - = std::conditional_t::value - && __is_std_equal_to<_Pred>::value, - __boyer_moore_array_base<_Diff, 256, _Pred>, - __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; + = conditional_t::value + && __is_std_equal_to<_Pred>::value, + __boyer_moore_array_base<_Diff, 256, _Pred>, + __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>; template::value_type>, - typename _BinaryPredicate = std::equal_to<>> + = hash::value_type>, + typename _BinaryPredicate = equal_to<>> class boyer_moore_searcher : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> { @@ -1123,8 +1123,8 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) }; template::value_type>, - typename _BinaryPredicate = std::equal_to<>> + = hash::value_type>, + typename _BinaryPredicate = equal_to<>> class boyer_moore_horspool_searcher : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate> { @@ -1156,8 +1156,7 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) for (auto __scan = __patlen - 1; __pred(__first[__scan], _M_pat[__scan]); --__scan) if (__scan == 0) - return std::make_pair(__first, - std::next(__first, __patlen)); + return std::make_pair(__first, __first + __patlen); auto __shift = _M_bad_char_shift(__first[__patlen - 1]); __len -= __shift; __first += __shift; @@ -1223,8 +1222,10 @@ _GLIBCXX_MEM_FN_TRAITS(&&, false_type, true_type) --__j; } if (__j < 0) - return std::make_pair(__first + __i + 1, std::next(__first, - __patlen)); + { + const auto __match = __first + __i + 1; + return std::make_pair(__match, __match + __patlen); + } __i += std::max(_M_bad_char_shift(__first[__i]), _M_good_suffix[__j]); } diff --git a/libstdc++-v3/testsuite/20_util/function_objects/searchers.cc b/libstdc++-v3/testsuite/20_util/function_objects/searchers.cc index 9cc1455c85c..4f7b1d4818d 100644 --- a/libstdc++-v3/testsuite/20_util/function_objects/searchers.cc +++ b/libstdc++-v3/testsuite/20_util/function_objects/searchers.cc @@ -49,7 +49,8 @@ test01() for (auto n : needles) { - auto ne = n + std::strlen(n); + auto nlen = std::strlen(n); + auto ne = n + nlen; default_searcher d(n, ne); boyer_moore_searcher bm(n, ne); boyer_moore_horspool_searcher bmh(n, ne); @@ -59,10 +60,22 @@ test01() auto res = std::search(h, he, n, ne); auto d_res = d(h, he); VERIFY( d_res.first == res ); + if (res == he) + VERIFY( d_res.second == d_res.first ); + else + VERIFY( d_res.second == (d_res.first + nlen) ); auto bm_res = bm(h, he); VERIFY( bm_res.first == res ); + if (res == he) + VERIFY( bm_res.second == bm_res.first ); + else + VERIFY( bm_res.second == (bm_res.first + nlen) ); auto bmh_res = bmh(h, he); VERIFY( bmh_res.first == res ); + if (res == he) + VERIFY( bmh_res.second == bmh_res.first ); + else + VERIFY( bmh_res.second == (bmh_res.first + nlen) ); } } } @@ -82,7 +95,8 @@ test02() for (auto n : needles) { - auto ne = n + std::wcslen(n); + auto nlen = std::wcslen(n); + auto ne = n + nlen; default_searcher d(n, ne); boyer_moore_searcher bm(n, ne); boyer_moore_horspool_searcher bmh(n, ne); @@ -92,10 +106,22 @@ test02() auto res = std::search(h, he, n, ne); auto d_res = d(h, he); VERIFY( d_res.first == res ); + if (res == he) + VERIFY( d_res.second == d_res.first ); + else + VERIFY( d_res.second == (d_res.first + nlen) ); auto bm_res = bm(h, he); VERIFY( bm_res.first == res ); + if (res == he) + VERIFY( bm_res.second == bm_res.first ); + else + VERIFY( bm_res.second == (bm_res.first + nlen) ); auto bmh_res = bmh(h, he); VERIFY( bmh_res.first == res ); + if (res == he) + VERIFY( bmh_res.second == bmh_res.first ); + else + VERIFY( bmh_res.second == (bmh_res.first + nlen) ); } } #endif @@ -119,7 +145,8 @@ test03() const char* needle = " foo 123 "; const char* haystack = "*****foo*123******"; - const char* ne = needle + std::strlen(needle); + auto nlen = std::strlen(needle); + const char* ne = needle + nlen; const char* he = haystack + std::strlen(haystack); default_searcher d(needle, ne, eq); @@ -129,10 +156,22 @@ test03() auto res = std::search(haystack, he, needle, ne, eq); auto d_res = d(haystack, he); VERIFY( d_res.first == res ); + if (res == he) + VERIFY( d_res.second == d_res.first ); + else + VERIFY( d_res.second == (d_res.first + nlen) ); auto bm_res = bm(haystack, he); VERIFY( bm_res.first == res ); + if (res == he) + VERIFY( bm_res.second == bm_res.first ); + else + VERIFY( bm_res.second == (bm_res.first + nlen) ); auto bmh_res = bmh(haystack, he); VERIFY( bmh_res.first == res ); + if (res == he) + VERIFY( bmh_res.second == bmh_res.first ); + else + VERIFY( bmh_res.second == (bmh_res.first + nlen) ); } int -- 2.30.2