HotPDF의 PDF 페이지 순서 버그: 물리적 구조 vs 논리적 구조

이 증상은 HotPDF 컴포넌트를 기반으로 구축된 페이지 복사(page-copying) 유틸리티에서 나타났습니다: 3페이지짜리 문서의 1페이지를 요청하면 일관되게 2페이지가 생성되었습니다. 인덱싱 로직을 확인해보았으나 아무런 문제도 없었습니다. 호출은 0부터 시작하는(0-based) 논리적 인덱스를 사용하고 있었고, 산술 연산도 올바르며 경계 조건(boundary conditions)도 완벽했습니다. 하지만 번번이 잘못된 페이지가 출력되었습니다

버그는 복사 코드에 전혀 있지 않았습니다. 그것은 HotPDF가 파일을 로드할 때 내부 페이지 배열을 구축하는 방식에 있었습니다

두 가지 순서, 그리고 혼란의 원인 한 가지

PDF 파일은 각각 객체 번호로 식별되는 간접 객체(indirect objects)의 모음입니다. 이 파일 구조는 해당 번호들이 읽기 순서(reading order)를 반영해야 한다는 어떠한 의무도 부과하지 않습니다. 객체 1이 2페이지를 가질 수도 있고, 객체 20이 1페이지를 가질 수도 있습니다. 실제로 읽기 순서를 정의하는 것은 페이지 트리입니다: 뷰어가 표시해야 하는 순서대로 페이지 참조 목록을 /Kids 배열에 나열하는 /Pages 딕셔너리의 계층 구조입니다 (ISO 32000-1 §7.7.3)

이 버그를 유발한 문서는 다음과 같은 페이지 트리 구조를 가졌습니다:

{ Pages 트리 루트, 객체 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { 논리적 페이지 1 }
         1 0 R    { 논리적 페이지 2 }
         4 0 R]   { 논리적 페이지 3 }
>>
endobj

이 파일은 우연히 바이트 스트림에서 객체 20 이전에 객체 1과 객체 4를 나열하고 있었습니다. 파일 순서대로 간접 객체를 순회(iterated)하며 페이지-유형 딕셔너리를 발견할 때마다 PageArr에 이를 기록하는(stamped) 파서(parser)라면, 결국 인덱스 0에 객체 1을, 인덱스 1에 객체 4를, 인덱스 2에 객체 20을 위치시키게 됩니다. 논리적 페이지 1은 PageArr[2]에 자리하게 됩니다. 인덱스 0의 페이지를 요청하면 그 대신 논리적 페이지 2를 가져오게 되는 것입니다

이것이 정확히 HotPDF의 두 내부 파싱 경로(parsing paths)가 하고 있던 작업입니다. PDF 1.3/1.4 파일에 사용되는 기존(traditional) 경로와 객체 스트림 문서(PDF 1.5 이상)에 사용되는 최신(modern) 경로 모두 /Kids 체인을 따르지 않고, 물리적인 파일 순서에 따라 간접 객체를 거닐며 PageArr를 구축했습니다

가설 확인하기

수정 작업에 손을 대기 전에, 이 불일치는 그저 추측이 아닌 증명되어야 했습니다. qpdf 명령줄 도구가 이를 간단하게 해줍니다:

{ shell }
qpdf --show-pages input.pdf
{ 출력은 Kids 순서를 보여줌: 20 0 R, 그다음에 1 0 R, 그다음 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ 읽기 순서대로 /Kids를 포함한 Pages 딕셔너리를 보여줌 }

각 페이지를 개별적으로 추출하고 파일 크기를 확인해보니 이 매핑이 맞다는 것이 확인되었습니다: PageArr[0]이 생성한 것은 논리적 페이지 2에 속한 콘텐츠였으며, PageArr[2]는 논리적 페이지 1을 보관하고 있었습니다. 이 순환적 이동(circular shift)이 바로 결정적 증거였습니다. 이것은 왜 이 문제가 여러 다양한 원본 문서에서 나타났는지도 설명해주었습니다: 논리적으로 나중에 오는 페이지보다 앞선 페이지가 우연히 더 높은 객체 번호를 갖게 되는 모든 PDF에서 이 버그가 촉발되는 것입니다

PDF가 이런 상태에 이르게 되는 데는 간단한 이유가 있습니다. 증분 저장(Incremental saves)은 업데이트된 객체를 새로운 객체 번호와 함께 덧붙이며(append), 상호 참조 테이블의 예전 슬롯은 아무 곳도 가리키지 않게 둡니다. 표지 페이지를 추가하는 편집기는 Kids 배열 내의 위치에 상관없이 높은 객체 번호로 그것을 삽입합니다. 어떤 생성기(generators)는 논리적인 페이지 순서보다는 콘텐츠 스트리밍에 편리한 순서대로 페이지를 단순히 작성하기도 합니다. PDF 포맷은 그들이 반드시 다른 방식으로 해야 한다고 강제하지 않습니다

해결책: Kids 배열 따르기

