oxipdf-ir 0.1.0

//! The immutable, validated `StyledTree` and its accessors.

use crate::config::ResourceLimits;
use crate::error::InputValidationError;
use crate::node::{ContentVariant, Node, NodeId};
use crate::version::{CURRENT_IR_VERSION, IrVersion};

/// A validated, immutable styled tree ready for layout and emission.
///
/// Constructed via [`StyledTreeBuilder`](super::StyledTreeBuilder). Guarantees:
/// - A single root node exists.
/// - All child references are valid, single-parent, no self-refs.
/// - All nodes are reachable from root.
#[derive(Debug, Clone)]
pub struct StyledTree {
    pub(crate) ir_version: IrVersion,
    pub(crate) nodes: Vec<Node>,
    pub(crate) root: NodeId,
}

impl StyledTree {
    #[must_use]
    pub fn ir_version(&self) -> IrVersion {
        self.ir_version
    }

    #[must_use]
    pub fn root(&self) -> NodeId {
        self.root
    }

    /// # Panics
    /// Panics if `id` does not correspond to a node in this tree.
    #[must_use]
    pub fn node(&self, id: NodeId) -> &Node {
        &self.nodes[id.raw() as usize]
    }

    #[must_use]
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    pub fn iter_nodes(&self) -> impl Iterator<Item = &Node> {
        self.nodes.iter()
    }

    #[must_use]
    pub fn children(&self, id: NodeId) -> &[NodeId] {
        &self.node(id).children
    }

    pub fn walk_preorder(&self, start: NodeId) -> PreorderIter<'_> {
        PreorderIter {
            tree: self,
            stack: vec![start],
        }
    }

    /// Compute depth of a node via BFS from root. O(n) — use for diagnostics only.
    #[must_use]
    pub fn depth(&self, target: NodeId) -> usize {
        let mut queue = std::collections::VecDeque::new();
        queue.push_back((self.root, 0usize));
        while let Some((id, d)) = queue.pop_front() {
            if id == target {
                return d;
            }
            for &child in &self.node(id).children {
                queue.push_back((child, d + 1));
            }
        }
        0
    }

    /// Validate against resource limits and IR version compatibility.
    ///
    /// Separated from `build()` so structural validation (builder) and
    /// policy validation (limits, version) are independent. The engine
    /// calls this during IR ingestion.
    pub fn validate(&self, limits: &ResourceLimits) -> Result<(), InputValidationError> {
        if !self.ir_version.is_compatible_with(CURRENT_IR_VERSION) {
            return Err(InputValidationError::IncompatibleVersion {
                tree_version: self.ir_version,
                engine_version: CURRENT_IR_VERSION,
            });
        }

        let count = self.nodes.len() as u64;
        if count > limits.max_node_count as u64 {
            return Err(InputValidationError::ResourceLimitExceeded {
                limit_name: "node_count",
                current: count,
                max: limits.max_node_count as u64,
                node_path: vec![],
            });
        }

        // Max depth via BFS — also track the deepest node for diagnostics.
        let mut max_depth: u32 = 0;
        let mut deepest_node = self.root;
        let mut queue = std::collections::VecDeque::new();
        queue.push_back((self.root, 0u32));
        while let Some((id, d)) = queue.pop_front() {
            if d > max_depth {
                max_depth = d;
                deepest_node = id;
            }
            for &child in &self.node(id).children {
                queue.push_back((child, d + 1));
            }
        }
        if max_depth > limits.max_tree_depth {
            // Build path to deepest node for diagnostics.
            let depth_path = crate::diagnostics::build_node_path(self, deepest_node);
            return Err(InputValidationError::ResourceLimitExceeded {
                limit_name: "tree_depth",
                current: max_depth as u64,
                max: limits.max_tree_depth as u64,
                node_path: depth_path,
            });
        }

        // Total text bytes.
        let mut total_text_bytes: u64 = 0;
        for node in &self.nodes {
            if let ContentVariant::Text(ref text) = node.content {
                total_text_bytes += text.text.len() as u64;
            }
        }
        if total_text_bytes > limits.max_text_bytes {
            return Err(InputValidationError::ResourceLimitExceeded {
                limit_name: "text_bytes",
                current: total_text_bytes,
                max: limits.max_text_bytes,
                node_path: vec![],
            });
        }

        Ok(())
    }
}

