nfa

package
v0.0.0-...-2f994d5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 15, 2026 License: MIT Imports: 6 Imported by: 0

Documentation

Overview

Package nfa provides a Thompson NFA (Non-deterministic Finite Automaton) implementation for regex matching.

This package implements the core Thompson NFA algorithm along with a PikeVM execution engine. The NFA is compiled from regexp/syntax.Regexp patterns and can be used for matching with full support for capturing groups (future).

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrInvalidState indicates an invalid NFA state ID was encountered
	ErrInvalidState = errors.New("invalid NFA state")

	// ErrInvalidPattern indicates the regex pattern is invalid or unsupported
	ErrInvalidPattern = errors.New("invalid regex pattern")

	// ErrTooComplex indicates the pattern is too complex to compile
	ErrTooComplex = errors.New("pattern too complex")

	// ErrCompilation indicates a general NFA compilation failure
	ErrCompilation = errors.New("NFA compilation failed")

	// ErrInvalidConfig indicates invalid configuration was provided
	ErrInvalidConfig = errors.New("invalid NFA configuration")

	// ErrNoMatch indicates no match was found (not an error, used internally)
	ErrNoMatch = errors.New("no match found")
)

Common NFA errors

Functions

func ContainsDot 

func ContainsDot(re *syntax.Regexp) bool

ContainsDot checks if the regex pattern contains '.' (any char or any char except newline). When true, the pattern will benefit from ASCII-only NFA compilation for ASCII-only inputs.

This is used for ASCII runtime detection optimization (V11-002): patterns with '.' create ~28 NFA states for UTF-8 handling, but only 1-2 states in ASCII mode. Runtime detection allows using the faster ASCII NFA when input is ASCII.

func ExtractCharClassRanges 

func ExtractCharClassRanges(re *syntax.Regexp) [][2]byte

ExtractCharClassRanges extracts byte ranges from a simple char_class+ pattern AST. Returns nil if the pattern is not a simple char_class+ pattern.

Simple char_class+ patterns are:

  • [a-z]+, [A-Z]+, [0-9]+ (single range)
  • [\w]+, [\d]+, [\s]+ (predefined classes)
  • [a-zA-Z0-9_]+ (multiple ranges)

NOT supported:

  • char_class* patterns (zero-width matches not handled by CharClassSearcher)
  • Patterns with anchors (^, $)
  • Patterns with alternation outside char class
  • Patterns with concatenation (abc[\w]+)
  • Unicode char classes (need rune handling)

func HasImpossibleEndAnchor 

func HasImpossibleEndAnchor(re *syntax.Regexp) bool

HasImpossibleEndAnchor checks if the pattern contains an end anchor ($, \z) that is NOT at the end of the pattern. Such patterns like `$00` can never match because nothing can follow the end-of-string assertion.

Examples:

  • `$00` → true ($ followed by "00" - impossible)
  • `00$` → false ($ at end - valid end-anchored pattern)
  • `a$b` → true ($ followed by "b" - impossible)
  • `(a$)` → false ($ at end of group - valid)

func IsBranchDispatchPattern 

func IsBranchDispatchPattern(re *syntax.Regexp) bool

IsBranchDispatchPattern checks if pattern is suitable for branch dispatch. Pattern must be start-anchored alternation with distinct first bytes per branch.

func IsCompositeCharClassPattern 

func IsCompositeCharClassPattern(re *syntax.Regexp) bool

IsCompositeCharClassPattern returns true if the pattern is a valid composite char class pattern. A composite pattern is a concatenation of 2+ quantified character classes like [a-zA-Z]+[0-9]+.

Requirements:

  • Must be OpConcat
  • Each sub-pattern must be a quantified char class (OpPlus, OpStar, OpQuest, OpRepeat)
  • At least 2 parts
  • No anchors, no captures, no alternations

func IsCompositeSequenceDFAPattern 

func IsCompositeSequenceDFAPattern(re *syntax.Regexp) bool

IsCompositeSequenceDFAPattern checks if a pattern is suitable for CompositeSequenceDFA.

func IsPatternEndAnchored 

func IsPatternEndAnchored(re *syntax.Regexp) bool

IsPatternEndAnchored checks if a pattern is inherently anchored at end (ends with \z).

A pattern is end-anchored if it ends with:

  • OpEndText (\z or non-multiline $) - only matches at EOF

Note: OpEndLine (multiline $ with (?m)) is NOT considered end-anchored because it can match at multiple positions (before each \n and at EOF). Using reverse search for multiline $ would miss matches before \n characters.

This is used to select the ReverseAnchored strategy which searches backward from the end of haystack for O(m) instead of O(n*m) performance.

IMPORTANT: This also checks for internal end anchors (like in `(a$)b$`). If there's an end anchor that's NOT at the very end, ReverseAnchored won't work.

func IsPatternStartAnchored 

func IsPatternStartAnchored(re *syntax.Regexp) bool

IsPatternStartAnchored checks if ANY branch of the pattern starts with ^ or \A. This is used to prevent UseReverseAnchored strategy selection for patterns like `^a?$|^b?$` where the start anchor constrains matching positions.

Unlike IsPatternEndAnchored which requires ALL branches to be end-anchored, this function returns true if ANY branch has a start anchor, because reverse search cannot properly handle partial start anchoring in alternations.

func IsSimpleCharClassPlus 

func IsSimpleCharClassPlus(re *syntax.Regexp) bool

IsSimpleCharClassPlus returns true if the pattern is a simple char_class+ pattern that can use CharClassSearcher for optimized matching.

func PatternHasUTF8Dependence 

func PatternHasUTF8Dependence(re *syntax.Regexp) bool

PatternHasUTF8Dependence checks if the pattern has constructs that depend on UTF-8 handling beyond '.' (such as Unicode character classes, word boundaries, etc).

When this returns true, ASCII optimization may not be valid for all cases. Currently checks for:

  • Unicode character classes (\p{...}, \P{...})
  • Word boundaries (\b, \B) - these depend on Unicode word chars in Go regexp

Note: This is conservative - patterns that ONLY use '.' and ASCII literals can safely use ASCII optimization.

Types

type BacktrackerState 

type BacktrackerState struct {
	// Visited stores generation numbers for (state, position) pairs.
	// Layout: Visited[pos * NumStates + state] = generation when visited.
	// Uses uint16 for 2x memory savings over uint32 (65536 generations before overflow).
	// Generation-based approach enables O(1) reset between search attempts.
	Visited []uint16

	// Generation is incremented for each new search attempt (0-65535).
	// A position is considered visited if Visited[idx] == Generation.
	// When overflow occurs, array is cleared and generation resets to 1.
	Generation uint16

	// NumStates is cached for index calculations (column stride)
	NumStates int

	// InputLen is cached for bounds checking
	InputLen int

	// SpanStart is the starting offset within the haystack for this search.
	// The visited table is sized for the span [SpanStart, SpanStart+InputLen],
	// and positions are stored relative to SpanStart.
	// This follows Rust regex's Input span model: the visited table covers
	// only the search span, while the full haystack remains available for
	// zero-width assertions like \b that need backward context.
	SpanStart int

	// Longest enables leftmost-longest match semantics (POSIX/AWK compatibility).
	// When true, explores all branches to find the longest match instead of
	// returning on the first match found.
	Longest bool
}

BacktrackerState holds mutable per-search state for BoundedBacktracker. This struct should be pooled (via sync.Pool) for concurrent usage. Each goroutine must use its own BacktrackerState instance.

