Aho-Corasick automaton for a fixed_alternation program's branch set, built once per compiled program and reused across every match on it. More...

#include <aho_corasick.hpp>

Classes
struct	best_so_far
	The best match so far: earliest start, then smallest branch id. More...

struct	match_result
	One search's answer. More...

struct	trie_node
	One trie node: while the automaton is built, and searched in the sparse form after. More...

Public Member Functions
constexpr	ac_automaton (const std::array< std::uint8_t, 256 > &byte_class, std::uint32_t class_count)
	Starts an empty trie over `class_count` byte classes.

bool	add_literal (std::span< const std::uint8_t > classes, std::int32_t id)
	Adds one class sequence of branch `id`. Several calls with one `id` are expected: a branch whose positions span classes the others tell apart expands into each, all sharing its id, and the smallest-id tie-break then reads every one as that branch.

void	build ()
	Computes the fail and output links on the sparse trie, then lays the automaton out, dense or sparse by ac_memory_budget.

template<typename WbOk >
match_result	search (std::string_view text, std::size_t start, const WbOk &wb_ok) const
	The leftmost-first match at or after `start:` earliest start, then smallest branch id.

std::size_t	node_count () const
	The trie's node count.

bool	is_sparse () const
	Whether the automaton searches its sparse trie (the dense table did not fit, or was disabled).

std::size_t	sparse_rows () const
	Dense rows the sparse form was given.

std::size_t	memory_bytes () const
	Heap bytes the automaton holds once built.

Private Member Functions
std::int32_t	sparse_next (std::int32_t s, std::uint8_t c) const
	Sparse form: the total transition from `s` on class `c` – the node's dense row where it has one, else its children, else along the fail chain (which ends at the root, which has a row).

std::int32_t	sparse_child (std::int32_t s, std::uint8_t c) const
	The child of `s` on class `c`.

template<typename WbOk >
void	report_dense (std::int32_t state, std::size_t i, best_so_far &best, const WbOk &wb_ok) const
	Dense form: offers `best` the longest match ending at `i` that `wb_ok` passes, down the output chain from `state` (longest first, so the first that passes starts earliest).

template<typename WbOk >
match_result	search_dense (std::string_view text, std::size_t start, const WbOk &wb_ok) const
	Dense form of search.

template<typename WbOk >
void	report_sparse (std::int32_t node, std::size_t i, best_so_far &best, const WbOk &wb_ok) const
	Sparse form of report_dense.

template<typename WbOk >
match_result	search_sparse (std::string_view text, std::size_t start, const WbOk &wb_ok) const
	Sparse form of search.

Private Attributes
std::array< std::uint8_t, 256 >	cls_ {}
	Byte to class.

std::uint32_t	stride_ {1}
	The class count: a dense row's width.

std::vector< std::int32_t >	trans_
	Dense form: `[state + class]` to the next state, premultiplied.

std::int32_t	match_limit_ {0}
	Dense form: states below it report a match.

std::int32_t	start_ {0}
	Dense form: the root's id.

std::vector< std::int32_t >	out_pid_
	Dense form: a reporting state's branch, or -1.

std::vector< std::int32_t >	out_len_
	Dense form: its length.

std::vector< std::int32_t >	out_link_
	Dense form: the next reporting state on its fail chain, or -1.

std::vector< trie_node >	trie_
	The trie: while building, and searched in the sparse form.

std::vector< std::int32_t >	rows_
	Sparse form: the dense rows granted, `[row * stride + class]`.

std::size_t	node_count_ {0}
	The trie's node count.

std::int32_t	max_pattern_len_ {1}
	The longest sequence: how far back a match can start.

bool	sparse_ {false}
	Searched through the trie.

Detailed Description

Aho-Corasick automaton for a fixed_alternation program's branch set, built once per compiled program and reused across every match on it.

Constructor & Destructor Documentation

◆ ac_automaton()

constexpr real::detail::ac_automaton::ac_automaton	(	const std::array< std::uint8_t, 256 > &	byte_class,
		std::uint32_t	class_count
	)

inlineconstexpr

Starts an empty trie over class_count byte classes.

Parameters

[in]	byte_class	The class of each byte.
[in]	class_count	How many classes there are: a dense row's width.

