PDF Sayfa Ağaçları: Sayfa Sırası, Fan-Out ve /Count

1 numaralı nesne, 1. sayfa değildir. Bu tek gerçek, PDF işleme kodunu biçimin öteki hiçbir parçasından çok yanıltır ve nedeni ancak görüntüleyicinin ne çizdiğine bakmayı bırakıp görüntüleyicinin gerçekte okuduğu nesne grafiğine bakmaya başlayınca ortaya çıkar

Bir PDF dosyası, numaralı dolaylı nesnelerin bir koleksiyonudur. Her biri bir nesne numarası ve bir üretim numarası taşır; öteki nesneler ona N G R yazılan bir başvuruyla işaret eder — 3 0 R, 3 nesnesinin geçerli sürümü demektir. Sayfalar da öteki nesneler gibidir ama dosyada nerede durduğu ve hangi numaraları taşıdığı, görüntüleme sırası hakkında hiçbir şey söylemez. Sıra /Pages ağacından gelir. Nesneleri numara sırasına göre tarayan kod, gerçek dünyadaki dosyaların epey bir bölümü için sayfaları yanlış sırada birleştirir

Ağaç, aynı zamanda daha az belirgin pek çok davranışın da yaşadığı yerdir. Biçimi, bir görüntüleyicinin 8.214. sayfaya ne kadar hızlı atlayabileceğine karar verir; iç düğümleri sayfa boyutunu ve fontları sessizce altındaki yapraklara devreder ve bütün yapıyı hızlı kılan /Count toplamlarını hiçbir şey zorunlu kılmaz. Üçünü de ele alacağız; önce sıranın kendisiyle

Sırayı sayfa ağacı belirler

Her PDF'in bir belge kataloğu vardır (ISO 32000-2 §7.7.2) ve kataloğun /Pages girdisi, sayfa ağacının kök düğümünü işaret eder. O kök, /Type /Pages taşıyan, dolaylı başvurulardan oluşan bir /Kids dizisi tutan ve altındaki yaprak sayfası sayısını veren bir /Count taşıyan bir sözlüktür. Görüntüleme sırası, o ağacın derinlik öncelikli, soldan sağa bir gezinimidir. Kuralın tamamı budur

Üç sayfalık asgari bir dosya bunu somutlaştırır:

%PDF-1.7

1 0 obj
<< /Type /Catalog /Pages 2 0 R >>
endobj

2 0 obj
<< /Type /Pages /Kids [20 0 R  4 0 R  9 0 R] /Count 3 >>
endobj

% 4 nesnesi dosyada üçüncü saklanır ama görüntüleme sırasında 2. sayfadır
4 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
   /Contents 5 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj

% 9 nesnesi dördüncü saklanır ama 3. sayfadır
9 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
   /Contents 10 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj

% 20 nesnesi en son saklanır ama 1. sayfadır; karar veren Kids[0]'dır, nesne numarası değil
20 0 obj
<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792]
   /Contents 21 0 R /Resources << /Font << /F1 6 0 R >> >> >>
endobj

/Kids dizisi [20 0 R 4 0 R 9 0 R] okur; dolayısıyla 20 nesnesi 1. sayfa, 4 nesnesi 2. sayfa ve 9 nesnesi 3. sayfadır. Nesneleri sayısal sırada gezip /Type /Page olanları toplayan kod bu dosyayı yanlış okur. Daha kötüsü, çıktı hâlâ inandırıcı görünür: sayfa sayısı doğru, her sayfada tanınabilir içerik var, sıra yanlış

Üreteçler bu tür düzenleri sıradan nedenlerle üretir. Tüm sayfalar için baştan nesne numarası ayıran bir kütüphane, onları oluşturma sırasına göre numaralandırır, sonra baytları serileştiricisinin uygun gördüğü sırada yazar. Bir birleştirme aracı, çakışmaları önlemek için her kaynak belgenin nesnelerini yeniden numaralandırır; sayfa nesneleri birleşik nesne tablosuna dağınık düşer, yeni kökün /Kids dizisi ise doğru sırayı taşır. Ve artımlı güncellemeler yeni nesneleri dosyanın sonuna yeni numaralarla ekler; böylece bir revizyonda eklenen sayfa, 1. konuma ait olsa bile bayt akışının sonuna yakın yaşar

