prefilter.hpp File Reference

Search acceleration: pattern analysis and candidate-finding. More...

#include "real/version.hpp"
#include "real/core/config.hpp"
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <limits>
#include <span>
#include <string_view>
#include <type_traits>
#include <vector>
#include "real/core/charclass.hpp"
#include "real/core/program.hpp"
#include "real/engine/simd.hpp"
#include "real/unicode/unicode_props.hpp"
#include <array>
#include <atomic>

Include dependency graph for prefilter.hpp:

Classes
struct	real::detail::shape_lead
	A fixed shape's lead: save 0, an optional \A/^, an optional \b/\B. More...
struct	real::detail::shape_close
	The shape_lead counterpart: optional trail \b/\B, optional \Z/$, then exactly save 1, match ending the program. More...
struct	real::detail::literal_density
	What the adaptive literal search learned about one subject: whether the needle's rarest byte is common there. More...
struct	real::detail::literal_memo
	The two literal densities of one subject, held in a std::optional built at the first literal search, so constructing a search state (every search does) writes no densities. More...
struct	real::detail::alternation_pairs
	Two probe bytes per branch of a literal alternation: the branch's first byte and one byte further in it, for the pair filter an alternation's block scan turns to once the first bytes prove common. More...
struct	real::detail::alternation_density
	Whether an alternation's first bytes are dense in one subject, decided once from a sample of it. More...

Namespaces
namespace	real
	REAL's public API: real::regex, real::static_regex, real::flags and the match/iterator types built on them.
namespace	real::detail
	DFA construction internals: subset construction over a flattened NFA. Not a stable API.

Enumerations
enum class	real::detail::counter : std::uint8_t {   real::detail::prefilter_work_units , real::detail::vm_window_runs , real::detail::batch_fills , real::detail::inner_literal_bill_trips ,   real::detail::inner_literal_reverse_bytes , real::detail::inner_literal_confirm_bytes , real::detail::byte_program_builds , real::detail::il_prefix_run_walks ,   real::detail::batch_handouts , real::detail::vm_reseeds , real::detail::onepass_anchored_walks , real::detail::bounded_backtrack_runs ,   real::detail::dfa_quits , real::detail::literal_pair_scans , real::detail::alternation_avx2_blocks , real::detail::literal_avx2_scans ,   real::detail::fixed_shape_batches , real::detail::literal_rest_scans , real::detail::alternation_pair_blocks , real::detail::alternation_nibble_blocks ,   real::detail::ac_completion_walks , real::detail::alternation_variant_scans , real::detail::alternation_wide_scans , real::detail::alternation_pair_candidates ,   real::detail::ahead_table_rows , real::detail::behind_walk_steps , real::detail::behind_atom_steps , real::detail::dfa_span_batches ,   real::detail::dfa_leases_taken , real::detail::class_folds , real::detail::count_ }
	Test counters, one per mechanism, for the tests that pin when it runs. Billed through note() only under REAL_TEST_INSTRUMENT (free in production); process-wide relaxed atomics. More...

Functions
std::atomic< std::uint64_t > &	real::detail::tally (counter c) noexcept
	The value of a test counter, to read or to reset.
constexpr void	real::detail::note (counter c, std::uint64_t n=1) noexcept
	Bills n to a test counter. A no-op unless the test binary defines REAL_TEST_INSTRUMENT.
bool &	real::detail::alternation_avx2_disabled ()
	Test seam: keep the alternation fingerprint on 16-byte blocks where the CPU has AVX2, so a differential can compare both widths in one binary. Not for production use.
bool &	real::detail::literal_avx2_disabled ()
	Test seam: keep the literal filter on 16-byte blocks where the CPU has AVX2, so a differential can compare both widths in one binary. Not for production use.
constexpr bool	real::detail::is_word_boundary_kind (assert_kind kind) noexcept
	True if kind is \b or \B (the only position asserts a fast path wraps).
constexpr std::uint8_t	real::detail::wb_hint_of (assert_kind kind) noexcept
	Encodes kind as a wb_lead/wb_trail hint value (1 = \b, 2 = \B); 0 if not a word boundary.
constexpr bool	real::detail::peel_optional_wb (std::span< const instr > code, std::size_t &p, std::uint8_t &hint) noexcept
	Peels an optional \b/\B assertion at p, lead or trail alike.
constexpr shape_lead	real::detail::parse_shape_lead (std::span< const instr > code) noexcept
	Peels a fixed shape's save 0 and its optional lead \b/\B.
constexpr shape_close	real::detail::parse_shape_close (std::span< const instr > code, std::size_t from) noexcept
	Peels a fixed shape's optional trail \b/\B, then its save 1 and match.
constexpr bool	real::detail::is_full_ascii_word_class (const char_class &cls) noexcept
	True if cls is exactly the ASCII word set [0-9A-Za-z_] (\w under bytes/re.A).
constexpr bool	real::detail::is_ascii_word_subset_class (const char_class &cls) noexcept
	True if every member of cls is an ASCII word byte (subset of \w under bytes/re.A).
constexpr bool	real::detail::is_full_unicode_word_cp_class (const cp_class &cc, std::span< const code_range > all_ranges) noexcept
	True if cc is exactly the canonical Unicode \w class (not a user superset).
constexpr bool	real::detail::wb_redundant_for_full_word (std::uint8_t lead, std::uint8_t trail) noexcept
	The DROP rule: \b next to a full-\w maximal run is redundant (\B never is).
constexpr bool	real::detail::resolve_class_wb_hints (bool full_word, bool word_sub, bool maximal_run, std::uint8_t lead, std::uint8_t trail, std::uint8_t &out_lead, std::uint8_t &out_trail) noexcept
	DROP / WRAP policy for class / cp-class loops under optional \b/\B wraps.
constexpr bool	real::detail::word_ranges_cover_interval_from (char32_t lo, char32_t hi, std::size_t &cursor) noexcept
	True if every code point in [lo, hi] is a Unicode word char (word_ranges), resuming the scan at cursor and leaving it past the last range consulted.
constexpr bool	real::detail::word_ranges_cover_interval (char32_t lo, char32_t hi) noexcept
	True if every code point in [lo, hi] is a Unicode word char (covered by word_ranges). Standalone form of word_ranges_cover_interval_from.
constexpr bool	real::detail::is_unicode_word_subset_cp_class (const cp_class &cc, std::span< const code_range > all_ranges) noexcept
	True if cc is a non-empty subset of Unicode \w (safe for maximal-run + \b wrap).
constexpr bool	real::detail::cp_class_may_contain_ascii_byte (const cp_class &cc, std::uint8_t b) noexcept
	Whether byte b could be a member of cc; a delimiter that could hide in a possessive code-point loop makes the delimited fast path decline (pattern_hints::possessive_prefix).
constexpr bool	real::detail::is_fixed_alternation (std::span< const instr > code, std::uint8_t *out_wb_lead=nullptr, std::uint8_t *out_wb_trail=nullptr, std::uint8_t *out_body_pc=nullptr, std::int32_t *out_branch_count=nullptr)
	Alternation of straight-line byte/klass branches, optionally wrapped in \b/\B.
constexpr void	real::detail::extract_anchoring (std::span< const instr > code, pattern_hints &hints)
	Records start anchoring: the first non-save instruction tells whether every match must begin at position 0 (\A/^ non-multiline) or at a line start.
constexpr void	real::detail::extract_prefix (std::span< const instr > code, pattern_hints &hints)
	Collects the required literal prefix and the exact-literal fast-path length.
constexpr void	real::detail::compute_first_bytes (std::span< const instr > code, std::span< const char_class > classes, std::span< const cp_class > cp_classes, pattern_hints &hints)
	Computes the possible first-byte set by a DFS over the epsilon closure of pc 0.
constexpr int	real::detail::class_range_count (const char_class &klass, std::uint8_t &lo0, std::uint8_t &hi0, std::uint8_t &lo1, std::uint8_t &hi1)
	Reports klass as up to two contiguous byte ranges.
REAL_BUILD_COLD constexpr void	real::detail::detect_fast_shapes (std::span< const instr > code, std::span< const char_class > classes, std::span< const cp_class > cp_classes, std::span< const code_range > cp_ranges, std::int32_t cp_mark_ascii, std::int32_t cp_mark_offset, std::int32_t cp_mark_end, std::span< const lookaround_sub > lookarounds, pattern_hints &hints)
	Detects the whole-pattern fast-path shapes and sets their hint flags: class+, fixed-shape straight runs, a single codepoint class (./negated, optional +), an alternation of straight-line branches, and trailing-lookaround class+.
constexpr std::uint16_t	real::detail::byte_frequency (std::uint8_t b)
	Approximate static frequency of a byte in mixed English and source text, per 10000, used only to rank candidate prefilter bytes: a rare required byte (-, @) is a far more selective memchr target than a common first-byte class.
constexpr std::uint8_t	real::detail::literal_rarest_offset (std::string_view literal)
	Offset of the rarest byte of literal by byte_frequency (the first of equals).
constexpr void	real::detail::extract_rare_byte (std::span< const instr > code, pattern_hints &hints)
	Records a required literal byte at a FIXED offset far rarer than the first-byte set (pattern_hints::rare_byte / rare_offset), so the search can memchr that one byte.
constexpr void	real::detail::extract_rare_discriminant (std::span< const instr > code, pattern_hints &hints)
	Arms the rare-discriminant prefilter for shapes like https?://…: fixed prefix (http) + optional mono-byte (s?) + fixed mid with a rare disc (://).
constexpr bool	real::detail::capture_free_walk_structural (std::span< const instr > code) noexcept
	The structural half of pattern_hints::capture_free_walk, that save 0 is the program's first instruction.
constexpr pattern_hints	real::detail::analyze_program (std::span< const instr > code, std::span< const char_class > classes, std::span< const cp_class > cp_classes, std::span< const code_range > cp_ranges, std::int32_t cp_mark_ascii, std::int32_t cp_mark_offset, std::int32_t cp_mark_end, std::span< const lookaround_sub > lookarounds={})
	Walks a compiled program once to derive its search hints.
constexpr bool	real::detail::fixed_shape_walk_pays (std::span< const instr > code, const pattern_hints &hints) noexcept
	Whether a search over this fixed shape (pattern_hints::fixed_shape) should walk each candidate start rather than run the lazy DFA.
constexpr std::size_t	real::detail::find_byte (std::string_view text, std::size_t pos, char byte)
	Index of byte in text[pos..), or real::npos.
constexpr std::size_t	real::detail::find_rare_disc_candidate (std::string_view text, std::size_t pos, const pattern_hints &hints, bool *density_abandon=nullptr)
	Next candidate start for the rare-discriminant prefilter, or real::npos.
constexpr void	real::detail::store_literal_density (literal_density &density, std::uint32_t cands, std::size_t origin, std::size_t next) noexcept
	Writes the adaptive search's local density back (find_literal_adaptive_rest keeps it in locals while it scans).
std::size_t	real::detail::find_literal_adaptive_rest (std::string_view text, std::size_t pos, std::string_view literal, std::size_t rare, literal_density &density)
	The body of find_literal_adaptive past its first stop: the pair filter for a dense subject, else the rarest-byte scan that counts its stops and judges their density.
std::size_t	real::detail::find_literal_adaptive (std::string_view text, std::size_t pos, std::string_view literal, std::size_t rare, literal_density &density)
	Index of the first occurrence of literal in text[pos..), or real::npos, by its rarest byte while that byte is rare in the subject and by the two-byte block filter once it is not.
bool	real::detail::alternation_nibbles_supported ()
	Whether the nibble fingerprint can run here: AArch64 always, x86 when the build enables SSSE3 or, with gcc or clang, when the running CPU has it. A plan built elsewhere never claims one: the fingerprint's reach is shorter than the pairs', and a scan that bounded its blocks by it while masking by the pairs would read past the subject.
constexpr std::size_t	real::detail::find_literal (std::string_view text, std::size_t pos, std::string_view literal)
	Index of the first occurrence of literal in text[pos..), or real::npos.
constexpr std::size_t	real::detail::find_prefix (std::string_view text, std::size_t pos, std::string_view prefix)
	First position >= pos where prefix occurs in text, or npos; the dispatch of find_literal.
std::size_t	real::detail::find_members (std::string_view text, std::size_t pos, const std::array< std::uint8_t, 8 > &mem, std::uint8_t n)
	Least index at or after pos whose byte is one of n members, in ONE pass.
std::size_t	real::detail::find_folded_literal (std::string_view text, std::size_t pos, std::string_view lit, std::uint16_t folded, std::size_t rare)
	The first occurrence at or after pos of a literal some of whose letters match in either case.
constexpr std::size_t	real::detail::find_line_end_cr (std::string_view text, std::size_t pos)
	Where an ECMAScript line ends: the index of the first \n or \r in text[pos..), or real::npos.
constexpr std::size_t	real::detail::find_bytes_cascade (std::string_view text, std::size_t pos, const char *set, std::uint8_t n)
	Index of the first byte in text[pos..) that belongs to a small first-byte set.
constexpr std::size_t	real::detail::first_high_byte (std::string_view text, std::size_t pos, std::size_t end)
	Index of the first byte >= 0x80 in text[pos, end), or end if the range is pure ASCII.

Variables
constexpr std::size_t	real::detail::fixed_shape_walk_max_width {8}
	Widest unfiltered shape kept on the walk.
constexpr std::uint32_t	real::detail::rare_disc_fail_abandon {32}
	Consecutive disc hits that fail back-verify before the density gate trips. Dense : filler (e.g. a:b:c:d…) makes memchr+verify lose to a selective http prefix.
constexpr std::uint32_t	real::detail::literal_dense_min_cands {8}
	Stops the rarest-byte scan makes before its density is judged: fewer say nothing.
constexpr std::size_t	real::detail::literal_dense_gap {64}
	Mean bytes between stops below which the rarest byte counts as common: under it, a stop costs more than the pair filter spends crossing that many bytes.
constexpr std::size_t	real::detail::alternation_nibbles_min_branches {3}
	Fewest branches for which the fingerprint replaces the pairs. Two pairs are two compares a block, a fingerprint six table lookups: on x86 (SSSE3) two branches lose by the fingerprint and three break even; AArch64's lookups are cheap enough that two branches already gain.
constexpr std::size_t	real::detail::alternation_sample_min {4096}
	Shorter rests are scanned by the first bytes, unsampled (at least the sample and its reach).
constexpr std::size_t	real::detail::alternation_sample_bytes {512}
	Bytes sampled for the first bytes' density.
constexpr std::size_t	real::detail::alternation_wide_min_branches {2}
	Fewest branches the wide route considers: branches that open on classes outgrow the small set with a few.
constexpr std::size_t	real::detail::alternation_wide_max_branches {16}
	Most branches the fingerprint's plan holds.
constexpr std::size_t	real::detail::alternation_wide_false_budget {256}
	Past this many false candidates times branches in a sample, the automaton scans cheaper than the fingerprint and its verifier.
constexpr std::size_t	real::detail::alternation_dense_gap {32}
	Mean bytes between first-byte hits in the sample below which the pair filter takes over (both ISAs: where the first-byte scan and the pair filter crossed on 500 KB of log lines).
constexpr std::size_t	real::detail::alternation_dense_gap_nibbles {128}
	The same threshold for a plan masking by the nibble fingerprint, whose cost per block is fixed: it crossed the first-byte loop at 256-512 bytes between false stops (arm64, x86-64 AVX2, 3 to 10 branches); at 128 its worst ratio was 0.77 of the loop's time.
constexpr bool	real::detail::have_members_scan {false}
	Whether a consumer should ARM a filter on find_members (one ISA only, measured).

Detailed Description

Search acceleration: pattern analysis and candidate-finding.

Extracts real::detail::pattern_hints from a compiled program (literal prefix, start anchoring, first-byte set, fast-path shapes) and provides the skip-ahead primitives used when no thread is alive: memchr / the platform substring search at run time, plain loops in constexpr. Hints change only speed, never what matches; an equivalence test runs the engine with hints disabled.