aho-corasick API reference Changelog View on GitHub

API reference

Aho-Corasick multi-pattern search in Zig, with the automaton built at comptime.

Aho-Corasick finds every occurrence of a set of patterns in one pass over the haystack, whatever the number of patterns. Matcher puts the patterns in the type and builds the automaton at comptime, so searching allocates nothing. Automaton builds the same tables at runtime from a pattern list and an allocator.

const ac = @import("aho-corasick");

const Keywords = ac.Matcher(&.{ "apple", "maple" }, .{});

const m = Keywords.find("a maple leaf").?;
// m.pattern == 1, m.start == 2, m.end == 7

var it = Keywords.findOverlappingIter("apples and maples");
while (it.next()) |hit| {
    // every occurrence, including nested ones
}

module Automaton

src

A runtime-built Aho-Corasick automaton.

Matcher builds at comptime from a pattern list in the type. This type builds the same tables at runtime from patterns the caller supplies, which is what a program reading a dictionary or a tool inspecting an automaton needs.

Constants

pub const State = u32

src

pub const start_state: State = 0

src

The state before any byte has been read.

pub const Error = …

src
value
error{
    NoPatterns,
    TooManyPatterns,
    EmptyPattern,
    DuplicatePattern,
    PatternTooLong,
    OutOfMemory,
}

Functions

pub fn init( gpa: Allocator, patterns: []const []const u8, options: Options, ) Error!Automaton

src

Builds the automaton for patterns. The automaton copies the pattern bytes, so the caller can free its own copy after this returns.

pub fn deinit(self: *Automaton) void

src

pub fn pattern(self: *const Automaton, id: u32) []const u8

src

pub fn patternCount(self: *const Automaton) usize

src

pub fn patternLen(self: *const Automaton, id: u32) usize

src

pub fn minPatternLen(self: *const Automaton) usize

src

pub fn maxPatternLen(self: *const Automaton) usize

src

pub fn matchKind(self: *const Automaton) MatchKind

src

pub fn stateCount(self: *const Automaton) usize

src

pub fn transitionCount(self: *const Automaton) usize

src

pub fn alphabet(self: *const Automaton) []const u8

src

pub fn stateDepth(self: *const Automaton, state: State) usize

src

pub fn stateFailure(self: *const Automaton, state: State) State

src

pub fn stateOutput(self: *const Automaton, state: State) ?u32

src

pub fn transitions(self: *const Automaton, state: State) Search.Transitions

src

pub fn matchesAt(self: *const Automaton, state: State, end: usize) Search.Matches

src

pub fn firstMatch(self: *const Automaton, state: State, end: usize) ?Match

src

pub inline fn nextState(self: *const Automaton, state: State, byte: u8) State

src

pub fn isMatchState(self: *const Automaton, state: State) bool

src

pub fn find(self: *const Automaton, haystack: []const u8) ?Match

src

pub fn isMatch(self: *const Automaton, haystack: []const u8) bool

src

pub fn findIter(self: *const Automaton, haystack: []const u8) Search.Iterator

src

pub fn findOverlapping(self: *const Automaton, haystack: []const u8) ?Match

src

pub fn findOverlappingIter( self: *const Automaton, haystack: []const u8, ) Search.OverlappingIterator

src

pub fn whichMatches( self: *const Automaton, gpa: Allocator, haystack: []const u8, ) !bit_set.RuntimeSet

src

pub fn replaceAll( self: *const Automaton, writer: anytype, haystack: []const u8, replacements: []const []const u8, ) !void

src

pub fn memoryUsage(self: *const Automaton) usize

src

Bytes allocated for the tables and the pattern copy. The arena may hold more than this: the build's scratch lists live until deinit.

Types

struct Dfa

src

A dense DFA built from the runtime NFA.

The NFA follows failure links on a transition miss. This type precomputes every transition for every state and alphabet class, so a byte is one table lookup. It keeps the NFA for the outputs, the pattern bytes, and the introspection methods; the search reads the dense table.

