use super::Environment;
use super::Error;
use super::Expression;
use super::{peek, Token};

type Parameter = String;
type Frame = Vec<Parameter>;
type Stack = Vec<Frame>;

fn index(stack: &Stack, name: &String) -> Option<usize> {
    let mut index = 0;
    for frame in stack.iter().rev() {
        for parameter in frame.iter().rev() {
            if *parameter == *name {
                return Some(index);
            };
            index += 1;
        }
    }
    return None;
}

type Result<'a, X=crate::impls::Expression, E=crate::impls::Error> = std::result::Result<(X, &'a str, usize, Stack), E>;

pub fn parse<'a, X, E, N>(input: &str, env: &N) -> std::result::Result<X, E>
where
    X: Expression,
    E: Error,
    N: Environment<X>,
{
    match expression(&input, 0, Vec::new(), env, false) {
        Ok((expr, rest, end, frames)) => match peek(rest, end) {
            (None, _, _, _) if frames.is_empty() => return Ok(expr),
            _ => unreachable!(),
        },
        Err(err) => return Err(err),
    }
}

fn term<'a, X, E, N>(
    input: &'a str,
    beginning: usize,
    frames: Stack,
    env: &N,
    pflag: bool,
) -> Result<'a, X, E>
where
    X: Expression,
    E: Error,
    N: Environment<X>,
{
    // term is a common name for a variable, an abstraction and an another parenthesised term
    //   term = variable | abstraction | "(", term, ")"
    // to determine what's actually inside a term we need to look at the next token in the input
    // the peek function is capable of returning the next token, so we match on that
    match peek(input, beginning) {
        (Some(Token::OpenParenthesis), _, _, _) => {
            // the parser encountered an open parenthesis, so we must enter a new parenthesized scope
            return parenthesized_expression(input, beginning, frames, env);
        }
        (Some(Token::Lambda), _, rest, end) => {
            // the parser encountered a lambda token, so the term must be an abstraction
            // accept the lambda token and move on
            match peek(rest, end) {
                (Some(Token::Identifier(name)), _, rest, end) => {
                    // encountered the requisite identifier
                    // declare a vector of identifiers and push the first one
                    let mut parameters = Vec::new();
                    parameters.push(name);
                    // read identifiers until there are none
                    let mut lrest = rest;
                    let mut lend = end;
                    while let (Some(Token::Identifier(name)), _, rest, end) = peek(lrest, lend) {
                        parameters.push(name);
                        lrest = rest;
                        lend = end;
                    }
                    match peek(lrest, lend) {
                        (Some(Token::Dot), _, rest, end) => {
                            // if the token is a dot we terminate the identifier reading
                            // a vector of collected identifiers is called a stack frame
                            let mut frames = frames;
                            // push the current stack frame onto the stack
                            //remember the parameter count
                            let parameter_count = parameters.len();
                            frames.push(parameters);
                            // parse the body of the abstraction
                            match expression(rest, end, frames, env, pflag) {
                                Ok((expr, rest, end, frames)) => {
                                    // construct a chain of abstractions -- one for each parameter
                                    // abstraction -> abstraction -> ... -> abstraction -> body
                                    let mut chain = expr;
                                    for _ in 0..parameter_count {
                                        chain = X::abstraction(chain);
                                    }
                                    // pop off the frame
                                    let mut frames = frames;
                                    frames.pop();
                                    let frames = frames;
                                    // finally return
                                    return Ok((chain, rest, end, frames));
                                }
                                Err(err) => return Err(err),
                            }
                        }
                        (_, position, _, _) => return Err(E::dot_expected(position)),
                    }
                }
                (_, position, _, _) => return Err(E::parameter_expected(position)),
            }
        }
        (Some(Token::Identifier(name)), position, rest, end) => {
            // accept the variable name and get its index from the current frame stack
            if let Some(index) = index(&frames, &name) {
                let variable = X::variable(index + 1);
                return Ok((variable, rest, end, frames));
            } else if let Some(expr) = env.get_expression(&name) {
                return Ok((expr.clone(), rest, end, frames));
            } else {
                return Err(E::unbound_variable(name, position));
            }
        }
        (Some(Token::Dot), position, _, _) => return Err(E::dot_unexpected(position)),
        (Some(Token::CloseParenthesis), position, _, _) => {
            return Err(E::close_parenthesis_unexpected(position))
        }
        (None, position, _, _) => return Err(E::end_unexpected(position)),
    }
}

