Match rules

Byte offsets

A match covers [start, stop). Its length is stop - start. Extract it with String.sub text start (stop - start).

input:    u s h e r s
offset:   0 1 2 3 4 5 6
she:        [-----)       1..4
he:           [---)       2..4
hers:         [-------)   2..6

Overlapping matches

find_all, find_iter, and Stream.feed report every occurrence. Order is increasing end offset, then longest first, then lowest pattern index for identical spans.

Non-overlapping matches

Earliest end: Stream.feed_nonoverlapping takes the first match to finish, preferring the longest at that end position, then the lowest pattern index. Scanning restarts after it.

Leftmost-longest: choose the earliest start, then the longest match, then the lowest pattern index. Continue after the match. This drives find_leftmost_longest, replace_all, and the two leftmost-longest streaming modules.

Patterns and case

• Literal bytes, including NUL. UTF-8 offsets are byte offsets.
• ~ignore_case:true folds ASCII A–Z only.
• Duplicate patterns have separate IDs; selection ties use the lowest ID.
• An empty pattern list matches nothing; an empty pattern string raises Invalid_argument.

Streaming

Overlapping and earliest-end modes need no flush or retained input. Leftmost-longest modes retain candidates in a window bounded by the longest pattern length. Replacement also retains at most that many input bytes. Call flush at end of input.

Use the same automaton for every call. Keep the returned state; states are immutable. Total offsets must fit in an OCaml int.

Performance

Search is O(input + matches examined). Overlapping modes allocate all reported matches. Leftmost-longest modes keep only the best match for each possible start in a longest-pattern window and do not sort.

Shallow automaton nodes have resolved 256-entry transition rows; deeper nodes use sorted child arrays and failure links. There is no SIMD prefilter.

See the full cost table.