cliard24 0.1.2

//! # Expression Parser Module
//!
//! Provides functionality to parse infix expression strings into tokens,
//! and convert them to postfix notation (Reverse Polish Notation) for
//! efficient evaluation by the AST builder.
//!
//! The parser supports:
//! - Numeric literals (integers and floating-point numbers)
//! - Variable identifiers
//! - Binary arithmetic operators (+, -, *, /)
//! - Parentheses for grouping expressions
//! - Whitespace-insensitive parsing

use crate::expression::{
    ast::{BinaryOpr, ExprNum},
    error::AstError,
};

/// Token types representing the fundamental building blocks of arithmetic expressions
///
/// Each token corresponds to a distinct syntactic element in the expression language.
/// The tokens are produced by the lexical analysis phase and consumed by the parser.
#[cfg_attr(test, derive(Debug, PartialEq))]
pub enum ExprToken<'a> {
    /// Numeric literal value (e.g., 42, 3.14)
    Literal(ExprNum),
    /// Variable identifier that requires value substitution
    Variable(&'a str),
    /// Binary arithmetic operator connecting two expressions
    BinaryOpr(BinaryOpr),
    /// Left parenthesis for expression grouping
    LeftParen,
    /// Right parenthesis for expression grouping
    RightParen,
}

impl<'a> ExprToken<'a> {
    /// Converts a string slice to a numeric literal token
    ///
    /// # Arguments
    /// * `input` - String slice containing the numeric representation
    ///
    /// # Returns
    /// - `Ok(ExprToken::Literal)` with the parsed numeric value
    /// - `Err(AstError::ParseLiteralError)` if parsing fails
    ///
    /// # Note
    /// Supports underscore separators in numbers (e.g., "1_000" becomes 1000.0)
    pub fn literal_from_str(input: &'a str) -> Result<Self, AstError<'a>> {
        Ok(ExprToken::Literal(input.replace("_", "").parse().map_err(
            |source| AstError::ParseLiteralError { input, source },
        )?))
    }
}

/// Display implementation for pretty-printing tokens in human-readable form
impl<'a> std::fmt::Display for ExprToken<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        match self {
            ExprToken::Literal(num) => write!(f, "{}", num),
            ExprToken::Variable(var) => write!(f, "{}", var),
            ExprToken::BinaryOpr(opr) => write!(f, "{}", opr.as_str()),
            ExprToken::LeftParen => write!(f, "("),
            ExprToken::RightParen => write!(f, ")"),
        }
    }
}

/// Container for a sequence of expression tokens with parsing capabilities
///
/// This struct holds tokens in either infix or postfix order and provides
/// methods for converting between these notations using the shunting-yard algorithm.
pub struct Expression<'a> {
    /// Sequence of tokens representing the expression
    pub tokens: Vec<ExprToken<'a>>,
}

impl<'a> Expression<'a> {
    /// Creates a new empty expression
    ///
    /// # Returns
    /// New `Expression` instance with no tokens
    pub fn new() -> Self {
        Expression { tokens: Vec::new() }
    }

