use crate::collections::Collection;
use crate::grammar::repr::*;
use crate::lr1::core::*;
use crate::lr1::tls::Lr1Tls;
use bit_set::{self, BitSet};
use std::fmt::{Debug, Error, Formatter};
use std::hash::Hash;
pub trait Lookahead: Clone + Debug + Eq + Ord + Hash + Collection<Item = Self> {
fn fmt_as_item_suffix(&self, fmt: &mut Formatter<'_>) -> Result<(), Error>;
fn conflicts<'grammar>(this_state: &State<'grammar, Self>) -> Vec<Conflict<'grammar, Self>>;
}
#[derive(Copy, Clone, Debug, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Nil;
impl Collection for Nil {
type Item = Nil;
fn push(&mut self, _: Nil) -> bool {
false
}
}
impl Lookahead for Nil {
fn fmt_as_item_suffix(&self, _fmt: &mut Formatter<'_>) -> Result<(), Error> {
Ok(())
}
fn conflicts<'grammar>(this_state: &State<'grammar, Self>) -> Vec<Conflict<'grammar, Self>> {
let index = this_state.index;
let mut conflicts = vec![];
for (terminal, &next_state) in &this_state.shifts {
conflicts.extend(
this_state
.reductions
.iter()
.map(|&(_, production)| Conflict {
state: index,
lookahead: Nil,
production,
action: Action::Shift(terminal.clone(), next_state),
}),
);
}
if this_state.reductions.len() > 1 {
for &(_, production) in &this_state.reductions[1..] {
let other_production = this_state.reductions[0].1;
conflicts.push(Conflict {
state: index,
lookahead: Nil,
production,
action: Action::Reduce(other_production),
});
}
}
conflicts
}
}
#[derive(Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum Token {
Eof,
Error,
Terminal(TerminalString),
}
impl Lookahead for TokenSet {
fn fmt_as_item_suffix(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> {
write!(fmt, " {self:?}")
}
fn conflicts<'grammar>(this_state: &State<'grammar, Self>) -> Vec<Conflict<'grammar, Self>> {
let mut conflicts = vec![];
for (terminal, &next_state) in &this_state.shifts {
let token = Token::Terminal(terminal.clone());
let inconsistent =
this_state
.reductions
.iter()
.filter_map(|&(ref reduce_tokens, production)| {
if reduce_tokens.contains(&token) {
Some(production)
} else {
None
}
});
let set = TokenSet::from(token.clone());
for production in inconsistent {
conflicts.push(Conflict {
state: this_state.index,
lookahead: set.clone(),
production,
action: Action::Shift(terminal.clone(), next_state),
});
}
}
let len = this_state.reductions.len();
for i in 0..len {
for j in i + 1..len {
let &(ref i_tokens, i_production) = &this_state.reductions[i];
let &(ref j_tokens, j_production) = &this_state.reductions[j];
if i_tokens.is_disjoint(j_tokens) {
continue;
}
conflicts.push(Conflict {
state: this_state.index,
lookahead: i_tokens.intersection(j_tokens),
production: i_production,
action: Action::Reduce(j_production),
});
}
}
conflicts
}
}
impl Token {
#[deprecated(since = "0.20.0", note = "use `Eof` instead")]
pub const EOF: Self = Self::Eof;
pub fn unwrap_terminal(&self) -> &TerminalString {
match *self {
Token::Terminal(ref t) => t,
Token::Eof | Token::Error => {
panic!("`unwrap_terminal()` invoked but with EOF or Error")
}
}
}
}
#[derive(Clone, Default, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct TokenSet {
bit_set: BitSet<u32>,
}
fn with<OP, RET>(op: OP) -> RET
where
OP: FnOnce(&TerminalSet) -> RET,
{
Lr1Tls::with(op)
}
impl TokenSet {
pub fn new() -> Self {
with(|terminals| TokenSet {
bit_set: BitSet::with_capacity(terminals.all.len() + 2),
})
}
pub fn all() -> Self {
let mut s = TokenSet::new();
with(|terminals| {
for i in 0..terminals.all.len() {
s.bit_set.insert(i);
}
s.insert_eof();
});
s
}
pub fn eof() -> Self {
let mut set = TokenSet::new();
set.insert_eof();
set
}
fn eof_bit(&self) -> usize {
with(|terminals| terminals.all.len())
}
fn bit(&self, lookahead: &Token) -> usize {
with(|t| self.bit_with(lookahead, t))
}
fn bit_with(&self, lookahead: &Token, terminals: &TerminalSet) -> usize {
match *lookahead {
Token::Eof => terminals.all.len(),
Token::Error => terminals.all.len() + 1,
Token::Terminal(ref t) => terminals.bits[t],
}
}
pub fn reserve(&mut self, len: usize) {
self.bit_set.reserve_len(len)
}
pub fn len(&self) -> usize {
self.bit_set.len()
}
pub fn insert(&mut self, lookahead: Token) -> bool {
let bit = self.bit(&lookahead);
self.bit_set.insert(bit)
}
pub fn insert_with(&mut self, lookahead: Token, terminals: &TerminalSet) -> bool {
let bit = self.bit_with(&lookahead, terminals);
self.bit_set.insert(bit)
}
pub fn insert_eof(&mut self) -> bool {
let bit = self.eof_bit();
self.bit_set.insert(bit)
}
pub fn union_with(&mut self, set: &TokenSet) -> bool {
let len = self.len();
self.bit_set.union_with(&set.bit_set);
self.len() != len
}
pub fn intersection(&self, set: &TokenSet) -> TokenSet {
let mut bit_set = self.bit_set.clone();
bit_set.intersect_with(&set.bit_set);
TokenSet { bit_set }
}
pub fn contains(&self, token: &Token) -> bool {
self.bit_set.contains(self.bit(token))
}
pub fn contains_eof(&self) -> bool {
self.bit_set.contains(self.eof_bit())
}
pub fn take_eof(&mut self) -> bool {
let eof_bit = self.eof_bit();
let contains_eof = self.bit_set.contains(eof_bit);
self.bit_set.remove(eof_bit);
contains_eof
}
pub fn is_disjoint(&self, other: &TokenSet) -> bool {
self.bit_set.is_disjoint(&other.bit_set)
}
pub fn is_intersecting(&self, other: &TokenSet) -> bool {
!self.is_disjoint(other)
}
pub fn iter(&self) -> TokenSetIter<'_> {
TokenSetIter {
bit_set: self.bit_set.iter(),
}
}
}
pub struct TokenSetIter<'iter> {
bit_set: bit_set::Iter<'iter, u32>,
}
impl Iterator for TokenSetIter<'_> {
type Item = Token;
fn next(&mut self) -> Option<Token> {
self.bit_set.next().map(|bit| {
with(|terminals| {
if bit == terminals.all.len() + 1 {
Token::Error
} else if bit == terminals.all.len() {
Token::Eof
} else {
Token::Terminal(terminals.all[bit].clone())
}
})
})
}
}
impl Debug for TokenSet {
fn fmt(&self, fmt: &mut Formatter<'_>) -> Result<(), Error> {
let terminals: Vec<_> = self.iter().collect();
Debug::fmt(&terminals, fmt)
}
}
impl<'iter> IntoIterator for &'iter TokenSet {
type IntoIter = TokenSetIter<'iter>;
type Item = Token;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
impl Collection for TokenSet {
type Item = TokenSet;
fn push(&mut self, item: TokenSet) -> bool {
self.union_with(&item)
}
}
impl From<Token> for TokenSet {
fn from(token: Token) -> Self {
let mut set = TokenSet::new();
set.insert(token);
set
}
}