automaton

enfa.rs (18337B)

---

 use crate::{
     dfa::{self, DFA},
     nfa::{self, NFA},
     Automaton, AutomatonError, Dot, Encodable, FiniteStateAutomaton,
 };
 use core::fmt::Display;
 use petgraph::{Directed, Graph};
 use serde_json::{from_str, Value};
 use std::collections::{BTreeMap, HashMap, HashSet};
 
 #[derive(Hash, Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord)]
 pub enum Transition {
     Char(char),
     Epsilon,
     Wildcard,
 }
 
 impl Display for Transition {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         match self {
             Transition::Char(c) => write!(f, "'{}'", c),
             Transition::Epsilon => write!(f, "ε"),
             Transition::Wildcard => write!(f, "•"),
         }
     }
 }
 
 impl From<nfa::Transition> for Transition {
     fn from(transition: nfa::Transition) -> Self {
         match transition {
             nfa::Transition::Char(c) => Self::Char(c),
             nfa::Transition::Wildcard => Self::Wildcard,
         }
     }
 }
 
 impl From<dfa::Transition> for Transition {
     fn from(transition: dfa::Transition) -> Self {
         match transition {
             dfa::Transition::Char(c) => Self::Char(c),
             dfa::Transition::Wildcard => Self::Wildcard,
         }
     }
 }
 
 impl TryFrom<Transition> for nfa::Transition {
     type Error = AutomatonError;
     fn try_from(transition: Transition) -> Result<Self, Self::Error> {
         match transition {
             Transition::Char(c) => Ok(nfa::Transition::Char(c)),
             Transition::Wildcard => Ok(nfa::Transition::Wildcard),
             Transition::Epsilon => Err(AutomatonError::conversion_error("Unable to convert ENFA epsilon transition to NFA transition, NFAs have no notion of an epsilon transition!"))
         }
     }
 }
 
 // ε-NFAs!
 #[derive(Clone, Debug, PartialEq)]
 pub struct ENFA {
     pub alphabet: HashSet<char>,
     states: HashSet<u64>,
     initial_state: u64,
     final_states: HashSet<u64>,
     transition_table: HashMap<(u64, Transition), Vec<u64>>,
 }
 
 impl ENFA {
     fn eclose(&self, state: u64, visited: Option<&mut HashSet<u64>>) -> HashSet<u64> {
         let mut reachable: HashSet<u64> = HashSet::new();
         let mut visited_set = HashSet::new(); // Lifetime hack. There has to be a better way
         let visited = visited.unwrap_or(&mut visited_set);
         reachable.insert(state);
         for state in self
             .transition_table
             .get(&(state, Transition::Epsilon))
             .unwrap_or(&vec![])
         {
             if !visited.contains(state) {
                 visited.insert(*state);
                 for state in self.eclose(*state, Some(visited)).iter() {
                     reachable.insert(*state);
                     visited.insert(*state);
                 }
             }
         }
         reachable
     }
 
     pub fn new(
         alphabet: HashSet<char>,
         states: HashSet<u64>,
         initial_state: u64,
         final_states: HashSet<u64>,
         transition_table: HashMap<(u64, Transition), Vec<u64>>,
     ) -> ENFA {
         ENFA {
             alphabet,
             states,
             initial_state,
             final_states,
             transition_table,
         }
     }
 
     pub fn as_nfa(&self) -> NFA {
         let preemptive_final_states: HashSet<u64> = self
             .states
             .iter()
             .filter(|&&starting_state| {
                 self.eclose(starting_state, None)
                     .into_iter()
                     .any(|epsilon_accessible| self.final_states.contains(&epsilon_accessible))
             })
             .map(u64::to_owned)
             .collect();
 
         let mut nfa_transition_table: HashMap<(u64, nfa::Transition), Vec<u64>> = HashMap::new();
 
         let mut enfa_state_accepted_input_map: HashMap<u64, HashSet<Transition>> = HashMap::new();
 
         for (from, transition) in self.transition_table.keys() {
             match enfa_state_accepted_input_map.get(from) {
                 None => {
                     let mut transitions = HashSet::new();
                     transitions.insert(*transition);
                     enfa_state_accepted_input_map.insert(*from, transitions);
                 }
                 Some(transitions) => {
                     let mut transitions = transitions.to_owned();
                     transitions.insert(*transition);
                     enfa_state_accepted_input_map.insert(*from, transitions);
                 }
             }
         }
 
         for &state in self.states.iter() {
             let eclose = self.eclose(state, None);
             for (enfa_from, transition) in eclose
                 .into_iter()
                 .flat_map(|s| {
                     enfa_state_accepted_input_map
                         .get(&s)
                         .map_or(HashSet::new(), HashSet::to_owned)
                         .into_iter()
                         .map(move |t| (s, t))
                 })
                 .filter_map(|(s, t)| nfa::Transition::try_from(t).map(|t| (s, t)).ok())
             {
                 let mut enfa_to = self
                     .transition_table
                     .get(&(enfa_from, Transition::from(transition)))
                     .map_or(vec![], Vec::to_owned);
                 let nfa_to = nfa_transition_table.get_mut(&(state, transition));
                 match nfa_to {
                     Some(v) => {
                         v.append(&mut enfa_to);
                     }
                     None => {
                         nfa_transition_table.insert((state, transition), enfa_to);
                     }
                 }
             }
         }
 
         let mut nfa_states: HashSet<u64> = nfa_transition_table
             .values()
             .flat_map(Vec::to_owned)
             .collect(); // Prune off the states without an entrypoint
         nfa_states.insert(self.initial_state); // The only state without an entrypoint
 
         let nfa_final_states: HashSet<u64> = preemptive_final_states
             .into_iter()
             .filter(|s| nfa_states.contains(s))
             .collect();
 
         // TODO: Maybe try re-numbering the states here before making the NFA so that they're sequential?
 
         NFA::new(
             self.alphabet.clone(),
             nfa_states,
             self.initial_state,
             nfa_final_states,
             nfa_transition_table,
         )
     }
 }
 
 impl Automaton for ENFA {
     // TODO: Check that this is all g
     fn accepts(&self, input: &str) -> bool {
         let mut current_states: HashSet<u64> =
             self.eclose(self.initial_state, None).into_iter().collect();
         let mut new_states: HashSet<u64> = HashSet::new();
 
         for c in input.chars() {
             for state in current_states.iter() {
                 for newstate in self
                     .transition_table
                     .get(&(*state, Transition::Char(c)))
                     // FIXME: This is ugly
                     .map_or(
                         self.transition_table
                             .get(&(*state, Transition::Wildcard))
                             .map_or(vec![], Vec::to_owned),
                         |v| {
                             let mut transitions = v.to_owned();
                             self.transition_table
                                 .get(&(*state, Transition::Wildcard))
                                 .map(|s| transitions.append(&mut s.clone()));
                             transitions
                         },
                     )
                     .iter()
                     .flat_map(|s| self.eclose(*s, None))
                 {
                     new_states.insert(newstate);
                 }
             }
             current_states = new_states;
             new_states = HashSet::new();
             if current_states.len() == 0 {
                 return false;
             }
         }
         current_states.iter().any(|s| self.final_states.contains(s))
     }
 }
 
 impl FiniteStateAutomaton for ENFA {
     fn as_dfa(&self) -> Result<DFA, AutomatonError> {
         let nfa = self.as_nfa();
         nfa.as_dfa()
     }
 
     fn from_dfa(dfa: crate::dfa::DFA) -> Result<Self, AutomatonError>
     where
         Self: Sized,
     {
         let transition_table = dfa
             .transition_table
             .iter()
             .map(|((from, input), to)| ((*from, Transition::from(*input)), vec![*to]))
             .collect();
         Ok(ENFA {
             alphabet: dfa.alphabet,
             states: dfa.states,
             initial_state: dfa.initial_state,
             final_states: dfa.final_states,
             transition_table,
         })
     }
 }
 
 impl Display for ENFA {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         let mut transition_vec: Vec<Transition> =
             self.alphabet.iter().map(|&c| Transition::Char(c)).collect();
         let mut states_vec: Vec<u64> = self.states.iter().copied().collect();
         let mut final_states_vec: Vec<u64> = self.final_states.iter().copied().collect();
 
         transition_vec.push(Transition::Epsilon);
         transition_vec.push(Transition::Wildcard);
         transition_vec.sort();
         states_vec.sort();
         final_states_vec.sort();
 
         let transition_str = format!("{:?}", transition_vec);
         let states_str = format!("{:?}", states_vec);
         let initial_state_str = self.initial_state.to_string();
         let final_states_str = format!("{:?}", final_states_vec);
 
         let transition_tbl_hdr = transition_vec
             .iter()
             .fold("\t|".to_owned(), |acc, &t| format!("{}\t{}\t|", acc, t));
 
         let mut transition_map: HashMap<u64, Vec<Option<Vec<u64>>>> = HashMap::new();
         for &state in states_vec.iter() {
             let input_dests = transition_vec
                 .iter()
                 .map(|&transition| {
                     self.transition_table
                         .get(&(state, transition))
                         .and_then(|v| Some(v.to_owned()))
                 })
                 .collect();
             transition_map.insert(state, input_dests);
         }
 
         let transition_table_str =
             transition_map
                 .iter()
                 .fold(transition_tbl_hdr, |acc, (from, dest_groups)| {
                     let line_str = dest_groups.into_iter().fold("".to_owned(), |acc, dests| {
                         let dests_str = match dests {
                             None => "∅".to_owned(),
                             Some(v) => {
                                 v.iter()
                                     .enumerate()
                                     .fold("{".to_owned(), |acc, (index, &dest)| {
                                         let suffix = if index == v.len() - 1 { "}" } else { ", " };
                                         format!("{}{}{}", acc, dest, suffix)
                                     })
                             }
                         };
                         format!("{}{}\t|\t", acc, dests_str)
                     });
                     format!("{}\n{}\t|\t{}", acc, from, line_str)
                 });
         writeln!(f, "Alphabet: {}", transition_str)?;
         writeln!(f, "States: {}", states_str)?;
         writeln!(f, "Initial State: {}", initial_state_str)?;
         writeln!(f, "Final States: {}", final_states_str)?;
         writeln!(f, "Transition Table:\n{}", transition_table_str)?;
         let graphviz_repr: Result<Dot<Transition>, AutomatonError> = self.try_into();
         match graphviz_repr {
             Ok(s) => writeln!(f, "Graphviz Representation:\n{}", s),
             Err(e) => writeln!(f, "Error getting Graphviz representation: {}", e),
         }
     }
 }
 
 impl Encodable<&str> for ENFA {
     fn parse(json_str: &str) -> Result<Self, AutomatonError> {
         ENFA::parse(from_str::<Value>(json_str)?)
     }
 }
 
 impl Encodable<Value> for ENFA {
     fn parse(json: Value) -> Result<Self, AutomatonError> {
         let alphabet_vec: Vec<char> = json["alphabet"]
             .as_array()
             .ok_or(AutomatonError::conversion_error(
                 "Could not get the alphabet from the JSON",
             ))?
             .iter()
             .map(|v| v.to_string().chars().next())
             .collect::<Option<Vec<char>>>()
             .ok_or(AutomatonError::conversion_error(
                 "Could not convert the alphabet to UTF-8 characters",
             ))?;
 
         let alphabet_size = alphabet_vec.len();
 
         let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
 
         let states: HashSet<u64> = json["states"]
             .as_array()
             .ok_or(AutomatonError::conversion_error(
                 "Could not get the states from the JSON",
             ))?
             .iter()
             .map(|v| v.as_u64())
             .collect::<Option<_>>()
             .ok_or(AutomatonError::conversion_error(
                 "Could not convert the states to u64",
             ))?;
 
         let initial_state: u64 =
             json["initial_state"]
                 .as_u64()
                 .ok_or(AutomatonError::conversion_error(
                     "Initial state incorrectly formatted",
                 ))?;
 
         let final_states: HashSet<u64> = json["final_states"]
             .as_array()
             .ok_or(AutomatonError::conversion_error(
                 "Could not get the final states from the JSON",
             ))?
             .iter()
             .map(|v| v.as_u64())
             .collect::<Option<_>>()
             .ok_or(AutomatonError::conversion_error(
                 "Could not convert the final states to u64",
             ))?;
 
         let mut transition_table: HashMap<(u64, Transition), Vec<u64>> = HashMap::new();
 
         for row in json["transition_table"]
             .as_array()
             .ok_or(AutomatonError::conversion_error(
                 "Unable to parse rows in transition table",
             ))?
             .iter()
         {
             let transitions = row
                 .as_array()
                 .ok_or(AutomatonError::conversion_error(
                     "Unable to get a row in the transition table",
                 ))?
                 .to_owned();
 
             let from: u64 = transitions
                 .get(0)
                 .ok_or(AutomatonError::conversion_error(
                     "Unable to get the \"from\" state of a row",
                 ))?
                 .as_u64()
                 .ok_or(AutomatonError::conversion_error(
                     "Unable to parse the \"from\" state of a row as a u64",
                 ))?;
 
             let dest_sets: Vec<(char, Vec<u64>)> = alphabet_vec
                 .iter()
                 .zip(
                     transitions
                         .iter()
                         .skip(1)
                         .take(alphabet_size)
                         .map(Value::as_array),
                 )
                 .map(|(input, states)| {
                     states.and_then(|vs| {
                         vs.iter()
                             .map(|v| v.as_u64())
                             .collect::<Option<_>>()
                             .and_then(|sts| Some((*input, sts)))
                     })
                 })
                 .collect::<Option<_>>()
                 .ok_or(AutomatonError::conversion_error(
                     "Unable to parse the transition destinations in the table",
                 ))?;
             let epsilon_transitions: Vec<Vec<u64>> = transitions
                 .iter()
                 .skip(alphabet_size + 1)
                 .map(Value::as_array)
                 .map(|states| {
                     states.and_then(|vs| vs.iter().map(Value::as_u64).collect::<Option<_>>())
                 })
                 .collect::<Option<_>>()
                 .ok_or(AutomatonError::conversion_error(
                     "Unable to parse the ε-closure destinations in the table",
                 ))?;
             for (input, dests) in dest_sets.iter() {
                 transition_table.insert((from, Transition::Char(*input)), dests.to_owned());
             }
             for transition in epsilon_transitions.iter() {
                 transition_table.insert((from, Transition::Epsilon), transition.to_owned());
             }
         }
 
         //panic!("Not yet implemented!");
         Ok(ENFA {
             alphabet,
             states,
             initial_state,
             final_states,
             transition_table,
         })
     }
 }
 
 impl TryFrom<&ENFA> for Dot<Transition> {
     type Error = AutomatonError;
     fn try_from(enfa: &ENFA) -> Result<Self, Self::Error> {
         let mut graph: Graph<u64, Transition, Directed> = Graph::new();
 
         let states: HashMap<u64, _> = enfa
             .states
             .iter()
             .map(|&s| (s, graph.add_node(s)))
             .collect();
 
         let mut alphabet: HashSet<Transition> =
             enfa.alphabet.iter().map(|&c| Transition::Char(c)).collect();
         alphabet.insert(Transition::Epsilon);
         alphabet.insert(Transition::Wildcard);
 
         for transition in alphabet {
             for (from_id, dest) in states
                 .iter()
                 .filter_map(|(&from, &from_id)| {
                     enfa.transition_table
                         .get(&(from, transition))
                         .map(move |dests| dests.iter().map(move |dest| (from_id, dest)))
                 })
                 .flatten()
             {
                 let dest_id = *states.get(dest).ok_or(AutomatonError::dot_error(
                     "The destination of a transition does not exist in the enfa states!",
                 ))?;
                 graph.add_edge(from_id, dest_id, transition);
             }
         }
 
         let initial_state_id =
             *states
                 .get(&enfa.initial_state)
                 .ok_or(AutomatonError::dot_error(
                     "Unable to get initial state graph index!",
                 ))?;
 
         let final_states = enfa
             .final_states
             .iter()
             .map(|s| states.get(s).map(|&ix| (*s, ix)))
             .collect::<Option<BTreeMap<u64, _>>>()
             .ok_or(AutomatonError::dot_error(
                 "Unable to get the graph index of a final state!",
             ))?;
 
         Ok(Self::new(
             graph,
             (enfa.initial_state, initial_state_id),
             final_states,
         ))
     }
 }