    /// Parses a string into a sequence of expression tokens (lexical analysis)
    ///
    /// Performs character-by-character scanning to identify numeric literals,
    /// variables, operators, and parentheses. Handles whitespace and validates
    /// token boundaries.
    ///
    /// # Arguments
    /// * `infix_expr` - String containing the arithmetic expression
    ///
    /// # Returns
    /// - `Ok(Expression)` with the tokenized expression
    /// - `Err(AstError)`  for invalid characters, unmatched parentheses, or malformed numbers
    ///
    /// # Examples
    /// ```
    /// use cliard24::expression::parser::Expression;
    ///
    /// let expr = Expression::from_expr("3 + x * 2").unwrap();
    /// assert_eq!(expr.to_string(), "3 + x * 2");
    /// ```
    ///
    /// # Algorithm
    /// 1. Scan characters left to right, maintaining a sliding window for multi-character tokens
    /// 2. Classify characters as digits (numeric), letters (variables), or symbols (operators)
    /// 3. Handle token boundaries when transitioning between character types
    /// 4. Validate operator symbols and parentheses matching
    pub fn from_expr(infix_expr: &'a str) -> Result<Self, AstError<'a>> {
        let mut tokenized = Expression::new();
        // Track the current token being scanned
        let mut start_idx = None; // Start index of current token in the input string
        let mut is_recording_var = false; // Whether we're scanning a variable (vs. number)

        for (i, ch) in infix_expr.char_indices() {
            match ch {
                // Numeric characters (digits, decimal point, underscore separators)
                '0'..='9' | '.' | '_' => {
                    if start_idx.is_none() {
                        start_idx = Some(i);
                        is_recording_var = false; // We're scanning a number
                    }
                }
                // Alphabetic characters (variable names)
                'A'..='Z' | 'a'..='z' => {
                    if let Some(s_idx) = start_idx {
                        if !is_recording_var {
                            // Transition from number to variable: finish number token first
                            tokenized
                                .tokens
                                .push(ExprToken::literal_from_str(&infix_expr[s_idx..i])?);
                            // Start new variable token
                            start_idx = Some(i);
                            is_recording_var = true;
                        }
                    } else {
                        // Start scanning a variable
                        start_idx = Some(i);
                        is_recording_var = true;
                    }
                }
                // Symbol characters (operators, parentheses, whitespace)
                symbol => {
                    // Process any pending token before handling the symbol
                    if let Some(s_idx) = start_idx {
                        if is_recording_var {
                            tokenized
                                .tokens
                                .push(ExprToken::Variable(&infix_expr[s_idx..i]));
                        } else {
                            tokenized
                                .tokens
                                .push(ExprToken::literal_from_str(&infix_expr[s_idx..i])?);
                        }
                        start_idx = None;
                    }

                    // Handle the symbol character
                    match symbol {
                        '+' | '-' | '*' | '/' => {
                            tokenized
                                .tokens
                                .push(ExprToken::BinaryOpr(BinaryOpr::from_opr(
                                    &infix_expr[i..(i + 1)],
                                )?));
                        }
                        '(' => {
                            tokenized.tokens.push(ExprToken::LeftParen);
                        }
                        ')' => {
                            tokenized.tokens.push(ExprToken::RightParen);
                        }
                        ' ' | '\t' | '\n' => continue, // Skip whitespace
                        _ => {
                            // Invalid character encountered
                            return Err(AstError::SyntaxError {
                                token: &infix_expr[i..(i + 1)],
                                position: i,
                            });
                        }
                    }
                }
            }
        }

        // Process any remaining token at the end of input
        if let Some(s_idx) = start_idx {
            if is_recording_var {
                tokenized
                    .tokens
                    .push(ExprToken::Variable(&infix_expr[s_idx..]));
            } else {
                tokenized
                    .tokens
                    .push(ExprToken::literal_from_str(&infix_expr[s_idx..])?);
            }
        }
        Ok(tokenized)
    }

    /// Converts infix expression tokens to postfix notation using shunting-yard algorithm
    ///
    /// The shunting-yard algorithm rearranges tokens from infix (human-readable) order
    /// to postfix (Reverse Polish Notation) order, which is easier for expression
    /// tree construction and evaluation.
    ///
    /// # Returns
    /// - `Ok(&Self)` reference to the modified expression (now in postfix order)
    /// - `Err(AstError)` for mismatched parentheses or invalid expression structure
    ///
    /// # Examples
    /// ```
    /// use cliard24::expression::parser::Expression;
    /// let mut expr = Expression::from_expr("A + B * C").unwrap();
    /// expr.to_postfix().unwrap();
    /// assert_eq!(expr.to_string(), "A B C * +".to_string());
    /// ```
    ///
    /// # Algorithm (Dijkstra's Shunting Yard)
    /// 1. Initialize empty stack for operators and parentheses
    /// 2. Process tokens left to right:
    ///    - Operands (literals/variables) go directly to output
    ///    - Operators are pushed to stack after popping higher-precedence operators
    ///    - Left parentheses are pushed to stack
    ///    - Right parentheses pop operators until matching left parenthesis
    /// 3. After processing all tokens, pop remaining operators from stack
    ///
    /// # Note
    /// This method modifies the expression in-place and truncates the token vector
    pub fn to_postfix(&mut self) -> Result<&Self, AstError<'a>> {
        let mut write_idx = 0; // Current position in output sequence
        let mut stack = Vec::new(); // Operator stack

        // Process each token in the infix expression
        for cur_idx in 0..self.tokens.len() {
            match self.tokens[cur_idx] {
                // Operands go directly to output (in original order)
                ExprToken::Literal(_) | ExprToken::Variable(_) => {
                    self.tokens.swap(write_idx, cur_idx);
                    write_idx += 1;
                }
                // Operators: handle precedence and associativity
                ExprToken::BinaryOpr(cur_opr) => {
                    // Pop operators from stack while they have higher or equal precedence
                    'check_pop: while let Some(top_tk) = stack.last() {
                        if let ExprToken::BinaryOpr(top_opr) = top_tk {
                            if top_opr.get_precedence() >= cur_opr.get_precedence() {
                                if let Some(pop_tk) = stack.pop() {
                                    self.tokens[write_idx] = pop_tk;
                                    write_idx += 1;
                                } else {
                                    break 'check_pop; // Stack empty
                                }
                            } else {
                                break 'check_pop; // Lower precedence operator found
                            }
                        } else {
                            // Stop at left parenthesis or other non-operator
                            break 'check_pop;
                        }
                    }
                    // Push current operator to stack
                    stack.push(ExprToken::BinaryOpr(cur_opr));
                }
                // Left parenthesis: push to stack as marker
                ExprToken::LeftParen => stack.push(ExprToken::LeftParen),
                // Right parenthesis: pop operators until matching left parenthesis
                ExprToken::RightParen => {
                    'until_left: while let Some(stack_last) = stack.pop() {
                        if matches!(stack_last, ExprToken::BinaryOpr(_)) {
                            self.tokens[write_idx] = stack_last;
                            write_idx += 1;
                        } else {
                            break 'until_left; // Found left parenthesis (discarded)
                        }
                    }
                }
            }
        }

        // Pop remaining operators from stack to output
        while let Some(opr) = stack.pop() {
            match opr {
                ExprToken::BinaryOpr(_) => {
                    self.tokens[write_idx] = opr;
                    write_idx += 1;
                }
                ExprToken::LeftParen => return Err(AstError::UnmatchedParentheses),
                _ => {
                    return Err(AstError::InvalidExpressionStructure(
                        "Unexpected token type in operator stack during infix-to-postfix conversion",
                    ));
                }
            }
        }

        // Truncate token vector to remove unused positions
        self.tokens.truncate(write_idx);
        Ok(self)
    }
}

