lrtable/
statetable.rs

1#![allow(clippy::derive_partial_eq_without_eq)]
2use std::{
3    cmp::Ordering,
4    collections::hash_map::HashMap,
5    error::Error,
6    fmt::{self, Debug, Write},
7    hash::Hash,
8    marker::PhantomData,
9};
10
11#[cfg(feature = "bincode")]
12use bincode::{Decode, Encode};
13use cfgrammar::{
14    yacc::{AssocKind, YaccGrammar},
15    PIdx, RIdx, Symbol, TIdx,
16};
17use num_traits::{AsPrimitive, PrimInt, Unsigned};
18#[cfg(feature = "serde")]
19use serde::{Deserialize, Serialize};
20use sparsevec::SparseVec;
21use vob::{IterSetBits, Vob};
22
23use crate::{stategraph::StateGraph, StIdx};
24
25#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
26#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
27#[derive(Debug)]
28pub struct Conflicts<StorageT> {
29    reduce_reduce: Vec<(
30        TIdx<StorageT>,
31        PIdx<StorageT>,
32        PIdx<StorageT>,
33        StIdx<StorageT>,
34    )>,
35    shift_reduce: Vec<(TIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)>,
36}
37
38impl<StorageT: 'static + Hash + PrimInt + Unsigned> Conflicts<StorageT>
39where
40    usize: AsPrimitive<StorageT>,
41{
42    /// Return an iterator over all reduce/reduce conflicts.
43    pub fn rr_conflicts(
44        &self,
45    ) -> impl Iterator<
46        Item = &(
47            TIdx<StorageT>,
48            PIdx<StorageT>,
49            PIdx<StorageT>,
50            StIdx<StorageT>,
51        ),
52    > {
53        self.reduce_reduce.iter()
54    }
55
56    /// Return an iterator over all shift/reduce conflicts.
57    pub fn sr_conflicts(
58        &self,
59    ) -> impl Iterator<Item = &(TIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)> {
60        self.shift_reduce.iter()
61    }
62
63    /// How many reduce/reduce conflicts are there?
64    pub fn rr_len(&self) -> usize {
65        self.reduce_reduce.len()
66    }
67
68    /// How many shift/reduce conflicts are there?
69    pub fn sr_len(&self) -> usize {
70        self.shift_reduce.len()
71    }
72
73    /// Returns a pretty-printed version of the conflicts.
74    #[deprecated(since = "0.10.1", note = "Please use pp_rr() and pp_sr() instead")]
75    pub fn pp(&self, grm: &YaccGrammar<StorageT>) -> String {
76        let mut s = String::new();
77        s.push_str(&self.pp_sr(grm));
78        s.push_str(&self.pp_rr(grm));
79        s
80    }
81
82    /// Returns a pretty-printed version of the reduce/reduce conflicts.
83    pub fn pp_rr(&self, grm: &YaccGrammar<StorageT>) -> String {
84        let mut s = String::new();
85        if self.rr_len() > 0 {
86            s.push_str("Reduce/Reduce conflicts:\n");
87            for (tidx, pidx, r_pidx, stidx) in self.rr_conflicts() {
88                writeln!(
89                    s,
90                    "   State {:?} (lookahead {}): Reduce({}) / Reduce({})",
91                    usize::from(*stidx),
92                    grm.token_name(*tidx).unwrap_or("$"),
93                    grm.pp_prod(*pidx),
94                    grm.pp_prod(*r_pidx)
95                )
96                .ok();
97            }
98        }
99        s
100    }
101
102    /// Returns a pretty-printed version of the shift/reduce conflicts.
103    pub fn pp_sr(&self, grm: &YaccGrammar<StorageT>) -> String {
104        let mut s = String::new();
105        if self.sr_len() > 0 {
106            s.push_str("Shift/Reduce conflicts:\n");
107            for (tidx, pidx, stidx) in self.sr_conflicts() {
108                writeln!(
109                    s,
110                    "   State {:?}: Shift(\"{}\") / Reduce({})",
111                    usize::from(*stidx),
112                    grm.token_name(*tidx).unwrap(),
113                    grm.pp_prod(*pidx)
114                )
115                .ok();
116            }
117        }
118        s
119    }
120}
121
122/// The various different possible Yacc parser errors.
123#[derive(Debug)]
124#[non_exhaustive]
125pub enum StateTableErrorKind<StorageT> {
126    AcceptReduceConflict(Option<PIdx<StorageT>>),
127}
128
129/// Any error from the Yacc parser returns an instance of this struct.
130#[derive(Debug)]
131#[non_exhaustive]
132pub struct StateTableError<StorageT> {
133    pub kind: StateTableErrorKind<StorageT>,
134    pub pidx: PIdx<StorageT>,
135}
136
137impl<StorageT: Debug> Error for StateTableError<StorageT> {}
138
139impl<StorageT> fmt::Display for StateTableError<StorageT> {
140    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
141        let s = match self.kind {
142            StateTableErrorKind::AcceptReduceConflict(_) => "Accept/reduce conflict",
143        };
144        write!(f, "{}", s)
145    }
146}
147
148/// A representation of a `StateTable` for a grammar. `actions` and `gotos` are split into two
149/// separate hashmaps, rather than a single table, due to the different types of their values.
150#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
151#[cfg_attr(feature = "bincode", derive(Encode, Decode))]
152pub struct StateTable<StorageT> {
153    actions: SparseVec<usize>,
154    state_actions: Vob<u64>,
155    gotos: SparseVec<usize>,
156    start_state: StIdx<StorageT>,
157    core_reduces: Vob<u64>,
158    state_shifts: Vob<u64>,
159    reduce_states: Vob<u64>,
160    prods_len: PIdx<StorageT>,
161    tokens_len: TIdx<StorageT>,
162    conflicts: Option<Conflicts<StorageT>>,
163    #[cfg(test)]
164    final_state: StIdx<StorageT>,
165}
166
167#[derive(Clone, Copy, Debug, PartialEq)]
168#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
169pub enum Action<StorageT> {
170    /// Shift to state X in the statetable.
171    Shift(StIdx<StorageT>),
172    /// Reduce production X in the grammar.
173    Reduce(PIdx<StorageT>),
174    /// Accept this input.
175    Accept,
176    /// No valid action.
177    Error,
178}
179
180const SHIFT: usize = 1;
181const REDUCE: usize = 2;
182const ACCEPT: usize = 3;
183const ERROR: usize = 0;
184
185impl<StorageT: 'static + Hash + PrimInt + Unsigned> StateTable<StorageT>
186where
187    usize: AsPrimitive<StorageT>,
188{
189    pub fn new(
190        grm: &YaccGrammar<StorageT>,
191        sg: &StateGraph<StorageT>,
192    ) -> Result<Self, StateTableError<StorageT>> {
193        let mut state_actions = Vob::<u64>::from_elem_with_storage_type(
194            false,
195            usize::from(sg.all_states_len())
196                .checked_mul(usize::from(grm.tokens_len()))
197                .unwrap(),
198        );
199        let maxa = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
200        let maxg = usize::from(grm.rules_len()) * usize::from(sg.all_states_len());
201        // We only have usize-2 bits to store state IDs and rule indexes
202        assert!(usize::from(sg.all_states_len()) < (usize::MAX - 4));
203        assert!(usize::from(grm.rules_len()) < (usize::MAX - 4));
204        let mut actions: Vec<usize> = vec![0; maxa];
205
206        // Since 0 is reserved for the error type, and states are encoded by adding 1, we can only
207        // store max_value - 1 states within the goto table
208        assert!(sg.all_states_len().as_storaget() < StorageT::max_value() - StorageT::one());
209        let mut gotos: Vec<usize> = vec![0; maxg];
210
211        // Store automatically resolved conflicts, so we can print them out later
212        let mut reduce_reduce = Vec::new();
213        let mut shift_reduce = Vec::new();
214        let mut final_state = None;
215
216        for (stidx, state) in sg
217            .iter_closed_states()
218            .enumerate()
219            // Since stidx comes from the stategraph it can be safely cast to StorageT.
220            .map(|(x, y)| (StIdx(x.as_()), y))
221        {
222            // Populate reduce and accepts
223            for (&(pidx, dot), ctx) in &state.items {
224                if dot < grm.prod_len(pidx) {
225                    continue;
226                }
227                for tidx in ctx.iter_set_bits(..) {
228                    let off = actions_offset(
229                        grm.tokens_len(),
230                        stidx,
231                        // Since ctx is exactly tokens_len bits long, the call
232                        // to as_ is safe.
233                        TIdx(tidx.as_()),
234                    );
235                    state_actions.set(off, true);
236                    match StateTable::decode(actions[off]) {
237                        Action::Reduce(r_pidx) => {
238                            if pidx == grm.start_prod() && tidx == usize::from(grm.eof_token_idx())
239                            {
240                                return Err(StateTableError {
241                                    kind: StateTableErrorKind::AcceptReduceConflict(Some(r_pidx)),
242                                    pidx,
243                                });
244                            }
245                            // By default, Yacc resolves reduce/reduce conflicts in favour
246                            // of the earlier production in the grammar.
247                            match pidx.cmp(&r_pidx) {
248                                Ordering::Less => {
249                                    reduce_reduce.push((TIdx(tidx.as_()), pidx, r_pidx, stidx));
250                                    actions[off] = StateTable::encode(Action::Reduce(pidx));
251                                }
252                                Ordering::Greater => {
253                                    reduce_reduce.push((TIdx(tidx.as_()), r_pidx, pidx, stidx))
254                                }
255                                Ordering::Equal => (),
256                            }
257                        }
258                        Action::Accept => {
259                            return Err(StateTableError {
260                                kind: StateTableErrorKind::AcceptReduceConflict(None),
261                                pidx,
262                            });
263                        }
264                        Action::Error => {
265                            if pidx == grm.start_prod() && tidx == usize::from(grm.eof_token_idx())
266                            {
267                                assert!(final_state.is_none());
268                                final_state = Some(stidx);
269                                actions[off] = StateTable::encode(Action::Accept);
270                            } else {
271                                actions[off] = StateTable::encode(Action::Reduce(pidx));
272                            }
273                        }
274                        _ => panic!("Internal error"),
275                    }
276                }
277            }
278
279            let nt_len = grm.rules_len();
280            for (&sym, ref_stidx) in sg.edges(stidx) {
281                match sym {
282                    Symbol::Rule(s_ridx) => {
283                        // Populate gotos
284                        let off = (usize::from(stidx) * usize::from(nt_len)) + usize::from(s_ridx);
285                        debug_assert!(gotos[off] == 0);
286                        // Since 0 is reserved for no entry, encode states by adding 1
287                        gotos[off] = usize::from(*ref_stidx) + 1;
288                    }
289                    Symbol::Token(s_tidx) => {
290                        // Populate shifts
291                        let off = actions_offset(grm.tokens_len(), stidx, s_tidx);
292                        state_actions.set(off, true);
293                        match StateTable::decode(actions[off]) {
294                            Action::Shift(x) => assert!(*ref_stidx == x),
295                            Action::Reduce(r_pidx) => {
296                                resolve_shift_reduce(
297                                    grm,
298                                    &mut actions,
299                                    off,
300                                    s_tidx,
301                                    r_pidx,
302                                    *ref_stidx,
303                                    &mut shift_reduce,
304                                    stidx,
305                                );
306                            }
307                            Action::Accept => panic!("Internal error"),
308                            Action::Error => {
309                                actions[off] = StateTable::encode(Action::Shift(*ref_stidx));
310                            }
311                        }
312                    }
313                }
314            }
315        }
316        assert!(final_state.is_some());
317
318        let mut nt_depth = HashMap::new();
319        let mut core_reduces = Vob::<u64>::from_elem_with_storage_type(
320            false,
321            usize::from(sg.all_states_len())
322                .checked_mul(usize::from(grm.prods_len()))
323                .unwrap(),
324        );
325        let mut state_shifts = Vob::<u64>::from_elem_with_storage_type(
326            false,
327            usize::from(sg.all_states_len())
328                .checked_mul(usize::from(grm.tokens_len()))
329                .unwrap(),
330        );
331        let mut reduce_states =
332            Vob::<u64>::from_elem_with_storage_type(false, usize::from(sg.all_states_len()));
333        for stidx in sg.iter_stidxs() {
334            nt_depth.clear();
335            let mut only_reduces = true;
336            for tidx in grm.iter_tidxs() {
337                let off = actions_offset(grm.tokens_len(), stidx, tidx);
338                match StateTable::decode(actions[off]) {
339                    Action::Reduce(pidx) => {
340                        let prod_len = grm.prod(pidx).len();
341                        let ridx = grm.prod_to_rule(pidx);
342                        nt_depth.insert((ridx, prod_len), pidx);
343                    }
344                    Action::Shift(_) => {
345                        only_reduces = false;
346                        state_shifts.set(off, true);
347                    }
348                    Action::Accept => {
349                        only_reduces = false;
350                    }
351                    Action::Error => (),
352                }
353            }
354
355            let mut distinct_reduces = 0; // How many distinct reductions do we have?
356            for &pidx in nt_depth.values() {
357                let off = usize::from(stidx)
358                    .checked_mul(usize::from(grm.prods_len()))
359                    .unwrap()
360                    .checked_add(usize::from(pidx))
361                    .unwrap();
362                if core_reduces.set(off, true) {
363                    distinct_reduces += 1;
364                }
365            }
366
367            if only_reduces && distinct_reduces == 1 {
368                reduce_states.set(usize::from(stidx), true);
369            }
370        }
371
372        let actions_sv = SparseVec::<usize>::from(&actions, 0, usize::from(grm.tokens_len()));
373        let gotos_sv = SparseVec::<usize>::from(&gotos, 0, usize::from(grm.rules_len()));
374
375        let conflicts = if !(reduce_reduce.is_empty() && shift_reduce.is_empty()) {
376            Some(Conflicts {
377                reduce_reduce,
378                shift_reduce,
379            })
380        } else {
381            None
382        };
383
384        Ok(StateTable {
385            actions: actions_sv,
386            state_actions,
387            gotos: gotos_sv,
388            start_state: sg.start_state(),
389            state_shifts,
390            core_reduces,
391            reduce_states,
392            prods_len: grm.prods_len(),
393            tokens_len: grm.tokens_len(),
394            conflicts,
395            #[cfg(test)]
396            final_state: final_state.unwrap(),
397        })
398    }
399
400    fn decode(bits: usize) -> Action<StorageT> {
401        let action = bits & 0b11;
402        let val = bits >> 2;
403
404        match action {
405            SHIFT => {
406                // Since val was originally stored in an StIdxStorageT, we know that it's safe to
407                // cast it back to an StIdxStorageT here.
408                Action::Shift(StIdx(val.as_()))
409            }
410            REDUCE => Action::Reduce(PIdx(val.as_())),
411            ACCEPT => Action::Accept,
412            ERROR => Action::Error,
413            _ => unreachable!(),
414        }
415    }
416
417    fn encode(action: Action<StorageT>) -> usize {
418        match action {
419            Action::Shift(stidx) => SHIFT | (usize::from(stidx) << 2),
420            Action::Reduce(ridx) => REDUCE | (usize::from(ridx) << 2),
421            Action::Accept => ACCEPT,
422            Action::Error => ERROR,
423        }
424    }
425
426    /// Return the action for `stidx` and `sym`, or `None` if there isn't any.
427    pub fn action(&self, stidx: StIdx<StorageT>, tidx: TIdx<StorageT>) -> Action<StorageT> {
428        StateTable::decode(
429            self.actions
430                .get(usize::from(stidx), usize::from(tidx))
431                .unwrap(),
432        )
433    }
434
435    /// Return an iterator over the indexes of all non-empty actions of `stidx`.
436    pub fn state_actions(&self, stidx: StIdx<StorageT>) -> StateActionsIterator<StorageT> {
437        let start = usize::from(stidx) * usize::from(self.tokens_len);
438        let end = start + usize::from(self.tokens_len);
439        StateActionsIterator {
440            iter: self.state_actions.iter_set_bits(start..end),
441            start,
442            phantom: PhantomData,
443        }
444    }
445
446    /// Return an iterator over the indexes of all shift actions of `stidx`. By definition this
447    /// is a subset of the indexes produced by [`state_actions`](#method.state_actions).
448    pub fn state_shifts(&self, stidx: StIdx<StorageT>) -> StateActionsIterator<StorageT> {
449        let start = usize::from(stidx) * usize::from(self.tokens_len);
450        let end = start + usize::from(self.tokens_len);
451        StateActionsIterator {
452            iter: self.state_shifts.iter_set_bits(start..end),
453            start,
454            phantom: PhantomData,
455        }
456    }
457
458    /// Does the state `stidx` 1) only contain reduce (and error) actions 2) do those
459    /// reductions all reduce to the same production?
460    pub fn reduce_only_state(&self, stidx: StIdx<StorageT>) -> bool {
461        self.reduce_states[usize::from(stidx)]
462    }
463
464    /// Return an iterator over a set of "core" reduces of `stidx`. This is a minimal set of
465    /// reduce actions which explore all possible reductions from a given state. Note that these
466    /// are chosen non-deterministically from a set of equivalent reduce actions: you must not rely
467    /// on always seeing the same reduce actions. For example if a state has these three items:
468    ///
469    ///   [E -> a ., $]
470    ///   [E -> b ., $]
471    ///   [F -> c ., $]
472    ///
473    /// then the core reduces will be:
474    ///
475    ///   One of: [E -> a., $] or [E -> b., $]
476    ///   And:    [F -> c., $]
477    ///
478    /// since the two [E -> ...] items both have the same effects on a parse stack.
479    pub fn core_reduces(&self, stidx: StIdx<StorageT>) -> CoreReducesIterator<StorageT> {
480        let start = usize::from(stidx) * usize::from(self.prods_len);
481        let end = start + usize::from(self.prods_len);
482        CoreReducesIterator {
483            iter: self.core_reduces.iter_set_bits(start..end),
484            start,
485            phantom: PhantomData,
486        }
487    }
488
489    /// Return the goto state for `stidx` and `ridx`, or `None` if there isn't any.
490    pub fn goto(&self, stidx: StIdx<StorageT>, ridx: RIdx<StorageT>) -> Option<StIdx<StorageT>> {
491        // Goto entries are encoded by adding 1 to their value, while 0 is reserved for no entry
492        // (i.e. error)
493        match self.gotos.get(usize::from(stidx), usize::from(ridx)) {
494            Some(0) => None,
495            // gotos can only contain state id's which we know can fit into StIdxStorageT so this
496            // cast is safe
497            Some(i) => Some(StIdx((i - 1).as_())),
498            None => unreachable!(),
499        }
500    }
501
502    /// Return this state table's start state.
503    pub fn start_state(&self) -> StIdx<StorageT> {
504        self.start_state
505    }
506
507    /// Return a struct containing all conflicts or `None` if there aren't any.
508    pub fn conflicts(&self) -> Option<&Conflicts<StorageT>> {
509        self.conflicts.as_ref()
510    }
511}
512
513fn actions_offset<StorageT: PrimInt + Unsigned>(
514    tokens_len: TIdx<StorageT>,
515    stidx: StIdx<StorageT>,
516    tidx: TIdx<StorageT>,
517) -> usize {
518    usize::from(stidx) * usize::from(tokens_len) + usize::from(tidx)
519}
520
521pub struct StateActionsIterator<'a, StorageT> {
522    iter: IterSetBits<'a, u64>,
523    start: usize,
524    phantom: PhantomData<StorageT>,
525}
526
527impl<StorageT: 'static + PrimInt + Unsigned> Iterator for StateActionsIterator<'_, StorageT>
528where
529    usize: AsPrimitive<StorageT>,
530{
531    type Item = TIdx<StorageT>;
532
533    fn next(&mut self) -> Option<TIdx<StorageT>> {
534        // Since self.iter's IterSetBits range as exactly tokens_len long, by definition `i -
535        // self.start` fits into StorageT and thus the as_ call here is safe.
536        self.iter.next().map(|i| TIdx((i - self.start).as_()))
537    }
538}
539
540pub struct CoreReducesIterator<'a, StorageT> {
541    iter: IterSetBits<'a, u64>,
542    start: usize,
543    phantom: PhantomData<StorageT>,
544}
545
546impl<StorageT: 'static + PrimInt + Unsigned> Iterator for CoreReducesIterator<'_, StorageT>
547where
548    usize: AsPrimitive<StorageT>,
549{
550    type Item = PIdx<StorageT>;
551
552    fn next(&mut self) -> Option<PIdx<StorageT>> {
553        // Since self.iter's IterSetBits range as exactly tokens_len long, by definition `i -
554        // self.start` fits into StorageT and thus the as_ call here is safe.
555        self.iter.next().map(|i| PIdx((i - self.start).as_()))
556    }
557}
558
559fn resolve_shift_reduce<StorageT: 'static + Hash + PrimInt + Unsigned>(
560    grm: &YaccGrammar<StorageT>,
561    actions: &mut [usize],
562    off: usize,
563    tidx: TIdx<StorageT>,
564    pidx: PIdx<StorageT>,
565    stidx: StIdx<StorageT>, // State we want to shift to
566    shift_reduce: &mut Vec<(TIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)>,
567    conflict_stidx: StIdx<StorageT>, // State in which the conflict occured
568) where
569    usize: AsPrimitive<StorageT>,
570{
571    let tidx_prec = grm.token_precedence(tidx);
572    let pidx_prec = grm.prod_precedence(pidx);
573    match (tidx_prec, pidx_prec) {
574        (_, None) | (None, _) => {
575            // If the token and production don't both have precedences, we use Yacc's default
576            // resolution, which is in favour of the shift.
577            actions[off] = StateTable::encode(Action::Shift(stidx));
578            shift_reduce.push((tidx, pidx, conflict_stidx));
579        }
580        (Some(token_prec), Some(prod_prec)) => {
581            match token_prec.level.cmp(&prod_prec.level) {
582                Ordering::Equal => {
583                    // Both token and production have the same level precedence, so we need to look
584                    // at the precedence kind.
585                    match (token_prec.kind, prod_prec.kind) {
586                        (AssocKind::Left, AssocKind::Left) => {
587                            // Left associativity is resolved in favour of the reduce (i.e. leave
588                            // as-is).
589                        }
590                        (AssocKind::Right, AssocKind::Right) => {
591                            // Right associativity is resolved in favour of the shift.
592                            actions[off] = StateTable::encode(Action::Shift(stidx));
593                        }
594                        (AssocKind::Nonassoc, AssocKind::Nonassoc) => {
595                            // Nonassociativity leads to a run-time parsing error, so we need to
596                            // remove the action entirely.
597                            actions[off] = StateTable::encode(Action::Error);
598                        }
599                        (_, _) => {
600                            panic!("Not supported.");
601                        }
602                    }
603                }
604                Ordering::Greater => {
605                    // The token has higher level precedence, so resolve in favour of shift.
606                    actions[off] = StateTable::encode(Action::Shift(stidx));
607                }
608                Ordering::Less => {
609                    // If token_lev < prod_lev, then the production has higher level precedence and
610                    // we keep the reduce as-is.
611                }
612            }
613        }
614    }
615}
616
617#[cfg(test)]
618mod test {
619    use super::{Action, StateTable, StateTableError, StateTableErrorKind};
620    use crate::{pager::pager_stategraph, StIdx};
621    use cfgrammar::{
622        yacc::{
623            ast::{self, ASTWithValidityInfo},
624            YaccGrammar, YaccKind, YaccKindResolver, YaccOriginalActionKind,
625        },
626        PIdx, Span, Symbol, TIdx,
627    };
628    use std::collections::HashSet;
629
630    #[test]
631    #[rustfmt::skip]
632    fn test_statetable() {
633        // Taken from p19 of www.cs.umd.edu/~mvz/cmsc430-s07/M10lr.pdf
634        let grm = YaccGrammar::new(
635            YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)),
636            "
637            %start Expr
638            %%
639            Expr : Term '-' Expr | Term;
640            Term : Factor '*' Term | Factor;
641            Factor : 'id';
642          "
643        ).unwrap();
644        let sg = pager_stategraph(&grm);
645        assert_eq!(sg.all_states_len(), StIdx(9));
646
647        let s0 = sg.start_state();
648        let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
649        let s2 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Term").unwrap())).unwrap();
650        let s3 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Factor").unwrap())).unwrap();
651        let s4 = sg.edge(s0, Symbol::Token(grm.token_idx("id").unwrap())).unwrap();
652        let s5 = sg.edge(s2, Symbol::Token(grm.token_idx("-").unwrap())).unwrap();
653        let s6 = sg.edge(s3, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
654        let s7 = sg.edge(s5, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
655        let s8 = sg.edge(s6, Symbol::Rule(grm.rule_idx("Term").unwrap())).unwrap();
656
657        let st = StateTable::new(&grm, &sg).unwrap();
658
659        // Actions
660        assert_eq!(st.actions.len(), 9*4);
661        let assert_reduce = |stidx: StIdx<_>, tidx: TIdx<_>, rule: &str, prod_off: usize| {
662            let pidx = grm.rule_to_prods(grm.rule_idx(rule).unwrap())[prod_off];
663            assert_eq!(st.action(stidx, tidx), Action::Reduce(pidx));
664        };
665
666        assert_eq!(st.action(s0, grm.token_idx("id").unwrap()), Action::Shift(s4));
667        assert_eq!(st.action(s1, grm.eof_token_idx()), Action::Accept);
668        assert_eq!(st.final_state, s1);
669        assert_eq!(st.action(s2, grm.token_idx("-").unwrap()), Action::Shift(s5));
670        assert_reduce(s2, grm.eof_token_idx(), "Expr", 1);
671        assert_reduce(s3, grm.token_idx("-").unwrap(), "Term", 1);
672        assert_eq!(st.action(s3, grm.token_idx("*").unwrap()), Action::Shift(s6));
673        assert_reduce(s3, grm.eof_token_idx(), "Term", 1);
674        assert_reduce(s4, grm.token_idx("-").unwrap(), "Factor", 0);
675        assert_reduce(s4, grm.token_idx("*").unwrap(), "Factor", 0);
676        assert_reduce(s4, grm.eof_token_idx(), "Factor", 0);
677        assert_eq!(st.action(s5, grm.token_idx("id").unwrap()), Action::Shift(s4));
678        assert_eq!(st.action(s6, grm.token_idx("id").unwrap()), Action::Shift(s4));
679        assert_reduce(s7, grm.eof_token_idx(), "Expr", 0);
680        assert_reduce(s8, grm.token_idx("-").unwrap(), "Term", 0);
681        assert_reduce(s8, grm.eof_token_idx(), "Term", 0);
682
683        let mut s4_actions = HashSet::new();
684        s4_actions.extend([grm.token_idx("-").unwrap(),
685                            grm.token_idx("*").unwrap(),
686                            grm.eof_token_idx()]);
687        assert_eq!(st.state_actions(s4).collect::<HashSet<_>>(), s4_actions);
688
689        let s2_state_shifts = &[grm.token_idx("-").unwrap()]
690                               .iter()
691                               .cloned()
692                               .collect::<HashSet<_>>();
693        assert_eq!(st.state_shifts(s2).collect::<HashSet<_>>(), *s2_state_shifts);
694
695        let s4_core_reduces = &[grm.rule_to_prods(grm.rule_idx("Factor").unwrap())[0]]
696                              .iter()
697                              .cloned()
698                              .collect::<HashSet<_>>();
699        assert_eq!(st.core_reduces(s4).collect::<HashSet<_>>(), *s4_core_reduces);
700
701        // Gotos
702        assert_eq!(st.gotos.len(), 9*4);
703        assert_eq!(st.goto(s0, grm.rule_idx("Expr").unwrap()).unwrap(), s1);
704        assert_eq!(st.goto(s0, grm.rule_idx("Term").unwrap()).unwrap(), s2);
705        assert_eq!(st.goto(s0, grm.rule_idx("Factor").unwrap()).unwrap(), s3);
706        assert_eq!(st.goto(s5, grm.rule_idx("Expr").unwrap()).unwrap(), s7);
707        assert_eq!(st.goto(s5, grm.rule_idx("Term").unwrap()).unwrap(), s2);
708        assert_eq!(st.goto(s5, grm.rule_idx("Factor").unwrap()).unwrap(), s3);
709        assert_eq!(st.goto(s6, grm.rule_idx("Term").unwrap()).unwrap(), s8);
710        assert_eq!(st.goto(s6, grm.rule_idx("Factor").unwrap()).unwrap(), s3);
711    }
712
713    #[test]
714    #[rustfmt::skip]
715    fn test_default_reduce_reduce() {
716        let grm = YaccGrammar::new(YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)), "
717            %start A
718            %%
719            A : B 'x' | C 'x' 'x';
720            B : 'a';
721            C : 'a';
722          ").unwrap();
723        let sg = pager_stategraph(&grm);
724        let st = StateTable::new(&grm, &sg).unwrap();
725
726        let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
727        assert_eq!(st.actions.len(), len);
728
729        // We only extract the states necessary to test those rules affected by the reduce/reduce.
730        let s0 = sg.start_state();
731        let s4 = sg.edge(s0, Symbol::Token(grm.token_idx("a").unwrap())).unwrap();
732
733        assert_eq!(st.action(s4, grm.token_idx("x").unwrap()),
734                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("B").unwrap())[0]));
735    }
736
737    #[test]
738    #[rustfmt::skip]
739    fn test_default_shift_reduce() {
740        let grm = YaccGrammar::new(YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)), "
741            %start Expr
742            %%
743            Expr : Expr '+' Expr
744                 | Expr '*' Expr
745                 | 'id' ;
746          ").unwrap();
747        let sg = pager_stategraph(&grm);
748        let st = StateTable::new(&grm, &sg).unwrap();
749        let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
750        assert_eq!(st.actions.len(), len);
751
752        let s0 = sg.start_state();
753        let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
754        let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
755        let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
756        let s5 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
757        let s6 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
758
759        assert_eq!(st.action(s5, grm.token_idx("+").unwrap()), Action::Shift(s3));
760        assert_eq!(st.action(s5, grm.token_idx("*").unwrap()), Action::Shift(s4));
761
762        assert_eq!(st.action(s6, grm.token_idx("+").unwrap()), Action::Shift(s3));
763        assert_eq!(st.action(s6, grm.token_idx("*").unwrap()), Action::Shift(s4));
764    }
765
766    #[test]
767    #[rustfmt::skip]
768    fn test_conflict_resolution() {
769        // Example taken from p54 of Locally least-cost error repair in LR parsers, Carl Cerecke
770        let grm = YaccGrammar::new(YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)), "
771            %start S
772            %%
773            S: A 'c' 'd'
774             | B 'c' 'e';
775            A: 'a';
776            B: 'a'
777             | 'b';
778            A: 'b';
779            ").unwrap();
780        let sg = pager_stategraph(&grm);
781        let st = StateTable::new(&grm, &sg).unwrap();
782        let s0 = sg.start_state();
783        let s1 = sg.edge(s0, Symbol::Token(grm.token_idx("a").unwrap())).unwrap();
784        let s2 = sg.edge(s0, Symbol::Token(grm.token_idx("b").unwrap())).unwrap();
785
786        assert_eq!(st.action(s1, grm.token_idx("c").unwrap()),
787                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("A").unwrap())[0]));
788        assert_eq!(st.action(s2, grm.token_idx("c").unwrap()),
789                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("B").unwrap())[1]));
790    }
791
792    #[test]
793    #[rustfmt::skip]
794    fn test_left_associativity() {
795        let grm = YaccGrammar::new(YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)), "
796            %start Expr
797            %left '+'
798            %left '*'
799            %%
800            Expr : Expr '+' Expr
801                 | Expr '*' Expr
802                 | 'id' ;
803          ").unwrap();
804        let sg = pager_stategraph(&grm);
805        let st = StateTable::new(&grm, &sg).unwrap();
806        let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
807        assert_eq!(st.actions.len(), len);
808
809        let s0 = sg.start_state();
810        let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
811        let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
812        let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
813        let s5 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
814        let s6 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
815
816        assert_eq!(st.action(s5, grm.token_idx("+").unwrap()),
817                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
818        assert_eq!(st.action(s5, grm.token_idx("*").unwrap()),
819                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
820        assert_eq!(st.action(s5, grm.eof_token_idx()),
821                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
822
823        assert_eq!(st.action(s6, grm.token_idx("+").unwrap()),
824                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
825        assert_eq!(st.action(s6, grm.token_idx("*").unwrap()),
826                   Action::Shift(s4));
827        assert_eq!(st.action(s6, grm.eof_token_idx()),
828                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
829    }
830
831    #[test]
832    #[rustfmt::skip]
833    fn test_left_right_associativity() {
834        let grm = &YaccGrammar::new(YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)), "
835            %start Expr
836            %right '='
837            %left '+'
838            %left '*'
839            %%
840            Expr : Expr '+' Expr
841                 | Expr '*' Expr
842                 | Expr '=' Expr
843                 | 'id' ;
844          ").unwrap();
845        let sg = &pager_stategraph(grm);
846        let st = StateTable::new(grm, sg).unwrap();
847        let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
848        assert_eq!(st.actions.len(), len);
849
850        let s0 = sg.start_state();
851        let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
852        let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
853        let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
854        let s5 = sg.edge(s1, Symbol::Token(grm.token_idx("=").unwrap())).unwrap();
855        let s6 = sg.edge(s5, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
856        let s7 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
857        let s8 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
858
859        assert_eq!(st.action(s6, grm.token_idx("+").unwrap()),
860                   Action::Shift(s3));
861        assert_eq!(st.action(s6, grm.token_idx("*").unwrap()),
862                   Action::Shift(s4));
863        assert_eq!(st.action(s6, grm.token_idx("=").unwrap()),
864                   Action::Shift(s5));
865        assert_eq!(st.action(s6, grm.eof_token_idx()),
866                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[2]));
867
868        assert_eq!(st.action(s7, grm.token_idx("+").unwrap()),
869                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
870        assert_eq!(st.action(s7, grm.token_idx("*").unwrap()),
871                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
872        assert_eq!(st.action(s7, grm.token_idx("=").unwrap()),
873                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
874        assert_eq!(st.action(s7, grm.eof_token_idx()),
875                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
876
877        assert_eq!(st.action(s8, grm.token_idx("+").unwrap()),
878                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
879        assert_eq!(st.action(s8, grm.token_idx("*").unwrap()),
880                   Action::Shift(s4));
881        assert_eq!(st.action(s8, grm.token_idx("=").unwrap()),
882                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
883        assert_eq!(st.action(s8, grm.eof_token_idx()),
884                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
885    }
886
887    #[test]
888    #[rustfmt::skip]
889    fn test_left_right_nonassoc_associativity() {
890        let grm = YaccGrammar::new(YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)), "
891            %start Expr
892            %right '='
893            %left '+'
894            %left '*'
895            %nonassoc '~'
896            %%
897            Expr : Expr '+' Expr
898                 | Expr '*' Expr
899                 | Expr '=' Expr
900                 | Expr '~' Expr
901                 | 'id' ;
902          ").unwrap();
903        let sg = pager_stategraph(&grm);
904        let st = StateTable::new(&grm, &sg).unwrap();
905        let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
906        assert_eq!(st.actions.len(), len);
907
908        let s0 = sg.start_state();
909        let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
910        let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
911        let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
912        let s5 = sg.edge(s1, Symbol::Token(grm.token_idx("=").unwrap())).unwrap();
913        let s6 = sg.edge(s1, Symbol::Token(grm.token_idx("~").unwrap())).unwrap();
914        let s7 = sg.edge(s6, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
915        let s8 = sg.edge(s5, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
916        let s9 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
917        let s10 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
918
919        assert_eq!(st.action(s7, grm.token_idx("+").unwrap()),
920                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
921        assert_eq!(st.action(s7, grm.token_idx("*").unwrap()),
922                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
923        assert_eq!(st.action(s7, grm.token_idx("=").unwrap()),
924                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
925        assert_eq!(st.action(s7, grm.eof_token_idx()),
926                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
927
928        assert_eq!(st.action(s8, grm.token_idx("+").unwrap()),
929                   Action::Shift(s3));
930        assert_eq!(st.action(s8, grm.token_idx("*").unwrap()),
931                   Action::Shift(s4));
932        assert_eq!(st.action(s8, grm.token_idx("=").unwrap()),
933                   Action::Shift(s5));
934        assert_eq!(st.action(s8, grm.token_idx("~").unwrap()),
935                   Action::Shift(s6));
936        assert_eq!(st.action(s8, grm.eof_token_idx()),
937                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[2]));
938
939        assert_eq!(st.action(s9, grm.token_idx("+").unwrap()),
940                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
941        assert_eq!(st.action(s9, grm.token_idx("*").unwrap()),
942                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
943        assert_eq!(st.action(s9, grm.token_idx("=").unwrap()),
944                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
945        assert_eq!(st.action(s9, grm.token_idx("~").unwrap()),
946                   Action::Shift(s6));
947        assert_eq!(st.action(s9, grm.eof_token_idx()),
948                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
949
950        assert_eq!(st.action(s10, grm.token_idx("+").unwrap()),
951                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
952        assert_eq!(st.action(s10, grm.token_idx("*").unwrap()),
953                   Action::Shift(s4));
954        assert_eq!(st.action(s10, grm.token_idx("=").unwrap()),
955                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
956        assert_eq!(st.action(s10, grm.token_idx("~").unwrap()),
957                   Action::Shift(s6));
958        assert_eq!(st.action(s10, grm.eof_token_idx()),
959                   Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
960    }
961
962    #[test]
963    fn conflicts() {
964        let grm = YaccGrammar::new(
965            YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)),
966            "
967%start A
968%%
969A : 'a' 'b' | B 'b';
970B : 'a' | C;
971C : 'a';
972          ",
973        )
974        .unwrap();
975        let sg = pager_stategraph(&grm);
976        let st = StateTable::new(&grm, &sg).unwrap();
977        let conflicts = st.conflicts().unwrap();
978        assert_eq!(conflicts.sr_len(), 1);
979        assert_eq!(conflicts.rr_len(), 1);
980        assert_eq!(
981            conflicts.sr_conflicts().next().unwrap(),
982            &(
983                grm.token_idx("b").unwrap(),
984                grm.rule_to_prods(grm.rule_idx("B").unwrap())[0],
985                StIdx(2)
986            )
987        );
988        assert_eq!(
989            conflicts.rr_conflicts().next().unwrap(),
990            &(
991                TIdx(1),
992                grm.rule_to_prods(grm.rule_idx("B").unwrap())[0],
993                grm.rule_to_prods(grm.rule_idx("C").unwrap())[0],
994                StIdx(2)
995            )
996        );
997    }
998
999    #[test]
1000    fn reduce_reduce_conflict() {
1001        let grm = YaccGrammar::new(
1002            YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)),
1003            "
1004%start S
1005%%
1006S: A X | B X | A Y;
1007A: '0' ; B: '0' ; C: '0' ;
1008X: '1' ; Y: '2' ;
1009          ",
1010        )
1011        .unwrap();
1012        let sg = pager_stategraph(&grm);
1013        let st = StateTable::new(&grm, &sg).unwrap();
1014        let conflicts = st.conflicts().unwrap();
1015        assert_eq!(conflicts.sr_len(), 0);
1016
1017        // There is only one reduce/reduce conflict because state 1 has the following item set:
1018        // 1:  [B -> '0' ., {'1'}]
1019        //     [A -> '0' ., {'1', '2'}]
1020        // which causes a conflict only if the lookahead is '1' but not if the lookahead is '2'.
1021        assert_eq!(conflicts.rr_len(), 1);
1022        assert_eq!(
1023            conflicts.rr_conflicts().next().unwrap(),
1024            &(
1025                TIdx(1),
1026                grm.rule_to_prods(grm.rule_idx("A").unwrap())[0],
1027                grm.rule_to_prods(grm.rule_idx("B").unwrap())[0],
1028                StIdx(1)
1029            )
1030        );
1031    }
1032
1033    #[test]
1034    fn accept_reduce_conflict() {
1035        let grm = YaccGrammar::new(
1036            YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::GenericParseTree)),
1037            "
1038%start D
1039%%
1040D : D;
1041          ",
1042        )
1043        .unwrap();
1044        let sg = pager_stategraph(&grm);
1045        match StateTable::new(&grm, &sg) {
1046            Ok(_) => panic!("Infinitely recursive rule let through"),
1047            Err(StateTableError {
1048                kind: StateTableErrorKind::AcceptReduceConflict(_),
1049                pidx: PIdx(1),
1050            }) => (),
1051            Err(e) => panic!("Incorrect error returned {:?}", e),
1052        }
1053    }
1054
1055    #[test]
1056    fn test_accept_reduce_conflict_spans1() {
1057        let src = "%%
1058S: S | ;";
1059        let yk = YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::NoAction));
1060        let ast_validity = ASTWithValidityInfo::new(yk, src);
1061        let grm = YaccGrammar::<u32>::new_from_ast_with_validity_info(&ast_validity).unwrap();
1062        let sg = pager_stategraph(&grm);
1063        match StateTable::new(&grm, &sg) {
1064            Ok(_) => panic!("Expected accept reduce conflict"),
1065            Err(StateTableError {
1066                kind: StateTableErrorKind::AcceptReduceConflict(r_pidx),
1067                pidx,
1068            }) if pidx == PIdx(2) => {
1069                assert!(ast_validity.ast().prods.len() <= usize::from(pidx));
1070                // Note that we expect `pidx` to occur at the implicit start symbol `^`
1071                // which is not present in the AST but is present in the grammar.
1072                //
1073                // Can get a span for the rule "S", at the LHS of the rule at "S:" from that.
1074                // Which corresponds to the rule for the production within `^`.
1075                let symbols = grm.prod(pidx);
1076                assert_eq!(symbols.len(), 1);
1077                let sym = symbols.first().unwrap();
1078                match sym {
1079                    Symbol::Rule(r) => {
1080                        let span = grm.rule_name_span(*r);
1081                        assert_eq!(span, Span::new(3, 4));
1082                    }
1083                    Symbol::Token(t) => {
1084                        let span = grm.token_span(*t);
1085                        panic!("Unexpected symbol at {:?}", span);
1086                    }
1087                }
1088
1089                // A span for a production within S may be obtained from the r_pidx in this case
1090                assert!(r_pidx.is_some());
1091                let r_pidx = r_pidx.unwrap();
1092                assert!(ast_validity.ast().prods.len() >= usize::from(r_pidx));
1093                let prod = &ast_validity.ast().prods[usize::from(r_pidx)];
1094                let symbols = &prod.symbols;
1095                assert_eq!(symbols.len(), 1);
1096                let sym = symbols.first().unwrap();
1097                match sym {
1098                    ast::Symbol::Rule(_, span) => assert_eq!(span, &Span::new(6, 7)),
1099                    ast::Symbol::Token(_, _) => panic!("Incorrect symbol"),
1100                }
1101            }
1102            Err(e) => panic!("Incorrect error returned {:?}", e),
1103        }
1104    }
1105
1106    #[test]
1107    fn test_accept_reduce_conflict_spans2() {
1108        let src = "%%
1109S: T | ;
1110T: S | ;";
1111        let yk = YaccKindResolver::Force(YaccKind::Original(YaccOriginalActionKind::NoAction));
1112        let ast_validity = ASTWithValidityInfo::new(yk, src);
1113        let grm = YaccGrammar::<u32>::new_from_ast_with_validity_info(&ast_validity).unwrap();
1114        let sg = pager_stategraph(&grm);
1115        match StateTable::new(&grm, &sg) {
1116            Ok(_) => panic!("Expected accept reduce conflict"),
1117            Err(StateTableError {
1118                kind: StateTableErrorKind::AcceptReduceConflict(None),
1119                pidx,
1120            }) if pidx == PIdx(2) => {
1121                assert!(ast_validity.ast().prods.len() > usize::from(pidx));
1122                // We expect this one to have a symbol in the ast.
1123                // We can get a span for the RHS "S" at "S |" in rule T.
1124                let prod = &ast_validity.ast().prods[usize::from(pidx)];
1125                let symbols = &prod.symbols;
1126                assert_eq!(symbols.len(), 1);
1127                let sym = symbols.first().unwrap();
1128                match sym {
1129                    ast::Symbol::Rule(_, span) => assert_eq!(span, &Span::new(15, 16)),
1130                    ast::Symbol::Token(_, _) => panic!("Incorrect symbol"),
1131                }
1132            }
1133            Err(e) => panic!("Incorrect error returned {:?}", e),
1134        }
1135    }
1136}