Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

4.8 KB
Raw Blame
//! The page tree (ISO 32000-1 §7.7.3): pages in order with the attributes
//! they inherit. Cycles, broken `Kids`, and wrong `Count`s are tolerated;
//! a file whose tree yields no pages falls back to its `Page` objects.

use super::{Dict, Object, PageRef, Pdf};

/// Attributes pages inherit from their ancestors.
const INHERITED: [&str; 4] = ["Resources", "MediaBox", "CropBox", "Rotate"];

/// How many nodes a walk visits at most (a tree that is really a graph
/// with shared subtrees could otherwise explode).
const MAX_NODES: usize = 1 << 18;

/// How deep the tree may be.
const MAX_DEPTH: usize = 256;

/// Inheritable attributes, by [`INHERITED`] index.
#[derive(Clone, Default)]
struct Inherited([Option<Object>; 4]);

impl Inherited {
    /// These, overridden by what `node` sets.
    fn with(&self, node: &Dict) -> Inherited {
        let mut out = self.clone();
        for (slot, key) in out.0.iter_mut().zip(INHERITED) {
            if let Some(v) = node.get(key) {
                *slot = Some(v.clone());
            }
        }
        out
    }

    /// `page` with what it lacks filled in.
    fn apply(&self, mut page: Dict) -> Dict {
        for (slot, key) in self.0.iter().zip(INHERITED) {
            if let Some(v) = slot
                && !page.contains(key)
            {
                page.set(key, v.clone());
            }
        }
        page
    }
}

/// An intermediate node being walked.
struct Frame {
    num: Option<u32>,
    kids: Vec<Object>,
    next: usize,
    inherited: Inherited,
}

/// Whether a node has kids rather than being a page (untyped nodes go by
/// whether they have `Kids`).
fn is_tree_node(dict: &Dict) -> bool {
    dict.is("Type", "Pages") || (!dict.is("Type", "Page") && dict.contains("Kids"))
}

impl Pdf {
    /// The pages, in order.
    pub(super) fn page_tree(&self) -> Vec<PageRef> {
        let mut pages = Vec::new();
        if let Some(root) = self.catalog().and_then(|c| c.get("Pages").cloned()) {
            self.walk(root, &mut pages);
        }
        if pages.is_empty() {
            self.loose_pages(&mut pages);
        }
        pages
    }

    /// Depth first from `root`; a node that is its own ancestor is skipped.
    fn walk(&self, root: Object, out: &mut Vec<PageRef>) {
        let mut stack: Vec<Frame> = Vec::new();
        let mut visits = 0;
        let mut pending = Some((root, Inherited::default()));
        loop {
            if let Some((node, inherited)) = pending.take() {
                visits += 1;
                if visits > MAX_NODES {
                    break;
                }
                let num = node.as_ref().map(|r| r.num);
                if num.is_some_and(|n| stack.iter().any(|f| f.num == Some(n))) {
                    continue;
                }
                let Object::Dict(dict) = self.resolve(&node) else {
                    continue;
                };
                if is_tree_node(&dict) {
                    if stack.len() < MAX_DEPTH {
                        let kids = match dict.get("Kids").map(|k| self.resolve(k)) {
                            Some(Object::Array(kids)) => kids,
                            _ => Vec::new(),
                        };
                        stack.push(Frame {
                            num,
                            kids,
                            next: 0,
                            inherited: inherited.with(&dict),
                        });
                    }
                } else if let Some(obj) = node.as_ref() {
                    out.push(PageRef {
                        obj,
                        dict: inherited.apply(dict),
                    });
                }
                continue;
            }
            let Some(top) = stack.last_mut() else {
                break;
            };
            match top.kids.get(top.next) {
                Some(kid) => {
                    top.next += 1;
                    pending = Some((kid.clone(), top.inherited.clone()));
                }
                None => {
                    stack.pop();
                }
            }
        }
    }

    /// Every object typed `Page`, by number, inheriting through `Parent`.
    fn loose_pages(&self, out: &mut Vec<PageRef>) {
        for r in self.object_refs() {
            let Some(Object::Dict(mut dict)) = self.get(r) else {
                continue;
            };
            if !dict.is("Type", "Page") {
                continue;
            }
            let mut parent = dict.get("Parent").cloned();
            for _ in 0..MAX_DEPTH {
                let Some(Object::Dict(node)) = parent.map(|p| self.resolve(&p)) else {
                    break;
                };
                dict = Inherited::default().with(&node).apply(dict);
                parent = node.get("Parent").cloned();
            }
            out.push(PageRef { obj: r, dict });
        }
    }
}