Skip to content

Softwareirregex

Technical report

What is irregex?

Irregex is the engine underneath gist, relate, and blast. It is not a command-line search product wearing a library costume. It is the toolkit a search product is built from: a linear regular-expression engine, a deliberate PCRE2 escape hatch, literal scanners, candidate indexes, a freshness law, compiled queries, ranking, corpus machinery, and a small C ABI that carries the same semantics into Python, Rust, Go, Zig, and anything else that can call C.

That dividing line matters. A product owns argv, presentation, daemon lifecycle, and the promises attached to an executable. Irregex owns the machines beneath those promises: which bytes may match, which files may be skipped, and when an accelerator must decline rather than risk becoming an authority.

The default engine is linear in the Thompson tradition, so a pathological pattern cannot detonate on an unlucky input. Lookaround and backreferences are not regular in Kleene's sense, so they go to a vendored PCRE2 JIT when the caller explicitly asks for that grammar. Nobody gets to promise both guarantees without saying which one they handed you.

Installation

Each binding ships the native library with it. Installing one does not require Zig or a compiler.

pip install irregex
cargo add irgx
go get github.com/The-Billy-Company/irregex/bindings/go

The distribution is named irregex; the import, crate, package prefix, header, and ABI are named irgx. Zig consumes the repository as a package dependency. C and every other FFI host build one library and include one header:

zig build
# zig-out/lib/libirgx.* + zig-out/include/irgx.h

The surface in each language is the one that language already expects: Pattern, finditer, and sub in Python; Regex, RegexBuilder, and captures_iter in Rust; the regexp-shaped Find, Split, and Replace family in Go. The machinery is shared. The manners are native.

How does search work?

My predecessor Andrew Gallant has an amazing description of how this machinery works, in the Anatomy of a grep section of his 2016 post announcing ripgrep's benchmarks.

It is, in my opinion, the easiest to read and by far the most useful for this discussion. What follows is a quick and less comprehensive summary; his remains the truer vivisection, and I gleaned mine from it.

A grep does four things in order.

  • It decides which files to look at.
  • It gets their bytes into memory.
  • It decides which of those bytes match.
  • Then it prints, in a shape somebody downstream can use.

That is the whole program, and every tool in the field is an argument about which of those four steps you are allowed to skip.

The step people underrate is the third one, because a grep is not a regex library wearing a command line.

Gallant makes this point directly: a grep is line oriented, and line orientation buys optimizations a general regex engine cannot make.

Mike Haertel's account of why GNU grep is fast is the classic statement of it, and his first trick is a refusal: GNU grep is fast because it avoids looking at every input byte.

It runs Boyer-Moore with an unrolled inner loop, spends fewer than three instructions on the bytes it does look at, and - the part that surprises people

  • deliberately does not split the input into lines, because finding the newlines would itself require touching every byte. It reads raw into a big buffer, skips through it, and goes looking for the bounding newlines only once it already has a match.

Haertel's summary of the whole discipline: "the key to making programs fast is to make them do practically nothing."

Hold onto that, because it generalizes past bytes. There are only two costs in search - the files you open and the bytes you scan - and every serious tool of the last fifty years is a position on which of the two it refuses to pay. The history is the story of that refusal getting more sophisticated.

Irregex stops at the product boundary, but it contains every mechanism that makes those refusals sound. A literal scanner may answer instead of an automaton. A candidate index may nominate files. A freshness sweep may force a stale file back through current bytes. None of them may change the answer.

A Quick History and Introduction

The algebra came first

Search of this kind is downstream of a piece of pure mathematics. In a 1951 RAND memorandum published in Automata Studies in 1956, Stephen Kleene described the "regular events" a finite-state machine can recognize and gave them an algebra: concatenation, alternation, and the closure that carries his name.

Rabin and Scott then proved in 1959 that letting the machine guess buys it nothing in power, since any nondeterministic automaton has a deterministic equivalent. Three things that look nothing alike - an expression you can type, a machine you can draw, a program you can run - turned out to be the same object wearing different clothes.

Ken Thompson made that equivalence operational in Regular Expression Search Algorithm (CACM, 1968): compile the expression into machine code, then run the input through it, simulating all live states at once so the cost per byte stays bounded no matter how ambiguous the pattern is. Everything irregex's default engine does descends directly from that paper. A regular expression is not a string matcher with extra syntax; it is a program you generate, and the field's whole performance story is about how cleverly you generate and then avoid running it.

Shannon, and where he shows up here

Claude Shannon's 1948 A Mathematical Theory of Communication is the other root, and it turns out to be load-bearing in three separate places in this codebase.

