commit f5e3b90bbda00a01ab80a0585e825214ad6fc49e
parent 899212a15a67f1adb00cd6b8fedd64e6054dcd06
Author: Ethan Long <ethan@Ethans-MacBook-Pro.local>
Date: Wed, 29 Nov 2023 15:49:48 +1100
Cleaned up the API a bit.
Diffstat:
6 files changed, 180 insertions(+), 111 deletions(-)
diff --git a/src/bin/nfa.rs b/src/bin/nfa.rs
@@ -40,7 +40,7 @@ fn main() -> Result<(), Box<dyn Error>> {
println!("NFA:\n{nfa}\n");
println!("Running on the following input:\n{input_string}");
println!("Accepts: {}", nfa.accepts(input_string));
- let dfa: DFA = DFA::convert(Box::new(nfa));
+ let dfa: DFA = DFA::convert(Box::new(nfa))?;
println!("Converted to DFA, accepts: {}", dfa.accepts(input_string));
println!("DFA:\n{dfa}\n");
diff --git a/src/lib/automaton.rs b/src/lib/automaton.rs
@@ -8,11 +8,11 @@ pub trait Automaton {
}
pub trait FiniteStateAutomaton: Automaton {
- fn as_dfa(&self) -> dfa::DFA;
- fn from_dfa(dfa: dfa::DFA) -> Self
+ fn as_dfa(&self) -> Result<dfa::DFA, Box<dyn Error>>;
+ fn from_dfa(dfa: dfa::DFA) -> Result<Self, Box<dyn Error>>
where
Self: Sized;
- fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Self
+ fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, Box<dyn Error>>
where
Self: Sized;
}
diff --git a/src/lib/dfa.rs b/src/lib/dfa.rs
@@ -3,6 +3,7 @@ use std::{
collections::{HashMap, HashSet},
error::Error,
fmt,
+ panic::Location,
};
use crate::{Automaton, Encodable, FiniteStateAutomaton};
@@ -20,16 +21,39 @@ impl Display for DFAParseError {
}
impl DFAParseError {
- fn cause(reason: &str) -> Self {
+ #[track_caller]
+ fn warn_str(reason: &str, loc: Option<&Location>) -> String {
+ let location = loc.unwrap_or(Location::caller());
+ format!("[DFA::{} WARN] {}", location, reason)
+ }
+ #[track_caller]
+ fn print_warn(reason: &str) {
+ let location = Location::caller();
+ eprintln!("{}", DFAParseError::warn_str(reason, Some(location)))
+ }
+
+ #[track_caller]
+ fn error_str(reason: &str, loc: Option<&Location>) -> String {
+ let location = loc.unwrap_or(Location::caller());
+ format!("[DFA::{} ERROR] {}", location, reason)
+ }
+ #[track_caller]
+ fn error(reason: &str) -> Self {
+ let location = Location::caller();
DFAParseError {
- reason: reason.to_owned(),
+ reason: DFAParseError::error_str(reason, Some(location)),
}
}
+ #[track_caller]
+ fn print_error(reason: &str) {
+ let location = Location::caller();
+ eprintln!("{}", DFAParseError::error_str(reason, Some(location)))
+ }
}
impl Error for DFAParseError {}
-#[derive(Clone,Debug,PartialEq)]
+#[derive(Clone, Debug, PartialEq)]
pub struct DFA {
pub alphabet: HashSet<char>,
pub states: HashSet<u64>,
@@ -43,16 +67,18 @@ impl Automaton for DFA {
let mut current_state: u64 = self.initial_state;
for c in input.chars() {
if !self.alphabet.contains(&c) {
- eprintln!(
- "[DFA::accepts WARNING] Input character {} is not in the alphabet of the DFA",
+ DFAParseError::print_warn(&format!(
+ "Input character {} is not in the alphabet of the DFA",
c
- );
+ ));
return false;
}
match self.transition_table.get(&(current_state, c)) {
Some(state) => current_state = state.to_owned(),
None => {
- eprintln!("[DFA::accepts ERROR] The DFA's transition table is incomplete or malformed!");
+ DFAParseError::print_error(
+ "The DFA's transition table is incomplete or malformed!",
+ );
return false;
}
}
@@ -62,20 +88,20 @@ impl Automaton for DFA {
}
impl FiniteStateAutomaton for DFA {
- fn as_dfa(&self) -> DFA {
- self.clone()
+ fn as_dfa(&self) -> Result<DFA, Box<dyn Error>> {
+ Ok(self.clone())
}
- fn from_dfa(dfa: self::DFA) -> Self
+ fn from_dfa(dfa: self::DFA) -> Result<Self, Box<dyn Error>>
where
- Self: Sized
+ Self: Sized,
{
- dfa
+ Ok(dfa)
}
- fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Self
+ fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, Box<dyn Error>>
where
- Self: Sized
+ Self: Sized,
{
automaton.as_dfa()
}
@@ -165,7 +191,7 @@ impl Display for DFA {
format!("{str}\n{input}\t|\t{dests}")
});
- write!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}\nTransition Table:\n{transition_table_str}")
+ writeln!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}\nTransition Table:\n{transition_table_str}")
}
}
@@ -178,48 +204,85 @@ impl Encodable<&str> for DFA {
impl Encodable<Value> for DFA {
fn parse(json: Value) -> Result<DFA, Box<dyn Error>> {
- let alphabet_vec: Vec<char> = json["alphabet"].as_array().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not get the alphabet from the JSON"))?.iter().map(|v| v.to_string().chars().next()).collect::<Option<Vec<char>>>().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not convert the alphabet to UTF-8 characters"))?;
+ let alphabet_vec: Vec<char> = json["alphabet"]
+ .as_array()
+ .ok_or(DFAParseError::error(
+ "Could not get the alphabet from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.to_string().chars().next())
+ .collect::<Option<Vec<char>>>()
+ .ok_or(DFAParseError::error(
+ "Could not convert the alphabet to UTF-8 characters",
+ ))?;
- let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
+ let alphabet: HashSet<char> = alphabet_vec.iter().map(char::to_owned).collect();
- let states: HashSet<u64> = json["states"].as_array().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not get the states from the JSON"))?.iter().map(|v| v.as_u64()).collect::<Option<HashSet<u64>>>().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not convert the states to u64"))?;
+ let states: HashSet<u64> = json["states"]
+ .as_array()
+ .ok_or(DFAParseError::error(
+ "Could not get the states from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<HashSet<u64>>>()
+ .ok_or(DFAParseError::error("Could not convert the states to u64"))?;
let initial_state: u64 =
json["initial_state"]
.as_u64()
- .ok_or(Box::new(DFAParseError::cause(
- "[DFA::parse ERROR] Initial state incorrectly formatted",
+ .ok_or(Box::new(DFAParseError::error(
+ "Initial state incorrectly formatted",
)))?;
- let final_states: HashSet<u64> = json["final_states"].as_array().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not get the final states from the JSON"))?.iter().map(|v| v.as_u64()).collect::<Option<_>>().ok_or(DFAParseError::cause("[DFA::parse ERROR] Could not convert the final states to u64"))?;
+ let final_states: HashSet<u64> = json["final_states"]
+ .as_array()
+ .ok_or(DFAParseError::error(
+ "Could not get the final states from the JSON",
+ ))?
+ .iter()
+ .map(|v| v.as_u64())
+ .collect::<Option<_>>()
+ .ok_or(DFAParseError::error(
+ "Could not convert the final states to u64",
+ ))?;
- // FIXME: This really should be redone, look at the NFA one for inspo
let mut transition_table: HashMap<(u64, char), u64> = HashMap::new();
for row in json["transition_table"]
.as_array()
+ .ok_or(DFAParseError::error(
+ "Unable to parse rows in transition table",
+ ))?
.iter()
- .flat_map(|opt| opt.iter())
{
- let v: Option<(u64, Vec<(u64, char)>)> = row.as_array().map_or(None, |arr| {
- let from: u64 = arr[0].as_u64()?;
- let to: Vec<(u64, char)> = arr[1..]
- .into_iter()
- .filter_map(|v| v.as_u64())
- .zip(alphabet_vec.clone())
- .collect();
- Some((from, to))
- });
- match v {
- Some((from, to)) => {
- for (dest, input) in to.into_iter() {
- transition_table.insert((from, input), dest);
- }
- }
- None => {
- return Err(Box::new(DFAParseError::cause(
- "Unable to parse DFA, incorrect types in the JSON",
- )));
- }
+ let transitions = row
+ .as_array()
+ .ok_or(DFAParseError::error(
+ "Unable to get a row in the transition table",
+ ))?
+ .to_owned();
+
+ let from: u64 = transitions
+ .get(0)
+ .ok_or(DFAParseError::error(
+ "Unable to get the \"from\" state of a row",
+ ))?
+ .as_u64()
+ .ok_or(DFAParseError::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(DFAParseError::error(
+ "Unable to parse the transition destinations in the table",
+ ))?;
+ for (input, dest) in dests.iter() {
+ transition_table.insert((from, *input), *dest);
}
}
diff --git a/src/lib/nfa.rs b/src/lib/nfa.rs
@@ -4,6 +4,7 @@ use std::{
collections::{BTreeSet, HashMap, HashSet},
error::Error,
fmt,
+ panic::Location,
};
use serde_json::{from_str, Value};
@@ -20,9 +21,27 @@ impl Display for NFAParseError {
}
impl NFAParseError {
- fn cause(reason: &str) -> Self {
+ #[track_caller]
+ fn warn_str(reason: &str, loc: Option<&Location>) -> String {
+ let location = loc.unwrap_or(Location::caller());
+ format!("[NFA::{} WARN] {}", location, reason)
+ }
+ #[track_caller]
+ fn print_warn(reason: &str) {
+ let location = Location::caller();
+ eprintln!("{}", NFAParseError::warn_str(reason, Some(location)))
+ }
+
+ #[track_caller]
+ fn error_str(reason: &str, loc: Option<&Location>) -> String {
+ let location = loc.unwrap_or(Location::caller());
+ format!("[NFA::{} ERROR] {}", location, reason)
+ }
+ #[track_caller]
+ fn error(reason: &str) -> Self {
+ let location = Location::caller();
NFAParseError {
- reason: reason.to_owned(),
+ reason: NFAParseError::error_str(reason, Some(location)),
}
}
}
@@ -44,10 +63,10 @@ impl Automaton for NFA {
let mut new_states: Vec<u64> = Vec::new();
for c in input.chars() {
if !self.alphabet.contains(&c) {
- eprintln!(
- "[NFA::accepts WARNING] Input character {} is not in the alphabet of the DFA",
+ NFAParseError::print_warn(&format!(
+ "Input character {} is not in the alphabet of the DFA",
c
- );
+ ));
return false;
}
for i in 0..current_states.len() {
@@ -72,7 +91,7 @@ impl Automaton for NFA {
}
impl FiniteStateAutomaton for NFA {
- fn as_dfa(&self) -> DFA {
+ fn as_dfa(&self) -> Result<DFA, Box<dyn Error>> {
let mut current_newstate = self.initial_state;
let mut newest_newstate = current_newstate;
// Subset construction algo
@@ -88,7 +107,7 @@ impl FiniteStateAutomaton for NFA {
let current_states = state_reverse_map
.clone()
.get(¤t_newstate)
- .expect("We should have already added this state into the reverse map!")
+ .ok_or(NFAParseError::error("We should have already added this state into the reverse map!"))?
.to_owned();
let to: BTreeSet<u64> = current_states
.iter()
@@ -112,9 +131,7 @@ impl FiniteStateAutomaton for NFA {
state_forward_map.insert(to.clone(), newest_newstate);
state_reverse_map.insert(newest_newstate, to.clone());
transition_table.insert((current_newstate, *c), newest_newstate);
- if to.len() == 0 {
- println!("Should be here!");
- // Add the transitions to the new trap state
+ if to.len() == 0 { // Trap state!
for c in self.alphabet.iter() {
transition_table.insert((newest_newstate, *c), newest_newstate);
}
@@ -135,16 +152,16 @@ impl FiniteStateAutomaton for NFA {
.map(|(new_state, _)| new_state.to_owned())
.collect();
- DFA {
+ Ok(DFA {
alphabet: self.alphabet.clone(),
states,
initial_state: self.initial_state,
final_states,
transition_table,
- }
+ })
}
- fn from_dfa(dfa: DFA) -> Self
+ fn from_dfa(dfa: DFA) -> Result<Self, Box<dyn Error>>
where
Self: Sized,
{
@@ -153,20 +170,20 @@ impl FiniteStateAutomaton for NFA {
.iter()
.map(|(from_input, to)| (*from_input, vec![*to]))
.collect();
- NFA {
+ Ok(NFA {
alphabet: dfa.alphabet,
states: dfa.states,
initial_state: dfa.initial_state,
final_states: dfa.final_states,
transition_table,
- }
+ })
}
- fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Self
+ fn convert(automaton: Box<dyn FiniteStateAutomaton>) -> Result<Self, Box<dyn Error>>
where
Self: Sized,
{
- NFA::from_dfa(automaton.as_dfa())
+ NFA::from_dfa(automaton.as_dfa()?)
}
}
@@ -220,7 +237,7 @@ impl Display for NFA {
let initial_state_str: String = self.initial_state.to_string();
- write!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}")
+ writeln!(f, "Alphabet: {alphabet_str}\nStates: {states_str}\nInitial State: {initial_state_str}\nFinal States: {final_states_str}")
}
}
@@ -234,99 +251,88 @@ impl Encodable<Value> for NFA {
fn parse(json: Value) -> Result<Self, Box<dyn Error>> {
let alphabet_vec: Vec<char> = json["alphabet"]
.as_array()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Could not get the alphabet from the JSON",
+ .ok_or(NFAParseError::error(
+ "Could not get the alphabet from the JSON",
))?
.iter()
.map(|v| v.to_string().chars().next())
.collect::<Option<Vec<char>>>()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Could not convert the alphabet to UTF-8 characters",
+ .ok_or(NFAParseError::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(NFAParseError::cause(
- "[NFA::parse ERROR] Could not get the states from the JSON",
+ .ok_or(NFAParseError::error(
+ "Could not get the states from the JSON",
))?
.iter()
.map(|v| v.as_u64())
.collect::<Option<_>>()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Could not convert the states to u64",
+ .ok_or(NFAParseError::error(
+ "Could not convert the states to u64",
))?;
let initial_state: u64 =
json["initial_state"]
.as_u64()
- .ok_or(Box::new(NFAParseError::cause(
- "[NFA::parse ERROR] Initial state incorrectly formatted",
- )))?;
+ .ok_or(NFAParseError::error(
+ "Initial state incorrectly formatted",
+ ))?;
let final_states: HashSet<u64> = json["final_states"]
.as_array()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Could not get the final states from the JSON",
+ .ok_or(NFAParseError::error(
+ "Could not get the final states from the JSON",
))?
.iter()
.map(|v| v.as_u64())
.collect::<Option<_>>()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Could not convert the final states to u64",
+ .ok_or(NFAParseError::error(
+ "Could not convert the final states to u64",
))?;
- /*
- {
- "description": "...",
- "alphabet": [...],
- "states": [...],
- "initial_state": ...,
- "final_states": [...],
- "transition_table": [
- [0, [...], [...], ...],
- [1, [...], [...], ...]
- ]
- }
- */
let mut transition_table: HashMap<(u64, char), Vec<u64>> = HashMap::new();
for row in json["transition_table"]
.as_array()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Unable to parse rows in transition table",
- ))
+ .ok_or(NFAParseError::error(
+ "Unable to parse rows in transition table",
+ ))?
.iter()
- .flat_map(|opt| opt.iter())
{
let transitions = row
.as_array()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Unable to get a row in the transition table",
+ .ok_or(NFAParseError::error(
+ "Unable to get a row in the transition table",
))?
.to_owned();
+
let from: u64 = transitions
.get(0)
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Unable to get the \"from\" state of a row",
+ .ok_or(NFAParseError::error(
+ "Unable to get the \"from\" state of a row",
))?
.as_u64()
- .ok_or("[NFA::parse ERROR] Unable to parse the \"from\" state of a row as a u64")?;
- let dest_sets: Vec<(char, Vec<u64>)> = transitions[1..]
+ .ok_or(NFAParseError::error(
+ "Unable to parse the \"from\" state of a row as a u64",
+ ))?;
+
+ let dest_sets: Vec<(char, Vec<u64>)> = alphabet_vec
.iter()
- .map(|v| v.as_array())
- .zip(alphabet_vec.clone())
- .map(|(states, input)| {
+ .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)))
+ .and_then(|sts| Some((*input, sts)))
})
})
.collect::<Option<_>>()
- .ok_or(NFAParseError::cause(
- "[NFA::parse ERROR] Unable to parse the transition destinations in the table",
+ .ok_or(NFAParseError::error(
+ "Unable to parse the transition destinations in the table",
))?;
for (input, dests) in dest_sets.iter() {
transition_table.insert((from, *input), dests.to_owned().clone());
diff --git a/src/lib/tests/dfa_tests.rs b/src/lib/tests/dfa_tests.rs
@@ -68,7 +68,7 @@ fn dfa_conversion() {
for dfa_enc in dfas.iter() {
let dfa = DFA::parse(dfa_enc.as_str()).expect("Unable to parse DFA!");
- let as_dfa = dfa.as_dfa();
+ let as_dfa = dfa.as_dfa().expect("Error converting DFA to DFA!");
for i in 1..2000 {
let input = rand_string(i, dfa.alphabet.iter().map(char::to_owned).collect());
diff --git a/src/lib/tests/nfa_tests.rs b/src/lib/tests/nfa_tests.rs
@@ -64,7 +64,7 @@ fn dfa_conversion() {
for nfa_enc in nfas.iter() {
let nfa = NFA::parse(nfa_enc.as_str()).expect("Unable to parse NFA!");
- let as_dfa = nfa.as_dfa();
+ let as_dfa = nfa.as_dfa().expect("Error converting NFA to DFA!");
for i in 1..2000 {
let input = rand_string(i, nfa.alphabet.iter().map(char::to_owned).collect());
