pdfrum_doc/structure/
mod.rs

1//! The logical structure tree (ISO 32000-1 §14.7), read **per page and
2//! bottom-up**.
3//!
4//! The shape is unusual and it matters. Nothing here walks `/StructTreeRoot`
5//! `/K` downward. Instead the page's `/StructParents` key indexes the
6//! `/ParentTree`, which yields the elements that own this page's marked
7//! content; each of those walks *up* its `/P` chain until it reaches the root,
8//! building the ancestors it passes and linking itself into each one's kid
9//! list. Elements on other pages are never visited, which is why the same
10//! logical tree looks different from each page.
11//!
12//! Two consequences worth expecting:
13//!
14//! - The top-level slot list is sized from the root's `/K` but filled only by
15//!   the upward walk, so a document can report more top-level children than
16//!   it can produce. The dump skips the empty slots.
17//! - Top-level linking matches **direct references only**, so an inline
18//!   dictionary written straight into `/K` is never linked, however well
19//!   formed it is.
20
21mod dump;
22mod element;
23
24pub use dump::render as dump_tree;
25pub use element::Kid;
26pub use element::StructElement;
27
28use pdfrum_common::{DiagKind, Diagnostics, Limits, Severity};
29use pdfrum_object::{Dict, Object, Resolve};
30
31use crate::names;
32use crate::nav::number_tree;
33
34/// One page's view of the document's structure tree.
35///
36/// ```
37/// use pdfrum_common::{Diagnostics, Limits};
38/// use pdfrum_doc::StructTree;
39/// use pdfrum_object::{Dict, Name, NoResolve, Object};
40///
41/// // "Tagged" is `/MarkInfo /Marked` read as a non-zero integer, so a
42/// // Boolean `true` and a written `1` both count.
43/// let catalog = Dict::from_pairs([(
44///     Name::from("MarkInfo"),
45///     Object::Dict(Dict::from_pairs([(Name::from("Marked"), Object::Bool(true))])),
46/// )]);
47///
48/// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
49/// let tree = StructTree::load_page(
50///     &catalog, &Dict::default(), 1, &NoResolve, &limits, &mut diags,
51/// ).expect("the document is tagged");
52///
53/// // No `/StructTreeRoot`: a tree, but an empty one.
54/// assert!(tree.elements.is_empty());
55/// ```
56#[derive(Debug, Clone, Default, PartialEq)]
57pub struct StructTree {
58    /// Every element reached from this page, in discovery order. Kid and
59    /// parent links are indices into this table.
60    pub elements: Vec<StructElement>,
61    /// The root's `/K` slots. Sized from `/K`, filled only where the upward
62    /// walk reached a top-level element, so a `None` is normal.
63    pub top: Vec<Option<usize>>,
64}
65
66impl StructTree {
67    /// Builds the tree for one page, or nothing when the document is not
68    /// tagged.
69    ///
70    /// "Tagged" is `catalog[/MarkInfo][/Marked]` read as a **non-zero
71    /// integer**, and a Boolean has an integer reading of zero or one — so
72    /// the spec-conforming `/Marked true` works, and so does a file writing
73    /// `/Marked 1`.
74    ///
75    /// ```
76    /// use pdfrum_common::{Diagnostics, Limits};
77    /// use pdfrum_doc::StructTree;
78    /// use pdfrum_object::{Dict, Name, NoResolve, Object};
79    ///
80    /// // "Tagged" is `/MarkInfo /Marked` read as a non-zero integer, so a
81    /// // Boolean `true` and a written `1` both count.
82    /// let catalog = Dict::from_pairs([(
83    ///     Name::from("MarkInfo"),
84    ///     Object::Dict(Dict::from_pairs([(Name::from("Marked"), Object::Bool(true))])),
85    /// )]);
86    ///
87    /// let (limits, mut diags) = (Limits::default(), Diagnostics::default());
88    /// let page = Dict::default();
89    /// assert!(
90    ///     StructTree::load_page(&catalog, &page, 1, &NoResolve, &limits, &mut diags).is_some(),
91    /// );
92    ///
93    /// // An untagged document has no tree at all -- a different answer from
94    /// // an empty one.
95    /// assert!(
96    ///     StructTree::load_page(
97    ///         &Dict::default(), &page, 1, &NoResolve, &limits, &mut diags,
98    ///     ).is_none(),
99    /// );
100    /// ```
101    #[must_use]
102    pub fn load_page<R: Resolve>(
103        catalog: &Dict,
104        page: &Dict,
105        page_obj_num: u32,
106        r: &R,
107        limits: &Limits,
108        diags: &mut Diagnostics,
109    ) -> Option<StructTree> {
110        if !is_tagged(catalog, r) {
111            return None;
112        }
113        let root = catalog.dict(names::STRUCT_TREE_ROOT, r);
114        let mut tree = StructTree::default();
115        let Some(root) = root else {
116            return Some(tree);
117        };
118        let role_map = root.dict(names::ROLE_MAP, r);
119
120        let Some(kids) = root.get(names::K, r).map(|k| k.get().clone()) else {
121            return Some(tree);
122        };
123        tree.top = match &kids {
124            Object::Dict(_) => vec![None],
125            Object::Array(array) => vec![None; array.len()],
126            _ => return Some(tree),
127        };
128
129        let Some(parent_tree) = root.dict(names::PARENT_TREE, r) else {
130            return Some(tree);
131        };
132        let parents_id = page.int(names::STRUCT_PARENTS, r).unwrap_or(-1);
133        if parents_id < 0 {
134            return Some(tree);
135        }
136        let entry = number_tree::find(&parent_tree, parents_id, r, limits, diags);
137        let Some(Object::Array(owners)) = entry else {
138            return Some(tree);
139        };
140
141        let mut build = Build {
142            root: &root,
143            root_kids: &kids,
144            role_map: role_map.as_ref(),
145            page_obj_num,
146            memo: Vec::new(),
147        };
148        for index in 0..owners.len() {
149            if let Some(dict) = owners.dict_at(index, r) {
150                let reference = owners.reference_at(index);
151                build.add_page_node(
152                    &mut tree,
153                    Node {
154                        dict: &dict,
155                        reference,
156                    },
157                    0,
158                    r,
159                    limits,
160                    diags,
161                );
162            }
163        }
164        Some(tree)
165    }
166}
167
168/// Whether the catalog claims the document is tagged.
169fn is_tagged<R: Resolve>(catalog: &Dict, r: &R) -> bool {
170    catalog
171        .dict(names::MARK_INFO, r)
172        .and_then(|info| info.int(names::MARKED, r))
173        .is_some_and(|marked| marked != 0)
174}
175
176/// One node the upward walk is about to build: the dictionary and, when it
177/// has one, the reference that named it.
178#[derive(Debug, Clone, Copy)]
179struct Node<'a> {
180    dict: &'a Dict,
181    reference: Option<pdfrum_object::ObjRef>,
182}
183
184/// Scratch state for the upward walk.
185struct Build<'a> {
186    root: &'a Dict,
187    root_kids: &'a Object,
188    role_map: Option<&'a Dict>,
189    page_obj_num: u32,
190    /// Elements already built, keyed by the dictionary that produced them so
191    /// a shared ancestor is visited once.
192    memo: Vec<(Dict, usize)>,
193}
194
195impl Build<'_> {
196    /// Builds `dict`'s element and everything above it, returning its index.
197    fn add_page_node<R: Resolve>(
198        &mut self,
199        tree: &mut StructTree,
200        node: Node,
201        depth: u32,
202        r: &R,
203        limits: &Limits,
204        diags: &mut Diagnostics,
205    ) -> Option<usize> {
206        let Node { dict, reference } = node;
207        if depth > limits.max_name_tree_depth {
208            diags.record(Severity::Suspicious, DiagKind::TreeDepthExceeded, None);
209            return None;
210        }
211        if let Some((_, index)) = self.memo.iter().find(|(seen, _)| seen == dict) {
212            return Some(*index);
213        }
214
215        let kind = dict
216            .name(names::S)
217            .map_or_else(Vec::new, |s| s.as_bytes().to_vec());
218        let element = StructElement {
219            dict: dict.clone(),
220            reference,
221            kind: element::map_role(self.role_map, &kind),
222            kids: StructElement::load_kids(dict, self.page_obj_num, r),
223            parent: None,
224        };
225        let index = tree.elements.len();
226        tree.elements.push(element);
227        self.memo.push((dict.clone(), index));
228
229        // A structure element names its parent `/P`, not `/Parent` — the
230        // latter is the page tree's key and is absent here.
231        let parent = dict.dict(names::P, r);
232        let is_top = match &parent {
233            None => true,
234            Some(p) => p.name(names::TYPE) == Some(names::STRUCT_TREE_ROOT),
235        };
236        if is_top {
237            if !self.add_top_level_node(tree, dict, reference, index) {
238                self.forget(tree, dict, index, diags);
239            }
240            return Some(index);
241        }
242
243        let Some(parent) = parent else {
244            return Some(index);
245        };
246        let parent_ref = dict.reference(names::P);
247        let parent_index = self.add_page_node(
248            tree,
249            Node {
250                dict: &parent,
251                reference: parent_ref,
252            },
253            depth + 1,
254            r,
255            limits,
256            diags,
257        )?;
258        let linked = tree
259            .elements
260            .get_mut(parent_index)
261            .is_some_and(|p| p.link_kid(dict, reference, index));
262        if !linked {
263            self.forget(tree, dict, index, diags);
264            return Some(index);
265        }
266        if let Some(child) = tree.elements.get_mut(index) {
267            child.parent = Some(parent_index);
268        }
269        Some(index)
270    }
271
272    /// Drops an element from the memo so a later path can rebuild it.
273    ///
274    /// The element itself stays in the table — nothing else holds an index
275    /// into it, and removing it would shift every index above.
276    fn forget(
277        &mut self,
278        tree: &mut StructTree,
279        dict: &Dict,
280        index: usize,
281        diags: &mut Diagnostics,
282    ) {
283        self.memo.retain(|(seen, at)| seen != dict || *at != index);
284        let _ = tree;
285        diags.record(Severity::Recovered, DiagKind::StructElementDropped, None);
286    }
287
288    /// Files an element into the root's `/K` slots.
289    ///
290    /// A dictionary-valued `/K` fills slot zero and then **falls through** to
291    /// the array branch, which finds no array and reports success — that is
292    /// why a single top-level element works at all. The array branch matches
293    /// only direct references, so an inline kid is never filed.
294    fn add_top_level_node(
295        &self,
296        tree: &mut StructTree,
297        dict: &Dict,
298        reference: Option<pdfrum_object::ObjRef>,
299        index: usize,
300    ) -> bool {
301        let _ = self.root;
302        match self.root_kids {
303            Object::Dict(root_kid) => {
304                if root_kid != dict {
305                    return false;
306                }
307                if let Some(slot) = tree.top.first_mut() {
308                    *slot = Some(index);
309                }
310                // No array follows, so the fall-through reports success.
311                true
312            }
313            Object::Array(array) => {
314                let mut saved = false;
315                for (slot, item) in array.iter().enumerate() {
316                    if let (Some(item_ref), Some(reference)) = (item.as_ref_id(), reference)
317                        && item_ref.num == reference.num
318                        && let Some(cell) = tree.top.get_mut(slot)
319                    {
320                        *cell = Some(index);
321                        saved = true;
322                    }
323                }
324                saved
325            }
326            _ => true,
327        }
328    }
329}
330
331#[cfg(test)]
332mod tests {
333    use super::StructTree;
334    use pdfrum_common::{Diagnostics, Limits};
335    use pdfrum_object::{Dict, Name, NoResolve, Object};
336
337    fn dict(pairs: &[(&str, Object)]) -> Dict {
338        Dict::from_pairs(
339            pairs
340                .iter()
341                .map(|(k, v)| (Name::from(*k), v.clone()))
342                .collect::<Vec<_>>(),
343        )
344    }
345
346    #[test]
347    fn an_untagged_document_has_no_tree_at_all() {
348        let (l, mut d) = (Limits::default(), Diagnostics::default());
349        assert!(
350            StructTree::load_page(&Dict::new(), &Dict::new(), 0, &NoResolve, &l, &mut d).is_none()
351        );
352    }
353
354    #[test]
355    fn the_marked_flag_reads_as_an_integer_whichever_way_it_is_written() {
356        let (l, mut d) = (Limits::default(), Diagnostics::default());
357        for marked in [Object::Bool(true), Object::Int(1)] {
358            let catalog = dict(&[("MarkInfo", Object::Dict(dict(&[("Marked", marked)])))]);
359            assert!(
360                StructTree::load_page(&catalog, &Dict::new(), 0, &NoResolve, &l, &mut d).is_some()
361            );
362        }
363        // Zero, false, and a non-numeric value all leave it untagged.
364        for marked in [
365            Object::Bool(false),
366            Object::Int(0),
367            Object::Name(Name::from("yes")),
368        ] {
369            let catalog = dict(&[("MarkInfo", Object::Dict(dict(&[("Marked", marked)])))]);
370            assert!(
371                StructTree::load_page(&catalog, &Dict::new(), 0, &NoResolve, &l, &mut d).is_none()
372            );
373        }
374    }
375
376    #[test]
377    fn a_tagged_document_with_no_root_yields_an_empty_tree() {
378        let catalog = dict(&[(
379            "MarkInfo",
380            Object::Dict(dict(&[("Marked", Object::Int(1))])),
381        )]);
382        let (l, mut d) = (Limits::default(), Diagnostics::default());
383        let tree = StructTree::load_page(&catalog, &Dict::new(), 0, &NoResolve, &l, &mut d);
384        assert_eq!(tree, Some(StructTree::default()));
385    }
386}
pdfrum_doc/structure/mod.rs

pdfrum_doc/structure/
mod.rs
