use bit_matrix::BitMatrix;
use bit_vec::BitVec;
use crate::analysis::{self, RhsClosure};
use crate::prelude::*;
use crate::symbol::SymbolBitSet;
pub struct Usefulness<G> {
grammar: G,
reachability: BitMatrix,
reachable_syms: BitVec,
productivity: BitVec,
all_useful: bool,
all_productive: bool,
}
pub struct UselessRules<'a, G, R>
where
G: 'a,
{
rules: R,
usefulness: &'a Usefulness<&'a mut G>,
}
#[derive(Clone, Debug)]
pub struct UselessRule<R> {
pub rule: R,
pub unreachable: bool,
pub unproductive: bool,
}
fn used_syms<'a, G>(grammar: &'a G) -> BitVec
where
G: RuleContainer + Default,
&'a G: RuleContainerRef<'a, Target = G>,
{
let num_syms = grammar.sym_source().num_syms();
let mut used_syms = BitVec::from_elem(num_syms, false);
for rule in grammar.rules() {
used_syms.set(rule.lhs().usize(), true);
for &sym in rule.rhs() {
used_syms.set(sym.usize(), true);
}
}
used_syms
}
fn productive_syms<'a, G>(grammar: &'a G) -> BitVec
where
G: RuleContainer + Default,
&'a G: RuleContainerRef<'a, Target = G>,
{
let mut productive_syms = SymbolBitSet::terminal_or_nulling_set(&grammar).into_bit_vec();
RhsClosure::new(grammar).rhs_closure(&mut productive_syms);
productive_syms
}
impl<'a, G> Usefulness<&'a mut G>
where
G: RuleContainer + Default,
for<'b> &'b G: RuleContainerRef<'b, Target = G>,
for<'b> &'b mut G: RuleContainerMut<'b, Target = G>,
{
pub fn new(grammar: &'a mut G) -> Usefulness<&'a mut G> {
let mut productivity = productive_syms(grammar);
let reachability = analysis::reachability_matrix(grammar);
let used_syms = used_syms(grammar);
let mut reachable_syms = BitVec::from_elem(grammar.sym_source().num_syms(), false);
unsafe {
for ((productive, reachable), &used) in productivity
.storage_mut()
.iter_mut()
.zip(reachable_syms.storage_mut().iter_mut())
.zip(used_syms.storage().iter())
{
*productive |= !used;
*reachable |= !used;
}
}
let all_productive = productivity
.storage()
.iter()
.all(|&productive| productive == !0);
Usefulness {
grammar: grammar,
productivity: productivity,
reachability: reachability,
reachable_syms: reachable_syms,
all_useful: false,
all_productive: all_productive,
}
}
pub fn productivity(&self, sym: Symbol) -> bool {
self.productivity[sym.usize()]
}
pub fn reachable<Sr>(mut self, syms: Sr) -> Self
where
Sr: AsRef<[Symbol]>,
{
for &sym in syms.as_ref().iter() {
let reachability = self.reachability[sym.usize()].iter();
unsafe {
for (dst, &src) in self
.reachable_syms
.storage_mut()
.iter_mut()
.zip(reachability)
{
*dst |= src;
}
}
}
self.all_useful = self.all_productive
& self
.reachable_syms
.storage()
.iter()
.all(|&reachable| reachable == !0);
self
}
pub fn all_useful(&self) -> bool {
self.all_useful
}
pub fn all_productive(&self) -> bool {
self.all_productive
}
}
impl<'a, G> Usefulness<&'a mut G>
where
G: RuleContainer + Default,
&'a G: RuleContainerRef<'a, Target = G>,
&'a mut G: RuleContainerMut<'a, Target = G>,
{
pub fn useless_rules(&'a self) -> UselessRules<'a, G, <&'a G as RuleContainerRef<'a>>::Rules> {
UselessRules {
rules: self.grammar.rules(),
usefulness: self,
}
}
pub fn remove_useless_rules(&mut self) {
if !self.all_useful {
let productivity = &self.productivity;
let reachable_syms = &self.reachable_syms;
self.grammar.retain(|lhs, rhs, _| {
let productive = rhs.iter().all(|sym| productivity[sym.usize()]);
let reachable = reachable_syms[lhs.usize()];
productive && reachable
});
}
}
}
impl<'a, G> Iterator for UselessRules<'a, G, <&'a G as RuleContainerRef<'a>>::Rules>
where
G: RuleContainer + Default + 'a,
&'a G: RuleContainerRef<'a, Target = G>,
{
type Item = UselessRule<<<&'a G as RuleContainerRef<'a>>::Rules as Iterator>::Item>;
fn next(&mut self) -> Option<Self::Item> {
if self.usefulness.all_useful {
return None;
}
for rule in &mut self.rules {
let lhs = rule.lhs().usize();
let usefulness = &self.usefulness;
let productive = rule
.rhs()
.iter()
.all(|sym| usefulness.productivity[sym.usize()]);
let reachable = usefulness.reachable_syms[lhs];
if !reachable || !productive {
return Some(UselessRule {
rule: rule,
unreachable: !reachable,
unproductive: !productive,
});
}
}
None
}
}