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 <array>
#include <cstddef>
#include <ranges>
#include <cstdint>
#include <limits>
#include <optional>
#include <span>
#include <stdexcept>
#include <string>
#include <string_view>
#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::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...
class	real::dfa
	A multi-rule DFA: maximal-munch (dfa_mode::munch) or which-matched unanchored scan (dfa_mode::which_matched). 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. 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.
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.

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.

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 is linear but re-scans the input once per candidate rule. real::dfa fuses a set of patterns into one deterministic automaton that recognizes the winning rule in a single left-to-right pass — the same maximal-munch decision (longest match; ties to the earliest rule), reached far faster when many rules share leading bytes. It is built from the patterns' compiled programs, runs at run time (the tables are heap-allocated once and then immutable), and is the accelerated rule-dispatch path SciLex opts into.

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). A pattern with any other assertion ($, \b, multiline ^/$, …) is not representable as a pure DFA; the constructor throws real::dfa_error rather than silently mis-recognizing — the caller keeps such rules on the Pike VM. Lazy/greedy makes no difference to a DFA: it recognizes the pattern's language and takes the longest match, which is the lexer's munch for greedy rules but not for lazy ones (whose match() is the shortest) — so the caller must only feed DFA-faithful (greedy, assertion-free) rules. Include this header explicitly; real.hpp does not.