올바른 접근 방식은 간접 객체를 스캔하는 것이 아니라 카탈로그 루트에서부터 /Kids 체인을 거닐며 PageArr를 구축하는 것입니다. 두 파싱 경로가 초기 패스(initial pass)를 완료한 후, 논리적 순서를 해결하는 후처리 단계가 추가되었습니다:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { FRootIndex를 통해 루트 /Pages 딕셔너리 찾기 }
  PagesObj := FindPagesRootFromCatalog;
  if PagesObj = nil then Exit;

  KidsIndex := PagesObj.FindValue('Kids');
  if KidsIndex < 0 then Exit;
  KidsArray := THPDFArrayObject(PagesObj.GetIndexedItem(KidsIndex));

  SetLength(NewPageArr, KidsArray.Items.Count);
  PageIndex := 0;

  for I := 0 to KidsArray.Items.Count - 1 do
  begin
    RefObj     := THPDFLink(KidsArray.GetIndexedItem(I));
    PageObjNum := RefObj.Value.ObjectNumber;

    Found := False;
    for J := 0 to Length(PageArr) - 1 do
    begin
      if PageArr[J].PageLink.ObjectNumber = PageObjNum then
      begin
        NewPageArr[PageIndex] := PageArr[J];
        Inc(PageIndex);
        Found := True;
        Break;
      end;
    end;
    { 페이지가 아닌 Kids (중간 /Pages 노드)는 일치 항목을 생성하지 않음; 건너뛰기 }
  end;

  if PageIndex > 0 then
  begin
    SetLength(PageArr, PageIndex);
    for I := 0 to PageIndex - 1 do
      PageArr[I] := NewPageArr[I];
  end;
end;

이 호출(call)은 모든 객체가 카탈로그화되었지만 어떠한 페이지 작업도 서비스되기 전인 각 파싱 경로의 끝부분에 들어갑니다:

{ 기존 경로 }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ 최신 경로 (객체 스트림) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

이 재정렬 단계의 복잡도는 O(n * m)이며, 여기서 n은 Kids의 개수이고 m은 현재 PageArr의 길이입니다. 그러나 평면적인 페이지 트리(모든 리프 노드의 깊이가 1이며 실세계 PDF의 압도적 다수를 차지함)를 지닌 문서의 경우 이 둘은 같은 값이며 그 비용은 무시할 만합니다. 깊게 중첩된 페이지 트리는 여기에 표시된 단일 수준(single-level) 접근 방식이 아닌 재귀적 걷기(recursive walk)를 요구하며, 실제 프로덕션 구현에서는 그 경우를 따로 처리합니다

수정 후 CopyPageFromDocument 사용하기

ReorderPageArrByPagesTree가 적용된 상태에서, 논리적 페이지 인덱스들은 이제 예상대로 작동합니다. 상위 수준의 CopyPageFromDocument는 0부터 시작하는 논리적 인덱스를 취해 올바른 페이지를 목적지 문서로 복사합니다:

var
  Source, Dest: THotPDF;
begin
  Source := THotPDF.Create(nil);
  Dest   := THotPDF.Create(nil);
  try
    Source.LoadFromFile('source.pdf');

    Dest.FileName := 'extracted.pdf';
    Dest.BeginDoc;

    { 논리적 페이지 0 (사용자가 보는 첫 페이지) 복사 }
    Dest.CopyPageFromDocument(Source, 0, 0);

    Dest.EndDoc;
  finally
    Source.Free;
    Dest.Free;
  end;
end;

CopyPageFromDocument는 로우(raw) PageArr 인덱스에 의존하는 대신 내부적으로 페이지 트리 순서를 조회하므로, 물리적 순서와 논리적 순서가 어긋나는(diverge) 문서에서도 올바르게 작동합니다. 일괄(batch) 작업을 위해 InsertPagesFromDocument는 논리적 인덱스의 배열을 받아들여 이를 한 번의 패스로(in one pass) 복사합니다

이 사례가 PDF 파싱에 대해 밝혀주는 사실

PDF 사양은 명확합니다: 논리적 페이지 순서는 객체 번호나 바이트 오프셋이 아닌 페이지 트리의 /Kids 배열에 의해 정의됩니다 (ISO 32000-1 §7.7.3.2). 지름길로 다른 순서 방식을 취하는 파서는 대부분의 생성기가 자연스러운 순서대로 페이지를 작성하고 순차적인 객체 번호를 할당하기 때문에 접하는 문서 대다수에서 올바른 결과를 도출할 것입니다. 버그는 누군가 점진적으로 편집된(incrementally edited), 다른 도구에 의해 재구성된, 또는 다른 레이아웃을 선택한 소프트웨어에 의해 생성된 PDF를 로드할 때까지 숨어 있습니다

자체 생성된 PDF에 대해서만 테스트하는 것은 이러한 종류의 문제를 완전히 놓치게 만듭니다. 따라서 페이지 순서 회귀(regression)에 대한 해결책은 다양한 출처의 문서 코퍼스(corpus)를 요구합니다: 증분 저장, 표지 페이지가 삽입된 스캔 문서, 그리고 객체 그래프를 다르게 선형화(linearize)하거나 최적화하는 도구에 의해 생성된 PDF 말입니다. 원래 버그를 유발했던 문서는 회귀 테스트 제품군(regression suite)에 영구적으로 남아있어야 합니다

HotPDF 컴포넌트 페이지는 CopyPageFromDocument, InsertPagesFromDocument, 그리고 MovePage를 포함한 페이지 작업의 전체 API를 다루고 있습니다