#![allow(clippy::derive_partial_eq_without_eq)]
use std::{
cmp::Ordering,
collections::hash_map::HashMap,
error::Error,
fmt::{self, Debug, Write},
hash::Hash,
marker::PhantomData,
};
use cfgrammar::{
yacc::{AssocKind, YaccGrammar},
PIdx, RIdx, Symbol, TIdx,
};
use num_traits::{AsPrimitive, PrimInt, Unsigned};
#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};
use sparsevec::SparseVec;
use vob::{IterSetBits, Vob};
use crate::{stategraph::StateGraph, StIdx};
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Debug)]
pub struct Conflicts<StorageT> {
reduce_reduce: Vec<(PIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)>,
shift_reduce: Vec<(TIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)>,
}
impl<StorageT: 'static + Hash + PrimInt + Unsigned> Conflicts<StorageT>
where
usize: AsPrimitive<StorageT>,
{
pub fn rr_conflicts(
&self,
) -> impl Iterator<Item = &(PIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)> {
self.reduce_reduce.iter()
}
pub fn sr_conflicts(
&self,
) -> impl Iterator<Item = &(TIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)> {
self.shift_reduce.iter()
}
pub fn rr_len(&self) -> usize {
self.reduce_reduce.len()
}
pub fn sr_len(&self) -> usize {
self.shift_reduce.len()
}
#[deprecated(since = "0.10.1", note = "Please use pp_rr() and pp_sr() instead")]
pub fn pp(&self, grm: &YaccGrammar<StorageT>) -> String {
let mut s = String::new();
s.push_str(&self.pp_sr(grm));
s.push_str(&self.pp_rr(grm));
s
}
pub fn pp_rr(&self, grm: &YaccGrammar<StorageT>) -> String {
let mut s = String::new();
if self.rr_len() > 0 {
s.push_str("Reduce/Reduce conflicts:\n");
for (pidx, r_pidx, stidx) in self.rr_conflicts() {
writeln!(
s,
" State {:?}: Reduce({}) / Reduce({})",
usize::from(*stidx),
grm.pp_prod(*pidx),
grm.pp_prod(*r_pidx)
)
.ok();
}
}
s
}
pub fn pp_sr(&self, grm: &YaccGrammar<StorageT>) -> String {
let mut s = String::new();
if self.sr_len() > 0 {
s.push_str("Shift/Reduce conflicts:\n");
for (tidx, pidx, stidx) in self.sr_conflicts() {
writeln!(
s,
" State {:?}: Shift(\"{}\") / Reduce({})",
usize::from(*stidx),
grm.token_name(*tidx).unwrap(),
grm.pp_prod(*pidx)
)
.ok();
}
}
s
}
}
#[derive(Debug)]
pub enum StateTableErrorKind<StorageT> {
AcceptReduceConflict(Option<PIdx<StorageT>>),
}
#[derive(Debug)]
pub struct StateTableError<StorageT> {
pub kind: StateTableErrorKind<StorageT>,
pub pidx: PIdx<StorageT>,
}
impl<StorageT: Debug> Error for StateTableError<StorageT> {}
impl<StorageT> fmt::Display for StateTableError<StorageT> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
let s = match self.kind {
StateTableErrorKind::AcceptReduceConflict(_) => "Accept/reduce conflict",
};
write!(f, "{}", s)
}
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct StateTable<StorageT> {
actions: SparseVec<usize>,
state_actions: Vob<u64>,
gotos: SparseVec<usize>,
start_state: StIdx<StorageT>,
core_reduces: Vob<u64>,
state_shifts: Vob<u64>,
reduce_states: Vob<u64>,
prods_len: PIdx<StorageT>,
tokens_len: TIdx<StorageT>,
conflicts: Option<Conflicts<StorageT>>,
#[cfg(test)]
final_state: StIdx<StorageT>,
}
#[derive(Clone, Copy, Debug, PartialEq)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub enum Action<StorageT> {
Shift(StIdx<StorageT>),
Reduce(PIdx<StorageT>),
Accept,
Error,
}
const SHIFT: usize = 1;
const REDUCE: usize = 2;
const ACCEPT: usize = 3;
const ERROR: usize = 0;
impl<StorageT: 'static + Hash + PrimInt + Unsigned> StateTable<StorageT>
where
usize: AsPrimitive<StorageT>,
{
pub fn new(
grm: &YaccGrammar<StorageT>,
sg: &StateGraph<StorageT>,
) -> Result<Self, StateTableError<StorageT>> {
let mut state_actions = Vob::<u64>::from_elem_with_storage_type(
false,
usize::from(sg.all_states_len())
.checked_mul(usize::from(grm.tokens_len()))
.unwrap(),
);
let maxa = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
let maxg = usize::from(grm.rules_len()) * usize::from(sg.all_states_len());
assert!(usize::from(sg.all_states_len()) < (usize::MAX - 4));
assert!(usize::from(grm.rules_len()) < (usize::MAX - 4));
let mut actions: Vec<usize> = vec![0; maxa];
assert!(sg.all_states_len().as_storaget() < StorageT::max_value() - StorageT::one());
let mut gotos: Vec<usize> = vec![0; maxg];
let mut reduce_reduce = Vec::new();
let mut shift_reduce = Vec::new();
let mut final_state = None;
for (stidx, state) in sg
.iter_closed_states()
.enumerate()
.map(|(x, y)| (StIdx(x.as_()), y))
{
for (&(pidx, dot), ctx) in &state.items {
if dot < grm.prod_len(pidx) {
continue;
}
for tidx in ctx.iter_set_bits(..) {
let off = actions_offset(
grm.tokens_len(),
stidx,
TIdx(tidx.as_()),
);
state_actions.set(off, true);
match StateTable::decode(actions[off]) {
Action::Reduce(r_pidx) => {
if pidx == grm.start_prod() && tidx == usize::from(grm.eof_token_idx())
{
return Err(StateTableError {
kind: StateTableErrorKind::AcceptReduceConflict(Some(r_pidx)),
pidx,
});
}
match pidx.cmp(&r_pidx) {
Ordering::Less => {
reduce_reduce.push((pidx, r_pidx, stidx));
actions[off] = StateTable::encode(Action::Reduce(pidx));
}
Ordering::Greater => reduce_reduce.push((r_pidx, pidx, stidx)),
Ordering::Equal => (),
}
}
Action::Accept => {
return Err(StateTableError {
kind: StateTableErrorKind::AcceptReduceConflict(None),
pidx,
});
}
Action::Error => {
if pidx == grm.start_prod() && tidx == usize::from(grm.eof_token_idx())
{
assert!(final_state.is_none());
final_state = Some(stidx);
actions[off] = StateTable::encode(Action::Accept);
} else {
actions[off] = StateTable::encode(Action::Reduce(pidx));
}
}
_ => panic!("Internal error"),
}
}
}
let nt_len = grm.rules_len();
for (&sym, ref_stidx) in sg.edges(stidx) {
match sym {
Symbol::Rule(s_ridx) => {
let off = (usize::from(stidx) * usize::from(nt_len)) + usize::from(s_ridx);
debug_assert!(gotos[off] == 0);
gotos[off] = usize::from(*ref_stidx) + 1;
}
Symbol::Token(s_tidx) => {
let off = actions_offset(grm.tokens_len(), stidx, s_tidx);
state_actions.set(off, true);
match StateTable::decode(actions[off]) {
Action::Shift(x) => assert!(*ref_stidx == x),
Action::Reduce(r_pidx) => {
resolve_shift_reduce(
grm,
&mut actions,
off,
s_tidx,
r_pidx,
*ref_stidx,
&mut shift_reduce,
stidx,
);
}
Action::Accept => panic!("Internal error"),
Action::Error => {
actions[off] = StateTable::encode(Action::Shift(*ref_stidx));
}
}
}
}
}
}
assert!(final_state.is_some());
let mut nt_depth = HashMap::new();
let mut core_reduces = Vob::<u64>::from_elem_with_storage_type(
false,
usize::from(sg.all_states_len())
.checked_mul(usize::from(grm.prods_len()))
.unwrap(),
);
let mut state_shifts = Vob::<u64>::from_elem_with_storage_type(
false,
usize::from(sg.all_states_len())
.checked_mul(usize::from(grm.tokens_len()))
.unwrap(),
);
let mut reduce_states =
Vob::<u64>::from_elem_with_storage_type(false, usize::from(sg.all_states_len()));
for stidx in sg.iter_stidxs() {
nt_depth.clear();
let mut only_reduces = true;
for tidx in grm.iter_tidxs() {
let off = actions_offset(grm.tokens_len(), stidx, tidx);
match StateTable::decode(actions[off]) {
Action::Reduce(pidx) => {
let prod_len = grm.prod(pidx).len();
let ridx = grm.prod_to_rule(pidx);
nt_depth.insert((ridx, prod_len), pidx);
}
Action::Shift(_) => {
only_reduces = false;
state_shifts.set(off, true);
}
Action::Accept => {
only_reduces = false;
}
Action::Error => (),
}
}
let mut distinct_reduces = 0; for &pidx in nt_depth.values() {
let off = usize::from(stidx)
.checked_mul(usize::from(grm.prods_len()))
.unwrap()
.checked_add(usize::from(pidx))
.unwrap();
if core_reduces.set(off, true) {
distinct_reduces += 1;
}
}
if only_reduces && distinct_reduces == 1 {
reduce_states.set(usize::from(stidx), true);
}
}
let actions_sv = SparseVec::<usize>::from(&actions, 0, usize::from(grm.tokens_len()));
let gotos_sv = SparseVec::<usize>::from(&gotos, 0, usize::from(grm.rules_len()));
let conflicts = if !(reduce_reduce.is_empty() && shift_reduce.is_empty()) {
Some(Conflicts {
reduce_reduce,
shift_reduce,
})
} else {
None
};
Ok(StateTable {
actions: actions_sv,
state_actions,
gotos: gotos_sv,
start_state: sg.start_state(),
state_shifts,
core_reduces,
reduce_states,
prods_len: grm.prods_len(),
tokens_len: grm.tokens_len(),
conflicts,
#[cfg(test)]
final_state: final_state.unwrap(),
})
}
fn decode(bits: usize) -> Action<StorageT> {
let action = bits & 0b11;
let val = bits >> 2;
match action {
SHIFT => {
Action::Shift(StIdx(val.as_()))
}
REDUCE => Action::Reduce(PIdx(val.as_())),
ACCEPT => Action::Accept,
ERROR => Action::Error,
_ => unreachable!(),
}
}
fn encode(action: Action<StorageT>) -> usize {
match action {
Action::Shift(stidx) => SHIFT | (usize::from(stidx) << 2),
Action::Reduce(ridx) => REDUCE | (usize::from(ridx) << 2),
Action::Accept => ACCEPT,
Action::Error => ERROR,
}
}
pub fn action(&self, stidx: StIdx<StorageT>, tidx: TIdx<StorageT>) -> Action<StorageT> {
StateTable::decode(
self.actions
.get(usize::from(stidx), usize::from(tidx))
.unwrap(),
)
}
pub fn state_actions(&self, stidx: StIdx<StorageT>) -> StateActionsIterator<StorageT> {
let start = usize::from(stidx) * usize::from(self.tokens_len);
let end = start + usize::from(self.tokens_len);
StateActionsIterator {
iter: self.state_actions.iter_set_bits(start..end),
start,
phantom: PhantomData,
}
}
pub fn state_shifts(&self, stidx: StIdx<StorageT>) -> StateActionsIterator<StorageT> {
let start = usize::from(stidx) * usize::from(self.tokens_len);
let end = start + usize::from(self.tokens_len);
StateActionsIterator {
iter: self.state_shifts.iter_set_bits(start..end),
start,
phantom: PhantomData,
}
}
pub fn reduce_only_state(&self, stidx: StIdx<StorageT>) -> bool {
self.reduce_states[usize::from(stidx)]
}
pub fn core_reduces(&self, stidx: StIdx<StorageT>) -> CoreReducesIterator<StorageT> {
let start = usize::from(stidx) * usize::from(self.prods_len);
let end = start + usize::from(self.prods_len);
CoreReducesIterator {
iter: self.core_reduces.iter_set_bits(start..end),
start,
phantom: PhantomData,
}
}
pub fn goto(&self, stidx: StIdx<StorageT>, ridx: RIdx<StorageT>) -> Option<StIdx<StorageT>> {
match self.gotos.get(usize::from(stidx), usize::from(ridx)) {
Some(0) => None,
Some(i) => Some(StIdx((i - 1).as_())),
None => unreachable!(),
}
}
pub fn start_state(&self) -> StIdx<StorageT> {
self.start_state
}
pub fn conflicts(&self) -> Option<&Conflicts<StorageT>> {
self.conflicts.as_ref()
}
}
fn actions_offset<StorageT: PrimInt + Unsigned>(
tokens_len: TIdx<StorageT>,
stidx: StIdx<StorageT>,
tidx: TIdx<StorageT>,
) -> usize {
usize::from(stidx) * usize::from(tokens_len) + usize::from(tidx)
}
pub struct StateActionsIterator<'a, StorageT> {
iter: IterSetBits<'a, u64>,
start: usize,
phantom: PhantomData<StorageT>,
}
impl<'a, StorageT: 'static + PrimInt + Unsigned> Iterator for StateActionsIterator<'a, StorageT>
where
usize: AsPrimitive<StorageT>,
{
type Item = TIdx<StorageT>;
fn next(&mut self) -> Option<TIdx<StorageT>> {
self.iter.next().map(|i| TIdx((i - self.start).as_()))
}
}
pub struct CoreReducesIterator<'a, StorageT> {
iter: IterSetBits<'a, u64>,
start: usize,
phantom: PhantomData<StorageT>,
}
impl<'a, StorageT: 'static + PrimInt + Unsigned> Iterator for CoreReducesIterator<'a, StorageT>
where
usize: AsPrimitive<StorageT>,
{
type Item = PIdx<StorageT>;
fn next(&mut self) -> Option<PIdx<StorageT>> {
self.iter.next().map(|i| PIdx((i - self.start).as_()))
}
}
fn resolve_shift_reduce<StorageT: 'static + Hash + PrimInt + Unsigned>(
grm: &YaccGrammar<StorageT>,
actions: &mut [usize],
off: usize,
tidx: TIdx<StorageT>,
pidx: PIdx<StorageT>,
stidx: StIdx<StorageT>, shift_reduce: &mut Vec<(TIdx<StorageT>, PIdx<StorageT>, StIdx<StorageT>)>,
conflict_stidx: StIdx<StorageT>, ) where
usize: AsPrimitive<StorageT>,
{
let tidx_prec = grm.token_precedence(tidx);
let pidx_prec = grm.prod_precedence(pidx);
match (tidx_prec, pidx_prec) {
(_, None) | (None, _) => {
actions[off] = StateTable::encode(Action::Shift(stidx));
shift_reduce.push((tidx, pidx, conflict_stidx));
}
(Some(token_prec), Some(prod_prec)) => {
match token_prec.level.cmp(&prod_prec.level) {
Ordering::Equal => {
match (token_prec.kind, prod_prec.kind) {
(AssocKind::Left, AssocKind::Left) => {
}
(AssocKind::Right, AssocKind::Right) => {
actions[off] = StateTable::encode(Action::Shift(stidx));
}
(AssocKind::Nonassoc, AssocKind::Nonassoc) => {
actions[off] = StateTable::encode(Action::Error);
}
(_, _) => {
panic!("Not supported.");
}
}
}
Ordering::Greater => {
actions[off] = StateTable::encode(Action::Shift(stidx));
}
Ordering::Less => {
}
}
}
}
}
#[cfg(test)]
mod test {
use super::{Action, StateTable, StateTableError, StateTableErrorKind};
use crate::{pager::pager_stategraph, StIdx};
use cfgrammar::{
yacc::{
ast::{self, ASTWithValidityInfo},
YaccGrammar, YaccKind, YaccOriginalActionKind,
},
PIdx, Span, Symbol, TIdx,
};
use std::collections::HashSet;
#[test]
#[rustfmt::skip]
fn test_statetable() {
let grm = YaccGrammar::new(
YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
"
%start Expr
%%
Expr : Term '-' Expr | Term;
Term : Factor '*' Term | Factor;
Factor : 'id';
"
).unwrap();
let sg = pager_stategraph(&grm);
assert_eq!(sg.all_states_len(), StIdx(9));
let s0 = sg.start_state();
let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s2 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Term").unwrap())).unwrap();
let s3 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Factor").unwrap())).unwrap();
let s4 = sg.edge(s0, Symbol::Token(grm.token_idx("id").unwrap())).unwrap();
let s5 = sg.edge(s2, Symbol::Token(grm.token_idx("-").unwrap())).unwrap();
let s6 = sg.edge(s3, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
let s7 = sg.edge(s5, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s8 = sg.edge(s6, Symbol::Rule(grm.rule_idx("Term").unwrap())).unwrap();
let st = StateTable::new(&grm, &sg).unwrap();
assert_eq!(st.actions.len(), 9*4);
let assert_reduce = |stidx: StIdx<_>, tidx: TIdx<_>, rule: &str, prod_off: usize| {
let pidx = grm.rule_to_prods(grm.rule_idx(rule).unwrap())[prod_off];
assert_eq!(st.action(stidx, tidx), Action::Reduce(pidx));
};
assert_eq!(st.action(s0, grm.token_idx("id").unwrap()), Action::Shift(s4));
assert_eq!(st.action(s1, grm.eof_token_idx()), Action::Accept);
assert_eq!(st.final_state, s1);
assert_eq!(st.action(s2, grm.token_idx("-").unwrap()), Action::Shift(s5));
assert_reduce(s2, grm.eof_token_idx(), "Expr", 1);
assert_reduce(s3, grm.token_idx("-").unwrap(), "Term", 1);
assert_eq!(st.action(s3, grm.token_idx("*").unwrap()), Action::Shift(s6));
assert_reduce(s3, grm.eof_token_idx(), "Term", 1);
assert_reduce(s4, grm.token_idx("-").unwrap(), "Factor", 0);
assert_reduce(s4, grm.token_idx("*").unwrap(), "Factor", 0);
assert_reduce(s4, grm.eof_token_idx(), "Factor", 0);
assert_eq!(st.action(s5, grm.token_idx("id").unwrap()), Action::Shift(s4));
assert_eq!(st.action(s6, grm.token_idx("id").unwrap()), Action::Shift(s4));
assert_reduce(s7, grm.eof_token_idx(), "Expr", 0);
assert_reduce(s8, grm.token_idx("-").unwrap(), "Term", 0);
assert_reduce(s8, grm.eof_token_idx(), "Term", 0);
let mut s4_actions = HashSet::new();
s4_actions.extend([grm.token_idx("-").unwrap(),
grm.token_idx("*").unwrap(),
grm.eof_token_idx()]);
assert_eq!(st.state_actions(s4).collect::<HashSet<_>>(), s4_actions);
let s2_state_shifts = &[grm.token_idx("-").unwrap()]
.iter()
.cloned()
.collect::<HashSet<_>>();
assert_eq!(st.state_shifts(s2).collect::<HashSet<_>>(), *s2_state_shifts);
let s4_core_reduces = &[grm.rule_to_prods(grm.rule_idx("Factor").unwrap())[0]]
.iter()
.cloned()
.collect::<HashSet<_>>();
assert_eq!(st.core_reduces(s4).collect::<HashSet<_>>(), *s4_core_reduces);
assert_eq!(st.gotos.len(), 9*4);
assert_eq!(st.goto(s0, grm.rule_idx("Expr").unwrap()).unwrap(), s1);
assert_eq!(st.goto(s0, grm.rule_idx("Term").unwrap()).unwrap(), s2);
assert_eq!(st.goto(s0, grm.rule_idx("Factor").unwrap()).unwrap(), s3);
assert_eq!(st.goto(s5, grm.rule_idx("Expr").unwrap()).unwrap(), s7);
assert_eq!(st.goto(s5, grm.rule_idx("Term").unwrap()).unwrap(), s2);
assert_eq!(st.goto(s5, grm.rule_idx("Factor").unwrap()).unwrap(), s3);
assert_eq!(st.goto(s6, grm.rule_idx("Term").unwrap()).unwrap(), s8);
assert_eq!(st.goto(s6, grm.rule_idx("Factor").unwrap()).unwrap(), s3);
}
#[test]
#[rustfmt::skip]
fn test_default_reduce_reduce() {
let grm = YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), "
%start A
%%
A : B 'x' | C 'x' 'x';
B : 'a';
C : 'a';
").unwrap();
let sg = pager_stategraph(&grm);
let st = StateTable::new(&grm, &sg).unwrap();
let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
assert_eq!(st.actions.len(), len);
let s0 = sg.start_state();
let s4 = sg.edge(s0, Symbol::Token(grm.token_idx("a").unwrap())).unwrap();
assert_eq!(st.action(s4, grm.token_idx("x").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("B").unwrap())[0]));
}
#[test]
#[rustfmt::skip]
fn test_default_shift_reduce() {
let grm = YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), "
%start Expr
%%
Expr : Expr '+' Expr
| Expr '*' Expr
| 'id' ;
").unwrap();
let sg = pager_stategraph(&grm);
let st = StateTable::new(&grm, &sg).unwrap();
let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
assert_eq!(st.actions.len(), len);
let s0 = sg.start_state();
let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
let s5 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s6 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
assert_eq!(st.action(s5, grm.token_idx("+").unwrap()), Action::Shift(s3));
assert_eq!(st.action(s5, grm.token_idx("*").unwrap()), Action::Shift(s4));
assert_eq!(st.action(s6, grm.token_idx("+").unwrap()), Action::Shift(s3));
assert_eq!(st.action(s6, grm.token_idx("*").unwrap()), Action::Shift(s4));
}
#[test]
#[rustfmt::skip]
fn test_conflict_resolution() {
let grm = YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), "
%start S
%%
S: A 'c' 'd'
| B 'c' 'e';
A: 'a';
B: 'a'
| 'b';
A: 'b';
").unwrap();
let sg = pager_stategraph(&grm);
let st = StateTable::new(&grm, &sg).unwrap();
let s0 = sg.start_state();
let s1 = sg.edge(s0, Symbol::Token(grm.token_idx("a").unwrap())).unwrap();
let s2 = sg.edge(s0, Symbol::Token(grm.token_idx("b").unwrap())).unwrap();
assert_eq!(st.action(s1, grm.token_idx("c").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("A").unwrap())[0]));
assert_eq!(st.action(s2, grm.token_idx("c").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("B").unwrap())[1]));
}
#[test]
#[rustfmt::skip]
fn test_left_associativity() {
let grm = YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), "
%start Expr
%left '+'
%left '*'
%%
Expr : Expr '+' Expr
| Expr '*' Expr
| 'id' ;
").unwrap();
let sg = pager_stategraph(&grm);
let st = StateTable::new(&grm, &sg).unwrap();
let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
assert_eq!(st.actions.len(), len);
let s0 = sg.start_state();
let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
let s5 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s6 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
assert_eq!(st.action(s5, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s5, grm.token_idx("*").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s5, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s6, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
assert_eq!(st.action(s6, grm.token_idx("*").unwrap()),
Action::Shift(s4));
assert_eq!(st.action(s6, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
}
#[test]
#[rustfmt::skip]
fn test_left_right_associativity() {
let grm = &YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), "
%start Expr
%right '='
%left '+'
%left '*'
%%
Expr : Expr '+' Expr
| Expr '*' Expr
| Expr '=' Expr
| 'id' ;
").unwrap();
let sg = &pager_stategraph(grm);
let st = StateTable::new(grm, sg).unwrap();
let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
assert_eq!(st.actions.len(), len);
let s0 = sg.start_state();
let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
let s5 = sg.edge(s1, Symbol::Token(grm.token_idx("=").unwrap())).unwrap();
let s6 = sg.edge(s5, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s7 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s8 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
assert_eq!(st.action(s6, grm.token_idx("+").unwrap()),
Action::Shift(s3));
assert_eq!(st.action(s6, grm.token_idx("*").unwrap()),
Action::Shift(s4));
assert_eq!(st.action(s6, grm.token_idx("=").unwrap()),
Action::Shift(s5));
assert_eq!(st.action(s6, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[2]));
assert_eq!(st.action(s7, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s7, grm.token_idx("*").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s7, grm.token_idx("=").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s7, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s8, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
assert_eq!(st.action(s8, grm.token_idx("*").unwrap()),
Action::Shift(s4));
assert_eq!(st.action(s8, grm.token_idx("=").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
assert_eq!(st.action(s8, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
}
#[test]
#[rustfmt::skip]
fn test_left_right_nonassoc_associativity() {
let grm = YaccGrammar::new(YaccKind::Original(YaccOriginalActionKind::GenericParseTree), "
%start Expr
%right '='
%left '+'
%left '*'
%nonassoc '~'
%%
Expr : Expr '+' Expr
| Expr '*' Expr
| Expr '=' Expr
| Expr '~' Expr
| 'id' ;
").unwrap();
let sg = pager_stategraph(&grm);
let st = StateTable::new(&grm, &sg).unwrap();
let len = usize::from(grm.tokens_len()) * usize::from(sg.all_states_len());
assert_eq!(st.actions.len(), len);
let s0 = sg.start_state();
let s1 = sg.edge(s0, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s3 = sg.edge(s1, Symbol::Token(grm.token_idx("+").unwrap())).unwrap();
let s4 = sg.edge(s1, Symbol::Token(grm.token_idx("*").unwrap())).unwrap();
let s5 = sg.edge(s1, Symbol::Token(grm.token_idx("=").unwrap())).unwrap();
let s6 = sg.edge(s1, Symbol::Token(grm.token_idx("~").unwrap())).unwrap();
let s7 = sg.edge(s6, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s8 = sg.edge(s5, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s9 = sg.edge(s4, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
let s10 = sg.edge(s3, Symbol::Rule(grm.rule_idx("Expr").unwrap())).unwrap();
assert_eq!(st.action(s7, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
assert_eq!(st.action(s7, grm.token_idx("*").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
assert_eq!(st.action(s7, grm.token_idx("=").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
assert_eq!(st.action(s7, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[3]));
assert_eq!(st.action(s8, grm.token_idx("+").unwrap()),
Action::Shift(s3));
assert_eq!(st.action(s8, grm.token_idx("*").unwrap()),
Action::Shift(s4));
assert_eq!(st.action(s8, grm.token_idx("=").unwrap()),
Action::Shift(s5));
assert_eq!(st.action(s8, grm.token_idx("~").unwrap()),
Action::Shift(s6));
assert_eq!(st.action(s8, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[2]));
assert_eq!(st.action(s9, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s9, grm.token_idx("*").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s9, grm.token_idx("=").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s9, grm.token_idx("~").unwrap()),
Action::Shift(s6));
assert_eq!(st.action(s9, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[1]));
assert_eq!(st.action(s10, grm.token_idx("+").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
assert_eq!(st.action(s10, grm.token_idx("*").unwrap()),
Action::Shift(s4));
assert_eq!(st.action(s10, grm.token_idx("=").unwrap()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
assert_eq!(st.action(s10, grm.token_idx("~").unwrap()),
Action::Shift(s6));
assert_eq!(st.action(s10, grm.eof_token_idx()),
Action::Reduce(grm.rule_to_prods(grm.rule_idx("Expr").unwrap())[0]));
}
#[test]
fn conflicts() {
let grm = YaccGrammar::new(
YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
"
%start A
%%
A : 'a' 'b' | B 'b';
B : 'a' | C;
C : 'a';
",
)
.unwrap();
let sg = pager_stategraph(&grm);
let st = StateTable::new(&grm, &sg).unwrap();
let conflicts = st.conflicts().unwrap();
assert_eq!(conflicts.sr_len(), 1);
assert_eq!(conflicts.rr_len(), 1);
assert_eq!(
conflicts.sr_conflicts().next().unwrap(),
&(
grm.token_idx("b").unwrap(),
grm.rule_to_prods(grm.rule_idx("B").unwrap())[0],
StIdx(2)
)
);
assert_eq!(
conflicts.rr_conflicts().next().unwrap(),
&(
grm.rule_to_prods(grm.rule_idx("B").unwrap())[0],
grm.rule_to_prods(grm.rule_idx("C").unwrap())[0],
StIdx(2)
)
);
}
#[test]
fn accept_reduce_conflict() {
let grm = YaccGrammar::new(
YaccKind::Original(YaccOriginalActionKind::GenericParseTree),
"
%start D
%%
D : D;
",
)
.unwrap();
let sg = pager_stategraph(&grm);
match StateTable::new(&grm, &sg) {
Ok(_) => panic!("Infinitely recursive rule let through"),
Err(StateTableError {
kind: StateTableErrorKind::AcceptReduceConflict(_),
pidx: PIdx(1),
}) => (),
Err(e) => panic!("Incorrect error returned {:?}", e),
}
}
#[test]
fn test_accept_reduce_conflict_spans1() {
let src = "%%
S: S | ;";
let yk = YaccKind::Original(YaccOriginalActionKind::NoAction);
let ast_validity = ASTWithValidityInfo::new(yk, src);
let grm = YaccGrammar::<u32>::new_from_ast_with_validity_info(yk, &ast_validity).unwrap();
let sg = pager_stategraph(&grm);
match StateTable::new(&grm, &sg) {
Ok(_) => panic!("Expected accept reduce conflict"),
Err(StateTableError {
kind: StateTableErrorKind::AcceptReduceConflict(r_pidx),
pidx,
}) if pidx == PIdx(2) => {
assert!(ast_validity.ast().prods.len() <= usize::from(pidx));
let symbols = grm.prod(pidx);
assert_eq!(symbols.len(), 1);
let sym = symbols.first().unwrap();
match sym {
Symbol::Rule(r) => {
let span = grm.rule_name_span(*r);
assert_eq!(span, Span::new(3, 4));
}
Symbol::Token(t) => {
let span = grm.token_span(*t);
panic!("Unexpected symbol at {:?}", span);
}
}
assert!(r_pidx.is_some());
let r_pidx = r_pidx.unwrap();
assert!(ast_validity.ast().prods.len() >= usize::from(r_pidx));
let prod = &ast_validity.ast().prods[usize::from(r_pidx)];
let symbols = &prod.symbols;
assert_eq!(symbols.len(), 1);
let sym = symbols.first().unwrap();
match sym {
ast::Symbol::Rule(_, span) => assert_eq!(span, &Span::new(6, 7)),
ast::Symbol::Token(_, _) => panic!("Incorrect symbol"),
}
}
Err(e) => panic!("Incorrect error returned {:?}", e),
}
}
#[test]
fn test_accept_reduce_conflict_spans2() {
let src = "%%
S: T | ;
T: S | ;";
let yk = YaccKind::Original(YaccOriginalActionKind::NoAction);
let ast_validity = ASTWithValidityInfo::new(yk, src);
let grm = YaccGrammar::<u32>::new_from_ast_with_validity_info(yk, &ast_validity).unwrap();
let sg = pager_stategraph(&grm);
match StateTable::new(&grm, &sg) {
Ok(_) => panic!("Expected accept reduce conflict"),
Err(StateTableError {
kind: StateTableErrorKind::AcceptReduceConflict(None),
pidx,
}) if pidx == PIdx(2) => {
assert!(ast_validity.ast().prods.len() > usize::from(pidx));
let prod = &ast_validity.ast().prods[usize::from(pidx)];
let symbols = &prod.symbols;
assert_eq!(symbols.len(), 1);
let sym = symbols.first().unwrap();
match sym {
ast::Symbol::Rule(_, span) => assert_eq!(span, &Span::new(15, 16)),
ast::Symbol::Token(_, _) => panic!("Incorrect symbol"),
}
}
Err(e) => panic!("Incorrect error returned {:?}", e),
}
}
}