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

use crate::collections::{map, Map};
use crate::grammar::consts::INLINE;
use crate::grammar::repr::*;
use crate::normalize::{NormError, NormResult};
use petgraph::graph::{Graph, NodeIndex};
use string_cache::DefaultAtom as Atom;

#[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,
            graph: Graph::new(),
            nonterminal_map: map(),
        }
    }

    fn create_nodes(&mut self) {
        let inline = Atom::from(INLINE);
        for (name, data) in &self.grammar.nonterminals {
            if data.annotations.iter().any(|a| a.id == inline) {
                let index = self.graph.add_node(name.clone());
                self.nonterminal_map.insert(name.clone(), 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(ref 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() {
            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) {
                    self.walk(states, result, target)?;
                }
                states[source.index()] = WalkState::Visited;
                result.push(nt.clone());
                Ok(())
            }
            WalkState::Visited => Ok(()),
            WalkState::Visiting => {
                return_err!(
                    self.grammar.nonterminals[nt].span,
                    "cyclic inline directive: `{}` would have to be inlined into itself",
                    nt
                );
            }
        }
    }
}