zerodds-idl 1.0.0-rc.1

// SPDX-License-Identifier: Apache-2.0
// Copyright 2026 ZeroDDS Contributors
//! Tree-Traversal-Helper fuer den CST.
//!
//! Alle Helper kollektieren `Vec<&CstNode>`-Refs (eager). Lazy-Iteratoren
//! waeren idiomatischer, verlangen aber Stack-State und kosten Klarheit.
//! Fuer IDL-typische Tree-Groessen (einige hundert bis wenige tausend
//! Knoten) ist die Eager-Sammlung in Praxis irrelevant.
//!
//! API-Familien:
//!
//! - **Reihenfolge-Traversal**: [`preorder`], [`postorder`]
//! - **Typ-Filter**: [`tokens_only`], [`internals_only`]
//! - **Such-Helper**: [`find_by_production`], [`find_first_by_production`],
//!   [`find_by_token_kind`], [`count_by_production`]
//! - **Struktur-Metrik**: [`depth`]
//!
//! Siehe RFC 0001 §5.4.

use crate::grammar::{ProductionId, TokenKind};

use super::node::CstNode;

/// Pre-order Depth-First-Traversal: root → children left-to-right.
#[must_use]
pub fn preorder<'a, 'src>(root: &'a CstNode<'src>) -> Vec<&'a CstNode<'src>> {
    let mut out = Vec::new();
    collect_preorder(root, &mut out);
    out
}

/// zerodds-lint: recursion-depth 64 (Parser/AST-Walk; bounded by IDL nesting)
fn collect_preorder<'a, 'src>(node: &'a CstNode<'src>, out: &mut Vec<&'a CstNode<'src>>) {
    out.push(node);
    for child in &node.children {
        collect_preorder(child, out);
    }
}

/// Post-order Depth-First-Traversal: children left-to-right → root.
#[must_use]
pub fn postorder<'a, 'src>(root: &'a CstNode<'src>) -> Vec<&'a CstNode<'src>> {
    let mut out = Vec::new();
    collect_postorder(root, &mut out);
    out
}

/// zerodds-lint: recursion-depth 64 (Parser/AST-Walk; bounded by IDL nesting)
fn collect_postorder<'a, 'src>(node: &'a CstNode<'src>, out: &mut Vec<&'a CstNode<'src>>) {
    for child in &node.children {
        collect_postorder(child, out);
    }
    out.push(node);
}

/// Pre-order, gefiltert auf Token-Leaves.
#[must_use]
pub fn tokens_only<'a, 'src>(root: &'a CstNode<'src>) -> Vec<&'a CstNode<'src>> {
    preorder(root)
        .into_iter()
        .filter(|n| n.is_token())
        .collect()
}

/// Pre-order, gefiltert auf Internal-Nodes.
#[must_use]
pub fn internals_only<'a, 'src>(root: &'a CstNode<'src>) -> Vec<&'a CstNode<'src>> {
    preorder(root)
        .into_iter()
        .filter(|n| n.is_internal())
        .collect()
}

/// Alle Internal-Nodes mit der gegebenen Production-ID, in Pre-order.
#[must_use]
pub fn find_by_production<'a, 'src>(
    root: &'a CstNode<'src>,
    production: ProductionId,
) -> Vec<&'a CstNode<'src>> {
    preorder(root)
        .into_iter()
        .filter(|n| n.production() == Some(production))
        .collect()
}

/// Erster Internal-Node mit gegebener Production-ID, in Pre-order.
#[must_use]
pub fn find_first_by_production<'a, 'src>(
    root: &'a CstNode<'src>,
    production: ProductionId,
) -> Option<&'a CstNode<'src>> {
    preorder(root)
        .into_iter()
        .find(|n| n.production() == Some(production))
}

/// Alle Token-Leaves mit gegebener TokenKind, in Pre-order.
#[must_use]
pub fn find_by_token_kind<'a, 'src>(
    root: &'a CstNode<'src>,
    kind: TokenKind,
) -> Vec<&'a CstNode<'src>> {
    preorder(root)
        .into_iter()
        .filter(|n| n.token_kind() == Some(kind))
        .collect()
}