Isıran durum sonuncusudur. Tek bir araçla üretilmiş bir test korpusu tamamen geçebilir; sonra bir birleştirme akışından çıkan dosyalar ya da birkaç revizyondan geçmiş belgeler karışmış çıkar. Sezgisel düzeltmeler tutmaz, çünkü başarısızlık üretece ve dosyanın düzenleme geçmişine bağlıdır. Gerçek düzeltme kısadır: katalogdan başlayın, /Pages'i çözün, /Kids'i özyinelemeli gezin ve yaprakları karşılaştığınız sırada yayın. Sayfa sırası hata ayıklama vaka çalışmamız, tam da bu belirtiyi bir yanlış teşhisten kök nedene kadar izler; özyinelemeli gezinim kodu ve sonucu kontrol etmek için qpdf adımlarıyla birlikte

Fan-out bir performans kararıdır

Spesifikasyon iki biçime izin verir. Basit üreteçler düz bir ağaç yayar: tek bir kök /Pages düğümü; onun /Kids dizisi /Page yapraklarından başka bir şey tutmaz. Hiçbir şey bir yazıcıyı iç içe geçmeye zorlamaz; tek bir dizide 10.000 yaprak başvurusu taşıyan 10.000 sayfalık bir belge uyumludur. PDF Reference yine de büyük belgeler için dengeli bir ağaç önerir ve ana akım üreteçler ölçülü bir fan-out'la o tavsiyeye uyar — tipik olarak ara düğüm başına bir düzine düğüm dolusu; her ara düğümün kendi /Kids'i ve kendi /Count'u vardır

Nedeni, bir görüntüleyicinin bir şey gösterebilmeden önce okumak zorunda olduğu şeydir. O 10.000 sayfalık dosyada doğrudan 8.214. sayfaya bir atlama alın. Düz ağaçta görüntüleyici önce kökü ayrıştırmak zorundadır ve kök tek bir dev dizidir: dolaylı başvuru başına kabaca sekiz baytla, 8.213. girdi çözülmeden baştan sona simgeleştirilmesi gereken 80 KB'lik bir nesne. Fan-out'u 32 olan dengeli bir ağaçta aynı atlama kökü okur, doğru çocuğu seçmek için koşan /Count toplamlarını karşılaştırır ve iner. Üç dört küçük sözlük, her biri birkaç yüz bayt. O O(log n) rastgele erişim, ağacın tasarlandığı şeydir ve /Count'un ara düğümlerde var olmasının bütün nedeni de budur — bir okuyucu, içindeki tek bir nesneyi açmadan bütün bir alt ağacı atlayabilir

Ağaç biçimi aynı zamanda düzenleme maliyetini belirler. Bir sayfa ekleyen artımlı güncelleme, /Kids'i ya da /Count'u değişen her düğümü yeniden yazmak zorundadır; bu da yeni yaprağın ebeveynden köke giden yoludur. Dengeli ağaçta o yol, dosyaya eklenen bir avuç küçük sözlüktür. Düz ağaçta "yol", dev kök dizisinin ta kendisidir ve her revizyonda tamamen kopyalanır. Otuz gözden geçirme ve not ekleme turundan geçen bir sözleşme, bayt akışında aynı 80 KB'lik dizinin otuz eskimiş kopyasını taşıyabilir

İşleme kodu için iç içelik daha sert bir sonuç doğurur. /Kids'in ilk düzeyinin sayfalar içerdiğini varsayamazsınız; her çocuk kontrol edilmelidir: /Type /Pages ise iç içe gir, /Type /Page ise yaprak. İlk düzeyde duran kod, karşılaştığı her düz dosyada çalışır ve bir üreteç ilk kez iç içe karar verdiğinde bütün alt ağaçları sessizce düşürür

İç düğümler kalıtsal öznitelikler taşır

Ara düğümler aramaları yönlendirmekten fazlasını yapar. Dört sayfa özniteliği kalıtsaldır (ISO 32000-2 §7.7.3.4): /Resources, /MediaBox, /CropBox ve /Rotate. Herhangi biri bir /Pages düğümünde durabilir; orada altındaki her yaprağa uygulanır, ta ki bir soyundan geleni geçersiz kılana dek. Yatay ekli bir rapor üreten yazıcı, o düzeni ağacın kendisinde ifade edebilir:

