A multi-rule DFA: maximal-munch (dfa_mode::munch) or which-matched unanchored scan (dfa_mode::which_matched). More...

#include <dfa.hpp>

Collaboration diagram for real::dfa:

[legend]

Classes
struct	walk_end
	Where a munch walk stopped and the last accept it passed. More...

Public Member Functions
	dfa (std::span< const detail::program_view > programs, dfa_mode mode=dfa_mode::munch)
	Builds the DFA from compiled programs (the embedder path).

	dfa (std::span< const regex > patterns, dfa_mode mode=dfa_mode::munch)
	Builds the DFA from regexes (a convenience over regex::raw_program).

std::optional< dfa_match >	match (std::string_view rest) const noexcept
	Matches the longest pattern anchored at the start of `rest`.

std::optional< dfa_match >	match (std::string_view subject, std::size_t offset, dfa_munch_memo &memo) const
	match(std::string_view) const at `offset` of `subject`, remembering in `memo` what the walk proved so that successive calls over the same subject cost linear time in total.

dfa_munch	munch (std::string_view subject, std::size_t offset, dfa_munch_memo &memo) const
	match(std::string_view, std::size_t, dfa_munch_memo&) const, and whether text after `subject` could change the answer: a lexer reading text that arrives in pieces commits to a munch only when it could not.

std::vector< bool >	which_matched (std::string_view text, bool first_byte_skip=true) const
	Which patterns match the subject at least once (single-pass).

bool	has_first_byte_skip () const noexcept
	True if set-level first-byte skip is armed for which_matched.

bool	is_unanchored () const noexcept
	True if this DFA was built with mid-stream restart (which-matched mode).

std::size_t	state_count () const noexcept
	The number of states in the minimized automaton (includes the dead state).

std::size_t	rule_count () const noexcept
	The number of patterns the DFA was built from.

std::size_t	class_count () const noexcept
	The number of byte-equivalence classes (the reduced alphabet width).

Private Member Functions
std::uint32_t	next_state (std::uint32_t state, char c) const noexcept
	The state the DFA moves to from `state` on byte `c` (0 is the dead state).

bool	leads_only_to_death (std::uint32_t state) const noexcept
	Whether every byte takes `state` to the dead state.

walk_end	memo_walk (std::string_view subject, std::size_t offset, dfa_munch_memo &memo) const
	The memo-checked munch walk behind match and munch, the plain walk or, once the subject's memo has proved a dead stretch, the armed one; it marks a long new stretch.

template<bool Armed>
walk_end	walk (std::string_view subject, std::size_t offset, const dfa_munch_memo *memo) const noexcept
	The munch walk from the start state at `offset` until the DFA dies or the subject ends.

std::uint32_t	state_at (std::string_view subject, std::size_t from, std::size_t to) const noexcept
	The state a walk from the start state at `from` reaches at `to` (a replay, only on the rare path that arms a memo).

walk_end	match_armed (std::string_view subject, std::size_t offset, dfa_munch_memo &memo) const
	match once `memo` is armed: the same walk, stopping at a pair an earlier walk proved dead, and marking a long dead stretch of its own. Out of line: only a subject that armed its memo – one with a long dead stretch – reaches it.

void	mark_dead_stretch (std::string_view subject, std::uint32_t state, std::size_t from, std::size_t to, dfa_munch_memo &memo) const
	Replays the walk from `state` at `from` to `to`, marking every pair it passes as dead in `memo` (arming it on first use). Out of line: only a long dead stretch reaches it, and keeping it out of match keeps the per-token walk as small as the plain one.

Static Private Member Functions
static std::optional< dfa_match >	answer (const walk_end &w, std::size_t offset) noexcept
	The public answer for a walk started at `offset`.

static std::vector< detail::program_view >	views_of (std::span< const regex > patterns)
	Materializes program views from `patterns` (helper for the regex ctor).

Private Attributes
detail::dfa_tables	tables_
	The immutable baked tables.

Detailed Description

A multi-rule DFA: maximal-munch (dfa_mode::munch) or which-matched unanchored scan (dfa_mode::which_matched).

Built once (heap-allocated tables), then immutable. match is the lexer munch; which_matched is valid only when built with dfa_mode::which_matched.

Constructor & Destructor Documentation

◆ dfa() [1/2]

real::dfa::dfa	(	std::span< const detail::program_view >	programs,
		dfa_mode	mode = `dfa_mode::munch`
	)

inlineexplicit

Builds the DFA from compiled programs (the embedder path).

Warning: An advanced, unstable extension point: detail::program_view is an implementation type, and its members may change in any release. Build from regexes instead unless the programs come from an embedder that already holds them.

Parameters

