use std::collections::{BTreeSet, HashMap, VecDeque};
use std::io::{Read, Seek};
use crate::object_handle::MAX_INLINE_DEPTH;
use crate::object_ref::ObjectRef;
use crate::parser::MAX_PARSE_DEPTH;
use crate::writer::object_streams::ObjectStreamGroup;
use crate::Error;
use crate::Pdf;
use crate::XrefEntry;
pub(crate) type StreamParametersRemoved<'a> =
Option<&'a dyn Fn(&crate::ObjectHandle) -> crate::Result<bool>>;
pub(crate) trait NewNumberLookup {
fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef>;
}
impl NewNumberLookup for ObjectStreamRenumber {
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()
}
}
fn qpdf_source_objstm_containers<R: Read + Seek>(pdf: &Pdf<R>) -> BTreeSet<ObjectRef> {
pdf.source_xref_entries()
.into_values()
.filter_map(|entry| match entry {
XrefEntry::Compressed { stream, .. } => Some(ObjectRef::new(stream, 0)),
XrefEntry::Free { .. } | XrefEntry::Uncompressed { .. } => None,
})
.collect()
}
pub(crate) struct CanonicalCatalogFirstRenumber {
old_to_new: HashMap<ObjectRef, ObjectRef>,
order: Vec<ObjectRef>,
}
impl NewNumberLookup for CanonicalCatalogFirstRenumber {
fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.old_to_new.get(&original).copied()
}
}
impl CanonicalCatalogFirstRenumber {
pub(crate) fn len(&self) -> usize {
self.order.len()
}
pub(crate) fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.old_to_new.get(&original).copied()
}
pub(crate) fn pairs(&self) -> impl Iterator<Item = (ObjectRef, ObjectRef)> + '_ {
self.order
.iter()
.enumerate()
.map(|(index, &source)| (ObjectRef::new(index as u32 + 1, 0), source))
}
pub(crate) fn build_qpdf_with_stream_policy<R: Read + Seek>(
pdf: &mut Pdf<R>,
skip_length: bool,
preserve_unreferenced_objects: bool,
removed_refs: &BTreeSet<ObjectRef>,
stream_parameters_removed: StreamParametersRemoved<'_>,
) -> crate::Result<Self> {
let root_ref = pdf.root_ref();
let direct_root = if root_ref.is_none() {
let candidate = pdf.trailer_key_handle(b"Root");
if candidate.is_null() {
return Err(Error::Unsupported(
"plain rewrite: trailer has no /Root".to_string(),
));
}
Some(pdf.root_handle()?)
} else {
None
};
let mut seeds = if preserve_unreferenced_objects {
let mut seeds = Vec::new();
let source_objstm_containers = qpdf_source_objstm_containers(pdf);
for object_ref in pdf
.get_all_objects()?
.into_iter()
.filter_map(|handle| handle.object_ref())
{
if object_ref.number == 0
|| removed_refs.contains(&object_ref)
|| source_objstm_containers.contains(&object_ref)
{
continue;
}
seeds.push(object_ref);
}
seeds
} else {
Vec::new()
};
if let Some(root) = root_ref {
seeds.push(root);
} else if let Some(root) = &direct_root {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
root,
0,
skip_length,
&mut seeds,
stream_parameters_removed,
)?; }
let trailer = pdf.trailer();
let trailer_entries = trailer.try_as_dictionary()?.unwrap_or_default();
for (key, value) in trailer_entries {
if matches!(
key.as_slice(),
b"/ID" | b"/Encrypt" | b"/Prev" | b"/Root" | b"/Size"
) {
continue;
}
if !value.try_is_null()? {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
&value,
0,
skip_length,
&mut seeds,
stream_parameters_removed,
)?; }
}
let mut old_to_new = HashMap::new();
let mut order = Vec::new();
let mut queue = VecDeque::new();
for seed in seeds {
if !removed_refs.contains(&seed) {
enqueue(seed, &mut old_to_new, &mut order, &mut queue);
}
}
while let Some(source) = queue.pop_front() {
let handle = pdf.get_object_handle(source);
pdf.resolve(&handle)?;
let mut found = Vec::new();
collect_canonical_children_with_stream_policy(
pdf,
&handle,
0,
skip_length,
&mut found,
stream_parameters_removed,
)?;
for reference in found {
if !removed_refs.contains(&reference) {
enqueue(reference, &mut old_to_new, &mut order, &mut queue);
}
}
}
Ok(Self { old_to_new, order })
}
}
pub(crate) fn collect_canonical_enqueue_refs<R: Read + Seek>(
pdf: &mut Pdf<R>,
handle: &crate::ObjectHandle,
depth: usize,
skip_length: bool,
found: &mut Vec<ObjectRef>,
) -> crate::Result<()> {
collect_canonical_enqueue_refs_with_stream_policy(pdf, handle, depth, skip_length, found, None)
}
fn collect_canonical_enqueue_refs_with_stream_policy<R: Read + Seek>(
pdf: &mut Pdf<R>,
handle: &crate::ObjectHandle,
depth: usize,
skip_length: bool,
found: &mut Vec<ObjectRef>,
stream_parameters_removed: StreamParametersRemoved<'_>,
) -> crate::Result<()> {
if let Some(object_ref) = handle.object_ref() {
ensure_canonical_owner(pdf, handle)?;
if object_ref.number != 0 {
found.push(object_ref);
}
return Ok(());
}
collect_canonical_children_with_stream_policy(
pdf,
handle,
depth,
skip_length,
found,
stream_parameters_removed,
)
}
pub(crate) fn collect_canonical_children<R: Read + Seek>(
pdf: &mut Pdf<R>,
handle: &crate::ObjectHandle,
depth: usize,
skip_length: bool,
found: &mut Vec<ObjectRef>,
) -> crate::Result<()> {
collect_canonical_children_with_stream_policy(pdf, handle, depth, skip_length, found, None)
}
fn collect_canonical_children_with_stream_policy<R: Read + Seek>(
pdf: &mut Pdf<R>,
handle: &crate::ObjectHandle,
depth: usize,
skip_length: bool,
found: &mut Vec<ObjectRef>,
stream_parameters_removed: StreamParametersRemoved<'_>,
) -> crate::Result<()> {
if depth > MAX_PARSE_DEPTH {
return Err(Error::Unsupported(
"plain rewrite: inline object nesting exceeds MAX_PARSE_DEPTH during canonical enqueue collection"
.to_string(),
));
}
pdf.resolve(handle)?;
if let Some(items) = handle.try_as_array()? {
for item in items {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
&item,
depth + 1,
skip_length,
found,
stream_parameters_removed,
)?; }
return Ok(());
}
if let Some(entries) = handle.try_as_dictionary()? {
for (_, value) in entries {
if !value.try_is_null()? {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
&value,
depth + 1,
skip_length,
found,
stream_parameters_removed,
)?; }
}
return Ok(());
}
if let Some(stream_dict) = handle.as_stream_dict() {
pdf.resolve(&stream_dict)?;
let skip_stream_parameters = stream_parameters_removed
.map(|predicate| predicate(handle))
.transpose()?
.unwrap_or(false);
if let Some(entries) = stream_dict.try_as_dictionary()? {
for (key, value) in entries {
if skip_length && key.as_slice() == b"/Length" {
continue;
}
if skip_stream_parameters && matches!(key.as_slice(), b"/Filter" | b"/DecodeParms")
{
continue;
}
if !value.try_is_null()? {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
&value,
depth + 1,
skip_length,
found,
stream_parameters_removed,
)?; }
}
} }
Ok(())
}
fn ensure_canonical_owner<R: Read + Seek>(
pdf: &Pdf<R>,
handle: &crate::ObjectHandle,
) -> crate::Result<()> {
if !pdf.is_canonical_object_handle(handle) {
return Err(Error::Unsupported(
"QPDFObjectHandle from different QPDF found while writing".to_string(),
));
}
Ok(())
}
pub(crate) fn reachable_object_set_with_stream_parameters<R: Read + Seek>(
pdf: &mut Pdf<R>,
skip_length: bool,
skipped_stream_parameter_streams: &BTreeSet<ObjectRef>,
) -> 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 = pdf.trailer().try_as_dictionary()?.unwrap_or_default();
let skip_stream_parameters = |handle: &crate::ObjectHandle| -> crate::Result<bool> {
Ok(handle
.object_ref()
.is_some_and(|object_ref| skipped_stream_parameter_streams.contains(&object_ref)))
};
for (key, value) in trailer_entries {
if matches!(key.as_slice(), b"/ID" | b"/Prev" | b"/Root" | b"/Size") {
continue;
}
if !value.try_is_null()? {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
&value,
0,
skip_length,
&mut seeds,
Some(&skip_stream_parameters),
)?; }
}
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 handle = pdf.get_object_handle(cur);
pdf.resolve(&handle)?;
let mut found = Vec::new();
collect_canonical_children_with_stream_policy(
pdf,
&handle,
0,
skip_length,
&mut found,
Some(&skip_stream_parameters),
)?; 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 = pdf.trailer().try_as_dictionary()?.unwrap_or_default();
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();
let mut state = ResurrectableWalkState {
follow: &mut follow,
result: &mut result,
removed_refs,
};
walk_resurrectable_handle(&value, 0, false, true, &mut state)?;
queue.extend(follow);
}
while let Some(cur) = queue.pop_front() {
if !visited.insert(cur) {
continue;
}
let handle = pdf.get_object_handle(cur);
pdf.resolve(&handle)?;
let mut follow: Vec<ObjectRef> = Vec::new();
let mut state = ResurrectableWalkState {
follow: &mut follow,
result: &mut result,
removed_refs,
};
walk_resurrectable_handle(&handle, 0, false, false, &mut state)?;
for r in follow {
if !visited.contains(&r) {
queue.push_back(r);
}
}
}
Ok(result)
}
struct ResurrectableWalkState<'a> {
follow: &'a mut Vec<ObjectRef>,
result: &'a mut BTreeSet<ObjectRef>,
removed_refs: &'a BTreeSet<ObjectRef>,
}
fn walk_resurrectable_handle(
handle: &crate::ObjectHandle,
depth: usize,
in_array: bool,
edge_context: bool,
state: &mut ResurrectableWalkState<'_>,
) -> crate::Result<()> {
if depth > MAX_INLINE_DEPTH {
return Err(Error::Unsupported(
"linearization: inline nesting exceeds MAX_INLINE_DEPTH during resurrectable walk"
.to_string(),
));
}
let is_null = handle.try_is_null()?;
let edge_ref = edge_context.then_some(handle.object_ref()).flatten();
if is_null {
if in_array {
if let Some(reference) = edge_ref {
if reference.number > 0 && !state.removed_refs.contains(&reference) {
state.result.insert(reference);
}
}
}
return Ok(());
}
if let Some(reference) = edge_ref {
if reference.number > 0 {
state.follow.push(reference);
}
return Ok(());
}
if let Some(elements) = handle.try_as_array()? {
for element in elements {
walk_resurrectable_handle(&element, depth + 1, true, true, state)?;
}
return Ok(());
}
if let Some(entries) = handle.try_as_dictionary()? {
for (_key, value) in entries {
walk_resurrectable_handle(&value, depth + 1, false, true, state)?;
}
return Ok(());
}
if let Some(stream_dict) = handle.as_stream_dict() {
if let Some(entries) = stream_dict.try_as_dictionary()? {
for (_key, value) in entries {
walk_resurrectable_handle(&value, depth + 1, false, true, state)?;
}
}
}
Ok(())
}
pub(crate) struct ObjectStreamRenumber {
old_to_new: HashMap<ObjectRef, ObjectRef>,
container_new: Vec<Option<u32>>,
}
impl ObjectStreamRenumber {
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_with_stream_policy<R: Read + Seek>(
pdf: &mut Pdf<R>,
groups: &[ObjectStreamGroup],
skip_length: bool,
removed_refs: &BTreeSet<ObjectRef>,
preserve_unreferenced_objects: bool,
stream_parameters_removed: StreamParametersRemoved<'_>,
) -> crate::Result<Self> {
Self::build_with_seed_policy(
pdf,
groups,
skip_length,
removed_refs,
preserve_unreferenced_objects,
stream_parameters_removed,
)
}
fn build_with_seed_policy<R: Read + Seek>(
pdf: &mut Pdf<R>,
groups: &[ObjectStreamGroup],
skip_length: bool,
removed_refs: &BTreeSet<ObjectRef>,
preserve_unreferenced_objects: bool,
stream_parameters_removed: StreamParametersRemoved<'_>,
) -> crate::Result<Self> {
let mut member_to_group: HashMap<ObjectRef, usize> = HashMap::new();
let mut source_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.members().to_vec();
if sorted.is_empty() {
return Err(Error::Unsupported(format!(
"object-stream renumber: group {gi} has no members"
)));
}
sorted.sort_unstable_by_key(|r| (r.number, r.generation));
for &m in &sorted {
if let Some(previous) = member_to_group.insert(m, gi) {
return Err(Error::Unsupported(format!(
"object-stream renumber: member {m} occurs in groups {previous} and {gi}"
)));
}
}
if let ObjectStreamGroup::SourceBacked { source, .. } = group {
if let Some(previous) = source_to_group.insert(*source, gi) {
return Err(Error::Unsupported(format!(
"object-stream renumber: source container {source} occurs in groups {previous} and {gi}"
)));
}
}
groups_sorted.push(sorted);
}
if let Some(source) = source_to_group
.keys()
.find(|source| member_to_group.contains_key(source))
{
return Err(Error::Unsupported(format!(
"object-stream renumber: source container {source} is also a member"
)));
}
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<RenumberWork> = VecDeque::new();
let root_ref = pdf.root_ref();
let direct_root = if root_ref.is_none() {
let candidate = pdf.trailer_key_handle(b"Root");
if candidate.is_null() {
return Err(Error::Unsupported(
"object-stream renumber: trailer has no /Root".to_string(),
));
}
Some(pdf.root_handle()?)
} else {
None
};
let mut seeds: Vec<ObjectRef> = if preserve_unreferenced_objects {
pdf.live_object_refs()
.into_iter()
.filter(|object_ref| !removed_refs.contains(object_ref))
.collect()
} else {
Vec::new()
};
if let Some(root) = root_ref {
seeds.push(root);
} else if let Some(root) = &direct_root {
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
root,
0,
skip_length,
&mut seeds,
stream_parameters_removed,
)?; } let trailer = pdf.trailer();
let trailer_entries = trailer.try_as_dictionary()?.unwrap_or_default();
for (key, value) in trailer_entries {
if matches!(
key.as_slice(),
b"/ID" | b"/Encrypt" | b"/Prev" | b"/Root" | b"/Size"
) {
continue;
}
if value.try_is_null()? {
continue;
}
collect_canonical_enqueue_refs_with_stream_policy(
pdf,
&value,
0,
skip_length,
&mut seeds,
stream_parameters_removed,
)?; }
seeds.retain(|reference| !removed_refs.contains(reference));
for seed in seeds {
enqueue_object_stream(
seed,
groups,
&member_to_group,
&source_to_group,
&groups_sorted,
&mut old_to_new,
&mut container_new,
&mut next,
&mut queue,
);
}
while let Some(work) = queue.pop_front() {
match work {
RenumberWork::Ordinary(cur) => {
let handle = pdf.get_object_handle(cur);
pdf.resolve(&handle)?;
let mut found = Vec::new();
collect_canonical_children_with_stream_policy(
pdf,
&handle,
0,
skip_length,
&mut found,
stream_parameters_removed,
)?; found.retain(|reference| !removed_refs.contains(reference));
for reference in found {
enqueue_object_stream(
reference,
groups,
&member_to_group,
&source_to_group,
&groups_sorted,
&mut old_to_new,
&mut container_new,
&mut next,
&mut queue,
);
}
}
RenumberWork::SourceContainer(source) => {
if removed_refs.contains(&source) {
continue;
}
let handle = pdf.get_object_handle(source);
pdf.resolve(&handle)?;
if handle.is_null() {
continue;
}
let stream_dict = handle.as_stream_dict().ok_or_else(|| {
Error::Unsupported(format!(
"object-stream renumber: source container {source} is not a stream"
))
})?;
let extends = stream_dict.try_get_key(b"/Extends")?.object_ref();
if let Some(extends) = extends.filter(|extends| !removed_refs.contains(extends))
{
enqueue_object_stream(
extends,
groups,
&member_to_group,
&source_to_group,
&groups_sorted,
&mut old_to_new,
&mut container_new,
&mut next,
&mut queue,
);
}
}
}
}
Ok(Self {
old_to_new,
container_new,
})
}
}
#[derive(Clone, Copy, Debug)]
enum RenumberWork {
Ordinary(ObjectRef),
SourceContainer(ObjectRef),
}
#[allow(clippy::too_many_arguments)]
fn enqueue_object_stream(
r: ObjectRef,
groups: &[ObjectStreamGroup],
member_to_group: &HashMap<ObjectRef, usize>,
source_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<RenumberWork>,
) {
if old_to_new.contains_key(&r) {
return;
}
let group_index = member_to_group
.get(&r)
.or_else(|| source_to_group.get(&r))
.copied();
match group_index {
Some(gi) => {
let container = *next;
container_new[gi] = Some(container);
*next += 1;
let source = match &groups[gi] {
ObjectStreamGroup::SourceBacked { source, .. } => {
old_to_new.insert(*source, ObjectRef::new(container, 0));
Some(*source)
}
ObjectStreamGroup::Synthetic { .. } => None,
};
for &m in &groups_sorted[gi] {
old_to_new.insert(m, ObjectRef::new(*next, 0));
*next += 1;
queue.push_back(RenumberWork::Ordinary(m));
}
if let Some(source) = source {
queue.push_back(RenumberWork::SourceContainer(source));
}
}
None => {
old_to_new.insert(r, ObjectRef::new(*next, 0));
*next += 1;
queue.push_back(RenumberWork::Ordinary(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);
}