pdf_oxide 0.3.59

//! PDF document outline (bookmarks) support.
//!
//! Provides access to the PDF document outline, also known as bookmarks,
//! which allow users to navigate a PDF document.

use crate::document::PdfDocument;
use crate::error::{Error, Result};
use crate::object::Object;

/// A single outline item (bookmark) in the document hierarchy.
#[derive(Debug, Clone)]
pub struct OutlineItem {
    /// The title of this bookmark
    pub title: String,

    /// The destination (page number or named destination)
    /// None if destination cannot be determined
    pub dest: Option<Destination>,

    /// Child bookmarks under this item
    pub children: Vec<OutlineItem>,
}

/// Destination in the PDF
#[derive(Debug, Clone)]
pub enum Destination {
    /// Direct page reference (page index, 0-based)
    PageIndex(usize),

    /// Named destination (string identifier)
    Named(String),
}

impl PdfDocument {
    /// Get the document outline (bookmarks) if present.
    ///
    /// Returns a hierarchical structure of bookmarks that can be used
    /// for document navigation.
    ///
    /// # Returns
    ///
    /// - `Ok(Some(Vec<OutlineItem>))` - Bookmarks found and parsed
    /// - `Ok(None)` - No bookmarks in document
    /// - `Err` - Error parsing bookmarks
    ///
    /// # Example
    ///
    /// ```no_run
    /// use pdf_oxide::PdfDocument;
    ///
    /// let mut doc = PdfDocument::open("sample.pdf")?;
    /// if let Some(outline) = doc.get_outline()? {
    ///     for item in outline {
    ///         println!("Bookmark: {}", item.title);
    ///     }
    /// }
    /// # Ok::<(), pdf_oxide::error::Error>(())
    /// ```
    pub fn get_outline(&self) -> Result<Option<Vec<OutlineItem>>> {
        // Get catalog
        let catalog = self.catalog()?;

        // Check if catalog has /Outlines entry
        let outlines_ref = match catalog.as_dict() {
            Some(dict) => match dict.get("Outlines") {
                Some(Object::Reference(obj_ref)) => *obj_ref,
                _ => return Ok(None),
            },
            None => return Ok(None),
        };

        // Load the outlines dictionary
        let outlines_dict = self.load_object(outlines_ref)?;

        // Get the first outline item
        let first_ref = match outlines_dict.as_dict() {
            Some(dict) => match dict.get("First") {
                Some(Object::Reference(obj_ref)) => *obj_ref,
                _ => return Ok(None),
            },
            None => return Ok(None),
        };

        // Parse outline items at root level
        let mut items = Vec::new();
        let mut current_ref = Some(first_ref);

        while let Some(item_ref) = current_ref {
            if let Ok(item) = self.parse_outline_item(item_ref) {
                items.push(item);
            }

            // Get next sibling
            let item_obj = self.load_object(item_ref)?;
            current_ref = match item_obj.as_dict() {
                Some(dict) => match dict.get("Next") {
                    Some(Object::Reference(obj_ref)) => Some(*obj_ref),
                    _ => None,
                },
                None => None,
            };
        }

        if items.is_empty() {
            Ok(None)
        } else {
            Ok(Some(items))
        }
    }

    /// Parse a single outline item and its children recursively.
    fn parse_outline_item(&self, item_ref: crate::object::ObjectRef) -> Result<OutlineItem> {
        let item_obj = self.load_object(item_ref)?;

        // Extract title
        let title = match item_obj.as_dict() {
            Some(dict) => match dict.get("Title") {
                Some(Object::String(s)) => String::from_utf8_lossy(s).to_string(),
                _ => "(No Title)".to_string(),
            },
            None => "(No Title)".to_string(),
        };

        // Extract destination
        let dest = self.parse_outline_destination(&item_obj)?;

        // Parse children if present
        let mut children = Vec::new();
        if let Some(dict) = item_obj.as_dict() {
            if let Some(Object::Reference(first_child_ref)) = dict.get("First") {
                let mut child_ref = Some(*first_child_ref);

                while let Some(c_ref) = child_ref {
                    if let Ok(child) = self.parse_outline_item(c_ref) {
                        children.push(child);
                    }

                    // Get next sibling
                    let child_obj = self.load_object(c_ref)?;
                    child_ref = match child_obj.as_dict() {
                        Some(dict) => match dict.get("Next") {
                            Some(Object::Reference(obj_ref)) => Some(*obj_ref),
                            _ => None,
                        },
                        None => None,
                    };
                }
            }
        }

        Ok(OutlineItem {
            title,
            dest,
            children,
        })
    }

