https://llvm.org/bugs/show_bug.cgi?id=31462
Bug ID: 31462
Summary: booyer moore searchers violate algorithmic complexity
requirements.
Product: libc++
Version: unspecified
Hardware: PC
OS: Windows NT
Status: NEW
Severity: normal
Priority: P
Component: All Bugs
Assignee: unassignedclangb...@nondot.org
Reporter: e...@efcs.ca
CC: llvm-bugs@lists.llvm.org, mclow.li...@gmail.com
Classification: Unclassified
The standard states the required complexity for the boyer_moore and
boyer_moore_horspool searchers as:
> Complexity: At most (last - first) * (pat_last_ - pat_first_) applications of
> the predicate
However certain test cases violate this requirement. Specifically when the
input range is smaller than the "pat" range. There are FIXME comments in the
searchers tests which mark these test cases. When this bug gets fixed those
should be fixed as well.
Minimal reproducer:
#include <experimental/algorithm>
#include <experimental/functional>
#include <cassert>
struct count_equal {
static unsigned count;
template <class T>
bool operator()(const T& x, const T& y) const
{++count; return x == y;}
};
unsigned count_equal::count = 0;
int main() {
count_equal::count = 0;
char ia[] = {0, 1, 2, 3, 4, 5};
const unsigned sa = sizeof(ia)/sizeof(ia[0]);
std::experimental::boyer_moore_searcher<char*, std::hash<char>, count_equal>
searcher(ia, ia+sa);
std::experimental::search(ia, ia+1, searcher);
assert(count_equal::count <= sa); // fails
}
--
You are receiving this mail because:
You are on the CC list for the bug.
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
