sipha_parse/parser/

mod.rs

//! High-level parser that evaluates grammar rules.
//!
//! The `Parser` is the main entry point for parsing token streams into concrete
//! syntax trees (CST). It supports grammar-based parsing.

mod grammar;
mod recovery;

use std::collections::{HashMap, HashSet};

use crate::grammar::{GrammarRule, GrammarRuleParser};
use crate::pratt::PrattParser;
use crate::state::ParserState;
use builder_pattern::Builder;
use sipha_core::traits::{GrammarContext, NodeId, RuleId, TokenKind};
use sipha_error::ParseError;
use sipha_pratt::PrattRuleKind;

use self::grammar::*;

/// Main parser entry point.
///
/// The `Parser` is responsible for evaluating grammar rules and building
/// concrete syntax trees (CST) from token streams. It supports both
/// grammar-based parsing and Pratt parsing for operator precedence.
///
/// # Architecture
///
/// The parser uses a recursive descent approach with:
/// - **Grammar rules**: Traditional parser combinators (seq, choice, many, etc.)
/// - **Pratt rules**: Operator precedence parsing for expressions
/// - **Error recovery**: Configurable recovery strategies using sync tokens
/// - **Memoization**: Optional memoization for packrat parsing
///
/// # Performance Characteristics
///
/// - **Time Complexity**: O(n) for most grammars, where n is the number of tokens
/// - **Space Complexity**: O(n) for the CST arena
/// - **Memoization**: Optional, can be enabled for recursive grammars
///
/// # Example
///
/// ```rust
/// use sipha_parse::{Parser, helpers, ParserState};
/// use sipha_tree::{NodeArena, RawNodeId};
///
/// # #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
/// # enum Token { Ident, Plus }
/// # impl sipha_core::traits::TokenKind for Token {
/// #     fn is_trivia(&self) -> bool { false }
/// # }
/// # #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
/// # enum Rule { Expr }
/// let mut parser = Parser::create();
/// parser.register_rule(
///     Rule::Expr,
///     helpers::seq(vec![
///         helpers::token(Token::Ident),
///         helpers::token(Token::Plus),
///         helpers::token(Token::Ident),
///     ]),
/// );
/// ```
#[derive(Builder)]
pub struct Parser<K: TokenKind, R: RuleId> {
    /// Grammar rules registered with the parser.
    #[default(HashMap::new())]
    grammar_rules: HashMap<R, GrammarRule<K, R>>,
    /// Pratt operator rules registered with the parser.
    #[default(HashMap::new())]
    pratt_rules: HashMap<K, PrattRuleKind<K, R>>,
    /// Synchronization tokens for error recovery.
    #[default(HashSet::new())]
    pub(crate) sync_tokens: HashSet<K>,
    /// Maximum depth for error recovery attempts.
    #[default(10)]
    pub(crate) max_recovery_depth: usize,
}

impl<K: TokenKind, R: RuleId> Parser<K, R> {
    /// Create a new parser with default settings.
    ///
    /// For builder pattern usage, use `Parser::new()` which returns a builder.
    pub fn create() -> Self {
        Self::default()
    }

    /// Set the maximum depth for error recovery attempts.
    pub fn set_max_recovery_depth(&mut self, depth: usize) {
        self.max_recovery_depth = depth;
    }

    /// Register a grammar rule.
    ///
    /// Validates the rule before registration (e.g., ensures range min <= max).
    /// Invalid rules will cause a panic to prevent silent failures.
    pub fn register_rule(&mut self, rule_id: R, rule: GrammarRule<K, R>) {
        if let Err(err) = crate::grammar::validate_rule(&rule) {
            panic!("Invalid grammar rule registered: {:?}", err);
        }
        self.grammar_rules.insert(rule_id, rule);
    }

    /// Configure synchronization tokens for error recovery.
    pub fn set_sync_tokens(&mut self, tokens: Vec<K>) {
        self.sync_tokens = tokens.into_iter().collect();
    }

    /// Register a Pratt operator rule.
    ///
    /// This allows the parser to handle operator precedence parsing for the given token kind.
    pub fn register_pratt_rule(&mut self, token_kind: K, rule: PrattRuleKind<K, R>) {
        self.pratt_rules.insert(token_kind, rule);
    }

