Бъгове с реда на страниците в PDF в HotPDF: Физическа срещу логическа структура

Симптомът се появи в помощна програма за копиране на страници, изградена върху HotPDF Component: изискването на страница 1 от документ от три страници последователно произвеждаше страница 2. Проверката на логиката на индексиране не откри нищо нередно. Извикването използваше логически индекс, базиран на 0, аритметиката беше правилна, граничните условия бяха наред. Въпреки това всеки път излизаше грешната страница.

Бъгът изобщо не беше в кода за копиране. Той беше в начина, по който HotPDF изграждаше своя вътрешен масив от страници при зареждане на файла.

Две подредби, един източник на объркване

PDF файлът е колекция от непреки обекти, всеки идентифициран с номер на обект. Файловата структура не налага никакво задължение тези номера да отразяват реда на четене. Обект 1 може да съдържа страница 2; обект 20 може да съдържа страница 1. Това, което действително определя реда на четене, е дървото на страниците: йерархия от речници /Pages, чиито масиви /Kids изброяват препратките към страниците в последователността, в която четецът трябва да ги покаже (ISO 32000-1 §7.7.3).

Документът, който задейства бъга, имаше следната структура на дървото на страниците:

{ Pages tree root, object 16 }
16 0 obj
<<
  /Type /Pages
  /Count 3
  /Kids [20 0 R   { logical page 1 }
         1 0 R    { logical page 2 }
         4 0 R]   { logical page 3 }
>>
endobj

Случайно се оказа, че файлът изброява обект 1 и обект 4 преди обект 20 в потока от байтове. Всеки парсер, който обхожда непреките обекти в реда на файла и ги записва в PageArr при намиране на речници от тип страница, би завършил с обект 1 на индекс 0, обект 4 на индекс 1 и обект 20 на индекс 2. Така логическа страница 1 се намира на PageArr[2]. Изискването на страница с индекс 0 извлича логическа страница 2 вместо нея.

Точно това правеха и двата вътрешни пътя за анализ на HotPDF. Традиционният път, използван за PDF 1.3/1.4 файлове, и модерният път, използван за документи с потоци от обекти (PDF 1.5+), изграждаха PageArr чрез обхождане на непреките обекти във физическия ред на файла, вместо да следват веригата /Kids.

Потвърждаване на хипотезата

Преди да се предприеме каквато и да е корекция, несъответствието трябваше да бъде доказано, а не просто предположено. Инструментът за команден ред qpdf прави това лесно:

{ shell }
qpdf --show-pages input.pdf
{ Output reveals Kids order: 20 0 R, then 1 0 R, then 4 0 R }

qpdf --show-object="16 0 R" input.pdf
{ Shows the Pages dictionary with /Kids in reading order }

Извличането на всяка страница поотделно и проверката на размерите на файловете потвърдиха съответствието: това, което PageArr[0] произвеждаше, беше съдържанието на логическа страница 2, а PageArr[2] съдържаше логическа страница 1. Цикличното изместване беше неоспоримото доказателство. Това също обясни защо проблемът се появяваше в множество различни изходни документи: всеки PDF файл, в който обектите на страниците случайно имат по-малки номера от по-ранна логическа страница, би задействал този бъг.

Има проста причина, поради която PDF файловете се оказват в това състояние. Инкрементите при запис (incremental saves) добавят актуализирани обекти с нови номера на обекти, оставяйки старите слотове в таблицата с кръстосани препратки да сочат наникъде. Редакторите, които добавят заглавна страница, я вмъкват с висок номер на обект, независимо от позицията й в масива Kids. Някои генератори просто пишат страници в ред, удобен за предаване на съдържанието, а не в логическа последователност. PDF форматът не изисква от тях да правим нещо друго.

Корекцията: следване на масива Kids

Правилният подход е да се изгради PageArr чрез обхождане на веригата /Kids от корена на каталога, а не чрез сканиране на непреки обекти. След като и двата пътя за анализ завършат първоначалното си преминаване, стъпка за последваща обработка възстановява логическия ред:

procedure THotPDF.ReorderPageArrByPagesTree;
var
  PagesObj  : THPDFDictionaryObject;
  KidsArray : THPDFArrayObject;
  NewPageArr: array of THPDFDictArrItem;
  I, J, PageIndex, KidsIndex: Integer;
  RefObj    : THPDFLink;
  PageObjNum: Integer;
  Found     : Boolean;
