A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass). More...

#include <lazy_dfa.hpp>

Collaboration diagram for real::detail::lazy_dfa:

Classes
struct	anchored_result
	anchored_end's result: the match end (or real::npos) and how far the walk got. More...

struct	counters
	Cache-behaviour counters, for the policy tests. More...

Public Member Functions
constexpr	lazy_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 byte_mode=true, bool word_quit=false, bool raw_byte_starts=false, std::size_t byte_budget=lazy_dfa_default_byte_budget)
	Builds the (initially empty) lazy DFA over a Pike program.

bool	eligible () const
	Whether the program can be represented at all (see `compute_eligibility`).

std::uint16_t	num_classes () const
	Width of one cached transition row.

std::uint32_t	start_state () const
	The state a scan starts in.

void	begin_scan ()
	Begin a search: clear the per-scan flush counter and the thrash flag. No cache flush: states carry over between searches, which is where the cache pays.

bool	thrashing () const
	Whether this scan stopped paying: its cache filled again before reading quit_bytes_per_state bytes per state (or, for a DFA that may not quit, crossed thrash_flushes flushes).

const counters &	stats () const
	Cache-behaviour counters.

std::size_t	bytes () const
	Bytes the cached states hold now, as the byte budget counts them.

std::size_t	forward_end (std::string_view text, std::size_t start=0)
	The end offset of the leftmost-first match in `text` (`kFirstMatch`), or real::npos.

anchored_result	anchored_end (std::string_view text, std::size_t start)
	The end offset of the leftmost-first match ANCHORED at `start` in `text`, or real::npos.

bool	looks () const
	Whether the program carries position assertions: a caller that confirms a match found here by running the Pike VM over a slice must not cut the slice at the match end, where a `$` or a `\b` would read the cut as the end of the text.

bool	is_match (std::uint32_t state) const
	Whether `state` accepts here (its ordered set contains a `match` PC).

std::uint32_t	step (std::uint32_t state, std::uint8_t byte)
	Transition `state` on `byte` to the next DFA state, computing and caching it on first use.

Static Public Attributes
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 forward_end() gives when its scan quit (see anchored_result::quit).

static constexpr std::uint32_t	no_match_idx {0xFFFFFFFFU}
	A state whose ordered set holds no accept.

static constexpr std::uint32_t	pending_idx {0xFFFFFFFEU}
	A state whose accept waits on a pending assertion: only resolve() decides it.

static constexpr std::size_t	state_budget {65536}
	Cached states before a flush; the memory cap is lazy_dfa_byte_budget.

static constexpr std::size_t	thrash_flushes {2}

static constexpr std::size_t	quit_bytes_per_state {10}

Private Member Functions
constexpr visit_marks &	begin_visit ()
	Starts a closure computation on this DFA's marks.

std::uint32_t	step_seeded (std::uint32_t state, std::uint8_t byte)
	Like step, but appends pc 0's closure at the lowest priority (a fresh thread at every position until a match). Cached in its own pre-match transition table.

std::uint32_t	cut (std::uint32_t state, std::uint32_t m)
	The priority-cut at an accept: intern the prefix of `state's` ordered pc-set before index `m` (dropping the accept and every lower-priority thread).

std::uint32_t	cut_cached (std::uint32_t state)
	The priority-cut of `state` at its own accept, memoized: `cut` is O(state size) and Unicode byte-program states run thousands of pcs wide, so a per-match recompute dominated. Exact, since a state's accept index is fixed.

std::uint16_t	key_at (std::string_view text, std::size_t pos) const
	The key the text gives a pending assertion at `pos:` the class of the byte there, or the end.

bool	holds_ahead (assert_kind kind, std::uint8_t ctx, std::uint16_t key) const
	Whether an assertion that looks right holds, given the position's context and the key ahead.

bool	consumes (std::int32_t pc, std::uint8_t byte) const
	Whether the instruction at `pc` is a consuming edge that accepts `byte`.

constexpr void	close_into (std::int32_t pc, std::vector< std::int32_t > &out, visit_marks &seen) const
	Append the ordered epsilon-closure of `pc` to `out` (split priority; save/jump crossed), collecting the consuming and `match` PCs. Uses `seen` to dedup within this closure.

