PDFlibPas: цикли, /Limits и огромни листа в name дървета

PDFlibPas, PDF библиотеката на losLab за Delphi, обхожда PDF name и number дърветата с изричен стек и набор от посетени възли от v3.539.45 насам, така че цикличен /Kids, споделени деца и дървета с хиляди нива дълбочина вече не изчерпват call стека и не дублират записи. От v3.539.51 липсваща, повредена или обърната двойка /Limits никога не скрива клон, който държи ключа. Именувани дестинации, етикети на страници, прикачени файлове и JavaScript на ниво документ минават през тези два кодови пътя, което ги прави част от attack surface на всеки PDF, който не сте произвели сами

Тригерът рядко е екзотичен. Fuzzer, враждебен upload или бъгав incremental save записва /Kids запис, сочещ обратно към предшественик, а рекурсивен обход умира със stack overflow върху файл от два килобайта. По-тихата повреда е търсене, което вярва на счупен масив /Limits и докладва „не е намерено“ за дестинация, която ясно е там

Къде се срещат name и number дърветата в един PDF?

Name и number дърветата се появяват навсякъде, където един PDF съпоставя голямо множество от ключове към обекти, а PDFlibPas чете поне четири от тях през публични API. ISO 32000-1 §7.9.6 дефинира name дървото (string ключове, Table 36), а §7.9.7 — number дървото (integer ключове, Table 37). И двете са полубалансирани дървета, чиито корен и междинни възли носят /Kids, чиито листа носят сортираните двойки ключ/стойност в /Names или /Nums, а чиито не-коренни възли носят двуелементен масив /Limits с най-малкия и най-големия ключ под тях

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

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

Всеки байт от тези структури идва от файла. Спецификацията казва какво е длъжен да произведе един writer; тя не може да спре четец да получи нещо друго, което е същият урок зад закаляването на Pascal PDF парсер срещу зловредни файлове, приложено тук към формата на дървото, а не към размерите на буферите

Защо цикличен масив /Kids кръши рекурсивен обход на дърво?

Цикличен масив /Kids кръши рекурсивен обход, защото нищо в рекурсията не забелязва, че вече е виждало даден възел, така че дете, сочащо собствения си предшественик, превръща краен файл в безкрайно спускане. Преди v3.539.45 NameTreeLookup, NumTreeLookup, EnumNumTree и вътрешният TPDFNameTree.ProcessNode всички се извикваха сами по веднъж на дете. Една-единствена самоотправка стигаше да убие процеса, а легитимно, но много дълбоко дърво можеше да направи същото без никакъв цикъл

По-мека разновидност разваля резултати, вместо да кръши. Когато два записа /Kids сочат един и същ лист, наивно изброяване минава през него два пъти, а брояч на прикачени файлове или списък със скриптови пакети докладва записи, които не съществуват

Поправката заменя рекурсията с изричен LIFO стек в heap-а и набор от посетени възли, ключуван по идентичност на речника. Възел се маркира когато е изваден от стека, не когато е сложен, така че циклична отправка може да седи малко в стека, но се изхвърля в момента, в който изплува отново. Всеки различен възел разгаря децата си точно веднъж, което ограничава общата работа с броя различни речници плюс общата дължина на масивите им /Kids. Дълбочината спира да има значение: верига на 4096 нива е просто 4096 итерации на цикъл и 4096 записа в hash set

Редът обаче пак има значение, а стекът трябва да се пълни обратно, за да се запази. Децата се добавят от последния индекс надолу до първия, така че най-лявото дете излиза пръв, а листата излизат в същия порядък отляво надясно, в който ги е написал producer-ът. GetPageLabel зависи от това: то минава през всеки изброен диапазон и прилага последния, чийто начален индекс е на страницата или под нея, така че обърнато изброяване мълчаливо би дало на страница 200 стила на уводните страници. Скелетът по-долу показва образеца върху абстрактен тип възел, независимо от всеки PDF обектен модел

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // празно при листо
    Keys: TArray<string>;      // ключове на листа, сортирани от коректен producer
    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 да са сортирани по byte стойност, така че листът първо се претърсва с binary search. Ако това провали, PDFlibPas пада обратно на линейно сканиране на двойките, защото иначе лист извън ред би направил наличен ключ невидим. Сортирането е бърз път, не филтър

Търсенето също отказва да гадае при едно структурно противоречие. Table 36 позволява възел да носи или /Kids, или /Names, никога и двете, а пътят на търсенето третира възел, носещ и двете, като повреден и го прескача, вместо да избере една от интерпретациите. Пътищата за изброяване като EnumNumTree са по-снизходителни и следват /Kids, когато и двете са налични

За какво може да вярва един четец на /Limits?

Един четец може да вярва на /Limits само за да прескача работа, никога за да реши, че ключ липсва, и само когато двойката е коректна. Table 36 казва, че междинните и листните възли трябва да носят /Limits като двуелементен масив от най-малкия и най-големия ключ, но на практика записът изчезва след ръчни редакции, държи числа в name дърво или пристига с разменени граници. PDFlibPas v3.539.45 и v3.539.51 решават всеки случай по един и същ начин: ако диапазонът не може да се прочете като подредена двойка от правилния тип, детето остава търсимо

