Rinnakkainen artikkelimme (companion explainer on) PDF-sivujärjestyksestä (PDF page ordering) kattaa (covers the) perussäännön (ground rule: display order comes from a): näyttöjärjestys tulee syvyys (display order comes from a depth-first) ensin, vasemmalta (left-to-right walk of the) oikealle -läpikulusta (left-to-right walk of the) /Pages -puun /Kids-taulukoille (arrays in the), ei koskaan (never from) objektinumeroista (object numbers). Tämä (This) artikkeli (article looks at the) tarkastelee (looks at the) puuta (tree from a) toisesta (different angle — its) näkökulmasta (angle — its) — sen muodosta (its shape). Miksi kypsät (Why do mature PDF writers emit) PDF-kirjoittajat tuottavat (writers emit) hierarkioita (hierarchies of) väli- (intermediate) /Pages-solmuista (nodes when a single flat array would be perfectly), kun yksittäinen litteä taulukko (single flat array would be perfectly) olisi täysin laillinen (would be perfectly legal)? Mikä (What actually changes when a) todella (actually changes when a) muuttuu, kun (changes when a) työkalu (tool flattens or rebuilds the) litistää (flattens or rebuilds the) tai (or rebuilds the) rakentaa (rebuilds the) puun (tree) uudelleen (rebuilds the)? Ja (And what happens when the) mitä (what happens when the) tapahtuu, kun /Count-kirjanpito, joka tekee koko (that makes the whole) rakenteesta (structure fast stops telling the) nopean (fast stops telling the), lakkaa (stops telling the) kertomasta (telling the) totuutta (truth)
Haarautuminen on suorituskykypäätös (performance decision)
Mikään ei pakota (Nothing forces a writer to nest) kirjoittajaa muodostamaan sisäkkäisyyksiä (nest). 10 000-sivuinen asiakirja, jossa (document with one root) on (with one root) yksi (one root) /Pages-juurisolmu ja 10 000 lehtiviittausta (leaf references in a single) yhdessä (single) /Kids-taulukossa, on määritysten (conforms to the spec) mukainen (conforms to the). PDF-viite (Reference nevertheless recommends a balanced tree for) suosittelee (recommends a balanced tree for) kuitenkin (nevertheless) tasapainoista (balanced tree for) puuta suurille asiakirjoille, ja (and) valtavirran generaattorit noudattavat (mainstream generators follow that) tuota (that) neuvoa (advice with a) vaatimattomalla haarautumisella (modest fan-out, typically a few), tyypillisesti (typically a few dozen) muutamalla kymmenellä lapsella (dozen kids per intermediate) välisolmua (intermediate node) kohden
Syy tähän on se (reason is what a viewer must read before it can show anything), mitä katseluohjelman on luettava, ennen kuin (before it can show anything) se voi (it can show anything) näyttää mitään (anything). Kuvitellaanpa suoraa (Consider a jump straight to page) hyppyä (jump straight to page) tuon (that) 10 000-sivuisen tiedoston sivulle 8 214. Litteällä (flat) puulla katseluohjelman (viewer first has to) on (has to) ensin jäsennettävä (parse the) juurisolmu, ja (and) tuo (that) juurisolmu on (root node is) yksi valtava (enormous) taulukko: karkeasti (roughly) kahdeksan (eight bytes per) tavua epäsuoraa viittausta (indirect reference, an) kohden tarkoittaa 80 kt:n (KB) objektia (object that must be tokenized end to end before entry), joka on tokenisoitava alusta (must be tokenized end to end before entry) loppuun (end to end before entry), ennen (before entry) kuin merkintä (entry) 8 213 voidaan ratkaista (resolved). Tasapainoisessa puussa, jonka (balanced tree of) haarautuminen (fan-out) on (is) 32, sama (same) hyppy (jump reads the root, compares running) lukee juuren (root, compares running), vertailee (compares running) /Count-kokonaissummia (totals to pick the) valitakseen (pick the) oikean (correct) lapsen (child, and descends — three or four small) ja laskeutuu (descends — three or four small) alaspäin — kaikkiaan (in total, each a few) kolme (three) tai neljä (four) pientä sanakirjaa (small dictionaries in total, each a few), joista kukin (each a few) on (a few) muutaman (few hundred bytes) sadan (hundred bytes) tavun (bytes) kokoinen. Tuo (That is the O(log) on (is the O(log) se O(log n) -satunnaissaanti (random access the), jota (the tree was designed to) puu (tree was designed to) suunniteltiin tarjoamaan (was designed to provide, and it), ja (and it is the) se (it is the) on (is the) koko (entire) syy siihen, miksi (reason) /Count on olemassa (exists on) välisolmuissa (intermediate nodes: it lets a reader skip a whole): se antaa lukijan ohittaa (lets a reader skip a whole) kokonaisen (whole) alipuun avaamatta ainuttakaan (without opening a single) sen (it) sisällä (inside it) olevaa (single object inside) objektia (object inside)
Puun muoto asettaa myös muokkauskustannukset (cost of editing). Inkrementaalisen päivityksen, joka (incremental update that) lisää (inserts one) yhden (one) sivun (page must rewrite every node whose), on (must rewrite every node whose) kirjoitettava uudelleen (rewrite every node whose) jokainen (every) solmu (node whose), jonka (whose) /Kids tai /Count muuttui (changed, meaning the), mikä tarkoittaa (meaning the) polkua uuden lehden isännästä ylös juureen (path from the new leaf's parent up to the root). Tasapainoisessa puussa (balanced tree that) tuo (that) polku on kourallinen tiedoston loppuun liitettyjä (handful of small dictionaries appended to the) pieniä sanakirjoja (small dictionaries appended to the). Litteässä puussa (flat tree the) "polku" (path" is the single giant root array, duplicated in full on every revision) on yksittäinen jättimäinen juuritaulukko (single giant root array, duplicated in full on every revision), joka (duplicated in full on every revision) monistetaan (duplicated in full on every revision) kokonaisuudessaan jokaiseen versioon (in full on every revision). Sopimus (contract that goes through thirty review-and-annotate cycles can end up hauling thirty), joka käy läpi kolmekymmentä arvostelu- (thirty review-and-annotate cycles can end up hauling thirty) ja huomautuskierrosta, voi päätyä (can end up hauling thirty superseded) raahaamaan tavuvirrassa (hauling thirty superseded copies of the same) mukanaan kolmeakymmentä (thirty) korvattua koodia (superseded copies of the same) samasta 80 kt:n taulukosta (array in its)
Sisäiset (Interior nodes carry) solmut (nodes carry) kantavat perittyjä (inherited) attribuutteja (attributes)
Välisolmut (Intermediate nodes are not just routing) eivät (are not just) ole vain (just) reititystä varten (routing). Neljä perittävää sivuattribuuttia (four inheritable page attributes —) — /Resources, /MediaBox, /CropBox ja (and) /Rotate — voidaan nostaa (may be hoisted onto) mihin (any) tahansa (any) /Pages-solmuun (node, where they apply to every leaf beneath it unless a descendant overrides them), jossa (where they apply to every leaf beneath it unless a descendant overrides them) ne koskevat jokaista sen (every leaf beneath it unless a descendant overrides them) alapuolella (beneath it unless a descendant overrides them) olevaa lehteä (leaf beneath it unless a descendant overrides them), ellei (unless a descendant overrides them) jälkeläinen ohita (descendant overrides them) niitä (them). Kirjoittaja (writer producing a), joka (producing a) tuottaa raportin, jossa (report with a) on vaakasuuntainen liite (landscape appendix can), voi (can) ilmaista tuon (express that) asettelun itse puussa (layout in the tree itself):
5 0 obj % asiakirjan (document root) juuri (root)
<< /Type /Pages /Count 6 /Kids [6 0 R 7 0 R] >>
endobj
6 0 obj % raportin runko (report body: portrait A4, body font): pystysuuntainen (portrait) A4, runkofontti (body font)
<< /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 % liite (appendix: landscape A4, rotated, its own font): vaakasuuntainen (landscape) A4, kierretty (rotated), sen oma (its own) fontti (font)
<< /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 % liitesivu (appendix page: inherits size, rotation, fonts): perii koon (inherits size, rotation, fonts), kierron (rotation, fonts) ja (and) fontit (fonts)
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobjObjektit 40-42 (Objects 40 through 42 are nearly empty) ovat (are) lähes (nearly) tyhjiä (empty). Niiden (Their page size, rotation, and) sivukoko, kierto (rotation, and) ja (and) fonttiresurssit (font resources all arrive by inheritance from) saapuvat kaikki perintönä (all arrive by inheritance from) solmulta 7, mikä pitää (which keeps the) tiedoston (file compact and) kompaktina ja itseään ylläpitävänä (self-maintaining: add a): lisää (add a) neljäs (fourth) sivu (page under the) liitesolmun (appendix node and) alle, ja se tulostuu (it comes out) vaakasuuntaisena automaattisesti (landscape automatically)
Sama (The same mechanism creates the) mekanismi (mechanism creates the) luo klassisen (classic) sivu-siirron (page-move) vaaran (hazard). Oletetaan (Suppose a), että (that) työkalu (tool moves object 40 into the) siirtää objektin (object 40 into the) 40 raportin runkoon (report body by) muokkaamalla kahta /Kids-taulukkoa ja (arrays and) osoittamalla /Parent-arvon (repointing) uudelleen solmuun (node 6) 6. Siirto on (The move is structurally) rakenteellisesti kelvollinen (structurally valid, yet), mutta silti (yet) objekti (object 40 now) 40 perii nyt pystysuuntaisen (inherits the portrait) /MediaBox-arvon, ei kiertoa (no rotation, and), ja fontin /F1 — vaikka sen (while its) sisältövirta valitsee (content stream still selects) edelleen arvon (still selects) /F2, jota (which no longer resolves) ei enää (no longer resolves) pystytä ratkaisemaan (resolves). Sivu kutistuu (page shrinks, un-rotates, and), purkautuu (un-rotates, and) kierrosta, ja kadottaa (loses its) tekstinsä yhdessä (single edit) muokkauksessa (edit). Vankka (Robust reordering code therefore) uudelleenjärjestelykoodi realisoikin (reordering code therefore materializes the) siksi kaikkien neljän (all four) perittävän attribuutin (inheritable attributes onto the) ratkaistut (resolved values of) arvot sivusanakirjaan (page dictionary before) ennen (before) sivun uudelleenisännöintiä (reparenting it). Jos olet (If you have ever dragged a page in an) koskaan (ever) vetänyt (dragged a page in an) sivua (page in an) editorissa ja seurannut sen (watched it change size or) muuttavan kokoa tai (or) suuntaa (orientation, this is the), tämä (this is the) on se mekanismi, jonka (mechanism you) näit (witnessed)
Litistäminen (Flattening: legal, common, occasionally expensive): laillista (legal), yleistä (common), ajoittain (occasionally) kallista (expensive)
Useat työkalut kulkevat (go the) toiseen (other way) suuntaan (way). Minimaaliset kirjoittajat tuottavat (writers emit a) yksitasoisen puun (single-level tree because it is simple, and), koska (because it is simple, and) se on (it is) yksinkertaista (simple, and), ja monet (and many) yhdistämis- ja (merge and) jakotyökalut rakentavat uudelleen lukemansa puun (rebuild whatever tree they read into one) yhdeksi (one) litteäksi (flat) /Kids-taulukoksi, koska tasapainoisen rakenteen luominen on (generating balanced structure is) ylimääräistä (extra) työtä (work and) ja (and) litteä tuloste on aina (flat output is always) määritysten mukainen (conforming). Oikean (A correct rebuild must) uudelleenrakentamisen (rebuild must) on ratkaistava (must resolve inheritance at the) perintä (inheritance at the) samalla (same time: every): jokainen attribuutti (every attribute a), jonka lehti (leaf was inheriting has to) peri, on (has to) kopioitava (be copied onto the) lehteen (leaf, or) tai (or) nostettava (hoisted to the) uuteen (new) juureen (root if it is), jos (if it is) se on (it is) yhdenmukainen (uniform across the) koko asiakirjassa (across the document — otherwise the) — muuten tulosteen (output changes geometry exactly the) geometria (geometry exactly the) muuttuu aivan samalla tavalla kuin (way the page-move case does) sivunsiirtotapauksessa (page-move case does)
Tyypillisille (For typical documents flattening is) asiakirjoille (documents flattening is) litistäminen on vaaratonta (harmless). Se satuttaa skaalautuessa (hurts at scale, in the) kahdella jo (two ways already) kuvatulla tavalla: juuritaulukosta (root array becomes one) tulee yksi suuri objekti, joka (large object that every) jokaisen (every) avaus- ja (open and) sivuhyppytapahtuman (every page jump must parse in) on (must parse in) jäsennettävä kokonaisuudessaan (full, and every), ja (and every) jokainen (every) rakenteellinen muokkaus (structural edit rewrites it) kirjoittaa sen (it) kokonaan (whole) uudelleen (rewrites it). Mitä (What flattening does not destroy is) litistäminen ei tuhoa, on (destroy is) jakaminen epäsuorien (sharing through indirect) viittausten (references — a) kautta (through) — litteä (flat) puu, jossa kaikki (tree in which all) 10 000 sivua osoittavat (pages point at the) samaan /Resources-sanakirjaobjektiin (dictionary object is still), on (is still) edelleen (still) deduplikoitu (deduplicated). Ainoastaan (What is lost is only the) menetettävä (lost is only the) asia (option to leave the) on (is only the) mahdollisuus jättää merkintä (option to leave the entry off the) pois sivulta (page and) ja (and) antaa (let an) esi-isän tarjota (ancestor supply it) se (it)
Kun (When /Count lies) /Count valehtelee (lies)
/Count on (is pure bookkeeping: it must equal the) puhdasta kirjanpitoa (pure bookkeeping: it must equal the): sen on oltava yhtä suuri (must equal the) kuin (equal the) solmun alipuun lehtisivujen määrä (number of leaf pages in the node's subtree, and), eikä (and nothing) mikään (nothing in the) tiedostomuodossa valvo (file format enforces that) sitä (that). Kaksi korruptiokuviota aiheuttaa (Two corruption patterns account for most of the) suurimman osan luonnossa nähdyistä valehtelevista (lying counts seen in the) laskuista (counts seen in the wild)
Ensimmäinen on inkrementaalisen (The first is the stale count left behind by an incremental) päivityksen taakseen jättämä vanhentunut (stale) arvo (count left behind by an incremental update). Editori lisää (editor inserts a) sivun (page, rewrites the), kirjoittaa välittömän isännän uudelleen (rewrites the immediate parent with a) uudella (new) /Kids-taulukolla (Kids and an) ja (and an) päivitetyllä (updated) /Count-arvolla, liittää (appends both to the) molemmat tiedostoon (file — and) — eikä koskaan koske esi-isiin (never touches the ancestors):
% Alkuperäinen (Original revision) versio (revision)
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
% Liitetty versio (Appended revision: one): yksi sivu (page inserted into the) lisätty keskimmäiseen (middle) haaraan (branch).
% Objekti (Object 14 is) 14 korvataan (is superseded; object); objektia 12 ei (12 is never) koskaan kirjoiteta uudelleen (never rewritten)
14 0 obj
<< /Type /Pages /Parent 12 0 R /Count 4
/Kids [50 0 R 51 0 R 90 0 R 52 0 R] >>
endobjPuu (tree now holds ten) pitää nyt (holds ten) sisällään kymmenen (ten) lehteä (leaves, but the), mutta (but the) juuri (root still says) sanoo edelleen (still says) yhdeksän (nine). Katseluohjelma, joka luottaa (viewer that trusts the) juureen (root reports nine), ilmoittaa yhdeksän sivua (reports nine pages in its) sivulaskurissaan (page counter). Ohjelma, joka käyttää sisäisiä laskuja (interior counts to) binäärihaun sivuhyppyyn (binary-search a page jump computes a), laskee väärän indeksin (wrong index for every) jokaiselle (every) lisäyskohdan (insertion) jälkeiselle sivulle (page after the insertion point). Täysi läpikäynti löytää (full traversal finds ten) kymmenen (ten). Kolme (Three) eri (different) vastausta, yksi tiedosto (file)
Toinen kuvio (The second pattern is the) on lasku, joka ei koskaan (count that could never) voisi olla (be right: negative, zero) oikein (right: negative, zero): negatiivinen (negative, zero on a), nolla (zero on a) asutetussa (populated) solmussa (node, or), tai (or) absurdin valtava (absurdly huge). Nämä johtuvat sumennuksesta (These come from fuzzing, from), siirtovaurioista (transmission damage, and) ja (and) satunnaisesti editorien (occasionally from arithmetic bugs in) aritmeettisista bugeista (arithmetic bugs in editors). Ne (They are dangerous specifically to) ovat (are dangerous specifically to) vaarallisia erityisesti (dangerous specifically to) koodille, joka luottaa (code that trusts) /Count-arvoon allokoinnissa (Count for allocation — sizing an) — taulukon mitoittaminen (sizing an array from a) -3:n (Count of -3 raises a) /Count-arvosta nostaa parhaimmillaan (raises a range error at) aluevirheen (range error at best, and), ja sen (and doing so from a) tekeminen kahden miljardin (Count of two billion is a) /Count-arvosta on (is a denial-of-service) palvelunestohyökkäys (denial-of-service allocation). Arvo on epäluotettavaa syötettä (value is untrusted input, like), kuten (like) kaikki (every) muutkin (other) tiedoston (file) numerot (number in the)
Jäsentimet jakautuvat kahteen (Parsers split into two) leiriin kaiken tämän (camps over all of) suhteen (this). Tiukat kuluttajat (Strict consumers — preflight) — esitarkastustyökalut (preflight tools, PDF/A), PDF/A-validaattorit (validators, archival), arkistointiputket (archival pipelines — compare) — vertaavat (compare) /Count-arvoa läpikäyntitulokseen (traversal result and) ja (and) hylkäävät tiedoston (reject or flag the file) tai (or flag the file) merkitsevät (flag the file) sen (file). Interaktiiviset (Interactive viewers are almost universally) katseluohjelmat (viewers are almost universally) ovat (are almost universally) lähes poikkeuksetta (almost universally) lempeitä (lenient: they): ne tekevät läpikäynnin (they traverse, derive the), johtavat todellisen (derive the real count, and) määrän (count, and) ja jättävät (and silently ignore the) tallennetun äänettömästi (silently ignore the stored one, which) huomiotta (ignore the stored one, which), mikä on täsmälleen (exactly) se (is exactly why a) syy, miksi (why a) vanhentuneella (stale-count file can) laskulla (count file can) varustettu tiedosto (file can circulate for) voi (can) kiertää vuosia (years without) ilman (without) valituksia (complaint until it), kunnes se (until it meets a stricter) kohtaa jonkin automaattisen työnkulun sisällä (parser inside some automated workflow) tiukemman jäsentimen (stricter parser inside some automated workflow). Puolustava (defensive) keskitie (middle ground for) kirjastokoodille on käsitellä (library code is to treat) /Count-arvoa (Count as a hint — useful) vihjeenä (hint — useful) — hyödyllisenä (useful for preallocation, and) ennakkoallokointiin (preallocation, and) ja (and) alipuun (subtree) ohittamiseen (skipping once verified — while) sen (once) jälkeen kun (once verified — while) se on varmennettu (verified — while) — samalla (while letting) antaen (letting traversal remain the) läpikäynnin (traversal remain the) pysyä (remain the) totuuden lähteenä (source of truth)
Itse läpikäyntialgoritmiin, (For the traversal algorithm itself, the) perinnän hakusääntöihin ja hakemistosta (inheritance lookup rules, and the) lehteen -kävelyyn (catalog-to-leaf walk, start) liittyen, aloita (start with the) sivujärjestyksen selityksestä (page ordering explainer). Jos (For what) haluat (what these failure modes look like when a) nähdä (look like when a), miltä nämä (what these failure modes look like when a) epäonnistumistilat (failure modes look like when a) näyttävät, kun todellinen asiakasasiakirja (real customer document reaches production) saavuttaa tuotantokoodin (reaches production code, read the), lue (read the) sivujärjestyksen virheenkorjauksen (page-order debugging case study) tapaustutkimus (debugging case study), joka seuraa sivujen sekoittumistapausta (follows a shuffled-pages incident from) oireesta (symptom to) juurisyyhyn (root cause)
HotPDF Component käsittelee tämän kaiken (deals with all of this internally: it) sisäisesti: se käy läpi (it traverses nested) minkä tahansa (any) syvyiset (depth, resolves) sisäkkäiset (nested) puut (trees of), ratkaisee (resolves inherited) perityt (inherited attributes when) attribuutit (attributes when), kun (when pages are) sivuja kopioidaan (pages are copied or) tai (or) siirretään (moved, and), ja varmistaa (and verifies) /Count-arvon todellisia lehtimääriä (actual leaf counts instead of) vasten (against actual leaf counts instead of) luottamisen sijaan (trusting it, so), joten sivuindeksit sen sovellusliittymässä tarkoittavat aina loogisia sivuja (so page indices in its API always mean logical pages)