impl StyledTree {
    /// Extract a subtree containing only the root node and the specified
    /// top-level children (plus all their descendants).
    ///
    /// Used by the chunked rendering pipeline to create an independent
    /// subtree for each chunk. The returned tree has new `NodeId`s —
    /// use the returned `NodeId` mapping to translate between original
    /// and subtree IDs.
    ///
    /// Returns `(subtree, old_to_new_id_map)`.
    #[must_use]
    pub fn extract_chunk_subtree(
        &self,
        chunk_children: &[NodeId],
    ) -> (StyledTree, Vec<Option<NodeId>>) {
        let mut id_map: Vec<Option<NodeId>> = vec![None; self.nodes.len()];
        let mut new_nodes: Vec<Node> = Vec::new();

        // Clone the root node, but with only the chunk's children.
        let root = self.node(self.root);
        let new_root_id = NodeId::from_raw(0);
        id_map[self.root.raw() as usize] = Some(new_root_id);
        new_nodes.push(Node {
            id: new_root_id,
            content: root.content.clone(),
            style: root.style.clone(),
            children: Vec::new(), // populated below
            semantic_role: root.semantic_role,
            element_id: root.element_id.clone(),
        });

        // BFS to clone each chunk child and all descendants.
        let mut queue = std::collections::VecDeque::new();
        for &child_id in chunk_children {
            queue.push_back(child_id);
        }

        while let Some(old_id) = queue.pop_front() {
            let old_node = self.node(old_id);
            let new_id = NodeId::from_raw(new_nodes.len() as u32);
            id_map[old_id.raw() as usize] = Some(new_id);

            new_nodes.push(Node {
                id: new_id,
                content: old_node.content.clone(),
                style: old_node.style.clone(),
                children: Vec::new(), // populated in second pass
                semantic_role: old_node.semantic_role,
                element_id: old_node.element_id.clone(),
            });

            for &grandchild in &old_node.children {
                queue.push_back(grandchild);
            }
        }

        // Second pass: wire children using the id map.
        // Root's children are the chunk_children.
        let root_new_children: Vec<NodeId> = chunk_children
            .iter()
            .map(|old| id_map[old.raw() as usize].unwrap())
            .collect();
        new_nodes[0].children = root_new_children;

        // Wire each non-root node's children.
        for &old_id in chunk_children {
            self.wire_children_recursive(old_id, &id_map, &mut new_nodes);
        }

        // Strip break_before from the chunk's top-level children.
        // The chunk boundary is the implicit page break; keeping
        // break_before: Always would create a spurious empty page
        // at the start of each chunk's paginated output.
        let root_new_children: Vec<NodeId> = new_nodes[0].children.clone();
        for &child_new_id in &root_new_children {
            new_nodes[child_new_id.raw() as usize]
                .style
                .fragmentation
                .break_before = crate::style::fragmentation::BreakValue::Auto;
        }

        let subtree = StyledTree {
            ir_version: self.ir_version,
            nodes: new_nodes,
            root: new_root_id,
        };

        (subtree, id_map)
    }

    /// Recursively wire children for `extract_chunk_subtree`.
    fn wire_children_recursive(
        &self,
        old_id: NodeId,
        id_map: &[Option<NodeId>],
        new_nodes: &mut [Node],
    ) {
        let old_node = self.node(old_id);
        let new_id = id_map[old_id.raw() as usize].unwrap();
        let new_children: Vec<NodeId> = old_node
            .children
            .iter()
            .map(|old_child| id_map[old_child.raw() as usize].unwrap())
            .collect();
        new_nodes[new_id.raw() as usize].children = new_children;

        for &child_id in &old_node.children {
            self.wire_children_recursive(child_id, id_map, new_nodes);
        }
    }
}