func NewBacktrackerState 

func NewBacktrackerState() *BacktrackerState

NewBacktrackerState creates a new mutable state for use with BoundedBacktracker. This should be pooled via sync.Pool for concurrent usage.

type BoundedBacktracker 

type BoundedBacktracker struct {
	// contains filtered or unexported fields
}

BoundedBacktracker implements a bounded backtracking regex matcher. It uses generation-based visited tracking with uint8 for (state, position) pairs, providing 4x memory efficiency over uint32 tracking while maintaining O(1) reset.

Memory usage: 1 byte per (state, position) pair = numStates * inputLen bytes. For 35 states and 6MB input: 35 * 6MB = 210MB.

This engine is selected when:

  • numStates * (haystackLen + 1) <= maxVisitedSize
  • No prefilter is available (no good literals)
  • Pattern doesn't benefit from DFA (simple character classes)

BoundedBacktracker is 2-5x faster than PikeVM for patterns like \d+, \w+, [a-z]+.

Thread safety: BoundedBacktracker config is immutable after creation. Use BacktrackerState for per-search mutable state to enable concurrent usage.

func NewBoundedBacktracker 

func NewBoundedBacktracker(nfa *NFA) *BoundedBacktracker

NewBoundedBacktracker creates a new bounded backtracker for the given NFA. Default maxVisitedSize is 32M entries (64MB memory with uint16), allowing ~900KB inputs for patterns with 35 states like (\w{2,8})+.

This large limit is required for UseBoundedBacktracker strategy where BT is the primary engine with leftmost-longest semantics. PikeVM fallback gives leftmost-first results which would break correctness.

For UseNFA strategy (where BT is optional), use NewBoundedBacktrackerSmall.

func NewBoundedBacktrackerSmall 

func NewBoundedBacktrackerSmall(nfa *NFA) *BoundedBacktracker

NewBoundedBacktrackerSmall creates a BoundedBacktracker with Rust-aligned visited capacity (128K entries = 256KB). Use for UseNFA paths where BT is an optional optimization and PikeVM is the correct fallback.

This prevents massive visited table allocations (37MB+) for patterns like ` [5][0-9]{2} | [4][0-9]{2} ` on large inputs. When BT can't handle the input size, the caller falls back to PikeVM which is O(n*states) memory per step, not O(n*states) total.

Matches Rust regex's default visited_capacity of 256KB.

func (*BoundedBacktracker) CanHandle 

func (b *BoundedBacktracker) CanHandle(haystackLen int) bool

CanHandle returns true if this engine can handle the given input size. Returns false if the visited array would exceed maxVisitedSize entries.

func (*BoundedBacktracker) IsMatch 

func (b *BoundedBacktracker) IsMatch(haystack []byte) bool

IsMatch returns true if the pattern matches anywhere in the haystack. This is optimized for boolean-only matching. This method uses internal state and is NOT thread-safe. For concurrent usage, use IsMatchWithState.

func (*BoundedBacktracker) IsMatchAnchored 

func (b *BoundedBacktracker) IsMatchAnchored(haystack []byte) bool

IsMatchAnchored returns true if the pattern matches at the start of haystack. This method uses internal state and is NOT thread-safe.

func (*BoundedBacktracker) IsMatchAnchoredWithState 

func (b *BoundedBacktracker) IsMatchAnchoredWithState(haystack []byte, state *BacktrackerState) bool

IsMatchAnchoredWithState returns true if the pattern matches at the start of haystack. This method uses external state and IS thread-safe when each goroutine uses its own state.

func (*BoundedBacktracker) IsMatchWithState 

func (b *BoundedBacktracker) IsMatchWithState(haystack []byte, state *BacktrackerState) bool

IsMatchWithState returns true if the pattern matches anywhere in the haystack. This method uses external state and IS thread-safe when each goroutine uses its own state.

func (*BoundedBacktracker) MaxInputSize 

func (b *BoundedBacktracker) MaxInputSize() int

MaxInputSize returns the maximum input size this engine can handle. This is derived from maxVisitedSize / numStates - 1.

func (*BoundedBacktracker) MaxVisitedSize 

func (b *BoundedBacktracker) MaxVisitedSize() int

MaxVisitedSize returns the maximum visited array size in entries.

func (*BoundedBacktracker) NumStates 

func (b *BoundedBacktracker) NumStates() int

NumStates returns the number of NFA states (for state allocation).

func (*BoundedBacktracker) Search 

func (b *BoundedBacktracker) Search(haystack []byte) (int, int, bool)

Search finds the first match in the haystack. Returns (start, end, true) if found, (-1, -1, false) otherwise. This method uses internal state and is NOT thread-safe.

func (*BoundedBacktracker) SearchAt 

func (b *BoundedBacktracker) SearchAt(haystack []byte, at int) (int, int, bool)

SearchAt finds the first match starting from position 'at'. Returns (start, end, true) if found, (-1, -1, false) otherwise. This is used by FindAll* operations for efficient iteration. In longest mode, finds the longest match at the leftmost position. This method uses internal state and is NOT thread-safe.

func (*BoundedBacktracker) SearchAtWithState 

func (b *BoundedBacktracker) SearchAtWithState(haystack []byte, at int, state *BacktrackerState) (int, int, bool)

SearchAtWithState finds the first match starting from position 'at'. Returns (start, end, true) if found, (-1, -1, false) otherwise. This method uses external state and IS thread-safe when each goroutine uses its own state.

func (*BoundedBacktracker) SearchWithState 

func (b *BoundedBacktracker) SearchWithState(haystack []byte, state *BacktrackerState) (int, int, bool)

SearchWithState finds the first match in the haystack. Returns (start, end, true) if found, (-1, -1, false) otherwise. This method uses external state and IS thread-safe when each goroutine uses its own state.

func (*BoundedBacktracker) SetLongest 

func (b *BoundedBacktracker) SetLongest(longest bool)

SetLongest enables or disables leftmost-longest match semantics on internal state. When enabled, the backtracker finds the longest match at each position instead of returning on the first match found. Note: For thread-safe usage, set Longest directly on BacktrackerState.

type BranchDispatcher 

type BranchDispatcher struct {
	// contains filtered or unexported fields
}

BranchDispatcher provides O(1) branch selection for anchored alternations. For patterns like ^(\d+|UUID|hex32), it dispatches directly to the matching branch based on the first byte, avoiding the need to try all branches.

This is only applicable when:

  • Pattern is start-anchored (^)
  • Top-level is an alternation (a|b|c)
  • Each branch has distinct first bytes (no overlap)

Performance: O(1) branch selection vs O(branches) for naive approach. For 3-branch pattern: ~3x faster on match, ~10x faster on no-match.

func NewBranchDispatcher 

func NewBranchDispatcher(re *syntax.Regexp) *BranchDispatcher

NewBranchDispatcher creates a dispatcher for an anchored alternation. Returns nil if the pattern is not suitable for branch dispatch.

func (*BranchDispatcher) IsMatch 

func (d *BranchDispatcher) IsMatch(haystack []byte) bool

IsMatch returns true if the haystack matches the pattern. Only checks at position 0 (for anchored patterns).

func (*BranchDispatcher) Search 

func (d *BranchDispatcher) Search(haystack []byte) (int, int, bool)

Search finds the first match starting at position 0. Returns (start, end, found).

type BuildError 

