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 <bit>
#include <mutex>
#include <optional>
#include <cstddef>
#include <cstdint>
#include <string>
#include <string_view>
#include <vector>
#include "real/engine/assert_eval.hpp"
#include "real/automata/lazy_dfa.hpp"
#include "real/core/program.hpp"

Include dependency graph for onepass.hpp:

Go to the source code of this file.

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. Built exactly once, under once, so a const regex used from many threads (the binding shares the compiled object across GIL-released calls) builds it race-free. The mutable DFA transition caches stay per-iterator — they warm per scan and would need a lock here. More...

Namespaces
namespace	real
namespace	real::detail

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 is the builder only (the arc's first slice): it classifies a pattern and, when one-pass, produces the node table. Nothing runs matching through it yet. It builds over the L2.5 byte_program (Unicode \w \d \s already expanded to byte ranges), so the one-pass check runs at the byte level. The table format here is a readable struct, not RE2's packed uint32; packing is a runtime concern (a later slice) that the differential would catch either way.

Definition in file onepass.hpp.