real::detail::pattern_hints Struct Reference

Search-acceleration hints extracted from a compiled program by analyze_program (prefilter.hpp). They change how fast, never what matches. More...

Collaboration diagram for real::detail::pattern_hints:

Public Attributes
std::array< char, 16 >	prefix {}
	Required literal prefix (possibly truncated).
std::uint8_t	prefix_size {}
	Valid bytes in prefix.
bool	anchored_start {}
	\A / ^ (no multiline): only position 0.
std::uint8_t	line_anchored {}
	^ multiline: 0 none, 1 position 0 or after \n, 2 also after \r (ecma).
bool	first_bytes_valid {}
	False when an empty match is possible.
bool	empty_match_possible {}
	The pattern can match the empty string. Conservative: assertions count as nullable, so ^$ is flagged.
bool	nullable_captured_repeat {}
	A capturing group with a nullable body sits under a quantifier ((ab|)+a); set from the AST (compiler.hpp). REAL captures the last consuming iteration, an ECMAScript backtracker an extra empty one, so real::compat sends replace/iterate to std (real::compat::basic_regex::uses_real_traversal). Over-approximating is safe.
std::int16_t	single_first {-1}
	The unique possible first byte, or -1.
char_class	first_bytes
	All possible first bytes.
std::int32_t	greedy_class_loop {-1}
std::uint8_t	greedy_class_loop_end {}
	Trailing end anchor on greedy_class_loop — 0 none, 1 \Z, 2 $ (also before one final newline). The route walks the run BACKWARD from that limit instead of scanning and retrying.
std::uint16_t	greedy_class_loop_min {1}
	Minimum run length (bytes) for greedy_class_loop — 1 for X+, k for X{k,}.
std::int32_t	greedy_cp_class {-1}
	cp_class index if the whole pattern is a code-point class klass_cp (optionally +), else -1.
bool	greedy_cp_class_plus {}
std::uint8_t	greedy_cp_class_end {}
	Trailing end anchor on greedy_cp_class, encoded as greedy_class_loop_end.
std::uint16_t	greedy_cp_class_min {1}
	Minimum run length in CODE POINTS for greedy_cp_class (with greedy_cp_class_plus).
std::int16_t	greedy_group_start {-1}
	For a class loop wrapped in one capturing group ((\w+)): the group's start slot, mirroring the match start (-1 = none).
std::int16_t	greedy_group_end {-1}
	The enveloping group's end slot (mirrors the whole-match end).
bool	fixed_shape {}
	Whole pattern is a fixed-width byte/klass sequence (no branches/asserts/captures).
std::int32_t	codepoint_class_ascii {-1}
	ASCII-class index when the whole pattern is ./negated-class (optionally +), else -1.
bool	codepoint_class_plus {}
	The codepoint_class_ascii pattern is a greedy + loop (vs a single codepoint).
bool	fixed_alternation {}
	Whole pattern is an alternation of straight-line branches (no captures/asserts).
std::uint8_t	exact_literal_len {}
	Length of the pure-literal match, or 0.
std::array< char, 6 >	stop_set {}
	For a whole-pattern class+ whose accepted set has a complement of <= 6 bytes: those STOP bytes, driving the run scan. Kept out of the hot prefix (see the layout note).
std::uint8_t	stop_set_size {}
	Members in stop_set — 0 when the complement is too large, else 1..6.
std::array< char, 8 >	small_set {}
	The 2..8 possible first bytes, for the alternation route's masked block scan. In the cold tail: next to first_bytes it moved the greedy_class_loop* fields across a cache line.
std::uint8_t	small_set_size {}
	Members in small_set — 0 when not a small set, else 2..8.
std::int16_t	rare_byte {-1}
	A required byte at a fixed offset from the match start, rarer than the first-byte set (the date - at offset 4): the search memchrs it and back-verifies from found - rare_offset. -1 when none.
