mpl 0.3.0

//! Direct left recursion via Squirrel-style seed-growing.
//!
//! Grammar (mpl single-rule form):
//!   LSum   = LSum N / N
//!   N      = '1' () / N1
//!   N1     = '2' () / N2
//!   N2     = '3' () / f
//!
//! Without left-recursion support `parse(LSum)` would infinite-loop.
//! With `squirrel_parse` it grows the seed left-associatively:
//!   "1"     →  N(1)
//!   "12"    →  LSum(N(1), N(2))
//!   "123"   →  LSum(LSum(N(1), N(2)), N(3))

use std::collections::HashMap;

use mpl::output::Output;
use mpl::parser::Parser;
use mpl::rules::{RightRule, RightRuleKind, Rules};
use mpl::span::{Len, Start, StartAndLenSpan};
use mpl::symbols::{StrTerminal, Variable};
use mpl::trees::AST;

#[derive(Clone, Debug, Hash, Eq, PartialEq)]
enum LSumVariable {
    LSum,
    N,
    N1,
    N2,
}

impl Variable for LSumVariable {}

type LSumSpan = StartAndLenSpan<u32, u16>;
type LSumAst = AST<LSumVariable, LSumSpan, ()>;

struct LSumParser;

impl<'i, V, P, L, R, O> Parser<'i, str, StrTerminal<'i>, V, StartAndLenSpan<P, L>, P, R, O>
    for LSumParser
where
    V: Variable,
    P: Start<str, L>,
    L: Len<str, P>,
    R: Rules<StrTerminal<'i>, V>,
    O: Output<'i, str, V, StartAndLenSpan<P, L>>,
{
}

fn make_rules() -> HashMap<LSumVariable, RightRule<StrTerminal<'static>, LSumVariable>> {
    use LSumVariable::*;
    use RightRuleKind as K;

    let mut rules = HashMap::new();
    // LSum = LSum N / N
    rules.insert(
        LSum,
        RightRule::from_right_rule_kind((K::V(LSum), K::V(N)), K::V(N)),
    );
    // N = '1' () / N1
    rules.insert(
        N,
        RightRule::from_right_rule_kind((K::T(StrTerminal::Char('1')), K::Empty), K::V(N1)),
    );
    // N1 = '2' () / N2
    rules.insert(
        N1,
        RightRule::from_right_rule_kind((K::T(StrTerminal::Char('2')), K::Empty), K::V(N2)),
    );
    // N2 = '3' () / f
    rules.insert(
        N2,
        RightRule::from_right_rule_kind((K::T(StrTerminal::Char('3')), K::Empty), K::Failure),
    );
    rules
}

fn parse(input: &str) -> Result<LSumAst, LSumAst> {
    let parser = LSumParser;
    let rules = make_rules();
    let span = StartAndLenSpan::<u32, u16>::from_start_len(0, input.len() as u16);
    parser.squirrel_parse(input, &rules, &LSumVariable::LSum, &span)
}

#[test]
fn single_digit() {
    // "1": only the non-recursive alternative N matches.
    let r = parse("1");
    assert!(r.is_ok(), "expected parse success");
}

#[test]
fn two_digits_grows_seed_once() {
    // "12": one growth of the seed produces LSum(N, N).
    let r = parse("12");
    assert!(r.is_ok(), "expected parse success");
    let ast = r.unwrap();
    assert_eq!(ast.span.start, 0);
    assert_eq!(ast.span.len, 2);
}

#[test]
fn three_digits_left_associates() {
    // "123": two growths produce LSum(LSum(N, N), N).
    let r = parse("123");
    assert!(r.is_ok(), "expected parse success");
    let ast = r.unwrap();
    assert_eq!(ast.span.start, 0);
    assert_eq!(ast.span.len, 3);

    // Verify the AST is left-associative: outermost LSum's first choice
    // has another LSum on the LHS, not a plain N.
    let first_choice = ast.as_first().expect("first choice");
    let lhs_ast = &first_choice.lhs;
    let lhs_internal = lhs_ast.as_internal().expect("internal node on LHS");
    assert_eq!(lhs_internal.value.0, LSumVariable::LSum,
        "LHS of outermost LSum should be another LSum (left-associative)");
}

#[test]
fn rejects_invalid_input() {
    // "9" — N cannot match.
    let r = parse("9");
    assert!(r.is_err(), "9 should not parse");

    // "129" — first two digits parse, '9' fails to extend.
    // squirrel_parse only accepts when the full span is consumed, so this fails.
    let r = parse("129");
    assert!(r.is_err(), "129 should not match the full span");
}

#[test]
fn empty_input_fails() {
    // No alternative produces zero-length match.
    let r = parse("");
    assert!(r.is_err(), "empty input should fail");
}

#[test]
fn stress_chain_of_ten() {
    // "1212123212" — alternates 1/2/3 repeatedly, 10 chars.
    // Left associativity means 9 nested LSums, no infinite recursion.
    let r = parse("1212123212");
    assert!(r.is_ok(), "10-char input should parse");
    let ast = r.unwrap();
    assert_eq!(ast.span.start, 0);
    assert_eq!(ast.span.len, 10);
}