DEV Community

Daniel
Daniel

Posted on

Fifty Green Tests, Two Real Bugs, and the Oracle One `npm install` Away

#node #testing #javascript #programming

A QR code cannot hide a bug from you, because checking it costs nothing. You point a phone at it. A URL pops up or it doesn't.

That's why I picked a QR encoder for a hackathon whose entire rule is standard library only: no packages, an empty dependency manifest, verified at submission. I rebuilt qrcode, the library nearly every JavaScript project reaches for, in 844 lines of Node and an empty dependency manifest. By the end I had fifty tests, all green, and two bugs that not one of them could see. A phone found the first in four seconds, on day three, the first time I bothered to try. A tool one command away would have found both on the first afternoon. I just wouldn't run it, because running it felt like cheating.

The encoder was the easy part. This is a write-up about the hard part, which was verification, which I also got wrong.

What npm install qrcode actually installs

qrcode gets 24 million downloads a week. Before rebuilding it I looked at what it was.

npm install qrcode writes 29 packages to disk, 2.4 MB. Three of them do the actual work: qrcode itself, pngjs for image output, and dijkstrajs, a shortest-path graph algorithm it uses to choose the most compact way to split text across QR's encoding modes. The other 26 are yargs and its dependency tree, there for a command-line interface: cliui, string-width, wrap-ansi, emoji-regex, y18n, camelcase, and down. They install on your server whether or not you ever run qrcode from a terminal. Call require('qrcode') and you have shipped an internationalized argument parser and everything under it.

This isn't a complaint about qrcode. It's that "one dependency" was a fiction. The number was 29, and I hadn't read a line of any of them, which is the normal condition of every Node service I've worked on: a few thousand packages of strangers' code, unread, running as me. The polite word is "dependency." The accurate word is borrowed trust. I trust these people because auditing them is more work than the feature is worth.

The hackathon's premise is that we borrow far more than we need. So how much of the 29 is load-bearing?

The parts you build, and the one you don't

Most of it. The specification (ISO/IEC 18004) is a stack of small closed problems: Reed-Solomon error correction over GF(2โธ), which is two lookup tables and polynomial division; the module matrix with its finder squares and timing lines; eight mask patterns and a penalty function to choose one; fifteen and eighteen bits of metadata wrapped in BCH codes. None of it needs anything outside std.

The one place I stopped was DEFLATE. PNG compresses its pixels with zlib, and a DEFLATE encoder is a hackathon project by itself. node:zlib is standard library; I called deflateSync and wrote the rest of the PNG by hand: signature, chunks, CRCs. That's the single asterisk on "zero dependencies." It's the opening line of my README and the last time I'll mention it, because it isn't where this goes.

Fifty green tests and a phone that said no

By the end of day two I had a test suite I trusted. It wasn't lazy.

Galois-field arithmetic, checked against the values printed in the standard. Reed-Solomon output, checked byte for byte against the standard's worked example: encode "01234567" at version 1, level M, and Annex I gives you the exact codewords. The matrix, checked by an invariant: total modules minus fixed-pattern modules must equal the data-bit count, for every version. Format and version bits, checked against the standard's BCH tables. And a round-trip: a small decoder in the test file that walked the data path and pulled the bytes back, asserting decode(encode(text)) === text for every text, every error level, every mask.

Fifty tests. Green. I rendered "01234567", held up my phone, and got nothing. Bigger, more light, a printout, a different scanner app. Nothing scanned.

The bug a scanner reads first

QR format information is fifteen bits (mask, error level, ten of BCH check) written twice for redundancy, one copy in an L around the top-left finder square. A scanner reads it before it reads anything else.

This placed the first six:

for (let i = 0; i <= 5; i++) modules[8][i] = bit(i);
Enter fullscreen mode Exit fullscreen mode

modules[row][col]. That runs along row 8. It should run down column 8:

for (let i = 0; i <= 5; i++) modules[i][8] = bit(i);
Enter fullscreen mode Exit fullscreen mode

Row and column, swapped, in both copies. Every bit a scanner needs to begin was on the wrong axis.

The round-trip test didn't catch it because it never read the format bits. They're fixed-function modules, and the data-path walk skips them by definition. The payload round-tripped perfectly, and the payload was never where the bug was.

The BCH test didn't catch it because it checked the value, not the address. My fifteen bits were the correct fifteen bits. I had verified what they were and assumed that told me where they went.

Fifty tests, one blind spot

The tests were not weak. They were the wrong shape.

Every one was rigorous about computation: fields, polynomials, BCH. Computation is the part of a QR code that looks hard, and it's the part I'd worked to understand. None checked placement, because by the time I wrote tests, placement felt beneath checking. Put the bits where the figure shows them. I wasn't going to get that wrong.

A test suite is built from its author's model of where the danger is. Mine faithfully encoded mine. The bug lived in the exact gap between "I checked this closely" and "this didn't need checking," and fifty green marks correctly reported that everything I'd thought to test was fine.

That generalizes past QR codes. A passing suite is evidence about the parts you thought to check. Its silence is not evidence.

The oracle I refused to install

qrcode was one npm install away the whole time. I could have generated the same code with both, in a scratch directory that never touched my submission, and diffed the matrices. The transposed bits would have shown immediately.

I didn't, because on a zero-dependency project, installing the thing I was replacing felt like cheating. Not against a rule (there is no such rule), but against the point. I was doing this properly. From the spec. Myself.

