onepass.hpp File Reference

The one-pass builder: decides whether a pattern is one-pass and, if so, tabulates a deterministic capture-writing automaton over the byte-program. More...

#include <algorithm>
#include <array>
#include <atomic>
#include <bit>
#include <cassert>
#include <memory>
#include <mutex>
#include <span>
#include <type_traits>
#include <unordered_map>
#include <optional>
#include <cstddef>
#include <cstdint>
#include <string>
#include <string_view>
#include <vector>
#include "real/engine/aho_corasick.hpp"
#include "real/engine/assert_eval.hpp"
#include "real/automata/lazy_dfa.hpp"
#include "real/core/program.hpp"

Include dependency graph for onepass.hpp:

Classes
struct	real::detail::onepass_edge
	One outgoing edge of a one-pass node, for a byte-class: the next node and the capture slots that take the current position as the byte is consumed. Two epsilon paths reaching the same class with a different edge is the one-pass conflict — the pattern is then rejected. More...
struct	real::detail::onepass_node
	A one-pass node: one edge per byte-class, plus whether the run may end here and with what captures. Nodes are the points the automaton can be in between byte reads. More...
class	real::detail::onepass
	Builds and holds the one-pass classification (and table, when eligible) of a byte-program. More...
struct	real::detail::regex_immutables
	The per-regex immutable cache the router shares across every find_iter on a regex: the byte program (klass_cp expanded to the deterministic trie) and, when the pattern is one-pass, the extractor table. More...
struct	real::detail::shared_dfa_slot
	Process-wide shared DFA transition caches keyed by regex_immutables*. 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.

Functions
void	real::detail::erase_shared_dfas (const regex_immutables *immut)
	Retire this regex's slot (called from ~regex_immutables). Concurrent scans that still hold a shared_ptr via TLS keep the slot object alive until they release; clearing shared_dfa_slot::owner is what makes their cached copy stop matching, so a new regex landing on this address can never be served the retired slot.
std::mutex &	real::detail::immut_build_mu (const regex_immutables *immut)
	Striped rebuild lock for pike_vm::ensure_immutables (not on regex_immutables — layout isolation). Distinct from shared_dfa_map_mu / slot.mu so reset_shared_dfas cannot self-deadlock. Different immutables rarely share a stripe.
std::mutex &	real::detail::shared_dfa_map_mu ()
	The mutex guarding insert/erase on the process-wide shared_dfa_slot map.
std::unordered_map< const regex_immutables *, std::shared_ptr< shared_dfa_slot > > &	real::detail::shared_dfa_map ()
	Process-wide map. Intentionally never destroyed (leaky singleton): a static map would tear down at exit while other statics' ~regex_immutables still call erase_shared_dfas. The OS reclaims the map at process exit — not an accumulating leak; entries are erased on dtor.
shared_dfa_slot &	real::detail::shared_dfa_for (regex_immutables *immut)
	Resolve the process-wide DFA slot for this regex (map insert under shared_dfa_map_mu).
void	real::detail::reset_shared_dfas (regex_immutables *immut)
	Drop any DFAs cached for immut (caller holds nothing; takes map + slot locks). Invoked from pike_vm's ensure_immutables rebuild so a reused immutables address — or the same address under a new program — cannot keep a previous pattern's DFAs.
std::size_t	real::detail::shared_dfa_map_size_for_test ()
	Test/audit: number of live shared-DFA map entries (process-wide). Not for production.

Variables
constexpr std::size_t	real::detail::il_warm_floor {4UL * 1024}
	Warm-regime IL minimum haystack, in bytes. The shared reverse DFA is amortised after the first scan, but below this size the candidate scan itself can cost more than the route saves, so the floor stays. A cold first scan uses the higher regex_immutables::il_min_haystack instead.

Detailed Description

The one-pass builder: decides whether a pattern is one-pass and, if so, tabulates a deterministic capture-writing automaton over the byte-program.

A pattern is one-pass (Brüggemann-Klein & Wood, "One-unambiguous regular languages"; RE2 onepass.cc) when, matched anchored, at most one thread crosses any byte — the non-determinism is contained. For such a pattern the capture slots can be filled in a single left-to-right pass with no thread lists at all: at each node, the byte read selects exactly one outgoing edge, whose recorded conditions say which slots take the current position. (\w+)@(\w+) is one-pass (inside \w+ an @ cannot extend the run, so there is no ambiguity); (\w+)_(\w+) is not (_ is itself a \w, so a _ both extends group 1 and starts the separator — a genuine conflict).

This header classifies a pattern and, when one-pass, produces the node table; pike_vm walks it through real::detail::onepass::extract, which is what the onepass_full and onepass_window routes are. It builds over the byte program (Unicode \w \d \s already expanded to byte ranges), so the one-pass check runs at the byte level. The table is a readable struct rather than RE2's packed uint32: packing would be a runtime decision, and the differential holds either form to the same answers.