use std::fmt;
use std::ops::{ControlFlow, RangeFrom, RangeInclusive, RangeToInclusive};

// These types were extracted as their signatures were getting too long for clippy

/// A [`Fold`] init function that uses a `Vec` as an accumulator
pub type AccumulateInit<Out> = fn() -> Vec<Out>;
/// A [`Fold`] operation function that uses a `Vec` as an accumulator
pub type AccumulateOperation<Out> = fn(Vec<Out>, Out) -> Vec<Out>;
/// A [`Fold`] init function that does not use an accumulator.
pub type RepeatsInit = fn() -> ();
/// A [`Fold`] operation function that does nothing with what is given to it
pub type RepeatsOperation<Out> = fn((), Out) -> ();

/// A trait for parsers
///
/// A `Parser` accepts input of type `In` and tries to match it. If it succeeds, it returns a
/// value of type `Some<(Out, In)>`. The first element of the tuple is the parser's output, and the
/// second is whatever is left of the input after parsing. If the parser fails, it returns `None`
///
///
/// Given a _thing_ that implements `Parser`, calling one of the associated methods returns a new
/// `Parser` that augments its functionality.
pub trait Parser<In> {
    // Note: I had tried both of these definitions:
    //
    // (a) `Parser<In, Out>` and
    // (b) `Parser` with `In` and `Out` associated types.
    //
    // (a) was problematic when implementing the trait for `Map` or parsers with a concrete return
    // type. You end up with an unconstrained `Out` type parameter. I got around this by using
    // `PhantomData`...which i didn't really want to keep around.
    //
    // (b) meant I could not implement the trait for all `F` where `F:
    // Fn(In) -> Out` because the `In` type would be unconstrained.
    //
    // The Fix to this is to make `In` generic and `Out` associated. There seems to be some theory
    // to why this is the right way to go, but I can't quite articulate it. So i'll leave some
    // relevant links:
    //
    // My question in the forums: https://users.rust-lang.org/t/unconstrained-type-parameter-when-using-generic-trait/100698
    // Discussion around why Fn output should be an associated type: https://github.com/rust-lang/rust/issues/20871

    /// The type this parser outputs if successfull
    type Out;

