DEV Community

codewitharyan29
codewitharyan29

Posted on

Porting natsort to Rust taught me that "it compiles" is the easy 5%

#algorithms #python #rust #software

TL;DR: I ported Python's natsort library to Rust for Port Mortem 2026.

Writing the sorting algorithm turned out to be the easy part.

The difficult part was proving the Rust implementation behaved identically to the original Python library across thousands of edge cases without quietly changing behavior.

That meant treating verification as the real project.

Why I chose natsort

Most demo ports are calculators, parsers, or utilities with a handful of tests.

I wanted something that would actually stress the verification process.

natsort sorts strings the way humans expect:

file2
file10
file20
Enter fullscreen mode Exit fullscreen mode

instead of lexicographic order.

That sounds simple until you discover it supports:

  • seven algorithm variants
  • signed and floating-point numbers
  • scientific notation
  • full Unicode numeric characters
  • locale-aware behavior
  • Roman numerals
  • fractions
  • a real upstream test suite covering years of edge cases

A port that looks correct on five examples proves almost nothing.

A port that survives the library's own test suite, differential fuzzing, CLI comparisons, property testing, and mutation testing starts becoming evidence.

The architecture

The verification pipeline ended up looking like this:

             Python Test Suite
                    │
                    ▼
          Thin Python Adapter
                    │
                    ▼
             Compiled Rust Binary
                    │
                    ▼
          Rust natsort Implementation
                    │
                    ▼
 Compare:
 • stdout
 • stderr
 • exit codes
 • ordering
 • fuzz results
 • properties
Enter fullscreen mode Exit fullscreen mode

The adapter intentionally contains almost no logic.

Its only job is forwarding Python test inputs to the Rust implementation.

That design choice turned out to matter more than I expected.

What broke (and why those bugs mattered)

1. Differential fuzzing found a bug in the original library

Differential fuzzing generates thousands of random inputs and compares both implementations.

Most mismatches were my mistakes.

One wasn't.

>>> natsorted(["1e400", "1e500"], alg=ns.REAL)
['1e400', '1e500']

>>> natsorted(["1e500", "1e400"], alg=ns.REAL)
['1e500', '1e400']
Enter fullscreen mode Exit fullscreen mode

Both calls succeed.

Both disagree.

The reason is surprisingly simple.

Both values overflow to floating-point infinity.

Since both become inf, the comparison reports them equal, and Python's stable sort simply preserves whichever order the inputs arrived in.

Rust's f64 behaves the same way.

That means the correct port is not one that "fixes" the behavior.

The correct port reproduces it.

I reported the issue upstream:

natsort#192

Finding a real bug in a mature library simply by holding another implementation beside it was one of the most satisfying moments of the project.

2. My adapter was lying to me

I assumed the adapter was a thin wrapper.

It wasn't.

One function calculated the correct Rust-backed answer...

...and then ignored it.

Instead it silently fell back to a handwritten Python implementation that didn't understand signed numbers or Unicode.

index_natsorted(["-5", "-1", "3"], alg=ns.REAL)

returned:
[2, 1, 0]

correct:
[0, 1, 2]
Enter fullscreen mode Exit fullscreen mode

Differential testing doesn't automatically catch bugs in the adapter.

You have to verify the adapter itself.

That lesson probably saved me more time than any optimization.

3. Windows disagreed with Linux

Everything looked perfect.

Until I ran it on Windows.

Five bugs immediately appeared.

  • executable needed .exe
  • python3 didn't exist (py does)
  • subprocess output defaulted to CP-1252 instead of UTF-8
  • file reads had the same encoding problem
  • Unix-only resource crashed benchmarks entirely

None of those appeared on Linux.

None appeared in my development environment.

Every one appeared on a real Windows machine.

"Works on my machine" turned out to be the weakest verification strategy of all.

4. GitHub Actions lied with a green checkmark

The deployment workflow looked successful.

The live website returned 404.

The culprit?

A multi-line shell block:

curl ... | sh
build
deploy
Enter fullscreen mode Exit fullscreen mode

The installation silently failed.

The following commands still exited successfully.

GitHub reported the entire step as green.

The fix wasn't clever.

It was boring.

I switched to:

cargo install wasm-pack
Enter fullscreen mode Exit fullscreen mode

and added a deployment check that refuses to publish unless the expected build artifacts actually exist.

A green checkmark only matters if it's checking the thing you care about.

How I proved behavioral equivalence

The implementation wasn't the deliverable.

Evidence was.

I ended up with six independent layers of verification.

1. Upstream tests

Run the original natsort test suite without modifying it.

Tests excluded only when Rust genuinely cannot reproduce Python-specific behavior, and every exclusion is documented.

2. Differential fuzzing

27,000 seeded comparisons across all algorithm variants.

Same inputs.

Same outputs.

Reproducible failures.

3. CLI differential testing

2,800 CLI invocations comparing:

  • stdout
  • stderr
  • exit codes

Matching output alone isn't enough.

Programs communicate failure through exit codes too.

4. Property testing

Randomized verification of:

  • idempotence
  • antisymmetry
  • transitivity

These find classes of bugs that handwritten examples never will.

5. Mutation testing

I deliberately broke my implementation.

  • reversed comparisons
  • removed signs
  • altered parsing logic

If the verification pipeline couldn't detect injected bugs, it wasn't trustworthy.

Every injected mutation was caught.

6. Honest benchmarking

Instead of publishing a single "10× faster" headline, I reported:

  • mean
  • median
  • p95
  • p99
  • peak memory

The real result was 6–8× faster, depending on workload.

Honest numbers build more confidence than inflated ones.

The decision I'd take back

I spent a huge amount of time chasing perfect Unicode parity.

It was technically rewarding.

It pushed differential matching from roughly 43% to 100% across the full Unicode character set.

I'm proud of that work.

But I crossed the point of diminishing returns.

One adapter-level discrepancy survived until the deadline on a single CI runner.

I excluded that specific test rather than claim support I couldn't fully defend.

Looking back, I'd stop polishing Unicode earlier and spend those hours investigating the remaining verification discrepancy instead.

Verification gets exponentially more expensive near the finish line.

Knowing when to stop is part of engineering.

Final numbers

By the end of the project:

  • Original upstream tests running against Rust
  • 27,000 differential fuzz comparisons
  • 2,800 CLI differential runs
  • Property testing
  • Mutation testing
  • Honest benchmark suite
  • 6–8× speedup
  • One upstream bug reported
  • Cross-platform verification on Linux and Windows

Reproduce everything

Everything needed to verify the project is public.

Demo

https://youtu.be/jVz_2AP4U4w

Live WASM demo + verification dashboard

https://codewitharyan29.github.io/Port-Mortem/

Repository

https://github.com/codewitharyan29/Port-Mortem

Upstream issue

https://github.com/SethMMorton/natsort/issues/192

Closing thoughts

Anyone with an AI coding agent can produce something that compiles.

Compilation is the easy part.

The difficult part is proving—without hand-waving—that another implementation behaves the same as the original across thousands of edge cases, different operating systems, different execution paths, and even the original project's own bugs.

By the end of this project, I stopped measuring success by whether the Rust code compiled.

I measured success by how much evidence I had that it behaved like Python.

That, more than the port itself, is what I learned from Port Mortem 2026.

#PortMortem2026 #HackathonRaptors #Rust #Python #OpenSource #SystemsProgramming #Testing #Verification #Fuzzing
**

Top comments (0)