[llvm-bugs] [Bug 31462] New: booyer moore searchers violate algorithmic complexity requirements.

[via llvm-bugs]

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: unassignedclangbugs at nondot.org
          Reporter: eric at efcs.ca
                CC: llvm-bugs at lists.llvm.org, mclow.lists at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20161223/ed524ea5/attachment.html>