1 use crate::grammar::repr::*;
2 use crate::lr1::core::*;
3 use crate::lr1::lookahead::Lookahead;
4 use petgraph::graph::NodeIndex;
5 use petgraph::prelude::*;
6 use petgraph::{EdgeDirection, Graph};
7 
8 // Each state `s` corresponds to the node in the graph with index
9 // `s`. The edges are the shift transitions.
10 pub struct StateGraph {
11     graph: Graph<(), Symbol>,
12 }
13 
14 impl StateGraph {
new<'grammar, L>(states: &[State<'grammar, L>]) -> StateGraph where L: Lookahead,15     pub fn new<'grammar, L>(states: &[State<'grammar, L>]) -> StateGraph
16     where
17         L: Lookahead,
18     {
19         let mut graph = Graph::new();
20 
21         // First, create the nodes.
22         for i in 0..states.len() {
23             let j = graph.add_node(());
24             assert_eq!(i, j.index());
25         }
26 
27         // Add in the edges.
28         for (i, state) in states.iter().enumerate() {
29             // Successors of a node arise from:
30             // - shifts (found in the `conflicts` and `tokens` maps)
31             // - gotos (found in the `gotos` map)
32             graph.extend_with_edges(
33                 state
34                     .shifts
35                     .iter()
36                     .map(|(terminal, &state)| (Symbol::Terminal(terminal.clone()), state))
37                     .chain(
38                         state
39                             .gotos
40                             .iter()
41                             .map(|(nt, &state)| (Symbol::Nonterminal(nt.clone()), state)),
42                     )
43                     .map(|(symbol, successor)| {
44                         (NodeIndex::new(i), NodeIndex::new(successor.0), symbol)
45                     }),
46             );
47         }
48 
49         StateGraph { graph }
50     }
51 
52     /// Given a list of symbols `[X, Y, Z]`, traces back from
53     /// `initial_state_index` to find the set of states whence we
54     /// could have arrived at `initial_state_index` after pushing `X`,
55     /// `Y`, and `Z`.
trace_back( &self, initial_state_index: StateIndex, initial_symbols: &[Symbol], ) -> Vec<StateIndex>56     pub fn trace_back(
57         &self,
58         initial_state_index: StateIndex,
59         initial_symbols: &[Symbol],
60     ) -> Vec<StateIndex> {
61         let mut stack = vec![(initial_state_index, initial_symbols)];
62         let mut result = vec![];
63         while let Some((state_index, symbols)) = stack.pop() {
64             if let Some((head, tail)) = symbols.split_last() {
65                 stack.extend(
66                     self.graph
67                         .edges_directed(NodeIndex::new(state_index.0), EdgeDirection::Incoming)
68                         .filter(|edge| edge.weight() == head)
69                         .map(|edge| (StateIndex(edge.source().index()), tail)),
70                 );
71             } else {
72                 result.push(state_index);
73             }
74         }
75         result.sort();
76         result.dedup();
77         result
78     }
79 
successors(&self, state_index: StateIndex) -> Vec<StateIndex>80     pub fn successors(&self, state_index: StateIndex) -> Vec<StateIndex> {
81         self.graph
82             .edges_directed(NodeIndex::new(state_index.0), EdgeDirection::Outgoing)
83             .map(|edge| StateIndex(edge.target().index()))
84             .collect()
85     }
86 
predecessors(&self, state_index: StateIndex, symbol: Symbol) -> Vec<StateIndex>87     pub fn predecessors(&self, state_index: StateIndex, symbol: Symbol) -> Vec<StateIndex> {
88         self.graph
89             .edges_directed(NodeIndex::new(state_index.0), EdgeDirection::Incoming)
90             .filter(|edge| *edge.weight() == symbol)
91             .map(|edge| StateIndex(edge.source().index()))
92             .collect()
93     }
94 }
95