1 use super::{nfa, Byte, Nfa, Ref};
4 use std::sync::atomic::{AtomicU32, Ordering};
6 #[derive(PartialEq, Clone, Debug)]
7 pub(crate) struct Dfa<R>
11 pub(crate) transitions: Map<State, Transitions<R>>,
12 pub(crate) start: State,
13 pub(crate) accepting: State,
16 #[derive(PartialEq, Clone, Debug)]
17 pub(crate) struct Transitions<R>
21 byte_transitions: Map<Byte, State>,
22 ref_transitions: Map<R, State>,
25 impl<R> Default for Transitions<R>
29 fn default() -> Self {
30 Self { byte_transitions: Map::default(), ref_transitions: Map::default() }
34 impl<R> Transitions<R>
38 fn insert(&mut self, transition: Transition<R>, state: State) {
40 Transition::Byte(b) => {
41 self.byte_transitions.insert(b, state);
43 Transition::Ref(r) => {
44 self.ref_transitions.insert(r, state);
50 /// The states in a `Nfa` represent byte offsets.
51 #[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)]
52 pub(crate) struct State(u32);
54 #[derive(Hash, Eq, PartialEq, Clone, Copy)]
55 pub(crate) enum Transition<R>
63 impl fmt::Debug for State {
64 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
65 write!(f, "S_{}", self.0)
69 impl<R> fmt::Debug for Transition<R>
73 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75 Self::Byte(b) => b.fmt(f),
76 Self::Ref(r) => r.fmt(f),
85 pub(crate) fn unit() -> Self {
86 let transitions: Map<State, Transitions<R>> = Map::default();
87 let start = State::new();
88 let accepting = start;
90 Self { transitions, start, accepting }
94 pub(crate) fn bool() -> Self {
95 let mut transitions: Map<State, Transitions<R>> = Map::default();
96 let start = State::new();
97 let accepting = State::new();
99 transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x00)), accepting);
101 transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x01)), accepting);
103 Self { transitions, start, accepting }
106 #[instrument(level = "debug")]
107 pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
108 let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
110 let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
111 let mut nfa_to_dfa: Map<nfa::State, State> = Map::default();
112 let dfa_start = State::new();
113 nfa_to_dfa.insert(nfa_start, dfa_start);
115 let mut queue = vec![(nfa_start, dfa_start)];
117 while let Some((nfa_state, dfa_state)) = queue.pop() {
118 if nfa_state == nfa_accepting {
122 for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() {
123 let dfa_transitions =
124 dfa_transitions.entry(dfa_state).or_insert_with(Default::default);
126 let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied());
128 let next_dfa_state = match nfa_transition {
129 &nfa::Transition::Byte(b) => *dfa_transitions
132 .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
133 &nfa::Transition::Ref(r) => *dfa_transitions
136 .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
139 for &next_nfa_state in next_nfa_states {
140 nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| {
141 queue.push((next_nfa_state, next_dfa_state));
148 let dfa_accepting = nfa_to_dfa[&nfa_accepting];
150 Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting }
153 pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> {
154 Some(&self.transitions.get(&start)?.byte_transitions)
157 pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
158 self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
161 pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
162 Some(&self.transitions.get(&start)?.ref_transitions)
167 pub(crate) fn new() -> Self {
168 static COUNTER: AtomicU32 = AtomicU32::new(0);
169 Self(COUNTER.fetch_add(1, Ordering::SeqCst))
173 impl<R> From<nfa::Transition<R>> for Transition<R>
177 fn from(nfa_transition: nfa::Transition<R>) -> Self {
178 match nfa_transition {
179 nfa::Transition::Byte(byte) => Transition::Byte(byte),
180 nfa::Transition::Ref(r) => Transition::Ref(r),