type BuildError struct {
	Message string
	StateID StateID
}

BuildError represents an error during NFA construction via the Builder API

func (*BuildError) Error 

func (e *BuildError) Error() string

Error implements the error interface

type BuildOption 

type BuildOption func(*NFA)

BuildOption is a functional option for configuring the built NFA

func WithAnchored 

func WithAnchored(anchored bool) BuildOption

WithAnchored sets whether the NFA requires anchored matching

func WithCaptureCount 

func WithCaptureCount(count int) BuildOption

WithCaptureCount sets the number of capture groups in the NFA

func WithCaptureNames 

func WithCaptureNames(names []string) BuildOption

WithCaptureNames sets the names of capture groups in the NFA. The slice should have length equal to captureCount. Index 0 should be "" (entire match), named groups have their names, unnamed groups are "".

func WithPatternCount 

func WithPatternCount(count int) BuildOption

WithPatternCount sets the number of patterns in the NFA

func WithUTF8 

func WithUTF8(utf8 bool) BuildOption

WithUTF8 sets whether the NFA respects UTF-8 boundaries

type Builder 

type Builder struct {
	// contains filtered or unexported fields
}

Builder constructs NFAs incrementally using a low-level API. This provides full control over NFA construction and is used by the Compiler.

func NewBuilder 

func NewBuilder() *Builder

NewBuilder creates a new NFA builder with default capacity

func NewBuilderWithCapacity 

func NewBuilderWithCapacity(capacity int) *Builder

NewBuilderWithCapacity creates a new NFA builder with specified initial capacity

func (*Builder) AddByteRange 

func (b *Builder) AddByteRange(lo, hi byte, next StateID) StateID

AddByteRange adds a state that transitions on a single byte or byte range [lo, hi]. For a single byte, set lo == hi.

func (*Builder) AddCapture 

func (b *Builder) AddCapture(captureIndex uint32, isStart bool, next StateID) StateID

AddCapture adds a capture boundary state. captureIndex is the capture group number (1-based for explicit groups, 0 for entire match). isStart is true for opening boundary '(', false for closing ')'. next is the state to transition to after recording the capture position.

func (*Builder) AddEpsilon 

func (b *Builder) AddEpsilon(next StateID) StateID

AddEpsilon adds a state with a single epsilon transition (no input consumed)

func (*Builder) AddFail 

func (b *Builder) AddFail() StateID

AddFail adds a dead state with no transitions

func (*Builder) AddLook 

func (b *Builder) AddLook(look Look, next StateID) StateID

AddLook adds a zero-width assertion state (look-around). look is the assertion type (start/end of text/line). next is the state to transition to if the assertion succeeds.

func (*Builder) AddMatch 

func (b *Builder) AddMatch() StateID

AddMatch adds a match (accepting) state and returns its ID

func (*Builder) AddQuantifierSplit 

func (b *Builder) AddQuantifierSplit(left, right StateID) StateID

AddQuantifierSplit adds a state with epsilon transitions for quantifiers (*, +, ?, {n,m}). Unlike alternation splits, quantifier splits don't affect thread priority. Left branch is the "continue/repeat" path, right branch is the "exit" path. This distinction is crucial for correct leftmost-first matching semantics.

func (*Builder) AddRuneAny 

func (b *Builder) AddRuneAny(next StateID) StateID

AddRuneAny adds a state that matches any Unicode codepoint (including newlines). This is used for (?s). (dot with DOTALL flag). The state consumes 1-4 bytes (UTF-8 encoded rune) and transitions to next.

func (*Builder) AddRuneAnyNotNL 

func (b *Builder) AddRuneAnyNotNL(next StateID) StateID

AddRuneAnyNotNL adds a state that matches any Unicode codepoint except newline. This is used for the default . (dot) behavior. The state consumes 1-4 bytes (UTF-8 encoded rune) and transitions to next.

func (*Builder) AddSparse 

func (b *Builder) AddSparse(transitions []Transition) StateID

AddSparse adds a state with multiple byte range transitions (character class). The transitions slice is copied to avoid aliasing issues.

func (*Builder) AddSplit 

func (b *Builder) AddSplit(left, right StateID) StateID

AddSplit adds a state with epsilon transitions to two states (alternation). This is used for alternation (a|b). For quantifiers, use AddQuantifierSplit.

func (*Builder) Build 

func (b *Builder) Build(opts ...BuildOption) (*NFA, error)

Build finalizes and returns the constructed NFA. Options can be provided to set anchored/utf8 modes and pattern count.

func (*Builder) Patch 

func (b *Builder) Patch(stateID, target StateID) error

Patch updates a state's target. This is used during compilation to handle forward references (e.g., loops, alternations). This only works for states with a single 'next' target (ByteRange, Epsilon).

func (*Builder) PatchSplit 

func (b *Builder) PatchSplit(stateID StateID, left, right StateID) error

PatchSplit updates the left or right target of a Split state

func (*Builder) SetStart deprecated 

func (b *Builder) SetStart(start StateID)

SetStart sets the starting state for the NFA (both anchored and unanchored)

Deprecated: Use SetStarts() to set dual start states explicitly

func (*Builder) SetStarts 

func (b *Builder) SetStarts(anchored, unanchored StateID)

SetStarts sets separate anchored and unanchored start states

func (*Builder) States 

func (b *Builder) States() int

States returns the current number of states

func (*Builder) Validate 

func (b *Builder) Validate() error

Validate checks that the NFA is well-formed: - Start state is valid - All state references point to valid states - No dangling references

type ByteClassSet 

type ByteClassSet struct {
	// contains filtered or unexported fields
}

ByteClassSet tracks byte boundaries during NFA construction.

During NFA compilation, we track which bytes are "boundary" bytes where equivalence classes change. For example, if pattern is [a-z], then bytes 'a'-1 and 'z' are boundaries.

Algorithm:

  1. For each ByteRange [lo, hi] in NFA transitions: - If lo > 0: mark lo-1 as boundary - Mark hi as boundary
  2. Convert boundaries to classes by incrementing class at each boundary

func NewByteClassSet 

func NewByteClassSet() *ByteClassSet

NewByteClassSet creates an empty ByteClassSet with no boundaries.

func (*ByteClassSet) ByteClasses 

func (bcs *ByteClassSet) ByteClasses() ByteClasses

ByteClasses converts the boundary set into a ByteClasses lookup table.

Algorithm: Walk through all 256 bytes, incrementing the class number each time we encounter a boundary byte.

func (*ByteClassSet) Merge 

func (bcs *ByteClassSet) Merge(other *ByteClassSet)

Merge combines another ByteClassSet into this one. Used when building composite patterns.

func (*ByteClassSet) SetByte 

func (bcs *ByteClassSet) SetByte(b byte)

SetByte marks a single byte as having a distinct transition. Equivalent to SetRange(b, b).

func (*ByteClassSet) SetRange 

func (bcs *ByteClassSet) SetRange(start, end byte)

SetRange marks a byte range [start, end] as having distinct transitions. This sets boundary bits at start-1 and end.

type ByteClasses 

type ByteClasses struct {
	// contains filtered or unexported fields
}

ByteClasses maps each byte value to its equivalence class.

ByteClasses is an alphabet reduction technique that groups bytes into equivalence classes based on how the regex treats them. Instead of maintaining 256 transitions per DFA state, transitions are reduced to N classes (typically 4-64), dramatically reducing memory footprint.

