use std::fmt;
use terms::Term;
use crate::{
Symbol,
State,
NoLabel,
bottom_up::{
Automaton,
Configuration,
}
};
#[derive(Debug, Clone, Copy)]
pub struct Killed;
pub trait LanguageState<F: Symbol, E: ?Sized>: State + Sized {
fn configurations<'a>(&self, env: &'a E) -> Box<dyn Iterator<Item = Configuration<F, Self>> + 'a>;
}
impl<F: Symbol, Q: State> LanguageState<F, Automaton<F, Q, NoLabel>> for Q {
fn configurations<'a>(&self, aut: &'a Automaton<F, Q, NoLabel>) -> Box<dyn Iterator<Item = Configuration<F, Self>> + 'a> {
Box::new(aut.configurations_for_state(self).map(|(conf, _)| conf.clone()))
}
}
impl<'e, F: Symbol, Q: State> LanguageState<F, [&'e Automaton<F, Q, NoLabel>]> for Indexed<Q> {
fn configurations<'a>(&self, automata: &'a [&'e Automaton<F, Q, NoLabel>]) -> Box<dyn Iterator<Item = Configuration<F, Self>> + 'a> {
let index = self.1;
let aut = automata[index];
Box::new(aut.configurations_for_state(&self.0).map(move |(conf, _)| {
let states = conf.states().iter().map(|q| Indexed((*q).clone(), index)).collect();
Configuration(conf.symbol().clone(), states)
}))
}
}
fn add_language_state<'a, F: Symbol, E, Q: LanguageState<F, E>>(q: Q, env: &'a E, aut: &mut Automaton<F, Q, NoLabel>) {
if !aut.includes(&q) {
for conf in q.configurations(env) {
aut.add(conf.clone(), NoLabel, q.clone());
for sub in conf.1.into_iter() {
add_language_state(sub, env, aut);
}
}
}
}
impl<'a, F: Symbol, E, Q: LanguageState<F, E>> From<(Q, &'a E)> for Automaton<F, Q, NoLabel> {
fn from((q, env): (Q, &'a E)) -> Automaton<F, Q, NoLabel> {
let mut aut = Automaton::new();
add_language_state(q.clone(), env, &mut aut);
aut.set_final(q);
aut
}
}
impl<'a, F: Symbol, Q: LanguageState<F, ()>> From<Q> for Automaton<F, Q, NoLabel> {
fn from(q: Q) -> Automaton<F, Q, NoLabel> {
let mut aut = Automaton::new();
add_language_state(q.clone(), &(), &mut aut);
aut.set_final(q);
aut
}
}
#[derive(Clone, Debug, Hash, PartialEq, Eq)]
pub struct Indexed<Q: State>(pub Q, pub usize);
impl<T: State + fmt::Display> fmt::Display for Indexed<T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{}.{}", self.0, self.1)
}
}
#[cfg(not(debug_assertions))]
pub trait SearchPattern<F: Symbol, Q: State, C: SearchContext>: Clone {
fn matches(&self, depth: usize, context: &C, q: &Q, configuration: &Configuration<F, Q>) -> Option<(C, Vec<Self>)>;
}
#[cfg(debug_assertions)]
pub trait SearchPattern<F: Symbol, Q: State, C: SearchContext>: Clone + fmt::Display + fmt::Debug {
fn matches(&self, depth: usize, context: &C, q: &Q, configuration: &Configuration<F, Q>) -> Option<(C, Vec<Self>)>;
}
#[cfg(not(debug_assertions))]
pub trait SearchContext: Clone {
fn looping(&self) -> bool;
}
#[cfg(debug_assertions)]
pub trait SearchContext: Clone + fmt::Display + fmt::Debug {
fn looping(&self) -> bool;
}
#[cfg(debug_assertions)]
struct DebugInfos {
depth: usize
}
#[derive(Hash, PartialEq, Eq)]
struct Item<F: Symbol, Q: State, C, P>(Configuration<F, Q>, C, Vec<P>);
impl<F: Symbol + fmt::Display, Q: State + fmt::Display, C: fmt::Display, P: fmt::Display> fmt::Debug for Item<F, Q, C, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "({}/{}/{})", self.0, self.1, PList(&self.2))
}
}
pub struct TermFragment<'a, E: ?Sized, F: Symbol, Q: LanguageState<F, E>, C: SearchContext, P: SearchPattern<F, Q, C>> {
env: &'a E,
context: C,
patterns: Vec<P>,
leaves: Vec<Q>,
leaves_configurations: Vec<Box<dyn Iterator<Item = Configuration<F, Q>> + 'a>>,
current: Vec<Item<F, Q, C, P>>,
next_fragment: Option<Box<TermFragment<'a, E, F, Q, C, P>>>,
visited: bool,
depth: usize,
kill_signal: Option<crossbeam_channel::Receiver<()>>
}
impl<'a, E: ?Sized, F: Symbol, Q: LanguageState<F, E>, C: SearchContext, P: SearchPattern<F, Q, C>> TermFragment<'a, E, F, Q, C, P> {
pub fn new(env: &'a E, depth: usize, context: C, leaves: Vec<Q>, patterns: Vec<P>, kill_signal: Option<crossbeam_channel::Receiver<()>>) -> TermFragment<'a, E, F, Q, C, P> {
let leaves_configurations = if leaves.is_empty() {
Vec::new()
} else {
vec![leaves[0].configurations(env)]
};
TermFragment {
env,
context,
patterns,
leaves,
leaves_configurations,
current: Vec::new(),
next_fragment: None,
visited: false,
depth,
kill_signal
}
}
}
impl<'a, E: ?Sized, F: Symbol, Q: LanguageState<F, E>, C: SearchContext, P: SearchPattern<F, Q, C>> Iterator for TermFragment<'a, E, F, Q, C, P> {
type Item = Result<Vec<Term<F>>, Killed>;
fn next(&mut self) -> Option<Result<Vec<Term<F>>, Killed>> {
loop {
if let Some(kill_signal) = self.kill_signal.as_ref() {
if let Ok(()) = kill_signal.try_recv() {
return Some(Err(Killed))
}
}
if self.leaves.is_empty() {
if self.visited {
return None
} else {
self.visited = true;
return Some(Ok(Vec::new()))
}
} else {
let current_context = match self.current.last() {
Some(Item(_, context, _)) => context,
None => &self.context
};
if self.current.len() < self.leaves.len() {
let i = self.current.len();
let j = i + 1;
match self.leaves_configurations.last_mut().unwrap().next() {
Some(conf) => {
if let Some((next_context, sub_patterns)) = self.patterns[i].matches(self.depth, ¤t_context, &self.leaves[i], &conf) {
assert!(conf.states().len() == sub_patterns.len());
self.current.push(Item(conf, next_context, sub_patterns));
if j < self.leaves.len() {
let confs = self.leaves[j].configurations(self.env);
self.leaves_configurations.push(confs);
}
} else {
}
},
None => {
if i > 0 {
self.current.pop();
self.leaves_configurations.pop();
} else {
return None
}
}
}
} else {
match self.next_fragment {
Some(ref mut frag) => {
match frag.next() {
Some(Err(Killed)) => return Some(Err(Killed)),
Some(Ok(mut sub_terms)) => {
sub_terms.reverse();
let mut terms = Vec::with_capacity(self.current.len());
for Item(Configuration(f, sub_states), _, _) in self.current.iter() {
let mut subs = Vec::with_capacity(sub_states.len());
for _ in sub_states.iter() {
subs.push(sub_terms.pop().unwrap());
}
terms.push(Term::new(f.clone(), subs))
}
return Some(Ok(terms))
},
None => {
self.next_fragment = None;
self.current.pop();
}
}
},
None if !current_context.looping() => {
let mut leaves = Vec::new();
let mut patterns = Vec::new();
for Item(Configuration(_, sub_states), _, sub_patterns) in self.current.iter() {
for q in sub_states.iter() {
leaves.push(q.clone())
}
for p in sub_patterns.iter() {
patterns.push(p.clone())
}
}
let next_fragment = TermFragment::new(self.env, self.depth + 1, current_context.clone(), leaves, patterns, self.kill_signal.clone());
self.next_fragment = Some(Box::new(next_fragment))
},
None => {
self.current.pop();
}
}
}
}
}
}
}
struct PList<'a, T: fmt::Display>(&'a [T]);
impl<'a, T: fmt::Display> fmt::Display for PList<'a, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
match self.0.split_first() {
Some((head, tail)) => {
head.fmt(f)?;
for e in tail.iter() {
write!(f, ",")?;
e.fmt(f)?;
}
Ok(())
},
None => Ok(())
}
}
}
#[cfg(debug_assertions)]
impl<'a, E: ?Sized, F: Symbol, Q: LanguageState<F, E>, C: SearchContext, P: SearchPattern<F, Q, C>> fmt::Display for TermFragment<'a, E, F, Q, C, P> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "({}) {} with context {}", PList(&self.patterns), PList(&self.leaves), self.context)
}
}