Lol, I was taught by Rytter like 20 years ago. He did much more in text algorithms than just correcting B-M. The two books by Crochemore & Rytter are basically the books on text algorithms.
Fix Boyer-Moore searcher with the Rytter correction
21–30 of 56 posts
Re: Fix Boyer-Moore searcher with the Rytter correction
#22Any one know why the Turbo Boyer-Moore algorithm is not more popular. Any case when Boyer Moore would be better?
because BM or BM-horspool is generally very good over all and very few algorithms are always better.
Re: Fix Boyer-Moore searcher with the Rytter correction
#23What is a minimal test case (needle + haystack) for which the old code yields a different result than the new code?
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.
Re: Fix Boyer-Moore searcher with the Rytter correction
#24Nice fix! It's been a while since I've done c++ so does the following code const auto elapsed = steady_clock::now() - start; if (elapsed > 10s) { actually use a units quantifier on the 10, i.e. does 10s mean 10 seconds? Is that a library thing? Cool if so.
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...
And this works because I have `using namespace std;` in the test, which makes all of the Standard Library's "user"-defined literals available. So does `using namespace std::literals;` (without dragging in other names). There's also the extremely fine-grained `using namespace std::chrono_literals;` (no need to type `using namespace std::literals::chrono_literals;` due to how inline namespaces work) which drags in just the chrono duration literals. Finally, `using namespace std::chrono;` drags in all of the chrono names and the chrono literals.
The reason that a using-directive of some kind is necessary is that UDLs are provided by operators, and directly spelling out the operator in order to namespace-qualify it would be self-defeating. (Many people dislike `using namespace std;` and I understand their point, but when one works on the STL all day every day, this using-directive is sure nice for test code.)
My exhaustive test case for this is (demonstrating all the different ways that chrono literals can be accessed): https://github.com/microsoft/STL/blob/31419650d472932dd24b9c...
Re: Fix Boyer-Moore searcher with the Rytter correction
#25What is a minimal test case (needle + haystack) for which the old code yields a different result than the new code?
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".
After comparing the outputs of the old and new algorithms, I believe that a needle needs more than two repeats in order to trigger the bug. That is, "aa" and "abab" don't trigger the bug, but "aaa" and "ababa" do, the last one having a partial third repeat (needle "ababa" with haystack "WXYZababa" was definitely wrong). I tested the table output for "aa" for completeness (and just in case we manage to damage it in the future).
Disclaimer: I don't understand the algorithms deeply enough to write them from scratch, and I'm writing this at 6 AM.
Re: Fix Boyer-Moore searcher with the Rytter correction
#26This guy is a hero! I have so much respect for his work. By i’m still wondering if this bug could have been detected by automatic fuzzing testing ?
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.
Re: Fix Boyer-Moore searcher with the Rytter correction
#27A while back I filed an issue on the MSVC std::vector implementation as the behaviour of a weird corner case differed from GCC/Clang. The reply I got from STL himself was fantastic, pointing out that it was [paraphrasing here] a wart in the spec, and that neither were actually incorrect. To my lasting regret, I didn't keep an ahem offsite backup of some of those corp emails. Hence I can't recall the exact details.
This sounds like the vector>> fiasco, where a vector contains elements that are movable-only (you can't copy a list>, 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 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> 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> 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 :-)
Re: Fix Boyer-Moore searcher with the Rytter correction
#28What is a minimal test case (needle + haystack) for which the old code yields a different result than the new code?
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.
Seems astonishing that nobody has run into this in the wild. How does it do on finding ‘www’ in ‘http://www.example.com/, for example?
Re: Fix Boyer-Moore searcher with the Rytter correction
#29Earlier quoted context omitted.
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.
Seems astonishing that nobody has run into this in the wild. How does it do on finding ‘www’ in ‘ http://www.example.com/ , for example?
I conclude that usage of std::boyer_moore_searcher is relatively low, despite this C++17 feature shipping in VS 2017 15.3 (August 2017).
"www" triggers the bug like all 3-character repeats, but Boyer-Moore manages to find it in "http://www.example.com/" despite the damaged delta2 table, because the incorrect shift value is never exercised. However, a haystack of "https://www.example.com/" triggers the bug, because now the "www" is at an offset of 8.
Re: Fix Boyer-Moore searcher with the Rytter correction
#30So there is potentially a simpler fix than the Rytter correction, is that also yet to discover in published papers somewhere, or do we need to ask Knuth himself?
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!)