oxipdf-ir 0.1.0

//! Diagnostic helpers for tracing node context through the IR tree.
//!
//! Provides `NodePath` and `build_node_path` for producing human-readable
//! and machine-readable node location context in error messages. Every
//! structured error that references a specific node can include its full
//! path from root, enabling consumers to locate the problem without
//! searching the tree themselves.

use crate::node::NodeId;
use crate::tree::StyledTree;

/// A path from the tree root to a specific node, expressed as an ordered
/// list of `NodeId`s. The first element is always the root; the last is
/// the target node.
///
/// ```text
/// NodePath: [node#0, node#3, node#12, node#45]
///           root    section  paragraph target
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct NodePath {
    /// Node IDs from root to target, inclusive.
    pub segments: Vec<NodeId>,
}

impl NodePath {
    /// Create an empty path (used when no path context is available).
    #[must_use]
    pub fn empty() -> Self {
        Self {
            segments: Vec::new(),
        }
    }

    /// Create a path from a pre-computed segment list.
    #[must_use]
    pub fn from_segments(segments: Vec<NodeId>) -> Self {
        Self { segments }
    }

    /// The depth of the target node (0 = root).
    #[must_use]
    pub fn depth(&self) -> usize {
        self.segments.len().saturating_sub(1)
    }

    /// Whether this path contains any segments.
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.segments.is_empty()
    }
}

impl std::fmt::Display for NodePath {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.segments.is_empty() {
            return write!(f, "<no path>");
        }
        for (i, id) in self.segments.iter().enumerate() {
            if i > 0 {
                write!(f, " > ")?;
            }
            write!(f, "{id}")?;
        }
        Ok(())
    }
}

/// Build a path from the root of `tree` to `target`.
///
/// Walks the tree from root via BFS, tracking parent pointers, then
/// reconstructs the path by following parents from target back to root.
///
/// Returns an empty `Vec` if `target` is not found in the tree (which
/// should not happen for valid trees, but defensive code never panics).
///
/// This is O(n) — intended for diagnostics only, not hot paths.
#[must_use]
pub fn build_node_path(tree: &StyledTree, target: NodeId) -> Vec<NodeId> {
    let node_count = tree.node_count();
    if node_count == 0 {
        return Vec::new();
    }

    // Parent map: parent_of[child_raw] = Some(parent_id).
    let mut parent_of: Vec<Option<NodeId>> = vec![None; node_count];
    let mut found = false;

    let mut queue = std::collections::VecDeque::new();
    queue.push_back(tree.root());

    while let Some(id) = queue.pop_front() {
        if id == target {
            found = true;
        }
        for &child in &tree.node(id).children {
            parent_of[child.raw() as usize] = Some(id);
            queue.push_back(child);
        }
    }

    if !found {
        return Vec::new();
    }

    // Walk from target back to root.
    let mut path = vec![target];
    let mut current = target;
    while let Some(parent) = parent_of[current.raw() as usize] {
        path.push(parent);
        current = parent;
    }
    path.reverse();
    path
}

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

    #[test]
    fn build_path_to_root() {
        let mut b = StyledTreeBuilder::new(IrVersion::new(1, 0));
        b.add_node(
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        let tree = b.build().unwrap();
        let path = build_node_path(&tree, tree.root());
        assert_eq!(path, vec![NodeId::from_raw(0)]);
    }

    #[test]
    fn build_path_to_deep_node() {
        let mut b = StyledTreeBuilder::new(IrVersion::new(1, 0));
        let root = b.add_node(
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        let mid = b.add_child(
            root,
            ContentVariant::Container,
            ResolvedStyle::default(),
            None,
            None,
        );
        let leaf = b.add_child(
            mid,
            ContentVariant::Text(TextContent::new("deep")),
            ResolvedStyle::default(),
            None,
            None,
        );
        let tree = b.build().unwrap();
        let path = build_node_path(&tree, leaf);
        assert_eq!(
            path,
            vec![
                NodeId::from_raw(0),
                NodeId::from_raw(1),
                NodeId::from_raw(2),
            ]
        );
    }

    #[test]
    fn node_path_display() {
        let np = NodePath::from_segments(vec![
            NodeId::from_raw(0),
            NodeId::from_raw(3),
            NodeId::from_raw(7),
        ]);
        assert_eq!(np.to_string(), "node#0 > node#3 > node#7");
        assert_eq!(np.depth(), 2);
    }

    #[test]
    fn empty_node_path_display() {
        let np = NodePath::empty();
        assert_eq!(np.to_string(), "<no path>");
        assert!(np.is_empty());
        assert_eq!(np.depth(), 0);
    }
}