use crate::nntree::NameTree;
use crate::outline_object_helper::{OutlineId, OutlineItem, OutlineTree};
use crate::{ObjectHandle, ObjectRef, Pdf, Result};
use std::collections::BTreeSet;
use std::io::{Read, Seek};
const QPDF_MAX_EXPANDED_OUTLINE_DEPTH: usize = 50;
fn object_key(object: &ObjectHandle, key: &[u8]) -> Result<Option<ObjectHandle>> {
let value = object.try_get_key(key)?;
if value.try_is_null()? {
Ok(None)
} else {
Ok(Some(value))
}
}
fn mark_direct_sibling_seen(direct_seen: &mut Vec<ObjectHandle>, current: &ObjectHandle) -> bool {
if !current.is_direct() {
return true;
}
if direct_seen
.iter()
.any(|handle: &ObjectHandle| handle.is_same_object_as(current))
{
return false;
}
direct_seen.push(current.clone());
true
}
#[derive(Default)]
struct SiblingSeen {
seen: BTreeSet<ObjectRef>,
direct_seen: Vec<ObjectHandle>,
}
pub struct OutlineDocumentHelper<'a, R: Read + Seek + 'static> {
pdf: &'a mut Pdf<R>,
dest_dict: Option<ObjectHandle>,
names_dest: Option<NameTree>,
}
impl<'a, R: Read + Seek> OutlineDocumentHelper<'a, R> {
pub fn new(pdf: &'a mut Pdf<R>) -> Self {
Self {
pdf,
dest_dict: None,
names_dest: None,
}
}
pub fn has_outlines(&mut self) -> Result<bool> {
let Some(outlines) = self.catalog_outlines()? else {
return Ok(false);
};
self.pdf.resolve(&outlines)?;
if outlines.try_as_dictionary()?.is_none() {
return Ok(false);
}
if !outlines.try_has_key(b"/First")? {
return Ok(false);
}
let first = outlines.try_get_key(b"/First")?;
let first = self.resolve_value_handle(first)?;
Ok(!first.try_is_null()?)
}
pub(crate) fn resolve_handle(&mut self, handle: &ObjectHandle) -> Result<()> {
self.pdf.resolve(handle)
}
pub(crate) fn resolve_value_handle(&mut self, handle: ObjectHandle) -> Result<ObjectHandle> {
self.pdf.resolve_handle(&handle)
}
fn chase_and_mark_seen(
&mut self,
cursor: ObjectHandle,
seen: &mut SiblingSeen,
) -> Result<Option<ObjectHandle>> {
let cursor = self.resolve_value_handle(cursor)?;
if let Some(reference) = cursor.object_ref() {
if !seen.seen.insert(reference) {
return Ok(None);
}
} else if !mark_direct_sibling_seen(&mut seen.direct_seen, &cursor) {
return Ok(None);
}
Ok(Some(cursor))
}
fn catalog_handle(&mut self) -> Result<Option<ObjectHandle>> {
let Some(catalog_ref) = self.pdf.root_ref() else {
return Ok(None);
};
let catalog = self.pdf.get_object_handle(catalog_ref);
self.resolve_handle(&catalog)?;
if catalog.try_as_dictionary()?.is_none() {
return Ok(None);
}
Ok(Some(catalog))
}
fn catalog_outlines(&mut self) -> Result<Option<ObjectHandle>> {
let Some(catalog) = self.catalog_handle()? else {
return Ok(None);
};
if !catalog.try_has_key(b"/Outlines")? {
return Ok(None);
}
Ok(Some(catalog.try_get_key(b"/Outlines")?))
}
pub fn get_tree(&mut self) -> Result<OutlineTree> {
let mut tree = OutlineTree::new();
let Some(outlines) = self.catalog_outlines()? else {
return Ok(tree);
};
self.resolve_handle(&outlines)?;
if outlines.try_as_dictionary()?.is_none() {
return Ok(tree);
}
if !outlines.try_has_key(b"/First")? {
return Ok(tree);
}
let first = outlines.try_get_key(b"/First")?;
let first = self.resolve_value_handle(first)?;
if first.try_is_null()? {
return Ok(tree);
}
let mut cursor = first;
let mut top_level_seen = SiblingSeen::default();
let mut constructor_seen = BTreeSet::new();
loop {
let Some(chased) = self.chase_and_mark_seen(cursor, &mut top_level_seen)? else {
break;
};
let Some(id) = self.build_item(chased, None, &mut tree, &mut constructor_seen)? else {
break;
};
tree.roots.push(id);
let Some(next) = object_key(&tree[id].object, b"/Next")? else {
break;
};
cursor = next;
}
Ok(tree)
}
fn build_item(
&mut self,
cursor: ObjectHandle,
parent: Option<OutlineId>,
tree: &mut OutlineTree,
constructor_seen: &mut BTreeSet<ObjectRef>,
) -> Result<Option<OutlineId>> {
let Some(root) = self.materialize_item(cursor, parent, tree)? else {
return Ok(None);
};
if let Some(reference) = tree[root].source_ref {
if !constructor_seen.insert(reference) {
return Ok(Some(root));
}
}
struct Frame {
owner: OutlineId,
next: Option<ObjectHandle>,
depth: usize,
seen: SiblingSeen,
}
let mut frames = Vec::new();
let first = object_key(&tree[root].object, b"/First")?;
if first.is_some() {
frames.push(Frame {
owner: root,
next: first,
depth: 2,
seen: SiblingSeen::default(),
});
}
while !frames.is_empty() {
let next_cursor = frames.last_mut().and_then(|frame| frame.next.take());
let Some(cursor) = next_cursor else {
frames.pop();
continue;
};
let (owner, child_depth, chased) = {
let frame = frames
.last_mut()
.expect("outline construction frame exists");
let owner = frame.owner;
let child_depth = frame.depth;
let chased = self.chase_and_mark_seen(cursor, &mut frame.seen)?;
(owner, child_depth, chased)
};
let Some(cursor) = chased else {
frames
.last_mut()
.expect("outline construction frame exists")
.next = None;
continue;
};
let Some(child) = self.materialize_item(cursor, Some(owner), tree)? else {
continue;
};
tree.items[owner.0].kids.push(child);
let expand_child = if child_depth > QPDF_MAX_EXPANDED_OUTLINE_DEPTH {
false
} else if let Some(reference) = tree[child].source_ref {
constructor_seen.insert(reference)
} else {
true
};
frames
.last_mut()
.expect("outline construction frame exists")
.next = object_key(&tree[child].object, b"/Next")?;
if expand_child {
let first = object_key(&tree[child].object, b"/First")?;
if first.is_some() {
frames.push(Frame {
owner: child,
next: first,
depth: child_depth + 1,
seen: SiblingSeen::default(),
});
}
}
}
Ok(Some(root))
}
fn materialize_item(
&mut self,
cursor: ObjectHandle,
parent: Option<OutlineId>,
tree: &mut OutlineTree,
) -> Result<Option<OutlineId>> {
let cursor = self.resolve_value_handle(cursor)?;
let source_ref = cursor.object_ref();
if cursor.try_is_null()? {
return Ok(None);
}
let id = OutlineId(tree.items.len());
tree.items.push(OutlineItem {
source_ref,
parent,
kids: Vec::new(),
object: cursor,
});
Ok(Some(id))
}
fn cached_dest_dict(&mut self) -> Result<ObjectHandle> {
if let Some(dests) = &self.dest_dict {
return Ok(dests.clone());
}
let dests = match self.catalog_value_handle(b"/Dests")? {
Some(dests) => self.resolve_value_handle(dests)?,
None => ObjectHandle::null(),
};
self.dest_dict = Some(dests.clone());
Ok(dests)
}
fn resolve_named_dest_by_name(&mut self, name: &[u8]) -> Result<Option<ObjectHandle>> {
let dests = self.cached_dest_dict()?;
if dests.try_as_dictionary()?.is_none() {
return Ok(None);
}
let mut key = Vec::with_capacity(name.len() + 1);
key.push(b'/');
key.extend_from_slice(name);
if !dests.try_has_key(&key)? {
return Ok(None);
}
let value = dests.try_get_key(&key)?;
Ok(Some(self.resolve_value_handle(value)?))
}
fn resolve_named_dest_by_string(&mut self, bytes: &[u8]) -> Result<Option<ObjectHandle>> {
let lookup =
crate::pdf_string::normalized_utf8_value(&crate::pdf_string::utf8_value(bytes));
if self.names_dest.is_none() {
let Some(names) = self.catalog_value_handle(b"/Names")? else {
return Ok(None);
};
let names = self.resolve_value_handle(names)?;
if names.try_as_dictionary()?.is_none() || !names.try_has_key(b"/Dests")? {
return Ok(None);
}
let root = names.try_get_key(b"/Dests")?;
let root = self.resolve_value_handle(root)?;
if root.try_as_dictionary()?.is_none() {
return Ok(None);
}
self.names_dest = Some(NameTree::new(root, true));
}
let tree = self
.names_dest
.as_mut()
.expect("populated by the check above");
let found = tree.find_object(&mut *self.pdf, lookup.as_slice())?;
found
.map(|value| self.resolve_value_handle(value))
.transpose()
}
pub(crate) fn resolve_named_dest(&mut self, name: ObjectHandle) -> Result<ObjectHandle> {
let found = if let Some(name_bytes) = name.try_as_name()? {
self.resolve_named_dest_by_name(&name_bytes)?
} else if let Some(bytes) = name.as_string() {
self.resolve_named_dest_by_string(&bytes)?
} else {
None
};
Ok(found.unwrap_or_else(ObjectHandle::null))
}
fn catalog_value_handle(&mut self, key: &[u8]) -> Result<Option<ObjectHandle>> {
let Some(catalog) = self.catalog_handle()? else {
return Ok(None);
};
if !catalog.try_has_key(key)? {
return Ok(None);
}
Ok(Some(catalog.try_get_key(key)?))
}
}
impl<R: Read + Seek> Pdf<R> {
pub fn outline(&mut self) -> OutlineDocumentHelper<'_, R> {
OutlineDocumentHelper::new(self)
}
}
#[cfg(test)]
mod tests {
use super::mark_direct_sibling_seen;
use crate::{ObjectHandle, ObjectRef, Pdf};
use std::io::Cursor;
fn minimal_pdf_bytes() -> Vec<u8> {
let mut pdf = Vec::new();
pdf.extend_from_slice(b"%PDF-1.4\n");
let off1 = pdf.len();
pdf.extend_from_slice(b"1 0 obj\n<< /Type /Catalog /Pages 2 0 R >>\nendobj\n");
let off2 = pdf.len();
pdf.extend_from_slice(b"2 0 obj\n<< /Type /Pages /Kids [] /Count 0 >>\nendobj\n");
let xref_start = pdf.len();
pdf.extend_from_slice(
format!("xref\n0 3\n0000000000 65535 f \n{off1:010} 00000 n \n{off2:010} 00000 n \n")
.as_bytes(),
);
pdf.extend_from_slice(
format!("trailer\n<< /Size 3 /Root 1 0 R >>\nstartxref\n{xref_start}\n%%EOF\n")
.as_bytes(),
);
pdf
}
#[test]
fn resolve_named_dest_returns_null_for_a_non_name_non_string_candidate() {
let mut pdf = Pdf::open(Cursor::new(minimal_pdf_bytes())).unwrap();
let mut helper = pdf.outline();
let resolved = helper
.resolve_named_dest(ObjectHandle::integer(42))
.unwrap();
assert!(
resolved.try_is_null().unwrap(),
"a non-name, non-string candidate must resolve to null"
);
}
#[test]
fn direct_sibling_seen_set_ignores_indirect_handles_and_tracks_direct_identity() {
let mut direct_seen = Vec::new();
let indirect = ObjectHandle::new_indirect_unresolved(ObjectRef::new(10, 0), -1);
assert!(mark_direct_sibling_seen(&mut direct_seen, &indirect));
assert!(mark_direct_sibling_seen(&mut direct_seen, &indirect));
assert!(direct_seen.is_empty());
let direct = ObjectHandle::dictionary(Vec::new());
assert!(mark_direct_sibling_seen(&mut direct_seen, &direct));
assert!(!mark_direct_sibling_seen(&mut direct_seen, &direct));
let other_direct = ObjectHandle::dictionary(Vec::new());
assert!(mark_direct_sibling_seen(&mut direct_seen, &other_direct));
}
}