• Липсващ /Limits: старата проверка на диапазон връщаше False и детето се прескачаше изцяло, така че producer, забравил записа, правеше целия си subtree недостижим. От v3.539.45 детето се търси
• Грешен тип или грешна дължина, като числа в name дърво или едноелементен масив: третира се точно като липсващ запис от 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), после name дървото /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 с view тип 2 (Fit). Преди v3.539.45 същото търсене връщаше 0, защото цикличното дете претендираше ключа пръв и търсенето никога не стигаше до брат му; самото v3.539.45 пак връщаше 0, защото обърнатият диапазон изключваше истинския лист. Ако после четете outline-а, сочащ тези дестинации, статията-спътник за четене на PDF bookmark и annotation действия в Delphi покрива страната на действията

Как лист с 32769 имена счупи TPDFNameTree?

Лист с 32769 двойки име/стойност счупи TPDFNameTree, защото вътрешният му FindIndex опакова два числа в един 32-битов Integer: позицията на листа във вътрешния списък-масив в горните 16 бита и отместването на записа в масива /Names на този лист в долните 16 бита. Всяка двойка заема два слота в масива, така че 32769-та двойка, с индекс 32768, започва на отместване 65536, тоест $10000. Тази стойност пренася в горната половина, а декодерът я прочиташе обратно като отместване 0 в следващия лист

TPDFNameTree е класът зад прикачени файлове, глобални JavaScript пакети и записвания на именувани дестинации, което прави последствията конкретни. В еднолистово дърво няма следващ лист, така че FindKey и DeleteKey индексираха след края на списъка с листа; в многолистово дърво връщаха или изтриваха първата двойка на следващия лист вместо поисканата. Междувременно HasKey вършеше собствено сканиране и докладваше ключа като наличен, така че класът си противоречеше. Генерирано reference ръководство с по една именувана дестинация на API символ надхвърля 32768 записа без да се напряга, а някои producers пишат всичките в един плосък лист

От v3.539.45 FindIndex връща индекса в масива през отделен out параметър, а пълното отместване на записа — като свой резултат, така че нито една стойност не се отрязва. Същото издание стегна и два съседа. KeyName вече брои и връща само истински string ключове и връща празен низ за индекс 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 number дърво; файлове без такова връщат обикновени номера
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // /EmbeddedFiles name дърво; индексите са от 1, не-string ключове прескачани
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // име, MIME тип
    // /JavaScript name дърво: изброявай имена на пакети, нищо не изпълнявай
    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 етикети на страници, съхранявани в number дървета /Kids; AddPageLabels изравнява такъв корен преди вмъкване и разчита на същото изброяване EnumNumTree, описано тук

Какво това закаляване все още не гарантира?

Закаляването гарантира крайност, стабилен ред и верни резултати за дървета, чиито истински ключове са целите; то не кара повредено дърво да значи онова, което авторът му е имал предвид. Няколко ограничения си струват да ги знаете, преди да градите върху него

• Наборът от посетени възли работи по обектна идентичност. Два различни речника с идентично съдържание са два възела, така че producer, който копира лист вместо да го сочи, пак дава дублирани записи
• Коректен, подреден, но неверен /Limits все още отрязва. Четец, ползващ диапазони като оптимизация, не може едновременно да е имунен срещу диапазон, който убеждаващо лъже; единствената алтернатива е да игнорирате /Limits изцяло и да сканирате всеки лист
• Изброяването пази файловия ред, но не сортира. GetPageLabel прилага последния изброен диапазон на страницата или под нея, така че producer, пишащ диапазони извън ред, получава семантика по файлов ред
• Паметта расте с броя различни възли и записи. Обхождането добавя списък и hash set, нищо повече, но name дърво от 100 MB си остава name дърво от 100 MB и след парсването
• Дублирани ключове в един лист не се докладват. Binary search връща която и да е съвпадаща двойка, в която удари пръв; линейният fallback пази последното съвпадение, което сканира

Бърза справка: четене на PDF дървета от недоверени файлове

• Надградете към v3.539.45 или по-нова за обхождане на name и number дървета, устойчиво на цикли и на стек, и към v3.539.51 или по-нова, така че обърнати /Limits вече да не крият ключове
• Третирайте GetNamedDestination, връщащ 0, като „липсва“, а GetDestPage, връщащ 0, като „налична, но неизползваема“
• Ползвайте GlobalJavaScriptCount и GlobalJavaScriptPackageName за name дървото /JavaScript; GetDocJavaScript чете вместо това тригерите /AA на каталога
• Индексирайте прикачени файлове и скриптови пакети от 1 до броя, който библиотеката докладва; невалидните ключове не се броят
• В собствения си код за дървета маркирайте възлите като посетени при изваждане, добавяйте децата в обратен ред и оставяйте /Limits да отрязва само когато е коректно типизирана, подредена двойка

Pre-flight инструменти, архиватори и прегледачи четат тези дървета, преди която и да е страница да е рендирана, така че те трябва да оцелеят срещу каквото и да пристигне в опашка за upload. Четеците на дървета, описани по-горе, идват с PDFlibPas, PDF библиотеката за Delphi, която се компилира както с Delphi, така и с Free Pascal