    /// Parse destination from an outline item.
    fn parse_outline_destination(&self, item: &Object) -> Result<Option<Destination>> {
        let dict = match item.as_dict() {
            Some(d) => d,
            None => return Ok(None),
        };

        // Try /Dest entry first
        if let Some(dest_obj) = dict.get("Dest") {
            return self.resolve_destination(dest_obj);
        }

        // Try /A (action) entry
        let mut action = dict.get("A");

        // Resolve indirect reference to action
        let obj;
        if let Some(Object::Reference(obj_ref)) = action {
            obj = self.load_object(*obj_ref)?;
            action = Some(&obj);
        }

        // Look for destination under /D key
        if let Some(Object::Dictionary(action)) = action {
            if let Some(dest_obj) = action.get("D") {
                return self.resolve_destination(dest_obj);
            }
        }

        Ok(None)
    }

    /// Resolve a *named* destination (PDF 1.1 catalog `/Dests` dict, or
    /// PDF 1.2+ `/Names` → `/Dests` name tree, ISO 32000-1 §12.3.2.3 /
    /// §7.9.6) to a 0-based page index. `Ok(None)` when the name is
    /// genuinely unresolvable (caller keeps [`Destination::Named`]).
    pub(crate) fn resolve_named_destination(&self, name: &str) -> Result<Option<usize>> {
        let catalog = self.catalog()?;
        let Some(cat) = catalog.as_dict() else {
            return Ok(None);
        };
        let resolve = |r: crate::object::ObjectRef| self.load_object(r).ok();
        let Some(dest) = lookup_named_dest(cat, name.as_bytes(), &resolve, 0) else {
            return Ok(None);
        };
        // The found value is a dest array (or was already normalised
        // from a `<< /D [...] >>` wrapper). Reuse the array path.
        match self.resolve_destination(&dest)? {
            Some(Destination::PageIndex(i)) => Ok(Some(i)),
            _ => Ok(None),
        }
    }

    /// Resolve a destination object to a Destination enum.
    fn resolve_destination(&self, dest_obj: &Object) -> Result<Option<Destination>> {
        match dest_obj {
            // Named destination — a byte string (`/Dest (name)`) or a
            // name object (`/Dest /name`). Resolve via the catalog
            // /Dests dict / /Names name tree; fall back to the
            // unresolved name for backward compatibility (the
            // `bookmarks` JSON still prints names when unresolvable).
            Object::String(name) => {
                let s = String::from_utf8_lossy(name).to_string();
                match self.resolve_named_destination(&s)? {
                    Some(idx) => Ok(Some(Destination::PageIndex(idx))),
                    None => Ok(Some(Destination::Named(s))),
                }
            },
            Object::Name(name) => match self.resolve_named_destination(name)? {
                Some(idx) => Ok(Some(Destination::PageIndex(idx))),
                None => Ok(Some(Destination::Named(name.clone()))),
            },

            // Direct destination (array)
            Object::Array(arr) if !arr.is_empty() => {
                // First element is page reference
                match &arr[0] {
                    Object::Reference(page_ref) => {
                        // Try to find which page this is
                        if let Ok(page_index) = self.find_page_index(*page_ref) {
                            Ok(Some(Destination::PageIndex(page_index)))
                        } else {
                            Ok(None)
                        }
                    },
                    _ => Ok(None),
                }
            },

            // Indirect reference to destination
            Object::Reference(dest_ref) => {
                let resolved = self.load_object(*dest_ref)?;
                self.resolve_destination(&resolved)
            },

            _ => Ok(None),
        }
    }