[in]	programs	The patterns' programs, in priority order (see regex::raw_program).
[in]	mode	Munch (default) or which-matched unanchored multi-accept.

Exceptions

real::dfa_error for a pattern that is not DFA-able (see dfa_error).

◆ dfa() [2/2]

real::dfa::dfa	(	std::span< const regex >	patterns,
		dfa_mode	mode = `dfa_mode::munch`
	)

inlineexplicit

Builds the DFA from regexes (a convenience over regex::raw_program).

Parameters

[in]	patterns	The patterns, in priority order; they must outlive this call.
[in]	mode	Munch (default) or which-matched.

Exceptions

real::dfa_error for a pattern that is not DFA-able (see dfa_error).

Member Function Documentation

◆ answer()

static std::optional< dfa_match > real::dfa::answer	(	const walk_end &	w,
		std::size_t	offset
	)

inlinestaticprivatenoexcept

The public answer for a walk started at offset.

Parameters

[in]	w	The walk.
[in]	offset	Where it started.

Returns: The winning rule and length, or std::nullopt.

◆ class_count()

std::size_t real::dfa::class_count ( ) const

inlinenoexcept

The number of byte-equivalence classes (the reduced alphabet width).

Returns: The class count.

◆ has_first_byte_skip()

bool real::dfa::has_first_byte_skip ( ) const

inlinenoexcept

True if set-level first-byte skip is armed for which_matched.

Returns: Whether every rule contributed a valid first-byte set at build time.

◆ is_unanchored()

bool real::dfa::is_unanchored ( ) const

inlinenoexcept

True if this DFA was built with mid-stream restart (which-matched mode).

Returns: Whether the tables carry self-restart transitions.

◆ leads_only_to_death()

bool real::dfa::leads_only_to_death ( std::uint32_t state ) const

inlineprivatenoexcept

Whether every byte takes state to the dead state.

Parameters

[in] state A live state.

Returns: True when no walk can go on from it.

◆ mark_dead_stretch()

void real::dfa::mark_dead_stretch	(	std::string_view	subject,
		std::uint32_t	state,
		std::size_t	from,
		std::size_t	to,
		dfa_munch_memo &	memo
	)		const

inlineprivate

Replays the walk from state at from to to, marking every pair it passes as dead in memo (arming it on first use). Out of line: only a long dead stretch reaches it, and keeping it out of match keeps the per-token walk as small as the plain one.

Parameters

[in]	subject	The memo's subject.
[in]	state	The state the walk stood on at `from` (its last accept, or the start).
[in]	from	Where the dead stretch begins.
[in]	to	Where the walk stopped.
[in,out]	memo	The subject's memo.

◆ match() [1/2]

std::optional< dfa_match > real::dfa::match ( std::string_view rest ) const

inlinenoexcept

Matches the longest pattern anchored at the start of rest.

Maximal munch: the longest match wins; on equal length the earliest pattern (lowest index passed to the constructor) wins; an empty match never wins.

Parameters

[in] rest The text to match at its start.

Returns: The winning rule index and byte length, or std::nullopt if nothing non-empty matches.

◆ match() [2/2]

std::optional< dfa_match > real::dfa::match	(	std::string_view	subject,
		std::size_t	offset,
		dfa_munch_memo &	memo
	)		const

inline

match(std::string_view) const at offset of subject, remembering in memo what the walk proved so that successive calls over the same subject cost linear time in total.

Answers exactly what match(subject.substr(offset)) answers.

Parameters

[in]	subject	The whole subject; every call with `memo` must pass the same one.
[in]	offset	Where this munch starts (at most `subject.size()`).
[in,out]	memo	The subject's memo (see dfa_munch_memo).

Returns: The winning rule index and byte length, or std::nullopt if nothing non-empty matches.

Exceptions

std::invalid_argument If memo was made for a subject of another length, was used with another DFA, or offset lies beyond subject.

◆ match_armed()

walk_end real::dfa::match_armed	(	std::string_view	subject,
		std::size_t	offset,
		dfa_munch_memo &	memo
	)		const

inlineprivate

match once memo is armed: the same walk, stopping at a pair an earlier walk proved dead, and marking a long dead stretch of its own. Out of line: only a subject that armed its memo – one with a long dead stretch – reaches it.

Parameters

[in]	subject	The memo's subject.
[in]	offset	Where this munch starts.
[in,out]	memo	The subject's memo, armed.

Returns: The winning rule index and byte length, or std::nullopt.

◆ memo_walk()

walk_end real::dfa::memo_walk	(	std::string_view	subject,
		std::size_t	offset,
		dfa_munch_memo &	memo
	)		const

inlineprivate

The memo-checked munch walk behind match and munch, the plain walk or, once the subject's memo has proved a dead stretch, the armed one; it marks a long new stretch.