    /// Recognizes a value from the input and returns the result
    ///
    /// Reports an error if the input could not be matched.
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)>;

    /// Returns a parser that applies the function `f` to its output
    ///
    /// ```
    /// use parser_compose::Parser;
    ///
    /// let msg = "a";
    ///
    /// let (value, _) = "a".map(|s| s.to_ascii_uppercase()).try_parse(msg).unwrap();
    ///
    /// assert_eq!(value, "A");
    /// ```
    fn map<F, Mapped>(self, f: F) -> Map<Self, F>
    where
        Self: Sized,
        F: Fn(Self::Out) -> Mapped,
    {
        Map { parser: self, f }
    }

    /// Returns a parser that calls the `next` parser if it fails to match its input.
    ///
    /// ```
    /// use  parser_compose::Parser;
    ///
    /// let msg = "a";
    ///
    /// let (value, _) = "1".or("a").try_parse(msg).unwrap();
    ///
    /// assert_eq!(value, "a");
    /// ```
    fn or<P>(self, next: P) -> Or<Self, P>
    where
        Self: Sized,
    {
        Or {
            parser1: self,
            parser2: next,
        }
    }

    /// Returns a parser that only succeeds if `pred` returns `true` when given the parser's output
    /// ```
    /// use parser_compose::{first_utf8_scalar,Parser};
    ///
    /// let msg = "boo";
    ///
    /// let (value, _) = first_utf8_scalar.when(|s| s == "b").try_parse(msg).unwrap();
    ///
    /// assert_eq!(value, "b");
    /// ```
    fn when<F>(self, predicate: F) -> Predicate<Self, F>
    where
        Self: Sized,
        F: Fn(Self::Out) -> bool,
    {
        Predicate {
            parser: self,
            predicate,
        }
    }

    /// Returns a parser that succeeds if it is able to match its input `count` times.
    ///
    /// The funcion `op` is executed for each successful repetition. Its return value is used as an
    /// argument for its next invocation.
    ///
    /// The function `init` determines what the argument to `op` will be the first time it is
    /// called.
    ///
    /// `.fold()` is useful whenever you want invoke a parser multiple times and do something with
    /// the result of each invocation.
    ///
    /// Here is a contrived example:
    /// ```
    /// use parser_compose::{Parser, utf8_scalar};
    /// use std::str::FromStr;
    ///
    /// fn digit(input: &str) -> Option<(u8, &str)> {
    ///     utf8_scalar(0x30..=0x39)
    ///     .and_then(u8::from_str)
    ///     .try_parse(input)
    /// }
    ///
    /// // We want to sum the digits in this string
    /// let input = "8.8.2.4";
    ///
    /// let sum_parser = (digit, ".".optional()).fold(4, |accum, curr| accum + curr.0, || 0u8);
    ///
    /// let (sum, rest) = sum_parser.try_parse(input).unwrap();
    ///
    /// assert_eq!(sum , 22);
    /// assert!(rest.is_empty());
    /// ```
    fn fold<R, Op, Init, IV>(self, count: R, op: Op, init: Init) -> Fold<Self, Op, Init>
    where
        R: RepetitionArgument,
        Init: Fn() -> IV,
        Op: Fn(IV, Self::Out) -> IV,
        Self: Sized,
    {
        Fold {
            parser: self,
            at_least: count.at_least(),
            at_most: count.at_most(),
            op,
            init,
        }
    }

    /// Returns a parser that succeeds if it is able to match its input `count` times, discarding
    /// any output along the way
    ///
    /// ```
    /// use parser_compose::{Parser, utf8_scalar};
    ///
    /// let valid_number = "123-456-7899";
    /// let invalid_number = "123-3454-34";
    ///
    /// let digit = utf8_scalar(0x30..=0x39);
    /// let validator = (digit.repeats(3), "-", digit.repeats(3), "-", digit.repeats(4));
    ///
    /// let (value, rest) = validator.try_parse(valid_number).unwrap();
    /// assert_eq!(value, ((), "-", (), "-", ()));
    /// assert_eq!(rest, "");
    ///
    /// let res = validator.try_parse(invalid_number.into());
    /// assert!(res.is_none());
    ///
    /// ```
    fn repeats<R>(self, count: R) -> Fold<Self, RepeatsOperation<Self::Out>, RepeatsInit>
    where
        Self: Sized,
        R: RepetitionArgument,
    {
        Fold {
            parser: self,
            at_least: count.at_least(),
            at_most: count.at_most(),
            op: |_, _| (),
            init: || (),
        }
    }

    /// Returns a parser that succeeds if it is able to match its input `count` times, accumulating
    /// output into a `Vec` along the way.
    ///
    /// ```
    /// use parser_compose::Parser;
    ///
    /// let msg = "AAAA";
    /// let (value, rest) = "A".accumulate(2..=3).try_parse(msg).unwrap();
    ///
    /// assert_eq!(value, vec!["A", "A", "A"]);
    /// assert_eq!(rest, "A");
    /// ```
    fn accumulate<R>(
        self,
        count: R,
    ) -> Fold<Self, AccumulateOperation<Self::Out>, AccumulateInit<Self::Out>>
    where
        R: RepetitionArgument,
        Self: Sized,
    {
        Fold {
            parser: self,
            at_least: count.at_least(),
            at_most: count.at_most(),
            init: Vec::<Self::Out>::new,
            op: |mut accum: Vec<Self::Out>, res: Self::Out| {
                accum.push(res);
                accum
            },
        }
    }

    /// Returns a parser that outputs the slice of the input that was recognized.
    ///
    /// Works very well with the `.repeats()` combinator as an alternative to `.accumulate()` if you
    /// want to avoid allocating a `Vec`.
    ///
    /// Here is the same example from `.accumulate()`, this time using `.input()`:
    ///
    /// ```
    /// use parser_compose::Parser;
    ///
    /// let msg = "AAAA";
    /// let (value, rest) = "A".repeats(2..=3).input().try_parse(msg).unwrap();
    ///
    /// assert_eq!(value, "AAA");
    /// assert_eq!(rest, "A");
    /// ```
    fn input(self) -> Input<Self>
    where
        Self: Sized,
    {
        Input { inner: self }
    }

    /// Returns a parser always succeeds but wraps the output in an [`Option`]. If the original
    /// parser would have failed, the parser outputs a `Some(None)`.
    ///
    /// ```
    /// use parser_compose::Parser;
    ///
    /// let msg = "a";
    ///
    /// let ((b, a), _) = ("b".optional(), "a").try_parse(msg).unwrap();
    ///
    /// assert_eq!(b, None);
    /// assert_eq!(a, "a");
    /// ```
    fn optional(self) -> Optional<Self>
    where
        Self: Sized,
    {
        Optional { inner: self }
    }

    /// Returns a parser that never consumes any input regardless of its outcome. It can be used to
    /// look ahead.
    ///
    /// ```
    /// use parser_compose::Parser;
    ///
    /// // Recognize the sequence "a" followed by "b", but only if it is followed by a "c"
    /// let a_then_b = ("a", "b", "c".peek());
    ///
    /// let (value, rest) = a_then_b.try_parse("abc".into()).unwrap();
    /// // The peeked output is still returned, but is not consumed
    /// assert_eq!(value, ("a", "b", "c"));
    /// assert_eq!(rest, "c");
    ///
    /// let result = a_then_b.try_parse("abb");
    /// assert!(result.is_none());
    /// ```
    fn peek(self) -> Peek<Self>
    where
        Self: Sized,
    {
        Peek { inner: self }
    }

    /// Returns a parser that succeeds if it was not able to recognize its input and fails if it
    /// was able to. It never consumes any input
    ///
    /// ```
    /// use parser_compose::Parser;
    ///
    /// // This parser matches "foo", but only if it is not followed by  "bar"
    /// let parser = ("foo", "bar".not());
    ///
    /// let msg = "foobar";
    ///
    /// let result = parser.try_parse(msg);
    ///
    /// assert!(result.is_none());
    ///
    /// let (value, rest) = parser.try_parse("foobaz").unwrap();
    ///
    /// assert_eq!(value, ("foo", ()));
    /// assert_eq!(rest, "baz");
    /// ```
    fn not(self) -> Not<Self>
    where
        Self: Sized,
    {
        Not { inner: self }
    }

    /// Returns a parser that applies a falible function `f` to its output. The parser will return
    /// `None` if `f` fails.
    ///
    /// ```
    /// use parser_compose::{Parser};
    ///
    /// let msg = [98].as_slice();
    ///
    /// let (value, _) = [98].and_then(|b| {
    ///     // converting to utf8 can fail
    ///     std::str::from_utf8(b)
    /// }).try_parse(msg).unwrap();
    ///
    /// assert_eq!("b", value);
    /// ```
    fn and_then<F, U, E>(self, f: F) -> AndThen<Self, F>
    where
        Self: Sized,
        F: Fn(Self::Out) -> Result<U, E>,
        E: std::error::Error,
    {
        AndThen { inner: self, f }
    }
}

