$ show katef/libfsm
libfsm is a C library and toolchain for constructing, manipulating, and compiling finite state machines (FSMs) from regular expressions. It supports multiple regex dialects (PCRE, glob, SQL LIKE, literal, native) and compiles them into deterministic finite automata (DFAs) that guarantee linear-time matching. The library provides a rich set of FSM operations: determinisation, minimisation, union, intersection, complement, reversal, trimming, and more. It also includes a lexer generator (lx) that produces C lexers from specification files, and a pattern matcher builder (rx) that merges many patterns into a single DFA with conflict detection. The architecture is modular: an abstract data type (ADT) layer provides reusable data structures (sets, hash tables, priority queues, edge sets, interned state sets); the libfsm core implements FSM algorithms; libre handles regex parsing and AST analysis; and multiple code generation backends emit C, Rust, Go, LLVM IR, x86 assembly, awk, shell, JSON, and a custom VM bytecode. The build system uses BSD make (bmake) and the project is extensively tested with unit tests, property-based fuzzing (theft), and a cross-implementation test runner (retest) that compiles and runs generated code via dlopen. Key entry points include the fsm CLI tool for interactive FSM operations, the re CLI for regex compilation and code generation, the lx CLI for lexer generation, and the rx CLI for building pattern matchers. The library is designed for embedding in other applications, with allocator hooks and a clean public API. It is particularly suited for high-performance pattern matching, protocol parsing, and any domain requiring deterministic automata with guaranteed worst-case performance.
The LLM identified 3 files worth highlighting for reuse:
Implements a compact edge set for storing FSM transitions using bit groups and binary search. Supports bulk addition, ordered/unordered iteration, and efficient grouping of transitions by character range. This is a self-contained data structure that could be reused in any graph or automaton representation requiring memory-efficient edge storage with fast iteration.
Provides a pool of interned state sets for efficient deduplication during NFA-to-DFA conversion. Uses a hash table to store unique sets of NFA states, returning canonical handles. This pattern is reusable in any algorithm that needs to avoid duplicate set computations, such as subset construction or closure operations.
Translates a DFA into a sequence of VM IR opcodes (FETCH, STOP, BRANCH). The IR is a linked list of instructions that can later be encoded into variable-length or fixed-length bytecode. This demonstrates a clean separation between the automaton representation and the execution model, and the pattern is reusable for any compiler that needs to generate low-level code from a state machine.