fn parenthesized_expression<'a, X, E, N>(
    input: &'a str,
    beginning: usize,
    frames: Stack,
    env: &N,
) -> Result<'a, X, E>
where
    X: Expression,
    E: Error,
    N: Environment<X>,
{
    match peek(input, beginning) {
        (Some(Token::OpenParenthesis), _, rest, end) => match peek(rest, end) {
            (Some(Token::CloseParenthesis), position, _, _) => {
                return Err(E::no_expression(position))
            }
            (None, position, _, _) => return Err(E::close_parenthesis_expected(position)),
            (Some(Token::Dot), position, _, _) => return Err(E::dot_unexpected(position)),
            _ => match term(rest, end, frames, env, true) {
                Ok((expr, rest, end, frames)) => {
                    let mut tree = expr;
                    let mut lrest = rest;
                    let mut lend = end;
                    let mut lframes = frames;
                    loop {
                        let expr = match peek(lrest, lend) {
                            (Some(Token::CloseParenthesis), _, rest, end) => {
                                lrest = rest;
                                lend = end;
                                break;
                            }
                            (None, position, _, _) => {
                                return Err(E::close_parenthesis_expected(position))
                            }
                            (Some(Token::Dot), position, _, _) => {
                                return Err(E::dot_unexpected(position))
                            }
                            _ => match term(lrest, lend, lframes, env, true) {
                                Ok((expr, rest, end, frames)) => {
                                    lrest = rest;
                                    lend = end;
                                    lframes = frames;
                                    expr
                                }
                                Err(err) => return Err(err),
                            },
                        };
                        tree = X::application(tree, expr);
                    }
                    return Ok((tree, lrest, lend, lframes));
                }
                Err(err) => return Err(err),
            },
        },
        (_, position, _, _) => return Err(E::open_parenthesis_expected(position)),
    }
}

fn expression<'a, X, E, N>(
    input: &'a str,
    beginning: usize,
    frames: Stack,
    env: &N,
    pflag: bool,
) -> Result<'a, X, E>
where
    X: Expression,
    E: Error,
    N: Environment<X>,
{
    match peek(input, beginning) {
        (Some(Token::CloseParenthesis), position, _, _) if pflag => {
            return Err(E::no_expression(position));
        }
        (Some(Token::CloseParenthesis), position, _, _) => {
            return Err(E::close_parenthesis_unexpected(position));
        }
        (None, position, _, _) => {
            return Err(E::no_expression(position));
        }
        (Some(Token::Dot), position, _, _) => {
            return Err(E::dot_unexpected(position));
        }
        _ => match term(input, beginning, frames, env, pflag) {
            Ok((expr, rest, end, frames)) => {
                let mut tree = expr;
                let mut lrest = rest;
                let mut lend = end;
                let mut lframes = frames;
                loop {
                    let expr = match peek(lrest, lend) {
                        (Some(Token::CloseParenthesis), _, _, _) if pflag => break,
                        (Some(Token::CloseParenthesis), position, _, _) => {
                            return Err(E::close_parenthesis_unexpected(position))
                        }
                        (None, _, _, _) => break,
                        (Some(Token::Dot), position, _, _) => {
                            return Err(E::dot_unexpected(position))
                        }
                        _ => match term(lrest, lend, lframes, env, pflag) {
                            Ok((expr, rest, end, frames)) => {
                                lrest = rest;
                                lend = end;
                                lframes = frames;
                                expr
                            }
                            Err(err) => return Err(err),
                        },
                    };
                    tree = X::application(tree, expr);
                }
                return Ok((tree, lrest, lend, lframes));
            }
            Err(err) => return Err(err),
        },
    }
}

