lalrpop 0.12.2

convenient LR(1) parser generator
Documentation 
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

#![allow(dead_code)]

use intern::intern;
use normalize::{NormError, NormResult};
use petgraph::graph::{Graph, NodeIndex};
use grammar::consts::INLINE;
use grammar::repr::*;
use collections::{map, Map};

#[cfg(test)]
mod test;

/// Computes the proper order to inline the various nonterminals in
/// `grammar`. Reports an error if there is an inline
/// cycle. Otherwise, yields an ordering such that we inline X before
/// Y if Y references X.  I actually think it doesn't matter what
/// order we do the inlining, really, but this order seems better
/// somehow. :) (That is, inline into something before we inline it.)
pub fn inline_order(grammar: &Grammar) -> NormResult<Vec<NonterminalString>> {
    let mut graph = NonterminalGraph::new(grammar);
    graph.create_nodes();
    graph.add_edges();
    graph.inline_order()
}

struct NonterminalGraph<'grammar> {
    grammar: &'grammar Grammar,
    graph: Graph<NonterminalString, ()>,
    nonterminal_map: Map<NonterminalString, NodeIndex>,
}

#[derive(Copy, Clone)]
enum WalkState {
    NotVisited,
    Visiting,
    Visited,
}

impl<'grammar> NonterminalGraph<'grammar> {
    fn new(grammar: &'grammar Grammar) -> NonterminalGraph<'grammar> {
        NonterminalGraph {
            grammar: grammar,
            graph: Graph::new(),
            nonterminal_map: map(),
        }
    }

    fn create_nodes(&mut self) {
        let inline = intern(INLINE);
        for (&name, data) in &self.grammar.nonterminals {
            if data.annotations.iter().any(|a| a.id == inline) {
                let index = self.graph.add_node(name);
                self.nonterminal_map.insert(name, index);
            }
        }
    }

    fn add_edges(&mut self) {
        for production in self.grammar.nonterminals.values().flat_map(|d| &d.productions) {
            let from_index = match self.nonterminal_map.get(&production.nonterminal) {
                Some(&index) => index,
                None => continue, // this is not an inlined nonterminal
            };

            for &symbol in &production.symbols {
                match symbol {
                    Symbol::Nonterminal(to) => {
                        if let Some(&to_index) = self.nonterminal_map.get(&to) {
                            self.graph.add_edge(from_index, to_index, ());
                        }
                    }
                    Symbol::Terminal(_) => { }
                }
            }
        }
    }

    fn inline_order(&self) -> NormResult<Vec<NonterminalString>> {
        let mut states = vec![WalkState::NotVisited; self.graph.node_count()];
        let mut result = vec![];
        for node in self.nonterminal_map.values().cloned() {
            try!(self.walk(&mut states, &mut result, node));
        }
        Ok(result)
    }

    fn walk(&self,
            states: &mut Vec<WalkState>,
            result: &mut Vec<NonterminalString>,
            source: NodeIndex)
            -> NormResult<()>
    {
        let nt = *self.graph.node_weight(source).unwrap();

        match states[source.index()] {
            WalkState::NotVisited => {
                states[source.index()] = WalkState::Visiting;
                for target in self.graph.neighbors(source) {
                    try!(self.walk(states, result, target));
                }
                states[source.index()] = WalkState::Visited;
                result.push(nt);
                Ok(())
            }
            WalkState::Visited => {
                Ok(())
            }
            WalkState::Visiting => {
                return_err!(
                    self.grammar.nonterminals[&nt].span,
                    "cyclic inline directive: `{}` would have to be inlined into itself", nt);
            }
        }
    }
}