技術記事

PDFlibPasネームツリー:サイクル、不正なLimits、巨大なリーフ

/Destsネームツリーのルートに2つの子を持つPDFを組み立ててみます。最初の子は/Limits [(a) (z)]を宣言し、その/Kids配列はルートへ真っすぐ突き返します。2つ目の子は(chapter7)の本当のエントリーを保持しますが、そのlimitsは逆に書かれています。[(z) (a)]です。教科書通りのネームツリー参照にchapter7を問い合わせると、スタックを使い果たすまで再帰するか、ビューアーなら跳べるはずの宛先に対して「見つからない」を返します。ファイル全体は2キロバイト程度に収まり、中のオブジェクトはどれもきれいに解析されます

このファイルは3つの独立した罠を1つの構造に詰め込んでいます。子を参照する/Kidsの循環、持っていない鍵を要求するレンジ、そして何とも一致し得ないレンジです。4つ目の罠にはずっと大きなファイルが要ります。1つのリーフが32,768組の名前/値ペアを超えて運ぶと、「どのリーフか」と「どのエントリーか」を1つの32ビット整数に詰め込むコードは間違ったペアを指し始めます。この記事の残りは、各罠の中身、リーダーがどう対処すべきか、そしてこういう作りのファイルでDelphiの呼び出しがどう振る舞うかを順に見ていきます

ネームツリーとナンバーツリーの上に座る4つのPDF機能

ネームツリーとナンバーツリーは、大きな鍵の集合をオブジェクトへ写すすべてのPDF機能を支えており、PDFlibPas、losLabのDelphi向けPDF Libraryは、そのうち4つを公開された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

2行には小さな折りたたみが隠れています。名前付き宛先は古いPDF 1.1の形式でも存在します。カタログの名前オブジェクトを鍵にした素の/Dests辞書で、GetNamedDestinationはまずその辞書を確認し、それからPDF 1.2のネームツリーを降ります。JavaScriptの行には全然別のものを読む同名の似非物がいます。GetDocJavaScriptはカタログの/AA辞書のドキュメントトリガー(WS、DS、WP、DP、DC)に付いたスクリプトを返し、ドキュメントを開くときに走る名前付きパッケージは/JavaScriptネームツリーに住み、GlobalJavaScriptPackageNameが一覧します

これらの構造はすべてファイルから来ます。仕様は書き手が生産すべきものを語り、リーダーはそれでも、書き手と、壊れたインクリメンタルセーブと、ファザーが実際に置いたものを受け取ります。悪意あるファイルに対してPascalのPDFパーサを強化する記事と同じ教訓の、バッファ長ではなくツリーの形状への適用です

循環する/Kids配列がなぜ再帰ツリーウォーカーをクラッシュさせるのか

再帰的ウォーカーが循環する/Kids配列でクラッシュするのは、再帰の中の何も、どのノードに既に入ったかを覚えていないからです。祖先への1つの子参照が有限のファイルを終わりのない下降に変えます。循環なしでも正統なツリーは同じ被害を与えられます。1つの子だけを持つノードの4,096レベルの連鎖は妥当な構文であり、再帰するリーダーに4,096個のスタックフレームを要求します

穏やかな変種はまったくクラッシュしません。2つの/Kidsエントリーが同じリーフを参照すると、素朴な列挙はそれを2回訪れ、添付ファイル数はドキュメント内のファイル数より多く返り、スクリプトリストは同じパッケージを2回見せます

PDFlibPasは両方のツリーを、ヒープ上の明示的な後入れ先出しスタックと、辞書のアイデンティティを鍵にしたvisited集合で歩きます。ノードはpopされるときに印を付けられます。循環参照は一瞬スタックの上に座れますが、戻ってきた瞬間に捨てられ、それぞれの異なるノードは子を正確に1回だけ展開します。総仕事量は異なる辞書の数とそれらの/Kids配列の合計長で抑えられ、4,096レベルの連鎖は4,096回のループ反復と4,096個のハッシュ集合エントリーになります

PDFlibPasのネームツリー走査を示す図。ルートへ戻るKids配列は再帰的ウォーカーのスタックを溢れさせるため、PDFlibPasは明示スタックとpop時にノードを印付けるvisited集合を使い、子を右から左へpushし、GetPageLabelのためにリーフをファイル順に保持します
再帰がループになると深さは問題でなくなります。4,096レベルの連鎖は4,096回の反復と4,096個のハッシュ集合エントリーにすぎません

