dd_statechart 0.7.0

/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
Filename : interpreter/parser.rs

Copyright (C) 2021 CJ McAllister
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 3 of the License, or
    (at your option) any later version.
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software Foundation,
    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA

Purpose:
    This module comprises the second phase of the ECMAScript Interpreter.

    It consumes the Tokens generated by the Lexer, and parses them into
    an Abstract Syntax Tree represented by an Expression object. This
    AST can then be passed to the Evaluator for the next phase of
    interpretation.


    Precedence Hierarchy:
    expression     → equality ;
    equality       → comparison ( ( "!=" | "==" ) comparison )* ;
    comparison     → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
    term           → factor ( ( "-" | "+" ) factor )* ;
    factor         → unary ( ( "/" | "*" ) unary )* ;
    unary          → ( "!" | "-" ) unary
                     | primary ;
    primary        → NUMBER | STRING | IDENTIFIER | "true" | "false" | "null"
                     | "(" expression ")" ;

\* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

use std::{error::Error, fmt, iter::Peekable, slice::Iter};

use crate::interpreter::{
    ArithmeticOperator, Expression, Literal, LogicalOperator, Operator, Token, Unary,
};


///////////////////////////////////////////////////////////////////////////////
//  Data Structures
///////////////////////////////////////////////////////////////////////////////

pub struct Parser<'i> {
    token_iter: Peekable<Iter<'i, Token>>,
    position: u32,
}
#[derive(Debug, PartialEq)]
pub enum ParserError {
    InvalidOperatorConversion(
        Token, /* Token that could not be converted to Operator */
    ),
    InvalidPrimaryToken(
        Token, /* Invalid Token */
        u32,   /* Start location of invalid Token */
    ),
    UnexpectedEndOfExpression,
    UnterminatedGroup(
        Expression, /* Expression within unterminated group */
        u32,        /* Start location of unterminated group */
    ),
}


///////////////////////////////////////////////////////////////////////////////
//  Object Implementations
///////////////////////////////////////////////////////////////////////////////

impl<'i> Parser<'i> {
    pub fn new(tokens: &'i [Token]) -> Self {
        Self {
            token_iter: tokens.iter().peekable(),
            position: 0,
        }
    }


    /*  *  *  *  *  *  *  *\
     *  Utility Methods   *
    \*  *  *  *  *  *  *  */

    pub fn parse(&mut self) -> Result<Expression, ParserError> {
        self.expression()
    }


    /*  *  *  *  *  *  *  *\
     *   Helper Methods   *
    \*  *  *  *  *  *  *  */

    // expression → equality ;
    fn expression(&mut self) -> Result<Expression, ParserError> {
        // All Expressions can be parsed as Equalities, so call down to that level immediately
        self.equality()
    }

    // equality → comparison ( ( "!=" | "==" ) comparison )* ;
    fn equality(&mut self) -> Result<Expression, ParserError> {
        let equivalence_tokens = [&&Token::EqualEqual, &&Token::BangEqual];

        // The LHS of an Equality can be parsed as a Comparison, so call down to that level
        let mut expr = self.comparison()?;

        // The rest of an Equality (if it exists) can also be parsed as Comparison(s)
        // Continually peek the next Token and see if it is an equivalence operator,
        // attempt conversion and catch invalid Tokens if filter is passed.
        while let Some(eq_op) = self
            .token_iter
            .peek()
            .filter(|v| equivalence_tokens.contains(v))
            .map(|v| Self::try_op_from_token(v))
            .transpose()?
        {
            // Match and convert succeeded, consume Token
            self.consume_token();

            let right = self.comparison()?;
            expr = Expression::Binary(Box::new(expr), eq_op, Box::new(right));
        }

        Ok(expr)
    }

    // comparison → term ( ( ">" | ">=" | "<" | "<=" ) term )* ;
    fn comparison(&mut self) -> Result<Expression, ParserError> {
        let comparison_tokens = [
            &&Token::GreaterThan,
            &&Token::GreaterThanOrEqualTo,
            &&Token::LessThan,
            &&Token::LessThanOrEqualTo,
        ];

        // The LHS of a Comparison can be parsed as a Term, so call down to that level
        let mut expr = self.term()?;

        // The rest of a Comparison (if it exists) can also be parsed as Term(s)
        // Continually peek the next Token and see if it is a comparison operator,
        // attempt conversion and catch invalid Tokens if filter is passed.
        while let Some(comp_op) = self
            .token_iter
            .peek()
            .filter(|v| comparison_tokens.contains(v))
            .map(|v| Self::try_op_from_token(v))
            .transpose()?
        {
            // Match and convert succeeded, consume Token
            self.consume_token();

            let right = self.comparison()?;
            expr = Expression::Binary(Box::new(expr), comp_op, Box::new(right));
        }

        Ok(expr)
    }

