Debian Codegraph @

.cargo/vendor/aho-corasick/DESIGN.md

raw
1 This document describes the internal design of this crate, which is an object
2 lesson in what happens when you take a fairly simple old algorithm like
3 Aho-Corasick and make it fast and production ready.
4
5 The target audience of this document is Rust programmers that have some
6 familiarity with string searching, however, one does not need to know the
7 Aho-Corasick algorithm in order to read this (it is explained below). One
8 should, however, know what a trie is. (If you don't, go read its Wikipedia
9 article.)
10
11 The center-piece of this crate is an implementation of Aho-Corasick. On its
12 own, Aho-Corasick isn't that complicated. The complex pieces come from the
13 different variants of Aho-Corasick implemented in this crate. Specifically,
14 they are:
15
16 * Aho-Corasick as a noncontiguous NFA. States have their transitions
17 represented sparsely, and each state puts its transitions in its own separate
18 allocation. Hence the same "noncontiguous."
19 * Aho-Corasick as a contiguous NFA. This NFA uses a single allocation to
20 represent the transitions of all states. That is, transitions are laid out
21 contiguously in memory. Moreover, states near the starting state are
22 represented densely, such that finding the next state ID takes a constant
23 number of instructions.
24 * Aho-Corasick as a DFA. In this case, all states are represented densely in
25 a transition table that uses one allocation.
26 * Supporting "standard" match semantics, along with its overlapping variant,
27 in addition to leftmost-first and leftmost-longest semantics. The "standard"
28 semantics are typically what you see in a textbook description of
29 Aho-Corasick. However, Aho-Corasick is also useful as an optimization in
30 regex engines, which often use leftmost-first or leftmost-longest semantics.
31 Thus, it is useful to implement those semantics here. The "standard" and
32 "leftmost" search algorithms are subtly different, and also require slightly
33 different construction algorithms.
34 * Support for ASCII case insensitive matching.
35 * Support for accelerating searches when the patterns all start with a small
36 number of fixed bytes. Or alternatively, when the patterns all contain a
37 small number of rare bytes. (Searching for these bytes uses SIMD vectorized
38 code courtesy of `memchr`.)
39 * Transparent support for alternative SIMD vectorized search routines for
40 smaller number of literals, such as the Teddy algorithm. We called these
41 "packed" search routines because they use SIMD. They can often be an order of
42 magnitude faster than just Aho-Corasick, but don't scale as well.
43 * Support for searching streams. This can reuse most of the underlying code,
44 but does require careful buffering support.
45 * Support for anchored searches, which permit efficient "is prefix" checks for
46 a large number of patterns.
47
48 When you combine all of this together along with trying to make everything as
49 fast as possible, what you end up with is enitrely too much code with too much
50 `unsafe`. Alas, I was not smart enough to figure out how to reduce it. Instead,
51 we will explain it.
52
53
54 # Basics
55
56 The fundamental problem this crate is trying to solve is to determine the
57 occurrences of possibly many patterns in a haystack. The naive way to solve
58 this is to look for a match for each pattern at each position in the haystack:
59
60 for i in 0..haystack.len():
61 for p in patterns.iter():
62 if haystack[i..].starts_with(p.bytes()):
63 return Match(p.id(), i, i + p.bytes().len())
64
65 Those four lines are effectively all this crate does. The problem with those
66 four lines is that they are very slow, especially when you're searching for a
67 large number of patterns.
68
69 While there are many different algorithms available to solve this, a popular
70 one is Aho-Corasick. It's a common solution because it's not too hard to
71 implement, scales quite well even when searching for thousands of patterns and
72 is generally pretty fast. Aho-Corasick does well here because, regardless of
73 the number of patterns you're searching for, it always visits each byte in the
74 haystack exactly once. This means, generally speaking, adding more patterns to
75 an Aho-Corasick automaton does not make it slower. (Strictly speaking, however,
76 this is not true, since a larger automaton will make less effective use of the
77 CPU's cache.)
78
79 Aho-Corasick can be succinctly described as a trie with state transitions
80 between some of the nodes that efficiently instruct the search algorithm to
81 try matching alternative keys in the trie. The trick is that these state
82 transitions are arranged such that each byte of input needs to be inspected
83 only once. These state transitions are typically called "failure transitions,"
84 because they instruct the searcher (the thing traversing the automaton while
85 reading from the haystack) what to do when a byte in the haystack does not
86 correspond to a valid transition in the current state of the trie.
87
88 More formally, a failure transition points to a state in the automaton that may
89 lead to a match whose prefix is a proper suffix of the path traversed through
90 the trie so far. (If no such proper suffix exists, then the failure transition
91 points back to the start state of the trie, effectively restarting the search.)
92 This is perhaps simpler to explain pictorally. For example, let's say we built
93 an Aho-Corasick automaton with the following patterns: 'abcd' and 'cef'. The
94 trie looks like this:
95
96 a - S1 - b - S2 - c - S3 - d - S4*
97 /
98 S0 - c - S5 - e - S6 - f - S7*
99
100 where states marked with a `*` are match states (meaning, the search algorithm
101 should stop and report a match to the caller).
102
103 So given this trie, it should be somewhat straight-forward to see how it can
104 be used to determine whether any particular haystack *starts* with either
105 `abcd` or `cef`. It's easy to express this in code:
106
107 fn has_prefix(trie: &Trie, haystack: &[u8]) -> bool {
108 let mut state_id = trie.start();
109 // If the empty pattern is in trie, then state_id is a match state.
110 if trie.is_match(state_id) {
111 return true;
112 }
113 for (i, &b) in haystack.iter().enumerate() {
114 state_id = match trie.next_state(state_id, b) {
115 Some(id) => id,
116 // If there was no transition for this state and byte, then we know
117 // the haystack does not start with one of the patterns in our trie.
118 None => return false,
119 };
120 if trie.is_match(state_id) {
121 return true;
122 }
123 }
124 false
125 }
126
127 And that's pretty much it. All we do is move through the trie starting with the
128 bytes at the beginning of the haystack. If we find ourselves in a position
129 where we can't move, or if we've looked through the entire haystack without
130 seeing a match state, then we know the haystack does not start with any of the
131 patterns in the trie.
132
133 The meat of the Aho-Corasick algorithm is in how we add failure transitions to
134 our trie to keep searching efficient. Specifically, it permits us to not only
135 check whether a haystack *starts* with any one of a number of patterns, but
136 rather, whether the haystack contains any of a number of patterns *anywhere* in
137 the haystack.
138
139 As mentioned before, failure transitions connect a proper suffix of the path
140 traversed through the trie before, with a path that leads to a match that has a
141 prefix corresponding to that proper suffix. So in our case, for patterns `abcd`
142 and `cef`, with a haystack `abcef`, we want to transition to state `S5` (from
143 the diagram above) from `S3` upon seeing that the byte following `c` is not
144 `d`. Namely, the proper suffix in this example is `c`, which is a prefix of
145 `cef`. So the modified diagram looks like this:
146
147
148 a - S1 - b - S2 - c - S3 - d - S4*
149 / /
150 / ----------------
151 / /
152 S0 - c - S5 - e - S6 - f - S7*
153
154 One thing that isn't shown in this diagram is that *all* states have a failure
155 transition, but only `S3` has a *non-trivial* failure transition. That is, all
156 other states have a failure transition back to the start state. So if our
157 haystack was `abzabcd`, then the searcher would transition back to `S0` after
158 seeing `z`, which effectively restarts the search. (Because there is no pattern
159 in our trie that has a prefix of `bz` or `z`.)
160
161 The code for traversing this *automaton* or *finite state machine* (it is no
162 longer just a trie) is not that much different from the `has_prefix` code
163 above:
164
165 fn contains(fsm: &FiniteStateMachine, haystack: &[u8]) -> bool {
166 let mut state_id = fsm.start();
167 // If the empty pattern is in fsm, then state_id is a match state.
168 if fsm.is_match(state_id) {
169 return true;
170 }
171 for (i, &b) in haystack.iter().enumerate() {
172 // While the diagram above doesn't show this, we may wind up needing
173 // to follow multiple failure transitions before we land on a state
174 // in which we can advance. Therefore, when searching for the next
175 // state, we need to loop until we don't see a failure transition.
176 //
177 // This loop terminates because the start state has no empty
178 // transitions. Every transition from the start state either points to
179 // another state, or loops back to the start state.
180 loop {
181 match fsm.next_state(state_id, b) {
182 Some(id) => {
183 state_id = id;
184 break;
185 }
186 // Unlike our code above, if there was no transition for this
187 // state, then we don't quit. Instead, we look for this state's
188 // failure transition and follow that instead.
189 None => {
190 state_id = fsm.next_fail_state(state_id);
191 }
192 };
193 }
194 if fsm.is_match(state_id) {
195 return true;
196 }
197 }
198 false
199 }
200
201 Other than the complication around traversing failure transitions, this code
202 is still roughly "traverse the automaton with bytes from the haystack, and quit
203 when a match is seen."
204
205 And that concludes our section on the basics. While we didn't go deep into how
206 the automaton is built (see `src/nfa/noncontiguous.rs`, which has detailed
207 comments about that), the basic structure of Aho-Corasick should be reasonably
208 clear.
209
210
211 # NFAs and DFAs
212
213 There are generally two types of finite automata: non-deterministic finite
214 automata (NFA) and deterministic finite automata (DFA). The difference between
215 them is, principally, that an NFA can be in multiple states at once. This is
216 typically accomplished by things called _epsilon_ transitions, where one could
217 move to a new state without consuming any bytes from the input. (The other
218 mechanism by which NFAs can be in more than one state is where the same byte in
219 a particular state transitions to multiple distinct states.) In contrast, a DFA
220 can only ever be in one state at a time. A DFA has no epsilon transitions, and
221 for any given state, a byte transitions to at most one other state.
222
223 By this formulation, the Aho-Corasick automaton described in the previous
224 section is an NFA. This is because failure transitions are, effectively,
225 epsilon transitions. That is, whenever the automaton is in state `S`, it is
226 actually in the set of states that are reachable by recursively following
227 failure transitions from `S` until you reach the start state. (This means
228 that, for example, the start state is always active since the start state is
229 reachable via failure transitions from any state in the automaton.)
230
231 NFAs have a lot of nice properties. They tend to be easier to construct, and
232 also tend to use less memory. However, their primary downside is that they are
233 typically slower to execute a search with. For example, the code above showing
234 how to search with an Aho-Corasick automaton needs to potentially iterate
235 through many failure transitions for every byte of input. While this is a
236 fairly small amount of overhead, this can add up, especially if the automaton
237 has a lot of overlapping patterns with a lot of failure transitions.
238
239 A DFA's search code, by contrast, looks like this:
240
241 fn contains(dfa: &DFA, haystack: &[u8]) -> bool {
242 let mut state_id = dfa.start();
243 // If the empty pattern is in dfa, then state_id is a match state.
244 if dfa.is_match(state_id) {
245 return true;
246 }
247 for (i, &b) in haystack.iter().enumerate() {
248 // An Aho-Corasick DFA *never* has a missing state that requires
249 // failure transitions to be followed. One byte of input advances the
250 // automaton by one state. Always.
251 state_id = dfa.next_state(state_id, b);
252 if dfa.is_match(state_id) {
253 return true;
254 }
255 }
256 false
257 }
258
259 The search logic here is much simpler than for the NFA, and this tends to
260 translate into significant performance benefits as well, since there's a lot
261 less work being done for each byte in the haystack. How is this accomplished?
262 It's done by pre-following all failure transitions for all states for all bytes
263 in the alphabet, and then building a single state transition table. Building
264 this DFA can be much more costly than building the NFA, and use much more
265 memory, but the better performance can be worth it.
266
267 Users of this crate can actually choose between using one of two possible NFAs
268 (noncontiguous or contiguous) or a DFA. By default, a contiguous NFA is used,
269 in most circumstances, but if the number of patterns is small enough a DFA will
270 be used. A contiguous NFA is chosen because it uses orders of magnitude less
271 memory than a DFA, takes only a little longer to build than a noncontiguous
272 NFA and usually gets pretty close to the search speed of a DFA. (Callers can
273 override this automatic selection via the `AhoCorasickBuilder::start_kind`
274 configuration.)
275
276
277 # More DFA tricks
278
279 As described in the previous section, one of the downsides of using a DFA
280 is that it uses more memory and can take longer to build. One small way of
281 mitigating these concerns is to map the alphabet used by the automaton into
282 a smaller space. Typically, the alphabet of a DFA has 256 elements in it:
283 one element for each possible value that fits into a byte. However, in many
284 cases, one does not need the full alphabet. For example, if all patterns in an
285 Aho-Corasick automaton are ASCII letters, then this only uses up 52 distinct
286 bytes. As far as the automaton is concerned, the rest of the 204 bytes are
287 indistinguishable from one another: they will never disrciminate between a
288 match or a non-match. Therefore, in cases like that, the alphabet can be shrunk
289 to just 53 elements. One for each ASCII letter, and then another to serve as a
290 placeholder for every other unused byte.
291
292 In practice, this library doesn't quite compute the optimal set of equivalence
293 classes, but it's close enough in most cases. The key idea is that this then
294 allows the transition table for the DFA to be potentially much smaller. The
295 downside of doing this, however, is that since the transition table is defined
296 in terms of this smaller alphabet space, every byte in the haystack must be
297 re-mapped to this smaller space. This requires an additional 256-byte table.
298 In practice, this can lead to a small search time hit, but it can be difficult
299 to measure. Moreover, it can sometimes lead to faster search times for bigger
300 automata, since it could be difference between more parts of the automaton
301 staying in the CPU cache or not.
302
303 One other trick for DFAs employed by this crate is the notion of premultiplying
304 state identifiers. Specifically, the normal way to compute the next transition
305 in a DFA is via the following (assuming that the transition table is laid out
306 sequentially in memory, in row-major order, where the rows are states):
307
308 next_state_id = dfa.transitions[current_state_id * 256 + current_byte]
309
310 However, since the value `256` is a fixed constant, we can actually premultiply
311 the state identifiers in the table when we build the table initially. Then, the
312 next transition computation simply becomes:
313
314 next_state_id = dfa.transitions[current_state_id + current_byte]
315
316 This doesn't seem like much, but when this is being executed for every byte of
317 input that you're searching, saving that extra multiplication instruction can
318 add up.
319
320 The same optimization works even when equivalence classes are enabled, as
321 described above. The only difference is that the premultiplication is by the
322 total number of equivalence classes instead of 256.
323
324 There isn't much downside to premultiplying state identifiers, other than it
325 imposes a smaller limit on the total number of states in the DFA. Namely, with
326 premultiplied state identifiers, you run out of room in your state identifier
327 representation more rapidly than if the identifiers are just state indices.
328
329 Both equivalence classes and premultiplication are always enabled. There is a
330 `AhoCorasickBuilder::byte_classes` configuration, but disabling this just makes
331 it so there are always 256 equivalence classes, i.e., every class corresponds
332 to precisely one byte. When it's disabled, the equivalence class map itself is
333 still used. The purpose of disabling it is when one is debugging the underlying
334 automaton. It can be easier to comprehend when it uses actual byte values for
335 its transitions instead of equivalence classes.
336
337
338 # Match semantics
339
340 One of the more interesting things about this implementation of Aho-Corasick
341 that (as far as this author knows) separates it from other implementations, is
342 that it natively supports leftmost-first and leftmost-longest match semantics.
343 Briefly, match semantics refer to the decision procedure by which searching
344 will disambiguate matches when there are multiple to choose from:
345
346 * **standard** match semantics emits matches as soon as they are detected by
347 the automaton. This is typically equivalent to the textbook non-overlapping
348 formulation of Aho-Corasick.
349 * **leftmost-first** match semantics means that 1) the next match is the match
350 starting at the leftmost position and 2) among multiple matches starting at
351 the same leftmost position, the match corresponding to the pattern provided
352 first by the caller is reported.
353 * **leftmost-longest** is like leftmost-first, except when there are multiple
354 matches starting at the same leftmost position, the pattern corresponding to
355 the longest match is returned.
356
357 (The crate API documentation discusses these differences, with examples, in
358 more depth on the `MatchKind` type.)
359
360 The reason why supporting these match semantics is important is because it
361 gives the user more control over the match procedure. For example,
362 leftmost-first permits users to implement match priority by simply putting the
363 higher priority patterns first. Leftmost-longest, on the other hand, permits
364 finding the longest possible match, which might be useful when trying to find
365 words matching a dictionary. Additionally, regex engines often want to use
366 Aho-Corasick as an optimization when searching for an alternation of literals.
367 In order to preserve correct match semantics, regex engines typically can't use
368 the standard textbook definition directly, since regex engines will implement
369 either leftmost-first (Perl-like) or leftmost-longest (POSIX) match semantics.
370
371 Supporting leftmost semantics requires a couple key changes:
372
373 * Constructing the Aho-Corasick automaton changes a bit in both how the trie is
374 constructed and how failure transitions are found. Namely, only a subset
375 of the failure transitions are added. Specifically, only the failure
376 transitions that either do not occur after a match or do occur after a match
377 but preserve that match are kept. (More details on this can be found in
378 `src/nfa/noncontiguous.rs`.)
379 * The search algorithm changes slightly. Since we are looking for the leftmost
380 match, we cannot quit as soon as a match is detected. Instead, after a match
381 is detected, we must keep searching until either the end of the input or
382 until a dead state is seen. (Dead states are not used for standard match
383 semantics. Dead states mean that searching should stop after a match has been
384 found.)
385
386 Most other implementations of Aho-Corasick do support leftmost match semantics,
387 but they do it with more overhead at search time, or even worse, with a queue
388 of matches and sophisticated hijinks to disambiguate the matches. While our
389 construction algorithm becomes a bit more complicated, the correct match
390 semantics fall out from the structure of the automaton itself.
391
392
393 # Overlapping matches
394
395 One of the nice properties of an Aho-Corasick automaton is that it can report
396 all possible matches, even when they overlap with one another. In this mode,
397 the match semantics don't matter, since all possible matches are reported.
398 Overlapping searches work just like regular searches, except the state
399 identifier at which the previous search left off is carried over to the next
400 search, so that it can pick up where it left off. If there are additional
401 matches at that state, then they are reported before resuming the search.
402
403 Enabling leftmost-first or leftmost-longest match semantics causes the
404 automaton to use a subset of all failure transitions, which means that
405 overlapping searches cannot be used. Therefore, if leftmost match semantics are
406 used, attempting to do an overlapping search will return an error (or panic
407 when using the infallible APIs). Thus, to get overlapping searches, the caller
408 must use the default standard match semantics. This behavior was chosen because
409 there are only two alternatives, which were deemed worse:
410
411 * Compile two automatons internally, one for standard semantics and one for
412 the semantics requested by the caller (if not standard).
413 * Create a new type, distinct from the `AhoCorasick` type, which has different
414 capabilities based on the configuration options.
415
416 The first is untenable because of the amount of memory used by the automaton.
417 The second increases the complexity of the API too much by adding too many
418 types that do similar things. It is conceptually much simpler to keep all
419 searching isolated to a single type.
420
421
422 # Stream searching
423
424 Since Aho-Corasick is an automaton, it is possible to do partial searches on
425 partial parts of the haystack, and then resume that search on subsequent pieces
426 of the haystack. This is useful when the haystack you're trying to search is
427 not stored contiguously in memory, or if one does not want to read the entire
428 haystack into memory at once.
429
430 Currently, only standard semantics are supported for stream searching. This is
431 some of the more complicated code in this crate, and is something I would very
432 much like to improve. In particular, it currently has the restriction that it
433 must buffer at least enough of the haystack in memory in order to fit the
434 longest possible match. The difficulty in getting stream searching right is
435 that the implementation choices (such as the buffer size) often impact what the
436 API looks like and what it's allowed to do.
437
438
439 # Prefilters
440
441 In some cases, Aho-Corasick is not the fastest way to find matches containing
442 multiple patterns. Sometimes, the search can be accelerated using highly
443 optimized SIMD routines. For example, consider searching the following
444 patterns:
445
446 Sherlock
447 Moriarty
448 Watson
449
450 It is plausible that it would be much faster to quickly look for occurrences of
451 the leading bytes, `S`, `M` or `W`, before trying to start searching via the
452 automaton. Indeed, this is exactly what this crate will do.
453
454 When there are more than three distinct starting bytes, then this crate will
455 look for three distinct bytes occurring at any position in the patterns, while
456 preferring bytes that are heuristically determined to be rare over others. For
457 example:
458
459 Abuzz
460 Sanchez
461 Vasquez
462 Topaz
463 Waltz
464
465 Here, we have more than 3 distinct starting bytes, but all of the patterns
466 contain `z`, which is typically a rare byte. In this case, the prefilter will
467 scan for `z`, back up a bit, and then execute the Aho-Corasick automaton.
468
469 If all of that fails, then a packed multiple substring algorithm will be
470 attempted. Currently, the only algorithm available for this is Teddy, but more
471 may be added in the future. Teddy is unlike the above prefilters in that it
472 confirms its own matches, so when Teddy is active, it might not be necessary
473 for Aho-Corasick to run at all. However, the current Teddy implementation
474 only works in `x86_64` when SSSE3 or AVX2 are available or in `aarch64`
475 (using NEON), and moreover, only works _well_ when there are a small number
476 of patterns (say, less than 100). Teddy also requires the haystack to be of a
477 certain length (more than 16-34 bytes). When the haystack is shorter than that,
478 Rabin-Karp is used instead. (See `src/packed/rabinkarp.rs`.)
479
480 There is a more thorough description of Teddy at
481 [`src/packed/teddy/README.md`](src/packed/teddy/README.md).