Porting a Python PEG parser to Rust in 72 hours, and actually proving it worked

Avyukt Soni — Tue, 11 Aug 2026 05:17:39 +0000

There's a joke that every Rust project starts with someone saying "we should rewrite this in Rust" and ends four weekends later with a half-finished repo and a lot of new opinions about lifetimes.

We had 72 hours. So we skipped the opinions.

This is the story of rs-parsimonious — a complete Rust port of erikrose/parsimonious, a pure-Python PEG packrat parser — built for Port Mortem 2026, a hackathon whose entire premise is that writing a port is easy and proving it works is the interesting part.

Here's where we landed:


Differential fuzz	20,041 cases, 0 divergences, 600s continuous
Upstream test suite	84 passed, 2 skipped — running unmodified
Port test suite	54 Rust parity tests, all green
`unsafe` blocks	0 — `#![forbid(unsafe_code)]`, enforced in CI
Cold start	23 ms → 2 ms
p99 latency	0.068 ms → 0.016 ms
Peak memory	~13 MB → ~6.7 MB
Ships as	one 2.1 MB static binary

Let me walk through how we got there.

Why a parser was the right thing to port

This was the most important decision we made, and we made it before writing a single line of Rust.

A PEG parser has a beautiful property for this kind of work: its interface is (grammar, input) -> parse_tree | error. That's it. No timezones. No locale handling. No floating-point tolerance you have to negotiate with yourself. Two implementations either produce the same tree or they don't, and there's never an argument about what "the same" means.

That clarity is what made everything downstream possible. When your oracle is unambiguous, you can automate the proof. When it's fuzzy, you're hand-checking cases forever.

We also confirmed nobody had already ported this specific project — a surprisingly involved check, since the obvious candidates in this space (textdistance, croniter, wcwidth) all turned out to have Rust ports already published. parsimonious came back clean. The Rust PEG libraries that exist (pest, rust-peg) are independent implementations, not translations of this codebase.

Designing around the packrat cache

The first real design decision was how to model expressions, and it's where the Rust version diverges most interestingly from the Python one.

Python models expressions as a class hierarchy — Literal, Regex, Sequence, OneOf, Lookahead, Quantifier, all subclassing Expression. The reflexive Rust translation would be Box<dyn Expression> trait objects.

We went a different way, and packrat memoization is the reason.

Packrat parsing caches (expression, position) -> result to turn what would be exponential backtracking into linear-time parsing. For that cache to work, two things have to be true: expressions need stable identity, and subexpressions need to be genuinely shared. A rule referenced from three places in a grammar has to be the same object in all three, or you get three separate cache entries doing three separate redundant parses.

So: one owned struct, a kind enum, shared through Arc.

pub struct Expression {
    pub name: String,
    pub kind: ExprKind,
}

pub type Expr = Arc<Expression>;

pub enum ExprKind {
    Literal    { literal: String },
    Regex      { re: fancy_regex::Regex, pattern: String, flags_bits: u32 },
    Sequence   { members: RwLock<Vec<Expr>> },
    OneOf      { members: RwLock<Vec<Expr>> },
    Lookahead  { member: Expr, negative: bool },
    Quantifier { member: Expr, min: usize, max: Option<usize> },
    // TokenMatcher, LazyRef, AdHoc …
}

The cache keys on Arc::as_ptr. That gives us exactly the object identity Python got for free from its object model — but explicitly and cheaply. No allocation, no hashing an entire expression tree, just a pointer comparison.

Nice side effect: with Arc, sharing a subexpression costs a refcount bump instead of a deep clone. In a grammar where rules reference each other heavily, that adds up fast.

The `RwLock` that earns its keep

You'll have noticed members: RwLock<Vec<Expr>> up there. A lock inside a parser structure looks like something went wrong. It's actually the thing that makes recursive grammars work.

When you compile a grammar, rules reference each other by name before those rules exist. parsimonious handles this with lazy references resolved in a second pass. In Python, that resolution mutates in place — and because everything points at the same object, every parent automatically sees the resolved version.

Getting that right in Rust meant matching the semantics, not just the shape: resolve in place, so a rule referenced from anywhere in the tree sees the fully-resolved version. Interior mutability is the honest way to express "this graph gets patched up once during construction, then never changes again."

It's the kind of thing that looks like a smell until you understand why it's there, and then it looks obvious.

Keeping the meta-grammar intact

Here's a fun wrinkle: parsimonious is self-hosting. The grammar that parses grammar definitions is itself written in parsimonious grammar syntax. Which means the meta-grammar has to work before anything else does.

