技術文章

PDFlibPas 名稱樹走訪:環、/Limits 與巨型葉節點

造一份 /Dests 名稱樹的 PDF:根節點有兩個子節點,第一個子節點宣告 /Limits [(a) (z)]、/Kids 陣列卻直接指回根節點;第二個子節點持有 (chapter7) 的真正條目,limits 卻寫反了:[(z) (a)]。拿教科書式的名稱樹查找問 chapter7,它要嘛遞迴到堆疊耗盡,要嘛對一個檢視器明明跳得過去的目的地回報「找不到」。整份檔案約兩 KB,每個物件都解析得乾乾淨淨

這份檔案把三個獨立的陷阱裝進一個結構:/Kids 環、宣稱持有自己沒有的鍵的範圍、以及永遠匹配不到東西的範圍。第四個陷阱需要大得多的檔案:一旦單一葉子帶著超過 32,768 個名稱/值對,任何把「哪片葉子」與「哪個條目」塞進一個 32 位元整數的程式碼,都會開始指到錯的對。本文接下來逐個走過這些陷阱、讀取端該怎麼應對,以及在這種檔案上 Delphi 呼叫的行為

坐在名稱樹與數字樹上的四個 PDF 功能

名稱樹與數字樹撐起 PDF 裡每個「把大量鍵集映射到物件」的功能,PDFlibPas(losLab 的 Delphi PDF Library)透過公開的 TPDFlib 方法暴露其中四個。ISO 32000-1 §7.9.6 定義名稱樹(字串鍵、Table 36)、§7.9.7 定義數字樹(整數鍵、Table 37)。根節點與中間節點帶 /Kids;葉子帶按序排好的鍵值對於 /Names 或 /Nums;每個非根節點按規範都該帶一個兩元素的 /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 列出

這些結構全部來自檔案本身。規範告訴寫入端該產出什麼,讀取端收到的仍是寫入端、壞掉的增量儲存或 fuzzer 實際放進去的東西。這跟強化 Pascal PDF 解析器以對抗惡意檔案是同一課,只是這次用在樹形狀上、而不是緩衝區長度上

環狀 /Kids 陣列為什麼會讓遞迴樹走訪器崩潰?

遞迴走訪器碰上環狀 /Kids 陣列會崩潰,因為遞迴裡沒有任何東西記得自己進過哪些節點,一個指回祖先的子節點參照就把有限檔案變成無限下探。合法的樹不需要環也能造成同樣傷害:4,096 層的單子節點鏈是完全合法的語法,卻要遞迴讀取器付出 4,096 個堆疊框架

溫和的變體根本不崩潰。兩個 /Kids 條目參照同一片葉子時,天真的列舉會造訪它兩次:附件計數比文件裡的檔案數多,腳本清單把同一個套件列兩遍

PDFlibPas 走訪兩種樹,靠堆積上的明確後進先出堆疊,外加一個以字典身分為鍵的已造訪集合。節點在彈出時標記。環狀參照可以在堆疊上待一會兒,但它一冒上來就被丟棄,每個不同的節點恰好展開一次子節點。總工作量以不同字典的數量加上它們 /Kids 陣列的總長度為上界;4,096 層的鏈就是 4,096 次迴圈迭代加 4,096 個雜湊集合條目

PDFlibPas 的名稱樹走訪示意圖:指回根節點的 Kid 陣列曾讓遞迴走訪器死於堆疊溢位,v3.539.45 起改用明確堆疊加已造訪集合——彈出時標記節點、由右至左推入子節點,並讓葉子保持檔案順序供 GetPageLabel 使用
遞迴變成迴圈之後,深度就不再要緊:4,096 層的鏈只是 4,096 次迭代加 4,096 個雜湊集合條目

把遞迴改寫成迴圈時,人們搞錯的往往是順序。堆疊會反轉您餵進去的東西,所以子節點必須從最後一個索引往下推到第一個;最左邊的子節點才會先彈出,葉子按寫入端寫下的由左至右順序出來。在彈出時而非推入時標記,道理相同:若在推入時標記又由右至左推,被位置 0 與位置 2 共用的葉子會被位置 2 認領,它的條目就出現在檔案所說的順序之後。頁面標籤依賴這個順序,最後一節會講到