constexpr std::int32_t	loop_exit_target (const instr &in, const visit_marks &seen) const
	Where a `jump` leads within one step's closure, as in the VM: into a loop head the closure already entered at this position, the loop's exit. An empty iteration ends the loop there, in its priority place, before any branch that would consume.

constexpr void	close_look (std::int32_t pc, std::vector< std::int32_t > &out, visit_marks &seen, std::uint8_t ctx, std::uint16_t key) const
	close_into for a program with position assertions: an assertion that looks left is decided by `ctx`; one that looks right is decided by `key` when it is known, and otherwise waits in `out` as a pending pc, in its priority place, until resolve knows what follows.

constexpr void	close_any (std::int32_t pc, std::vector< std::int32_t > &out, visit_marks &seen, std::uint8_t ctx) const
	The closure a step takes: close_look when the program carries assertions, else close_into (which never reads `ctx`).

constexpr std::uint32_t	intern_any (std::vector< std::int32_t > pcs, std::uint8_t ctx)
	Interns `pcs`; a set holding a pending assertion also holds its context, as a negative sentinel at its end, because the same pcs with another context resolve differently.

std::uint32_t	resolve (std::uint32_t state, std::uint16_t key)
	`state` with its pending assertions decided by `key:` each is replaced, in its priority place, by the closure past it when it holds and by nothing when it does not. A state with nothing pending is its own resolution. Cached per (state, key).

std::uint32_t	start_for (std::uint8_t ctx)
	The start state for a position with context `ctx:` the closure of pc 0 there. Cached per context; a program without assertions has one start whatever the context.

std::uint8_t	ctx_at (std::string_view text, std::size_t pos) const
	The context of position `pos` in `text`.

template<bool Anchored>
std::conditional_t< Anchored, anchored_result, std::size_t >	scan_look (std::string_view text, std::size_t start)
	forward_end and anchored_end for a program with position assertions: the walk runs over the whole text, so `^`, `\b` and `$` see what is there, and a state holding a pending assertion resolves it on the key of what follows.

constexpr std::uint32_t	intern (const std::vector< std::int32_t > &pcs)
	Intern an ordered pc-set into a state id (cached). Flushes the cache when the budget is hit.

constexpr std::uint32_t	intern_fresh (const std::vector< std::int32_t > &pcs)
	Append a new state for `pcs:` its two transition rows, its accept index and its empty cut memo.

constexpr void	flush ()
	Empty the cache back to the dead + start states (the eviction: bounded memory).

Static Private Member Functions
static constexpr bool	opens_on_continuation (std::span< const instr > code, std::span< const char_class > classes)
	Whether a match can open on a UTF-8 continuation byte: a byte or class the start's closure reaches takes one. In text mode such a match may not start inside a code point, and neither the forward scan's seeds nor the reverse walk's start test for that; the VM does (pike_vm::seed_viable).

static constexpr bool	holds_behind (assert_kind kind, std::uint8_t ctx)
	Whether an assertion that looks left holds with context `ctx`.

static constexpr bool	looks_behind_only (assert_kind kind)
	Whether `kind` looks only left, so a closure decides it without the next byte.

static std::int32_t	consumed_width (std::int32_t)
	Instructions a consuming op occupies. Always 1 here: the byte program has no wider op left.

static constexpr bool	starts_inside_code_point (std::string_view text, std::size_t pos)
	Whether `pos` is inside a UTF-8 code point: the byte there is a continuation byte.

template<bool Anchored>
static constexpr std::conditional_t< Anchored, anchored_result, std::size_t >	look_quit (std::size_t pos)
	scan_look's answer when the walk quits.

Private Attributes
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 plus two is the row stride.

bool	eligible_ {false}
	dfa_representable's verdict, fixed at construction.

bool	byte_mode_ {true}
	A match may start at any byte (else only at a code-point start).

bool	word_quit_ {false}
	Unicode word boundaries carried, quitting next to a non-ASCII byte.

bool	may_quit_ {false}
	A scan may quit: on a Unicode word boundary next to non-ASCII, and once its cache thrashes.

bool	quit_hit_ {false}
	Set by holds_ahead() inside one resolve(): that resolution is quit_state.

bool	look_ {false}
	The program carries position assertions (the look paths).

