real::detail::ac_automaton Class Reference

Dense Aho-Corasick automaton for a fixed_alternation program's branch set. More...

#include <aho_corasick.hpp>

Classes
struct	match_result
	One AC search outcome: whether/where/which branch matched. More...

Public Member Functions
void	add_literal (const std::vector< std::uint8_t > &bytes, std::int32_t id)
	Adds one branch's literal byte-set sequence, tagged with its source declaration order (id).
void	build ()
	Standard single-pass BFS goto-function-as-DFA construction.
template<typename WbOk >
match_result	search (std::string_view text, std::size_t start, const WbOk &wb_ok) const
	Leftmost-first search over text starting at start.
std::size_t	node_count () const
	States in the automaton, root included.

Private Attributes
std::vector< ac_node >	nodes_ {ac_node {}}
	Pool storage; root at index 0. No raw new/delete.
std::int32_t	max_pattern_len_ {1}
	Longest literal added, bounding how far back a match can start.

Detailed Description

Dense Aho-Corasick automaton for a fixed_alternation program's branch set.

Built once per compiled program (see build_ac_automaton), then reused across every match on that program via the state cache in pike_state — the same build-once-per-program discipline the lazy DFA and the inner-literal prefix follow.

Member Function Documentation

add_literal()

void real::detail::ac_automaton::add_literal ( const std::vector< std::uint8_t > &  bytes, std::int32_t  id  )

inline

Adds one branch's literal byte-set sequence, tagged with its source declaration order (id).

Multiple calls with the same id are legal and expected: icase fan-out means one source branch containing a klass op at some position expands into every concrete byte string that op accepts, all sharing the branch's single id — the smallest-id-wins tie-break in search then treats every expansion of one branch as equally (and correctly) that one branch's priority, regardless of which concrete spelling matched.

Parameters

[in]	bytes	One concrete byte string the branch accepts.
[in]	id	The branch's declaration order.

build()

void real::detail::ac_automaton::build ( )

inline

Standard single-pass BFS goto-function-as-DFA construction.

Every state's fail link points to a strictly shallower state, so by the time a state is dequeued its fail state's goto_ row is already total — letting every missing edge be filled in place as goto_[state][c] = goto_[fail(state)][c], with no separate fail-chain-walk pass.

node_count()

std::size_t real::detail::ac_automaton::node_count ( ) const

inline

States in the automaton, root included.

Returns

The node count.

search()

template<typename WbOk >

match_result real::detail::ac_automaton::search ( std::string_view  text, std::size_t  start, const WbOk &  wb_ok  ) const

inline

Leftmost-first search over text starting at start.

Earliest match start wins; among matches starting at the same position, the smallest pattern id (first-listed branch) wins — REAL's own alternation semantics.

Template Parameters

WbOk	bool(std::size_t match_start, std::size_t match_end) — the caller's word-boundary check (e.g. pike_vm::wb_boundaries_ok); always-true when the alternation carries no \b/\B wrap.

A trail \b/\B depends only on the END position (identical for every branch ending there), but a LEAD \b/\B depends on the START position, which DOES differ across branches sharing one output-link chain (a shorter suffix starts later) — so a wb-rejected candidate is not necessarily the chain's last usable one. wb_ok is therefore checked per candidate, walking deeper into the chain only when the shallower one fails it; when wb_ok is trivially true (the common, unwrapped case) this still costs one check and stops at the first (shallowest) hit, same as the unconstrained walk.

Parameters

[in]	text	Subject.
[in]	start	Byte offset to begin scanning at.
[in]	wb_ok	The caller's word-boundary check, per WbOk.

Returns

The leftmost-first match, or a result whose match_result::matched is false.

---

The documentation for this class was generated from the following file:

• include/real/engine/aho_corasick.hpp