#[cfg(test)]
mod tests {
    use crate::impls::{Environment, Error, Expression};

    #[test]
    fn index_variables() {
        use super::index;

        let frames = vec![
            vec!["x".to_owned(), "y".to_owned()],
            vec!["z".to_owned()],
            vec!["a".to_owned(), "b".to_owned()],
        ];
        assert_eq!(index(&frames, &"x".to_owned()), Some(4));
        assert_eq!(index(&frames, &"b".to_owned()), Some(0));
        assert_eq!(index(&frames, &"a".to_owned()), Some(1));
        assert_eq!(index(&frames, &"none".to_owned()), None);
    }

    #[test]
    fn parse_identity() {
        use super::parse;

        let identity = Expression::Abstraction(Box::new(Expression::Variable(1)));
        let env = Environment::new();
        assert_eq!(
            parse::<_, Error, _>(&"\\x.x".to_owned(), &env),
            Ok(identity.clone())
        );
        assert_eq!(
            parse::<_, Error, _>(&"   \\  x . x    ".to_owned(), &env),
            Ok(identity.clone())
        );
        assert_eq!(
            parse::<_, Error, _>(&"\\aaa.aaa".to_owned(), &env),
            Ok(identity.clone())
        );
        assert_eq!(
            parse::<_, Error, _>(&"\\漢. 漢".to_owned(), &env),
            Ok(identity.clone())
        );
    }

    #[test]
    fn contract_sequence_of_abstractions() {
        use super::parse;

        let env = Environment::new();
        assert_eq!(
            parse::<_, Error, _>(&"\\a.\\b.\\c.a b c".to_owned(), &env),
            parse(&"\\a b c.a b c".to_owned(), &env)
        );
        assert_eq!(
            parse::<_, Error, _>(&"\\a b.a".to_owned(), &env),
            Ok(Expression::Abstraction(Box::new(
                Expression::Abstraction(Box::new(Expression::Variable(2)))
            )))
        );
    }

    #[test]
    fn drop_outermost_parentheses() {
        use super::parse;

        let env: Environment<Expression> = Environment::new();
        assert_eq!(
            parse::<_, Error, _>(&"(\\x.x)".to_owned(), &env),
            parse(&"\\x.x".to_owned(), &env)
        );
    }

    #[test]
    fn check_left_associativity() {
        use super::parse;

        let env = Environment::new();
        assert_eq!(
            parse::<_, Error, _>(&"\\x.x x x".to_owned(), &env),
            parse(&"\\x.(x x) x".to_owned(), &env)
        );
        assert_eq!(
            parse::<_, Error, _>(&"\\x.x x x".to_owned(), &env),
            Ok(Expression::Abstraction(Box::new(
                Expression::Application(
                    Box::new(Expression::Application(
                        Box::new(Expression::Variable(1)),
                        Box::new(Expression::Variable(1))
                    )),
                    Box::new(Expression::Variable(1))
                )
            )))
        );
    }

    #[test]
    fn parse_sequence_of_abstractions() {
        use super::parse;

        let zero_numeral = Expression::Abstraction(Box::new(Expression::Abstraction(Box::new(
            Expression::Variable(1),
        ))));
        let env = Environment::new();
        assert_eq!(
            parse::<_, Error, _>(&"\\f.\\x.x".to_owned(), &env),
            Ok(zero_numeral.clone())
        );
        assert_eq!(
            parse::<_, Error, _>(&"\\ α β . β  ".to_owned(), &env),
            Ok(zero_numeral.clone())
        );
    }
}