Guidedog / 문서 0.2.0

알고리즘에 앞서는 불변식¶

유용한 불변식은 알고리즘 실행 중 유지되는 사실과 종료 후 호출자가 의존할 사실을 밝힌다. 반복문보다 먼저 작성한다.

전위 순회에서의 서브트리 구간¶

트리를 전위 순회로 출력한다고 가정한다. 노드는 자식보다 먼저 출력되고 각 부분 트리는 연속한다. \(e_i\)를 노드 \(i\)와 모든 자손 직후의 첫 인덱스라 하자.

(3)¶\[\operatorname{subtree}(i) = [i,e_i), \qquad i < e_i \le N.\]

명제. 인덱스를 \(e_i\)로 옮기면 부분 트리를 건너뛸 수 있다.

증명. 연속성에 따라 모든 자손은 \(e_i\) 앞에 있다. 배타적 끝의 정의에 따라 이후 노드는 \(e_i\) 이상에 있다. 따라서 그곳으로 이동하면 정확히 부분 트리만 건너뛴다. 렌더러가 가정에 의존하기 전에 검증기가 확인한다.

전체 스캔은 각 노드를 한 번 방문하므로 순회 비용은 \(O(N)\)이다. 부분 트리 건너뛰기는 인덱스 갱신 한 번이면 된다. 페이로드 작업의 비용은 여전히 발생한다. 상수 시간 건너뛰기와 상수 시간 렌더링을 혼동하지 않는다.

렌더러는 먼저 바이트 수 \(m\)을 측정한다. 호출자의 출력 용량을 \(c\)라 하자.

\[m \le c \quad \Longrightarrow \quad \text{출력을 시작할 수 있다}.\]

측정과 출력 순회는 같은 규칙을 쓴다. 성공하면 정확히 \(m\)바이트를 써야 한다. 실패 시 유효한 부분 산출물을 반환하지 않는다. 게시를 호스트가 맡으므로 불완전한 바이트가 이전 출력을 대체할 수 없다.

캐시 키는 결과를 바꿀 수 있는 모든 데이터를 포함해야 한다. 소스만으로는 부족하다. 포함 파일, 템플릿, 설정, 참조 조회, 리소스, 어댑터 버전도 출력에 영향을 준다. 기록된 의존성이 일치할 때만 재사용한다. 키가 같아도 출력이 없으면 재사용할 수 없다.

테스트는 코어 경계에 실패하는 할당자를 설치하고 출력 내용을 비교한다. import도 감사한다. 결과 확인 없이 할당 수만 세면 거부 때문에 문서 일부가 조용히 사라지는 문제를 놓칠 수 있다.