// Please refer to grammar.ebnf for the outline of how the parser works. It is a mandatory read,
// and every change you make here, you must update the grammar with.

//! For using the symbols generated by the lexer and making sense of them in the context of
//! mathematical expressions.

use std::slice::Iter;
use std::iter::Peekable;

use crate::lexer::*;

#[derive(Debug, Clone, PartialEq)]
pub enum Expr {
    BinOp(Operator, Box<Expr>, Box<Expr>),
    Pow(Box<Expr>, Box<Expr>),
    Neg(Box<Expr>),
    Function(Function, Box<Expr>),
    Assignment(String, Box<Expr>),
    Constant(f64),
    Identifier(String),
}

impl Expr {
    /// Replaces all instances of `old` with `new`. This method returns `true` if a value has been replaced, and `false` otherwise.
    /// # Example
    /// One could use this function to replace all references to an identifier "x" with the constant `20`.
    /// ```
    /// let input = "x^2 * 4";
    /// let replacement = parser::Expr::Constant(20.);
    /// let mut ast = parser::parse(&lexer::tokenize(&input).unwrap()).unwrap();
    /// ast.replace(&parser::Expr::Identifier(String::from("x")), &replacement, false);
    /// assert_eq!(computer::compute(&ast), 1600.);
    /// ```
    #[allow(dead_code)]
    pub fn replace(&mut self, old: &Expr, new: &Expr, ignore_fields: bool) -> bool {
        if ignore_fields {
            if std::mem::discriminant(self) == std::mem::discriminant(old) {
                *self = new.clone();
                return true;
            }
        } else {
            if self == old {
                *self = new.clone();
                return true;
            }
        }

        let mut replaced = false;
        match self {
            Expr::BinOp(_, a, b) => {
                if a.replace(old, new, ignore_fields) { replaced = true; }
                if b.replace(old, new, ignore_fields) { replaced = true; }
            }
            Expr::Pow(a, b) => {
                if a.replace(old, new, ignore_fields) { replaced = true; }
                if b.replace(old, new, ignore_fields) { replaced = true; }
            }
            Expr::Neg(a) => {
                if a.replace(old, new, ignore_fields) { replaced = true; }
            }
            Expr::Function(_, a) => {
                if a.replace(old, new, ignore_fields) { replaced = true; }
            }
            _ => {}
        }

        replaced
    }
}

#[derive(Debug, Clone, PartialEq)]
pub enum ParserError {
    ExpectedClosingParenthesis,
    ExpectedClosingPipe,
    /// Its value is the `Token` that was found instead of a factor.
    ExpectedFactor(Option<Token>),
    UnexpectedNumber(Token),
}
use self::ParserError::*;

/// For detecting parsing errors using an iterative solution. This function can tell when
/// users accidentally enter an expression such as "2x" (when they mean "2(x)"). But just
/// as easily detects unknowingly valid expressions like "neg 3" where "neg" is currently
/// `Token::Identifier`.
pub fn preprocess(tokens: &[Token]) -> Option<ParserError> {
    // Preprocess and preemptive erroring on inputs like "2x"
    let mut t = tokens.iter().peekable();
    while let Some(tok) = t.next() {
        match tok {
            Token::Number(_) | Token::Constant(_) | Token::Identifier(_) => {
                if let Some(peek_tok) = t.peek() {
                    match peek_tok {
                        Token::Number(_) | Token::Constant(_) | Token::Identifier(_) => {
                            return Some(UnexpectedNumber((*peek_tok).clone()));
                        }
                        _ => {}
                    }
                }
            }
            _ => {}
        }
    }
    None
}

/// Turn an array of tokens into an expression, which can be computed into a final number.
pub fn parse(tokens: &[Token]) -> Result<Expr, ParserError> {
    match preprocess(tokens) {
        Some(e) => Err(e),
        None => parse_additive_expr(&mut tokens.iter().peekable()),
    }
}

/// Same as `parse`, except this does not automatically run `preprocess`. There are a few reasons one may use this function:
/// * Performance or timing
/// * AST will have identifiers that act as functions
/// * You have your own preprocess function
/// If you are not sure, use default `parse` instead.
#[allow(dead_code)]
pub fn parse_no_preprocess(tokens: &[Token]) -> Result<Expr, ParserError> {
    parse_additive_expr(&mut tokens.iter().peekable())
}

