From c8a3ecc3bcb36f0259f4d8ad2e0cdfcdc3183c9f Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Mon, 28 Sep 2026 12:39:43 -0300 Subject: 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 --- docs/fs.md | 17 ++++++++--------- 1 file changed, 8 insertions(+), 9 deletions(-) (limited to 'docs/fs.md') 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 -- cgit v1.3