The start-finder companion to lazy_dfa. Given a match end, it finds the leftmost start (the design guide §7.6 contract). It runs the inverted program — the forward program's edges transposed, its consuming bytes kept — as a cached DFA over the text scanned right-to-left from the end, recording an accept each time it reaches the original start (reverse-kLongest: the furthest-back accept is the start). It needs no priority ordering — its states are plain unordered (sorted) PC sets and its rule is longest — so it is simpler than the forward pass. Dynamic only. More...

#include <lazy_dfa.hpp>

Collaboration diagram for real::detail::reverse_dfa:

[legend]

Public Member Functions
constexpr	reverse_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) reverse DFA, transposing the program's edges as it goes.

bool	eligible () const
	Whether the program can be represented at all (no assertion, `klass_cp` or lookaround).

std::size_t	reverse_start (std::string_view text, std::size_t e, std::size_t resume)
	The leftmost start of the match ending at `e`, not before `resume`. Scans the text backward from `e` over the inverted program, keeping the furthest-back position that reaches the program start (reverse-`kLongest`). Precondition: a match ends at `e`; eligible programs only.

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::size_t	state_budget {4096}
	Cached states before a flush (the memory cap).

Private Member Functions
constexpr void	rev_closure (std::vector< std::int32_t > &set, std::vector< char > &seen) const
	Saturate `set` with its backward epsilon-closure, then sort it into a canonical key. Unordered by design: the reverse rule is longest, so priority carries no meaning here.

std::uint32_t	step (std::uint32_t state, std::uint8_t byte)
	Transition `state` backward over `byte`, computing and caching the edge on first use.

bool	consumes (std::int32_t pc, std::uint8_t byte) const
	Whether the instruction at `pc` is a consuming edge that accepts `byte`.

constexpr std::uint32_t	intern (const std::vector< std::int32_t > &pcs)
	Intern a sorted pc-set into a state id (cached), recording whether it reaches the program start.

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)
	Scan `code` for an op the transposed program cannot represent.

Private Attributes
std::span< const instr >	code_
	The byte program, owned by the caller.

std::span< const char_class >	classes_
	Its byte classes, likewise borrowed.

lazy_byte_alphabet	alpha_
	Byte-to-class map; its count is the row stride.

bool	eligible_ {false}
	compute_eligibility's verdict, fixed at construction.

std::int32_t	match_pc_ {-1}
	The forward `match` pc — this pass's start; -1 when absent.

std::uint32_t	start_state_ {0}
	Id of match_pc_'s backward closure, re-interned by each flush.

std::size_t	budget_ {state_budget}
	Cached states tolerated before a flush.

std::size_t	flushes_ {0}
	bumped by flush(); step()'s stale-state guard against a mid-call reset.

std::vector< std::int32_t >	rev_eps_pool_
	transposed epsilon edges, CSR-packed.

std::vector< std::uint32_t >	rev_eps_at_
	CSR offsets into rev_eps_pool_, size code+2.

std::vector< std::int32_t >	rev_consume_pool_
	transposed consuming edges, CSR-packed.

std::vector< std::uint32_t >	rev_consume_at_
	CSR offsets into rev_consume_pool_.

std::vector< std::int32_t >	stack_
	rev_closure's work stack, hoisted for the same reason.

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

std::vector< std::uint32_t >	trans_
	flat [state*stride + class] -> next.

std::vector< char >	state_has_start_
	state -> reaches the program start (an accept).

pc_set_cache	cache_
	pc-set -> state id, the memo behind intern.

Detailed Description

The start-finder companion to lazy_dfa. Given a match end, it finds the leftmost start (the design guide §7.6 contract). It runs the inverted program — the forward program's edges transposed, its consuming bytes kept — as a cached DFA over the text scanned right-to-left from the end, recording an accept each time it reaches the original start (reverse-kLongest: the furthest-back accept is the start). It needs no priority ordering — its states are plain unordered (sorted) PC sets and its rule is longest — so it is simpler than the forward pass. Dynamic only.

Constructor & Destructor Documentation

◆ reverse_dfa()

constexpr real::detail::reverse_dfa::reverse_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) reverse DFA, transposing the program's edges as it goes.

Parameters

[in]	code	The program's instruction stream (must outlive this object — held as a span).
[in]	classes	The program's interned byte classes (likewise held as a span).
[in]	budget	Cached states before a flush; defaults to state_budget.
[in]	shared_alpha	A precomputed alphabet the caller shares per regex, or null to compute it here.

Member Function Documentation

◆ compute_eligibility()

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

inlinestaticconstexprprivate

Scan code for an op the transposed program cannot represent.

Parameters

[in] code The program's instruction stream.

Returns: True when every op is representable.

◆ consumes()

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

inlineprivate

Whether the instruction at pc is a consuming edge that accepts byte.

Parameters

[in]	pc	Program counter to test.
[in]	byte	The byte offered to it.

Returns: True for a byte/klass op accepting it; false for any non-consuming op.

◆ eligible()

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

inline

Whether the program can be represented at all (no assertion, klass_cp or lookaround).

Returns: False when the caller must find the start another way.

◆ intern()

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

inlineconstexprprivate

Intern a sorted pc-set into a state id (cached), recording whether it reaches the program start.

Parameters

[in] pcs The sorted pc-set.

Returns: Its state id, existing or freshly built; dead_state for an empty set.

◆ rev_closure()

constexpr void real::detail::reverse_dfa::rev_closure	(	std::vector< std::int32_t > &	set,
		std::vector< char > &	seen
	)		const

inlineconstexprprivate

Saturate set with its backward epsilon-closure, then sort it into a canonical key. Unordered by design: the reverse rule is longest, so priority carries no meaning here.

Parameters

[in,out]	set	The pc-set to close over, in place.
[in,out]	seen	Per-pc visited marks, sized to the program.

◆ reverse_start()

std::size_t real::detail::reverse_dfa::reverse_start	(	std::string_view	text,
		std::size_t	e,
		std::size_t	resume
	)

inline

The leftmost start of the match ending at e, not before resume. Scans the text backward from e over the inverted program, keeping the furthest-back position that reaches the program start (reverse-kLongest). Precondition: a match ends at e; eligible programs only.

Parameters

[in]	text	Subject.
[in]	e	The known match end.
[in]	resume	Lower bound the backward scan will not cross.

Returns: The leftmost start at or after resume, or real::npos when none was reached.

◆ step()

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

inlineprivate

Transition state backward over byte, computing and caching the edge on first use.

Parameters

[in]	state	The current state id.
[in]	byte	The byte consumed, read right-to-left.

Returns: The predecessor state, or dead_state when nothing reaches back through byte.

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

include/real/automata/lazy_dfa.hpp

Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ reverse_dfa()

Member Function Documentation

◆ compute_eligibility()

◆ consumes()

◆ eligible()

◆ intern()

◆ rev_closure()

◆ reverse_start()

◆ step()