A backward search along one long line takes time in the line's length, not its square: ?a? over 117 KB goes from 6.4 s to 0.03 s

The 9P fuzzer (seed 124) hung a session for over 5 s on `?a?` in a
117 KB file of one line. A backward search is every forward match up to
the limit, so Regex.find ran once per match. Each call looked back from its
start to the line's start, and forward to the line's end, over the whole
line each time. That is quadratic, and the step budget, which counts only
mvzr's steps, never saw it. find now keeps where it last learned a line
starts and ends in the same text, and looks back only to there. The
literal prefix's look back stops at the known part of the line.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

0 files changed, 0 insertions, 0 deletions