A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass). More...

#include <lazy_dfa.hpp>

Collaboration diagram for real::detail::lazy_dfa:

Classes
struct	counters
	Cache-behaviour counters, for the policy tests and later tuning. More...

Public Member Functions
constexpr	lazy_dfa (std::span< const instr > code, std::span< const char_class > classes, std::size_t budget=state_budget, const lazy_byte_alphabet *shared_alpha=nullptr)
	Builds the (initially empty) lazy DFA over a Pike program.

bool	eligible () const

std::uint16_t	num_classes () const

std::uint32_t	start_state () const

void	begin_scan ()
	Begin a search: clear the per-scan flush counter and the thrash flag. (No cache flush — the states carry over between searches on the same text, which is where the cache pays.)

bool	thrashing () const

const counters &	stats () const

std::size_t	forward_end (std::string_view text)
	The end offset of the leftmost-first match in `text` (`kFirstMatch`), or real::npos.

bool	is_match (std::uint32_t state) const
	Whether `state` accepts here (its ordered set contains a `match` PC).

std::uint32_t	step (std::uint32_t state, std::uint8_t byte)
	Transition `state` on `byte` to the next DFA state, computing and caching it on first use. Returns dead_state when no thread survives the byte.

Static Public Attributes
static constexpr std::uint32_t	dead_state {0}
	The empty state: every transition from it stays here.

static constexpr std::uint32_t	no_transition {0xFFFFFFFFU}
	A not-yet-computed cached transition.

static constexpr std::uint32_t	no_match_idx {0xFFFFFFFFU}
	A state whose ordered set holds no accept.

static constexpr std::size_t	state_budget {4096}
	Cached states before a flush (the memory cap).

static constexpr std::size_t	thrash_flushes {2}
	Flushes within one scan that trip thrashing.

Private Member Functions
std::uint32_t	step_seeded (std::uint32_t state, std::uint8_t byte)
	Like step, but re-seeds: the unanchored-search variant appends pc 0's closure at the lowest priority, so a fresh thread starts at every position until a match is found. Cached in its own transition row (the pre-match state family).

std::uint32_t	cut (std::uint32_t state, std::uint32_t m)
	The priority-cut at an accept: intern the prefix of `state's` ordered pc-set before index `m` (dropping the accept and every lower-priority thread). Returns dead_state if empty.

std::uint32_t	cut_cached (std::uint32_t state)
	The priority-cut of `state` at its own accept, memoized. `cut` is O(state size) — it rebuilds and re-interns the prefix — and a Unicode `klass_cp` byte-program makes states thousands of PCs wide, so recomputing it once per match (per find_iter step) dominated. Cached per state, it is computed once and then O(1). The state's accept index is fixed, so the cut is deterministic.

bool	consumes (std::int32_t pc, std::uint8_t byte) const

constexpr void	close_into (std::int32_t pc, std::vector< std::int32_t > &out, std::vector< char > &seen) const
	Append the ordered epsilon-closure of `pc` to `out` (split priority; save/jump crossed), collecting the consuming and `match` PCs. Uses `seen` to dedup within this closure.

constexpr std::uint32_t	intern (const std::vector< std::int32_t > &pcs)
	Intern an ordered pc-set into a state id (cached). Flushes the cache when the budget is hit.

constexpr std::uint32_t	intern_fresh (const std::vector< std::int32_t > &pcs)

constexpr void	flush ()
	Empty the cache back to the dead + start states (the eviction: bounded memory).

Static Private Member Functions
static constexpr bool	compute_eligibility (std::span< const instr > code)

static std::int32_t	consumed_width (std::int32_t)

Private Attributes
std::span< const instr >	code_

std::span< const char_class >	classes_

lazy_byte_alphabet	alpha_

bool	eligible_ {false}

std::uint32_t	start_state_ {0}

std::vector< std::vector< std::int32_t > >	state_pcs_
	state id -> ordered pc-set.

std::vector< std::uint32_t >	trans_
	flat [state*stride + class] -> next, unseeded (post-match); stride = alpha_.count.

std::vector< std::uint32_t >	trans_seeded_
	flat [state*stride + class] -> next, re-seeding (pre-match).