    /// Find the page index for a given page object reference.
    fn find_page_index(&self, page_ref: crate::object::ObjectRef) -> Result<usize> {
        // Single tree walk; otherwise per-call get_page_ref(i) is O(n) and the
        // outer loop becomes O(n²) — outlines with many bookmarks turn into n³.
        let refs = self.all_page_refs()?;
        refs.iter()
            .position(|r| *r == page_ref)
            .ok_or_else(|| Error::InvalidPdf(format!("Page reference {:?} not found", page_ref)))
    }
}

/// Max name-tree descent — guards malformed/cyclic `/Kids` trees from
/// unbounded recursion (foundation §6.3 untrusted-input limits).
const NAME_TREE_MAX_DEPTH: u8 = 32;

/// Follow one level of indirection. Pure given `resolve`.
fn deref_obj(
    o: &Object,
    resolve: &dyn Fn(crate::object::ObjectRef) -> Option<Object>,
) -> Option<Object> {
    match o {
        Object::Reference(r) => resolve(*r),
        other => Some(other.clone()),
    }
}

/// A name-tree / `/Dests` value is either the destination **array**
/// directly, or a dictionary with a `/D` entry holding it
/// (ISO 32000-1 §12.3.2.3). Normalise to the array object.
fn normalize_dest_value(
    v: &Object,
    resolve: &dyn Fn(crate::object::ObjectRef) -> Option<Object>,
) -> Option<Object> {
    let v = deref_obj(v, resolve)?;
    if let Some(d) = v.as_dict() {
        if let Some(inner) = d.get("D") {
            return deref_obj(inner, resolve);
        }
    }
    if v.as_array().is_some() {
        return Some(v);
    }
    None
}

/// Walk a name-tree node (`/Names` leaf or `/Kids` intermediate),
/// `/Limits`-guided per ISO 32000-1 §7.9.6. Pure given `resolve`.
fn walk_name_tree(
    node: &Object,
    target: &[u8],
    resolve: &dyn Fn(crate::object::ObjectRef) -> Option<Object>,
    depth: u8,
) -> Option<Object> {
    if depth > NAME_TREE_MAX_DEPTH {
        return None;
    }
    let node = deref_obj(node, resolve)?;
    let dict = node.as_dict()?;

    // Leaf: `/Names` is a flat [key1 val1 key2 val2 …] array.
    if let Some(names) = dict.get("Names").and_then(|n| {
        deref_obj(n, resolve).and_then(|d| {
            if d.as_array().is_some() {
                Some(d)
            } else {
                None
            }
        })
    }) {
        let arr = names.as_array().expect("checked array above");
        let mut i = 0;
        while i + 1 < arr.len() {
            if arr[i].as_string() == Some(target) {
                return normalize_dest_value(&arr[i + 1], resolve);
            }
            i += 2;
        }
        // A pure-leaf node with no match is terminal.
        if !dict.contains_key("Kids") {
            return None;
        }
    }

    // Intermediate: `/Kids` are child node refs; `/Limits [lo hi]`
    // (byte strings) bracket each child's key range.
    if let Some(kids) = dict
        .get("Kids")
        .and_then(|k| deref_obj(k, resolve))
        .and_then(|k| {
            if k.as_array().is_some() {
                Some(k)
            } else {
                None
            }
        })
    {
        for kid in kids.as_array().expect("checked array above") {
            let Some(kid_node) = deref_obj(kid, resolve) else {
                continue;
            };
            let in_range = match kid_node.as_dict().and_then(|d| d.get("Limits")) {
                Some(lim) => match deref_obj(lim, resolve).as_ref().and_then(Object::as_array) {
                    Some(l) if l.len() == 2 => match (l[0].as_string(), l[1].as_string()) {
                        (Some(lo), Some(hi)) => lo <= target && target <= hi,
                        // Malformed Limits → search the kid anyway (robust).
                        _ => true,
                    },
                    _ => true,
                },
                None => true,
            };
            if in_range {
                if let Some(found) = walk_name_tree(&kid_node, target, resolve, depth + 1) {
                    return Some(found);
                }
            }
        }
    }
    None
}

