기술 문서

PDFlibPas 네임 트리: 사이클, 나쁜 Limits, 거대한 리프

/Dests 네임 트리의 루트에 자식 둘을 둔 PDF를 만들어 보세요. 첫 자식은 /Limits [(a) (z)]를 선언하고 /Kids 배열이 루트를 곧장 다시 가리킵니다. 둘째 자식은 (chapter7)의 진짜 엔트리를 갖고 있지만 limits가 거꾸로 쓰여 있습니다. [(z) (a)]입니다. 교과서적인 네임 트리 탐색에 chapter7을 물으면 뷰어가 점프할 수 있는 대상인데도 스택이 다할 때까지 재귀하거나 "못 찾음"을 돌려줍니다. 파일 전체는 약 2킬로바이트에 들어가고 모든 오브젝트는 깨끗하게 파싱됩니다

그 파일은 하나의 구조에 서로 다른 함정 세 개를 채워 넣습니다. /Kids 사이클, 갖고 있지 않은 키를 주장하는 범위, 그리고 어떤 것과도 매치될 수 없는 범위입니다. 네 번째 함정은 훨씬 큰 파일이 필요합니다. 단일 리프가 32,768개 넘는 이름/값 쌍을 담는 순간, "어느 리프"와 "어느 엔트리"를 하나의 32비트 정수에 짜 넣는 코드는 엉뚱한 쌍을 가리키기 시작합니다. 이 글의 나머지는 함정들을 하나씩 훑고, 읽는 쪽이 무엇을 해야 하는지, 그리고 그렇게 만든 파일에서 Delphi 호출이 어떻게 굴러가는지 다룹니다

네임 트리와 넘버 트리 위에 앉은 네 가지 PDF 기능

네임 트리와 넘버 트리는 큰 키 집합을 오브젝트에 사상하는 모든 PDF 기능의 기반이고, losLab의 Delphi용 PDF Library인 PDFlibPas는 그중 넷을 공개 TPDFlib 메서드로 노출합니다. ISO 32000-1 §7.9.6이 네임 트리(문자열 키, Table 36)를, §7.9.7이 넘버 트리(정수 키, Table 37)를 정의합니다. 루트와 중간 노드는 /Kids를 달고, 리프는 정렬된 키/값 쌍을 /Names나 /Nums에 담으며, 루트가 아닌 모든 노드는 그 아래의 가장 작은 키와 가장 큰 키를 담은 2원소 /Limits 배열을 갖추는 것이 규정입니다

트리사는 곳규격PDFlibPas 읽기 API
이름 붙은 대상이름 딕셔너리의 /Dests§12.3.2.3GetNamedDestination, 이어서 GetDestPage / GetDestType
페이지 레이블카탈로그의 /PageLabels(넘버 트리)§12.4.2GetPageLabel
첨부이름 딕셔너리의 /EmbeddedFiles§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
문서 수준 JavaScript이름 딕셔너리의 /JavaScript§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

두 행에는 숨은 주름이 있습니다. 이름 붙은 대상에는 오래된 PDF 1.1 형식, 즉 이름 오브젝트를 키로 하는 카탈로그의 평범한 /Dests 딕셔너리도 존재하고, GetNamedDestination은 그 딕셔너리를 먼저 확인한 뒤에야 PDF 1.2 네임 트리를 내려갑니다. JavaScript 행에는 전혀 다른 것을 읽는 이름이 비슷한 함수가 있습니다. GetDocJavaScript는 카탈로그 /AA 딕셔너리의 문서 트리거(WS, DS, WP, DP, DC)에 붙은 스크립트를 돌려주고, 문서가 열릴 때 실행되는 이름 붙은 패키지들은 /JavaScript 네임 트리에 살며 GlobalJavaScriptPackageName이 나열합니다

이 구조들은 전부 파일에서 옵니다. 명세는 작성자가 무엇을 만들어야 하는지 말해 줄 뿐, 읽는 쪽은 작성자나 망가진 증분 저장, 퍼저가 실제로 놓아 둔 것을 그대로 받습니다. 이는 악성 파일에 맞서 Pascal PDF 파서를 굳히기에서 배운 교훈과 같은 것으로, 버퍼 길이 대신 트리 모양에 적용한 것입니다

순환 /Kids 배열은 재귀 트리 걷기를 왜 크래시시킬까?

