aho_corasick.hpp File Reference

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

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

Include dependency graph for aho_corasick.hpp:

Classes
class	real::detail::ac_automaton
	Aho-Corasick automaton for a fixed_alternation program's branch set, built once per compiled program and reused across every match on it. More...
struct	real::detail::ac_automaton::match_result
	One search's answer. More...
struct	real::detail::ac_automaton::trie_node
	One trie node: while the automaton is built, and searched in the sparse form after. More...
struct	real::detail::ac_automaton::best_so_far
	The best match so far: earliest start, then smallest branch id. 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::size_t &	real::detail::ac_memory_budget ()
	Bytes an automaton may hold (the layout rule is in the file header); ac_memory_budget_default unless a test shrinks it to reach the sparse form and the decline.
bool &	real::detail::ac_dense_disabled ()
	Test seam: search the sparse trie even where the dense table fits.
std::size_t &	real::detail::ac_sparse_row_cap ()
	Test seam: at most this many dense rows in the sparse form below what the budget allows. The root keeps its row whatever the cap: a miss there has no fail link to fall along.
REAL_BUILD_COLD 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, over the program's own byte classes (every class it tests is a union of them, so no position is split).

Variables
constexpr std::size_t	real::detail::ac_memory_budget_default {std::size_t {32} << 20U}
constexpr std::size_t	real::detail::ac_max_branch_expansion = 64
	Maximum class sequences one branch may expand into (one per combination of the classes its positions span); past this the WHOLE pattern takes the ordinary pattern_hints::fixed_alternation route. A case-folded letter is one class unless another branch tells its cases apart.

Detailed Description

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

Built lazily per program from the byte/klass ops 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 one O(n) automaton walk beats the first-byte scans; under it the pattern stays on its usual route.

The trie is built over the program's byte CLASSES (bytes no branch position tells apart share one), so a case-folded branch is one path, in a sparse first-child/next-sibling form sized by the node count. Fail links are computed on it. Where the dense table fits real::detail::ac_memory_budget, states are numbered reporting-first and the table is allocated once at its exact size, with premultiplied ids (index * stride): a step is one class lookup and one dependent load, "does this state report" one compare. Otherwise the sparse trie is searched, the shallowest nodes given dense rows while the budget lasts; past what the trie itself may take, nothing is built and the ordinary alternation route runs.

Leftmost-first: earliest start wins, then the FIRST-LISTED branch (smallest id), as REAL's thread-priority alternation does; held to it by a differential (tests/engine/test_fastpath_seam_matrix.cpp, seam_run_aho_corasick). Storage is std::vector throughout, no raw new/delete.