    // term → factor ( ( "-" | "+" ) factor )* ;
    fn term(&mut self) -> Result<Expression, ParserError> {
        let arithmetic_tokens = [&&Token::Minus, &&Token::Plus];

        // The LHS of a Term can be parsed as a Factor, so call down to that level
        let mut expr = self.factor()?;

        // The rest of a Term (if it exists) can also be parsed as Factor(s)
        // Continually peek the next Token and see if it is an arithmetic operator,
        // attempt conversion and catch invalid Tokens if filter is passed.
        while let Some(math_op) = self
            .token_iter
            .peek()
            .filter(|v| arithmetic_tokens.contains(v))
            .map(|v| Self::try_op_from_token(v))
            .transpose()?
        {
            // Match and convert succeeded, consume Token
            self.consume_token();

            let right = self.comparison()?;
            expr = Expression::Binary(Box::new(expr), math_op, Box::new(right));
        }

        Ok(expr)
    }

    // factor → unary ( ( "/" | "*" ) unary )* ;
    fn factor(&mut self) -> Result<Expression, ParserError> {
        let arithmetic_tokens = [&&Token::Slash, &&Token::Star];

        // The LHS of a Factor can be parsed as a Unary, so call down to that level
        let mut expr = self.unary()?;

        // The rest of a Factor (if it exists) can also be parsed as Unary(s)
        // Continually peek the next Token and see if it is an arithmetic operator,
        // attempt conversion and catch invalid Tokens if filter is passed.
        while let Some(math_op) = self
            .token_iter
            .peek()
            .filter(|v| arithmetic_tokens.contains(v))
            .map(|v| Self::try_op_from_token(v))
            .transpose()?
        {
            // Match and convert succeeded, consume Token
            self.consume_token();

            let right = self.comparison()?;
            expr = Expression::Binary(Box::new(expr), math_op, Box::new(right));
        }

        Ok(expr)
    }

    // unary → ( "!" | "-" ) unary
    //         | primary ;
    fn unary(&mut self) -> Result<Expression, ParserError> {
        // Unaries can recursively contain another Unary if the expression
        // begins with a unary operator.
        match self.token_iter.peek() {
            Some(&&Token::Bang) => {
                self.consume_token();
                Ok(Expression::Unary(Unary::Not(Box::new(self.unary()?))))
            }
            Some(&&Token::Minus) => {
                self.consume_token();
                Ok(Expression::Unary(Unary::Negation(Box::new(self.unary()?))))
            }
            // Otherwise, the Unary can be parsed as a Primary, so call down to that level
            _ => self.primary(),
        }
    }

    // primary → NUMBER | STRING | IDENTIFIER | "true" | "false" | "null" |
    //           | "(" expression ")" ;
    fn primary(&mut self) -> Result<Expression, ParserError> {
        let start = self.position;

        // Primaries are either Literals/Identifiers, or a Grouping containing another Expression
        match self.consume_token() {
            // Literals and Identifiers can be parsed directly
            Some(&Token::Number(value)) => Ok(Expression::Literal(Literal::Number(value))),
            Some(&Token::String(ref string)) => {
                Ok(Expression::Literal(Literal::String(string.clone())))
            }
            Some(&Token::Identifier(ref identifier)) => match identifier.as_str() {
                "true" => Ok(Expression::Literal(Literal::True)),
                "false" => Ok(Expression::Literal(Literal::False)),
                "null" => Ok(Expression::Literal(Literal::Null)),
                _ => Ok(Expression::Identifier(identifier.clone())),
            },

            // Groupings result in parsing of the contained Expression
            Some(&Token::LeftParen) => {
                let expr = self.expression()?;

                // Check for trailing ')', return error if it's missing
                if let Some(Token::RightParen) = self.token_iter.peek() {
                    // Found the trailing ')', consume it and return the Grouping
                    self.consume_token();

                    Ok(Expression::Grouping(Box::new(expr)))
                } else {
                    Err(ParserError::UnterminatedGroup(expr, start))
                }
            }

            // Unexpected Tokens and End-of-Expression are both errors at this point
            Some(unexpected) => Err(ParserError::InvalidPrimaryToken(unexpected.clone(), start)),
            None => Err(ParserError::UnexpectedEndOfExpression),
        }
    }

    fn consume_token(&mut self) -> Option<&Token> {
        self.position += 1;

        self.token_iter.next()
    }


    /*  *  *  *  *  *  *  *\
     *  Helper Functions  *
    \*  *  *  *  *  *  *  */

    fn try_op_from_token(src: &Token) -> Result<Operator, ParserError> {
        match src {
            Token::EqualEqual => Ok(Operator::Logical(LogicalOperator::EqualTo)),
            Token::BangEqual => Ok(Operator::Logical(LogicalOperator::NotEqualTo)),
            Token::GreaterThan => Ok(Operator::Logical(LogicalOperator::GreaterThan)),
            Token::GreaterThanOrEqualTo => {
                Ok(Operator::Logical(LogicalOperator::GreaterThanOrEqualTo))
            }
            Token::LessThan => Ok(Operator::Logical(LogicalOperator::LessThan)),
            Token::LessThanOrEqualTo => Ok(Operator::Logical(LogicalOperator::LessThanOrEqualTo)),
            Token::Plus => Ok(Operator::Arithmetic(ArithmeticOperator::Plus)),
            Token::Minus => Ok(Operator::Arithmetic(ArithmeticOperator::Minus)),
            Token::Star => Ok(Operator::Arithmetic(ArithmeticOperator::Star)),
            Token::Slash => Ok(Operator::Arithmetic(ArithmeticOperator::Slash)),
            _ => Err(ParserError::InvalidOperatorConversion(src.clone())),
        }
    }
}


