Module regex/compiler
NFA compiler — compiles a RegexNode AST into a flat list of NFA instructions
using Thompson's construction algorithm.
Internal to std/regex. Nothing here is public API: import
std/regex and use Regex. This module's shape changes freely.
What it produces
A NfaProgram: one flat ArrayList(Instr) addressed by index (the "pc"),
plus a side table of character classes, the group count, the named-group
table and an optional literal prefix. Control flow is entirely by pc —
Split forks to two pcs, Jump goes to one — so the tree shape is gone
and the VM never recurses over an AST.
compile wraps the pattern in the group-0 saves, so every program is
Save 0, the pattern's own instructions, Save 1, Match. That is why
group 0 needs no special case anywhere downstream: it is just the
outermost capture. Capture slots are laid out two per group — group g
writes 2g and 2g+1 — which is where the VM's 2 * (n_groups + 1) slot
allocation comes from.
Where the cost is
Thompson's construction is linear in the pattern EXCEPT for a bounded
quantifier: {m,n} is compiled by emitting n - m optional copies of the
body, so (ab){1,500} emits ~500 copies and (a{100}){100} emits 10 000.
There is no repetition-size limit, unlike Rust's regex crate, which
refuses a pattern whose compiled size exceeds a budget. * and + are
loops and cost nothing extra.
Greediness is not a property of any instruction — it is only the ORDER a
Split's two targets are written in, body-first for greedy and exit-first
for lazy. The VM always tries target_a before target_b.
Stability
unstable, and deliberately not public. InstrKind and Instr are the
engine's internal wire format between this module and vm.yo: they change
together, in the same commit, and neither is meaningful without the other.
Two known changes are pending — a repetition-size budget, so {m,n} cannot
blow the program up, and a sorted/merged class table so class membership is
not a linear scan — and both alter the produced program. NfaProgram is
exported only because Regex has to hold one and clear its
literal_prefix; treat that as an implementation detail, not API.
Types
The compiler itself: a NfaProgram under construction plus the emit
helpers that append to it. SINGLE USE — compile returns the program it
has been accumulating into, so a second compile on the same instance
would append to a finished program. Regex.new_with_flags builds a fresh
one per pattern.
Fields
| Name | Type | Description |
|---|---|---|
_program | NfaProgram |
impl(NfaCompiler, ...)
new : (NfaCompiler) fn() -> NfaCompilerA compiler with an empty program. Use it for exactly one compile.
Returns: NfaCompiler
_emit : (NfaCompiler) fn(self : NfaCompiler, instr : Instr) -> usize_current_pc : (NfaCompiler) fn(self : NfaCompiler) -> usize_add_class : (NfaCompiler) fn(self : NfaCompiler, ranges : ArrayList(CharRange), negated : bool) -> usizeParameters
| Name | Type | Notes | Description |
|---|---|---|---|
self | NfaCompiler | ||
ranges | ArrayList(CharRange) | Inclusive code-point ranges, exactly as the parser built them: NOT sorted, NOT merged and possibly overlapping, so membership is a linear scan in the VM rather than a binary search. | |
negated | bool |
|
Returns: usize
impl(NfaCompiler, ...)
_compile_node : (NfaCompiler) fn(self : NfaCompiler, node : RegexNode) -> unitimpl(NfaCompiler, ...)
_extract_literal_prefix : (NfaCompiler) fn(self : NfaCompiler) -> unitimpl(NfaCompiler, ...)
compile : (NfaCompiler) fn(self : NfaCompiler, root : RegexNode, n_groups : usize, group_names : ArrayList(GroupNameEntry)) -> NfaProgramLower the AST root into a runnable program.
Wraps the pattern in the group-0 captures and terminates it, so the
result is always Save 0 / pattern / Save 1 / Match — which is why
nothing downstream special-cases the whole match. n_groups and
group_names come from the parser and are stored verbatim; this function
does not re-derive or validate them.
Finally extracts the literal prefix, so the returned program is complete: after this call the compiler has no more work to do and the program is only read.
Parameters
| Name | Type | Notes | Description |
|---|---|---|---|
self | NfaCompiler | ||
root | RegexNode | ||
n_groups | usize | How many capturing groups the pattern declared, NOT counting group 0.
The VM allocates | |
group_names | ArrayList(GroupNameEntry) |
|
Returns: NfaProgram
A compiled pattern: everything the VM needs and nothing about a particular
input. A Regex holds one and runs it against many haystacks, so it must
stay immutable during execution — the VM only reads it.
Fields
| Name | Type | Description |
|---|---|---|
instructions | ArrayList(Instr) | The program. Instruction |
classes | ArrayList(ClassEntry) | Character classes, referenced by |
n_groups | usize | How many capturing groups the pattern declared, NOT counting group 0.
The VM allocates |
group_names | ArrayList(GroupNameEntry) |
|
literal_prefix | ArrayList(u8) | ASCII bytes every match must begin with, or empty when there is no
such prefix — a |
One entry of a program's character-class table, referenced by index from a
CharClass instruction. Kept out of the instruction so Instr can stay a
fixed-size value struct with no owned allocation.
Fields
| Name | Type | Description |
|---|---|---|
ranges | ArrayList(CharRange) | Inclusive code-point ranges, exactly as the parser built them: NOT sorted, NOT merged and possibly overlapping, so membership is a linear scan in the VM rather than a binary search. |
negated | bool |
|