Documentation
¶
Overview ¶
Package vm executes a compiled program against an input using explicit backtracking with greedy, leftmost-first semantics (as in Ruby/Onigmo).
Index ¶
- Constants
- Variables
- func Match(prog *compile.Program, input string, budget int) ([]int, bool, error)
- func MatchAt(prog *compile.Program, input string, pos, budget int) ([]int, bool, error)
- func MatchTimeout(prog *compile.Program, input string, budget int, deadline time.Time) ([]int, bool, error)
- func MatchTimeoutAt(prog *compile.Program, input string, pos, budget int, deadline time.Time) ([]int, bool, error)
- func MatchTimeoutFrom(prog *compile.Program, input string, from, budget int, deadline time.Time) ([]int, bool, error)
- type DFA
Examples ¶
Constants ¶
const DefaultBudget = 100_000_000
DefaultBudget is the maximum number of VM steps a single search may take before it aborts. It is intentionally high so well-behaved patterns never hit it.
const MaxCallDepth = 4096
MaxCallDepth bounds the depth of nested subexpression calls (\g<…>) on the VM's call stack. A recursive grammar (e.g. balanced parentheses, \g<0> whole-pattern recursion) that would otherwise recurse without bound is cut off here so the match fails deterministically rather than exhausting the step budget or the Go stack. It is generous enough that any realistic nesting matches: the canonical balanced-parens idiom needs one call frame per nesting level. A call that would exceed this depth is treated as a local failure (the engine backtracks), which is how Onigmo's own recursion limit surfaces.
Variables ¶
var ErrBudget = errors.New("backtrack step budget exceeded")
ErrBudget is returned when a match exceeds the configured backtrack-step budget. It is the deterministic hook later phases use for ReDoS hardening.
var ErrTimeout = errors.New("regexp match timeout exceeded")
ErrTimeout is returned when a match exceeds the configured wall-clock deadline (Ruby's Regexp.timeout equivalent). It is the real-time backstop that complements the deterministic step budget: a pathological match is aborted by whichever limit it hits first.
Functions ¶
func Match ¶
Match runs prog against input, scanning start positions left to right until a match is found. It returns the capture slots (len == prog.NumSlots), whether a match was found, and an error only when the step budget is exhausted. It imposes no wall-clock limit; use MatchTimeout for that.
func MatchAt ¶
MatchAt attempts a match anchored exactly at byte offset pos, with \G bound to pos, while the whole input string remains visible so the line/text anchors (^ \A) and lookbehind see the real prefix input[:pos]. Unlike Match it does not scan forward: it either matches at pos or fails. This is the primitive a StringScanner-style tokenizer (e.g. a Rouge RegexLexer) needs so that a pattern's ^ matches only at a true line start and \G pins to the cursor. It returns the capture slots, whether a match occurred, and an error only when the step budget is exhausted.
func MatchTimeout ¶
func MatchTimeout(prog *compile.Program, input string, budget int, deadline time.Time) ([]int, bool, error)
MatchTimeout is Match with an additional wall-clock deadline (Ruby's Regexp.timeout equivalent). When deadline is non-zero the search aborts with ErrTimeout if it is still running past that instant; a pathological match is then bounded by whichever of the step budget or the deadline it reaches first. A zero deadline means no time limit, identical to Match, and incurs no per-step clock cost.
func MatchTimeoutAt ¶
func MatchTimeoutAt(prog *compile.Program, input string, pos, budget int, deadline time.Time) ([]int, bool, error)
MatchTimeoutAt is MatchAt with a wall-clock deadline, mirroring the MatchTimeout / Match relationship.
func MatchTimeoutFrom ¶
func MatchTimeoutFrom(prog *compile.Program, input string, from, budget int, deadline time.Time) ([]int, bool, error)
MatchTimeoutFrom is MatchTimeout with an explicit search origin: it scans start positions from byte offset `from` (rather than 0) to the end of the input, returning the leftmost match at or after `from`. The whole input string stays visible to the matcher, so the text/line anchors (\A ^), lookbehind, and \b see the real prefix input[:start] and \G binds to `from` — this is the primitive an iterative, non-overlapping scan (a FindAll walk) resumes from after a previous match, keeping its match semantics identical to a fresh whole-string search that happens to begin at `from`. A `from` past len(input) yields no match.
Types ¶
type DFA ¶
type DFA struct {
// contains filtered or unexported fields
}
DFA is the per-program lazy-NFA accelerator: the expanded NFA plus a pool of reusable thread lists. It is built once from a compiled program (BuildDFA) and reused across matches; it is safe for concurrent use because each search borrows its own thread lists from the pool. A program outside the DFA subset (a backreference, call, lookaround, atomic group, or over-large bounded loop) yields a nil DFA, and the caller falls back to the backtracking VM.
Example ¶
res, _ := syntax.ParseEnc(`[a-z]+`, syntax.UTF8)
prog := compile.CompileEnc(res, compile.UTF8)
dfa := BuildDFA(prog)
b, e, ok := dfa.Search(" hello ", compile.UTF8, 0)
fmt.Println(b, e, ok)
Output: 2 7 true
func BuildDFA ¶
BuildDFA expands prog into a DFA, returning nil when the program is outside the DFA subset (so the caller uses the backtracking VM). It is run once per compiled program. A program with a backreference or a subexpression call is rejected up front via the program's own flags; buildNFA rejects the remaining excluded constructs (lookaround, atomic groups, over-large bounded loops) while walking.
func (*DFA) MatchAt ¶
MatchAt runs the NFA anchored at pos: the whole match must BEGIN exactly at pos (so begin==pos on success), with the entire input visible so the text/line anchors (\A ^) and lookbehind see the real prefix input[:pos] and \G binds to pos. It plants a single start thread at pos and never scans forward, which is the cursor-anchored primitive a StringScanner-style tokenizer needs (Scan / Skip / match? re-matching from an advancing position). It returns the [begin,end) span and whether a match occurred.
It runs on the per-step simulation directly rather than the cached driver: the cached transition table amortises its per-position state-interning cost over a long forward scan, but a single anchored attempt visits too few positions to repay it, so the plain simulation (sharing the same pooled thread lists) is both simpler and faster here. The span is identical to what the backtracking VM anchored at pos would report for every program the DFA accepts.
func (*DFA) Search ¶
Search returns the leftmost-first match's [begin, end) byte span in input and whether any match was found, using the linear-time NFA simulation. gpos is the scan origin for \G (0 for a plain whole-string match). Results are identical to the backtracking VM's whole-match span for every program the DFA accepts.
Source Files