use crate::object::MAX_INLINE_DEPTH;
use crate::{Object, ObjectRef, Pdf, Result};
use std::collections::{BTreeSet, VecDeque};
use std::io::{Read, Seek};
pub fn page_object_closure<R: Read + Seek>(
pdf: &mut Pdf<R>,
page_ref: ObjectRef,
) -> Result<BTreeSet<ObjectRef>> {
let mut visited: BTreeSet<ObjectRef> = BTreeSet::new();
extend_page_object_closure(pdf, page_ref, &mut visited)?;
Ok(visited)
}
pub(crate) fn extend_page_object_closure<R: Read + Seek>(
pdf: &mut Pdf<R>,
page_ref: ObjectRef,
visited: &mut BTreeSet<ObjectRef>,
) -> Result<()> {
let mut queue: VecDeque<ObjectRef> = VecDeque::new();
visited.insert(page_ref);
queue.push_back(page_ref);
extend_closure_from_queue(pdf, queue, Some(page_ref), visited)
}
pub(crate) fn extend_object_closure<R: Read + Seek>(
pdf: &mut Pdf<R>,
root: &Object,
visited: &mut BTreeSet<ObjectRef>,
) -> Result<()> {
let mut refs = Vec::new();
collect_refs_in_object(root, 0, &mut refs)?;
let mut queue = VecDeque::new();
for reference in refs {
if visited.insert(reference) {
queue.push_back(reference);
}
}
extend_closure_from_queue(pdf, queue, None, visited)
}
fn extend_closure_from_queue<R: Read + Seek>(
pdf: &mut Pdf<R>,
mut queue: VecDeque<ObjectRef>,
top_page: Option<ObjectRef>,
visited: &mut BTreeSet<ObjectRef>,
) -> Result<()> {
let mut refs_found = Vec::new();
while let Some(current_ref) = queue.pop_front() {
let obj = pdf.resolve_borrowed(current_ref)?;
if Some(current_ref) != top_page {
if let Object::Dictionary(dict) = obj {
let boundary = dict
.get("Type")
.and_then(Object::as_name)
.is_some_and(|name| name == b"Page" || name == b"Catalog");
if boundary {
continue;
}
}
}
collect_refs_in_object(obj, 0, &mut refs_found)?;
for r in refs_found.drain(..) {
if visited.insert(r) {
queue.push_back(r);
}
}
}
Ok(())
}
fn collect_refs_in_object(obj: &Object, depth: usize, out: &mut Vec<ObjectRef>) -> Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(crate::Error::Unsupported(format!(
"page closure: inline object nesting exceeds maximum of {MAX_INLINE_DEPTH}"
)));
}
match obj {
Object::Reference(r) => out.push(*r),
Object::Array(items) => {
for item in items {
collect_refs_in_object(item, depth + 1, out)?;
}
}
Object::Dictionary(dict) => {
let is_pages_node = dict
.get("Type")
.and_then(|o| o.as_name())
.map(|n| n == b"Pages")
.unwrap_or(false);
for (key, value) in dict.iter() {
if is_pages_node && key == b"Kids" {
continue;
}
collect_refs_in_object(value, depth + 1, out)?;
}
}
Object::Stream(stream) => {
for (_key, value) in stream.dict.iter() {
collect_refs_in_object(value, depth + 1, out)?;
}
}
Object::Null
| Object::Boolean(_)
| Object::Integer(_)
| Object::Real(_)
| Object::RealLiteral { .. }
| Object::Name(_)
| Object::String(_) => {}
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::object::MAX_INLINE_DEPTH;
use std::collections::BTreeMap;
fn build_pdf(objects: &[(u32, &str)], root: u32) -> Vec<u8> {
let mut out: Vec<u8> = b"%PDF-1.7\n".to_vec();
let mut offsets: BTreeMap<u32, u64> = BTreeMap::new();
let max = objects.iter().map(|(n, _)| *n).max().unwrap_or(0);
for (n, body) in objects {
offsets.insert(*n, out.len() as u64);
out.extend_from_slice(format!("{n} 0 obj\n{body}\nendobj\n").as_bytes());
}
let xref_start = out.len() as u64;
let size = max + 1;
out.extend_from_slice(format!("xref\n0 {size}\n").as_bytes());
out.extend_from_slice(b"0000000000 65535 f \n");
for n in 1..=max {
match offsets.get(&n) {
Some(off) => out.extend_from_slice(format!("{off:010} 00000 n \n").as_bytes()),
None => out.extend_from_slice(b"0000000000 65535 f \n"),
}
}
out.extend_from_slice(
format!(
"trailer\n<< /Size {size} /Root {root} 0 R >>\nstartxref\n{xref_start}\n%%EOF\n"
)
.as_bytes(),
);
out
}
#[test]
fn extend_force_traverses_a_start_page_already_seen_as_a_sibling() {
let bytes = build_pdf(
&[
(1, "<< /Type /Catalog /Pages 2 0 R >>"),
(2, "<< /Type /Pages /Kids [3 0 R 4 0 R] /Count 2 >>"),
(3, "<< /Type /Page /Parent 2 0 R /Annots [5 0 R] >>"),
(4, "<< /Type /Page /Parent 2 0 R /Resources 7 0 R >>"),
(5, "<< /Subtype /Link /Dest [4 0 R /Fit] >>"),
(7, "<< /Font << /F1 8 0 R >> >>"),
(8, "<< /Type /Font /Subtype /Type1 /BaseFont /Helvetica >>"),
],
1,
);
let mut pdf = Pdf::open_mem_owned(bytes).unwrap();
let p1 = ObjectRef::new(3, 0);
let p2 = ObjectRef::new(4, 0);
let mut shared: BTreeSet<ObjectRef> = BTreeSet::new();
extend_page_object_closure(&mut pdf, p1, &mut shared).unwrap();
assert!(shared.contains(&p2), "p1's walk reaches p2's ref");
assert!(
!shared.contains(&ObjectRef::new(7, 0)),
"p2's exclusive resource is not collected by p1's walk (Page guard stops at p2)"
);
extend_page_object_closure(&mut pdf, p2, &mut shared).unwrap();
assert!(
shared.contains(&ObjectRef::new(7, 0)),
"p2's exclusive /Resources must be collected when p2 is its own start"
);
assert!(
shared.contains(&ObjectRef::new(8, 0)),
"the font under p2's exclusive /Resources must be collected too"
);
}
#[test]
fn shared_union_equals_independent_union() {
let bytes = build_pdf(
&[
(1, "<< /Type /Catalog /Pages 2 0 R >>"),
(2, "<< /Type /Pages /Kids [3 0 R 4 0 R] /Count 2 >>"),
(
3,
"<< /Type /Page /Parent 2 0 R /Annots [5 0 R] /Resources 6 0 R >>",
),
(4, "<< /Type /Page /Parent 2 0 R /Resources 7 0 R >>"),
(5, "<< /Subtype /Link /Dest [4 0 R /Fit] >>"),
(6, "<< /Font << /F1 8 0 R >> >>"),
(7, "<< /Font << /F1 8 0 R >> >>"),
(8, "<< /Type /Font /Subtype /Type1 /BaseFont /Helvetica >>"),
],
1,
);
let mut pdf = Pdf::open_mem_owned(bytes).unwrap();
let p1 = ObjectRef::new(3, 0);
let p2 = ObjectRef::new(4, 0);
let independent: BTreeSet<ObjectRef> = {
let mut u = page_object_closure(&mut pdf, p1).unwrap();
u.extend(page_object_closure(&mut pdf, p2).unwrap());
u
};
let mut shared: BTreeSet<ObjectRef> = BTreeSet::new();
extend_page_object_closure(&mut pdf, p1, &mut shared).unwrap();
extend_page_object_closure(&mut pdf, p2, &mut shared).unwrap();
assert_eq!(shared, independent);
}
#[test]
fn direct_root_follows_long_indirect_array_chain_but_stops_at_page() {
let mut owned: Vec<(u32, String)> = vec![
(1, "<< /Type /Catalog /Pages 2 0 R >>".into()),
(2, "<< /Type /Pages /Kids [3 0 R] /Count 1 >>".into()),
(3, "<< /Type /Page /Parent 2 0 R /Contents 90 0 R >>".into()),
(90, "<< /Length 0 >>\nstream\n\nendstream".into()),
];
for number in 10..80 {
owned.push((number, format!("[{} 0 R]", number + 1)));
}
owned.push((80, "[3 0 R]".into()));
let borrowed: Vec<(u32, &str)> = owned
.iter()
.map(|(number, body)| (*number, body.as_str()))
.collect();
let mut pdf = Pdf::open_mem_owned(build_pdf(&borrowed, 1)).unwrap();
let mut closure = BTreeSet::new();
extend_object_closure(
&mut pdf,
&Object::Reference(ObjectRef::new(10, 0)),
&mut closure,
)
.unwrap();
assert!(closure.contains(&ObjectRef::new(3, 0)));
assert!(!closure.contains(&ObjectRef::new(90, 0)));
}
fn nested_arrays(depth: usize) -> Object {
let mut o = Object::Null;
for _ in 0..depth {
o = Object::Array(vec![o]);
}
o
}
#[test]
fn collect_refs_in_object_errors_on_excessive_nesting() {
let mut out = Vec::new();
let err = collect_refs_in_object(&nested_arrays(MAX_INLINE_DEPTH + 5), 0, &mut out);
assert!(matches!(err, Err(crate::Error::Unsupported(_))));
}
#[test]
fn collect_refs_in_object_accepts_nesting_up_to_the_limit() {
let mut out = Vec::new();
let leaf = Object::Array(vec![Object::Reference(ObjectRef::new(7, 0))]);
let mut o = leaf;
for _ in 0..(MAX_INLINE_DEPTH - 1) {
o = Object::Array(vec![o]);
}
collect_refs_in_object(&o, 0, &mut out).unwrap();
assert_eq!(out, vec![ObjectRef::new(7, 0)]);
}
#[test]
fn collect_refs_in_object_rejects_one_past_the_limit() {
let mut out = Vec::new();
let err = collect_refs_in_object(&nested_arrays(MAX_INLINE_DEPTH + 1), 0, &mut out);
assert!(matches!(err, Err(crate::Error::Unsupported(_))));
}
}