재귀 걷기는 순환 /Kids 배열에서 크래시합니다. 재귀 안의 어떤 것도 이미 들어간 노드를 기억하지 않으므로, 조상을 가리키는 자식 참조 하나가 유한한 파일을 끝없는 하강으로 바꿉니다. 정당한 트리도 사이클 없이 같은 피해를 줄 수 있습니다. 자식 하나짜리 노드의 4,096수준 체인은 유효한 문법이고 재귀 리더에게 4,096개 스택 프레임의 비용입니다

더 온건한 변형은 아예 크래시하지 않습니다. 두 /Kids 엔트리가 같은 리프를 참조하면 순진한 열거는 그것을 두 번 방문하므로, 첨부 개수는 문서 안 파일 수보다 크게 돌아오고 스크립트 목록은 같은 패키지를 두 번 보여 줍니다

PDFlibPas는 두 종류의 트리를 힙 위의 명시적 LIFO 스택과 딕셔너리 신원을 키로 하는 방문 집합으로 걷습니다. 노드는 팝될 때 표시됩니다. 순환 참조는 잠깐 스택에 앉을 수 있지만 돌아오는 대로 버려지고, 서로 다른 노드 각각은 자식을 정확히 한 번 확장합니다. 총 작업량은 서로 다른 딕셔너리의 수와 그들의 /Kids 배열 합산 길이로 갈리고, 4,096수준 체인은 4,096회 루프 반복과 4,096개 해시 집합 엔트리가 됩니다

PDFlibPas 네임 트리 순회: 루트로 되돌아가는 Kids 배열이 재귀 걷기의 스택을 넘어서게 하므로, PDFlibPas는 명시적 스택과 팝 시점에 노드를 표시하는 방문 집합을 쓰고, 자식을 오른쪽에서 왼쪽으로 푸시하며 GetPageLabel을 위해 리프를 파일 순서로 유지합니다
재귀가 루프가 되면 깊이는 더 이상 문제가 아닙니다. 4,096수준 체인은 그저 4,096회 반복과 4,096개 해시 집합 엔트리일 뿐입니다

재귀를 루프로 바꿀 때 사람들이 틀리는 부분이 순서입니다. 스택은 넣는 것을 뒤집으므로 자식은 마지막 인덱스부터 첫 인덱스 순으로 푸시해야 하고, 그러면 가장 왼쪽 자식이 먼저 팝되어 리프가 작성자가 쓴 왼쪽에서 오른쪽 순서로 나옵니다. 푸시가 아니라 팝에 표시하는 것도 같은 이유입니다. 푸시에 표시하고 오른쪽에서 왼쪽으로 푸시하면, 위치 0과 2가 공유하는 리프는 위치 2에게 점유되고 그 엔트리들은 파일이 말하는 것보다 늦게 나타납니다. 페이지 레이블이 그 순서에 의존하는데, 마지막 섹션이 보여 줍니다

다른 오브젝트 모델로 직접 트리 코드를 쓴다면, 우리가 권하는 모양이 이것입니다. 아래 노드 타입은 의도적으로 추상적이고 두 함수 모두 리더 쪽 코드지 라이브러리 호출이 아닙니다

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // 리프에서는 비어 있음
    Keys: TArray<string>;      // 리프 키, 잘 행동하는 작성자는 정렬해서 옴
    Values: TArray<Integer>;   // Keys와 평행
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// 여러분의 헬퍼: /Limits는 잘 만들어진 순서 쌍일 때만 가지치기할 수 있음
function LimitsExclude(Node: TTreeNode; const Key: string): Boolean;
begin
  Result := Node.HasLimits and (Node.LoKey <= Node.HiKey) and
    ((Key < Node.LoKey) or (Key > Node.HiKey));
end;

// 여러분의 탐색: 명시적 스택, 방문 집합, 팝에 표시
function FindValue(Root: TTreeNode; const Key: string;
  out Value: Integer): Boolean;
var
  Pending: TList<TTreeNode>;
  Visited: TDictionary<TTreeNode, Byte>;
  Node: TTreeNode;
  I: Integer;
