1 use super::{nfa, Byte, Nfa, Ref}; 2 use crate::Map; 3 use std::fmt; 4 use std::sync::atomic::{AtomicU32, Ordering}; 5 6 #[derive(PartialEq, Clone, Debug)] 7 pub(crate) struct Dfa<R> 8 where 9 R: Ref, 10 { 11 pub(crate) transitions: Map<State, Transitions<R>>, 12 pub(crate) start: State, 13 pub(crate) accepting: State, 14 } 15 16 #[derive(PartialEq, Clone, Debug)] 17 pub(crate) struct Transitions<R> 18 where 19 R: Ref, 20 { 21 byte_transitions: Map<Byte, State>, 22 ref_transitions: Map<R, State>, 23 } 24 25 impl<R> Default for Transitions<R> 26 where 27 R: Ref, 28 { default() -> Self29 fn default() -> Self { 30 Self { byte_transitions: Map::default(), ref_transitions: Map::default() } 31 } 32 } 33 34 impl<R> Transitions<R> 35 where 36 R: Ref, 37 { insert(&mut self, transition: Transition<R>, state: State)38 fn insert(&mut self, transition: Transition<R>, state: State) { 39 match transition { 40 Transition::Byte(b) => { 41 self.byte_transitions.insert(b, state); 42 } 43 Transition::Ref(r) => { 44 self.ref_transitions.insert(r, state); 45 } 46 } 47 } 48 } 49 50 /// The states in a `Nfa` represent byte offsets. 51 #[derive(Hash, Eq, PartialEq, PartialOrd, Ord, Copy, Clone)] 52 pub(crate) struct State(u32); 53 54 #[derive(Hash, Eq, PartialEq, Clone, Copy)] 55 pub(crate) enum Transition<R> 56 where 57 R: Ref, 58 { 59 Byte(Byte), 60 Ref(R), 61 } 62 63 impl fmt::Debug for State { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result64 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 65 write!(f, "S_{}", self.0) 66 } 67 } 68 69 impl<R> fmt::Debug for Transition<R> 70 where 71 R: Ref, 72 { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result73 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 74 match &self { 75 Self::Byte(b) => b.fmt(f), 76 Self::Ref(r) => r.fmt(f), 77 } 78 } 79 } 80 81 impl<R> Dfa<R> 82 where 83 R: Ref, 84 { unit() -> Self85 pub(crate) fn unit() -> Self { 86 let transitions: Map<State, Transitions<R>> = Map::default(); 87 let start = State::new(); 88 let accepting = start; 89 90 Self { transitions, start, accepting } 91 } 92 93 #[cfg(test)] bool() -> Self94 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(); 98 99 transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x00)), accepting); 100 101 transitions.entry(start).or_default().insert(Transition::Byte(Byte::Init(0x01)), accepting); 102 103 Self { transitions, start, accepting } 104 } 105 106 #[instrument(level = "debug")] from_nfa(nfa: Nfa<R>) -> Self107 pub(crate) fn from_nfa(nfa: Nfa<R>) -> Self { 108 let Nfa { transitions: nfa_transitions, start: nfa_start, accepting: nfa_accepting } = nfa; 109 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); 114 115 let mut queue = vec![(nfa_start, dfa_start)]; 116 117 while let Some((nfa_state, dfa_state)) = queue.pop() { 118 if nfa_state == nfa_accepting { 119 continue; 120 } 121 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); 125 126 let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied()); 127 128 let next_dfa_state = match nfa_transition { 129 &nfa::Transition::Byte(b) => *dfa_transitions 130 .byte_transitions 131 .entry(b) 132 .or_insert_with(|| mapped_state.unwrap_or_else(State::new)), 133 &nfa::Transition::Ref(r) => *dfa_transitions 134 .ref_transitions 135 .entry(r) 136 .or_insert_with(|| mapped_state.unwrap_or_else(State::new)), 137 }; 138 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)); 142 next_dfa_state 143 }); 144 } 145 } 146 } 147 148 let dfa_accepting = nfa_to_dfa[&nfa_accepting]; 149 150 Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting } 151 } 152 bytes_from(&self, start: State) -> Option<&Map<Byte, State>>153 pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> { 154 Some(&self.transitions.get(&start)?.byte_transitions) 155 } 156 byte_from(&self, start: State, byte: Byte) -> Option<State>157 pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> { 158 self.transitions.get(&start)?.byte_transitions.get(&byte).copied() 159 } 160 refs_from(&self, start: State) -> Option<&Map<R, State>>161 pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> { 162 Some(&self.transitions.get(&start)?.ref_transitions) 163 } 164 } 165 166 impl State { new() -> Self167 pub(crate) fn new() -> Self { 168 static COUNTER: AtomicU32 = AtomicU32::new(0); 169 Self(COUNTER.fetch_add(1, Ordering::SeqCst)) 170 } 171 } 172 173 impl<R> From<nfa::Transition<R>> for Transition<R> 174 where 175 R: Ref, 176 { from(nfa_transition: nfa::Transition<R>) -> Self177 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), 181 } 182 } 183 } 184