順序は、再帰をループへ変換するときに人が間違える部分です。スタックは入れたものを逆にして出すので、子は最後のインデックスから最初へ向かってpushしなければなりません。そうして初めて、最も左の子が最初にpopされ、リーフは生産者が書いた左から右の順で出てきます。push時ではなくpop時に印を付けるのも同じ理由です。push時に印を付け右から左へpushすると、位置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;

// 自作の参照:明示スタック、visited集合、pop時に印付け
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
        // 右から左へpushし、最も左の子が最初にpopされるように
        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;
      // このリーフでのミス:兄弟をpopし続ける
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

1つの枝でのミスはツリーについて何も語らない

最もよくある参照の近道は、/Limitsが鍵をカバーする最初の子を選び、その中へ降りて、兄弟を2度と見ません。きれいなツリーでは正しく速いです。冒頭のファイルでは失敗します。最初の子はchapter7を請求し、ルートへ返り、次の兄弟がエントリーを保持しているのに探索は手ぶらで終わります

PDFlibPasは最初のそれらしい枝で止まりません。GetNamedDestinationの背後にある鍵付き参照は、レンジが鍵を排除しないすべての子をpushし、一致を見つけるかスタックが空になるまでpopし続けます。レンジが重複しない整形式ツリーでは、各レベルでレンジ検査を生き延びる子は高々1つなので、追加コストはゼロです。壊れたツリーでは追加のノード訪問が数回あり、答えは正しく返ります

リーフも同じ扱いです。ISO 32000-1は/Names配列の鍵がバイト値でソートされていることを要求するので、ライブラリはまず二分探索を試します。外れたときはペアの線形走査へフォールバックします。順序が乱れたリーフがあると、存在する鍵が見えなくなってしまうからです。本物のミスのたびに線形走査の代金を払うのは、受け入れたコストです。本当に存在しない名前の参照は希で、動いているリンクに対する誤った「見つからない」は、リーフの1回の追加分の走査よりずっと高くつきます

1つの構造的矛盾は拒否で扱います。Table 36はノードに/Kidsか/Namesのどちらか一方だけを許し、両方を許しません。鍵付き参照は両方を運ぶノードを不正として扱い、生産者がどちらを意図したか当て推量する代わりにスキップします。ナンバーツリーの列挙、たとえばGetPageLabelの背後の歩きは、より寛容で、両方あるときは/Kidsに従います。レンジ全体を落とすとその後のすべてのページのラベルが狂うからです

リーダーが/Limitsを信じていいこととは

リーダーは/Limitsを仕事を省くために信じてよく、それはペアが整形式のときに限ります。鍵が存在しないと結論するのに使ってはいけません。Table 36は中間ノードとリーフノードがそれを運ぶshallと言いますが、実地では手編集の後に消え、ネームツリーの中で数字を保持し、境界を入れ替えた状態で届きます。PDFlibPasはそのすべてのケースを同じやり方で、子を探索可能に保つことで解決します

  • /Limitsがない:そのような子をスキップするレンジ検査は、生産者がエントリーを忘れた瞬間に子の部分木全体を到達不能にするので、子は探索されます
  • 型違いや長さ違い、ネームツリーの中の数字や1要素配列:欠けたエントリーとまったく同じに扱われます
  • [(Z) (A)]や[9 0]のような逆転した境界:Lo > HiのときLo <= Key <= Hiを満たす鍵はなく、ペアを信じるとすべての参照でその枝が排除されます。レンジが枝を刈れるのは下限が上限を超えないときだけです
  • 整形式で順序付き:枝をスキップするために使われます。エントリーが存在する目的はこれです
ネームツリーのLimits配列を信じるPDFlibPasの規則を示す図。欠けた、型違いの、逆転したペアは子を探索可能なまま残し、整形式で順序付きのペアだけが枝を刈れるため、敵意あるLimitsは訪問のコストを課せても、既存の宛先を隠せません
レンジは仕事を省けますが、不在を決めることは決してありません。リーフに保存された本当の鍵がすべての参照の結果を決めるからです

呼び出し側からは、区別すべき2つのゼロがあります。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;

これは手頃な回帰検査になります。冒頭の2子ファイルを組み立て、本当のchapter7エントリーを/Fitビュー付きでページ2に向けると、この手続きはページ2とビュータイプ2を印字するはずです。最初の一致で止まる参照は「宛先なし」を印字します。循環する子が競争に勝つからです。逆転レンジを信じる参照は、反対の理由で同じものを印字します。宛先が解決できるようになったら、それらを指すアウトラインエントリーはDelphiでPDFのブックマークと注釈アクションを読むで扱います