/// ## `Parser` implementation for functions
///
/// The [`Parser`](crate::Parser) trait is automatically implemented for any function with
/// the following signature:
///
/// `Fn(In) -> Option<(Out, In)>`
///
/// See the trait documentation for more info about the type parameters.
impl<In, Out, F> Parser<In> for F
where
    F: Fn(In) -> Option<(Out, In)>,
{
    type Out = Out;

    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        (self)(input)
    }
}

/// ## Parser implementation for slices
///
/// The [`Parser`](crate::Parser) trait is implemented for all slices, which means all `&[T]` will have the
/// `try_parse()` method. Calling it will try to do a prefix match of the input with the slice used
/// as the pattern.
///
/// ```
/// use parser_compose::Parser;
///
/// let msg = &['H', 'E', 'L', 'L', 'O'][..];
///
/// let (res, rest) = ['H', 'E'].as_slice().try_parse(msg).unwrap();
///
///
/// assert_eq!(res, &['H', 'E'][..]);
/// assert_eq!(rest, &['L', 'L', 'O'][..]);
/// ```
impl<'p, 'i, T> Parser<&'i [T]> for &'p [T]
where
    T: PartialEq + fmt::Debug,
{
    type Out = &'p [T];
    fn try_parse(&self, input: &'i [T]) -> Option<(Self::Out, &'i [T])> {
        if input.starts_with(self) {
            Some((*self, &input[self.len()..]))
        } else {
            None
        }
    }
}

/// ## Parser implementation for string slices
///
/// The [`Parser`](crate::Parser) trait is implemented for string slices, which means all `&str`s
/// will have the `try_parse()` method. Calling it will try to do a prefix match of the input with
/// the `&str` used as the pattern.
///
/// ```
/// use parser_compose::Parser;
///
/// let msg = "HELLO";
///
/// let (value, rest) = "HE".try_parse(msg).unwrap();
///
/// assert_eq!(value, "HE");
/// assert_eq!(rest, "LLO");
/// ```
impl<'input, 'pat> Parser<&'input str> for &'pat str {
    type Out = &'pat str;

    fn try_parse(&self, input: &'input str) -> Option<(Self::Out, &'input str)> {
        if let Some(rest) = input.strip_prefix(self) {
            return Some((self, rest));
        }
        None
    }
}

/// A parser that recognizes the first unicode scalar value at the start of a string slice.
///
/// A unicode scalar value is not always what you might consider a
/// "character". This function will output the first thing that rust considers a [`char`](char).
///
/// ```
/// use parser_compose::{Parser, first_utf8_scalar};
///
/// let msg = "👻Boo";
///
/// let (value, rest) = first_utf8_scalar(msg).unwrap();
///
/// assert_eq!(value, "👻");
/// ```
pub fn first_utf8_scalar(input: &str) -> Option<(&str, &str)> {
    let mut iter = input.char_indices();
    let Some((start_idx, _)) = iter.next() else {
        return None;
    };

    // If there was just one char in the &str, this `next()` call would return `None`.
    let (end, _) = iter.next().unwrap_or((input.len(), ' '));
    Some((&input[start_idx..end], &input[end..]))
}

/// Returns a parser that recognizes the first unicode scalar value in a string slice if its value
/// is in the specified range
///
/// The range must be bounded on both ends. Only inclusive ranges are allowed.
///
/// ```
/// use parser_compose::{Parser, utf8_scalar};
///
/// let msg = "a1";
///
/// let alphabetic = utf8_scalar(97..=122);
/// let (value, rest) = alphabetic.try_parse(msg).unwrap();
///
/// assert_eq!(value, "a");
/// assert_eq!(rest, "1");
///
/// let result = alphabetic.try_parse(rest);
/// assert!(result.is_none());
///
/// ```
pub fn utf8_scalar(range: RangeInclusive<u32>) -> Utf8Scalar {
    Utf8Scalar {
        start: *range.start(),
        end: *range.end(),
    }
}