bool	plain_ {false}
	Eligible and without assertions: the scans' one-test common path.

std::array< std::uint8_t, 256 >	class_ctx_ {}
	Class -> the context after one of its bytes (look programs).

std::array< std::uint32_t, 8 >	starts_ {}
	Context -> start state, per flush (look programs).

std::uint32_t	start_state_ {0}
	Id of the closure of pc 0, re-interned by each flush.

std::vector< std::int32_t >	stack_
	close_into's work stack, hoisted: it ran once per pc of the source state.

std::vector< std::vector< std::int32_t > >	state_pcs_
	state id -> ordered pc-set.

std::vector< std::uint32_t >	trans_
	[state + accept_col] accept word, [state + cut_col] memoized cut, [state + trans_col + class] next, unseeded (post-match).

std::vector< std::uint32_t >	trans_seeded_
	The same rows re-seeding (pre-match); its accept word repeats trans_'s, its cut cell is unused.

std::vector< std::uint32_t >	res_
	[state + key] -> resolved state (look programs); a key spans the row's count + 2 cells.

pc_set_cache	cache_
	pc-set -> row index, the memo behind intern.

std::uint32_t	stride_ {2}
	Cells per row, alpha_.count + 2: a state id is its row's offset.

std::size_t	budget_ {state_budget}
	Cached states tolerated before a flush.

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 (pc-sets, rows, hash entries).

counters	stats_ {}
	Live counters, exposed by stats.

std::size_t	epoch_ {0}
	Bumped by every flush and every refused one: a caller's cached ids went stale.

std::size_t	scan_origin_ {0}
	Where the bytes the current scan has read are counted from.

std::size_t	miss_pos_ {0}
	Position of the scan's latest cache miss.

std::size_t	window_bytes_ {0}
	Bytes read since the last flush by scans that have ended.

visit_marks	marks_ {}
	The pcs the closure being computed has entered (begin_visit).

bool	thrashing_ {false}
	Set once this scan stopped paying: a refused flush, or thrash_flushes flushes where it may not quit.

Static Private Attributes
static constexpr std::uint8_t	ctx_start {1}
	The position is the start of the text.

static constexpr std::uint16_t	key_unknown {0xFFFFU}
	Closing inside a step: the next byte is not known yet.

static constexpr std::uint32_t	accept_col {0}
	A row's accept word: the first accept's index, no_match_idx or pending_idx.

static constexpr std::uint32_t	cut_col {1}
	A row's memoized priority cut (no_transition until built).

static constexpr std::uint32_t	trans_col {2}
	A row's first transition; the accept word leads so a wide row keeps it on the first cache line.

Detailed Description

A lazy priority-preserving forward DFA over a Pike program (the kFirstMatch forward pass).

A DFA state is the ordered epsilon-closure of a pc set (the Pike thread list in split priority); step consumes a byte from each pc, re-closes, and interns the ordered result: subset construction, memoized on demand.

The cache is bounded: past its state or byte budget it is flushed and rebuilt. A scan that keeps flushing trips thrashing; a DFA built to quit then reports a quit and its caller finishes that one search on the Pike VM (per scan, never re-attempted per position).

A program with an op the DFA cannot represent (a klass_cp, a lookaround, a possessive loop, a scoped assertion, or a word boundary on code-point word-ness without word_quit) is ineligible; this builds the machinery, it does not decide policy.

Constructor & Destructor Documentation

◆ lazy_dfa()

constexpr real::detail::lazy_dfa::lazy_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	byte_mode = `true`,
		bool	word_quit = `false`,
		bool	raw_byte_starts = `false`,
		std::size_t	byte_budget = `lazy_dfa_default_byte_budget`
	)

inlineexplicitconstexpr

Builds the (initially empty) lazy DFA over a Pike program.

Parameters