impl StyledTree {
    /// Propagate inheritable typography properties from parent to child.
    ///
    /// Walks the tree in pre-order. For each child, if an inheritable property
    /// is at its default value, it receives the parent's resolved value.
    ///
    /// Inheritable properties (CSS-like): font_families, font_size,
    /// font_weight, font_style, color, line_height, text_align, direction,
    /// letter_spacing, word_spacing.
    pub(crate) fn apply_style_inheritance(&mut self) {
        // Collect children in BFS order to avoid borrow conflicts.
        let mut work: Vec<(NodeId, NodeId)> = Vec::new(); // (parent, child)
        let mut queue = std::collections::VecDeque::new();
        queue.push_back(self.root);
        while let Some(parent_id) = queue.pop_front() {
            let children: Vec<NodeId> = self.nodes[parent_id.raw() as usize].children.clone();
            for &child_id in &children {
                work.push((parent_id, child_id));
                queue.push_back(child_id);
            }
        }

        let typo_default = crate::style::typography::TypographyStyle::default();

        for (parent_id, child_id) in work {
            let parent_typo = self.nodes[parent_id.raw() as usize]
                .style
                .typography
                .clone();
            let child = &mut self.nodes[child_id.raw() as usize];
            let ct = &mut child.style.typography;

            if ct.font_families.is_empty() && !parent_typo.font_families.is_empty() {
                ct.font_families = parent_typo.font_families.clone();
            }
            if ct.font_size == typo_default.font_size
                && parent_typo.font_size != typo_default.font_size
            {
                ct.font_size = parent_typo.font_size;
            }
            if ct.font_weight == typo_default.font_weight
                && parent_typo.font_weight != typo_default.font_weight
            {
                ct.font_weight = parent_typo.font_weight;
            }
            if ct.font_style == typo_default.font_style
                && parent_typo.font_style != typo_default.font_style
            {
                ct.font_style = parent_typo.font_style;
            }
            if ct.color == typo_default.color && parent_typo.color != typo_default.color {
                ct.color = parent_typo.color;
            }
            if ct.line_height == typo_default.line_height
                && parent_typo.line_height != typo_default.line_height
            {
                ct.line_height = parent_typo.line_height;
            }
            if ct.text_align == typo_default.text_align
                && parent_typo.text_align != typo_default.text_align
            {
                ct.text_align = parent_typo.text_align;
            }
            if ct.direction == typo_default.direction
                && parent_typo.direction != typo_default.direction
            {
                ct.direction = parent_typo.direction;
            }
            if ct.letter_spacing == typo_default.letter_spacing
                && parent_typo.letter_spacing != typo_default.letter_spacing
            {
                ct.letter_spacing = parent_typo.letter_spacing;
            }
            if ct.word_spacing == typo_default.word_spacing
                && parent_typo.word_spacing != typo_default.word_spacing
            {
                ct.word_spacing = parent_typo.word_spacing;
            }
        }
    }
}

/// Depth-first pre-order iterator over a `StyledTree`.
pub struct PreorderIter<'a> {
    tree: &'a StyledTree,
    stack: Vec<NodeId>,
}

impl<'a> Iterator for PreorderIter<'a> {
    type Item = NodeId;