That reflex is the same one the hackathon criticizes, pointed inward. "Don't blindly trust a stranger's package" and "don't blindly trust your own code" are one statement. Both kinds of trust need an outside check, and I had argued myself out of the best one on the table.

Writing this, I finally ran the diff. The broken build differs from qrcode on "01234567" by twelve modules, all in the format region, all visible in the first comparison anyone would run. A phone in four seconds, or one diff on day one. I took neither.

The diff also found a second bug.

The second bug, the one that scanned fine

With the format bits fixed, my codes scanned, and I thought I was done. Then I diffed qrkit against qrcode properly: every byte-mode input I could think of, versions 1 through 10, all four error levels. 47 of 48 came back byte-identical. The one that didn't was the string "zero dependency": same version, same mask, same mode, 124 modules different.

It was the padding. When your data doesn't fill the symbol, the spec tops it up with two alternating codewords, 0xEC and 0x11, and it says the first is always 0xEC. Mine:

while (bytes.length < capacity) bytes.push(pad[bytes.length % 2 === 0 ? 0 : 1]);
Enter fullscreen mode Exit fullscreen mode

I picked the pad byte from its absolute position in the stream. When the real data ended on an even byte count the first pad came out 0xEC, correct by accident. When it ended odd, like "zero dependency" does, the first pad came out 0x11 and the entire tail inverted.

This bug cannot break a scan. Pad codewords are discarded before the decoder reads your data. The round-trip test walked over these exact bytes on every run and could not see it, because "correct" meant "the text comes back," and the text always came back. Wrong, and fully functional. Only a byte comparison against an implementation I didn't write could surface it, and that was the comparison I'd spent three days avoiding.

The fix counts the pad bytes instead of the stream bytes, plus a fifty-first test so it can't come back:

for (let p = 0; bytes.length < capacity; p++) bytes.push(pad[p % 2]);
Enter fullscreen mode Exit fullscreen mode

The spec that disagrees with itself

There's a third source of truth here, and it's also unreliable.

Mask selection is meant to be deterministic: apply eight masks, score each, keep the lowest. But the rule that penalizes finder-lookalike patterns is loose enough that implementations disagree on what counts. qrkit, whose scoring I ported from Nayuki's reference implementation, and qrcode, which rolls its own, choose different masks on three of every eight inputs I tested. Both scan.

And a 2008 note by Johan Persson works through the standard's own example, the "01234567" I'd been testing against, and shows the mask it picks is not the lowest-scoring one by the standard's own rules. The reference fails the reference.

So the spec is an oracle you cross-check too. There's no document that hands you the answer. There's a quorum: the spec, its examples, other implementations, a physical scanner. Where they disagree, you decide. I lost an evening treating my mask disagreement with qrcode as a defect before I understood that.

The scorecard, told honestly

Measure Result
npm install qrcode 29 packages, 2.4 MB
yargs and its subtree 26 of the 29
qrkit 0 dependencies, one 844-line file
Format matrix vs qrcode, all 4 EC levels by 8 masks 32 / 32 byte-identical
Byte-mode output vs qrcode, versions 1 to 10 by 4 EC levels, after the fix 48 / 48 byte-identical
Mask choice matching qrcode when both choose freely 5 / 8
Encode speed, qrkit vs qrcode 677 ยตs vs 271 ยตs
Bugs shipped 2
found by 50 unit tests 0
found by a phone 1
found by a diff available on day one 2

The speed number held at 2.5x across four runs. That's not measurement noise, qrkit is genuinely slower. It re-scores all eight masks with the full penalty function on every build; qrcode has had years to not do that. The value here is the third row of the table, not the seventh.

What I didn't do

I wrote this list before I wrote the README, because the failure mode of a solo project is finding out your limits were load-bearing.

Byte and numeric encoding modes only, no alphanumeric, no kanji, so an all-caps string that qrcode packs tighter comes out larger from qrkit. Versions 1 through 10, not 40. No ECI, no structured append. No decoder: reading a code back out of a photo is thresholding, perspective correction, and error location, and it's the same large, fragile surface that would have sunk the project if I'd tried it in a weekend.

What I'd tell someone building one of these

  • Reach for the oracle you didn't write first, before the first unit test. A phone, a reference implementation, a printed example. If you're rebuilding X, npm install X in a scratch directory and diff. That's the control group.
  • Treat a green suite as a map of the ground you thought to cover. Ask what class of bug it structurally cannot see.
  • "Different function" is not "independent implementation." An encoder and a decoder written by one person from one reading of one spec agree with each other, not with the world.
  • Some bugs never fail a functional test, because the function still works. Conformance is a separate question, and only a foreign implementation answers it.
  • Write down what you didn't do.

Where trust actually comes from

I expected the lesson to be about dependencies, that I'd finish having shown you don't need the tree.

That isn't it. Deleting the dependencies bought me nothing; an empty manifest is just a different set of things to be wrong about. Writing it myself bought me less than I thought, because every check I built came from the same head as the bug. My test file is 769 lines against 844 of source. I spent nearly as long proving the thing as building it, and I still shipped two defects, because the proof and the code had the same author and the same blind spot.

The bugs died when the code met something with no stake in whether I was right: a phone camera, a committee's standard, a stranger's hand arithmetic from 2008, and the library I was too proud to install.

References

Built for the Zero Dependency Hackathon by Hackathon Raptors. #hackathonraptors

Top comments (0)