dfa.hpp File Reference

real::dfa — a maximal-munch DFA over a set of patterns (opt-in). More...

#include "real/version.hpp"
#include <algorithm>
#include <bit>
#include <array>
#include <cstddef>
#include <ranges>
#include <cstdint>
#include <limits>
#include <map>
#include <optional>
#include <span>
#include <stdexcept>
#include <string>
#include <string_view>
#include <tuple>
#include <utility>
#include <vector>
#include "real/core/config.hpp"
#include "real/real.hpp"

Include dependency graph for dfa.hpp:

Classes
class	real::dfa_error
	Thrown when a pattern cannot be represented as a DFA. More...
struct	real::dfa_match
	The outcome of dfa::match — which rule won, and how many bytes it spans. More...
struct	real::dfa_munch
	A munch, and whether text after the subject could change it (dfa::munch). More...
struct	real::detail::dfa_instr
	A flattened NFA instruction (global PCs, global class index). More...
struct	real::detail::dfa_nfa
	The union NFA over all the patterns, flattened into one address space. More...
struct	real::detail::dfa_byte_classes
	Computes byte-equivalence classes: two bytes are equivalent iff they satisfy the same consuming predicates (every klass test and every byte literal). Reduces the alphabet so the DFA is built over classes, not over 256 bytes. More...
struct	real::detail::dfa_tables
	The baked DFA tables produced by dfa_build. More...
struct	real::detail::dfa_fidelity_raw
	The per-pattern answer of real::dfa_faithful, before the public wrapping. More...
class	real::dfa_munch_memo
	What successive munches over ONE subject have learnt, so that tokenizing the whole subject costs O(states × length) instead of O(length²) (Reps, "Maximal-munch tokenization in linear time", 1998). More...
class	real::dfa
	A multi-rule DFA: maximal-munch (dfa_mode::munch) or which-matched unanchored scan (dfa_mode::which_matched). More...
struct	real::dfa::walk_end
	Where a munch walk stopped and the last accept it passed. More...
struct	real::dfa_fidelity
	The answer of real::dfa_faithful. More...

Namespaces
namespace	real
	REAL's public API: real::regex, real::static_regex, real::flags and the match/iterator types built on them.
namespace	real::detail
	DFA construction internals: subset construction over a flattened NFA. Not a stable API.

Typedefs
using	real::detail::dfa_set = std::vector< std::uint64_t >
	A set of NFA PCs as a bitset (one per DFA state during construction).

Enumerations
enum class	real::dfa_mode : std::uint8_t { real::munch = 0 , real::which_matched = 1 }
	Build mode for real::dfa: maximal munch at the cursor (a lexer; the default), or an unanchored multi-accept single pass (which patterns match anywhere). More...
enum class	real::dfa_fidelity_outcome : std::uint8_t { real::faithful = 0 , real::divergent = 1 , real::undecided = 2 }
	The three answers real::dfa_faithful can give. More...

Functions
dfa_nfa	real::detail::dfa_flatten (std::span< const program_view > programs)
	Flattens programs into one union NFA, auditing DFA-ability.
void	real::detail::dfa_set_bit (dfa_set &s, std::size_t i)
	Set bit i in s. Indices past the set's size are ignored (it is sized to fit).
bool	real::detail::dfa_test_bit (const dfa_set &s, std::size_t i)
	Whether bit i is set in s.
dfa_set	real::detail::dfa_closure (const dfa_nfa &nfa, const std::vector< std::uint32_t > &seeds, bool at_start)
	The epsilon-closure of seeds (a PC list), as a canonical PC bitset. at_start follows a text_start assertion (true only at offset 0).
dfa_set	real::detail::dfa_move (const dfa_nfa &nfa, const dfa_set &set, std::uint8_t rep)
	The move on the byte rep: ε-closure of the successors of every PC in set that consumes rep.
std::int64_t	real::detail::dfa_accept_of (const dfa_nfa &nfa, const dfa_set &set)
	The accepting rule of a state set: the SMALLEST rule index among its match PCs (the order tie-break), or -1 if none accept.
std::size_t	real::detail::dfa_mask_words (std::size_t rule_count) noexcept
	Word count for a which-matched bitset over rule_count rules.
std::vector< std::uint64_t >	real::detail::dfa_accept_mask_of (const dfa_nfa &nfa, const dfa_set &set)
	Bitset of ALL accepting rule indices in set (which-matched; word-packed). Empty vector when no rule accepts (or rule_count == 0).