/// Returns a parser that recognizes the first byte in a slice if its value is in the specified
/// range.
///
/// The range can be specified in two ways:
/// - An inclusive range (e.g. `0..=30`)
/// - A single u8 value (e.g. `8`)
///
/// ```
/// use parser_compose::{Parser, byte};
///
/// let msg = b"1a";
///
/// let digit = byte(0x30..=0x39);
/// let (value, rest) = digit.try_parse(msg).unwrap();
///
/// assert_eq!(value, [0x31]);
/// assert_eq!(rest, b"a");
///
/// let result = digit.try_parse(rest);
/// assert!(result.is_none());
/// ```
pub fn byte(range: impl ByteRange) -> Byte {
    Byte {
        start: range.start(),
        end: range.end(),
    }
}

/// A parser that recognizes the first item in a slice.
///
/// ```
/// use parser_compose::{Parser, first_slice_item};
///
/// let msg = &[254, 1, 2][..];
///
/// let (value, _) = first_slice_item(msg).unwrap();
///
/// assert_eq!(*value, [254]);
/// ```
pub fn first_slice_item<T>(input: &[T]) -> Option<(&[T], &[T])> {
    if input.is_empty() {
        None
    } else {
        Some((&input[0..1], &input[1..]))
    }
}

/// See [`utf8_scalar`](crate::parser::utf8_scalar)
#[derive(Copy, Clone)]
pub struct Utf8Scalar {
    start: u32,
    end: u32,
}

impl<'i> Parser<&'i str> for Utf8Scalar {
    type Out = &'i str;
    fn try_parse(&self, input: &'i str) -> Option<(Self::Out, &'i str)> {
        first_utf8_scalar
            .when(|s| {
                let char = s
                    .chars()
                    .next()
                    .expect("first_utf8_scalar should only yield one char")
                    as u32;
                char >= self.start && char <= self.end
            })
            .try_parse(input)
    }
}

/// See [`byte`](crate::parser::byte)
#[derive(Copy, Clone)]
pub struct Byte {
    start: u8,
    end: u8,
}

impl<'i> Parser<&'i [u8]> for Byte {
    type Out = &'i [u8];

    fn try_parse(&self, input: &'i [u8]) -> Option<(Self::Out, &'i [u8])> {
        first_slice_item
            .when(|s| s[0] >= self.start && s[0] <= self.end)
            .try_parse(input)
    }
}

/// Trait used to specify a range for the value of a byte
pub trait ByteRange {
    /// The inclusive lower bound
    fn start(&self) -> u8;
    /// The inclusive uppler bound
    fn end(&self) -> u8;
}

impl ByteRange for RangeInclusive<u8> {
    fn start(&self) -> u8 {
        *self.start()
    }

    fn end(&self) -> u8 {
        *self.end()
    }
}

impl ByteRange for u8 {
    fn start(&self) -> u8 {
        *self
    }
    fn end(&self) -> u8 {
        *self
    }
}

/// Trait used to specify how many times a parser should run.
///
/// The following types implement this trait:
///
/// - [`usize`] (e.g. `8`):  Run the parser 8 times.
/// - [`RangeFrom`] (e.g. `4..`) Run the parser at least 4 times (maybe more).
/// - [`RangeInclusive`] (e.g. `3..=7`) Run the parser at least 3 times,  but no more than 7 times.
/// - [`RangeToInclusive`] (e.g. `..=4`) Run the parser at most 4 times (maybe less, even 0).
pub trait RepetitionArgument: Clone {
    /// The minimum amount of times the _thing_ should be repeated
    fn at_least(&self) -> usize;
    /// The maximum aount of times the _thing_ should be repeated. If it is unbounded, this will
    /// return `None`
    fn at_most(&self) -> Option<usize>;
}

impl RepetitionArgument for RangeFrom<usize> {
    fn at_least(&self) -> usize {
        self.start
    }
    fn at_most(&self) -> Option<usize> {
        None
    }
}

impl RepetitionArgument for RangeInclusive<usize> {
    fn at_least(&self) -> usize {
        *self.start()
    }

    fn at_most(&self) -> Option<usize> {
        Some(*self.end())
    }
}

impl RepetitionArgument for RangeToInclusive<usize> {
    fn at_least(&self) -> usize {
        0
    }
    fn at_most(&self) -> Option<usize> {
        Some(self.end)
    }
}

impl RepetitionArgument for usize {
    fn at_least(&self) -> usize {
        *self
    }

    fn at_most(&self) -> Option<usize> {
        Some(*self)
    }
}

///  See [`fold()`](crate::Parser::fold)
#[derive(Clone, Copy)]
pub struct Fold<P, Operation, Init> {
    at_least: usize,
    at_most: Option<usize>,
    parser: P,
    op: Operation,
    init: Init,
}

