aho_corasick.hpp File Reference

Aho-Corasick multi-literal engine for large pure-literal alternations. More...

#include "real/version.hpp"
#include "real/core/charclass.hpp"
#include "real/core/program.hpp"
#include <algorithm>
#include <array>
#include <cstdint>
#include <optional>
#include <queue>
#include <span>
#include <string_view>
#include <vector>

Include dependency graph for aho_corasick.hpp:

Classes
struct	real::detail::ac_node
	One Aho-Corasick trie/DFA node: a dense 256-entry goto row plus fail/output links. More...
class	real::detail::ac_automaton
	Dense Aho-Corasick automaton for a fixed_alternation program's branch set. More...
struct	real::detail::ac_automaton::match_result
	One AC search outcome: whether/where/which branch matched. 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::optional< ac_automaton >	real::detail::build_ac_automaton (std::span< const instr > code, std::span< const char_class > classes, std::size_t body_pc)
	Builds an ac_automaton from a fixed_alternation-shaped program's branch set.

Variables
constexpr std::size_t	real::detail::ac_max_branch_expansion = 64
	Maximum concrete literal strings a single branch may expand into (icase klass fan-out).

Detailed Description

Aho-Corasick multi-literal engine for large pure-literal alternations.

A dense-trie automaton (goto-function-as-total-transition-table), built lazily per program from the compiled byte/klass op sequence of a real::detail::pattern_hints::fixed_alternation -shaped program (see prefilter.hpp's is_fixed_alternation) once its branch count reaches the threshold where a single O(n) automaton walk beats real::detail::pattern_hints::small_set's 2..8-member memchr-cascade scan — that scan has no fast path at all past 8 distinct first bytes. It complements small_set/fixed_alternation rather than replacing them: an eligible pattern under the threshold stays on its usual route.

Leftmost-first semantics: earliest match start wins; among matches starting at the same position, the FIRST-LISTED branch (smallest declared id) wins, matching REAL's own thread- priority alternation semantics exactly — held to it by a differential rather than by assertion (tests/engine/test_fastpath_seam_matrix.cpp, seam_run_aho_corasick).

Storage is a std::vector<ac_node> pool throughout — no raw new/delete anywhere in this file.