Key principle: Two bytes belong to the same equivalence class if they will never cause different transitions in any DFA state for the given regex.

Example for pattern [a-z]+:

  • Class 0: bytes 0x00-0x60 (before 'a')
  • Class 1: bytes 0x61-0x7a ('a' to 'z')
  • Class 2: bytes 0x7b-0xff (after 'z')

Memory impact:

  • Without ByteClasses: 256 transitions per state
  • With ByteClasses: ~8-16 transitions per state (15-30x reduction)

func NewByteClasses 

func NewByteClasses() ByteClasses

NewByteClasses creates a new ByteClasses where all bytes are in class 0.

func SingletonByteClasses 

func SingletonByteClasses() ByteClasses

SingletonByteClasses creates ByteClasses where each byte is its own class. This is equivalent to no alphabet reduction (256 classes).

func (*ByteClasses) AlphabetLen 

func (bc *ByteClasses) AlphabetLen() int

AlphabetLen returns the total number of equivalence classes. This is the number of distinct class values + 1 for potential EOI sentinel.

func (*ByteClasses) Elements 

func (bc *ByteClasses) Elements(class byte) []byte

Elements returns all bytes that belong to the given equivalence class.

func (*ByteClasses) Get 

func (bc *ByteClasses) Get(b byte) byte

Get returns the equivalence class for the given byte. This is an O(1) lookup.

func (*ByteClasses) IsEmpty 

func (bc *ByteClasses) IsEmpty() bool

IsEmpty returns true if all bytes are in the same equivalence class (class 0). This typically means the regex matches any byte or no bytes at all.

func (*ByteClasses) IsSingleton 

func (bc *ByteClasses) IsSingleton() bool

IsSingleton returns true if each byte is its own equivalence class. This means no alphabet reduction is possible.

func (*ByteClasses) Representatives 

func (bc *ByteClasses) Representatives() []byte

Representatives returns a slice of representative bytes, one for each class. Each representative can be used to compute transitions for all bytes in that class.

type CharClassSearcher 

type CharClassSearcher struct {
	// contains filtered or unexported fields
}

CharClassSearcher provides optimized search for simple character class patterns. For patterns like [\w]+, [a-z]+, \d+ where:

  • Pattern is just a repeated character class (no alternation, no anchors)
  • Character class can be represented as byte ranges

This searcher uses a 256-byte lookup table for O(1) membership test, avoiding the overhead of recursive backtracking.

Performance: 3-5x faster than BoundedBacktracker for char_class patterns.

Note: SIMD optimization was evaluated but found to be slower for char_class patterns because matches are frequent (30-50% of positions) and short. The scalar lookup table approach is optimal for this use case. For large-scale char_class search, consider using Lazy DFA instead.

func NewCharClassSearcher 

func NewCharClassSearcher(ranges [][2]byte, minMatch int) *CharClassSearcher

NewCharClassSearcher creates a searcher from byte ranges. ranges is a list of [lo, hi] pairs where bytes in [lo, hi] match. minMatch is 1 for + quantifier, 0 for * quantifier.

func NewCharClassSearcherFromNFA 

func NewCharClassSearcherFromNFA(n *NFA) *CharClassSearcher

NewCharClassSearcherFromNFA extracts byte ranges from an NFA and creates a searcher. Returns nil if the NFA is not a simple char_class+ pattern.

func (*CharClassSearcher) CanHandle 

func (s *CharClassSearcher) CanHandle(_ int) bool

CanHandle returns true - CharClassSearcher can handle any input size.

func (*CharClassSearcher) Count 

func (s *CharClassSearcher) Count(haystack []byte) int

Count returns the number of non-overlapping matches using single-pass state machine. This is faster than len(FindAllIndices()) because it doesn't allocate a results slice.

func (*CharClassSearcher) FindAllIndices 

func (s *CharClassSearcher) FindAllIndices(haystack []byte, results [][2]int) [][2]int

FindAllIndices finds all non-overlapping matches using a single-pass state machine. This is significantly faster than repeated SearchAt calls because:

  • No per-match function call overhead
  • Better CPU branch prediction (consistent state transitions)
  • Single pass through input (cache-friendly)

Returns slice of [start, end] pairs. If results slice is provided and has sufficient capacity, it will be reused to avoid allocation.

This implements the Rust regex approach: streaming state machine with SEARCHING/MATCHING states instead of separate find-start/find-end loops.

func (*CharClassSearcher) IsMatch 

func (s *CharClassSearcher) IsMatch(haystack []byte) bool

IsMatch returns true if pattern matches anywhere in haystack.

func (*CharClassSearcher) Search 

func (s *CharClassSearcher) Search(haystack []byte) (int, int, bool)

Search finds the first match in haystack. Returns (start, end, true) if found, (-1, -1, false) otherwise.

func (*CharClassSearcher) SearchAt 

func (s *CharClassSearcher) SearchAt(haystack []byte, at int) (int, int, bool)

SearchAt finds the first match starting from position at. Returns (start, end, true) if found, (-1, -1, false) otherwise.

type CompileError 

type CompileError struct {
	Pattern string
	Err     error
}

CompileError wraps compilation errors with additional context

func (*CompileError) Error 

func (e *CompileError) Error() string

Error implements the error interface

func (*CompileError) Unwrap 

func (e *CompileError) Unwrap() error

Unwrap returns the underlying error

type Compiler 

type Compiler struct {
	// contains filtered or unexported fields
}

Compiler compiles regexp/syntax.Regexp patterns into Thompson NFAs

func NewCompiler 

func NewCompiler(config CompilerConfig) *Compiler

NewCompiler creates a new NFA compiler with the given configuration

func NewDefaultCompiler 

func NewDefaultCompiler() *Compiler

NewDefaultCompiler creates a new NFA compiler with default configuration

func (*Compiler) Compile 

func (c *Compiler) Compile(pattern string) (*NFA, error)

Compile compiles a regex pattern string into an NFA

func (*Compiler) CompileRegexp 

func (c *Compiler) CompileRegexp(re *syntax.Regexp) (*NFA, error)

CompileRegexp compiles a parsed syntax.Regexp into an NFA

type CompilerConfig 

type CompilerConfig struct {
	// UTF8 determines whether the NFA respects UTF-8 boundaries.
	// When true, empty matches that split UTF-8 sequences are avoided.
	UTF8 bool

	// Anchored forces the pattern to match only at the start of input
	Anchored bool

	// DotNewline determines whether '.' matches '\n'
	DotNewline bool

	// ASCIIOnly when true, compiles '.' to match only ASCII bytes (0x00-0x7F).
	// This dramatically reduces NFA state count (1 state vs ~28 states) and
	// improves performance for patterns with '.' when input is known to be ASCII.
	//
	// When false (default), '.' compiles to match any valid UTF-8 codepoint,
	// requiring ~28 NFA states to handle all valid UTF-8 byte sequences.
	//
	// This is used for ASCII runtime detection optimization (V11-002):
	// compile both ASCII and UTF-8 NFAs, select at runtime based on input.
	ASCIIOnly bool

	// UseRuneStates when true, compiles '.' as a single sparse dispatch state
	// instead of ~9 split states chaining UTF-8 byte-range alternation branches.
	// The sparse state maps each leading byte range directly to its continuation
	// chain, giving PikeVM O(1) dispatch instead of O(branches) DFS traversal.
	//
	// Measured 2.8-4.8x PikeVM speedup on dot-heavy patterns.
	// Safe for all engines (DFA, PikeVM, BoundedBacktracker) since it uses
	// standard byte-range states, just organized as sparse instead of splits.
	UseRuneStates bool

	// MaxRecursionDepth limits recursion during compilation to prevent stack overflow
	// Default: 100
	MaxRecursionDepth int
}

