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)

bool	eligible () const

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}

static constexpr std::uint32_t	no_transition {0xFFFFFFFFU}

static constexpr std::size_t	state_budget {4096}

Private Member Functions
constexpr void	rev_closure (std::vector< std::int32_t > &set, std::vector< char > &seen) const

std::uint32_t	step (std::uint32_t state, std::uint8_t byte)

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

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

constexpr void	flush ()

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

Private Attributes
std::span< const instr >	code_

std::span< const char_class >	classes_

lazy_byte_alphabet	alpha_

bool	eligible_ {false}

std::int32_t	match_pc_ {-1}

std::uint32_t	start_state_ {0}

std::size_t	budget_ {state_budget}

std::vector< std::vector< std::int32_t > >	rev_eps_
	transposed epsilon edges.

std::vector< std::vector< std::int32_t > >	rev_consume_
	transposed consuming edges (the pred consuming pcs).

std::vector< std::vector< std::int32_t > >	state_pcs_

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_

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.

Definition at line 867 of file lazy_dfa.hpp.

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

Definition at line 875 of file lazy_dfa.hpp.

Member Function Documentation

◆ compute_eligibility()

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

inlinestaticconstexprprivate

Definition at line 999 of file lazy_dfa.hpp.

◆ consumes()

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

inlineprivate

Definition at line 989 of file lazy_dfa.hpp.

◆ eligible()

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

inline

Definition at line 914 of file lazy_dfa.hpp.

◆ flush()

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

inlineconstexprprivate

Definition at line 1037 of file lazy_dfa.hpp.

◆ intern()

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

inlineconstexprprivate

Definition at line 1010 of file lazy_dfa.hpp.

◆ rev_closure()

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

inlineconstexprprivate

Definition at line 946 of file lazy_dfa.hpp.

◆ 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.

Definition at line 924 of file lazy_dfa.hpp.

◆ step()

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

inlineprivate

Definition at line 964 of file lazy_dfa.hpp.

Member Data Documentation

◆ alpha_

lazy_byte_alphabet real::detail::reverse_dfa::alpha_

private

Definition at line 1058 of file lazy_dfa.hpp.

◆ budget_

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

private

Definition at line 1062 of file lazy_dfa.hpp.

◆ cache_

pc_set_cache real::detail::reverse_dfa::cache_

private

Definition at line 1068 of file lazy_dfa.hpp.

◆ classes_

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

private

Definition at line 1057 of file lazy_dfa.hpp.

◆ code_

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

private

Definition at line 1056 of file lazy_dfa.hpp.

◆ dead_state

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

staticconstexpr

Definition at line 871 of file lazy_dfa.hpp.

◆ eligible_

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

private

Definition at line 1059 of file lazy_dfa.hpp.

◆ match_pc_

std::int32_t real::detail::reverse_dfa::match_pc_ {-1}

private

Definition at line 1060 of file lazy_dfa.hpp.

◆ no_transition

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

staticconstexpr

Definition at line 872 of file lazy_dfa.hpp.

◆ rev_consume_

std::vector<std::vector<std::int32_t> > real::detail::reverse_dfa::rev_consume_

private

transposed consuming edges (the pred consuming pcs).

Definition at line 1064 of file lazy_dfa.hpp.

◆ rev_eps_

std::vector<std::vector<std::int32_t> > real::detail::reverse_dfa::rev_eps_

private

transposed epsilon edges.

Definition at line 1063 of file lazy_dfa.hpp.

◆ start_state_

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

private

Definition at line 1061 of file lazy_dfa.hpp.

◆ state_budget

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

staticconstexpr

Definition at line 873 of file lazy_dfa.hpp.

◆ state_has_start_

std::vector<char> real::detail::reverse_dfa::state_has_start_

private

state -> reaches the program start (an accept).

Definition at line 1067 of file lazy_dfa.hpp.

◆ state_pcs_

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

private

Definition at line 1065 of file lazy_dfa.hpp.

◆ trans_

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

private

flat [state*stride + class] -> next.

Definition at line 1066 of file lazy_dfa.hpp.

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()

◆ flush()

◆ intern()

◆ rev_closure()

◆ reverse_start()

◆ step()

Member Data Documentation

◆ alpha_

◆ budget_

◆ cache_

◆ classes_

◆ code_

◆ dead_state

◆ eligible_

◆ match_pc_

◆ no_transition

◆ rev_consume_

◆ rev_eps_

◆ start_state_

◆ state_budget

◆ state_has_start_

◆ state_pcs_

◆ trans_