rantlr_core/

linter.rs

//! Grammar linter — catches constructs that break recursive-descent / PEG engines.

use crate::ast::{Expr, Grammar, GrammarItem, RuleDecl};
use crate::diagnostic::{Diagnostic, DiagnosticKind};
use crate::error::RantlrError;
use crate::fix_hint::FixHint;

/// Run all lint passes. Returns an error on the first hard failure.
pub fn lint(source: &str, grammar: &Grammar) -> Result<(), RantlrError> {
    let diags = lint_all(source, grammar);
    if let Some(diag) = diags.into_iter().next() {
        return Err(RantlrError::from_diagnostic(source, diag));
    }
    Ok(())
}

/// Collect every lint diagnostic (useful for LSP / playground).
pub fn lint_all(source: &str, grammar: &Grammar) -> Vec<Diagnostic> {
    let mut out = Vec::new();
    for item in &grammar.items {
        if let GrammarItem::Rule(rule) = item {
            if let Some(diag) = check_direct_left_recursion(source, rule) {
                out.push(diag);
            }
        }
    }
    out
}

/// Detect direct left recursion: a rule that can begin by calling itself.
fn check_direct_left_recursion(source: &str, rule: &RuleDecl) -> Option<Diagnostic> {
    if !leftmost_refs(&rule.body).iter().any(|r| r == &rule.name) {
        return None;
    }

    let message = format!(
        "Rule '{}' is left-recursive. In Rantlr, use 'repeat {{ ... }}' instead of calling the rule at the start to ensure better performance and avoid stack overflow.",
        rule.name
    );

    let fix = suggest_left_recursion_fix(source, rule);

    let mut diag = Diagnostic::error(DiagnosticKind::Lint, message, rule.name_span)
        .with_code("left-recursion")
        .with_help(format!(
            "rewrite `{name}` so it starts with a different symbol, then use `repeat {{ ... }}` for the recursive suffix",
            name = rule.name
        ));

    if let Some(fix) = fix {
        diag = diag.with_fix(fix);
    }

    Some(diag)
}

fn suggest_left_recursion_fix(source: &str, rule: &RuleDecl) -> Option<FixHint> {
    let start = rule.span.start.as_usize().min(source.len());
    let end = rule.span.end.as_usize().min(source.len());
    if start >= end {
        return None;
    }
    let before = source[start..end].trim_end().to_string();

    let after = match &rule.body {
        // rule expr { expr "+" term }  →  rule expr { term repeat { "+" term } }
        Expr::Seq { items } if matches!(items.first(), Some(Expr::Ref { name, .. }) if name == &rule.name)
            && items.len() >= 2 =>
        {
            let rest = &items[1..];
            let base = infer_base_symbol(rest, &rule.name)
                .unwrap_or_else(|| "/* your_base_case */".into());
            let suffix = rest
                .iter()
                .map(expr_to_gr)
                .collect::<Vec<_>>()
                .join("\n        ");
            format!(
                "rule {} {{\n    {}\n    repeat {{\n        {}\n    }}\n}}",
                rule.name, base, suffix
            )
        }
        // rule expr { match expr | "x" }  →  rule expr { "x" }
        Expr::Match { arms } => {
            let non_self: Vec<&Expr> = arms
                .iter()
                .filter(|a| !leftmost_refs(a).iter().any(|r| *r == rule.name.as_str()))
                .collect();
            if non_self.is_empty() {
                format!(
                    "rule {} {{\n    // TODO: add a base case that does NOT call `{0}` first\n    /* base */\n}}",
                    rule.name
                )
            } else if non_self.len() == 1 {
                format!(
                    "rule {} {{\n    {}\n}}",
                    rule.name,
                    expr_to_gr(non_self[0])
                )
            } else {
                let arms_txt = non_self
                    .iter()
                    .map(|a| expr_to_gr(a))
                    .collect::<Vec<_>>()
                    .join(" | ");
                format!("rule {} {{\n    match {}\n}}", rule.name, arms_txt)
            }
        }
        _ => format!(
            "rule {} {{\n    // Start with something that is NOT `{0}`, then loop:\n    /* base */\n    repeat {{\n        /* recursive suffix */\n    }}\n}}",
            rule.name
        ),
    };

    Some(FixHint::new(
        "Rewrite left recursion with repeat",
        format!(
            "Whoops! Rule `{name}` is calling itself too early — that's a left-recursion loop. Click Fix to turn it into a `repeat` block that starts with a base case first.",
            name = rule.name
        ),
        before,
        after,
        rule.span,
        source,
    ))
}

fn infer_base_symbol(rest: &[Expr], self_name: &str) -> Option<String> {
    // Prefer the last Ref that isn't self — common pattern: expr Op term
    for expr in rest.iter().rev() {
        if let Expr::Ref { name, .. } = expr {
            if name != self_name {
                return Some(name.clone());
            }
        }
    }
    None
}

