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 dependency graph for prefilter.hpp:

Go to the source code of this file.

Namespaces
namespace	real
namespace	real::detail

Functions
constexpr bool	real::detail::is_fixed_alternation (std::span< const instr > code)
	Tests whether the whole program is an alternation of straight-line branches (e.g. the|fox|dog).
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 void	real::detail::detect_fast_shapes (std::span< const instr > code, std::span< const char_class > classes, std::int32_t cp_mark_ascii, std::int32_t cp_mark_offset, 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 +), and an alternation of straight-line branches.
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 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::int32_t cp_mark_ascii, std::int32_t cp_mark_offset)
	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_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.
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.

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.

Definition in file prefilter.hpp.