Деревья имён в PDFlibPas: циклы, Limits и огромные листья

PDFlibPas, PDF-библиотека losLab для Delphi, обходит деревья имён и числовые деревья PDF с явным стеком и множеством посещённых узлов начиная с v3.539.45, так что циклические /Kids, общие потомки и деревья в тысячи уровней больше не выжигают стек вызовов и не дублируют записи. С v3.539.51 отсутствующая, испорченная или перевёрнутая пара /Limits уже никогда не прячет ветку, в которой лежит ключ. Именованные назначения, метки страниц, вложения и JavaScript уровня документа всё читается через эти два кодовых пути, что делает их частью поверхности атаки любого PDF, который вы не производили сами

Триггер редко бывает экзотикой. Фаззер, враждебная загрузка или багованный инкрементальный save пишут запись /Kids, указывающую обратно на предка, и рекурсивный обходчик умирает от переполнения стека на файле в два килобайта. Более тихий отказ — поиск, доверяющий битому массиву /Limits и отчитывающий «не найдено» для назначения, которое явно на месте

Где в PDF всплывают деревья имён и числовые деревья?

Деревья имён и числовые деревья всплывают всюду, где PDF мапит большое множество ключей на объекты, и PDFlibPas читает как минимум четыре из них через публичные API. ISO 32000-1 §7.9.6 определяет дерево имён (строковые ключи, Table 36), а §7.9.7 — числовое дерево (целые ключи, Table 37). Оба — почти сбалансированные деревья, чьи корень и промежуточные узлы несут /Kids, чьи листья несут отсортированные пары ключ/значение в /Names или /Nums, и чьи некорневые узлы несут двухэлементный массив /Limits с наименьшим и наибольшим ключом под ними

Дерево	Где живёт	Спецификация	API чтения в PDFlibPas
Именованные назначения	/Dests в словаре имён	§12.3.2.3	GetNamedDestination, затем GetDestPage / GetDestType
Метки страниц	/PageLabels в каталоге (числовое дерево)	§12.4.2	GetPageLabel
Вложения	/EmbeddedFiles в словаре имён	§7.7.4, §7.11.4	EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript уровня документа	/JavaScript в словаре имён	§7.7.4	GlobalJavaScriptCount, GlobalJavaScriptPackageName

Две детали в этой таблице легко упустить. У именованных назначений есть и старая форма из PDF 1.1 — обычный словарь /Dests в каталоге с ключами-именными объектами, — и GetNamedDestination сперва проверяет этот словарь, прежде чем спускаться в дерево имён PDF 1.2. А GetDocJavaScript вообще не читатель дерева имён: он возвращает скрипты, привязанные к триггерам документа в словаре /AA каталога (WS, DS, WP, DP, DC), тогда как именованные пакеты скриптов, запускаемые при открытии документа, живут в дереве имён /JavaScript

Каждый байт этих структур приходит из файла. Спецификация говорит, что писатель обязан выдать; она не может помешать читателю получить нечто иное — тот же урок, что стоит за упрочнением Pascal-парсера PDF против злонамеренных файлов, применённый здесь к форме дерева, а не к размерам буферов

Почему циклический массив /Kids валит рекурсивный обходчик?

Циклический массив /Kids валит рекурсивный обходчик, потому что ничто в рекурсии не замечает, что узел уже встречался, так что потомок, ссылающийся на собственного предка, превращает конечный файл в бесконечное погружение. До v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree и внутренний TPDFNameTree.ProcessNode звали себя по разу на каждого потомка. Одиночной самоссылки было достаточно, чтобы убить процесс, а легитимное, но очень глубокое дерево могло сделать то же безо всякого цикла

Более мягкий вариант портит результаты вместо падения. Когда две записи /Kids ссылаются на один лист, наивное перечисление посещает его дважды, и счётчик вложений или список пакетов скриптов отчитывает несуществующие записи

Правка заменяет рекурсию явным стеком LIFO на куче и множеством посещённых узлов, ключом в котором служит идентичность словаря. Узел помечается, когда с него снимают, а не когда кладут, поэтому циклическая ссылка может недолго побыть в стеке, но отбрасывается в момент возвращения. Каждый различный узел раскрывает своих потомков ровно один раз, что ограничивает суммарную работу числом различных словарей плюс суммарной длиной их массивов /Kids. Глубина перестаёт иметь значение: цепочка в 4 096 уровней — это 4 096 итераций цикла и 4 096 записей в хэш-множестве