/// Anzahl Internal-Nodes mit gegebener Production-ID.
#[must_use]
pub fn count_by_production(root: &CstNode<'_>, production: ProductionId) -> usize {
    find_by_production(root, production).len()
}

/// Maximale Tiefe des Teilbaums. Ein Single-Node hat Tiefe 0,
/// Root + Single-Child hat Tiefe 1, etc.
#[must_use]
pub fn depth(node: &CstNode<'_>) -> usize {
    if node.children.is_empty() {
        return 0;
    }
    1 + node.children.iter().map(depth).max().unwrap_or(0)
}

#[cfg(test)]
mod tests {
    #![allow(clippy::expect_used, clippy::panic)]

    use super::*;
    use crate::cst::CstNode;
    use crate::cst::build::build_cst;
    use crate::engine::Recognizer;
    use crate::errors::Span;
    use crate::grammar::toy::TOY;
    use crate::grammar::{ProductionId, TokenKind};
    use crate::lexer::Token;

    fn t(kind: TokenKind) -> Token<'static> {
        Token::synthetic(kind)
    }

    fn make_toy_cst<'src>(tokens: &[Token<'src>]) -> CstNode<'src> {
        let result = Recognizer::new(&TOY).recognize(tokens);
        build_cst(&TOY, tokens, &result).expect("must build")
    }

    // -----------------------------------------------------------------
    // Reihenfolgen
    // -----------------------------------------------------------------

    #[test]
    fn preorder_visits_root_first_then_children() {
        let mut root = CstNode::internal(ProductionId(0), 0, Span::SYNTHETIC);
        root.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("a"))));
        let mut sub = CstNode::internal(ProductionId(1), 0, Span::SYNTHETIC);
        sub.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("b"))));
        root.push_child(sub);

        let order: Vec<_> = preorder(&root)
            .iter()
            .map(|n| {
                if let Some(p) = n.production() {
                    format!("I({})", p.0)
                } else if let Some(k) = n.token_kind() {
                    format!("T({k:?})")
                } else {
                    "?".to_string()
                }
            })
            .collect();
        assert_eq!(order[0], "I(0)");
        assert_eq!(order[1], "T(Keyword(\"a\"))");
        assert_eq!(order[2], "I(1)");
        assert_eq!(order[3], "T(Keyword(\"b\"))");
    }

    #[test]
    fn postorder_visits_children_first_then_root() {
        let mut root = CstNode::internal(ProductionId(0), 0, Span::SYNTHETIC);
        let mut sub = CstNode::internal(ProductionId(1), 0, Span::SYNTHETIC);
        sub.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("a"))));
        root.push_child(sub);
        root.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("b"))));

        let order: Vec<_> = postorder(&root)
            .iter()
            .map(|n| {
                if let Some(p) = n.production() {
                    format!("I({})", p.0)
                } else if let Some(k) = n.token_kind() {
                    format!("T({k:?})")
                } else {
                    "?".to_string()
                }
            })
            .collect();
        // Erwartet: T(a), I(1), T(b), I(0)
        assert_eq!(
            order,
            vec![
                "T(Keyword(\"a\"))".to_string(),
                "I(1)".to_string(),
                "T(Keyword(\"b\"))".to_string(),
                "I(0)".to_string(),
            ]
        );
    }

    // -----------------------------------------------------------------
    // Typ-Filter
    // -----------------------------------------------------------------

    #[test]
    fn tokens_only_returns_only_leaves() {
        let cst = make_toy_cst(&[
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("+")),
            t(TokenKind::Keyword("n")),
        ]);
        let toks = tokens_only(&cst);
        assert_eq!(toks.len(), 3);
        assert!(toks.iter().all(|n| n.is_token()));
    }

    #[test]
    fn internals_only_returns_only_internals() {
        let cst = make_toy_cst(&[t(TokenKind::Keyword("n"))]);
        let internals = internals_only(&cst);
        // E → T → F, alle drei sind Internal.
        assert_eq!(internals.len(), 3);
        assert!(internals.iter().all(|n| n.is_internal()));
    }

    // -----------------------------------------------------------------
    // Production-Such-Helper
    // -----------------------------------------------------------------

    #[test]
    fn find_by_production_collects_all_matches_in_preorder() {
        // n + n + n  → 3 E-Knoten (Top, Sub, Sub-Sub) im Baum.
        let cst = make_toy_cst(&[
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("+")),
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("+")),
            t(TokenKind::Keyword("n")),
        ]);
        let es = find_by_production(&cst, ProductionId(0));
        assert_eq!(
            es.len(),
            3,
            "Erwartet 3 E-Knoten in n+n+n, gefunden {}",
            es.len()
        );
    }

    #[test]
    fn find_first_by_production_returns_root_if_match() {
        let cst = make_toy_cst(&[t(TokenKind::Keyword("n"))]);
        let first_e = find_first_by_production(&cst, ProductionId(0));
        // Erstes E ist die Wurzel selbst.
        assert!(first_e.map(|n| std::ptr::eq(n, &cst)).unwrap_or(false));
    }

    #[test]
    fn find_first_by_production_none_for_missing() {
        let cst = make_toy_cst(&[t(TokenKind::Keyword("n"))]);
        // ProductionId(99) existiert nicht in TOY.
        assert!(find_first_by_production(&cst, ProductionId(99)).is_none());
    }

    #[test]
    fn count_by_production_matches_find_length() {
        let cst = make_toy_cst(&[
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("*")),
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("*")),
            t(TokenKind::Keyword("n")),
        ]);
        let t_nodes = find_by_production(&cst, ProductionId(1));
        assert_eq!(count_by_production(&cst, ProductionId(1)), t_nodes.len());
    }

    // -----------------------------------------------------------------
    // Token-Such-Helper
    // -----------------------------------------------------------------

    #[test]
    fn find_by_token_kind_collects_matching_tokens() {
        let cst = make_toy_cst(&[
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("+")),
            t(TokenKind::Keyword("n")),
            t(TokenKind::Punct("+")),
            t(TokenKind::Keyword("n")),
        ]);
        let pluses = find_by_token_kind(&cst, TokenKind::Punct("+"));
        assert_eq!(pluses.len(), 2);
        let ns = find_by_token_kind(&cst, TokenKind::Keyword("n"));
        assert_eq!(ns.len(), 3);
    }

    // -----------------------------------------------------------------
    // Depth
    // -----------------------------------------------------------------

    #[test]
    fn depth_of_single_token_is_zero() {
        let leaf = CstNode::token(Token::synthetic(TokenKind::Keyword("x")));
        assert_eq!(depth(&leaf), 0);
    }

    #[test]
    fn depth_of_root_with_single_child_is_one() {
        let mut root = CstNode::internal(ProductionId(0), 0, Span::SYNTHETIC);
        root.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("x"))));
        assert_eq!(depth(&root), 1);
    }

    #[test]
    fn depth_of_toy_single_n_is_three() {
        // E → T → F → "n"  ⇒ Tiefe 3
        let cst = make_toy_cst(&[t(TokenKind::Keyword("n"))]);
        assert_eq!(depth(&cst), 3);
    }

    #[test]
    fn depth_takes_max_of_children() {
        // Asymmetrischer Baum: ein langer und ein kurzer Zweig.
        let mut root = CstNode::internal(ProductionId(0), 0, Span::SYNTHETIC);
        // Kurzer Zweig: ein Token
        root.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("a"))));
        // Langer Zweig: drei Internal-Ebenen
        let mut deep = CstNode::internal(ProductionId(1), 0, Span::SYNTHETIC);
        let mut deeper = CstNode::internal(ProductionId(2), 0, Span::SYNTHETIC);
        deeper.push_child(CstNode::token(Token::synthetic(TokenKind::Keyword("b"))));
        deep.push_child(deeper);
        root.push_child(deep);
        // Root + Internal + Internal + Token ⇒ Tiefe 3.
        assert_eq!(depth(&root), 3);
    }
}