recursive.rs raw

//! Self-referential parser support through deferred construction.
//!
//! This module provides the [`Recursive`] wrapper that solves the circular
//! dependency problem when building parsers that need to reference themselves
//! directly or indirectly. Instead of constructing the parser immediately,
//! it defers construction using a closure and caches the result.
//!
//! Recursive parsers are essential for parsing nested structures like
//! arithmetic expressions, JSON objects, or any grammar with recursive
//! production rules.

use std::cell::OnceCell;

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

/// A wrapper that enables self-referential parsers by deferring construction.
///
/// This solves the circular dependency problem where a parser needs to contain
/// itself (directly or indirectly). Instead of creating the parser during
/// construction, `Recursive<P>` creates it lazily on first use and caches it.
///
/// # The Problem
///
/// Self-referential parsers are common in language grammars but cause compilation issues:
///
/// ```compile_fail
/// // This won't compile - infinite type size!
/// struct Expression {
///     parenthesized: Expression,  // ERROR: recursive without indirection
/// }
/// ```
///
/// # The Solution  
///
/// `Recursive<P>` breaks the cycle during construction while enabling unlimited recursion at parse time:
///
/// ```rust
/// use std::io::Cursor;
/// use neotoma::{
///     recursive::Recursive,
///     parser::{Parser, Source, parse},
///     literal::Literal,
///     result::ParseResult,
///     cache::ParsingCache
/// };
///
/// // Example AST for expressions
/// #[derive(Debug, PartialEq, Clone)]
/// enum MyAst {
///     Atom(String),
///     Parenthesized(Box<MyAst>),
/// }
///
/// #[derive(Clone, Default)]
/// struct Expression {
///     // This compiles and works!
///     parenthesized: Recursive<Expression>,
/// }
///
/// impl Parser for Expression {
///     type Output = MyAst;
///     
///     fn read<S>(
///         &self,
///         source: &mut Source<S>,
///         cache: &mut impl ParsingCache,
///         context: &mut ()
///     ) -> ParseResult<Self::Output>
///     where
///         S: neotoma::parser::Parsable,
///     {
///         // Try to parse parentheses like: (inner_expression)
///         let open_paren = Literal::from_str("(");
///         if open_paren.parse(source, cache, context).is_ok() {
///             // This creates unlimited recursion depth as needed
///             let inner = self.parenthesized.parse(source, cache, context)?;
///             let close_paren = Literal::from_str(")");
///             close_paren.parse(source, cache, context)?;
///             Ok(MyAst::Parenthesized(Box::new(inner)))
///         } else {
///             // Parse a simple atom (single letter)
///             let atom = Literal::from_str("x");
///             atom.parse(source, cache, context)?;
///             Ok(MyAst::Atom("x".to_string()))
///         }
///     }
/// }
///
/// // Test it works with nested parentheses
/// let parser = Expression::default();
/// let cursor = Cursor::new(b"((x))");
/// let mut source = Source::new(cursor);
///
/// let result = parse(parser, &mut source).unwrap();
/// assert_eq!(result, MyAst::Parenthesized(Box::new(
///     MyAst::Parenthesized(Box::new(MyAst::Atom("x".to_string())))
/// )));
/// ```
///
/// # How it works
///
/// 1. **Construction**: `Recursive::new()` creates an empty wrapper (no cycles)
/// 2. **First parse**: Creates the wrapped parser using `P::default()` and caches it  
/// 3. **Subsequent parses**: Reuses the same cached instance for efficiency
///
/// This enables parsers that can handle arbitrarily deep nesting (like deeply nested parentheses)
/// without construction-time infinite recursion.
///
/// # Requirements
///
/// The wrapped parser type `P` must implement `Default` so that `Recursive<P>` can create
/// an instance when first needed.
pub struct Recursive<P> {
    cached_parser: OnceCell<Box<P>>,
}

impl<P> Recursive<P>
where
    P: Default,
{
    /// Creates a new `Recursive` wrapper that will construct the parser
    /// using `P::default()` on first use.
    ///
    /// The wrapped parser is created lazily - only when first needed during parsing.
    pub fn new() -> Self {
        Self {
            cached_parser: OnceCell::new(),
        }
    }

    /// Gets or creates the cached parser instance.
    fn get_parser(&self) -> &P {
        self.cached_parser.get_or_init(|| Box::new(P::default()))
    }
}

impl<P, Ctx> Parser<Ctx> for Recursive<P>
where
    P: Parser<Ctx> + Default,
{
    type Output = P::Output;

    fn read<S>(
        &self,
        source: &mut crate::parser::Source<S>,
        cache: &mut impl ParsingCache,
        context: &mut Ctx,
    ) -> ParseResult<Self::Output>
    where
        S: crate::parser::Parsable,
    {
        // Delegate to the cached parser instance
        self.get_parser().read(source, cache, context)
    }

    fn id(&self) -> u64 {
        // Use the same cached instance for consistent ID
        self.get_parser().id()
    }
}

impl<P> Default for Recursive<P> {
    fn default() -> Self {
        Self {
            cached_parser: OnceCell::new(),
        }
    }
}

// Implement Clone by creating a new empty Recursive
// (we don't want to share the cached instance between clones)
impl<P> Clone for Recursive<P> {
    fn clone(&self) -> Self {
        Self::default()
    }
}

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

    // Simple test parser that just parses "hello"
    #[derive(Clone)]
    struct HelloParser;

    impl Default for HelloParser {
        fn default() -> Self {
            Self
        }
    }

    impl<Ctx> Parser<Ctx> for HelloParser {
        type Output = String;

        fn read<S>(
            &self,
            source: &mut Source<S>,
            cache: &mut impl ParsingCache,
            context: &mut Ctx,
        ) -> ParseResult<Self::Output>
        where
            S: crate::parser::Parsable,
        {
            let literal = Literal::from_str_const("hello");
            literal
                .parse(source, cache, context)
                .map(|_| "hello".to_string())
        }
    }

    #[test]
    fn recursive_parser_works() {
        use crate::parser::parse;
        let recursive = Recursive::<HelloParser>::new();
        let cursor = Cursor::new(b"hello");
        let mut source = Source::new(cursor);

        let result = parse(recursive, &mut source);
        assert!(result.is_ok());
        assert_eq!(result.unwrap(), "hello");
    }

    #[test]
    fn recursive_parser_caches_instance() {
        let recursive = Recursive::<HelloParser>::new();

        // First access should create the parser
        let id1 = <Recursive<HelloParser> as crate::parser::Parser<()>>::id(&recursive);

        // Second access should use the same cached instance
        let id2 = <Recursive<HelloParser> as crate::parser::Parser<()>>::id(&recursive);

        assert_eq!(id1, id2, "IDs should be identical for cached instance");
    }
}