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/prefilter.hpp"
#include "real/engine/assert_eval.hpp"
#include "real/automata/lazy_dfa.hpp"
#include "real/core/config.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_step
	One edge of the flattened table onepass::extract walks: onepass_edge with the target given as the offset of its row, so a step is one load from one array. 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_set
	One thread's lazy DFAs for one regex: the transition caches a scan fills as it walks. More...
struct	real::detail::shared_dfa_slot
	Process-wide per-regex DFA state keyed by regex_immutables*: a pool of shared_dfa_set, one per thread using the regex, and the flags every thread shares. More...
class	real::detail::dfa_lease
	This thread's DFA set for one regex, for the lifetime of the lease: a scan through it takes no lock, so threads sharing a regex do not queue on its DFAs. More...
struct	real::detail::dfa_lease::cache
	The set a thread keeps between leases, and the slot it returns to. 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). Scans still holding the slot's shared_ptr keep it alive; clearing shared_dfa_slot::owner stops their cached copy matching, so a new regex at this address is never 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 / shared_dfa_slot::pool_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, deliberately never destroyed: other statics' ~regex_immutables still call erase_shared_dfas at exit. Entries are erased per destructor, so nothing accumulates.
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, bool keep_warm=false)
	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: below it the candidate scan can cost more than the route saves, even with the reverse DFA already built. A cold first scan uses the higher regex_immutables::il_min_haystack.
constexpr std::size_t	real::detail::il_short_scan_budget {64UL * 1024}
	Subject bytes a regex lets the inner-literal route decline under its floor before it builds what the route needs: the cold floor's least amortization. Short subjects that add up to it have paid for the build as one long subject would, and the build lifts both floors for good. Without it a regex only ever searched on short subjects stays on the bounded backtracker, many times dearer per search than the built route.
constexpr std::uint32_t	real::detail::onepass_prefix_warm_calls {8192}
	Anchored matches a regex runs before it builds its one-pass table for them. Rent before buying: the build (byte program, table, minimization) costs about as much as 5 000 to 13 000 of these calls made without it, so a regex matched a few times never pays it, and one matched in a loop pays at most about twice what the best choice made in hindsight would have.

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. Its capture slots then fill in one left-to-right pass with no thread lists: at each node the byte read selects exactly one edge, whose conditions say which slots take the current position. (\w+)@(\w+) is one-pass; (\w+)_(\w+) is not (_ both extends group 1 and starts the separator).

pike_vm walks the table through real::detail::onepass::extract (the onepass_full and onepass_window routes). The build runs over the byte program (Unicode \w \d \s already expanded to byte ranges), so the one-pass check is byte-level.