automaton

nfa.rs (16563B)

---

 use crate::{
     dfa::{self, DFA},
     Automaton, AutomatonError, Dot, Encodable, FiniteStateAutomaton,
 };
 use core::fmt::Display;
 use petgraph::{Directed, Graph};
 use std::{
     collections::{BTreeMap, BTreeSet, HashMap, HashSet},
     fmt,
 };
 
 use serde_json::{from_str, Value};
 
 #[derive(Hash, Debug, PartialEq, Eq, Clone, Copy, PartialOrd, Ord)]
 pub enum Transition {
     Char(char),
     Wildcard,
 }
 
 impl Display for Transition {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             Transition::Char(c) => write!(f, "'{}'", c),
             Transition::Wildcard => write!(f, "•"),
         }
     }
 }
 
 // TODO: From doesn't seem to be 2-way... Maybe I'm using it wrong?
 impl From<dfa::Transition> for Transition {
     fn from(transition: dfa::Transition) -> Self {
         match transition {
             dfa::Transition::Char(c) => Transition::Char(c),
             dfa::Transition::Wildcard => Transition::Wildcard,
         }
     }
 }
 
 impl From<Transition> for dfa::Transition {
     fn from(transition: Transition) -> Self {
         match transition {
             Transition::Char(c) => dfa::Transition::Char(c),
             Transition::Wildcard => dfa::Transition::Wildcard,
         }
     }
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub struct NFA {
     pub alphabet: HashSet<char>,
     states: HashSet<u64>,
     initial_state: u64,
     final_states: HashSet<u64>,
     transition_table: HashMap<(u64, Transition), Vec<u64>>,
 }
 
 impl NFA {
     pub fn new(
         alphabet: HashSet<char>,
         states: HashSet<u64>,
         initial_state: u64,
         final_states: HashSet<u64>,
         transition_table: HashMap<(u64, Transition), Vec<u64>>,
     ) -> Self {
         NFA {
             alphabet,
             states,
             initial_state,
             final_states,
             transition_table,
         }
     }
 }
 
 impl Automaton for NFA {
     fn accepts(&self, input: &str) -> bool {
         let mut current_states: Vec<u64> = vec![self.initial_state];
         let mut new_states: Vec<u64> = Vec::new();
         for c in input.chars() {
             for i in 0..current_states.len() {
                 match current_states.get(i).map_or(None, |&s| {
                     self.transition_table.get(&(s, Transition::Char(c))).map_or(
                         self.transition_table
                             .get(&(s, Transition::Wildcard))
                             .and_then(|s| Some(s.to_owned())),
                         |v| Some(v.to_owned()),
                     )
                 }) {
                     Some(states) => {
                         new_states.append(&mut states.clone());
                     }
                     None => (),
                 }
             }
             current_states = new_states;
             new_states = Vec::new();
             if current_states.len() == 0 {
                 return false;
             }
         }
         current_states.iter().any(|s| self.final_states.contains(s))
     }
 }
 
 impl FiniteStateAutomaton for NFA {
     fn as_dfa(&self) -> Result<dfa::DFA, AutomatonError> {
         let mut states = HashSet::new();
         let initial_state = 0;
         let mut current_state = initial_state;
         let mut final_states = HashSet::new();
         let mut dfa_transition_to_nfa_sets: HashMap<(u64, dfa::Transition), BTreeSet<u64>> =
             HashMap::new();
 
         let mut to_be_processed: BTreeSet<BTreeSet<u64>> = BTreeSet::new();
         let mut processed: BTreeSet<BTreeSet<u64>> = BTreeSet::new();
         let mut nfa_set_to_dfa_state: HashMap<BTreeSet<u64>, u64> = HashMap::new();
         let mut dfa_state_to_nfa_set: HashMap<u64, BTreeSet<u64>> = HashMap::new();
 
         to_be_processed.insert(BTreeSet::from([self.initial_state]));
 
         let mut nfa_alphabet: Vec<Transition> =
             self.alphabet.iter().map(|&c| Transition::Char(c)).collect();
         nfa_alphabet.push(Transition::Wildcard);
 
         while to_be_processed.len() != 0 {
             let current_nfa_set = match to_be_processed.pop_first() {
                 Some(set) => set,
                 None => continue,
             };
             if processed.contains(&current_nfa_set) {
                 continue;
             }
 
             states.insert(current_state);
             if current_nfa_set
                 .iter()
                 .any(|state| self.final_states.contains(state))
             {
                 final_states.insert(current_state);
             }
 
             nfa_set_to_dfa_state.insert(current_nfa_set.clone(), current_state);
             dfa_state_to_nfa_set.insert(current_state, current_nfa_set.clone());
 
             for &transition in nfa_alphabet.iter() {
                 let nfa_dests: BTreeSet<u64> = current_nfa_set
                     .iter()
                     .filter_map(|&s| {
                         // We need to take into account the wildcard transition dests and take the union of them with our transition dests (determinism)
                         let wildcard_transitions =
                             self.transition_table.get(&(s, Transition::Wildcard));
                         if transition == Transition::Wildcard {
                             wildcard_transitions.map(Vec::to_owned)
                         } else {
                             match wildcard_transitions {
                                 Some(wcs) => {
                                     let regular_dests = self
                                         .transition_table
                                         .get(&(s, transition))
                                         .map_or([].iter(), |dests| dests.into_iter());
                                     let mut union = wcs.to_owned();
                                     union.extend(regular_dests);
                                     Some(union)
                                 }
                                 None => self
                                     .transition_table
                                     .get(&(s, transition))
                                     .map(Vec::to_owned),
                             }
                         }
                     })
                     .flatten()
                     .collect();
                 to_be_processed.insert(nfa_dests.clone());
                 dfa_transition_to_nfa_sets.insert(
                     (current_state, dfa::Transition::from(transition)),
                     nfa_dests.clone(),
                 );
             }
 
             processed.insert(current_nfa_set);
             current_state += 1;
         }
 
         let transition_table: HashMap<(u64, dfa::Transition), u64> = dfa_transition_to_nfa_sets
             .iter()
             .map(|((from, transition), to)| {
                 Ok::<((u64, dfa::Transition), u64), AutomatonError>((
                     (*from, *transition),
                     nfa_set_to_dfa_state.get(to).map(u64::to_owned).ok_or(
                         AutomatonError::conversion_error(
                             "Unable to get the DFA state from a set of NFA states!",
                         ),
                     )?,
                 ))
             })
             .collect::<Result<HashMap<(u64, dfa::Transition), u64>, AutomatonError>>()?; // A monad is just a monoid in the category of endofunctors
 
         Ok(DFA {
             alphabet: self.alphabet.clone(),
             states,
             initial_state,
             final_states,
             transition_table,
         })
     }
 
     fn from_dfa(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(NFA {
             alphabet: dfa.alphabet,
             states: dfa.states,
             initial_state: dfa.initial_state,
             final_states: dfa.final_states,
             transition_table,
         })
     }
 }
 
 impl Display for NFA {
     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::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 NFA {
     fn parse(json_str: &str) -> Result<Self, AutomatonError> {
         NFA::parse(from_str::<Value>(json_str)?)
     }
 }
 
 impl Encodable<Value> for NFA {
     fn parse(json: Value) -> Result<Self, AutomatonError> {
         let alphabet_vec: Vec<char> = json["alphabet"]
             .as_array()
             .ok_or(AutomatonError::parse_error(
                 "Could not get the alphabet from the JSON",
             ))?
             .iter()
             .map(|v| v.to_string().chars().next())
             .collect::<Option<Vec<char>>>()
             .ok_or(AutomatonError::parse_error(
                 "Could not convert the alphabet to UTF-8 characters",
             ))?;
 
         let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
 
         let states: HashSet<u64> = json["states"]
             .as_array()
             .ok_or(AutomatonError::parse_error(
                 "Could not get the states from the JSON",
             ))?
             .iter()
             .map(|v| v.as_u64())
             .collect::<Option<_>>()
             .ok_or(AutomatonError::parse_error(
                 "Could not convert the states to u64",
             ))?;
 
         let initial_state: u64 =
             json["initial_state"]
                 .as_u64()
                 .ok_or(AutomatonError::parse_error(
                     "Initial state incorrectly formatted",
                 ))?;
 
         let final_states: HashSet<u64> = json["final_states"]
             .as_array()
             .ok_or(AutomatonError::parse_error(
                 "Could not get the final states from the JSON",
             ))?
             .iter()
             .map(|v| v.as_u64())
             .collect::<Option<_>>()
             .ok_or(AutomatonError::parse_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::parse_error(
                 "Unable to parse rows in transition table",
             ))?
             .iter()
         {
             let transitions = row
                 .as_array()
                 .ok_or(AutomatonError::parse_error(
                     "Unable to get a row in the transition table",
                 ))?
                 .to_owned();
 
             let from: u64 = transitions
                 .get(0)
                 .ok_or(AutomatonError::parse_error(
                     "Unable to get the \"from\" state of a row",
                 ))?
                 .as_u64()
                 .ok_or(AutomatonError::parse_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).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::parse_error(
                     "Unable to parse the transition destinations in the table",
                 ))?;
             for (input, dests) in dest_sets.iter() {
                 transition_table.insert((from, Transition::Char(*input)), dests.to_owned());
             }
         }
 
         Ok(NFA {
             alphabet,
             states,
             initial_state,
             final_states,
             transition_table,
         })
     }
 }
 
 impl TryFrom<&NFA> for Dot<Transition> {
     type Error = AutomatonError;
     fn try_from(nfa: &NFA) -> Result<Self, Self::Error> {
         let mut graph: Graph<u64, Transition, Directed> = Graph::new();
 
         let states: HashMap<u64, _> = nfa.states.iter().map(|&s| (s, graph.add_node(s))).collect();
 
         let mut alphabet: HashSet<Transition> =
             nfa.alphabet.iter().map(|&c| Transition::Char(c)).collect();
         alphabet.insert(Transition::Wildcard);
 
         for transition in alphabet {
             for (from_id, dest) in states
                 .iter()
                 .filter_map(|(&from, &from_id)| {
                     nfa.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 nfa states!",
                 ))?;
                 graph.add_edge(from_id, dest_id, transition);
             }
         }
 
         let initial_state_id = *states
             .get(&nfa.initial_state)
             .ok_or(AutomatonError::dot_error(
                 "Unable to get initial state graph index!",
             ))?;
 
         let final_states = nfa
             .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,
             (nfa.initial_state, initial_state_id),
             final_states,
         ))
     }
 }