hawdb-sql-syntax 0.16.0

// Copyright 2026 Nowledge
// SPDX-License-Identifier: Apache-2.0

use super::*;
use crate::tokenize;
use Expression::{
    Choice, Keyword as K, Not, Optional, Repeat, Rule as R, Sequence as S, Token as Tok,
};

fn parse(grammar: &Grammar<()>, sql: &str, limits: Limits) -> Result<ParseTree<()>, SyntaxError> {
    grammar.parse(sql, &tokenize(sql).unwrap(), "Root", limits)
}

#[test]
fn choice_is_ordered_and_does_not_retry_after_a_successful_prefix() {
    let grammar = Grammar::<()>::compile(vec![
        ("Root", S(vec![R("Choice"), Tok(TokenKind::End, "end")])),
        (
            "Choice",
            Choice(vec![K("SELECT"), S(vec![K("SELECT"), K("ALL")])]),
        ),
    ])
    .unwrap();
    let error = parse(&grammar, "SELECT ALL", Limits::default())
        .err()
        .unwrap();
    assert_eq!(error.span, Span::new(7, 10));
}

#[test]
fn caches_success_and_failure_at_the_same_token_position() {
    let grammar = Grammar::<()>::compile(vec![
        (
            "Root",
            Choice(vec![
                S(vec![R("Prefix"), R("Missing")]),
                S(vec![R("Prefix"), R("Missing")]),
                S(vec![
                    R("Prefix"),
                    Tok(TokenKind::Number, "number"),
                    Tok(TokenKind::End, "end"),
                ]),
            ]),
        ),
        ("Prefix", K("SELECT")),
        ("Missing", K("FROM")),
    ])
    .unwrap();
    let tree = parse(&grammar, "SELECT 1", Limits::default()).unwrap();
    assert_eq!(tree.memo_entries, 3);
    assert_eq!(tree.memo_hits, 3);
    assert_eq!(
        tree.nodes
            .iter()
            .filter(|node| node.name == Some("Prefix"))
            .count(),
        1
    );
}

#[test]
fn invalid_recursive_and_nullable_grammars_fail_compilation() {
    for rules in [
        vec![("Root", R("Missing"))],
        vec![("Root", K("SELECT")), ("Root", K("FROM"))],
        vec![("Root", R("Root"))],
        vec![
            ("Root", R("Other")),
            ("Other", S(vec![Optional(Box::new(K("SELECT"))), R("Root")])),
        ],
        vec![("Root", Repeat(Box::new(Optional(Box::new(K("SELECT"))))))],
        vec![("Root", Repeat(Box::new(Tok(TokenKind::End, "end"))))],
        vec![("Root", Not(Box::new(R("Root")), "not recursive"))],
    ] {
        assert!(Grammar::<()>::compile(rules).is_err());
    }
}

#[test]
fn reports_farthest_unicode_token_and_discards_lookahead_errors() {
    let grammar = Grammar::<()>::compile(vec![(
        "Root",
        S(vec![
            Not(
                Box::new(S(vec![K("SELECT"), K("FROM")])),
                "a nonempty SELECT",
            ),
            K("SELECT"),
            K("ALL"),
        ]),
    )])
    .unwrap();
    let error = parse(&grammar, "SELECT \u{540d}\u{79f0}", Limits::default())
        .err()
        .unwrap();
    assert_eq!(error.span, Span::new(7, 13));
    assert_eq!(error.expected, Some("ALL"));
}

#[test]
fn work_limit_boundary_and_all_resource_failures_are_fatal() {
    let grammar = Grammar::<()>::compile(vec![("Root", K("SELECT"))]).unwrap();
    let tree = parse(&grammar, "SELECT", Limits::default()).unwrap();
    assert!(parse(
        &grammar,
        "SELECT",
        Limits {
            steps: tree.steps,
            ..Limits::default()
        }
    )
    .is_ok());
    let error = parse(
        &grammar,
        "SELECT",
        Limits {
            steps: tree.steps - 1,
            ..Limits::default()
        },
    )
    .err()
    .unwrap();
    assert_eq!(error.code, SyntaxErrorCode::ParserLimitExceeded);

    let grammar = Grammar::<()>::compile(vec![
        ("Root", Choice(vec![R("Nested"), K("SELECT")])),
        ("Nested", R("Leaf")),
        ("Leaf", K("SELECT")),
    ])
    .unwrap();
    for limits in [
        Limits {
            nodes: 0,
            ..Limits::default()
        },
        Limits {
            memo_entries: 1,
            ..Limits::default()
        },
        Limits {
            depth: 2,
            ..Limits::default()
        },
        Limits {
            steps: 3,
            ..Limits::default()
        },
    ] {
        let error = parse(&grammar, "SELECT", limits).err().unwrap();
        assert_eq!(error.code, SyntaxErrorCode::ParserLimitExceeded);
    }
}

#[test]
fn native_resource_errors_are_not_alternative_mismatches() {
    let grammar = Grammar::compile(vec![(
        "Root",
        Choice(vec![
            Expression::Native {
                matcher: |_, tokens, position| NativeMatch::<()> {
                    end: position,
                    value: Err(SyntaxError::new(
                        SyntaxErrorCode::ExpressionNestingLimitExceeded,
                        tokens[position].span,
                    )),
                },
                nullable: false,
            },
            K("SELECT"),
        ]),
    )])
    .unwrap();
    let error = parse(&grammar, "SELECT", Limits::default()).err().unwrap();
    assert_eq!(error.code, SyntaxErrorCode::ExpressionNestingLimitExceeded);
}

