regexx/concept.md

Concept: A Single File C Regex Interpreter with Python re Semantics

1. Objective

The objective is a regex interpreter, implemented as a single C source file, that reproduces the observable behavior of Python's re module (pattern syntax, flags, and the match, search, fullmatch, findall, finditer, split, sub, and subn operations) while being usable on inputs of arbitrary size, including multi-gigabyte files, without holding the entire input in memory. The implementation is required to operate in three data modes: binary (arbitrary byte streams), ASCII text, and UTF-8 text. Simplicity of the C code takes priority over raw execution speed.

Sections 2 through 4 record what "full Python re support" concretely means. Section 5 records why an unrestricted single pass, constant memory implementation of that full feature set is not mathematically possible, and states the boundary precisely. Sections 6 through 12 describe the architecture chosen to get as close to the objective as that boundary allows, in the simplest C design found. Section 13 lists the residual gaps against CPython's re. Section 14 records, for a reader coming from C rather than Python, the respects in which the native C regular expression facility (POSIX regex.h) differs from Python re, and therefore from this design, none of which this design adopts beyond what Section 1 already asks for.

2. Reference Semantics: Python re Pattern Syntax

The engine parses the following syntax, matching CPython's documented and observed behavior.

2.1 Atoms and literals

• Literal characters (bytes in binary/ASCII mode, decoded code points in UTF-8 mode).
• . matches any character except \n, or any character at all under DOTALL.
• \ followed by a non-alphanumeric character is that literal character.
• Escapes: \n \r \t \f \v \a \0, octal \ooo, hexadecimal \xhh, \uxxxx, \Uxxxxxxxx, and named code points \N{NAME} (requires a Unicode name table; see 13.3).

2.2 Character classes

• [...] with ranges (a-z), negation ([^...]), and literal ], -, ^ when escaped or positionally safe, matching CPython's class parser exactly (including that ] as the first class member is literal).
• Shorthand classes \d \D \w \W \s \S, each with an ASCII definition and a Unicode definition, selected by mode and by the ASCII/UNICODE flags exactly as CPython selects them for str versus bytes patterns.
• \b and \B (word boundary and non boundary), defined with the same "word character" set as \w in the active mode.

2.3 Anchors

• ^ and $: string boundaries by default; line boundaries under MULTILINE.
• \A and \Z: string boundaries, unaffected by MULTILINE.

2.4 Quantifiers

• Greedy: * + ? {m,n} {m,} {,n} {m}.
• Lazy: *? +? ?? {m,n}?.
• Possessive (CPython 3.11 and later): *+ ++ ?+ {m,n}+.
• Atomic groups (CPython 3.11 and later): (?>...).

2.5 Groups and grouping constructs

