pardes.git/src/regexp.zig, branch release-0.24

A backward search along one long line takes time in the line's length, not its square: ?a? over 117 KB goes from 6.4 s to 0.03 s

2026-10-01T03:12:17Z

The 9P fuzzer (seed 124) hung a session for over 5 s on `?a?` in a 117 KB file of one line. A backward search is every forward match up to the limit, so Regex.find ran once per match. Each call looked back from its start to the line's start, and forward to the line's end, over the whole line each time. That is quadratic, and the step budget, which counts only mvzr's steps, never saw it. find now keeps where it last learned a line starts and ends in the same text, and looks back only to there. The literal prefix's look back stops at the known part of the line. Co-Authored-By: Claude Opus 5.5

A pattern anchoring some alternatives with ^ and not others is refused with why, not a bare bad regular expression

2026-10-01T03:12:17Z

`^def|x` and `foo$|^zèbre` were refused with a bare "bad regular expression", the same words as a syntax error, so a script could not tell what to change. They now say "an alternation anchors every branch with ^ or none (^a|^b, not ^a|b)", through addr and Edit alike. fs.md states the rule and that a `$` does not count toward it (`foo$|bar` is fine). Co-Authored-By: Claude Opus 5.5

A class with non-ASCII runes matches them: [éa-z] is taken as (é|[a-z]), a range up to 256 runes spelled out

2026-10-01T03:12:17Z

mvzr's classes hold bytes, and it refused a multibyte member as a bad expression. Rewriting the class before compiling, as ^a|^b already is, needs no mvzr patch; runes that differ only in their last byte go as one alternative (\xc3[\xa0-\xbf] for [à-ÿ]) so a 256-rune range fits the 512-operation limit, which counts the pattern as rewritten. A wider range and [^é] are refused, naming why. Co-Authored-By: Claude Opus 5.5

A search whose pattern opens with a literal jumps to where that literal is, not through every line

2026-10-01T03:12:17Z

Finding /line 049999/ in 1171 KB took 175.5 ms (Debug), each line run through mvzr's matcher in turn. The literal prefix (none when the pattern has a | anywhere) is found with indexOfPos first and matching starts on its line: 4.44 ms. Co-Authored-By: Claude Opus 5.5

A pattern up to 512 characters compiles; a longer one is refused naming the limit

2026-10-01T03:12:16Z

mvzr's Regex holds 64 operations, so a pattern much past 64 bytes was refused as bad regular expression. pardes now compiles into mvzr's SizedRegex(512, 64), and a pattern that is too long (told apart from a malformed one by compiling it with room) says it is longer than mvzr's 512 operations. Co-Authored-By: Claude Opus 5.5

A ^ after | anchors its branch: ^def|^ finds lines starting either way

2026-10-01T03:12:16Z

mvzr takes ^ only at its pattern's start, so in ^def|^ the second branch never matched mid-text. An alternation whose every top-level branch starts with ^ is now compiled as ^(def| ); a mix of anchored and unanchored branches is refused rather than silently wrong. Co-Authored-By: Claude Opus 5.5

A pattern with a newline and an anchor mvzr would misread is refused EINVAL, as the doc says

2026-10-01T03:12:16Z

Its words named no malformed input, so 9ns read the refusal as EIO, and Edit's failed EIO directly. It now says bad regular expression: ..., and Edit's failure with those words is EINVAL too. Co-Authored-By: Claude Opus 5.5

$ may end any alternative in a pattern, not only the last

2026-10-01T03:12:15Z

mvzr refuses $ anywhere but at the very end, so /h$|zz/ and Edit ,x/r$|pi/ were bad patterns while /zz|h$/ worked. Its matcher already ends an alternative at .end, so a build-time patch, anchor-checked like the group one, lets $ stand before | and ). The upstream report is in docs/mvzr-group-backtrack.md. Co-Authored-By: Claude Opus 5.5

A repeat inside a regexp group gives back to what follows the group

2026-10-01T03:12:15Z

On aab, /a+ab/ matched but /(a+)ab/ and /(a*)ab/ missed, and so did (.+)_area and ([a-z_]+)_area, in addr, Edit and look alike. mvzr's hasAlt counts a group's own ) as an alternative, so every group with pattern after it takes matchGroup's alternatives branch, which never tries a repeat's shorter matches. No newer mvzr fixes it (trunk is the pinned commit), so the build patches the fetched source as it does the step budget, anchor-checked: when the rest fails after a group, the group's shorter matches are tried, longest first. docs/mvzr-group-backtrack.md is a report for upstream. Co-Authored-By: Claude Opus 5.5

Merge: 9P round 6 + empty columns + render (acme theme, grips, Lift, Motion)

2026-10-01T03:12:15Z