CompilerConfig configures NFA compilation behavior

func DefaultCompilerConfig 

func DefaultCompilerConfig() CompilerConfig

DefaultCompilerConfig returns a compiler configuration with sensible defaults

type CompositeSearcher 

type CompositeSearcher struct {
	// contains filtered or unexported fields
}

CompositeSearcher is a specialized searcher for concatenated character class patterns. For patterns like `[a-zA-Z]+[0-9]+`, it uses sequential lookup tables to achieve 5-6x speedup over BoundedBacktracker.

Algorithm:

  1. Each char class part has a [256]bool membership table for O(1) lookup
  2. Greedy matching: consume as many characters as possible for each part
  3. Backtrack if a part doesn't meet its minimum match requirement

Example patterns:

  • [a-zA-Z]+[0-9]+ → letters followed by digits
  • \d+\s+\w+ → digits, whitespace, word chars
  • [a-z]+[A-Z]+ → lowercase then uppercase

Thread safety: NOT thread-safe. For concurrent usage, each goroutine needs its own instance.

Reference: https://github.com/donge/coregex/issues/72

func NewCompositeSearcher 

func NewCompositeSearcher(re *syntax.Regexp) *CompositeSearcher

NewCompositeSearcher creates a CompositeSearcher from a syntax.Regexp. Returns nil if the pattern is not a valid composite char class pattern.

Valid patterns are concatenations of character classes with +, *, ?, or {n,m} quantifiers.

func (*CompositeSearcher) IsMatch 

func (c *CompositeSearcher) IsMatch(haystack []byte) bool

IsMatch returns true if the haystack contains a match.

func (*CompositeSearcher) Search 

func (c *CompositeSearcher) Search(haystack []byte) (int, int, bool)

Search finds the first match in haystack. Returns (start, end, found).

func (*CompositeSearcher) SearchAt 

func (c *CompositeSearcher) SearchAt(haystack []byte, at int) (int, int, bool)

SearchAt finds the first match starting at or after position at. Returns (start, end, found).

type CompositeSequenceDFA 

type CompositeSequenceDFA struct {
	// contains filtered or unexported fields
}

CompositeSequenceDFA is a specialized DFA for composite character class patterns. It uses NFA subset construction to handle overlapping character classes correctly.

For pattern `\w+[0-9]+` with overlapping chars (digits are in both \w and [0-9]):

  • Uses byte classes to reduce transitions
  • Each DFA state represents a set of NFA positions (which parts could be active)
  • Handles overlap by tracking multiple possible parse positions simultaneously

Thread safety: NOT thread-safe. For concurrent usage, each goroutine needs its own instance.

func NewCompositeSequenceDFA 

func NewCompositeSequenceDFA(re *syntax.Regexp) *CompositeSequenceDFA

NewCompositeSequenceDFA creates a specialized DFA for composite patterns. Returns nil if the pattern is not suitable for this DFA.

func (*CompositeSequenceDFA) IsMatch 

func (d *CompositeSequenceDFA) IsMatch(haystack []byte) bool

IsMatch returns true if the haystack contains a match.

func (*CompositeSequenceDFA) Search 

func (d *CompositeSequenceDFA) Search(haystack []byte) (int, int, bool)

Search finds the first match in haystack. Returns (start, end, found).

func (*CompositeSequenceDFA) SearchAt 

func (d *CompositeSequenceDFA) SearchAt(haystack []byte, at int) (int, int, bool)

SearchAt finds the first match starting at or after position 'at'. Returns (start, end, found).

type FirstByteSet 

type FirstByteSet struct {
	// contains filtered or unexported fields
}

FirstByteSet represents the set of bytes that can start a match. Used for O(1) early rejection of non-matching inputs.

func ExtractFirstBytes 

func ExtractFirstBytes(re *syntax.Regexp) *FirstByteSet

ExtractFirstBytes extracts the set of possible first bytes from a pattern. Returns nil if the pattern is too complex or can match empty string.

This is used for O(1) early rejection of non-matching inputs in anchored patterns. For example, for ^(\d+|UUID|hex32):

  • Valid first bytes: 0-9, 'U', 'h'
  • Any other first byte → immediate rejection

func (*FirstByteSet) Contains 

func (f *FirstByteSet) Contains(b byte) bool

Contains returns true if b can be the first byte of a match.

func (*FirstByteSet) Count 

func (f *FirstByteSet) Count() int

Count returns the number of possible first bytes.

func (*FirstByteSet) IsComplete 

func (f *FirstByteSet) IsComplete() bool

IsComplete returns true if this set is exhaustive.

func (*FirstByteSet) IsUseful 

func (f *FirstByteSet) IsUseful() bool

IsUseful returns true if this prefilter can reject inputs. Returns false if:

  • All 256 bytes are valid (e.g., for .* patterns)
  • No bytes are valid (e.g., for ^ patterns that match empty at position 0)
  • Set is incomplete (pattern may match starting with unknown bytes)

type Look 

type Look uint8

Look represents a zero-width assertion type (look-around) 

const (
	// LookStartText matches the start of input (\A)
	LookStartText Look = iota

	// LookEndText matches the end of input (\z)
	LookEndText

	// LookStartLine matches the start of a line (^)
	// Matches at position 0 or after a newline
	LookStartLine

	// LookEndLine matches the end of a line ($)
	// Matches at end of input or before a newline
	LookEndLine

	// LookWordBoundary matches a word boundary (\b)
	// Matches where is_word_char(prev) != is_word_char(curr)
	// Word chars are ASCII: [a-zA-Z0-9_]
	LookWordBoundary

	// LookNoWordBoundary matches a non-word boundary (\B)
	// Matches where is_word_char(prev) == is_word_char(curr)
	LookNoWordBoundary
)

type Match 

type Match struct {
	Start int
	End   int
}

Match represents a successful regex match with start and end positions

type MatchWithCaptures 

type MatchWithCaptures struct {
	Start    int
	End      int
	Captures [][]int // Captures[i] = [start, end] for group i, or nil if not captured
}

MatchWithCaptures represents a match including capture group positions. Captures is a slice where Captures[i] is [start, end] for group i. Group 0 is the entire match.

type NFA 

type NFA struct {
	// contains filtered or unexported fields
}

NFA represents a compiled Thompson NFA. It is the result of compiling a regexp/syntax.Regexp pattern.

func Reverse 

func Reverse(forward *NFA) *NFA

Reverse builds a reverse NFA from the given forward NFA.

In a reverse NFA:

  • Start and match states are swapped
  • All transitions are reversed (A->B becomes B->A)
  • The automaton matches patterns backward from the end

This is used for reverse searching, which enables efficient matching of patterns with $ anchor by searching backward from the end of the haystack.

Algorithm (Two-Pass): 

Pass 1: Collect all reverse edges and allocate state IDs
Pass 2: Build actual states with correct transition targets

Note: Reverse NFA does NOT support capture groups. Captures require forward search to maintain correct positions.

Example: 

Forward NFA for "abc":
  start -> a -> b -> c -> match

Reverse NFA:
  start(from match) -> c -> b -> a -> match(from start)