impl<In, Out, P, Operation, Init, Accum> Parser<In> for Fold<P, Operation, Init>
where
    P: Parser<In, Out = Out>,
    Init: Fn() -> Accum,
    Operation: Fn(Accum, Out) -> Accum,
    In: Clone,
{
    type Out = Accum;

    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        let lower_bound = self.at_least;
        let upper_bound = self.at_most;

        // Do not proceed any further if the lower bound is greater than the upper bound
        // I consider this a programmer error and deem it non-recoverable.
        if let Some(u) = upper_bound {
            assert!(
                u >= lower_bound,
                "upper bound should be greater than or equal to the lower bound"
            );
        };

        // Given our current state (e.g. upper and lower bounds, how many loops we have dong so far
        // etc..), determines if we should continue looping or if we should break out.
        let check = |counter: usize, rest: In, accumulator: Accum, latest_attempt: Option<In>| {
            // What we do depends on the latest parsing result
            match latest_attempt {
                // If the last call to `try_parse` was successful...
                Some(n) => {
                    if let Some(u) = upper_bound {
                        // Break out of the loop if we have satisfied the lower bound and the current
                        // count is equal to the upper bound
                        if counter >= lower_bound && counter == u {
                            return ControlFlow::Break(Some((accumulator, n)));
                        }
                    }
                    ControlFlow::Continue(accumulator)
                }
                // If the latest attempt was a failure...
                None => {
                    if counter < lower_bound {
                        // and we have not yet hit the lower bound we need to break out
                        return ControlFlow::Break(None);
                    }

                    // otherwise, we consider it a success and break out with whatever we have
                    // accumulated so far.
                    ControlFlow::Break(Some((accumulator, rest)))
                }
            }
        };

        // Keeps track of how many successful parser executions we have had so far
        let mut counter = 0;

        // The input returned from the last successful parser execution
        let mut rest = input;

        // The result of the last parser execution, successful or not.
        let mut latest_attempt = Some(rest.clone());

        // The `init` call gives us the initial value of whatever it is we are accumulating into.
        let mut accumulator = (self.init)();

        loop {
            // Note that `accumulator` is opaque, we know nothing about it and make no requirements on
            // it implementing Clone/Copy.
            // So when we move it to `check`, we need to make sure we get it back.
            accumulator = match check(counter, rest.clone(), accumulator, latest_attempt) {
                ControlFlow::Break(outcome) => return outcome,
                ControlFlow::Continue(a) => a,
            };

            latest_attempt = match self.parser.try_parse(rest.clone()) {
                Some((o, r)) => {
                    counter += 1;
                    rest = r;
                    accumulator = (self.op)(accumulator, o);
                    Some(rest.clone())
                }
                None => None,
            };
        }
    }
}

/// See [`when()`](crate::Parser::when)
#[derive(Clone, Copy)]
pub struct Predicate<P, F> {
    parser: P,
    predicate: F,
}

impl<In, Out, P, F> Parser<In> for Predicate<P, F>
where
    P: Parser<In, Out = Out>,
    F: Fn(Out) -> bool,
    Out: Clone,
{
    type Out = Out;
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        match self.parser.try_parse(input) {
            Some((value, rest)) => match (self.predicate)(value.clone()) {
                true => Some((value, rest)),
                false => None,
            },
            None => None,
        }
    }
}

/// See [`optional()`](crate::Parser::optional)
#[derive(Clone, Copy)]
pub struct Optional<P> {
    inner: P,
}

impl<In, Out, P> Parser<In> for Optional<P>
where
    In: Clone,
    P: Parser<In, Out = Out>,
{
    type Out = Option<Out>;
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        match self.inner.try_parse(input.clone()) {
            Some((value, rest)) => Some((Some(value), rest)),
            None => Some((None, input)),
        }
    }
}

/// See [`peek()`](crate::Parser::peek)
#[derive(Clone, Copy)]
pub struct Peek<P> {
    inner: P,
}

impl<In, Out, P> Parser<In> for Peek<P>
where
    In: Clone,
    P: Parser<In, Out = Out>,
{
    type Out = Out;
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        self.inner.try_parse(input.clone()).map(|(p, _)| (p, input))
    }
}

/// See [`not()`](crate::Parser::not)
#[derive(Clone, Copy)]
pub struct Not<P> {
    inner: P,
}

impl<In, Out, P> Parser<In> for Not<P>
where
    In: Clone,
    P: Parser<In, Out = Out>,
{
    type Out = ();
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        match self.inner.try_parse(input.clone()) {
            Some(_) => None,
            None => Some(((), input)),
        }
    }
}

/// See [`and_then()`](crate::Parser::and_then)
#[derive(Clone, Copy)]
pub struct AndThen<P, F> {
    inner: P,
    f: F,
}

impl<In, Out, E, P, F, U> Parser<In> for AndThen<P, F>
where
    P: Parser<In, Out = Out>,
    F: Fn(P::Out) -> Result<U, E>,
    for<'a> E: std::error::Error + 'a,
{
    type Out = U;

    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        match self.inner.try_parse(input) {
            Some((value, rest)) => match (self.f)(value) {
                Ok(m) => Some((m, rest)),
                Err(_) => None,
            },
            None => None,
        }
    }
}

