dandy/nfa/
eval.rs

1use crate::nfa::{Nfa, NfaState};
2use std::collections::{HashMap, HashSet};
3use std::iter;
4use std::rc::Rc;
5
6#[derive(Clone, Debug)]
7pub struct NfaEvaluator<'a> {
8    nfa: &'a Nfa,
9    rev_map: Rc<HashMap<&'a str, usize>>,
10    current_states: HashSet<usize>,
11    unknown_elem_seen: bool,
12}
13
14impl<'a> NfaEvaluator<'a> {
15    pub fn is_accepting(&self) -> bool {
16        if self.unknown_elem_seen {
17            false
18        } else {
19            self.current_states().iter().any(|s| s.accepting)
20        }
21    }
22
23    pub fn current_states(&self) -> Vec<&NfaState> {
24        self.current_states
25            .iter()
26            .map(|&s| &self.nfa.states[s])
27            .collect()
28    }
29
30    pub fn current_states_idx(&self) -> &HashSet<usize> {
31        &self.current_states
32    }
33
34    pub fn step_all(&self) -> Vec<NfaEvaluator<'a>> {
35        iter::repeat(self.clone())
36            .zip(self.nfa.alphabet())
37            .map(|(mut eval, elem)| {
38                eval.step(elem);
39                eval
40            })
41            .collect()
42    }
43
44    pub fn step(&mut self, elem: &str) -> Option<()> {
45        match self.rev_map.get(elem) {
46            None => {
47                self.unknown_elem_seen = true;
48                None
49            }
50            Some(&idx) => {
51                self.current_states = self
52                    .current_states
53                    .iter()
54                    .flat_map(|&state| &self.nfa.states[state].transitions[idx])
55                    .copied()
56                    .collect();
57                self.include_closure();
58                Some(())
59            }
60        }
61    }
62
63    pub fn step_multiple(&mut self, elems: &[&str]) -> Option<()> {
64        match elems.iter().try_for_each(|e| self.step(e)) {
65            None => {
66                self.unknown_elem_seen = true;
67                None
68            }
69            Some(_) => Some(())
70        }
71    }
72
73    fn include_closure(&mut self) {
74        let mut updated = true;
75        let mut to_push = HashSet::new();
76        while updated {
77            updated = false;
78            for state in self.current_states.iter() {
79                for epsilon_state in self.nfa.states[*state].epsilon_transitions.iter() {
80                    if !self.current_states.contains(epsilon_state) {
81                        updated = true;
82                        to_push.insert(epsilon_state);
83                    }
84                }
85            }
86            self.current_states.extend(to_push.drain());
87        }
88    }
89}
90
91impl<'a> From<&'a Nfa> for NfaEvaluator<'a> {
92    fn from(value: &'a Nfa) -> Self {
93        let map = value
94            .alphabet
95            .iter()
96            .enumerate()
97            .map(|(idx, c)| (c as &str, idx))
98            .collect();
99        let mut evaluator = Self {
100            nfa: value,
101            rev_map: Rc::new(map),
102            current_states: HashSet::new(),
103            unknown_elem_seen: false,
104        };
105        evaluator.current_states.insert(value.initial_state);
106        evaluator.include_closure();
107        evaluator
108    }
109}
dandy/nfa/eval.rs

dandy/nfa/
eval.rs
