Debian Codegraph @

.cargo/vendor/aho-corasick/src/packed/mod.rs

raw
1 /*!
2 Provides packed multiple substring search, principally for a small number of
3 patterns.
4
5 This sub-module provides vectorized routines for quickly finding
6 matches of a small number of patterns. In general, users of this crate
7 shouldn't need to interface with this module directly, as the primary
8 [`AhoCorasick`](crate::AhoCorasick) searcher will use these routines
9 automatically as a prefilter when applicable. However, in some cases, callers
10 may want to bypass the Aho-Corasick machinery entirely and use this vectorized
11 searcher directly.
12
13 # Overview
14
15 The primary types in this sub-module are:
16
17 * [`Searcher`] executes the actual search algorithm to report matches in a
18 haystack.
19 * [`Builder`] accumulates patterns incrementally and can construct a
20 `Searcher`.
21 * [`Config`] permits tuning the searcher, and itself will produce a `Builder`
22 (which can then be used to build a `Searcher`). Currently, the only tuneable
23 knob are the match semantics, but this may be expanded in the future.
24
25 # Examples
26
27 This example shows how to create a searcher from an iterator of patterns.
28 By default, leftmost-first match semantics are used. (See the top-level
29 [`MatchKind`] type for more details about match semantics, which apply
30 similarly to packed substring search.)
31
32 ```
33 use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
34
35 # fn example() -> Option<()> {
36 let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
37 let matches: Vec<PatternID> = searcher
38 .find_iter("foobar")
39 .map(|mat| mat.pattern())
40 .collect();
41 assert_eq!(vec![PatternID::ZERO], matches);
42 # Some(()) }
43 # if cfg!(all(feature = "std", any(
44 # target_arch = "x86_64", target_arch = "aarch64",
45 # ))) {
46 # example().unwrap()
47 # } else {
48 # assert!(example().is_none());
49 # }
50 ```
51
52 This example shows how to use [`Config`] to change the match semantics to
53 leftmost-longest:
54
55 ```
56 use aho_corasick::{packed::{Config, MatchKind}, PatternID};
57
58 # fn example() -> Option<()> {
59 let searcher = Config::new()
60 .match_kind(MatchKind::LeftmostLongest)
61 .builder()
62 .add("foo")
63 .add("foobar")
64 .build()?;
65 let matches: Vec<PatternID> = searcher
66 .find_iter("foobar")
67 .map(|mat| mat.pattern())
68 .collect();
69 assert_eq!(vec![PatternID::must(1)], matches);
70 # Some(()) }
71 # if cfg!(all(feature = "std", any(
72 # target_arch = "x86_64", target_arch = "aarch64",
73 # ))) {
74 # example().unwrap()
75 # } else {
76 # assert!(example().is_none());
77 # }
78 ```
79
80 # Packed substring searching
81
82 Packed substring searching refers to the use of SIMD (Single Instruction,
83 Multiple Data) to accelerate the detection of matches in a haystack. Unlike
84 conventional algorithms, such as Aho-Corasick, SIMD algorithms for substring
85 search tend to do better with a small number of patterns, where as Aho-Corasick
86 generally maintains reasonably consistent performance regardless of the number
87 of patterns you give it. Because of this, the vectorized searcher in this
88 sub-module cannot be used as a general purpose searcher, since building the
89 searcher may fail even when given a small number of patterns. However, in
90 exchange, when searching for a small number of patterns, searching can be quite
91 a bit faster than Aho-Corasick (sometimes by an order of magnitude).
92
93 The key take away here is that constructing a searcher from a list of patterns
94 is a fallible operation with no clear rules for when it will fail. While the
95 precise conditions under which building a searcher can fail is specifically an
96 implementation detail, here are some common reasons:
97
98 * Too many patterns were given. Typically, the limit is on the order of 100 or
99 so, but this limit may fluctuate based on available CPU features.
100 * The available packed algorithms require CPU features that aren't available.
101 For example, currently, this crate only provides packed algorithms for
102 `x86_64` and `aarch64`. Therefore, constructing a packed searcher on any
103 other target will always fail.
104 * Zero patterns were given, or one of the patterns given was empty. Packed
105 searchers require at least one pattern and that all patterns are non-empty.
106 * Something else about the nature of the patterns (typically based on
107 heuristics) suggests that a packed searcher would perform very poorly, so
108 no searcher is built.
109 */
110
111 pub use crate::packed::api::{Builder, Config, FindIter, MatchKind, Searcher};
112
113 mod api;
114 mod ext;
115 mod pattern;
116 mod rabinkarp;
117 mod teddy;
118 #[cfg(all(feature = "std", test))]
119 mod tests;
120 mod vector;