Fields

nfa: Automaton
goto: []u32
tables: DfaTables
gpa: Allocator

Functions

pub fn init( gpa: Allocator, patterns: []const []const u8, options: Options, ) Error!Dfa

src

pub fn deinit(self: *Dfa) void

src

pub fn pattern(self: *const Dfa, id: u32) []const u8

src

pub fn patternCount(self: *const Dfa) usize

src

pub fn patternLen(self: *const Dfa, id: u32) usize

src

pub fn minPatternLen(self: *const Dfa) usize

src

pub fn maxPatternLen(self: *const Dfa) usize

src

pub fn matchKind(self: *const Dfa) MatchKind

src

pub fn stateCount(self: *const Dfa) usize

src

pub fn alphabet(self: *const Dfa) []const u8

src

pub fn stateDepth(self: *const Dfa, state: State) usize

src

pub fn stateOutput(self: *const Dfa, state: State) ?u32

src

pub fn matchesAt(self: *const Dfa, state: State, end: usize) DfaSearch.Matches

src

pub fn firstMatch(self: *const Dfa, state: State, end: usize) ?Match

src

pub fn find(self: *const Dfa, haystack: []const u8) ?Match

src

pub fn isMatch(self: *const Dfa, haystack: []const u8) bool

src

pub fn findIter(self: *const Dfa, haystack: []const u8) DfaSearch.Iterator

src

pub fn findOverlapping(self: *const Dfa, haystack: []const u8) ?Match

src

pub fn findOverlappingIter( self: *const Dfa, haystack: []const u8, ) DfaSearch.OverlappingIterator

src

pub fn whichMatches( self: *const Dfa, gpa: Allocator, haystack: []const u8, ) !bit_set.RuntimeSet

src

pub fn replaceAll( self: *const Dfa, writer: anytype, haystack: []const u8, replacements: []const []const u8, ) !void

src

pub fn memoryUsage(self: *const Dfa) usize

src

The NFA's tables plus the dense transition table.

struct Dfa

src 
pub const Dfa = @import("Automaton.zig").Dfa

A dense DFA built from the runtime NFA.

The NFA follows failure links on a transition miss. This type precomputes every transition for every state and alphabet class, so a byte is one table lookup. It keeps the NFA for the outputs, the pattern bytes, and the introspection methods; the search reads the dense table.

Fields

nfa: Automaton
goto: []u32
tables: DfaTables
gpa: Allocator

Functions

pub fn init( gpa: Allocator, patterns: []const []const u8, options: Options, ) Error!Dfa

src

pub fn deinit(self: *Dfa) void

src

pub fn pattern(self: *const Dfa, id: u32) []const u8

src

pub fn patternCount(self: *const Dfa) usize

src

pub fn patternLen(self: *const Dfa, id: u32) usize

src

pub fn minPatternLen(self: *const Dfa) usize

src

pub fn maxPatternLen(self: *const Dfa) usize

src

pub fn matchKind(self: *const Dfa) MatchKind

src

pub fn stateCount(self: *const Dfa) usize

src

pub fn alphabet(self: *const Dfa) []const u8

src

pub fn stateDepth(self: *const Dfa, state: State) usize

src

pub fn stateOutput(self: *const Dfa, state: State) ?u32

src

pub fn matchesAt(self: *const Dfa, state: State, end: usize) DfaSearch.Matches

src

pub fn firstMatch(self: *const Dfa, state: State, end: usize) ?Match

src

pub fn find(self: *const Dfa, haystack: []const u8) ?Match

src

pub fn isMatch(self: *const Dfa, haystack: []const u8) bool

src

pub fn findIter(self: *const Dfa, haystack: []const u8) DfaSearch.Iterator

src

pub fn findOverlapping(self: *const Dfa, haystack: []const u8) ?Match

src

pub fn findOverlappingIter( self: *const Dfa, haystack: []const u8, ) DfaSearch.OverlappingIterator

src

