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) |
| | Classifies bp and, when it is one-pass, builds the table. A smaller cap is a test hook.
|
| |
| 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 nodes, for tests that pin the table's shape. A built table keeps its edges in steps_ alone, so each node's onepass_node::edge row is empty once the build is over.
|
| |
| 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): fullmatch on the span the router located, anchored at s and accepting exactly at e. A slot no edge wrote is real::npos.
|
| |
| bool | ends_known () const |
| | Whether extract_leftmost applies: no node accepts with edges on both sides of its match.
|
| |
| template<typename OutSlots > |
| std::size_t | extract_leftmost (std::string_view text, std::size_t s, OutSlots &out, std::size_t &reach) const |
| | The leftmost-first match anchored at s, found and captured in one pass: no end needs to be known beforehand, unlike extract.
|
| |
| 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::uint32_t | no_row {0xFFFFFFFFU} |
| | onepass_step::row of an unassigned edge.
|
| |
|
static constexpr std::uint8_t | rank_none {0} |
| | accept_rank of a node that does not accept.
|
| |
|
static constexpr std::uint8_t | rank_continue {1} |
| | Accepts, and every edge outranks the match.
|
| |
|
static constexpr std::uint8_t | rank_match {2} |
| | Accepts, and the match outranks every edge.
|
| |
|
static constexpr std::uint8_t | rank_mixed {3} |
| | Accepts, with edges on both sides of the match.
|
| |
|
static constexpr std::size_t | max_nodes {65000} |
| | Node cap, 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} |
| | Moore-refinement dedup buckets; sizing only (a collision costs a comparison).
|
| |
| 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 std::uint32_t | ranked (std::uint32_t node) const |
| | A node id with its accept_rank in the top byte, as onepass_step::target holds it.
|
| |
|
REAL_BUILD_COLD constexpr void | minimize () |
| | Moore partition refinement: merges nodes with the same accept, match masks and, per byte-class, the same edge (target partition and masks). The graph has cycles (\w+), so bottom-up hash-consing is not enough; refinement runs to a fixpoint. Merged nodes share their masks by construction, and each keeps a dense edge row.
|
| |
| 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::vector< onepass_step > | steps_ |
| | nodes_' edges in one array, row by row: what extract walks.
|
| |
|
std::uint32_t | start_ {0} |
| | Node 0 packed as onepass_step::target is.
|
| |
|
bool | ends_known_ {true} |
| | No node is rank_mixed, so extract_leftmost applies.
|
| |
|
std::size_t | max_bytes_ {max_table_bytes} |
| | Table-memory cap (a constructor test hook).
|
| |
|
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} |
| | ASCII word-ness for \b \B \< \> edge conditions unless byte_program::unicode_word.
|
| |
|
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: each node walks its epsilon-closure (split, jump, save, assertions) accumulating masks, and each consuming instruction (byte, klass) writes the edge for its byte-classes. A byte-class written twice with different edges, a second reachable match with different captures, or an epsilon cycle (a nullable loop) means not one-pass, and the build bails with a reason. Node, slot, memory and refinement-work caps bound a pathological program.
template<typename OutSlots >
| std::size_t real::detail::onepass::extract_leftmost |
( |
std::string_view |
text, |
|
|
std::size_t |
s, |
|
|
OutSlots & |
out, |
|
|
std::size_t & |
reach |
|
) |
| const |
|
inline |
The leftmost-first match anchored at s, found and captured in one pass: no end needs to be known beforehand, unlike extract.
Each accepting node met is a candidate end. Where its edges outrank the match (rank_continue) the walk goes on and a later end replaces it, as backtracking would; where the match outranks them (rank_match) the walk stops. The groups are those of the last end kept: a slot written past it is discarded.
- Precondition
- ends_known().
- Parameters
-
| [in] | text | The full subject (assertions read around a position). |
| [in] | s | Match start. |
| [out] | out | Capture slots, sized to slot_count, filled on a match. |
| [out] | reach | How far the walk read, the match's end on a match. |
- Returns
- The match's end, or real::npos when none begins at
s.
| 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 pure epsilon, so a jump's node and its target's get identical edges. emit_utf8_trie writes klass then jump(target) per trie edge: without this, the flood copies every shared trie subgraph for minimize to merge back; resolving the chain builds the shared node directly.
Bounded by the code size: on a jump cycle the pc comes back as-is and build_edges bails on it.
- Parameters
-
- Returns
- The resolved pc (
pc itself when it is not a jump, or on running out of steps).
1.9.8