Порядок, впрочем, всё ещё важен, и стек нужно кормить задом наперёд, чтобы его сохранить. Потомки кладутся от последнего индекса к первому, так что левейший снимается первым и листья выходят в том же порядке слева направо, в каком их записал продюсер. На этом держится GetPageLabel: он проходит все перечисленные диапазоны и применяет последний, чей стартовый индекс не выше страницы, так что разворот перечисления молча выдал бы странице 200 стиль фронт-материи. Скелет ниже показывает паттерн на абстрактном типе узла, независимо от какой бы то ни было PDF-объектной модели

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 в настоящем файле могут перекрываться или лгать, и ветка, претендующая на ключ, — не обязательно ветка, его держащая. Поиски до v3.539.45 ставили флаг Found на первом потомке, чьи /Limits покрывали ключ, спускались в него и больше не смотрели на других соседей. Если тот потомок оказывался пустым, протухшим или циклом на корень, ответом был nil — даже когда самый следующий сосед держал ключ

Переписанный FindTreeValue, который теперь стоит за обоими NameTreeLookup и NumTreeLookup, кладёт каждого потомка, чей диапазон не исключает ключ, и продолжает снимать, пока не найдёт совпадение или не опустошит стек. Промах внутри одного листа — просто промах внутри одного листа. В корректном дереве это не стоит ничего лишнего; в битом стоит нескольких лишних посещений узлов и возвращает правильный ответ

Поиск в листе следует той же философии. ISO 32000-1 требует, чтобы ключи в массиве /Names были отсортированы по байтовому значению, поэтому лист сперва ищется бинарным поиском. Если это не сработало, PDFlibPas откатывается к линейному проходу по парам, ведь лист с нарушенным порядком иначе сделал бы присутствующий ключ невидимым. Сортировка — быстрый путь, а не фильтр

Поиск к тому же отказывается гадать на одном структурном противоречии. Table 36 разрешает узлу нести либо /Kids, либо /Names, никогда оба, и путь поиска трактует узел с обоими как испорченный и пропускает его, а не выбирает одну из трактовок. Пути перечисления вроде EnumNumTree снисходительнее и при наличии обоих идут за /Kids

На что читателю можно полагаться с /Limits?

Полагаться на /Limits можно лишь чтобы пропускать работу, никогда — чтобы решить, что ключ отсутствует, и только когда пара корректна. Table 36 говорит, что промежуточные и листовые узлы обязаны нести /Limits как двухэлементный массив наименьшего и наибольшего ключей, но на практике запись пропадает после ручных правок, держит числа в дереве имён или приезжает с перепутанными границами. PDFlibPas v3.539.45 и v3.539.51 разрешают каждый случай одинаково: если диапазон не читается как упорядоченная пара нужного типа, потомок остаётся searchable

• Отсутствующие /Limits: старая проверка диапазона возвращала False, и потомок отбрасывался целиком, так что продюсер, забывший запись, делал недостижимым всё своё поддерево. С v3.539.45 потомок ищется
• Неверный тип или неверная длина — числа в дереве имён или одноэлементный массив: обрабатывается в точности как отсутствующая запись с v3.539.45
• Перевёрнутые границы вроде [(Z) (A)] или [9 0]: v3.539.45 всё ещё их использовал, а ключ не может удовлетворять Lo <= Key <= Hi при Lo > Hi, так что ветка отсекалась для любого поиска. С v3.539.51 диапазон используется для отсечения, только когда нижняя граница не превышает верхнюю
• Корректная, упорядоченная и верная: используется, чтобы отсечь ветку, — в этом весь смысл записи

Исход во всех случаях решают настоящие ключи. Враждебный /Limits может заставить PDFlibPas посетить больше узлов, чем нужно, но испорченный больше не может заставить существующее назначение исчезнуть. Со стороны вызывающего ничего не меняется: GetNamedDestination возвращает 0, когда имени действительно нет, и ID назначения в противном случае, а дальше эстафету принимают функции назначения

uses
  PDFlibrary;

procedure LookUpDestination(const FileName, DestName: string);
var
  Lib: TPDFlib;
  DestID: 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
      WriteLn('No destination named ', DestName)
    else if Lib.GetDestPage(DestID) = 0 then
      WriteLn(DestName, ' exists but does not resolve to a page')
    else
      WriteLn(DestName, ' -> page ', Lib.GetDestPage(DestID),
        ', view type ', Lib.GetDestType(DestID));  // 1 = XYZ, 2 = Fit ...
  finally
    Lib.Free;
  end;
end;

Запущенный на самодельном файле, чей корень /Dests держит одного потомка, зацикленного на корень под диапазоном [(a) (z)], и второго потомка с настоящей записью под перевёрнутыми границами [(z) (a)], этот процесс разрешает назначение на страницу 2 с типом просмотра 2 (Fit). До v3.539.45 тот же поиск возвращал 0, потому что зацикленный потомок первым претендовал на ключ, и поиск никогда не добирался до соседа; один v3.539.45 всё ещё возвращал 0, потому что перевёрнутый диапазон отсекал настоящий лист. Если затем читать закладки, указывающие на эти назначения, сторону actions разбирает статья о чтении действий закладок и аннотаций PDF на Delphi

Как лист с 32 769 именами сломал TPDFNameTree?