/// Resolve `target` to its destination object via the catalog
/// `/Dests` dictionary (PDF 1.1) then the `/Names` → `/Dests` name
/// tree (PDF 1.2+). Pure given `resolve`; bounded; returns the
/// normalised destination array object, or `None`.
fn lookup_named_dest(
    catalog: &std::collections::HashMap<String, Object>,
    target: &[u8],
    resolve: &dyn Fn(crate::object::ObjectRef) -> Option<Object>,
    depth: u8,
) -> Option<Object> {
    // Step A — catalog /Dests (a name→dest *dictionary*, PDF 1.1).
    if let Some(dests) = catalog.get("Dests").and_then(|d| deref_obj(d, resolve)) {
        if let Some(dd) = dests.as_dict() {
            let key = String::from_utf8_lossy(target);
            if let Some(v) = dd.get(key.as_ref()) {
                if let Some(found) = normalize_dest_value(v, resolve) {
                    return Some(found);
                }
            }
        }
    }
    // Step B — catalog /Names → /Dests name tree (PDF 1.2+).
    let names = catalog.get("Names").and_then(|n| deref_obj(n, resolve))?;
    let root = names
        .as_dict()?
        .get("Dests")
        .and_then(|d| deref_obj(d, resolve))?;
    walk_name_tree(&root, target, resolve, depth)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashMap;

    fn s(b: &str) -> Object {
        Object::String(b.as_bytes().to_vec())
    }
    fn arr_dest(page_obj: u32) -> Object {
        Object::Array(vec![
            Object::Reference(crate::object::ObjectRef::new(page_obj, 0)),
            Object::Name("Fit".to_string()),
        ])
    }
    fn no_resolve() -> impl Fn(crate::object::ObjectRef) -> Option<Object> {
        |_r| None
    }

    #[test]
    fn test_outline_item_creation() {
        let item = OutlineItem {
            title: "Chapter 1".to_string(),
            dest: Some(Destination::PageIndex(0)),
            children: vec![],
        };

        assert_eq!(item.title, "Chapter 1");
        assert!(matches!(item.dest, Some(Destination::PageIndex(0))));
        assert!(item.children.is_empty());
    }

    #[test]
    fn test_outline_hierarchy() {
        let child = OutlineItem {
            title: "Section 1.1".to_string(),
            dest: Some(Destination::PageIndex(1)),
            children: vec![],
        };

        let parent = OutlineItem {
            title: "Chapter 1".to_string(),
            dest: Some(Destination::PageIndex(0)),
            children: vec![child],
        };

        assert_eq!(parent.children.len(), 1);
        assert_eq!(parent.children[0].title, "Section 1.1");
    }

    // ---- pure named-destination resolver (#482) -------------------

    /// Catalog `/Dests` dict, value is the destination array directly.
    #[test]
    fn dests_dict_direct_array() {
        let mut dests = HashMap::new();
        dests.insert("chap1".to_string(), arr_dest(7));
        let mut cat = HashMap::new();
        cat.insert("Dests".to_string(), Object::Dictionary(dests));
        let r = no_resolve();
        let got = lookup_named_dest(&cat, b"chap1", &r, 0).expect("found");
        assert_eq!(got.as_array().unwrap()[0].as_reference().unwrap().id, 7);
        assert!(lookup_named_dest(&cat, b"missing", &r, 0).is_none());
    }

    /// `/Dests` value is a `<< /D [...] >>` wrapper (must unwrap /D).
    #[test]
    fn dests_dict_d_wrapper() {
        let mut inner = HashMap::new();
        inner.insert("D".to_string(), arr_dest(9));
        let mut dests = HashMap::new();
        dests.insert("c".to_string(), Object::Dictionary(inner));
        let mut cat = HashMap::new();
        cat.insert("Dests".to_string(), Object::Dictionary(dests));
        let got = lookup_named_dest(&cat, b"c", &no_resolve(), 0).expect("found");
        assert_eq!(got.as_array().unwrap()[0].as_reference().unwrap().id, 9);
    }

    /// `/Names` → `/Dests` flat-`/Names`-array leaf.
    #[test]
    fn names_tree_flat_leaf() {
        let dests_root = Object::Dictionary(HashMap::from([(
            "Names".to_string(),
            Object::Array(vec![
                s("a"),
                arr_dest(1),
                s("b"),
                arr_dest(4),
                s("c"),
                arr_dest(6),
            ]),
        )]));
        let names = Object::Dictionary(HashMap::from([("Dests".to_string(), dests_root)]));
        let cat = HashMap::from([("Names".to_string(), names)]);
        let r = no_resolve();
        assert_eq!(
            lookup_named_dest(&cat, b"b", &r, 0)
                .unwrap()
                .as_array()
                .unwrap()[0]
                .as_reference()
                .unwrap()
                .id,
            4
        );
        assert!(lookup_named_dest(&cat, b"z", &r, 0).is_none());
    }

    /// `/Kids` intermediate node with `/Limits`-guided descent, the
    /// child nodes reached through indirect references (exercises the
    /// injected `resolve`).
    #[test]
    fn names_tree_kids_with_limits_and_indirection() {
        use crate::object::ObjectRef;
        // obj 100 = left leaf [a,b], obj 101 = right leaf [m,z]
        let leaf_l = Object::Dictionary(HashMap::from([
            ("Limits".to_string(), Object::Array(vec![s("a"), s("b")])),
            (
                "Names".to_string(),
                Object::Array(vec![s("a"), arr_dest(1), s("b"), arr_dest(2)]),
            ),
        ]));
        let leaf_r = Object::Dictionary(HashMap::from([
            ("Limits".to_string(), Object::Array(vec![s("m"), s("z")])),
            (
                "Names".to_string(),
                Object::Array(vec![s("m"), arr_dest(3), s("z"), arr_dest(4)]),
            ),
        ]));
        let resolve = move |rf: ObjectRef| match rf.id {
            100 => Some(leaf_l.clone()),
            101 => Some(leaf_r.clone()),
            _ => None,
        };
        let root = Object::Dictionary(HashMap::from([(
            "Kids".to_string(),
            Object::Array(vec![
                Object::Reference(ObjectRef::new(100, 0)),
                Object::Reference(ObjectRef::new(101, 0)),
            ]),
        )]));
        let names = Object::Dictionary(HashMap::from([("Dests".to_string(), root)]));
        let cat = HashMap::from([("Names".to_string(), names)]);
        assert_eq!(
            lookup_named_dest(&cat, b"z", &resolve, 0)
                .unwrap()
                .as_array()
                .unwrap()[0]
                .as_reference()
                .unwrap()
                .id,
            4
        );
        assert_eq!(
            lookup_named_dest(&cat, b"a", &resolve, 0)
                .unwrap()
                .as_array()
                .unwrap()[0]
                .as_reference()
                .unwrap()
                .id,
            1
        );
        // Out of every child's Limits → not found, no panic.
        assert!(lookup_named_dest(&cat, b"c", &resolve, 0).is_none());
    }

    /// Cyclic `/Kids` must terminate via the depth guard (no panic /
    /// stack overflow) — adversarial-input safety (foundation §6.3).
    #[test]
    fn names_tree_cyclic_kids_is_bounded() {
        use crate::object::ObjectRef;
        // obj 200's Kids points back at obj 200 forever.
        let resolve = |rf: ObjectRef| {
            if rf.id == 200 {
                Some(Object::Dictionary(HashMap::from([(
                    "Kids".to_string(),
                    Object::Array(vec![Object::Reference(ObjectRef::new(200, 0))]),
                )])))
            } else {
                None
            }
        };
        let names = Object::Dictionary(HashMap::from([(
            "Dests".to_string(),
            Object::Reference(ObjectRef::new(200, 0)),
        )]));
        let cat = HashMap::from([("Names".to_string(), names)]);
        // Must return None (bounded), not hang or overflow.
        assert!(lookup_named_dest(&cat, b"x", &resolve, 0).is_none());
    }

    /// No /Dests and no /Names → cleanly None.
    #[test]
    fn no_dests_no_names_is_none() {
        let cat = HashMap::from([("Type".to_string(), Object::Name("Catalog".to_string()))]);
        assert!(lookup_named_dest(&cat, b"anything", &no_resolve(), 0).is_none());
    }
}