automaton

automaton.rs (4957B)

---

 use petgraph::{graph::NodeIndex, Directed, Graph};
 use std::collections::BTreeMap;
 use std::error::Error;
 use std::fmt::Display;
 use std::panic::Location;
 
 pub mod web_automaton;
 
 pub mod dfa;
 pub mod enfa;
 pub mod graph_enfa;
 pub mod nfa;
 pub mod regex;
 
 #[derive(Debug)]
 pub enum AutomatonError {
     Tokenise(String),
     Parse(String),
     Convertion(String),
     Builder(String),
     Dot(String),
 }
 
 impl AutomatonError {
     pub fn cause(&self) -> String {
         match self {
             Self::Tokenise(s) => s.to_owned(),
             Self::Parse(s) => s.to_owned(),
             Self::Convertion(s) => s.to_owned(),
             Self::Builder(s) => s.to_owned(),
             Self::Dot(s) => s.to_owned(),
         }
     }
 
     #[track_caller]
     fn error_str(err_type: &str, reason: &str, loc: Option<&Location>) -> String {
         let location = loc.unwrap_or(Location::caller());
         format!("[{}::{} ERROR] {}", location, err_type, reason)
     }
 
     #[track_caller]
     fn tokenise_error(reason: &str) -> Self {
         let location = Location::caller();
         AutomatonError::Tokenise(AutomatonError::error_str(
             "Tokenisation",
             reason,
             Some(location),
         ))
     }
 
     #[track_caller]
     fn parse_error(reason: &str) -> Self {
         let location = Location::caller();
         AutomatonError::Parse(AutomatonError::error_str("Parsing", reason, Some(location)))
     }
 
     #[track_caller]
     fn conversion_error(reason: &str) -> Self {
         let location = Location::caller();
         AutomatonError::Convertion(AutomatonError::error_str(
             "Conversion",
             reason,
             Some(location),
         ))
     }
 
     #[track_caller]
     fn builder_error(reason: &str) -> Self {
         let location = Location::caller();
         AutomatonError::Builder(AutomatonError::error_str("Builder", reason, Some(location)))
     }
 
     #[track_caller]
     fn dot_error(reason: &str) -> Self {
         let location = Location::caller();
         AutomatonError::Dot(AutomatonError::error_str("Dot", reason, Some(location)))
     }
 }
 
 impl Error for AutomatonError {}
 
 impl Display for AutomatonError {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         write!(f, "{}", self.cause())
     }
 }
 
 impl From<serde_json::Error> for AutomatonError {
     fn from(err: serde_json::Error) -> Self {
         Self::parse_error(&err.to_string())
     }
 }
 
 pub trait Automaton: Display {
     fn accepts(&self, input: &str) -> bool;
 }
 
 pub trait FiniteStateAutomaton: Automaton {
     fn as_dfa(&self) -> Result<dfa::DFA, AutomatonError>;
     fn from_dfa(dfa: dfa::DFA) -> Result<Self, AutomatonError>
     where
         Self: Sized;
     fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, AutomatonError>
     where
         Self: Sized,
     {
         Self::from_dfa(automaton.as_dfa()?)
     }
 }
 
 pub trait Encodable<T>
 where
     Self: Sized,
 {
     fn parse(encoding: T) -> Result<Self, AutomatonError>;
 }
 
 pub struct Dot<V>
 where
     V: Display,
 {
     graph: Graph<u64, V, Directed>,
     initial_state: (u64, NodeIndex),
     final_states: BTreeMap<u64, NodeIndex>,
 }
 
 impl<V> Dot<V>
 where
     V: Display,
 {
     pub fn new(
         graph: Graph<u64, V, Directed>,
         initial_state: (u64, NodeIndex),
         final_states: BTreeMap<u64, NodeIndex>,
     ) -> Dot<V> {
         Dot {
             graph,
             initial_state,
             final_states,
         }
     }
 }
 
 impl<V> Display for Dot<V>
 where
     V: Display,
 {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         writeln!(f, "digraph {{")?;
         writeln!(f, "    entrypoint [ label = \"\", shape = none ]")?;
 
         for (id, label) in self
             .graph
             .node_indices()
             .filter_map(|id| Some((id, *self.graph.node_weight(id)?)))
         {
             let shape = if self.final_states.contains_key(&label) {
                 "doublecircle"
             } else {
                 "circle"
             };
             writeln!(
                 f,
                 "    {} [ label = \"{}\", shape = {} ]",
                 id.index(),
                 label,
                 shape
             )?;
         }
         writeln!(f, "    entrypoint -> {}", self.initial_state.1.index())?;
         for (from, to, transition) in self.graph.edge_indices().filter_map(|ex| {
             let (from_ix, to_ix) = self.graph.edge_endpoints(ex)?;
             let label = self.graph.edge_weight(ex)?.to_string();
             Some((from_ix, to_ix, label))
         }) {
             writeln!(
                 f,
                 "    {} -> {} [ label = \"{}\" ]",
                 from.index(),
                 to.index(),
                 transition
             )?;
         }
         writeln!(f, "}}")
     }
 }
 
 #[cfg(test)]
 mod tests {
     mod testlib {
         pub mod util;
     }
 
     mod dfa_tests;
     mod enfa_tests;
     mod nfa_tests;
     mod regex_tests;
 }