lazy_dfa.hpp File Reference

A lazy, priority-preserving forward DFA over the Pike program (the kFirstMatch forward pass + cache). More...

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <span>
#include <string>
#include <string_view>
#include <vector>
#include "real/core/program.hpp"
#include "real/automata/utf8_ranges.hpp"

Include dependency graph for lazy_dfa.hpp:

Go to the source code of this file.

Classes
struct	real::detail::byte_program
	A byte-level program derived from a Pike program for the DFA passes: every klass_cp construct is expanded into UTF-8 byte-range split/klass chains, so the whole thing is byte-transition-only and a forward DFA can represent it. The Pike program itself is untouched (byte-identity); this is a private recognition view the DFAs own. eligible is false when an op no DFA can represent (a position assertion or a lookaround) is present — the caller then keeps the Pike VM. More...
struct	real::detail::utf8_trie_node
	One node of a minimal deterministic UTF-8 trie for a code-point class. Its transitions are byte ranges that are pairwise disjoint, so at most one edge matches any byte — that determinism is what makes the byte-program one-pass-friendly. child >= 0 is a node id; child == -1 is accept (a code point ends here — the run continues at the construct's successor). More...
struct	real::detail::utf8_trie
	A minimal deterministic UTF-8 trie for a code-point class. root == -1 means the class is empty. More...
struct	real::detail::lazy_byte_alphabet
	Byte-class alphabet over a Pike program: bytes that satisfy exactly the same byte/klass predicates share a class, so the DFA transitions over classes instead of 256 raw bytes. The same reduction real::dfa uses, computed here from the Pike program's own ops. More...
struct	real::detail::pc_set_cache
	A tiny open-chaining hash set of interned PC-set state ids, keyed by their pc-set. Replaces a std::unordered_map so the DFAs stay literal types (a constexpr real::regex embeds one in its scratch state); all-std::vector storage is constexpr-constructible in C++20. Maps a candidate pc-set to its existing state id, or not_found, comparing against the owner's pcs. More...
class	real::detail::lazy_dfa
	A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass). More...
struct	real::detail::lazy_dfa::counters
	Cache-behaviour counters, for the policy tests and later tuning. More...
class	real::detail::reverse_dfa
	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...

Namespaces
namespace	real
namespace	real::detail

Functions
bool &	real::detail::lazy_dfa_route_disabled ()
	Test seam: force the matcher off the lazy-DFA route onto the pure Pike VM, so a differential can assert that routed and unrouted searches give identical results within one binary. Not for production use — the routing is transparent by contract, and this only exists to prove it.
bool &	real::detail::inner_literal_route_disabled ()
	Test seam: force the matcher off the inner-literal search route (IL.2) onto the core search, so a differential can assert routed and unrouted searches agree. Not for production use — the route is transparent by contract (its reverse bound never advances mid-search, so it cannot miss a leftmost match), and this only exists to prove it.
bool &	real::detail::inner_literal_guard_disabled ()
	Test seam: force the inner-literal small-haystack guard off, so the route fires on any size. In production the guard keeps the route off a haystack too small for its per-iterator reverse cache to amortize (it would else be slower than the core). The correctness suites (the exhaustive compat run, the routed==core differential) use tiny inputs, so they set this to exercise the route itself rather than the core it would otherwise fall back to. Not for production use.
utf8_trie	real::detail::build_utf8_trie (const cp_class &cc, std::span< const code_range > cp_ranges)
	Builds the minimal deterministic trie recognising a code-point class's UTF-8 byte sequences.
std::size_t	real::detail::utf8_trie_emit_size (const utf8_trie &trie)
	The instruction count emit_utf8_trie writes: an empty class is one dead klass; otherwise each node is a split-guarded chain of k byte ranges (3k - 1 instructions).
void	real::detail::emit_utf8_trie (byte_program &bp, const utf8_trie &trie, std::int32_t after)
	Emits trie into bp as a deterministic split/klass/jump fragment; accept edges jump to after (the construct's successor). The root is emitted first, so the fragment's entry is its base pc. Disjoint ranges mean at most one branch matches any byte.
byte_program	real::detail::build_byte_program (const program_view &prog, bool keep_assertions=false)
	Builds the byte-level DFA program for prog (see byte_program). A klass_cp at P (a four- instruction construct: the op plus three utf8_cont continuation slots) is replaced by the deterministic UTF-8 trie recognising its code-point class (build_utf8_trie), converging on the mapped P+4; every other op is copied with its branch targets remapped. Two passes: the first builds each trie and sizes it to form the old→new pc map, the second emits.
constexpr lazy_byte_alphabet	real::detail::compute_lazy_alphabet (std::span< const instr > code, std::span< const char_class > classes)
	Partition 0..255 by the program's consuming predicates (every klass test, every byte literal). Bytes with an identical signature collapse to one class.

Detailed Description

A lazy, priority-preserving forward DFA over the Pike program (the kFirstMatch forward pass + cache).

DISTINCT from real::dfa (<real/dfa.hpp>): that one is a capture-free maximal-munch recognizer over unordered NFA-state sets (a lexer's rule dispatch). This one memoizes the leftmost-first Pike closure — its DFA states are ordered NFA-state sets, so a kFirstMatch forward pass reports the same match boundary the Pike VM would. It reuses only the byte-class idea (an alphabet smaller than 256), not that engine's subset construction.

Note

The forward pass (forward_end), the reverse start-finder (reverse_dfa) and the byte-program that makes a Unicode klass_cp DFA-representable are wired into the matcher: pike.hpp routes an eligible search through them (forward end + reverse start, then the Pike VM on the located window). Dynamic only: the cache is mutable, so it never participates in constant evaluation.

Definition in file lazy_dfa.hpp.