$ show timbray/quamina
Quamina is a high-performance Go library for matching patterns against JSON events. It uses a custom NFA/DFA automaton approach internally, supporting exact strings, shell-style wildcards, and a subset of I-Regexp (RFC 9485). Patterns are defined as JSON objects with field/value constraints, and the library provides a concise API to add patterns and efficiently retrieve matches for events. The core is a compact `smallTable` data structure for byte-transition tables, with optimizations like incremental epsilon closures and table-pointer deduplication to keep matching near O(1) for exact patterns. Quamina is version 2.0.1, has zero runtime dependencies, and includes extensive benchmarks and a research subdirectory for performance analysis. It is intended as an embedded library for real-time event classification (e.g., routing, log analysis) rather than a standalone service.
The LLM identified 5 files worth highlighting for reuse:
Implements `smallTable`, a packed byte-range transition table using `ceilings` and `steps` slices to minimize memory. Lookups are O(log n) via binary search on ceilings. This data structure is the heart of the automaton engine and is fully self-contained; it could be extracted for any project needing compact associative byte-to-value mappings.
Provides incremental epsilon closure computation for NFA states using generation counters and a `selfOnlyClosure` sentinel to avoid allocations for trivial closures. The logic is isolated (only depends on `faState` and `smallTable`) and represents a non‑obvious optimization technique for automata engines.
Implements an interning mechanism for sorted NFA state lists during DFA conversion. It provides a `StateLists` structure that interns slices of `stateIdx` to deduplicate equivalent state combinations, significantly reducing memory in DFA construction. The pattern (interning sorted slices with hash keys) is generally reusable for any DFA or product‑state generation.
Contains a custom JSON flattener that uses a `SegmentsTreeTracker` to skip branches not referenced by any pattern. This optimisation avoids parsing irrelevant parts of the event tree, improving throughput in high‑cardinality event streams. The flattener interface is clean and could be adapted for other tree‑structured data formats (e.g., Avro, Protobuf).
Implements `segmentsTree` – a trie‑like structure that records which field paths are used by patterns. It enables the flattener to skip whole JSON subtrees that cannot match any pattern. The tree supports add, lookup, and merge operations, and is isolated from the rest of the library except for its own types. It could be reused as a generic path tracker for any selective traversal.