begin
  Result := False;
  Value := 0;
  if Root = nil then
    Exit;
  Pending := TList<TTreeNode>.Create;
  Visited := TDictionary<TTreeNode, Byte>.Create;
  try
    Pending.Add(Root);
    while Pending.Count > 0 do
    begin
      Node := Pending[Pending.Count - 1];
      Pending.Delete(Pending.Count - 1);
      if Visited.ContainsKey(Node) then
        Continue;                      // 사이클이나 공유 자식: 이미 본 것
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // 오른쪽에서 왼쪽으로 푸시해 가장 왼쪽 자식이 먼저 팝되게
        for I := High(Node.Kids) downto 0 do
          if (Node.Kids[I] <> nil) and not LimitsExclude(Node.Kids[I], Key) then
            Pending.Add(Node.Kids[I]);
      end
      else
        for I := 0 to High(Node.Keys) do
          if (Node.Keys[I] = Key) and (I <= High(Node.Values)) then
          begin
            Value := Node.Values[I];
            Exit(True);
          end;
      // 이 리프에서의 미스: 형제들을 계속 팝
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

한 가지에서의 미스는 트리에 대해 아무것도 말하지 않는다

가장 흔한 탐색 지름길은 /Limits가 키를 커버하는 첫 자식을 골라 내려가고 형제는 다시 보지 않는 것입니다. 깨끗한 트리에서는 올바르고 빠릅니다. 도입부의 파일에서는 실패합니다. 첫 자식이 chapter7을 주장하다 루트로 되돌아가고, 다음 형제가 엔트리를 들고 있는데도 탐색은 빈손으로 끝납니다

PDFlibPas는 첫 그럴듯한 가지에서 멈추지 않습니다. GetNamedDestination 뒤의 키 탐색은 범위가 키를 배제하지 않는 모든 자식을 푸시하고, 매치를 찾거나 스택이 빌 때까지 계속 팝합니다. 범위가 서로 겹치지 않는 잘 만들어진 트리에서는 각 수준에서 범위 검사를 통과하는 자식이 많아야 하나라 추가 비용은 0입니다. 손상된 트리에서는 노드 방문 몇 번이 추가될 뿐 답은 올바르게 돌아옵니다

리프도 같은 대우를 받습니다. ISO 32000-1은 /Names 배열의 키가 바이트 값으로 정렬되기를 요구하므로 라이브러리는 먼저 이진 탐색을 시도합니다. 미스면 쌍들의 선형 스캔으로 폴백합니다. 순서가 어긋난 리프가 존재하는 키를 보이지 않게 만들지 않기 위해서입니다. 진짜 미스마다 선형 스캔 값을 지불하는 건 우리가 받아들이는 비용입니다. 실제로 없는 이름의 탐색은 드물고, 동작하는 링크에 대한 거짓 "못 찾음"은 리프 한 번 더 훑는 것보다 훨씬 비쌉니다

하나의 구조적 모순은 거부로 처리됩니다. Table 36은 노드가 /Kids나 /Names 중 하나만 달게 하고, 둘 다는 없습니다. 키 탐색은 둘 다를 달고 있는 노드를 malformed로 취급해, 작성자가 어느 쪽을 의도했는지 추측하는 대신 건너뜁니다. GetPageLabel 뒤의 걷기 같은 넘버 트리 열거는 더 관대해서 둘 다 있으면 /Kids를 따릅니다. 범위 전체를 떨어뜨리면 그 뒤의 모든 페이지가 잘못 라벨 붙습니다

읽는 쪽은 /Limits를 무엇에 대해 신뢰할 수 있을까?

읽는 쪽은 쌍이 잘 만들어졌을 때에 한해 일을 건너뛰는 용도로 /Limits를 믿을 수 있고, 키의 부재를 결론지는 데에는 절대 쓸 수 없습니다. Table 36은 중간과 리프 노드가 그것을 달라고 하지만, 실제로는 손 편집 뒤에 사라지거나, 네임 트리 안에 숫자를 담거나, 경계가 뒤바뀐 채 도착합니다. PDFlibPas는 그 모든 사례를 같은 방식으로, 자식을 검색 가능하게 유지하는 것으로 풉니다

  • 빠진 /Limits: 그런 자식을 건너뛰는 범위 검사는 작성자가 엔트리를 잊은 순간 자식의 서브트리 전체를 닿지 않게 만드므로, 자식은 검색됩니다
  • 타입이나 길이가 틀린 경우, 이를테면 네임 트리 안의 숫자나 1원소 배열: 빠진 엔트리와 정확히 같은 방식으로 처리됩니다
  • [(Z) (A)]나 [9 0] 같은 뒤집힌 경계: Lo > Hi면 Lo <= Key <= Hi를 만족하는 키가 없으므로, 쌍을 믿으면 모든 탐색에서 그 가지가 배제됩니다. 범위는 하한이 상한을 넘지 않을 때만 가지치기합니다
  • 잘 만들어진 순서 쌍: 가지를 건너뛰는 데 쓰이며, 엔트리가 존재하는 이유가 바로 그것입니다