func ReverseAnchored 

func ReverseAnchored(forward *NFA) *NFA

ReverseAnchored builds a reverse NFA that is anchored at start. This is used for patterns ending with $ anchor, where the reverse NFA should only match starting at position 0 of the reversed haystack.

This is equivalent to Reverse() followed by marking the result as anchored.

func (*NFA) ByteClasses 

func (n *NFA) ByteClasses() *ByteClasses

ByteClasses returns the byte equivalence classes for this NFA. Used by DFA to reduce transition table size from 256 to ~8-16 entries.

func (*NFA) CaptureCount 

func (n *NFA) CaptureCount() int

CaptureCount returns the number of capture groups in the NFA. Group 0 is the entire match, groups 1+ are explicit captures. For a pattern like "(a)(b)", this returns 3 (entire match + 2 groups).

func (*NFA) IsAlwaysAnchored 

func (n *NFA) IsAlwaysAnchored() bool

IsAlwaysAnchored returns true if anchored and unanchored starts are the same. This indicates the pattern is inherently anchored (has ^ prefix).

func (*NFA) IsAnchored 

func (n *NFA) IsAnchored() bool

IsAnchored returns true if the NFA requires anchored matching

func (*NFA) IsMatch 

func (n *NFA) IsMatch(id StateID) bool

IsMatch returns true if the given state is a match state

func (*NFA) IsUTF8 

func (n *NFA) IsUTF8() bool

IsUTF8 returns true if the NFA respects UTF-8 boundaries

func (*NFA) Iter 

func (n *NFA) Iter() *StateIter

Iter returns an iterator over all states in the NFA

func (*NFA) PatternCount 

func (n *NFA) PatternCount() int

PatternCount returns the number of patterns in the NFA

func (*NFA) Start deprecated 

func (n *NFA) Start() StateID

Start returns the starting state ID of the NFA

Deprecated: Use StartAnchored() or StartUnanchored() for explicit control

func (*NFA) StartAnchored 

func (n *NFA) StartAnchored() StateID

StartAnchored returns the start state for anchored searches

func (*NFA) StartUnanchored 

func (n *NFA) StartUnanchored() StateID

StartUnanchored returns the start state for unanchored searches

func (*NFA) State 

func (n *NFA) State(id StateID) *State

State returns the state with the given ID. Returns nil if the ID is invalid.

func (*NFA) States 

func (n *NFA) States() int

States returns the total number of states in the NFA

func (*NFA) String 

func (n *NFA) String() string

String returns a human-readable representation of the NFA

func (*NFA) SubexpNames 

func (n *NFA) SubexpNames() []string

SubexpNames returns the names of capture groups in the pattern. Index 0 is always "" (representing the entire match). Named groups return their names, unnamed groups return "".

Example: 

pattern: `(?P<year>\d+)-(\d+)-(?P<day>\d+)`
returns: ["", "year", "", "day"]

This matches stdlib regexp.Regexp.SubexpNames() behavior.

type PikeVM 

type PikeVM struct {
	// contains filtered or unexported fields
}

func NewPikeVM 

func NewPikeVM(nfa *NFA) *PikeVM

NewPikeVM creates a new PikeVM for executing the given NFA

func (*PikeVM) InitState 

func (p *PikeVM) InitState(state *PikeVMState)

InitState initializes this state for use with the given PikeVM. Must be called before using the state with *WithState methods.

func (*PikeVM) IsMatch 

func (p *PikeVM) IsMatch(haystack []byte) bool

IsMatch returns true if the pattern matches anywhere in the haystack. This is optimized for boolean-only matching - it returns as soon as any match is found without computing exact match positions.

This is significantly faster than Search() when you only need to know if a match exists, not where it is.

func (*PikeVM) NumStates 

func (p *PikeVM) NumStates() int

NumStates returns the number of NFA states (for state allocation).

func (*PikeVM) Search 

func (p *PikeVM) Search(haystack []byte) (int, int, bool)

Search finds the first match in the haystack. Returns (start, end, true) if a match is found, or (-1, -1, false) if not.

The search is unanchored by default (matches anywhere in haystack) unless the NFA was compiled with anchored mode.

This method uses internal state and is NOT thread-safe. For concurrent usage, use SearchWithState.

func (*PikeVM) SearchAll 

func (p *PikeVM) SearchAll(haystack []byte) []Match

SearchAll finds all non-overlapping matches in the haystack. Returns a slice of matches in order of occurrence.

func (*PikeVM) SearchAt 

func (p *PikeVM) SearchAt(haystack []byte, at int) (int, int, bool)

SearchAt finds the first match in the haystack starting from position 'at'. Returns (start, end, true) if a match is found, or (-1, -1, false) if not.

This method is used by FindAll* operations to correctly handle anchors like ^. Unlike Search, it takes the FULL haystack and a starting position, so assertions like ^ correctly check against the original input start, not a sliced position.

func (*PikeVM) SearchBetween 

func (p *PikeVM) SearchBetween(haystack []byte, startAt, maxEnd int) (int, int, bool)

SearchBetween finds the first match in the range [startAt, maxEnd] of haystack. This is an optimization for cases where we know the match ends at or before maxEnd (e.g., after DFA found the end position). It avoids scanning the full haystack.

Parameters:

  • haystack: the input byte slice
  • startAt: minimum position to start searching
  • maxEnd: maximum position where match can end (exclusive for search, inclusive for match)

Returns (start, end, found) where start >= startAt and end <= maxEnd.

Performance: O(maxEnd - startAt) instead of O(len(haystack) - startAt).

func (*PikeVM) SearchWithCaptures 

func (p *PikeVM) SearchWithCaptures(haystack []byte) *MatchWithCaptures

SearchWithCaptures finds the first match with capture group positions. Returns nil if no match is found.

func (*PikeVM) SearchWithCapturesAt 

func (p *PikeVM) SearchWithCapturesAt(haystack []byte, at int) *MatchWithCaptures

SearchWithCapturesAt finds the first match with capture group positions, starting from position 'at' in the haystack. Returns nil if no match is found.

This method is used by FindAll* operations to correctly handle anchors like ^. Unlike SearchWithCaptures, it takes the FULL haystack and a starting position.

func (*PikeVM) SearchWithCapturesInSpan 

func (p *PikeVM) SearchWithCapturesInSpan(haystack []byte, spanStart, spanEnd int) *MatchWithCaptures

SearchWithCapturesInSpan searches for a match anchored at spanStart, not exceeding spanEnd. The full haystack is preserved for lookbehind context (e.g., \b word boundary assertions at spanStart-1).

This implements Phase 2 of the DFA-first two-phase search: 

Phase 1: DFA/strategy finds match boundaries [spanStart, spanEnd]
Phase 2: PikeVM extracts captures within [spanStart, spanEnd]

The search is anchored: threads are seeded only at spanStart, not at every position. This reduces PikeVM work from O(remaining_haystack) to O(match_len) per match.

Preconditions:

  • 0 <= spanStart <= spanEnd <= len(haystack)
  • A match is known to exist in [spanStart, spanEnd] (from Phase 1)

Returns nil if no match is found (should not happen if Phase 1 is correct).

func (*PikeVM) SearchWithSlotTable 

func (p *PikeVM) SearchWithSlotTable(haystack []byte, mode SearchMode) (int, int, bool)