32,768エントリーを超えるリーフとパック済みインデックスの罠

コードが「リーフMのエントリーN」に1つの整数ハンドルを要するとき、魅力的なエンコードはリーフ位置をIntegerの上位16ビットへ、そのリーフの/Names配列内のオフセットを下位16ビットへ詰めます。各ペアは配列スロットを2つ取ります。ペアインデックス32,768、つまり32,769番目のペアはオフセット65,536、$10000から始まります。そのビットが上半分へ繰り上がり、デコーダはそれを次のリーフのオフセット0として読み戻します

リーフ位置とエントリーオフセットが1つの32ビットIntegerを共有するパック済みネームツリーインデックスを示す図。ペア32768はオフセット65536から始まり、上半分への繰り上がりが次のリーフのオフセット0として読まれ、findやdeleteは間違ったペアに触れ、別の鍵走査とは食い違います
1つの32ビット整数に詰め込まれた2つの16ビット値は、リーフが32,768ペアを越えた瞬間に黙って切り詰められます。現実のリファレンスマニュアルが届くサイズです

症状はツリーの形状で変わります。リーフが1つだけなら次のリーフはなく、デコードされたハンドルはリーフリストの終端の先をインデックスします。リーフが複数なら、findやdeleteは次のリーフの最初のペアに着地し、素の鍵走査は要求された鍵がまだ存在すると報告します。このサイズのファイルは珍品ではありません。シンボルごとに1つの名前付き宛先を持つ生成済みAPIリファレンスはすぐ32,768エントリーを越え、いくつかの生産者はツリーをバランスさせず、その全部を1つのフラットなリーフへ書き込みます

PDFlibPasはリーフ位置とエントリーオフセットを2つのフル幅整数で保持するので、どのリーフサイズでも互いに溢れません。同じリーダーは本物の文字列鍵だけを数えます。[(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;

2ページのテストファイルが期待出力をよく示します。その/PageLabelsルートに、1つのリーフを2回列挙しルート自身も参照する/Kids配列を与え、レンジはページ1から小文字ローマ数字、ページ2から接頭辞A-付きのアラビア数字とします。監査はiとA-1を印字するはずで、各レンジは1回だけ適用されます。こういうツリーへのページラベル書き込みには独自の綾があり、/Kidsナンバーツリーに保存されたPDFページラベルを直すで扱います。AddPageLabelsは挿入前に/Kidsルートを単一の/Numsリーフへフラット化し、同じ循環安全な列挙を使います

走査が線を引く場所

走査は、本当の鍵が無事なあらゆるツリーに対して停止、安定した順序、正しい答えを保証します。壊れたツリーは書かれた通りに読み、著者が意図したものを再構築しようとしません。この選択から5つの帰結が従います

  • ノードを定義するのはアイデンティティであって内容ではありません。同一のエントリーを持つ2つの別の辞書は2つのノードであり、リーフを参照でなくコピーする生産者はそのエントリーを2回手に入れます
  • 整形式で順序付きの/Limitsペアは、間違っていても枝を刈ります。もっともらしく嘘をつくレンジ、たとえば(q)も保持するリーフの上の[(a) (m)]はqを隠します。唯一の防御は/Limitsをどこでも無視してすべてのリーフを走査することですが、数万エントリーの宛先ツリーでは、エントリーが存在する理由を捨てることになります。私たちは刈り続けます
  • 列挙はファイル順を保持します。GetPageLabelは列挙されたすべてのレンジを歩き、開始インデックスがページ以下の最後のレンジを適用するので、レンジを順序無視で書く生産者はファイル順の意味論を受け取り、歩きを逆にするとページ200に前付けのスタイルが渡ります
  • メモリーは異なるノードとエントリーに比例して増えます。走査は解析済みオブジェクトの上に1つのリストと1つのハッシュ集合を足すだけです
  • 1つのリーフ内の重複鍵は決定論的に解決されます。二分探索は着地した最初の一致ペアを返し、線形フォールバックは走査した最後の一致を保持します

プリフライトツール、アーカイバー、ドキュメントビューアーは、1ページがレンダリングされる前にこれらのツリーを読むので、アップロードキューに届く何ものかに最初に立たされます。ここで述べたツリーリーダーはPDFlibPas、Delphi向けPDF Libraryとともに出荷され、DelphiとFree Pascalの両方でビルドできます