//! Sequential parser composition and the `seq!` macro.
//!
//! This module provides the [`Sequence`] combinator for chaining parsers together
//! in order, along with the [`seq!`](crate::seq) macro for convenient composition syntax.
//!
//! The implementation uses a Lisp-style right-associative nesting pattern where
//! `seq![A, B, C]` expands to `Sequence<A, Sequence<B, Sequence<C, ()>>>`.
//! This creates nested tuple outputs following the same pattern.
//!
//! Sequential composition is fundamental to building structured parsers that
//! match multiple elements in a specific order.

use crate::{
    cache::ParsingCache,
    parser::{Parsable, Parser, Source},
    result::ParseResult,
};

/// Create a sequence parser from multiple parsers.
///
/// This macro creates a Lisp-style nested list structure from the
/// provided parsers. The resulting type follows the pattern:
/// `Sequence<A, Sequence<B, Sequence<C, ()>>>` for `seq![A, B, C]`.
///
/// # Examples
///
/// ```rust
/// use neotoma::{seq, literal::Literal, parser::{parse, Source}};
/// use std::io::Cursor;
///
/// // Create a sequence of three literal parsers
/// let greeting = seq![
///     Literal::from_str("hello"),
///     Literal::from_str(" "),
///     Literal::from_str("world")
/// ];
///
/// let mut input = Cursor::new(b"hello world");
/// let mut source = Source::new(input);
/// let result = parse(greeting, &mut source).unwrap();
/// assert_eq!(result.0, b"hello".as_slice().into());
/// assert_eq!(result.1.0, b" ".as_slice().into());
/// assert_eq!(result.1.1.0, b"world".as_slice().into());
/// assert_eq!(result.1.1.1, ());
/// ```
///
/// The macro supports sequences of any length:
///
/// ```rust
/// use neotoma::{seq, literal::Literal};
///
/// // Two parsers
/// let two = seq![Literal::from_str("a"), Literal::from_str("b")];
///
/// // Five parsers
/// let five = seq![
///     Literal::from_str("a"),
///     Literal::from_str("b"),
///     Literal::from_str("c"),
///     Literal::from_str("d"),
///     Literal::from_str("e")
/// ];
/// ```
#[macro_export]
macro_rules! seq {
    // Base case: single parser becomes Sequence<P, ()>
    ($parser:expr) => {
        $crate::sequence::Sequence::new($parser, ())
    };

    // Recursive case: first parser + sequence of rest
    ($first:expr, $($rest:expr),+ $(,)?) => {
        $crate::sequence::Sequence::new($first, seq!($($rest),+))
    };
}

/// A parser combinator that matches two parsers in sequence.
///
/// Sequence applies the first parser, and if it succeeds, applies the second parser.
/// The output is a tuple `(A::Output, B::Output)` containing both results.
/// If either parser fails, the entire sequence fails.
///
/// # Examples
///
/// ```rust
/// use neotoma::{sequence::Sequence, literal::Literal, parser::{parse, Source}};
/// use std::io::Cursor;
///
/// // Match "hello" followed by "world"
/// let greeting = Sequence::new(
///     Literal::from_str("hello"),
///     Literal::from_str("world")
/// );
///
/// let mut input = Cursor::new(b"helloworld");
/// let mut source = Source::new(input);
/// let result = parse(greeting, &mut source).unwrap();
/// assert_eq!(result.0, b"hello".as_slice().into());
/// assert_eq!(result.1, b"world".as_slice().into());
/// ```
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Sequence<A, B> {
    first: A,
    second: B,
}

/// Trait for types that can have a parser pushed to their end.
pub trait Push<P> {
    type Output;
    fn push(self, parser: P) -> Self::Output;
}

