automaton

dfa.rs (10240B)

---

 use core::fmt::Display;
 use petgraph::{Directed, Graph};
 use std::{
     collections::{BTreeMap, HashMap, HashSet},
     fmt,
 };
 
 use crate::{Automaton, AutomatonError, Dot, Encodable, FiniteStateAutomaton};
 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, "•"),
         }
     }
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub struct DFA {
     pub alphabet: HashSet<char>,
     pub states: HashSet<u64>,
     pub initial_state: u64,
     pub final_states: HashSet<u64>,
     pub transition_table: HashMap<(u64, Transition), u64>,
 }
 
 impl Automaton for DFA {
     fn accepts(&self, input: &str) -> bool {
         let mut current_state: u64 = self.initial_state;
         for c in input.chars() {
             match self
                 .transition_table
                 .get(&(current_state, Transition::Char(c)))
                 .or(self
                     .transition_table
                     .get(&(current_state, Transition::Wildcard)))
             {
                 Some(state) => current_state = state.to_owned(),
                 None => {
                     eprintln!("The DFA's transition table is incomplete or malformed!");
                     return false;
                 }
             }
         }
         self.final_states.contains(&current_state)
     }
 }
 
 impl FiniteStateAutomaton for DFA {
     fn as_dfa(&self) -> Result<DFA, AutomatonError> {
         Ok(self.clone())
     }
 
     fn from_dfa(dfa: self::DFA) -> Result<Self, AutomatonError>
     where
         Self: Sized,
     {
         Ok(dfa)
     }
 
     fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, AutomatonError>
     where
         Self: Sized,
     {
         automaton.as_dfa()
     }
 }
 
 impl Display for DFA {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> 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<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 dest_str = match dests {
                             None => "∅".to_owned(),
                             Some(v) => v.to_string(),
                         };
                         format!("{}{}\t|\t", acc, dest_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),
         }
     }
 }
 
 // This is the impl that should be used when reading DFA files
 impl Encodable<&str> for DFA {
     fn parse(json_str: &str) -> Result<DFA, AutomatonError> {
         DFA::parse(from_str::<Value>(json_str)?)
     }
 }
 
 impl Encodable<Value> for DFA {
     fn parse(json: Value) -> Result<DFA, 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<HashSet<u64>>>()
             .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), 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 dests: Vec<(char, u64)> = transitions[1..]
             let dests: Vec<(char, u64)> = alphabet_vec
                 .iter()
                 .zip(transitions.iter().skip(1).map(Value::as_u64))
                 .map(|(input, dest)| dest.and_then(|v| Some((*input, v))))
                 .collect::<Option<_>>()
                 .ok_or(AutomatonError::parse_error(
                     "Unable to parse the transition destinations in the table",
                 ))?;
             for (input, dest) in dests.iter() {
                 transition_table.insert((from, Transition::Char(*input)), *dest);
             }
         }
 
         Ok(DFA {
             alphabet,
             states,
             final_states,
             transition_table,
             initial_state,
         })
     }
 }
 
 impl TryFrom<&DFA> for Dot<Transition> {
     type Error = AutomatonError;
     fn try_from(dfa: &DFA) -> Result<Self, Self::Error> {
         let mut graph: Graph<u64, Transition, Directed> = Graph::new();
 
         let states: HashMap<u64, _> = dfa.states.iter().map(|&s| (s, graph.add_node(s))).collect();
 
         let mut alphabet: HashSet<Transition> =
             dfa.alphabet.iter().map(|&c| Transition::Char(c)).collect();
         alphabet.insert(Transition::Wildcard);
 
         for transition in alphabet {
             for (from, from_id, dest) in states.iter().filter_map(|(&from, &from_id)| {
                 dfa.transition_table
                     .get(&(from, transition))
                     .map(|dest| (from, from_id, dest))
             }) {
                 let dest_id = *states.get(dest).ok_or(AutomatonError::dot_error(
                     "The destination of a transition does not exist in the dfa states!",
                 ))?; // Maybe not really necessary...
                 if transition == Transition::Wildcard
                     || !dfa
                         .transition_table
                         .get(&(from, Transition::Wildcard))
                         .is_some_and(|wildcard_dest| dest == wildcard_dest)
                 {
                     graph.add_edge(from_id, dest_id, transition);
                 }
             }
         }
 
         let initial_state_id = *states
             .get(&dfa.initial_state)
             .ok_or(AutomatonError::dot_error(
                 "Unable to get initial state graph index!",
             ))?;
 
         let final_states = dfa
             .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,
             (dfa.initial_state, initial_state_id),
             final_states,
         ))
     }
 }