[in]	code	The program's instruction stream (must outlive this object — held as a span).
[in]	classes	The program's interned character classes (likewise held as a span).
[in]	budget	Cached states before a flush; defaults to state_budget (smaller: a test hook).
[in]	shared_alpha	The regex's shared alphabet, or null to compute it here (O(256 x classes), so the router passes the shared one).
[in]	ascii_word	Whether word boundaries use ASCII word-ness (bytes mode, `(?a)`): only then does one byte decide them. False declines any word boundary.
[in]	byte_mode	Whether a match may start at any byte. In text mode the scans do not seed at a continuation byte, as the VM does not.
[in]	word_quit	Let a scan quit, and say so, where the DFA cannot answer well: a Unicode word boundary next to a non-ASCII byte, or once the cache thrashes (thrashing). The caller then asks the VM.
[in]	raw_byte_starts	The program was compiled with flags::allow_raw_byte, so a lead opening on a continuation byte is built as any other (pattern_hints::raw_byte_starts).
[in]	byte_budget	Bytes the cached states may hold before a flush; see lazy_dfa_byte_budget.

Member Function Documentation

◆ anchored_end()

anchored_result real::detail::lazy_dfa::anchored_end	(	std::string_view	text,
		std::size_t	start
	)

inline

The end offset of the leftmost-first match ANCHORED at start in text, or real::npos.

The forward_end walk without re-seeding: one thread seeded at start (a prefilter hit), so no reverse pass is needed. No captures. Does not call begin_scan — a caller trying several candidates for one search calls it once before its loop, since a per-candidate reset would mask thrashing.

Cached transitions and cuts are read inline (step / cut_cached only on a miss), so hits do not bump counters::hits.

Parameters

[in]	text	The subject text.
[in]	start	Offset to anchor the match at (must be `<= text.size()`).

Returns: The match end and the position the walk stopped at (anchored_result::scanned_to). On a miss, scanned_to == text.size() means no dead state bounded the reach (.* with no terminator ahead): a caller trying candidate after candidate is then in the O(n^2) regime.

◆ begin_visit()

constexpr visit_marks & real::detail::lazy_dfa::begin_visit ( )

inlineconstexprprivate

Starts a closure computation on this DFA's marks.

Returns: The marks, none entered.

◆ bytes()

std::size_t real::detail::lazy_dfa::bytes ( ) const

inline

Bytes the cached states hold now, as the byte budget counts them.

Returns: The bytes.

◆ close_any()

constexpr void real::detail::lazy_dfa::close_any	(	std::int32_t	pc,
		std::vector< std::int32_t > &	out,
		visit_marks &	seen,
		std::uint8_t	ctx
	)		const

inlineconstexprprivate

The closure a step takes: close_look when the program carries assertions, else close_into (which never reads ctx).

Parameters

[in]	pc	Program counter to close over.
[in,out]	out	Ordered pc-set.
[in,out]	seen	Per-pc visited marks.
[in]	ctx	The context after the byte just consumed.

◆ close_into()

constexpr void real::detail::lazy_dfa::close_into	(	std::int32_t	pc,
		std::vector< std::int32_t > &	out,
		visit_marks &	seen
	)		const

inlineconstexprprivate

Append the ordered epsilon-closure of pc to out (split priority; save/jump crossed), collecting the consuming and match PCs. Uses seen to dedup within this closure.

Parameters

[in]	pc	Program counter to close over.
[in,out]	out	Ordered pc-set the closure is appended to.
[in,out]	seen	Per-pc visited marks, sized to the program, deduping within this closure.

◆ close_look()

constexpr void real::detail::lazy_dfa::close_look	(	std::int32_t	pc,
		std::vector< std::int32_t > &	out,
		visit_marks &	seen,
		std::uint8_t	ctx,
		std::uint16_t	key
	)		const

inlineconstexprprivate

close_into for a program with position assertions: an assertion that looks left is decided by ctx; one that looks right is decided by key when it is known, and otherwise waits in out as a pending pc, in its priority place, until resolve knows what follows.

Parameters

[in]	pc	Program counter to close over.
[in,out]	out	Ordered pc-set the closure is appended to.
[in,out]	seen	Per-pc visited marks.
[in]	ctx	The position's context.
[in]	key	What follows the position, or key_unknown.

◆ consumed_width()

static std::int32_t real::detail::lazy_dfa::consumed_width ( std::int32_t )

inlinestaticprivate

Instructions a consuming op occupies. Always 1 here: the byte program has no wider op left.

Returns: 1.

◆ consumes()

bool real::detail::lazy_dfa::consumes	(	std::int32_t	pc,
		std::uint8_t	byte
	)		const

