//! This is an `Iterator` and `Result` first minimal LL1 parsing library.
//!
//! The code in this file assumes that an outer `Result::Err` is only recoverable (when recovery is requested) if none of the input is consumed.

/// An itterator wrapper that provides single item lookahead and tracks acceptance.
pub struct Tokens<I: Iterator> {
    iter: I,
    lookahead: Option<I::Item>,
    accepted: bool
}

impl<I: Iterator> Tokens<I> {
    /// Wraps a given parser, lookahead is done on an as-needed basis.
    pub fn new(iter: I) -> Self {
        Tokens {
            iter,
            lookahead: None,
            accepted: false
        }
    }

    /// Runs parsing code and tracks token acceptance.
    ///
    /// The `bool` return indicates wether or not any tokens were accepted.
    pub fn scope<T>(
        &mut self,
        f: impl for<'a> FnOnce(&'a mut Self) -> T
    )
        -> (bool, T)
    {
        let outer_accepted = self.accepted;
        self.accepted = false;
        let x = f(self);
        let inner_accepted = self.accepted;
        self.accepted |= outer_accepted;
        (inner_accepted, x)
    }

    fn peak_inner(&mut self) -> &mut Option<I::Item> {
        if self.lookahead.is_none() {
            self.lookahead = self.iter.next();
        };
        &mut self.lookahead
    }

    /// Looks at the next item if present.
    ///
    /// *this method is mutable because we take from the base iterator on an as-needed basis*
    pub fn peak(&mut self) -> Option<&I::Item> {
        self.peak_inner().as_ref()
    }

    fn scry_or_inner<T, F: for<'a> FnOnce(I::Item, &'a mut Self) -> T>(
        &mut self,
        f: impl for<'a> FnOnce(&'a I::Item) -> Option<F>,
        def: impl FnOnce() -> Option<T>
    )
        -> Option<T>
    {
        match self.peak_inner().take() {
            Some(tok) => match f(&tok) {
                Some(g) => {
                    self.accepted = true;
                    Some(g(tok, self))
                },
                None => {
                    self.lookahead = Some(tok);
                    None
                }
            },
            None => def()
        }
    }

    /// Decides wether to accept the next token, providing a default value if there is no next token.
    pub fn scry_or<T, F: for<'a> FnOnce(I::Item, &'a mut Self) -> T>(
        &mut self,
        f: impl for<'a> FnOnce(&'a I::Item) -> Option<F>,
        def: impl FnOnce() -> T
    )
        -> Option<T>
    {
        self.scry_or_inner(f, move || Some(def()))
    }
    
    /// Decide wether to accept the next token if present.
    pub fn scry<T, F: for<'a> FnOnce(I::Item, &'a mut Self) -> T>(
        &mut self,
        f: impl for<'a> FnOnce(&'a I::Item) -> Option<F>
    )
        -> Option<T>
    {
        self.scry_or_inner(f, || None)
    }
}

impl<I: Iterator> Iterator for Tokens<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(tok) = self.lookahead.take() {
            self.accepted = true;
            return Some(tok)
        };
        if let Some(tok) = self.iter.next() {
            self.accepted = true;
            return Some(tok)
        };
        None
    }
}

/// Attempt to run a parser, recovering if no tokens were consumed.
pub fn try_parse<I: Iterator, T, E>(
    tokens: &mut Tokens<I>,
    f: impl FnOnce(&mut Tokens<I>) -> Result<T, E>
)
    -> Result<Result<T, E>, E>
{
    let (accepted, res) = tokens.scope(f);
    match res {
        Ok(x) => Ok(Ok(x)),
        Err(e) => if accepted {
            Err(e)
        } else {
            Ok(Err(e))
        }
    }
}

/// Runs continually whilst tokens are accepted, useful for repeated attempts like handling unordered terms.
pub fn while_accepted<I: Iterator, T, E>(
    tokens: &mut Tokens<I>,
    mut f: impl FnMut(&mut Tokens<I>) -> Result<T, E>
)
    -> (Vec<T>, Result<T, E>)
{
    let mut xs = vec![];
    loop {
        let (accepted, res) = tokens.scope(&mut f);
        if !accepted {
            break (xs, res);
        }
        match res {
            Ok(x) => xs.push(x),
            Err(e) => break (xs, Err(e))
        }
    }
}

