140 Bugs Were Hiding in One Function, and My Tests Couldn't See Any of Them

Daniel — Mon, 10 Aug 2026 09:57:25 +0000

Anyone can port a library. Point a translator at the source, clean up the output, get it to compile, and you have something that looks like a port. The actual engineering problem is different and much harder: proving that the new code means the same thing as the old code, across thirty algorithms, hundreds of edge cases, and a test suite written by people who were not thinking about you.

This is the story of porting textdistance, a Python library for measuring string similarity, to Rust. The result is textdistance-rs. The porting took a fraction of the time. Everything else: the differential fuzzing, the 140 divergences, the 35 year old threshold I violated, the floating-point drift at the 15th decimal place, is what this writeup is actually about.

Thirty algorithms and one architectural bet

The original textdistance covers a lot of ground: edit-based distances (Levenshtein, Damerau-Levenshtein, Hamming, Jaro-Winkler), token-based measures (Jaccard, Sørensen-Dice, cosine, Tversky), sequence-based methods (LCS, Ratcliff-Obershelp), phonetic algorithms (MRA, Editex), and compression-based distances built on normalized compression distance. Over thirty algorithms in total, all reimplemented in Rust.

But before writing a single algorithm, I had to make the decision that shaped everything downstream: how does the existing Python test suite (397 tests I did not write) talk to the Rust code?

The obvious answer is PyO3: wrap every algorithm in a #[pyclass], build a native extension, and the Python tests import Rust directly. The answer I chose instead was a subprocess CLI. The Rust core is a standalone binary that speaks JSON over stdin/stdout, and a thin Python adapter shells out to it:

// The entire cross-language surface is one struct.
#[derive(Deserialize)]
struct Request {
    algorithm: String,
    s1: String,
    s2: String,
    qval: Option<usize>,
    external: Option<bool>,
}

fn dispatch(req: &Request) -> Response {
    match req.algorithm.as_str() {
        "hamming" => hamming::distance(&req.s1, &req.s2),
        "levenshtein" => levenshtein::distance(&req.s1, &req.s2),
        "jaro_winkler" => jaro::winkler_similarity(&req.s1, &req.s2),
        // …thirty more arms
        _ => Response::error("unknown algorithm"),
    }
}

The reasoning: PyO3 binds you to Python's ABI, complicates the build for anyone who just wants the Rust crate, and turns every signature mismatch into a compile-and-link problem. A JSON pipe is crude, but it is debuggable with your eyes. You can replay any failing case by piping a JSON string into the binary from your shell. When the goal is verifying behavioral equivalence against a foreign test suite, that inspectability is worth a lot.

It was a speed decision, and I knew it. What I did not know was that this bet had quietly closed a door I would walk straight into later on.

The bug that was older than the port

The single worst debugging session of the project traced back to Jaro-Winkler, and specifically to a paper published in 1990.

Jaro similarity comes from Matthew Jaro's 1989 work on record linkage for census data. William Winkler's 1990 refinement adds a bonus for strings that share a common prefix, on the empirical observation that clerical typos rarely occur in the first few characters of a name. My first implementation applied that prefix boost the way the formula usually gets quoted:

// What I wrote first: boost applied unconditionally.
let jaro = jaro_similarity(s1, s2);
jaro + (prefix_len as f64) * P * (1.0 - jaro)

It looks right. It passes the examples people paste into blog posts. And it is wrong, because Winkler's actual method only applies the boost when the base Jaro score exceeds a threshold of 0.7 in his published work. Below that, the strings are too dissimilar for a shared prefix to mean anything, and boosting them inflates scores for garbage matches:

// What Winkler actually specified in 1990.
let jaro = jaro_similarity(s1, s2);
if jaro > BOOST_THRESHOLD { // 0.7
    jaro + (prefix_len as f64) * P * (1.0 - jaro)
} else {
    jaro
}

Combined with a second, smaller mistake: the original library treats two empty strings as perfectly similar (1.0), and my port returned 0.0. This one function accounted for 140 divergences in fuzz testing. One commit fixed all of them.

The lesson that stuck with me: I was not diverging from the Python library. I was diverging from a 35-year-old paper that the Python library had implemented faithfully and I had implemented from memory. When you port a library, you inherit its citations, not just its code.

Proof by ten thousand disagreements

That raises the obvious question: how did I even know there were 140 divergences? The unit tests for Jaro-Winkler passed. Example-based tests check the inputs somebody thought of, and nobody thinks of "ab" vs "aaab" with a coincidental prefix and a sub-threshold Jaro score.

The answer was differential fuzzing — running both implementations on the same randomized inputs and diffing the outputs. The technique goes back to McKeeman's work on differential testing for compilers: when you have two implementations that claim to compute the same function, disagreement between them is a test oracle you get for free. You don't need to know the correct answer; you only need to know they should match.

The harness is embarrassingly simple, which is the point:

from hypothesis import given, strategies as st
import textdistance          # the Python original
import textdistance_rs       # the port, via the JSON pipe