    fn next(&mut self) -> Option<NodeId> {
        let id = self.stack.pop()?;
        let children = &self.tree.node(id).children;
        for &child in children.iter().rev() {
            self.stack.push(child);
        }
        Some(id)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::node::TextContent;
    use crate::semantic::SemanticRole;
    use crate::style::ResolvedStyle;
    use crate::tree::StyledTreeBuilder;
    use crate::version::IrVersion;

    fn sample_tree() -> StyledTree {
        let mut b = StyledTreeBuilder::new(IrVersion::new(1, 0));
        let root = b.add_node(
            ContentVariant::Container,
            ResolvedStyle::default(),
            Some(SemanticRole::Document),
            None,
        );
        b.add_child(
            root,
            ContentVariant::Text(TextContent::new("First paragraph")),
            ResolvedStyle::default(),
            Some(SemanticRole::Paragraph),
            None,
        );
        b.add_child(
            root,
            ContentVariant::Text(TextContent::new("Second paragraph")),
            ResolvedStyle::default(),
            Some(SemanticRole::Paragraph),
            Some("section-2".into()),
        );
        b.build().unwrap()
    }

    #[test]
    fn build_and_query() {
        let tree = sample_tree();
        assert_eq!(tree.node_count(), 3);
        assert_eq!(tree.ir_version(), IrVersion::new(1, 0));
        assert_eq!(tree.children(tree.root()).len(), 2);
    }

    #[test]
    fn preorder_traversal() {
        let tree = sample_tree();
        let ids: Vec<NodeId> = tree.walk_preorder(tree.root()).collect();
        assert_eq!(ids.len(), 3);
        assert_eq!(ids[0], tree.root());
    }

    #[test]
    fn depth_calculation() {
        let tree = sample_tree();
        assert_eq!(tree.depth(tree.root()), 0);
        let children = tree.children(tree.root());
        assert_eq!(tree.depth(children[0]), 1);
        assert_eq!(tree.depth(children[1]), 1);
    }

    #[test]
    fn element_id_stored() {
        let tree = sample_tree();
        let children = tree.children(tree.root());
        assert_eq!(tree.node(children[0]).element_id, None);
        assert_eq!(
            tree.node(children[1]).element_id.as_deref(),
            Some("section-2")
        );
    }

    #[test]
    fn validate_passes_within_limits() {
        assert!(sample_tree().validate(&ResourceLimits::default()).is_ok());
    }

    #[test]
    fn validate_node_count_exceeded() {
        let tree = sample_tree();
        let limits = ResourceLimits {
            max_node_count: 2,
            ..ResourceLimits::default()
        };
        match tree.validate(&limits).unwrap_err() {
            InputValidationError::ResourceLimitExceeded {
                limit_name,
                current,
                max,
                ..
            } => {
                assert_eq!(limit_name, "node_count");
                assert_eq!(current, 3);
                assert_eq!(max, 2);
            }
            other => panic!("expected ResourceLimitExceeded, got {other:?}"),
        }
    }

    #[test]
    fn validate_tree_depth_exceeded() {
        let mut b = StyledTreeBuilder::new(IrVersion::new(1, 0));
        let root = b.add_node(
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        let a = b.add_child(
            root,
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        let b_node = b.add_child(
            a,
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        b.add_child(
            b_node,
            ContentVariant::Text(TextContent::new("deep")),
            ResolvedStyle::default(),
            None,
            None,
        );
        let tree = b.build().unwrap();

        let limits = ResourceLimits {
            max_tree_depth: 2,
            ..ResourceLimits::default()
        };
        match tree.validate(&limits).unwrap_err() {
            InputValidationError::ResourceLimitExceeded {
                limit_name,
                current,
                max,
                node_path,
                ..
            } => {
                assert_eq!(limit_name, "tree_depth");
                assert_eq!(current, 3);
                assert_eq!(max, 2);
                // Path should trace from root to the deepest node.
                assert!(!node_path.is_empty());
                assert_eq!(node_path[0], NodeId::from_raw(0)); // root
            }
            other => panic!("expected ResourceLimitExceeded, got {other:?}"),
        }
    }

    #[test]
    fn validate_text_bytes_exceeded() {
        let mut b = StyledTreeBuilder::new(IrVersion::new(1, 0));
        let root = b.add_node(
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        b.add_child(
            root,
            ContentVariant::Text(TextContent::new("Hello, world!")),
            ResolvedStyle::default(),
            None,
            None,
        );
        let tree = b.build().unwrap();

        let limits = ResourceLimits {
            max_text_bytes: 10,
            ..ResourceLimits::default()
        };
        match tree.validate(&limits).unwrap_err() {
            InputValidationError::ResourceLimitExceeded {
                limit_name,
                current,
                max,
                ..
            } => {
                assert_eq!(limit_name, "text_bytes");
                assert_eq!(current, 13);
                assert_eq!(max, 10);
            }
            other => panic!("expected ResourceLimitExceeded, got {other:?}"),
        }
    }

    #[test]
    fn validate_version_incompatible() {
        let mut b = StyledTreeBuilder::new(IrVersion::new(2, 0));
        b.add_node(
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        let tree = b.build().unwrap();
        assert!(matches!(
            tree.validate(&ResourceLimits::default()).unwrap_err(),
            InputValidationError::IncompatibleVersion { .. }
        ));
    }

    #[test]
    fn validate_unlimited_passes_anything() {
        assert!(sample_tree().validate(&ResourceLimits::unlimited()).is_ok());
    }
}