若您對著別的物件模型寫自己的樹程式碼,這是我們推薦的形狀。下面的節點型別刻意保持抽象,兩個函式都是讀取端程式碼、不是程式庫呼叫

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // empty on a leaf
    Keys: TArray<string>;      // leaf keys, sorted by a well-behaved producer
    Values: TArray<Integer>;   // parallel to 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 背後的按鍵查找,把範圍沒有排除該鍵的每個子節點都推入堆疊,一直彈到找到匹配或堆疊見底。範圍互斥的格式完好樹上,每層至多一個子節點過得了範圍檢查,額外成本是零;受損的樹上,多付的是幾次節點造訪,而答案是對的

葉子得到同樣待遇。ISO 32000-1 要求 /Names 陣列的鍵按位元組值排序,程式庫先試二分搜尋;二分不中,後備到逐對線性掃描——否則亂序的葉子會讓存在的鍵隱形。每次真實的未命中都付一次線性掃描,這個成本我們接受:確實不存在的名稱查找很少見,而把一條活著的連結誤報「找不到」,代價遠高於多掃一遍葉子

有一種結構矛盾用拒收處理。Table 36 允許節點帶 /Kids 或 /Names,絕不同時帶兩者。按鍵查找把同時帶兩者的節點視為畸形、直接跳過,不去猜寫入端想表達哪一半。數字樹的列舉——例如 GetPageLabel 背後的走訪——更寬容,兩者都在時跟著 /Kids 走,因為丟掉一整個範圍會讓之後每一頁標錯

讀取端可以拿 /Limits 信什麼?

讀取端可以信 /Limits 來省掉工作——而且只在配對格式完好時;它絕不能拿這個條目斷定鍵不存在。Table 36 說中間與葉子節點都該帶它,實務上這個條目會在手工編輯後消失、在名稱樹裡裝著數字、或邊界寫反。PDFlibPas 對每一種情況都用同一招收尾:讓子節點保持可搜尋

  • 缺 /Limits:跳過這種子節點的範圍檢查,會在寫入端忘記寫條目時讓整棵子樹到不了,所以照搜
  • 型別錯或長度錯,例如名稱樹裡裝數字、或只有一個元素的陣列:照缺條目處理
  • 邊界反向,如 [(Z) (A)] 或 [9 0]:Lo > Hi 時沒有任何鍵滿足 Lo <= Key <= Hi,信了這個配對會讓每個查找都排除這個分支;範圍只有在下界不大於上界時才准修剪
  • 格式完好且有序:用來跳過分支——這正是這個條目存在的目的
PDFlibPas 對名稱樹 Limits 陣列的信任規則示意圖:缺失、型別錯誤或反向的對,自 v3.539.45 與 v3.539.51 起都讓子節點保持可搜尋,只有格式完好的有序對才能修剪分支,惡意的 Limits 因此頂多多花幾次造訪,再也藏不住一個存在的目的地
範圍可以用來省事,但絕不能裁決「不存在」,因為每次查找的結果都由葉子裡真正的鍵決定

從呼叫端看,有兩個 0 要分清楚。GetNamedDestination 在名稱確實不存在時回傳 0,否則回傳目的地 ID。GetDestPage 對有效的 ID 回傳 0,意思是名稱存在、但它的目標解析不到這份文件裡的頁——那是另一種 bug 報告。GetDestType 回報檢視方式:1 是 XYZ、2 是 Fit,依此到 8 的 FitBV

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 條目指向第 2 頁、配 /Fit 檢視,程序應該印出第 2 頁、檢視型別 2。首個匹配就停的查找會印「No destination」,因為繞環的子節點搶先贏了;相信反向範圍的查找基於相反的理由印出同一句。目的地能解析之後,指向它們的大綱條目見 在 Delphi 中讀取 PDF 書籤與註釋動作一文

超過 32,768 條目的葉子與打包索引陷阱

