stet_pdf_reader/
name_tree.rs

1// stet-pdf-reader
2// Copyright (c) 2026 Scott Bowman
3// SPDX-License-Identifier: Apache-2.0 OR MIT
4
5//! PDF name tree traversal.
6//!
7//! Per ISO 32000-2 §7.9.6, several catalog entries (named destinations,
8//! embedded files, JavaScript, AP appearance streams, etc.) live in
9//! *name trees*: B-tree-like structures keyed by string. Each node is
10//! either a leaf (has `/Names` — an array of alternating
11//! `(string, value)` pairs in sorted order) or a branch (has `/Kids`
12//! — references to child nodes). The root may have either or both.
13//!
14//! [`walk_name_tree`] is generic over the value type: callers supply
15//! a parser that converts a `PdfObj` value into their typed
16//! representation, and the walker traverses the tree producing a
17//! `HashMap<String, T>` of every leaf entry.
18
19use std::collections::{HashMap, HashSet};
20
21use crate::objects::PdfObj;
22use crate::resolver::Resolver;
23
24/// Maximum total leaf entries to collect.
25///
26/// Real-world name trees rarely exceed a few thousand entries; this
27/// cap stops pathological documents from running away.
28const MAX_NAME_TREE_ENTRIES: usize = 1_000_000;
29
30/// Maximum branch-node depth to follow.
31///
32/// Spec-conformant name trees are typically shallow (depth 1–3 even
33/// for tens of thousands of entries). 64 is a generous upper bound.
34const MAX_NAME_TREE_DEPTH: u32 = 64;
35
36/// Walk a PDF name tree starting at `root`, producing a map of all
37/// leaf entries.
38///
39/// `parse_value` is invoked for every leaf entry; if it returns
40/// `None`, that entry is skipped (the rest of the tree continues to
41/// be traversed normally). Cycles are detected via an object-number
42/// visited set; depth is capped.
43///
44/// Returns an empty `HashMap` for empty/missing/invalid trees.
45pub fn walk_name_tree<T, F>(
46    resolver: &Resolver,
47    root: &PdfObj,
48    mut parse_value: F,
49) -> HashMap<String, T>
50where
51    F: FnMut(&Resolver, &PdfObj) -> Option<T>,
52{
53    let mut out = HashMap::new();
54    let mut visited = HashSet::new();
55    walk_node(resolver, root, &mut visited, &mut out, &mut parse_value, 0);
56    out
57}
58
59fn walk_node<T, F>(
60    resolver: &Resolver,
61    node_obj: &PdfObj,
62    visited: &mut HashSet<u32>,
63    out: &mut HashMap<String, T>,
64    parse_value: &mut F,
65    depth: u32,
66) where
67    F: FnMut(&Resolver, &PdfObj) -> Option<T>,
68{
69    if depth >= MAX_NAME_TREE_DEPTH {
70        return;
71    }
72    if out.len() >= MAX_NAME_TREE_ENTRIES {
73        return;
74    }
75    // If this is an indirect ref, dereference and record visit.
76    if let Some((num, _gen)) = node_obj.as_ref()
77        && !visited.insert(num)
78    {
79        return;
80    }
81    let Ok(node) = resolver.deref(node_obj) else {
82        return;
83    };
84    let Some(dict) = node.as_dict() else {
85        return;
86    };
87
88    // Leaf: /Names is an array of alternating (string, value) pairs.
89    if let Some(names) = dict.get_array(b"Names") {
90        let mut i = 0;
91        while i + 1 < names.len() {
92            if out.len() >= MAX_NAME_TREE_ENTRIES {
93                return;
94            }
95            let key_obj = &names[i];
96            let val_obj = &names[i + 1];
97            if let Some(key_bytes) = resolver
98                .deref(key_obj)
99                .ok()
100                .as_ref()
101                .and_then(|o| o.as_str().map(<[u8]>::to_vec))
102            {
103                let key = String::from_utf8_lossy(&key_bytes).into_owned();
104                if let Some(value) = parse_value(resolver, val_obj) {
105                    out.insert(key, value);
106                }
107            }
108            i += 2;
109        }
110    }
111
112    // Branch: /Kids is an array of refs to child nodes. A node may
113    // have both /Names (own leaves) and /Kids (further descent) — rare
114    // but legal — so this is independent of the leaf check.
115    if let Some(kids) = dict.get_array(b"Kids") {
116        for kid in kids {
117            if out.len() >= MAX_NAME_TREE_ENTRIES {
118                return;
119            }
120            walk_node(resolver, kid, visited, out, parse_value, depth + 1);
121        }
122    }
123}
124
125#[cfg(test)]
126mod tests {
127    use super::*;
128    use crate::objects::{PdfDict, PdfObj};
129    use crate::xref::XrefTable;
130
131    /// Build a tiny in-memory resolver harness so we can run leaf-only
132    /// trees without a real PDF. /Kids tests need indirect-ref support
133    /// which requires xref entries; we cover those via lib.rs's
134    /// synthetic-PDF tests.
135    fn empty_resolver() -> (Vec<u8>, XrefTable) {
136        // Minimal valid PDF stub so XrefTable construction is well-formed.
137        let data = b"%PDF-1.4\nxref\n0 1\n0000000000 65535 f \ntrailer\n<< /Size 1 >>\nstartxref\n9\n%%EOF\n".to_vec();
138        let xref = crate::xref::parse_xref(&data).unwrap();
139        (data, xref)
140    }
141
142    #[test]
143    fn flat_leaf_tree() {
144        let (data, xref) = empty_resolver();
145        let resolver = Resolver::with_encryption(&data, xref, None);
146
147        // Build a leaf node: /Names [(A) 1 (B) 2 (C) 3]
148        let mut leaf = PdfDict::new();
149        leaf.insert(
150            b"Names".to_vec(),
151            PdfObj::Array(vec![
152                PdfObj::Str(b"A".to_vec()),
153                PdfObj::Int(1),
154                PdfObj::Str(b"B".to_vec()),
155                PdfObj::Int(2),
156                PdfObj::Str(b"C".to_vec()),
157                PdfObj::Int(3),
158            ]),
159        );
160        let root = PdfObj::Dict(leaf);
161
162        let map = walk_name_tree(&resolver, &root, |_r, v| v.as_int());
163
164        assert_eq!(map.len(), 3);
165        assert_eq!(map.get("A"), Some(&1));
166        assert_eq!(map.get("B"), Some(&2));
167        assert_eq!(map.get("C"), Some(&3));
168    }
169
170    #[test]
171    fn parse_value_can_skip() {
172        let (data, xref) = empty_resolver();
173        let resolver = Resolver::with_encryption(&data, xref, None);
174
175        let mut leaf = PdfDict::new();
176        leaf.insert(
177            b"Names".to_vec(),
178            PdfObj::Array(vec![
179                PdfObj::Str(b"keep".to_vec()),
180                PdfObj::Int(42),
181                PdfObj::Str(b"skip".to_vec()),
182                PdfObj::Null,
183            ]),
184        );
185        let root = PdfObj::Dict(leaf);
186
187        let map = walk_name_tree(&resolver, &root, |_r, v| v.as_int());
188
189        assert_eq!(map.len(), 1);
190        assert_eq!(map.get("keep"), Some(&42));
191        assert!(!map.contains_key("skip"));
192    }
193
194    #[test]
195    fn empty_tree_yields_empty_map() {
196        let (data, xref) = empty_resolver();
197        let resolver = Resolver::with_encryption(&data, xref, None);
198
199        // An empty dict — no /Names, no /Kids.
200        let root = PdfObj::Dict(PdfDict::new());
201        let map: HashMap<String, i64> = walk_name_tree(&resolver, &root, |_r, v| v.as_int());
202        assert!(map.is_empty());
203    }
204
205    #[test]
206    fn malformed_names_array_odd_length() {
207        let (data, xref) = empty_resolver();
208        let resolver = Resolver::with_encryption(&data, xref, None);
209
210        // /Names with odd count — the trailing unmatched key is dropped.
211        let mut leaf = PdfDict::new();
212        leaf.insert(
213            b"Names".to_vec(),
214            PdfObj::Array(vec![
215                PdfObj::Str(b"A".to_vec()),
216                PdfObj::Int(1),
217                PdfObj::Str(b"orphan".to_vec()),
218            ]),
219        );
220        let root = PdfObj::Dict(leaf);
221
222        let map = walk_name_tree(&resolver, &root, |_r, v| v.as_int());
223        assert_eq!(map.len(), 1);
224        assert_eq!(map.get("A"), Some(&1));
225    }
226}
stet_pdf_reader/name_tree.rs

stet_pdf_reader/
name_tree.rs
