Builds and holds the one-pass classification (and table, when eligible) of a byte-program.
More...
|
| constexpr | onepass (const byte_program &bp, std::size_t max_bytes=max_table_bytes, std::size_t node_cap=max_nodes, std::uint64_t work_cap=max_minimize_work) |
| |
| bool | eligible () const |
| | Whether the table was built and may be used.
|
| |
| const std::string & | bail_reason () const |
| | Why the build declined, when it did.
|
| |
| std::size_t | node_count () const |
| | Size of the built table.
|
| |
| std::uint16_t | num_classes () const |
| | Width of each node's edge row.
|
| |
| const std::vector< onepass_node > & | nodes () const |
| | The table itself, for a runtime that walks it (and for tests that pin its shape).
|
| |
| std::uint8_t | class_of (std::uint8_t byte) const |
| | The byte-class of byte, for a runtime that walks this table.
|
| |
| std::size_t | slot_count () const |
| | The number of capture slots (group 0 start/end plus each group's).
|
| |
| template<typename OutSlots > |
| bool | extract (std::string_view text, std::size_t s, std::size_t e, OutSlots &out) const |
| | Fills out with the capture slots of the one-pass match on text[s, e) — one left-to-right pass, no thread lists. text is the full subject (never a substring: assertions look at s - 1 and e). Anchored at s; this is fullmatch-on-span (the span the router located): it consumes to e and requires the run to accept exactly there. \ref real::npos marks a slot no edge wrote. Returns false (leaving out unspecified) if the pattern is ineligible or the span does not in fact match — which the caller has already ruled out for a router-supplied span.
|
| |
| bool | asserts_hold (std::uint32_t mask, std::string_view text, std::size_t pos) const |
| | Whether every assertion in mask (a set of assert_kind bits) holds at pos in text.
|
| |
|
|
static constexpr std::uint32_t | no_node {0xFFFFFFFFU} |
| | "No node yet" sentinel in the pc->node map.
|
| |
|
static constexpr std::size_t | max_nodes {65000} |
| | Node cap (RE2's), a memory/DoS bound.
|
| |
|
static constexpr std::size_t | max_slots {10} |
| | Slot-pointer cap: group 0 + four user groups.
|
| |
|
static constexpr std::size_t | minimize_buckets {4096} |
| | Hash buckets for the Moore-refinement dedup.
|
| |
| static constexpr std::size_t | max_table_bytes {8U << 20} |
| |
| static constexpr std::uint64_t | max_minimize_work {100'000'000ULL} |
| |
|
| constexpr void | bail (const char *reason, std::int32_t node=-1, std::int32_t klass=-1, std::int32_t pc=-1) |
| | Reject as not one-pass, recording a category and the offending node / byte-class / pc.
|
| |
| constexpr std::int32_t | follow_jumps (std::int32_t pc) const |
| | The first non-jump pc reachable from pc by following unconditional jumps.
|
| |
| constexpr std::uint32_t | node_of (std::int32_t pc, std::vector< std::int32_t > &queue) |
| | Get-or-create the node whose entry pc is pc, enqueueing a fresh one for the flood.
|
| |
| constexpr void | build (const byte_program &bp) |
| | Builds the table: flood the byte program into nodes, write their edges, then minimize.
|
| |
|
constexpr void | minimize () |
| | Moore partition refinement of the one-pass automaton: merge nodes that are behaviourally identical (same accept + match captures, and for every byte-class the same edge — target partition AND capture mask). The one-pass graph has cycles (\w+ loops), so bottom-up hash-consing is not enough; refinement to a fixpoint is. Merged nodes have identical capture masks by construction, so captures are unchanged. The dense per-node edge table is preserved, so extract's O(1) lookup is unchanged — the whole point of not going sparse.
|
| |
| constexpr void | build_edges (std::int32_t pc, std::uint64_t cap_mask, std::uint32_t assert_mask, std::vector< char > &on_path, std::uint32_t node_id, std::vector< std::int32_t > &queue) |
| | Walk the epsilon-closure from pc, writing this node's edges.
|
| |
|
|
std::span< const instr > | code_ |
| | The byte program being compiled; borrowed, not owned.
|
| |
|
std::span< const char_class > | classes_ |
| | Its interned byte classes; borrowed alongside code_.
|
| |
|
lazy_byte_alphabet | alpha_ |
| | Byte-equivalence classes: what class_of answers with.
|
| |
|
std::vector< std::vector< std::uint16_t > > | class_cover_ |
| | char-class index -> the byte-classes it consumes.
|
| |
|
std::vector< std::uint32_t > | pc_to_node_ |
| | pc -> node id (or no_node).
|
| |
|
std::vector< onepass_node > | nodes_ |
| | The table, node 0 being the start; empty until built.
|
| |
|
std::size_t | slot_count_ {0} |
| | Capture slots the program uses (slot_count).
|
| |
|
std::size_t | max_bytes_ {max_table_bytes} |
| | Table-memory cap; a larger table declines. Constructor parameter, so a test can exercise the cap without a pattern big enough to reach max_table_bytes.
|
| |
|
std::size_t | node_cap_ {max_nodes} |
| | Node-count cap; same test-hook role.
|
| |
|
std::uint64_t | work_cap_ {max_minimize_work} |
| | Moore-refinement work cap; same role.
|
| |
|
bool | ascii_word_ {true} |
| | Word-ness mode for \b \B \< \> in edge conditions (Tier-B): ASCII when the byte program carries no Unicode word-ness, which is what byte_program::unicode_word reports.
|
| |
|
std::int32_t | bail_node_ {-1} |
| | Node the decline was found at, or -1. Diagnostic only.
|
| |
|
std::int32_t | bail_class_ {-1} |
| | Byte-class involved in the decline, or -1.
|
| |
|
std::int32_t | bail_pc_ {-1} |
| | Program counter involved in the decline, or -1.
|
| |
|
bool | eligible_ {true} |
| | Cleared by bail; read through eligible.
|
| |
|
std::string | bail_reason_ |
| | Human-readable decline reason (bail_reason).
|
| |
Builds and holds the one-pass classification (and table, when eligible) of a byte-program.
Construction floods the program from the start: for each node it walks the epsilon-closure (split, jump, save) accumulating the capture mask, and every consuming instruction (byte, klass) writes the edge for its byte-class(es). A byte-class written twice with a different edge, a second reachable match with different captures, or an epsilon cycle (a nullable loop) each means not one-pass and the build bails with a human-readable reason. Node and slot counts are capped, so a pathological program is rejected rather than explored without bound.
| constexpr std::int32_t real::detail::onepass::follow_jumps |
( |
std::int32_t |
pc | ) |
const |
|
inlineconstexprprivate |
The first non-jump pc reachable from pc by following unconditional jumps.
A jump is a pure epsilon step – no byte consumed, no capture written, no assertion added (see the opcode::jump case in build_edges, which just recurses with the masks unchanged) – so the node at a jump's pc and the node at its target receive identical edges. Creating one for each leaves the flood holding a private copy of every shared trie subgraph, for minimize to merge afterwards – and emit_utf8_trie writes klass then jump(target) per trie edge, so on a Unicode class nearly every node sits on a jump. Resolving the chain makes the flood produce the shared node directly, so on those patterns it lands on the minimal automaton with nothing left for minimize to merge.
Bounded by the code size. A jump cycle would spin here, and build_edges's on_path detection only sees pcs it actually visits; on hitting the bound the pc is returned as-is, the flood reaches the cycle through build_edges, and that bails exactly as before.
- Parameters
-
- Returns
- The resolved pc (
pc itself when it is not a jump, or on running out of steps).
| constexpr std::uint64_t real::detail::onepass::max_minimize_work {100'000'000ULL} |
|
staticconstexpr |
Moore-refinement work cap (rounds x nodes x per-node signature width). A repeated large class (e.g. \w{k}, whose Unicode trie floods thousands of nodes per copy) forms a chain of that many node groups, and Moore refinement needs one round per link of the chain to propagate a distinguishing byte all the way back to the start – rounds ~ O(k), each O(nodes x alphabet), so total work is quadratic in k and unbounded as k grows. Bounding the CUMULATIVE work rather than the round count is what lets a small automaton refine as long as it needs while a long chain is caught early; the cap sits well above what the suite's own one-pass patterns reach. Larger declines to the VM, as the other caps do.
1.9.8