/// Access the contents of an option or parse to inhabit it.
pub fn get_or_parse<'a, I: Iterator, T, E>(
    tokens: &mut Tokens<I>,
    option: &'a mut Option<T>,
    f: impl FnOnce(&mut Tokens<I>) -> Result<T, E>
)
    -> Result<&'a mut T, E>
{
    if let Some(x) = option {
        return Ok(x)
    };
    *option = Some(f(tokens)?);
    Ok(option.as_mut().unwrap_or_else(|| unreachable!()))
}

/// Access the contents of a result or store a recovered error.
pub fn get_or_try_parse<'a, I: Iterator, T, E>(
    tokens: &mut Tokens<I>,
    result: &'a mut Result<T, E>,
    f: impl FnOnce(&mut Tokens<I>) -> Result<T, E>
)
    -> Result<Option<&'a mut T>, E>
{
    if let Ok(x) = result {
        return Ok(Some(x))
    };
    *result = try_parse(tokens, f)?;
    Ok(result.as_mut().ok())
}

/// Parse a value from a single token, raising a pre-determined error on failure.
pub fn some_token<I: Iterator, T, E>(
    tokens: &mut Tokens<I>,
    e: E,
    f: impl for<'a> FnOnce(&'a I::Item) -> Option<T>
)
    -> Result<T, E>
{
    tokens.scry(move |tok| f(tok).map(|x| |_: I::Item, _: &mut Tokens<I>| x)).ok_or(e)
}

/// Expect the end of the iterator.
pub fn iter_end<I: Iterator, E>(tokens: &mut Tokens<I>, e: E) -> Result<(), E> {
    tokens.peak().is_none().then_some(()).ok_or(e)
}

/// Try the first, then the second.
pub fn or<I: Iterator, T, E>(
    f: impl for<'a> FnOnce(&'a mut Tokens<I>) -> Result<T, E>,
    g: impl for<'a> FnOnce(&'a mut Tokens<I>) -> Result<T, E>
)
    -> impl for<'a> FnOnce(&'a mut Tokens<I>) -> Result<T, E>
{
    move |tokens| try_parse(tokens, f)?.or_else(|_| g(tokens))
}