///////////////////////////////////////////////////////////////////////////////
//  Trait Implementations
///////////////////////////////////////////////////////////////////////////////


/*  *  *  *  *  *  *  *\
 *    ParserError     *
\*  *  *  *  *  *  *  */

impl Error for ParserError {}

impl fmt::Display for ParserError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Self::InvalidOperatorConversion(token) => {
                write!(f, "Could not convert Token '{:?}' to Operator", token)
            }
            Self::InvalidPrimaryToken(token, start) => {
                write!(
                    f,
                    "Invalid token '{:?}' starting at location {}",
                    token, start
                )
            }
            Self::UnexpectedEndOfExpression => {
                write!(f, "Expression ended unexpectedly")
            }
            Self::UnterminatedGroup(expr, start) => {
                write!(
                    f,
                    "Unterminated grouping expression '{}' starting at location {}",
                    expr, start
                )
            }
        }
    }
}


///////////////////////////////////////////////////////////////////////////////
//  Unit Tests
///////////////////////////////////////////////////////////////////////////////

#[cfg(test)]
mod tests {

    use std::error::Error;

    use crate::interpreter::{
        lexer::Lexer,
        parser::{Parser, ParserError},
        ArithmeticOperator, Expression, Literal, Operator, Token, Unary,
    };


    type TestResult = Result<(), Box<dyn Error>>;


    #[test]
    fn output_test() -> TestResult {
        let expr_str = "-123 * (45.67)";

        // Tokenize the expression string
        let mut lexer = Lexer::new(expr_str);
        let tokens = lexer.scan()?;

        // Parse the tokens
        let mut parser = Parser::new(&tokens);
        let expr = parser.parse()?;

        eprintln!("Expression '{}' \"pretty\"-printed:\n{}", expr_str, expr);

        let pretty_expr = format!("{}", expr);
        assert_eq!(pretty_expr, "(* (- 123.0) (group 45.67))");

        Ok(())
    }

    #[test]
    fn invalid_operator_conversion() -> TestResult {
        let valid_token = Token::Plus;
        let invalid_token = Token::LeftBrace;

        assert_eq!(
            Parser::try_op_from_token(&valid_token),
            Ok(Operator::Arithmetic(ArithmeticOperator::Plus))
        );

        assert_eq!(
            Parser::try_op_from_token(&invalid_token),
            Err(ParserError::InvalidOperatorConversion(invalid_token))
        );

        Ok(())
    }

    #[test]
    fn unterm_group() -> TestResult {
        let valid_tokens = vec![
            Token::Number(1.0),
            Token::Plus,
            Token::LeftParen,
            Token::Number(2.0),
            Token::RightParen,
        ];
        let invalid_tokens = vec![
            Token::Number(1.0),
            Token::Plus,
            Token::LeftParen,
            Token::Number(2.0),
            Token::Star,
            Token::Number(5.0),
        ];

        let mut valid_parser = Parser::new(&valid_tokens);
        assert_eq!(
            valid_parser.parse(),
            Ok(Expression::Binary(
                Box::new(Expression::Literal(Literal::Number(1.0))),
                Operator::Arithmetic(ArithmeticOperator::Plus),
                Box::new(Expression::Grouping(Box::new(Expression::Literal(
                    Literal::Number(2.0)
                ))))
            ))
        );

        let mut invalid_parser = Parser::new(&invalid_tokens);
        assert_eq!(
            invalid_parser.parse(),
            Err(ParserError::UnterminatedGroup(
                Expression::Binary(
                    Box::new(Expression::Literal(Literal::Number(2.0))),
                    Operator::Arithmetic(ArithmeticOperator::Star),
                    Box::new(Expression::Literal(Literal::Number(5.0)))
                ),
                2,
            ))
        );

        Ok(())
    }

    #[test]
    fn invalid_primary_token() -> TestResult {
        let valid_tokens = vec![Token::Minus, Token::Number(1.0)];
        let invalid_tokens = vec![Token::Minus, Token::Plus];

        let mut valid_parser = Parser::new(&valid_tokens);
        assert_eq!(
            valid_parser.parse(),
            Ok(Expression::Unary(Unary::Negation(Box::new(
                Expression::Literal(Literal::Number(1.0))
            ))))
        );

        let mut invalid_parser = Parser::new(&invalid_tokens);
        assert_eq!(
            invalid_parser.parse(),
            Err(ParserError::InvalidPrimaryToken(Token::Plus, 1))
        );

        Ok(())
    }

    #[test]
    fn unexpected_eoe() -> TestResult {
        let no_tokens: Vec<Token> = Vec::new();

        let mut invalid_parser = Parser::new(&no_tokens);
        assert_eq!(
            invalid_parser.parse(),
            Err(ParserError::UnexpectedEndOfExpression)
        );

        Ok(())
    }
}