Parameters

[in]	subject	The text; every call with `memo` must pass the same one.
[in]	offset	Where the walk starts.
[in,out]	memo	The subject's memo.

Returns: The walk.

Exceptions

std::invalid_argument If memo belongs to another subject or DFA, or offset is past it.

◆ munch()

dfa_munch real::dfa::munch	(	std::string_view	subject,
		std::size_t	offset,
		dfa_munch_memo &	memo
	)		const

inline

match(std::string_view, std::size_t, dfa_munch_memo&) const, and whether text after subject could change the answer: a lexer reading text that arrives in pieces commits to a munch only when it could not.

The walk is the same; telling costs nothing more. A walk that died within the subject proves the answer final, whatever follows; so does one that ends in a state every byte leaves for the dead one, and one the memo stopped while every stretch it marked was walked to a death. Any other walk alive at the subject's end may not be final.

Parameters

[in]	subject	The text so far; every call with `memo` must pass the same one.
[in]	offset	Where this munch starts (at most `subject.size()`).
[in,out]	memo	The subject's memo (see dfa_munch_memo).

Returns: The munch and whether more text may change it.

Exceptions

std::invalid_argument As match(std::string_view, std::size_t, dfa_munch_memo&) const.

◆ next_state()

std::uint32_t real::dfa::next_state	(	std::uint32_t	state,
		char	c
	)		const

inlineprivatenoexcept

The state the DFA moves to from state on byte c (0 is the dead state).

Parameters

[in]	state	The current state.
[in]	c	The byte read.

Returns: The next state.

◆ rule_count()

std::size_t real::dfa::rule_count ( ) const

inlinenoexcept

The number of patterns the DFA was built from.

Returns: The rule count, which is also the width of which_matched's answer.

◆ state_at()

std::uint32_t real::dfa::state_at	(	std::string_view	subject,
		std::size_t	from,
		std::size_t	to
	)		const

inlineprivatenoexcept

The state a walk from the start state at from reaches at to (a replay, only on the rare path that arms a memo).

Parameters

[in]	subject	The text.
[in]	from	Where the walk begins.
[in]	to	Where it has read up to.

Returns: The state after reading subject[from, to).

◆ state_count()

std::size_t real::dfa::state_count ( ) const

inlinenoexcept

The number of states in the minimized automaton (includes the dead state).

Returns: The state count.

◆ views_of()

static std::vector< detail::program_view > real::dfa::views_of ( std::span< const regex > patterns )

inlinestaticprivate

Materializes program views from patterns (helper for the regex ctor).

Parameters

[in] patterns The compiled regexes, which must outlive the views.

Returns: One view per pattern, in the same order.

◆ walk()

template<bool Armed>

walk_end real::dfa::walk	(	std::string_view	subject,
		std::size_t	offset,
		const dfa_munch_memo *	memo
	)		const

inlineprivatenoexcept

The munch walk from the start state at offset until the DFA dies or the subject ends.

Template Parameters

Armed Also stop at a (state, position) pair memo proved dead, and track the state at the last accept; unarmed, the walk is the plain one plus nothing.

Parameters

[in]	subject	The text.
[in]	offset	Where the walk starts.
[in]	memo	The armed memo (Armed only; null otherwise).

Returns: Where it stopped and its last accept.

Note: Force-inlined: out of line, the memo-taking match's per-token walk costs 5-9 % more.

◆ which_matched()

std::vector< bool > real::dfa::which_matched	(	std::string_view	text,
		bool	first_byte_skip = `true`
	)		const

inline

Which patterns match the subject at least once (single-pass).

Requires a build with dfa_mode::which_matched. Early-exits when every pattern has hit. The start state's accept mask is folded in before the walk, so a rule accepting the EMPTY string answers true on an empty subject, as N separate walks would; every other accept comes from a post-move mask.

Parameters

[in]	text	Subject text.
[in]	first_byte_skip	When true (default), fast-forward over bytes that cannot start any rule while the walk is in the start state; false is for equivalence tests.

Returns: One bool per rule, in construction order, true where that pattern matched.

Fold one state's accept mask into the accumulator, counting newly-set bits for early exit.

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

include/real/dfa.hpp

Classes

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ dfa() [1/2]

◆ dfa() [2/2]

Member Function Documentation

◆ answer()

◆ class_count()

◆ has_first_byte_skip()

◆ is_unanchored()

◆ leads_only_to_death()

◆ mark_dead_stretch()

◆ match() [1/2]

◆ match() [2/2]

◆ match_armed()

◆ memo_walk()

◆ munch()

◆ next_state()

◆ rule_count()

◆ state_at()

◆ state_count()

◆ views_of()

◆ walk()

◆ which_matched()