Техническая статья

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

Соберите PDF, у которого дерево имён /Dests имеет корень с двумя детьми. Первый ребёнок декларирует /Limits [(a) (z)], и его массив /Kids указывает прямо обратно на корень. Второй ребёнок держит настоящую запись для (chapter7), но его пределы записаны задом наперёд: [(z) (a)]. Спросите у учебникового поиска по дереву имён chapter7 — и он либо уйдёт в рекурсию, пока не кончится стек, либо вернёт «не найдено» для назначения, куда вьюер может прыгнуть. Весь файл умещается примерно в два килобайта, и каждый объект в нём разбирается чисто

Этот файл пакует три отдельные ловушки в одну структуру: цикл по /Kids, диапазон, претендующий на ключ, которого не держит, и диапазон, который вообще ни с чем не может совпасть. Четвёртой ловушке нужен файл значительно крупнее. Как только один лист несёт больше 32768 пар имя/значение, любой код, утрамбовывающий «какой лист» и «какая запись» в один 32-битный integer, начинает указывать на чужую пару. Остаток статьи проходит каждую ловушку, то, что читателю с ней делать, и как ведут себя вызовы Delphi на файлах такой сборки

Четыре PDF-фичи, которые сидят на деревьях имён и чисел

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

ДеревоГде живётСпецификацияAPI чтения в PDFlibPas
Именованные назначения/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, потому что ничто в рекурсии не помнит, в какие узлы он уже входил, поэтому одна дочерняя ссылка на предка превращает конечный файл в бесконечный спуск. Легитимное дерево способно нанести тот же ущерб без всякого цикла: цепь одиночных узлов в 4096 уровней — валидный синтаксис, стоящий рекурсивному читателю 4096 кадров стека

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

PDFlibPas проходит оба вида деревьев с явным стеком LIFO на куче плюс набором посещённых, ключёванным по идентичности словаря. Узел помечается при извлечении. Циклическая ссылка может посидеть на стеке мгновение, но отбрасывается, как только поднимется обратно, и каждый различный узел разворачивает своих детей ровно один раз. Суммарная работа ограничена числом различных словарей плюс суммарной длиной их массивов /Kids; цепь в 4096 уровней становится 4096 итерациями цикла и 4096 записями hash set

Обход дерева имён в PDFlibPas: массив Kids, зацикленный на корень, переполняет стек рекурсивного обходчика, поэтому PDFlibPas работает с явным стеком и набором посещённых, помечающим узлы при извлечении, пушит детей справа налево и держит листья в файловом порядке для GetPageLabel
Глубина перестаёт иметь значение, когда рекурсия становится циклом: цепь в 4096 уровней — это просто 4096 итераций и 4096 записей hash set

Порядок — та часть, где люди ошибаются, превращая рекурсию в цикл. Стек переворачивает всё, что ему дали, поэтому детей надо пушить от последнего индекса к первому; тогда левейший ребёнок выскочит первым и листья выйдут в порядке слева направо, в котором их написал производитель. Помечать при извлечении, а не при помещении, важно по той же причине. С пометками при пуше и пушами справа налево лист, разделяемый позициями 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 пушит каждого ребёнка, чей диапазон не исключает ключ, и продолжает извлекать, пока не найдёт совпадение или стек не опустеет. На хорошо сформированном дереве с непересекающимися диапазонами проверку диапазона на каждом уровне переживает максимум один ребёнок, так что дополнительная цена — ноль. На повреждённом это горстка лишних посещений узлов, а ответ возвращается правильный

Листам — то же отношение. ISO 32000-1 требует, чтобы ключи в массиве /Names были отсортированы по байтовому значению, поэтому библиотека сначала пробует бинарный поиск. Когда он промахивается, идёт откат к линейному проходу по парам, иначе лист с нарушенным порядком сделал бы присутствующий ключ невидимым. Платить за линейный проход при каждом настоящем промахе — цена, которую мы принимаем: поиски по-настоящему отсутствующих имён редки, а ложное «не найдено» на работающей ссылке стоит куда дороже одного лишнего прохода по листу

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

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

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

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

