|
| constexpr | reverse_dfa (std::span< const instr > code, std::span< const char_class > classes, std::size_t budget=state_budget, const lazy_byte_alphabet *shared_alpha=nullptr, bool ascii_word=false, bool word_quit=false, std::size_t byte_budget=lazy_dfa_default_byte_budget) |
| | Builds the (initially empty) reverse DFA, transposing the program's edges as it goes.
|
| |
| bool | eligible () const |
| | Whether the program can be represented at all (see compute_eligibility).
|
| |
| std::size_t | bytes () const |
| | Bytes the cached states hold now, as the byte budget counts them.
|
| |
| std::size_t | byte_flushes () const |
| | Flushes over this object's lifetime that the byte budget called, the state budget not reached.
|
| |
| std::size_t | reverse_start (std::string_view text, std::size_t e, std::size_t resume, std::size_t *read=nullptr) |
| | The leftmost start of the match ending at e, not before resume. Scans the text backward from e over the inverted program, keeping the furthest-back position that reaches the program start (reverse-kLongest). Precondition: a match ends at e; eligible programs only.
|
| |
|
|
static constexpr std::uint32_t | dead_state {0} |
| | The empty state: every transition from it stays here.
|
| |
|
static constexpr std::uint32_t | no_transition {0xFFFFFFFFU} |
| | A not-yet-computed cached transition.
|
| |
|
static constexpr std::uint32_t | quit_state {0xFFFFFFFEU} |
| | What resolve() gives when a Unicode word boundary meets a non-ASCII byte; never interned.
|
| |
|
static constexpr std::size_t | quit_pos {npos - 1U} |
| | What reverse_start() gives when its scan quit.
|
| |
|
static constexpr std::size_t | state_budget {65536} |
| | Cached states before a flush; the memory cap is lazy_dfa_byte_budget.
|
| |
|
| constexpr visit_marks & | begin_visit () |
| | Starts a closure computation on this DFA's marks.
|
| |
| std::uint8_t | right_ctx_at (std::string_view text, std::size_t pos) const |
| | The right context of position pos in the whole text.
|
| |
| bool | holds_left (assert_kind kind, std::uint8_t ctx, std::uint16_t key) const |
| | Whether an assertion that looks left holds, given the right context and the key to the left.
|
| |
| constexpr void | rev_closure_look (std::vector< std::int32_t > &set, visit_marks &seen, std::uint8_t ctx, std::uint16_t key) const |
| | rev_closure for a program with position assertions: crossing back over an assertion needs it to hold at this position. One that looks only right is decided by ctx; one that looks left is decided by key when known, and otherwise stays in set as a pending pc that the closure does not cross until resolve reads the byte to the left.
|
| |
| std::uint32_t | resolve (std::uint32_t state, std::uint16_t key) |
| | state with its pending assertions decided by key, the byte to the left (or the start): each that holds lets the closure continue past it. A state with nothing pending is its own resolution. Cached per (state, key).
|
| |
| std::uint32_t | start_for (std::uint8_t ctx) |
| | The state that starts the backward scan at a match end with right context ctx: the backward closure of the forward match there.
|
| |
| std::uint32_t | step_with (std::uint32_t state, std::uint8_t byte, std::uint8_t ctx) |
| | One backward step for a program with assertions, with the right context given rather than read from the byte's class: the step onto the text's last byte, where a newline is final.
|
| |
| std::size_t | reverse_start_look (std::string_view text, std::size_t e, std::size_t resume, std::size_t *read) |
| | reverse_start for a program with position assertions: each position's state is resolved by the byte to its left before the accept test and the step, and the scan begins with the right context the whole text gives the match end.
|
| |
| constexpr void | rev_closure (std::vector< std::int32_t > &set, visit_marks &seen) const |
| | Saturate set with its backward epsilon-closure, then sort it into a canonical key. Unordered by design: the reverse rule is longest, so priority carries no meaning here.
|
| |
| std::uint32_t | step (std::uint32_t state, std::uint8_t byte) |
| | Transition state backward over byte, computing and caching the edge on first use.
|
| |
| bool | consumes (std::int32_t pc, std::uint8_t byte) const |
| | Whether the instruction at pc is a consuming edge that accepts byte.
|
| |
| constexpr std::uint32_t | intern (const std::vector< std::int32_t > &pcs) |
| | Intern a sorted pc-set into a state id (cached), recording whether it reaches the program start.
|
| |
|
constexpr void | flush () |
| | Empty the cache back to the dead + start states (the eviction: bounded memory).
|
| |
|
| static constexpr bool | is_pending (std::int32_t entry) |
| | Whether entry encodes an undecided assertion.
|
| |
| static constexpr bool | looks_left (assert_kind kind) |
| | Whether kind needs the text to the left of the position (so backward it waits for the next byte); an assertion that looks only right is decided by the context.
|
| |
| static constexpr bool | holds_right (assert_kind kind, std::uint8_t ctx) |
| | Whether an assertion that looks only right holds with right context ctx.
|
| |
| static constexpr void | mark_context (std::vector< std::int32_t > &set, std::uint8_t ctx) |
| | Appends ctx to set as a negative sentinel when set holds a pending assertion: the same pcs resolve differently in another context, so the context is part of the state.
|
| |
|
|
std::span< const instr > | code_ |
| | The byte program, owned by the caller.
|
| |
|
std::span< const char_class > | classes_ |
| | Its byte classes, likewise borrowed.
|
| |
|
lazy_byte_alphabet | alpha_ |
| | Byte-to-class map; its count is the row stride.
|
| |
|
bool | eligible_ {false} |
| | dfa_representable's verdict, fixed at construction.
|
| |
|
bool | word_quit_ {false} |
| | Unicode word boundaries carried, quitting next to a non-ASCII byte.
|
| |
|
bool | quit_hit_ {false} |
| | Set by holds_left() inside one resolve(): that resolution is quit_state.
|
| |
|
bool | look_ {false} |
| | The program carries position assertions (the look paths).
|
| |
|
std::array< std::uint8_t, 256 > | class_ctx_ {} |
| | Class -> the right context a byte of it gives (look programs).
|
| |
|
std::array< std::uint32_t, 16 > | starts_ {} |
| | Right context -> start state, per flush (look programs).
|
| |
|
std::int32_t | match_pc_ {-1} |
| | The forward match pc — this pass's start; -1 when absent.
|
| |
|
std::uint32_t | start_state_ {0} |
| | Id of match_pc_'s backward closure, re-interned by each flush.
|
| |
|
std::size_t | budget_ {state_budget} |
| | Cached states tolerated before a flush.
|
| |
|
visit_marks | marks_ {} |
| | The pcs the closure being computed has entered (begin_visit).
|
| |
|
std::size_t | flushes_ {0} |
| | bumped by flush(); step()'s stale-state guard against a mid-call reset.
|
| |
|
std::size_t | byte_budget_ {lazy_dfa_default_byte_budget} |
| | Cached bytes tolerated before a flush.
|
| |
|
std::size_t | bytes_ {0} |
| | Bytes the cached states hold.
|
| |
|
std::size_t | byte_flushes_ {0} |
| | Flushes the byte budget called, the state budget not reached.
|
| |
|
std::vector< std::int32_t > | rev_eps_pool_ |
| | transposed epsilon edges, CSR-packed.
|
| |
|
std::vector< std::uint32_t > | rev_eps_at_ |
| | CSR offsets into rev_eps_pool_, size code+2.
|
| |
|
std::vector< std::int32_t > | rev_consume_pool_ |
| | transposed consuming edges, CSR-packed.
|
| |
|
std::vector< std::uint32_t > | rev_consume_at_ |
| | CSR offsets into rev_consume_pool_.
|
| |
|
std::vector< std::int32_t > | stack_ |
| | The closures' work stack, a member to spare a heap block per call.
|
| |
|
std::vector< std::vector< std::int32_t > > | state_pcs_ |
| | state id -> sorted pc-set.
|
| |
|
std::vector< std::uint32_t > | trans_ |
| | flat [state*stride + class] -> next.
|
| |
|
std::vector< char > | state_has_start_ |
| | state -> reaches the program start (an accept).
|
| |
|
std::vector< std::uint8_t > | state_pending_ |
| | state -> holds a pending assertion (look programs).
|
| |
|
std::vector< std::uint32_t > | res_ |
| | flat [state*(count+1) + key] -> resolved state (look programs).
|
| |
|
pc_set_cache | cache_ |
| | pc-set -> state id, the memo behind intern.
|
| |
The start-finder companion to lazy_dfa. Given a match end, it finds the leftmost start (the design guide §7.6 contract). It runs the inverted program — the forward program's edges transposed, its consuming bytes kept — as a cached DFA over the text scanned right-to-left from the end, recording an accept each time it reaches the original start (reverse-kLongest: the furthest-back accept is the start). It needs no priority ordering — its states are plain unordered (sorted) PC sets and its rule is longest — so it is simpler than the forward pass. Dynamic only.
1.9.8