當程式碼需要一個整數 handle 表示「葉子 M 裡的第 N 條」,誘人的編碼是把葉子位置塞進 Integer 的高 16 位、該葉 /Names 陣列內的偏移塞進低 16 位。每一對占兩個陣列槽位,於是第 32,768 對從偏移 65,536——也就是 $10000——開始。這個位元進位到高半部,解碼端把它讀成下一片葉子的偏移 0

打包的名稱樹索引示意圖:葉子位置與條目偏移共用一個 32 位元 Integer,第 32768 對起始於偏移 65536,進位到高半部後被讀成下一片葉子的偏移 0,查找或刪除因此碰到錯的鍵值對,純掃描卻照樣回報鍵存在
一個 32 位元整數裝兩個 16 位元值,葉子一過 32,768 對就悄悄截斷——真實的參考手冊達得到這個量級

症狀取決於樹形。單一葉子時沒有下一片葉子,解碼出的 handle 直接越過葉子清單結尾;多片葉子時,查找或刪除落在下一片葉子的第一對上,純鍵掃描卻仍回報請求的鍵存在。這種大小的檔案並不罕見:每個符號一個具名目的地的自動生成 API 手冊,很快越過 32,768 條目,而有些寫入端把它們全部塞進單一扁平葉子、不平衡樹

PDFlibPas 把葉子位置與條目偏移放在兩個全寬整數裡,任何葉子大小下都互不溢漏。同一個讀取端只數真正的字串鍵:對 [(Valid) 42 123 456] 這種葉子,EmbeddedFileCount 回報 1,數字鍵 123 不會被誤當空名稱,索引 0 或以下時 GetEmbeddedFileStrProperty 回傳空字串、而不是碰巧排在後面的什麼物件。該函式 tag 1 是檔名、tag 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 number tree; files without one return plain page numbers
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name tree; indexes are 1-based, non-string keys skipped
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // 名稱、MIME 子類型
    // /JavaScript name tree: list package names, execute nothing
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

兩頁的測試檔案能把預期輸出展示得很清楚。讓它的 /PageLabels 根節點的 /Kids 陣列把一片葉子列兩次、還參照根節點自己,範圍是第 1 頁起的小寫羅馬數字與第 2 頁起帶前綴 A- 的十進位。稽核應該印出 i 與 A-1,每個範圍只套用一次。把頁面標籤寫進這種樹另有皺褶,見 修正存於 /Kids 數字樹的 PDF 頁面標籤一文;AddPageLabels 插入前會把 /Kids 根節點攤平成單一 /Nums 葉子,用的正是同一套環安全列舉

走訪在哪裡畫下界線

對真實鍵完好的任何樹,走訪保證終止、順序穩定、答案正確。它按檔案原樣讀受損的樹,不去重構作者本來想表達什麼,而這個選擇帶來五個後果

  • 定義節點的是身分、不是內容。兩個條目完全相同的字典是兩個節點,所以複製葉子而非參照葉子的寫入端,會讓那些條目出現兩次
  • 格式完好且有序的 /Limits 配對,錯了也照樣修剪。一個謊得像樣的範圍——例如對還持有 (q) 的葉子寫 [(a) (m)]——會把 q 藏起來。唯一的防禦是到處無視 /Limits、每片葉子都掃,而在有數萬條目的目的地樹上,這等於扔掉這個條目存在的理由。我們保留修剪
  • 列舉保持檔案順序。GetPageLabel 走過每個列舉到的範圍、套用起始索引不大於頁碼的最後一個,所以範圍寫亂序的寫入端得到的是檔案順序語意;反向走訪會把前言樣式發給第 200 頁
  • 記憶體隨不同節點與條目增長。走訪在已解析物件之上只多加一個清單與一個雜湊集合
  • 同一葉子裡的重複鍵確定性地解析:二分搜尋回傳它第一個落點的匹配對,線性後備留下它掃到的最後一個匹配

預檢工具、歸檔器與文件檢視器在渲染任何一頁之前就讀這些樹,上傳佇列裡進來的任何東西都輪不到別人先碰。這裡描述的樹讀取端隨 PDFlibPas(Delphi PDF Library)出貨,Delphi 與 Free Pascal 都能建置