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

//! Code to trace out a single lane, collecting information into the
//! lane table as we go.

use crate::collections::Set;
use crate::grammar::repr::*;
use crate::lr1::core::*;
use crate::lr1::first::FirstSets;
use crate::lr1::lookahead::*;
use crate::lr1::state_graph::StateGraph;

use super::table::{ConflictIndex, LaneTable};

pub struct LaneTracer<'trace, 'grammar: 'trace, L: Lookahead + 'trace> {
    states: &'trace [State<'grammar, L>],
    first_sets: &'trace FirstSets,
    state_graph: &'trace StateGraph,
    table: LaneTable<'grammar>,
    start_nt: NonterminalString,
}

impl<'trace, 'grammar, L: Lookahead> LaneTracer<'trace, 'grammar, L> {
    pub fn new(
        grammar: &'grammar Grammar,
        start_nt: NonterminalString,
        states: &'trace [State<'grammar, L>],
        first_sets: &'trace FirstSets,
        state_graph: &'trace StateGraph,
        conflicts: usize,
    ) -> Self {
        LaneTracer {
            states,
            first_sets,
            state_graph,
            start_nt,
            table: LaneTable::new(grammar, conflicts),
        }
    }

    pub fn into_table(self) -> LaneTable<'grammar> {
        self.table
    }

    pub fn start_trace(
        &mut self,
        state: StateIndex,
        conflict: ConflictIndex,
        action: Action<'grammar>,
    ) {
        let mut visited_set = Set::default();

        // if the conflict item is a "shift" item, then the context
        // is always the terminal to shift (and conflicts only arise
        // around shifting terminal, so it must be a terminal)
        match action {
            Action::Shift(term, _) => {
                let mut token_set = TokenSet::new();
                token_set.insert(Token::Terminal(term));
                self.table.add_lookahead(state, conflict, &token_set);
            }

            Action::Reduce(prod) => {
                let item = Item::lr0(prod, prod.symbols.len());
                self.continue_trace(state, conflict, item, &mut visited_set);
            }
        }
    }

    fn continue_trace(
        &mut self,
        state: StateIndex,
        conflict: ConflictIndex,
        item: Lr0Item<'grammar>,
        visited: &mut Set<(StateIndex, Lr0Item<'grammar>)>,
    ) {
        if !visited.insert((state, item)) {
            return;
        }

        if item.index > 0 {
            // This item was reached by shifting some symbol.  We need
            // to unshift that symbol, which means we walk backwards
            // to predecessors of `state` in the state graph.
            //
            // Example:
            //
            //     X = ...p T (*) ...s
            //
            // Here we would be "unshifting" T, which means we will
            // walk to predecessors of the current state that were
            // reached by shifting T. Those predecessors will contain
            // an item like `X = ...p (*) T ...s`, which we will then
            // process in turn.
            let unshifted_item = Item {
                index: item.index - 1,
                ..item
            };
            let shifted_symbol = &item.production.symbols[unshifted_item.index];
            let predecessors = self.state_graph.predecessors(state, shifted_symbol);
            for predecessor in predecessors {
                self.table.add_successor(predecessor, state);
                self.continue_trace(predecessor, conflict, unshifted_item, visited);
            }
            return;
        }

        // Either: we are in the start state, or this item was
        // reached by an epsilon transition. We have to
        // "unepsilon", which means that we search elsewhere in
        // the state for where the epsilon transition could have
        // come from.
        //
        // Example:
        //
        //     X = (*) ...
        //
        // We will search for other items in the same state like:
        //
        //     Y = ...p (*) X ...s
        //
        // We can then insert `FIRST(...s)` as lookahead for
        // `conflict`. If `...s` may derive epsilon, though, we
        // have to recurse and search with the previous item.

        let state_items = &self.states[state.0].items.vec;
        let nonterminal = &item.production.nonterminal;
        if *nonterminal == self.start_nt {
            // as a special case, if the `X` above is the special, synthetic
            // start-terminal, then the only thing that comes afterwards is EOF.
            self.table.add_lookahead(state, conflict, &TokenSet::eof());
        }

        // NB: Under the normal LR terms, the start nonterminal will
        // only have one production like `X' = X`, in which case this
        // loop is useless, but sometimes in tests we don't observe
        // that restriction, so do it anyway.
        for pred_item in state_items
            .iter()
            .filter(|i| i.can_shift_nonterminal(nonterminal))
        {
            let symbol_sets = pred_item.symbol_sets();
            let mut first = self.first_sets.first0(symbol_sets.suffix);
            let derives_epsilon = first.take_eof();
            self.table.add_lookahead(state, conflict, &first);
            if derives_epsilon {
                self.continue_trace(state, conflict, pred_item.to_lr0(), visited);
            }
        }
    }
}