A regular-expression library for Nitpick — the safety-critical systems language. No dependencies, no libc, no C. It makes no syscall at all: it is pure computation over bytes, and that is most of what makes the guarantee below possible.
The guarantee, in one sentence: a search takes time linear in the length of the haystack, on every pattern, on every input, always.
Status: cycle 0.2, the HIR, closed on 2026-10-20 — its eight parts, the arena, the desugaring, the adoption of compiler
7e91730, the repetition product, normalisation, the computed properties, literal extraction and the adoption of compilerc9baa9e, and then its close; cycle 0.1, the pattern parser, closed on 2026-10-08. Cycle 0.0, the foundations, closed on 2026-09-26 — the language probes, the test harness and the storage primitives insrc/core/are built and audited — and cycle 0.1.0 laid the parser's pieces insrc/syntax/: the closed list of pattern errors, the byte cursor and the AST arena. Cycle 0.1.0b moved the pinned compiler to5fbaf4a, and cycle 0.1.1 parses the core grammar — literals, groups, alternation and quantifiers — into an AST, refusing a bad pattern with the byte it is at and a sentence saying what to write instead. Cycle 0.1.1b boundedVec's element type by the prelude'sCopy, so the compiler refuses an owning element wherever one is written. Cycle 0.1.2 bounded the parser's nesting: a pattern nested more than 250 groups deep is refused at the(that goes too deep, never a blown stack, and no function in the library calls itself. Cycle 0.1.3 parses classes — ranges, nested classes,&&--~~,\d,\p{…}and[:alpha:]— reading every shape as Rust'sregexreads it or refusing it with what to write. Cycle 0.1.4 reads every escape —\x{1F600},\u00E9,\A,\b— and the flagsi,m,s,xandu, scoped to their group, refusing what the engines read two ways. Cycle 0.1.5 refuses what nregex declines — a backreference, lookaround,\Q…\E— each by its own kind, with a sentence saying why and what to write instead, andregex_escapewrites any text as a pattern that matches exactly it. Cycle 0.1.6 closes the cycle on its audit, which found one wrong answer — an escaped text read as a POSIX class straight after a nested class's[— and:is escaped now; and a fuzz pass of 120 000 seeded patterns holds the parser to its offsets on every run. Cycle 0.2.0 laid the HIR's arena insrc/hir/— nine kinds of node that own nothing, read and written through accessors that check every index — and wrote a HIR as one line of text that reads back to the same bytes. Cycle 0.2.1 builds the HIR from a parsed pattern — quantifiers, groups, anchors,.and classes written as ranges, every flag erased into what it means — and stops where cycle 0.3 must resolve or fold: a Perl or POSIX class, a property, a class's^or operators, andi. Cycle 0.2.1a moved the pinned compiler to7e91730, where a string's bytes are a read-only view: every slice the library takes says so, and LLVM is 20.1.8. Cycle 0.2.2 refuses a pattern whose nested repetitions would multiply past 100 000 copies —((a{1000}){1000}){1000}at its second{1000}— before any memory is asked for its expansion. Cycle 0.2.3 writes a HIR in a normal form, so patterns that differ only in how they are written —a(?:bc)andabc,[ba]and[a-b]— are one HIR and one line of text, while nothing that changes what a pattern matches is joined. Cycle 0.2.4 computes four facts of every node once, for the engines to ask — whether it may match the empty string, whether every match is anchored at the haystack's start or at its end, and whether it is a literal or a union of them. Cycle 0.2.5 extracts, for the prefilters to scan for, the bytes every match begins with, the bytes a match can begin with and a literal every match holds — each one only where it is certain, so a pattern it cannot read is searched slower, never wrongly. Cycle 0.2.5a moved the pinned compiler toc9baa9e, which refuses a keyword as a field's name: the parser's explicit stack isframesnow, and nothing else the library holds moved. Cycle 0.2.6 closed the cycle: a tree check holds every kind of HIR node to the code that builds it, and a HIR is compared by its text. Cycle 0.3, Unicode, is next. Nothing matches a pattern yet. The specification set is inmeta/specs/and the plan inmeta/roadmap/, written in the same order and by the same discipline the compiler used — specs first, then a cycle map, then execution-grade subcycles, then code.
Every regex engine built on backtracking — PCRE, Perl, Python's re, Java's,
JavaScript's, .NET's — can be made to run for longer than the universe has
existed by an input of a few dozen characters against a pattern of a few dozen
characters. (a+)+$ against aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! is the textbook
one. It is called ReDoS, it has taken down Cloudflare and Stack Overflow, and
it is a denial of service triggered by data somebody else controls.
In a language whose entire proposition is that a failure is a controlled stop
chosen by the programmer, a library that lets a remote string hang the process
is not a library that belongs in it. So nregex is built on finite automata
— Thompson construction, a Pike VM, a lazy DFA — where the work is bounded by
the product of the pattern size and the haystack size and cannot be otherwise.
This is the choice RE2 and Rust's regex made, for the same reason.
The price is stated plainly and is not softened: there are no backreferences
and no lookaround. Backreferences describe no regular language, and they are
what makes backtracking unavoidable. Lookaround is different: finite automata
can match it in linear time, by algorithms published in 2024, but nregex's
automata read none of it and a search allocates nothing, so it is refused as
well (meta/specs/SAFETY.md S-2, RX-218). A pattern
needing either is refused at compile time, by name, with the position — never
accepted and then slow.
Matching cannot fail and cannot trap. Every way a pattern can be wrong is
found when it is compiled. Once you hold a Regex, a search returns an answer
or the absence of one; there is no error path, no allocation, and no
possibility of a stop. That is why importing this library costs your program's
failsafe exactly one arm.
The same pattern and the same haystack give the same answer, always. The engine chosen internally — Pike VM, lazy DFA, one-pass, prefiltered — is a performance decision that can never change a result, and the test suite proves it by running every case through every engine and requiring agreement.
Nothing is hidden. The mutable state a lazy DFA needs lives in a Cache
value the caller owns and passes in, so a Regex is immutable, shareable
across threads with no lock, and a search allocates nothing.
Every bound is named, stated, and tested — program size, nesting depth, repetition expansion, DFA cache bytes. A pattern that would exceed one is refused when it is compiled, and the DFA cache falls back to the Pike VM rather than growing.
| Layer | Contents |
|---|---|
| syntax | the pattern parser — an explicit stack, never native recursion, with byte-accurate error positions |
| hir | desugaring and normalisation into a high-level intermediate: literals extracted, classes computed, repetitions bounded |
| unicode | \p{…} properties, scripts, simple case folding, and the class ranges — from generated, committed, version-pinned tables |
| compile | codepoint ranges to UTF-8 byte automata, alphabet compression, and the NFA program |
| engine | the Pike VM (the reference), a lazy DFA, literal prefilters, and a deterministic meta-engine that chooses between them |
| api | Regex, Cache, Match, Captures, iterators, and template replacement |
Matching is over uint8[], so a haystack may be a network buffer, a mapped
file, or anything else that is bytes — not only a validated string.
src/ # THE LIBRARY — Nitpick source only
core/ # storage primitives, bitsets, named limits
syntax/ # the pattern parser
hir/ # desugaring, normalisation, literal extraction
unicode/ # GENERATED property and case-folding tables, and their range type
compile/ # HIR -> NFA program, UTF-8 automata, alphabet compression
engine/ # Pike VM, lazy DFA, prefilters, the meta-engine
api/ # the public surface
tests/ # probe, conformance, unit, oracle, rejection, fixtures
examples/ # runnable demonstrations
harness/ # the Python build and test runner, until `npkg` can build a library
tools/ # generators — the Unicode tables; the fuzzer; the corpus fetcher
meta/specs/ # the design authority
meta/roadmap/ # the plan, in numbered cycles
docs/ # user-facing documentation, written at 1.0
meta/specs/ is the authority on behaviour, and
meta/DECISIONS.md records every settled design decision
with its reasoning — start there when something looks unusual, because it is
recorded why.
meta/roadmap/ROADMAP.md is the cycle map. A cycle
is a folder, a subcycle is a file inside it, and a finished cycle moves to
meta/roadmap/done/.
The Nitpick compiler and LLVM 20.1.8 — the same toolchain the compiler pins. The library itself makes no syscall and assumes no operating system; only the test harness is Linux-specific.
Apache 2.0. See LICENSE.