onepass

Documentation

Overview

Package onepass implements a one-pass DFA for regex patterns that have no ambiguity in their matching paths.

A regex is "one-pass" when at each input byte during an anchored match, there is at most one possible path through the automaton. This property enables efficient capture group extraction without backtracking.

Performance: OnePass DFA provides ~10-20x speedup over PikeVM for patterns with capture groups, approaching the speed of non-capturing DFA.

Limitations:

• Only supports anchored searches (no unanchored prefix)
• Maximum 16 capture groups including group 0 (32 slots fit in uint32 mask)
• Not all patterns are one-pass (e.g., `a*a`, `(.*)x` are NOT one-pass)

Example one-pass patterns:

• `(\d+)-(\d+)` - Digit groups separated by dash
• `([a-z]+)\s+([a-z]+)` - Word pairs
• `x*yx*` - Unambiguous repetition
• `[^ ]* .*` - Non-space followed by anything

Example non-one-pass patterns:

• `a*a` - Ambiguous: extend a* or final a?
• `(.*) (.*)` - Where does first group end?
• `(ab|ac)` - Same first byte in alternation

Index

• Variables
• func IsOnePass(n *nfa.NFA) bool
• type Builder
• type Cache
  • func NewCache(numCaptures int) *Cache
  • func (c *Cache) Reset()
  • func (c *Cache) Slots() []int
• type DFA
  • func Build(n *nfa.NFA) (*DFA, error)
  • func (d *DFA) IsMatch(input []byte) bool
  • func (d *DFA) NumCaptures() int
  • func (d *DFA) Search(input []byte, cache *Cache) []int
  • func (d *DFA) SearchAt(input []byte, start int, cache *Cache) []int
• type StateID
• type Transition
  • func NewTransition(next StateID, matchWins bool, slots uint32) Transition
  • func (t Transition) IsDead() bool
  • func (t Transition) IsMatchWins() bool
  • func (t Transition) LookAround() uint16
  • func (t Transition) NextState() StateID
  • func (t Transition) SlotMask() uint32
  • func (t Transition) UpdateSlots(slots []int, pos int)
  • func (t Transition) WithLookAround(look uint16) Transition
  • func (t Transition) WithSlotMask(slots uint32) Transition

Variables

var (
	// ErrNotOnePass is returned when a pattern is not one-pass.
	ErrNotOnePass = errors.New("pattern is not one-pass")

	// ErrTooManyCaptures is returned when a pattern has more than 16 capture groups
	// (including group 0), i.e., more than 15 explicit capture groups.
	ErrTooManyCaptures = errors.New("too many capture groups for onepass (max 16 including group 0)")
)

Functions

func IsOnePass

func IsOnePass(n *nfa.NFA) bool

IsOnePass quickly checks if an NFA might be one-pass (heuristic). This is a fast pre-check before attempting full DFA construction.

Returns false for patterns that are definitely not one-pass:

• Patterns with unanchored prefix (one-pass requires anchored search)
• Patterns with too many capture groups

Returns true for patterns that might be one-pass (need full check).

Types

type Builder

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

Builder constructs a one-pass DFA from an NFA.

type Cache

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

Cache holds per-search state for capture groups.

This is allocated once and reused across searches to avoid allocations.

func NewCache

func NewCache(numCaptures int) *Cache

NewCache creates a new cache for the given number of capture groups. numCaptures includes group 0 (entire match).

func (*Cache) Reset

func (c *Cache) Reset()

Reset clears the cache for a new search.

func (*Cache) Slots

func (c *Cache) Slots() []int

Slots returns the capture group slots. Returns [start0, end0, start1, end1, ...] where group i is at [i*2, i*2+1].

type DFA

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

DFA represents a one-pass deterministic finite automaton.

The DFA can only be used for anchored searches but provides ~10-20x speedup over PikeVM for patterns with capture groups.

The transition table is organized as:

table[stateID * stride + byteClass] → Transition

where stride is the next power of 2 >= alphabetLen.

func Build

func Build(n *nfa.NFA) (*DFA, error)

Build attempts to build a one-pass DFA from the given NFA. Returns (nil, ErrNotOnePass) if the pattern is not one-pass. Returns (nil, ErrTooManyCaptures) if more than 16 capture groups (including group 0).

func (*DFA) IsMatch

func (d *DFA) IsMatch(input []byte) bool

IsMatch returns true if the input matches (anchored). Faster than Search when captures aren't needed.

func (*DFA) NumCaptures

func (d *DFA) NumCaptures() int

NumCaptures returns the number of capture groups tracked by this DFA. This includes group 0 (entire match) plus explicit capture groups.

func (*DFA) Search

func (d *DFA) Search(input []byte, cache *Cache) []int

Search performs an anchored search starting at input[0]. Returns the capture group slots or nil if no match.

The returned slice contains [start0, end0, start1, end1, ...] where group i is at indices [i*2, i*2+1]. Group 0 is the entire match.

Example:

dfa, _ := Build(nfa)
cache := NewCache(dfa.NumCaptures())
slots := dfa.Search(input, cache)
if slots != nil {
    entireMatch := input[slots[0]:slots[1]]
    group1 := input[slots[2]:slots[3]]
}

func (*DFA) SearchAt

func (d *DFA) SearchAt(input []byte, start int, cache *Cache) []int

SearchAt performs an anchored search starting at input[start:]. This is a convenience wrapper around Search.

type StateID

type StateID uint32

StateID is a DFA state identifier (21 bits max = 2M states).

const (

	// DeadState represents a dead/fail state (no valid transition)
	DeadState StateID = 0

	// MaxStateID is the maximum valid state ID (21 bits)
	MaxStateID StateID = (1 << stateIDBits) - 1
)

type Transition

type Transition uint64

Transition encodes DFA state transition + slot updates in 64 bits.

Bit layout (from high to low):

• Bits 43-63 (21 bits): Next StateID (max 2M states)
• Bit 42 (1 bit): MatchWins flag for leftmost-first semantics
• Bits 32-41 (10 bits): Look-around assertions (word boundary, line boundary, etc.)
• Bits 0-31 (32 bits): Slot update mask (one bit per slot)

This encoding enables single uint64 lookup per transition with all metadata included.

func NewTransition

func NewTransition(next StateID, matchWins bool, slots uint32) Transition

NewTransition creates a new transition with the given next state, match-wins flag, and slot mask.

func (Transition) IsDead

func (t Transition) IsDead() bool

IsDead returns true if this transition leads to a dead state.

func (Transition) IsMatchWins

func (t Transition) IsMatchWins() bool

IsMatchWins returns true if the match-wins flag is set. This flag indicates that if the current state is a match state, the match should be accepted immediately (leftmost-first semantics).

func (Transition) LookAround

func (t Transition) LookAround() uint16

LookAround returns the look-around assertion flags.

func (Transition) NextState

func (t Transition) NextState() StateID

NextState extracts the next state ID from the transition.

func (Transition) SlotMask

func (t Transition) SlotMask() uint32

SlotMask returns the 32-bit slot update mask. Each bit indicates whether to save the current position to that slot.

func (Transition) UpdateSlots

func (t Transition) UpdateSlots(slots []int, pos int)

UpdateSlots applies the slot updates to the given slots array. For each bit set in the slot mask, slots[i] is set to pos.

func (Transition) WithLookAround

func (t Transition) WithLookAround(look uint16) Transition

WithLookAround creates a new transition with the given look-around flags.

func (Transition) WithSlotMask

func (t Transition) WithSlotMask(slots uint32) Transition

WithSlotMask creates a new transition with the given slot mask, preserving other fields.