Skip to main content

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}