Hunting Three Bugs That Only Appear in a Mirror

Once the tail calls flattened the stack, the self-compiled compiler stopped crashing from exhaustion and started failing in a stranger way. On one input it trapped and exited; on another it produced no output where it should have produced a long program; the symptom moved depending on what it was asked to compile. A moving symptom is the signature of a bug that corrupts memory rather than following a clean logical path, and it is the kind that resists reasoning, because the same defect wears a different face each time you look. The only way through was to stop reasoning about what should happen and measure, at finer and finer resolution, where the compiled compiler’s behaviour first diverged from the interpreter’s.

Narrowing by trace

The method was unglamorous and it worked. The reference — the compiler running under the interpreter — was known to be correct, so it became the oracle: whatever it did at each stage was the right answer, and the question was only where the compiled version first did something else. Print a marker after tokenising: both agree. After parsing: both agree. So the trap was not in reading the program but in generating code from it. Push the markers inward — into the pass that resolves names, then into its individual steps, then into the single function that walks expressions, then into the branches of that function’s big case analysis. Each marker halved the territory. What began as “somewhere in a program of thousands of lines” became “in this function, on this kind of expression,” and finally “on this exact shape, at this line.” The bug had nowhere left to hide, and there turned out to be three of them, uncovered one narrowing at a time.

The eager check that read garbage

The first was in how the compiler tests whether a value matches a pattern. To check a constructor with a payload — is this the Some case, and if so, look at what’s inside — the generated code checked the tag and examined the payload together, as a single combined condition. But “together” meant the payload was examined even when the tag did not match. For a value of the wrong shape, the thing sitting where a payload pointer would be was not a pointer at all; following it read arbitrary memory, and on a wild enough value the program trapped. In the ordinary compiler this had never mattered, because the values it happened to check always had a compatible shape. The compiler’s own code, compiling itself, finally checked a pattern against a value shaped differently enough to step off the edge. The fix was to make the check short-circuit — examine the payload only after the tag has matched — which is what a hand-written check would do without thinking, and which the generator had simply never been made to emit.

The equality that compared addresses

The second was subtler and is, in a small way, a classic of the genre. In two places the compiler compared strings — a name against a name — with the ordinary equality operator. In the full compiler, the type inferencer knew those operands were strings and arranged for a real character-by-character comparison. But the compiler compiling itself has no inferencer running over the code it emits; it is the code being emitted. And in that setting, comparing two strings with the plain operator fell through to comparing their addresses — whether they were the same object in memory, not whether they held the same characters. Two equal names built at different times compared as unequal. The effect was quietly catastrophic: a pass that collects the free variables of a function started inventing captures that weren’t there, because a name failed to match itself, and the generated code then referred to variables it never defined. The fix was to compare those strings by content explicitly. But the bug is worth pausing on, because it is exactly the shape of the classic bootstrap trap: a convenience the host provides — here, the inferencer’s knowledge that these are strings — silently absent when the language stands on its own, and wrong in a way that only self-application reveals.

The carriage return, five parts later

The third had been waiting a long time. With the other two fixed, the two outputs — the reference and the self-compiled — were finally almost identical, differing by a handful of bytes in one place. The compiler emits string data with certain characters escaped so they survive being written into the output, and the routine that did the escaping handled a newline and a tab but had quietly omitted the carriage return. A stray carriage return therefore passed through unescaped and corrupted the very output it sat in — so that a name like Err came out mangled. This exact omission had been noticed and fixed once before, five parts earlier, the first time a wire-protocol library met the native compiler and its binary payloads exposed the same missing escape. It had been fixed there, in one place, and the same gap survived in another — and only the compiler escaping its own string data, the last four bytes of difference between the two outputs, brought it back into the light. It was added, and the last difference closed.

What the mirror shows

Three bugs, and a single family resemblance. None of them was a flaw in the compiler’s logic; the interpreter had run that logic correctly all along. Each was a flaw in the code the compiler emitted, and each stayed invisible until the emitted code was made to do the one thing it had never done — run the compiler’s own program, whose shapes and names and byte sequences were more varied and more adversarial than any test had thought to be. A pattern checked against a value of surprising shape; a name compared against itself without a type system to help; a control character in the compiler’s own strings. These are the bugs a program can only find by looking into a mirror, because only its reflection exercises it as thoroughly as it exercises everything else. With the three of them fixed, the two outputs were, at last, worth comparing byte for byte. The final part is that comparison.