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/helix-keys.md | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'docs/helix-keys.md') 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 | | --- | --- | --- | --- | -- cgit v1.3