use std::collections::HashMap;
use std::collections::hash_map::Entry;
use history::{RewriteSequence, HistorySource, NullHistory};
use rule::builder::RuleBuilder;
use rule::container::RuleContainer;
use sequence::{Separator, Sequence};
use sequence::Separator::{Trailing, Proper, Liberal};
use sequence::builder::SequenceRuleBuilder;
use sequence::destination::SequenceDestination;
use symbol::Symbol;
pub struct SequencesToProductions<H, D>
where H: RewriteSequence,
D: RuleContainer
{
destination: D,
stack: Vec<Sequence<NullHistory>>,
map: HashMap<PartialSequence, Symbol>,
top_history: Option<H>,
at_top: bool,
rhs: Option<Symbol>,
separator: Option<Symbol>,
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
struct PartialSequence {
rhs: Symbol,
start: u32,
end: Option<u32>,
separator: Separator,
}
impl<H, D> SequenceDestination<H> for SequencesToProductions<H, D>
where D: RuleContainer<History = H::Rewritten>,
H: Clone + RewriteSequence,
H::Rewritten: Clone
{
fn add_sequence(&mut self, seq: Sequence<H>) {
self.rewrite(seq);
}
}
impl<H, D> SequencesToProductions<H, D>
where D: RuleContainer<History = H::Rewritten>,
H: Clone + RewriteSequence,
H::Rewritten: Clone
{
pub fn new(destination: D) -> Self {
SequencesToProductions {
destination: destination,
stack: vec![],
map: HashMap::new(),
top_history: None,
at_top: false,
rhs: None,
separator: None,
}
}
pub fn rewrite_sequences(sequence_rules: &[Sequence<H>], rules: D) {
let mut rewrite = SequenceRuleBuilder::new(SequencesToProductions::new(rules));
for rule in sequence_rules {
rewrite = rewrite.sequence(rule.lhs)
.separator(rule.separator)
.inclusive(rule.start, rule.end)
.rhs_with_history(rule.rhs, &rule.history);
}
}
pub fn rewrite(&mut self, top: Sequence<H>) {
self.stack.clear();
self.map.clear();
self.top_history = Some(top.history);
let top = Sequence {
lhs: top.lhs,
rhs: top.rhs,
start: top.start,
end: top.end,
separator: top.separator,
history: NullHistory,
};
self.rhs = Some(top.rhs);
self.separator = top.separator.into();
self.at_top = true;
self.reduce(top);
self.at_top = false;
while let Some(seq) = self.stack.pop() {
assert!(seq.start <= seq.end.unwrap_or(!0));
self.reduce(seq);
}
}
fn rule(&mut self, lhs: Symbol) -> RuleBuilder<&mut D, DefaultSeqHistory<H>> {
let default = DefaultSeqHistory {
top_history: self.top_history.as_ref().unwrap(),
at_top: self.at_top,
elem: self.rhs.unwrap(),
separator: self.separator,
};
RuleBuilder::new(&mut self.destination).rule(lhs).default_history(default)
}
fn recurse(&mut self, seq: &Sequence<NullHistory>) -> Symbol {
let sym_source = &mut self.destination;
let partial = PartialSequence {
rhs: seq.rhs,
separator: seq.separator,
start: seq.start,
end: seq.end,
};
match self.map.entry(partial) {
Entry::Vacant(vacant) => {
let lhs = sym_source.sym();
vacant.insert(lhs);
self.stack.push(Sequence {
lhs: lhs,
rhs: seq.rhs,
start: seq.start,
end: seq.end,
separator: seq.separator,
history: seq.history,
});
lhs
}
Entry::Occupied(lhs) => *lhs.get(),
}
}
fn reduce(&mut self, sequence: Sequence<NullHistory>) {
let Sequence { lhs, rhs, start, end, separator, .. } = sequence;
match (separator, start, end) {
(Liberal(sep), _, _) => {
let sym1 = self.recurse(&sequence.clone().separator(Proper(sep)));
let sym2 = self.recurse(&sequence.clone().separator(Trailing(sep)));
self.rule(lhs)
.rhs([sym1])
.rhs([sym2]);
}
(_, _, _) if start == 0 => {
self.rule(lhs).rhs([]);
if end != Some(0) {
let sym = self.recurse(&sequence.inclusive(1, end));
self.rule(lhs).rhs([sym]);
}
}
(Trailing(sep), _, _) => {
let sym = self.recurse(&sequence.separator(Proper(sep)));
self.rule(lhs).rhs([sym, sep]);
}
(_, _, _) if start == 1 && end == None => {
if self.at_top {
let rec = self.recurse(&sequence);
self.rule(lhs).rhs([rec]);
} else {
self.rule(lhs).rhs([rhs]);
if let Proper(sep) = separator {
self.rule(lhs).rhs([lhs, sep, rhs]);
} else {
self.rule(lhs).rhs([lhs, rhs]);
}
}
}
(_, _, _) if (start, end) == (1, Some(1)) => {
self.rule(lhs).rhs([rhs]);
}
(_, _, _) if (start, end) == (1, Some(2)) => {
let sym1 = self.recurse(&sequence.clone().inclusive(1, Some(1)));
let sym2 = self.recurse(&sequence.clone().inclusive(2, Some(2)));
self.rule(lhs)
.rhs([sym1])
.rhs([sym2]);
}
(_, _, Some(end)) if start == 1 => {
let pow2 = end.next_power_of_two() / 2;
let (seq1, block, seq2) = (sequence.clone().inclusive(1, Some(pow2)),
sequence.clone().inclusive(pow2, Some(pow2)),
sequence.clone().inclusive(1, Some(end - pow2)));
let rhs1 = self.recurse(&seq1);
let block = self.recurse(&block.separator(separator.prefix_separator()));
let rhs2 = self.recurse(&seq2);
self.rule(lhs).rhs([rhs1])
.rhs([block, rhs2]);
}
(Proper(sep), start, end) if start == 2 && end == Some(2) => {
self.rule(lhs).rhs([rhs, sep, rhs]);
}
(_, _, _) if start == 2 && end == Some(2) => {
self.rule(lhs).rhs([rhs, rhs]);
}
(_, _, end) if start >= 2 => {
let (seq1, seq2) = if Some(start) == end {
let pow2 = start.next_power_of_two() / 2;
(sequence.clone().inclusive(pow2, Some(pow2)),
sequence.clone().inclusive(start - pow2, Some(start - pow2)))
} else {
(sequence.clone().inclusive(start - 1, Some(start - 1)),
sequence.clone().inclusive(1, end.map(|end| end - start + 1)))
};
let (rhs1, rhs2) = (self.recurse(&seq1.separator(separator.prefix_separator())),
self.recurse(&seq2.separator(separator)));
self.rule(lhs).rhs([rhs1, rhs2]);
}
_ => panic!(),
}
}
}
struct DefaultSeqHistory<'a, H: 'a>
where H: RewriteSequence
{
top_history: &'a H,
at_top: bool,
elem: Symbol,
separator: Option<Symbol>,
}
impl<'a, H> HistorySource<H::Rewritten> for DefaultSeqHistory<'a, H>
where H: RewriteSequence,
H::Rewritten: Clone
{
fn build(&mut self, _lhs: Symbol, rhs: &[Symbol]) -> H::Rewritten {
if self.at_top {
self.top_history.top(self.elem, self.separator, rhs)
} else {
self.top_history.bottom(self.elem, self.separator, rhs)
}
}
}