SearchWithSlotTable finds the first match using the SlotTable architecture. This is more memory-efficient than the legacy Search methods as it uses lightweight threads (16 bytes) with per-state capture storage.

Parameters:

  • haystack: input bytes to search
  • mode: determines how many capture slots to track (0/2/full)

Returns (start, end, found) for the first match.

This method uses internal state and is NOT thread-safe.

func (*PikeVM) SearchWithSlotTableAt 

func (p *PikeVM) SearchWithSlotTableAt(haystack []byte, at int, mode SearchMode) (int, int, bool)

SearchWithSlotTableAt finds the first match starting from position 'at'. Uses the SlotTable architecture for efficient capture tracking.

Parameters:

  • haystack: input bytes to search
  • at: starting position in haystack
  • mode: determines how many capture slots to track

Returns (start, end, found) for the first match.

func (*PikeVM) SearchWithSlotTableCaptures 

func (p *PikeVM) SearchWithSlotTableCaptures(haystack []byte) *MatchWithCaptures

SearchWithSlotTableCaptures finds the first match and returns captures. Uses zero-allocation SlotTable architecture (Rust approach).

func (*PikeVM) SearchWithSlotTableCapturesAt 

func (p *PikeVM) SearchWithSlotTableCapturesAt(haystack []byte, at int) *MatchWithCaptures

SearchWithSlotTableCapturesAt finds the first match with captures starting from 'at'. Uses dual SlotTable (curr/next) for zero-allocation capture tracking. Matches Rust's PikeVM Cache with curr/next ActiveStates (pikevm.rs:1878).

func (*PikeVM) SetLongest 

func (p *PikeVM) SetLongest(longest bool)

SetLongest enables or disables leftmost-longest (POSIX) matching semantics. By default, uses leftmost-first (Perl) semantics where first alternative wins. When longest=true, the longest match at the same start position wins. Note: This modifies internal state. For thread-safe usage, set Longest directly on PikeVMState.

func (*PikeVM) SetSkipAhead 

func (p *PikeVM) SetSkipAhead(sa SkipAhead)

SetSkipAhead sets the prefilter for skip-ahead optimization. When set, PikeVM uses it to skip positions where no match can start (when there are no active NFA threads). Safe for partial-coverage prefilters.

type PikeVMState 

type PikeVMState struct {
	// Thread queues for current and next generation (legacy, with COW captures)
	// Pre-allocated to avoid allocations during search
	Queue     []thread
	NextQueue []thread

	// Lightweight thread queues for SlotTable-based search (new architecture)
	// These use searchThread which is 16 bytes vs 40+ bytes for thread
	SearchQueue     []searchThread
	SearchNextQueue []searchThread

	// Sparse set for tracking visited states in current generation
	// This prevents processing the same state multiple times
	Visited *sparse.SparseSet

	// SlotTable / NextSlotTable: two slot tables swapped between generations.
	// Mirrors Rust's curr/next ActiveStates pattern (pikevm.rs:1878).
	// SlotTable = current generation, NextSlotTable = next generation.
	// After each byte transition: swap(SlotTable, NextSlotTable).
	SlotTable     *SlotTable
	NextSlotTable *SlotTable

	// Longest enables leftmost-longest (POSIX) matching semantics.
	// By default (false), uses leftmost-first (Perl) semantics where
	// the first alternative wins. When true, the longest match wins.
	Longest bool
	// contains filtered or unexported fields
}

PikeVMState holds mutable per-search state for PikeVM. This struct should be pooled (via sync.Pool) for concurrent usage. Each goroutine must use its own PikeVMState instance.

func NewPikeVMState 

func NewPikeVMState() *PikeVMState

NewPikeVMState creates a new mutable state for use with PikeVM. The state must be initialized by calling PikeVM.InitState before use. This should be pooled via sync.Pool for concurrent usage.

type SearchMode 

type SearchMode int

SearchMode determines how many capture slots to track during search. This enables dynamic slot sizing for optimal performance based on the type of search being performed.

Reference: rust-regex/regex-automata/src/nfa/thompson/pikevm.rs:1898-1921 

const (
	// SearchModeIsMatch tracks 0 slots - just returns boolean match result.
	// This is the fastest mode, used for IsMatch() calls.
	SearchModeIsMatch SearchMode = iota

	// SearchModeFind tracks 2 slots - only overall match start/end positions.
	// Used for Find() and FindIndices() when captures are not needed.
	SearchModeFind

	// SearchModeCaptures tracks all slots - full capture group positions.
	// Used for FindWithCaptures() and similar methods.
	SearchModeCaptures
)

func (SearchMode) SlotsNeeded 

func (m SearchMode) SlotsNeeded(totalSlots int) int

SlotsNeeded returns the number of slots required for this search mode. Parameters:

  • totalSlots: the total number of capture slots (CaptureCount * 2)

type SkipAhead 

type SkipAhead interface {
	Find(haystack []byte, start int) int
}

PikeVM implements the Pike VM algorithm for NFA execution. It simulates the NFA by maintaining a set of active states and exploring all possible paths through the automaton.

The Pike VM is slower than DFA-based approaches but handles all regex features including backreferences (future) and capturing groups.

Thread safety: PikeVM configuration (nfa) is immutable after creation. For thread-safe concurrent usage, use *WithState methods with external PikeVMState. The legacy methods without state use internal state and are NOT thread-safe. SkipAhead is a prefilter interface for PikeVM skip-ahead optimization. When NFA has no active threads, Find skips to the next candidate position instead of scanning byte-by-byte. This is the Rust approach (pikevm.rs:1293). Safe for both complete and partial-coverage prefilters.

type SlotTable 

type SlotTable struct {
	// contains filtered or unexported fields
}

SlotTable is a 2D table (flattened to 1D) storing capture slot values per NFA state.

This design follows the Rust regex crate's SlotTable architecture: - Each state has a row of slots (one slot per capture position: start/end for each group) - The table is pre-allocated for all states to enable O(1) random access - Dynamic slot sizing allows using 0 slots (IsMatch), 2 slots (Find), or full slots (Captures)

Memory layout: table[stateID * slotsPerState + slotIndex]

Reference: rust-regex/regex-automata/src/nfa/thompson/pikevm.rs:2044-2160

func NewSlotTable 

func NewSlotTable(numStates, slotsPerState int) *SlotTable

NewSlotTable creates a new SlotTable for an NFA with the given parameters.

Parameters:

  • numStates: total NFA states (determines table rows)
  • slotsPerState: total capture slots per state (CaptureCount * 2)

The table is pre-allocated to enable O(1) access. All slots are initialized to -1 (unset).

func (*SlotTable) ActiveSlots 

func (st *SlotTable) ActiveSlots() int

ActiveSlots returns the current number of active slots.

func (*SlotTable) AllAbsent 

func (st *SlotTable) AllAbsent() []int

AllAbsent returns a slice of slots where all values are guaranteed to be -1.

This is used for epsilon closure when computing transitions that should not have any capture slots set. The scratch space at the end of the table is used for this purpose.

Reference: rust-regex pikevm.rs:2156-2159

func (*SlotTable) Clone 

func (st *SlotTable) Clone() *SlotTable

Clone creates a deep copy of the SlotTable.

This is useful for creating independent copies for parallel searches.

func (*SlotTable) CopySlots 

func (st *SlotTable) CopySlots(dst, src StateID)

CopySlots copies active slots from src state to dst state.

This is used during epsilon closure to propagate capture positions from one state to another.

