rust-lang/rust — pull request #16936 by nham (2014-09-02 06:23:27+00:00)
Title: core: Make TwoWaySearcher reset its prefix memory when shifting by byteset

This is primarily an attempt to fix #16878.

The reason we have a false positive in the case of `"1234567ah012345678901ah".contains("hah")` is a bit subtle. Two-Way starts off by factorizing the needle into two halves `(u, v)` based on some criteria. it then checks whether `u` is a suffix of `v[:period(v)]`. If so, it uses what is called "Algorithm CP1" in Crochemore and Rytter's book *Text Algorithms*, and "Algorithm CP2" otherwise. CP2 is optimized for needles with large periods.

`"hah"` happens to get factorized into `("h", "ah")`, which means it runs CP1. As far as I understand, this bug can only occur in CP1, because only CP1 uses an extra variable to memorize prefixes (this is the `memory` field in the `TwoWaySearcher` struct). To quote from Crochemore and Rytter, p. 317:

> The variable s is used to memorize a prefix of the pattern that matches the text at the current position, given the variable pos. Variable s is updated at every mismatch. It can be set to a non-zero value only in the case of a mismatch occurring during the scan of the left part of the pattern.

`self.memory` (which plays the role of `s` in our implementation) actually gets reset to 0 when a mismatch occurs during right scan, but it wasn't being reset to 0 during a jump that occurred via `byteset` mismatch. The `byteset` thing is not a part of the original Two-Way algorithm, and I actually don't understand how it works. But it checks something to determine if we can skip by the entire length of the needle. The fix should be to reset `self.memory` to 0 when doing a byteset skip, because no prefix can match after such a skip (such skips are longer than the skips for mismatches during right scans).

I've also added extensive comments, maybe too many. Let me know if I've gone into too much detail.