inlineprivate

Whether the instruction at pc is a consuming edge that accepts byte.

Parameters

[in]	pc	Program counter to test.
[in]	byte	The byte offered to it.

Returns: True for a byte/klass op accepting it; false for any non-consuming op.

◆ ctx_at()

std::uint8_t real::detail::lazy_dfa::ctx_at	(	std::string_view	text,
		std::size_t	pos
	)		const

inlineprivate

The context of position pos in text.

Parameters

[in]	text	The subject.
[in]	pos	The position.

Returns: The start context at 0, else the context after the byte before pos.

◆ cut()

std::uint32_t real::detail::lazy_dfa::cut	(	std::uint32_t	state,
		std::uint32_t	m
	)

inlineprivate

The priority-cut at an accept: intern the prefix of state's ordered pc-set before index m (dropping the accept and every lower-priority thread).

Parameters

[in]	state	The accepting state id.
[in]	m	Index of the accept in that state's ordered pc-set.

Returns: The interned prefix state, or dead_state when the prefix is empty.

◆ cut_cached()

std::uint32_t real::detail::lazy_dfa::cut_cached ( std::uint32_t state )

inlineprivate

The priority-cut of state at its own accept, memoized: cut is O(state size) and Unicode byte-program states run thousands of pcs wide, so a per-match recompute dominated. Exact, since a state's accept index is fixed.

Parameters

[in] state The accepting state id.

Returns: The cut state, memoized after the first call.

◆ eligible()

bool real::detail::lazy_dfa::eligible ( ) const

inline

Whether the program can be represented at all (see compute_eligibility).

Returns: False when the caller must keep the Pike VM.

◆ forward_end()

std::size_t real::detail::lazy_dfa::forward_end	(	std::string_view	text,
		std::size_t	start = `0`
	)

inline

The end offset of the leftmost-first match in text (kFirstMatch), or real::npos.

Seeds a fresh lowest-priority thread at every position until a match, then reports the end of the highest-priority thread reaching match (a lower-priority accept is suppressed while a higher one lives). One left-to-right pass: linear per search. No captures: the windowed Pike pass fills the span and applies the empty-match rule. With assertions the scan runs in the whole text, not a slice, so ^, \b, $ see what is there (scan_look).

Parameters

[in]	text	Subject.
[in]	start	Offset the search starts at (the first seed).

Returns: The match end, as an offset in text, or real::npos when there is none (or the program is ineligible).

◆ holds_ahead()

bool real::detail::lazy_dfa::holds_ahead	(	assert_kind	kind,
		std::uint8_t	ctx,
		std::uint16_t	key
	)		const

inlineprivate

Whether an assertion that looks right holds, given the position's context and the key ahead.

Parameters

[in]	kind	The assertion.
[in]	ctx	The position's context.
[in]	key	What follows (key_at).

Returns: True when it holds.

◆ holds_behind()

static constexpr bool real::detail::lazy_dfa::holds_behind	(	assert_kind	kind,
		std::uint8_t	ctx
	)

inlinestaticconstexprprivate

Whether an assertion that looks left holds with context ctx.

Parameters

[in]	kind	The assertion.
[in]	ctx	The position's context.

Returns: True when it holds; always false for an assertion that also looks right (it waits instead).

◆ intern()

constexpr std::uint32_t real::detail::lazy_dfa::intern ( const std::vector< std::int32_t > & pcs )

inlineconstexprprivate

Intern an ordered pc-set into a state id (cached). Flushes the cache when the budget is hit.

Parameters

[in] pcs The ordered pc-set.

Returns: Its state id, existing or freshly built; dead_state for an empty set. A flush here invalidates every id the caller holds.

◆ intern_any()

constexpr std::uint32_t real::detail::lazy_dfa::intern_any	(	std::vector< std::int32_t >	pcs,
		std::uint8_t	ctx
	)

inlineconstexprprivate

Interns pcs; a set holding a pending assertion also holds its context, as a negative sentinel at its end, because the same pcs with another context resolve differently.

Parameters

[in]	pcs	The ordered pc-set.
[in]	ctx	Its position's context.

Returns: The state id.

◆ intern_fresh()