/// Additive expressions are things like `expr + expr`, or `expr - expr`. It reads a multiplicative
/// expr first, which allows precedence to exist.
fn parse_additive_expr(tokens: &mut Peekable<Iter<Token>>) -> Result<Expr, ParserError> {
    let mut expr = parse_multiplicative_expr(tokens)?;
    loop {
        match tokens.peek() {
            Some(Token::Operator(op)) if op == &Operator::Plus || op == &Operator::Minus => {
                tokens.next();
                let r_expr = parse_multiplicative_expr(tokens)?;
                expr = Expr::BinOp(*op, Box::new(expr), Box::new(r_expr));
            }
            _ => break,
        }
    }
    Ok(expr)
}

/// Multiplicative expressions are `expr * expr`, or `expr / expr`.
fn parse_multiplicative_expr(tokens: &mut Peekable<Iter<Token>>) -> Result<Expr, ParserError> {
    let mut expr = parse_parenthetical_multiplicative_expr(tokens)?;
    loop {
        match tokens.peek() {
            Some(Token::Operator(op)) if op == &Operator::Star || op == &Operator::Slash => {
                tokens.next();
                let r_expr = parse_parenthetical_multiplicative_expr(tokens)?;
                expr = Expr::BinOp(*op, Box::new(expr), Box::new(r_expr));
            }
            _ => break,
        }
    }
    Ok(expr)
}

/// Parenthetical, multiplicative expressions are just expressions times an expression wrapped in parenthesis: `expr(expr)`, which is
/// the same as `expr * expr`.
fn parse_parenthetical_multiplicative_expr(tokens: &mut Peekable<Iter<Token>>) -> Result<Expr, ParserError> {
    let mut expr = parse_power_expr(tokens)?;
    loop {
        match tokens.peek() {
            Some(Token::Operator(op)) if op == &Operator::LParen => {
                tokens.next();
                let internal_expr = parse_additive_expr(tokens)?;
                match tokens.next() {
                    Some(Token::Operator(op)) if op == &Operator::RParen => expr = Expr::BinOp(Operator::Star, Box::new(expr), Box::new(internal_expr)),
                    _ => return Err(ExpectedClosingParenthesis),
                }
            }
            _ => break,
        }
    }
    Ok(expr)
}

/// Power expressions are any expressions with an exponential: `factor ^ factor`.
fn parse_power_expr(tokens: &mut Peekable<Iter<Token>>) -> Result<Expr, ParserError> {
    let mut expr = parse_factor(tokens)?;
    loop {
        match tokens.peek() {
            Some(Token::Operator(op)) if op == &Operator::Caret => {
                tokens.next();
                let exponent = parse_factor(tokens)?;
                expr = Expr::Pow(Box::new(expr), Box::new(exponent));
            }
            _ => break,
        }
    }
    Ok(expr)
}

/// The most important item -- a factor. A factor is generally the bottom level ideas
/// like numbers or expressions in parenthesis. The factor makes the recursion in `Expr`
/// finite.
fn parse_factor(tokens: &mut Peekable<Iter<Token>>) -> Result<Expr, ParserError> {
    match tokens.next() {
        // Parenthetical expressions such as `(expr)`.
        Some(Token::Operator(Operator::LParen)) => {
            let expr = parse_additive_expr(tokens);
            match tokens.next() {
                Some(Token::Operator(Operator::RParen)) => expr,
                _ => Err(ExpectedClosingParenthesis),
            }
        }
        Some(Token::Operator(Operator::Pipe)) => {
            let expr = parse_additive_expr(tokens)?;
            match tokens.next() {
                Some(Token::Operator(Operator::Pipe)) => Ok(Expr::Function(Function::Abs, Box::new(expr))),
                _ => return Err(ExpectedClosingPipe),
            }
        }
        Some(Token::Function(function)) => {
            Ok(Expr::Function(*function, Box::new(parse_factor(tokens)?))) // All functions assume the next factor is its operand.
        }
        Some(Token::Constant(constant)) => {
            Ok(Expr::Constant(match constant {
                Constant::Pi => ::std::f64::consts::PI,
                Constant::E => ::std::f64::consts::E,
            }))
        }
        Some(Token::Identifier(id)) => {
            match tokens.peek() {
                Some(Token::Operator(Operator::Equals)) => {
                    tokens.next();
                    Ok(Expr::Assignment(id.clone(), Box::new(parse_additive_expr(tokens)?)))
                }
                _ => Ok(Expr::Identifier(id.clone())),
            }
        }
        Some(Token::Operator(Operator::Minus)) => {
            Ok(Expr::Neg(Box::new(parse_factor(tokens)?))) // Unary negative expressions like `-factor`.
        }
        Some(Token::Number(n)) => Ok(Expr::Constant(*n)), // Number constants like `3`, `2.21`, `.34` or `-.2515262`.
        t => Err(ExpectedFactor(t.cloned())), // The token being read isn't in the right place.
    }
}