macro_rules! impl_tuple {
    ($($parser:ident : $parser_type:ident : $out:ident : $out_type:ident),+) => {
        /// A tuple of parsers is treated as a parser that tries its inner parsers in turn, feeding
        /// the leftover input from the first as the input to the other and so on
        ///
        /// Calling the `.try_parse()` on the tuple returns a new tuple containing the extracted values.
        ///
        /// This is implemented for tuples up to 12 items long
        impl<In $(, $parser_type, $out_type)+> Parser<In> for ($($parser_type,)+)
        where $($parser_type: $crate::Parser<In, Out=$out_type>,)+
        {
            type Out = ($($out_type,)+);

            #[allow(unused_assignments)]
            fn try_parse(&self, ctx: In) -> Option<(($($out_type,)+), In)> {
                let rest = ctx;
                let ( $( $parser, )+) = self;

                $(
                    let ($out, rest) = match $parser.try_parse(rest) {
                        Some(v) => v,
                        None => return None,
                    };
                ) *

                Some((($($out, )+) , rest))
            }
        }
    }
}

// Ah, good 'ole macros.
//
// The purpose of the `impl_tuple` macro is to generate the following impl for a tuple whose length
// is the number of arguments to the macro.
// `impl Parser<...> for (T1, ) where T1: Parser<..> { ... }`
//
// So this call: `impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1);` generates the Parser impl for tuples of
// length 2.
// This call to `impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2);`  generates the impl for
// tuples of length 3, and so on.
//
// Each argument to the macro is a colon delimited keyword that will be used as is in the
// implementation to refer to the type/name of the parser or its output at that tuple location
impl_tuple!(p0:P0:o0:O0);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5, p6:P6:o6:O6);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5, p6:P6:o6:O6, p7:P7:o7:O7);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5, p6:P6:o6:O6, p7:P7:o7:O7, p8:P8:o8:O8);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5, p6:P6:o6:O6, p7:P7:o7:O7, p8:P8:o8:O8, p9:P9:o9:O9);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5, p6:P6:o6:O6, p7:P7:o7:O7, p8:P8:o8:O8, p9:P9:o9:O9, p10:P10:o10:O10);
impl_tuple!(p0:P0:o0:O0, p1:P1:o1:O1, p2:P2:o2:O2, p3:P3:o3:O3, p4:P4:o4:O4, p5:P5:o5:O5, p6:P6:o6:O6, p7:P7:o7:O7, p8:P8:o8:O8, p9:P9:o9:O9, p10:P10:o10:O10, p11:P11:o11:O11);

/// See [`or()`](crate::Parser::or)
#[derive(Clone, Copy)]
pub struct Or<P1, P2> {
    parser1: P1,
    parser2: P2,
}

impl<In, Out, P1, P2> Parser<In> for Or<P1, P2>
where
    P1: Parser<In, Out = Out>,
    P2: Parser<In, Out = Out>,
    In: Clone,
{
    type Out = Out;
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        match self.parser1.try_parse(input.clone()) {
            Some((value, rest)) => Some((value, rest)),
            None => self.parser2.try_parse(input),
        }
    }
}

/// See [`map()`](crate::Parser::map).
#[derive(Clone, Copy)]
pub struct Map<P, F> {
    parser: P,
    f: F,
}

impl<In, Out, P, F, M> Parser<In> for Map<P, F>
where
    P: Parser<In, Out = Out>,
    F: Fn(P::Out) -> M,
{
    type Out = M;
    fn try_parse(&self, input: In) -> Option<(Self::Out, In)> {
        self.parser
            .try_parse(input)
            .map(|(v, rest)| ((self.f)(v), rest))
    }
}

#[derive(Clone, Copy)]
pub struct Input<P> {
    inner: P,
}

impl<'a, P, Out> Parser<&'a str> for Input<P>
where
    P: Parser<&'a str, Out = Out>,
{
    type Out = &'a str;

    fn try_parse(&self, input: &'a str) -> Option<(Self::Out, &'a str)> {
        match self.inner.try_parse(input) {
            Some((_, rest)) => {
                let consumed = input.strip_suffix(rest).unwrap();
                Some((consumed, rest))
            }
            None => None,
        }
    }
}

impl<'a, P, T, Out> Parser<&'a [T]> for Input<P>
where
    P: Parser<&'a [T], Out = Out>,
    T: PartialEq,
{
    type Out = &'a [T];

    fn try_parse(&self, input: &'a [T]) -> Option<(Self::Out, &'a [T])> {
        match self.inner.try_parse(input) {
            Some((_, rest)) => {
                let consumed = input.strip_suffix(rest).unwrap();
                Some((consumed, rest))
            }
            None => None,
        }
    }
}

#[cfg(test)]
mod test {
    use crate::{first_slice_item, Parser};

    #[derive(PartialEq, Eq, Debug)]
    enum Token {
        A,
        B,
        C,
        D,
        E,
    }

