regex
Thompson NFA regex engine.
MVP scope :
- Literal bytes,
., escapes (\n/\t/\r/\\/\.…). - Char classes :
[abc],[^abc],[a-z]plus the\d/\D/\w/\W/\s/\Sshorthands (ASCII-only). - Quantifiers :
*,+,?,{n},{n,},{n,m}, all greedy. - Alternation
a|b. - Groups
(…): every group captures, addressable by index 1..N. - Anchors
^,$(whole-input, not multiline).
Hors-scope (post-MVP) : non-greedy *?, named groups (?<x>…),
backrefs \1, lookaround (?=…) / (?!…), Unicode properties.
Algorithm : Thompson VM (Cox, "Regular Expression Matching: the
Virtual Machine Approach"). Each compiled Pattern is an array of
Inst ops ; matching runs a BFS over a Thread set, and add_thread
deduplicates by pc within each step (the seen generation array), so a
step holds at most one thread per instruction. That per-pc dedup is what
makes the worst case O(n × m) (input length × program length), no
catastrophic backtracking, and what bounds the epsilon-closure recursion
on cyclic programs like (a*)*. Captures use the Save N op writing the
current input offset into the thread's groups array.
Pure Vader, zero host imports: WASM-ready as-is.
Types
Pattern :: structCompiled regex. Treat as opaque: the field layout may change.
Match :: structA successful match. start and end are byte offsets into the
input string (end exclusive). groups[0] is always the whole
match ; groups[i] (1 ≤ i ≤ group_count) is the i-th capture, or
empty if the group never matched.
Fields
start: i64 end: i64 groups: string[] RegexError :: structError returned by compile when the pattern doesn't parse.
Fields
msg: string position: i64 Inst :: InstChar | InstAny | InstClass | InstMatch | InstJump | InstSplit | InstSave | InstAnchorStart | InstAnchorEndInstChar :: structMatch a single literal codepoint c. Advances input by one char.
Fields
c: char InstAny :: structMatch any codepoint except \n.
InstClass :: structMatch any codepoint in ranges. Each [lo, hi] is inclusive ;
negated == true flips the membership test.
Fields
ranges: CharRange[] negated: bool CharRange :: structAn inclusive [lo, hi] codepoint range inside an InstClass. Part of the
public compiled-instruction surface: InstClass.ranges exposes these, so a
consumer introspecting a compiled Inst can read them.
Fields
lo: char hi: char InstMatch :: structAccept state.
InstJump :: structUnconditional jump to target.
Fields
target: i64 InstSplit :: structNon-deterministic split: spawn one thread at a, another at b.
Fields
a: i64 b: i64 InstSave :: structRecord the current input offset into groups[slot] (and advance pc).
Slot 0 / 1 = group 0 start/end (whole match) ;
2 * i / 2 * i + 1 = group i start/end.
Fields
slot: i64 InstAnchorStart :: struct^: match only at input position 0.
InstAnchorEnd :: struct$: match only at input length.
Functions
compile :: fn(pattern: string) -> Pattern | RegexErrorCompile a regex source string into a Pattern. Anchors ^/$
inside the pattern bind to the input boundaries. The pattern is
implicitly anchored at the start during matches (whole input)
and unanchored during find / find_all / replace_all.
Parameters
| pattern | string | No description. |