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:

    $ ./bench/run rust

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

    $ ./bench/run rust | tee old

    $ ... make it faster

    $ ./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 https://github.com/rust-lang/rust/issues/15347 for more info

about generating developer docs for internal use.