• (...) capturing group, numbered left to right by opening parenthesis.
• (?:...) non capturing group.
• (?P<name>...) named capturing group; (?P=name) named backreference; \1..\99 numbered backreference; \g<name> and \g<1> backreference forms usable inside a pattern as well as in a replacement string.
• (?#...) comment, discarded at parse time.
• (?=...), (?!...): lookahead, positive and negative, of unrestricted width.
• (?<=...), (?<!...): lookbehind, positive and negative. CPython requires the lookbehind body to be fixed width (a fixed number of characters, alternation of equal width branches permitted); the engine enforces the same restriction at compile time and rejects variable width lookbehind with a compile error, matching CPython's error: look-behind requires fixed-width pattern.
• (?(id)yes|no) and (?(name)yes|no): conditional branch on whether a numbered or named group has already matched; the |no branch is optional ((?(id)yes) is valid, matching CPython, with an implicit empty "no" branch).
• (?aiLmsux) global inline flags, valid only at the start of the pattern, and (?aiLmsux-imsx:...) scoped inline flags valid anywhere, matching CPython's restriction that only i, m, s, x are removable and a, L, u are global only.
• | alternation, ordered, first match wins (not longest match), matching backtracking semantics rather than POSIX leftmost longest.

2.6 Flags

IGNORECASE, MULTILINE, DOTALL, VERBOSE (whitespace and # comments outside classes and outside escapes are ignored), ASCII, UNICODE (default for text mode), LOCALE (accepted for compatibility; see 13.4 for what it does under the "C" locale this design commits to, which, verified directly against a real CPython interpreter, turns out to be nothing beyond plain ASCII classification), DEBUG (accepted, prints the compiled program instead of executing it).

3. Reference Semantics: Python re Operations

• match(pattern, string): anchored at position 0, not required to consume the whole string.
• fullmatch(pattern, string): anchored at position 0 and at the end of the string.
• search(pattern, string): first match anywhere.
• finditer / findall: all non overlapping matches, left to right. The precise CPython 3.7+ empty-match rule, reverse engineered against a real interpreter since it is not fully spelled out in CPython's own documentation: at each scan position, the ordinary (greedy/lazy, as the pattern specifies) match is found and reported first; if that match was empty, a second match, requiring non-empty this time, is additionally searched for and reported at that same starting position if one exists (confirmed with \d*? against "123abc456": CPython's finditer yields (0,0), then (0,1), then (1,1), then (1,2), and so on, an empty match immediately followed by a non-empty one at the same start, not two separate scan positions); the scan then advances to the end of whichever of the two was reported last, or by one position if only the empty match existed. split and sub/subn are built on the same scan and inherit the same rule.
• split(pattern, string, maxsplit=0): text of capturing groups is interleaved into the result list, matching CPython; splitting on a pattern that can match an empty string is permitted, matching the CPython 3.7+ behavior change.
• sub(pattern, repl, string, count=0) / subn: repl is either a template string honoring \g<name>, \g<1>, \1, and literal backslash escapes, or a callback invoked once per match with a match record and expected to return replacement bytes/text (the C equivalent of a Python callable, see 9.4).
• escape(string): backslash escaping of all characters outside [A-Za-z0-9_] in the same way re.escape does since Python 3.7 (that version narrowed the escaped set relative to earlier Python releases; the engine follows the narrowed, current set).
• Match record fields: group(n), group(name), groups(), groupdict(), start(n), end(n), span(n), lastindex, lastgroup.

4. Feature Compatibility Table

Feature	Status
Literals, classes, anchors, quantifiers (greedy/lazy)	Full
Alternation, grouping, named groups	Full
Backreferences (pattern and replacement)	Full, bounded (Section 5)
Lookahead, fixed width	Full
Lookahead, unbounded width	Full, bounded (Section 5), same window as backreferences
Lookbehind, fixed width	Full
Lookbehind, variable width	Rejected at compile time, as in CPython
Conditional groups `(?(id)yes	no)`
Possessive quantifiers, atomic groups	Full (OP_ATOMIC, Section 7.1)
Inline and scoped flags	Full
\N{NAME} named code points	Partial (Section 13.3)
Full Unicode \w/\s/IGNORECASE case folding	Partial (Section 13.3)
LOCALE flag beyond the "C" locale	Not supported (Section 13.4)
Streaming over unbounded input	Full for the regular subset, bounded window for backreferences/lookaround (Section 5)

5. The Single Pass, Bounded Memory Constraint

This section states a limit that shapes the rest of the design, so it is recorded before the architecture.

A pattern language restricted to literals, classes, anchors, quantifiers, grouping, and alternation is a regular language. Regular languages are recognized by a finite automaton, and a finite automaton processes an input stream in one pass, in time linear in the input length, using memory bounded by the automaton's state count, independent of input length. Thompson's construction (converting a pattern to a nondeterministic finite automaton) and its simulation without backtracking (the approach used by grep -E, awk, RE2, and Rob Pike's regular expression virtual machine) achieve exactly this, including for findall style capture extraction.

Backreferences (\1, (?P=name)) break this property. No fixed size finite automaton recognizes a language defined with a backreference in general, because such an automaton would need to remember an arbitrarily long previously matched substring verbatim and compare it later, and a finite automaton has, by definition, only finitely many states with which to do so. The precise formal result here is a combined complexity result: deciding whether a string matches a pattern is NP-hard when both the pattern and the string are counted as part of the problem input. That result does not, by itself, say anything about a fixed pattern, compiled once, matched against a growing string, which is this design's actual situation; for a fixed pattern the practically relevant obstacle is different and better known by name, worst case exponential backtracking time in the length of the string, the mechanism behind catastrophic backtracking (commonly called ReDoS) in every production backtracking engine, including CPython's own _sre. Unbounded width lookahead and lookbehind create the same obstacle for a related reason: resolving them can require holding an unbounded span of the input, forward or backward, before the assertion's truth value is known. This is a property of the language class and of the evaluation strategy required to decide it, not of any particular implementation choice, and it means a literal reading of "full Python re support" and "does not remain in memory or hold the input" are mutually exclusive whenever a pattern actually uses a backreference or an unbounded width lookaround on unbounded input.

The engine resolves this by splitting execution into two engines sharing one bytecode format:

1. Regular engine. Any compiled pattern that contains no backreference and no lookaround whose body has unbounded width is executed by a Thompson/Pike style simulation: single pass, one buffered chunk of input at a time, memory bounded by the number of program instructions multiplied by the number of capture groups, independent of input length. This covers the large majority of patterns used in practice, including nested quantifiers, alternation, and fixed width lookaround.

2. Bounded backtracking engine. Any compiled pattern that contains a backreference or an unbounded width lookahead (fixed width lookaround of either polarity always stays in the regular engine, per 7.1) is executed by a backtracking simulation over a sliding window of the input, of a fixed configurable size (default 1 MiB, see 7.3). This engine gives exact CPython semantics as long as the text a backreference or lookahead needs to inspect fits inside the window relative to the current match attempt. If it does not, the engine reports a recoverable error (ERANGE-style status) identifying the offending construct and offset, rather than silently returning a wrong answer or reading the whole file into memory. This is the same trade every production streaming text tool with backreference support makes; the engine documents the bound instead of hiding it.

This split is decided once, at compile time, from the parsed pattern, before any input is read. A caller who needs a hard guarantee of bounded memory on arbitrary input can inspect the compiled pattern's engine selection before running it.

6. Architecture Overview

Single C file, four sections in this order, each independent of the ones after it:

1. Parser: pattern text to abstract syntax tree (AST). Recursive descent, one function per grammar production (parse_alt, parse_concat, parse_repeat, parse_atom), matching the structure of the grammar in Section 2 directly, so the parser can be read as an executable grammar.
2. Compiler: AST to bytecode, by direct recursive translation (Thompson's construction), one code generation function per AST node kind. Same bytecode format is emitted regardless of which of the two engines (5.1/5.2) will run it; the engine choice is a separate flag computed from the AST (does it contain OP_BACKREF, or an OP_LOOKAHEAD whose body width is unbounded; CPython already forces OP_LOOKBEHIND to be fixed width, Section 2.5, so lookbehind never contributes to this flag).
3. Engines: the regular engine (Pike VM) and the bounded backtracking engine (recursive backtracking over the sliding window), described in Section 7.
4. Public API: the Python re equivalent entry points, described in Section 9.

Keeping parser, compiler, and both engines as pure functions over explicit structs (no hidden global state except one user supplied allocator, see 8.1) is what keeps the single file simple to read despite covering the full grammar.

7. Execution Engines

7.1 Bytecode

One flat instruction set, an array of tagged structs, used by both engines:

enum opcode {
    OP_CHAR,        /* match one literal byte/codepoint            */
    OP_CLASS,       /* match one byte/codepoint against a class     */
    OP_ANY,         /* match one byte/codepoint, DOTALL-sensitive   */
    OP_SPLIT,       /* two continuations (alternation, quantifiers) */
    OP_JMP,
    OP_SAVE,        /* record current offset into capture slot N    */
    OP_MATCH,
    OP_ASSERT,      /* zero-width: ^ $ \b \B \A \Z                  */
    OP_BACKREF,     /* forces bounded backtracking engine            */
    OP_LOOKAHEAD,   /* sub-program, zero-width, polarity flag        */
    OP_LOOKBEHIND,  /* sub-program, fixed width, zero-width, polarity*/
    OP_ATOMIC,      /* sub-program, consuming, discards choice points */
    OP_COND,        /* branch on whether group N has matched         */
};

struct inst { enum opcode op; int32_t x, y; uint32_t data; };

This is the same instruction shape used by Pike's virtual machine and by RE2's bytecode; reusing it rather than inventing a new one is what keeps the compiler small (roughly one case per AST node).

OP_LOOKAHEAD and OP_LOOKBEHIND each carry, alongside the sub-program pointer and polarity bit, a compile time computed width: a concrete integer for OP_LOOKBEHIND (CPython requires this to exist and be fixed, Section 2.5) and either a concrete integer or an explicit "unbounded" marker for OP_LOOKAHEAD. Only an unbounded width OP_LOOKAHEAD, together with OP_BACKREF, forces engine selection to the bounded backtracking engine (7.3); a fixed width OP_LOOKAHEAD or OP_LOOKBEHIND, of either polarity, is executed by the regular engine (7.2) using a peek buffer sized to exactly that width, never the full window W.

Atomic groups ((?>...)) and possessive quantifiers (*+ ++ ?+ {m,n}+) both compile to OP_ATOMIC, which is the only new opcode either needs: a possessive quantifier is first desugared, at compile time, into the atomic group wrapping its ordinary greedy form (X*+ becomes (?>X*), X{m,n}+ becomes (?>X{m,n}), and so on), so the compiler and both engines only ever have to implement OP_ATOMIC once. OP_ATOMIC runs its sub-program to its single highest priority success (one priority ordered thread simulation restricted to the sub-program in the regular engine, 7.2; one recursive match attempt in the bounded engine, 7.3), advances the current position past whatever it consumed, and then permanently discards every choice point created while matching the sub-program, so that if matching fails later in the overall pattern, the engine never backtracks into the atomic group looking for a different internal match, which is the defining behavior of both constructs in CPython. Unlike OP_LOOKAHEAD, OP_ATOMIC never forces the bounded backtracking engine, regardless of the width of its body: it advances the stream position as it matches, so, unlike a zero-width assertion, it never needs to hold matched text in memory for a decision made later. Only OP_BACKREF and an unbounded width OP_LOOKAHEAD trigger the bounded engine (Section 5, 6).

7.2 Regular engine: Pike VM over a chunk stream

Standard Thompson NFA simulation extended with capture slots, run breadth first ("all current threads advance over the same input character, in priority order, duplicate states are merged"). Per input character the engine holds at most N threads, N being the instruction count, each thread owning only its capture slot array (2 * ngroups offsets), so per character memory is O(N * ngroups), not O(input length).

Streaming adaptation: input arrives as a sequence of chunks (see 7.3) rather than one buffer. Thread capture slots store absolute stream offsets (a 64 bit counter incremented across chunk boundaries), not pointers into the chunk buffer, so a thread survives a chunk boundary without copying. Once every live thread's earliest referenced offset has advanced past a chunk boundary, that chunk is released back to the caller supplied allocator. This is the entire mechanism that lets the regular engine run over an arbitrarily large file in bounded memory: it never needs to look backward, so it never needs to keep anything but the current chunk and the small thread list.

Two small, constant size pieces of state cross a chunk boundary alongside the thread list. First, in UTF8 mode, a partially read multi-byte sequence: at most 3 pending lead bytes (the longest UTF-8 sequence is 4 bytes), carried into the next chunk before character classification resumes; a chunk is only eligible for release once any sequence straddling its end has been completed by the following chunk. Second, under MULTILINE, one bit recording whether the byte immediately before the current chunk was \n, needed to classify ^ at the very first position of a new chunk without rereading the previous one; \n (0x0A) cannot appear as a non-initial byte of any valid multi-byte UTF-8 sequence, so this bit and the UTF-8 continuation state never interact with each other. Neither addition affects the O(instruction count x group count) memory bound of Section 10, since both are O(1) regardless of chunk size or input length.

7.3 Bounded backtracking engine: sliding window

Used only for the minority of patterns containing a backreference or an unbounded width lookahead (7.1). Maintains an explicit ring buffer window of W bytes (default W = 1 MiB, a run time parameter). The window always contains the current match attempt's start position and everything from there forward that has been read so far, up to W bytes. A recursive backtracking matcher, structurally the direct translation of the AST (one function per node kind, exactly as _sre and most textbook backtracking matchers are structured), walks the bytecode against the window. If a match attempt's required span would exceed W, the call returns the documented bounded-window error described in Section 5 instead of growing the window past its configured limit.

Because this engine is only invoked for patterns that need it, ordinary patterns (the large majority) never pay for the ring buffer or for backtracking, and get the linear time guarantee of 7.2 instead.

7.4 Anchoring across chunks

Both engines expose the same chunk boundary contract: a match cannot be reported as final until either (a) OP_MATCH is reached, or (b) enough trailing context has been seen to prove that no continuation of the current input would change the answer for the leftmost still-open match attempt. For quantifiers this is decided directly by the bytecode's OP_SPLIT/OP_JMP shape; for anchors ($, \Z) the final chunk is distinguished by an explicit "end of stream" sentinel token, so $ and \Z behave identically whether or not MULTILINE is set, matching CPython.

7.5 Implementation finding: memoized backtracking as a practical stand-in for 7.2

The v1 implementation (README.md "Implementation status") does not yet have Section 7.2's Pike VM at all; every pattern runs on this section's backtracking engine, without the sliding window (v1 materializes the whole input instead, a separate, already-documented simplification). Building it anyway surfaced a result worth recording here because it affects how urgent 7.2 actually is: a plain backtracking search is not merely "exponential in the worst case for pathological patterns," it is quadratic even for the simplest ordinary pattern, because trying every start position from scratch re-derives the same failures over and over. Two additions to this section's engine, kept but not originally specified here, close most of that gap without building 7.2:

• Memoizing every proven match failure at the (instruction, position) level, never a success, so it cannot change which match is found, only skip re-deriving failures already known. Valid only when the compiled program contains no OP_BACKREF anywhere (a backreference's outcome depends on capture history, not on position alone, so the memoized fact would not be a pure function of position). This is a published technique: recent work on backtracking regex matchers describes the identical "failures only" memoization scheme, and a further refinement, memoizing selectively only at loop "feedback nodes" instead of every instruction, which this implementation does not do but could, for less memory.
• Precomputing, for a quantifier over a single character, class, or ., how far it can run from any position, and, when it is immediately followed by another single atom, the rightmost position where that atom matches, so the backtrack loop jumps to candidates worth trying instead of visiting every position in between. This is the same idea as the literal prefilters (memchr/memmem/Teddy) production engines like RE2 and Rust's regex crate use to skip positions that provably cannot match, implemented here with a precomputed array rather than a SIMD library call, in keeping with this document's convenience-over-performance priority.

Together these make the backtracking engine linear, not quadratic, for a pattern with no backreference built from simple repeated atoms (measured: a pattern searched over 80,000 non-matching bytes dropped from 19.2s to 0.0016s), and turn the textbook catastrophic-backtracking shape (a+)+b from exponential into empirically quadratic, though not linear, since a repeat over a compound body only gets the failure memoization, not the skip-ahead table. Neither technique gives the bounded, input-length-independent memory guarantee that is 7.2's actual reason for existing (Section 5): both use O(instruction count x input length) memory for their tables, which is bounded but scales with input length, unlike 7.2's O(instruction count). 7.2 therefore remains the correct target for the memory axis of Section 1's objective; what changed is that the time axis, for the backreference-free majority of patterns, no longer depends on building it. README.md and docs/API.md carry the measured numbers and full citations.

7.6 Implementation finding: profiling the memory axis directly, and a reverted attempt at bounding it

Measuring 7.5's tables' memory cost directly with Valgrind/Massif, rather than trusting the abstract O(instruction count x input length) bound, found it was worse in practice than that bound alone suggested: a real 10MB search peaked at 140.3MB (13.4x the input), and a real 200MB file search was killed by the operating system's OOM killer before finishing. Tracing that measurement to its allocation sites found two contributors 7.5 did not separately account for, both fixed without touching the matcher's correctness at all:

• build_matbuf (Section 8.4/9.3) widened every byte to a 4-byte code point even in BINARY/ASCII mode, where a byte never exceeds 255 and the widening buys nothing (only UTF8 mode's actual code points, up to 0x10FFFF, need it). Fixed by reading BINARY/ASCII mode's bytes directly instead of widening them first, dropping the measured 10MB case from 140.3MB to 87.8MB (13.4x to 8.4x).
• Input_from_file (Section 9.2) copied every file into a fresh, private buffer even though the operating system's page cache already holds its bytes. Fixed by using mmap for regular, seekable, non-empty files instead: the mapped pages stay clean (read-only, never written) and file-backed, so the kernel can reclaim them under memory pressure and re-fault them in from disk later, rather than them being pinned in a private allocation for the whole match attempt, and one whole redundant copy of the file disappears. Input_from_file is the one place this document's dependency-free, single-file design (Section 8) already had to step outside strict ISO C (fopen/fread are C standard library, but reading a whole file's size upfront portably is not); using mmap/open/fstat here is an extension of a dependency this design already carries (POSIX, the same family wctype.h's locale behavior already depends on, Section 13.3), not a new one.

A third change was attempted, measured, and reverted, which is recorded here because the negative result is as load-bearing as the two fixes above: capping 7.5's two tables above a size budget and falling back to the plain scan already used when either is unavailable seemed like an obvious way to bound memory for huge inputs. Measured directly against a real 200MB non-matching search, it was strictly worse than doing nothing: both tables are needed together to keep an unbounded-quantifier-followed-by-a-required-literal pattern (x*y-shaped) at linear time; disabling either one alone reintroduces the O(n^2) time they exist to prevent, and O(n^2) at n in the hundreds of millions does not finish in practice. A fast, diagnosable allocation failure (every allocation on this path is now checked and fails through the ordinary PatternError/-1 path instead of crashing on an unchecked NULL, a separate finding from the same audit) is a better failure mode than a silent, effectively-unbounded hang, so the tables are allocated unconditionally again. This is the same conclusion 7.5 already reached from the time axis, now confirmed from the memory axis too: there is no way to get both bounded memory and linear time out of a precomputed-table technique for this pattern shape; only 7.2's actual streaming automaton gets both at once, by construction, which is why it remains the correct long-term answer for this axis specifically rather than a further iteration on tables. README.md "Memory footprint" carries the full measured numbers.

7.7 Implementation plan: a Pike VM over the materialized buffer (v1 of 7.2)

This section is the concrete plan for a first working implementation of 7.2's regular engine, written before writing any code, per the practice this document already follows for 7.5/7.6. Three published sources ground it, fetched and read directly rather than recalled from memory, since this document's standing rule is to verify a technique before relying on it: Russ Cox, "Regular Expression Matching: the Virtual Machine Approach" (the instruction set, the thread list with one-thread-per-PC deduplication, the addthread/step algorithm, capture slots stored per thread); the same author's research!rsc article on submatch extraction, crediting Ville Laurikari's tagged-NFA work as the origin of storing submatch boundaries in per-thread state; and the rust-lang/regex crate's regex-automata PikeVM implementation, read directly for its exact rule on what happens when a thread reaches Match mid-search under leftmost-first (Perl/Python-style, not POSIX leftmost-longest) semantics: stop processing only the remaining, strictly lower priority threads in that step's list, keep any higher priority thread already queued for the next step running (one of them may still produce a more preferred match later), and stop seeding new unanchored start threads once any match has been recorded.

A favorable discovery that changes the scope of this work. Section 7.1's bytecode was designed by direct analogy to Pike's VM, and reading compile_node/compile_repeat (Section 6) to plan this confirms it did not just take inspiration from that instruction set, it produced output that already is one: N_CONCAT is sequencing, N_ALT and unbounded N_REPEAT compile to exactly the split/jmp shapes Cox's article gives for alternation and e*, N_GROUP compiles to save at 2*i/2*i+1. The one existing implementation detail Cox's minimal instruction set does not have is OP_REPEAT1, a backtracking-only fast path (Section 7.5) that collapses a quantified single character/class/. into one counted instruction instead of an explicit loop; compile_repeat already contains the ordinary split/jmp loop as its fallback for a compound repeated body, so producing pure-NFA bytecode for a simple-atom repeat too is a matter of skipping the OP_REPEAT1 fast path for that one compile, not writing a new compiler. Concretely: Prog gains one field, no_repeat1, and compile_repeat gains one condition, if (!pr->no_repeat1 && is_simple_atom(n->a)), guarding the existing fast path. This means no new compiler is needed at all; the existing parser and compile_node are reused unchanged, called a second time with no_repeat1 set, to produce a second Prog from the same AST, structurally guaranteed to contain only the instructions a Pike VM understands.

Eligibility (what v1 supports, and what it deliberately does not). OP_BACKREF (not a regular-language construct at all; no NFA, however constructed, can execute it) and OP_LOOKAHEAD/OP_LOOKBEHIND/OP_ATOMIC (each compiles to a self-contained sub-program executed to a single yes/no/where-it-ended answer, Section 7.1, which needs the recursive engine's call structure and is not a natural fit for a flat thread-priority simulation) make a pattern ineligible; a possessive quantifier is already desugared to OP_ATOMIC at parse time (Section 7.1), so it needs no separate check. Eligibility is decided once, right after compiling the ordinary (backtracking) Prog exactly as has_backref already is (Section 8): a single scan of the compiled instructions for any of those four opcodes. An eligible pattern gets a second, NFA-only Prog compiled immediately afterward, from the same AST, and is matched by the engine below through every Pattern_/re_ entry point; an ineligible pattern is matched exactly as it is today, by Section 7.5's memoized backtracking engine, completely unchanged. This is a strict, permanent subset relationship for v1: nothing about a pattern's eligibility depends on which entry point is called or how large the input is, and the excluded constructs are not planned for a later version of this same engine, since each one is excluded for a structural reason given above, not a temporary implementation gap; a pattern needing one of them keeps the correctness and the existing measured performance characteristics of Section 7.5/7.6 indefinitely.

The algorithm. One forward pass over the position range being searched, sp from the caller's pos to endpos, maintaining two thread lists (current step, next step) exactly as Cox describes:

• A thread is { pc, saved }, saved a heap array of 2 * (ngroups + 1) offsets, each thread's own copy.
• addthread(list, pc, saved, sp) is the epsilon closure: OP_JMP follows to its target; OP_SPLIT duplicates saved and recurses into both targets, the higher priority branch (x) first, so list order encodes match preference (greedy-first or lazy-first, whichever the existing compiler already chose for this quantifier, Section 7.1, unchanged); OP_SAVE writes sp into the thread's own saved (safe to mutate in place, not copy: by construction, the only place a saved array is ever shared between two in-flight branches is the instant OP_SPLIT duplicates it, so past that point each copy is exclusively owned by one recursive path) and continues; OP_ASSERT (^ $ \A \Z \b \B) tests the same condition run's OP_ASSERT case already tests (Section 6), reusing that exact logic, and either continues or discards the thread; OP_CHAR/OP_CLASS/OP_ANY/OP_MATCH are the only instructions that end the closure and actually get stored in the list, deduplicated by PC (first writer at a given PC this step wins, since it is by construction the higher priority one; every later duplicate is redundant and its saved array is freed immediately, Cox's stated optimization for why at most one thread per PC is ever needed).
• Per input position: walk the current list in priority order; a char/class/any thread that matches the position is carried into the next list's addthread at pc+1; a match thread is recorded as the best match found so far (subject to forbid_empty, Section 7.5's empty-match retry rule, reusing that same flag and semantics, and to an exact-end requirement for fullmatch, reusing require_end's existing meaning), and the remaining, lower priority threads in this step's list are dropped without being run (the leftmost-first rule verified against rust-lang/regex above); threads already queued into the next list from earlier, higher priority threads in this same step keep running. New unanchored start threads (search/finditer/split only, never match/fullmatch, which seed exactly one thread at the given pos and never inject another) are appended, at lowest priority, at every position up to endpos, but only until a match has been recorded; once one has, no further start is injected, since anything it could find is by definition lower priority than a match already in hand. The pass ends when the current list is empty (nothing left that could still improve on the recorded match) or endpos is reached; the recorded match, if any, is the answer.
• This produces one match, in the same place a single run_memo call produces one; Pattern_search/match/fullmatch's existing call sites, and Pattern_finditer/Pattern_split's existing "find the next match, then the empty-match retry" structure, are unchanged in every respect except that the inner "try every position s from start to ep, one run_memo call each" loop each of those functions has today is replaced, for an eligible pattern, by one call to this single-pass function, which performs that same search in one forward scan instead of restarting once per candidate start position.

Error proofing, decided up front rather than found by audit afterward, per the existing practice (7.6's "failing safely" paragraph, README.md's NULL-check audit). addthread's epsilon closure is specified recursively above because that is how the source material states it, but it is implemented with an explicit heap stack (a DArr of pending (pc, saved) pairs, pushed and popped in a loop), not C call recursion: a pattern with a long chain of alternations or nested groups could otherwise recurse as deep as the instruction count, and this document's standing position (Section 6, MAX_DEPTH) is that input- or pattern-driven recursion depth is exactly the class of thing that must be bounded or made iterative, not assumed small. Every allocation on this path (saved array duplication at each OP_SPLIT, the two thread lists, the explicit closure stack) is checked; a failure anywhere aborts the current call and reports it the same way the existing engine reports its own resource exhaustion (do_one's depth_exceeded check, Section 6): a -1 return through the ordinary PatternError-free error path already documented for the matching functions (docs/API.md Section 3), never a NULL dereference. The thread list itself needs no growth logic at all and therefore nothing can overflow it: Cox's one-thread-per-PC invariant means a list never holds more than Prog.n threads, a fixed, compile-time-known bound, so both lists are allocated once, sized to Prog.n, and never reallocated during the scan.

Testing. The existing 3,252-case suite (tests/cases.py, ground truth from a real CPython interpreter, tests/TEST_PLAN.md) is not specific to the backtracking engine; every case that happens to compile to an eligible pattern automatically exercises this engine too, at no extra authoring cost, and any divergence between the two engines' output for the same eligible pattern is, by construction, a bug in one of them, not an ambiguity in what the correct answer is. A build-time debug mode, added alongside this engine, runs both engines on every eligible test case and asserts their results agree byte-for-byte (match/no-match, every capture span, every group's participation) before comparing either to the CPython-derived expectation, so a regression that made the two engines agree with each other but not with CPython is still caught, and, separately, so a divergence between the two engines specifically (the more likely class of new bug, since CPython-conformance for the covered subset was already established by the existing suite) is reported precisely rather than only as "some test failed."

What is explicitly deferred, per the instruction to get a correct first version before a fast one. Everything Section 7.2 originally specified for the memory axis, streaming: chunked input, releasing a chunk once no live thread still references it, the constant O(instruction count) memory bound regardless of input length. V1 runs this engine over the same fully materialized MatBuf (Section 8.4/9.3) the existing engine already uses, exactly as 7.5's opening paragraph already documents the backtracking engine doing; this is a second instance of the same, already-acknowledged simplification, not a new one. The performance axis is also explicitly deferred: no lazy/cached DFA state table (RE2's and Rust's regex crate's actual production technique, layered on top of an NFA simulation exactly like this one, caching the set of live thread PCs reached from a given state and input byte so repeat visits to the same state skip the closure computation entirely), no literal prefilter, no thread list or saved-array pooling to reduce allocation traffic. Whether this engine ends up faster or slower than Section 7.5's already-shipped, already-measured memoized backtracking engine for the patterns both can run is therefore an open, unmeasured question at the time this plan was written, to be settled after v1 exists and can be benchmarked the same way examples/bench_vs_posix.c benchmarks the backtracking engine today, not assumed in either direction beforehand.

7.8 Implementation finding: the Pike VM, built and measured

7.7's plan was implemented essentially as written; this section records what building it against the existing 3,252-case suite actually found, per the practice 7.6 already established for 7.5. Prog gained the planned no_repeat1 field and one extra condition in compile_repeat; re_compile gained the eligibility scan and, for an eligible pattern, a second compile_node call producing PatternImpl.nfa_prog; do_one, Pattern_finditer, and Pattern_split each gained an impl->has_nfa branch to the new engine, sharing one small helper (find_next) for the "unanchored scan starting no earlier than a position" versus "single anchored attempt at exactly a position" distinction finditer/split's empty-match retry needs, since that retry is anchored, not a forward scan, and conflating the two was the source of one of the two bugs below.

Two real bugs, both found by the existing suite, not by inspection. First: OP_MATCH has no OP_SAVE for group 0's end position (run's own OP_MATCH handler writes c->caps[1] = sp directly, outside the general save mechanism, Section 6); the first version of the Pike VM's OP_MATCH case accepted a thread's saved array without doing the equivalent write, so caps[1] stayed -1 for every unnested match, an error the existing 1000+ eligible cases caught immediately and precisely (every failure was a span ending in -1). Second, and more interesting: an unconditional if (clist.count == 0) break after each step, intended as a reasonable-looking early exit once nothing was left to run, is wrong for unanchored search specifically, because "the current thread list is momentarily empty" does not mean "no later start position could still match": a start thread freshly injected at some position can die immediately during its own epsilon closure (a leading \b failing outright, which happens repeatedly inside a longer word like "catalog" for the pattern \bcat\b) without that implying every later position will too. The existing suite caught this as seven failing cases, all involving \b, all finding zero or one match where CPython finds one or two; the fix restricts the early exit to the two cases where it is actually sound, anchored (a single seed, never renewed, so a dead list really is final) or matched (no further start is seeded once true, so a list that has gone empty after that point can never revive). Both fixes are small, both were found and precisely localized entirely by the existing CPython-derived suite, which was not written with this engine in mind at all; this is the same claim 7.7's testing paragraph predicted for the general case, and it held.

The planned build-time dual-engine debug mode (7.7's testing paragraph) was not built. In practice the existing suite's failures already pinpointed both bugs precisely enough (by pattern, by subject, by exact expected-versus-actual span) that the extra infrastructure was not needed to localize either one; it remains a reasonable thing to add later if a future divergence is ever found that the CPython-derived suite's coverage does not happen to exercise, but building it preemptively, once the simpler approach had already worked twice, was not justified by anything actually observed while doing this work. Targeted whitebox checks were run by hand instead, directly against the compiled library, covering cases the generated suite does not specifically emphasize: a 20,000-branch alternation (iterative addthread's actual reason for existing, Section 7.7's error-proofing paragraph: this compiles and matches correctly, confirming the explicit stack handles a chain of OP_SPLITs far deeper than any hand-written pattern would produce), an empty pattern, UTF8-mode named groups, BINARY-mode matching across an embedded NUL byte, greedy-versus-lazy priority, and alternation branch priority; all passed on the first run after the two fixes above. Two clean AddressSanitizer/UndefinedBehaviorSanitizer passes over the full suite, and a further clean pass over the whitebox checks above, found no memory error or undefined behavior in the new code (thread list and saved array ownership, the most manually managed part of this engine, Section 7.7's error-proofing paragraph).

A result not anticipated by 7.7, which called the relative performance of the two engines "an open, unmeasured question." It is no longer open for the specific case that motivated writing 7.7 in the first place: (a+)+b, README.md's own textbook example of the backtracking engine's remaining weak spot, contains no backreference and is therefore Pike VM eligible, and now measures as genuinely linear, not the "empirically quadratic" figure 7.5 measured for the backtracking engine on the same pattern (that figure remains accurate for what it was actually measuring, the backtracking engine specifically, which still runs this exact pattern shape when it also contains a backreference or another construct that makes it ineligible for this section's engine; the pattern most often used to illustrate the trade-off simply no longer needs that engine at all). Measured directly: search time against n non-matching a characters went from roughly 2x per doubling of n under the backtracking engine (7.5's figure) to also roughly 2x per doubling under the Pike VM, i.e. linear, confirmed from n = 10,000 to n = 160,000 (0.0018s to 0.0308s). This is a real, measured improvement for every backreference-free pattern, not a projected one, but it is not the whole picture: re-running examples/bench_vs_posix.c's literal search, number extraction, and a*b scenarios, none of them adversarial and all of them now Pike VM eligible, found the gap to POSIX <regex.h> on those three widened, from roughly 2x-25x before this engine existed (running on the backtracking engine plus 7.5's skip-ahead tables) to roughly 8x-70x now. This is the direct, expected cost of 7.7's deferred performance axis actually being deferred: 7.5's tables were themselves a targeted, measured optimization for exactly this kind of pattern, and the Pike VM has no equivalent yet (no literal prefilter, no lazy DFA state caching, no allocation pooling), so an ordinary pattern that used to benefit from that work now runs on a correctness-first engine that does not have it, a real regression for the common case traded for the (a+)+b-class fix above, not a net win averaged across all patterns. Whether the Pike VM ends up faster than the backtracking engine specifically (as opposed to against POSIX) on these same ordinary patterns, which would settle whether 7.5's tables are still worth keeping once this engine has its own optimization pass, remains genuinely unmeasured and is the next open question on this axis.

7.9 Implementation finding: the dual-engine cross-check, a literal prefilter, and a memory measurement

Continued work after 7.8 closed three of the items it left open, in the order they were tackled.

The dual-engine debug mode 7.8 said was not built was built. Not as a permanent build-time mode as 7.7 originally specified, but as an ad hoc whitebox harness (#include "regexx.c" for direct access to PatternImpl.has_nfa, toggled on the same compiled Pattern to run match/fullmatch/search/finditer through both engines and compare every result field by field), run against 6,000 randomly generated eligible patterns (literals, classes, anchors, quantifiers including lazy and bounded forms, alternation, capturing/non-capturing/named groups, nested combinations) across 20 subjects, all three data modes, several flag combinations: 24,000 match/fullmatch/search comparisons and roughly 2,700 finditer comparisons, zero mismatches, clean under AddressSanitizer/UndefinedBehaviorSanitizer. Not committed as a permanent test target, the same judgment 7.8 already made and still holds (the CPython-derived suite continues to be what actually finds and localizes divergences); this was additional, freshly gathered evidence on demand, not a change of strategy.

A literal prefilter was added to pike_find's unanchored injection loop, the single highest leverage item on 7.7/7.8's deferred performance list, chosen specifically because examples/bench_vs_posix.c's literal-search scenario was the one 7.8 found had regressed the most (roughly 2x before this engine existed to roughly 70x after). When the very first instruction of the NFA-only Prog is a mandatory OP_CHAR or OP_CLASS (a pattern beginning with a required literal or class, not a nullable loop or a leading assertion), injecting a fresh start thread at a position that instruction would reject is certain, by construction, 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 work is spent finding out that most of them will not. This is the same literal-prefilter idea 7.5 already cites for the backtracking engine's own compute_next_prevmatch, applied here in its simplest form, a per-position check rather than a precomputed table, deliberately: README.md "Implementation status" already documents that a precomputed skip-ahead table traded for a correctness problem once (the reverted size-cap attempt, 7.6), and this narrower, unconditional check carries no equivalent risk, since it can only ever skip work a fuller simulation would also have discarded. Measured directly: the literal-search scenario dropped from roughly 70x slower than POSIX <regex.h> to roughly 11x-13x, better than this build's own pre-Pike-VM baseline (roughly 22x-35x, 7.8); the number-extraction scenario ([0-9]+, beginning with a mandatory class) improved from roughly 8x to roughly 7x; the a*b scenario, whose leading a* is a nullable loop the prefilter structurally cannot help, is unchanged, exactly as expected rather than as a gap. Verified against the dual-engine cross-check above (0 mismatches) and the full CPython-derived suite (3,252/3,252) both before and after.

The Pike VM's own memory cost, which Section 10's table stated as a design bound without measurement, was profiled with Valgrind/Massif the same way 7.6 profiled the backtracking engine, on the same adversarial choice of pattern for a fair comparison: a*b against 10MB of non-matching a characters, the nullable-loop worst case a literal prefilter cannot reduce, so this number is not flattered by the fix above. Peak heap use was 10,497,824 bytes, of which 10,485,761 bytes, 99.89%, is the test harness's own 10MB input buffer, present regardless of which engine runs; the engine's own contribution, compiling the pattern and running the full search, was the remaining 12,063 bytes, an amount that does not grow with input length (the thread lists are cleared and reused every input position, never accumulating) and is small enough, relative to a multi-megabyte input, to be indistinguishable from a constant in practice. This confirms Section 10's O(instruction count x group count), input-length-independent bound for the Pike VM actually holds for the v1 implementation, not only for the design (Section 10's table updated accordingly).

7.10 Implementation finding: eliminating per-thread allocation, a real literal prefilter, and why a lazy DFA cache was researched and not built

Requested directly: research production regex engines specifically for optimizations applicable to this one, critically, then implement what the research justified. This section records both.

Research, read directly from source, not recalled. Two independently maintained, production Pike-VM-family engines were fetched and read for how each avoids the cost 7.9's benchmark blamed for the Pike VM's two measured weaknesses (a*b's nullable loop, dense finditer): per-thread capture-array allocation. RE2's nfa.cc pools Thread objects from a free list (AllocThread pulls from freelist_ before ever calling new; each pooled slot's capture array, once allocated, is reused via reference counting rather than freed and reallocated) and walks the epsilon closure with a stack pre-sized once from the instruction count, not grown on demand. rust-lang/regex's regex-automata goes further: a SlotTable, one flat array indexed table[stateID * slotsPerState + slotIndex], needs no per-thread allocation at all, because Pike's own one-thread-per-PC invariant (already relied on here for PikeList's fixed capacity, 7.7) makes the PC itself a sufficient index; its Cache (the thread lists plus this table) is constructed once and reused across repeated searches, not reallocated per call. Separately, Hyperscan's Teddy algorithm (SIMD, up to 64 bytes per 16 vector instructions, a published ~35x over naive scanning for small literal sets) was researched for literal prefiltering specifically and set aside: it needs platform-specific SIMD intrinsics, in direct tension with this design's single-file, portable-C, simplicity-over-performance priority (Section 1), and a portable byte-oriented technique (Boyer-Moore-Horspool, below) was judged proportionate where Teddy was not.

What was built. PikeThread's owned int64_t *saved pointer is gone. Capture rows for a step's committed (terminal-instruction) threads now live in PikeList.table, one flat array per list, indexed directly by PC exactly as regex-automata's SlotTable does; nothing is allocated or freed to store or discard one, since a stale row is simply never read (gated by seen[]/pcs[], both reset every step). The transient rows needed mid-closure, before the eventual terminal PC is known, come from ScratchPool, a fixed block of rows with an explicit free list, sized once from the same n+1-rows-at-once bound PikeList already relies on. A plain bump/decrement counter was tried first, for this specific pool, and rejected before being written into the file: proved incorrect by hand-tracing a case where an OP_SPLIT's second branch's row must outlive several non-branching pushes that reuse an earlier row without reallocating it, which only a real free list (any release order, not just strict LIFO) handles safely. pike_addthread's own closure stack (WorkStack) is likewise pre-sized once from the same bound rather than grown by realloc on demand, closing the smallest of the three gaps 7.9's summary listed. All three (thread lists, scratch pool, work stack) are bundled into one PikeEngine, built once per top-level Pattern_/re_ call and reused across every match Pattern_finditer/Pattern_split find within that one call, not reallocated per match; explicitly never cached on PatternImpl itself, since that would make concurrent Pattern_search calls on the same compiled Pattern from different threads race on shared mutable state, silently breaking the existing guarantee that a Pattern no thread is concurrently modifying needs no external synchronization (13.6).

The literal prefilter (7.9) was extended from a single leading character to the full mandatory literal prefix (every consecutive leading OP_CHAR, however long) with a real Boyer-Moore-Horspool bad-character skip table, built once per PikeEngine from the prefix, case-folded first when IGNORECASE is set. Sound for BINARY/ASCII mode, where text_at() already returns a raw byte and a 256-entry table suffices; UTF8 mode's code points range past 0x10FFFF, too wide for a flat byte table, so it keeps the without-skip fallback (checking the whole prefix, not only its first character, still real, just without the multi-position skip). A single leading OP_CLASS (no multi-character literal to extract) gets its own tight linear scan, cheaper than the full injection machinery even without a skip table. Crucially, the skip-ahead itself is only ever applied to where a new start thread is injected, never to the position already-live threads are stepped through: skipping sp itself is only sound when nothing is currently in flight (clist empty), since a live thread from an earlier start position must still be advanced one character at a time regardless of what the prefilter finds further ahead.

Verification. Full 3,252-case suite, unchanged, four clean runs; a whitebox dual-engine cross-check extended beyond 7.9's version to also cover finditer, split, and BINARY mode (patterns deliberately built from the prefilter's own literal fixtures, e.g. needle_marker, MAGIC): 30,000 match/fullmatch/search comparisons, 3,334 finditer, 2,500 split, zero mismatches. A targeted whitebox suite specifically for the new prefilter machinery, including the classic Boyer-Moore-Horspool correctness trap (a literal whose own suffix overlaps its prefix, abcabd against xxabcabcabdxx, wrong on a naively-built skip table) and IGNORECASE-folded BMH matching: 12/12. Two clean AddressSanitizer/UndefinedBehaviorSanitizer passes on the suite, two more on the dual-engine and prefilter checks (a third run of each hit the same pre-existing sandbox dynamic-linker flake this document already recorded, unrelated to this code, confirmed the same way: retried clean).

Measured, before this section's changes versus after, same benchmarks 7.9 used:

Case	Pike/backtracking, before	Pike/backtracking, after
Literal search, 32MB	0.64x (already ahead)	0.03x (~33x faster than backtracking)
a*b non-match, 32MB (no prefilter applies)	3.45x slower	1.97x slower (allocation fix alone, prefilter-independent)
(a+)+b, n=80,000	0.0007x	0.0005x
Dense finditer, [0-9]+, 5MB	3.21x slower	1.69x slower
Dense finditer, \w+, 5MB	5.57x slower	2.78x slower
Dense finditer, id\d+ (literal-prefixed), 5MB	1.84x slower	0.84x (now faster than backtracking)

Against POSIX <regex.h> (examples/bench_vs_posix.c, README.md "Benchmarks"), the literal-search scenario went from roughly 12x slower than glibc to roughly 2x faster than glibc; a*b from roughly 27x slower to roughly 14x; number extraction from roughly 7x to roughly 4x. The a*b/dense-finditer improvement (roughly halved in every case) is attributable entirely to the allocation fix, since none of those patterns benefit from the prefilter at all (a nullable leading loop, or a leading class with no multi-character literal to extract); the literal-search improvement is dominated by the Boyer-Moore-Horspool skip specifically.

Why a lazy DFA state cache (memoizing a live-PC-set-plus-byte transition, so a repeated state skips recomputing its own closure) was researched and not built, a critical decision, not an omission. Two reasons, one structural and one now empirical. Structurally: RE2's own lazy DFA "cannot track submatch boundaries" (confirmed directly against its documented engine-selection table, 7.9's research) for exactly the reason this project's every matching call wants captures, at minimum group 0's span: a cached state-set transition only answers "is a match possible from here," not "which specific path was taken," and captures depend on the path, not merely on which PCs are reachable. Using one at all would need a two-phase architecture (a fast boolean pass to find that a match exists, then a second, slower pass to find where exactly), which is a materially different, larger design than a bolt-on cache, deserving its own research-and-plan pass the way this Pike VM itself got, not a rushed addition under an unrelated body of work. Empirically, checked directly rather than assumed: the case a lazy DFA cache would help most, a*b's nullable loop, has at most two live PCs at any position for its entire run (inside the loop, past it), meaning there is no repeated, expensive-to-recompute state to cache in the first place; profiling this section's own numbers shows the remaining backtracking-engine advantage there (roughly 2x, down from 3.45x) tracking the general per-position dispatch-loop cost of a handful of instructions against run()'s single, hand-specialized OP_REPEAT1 counting instruction, not epsilon-closure recomputation, which a lazy DFA cache specifically targets and this pattern shape does not exhibit. Building it would have added real, correctness-sensitive complexity (a hash table, state interning, an eviction policy, and the two-phase capture problem above) for a benefit this section's own measurements do not support for the cases that motivated looking at it.

8. Core Data Structures

Kept intentionally minimal, all defined in the single file, no dependency beyond the C standard library (stdint.h, stddef.h, string.h) for the data structures in this section specifically. Input_from_file (Section 9.2) is the one place the file as a whole steps outside strict ISO C, using POSIX (mmap/open/fstat, Section 7.6), already in the same family of platform dependency wctype.h's locale behavior carries (Section 13.3).

8.1 Allocator

One struct of three function pointers (alloc, realloc, free) passed once at engine creation, defaulting to the libc equivalents. This is the only piece of "infrastructure" abstraction in the file, and it exists so the sliding window (7.3) and chunk buffers (7.2) can be sized and released under caller control, which is a prerequisite for the gigabyte scale requirement.

8.2 Dynamic array

One generic growable array ({ void *data; size_t len, cap, elemsize; }) with push/get, used for the instruction array, the capture slot array, and the AST node pool. Deliberately not a macro-heavy generic container; three functions (da_init, da_push, da_free) cover every use site in the file.

8.3 Byte class table

A 256 bit set (uint32_t bits[8]) per compiled [...] class or shorthand class, precomputed at compile time. In UTF-8 mode, code points above 127 are matched against a small number of precompiled Unicode range tables (Section 13.3) instead of the 256 bit set.

8.4 Capture slots

A flat array of 2 * groups capture records per thread (regular engine) or per backtracking call frame (bounded engine), -1 meaning unset. In BINARY and ASCII mode a record is a single int64_t byte offset. In UTF8 mode a record is a pair, { int64_t byte_offset; int64_t codepoint_index; }: the byte offset is what is needed to read the matched bytes back out of Input, and the code point index is what is needed to report Match_start/Match_end/Match_span in the same unit Python uses for str subjects (Section 9.1). The code point index is a running counter incremented once per decoded scalar value as the engine advances, so recording it at a SAVE costs one extra integer copy, not a second pass over the input; it changes the constant factor of the O(instruction count x group count) memory bound of Section 10 in UTF8 mode, not its asymptotic class. This single representation backs Match_group, Match_start, Match_end, Match_span, Match_start_byte, Match_end_byte, Match_span_byte, and Match_groupdict in the public API.

9. Public API (Python re equivalents)

9.0 Naming convention

Every public identifier that has a direct counterpart in Python's re module uses that counterpart's exact spelling, not a transliterated or prefixed variant. Concretely:

• The two data types Python's re exposes, Pattern and Match, are C structs named Pattern and Match, not regex_t or regexx_pattern.
• A method Python calls as pattern_obj.search(...) is written Pattern_search(Pattern *self, ...); a method called as match_obj.group(...) is written Match_group(Match *self, ...). The Type_method shape is the direct C rendering of type.method, needed only because C has no bound methods; the two name fragments either side of the underscore are otherwise exactly the Python names.
• A module level function such as re.compile(...) or re.sub(...) is written re_compile(...), re_sub(...), and so on: the re_ prefix stands for the module the function lives in in Python (re.compile), the same relationship Pattern_ and Match_ have to their types.
• Flag constants (IGNORECASE, MULTILINE, DOTALL, VERBOSE, ASCII, UNICODE, LOCALE, DEBUG) are #define or enum constants with exactly those names, no RE_ or REGEXX_ prefix, combined with bitwise | exactly as re.IGNORECASE | re.MULTILINE is combined with Python's |.
• Pattern fields are named pattern, flags, groups, groupindex, matching re.Pattern.pattern, .flags, .groups, .groupindex exactly. Match fields are named string, pos, endpos, lastindex, lastgroup, re (a pointer back to the owning Pattern, matching re.Match.re), matching re.Match's attributes exactly.
• The exception is Input (9.1), which has no Python counterpart because Python's re never streams: it always operates on an in-memory str or bytes object. Input is the one C-only type the design adds, and it is named descriptively rather than after a nonexistent Python name, precisely so it stands out as the one addition a reader should not go looking for in the re documentation.
• The error type is named PatternError, matching the alias CPython itself introduced for re.error (re.PatternError), rather than a plain error (which would collide too easily with errno.h-style conventions) or an invented regexx_error.

9.1 Declarations

typedef struct Pattern Pattern;   /* re.Pattern   */
typedef struct Match   Match;     /* re.Match     */
typedef struct Input   Input;     /* no Python counterpart, see 9.0; left without a
                                    * struct body here because its concrete layout is
                                    * one of the two variants described in 9.2 and no
                                    * code outside the Input implementation itself
                                    * needs to see inside it, unlike Pattern and Match
                                    * whose fields are part of the public, Python-
                                    * mirroring surface. */

typedef void (*MatchIterCb)(void *ctx, const Match *m);
typedef void (*MatchSubCb)(void *ctx, const Match *m, char **out, size_t *outlen);

typedef struct PatternError PatternError; /* re.error / re.PatternError */
struct PatternError {
    const char *msg;      /* re.error.msg     */
    const char *pattern;  /* re.error.pattern */
    int64_t     pos;      /* re.error.pos     */
    int64_t     lineno;   /* re.error.lineno  */
    int64_t     colno;    /* re.error.colno   */
};

struct Pattern {
    const char *pattern;          /* re.Pattern.pattern    */
    int         flags;            /* re.Pattern.flags      */
    int         groups;           /* re.Pattern.groups     */
    void       *groupindex;       /* re.Pattern.groupindex, name -> group number */
    void       *program;          /* compiled bytecode, private (7.1) */
};

struct Match {
    Pattern    *re;                /* re.Match.re      */
    Input      *string;            /* re.Match.string  */
    int64_t     pos, endpos;       /* re.Match.pos, re.Match.endpos; code point indices in UTF8 mode, byte offsets otherwise, see 8.4 */
    int         lastindex;         /* re.Match.lastindex */
    const char *lastgroup;         /* re.Match.lastgroup */
    void       *slots;             /* private, see 8.4 */
};

/* Pattern methods: the primitives, bound to an already compiled Pattern,
 * mirroring re.Pattern.match / .search / .fullmatch / .finditer / .findall /
 * .split / .sub / .subn exactly, including their pos/endpos parameters. */
int      Pattern_match(Pattern *self, Input *string, int64_t pos, int64_t endpos, Match *out);
int      Pattern_fullmatch(Pattern *self, Input *string, int64_t pos, int64_t endpos, Match *out);
int      Pattern_search(Pattern *self, Input *string, int64_t pos, int64_t endpos, Match *out);
int      Pattern_finditer(Pattern *self, Input *string, int64_t pos, int64_t endpos, MatchIterCb cb, void *ctx);
int      Pattern_findall(Pattern *self, Input *string, int64_t pos, int64_t endpos, MatchIterCb cb, void *ctx);
int      Pattern_split(Pattern *self, Input *string, int maxsplit, MatchIterCb cb, void *ctx);
int      Pattern_sub(Pattern *self, Input *string, const char *repl, MatchSubCb cb, void *ctx, int count, char **out, size_t *outlen);
int      Pattern_subn(Pattern *self, Input *string, const char *repl, MatchSubCb cb, void *ctx, int count, char **out, size_t *outlen, int *n);
void     Pattern_free(Pattern *self);

/* Match accessors, matching re.Match's bound methods and attributes */
int         Match_group(Match *self, const char *name_or_null, int index, const char **out, size_t *outlen);
void        Match_groups(Match *self, /* out array of (ptr,len) */ void *out);
void        Match_groupdict(Match *self, /* out name -> (ptr,len) map */ void *out);
int64_t     Match_start(Match *self, int group);       /* code point index in UTF8 mode, byte offset otherwise */
int64_t     Match_end(Match *self, int group);
void        Match_span(Match *self, int group, int64_t *start, int64_t *end);
int64_t     Match_start_byte(Match *self, int group);  /* always a byte offset into Input, see 8.4 */
int64_t     Match_end_byte(Match *self, int group);
void        Match_span_byte(Match *self, int group, int64_t *start, int64_t *end);
void        Match_expand(Match *self, const char *template, char **out, size_t *outlen);

/* Module level functions, mirroring re.compile / re.match / re.search / ...
 * exactly: each of the search-family functions compiles pattern through an
 * internal bounded cache and then calls the matching Pattern_ function,
 * exactly as CPython's re/__init__.py implements re.match as
 * _compile(pattern, flags).match(string). */
Pattern *re_compile(const char *pattern, size_t len, int flags, PatternError *err);
int      re_match(const char *pattern, size_t len, int flags, Input *string, Match *out);
int      re_fullmatch(const char *pattern, size_t len, int flags, Input *string, Match *out);
int      re_search(const char *pattern, size_t len, int flags, Input *string, Match *out);
int      re_finditer(const char *pattern, size_t len, int flags, Input *string, MatchIterCb cb, void *ctx);
int      re_findall(const char *pattern, size_t len, int flags, Input *string, MatchIterCb cb, void *ctx);
int      re_split(const char *pattern, size_t len, int flags, Input *string, int maxsplit, MatchIterCb cb, void *ctx);
int      re_sub(const char *pattern, size_t len, int flags, Input *string, const char *repl, MatchSubCb cb, void *ctx, int count, char **out, size_t *outlen);
int      re_subn(const char *pattern, size_t len, int flags, Input *string, const char *repl, MatchSubCb cb, void *ctx, int count, char **out, size_t *outlen, int *n);
void     re_escape(const char *in, size_t len, char **out, size_t *outlen);
void     re_purge(void);

The dependency runs from module level to Pattern, not the other way around, which is the same direction CPython itself uses: re.py defines match, search, and the rest as thin wrappers that call _compile(pattern, flags) and then the corresponding Pattern method. Each module level function above holds an internal cache keyed by (pattern, len, flags), bounded to a fixed capacity and cleared entirely on overflow rather than evicting individual entries, again mirroring the strategy CPython's own re module cache uses. re_purge() clears that cache on demand, matching re.purge() exactly, including that it has no effect on any Pattern * a caller is still holding a direct reference to. re_compile bypasses the cache and always produces a fresh Pattern, matching re.compile. A caller working against a large or streaming Input and applying the same pattern repeatedly should call re_compile once and use the Pattern_ functions directly, exactly as idiomatic Python precompiles a pattern that is reused in a loop rather than calling the module level function repeatedly; the module level functions exist for parity with re.match/re.search/etc., not as the recommended entry point for the gigabyte scale case this design targets.

9.2 Input

An abstraction over "a source of chunks": either a fixed buffer (small strings, a drop in replacement for the CPython str/bytes case) or a caller supplied read(void *ctx, uint8_t *buf, size_t cap) -> size_t callback (files, pipes, sockets), which is how gigabyte scale input is supplied without ever requiring the caller to load it fully into memory. See 9.0 for why this type does not carry a Python name.

pos and endpos on the Pattern_ functions are expressed in the same unit as Match_start/Match_end for the pattern's mode (code point index in UTF8 mode, byte offset otherwise, Section 8.4). Honoring a nonzero pos against a streaming Input that only exposes sequential read requires decoding forward from the start of the stream until that position is reached, an O(pos) cost paid once per call, not a departure from the per-character bound of Section 10, which is stated per byte of input actually scanned. An Input that also exposes an optional seek(void *ctx, int64_t byte_offset) -> int callback lets the engine skip that decode pass in ASCII/BINARY mode, or in UTF8 mode whenever the caller already knows the target byte offset, for example one returned earlier by Match_start_byte against the same Input.

9.3 Encoding mode

A field of the compile-time flags alongside IGNORECASE, MULTILINE, and the rest: BINARY, ASCII, UTF8 (no RE_ prefix, per 9.0; CPython has no equivalent constant because the choice between binary and text mode is implicit in whether a bytes or str pattern was compiled, so Pattern_compile here makes that same choice explicit through a flag instead). This flag selects, at compile time, which byte class tables (8.3), which ./\w/\s definitions (2.2), and which decoder (raw byte, or the UTF-8 decoder producing code points for classification while recording both a code point index and a byte offset per capture, Section 8.4) the compiled program uses. Binary mode never decodes: every byte value 0 to 255, including embedded NUL, is a valid atom, matching the behavior Python gets by compiling a bytes pattern against a bytes subject.

A byte sequence in UTF8 mode that is not valid UTF-8 at the point the decoder reaches it is handled the way bytes.decode('utf-8', errors=...) is in Python: the default policy, strict, surfaces a PatternError identifying the byte offset of the first invalid byte, matching the fact that CPython can never hand re a str that was not already validly decoded in the first place. An opt-in replace policy substitutes the Unicode replacement character U+FFFD for the offending bytes and continues, for callers that must process untrusted or partially corrupt streams without aborting. BINARY and ASCII mode have no decode step and so have no analogous failure mode; a byte outside 0-127 in ASCII mode is simply a byte no ASCII-mode class matches, not an error.

9.4 Replacement callback

Pattern_sub/Pattern_subn (and the module level re_sub/re_subn that wrap them, 9.1) take both a repl template string and a cb callback of type MatchSubCb as separate parameters, of which exactly one is non-NULL on any given call: a non-NULL repl is parsed once, at compile time, into a small list of literal/backreference segments, mirroring Section 3's replacement syntax; a non-NULL cb is invoked once per match with the match record and a caller supplied ctx, and is expected to write the replacement text through out/outlen, which is the C shape of Python's callable repl argument to re.sub. Two separate parameters, rather than one parameter serving both roles, is the direct C consequence of Python's single repl argument being polymorphic (string or callable) in a way C's static type system cannot express in one slot, the same kind of unavoidable, minimal departure from a one to one name and shape mapping that 9.0 already accepts for Type_method.

10. Complexity Summary

Engine	Time	Memory	Applies to
Regular (Pike VM, 7.2)	O(input length x instruction count)	O(instruction count x group count), independent of input length	Patterns with no backreference and no unbounded lookaround
Bounded backtracking (7.3)	Worst case exponential in window size, as in CPython	O(window size W), independent of input length beyond W	Patterns with a backreference or an unbounded width lookahead

Both figures are stated relative to input length specifically because that is the axis the gigabyte scale requirement constrains; instruction count and group count are properties of the pattern, not the input, and are expected to stay small (tens to low hundreds) for realistically written patterns.

This table describes the two engines as designed. Section 7.5 records that the bounded backtracking engine's v1 implementation, augmented with memoization and precomputed skip-ahead tables, in practice achieves the Regular engine's linear time bound for the backreference-free majority of patterns, at the cost of O(instruction count x input length) memory rather than the Regular engine's O(instruction count x group count), so the two rows above remain the correct statement of each engine's guarantee, not of what a specific implementation happens to measure. The Regular row's own memory bound, for the Pike VM v1 implementation, is now held to the same standard: 7.9 records a Valgrind/Massif profile (the same adversarial, nullable-loop pattern shape a*b this document uses for the backtracking engine's own worst case) finding the engine's own contribution, beyond holding the input itself, at roughly 12KB for a 10MB search, an amount that does not grow with input length because the thread lists are cleared and reused every input position rather than accumulated, confirming the design bound in this row holds for the v1 implementation, not only in theory. Both engines, regardless of this row, still hold the entire input in memory in v1 (7.7's "what is explicitly deferred" paragraph), which this table's "independent of input length" language describes the engine's own working set as achieving, not the absence of that separate, already-documented cost.

11. Testing Strategy

CPython ships its own re test suite (Lib/test/test_re.py / re_tests.py) as executable pattern, string, expected-result triples. The plan is to translate that suite mechanically into a table of C test cases run against re_match/re_search/re_sub, so the engine's conformance is measured against CPython's own stated behavior rather than against a re-derived interpretation of the documentation. Cases that exercise the explicitly out of scope items in Section 13 are recorded as known deviations rather than deleted, so the gap stays visible.

12. Worked Example: Why This Is the Simplest Design That Reaches the Goal

A single unified backtracking engine (matching CPython's own _sre design most closely) would be simpler to write than the two-engine split in Section 5 and Section 7, but it cannot satisfy the gigabyte scale, bounded memory requirement for the common case, because a naive backtracking matcher's stack depth and re-scan behavior scale with input length for ordinary patterns, not only for pattern using backreferences. Conversely, a single unified automaton engine (no backtracking at all) is simpler still, but cannot express backreferences, or the same unbounded width lookaround built from the widening this design already restricts to the bounded engine (Section 5, 7.1), which the objective in Section 1 requires. The two-engine split is the smallest design found that keeps the automaton engine's linear-time, bounded-memory property for the patterns that admit it, while still offering exact backreference and lookaround semantics for the patterns that need them, at an explicit and configurable memory cost.

13. Known Gaps Against CPython re

13.1 POSIX leftmost-longest matching

Not applicable; CPython's re itself uses ordered, first-alternative-wins backtracking semantics, and this engine matches that, not POSIX grep -E semantics. See Section 14.1 for the full comparison against native C regex.h behavior, which this section only touched on briefly before that comparison existed.

13.2 Recursion limit parity

CPython raises RecursionError past a configurable backtracking depth. The bounded backtracking engine (7.3) instead bounds by window size and an explicit call depth counter with a similar default; exact error message parity is not a goal, only the presence of a safe failure mode.

13.3 Full Unicode tables

\N{NAME} lookup, full IGNORECASE case folding (including special casing such as German ß), and complete \w/\s Unicode category coverage require the Unicode Character Database. The concept ships a reduced set of range tables covering the common categories (letters, digits, marks, common whitespace) rather than the full database, to keep the single file small; the compiled tables are generated from the Unicode Character Database offline and checked in as static arrays, with the generation script kept outside the single interpreter file.

13.4 LOCALE flag

Only the "C" locale behavior is implemented; full locale.h integration (honoring whatever locale the embedding program has set, the way CPython's own re.LOCALE does) is out of scope because it reintroduces global, environment dependent state into an otherwise pure, single file design. Under the "C" locale specifically, this flag has no effect on \w/\b/\B beyond plain ASCII classification: an earlier revision of this design stated that bytes \x80-\xff would additionally be treated as word characters, on the unverified assumption that this is what "the C locale" does; checked directly, both the C standard's own guarantee for isalnum() under the "C" locale and a real CPython interpreter's re.LOCALE (explicitly set to the "C" locale) classify only the ASCII letters and digits, nothing above 0x7f. The large combinatorial test expansion caught the mismatch this produced against regexx's own prior implementation of the (incorrect) claim; both have been corrected (README.md "Known deviations", regexx.c's cls_is_word).

13.5 regex third party module extensions

Constructs from the third party regex package (set operations inside classes such as --/&&, fuzzy matching, recursive patterns (?R), variable width lookbehind) are not part of CPython's re and are out of scope by Section 1's own definition of "what Python supports."

13.6 Concurrency of the module level pattern cache

The internal cache backing the module level functions of Section 9.1 (re_match, re_search, and the rest) is shared, mutable state. CPython's own equivalent cache is implicitly protected by the GIL; this design has no equivalent, so a caller invoking the module level functions from more than one thread concurrently must serialize access to the cache itself (a mutex around lookup and insertion, sized independently of the allocator in 8.1) or avoid the module level functions entirely and call re_compile once per pattern up front, sharing the resulting read only Pattern * across threads. The latter is already the recommended pattern for the gigabyte scale case (9.1's closing paragraph), so this limitation is expected to be inactive on the path the design is optimized for.

14. POSIX / Native C Regex (regex.h) Capabilities Absent From Python re

Because this project is delivered as a C module, a reader coming from C rather than from Python may reasonably expect it to behave like the regular expression facility native to the C standard library, POSIX regex.h (regcomp, regexec, regfree, regerror, specified by IEEE Std 1003.1). This section records, completely and for that reader specifically, the respects in which POSIX's native facility does something Python re does not do at all. Every item is either omitted by design, meaning it is incompatible with matching Python re's own behavior and is therefore excluded by Section 1's own definition of the target, or out of scope, meaning it would not conflict with Python parity but was not requested and is not free to add under Section 1's simplicity priority. Section 14.6 closes with the one respect in which this design already exceeds POSIX regex.h, included so the comparison is not one sided.

14.1 Leftmost-longest ("POSIX") matching

POSIX regex.h is specified to find the leftmost match and, among matches starting at that leftmost position, the longest one, applied recursively to subexpressions as well as to the overall match. Python re, like every Perl-derived engine, instead uses leftmost-first, ordered-alternation, backtracking semantics: the first alternative that leads to any overall match wins, even when a later alternative would consume more text, and quantifier greediness is resolved by backtracking order rather than by a global longest-match search. These are two different, mutually incompatible definitions of "the match" for the same pattern and string; a|ab against "ab" matches "a" under Python/Perl semantics and "ab" under POSIX semantics. This design follows Python's ordered semantics throughout (Section 2.5, Section 13.1), by the objective in Section 1. Omitted by design: Pike's priority ordered thread simulation (7.2), used here specifically to reproduce Perl style ordered semantics, is a different algorithm from the one POSIX-longest resolution requires, and running both simultaneously would cost the single, simple engine design Section 12 argues for, for a mode nothing in Section 1 asks for.

14.2 POSIX bracket-expression collating symbols and equivalence classes

A POSIX bracket expression may contain [.collating-symbol.] (a named, possibly multi-character collating element treated as one unit, useful for ranges) and [=equivalence-class=] (every character the active locale's collation treats as primary equivalent to the given one). Python's [...] syntax has no counterpart to either: [[.ch.]] and [[=e=]] in a Python pattern parse as plain sets of the literal characters [, ., c, h, ] and [, =, e, ], never as collating constructs, because Python bracket expressions are defined purely over literal characters and ranges, never over locale collation data. Out of scope: these constructs only have observable effect in locales with genuine multi-character collating elements, which is rare in practice, Python's re has never implemented them for str or bytes patterns, and adding them would require linking the compiled tables of Section 8.3 to the system's LC_COLLATE data, in direct tension with the dependency-free, pure-function design of Section 8.

14.3 POSIX named character classes inside bracket expressions

POSIX bracket expressions accept the twelve standard named classes, alpha, digit, alnum, upper, lower, space, blank, cntrl, graph, print, punct, xdigit, written as [:name:] inside a bracket expression, for example [[:alpha:][:digit:]]. Python's re has no equivalent syntax; the same intent is expressed with ranges and the shorthand classes of Section 2.2 instead ([a-zA-Z], \d, \s), and [[:alpha:]] in Python parses as a literal set containing :, a, l, p, h, [, ]. Out of scope by direct consequence of Section 1: Python re genuinely has no such syntax, so parity with Python re already excludes it; it is recorded here only because a C-background reader is likely to look for it and be surprised to find it silently absent rather than documented.

14.4 Locale collating sequence for bracket-expression ranges

POSIX specifies that a bracket-expression range such as [a-z] is resolved according to the current locale's collating sequence (LC_COLLATE), not according to raw code point or byte value order; in a locale whose collation is not a simple ascending code point order, [a-z] can therefore include, exclude, or reorder characters relative to what it means in the "C" locale, a well known source of surprising results in POSIX tools run under a non-"C" locale. Python's re never does this: a range in a Python pattern is always defined by code point value (str patterns) or byte value (bytes patterns), unconditionally, in every locale. This design follows Python exactly, ranges are always resolved by code point or byte value (Section 2.2), independent of the LOCALE flag (Section 13.4). Omitted by design, for the same reason LOCALE itself is restricted to the "C" locale in Section 13.4: honoring arbitrary system collation would reintroduce global, environment dependent state into a design that is otherwise a pure function of its inputs, and would make the meaning of a compiled Pattern depend on a process-wide setting instead of on the flags given to re_compile.

14.5 REG_NOSUB: compiling a pattern that reports no subexpression positions

regcomp(..., REG_NOSUB) compiles a pattern that reports only whether it matched, not where its subexpressions matched, letting an implementation skip the capture bookkeeping of Section 8.4 entirely. Python's re has no equivalent compile-time flag; a compiled Pattern always reports full match and group data through Match. Out of scope: this is a pure performance optimization with no observable behavior difference, and Section 1 places convenience above performance throughout, so there is nothing here worth the added compile-time flag and the second code path it would require in both engines.

14.6 Where this design already exceeds plain POSIX regex.h

regexec takes a nul-terminated C string, so plain POSIX regex.h, on most implementations, cannot search a subject containing an embedded NUL byte at all; the widely available but non-standard REG_STARTEND extension (present in glibc and the BSDs, not part of IEEE Std 1003.1 itself) works around this only on the platforms that provide it. Python's re has never had this limitation, since str and bytes are always explicit-length, never nul-terminated, and this design follows Python and inherits the same freedom from it directly: Input (Section 9.2) is always an explicit-length byte source, and BINARY mode (Section 9.3) explicitly allows an embedded NUL as an ordinary byte value, matching the gigabyte scale, arbitrary-binary-data objective of Section 1. This item is placed last, and out of sequence with the rest of Section 14's "absent from Python re" framing, specifically so the comparison in this section is accurate in both directions rather than reading as one sided.