libfsm: regular expressions compiled to deterministic finite state machines

The restriction is the product

The readme opens with the caveat that matters most, and it is worth reading before anything else. libfsm is not a drop-in replacement for other regex engines, and it only supports patterns that can be compiled to deterministic FSMs. In return, supported patterns run in linear time. That is a real trade, and a different one from the usual regex library trade, where you get more features and accept the possibility of catastrophic backtracking. Here you give up the patterns that cannot be expressed as a deterministic machine, and in exchange the matching time is bounded by the length of the input regardless of what the pattern looks like. For a validator sitting in front of a network, or a lexer in a parser that must not stall on a hostile input, that guarantee is the entire reason to accept the restriction. The library also supports NFA as well as DFA, so the intermediate representation is available when you need it, and the fsm command line tool exposes that machinery directly.

Two libraries and four command line tools

The package is a family rather than a single library, and the readme lists what you get. libfsm is the library for manipulating FSMs, covering both NFA and DFA. libre is the library for compiling regular expressions to NFA, so the two libraries split along the compilation pipeline. Then there are four command line tools. fsm(1) is the interface for working with finite state machines directly. re(1) is the interface for regular expressions, and the tutorial introduction to it is the fastest way in. rx(1) compiles sets of regular expressions, which is what you want when a pattern is a set rather than a single expression. lx(1) is the lexer generator. The commands in the readme show the shape of the tool, with a pipeline that applies a regular expression to text and passes the result on, and the presence of pipe-friendly Unix tools throughout is not incidental, because the whole design assumes you will compose these commands in a shell pipeline rather than call them from a program.

lx is a lexer generator that does only lexing

The description of lx is worth quoting in spirit because it explains the design philosophy of the project. lx is an attempt to produce a simple, expressive and unobtrusive lexer generator which is good at lexing, does just lexing, is language independent, and has no other features. That last clause is a design position rather than a gap. Most lexer generators in this space accumulate features, and a generator that also does parsing, or formatting, or a language specific output dialect, becomes hard to reason about when a pattern misbehaves. Here the output is a lexer and the boundary is clear. The documentation set backs this up: there is a tutorial introduction to the re command line interface, a page on the compilation phases for typical applications which compile regular expressions to code, and an advice document with suggestions around compilation time, unsupported features, common usage patterns and examples. The examples directory backs it up too, with a directory per tool and per technique, including glob, iprange, urldecode, uncomment, utf8dfa and words.

The build insists on BSD make, and refuses to be flexible

Getting the source requires submodules, because they contain the required .mk files, and the build uses a BSD make rather than GNU make:

git clone --recursive https://github.com/katef/libfsm.git
bmake -r
bmake -r install

A few things can be overridden, and the compiler and the install prefix are the two that matter:

CC=clang bmake -r
PREFIX=$HOME bmake -r install

The -r flag is not optional, and the Makefile explains why. It refuses to use sys.mk, printing that the system makefile is not used and that you should run make with -r, and it also refuses any .OBJDIR other than the current directory. The build depends on any BSD make, a C compiler where gcc and clang are the best supported, and ar, ld and other tools you probably already have. Getting bmake is its own small quest, and the readme lists the options in order of preference: on a BSD system it is make(1), on Linux or macOS you can install the package called bmake, on Linux the package called pmake is the same thing, and on macOS bsdmake is Apple's own fork. Failing all that, you can build bmake from source, and only the bmake tarball is needed rather than the full mk tarball.

Tests, documentation and property based fuzzing

The test target needs one more tool, and the documentation needs two more. Running the tests requires xmllint, packaged as libxml2-utils, and the invocation passes the freshly built lexer in explicitly:

bmake -r LX=./build/bin/lx test

Building the documentation additionally requires xsltproc and the Docbook XSLT stylesheets with their XML catalog entries, packaged as docbook-xsl and docbook-xml, which is why the makefile carries a NODOC option and an install target that skips the documentation when you want it:

CC=clang PREFIX=$HOME pmake -r -DNODOC install

The third dependency is the interesting one. Fuzzing depends on the theft property based testing library, and the tests are currently written against the libtheft 0.4.2 API, with a theft directory in the tree and a separate make target. Property based testing is a good fit for a library like this, because the interesting inputs for a regular expression engine are the ones nobody thought to write down, and a generator that produces them systematically beats a hand written list of edge cases. The repository also carries a fuzz directory and a reperf directory, which points at performance measurement as a first class activity rather than an afterthought.

What the man pages reveal about the scope

The Makefile lists the manual pages it builds, and the list is a better description of the project than the readme summary. There are the command pages for fsm, re, rx and lx, the library page for libfsm, a printing page, and a set of format pages: fsm.5 and lx.5, a language description in fsm_lang.5fsm, and a family of regular expression dialect files in glob.5re, like.5re, literal.5re, native.5re, re_dialect.5re and sql.5re. The dialect pages are the significant part. They describe regular expression dialects that libfsm can target, so a pattern written for one of those conventions can be compiled for a tool that expects it, and the sql dialect is the kind of detail you only find in a library that has been used to build real things. The source layout supports the same picture, with directories for the cost and predicate parts of the libfsm core, a print module and an abstract data type module, plus a pkg-config directory for the pc file.

Where libfsm is the wrong tool

The boundary is the same one the readme draws, and it is worth stating with the consequences attached. If your patterns need features that cannot be compiled to a deterministic finite state machine, they are out of scope, and doc/advice.md is where the unsupported feature list and the suggested workarounds live. That rules out the class of patterns that depend on looking backwards in the input, and it means that a regex feature you use in a scripting language may simply not be expressible here. The second limit is the build environment, since a build that needs a BSD make has to have bmake or pmake on hand, which is a small but real friction in a build system. The third is the release model: the repository publishes no GitHub releases, so there is no tagged version to depend on and no changelog of releases to read, and the only contact offered for bugs and ideas is an email address. The licence is BSD-2-Clause, which allows commercial use as long as the copyright notice is kept.

Editorial conclusion

libfsm is the right choice when matching speed and predictability matter more than language compatibility, in a lexer, a protocol filter or a validator where you want a linear time guarantee and a state machine you can inspect. It is the wrong choice if you need the expressive features that only a backtracking engine offers, or if your build environment cannot run BSD make. Before you start, read doc/advice.md for the unsupported feature list and the common usage patterns, decide whether the deterministic restriction fits your patterns, and remember that the project publishes no GitHub releases, so pin the commit you build.

Frequently asked questions

Official sources

1. Issues
2. katef/libfsm on GitHub
3. License: BSD-2-Clause
4. README