PDFlibPas의 네임 트리 Limits 배열 신뢰 규칙: 빠졌거나 타입이 틀리거나 뒤집힌 쌍은 자식을 검색 가능하게 남기고, 잘 만들어진 순서 쌍만이 가지를 가지치기할 수 있으므로, 적대적인 Limits는 방문 비용을 부과할 수 있어도 기존 대상을 숨길 수는 없습니다
범위는 작업을 건너뛸 수 있지만 부재를 결코 판정하지 않습니다. 리프에 저장된 진짜 키가 모든 탐색의 결과를 결정합니다

호출자 쪽에서는 구별해야 할 0이 둘입니다. 이름이 정말로 없을 때 GetNamedDestination은 0을 돌려주고 그 외에는 대상 ID를 돌려줍니다. 유효한 ID에 대해 GetDestPage가 0을 돌려주는 것은 이름은 존재하지만 그 대상이 이 문서의 페이지로 해석되지 않는다는 뜻으로, 다른 버그 보고입니다. GetDestType은 XYZ를 1, Fit를 2로, FitBV까지 8로 보고합니다

uses
  PDFlibrary;

procedure LookUpDestination(const FileName, DestName: string);
var
  Lib: TPDFlib;
  DestID, Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
    begin
      WriteLn('Load failed, error ', Lib.LastErrorCode);
      Exit;
    end;
    // 카탈로그 /Dests(PDF 1.1) 먼저, 이어서 /Dests 네임 트리
    DestID := Lib.GetNamedDestination(DestName);
    if DestID = 0 then
    begin
      WriteLn('No destination named ', DestName);
      Exit;
    end;
    Page := Lib.GetDestPage(DestID);
    if Page = 0 then
      WriteLn(DestName, ' exists but does not resolve to a page')
    else
      WriteLn(DestName, ' -> page ', Page,
        ', view type ', Lib.GetDestType(DestID));  // 1 = XYZ, 2 = Fit ...
  finally
    Lib.Free;
  end;
end;

이것은 알찬 회귀 검사가 됩니다. 도입부의 두 자식 파일을 만들고 진짜 chapter7 엔트리를 /Fit 보기로 2페이지에 걸면, 프로시저는 보기 타입 2와 함께 2페이지를 인쇄해야 합니다. 첫 매치 탐색은 무는 자식이 경주에서 이기므로 "No destination"을 인쇄하고, 뒤집힌 범위를 믿는 탐색은 반대 이유로 같은 것을 인쇄합니다. 대상이 해석되면, 그것을 가리키는 아웃라인 엔트리는 Delphi에서 PDF 북마크와 주석 액션 읽기가 다룹니다

32,768개를 넘는 엔트리를 담은 리프와 포장 인덱스 함정

코드가 "리프 M의 엔트리 N"에 정수 핸들 하나가 필요할 때, 유혹적인 인코딩은 리프 위치를 Integer의 상위 16비트에, 그 리프 /Names 배열 안의 오프셋을 하위 16비트에 포장합니다. 쌍 하나는 배열 슬롯 두 개를 차지하므로, 쌍 인덱스 32,768, 즉 32,769번째 쌍은 오프셋 65,536, $10000에서 시작합니다. 그 비트가 상위 절반으로 넘어가고, 디코더는 그것을 다음 리프의 오프셋 0으로 읽어 들입니다

리프 위치와 엔트리 오프셋이 하나의 32비트 Integer를 나눠 갖는 포장된 네임 트리 인덱스: 쌍 32768은 오프셋 65536에서 시작하므로 상위 절반으로의 올림수가 다음 리프의 오프셋 0으로 읽혀 find나 delete가 엉뚱한 쌍을 건드리고, 별도의 키 스캔은 그와 엇갈립니다
하나의 32비트 정수에 담긴 두 16비트 값은 리프가 32,768쌍을 넘는 순간 조용히 잘립니다. 실제 레퍼런스 매뉴얼이 닿는 크기입니다

증상은 트리 모양에 따라 갈립니다. 단일 리프라면 다음 리프가 없어 디코딩된 핸들이 리프 목록 끝을 넘어 인덱스합니다. 여러 리프라면 find나 delete가 다음 리프의 첫 쌍에 착지하는 동안, 평범한 키 스캔은 여전히 요청된 키가 존재한다고 보고합니다. 이 크기의 파일은 희한한 게 아닙니다. 심볼마다 이름 붙은 대상 하나씩 달린 생성된 API 레퍼런스는 32,768 엔트리를 금방 넘고, 일부 작성자는 트리를 균형 잡는 대신 전부 하나의 평평한 리프에 씁니다

