1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

use proc_macro2::Span;
use std::collections::HashMap;

use crate::ast::*;

pub struct GrammarAnalysis<'a> {
    pub rules: HashMap<String, &'a Rule>,
    pub left_recursion: Vec<RecursionError>,
}

pub fn check<'a>(grammar: &'a Grammar) -> GrammarAnalysis<'a> {
    let mut rules = HashMap::new();

    for rule in grammar.iter_rules() {
        rules.entry(rule.name.to_string()).or_insert(rule);
    }

    let left_recursion = RecursionVisitor::check(grammar, &rules);

    GrammarAnalysis {
        rules,
        left_recursion,
    }
}

struct RecursionVisitor<'a> {
    stack: Vec<String>,
    rules: &'a HashMap<String, &'a Rule>,
    errors: Vec<RecursionError>,
}

pub struct RecursionError {
    pub span: Span,
    pub path: Vec<String>,
}

impl RecursionError {
    pub fn msg(&self) -> String {
        format!(
            "left recursive rules create an infinite loop: {}",
            self.path.join(" -> ")
        )
    }
}

#[derive(Clone)]
struct RuleInfo {
    /// True if the rule is known to match without consuming any input.
    /// This is a conservative heuristic, if unknown, we return false to avoid reporting false-positives
    /// for left recursion.
    nullable: bool,
}

impl<'a> RecursionVisitor<'a> {
    fn check(grammar: &'a Grammar, rules: &HashMap<String, &'a Rule>) -> Vec<RecursionError> {
        let mut visitor = RecursionVisitor {
            rules,
            errors: Vec::new(),
            stack: Vec::new(),
        };

        for rule in grammar.iter_rules() {
            visitor.walk_rule(rule);
            debug_assert!(visitor.stack.is_empty());
        }

        visitor.errors
    }

    fn walk_rule(&mut self, rule: &'a Rule) -> RuleInfo {
        self.stack.push(rule.name.to_string());
        let res = self.walk_expr(&rule.expr);
        self.stack.pop().unwrap();
        res
    }

    fn walk_expr(&mut self, this_expr: &Expr) -> RuleInfo {
        use self::Expr::*;
        match *this_expr {
            RuleExpr(ref rule_ident, _) => {
                let name = rule_ident.to_string();

                if let Some(loop_start) = self
                    .stack
                    .iter()
                    .position(|caller_name| caller_name == &name)
                {
                    let mut recursive_loop = self.stack[loop_start..].to_vec();
                    recursive_loop.push(name);
                    self.errors.push(RecursionError {
                        path: recursive_loop,
                        span: rule_ident.span(),
                    });
                    return RuleInfo { nullable: false };
                }

                if let Some(rule) = self.rules.get(&name) {
                    self.walk_rule(rule)
                } else {
                    // Missing rule would have already been reported
                    RuleInfo { nullable: false }
                }
            }
            ActionExpr(ref elems, ..) => {
                for elem in elems {
                    if !self.walk_expr(&elem.expr).nullable {
                        return RuleInfo { nullable: false };
                    }
                }

                RuleInfo { nullable: true }
            }
            ChoiceExpr(ref choices) => {
                let mut nullable = false;

                for expr in choices {
                    nullable |= self.walk_expr(expr).nullable;
                }

                RuleInfo { nullable }
            }

            OptionalExpr(ref expr) | PosAssertExpr(ref expr) | NegAssertExpr(ref expr) => {
                self.walk_expr(expr);
                RuleInfo { nullable: true }
            }

            Repeat(ref expr, ref bounds, _) => {
                let nullable = match bounds {
                    BoundedRepeat::None => true,
                    _ => false,
                };

                let res = self.walk_expr(expr);
                RuleInfo {
                    nullable: res.nullable | nullable,
                }
            }

            MatchStrExpr(ref expr) | QuietExpr(ref expr) => self.walk_expr(expr),

            PrecedenceExpr { .. } => RuleInfo { nullable: false },

            LiteralExpr(_) | PatternExpr(_) | MethodExpr(_, _) | FailExpr(_) | MarkerExpr(_) => {
                RuleInfo { nullable: false }
            }
            PositionExpr => RuleInfo { nullable: true },
        }
    }
}