[PATCH] Fix incorrect results from std::boyer_moore_searcher
Jonathan Wakely
jwakely@redhat.com
Tue Apr 18 11:09:00 GMT 2017
Nico noticed the return value of std::boyer_moore_searcher has the
wrong position for the end of the match. Fixed by this patch, which
also does some minor cleanup (like removing redundant std:: quals that
were copied from the std::experimental::boyer_moore_searcher version).
* 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.
Tested ppc64le-linux, committed to trunk.
-------------- next part --------------
commit 35bccf225502eaa895321500b20e432605119b93
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Tue Apr 18 11:51:35 2017 +0100
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.
diff --git a/libstdc++-v3/include/std/functional b/libstdc++-v3/include/std/functional
index 0661253..e4a82ee 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<typename _Key, typename _Tp, typename _Hash, typename _Pred>
@@ -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<decltype(__ch)>;
+ using _UCh = make_unsigned_t<decltype(__ch)>;
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<std::make_unsigned_t<_Key>>(__key);
+ auto __ukey = static_cast<make_unsigned_t<_Key>>(__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<typename _Pred>
- struct __is_std_equal_to : std::false_type { };
+ struct __is_std_equal_to : false_type { };
template<>
- struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };
+ struct __is_std_equal_to<equal_to<void>> : 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<sizeof(_Val) == 1 && is_integral<_Val>::value
- && __is_std_equal_to<_Pred>::value,
- __boyer_moore_array_base<_Diff, 256, _Pred>,
- __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
+ = conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
+ && __is_std_equal_to<_Pred>::value,
+ __boyer_moore_array_base<_Diff, 256, _Pred>,
+ __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
template<typename _RAIter, typename _Hash
- = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
- typename _BinaryPredicate = std::equal_to<>>
+ = hash<typename iterator_traits<_RAIter>::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<typename _RAIter, typename _Hash
- = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
- typename _BinaryPredicate = std::equal_to<>>
+ = hash<typename iterator_traits<_RAIter>::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 9cc1455..4f7b1d4 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
More information about the Libstdc++
mailing list