Skip to content

About

Regular expressions for Nitpick — linear time guaranteed on every pattern and every input. Automata-based, zero dependency, no libc, no syscalls. Catastrophic backtracking is not slow here; it is impossible.

Topics

Resources

Contributing

Stars

1 star

Watchers

1 watching

Forks

Latest commit

 

History

226 Commits

Folders and files

Repository files navigation

nregex

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 compiler c9baa9e, 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 in src/core/ are built and audited — and cycle 0.1.0 laid the parser's pieces in src/syntax/: the closed list of pattern errors, the byte cursor and the AST arena. Cycle 0.1.0b moved the pinned compiler to 5fbaf4a, 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 bounded Vec's element type by the prelude's Copy, 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's regex reads it or refusing it with what to write. Cycle 0.1.4 reads every escape — \x{1F600}, \u00E9, \A, \b — and the flags i, m, s, x and u, 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, and regex_escape writes 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 in src/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, and i. Cycle 0.2.1a moved the pinned compiler to 7e91730, 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) and abc, [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 to c9baa9e, which refuses a keyword as a field's name: the parser's explicit stack is frames now, 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 in meta/specs/ and the plan in meta/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.


Why the guarantee is the whole design

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.

What follows from it

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.


What it will provide

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.


Layout

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

Specification

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.

Plan

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/.

Requirements

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.

Licence

Apache 2.0. See LICENSE.

About

Regular expressions for Nitpick — linear time guaranteed on every pattern and every input. Automata-based, zero dependency, no libc, no syscalls. Catastrophic backtracking is not slow here; it is impossible.

Topics

Resources

Contributing

Stars

1 star

Watchers

1 watching

Forks

Releases

Packages

Contributors

Languages