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