鏡の中にだけ現れる三つのバグを狩る

末尾呼び出しがスタックを平らにすると、自己コンパイルしたコンパイラは枯渇でクラッシュするのをやめ、より 奇妙なふうに失敗し始めた。ある入力では trap して exit し；別のでは長いプログラムを生むべきところで出力を 生まず；症状がコンパイルするよう求められたものによって動いた。動く症状は、綺麗な logic の道を辿るでなく メモリを壊すバグの署名で、それは推論に抵抗する類だ、なぜなら同じ欠陥が見るたびに違う顔を着けるから。 通り抜ける唯一の道は、何が起きるべきかを推論するのをやめ、より細かい解像度で、コンパイルされた コンパイラの振る舞いが interpreter のそれから最初にどこで分岐するかを測ることだった。

trace による絞り込み

方法は華々しくなく、そして効いた。リファレンス —— interpreter の下で走るコンパイラ —— は正しいと知られて いたので、それが oracle になった：各段階でそれがしたことが正しい答えで、問いはコンパイル版が最初にどこで 違うことをしたか、だけだった。tokenize の後に marker を print：両方一致。parse の後：両方一致。だから trap はプログラムを読むことでなく、それからコードを生成することにあった。marker を内へ押す —— 名前を 解決する pass へ、それからその個々のステップへ、それから式を歩く単一の関数へ、それからその関数の大きな 場合分けの分岐へ。各 marker が領土を半分にした。「数千行のプログラムのどこか」で始まったものが「この 関数の、この種の式で」になり、ついに「この正確な形の、この行で」になった。バグは隠れる場所を失い、そして 三つあると判明した、一度に一つの絞り込みで暴かれて。

garbage を読んだ性急なチェック

一つ目は、値がパターンに match するかをコンパイラがテストするやり方にあった。payload つきの constructor を チェックするには —— これは Some の場合か、そうなら中身を見る —— 生成コードは tag と payload を一緒に、 単一の結合した条件としてチェックした。だが「一緒に」は payload が tag が match しないときでも調べられる ことを意味した。間違った形の値では、payload ポインタがあるはずの場所に座っていたものはポインタでは まったくなく；それを辿ることは任意のメモリを読み、十分に wild な値ではプログラムが trap した。普通の コンパイラではこれは決して問題にならなかった、なぜならそれがたまたまチェックした値は常に互換な形を持って いたから。コンパイラ自身のコードが、自分自身をコンパイルして、ついに縁を踏み外すほど十分に違う形の値に 対してパターンをチェックした。修正はチェックを short-circuit させること —— tag が match した後にだけ payload を調べる —— で、それは手書きのチェックが考えずにすることで、そして生成器が単に emit するよう 作られたことがなかったことだ。

アドレスを比べた等価

二つ目はより微妙で、そして小さなやり方で、この種の古典だ。二箇所でコンパイラが文字列を比べた —— 名前を 名前と —— 普通の等価演算子で。完全なコンパイラでは、型推論器がそれら operand が文字列だと知り、本物の 一文字ずつの比較を手配した。だが自分自身をコンパイルするコンパイラには、それが emit するコードの上を 走る推論器がない；それが emit されているコードなのだ。そしてその状況では、二つの文字列を素の演算子で 比べることが、そのアドレスを比べることに落ちた —— それらがメモリの中で同じオブジェクトかどうか、同じ 文字を持つかどうかでなく。違う時に建てられた二つの等しい名前が、等しくないと比較された。効果は静かに 破滅的だった：関数の自由変数を集める pass が、そこに無い capture を発明し始めた、なぜなら名前が自分自身に match しなかったから、そして生成コードがそれから決して定義しない変数を参照した。修正はそれらの文字列を 内容で明示的に比べることだった。だがバグは立ち止まる価値がある、なぜならそれはまさに古典的な bootstrap の 罠の形だから：ホストが提供する便利さ —— ここでは、これらが文字列だという推論器の知識 —— が言語が自分自身 で立つとき静かに不在で、そして自己適用だけが明かすふうに間違っている。

キャリッジリターン、五 Part 後

三つ目は長く待っていた。他の二つが直ると、二つの出力 —— リファレンスと自己コンパイル —— はついにほとんど 同一で、一箇所で一握りのバイトだけ違った。コンパイラは特定の文字を escape して文字列データを emit する、 出力へ書き込まれるのを生き延びるように、そして escape をするルーチンは newline と tab を扱ったが、 キャリッジリターンを静かに省いていた。だから迷子のキャリッジリターンが escape されずに通り抜け、それが 座るまさにその出力を壊した —— だから Err のような名前が損なわれて出てきた。この正確な省略は、五 Part 前に一度、以前に気づかれ直されていた、wire-protocol ライブラリが初めて native コンパイラに会い、その バイナリの payload が同じ欠けた escape を露呈したとき。それはそこで、一箇所で直され、そして同じ gap が 別の場所で生き残った —— そしてコンパイラが自分自身の文字列データを escape すること、二つの出力の間の 最後の四バイトの違いだけが、それを光の中に連れ戻した。それが足され、最後の違いが閉じた。

鏡が見せるもの

三つのバグ、そして単一の家族的類似。そのどれもコンパイラの logic の欠陥でなかった；interpreter は その logic をずっと正しく走らせていた。それぞれがコンパイラのemit したコードの欠陥で、それぞれが emit されたコードが決してしたことのない一つのこと —— コンパイラ自身のプログラム、その形と名前とバイト列が どのテストが思いついたよりも多様で敵対的なもの、を走らせること —— をさせられるまで見えなかった。驚くべき 形の値に対してチェックされたパターン；助ける型システムなしに自分自身と比べられた名前；コンパイラ自身の 文字列の中の制御文字。これらはプログラムが鏡を覗くことでしか見つけられないバグだ、なぜならその反射だけが、 それが他のすべてを行使するのと同じ徹底で、それを行使するから。三つが直ると、二つの出力は、ついに、 バイトごとに比べる価値があった。最後の Part はその比較だ。