use std::collections::{BTreeSet, HashMap, VecDeque};
use std::io::{Read, Seek};
use crate::object::{Dictionary, Object, ObjectRef, MAX_INLINE_DEPTH};
use crate::reader::Pdf;
use crate::Error;
pub(crate) trait NewNumberLookup {
fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef>;
}
impl NewNumberLookup for CatalogFirstRenumber {
fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.old_to_new.get(&original).copied()
}
}
impl NewNumberLookup for GenerateRenumber {
fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.old_to_new.get(&original).copied()
}
}
impl NewNumberLookup for HashMap<ObjectRef, ObjectRef> {
fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.get(&original).copied()
}
}
pub(crate) struct CatalogFirstRenumber {
old_to_new: HashMap<ObjectRef, ObjectRef>,
order: Vec<ObjectRef>,
}
impl CatalogFirstRenumber {
pub(crate) fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.old_to_new.get(&original).copied()
}
pub(crate) fn len(&self) -> usize {
self.order.len()
}
pub(crate) fn pairs(&self) -> impl Iterator<Item = (ObjectRef, ObjectRef)> + '_ {
self.order
.iter()
.enumerate()
.map(|(i, &old)| (ObjectRef::new(i as u32 + 1, 0), old))
}
pub(crate) fn build<R: Read + Seek>(
pdf: &mut Pdf<R>,
skip_length: bool,
) -> crate::Result<Self> {
Self::build_with_visibility(pdf, skip_length, false)
}
pub(crate) fn build_qpdf<R: Read + Seek>(
pdf: &mut Pdf<R>,
skip_length: bool,
) -> crate::Result<Self> {
Self::build_with_visibility(pdf, skip_length, true)
}
fn build_with_visibility<R: Read + Seek>(
pdf: &mut Pdf<R>,
skip_length: bool,
qpdf_visibility: bool,
) -> crate::Result<Self> {
let mut old_to_new: HashMap<ObjectRef, ObjectRef> = HashMap::new();
let mut order: Vec<ObjectRef> = Vec::new();
let mut queue: VecDeque<ObjectRef> = VecDeque::new();
let root = pdf
.root_ref()
.ok_or_else(|| Error::Unsupported("plain rewrite: trailer has no /Root".to_string()))?;
let mut seeds: Vec<ObjectRef> = vec![root];
let trailer_entries = crate::qpdf_null::snapshot_entries(pdf.trailer(), false);
let trailer_entries = if qpdf_visibility {
crate::qpdf_null::visible_entries(pdf, trailer_entries)?
} else {
trailer_entries
};
for (key, value) in trailer_entries {
if matches!(
key.as_slice(),
b"ID" | b"Encrypt" | b"Prev" | b"Root" | b"Size"
) {
continue;
}
if qpdf_visibility {
collect_qpdf_enqueue_refs(pdf, &value, 0, skip_length, &mut seeds)?;
} else {
collect_refs(&value, 0, skip_length, &mut |r| seeds.push(r))?;
}
}
for seed in seeds {
enqueue(seed, &mut old_to_new, &mut order, &mut queue);
}
while let Some(cur) = queue.pop_front() {
if qpdf_visibility {
let obj = pdf.resolve(cur)?;
let mut found = Vec::new();
collect_qpdf_enqueue_refs(pdf, &obj, 0, skip_length, &mut found)?;
for reference in found {
enqueue(reference, &mut old_to_new, &mut order, &mut queue);
}
} else {
let obj = pdf.resolve_borrowed(cur)?;
collect_refs(obj, 0, skip_length, &mut |r| {
enqueue(r, &mut old_to_new, &mut order, &mut queue);
})?;
}
}
Ok(Self { old_to_new, order })
}
}
fn collect_qpdf_enqueue_refs<R: Read + Seek>(
pdf: &mut Pdf<R>,
obj: &Object,
depth: usize,
skip_length: bool,
found: &mut Vec<ObjectRef>,
) -> crate::Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(Error::Unsupported(
"plain rewrite: inline object nesting exceeds MAX_INLINE_DEPTH during \
qpdf enqueue collection"
.to_string(),
));
}
match obj {
Object::Reference(reference) => {
if reference.number != 0 {
found.push(*reference);
}
}
Object::Array(items) => {
for item in items {
collect_qpdf_enqueue_refs(pdf, item, depth + 1, skip_length, found)?;
}
}
Object::Dictionary(dict) => {
let entries = crate::qpdf_null::snapshot_entries(dict, false);
for (_, value) in crate::qpdf_null::visible_entries(pdf, entries)? {
collect_qpdf_enqueue_refs(pdf, &value, depth + 1, skip_length, found)?;
}
}
Object::Stream(stream) => {
let entries = crate::qpdf_null::snapshot_entries(&stream.dict, skip_length);
for (_, value) in crate::qpdf_null::visible_entries(pdf, entries)? {
collect_qpdf_enqueue_refs(pdf, &value, depth + 1, skip_length, found)?;
}
}
_ => {}
}
Ok(())
}
pub(crate) fn reachable_object_set<R: Read + Seek>(
pdf: &mut Pdf<R>,
skip_length: bool,
) -> crate::Result<BTreeSet<ObjectRef>> {
let root = pdf
.root_ref()
.ok_or_else(|| Error::Unsupported("reachability: trailer has no /Root".to_string()))?;
let mut seeds: Vec<ObjectRef> = vec![root];
let trailer_entries = crate::qpdf_null::snapshot_entries(pdf.trailer(), false);
for (key, value) in crate::qpdf_null::visible_entries(pdf, trailer_entries)? {
if matches!(key.as_slice(), b"ID" | b"Prev" | b"Root" | b"Size") {
continue;
}
collect_qpdf_enqueue_refs(pdf, &value, 0, skip_length, &mut seeds)?;
}
let mut reachable: BTreeSet<ObjectRef> = BTreeSet::new();
let mut queue: VecDeque<ObjectRef> = VecDeque::new();
for seed in seeds {
if reachable.insert(seed) {
queue.push_back(seed);
}
}
while let Some(cur) = queue.pop_front() {
let obj = pdf.resolve(cur)?;
let mut found = Vec::new();
collect_qpdf_enqueue_refs(pdf, &obj, 0, skip_length, &mut found)?;
for r in found {
if reachable.insert(r) {
queue.push_back(r);
}
}
}
Ok(reachable)
}
pub(crate) fn resurrectable_null_refs_excluding<R: Read + Seek>(
pdf: &mut Pdf<R>,
removed_refs: &BTreeSet<ObjectRef>,
) -> crate::Result<BTreeSet<ObjectRef>> {
let root = pdf
.root_ref()
.ok_or_else(|| Error::Unsupported("resurrectable: trailer has no /Root".to_string()))?;
let mut result: BTreeSet<ObjectRef> = BTreeSet::new();
let mut visited: BTreeSet<ObjectRef> = BTreeSet::new();
let mut queue: VecDeque<ObjectRef> = VecDeque::from([root]);
let trailer_entries = crate::qpdf_null::snapshot_entries(pdf.trailer(), false);
for (key, value) in trailer_entries {
if matches!(key.as_slice(), b"ID" | b"Prev" | b"Root" | b"Size") {
continue;
}
let mut follow: Vec<ObjectRef> = Vec::new();
walk_surviving(
pdf,
&value,
0,
false,
&mut follow,
&mut result,
removed_refs,
)?;
queue.extend(follow);
}
while let Some(cur) = queue.pop_front() {
if !visited.insert(cur) {
continue;
}
let obj = pdf.resolve(cur)?;
let mut follow: Vec<ObjectRef> = Vec::new();
walk_surviving(pdf, &obj, 0, false, &mut follow, &mut result, removed_refs)?;
for r in follow {
if !visited.contains(&r) {
queue.push_back(r);
}
}
}
Ok(result)
}
fn walk_surviving<R: Read + Seek>(
pdf: &mut Pdf<R>,
obj: &Object,
depth: usize,
in_array: bool,
follow: &mut Vec<ObjectRef>,
result: &mut BTreeSet<ObjectRef>,
removed_refs: &BTreeSet<ObjectRef>,
) -> crate::Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(Error::Unsupported(
"linearization: inline nesting exceeds MAX_INLINE_DEPTH during resurrectable walk"
.to_string(),
));
}
if crate::qpdf_null::value_is_null(pdf, obj)? {
if in_array {
if let Object::Reference(reference) = obj {
if reference.number > 0 && !removed_refs.contains(reference) {
result.insert(*reference);
}
}
}
return Ok(());
}
match obj {
Object::Reference(r) => {
follow.push(*r);
}
Object::Array(elements) => {
for e in elements {
walk_surviving(pdf, e, depth + 1, true, follow, result, removed_refs)?;
}
}
Object::Dictionary(dict) => {
for (_key, value) in dict.iter() {
walk_surviving(pdf, value, depth + 1, false, follow, result, removed_refs)?;
}
}
Object::Stream(stream) => {
for (_key, value) in stream.dict.iter() {
walk_surviving(pdf, value, depth + 1, false, follow, result, removed_refs)?;
}
}
_ => {}
}
Ok(())
}
#[cfg(test)]
impl CatalogFirstRenumber {
pub(crate) fn from_pairs_for_test(pairs: &[(ObjectRef, ObjectRef)]) -> Self {
Self {
old_to_new: pairs.iter().copied().collect(),
order: pairs.iter().map(|(old, _)| *old).collect(),
}
}
}
#[allow(dead_code)]
pub(crate) struct GenerateRenumber {
old_to_new: HashMap<ObjectRef, ObjectRef>,
container_new: Vec<Option<u32>>,
}
#[allow(dead_code)]
impl GenerateRenumber {
pub(crate) fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.old_to_new.get(&original).copied()
}
pub(crate) fn container_numbers(&self) -> Vec<u32> {
self.container_new.iter().flatten().copied().collect()
}
pub(crate) fn container_number(&self, group_index: usize) -> Option<u32> {
self.container_new.get(group_index).copied().flatten()
}
pub(crate) fn pairs(&self) -> impl Iterator<Item = (ObjectRef, ObjectRef)> + '_ {
self.old_to_new.iter().map(|(&old, &new)| (new, old))
}
pub(crate) fn build<R: Read + Seek>(
pdf: &mut Pdf<R>,
groups: &[Vec<ObjectRef>],
skip_length: bool,
removed_refs: &BTreeSet<ObjectRef>,
) -> crate::Result<Self> {
let mut member_to_group: HashMap<ObjectRef, usize> = HashMap::new();
let mut groups_sorted: Vec<Vec<ObjectRef>> = Vec::with_capacity(groups.len());
for (gi, group) in groups.iter().enumerate() {
let mut sorted = group.clone();
sorted.sort_unstable_by_key(|r| (r.number, r.generation));
for &m in &sorted {
member_to_group.insert(m, gi);
}
groups_sorted.push(sorted);
}
let mut old_to_new: HashMap<ObjectRef, ObjectRef> = HashMap::new();
let mut container_new: Vec<Option<u32>> = vec![None; groups.len()];
let mut next: u32 = 1;
let mut queue: VecDeque<ObjectRef> = VecDeque::new();
let root = pdf
.root_ref()
.ok_or_else(|| Error::Unsupported("generate: trailer has no /Root".to_string()))?;
let mut seeds: Vec<ObjectRef> = vec![root];
let trailer_entries = crate::qpdf_null::snapshot_entries(pdf.trailer(), false);
let trailer_entries = crate::qpdf_null::visible_entries(pdf, trailer_entries)?;
for (key, value) in trailer_entries {
if matches!(
key.as_slice(),
b"ID" | b"Encrypt" | b"Prev" | b"Root" | b"Size"
) {
continue;
}
collect_qpdf_enqueue_refs(pdf, &value, 0, skip_length, &mut seeds)?;
}
seeds.retain(|reference| !removed_refs.contains(reference));
for seed in seeds {
enqueue_gen(
seed,
&member_to_group,
&groups_sorted,
&mut old_to_new,
&mut container_new,
&mut next,
&mut queue,
);
}
while let Some(cur) = queue.pop_front() {
let obj = pdf.resolve(cur)?;
let mut found = Vec::new();
collect_qpdf_enqueue_refs(pdf, &obj, 0, skip_length, &mut found)?;
found.retain(|reference| !removed_refs.contains(reference));
for reference in found {
enqueue_gen(
reference,
&member_to_group,
&groups_sorted,
&mut old_to_new,
&mut container_new,
&mut next,
&mut queue,
);
}
}
Ok(Self {
old_to_new,
container_new,
})
}
}
#[allow(dead_code, clippy::too_many_arguments)]
fn enqueue_gen(
r: ObjectRef,
member_to_group: &HashMap<ObjectRef, usize>,
groups_sorted: &[Vec<ObjectRef>],
old_to_new: &mut HashMap<ObjectRef, ObjectRef>,
container_new: &mut [Option<u32>],
next: &mut u32,
queue: &mut VecDeque<ObjectRef>,
) {
if old_to_new.contains_key(&r) {
return;
}
match member_to_group.get(&r) {
Some(&gi) => {
debug_assert!(container_new[gi].is_none());
container_new[gi] = Some(*next);
*next += 1;
for &m in &groups_sorted[gi] {
old_to_new.insert(m, ObjectRef::new(*next, 0));
*next += 1;
queue.push_back(m);
}
}
None => {
old_to_new.insert(r, ObjectRef::new(*next, 0));
*next += 1;
queue.push_back(r);
}
}
}
fn enqueue(
original: ObjectRef,
old_to_new: &mut HashMap<ObjectRef, ObjectRef>,
order: &mut Vec<ObjectRef>,
queue: &mut VecDeque<ObjectRef>,
) {
if old_to_new.contains_key(&original) {
return;
}
let new_ref = ObjectRef::new(order.len() as u32 + 1, 0);
old_to_new.insert(original, new_ref);
order.push(original);
queue.push_back(original);
}
fn collect_refs(
obj: &Object,
depth: usize,
skip_length: bool,
f: &mut impl FnMut(ObjectRef),
) -> crate::Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(Error::Unsupported(
"plain rewrite: inline object nesting exceeds MAX_INLINE_DEPTH during \
reference collection"
.to_string(),
));
}
match obj {
Object::Reference(r) => f(*r),
Object::Array(elements) => {
for element in elements {
collect_refs(element, depth + 1, skip_length, f)?;
}
}
Object::Dictionary(dict) => {
for (_key, value) in dict.iter() {
collect_refs(value, depth + 1, skip_length, f)?;
}
}
Object::Stream(stream) => {
for (key, value) in stream.dict.iter() {
if skip_length && key == b"Length" {
continue;
}
collect_refs(value, depth + 1, skip_length, f)?;
}
}
_ => {}
}
Ok(())
}
pub(crate) fn renumber_refs_in_place<M: NewNumberLookup>(
obj: &mut Object,
map: &M,
) -> crate::Result<()> {
rewrite(obj, 0, map)
}
pub(crate) fn renumber_qpdf_refs_in_place<R: Read + Seek, M: NewNumberLookup>(
pdf: &mut Pdf<R>,
obj: &mut Object,
map: &M,
) -> crate::Result<()> {
renumber_qpdf_refs_in_place_with_removed(pdf, obj, map, &BTreeSet::new())
}
pub(crate) fn renumber_qpdf_refs_in_place_with_removed<R: Read + Seek, M: NewNumberLookup>(
pdf: &mut Pdf<R>,
obj: &mut Object,
map: &M,
removed_refs: &BTreeSet<ObjectRef>,
) -> crate::Result<()> {
rewrite_qpdf(pdf, obj, 0, map, removed_refs)
}
fn rewrite_qpdf<R: Read + Seek, M: NewNumberLookup>(
pdf: &mut Pdf<R>,
obj: &mut Object,
depth: usize,
map: &M,
removed_refs: &BTreeSet<ObjectRef>,
) -> crate::Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(Error::Unsupported(
"plain rewrite: inline object nesting exceeds MAX_INLINE_DEPTH during \
qpdf reference rewriting"
.to_string(),
));
}
match obj {
Object::Reference(reference) => {
if reference.number == 0 || removed_refs.contains(reference) {
*obj = Object::Null;
} else {
*reference = map.new_for_original(*reference).ok_or_else(|| {
Error::Unsupported(format!(
"plain rewrite: reference {reference} absent from renumber map \
(dangling ref)"
))
})?;
}
}
Object::Array(items) => {
for item in items {
rewrite_qpdf(pdf, item, depth + 1, map, removed_refs)?;
}
}
Object::Dictionary(dict) => {
let entries = crate::qpdf_null::snapshot_entries(dict, false);
let entries = crate::qpdf_null::visible_entries(pdf, entries)?;
let mut rewritten = Dictionary::new();
for (key, mut value) in entries {
rewrite_qpdf(pdf, &mut value, depth + 1, map, removed_refs)?;
if !matches!(value, Object::Null) {
rewritten.insert(key, value);
}
}
*dict = rewritten;
}
Object::Stream(stream) => {
let mut entries = crate::qpdf_null::snapshot_entries(&stream.dict, false);
for (key, value) in &mut entries {
if key == b"Length"
&& matches!(
value,
Object::Reference(reference)
if map.new_for_original(*reference).is_none()
)
{
*value = Object::Integer(stream.data.len() as i64);
}
}
let entries = crate::qpdf_null::visible_entries(pdf, entries)?;
let mut rewritten = Dictionary::new();
for (key, mut value) in entries {
rewrite_qpdf(pdf, &mut value, depth + 1, map, removed_refs)?;
if !matches!(value, Object::Null) {
rewritten.insert(key, value);
}
}
stream.dict = rewritten;
}
_ => {}
}
Ok(())
}
fn rewrite<M: NewNumberLookup>(obj: &mut Object, depth: usize, map: &M) -> crate::Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(Error::Unsupported(
"plain rewrite: inline object nesting exceeds MAX_INLINE_DEPTH during \
reference rewriting"
.to_string(),
));
}
match obj {
Object::Reference(r) => {
*r = map.new_for_original(*r).ok_or_else(|| {
Error::Unsupported(format!(
"plain rewrite: reference {r} absent from renumber map (dangling ref)"
))
})?;
}
Object::Array(elements) => {
for element in elements {
rewrite(element, depth + 1, map)?;
}
}
Object::Dictionary(dict) => {
for value in dict.values_mut() {
rewrite(value, depth + 1, map)?;
}
}
Object::Stream(stream) => {
let drop_length = matches!(
stream.dict.get("Length"),
Some(Object::Reference(r)) if map.new_for_original(*r).is_none()
);
if drop_length {
let data_len = stream.data.len() as i64;
stream.dict.insert("Length", Object::Integer(data_len));
}
for value in stream.dict.values_mut() {
rewrite(value, depth + 1, map)?;
}
}
_ => {}
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::object::{Dictionary, Stream};
fn type_tag<R: Read + Seek>(pdf: &mut Pdf<R>, r: ObjectRef) -> String {
let obj = pdf.resolve(r).expect("resolve");
match &obj {
Object::Stream(_) => "stream".to_string(),
Object::Dictionary(dict) => match dict.get("Type") {
Some(Object::Name(name)) => format!("/{}", String::from_utf8_lossy(name)),
Some(Object::Reference(tref)) => match pdf.resolve(*tref) {
Ok(Object::Name(name)) => format!("/{}", String::from_utf8_lossy(&name)),
_ => "dict".to_string(),
},
_ => "dict".to_string(),
},
_ => "other".to_string(),
}
}
fn tag_sequence<R: Read + Seek>(pdf: &mut Pdf<R>, map: &CatalogFirstRenumber) -> Vec<String> {
let olds: Vec<ObjectRef> = map.pairs().map(|(_new, old)| old).collect();
olds.into_iter().map(|old| type_tag(pdf, old)).collect()
}
fn build_raw_pdf(bodies: &[(u32, &[u8])]) -> Vec<u8> {
build_raw_pdf_with_trailer_extra(bodies, b"")
}
fn build_raw_pdf_with_trailer_extra(bodies: &[(u32, &[u8])], trailer_extra: &[u8]) -> Vec<u8> {
let mut out: Vec<u8> = b"%PDF-1.7\n%\xe2\xe3\xcf\xd3\n".to_vec();
let max_num = bodies.iter().map(|(n, _)| *n).max().unwrap_or(0);
let size = max_num + 1;
let mut offsets = vec![0usize; size as usize];
for (num, body) in bodies {
offsets[*num as usize] = out.len();
out.extend_from_slice(format!("{num} 0 obj\n").as_bytes());
out.extend_from_slice(body);
out.extend_from_slice(b"\nendobj\n");
}
let xref = out.len();
out.extend_from_slice(format!("xref\n0 {size}\n0000000000 65535 f \n").as_bytes());
for off in offsets.iter().skip(1) {
if *off == 0 {
out.extend_from_slice(b"0000000000 65535 f \n");
} else {
out.extend_from_slice(format!("{off:010} 00000 n \n").as_bytes());
}
}
out.extend_from_slice(format!("trailer\n<< /Size {size} /Root 1 0 R ").as_bytes());
out.extend_from_slice(trailer_extra);
out.extend_from_slice(b" >>\n");
out.extend_from_slice(format!("startxref\n{xref}\n%%EOF\n").as_bytes());
out
}
#[test]
fn one_page_tag_sequence_matches_qpdf_oracle() {
let bytes = include_bytes!("../../../tests/fixtures/compat/one-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert_eq!(map.len(), 7);
assert_eq!(
tag_sequence(&mut pdf, &map),
vec!["/Catalog", "dict", "/Pages", "/Page", "stream", "dict", "/Font"]
);
}
#[test]
fn catalog_first_null_visibility_matches_qpdf_order_without_mutating_source() {
let bytes = include_bytes!("../../../tests/fixtures/compat/null-visible-matrix.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let root = pdf.root_ref().expect("root");
let original_root = pdf.resolve(root).expect("resolve root");
let map = CatalogFirstRenumber::build_qpdf(&mut pdf, true).expect("build");
assert_eq!(
map.pairs().collect::<Vec<_>>(),
vec![
(ObjectRef::new(1, 0), ObjectRef::new(1, 0)),
(ObjectRef::new(2, 0), ObjectRef::new(6, 0)),
(ObjectRef::new(3, 0), ObjectRef::new(99, 0)),
(ObjectRef::new(4, 0), ObjectRef::new(8, 0)),
(ObjectRef::new(5, 0), ObjectRef::new(5, 0)),
(ObjectRef::new(6, 0), ObjectRef::new(2, 0)),
(ObjectRef::new(7, 0), ObjectRef::new(3, 0)),
(ObjectRef::new(8, 0), ObjectRef::new(4, 0)),
],
"source order must match qpdf 11.9.0's standard object queue"
);
assert_eq!(
pdf.resolve(root).unwrap(),
original_root,
"visibility analysis must not mutate the source graph"
);
}
#[test]
fn catalog_first_drops_dict_only_real_null_but_numbers_array_missing_ref() {
let catalog = b"<< /Type /Catalog /Pages 2 0 R /Drop 5 0 R /Keep [99 0 R] >>";
let pages = b"<< /Type /Pages /Kids [3 0 R] /Count 1 >>";
let page = b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>";
let bytes = build_raw_pdf(&[(1, catalog), (2, pages), (3, page), (5, b"null")]);
let mut pdf = Pdf::open_mem(&bytes).expect("open");
let map = CatalogFirstRenumber::build_qpdf(&mut pdf, true).expect("build");
assert_eq!(
map.new_for_original(ObjectRef::new(5, 0)),
None,
"dict-only REAL-null must not receive a number"
);
assert!(
map.new_for_original(ObjectRef::new(99, 0)).is_some(),
"the same missing ref reached from an array must receive a number"
);
}
#[test]
fn resurrectable_collects_array_nulls_not_dict_or_object_zero() {
let cat = b"<< /Type /Catalog /Pages 2 0 R /Arr [ 98 0 R 2 0 R 0 0 R ] \
/Held 99 0 R /Nest << /Inner 97 0 R >> /Free [ 5 0 R ] \
/Real [ 4 0 R ] /HeldReal 6 0 R >>";
let pages = b"<< /Type /Pages /Kids [3 0 R] /Count 1 >>";
let page = b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>";
let bytes = build_raw_pdf(&[
(1, cat),
(2, pages),
(3, page),
(4, b"null"),
(6, b"null"),
(10, b"<< >>"),
]);
let mut pdf = Pdf::open_mem(&bytes).expect("open");
let got =
resurrectable_null_refs_excluding(&mut pdf, &BTreeSet::new()).expect("resurrectable");
let nums: BTreeSet<u32> = got.iter().map(|r| r.number).collect();
assert!(
nums.contains(&98),
"missing array element 98 must be resurrectable"
);
assert!(
nums.contains(&5),
"free array element 5 must be resurrectable"
);
assert!(
nums.contains(&4),
"REAL-null array element 4 must be resurrectable"
);
assert!(
!nums.contains(&99),
"dict-only missing 99 must NOT be resurrectable"
);
assert!(
!nums.contains(&97),
"nested dict-value missing 97 must NOT be resurrectable"
);
assert!(
!nums.contains(&6),
"dict-only REAL-null 6 must NOT be resurrectable"
);
assert!(
!nums.contains(&2),
"live Pages ref must NOT be resurrectable"
);
assert!(
!nums.contains(&0),
"object 0 must NOT be resurrectable (inline null)"
);
}
#[test]
fn resurrectable_excludes_only_operation_removed_generation() {
let bytes =
include_bytes!("../../../tests/fixtures/compat/null-visible-stale-generation.pdf");
let stale = ObjectRef::new(4, 0);
let mut pdf = Pdf::open_mem(bytes).expect("open");
let standard = resurrectable_null_refs_excluding(&mut pdf, &BTreeSet::new())
.expect("standard resurrectable");
assert!(
standard.contains(&stale),
"standard enqueue retains the stale identity for the linearization guard"
);
let mut removed = BTreeSet::new();
removed.insert(stale);
let mut pdf = Pdf::open_mem(bytes).expect("open");
let filtered =
resurrectable_null_refs_excluding(&mut pdf, &removed).expect("filtered resurrectable");
assert!(
!filtered.contains(&stale),
"the operation-specific removed set directizes the stale reference"
);
}
#[test]
fn resurrectable_errors_on_excessive_array_nesting() {
let mut deep = b"99 0 R".to_vec();
for _ in 0..(MAX_INLINE_DEPTH + 2) {
let mut wrapped = b"[ ".to_vec();
wrapped.extend_from_slice(&deep);
wrapped.extend_from_slice(b" ]");
deep = wrapped;
}
let cat = [
b"<< /Type /Catalog /Pages 2 0 R /Deep ".to_vec(),
deep,
b" >>".to_vec(),
]
.concat();
let pages = b"<< /Type /Pages /Kids [3 0 R] /Count 1 >>";
let page = b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>";
let bytes = build_raw_pdf(&[(1, &cat), (2, pages), (3, page)]);
let mut pdf = Pdf::open_mem(&bytes).expect("open");
let got = resurrectable_null_refs_excluding(&mut pdf, &BTreeSet::new());
assert!(
matches!(got, Err(crate::Error::Unsupported(_))),
"over-deep nesting must error, not silently truncate"
);
}
#[test]
fn resurrectable_propagates_excessive_nesting_from_trailer_entry() {
let mut deep = b"99 0 R".to_vec();
for _ in 0..(MAX_INLINE_DEPTH + 2) {
let mut wrapped = b"[ ".to_vec();
wrapped.extend_from_slice(&deep);
wrapped.extend_from_slice(b" ]");
deep = wrapped;
}
let mut trailer_extra = b"/Deep ".to_vec();
trailer_extra.extend_from_slice(&deep);
let catalog = b"<< /Type /Catalog /Pages 2 0 R >>";
let pages = b"<< /Type /Pages /Kids [3 0 R] /Count 1 >>";
let page = b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>";
let bytes = build_raw_pdf_with_trailer_extra(
&[(1, catalog), (2, pages), (3, page)],
&trailer_extra,
);
let mut pdf = Pdf::open_mem(&bytes).expect("open");
let got = resurrectable_null_refs_excluding(&mut pdf, &BTreeSet::new());
assert!(
matches!(got, Err(crate::Error::Unsupported(_))),
"over-deep trailer entry must propagate the walk error"
);
}
#[test]
fn two_page_tag_sequence_matches_qpdf_oracle() {
let bytes = include_bytes!("../../../tests/fixtures/compat/two-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert_eq!(map.len(), 9);
assert_eq!(
tag_sequence(&mut pdf, &map),
vec![
"/Catalog", "dict", "/Pages", "/Page", "/Page", "stream", "dict", "stream", "/Font"
]
);
}
#[test]
fn three_page_tag_sequence_matches_qpdf_oracle() {
let bytes = include_bytes!("../../../tests/fixtures/compat/three-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert_eq!(map.len(), 11);
assert_eq!(
tag_sequence(&mut pdf, &map),
vec![
"/Catalog", "dict", "/Pages", "/Page", "/Page", "/Page", "stream", "dict",
"stream", "stream", "/Font"
]
);
}
#[test]
fn pairs_yield_ascending_new_numbers_from_one() {
let bytes = include_bytes!("../../../tests/fixtures/compat/one-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
let news: Vec<u32> = map.pairs().map(|(new, _old)| new.number).collect();
assert_eq!(news, vec![1, 2, 3, 4, 5, 6, 7]);
assert!(map.pairs().all(|(new, _)| new.generation == 0));
for (new, old) in map.pairs() {
assert_eq!(map.new_for_original(old), Some(new));
}
}
#[test]
fn build_drops_orphan_length_holder_via_length_skip_and_renumbers_contiguously() {
let bytes =
include_bytes!("../../../tests/fixtures/compat/objstm-lin-od-indirect-length.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert_eq!(map.len(), 6);
assert!(map.new_for_original(ObjectRef::new(7, 0)).is_none());
let mut news: Vec<u32> = map.pairs().map(|(new, _)| new.number).collect();
news.sort_unstable();
assert_eq!(news, vec![1, 2, 3, 4, 5, 6]);
}
#[test]
fn build_keeps_length_holder_when_not_skipping_length() {
let bytes =
include_bytes!("../../../tests/fixtures/compat/objstm-lin-od-indirect-length.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, false).expect("build");
assert!(
map.new_for_original(ObjectRef::new(7, 0)).is_some(),
"with skip_length=false the /Length holder stays numbered"
);
assert_eq!(map.len(), 7);
}
#[test]
fn build_drops_length_holder_referenced_only_from_unreachable_object() {
let pdf_bytes = build_raw_pdf(&[
(1, b"<< /Type /Catalog /Pages 2 0 R >>"),
(2, b"<< /Type /Pages /Count 1 /Kids [ 3 0 R ] >>"),
(
3,
b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /Contents 4 0 R >>",
),
(4, b"<< /Length 6 0 R >>\nstream\nBT ET\nendstream"),
(6, b"16"),
(7, b"<< /Held 6 0 R >>"),
]);
let mut pdf = Pdf::open_mem(&pdf_bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert!(
map.new_for_original(ObjectRef::new(6, 0)).is_none(),
"holder reached only via /Length plus an unreachable referrer must be dropped"
);
assert!(
map.new_for_original(ObjectRef::new(7, 0)).is_none(),
"the unreachable referrer must itself be GC'd"
);
let mut pdf2 = Pdf::open_mem(&pdf_bytes).expect("open");
let reachable = reachable_object_set(&mut pdf2, true).expect("walk");
assert!(!reachable.contains(&ObjectRef::new(6, 0)));
assert!(!reachable.contains(&ObjectRef::new(7, 0)));
assert!(
reachable.contains(&ObjectRef::new(4, 0)),
"the page's /Contents stream stays live"
);
}
#[test]
fn build_numbers_both_edges_holder_at_non_length_bfs_position() {
let stream4 = b"<< /Length 6 0 R /XObj 8 0 R >>\nstream\napp.alert('hi');\nendstream";
let pdf_bytes = build_raw_pdf(&[
(1, b"<< /Type /Catalog /Pages 2 0 R >>"),
(2, b"<< /Type /Pages /Count 1 /Kids [ 3 0 R ] >>"),
(
3,
b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /Contents 4 0 R /Tail 7 0 R >>",
),
(4, stream4),
(6, b"16"),
(7, b"<< /Held 6 0 R >>"),
(8, b"<< /Type /XObject /Subtype /Form >>"),
]);
let mut pdf = Pdf::open_mem(&pdf_bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert_eq!(
map.new_for_original(ObjectRef::new(6, 0)),
Some(ObjectRef::new(7, 0)),
"holder must be numbered via the non-/Length edge (obj 7), not the /Length edge"
);
assert_eq!(
map.new_for_original(ObjectRef::new(8, 0)),
Some(ObjectRef::new(6, 0)),
"the stream's non-/Length child (obj 8) precedes the holder"
);
let mut pdf_qdf = Pdf::open_mem(&pdf_bytes).expect("open");
let map_qdf = CatalogFirstRenumber::build(&mut pdf_qdf, false).expect("build");
assert_eq!(
map_qdf.new_for_original(ObjectRef::new(6, 0)),
Some(ObjectRef::new(6, 0))
);
assert_eq!(
map_qdf.new_for_original(ObjectRef::new(8, 0)),
Some(ObjectRef::new(7, 0))
);
}
#[test]
fn build_drops_length_holder_referenced_only_from_source_objstm() {
let pdf_bytes = build_raw_pdf(&[
(1, b"<< /Type /Catalog /Pages 2 0 R >>"),
(2, b"<< /Type /Pages /Count 1 /Kids [ 3 0 R ] >>"),
(
3,
b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /Contents 4 0 R >>",
),
(
4,
b"<< /Length 6 0 R >>\nstream\napp.alert('hi');\nendstream",
),
(6, b"16"),
(
7,
b"<< /Type /ObjStm /N 0 /First 0 /Length 0 /Aux 6 0 R >>\nstream\n\nendstream",
),
]);
let mut pdf = Pdf::open_mem(&pdf_bytes).expect("open");
let map = CatalogFirstRenumber::build(&mut pdf, true).expect("build");
assert!(
map.new_for_original(ObjectRef::new(6, 0)).is_none(),
"holder referenced only from an unreachable source ObjStm must be dropped"
);
assert!(map.new_for_original(ObjectRef::new(7, 0)).is_none());
}
#[test]
fn reachable_object_set_drops_source_linearization_artifacts() {
let bytes = include_bytes!("../../../tests/fixtures/compat/linearized-one-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let reachable = reachable_object_set(&mut pdf, true).expect("walk");
let mut nums: Vec<u32> = reachable.iter().map(|r| r.number).collect();
nums.sort_unstable();
assert_eq!(
nums,
vec![1, 2, 4, 6, 7, 8, 9],
"old /Linearized dict (3) and hint stream (5) must be GC'd"
);
assert!(!reachable.contains(&ObjectRef::new(3, 0)));
assert!(!reachable.contains(&ObjectRef::new(5, 0)));
}
#[test]
fn reachable_object_set_hides_dict_real_null_and_keeps_array_real_null() {
let bytes = build_raw_pdf(&[
(
1,
b"<< /Type /Catalog /Pages 2 0 R /DictNull 4 0 R /Array [5 0 R] >>",
),
(2, b"<< /Type /Pages /Count 1 /Kids [3 0 R] >>"),
(
3,
b"<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>",
),
(4, b"null"),
(5, b"null"),
]);
let mut pdf = Pdf::open_mem(&bytes).expect("open");
let reachable = reachable_object_set(&mut pdf, true).expect("walk");
assert!(
!reachable.contains(&ObjectRef::new(4, 0)),
"qpdf hides a dictionary edge whose live body resolves to null"
);
assert!(
reachable.contains(&ObjectRef::new(5, 0)),
"qpdf preserves an array null's indirect identity"
);
}
#[test]
fn reachable_object_set_drops_orphan_length_holder_via_length_skip() {
let bytes =
include_bytes!("../../../tests/fixtures/compat/objstm-lin-od-indirect-length.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let reachable = reachable_object_set(&mut pdf, true).expect("walk");
assert!(
!reachable.contains(&ObjectRef::new(7, 0)),
"orphan /Length holder must not be reachable once the /Length edge is skipped"
);
assert!(
reachable.contains(&ObjectRef::new(4, 0)),
"the page's /Contents stream stays live"
);
}
#[test]
fn reachable_object_set_includes_trailer_encrypt_dict() {
let bytes = include_bytes!("../../../tests/fixtures/compat/encrypted-r4-three-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let encrypt_ref = pdf
.trailer()
.get_ref("Encrypt")
.expect("fixture has /Encrypt");
let reachable = reachable_object_set(&mut pdf, true).expect("walk");
assert!(
reachable.contains(&encrypt_ref),
"the trailer /Encrypt dict ({encrypt_ref}) must be in the reachable universe"
);
}
#[test]
fn generate_build_drops_orphan_length_holder_via_length_skip() {
let bytes =
include_bytes!("../../../tests/fixtures/compat/objstm-lin-od-indirect-length.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = GenerateRenumber::build(&mut pdf, &[], true, &BTreeSet::new()).expect("build");
assert!(map.new_for_original(ObjectRef::new(7, 0)).is_none());
assert!(map.new_for_original(ObjectRef::new(4, 0)).is_some());
assert_eq!(map.pairs().count(), 6);
}
#[test]
fn renumber_refs_in_place_directizes_dropped_length_holder() {
let map = CatalogFirstRenumber {
old_to_new: HashMap::from([(ObjectRef::new(10, 0), ObjectRef::new(1, 0))]),
order: vec![ObjectRef::new(10, 0)],
};
let mut stream_dict = Dictionary::new();
stream_dict.insert("Length", Object::Reference(ObjectRef::new(40, 0)));
stream_dict.insert("S", Object::Reference(ObjectRef::new(10, 0)));
let mut obj = Object::Stream(Stream::new(stream_dict, b"hello".to_vec()));
renumber_refs_in_place(&mut obj, &map).expect("rewrite");
let strm = obj.as_stream().unwrap();
assert_eq!(strm.dict.get("Length"), Some(&Object::Integer(5)));
assert_eq!(
strm.dict.get("S"),
Some(&Object::Reference(ObjectRef::new(1, 0)))
);
}
#[test]
fn renumber_refs_in_place_renumbers_mapped_length_holder() {
let map = CatalogFirstRenumber {
old_to_new: HashMap::from([(ObjectRef::new(40, 0), ObjectRef::new(3, 0))]),
order: vec![ObjectRef::new(40, 0)],
};
let mut stream_dict = Dictionary::new();
stream_dict.insert("Length", Object::Reference(ObjectRef::new(40, 0)));
let mut obj = Object::Stream(Stream::new(stream_dict, b"x".to_vec()));
renumber_refs_in_place(&mut obj, &map).expect("rewrite");
assert_eq!(
obj.as_stream().unwrap().dict.get("Length"),
Some(&Object::Reference(ObjectRef::new(3, 0)))
);
}
#[test]
fn renumber_refs_in_place_rewrites_nested_refs() {
let map = CatalogFirstRenumber {
old_to_new: HashMap::from([
(ObjectRef::new(10, 0), ObjectRef::new(1, 0)),
(ObjectRef::new(20, 5), ObjectRef::new(2, 0)),
]),
order: vec![ObjectRef::new(10, 0), ObjectRef::new(20, 5)],
};
let mut inner = Dictionary::new();
inner.insert("Ref", Object::Reference(ObjectRef::new(20, 5)));
let mut stream_dict = Dictionary::new();
stream_dict.insert("S", Object::Reference(ObjectRef::new(10, 0)));
let mut dict = Dictionary::new();
dict.insert(
"Arr",
Object::Array(vec![
Object::Reference(ObjectRef::new(10, 0)),
Object::Dictionary(inner),
Object::Integer(7),
]),
);
dict.insert(
"Strm",
Object::Stream(Stream::new(stream_dict, b"opaque".to_vec())),
);
let mut obj = Object::Dictionary(dict);
renumber_refs_in_place(&mut obj, &map).expect("rewrite");
let dict = obj.as_dict().unwrap();
let arr = dict.get("Arr").unwrap().as_array().unwrap();
assert_eq!(arr[0], Object::Reference(ObjectRef::new(1, 0)));
let inner = arr[1].as_dict().unwrap();
assert_eq!(
inner.get("Ref"),
Some(&Object::Reference(ObjectRef::new(2, 0)))
);
assert_eq!(arr[2], Object::Integer(7));
let strm = dict.get("Strm").unwrap().as_stream().unwrap();
assert_eq!(
strm.dict.get("S"),
Some(&Object::Reference(ObjectRef::new(1, 0)))
);
assert_eq!(strm.data, b"opaque");
}
#[test]
fn renumber_refs_in_place_errors_on_unmapped_ref() {
let map = CatalogFirstRenumber {
old_to_new: HashMap::from([(ObjectRef::new(10, 0), ObjectRef::new(1, 0))]),
order: vec![ObjectRef::new(10, 0)],
};
let mut obj = Object::Reference(ObjectRef::new(99, 0));
let err = renumber_refs_in_place(&mut obj, &map).unwrap_err();
assert!(matches!(err, Error::Unsupported(_)));
}
#[test]
fn renumber_qpdf_refs_in_place_errors_on_unmapped_ref() {
let bytes = include_bytes!("../../../tests/fixtures/compat/one-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber {
old_to_new: HashMap::new(),
order: Vec::new(),
};
let mut obj = Object::Reference(ObjectRef::new(99, 0));
let err = renumber_qpdf_refs_in_place(&mut pdf, &mut obj, &map).unwrap_err();
assert!(matches!(err, Error::Unsupported(_)));
}
fn nest_in_arrays(leaf: Object, n: usize) -> Object {
let mut obj = leaf;
for _ in 0..n {
obj = Object::Array(vec![obj]);
}
obj
}
#[test]
fn renumber_refs_in_place_errors_on_excessive_nesting() {
let map = CatalogFirstRenumber {
old_to_new: HashMap::from([(ObjectRef::new(10, 0), ObjectRef::new(1, 0))]),
order: vec![ObjectRef::new(10, 0)],
};
let mut obj = nest_in_arrays(
Object::Reference(ObjectRef::new(10, 0)),
MAX_INLINE_DEPTH + 5,
);
let err = renumber_refs_in_place(&mut obj, &map).unwrap_err();
assert!(matches!(err, Error::Unsupported(_)));
}
#[test]
fn renumber_qpdf_refs_in_place_errors_on_excessive_nesting() {
let bytes = include_bytes!("../../../tests/fixtures/compat/one-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let map = CatalogFirstRenumber {
old_to_new: HashMap::from([(ObjectRef::new(10, 0), ObjectRef::new(1, 0))]),
order: vec![ObjectRef::new(10, 0)],
};
let mut obj = nest_in_arrays(
Object::Reference(ObjectRef::new(10, 0)),
MAX_INLINE_DEPTH + 5,
);
let err = renumber_qpdf_refs_in_place(&mut pdf, &mut obj, &map).unwrap_err();
assert!(matches!(err, Error::Unsupported(_)));
}
#[test]
fn collect_refs_errors_on_excessive_nesting() {
let obj = nest_in_arrays(
Object::Reference(ObjectRef::new(10, 0)),
MAX_INLINE_DEPTH + 5,
);
let err = collect_refs(&obj, 0, true, &mut |_| {}).unwrap_err();
assert!(matches!(err, Error::Unsupported(_)));
}
#[test]
fn collect_qpdf_enqueue_refs_errors_on_excessive_nesting() {
let bytes = include_bytes!("../../../tests/fixtures/compat/one-page.pdf");
let mut pdf = Pdf::open_mem(bytes).expect("open");
let obj = nest_in_arrays(
Object::Reference(ObjectRef::new(10, 0)),
MAX_INLINE_DEPTH + 5,
);
let mut found = Vec::new();
let err = collect_qpdf_enqueue_refs(&mut pdf, &obj, 0, true, &mut found).unwrap_err();
assert!(matches!(err, Error::Unsupported(_)));
}
#[test]
fn collect_refs_accepts_nesting_up_to_the_limit() {
let obj = nest_in_arrays(Object::Reference(ObjectRef::new(10, 0)), MAX_INLINE_DEPTH);
let mut collected: Vec<ObjectRef> = Vec::new();
collect_refs(&obj, 0, true, &mut |r| collected.push(r)).expect("within limit");
assert_eq!(collected, vec![ObjectRef::new(10, 0)]);
}
}