impl<A, B> Sequence<A, B> {
    /// Create a new Sequence parser that matches the first parser followed by the second.
    ///
    /// Both parsers must succeed for the sequence to succeed. The output is a tuple
    /// containing both results.
    ///
    /// For sequences of more than two parsers, consider using the `seq!` macro instead.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use neotoma::{sequence::Sequence, literal::Literal, parser::{parse, Source}};
    /// use std::io::Cursor;
    ///
    /// let greeting = Sequence::new(
    ///     Literal::from_str("hello"),
    ///     Literal::from_str(" world")
    /// );
    ///
    /// let mut input = Cursor::new(b"hello world");
    /// let mut source = Source::new(input);
    /// let result = parse(greeting, &mut source).unwrap();
    /// assert_eq!(result.0, b"hello".as_slice().into());
    /// assert_eq!(result.1, b" world".as_slice().into());
    /// ```
    pub fn new(first: A, second: B) -> Self {
        Self { first, second }
    }
}

impl<A, B> Sequence<A, B> {
    /// Push a new parser to the end of this sequence.
    ///
    /// This extends the sequence by appending a new parser to the end of the
    /// right-associative nesting structure.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use neotoma::{seq, sequence::Push, literal::Literal, parser::{parse, Source}};
    /// use std::io::Cursor;
    ///
    /// let base = seq![Literal::from_str("hello"), Literal::from_str(" ")];
    /// let extended = base.push(Literal::from_str("world"));
    ///
    /// let mut input = Cursor::new(b"hello world");
    /// let mut source = Source::new(input);
    /// let result = parse(extended, &mut source).unwrap();
    /// assert_eq!(result.0, b"hello".as_slice().into());
    /// assert_eq!(result.1.0, b" ".as_slice().into());
    /// assert_eq!(result.1.1.0, b"world".as_slice().into());
    /// assert_eq!(result.1.1.1, ());
    /// ```
    pub fn push<P>(self, parser: P) -> Sequence<A, B::Output>
    where
        B: Push<P>,
    {
        Sequence::new(self.first, self.second.push(parser))
    }
}

// Base case: () can be pushed to, becoming Sequence<P, ()>
impl<P> Push<P> for () {
    type Output = Sequence<P, ()>;

    fn push(self, parser: P) -> Self::Output {
        Sequence::new(parser, ())
    }
}

// Recursive case: Sequence<A, B> can be pushed to if B can be pushed to
impl<A, B, P> Push<P> for Sequence<A, B>
where
    B: Push<P>,
{
    type Output = Sequence<A, B::Output>;

    fn push(self, parser: P) -> Self::Output {
        Sequence::new(self.first, self.second.push(parser))
    }
}

