From 1e5904677535d219e9bba93964e531c786870539 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 29 Sep 2026 15:59:31 -0300 Subject: An Edit x gives each of its searches the step budget, and a search that spends it says it took too much time The budget was the compiled pattern's, spent over every search an x made: Edit ,x/x+/c/z/ over 100k lines ran out and failed, blamed on backtracking. Each search now starts with the whole budget, and one that spends it says regular expression search took too much time, gave up. (Not "too long": 9ns reads those words as ENAMETOOLONG.) Co-Authored-By: Claude Opus 5.5 --- docs/fs.md | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'docs') diff --git a/docs/fs.md b/docs/fs.md index 9ca5f936..5f3ef743 100644 --- a/docs/fs.md +++ b/docs/fs.md @@ -733,9 +733,10 @@ pattern that spans lines, `^`, `$` and `[^...]` keep mvzr's own meaning. 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 gave up, backtracking -past its step budget` rather -than answer a match it is not sure of. Ordinary patterns spend a few +about 300 ms, fails with `regular expression search took too much time, +gave up` rather +than answer a match it is not sure of. The budget is each search's: an +Edit `x` over 100k lines makes 100k searches, each with its own. 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. -- cgit v1.3