/// Display implementation for pretty-printing expressions in infix-like format
///
/// Reconstructs a human-readable string from the token sequence with
/// appropriate spacing around operators.
impl<'a> std::fmt::Display for Expression<'a> {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(
            f,
            "{}",
            self.tokens
                .iter()
                .map(|t| t.to_string())
                .collect::<Vec<String>>()
                .join(" ")
                .replace("( ", "(") // Clean up parentheses spacing
                .replace(" )", ")")
        )
    }
}

// Default implementation for Expression
impl<'a> Default for Expression<'a> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_tokenize_expression() {
        let expr =
            Expression::from_expr(" ( abc123 + 12.33)\n-( (De12fg*12hiJ34)/1.234)K.1 ).2").unwrap();
        assert_eq!(
            expr.tokens,
            vec![
                ExprToken::LeftParen,
                ExprToken::Variable("abc123"),
                ExprToken::BinaryOpr(BinaryOpr::Add),
                ExprToken::Literal(12.33),
                ExprToken::RightParen,
                ExprToken::BinaryOpr(BinaryOpr::Sub),
                ExprToken::LeftParen,
                ExprToken::LeftParen,
                ExprToken::Variable("De12fg"),
                ExprToken::BinaryOpr(BinaryOpr::Mul),
                ExprToken::Literal(12.0),
                ExprToken::Variable("hiJ34"),
                ExprToken::RightParen,
                ExprToken::BinaryOpr(BinaryOpr::Div),
                ExprToken::Literal(1.234),
                ExprToken::RightParen,
                ExprToken::Variable("K.1"),
                ExprToken::RightParen,
                ExprToken::Literal(0.2),
            ]
        );
        assert_eq!(
            expr.to_string(),
            "(abc123 + 12.33) - ((De12fg * 12 hiJ34) / 1.234) K.1) 0.2"
        );
    }

    #[test]
    fn test_expression_to_postfix() {
        let mut expr = Expression::from_expr("(1+(2-3))*(wow/zero)").unwrap();
        assert_eq!(expr.to_string(), "(1 + (2 - 3)) * (wow / zero)");
        assert_eq!(
            expr.to_postfix().unwrap().tokens,
            vec![
                ExprToken::Literal(1.0),
                ExprToken::Literal(2.0),
                ExprToken::Literal(3.0),
                ExprToken::BinaryOpr(BinaryOpr::Sub),
                ExprToken::BinaryOpr(BinaryOpr::Add),
                ExprToken::Variable("wow"),
                ExprToken::Variable("zero"),
                ExprToken::BinaryOpr(BinaryOpr::Div),
                ExprToken::BinaryOpr(BinaryOpr::Mul),
            ]
        );
        assert_eq!(expr.to_string(), "1 2 3 - + wow zero / *");
    }

    #[test]
    fn test_tokenize_can_not_parse() {
        let expr = Expression::from_expr(".1a.1.1 .1").unwrap();
        assert_eq!(
            expr.tokens,
            vec![
                ExprToken::Literal(0.1),
                ExprToken::Variable("a.1.1"),
                ExprToken::Literal(0.1)
            ]
        );
        assert_eq!(expr.to_string(), "0.1 a.1.1 0.1");
        let expr = Expression::from_expr(".1a.1.1 ..1");
        assert!(expr.is_err());
    }
}