Articolo tecnico

Alberi dei nomi in PDFlibPas: cicli, Limits e foglie enormi

Costruisci un PDF il cui albero dei nomi /Dests abbia una radice con due figli. Il primo figlio dichiara /Limits [(a) (z)], e il suo array /Kids punta dritto indietro alla radice. Il secondo figlio tiene la voce reale per (chapter7), ma i suoi limiti sono scritti al contrario: [(z) (a)]. Chiedete a una ricerca da manuale di name tree chapter7 e o ricorre finché lo stack non si esaurisce o risponde "non trovato" per una destinazione alla quale un viewer può saltare. L'intero file sta in circa due kilobyte, e ogni oggetto al suo interno si parserizza pulito

Quel file impacchetta tre trappole separate in una struttura sola: un ciclo /Kids, un intervallo che rivendica una chiave che non tiene, e un intervallo che non può combaciare con niente. Una quarta trappola richiede un file molto più grande. Appena una singola foglia porta più di 32.768 coppie nome/valore, qualsiasi codice che stipi "quale foglia" e "quale voce" in un solo intero a 32 bit inizia a puntare alla coppia sbagliata. Il resto dell'articolo attraversa ogni trappola, cosa dovrebbe fare un lettore, e come si comportano le chiamate Delphi su file costruiti così

Quattro funzionalità PDF che poggiano su alberi dei nomi e number tree

Gli alberi dei nomi e i number tree sorreggono ogni funzionalità PDF che mappa un grande insieme di chiavi a oggetti, e PDFlibPas, la PDF Library di losLab per Delphi, ne espone quattro attraverso metodi pubblici di TPDFlib. ISO 32000-1 §7.9.6 definisce il name tree (chiavi stringa, Table 36) e §7.9.7 il number tree (chiavi intere, Table 37). Radice e nodi intermedi portano /Kids; le foglie portano coppie chiave/valore ordinate in /Names o /Nums; ogni nodo non radice dovrebbe portare un array /Limits a due elementi con la chiave più piccola e più grande sotto di lui

AlberoDove viveSpecificazioneAPI di lettura PDFlibPas
Named destinations/Dests nel dizionario dei nomi§12.3.2.3GetNamedDestination, poi GetDestPage / GetDestType
Etichette di pagina/PageLabels nel catalogo (number tree)§12.4.2GetPageLabel
Allegati/EmbeddedFiles nel dizionario dei nomi§7.7.4, §7.11.4EmbeddedFileCount, GetEmbeddedFileStrProperty
JavaScript a livello di documento/JavaScript nel dizionario dei nomi§7.7.4GlobalJavaScriptCount, GlobalJavaScriptPackageName

Due righe nascondono una piega. Le named destinations esistono anche in una forma più vecchia del PDF 1.1, un semplice dizionario /Dests nel catalogo indicizzato da oggetti nome, e GetNamedDestination controlla prima quel dizionario e solo dopo scende nell'albero dei nomi del PDF 1.2. La riga JavaScript ha un quasi omonimo che legge tutt'altro: GetDocJavaScript restituisce gli script attaccati ai trigger del documento nel dizionario /AA del catalogo (WS, DS, WP, DP, DC), mentre i pacchetti nominati che girano all'apertura di un documento vivono nell'albero dei nomi /JavaScript e vengono elencati da GlobalJavaScriptPackageName

Tutte queste strutture vengono dal file. La specifica dice a chi scrive cosa deve produrre, e un lettore riceve comunque ciò che lo scrittore, un salvataggio incrementale bacato o un fuzzer ci hanno davvero messo. È la stessa lezione di irrobustire un parser PDF Pascal contro file ostili, applicata alla forma dell'albero invece che alle lunghezze dei buffer

Perché un array /Kids ciclico manda in crash un percorritore ricorsivo?

Un percorritore ricorsivo va in crash su un array /Kids ciclico perché nulla nella ricorsione ricorda quali nodi ha già attraversato, così un riferimento figlio a un antenato trasforma un file finito in una discesa infinita. Un albero legittimo può fare lo stesso danno senza alcun ciclo: una catena a 4.096 livelli di nodi a figlio singolo è sintassi valida che costa a un lettore ricorsivo 4.096 frame di stack

La variante più mite non va in crash affatto. Quando due voci /Kids riferiscono la stessa foglia, un'enumerazione ingenua la visita due volte, così un conteggio di allegati torna più alto del numero di file nel documento e una lista di script mostra lo stesso pacchetto due volte

