PDF puslapių medžio forma: išsišakojimas, suplokštinimas ir /Count vientisumas

Mūsų papildomame straipsnyje apie PDF puslapių tvarką aprašyta pagrindinė taisyklė: rodymo tvarka gaunama gilyn pirmiausia (depth-first), iš kairės į dešinę einant per /Kids masyvus /Pages medyje, o ne pagal objektų numerius. Šiame straipsnyje į medį žvelgiama kitu kampu — į jo formą. Kodėl subrendę PDF generatoriai kuria tarpinių mazgų hierarchijas, kai vienas plokščias masyvas būtų visiškai teisėtas? Kas iš tikrųjų pasikeičia, kai įrankis suplokština arba perkuria medį? Ir kas nutinka, kai /Count apskaita, dėl kurios visa struktūra veikia greitai, nustoja sakiusi tiesą

Išsišakojimas — tai našumo sprendimas

Niekas nereikalauja generatoriaus lizdinti mazgų. 10 000 puslapių dokumentas su vienu šakniniu /Pages mazgu ir 10 000 lapo nuorodų viename /Kids masyve atitinka specifikaciją. Vis dėlto PDF Reference rekomenduoja dideliems dokumentams naudoti subalansuotą medį, o pagrindiniai generatoriai šio patarimo laikosi su nedideliu išsišakojimu — paprastai po kelias dešimtis vaikų kiekviename tarpiniame mazge

Priežastis — tai, ką peržiūros programa turi perskaityti prieš ką nors parodydama. Įsivaizduokite šuolį tiesiai į 8 214 puslapį tame 10 000 puslapių faile. Su plokščiu medžiu peržiūros programa pirmiausia turi analizuoti šakninį mazgą, o šis mazgas yra vienas milžiniškas masyvas: apytiksliai aštuoni baitai vienai netiesioginei nuorodai, tad 80 KB objektą reikia visiškai tokenizuoti, kol bus išspręstas 8 213 įrašas. Su subalansuotu medžiu, kurio išsišakojimas 32, tas pats šuolis nuskaito šaknį, palygina einamąsias /Count sumas, kad parinktų tinkamą vaiką, ir leidžiasi žemyn — iš viso trys ar keturi maži žodynai, kiekvienas po kelis šimtus baitų. Tai ir yra O(log n) atsitiktinė prieiga, kuriai medis buvo sukurtas, ir būtent dėl to /Count egzistuoja tarpiniuose mazguose: jis leidžia skaitytojui praleisti visą pomedį neatidarant nė vieno jame esančio objekto

Medžio forma taip pat lemia redagavimo kainą. Dalinis atnaujinimas, įterpiantis vieną puslapį, turi perrašyti kiekvieną mazgą, kurio /Kids arba /Count pasikeitė, tai yra kelią nuo naujojo lapo tėvo iki šaknies. Subalansuotame medyje tas kelias — tai keletas mažų žodynų, pridedamų prie failo. Plokščiame medyje „kelias" yra tas pats vienintelis milžiniškas šakninis masyvas, kiekvienoje redakcijoje dubliuojamas ištisai. Sutartis, praėjusi trisdešimt peržiūros ir anotavimo ciklų, gali baigti tempdama trisdešimt pakeistų to paties 80 KB masyvo kopijų savo baitų sraute

Vidiniai mazgai perduoda paveldimus atributus

Tarpiniai mazgai nėra vien maršrutizavimas. Keturi paveldimi puslapio atributai — /Resources, /MediaBox, /CropBox ir /Rotate — gali būti perkelti į bet kurį /Pages mazgą, kur jie taikomi kiekvienam žemiau esančiam lapui, nebent palikuonis juos perrašo. Generatorius, kuriantis ataskaitą su gulsčiu priedu, gali šį išdėstymą išreikšti pačiame medyje:

5 0 obj   % dokumento šaknis
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % ataskaitos pagrindas: stačias A4, pagrindinis šriftas
<< /Type /Pages /Parent 5 0 R /Count 3
   /Kids [30 0 R  31 0 R  32 0 R]
   /MediaBox [0 0 595 842]
   /Resources << /Font << /F1 8 0 R >> >> >>
endobj

7 0 obj   % priedas: gulsčias A4, pasuktas, savas šriftas
<< /Type /Pages /Parent 5 0 R /Count 3
   /Kids [40 0 R  41 0 R  42 0 R]
   /MediaBox [0 0 842 595] /Rotate 90
   /Resources << /Font << /F2 9 0 R >> >> >>
endobj

40 0 obj  % priedo puslapis: paveldi dydį, pasukimą, šriftus
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

Objektai nuo 40 iki 42 yra beveik tušti. Jų puslapio dydis, pasukimas ir šrifto ištekliai atkeliauja per paveldėjimą iš mazgo 7, todėl failas lieka kompaktiškas ir savaime tvarkomas: pridėjus ketvirtą puslapį po priedo mazgu, jis automatiškai išeis gulsčias

Tas pats mechanizmas sukuria klasikinį puslapio perkėlimo pavojų. Tarkime, įrankis perkelia objektą 40 į ataskaitos pagrindą, redaguodamas abu /Kids masyvus ir nukreipdamas /Parent į mazgą 6. Perkėlimas struktūriniu požiūriu teisingas, tačiau objektas 40 dabar paveldi stačią /MediaBox, jokio pasukimo ir šriftą /F1 — nors jo turinio srautas vis dar renkasi /F2, kuris nebeišsprendžiamas. Puslapis susitraukia, atsisuka atgal ir viename redagavime praranda tekstą. Todėl patikimas puslapių pertvarkymo kodas prieš keisdamas tėvinį mazgą užfiksuoja visų keturių paveldimų atributų išspręstas reikšmes tiesiai puslapio žodyne. Jei kada nors tempėte puslapį redaktoriuje ir matėte, kaip jis pakeičia dydį ar orientaciją, — tai ir yra tas mechanizmas