constexpr std::uint32_t real::detail::lazy_dfa::intern_fresh ( const std::vector< std::int32_t > & pcs )

inlineconstexprprivate

Append a new state for pcs: its two transition rows, its accept index and its empty cut memo.

Parameters

[in] pcs The ordered pc-set, known not to be interned yet.

Returns: The new state's id.

◆ is_match()

bool real::detail::lazy_dfa::is_match ( std::uint32_t state ) const

inline

Whether state accepts here (its ordered set contains a match PC).

Parameters

[in] state The state id to test.

Returns: True when the state holds an accept.

◆ key_at()

std::uint16_t real::detail::lazy_dfa::key_at	(	std::string_view	text,
		std::size_t	pos
	)		const

inlineprivate

The key the text gives a pending assertion at pos: the class of the byte there, or the end.

Parameters

[in]	text	The subject.
[in]	pos	The position.

Returns: The resolution key.

◆ look_quit()

template<bool Anchored>

static constexpr std::conditional_t< Anchored, anchored_result, std::size_t > real::detail::lazy_dfa::look_quit ( std::size_t pos )

inlinestaticconstexprprivate

scan_look's answer when the walk quits.

Template Parameters

Anchored Which walk quit.

Parameters

[in] pos Where it stopped.

Returns: The quit result in that walk's form.

◆ looks()

bool real::detail::lazy_dfa::looks ( ) const

inline

Whether the program carries position assertions: a caller that confirms a match found here by running the Pike VM over a slice must not cut the slice at the match end, where a $ or a \b would read the cut as the end of the text.

Returns: True when it does.

◆ looks_behind_only()

static constexpr bool real::detail::lazy_dfa::looks_behind_only ( assert_kind kind )

inlinestaticconstexprprivate

Whether kind looks only left, so a closure decides it without the next byte.

Parameters

[in] kind The assertion.

Returns: True for \A, ^.

◆ loop_exit_target()

constexpr std::int32_t real::detail::lazy_dfa::loop_exit_target	(	const instr &	in,
		const visit_marks &	seen
	)		const

inlineconstexprprivate

Where a jump leads within one step's closure, as in the VM: into a loop head the closure already entered at this position, the loop's exit. An empty iteration ends the loop there, in its priority place, before any branch that would consume.

Parameters

[in]	in	The `jump`.
[in]	seen	This step's visited marks.

Returns: The pc to continue at.

◆ num_classes()

std::uint16_t real::detail::lazy_dfa::num_classes ( ) const

inline

Width of one cached transition row.

Returns: The byte alphabet's class count.

◆ opens_on_continuation()

static constexpr bool real::detail::lazy_dfa::opens_on_continuation	(	std::span< const instr >	code,
		std::span< const char_class >	classes
	)

inlinestaticconstexprprivate

Whether a match can open on a UTF-8 continuation byte: a byte or class the start's closure reaches takes one. In text mode such a match may not start inside a code point, and neither the forward scan's seeds nor the reverse walk's start test for that; the VM does (pike_vm::seed_viable).

Parameters

[in]	code	The program's instruction stream.
[in]	classes	Its classes.

Returns: True when some first byte is 10xxxxxx.

◆ resolve()

std::uint32_t real::detail::lazy_dfa::resolve	(	std::uint32_t	state,
		std::uint16_t	key
	)

inlineprivate

state with its pending assertions decided by key: each is replaced, in its priority place, by the closure past it when it holds and by nothing when it does not. A state with nothing pending is its own resolution. Cached per (state, key).

Parameters

[in]	state	The state.
[in]	key	What follows its position (key_at).

Returns: The resolved state, which holds no pending assertion.

◆ scan_look()

template<bool Anchored>

std::conditional_t< Anchored, anchored_result, std::size_t > real::detail::lazy_dfa::scan_look	(	std::string_view	text,
		std::size_t	start
	)

inlineprivate

forward_end and anchored_end for a program with position assertions: the walk runs over the whole text, so ^, \b and $ see what is there, and a state holding a pending assertion resolves it on the key of what follows.

Template Parameters

Anchored One thread seeded at start (anchored_end). Otherwise every position up to the first match seeds a thread (forward_end), and a dead state before a match does not end the walk: an assertion can kill every thread at one position and let the next seed live (^ after a newline).