PDFlibPas percorre entrambi i tipi di albero con uno stack esplicito last-in, first-out sull'heap più un insieme dei visitati indicizzato per identità del dizionario. Un nodo viene marcato quando viene estratto. Un riferimento ciclico può stare nello stack per un attimo, ma viene scartato appena riaffiora, e ogni nodo distinto espande i propri figli esattamente una volta. Il lavoro totale è limitato dal numero di dizionari distinti più la lunghezza combinata dei loro array /Kids; una catena a 4.096 livelli diventa 4.096 iterazioni di ciclo e 4.096 voci in un hash set

Percorso degli alberi dei nomi in PDFlibPas dove un array Kid che rimanda alla radice uccideva un percorritore ricorsivo con uno stack overflow, sostituito dalla v3.539.45 da uno stack esplicito e un insieme dei visitati che marca i nodi al pop, inserisce i figli da destra a sinistra e tiene le foglie in ordine di file per GetPageLabel
La profondità smette di contare quando la ricorsione diventa un ciclo: una catena a 4.096 livelli sono solo 4.096 iterazioni e 4.096 voci di hash set

L'ordine è la parte dove la gente sbaglia quando converte la ricorsione in un ciclo. Uno stack capovolge ciò che gli dai, quindi i figli vanno inseriti dall'ultimo indice al primo; poi il figlio più a sinistra esce per primo e le foglie arrivano nell'ordine da sinistra a destra in cui il produttore le ha scritte. Marcare all'estrazione anziché all'inserimento conta per lo stesso motivo. Con marche all'inserimento e inserimenti da destra a sinistra, una foglia condivisa dalle posizioni 0 e 2 verrebbe rivendicata dalla posizione 2, e le sue voci comparirebbero più tardi di quanto il file dice. Le etichette di pagina dipendono da quell'ordine, come mostra l'ultima sezione

Se scrivete codice di alberi vostro contro qualche altro object model, questa è la forma che raccomandiamo. Il tipo nodo qui sotto è deliberatamente astratto, ed entrambe le funzioni sono codice lato lettore, non chiamate di libreria

uses
  System.Generics.Collections;

type
  TTreeNode = class
  public
    Kids: TArray<TTreeNode>;   // vuoto su una foglia
    Keys: TArray<string>;      // chiavi foglia, ordinate da un produttore per bene
    Values: TArray<Integer>;   // parallelo a Keys
    HasLimits: Boolean;
    LoKey, HiKey: string;
  end;

// Helper tuo: /Limits può potare solo quando è una coppia ben formata e ordinata
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;

// Ricerca tua: stack esplicito, insieme dei visitati, marcate all'estrazione
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;                      // ciclo o figlio condiviso: già visto
      Visited.Add(Node, 0);
      if Length(Node.Kids) > 0 then
      begin
        // Inserisci da destra a sinistra così il kid più a sinistra esce per primo
        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;
      // Un mancato ritrovato in questa foglia: continua a pescare i suoi fratelli
    end;
  finally
    Visited.Free;
    Pending.Free;
  end;
end;

Un mancato ritrovato in un ramo non dice niente sull'albero

La scorciatoia di ricerca più comune sceglie il primo figlio i cui /Limits coprono la chiave, scende lì dentro, e non guarda mai più un fratello. Su un albero pulito è corretto e veloce. Sul file del paragrafo d'apertura fallisce: il primo figlio rivendica chapter7, rimanda alla radice, e la ricerca finisce a mani vuote mentre il fratello successivo tiene la voce

PDFlibPas non si ferma al primo ramo plausibile. La ricerca con chiave dietro GetNamedDestination inserisce ogni figlio il cui intervallo non esclude la chiave, e continua a pescare finché non trova una corrispondenza o lo stack si svuota. Su un albero ben formato con intervalli disgiunti, al massimo un figlio sopravvive al controllo di intervallo a ogni livello, quindi il costo extra è nullo. Su uno danneggiato sono poche visite di nodo in più, e la risposta torna giusta

Le foglie ricevono lo stesso trattamento. ISO 32000-1 richiede che le chiavi in un array /Names siano ordinate per valore di byte, quindi la libreria prova prima una ricerca binaria. Quando quella manca, ripiega su una scansione lineare delle coppie, perché una foglia fuori ordine altrimenti renderebbe invisibile una chiave presente. Pagare una scansione lineare a ogni mancato ritrovato genuino è un costo che accettiamo: le ricerche per nomi davvero assenti sono rare, e un falso "non trovato" su un link funzionante costa molto più di un passaggio in più su una foglia

Una contraddizione strutturale viene gestita con il rifiuto. La Table 36 consente a un nodo di portare o /Kids o /Names, mai entrambi. Una ricerca con chiave tratta un nodo che porta entrambi come malformato e lo salta invece di indovinare quale metà intendesse il produttore. L'enumerazione dei number tree, come il percorso dietro GetPageLabel, è più indulgente e segue /Kids quando entrambi sono presenti, dato che buttare via un intervallo intero etichetterebbe male ogni pagina successiva