func (*SlotTable) ExtractCaptures 

func (st *SlotTable) ExtractCaptures(sid StateID, matchStart, matchEnd int) [][]int

ExtractCaptures extracts capture group positions from a state's slots.

Returns a slice of [start, end] pairs for each capture group. If a group was not captured, its entry is nil.

This is a convenience method for converting slot data to the result format.

func (*SlotTable) ForState 

func (st *SlotTable) ForState(sid StateID) []int

ForState returns a slice of slots for the given state ID.

The returned slice has length = activeSlots (not slotsPerState), allowing dynamic slot sizing. Modifying the returned slice modifies the table.

Panics if stateID is out of bounds.

func (*SlotTable) ForStateUnchecked 

func (st *SlotTable) ForStateUnchecked(sid StateID) []int

ForStateUnchecked returns slots for a state without bounds checking. This is a performance optimization for hot paths where bounds are known valid.

func (*SlotTable) GetSlot 

func (st *SlotTable) GetSlot(sid StateID, slotIndex int) int

GetSlot returns a slot value for a state.

Returns -1 if slot is unset or if slotIndex is out of bounds.

func (*SlotTable) MemoryUsage 

func (st *SlotTable) MemoryUsage() int

MemoryUsage returns the heap memory usage in bytes.

func (*SlotTable) Reset 

func (st *SlotTable) Reset()

Reset clears all slots to -1 (unset).

This is called at the start of each search to reset the table. Note: This is O(n) where n = numStates * slotsPerState. For large tables, consider using generation-based clearing instead.

func (*SlotTable) ResetState 

func (st *SlotTable) ResetState(sid StateID)

ResetState clears only the slots for a specific state.

More efficient than Reset() when only specific states need clearing.

func (*SlotTable) SetActiveSlots 

func (st *SlotTable) SetActiveSlots(n int)

SetActiveSlots sets the number of active slots to track during search.

This enables dynamic slot sizing:

  • 0: IsMatch mode (no capture tracking, fastest)
  • 2: Find mode (only track overall match start/end)
  • full (slotsPerState): Captures mode (track all groups)

If n > slotsPerState, it is clamped to slotsPerState.

func (*SlotTable) SetSlot 

func (st *SlotTable) SetSlot(sid StateID, slotIndex, value int)

SetSlot sets a specific slot value for a state.

Parameters:

  • sid: state ID
  • slotIndex: index within the state's slots (0 = group 0 start, 1 = group 0 end, etc.)
  • value: position value (-1 for unset)

Does nothing if slotIndex >= activeSlots (respects dynamic sizing).

func (*SlotTable) SlotsPerState 

func (st *SlotTable) SlotsPerState() int

SlotsPerState returns the total slots per state (stride).

type State 

type State struct {
	// contains filtered or unexported fields
}

State represents a single NFA state with its transitions. The state's kind determines which fields are valid.

func (*State) ByteRange 

func (s *State) ByteRange() (lo, hi byte, next StateID)

ByteRange returns the byte range for ByteRange states. Returns (0, 0, InvalidState) for non-ByteRange states.

func (*State) Capture 

func (s *State) Capture() (index uint32, isStart bool, next StateID)

Capture returns capture group info for Capture states. Returns (group index, isStart, next state). isStart is true for opening boundary '(' and false for closing ')'.

func (*State) Epsilon 

func (s *State) Epsilon() StateID

Epsilon returns the target state for Epsilon states. Returns InvalidState for non-Epsilon states.

func (*State) ID 

func (s *State) ID() StateID

ID returns the state's unique identifier

func (*State) IsMatch 

func (s *State) IsMatch() bool

IsMatch returns true if this is a match state

func (*State) IsQuantifierSplit 

func (s *State) IsQuantifierSplit() bool

IsQuantifierSplit returns true if this Split state is for a quantifier (*, +, ?, {n,m}). Quantifier splits don't affect thread priority (greedy behavior is handled by DFS order). Alternation splits increment priority for the right branch (leftmost-first semantics).

func (*State) Kind 

func (s *State) Kind() StateKind

Kind returns the state's type

func (*State) Look 

func (s *State) Look() (Look, StateID)

Look returns the look-around assertion type and target state for Look states. Returns (0, InvalidState) for non-Look states.

func (*State) RuneAny 

func (s *State) RuneAny() StateID

RuneAny returns the next state for RuneAny states. Returns InvalidState for non-RuneAny states.

func (*State) RuneAnyNotNL 

func (s *State) RuneAnyNotNL() StateID

RuneAnyNotNL returns the next state for RuneAnyNotNL states. Returns InvalidState for non-RuneAnyNotNL states.

func (*State) Split 

func (s *State) Split() (left, right StateID)

Split returns the two target states for Split states. Returns (InvalidState, InvalidState) for non-Split states.

func (*State) String 

func (s *State) String() string

String returns a human-readable representation of the state

func (*State) Transitions 

func (s *State) Transitions() []Transition

Transitions returns the list of transitions for Sparse states. Returns nil for non-Sparse states.

type StateID 

type StateID uint32

StateID uniquely identifies an NFA state. This is a 32-bit unsigned integer for compact representation. 

const (
	// InvalidState represents an invalid/uninitialized state ID
	InvalidState StateID = 0xFFFFFFFF

	// FailState represents a dead/failure state (no transitions)
	FailState StateID = 0xFFFFFFFE
)

Special state constants

type StateIter 

type StateIter struct {
	// contains filtered or unexported fields
}

StateIter is an iterator over NFA states

func (*StateIter) HasNext 

func (it *StateIter) HasNext() bool

HasNext returns true if there are more states to iterate

func (*StateIter) Next 

func (it *StateIter) Next() *State

Next returns the next state in the iteration. Returns nil when iteration is complete.

type StateKind 

type StateKind uint8

StateKind identifies the type of NFA state and determines which transitions are valid. 

const (
	// StateMatch represents a match state (accepting state)
	StateMatch StateKind = iota

	// StateByteRange represents a single byte or byte range transition [lo, hi]
	StateByteRange

	// StateSparse represents multiple byte transitions (character class)
	// e.g., [a-zA-Z0-9] would use this with a list of byte ranges
	StateSparse

	// StateSplit represents an epsilon transition to 2 states (alternation)
	// Used for alternation (a|b) and optional patterns (a?)
	StateSplit

	// StateEpsilon represents an epsilon transition to 1 state
	// Used for sequencing without consuming input
	StateEpsilon

	// StateCapture represents a capture group boundary (future feature)
	// Not implemented in MVP but reserved for future use
	StateCapture

	// StateFail represents a dead state (no valid transitions)
	StateFail

	// StateLook represents a zero-width assertion (look-around)
	// Examples: ^, $, \A, \z (word boundaries \b, \B in future)
	StateLook

	// StateRuneAny matches any Unicode codepoint (including newlines)
	// This is the (?s). (dot with DOTALL flag)
	StateRuneAny

	// StateRuneAnyNotNL matches any Unicode codepoint except newline (\n)
	// This is the default . (dot) behavior
	StateRuneAnyNotNL
)

func (StateKind) String 

func (k StateKind) String() string

String returns a human-readable representation of the StateKind

type Transition 

type Transition struct {
	Lo   byte    // inclusive lower bound
	Hi   byte    // inclusive upper bound
	Next StateID // target state
}

Transition represents a byte range and target state for sparse transitions. Used in character classes like [a-zA-Z0-9].

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.