use crate::object_handle::ObjectHandle;
use crate::pages::tree_rebuild::RebuildResult;
use crate::{Error, ObjectRef, Pdf, Result};
use std::collections::{BTreeMap, BTreeSet};
use std::io::{Read, Seek};
pub const DEFAULT_MAX_STRUCT_TREE_DEPTH: usize = 100;
#[derive(Default)]
struct WalkState {
visited: BTreeSet<ObjectRef>,
objr_obj_targets: Vec<ObjectRef>,
}
fn child_if_present(parent: &ObjectHandle, key: &[u8]) -> Result<Option<ObjectHandle>> {
if parent.try_has_key(key)? {
Ok(Some(parent.try_get_key(key)?))
} else {
Ok(None)
}
}
fn raw_child(parent: &ObjectHandle, key: &[u8]) -> Result<Option<ObjectHandle>> {
Ok(parent
.try_as_dictionary()?
.and_then(|entries| entries.get(key).cloned()))
}
pub fn drop_struct_elem_dangling_pg<R: Read + Seek>(
pdf: &mut Pdf<R>,
result: &RebuildResult,
) -> Result<Vec<ObjectRef>> {
drop_struct_elem_dangling_pg_with_max_depth(pdf, result, DEFAULT_MAX_STRUCT_TREE_DEPTH)
}
pub fn drop_struct_elem_dangling_pg_with_max_depth<R: Read + Seek>(
pdf: &mut Pdf<R>,
result: &RebuildResult,
max_depth: usize,
) -> Result<Vec<ObjectRef>> {
let surviving: BTreeMap<ObjectRef, ObjectRef> = result
.ref_map
.iter()
.filter_map(|(&old, new_refs)| new_refs.first().map(|&new| (old, new)))
.collect();
let removed_pages = &result.removed_pages;
let mut state = WalkState::default();
let catalog_ref = match pdf.root_ref() {
Some(r) => r,
None => return Ok(Vec::new()), };
let catalog = pdf.get_object_handle(catalog_ref);
catalog.try_dereference()?;
if !catalog.try_is_dictionary()? {
return Ok(state.objr_obj_targets);
}
let Some(root) = child_if_present(&catalog, b"/StructTreeRoot")? else {
return Ok(state.objr_obj_targets);
};
if !root.try_is_dictionary()? {
return Ok(state.objr_obj_targets);
}
if let Some(root_ref) = root.object_ref() {
state.visited.insert(root_ref);
}
if let Some(k) = child_if_present(&root, b"/K")? {
walk_kids(pdf, &k, &surviving, removed_pages, 0, max_depth, &mut state)?;
}
Ok(state.objr_obj_targets)
}
fn walk_kids<R: Read + Seek>(
pdf: &mut Pdf<R>,
k: &ObjectHandle,
surviving: &BTreeMap<ObjectRef, ObjectRef>,
removed_pages: &BTreeSet<ObjectRef>,
depth: usize,
max_depth: usize,
state: &mut WalkState,
) -> Result<()> {
if depth >= max_depth {
return Err(Error::Unsupported(format!(
"structure tree depth exceeds maximum of {max_depth}"
)));
}
if let Some(kid_ref) = k.object_ref() {
if !state.visited.insert(kid_ref) {
return Ok(());
}
}
if let Some(items) = k.try_as_array()? {
for item in items {
walk_kids(
pdf,
&item,
surviving,
removed_pages,
depth,
max_depth,
state,
)?;
}
return Ok(());
}
if k.try_is_dictionary()? {
process_elem_dict(pdf, k, surviving, removed_pages, depth, max_depth, state)?;
}
Ok(())
}
fn process_elem_dict<R: Read + Seek>(
pdf: &mut Pdf<R>,
dict: &ObjectHandle,
surviving: &BTreeMap<ObjectRef, ObjectRef>,
removed_pages: &BTreeSet<ObjectRef>,
depth: usize,
max_depth: usize,
state: &mut WalkState,
) -> Result<()> {
if let Some(pg) = raw_child(dict, b"/Pg")? {
if let Some(pg_ref) = pg.object_ref() {
match surviving.get(&pg_ref) {
Some(&new) if new != pg_ref => {
dict.replace_key(b"/Pg", pdf.get_object_handle(new))?;
}
None if removed_pages.contains(&pg_ref) => {
dict.remove_key(b"/Pg");
}
_ => {}
}
}
}
if let Some(obj) = raw_child(dict, b"/Obj")? {
if is_objr(dict)? {
if let Some(obj_ref) = obj.object_ref() {
state.objr_obj_targets.push(obj_ref);
}
}
}
if let Some(k) = raw_child(dict, b"/K")? {
if !is_mcr_or_objr(dict)? {
walk_kids(
pdf,
&k,
surviving,
removed_pages,
depth + 1,
max_depth,
state,
)?;
}
}
Ok(())
}
fn is_mcr_or_objr(dict: &ObjectHandle) -> Result<bool> {
let Some(type_handle) = raw_child(dict, b"/Type")? else {
return Ok(false);
};
Ok(matches!(
type_handle.try_as_name()?.as_deref(),
Some(b"MCR" | b"OBJR")
))
}
fn is_objr(dict: &ObjectHandle) -> Result<bool> {
let Some(type_handle) = raw_child(dict, b"/Type")? else {
return Ok(false);
};
Ok(matches!(
type_handle.try_as_name()?.as_deref(),
Some(b"OBJR")
))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{ObjectHandle, Pdf};
use std::collections::BTreeMap;
use std::io::Cursor;
fn build_pdf(objs: &BTreeMap<u32, String>) -> Vec<u8> {
build_pdf_inner(objs, true)
}
fn build_pdf_inner(objs: &BTreeMap<u32, String>, with_root: bool) -> Vec<u8> {
let mut raw: Vec<u8> = b"%PDF-1.5\n".to_vec();
let mut offs: BTreeMap<u32, usize> = BTreeMap::new();
for (n, body) in objs {
offs.insert(*n, raw.len());
raw.extend_from_slice(format!("{n} 0 obj\n{body}\nendobj\n").as_bytes());
}
let max_num = *objs.keys().max().unwrap();
let xref_pos = raw.len();
raw.extend_from_slice(format!("xref\n0 {}\n0000000000 65535 f \n", max_num + 1).as_bytes());
for i in 1..=max_num {
if let Some(&off) = offs.get(&i) {
raw.extend_from_slice(format!("{off:010} 00000 n \n").as_bytes());
} else {
raw.extend_from_slice(b"0000000000 65535 f \n");
}
}
let root = if with_root { " /Root 1 0 R" } else { "" };
raw.extend_from_slice(
format!(
"trailer\n<< /Size {}{root} >>\nstartxref\n{xref_pos}\n%%EOF\n",
max_num + 1
)
.as_bytes(),
);
raw
}
fn base_objs() -> BTreeMap<u32, String> {
let mut objs: BTreeMap<u32, String> = BTreeMap::new();
objs.insert(
1,
"<< /Type /Catalog /Pages 2 0 R /StructTreeRoot 10 0 R >>".into(),
);
objs.insert(
2,
"<< /Type /Pages /Kids [3 0 R 4 0 R 5 0 R] /Count 3 >>".into(),
);
for n in 3..=5 {
objs.insert(
n,
"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>".into(),
);
}
objs.insert(10, "<< /Type /StructTreeRoot /K 20 0 R >>".into());
objs
}
fn open(objs: &BTreeMap<u32, String>) -> Pdf<Cursor<Vec<u8>>> {
Pdf::open(Cursor::new(build_pdf(objs))).expect("open fixture")
}
fn keep_3_and_5() -> RebuildResult {
let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
ref_map.insert(ObjectRef::new(3, 0), vec![ObjectRef::new(3, 0)]);
ref_map.insert(ObjectRef::new(5, 0), vec![ObjectRef::new(5, 0)]);
RebuildResult {
new_kids: vec![ObjectRef::new(3, 0), ObjectRef::new(5, 0)],
ref_map,
removed_pages: [ObjectRef::new(4, 0)].into_iter().collect(),
}
}
fn elem_dict(pdf: &mut Pdf<Cursor<Vec<u8>>>, num: u32) -> ObjectHandle {
let elem = pdf.get_object_handle(ObjectRef::new(num, 0));
elem.try_is_scalar().expect("resolve elem");
assert!(
elem.as_dictionary().is_some(),
"object {num} is not a dictionary"
);
elem
}
#[test]
fn surviving_pg_remapped_to_new_ref() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /P /P 10 0 R /Pg 3 0 R >>".into(),
);
let mut pdf = open(&objs);
let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
ref_map.insert(ObjectRef::new(3, 0), vec![ObjectRef::new(7, 0)]);
let result = RebuildResult {
new_kids: vec![ObjectRef::new(7, 0)],
ref_map,
..Default::default()
};
drop_struct_elem_dangling_pg(&mut pdf, &result).expect("pg drop");
let elem = elem_dict(&mut pdf, 20);
assert!(
elem.try_get_key(b"/Pg").unwrap().object_ref() == Some(ObjectRef::new(7, 0)),
"surviving /Pg must be remapped to the new ref"
);
}
#[test]
fn mcr_and_objr_dangling_pg_dropped() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /P /P 10 0 R \
/K [ << /Type /MCR /Pg 4 0 R /MCID 0 >> 21 0 R ] >>"
.into(),
);
objs.insert(21, "<< /Type /OBJR /Pg 4 0 R /Obj 5 0 R >>".into());
let mut pdf = open(&objs);
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("pg drop");
assert!(
targets.contains(&ObjectRef::new(5, 0)),
"OBJR /Obj target (object 5) must be collected, got {targets:?}"
);
let elem = elem_dict(&mut pdf, 20);
let kids = elem.try_get_key(b"/K").unwrap().as_array().expect("kids");
let mcr = kids[0].clone();
assert!(
mcr.as_dictionary().is_some(),
"inline MCR must be a dictionary"
);
assert!(
!mcr.try_has_key(b"/Pg").unwrap(),
"MCR dangling /Pg must be dropped"
);
let objr = elem_dict(&mut pdf, 21);
assert!(
!objr.try_has_key(b"/Pg").unwrap(),
"OBJR dangling /Pg must be dropped"
);
assert!(
objr.try_get_key(b"/Obj").unwrap().object_ref() == Some(ObjectRef::new(5, 0)),
"OBJR /Obj must be kept"
);
}
#[test]
fn non_objr_obj_key_not_collected() {
let mut objs = base_objs();
objs.insert(20, "<< /Type /StructElem /S /P /Obj 5 0 R >>".into());
let mut pdf = open(&objs);
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("ok");
assert!(
!targets.contains(&ObjectRef::new(5, 0)),
"a non-OBJR /Obj key must not be collected, got {targets:?}"
);
}
#[test]
fn objr_with_indirect_type_obj_collected() {
let mut objs = base_objs();
objs.insert(20, "<< /Type /StructElem /S /Document /K 21 0 R >>".into());
objs.insert(21, "<< /Type 22 0 R /Obj 5 0 R >>".into());
objs.insert(22, "/OBJR".into());
let mut pdf = open(&objs);
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("ok");
assert!(
targets.contains(&ObjectRef::new(5, 0)),
"an OBJR with an indirect /Type must collect its /Obj, got {targets:?}"
);
}
#[test]
fn typeless_obj_key_not_collected() {
let mut objs = base_objs();
objs.insert(20, "<< /S /P /Obj 5 0 R /K 21 0 R >>".into());
objs.insert(21, "7".into());
let mut pdf = open(&objs);
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("ok");
assert!(
!targets.contains(&ObjectRef::new(5, 0)),
"a /Obj key on a dictionary with no /Type must not be collected, got {targets:?}"
);
}
#[test]
fn mcr_and_objr_surviving_pg_remapped() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /P /P 10 0 R \
/K [ << /Type /MCR /Pg 3 0 R /MCID 0 >> 21 0 R ] >>"
.into(),
);
objs.insert(21, "<< /Type /OBJR /Pg 3 0 R /Obj 5 0 R >>".into());
let mut pdf = open(&objs);
let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
ref_map.insert(ObjectRef::new(3, 0), vec![ObjectRef::new(7, 0)]);
ref_map.insert(ObjectRef::new(5, 0), vec![ObjectRef::new(5, 0)]);
let result = RebuildResult {
new_kids: vec![ObjectRef::new(7, 0), ObjectRef::new(5, 0)],
ref_map,
..Default::default()
};
drop_struct_elem_dangling_pg(&mut pdf, &result).expect("pg remap");
let elem = elem_dict(&mut pdf, 20);
let kids = elem.try_get_key(b"/K").unwrap().as_array().expect("kids");
let mcr = kids[0].clone();
assert!(
mcr.as_dictionary().is_some(),
"inline MCR must be a dictionary"
);
assert!(
mcr.try_get_key(b"/Pg").unwrap().object_ref() == Some(ObjectRef::new(7, 0)),
"MCR surviving /Pg must be remapped to the new ref"
);
let objr = elem_dict(&mut pdf, 21);
assert!(
objr.try_get_key(b"/Pg").unwrap().object_ref() == Some(ObjectRef::new(7, 0)),
"OBJR surviving /Pg must be remapped to the new ref"
);
}
#[test]
fn pg_resolving_to_non_page_left_unchanged() {
let mut objs = base_objs();
objs.insert(20, "<< /Type /StructElem /S /P /Pg 30 0 R >>".into());
objs.insert(30, "<< /Type /Whatever >>".into());
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("non-page /Pg");
let elem = elem_dict(&mut pdf, 20);
assert_eq!(
elem.try_get_key(b"/Pg").unwrap().object_ref(),
Some(ObjectRef::new(30, 0))
);
}
#[test]
fn pg_resolving_to_orphan_page_left_unchanged() {
let mut objs = base_objs();
objs.insert(20, "<< /Type /StructElem /S /P /Pg 30 0 R >>".into());
objs.insert(
30,
"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>".into(),
);
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("orphan-page /Pg");
let elem = elem_dict(&mut pdf, 20);
assert_eq!(
elem.try_get_key(b"/Pg").unwrap().object_ref(),
Some(ObjectRef::new(30, 0))
);
}
#[test]
fn no_struct_tree_root_is_a_noop() {
let mut objs = base_objs();
objs.insert(1, "<< /Type /Catalog /Pages 2 0 R >>".into());
objs.remove(&10);
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("noop");
}
#[test]
fn direct_dict_kid_change_written_back_to_root() {
let mut objs = base_objs();
objs.insert(
10,
"<< /Type /StructTreeRoot \
/K << /Type /StructElem /S /P /Pg 4 0 R >> >>"
.into(),
);
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("pg drop");
let root = elem_dict(&mut pdf, 10);
let kid = root.try_get_key(b"/K").unwrap();
assert!(
kid.as_dictionary().is_some(),
"direct kid must be a dictionary"
);
assert!(
!kid.try_has_key(b"/Pg").unwrap(),
"direct-dict kid's dangling /Pg must be dropped and written back"
);
}
#[test]
fn indirect_kid_array_processed() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /Document /P 10 0 R /K 25 0 R >>".into(),
);
objs.insert(25, "[ 21 0 R ]".into());
objs.insert(
21,
"<< /Type /StructElem /S /P /P 20 0 R /Pg 4 0 R >>".into(),
);
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("pg drop");
let elem = elem_dict(&mut pdf, 21);
assert!(
!elem.try_has_key(b"/Pg").unwrap(),
"kid reached through an indirect /K array must have /Pg dropped"
);
}
#[test]
fn kid_cycle_terminates() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /P /P 10 0 R /Pg 4 0 R /K 21 0 R >>".into(),
);
objs.insert(
21,
"<< /Type /StructElem /S /P /P 20 0 R /K 20 0 R >>".into(),
);
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("cycle must terminate");
let elem = elem_dict(&mut pdf, 20);
assert!(
!elem.try_has_key(b"/Pg").unwrap(),
"dangling /Pg dropped despite cycle"
);
}
#[test]
fn direct_struct_tree_root_on_catalog_written_back() {
let mut objs = base_objs();
objs.insert(
1,
"<< /Type /Catalog /Pages 2 0 R /StructTreeRoot \
<< /Type /StructTreeRoot /K << /Type /StructElem /S /P /Pg 4 0 R >> >> >>"
.into(),
);
objs.remove(&10);
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("pg drop");
let catalog = elem_dict(&mut pdf, 1);
let root = catalog.try_get_key(b"/StructTreeRoot").unwrap();
assert!(
root.as_dictionary().is_some(),
"direct root must be a dictionary"
);
let kid = root.try_get_key(b"/K").unwrap();
assert!(
kid.as_dictionary().is_some(),
"direct kid must be a dictionary"
);
assert!(
!kid.try_has_key(b"/Pg").unwrap(),
"dangling /Pg under a catalog-direct /StructTreeRoot must be dropped"
);
}
#[test]
fn non_dict_struct_tree_root_is_a_noop() {
let mut objs = base_objs();
objs.insert(10, "42".into());
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("noop");
}
#[test]
fn non_dict_catalog_is_a_noop() {
let mut objs = base_objs();
objs.insert(1, "42".into());
let mut pdf = open(&objs);
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5())
.expect("non-dict catalog is a noop");
assert!(targets.is_empty());
}
#[test]
fn unresolved_catalog_is_a_noop() {
let mut objs = base_objs();
objs.remove(&1);
let mut pdf = open(&objs);
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5())
.expect("an unresolved catalog handle must be skipped");
assert!(targets.is_empty());
}
#[test]
fn no_catalog_is_a_noop() {
let pdf_bytes = build_pdf_inner(&base_objs(), false);
let mut pdf = Pdf::open(Cursor::new(pdf_bytes)).expect("open rootless fixture");
assert!(pdf.root_ref().is_none(), "fixture must have no catalog");
let targets = drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("noop");
assert!(
targets.is_empty(),
"no catalog => no /Obj targets collected"
);
}
#[test]
fn typeless_elem_processed_and_indirect_type_resolved() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /Document /P 10 0 R /K [21 0 R 22 0 R] >>".into(),
);
objs.insert(21, "<< /S /P /P 20 0 R /Pg 4 0 R >>".into());
objs.insert(22, "<< /Type 30 0 R /Pg 4 0 R /MCID 0 /K 23 0 R >>".into());
objs.insert(
23,
"<< /Type /StructElem /S /P /P 22 0 R /Pg 4 0 R >>".into(),
);
objs.insert(30, "/MCR".into());
let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("pg drop");
let typeless = elem_dict(&mut pdf, 21);
assert!(
!typeless.try_has_key(b"/Pg").unwrap(),
"typeless StructElem must still have its dangling /Pg dropped"
);
let mcr = elem_dict(&mut pdf, 22);
assert!(
!mcr.try_has_key(b"/Pg").unwrap(),
"MCR (indirect /Type) dangling /Pg must be dropped"
);
let unwalked_kid = elem_dict(&mut pdf, 23);
assert!(
unwalked_kid.try_get_key(b"/Pg").unwrap().object_ref() == Some(ObjectRef::new(4, 0)),
"kid under an MCR (indirect /Type) must not be walked, so its /Pg stays"
);
}
#[test]
fn indirect_kid_array_with_direct_dict_kid_written_back() {
let mut objs = base_objs();
objs.insert(
20,
"<< /Type /StructElem /S /Document /P 10 0 R /K 25 0 R >>".into(),
);
objs.insert(
25,
"[ << /Type /StructElem /S /P /Pg 4 0 R >> (noise) 26 0 R ]".into(),
);
objs.insert(26, "7".into()); let mut pdf = open(&objs);
drop_struct_elem_dangling_pg(&mut pdf, &keep_3_and_5()).expect("pg drop");
let arr_handle = pdf.get_object_handle(ObjectRef::new(25, 0));
arr_handle.try_is_scalar().expect("array");
let arr = arr_handle.as_array().expect("object 25 is not an array");
let kid = arr[0].clone();
assert!(
kid.as_dictionary().is_some(),
"direct kid must be a dictionary"
);
assert!(
!kid.try_has_key(b"/Pg").unwrap(),
"direct-dict kid in an indirect /K array must have /Pg dropped"
);
assert!(
arr[1].as_string() == Some(b"noise".to_vec()),
"non-kid array entry must round-trip unchanged"
);
}
#[test]
fn direct_dict_kid_error_propagates_from_array() {
let mut objs = base_objs();
objs.insert(
10,
"<< /Type /StructTreeRoot /K [ << /Type /StructElem /S /P /K 42 >> ] >>".into(),
);
let mut pdf = open(&objs);
let err = drop_struct_elem_dangling_pg_with_max_depth(&mut pdf, &keep_3_and_5(), 1)
.expect_err("nested direct array kid must hit the depth limit");
assert!(
matches!(err, Error::Unsupported(_)),
"over-deep direct array kid must surface Unsupported, got {err:?}"
);
}
#[test]
fn depth_limit_exceeded_is_unsupported() {
let mut objs = base_objs();
let mut nested = "<< /Type /StructElem /S /P /Pg 4 0 R >>".to_string();
for _ in 0..5 {
nested = format!("<< /Type /StructElem /S /P /K {nested} >>");
}
objs.insert(10, format!("<< /Type /StructTreeRoot /K {nested} >>"));
let mut pdf = open(&objs);
let err =
drop_struct_elem_dangling_pg_with_max_depth(&mut pdf, &keep_3_and_5(), 3).unwrap_err();
assert!(
matches!(err, Error::Unsupported(_)),
"over-deep tree must surface Unsupported, got {err:?}"
);
}
}