Prefilter matches

[jongiddy]

Some questions about the prefilter that aren't covered by the current documentation:

1. If aho_corasick is a pattern, a haystack of some aho_c returns a PossibleStartOfMatch starting at the a. Can this behaviour be relied on, or is it an accident of the implementation? The current behavior is useful for streams but, following the documentation, the implementation could return NoMatch for this case.
2. When a Match(m) is returned by the prefilter, where is the best position to restart the scan? m.start() + 1 or m.end()?

[BurntSushi]

1. If aho_corasick is a pattern, a haystack of some aho_c returns a PossibleStartOfMatch starting at the a. Can this behaviour be relied on, or is it an accident of the implementation? The current behavior is useful for streams but, following the documentation, the implementation could return NoMatch for this case.

It definitely cannot be relied upon. The only thing you can rely upon is that a prefilter never has any false negatives. It can have false positives, but which false positives it has is implementation defined.

2. When a Match(m) is returned by the prefilter, where is the best position to restart the scan? m.start() + 1 or m.end()?

It probably depends on what you're doing. Either are potentially valid. I believe m.end() is okay so long as you're doing a non-overlapping search. In the case of an overlapping search, probably even m.start() + 1 is wrong because you need to check if there are any other matches at the same position.

[jongiddy]

OK, so if the prefilter reports a Match there is not even a guarantee that this is the only match starting at this position? I expected that Match provides a unique match at position m.start(). So to find overlapping matches, Match needs to be treated the same as PossibleStartOfMatch and use the start to begin scanning with Automaton::start_state?

[BurntSushi]

Yes. The overlapping case is tricky.

[jongiddy]

Thanks for answering.

I was able to find that my example in point 1 does indeed return NoMatch if aho_corasick is the only pattern. It only returns PossibleStartOfMatch if there are multiple patterns.

[BurntSushi]

Right, because when there is only one pattern, it will defer to memmem. Multiple patterns might trigger a simple memchr or perhaps Teddy. All of these will give different results but will be consistent with the documented guarantees.