Parameters

[in]	text	Subject.
[in]	start	The anchor, or the first seed's position.

Returns: Anchored, the match end and how far the walk got (anchored_result::quit when a Unicode boundary met a non-ASCII byte or the cache thrashed); otherwise the match end, real::npos or quit_pos.

◆ start_for()

std::uint32_t real::detail::lazy_dfa::start_for ( std::uint8_t ctx )

inlineprivate

The start state for a position with context ctx: the closure of pc 0 there. Cached per context; a program without assertions has one start whatever the context.

Parameters

[in] ctx The start position's context.

Returns: Its state id.

◆ start_state()

std::uint32_t real::detail::lazy_dfa::start_state ( ) const

inline

The state a scan starts in.

Returns: The start state's id (1; 0 is dead_state).

◆ starts_inside_code_point()

static constexpr bool real::detail::lazy_dfa::starts_inside_code_point	(	std::string_view	text,
		std::size_t	pos
	)

inlinestaticconstexprprivate

Whether pos is inside a UTF-8 code point: the byte there is a continuation byte.

Parameters

[in]	text	The subject.
[in]	pos	The position.

Returns: True inside a code point; false at the end or at a code point's first byte.

◆ stats()

const counters & real::detail::lazy_dfa::stats ( ) const

inline

Cache-behaviour counters.

Returns: A reference to the live counters, valid for this object's lifetime.

◆ step()

std::uint32_t real::detail::lazy_dfa::step	(	std::uint32_t	state,
		std::uint8_t	byte
	)

inline

Transition state on byte to the next DFA state, computing and caching it on first use.

Parameters

[in]	state	The current state id.
[in]	byte	The byte consumed.

Returns: The successor state, or dead_state when no thread survives the byte. On a flush mid-step the id is a fresh post-flush one and the caller's state is stale.

◆ step_seeded()

std::uint32_t real::detail::lazy_dfa::step_seeded	(	std::uint32_t	state,
		std::uint8_t	byte
	)

inlineprivate

Like step, but appends pc 0's closure at the lowest priority (a fresh thread at every position until a match). Cached in its own pre-match transition table.

Parameters

[in]	state	The current state id.
[in]	byte	The byte consumed.

Returns: The successor state, with a fresh thread appended at the lowest priority.

◆ thrashing()

bool real::detail::lazy_dfa::thrashing ( ) const

inline

Whether this scan stopped paying: its cache filled again before reading quit_bytes_per_state bytes per state (or, for a DFA that may not quit, crossed thrash_flushes flushes).

Returns: True once the caller should abandon the DFA and finish the search on the Pike VM.

Member Data Documentation

◆ quit_bytes_per_state

constexpr std::size_t real::detail::lazy_dfa::quit_bytes_per_state {10}

staticconstexpr

Bytes read per cached state below which a DFA that may quit refuses its next flush and quits: a cache refilled faster than that costs more to rebuild than the VM costs to scan.

◆ thrash_flushes

constexpr std::size_t real::detail::lazy_dfa::thrash_flushes {2}

staticconstexpr

Flushes within one scan that trip thrashing, where the scan may not quit.

The documentation for this class was generated from the following file:

include/real/automata/lazy_dfa.hpp

Classes

Public Member Functions

Static Public Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ lazy_dfa()

Member Function Documentation

◆ anchored_end()

◆ begin_visit()

◆ bytes()

◆ close_any()

◆ close_into()

◆ close_look()

◆ consumed_width()

◆ consumes()

◆ ctx_at()

◆ cut()

◆ cut_cached()

◆ eligible()

◆ forward_end()

◆ holds_ahead()

◆ holds_behind()

◆ intern()

◆ intern_any()

◆ intern_fresh()

◆ is_match()

◆ key_at()

◆ look_quit()

◆ looks()

◆ looks_behind_only()

◆ loop_exit_target()

◆ num_classes()

◆ opens_on_continuation()

◆ resolve()

◆ scan_look()

◆ start_for()

◆ start_state()

◆ starts_inside_code_point()

◆ stats()

◆ step()

◆ step_seeded()

◆ thrashing()

Member Data Documentation

◆ quit_bytes_per_state

◆ thrash_flushes