| Commit message (Collapse) | Author | Age |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
its square: ?a? over 117 KB goes from 6.4 s to 0.03 s
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 <[email protected]>
|
| |
|
|
|
|
|
|
|
|
|
|
| |
why, not a bare bad regular expression
`^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 <[email protected]>
|
| |
|
|
|
|
|
|
| |
range up to 256 runes spelled out
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 <[email protected]>
|
| |
|
|
|
|
|
|
| |
not through every line
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 <[email protected]>
|
| |
|
|
|
|
|
|
| |
limit
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 <[email protected]>
|
| |
|
|
|
|
| |
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 <[email protected]>
|
| |
|
|
|
|
|
|
| |
as the doc says
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 <[email protected]>
|
| |
|
|
|
|
|
|
|
|
| |
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 <[email protected]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
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 <[email protected]>
|
| |\ \ |
|
| | |/
| |
| |
| | |
Co-Authored-By: Claude Opus 5.5 <[email protected]>
|
| |/
|
|
|
|
|
|
| |
work is refused
A pattern naming a newline runs over the whole text, where mvzr's ^ is only the text's start: /^def .*\n/ from #0 failed, and Edit ,x/^def .*\n/.../ silently did nothing. A leading ^ is now tried at each line start from the search's own; $ just before \n is dropped, as it changes nothing; any other ^ or $ in such a pattern is refused with why, since mvzr would read it as the text's ends. ^ inside an alternation holds only where a search starts, an mvzr limit, documented.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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 <[email protected]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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]>
|
|
|
The sam-style calling convention for mvzr (a line per haystack, . made
[^\\n] only when a pattern names \\n) lived in addr.zig; normal mode's s
and S called mvzr over the raw selection, where ^ meant the selection's
start and . crossed lines. src/regexp.zig now holds the one Regex
(compile, find) both call, and fs.zig and pardes.zig drop an unused mvzr
import. hxdiff and hxparity stay at their known 17 and 6 mismatches, none
of them regex cases.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
|
