use std::{error::Error, fmt::Display};
use crate::{
collections::{Bag, Stack},
graphs::{DirectedGraph, Graph, dfs, dfs_mul},
strings::char_at,
};
#[must_use = "building the NFA does not evaluate it"]
pub struct RegExpNFA {
graph: DirectedGraph,
regexp: String,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RegularExpressionErrors {
#[allow(missing_docs)]
InvalidRegularExpression { i: usize },
#[allow(missing_docs)]
InvalidCharacterInText { i: usize, c: char },
}
impl Display for RegularExpressionErrors {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
RegularExpressionErrors::InvalidCharacterInText { i, c } => write!(
f,
"text contains the meta-character {} at position {}",
c, i
),
RegularExpressionErrors::InvalidRegularExpression { i } => {
write!(f, "Invalid regular expression at {}", i)
}
}
}
}
impl Error for RegularExpressionErrors {}
impl RegExpNFA {
pub fn new(regexp: String) -> Result<Self, RegularExpressionErrors> {
let mut ops = Stack::new();
let mut graph = DirectedGraph::new(regexp.len() + 1);
for i in 0..regexp.len() {
let mut lp = i;
if char_at(®exp, i) == b'(' as i16
|| char_at(®exp, i) == b'|' as i16
{
ops.push(i);
} else if char_at(®exp, i) == b')' as i16 {
let or = ops.pop().ok_or(
RegularExpressionErrors::InvalidRegularExpression { i },
)?;
if char_at(®exp, i) == b'|' as i16 {
lp = ops.pop().ok_or(
RegularExpressionErrors::InvalidRegularExpression { i },
)?;
graph.add_edge(lp, or + 1);
graph.add_edge(or, i);
} else if char_at(®exp, or) == b'(' as i16 {
lp = or;
} else {
return Err(
RegularExpressionErrors::InvalidRegularExpression {
i: or,
},
);
}
}
if i < regexp.len() - 1 && char_at(®exp, i + 1) == b'*' as i16 {
graph.add_edge(lp, i + 1);
graph.add_edge(i + 1, lp);
}
let i_c = char_at(®exp, i);
if i_c == b'(' as i16 || i_c == b'*' as i16 || i_c == b')' as i16 {
graph.add_edge(i, i + 1);
}
}
if let Some(i) = ops.pop() {
Err(RegularExpressionErrors::InvalidRegularExpression { i })
} else {
Ok(Self { graph, regexp })
}
}
pub fn recognizes(
&self,
txt: &str,
) -> Result<bool, RegularExpressionErrors> {
let m = self.regexp.len();
let dfs = dfs(&self.graph, 0);
let mut pc = Bag::new();
for v in 0..self.graph.vertices() {
if dfs.marked()[v] {
pc.insert(v);
}
}
for i in 0..txt.len() {
let t_c = char_at(txt, i);
if t_c == b'*' as i16
|| t_c == b'|' as i16
|| t_c == b'(' as i16
|| t_c == b')' as i16
{
return Err(RegularExpressionErrors::InvalidCharacterInText {
i,
c: t_c as u8 as char,
});
}
let mut matches = Bag::new();
for &v in &pc {
if v == m {
continue;
}
let r_c = char_at(&self.regexp, v);
let t_c = char_at(txt, v);
if r_c == t_c || r_c == b'.' as i16 {
matches.insert(v + 1);
}
}
if matches.is_empty() {
continue;
}
let dfs = dfs_mul(&self.graph, matches.into_iter());
pc = Bag::new();
for v in 0..self.graph.vertices() {
if dfs.marked()[v] {
pc.insert(v);
}
}
if pc.is_empty() {
return Ok(false);
}
}
for v in pc {
if v == m {
return Ok(true);
}
}
Ok(false)
}
}