begin
  { Locate root /Pages dictionary via FRootIndex }
  PagesObj := FindPagesRootFromCatalog;
  if PagesObj = nil then Exit;

  KidsIndex := PagesObj.FindValue('Kids');
  if KidsIndex < 0 then Exit;
  KidsArray := THPDFArrayObject(PagesObj.GetIndexedItem(KidsIndex));

  SetLength(NewPageArr, KidsArray.Items.Count);
  PageIndex := 0;

  for I := 0 to KidsArray.Items.Count - 1 do
  begin
    RefObj     := THPDFLink(KidsArray.GetIndexedItem(I));
    PageObjNum := RefObj.Value.ObjectNumber;

    Found := False;
    for J := 0 to Length(PageArr) - 1 do
    begin
      if PageArr[J].PageLink.ObjectNumber = PageObjNum then
      begin
        NewPageArr[PageIndex] := PageArr[J];
        Inc(PageIndex);
        Found := True;
        Break;
      end;
    end;
    { Non-page Kids (intermediate /Pages nodes) produce no match; skip }
  end;

  if PageIndex > 0 then
  begin
    SetLength(PageArr, PageIndex);
    for I := 0 to PageIndex - 1 do
      PageArr[I] := NewPageArr[I];
  end;
end;

Извикването се поставя в края на всеки път за анализ, след като всички обекти са каталогизирани, но преди да бъде обслужена каквато и да е операция по страниците:

{ Traditional path }
ListExtDictionary(THPDFDictionaryObject(IndirectObjects.Items[I]), FPageslink);
ReorderPageArrByPagesTree;
Break;

{ Modern path (object streams) }
if TryParseModernPDF then
begin
  Result := ModernPageCount;
  ReorderPageArrByPagesTree;
  Exit;
end;

Стъпката на пренареждане е O(n * m), където n е броят на Kids, а m е текущата дължина на PageArr, но за всеки документ с плоско дърво на страниците (всички листа на дълбочина 1, което покрива огромното мнозинство от реалните PDF файлове) и двете са с еднаква стойност и цената е пренебрежима. Дълбоко вложените дървета на страници изискват рекурсивно обхождане, а не едноетапния подход, показан тук; производственото внедряване обработва този случай отделно.

Използване на CopyPageFromDocument след корекцията

С въвеждането на ReorderPageArrByPagesTree, логическите индекси на страниците работят според очакванията. По-високото ниво CopyPageFromDocument приема логически индекс, базиран на 0, и копира правилната страница в целевия документ:

var
  Source, Dest: THotPDF;
begin
  Source := THotPDF.Create(nil);
  Dest   := THotPDF.Create(nil);
  try
    Source.LoadFromFile('source.pdf');

    Dest.FileName := 'extracted.pdf';
    Dest.BeginDoc;

    { Copy logical page 0 (first page the user sees) }
    Dest.CopyPageFromDocument(Source, 0, 0);

    Dest.EndDoc;
  finally
    Source.Free;
    Dest.Free;
  end;
end;

CopyPageFromDocument вътрешно прави заявка за реда на дървото на страниците, вместо да разчита на необработения индекс PageArr, така че се държи правилно дори при документи, при които физическият и логическият ред се разминават. За пакетни операции, InsertPagesFromDocument приема масив от логически индекси и ги копира с едно преминаване.

Какво разкрива това за анализа на PDF

PDF спецификацията е изрична: логическият ред на страниците се дефинира от масива /Kids на дървото на страниците, а не от номерата на обектите или байтовите отмествания (ISO 32000-1 §7.7.3.2). Всеки парсер, който използва различно подреждане като пряк път, ще даде правилни резултати при по-голямата част от документите, защото повечето генератори пишат страници в естествен ред и присвояват последователни номера на обектите. Бъгът се крие, докато някой не зареди PDF, който е бил инкрементално редактиран, реорганизиран от друг инструмент или генериран от софтуер, който е избрал различно оформление.

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

Страницата на HotPDF Component покрива пълния API за операции по страници, включително CopyPageFromDocument, InsertPagesFromDocument и MovePage.