main
15
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
  retoorandClaude Sonnet 5
|
7461824de6 |
Bring regexx.c/regexx.h's own file-header comments up to date
Both still described the v1 implementation as a single backtracking engine with no mention of the Pike VM at all, stale since the engine was added several commits ago; regexx.c's went further and never mentioned it even in passing. Updated both to describe the actual dual-engine dispatch, the Pike VM's allocation-free thread model and literal prefilter (concept.md 7.10), and corrected the reentrancy note from a blanket "do not call from more than one thread" to the actual, narrower guarantee this session's PikeEngine design specifically preserved: re_compile and the module level cache still need external synchronization across threads, but Pattern_-prefixed calls on an already-compiled Pattern do not, because nothing mutates a compiled Pattern and PikeEngine is always scoped to one top-level call, never cached on the Pattern itself. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
e4fc067aa6 |
Eliminate the Pike VM's per-thread allocation, add a real BMH literal
prefilter, research and reject a lazy DFA cache Researched two production Pike-VM-family engines directly (RE2's nfa.cc, rust-lang/regex's regex-automata), fetched and read, not recalled, specifically for what explains the two weaknesses the last benchmark found (a*b's nullable loop, dense finditer): both avoid per-thread malloc/free, RE2 via a Thread free list, regex-automata via a flat SlotTable indexed directly by NFA state. Also researched Hyperscan's Teddy (SIMD literal matching) and set it aside: it needs platform-specific intrinsics, in tension with this project's single-file, portable-C, simplicity-over-performance priority: a portable Boyer-Moore-Horspool skip was judged proportionate where Teddy was not. Rewrote the Pike VM's memory model accordingly. PikeThread's owned int64_t* is gone; a committed thread's capture row now lives at a fixed offset in PikeList.table, indexed directly by instruction PC (Cox's one-thread-per-PC invariant already made this index unique, so no allocation is needed to store or discard one). Transient rows needed mid-closure, before the eventual terminal PC is known, come from ScratchPool, a fixed block with an explicit free list; a plain bump/decrement counter was tried first and proven incorrect by hand before being written into the file (an OP_SPLIT's second branch's row can outlive several non-branching pushes that reuse an *earlier* row without reallocating it, which only a real free list handles safely regardless of release order). The closure stack is pre-sized once instead of grown by realloc on demand. All three, plus a reusable best-match buffer and the prefilter below, bundle into one PikeEngine, built once per top level Pattern_/re_ call and reused across every match found within it, never cached on PatternImpl itself (that would make concurrent Pattern_search calls on the same compiled Pattern from different threads race on shared state, breaking the existing no-synchronization-needed guarantee for a Pattern nothing mutates). Extended the literal prefilter from a single leading character to the full mandatory literal prefix, with a real Boyer-Moore-Horspool bad-character skip table for BINARY/ASCII mode (UTF8 keeps a without-skip fallback: a byte-indexed table cannot cover code points past 0x10FFFF). The skip-ahead only ever applies to where a new unanchored start is injected, never to advancing sp itself while a thread from an earlier start position is still alive. Researched and did not build a lazy DFA state cache (memoizing a live-instruction-set-plus-byte transition). Not an omission: RE2's own lazy DFA cannot track submatch boundaries, the same structural reason applies here, since every call wants at least group 0's span, and a cached transition only answers whether a match is possible, not which path was taken; using one would need a two-phase architecture deserving its own research-and-plan pass. Checked empirically too: a*b, the case such a cache would help most, has at most two live instructions at any position for its whole run, so there is no repeated state worth caching in the first place. Verified: full 3,252-case suite (four clean runs), a whitebox dual-engine cross-check extended to also cover finditer/split/BINARY mode (30,000 + 3,334 + 2,500 comparisons, zero mismatches), a targeted suite for the new prefilter machinery including the classic Boyer-Moore-Horspool overlapping-suffix correctness trap (12/12), two clean AddressSanitizer/UndefinedBehaviorSanitizer passes on each (a third run of each hit the same pre-existing sandbox flake already documented, confirmed unrelated by retrying clean). Measured: literal search went from 0.64x of the backtracking engine's time (already ahead) to 0.03x (~33x faster), and against POSIX <regex.h> from roughly 11x slower to roughly 2x *faster* than glibc outright; a*b (no prefilter benefit at all) improved from 3.45x slower than backtracking to 1.97x, from the allocation fix alone; dense finditer over [0-9]+/\w+ improved from 3.2x/5.6x slower to 1.7x/2.8x. Full tables and citations in concept.md 7.10; README.md, docs/API.md, USAGE.md, and bench_vs_posix.c's own printed summary updated throughout with the corrected numbers and the full history, not just the final ones. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
09718eaaf6 |
Add Pattern_groupindex_count/_at, closing the groupindex enumeration gap
README.md and docs/API.md both previously documented "no way to list every name a pattern defines without already knowing what to look for" as an accepted limitation of Pattern_groupindex_lookup being the only access to groupindex. It was not actually a hard constraint: the underlying GroupIndex struct (regexx.c) already stores every name and its group number in two parallel arrays, populated once at compile time; only a public accessor was missing. Pattern_groupindex_count returns the number of named groups; Pattern_groupindex_at(self, i, &name) for 0 <= i < count writes the i-th name and returns its 1-based group number, or returns -1 for an out-of-range i. Enumeration order is declaration order, verified against a real CPython 3.11 interpreter to match groupindex's own practical (insertion-order) iteration order, not just assumed. Verified directly (count/name/group-number correctness, matching the exact snippet now in USAGE.md's own output), full 3,252-case suite unaffected (3252/3252, this is a pure accessor addition touching no matching logic), clean AddressSanitizer/UndefinedBehaviorSanitizer. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
5ae68d4ea6 |
Add a literal prefilter to the Pike VM, profile its memory with Massif
Closed two of the three gaps the previous commit's honest self-review left open (the third, full streaming/bounded-memory input, remains out of scope for this pass and is still documented as such). Literal prefilter (regexx.c, pike_find): when the NFA-only Prog's first instruction is a mandatory OP_CHAR or OP_CLASS, a pattern beginning with a required literal or class rather than a nullable loop or a leading assertion, injecting a fresh unanchored start thread at a position that instruction would reject is certain to die on the very next pike_step call regardless; checking that identical condition before injecting rather than after changes nothing about which threads ever exist, only how much wasted work is done finding out. This targeted exactly examples/bench_vs_posix.c's worst regression: the literal-search scenario went from roughly 70x slower than POSIX <regex.h> (up from roughly 22x before the Pike VM existed) down to roughly 11x-13x, better than the original pre-Pike-VM number; number extraction (starts with a class) improved more modestly; a*b (starts with a nullable loop, structurally unhelped) is unchanged, as expected. Verified with the full 3,252-case suite, three clean AddressSanitizer/UndefinedBehaviorSanitizer passes, and a rerun of the whitebox dual-engine cross-check (24,000 match/fullmatch/search plus ~2,700 finditer comparisons between the two engines on the same compiled patterns, zero mismatches). Memory profiling (concept.md 7.9): Valgrind/Massif on the same adversarial, prefilter-proof pattern shape (a*b, nullable leading loop) used for the backtracking engine's own worst case, for a fair comparison. Peak heap was almost entirely the 10MB input buffer itself; the Pike VM's own contribution was roughly 12KB, confirming the design's O(instruction count x group count), input-length- independent memory bound actually holds for the v1 implementation, not only on paper. concept.md Section 10's table, which had only a "not yet profiled" caveat for this row before, is updated with the measured result. README.md, docs/API.md, USAGE.md, and bench_vs_posix.c's own printed summary are updated throughout with the corrected numbers, rather than left describing the pre-prefilter regression as current. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
f54cda3311 |
Caveat the Pike VM's memory bound in the complexity table, run the dual-engine cross-check the plan called for
Section 10's table stated the Pike VM's O(instruction count x group count) memory bound without the same "as designed, not as measured" caveat 7.5/7.6 already apply to the backtracking engine's own row; added one, honestly noting the bound is structurally plausible (a thread list holds at most one thread per instruction) but not yet independently Massif-profiled the way the backtracking engine's actual number was, and that both engines still hold the whole input in memory in v1 regardless of this row. Also actually built the dual-engine debug mode concept.md 7.7 planned and 7.8 said had not been built (the existing suite's failures had already precisely localized both real bugs without it, so it was not built at the time). Built it now: a whitebox harness toggling PatternImpl.has_nfa on the same compiled Pattern to run match/ fullmatch/search/finditer through both engines directly and compare every result field by field, across 6,000 randomly generated eligible patterns (literals, classes, anchors, quantifiers including lazy and bounded forms, alternation, capturing/non-capturing/named groups, nested combinations, all data modes and flag combinations) against 20 subjects. 20,000 match/fullmatch/search comparisons plus 2,000 finditer comparisons, zero mismatches, clean under AddressSanitizer/ UndefinedBehaviorSanitizer (aside from a signed-overflow bug in the harness's own throwaway PRNG, not shipped code). Not committed as a permanent test target (kept as ad hoc verification, consistent with 7.8's original reasoning for not building it), but the result is real, fresh evidence, not a recycled claim, and is worth having run. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
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 |
||
|
retoorandClaude Sonnet 5
|
71e8bdaaa2 |
Add USAGE.md, a task-oriented guide with compiled and verified examples
docs/API.md is the exhaustive reference; concept.md is the design rationale. Neither is the right document for "I have never used this library before, show me working code," so this adds one that is: compiling a pattern, building an Input from a buffer or a file, match/fullmatch/search, named groups, finditer/findall, split, sub/subn with both template and callback replacement, all six flags, error handling, the module level convenience functions and their cache, re_escape, and a pattern syntax quick reference, each with BINARY, ASCII, or UTF8 examples as appropriate (including the code-point-versus-byte-offset distinction UTF8 mode introduces). Every example was written as a real, compiled program linked against the current regexx.c and run; the output shown in the document is that program's actual output, not a hand-written guess, the same verification standard already used for README.md's own measured numbers. README.md gets a one-line pointer to it alongside the existing pointer to docs/API.md. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
b24d63e5fd |
Reduce memory footprint for large inputs, harden allocation failure paths
Profiled a real search with Massif and found the memory-per-input-byte multiplier at 13.4x, dominated by two avoidable costs: - build_matbuf widened every BINARY/ASCII byte into a uint32_t before matching, a 4x copy that mode never needed (a byte never exceeds 255). Removed it: MCtx/MatBuf now carry an optional text8 (borrowed, unwidened) alongside the existing UTF8 text (owned, decoded code points), reconciled per-read through text_at()/buf_at(). BINARY/ ASCII mode now points directly into the Input's own buffer. - Input_from_file always copied the whole file into a malloc'd buffer. It now mmaps regular files read-only (MAP_PRIVATE) instead, so pages stay clean and reclaimable under memory pressure and the file is never copied. Non-seekable sources (pipes, FIFOs, process substitution, stdin) and mmap failures fall back to the previous incremental-read behavior via a separate read_fd_incrementally. Together these bring the multiplier to 8.4x and let a 200MB file that previously OOM-crashed complete a full non-matching search in about 6 seconds at roughly 1.69GB peak RSS. Also tried, measured, and reverted: capping compute_maxrun/ compute_next_prevmatch's table size with a plain-scan fallback above the cap. A real 200MB non-matching search against this fallback hung for minutes instead of failing fast, because disabling either table reintroduces the O(n^2) behavior they exist to prevent, and O(n^2) at n in the hundreds of millions is not practically finite. A fast, diagnosable allocation failure is a better failure mode than a silent, unbounded hang, so the tables are allocated unconditionally again; the finding is recorded in code comments, concept.md 7.6, and README's "Memory footprint" section so it is not retried blindly later. Separately audited every allocation on an input-proportional path (da_push, build_matbuf's UTF-8 decode loop, all three Input_from_file sites) and made each fail cleanly through PatternError instead of crashing on an unchecked NULL dereference. A 1GB file still exceeds available memory in the current environment; this is a property of the machine it was measured on, not a defect, and is documented as such (practical ceiling: available memory / 8.4 for search-family operations, pending the streaming automaton design in concept.md 7.2). Verified with four clean `make test` passes (3252/3252) and a clean ASan/UBSan pass after the change; rxgrep's mmap-backed paths (--sub with a regular file, with a non-seekable process-substitution source, and BINARY-mode embedded NUL handling) re-checked directly. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
b0991814cb |
Expand BINARY/UTF8/ASCII edge-case testing to 3,252 cases, fix a real LOCALE bug
Three new categories added to tests/cases.py (TEST_PLAN.md records the detail): Category H exercises BINARY mode with genuinely arbitrary raw bytes (embedded NUL, high bytes, non-UTF-8 sequences) via real Python `bytes` subjects, not just UTF-8-encoded text; Category I exercises UTF8 mode edge cases (4-byte/astral code points, combining marks, Arabic, Hebrew, CJK, offset correctness across multi-byte characters); Category J is a fixed-seed (reproducible, not flaky) random generator combining the existing atom/quantifier/grouping vocabulary across all three modes. This found and fixed a real bug, not just a test-generation one: LOCALE, in BINARY/ASCII mode, treated bytes 0x80-0xFF as word characters, based on an unverified assumption about what the "C" locale does. Checked directly against both the C standard's own guarantee for isalnum() under "C" and a real CPython interpreter with re.LOCALE and the "C" locale explicitly set, neither treats anything above 0x7f as a word character. Fixed in regexx.c's cls_is_word; LOCALE is now documented as an accepted no-op in non-UTF8 mode, matching verified reality instead of a prior assumption (concept.md 13.4, docs/API.md, README.md "Known deviations"). Two more findings were test-generation bugs, not regexx bugs: gen.py's own ASCII-mode ground truth used Python str + re.ASCII (code-point space) instead of a bytes pattern against a bytes subject (what regexx's byte-oriented ASCII mode actually is), and LOCALE combined with the (now removed as redundant) auto-added re.ASCII flag raised ValueError in Python for being an incompatible combination. Both fixed in gen.py. Two further findings were concrete instances of an already-documented category (glibc's wctype.h Unicode tables not matching CPython's own exactly): U+00A0 and fullwidth digits U+FF10-FF19 are recognized by CPython's \s/\d but not by glibc's iswspace()/iswdigit() under C.utf8. Recorded in README.md, not patched, for the reason already given for the first such instance (NBSP) in the previous commit. After these fixes: all 3,252 committed cases pass, clean under AddressSanitizer/UndefinedBehaviorSanitizer. The Category J generator was additionally run against 5 more seeds at 3,000 iterations each (26,760 further checks) as exploratory validation, all passing; not committed, to keep the regular suite's size proportionate. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
51f8ed19e9 |
Expand the test suite to 2,247 combinatorial cases, fix two real bugs it found
tests/TEST_PLAN.md records the plan before the result: seven categories (quantifier x grouping x flags, alternation x backreference x groups, lookaround combinatorics, sub/split specifics, real-world combination patterns, mode cross-checks, flag combination stress), each generated programmatically in tests/cases.py rather than hand-typed, still every case checked against a real CPython re result computed by tests/gen.py, per concept.md Section 11's existing strategy, just at 2,247 cases instead of 81. Running it immediately found two real, previously latent bugs, not just confirmed correctness of what was already covered by hand: - tests/gen.py's own C string-literal encoder had a trigraph bug: any generated pattern containing `??)` (the lazy quantifier next to a closing paren) was silently rewritten by the C compiler from 7 bytes to 5 before the suite ever ran, confirmed directly by compiling and printing the corrupted string. Fixed by escaping '?' as '\?', which is always safe and makes trigraph formation impossible. - Pattern_finditer/Pattern_split had a real, previously undocumented correctness defect: CPython's empty-match handling additionally searches for, and reports, a second, non-empty match at the same start position whenever the natural match found there was empty (reverse engineered against a real interpreter, since this is not written down in CPython's own documentation; \d*? against "123abc456" yields 16 matches, not 9). Fixed with a new MCtx forbid_empty flag that forces exactly that second search by rejecting the empty solution at OP_MATCH and letting ordinary backtracking find the next alternative, wired into both functions (they have independent scan loops). concept.md Section 3 and docs/API.md now state the rule precisely instead of the previous, incomplete description. A third, more mundane finding: the combinatorial mode cross-check category surfaced that ASCII-mode ground truth was being computed wrong in tests/gen.py itself (Python str + re.ASCII, which stays in code-point space, instead of a bytes pattern against a bytes subject, which is what regexx's byte-oriented ASCII mode actually is), and separately surfaced a genuine, now precisely documented Unicode-table gap already anticipated in principle by README.md's "Known deviations" (glibc's iswspace() under the C.utf8 locale does not classify U+00A0 NO-BREAK SPACE as whitespace; CPython's \s does). All 2,247 cases pass, clean under AddressSanitizer/UndefinedBehavior- Sanitizer; the 50MB/quadratic-time and ReDoS-scaling benchmarks from the previous two commits are unaffected. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
a9ca517981 |
Bring concept.md and file-header comments in line with the memoization fix
concept.md described the bounded backtracking engine (7.3) as plain recursive backtracking, with the Regular engine's linear-time guarantee reserved for patterns the streaming Pike VM (7.2) handles. v1 has no Pike VM yet, so every pattern actually runs on 7.3's engine; the previous commit added memoization and precomputed skip-ahead tables to that engine specifically because plain backtracking search was quadratic even for ordinary patterns, not just exponential for pathological ones. Added Section 7.5 recording that finding precisely: what the two techniques buy (linear time for the backreference-free majority, quadratic instead of exponential for the textbook (a+)+b shape), what they do not buy (7.2's bounded, input-length-independent memory guarantee, still the correct target for that axis), and citations to the published techniques they match. Added a short note to the Section 10 complexity table pointing at 7.5 so the table is read as the two engines' designed guarantees, not conflated with what a specific implementation measures. Updated regexx.c/regexx.h's top-of-file comments, which still described a plain backtracking engine. No code changes. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
19a7f678a9 |
Fix the search-family quadratic-time defect with memoized backtracking
Root cause: do_one/Pattern_finditer/Pattern_split tried every start position as an independent from-scratch backtracking attempt, so a pattern that ultimately fails, or matches only very late, redid the bulk of its work at every position. Measured: a*b over a run of a's with no b took 19.2s at n=80,000 (quadratic, confirmed by the ~4x slowdown per doubling). Two techniques fix it, researched against and matching published prior art rather than invented ad hoc: - run_memo caches every proven match failure at the (instruction, text position) level, never a success (so it cannot change which match is found), and is only enabled when the compiled program has no OP_BACKREF anywhere, since a backreference's outcome depends on capture history, not on position alone. This is the same "memoize only failures" scheme described in recent work on backtracking regex matchers (Selective Memoization for Efficient Backtracking Regular Expression Matching; Efficient Matching with Memoization for Regexes with Look-around and Atomic Grouping). - compute_maxrun and compute_next_prevmatch precompute, once per Pattern_search/finditer/split call, how far a simple-atom quantifier (OP_REPEAT1) can run from any position and, when it is immediately followed by a single literal/class/., the rightmost position where that next atom can match. This lets the backtrack loop jump straight to candidates worth trying instead of visiting every position in between, the same idea RE2 and Rust's regex crate call a literal prefilter, implemented here with a precomputed array instead of a SIMD memchr/memmem call, in keeping with concept.md's convenience over performance priority. Result: a*b at n=80,000 dropped from 19.2s to 0.0016s, now scaling linearly. As a side effect, since it needs no backreference, the textbook ReDoS pattern (a+)+b also went from exponential (already impractical past n=40) to empirically quadratic (3.2s at n=32,000), though not linear: the inner a+'s OP_REPEAT1 is followed by the group's closing save rather than a simple atom, so the skip-ahead table does not apply to it, only the failure memoization does. README.md and docs/API.md are updated with the measured numbers, the precise remaining limitations, and citations to the sources this was checked against. No test behavior changed: all 81 cases (checked against CPython's own re module output) still pass, clean under AddressSanitizer/UBSan. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
44f0b3eb39 |
Correct a false linear-time claim: search-family ops are quadratic
Auditing the documentation against the actual code (not against what I remembered writing) surfaced a real, previously undocumented defect: README.md claimed a backreference-free, unbounded-lookahead-free pattern "runs in linear time", but that is only true of Pattern_match/ Pattern_fullmatch (one anchored attempt). Pattern_search tries every candidate start position as an independent from-scratch attempt, so it is quadratic in the worst case even for the simplest pattern, since concept.md Section 7.2's engine (which shares work across start positions in one linear pass) is not implemented yet. Measured directly with a*b over a run of plain a's: 0.32s at n=10,000, 19.2s at n=80,000, an ~4x slowdown per doubling. Pattern_finditer/Pattern_split/ Pattern_sub all build on the same search loop and inherit it. README.md and docs/API.md now state this precisely, with the measured numbers, wherever the affected functions are documented, rather than repeating the incorrect blanket "linear time" claim. No code changed; this is a documentation correction only. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |
||
|
retoorandClaude Sonnet 5
|
8f6afd6cd4 |
Add regexx: a single-file C regex interpreter with Python re semantics
concept.md is the full design document: the objective (Python re parity plus binary/ASCII/UTF-8 modes, gigabyte-scale input, single C file), the automata-theory argument for why unrestricted backreferences/lookaround are incompatible with strict single-pass constant memory, the resulting two-engine architecture, the exact Python-mirroring naming convention, and a full comparison against POSIX regex.h for C-background readers. regexx.c/regexx.h are the v1 implementation: parser, compiler to a Pike/backtracking-style bytecode, and a single recursive backtracking engine covering the pattern syntax and operations listed in README.md, validated against CPython's own re module output (tests/), clean under AddressSanitizer/UBSan, and stress-tested (50MB simple-quantifier match, graceful failure rather than a crash on complex repeats over large input, clean rejection of every intentionally unsupported construct). Also included: examples/rxgrep.c (a small grep-like program exercising all three data modes and the substitution API), the Makefile, the MIT LICENSE, and docs/API.md, an exhaustive reference for every type, flag, and function's exact return-value and memory-ownership convention, checked against the current source and against a real CPython interpreter rather than against memory. Co-Authored-By: Claude Sonnet 5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_01EjuMk8kY9SDus1wWe2K9xY |