Di cosa può fidarsi un lettore riguardo a /Limits?

Un lettore può fidarsi di /Limits per saltare lavoro, e solo quando la coppia è ben formata; non può mai usare la voce per concludere che una chiave è assente. La Table 36 dice che i nodi intermedi e foglia devono portarla, eppure in pratica la voce sparisce dopo modifiche a mano, tiene numeri dentro un albero dei nomi, o arriva con i bordi invertiti. PDFlibPas risolve ognuno di questi casi allo stesso modo, tenendo il figlio ricercabile

  • /Limits mancanti: un controllo di intervallo che salta un figlio del genere rende il suo intero sottoalbero irraggiungibile ogni volta che un produttore dimentica la voce, quindi il figlio viene cercato
  • Tipo sbagliato o lunghezza sbagliata, come numeri in un albero dei nomi o un array a un elemento: gestito esattamente come una voce mancante
  • Bordi invertiti come [(Z) (A)] o [9 0]: nessuna chiave soddisfa Lo <= Key <= Hi quando Lo > Hi, quindi fidarsi della coppia escluderebbe il ramo per ogni ricerca; un intervallo pota solo quando il proprio bordo inferiore non supera il bordo superiore
  • Ben formata e ordinata: usata per saltare il ramo, che è ciò per cui la voce esiste
Regole di PDFlibPas per fidarsi di un array Limits di un albero dei nomi: una coppia mancante, di tipo sbagliato o invertita lascia il figlio ricercabile dalla v3.539.45 e v3.539.51, e solo una coppia ben formata e ordinata può potare il ramo, così un Limits ostile può costare visite ma non può più nascondere una destinazione esistente
Gli intervalli possono saltare lavoro ma non decidono mai l'assenza, perché le chiavi reali conservate nelle foglie decidono l'esito di ogni ricerca

Dal lato del chiamante ci sono due zeri da distinguere. GetNamedDestination restituisce 0 quando il nome è davvero assente e un ID di destinazione altrimenti. Un GetDestPage che restituisce 0 per un ID valido significa che il nome esiste ma il suo bersaglio non si risolve in una pagina di questo documento, il che è una segnalazione di difetto diversa. GetDestType riporta la vista come 1 per XYZ, 2 per Fit e così via fino a 8 per 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;
    // Prima il /Dests del catalogo (PDF 1.1), poi l'albero dei nomi /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;

Questo è un controllo di regressione compatto. Costruite il file a due figli del paragrafo d'apertura, puntate la voce reale chapter7 alla pagina 2 con una vista /Fit, e la procedura dovrebbe stampare pagina 2 con tipo di vista 2. Una ricerca al primo combaciamento stampa "No destination" perché il figlio ciclico vince la corsa; una ricerca che si fida degli intervalli invertiti stampa la stessa cosa per il motivo opposto. Una volta che le destinazioni si risolvono, le voci di outline che puntano a loro sono coperte in leggere le azioni di segnalibri e annotazioni PDF in Delphi

Foglie oltre le 32.768 voci e la trappola dell'indice impacchettato

Quando il codice richiede un handle intero unico per "voce N nella foglia M", la codifica allettante stipa la posizione della foglia nei 16 bit alti di un Integer e l'offset dentro l'array /Names di quella foglia nei 16 bit bassi. Ogni coppia occupa due slot dell'array. L'indice di coppia 32.768, la coppia numero 32.769, parte quindi all'offset 65.536, che è $10000. Quel bit riporta nella metà alta, e il decoder lo rilegge come offset 0 della foglia successiva

Impacchettamento FindIndex di TPDFNameTree in PDFlibPas dove una posizione di foglia e un offset di voce condividevano un Integer a 32 bit e la coppia 32768 partiva all'offset 65536, così il riporto nei bit alti veniva letto come offset 0 della foglia successiva e FindKey o DeleteKey toccavano la coppia sbagliata mentre HasKey dissentiva
Due valori a 16 bit in un intero a 32 bit troncano in silenzio nel momento in cui una foglia supera le 32.768 coppie, una dimensione che veri manuali di riferimento raggiungono

I sintomi dipendono dalla forma dell'albero. Con una foglia singola non c'è foglia successiva, quindi l'handle decodificato indicizza oltre la fine della lista di foglie. Con più foglie, un find o un delete atterra sulla prima coppia della foglia seguente, mentre una semplice scansione per chiave continua a riportare la chiave richiesta come presente. File di questa taglia non sono esotici. Un riferimento API generato con una named destination per simbolo supera le 32.768 voci in fretta, e alcuni produttori scrivono tutte in un'unica foglia piatta invece di bilanciare l'albero