    #[test]
    fn combinators_can_be_used_with_arbitrary_structs() {
        let msg = vec![Token::A, Token::B, Token::C, Token::D, Token::E];

        let (value, rest) = first_slice_item.repeats(2).input().try_parse(&msg).unwrap();

        assert_eq!(value, &[Token::A, Token::B]);
        assert_eq!(rest, &[Token::C, Token::D, Token::E]);
    }
}
#[cfg(test)]
mod test_map_combinator {
    use crate::Parser;

    #[test]
    fn test_map() {
        let msg = "ABCABC";
        let (value, rest) = ("A", "B", "C").map(|s| s.0).try_parse(msg).unwrap();

        assert_eq!(value, "A");
        assert_eq!(rest, "ABC");
    }
}

#[cfg(test)]
mod test_or_combinator {
    use crate::Parser;

    #[test]
    fn it_works() {
        let msg = "GET";

        let result = "POST".or("PUT").try_parse(msg.into());
        assert!(result.is_none());

        let (value, _) = "GET".or("POST").try_parse(msg.into()).unwrap();
        assert_eq!(value, "GET");

        // The first match is reported
        let (value, _) = "G".or("GE").or("GET").try_parse(msg.into()).unwrap();
        assert_eq!(value, "G");
    }
}

#[cfg(test)]
mod test_when_combinator {
    use crate::Parser;

    #[test]
    fn it_works() {
        let msg = "GET";
        let pass = false;

        let result = "GET".when(|_| pass).try_parse(msg.into());
        assert!(result.is_none());

        let pass = true;
        let (value, _) = "GET".when(|_| pass).try_parse(msg.into()).unwrap();
        assert_eq!(value, "GET");
    }
}

#[cfg(test)]
mod test_tuple_combinator {
    use crate::{utf8_scalar, Parser};

    #[test]
    fn it_works() {
        let msg = "GET https://example.org HTTP/1.1";

        let method_parser = "GET".or("POST").or("PUT");

        let scheme_parser = "http://".or("https://");

        let authority_parser = "example.org";

        let version_parser = "HTTP/1.0".or("HTTP/1.1");

        let whitespace = utf8_scalar(0x20..=0x20);

        let (method, _, scheme, authority, _, version) = (
            method_parser,
            whitespace,
            scheme_parser,
            authority_parser,
            whitespace,
            version_parser,
        )
            .try_parse(msg.into())
            .unwrap()
            .0;

        assert_eq!(method, "GET");
        assert_eq!(scheme, "https://");
        assert_eq!(authority, "example.org");
        assert_eq!(version, "HTTP/1.1");
    }
}

#[cfg(test)]
mod test_repeated_combinator {
    use crate::Parser;

    #[test]
    fn test_single_value_count() {
        let msg = "AAA";

        let (value, rest) = "A".accumulate(2).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A", "A"]);
        assert_eq!(rest, "A");

        let result = "A".accumulate(4).try_parse(msg.into());
        assert!(result.is_none());

        let (value, rest) = "A".accumulate(0).try_parse(msg.into()).unwrap();
        assert!(value.is_empty());
        assert_eq!(rest, "AAA");
    }

    #[test]
    fn test_bounded_both_sides() {
        let msg = "AAAABB";

        let (value, rest) = "A".accumulate(0..=0).try_parse(msg.into()).unwrap();
        assert!(value.is_empty());
        assert_eq!(rest, msg);

        let (value, rest) = "A".accumulate(1..=1).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A"]);
        assert_eq!(rest, "AAABB");

        let (value, rest) = "A".accumulate(1..=3).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A", "A", "A"]);
        assert_eq!(rest, "ABB");

        let (value, rest) = "A".accumulate(1..=10).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A", "A", "A", "A"]);
        assert_eq!(rest, "BB");
    }

    #[test]
    #[should_panic]
    fn test_bounded_both_sides_panics_if_lower_is_greater_than_upper() {
        let msg = "AAAABB";
        let _ = "A".accumulate(1..=0).try_parse(msg.into());
    }

    #[test]
    fn test_lower_bound() {
        let msg = "AAAB";

        let result = "A".accumulate(4..).try_parse(msg.into());
        assert!(result.is_none());

        let (value, rest) = "A".accumulate(1..).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A", "A", "A"]);
        assert_eq!(rest, "B");
    }

    #[test]
    fn test_upper_bound() {
        let msg = "BB";

        let (value, rest) = "A".accumulate(..=3).try_parse(msg.into()).unwrap();
        assert!(value.is_empty());
        assert_eq!(rest, "BB");

        let msg = "AAB";
        let (value, rest) = "A".accumulate(..=0).try_parse(msg.into()).unwrap();
        assert!(value.is_empty());
        assert_eq!(rest, "AAB");

        let (value, rest) = "A".accumulate(..=1).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A"]);
        assert_eq!(rest, "AB");

        let (value, rest) = "A".accumulate(..=10).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec!["A", "A"]);
        assert_eq!(rest, "B");
    }

    #[test]
    fn always_succeeds_with_zero_lower_bound() {
        let msg = "GG";

        let (value, rest) = "A".accumulate(0..).try_parse(msg.into()).unwrap();
        assert_eq!(value, vec![] as Vec<&str>);
        assert_eq!(rest, "GG");
    }
}