/// Parse multiple items until a recoverable error.
pub fn list<I: Iterator, T, E>(
    mut f: impl for<'a> FnMut(&'a mut Tokens<I>) -> Result<T, E>
)
    -> impl for<'a> FnMut(&'a mut Tokens<I>) -> Result<Vec<T>, E>
{
    move |tokens: &mut Tokens<I>| {
        let mut xs = vec![];
        while let Ok(x) = try_parse(tokens, &mut f)? {
            xs.push(x)
        }
        Ok(xs)
    }
}

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

    type TestIter = std::vec::IntoIter<&'static str>;
    type TestError = &'static str;
    
    fn parse_end(tokens: &mut Tokens<TestIter>) -> Result<(), TestError> {
        iter_end(tokens, "expected end of stream")
    }

    #[test]
    fn true_end() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec![].into_iter());

        assert_eq!(parse_end(&mut tokens), Ok(()));
    }

    #[test]
    fn false_end() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["a"].into_iter());

        assert_eq!(parse_end(&mut tokens), Err("expected end of stream"));
    }

    fn parse_a(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
        some_token(tokens, "expected 'a' or 'A'", |tok| match *tok {
            "a" => Some(false),
            "A" => Some(true),
            _ => None
        })
    }


    fn parse_b(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
        some_token(tokens, "expected 'b' or 'B'", |tok| match *tok {
            "b" => Some(false),
            "B" => Some(true),
            _ => None
        })
    }


    fn parse_c(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
        some_token(tokens, "expected 'c' or 'C'", |tok| match *tok {
            "c" => Some(false),
            "C" => Some(true),
            _ => None
        })
    }

    #[test]
    fn simple_error() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["B"].into_iter());

        assert_eq!(parse_a(&mut tokens), Err("expected 'a' or 'A'"));
    }

    #[test]
    fn series() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["A", "b", "C"].into_iter());

        fn test_parser(tokens: &mut Tokens<TestIter>) -> Result<[bool; 3], TestError> {
            Ok([parse_a(tokens)?, parse_b(tokens)?, parse_c(tokens)?])
        }

        assert_eq!(test_parser(&mut tokens), Ok([true, false, true]));
        assert_eq!(parse_end(&mut tokens), Ok(()));
    }

    #[test]
    fn parallel_0() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["B"].into_iter());

        fn test_parser(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
            or(parse_a, or(parse_b, parse_c))(tokens)
        }

        assert_eq!(test_parser(&mut tokens), Ok(true));
        assert_eq!(parse_end(&mut tokens), Ok(()));
    }

    #[test]
    fn parallel_1() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["B"].into_iter());

        fn test_parser(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
            or(or(parse_a, parse_b), parse_c)(tokens)
        }

        assert_eq!(test_parser(&mut tokens), Ok(true));
        assert_eq!(parse_end(&mut tokens), Ok(()));
    }


    fn parse_any(tokens: &mut Tokens<TestIter>) -> Result<&'static str, TestError> {
        tokens.next().ok_or("unexpected end of stream")
    }

    fn parse_complex(tokens: &mut Tokens<TestIter>) -> Result<&'static str, TestError> {
        some_token(tokens, "expected '->'", |tok| match *tok {
            "->" => Some(()),
            _ => None
        })?;
        parse_any(tokens)
    }

    #[test]
    fn deep_error() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["->"].into_iter());

        fn test_parser(tokens: &mut Tokens<TestIter>) -> Result<&'static str, TestError> {
            or(parse_complex, parse_any)(tokens)
        }

        assert_eq!(test_parser(&mut tokens), Err("unexpected end of stream"));
    }

    #[test]
    fn shallow_error() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["x"].into_iter());

        fn test_parser(tokens: &mut Tokens<TestIter>) -> Result<&'static str, TestError> {
            or(parse_complex, parse_any)(tokens)
        }

        assert_eq!(test_parser(&mut tokens), Ok("x"));
        assert_eq!(parse_end(&mut tokens), Ok(()));
    }

    fn parse_d(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
        some_token(tokens, "expected 'd' or 'D'", |tok| match *tok {
            "d" => Some(false),
            "D" => Some(true),
            _ => None
        })
    }


    fn parse_e(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
        some_token(tokens, "expected 'e' or 'E'", |tok| match *tok {
            "e" => Some(false),
            "E" => Some(true),
            _ => None
        })
    }

    fn parse_f(tokens: &mut Tokens<TestIter>) -> Result<bool, TestError> {
        some_token(tokens, "expected 'f' or 'F'", |tok| match *tok {
            "f" => Some(false),
            "F" => Some(true),
            _ => None
        })
    }

    #[test]
    fn unordered() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["d", "C", "B", "f", "A", "e"].into_iter());

        println!("");

        fn test_parser(tokens: &mut Tokens<TestIter>) -> Result<[bool; 6], TestError> {
            let mut a = Err("");
            let mut b = Err("");
            let mut c = Err("");
            let mut d = Err("");
            let mut e = Err("");
            let mut f = Err("");
            while_accepted(tokens, |tokens| {
                get_or_try_parse(tokens, &mut a, parse_a)?;
                get_or_try_parse(tokens, &mut b, parse_b)?;
                get_or_try_parse(tokens, &mut c, parse_c)?;
                get_or_try_parse(tokens, &mut d, parse_d)?;
                get_or_try_parse(tokens, &mut e, parse_e)?;
                get_or_try_parse(tokens, &mut f, parse_f)?;
                Ok(())
            }).1?;
            Ok([a?, b?, c?, d?, e?, f?])
        }

        assert_eq!(test_parser(&mut tokens), Ok([true, true, true, false, false, false]));
        assert_eq!(parse_end(&mut tokens), Ok(()));
    }

    fn parse_expr(tokens: &mut Tokens<TestIter>) -> Result<usize, TestError> {
        tokens.scry::<_, for<'a> fn(_, &'a mut _) -> _>(|tok| match *tok {
            "(" => Some(|_, tokens| {
                let n = tokens.scry::<_, for<'a> fn(_, &'a mut _) -> _>(|tok| match *tok {
                    "*" => Some(|_, tokens| Ok(list(parse_expr)(tokens)?.into_iter().product())),
                    "+" => Some(|_, tokens| Ok(list(parse_expr)(tokens)?.into_iter().sum())),
                    _ => None
                }).ok_or("expected operator").flatten()?;
                some_token(tokens, "expected ending bracket", |tok| (*tok == ")").then_some(()))?;
                Ok(n)
            }),
            tok if tok.chars().all(char::is_numeric) => Some(|tok, _|
                tok.parse::<usize>().map_err(|_| "malformed number")
            ),
            _ => None
        }).ok_or("expected expression").flatten()
    }
    
    #[test]
    fn calculator() {
        let mut tokens: Tokens<TestIter> = Tokens::new(vec!["(", "+", "(", "*", "2", "4", ")", "(", "*", "2", "2", "2", "2", ")", ")"].into_iter());

        assert_eq!(parse_expr(&mut tokens), Ok(24));
    }
}