Member Function Documentation

◆ add_literal()

bool real::detail::ac_automaton::add_literal	(	std::span< const std::uint8_t >	classes,
		std::int32_t	id
	)

inline

Adds one class sequence of branch id. Several calls with one id are expected: a branch whose positions span classes the others tell apart expands into each, all sharing its id, and the smallest-id tie-break then reads every one as that branch.

Parameters

[in]	classes	The sequence.
[in]	id	The branch's declaration order.

Returns: False once the sparse trie would pass ac_memory_budget – the automaton is then not built.

◆ is_sparse()

bool real::detail::ac_automaton::is_sparse ( ) const

inline

Whether the automaton searches its sparse trie (the dense table did not fit, or was disabled).

Returns: True in the sparse form.

◆ memory_bytes()

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

inline

Heap bytes the automaton holds once built.

Returns: The bytes.

◆ node_count()

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

inline

The trie's node count.

Returns: The number of states.

◆ report_dense()

template<typename WbOk >

void real::detail::ac_automaton::report_dense	(	std::int32_t	state,
		std::size_t	i,
		best_so_far &	best,
		const WbOk &	wb_ok
	)		const

inlineprivate

Dense form: offers best the longest match ending at i that wb_ok passes, down the output chain from state (longest first, so the first that passes starts earliest).

Template Parameters

WbOk	As search.

Parameters

[in]	state	The reporting state reached at `i` (premultiplied).
[in]	i	The position of the byte just consumed.
[in,out]	best	The best match so far.
[in]	wb_ok	The boundary test.

◆ report_sparse()

template<typename WbOk >

void real::detail::ac_automaton::report_sparse	(	std::int32_t	node,
		std::size_t	i,
		best_so_far &	best,
		const WbOk &	wb_ok
	)		const

inlineprivate

Sparse form of report_dense.

Template Parameters

WbOk	As search.

Parameters

[in]	node	The node reached at `i`.
[in]	i	The position of the byte just consumed.
[in,out]	best	The best match so far.
[in]	wb_ok	The boundary test.

◆ 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

The leftmost-first match at or after start: earliest start, then smallest branch id.

Template Parameters

WbOk	Callable `(start, end) -> bool`: the pattern's lead/trail word-boundary test.

Parameters

[in]	text	The subject.
[in]	start	Where to search from.
[in]	wb_ok	The boundary test; a candidate it refuses is passed over.

Returns: The match, if any.

◆ search_dense()

template<typename WbOk >

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

inlineprivate

Dense form of search.

Template Parameters

WbOk	As search.

Parameters

[in]	text	The subject.
[in]	start	Where to search from.
[in]	wb_ok	The boundary test.

Returns: The match, if any.

◆ search_sparse()

template<typename WbOk >

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

inlineprivate

Sparse form of search.

Template Parameters

WbOk	As search.

Parameters

[in]	text	The subject.
[in]	start	Where to search from.
[in]	wb_ok	The boundary test.

Returns: The match, if any.

◆ sparse_child()

std::int32_t real::detail::ac_automaton::sparse_child	(	std::int32_t	s,
		std::uint8_t	c
	)		const

inlineprivate

The child of s on class c.

Parameters

[in]	s	The node.
[in]	c	The class.

Returns: The child, or -1.

◆ sparse_next()

std::int32_t real::detail::ac_automaton::sparse_next	(	std::int32_t	s,
		std::uint8_t	c
	)		const

inlineprivate

Sparse form: the total transition from s on class c – the node's dense row where it has one, else its children, else along the fail chain (which ends at the root, which has a row).

Parameters

[in]	s	The state.
[in]	c	The class.

Returns: The next state.

◆ sparse_rows()

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

inline

Dense rows the sparse form was given.

Returns: The row count; 0 in the dense form.

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

include/real/engine/aho_corasick.hpp

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ac_automaton()

Member Function Documentation

◆ add_literal()

◆ is_sparse()

◆ memory_bytes()

◆ node_count()

◆ report_dense()

◆ report_sparse()

◆ search()

◆ search_dense()

◆ search_sparse()

◆ sparse_child()

◆ sparse_next()

◆ sparse_rows()