5 0 obj   % belge kökü
<< /Type /Pages /Count 6 /Kids [6 0 R  7 0 R] >>
endobj

6 0 obj   % rapor gövdesi: dikey A4, gövde fontu
<< /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   % ek: yatay A4, döndürülmüş, kendi fontu
<< /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  % ek sayfası: boyutu, döndürmeyi ve fontları kalıtır
<< /Type /Page /Parent 7 0 R /Contents 43 0 R >>
endobj

40'tan 42'ye kadar olan nesneler neredeyse boştur. Sayfa boyutu, döndürme ve font kaynaklarının hepsi 7 düğümünden gelir; bu, dosyayı kompakt ve kendi kendini idame ettiren tutar: ek düğümünün altına dördüncü bir sayfa ekleyin ve kimse dokunmadan yatay çıkar

Bu aynı zamanda bir sayfanın özelliklerinin tamamının sayfanın üzerinde olmadığı anlamına gelir. 40 nesnesinde /MediaBox anahtarı yoktur ve bu tamamen yasaldır — eksik anahtarı bozuk girdi sayan bir okuyucu, geçerli dosyaları reddeder. Arama, girdiyi bulana ya da köke ulaşana dek /Parent zincirini yukarı gezmek zorundadır. O gezinmenin bir döngü koruması gerekir. Bozuk bir dosya, hâlâ ziyaret edilmiş bir düğüme geri işaret eden bir /Parent başvurusu taşıyabilir ve ziyaret edilmiş nesneler kümesi olmadan arama sonsuza dek döner

Aynı mekanizma klasik sayfa taşıma tehlikesini yaratır. Bir aracın, 40 nesnesini iki /Kids dizisini düzenleyip /Parent'ı 6 düğümüne çevirerek rapor gövdesine taşıdığını söyleyin. Taşıma yapısal olarak geçerlidir; ama 40 nesnesi artık dikey /MediaBox'ı, döndürmesizliği ve /F1 fontunu kalıtır — içerik akışı hâlâ /F2 seçerken, o artık çözülmez. Sayfa tek bir düzenlemede küçülür, döndürmesi gider ve metnini kaybeder. Sağlam yeniden sıralama kodu, sayfayı yeni ebeveyne bağlamadan önce dört kalıtsal özniteliğin çözülmüş değerlerini sayfa sözlüğüne yazar. Bir düzenleyicide bir sayfayı sürükleyip boyutunun ya da yönünün değiştiğini izlediyseniz, gördüğünüz mekanizma buydu

Düzleştirme: yasal, yaygın, ara sıra maliyetli

Pek çok araç ters yönde gider. Asgari yazıcılar, basit olduğu için tek düzeyli bir ağaç yayar; pek çok birleştirme ve bölme aracı da okuduğu ağacı tek bir düz /Kids dizisine yeniden kurar, çünkü dengeli çıktı ek iş gerektirir ve düz çıktı her zaman uyumludur. Doğru bir yeniden kurulum, kalıtımı aynı anda çözmek zorundadır. Bir yaprağın kalıttığı her öznitelik ya yaprağın üzerine kopyalanmalı ya da belge boyunca tek düzeyliyse yeni köke yükseltilmelidir; o adımı atlayın ve çıktı, geometriyi tam olarak sayfa taşıma olayındaki gibi değiştirir

Tipik belgeler için düzleştirme zararsızdır. Ölçekte zarar verir, zaten anlatılan iki yolla: kök dizisi, her açılışta ve her sayfa atlamasında tam olarak ayrıştırılan tek bir büyük nesneye dönüşür ve her yapısal düzenleme onu baştan yazar. Düzleştirmenin yok etmediği şey, dolaylı başvurularla paylaşım aynı kalmaktadır. 10.000 sayfanın tamamı aynı /Resources sözlük nesnesini işaret ettiğinde düz ağaç hâlâ tekilleştirilmiştir — kaybedilen tek şey, girdiyi sayfada bırakmama ve bir atasına tedarik ettirme seçeneğidir

/Count yalan söylediğinde

