Debian Codegraph @

.cargo/vendor/aho-corasick/src/transducer.rs

raw
1 /*!
2 Provides implementations of `fst::Automaton` for Aho-Corasick automata.
3
4 This works by providing two wrapper types, [`Anchored`] and [`Unanchored`].
5 The former executes an anchored search on an FST while the latter executes
6 an unanchored search. Building these wrappers is fallible and will fail if
7 the underlying Aho-Corasick automaton does not support the type of search it
8 represents.
9 */
10
11 use crate::{
12 automaton::{Automaton, StateID},
13 Anchored as AcAnchored, Input, MatchError,
14 };
15
16 /// Represents an unanchored Aho-Corasick search of a finite state transducer.
17 ///
18 /// Wrapping an Aho-Corasick automaton in `Unanchored` will fail if the
19 /// underlying automaton does not support unanchored searches.
20 ///
21 /// # Example
22 ///
23 /// This shows how to build an FST of keys and then run an unanchored search on
24 /// those keys using an Aho-Corasick automaton.
25 ///
26 /// ```
27 /// use aho_corasick::{nfa::contiguous::NFA, transducer::Unanchored};
28 /// use fst::{Automaton, IntoStreamer, Set, Streamer};
29 ///
30 /// let set = Set::from_iter(&["abcd", "bc", "bcd", "xyz"]).unwrap();
31 /// let nfa = NFA::new(&["bcd", "x"]).unwrap();
32 /// // NFAs always support both unanchored and anchored searches.
33 /// let searcher = Unanchored::new(&nfa).unwrap();
34 ///
35 /// let mut stream = set.search(searcher).into_stream();
36 /// let mut results = vec![];
37 /// while let Some(key) = stream.next() {
38 /// results.push(std::str::from_utf8(key).unwrap().to_string());
39 /// }
40 /// assert_eq!(vec!["abcd", "bcd", "xyz"], results);
41 /// ```
42 #[derive(Clone, Debug)]
43 pub struct Unanchored<A>(A);
44
45 impl<A: Automaton> Unanchored<A> {
46 /// Create a new `Unanchored` implementation of the `fst::Automaton` trait.
47 ///
48 /// If the given Aho-Corasick automaton does not support unanchored
49 /// searches, then this returns an error.
50 pub fn new(aut: A) -> Result<Unanchored<A>, MatchError> {
51 let input = Input::new("").anchored(AcAnchored::No);
52 let _ = aut.start_state(&input)?;
53 Ok(Unanchored(aut))
54 }
55
56 /// Returns a borrow to the underlying automaton.
57 pub fn as_ref(&self) -> &A {
58 &self.0
59 }
60
61 /// Unwrap this value and return the inner automaton.
62 pub fn into_inner(self) -> A {
63 self.0
64 }
65 }
66
67 impl<A: Automaton> fst::Automaton for Unanchored<A> {
68 type State = StateID;
69
70 #[inline]
71 fn start(&self) -> StateID {
72 let input = Input::new("").anchored(AcAnchored::No);
73 self.0.start_state(&input).expect("support for unanchored searches")
74 }
75
76 #[inline]
77 fn is_match(&self, state: &StateID) -> bool {
78 self.0.is_match(*state)
79 }
80
81 #[inline]
82 fn accept(&self, state: &StateID, byte: u8) -> StateID {
83 if fst::Automaton::is_match(self, state) {
84 return *state;
85 }
86 self.0.next_state(AcAnchored::No, *state, byte)
87 }
88
89 #[inline]
90 fn can_match(&self, state: &StateID) -> bool {
91 !self.0.is_dead(*state)
92 }
93 }
94
95 /// Represents an anchored Aho-Corasick search of a finite state transducer.
96 ///
97 /// Wrapping an Aho-Corasick automaton in `Unanchored` will fail if the
98 /// underlying automaton does not support unanchored searches.
99 ///
100 /// # Example
101 ///
102 /// This shows how to build an FST of keys and then run an anchored search on
103 /// those keys using an Aho-Corasick automaton.
104 ///
105 /// ```
106 /// use aho_corasick::{nfa::contiguous::NFA, transducer::Anchored};
107 /// use fst::{Automaton, IntoStreamer, Set, Streamer};
108 ///
109 /// let set = Set::from_iter(&["abcd", "bc", "bcd", "xyz"]).unwrap();
110 /// let nfa = NFA::new(&["bcd", "x"]).unwrap();
111 /// // NFAs always support both unanchored and anchored searches.
112 /// let searcher = Anchored::new(&nfa).unwrap();
113 ///
114 /// let mut stream = set.search(searcher).into_stream();
115 /// let mut results = vec![];
116 /// while let Some(key) = stream.next() {
117 /// results.push(std::str::from_utf8(key).unwrap().to_string());
118 /// }
119 /// assert_eq!(vec!["bcd", "xyz"], results);
120 /// ```
121 ///
122 /// This is like the example above, except we use an Aho-Corasick DFA, which
123 /// requires explicitly configuring it to support anchored searches. (NFAs
124 /// unconditionally support both unanchored and anchored searches.)
125 ///
126 /// ```
127 /// use aho_corasick::{dfa::DFA, transducer::Anchored, StartKind};
128 /// use fst::{Automaton, IntoStreamer, Set, Streamer};
129 ///
130 /// let set = Set::from_iter(&["abcd", "bc", "bcd", "xyz"]).unwrap();
131 /// let dfa = DFA::builder()
132 /// .start_kind(StartKind::Anchored)
133 /// .build(&["bcd", "x"])
134 /// .unwrap();
135 /// // We've explicitly configured our DFA to support anchored searches.
136 /// let searcher = Anchored::new(&dfa).unwrap();
137 ///
138 /// let mut stream = set.search(searcher).into_stream();
139 /// let mut results = vec![];
140 /// while let Some(key) = stream.next() {
141 /// results.push(std::str::from_utf8(key).unwrap().to_string());
142 /// }
143 /// assert_eq!(vec!["bcd", "xyz"], results);
144 /// ```
145 #[derive(Clone, Debug)]
146 pub struct Anchored<A>(A);
147
148 impl<A: Automaton> Anchored<A> {
149 /// Create a new `Anchored` implementation of the `fst::Automaton` trait.
150 ///
151 /// If the given Aho-Corasick automaton does not support anchored searches,
152 /// then this returns an error.
153 pub fn new(aut: A) -> Result<Anchored<A>, MatchError> {
154 let input = Input::new("").anchored(AcAnchored::Yes);
155 let _ = aut.start_state(&input)?;
156 Ok(Anchored(aut))
157 }
158
159 /// Returns a borrow to the underlying automaton.
160 pub fn as_ref(&self) -> &A {
161 &self.0
162 }
163
164 /// Unwrap this value and return the inner automaton.
165 pub fn into_inner(self) -> A {
166 self.0
167 }
168 }
169
170 impl<A: Automaton> fst::Automaton for Anchored<A> {
171 type State = StateID;
172
173 #[inline]
174 fn start(&self) -> StateID {
175 let input = Input::new("").anchored(AcAnchored::Yes);
176 self.0.start_state(&input).expect("support for unanchored searches")
177 }
178
179 #[inline]
180 fn is_match(&self, state: &StateID) -> bool {
181 self.0.is_match(*state)
182 }
183
184 #[inline]
185 fn accept(&self, state: &StateID, byte: u8) -> StateID {
186 if fst::Automaton::is_match(self, state) {
187 return *state;
188 }
189 self.0.next_state(AcAnchored::Yes, *state, byte)
190 }
191
192 #[inline]
193 fn can_match(&self, state: &StateID) -> bool {
194 !self.0.is_dead(*state)
195 }
196 }
197
198 #[cfg(test)]
199 mod tests {
200 use alloc::{string::String, vec, vec::Vec};
201
202 use fst::{Automaton, IntoStreamer, Set, Streamer};
203
204 use crate::{
205 dfa::DFA,
206 nfa::{contiguous, noncontiguous},
207 StartKind,
208 };
209
210 use super::*;
211
212 fn search<A: Automaton, D: AsRef<[u8]>>(
213 set: &Set<D>,
214 aut: A,
215 ) -> Vec<String> {
216 let mut stream = set.search(aut).into_stream();
217 let mut results = vec![];
218 while let Some(key) = stream.next() {
219 results.push(String::from(core::str::from_utf8(key).unwrap()));
220 }
221 results
222 }
223
224 #[test]
225 fn unanchored() {
226 let set =
227 Set::from_iter(&["a", "bar", "baz", "wat", "xba", "xbax", "z"])
228 .unwrap();
229 let patterns = vec!["baz", "bax"];
230 let expected = vec!["baz", "xbax"];
231
232 let aut = Unanchored(noncontiguous::NFA::new(&patterns).unwrap());
233 let got = search(&set, &aut);
234 assert_eq!(got, expected);
235
236 let aut = Unanchored(contiguous::NFA::new(&patterns).unwrap());
237 let got = search(&set, &aut);
238 assert_eq!(got, expected);
239
240 let aut = Unanchored(DFA::new(&patterns).unwrap());
241 let got = search(&set, &aut);
242 assert_eq!(got, expected);
243 }
244
245 #[test]
246 fn anchored() {
247 let set =
248 Set::from_iter(&["a", "bar", "baz", "wat", "xba", "xbax", "z"])
249 .unwrap();
250 let patterns = vec!["baz", "bax"];
251 let expected = vec!["baz"];
252
253 let aut = Anchored(noncontiguous::NFA::new(&patterns).unwrap());
254 let got = search(&set, &aut);
255 assert_eq!(got, expected);
256
257 let aut = Anchored(contiguous::NFA::new(&patterns).unwrap());
258 let got = search(&set, &aut);
259 assert_eq!(got, expected);
260
261 let aut = Anchored(
262 DFA::builder()
263 .start_kind(StartKind::Anchored)
264 .build(&patterns)
265 .unwrap(),
266 );
267 let got = search(&set, &aut);
268 assert_eq!(got, expected);
269 }
270 }