Module regex/vm
NFA virtual machine (Thompson simulation).
Internal to std/regex. Nothing here is public API: import
std/regex and use Regex. This module's shape changes freely.
Executes a compiled NFA program against an input string. Uses Thompson's NFA simulation with parallel state tracking for O(n×m) worst-case time complexity.
Capture slots
Each live NFA thread carries its own capture-slot array of
2 * (n_groups + 1) usize entries — two (start, end) per group plus
two for the whole match — initialised to usize.MAX ("unset"). The count
is derived from the compiled program, so there is no cap on the number
of capture groups: the engine neither errors nor truncates, and the only
bound is memory. (A MAX_SLOTS :: 200 constant used to sit here; it was
referenced nowhere and bounded nothing, so it was deleted rather than
turned into a limit the engine never had.)
Match semantics
LEFTMOST-FIRST, like Perl/PCRE and Rust's regex crate — not POSIX
leftmost-longest. Threads within one generation are processed in priority
order and the first to reach Match wins, which is exactly what makes
a|ab match just a. Priority comes from the order _add_thread walks a
Split's two targets (target_a first), so the compiler's greedy/lazy
target ordering IS the greediness.
Where it stops being linear
The seen bitmap makes each generation visit every pc at most once, which
is what buys O(n×m). A Backref breaks that premise: it needs the actual
text a group captured, so two threads at the same pc are no longer
interchangeable, and a multi-byte backreference cannot be consumed in one
generation at all — those threads go into deferred and are revived at the
byte position they land on. Lookarounds also step outside the simulation:
each one runs its own nested generation loop over the sub-program. So
patterns using only the linear-time constructs get the linear-time bound,
and the others do not.
Stability
unstable, and deliberately not public. It is one half of an internal pair
with compiler.yo — the Instr set is their private wire format and moves
in the same commit as this file. Two behaviours here are known-approximate
and will change: _to_lower folds ASCII only, so the i flag does not
match é/É, and class membership is a linear scan of unsorted ranges. A
third is unbounded: nothing caps thread count or backtracking work, so a
pathological backreference pattern has no execution budget the way Rust's
engine does. Fixing any of those changes what matches or how long it takes.
Types
One execution context: a compiled program bound to one input, plus the scratch buffers the generation loop reuses.
Cheap to create and intended to be created per attempt — Regex's
Pattern methods build one per call. It is NOT reusable across inputs (the
input is a field) and not safe to run twice concurrently (the _seen
buffers are shared mutable scratch), but exec_at may be called repeatedly
on the same instance for different start offsets, which is how find_all
walks a string.
Fields
| Name | Type | Description |
|---|---|---|
_program | NfaProgram | |
_flags | RegexFlags | |
_input | String | |
_bytes | ArrayList(u8) | |
_n_slots | usize | |
_seen | ArrayList(bool) | |
_next_seen | ArrayList(bool) |
impl(NfaVm, ...)
new : (NfaVm) fn(program : NfaProgram, flags : RegexFlags, input : String) -> NfaVmBind program and flags to input, sizing the capture array from the
program's group count and pre-allocating the two per-generation seen
bitmaps to the instruction count. Those two allocations are hoisted here,
rather than made per generation, because exec_at clears them with a
memset on every step.
Parameters
| Name | Type | Notes |
|---|---|---|
program | NfaProgram | |
flags | RegexFlags | |
input | String |
Returns: NfaVm
_decode_codepoint : (NfaVm) fn(self : NfaVm, pos : usize) -> DecodedChar_to_lower : (NfaVm) fn(self : NfaVm, cp : u32) -> u32_is_word_char : (NfaVm) fn(self : NfaVm, cp : u32) -> bool_find_prev_char_start : (NfaVm) fn(self : NfaVm, pos : usize) -> usize_prev_byte_is_newline : (NfaVm) fn(self : NfaVm, pos : usize) -> bool_cur_byte_is_newline : (NfaVm) fn(self : NfaVm, pos : usize) -> boolimpl(NfaVm, ...)
_char_matches : (NfaVm) fn(self : NfaVm, expected : u32, actual : u32) -> bool_codepoint_in_class : (NfaVm) fn(self : NfaVm, cp : u32, cls : ClassEntry) -> bool_is_word_boundary : (NfaVm) fn(self : NfaVm, pos : usize) -> boolimpl(NfaVm, ...)
_add_thread : (NfaVm) fn(self : NfaVm, list : ArrayList(NfaThread), thread : NfaThread, byte_pos : usize, seen : ArrayList(bool)) -> unitimpl(NfaVm, ...)
_run_sub_vm : (NfaVm) fn(self : NfaVm, sub_start_pc : usize, start_byte : usize, required_end : usize) -> boolParameters
| Name | Type | Notes |
|---|---|---|
self | NfaVm | |
sub_start_pc | usize | |
start_byte | usize | |
required_end | usize |
Returns: bool
impl(NfaVm, ...)
exec_at : (NfaVm) fn(self : NfaVm, start_byte : usize) -> VmMatchRun the program against the input, starting at byte offset start_byte.
Without the y (sticky) flag the caller is expected to retry at
successive offsets — this function does not itself scan forward for a
start position; the surrounding Regex methods do, using
literal_prefix to skip offsets that cannot match.
Returns the LEFTMOST-FIRST match (see the module header): threads are
processed in priority order within each generation and the first to reach
Match ends that generation, so alternation order and greedy/lazy
ordering decide the result rather than match length.
The loop runs while byte_pos <= input_len — one generation PAST the
last byte — because the zero-width assertions ($, \b) and empty
matches have to be evaluated at the end of input too.
start_byte is not boundary-checked: a mid-rune offset simply decodes
the bytes it finds there and, for a valid pattern, fails to match.
Parameters
| Name | Type | Notes |
|---|---|---|
self | NfaVm | |
start_byte | usize |
Returns: VmMatch