/Count saf defter tutmadır. Düğümün alt ağacındaki yaprak sayfası sayısına eşit olmalıdır ve dosya biçimi bunu zorunlu kılmaz. Vahşi doğada görülen yalancı sayımların çoğunu iki bozulma deseni açıklar

İlki, artımlı bir güncellemenin geride bıraktığı bayat sayımdır. Bir düzenleyici bir sayfa ekler, yakın ebeveyni yeni bir /Kids ve güncellenmiş bir /Count ile yeniden yazar, ikisini de dosyaya ekler — ve atalara hiç dokunmaz:

% Özgün sürüm
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

% Eklenen sürüm: orta dala bir sayfa yerleştirildi.
% 14 nesnesi geçersiz kılındı; 12 nesnesi hiç yeniden yazılmadı
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

Ağaç artık on yaprak tutar ama kök hâlâ dokuz der. Köke güvenen bir görüntüleyici, sayfa sayacında dokuz gösterir. İç sayımları kullanarak bir sayfa atlamasını ikili aramayla hesaplayan biri, ekleme noktasından sonraki her sayfa için yanlış indeks bulur. Tam bir gezinim onu bulur. Tek dosya, üç farklı yanıt

Aynı dosyadan ısırmanın daha sessiz bir yolu daha vardır. Kök sayımını okuyan, ağacı gezmeye başlayan ve o kadar sayfa topladığında duran kod, onuncu sayfayı asla görmez. İstisna yok, uyarı yok; yalnızca bir sayfa eksik bir belge. /Count'u döngü sınırı ya da sınır kontrolü olarak kullanmak hatadır; gezinim, kayıtlı sayı ne derse desin, ağaç tükenene kadar çalışmalıdır

İkinci desen, asla doğru olamayacak sayımdır: negatif, dolu bir düğümde sıfır ya da absürt biçimde devasa. Bunlar fuzzing'den, aktarım hasarından ve ara sıra düzenleyicilerdeki aritmetik hatalardan gelir. Tehlikeli oldukları yer, özellikle /Count'a güvenerek bellek ayıran koddur. -3'lük bir /Count'tan dizi boyutlandırmak en iyi ihtimalle aralık hatası fırlatır; iki milyarlık bir /Count'tan yapmak, hizmet reddi ayırmasıdır. Değere, dosyadaki öteki her sayı gibi, güvenilmeyen girdi muamelesi yapın

Ayrıştırıcılar tüm bunlar üzerinde iki kampa ayrılır. Katı tüketiciler — preflight araçları, PDF/A doğrulayıcıları, arşivleme hatları — /Count'u gezinim sonucuyla karşılaştırır ve dosyayı reddeder ya da işaretler. Etkileşimli görüntüleyiciler neredeyse evrensel olarak esnektir: gezinirler, gerçek sayımı türetirler ve kayıtlı olanı sessizce yok sayarlar; bayat sayımlı bir dosyanın, otomatik bir iş akışının içinde daha katı bir ayrıştırıcıya rastlayana dek yıllarca şikâyetsiz dolaşabilmesinin nedeni tam olarak budur. Kütüphane kodu için bize göre doğru varsayılan orta yoldur: /Count'u ön ayırma için bir ipucu, doğrulandıktan sonra da alt ağaç atlama için kullanın ve gerçeğin kaynağını gezinimde bırakın

Üretimde bu başarısızlıklar kendini nadiren ağaç sorunu olarak ilan eder. Karışmış sayfalar, bir birleştirmenin sonunda eksik bir sayfa ya da yeniden sıralamadan sonra boyutu ya da yönü değişen bir sayfa olarak görünürler. Hata ayıklama vaka çalışması böyle bir raporu ağaç üzerinden geriye izler. Çevredeki dosya anatomisi (nesneler, çapraz başvuru verisi, trailer'lar) için PDF dosya yapısı genel bakışı başlangıç yeridir

HotPDF Delphi Component, bütün bunları kendi içinde halleder: istenen derinlikteki iç içe ağaçları gezer, sayfalar kopyalanırken ya da taşınırken kalıtsal öznitelikleri çözer ve /Count'a güvenmek yerine onu gerçek yaprak sayısıyla karşılaştırır; böylece API'sindeki sayfa indeksleri her zaman mantıksal sayfalar demektir