#[test]
fn memoized_recursive_failure_has_linear_rule_evaluations() {
    let grammar = Grammar::<()>::compile(vec![
        ("Root", R("Nested")),
        (
            "Nested",
            Choice(vec![
                S(vec![
                    Tok(TokenKind::LeftParen, "("),
                    R("Nested"),
                    Tok(TokenKind::RightParen, ")"),
                ]),
                S(vec![Tok(TokenKind::LeftParen, "("), R("Nested"), K("END")]),
                K("SELECT"),
            ]),
        ),
    ])
    .unwrap();
    // Without failure memoization, each extra unmatched '(' doubles the work.
    let sql = "(".repeat(24);
    let error = parse(
        &grammar,
        &sql,
        Limits {
            steps: 500,
            depth: 128,
            ..Limits::default()
        },
    )
    .err()
    .unwrap();
    assert_eq!(error.code, SyntaxErrorCode::UnexpectedEnd);
    assert_eq!(error.span, Span::new(24, 24));
}

#[test]
fn optional_and_lookahead_preserve_fatal_native_errors() {
    fn terminal() -> Expression<()> {
        Expression::Native {
            matcher: |_, tokens, position| NativeMatch {
                end: position,
                value: Err(SyntaxError::new(
                    SyntaxErrorCode::GraphPatternNestingLimitExceeded,
                    tokens[position].span,
                )),
            },
            nullable: false,
        }
    }
    for expression in [
        Optional(Box::new(terminal())),
        Repeat(Box::new(terminal())),
        Not(Box::new(terminal()), "not a terminal"),
        Expression::Ahead(Box::new(terminal()), "a terminal"),
    ] {
        let grammar = Grammar::compile(vec![("Root", expression)]).unwrap();
        let error = parse(&grammar, "SELECT", Limits::default()).err().unwrap();
        assert_eq!(
            error.code,
            SyntaxErrorCode::GraphPatternNestingLimitExceeded
        );
    }
}

#[test]
fn cached_success_preserves_diagnostics_after_lookahead() {
    let grammar = Grammar::<()>::compile(vec![
        (
            "Root",
            S(vec![
                Not(Box::new(S(vec![R("Prefix"), K("STOP")])), "no STOP"),
                R("Prefix"),
                K("WHERE"),
            ]),
        ),
        (
            "Prefix",
            S(vec![
                K("SELECT"),
                Optional(Box::new(S(vec![K("FROM"), K("TABLE")]))),
            ]),
        ),
    ])
    .unwrap();
    let error = parse(&grammar, "SELECT FROM name", Limits::default())
        .err()
        .unwrap();
    assert_eq!(error.span, Span::new(12, 16));
    assert_eq!(error.expected, Some("TABLE"));
}

#[test]
fn exact_capture_and_memo_budgets_admit_only_complete_matches() {
    let grammar = Grammar::<()>::compile(vec![("Root", R("Leaf")), ("Leaf", K("SELECT"))]).unwrap();
    for limits in [
        Limits {
            nodes: 2,
            memo_entries: 2,
            ..Limits::default()
        },
        Limits {
            nodes: 2,
            memo_entries: 3,
            ..Limits::default()
        },
    ] {
        assert!(parse(&grammar, "SELECT", limits).is_ok());
    }
    for limits in [
        Limits {
            nodes: 1,
            ..Limits::default()
        },
        Limits {
            memo_entries: 1,
            ..Limits::default()
        },
    ] {
        let error = parse(&grammar, "SELECT", limits).err().unwrap();
        assert_eq!(error.code, SyntaxErrorCode::ParserLimitExceeded);
    }
}

#[test]
fn native_nullable_contract_is_enforced_even_outside_repetition() {
    let grammar = Grammar::<()>::compile(vec![(
        "Root",
        Expression::Native {
            matcher: |_, _, position| NativeMatch {
                end: position,
                value: Ok(()),
            },
            nullable: false,
        },
    )])
    .unwrap();
    assert_eq!(
        parse(&grammar, "SELECT", Limits::default())
            .err()
            .unwrap()
            .code,
        SyntaxErrorCode::ParserLimitExceeded
    );
}

#[test]
fn long_invalid_tokens_keep_exact_final_error_text_and_span() {
    let grammar = Grammar::<()>::compile(vec![
        ("Root", Choice(vec![R("First"), R("Second"), R("Third")])),
        ("First", K("SELECT")),
        ("Second", K("CREATE")),
        ("Third", K("FROM")),
    ])
    .unwrap();
    let sql = "x".repeat(256 * 1024);
    let error = parse(&grammar, &sql, Limits::default()).err().unwrap();
    assert_eq!(error.code, SyntaxErrorCode::UnexpectedToken);
    assert_eq!(error.span, Span::new(0, sql.len()));
    assert_eq!(error.found.as_deref(), Some(sql.as_str()));
    assert_eq!(error.expected, Some("SELECT"));
}