fn expr_to_gr(expr: &Expr) -> String {
    match expr {
        Expr::Ref { name, .. } => name.clone(),
        Expr::Literal { value, .. } => format!("\"{}\"", escape_gr_string(value)),
        Expr::Group { body } => format!("({})", expr_to_gr(body)),
        Expr::Seq { items } => items.iter().map(expr_to_gr).collect::<Vec<_>>().join(" "),
        Expr::Match { arms } => {
            let inner = arms
                .iter()
                .map(expr_to_gr)
                .collect::<Vec<_>>()
                .join(" | ");
            format!("match {inner}")
        }
        Expr::Alt { alts } => alts
            .iter()
            .map(expr_to_gr)
            .collect::<Vec<_>>()
            .join(" | "),
        Expr::Optional { body } => format!("optional {{ {} }}", expr_to_gr(body)),
        Expr::Repeat { min, max, body } => {
            let bounds = match (min, max) {
                (None, None) => String::new(),
                (Some(a), None) => format!("({a}..)"),
                (Some(a), Some(b)) => format!("({a}..{b})"),
                (None, Some(b)) => format!("(..{b})"),
            };
            format!("repeat{bounds} {{ {} }}", expr_to_gr(body))
        }
    }
}

fn escape_gr_string(s: &str) -> String {
    s.chars()
        .map(|c| match c {
            '\\' => "\\\\".into(),
            '"' => "\\\"".into(),
            '\n' => "\\n".into(),
            '\t' => "\\t".into(),
            '\r' => "\\r".into(),
            c => c.to_string(),
        })
        .collect()
}

/// Names that can appear as the leftmost symbol of `expr`.
fn leftmost_refs(expr: &Expr) -> Vec<&str> {
    match expr {
        Expr::Alt { alts } => alts.iter().flat_map(leftmost_refs).collect(),
        Expr::Seq { items } => {
            let mut refs = Vec::new();
            for item in items {
                refs.extend(leftmost_refs(item));
                if !is_nullable(item) {
                    break;
                }
            }
            refs
        }
        Expr::Match { arms } => arms.iter().flat_map(leftmost_refs).collect(),
        Expr::Repeat { body, .. } | Expr::Optional { body } | Expr::Group { body } => {
            leftmost_refs(body)
        }
        Expr::Ref { name, .. } => vec![name.as_str()],
        Expr::Literal { .. } => vec![],
    }
}

fn is_nullable(expr: &Expr) -> bool {
    match expr {
        Expr::Optional { .. } => true,
        Expr::Repeat { min, .. } => matches!(min, None | Some(0)),
        Expr::Group { body } => is_nullable(body),
        Expr::Alt { alts } => alts.iter().any(is_nullable),
        Expr::Seq { items } => items.iter().all(is_nullable),
        Expr::Match { arms } => arms.iter().any(is_nullable),
        Expr::Ref { .. } | Expr::Literal { .. } => false,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::parser::parse;

    #[test]
    fn accepts_calculator() {
        let src = include_str!("../testdata/calculator.gr");
        let g = parse(src).unwrap();
        assert!(lint_all(src, &g).is_empty());
    }

    #[test]
    fn flags_direct_left_recursion_with_fix() {
        let src = r#"
            grammar Bad;
            token N = Number;
            rule expr {
                expr "+" term
            }
            rule term {
                N
            }
        "#;
        let g = parse(src).unwrap();
        let diags = lint_all(src, &g);
        assert_eq!(diags.len(), 1);
        assert_eq!(diags[0].code.as_deref(), Some("left-recursion"));
        let fix = diags[0].fix.as_ref().expect("fix hint");
        assert!(fix.after.contains("repeat"));
        assert!(fix.after.contains("term"));
        assert!(fix.after.contains("\"+\""));
        // Must not still start the body with a self-call.
        assert!(fix.after.contains("rule expr {\n    term\n"));
        assert!(!fix.suggestion.is_empty());
        assert_eq!(fix.suggestion, fix.after);
        assert!(fix.start < fix.end);
        assert!(fix.start_line >= 1);
        assert!(fix.explanation.to_lowercase().contains("left-recursion"));
    }

    #[test]
    fn flags_left_recursion_through_match() {
        let src = r#"
            grammar Bad;
            rule expr {
                match expr | "x"
            }
        "#;
        let g = parse(src).unwrap();
        let diags = lint_all(src, &g);
        assert_eq!(diags.len(), 1);
        assert!(diags[0].message.contains("left-recursive"));
        let fix = diags[0].fix.as_ref().unwrap();
        assert!(fix.after.contains("\"x\""));
    }

    #[test]
    fn allows_right_recursion_and_repeat() {
        let src = r#"
            grammar Ok;
            token N = Number;
            rule expr {
                term
                repeat {
                    match "+" | "-"
                    term
                }
            }
            rule term {
                N
            }
            rule list {
                item
                optional { list }
            }
            rule item { N }
        "#;
        let g = parse(src).unwrap();
        assert!(lint_all(src, &g).is_empty());
    }
}