And the meta-grammar uses negative lookahead:

label = ~"[a-zA-Z_][a-zA-Z_0-9]*(?![\"'])"

Rust's standard regex crate doesn't support lookaround. That's deliberate on their part — it's how they guarantee linear-time matching.

We could have simplified the meta-grammar to dodge the problem. We didn't, because the whole point of the exercise is fidelity to the original. Instead we reached for fancy-regex, which supports lookaround, and kept the upstream grammar exactly as written.

Small decision, but it's the one that lets us say the grammar is genuinely the same grammar rather than "close enough."

Squeezing out the performance

A few things stacked here.

Release profile tuning. Link-time optimization plus a single codegen unit:

[profile.release]
lto = true
codegen-units = 1

Trades compile time for runtime, which is exactly the right trade for a library people build once and then run constantly.

Zero-copy where it counts. Nodes hold an Arc<str> into the source text rather than owning a copy of every matched substring. Pulling the text out of a node is a slice, not an allocation.

The packrat cache itself. This is the algorithmic win — it's what stops pathological grammars from exploding. Getting the identity model right (above) is what makes it genuinely effective rather than nominally present.

No runtime to boot. This turned out to be the biggest practical improvement of all. Python has to start an interpreter and import a module before it can parse a single character. Our binary is already running.

Metric	Python	Rust
Cold start	23 ms	2 ms	~11×
p99 latency	0.068 ms	0.016 ms	~4×
Peak RSS	~13 MB	~6.7 MB	~2×
Parse throughput			1.5–3.4×

That startup number is the one I'd actually put on a slide. Nobody adopts a parser library because it shaves microseconds off a 40-character string. They adopt it because it starts instantly, uses half the memory, and deploys as a single file with no interpreter and no virtualenv in sight.

Proving it, which was most of the work

Here's the thing about writing your own tests: you wrote them. You tested what you thought of. The interesting failures live in the space you didn't think of.

So we built a differential harness.

The Rust CLI exposes a JSON-line mode:

printf '%s' '{"grammar":"g = \"hi\"\n","input":"hi","mode":"parse"}' \
  | ./target/release/parsimonious json-line

A Python oracle script accepts the identical schema and drives the original library. Then a fuzzer generates random grammars and random inputs, sends the same request to both sides, and compares results.

The comparison is normalized on the things that are actually semantics: the ok flag, tree structure (node spans and expression names), and on failure, the error kind and pos. Error message text is deliberately out of scope — where a parse fails and why is behavior; how that gets phrased for a human is presentation, and demanding byte-identical Python exception strings from a Rust program would mean writing un-Rusty code for zero behavioral gain.

Final run: 600.02 seconds. 20,041 cases. Zero divergences.

On top of that, upstream's own pytest suite runs completely untouched from a pinned git submodule — 84 passed, 2 skipped — and 54 Rust parity tests map back to specific test classes in the original.

Building tamper-evidence that actually works

One requirement of the hackathon is hashing the original test suite at kickoff, so the commit timestamp proves you didn't quietly edit tests later to make your port look better. (The event exists partly because a very high-profile Rust port did exactly that.)

We took this seriously enough to audit our own compliance late in the build — and found that while our hash was committed and our test files were provably untouched, the script that generated the hash had never been checked in. The method was described in a comment, but a prose description isn't an implementation: "SHA-256 of sorted per-file SHA-256s" leaves open which files, sorted how, hex digests or raw bytes, joined with what separator.

So we built scripts/hash_original_tests.py properly. It pins down every ambiguity explicitly, prints per-file digests alongside the combined one so the whole thing is auditable, and produces a hash anyone can regenerate in one command and check against the pinned submodule.

That's the version that shipped. A hash you can't reproduce is just a number — a hash with a committed script behind it is actual evidence. Easily worth the hour.

What I'd tell someone starting one of these

Build the thing that proves the port before you build the port.

We stood up the differential harness on day two, and from that moment on it paid for itself continuously — every divergence it caught was a five-minute fix instead of a day-three archaeology dig. Same story with the hash tooling.

In a project like this, the verification infrastructure isn't overhead wrapped around the real work. It is the real work. The port is almost a byproduct.

Repo: github.com/avyuktsoni0731/rs-parsimonious — MIT, same as upstream. Every number above is reproducible from the repo; methodology lives in bench/methodology.md.

Built for Port Mortem 2026 by Hackathon Raptors.

DEV Community: Avyukt Soni