zpdf_document/
outline.rs

1//! Document outline / bookmarks (ISO 32000-1 §12.3.3). The catalog's
2//! `/Outlines` dictionary roots a tree of outline items, each a `/Title` plus a
3//! navigation target — a destination (`/Dest`) or an action (`/A`, typically a
4//! go-to or a URI). Items are linked as a doubly-linked sibling list (`/First`,
5//! `/Last`, `/Next`, `/Prev`) with `/First`/`/Count` descending into children.
6//!
7//! This reads the tree into a nested [`OutlineItem`] structure, resolving each
8//! item's target through [`crate::destinations`]. Bounded by depth, a visited
9//! set, and a global item cap so a malformed/cyclic tree cannot loop.
10
11use std::collections::{HashMap, HashSet};
12
13use zpdf_core::{ObjectId, PdfDict, PdfObject};
14use zpdf_parser::PdfFile;
15
16use crate::destinations::{collect_named_dests, resolve_link_target, Destination};
17use crate::obj_util::{catalog_dict, resolve_dict, resolve_number, text};
18use crate::Catalog;
19
20/// Maximum nesting depth of the outline tree before a subtree is pruned.
21const MAX_OUTLINE_DEPTH: usize = 64;
22/// Global cap on outline items collected from one document.
23const MAX_OUTLINE_ITEMS: usize = 65_536;
24
25/// One bookmark: a title, an optional navigation target, and nested children.
26#[derive(Debug, Clone, PartialEq)]
27pub struct OutlineItem {
28    /// `/Title` — the bookmark label (text string; UTF-16BE/PDFDoc decoded).
29    pub title: String,
30    /// The resolved navigation destination (`/Dest`, or a go-to action's `/D`),
31    /// when this item carries one.
32    pub dest: Option<Destination>,
33    /// A URI target (`/A` with `/S /URI`), or a remote go-to file path
34    /// (`/S /GoToR` `/F`), when this item links outside the page model.
35    pub uri: Option<String>,
36    /// `/Count` > 0: the item is *open* (its children shown by default).
37    pub open: bool,
38    /// Nested child bookmarks (from `/First` … `/Next`).
39    pub children: Vec<OutlineItem>,
40}
41
42/// Parse the document outline (bookmarks). Empty when the document has none.
43pub fn parse_outlines(file: &PdfFile, catalog: &Catalog) -> Vec<OutlineItem> {
44    let Some(root) = catalog_dict(file) else {
45        return Vec::new();
46    };
47    let Some(outlines) = resolve_dict(file, root.get("Outlines")) else {
48        return Vec::new();
49    };
50
51    let mut visited = HashSet::new();
52    // Seed the cycle guard with the outline-root reference, so a malicious item
53    // whose /Next or /First points back at the root cannot spawn a spurious pass
54    // (parity with embedded_files / destinations tree-root seeding).
55    if let Some(PdfObject::Ref(id)) = root.get("Outlines") {
56        visited.insert(*id);
57    }
58    // Flatten the named-destination registries once, so each bookmark's named
59    // destination resolves in O(1) against this map rather than re-walking the
60    // name tree per item (which a crafted file could turn into a DoS).
61    let named = collect_named_dests(file);
62    let mut walk = OutlineWalk {
63        file,
64        catalog,
65        named: &named,
66        visited,
67        count: 0,
68    };
69
70    // The outline root's /First begins the top-level sibling chain.
71    let mut out = Vec::new();
72    if let Some(first_ref) = outlines.get("First").and_then(as_ref) {
73        walk.walk_siblings(first_ref, &mut out, 0);
74    }
75    out
76}
77
78/// Shared state for one outline traversal: the ambient object graph plus the
79/// cross-tree cycle guard and item budget. Collected into a context so the
80/// recursive walk methods stay legible (and avoid a long argument list).
81struct OutlineWalk<'a> {
82    file: &'a PdfFile,
83    catalog: &'a Catalog,
84    /// Pre-collected named destinations (see [`collect_named_dests`]).
85    named: &'a HashMap<Vec<u8>, PdfObject>,
86    /// Every outline item reference seen so far — a `/Next`/`/First` back-edge
87    /// to any of them terminates that chain.
88    visited: HashSet<ObjectId>,
89    /// Total items collected, capped at [`MAX_OUTLINE_ITEMS`].
90    count: usize,
91}
92
93impl OutlineWalk<'_> {
94    /// Walk a sibling chain (`item` → `/Next` → …), appending each item.
95    fn walk_siblings(&mut self, mut item_ref: ObjectId, out: &mut Vec<OutlineItem>, depth: usize) {
96        loop {
97            if depth > MAX_OUTLINE_DEPTH || self.count >= MAX_OUTLINE_ITEMS {
98                return;
99            }
100            // Cycle guard: a /Next or /First that points back to a seen item stops.
101            if !self.visited.insert(item_ref) {
102                return;
103            }
104            self.count += 1;
105
106            let Some(dict) = self
107                .file
108                .resolve(item_ref)
109                .ok()
110                .and_then(|o| o.as_dict().ok().cloned())
111            else {
112                return;
113            };
114
115            let item = self.build_item(&dict, depth);
116            out.push(item);
117
118            match dict.get("Next").and_then(as_ref) {
119                Some(next) => item_ref = next,
120                None => return,
121            }
122        }
123    }
124
125    /// Build one [`OutlineItem`] from its dictionary, recursing into `/First` for
126    /// children and resolving its `/Dest` or `/A` target.
127    fn build_item(&mut self, dict: &PdfDict, depth: usize) -> OutlineItem {
128        let title = text(self.file, dict, "Title").unwrap_or_default();
129        let (dest, uri) = self.resolve_target(dict);
130
131        // /Count > 0 means the item is displayed open (children visible). The
132        // magnitude is the visible-descendant count; only the sign matters here.
133        // Read it through the resolving numeric accessor so an indirect or Real
134        // /Count is honoured (matching the module's other numeric reads).
135        let open = resolve_number(self.file, dict.get("Count")).is_some_and(|c| c > 0.0);
136
137        let mut children = Vec::new();
138        if let Some(first) = dict.get("First").and_then(as_ref) {
139            self.walk_siblings(first, &mut children, depth + 1);
140        }
141
142        OutlineItem {
143            title,
144            dest,
145            uri,
146            open,
147            children,
148        }
149    }
150
151    /// Resolve an outline item's navigation target (`/Dest` or `/A`) through the
152    /// shared resolver, against the pre-collected named-destination map.
153    fn resolve_target(&self, dict: &PdfDict) -> (Option<Destination>, Option<String>) {
154        resolve_link_target(self.file, self.catalog, dict, Some(self.named))
155    }
156}
157
158/// An object that is (or resolves to) an indirect reference's id.
159fn as_ref(obj: &PdfObject) -> Option<ObjectId> {
160    match obj {
161        PdfObject::Ref(r) => Some(*r),
162        _ => None,
163    }
164}
165
166#[cfg(test)]
167mod tests {
168    use crate::destinations::DestView;
169    use crate::test_util::build_pdf;
170    use crate::PdfDocument;
171
172    fn open(objects: &[&str]) -> PdfDocument {
173        PdfDocument::open(build_pdf(objects)).expect("open pdf")
174    }
175
176    const PAGES2: &str = "<< /Type /Pages /Kids [3 0 R 4 0 R] /Count 2 >>";
177    const PAGE_A: &str = "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 100 100] >>";
178    const PAGE_B: &str = "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 100 100] >>";
179
180    #[test]
181    fn no_outlines_is_empty() {
182        let doc = open(&["<< /Type /Catalog /Pages 2 0 R >>", PAGES2, PAGE_A, PAGE_B]);
183        assert!(doc.outline().is_empty());
184    }
185
186    #[test]
187    fn single_item_with_explicit_dest() {
188        let doc = open(&[
189            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
190            PAGES2,
191            PAGE_A,
192            PAGE_B,
193            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
194            "<< /Title (Chapter 1) /Parent 5 0 R /Dest [4 0 R /Fit] >>",
195        ]);
196        let outline = doc.outline();
197        assert_eq!(outline.len(), 1);
198        assert_eq!(outline[0].title, "Chapter 1");
199        let dest = outline[0].dest.as_ref().expect("dest");
200        assert_eq!(dest.page, Some(1));
201        assert_eq!(dest.view, DestView::Fit);
202        assert!(outline[0].children.is_empty());
203    }
204
205    #[test]
206    fn sibling_chain_in_order() {
207        let doc = open(&[
208            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
209            PAGES2,
210            PAGE_A,
211            PAGE_B,
212            "<< /Type /Outlines /First 6 0 R /Last 8 0 R /Count 3 >>",
213            "<< /Title (One)   /Parent 5 0 R /Next 7 0 R >>",
214            "<< /Title (Two)   /Parent 5 0 R /Prev 6 0 R /Next 8 0 R >>",
215            "<< /Title (Three) /Parent 5 0 R /Prev 7 0 R >>",
216        ]);
217        let titles: Vec<_> = doc.outline().into_iter().map(|i| i.title).collect();
218        assert_eq!(titles, ["One", "Two", "Three"]);
219    }
220
221    #[test]
222    fn nested_children_and_open_flag() {
223        let doc = open(&[
224            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
225            PAGES2,
226            PAGE_A,
227            PAGE_B,
228            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 2 >>",
229            "<< /Title (Parent) /Parent 5 0 R /First 7 0 R /Last 7 0 R /Count 1 >>",
230            "<< /Title (Child) /Parent 6 0 R >>",
231        ]);
232        let outline = doc.outline();
233        assert_eq!(outline.len(), 1);
234        assert!(outline[0].open, "/Count 1 (> 0) means open");
235        assert_eq!(outline[0].children.len(), 1);
236        assert_eq!(outline[0].children[0].title, "Child");
237    }
238
239    #[test]
240    fn closed_item_negative_count() {
241        let doc = open(&[
242            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
243            PAGES2,
244            PAGE_A,
245            PAGE_B,
246            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
247            "<< /Title (Collapsed) /Parent 5 0 R /First 7 0 R /Last 7 0 R /Count -1 >>",
248            "<< /Title (Hidden child) /Parent 6 0 R >>",
249        ]);
250        let outline = doc.outline();
251        assert!(!outline[0].open, "/Count -1 (< 0) means closed");
252        // Children are still parsed (a viewer may expand them); only `open` differs.
253        assert_eq!(outline[0].children.len(), 1);
254    }
255
256    #[test]
257    fn open_flag_honors_indirect_and_real_count() {
258        // /Count as an indirect ref (legal) and as a Real (lax) must still set open.
259        let doc = open(&[
260            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
261            PAGES2,
262            PAGE_A,
263            PAGE_B,
264            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
265            "<< /Title (Indirect) /Parent 5 0 R /First 7 0 R /Last 7 0 R /Count 8 0 R >>",
266            "<< /Title (Child) /Parent 6 0 R >>",
267            "2", // object 8: the indirect /Count value
268        ]);
269        assert!(doc.outline()[0].open, "indirect /Count > 0 means open");
270
271        let doc_real = open(&[
272            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
273            PAGES2,
274            PAGE_A,
275            PAGE_B,
276            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
277            "<< /Title (Real) /Parent 5 0 R /First 7 0 R /Last 7 0 R /Count 3.0 >>",
278            "<< /Title (Child) /Parent 6 0 R >>",
279        ]);
280        assert!(doc_real.outline()[0].open, "Real /Count > 0 means open");
281    }
282
283    #[test]
284    fn item_next_pointing_to_root_makes_no_spurious_item() {
285        // The top-level item's /Next points back at the /Outlines root object;
286        // the root is pre-seeded into the visited set, so no bogus item appears.
287        let doc = open(&[
288            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
289            PAGES2,
290            PAGE_A,
291            PAGE_B,
292            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
293            "<< /Title (Only) /Parent 5 0 R /Next 5 0 R >>",
294        ]);
295        let titles: Vec<_> = doc.outline().into_iter().map(|i| i.title).collect();
296        assert_eq!(titles, ["Only"], "root back-edge yields no spurious item");
297    }
298
299    #[test]
300    fn uri_action_captured() {
301        let doc = open(&[
302            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
303            PAGES2,
304            PAGE_A,
305            PAGE_B,
306            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
307            "<< /Title (Website) /Parent 5 0 R /A << /S /URI /URI (https://example.com) >> >>",
308        ]);
309        let outline = doc.outline();
310        assert_eq!(outline[0].uri.as_deref(), Some("https://example.com"));
311        assert!(outline[0].dest.is_none());
312    }
313
314    #[test]
315    fn goto_action_dest_resolved() {
316        let doc = open(&[
317            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
318            PAGES2,
319            PAGE_A,
320            PAGE_B,
321            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
322            "<< /Title (Go) /Parent 5 0 R /A << /S /GoTo /D [3 0 R /XYZ null 700 null] >> >>",
323        ]);
324        let dest = doc.outline()[0].dest.clone().expect("dest");
325        assert_eq!(dest.page, Some(0));
326        assert_eq!(
327            dest.view,
328            DestView::Xyz {
329                left: None,
330                top: Some(700.0),
331                zoom: None,
332            }
333        );
334    }
335
336    #[test]
337    fn gotor_remote_file_name_captured() {
338        // A GoToR action records the destination *file* as the item's uri.
339        let doc = open(&[
340            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
341            PAGES2,
342            PAGE_A,
343            PAGE_B,
344            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
345            "<< /Title (Manual) /Parent 5 0 R /A << /S /GoToR /F (manual.pdf) >> >>",
346        ]);
347        let item = &doc.outline()[0];
348        assert_eq!(item.uri.as_deref(), Some("manual.pdf"));
349        assert!(item.dest.is_none());
350    }
351
352    #[test]
353    fn gotor_filespec_prefers_uf() {
354        // A /F file-specification dictionary: /UF (Unicode) wins over /F.
355        let doc = open(&[
356            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
357            PAGES2,
358            PAGE_A,
359            PAGE_B,
360            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
361            "<< /Title (Doc) /Parent 5 0 R /A << /S /GoToR /F << /F (legacy.txt) /UF (unicode.txt) >> >> >>",
362        ]);
363        assert_eq!(doc.outline()[0].uri.as_deref(), Some("unicode.txt"));
364    }
365
366    #[test]
367    fn gotor_utf16be_filename_decoded() {
368        // A bare /F carrying a UTF-16BE BOM decodes BOM-aware (consistent with
369        // the filespec path), not as raw Latin-1. <FEFF 0066 0069> = "fi".
370        let doc = open(&[
371            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
372            PAGES2,
373            PAGE_A,
374            PAGE_B,
375            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
376            "<< /Title (Doc) /Parent 5 0 R /A << /S /GoToR /F <FEFF00660069> >> >>",
377        ]);
378        assert_eq!(doc.outline()[0].uri.as_deref(), Some("fi"));
379    }
380
381    #[test]
382    fn named_dest_via_legacy_root_dests() {
383        // Outline item naming a destination registered in the legacy /Root /Dests
384        // dict — resolved through the once-collected named-destination map.
385        let doc = open(&[
386            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R /Dests 7 0 R >>",
387            PAGES2,
388            PAGE_A,
389            PAGE_B,
390            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
391            "<< /Title (Legacy) /Parent 5 0 R /Dest (intro) >>",
392            "<< /intro [4 0 R /Fit] >>",
393        ]);
394        assert_eq!(doc.outline()[0].dest.as_ref().unwrap().page, Some(1));
395    }
396
397    #[test]
398    fn many_items_share_named_dest_resolution() {
399        // Several bookmarks name the same (and a missing) destination; resolution
400        // goes through the once-collected name map, not a per-item tree walk.
401        let doc = open(&[
402            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R /Names << /Dests 9 0 R >> >>",
403            PAGES2,
404            PAGE_A,
405            PAGE_B,
406            "<< /Type /Outlines /First 6 0 R /Last 8 0 R /Count 3 >>",
407            "<< /Title (A) /Parent 5 0 R /Next 7 0 R /Dest (sec) >>",
408            "<< /Title (B) /Parent 5 0 R /Prev 6 0 R /Next 8 0 R /Dest (sec) >>",
409            "<< /Title (C) /Parent 5 0 R /Prev 7 0 R /Dest (missing) >>",
410            "<< /Names [ (sec) [4 0 R /Fit] ] >>",
411        ]);
412        let out = doc.outline();
413        assert_eq!(out.len(), 3);
414        assert_eq!(out[0].dest.as_ref().unwrap().page, Some(1));
415        assert_eq!(out[1].dest.as_ref().unwrap().page, Some(1));
416        assert!(out[2].dest.is_none(), "an unknown name resolves to no dest");
417    }
418
419    #[test]
420    fn named_dest_in_outline_resolves() {
421        let doc = open(&[
422            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R /Names << /Dests 7 0 R >> >>",
423            PAGES2,
424            PAGE_A,
425            PAGE_B,
426            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
427            "<< /Title (By name) /Parent 5 0 R /Dest (sec1) >>",
428            "<< /Names [ (sec1) [4 0 R /Fit] ] >>",
429        ]);
430        let dest = doc.outline()[0].dest.clone().expect("dest");
431        assert_eq!(dest.page, Some(1));
432    }
433
434    #[test]
435    fn sibling_cycle_terminates() {
436        // /Next points back to the first item; the visited guard must stop it.
437        let doc = open(&[
438            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
439            PAGES2,
440            PAGE_A,
441            PAGE_B,
442            "<< /Type /Outlines /First 6 0 R /Last 7 0 R /Count 2 >>",
443            "<< /Title (A) /Parent 5 0 R /Next 7 0 R >>",
444            "<< /Title (B) /Parent 5 0 R /Next 6 0 R >>", // cycle back to A
445        ]);
446        let titles: Vec<_> = doc.outline().into_iter().map(|i| i.title).collect();
447        assert_eq!(titles, ["A", "B"]); // each visited once, no hang
448    }
449
450    #[test]
451    fn first_pointing_to_self_terminates() {
452        // An item whose /First is itself: child recursion must not loop.
453        let doc = open(&[
454            "<< /Type /Catalog /Pages 2 0 R /Outlines 5 0 R >>",
455            PAGES2,
456            PAGE_A,
457            PAGE_B,
458            "<< /Type /Outlines /First 6 0 R /Last 6 0 R /Count 1 >>",
459            "<< /Title (Self) /Parent 5 0 R /First 6 0 R >>",
460        ]);
461        let outline = doc.outline();
462        assert_eq!(outline.len(), 1);
463        assert_eq!(outline[0].title, "Self");
464        assert!(
465            outline[0].children.is_empty(),
466            "self-child cut by visited set"
467        );
468    }
469}
zpdf_document/outline.rs

zpdf_document/
outline.rs