Со стороны вызывающего есть два нуля, которые надо различать. GetNamedDestination возвращает 0, когда имени действительно нет, и ID назначения в противном случае. GetDestPage, возвращающий 0 при валидном ID, значит: имя существует, но его цель не разворачивается в страницу этого документа — другой баг-репорт. 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», потому что зацикленный ребёнок выигрывает гонку; поиск, доверяющий перевёрнутым диапазонам, напечатает то же самое по противоположной причине. Когда назначения разрешаются, записи оглавления, указывающие на них, разобраны в статье чтение действий закладок и аннотаций PDF в Delphi

Листья за 32768 записей и ловушка упакованного индекса

Когда коду нужен один целочисленный хендл для «записи N в листе M», соблазнительная упаковка кладёт позицию листа в старшие 16 битов Integer, а смещение внутри массива /Names этого листа — в младшие 16. Каждая пара занимает два слота массива. Пара с индексом 32768 — 32769-я пара — начинается со смещения 65536, это $10000. Этот бит переезжает в старшую половину, и декодер прочитает его обратно как смещение 0 следующего листа

Упакованный индекс дерева имён, где позиция листа и смещение записи делят один 32-битный Integer и пара 32768 стартует со смещения 65536: перенос в старшую половину читается как смещение 0 следующего листа, и find или delete трогает чужую пару, а отдельный проход по ключам с ним расходится
Два 16-битных значения в одном 32-битном целом обрезаются молча в тот момент, когда лист переваливает за 32768 пар — размер, до которого реальные справочные руководства добираются

Симптомы зависят от формы дерева. С единственным листом следующего листа нет, и декодированный хендл индексирует за конец списка листов. С несколькими листьями find или delete приземляется на первую пару следующего листа, в то время как простой проход по ключам всё ещё докладывает запрошенный ключ как присутствующий. Файлы такого размера не экзотика. Сгенерированное справочное руководство API с одним именованным назначением на символ переваливает за 32768 записей быстро, и некоторые производители пишут их все в один плоский лист вместо балансировки дерева

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 и десятичных с префиксом A- со страницы 2. Аудит должен напечатать i и A-1, каждый диапазон применённый единожды. Запись меток страниц в такое дерево имеет свои морщины — об этом статья починка PDF page labels, хранимых в дереве чисел /Kids; AddPageLabels перед вставкой сплющивает корень с /Kids в единственный лист /Nums, используя ту же безопасную к циклам нумерацию

Где обход проводит свои границы

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

  • Узел определяет идентичность, а не содержимое. Два разных словаря с одинаковыми записями — два узла, поэтому производитель, копирующий лист вместо ссылки на него, получит эти записи дважды
  • Корректная упорядоченная пара /Limits отсекает, даже когда она неверна. Диапазон, правдоподобно лгущий — скажем, [(a) (m)] поверх листа, который ещё держит (q), — прячет q. Единственная защита — игнорировать /Limits везде и проходить каждый лист, а на дереве назначений с десятками тысяч записей это выбрасывает причину существования записи. Мы сохраняем отсечение
  • Нумерация сохраняет файловый порядок. GetPageLabel проходит каждый перечисленный диапазон и применяет последний, чей стартовый индекс не выше страницы, поэтому производитель, пишущий диапазоны не по порядку, получает семантику файлового порядка, а разворот обхода вручил бы странице 200 стиль вводной части
  • Память растёт с числом различных узлов и записей. Обход добавляет один список и один hash set поверх разобранных объектов
  • Дубликаты ключей внутри одного листа разрешаются детерминированно: бинарный поиск возвращает ту совпавшую пару, на которую приземлился первым, а линейный откат сохраняет последнюю просканированную пару

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