A regular expression search is bounded by a step budget patched into mvzr, not windows and a repeat cap

The windows returned wrong matches: a candidate reaching a window's edge was
left to the next window, half a window on, which could answer a match starting
mid-token rather than the leftmost, and addr then pointed data's next write at
the wrong bytes. The repeat cap missed mvzr's own worst case, a chain of a?,
and alternation under a repeat, each exponential inside one mvzr call the
deadline could not interrupt; and it refused ordinary s/S patterns. build.zig
now patches the fetched mvzr at build time with a step counter on its
backtracking recursion (matchPattern), so a fresh fetch keeps it and a moved
anchor stops the build; regexp.zig gives each compiled pattern a budget, about
300 ms here, and a search that spends it fails as taking too long. Windows,
the cap and their special cases are gone, and matches are exact again.

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

2 files changed, 11 insertions, 12 deletions

diff --git a/docs/fs.md b/docs/fs.md
index c9b268b0..a2d8a9b2 100644
--- a/docs/fs.md
+++ b/docs/fs.md
@@ -288,21 +288,20 @@ the alternatives at that place mvzr takes the first that matches where sam
 takes the longest (`/gam|gamma/` finds `gam`); in a search begun in the
 middle of a line, `^` inside an alternation can match there; and in a
 pattern that spans lines, `^`, `$` and `[^...]` keep mvzr's own meaning.
-mvzr backtracks without bound (`a*a*a*a*x` over a hundred `a`s takes a
-second), and a search holds the editor, so a pattern with more than four
-repeats (`*`, `+`, `{m,n}`) is refused as `regular expression has more than
-four repeats`, a long line is searched in overlapping windows (64 KB for
-a pattern with at most one repeat, 256, 96 and 40 bytes for two, three and
-four), where a match longer than half a window can be missed, and a
-search still running after 300 ms fails with `regular expression search
-took too long`.
+mvzr backtracks without bound of its own (`a?` twenty times then twenty
+`a`s is 2^20 steps from each place it tries), and a search holds the editor, so pardes patches a
+step budget into mvzr's matcher (build.zig): a search that spends it,
+about 300 ms, fails with `regular expression search took too long` rather
+than answer a match it is not sure of. Ordinary patterns spend a few
+thousand steps; what runs out is exponential backtracking, and a quadratic
+pattern over a very long line (`\s*(\w+)\s*=` over 20 KB of letters).
 pardes has no regex engine of its own on purpose; these are its limits.
 Normal mode's `s` and `S` search a selection the same way (src/regexp.zig
 is the one place both call), so `^` there also means a line's start.
 
 An address that does not evaluate fails the write with why: `bad address
 syntax`, `no match for regexp`, `address out of range`, `bad regular
-expression` or one of the two costs above. A failed write to `addr` leaves no address at all, where acme
+expression` or `regular expression search took too long`. A failed write to `addr` leaves no address at all, where acme
 keeps the old one: until an address is written or `addr` is truncated,
 reading `addr`, and reading, writing or truncating `data` and `xdata`, fail
 with `no address: the last one written to addr failed`, so a script that
diff --git a/docs/helix-keys.md b/docs/helix-keys.md
index 087b83d0..41f9b364 100644
--- a/docs/helix-keys.md
+++ b/docs/helix-keys.md
@@ -250,9 +250,9 @@ compiles a runtime pattern with no allocator, called the way sam searches
 haystack, so `^` and `$` match at every line's start and end and `.` never
 crosses a newline, and a pattern naming `\n` runs over the whole selection.
 Where helix's `^` is only the selection's start, this is sam's. mvzr
-backtracks without bound, so the caps docs/fs.md gives for `addr` hold
-here too: more than four repeats will not compile (the selection is left
-alone) and a search past 300 ms keeps the matches it found so far.
+backtracks without bound of its own, so the step budget docs/fs.md gives
+for `addr` holds here too: a search that runs out of it (about 300 ms)
+keeps the matches it found so far.
 
 | Key | Behavior | Notes | Status |
 | --- | --- | --- | --- |