Fix Boyer-Moore searcher with the Rytter correction (opens in new tab)

The smallest test case appears to be a needle of "aaa" and a haystack of "xxaaa", where VS 2019 16.5's boyer_moore_searcher will report "not found", while the corrected code finds the needle at offset 2 in the haystack.

There are a bunch of test cases here:

https://github.com/microsoft/STL/pull/724/commits/a7da5cce8c...

Looks like it can happen with quite small needles, eg. "aa".

I've implement a few string search algorithms and translating between 1- and 0- based offset functions was the source of a huge number of bugs, as you might expect. For some reason a lot of sources present the algorithms as 1-based.

Speaking of things that make code needlessly difficult to verify, we really need to start insisting on correct (zero-based) indexing in academic algorithms.

Yeah I wrote that Wikipedia article, as much as a single person can. Used the textbook Strings, Trees, and Sequences by Gusfield; it never made mention of Rytter. I wouldn't say Wikipedia is a "terrible" source, though; compared to what? Papers? Textbooks? During the course of my career I've found major technical errors in about half of CS papers. Now the error is being documented & fixed in the Wikipedia article.

My main takeaway was that people should avoid BM in favor of KMP as much as possible if you're writing a string search function, because you're guaranteed to have some bugs when implementing BM. Writing your own string search function seems nearly on the same level as implementing your own cryptographic functions, though.

Interestingly someone reported a bug in my BM sample code on the wikipedia article talk page some years ago (still not yet fixed) which might be related to this Rytter issue. And someone forked my wikipedia article code repo yesterday, which I thought was very weird; must be related to this.

I guess coming to a further defence of wikipedia: as you read technical books & papers (or philosophy!) you see knowledge is extremely unevenly-distributed in society. Much of it is locked up inside these dense, expensive books (if you're lucky!) and even more of it is sitting undigested in papers written for people with five years of postgrad education, and even more is in expert's brains and never put to paper. These barriers stay up for a long time, decades even. We just witnessed one such barrier falling. Wikipedia is an optimal resting place for such liberated knowledge, and I would go so far as to say knowledge that is not on Wikipedia is not yet liberated.

He meant the original paper for calculating delta2 which was merely referenced by the original BM paper.

Sadly this seems to be the pattern for most everything coming from 'academia' ever.

> the books on text algorithms.

And also "Flexible Pattern Matching in Strings" by Navarro and Raffinot.

I believe that fuzz testing would have found it, yes. I'm not sure if fuzz testing would have been guided towards highly repetitive patterns, given the relative lack of branches in the table construction code, but the incorrectly handled patterns can be very short so fuzz testing should have stumbled upon them (given a pattern that generated an incorrect table, finding a haystack which doesn't work is merely a matter of having the needle occur at a specific offset).

Currently we don't fuzz test MSVC's STL, but that is an extremely interesting area to explore in the future. I played around with this a little while working on std::from_chars() (and found no bugs), but it involved actually porting the code to Linux to be compiled with American Fuzzy Lop, so I didn't permanently add such test coverage to our repo.

I know him as the cpp pirate

It’s called user-defined literal suffix in C++11. https://en.cppreference.com/w/cpp/language/user_literal The “s” suffix come with C++14 https://en.cppreference.com/w/cpp/chrono/operator%22%22s

that's a user defined literal, a language feature: https://en.cppreference.com/w/cpp/language/user_literal

the std::chrono library reserved some suffixes (under std::literals::chrono_literals) for time units https://en.cppreference.com/w/cpp/symbol_index/chrono_litera...

This sounds like the vector<list<unique_ptr<T>>> fiasco, where a vector contains elements that are movable-only (you can't copy a list<unique_ptr<T>>, only move it), yet with throwing move constructors (as MSVC's list, set, and other node-based containers dynamically allocate sentinel nodes when default/move-constructed - this is a behavior difference from GCC's libstdc++ and Clang's libc++, where both dynamically-allocated and container-internal sentinel nodes are permitted by the Standard). The doom begins when STL containers like list (also vector itself) don't have "constrained copy constructors" - that is, list(const list&) always appears to be available, as far as type traits like is_copy_constructible are concerned, even if that copy constructor can't actually compile. The doom accelerates when vector<Elem> needs to ask the question "are you nothrow-movable? If so, I can move you efficiently. Otherwise, are you copyable? If so, I can fall back to copying you during reallocation, in order to preserve the strong exception guarantee. Otherwise, you're throwing movable-only, so I'll move you and you get the basic guarantee". The doom is complete when list<unique_ptr<T>> correctly reports that it isn't nothrow-move-constructible (it would throw due to allocating a sentinel), yet incorrectly claims to be is_copy_constructible. Therefore the vector tries to copy the list<unique_ptr<T>> and that fails to instantiate, resulting in an epic compiler error.

This situation is a fiasco because there is no good way out of it (constraining container copy constructors isn't possible because the Standard permits incomplete element types for many containers, and users use them for other containers even though they technically shouldn't, weakening EH guarantees is potentially problematic, changing the nature of sentinel nodes is ABI-breaking and affects iterator invalidation guarantees). It is also highly memorable, which is why I can guess what it was :-)

There are literally hundreds of string search algorithms published now (including a large number of Boyer Moore variants).

There's a great resource called SMART for those interested in exploring this, with implementations of many of them and a simple benchmarking tool.

https://smart-tool.github.io/smart/

Although Boyer Moore is well known, there are generally faster algorithms available these days.

For short patterns, SHIFTOR will tend to be a lot faster than BM. Even the much simpler variant of BM, Horspool is usually faster than BM.

This highlights an interesting tension in search algorithm design. Often a simpler algorithm outperforms one with theoretically higher performance, but not always!

1. What empirical data we have suggests that the 'good suffix' rule engages fairly rarely; that's why the -Horspool variant wins most tests. (It isn't just that you don't have to build Delta2, it also saves a lot of comparisons in the algorithm itself for most inputs.) 2. Because the standard says this is the Boyer-Moore algorithm :D

because BM or BM-horspool is generally very good over all and very few algorithms are always better.

Exactly the same problem occurs with legislation. For years this was solved by third-parties publishing enormous annotated legal references. Nowadays the government (in the UK anyway) publishes legislation online incorporating all the edits made by later legislation.

Knuth's TAOCP serves as an annotated third-party reference, except that in this case he's not a third-party. I don't have a copy to hand to see if it has the correct version of the algorithm.

Apparently there are multiple fixes, some of which are said to be simpler. See https://github.com/microsoft/STL/issues/727 and the cited comments within, which quote Knuth. (I'm learning a lot by having this PR appear on HN!)