impl<A, B, Ctx> Parser<Ctx> for Sequence<A, B>
where
    A: Parser<Ctx>,
    B: Parser<Ctx>,
{
    type Output = (A::Output, B::Output);

    fn id(&self) -> u64 {
        use std::any::TypeId;
        use std::hash::{DefaultHasher, Hash, Hasher};

        let mut hasher = DefaultHasher::new();
        TypeId::of::<Self>().hash(&mut hasher);
        self.first.id().hash(&mut hasher);
        self.second.id().hash(&mut hasher);
        hasher.finish()
    }

    fn read<S>(
        &self,
        source: &mut Source<S>,
        cache: &mut impl ParsingCache,
        context: &mut Ctx,
    ) -> ParseResult<Self::Output>
    where
        S: Parsable,
    {
        let first_result = self.first.parse(source, cache, context)?;
        let second_result = self.second.parse(source, cache, context)?;
        Ok((first_result, second_result))
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{literal::Literal, parser::parse, seq};
    use std::io::Cursor;

    #[test]
    fn test_sequence_both_match() {
        let parser = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));

        let mut input = Cursor::new(b"helloworld");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1, b"world".as_slice().into());
    }

    #[test]
    fn test_sequence_first_fails() {
        let parser = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));

        let mut input = Cursor::new(b"goodbye");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source);
        assert!(result.is_err());
    }

    #[test]
    fn test_sequence_second_fails() {
        let parser = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));

        let mut input = Cursor::new(b"hellogoodbye");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source);
        assert!(result.is_err());
    }

    #[test]
    fn test_sequence_empty_input() {
        let parser = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));

        let mut input = Cursor::new(b"");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source);
        assert!(result.is_err());
    }

    #[test]
    fn test_seq_macro_single() {
        let parser = seq![Literal::from_str("hello")];

        let mut input = Cursor::new(b"hello");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
    }

    #[test]
    fn test_seq_macro_two() {
        let parser = seq![Literal::from_str("hello"), Literal::from_str("world")];

        let mut input = Cursor::new(b"helloworld");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b"world".as_slice().into());
    }

    #[test]
    fn test_seq_macro_three() {
        let parser = seq![
            Literal::from_str("hello"),
            Literal::from_str(" "),
            Literal::from_str("world")
        ];

        let mut input = Cursor::new(b"hello world");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b" ".as_slice().into());
        assert_eq!(result.1.1.0, b"world".as_slice().into());
    }

    #[test]
    fn test_seq_macro_four() {
        let parser = seq![
            Literal::from_str("hello"),
            Literal::from_str(" "),
            Literal::from_str("beautiful"),
            Literal::from_str(" world")
        ];

        let mut input = Cursor::new(b"hello beautiful world");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b" ".as_slice().into());
        assert_eq!(result.1.1.0, b"beautiful".as_slice().into());
        assert_eq!(result.1.1.1.0, b" world".as_slice().into());
    }

    #[test]
    fn test_seq_macro_five() {
        let parser = seq![
            Literal::from_str("a"),
            Literal::from_str("b"),
            Literal::from_str("c"),
            Literal::from_str("d"),
            Literal::from_str("e")
        ];

        let mut input = Cursor::new(b"abcde");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"a".as_slice().into());
        assert_eq!(result.1.0, b"b".as_slice().into());
        assert_eq!(result.1.1.0, b"c".as_slice().into());
        assert_eq!(result.1.1.1.0, b"d".as_slice().into());
        assert_eq!(result.1.1.1.1.0, b"e".as_slice().into());
    }

    #[test]
    fn test_seq_macro_with_trailing_comma() {
        let parser = seq![
            Literal::from_str("hello"),
            Literal::from_str(" "),
            Literal::from_str("world"),
        ];

        let mut input = Cursor::new(b"hello world");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b" ".as_slice().into());
        assert_eq!(result.1.1.0, b"world".as_slice().into());
    }

    #[test]
    fn test_sequence_different_types() {
        use crate::class::Class;

        let parser = Sequence::new(Literal::from_str("prefix"), Class::digits());

        let mut input = Cursor::new(b"prefix123");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"prefix".as_slice().into());
        assert_eq!(result.1, b"123".to_vec());
    }

    #[test]
    fn test_seq_macro_different_types() {
        use crate::class::Class;

        let parser = seq![
            Literal::from_str("prefix"),
            Class::digits(),
            Literal::from_str("suffix")
        ];

        let mut input = Cursor::new(b"prefix123suffix");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"prefix".as_slice().into());
        assert_eq!(result.1.0, b"123".to_vec());
        assert_eq!(result.1.1.0, b"suffix".as_slice().into());
    }

    #[test]
    fn test_sequence_position_tracking() {
        let parser = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));

        let mut input = Cursor::new(b"helloworld123");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1, b"world".as_slice().into());

        // Position should be advanced past both parsers - test indirectly
        // by verifying we can read the remaining bytes
        let remaining = source.peek1().unwrap();
        assert_eq!(remaining, b'1');
    }

    #[test]
    fn test_seq_macro_failure() {
        let parser = seq![
            Literal::from_str("hello"),
            Literal::from_str(" "),
            Literal::from_str("world")
        ];

        let mut input = Cursor::new(b"hello goodbye");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source);
        assert!(result.is_err());
    }

    #[test]
    fn test_push_to_single_element() {
        let base = seq![Literal::from_str("hello")];
        let extended = base.push(Literal::from_str(" world"));

        let mut input = Cursor::new(b"hello world");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(extended, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b" world".as_slice().into());
    }

    #[test]
    fn test_push_to_two_elements() {
        let base = seq![Literal::from_str("hello"), Literal::from_str(" ")];
        let extended = base.push(Literal::from_str("world"));

        let mut input = Cursor::new(b"hello world");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(extended, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b" ".as_slice().into());
        assert_eq!(result.1.1.0, b"world".as_slice().into());
    }

    #[test]
    fn test_push_to_three_elements() {
        let base = seq![
            Literal::from_str("hello"),
            Literal::from_str(" "),
            Literal::from_str("beautiful")
        ];
        let extended = base.push(Literal::from_str(" world"));

        let mut input = Cursor::new(b"hello beautiful world");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(extended, &mut source).unwrap();
        assert_eq!(result.0, b"hello".as_slice().into());
        assert_eq!(result.1.0, b" ".as_slice().into());
        assert_eq!(result.1.1.0, b"beautiful".as_slice().into());
        assert_eq!(result.1.1.1.0, b" world".as_slice().into());
    }

    #[test]
    fn test_push_multiple_times() {
        let base = seq![Literal::from_str("a")];
        let step1 = base.push(Literal::from_str("b"));
        let step2 = step1.push(Literal::from_str("c"));
        let final_parser = step2.push(Literal::from_str("d"));

        let mut input = Cursor::new(b"abcd");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(final_parser, &mut source).unwrap();
        assert_eq!(result.0, b"a".as_slice().into());
        assert_eq!(result.1.0, b"b".as_slice().into());
        assert_eq!(result.1.1.0, b"c".as_slice().into());
        assert_eq!(result.1.1.1.0, b"d".as_slice().into());
    }

    #[test]
    fn test_push_chaining() {
        let parser = seq![Literal::from_str("a")]
            .push(Literal::from_str("b"))
            .push(Literal::from_str("c"))
            .push(Literal::from_str("d"));

        let mut input = Cursor::new(b"abcd");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"a".as_slice().into());
        assert_eq!(result.1.0, b"b".as_slice().into());
        assert_eq!(result.1.1.0, b"c".as_slice().into());
        assert_eq!(result.1.1.1.0, b"d".as_slice().into());
    }

    #[test]
    fn test_push_different_types() {
        use crate::class::Class;

        let base = seq![Literal::from_str("prefix")];
        let extended = base.push(Class::digits());

        let mut input = Cursor::new(b"prefix123");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(extended, &mut source).unwrap();
        assert_eq!(result.0, b"prefix".as_slice().into());
        assert_eq!(result.1.0, b"123".to_vec());
    }

    #[test]
    fn test_push_mixed_types_chain() {
        use crate::class::Class;

        let parser = seq![Literal::from_str("start")]
            .push(Class::digits())
            .push(Literal::from_str("_"))
            .push(Class::digits()) // Use digits instead of alpha for simplicity
            .push(Literal::from_str("end"));

        let mut input = Cursor::new(b"start123_456end");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"start".as_slice().into());
        assert_eq!(result.1.0, b"123".to_vec());
        assert_eq!(result.1.1.0, b"_".as_slice().into());
        assert_eq!(result.1.1.1.0, b"456".to_vec());
        assert_eq!(result.1.1.1.1.0, b"end".as_slice().into());
    }

    #[test]
    fn test_push_failure() {
        let base = seq![Literal::from_str("hello")];
        let extended = base.push(Literal::from_str(" world"));

        let mut input = Cursor::new(b"hello goodbye");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(extended, &mut source);
        assert!(result.is_err());
    }

    #[test]
    fn test_push_with_class_alpha() {
        use crate::class::Class;

        // Important: Class::alpha() consumes ALL consecutive alphabetic chars greedily
        // So we need a non-alphabetic separator to stop it from consuming everything
        let parser = seq![Literal::from_str("start")]
            .push(Class::digits())
            .push(Literal::from_str("_"))
            .push(Class::alpha())
            .push(Literal::from_str("_end"));

        let mut input = Cursor::new(b"start123_abc_end");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"start".as_slice().into());
        assert_eq!(result.1.0, b"123".to_vec());
        assert_eq!(result.1.1.0, b"_".as_slice().into());
        assert_eq!(result.1.1.1.0, b"abc".to_vec());
        assert_eq!(result.1.1.1.1.0, b"_end".as_slice().into());
    }

    #[test]
    fn test_push_with_until_parser() {
        use crate::{class::Class, until::Until};

        // Better solution using Until parser - no need for workarounds!
        let parser = seq![Literal::from_str("start")]
            .push(Class::digits())
            .push(Literal::from_str("_"))
            .push(Until::new(Literal::from_str("end")))
            .push(Literal::from_str("end"));

        let mut input = Cursor::new(b"start123_abcend");
        let mut source = crate::parser::Source::new(&mut input);

        let result = parse(parser, &mut source).unwrap();
        assert_eq!(result.0, b"start".as_slice().into());
        assert_eq!(result.1.0, b"123".to_vec());
        assert_eq!(result.1.1.0, b"_".as_slice().into());
        assert_eq!(result.1.1.1.0, b"abc".to_vec()); // Until stops at "end"
        assert_eq!(result.1.1.1.1.0, b"end".as_slice().into());
    }

    #[test]
    fn test_id_implementation_different_sequences() {
        // This test checks that Sequence implements proper id() method
        // Sequences with different parameters should have different IDs to avoid cache conflicts

        let seq1 = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));
        let seq2 = Sequence::new(Literal::from_str("foo"), Literal::from_str("bar"));

        // These sequences have different content and should have different IDs
        // This test will FAIL if Sequence uses default id() implementation
        let id1 = <Sequence<_, _> as crate::parser::Parser<()>>::id(&seq1);
        let id2 = <Sequence<_, _> as crate::parser::Parser<()>>::id(&seq2);

        assert_ne!(
            id1, id2,
            "Different Sequence instances should have different IDs to avoid cache collisions"
        );
    }

    #[test]
    fn test_id_implementation_same_sequences() {
        // Test that identical sequences have the same ID
        let seq1 = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));
        let seq2 = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));

        assert_eq!(
            <Sequence<_, _> as crate::parser::Parser<()>>::id(&seq1),
            <Sequence<_, _> as crate::parser::Parser<()>>::id(&seq2),
            "Identical Sequence instances should have the same ID for cache efficiency"
        );
    }

    #[test]
    fn test_id_implementation_sequence_cache_correctness() {
        // This test verifies that cache works correctly without collisions
        // when Sequence implements proper id() method

        let seq1 = Sequence::new(Literal::from_str("hello"), Literal::from_str("world"));
        let seq2 = Sequence::new(Literal::from_str("foo"), Literal::from_str("bar"));

        // Parse with first sequence
        let mut input1 = Cursor::new(b"helloworld");
        let mut source1 = crate::parser::Source::new(&mut input1);

        let result1 = parse(seq1, &mut source1);
        assert!(result1.is_ok(), "First parse should succeed");

        // Parse with second sequence at same position (0)
        // This should work correctly without cache collision
        let mut input2 = Cursor::new(b"foobar");
        let mut source2 = crate::parser::Source::new(&mut input2);

        let result2 = parse(seq2, &mut source2);
        assert!(
            result2.is_ok(),
            "Second parse should succeed without cache collision"
        );

        // Verify results are correct (no cache collision occurred)
        if let (Ok((first1, second1)), Ok((first2, second2))) = (result1, result2) {
            assert_eq!(first1, b"hello".as_slice().into());
            assert_eq!(second1, b"world".as_slice().into());
            assert_eq!(first2, b"foo".as_slice().into());
            assert_eq!(second2, b"bar".as_slice().into());
        } else {
            panic!("Both parses should succeed");
        }
    }

    #[test]
    fn test_id_implementation_nested_sequences() {
        // Test nested sequences have proper ID differentiation
        let seq1 = Sequence::new(
            Literal::from_str("outer1"),
            Sequence::new(Literal::from_str("inner1"), Literal::from_str("end1")),
        );

        let seq2 = Sequence::new(
            Literal::from_str("outer2"),
            Sequence::new(Literal::from_str("inner2"), Literal::from_str("end2")),
        );

        // Nested sequences should have different IDs
        // This test will FAIL if nested sequences use default id() implementation
        let id1 = <Sequence<_, _> as crate::parser::Parser<()>>::id(&seq1);
        let id2 = <Sequence<_, _> as crate::parser::Parser<()>>::id(&seq2);

        assert_ne!(
            id1, id2,
            "Different nested Sequence instances should have different IDs to avoid cache collisions"
        );
    }
}