pdfrum_doc/nav/
outline.rs

1//! The document outline (ISO 32000-1 §12.3.3), commonly called bookmarks.
2//!
3//! There is no tree object: an outline is a `/First`-and-`/Next` linked
4//! structure over dictionaries, walked pre-order. The cycle guard is a
5//! visited set of object references, and it is checked in **two** places —
6//! on entry to a node and again on each sibling step — because a
7//! self-referential root must be visited exactly once before the walk stops.
8
9use std::collections::HashSet;
10
11use pdfrum_common::{DiagKind, Diagnostics, Limits, Severity};
12use pdfrum_object::{Dict, ObjRef, Object, Resolve, decode_text, names as obj_names};
13
14use crate::names;
15use crate::nav::action::Action;
16use crate::nav::dest::Dest;
17
18/// One outline item.
19#[derive(Debug, Clone, PartialEq)]
20pub struct Bookmark {
21    /// The item's dictionary.
22    pub dict: Dict,
23    /// How deep in the outline it sits; the top level is zero.
24    pub depth: usize,
25}
26
27impl Bookmark {
28    /// The item's title.
29    ///
30    /// Two details: `/Title` is **type-filtered to a string**, so a
31    /// name-valued title reads as empty; and every code unit below `0x20` is
32    /// **raised to a space**, so control characters become blanks without
33    /// changing the length. The second matters because titles are compared
34    /// case-insensitively when searching.
35    ///
36    /// ```
37    /// use pdfrum_common::{Diagnostics, Limits};
38    /// use pdfrum_doc::nav::outline_bookmarks;
39    /// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
40    ///
41    /// let item = Dict::from_pairs([
42    ///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
43    /// ]);
44    /// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
45    /// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
46    ///
47    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
48    /// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
49    ///
50    /// assert_eq!(bookmarks[0].title(&NoResolve), "Introduction");
51    /// ```
52    #[must_use]
53    pub fn title<R: Resolve>(&self, r: &R) -> String {
54        let Some(raw) = self
55            .dict
56            .get(obj_names::TITLE, r)
57            .and_then(|v| v.get().as_string().map(|s| s.as_bytes().to_vec()))
58        else {
59            return String::new();
60        };
61        decode_text(&raw)
62            .chars()
63            .map(|c| if (c as u32) < 0x20 { ' ' } else { c })
64            .collect()
65    }
66
67    /// `/Count`: positive for an open item with that many visible
68    /// descendants, negative for a closed one, zero for a leaf.
69    ///
70    /// The sign is preserved and the value is not masked.
71    ///
72    /// ```
73    /// use pdfrum_common::{Diagnostics, Limits};
74    /// use pdfrum_doc::nav::outline_bookmarks;
75    /// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
76    ///
77    /// let item = Dict::from_pairs([
78    ///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
79    /// ]);
80    /// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
81    /// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
82    ///
83    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
84    /// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
85    ///
86    /// // A leaf: zero, with no `/Count` in the file.
87    /// assert_eq!(bookmarks[0].count(&NoResolve), 0);
88    /// ```
89    #[must_use]
90    pub fn count<R: Resolve>(&self, r: &R) -> i64 {
91        self.dict.int(obj_names::COUNT, r).unwrap_or(0)
92    }
93
94    /// `/F`, the style flag word, **unmasked** — a file writing 15 reports
95    /// 15, not the two defined bits.
96    ///
97    /// ```
98    /// use pdfrum_common::{Diagnostics, Limits};
99    /// use pdfrum_doc::nav::outline_bookmarks;
100    /// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
101    ///
102    /// let item = Dict::from_pairs([
103    ///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
104    /// ]);
105    /// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
106    /// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
107    ///
108    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
109    /// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
110    ///
111    /// assert_eq!(bookmarks[0].style(&NoResolve), 0);
112    /// ```
113    #[must_use]
114    pub fn style<R: Resolve>(&self, r: &R) -> i64 {
115        self.dict.int(names::F, r).unwrap_or(0)
116    }
117
118    /// `/C`, the item's colour, as three components in `[0, 1]`.
119    ///
120    /// The array must hold **exactly three** entries and every one must be a
121    /// number inside the unit interval; anything else is no colour. Upstream
122    /// dereferences a non-number here without checking, which is a latent
123    /// crash — we answer `None`.
124    ///
125    /// ```
126    /// use pdfrum_common::{Diagnostics, Limits};
127    /// use pdfrum_doc::nav::outline_bookmarks;
128    /// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
129    ///
130    /// let item = Dict::from_pairs([
131    ///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
132    /// ]);
133    /// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
134    /// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
135    ///
136    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
137    /// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
138    ///
139    /// // No `/C`: no colour. So is any array that is not exactly three
140    /// // numbers inside the unit interval.
141    /// assert_eq!(bookmarks[0].color(&NoResolve), None);
142    /// ```
143    #[must_use]
144    pub fn color<R: Resolve>(&self, r: &R) -> Option<(f32, f32, f32)> {
145        let array = self.dict.array(names::C, r)?;
146        if array.len() != 3 {
147            return None;
148        }
149        let component = |index: usize| {
150            array
151                .number_obj_at(index)
152                .and_then(Object::number)
153                .filter(|value| (0.0..=1.0).contains(value))
154        };
155        Some((component(0)?, component(1)?, component(2)?))
156    }
157
158    /// The item's action.
159    ///
160    /// ```
161    /// use pdfrum_common::{Diagnostics, Limits};
162    /// use pdfrum_doc::nav::outline_bookmarks;
163    /// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
164    ///
165    /// let item = Dict::from_pairs([
166    ///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
167    /// ]);
168    /// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
169    /// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
170    ///
171    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
172    /// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
173    ///
174    /// assert!(bookmarks[0].action(&NoResolve).is_none());
175    /// ```
176    #[must_use]
177    pub fn action<R: Resolve>(&self, r: &R) -> Option<Action> {
178        self.dict.dict(names::A, r).map(Action::new)
179    }
180
181    /// Where the item goes: `/Dest` first, the action's destination only when
182    /// that yields no array.
183    ///
184    /// ```
185    /// use pdfrum_common::{Diagnostics, Limits};
186    /// use pdfrum_doc::nav::outline_bookmarks;
187    /// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
188    ///
189    /// let item = Dict::from_pairs([
190    ///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
191    /// ]);
192    /// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
193    /// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
194    ///
195    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
196    /// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
197    ///
198    /// let dest = bookmarks[0].dest(&catalog, &NoResolve, &limits, &mut diags);
199    /// assert!(dest.array.is_none());
200    /// ```
201    #[must_use]
202    pub fn dest<R: Resolve>(
203        &self,
204        catalog: &Dict,
205        r: &R,
206        limits: &Limits,
207        diags: &mut Diagnostics,
208    ) -> Dest {
209        let own = self.dict.get(names::DEST, r).map(|d| d.get().clone());
210        let dest = Dest::create(catalog, own.as_ref(), r, limits, diags);
211        if dest.array.is_some() {
212            return dest;
213        }
214        self.action(r)
215            .map(|action| action.dest(catalog, r, limits, diags))
216            .unwrap_or_default()
217    }
218}
219
220/// Walks the whole outline pre-order: each item, then its subtree, then its
221/// next sibling.
222///
223/// ```
224/// use pdfrum_common::{Diagnostics, Limits};
225/// use pdfrum_doc::nav::outline_bookmarks;
226/// use pdfrum_object::{Dict, Name, NoResolve, Object, PdfString};
227///
228/// let item = Dict::from_pairs([
229///     (Name::from("Title"), Object::Str(PdfString::literal(b"Introduction"))),
230/// ]);
231/// let outlines = Dict::from_pairs([(Name::from("First"), Object::Dict(item))]);
232/// let catalog = Dict::from_pairs([(Name::from("Outlines"), Object::Dict(outlines))]);
233///
234/// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
235/// let bookmarks = outline_bookmarks(&catalog, &NoResolve, &limits, &mut diags);
236///
237/// // Pre-order, with the top level at depth zero.
238/// assert_eq!(bookmarks.len(), 1);
239/// assert_eq!(bookmarks[0].depth, 0);
240/// ```
241#[must_use]
242pub fn outline_bookmarks<R: Resolve>(
243    catalog: &Dict,
244    r: &R,
245    limits: &Limits,
246    diags: &mut Diagnostics,
247) -> Vec<Bookmark> {
248    let mut out = Vec::new();
249    let Some(outlines) = catalog.dict(names::OUTLINES, r) else {
250        return out;
251    };
252    let mut seen = HashSet::new();
253    let first = outlines.dict(names::FIRST, r);
254    let first_ref = outlines.reference(names::FIRST);
255    if let Some(first) = first {
256        visit(&first, first_ref, 0, &mut seen, &mut out, r, limits, diags);
257    }
258    out
259}
260
261#[allow(clippy::too_many_arguments)]
262fn visit<R: Resolve>(
263    dict: &Dict,
264    reference: Option<ObjRef>,
265    depth: usize,
266    seen: &mut HashSet<ObjRef>,
267    out: &mut Vec<Bookmark>,
268    r: &R,
269    limits: &Limits,
270    diags: &mut Diagnostics,
271) {
272    if depth > limits.max_name_tree_depth as usize {
273        diags.record(Severity::Suspicious, DiagKind::TreeDepthExceeded, None);
274        return;
275    }
276    let mut node = dict.clone();
277    let mut node_ref = reference;
278    loop {
279        if let Some(reference) = node_ref
280            && !seen.insert(reference)
281        {
282            diags.record(Severity::Recovered, DiagKind::NavigationCycle, None);
283            return;
284        }
285        out.push(Bookmark {
286            dict: node.clone(),
287            depth,
288        });
289        if let Some(child) = node.dict(names::FIRST, r) {
290            let child_ref = node.reference(names::FIRST);
291            visit(&child, child_ref, depth + 1, seen, out, r, limits, diags);
292        }
293        // A `/Next` pointing back at this very node ends the chain; that is
294        // a self-reference test, not a structural comparison, so a duplicate
295        // written inline is a distinct sibling.
296        let next_ref = node.reference(names::NEXT);
297        if next_ref.is_some() && next_ref == node_ref {
298            return;
299        }
300        let Some(next) = node.dict(names::NEXT, r) else {
301            return;
302        };
303        node = next;
304        node_ref = next_ref;
305    }
306}
307
308/// Finds the first item whose title matches, comparing case-insensitively.
309#[must_use]
310#[cfg(test)]
311pub(crate) fn find<R: Resolve>(
312    catalog: &Dict,
313    title: &str,
314    r: &R,
315    limits: &Limits,
316    diags: &mut Diagnostics,
317) -> Option<Bookmark> {
318    let wanted = title.to_lowercase();
319    outline_bookmarks(catalog, r, limits, diags)
320        .into_iter()
321        .find(|bookmark| bookmark.title(r).to_lowercase() == wanted)
322}
323
324#[cfg(test)]
325mod tests {
326    use super::{Bookmark, find, outline_bookmarks};
327    use pdfrum_common::{Diagnostics, Limits};
328    use pdfrum_object::{Array, Dict, Name, NoResolve, Object, PdfString};
329
330    fn dict(pairs: &[(&str, Object)]) -> Dict {
331        Dict::from_pairs(
332            pairs
333                .iter()
334                .map(|(k, v)| (Name::from(*k), v.clone()))
335                .collect::<Vec<_>>(),
336        )
337    }
338
339    fn bookmark(pairs: &[(&str, Object)]) -> Bookmark {
340        Bookmark {
341            dict: dict(pairs),
342            depth: 0,
343        }
344    }
345
346    #[test]
347    fn a_title_is_type_filtered_and_has_its_control_characters_raised() {
348        let named = bookmark(&[("Title", Object::Name(Name::from("Chapter")))]);
349        assert_eq!(named.title(&NoResolve), "");
350
351        let with_controls = bookmark(&[("Title", Object::Str(PdfString::literal(b"A\tB\x01C")))]);
352        // The length is unchanged; only the code points move up.
353        assert_eq!(with_controls.title(&NoResolve), "A B C");
354    }
355
356    #[test]
357    fn the_count_keeps_its_sign_and_is_not_masked() {
358        assert_eq!(
359            bookmark(&[("Count", Object::Int(-2))]).count(&NoResolve),
360            -2
361        );
362        assert_eq!(bookmark(&[]).count(&NoResolve), 0);
363        assert_eq!(bookmark(&[("F", Object::Int(15))]).style(&NoResolve), 15);
364        // A non-integer style reads as zero.
365        assert_eq!(
366            bookmark(&[("F", Object::Name(Name::from("x")))]).style(&NoResolve),
367            0
368        );
369    }
370
371    #[test]
372    fn a_colour_needs_exactly_three_numbers_inside_the_unit_interval() {
373        let good = bookmark(&[(
374            "C",
375            Object::Array(Array::of([0.1_f32, 0.2, 0.3].map(Object::from))),
376        )]);
377        assert_eq!(good.color(&NoResolve), Some((0.1, 0.2, 0.3)));
378
379        for bad in [
380            Object::Array(Array::of([0.1_f32, 0.2].map(Object::from))),
381            Object::Array(Array::of([0.1_f32, 0.2, 0.3, 0.4].map(Object::from))),
382            Object::Array(Array::of([1.5_f32, 0.2, 0.3].map(Object::from))),
383            Object::Array(Array::of([-0.1_f32, 0.2, 0.3].map(Object::from))),
384            Object::Int(4),
385        ] {
386            assert_eq!(bookmark(&[("C", bad)]).color(&NoResolve), None);
387        }
388    }
389
390    #[test]
391    fn a_non_numeric_component_answers_none_rather_than_crashing() {
392        let malformed = bookmark(&[(
393            "C",
394            Object::Array(Array::of([
395                Object::Name(Name::from("red")),
396                Object::from(0.2_f32),
397                Object::from(0.3_f32),
398            ])),
399        )]);
400        assert_eq!(malformed.color(&NoResolve), None);
401    }
402
403    #[test]
404    fn the_walk_is_pre_order_with_depth() {
405        // root -> (child, sibling); child has one grandchild.
406        let grandchild = dict(&[("Title", Object::Str(PdfString::literal(b"grandchild")))]);
407        let child = dict(&[
408            ("Title", Object::Str(PdfString::literal(b"child"))),
409            ("First", Object::Dict(grandchild)),
410        ]);
411        let sibling = dict(&[("Title", Object::Str(PdfString::literal(b"sibling")))]);
412        let root = dict(&[
413            ("Title", Object::Str(PdfString::literal(b"root"))),
414            ("First", Object::Dict(child)),
415            ("Next", Object::Dict(sibling)),
416        ]);
417        let catalog = dict(&[(
418            "Outlines",
419            Object::Dict(dict(&[("First", Object::Dict(root))])),
420        )]);
421        let (l, mut d) = (Limits::default(), Diagnostics::default());
422        let items = outline_bookmarks(&catalog, &NoResolve, &l, &mut d);
423        let seen: Vec<_> = items
424            .iter()
425            .map(|b| (b.title(&NoResolve), b.depth))
426            .collect();
427        assert_eq!(
428            seen,
429            [
430                ("root".to_owned(), 0),
431                ("child".to_owned(), 1),
432                ("grandchild".to_owned(), 2),
433                ("sibling".to_owned(), 0),
434            ]
435        );
436    }
437
438    #[test]
439    fn finding_a_title_ignores_case() {
440        let root = dict(&[(
441            "Title",
442            Object::Str(PdfString::literal(b"A Good Beginning")),
443        )]);
444        let catalog = dict(&[(
445            "Outlines",
446            Object::Dict(dict(&[("First", Object::Dict(root))])),
447        )]);
448        let (l, mut d) = (Limits::default(), Diagnostics::default());
449        assert!(find(&catalog, "a good beginning", &NoResolve, &l, &mut d).is_some());
450        assert!(find(&catalog, "A BAD Beginning", &NoResolve, &l, &mut d).is_none());
451    }
452
453    #[test]
454    fn an_outline_with_no_entries_walks_to_nothing() {
455        let (l, mut d) = (Limits::default(), Diagnostics::default());
456        assert!(outline_bookmarks(&Dict::new(), &NoResolve, &l, &mut d).is_empty());
457        let empty = dict(&[("Outlines", Object::Dict(Dict::new()))]);
458        assert!(outline_bookmarks(&empty, &NoResolve, &l, &mut d).is_empty());
459    }
460}
pdfrum_doc/nav/outline.rs

pdfrum_doc/nav/
outline.rs
