tree_automata/bottom_up/
mod.rs

1use std::fmt;
2use std::collections::{hash_set, hash_map, HashSet, HashMap};
3use terms::{
4    PatternLike,
5    PatternLikeKind
6};
7
8use crate::{
9    utils::combinations,
10    Symbol,
11    State,
12    Label,
13    Ranked,
14    NoLabel,
15    Labeled,
16    Language,
17    //LanguageState,
18    ConfigurationIterator
19};
20
21pub mod macros;
22pub mod search;
23pub mod width_search;
24
25pub use search::*;
26pub use width_search::*;
27
28/// Tree automaton configuration.
29#[derive(Hash, PartialEq, Eq, Clone, Debug)]
30pub struct Configuration<F, Q: State>(pub F, pub Vec<Q>);
31
32impl<F, Q: State> Configuration<F, Q> {
33    pub fn symbol(&self) -> &F {
34        &self.0
35    }
36
37    pub fn states(&self) -> &[Q] {
38        &self.1
39    }
40
41    pub fn len(&self) -> usize {
42        self.1.len()
43    }
44
45    pub fn signature(&self) -> (&F, usize) {
46        (&self.0, self.1.len())
47    }
48
49    pub fn map<R: State, M>(&self, g: M) -> Configuration<F, R> where M: Fn(&Q) -> R, F: Clone {
50        let states = self.1.iter().map(|q| g(q)).collect();
51        Configuration(self.0.clone(), states)
52    }
53}
54
55impl<F: fmt::Display, Q: State + fmt::Display> fmt::Display for Configuration<F, Q> {
56    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
57        self.0.fmt(f)?;
58        match self.1.split_first() {
59            Some((head, tail)) => {
60                write!(f, "({}", head)?;
61                for e in tail.iter() {
62                    write!(f, ", {}", e)?;
63                }
64                write!(f, ")")
65            },
66            None => Ok(())
67        }
68    }
69}
70
71pub type Configurations<'a, F, Q, L> = hash_set::Iter<'a, Labeled<Configuration<F, Q>, L>>;
72
73pub struct Transifions<'a, F, Q: State, L: Label> {
74    it: hash_map::Iter<'a, Q, HashSet<Labeled<Configuration<F, Q>, L>>>,
75    current: Option<(&'a Q, Configurations<'a, F, Q, L>)>
76}
77
78impl<'a, F, Q: State, L: Label> Transifions<'a, F, Q, L> {
79    fn new(aut: &'a Automaton<F, Q, L>) -> Transifions<'a, F, Q, L> {
80        Transifions {
81            it: aut.state_configurations.iter(),
82            current: None
83        }
84    }
85}
86
87impl<'a, F, Q: State, L: Label> Iterator for Transifions<'a, F, Q, L> {
88    type Item = (&'a Configuration<F, Q>, &'a L, &'a Q);
89
90    fn next(&mut self) -> Option<Self::Item> {
91        loop {
92            match self.current {
93                Some((q, ref mut configurations)) => {
94                    match configurations.next() {
95                        Some((configuration, label)) => {
96                            return Some((configuration, label, q))
97                        },
98                        None => self.current = None
99                    }
100                },
101                None => {
102                    match self.it.next() {
103                        Some((q, configurations)) => self.current = Some((q, configurations.iter())),
104                        None => return None
105                    }
106                }
107            }
108        }
109    }
110}
111
112/// Tree automaton.
113#[derive(Clone)]
114pub struct Automaton<F, Q: State, L: Label> {
115    /// An empty set of labeled states used to return an empty iterator.
116    dummy_states: HashSet<Labeled<Q, L>>,
117
118    /// An empty set of labeled configurations used to return an empty iterator.
119    dummy_configurations: HashSet<Labeled<Configuration<F, Q>, L>>,
120
121    /// For each configuration t, associates the set of states such that t -> q.
122    configuration_states: HashMap<Configuration<F, Q>, HashSet<Labeled<Q, L>>>,
123
124    /// For each state q, associates the set of configurations such that t -> q.
125    state_configurations: HashMap<Q, HashSet<Labeled<Configuration<F, Q>, L>>>,
126
127    // /// For each configuration, associate every known labeled version.
128    // labeled_configurations: HashMap<Configuration<F, Q>, HashSet<Labeled<Configuration<F, Q>, L>>>,
129
130    /// Final states of the automaton.
131    final_states: HashSet<Q>
132}
133
134pub type States<'a, F, Q, L> = hash_map::Keys<'a, Q, HashSet<Labeled<Configuration<F, Q>, L>>>;
135
136impl<F: Symbol, Q: State, L: Label> Language<F> for Automaton<F, Q, L> {
137    // ...
138}
139
140impl<F: Symbol, Q: State, L: Label> Automaton<F, Q, L> {
141    // type Configuration = Configuration<F, Q>;
142
143    /// Create a new empty automaton.
144    pub fn new() -> Automaton<F, Q, L> {
145        Automaton {
146            dummy_states: HashSet::new(),
147            dummy_configurations: HashSet::new(),
148            configuration_states: HashMap::new(),
149            state_configurations: HashMap::new(),
150            // labeled_configurations: HashMap::new(),
151            final_states: HashSet::new()
152        }
153    }
154
155    /// Return the number of states in the automaton.
156    pub fn len(&self) -> usize {
157        self.state_configurations.len()
158    }
159
160    pub fn states(&self) -> States<F, Q, L> {
161        self.state_configurations.keys()
162    }
163
164    /// Return an iterator to the final states of the automaton.
165    pub fn final_states(&self) -> hash_set::Iter<Q> {
166        self.final_states.iter()
167    }
168
169    /// Set the given state a final state.
170    /// Return `true` if the state was not already final.
171    /// Return `false` if the state was already a final state.
172    pub fn set_final(&mut self, q: Q) -> bool {
173        self.final_states.insert(q)
174    }
175
176    /// Checks if the given state is in the automaton.
177    /// Return true if at least one configuration is attached to the state in the automaton.
178    pub fn includes(&self, q: &Q) -> bool {
179        self.state_configurations.get(q).is_some()
180    }
181
182    pub fn transitions(&self) -> Transifions<F, Q, L> {
183        Transifions::new(self)
184    }
185
186    /// Return an iterator over the configurations connected to the given state.
187    pub fn configurations_for_state(&self, q: &Q) -> Configurations<F, Q, L> {
188        match self.state_configurations.get(q) {
189            Some(confs) => confs.iter(),
190            None => self.dummy_configurations.iter()
191        }
192    }
193
194    // /// Return an iterator over the configurations compatible with the given configuration.
195    // pub fn configurations_for<'a>(&'a self, source: &'a Configuration<F, Q>) -> Configurations<F, Q, L> {
196    //     // match source.kind() {
197    //     //     PatternKind::Var(q) => self.configurations_for_state(q),
198    //     //     _ =>
199    //     // }
200    //     self.labeled_configurations(source)
201    // }
202
203    // /// Return an iterator over the known labeled versions of the given configuration.
204    // pub fn labeled_configurations(&self, conf: &Configuration<F, Q>) -> Configurations<F, Q, L> {
205    //     match self.labeled_configurations.get(conf) {
206    //         Some(confs) => confs.iter(),
207    //         None => self.dummy_configurations.iter()
208    //     }
209    // }
210
211    /// Return an iterator over the states connected to the given configuration.
212    pub fn states_for_configuration(&self, conf: &Configuration<F, Q>) -> hash_set::Iter<Labeled<Q, L>> {
213        match self.configuration_states.get(conf) {
214            Some(states) => states.iter(),
215            None => self.dummy_states.iter()
216        }
217    }
218
219    /// Add a new transition to the automaton.
220    pub fn add(&mut self, conf: Configuration<F, Q>, label: L, state: Q) {
221        match self.configuration_states.get_mut(&conf) {
222            Some(states) => {
223                states.insert((state.clone(), label.clone()));
224            },
225            None => {
226                let mut states = HashSet::new();
227                states.insert((state.clone(), label.clone()));
228                self.configuration_states.insert(conf.clone(), states);
229            }
230        }
231
232        // match self.labeled_configurations.get_mut(&conf) {
233        //     Some(labeled_confs) => {
234        //         labeled_confs.insert((conf.clone(), label.clone()));
235        //     },
236        //     None => {
237        //         let mut labeled_confs = HashSet::new();
238        //         labeled_confs.insert((conf.clone(), label.clone()));
239        //         self.labeled_configurations.insert(conf.clone(), labeled_confs);
240        //     }
241        // }
242
243        match self.state_configurations.get_mut(&state) {
244            Some(configurations) => {
245                configurations.insert((conf, label));
246            },
247            None => {
248                let mut configurations = HashSet::new();
249                configurations.insert((conf, label));
250                self.state_configurations.insert(state, configurations);
251            }
252        }
253    }
254
255    /// Add new transitions in the automaton by adding and normalizing the given configuration,
256    /// label and state.
257    pub fn add_normalized<P: PatternLike<F, Q>, N>(&mut self, pattern: &P, normalizer: &mut N) -> Q
258    where N: FnMut(&Configuration<F, Q>) -> Labeled<Q, L> {
259        match pattern.kind() {
260            PatternLikeKind::Cons(f, l) => {
261                let mut normalized_l = Vec::with_capacity(l.len());
262                for sub_conf in l.iter() {
263                    let q = match sub_conf.kind() {
264                        PatternLikeKind::Var(q) => q.clone(),
265                        _ => {
266                            self.add_normalized(sub_conf, normalizer)
267                        }
268                    };
269                    normalized_l.push(q);
270                }
271
272                let normalized_conf = Configuration(f.clone(), normalized_l);
273
274                if let Some((state, _)) = self.states_for_configuration(&normalized_conf).next() {
275                    state.clone()
276                } else {
277                    let (state, label) = (*normalizer)(&normalized_conf);
278                    self.add(normalized_conf, label, state.clone());
279                    state
280                }
281            },
282            PatternLikeKind::Var(_) => {
283                panic!("epsilon transitions are not allowed!")
284            }
285        }
286    }
287
288    // /// Find a run in the automaton that recognizes the given pattern.
289    // pub fn find<X>(&self, pattern: Pattern<F, X>) -> Option<Configuration<F, Labeled<Q, L>>> {
290    //     panic!("TODO")
291    // }
292
293    /// Automata common configurations.
294    pub fn common_configurations<'a>(
295        automata: &'a [&'a Automaton<F, Q, L>],
296        positions: &'a [Q]
297    ) -> CommonConfigurations<'a, F, Q, L> {
298        CommonConfigurations::new(automata, positions)
299    }
300
301    // / Return an iterator over all the synchronized runs between the given automata,
302    // / starting from the given positions, matching the given patterns and with the given
303    // / constraints.
304    // pub fn synchronized_runs<'a, P: pattern::Meta<F>>(
305    //     automata: &'a [&'a Automaton<F, Q, L>],
306    //     positions: &'a [Configuration<F, Q>],
307    //     patterns: &'a [P],
308    //     constraints: &'a P::Constraints
309    // ) -> SynchronizedRuns<'a, F, Q, L, P>
310    // where P: Clone, P::Constraints: Clone
311    // {
312    //     SynchronizedRuns::new(automata, positions, patterns, constraints)
313    // }
314
315    /// Return an iterator over the representative terms of the automaton.
316    /// The representatives terms are all the terms recognized by the automaton *without cycle*.
317    /// Together they trigger every transition of the automaton.
318    pub fn representatives(&self) -> Representatives<F, Q, L> {
319        Representatives::new(self)
320    }
321
322    /// Complement the automaton.
323    /// This will invert the set of final and non-final states.
324    /// If the automaton is complete, then `self` becomes its own complement.
325    pub fn complement(&mut self) {
326        let states: HashSet<Q> = self.states().cloned().collect();
327        let new_final_states = states.difference(&self.final_states).cloned().collect();
328        self.final_states = new_final_states;
329    }
330
331    /// Return the alphabet on which this automaton is defined.
332    pub fn alphabet(&self) -> HashSet<F> {
333        let mut alphabet = HashSet::new();
334        for (Configuration(f, _), _, _) in self.transitions() {
335            alphabet.insert(f.clone());
336        }
337
338        alphabet
339    }
340
341    pub fn map_states<R: State, M>(&self, g: M) -> Automaton<F, R, L> where M: Fn(&Q) -> R {
342        let mut configuration_states: HashMap<Configuration<F, R>, HashSet<Labeled<R, L>>> = HashMap::new();
343        for (conf, states) in self.configuration_states.iter() {
344            let conf = conf.map(|q| g(q));
345            let states: HashSet<Labeled<R, L>> = states.iter().map(|(q, l)| (g(q), l.clone())).collect();
346            match configuration_states.get_mut(&conf) {
347                Some(conf_states) => {
348                    conf_states.extend(states.into_iter());
349                },
350                None => {
351                    configuration_states.insert(conf, states);
352                }
353            }
354        }
355
356        let mut state_configurations: HashMap<R, HashSet<Labeled<Configuration<F, R>, L>>> = HashMap::new();
357        for (state, confs) in self.state_configurations.iter() {
358            let state = g(state);
359            let confs: HashSet<Labeled<Configuration<F, R>, L>> = confs.iter().map(|(conf, l)| (conf.map(|q| g(q)), l.clone())).collect();
360            match state_configurations.get_mut(&state) {
361                Some(state_confs) => {
362                    state_confs.extend(confs.into_iter());
363                },
364                None => {
365                    state_configurations.insert(state, confs);
366                }
367            }
368        }
369
370        let mut final_states = HashSet::new();
371        for q in self.final_states.iter() {
372            final_states.insert(g(q));
373        }
374
375        Automaton {
376            dummy_states: HashSet::new(),
377            dummy_configurations: HashSet::new(),
378            configuration_states: configuration_states,
379            state_configurations: state_configurations,
380            final_states: final_states
381        }
382    }
383}
384
385impl<F: Symbol, Q: State> Automaton<F, Q, NoLabel> {
386    /// Complete the language with the given automaton.
387    /// Each state of `self` must be mappable into a state of `lang`, and each state of `lang`
388    /// must be transformed into a dead state of `self`.
389    pub fn complete_with<'a, A: Iterator<Item=&'a F>, R: State>(&mut self, alphabet: A, lang: &Automaton<F, R, NoLabel>) where F: 'a + Ranked, R: From<Q>, Q: From<R> {
390        let mut states: Vec<Q> = self.states().map(|q| (*q).clone()).collect();
391        states.extend(lang.states().map(|r| r.clone().into()));
392
393        for f in alphabet {
394            let indexes: Vec<usize> = (0..f.arity()).collect();
395            for states in combinations(&indexes, |_| states.clone().into_iter()) {
396                let conf = Configuration(f.clone(), states.clone());
397                match self.states_for_configuration(&conf).next() {
398                    Some(_) => (),
399                    None => {
400                        let parent_states: Vec<R> = states.iter().map(|q| (*q).clone().into()).collect();
401                        if let Some((r, _)) = lang.states_for_configuration(&Configuration(f.clone(), parent_states)).next() {
402                            self.add(conf, NoLabel, (*r).clone().into());
403                        }
404                    }
405                }
406            }
407        }
408    }
409}
410
411// fn map<'a, F: 'a + Clone, Q: 'a + State, L: 'a + Label>(conf: &'a Labeled<Configuration<F, Q>, L>) -> Labeled<Configuration<F, Q>, L> {
412//     conf.clone()
413// }
414
415pub struct CloneConfigurations<'a, F: Symbol, Q: State, L: Label> {
416    it: Configurations<'a, F, Q, L>
417}
418
419impl<'a, F: Symbol, Q: State, L: Label> Iterator for CloneConfigurations<'a, F, Q, L> {
420    type Item = Configuration<F, Q>;
421
422    fn next(&mut self) -> Option<Configuration<F, Q>> {
423        match self.it.next() {
424            Some((conf, _)) => Some(conf.clone()),
425            None => None
426        }
427    }
428}
429
430impl<'a, F: Symbol, Q: State, L: Label> ConfigurationIterator<'a, F, Q> for CloneConfigurations<'a, F, Q, L> {
431    // ...
432}
433
434// impl<F: Symbol, Q: State, L: Label> LanguageState<F, Automaton<F, Q, L>> for Q {
435//     // type Configurations<'a> = std::iter::Map<Configurations<'a, F, Q, L>, fn(&'a Labeled<Configuration<F, Q>, L>) -> Configuration<F, Q>> where L: 'a;
436//
437//     fn configurations<'a>(&'a self, lang: &'a Automaton<F, Q, L>) -> Box<ConfigurationIterator<'a, F, Q> + 'a> {
438//         Box::new(CloneConfigurations {
439//             it: lang.configurations_for_state(self)
440//         })
441//     }
442// }
443//
444
445impl<F: Symbol + fmt::Display, Q: State + fmt::Display, L: Label + fmt::Display> fmt::Display for Automaton<F, Q, L> {
446    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
447        for (conf, label, q) in self.transitions() {
448            write!(f, "{} -{}-> {}\n", conf, label, q)?;
449        }
450        write!(f, "final states: ")?;
451        for q in self.final_states() {
452            write!(f, "{} ", q)?;
453        }
454        Ok(())
455    }
456}
tree_automata/bottom_up/mod.rs

tree_automata/bottom_up/
mod.rs
