Mica::Core::ByteSearch
Substring search in linear time, for query engines that run caller- or
attacker-supplied patterns (stdlib String#index(String) is a
Rabin-Karp search with a fixed base, so crafted inputs can make it
quadratic).
The search is Knuth-Morris-Pratt over bytes: at most
2 * haystack.size + 2 * needle.size comparisons, plus needle.size
steps for allocating the failure table, all reported to the step block
before they happen. UTF-8 is
self-synchronizing, so a byte match of a valid UTF-8 needle in valid
UTF-8 text always starts on a character boundary.
Constants
Comparisons between two calls of the step block.
Class methods
Returns the byte offset of the first occurrence of needle in
haystack, or nil. The block is called with the number of
comparisons about to be made, in blocks of at most STEP_CHUNK
(while building the failure table and while scanning), before they
run, so a work meter can stop a long search before its work.
Mica::Core::ByteSearch.index("aaab".to_slice, "ab".to_slice) # => 2