otf_pdf_doc/
pages.rs

1//! The page tree (§7.7.3), with inherited attributes.
2
3use std::collections::HashSet;
4
5use otf_pdf_syntax::{DiagnosticKind, Dict, Error, LimitKind, ObjId, Object, Result, Strictness};
6
7use crate::store::Store;
8
9/// A rectangle `[llx lly urx ury]`, normalized so `llx <= urx` and
10/// `lly <= ury`.
11#[derive(Debug, Clone, Copy, PartialEq)]
12pub struct Rect {
13    /// Lower-left x.
14    pub llx: f64,
15    /// Lower-left y.
16    pub lly: f64,
17    /// Upper-right x.
18    pub urx: f64,
19    /// Upper-right y.
20    pub ury: f64,
21}
22
23impl Rect {
24    /// US Letter, the default when a page has no usable `/MediaBox`.
25    pub const LETTER: Rect = Rect {
26        llx: 0.0,
27        lly: 0.0,
28        urx: 612.0,
29        ury: 792.0,
30    };
31
32    /// A rectangle from a PDF array, normalized; `None` unless it has four
33    /// finite numbers.
34    pub fn from_array(items: &[Object]) -> Option<Rect> {
35        let [a, b, c, d] = items else { return None };
36        let n = |o: &Object| o.as_f64().filter(|v| v.is_finite());
37        let (a, b, c, d) = (n(a)?, n(b)?, n(c)?, n(d)?);
38        Some(Rect {
39            llx: a.min(c),
40            lly: b.min(d),
41            urx: a.max(c),
42            ury: b.max(d),
43        })
44    }
45
46    /// Width.
47    pub fn width(&self) -> f64 {
48        self.urx - self.llx
49    }
50
51    /// Height.
52    pub fn height(&self) -> f64 {
53        self.ury - self.lly
54    }
55
56    /// The intersection with `other`, or `None` if they do not overlap.
57    pub fn intersect(&self, other: &Rect) -> Option<Rect> {
58        let r = Rect {
59            llx: self.llx.max(other.llx),
60            lly: self.lly.max(other.lly),
61            urx: self.urx.min(other.urx),
62            ury: self.ury.min(other.ury),
63        };
64        (r.llx < r.urx && r.lly < r.ury).then_some(r)
65    }
66}
67
68/// One page, with inherited attributes resolved.
69#[derive(Debug, Clone, PartialEq)]
70pub struct Page {
71    /// The page object's id, or `None` for a direct page dictionary in a
72    /// `/Kids` array (invalid, but tolerated).
73    pub id: Option<ObjId>,
74    /// The page dictionary.
75    pub dict: Dict,
76    /// `/MediaBox`, inherited, defaulting to US Letter.
77    pub media_box: Rect,
78    /// `/CropBox`, inherited, clipped to the media box; defaults to it.
79    pub crop_box: Rect,
80    /// `/Rotate`, inherited, normalized to 0, 90, 180 or 270.
81    pub rotate: u16,
82    /// `/Resources`, inherited and resolved, if any.
83    pub resources: Option<Dict>,
84}
85
86/// Attributes a page inherits from its ancestors (§7.7.3.4).
87#[derive(Debug, Clone, Default)]
88struct Inherited {
89    resources: Option<Object>,
90    media_box: Option<Object>,
91    crop_box: Option<Object>,
92    rotate: Option<Object>,
93}
94
95impl Inherited {
96    fn with(&self, node: &Dict) -> Inherited {
97        let pick =
98            |key: &[u8], parent: &Option<Object>| node.get(key).cloned().or_else(|| parent.clone());
99        Inherited {
100            resources: pick(b"Resources", &self.resources),
101            media_box: pick(b"MediaBox", &self.media_box),
102            crop_box: pick(b"CropBox", &self.crop_box),
103            rotate: pick(b"Rotate", &self.rotate),
104        }
105    }
106}
107
108fn is_pages_node(dict: &Dict) -> bool {
109    dict.is_type(b"Pages") || (!dict.is_type(b"Page") && dict.contains_key(b"Kids"))
110}
111
112/// Walks the page tree from the catalog's `/Pages`. In lenient mode a broken
113/// tree falls back to every `/Type /Page` object in the file.
114pub fn collect_pages(file: &Store, catalog: &Dict) -> Result<Vec<Page>> {
115    let walked = match catalog.get(b"Pages") {
116        Some(root) => walk(file, root),
117        None => Err(Error::syntax(0, "catalog has no /Pages")),
118    };
119    match walked {
120        Ok(pages) if !pages.is_empty() => Ok(pages),
121        Err(e @ Error::Limit(_)) => Err(e),
122        other => {
123            if file.strictness() == Strictness::Strict {
124                return other;
125            }
126            let found = scan_for_pages(file)?;
127            if found.is_empty() {
128                return other;
129            }
130            file.diagnostics_sink()
131                .push(DiagnosticKind::PagesRecovered, None, None);
132            Ok(found)
133        }
134    }
135}
136
137fn walk(file: &Store, root: &Object) -> Result<Vec<Page>> {
138    let limits = file.limits();
139    let mut pages = Vec::new();
140    let mut visited: HashSet<ObjId> = HashSet::new();
141    // (node, inherited attributes, depth); kids are pushed in reverse so
142    // pages come out in document order.
143    let mut stack: Vec<(Object, Inherited, u32)> = vec![(root.clone(), Inherited::default(), 0)];
144    while let Some((node, inherited, depth)) = stack.pop() {
145        limits.charge(1)?;
146        if depth > limits.max_depth {
147            return Err(Error::Limit(LimitKind::Depth));
148        }
149        let id = node.as_ref();
150        if let Some(id) = id
151            && !visited.insert(id)
152        {
153            // A cycle, or a node listed twice.
154            bad_node(file, Some(id))?;
155            continue;
156        }
157        let Some(dict) = file.resolve_dict(&node) else {
158            bad_node(file, id)?;
159            continue;
160        };
161        let attrs = inherited.with(&dict);
162        if is_pages_node(&dict) {
163            let raw_kids = dict.get(b"Kids").cloned().unwrap_or_default();
164            let kids = match file.resolve(&raw_kids) {
165                Object::Array(kids) => kids,
166                // A lone reference instead of an array: one kid.
167                Object::Dict(_) if file.strictness() == Strictness::Lenient => {
168                    bad_node(file, id)?;
169                    vec![raw_kids]
170                }
171                _ => {
172                    bad_node(file, id)?;
173                    continue;
174                }
175            };
176            for kid in kids.iter().rev() {
177                stack.push((kid.clone(), attrs.clone(), depth + 1));
178            }
179        } else {
180            if pages.len() >= limits.max_pages as usize {
181                return Err(Error::Limit(LimitKind::Pages));
182            }
183            pages.push(make_page(file, id, dict, &attrs));
184        }
185    }
186    Ok(pages)
187}
188
189fn bad_node(file: &Store, id: Option<ObjId>) -> Result<()> {
190    if file.strictness() == Strictness::Strict {
191        return Err(Error::syntax(0, "bad page tree node"));
192    }
193    file.diagnostics_sink()
194        .push(DiagnosticKind::BadPageTree, None, id);
195    Ok(())
196}
197
198fn make_page(file: &Store, id: Option<ObjId>, dict: Dict, attrs: &Inherited) -> Page {
199    let rect = |o: &Option<Object>| {
200        o.as_ref()
201            .map(|o| file.resolve(o))
202            .and_then(|o| o.as_array().and_then(Rect::from_array))
203    };
204    let media_box = rect(&attrs.media_box).unwrap_or(Rect::LETTER);
205    let crop_box = rect(&attrs.crop_box)
206        .and_then(|c| c.intersect(&media_box))
207        .unwrap_or(media_box);
208    let rotate = attrs
209        .rotate
210        .as_ref()
211        .and_then(|o| file.resolve(o).as_int())
212        .map(|r| r.rem_euclid(360))
213        .filter(|r| r % 90 == 0)
214        .unwrap_or(0) as u16;
215    let resources = attrs.resources.as_ref().and_then(|r| file.resolve_dict(r));
216    Page {
217        id,
218        dict,
219        media_box,
220        crop_box,
221        rotate,
222        resources,
223    }
224}
225
226/// Every object with `/Type /Page`, in object-number order: the fallback
227/// for a page tree that yields nothing.
228fn scan_for_pages(file: &Store) -> Result<Vec<Page>> {
229    let mut pages = Vec::new();
230    for id in file.object_ids() {
231        file.limits().charge(1)?;
232        let Ok(obj) = file.get(id) else {
233            continue;
234        };
235        let Some(dict) = obj.as_dict() else { continue };
236        if dict.is_type(b"Page") {
237            if pages.len() >= file.limits().max_pages as usize {
238                return Err(Error::Limit(LimitKind::Pages));
239            }
240            // Inherit from the parent chain where it exists.
241            let mut attrs = Inherited::default();
242            let mut chain = Vec::new();
243            let mut parent = dict.get(b"Parent").cloned();
244            let mut seen = HashSet::new();
245            while let Some(p) = parent.take() {
246                if p.as_ref().is_some_and(|id| !seen.insert(id)) || chain.len() > 64 {
247                    break;
248                }
249                let Some(pd) = file.resolve_dict(&p) else {
250                    break;
251                };
252                parent = pd.get(b"Parent").cloned();
253                chain.push(pd);
254            }
255            for ancestor in chain.iter().rev() {
256                attrs = attrs.with(ancestor);
257            }
258            let attrs = attrs.with(dict);
259            pages.push(make_page(file, Some(id), dict.clone(), &attrs));
260        }
261    }
262    Ok(pages)
263}
264
265impl Rect {
266    /// The rectangle as a PDF array.
267    pub fn to_object(&self) -> Object {
268        Object::Array(vec![
269            Object::Real(self.llx),
270            Object::Real(self.lly),
271            Object::Real(self.urx),
272            Object::Real(self.ury),
273        ])
274    }
275}
276
277/// The page's dictionary with its inherited attributes written into it and
278/// `/Parent` removed, so it can be placed under any parent (or copied into
279/// another document) without losing its boxes, rotation or resources.
280pub fn standalone_page_dict(page: &Page) -> Dict {
281    let mut dict = page.dict.clone();
282    dict.remove(b"Parent");
283    dict.insert("Type", otf_pdf_syntax::Name::from("Page"));
284    dict.insert("MediaBox", page.media_box.to_object());
285    if page.crop_box != page.media_box {
286        dict.insert("CropBox", page.crop_box.to_object());
287    } else {
288        dict.remove(b"CropBox");
289    }
290    if page.rotate != 0 {
291        dict.insert("Rotate", i64::from(page.rotate));
292    } else {
293        dict.remove(b"Rotate");
294    }
295    if !dict.contains_key(b"Resources")
296        && let Some(res) = &page.resources
297    {
298        dict.insert("Resources", res.clone());
299    }
300    dict
301}
302
303/// Whether the catalog's page tree is sound as written: every node is an
304/// indirect object of the right type, every `/Kids` is an array of
305/// references, no node appears twice, and the leaves are exactly `pages`, in
306/// order. A full save rewrites any tree that is not.
307pub fn tree_is_sound(store: &Store, catalog: &Dict, pages: &[Page]) -> bool {
308    let Some(root) = catalog.get_ref(b"Pages") else {
309        return false;
310    };
311    let mut leaves = Vec::with_capacity(pages.len());
312    let mut seen = HashSet::new();
313    let mut stack = vec![(root, true, 0u32)];
314    while let Some((id, must_be_tree, depth)) = stack.pop() {
315        if depth > store.limits().max_depth || !seen.insert(id) || store.limits().charge(1).is_err()
316        {
317            return false;
318        }
319        let Ok(obj) = store.get(id) else { return false };
320        let Some(dict) = obj.as_dict() else {
321            return false;
322        };
323        if dict.is_type(b"Pages") {
324            let Some(kids) = store
325                .resolve(dict.get(b"Kids").unwrap_or(&Object::Null))
326                .as_array()
327                .map(<[_]>::to_vec)
328            else {
329                return false;
330            };
331            for kid in kids.iter().rev() {
332                let Some(kid) = kid.as_ref() else {
333                    return false;
334                };
335                stack.push((kid, false, depth + 1));
336            }
337        } else if dict.is_type(b"Page") && !must_be_tree {
338            leaves.push(id);
339        } else {
340            return false;
341        }
342    }
343    leaves.len() == pages.len() && leaves.iter().zip(pages).all(|(l, p)| p.id == Some(*l))
344}
345
346#[cfg(test)]
347mod tests {
348    use super::*;
349
350    #[test]
351    fn rect_normalizes_and_intersects() {
352        let r = Rect::from_array(&[
353            Object::Int(612),
354            Object::Int(792),
355            Object::Int(0),
356            Object::Real(0.0),
357        ])
358        .unwrap();
359        assert_eq!(r, Rect::LETTER);
360        assert_eq!(r.width(), 612.0);
361        assert_eq!(r.height(), 792.0);
362        assert!(Rect::from_array(&[Object::Int(1)]).is_none());
363        assert!(
364            Rect::from_array(&[
365                Object::Int(0),
366                Object::Int(0),
367                Object::Real(f64::NAN),
368                Object::Int(1)
369            ])
370            .is_none()
371        );
372        let small = Rect {
373            llx: 10.0,
374            lly: 10.0,
375            urx: 1000.0,
376            ury: 20.0,
377        };
378        assert_eq!(
379            small.intersect(&Rect::LETTER),
380            Some(Rect {
381                llx: 10.0,
382                lly: 10.0,
383                urx: 612.0,
384                ury: 20.0
385            })
386        );
387        let outside = Rect {
388            llx: 700.0,
389            lly: 0.0,
390            urx: 800.0,
391            ury: 10.0,
392        };
393        assert_eq!(outside.intersect(&Rect::LETTER), None);
394    }
395}
otf_pdf_doc/pages.rs

otf_pdf_doc/
pages.rs