@given(st.text(), st.text())
def test_jaro_winkler_parity(s1, s2):
    expected = textdistance.jaro_winkler(s1, s2)
    actual = textdistance_rs.jaro_winkler(s1, s2)
    assert abs(expected - actual) < 1e-9, (s1, s2, expected, actual)

Hypothesis, Python's property-based testing library, descended from Claessen and Hughes' QuickCheck, generates the adversarial inputs: empty strings, single characters, Unicode combining marks, strings that are prefixes of each other. Every property-based failure gets shrunk to a minimal reproducing case, which is how a six-hour bug hunt eventually collapsed into a two-character counterexample I could reason about on paper.

After the Jaro-Winkler fix and a handful of smaller ones, the fuzzer reached zero divergences across every algorithm and input class it could generate. That number, not the passing unit tests, is the claim I actually stand behind. But notice the caveat hiding in that sentence: zero divergences on everything that could cross the pipe. Two things could not.

The door I closed on myself

Several of textdistance's alignment algorithms — Needleman-Wunsch, Smith-Waterman, Gotoh — accept a sim_func parameter: an arbitrary Python callable that scores the similarity of two characters. The test suite exercises it:

# From the original test suite. This cannot be serialized.
alg = NeedlemanWunsch(sim_func=lambda a, b: 1 if a == b else -1)

A lambda cannot be serialized into JSON and sent down a pipe to a Rust subprocess. It is a closure over a live Python interpreter. There is no workaround that isn't a horror, no eval-strings-in-Rust, no RPC-callback-per-character scheme that would be slower than just running the Python.

So those tests fail. 22 of them, permanently, by architecture rather than by bug. This is the direct, foreseeable cost of the subprocess decision from the beginning of this article. PyO3 would have handled it natively: a #[pyfunction] can hold a reference to a Python callable and invoke it from Rust mid-algorithm. I traded that capability for build simplicity and debuggability, and for 28 algorithms the trade was clearly right. For these 4, I built a wall and then walked into it.

If I ran this project again, I would keep the subprocess architecture for development and verification, it earned it's keep during fuzzing, and add a PyO3 layer at the end specifically for callable-taking algorithms. That hybrid was always possible. I just didn't see the need until the tests told me.

The 15th decimal place

The other place the port compromised was subtler, and it's the result I'm least happy reporting: the "pure Rust" story does not fully hold for the compression-based algorithms.

Normalized compression distance, from Cilibrasi and Vitányi's work on clustering by compression, approximates the information distance between strings using a real compressor:

NCD(x, y) = (C(xy) − min(C(x), C(y))) / max(C(x), C(y))

By construction, the output is exquisitely sensitive to the compressor's exact byte counts and the arithmetic done on them.

The original library computes arithmetic-coding probabilities using Python's Fraction, exact rational arithmetic, no rounding. My Rust implementation used f64. The fuzzer caught divergences on the order of 1e-15: not wrong in any way a human would notice, but not equal, and for NCD "close" is doing real work in the formula, because those values get subtracted and divided in ways that can amplify the drift.

I tried rational arithmetic in Rust. I tried reordering operations to match Python's evaluation order. What shipped is the honest defeat: for the arithmetic-coding NCD path, the final distance computation moved back into the Python adapter, where Fraction guarantees exact parity. Rust still does the heavy lifting; Python does the last arithmetic mile. Eight algorithms carry that asterisk, and I'd rather document the asterisk than pretend it isn't there.

What the port actually proved

None of these four things — the JSON pipe, the Winkler threshold, the fuzzing harness, the sim_func wall were about writing Rust. They were about the much slower work of finding every place a fast, plausible looking reimplementation quietly disagrees with the thing it's replacing, and then deciding, for each one, whether to fix it, work around it, or write it down and ship anyway.

That's the actual deliverable here, more than the crate itself: not thirty algorithms in Rust, but a documented account of where equivalence held, where it took a 35 year old paper to restore, and where it simply didn't. A port you can't interrogate isn't really verified, it's just translated. This one, at zero fuzz divergences and two known, named exceptions, is the former.

References

life4/textdistance — the original Python library.
Len3hq/textdistance-rs — the Rust port discussed throughout.
Jaro, M. A. (1989). Advances in record-linking methodology as applied to matching the 1985 census of Tampa, Florida. Journal of the American Statistical Association, 84(406), 414–420.
Winkler, W. E. (1990). String Comparator Metrics and Enhanced Decision Rules in the Fellegi-Sunter Model of Record Linkage. Proceedings of the Section on Survey Research Methods, American Statistical Association.
McKeeman, W. M. (1998). Differential Testing for Software. Digital Technical Journal, 10(1), 100–107.
Claessen, K., & Hughes, J. (2000). QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP '00).
Cilibrasi, R., & Vitányi, P. M. B. (2005). Clustering by Compression. IEEE Transactions on Information Theory, 51(4), 1523–1545.

The full port and the DECISIONS log this writeup is pulled from is up at Len3hq/textdistance-rs if you want to dig in yourself.
Written for Hackathon Raptors, worth a follow if you're into this kind of writeup.

DEV Community: Daniel