sipha_parse/

parser.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.

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

use crate::grammar::{GrammarRule, GrammarRuleParser, Precedence};
use crate::state::ParserState;
use builder_pattern::Builder;
use sipha_core::traits::{GrammarContext, NodeId, RuleId, TokenKind};
use sipha_error::ParseError;
use sipha_tree::{CstKind, NodeChildren};

/// 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.
///
/// # 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**: Enabled by default for recursive grammars
///
/// # Example
///
/// ```rust
/// use sipha_core::{Parser, helpers, ParserState, cst::{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>>,
    /// Synchronization tokens for error recovery.
    #[default(HashSet::new())]
    sync_tokens: HashSet<K>,
    /// Maximum depth for error recovery attempts.
    #[default(10)]
    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();
    }

    /// 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();
        if let Some(memo_entry) = state.check_memo(rule_id) {
            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;
                    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
    }

    /// Attempt to recover from a parse error by scanning for sync tokens.
    fn try_recover<'tokens, 'arena, N, Ctx>(
        &self,
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
        recovery_depth: usize,
    ) -> bool
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        if recovery_depth >= self.max_recovery_depth {
            return false;
        }

        let start_pos = state.position();

        if !self.sync_tokens.is_empty() {
            let mut offset = 0;
            let max_scan = 100;

            while offset < max_scan {
                if let Some(token) = state.peek(offset) {
                    if self.sync_tokens.contains(&token.kind) {
                        state.reset(start_pos + offset);
                        return true;
                    }
                    offset += 1;
                } else {
                    break;
                }
            }
        }

        let mut offset = 1;
        let max_skip = 10;

        while offset < max_skip {
            if let Some(token) = state.peek(offset) {
                if !token.kind.is_trivia() {
                    state.reset(start_pos + offset);
                    return true;
                }
                offset += 1;
            } else {
                break;
            }
        }

        false
    }

    fn parse_sequence<'tokens, 'arena, N, Ctx>(
        &mut self,
        rule_id: R,
        rules: &[GrammarRule<K, R>],
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        self.parse_sequence_with_recovery(rule_id, rules, state, 0)
    }

    fn parse_sequence_with_recovery<'tokens, 'arena, N, Ctx>(
        &mut self,
        rule_id: R,
        rules: &[GrammarRule<K, R>],
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
        recovery_depth: usize,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        let start_pos = state.position();
        let mut builder = state.start_node(rule_id);
        for rule in rules {
            match self.parse_grammar_rule(rule_id, rule, state) {
                Ok(child) => {
                    builder.node(child);
                }
                Err(err) => {
                    let error_span = state.current_span();
                    if self.try_recover(state, recovery_depth) {
                        let error_node = state.alloc_node(
                            CstKind::Error("parse error"),
                            error_span,
                            NodeChildren::new(),
                        );
                        builder.node(error_node);
                    } else {
                        state.reset(start_pos);
                        return Err(err);
                    }
                }
            }
        }
        Ok(builder.finish(state))
    }

    fn parse_choice<'tokens, 'arena, N, Ctx>(
        &mut self,
        rule_id: R,
        rules: &[GrammarRule<K, R>],
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        if rules.is_empty() {
            return Err(ParseError::InvalidContext {
                rule: "empty choice",
                span: state.current_span(),
                rule_context: state.current_rule(),
                context_stack: state.build_context_stack(),
            });
        }

        let start = state.position();
        let mut errors: Vec<ParseError<K, R>> = Vec::new();

        for rule in rules {
            if let GrammarRule::Token(expected_kind) = rule {
                if state.at(*expected_kind) {
                    match self.parse_grammar_rule(rule_id, rule, state) {
                        Ok(node) => return Ok(node),
                        Err(err) => {
                            errors.push(err);
                            state.reset(start);
                        }
                    }
                    continue;
                } else {
                    errors.push(ParseError::Expected {
                        expected: sipha_error::Expected::Single(*expected_kind),
                        found: state.peek(0).map(|t| t.kind),
                        span: state.current_span(),
                        rule_context: state.current_rule(),
                        context_stack: state.build_context_stack(),
                    });
                    continue;
                }
            }

            match self.parse_grammar_rule(rule_id, rule, state) {
                Ok(node) => return Ok(node),
                Err(err) => {
                    errors.push(err);
                    state.reset(start);
                }
            }
        }

        if errors.is_empty() {
            Err(ParseError::UnexpectedEof {
                span: state.current_span(),
                rule_context: state.current_rule(),
                context_stack: state.build_context_stack(),
            })
        } else if errors.len() == 1 {
            Err(errors.into_iter().next().unwrap())
        } else {
            Err(ParseError::MultipleAlternatives {
                alternatives: errors,
                span: state.current_span(),
                rule_context: state.current_rule(),
                context_stack: state.build_context_stack(),
            })
        }
    }

    fn parse_optional<'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,
    {
        let start = state.position();
        match self.parse_grammar_rule(rule_id, rule, state) {
            Ok(node) => Ok(node),
            Err(_) => {
                state.reset(start);
                Ok(state.alloc_node(
                    CstKind::Rule(rule_id),
                    state.current_span(),
                    NodeChildren::new(),
                ))
            }
        }
    }

    fn parse_zero_or_more<'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,
    {
        let mut builder = state.start_node(rule_id);
        while let Ok(child) = self.parse_grammar_rule(rule_id, rule, state) {
            builder.node(child);
        }
        Ok(builder.finish(state))
    }

    fn parse_one_or_more<'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,
    {
        let mut builder = state.start_node(rule_id);
        let first = self.parse_grammar_rule(rule_id, rule, state)?;
        builder.node(first);
        while let Ok(child) = self.parse_grammar_rule(rule_id, rule, state) {
            builder.node(child);
        }
        Ok(builder.finish(state))
    }

    fn parse_range<'tokens, 'arena, N, Ctx>(
        &mut self,
        rule_id: R,
        rule: &GrammarRule<K, R>,
        min: usize,
        max: usize,
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        if min > max {
            return Err(ParseError::InvalidContext {
                rule: "range min > max",
                span: state.current_span(),
                rule_context: state.current_rule(),
                context_stack: state.build_context_stack(),
            });
        }
        let mut builder = state.start_node(rule_id);
        let mut count = 0;

        while count < max {
            match self.parse_grammar_rule(rule_id, rule, state) {
                Ok(node) => {
                    builder.node(node);
                    count += 1;
                }
                Err(err) => {
                    if count < min {
                        return Err(err);
                    }
                    break;
                }
            }
        }

        if count < min {
            return Err(ParseError::RangeError {
                min,
                max,
                found: count,
                span: state.current_span(),
                rule_context: state.current_rule(),
                context_stack: state.build_context_stack(),
            });
        }

        Ok(builder.finish(state))
    }

    fn parse_pratt_expr<'tokens, 'arena, N, Ctx>(
        &mut self,
        _rule_id: R,
        state: &mut ParserState<'tokens, 'arena, K, R, N, Ctx>,
        _min_prec: Precedence,
    ) -> Result<N, ParseError<K, R>>
    where
        N: NodeId,
        Ctx: GrammarContext,
    {
        // TODO: Integrate with sipha-pratt when it's created
        Err(ParseError::InvalidContext {
            rule: "Pratt parsing not yet integrated",
            span: state.current_span(),
            rule_context: state.current_rule(),
            context_stack: state.build_context_stack(),
        })
    }

    fn parse_negative_lookahead<'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,
    {
        let start = state.position();
        match self.parse_grammar_rule(rule_id, rule, state) {
            Ok(_) => {
                state.reset(start);
                let token_kind =
                    state
                        .peek(0)
                        .map(|t| t.kind)
                        .ok_or_else(|| ParseError::UnexpectedEof {
                            span: state.current_span(),
                            rule_context: state.current_rule(),
                            context_stack: state.build_context_stack(),
                        })?;
                Err(ParseError::UnexpectedToken {
                    kind: token_kind,
                    span: state.current_span(),
                    rule_context: state.current_rule(),
                    context_stack: state.build_context_stack(),
                })
            }
            Err(_) => {
                state.reset(start);
                let builder = state.start_node(rule_id);
                Ok(builder.finish(state))
            }
        }
    }

    fn parse_positive_lookahead<'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,
    {
        let start = state.position();
        match self.parse_grammar_rule(rule_id, rule, state) {
            Ok(_) => {
                state.reset(start);
                let builder = state.start_node(rule_id);
                Ok(builder.finish(state))
            }
            Err(err) => {
                state.reset(start);
                Err(err)
            }
        }
    }
}

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) => self.parse_sequence(rule_id, rules, state),
            GrammarRule::Choice(rules) => self.parse_choice(rule_id, rules, state),
            GrammarRule::Optional(inner) => self.parse_optional(rule_id, inner, state),
            GrammarRule::ZeroOrMore(inner) => self.parse_zero_or_more(rule_id, inner, state),
            GrammarRule::OneOrMore(inner) => self.parse_one_or_more(rule_id, inner, state),
            GrammarRule::Range {
                rule: inner,
                min,
                max,
            } => self.parse_range(rule_id, inner, *min, *max, state),
            GrammarRule::PrattExpr(min_prec) => self.parse_pratt_expr(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) => {
                self.parse_negative_lookahead(rule_id, rule, state)
            }
            GrammarRule::PositiveLookahead(rule) => {
                self.parse_positive_lookahead(rule_id, rule, state)
            }
        }
    }
}

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