main
2
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
  retoorandClaude Sonnet 5
|
fa07622671 |
Add a Pike VM (regular engine, concept.md 7.2), dispatched automatically
Researched first (Cox's regexp2 article, the submatch/tagged-NFA follow-up crediting Laurikari, and rust-lang/regex's PikeVM source for the exact leftmost-first mid-search Match handling), then planned in concept.md 7.7 before writing any code, per the explicit instruction to plan before implementing. The existing bytecode compiler turned out to already produce valid Thompson-construction NFA bytecode (OP_SPLIT/OP_JMP/OP_SAVE match Cox's instruction set almost exactly), so no new compiler was needed: Prog gained one field (no_repeat1) and compile_repeat one condition, letting the same compile_node produce a second, NFA-only Prog from the same AST for any pattern containing none of OP_BACKREF/OP_LOOKAHEAD/ OP_LOOKBEHIND/OP_ATOMIC (a possessive quantifier already desugars to the last of these at parse time). That second Prog is matched by a new Pike VM (pike_addthread/pike_step/pike_find): a breadth-first thread list simulation with per-thread capture arrays, epsilon closure implemented with an explicit heap stack rather than C recursion so a pattern with many alternations cannot recurse the C stack, every allocation checked and failing through the existing -1 error convention rather than a NULL dereference. do_one, Pattern_finditer, and Pattern_split each gained an impl->has_nfa branch to this engine, sharing one small helper (find_next) for the "unanchored scan from a position" versus "single anchored attempt at a position" distinction finditer/split's empty-match retry needs. Two real bugs, both found and precisely localized by the existing 3,252-case CPython-derived suite without writing a single test specifically for this engine: OP_MATCH not writing group 0's end position (it has no OP_SAVE; run()'s own OP_MATCH handler sets it directly, and this engine's first version missed replicating that), and an unconditional "thread list empty -> stop" early exit that is wrong for unanchored search specifically, since a freshly injected start thread can die immediately in its own epsilon closure (a leading \b failing outright, repeatedly, inside a longer word like "catalog" for \bcat\b) without that meaning every later position would too. Both fixed; full suite passes, three clean AddressSanitizer/ UndefinedBehaviorSanitizer runs, plus hand-written whitebox checks (a 20,000-branch alternation, UTF8 named groups, BINARY matching across an embedded NUL, greedy/lazy and alternation priority). Measured result: (a+)+b, this project's own running example of the backtracking engine's remaining weak spot, is Pike VM eligible and now measures as genuinely linear (0.0018s to 0.0308s, n=10,000 to 160,000), not merely improved. Measured cost: re-running bench_vs_posix.c's three ordinary scenarios (all now Pike VM eligible too) found the gap to POSIX <regex.h> widened, from roughly 2x-25x before this engine existed to roughly 8x-70x now, the direct, expected cost of this engine's performance axis being explicitly deferred (no literal prefilter, no lazy DFA state caching, no allocation pooling) in favor of correctness first, per the instruction this was built under. Both results, and the reasoning behind deferring the second, are recorded in concept.md 7.7/7.8. README.md, docs/API.md, USAGE.md, and examples/redos_atomic.c and bench_vs_posix.c are updated throughout to describe the new two-engine dispatch accurately, including this real trade-off, rather than leaving the previous single-engine description in place; redos_atomic.c specifically now shows both that (a+)+b no longer needs an atomic group at all and a backreference-forced variant where one still does. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
02743cd959 |
Add six feature examples and a direct benchmark against POSIX <regex.h>
Each new program under examples/ isolates one distinct feature rather than being a general purpose tool like the existing rxgrep.c: binary_scan.c (raw byte-range classes including an embedded NUL and an embedded 0x0A), utf8_scripts.c (\w across Latin/Greek/Cyrillic/CJK text, code point versus byte offsets), ascii_logparse.c (named groups against structured log text), redos_atomic.c (atomic groups and possessive quantifiers timed directly against the unprotected form of the textbook (a+)+b ReDoS shape), empty_match_rule.c (CPython's undocumented empty-match retry rule, verified: \d*? against "123abc456" gives 16 matches, not 9), and large_file_search.c (Input_from_file's mmap-backed reading on a generated 100MB file, with elapsed time and peak RSS printed). Every example was compiled and run while writing it; the claims in each file's top comment are checked against its own output, not written by hand and left unverified. Also adds examples/bench_vs_posix.c, a direct, honestly reported comparison against the C standard library's own <regex.h> (regcomp/regexec) on six scenarios at multi-megabyte or multi-hundred-thousand-line scale, using only pattern syntax valid for both engines so they run the identical pattern text. glibc's DFA-backed engine wins five of six scenarios by 2x-35x, which is the expected outcome of a roughly 2000-line backtracking interpreter built for Python `re` compatibility competing against a mature, heavily optimized engine with a much smaller feature set; the sixth scenario has no POSIX equivalent at all (an atomic group). Every scenario's match count is cross-checked between the two engines as an independent correctness signal beyond the existing CPython-derived test suite. Two real issues were found and fixed while building this benchmark, not left in: iterating regexec() over an advancing string pointer is quadratic in practice (no way to bound the search without an implicit NUL-scan on every call), fixed by using REG_STARTEND instead; and a signed integer overflow (undefined behavior, caught by UBSan) in the benchmark's own pseudo-random text generator, fixed by using an unsigned accumulator. README.md and USAGE.md gain pointers to examples/README.md (the new per-example index) and a "Benchmarks" section summarizing the POSIX comparison honestly, including where it loses. The Makefile gains a `make examples` target building all seven programs. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |