prefilter.hpp File Reference

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

#include "real/version.hpp"
#include <cstdint>
#include <cstring>
#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 dependency graph for prefilter.hpp:

Classes
struct	real::detail::shape_lead
	detect_fast_shapes's outer envelope: save 0, optional lead \b/\B. No-ops safely on a shape with no \b/\B support (e.g. a literal byte right after save 0). More...
struct	real::detail::shape_close
	The shape_lead counterpart: optional trail \b/\B at from, then exactly save 1, match at the very end of code. from (the body's own end) is the caller's to supply – only its shape-specific body walk knows where that is. 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.

Functions
std::uint64_t &	real::detail::prefilter_work_units () noexcept
	Prefilter work counter for the O(n) vs O(n²) smoke test. Always declared (clang-tidy / tests see the symbol). Billing is a no-op unless REAL_TEST_INSTRUMENT is defined on the test binary — wheel/prod pay nothing.
void	real::detail::prefilter_note_scan (std::size_t n) noexcept
	Bill n scanned bytes to prefilter_work_units. A no-op unless the test binary defines REAL_TEST_INSTRUMENT.
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
	Peel an optional \b/\B assertion at p.
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). Only sound when the match is a greedy + run: a maximal run of \w can only ever START where the character before it is non-word (or absent) – that IS \b (or the text edge), so checking it again is redundant. A SINGLE code point (no +) has no such guarantee: \b\w may legally start mid-run (any word code point qualifies as a candidate start), so dropping the boundary there is unsound, not just conservative. The caller is responsible for only calling this when lead / trail came from a provably maximal-run shape (see resolve_class_wb_hints's maximal_run).
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
	safety check: true if the ASCII byte b could be a member of code-point class cc — used only to test whether a single-byte delimiter (a "quoted"-shape prefix or suffix) could hide inside a klass_cp_loop_possessive body, in which case the delimited fast path must decline (see pattern_hints::possessive_prefix). A non-ASCII b (>= 0x80) is conservatively treated as a member (unsafe, declines) — this shape's corpus is single-byte ASCII delimiters (", ;, …), so a multi-byte delimiter simply stays general.
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 std::int32_t	real::detail::fixed_run_width (std::span< const instr > code)
	Total consuming width (in bytes) of a straight-line byte/klass program: save 0, an interleaved byte/klass/save sequence with no nested capturing groups, save 1, match – the same shape detect_fast_shapes's fixed_shape check recognizes, factored out so a SEPARATE complete program (e.g. the inner-literal prefix sub-program, compiled on its own AST) can be measured the same way without re-deriving the walk.
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.
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 + source text (occurrences per 10000; higher = more common). No text is ever scanned — this only ranks candidate prefilter bytes against one another. Punctuation like - @ . is far rarer than any letter, digit or space, which is the whole point: a required rare byte makes a far more selective memchr target than a common first-byte class.
constexpr void	real::detail::extract_rare_byte (std::span< const instr > code, pattern_hints &hints)
	Finds a required literal byte at a FIXED offset that is statically far rarer than the pattern's first-byte set, and records it (pattern_hints::rare_byte / rare_offset) so the search can memchr that one byte instead of scanning a common first-byte class per 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 – 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 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 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.
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.
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 (2..4) 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::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 bool	real::detail::have_members_scan {false}
	Whether a consumer should ARM a filter on find_members – one ISA only, and measured.

Detailed Description

Search acceleration: pattern analysis and candidate-finding.

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