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

The regex! macro no longer exists. It was developed in a bygone era as a compiler plugin during the infancy of the regex crate. Back then, then only matching engine in the crate was the Pike VM. The regex! macro was, itself, also a Pike VM. The only advantages it offered over the dynamic Pike VM that was built at runtime were the following:

1. Syntax checking was done at compile time. Your Rust program wouldn't compile if your regex didn't compile.
2. Reduction of overhead that was proportional to the size of the regex. For the most part, this overhead consisted of heap allocation, which was nearly eliminated in the compiler plugin.

The main takeaway here is that the compiler plugin was a marginally faster version of a slow regex engine. As the regex crate evolved, it grew other regex engines (DFA, bounded backtracker) and sophisticated literal optimizations. The regex macro didn't keep pace, and it therefore became (dramatically) slower than the dynamic engines. The only reason left to use it was for the compile time guarantee that your regex is correct. Fortunately, Clippy (the Rust lint tool) has a lint that checks your regular expression validity, which mostly replaces that use case.

Additionally, the regex compiler plugin stopped receiving maintenance. Nobody complained. At that point, it seemed prudent to just remove it.

Will a compiler plugin be brought back? The future is murky, but there is definitely an opportunity there to build something that is faster than the dynamic engines in some cases. But it will be challenging! As of now, there are no plans to work on this.

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_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.
• tests/test_crates_regex.rs - tests to make sure that all of the backends behave in the same way against a number of quickcheck generated random inputs. These tests need to be enabled through the RUST_REGEX_RANDOM_TEST environment variable (see below).

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.

The random testing takes quite a while, so it is not enabled by default. In order to run the random testing you can set the RUST_REGEX_RANDOM_TEST environment variable to anything before invoking cargo test. Note that this variable is inspected at compile time, so if the tests don't seem to be running, you may need to run cargo clean.

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 bench/src/misc.rs) and a newer set of benchmarks meant to test various optimizations. Specifically, the latter set contain some analysis and are in bench/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.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:

$ (cd bench && ./run rust)

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

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

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

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

Dev Docs

When digging your teeth into the codebase for the first time, the crate documentation can be a great resource. By default rustdoc will strip out all documentation of private crate members in an effort to help consumers of the crate focus on the interface without having to concern themselves with the implementation. Normally this is a great thing, but if you want to start hacking on regex internals it is not what you want. Many of the private members of this crate are well documented with rustdoc style comments, and it would be a shame to miss out on the opportunity that presents. You can generate the private docs with:

$ rustdoc --crate-name docs src/lib.rs -o target/doc -L target/debug/deps --no-defaults --passes collapse-docs --passes unindent-comments

Then just point your browser at target/doc/regex/index.html.

See rust-lang/rust#15347 for more info about generating developer docs for internal use.