std::regex Is the RE2 Dialect; a Regular Expression Is Typed by Its Engine, a Pattern the Build Knows Is Compiled Down a Ladder of Engines and Run by std’s Code Specialised for It, a Pattern That Arrives at Run Time Runs on Rust’s Automata CratesStatus: Accepted
Date: October 28, 2026
Answers: whether and how std offers regular expressions (#673): which dialect, what type a regular expression has, what the build does with a pattern it knows, which engine runs it, and what a pattern that arrives at run time runs on
Supersedes / Related: ADR-specialization-1 (comptime?, @unroll, branches decided while building, a result type computed from a comptime parameter), ADR-374 (a position in a text, text::Match), ADR-375 (ByteSet, Seq, positions as facts), ADR-377 (std::simd), ADR-296 D7 (a grammar has no regex terminals), D42 (a std type over a crate’s table), ADR-318 D5-D6 (a std type crosses into a comptime by its constant column; a std function runs at build time), ADR-311 (a build-time value crosses in its view form), ADR-333 D3 (a comptime parameter), ADR-287 (comptime), ADR-295 (a trait is not a type), ADR-218 (unsafe lives in crates/unsafe), ADR-188 (a backslash is written \\)
comptime DATE = regex::compile("(\\d{4})-(\\d{2})-(\\d{2})")
fn year(line: String) -> String? {
let c = DATE.captures(line) ?? return null
return c.group(1)?.text().clone()
}A regular expression is a pattern for a shape of text; an engine finds where
the shape occurs and which parts matched which group. std has find,
split, ByteSet and grammar, and no engine. A grammar is a parser:
ordered choice and a repetition that never gives back what it took, so the
pattern a*a accepts aaa as a regular expression and never as a grammar
rule.
A library sees a pattern when the program runs. A compiler sees most patterns while it builds - they are literals - and can do what no library can: choose an engine for the pattern’s shape, emit code made for it, and leave nothing to do when the first text arrives.
| when the pattern is compiled | engines | groups | |
|---|---|---|---|
| Perl, Python, Java, PCRE | run time | backtracking, exponential in the worst case | yes, with backreferences |
| RE2, Go | run time | DFA built lazily, NFA simulation, literal prefilter | NFA simulation or one-pass |
Rust regex (regex-automata) |
run time | literal prefilter, full DFA only for small patterns (by default up to 30 NFA states and 40 KiB), else lazy DFA, else Pike VM | Pike VM, one-pass or bounded backtracking over the matched span |
| re2c, logos | build time | DFA emitted as code | re2c: tagged DFA (Laurikari), registers written on transitions |
| C++ CTRE | build time (templates) | a matcher instantiated per pattern; the pattern is part of the type | yes |
| Hyperscan | ahead of the scan, into a database | literals with SIMD, DFAs, bit-parallel NFAs in vector registers | no |
What regex-automata 0.4 offers to a build, read in its source: a dense or
sparse DFA serializes to bytes and is used from a borrowed slice of u32
words without a copy (from_bytes, which validates, or from_bytes_unchecked,
which reads only the header); the Thompson NFA, the Pike VM, the one-pass DFA,
the lazy DFA and meta::Regex do not serialize. The NFA’s states refer to each
other by index; its transition lists, its names and its handle are separate
heap blocks, so it cannot be laid down as bytes and used in place.
regex crate writes it.A pattern has no backreference and no lookaround. A search takes time
proportional to the text times the pattern, whatever the pattern is. A match is
the leftmost one; among those, the one the pattern prefers (alternatives in
the order written, a repetition greedy unless marked lazy). Text is matched by
Unicode scalar; \d, \w and \s are Unicode classes, and (?-u) turns that
off for a class that means ASCII. (?:…) is a group that does not capture.
Why. A pattern a program receives at run time must not be able to stop the program, and every user already knows this dialect. Rejected: a backtracking engine (exponential time on a pattern an input chooses); a dialect of our own.
Cost, named: a pattern that needs a backreference is written in code. Adding the feature later never changes a pattern that works.
\\."\\d{4}", as Part I 2.5 already prints it. A raw-string form is not decided
here (ADR-188 §4).
regex::Regex[E], typed by its engine; a collection of different ones is regex::Any.E is the engine, a type implementing the trait regex::Engine: one per
stage of D6 (regex::Literal, regex::OnePass, regex::Dfa,
regex::TaggedDfa, regex::BitNfa, regex::FlatNfa) and regex::Dynamic for
a pattern compiled at run time (D8). Each engine’s calls are its own; a call
chooses no engine while the program runs. A function over any regular
expression is generic, fn f[E: regex::Engine](re: regex::Regex[E]), and is
emitted once per engine. regex::Any is an enum with one variant per engine,
re.any() makes one, and its calls choose the engine at run time - the one
place where that happens, and only where the program writes it.
| call | gives |
|---|---|
re.is_match(s) |
bool |
re.find(s; from: text::Pos) |
text::Match? |
re.find_all(s) |
Seq[text::Match], left to right, not overlapping |
re.captures(s; from: text::Pos) |
regex::Captures? |
c.group(i), c.named("year") |
text::Match? (group 0 is the whole match) |
re.replace_all(s, with) |
String; with may name groups as $1 or ${year} |
re.split(s) |
Seq[ref String], the pieces between matches |
Every position is a text::Pos of the searched text (ADR-374),
and a match is text::Match, so before, after and between cut with it.
A Regex is read-only and shared between threads. It searches a String;
matching a Bytes is not decided here.
Two ways in. regex::compile(comptime pattern) -> regex::Regex[E] takes a
pattern the build knows; the build chooses E from the pattern
(ADR-specialization-1 D7). A type written where the
result is received is a contract: comptime DATE: regex::Regex[regex::Dfa] =
regex::compile("…") is refused when the pattern needs another engine.
regex::dynamic(pattern) -> regex::Regex[regex::Dynamic] throws regex::Error
takes a pattern known only at run time. regex::compile with a pattern that is
not a build-time value is refused at the call (ADR-333 D3), and the help names
regex::dynamic.
Why. Which engine a pattern needs is a fact the build knows; held in the
type, it costs nothing while the program runs, and engines added later are
types added, not cases added. Rejected: one type whose calls match on
the engine (a branch on every call, also where every value has the same
engine); a list of values typed by the trait (a trait is not a type,
ADR-295); one compile for both stages (its result’s type would
depend on whether a caller wrote comptime); the pattern itself as the type’s
parameter, Regex[P] (every pattern a different type).
std’s code runs specialised for it.regex::compile(p) with a build-time text - a literal, a text composed of
other comptime values, asset("date.re") - is a program in the pattern
language. The build parses and checks it (a pattern that does not parse stops
the build with the engine’s own message, NK1244), chooses its engine (D6) and
lays down its tables (D7). The code that runs is std’s own, written once in
Nikaia: the calls of D3 take comptime? self, so a call on a known pattern
calls a copy made for that pattern, in which the engine’s states are constants
and its loops over them are unrolled
(ADR-specialization-1 D1-D4). A pattern known only
when the program runs is input, compiled by regex::dynamic (D8).
Why. Part II 10.1 forbids code nobody wrote; the
pattern is code the user wrote, in another notation, and the matcher is code
std wrote, specialised for it by the rules every library has. Rejected:
a case for regular expressions in the compiler’s lowering (the next library
with a pattern language would need its own); treating a known pattern as a
value compiled at run time (it repeats work the build could do, every time the
program starts); tables only, never code (it gives away the fastest form for
the small patterns that are most of them).
regex::Dynamic (D8), is the oracle: a pattern compiled by compile and by
dynamic gives the same matches on the same text, checked by a
differential test in Nikaia and by fuzzing. The test runs each pattern
through every engine that accepts it, not only the one the build
chooses, so that an engine chosen rarely is checked as often as one chosen
always. A crate version that disagrees with the specification is a finding,
not the new meaning.docs/measuring.md says.Regex is not read.| stage | engine | for | what runs |
|---|---|---|---|
| S0 | Literal |
a literal, or a few alternatives of literals | find, ByteSet, a literal search; no automaton |
| S1 | OnePass |
a pattern with one way on at every byte | straight-line code, groups included, no set of states |
| S2 | Dfa |
a DFA, forward for a match’s end and reverse, anchored at that end, for its start | under the unroll limit, the DFA as code: a block per state, a comparison per byte range, a state that loops on a set of bytes skipping them with ByteSet; over it, or for a pattern that reached the call through a run-time value, the DFA’s table, read in place (D7) - one engine, @unroll(up_to: N) deciding (ADR-specialization-1 D3) |
| S3 | TaggedDfa |
capturing groups, not one-pass, a tagged DFA under its limit | a DFA whose transitions write positions into registers; no NFA at run time |
| S4 | BitNfa |
up to as many NFA positions as the widest vector the build has | one bit a position, a step a few word or vector operations per byte (Glushkov, as Hyperscan) |
| S5 | FlatNfa |
anything larger | a flat NFA read in place, run by an NFA simulation and a lazily built DFA of our own |
Every engine gives the match D1 defines, and the choice of engine never
changes which match that is. A match is found in two steps. Locating it -
whether there is one, where it ends, where it starts - is done by an engine
that searches unanchored with D1’s preference: S0, a literal set searched with
the alternatives’ order as preference (leftmost-first, never the longest or the
first found); S2, forward for the end and reverse, anchored at that end, for the
start; S5. Extracting groups is done over the located span, anchored at its
start, by S1, S3 or S5. S1 and S3 are anchored by nature - a one-pass or tagged
DFA cannot search unanchored, since the prefix that makes a search unanchored
((?s-u:.)*?) leaves no pattern one-pass - and run alone only for a pattern
anchored at its start (^…). S4 answers is_match and finds candidates that S2
or S5 confirm, until it is shown to give D1’s preferred end itself.
The engine is chosen by the pattern and the limits alone. The limits are
numbers the build can be given; their defaults are set by measurement. A stage
not yet built falls to the next one that is; under all of them is
regex::Dynamic built at run time from the already checked pattern, which is
not a stage but the floor.
Why. The crate’s own default says a full DFA is a small-pattern
optimisation; the expensive cases - a DFA that grows with every position
((a|b)*a(a|b){20}), groups that are not one-pass - are where an NFA is
simulated at run time, and they are also where knowing the pattern ahead
helps most: a tagged DFA removes the NFA from group extraction, a bit-parallel
NFA turns the simulation into word operations. A lazily built DFA, the crate’s
answer to size, builds the states the text touches while the program runs; it
stays as the last stage, not as the answer.
A table crosses as an aligned ref Array[u32] (ADR-311) and is
read where it lies. It is written for the target, not for the host the
build runs on: the crate’s DFA is serialized in the target’s byte order
(to_bytes_little_endian or to_bytes_big_endian) and its words are packed in
the same order; an engine of our own crosses its words as integer literals,
which the language below lays out for the target. No table depends on the
host’s pointer width: the crate stores its counts as u32. The crate’s DFA is opened with
from_bytes_unchecked, which reads its header and nothing else; the bytes come
from the same build with the same crate, and the header carries its label, its
byte order, its version and its alignment. That header is the only check at run
time: a table written for another target is an error when it is opened, never
a wrong match.
The call is unsafe and lives in a crate of its own under crates/unsafe
(ADR-218). An engine of our own (S3-S5) is laid out flat: states
as u32 words, references as indices into the same table, names in one byte
run with offsets - nothing that must be rebuilt, checked or relocated before it
is read. The crate’s NFA is not used for a known pattern: it is heap blocks
joined by pointers and cannot lie in the binary.
Why. D5.3. A table that must be rebuilt or validated on first use is work the build has already done. Rejected: replaying the crate’s NFA through its builder at run time (a pass over every state, each time the program starts); dumping the crate’s NFA’s memory (its blocks hold addresses of the process that built them, its layout is not promised, and its handle writes a count).
regex::Regex[regex::Dynamic] wraps regex-automata’s meta::Regex (with
regex-syntax), as std’s maps wrap hashbrown’s table
(ADR-296 D42). No type of the crate appears in a program, in the
ledger or in a message. The crate is pinned in Cargo.lock; a version that
changes what a pattern matches is caught by D5.1 before it is taken.
Why. A run-time pattern has nothing to gain from the build; the crate is the tuned answer for it, and the oracle the engines of our own are checked against.
--comptime says what each known pattern became.For each pattern the build compiled: its engine, the sizes (DFA bytes, NFA states, tagged registers), which limit sent it further down, whether a group stage was built because the pattern has capturing groups, and the prefilter; for each call, the copy it calls or why it calls the ordinary function (ADR-specialization-1 D8). A pattern on the floor is listed as such.
Why. A pattern changes engine silently when it grows; the type and the report are where that is seen.
| part | where it runs | by whom |
|---|---|---|
| parsing a pattern, its error message | build; run time for dynamic |
regex-syntax |
| Unicode classes | build; run time for dynamic |
regex-syntax |
| literals for a prefilter | build | regex-syntax |
| the NFA | build | regex-automata; read through its public states into our flat form |
| determinising and minimising a DFA | build | regex-automata |
| whether a pattern is one-pass | build | regex-automata’s one-pass builder, which fails on a pattern that is not |
| S0 prefilter | run time | find, ByteSet; aho-corasick’s Teddy for many literals |
| S1, S2 as code | run time | std, specialised per pattern |
| S2 as a table | run time | regex-automata’s search over its own table, until a measurement says ours pays |
| S3-S5 | build and run time | std |
| a run-time pattern | run time | regex-automata’s meta::Regex |
Why. The crates define the dialect (D1) and do years of work on parsing, Unicode and determinising that a build runs once; what runs per byte for a pattern the build knows is where knowing it pays (D4). A parser of our own would have to match the crate’s in every flag and message, and could only differ from it.
dsl regex::Regex { (?P<year>\d{4}) } eod giving a result
struct with a field per named group is a record of its own.grammar stay a goal (ADR-296 D7).std gains regex-automata, regex-syntax and, through them,
aho-corasick; Cargo.lock is where their versions are decided.