A regular expression search comes back: costly patterns refused, long lines windowed, 300 ms deadline

mvzr backtracks with no bound on its work (a*a*a*a*x over a hundred a's takes a
second, each repeat multiplying by the haystack length), and a search runs holding
the editor's turn, so one pasted pattern froze the editor. pardes does not write or
vendor a regex engine, so regexp.zig bounds what it hands mvzr: more than four
repeats is refused, a line longer than a window sized from measured worst cases is
searched in half-overlapping windows, and a deadline stops the search. addr names
each failure; normal s/S keeps what it found. The prescan also stops reading an
escaped backslash before n as a newline, and ends a class where mvzr does.

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

2 files changed, 14 insertions, 3 deletions

diff --git a/docs/fs.md b/docs/fs.md
index 3b49105d..2c565ade 100644
--- a/docs/fs.md
+++ b/docs/fs.md
@@ -280,13 +280,21 @@ 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`.
 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` or `bad regular
-expression`. A failed write to `addr` leaves no address at all, where acme
+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
 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 f2855b3a..087b83d0 100644
--- a/docs/helix-keys.md
+++ b/docs/helix-keys.md
@@ -249,7 +249,10 @@ compiles a runtime pattern with no allocator, called the way sam searches
 (`src/regexp.zig`, shared with a pane's `addr` file): each line is its own
 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.
+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.
 
 | Key | Behavior | Notes | Status |
 | --- | --- | --- | --- |