pub fn whichMatches( self: *const Dfa, gpa: Allocator, haystack: []const u8, ) !bit_set.RuntimeSet

src

pub fn replaceAll( self: *const Dfa, writer: anytype, haystack: []const u8, replacements: []const []const u8, ) !void

src

pub fn memoryUsage(self: *const Dfa) usize

src

The NFA's tables plus the dense transition table.

module Match

src

One match: which pattern, and where.

Functions

pub fn len(self: Match) usize

src

pub fn isEmpty(self: Match) bool

src

type fn Matcher

src 
pub const Matcher = @import("matcher.zig").Matcher

Builds a matcher for patterns at comptime.

more

Pattern i in patterns is pattern id i in every Match. Two patterns that are equal, including equal after ASCII case folding, are a compile error. Empty patterns are a compile error: a zero-length match is a different algorithm, and the iterators here promise progress.

Constants

pub const State = NodeIndex

src

pub const start_state: State = 0

src

The state before any byte has been read.

pub const PatternSet = bit_set.PatternSet(n_patterns)

src

The set of patterns that match anywhere in the haystack. Only for .standard.

Functions

pub fn patternCount() usize

src

pub fn patternLen(id: u32) usize

src

pub fn minPatternLen() usize

src

pub fn maxPatternLen() usize

src

pub fn matchKind() MatchKind

src

pub fn memory() Memory

src

pub fn memoryUsage() usize

src

pub fn stateCount() usize

src

pub fn transitionCount() usize

src

pub fn alphabet() []const u8

src

pub fn pattern(id: u32) []const u8

src

The pattern at id.

pub fn stateDepth(state: State) usize

src

pub fn stateFailure(state: State) State

src

pub fn stateOutput(state: State) ?u32

src

pub fn transitions(state: State) Search.Transitions

src

pub fn matchesAt(state: State, end: usize) Search.Matches

src

pub fn firstMatch(state: State, end: usize) ?Match

src

pub inline fn nextState(state: State, byte: u8) State

src

pub fn isMatchState(state: State) bool

src

pub fn find(haystack: []const u8) ?Match

src

The first match in the haystack, or null.

pub fn isMatch(haystack: []const u8) bool

src

pub fn findIter(haystack: []const u8) Search.Iterator

src

Non-overlapping matches according to matchKind().

pub fn findOverlapping(haystack: []const u8) ?Match

src

The first match in end-offset order. Only for .standard.

pub fn findOverlappingIter(haystack: []const u8) Search.OverlappingIterator

src

Every match, including overlapping ones, in end-offset order. Only for .standard.

pub fn whichMatches(haystack: []const u8) PatternSet

src

pub fn replaceAll( writer: anytype, haystack: []const u8, replacements: []const []const u8, ) !void

src

Write haystack to writer, replacing each non-overlapping match with the replacement at the same pattern index.

Types

struct Memory

src

The size of each table in the automaton, in bytes. The arrays are sized for the worst case, not for the nodes actually built.

Fields

total: usize
failure: usize
masks: usize
offsets: usize
children: usize
depths: usize
own_id: usize
classes: usize
alphabet: usize

enum MatchKind

src 
pub const MatchKind = @import("Options.zig").MatchKind

How an automaton chooses the match to report when more than one ends up being a candidate.

Fields

standard standard

Report each match as soon as the automaton reaches it, which orders matches by end offset. This is the textbook Aho-Corasick behavior and the only kind that supports overlapping searches.

leftmost_first leftmost_first

Report the match that starts earliest. When two matches start at the same offset, the pattern listed first wins, so {"ab", "abc"} returns the one listed first on "abc".

leftmost_longest leftmost_longest

Report the match that starts earliest. When two matches start at the same offset, the longest wins.

struct Options

src 
pub const Options = @import("Options.zig").Options

Fields

match_kind: MatchKind = .standard
ascii_case_insensitive: bool = false

Fold ASCII letters in both the patterns and the haystack, so "Apple" matches "apple". Other bytes compare exactly.