HACKING.md

Your friendly guide to hacking and navigating the regex library.

This guide assumes familiarity with Rust and Cargo, and at least a perusal of the user facing documentation for this crate.

If you're looking for background on the implementation in this library, then you can do no better than Russ Cox's article series on implementing regular expressions using finite automata: https://swtch.com/~rsc/regexp/

Architecture overview

As you probably already know, this library executes regular expressions using finite automata. In particular, a design goal is to make searching linear with respect to both the regular expression and the text being searched. Meeting that design goal on its own is not so hard and can be done with an implementation of the Pike VM (similar to Thompson's construction, but supports capturing groups), as described in: https://swtch.com/~rsc/regexp/regexp2.html --- This library contains such an implementation in src/pikevm.rs.

Making it fast is harder. One of the key problems with the Pike VM is that it can be in more than one state at any point in time, and must shuffle capture positions between them. The Pike VM also spends a lot of time following the same epsilon transitions over and over again. We can employ one trick to speed up the Pike VM: extract one or more literal prefixes from the regular expression and execute specialized code to quickly find matches of those prefixes in the search text. The Pike VM can then be avoided for most the search, and instead only executed when a prefix is found. The code to find prefixes is in the regex-syntax crate (in this repository). The code to search for literals is in src/literals.rs. When more than one literal prefix is found, we fall back to an Aho-Corasick DFA using the aho-corasick crate. For one literal, we use a variant of the Boyer-Moore algorithm. Both Aho-Corasick and Boyer-Moore use memchr when appropriate. The Boyer-Moore variant in this library also uses elementary frequency analysis to choose the right byte to run memchr with.

Of course, detecting prefix literals can only take us so far. Not all regular expressions have literal prefixes. To remedy this, we try another approach to executing the Pike VM: backtracking, whose implementation can be found in src/backtrack.rs. One reason why backtracking can be faster is that it avoids excessive shuffling of capture groups. Of course, backtracking is susceptible to exponential runtimes, so we keep track of every state we've visited to make sure we never visit it again. This guarantees linear time execution, but we pay for it with the memory required to track visited states. Because of the memory requirement, we only use this engine on small search strings and small regular expressions.

Lastly, the real workhorse of this library is the "lazy" DFA in src/dfa.rs. It is distinct from the Pike VM in that the DFA is explicitly represented in memory and is only ever in one state at a time. It is said to be "lazy" because the DFA is computed as text is searched, where each byte in the search text results in at most one new DFA state. It is made fast by caching states. DFAs are susceptible to exponential state blow up (where the worst case is computing a new state for every input byte, regardless of what's in the state cache). To avoid using a lot of memory, the lazy DFA uses a bounded cache. Once the cache is full, it is wiped and state computation starts over again. If the cache is wiped too frequently, then the DFA gives up and searching falls back to one of the aforementioned algorithms.

All of the above matching engines expose precisely the same matching semantics. This is indeed tested. (See the section below about testing.)

The following sub-sections describe the rest of the library and how each of the matching engines are actually used.

Parsing

Regular expressions are parsed using the regex-syntax crate, which is maintained in this repository. The regex-syntax crate defines an abstract syntax and provides very detailed error messages when a parse error is encountered. Parsing is done in a separate crate so that others may benefit from its existence, and because it is relatively divorced from the rest of the regex library.

The regex-syntax crate also provides sophisticated support for extracting prefix and suffix literals from regular expressions.

Compilation

The compiler is in src/compile.rs. The input to the compiler is some abstract syntax for a regular expression and the output is a sequence of opcodes that matching engines use to execute a search. (One can think of matching engines as mini virtual machines.) The sequence of opcodes is a particular encoding of a non-deterministic finite automaton. In particular, the opcodes explicitly rely on epsilon transitions.

Consider a simple regular expression like a|b. Its compiled form looks like this:

000 Save(0)
001 Split(2, 3)
002 'a' (goto: 4)
003 'b'
004 Save(1)
005 Match

The first column is the instruction pointer and the second column is the instruction. Save instructions indicate that the current position in the input should be stored in a captured location. Split instructions represent a binary branch in the program (i.e., epsilon transitions). The instructions 'a' and 'b' indicate that the literal bytes 'a' or 'b' should match.

In older versions of this library, the compilation looked like this:

000 Save(0)
001 Split(2, 3)
002 'a'
003 Jump(5)
004 'b'
005 Save(1)
006 Match

In particular, empty instructions that merely served to move execution from one point in the program to another were removed. Instead, every instruction has a goto pointer embedded into it. This resulted in a small performance boost for the Pike VM, because it was one fewer epsilon transition that it had to follow.

There exist more instructions and they are defined and documented in src/prog.rs.

Compilation has several knobs and a few unfortunately complicated invariants. Namely, the output of compilation can be one of two types of programs: a program that executes on Unicode scalar values or a program that executes on raw bytes. In the former case, the matching engine is responsible for performing UTF-8 decoding and executing instructions using Unicode codepoints. In the latter case, the program handles UTF-8 decoding implicitly, so that the matching engine can execute on raw bytes. All matching engines can execute either Unicode or byte based programs except for the lazy DFA, which requires byte based programs. In general, both representations were kept because (1) the lazy DFA requires byte based programs so that states can be encoded in a memory efficient manner and (2) the Pike VM benefits greatly from inlining Unicode character classes into fewer instructions as it results in fewer epsilon transitions.

N.B. UTF-8 decoding is built into the compiled program by making use of the utf8-ranges crate. The compiler in this library factors out common suffixes to reduce the size of huge character classes (e.g., \pL).

A regrettable consequence of this split in instruction sets is we generally need to compile two programs; one for NFA execution and one for the lazy DFA.

In fact, it is worse than that: the lazy DFA is not capable of finding the starting location of a match in a single scan, and must instead execute a backwards search after finding the end location. To execute a backwards search, we must have compiled the regular expression in reverse.

This means that every compilation of a regular expression generally results in three distinct programs. It would be possible to lazily compile the Unicode program, since it is never needed if (1) the regular expression uses no word boundary assertions and (2) the caller never asks for sub-capture locations.

Execution

At the time of writing, there are four matching engines in this library:

1. The Pike VM (supports captures).
2. Bounded backtracking (supports captures).
3. Literal substring or multi-substring search.
4. Lazy DFA (no support for Unicode word boundary assertions).

Only the first two matching engines are capable of executing every regular expression program. They also happen to be the slowest, which means we need some logic that (1) knows various facts about the regular expression and (2) knows what the caller wants. Using this information, we can determine which engine (or engines) to use.

The logic for choosing which engine to execute is in src/exec.rs and is documented on the Exec type. Exec values contain regular expression Programs (defined in src/prog.rs), which contain all the necessary tidbits for actually executing a regular expression on search text.

For the most part, the execution logic is straight-forward and follows the limitations of each engine described above pretty faithfully. The hairiest part of src/exec.rs by far is the execution of the lazy DFA, since it requires a forwards and backwards search, and then falls back to either the Pike VM or backtracking if the caller requested capture locations.

The Exec type also contains mutable scratch space for each type of matching engine. This scratch space is used during search (for example, for the lazy DFA, it contains compiled states that are reused on subsequent searches).

Programs

A regular expression program is essentially a sequence of opcodes produced by the compiler plus various facts about the regular expression (such as whether it is anchored, its capture names, etc.).

The regex! macro (or why regex::internal exists)

The regex! macro is defined in the regex_macros crate as a compiler plugin, which is maintained in this repository. The regex! macro compiles a regular expression at compile time into specialized Rust code.

The regex! macro was written when this library was first conceived and unfortunately hasn't changed much since then. In particular, it encodes the entire Pike VM into stack allocated space (no heap allocation is done). When regex! was first written, this provided a substantial speed boost over so-called "dynamic" regexes compiled at runtime, and in particular had much lower overhead per match. This was because the only matching engine at the time was the Pike VM. The addition of other matching engines has inverted the relationship; the regex! macro is almost never faster than the dynamic variant. (In fact, it is typically substantially slower.)

In order to build the regex! macro this way, it must have access to some internals of the regex library, which is in a distinct crate. (Compiler plugins must be part of a distinct crate.) Namely, it must be able to compile a regular expression and access its opcodes. The necessary internals are exported as part of the top-level internal module in the regex library, but is hidden from public documentation. In order to present a uniform API between programs build by the regex! macro and their dynamic analoges, the Regex type is an enum whose variants are hidden from public documentation.

In the future, the regex! macro should probably work more like Ragel, but it's not clear how hard this is. In particular, the regex! macro should be able to support all the features of dynamic regexes, which may be hard to do with a Ragel-style implementation approach. (Which somewhat suggests that the regex! macro may also need to grow conditional execution logic like the dynamic variants, which seems rather grotesque.)

Testing

A key aspect of any mature regex library is its test suite. A subset of the tests in this library come from Glenn Fowler's AT&T test suite (its online presence seems gone at the time of writing). The source of the test suite is located in src/testdata. The scripts/regex-match-tests.py takes the test suite in src/testdata and generates tests/matches.rs.

There are also many other manually crafted tests and regression tests in tests/tests.rs. Some of these tests were taken from RE2.

The biggest source of complexity in the tests is related to answering this question: how can we reuse the tests to check all of our matching engines? One approach would have been to encode every test into some kind of format (like the AT&T test suite) and code generate tests for each matching engine. The approach we use in this library is to create a Cargo.toml entry point for each matching engine we want to test. The entry points are:

• tests/test_plugin.rs - tests the regex! macro
• tests/test_default.rs - tests Regex::new
• tests/test_default_bytes.rs - tests bytes::Regex::new
• tests/test_nfa.rs - tests Regex::new, forced to use the NFA algorithm on every regex.
• tests/test_nfa_bytes.rs - tests Regex::new, forced to use the NFA algorithm on every regex and use arbitrary byte based programs.
• tests/test_nfa_utf8bytes.rs - tests Regex::new, forced to use the NFA algorithm on every regex and use UTF-8 byte based programs.
• tests/test_backtrack.rs - tests Regex::new, forced to use backtracking on every regex.
• tests/test_backtrack_bytes.rs - tests Regex::new, forced to use backtracking on every regex and use arbitrary byte based programs.
• tests/test_backtrack_utf8bytes.rs - tests Regex::new, forced to use backtracking on every regex and use UTF-8 byte based programs.

The lazy DFA and pure literal engines are absent from this list because they cannot be used on every regular expression. Instead, we rely on tests/test_dynamic.rs to test the lazy DFA and literal engines when possible.

Since the tests are repeated several times, and because cargo test runs all entry points, it can take a while to compile everything. To reduce compile times slightly, try using cargo test --test default, which will only use the tests/test_default.rs entry point.

N.B. To run tests for the regex! macro, use:

cargo test --manifest-path regex_macros/Cargo.toml

Benchmarking

The benchmarking in this crate is made up of many micro-benchmarks. Currently, there are two primary sets of benchmarks: the benchmarks that were adopted at this library's inception (in benches/src/misc.rs) and a newer set of benchmarks meant to test various optimizations. Specifically, the latter set contain some analysis and are in benches/src/sherlock.rs. Also, the latter set are all executed on the same lengthy input whereas the former benchmarks are executed on strings of varying length.

There is also a smattering of benchmarks for parsing and compilation.

Benchmarks are in a separate crate so that its dependencies can be managed separately from the main regex crate.

Benchmarking follows a similarly wonky setup as tests. There are multiple entry points:

• bench_rust_plugin.rs - benchmarks the regex! macro
• bench_rust.rs - benchmarks Regex::new
• bench_rust_bytes.rs benchmarks bytes::Regex::new
• bench_pcre.rs - benchmarks PCRE
• bench_onig.rs - benchmarks Oniguruma

The PCRE and Oniguruma benchmarks exist as a comparison point to a mature regular expression library. In general, this regex library compares favorably (there are even a few benchmarks that PCRE simply runs too slowly on or outright can't execute at all). I would love to add other regular expression library benchmarks (especially RE2).

If you're hacking on one of the matching engines and just want to see benchmarks, then all you need to run is:

$ ./run-bench rust

If you want to compare your results with older benchmarks, then try:

$ ./run-bench rust | tee old
$ ... make it faster
$ ./run-bench rust | tee new
$ cargo-benchcmp old new --improvements

The cargo-benchcmp utility is available here: https://github.com/BurntSushi/cargo-benchcmp

The run-bench utility can run benchmarks for PCRE and Oniguruma too. See ./run-bench --help.