std::uint16_t	rare_offset {}
std::int16_t	rare_disc {-1}
	Rare discriminant with an optional byte before it (URL https?://…): memchr(rare_disc), then back-verify [prefix][opt?][disc][after]. Chosen over a weak literal prefix (http) when rarer. Unlike rare_byte its offset is not fixed when rare_disc_opt is set (s? puts the colon at 4 or 5). -1 = unarmed.
std::array< char, 8 >	rare_disc_prefix {}
	Required bytes before the optional (e.g. http).
std::uint8_t	rare_disc_prefix_len {}
	Length of rare_disc_prefix.
std::int16_t	rare_disc_opt {-1}
	Optional mono-byte before the disc (s), or -1.
std::array< char, 4 >	rare_disc_after {}
	Fixed bytes after the disc (e.g. //).
std::uint8_t	rare_disc_after_len {}
	Length of rare_disc_after.
std::array< std::uint8_t, 16 >	inner_literal {}
	A required inner literal every match contains (the inner-literal prefilter's candidate), and how many top-level children precede it (the prefix reverse-matched back to the match start). Raw bytes, so this core type need not know the frontend literal type.
std::uint8_t	inner_literal_len {}
	Bytes held in inner_literal; 0 means the pattern has no required inner literal.
std::int32_t	inner_literal_prefix {-1}
	Top-level children before the literal; 0 = at the head, -1 = nested with no clean boundary.
bool	capture_free_walk {false}
	Every save in this program writes slot 0 or slot 1, so a thread's whole capture state is the group-0 START.
std::uint8_t	fixed_shape_lo0 {}
	For a HOMOGENEOUS fixed_shape (every position accepts the same set of <= 2 ranges: [0-9a-f]{8}, \d{4}): the ranges and run length for the SIMD scan+verify in run_fixed_shape.
std::uint8_t	fixed_shape_hi0 {}
	First range's high byte.
std::uint8_t	fixed_shape_lo1 {1}
	lo1 > hi1 (default 1 > 0) encodes "no second range".
std::uint8_t	fixed_shape_hi1 {}
	Second range's high byte, when one is present.
std::uint8_t	fixed_shape_simd_len {}
	The run length (1..16) when eligible, else 0.
std::uint8_t	fs_end_anchor {}
	A fixed_shape whose trailing end anchor was peeled: 0 none, 1 \Z, 2 $ (also before ONE final newline, which is why ^X$ is not fullmatch(X)). Set only with anchored_start — one candidate position, so a failed end test owes no retry. $ without ^ stays on the VM.
std::uint8_t	bounded_backtrack {}
	Nonzero when the general loop may answer a small subject by bounded backtracking (pike_vm::run_bounded_backtrack): no lookaround, at most bounded_backtrack_max_slots slots; the subject budget is checked per search. A hint, not a runtime test, so blanking the hints (how differentials reach the plain Pike VM) also disables it.
std::int16_t	trailing_lookaround {-1}
	Trailing lookaround on a groupless greedy class+ ([a-z]+(?=[a-z])): index into lookarounds, -1 = not this shape. Leaves greedy_class_loop at -1 on purpose: sharing that selector makes every class+ search branch on this shape.
bool	trailing_la_cp {}
	The trailing_lookaround body is a klass_cp (cp_classes index).
std::int32_t	trailing_la_class {-1}
	Class index for trailing_lookaround body; −1 if unset.
std::array< char, 8 >	possessive_prefix {}
	Possessive fast path, UNBOUNDED loops only (X*+/X++) with min 0 or 1: a bounded count ((a){2,4}+b) lacks the "every start in the run reaches the same body end" invariant that makes a skip-based search linear. A non-empty possessive_prefix also needs the loop class to exclude the prefix's and suffix's leading bytes, or the delimited runner's retry is quadratic (id=[a-z0-9]*+; stays on the general VM).
std::uint8_t	possessive_prefix_size {}
	Meaningful bytes of possessive_prefix; 0 selects the bare/suffixed shape, non-zero the delimited one.
std::array< char, 8 >	possessive_suffix {}
	Required literal AFTER the loop (0 len = none; e.g. the 'x' in \d++x).
std::uint8_t	possessive_suffix_size {}
	Meaningful bytes of possessive_suffix; 0 means the loop has no required suffix.
class_ref	possessive_class {}
	The loop body's class, typed by opcode.
std::int16_t	possessive_group_start {-1}
	Enveloping single capture group's start slot (mirrors greedy_group_start), -1 = none.
std::int16_t	possessive_group_end {-1}
	The enveloping group's end slot.
bool	possessive_min_nonzero {}
	True for X++ (one mandatory copy): a candidate MUST be in-class; false for X*+, where an empty body is a candidate anywhere.
std::uint8_t	wb_lead {}
	Optional word-boundary wrap on fixed_shape / fixed_alternation / exact_literal, checked in O(1) at the match start/end once the body route accepts a candidate.
std::uint8_t	wb_trail {}
bool	wb_lead_maximal_run {}
	A leading \b was dropped by the DROP rule (resolve_class_wb_hints): a maximal run starts only after a non-word character, assuming "no preceding character" means the text start. A caller's search(text, pos) with pos > 0 breaks that (pos is no virtual start for \b, as in Python; endpos is a virtual end, so only the lead side needs this): a runner whose first candidate is start itself must check assertion_holds there.
std::uint8_t	body_pc {1}
	First consuming (byte/klass) or branch pc for fixed_shape / alternation after save 0 and an optional lead \b/\B. Default 1 (no lead wrap).
std::uint16_t	alternation_branch_count {}
	Branch count for fixed_alternation (0 when unset); the alternation route picks Aho-Corasick past a threshold. Appended last: earlier, it reflows wb_lead and body_pc (read per match), and after small_set_size it grows the struct.
std::uint8_t	inner_literal_prefix_skip {}
	Leading top-level children peeled before the IL reverse prefix (the \b of \b\w+@\w+\b): build_prefix_ast skips these, then takes inner_literal_prefix children.
bool	literal_one_search {}
	One find_prefix answers the whole exact-literal search; run_exact_literal's per-match steps are redundant for this program.
std::uint8_t	fs_pair_width {}
	HETEROGENEOUS fixed-shape pair filter ((?i)cafe, \w\d\w\d): two positions, each with its own <= 2-range set, reject 16 candidate starts per vector compare.
std::uint8_t	fs_pair_off_a {}
	Offset of the first probed position within the shape.
std::uint8_t	fs_pair_off_b {}
	Offset of the second probed position.
std::uint8_t	fs_pair_a_lo0 {}
	Position A, first range's low byte.
std::uint8_t	fs_pair_a_hi0 {}
	Position A, first range's high byte.
std::uint8_t	fs_pair_a_lo1 {1}
	Position A, second range's low byte; lo1 > hi1 encodes "no second range".
std::uint8_t	fs_pair_a_hi1 {}
	Position A, second range's high byte.
std::uint8_t	fs_pair_b_lo0 {}
	Position B, first range's low byte.
std::uint8_t	fs_pair_b_hi0 {}
	Position B, first range's high byte.
std::uint8_t	fs_pair_b_lo1 {1}
	Position B, second range's low byte; same "no second range" convention.
std::uint8_t	fs_pair_b_hi1 {}
	Position B, second range's high byte.
std::int32_t	il_rev_class {-1}
	IL reverse-by-class: the inner-literal prefix is one greedy class loop ([a-z]+@…), so a candidate literal at h starts its match where the class run ending at h starts.
bool	il_rev_is_cp {}
std::uint16_t	inner_literal_fold {}
	Bit i: byte i of inner_literal is a lower-case ASCII letter that matches in either case ((?i)x, [xX]); 0 for an exact literal. In the padding before il_fwd_class.
std::int32_t	il_fwd_class {-1}
	IL two-run confirm: the whole pattern is class+ <literal> class+ (groups around either run transparent), so a candidate is confirmed without an engine, every capture slot being one of four positions. For static_regex, which would otherwise confirm on the general VM. -1 when the suffix is not one greedy class loop ending the pattern.
bool	il_fwd_is_cp {}
bool	il_fwd_last {}
	The literal can occur inside the prefix run, so the greedy prefix leaves it at its LAST occurrence before the suffix, not at the candidate: the span is the same, the groups are not.
bool	il_fwd_run_to_end {}
	Both runs are one class, so the last occurrence the prefix run reaches is the last one before the suffix's end: the fill need not walk the prefix run past the literal.
bool	il_cp_shape_eligible {}
	IL fixed code-point shape: the whole pattern is a fixed sequence of code-point atoms and literal bytes (\d{4}-\d{2}-\d{2}), no loop. Not byte-fixed (a Unicode \d is multi-byte), but the code-point count is: step il_cp_prefix_cps code points back from the literal, then one forward walk verifies and fills every capture.
std::uint8_t	il_cp_prefix_cps {}
	Code points before the literal in il_cp_shape_eligible.
std::uint16_t	greedy_cp_class_max {}
	Upper bound, in code points, on greedy_cp_class's run, or 0 for unbounded (\w+, \w{8,}). \w{8} sets 8: the run must stop from above (\w{8} over a nine-letter word matches eight).
std::int32_t	single_class {-1}
	Class index when the whole pattern is a bare single byte-class ([a-z]; exactly save 0, klass, save 1, match), else -1.
std::uint8_t	prefix_rare {}
	Offset of the rarest byte of prefix (by byte_frequency), the byte the literal search scans first (find_literal_adaptive). Meaningful when prefix_size >= 2.
std::uint8_t	inner_literal_rare {}
	Offset of the rarest byte of inner_literal, as prefix_rare. Meaningful when inner_literal_len >= 2.
bool	raw_byte_starts {}
	Compiled with flags::allow_raw_byte, so a lead opening on a UTF-8 continuation byte (RE2's \C) keeps its routes and lazy DFA, matches starting inside a code point as RE2's do. In text mode otherwise such a lead is left to the VM. Fits the trailing padding.

Detailed Description

Search-acceleration hints extracted from a compiled program by analyze_program (prefilter.hpp). They change how fast, never what matches.

Note

The field order is load-bearing. Offsets 0..86 are the hot prefix every search reads (prefix, first_bytes, the greedy_* selectors, fixed_shape, fixed_alternation); the tail is per-route. Append new fields at the END: an insertion reflows every later field and can move hot fields across a cache line, charging patterns that read none of it. Do not split into hot and cold structs: an indirection to the tail would charge every route that reads it.

Member Data Documentation

capture_free_walk

bool real::detail::pattern_hints::capture_free_walk {false}

Every save in this program writes slot 0 or slot 1, so a thread's whole capture state is the group-0 START.

Derived by scanning the code, so it holds for any producer. The epsilon walk then carries no capture block: with save 0 at pc 0, every thread one add_thread call adds shares one start. A save 0 behind a split would hand one branch its sibling's start, a wrong answer.

exact_literal_len

std::uint8_t real::detail::pattern_hints::exact_literal_len {}

Length of the pure-literal match, or 0.

Non-zero when the prefix bytes are the whole match (group saves allowed, no branch or other consuming op), so a match is replayed without the Pike VM.

fixed_shape_lo0

std::uint8_t real::detail::pattern_hints::fixed_shape_lo0 {}

For a HOMOGENEOUS fixed_shape (every position accepts the same set of <= 2 ranges: [0-9a-f]{8}, \d{4}): the ranges and run length for the SIMD scan+verify in run_fixed_shape.

First range's low byte.

fs_pair_width

std::uint8_t real::detail::pattern_hints::fs_pair_width {}

HETEROGENEOUS fixed-shape pair filter ((?i)cafe, \w\d\w\d): two positions, each with its own <= 2-range set, reject 16 candidate starts per vector compare.

A prefilter: the per-position walk then confirms. The pair is the two most selective positions (ties toward the widest separation). Set only when fixed_shape_simd_len is 0, the width is 2..16, and every position has 1..2 ranges. lo1 > hi1 means "no second range". The shape's byte width (2..16); 0 when the pair filter is ineligible.

greedy_class_loop

std::int32_t real::detail::pattern_hints::greedy_class_loop {-1}

Class index if the whole pattern is "class+", else -1.

greedy_cp_class_plus

bool real::detail::pattern_hints::greedy_cp_class_plus {}

The greedy_cp_class pattern is a greedy + loop (vs a single code point).

il_fwd_is_cp

bool real::detail::pattern_hints::il_fwd_is_cp {}

il_fwd_class indexes cp_classes rather than classes.

il_rev_class

std::int32_t real::detail::pattern_hints::il_rev_class {-1}

IL reverse-by-class: the inner-literal prefix is one greedy class loop ([a-z]+@…), so a candidate literal at h starts its match where the class run ending at h starts.

No sub-program, DFA or allocation, so static_regex (no immutables) runs it; confirm_at verifies forward, so a rejected candidate costs an advance, never a wrong match. -1 otherwise (a fixed count, \d{4}-…, has no split and stays general).

il_rev_is_cp

bool real::detail::pattern_hints::il_rev_is_cp {}

il_rev_class indexes cp_classes (a klass_cp loop) rather than classes.

inner_literal

std::array<std::uint8_t, 16> real::detail::pattern_hints::inner_literal {}

A required inner literal every match contains (the inner-literal prefilter's candidate), and how many top-level children precede it (the prefix reverse-matched back to the match start). Raw bytes, so this core type need not know the frontend literal type.

The literal's bytes, the first inner_literal_len of which are meaningful.

literal_one_search

bool real::detail::pattern_hints::literal_one_search {}

One find_prefix answers the whole exact-literal search; run_exact_literal's per-match steps are redundant for this program.

Set when ALL hold: exact_literal_len >= 2 (one byte goes through find_byte); prefix_size == exact_literal_len (so literal_at's re-compare is redundant); no assert_position in code (\bdog, ^dog need a check per occurrence); none of anchored_start, line_anchored, rare_disc armed (each takes an earlier branch in next_candidate). Program-only terms, folded once rather than evaluated per match; the caller adds slot_count == 2. Assertion-freeness is read from code, never inferred from wb_lead or the anchors: an assert kind they do not represent would make that unsound.

possessive_prefix

std::array<char, 8> real::detail::pattern_hints::possessive_prefix {}

Possessive fast path, UNBOUNDED loops only (X*+/X++) with min 0 or 1: a bounded count ((a){2,4}+b) lacks the "every start in the run reaches the same body end" invariant that makes a skip-based search linear. A non-empty possessive_prefix also needs the loop class to exclude the prefix's and suffix's leading bytes, or the delimited runner's retry is quadratic (id=[a-z0-9]*+; stays on the general VM).

Required literal BEFORE the loop (0 len = none; the delimited/"quoted" shape).

rare_disc

std::int16_t real::detail::pattern_hints::rare_disc {-1}

Rare discriminant with an optional byte before it (URL https?://…): memchr(rare_disc), then back-verify [prefix][opt?][disc][after]. Chosen over a weak literal prefix (http) when rarer. Unlike rare_byte its offset is not fixed when rare_disc_opt is set (s? puts the colon at 4 or 5). -1 = unarmed.

Discriminant byte (e.g. :).

rare_offset

std::uint16_t real::detail::pattern_hints::rare_offset {}

The fixed byte offset of rare_byte from the match start; 16 bits sit in the padding before rare_disc.

single_class

std::int32_t real::detail::pattern_hints::single_class {-1}

Class index when the whole pattern is a bare single byte-class ([a-z]; exactly save 0, klass, save 1, match), else -1.

Without it the form matched no batchable selector and paid a route entry per match. A flag on greedy_class_loop would make every class+ site branch on it (as trailing_lookaround). A literal byte takes exact_literal instead.

wb_lead

std::uint8_t real::detail::pattern_hints::wb_lead {}

Optional word-boundary wrap on fixed_shape / fixed_alternation / exact_literal, checked in O(1) at the match start/end once the body route accepts a candidate.

Leading wrap: 0 none, 1 \b, 2 \B — asserted at the match start.

wb_trail

std::uint8_t real::detail::pattern_hints::wb_trail {}

Trailing wrap, same encoding as wb_lead — asserted at the match end.

---

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

• include/real/core/program.hpp