]>
Commit | Line | Data |
---|---|---|
064997fb FG |
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 | { | |
29 | 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 | { | |
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 { | |
64 | 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 | { | |
73 | 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 | { | |
85 | 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)] | |
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(); | |
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")] | |
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; | |
110 | ||
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); | |
115 | ||
116 | let mut queue = vec![(nfa_start, dfa_start)]; | |
117 | ||
118 | while let Some((nfa_state, dfa_state)) = queue.pop() { | |
119 | if nfa_state == nfa_accepting { | |
120 | continue; | |
121 | } | |
122 | ||
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); | |
126 | ||
127 | let mapped_state = next_nfa_states.iter().find_map(|x| nfa_to_dfa.get(x).copied()); | |
128 | ||
129 | let next_dfa_state = match nfa_transition { | |
130 | &nfa::Transition::Byte(b) => *dfa_transitions | |
131 | .byte_transitions | |
132 | .entry(b) | |
133 | .or_insert_with(|| mapped_state.unwrap_or_else(State::new)), | |
134 | &nfa::Transition::Ref(r) => *dfa_transitions | |
135 | .ref_transitions | |
136 | .entry(r) | |
137 | .or_insert_with(|| mapped_state.unwrap_or_else(State::new)), | |
138 | }; | |
139 | ||
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)); | |
143 | next_dfa_state | |
144 | }); | |
145 | } | |
146 | } | |
147 | } | |
148 | ||
149 | let dfa_accepting = nfa_to_dfa[&nfa_accepting]; | |
150 | ||
151 | Self { transitions: dfa_transitions, start: dfa_start, accepting: dfa_accepting } | |
152 | } | |
153 | ||
154 | pub(crate) fn bytes_from(&self, start: State) -> Option<&Map<Byte, State>> { | |
155 | Some(&self.transitions.get(&start)?.byte_transitions) | |
156 | } | |
157 | ||
158 | pub(crate) fn byte_from(&self, start: State, byte: Byte) -> Option<State> { | |
159 | self.transitions.get(&start)?.byte_transitions.get(&byte).copied() | |
160 | } | |
161 | ||
162 | pub(crate) fn refs_from(&self, start: State) -> Option<&Map<R, State>> { | |
163 | Some(&self.transitions.get(&start)?.ref_transitions) | |
164 | } | |
165 | } | |
166 | ||
167 | impl State { | |
168 | pub(crate) fn new() -> Self { | |
169 | static COUNTER: AtomicU32 = AtomicU32::new(0); | |
170 | Self(COUNTER.fetch_add(1, Ordering::SeqCst)) | |
171 | } | |
172 | } | |
173 | ||
174 | impl<R> From<nfa::Transition<R>> for Transition<R> | |
175 | where | |
176 | R: Ref, | |
177 | { | |
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), | |
182 | } | |
183 | } | |
184 | } |