use std::fmt;
use std::rc::Rc;
use crate::earley::Chart;
use crate::rules::{Grammar, Rule};
use crate::syntree::{Constituent, SynTree, Word};
use crate::utils::combinations;
#[derive(Debug, Clone, PartialEq)]
pub struct ForestState {
rule: Rc<Rule>,
span: (usize, usize),
}
impl ForestState {
pub fn new(rule: &Rc<Rule>, start: usize, end: usize) -> Self {
Self {
rule: rule.clone(),
span: (start, end),
}
}
}
impl fmt::Display for ForestState {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}..{}: {}", self.span.0, self.span.1, self.rule)
}
}
impl Into<Constituent<Rc<Rule>>> for &ForestState {
fn into(self) -> Constituent<Rc<Rule>> {
Constituent {
value: self.rule.clone(),
span: self.span,
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct Forest(Vec<Vec<ForestState>>);
impl Forest {
pub fn len(&self) -> usize {
self.0.len()
}
pub fn is_empty(&self) -> bool {
self.len() == 0
}
fn subtree_is_complete(node: &SynTree<Rc<Rule>, String>) -> bool {
if let Some((cons, children)) = node.get_branch() {
cons.value.productions.len() == children.len()
} else {
true
}
}
fn extend_out(
&self,
g: &Grammar,
rule: &Rule,
prod_idx: usize,
search_start: usize,
search_end: usize,
) -> Vec<Vec<SynTree<Rc<Rule>, String>>> {
if prod_idx == rule.len() && search_start == search_end {
return vec![Vec::new()];
} else if prod_idx == rule.len() || search_start == search_end {
return Vec::new();
}
let next_production = &rule.productions[prod_idx];
if next_production.is_nonterminal() {
let wanted_symbol = &next_production.symbol;
self.0[search_start]
.iter()
.filter(|s| s.span.1 <= search_end && wanted_symbol == &s.rule.symbol)
.map(|state| {
self
.extend_out(g, rule, prod_idx + 1, state.span.1, search_end)
.into_iter()
.map(move |mut seq| {
seq.insert(0, SynTree::Branch(state.into(), Vec::new()));
seq
})
})
.flatten()
.collect()
} else {
let leaf = SynTree::Leaf(Word {
value: next_production.symbol.to_string(),
span: (search_start, search_start + 1),
});
self
.extend_out(g, rule, prod_idx + 1, search_start + 1, search_end)
.into_iter()
.map(move |mut seq| {
seq.insert(0, leaf.clone());
seq
})
.collect()
}
}
fn make_trees(
&self,
g: &Grammar,
tree: SynTree<Rc<Rule>, String>,
) -> Vec<SynTree<Rc<Rule>, String>> {
if Self::subtree_is_complete(&tree) {
vec![tree]
} else {
let (cons, _) = tree.get_branch().unwrap();
self
.extend_out(g, &cons.value, 0, cons.span.0, cons.span.1)
.into_iter()
.map(|children| {
let child_sets = children
.into_iter()
.map(|child| self.make_trees(g, child))
.collect::<Vec<_>>();
combinations(&child_sets)
.into_iter()
.map(|set| SynTree::Branch(cons.clone(), set))
})
.flatten()
.collect::<Vec<_>>()
}
}
pub fn trees(&self, g: &Grammar) -> Vec<SynTree<Rc<Rule>, String>> {
if self.is_empty() {
Vec::new()
} else {
let root_states = self.0[0]
.iter()
.filter(|state| state.span.1 == self.len() && state.rule.symbol == g.start)
.map(|state| SynTree::Branch(state.into(), Vec::new()));
root_states.fold(Vec::<SynTree<Rc<Rule>, String>>::new(), |mut prev, tree| {
let mut trees = self.make_trees(g, tree);
prev.append(&mut trees);
prev
})
}
}
}
impl From<Chart> for Forest {
fn from(chart: Chart) -> Self {
let mut v = vec![Vec::new(); chart.len() - 1];
for (k, states) in chart.into_iter() {
for state in states {
if !state.lr0.is_active() {
v.get_mut(state.origin)
.expect("origin > input len")
.push(ForestState::new(&state.lr0.rule, state.origin, k));
}
}
}
Self(v)
}
}
impl fmt::Display for Forest {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
for k in 0..self.len() {
writeln!(f, "Origin {}:", k)?;
for fs in self.0[k].iter() {
writeln!(f, " {}", fs)?;
}
}
Ok(())
}
}
#[test]
fn test_parse_chart() {
let g: Grammar = r#"
S -> x
S -> S S
"#
.parse()
.unwrap();
let get_rule_with_len = |len: usize| {
g.rules
.get("S")
.unwrap()
.iter()
.find(|r| r.len() == len)
.unwrap()
};
let rule1 = get_rule_with_len(1);
let rule2 = get_rule_with_len(2);
let forest: Forest = crate::earley::parse_chart(&g, &["x", "x", "x"]).into();
assert_eq!(
forest,
Forest(vec![
vec![
ForestState::new(&rule1, 0, 1),
ForestState::new(&rule2, 0, 2),
ForestState::new(&rule2, 0, 3),
],
vec![
ForestState::new(&rule1, 1, 2),
ForestState::new(&rule2, 1, 3),
],
vec![ForestState::new(&rule1, 2, 3)],
])
);
println!("{}", forest);
}
#[test]
fn test_tree_generation() {
let g = r#"
S -> x
S -> S S
"#
.parse()
.unwrap();
let forest: Forest = crate::earley::parse_chart(&g, &["x", "x", "x"]).into();
let trees = forest.trees(&g);
for tree in trees.iter() {
println!("{}\n", tree);
}
assert_eq!(trees.len(), 2);
}