1 use grammar::repr::*;
2 use lr1::core::*;
3 
4 use super::trace_graph::*;
5 use super::Tracer;
6 
7 #[cfg(test)]
8 mod test;
9 
10 /// A backtrace explaining how a particular shift:
11 ///
12 ///    X = ...p (*) Token ...
13 ///
14 /// came to be in the list of items for some state S. This backtrace
15 /// always has a particular form. First, we can walk back over the
16 /// prefix, which will bring us to some set of states S1 all of which
17 /// contain the same item, but with the cursor at the front:
18 ///
19 ///    X = (*) ...p Token ...
20 ///
21 /// Then we can walk back within those states some number of epsilon
22 /// moves, traversing nonterminals of the form:
23 ///
24 ///    Y = (*) X ...s
25 ///
26 /// (Note that each nonterminal `Y` may potentially have many
27 /// productions of this form. I am not sure yet if they all matter or
28 /// not.)
29 ///
30 /// Finally, either we are in the start state, or else we reach some
31 /// production of the form:
32 ///
33 ///    Z = ...p (*) Y ...s
34 ///
35 /// Ultimately this "trace" is best represented as a DAG. The problem
36 /// is that some of those nonterminals could, for example, be
37 /// optional.
38 
39 impl<'trace, 'grammar> Tracer<'trace, 'grammar> {
backtrace_shift( mut self, item_state: StateIndex, item: LR0Item<'grammar>, ) -> TraceGraph<'grammar>40     pub fn backtrace_shift(
41         mut self,
42         item_state: StateIndex,
43         item: LR0Item<'grammar>,
44     ) -> TraceGraph<'grammar> {
45         let symbol_sets = item.symbol_sets();
46 
47         // The states `S`
48         let pred_states = self.state_graph.trace_back(item_state, symbol_sets.prefix);
49 
50         // Add the edge `[X] -{...p,Token,...s}-> [X = ...p (*) Token ...s]`
51         self.trace_graph
52             .add_edge(item.production.nonterminal.clone(), item, symbol_sets);
53 
54         for pred_state in pred_states {
55             self.trace_epsilon_edges(pred_state, &item.production.nonterminal);
56         }
57 
58         self.trace_graph
59     }
60 
61     // Because item.index is 0, we know we are at an index
62     // like:
63     //
64     //     Y = (*) ...
65     //
66     // This can only arise if `Y` is the start nonterminal
67     // or if there is an epsilon move from another item
68     // like:
69     //
70     //     Z = ...p (*) Y ...
71     //
72     // So search for items like Z.
trace_epsilon_edges(&mut self, item_state: StateIndex, nonterminal: &NonterminalString)73     fn trace_epsilon_edges(&mut self, item_state: StateIndex, nonterminal: &NonterminalString) // "Y"
74     {
75         if self.visited_set.insert((item_state, nonterminal.clone())) {
76             for pred_item in self.states[item_state.0].items.vec.iter() {
77                 if pred_item.can_shift_nonterminal(nonterminal) {
78                     if pred_item.index > 0 {
79                         // Add an edge:
80                         //
81                         //     [Z = ...p (*) Y ...s] -(...p,Y,...s)-> [Y]
82                         self.trace_graph.add_edge(
83                             pred_item,
84                             nonterminal.clone(),
85                             pred_item.symbol_sets(),
86                         );
87                     } else {
88                         // Trace back any incoming edges to [Z = ...p (*) Y ...].
89                         let pred_nonterminal = &pred_item.production.nonterminal;
90                         self.trace_graph.add_edge(
91                             pred_nonterminal.clone(),
92                             nonterminal.clone(),
93                             pred_item.symbol_sets(),
94                         );
95                         self.trace_epsilon_edges(item_state, pred_nonterminal);
96                     }
97                 }
98             }
99         }
100     }
101 }
102