Suplokštinimas: teisėta, dažna, kartais brangi operacija

Daugybė įrankių eina priešinga kryptimi. Minimalūs generatoriai kuria vieno lygio medį, nes tai paprasta, o daugelis sujungimo ir skaidymo priemonių bet kokį perskaitytą medį perkuria į vieną plokščią /Kids masyvą, nes subalansuotos struktūros generavimas — papildomas darbas, o plokščias rezultatas visada atitinka specifikaciją. Teisingas perkūrimas privalo tuo pačiu metu išspręsti paveldėjimą: kiekvienas atributas, kurį lapas paveldėjo, turi būti nukopijuotas į patį lapą arba, jei jis vienodas visame dokumente, perkeltas į naują šaknį — kitaip rezultatas pakeičia geometriją lygiai taip pat, kaip ir puslapio perkėlimo atveju

Įprastiems dokumentams suplokštinimas nekenksmingas. Jis pradeda skaudėti dideliu mastu, dviem jau aprašytais būdais: šakninis masyvas tampa vienu dideliu objektu, kurį reikia pilnai analizuoti kiekvieną kartą atidarant failą ir šokant per puslapius, o kiekvienas struktūrinis redagavimas jį perrašo ištisai. Ko suplokštinimas nesunaikina — tai bendrinimo per netiesiogines nuorodas: plokščias medis, kuriame visi 10 000 puslapių rodo į tą patį /Resources žodyno objektą, vis tiek išlieka be dubliavimo. Prarandama tik galimybė nepalikti įrašo puslapyje ir leisti jį pateikti protėviui

Kai /Count meluoja

/Count yra grynoji apskaita: jis turi būti lygus lapo puslapių skaičiui mazgo pomedyje, ir niekas failo formate to neužtikrina. Du pažeidimo šablonai paaiškina daugumą realiame pasaulyje pasitaikančių melagingų skaičių

Pirmasis — pasenęs skaičius, paliktas po dalinio atnaujinimo. Redaktorius įterpia puslapį, perrašo tiesioginį tėvą su nauju /Kids ir atnaujintu /Count, prideda abu prie failo — ir niekada nepaliečia protėvių:

% Originali redakcija
12 0 obj
<< /Type /Pages /Count 9 /Kids [13 0 R  14 0 R  15 0 R] >>
endobj

14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 3
   /Kids [50 0 R  51 0 R  52 0 R] >>
endobj

% Pridėta redakcija: vienas puslapis įterptas į vidurinę šaką.
% Objektas 14 pakeičiamas; objektas 12 niekada neperrašomas
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
   /Kids [50 0 R  51 0 R  90 0 R  52 0 R] >>
endobj

Medis dabar turi dešimt lapų, bet šaknis vis dar rodo devynis. Peržiūros programa, pasitikinti šaknimi, savo puslapių skaitiklyje praneša devynis puslapius. Ta, kuri naudoja vidinius skaičius dvejetainei paieškai šokant per puslapius, kiekvienam puslapiui po įterpimo taško apskaičiuoja neteisingą indeksą. Pilnas apėjimas randa dešimt. Trys skirtingi atsakymai — vienas failas

Antrasis šablonas — skaičius, kuris negalėjo būti teisingas: neigiamas, lygus nuliui užpildytame mazge arba absurdiškai didelis. Jie atsiranda dėl fuzzing testavimo, perdavimo pažeidimų ir kartais dėl aritmetinių klaidų redaktoriuose. Jie ypač pavojingi kodui, kuris /Count naudoja paskirstymui: masyvo dydžio nustatymas pagal /Count reikšmę -3 geriausiu atveju sukelia diapazono klaidą, o darant tą patį su /Count reikšme du milijardai — tai atminties išeikvojimo (denial-of-service) paskirstymas. Ši reikšmė yra nepatikima įvestis, kaip ir bet kuris kitas skaičius faile

Analizatoriai dėl viso to skyla į dvi stovyklas. Griežti vartotojai — parengiamosios patikros įrankiai, PDF/A validatoriai, archyvavimo konvejeriai — palygina /Count su apėjimo rezultatu ir atmeta arba pažymi failą. Interaktyvios peržiūros programos beveik visada tolerantiškos: jos apeina medį, apskaičiuoja tikrą skaičių ir tyliai ignoruoja saugomą reikšmę — būtent dėl to failas su pasenusiu skaičiumi gali cirkuliuoti metų metus be jokių skundų, kol nepasiekia griežtesnio analizatoriaus kokioje nors automatizuotoje darbo eigoje. Gynybinis vidurio kelias bibliotekos kodui — laikyti /Count užuomina: naudinga iš anksto paskirstant atmintį ir, patikrinus, praleidžiant pomedžius, — tiesos šaltiniu paliekant apėjimą

Patį apėjimo algoritmą, paveldėjimo paieškos taisykles ir ėjimą nuo katalogo iki lapo rasite pradedant nuo puslapių tvarkos aiškinamojo straipsnio. Kaip šie gedimo režimai atrodo, kai realus kliento dokumentas pasiekia gamybinį kodą, skaitykite puslapių tvarkos derinimo atvejo analizėje, kurioje sekamas sumaišytų puslapių incidentas nuo simptomo iki pagrindinės priežasties

HotPDF Delphi komponentas visa tai tvarko viduje: apeina bet kokio gylio įdėtus medžius, išsprendžia paveldimus atributus kopijuojant ar perkeliant puslapius ir patikrina /Count pagal faktinį lapų skaičių vietoj to, kad juo pasitikėtų, todėl puslapių indeksai jo API visada reiškia loginius puslapius