//! `LinearizationPlan` — pure data model for PDF linearization layout.
//!
//! qpdf correspondence: QPDF_linearization.cc object classification and layout planning.
//!
//! A `LinearizationPlan` partitions all objects in a document into the four
//! body parts defined by ISO 32000-1 Annex F, and carries the raw inputs needed
//! to build the Page-offset hint table and the Shared-object hint table.
//!
//! The plan is intentionally a data-only structure: no I/O or serialization.
//! The hint-table builder and linearized writer consume this structure and fill
//! in the placeholders.
//!
//! # Part layout (Annex F summary)
//!
//! | Part | Contents |
//! |------|----------|
//! | 1 | Linearization parameter dictionary + first-page xref/trailer |
//! | 2 | First-page objects (page dict, resources, content streams) |
//! | 3 | Non-first-page shared objects (catalog, font programs, etc.) |
//! | 4 | Remaining (non-first-page) objects |
//!
//! # Object closure algorithm
//!
//! `from_pdf` now computes the transitive closure of objects reachable from the
//! first page (`/Pages /Kids[0]`) and partitions them:
//!
//! * **Part 2** — objects reachable from page 1 and *not* shared with other pages.
//! * **Part 3** — objects reachable from page 1 *and also* reachable from page 2..N
//! (shared objects).
//! * **Part 4** — everything else (objects only reachable from pages 2..N, or from
//! the catalog root but not from any page).
//!
//! The four parts are always disjoint (invariant preserved by construction).
use crate::linearization::renumber::RenumberMap;
use crate::object_handle::{LiveDictionaryKeyBuffer, ObjectHandle, ObjectValue};
use crate::parser::MAX_PARSE_DEPTH;
use crate::pdf::WriterObjectOrderKey;
use crate::qpdf_obj_gen::QpdfObjGen;
use crate::writer::object_streams::{
compressible_objgens_qpdf_plan, eligibility_context, is_eligible_for_objstm_handle,
ObjectStreamMode, PlannerConfig,
};
use crate::{ObjectRef, Pdf, Result};
use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::io::{Read, Seek};
// ---------------------------------------------------------------------------
// Supporting types
// ---------------------------------------------------------------------------
/// Per-page entry for the **Page-offset hint table** (Annex F.3).
///
/// Byte-length and exact object indices are filled in as placeholders (zeros)
/// at construction time; a downstream writer pass must back-patch them once the
/// real file positions are known.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PageHintEntry {
/// Indirect reference to the page's dictionary object.
pub page_ref: ObjectRef,
/// Index (0-based) of the first object belonging to this page in the
/// object order that the linearized file will use.
pub first_object_index: u32,
/// Number of objects directly belonging to this page.
pub object_count: u32,
/// Byte length of all objects belonging to this page (placeholder: 0).
pub byte_length: u64,
}
impl PageHintEntry {
/// Construct a placeholder entry for `page_ref`.
pub fn placeholder(page_ref: ObjectRef) -> Self {
Self {
page_ref,
first_object_index: 0,
object_count: 0,
byte_length: 0,
}
}
}
/// Per-object entry for the **Shared-object hint table** (Annex F.4).
///
/// Annex F.4 keys shared objects by object index (within the linearized body
/// ordering), not by `ObjectRef`. The `referencing_pages` field lists the
/// 0-based page indices (not `ObjectRef`s) that reference this shared object.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SharedObjectHintEntry {
/// The shared object.
pub object_ref: ObjectRef,
/// 0-based indices of the pages that reference this object.
pub referencing_pages: Vec<u32>,
}
impl SharedObjectHintEntry {
/// Construct a shared-object entry that has no page references yet.
pub fn new(object_ref: ObjectRef) -> Self {
Self {
object_ref,
referencing_pages: Vec::new(),
}
}
}
// ---------------------------------------------------------------------------
// Closure helpers
// ---------------------------------------------------------------------------
/// The raw set of page-content stream identities, keyed by [`QpdfObjGen`]
/// like qpdf's `old_og`-keyed membership test (`QPDFWriter.cc:1279`). The
/// snapshot branch clones a `BTreeSet<QpdfObjGen>` and the fallback inserts
/// each handle's raw `qpdf_obj_gen()`, so a `gen >= 65535` content stream
/// stays in it -- which is what
/// `linearized_normalizes_a_raw_page_content_and_drops_its_parameters`
/// relies on. **2026-09-19**: the plain writer now reads the same raw
/// representation instead of the `ObjectRef`-projected `contents_seq` gate,
/// so the two routes agree on this identity.
///
/// Empty when `options.content_normalization` is off: qpdf's own
/// `m->normalize_content && m->normalized_streams.count(old_og)` gate
/// (`QPDFWriter.cc:1277`) is false for every stream in that case, so no
/// per-stream membership computation is needed.
fn linearization_content_normalize_refs(
options: &crate::writer::WriterOptions,
page_handles: &[ObjectHandle],
normalized_streams_snapshot: Option<&BTreeSet<QpdfObjGen>>,
) -> Result<BTreeSet<QpdfObjGen>> {
if !options.content_normalization {
return Ok(BTreeSet::new());
}
if let Some(snapshot) = normalized_streams_snapshot {
return Ok(snapshot.clone());
} // cov:ignore: LLVM attributes the executed snapshot-return block to the preceding lines.
let mut refs = BTreeSet::new();
for page in page_handles {
let contents = page.try_get_key(b"/Contents")?;
let mut record_stream = |stream: &ObjectHandle| -> Result<()> {
if stream.type_code()? == 10 {
if let Some(object_gen) = stream
.qpdf_obj_gen()
.filter(|object_gen| object_gen.is_indirect())
{
refs.insert(object_gen);
}
}
Ok(())
};
if contents.type_code()? == 10 {
record_stream(&contents)?;
} else if let Some(items) = contents.try_as_array()? {
for item in items {
record_stream(&item)?;
}
}
}
Ok(refs)
}
/// Return whether a stream's `/Filter` or `/DecodeParms` value contains an
/// indirect edge that the linearized writer may remove after refiltering.
///
/// This inspects only the stream dictionary already supplied by qpdf's
/// optimization walk. It deliberately does not resolve the parameter object:
/// qpdf's `skip_stream_parameters` callback runs before those edges are
/// traversed (`QPDF_optimization.cc:306-333`).
fn stream_has_indirect_parameter_edge(handle: &ObjectHandle) -> Result<bool> {
let Some(stream_dict) = handle.as_stream_dict() else {
return Ok(false); // cov:ignore: Optimization invokes the callback only for resolved stream handles
};
stream_dict.try_dereference()?;
for key in [b"/Filter".as_slice(), b"/DecodeParms".as_slice()] {
// QPDF_Dictionary::getKey returns a contextual null for a missing key,
// but a missing entry has no descendant to inspect. Read the known
// dictionary map directly on the hot path and retain getKey only for
// a malformed stream dictionary, where qpdf emits its type warning
// (`QPDFObjectHandle.cc:978-995`).
let (is_dictionary, value) = stream_dict.with_value(|value| match value {
Some(ObjectValue::Dictionary(entries)) => (true, entries.get(key).cloned()),
_ => (false, None),
});
let Some(value) = (if is_dictionary {
value
} else {
Some(stream_dict.try_get_key(key)?)
}) else {
continue;
};
let mut refs = Vec::new();
collect_direct_handle_refs(&value, 0, &mut refs)?;
if !refs.is_empty() {
return Ok(true);
}
}
Ok(false)
}
/// Probe one stream using the same policy as qpdf's linearized writer and
/// report whether `/Filter` and `/DecodeParms` will be removed.
fn stream_parameters_removed_for_linearization(
handle: &ObjectHandle,
stream_ref: Option<QpdfObjGen>,
options: &crate::writer::WriterOptions,
content_normalize_refs: &BTreeSet<QpdfObjGen>,
) -> Result<bool> {
// qpdf's linearization optimizer probes a token-filtered stream even when
// its /Filter and /DecodeParms entries are direct. That probe is
// observable because ValueSetter is stateful, so every stream shares the
// same writer-policy probe below regardless of isDataModified().
let normalize_content =
stream_ref.is_some_and(|object_gen| content_normalize_refs.contains(&object_gen));
crate::writer::plain::body::canonical_stream_will_be_refiltered_with_policy(
handle,
options,
true,
normalize_content,
) // cov:ignore: LLVM attributes the covered qpdf probe continuation to the call opening line
}
/// Collect indirect references from a live qpdf-shaped handle graph without
/// materializing the graph into an independent value snapshot.
///
/// An indirect child is recorded as one edge and expanded later by the
/// closure queue. Direct arrays, dictionaries, and stream dictionaries are
/// traversed in place. This mirrors qpdf's `QPDFObjectHandle` child access:
/// the handle identity is retained at each indirect boundary, while only the
/// current direct container is inspected.
fn collect_direct_handle_refs(
handle: &ObjectHandle,
depth: usize,
out: &mut Vec<ObjectRef>,
) -> Result<()> {
// qpdf-deviation: the qpdf writer's direct-container traversal has no MAX_PARSE_DEPTH cap.
if depth > MAX_PARSE_DEPTH {
return Err(crate::Error::Unsupported(format!(
"linearization plan: inline object nesting exceeds maximum of {MAX_PARSE_DEPTH}"
)));
}
let mut contextual = Vec::new();
collect_direct_handle_refs_with_context(handle, depth, false, &mut contextual)?;
out.extend(contextual.into_iter().map(|(object_ref, _)| object_ref));
Ok(())
}
fn collect_direct_handle_refs_with_stream_parameters(
handle: &ObjectHandle,
depth: usize,
out: &mut Vec<ObjectRef>,
skipped_stream_parameter_streams: &BTreeSet<QpdfObjGen>,
) -> Result<()> {
let mut contextual = Vec::new();
collect_direct_handle_refs_with_stream_parameters_context(
handle,
depth,
false,
&mut contextual,
skipped_stream_parameter_streams,
)?; // cov:ignore: thin projection into the context-carrying walker; its stream-policy branches are covered by the closure tests
out.extend(contextual.into_iter().map(|(object_ref, _)| object_ref));
Ok(())
}
/// Context-carrying form of [`collect_direct_handle_refs`]. The boolean is
/// true only when the edge to the indirect child came from an array element;
/// dictionary-value null references are removed by the qpdf writer and must
/// not resurrect a body object in the linearization plan.
fn collect_direct_handle_refs_with_context(
handle: &ObjectHandle,
depth: usize,
in_array: bool,
out: &mut Vec<(ObjectRef, bool)>,
) -> Result<()> {
// qpdf-deviation: qpdf linearization object-graph traversal has no MAX_PARSE_DEPTH cap for inline containers.
if depth > MAX_PARSE_DEPTH {
return Err(crate::Error::Unsupported(format!(
"linearization plan: inline object nesting exceeds maximum of {MAX_PARSE_DEPTH}"
)));
}
if let Some(object_ref) = handle.object_ref() {
out.push((object_ref, in_array));
return Ok(());
}
collect_direct_handle_children(
handle,
depth,
in_array,
&mut |child, child_depth, child_in_array| {
collect_direct_handle_refs_with_context(child, child_depth, child_in_array, out)
},
)
}
fn collect_direct_handle_refs_with_stream_parameters_context(
handle: &ObjectHandle,
depth: usize,
in_array: bool,
out: &mut Vec<(ObjectRef, bool)>,
skipped_stream_parameter_streams: &BTreeSet<QpdfObjGen>,
) -> Result<()> {
// qpdf-deviation: qpdf linearization object-graph traversal has no MAX_PARSE_DEPTH cap for inline containers.
if depth > MAX_PARSE_DEPTH {
return Err(crate::Error::Unsupported(format!(
"linearization plan: inline object nesting exceeds maximum of {MAX_PARSE_DEPTH}"
)));
}
if let Some(object_ref) = handle.object_ref() {
out.push((object_ref, in_array));
return Ok(());
}
collect_direct_handle_children_with_stream_parameters(
handle,
depth,
in_array,
skipped_stream_parameter_streams,
&mut |child, child_depth, child_in_array| {
collect_direct_handle_refs_with_stream_parameters_context(
child,
child_depth,
child_in_array,
out,
skipped_stream_parameter_streams,
)
},
)
}
/// Walk the direct children of one handle. The closure receives each child,
/// the incremented inline depth, and whether its edge came from an array.
fn collect_direct_handle_children<F>(
handle: &ObjectHandle,
depth: usize,
_parent_in_array: bool,
visit: &mut F,
) -> Result<()>
where
F: FnMut(&ObjectHandle, usize, bool) -> Result<()>,
{
collect_direct_handle_children_with_stream_parameters(
handle,
depth,
_parent_in_array,
&BTreeSet::new(),
visit,
)
}
fn collect_direct_handle_children_with_stream_parameters<F>(
handle: &ObjectHandle,
depth: usize,
_parent_in_array: bool,
skipped_stream_parameter_streams: &BTreeSet<QpdfObjGen>,
visit: &mut F,
) -> Result<()>
where
F: FnMut(&ObjectHandle, usize, bool) -> Result<()>,
{
handle.try_dereference()?;
let kind = handle.with_value(|value| match value {
Some(ObjectValue::Stream(stream)) => {
DirectContainerKind::Stream(stream.stream_dict.clone())
}
Some(ObjectValue::Array(_)) => DirectContainerKind::Array,
Some(ObjectValue::Dictionary(_)) => DirectContainerKind::Dictionary,
_ => DirectContainerKind::Scalar,
});
match kind {
DirectContainerKind::Stream(stream_dict) => {
// Resolve the dictionary handle before the live walk. qpdf reaches
// the same map through `getDictAsMap`, whose `asDictionary()` is
// `dereference() ? obj->as<QPDF_Dictionary>() : nullptr`
// (`QPDFObjectHandle.cc:1012-1020`, `:327-330`), so an indirect
// stream dictionary is resolved rather than treated as empty.
// `next_dictionary_entry_for_live_walk` inspects the stored value
// without resolving, so the deref has to happen here.
stream_dict.try_dereference()?;
let skip_stream_parameters =
handle_has_stream_parameter_skip(handle, skipped_stream_parameter_streams)?;
visit_live_dictionary_children(&stream_dict, depth, skip_stream_parameters, visit)?;
}
DirectContainerKind::Array => {
let items = handle.try_array_items()?;
let mut cursor = items.begin();
while !cursor.is_end() {
let child = cursor.current();
visit(&child, depth + 1, true)?;
cursor.next();
}
}
DirectContainerKind::Dictionary => {
visit_live_dictionary_children(handle, depth, false, visit)?;
}
DirectContainerKind::Scalar => {}
}
Ok(())
}
enum DirectContainerKind {
Stream(ObjectHandle),
Array,
Dictionary,
Scalar,
}
/// Visit one dictionary's children in qpdf's sorted-key order while keeping
/// only the current key and child handle alive across the callback. The
/// callback may resolve or mutate the child, so the parent value borrow must
/// be released before it is invoked (`QPDFWriter.cc:1488-1504`).
fn visit_live_dictionary_children<F>(
dictionary: &ObjectHandle,
depth: usize,
skip_stream_parameters: bool,
visit: &mut F,
) -> Result<()>
where
F: FnMut(&ObjectHandle, usize, bool) -> Result<()>,
{
let mut current_key = LiveDictionaryKeyBuffer::default();
let mut next_key = LiveDictionaryKeyBuffer::default();
let mut first_entry = true;
while let Some(child) = dictionary.next_dictionary_entry_for_live_walk(
(!first_entry).then_some(current_key.as_slice()),
&mut next_key,
) {
std::mem::swap(&mut current_key, &mut next_key);
if current_key.as_slice() == b"/Length"
|| (skip_stream_parameters
&& matches!(current_key.as_slice(), b"/Filter" | b"/DecodeParms"))
{
first_entry = false;
continue;
}
visit(&child, depth + 1, false)?;
first_entry = false;
}
Ok(())
}
fn handle_has_stream_parameter_skip(
handle: &ObjectHandle,
skipped_stream_parameter_streams: &BTreeSet<QpdfObjGen>,
) -> Result<bool> {
Ok(handle
.qpdf_obj_gen()
.is_some_and(|object_gen| skipped_stream_parameter_streams.contains(&object_gen)))
}
fn collect_handle_children_with_stream_parameters(
handle: &ObjectHandle,
depth: usize,
out: &mut Vec<(ObjectRef, bool)>,
skipped_stream_parameter_streams: &BTreeSet<QpdfObjGen>,
) -> Result<()> {
collect_direct_handle_children_with_stream_parameters(
handle,
depth,
false,
skipped_stream_parameter_streams,
&mut |child, child_depth, in_array| {
collect_direct_handle_refs_with_stream_parameters_context(
child,
child_depth,
in_array,
out,
skipped_stream_parameter_streams,
)
},
)
}
/// Returns whether a live handle is a page-tree interior or leaf node.
fn is_page_tree_handle(handle: &ObjectHandle) -> Result<bool> {
Ok(handle.try_is_dictionary_of_type(b"Pages", b"")?
|| handle.try_is_dictionary_of_type(b"Page", b"")?)
}
fn compute_closure_with_stream_parameters<R: Read + Seek>(
pdf: &mut Pdf<R>,
root: ObjectRef,
live: &BTreeSet<ObjectRef>,
resurrectable: &BTreeSet<ObjectRef>,
skipped_stream_parameter_streams: &BTreeSet<QpdfObjGen>,
) -> crate::Result<Vec<ObjectRef>> {
let mut visited: BTreeSet<ObjectRef> = BTreeSet::new();
let mut order: Vec<ObjectRef> = Vec::new();
// Each entry carries (ref, via_array): whether the ref was enqueued via an
// array element (true) or a dictionary value (false). Used at dequeue time
// to admit resurrectable null refs only when the reaching edge is a
// surviving array slot — matching qpdf's object-user classification, which
// excludes dict-value edges that the writer drops entirely.
let mut queue: VecDeque<(ObjectRef, bool)> = VecDeque::from([(root, false)]);
// Resurrectable refs that were not admissible at dequeue time (seen_as_array
// did not yet contain them — the live object holding the array edge had not
// been expanded yet). After the full BFS completes, seen_as_array is
// exhaustive; we then admit each deferred ref that appears there. This
// handles the "revorder" case: resurrectable ref number < live descendant
// number, so sort-at-enqueue puts the resurrectable ref in the queue before
// the live object that would reveal the array edge.
let mut deferred_resurrect: BTreeSet<ObjectRef> = BTreeSet::new();
// Tracks every ref that has been enqueued (or pushed to the Resources DFS
// stack) via an array-element edge within this closure walk. A resurrectable
// ref that appears in *both* a dict-value slot (dropped by the writer) and an
// array slot (survives as null) within the same page's closure must still be
// admitted: the dict-value tuple (r, false) may be dequeued before the
// array-edge tuple (r, true), but `seen_as_array` lets the dequeue check
// consult all edges discovered so far, not just the one in the current tuple.
let mut seen_as_array: BTreeSet<ObjectRef> = BTreeSet::new();
// Object 0 (free-list head / null singleton, ISO 32000-1 §7.3.10) and all
// null-resolving references have no ordinary body here. The holding dict key
// is dropped, while an array keeps the indirect null identity only through
// the `resurrectable` path below. Keeping other nulls in `visited` but out of
// `order` avoids a stray numbered body and an inflated first-page count.
//
// Exception: null-resolving refs reached via a surviving array edge in this
// page's object graph are resurrectable (see `resurrectable_null_refs`). qpdf
// classifies them as first-page users when reached from a first-page object,
// giving them HIGH object numbers inside Part 2. A null ref reached only via
// a dict value is dropped (not resurrectable), so it stays excluded.
let admits_body_object = |r: ObjectRef| -> bool { r.number != 0 && live.contains(&r) };
while let Some((current, via_array)) = queue.pop_front() {
if !visited.insert(current) {
continue;
}
if resurrectable.contains(¤t) {
// Null-resolving ref: the writer preserves array-element slots as
// null but drops dict-value slots (the key is omitted entirely). Only
// admit to the closure when an array edge exists — a ref reached
// solely via dict-value edges has no surviving body object in the
// first-page section, matching qpdf's object-user map which does not
// count dropped dict-value edges as page uses.
// `via_array` covers the common case; `seen_as_array` covers the case
// where the same ref appears in both a dict-value slot and an array
// slot in the same closure (the dict-value tuple may be dequeued first,
// but the array edge was already recorded at enqueue time).
// `deferred_resurrect` handles the "revorder" case: resurrectable ref
// number < live descendant number, so the resurrectable ref is dequeued
// before seen_as_array is populated. Deferred refs are re-checked
// after the full BFS completes.
if via_array || seen_as_array.contains(¤t) {
order.push(current);
} else {
deferred_resurrect.insert(current);
}
continue;
}
if !admits_body_object(current) {
continue;
}
order.push(current);
let current_handle = pdf.get_object_handle(current);
// Determine whether this is a Pages node (intermediate page-tree node)
// or a Page leaf node.
let is_pages_node = current_handle.try_is_dictionary_of_type(b"Pages", b"")?;
let is_page_leaf = current_handle.try_is_dictionary_of_type(b"Page", b"")?;
if is_pages_node || is_page_leaf {
if let Some(dict) = current_handle.try_as_dictionary()? {
// For a page leaf, expand the `/Resources` subtree depth-first
// and append it to `order` *before* the generic key loop runs.
// flpdf's `Dictionary` is a `BTreeMap`, so a plain key walk
// would visit `/Contents` (alphabetically first) before
// `/Resources`; qpdf instead numbers the Resources dictionary
// and the fonts/XObjects it references ahead of the content
// stream. Reproducing that order here is what makes the
// first-page object numbering match qpdf (e.g. one-page:
// Page, Resources, Font, Content). The depth-first walk is
// required because the content stream sits at depth 1 while a
// font hangs at depth 2 under `/Resources`; a breadth-first
// pass would otherwise emit the content stream first.
if is_page_leaf {
{
let resources = current_handle.try_get_key(b"/Resources")?;
let mut seeds: Vec<(ObjectRef, bool)> = Vec::new();
collect_direct_handle_refs_with_context(&resources, 0, false, &mut seeds)?;
for &(r, va) in &seeds {
if va {
seen_as_array.insert(r);
}
}
// DFS via an explicit stack (no recursion) so deeply
// nested resource graphs cannot overflow the stack.
// The visited set bounds cycles; `is_page_tree_handle`
// stops the walk if a resource value cross-links back
// into the page tree, so we never pull in sibling pages.
let mut stack: Vec<(ObjectRef, bool)> = seeds.into_iter().rev().collect();
while let Some((r, via_array)) = stack.pop() {
if !visited.insert(r) {
continue;
}
if resurrectable.contains(&r) {
// Same edge-type rule as the main BFS: admit the
// null body object only when an array edge exists.
// Defer if seen_as_array not yet populated (revorder
// case); the post-BFS pass will re-check.
if via_array || seen_as_array.contains(&r) {
order.push(r);
} else {
// cov:ignore-start: fires when a resurrectable ref is reachable via dict-value in the Resources subtree before the array edge in the same subtree is discovered; requires two resource objects cross-referencing the same xref-absent object via different edge types, which is extremely contrived
deferred_resurrect.insert(r);
} // cov:ignore-end
continue;
}
if !admits_body_object(r) {
// Null-resolving resource ref (object 0 / missing
// xref): no body object, same as the main loop.
continue;
}
let child_handle = pdf.get_object_handle(r);
// Stop at a page-tree boundary BEFORE adding `r` to
// the closure: a resource that malformedly cross-links
// to a sibling `/Page` or the `/Pages` node must be
// kept in `visited` (so it is never revisited) but
// excluded from the first-page closure entirely — per
// the page-closure boundary rule, we neither descend
// into it nor pull the boundary node itself into
// Part 2/3.
if is_page_tree_handle(&child_handle)? {
continue;
}
order.push(r);
let mut child_refs: Vec<(ObjectRef, bool)> = Vec::new();
collect_handle_children_with_stream_parameters(
&child_handle,
0,
&mut child_refs,
skipped_stream_parameter_streams,
)?;
// Push in reverse so the first reference is popped
// first, preserving left-to-right discovery order.
for cr in child_refs.into_iter().rev() {
if cr.1 {
seen_as_array.insert(cr.0);
}
if !visited.contains(&cr.0) {
stack.push(cr);
}
}
}
}
} // cov:ignore: llvm-cov attributes 0 to this `if is_page_leaf` closing brace; the block body (the /Resources DFS) runs and is covered above.
let mut refs_raw: Vec<(ObjectRef, bool)> = Vec::new();
for (k, v) in dict.iter() {
if k == b"/Kids" {
// Pages → sibling pages — never follow.
continue;
}
if k == b"/Thumb" {
// qpdf gives thumbnail objects the separate ou_thumb
// user (not a page user), so page closures never
// include /Thumb targets. Skipping here ensures
// thumbnail objects land in part4_rest (part 9)
// rather than the per-page private/shared sections.
continue;
}
if k == b"/Parent" {
// Walk the /Parent chain up to the root Pages node so
// inherited /Resources, /MediaBox, /Rotate, etc. from
// any ancestor (not just the immediate parent) end up
// in this page's closure. Without iterating to the
// root, a `/Page → /Pages → /Pages` tree with the
// inherited resource attached to the grandparent
// would leave that resource unreachable from any
// page's closure and land it in `part4_rest`,
// misclassifying it relative to qpdf's part7/8/9
// partition.
//
// The ancestor /Pages dicts themselves are NOT added
// to this page's closure — adding them would inflate
// the page's object_count beyond what qpdf computes
// from the linearized layout. We follow each
// ancestor's non-/Kids, non-/Parent entries and let
// the queue traverse into ref targets normally.
let mut to_visit: Vec<ObjectRef> = Vec::new();
let mut seen_parents: BTreeSet<ObjectRef> = BTreeSet::new();
collect_direct_handle_refs_with_stream_parameters(
v,
0,
&mut to_visit,
skipped_stream_parameter_streams,
)?; // cov:ignore: LLVM maps this covered parent-seed call terminator to a zero-count continuation region
while let Some(parent_ref) = to_visit.pop() {
if !seen_parents.insert(parent_ref) {
continue;
}
// Resolve the parent. Genuine resolve failures
// (I/O or parse errors) propagate via `?` instead
// of silently degrading the closure — mirroring
// the main BFS loop's canonical parent-handle resolution.
let parent_handle = pdf.get_object_handle(parent_ref);
// `parent_handle` is the canonical object for
// `parent_ref`; its `object_ref()` is identity,
// not a stored reference value. Inspect the live
// dictionary below so the ancestor's inherited
// entries are actually added to the closure.
let Some(parent_dict) = parent_handle.try_as_dictionary()? else {
// Any other non-dictionary parent (a free or
// missing object resolving to Null, etc.) is
// tolerated: the walk just climbs past it.
continue;
};
for (pk, pv) in parent_dict.iter() {
if pk == b"/Kids" {
continue;
}
if pk == b"/Parent" {
// Climb to the next ancestor instead of
// stopping at one level.
collect_direct_handle_refs(pv, 0, &mut to_visit)?;
continue;
}
let mut refs: Vec<(ObjectRef, bool)> = Vec::new();
collect_direct_handle_refs_with_stream_parameters_context(
pv,
0,
false,
&mut refs,
skipped_stream_parameter_streams,
)?; // cov:ignore: LLVM maps this covered ancestor-entry call terminator to a zero-count continuation region
for (r, va) in refs {
if va {
seen_as_array.insert(r);
}
if !visited.contains(&r) {
queue.push_back((r, va));
}
}
}
}
continue;
}
collect_direct_handle_refs_with_stream_parameters_context(
v,
0,
false,
&mut refs_raw,
skipped_stream_parameter_streams,
)?; // cov:ignore: LLVM maps this covered page-entry call terminator to a zero-count continuation region
}
for &(r, va) in &refs_raw {
if va {
seen_as_array.insert(r);
}
}
// Sort by original object number: qpdf assigns first-page slots in
// ascending original-number order regardless of dict key alphabetical
// order (empirically verified; see discriminator-fixture analysis).
refs_raw.sort_by_key(|(r, _)| pdf.writer_object_order_key(*r));
for (r, va) in refs_raw {
if !visited.contains(&r) {
queue.push_back((r, va));
}
}
}
} else {
let mut refs: Vec<(ObjectRef, bool)> = Vec::new();
collect_handle_children_with_stream_parameters(
¤t_handle,
0,
&mut refs,
skipped_stream_parameter_streams,
)?; // cov:ignore: LLVM maps this covered ordinary-object call terminator to a zero-count continuation region
for &(r, va) in &refs {
if va {
seen_as_array.insert(r);
}
}
// Same number-ordering rule as the page-dict loop above: qpdf enqueues
// a non-page object's children in ascending original-object-number order,
// not in dict-key (alphabetical) order.
refs.sort_by_key(|(r, _)| pdf.writer_object_order_key(*r));
for (r, va) in refs {
if !visited.contains(&r) {
queue.push_back((r, va));
}
}
}
}
// Sort the non-page tail (order[1..]) by original object number. qpdf emits
// first-page objects in ascending original-number order, with the Page leaf
// always in the first slot. Two discriminator fixtures confirm this:
// (a) Resources(5)/Font(6) at higher numbers than Content(4) → numeric order
// wins over Resources-DFS-first order;
// (b) Page(orig 10) with Content(orig 3) → Page stays first despite having a
// higher original number, so a fully-global sort would misplace it.
// Sorting only order[1..] satisfies both invariants simultaneously.
// A multi-source page-selection target carries qpdf's source/discovery
// order separately from its fresh references (see
// `Pdf::writer_object_order_key`); ordinary documents resolve to
// the same ascending original-number order as before.
if order.len() > 1 {
order[1..].sort_by_key(|r| pdf.writer_object_order_key(*r));
}
// Deferred resurrectable refs: now that the full BFS is complete and
// seen_as_array is exhaustive, admit those that turn out to be reachable
// via an array edge (i.e. they appear in seen_as_array). Insert each at
// the numerically correct position in the already-sorted non-page tail so
// the Page leaf remains first and the overall tail ordering stays ascending.
// BTreeSet iterates in ascending order, so each insertion preserves the
// invariant for subsequent entries.
for r in deferred_resurrect {
if seen_as_array.contains(&r) {
let tail_pos = order[1..].partition_point(|existing| existing.number < r.number);
order.insert(1 + tail_pos, r);
} // cov:ignore: false branch = deferred ref that has no array edge in the entire closure; qpdf correctly drops it (same as the dict-value-only drop path). Requires a resurrectable ref that appears *only* in a dict-value slot with no array counterpart anywhere in the closure — correctly exercised by the existing behaviour but the closing brace hits only the zero-count path.
}
Ok(order)
}
// ---------------------------------------------------------------------------
// LinearizationPlan
// ---------------------------------------------------------------------------
/// Raw identity backing for [`LinearizationPlan`]. The public plan fields
/// below are checked `ObjectRef` projections; this is the writer-facing source
/// of truth and therefore keeps object generations that cannot be represented
/// by an indirect PDF reference.
#[allow(dead_code)]
#[derive(Debug, Clone, Default)]
pub(crate) struct RawLinearizationPlan {
pub(crate) part2_objects: Vec<QpdfObjGen>,
pub(crate) part3_objects: Vec<QpdfObjGen>,
pub(crate) part4_other_pages_private: Vec<QpdfObjGen>,
pub(crate) part4_other_pages_shared: Vec<QpdfObjGen>,
pub(crate) part4_rest: Vec<QpdfObjGen>,
pub(crate) part4_open_document_plain: Vec<QpdfObjGen>,
pub(crate) root: Option<QpdfObjGen>,
pub(crate) pages_tree: Option<QpdfObjGen>,
pub(crate) info: Option<QpdfObjGen>,
pub(crate) per_page_private_objects: Vec<Vec<QpdfObjGen>>,
/// qpdf Part-9 thumbnail objects in emitted order: private thumbnails
/// grouped by page, followed by shared thumbnails.
pub(crate) part9_thumbnail_objects: Vec<QpdfObjGen>,
pub(crate) outline_first_page_members: Vec<QpdfObjGen>,
pub(crate) part9_outline_objects: Vec<QpdfObjGen>,
pub(crate) part6_outline_objects: Vec<QpdfObjGen>,
pub(crate) content_normalize_refs: BTreeSet<QpdfObjGen>,
pub(crate) removed_refs: BTreeSet<QpdfObjGen>,
pub(crate) shared_hints: Vec<RawSharedObjectHintEntry>,
/// Whether any raw part list contains an identity that cannot be projected
/// to the checked `ObjectRef` representation. qpdf keeps ObjGen as its
/// only identity; flpdf's checked views retain this one plan-time route
/// decision for the bounded migration surface that still exposes them.
pub(crate) projection_gap: bool,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct RawSharedObjectHintEntry {
pub(crate) object: Option<QpdfObjGen>,
pub(crate) container: Option<u32>,
pub(crate) referencing_pages: Vec<u32>,
}
/// Partition of a PDF document's objects into the four linearization parts
/// defined by ISO 32000-1 Annex F, together with the raw inputs for the
/// page-offset and shared-object hint tables.
///
/// Constructed from a [`Pdf`] handle via [`LinearizationPlan::from_pdf`].
/// This struct owns all data it needs and holds no reference into the source
/// document.
///
/// # Object disjointness
///
/// The four part lists are disjoint by construction. `from_pdf` computes the
/// first-page closure, partitions it into Part 2 (exclusive) and Part 3
/// (shared with other pages), and removes the moved objects from Part 4 so
/// the invariant is always maintained. The free-list head at object 0 is
/// excluded from Part 4 entirely (ISO 32000-1 §7.5.4).
#[derive(Debug, Clone)]
pub struct LinearizationPlan {
// ------------------------------------------------------------------
// Part membership
// ------------------------------------------------------------------
/// Part 1: linearization parameter dictionary and its xref stream.
/// Reserved for the linearization parameter dictionary and its xref
/// stream; plans built from a PDF leave this list empty.
pub part1_objects: Vec<ObjectRef>,
/// Part 2: first-page objects (page dict, resources, content streams).
/// Computed by `from_pdf` using the first-page closure algorithm.
pub part2_objects: Vec<ObjectRef>,
/// Part 3: non-first-page shared objects (objects referenced by both
/// page 1 and at least one other page).
/// Computed by `from_pdf`.
pub part3_objects: Vec<ObjectRef>,
/// Objects private to exactly one other page (pages 2..N).
///
/// Ordered by page index, then by BFS closure order within each page.
///
/// qpdf correspondence: linearization part7.
pub part4_other_pages_private: Vec<ObjectRef>,
/// Objects shared by two or more other pages (pages 2..N), but NOT
/// reachable from page 1.
///
/// qpdf correspondence: linearization part8.
pub part4_other_pages_shared: Vec<ObjectRef>,
/// All Part-4 objects that are not in part7 or part8.
/// Includes the Pages tree, Info dict, lc_other objects, and any objects
/// not reachable from any page closure (trailer-only refs, etc.).
///
/// qpdf correspondence: linearization part9.
pub part4_rest: Vec<ObjectRef>,
// ------------------------------------------------------------------
// Document summary (copied from the source at construction time)
// ------------------------------------------------------------------
/// Total number of objects as reported by the xref table.
pub total_object_count: u32,
/// `/Root` reference from the trailer, if present.
pub root_ref: Option<ObjectRef>,
/// `/Pages` tree root reference (catalog's `/Pages` entry).
///
/// Promoted into the renumber map's reserved prefix so the resulting
/// object number matches qpdf's `part9` head (qpdf assigns the pages
/// tree to object 1). May be `None` for malformed inputs missing this
/// entry; in that case no promotion happens.
pub pages_tree_ref: Option<ObjectRef>,
/// `/Info` reference from the trailer, if present.
///
/// Promoted into the renumber map's reserved prefix to mirror qpdf's
/// `lc_other` ordering (Info follows pages tree in the second-half
/// renumber pass).
pub info_ref: Option<ObjectRef>,
// ------------------------------------------------------------------
// Hint table inputs
// ------------------------------------------------------------------
/// Page-offset hint table inputs (one entry per page).
///
/// Entry 0 has `object_count` set to the number of Part-2 objects and
/// `first_object_index` set to 0. `byte_length` remains a placeholder (0)
/// for back-patching by the writer.
pub page_hints: Vec<PageHintEntry>,
/// Shared-object hint table inputs.
///
/// One entry per Part-3 object; `referencing_pages` lists the 0-based
/// page indices (across all pages) that reach this object.
pub shared_hints: Vec<SharedObjectHintEntry>,
/// Per-page private object lists for byte-length computation.
///
/// `per_page_private_objects[i]` is the list of objects that belong
/// exclusively to page `i` (not shared with any other page):
///
/// * For page 0: equal to `part2_objects`.
/// * For pages 1..N: the objects in that page's closure that are
/// **not** in Part 2 or Part 3 (i.e. they are private to this page
/// within Part 4).
///
/// The writer uses these lists to compute `page_hints[i].byte_length`
/// and to populate the Page Offset Hint Table's `page_length_minus_least`
/// and `least_page_length` fields.
pub per_page_private_objects: Vec<Vec<ObjectRef>>,
/// qpdf Part-9 thumbnail objects in emitted order: private thumbnails
/// grouped by page, followed by shared thumbnails. These objects remain in
/// `part4_rest`; this vector is ordering metadata consumed by the classic
/// renumberer, not a second membership list.
pub(crate) part9_thumbnail_objects: Vec<ObjectRef>,
/// Outline objects routed to the first-page section (part6) when the catalog
/// specifies `/PageMode /UseOutlines`, in emitted order (root first, then items
/// in traversal order). Empty when the predicate is false.
///
/// Ordered to match qpdf's `lc_outlines` traversal order so that `shared_hints`
/// entries are in the same sequence as physically emitted objects.
/// Used by `page0_object_count_with_objstm` to include the outline ObjStm
/// container in the page-0 object count (qpdf counts all part6 objects in
/// `entries.at(0).nobjects`, including outlines placed there when
/// `outlines_in_first_page` is set).
pub(crate) outline_first_page_members: Vec<ObjectRef>,
/// Outline objects for the classic (non-ObjStm) linearize path when
/// `/PageMode` is NOT `/UseOutlines`. Extracted from `part4_rest` and
/// assigned consecutive second-half object numbers (between `pages_tree`
/// and `info/param_dict` in the renumber map), then emitted after /E.
/// Matches qpdf's `lc_outlines` (part9) placement. Empty when
/// `UseOutlines` is active or when there are no outlines.
pub(crate) part9_outline_objects: Vec<ObjectRef>,
/// Outline objects for the classic (non-ObjStm) linearize path when
/// `/PageMode /UseOutlines` is set. Extracted from `part4_rest` and
/// given first-half numbers (after Part 3 in the renumber map), then
/// emitted **before** /E (between Part 3 and the /E boundary). Matches
/// qpdf's `lc_outlines` (part6) placement. Empty when `UseOutlines` is
/// not set or when there are no outlines.
pub(crate) part6_outline_objects: Vec<ObjectRef>,
/// Open-document objects (qpdf part4 = `lc_open_document`) emitted as plain
/// indirect objects in the pre-/O region, immediately after the Catalog, in
/// ascending source object number order.
///
/// In disable/preserve mode this holds the FULL open-document set — every
/// object reachable from the catalog open-document keys (`/OpenAction`,
/// `/AcroForm`, `/PageMode`, `/Threads`, `/ViewerPreferences`) and trailer
/// `/Encrypt`. In generate mode it holds only the ObjStm-ineligible subset
/// (e.g. stream objects such as `/AP /N` appearance streams that cannot be
/// ObjStm members); the eligible ones are packed into the open-document ObjStm
/// container instead.
///
/// Empty only when the document has no open-document objects (or, in generate
/// mode, when all of them are ObjStm-eligible).
pub part4_open_document_plain: Vec<ObjectRef>,
/// qpdf destination-object ordering projected onto a fresh page-selection
/// target. Ordinary parsed documents leave this absent and use their live
/// `ObjectRef` order. The hint builder needs this same projection when a
/// page references shared objects from different linearization sections.
pub(crate) writer_object_order: Option<BTreeMap<ObjectRef, WriterObjectOrderKey>>,
/// Retained qpdf-style bidirectional object-user map used to route generated
/// and preserved ObjStm containers without re-reading the PDF.
pub(crate) optimization: Option<crate::optimization::Optimization>,
/// Setup-owned Preserve source membership, retained through linearization
/// planning so the source-container identity is not reconstructed by a
/// later batch consumer. qpdf captures this map before optimization and
/// then folds object users onto the same containers.
pub(crate) preserve_objstm_plan: Option<crate::writer::object_streams::ObjectStreamPlan>,
/// Terminal indirect page-content stream refs, matching the plain
/// writer's `contents_seq` identity gate. Empty when
/// `options.content_normalization` was off. The writer must reuse this
/// exact set (not recompute it) so a stream's plan-time refilter probe
/// and its real emission agree on whether content normalization
/// applies, mirroring qpdf's single `m->normalized_streams` set shared
/// between `willFilterStream` and emission (`QPDFWriter.cc:1277`).
#[allow(dead_code)]
pub(crate) content_normalize_refs: BTreeSet<ObjectRef>,
/// Live source generations that qpdf drops while planning generated or
/// preserved object streams. References to these objects are rewritten as
/// qpdf-null values even though the source xref entry itself is live.
#[allow(dead_code)]
pub(crate) removed_refs: BTreeSet<ObjectRef>,
/// Object-stream mode whose traversal and stale-generation rules produced
/// this plan. The writer reconciles a legacy boolean plan with its final
/// [`WriterOptions`](crate::writer::WriterOptions) mode before using the plan's
/// partitions and renumbering.
pub(crate) object_stream_mode: crate::writer::ObjectStreamMode,
/// Raw qpdf identity plan consumed by linearization serialization.
pub(crate) raw: RawLinearizationPlan,
}
fn raw_refs_from_object_refs(refs: impl IntoIterator<Item = ObjectRef>) -> Vec<QpdfObjGen> {
refs.into_iter()
.filter_map(|object_ref| QpdfObjGen::try_from_object_ref(object_ref).ok())
.collect()
}
fn raw_refs_with_extras(
refs: impl IntoIterator<Item = ObjectRef>,
extras: impl IntoIterator<Item = QpdfObjGen>,
sort: bool,
) -> Vec<QpdfObjGen> {
let extras: Vec<_> = extras.into_iter().collect();
let mut result = raw_refs_from_object_refs(refs);
result.extend(extras.iter().copied());
if sort && !extras.is_empty() {
result.sort_unstable();
}
result
}
fn canonical_preserve_ref(
source_container_by_member: &BTreeMap<ObjectRef, ObjectRef>,
object_ref: ObjectRef,
) -> ObjectRef {
source_container_by_member
.get(&object_ref)
.copied()
.unwrap_or(object_ref)
}
fn canonicalize_preserve_refs(
source_container_by_member: &BTreeMap<ObjectRef, ObjectRef>,
refs: Vec<ObjectRef>,
) -> Vec<ObjectRef> {
if source_container_by_member.is_empty() {
return refs;
}
let mut seen = BTreeSet::new();
refs.into_iter()
.map(|object_ref| canonical_preserve_ref(source_container_by_member, object_ref))
.filter(|object_ref| seen.insert(*object_ref))
.collect()
}
fn raw_refs_with_extras_preserving_first(
refs: impl IntoIterator<Item = ObjectRef>,
extras: impl IntoIterator<Item = QpdfObjGen>,
) -> Vec<QpdfObjGen> {
let mut result = raw_refs_from_object_refs(refs);
let first = result.first().copied();
let extras: Vec<_> = extras.into_iter().collect();
result.extend(extras.iter().copied());
if !extras.is_empty() && result.len() > 1 {
result[1..].sort_unstable();
}
if let Some(first) = first {
if let Some(position) = result.iter().position(|object| *object == first) {
result.remove(position);
result.insert(0, first);
}
} // cov:ignore: the first projected identity is inserted before the optional raw extras, so LLVM attributes this identity-preservation closing brace to an uncovered branch
result
}
fn raw_refs_with_extras_root_first(
refs: impl IntoIterator<Item = ObjectRef>,
extras: impl IntoIterator<Item = QpdfObjGen>,
root: Option<QpdfObjGen>,
) -> Vec<QpdfObjGen> {
let mut result = raw_refs_from_object_refs(refs);
result.extend(extras);
result.sort_unstable();
if let Some(root) = root {
if let Some(position) = result.iter().position(|object| *object == root) {
result.remove(position);
result.insert(0, root);
}
}
result
}
#[allow(clippy::too_many_arguments)]
#[inline(never)]
fn build_raw_linearization_plan<R: Read + Seek>(
pdf: &mut Pdf<R>,
optimization: &crate::optimization::Optimization,
part2_objects: &[ObjectRef],
part3_objects: &[ObjectRef],
part4_other_pages_shared: &[ObjectRef],
part4_rest: &[ObjectRef],
part4_open_document_plain: &[ObjectRef],
per_page_private_objects: &[Vec<ObjectRef>],
page_refs: &[ObjectRef],
part9_outline_objects: &[ObjectRef],
part6_outline_objects: &[ObjectRef],
root_ref: Option<ObjectRef>,
pages_tree_ref: Option<ObjectRef>,
info_ref: Option<ObjectRef>,
content_normalize_refs: &BTreeSet<QpdfObjGen>,
removed_refs: &BTreeSet<ObjectRef>,
outlines_in_first_page: bool,
) -> Result<RawLinearizationPlan> {
let raw_removed_refs: BTreeSet<QpdfObjGen> = removed_refs
.iter()
.filter_map(|object_ref| QpdfObjGen::try_from_object_ref(*object_ref).ok())
.collect();
let outline_refs = optimization.raw_objects_for_root_key(b"Outlines");
let open_document_refs: BTreeSet<QpdfObjGen> = optimization
.raw_objects_for_trailer_key(b"Encrypt")
.into_iter()
.chain(
OPEN_DOCUMENT_CATALOG_KEYS
.into_iter()
.flat_map(|key| optimization.raw_objects_for_root_key(key)),
)
.collect();
let thumbnail_refs = optimization.raw_thumbnail_objects();
let mut raw_part2_extra = Vec::new();
let mut raw_part3_extra = Vec::new();
let mut raw_part4_shared_extra = Vec::new();
let mut raw_part4_rest_extra = Vec::new();
let mut raw_open_document_plain_extra = Vec::new();
let mut raw_private_by_page: BTreeMap<u32, Vec<QpdfObjGen>> = BTreeMap::new();
// `Optimization` has already traversed every qpdf user root. Its raw
// inverse is therefore the authoritative reachable universe for source
// identities that have no checked `ObjectRef` projection. Structural
// stream objects are writer-owned xref/ObjStm machinery, not body objects.
for (object_gen, users) in optimization.raw_object_users() {
if object_gen.to_object_ref().is_some()
|| object_gen.get_obj() <= 0
|| raw_removed_refs.contains(&object_gen)
{
continue;
}
let object =
pdf.get_object_handle_by_raw_identity(object_gen.get_obj(), object_gen.get_gen());
// cov:ignore-start: linearization object-user maps do not admit writer-owned structural streams as raw body identities
if object.try_is_stream_of_type(b"XRef", b"")?
|| object.try_is_stream_of_type(b"ObjStm", b"")?
{
continue;
}
// cov:ignore-end
let page_users: Vec<u32> = optimization.raw_page_users(object_gen).collect();
let in_first_page = page_users.contains(&0);
let in_other_page = page_users.iter().any(|page| *page != 0);
let in_outline = outline_refs.contains(&object_gen);
let in_open_document = open_document_refs.contains(&object_gen);
let in_document_other = users.iter().any(is_document_other_user);
let in_thumbnail = thumbnail_refs.contains(&object_gen);
if in_outline {
raw_part4_rest_extra.push(object_gen);
} else if in_open_document {
// Raw generations cannot cross the ObjStm member boundary, so the
// open-document raw object always remains a plain object before
// the hint stream.
raw_open_document_plain_extra.push(object_gen);
} else if in_first_page {
if in_other_page || in_document_other || in_thumbnail {
raw_part3_extra.push(object_gen);
} else {
raw_part2_extra.push(object_gen);
}
} else if let Some(page) = optimization.raw_other_page_private_owner(object_gen) {
raw_private_by_page
.entry(page)
.or_default()
.push(object_gen);
} else if page_users.len() >= 2 {
raw_part4_shared_extra.push(object_gen);
} else {
raw_part4_rest_extra.push(object_gen);
}
}
raw_part4_shared_extra.sort_unstable();
raw_part4_rest_extra.sort_unstable();
raw_open_document_plain_extra.sort_unstable();
let mut raw_per_page_private_objects = per_page_private_objects
.iter()
.map(|objects| raw_refs_from_object_refs(objects.iter().copied()))
.collect::<Vec<_>>();
for (page, objects) in raw_private_by_page {
if let Some(destination) = raw_per_page_private_objects.get_mut(page as usize) {
destination.extend(objects);
}
}
// qpdf emits Part 7 one page at a time. The page dictionary is the explicit
// head of each page group; every remaining member comes from that page's
// `std::set<QPDFObjGen>` user set. Merge raw-only members into the owning
// page before sorting the tail so a raw identity cannot be appended after
// all checked private objects from every page.
for objects in raw_per_page_private_objects.iter_mut().skip(1) {
if objects.len() > 1 {
objects[1..].sort_unstable();
}
}
let raw_part4_private: Vec<QpdfObjGen> = raw_per_page_private_objects
.iter()
.skip(1)
.flatten()
.copied()
.collect();
let raw_part6_outline_extra: Vec<_> = if outlines_in_first_page {
raw_part4_rest_extra
.iter()
.copied()
.filter(|object_gen| outline_refs.contains(object_gen))
.collect()
} else {
Vec::new()
};
let raw_part9_outline_extra: Vec<_> = if outlines_in_first_page {
Vec::new()
} else {
raw_part4_rest_extra
.iter()
.copied()
.filter(|object_gen| outline_refs.contains(object_gen))
.collect()
};
raw_part4_rest_extra.retain(|object_gen| !outline_refs.contains(object_gen));
let outline_root = pdf
.root_handle()?
.try_get_key(b"/Outlines")?
.qpdf_obj_gen()
.filter(|object_gen| object_gen.is_indirect());
let raw_part6_outline_objects = raw_refs_with_extras_root_first(
part6_outline_objects.iter().copied(),
raw_part6_outline_extra.clone(),
outline_root,
);
let raw_part9_outline_objects = raw_refs_with_extras_root_first(
part9_outline_objects.iter().copied(),
raw_part9_outline_extra.clone(),
outline_root,
);
let raw_part4_rest =
raw_refs_with_extras(part4_rest.iter().copied(), raw_part4_rest_extra, true);
let raw_part4_rest_set: BTreeSet<QpdfObjGen> = raw_part4_rest.iter().copied().collect();
let raw_part9_thumbnail_objects =
part9_thumbnail_objects(pdf, optimization, page_refs, &raw_part4_rest_set)?;
let raw_shared_hints = raw_part2_objects_for_hints(
&raw_refs_with_extras_preserving_first(
part2_objects.iter().copied(),
raw_part2_extra.clone(),
),
&raw_refs_with_extras(part3_objects.iter().copied(), raw_part3_extra.clone(), true),
&raw_part6_outline_objects,
&raw_refs_with_extras(
part4_other_pages_shared.iter().copied(),
raw_part4_shared_extra.clone(),
true,
),
optimization,
);
let mut raw = RawLinearizationPlan {
part2_objects: raw_refs_with_extras_preserving_first(
part2_objects.iter().copied(),
raw_part2_extra,
),
part3_objects: raw_refs_with_extras(part3_objects.iter().copied(), raw_part3_extra, true),
part4_other_pages_private: raw_part4_private,
part4_other_pages_shared: raw_refs_with_extras(
part4_other_pages_shared.iter().copied(),
raw_part4_shared_extra,
true,
),
part4_rest: raw_part4_rest,
part4_open_document_plain: raw_refs_with_extras(
part4_open_document_plain.iter().copied(),
raw_open_document_plain_extra,
true,
),
root: root_ref.and_then(|object_ref| QpdfObjGen::try_from_object_ref(object_ref).ok()),
pages_tree: pages_tree_ref
.and_then(|object_ref| QpdfObjGen::try_from_object_ref(object_ref).ok()),
info: info_ref.and_then(|object_ref| QpdfObjGen::try_from_object_ref(object_ref).ok()),
per_page_private_objects: raw_per_page_private_objects,
part9_thumbnail_objects: raw_part9_thumbnail_objects,
outline_first_page_members: raw_part6_outline_objects.clone(),
part9_outline_objects: raw_part9_outline_objects,
part6_outline_objects: raw_part6_outline_objects,
content_normalize_refs: content_normalize_refs.clone(),
removed_refs: raw_removed_refs,
shared_hints: raw_shared_hints,
projection_gap: false,
};
raw.projection_gap = raw.compute_projection_gap();
Ok(raw)
}
impl RawLinearizationPlan {
fn compute_projection_gap(&self) -> bool {
self.part2_objects
.iter()
.chain(&self.part3_objects)
.chain(&self.part4_other_pages_private)
.chain(&self.part4_other_pages_shared)
.chain(&self.part4_rest)
.chain(&self.part4_open_document_plain)
.chain(&self.part6_outline_objects)
.chain(&self.part9_outline_objects)
.any(|object_gen| object_gen.to_object_ref().is_none())
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Part9ThumbnailCategory {
Private(u32),
Shared,
}
/// Classify one object using qpdf's Part-9 precedence, limited to the two
/// thumbnail categories that are emitted by the classic linearization path.
/// `users` is the post-optimization object-user set; its values already carry
/// the shared-visited semantics of `QPDF::updateObjectMapsInternal`.
fn part9_thumbnail_category(
users: &crate::optimization::CompactObjectUserSet,
) -> Option<Part9ThumbnailCategory> {
let mut other_pages = BTreeSet::new();
let mut thumbnail_pages = BTreeSet::new();
let mut has_page_zero = false;
let mut has_root = false;
let mut has_outline = false;
let mut has_open_document = false;
let mut has_document_other = false;
for user in users.iter() {
match user {
crate::optimization::ObjectUser::Page(page) => {
if *page == 0 {
has_page_zero = true;
} else {
other_pages.insert(*page);
}
}
crate::optimization::ObjectUser::Thumbnail(page) => {
thumbnail_pages.insert(*page);
}
crate::optimization::ObjectUser::Root => has_root = true,
user if is_outline_user(user) => has_outline = true,
user if is_open_document_user(user) => has_open_document = true,
user if is_document_other_user(user) => has_document_other = true,
_ => {} // cov:ignore: ObjectUser is a closed qpdf user enum; every current variant is handled above
}
}
if has_page_zero || has_root || has_outline || has_open_document {
return None;
}
if other_pages.len() > 1 {
return None; // cov:ignore: qpdf routes objects with multiple non-first page users to Part 8 before part4_rest metadata is built
}
if other_pages.len() == 1 && thumbnail_pages.is_empty() && !has_document_other {
return None; // cov:ignore: qpdf routes this single-page object to Part 7 before part4_rest metadata is built
}
if thumbnail_pages.len() == 1 && !has_document_other {
return Some(Part9ThumbnailCategory::Private(
*thumbnail_pages.first().expect("thumbnail page exists"),
));
}
if thumbnail_pages.len() > 1 {
return Some(Part9ThumbnailCategory::Shared);
}
None
}
/// Return the raw source identities that qpdf emits in the Part-9 thumbnail
/// phase. Private thumbnail objects are emitted page-by-page with the `/Thumb`
/// root first and its `ou_thumb` descendants in object-generation order;
/// shared thumbnail objects follow as one object-generation-sorted group
/// (`QPDF_linearization.cc:1293-1327`).
fn part9_thumbnail_objects<R: Read + Seek>(
pdf: &mut Pdf<R>,
optimization: &crate::optimization::Optimization,
page_refs: &[ObjectRef],
part4_rest: &BTreeSet<QpdfObjGen>,
) -> Result<Vec<QpdfObjGen>> {
let mut ordered = Vec::new();
let mut placed = BTreeSet::new();
for (page_index, page_ref) in page_refs.iter().enumerate() {
let page_number = page_index as u32;
let page = pdf.get_object_handle(*page_ref);
let thumb_root = page.try_get_key(b"/Thumb")?.qpdf_obj_gen();
let is_private = |object: QpdfObjGen| {
part4_rest.contains(&object)
&& matches!(
part9_thumbnail_category(optimization.raw_users_for(object)),
Some(Part9ThumbnailCategory::Private(page)) if page == page_number
)
};
if let Some(object) = thumb_root.filter(|object| is_private(*object)) {
if placed.insert(object) {
ordered.push(object);
}
}
for &object in
optimization.raw_objects_for(&crate::optimization::ObjectUser::Thumbnail(page_number))
{
if is_private(object) && placed.insert(object) {
ordered.push(object);
}
}
}
let mut shared: Vec<QpdfObjGen> = part4_rest
.iter()
.copied()
.filter(|object| {
matches!(
part9_thumbnail_category(optimization.raw_users_for(*object)),
Some(Part9ThumbnailCategory::Shared)
)
})
.collect();
shared.sort_unstable();
ordered.extend(shared);
Ok(ordered)
}
fn raw_shared_hints_for_objects(
objects: &[QpdfObjGen],
optimization: &crate::optimization::Optimization,
include_first_page: bool,
) -> Vec<RawSharedObjectHintEntry> {
objects
.iter()
.copied()
.map(|object| RawSharedObjectHintEntry {
object: Some(object),
container: None,
referencing_pages: optimization
.raw_page_users(object)
.filter(|page| include_first_page || *page != 0)
.collect(),
})
.collect()
}
fn raw_part2_objects_for_hints(
part2: &[QpdfObjGen],
part3: &[QpdfObjGen],
outline: &[QpdfObjGen],
part4_shared: &[QpdfObjGen],
optimization: &crate::optimization::Optimization,
) -> Vec<RawSharedObjectHintEntry> {
let mut entries = raw_shared_hints_for_objects(part2, optimization, false);
entries.extend(raw_shared_hints_for_objects(part3, optimization, false));
entries.extend(raw_shared_hints_for_objects(outline, optimization, false));
entries.extend(raw_shared_hints_for_objects(
part4_shared,
optimization,
true,
));
entries
}
impl LinearizationPlan {
/// Return the Preserve member-to-container mapping for a manually
/// constructed plan.
///
/// Production plans use the setup-owned source membership map passed by
/// the writer. This allocation is only the bounded fallback for plans
/// that do not have that setup snapshot, and deliberately preserves the
/// old object-number-only lookup behavior (qpdf's existing ObjStm members
/// are generation zero).
pub(crate) fn preserve_source_membership(&self) -> Option<BTreeMap<u32, u32>> {
let plan = self.preserve_objstm_plan.as_ref()?;
let mut membership = BTreeMap::new();
for group in &plan.groups {
let crate::writer::object_streams::ObjectStreamGroup::SourceBacked { source, members } =
group
else {
continue;
};
for member in members {
membership.insert(member.number, source.number);
}
}
Some(membership)
}
/// Construct a `LinearizationPlan` from a parsed PDF document.
///
/// This method:
///
/// 1. Collects all known object refs into Part 4.
/// 2. Computes the transitive closure of objects reachable from page 1
/// (`/Pages /Kids[0]`).
/// 3. Computes closures for pages 2..N to identify shared objects.
/// 4. Partitions the page-1 closure into Part 2 (exclusive) and Part 3
/// (shared), removing them from Part 4.
/// 5. Fills `page_hints[0]` with the correct `object_count`; all
/// `byte_length` fields remain 0 (back-patched by the writer).
/// 6. Fills `shared_hints` with one entry per Part-3 object, listing
/// every page index that references it.
///
/// # Errors
///
/// Propagates any error from [`crate::pages::page_refs`] when collecting the
/// document's page references (e.g. a malformed or unresolvable `/Pages`
/// tree). Also propagates any error from resolving objects while computing
/// each page's reachability closure (via canonical ObjectHandle resolution /
/// canonical ObjectHandle resolution) — typically an [`crate::Error::Io`] or
/// [`crate::Error::Parse`] on a truncated or malformed object. Before any
/// of that, this also pushes inherited page attributes down the `/Pages`
/// tree, which propagates the same object-resolution errors and returns
/// [`crate::Error::Unsupported`] if the tree exceeds the page-tree depth
/// bound.
pub fn from_pdf<R: Read + Seek>(
pdf: &mut Pdf<R>,
use_generate_objstm: bool,
) -> crate::Result<Self> {
let mode = if use_generate_objstm {
crate::writer::ObjectStreamMode::Generate
} else {
crate::writer::ObjectStreamMode::Disable
};
Self::from_pdf_with_object_stream_mode(pdf, mode)
}
/// Construct a mode-aware linearization plan.
///
/// Unlike the historical boolean API, this distinguishes standard
/// Preserve from source-ObjStm Preserve. qpdf runs its
/// `getCompressibleObjGens` stale-generation removal only for Generate and
/// when Preserve actually consumes source object streams.
pub fn from_pdf_with_object_stream_mode<R: Read + Seek>(
pdf: &mut Pdf<R>,
object_stream_mode: crate::writer::ObjectStreamMode,
) -> crate::Result<Self> {
let options = crate::writer::WriterOptions {
object_streams: object_stream_mode,
..crate::writer::WriterOptions::default()
};
Self::from_pdf_with_writer_options(pdf, &options)
}
pub(crate) fn from_pdf_with_writer_options<R: Read + Seek>(
pdf: &mut Pdf<R>,
options: &crate::writer::WriterOptions,
) -> crate::Result<Self> {
Self::from_pdf_with_writer_options_and_source_membership(pdf, options, None, None, None)
}
#[inline(never)]
pub(crate) fn from_pdf_with_writer_options_and_source_membership<R: Read + Seek>(
pdf: &mut Pdf<R>,
options: &crate::writer::WriterOptions,
source_membership_snapshot: Option<&BTreeMap<u32, u32>>,
generated_compressible_snapshot: Option<&crate::writer::object_streams::CompressiblePlan>,
normalized_streams_snapshot: Option<&BTreeSet<QpdfObjGen>>,
) -> crate::Result<Self> {
let object_stream_mode = options.object_streams;
let use_generate_objstm = matches!(
object_stream_mode,
crate::writer::ObjectStreamMode::Generate
);
// QPDFWriter::initializeSpecialStreams calls getAllPages only when a
// special-stream trigger is active. In the default linearized route,
// object-stream setup runs before the later linearized page scan
// (QPDFWriter.cc:1912-1936,1970-2006,2114-2150).
let special_stream_trigger = options.qdf
|| options.content_normalization
|| options.decode_level != crate::writer::DecodeLevel::None;
let mut prepared_page_sequence = if special_stream_trigger {
crate::pages::repair::prepare_for_optimization(pdf)?
} else {
None
};
let capture_pre_optimization_objects =
!matches!(object_stream_mode, crate::writer::ObjectStreamMode::Disable);
// QPDFWriter::doWriteSetup fixes Generate's eligible object set before
// writeLinearized calls QPDF::optimize. The latter may mint indirect
// inherited-attribute objects, which must remain plain in the output.
// A live PdfWriter passes the exact setup-time snapshot; direct plan
// callers retain the pre-existing fallback for compatibility.
let generate_compressible_plan = if use_generate_objstm {
Some(match generated_compressible_snapshot {
Some(snapshot) => snapshot.clone(),
None => compressible_objgens_qpdf_plan(pdf)?,
})
} else {
None
};
let mut preserve_objstm_plan = if matches!(
object_stream_mode,
crate::writer::ObjectStreamMode::Preserve
) {
Some(
crate::writer::object_streams::plan_qpdf_preserve_object_streams_with_source_membership(
pdf,
options.preserve_unreferenced_objects,
source_membership_snapshot,
)?, // cov:ignore: LLVM attributes this multiline setup-plan terminator to an uncovered continuation line
)
} else {
None
};
let source_had_compressed_objects = preserve_objstm_plan
.as_ref()
.is_some_and(|plan| plan.source_membership_present);
if let Some(plan) = preserve_objstm_plan.as_mut() {
crate::writer::object_streams::filter_preserve_object_stream_plan_for_output(
pdf, plan, true, false,
)?; // cov:ignore: LLVM attributes this multiline Preserve filter terminator to an uncovered continuation line
}
let preserve_object_stream_data: BTreeMap<u32, u32> = preserve_objstm_plan
.as_ref()
.map(|plan| {
plan.groups
.iter()
.filter_map(|group| match group {
crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
source,
members,
} => Some((source, members)),
// cov:ignore-start: this plan is built only by the Preserve planner
crate::writer::object_streams::ObjectStreamGroup::Generated { .. } => None,
// cov:ignore-end
})
.flat_map(|(source, members)| {
members
.iter()
.map(move |member| (member.number, source.number))
})
.collect()
})
.unwrap_or_default();
if !special_stream_trigger {
prepared_page_sequence = crate::pages::repair::prepare_for_optimization(pdf)?;
}
let pre_optimization_object_refs = capture_pre_optimization_objects
.then(|| pdf.canonical_live_object_refs().into_iter().collect());
let preserve_source_container_by_member: BTreeMap<ObjectRef, ObjectRef> =
preserve_object_stream_data
.iter()
.map(|(&member, &source)| (ObjectRef::new(member, 0), ObjectRef::new(source, 0)))
.collect();
let generate_objstm_eligible = generate_compressible_plan
.as_ref()
.map(|plan| plan.eligible.clone());
// qpdf optimization performs direct-outline normalization, page-tree
// preparation, inherited-attribute push, and object-user traversal in
// this order. It must run before object-ref capture because those
// preparations may mint indirect objects.
//
// qpdf's writeLinearized goes straight from doWriteSetup into
// QPDF::optimize with no separate object-cache warmup pass
// (QPDFWriter.cc:2536-2554) - the sole object cache participates in
// every consumer that touches it, so there is nothing to warm.
// Optimization::optimize's own traversal already resolves every
// reachable object (including stream framing/length recovery for a
// malformed stream) through the canonical ObjectHandle route in one
// pass; a prior CanonicalCatalogFirstRenumber pre-pass here was
// redundant with that traversal rather than compensating for a real
// gap in it.
// QPDFWriter::initializeSpecialStreams calls getAllPages before
// QPDF::optimize (QPDFWriter.cc:1911-1935,2114-2116). Seed the
// canonical page cache through the same repair boundary, then let the
// content-normalization probe consume that stable sequence. Empty
// page lists intentionally remain uncached, matching qpdf's
// `m->all_pages.empty()` sentinel in QPDF_pages.cc:42-44.
let prepared_page_handles = if options.content_normalization {
prepared_page_sequence
.as_ref()
.map_or(&[][..], |prepared| prepared.pages.as_slice())
} else {
&[][..]
};
let content_normalize_refs = linearization_content_normalize_refs(
options,
prepared_page_handles,
normalized_streams_snapshot,
)?; // cov:ignore: LLVM attributes this executed multiline call terminator to the preceding line.
let mut skipped_raw_stream_parameter_streams: BTreeSet<QpdfObjGen> = BTreeSet::new();
let mut optimization = crate::optimization::Optimization::optimize(
pdf,
&preserve_object_stream_data,
true,
|stream_ref, stream| {
// qpdf invokes this callback only while traversing objects
// reachable from a page, trailer key, or root key. Keep the
// stream-parameter probe inside that callback so an orphaned
// stream cannot make linearization read its source data.
if stream_ref.is_some_and(|object_gen| {
skipped_raw_stream_parameter_streams.contains(&object_gen)
}) {
// A stream can be visited by more than one object user.
// Preserve the old prepass's one-probe state boundary:
// once the first reachable visit established that qpdf
// removes the parameter edges, later visits must not
// consume a stateful token filter again.
return Ok(2);
}
let has_indirect_parameter = stream_has_indirect_parameter_edge(stream)?;
// The parameter-edge helper is itself the qpdf-shaped
// `willFilterStream` probe. Reuse its result when the stream
// has an indirect parameter edge; a second probe here would
// consume a stateful provider/filter a second time within the
// same optimization callback.
let refiltered = if has_indirect_parameter {
stream_parameters_removed_for_linearization(
stream,
stream_ref,
options,
&content_normalize_refs,
)? // cov:ignore: LLVM attributes this covered reachable-stream branch continuation to the call opening line
} else {
crate::writer::plain::body::canonical_stream_filter_probe_for_linearization(
stream,
options,
stream_ref
.is_some_and(|object_gen| content_normalize_refs.contains(&object_gen)),
)? // cov:ignore: LLVM attributes this covered reachable-stream branch continuation to the call opening line
};
if refiltered {
if has_indirect_parameter {
if let Some(object_gen) = stream_ref {
skipped_raw_stream_parameter_streams.insert(object_gen);
}
}
// The probe above already consumed qpdf's stateful filter
// check; the optimization callback must not run it again.
Ok(2)
} else {
Ok(1)
}
},
)?;
if let Some(eligible) = generate_objstm_eligible {
optimization.set_generate_objstm_eligible(eligible);
}
if let Some(refs) = pre_optimization_object_refs {
optimization.set_pre_optimization_object_refs(refs);
}
if !has_page_user_objects(&optimization) {
// qpdf raises this through `stopOnError`, which builds a
// `qpdf_e_damaged_pdf` exception carrying the input name and the
// source's last read offset and no object description
// (`QPDF_linearization.cc:1190`, `QPDF.cc:2590-2592,2625-2628`).
return Err(qpdf_stop_on_error(
pdf,
b"no pages found while calculating linearization data",
));
}
// ----------------------------------------------------------------
// Step 1: collect all known object refs (Part 4 initial state).
// The free-list head at object 0 is excluded per ISO 32000-1 §7.5.4.
// ----------------------------------------------------------------
// Drop the source's structural containers (`/Type /ObjStm`, `/Type
// /XRef`) from the live object set. qpdf rebuilds the cross-reference
// and repacks ObjStm members into fresh containers, so the source
// containers are never live body objects (their members survive as
// individual objects via the compressed xref entries). Carrying them
// through would shift every offset and make qpdf's linearization
// length-calc reject them ("found unknown object"). This keeps the
// linearization universe aligned with the writer's structural-container
// emission rule.
// qpdf garbage-collects objects unreachable from the trailer roots (it
// only enqueues reachable objects). The plain full-rewrite path does this
// via the canonical handle renumber walk's trailer-seeded BFS; the linearize universe
// must too, or re-linearizing an already-linearized source leaks its old
// /Linearized parameter dict + hint stream — both unreachable structural
// artifacts — into the second half.
//
// `skip_length = true`: the linearized writer always emits a direct
// `/Length` — re-encoded and lone-`/FlateDecode`-verbatim streams alike,
// and `renumber_object` substitutes a direct length for a dropped holder's
// dangling reference — so a stream's indirect `/Length` edge is dead in the
// output regardless of object-stream mode. Not following it drops a holder
// reachable only through it, matching qpdf's reachability GC.
// Collect page references before choosing the fast universe route. A
// malformed or detached page /Parent is deliberately ignored by
// qpdf's object-user map but remains reachable for the writer's
// Part-9 universe, so that shape must retain the exact fallback walk.
let page_refs: Vec<ObjectRef> = crate::pages::page_refs(pdf)?;
if let Some(first_page_ref) = page_refs.first().copied() {
if !first_page_is_private(
&optimization,
first_page_ref,
&preserve_source_container_by_member,
) {
return Err(qpdf_stop_on_error(
pdf,
b"INTERNAL ERROR: QPDF::calculateLinearizationData: first page object not in lc_first_page_private",
));
}
} // cov:ignore: LLVM maps the successful first-page-private continuation to this cleanup brace
let page_parent_users_are_complete =
page_refs
.iter()
.try_fold(true, |complete, page_ref| -> Result<bool> {
if !complete {
return Ok(false);
}
let page = pdf.get_object_handle(*page_ref);
let parent = page.try_get_key(b"/Parent")?;
if parent.try_is_null()? {
return Ok(true);
}
let Some(parent_gen) = parent.qpdf_obj_gen() else {
return Ok(false);
};
Ok(optimization
.raw_users_for(parent_gen)
.iter()
.next()
.is_some())
})?;
// qpdf's Optimization object-user map is already the reachability
// traversal consumed by calculateLinearizationData. Reuse it when
// no source ObjStm member projection has replaced raw members with
// container identities and all page-parent edges are represented.
// Preserve mode with source containers keeps the explicit fallback
// walk because the filtered map no longer has the original member
// identities required by the writer universe.
let use_optimization_page_user_map =
preserve_object_stream_data.is_empty() && page_parent_users_are_complete;
let reachable: BTreeSet<ObjectRef> = if use_optimization_page_user_map {
optimization.linearization_reachable_object_refs().collect()
} else {
crate::writer::rewrite_renumber::reachable_object_set_with_stream_parameters(
pdf,
true,
&skipped_raw_stream_parameter_streams,
)? // cov:ignore: LLVM maps the covered fallback call's Result terminator to a zero-count continuation line
};
let object_refs = pdf.canonical_object_refs();
let mut all_refs: Vec<ObjectRef> = Vec::with_capacity(object_refs.len());
for r in object_refs {
if r.number == 0 {
continue;
}
if !reachable.contains(&r) {
// Unreachable from the trailer roots — qpdf drops it before
// any linearization part is formed. Check this before
// resolving so a discarded object cannot make planning read
// its source bytes.
continue;
}
let object_handle = pdf.get_object_handle(r);
// Both `/Type /XRef` and `/Type /ObjStm` objects are required to
// carry stream data (ISO 32000-1 §7.5.7/§7.5.8), so the genuine
// article is always `ObjectValue::Stream`, never a plain
// dictionary. `try_is_dictionary_of_type` only matches
// `ObjectValue::Dictionary` (mirroring qpdf's own
// `isDictionaryOfType`, `libqpdf/QPDFObjectHandle.cc:461-466`),
// so it can never match here; `try_is_stream_of_type` mirrors
// qpdf's dedicated `isStreamOfType` (`:468-471`) instead.
if object_handle.try_is_stream_of_type(b"XRef", b"")?
|| object_handle.try_is_stream_of_type(b"ObjStm", b"")?
{
continue;
}
all_refs.push(canonical_preserve_ref(
&preserve_source_container_by_member,
r,
));
}
if object_stream_mode == crate::writer::ObjectStreamMode::Preserve {
all_refs.sort_unstable();
all_refs.dedup();
}
// Resurrect null-resolving references reached via a surviving (array)
// edge that have NO xref entry (truly missing). Free entries are already
// admitted above — they are in the canonical cache and pass the
// `reachable` filter — so add only the missing ones. qpdf treats
// a missing array ref exactly like a free one: a renumbered `null` body
// object the array points at (verified byte-identical, /ID masked). The
// set is drop-aware (a null ref reached only as a dict value is omitted),
// so a dict-only missing ref stays dropped, not resurrected.
// `all_refs` is sorted (it filters the sorted canonical cache keys in order),
// so a binary search rejects the already-admitted (free) refs without
// allocating a temporary set.
//
// `resurrectable` is kept alive to pass to `compute_closure`, which
// includes these refs in the page closure they're first reached from.
// qpdf classifies them as first-page section objects (Part 2) when reached
// from the first page, giving them HIGH object numbers. Without this, they
// land in part4_rest with LOW numbers.
let operation_removes_stale_generations = use_generate_objstm
|| (matches!(
object_stream_mode,
crate::writer::ObjectStreamMode::Preserve
) && source_had_compressed_objects);
let removed_refs = if operation_removes_stale_generations {
if let Some(plan) = generate_compressible_plan.as_ref() {
plan.removed_refs.clone()
} else if let Some(plan) = preserve_objstm_plan.as_ref() {
plan.removed_refs.clone()
} else {
crate::writer::object_streams::compressible_objgens_qpdf_plan(pdf)?.removed_refs
}
} else {
BTreeSet::new()
};
if let Some(plan) = generate_compressible_plan.as_ref() {
// qpdf may directize an indirect Catalog value in
// `prepareFileForWrite` after Generate membership has already
// been assigned. Keep those setup-time members in the linearized
// object universe even when the post-prepare reachability walk no
// longer sees their old edge (QPDFWriter.cc:2034-2055).
all_refs.extend(plan.eligible.iter().copied());
all_refs.sort_unstable();
all_refs.dedup();
}
all_refs.retain(|reference| !removed_refs.contains(reference));
let resurrectable =
crate::writer::rewrite_renumber::resurrectable_null_refs_excluding(pdf, &removed_refs)?;
let mut resurrected: Vec<ObjectRef> = resurrectable
.iter()
.filter(|r| all_refs.binary_search(r).is_err())
.copied()
.collect();
if !resurrected.is_empty() {
all_refs.append(&mut resurrected);
// Keep source-object-number order (canonical cache keys are already sorted);
// the resurrected refs slot in at their numeric position.
all_refs.sort();
}
let total_object_count = all_refs.len() as u32;
let root_ref = pdf.root_ref();
let info_handle = pdf.trailer().try_get_key(b"/Info")?;
let info_ref = info_handle
.object_ref()
.or_else(|| info_handle.object_ref());
let pages_handle = pdf.root_handle()?.try_get_key(b"/Pages")?;
let pages_tree_ref = pages_handle
.object_ref()
.or_else(|| pages_handle.object_ref())
.map(|object_ref| {
canonical_preserve_ref(&preserve_source_container_by_member, object_ref)
});
// The live object set is invariant across every page's closure; compute it
// once so the per-page `compute_closure` calls below do not each re-scan
// the whole xref table (which would be O(pages × objects)).
let live: BTreeSet<ObjectRef> = pdf.canonical_live_object_refs().into_iter().collect();
let first_page_users = optimization
.objects_for(&crate::optimization::ObjectUser::Page(0))
.collect::<BTreeSet<_>>();
let root_objects = optimization
.objects_for(&crate::optimization::ObjectUser::Root)
.collect::<BTreeSet<_>>();
let mut open_document_objects: BTreeSet<ObjectRef> =
optimization.objects_for_trailer_key(b"Encrypt").collect();
for key in OPEN_DOCUMENT_CATALOG_KEYS {
open_document_objects.extend(optimization.objects_for_root_key(key));
}
let all_outline_refs: BTreeSet<ObjectRef> =
optimization.objects_for_root_key(b"Outlines").collect();
let document_other_objects: BTreeSet<ObjectRef> = optimization
.object_users()
.filter_map(|(object_ref, users)| {
users
.iter()
.any(is_document_other_user)
.then_some(object_ref)
})
.collect();
let elig_ctx = if use_generate_objstm {
Some(eligibility_context(pdf)?)
} else {
None
};
// ----------------------------------------------------------------
// Step 3: compute first-page closure
// ----------------------------------------------------------------
let mut first_page_closure: Vec<ObjectRef> = if let Some(&first_page) = page_refs.first() {
compute_closure_with_stream_parameters(
pdf,
first_page,
&live,
&resurrectable,
&skipped_raw_stream_parameter_streams,
)? // cov:ignore: LLVM maps this covered first-page closure call terminator to a zero-count continuation region
} else {
Vec::new()
};
first_page_closure =
canonicalize_preserve_refs(&preserve_source_container_by_member, first_page_closure);
first_page_closure.retain(|object_ref| first_page_users.contains(object_ref));
// compute_closure does not follow a stream dict's /Length (qpdf directizes
// /Length before computing object users), so a stream's indirect /Length
// holder never enters a page closure: an orphan holder (referenced only via
// /Length) is GC'd by the all_refs filter above, and a kept holder is
// reached only via its other (e.g. catalog) edge and partitions from there
// (for the indirect-length and shared-stream cases).
let first_page_set: BTreeSet<ObjectRef> = first_page_closure.iter().copied().collect();
// ----------------------------------------------------------------
// Step 4: compute closures for pages 2..N and find shared objects
// ----------------------------------------------------------------
// Build a full inverse map: (object_ref → set of page indices) across
// ALL pages (0..N). This is used to determine which objects are shared
// between multiple pages regardless of whether they appear in the
// first-page closure.
//
// `shared_page_indices` retains the old semantics for Part 3 partitioning
// (only first-page-set objects that also appear in other pages).
// The retained qpdf-shaped object-user map remains the sole source of
// page-user relationships. Closures here remain the authoritative
// ordered inputs for page partitioning and hint construction.
let mut shared_page_indices: BTreeMap<ObjectRef, BTreeSet<u32>> = BTreeMap::new();
let mut other_page_closures: Vec<Vec<ObjectRef>> =
Vec::with_capacity(page_refs.len().saturating_sub(1));
for (page_idx, &page_ref) in page_refs.iter().enumerate().skip(1) {
// qpdf's `obj_user_to_objects[ou_page(i)]` is already the exact
// later-page object set, and its std::set iteration order is the
// order consumed by calculateLinearizationData (QPDF_linearization.cc:
// 1224-1258). Reuse that canonical map instead of walking every
// page graph a second time. Keep the explicit walk for source
// ObjStm projections and malformed page shapes whose raw map is not
// the writer's object universe.
let closure: Vec<ObjectRef> = if use_optimization_page_user_map {
// qpdf places the page object itself before iterating the map
// (`QPDF_linearization.cc:1231-1238` pushes `pages.at(i)` and
// erases it from `lc_other_page_private`, so the loop at
// `:1249-1255` can no longer emit it). The map alone is sorted
// by object id, which would emit the page dictionary in the
// middle of its own descendants.
let mut closure = Vec::new();
closure.push(page_ref);
closure.extend(
optimization
.objects_for(&crate::optimization::ObjectUser::Page(page_idx as u32))
.filter(|object_ref| *object_ref != page_ref),
);
closure
} else {
let mut closure = compute_closure_with_stream_parameters(
pdf,
page_ref,
&live,
&resurrectable,
&skipped_raw_stream_parameter_streams,
)?; // cov:ignore: LLVM maps this covered later-page closure call terminator to a zero-count continuation region
closure = canonicalize_preserve_refs(&preserve_source_container_by_member, closure);
// Query the inverse user map per object. Re-deriving
// `objects_for(Page(i))` inside `retain` rebuilds the iterator and
// scans it from the start for every closure entry, which is
// quadratic in the closure size for object-heavy pages.
let page_user = crate::optimization::ObjectUser::Page(page_idx as u32);
closure.retain(|object_ref| {
optimization
.users_for(*object_ref)
.iter()
.any(|user| *user == page_user)
});
closure
};
for obj_ref in &closure {
// Track cross-page sharing for first-page objects (used by Part 3 partition).
if first_page_set.contains(obj_ref) {
shared_page_indices
.entry(*obj_ref)
.or_default()
.insert(page_idx as u32);
}
}
other_page_closures.push(closure);
}
// ----------------------------------------------------------------
// Step 4b: thumb-set for the first-page private/shared split.
// ----------------------------------------------------------------
// qpdf gives a page's /Thumb descendants the separate `ou_thumb` user
// while sharing the page traversal's one ordered `visited` set
// (QPDF_optimization.cc:261-337). The same exact map supplies ordinary
// page membership above and thumbnail membership here.
let thumbnail_user_set: BTreeSet<ObjectRef> = optimization.thumbnail_objects().collect();
// ----------------------------------------------------------------
// Step 5: partition into Part 2 (exclusive) and Part 3 (shared)
// ----------------------------------------------------------------
// Maintain closure discovery order from first_page_closure for Part 2
// (page dict first, then its `/Resources` subtree, then `/Contents`,
// matching qpdf's first-page object numbering).
//
// The page-1 dictionary is pinned to Part 2 after the qpdf
// lc_first_page_private invariant above has accepted it. This is the
// anchor reached via /O in the parameter dictionary.
let first_page_ref = page_refs.first().copied();
let mut part2_objects: Vec<ObjectRef> = Vec::new();
let mut part3_objects: Vec<ObjectRef> = Vec::new();
for obj_ref in &first_page_closure {
// qpdf: in_open_document takes precedence over in_first_page in EVERY
// object-stream mode. Objects reachable from catalog open-document keys
// (/AcroForm, /OpenAction, etc.) are placed in the open-document section
// (part4, first half, before /O) even when they also appear in the
// first-page closure, so peel them out of Part 2/3 here:
// - generate: eligible ones pack into the open-document ObjStm
// container (route_objstm_containers -> ContainerPart::OpenDocument);
// ineligible streams emit plain pre-/O (part4_open_document_plain).
// - disable/preserve: all are emitted plain pre-/O.
// Verified against qpdf 11.9.0: acroform-widget-page0-5-10 in disable
// mode places the AcroForm dict + widgets in part4, NOT the first-page
// section (the 12 first-page objects there are the page dict + content
// + 10 Fonts, not the widgets).
//
// in_outlines outranks in_first_page the same way (and outranks
// in_open_document, so check it first): an object reached from both the
// first page and /Outlines is lc_outlines (second-half part9, or part6
// under /UseOutlines), never part2/part3. Peel it here so the part4
// outline extraction in Step 8 can place it. Verified against qpdf
// 11.9.0: outlines-shared-page-80-80's /Extra-referenced font is the
// last second-half object, not a first-page-shared object.
if root_objects.contains(obj_ref)
|| all_outline_refs.contains(obj_ref)
|| open_document_objects.contains(obj_ref)
{
continue;
}
if Some(*obj_ref) == first_page_ref {
part2_objects.push(*obj_ref);
} else if shared_page_indices.contains_key(obj_ref)
|| document_other_objects.contains(obj_ref)
|| thumbnail_user_set.contains(obj_ref)
{
// lc_first_page_shared: in_first_page AND (other_pages>0 ||
// others>0 || thumbs>0). `shared_page_indices` supplies
// other_pages (another page's closure); `document_other_objects`
// supplies others (a document-level reference such as a Catalog
// key); `thumbnail_user_set` supplies thumbs (a page's /Thumb
// target). Any of these makes the object shared
// (QPDF_linearization.cc:1124-1127), so it sorts after the
// first-page-private objects in part 6.
part3_objects.push(*obj_ref);
} else {
part2_objects.push(*obj_ref);
}
}
// qpdf packs first-half shared objects in the source/discovery order
// assigned by the input document. A page-selection merge records that
// order separately because its fresh target references no longer carry
// the primary source's object numbers; ordinary parsed documents fall
// back to their live references. This is also the order used by qpdf's
// `std::set<QPDFObjGen>` part-6 packing after the primary/foreign
// provenance has been accounted for.
part3_objects.sort_unstable_by_key(|r| pdf.writer_object_order_key(*r));
// qpdf numbers the first-page section (qpdf part6) as: the first-page
// object first, then the remaining first-page-private objects in
// source/discovery order. Pin the page dict first (qpdf pushes the
// first-page object explicitly), then apply that order key rather than
// the fresh merge target's allocation number.
part2_objects.sort_unstable_by_key(|r| {
(Some(*r) != first_page_ref, pdf.writer_object_order_key(*r))
});
// ----------------------------------------------------------------
// Step 6: build Part 4 by removing Part 2 and Part 3 objects.
//
// Provisional list — the final order (per-page private groups
// contiguous, then leftover globally-shared) is computed below in
// Step 7 once we know which objects belong to which page.
let moved: BTreeSet<ObjectRef> = part2_objects
.iter()
.chain(&part3_objects)
.copied()
.collect();
let part4_provisional: Vec<ObjectRef> = all_refs
.into_iter()
.filter(|r| !moved.contains(r))
.collect();
// ----------------------------------------------------------------
// Step 7: build page_hints and per_page_private_objects
// ----------------------------------------------------------------
let mut page_hints: Vec<PageHintEntry> = page_refs
.iter()
.map(|&r| PageHintEntry::placeholder(r))
.collect();
// For quick membership checks across all pages.
let part2_set: BTreeSet<ObjectRef> = part2_objects.iter().copied().collect();
let part3_set: BTreeSet<ObjectRef> = part3_objects.iter().copied().collect();
// Page 0: private objects = Part 2 objects.
let page0_private = part2_objects.clone();
// Fill page-0 hint: first_object_index = 0; object_count = Part 2 +
// Part 3 (shared) objects, since the first-page section physically
// contains both before /E. qpdf's hint-table checker validates
// object_count[0] against the count of objects in [first_page_offset,
// /E), which equals |Part 2| + |Part 3|.
if !page_hints.is_empty() {
page_hints[0].first_object_index = 0;
page_hints[0].object_count = (page0_private.len() + part3_objects.len()) as u32;
}
// Per-page private object lists, page 0 first.
let mut per_page_private_objects: Vec<Vec<ObjectRef>> = Vec::with_capacity(page_refs.len());
per_page_private_objects.push(page0_private);
// Pages 1..N: private objects = closure(i) ∩ (reachable from exactly
// 1 page). Excluding only part2_set / part3_set is too narrow:
// globally-shared objects like the Catalog or /Pages tree intermediate
// nodes are reachable from EVERY page, including page 0 (via the
// /Parent chain), so they sit in our part4_objects rather than
// part3_objects. qpdf's per-page object_count and page_length only
// count objects exclusive to one page (it walks the file body forward
// from the page object and stops at the first non-exclusive object),
// so we mirror that by checking page-reach-count == 1.
for (i, closure) in other_page_closures.into_iter().enumerate() {
let page_idx = i + 1; // skip(1) above started page indexing at 1
let private: Vec<ObjectRef> = closure
.into_iter()
.filter(|r| {
if part2_set.contains(r) || part3_set.contains(r) {
return false;
}
// Open-document objects (AcroForm widgets, etc.) that happen
// to be exclusive to one later page must NOT be counted as
// page-private: qpdf routes them to the pre-/O open-document
// section (not the per-page section) in every mode, so they are
// absent from the second-half page objects and should not
// inflate page_hints[page_idx].object_count. Excluding them
// here also keeps them out of per_page_private_objects, so the
// part7 pre-pass below never captures them and they remain
// available for OD routing in the part8/part9 loop.
if open_document_objects.contains(r) {
return false;
}
// Outline objects (in_outlines) outrank other-page-private the
// same way: keep them out of the per-page-private set so the
// part7 pre-pass never claims them and they stay available for
// outline routing in the part8/part9 loop.
if all_outline_refs.contains(r) {
return false;
}
// qpdf routes a non-first-page object to lc_other_page_private
// (part7) ONLY when others==0 (QPDF_linearization.cc:1128). An
// object also reached by a document-level `others` reference
// (a Catalog non-open-document key, or a trailer key other than
// /Root,/Encrypt) is lc_other (part9) even at other_pages==1.
// Keep it out of the per-page-private set so it is neither placed
// in part7 nor counted in this page's part7 object_count hint; it
// flows through part4_provisional into the part8/part9 loop and
// lands in part4_rest (part9).
if document_other_objects.contains(r) {
return false;
}
// qpdf's lc_other_page_private predicate also requires
// thumbs==0. A normal page object that is another page's
// thumbnail belongs to part9, not part7.
if thumbnail_user_set.contains(r) {
return false;
}
optimization.page_users(*r).count() == 1
})
.collect();
// qpdf categorizes the page object itself into lc_other_page_private
// during the object-user classification pass, then asserts that
// placement immediately before pushing it into part7
// (QPDF_linearization.cc:1226-1231). A page reached by any user
// besides its own Page(page_idx) entry -- a shared /Kids slot, a
// non-/Root trailer key, an outline, an open-document key, or a
// thumbnail -- fails this invariant and qpdf refuses to linearize.
if !private.contains(&page_refs[page_idx]) {
return Err(qpdf_stop_on_error(
pdf,
format!(
"INTERNAL ERROR: QPDF::calculateLinearizationData: page object for page {page_idx} not in lc_other_page_private"
),
));
}
if page_idx < page_hints.len() {
// Use private count; guarantee at least 1 so hint table isn't all zeros.
let count = private.len().max(1) as u32;
page_hints[page_idx].object_count = count;
}
per_page_private_objects.push(private);
}
// qpdf places the Pages tree into part9 by looking up
// `m->obj_user_to_objects[ObjUser(ou_root_key, "/Pages")]` and stops
// if that set is empty (QPDF_linearization.cc:1279-1283) -- a direct
// (non-indirect) /Pages value, or a missing /Pages key, leaves no
// object-user entry to place. This must be checked here, not
// defaulted to a fallback in a later derived view: qpdf treats an
// empty pages-tree user set as a fatal internal-consistency error,
// not a value to substitute.
if optimization.objects_for_root_key(b"Pages").next().is_none() {
return Err(qpdf_stop_on_error(
pdf,
b"found empty pages tree while calculating linearization data",
));
}
// ----------------------------------------------------------------
// Step 6b: partition Part 4 into qpdf part7 / part8 / part9.
//
// qpdf numbers objects in the second half (Part 4) as:
// part7 (other pages' private): objects reached by exactly ONE
// other page (pages 2..N), iterated page by page in closure order.
// part8 (other pages' shared): objects reached by TWO OR MORE
// other pages (but NOT page 1), in plan order.
// part9 (rest): everything else — Pages tree, Info, lc_other, and
// objects not reached from any page closure (trailer-only refs).
//
// The renumber pass uses these three sub-partitions directly.
// `part4_objects` is then built as part7 ++ part8 ++ part9 so the
// writer (which iterates `part4_objects`) emits bytes in the same
// order as the renumber map.
// qpdf's canonical object-user map counts page reach directly. For an
// object NOT in first_page_set:
// - one page user → exactly one other page → part7
// - two or more page users → part8
// - no page users → part9
let provisional_set: BTreeSet<ObjectRef> = part4_provisional.iter().copied().collect();
// `all_outline_refs` (qpdf's `in_outlines` set) was computed in Step 1c and
// already peeled out of part2/part3 (Step 5) and the per-page-private sets
// (Step 7); the loop below routes its members to part4_rest with top
// precedence so the Step 8 outline extraction places them.
let mut part4_other_pages_private: Vec<ObjectRef> = Vec::new();
let mut part4_other_pages_shared: Vec<ObjectRef> = Vec::new();
let mut part4_rest: Vec<ObjectRef> = Vec::new();
let mut part4_open_document_plain: Vec<ObjectRef> = Vec::new();
// Track which objects are already in part7 (private) to build in page order.
let mut placed_private: BTreeSet<ObjectRef> = BTreeSet::new();
// part7: iterate pages 2..N in order, closure order within each page.
// Use per_page_private_objects[1..] — these are already private (reach==1).
for privates in per_page_private_objects.iter().skip(1) {
for &r in privates {
if provisional_set.contains(&r) && placed_private.insert(r) {
part4_other_pages_private.push(r);
}
}
}
// part8 and part9: iterate provisional in original order.
for &r in &part4_provisional {
if placed_private.contains(&r) {
// Already in part7.
continue;
}
// in_outlines has top precedence (QPDF_linearization.cc:1120, above
// in_open_document and in_first_page). Route every outline object to
// part4_rest so the Step 8 extraction lifts it into the outline section
// (part6 under /UseOutlines, else part9). They were peeled from
// part2/part3 (Step 5) and the per-page-private sets (Step 7), so they
// reach this loop via part4_provisional even when first-page-reachable.
if all_outline_refs.contains(&r) {
part4_rest.push(r);
continue;
}
let reach = optimization.page_users(r).count() as u32;
// OD+first-page objects were peeled out of Part 2/3 by Step 5 in
// every mode, so they ARE present in part4_provisional and must not be
// treated as first-page here — they flow to the OD routing below. A
// genuine first-page object reaching this point is skipped defensively.
let in_first_page = first_page_set.contains(&r)
&& !root_objects.contains(&r)
&& !open_document_objects.contains(&r);
if in_first_page {
// Should have been in Part 2 or Part 3 — skip (defensive).
continue;
}
// Route the qpdf root and open-document objects to part4 (first
// half, before /O) in EVERY mode — qpdf's part4 is
// [lc_root] ++ lc_open_document. Outline objects (which qpdf
// orders above in_open_document) were already routed above.
if root_objects.contains(&r) || open_document_objects.contains(&r) {
if let Some(ctx) = elig_ctx.as_ref() {
// generate mode: an OD object eligible for ObjStm packing goes
// to part4_rest (the batch planner packs it into the
// open-document container); an ineligible stream (e.g. an /AP /N
// appearance stream, which cannot be an ObjStm member) emits
// plain pre-/O. Oracle: qpdf --object-streams=generate places
// such a Form XObject at a lower object number than the OD
// ObjStm, physically before the hint stream.
let obj = pdf.get_object_handle(r);
if is_eligible_for_objstm_handle(r, &obj, ctx)? {
part4_rest.push(r);
} else {
part4_open_document_plain.push(r);
}
} else {
// disable/preserve mode: no ObjStm, so every OD object is a
// plain pre-/O (part4) object emitted between the Catalog and
// the hint stream.
part4_open_document_plain.push(r);
}
continue;
}
// What remains: non-outline, non-open-document objects. Partition by
// page reach (qpdf's other_pages count): two or more other pages →
// lc_other_page_shared (part8); otherwise lc_other (part9).
if reach >= 2 {
part4_other_pages_shared.push(r);
} else {
// reach == 0 (trailer-/document-only), or reach == 1 with others>0
// (excluded from per_page_private above, so it is lc_other not
// lc_other_page_private — QPDF_linearization.cc:1128).
// Both are qpdf part9.
part4_rest.push(r);
}
}
debug_assert_eq!(
part4_other_pages_private.len()
+ part4_other_pages_shared.len()
+ part4_rest.len()
+ part4_open_document_plain.len(),
part4_provisional.len(),
"Part-4 sub-partition must preserve membership"
);
// qpdf builds part4 as [lc_root] ++ lc_open_document, where
// lc_open_document is a std::set<QPDFObjGen> — i.e. ascending
// (object number, generation) in the post-selection destination
// document (QPDF_linearization.cc:1179-1182). The Catalog (lc_root)
// is placed separately by the renumber map's root_ref promote. A
// page-selection merge gives copied objects fresh target references,
// so target-number sorting would not reproduce qpdf's destination
// allocation order; use the writer provenance key that projects that
// qpdf order, just as for the Part-2/Part-3 ordering above. For an
// ordinary parsed document this key is the live ObjectRef, preserving
// the direct qpdf ObjGen order.
part4_open_document_plain.sort_unstable_by_key(|r| pdf.writer_object_order_key(*r));
// ----------------------------------------------------------------
// Step 8: build shared_hints
// ----------------------------------------------------------------
// The Shared Object Hint Table covers ALL objects in the first-page
// section (Part 2 + Part 3) plus any Part-4 shared objects.
//
// qpdf always lists all objects in the first-page section in the SO
// hint table, even for single-page PDFs where no objects are truly
// shared across pages. We match this behaviour unconditionally:
// shared_hints is always non-empty whenever part2_objects is non-empty.
//
// Layout of shared_hints (in file order):
// [part2 entries] - first-page section private objects (page 0 owns
// them by physical position; referencing_pages = [])
// [part3 entries] - first-page section shared objects (also owned by
// page 0 physically; referencing_pages lists pages
// 1..N that also use them, NOT page 0)
// [outline entries] - outline objects routed to the first-page section
// when /PageMode /UseOutlines is set; physically
// owned by page 0 via layout (referencing_pages = [])
// [part4_shared] - Part-4 shared objects (after /E; owned by no
// page via physical position; referencing_pages lists
// ALL pages that reference them)
// Outline objects routed to the first-page section when
// /PageMode /UseOutlines is set (QPDF_linearization.cc:1031-1043).
// Must be built before shared_hints so they can be included in it.
//
// For the classic (non-ObjStm) linearize path, outlines in part4_rest
// need to be extracted into dedicated fields so the renumber map can
// assign them the correct half:
// part6_outline_objects — UseOutlines: first-half numbers, emitted before /E
// part9_outline_objects — !UseOutlines: second-half numbers, emitted after /E
let outlines_in_first_page = outlines_in_first_page_predicate(pdf)?;
// `all_outline_refs` is computed once above (step 6b), before the
// open-document routing that defers to it.
// Outline root reference: placed first in the extracted vectors so the
// renumber map assigns it the lowest new unit among outline objects,
// matching qpdf's lc_outlines traversal-from-root order (used by
// compute_outline_hint_info's first_object).
let outlines = pdf.root_handle()?.try_get_key(b"/Outlines")?;
let outline_root_ref: Option<ObjectRef> = outlines.object_ref().map(|object_ref| {
canonical_preserve_ref(&preserve_source_container_by_member, object_ref)
});
let extract_outlines = |src: &[ObjectRef]| -> Vec<ObjectRef> {
let mut v: Vec<ObjectRef> = src
.iter()
.filter(|r| all_outline_refs.contains(r))
.copied()
.collect();
// Rotate root to front so it receives the lowest consecutive new number.
if let Some(root) = outline_root_ref {
if let Some(pos) = v.iter().position(|&r| r == root) {
v[..=pos].rotate_right(1);
}
}
v
};
let (part6_outline_objects, part9_outline_objects): (Vec<ObjectRef>, Vec<ObjectRef>) =
if outlines_in_first_page {
(extract_outlines(&part4_rest), vec![])
} else {
(vec![], extract_outlines(&part4_rest))
};
// Remove extracted outlines from part4_rest to avoid double assignment.
let outline_extract_set: BTreeSet<ObjectRef> = part6_outline_objects
.iter()
.chain(&part9_outline_objects)
.copied()
.collect();
part4_rest.retain(|r| !outline_extract_set.contains(r));
// For UseOutlines: outlines are emitted before /E and count toward page 0.
if outlines_in_first_page && !page_hints.is_empty() {
page_hints[0].object_count += part6_outline_objects.len() as u32;
}
// Use part6_outline_objects (already root-first, only objects actually
// extracted from part4_rest) so that shared_hints iteration order matches
// the physical emitted order and objects also reachable from a page closure
// are not double-counted in shared_hints.
let outline_first_page_members: Vec<ObjectRef> = if outlines_in_first_page {
part6_outline_objects.clone()
} else {
vec![]
};
let raw = build_raw_linearization_plan(
pdf,
&optimization,
&part2_objects,
&part3_objects,
&part4_other_pages_shared,
&part4_rest,
&part4_open_document_plain,
&per_page_private_objects,
&page_refs,
&part9_outline_objects,
&part6_outline_objects,
root_ref,
pages_tree_ref,
info_ref,
&content_normalize_refs,
&removed_refs,
outlines_in_first_page,
)?; // cov:ignore: the raw plan builder consumes this qpdf outline-routing predicate; LLVM attributes the continuation to the call terminator
// Object counts are scalar hint inputs rather than source identities,
// so they may include raw-only objects even though the public object
// vectors are checked projections. Keep the public hint record
// accurate for both the classic and ObjStm-folded page-offset paths.
if let Some(first_hint) = page_hints.first_mut() {
first_hint.object_count = (raw.part2_objects.len()
+ raw.part3_objects.len()
+ raw.part6_outline_objects.len()) as u32;
}
for (page_index, hint) in page_hints.iter_mut().enumerate().skip(1) {
if let Some(private) = raw.per_page_private_objects.get(page_index) {
hint.object_count = private.len().max(1) as u32;
}
}
let part9_thumbnail_objects: Vec<ObjectRef> = raw
.part9_thumbnail_objects
.iter()
.filter_map(|object| object.to_object_ref())
.collect();
let part2_entries = part2_objects.iter().map(|&obj_ref| SharedObjectHintEntry {
object_ref: obj_ref,
referencing_pages: vec![],
});
let part3_entries = part3_objects.iter().map(|&obj_ref| {
let pages: Vec<u32> = shared_page_indices
.get(&obj_ref)
.map(|s| s.iter().copied().collect())
.unwrap_or_default();
// Do NOT add page 0: Part-3 shared objects are in the first-page
// section, so page 0 implicitly owns them by physical layout.
SharedObjectHintEntry {
object_ref: obj_ref,
referencing_pages: pages,
}
});
// Outline objects are in the first-page section (physically owned by
// page 0), so page 0 is not listed in referencing_pages. An outline
// object that is also reached from a later page must still list that
// later page: qpdf includes every part-6 object in the shared-object
// table and adds identifiers for later-page users
// (QPDF_linearization.cc:1354-1356,1388-1400).
let outline_entries = outline_first_page_members.iter().map(|&obj_ref| {
let pages: Vec<u32> = optimization
.page_users(obj_ref)
.filter(|&page| page != 0)
.collect();
SharedObjectHintEntry {
object_ref: obj_ref,
referencing_pages: pages,
}
});
// Part-4 shared objects: referenced by ≥ 2 pages but NOT in the
// first-page closure. These live after /E (not physically owned
// by any page via layout), so ALL referencing pages are listed.
let part4_shared_entries = part4_other_pages_shared.iter().map(|&obj_ref| {
let pages: Vec<u32> = optimization.page_users(obj_ref).collect();
SharedObjectHintEntry {
object_ref: obj_ref,
referencing_pages: pages,
}
});
let shared_hints: Vec<SharedObjectHintEntry> = part2_entries
.chain(part3_entries)
.chain(outline_entries)
.chain(part4_shared_entries)
.collect();
Ok(Self {
part1_objects: Vec::new(),
part2_objects,
part3_objects,
part4_other_pages_private,
part4_other_pages_shared,
part4_rest,
part4_open_document_plain,
writer_object_order: pdf.writer_object_order.clone(),
total_object_count,
root_ref,
pages_tree_ref,
info_ref,
page_hints,
shared_hints,
per_page_private_objects,
part9_thumbnail_objects,
outline_first_page_members,
part9_outline_objects,
part6_outline_objects,
object_stream_mode,
removed_refs,
optimization: Some(optimization),
preserve_objstm_plan,
content_normalize_refs: content_normalize_refs
.iter()
.filter_map(|object_gen| object_gen.to_object_ref())
.collect(),
raw,
})
}
/// Return the set of all objects assigned to at least one part.
///
/// Part-4 body objects (Annex F Part 5), in the order the writer emits them.
///
/// This is a derived view: the ordered concatenation of
/// [`part4_other_pages_private`](Self::part4_other_pages_private),
/// [`part4_other_pages_shared`](Self::part4_other_pages_shared), and
/// [`part4_rest`](Self::part4_rest). Callers that previously read a
/// `part4_objects` field should call this getter instead — it cannot
/// drift from the three sub-partitions because there is no separate
/// backing storage.
pub fn part4_objects(&self) -> Vec<ObjectRef> {
let mut objects: Vec<ObjectRef> = self
.part4_other_pages_private
.iter()
.chain(&self.part4_other_pages_shared)
.copied()
.collect();
// qpdf's root /Pages user can contain several nested Pages nodes. It
// places every such node that remains in lc_other before the rest of
// part9, not only the Catalog's direct /Pages object.
let part9_pages: BTreeSet<ObjectRef> = self
.optimization
.as_ref()
.map(|optimization| {
optimization
.objects_for_root_key(b"Pages")
.collect::<BTreeSet<ObjectRef>>()
})
.filter(|pages| !pages.is_empty())
.unwrap_or_else(|| self.pages_tree_ref.into_iter().collect());
for pages_tree in part9_pages.iter().copied() {
if self.part4_rest.contains(&pages_tree) {
objects.push(pages_tree);
}
}
objects.extend(self.part9_outline_objects.iter().copied());
objects.extend(
self.part4_rest
.iter()
.copied()
.filter(|object| !part9_pages.contains(object)),
);
objects
}
/// Fold first-page-section ObjStm members into their containers to match
/// qpdf's shared-object hint list.
///
/// When the first-page shared dicts are packed into a first-half ObjStm
/// container, qpdf lists the *container* (one entry) in the shared-object
/// hint table — not each compressed member. This rewrites
/// [`shared_hints`](Self::shared_hints): every member present in
/// `member_to_container` is replaced by a single entry for its container
/// (with the `referencing_pages` of all that container's members unioned),
/// and the second-and-later members of the same container are dropped.
/// Non-member entries are kept verbatim.
///
/// The first-page section of the result is then emitted in **ascending
/// physical object-number order**. qpdf's `checkHSharedObject` walks the
/// first-page shared entries positionally, starting from the first page
/// object, so the hint list must follow the order in which
/// [`RenumberMap::place_objstm_members_per_half`](crate::linearization::renumber::RenumberMap::place_objstm_members_per_half)
/// numbers the first half (plain objects first, then containers, then
/// compressed members). A plain (ineligible) shared stream can therefore be
/// numbered *before* the container of the eligible dicts even when the
/// container appeared earlier in `shared_hints`; the sort restores the
/// physical order. Part-8 entries (`part4_other_pages_shared`, after /E)
/// are left in place.
///
/// The container entry's `object_ref` carries the container's *new* object
/// number with generation `u16::MAX` — a sentinel no live object uses,
/// marking it as a synthetic container entry rather than a resolvable PDF
/// object. A plain entry carries an original ref whose physical number is
/// resolved through `renumber`; a synthetic container entry already carries
/// its new number, so it is never resolved through the
/// [`RenumberMap`].
///
/// ObjStm container object numbers that are qpdf **part8** (other-page-shared)
/// objects: their members reach two or more pages but none is a first-page
/// (Part-2 / Part-3) object.
///
/// The global even split can fill such a container entirely with objects that
/// are individually page-*private* (one page's privates co-located with
/// another's), so the container does not appear in `shared_hints` (built from
/// the per-object part2/part3/part4_shared partition) even though it is a
/// shared object that belongs in the shared-object hint table. This enumerates
/// those containers so the table and its entry counts include them.
pub(crate) fn part8_container_nums(
&self,
member_to_container: &BTreeMap<ObjectRef, (u32, u32)>,
) -> BTreeSet<u32> {
let first_page: BTreeSet<ObjectRef> = self
.part2_objects
.iter()
.chain(&self.part3_objects)
.copied()
.collect();
let part4_shared: BTreeSet<ObjectRef> =
self.part4_other_pages_shared.iter().copied().collect();
let mut all_containers: BTreeSet<u32> = BTreeSet::new();
let mut container_pages: BTreeMap<u32, BTreeSet<u32>> = BTreeMap::new();
let mut has_first_page_member: BTreeSet<u32> = BTreeSet::new();
let mut has_shared_member: BTreeSet<u32> = BTreeSet::new();
for (member, &(cnum, _)) in member_to_container {
all_containers.insert(cnum);
if first_page.contains(member) {
has_first_page_member.insert(cnum);
}
// A reach-≥2 (part4_other_pages_shared) member makes the container a
// shared object directly — used when optimization data is absent
// (e.g. manually-built plans) and as a robust signal otherwise.
if part4_shared.contains(member) {
has_shared_member.insert(cnum);
}
if let Some(optimization) = self.optimization.as_ref() {
container_pages
.entry(cnum)
.or_default()
.extend(optimization.page_users(*member).filter(|&p| p != 0));
}
}
// A container is part8 when no member is a first-page object AND it is
// shared — either it holds an explicitly-shared (reach-≥2) member, or its
// members span two or more pages (the even split co-located two pages'
// privates).
all_containers
.into_iter()
.filter(|cnum| {
!has_first_page_member.contains(cnum)
&& (has_shared_member.contains(cnum)
|| container_pages.get(cnum).is_some_and(|p| p.len() >= 2))
})
.collect()
}
/// ObjStm container new-numbers routed to part9 (Rest) by qpdf's outline
/// priority (QPDF_linearization.cc:1118-1122): every container carrying a
/// `part9_outline_objects` member.
///
/// Such a container is placed in the second half even when the global even
/// split co-locates a `part4_other_pages_shared` object in it, and it is NOT
/// a shared object in qpdf's Shared Object Hint Table. Both
/// [`Self::canonical_shared_hints`] (the Part-8 main-loop guard and the
/// `part8_container_nums` enumeration tail) and
/// `SharedObjectHintTable::from_plan` (the Part-8 entry COUNT, which feeds
/// `first_page_entries`) must exclude it, or the table's entry list and its
/// header counts disagree.
///
/// A member reachable from BOTH `/Outlines` and ≥2 non-first pages stays in
/// `part4_other_pages_shared` rather than `part9_outline_objects`, so a
/// container carrying ONLY such a member (no other `part9_outline_objects`
/// member) is missed here. That can only happen across a 2+-container even
/// split, which is blocked by the page-dict-erasure boundary divergence
/// (flpdf-g1eu); the robust fix (keying on the actual Rest routing) lands with
/// that issue's 2-container fixture. `part9_outline_objects` is small, so look
/// each up in `member_to_container` rather than scanning all members.
pub(crate) fn rest_container_nums(
&self,
member_to_container: &BTreeMap<ObjectRef, (u32, u32)>,
) -> BTreeSet<u32> {
self.part9_outline_objects
.iter()
.filter_map(|member| member_to_container.get(member).map(|&(cnum, _)| cnum))
.collect()
}
/// An empty `member_to_container` yields a clone of `shared_hints` (the
/// no-ObjStm / classic path is unchanged).
pub(crate) fn canonical_shared_hints(
&self,
member_to_container: &BTreeMap<ObjectRef, (u32, u32)>,
renumber: &RenumberMap,
second_half_container_nums: &BTreeSet<u32>,
open_document_container_nums: &BTreeSet<u32>,
) -> Vec<SharedObjectHintEntry> {
if member_to_container.is_empty() {
return self.shared_hints.clone();
}
// The first-page section of `shared_hints` is the leading part2 ++ part3
// ++ outline entries; trailing entries are Part-8 (`part4_other_pages_shared`,
// after /E).
// Invariant: this split is only correct because `Self::new` builds
// `shared_hints` as exactly `part2_entries ++ part3_entries ++
// outline_entries ++ part4_shared_entries` (one entry per object, no filter).
// Keep the two in lockstep — reordering the construction there silently
// breaks this boundary.
let first_page_input = self.part2_objects.len()
+ self.part3_objects.len()
+ self.outline_first_page_members.len();
// Containers routed to part9 (Rest) by qpdf's outline priority: never
// shared objects in the SOHT, so skip them in the Part-8 section here AND
// in the `part8_container_nums` enumeration tail below. The first-page
// section is already covered by the `second_half_container_nums` guard
// (it skips ALL second-half containers there); in the Part-8 section that
// guard cannot be reused because it would also drop legitimate part8
// containers. See [`Self::rest_container_nums`].
let rest_container_nums = self.rest_container_nums(member_to_container);
// Position (index into the output list) at which each container was
// first emitted, so later members of the same container fold into it.
let mut container_pos: BTreeMap<u32, usize> = BTreeMap::new();
let mut out: Vec<SharedObjectHintEntry> = Vec::with_capacity(self.shared_hints.len());
let mut first_page_out_end: Option<usize> = None;
for (input_idx, entry) in self.shared_hints.iter().enumerate() {
if input_idx == first_page_input {
// Crossed into the Part-8 region: freeze the first-page boundary.
first_page_out_end = Some(out.len());
}
match member_to_container.get(&entry.object_ref) {
Some(&(container_num, _idx)) => {
// Open-document containers live in the pre-/O region (before
// the first-page section and before /E), so qpdf excludes
// them from the SOHT unconditionally — regardless of whether
// the triggering entry is in the first-page section or in the
// Part-8 section.
if open_document_container_nums.contains(&container_num) {
continue;
}
// Within the first-page section: skip second-half
// (outline-routed) ObjStm containers placed after /E.
if input_idx < first_page_input
&& second_half_container_nums.contains(&container_num)
{
continue;
}
// Within the Part-8 section: skip part9 (Rest) containers that
// qpdf's outline priority placed in the second half. The
// first-page guard above cannot fire here (input_idx is past
// the boundary), and `second_half_container_nums` would wrongly
// also drop legitimate part8 containers — so key on the
// part9-only `rest_container_nums` instead.
if input_idx >= first_page_input && rest_container_nums.contains(&container_num)
{
continue;
}
if let Some(&pos) = container_pos.get(&container_num) {
// Fold into the already-emitted container entry: union
// the referencing pages (dedup, keep ascending order).
let merged: &mut Vec<u32> = &mut out[pos].referencing_pages;
for &p in &entry.referencing_pages {
if let Err(insert_at) = merged.binary_search(&p) {
merged.insert(insert_at, p);
}
}
} else {
// First member of this container: emit one entry for the
// container, carrying its new object number. The
// generation is the sentinel `u16::MAX`: no live object
// ever uses it, so consumers can identify this synthetic
// container entry unambiguously — even when `container_num`
// coincides with a surviving original object's number,
// which would otherwise resolve through a `RenumberMap`.
let mut pages = entry.referencing_pages.clone();
pages.sort_unstable();
pages.dedup();
container_pos.insert(container_num, out.len());
out.push(SharedObjectHintEntry {
object_ref: ObjectRef::new(container_num, u16::MAX),
referencing_pages: pages,
});
}
}
None => out.push(entry.clone()),
}
}
// Reorder the first-page section to ascending physical object number —
// the order qpdf's `checkHSharedObject` walks (positionally from the
// first page object). `place_objstm_members_per_half` numbers the first
// half as plain… then containers…, so a plain ObjStm-ineligible shared
// stream is numbered BEFORE the container of the eligible dicts. A
// folded container entry carries its new number with the sentinel
// generation `u16::MAX`; a plain entry carries an original ref resolved
// through `renumber`. Part-8 entries (after the boundary) stay in place.
let boundary = first_page_out_end.unwrap_or(out.len());
let new_number = |e: &SharedObjectHintEntry| -> u32 {
if e.object_ref.generation == u16::MAX {
e.object_ref.number
} else {
// A malformed source can carry a reserved/dangling reference
// (object number 0, any generation) into the first-page closure
// and thus into `shared_hints`; `place_objstm_members_per_half`
// rebuilds the forward renumber index while dropping object
// number 0 (it doubles as the reserved-slot sentinel), so such an
// entry has no mapping here. Sort it deterministically last
// instead of panicking — the writer's shared-hint back-patch
// (`new_for_original(..).ok_or_else(Err)`, gated only on a
// non-empty `shared_hints` and run before any output) then
// surfaces the planner/renumber inconsistency as a structured
// error. For a well-formed PDF every shared-hint object has a
// mapping, so this fallback never triggers and the order is
// unchanged. Mirrors `SharedObjectHintTable::from_plan`'s
// `new_for_original(..).map_or(0, ..)` graceful handling.
renumber
.new_for_original(e.object_ref)
.map_or(u32::MAX, |r| r.number)
}
};
out[..boundary].sort_unstable_by_key(&new_number);
// Append any qpdf part8 (other-page-shared) ObjStm container that the
// even split filled entirely with page-PRIVATE objects: such a container
// never appears in `shared_hints` (no part2/part3/part4_shared member) but
// IS a shared object in qpdf's hint table. Skip containers already folded
// into `out` (those carry a part4_shared member). Then order the whole
// Part-8 section by physical object number, matching qpdf's ObjGen-keyed
// `lc_other_page_shared`.
for cnum in self.part8_container_nums(member_to_container) {
// Open-document containers live in the pre-/O region (before the
// first-page section), so qpdf excludes them from the SOHT even
// when their members span multiple later pages (which would
// otherwise qualify them as Part-8 shared containers via the
// `container_pages.len() >= 2` criterion in `part8_container_nums`).
//
// A part9 (Rest) container routed there by outline priority must also
// be excluded here, not just in the main loop above. `part8_container_nums`
// keys on page reachability (`!has_first_page_member && shared/≥2 pages`),
// so when the co-located part9 container has NO ObjStm-eligible
// first-page member (e.g. page 0 carries no compressible private object)
// it satisfies that predicate and would be re-added as a Part-8 entry —
// re-introducing exactly the SOHT divergence the main-loop guard removes.
if !container_pos.contains_key(&cnum)
&& !open_document_container_nums.contains(&cnum)
&& !rest_container_nums.contains(&cnum)
{
out.push(SharedObjectHintEntry {
object_ref: ObjectRef::new(cnum, u16::MAX),
referencing_pages: Vec::new(), // recomputed below
});
}
}
out[boundary..].sort_unstable_by_key(&new_number);
// Recompute each entry's referencing pages from its FULL membership via
// the retained qpdf-shaped object-user map (excluding page 0, which
// owns the first-page section and lists no shared identifiers). The fold above unions only
// the `shared_hints` inputs (part2/part3/part4_shared); the global even
// split can also place a page's PRIVATE object inside a shared container
// (the first-page part6 container, or a part8 container co-locating two
// pages' privates), and the page then references that container through
// the private object — a reference the input entries do not record. This
// is a no-op for documents whose containers hold only shared_hints
// objects (the union is identical).
if let Some(optimization) = self.optimization.as_ref().filter(|optimization| {
optimization.object_users().any(|(_, users)| {
users
.iter()
.any(|user| matches!(user, crate::optimization::ObjectUser::Page(_)))
})
}) {
let mut container_members: BTreeMap<u32, Vec<ObjectRef>> = BTreeMap::new();
for (&member, &(cnum, _)) in member_to_container {
container_members.entry(cnum).or_default().push(member);
}
let pages_excluding_first = |refs: &mut dyn Iterator<Item = ObjectRef>| -> Vec<u32> {
let mut pages: BTreeSet<u32> = BTreeSet::new();
for r in refs {
pages.extend(optimization.page_users(r).filter(|&p| p != 0));
}
pages.into_iter().collect()
};
for entry in &mut out {
entry.referencing_pages = if entry.object_ref.generation == u16::MAX {
let members = container_members
.get(&entry.object_ref.number)
.cloned()
.unwrap_or_default();
pages_excluding_first(&mut members.into_iter())
} else {
pages_excluding_first(&mut std::iter::once(entry.object_ref))
};
}
}
out
}
/// Return the shared-hint inputs without narrowing raw source identities.
/// The public `canonical_shared_hints` view remains available to callers
/// that expose `SharedObjectHintEntry`; linearization hint encoders use
/// this raw view so a first-page or Part-8 object with generation 65536 is
/// still counted and looked up through `RenumberMap::new_for_raw`.
pub(crate) fn canonical_raw_shared_hints(
&self,
member_to_container: &BTreeMap<ObjectRef, (u32, u32)>,
renumber: &RenumberMap,
second_half_container_nums: &BTreeSet<u32>,
open_document_container_nums: &BTreeSet<u32>,
) -> Vec<RawSharedObjectHintEntry> {
let has_raw_plan = self.has_raw_projection_gap();
if member_to_container.is_empty() {
if has_raw_plan {
return self.raw.shared_hints.clone();
}
return self
.shared_hints
.iter()
.filter_map(|entry| {
QpdfObjGen::try_from_object_ref(entry.object_ref)
.ok()
.map(|object| RawSharedObjectHintEntry {
object: Some(object),
container: None,
referencing_pages: entry.referencing_pages.clone(),
})
})
.collect();
}
let public = self.canonical_shared_hints(
member_to_container,
renumber,
second_half_container_nums,
open_document_container_nums,
);
let mut result: Vec<RawSharedObjectHintEntry> = public
.into_iter()
.filter_map(|entry| {
if entry.object_ref.generation == u16::MAX {
Some(RawSharedObjectHintEntry {
object: None,
container: Some(entry.object_ref.number),
referencing_pages: entry.referencing_pages,
})
} else {
QpdfObjGen::try_from_object_ref(entry.object_ref)
.ok()
.map(|object| RawSharedObjectHintEntry {
object: Some(object),
container: None,
referencing_pages: entry.referencing_pages,
})
}
})
.collect();
if !has_raw_plan {
return result;
}
let first_page_input = self.part2_objects.len()
+ self.part3_objects.len()
+ self.outline_first_page_members.len();
let mut first_page_count = 0usize;
let mut folded_containers = BTreeSet::new();
for entry in self.shared_hints.iter().take(first_page_input) {
if let Some(&(container_num, _)) = member_to_container.get(&entry.object_ref) {
if open_document_container_nums.contains(&container_num)
|| second_half_container_nums.contains(&container_num)
{
continue; // cov:ignore: raw-only additions cannot be ObjStm members; this is the projected-container exclusion guard
}
if folded_containers.insert(container_num) {
first_page_count += 1;
}
} else {
first_page_count += 1;
}
}
let first_page_raw: BTreeSet<QpdfObjGen> = self
.raw
.part2_objects
.iter()
.chain(&self.raw.part3_objects)
.chain(&self.raw.part6_outline_objects)
.filter(|object| object.to_object_ref().is_none())
.copied()
.collect();
let part8_raw: BTreeSet<QpdfObjGen> = self
.raw
.part4_other_pages_shared
.iter()
.filter(|object| object.to_object_ref().is_none())
.copied()
.collect();
let mut first_extra = Vec::new();
let mut part8_extra = Vec::new();
for entry in &self.raw.shared_hints {
let Some(object) = entry.object else {
continue; // cov:ignore: raw shared-hint records contain source identities only; synthetic containers come from the public folded view
};
if first_page_raw.contains(&object) {
first_extra.push(entry.clone());
} else if part8_raw.contains(&object) {
part8_extra.push(entry.clone());
}
}
let raw_number = |entry: &RawSharedObjectHintEntry| {
entry.container.unwrap_or_else(|| {
entry
.object
.and_then(|object| renumber.new_for_raw(object))
.map_or(u32::MAX, |object_ref| object_ref.number)
})
};
first_extra.sort_unstable_by_key(&raw_number);
let first_extra_count = first_extra.len();
result.splice(first_page_count..first_page_count, first_extra);
let first_page_end = first_page_count + first_extra_count;
result[..first_page_end].sort_unstable_by_key(&raw_number);
// `result` already has the canonical first-page/Part-8 split. Raw
// Part-8 entries must join the existing suffix at the physical output
// position assigned by the same `RenumberMap`, rather than being
// appended after every checked entry. This preserves the order that
// qpdf's shared-hint checker derives from its emitted object units.
result.extend(part8_extra);
result[first_page_end..].sort_unstable_by_key(&raw_number);
result
}
pub(crate) fn has_raw_projection_gap(&self) -> bool {
self.raw.projection_gap
}
/// Useful for callers that want to verify the disjoint invariant.
/// Uses the three fine-grained Part-4 sub-partitions as the canonical
/// source of truth.
pub fn all_assigned_refs(&self) -> BTreeSet<ObjectRef> {
self.part1_objects
.iter()
.chain(&self.part2_objects)
.chain(&self.part3_objects)
.chain(&self.part4_other_pages_private)
.chain(&self.part4_other_pages_shared)
.chain(&self.part4_rest)
.copied()
.collect()
}
/// Return qpdf's destination-object ordering projection for a plan ref.
///
/// A page-selection target retains this map from the merge job so hint
/// consumers can compare objects across Part 3 and Part 8 without falling
/// back to fresh target object numbers. Ordinary parsed documents use the
/// live ref as their destination ObjGen, matching qpdf's direct order.
pub(crate) fn writer_object_order_key(&self, object_ref: ObjectRef) -> WriterObjectOrderKey {
match &self.writer_object_order {
Some(order) => order
.get(&object_ref)
.copied()
.unwrap_or_else(|| WriterObjectOrderKey::fresh(object_ref)),
None => WriterObjectOrderKey::primary(object_ref),
}
}
/// The refs that [`RenumberMap::from_plan`] assigns a renumber slot
/// (`by_original` key set).
///
/// This is the exact union of the parts `from_plan` walks
/// (`crates/flpdf/src/linearization/renumber.rs`): part2, part3, the two
/// Part-4 page sets, part4_rest (which subsumes the promoted pages-tree /
/// info / catalog refs), the two outline sets, and the open-document plain
/// set. `part1_objects` is deliberately excluded — `from_plan` never maps
/// it (and it is always empty today).
///
/// A generated ObjStm may only batch members drawn from this set: an
/// ObjStm member that lacks a renumber slot makes
/// [`RenumberMap::place_objstm_members_per_half`] panic. The
/// `renumber_assigned_refs_match_from_plan` test pins this set to
/// `from_plan`'s `by_original` keys so the two cannot drift apart.
pub(crate) fn renumber_assigned_refs(&self) -> BTreeSet<ObjectRef> {
self.part2_objects
.iter()
.chain(&self.part3_objects)
.chain(&self.part4_other_pages_private)
.chain(&self.part4_other_pages_shared)
.chain(&self.part4_rest)
.chain(&self.part6_outline_objects)
.chain(&self.part9_outline_objects)
.chain(&self.part4_open_document_plain)
.copied()
.collect()
}
/// Raw source identities that receive linearization slots. This is the
/// generation-preserving counterpart to `renumber_assigned_refs`; the
/// latter intentionally remains a checked projection for ObjStm planner
/// APIs that can only accept valid PDF references.
pub(crate) fn renumber_assigned_raw(&self) -> BTreeSet<QpdfObjGen> {
let has_raw_plan = self.raw.root.is_some()
|| !self.raw.part2_objects.is_empty()
|| !self.raw.part3_objects.is_empty()
|| !self.raw.part4_other_pages_private.is_empty()
|| !self.raw.part4_other_pages_shared.is_empty()
|| !self.raw.part4_rest.is_empty()
|| !self.raw.part4_open_document_plain.is_empty();
if has_raw_plan {
self.raw
.part2_objects
.iter()
.chain(&self.raw.part3_objects)
.chain(&self.raw.part4_other_pages_private)
.chain(&self.raw.part4_other_pages_shared)
.chain(&self.raw.part4_rest)
.chain(&self.raw.part6_outline_objects)
.chain(&self.raw.part9_outline_objects)
.chain(&self.raw.part4_open_document_plain)
.copied()
.collect()
} else {
self.renumber_assigned_refs()
.into_iter()
.filter_map(|object_ref| QpdfObjGen::try_from_object_ref(object_ref).ok())
.collect()
}
}
/// Return `true` if every object appears in **at most** one part.
/// Uses the three fine-grained Part-4 sub-partitions as the canonical
/// source of truth.
pub fn parts_are_disjoint(&self) -> bool {
let mut seen = BTreeSet::new();
for r in self
.part1_objects
.iter()
.chain(&self.part2_objects)
.chain(&self.part3_objects)
.chain(&self.part4_other_pages_private)
.chain(&self.part4_other_pages_shared)
.chain(&self.part6_outline_objects)
.chain(&self.part9_outline_objects)
.chain(&self.part4_rest)
.chain(&self.part4_open_document_plain)
{
if !seen.insert(*r) {
return false;
}
}
true
}
}
impl Default for LinearizationPlan {
/// Construct a blank plan with no objects in any part.
///
/// Useful in test fixtures via `LinearizationPlan { part2_objects: ...,
/// ..Default::default() }` to avoid repeating empty-vec boilerplate for
/// fields that are not under test.
fn default() -> Self {
Self {
part1_objects: Vec::new(),
part2_objects: Vec::new(),
part3_objects: Vec::new(),
part4_other_pages_private: Vec::new(),
part4_other_pages_shared: Vec::new(),
part4_rest: Vec::new(),
part4_open_document_plain: Vec::new(),
writer_object_order: None,
total_object_count: 0,
root_ref: None,
pages_tree_ref: None,
info_ref: None,
page_hints: Vec::new(),
shared_hints: Vec::new(),
per_page_private_objects: Vec::new(),
part9_thumbnail_objects: Vec::new(),
outline_first_page_members: Vec::new(),
part9_outline_objects: Vec::new(),
part6_outline_objects: Vec::new(),
optimization: None,
preserve_objstm_plan: None,
removed_refs: BTreeSet::new(),
object_stream_mode: crate::writer::ObjectStreamMode::Disable,
content_normalize_refs: BTreeSet::new(),
raw: RawLinearizationPlan::default(),
}
}
}
// ---------------------------------------------------------------------------
// ObjStm batch planning
// ---------------------------------------------------------------------------
/// Part-tagged ObjStm batch plan produced by `LinearizationPlan::objstm_batches`.
///
/// Each inner `Vec<ObjectRef>` describes one ObjStm container; the contained
/// refs are still **original** (pre-renumber) object references. Renumbering
/// and actual container-object allocation happen in downstream subtasks (5.8.2+).
///
/// # Part constraints
///
/// * `open_document_batches` — containers qpdf categorizes `in_open_document`
/// (qpdf part4: the open-document objects placed FIRST in the first half,
/// right after the Catalog and before the first-page section). A container
/// lands here when any member is reachable from the catalog's `/OpenAction`,
/// `/AcroForm`, `/ViewerPreferences`, `/PageMode`, `/Threads`, or the
/// trailer's `/Encrypt`.
/// * `part3_batches` — containers that belong in the first-page section
/// (ISO 32000-1 Annex F Part 3 = qpdf part6: shared/catalog objects).
/// * `part4_batches` — containers that belong after `/E` (Part 4 = qpdf
/// part7/8/9: remaining document objects from `part4_other_pages_private`,
/// `part4_other_pages_shared`, and `part4_rest`).
///
/// Every ObjStm container has one union-derived route. Its members may have
/// different classic per-object parts, but the container itself is emitted
/// wholly in that one qpdf-selected part. Page dictionaries and the Catalog
/// are never placed in any batch list.
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub(crate) struct ObjStmBatchPlan {
/// ObjStm batches for qpdf part4 (open-document objects). Numbered and
/// emitted in the first half, before the first-page section.
pub(crate) open_document_batches: Vec<RoutedObjStmBatch>,
/// ObjStm batches for Part 3 (shared/catalog) objects.
pub(crate) part3_batches: Vec<RoutedObjStmBatch>,
/// ObjStm batches for Part 4 (rest-of-document) objects.
pub(crate) part4_batches: Vec<RoutedObjStmBatch>,
}
impl LinearizationPlan {
/// Build a Part-tagged ObjStm packing plan from this `LinearizationPlan`.
///
/// # Mode behaviour
///
/// | Mode | Result |
/// |------|--------|
/// | `Disable` | Both batch lists are empty (no ObjStms emitted). |
/// | `Generate` | Eligible Part-3 (first-page shared) objects are packed into `part3_batches`; eligible Part-4 objects are packed into `part4_batches`. The membership is qpdf-canonical by construction (a global even split with the page dictionaries and `/Catalog` erased), so no post-packing reshape is applied. |
/// | `Preserve` | Each surviving source ObjStm is retained as one container and routed once from the union of its members' users. Page dictionaries, the `/Catalog`, unassigned objects, and ineligible members are removed; `/Pages` and `/Info` stay with their source container. Part-9 containers are ordered as qpdf emits them: `/Pages`, thumbnails, outlines, then remaining `lc_other`, with source-container order as the tie-break. The configured Generate batch cap is ignored because qpdf Preserve neither splits nor re-chunks source containers. If the source document contained no ObjStms, all batch lists are empty. |
///
/// **Note:** the `/Pages` tree and `/Info` dictionary are not relocated.
/// qpdf's `preserveObjectStreams` copies the source object->stream
/// assignment and the linearized pass only erases the `/Page` dictionaries
/// and the `/Catalog` (QPDFWriter.cc:1939, 2141-2161); the `/Pages` tree and
/// `/Info` stay in their source container. Preserve mirrors that by routing
/// them into their source container's first-half batch, so the resulting
/// container membership matches qpdf.
///
/// # Invariants
///
/// * No page dictionary or Catalog ref appears in any batch.
/// * Ineligible objects (streams, gen > 0, encryption dict, `/Type /ObjStm`,
/// `/Type /XRef`) are excluded via the
/// shared [`crate::writer::object_streams::is_eligible_for_objstm_handle`]
/// predicate.
/// * Generate uses qpdf's fixed even split; Preserve retains source
/// container boundaries regardless of the configured planner cap.
///
/// # Snapshot contract
///
/// For Generate and Preserve, construct this plan with [`Self::from_pdf`]
/// from the same `Pdf` passed here, and pass `true` to `from_pdf` exactly
/// for Generate mode. Both modes classify their container-member unions
/// from that one retained object-user snapshot. A hand-built plan without
/// the snapshot is accepted only in Disable mode.
pub(crate) fn objstm_batches<R: Read + Seek>(
&self,
pdf: &mut Pdf<R>,
config: &PlannerConfig,
) -> crate::Result<ObjStmBatchPlan> {
if config.mode == ObjectStreamMode::Disable {
return Ok(ObjStmBatchPlan::default());
}
let optimization = self.optimization.as_ref().ok_or_else(|| {
crate::Error::Unsupported(
"linearization plan: missing optimization snapshot".to_string(),
)
})?;
let ctx = eligibility_context(pdf)?;
// Preserve already owns the setup-time source membership and its
// stale-generation result in `preserve_objstm_plan`; neither the
// Preserve batch planner nor its routed consumers use the indirect
// `/Length` exclusion set. qpdf only needs this compressible walk for
// Generate's fresh membership traversal.
let length_exclusions = if config.mode == ObjectStreamMode::Generate {
compressible_objgens_qpdf_plan(pdf)?.indirect_objstm_length_refs
} else {
BTreeSet::new()
};
let plan = match config.mode {
ObjectStreamMode::Disable => unreachable!(),
ObjectStreamMode::Generate => {
// The Generate path reproduces qpdf's linearized
// `generateObjectStreams` directly: a GLOBAL even split over the
// compressible set, with the page dictionaries + root Catalog
// erased and `/Info` / the `/Pages` tree kept as ordinary
// members. That membership is already qpdf-canonical, so no
// post-packing reshape is applied.
self.objstm_batches_generate(pdf, config, &ctx, &length_exclusions, optimization)?
}
ObjectStreamMode::Preserve => {
self.objstm_batches_preserve(pdf, config, &ctx, &length_exclusions, optimization)?
}
};
Ok(plan)
}
/// Generate mode: reproduce qpdf's linearized `generateObjectStreams`.
///
/// A GLOBAL even split over the compressible set
/// ([`objstm_membership_linearized_with_eligibility`]), with the page dictionaries + root
/// Catalog erased, then each container routed to a linearization part by the
/// union of its members' page users ([`route_objstm_containers`]). Containers
/// routed to part 6 ([`ContainerPart::FirstPagePrivate`],
/// [`ContainerPart::FirstPageShared`], or
/// [`ContainerPart::FirstPageOutlines`]) become first-half
/// (`part3_batches`); every other container becomes second-half
/// (`part4_batches`). Within a container, members use qpdf's
/// source/destination order key: ordinary and primary objects use their
/// source object number, while foreign and fresh merge objects use their
/// destination allocation order (`object_stream_to_objects` is a
/// `std::set<QPDFObjGen>`).
///
/// This replaces flpdf's earlier per-part greedy chunking, which diverged
/// from qpdf at `>cap` (see `docs/plans/2026-06-17-objstm-generate-linearized-phase2.md`).
///
/// The `config` / `ctx` / `length_exclusions` arguments are unused: the
/// compressible-set traversal applies qpdf's own eligibility and a fixed
/// 100-per-stream split (not the planner cap).
fn objstm_batches_generate<R: Read + Seek>(
&self,
pdf: &mut Pdf<R>,
_config: &PlannerConfig,
_ctx: &crate::writer::object_streams::EligibilityContext,
_length_exclusions: &BTreeSet<ObjectRef>,
optimization: &crate::optimization::Optimization,
) -> crate::Result<ObjStmBatchPlan> {
// `objstm_membership_linearized` filters its containers to the plan's
// renumber-assigned set BEFORE the even split, so a trailer-only ref with
// no slot neither inflates the split boundary nor reaches
// `place_objstm_members_per_half` without a slot (which would panic).
// Dangling/missing refs (e.g. `/Info 99 0 R` with no xref entry) are
// already excluded upstream by `get_compressible_objgens`. For a well-formed
// PDF every member is assigned, so the filter is a no-op and the batches
// stay byte-identical.
let assigned = self.renumber_assigned_refs();
let containers = objstm_membership_linearized_with_eligibility(
pdf,
&assigned,
optimization.generate_objstm_eligible(),
)?; // cov:ignore: closing line of a multi-line call; llvm-cov misattributes the hit count to the previous line, not an untested branch
let routes = route_objstm_containers(
optimization,
!self.outline_first_page_members.is_empty(),
&containers,
);
let mut open_document_batches: Vec<RoutedObjStmBatch> = Vec::new();
// qpdf part 6 is private, shared, then outline containers. Preserve
// first-encounter order within each bucket.
let mut part3_private: Vec<RoutedObjStmBatch> = Vec::new();
let mut part3_shared: Vec<RoutedObjStmBatch> = Vec::new();
let mut part3_outlines: Vec<RoutedObjStmBatch> = Vec::new();
// Second-half containers, grouped by part so they can be emitted in qpdf's
// strict part order (part7, then part8, then part9 — QPDF_linearization.cc:1342).
// qpdf's file layout writes lc_other_page_private, lc_other_page_shared, then
// lc_other/lc_outlines; the even-split (DFS) order a container arrives in is
// NOT that order (a DFS-early /Outlines container routes to part9 yet precedes
// a part8 shared-font container in the split). Bucketing into three vectors and
// concatenating them (like the part3 regular/outlines split below) reorders only
// ACROSS parts, leaving within-part even-split arrival order intact.
//
// For part8 that within-part order is qpdf's `std::set<QPDFObjGen>` order:
// a generate-mode container's ObjGen comes from makeIndirectObject in
// even-split order. Part7 is ordered page by page, while part9 has its
// own Pages-tree / thumbnail / outlines / remaining-object sub-order.
// The latter two are sorted below after routing; stable ties retain the
// even-split order within one qpdf category.
let mut part4_private: Vec<RoutedObjStmBatch> = Vec::new();
let mut part4_shared: Vec<RoutedObjStmBatch> = Vec::new();
let mut part4_rest: Vec<RoutedObjStmBatch> = Vec::new();
for (mut members, route) in containers.into_iter().zip(routes) {
members.sort_unstable_by_key(|r| pdf.writer_object_order_key(*r));
push_routed_objstm_batch(
members,
route,
None,
&mut open_document_batches,
&mut part3_private,
&mut part3_shared,
&mut part3_outlines,
&mut part4_private,
&mut part4_shared,
&mut part4_rest,
);
}
// qpdf's Part 9 emission is not simply the order in which generated
// containers arrive from the global DFS split. It emits the container
// carrying the `/Pages` user set first, then private thumbnails in page
// order, shared thumbnails, outlines, and finally the remaining
// `lc_other` containers (QPDF_linearization.cc:1279-1337). A container
// inherits the union of its member users (QPDF_optimization.cc:340-380),
// so outline membership has precedence over every later category and a
// `/Pages` member has precedence over a thumbnail/rest member in the
// `lc_other` category. Keep only the category rank in the key: stable
// sorting then preserves qpdf's ObjGen/even-split order within a
// category. Preserve mode has its own source-ObjGen anchor path and does
// not use this Generate-only ordering.
let part9_pages: BTreeSet<ObjectRef> =
optimization.objects_for_root_key(b"Pages").collect();
part4_rest.sort_by_key(|batch| {
part9_category_order_key(optimization, &part9_pages, batch.members.iter())
});
// Concatenate the buckets in part order (part7, part8, part9).
let mut part4_batches = part4_private;
part4_batches.extend(part4_shared);
part4_batches.extend(part4_rest);
// qpdf part 6 order: private, shared, then outlines.
let mut part3_batches = part3_private;
part3_batches.extend(part3_shared);
part3_batches.extend(part3_outlines);
Ok(ObjStmBatchPlan {
open_document_batches,
part3_batches,
part4_batches,
})
}
/// Preserve mode: retain each surviving source ObjStm and route its member-user union.
fn objstm_batches_preserve<R: Read + Seek>(
&self,
pdf: &mut Pdf<R>,
_config: &PlannerConfig,
_ctx: &crate::writer::object_streams::EligibilityContext,
_length_exclusions: &BTreeSet<ObjectRef>,
optimization: &crate::optimization::Optimization,
) -> crate::Result<ObjStmBatchPlan> {
// QPDFWriter::preserveObjectStreams is the shared owner of source
// membership. It captures the document map before the compressible walk,
// applies preserve-unreferenced policy, and retains source-container
// identity for every group. Linearization only adds its output-sensitive
// page/Catalog/signature/assigned filtering and part routing below.
let source_plan = match self.preserve_objstm_plan.clone() {
Some(plan) => plan,
None => {
// cov:ignore-start: only hand-built Preserve plans lack the setup-owned snapshot
crate::writer::object_streams::plan_qpdf_preserve_object_streams_with_unreferenced(
pdf,
_config.preserve_unreferenced_objects,
)?
// cov:ignore-end
} // cov:ignore: hand-built test plans do not carry the setup snapshot
}; // cov:ignore: LLVM attributes this covered multiline planner terminator to the call setup
let mut assigned = self.renumber_assigned_refs();
for group in &source_plan.groups {
if let crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
members, ..
} = group
{
assigned.extend(members.iter().copied());
}
}
let mut containers: Vec<Vec<ObjectRef>> = Vec::new();
let mut source_container_refs: Vec<Option<ObjectRef>> = Vec::new();
for group in source_plan.groups {
let crate::writer::object_streams::ObjectStreamGroup::SourceBacked { source, members } =
group
else {
// cov:ignore-start: the shared Preserve planner returns SourceBacked groups only.
return Err(crate::Error::Internal(
"linearized Preserve planner returned a generated ObjStm group".to_string(),
)); // cov:ignore: defensive invariant rejects an impossible generated group
// cov:ignore-end
};
let mut surviving = Vec::new();
for obj_ref in members {
if !assigned.contains(&obj_ref) {
continue;
}
let obj = pdf.get_object_handle(obj_ref);
if !crate::writer::object_streams::is_qpdf_signature_dict(&obj)? {
surviving.push(obj_ref);
}
}
if !surviving.is_empty() {
source_container_refs.push(Some(source));
containers.push(surviving);
}
}
crate::writer::object_streams::filter_objstm_batches_for_output(
pdf,
&mut containers,
&mut source_container_refs,
true,
false,
)?; // cov:ignore: LLVM attributes this covered multiline exclusion terminator to the call setup
let routes = route_preserve_objstm_containers(
optimization,
!self.outline_first_page_members.is_empty(),
&containers,
&source_container_refs,
);
let mut open_document_batches = Vec::new();
let mut part3_private = Vec::new();
let mut part3_shared = Vec::new();
let mut part3_outlines = Vec::new();
let mut part4_private = Vec::new();
let mut part4_shared = Vec::new();
let mut part4_rest = Vec::new();
for ((members, route), source_container_ref) in containers
.into_iter()
.zip(routes)
.zip(source_container_refs)
{
let source_container_number = source_container_ref
.expect("Preserve ObjStm batch retains its source container")
.number;
push_routed_objstm_batch(
members,
route,
Some(source_container_number),
&mut open_document_batches,
&mut part3_private,
&mut part3_shared,
&mut part3_outlines,
&mut part4_private,
&mut part4_shared,
&mut part4_rest,
);
}
let mut part3_batches = part3_private;
part3_batches.extend(part3_shared);
part3_batches.extend(part3_outlines);
let mut part4_batches = part4_private;
part4_batches.extend(part4_shared);
// qpdf's Part 9 is not source-container order. After the Pages user set,
// it places private/shared thumbnail groups, outlines, and only then the
// remaining lc_other containers (QPDF_linearization.cc:1279-1337).
// Preserve retains source container boundaries, so apply that category
// order to the containers while retaining source-number order within a
// category. The folded Optimization map must be queried with the source
// container itself, not with its compressed members.
let part9_pages: BTreeSet<ObjectRef> =
optimization.objects_for_root_key(b"Pages").collect();
part4_rest.sort_by_key(|batch| {
let source_container_number = batch
.source_container_number
.expect("Preserve Part-9 batch must retain its source container");
let source_container = ObjectRef::new(source_container_number, 0);
let (category, page) =
part9_category_order_key(optimization, &part9_pages, [&source_container]);
(category, page, source_container_number)
});
part4_batches.extend(part4_rest);
Ok(ObjStmBatchPlan {
open_document_batches,
part3_batches,
part4_batches,
})
}
}
// ---------------------------------------------------------------------------
// Linearized generate-mode ObjStm membership + container part routing
//
// These mirror qpdf 11.9.0's linearized `--object-streams=generate` pipeline:
// * `objstm_membership_linearized` = `generateObjectStreams` (global even
// split over `getCompressibleObjGens`) then the linearized erasure of every
// page dictionary and the root Catalog (QPDFWriter.cc:2141-2161).
// * `route_objstm_containers` = `filterCompressedObjects`
// (QPDF_optimization.cc:340-380) folding each member's obj_users onto its
// container, then `calculateLinearizationData`'s `lc_*` categorization
// (QPDF_linearization.cc:963-1200) applied to the container's union.
// ---------------------------------------------------------------------------
/// Linearization part a generate-mode ObjStm container is routed to, by the
/// union of its members' object users.
///
/// `OpenDocument` is qpdf part 4 (open-document objects, first half), the three
/// `FirstPage*` variants are part 6 (first-page section),
/// `OtherPagePrivate` is part 7, `OtherPageShared` is part 8, and `Rest` is part
/// 9. qpdf checks outlines, open-document objects, and first-page objects in
/// that precedence order; [`route_objstm_containers`] retains it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum ContainerPart {
/// qpdf part 4 — the container holds at least one open-document object
/// (reachable from the catalog's `/OpenAction`, `/AcroForm`,
/// `/ViewerPreferences`, `/PageMode`, `/Threads`, or the trailer's
/// `/Encrypt`). Takes precedence over every page category.
OpenDocument,
/// qpdf part 6 — every container member user is compatible with
/// `lc_first_page_private`.
FirstPagePrivate,
/// qpdf part 6 — the container reaches the first page and also has a
/// document-other, non-first-page, or thumbnail user.
FirstPageShared,
/// qpdf part 6 — an outline container when `/PageMode /UseOutlines`.
FirstPageOutlines,
/// qpdf part 7 — the container's members are private to exactly one
/// non-first page.
OtherPagePrivate,
/// qpdf part 8 — the container's members are shared by two or more
/// non-first pages.
OtherPageShared,
/// qpdf part 9 — the container reaches no page (trailer-only members).
Rest,
}
/// One second-half ObjStm batch paired with qpdf's canonical container route.
///
/// Keeping the route beside the members prevents the writer from reclassifying
/// the container from per-object classic partitions after qpdf's member-user
/// union has already selected its part.
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct RoutedObjStmBatch {
pub(crate) members: Vec<ObjectRef>,
pub(crate) route: ContainerPart,
/// Original ObjStm object number in Preserve mode. Generate mode creates a
/// fresh container after the source objects, so it uses `None`.
pub(crate) source_container_number: Option<u32>,
}
#[allow(clippy::too_many_arguments)]
fn push_routed_objstm_batch(
members: Vec<ObjectRef>,
route: ContainerPart,
source_container_number: Option<u32>,
open_document_batches: &mut Vec<RoutedObjStmBatch>,
part3_private: &mut Vec<RoutedObjStmBatch>,
part3_shared: &mut Vec<RoutedObjStmBatch>,
part3_outlines: &mut Vec<RoutedObjStmBatch>,
part4_private: &mut Vec<RoutedObjStmBatch>,
part4_shared: &mut Vec<RoutedObjStmBatch>,
part4_rest: &mut Vec<RoutedObjStmBatch>,
) {
match route {
ContainerPart::OpenDocument => open_document_batches.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
ContainerPart::FirstPagePrivate => part3_private.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
ContainerPart::FirstPageShared => part3_shared.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
ContainerPart::FirstPageOutlines => part3_outlines.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
ContainerPart::OtherPagePrivate => part4_private.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
ContainerPart::OtherPageShared => part4_shared.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
ContainerPart::Rest => part4_rest.push(RoutedObjStmBatch {
members,
route,
source_container_number,
}),
}
}
impl std::ops::Deref for RoutedObjStmBatch {
type Target = [ObjectRef];
fn deref(&self) -> &Self::Target {
&self.members
}
}
/// Compute the linearized generate-mode ObjStm membership.
///
/// Runs qpdf's `generateObjectStreams` even split
/// ([`get_compressible_objgens`](crate::writer::object_streams::get_compressible_objgens)
/// →
/// [`even_split_into_streams`](crate::writer::object_streams::even_split_into_streams),
/// hard-coded 100 per stream — *not* the planner cap) over the whole document,
/// then erases every page dictionary and the root Catalog from the resulting
/// containers (qpdf's linearized exclusion at QPDFWriter.cc:2141-2161; the
/// `/Pages` tree node and `/Info` dictionary are *not* erased — they stay ObjStm
/// members). Containers are returned in even-split order; each inner vector is
/// one container's surviving members in even-split (DFS) order. A container left
/// empty by the erasure is dropped.
///
/// `assigned` is the set of refs that receive a renumber slot
/// ([`LinearizationPlan::renumber_assigned_refs`]). A live, reachable object that
/// [`get_compressible_objgens`](crate::writer::object_streams::get_compressible_objgens)
/// admits but the linearization plan places in no part — a trailer-only object
/// with no slot — is dropped **before** the even split, so it cannot inflate the
/// split boundary and scatter real members across separate ObjStms. (Dangling /
/// missing refs are already excluded upstream by `get_compressible_objgens`, which
/// qpdf treats as null, so they never reach this retain.) The page dictionaries
/// and root Catalog are in `assigned`, so they still consume split positions and
/// are erased afterwards, exactly as qpdf does.
///
/// # Errors
///
/// Propagates reader errors from the compressible-set traversal or the page-tree
/// walk used to build the erase set.
pub(crate) fn objstm_membership_linearized_with_eligibility<R: Read + Seek>(
pdf: &mut Pdf<R>,
assigned: &BTreeSet<ObjectRef>,
eligibility_override: Option<&[ObjectRef]>,
) -> crate::Result<Vec<Vec<ObjectRef>>> {
// qpdf's DFS already preserves the indirect identity of null-resolving
// references reached from arrays. Do not append `resurrectable_null_refs`
// here: that set remains a planner/all-refs aid, and appending it would give
// array-null objects duplicate ObjStm membership.
let mut eligible = match eligibility_override {
Some(eligible) => eligible.to_vec(),
None => crate::writer::object_streams::get_compressible_objgens(pdf)?,
};
// Drop refs without a renumber slot before the split (see doc above).
eligible.retain(|r| assigned.contains(r));
// A fresh multi-source page-selection target carries qpdf's primary source
// and foreign destination order separately from its target references.
// Apply that provenance before the GLOBAL split, matching the plain
// Generate planner and qpdf's `generateObjectStreams` input sequence.
if pdf.writer_object_order.is_some() {
eligible.sort_unstable_by_key(|object_ref| pdf.writer_object_order_key(*object_ref));
}
let mut streams = crate::writer::object_streams::even_split_into_streams(&eligible);
// qpdf's setup removes every page dictionary and the Catalog after
// membership is selected. Keep that exclusion in the shared writer owner
// used by specialized Preserve so Generate and Preserve cannot drift.
let mut source_containers = vec![None; streams.len()];
crate::writer::object_streams::filter_objstm_batches_for_output(
pdf,
&mut streams,
&mut source_containers,
true,
false,
)?; // cov:ignore: LLVM attributes this covered multiline exclusion terminator to the call setup
Ok(streams)
}
/// Catalog keys qpdf treats as `open_document_keys` in
/// `calculateLinearizationData` (QPDF_linearization.cc:1045-1050): a catalog
/// reference through one of these is `in_open_document`, while a reference
/// through any OTHER catalog key (except `/Outlines`) increments `others`.
/// Used to classify the retained optimization users into open-document and
/// document-other categories from one source of truth.
const OPEN_DOCUMENT_CATALOG_KEYS: [&[u8]; 5] = [
b"ViewerPreferences",
b"PageMode",
b"Threads",
b"OpenAction",
b"AcroForm",
];
fn is_open_document_user(user: &crate::optimization::ObjectUser) -> bool {
match user {
crate::optimization::ObjectUser::TrailerKey(key) => key == b"Encrypt",
crate::optimization::ObjectUser::RootKey(key) => {
OPEN_DOCUMENT_CATALOG_KEYS.contains(&key.as_slice())
}
_ => false,
}
}
fn is_document_other_user(user: &crate::optimization::ObjectUser) -> bool {
match user {
crate::optimization::ObjectUser::TrailerKey(key) => key != b"Encrypt",
crate::optimization::ObjectUser::RootKey(key) => {
key != b"Outlines" && !OPEN_DOCUMENT_CATALOG_KEYS.contains(&key.as_slice())
}
_ => false,
}
}
/// Whether qpdf would place the first page's object in
/// `lc_first_page_private` before generating the linearization parts.
///
/// qpdf classifies the post-ObjStm-folded object-user set in strict priority
/// order (`QPDF_linearization.cc:1118-1128`). The first page must have a page-0
/// user and no root, outline, open-document, later-page, thumbnail, or
/// document-other user. A non-private first page cannot be represented by the
/// linearized part layout, so qpdf raises `stopOnError` rather than pinning it
/// into Part 6.
fn first_page_is_private(
optimization: &crate::optimization::Optimization,
first_page_ref: ObjectRef,
source_container_by_member: &BTreeMap<ObjectRef, ObjectRef>,
) -> bool {
let first_page_ref = canonical_preserve_ref(source_container_by_member, first_page_ref);
let Ok(first_page_gen) = QpdfObjGen::try_from_object_ref(first_page_ref) else {
return false;
};
let users = optimization.raw_users_for(first_page_gen);
let mut has_first_page = false;
let mut has_later_page = false;
let mut has_thumbnail = false;
let mut has_document_other = false;
let mut has_open_document = false;
let mut has_outline = false;
let mut has_root = false;
for user in users.iter() {
match user {
crate::optimization::ObjectUser::Page(page) if *page == 0 => {
has_first_page = true;
}
crate::optimization::ObjectUser::Page(_) => has_later_page = true,
crate::optimization::ObjectUser::Thumbnail(_) => has_thumbnail = true,
crate::optimization::ObjectUser::Root => has_root = true,
user if is_outline_user(user) => has_outline = true,
user if is_open_document_user(user) => has_open_document = true,
user if is_document_other_user(user) => has_document_other = true,
_ => {} // cov:ignore: qpdf ObjectUser variants are fully partitioned by the classifiers above
}
}
has_first_page
&& !has_later_page
&& !has_thumbnail
&& !has_document_other
&& !has_open_document
&& !has_outline
&& !has_root
}
fn has_page_user_objects(optimization: &crate::optimization::Optimization) -> bool {
!optimization
.raw_objects_for(&crate::optimization::ObjectUser::Page(0))
.is_empty()
}
fn qpdf_stop_on_error<R: Read + Seek>(pdf: &Pdf<R>, message: impl AsRef<[u8]>) -> crate::Error {
crate::Error::QpdfExc(crate::QpdfExc::new(
crate::QpdfErrorCode::DamagedPdf,
pdf.input_description(),
b"",
i64::try_from(pdf.source_last_offset()).unwrap_or(i64::MAX),
message,
))
}
/// Return qpdf's Part-9 category and its page secondary key for a plain object
/// or a generated ObjStm container. The category numbers are ordered as qpdf's
/// `calculateLinearizationData` emits them: Pages (`0`), private thumbnails
/// (`1`), shared thumbnails (`2`), outlines (`3`), and remaining `lc_other`
/// (`4`). The `others == 0` gate belongs only to the private-thumbnail arm;
/// qpdf's `thumbs > 1` arm still wins when document-other users are present
/// (QPDF_linearization.cc:1128-1137).
pub(crate) fn part9_category_order_key<'a>(
optimization: &crate::optimization::Optimization,
part9_pages: &BTreeSet<ObjectRef>,
members: impl IntoIterator<Item = &'a ObjectRef>,
) -> (u8, u32) {
let member_refs: Vec<ObjectRef> = members.into_iter().copied().collect();
let users = optimization.users_for_members(member_refs.iter());
let has_outline = users.iter().any(is_outline_user);
let has_document_other = users.iter().any(is_document_other_user);
let thumbnail_pages: BTreeSet<u32> = users
.iter()
.filter_map(|user| match user {
crate::optimization::ObjectUser::Thumbnail(page) => Some(*page),
_ => None,
})
.collect();
if has_outline {
// qpdf categorizes in_outlines before lc_other and all page
// categories; this remains true when a container co-locates outline
// members with other users.
(3, 0)
} else if thumbnail_pages.len() == 1 && !has_document_other {
// qpdf emits private thumbnail sets page by page, then the
// shared-thumbnail set. Use the private page number as the secondary
// key; a category-only tie remains stable.
(1, *thumbnail_pages.first().expect("thumbnail page exists"))
} else if thumbnail_pages.len() > 1 {
// qpdf's `thumbs > 1` arm is not gated by `others == 0`. A
// thumbnail-shared container can therefore also carry a document-other
// member, and still precedes outlines and remaining lc_other.
(2, 0)
} else if member_refs
.iter()
.any(|member| part9_pages.contains(member))
{
// The Pages-tree promotion applies only to qpdf's lc_other category.
// A container with both `/Pages` and shared thumbnails was handled
// above, just as qpdf's `if (lc_other.count(og))` guard skips it.
(0, 0)
} else {
(4, 0)
}
}
/// Returns `true` when the catalog specifies `/PageMode /UseOutlines` AND has
/// an `/Outlines` entry (QPDF_linearization.cc:1031-1043).
///
/// When `true`, outline objects are routed to the first-page section (part6)
/// rather than part9 by [`route_objstm_containers`].
fn outlines_in_first_page_predicate<R: Read + Seek>(pdf: &mut Pdf<R>) -> crate::Result<bool> {
let root_handle = pdf.root_handle()?;
if !root_handle.try_has_key(b"/Outlines")? {
return Ok(false);
}
Ok(root_handle
.try_get_key(b"/PageMode")?
.try_as_name()?
.is_some_and(|name| name == b"UseOutlines"))
}
/// Route each ObjStm container to a linearization part by the union of its
/// members' object users.
///
/// Mirrors qpdf's `filterCompressedObjects` (the container inherits the union of
/// every member's obj_users) followed by the `lc_*` categorization. In qpdf's
/// precedence order: a container holding any outline object is part 6
/// ([`ContainerPart::FirstPageOutlines`]) when `/PageMode /UseOutlines` is set,
/// or part 9 ([`ContainerPart::Rest`]) otherwise; a container holding any
/// open-document object is part 4 ([`ContainerPart::OpenDocument`]).
/// A remaining container holding a first-page object is private only when its
/// union has no non-first-page, document-other, or thumbnail user; otherwise it
/// is shared. Containers without a first-page object route to part 7 / part 8 /
/// part 9 by the number of *distinct non-first* pages their members reach (one →
/// [`ContainerPart::OtherPagePrivate`], two or more →
/// [`ContainerPart::OtherPageShared`], none → [`ContainerPart::Rest`]). The
/// one-page case is part 7 ONLY when the member union has neither a
/// document-level `others` object nor a thumbnail user
/// (QPDF_linearization.cc:1128 gates lc_other_page_private on `others==0` and
/// `thumbs==0`); either signal demotes it to part 9
/// ([`ContainerPart::Rest`]). The two-or-more case is part 8 regardless of
/// `others` or thumbnails (QPDF_linearization.cc:1130).
///
/// The retained routing snapshot comes from [`LinearizationPlan::from_pdf`].
/// This classifier does not resolve objects or read the PDF.
///
/// # Deviation
///
/// **Multiple open-document containers (verified, flpdf-699x):** qpdf assigns
/// container `ObjGen`s sequentially in even-split order, so its
/// `std::set<QPDFObjGen>` (used for `lc_open_document`) iterates them in the
/// same DFS / even-split order that this function preserves. The ordering is
/// therefore byte-identical to qpdf for ≥2 open-document containers; verified
/// with `objstm-lin-openaction-multi-od` (two OD containers whose min-member
/// numbers are non-ascending in DFS order).
///
pub(crate) fn route_objstm_containers(
optimization: &crate::optimization::Optimization,
outlines_in_first_page: bool,
containers: &[Vec<ObjectRef>],
) -> Vec<ContainerPart> {
containers
.iter()
.map(|members| {
let users = optimization.users_for_members(members.iter());
classify_container_users(&users, outlines_in_first_page)
})
.collect()
}
/// Route Preserve containers from qpdf's folded source-container users rather
/// than from member-level users, which no longer exist after
/// `filter_compressed_objects` folds each member onto its source ObjStm.
fn route_preserve_objstm_containers(
optimization: &crate::optimization::Optimization,
outlines_in_first_page: bool,
containers: &[Vec<ObjectRef>],
source_containers: &[Option<ObjectRef>],
) -> Vec<ContainerPart> {
containers
.iter()
.zip(source_containers)
.map(|(_members, source)| {
let source = source.expect("Preserve ObjStm batch must have a source container");
let users: BTreeSet<crate::optimization::ObjectUser> =
optimization.users_for(source).iter().cloned().collect();
classify_container_users(&users, outlines_in_first_page)
})
.collect()
}
fn classify_container_users(
users: &BTreeSet<crate::optimization::ObjectUser>,
outlines_in_first_page: bool,
) -> ContainerPart {
if users.iter().any(is_outline_user) {
return if outlines_in_first_page {
ContainerPart::FirstPageOutlines
} else {
ContainerPart::Rest
};
}
if users.iter().any(is_open_document_user) {
return ContainerPart::OpenDocument;
}
let page_numbers: BTreeSet<u32> = users
.iter()
.filter_map(|user| match user {
crate::optimization::ObjectUser::Page(page_number) => Some(*page_number),
_ => None,
})
.collect();
let has_document_other = users.iter().any(is_document_other_user);
let has_thumbnail = users.iter().any(is_thumbnail_user);
if page_numbers.contains(&0) {
return if page_numbers.iter().any(|&page| page != 0) || has_document_other || has_thumbnail
{
ContainerPart::FirstPageShared
} else {
ContainerPart::FirstPagePrivate
};
}
match page_numbers.len() {
0 => ContainerPart::Rest,
1 if has_document_other || has_thumbnail => ContainerPart::Rest,
1 => ContainerPart::OtherPagePrivate,
_ => ContainerPart::OtherPageShared,
}
}
fn is_outline_user(user: &crate::optimization::ObjectUser) -> bool {
matches!(
user,
crate::optimization::ObjectUser::RootKey(key) if key == b"Outlines"
)
}
fn is_thumbnail_user(user: &crate::optimization::ObjectUser) -> bool {
matches!(user, crate::optimization::ObjectUser::Thumbnail(_))
}
// ---------------------------------------------------------------------------
// Unit tests
// ---------------------------------------------------------------------------
#[cfg(test)]
mod tests {
use super::{
collect_direct_handle_refs, collect_direct_handle_refs_with_context,
collect_direct_handle_refs_with_stream_parameters_context, first_page_is_private,
linearization_content_normalize_refs, LinearizationPlan, RawLinearizationPlan,
};
use crate::acroform_document_helper::AcroFormDocumentHelper;
use crate::object_handle::ObjectHandle;
use crate::optimization::{ObjectUser, Optimization};
use crate::parser::MAX_PARSE_DEPTH;
use crate::qpdf_obj_gen::QpdfObjGen;
use crate::writer::{ObjectStreamMode, WriterOptions};
use crate::{Error, ObjectRef, Pdf};
use flate2::write::ZlibEncoder;
use flate2::Compression;
use std::cell::Cell;
use std::collections::{BTreeMap, BTreeSet};
use std::io::{Cursor, Write};
use std::rc::Rc;
#[test]
fn first_page_private_matches_qpdf_object_user_classification() {
let page = ObjectRef::new(3, 0);
let mut private = Optimization::default();
private.record_for_test(ObjectUser::Page(0), page);
assert!(first_page_is_private(&private, page, &BTreeMap::new()));
for extra_user in [
ObjectUser::Page(1),
ObjectUser::Thumbnail(0),
ObjectUser::TrailerKey(b"Info".to_vec()),
ObjectUser::TrailerKey(b"Encrypt".to_vec()),
ObjectUser::RootKey(b"Outlines".to_vec()),
ObjectUser::RootKey(b"PageMode".to_vec()),
ObjectUser::RootKey(b"Other".to_vec()),
ObjectUser::Root,
] {
let mut shared = Optimization::default();
shared.record_for_test(ObjectUser::Page(0), page);
shared.record_for_test(extra_user, page);
assert!(!first_page_is_private(&shared, page, &BTreeMap::new()));
}
assert!(!first_page_is_private(
&Optimization::default(),
ObjectRef::new(u32::MAX, 0),
&BTreeMap::new()
));
}
#[test]
fn linearization_page_presence_accepts_a_raw_generation_user() {
let mut optimization = Optimization::default();
optimization.record_raw_for_test(ObjectUser::Page(0), QpdfObjGen::new(11, 65_535));
assert!(super::has_page_user_objects(&optimization));
}
#[test]
fn raw_projection_route_is_materialized_at_plan_construction() {
let plan = LinearizationPlan {
raw: RawLinearizationPlan {
projection_gap: true,
..Default::default()
},
..Default::default()
};
assert!(plan.has_raw_projection_gap());
}
#[test]
fn content_normalize_probe_walks_prepared_page_handles_without_snapshot() {
let options = WriterOptions {
content_normalization: true,
..WriterOptions::default()
};
let page = ObjectHandle::dictionary(vec![(
b"/Contents".to_vec(),
ObjectHandle::stream(ObjectHandle::dictionary(Vec::new()), Rc::new(Vec::new())),
)]);
let refs = linearization_content_normalize_refs(&options, &[page], None)
.expect("live page handles should be inspected when no snapshot exists");
assert!(refs.is_empty(), "a direct stream has no indirect identity");
}
#[test]
fn preserve_source_membership_keeps_one_canonical_container_per_group() {
let plan = LinearizationPlan {
preserve_objstm_plan: Some(crate::writer::object_streams::ObjectStreamPlan {
groups: vec![
crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
source: ObjectRef::new(1, 0),
members: vec![ObjectRef::new(2, 0), ObjectRef::new(3, 0)],
},
crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
source: ObjectRef::new(7, 0),
members: vec![ObjectRef::new(8, 0)],
},
crate::writer::object_streams::ObjectStreamGroup::Generated {
source: ObjectRef::new(9, 0),
members: vec![ObjectRef::new(10, 0)],
},
],
removed_refs: BTreeSet::new(),
source_membership_present: true,
}),
..Default::default()
};
assert_eq!(
plan.preserve_source_membership(),
Some(BTreeMap::from([(2, 1), (3, 1), (8, 7)]))
);
}
#[test]
fn preserve_source_membership_keeps_last_duplicate_group() {
let member = ObjectRef::new(2, 0);
let plan = LinearizationPlan {
preserve_objstm_plan: Some(crate::writer::object_streams::ObjectStreamPlan {
groups: vec![
crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
source: ObjectRef::new(1, 0),
members: vec![member],
},
crate::writer::object_streams::ObjectStreamGroup::SourceBacked {
source: ObjectRef::new(7, 0),
members: vec![member],
},
],
removed_refs: BTreeSet::new(),
source_membership_present: true,
}),
..LinearizationPlan::default()
};
assert_eq!(
plan.preserve_source_membership(),
Some(BTreeMap::from([(2, 7)]))
);
}
#[test]
fn preserve_objstm_batches_do_not_rewalk_compressible_objects() {
crate::writer::object_streams::reset_compressible_plan_call_count();
let mut pdf = Pdf::open(Cursor::new(parameter_probe_fixture())).expect("parse fixture");
let options = WriterOptions {
object_streams: ObjectStreamMode::Preserve,
..WriterOptions::default()
};
let plan = LinearizationPlan::from_pdf_with_writer_options(&mut pdf, &options)
.expect("build Preserve linearization plan");
let setup_calls = crate::writer::object_streams::compressible_plan_call_count();
let _ = plan
.objstm_batches(&mut pdf, &super::PlannerConfig::default())
.expect("build Preserve ObjStm batches");
assert_eq!(
crate::writer::object_streams::compressible_plan_call_count(),
setup_calls,
"Preserve batching must reuse setup ownership instead of walking compressible objects"
);
}
fn flate(data: &[u8]) -> Vec<u8> {
let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
encoder.write_all(data).expect("compress fixture stream");
encoder.finish().expect("finish fixture stream")
}
fn stream_object(number: u32, dictionary: &str, data: &[u8]) -> Vec<u8> {
let mut object = format!(
"{number} 0 obj\n<< {dictionary} /Length {} >>\nstream\n",
data.len()
)
.into_bytes();
object.extend_from_slice(data);
object.extend_from_slice(b"\nendstream\nendobj\n");
object
}
fn parameter_probe_fixture() -> Vec<u8> {
let page_content_indirect_filter = flate(b"q Q\n");
let page_content_direct_filter = flate(b"q Q\n");
let existing_appearance = flate(b"/Tx BMC\nEMC\n");
// The inline `/Resources` and ancestor `/ColorSpace` arrays exercise
// the generic array-edge context used by the qpdf-shaped closure walk.
let objects = vec![
b"1 0 obj\n<< /Type /Catalog /Pages 2 0 R /AcroForm 6 0 R >>\nendobj\n"
.to_vec(),
b"2 0 obj\n<< /Type /Pages /Count 1 /Kids [3 0 R] /ColorSpace [10 0 R] >>\nendobj\n".to_vec(),
b"3 0 obj\n<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /Resources << /ProcSet [10 0 R] >> /Contents [4 0 R 12 0 R] /Annots [5 0 R] >>\nendobj\n".to_vec(),
stream_object(4, "/Filter 9 0 R", &page_content_indirect_filter),
b"5 0 obj\n<< /Type /Annot /Subtype /Widget /FT /Tx /T (name) /V (Hello) /DA (/Helv 12 Tf 0 g) /Rect [10 10 200 30] /P 3 0 R /AP << /N 8 0 R >> >>\nendobj\n".to_vec(),
b"6 0 obj\n<< /Fields [5 0 R] /NeedAppearances true /DR << >> /DA (/Helv 12 Tf 0 g) >>\nendobj\n".to_vec(),
b"7 0 obj\nnull\nendobj\n".to_vec(),
stream_object(
8,
"/Type /XObject /Subtype /Form /BBox [0 0 190 20] /Resources << >> /Filter 9 0 R",
&existing_appearance,
),
b"9 0 obj\n/FlateDecode\nendobj\n".to_vec(),
b"10 0 obj\n<< /Type /ExtGState >>\nendobj\n".to_vec(),
b"11 0 obj\nnull\nendobj\n".to_vec(),
stream_object(12, "/Filter /FlateDecode", &page_content_direct_filter),
];
let mut pdf = b"%PDF-1.7\n".to_vec();
let object_count = objects.len();
let mut offsets = Vec::with_capacity(object_count);
for object in objects {
offsets.push(pdf.len());
pdf.extend_from_slice(&object);
}
let xref = pdf.len();
let _ = writeln!(&mut pdf, "xref\n0 {}", object_count + 1);
pdf.extend_from_slice(b"0000000000 65535 f \n");
for offset in offsets {
let _ = writeln!(&mut pdf, "{offset:010} 00000 n ");
}
let _ = writeln!(
&mut pdf,
"trailer\n<< /Size {} /Root 1 0 R >>\nstartxref\n{xref}\n%%EOF",
object_count + 1
);
pdf
}
struct PassThroughTokenFilter;
impl crate::token_filter::TokenFilter for PassThroughTokenFilter {
fn handle_token(
&mut self,
token: &crate::tokenizer::Token,
output: &mut crate::token_filter::TokenFilterOutput<'_>,
) -> crate::pipeline::PipelineResult<()> {
output.write_token(token)
}
}
#[test]
fn qpdf_linearization_probe_consumes_modified_and_parameterized_streams() {
let mut pdf = Pdf::open(Cursor::new(parameter_probe_fixture())).expect("parse fixture");
AcroFormDocumentHelper::new(&mut pdf)
.expect("AcroForm")
.generate_appearances_if_needed()
.expect("generate appearance");
let options = WriterOptions {
object_streams: ObjectStreamMode::Disable,
..WriterOptions::default()
};
let plan = LinearizationPlan::from_pdf_with_writer_options(&mut pdf, &options)
.expect("build linearization plan");
assert_eq!(plan.page_hints.len(), 1);
assert!(!plan.part2_objects.is_empty());
assert!(
plan.all_assigned_refs()
.contains(&crate::ObjectRef::new(10, 0)),
"inline resource and ancestor array references must reach the plan"
);
}
#[test]
fn qpdf_linearization_parameter_probe_runs_once_before_raw_retry() {
let mut pdf = Pdf::open(Cursor::new(parameter_probe_fixture())).expect("parse fixture");
let stream = pdf.get_object_handle(crate::ObjectRef::new(4, 0));
stream.try_is_scalar().expect("resolve page content");
let token = crate::tokenizer::Token::new(crate::tokenizer::TokenType::Word, b"q".to_vec());
let mut filter = PassThroughTokenFilter;
let mut output = crate::token_filter::TokenFilterOutput::new(None);
crate::token_filter::TokenFilter::handle_token(&mut filter, &token, &mut output)
.expect("pass-through filter token");
let provider_calls = Rc::new(Cell::new(0));
let provider_calls_for_callback = Rc::clone(&provider_calls);
stream
.replace_stream_data_with_retry_callback(
move |_pipeline, _suppress_warnings, _will_retry| {
provider_calls_for_callback.set(provider_calls_for_callback.get() + 1);
Ok(false)
},
None,
None,
)
.expect("install stateful stream provider");
stream
.add_token_filter(Rc::new(std::cell::RefCell::new(PassThroughTokenFilter)))
.expect("register token filter");
let options = WriterOptions {
object_streams: ObjectStreamMode::Disable,
..WriterOptions::default()
};
LinearizationPlan::from_pdf_with_writer_options(&mut pdf, &options)
.expect("build linearization plan");
assert_eq!(
provider_calls.get(),
2,
"one qpdf parameter probe may retry once with raw data, but the optimization callback must not probe the same stream again"
);
}
#[test]
fn linearized_writer_pipes_provider_once_for_probe_and_each_output_pass() {
let mut pdf = Pdf::open(Cursor::new(parameter_probe_fixture())).expect("parse fixture");
let stream = pdf.get_object_handle(ObjectRef::new(4, 0));
stream.try_is_scalar().expect("resolve page content");
let provider_calls = Rc::new(Cell::new(0));
let provider_calls_for_callback = Rc::clone(&provider_calls);
let compressed_content = flate(b"q Q\n");
stream
.replace_stream_data_with_retry_callback(
move |pipeline, _suppress_warnings, _will_retry| {
provider_calls_for_callback.set(provider_calls_for_callback.get() + 1);
pipeline.write(&compressed_content)?;
pipeline.finish()?;
Ok(true)
},
None,
None,
)
.expect("install successful retry-aware stream provider");
let mut writer = crate::writer::PdfWriter::new(&mut pdf);
writer.set_object_stream_mode(ObjectStreamMode::Disable);
writer.set_compress_streams(true);
writer.set_linearization(true);
writer.set_output_memory().expect("install output memory");
writer.write().expect("write linearized output");
let output = writer.get_buffer().expect("read linearized output");
assert!(!output.is_empty(), "linearized output must be emitted");
assert_eq!(
provider_calls.get(),
3,
"qpdf probes once during optimization and pipes once in each of its two output passes"
);
}
#[test]
fn stream_parameter_probe_uses_a_live_dictionary_lookup_with_warning_fallback() {
let source = include_str!("plan.rs").replace("\r\n", "\n");
let start = source
.find("fn stream_has_indirect_parameter_edge")
.expect("stream parameter probe");
let body = &source[start
..source[start..]
.find("\nfn stream_parameters_removed_for_linearization")
.expect("stream parameter probe end")
+ start];
assert!(
body.contains("with_value"),
"the ordinary stream dictionary probe must use a live map lookup"
);
assert!(
body.contains("try_get_key"),
"the malformed non-dictionary fallback must retain qpdf warnings"
);
}
#[test]
fn stream_parameter_probe_preserves_present_missing_and_malformed_shapes() -> crate::Result<()>
{
let empty_stream =
ObjectHandle::stream(ObjectHandle::dictionary(Vec::new()), Rc::new(Vec::new()));
assert!(!super::stream_has_indirect_parameter_edge(&empty_stream)?);
let mut pdf = Pdf::empty()?;
let filter_child = pdf.make_indirect_object_handle(ObjectHandle::integer(7))?;
let stream_with_filter = ObjectHandle::stream(
ObjectHandle::dictionary(vec![(b"/Filter".to_vec(), filter_child)]),
Rc::new(Vec::new()),
);
assert!(super::stream_has_indirect_parameter_edge(
&stream_with_filter
)?); // cov:ignore: the covered boolean probe is attributed to its multiline call opening by LLVM.
let malformed_stream = ObjectHandle::stream(ObjectHandle::integer(7), Rc::new(Vec::new()));
let error = super::stream_has_indirect_parameter_edge(&malformed_stream)
.expect_err("a non-dictionary stream dictionary must retain qpdf's warning error");
assert!(error
.to_string()
.contains("operation for dictionary attempted on object of type integer"));
Ok(())
}
#[test]
fn direct_child_plan_walk_uses_live_container_cursors() {
let source = include_str!("plan.rs");
let start = source
.find("fn collect_direct_handle_children_with_stream_parameters")
.expect("direct child plan walker");
let body = &source[start
..source[start..]
.find("\nfn handle_has_stream_parameter_skip")
.expect("direct child plan walker end")
+ start];
assert!(
body.contains("try_array_items"),
"linearization plan must walk arrays through the live cursor"
);
assert!(
body.contains("next_dictionary_entry_for_live_walk"),
"linearization plan must walk dictionaries through the live cursor"
);
assert!(
!body.contains("try_as_array") && !body.contains("try_as_dictionary"),
"linearization plan must not clone complete container edges"
);
}
#[test]
fn indirect_stream_dictionary_children_are_reached_through_the_live_walk() {
use crate::object_handle::identity_tests::resolver_bearing_handle;
use crate::object_handle::ObjectValue;
// qpdf reads a stream's dictionary through `getDictAsMap`, whose
// `asDictionary()` dereferences (`QPDFObjectHandle.cc:1012-1020`,
// `:327-330`). A stream built with an indirect dictionary handle must
// therefore still expose its children to the plan walk.
let (stream_dict, _resolver) = resolver_bearing_handle(ObjectValue::Dictionary(
[
(b"/Kid".to_vec(), ObjectHandle::integer(42)),
(b"/Length".to_vec(), ObjectHandle::integer(0)),
]
.into_iter()
.collect(),
));
assert!(
!stream_dict.is_resolved(),
"the dictionary handle starts unresolved"
);
let stream = ObjectHandle::stream(stream_dict, std::rc::Rc::new(Vec::new()));
let mut visited = Vec::new();
super::collect_direct_handle_children(
&stream,
0,
false,
&mut |child, _depth, _in_array| {
visited.push(child.as_integer());
Ok(())
},
)
.expect("an indirect stream dictionary resolves during the walk");
// `/Length` is skipped like qpdf's writer does; `/Kid` must survive.
assert_eq!(visited, vec![Some(42)]);
}
#[test]
fn direct_reference_walkers_reject_depth_beyond_parser_limit() {
let handle = ObjectHandle::null();
let mut refs = Vec::new();
let error = collect_direct_handle_refs(&handle, MAX_PARSE_DEPTH + 1, &mut refs)
.expect_err("the direct reference walk has a parser-depth guard");
assert!(error.to_string().contains("maximum of 500"));
let mut contextual = Vec::new();
let error = collect_direct_handle_refs_with_context(
&handle,
MAX_PARSE_DEPTH + 1,
false,
&mut contextual,
)
.expect_err("the contextual reference walk has a parser-depth guard");
assert!(error.to_string().contains("maximum of 500"));
let mut stream_contextual = Vec::new();
let error = collect_direct_handle_refs_with_stream_parameters_context(
&handle,
MAX_PARSE_DEPTH + 1,
false,
&mut stream_contextual,
&BTreeSet::new(),
)
.expect_err("the stream-policy reference walk has a parser-depth guard");
assert!(error.to_string().contains("maximum of 500"));
}
#[test]
fn page_tree_classification_propagates_resolution_errors() {
let unresolved = ObjectHandle::new_indirect_unresolved(ObjectRef::new(91, 0), -1);
let error = super::is_page_tree_handle(&unresolved)
.expect_err("page-tree classification must propagate resolution errors");
assert!(matches!(
error,
Error::Internal(message) if message == "object 91 0 belongs to a dropped PDF"
));
}
#[test]
fn merge_writer_order_missing_ref_uses_fresh_fallback() {
let plan = LinearizationPlan {
writer_object_order: Some(BTreeMap::new()),
..Default::default()
};
let object_ref = ObjectRef::new(91, 0);
assert_eq!(
plan.writer_object_order_key(object_ref),
crate::pdf::WriterObjectOrderKey::fresh(object_ref)
);
}
}