#[cfg(test)]
mod test_fold_combinator {
    use crate::Parser;

    #[test]
    fn operation_is_not_run_if_parser_fails() {
        let msg = "EE";

        let (value, rest) = "A"
            .fold(0.., |a, _| a + 1, || 0u8)
            .try_parse(msg.into())
            .unwrap();

        assert_eq!(value, 0);
        assert_eq!(rest, "EE");
    }

    #[test]
    fn operation_is_run_on_each_repetition() {
        let msg = "AAAA";

        let (value, rest) = "A"
            .fold(2..=3, |a, _| a + 1, || 0u8)
            .try_parse(msg.into())
            .unwrap();
        assert_eq!(3, value);
        assert_eq!(rest, "A");
    }
}

#[cfg(test)]
mod test_peeked_combinator {
    use crate::Parser;

    #[test]
    fn test_peeked_does_not_consume_input_on_success() {
        let method = "GET".or("POST");
        let host = "example.com".or("example.org");

        let msg = "GET/example.org";

        let ((method, peeked), rest) = (method, ("/", host).peek()).try_parse(msg.into()).unwrap();

        assert_eq!(method, "GET");
        assert_eq!(peeked, ("/", "example.org"));
        assert_eq!(rest, "/example.org");
    }

    #[test]
    fn test_not() {
        // This parser matches a single "a", but only if it is not part of an arbitrary long
        // sequence of "a"'s followed by a "b".
        // I got this from the wikipedia page on parsing expression grammars
        let tricky = (("a".accumulate(1..), "b").not(), "a");

        let fail = "aaaba";
        let pass = "aaaa";

        let result = tricky.try_parse(fail.into());
        assert!(result.is_none());

        let (value, rest) = tricky.try_parse(pass.into()).unwrap();

        assert_eq!(value, ((), "a"));
        assert_eq!(rest, "aaa");
    }
}

#[cfg(test)]
mod test_input_combinator {
    use crate::{utf8_scalar, Parser};
    use std::str::FromStr;

    #[test]
    fn test_input() {
        let digit = utf8_scalar(0x30..=0x39).and_then(u8::from_str);
        let msg = "1234.4";
        let decimal = (digit.repeats(1..), ".", digit.repeats(1..)).input();

        let (value, rest) = decimal.try_parse(msg.into()).unwrap();
        assert_eq!(value, "1234.4");
        assert_eq!(rest, "");
    }

    #[test]
    fn test_input_with_peek() {
        let msg = "ABC";
        let (value, rest) = "ABC".peek().input().try_parse(msg.into()).unwrap();

        assert_eq!(value, "");
        assert_eq!(rest, "ABC");
    }
}

#[cfg(test)]
mod test_parsers {
    use crate::{first_utf8_scalar, utf8_scalar, Parser};
    #[test]
    fn empty_str() {
        let msg = "H";
        let (value, rest) = "".try_parse(msg.into()).unwrap();
        assert_eq!(value, "");
        assert_eq!(rest, msg);
    }

    #[test]
    fn test_first_utf8_scalar() {
        let msg = "🏠";
        let (value, rest) = first_utf8_scalar.try_parse(msg.into()).unwrap();

        assert_eq!(value, "🏠");
        assert_eq!(rest, "");
    }

    #[test]
    fn test_utf8_scalar() {
        let msg = "abc";
        let (value, rest) = utf8_scalar(97..=97).try_parse(msg.into()).unwrap();
        assert_eq!(value, "a");
        let result = utf8_scalar(97..=97).try_parse(rest);
        assert!(result.is_none());

        let msg = "🤣Hello";

        let (value, _) = utf8_scalar('\u{1f923}' as u32..='\u{1f923}' as u32)
            .try_parse(msg.into())
            .unwrap();
        assert_eq!(value, "🤣");
    }

    #[test]
    fn huh() {
        fn parse_quoted_string(input: &[u8]) -> Option<(&[u8], &[u8])> {
            use crate::byte;

            let htab: &[u8] = b"\t";
            let sp: &[u8] = b" ";
            let exc: &[u8] = b"!";
            let dquote: &[u8] = b"\"";
            let backslash: &[u8] = b"\\";
            let obs_text = byte(0x80..=0xFF);
            let vchar = byte(0x21..=0x7E);

            let qdtext = htab
                .or(sp)
                .or(exc)
                .or(byte(0x23..=0x5B))
                .or(byte(0x5D..=0x7E))
                .or(obs_text)
                .input();

            let quoted_pair = (backslash, htab.or(sp).or(vchar).or(obs_text)).input();

            (dquote, qdtext.or(quoted_pair).repeats(0..).input(), dquote)
                .map(|(_, r, _)| r)
                .try_parse(input)
        }

        let quoted_string = br##""a\"value\"""##;
        let not_quoted_string = br##"a value"##;

        assert_eq!(
            br##"a\"value\""##,
            parse_quoted_string(quoted_string).unwrap().0,
        );
    }
}

#[doc = include_str!("../README.md")]
#[cfg(doctest)]
pub struct ReadmeDocTests {}