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 #[cfg_attr(feature = "rustc", allow(rustc::potential_query_instability))]
108 pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self {
109 let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa;
111 let mut dfa_transitions: Map<State, Transitions<R>> = Map::default();
112 let mut nfa_to_dfa: Map<nfa::State, State> = Map::default();
113 let dfa_start = State::new();
114 nfa_to_dfa.insert(nfa_start, dfa_start);
116 let mut queue = vec![(nfa_start, dfa_start)];
118 while let Some((nfa_state, dfa_state)) = queue.pop() {
119 if nfa_state == nfa_accepting {
123 for (nfa_transition, next_nfa_states) in nfa_transitions[&nfa_state].iter() {
124 let dfa_transitions =
125 dfa_transitions.entry(dfa_state).or_insert_with(Default::default);
127 let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied());
129 let next_dfa_state = match nfa_transition {
130 &nfa::Transition::Byte(b) => *dfa_transitions
133 .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
134 &nfa::Transition::Ref(r) => *dfa_transitions
137 .or_insert_with(|| mapped_state.unwrap_or_else(State::new)),
140 for &next_nfa_state in next_nfa_states {
141 nfa_to_dfa.entry(next_nfa_state).or_insert_with(|| {
142 queue.push((next_nfa_state, next_dfa_state));
149 let dfa_accepting = nfa_to_dfa[&nfa_accepting];
151 Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting }
154 pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> {
155 Some(&self.transitions.get(&start)?.byte_transitions)
158 pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> {
159 self.transitions.get(&start)?.byte_transitions.get(&byte).copied()
162 pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> {
163 Some(&self.transitions.get(&start)?.ref_transitions)
168 pub(crate) fn new() -> Self {
169 static COUNTER: AtomicU32 = AtomicU32::new(0);
170 Self(COUNTER.fetch_add(1, Ordering::SeqCst))
174 impl<R> From<nfa::Transition<R>> for Transition<R>
178 fn from(nfa_transition: nfa::Transition<R>) -> Self {
179 match nfa_transition {
180 nfa::Transition::Byte(byte) => Transition::Byte(byte),
181 nfa::Transition::Ref(r) => Transition::Ref(r),