std::int64_t	real::detail::dfa_mask_min_rule (const std::vector< std::uint64_t > &mask)
	Smallest rule index set in mask, or -1 if empty (munch tag derivation).
dfa_byte_classes	real::detail::dfa_compute_classes (const dfa_nfa &nfa)
	Partition 0..255 by the union NFA's consuming predicates.
void	real::detail::dfa_seeds_all (const dfa_nfa &nfa, const dfa_set &set, const dfa_byte_classes &bc, const std::vector< std::vector< std::uint8_t > > &klass_members, std::vector< std::vector< std::uint32_t > > &seeds)
	Every class's seed list from one state in one pass over the state's PCs: the PCs after each consuming instruction that class passes, without rescanning the set once per class.
dfa_tables	real::detail::dfa_build (std::span< const program_view > programs, std::size_t state_cap=max_dfa_states, bool unanchored=false)
	Subset construction over byte-classes, then Moore minimization.
bool	real::detail::dfa_priority_closure (const dfa_nfa &nfa, std::uint32_t seed, bool at_start, std::vector< std::uint8_t > &seen, std::vector< std::uint32_t > &out)
	The priority-ordered epsilon closure of seed, as the Pike walk builds it: consuming pcs are appended to out in priority order, and reaching a match stops the walk, because a thread list is cut below its first accepting thread.
dfa_fidelity_raw	real::detail::dfa_decide_fidelity (const program_view &prog, std::size_t budget)
	Decides whether prog's priority match equals its longest match on every input.
void	real::detail::dfa_memo_misuse (const char *what)
	Throws the std::invalid_argument a misused dfa_munch_memo raises, out of line so the throw does not weigh on the per-token match that checks for it.
dfa_fidelity	real::dfa_faithful (const regex &pattern, std::size_t state_budget=dfa_default_state_budget)
	Decides whether pattern's match() is always its longest match – whether a dfa built from it reproduces pattern.match() on every input.
dfa_fidelity	real::dfa_faithful (std::span< const regex > patterns, std::size_t state_budget=dfa_default_state_budget)
	Decides real::dfa_faithful for each of patterns, in order, and answers for the first one not proven faithful (its index in dfa_fidelity::rule_index).

Variables
constexpr std::size_t	real::detail::max_dfa_byte_program {512}
	Cap on a pattern's expanded byte program before subset construction runs on it.
constexpr std::uint32_t	real::detail::dfa_no_rule {std::numeric_limits<std::uint32_t>::max()}
	dfa_tables::accept's "this state does not accept" marker.
constexpr std::size_t	real::dfa_default_state_budget {65536}
	The default search budget of real::dfa_faithful, in product states: the default cap a dfa's own construction runs under. A build that lowers that cap (REAL_MAX_DFA_STATES) keeps this budget; its construction then refuses, with real::dfa_error, what the search accepts.

Detailed Description

real::dfa — a maximal-munch DFA over a set of patterns (opt-in).

A lexer matches many rules at every position; running each rule's Pike VM in turn re-scans the input once per candidate rule. real::dfa fuses a rule set into one deterministic automaton that finds the winning rule in a single left-to-right pass (longest match; ties to the earliest rule). It is built at run time from the patterns' compiled programs; the tables are heap-allocated once, then immutable.

Note

NOT the internal real::detail::lazy_dfa (automata/lazy_dfa.hpp): that one is a private, priority-preserving forward DFA that finds a single pattern's match boundary for the Pike route. This real::dfa is a public, capture-free maximal-munch recognizer over a whole rule set.

Scope: a pattern is DFA-able iff its program holds no zero-width assertion other than a leading \A/^ (a no-op under anchored scanning), no lookaround, no possessive quantifier or atomic group, and a byte expansion small enough to build. Anything else throws real::dfa_error, never a silent mis-recognition; the caller keeps such rules on the Pike VM.

DFA-able is not faithful. A DFA takes the LONGEST match of the pattern's language, regex::match() the one its priority order prefers, and the syntax does not show which patterns differ: a|ab on "ab" matches 1 byte where the DFA takes 2, as does (?:ab|a)(?:bc)? on "abc", while x*?y agrees on every input. A caller that needs the DFA to reproduce a per-rule match() munch asks real::dfa_faithful, which decides it per pattern and names a separating input. Include this header explicitly; real.hpp does not.