std::vector< std::uint32_t >	state_match_idx_
	state id -> index of its first accept, or no_match_idx.

std::vector< std::uint32_t >	state_cut_
	state id -> memoized priority-cut result (no_transition = not yet computed).

pc_set_cache	cache_

std::size_t	budget_ {state_budget}

counters	stats_ {}

bool	thrashing_ {false}

Detailed Description

A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass).

A DFA state is the ordered epsilon-closure of a set of program counters (the Pike thread list's PCs, in split priority). step transitions on a byte by consuming it from each PC and re-closing, then interns the resulting ordered set into a cached state — the subset construction, memoized on demand.

The cache is bounded: once it reaches state_budget states it is flushed and rebuilt (states are cheap to recompute; a bounded cache keeps memory flat). state_budget flushes crossed within one scan (see begin_scan) trips thrashing — the signal an eventual caller uses to abandon the DFA and finish that one search on the Pike VM, per-scan and linear, never re-attempting per position.

A program with an op no forward DFA can represent — a position assertion (\b, ^, $), a klass_cp, or a lookaround — is ineligible; this only builds the machinery, it does not decide policy.

Definition at line 489 of file lazy_dfa.hpp.

Constructor & Destructor Documentation

◆ lazy_dfa()

constexpr real::detail::lazy_dfa::lazy_dfa	(	std::span< const instr >	code,
		std::span< const char_class >	classes,
		std::size_t	budget = `state_budget`,
		const lazy_byte_alphabet *	shared_alpha = `nullptr`
	)

inlineexplicitconstexpr

Builds the (initially empty) lazy DFA over a Pike program.

Parameters

[in]	code	The program's instruction stream (must outlive this object — held as a span).
[in]	classes	The program's interned character classes (likewise held as a span).
[in]	budget	Cached states before a flush; defaults to state_budget. A smaller value is a test hook to exercise eviction and thrash without a state-exploding pattern.
[in]	shared_alpha	A precomputed alphabet the caller shares per regex, or null to compute it here. Recomputing is O(256 x classes) and a Unicode byte-program has thousands, so the router passes the shared one rather than paying it on every scan.

Definition at line 518 of file lazy_dfa.hpp.

Member Function Documentation

◆ begin_scan()

void real::detail::lazy_dfa::begin_scan ( )

inline

Begin a search: clear the per-scan flush counter and the thrash flag. (No cache flush — the states carry over between searches on the same text, which is where the cache pays.)

Definition at line 546 of file lazy_dfa.hpp.

◆ close_into()

constexpr void real::detail::lazy_dfa::close_into	(	std::int32_t	pc,
		std::vector< std::int32_t > &	out,
		std::vector< char > &	seen
	)		const

inlineconstexprprivate

Append the ordered epsilon-closure of pc to out (split priority; save/jump crossed), collecting the consuming and match PCs. Uses seen to dedup within this closure.

Definition at line 738 of file lazy_dfa.hpp.

◆ compute_eligibility()

static constexpr bool real::detail::lazy_dfa::compute_eligibility ( std::span< const instr > code )

inlinestaticconstexprprivate

Definition at line 707 of file lazy_dfa.hpp.

◆ consumed_width()

static std::int32_t real::detail::lazy_dfa::consumed_width ( std::int32_t )

inlinestaticprivate

Definition at line 731 of file lazy_dfa.hpp.

◆ consumes()

bool real::detail::lazy_dfa::consumes	(	std::int32_t	pc,
		std::uint8_t	byte
	)		const

inlineprivate

Definition at line 718 of file lazy_dfa.hpp.

◆ cut()

std::uint32_t real::detail::lazy_dfa::cut	(	std::uint32_t	state,
		std::uint32_t	m
	)

inlineprivate

The priority-cut at an accept: intern the prefix of state's ordered pc-set before index m (dropping the accept and every lower-priority thread). Returns dead_state if empty.

Definition at line 675 of file lazy_dfa.hpp.

◆ cut_cached()

std::uint32_t real::detail::lazy_dfa::cut_cached ( std::uint32_t state )

inlineprivate

The priority-cut of state at its own accept, memoized. cut is O(state size) — it rebuilds and re-interns the prefix — and a Unicode klass_cp byte-program makes states thousands of PCs wide, so recomputing it once per match (per find_iter step) dominated. Cached per state, it is computed once and then O(1). The state's accept index is fixed, so the cut is deterministic.

Definition at line 693 of file lazy_dfa.hpp.

◆ eligible()

bool real::detail::lazy_dfa::eligible ( ) const

inline

Definition at line 529 of file lazy_dfa.hpp.

◆ flush()

constexpr void real::detail::lazy_dfa::flush ( )

inlineconstexprprivate

Empty the cache back to the dead + start states (the eviction: bounded memory).

Definition at line 813 of file lazy_dfa.hpp.

◆ forward_end()

std::size_t real::detail::lazy_dfa::forward_end ( std::string_view text )

inline

The end offset of the leftmost-first match in text (kFirstMatch), or real::npos.

The forward pass the contract in the design guide (§7.6) specifies: an unanchored priority-ordered closure that seeds a fresh thread at every position (at the lowest priority) until a match is found, then reports the end of the highest-priority thread that reaches match — a lower-priority accept is suppressed while a higher one lives. It is a single left-to-right pass over the ordered PC-sets, so it is linear per search regardless of how the state space would explode under memoization. Eligible programs only (an ineligible one returns real::npos; the caller keeps the Pike VM). No captures: this reports the end; the windowed Pike pass fills the span and applies the empty-match rule.

Definition at line 573 of file lazy_dfa.hpp.

◆ intern()

constexpr std::uint32_t real::detail::lazy_dfa::intern ( const std::vector< std::int32_t > & pcs )

inlineconstexprprivate

Intern an ordered pc-set into a state id (cached). Flushes the cache when the budget is hit.

Definition at line 777 of file lazy_dfa.hpp.

◆ intern_fresh()

constexpr std::uint32_t real::detail::lazy_dfa::intern_fresh ( const std::vector< std::int32_t > & pcs )

inlineconstexprprivate

Definition at line 793 of file lazy_dfa.hpp.

◆ is_match()

bool real::detail::lazy_dfa::is_match ( std::uint32_t state ) const

inline

Whether state accepts here (its ordered set contains a match PC).

Definition at line 605 of file lazy_dfa.hpp.

◆ num_classes()

std::uint16_t real::detail::lazy_dfa::num_classes ( ) const

inline

Definition at line 534 of file lazy_dfa.hpp.

◆ start_state()

std::uint32_t real::detail::lazy_dfa::start_state ( ) const

inline

Definition at line 539 of file lazy_dfa.hpp.

◆ stats()

const counters & real::detail::lazy_dfa::stats ( ) const

inline

Definition at line 557 of file lazy_dfa.hpp.

◆ step()

std::uint32_t real::detail::lazy_dfa::step	(	std::uint32_t	state,
		std::uint8_t	byte
	)

inline

Transition state on byte to the next DFA state, computing and caching it on first use. Returns dead_state when no thread survives the byte.

Definition at line 614 of file lazy_dfa.hpp.

◆ step_seeded()

std::uint32_t real::detail::lazy_dfa::step_seeded	(	std::uint32_t	state,
		std::uint8_t	byte
	)

inlineprivate

Like step, but re-seeds: the unanchored-search variant appends pc 0's closure at the lowest priority, so a fresh thread starts at every position until a match is found. Cached in its own transition row (the pre-match state family).

Definition at line 646 of file lazy_dfa.hpp.

◆ thrashing()

bool real::detail::lazy_dfa::thrashing ( ) const

inline

Definition at line 552 of file lazy_dfa.hpp.

Member Data Documentation

◆ alpha_

lazy_byte_alphabet real::detail::lazy_dfa::alpha_

private

Definition at line 843 of file lazy_dfa.hpp.

◆ budget_

std::size_t real::detail::lazy_dfa::budget_ {state_budget}

private

Definition at line 854 of file lazy_dfa.hpp.

◆ cache_

pc_set_cache real::detail::lazy_dfa::cache_

private

Definition at line 852 of file lazy_dfa.hpp.

◆ classes_

std::span<const char_class> real::detail::lazy_dfa::classes_

private

Definition at line 842 of file lazy_dfa.hpp.

◆ code_

std::span<const instr> real::detail::lazy_dfa::code_

private

Definition at line 841 of file lazy_dfa.hpp.

◆ dead_state

constexpr std::uint32_t real::detail::lazy_dfa::dead_state {0}

staticconstexpr

The empty state: every transition from it stays here.

Definition at line 493 of file lazy_dfa.hpp.

◆ eligible_

bool real::detail::lazy_dfa::eligible_ {false}

private

Definition at line 844 of file lazy_dfa.hpp.

◆ no_match_idx

constexpr std::uint32_t real::detail::lazy_dfa::no_match_idx {0xFFFFFFFFU}

staticconstexpr

A state whose ordered set holds no accept.

Definition at line 495 of file lazy_dfa.hpp.

◆ no_transition

constexpr std::uint32_t real::detail::lazy_dfa::no_transition {0xFFFFFFFFU}

staticconstexpr

A not-yet-computed cached transition.

Definition at line 494 of file lazy_dfa.hpp.

◆ start_state_

std::uint32_t real::detail::lazy_dfa::start_state_ {0}

private

Definition at line 845 of file lazy_dfa.hpp.

◆ state_budget

constexpr std::size_t real::detail::lazy_dfa::state_budget {4096}

staticconstexpr

Cached states before a flush (the memory cap).

Definition at line 496 of file lazy_dfa.hpp.

◆ state_cut_

std::vector<std::uint32_t> real::detail::lazy_dfa::state_cut_

private

state id -> memoized priority-cut result (no_transition = not yet computed).

Definition at line 851 of file lazy_dfa.hpp.

◆ state_match_idx_

std::vector<std::uint32_t> real::detail::lazy_dfa::state_match_idx_

private

state id -> index of its first accept, or no_match_idx.

Definition at line 850 of file lazy_dfa.hpp.

◆ state_pcs_

std::vector<std::vector<std::int32_t> > real::detail::lazy_dfa::state_pcs_

private

state id -> ordered pc-set.

Definition at line 847 of file lazy_dfa.hpp.

◆ stats_

counters real::detail::lazy_dfa::stats_ {}

private

Definition at line 855 of file lazy_dfa.hpp.

◆ thrash_flushes

constexpr std::size_t real::detail::lazy_dfa::thrash_flushes {2}

staticconstexpr

Flushes within one scan that trip thrashing.

Definition at line 497 of file lazy_dfa.hpp.

◆ thrashing_

bool real::detail::lazy_dfa::thrashing_ {false}

private

Definition at line 856 of file lazy_dfa.hpp.

◆ trans_

std::vector<std::uint32_t> real::detail::lazy_dfa::trans_

private

flat [state*stride + class] -> next, unseeded (post-match); stride = alpha_.count.

Definition at line 848 of file lazy_dfa.hpp.

◆ trans_seeded_

std::vector<std::uint32_t> real::detail::lazy_dfa::trans_seeded_

private

flat [state*stride + class] -> next, re-seeding (pre-match).

Definition at line 849 of file lazy_dfa.hpp.

The documentation for this class was generated from the following file:

include/real/automata/lazy_dfa.hpp

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ lazy_dfa()

Member Function Documentation

◆ begin_scan()

◆ close_into()

◆ compute_eligibility()

◆ consumed_width()

◆ consumes()

◆ cut()

◆ cut_cached()

◆ eligible()

◆ flush()

◆ forward_end()

◆ intern()

◆ intern_fresh()

◆ is_match()

◆ num_classes()

◆ start_state()

◆ stats()

◆ step()

◆ step_seeded()

◆ thrashing()

Member Data Documentation

◆ alpha_

◆ budget_

◆ cache_

◆ classes_

◆ code_

◆ dead_state

◆ eligible_

◆ no_match_idx

◆ no_transition

◆ start_state_

◆ state_budget

◆ state_cut_

◆ state_match_idx_

◆ state_pcs_

◆ stats_

◆ thrash_flushes

◆ thrashing_

◆ trans_

◆ trans_seeded_