flpdf/linearization/hint_shared.rs
1//! Shared Object Hint Table data structure (ISO 32000-1 Annex F.3.2).
2//!
3//! qpdf correspondence: QPDF_linearization.cc shared-object hint planning split into a data module.
4//!
5//! This module builds the **data** for the Shared Object Hint Table. It does
6//! **not** encode the table as bits/bytes — that is the responsibility of the
7//! hint-stream encoder.
8//!
9//! # Structure overview (Annex F.3.2)
10//!
11//! The hint table consists of:
12//!
13//! * A **header** with 7 integer items describing the ranges and bit widths
14//! needed to encode the per-shared-object entries.
15//! * **S per-shared-object entries** (one per shared object).
16//!
17//! # Simplifications (relative to full Annex F.3.2)
18//!
19//! This implementation adopts the same simplifications used by qpdf:
20//!
21//! * **1-object-per-group model**: each shared object forms its own group.
22//! The invariant is represented only by each entry's
23//! `nobjects_minus_one = 0`; qpdf's `calculateHSharedObject` likewise emits
24//! `nbits_nobjects = 0` and does not serialize a separate group-entry
25//! section.
26//! * **Signature suppressed**: the per-object signature flag is always 0
27//! (signature computation, e.g. MD5, is not performed). When the flag is 0
28//! the 16-byte signature field is omitted from the encoded stream.
29//!
30//! # Back-patch discipline
31//!
32//! Several fields depend on byte offsets that are only known after the file
33//! has been written:
34//!
35//! | Field | Location | Placeholder |
36//! |-------|----------|-------------|
37//! | `header.location` (item 2) | header | `0` |
38//! | `header.least_length` (item 6) | header | `0` |
39//! | `entry.length_minus_least` (item 2) per object | entries | `0` |
40//!
41//! These fields are stored as `0` in the returned structs. The back-patcher
42//! locates them by field name and overwrites them once the real
43//! byte offsets are available.
44
45use super::plan::LinearizationPlan;
46use super::renumber::RenumberMap;
47use crate::ObjectRef;
48
49// ---------------------------------------------------------------------------
50// Header
51// ---------------------------------------------------------------------------
52
53/// Header for the Shared Object Hint Table (7 items per Annex F.3.2).
54///
55/// Items are numbered 1–7 in the spec; field names here follow the spec text.
56///
57/// ## Back-patch fields
58///
59/// * `location` (item 2): byte offset of the first object in the shared
60/// objects section. Set to `0` (placeholder); back-patched once the real offset is known.
61/// * `least_length` (item 6): minimum byte length of an object in the shared
62/// objects section. Set to `0` (placeholder); back-patched once the real offset is known.
63#[derive(Debug, Clone, PartialEq, Eq)]
64pub struct SharedObjectHeader {
65 /// Item 1 — Object number of the first object in the shared objects
66 /// section (i.e. the first new number assigned to a Part-3 object).
67 ///
68 /// `0` if there are no shared objects (degenerate case).
69 pub first_object_number: u32,
70
71 /// Item 2 — Byte offset of the first object in the shared objects section.
72 ///
73 /// **Placeholder: 0; back-patched once the real offset is known.**
74 pub location: u64,
75
76 /// Item 3 — Number of shared object entries for the first page
77 /// (= count of Part-3 objects whose `referencing_pages` includes page 0).
78 pub first_page_entries: u32,
79
80 /// Item 4 — Total number of shared object entries (= `plan.shared_hints.len()`).
81 pub section_entries: u32,
82
83 /// Item 5 — Bits used for each entry's `nobjects_minus_one` value
84 /// (`nbits_nobjects` in qpdf).
85 pub bits_group_object_count: u32,
86
87 /// Item 6 — Least byte length of an object in the shared objects section.
88 ///
89 /// **Placeholder: 0; back-patched once the real offset is known.**
90 pub least_length: u64,
91
92 /// Item 7 — Bits needed to represent the difference between the greatest
93 /// and least length of an object in the shared objects section (item 2 of
94 /// the per-shared-object entry).
95 ///
96 /// Since all lengths are 0 (placeholder) at this stage the delta is 0 and
97 /// bits = 0. The encoder must re-derive bit widths at encode time using
98 /// the final values after back-patching.
99 pub bits_length_delta: u32,
100}
101
102// ---------------------------------------------------------------------------
103// Per-shared-object entry
104// ---------------------------------------------------------------------------
105
106/// Per-shared-object entry for the Shared Object Hint Table (Annex F.3.2).
107///
108/// ## Back-patch fields
109///
110/// * `length_minus_least` (column 1): byte length of this object minus
111/// `header.least_length`. Set to `0` (placeholder); back-patched once
112/// the real offsets are known.
113/// * `nobjects_minus_one` (column 3): number of additional objects in this
114/// shared object's group, minus one. In our 1-object-per-group model this is
115/// always `0`; it is encoded with `bits_group_object_count` bits.
116#[derive(Debug, Clone, PartialEq, Eq)]
117pub struct SharedObjectEntry {
118 /// Column 1 — Byte length of this object minus
119 /// `header.least_length`. Populated by the writer in `from_plan`.
120 pub length_minus_least: u32,
121
122 /// Column 2 — Signature present flag.
123 ///
124 /// Always `false` in this implementation; signature computation (MD5) is
125 /// not performed. When `false`, the 16-byte signature is omitted from
126 /// the encoded stream.
127 pub signature_present: bool,
128
129 /// Inline after column 2 when `signature_present` is true — 16-byte MD5
130 /// signature of the object data.
131 ///
132 /// Always `None` because `signature_present` is always `false`.
133 pub signature: Option<[u8; 16]>,
134
135 /// Column 3 — Number of additional objects in this group, minus one. Our
136 /// writer always uses one object per group, so this is always `0`.
137 /// Encoded with `bits_group_object_count` bits.
138 pub nobjects_minus_one: u32,
139}
140
141// ---------------------------------------------------------------------------
142// SharedObjectHintTable
143// ---------------------------------------------------------------------------
144
145/// Complete Shared Object Hint Table: header plus one entry per shared object.
146///
147/// Constructed via [`SharedObjectHintTable::from_plan`]. All placeholder fields
148/// (`location`, `least_length`, and per-object `length_minus_least`) are
149/// initialized to `0`; the back-patcher fills them in once the real byte
150/// offsets are available.
151///
152/// The hint-stream encoder serializes this struct into the binary bit-packed
153/// format required by Annex F.
154///
155/// # Group model
156///
157/// This implementation uses the **1-object-per-group model**: each shared
158/// object forms its own group. The model is encoded by
159/// `nobjects_minus_one = 0` for every entry; qpdf emits the same value with
160/// `nbits_nobjects = 0` and has no separate serialized group entries.
161#[derive(Debug, Clone, PartialEq, Eq)]
162pub struct SharedObjectHintTable {
163 /// The 7-item header.
164 pub header: SharedObjectHeader,
165 /// One entry per shared object, in `plan.shared_hints` order.
166 pub objects: Vec<SharedObjectEntry>,
167}
168
169impl SharedObjectHintTable {
170 /// Build the Shared Object Hint Table from a [`LinearizationPlan`] and a
171 /// [`RenumberMap`].
172 ///
173 /// # Placeholder conventions
174 ///
175 /// Fields that depend on byte offsets not yet known are set to `0` and
176 /// must be filled in by the back-patcher:
177 ///
178 /// * `header.location`
179 /// * `header.least_length`
180 /// * `entry.length_minus_least` (all entries)
181 ///
182 /// # Degenerate case (no shared objects)
183 ///
184 /// When `plan.shared_hints` is empty the table is almost empty:
185 /// * All header numeric fields are `0`.
186 /// * `objects` is empty.
187 ///
188 /// # Panics
189 ///
190 /// When `shared_hints` is non-empty, panics if `part3_objects` is empty
191 /// or if its first entry is not present in `renumber` — both indicate a
192 /// malformed `LinearizationPlan` / `RenumberMap` pair that the caller
193 /// must construct consistently. Silently writing
194 /// `first_object_number = 0` would emit a header pointing at PDF
195 /// object 0 (the free-list head), which is invalid.
196 pub fn from_plan(
197 plan: &LinearizationPlan,
198 renumber: &RenumberMap,
199 member_to_container: &std::collections::BTreeMap<ObjectRef, (u32, u32)>,
200 second_half_container_nums: &std::collections::BTreeSet<u32>,
201 open_document_container_nums: &std::collections::BTreeSet<u32>,
202 ) -> Self {
203 // Fold first-page ObjStm members into their container (one shared entry
204 // per container) so the table matches qpdf's positional shared list.
205 // With no ObjStm packing this equals `plan.shared_hints`.
206 let shared_hints = plan.canonical_raw_shared_hints(
207 member_to_container,
208 renumber,
209 second_half_container_nums,
210 open_document_container_nums,
211 );
212 let shared_count = shared_hints.len() as u32;
213
214 // ------------------------------------------------------------------
215 // Degenerate case: no shared objects.
216 // ------------------------------------------------------------------
217 if shared_count == 0 {
218 return Self {
219 header: SharedObjectHeader {
220 first_object_number: 0,
221 location: 0,
222 first_page_entries: 0,
223 section_entries: 0,
224 bits_group_object_count: 0,
225 least_length: 0,
226 bits_length_delta: 0,
227 },
228 objects: vec![],
229 };
230 }
231
232 // ------------------------------------------------------------------
233 // Step 1: first object number in the "Part 8" section.
234 //
235 // Per ISO 32000-1 Annex F and qpdf's checkHSharedObject algorithm:
236 //
237 // - Item 1 (`first_object_number`) is the object number of the FIRST
238 // shared object in the "end of file section" (Part 8 in qpdf's terms
239 // = our part4_other_pages_shared).
240 //
241 // - This value is ONLY meaningful when `nshared_total > nshared_first_page`
242 // (i.e., when there are Part-8 shared objects beyond the first-page
243 // section). Per qpdf's Implementation Note 131, the value is
244 // meaningless when `nshared_total == nshared_first_page`.
245 //
246 // - qpdf's check walks the first `nshared_first_page` shared entries
247 // starting from `pages[0].getObjectID()` (the first page object, not
248 // from first_object_number). Only at index `nshared_first_page` does
249 // it jump to `first_object_number` and verify it matches the actual
250 // first object of part8.
251 //
252 // When there are no Part-8 shared objects (`part4_other_pages_shared`
253 // is empty), we emit `0` (or any value; it is ignored by readers).
254 // When there ARE Part-8 shared objects, emit the renumbered object ID
255 // of the first entry in `part4_other_pages_shared`.
256 //
257 // ------------------------------------------------------------------
258 // Step 2: split the folded shared list into the first-page section and
259 // the Part-8 (after-/E) section, and find the first Part-8 object.
260 //
261 // `shared_hints` is `canonical_shared_hints` output: the first-page
262 // section (Part-2/Part-3, with eligible members folded into part6
263 // containers) followed by the Part-8 section. The Part-8 section is the
264 // plain `part4_other_pages_shared` objects PLUS the part8 ObjStm
265 // containers `canonical_shared_hints` appends — containers the global even
266 // split filled with page-private objects, which are shared objects qpdf
267 // lists even though no individual member is `part4_other_pages_shared`.
268 // So the Part-8 count is the part8 containers plus the plain (no-container)
269 // `part4_other_pages_shared` objects.
270 // Open-document containers are excluded here for the same reason
271 // `canonical_shared_hints` excludes them: they live in the pre-/O
272 // region (before /E), so they do not appear in the Part-8 SOHT section
273 // and must not count toward `part8_entries`.
274 // part9 (Rest) containers routed there by outline priority are NOT part8
275 // shared objects; `canonical_shared_hints` excludes them from the entry
276 // list, so they must be excluded from the entry COUNT here too (otherwise
277 // `first_page_entries = shared_count - part8_entries` undercounts the
278 // first-page section, diverging from qpdf — e.g. when the first page has
279 // no ObjStm-eligible member so the part9 container has no first-page member
280 // and `part8_container_nums` would otherwise count it).
281 let rest_container_nums = plan.rest_container_nums(member_to_container);
282 let part8_containers: std::collections::BTreeSet<u32> = plan
283 .part8_container_nums(member_to_container)
284 .into_iter()
285 .filter(|cnum| {
286 !open_document_container_nums.contains(cnum) && !rest_container_nums.contains(cnum)
287 })
288 .collect();
289 let part8_plain = if plan.has_raw_projection_gap() {
290 plan.raw
291 .part4_other_pages_shared
292 .iter()
293 .filter(|object_gen| {
294 object_gen
295 .to_object_ref()
296 .is_none_or(|object_ref| !member_to_container.contains_key(&object_ref))
297 })
298 .count() as u32
299 } else {
300 plan.part4_other_pages_shared
301 .iter()
302 .filter(|r| !member_to_container.contains_key(r))
303 .count() as u32
304 };
305 let part8_entries = part8_containers.len() as u32 + part8_plain;
306 let first_page_entries = shared_count.saturating_sub(part8_entries);
307
308 // first_object_number (Annex F.4.1 item 1): the object number of the
309 // first object in the Part-8 section. `canonical_shared_hints` orders that
310 // section by physical object number, so it is the entry at index
311 // `first_page_entries` — 0 when there is no Part-8 section (meaningless per
312 // Implementation Note 131; qpdf emits 0 too).
313 // qpdf-deviation-start: sentinel dispatch (generation==u16::MAX) has
314 // no qpdf counterpart -- qpdf's containers get a real original
315 // QPDFObjGen from makeIndirectObject (QPDFWriter.cc
316 // generateObjectStreams) and resolve uniformly via a single total
317 // obj_renumber map (QPDF_linearization.cc:1598); flpdf's
318 // RenumberMap never registers an original identity for containers
319 // (their number is assigned directly while building the renumber
320 // table), so this branch exists only to avoid aliasing a
321 // container's new number with an unrelated original object's
322 // number.
323 let first_object_number: u32 =
324 shared_hints
325 .get(first_page_entries as usize)
326 .map_or(0, |e| {
327 if let Some(container) = e.container {
328 container
329 } else {
330 e.object
331 .and_then(|object| renumber.new_for_raw(object))
332 .map_or(0, |r| r.number)
333 }
334 });
335 // qpdf-deviation-end
336
337 // ------------------------------------------------------------------
338 // Step 3: build header bit-width fields.
339 //
340 // Each shared object is its own group, so every per-entry
341 // `nobjects_minus_one` is 0. This gives qpdf's `nbits_nobjects = 0`.
342 //
343 // bits_length_delta: since all lengths are 0 (placeholder) the delta
344 // is 0, so bits = 0. The encoder re-derives this after back-patching.
345 let bits_group_object_count: u32 = 0;
346
347 let header = SharedObjectHeader {
348 first_object_number,
349 location: 0, // placeholder — back-patched by sub-task 2.9
350 first_page_entries,
351 section_entries: shared_count,
352 bits_group_object_count,
353 least_length: 0, // placeholder — back-patched by sub-task 2.9
354 bits_length_delta: 0, // placeholder — re-derived by encoder after back-patch
355 };
356
357 // ------------------------------------------------------------------
358 // Step 4: build per-shared-object entries.
359 //
360 // Entries are in folded `shared_hints` order (Part-2, then Part-3 with
361 // packed members folded into their container, then Part-8).
362 // All byte-dependent fields are 0 (placeholder).
363 // signature_present is always false; signature is always None.
364 // ------------------------------------------------------------------
365 let objects: Vec<SharedObjectEntry> = shared_hints
366 .iter()
367 .map(|_hint| SharedObjectEntry {
368 length_minus_least: 0, // placeholder — populated by writer
369 signature_present: false,
370 signature: None,
371 nobjects_minus_one: 0, // 1-object-per-group model
372 })
373 .collect();
374
375 Self { header, objects }
376 }
377}
378
379// ---------------------------------------------------------------------------
380// Unit tests
381// ---------------------------------------------------------------------------
382
383#[cfg(test)]
384mod tests {
385 use super::*;
386 use crate::linearization::plan::{LinearizationPlan, PageHintEntry, SharedObjectHintEntry};
387 use crate::linearization::renumber::RenumberMap;
388 use crate::ObjectRef;
389
390 // -----------------------------------------------------------------------
391 // Fixture helpers (mirrors hint_page.rs fixtures for symmetry)
392 // -----------------------------------------------------------------------
393
394 /// Single-page plan with no shared objects (degenerate case).
395 ///
396 /// Part 2: [3 0 R, 2 0 R, 1 0 R]
397 /// Part 3: []
398 /// Pages: [page_ref = 3 0 R, object_count = 3]
399 fn single_page_no_shared() -> LinearizationPlan {
400 let page_ref = ObjectRef::new(3, 0);
401 LinearizationPlan {
402 part2_objects: vec![
403 ObjectRef::new(3, 0),
404 ObjectRef::new(2, 0),
405 ObjectRef::new(1, 0),
406 ],
407 total_object_count: 3,
408 page_hints: vec![PageHintEntry {
409 page_ref,
410 first_object_index: 0,
411 object_count: 3,
412 byte_length: 0,
413 }],
414 ..Default::default()
415 }
416 }
417
418 /// Two-page plan with 2 shared objects each referenced by both pages.
419 ///
420 /// Part 2 (page 0 exclusive): [3 0 R, 6 0 R] → new numbers 2, 3
421 /// Part 3 (shared): [5 0 R, 8 0 R] → new numbers 4, 5
422 /// Part 4 (remaining): [4 0 R, 7 0 R] → new numbers 6, 7
423 /// Pages:
424 /// page 0: page_ref = 3 0 R
425 /// page 1: page_ref = 4 0 R
426 /// Shared hints (part2 entries first, then part3 entries):
427 /// 3 0 R → referencing_pages [] (part2, page 0 owns by layout)
428 /// 6 0 R → referencing_pages [] (part2, page 0 owns by layout)
429 /// 5 0 R → referencing_pages [0, 1]
430 /// 8 0 R → referencing_pages [0, 1]
431 fn two_page_shared_both_pages() -> LinearizationPlan {
432 LinearizationPlan {
433 part2_objects: vec![ObjectRef::new(3, 0), ObjectRef::new(6, 0)],
434 part3_objects: vec![ObjectRef::new(5, 0), ObjectRef::new(8, 0)],
435 part4_other_pages_private: vec![ObjectRef::new(4, 0), ObjectRef::new(7, 0)],
436 total_object_count: 8,
437 page_hints: vec![
438 PageHintEntry {
439 page_ref: ObjectRef::new(3, 0),
440 first_object_index: 0,
441 object_count: 3,
442 byte_length: 0,
443 },
444 PageHintEntry {
445 page_ref: ObjectRef::new(4, 0),
446 first_object_index: 0,
447 object_count: 5,
448 byte_length: 0,
449 },
450 ],
451 shared_hints: vec![
452 // part2 entries (referencing_pages = [] — page 0 owns by physical layout)
453 SharedObjectHintEntry {
454 object_ref: ObjectRef::new(3, 0),
455 referencing_pages: vec![],
456 },
457 SharedObjectHintEntry {
458 object_ref: ObjectRef::new(6, 0),
459 referencing_pages: vec![],
460 },
461 // part3 entries (truly cross-page shared objects)
462 SharedObjectHintEntry {
463 object_ref: ObjectRef::new(5, 0),
464 referencing_pages: vec![0, 1],
465 },
466 SharedObjectHintEntry {
467 object_ref: ObjectRef::new(8, 0),
468 referencing_pages: vec![0, 1],
469 },
470 ],
471 ..Default::default()
472 }
473 }
474
475 /// Two-page plan with 3 shared objects: 2 referenced from page 0, 1 only from page 1.
476 ///
477 /// Part 2: [10 0 R] → new number 2
478 /// Part 3: [20 0 R, 21 0 R, 22 0 R] → new numbers 3, 4, 5
479 /// Part 4: [30 0 R] → new number 6
480 /// Pages:
481 /// page 0: page_ref = 10 0 R
482 /// page 1: page_ref = 30 0 R
483 /// Shared hints (part2 first, then part3):
484 /// 10 0 R → referencing_pages [] (part2, page 0 owns by layout)
485 /// 20 0 R → referencing_pages [0, 1]
486 /// 21 0 R → referencing_pages [0]
487 /// 22 0 R → referencing_pages [1] ← NOT referenced from page 0
488 fn two_page_partial_first_page() -> LinearizationPlan {
489 LinearizationPlan {
490 part2_objects: vec![ObjectRef::new(10, 0)],
491 part3_objects: vec![
492 ObjectRef::new(20, 0),
493 ObjectRef::new(21, 0),
494 ObjectRef::new(22, 0),
495 ],
496 part4_other_pages_private: vec![ObjectRef::new(30, 0)],
497 total_object_count: 5,
498 page_hints: vec![
499 PageHintEntry {
500 page_ref: ObjectRef::new(10, 0),
501 first_object_index: 0,
502 object_count: 1,
503 byte_length: 0,
504 },
505 PageHintEntry {
506 page_ref: ObjectRef::new(30, 0),
507 first_object_index: 0,
508 object_count: 1,
509 byte_length: 0,
510 },
511 ],
512 shared_hints: vec![
513 // part2 entry (referencing_pages = [] — page 0 owns by physical layout)
514 SharedObjectHintEntry {
515 object_ref: ObjectRef::new(10, 0),
516 referencing_pages: vec![],
517 },
518 // part3 entries (truly cross-page shared objects)
519 SharedObjectHintEntry {
520 object_ref: ObjectRef::new(20, 0),
521 referencing_pages: vec![0, 1],
522 },
523 SharedObjectHintEntry {
524 object_ref: ObjectRef::new(21, 0),
525 referencing_pages: vec![0],
526 },
527 SharedObjectHintEntry {
528 object_ref: ObjectRef::new(22, 0),
529 referencing_pages: vec![1],
530 },
531 ],
532 ..Default::default()
533 }
534 }
535
536 // -----------------------------------------------------------------------
537 // Degenerate case: no shared objects
538 // -----------------------------------------------------------------------
539
540 #[test]
541 fn degenerate_objects_are_empty() {
542 let plan = single_page_no_shared();
543 let renumber = RenumberMap::from_plan(&plan);
544 let table = SharedObjectHintTable::from_plan(
545 &plan,
546 &renumber,
547 &Default::default(),
548 &Default::default(),
549 &Default::default(),
550 );
551
552 assert!(
553 table.objects.is_empty(),
554 "no shared objects → objects must be empty"
555 );
556 }
557
558 #[test]
559 fn degenerate_header_all_zero() {
560 let plan = single_page_no_shared();
561 let renumber = RenumberMap::from_plan(&plan);
562 let table = SharedObjectHintTable::from_plan(
563 &plan,
564 &renumber,
565 &Default::default(),
566 &Default::default(),
567 &Default::default(),
568 );
569
570 assert_eq!(table.header.first_object_number, 0);
571 assert_eq!(table.header.location, 0);
572 assert_eq!(table.header.first_page_entries, 0);
573 assert_eq!(table.header.section_entries, 0);
574 assert_eq!(table.header.bits_group_object_count, 0);
575 assert_eq!(table.header.least_length, 0);
576 assert_eq!(table.header.bits_length_delta, 0);
577 }
578
579 // -----------------------------------------------------------------------
580 // Two-page plan: both shared objects referenced from both pages
581 // -----------------------------------------------------------------------
582
583 #[test]
584 fn two_page_section_entries_equals_shared_hint_count() {
585 let plan = two_page_shared_both_pages();
586 let renumber = RenumberMap::from_plan(&plan);
587 let table = SharedObjectHintTable::from_plan(
588 &plan,
589 &renumber,
590 &Default::default(),
591 &Default::default(),
592 &Default::default(),
593 );
594
595 assert_eq!(
596 table.header.section_entries, 4,
597 "section_entries must equal plan.shared_hints.len() (2 part2 + 2 part3 = 4)"
598 );
599 }
600
601 #[test]
602 fn two_page_first_page_entries_equals_section_entries() {
603 let plan = two_page_shared_both_pages();
604 let renumber = RenumberMap::from_plan(&plan);
605 let table = SharedObjectHintTable::from_plan(
606 &plan,
607 &renumber,
608 &Default::default(),
609 &Default::default(),
610 &Default::default(),
611 );
612
613 // All shared objects are in the first-page section (before /E).
614 // first_page_entries must equal section_entries so qpdf doesn't
615 // expect a non-empty Part 8.
616 assert_eq!(
617 table.header.first_page_entries, 4,
618 "all shared objects are in first-page section → first_page_entries must equal section_entries (4)"
619 );
620 }
621
622 #[test]
623 fn two_page_first_object_number_is_zero_when_no_part8() {
624 let plan = two_page_shared_both_pages();
625 let renumber = RenumberMap::from_plan(&plan);
626 let table = SharedObjectHintTable::from_plan(
627 &plan,
628 &renumber,
629 &Default::default(),
630 &Default::default(),
631 &Default::default(),
632 );
633
634 // When part4_other_pages_shared is empty (no Part-8 shared objects),
635 // first_object_number must be 0 per ISO 32000-1 Implementation Note 131:
636 // the value is meaningless when nshared_total == nshared_first_page,
637 // so we emit 0 rather than pointing at an unrelated Part-2 object.
638 assert_eq!(
639 table.header.first_object_number, 0,
640 "first_object_number must be 0 when there are no Part-8 shared objects \
641 (nshared_total == nshared_first_page, value is meaningless per Note 131)"
642 );
643 }
644
645 #[test]
646 fn two_page_bits_group_object_count() {
647 let plan = two_page_shared_both_pages();
648 let renumber = RenumberMap::from_plan(&plan);
649 let table = SharedObjectHintTable::from_plan(
650 &plan,
651 &renumber,
652 &Default::default(),
653 &Default::default(),
654 &Default::default(),
655 );
656
657 // Every shared object is its own group, so each
658 // `nobjects_minus_one` is 0 and qpdf's `nbits_nobjects` is 0.
659 assert_eq!(table.header.bits_group_object_count, 0);
660 }
661
662 #[test]
663 fn two_page_entries_use_one_object_groups() {
664 let plan = two_page_shared_both_pages();
665 let renumber = RenumberMap::from_plan(&plan);
666 let table = SharedObjectHintTable::from_plan(
667 &plan,
668 &renumber,
669 &Default::default(),
670 &Default::default(),
671 &Default::default(),
672 );
673
674 assert_eq!(table.objects.len(), 4);
675 for (i, entry) in table.objects.iter().enumerate() {
676 assert_eq!(
677 entry.nobjects_minus_one, 0,
678 "entry {i} must describe a one-object group"
679 );
680 }
681 }
682
683 #[test]
684 fn two_page_objects_count_matches_shared_hints() {
685 let plan = two_page_shared_both_pages();
686 let renumber = RenumberMap::from_plan(&plan);
687 let table = SharedObjectHintTable::from_plan(
688 &plan,
689 &renumber,
690 &Default::default(),
691 &Default::default(),
692 &Default::default(),
693 );
694
695 assert_eq!(
696 table.objects.len(),
697 plan.shared_hints.len(),
698 "objects vec length must match shared_hints count"
699 );
700 }
701
702 #[test]
703 fn two_page_signature_always_absent() {
704 let plan = two_page_shared_both_pages();
705 let renumber = RenumberMap::from_plan(&plan);
706 let table = SharedObjectHintTable::from_plan(
707 &plan,
708 &renumber,
709 &Default::default(),
710 &Default::default(),
711 &Default::default(),
712 );
713
714 for entry in &table.objects {
715 assert!(
716 !entry.signature_present,
717 "signature_present must be false (signature not computed)"
718 );
719 assert!(entry.signature.is_none(), "signature must be None");
720 }
721 }
722
723 #[test]
724 fn two_page_placeholder_fields_are_zero() {
725 let plan = two_page_shared_both_pages();
726 let renumber = RenumberMap::from_plan(&plan);
727 let table = SharedObjectHintTable::from_plan(
728 &plan,
729 &renumber,
730 &Default::default(),
731 &Default::default(),
732 &Default::default(),
733 );
734
735 assert_eq!(table.header.location, 0);
736 assert_eq!(table.header.least_length, 0);
737 assert_eq!(table.header.bits_length_delta, 0);
738 for entry in &table.objects {
739 assert_eq!(entry.length_minus_least, 0);
740 assert_eq!(entry.nobjects_minus_one, 0);
741 }
742 }
743
744 // -----------------------------------------------------------------------
745 // Partial first-page reference: first_page_entries < section_entries
746 // -----------------------------------------------------------------------
747
748 #[test]
749 fn partial_first_page_section_entries_is_four() {
750 let plan = two_page_partial_first_page();
751 let renumber = RenumberMap::from_plan(&plan);
752 let table = SharedObjectHintTable::from_plan(
753 &plan,
754 &renumber,
755 &Default::default(),
756 &Default::default(),
757 &Default::default(),
758 );
759
760 assert_eq!(
761 table.header.section_entries, 4,
762 "section_entries must equal total shared hints count (1 part2 + 3 part3 = 4)"
763 );
764 }
765
766 #[test]
767 fn partial_first_page_first_page_entries_equals_section_entries() {
768 let plan = two_page_partial_first_page();
769 let renumber = RenumberMap::from_plan(&plan);
770 let table = SharedObjectHintTable::from_plan(
771 &plan,
772 &renumber,
773 &Default::default(),
774 &Default::default(),
775 &Default::default(),
776 );
777
778 // All shared objects (4 = 1 part2 + 3 part3) are physically in the first-page section.
779 // first_page_entries must equal section_entries = 4 so that qpdf
780 // does not expect a non-empty Part 8.
781 assert_eq!(
782 table.header.first_page_entries, 4,
783 "all 4 shared objects are in first-page section → first_page_entries must be 4"
784 );
785 }
786
787 #[test]
788 fn partial_first_page_entries_use_one_object_groups() {
789 let plan = two_page_partial_first_page();
790 let renumber = RenumberMap::from_plan(&plan);
791 let table = SharedObjectHintTable::from_plan(
792 &plan,
793 &renumber,
794 &Default::default(),
795 &Default::default(),
796 &Default::default(),
797 );
798
799 assert_eq!(table.objects.len(), 4);
800 for entry in &table.objects {
801 assert_eq!(entry.nobjects_minus_one, 0);
802 }
803 }
804
805 #[test]
806 fn partial_first_page_bits_group_object_count() {
807 let plan = two_page_partial_first_page();
808 let renumber = RenumberMap::from_plan(&plan);
809 let table = SharedObjectHintTable::from_plan(
810 &plan,
811 &renumber,
812 &Default::default(),
813 &Default::default(),
814 &Default::default(),
815 );
816
817 // One-object-per-group model: see two_page_bits_group_object_count.
818 assert_eq!(table.header.bits_group_object_count, 0);
819 }
820
821 #[test]
822 fn partial_first_page_first_object_number_is_zero_when_no_part8() {
823 let plan = two_page_partial_first_page();
824 let renumber = RenumberMap::from_plan(&plan);
825 let table = SharedObjectHintTable::from_plan(
826 &plan,
827 &renumber,
828 &Default::default(),
829 &Default::default(),
830 &Default::default(),
831 );
832
833 // Two-page plan with 3 part3 objects but no part4_other_pages_shared.
834 // first_object_number must be 0 — value is meaningless when
835 // nshared_total == nshared_first_page (Implementation Note 131).
836 assert_eq!(
837 table.header.first_object_number, 0,
838 "first_object_number must be 0 when part4_other_pages_shared is empty \
839 (nshared_total == nshared_first_page, value is meaningless per Note 131)"
840 );
841 }
842
843 #[test]
844 fn partial_first_page_objects_count_is_three() {
845 let plan = two_page_partial_first_page();
846 let renumber = RenumberMap::from_plan(&plan);
847 let table = SharedObjectHintTable::from_plan(
848 &plan,
849 &renumber,
850 &Default::default(),
851 &Default::default(),
852 &Default::default(),
853 );
854
855 assert_eq!(table.objects.len(), 4);
856 }
857
858 // -----------------------------------------------------------------------
859 // Plan with Part-8 shared objects (part4_other_pages_shared non-empty).
860 //
861 // This models objects shared by two or more pages (pages 2..N) but NOT
862 // reachable from page 0 (i.e., not in Part 2 or Part 3).
863 //
864 // Part 2: [3 0 R] → first-page private (page dict)
865 // Part 3: [5 0 R] → first-page shared (font)
866 // part4_other_pages_shared: [9 0 R, 10 0 R] → Part-8 shared (content streams)
867 // part4_other_pages_private: [4 0 R] → page 2 private
868 // Pages:
869 // page 0: page_ref = 3 0 R
870 // page 1: page_ref = 4 0 R
871 // Shared hints: part2 + part3 + part4_shared entries.
872 // 3 0 R → [] (part2, page 0 layout)
873 // 5 0 R → [1] (part3, page 0 layout, page 1 reference)
874 // 9 0 R → [1, 2] (part8, pages 1 and 2 reference it)
875 // 10 0 R → [1, 3] (part8, pages 1 and 3 reference it)
876 // -----------------------------------------------------------------------
877
878 fn two_page_with_part8_shared() -> LinearizationPlan {
879 LinearizationPlan {
880 part2_objects: vec![ObjectRef::new(3, 0)],
881 part3_objects: vec![ObjectRef::new(5, 0)],
882 part4_other_pages_shared: vec![ObjectRef::new(9, 0), ObjectRef::new(10, 0)],
883 part4_other_pages_private: vec![ObjectRef::new(4, 0)],
884 total_object_count: 5,
885 page_hints: vec![
886 PageHintEntry {
887 page_ref: ObjectRef::new(3, 0),
888 first_object_index: 0,
889 object_count: 2,
890 byte_length: 0,
891 },
892 PageHintEntry {
893 page_ref: ObjectRef::new(4, 0),
894 first_object_index: 0,
895 object_count: 1,
896 byte_length: 0,
897 },
898 ],
899 shared_hints: vec![
900 // part2 entry
901 SharedObjectHintEntry {
902 object_ref: ObjectRef::new(3, 0),
903 referencing_pages: vec![],
904 },
905 // part3 entry
906 SharedObjectHintEntry {
907 object_ref: ObjectRef::new(5, 0),
908 referencing_pages: vec![1],
909 },
910 // part4_other_pages_shared entries
911 SharedObjectHintEntry {
912 object_ref: ObjectRef::new(9, 0),
913 referencing_pages: vec![1, 2],
914 },
915 SharedObjectHintEntry {
916 object_ref: ObjectRef::new(10, 0),
917 referencing_pages: vec![1, 3],
918 },
919 ],
920 ..Default::default()
921 }
922 }
923
924 #[test]
925 fn part8_shared_first_page_entries_less_than_section_entries() {
926 let plan = two_page_with_part8_shared();
927 let renumber = RenumberMap::from_plan(&plan);
928 let table = SharedObjectHintTable::from_plan(
929 &plan,
930 &renumber,
931 &Default::default(),
932 &Default::default(),
933 &Default::default(),
934 );
935
936 // first_page_entries = |part2| + |part3| = 1 + 1 = 2
937 // section_entries = |shared_hints| = 4
938 assert_eq!(
939 table.header.first_page_entries, 2,
940 "first_page_entries must equal |part2| + |part3| = 2"
941 );
942 assert_eq!(
943 table.header.section_entries, 4,
944 "section_entries must equal total shared_hints count = 4"
945 );
946 assert!(
947 table.header.first_page_entries < table.header.section_entries,
948 "first_page_entries ({}) must be less than section_entries ({}) \
949 when there are Part-8 shared objects",
950 table.header.first_page_entries,
951 table.header.section_entries
952 );
953 }
954
955 #[test]
956 fn part8_shared_first_object_number_is_new_number_of_part8_first() {
957 let plan = two_page_with_part8_shared();
958 let renumber = RenumberMap::from_plan(&plan);
959 let table = SharedObjectHintTable::from_plan(
960 &plan,
961 &renumber,
962 &Default::default(),
963 &Default::default(),
964 &Default::default(),
965 );
966
967 // part4_other_pages_shared[0] = 9 0 R.
968 // first_object_number must point to its renumbered slot.
969 assert_eq!(
970 table.header.first_object_number,
971 renumber
972 .new_for_original(ObjectRef::new(9, 0))
973 .unwrap()
974 .number,
975 "first_object_number must equal the renumbered slot of \
976 part4_other_pages_shared[0] (9 0 R) when Part-8 shared objects exist"
977 );
978 }
979
980 #[test]
981 fn part8_shared_folded_container_does_not_overcount_first_page_entries() {
982 // Two Part-8 (after-/E) shared objects packed into ONE second-half
983 // ObjStm container. `canonical_shared_hints` folds them into a single
984 // shared entry, so `section_entries` is 3 (part2 + part3 + 1 folded
985 // Part-8). `first_page_entries` must stay 2 (part2 + part3): subtracting
986 // the unfolded `part4_other_pages_shared.len()` (2) would wrongly yield 1
987 // and tell qpdf a first-page entry belongs to Part 8.
988 let plan = two_page_with_part8_shared();
989 let renumber = RenumberMap::from_plan(&plan);
990 let mut member_to_container: std::collections::BTreeMap<ObjectRef, (u32, u32)> =
991 std::collections::BTreeMap::new();
992 member_to_container.insert(ObjectRef::new(9, 0), (42, 0));
993 member_to_container.insert(ObjectRef::new(10, 0), (42, 1));
994 let table = SharedObjectHintTable::from_plan(
995 &plan,
996 &renumber,
997 &member_to_container,
998 &Default::default(),
999 &Default::default(),
1000 );
1001
1002 assert_eq!(
1003 table.header.section_entries, 3,
1004 "two Part-8 members folded into one container → section_entries = \
1005 part2(1) + part3(1) + folded part8(1) = 3"
1006 );
1007 assert_eq!(
1008 table.header.first_page_entries, 2,
1009 "first_page_entries must stay |part2| + |part3| = 2 even when the \
1010 Part-8 members fold into a single container"
1011 );
1012 }
1013
1014 /// A part9 (Rest) container routed by outline priority, carrying a
1015 /// `part4_other_pages_shared` member but NO first-page member, must be
1016 /// excluded from the Part-8 entry COUNT — not just from the entry list.
1017 /// `canonical_shared_hints` drops it from `section_entries`; if `from_plan`
1018 /// still counted it via `part8_container_nums`, `first_page_entries =
1019 /// section_entries - part8_entries` would undercount the first-page section
1020 /// (the `objstm-lin-outlines-otherpage-0-60-20` byte divergence, flpdf-7aek).
1021 #[test]
1022 fn part9_outline_container_excluded_from_part8_entry_count() {
1023 let page = ObjectRef::new(3, 0); // part2 first-page object (plain)
1024 let outline = ObjectRef::new(6, 0); // in_outlines (part9), member of 42
1025 let shared_a = ObjectRef::new(9, 0); // part4_other_pages_shared, member of 42
1026 let plan = LinearizationPlan {
1027 part2_objects: vec![page],
1028 part4_other_pages_shared: vec![shared_a],
1029 part9_outline_objects: vec![outline],
1030 shared_hints: vec![
1031 SharedObjectHintEntry {
1032 object_ref: page,
1033 referencing_pages: vec![],
1034 },
1035 SharedObjectHintEntry {
1036 object_ref: shared_a,
1037 referencing_pages: vec![1, 2],
1038 },
1039 ],
1040 ..Default::default()
1041 };
1042 let mut member_to_container: std::collections::BTreeMap<ObjectRef, (u32, u32)> =
1043 std::collections::BTreeMap::new();
1044 member_to_container.insert(outline, (42, 0));
1045 member_to_container.insert(shared_a, (42, 1));
1046
1047 // Precondition: container 42 would be counted as part8 without the guard.
1048 assert!(plan
1049 .part8_container_nums(&member_to_container)
1050 .contains(&42));
1051
1052 let renumber = RenumberMap::from_plan(&plan);
1053 let table = SharedObjectHintTable::from_plan(
1054 &plan,
1055 &renumber,
1056 &member_to_container,
1057 &Default::default(),
1058 &Default::default(),
1059 );
1060
1061 // The part9 container is excluded from BOTH the entry list and the count.
1062 assert_eq!(
1063 table.header.section_entries, 1,
1064 "part9 container dropped from the shared entry list → only `page` remains"
1065 );
1066 assert_eq!(
1067 table.header.first_page_entries, 1,
1068 "part9 container must not be counted as a Part-8 entry → \
1069 first_page_entries equals section_entries (no Part-8 section)"
1070 );
1071 }
1072
1073 #[test]
1074 fn part8_shared_entries_count_equals_total_shared_hints() {
1075 let plan = two_page_with_part8_shared();
1076 let renumber = RenumberMap::from_plan(&plan);
1077 let table = SharedObjectHintTable::from_plan(
1078 &plan,
1079 &renumber,
1080 &Default::default(),
1081 &Default::default(),
1082 &Default::default(),
1083 );
1084
1085 assert_eq!(table.objects.len(), plan.shared_hints.len());
1086 }
1087
1088 // -----------------------------------------------------------------------
1089 // ObjStm-aware back-patch behaviour
1090 //
1091 // `from_plan` computes `first_object_number` from the renumber map only
1092 // — it has no knowledge of ObjStm containers. When the first Part-8
1093 // shared object is packed inside an ObjStm the writer's convergence loop
1094 // patches `so_table.header.first_object_number` with the *container's*
1095 // new object number (not the member's renumber slot).
1096 //
1097 // The tests below verify two invariants:
1098 //
1099 // 1. `from_plan` returns the member's own renumber slot (the "before-patch"
1100 // value). This is *intentionally different* from the ObjStm-container
1101 // number; the convergence loop is responsible for correcting it.
1102 //
1103 // 2. If the writer's patch replaces `first_object_number` with a
1104 // hypothetical container number, the field must store *that* container
1105 // number, not the original member slot — demonstrating that the patch
1106 // logic selects the right source when `member_to_container` has an entry.
1107 //
1108 // Note: these tests operate on the struct directly (before the writer patch
1109 // runs). They document the two-step contract: (a) from_plan establishes the
1110 // member-slot baseline, and (b) the writer overwrites it with container_num
1111 // when the member is ObjStm-packed.
1112 // -----------------------------------------------------------------------
1113
1114 /// `from_plan` returns the member's own renumber slot for Part-8 shared objects.
1115 /// The writer's convergence loop is responsible for patching this to the
1116 /// container's number when the member lives inside an ObjStm.
1117 #[test]
1118 fn part8_shared_from_plan_returns_member_renumber_slot_before_objstm_patch() {
1119 let plan = two_page_with_part8_shared();
1120 let renumber = RenumberMap::from_plan(&plan);
1121 let table = SharedObjectHintTable::from_plan(
1122 &plan,
1123 &renumber,
1124 &Default::default(),
1125 &Default::default(),
1126 &Default::default(),
1127 );
1128
1129 // from_plan: member's renumber slot (before writer patch)
1130 let member_slot = renumber
1131 .new_for_original(ObjectRef::new(9, 0))
1132 .expect("9 0 R must be in renumber map")
1133 .number;
1134 assert_eq!(
1135 table.header.first_object_number, member_slot,
1136 "from_plan must return the member's renumber slot (pre-patch baseline)"
1137 );
1138 }
1139
1140 /// When the writer patches `first_object_number` with an ObjStm container
1141 /// number, the patched value must differ from the member's renumber slot
1142 /// (unless the object happens to be allocated the same number, which is
1143 /// impossible since ObjStm containers are allocated above the renumber
1144 /// range). This test simulates the patch by hand to verify the expected
1145 /// post-patch value.
1146 #[test]
1147 fn part8_shared_objstm_patch_uses_container_num_not_member_slot() {
1148 let plan = two_page_with_part8_shared();
1149 let renumber = RenumberMap::from_plan(&plan);
1150 let mut table = SharedObjectHintTable::from_plan(
1151 &plan,
1152 &renumber,
1153 &Default::default(),
1154 &Default::default(),
1155 &Default::default(),
1156 );
1157
1158 // Simulate the writer's ObjStm-aware patch: container numbers are
1159 // allocated above the RenumberMap range (renumber.len() + 1, +2 …).
1160 // For this plan, renumber.len() == 5 (objects 3,5,9,10,4 → slots 2-6),
1161 // so a Part-4 ObjStm container might get number 7.
1162 let simulated_container_num: u32 = renumber.len() as u32 + 2; // > any member slot
1163 table.header.first_object_number = simulated_container_num;
1164
1165 // After patch: the field must hold the container number, not the member slot.
1166 let member_slot = renumber
1167 .new_for_original(ObjectRef::new(9, 0))
1168 .expect("9 0 R must be in renumber map")
1169 .number;
1170 assert_ne!(
1171 table.header.first_object_number, member_slot,
1172 "post-patch: first_object_number must differ from member's renumber slot \
1173 when the member is ObjStm-packed (container_num > all member slots)"
1174 );
1175 assert_eq!(
1176 table.header.first_object_number, simulated_container_num,
1177 "post-patch: first_object_number must equal the ObjStm container number"
1178 );
1179 }
1180
1181 // -----------------------------------------------------------------------
1182 // OD container filter: must not count OD ObjStm as Part-8 entry
1183 // -----------------------------------------------------------------------
1184
1185 /// Plan where a Part-3 font is in a first-half ObjStm (fh_cnum) and an OD
1186 /// widget is in a separate OD ObjStm (od_cnum). The widget spans pages 1
1187 /// and 2, so `part8_container_nums` includes od_cnum via the
1188 /// `container_pages.len() >= 2` path. The OD container must be filtered
1189 /// out of `part8_entries` so `first_page_entries` is not undercounted.
1190 #[test]
1191 fn od_container_spanning_two_later_pages_not_counted_as_part8_entry() {
1192 use std::collections::{BTreeMap, BTreeSet};
1193
1194 use crate::optimization::{ObjectUser, Optimization};
1195
1196 let font = ObjectRef::new(7, 0);
1197 let widget = ObjectRef::new(6, 0);
1198 let fh_cnum: u32 = 20; // first-half ObjStm container
1199 let od_cnum: u32 = 21; // OD ObjStm container
1200
1201 let mut optimization = Optimization::default();
1202 // Widget reaches pages 1 and 2 (not page 0), which makes od_cnum
1203 // eligible for part8_container_nums via container_pages.len() >= 2.
1204 optimization.record_for_test(ObjectUser::Page(1), widget);
1205 optimization.record_for_test(ObjectUser::Page(2), widget);
1206
1207 let plan = LinearizationPlan {
1208 part3_objects: vec![font],
1209 optimization: Some(optimization),
1210 shared_hints: vec![SharedObjectHintEntry {
1211 object_ref: font,
1212 referencing_pages: vec![0, 1, 2],
1213 }],
1214 ..Default::default()
1215 };
1216
1217 let renumber = RenumberMap::from_plan(&plan);
1218
1219 // Font packed in first-half ObjStm; widget packed in OD ObjStm.
1220 let member_to_container: BTreeMap<ObjectRef, (u32, u32)> =
1221 [(font, (fh_cnum, 0)), (widget, (od_cnum, 0))]
1222 .into_iter()
1223 .collect();
1224
1225 // od_cnum is the open-document container.
1226 let open_document_container_nums: BTreeSet<u32> = BTreeSet::from([od_cnum]);
1227
1228 let table = SharedObjectHintTable::from_plan(
1229 &plan,
1230 &renumber,
1231 &member_to_container,
1232 &Default::default(), // second_half_container_nums
1233 &open_document_container_nums,
1234 );
1235
1236 // canonical_shared_hints emits one entry (fh_cnum for font); od_cnum
1237 // is filtered by open_document_container_nums. No Part-8 section.
1238 assert_eq!(
1239 table.header.section_entries, 1,
1240 "one shared entry: font folded into first-half container"
1241 );
1242 assert_eq!(
1243 table.header.first_page_entries, 1,
1244 "OD container must NOT inflate part8_entries: all 1 entries are first-page"
1245 );
1246 assert_eq!(
1247 table.header.first_object_number, 0,
1248 "no Part-8 shared objects → first_object_number must be 0 (Note 131)"
1249 );
1250 }
1251}