Лист с 32 769 парами имя/значение ломал TPDFNameTree, потому что его внутренний FindIndex упаковывал два числа в один 32-битный Integer: позицию листа во внутреннем списке массивов — в старших 16 битах, а смещение записи внутри массива /Names этого листа — в младших 16. Каждая пара занимает два слота массива, так что 32 769-я пара, с индексом 32 768, стартует со смещения 65 536, то есть $10000. Это значение переносится в старшую половину, и декодер читал его обратно как смещение 0 в следующем листе

TPDFNameTree — класс за вложениями, глобальными пакетами JavaScript и записями именованных назначений, что делает последствия осязаемыми. В дереве с одним листом следующего листа нет, поэтому FindKey и DeleteKey индексировали за концом списка листов; в дереве с несколькими листьями они возвращали или удаляли первую пару следующего листа вместо запрошенной. Тем временем HasKey гонял собственный скан и отчитывал ключ присутствующим, так что класс противоречил сам себе. Сгенерированное справочное руководство с одним именованным назначением на API-символ переваливает за 32 768 записей не напрягаясь, а некоторые продюсеры пишут их все в один плоский лист

С v3.539.45 FindIndex возвращает индекс массива через отдельный out-параметр, а полное смещение записи — как результат, так что ни одно из значений не усекается. Тот же релиз подтянул двух соседей. KeyName теперь считает и возвращает только настоящие строковые ключи и возвращает пустую строку для индекса 0 и ниже, где раньше кастовал любой объект, следовавший за неверным ключом. HasKey больше не трактует числовой или иной неверный ключ как пустое имя. Для листа вроде [(Valid) 42 123 456] HasKey('') теперь False, а KeyName(2) возвращает пустую строку

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; индексы с единицы, нестроковые ключи пропускаются
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // имя, MIME type
    // Дерево имён /JavaScript: перечисляем имена пакетов, ничего не выполняем
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

На том же самодельном файле, чей корень /PageLabels перечисляет один лист дважды и ссылается сам на себя, этот аудит печатает i и A-1 для двух страниц, каждый диапазон по разу, и единственный пакет скриптов из дерева /JavaScript, которое тоже указывает на собственный корень. У записи меток страниц своя история с корнями из /Kids, разобранная в статье о починке меток страниц PDF, хранящихся в числовых деревьях /Kids; AddPageLabels сплющивает такой корень перед вставкой и опирается на то же перечисление EnumNumTree, описанное здесь

Чего это упрочнение всё ещё не гарантирует?

Упрочнение гарантирует завершимость, стабильный порядок и корректные результаты для деревьев с целыми настоящими ключами; оно не заставляет битое дерево значить то, что задумывал его автор. Несколько ограничений стоит знать, прежде чем строить на нём

• Множество посещённых работает по идентичности объектов. Два различных словаря с идентичным содержимым — два узла, так что продюсер, копирующий лист вместо ссылки на него, всё равно получит дубликаты записей
• Корректная, упорядоченная, но неверная /Limits всё равно отсекает. Читатель, использующий диапазоны как оптимизацию, не может заодно быть невосприимчивым к правдоподобно лгущему диапазону; единственная альтернатива — игнорировать /Limits целиком и сканировать каждый лист
• Перечисление сохраняет порядок файла, но не сортирует. GetPageLabel применяет последний перечисленный диапазон не выше страницы, так что продюсер, пишущий диапазоны не по порядку, получает семантику файлового порядка
• Память растёт с числом различных узлов и записей. Обход добавляет список и хэш-множество, больше ничего, но дерево имён на 100 МБ остаётся деревом имён на 100 МБ и после разбора
• Дубликаты ключей внутри одного листа не отчитываются. Бинарный поиск возвращает первую попавшуюся совпавшую пару; линейный фоллбэк держит последнее совпадение из просмотренных

Шпаргалка: чтение PDF-деревьев из недоверенных файлов

• Обновляйтесь до v3.539.45 или новее ради обхода деревьев имён и числовых деревьев, безопасного по циклам и стеку, и до v3.539.51 или новее, чтобы перевёрнутые /Limits больше не прятали ключи
• Трактуйте GetNamedDestination с возвратом 0 как «отсутствует», а GetDestPage с возвратом 0 как «присутствует, но непригодно»
• Для дерева имён /JavaScript используйте GlobalJavaScriptCount и GlobalJavaScriptPackageName; GetDocJavaScript читает вместо этого триггеры /AA каталога
• Индексируйте вложения и пакеты скриптов от 1 до количества, которое отчитывает библиотека; неверные ключи не считаются
• В собственном древовидном коде помечайте узлы посещёнными при снятии, кладите потомков в обратном порядке и позволяйте /Limits отсекать, только если это корректно типизированная упорядоченная пара

Пре-флайт инструменты, архиваторы и вьюеры читают эти деревья до рендеринга хоть одной страницы, так что выживать им придётся с чем угодно из очереди загрузок. Описанные выше читатели деревьев поставляются с PDFlibPas, PDF Library for Delphi, собирающейся и в Delphi, и в Free Pascal