    /// Parse a top-level rule by identifier.
    #[must_use = "parse results should be checked for errors"]
    pub fn parse_rule<'tokens, 'arena, N, Ctx>(
        &mut self,
        rule_id: R,
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        let start_pos = state.position();
        let debug_enabled = std::env::var("SIPHA_DEBUG").is_ok();
        if let Some(memo_entry) = state.check_memo(rule_id) {
            if debug_enabled {
                eprintln!(
                    "[DEBUG] parse_rule: Found memo entry for {:?} at position {}",
                    rule_id, start_pos
                );
            }
            match memo_entry {
                sipha_memo::MemoEntry::Success { node, consumed } => {
                    let node = *node;
                    let consumed = *consumed;
                    state.reset(start_pos + consumed);
                    return Ok(node);
                }
                sipha_memo::MemoEntry::Failure { error, consumed } => {
                    let error = error.clone();
                    let consumed = *consumed;
                    if debug_enabled {
                        eprintln!(
                            "[DEBUG] parse_rule: Using cached failure for {:?}: {:?}",
                            rule_id, error
                        );
                    }
                    state.reset(start_pos + consumed);
                    return Err(error);
                }
            }
        }

        state.push_rule(rule_id);
        let result = {
            let rule = self.grammar_rules.get(&rule_id).cloned().ok_or_else(|| {
                ParseError::InvalidContext {
                    rule: "unknown rule",
                    span: state.current_span(),
                    rule_context: state.current_rule(),
                    context_stack: state.build_context_stack(),
                }
            })?;
            self.parse_grammar_rule(rule_id, &rule, state)
        };

        let consumed = state.position() - start_pos;
        match &result {
            Ok(node) => state.store_memo_success(rule_id, start_pos, *node, consumed),
            Err(error) => state.store_memo_failure(rule_id, start_pos, error.clone(), consumed),
        }

        state.pop_rule();
        result
    }
}

impl<K: TokenKind, R: RuleId> GrammarRuleParser<K, R> for Parser<K, R> {
    fn parse_grammar_rule<'tokens, 'arena, N, Ctx>(
        &mut self,
        rule_id: R,
        rule: &GrammarRule<K, R>,
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        match rule {
            GrammarRule::Sequence(rules) => parse_sequence(self, rule_id, rules, state),
            GrammarRule::Choice(rules) => parse_choice(self, rule_id, rules, state),
            GrammarRule::Optional(inner) => parse_optional(self, rule_id, inner, state),
            GrammarRule::ZeroOrMore(inner) => parse_zero_or_more(self, rule_id, inner, state),
            GrammarRule::OneOrMore(inner) => parse_one_or_more(self, rule_id, inner, state),
            GrammarRule::Range {
                rule: inner,
                min,
                max,
            } => parse_range(self, rule_id, inner, *min, *max, state),
            GrammarRule::PrattExpr(min_prec) => parse_pratt_expr(self, rule_id, state, *min_prec),
            GrammarRule::Token(kind) => state.expect_node(*kind),
            GrammarRule::Rule(id) => self.parse_rule(*id, state),
            GrammarRule::Conditional {
                rule: inner,
                condition,
            } => {
                if condition(state.position()) {
                    self.parse_grammar_rule(rule_id, inner, state)
                } else {
                    Err(ParseError::InvalidContext {
                        rule: "conditional",
                        span: state.current_span(),
                        rule_context: state.current_rule(),
                        context_stack: state.build_context_stack(),
                    })
                }
            }
            GrammarRule::NegativeLookahead(rule) => {
                parse_negative_lookahead(self, rule_id, rule, state)
            }
            GrammarRule::PositiveLookahead(rule) => {
                parse_positive_lookahead(self, rule_id, rule, state)
            }
        }
    }
}

impl<K: TokenKind, R: RuleId> PrattParser<K, R> for Parser<K, R> {
    fn get_rule(&self, kind: &K) -> Option<&PrattRuleKind<K, R>> {
        self.pratt_rules.get(kind)
    }
}

impl<K: TokenKind, R: RuleId> Default for Parser<K, R> {
    fn default() -> Self {
        Parser::new().build()
    }
}