PDFlibPas는 리프 위치와 엔트리 오프셋을 전체 폭 정수 둘에 유지하므로, 어느 리프 크기에서도 한쪽이 다른 쪽으로 흘러넘치지 않습니다. 같은 리더는 진짜 문자열 키만 셉니다. [(Valid) 42 123 456] 같은 리프에서 EmbeddedFileCount는 1을 보고하고, 숫자 키 123은 빈 이름으로 오독되지 않으며, 0 이하 인덱스는 뒤따르는 오브젝트가 뭐든 그것을 돌려주는 대신 GetEmbeddedFileStrProperty에서 빈 문자열을 돌려줍니다. 그 함수의 태그 1이 파일 이름이고 태그 2가 MIME 서브타입입니다

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // /PageLabels 넘버 트리, 없는 파일은 평범한 페이지 번호를 돌려줌
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles 네임 트리, 인덱스는 1 기반, 문자열 아닌 키는 건너뜀
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // 이름, MIME 서브타입
    // /JavaScript 네임 트리: 패키지 이름을 나열, 아무것도 실행하지 않음
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

두 페이지짜리 테스트 파일이 기대 출력을 잘 보여 줍니다. 그 /PageLabels 루트에 리프 하나를 두 번 나열하고 루트 자신도 참조하는 /Kids 배열을 달고, 1페이지부터 소문자 로마자, 2페이지부터 접두어 A-를 붙인 10진수 범위를 주세요. 감사는 각 범위를 한 번씩 적용해 i와 A-1을 인쇄해야 합니다. 그런 트리에 페이지 레이블을 쓰는 일에는 자체 주름이 있는데 /Kids 넘버 트리에 저장된 PDF 페이지 레이블 고치기가 다룹니다. AddPageLabels는 삽입 전에 /Kids 루트를 하나의 /Nums 리프로 평탄화하며, 같은 사이클 안전 열거를 씁니다

순회가 어디에 선을 긋는가

순회는 진짜 키가 온전한 트리라면 무엇이든 종료 보장, 안정 순서, 올바른 답을 약속합니다. 손상된 트리는 쓰인 그대로 읽으며 작성자가 의도했을 무엇을 재구성하려 하지 않고, 그 선택에서 다섯 가지 귀결이 따라옵니다

  • 노드를 정의하는 것은 신원이지 내용이 아닙니다. 같은 엔트리를 담은 서로 다른 딕셔너리 둘은 노드 둘이며, 리프를 참조 대신 복제한 작성자는 그 엔트리들을 두 번 얻습니다
  • 잘 만들어진 순서 /Limits 쌍은 틀렸어도 가지치기합니다. [(a) (m)]이 (q)를 간직한 리프 위에 그럴듯하게 거짓말하면 q는 숨겨집니다. 유일한 방어는 /Limits를 어디서든 무시하고 모든 리프를 스캔하는 것인데, 수만 엔트리의 대상 트리에서는 엔트리가 존재하는 이유를 버리는 일입니다. 우리는 가지치기를 유지합니다
  • 열거는 파일 순서를 지킵니다. GetPageLabel은 열거된 모든 범위를 걷고 시작 인덱스가 페이지 이하인 마지막 범위를 적용하므로, 범위를 순서 어긋나게 쓴 작성자에게는 파일 순서 의미론이 적용되고 걷기를 뒤집으면 200페이지가 머리말 스타일을 받습니다
  • 메모리는 서로 다른 노드와 엔트리에 비례해 자랍니다. 순회는 파싱된 오브젝트 위에 리스트 하나와 해시 집합 하나를 얹습니다
  • 한 리프 안의 중복 키는 결정적으로 해석됩니다. 이진 탐색은 처음 착지한 매치 쌍을 돌려주고, 선형 폴백은 스캔하는 마지막 매치를 지킵니다

프리플라이트 도구, 아카이버, 문서 뷰어는 단 한 페이지가 렌더링되기 전에 이 트리들을 읽으므로, 업로드 큐에 도착하는 무엇이든 일단 맞서야 하는 첫 줄에 섭니다. 여기서 설명한 트리 리더들은 Delphi용 PDF Library인 PDFlibPas에 실려 나가며, Delphi와 Free Pascal 모두로 빌드됩니다