First, it is the reason an index can work at all. A trigram filter is a bet that source text is wildly non-uniform - that pgx is rare and for is not. If code were uniform random bytes, every three-byte window would be equally likely, no n-gram would prune anything, and the entire indexed-search family would be pointless. Redundancy is what we are selling. Second, it is the unit ranking is priced in: shape rarity erases a line's vocabulary, hashes the residue, and prices it at log₂(N/df), so a ubiquitous call-site geometry costs nothing and a rare one keeps full credit. Third, it is the yardstick the codex self-index is held to, since a searchable index that lands below the order-0 entropy of the text it indexes is a claim you can only state in Shannon's units.

Kleene tells you what a pattern is. Shannon tells you why you get to skip most of the corpus. The rest is engineering.

grep was not written overnight

The story everybody tells is that Ken Thompson wrote grep in a night. It is a great story, and the person who debunked it is Thompson.

What happened, per the accounts of the people in the room: Lee McMahon wanted to search the Federalist Papers for authorship clues, and ed - Thompson's own editor, which had perfectly good regular expressions - loaded whole files into memory to support random-access editing and therefore choked on a megabyte.

Doug McIlroy, in his own telling, "asked Ken Thompson if he could lift the regular expression recognizer out of the editor and make a one-pass program to do it," and found a note the next morning announcing a program named grep.

But Thompson's version is better: he already had one. A private tool called s, for search. He said he would think about McIlroy's request overnight, spent about an hour improving a program that already existed, and presented it the next day. The legend of the overnight miracle is an artifact of a man being modest about a head start.

The name is the ed command it replaced, g/re/p - global, regular expression, print - and it shipped in Version 4 Unix, written in PDP-11 assembly. McIlroy later credited grep with "irrevocably ingraining" the tools philosophy into Unix, which is a large claim for a program whose entire design is an extraction: take the recognizer out of the editor and point it at a stream too big to hold. Every grep since is that same move performed against a corpus that has outgrown something.

The schism: two roads out of Thompson

Thompson's linear road was not the one the field took. Henry Spencer's widely-copied backtracking engine, and then Perl, went the other way, and for a good reason: backtracking can express lookaround and backreferences, which are not regular in Kleene's sense at all. The price was catastrophic blowup, where an innocent-looking pattern goes exponential on an unlucky input.

Russ Cox put the linear road back on the map with Regular Expression Matching Can Be Simple And Fast and productionized it as RE2; Rust's regex crate carried the same guarantee into ripgrep.

That is the fork irregex sits on deliberately: the default engine is linear in the Thompson/Pike tradition, so a pathological pattern cannot detonate, and the vendored PCRE2 JIT is opted into rather than disguised as linear.

Nobody gets to promise both without saying which one they gave you.

Two lineages of tools, and ripgrep's merge

Gallant's taxonomy is the clearest one available, and it is his rather than mine. Command-line search split into two families with different obsessions. The grep-descended tools - GNU grep, sift - got very good at blowing through enormous files; they search what you point them at and treat file selection as your problem.

The ack-descended tools - ack, ag, ucg, pt - inverted the priority: be smart about which files, read your source-control configuration, skip node_modules and vendored trees and binaries, and accept a slower scan for a much smaller one. git grep is the interesting hybrid of manners: its flags read like grep's while its default behavior is pure ack, since it searches only what is checked in.

Ripgrep merged the two, and that merge is the reason it won. A genuinely fast regex engine with literal prefiltering, riding a parallel directory traversal that honors .gitignore by default. Both costs attacked at once instead of one traded against the other.

The third lineage: indexes

There is a third family, and the first two structurally cannot contain it, because both of them re-read the tree on every query. If you are willing to remember something between queries, the shape of the problem changes.

Russ Cox laid out the canonical construction in Regular Expression Matching with a Trigram Index (2012), the design behind Google Code Search: extract from the regex the trigrams a match must contain, turn that into a boolean query over posting lists, and verify only the survivors with a real matcher. google/codesearch ships it as cindex/csearch, and it is irregex's direct ancestor - the candidate index here is that idea, carefully.

The family fanned out from there, and each member picked a different thing to spend:

  • Hound wraps Cox's design per repository behind a service and a browser UI.
  • livegrep changed the index rather than the plan: Nelson Elhage flattens the whole corpus into one buffer, builds a suffix array over it, compiles the regex into an IndexKey with a selectivity estimate, binary-searches ranges, and hands candidates to RE2. Substrings a trigram index cannot see, at the cost of an index and a resident backend.
  • Zoekt went positional - trigrams that remember where - plus mmap-friendly shards, ranking, and ctags symbols; it is the engine under Sourcegraph.
  • GitHub's Blackbird took the same presence idea to global scale with sparse variable-length n-grams.
  • qgrep searches a compressed indexed copy, and Postgres carries the whole trick inside a database as pg_trgm, which walks a color-trigram graph off the regex automaton.

