I ported a Python library to Rust. My fuzzer was lying to me.

Every "port to Rust" post is the same shape: I rewrote it in Rust and it's faster. This one isn't. I ported a Python string-similarity library to Rust, and the honest story is mostly about proving the port, not writing it. The original's own tests pass unmodified. A differential fuzzer compares the two on hundreds of thousands of random inputs. And the hardest bug I fixed wasn't in the algorithms. It was in the tool that was supposed to be verifying them. It was telling me "0 divergences" while not actually testing most of the code.

That is the part nobody writes about. Here is the whole thing: what I picked, what broke, how I proved equivalence, the bug that ate a day, and the decision I would take back.

What I picked

textdistance is a pure-Python library with 30+ string-similarity algorithms: edit distances (Levenshtein, Damerau-Levenshtein, strcmp95), sequence metrics (LCS), token metrics (Jaccard, Sorensen), phonetic metrics, and a family of compression-based metrics (NCD) that literally compress your strings and compare the lengths. That last family is why this is a good port to attempt. The compression metrics need real liblzma and libbz2, so I vendor them through lzma-sys from a small C wrapper crate. The port is a Rust core (tdcore, #![forbid(unsafe_code)]) plus a thin PyO3 FFI (pyapi) plus a Python adapter package that keeps the exact public API, wrapped for distribution with maturin.

My rule from the start: this is a behavioral port, not a rewrite. The original's behavior is the specification, including its quirks and its bugs. A port that "improves" Smith-Waterman to the textbook definition has failed. So "correct" means: same values, same types, same exceptions, same edge cases, on every input the original's own tests and a lot of random inputs can reach.

How I proved it

Three independent checks, and I published the scripts for all of them (bench/, scripts/):

1. The original test suite runs unmodified. tests/original/ is pinned byte-for-byte to a specific upstream commit. All 400 tests pass. With the port's own tests that is 428 passed, 30 deselected (the 30 are external; they call into third-party libs like nltk and jellyfish).
2. Differential fuzzing. fuzz/ runs the original package and the port side by side on identical random inputs (text, Unicode, lone surrogates, lists, varying constructor kwargs) and asserts identical outputs for distance, similarity, normalized_distance, normalized_similarity, and maximum. Final runs: 59,000 + 101,400 cases, 0 divergences. Earlier I ran 1.75M + 1.37M lone-surrogate cases.
3. Honest-number scripts. honest_report.py counts unsafe blocks per crate. coverage_diff.py measures statement coverage of the adapter on both sides (port 87.3% vs original 79.8%; the port's real math is in Rust, so that raw percentage understates it, and I say so in the file). cli_diff.py diffs the tdc CLI against the original on 792 shared inputs.

Now the part with the meat on it.

Problem 1: my fuzzer was lying to me

I wrote the differential harness, let it run for hours, and saw the magic line: divergences: 0. I was ready to call it a day. Then I actually read my own code.

The harness was passing the same constructor kwargs to all 37 algorithms. One of the shared kwargs was as_set=True. Twenty-eight of the algorithms reject as_set. For those algorithms every case died of TypeError at construction, the harness caught the error, and moved on. The "0 divergences" run had compared a handful of the easiest algorithms and skipped everything else. My verification tool, the thing I built so I wouldn't fool myself, was the thing fooling me.

The fix was boring and correct: filter kwargs through inspect.signature, identically on both the port and the reference side, so every algorithm actually gets constructed and value-compared. While I was in there I found two more silent problems: numpy reprs (np.float64(3.0)) were being compared as strings, and maximum was being compared as a bound-method repr instead of a called value. All fixed. The honest lesson is the headline: before you trust a differential fuzzer, test that the fuzzer is testing. I would take back every minute I spent trusting the first "0 divergences."

Problem 2: the latent bug (and the one good thing the harness did)

The repaired harness immediately found its first real divergence. It was not a port bug. It was an upstream one:

>>> textdistance.gotoh('', 'x')
IndexError: index 1 is out of bounds for axis 0 with size 1

Upstream's Gotoh runs its dynamic programming on numpy matrices of shape (len_s1+1, len_s2+1). When exactly one input is empty, that matrix has a single row or a single column, and the initialization loop writes p_mat[1, j], which is row 1 of a one-row matrix. Crash. gotoh('', '') is fine and gotoh('x', 'y') is fine. The single-empty case just explodes.

Why is it latent? Two reasons. Upstream's own tests never pass exactly one empty string, so no test reaches that path. And my broken harness was never value-comparing gotoh at all, so I could not have found it anyway. A real bug revealed by fixing the tooling.

Now the porting-philosophy moment: do I fix it? No. Behavioral parity means the port must reproduce it byte-for-byte. gotoh('', 'x') raises the same IndexError, and a test pins it so nobody "helpfully" patches it out later. The finding is documented in BUG.md and the upstream report is ready to file. A port that silently "fixes" this is less faithful, not more.

Problem 3: the byte war over LZMA

The compression metrics compute NCD from compressed lengths, so they depend on the exact bytes liblzma emits. My first implementation used the one-shot lzma_stream_buffer_encode. CPython's lzma.compress drives the streaming lzma_stream_encoder plus lzma_code(LZMA_FINISH). Both call the same vendored liblzma 5.2.5, so I assumed the outputs matched.

They do not. The block header differs, the LZMA2 payload differs, and for one repeated-string input the compressed length came out 58 vs 62 bytes, which changes the NCD value and, with it, the whole algorithm's result. This one cost hours because it only showed up on specific inputs.

I killed it with a Rust experiment: a tiny example binary compressing the same inputs through both APIs and dumping lengths and bytes. Streaming was byte-identical to CPython. The codec now uses the streaming path and pins CPython's header-trimmed lengths in a unit test. Two more LZMA gremlins showed up on the way: lzma_lzma_preset returning 0 on the toolchain while still populating dict_size (an assert panicked at startup; the fix is to check the options, not the return value), and the whole problem only mattering because the CI Python and the local Python happened to bundle different liblzma builds.

Problem 4: quirk-for-quirks is a menu, not a bug list

The fuzzer then taught me what "behavioral port" really means, one quirk at a time:

• strcmp95: the matching, transposition, and similarity loops each deviated from the original. The similarity pass rewards only the phonetic pairs from the adjwt table, not plain character equality. And the transposition pass reuses the matching loop's final j and falls back to s2[len_s2-1] when no flagged position is found. You cannot guess this. You have to transcribe it. A 12-pair probe went from 10/12 to 12/12.
• Hamming on lists: the original pads with None via zip_longest and compares with Python ==, so None == None matches. My Rust kernel treated padding as an automatic mismatch and even distinguished Rust's Option::None from an actual None element. Padding now maps to Python None, and everything compares through ==. This also fixed MLIPNS, which delegates to Hamming.
• BWTRLENCD on a list: the original appends a '\0' terminator and then calls type(data)().join(...). On a list that is list().join(...), which raises AttributeError. The port returned a value. Now it raises the identical AttributeError. Faithfully.
• MLIPNS return type: the original returns 1 or 0 as int on every path. My port returned the f64 kernel value. 1.0 == 1 numerically, so a type-insensitive comparison never caught it. Now it is narrowed to int.

Problem 5: the environment fight (numpy, everywhere)

The CI differential-fuzz step failed with about 2,025 divergences. Locally it was zero. The count was a clue: 3 x (25000/37). Exactly three algorithms, diverging on every case: NeedlemanWunsch, SmithWaterman, Gotoh. Upstream implements all three in numpy, and at the top of each __call__ it does if not numpy: raise ImportError(...). The CI runner had no numpy, so the reference raised on every call while my Rust kernels happily computed values. Locally numpy was installed, so both sides computed. Environment, not code.

The fix was philosophically interesting. I did not just install numpy on CI (that only patches the environment). I mirrored the dependency in the port: same guarded import numpy, same ImportError, same message. Now with numpy installed, both compute and match. Without it, both raise identically. The port behaves like the original in every environment, and the fuzzer stays honest.

That one change then broke the test suite on CI, because the pinned upstream tests exercise those three algorithms and need numpy to compute. So the CI workflow needed numpy too. And then build.ps1 needed numpy too. Three separate fixes for one environmental truth, each one discovered by a CI run that was, in hindsight, doing its job. The CI whack-a-mole (fmt, then clippy -D warnings, then numpy) was annoying, but it is exactly what a pipeline is for: it kept failing until the environment and the port agreed.

The benchmark that disappointed me

I wanted to print a clean "bit-identical on everything." Reality is messier, and publishing the mess is the point of this write-up.

• The fuzzer's 0 divergences comes with 4,140 + 5,504 near-misses within 1e-9. These are floating-point repr differences I cannot scrub away (numpy computes some values differently than my Rust f64). I report them. I do not hide them.
• gotoh('', 'x') crashes on purpose. That is a feature of a faithful port and a bug in upstream. Both are true.
• The CLI diff is 0 numeric diffs on 792 inputs, plus 4 cases where the original raises and my CLI answers. Faithful, and weird to ship.

And the performance table has a row that hurts. The edit and sequence kernels are 6 to 330 times faster (levenshtein 6x, damerau_levenshtein 10x, lcsseq 12x, levenshtein on long strings 331x, lcsseq on long strings 199x). But the compression family, the whole reason I vendored liblzma, is basically flat: bz2_ncd is 1.09x. The bottleneck there is the compression itself, not the Python glue, and Rust does not make libbz2 faster. I wrote that number down anyway, because "ported to Rust, everything is faster" is the claim that this row disproves. (The good news in the same table: the port imports in 15ms vs 90ms, and uses about 17MB of RAM vs 27MB.)

The unsafe block I could not remove

honest_report.py counts 10 unsafe blocks, all of them in the codec C-wrapper crate, the FFI to vendored liblzma and libbz2. The Rust core (tdcore), the PyO3 glue (pyapi), and the CLI (tdc) are #![forbid(unsafe_code)]: zero blocks. I could not remove the ten because you cannot call C from Rust without unsafe. The discipline is containment: the unsafe is exactly where the C is, and nowhere else. I would rather point at the line than pretend it does not exist.

What I would take back

1. Trusting the first "0 divergences." The most expensive mistake was believing my own tool before auditing it. The harness is the crown jewel of this project. It should have been built first and audited first.
2. Not standardizing the dev and CI environment sooner. numpy, the local liblzma, the build script: three separate fights for one lesson. The reference and the port must run in identical environments, or the comparison is meaningless.
3. Reproduce-don't-fix for gotoh. I would defend this one, not take it back. But I underestimated how much it costs to explain "my port crashes on purpose, and that is correct" to people who glance at a README. The documentation does the heavy lifting.

The honest close

What this port is: the original's own suite passing unmodified; 160,000+ fresh random cases with zero divergence; the bugs in the tooling that proved it; the deviating behaviors documented as deliberate, not swept under the rug; and a benchmark table that includes its own embarrassment. What it is not: "Rust made everything faster." It made the edit distances absurdly faster and left the compression metrics exactly where they were. Both of those are true.

If you are porting something, port the behavior, not the happy path. And before you trust your fuzzer, fuzz the fuzzer.

Code and all the numbers behind this: github.com/Amitk003/textdistance-rust. The differential harness is in fuzz/, the honest-number scripts in scripts/ and bench/, and the documented latent bug is in BUG.md. Written for the Hackathon Raptors side quest.