PDFlibPas tiene la posizione della foglia e l'offset della voce in due interi a larghezza piena, quindi nessuno dei due può traboccare nell'altro a qualsiasi dimensione di foglia. Lo stesso lettore conta solo chiavi stringa genuine. Per una foglia come [(Valid) 42 123 456], EmbeddedFileCount riporta 1, la chiave numerica 123 non viene mai scambiata per un nome vuoto, e un indice di 0 o sotto restituisce una stringa vuota da GetEmbeddedFileStrProperty invece di qualsiasi oggetto capiti dopo. Il tag 1 di quella funzione è il nome del file e il tag 2 il sottotipo MIME

procedure AuditTrees(const FileName: string);
var
  Lib: TPDFlib;
  I: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile(FileName, '') <> 1 then
      Exit;
    // Number tree /PageLabels; i file senza restituiscono numeri di pagina semplici
    for I := 1 to Lib.PageCount do
      WriteLn('Page ', I, ' label: ', Lib.GetPageLabel(I));
    // Albero dei nomi /EmbeddedFiles; indici a base 1, chiavi non stringa saltate
    for I := 1 to Lib.EmbeddedFileCount do
      WriteLn('Attachment ', I, ': ', Lib.GetEmbeddedFileStrProperty(I, 1),
        ' (', Lib.GetEmbeddedFileStrProperty(I, 2), ')');  // nome, sottotipo MIME
    // Albero dei nomi /JavaScript: elenca i nomi dei pacchetti, non esegue nulla
    for I := 1 to Lib.GlobalJavaScriptCount do
      WriteLn('Script package: ', Lib.GlobalJavaScriptPackageName(I));
  finally
    Lib.Free;
  end;
end;

Un file di test a due pagine mostra bene l'output atteso. Date al suo radice /PageLabels un array /Kids che elenca una foglia due volte e riferisce anche la radice stessa, con intervalli per il romano minuscolo dalla pagina 1 e per il decimale con prefisso A- dalla pagina 2. L'audit dovrebbe stampare i e A-1, ogni intervallo applicato una volta. Scrivere etichette di pagina in un albero simile ha le sue proprie pieghe, coperte in correggere le etichette di pagina PDF conservate in number tree /Kids; AddPageLabels appiattisce un radice /Kids in un'unica foglia /Nums prima di inserire, usando la stessa enumerazione sicura dai cicli

Dove il percorso di attraversamento traccia i propri confini

L'attraversamento garantisce terminazione, ordine stabile e risposte corrette per qualsiasi albero le cui chiavi reali siano intatte. Legge un albero danneggiato così com'è scritto e non prova a ricostruire cosa intendesse l'autore, e da quella scelta seguono cinque conseguenze

  • L'identità, non il contenuto, definisce un nodo. Due dizionari distinti con voci identiche sono due nodi, così un produttore che copia una foglia invece di referenziarla prende quelle voci due volte
  • Una coppia /Limits ben formata e ordinata pota anche quando è sbagliata. Un intervallo che mente in modo plausibile, diciamo [(a) (m)] sopra una foglia che tiene anche (q), nasconde q. L'unica difesa sarebbe ignorare /Limits ovunque e scansionare ogni foglia, e su un albero di destinazioni con decine di migliaia di voci questo butta via il motivo per cui la voce esiste. Noi continuiamo a potare
  • L'enumerazione conserva l'ordine del file. GetPageLabel percorre ogni intervallo enumerato e applica l'ultimo il cui indice di partenza è alla pagina o sotto, quindi un produttore che scrive gli intervalli fuori ordine ottiene semantica da ordine di file, e invertire il percorso consegnerebbe alla pagina 200 lo stile del frontespizio
  • La memoria cresce con i nodi e le voci distinti. L'attraversamento aggiunge una lista e un hash set sopra gli oggetti parserizzati
  • Le chiavi duplicate dentro una foglia si risolvono in modo deterministico: la ricerca binaria restituisce la coppia corrispondente su cui atterra per prima, e il ripiego lineare conserva l'ultima corrispondenza che scansiona

Gli strumenti di preflight, gli archiviatori e i viewer di documenti leggono questi alberi prima che una singola pagina venga renderizzata, il che li mette in prima fila per qualsiasi cosa arrivi in una coda di upload. I lettori di alberi descritti qui vengono con PDFlibPas, la PDF Library per Delphi, che si compila sia con Delphi sia con Free Pascal