Google's own arc is documented in Software Engineering at Google, ch. 17: trigrams, then suffix arrays, then sparse n-grams, each step a different bet on index size against query cost.

The literature is equally explicit about the limits - Cho & Rajagopalan (2002) on selective multi-gram indexes, Gibney & Thankachan (2021) on conditional lower bounds for regex indexing, and Zhang et al. (2025) on modern n-gram selection.

Two things are true of every member of that family, irregex included. The first is a blind spot: they all test presence, so a pattern with no literal in it

  • [0-9a-f]{12}, which is what a hunt for a hash or a MAC address looks like - proves nothing about any file and concedes the entire corpus.

That hole is what the crest sieve exists to close, and it is the one piece of mathematics here that is ours.

The second is an assumption: that the index is authoritative. Perfectly reasonable when you are a hosted mirror synced from a repository. Wrong, and quietly wrong, when the thing you are indexing is a working tree somebody is editing.

The engine

A pattern enters once. The parser turns it into an AST over byte and scalar classes; an analysis pass interns that tree into a canonical DAG and derives every sound fact an accelerator may use. One lowering emits Thompson instructions. Two determinization roads then compete: a byte powerset for the ordinary case, and a symbolic road that discovers Unicode automata over the pattern's own minterms before transcribing them back to bytes.

The runtime takes the cheapest sound rung:

  1. an exact zero-width or literal answer;
  2. a class-run kernel;
  3. an accelerator that can prove its precondition;
  4. an eager DFA;
  5. a lazy DFA under a bounded cache;
  6. the Pike VM that serves as the in-family oracle.

Every optional rung returns hit, miss, or unproven. Unproven falls through. A state ceiling, visit ceiling, unsupported grammar, stale index, corrupt artifact, missing clock, or uncertain watcher all have the same moral shape: decline to something slower that can still answer exactly.

This is the governing law:

An accelerator may elide work. It may never become an authority.

The compiled query makes that law structural. The prefilter an index is allowed to use and the matcher that verifies the surviving bytes come from one compilation, so a caller cannot accidentally maintain two grammars for the same question.

Crest

Everything in the trigram family asks whether a document contains a substring the match requires. A literal-free class repetition requires no substring at all, which is why [0-9a-f]{12} concedes every file.

Crest asks a different necessary question. Index each document by the longest consecutive run it contains for each byte class. Then derive, from the regex AST, the class runs every top-level alternative is forced to contain. A document whose profile never crests that high cannot match.

The bound is built to be wrong in one direction only. Every term rounds down; anything the calculus cannot certify contributes nothing; unsafe caseless folds decline to zero. A missed pruning costs time. A false pruning would cost a match, so the algebra makes that failure unavailable before the tests begin.

Then it is tested anyway, fail-closed: matched ⇒ ¬pruned against the production matcher over real and randomized adversarial inputs. The theorem, prior-art review, and falsification strategy live with the engine in research/crest/.

Evidence

A performance claim in a report is a wish. Irregex measures mechanisms against bounds and independent oracles, then lets the product faces measure the complete walk.

The first floor is semantic. The Pike VM and the deterministic roads descend from the same lowering, so they are useful differentials but not independent enough to certify that lowering. The engine therefore carries an AST backtracker that shares only the parser, implements its own UTF-8 and assertion logic, and returns a second opinion over short exhaustive subjects. External differentials run against rg and grep -oP at their own semantics.

The second floor is informational. Verify is Ω(candidate bytes) in the worst case - the classical Knuth-Morris-Pratt and Boyer-Moore result, since an unread byte could be the match. The fused byte-class DFA reads every admitted byte exactly once; the SIMD literal roads may read less by skipping vectors or exiting early. Sublinearity belongs to the candidate stage, which makes the input to verify smaller.

The third floor is mechanical. The hot loops are judged against static microarchitectural budgets where LLVM has a real scheduling model, measured PMU counters where the operating system exposes them, and a roofline against measured memory bandwidth. An absent number beats an invented one. Apple silicon therefore keeps a blank static-cycle column: xnu gates the PMU and LLVM models every Apple core as 2013's Cyclone.

Those are fit claims, not universal optimality. A benchmark can establish that a mechanism met a stated bound on a named machine and corpus. It cannot establish that no better program exists. The complete inventory, including the losing rows, lives in the repository's bench/ and research/ trees.

Kleene gave us the algebra. Thompson made it a program. Haertel taught the program to refuse work, and Cox taught it to refuse files. Irregex makes every one of those refusals a value the caller can inspect, route around, and trust.