거울 속에서만 나타나는 세 버그를 사냥하다

말단 호출이 스택을 평평하게 하자, 자기 컴파일한 컴파일러는 고갈로 크래시하기를 멈추고, 더 이상한 방식으로 실패하기 시작했다. 어떤 입력에서는 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는 그 비교다.