aho_corasick/packed/
api.rs

1use alloc::sync::Arc;
2
3use crate::{
4    packed::{pattern::Patterns, rabinkarp::RabinKarp, teddy},
5    util::search::{Match, Span},
6};
7
8/// This is a limit placed on the total number of patterns we're willing to try
9/// and match at once. As more sophisticated algorithms are added, this number
10/// may be increased.
11const PATTERN_LIMIT: usize = 128;
12
13/// A knob for controlling the match semantics of a packed multiple string
14/// searcher.
15///
16/// This differs from the [`MatchKind`](crate::MatchKind) type in the top-level
17/// crate module in that it doesn't support "standard" match semantics,
18/// and instead only supports leftmost-first or leftmost-longest. Namely,
19/// "standard" semantics cannot be easily supported by packed searchers.
20///
21/// For more information on the distinction between leftmost-first and
22/// leftmost-longest, see the docs on the top-level `MatchKind` type.
23///
24/// Unlike the top-level `MatchKind` type, the default match semantics for this
25/// type are leftmost-first.
26#[derive(Clone, Copy, Debug, Eq, PartialEq)]
27#[non_exhaustive]
28pub enum MatchKind {
29    /// Use leftmost-first match semantics, which reports leftmost matches.
30    /// When there are multiple possible leftmost matches, the match
31    /// corresponding to the pattern that appeared earlier when constructing
32    /// the automaton is reported.
33    ///
34    /// This is the default.
35    LeftmostFirst,
36    /// Use leftmost-longest match semantics, which reports leftmost matches.
37    /// When there are multiple possible leftmost matches, the longest match
38    /// is chosen.
39    LeftmostLongest,
40}
41
42impl Default for MatchKind {
43    fn default() -> MatchKind {
44        MatchKind::LeftmostFirst
45    }
46}
47
48/// The configuration for a packed multiple pattern searcher.
49///
50/// The configuration is currently limited only to being able to select the
51/// match semantics (leftmost-first or leftmost-longest) of a searcher. In the
52/// future, more knobs may be made available.
53///
54/// A configuration produces a [`packed::Builder`](Builder), which in turn can
55/// be used to construct a [`packed::Searcher`](Searcher) for searching.
56///
57/// # Example
58///
59/// This example shows how to use leftmost-longest semantics instead of the
60/// default (leftmost-first).
61///
62/// ```
63/// use aho_corasick::{packed::{Config, MatchKind}, PatternID};
64///
65/// # fn example() -> Option<()> {
66/// let searcher = Config::new()
67///     .match_kind(MatchKind::LeftmostLongest)
68///     .builder()
69///     .add("foo")
70///     .add("foobar")
71///     .build()?;
72/// let matches: Vec<PatternID> = searcher
73///     .find_iter("foobar")
74///     .map(|mat| mat.pattern())
75///     .collect();
76/// assert_eq!(vec![PatternID::must(1)], matches);
77/// # Some(()) }
78/// # if cfg!(all(feature = "std", any(
79/// #     target_arch = "x86_64", target_arch = "aarch64",
80/// # ))) {
81/// #     example().unwrap()
82/// # } else {
83/// #     assert!(example().is_none());
84/// # }
85/// ```
86#[derive(Clone, Debug)]
87pub struct Config {
88    kind: MatchKind,
89    force: Option<ForceAlgorithm>,
90    only_teddy_fat: Option<bool>,
91    only_teddy_256bit: Option<bool>,
92    heuristic_pattern_limits: bool,
93}
94
95/// An internal option for forcing the use of a particular packed algorithm.
96///
97/// When an algorithm is forced, if a searcher could not be constructed for it,
98/// then no searcher will be returned even if an alternative algorithm would
99/// work.
100#[derive(Clone, Debug)]
101enum ForceAlgorithm {
102    Teddy,
103    RabinKarp,
104}
105
106impl Default for Config {
107    fn default() -> Config {
108        Config::new()
109    }
110}
111
112impl Config {
113    /// Create a new default configuration. A default configuration uses
114    /// leftmost-first match semantics.
115    pub fn new() -> Config {
116        Config {
117            kind: MatchKind::LeftmostFirst,
118            force: None,
119            only_teddy_fat: None,
120            only_teddy_256bit: None,
121            heuristic_pattern_limits: true,
122        }
123    }
124
125    /// Create a packed builder from this configuration. The builder can be
126    /// used to accumulate patterns and create a [`Searcher`] from them.
127    pub fn builder(&self) -> Builder {
128        Builder::from_config(self.clone())
129    }
130
131    /// Set the match semantics for this configuration.
132    pub fn match_kind(&mut self, kind: MatchKind) -> &mut Config {
133        self.kind = kind;
134        self
135    }
136
137    /// An undocumented method for forcing the use of the Teddy algorithm.
138    ///
139    /// This is only exposed for more precise testing and benchmarks. Callers
140    /// should not use it as it is not part of the API stability guarantees of
141    /// this crate.
142    #[doc(hidden)]
143    pub fn only_teddy(&mut self, yes: bool) -> &mut Config {
144        if yes {
145            self.force = Some(ForceAlgorithm::Teddy);
146        } else {
147            self.force = None;
148        }
149        self
150    }
151
152    /// An undocumented method for forcing the use of the Fat Teddy algorithm.
153    ///
154    /// This is only exposed for more precise testing and benchmarks. Callers
155    /// should not use it as it is not part of the API stability guarantees of
156    /// this crate.
157    #[doc(hidden)]
158    pub fn only_teddy_fat(&mut self, yes: Option<bool>) -> &mut Config {
159        self.only_teddy_fat = yes;
160        self
161    }
162
163    /// An undocumented method for forcing the use of SSE (`Some(false)`) or
164    /// AVX (`Some(true)`) algorithms.
165    ///
166    /// This is only exposed for more precise testing and benchmarks. Callers
167    /// should not use it as it is not part of the API stability guarantees of
168    /// this crate.
169    #[doc(hidden)]
170    pub fn only_teddy_256bit(&mut self, yes: Option<bool>) -> &mut Config {
171        self.only_teddy_256bit = yes;
172        self
173    }
174
175    /// An undocumented method for forcing the use of the Rabin-Karp algorithm.
176    ///
177    /// This is only exposed for more precise testing and benchmarks. Callers
178    /// should not use it as it is not part of the API stability guarantees of
179    /// this crate.
180    #[doc(hidden)]
181    pub fn only_rabin_karp(&mut self, yes: bool) -> &mut Config {
182        if yes {
183            self.force = Some(ForceAlgorithm::RabinKarp);
184        } else {
185            self.force = None;
186        }
187        self
188    }
189
190    /// Request that heuristic limitations on the number of patterns be
191    /// employed. This useful to disable for benchmarking where one wants to
192    /// explore how Teddy performs on large number of patterns even if the
193    /// heuristics would otherwise refuse construction.
194    ///
195    /// This is enabled by default.
196    pub fn heuristic_pattern_limits(&mut self, yes: bool) -> &mut Config {
197        self.heuristic_pattern_limits = yes;
198        self
199    }
200}
201
202/// A builder for constructing a packed searcher from a collection of patterns.
203///
204/// # Example
205///
206/// This example shows how to use a builder to construct a searcher. By
207/// default, leftmost-first match semantics are used.
208///
209/// ```
210/// use aho_corasick::{packed::{Builder, MatchKind}, PatternID};
211///
212/// # fn example() -> Option<()> {
213/// let searcher = Builder::new()
214///     .add("foobar")
215///     .add("foo")
216///     .build()?;
217/// let matches: Vec<PatternID> = searcher
218///     .find_iter("foobar")
219///     .map(|mat| mat.pattern())
220///     .collect();
221/// assert_eq!(vec![PatternID::ZERO], matches);
222/// # Some(()) }
223/// # if cfg!(all(feature = "std", any(
224/// #     target_arch = "x86_64", target_arch = "aarch64",
225/// # ))) {
226/// #     example().unwrap()
227/// # } else {
228/// #     assert!(example().is_none());
229/// # }
230/// ```
231#[derive(Clone, Debug)]
232pub struct Builder {
233    /// The configuration of this builder and subsequent matcher.
234    config: Config,
235    /// Set to true if the builder detects that a matcher cannot be built.
236    inert: bool,
237    /// The patterns provided by the caller.
238    patterns: Patterns,
239}
240
241impl Builder {
242    /// Create a new builder for constructing a multi-pattern searcher. This
243    /// constructor uses the default configuration.
244    pub fn new() -> Builder {
245        Builder::from_config(Config::new())
246    }
247
248    fn from_config(config: Config) -> Builder {
249        Builder { config, inert: false, patterns: Patterns::new() }
250    }
251
252    /// Build a searcher from the patterns added to this builder so far.
253    pub fn build(&self) -> Option<Searcher> {
254        if self.inert || self.patterns.is_empty() {
255            return None;
256        }
257        let mut patterns = self.patterns.clone();
258        patterns.set_match_kind(self.config.kind);
259        let patterns = Arc::new(patterns);
260        let rabinkarp = RabinKarp::new(&patterns);
261        // Effectively, we only want to return a searcher if we can use Teddy,
262        // since Teddy is our only fast packed searcher at the moment.
263        // Rabin-Karp is only used when searching haystacks smaller than what
264        // Teddy can support. Thus, the only way to get a Rabin-Karp searcher
265        // is to force it using undocumented APIs (for tests/benchmarks).
266        let (search_kind, minimum_len) = match self.config.force {
267            None | Some(ForceAlgorithm::Teddy) => {
268                debug!("trying to build Teddy packed matcher");
269                let teddy = match self.build_teddy(Arc::clone(&patterns)) {
270                    None => return None,
271                    Some(teddy) => teddy,
272                };
273                let minimum_len = teddy.minimum_len();
274                (SearchKind::Teddy(teddy), minimum_len)
275            }
276            Some(ForceAlgorithm::RabinKarp) => {
277                debug!("using Rabin-Karp packed matcher");
278                (SearchKind::RabinKarp, 0)
279            }
280        };
281        Some(Searcher { patterns, rabinkarp, search_kind, minimum_len })
282    }
283
284    fn build_teddy(&self, patterns: Arc<Patterns>) -> Option<teddy::Searcher> {
285        teddy::Builder::new()
286            .only_256bit(self.config.only_teddy_256bit)
287            .only_fat(self.config.only_teddy_fat)
288            .heuristic_pattern_limits(self.config.heuristic_pattern_limits)
289            .build(patterns)
290    }
291
292    /// Add the given pattern to this set to match.
293    ///
294    /// The order in which patterns are added is significant. Namely, when
295    /// using leftmost-first match semantics, then when multiple patterns can
296    /// match at a particular location, the pattern that was added first is
297    /// used as the match.
298    ///
299    /// If the number of patterns added exceeds the amount supported by packed
300    /// searchers, then the builder will stop accumulating patterns and render
301    /// itself inert. At this point, constructing a searcher will always return
302    /// `None`.
303    pub fn add<P: AsRef<[u8]>>(&mut self, pattern: P) -> &mut Builder {
304        if self.inert {
305            return self;
306        } else if self.patterns.len() >= PATTERN_LIMIT {
307            self.inert = true;
308            self.patterns.reset();
309            return self;
310        }
311        // Just in case PATTERN_LIMIT increases beyond u16::MAX.
312        assert!(self.patterns.len() <= core::u16::MAX as usize);
313
314        let pattern = pattern.as_ref();
315        if pattern.is_empty() {
316            self.inert = true;
317            self.patterns.reset();
318            return self;
319        }
320        self.patterns.add(pattern);
321        self
322    }
323
324    /// Add the given iterator of patterns to this set to match.
325    ///
326    /// The iterator must yield elements that can be converted into a `&[u8]`.
327    ///
328    /// The order in which patterns are added is significant. Namely, when
329    /// using leftmost-first match semantics, then when multiple patterns can
330    /// match at a particular location, the pattern that was added first is
331    /// used as the match.
332    ///
333    /// If the number of patterns added exceeds the amount supported by packed
334    /// searchers, then the builder will stop accumulating patterns and render
335    /// itself inert. At this point, constructing a searcher will always return
336    /// `None`.
337    pub fn extend<I, P>(&mut self, patterns: I) -> &mut Builder
338    where
339        I: IntoIterator<Item = P>,
340        P: AsRef<[u8]>,
341    {
342        for p in patterns {
343            self.add(p);
344        }
345        self
346    }
347
348    /// Returns the number of patterns added to this builder.
349    pub fn len(&self) -> usize {
350        self.patterns.len()
351    }
352
353    /// Returns the length, in bytes, of the shortest pattern added.
354    pub fn minimum_len(&self) -> usize {
355        self.patterns.minimum_len()
356    }
357}
358
359impl Default for Builder {
360    fn default() -> Builder {
361        Builder::new()
362    }
363}
364
365/// A packed searcher for quickly finding occurrences of multiple patterns.
366///
367/// If callers need more flexible construction, or if one wants to change the
368/// match semantics (either leftmost-first or leftmost-longest), then one can
369/// use the [`Config`] and/or [`Builder`] types for more fine grained control.
370///
371/// # Example
372///
373/// This example shows how to create a searcher from an iterator of patterns.
374/// By default, leftmost-first match semantics are used.
375///
376/// ```
377/// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
378///
379/// # fn example() -> Option<()> {
380/// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
381/// let matches: Vec<PatternID> = searcher
382///     .find_iter("foobar")
383///     .map(|mat| mat.pattern())
384///     .collect();
385/// assert_eq!(vec![PatternID::ZERO], matches);
386/// # Some(()) }
387/// # if cfg!(all(feature = "std", any(
388/// #     target_arch = "x86_64", target_arch = "aarch64",
389/// # ))) {
390/// #     example().unwrap()
391/// # } else {
392/// #     assert!(example().is_none());
393/// # }
394/// ```
395#[derive(Clone, Debug)]
396pub struct Searcher {
397    patterns: Arc<Patterns>,
398    rabinkarp: RabinKarp,
399    search_kind: SearchKind,
400    minimum_len: usize,
401}
402
403#[derive(Clone, Debug)]
404enum SearchKind {
405    Teddy(teddy::Searcher),
406    RabinKarp,
407}
408
409impl Searcher {
410    /// A convenience function for constructing a searcher from an iterator
411    /// of things that can be converted to a `&[u8]`.
412    ///
413    /// If a searcher could not be constructed (either because of an
414    /// unsupported CPU or because there are too many patterns), then `None`
415    /// is returned.
416    ///
417    /// # Example
418    ///
419    /// Basic usage:
420    ///
421    /// ```
422    /// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
423    ///
424    /// # fn example() -> Option<()> {
425    /// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
426    /// let matches: Vec<PatternID> = searcher
427    ///     .find_iter("foobar")
428    ///     .map(|mat| mat.pattern())
429    ///     .collect();
430    /// assert_eq!(vec![PatternID::ZERO], matches);
431    /// # Some(()) }
432    /// # if cfg!(all(feature = "std", any(
433    /// #     target_arch = "x86_64", target_arch = "aarch64",
434    /// # ))) {
435    /// #     example().unwrap()
436    /// # } else {
437    /// #     assert!(example().is_none());
438    /// # }
439    /// ```
440    pub fn new<I, P>(patterns: I) -> Option<Searcher>
441    where
442        I: IntoIterator<Item = P>,
443        P: AsRef<[u8]>,
444    {
445        Builder::new().extend(patterns).build()
446    }
447
448    /// A convenience function for calling `Config::new()`.
449    ///
450    /// This is useful for avoiding an additional import.
451    pub fn config() -> Config {
452        Config::new()
453    }
454
455    /// A convenience function for calling `Builder::new()`.
456    ///
457    /// This is useful for avoiding an additional import.
458    pub fn builder() -> Builder {
459        Builder::new()
460    }
461
462    /// Return the first occurrence of any of the patterns in this searcher,
463    /// according to its match semantics, in the given haystack. The `Match`
464    /// returned will include the identifier of the pattern that matched, which
465    /// corresponds to the index of the pattern (starting from `0`) in which it
466    /// was added.
467    ///
468    /// # Example
469    ///
470    /// Basic usage:
471    ///
472    /// ```
473    /// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
474    ///
475    /// # fn example() -> Option<()> {
476    /// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
477    /// let mat = searcher.find("foobar")?;
478    /// assert_eq!(PatternID::ZERO, mat.pattern());
479    /// assert_eq!(0, mat.start());
480    /// assert_eq!(6, mat.end());
481    /// # Some(()) }
482    /// # if cfg!(all(feature = "std", any(
483    /// #     target_arch = "x86_64", target_arch = "aarch64",
484    /// # ))) {
485    /// #     example().unwrap()
486    /// # } else {
487    /// #     assert!(example().is_none());
488    /// # }
489    /// ```
490    #[inline]
491    pub fn find<B: AsRef<[u8]>>(&self, haystack: B) -> Option<Match> {
492        let haystack = haystack.as_ref();
493        self.find_in(haystack, Span::from(0..haystack.len()))
494    }
495
496    /// Return the first occurrence of any of the patterns in this searcher,
497    /// according to its match semantics, in the given haystack starting from
498    /// the given position.
499    ///
500    /// The `Match` returned will include the identifier of the pattern that
501    /// matched, which corresponds to the index of the pattern (starting from
502    /// `0`) in which it was added. The offsets in the `Match` will be relative
503    /// to the start of `haystack` (and not `at`).
504    ///
505    /// # Example
506    ///
507    /// Basic usage:
508    ///
509    /// ```
510    /// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID, Span};
511    ///
512    /// # fn example() -> Option<()> {
513    /// let haystack = "foofoobar";
514    /// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
515    /// let mat = searcher.find_in(haystack, Span::from(3..haystack.len()))?;
516    /// assert_eq!(PatternID::ZERO, mat.pattern());
517    /// assert_eq!(3, mat.start());
518    /// assert_eq!(9, mat.end());
519    /// # Some(()) }
520    /// # if cfg!(all(feature = "std", any(
521    /// #     target_arch = "x86_64", target_arch = "aarch64",
522    /// # ))) {
523    /// #     example().unwrap()
524    /// # } else {
525    /// #     assert!(example().is_none());
526    /// # }
527    /// ```
528    #[inline]
529    pub fn find_in<B: AsRef<[u8]>>(
530        &self,
531        haystack: B,
532        span: Span,
533    ) -> Option<Match> {
534        let haystack = haystack.as_ref();
535        match self.search_kind {
536            SearchKind::Teddy(ref teddy) => {
537                if haystack[span].len() < teddy.minimum_len() {
538                    return self.find_in_slow(haystack, span);
539                }
540                teddy.find(&haystack[..span.end], span.start)
541            }
542            SearchKind::RabinKarp => {
543                self.rabinkarp.find_at(&haystack[..span.end], span.start)
544            }
545        }
546    }
547
548    /// Return an iterator of non-overlapping occurrences of the patterns in
549    /// this searcher, according to its match semantics, in the given haystack.
550    ///
551    /// # Example
552    ///
553    /// Basic usage:
554    ///
555    /// ```
556    /// use aho_corasick::{packed::{MatchKind, Searcher}, PatternID};
557    ///
558    /// # fn example() -> Option<()> {
559    /// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
560    /// let matches: Vec<PatternID> = searcher
561    ///     .find_iter("foobar fooba foofoo")
562    ///     .map(|mat| mat.pattern())
563    ///     .collect();
564    /// assert_eq!(vec![
565    ///     PatternID::must(0),
566    ///     PatternID::must(1),
567    ///     PatternID::must(1),
568    ///     PatternID::must(1),
569    /// ], matches);
570    /// # Some(()) }
571    /// # if cfg!(all(feature = "std", any(
572    /// #     target_arch = "x86_64", target_arch = "aarch64",
573    /// # ))) {
574    /// #     example().unwrap()
575    /// # } else {
576    /// #     assert!(example().is_none());
577    /// # }
578    /// ```
579    #[inline]
580    pub fn find_iter<'a, 'b, B: ?Sized + AsRef<[u8]>>(
581        &'a self,
582        haystack: &'b B,
583    ) -> FindIter<'a, 'b> {
584        let haystack = haystack.as_ref();
585        let span = Span::from(0..haystack.len());
586        FindIter { searcher: self, haystack, span }
587    }
588
589    /// Returns the match kind used by this packed searcher.
590    ///
591    /// # Examples
592    ///
593    /// Basic usage:
594    ///
595    /// ```
596    /// use aho_corasick::packed::{MatchKind, Searcher};
597    ///
598    /// # fn example() -> Option<()> {
599    /// let searcher = Searcher::new(["foobar", "foo"].iter().cloned())?;
600    /// // leftmost-first is the default.
601    /// assert_eq!(&MatchKind::LeftmostFirst, searcher.match_kind());
602    /// # Some(()) }
603    /// # if cfg!(all(feature = "std", any(
604    /// #     target_arch = "x86_64", target_arch = "aarch64",
605    /// # ))) {
606    /// #     example().unwrap()
607    /// # } else {
608    /// #     assert!(example().is_none());
609    /// # }
610    /// ```
611    #[inline]
612    pub fn match_kind(&self) -> &MatchKind {
613        self.patterns.match_kind()
614    }
615
616    /// Returns the minimum length of a haystack that is required in order for
617    /// packed searching to be effective.
618    ///
619    /// In some cases, the underlying packed searcher may not be able to search
620    /// very short haystacks. When that occurs, the implementation will defer
621    /// to a slower non-packed searcher (which is still generally faster than
622    /// Aho-Corasick for a small number of patterns). However, callers may
623    /// want to avoid ever using the slower variant, which one can do by
624    /// never passing a haystack shorter than the minimum length returned by
625    /// this method.
626    #[inline]
627    pub fn minimum_len(&self) -> usize {
628        self.minimum_len
629    }
630
631    /// Returns the approximate total amount of heap used by this searcher, in
632    /// units of bytes.
633    #[inline]
634    pub fn memory_usage(&self) -> usize {
635        self.patterns.memory_usage()
636            + self.rabinkarp.memory_usage()
637            + self.search_kind.memory_usage()
638    }
639
640    /// Use a slow (non-packed) searcher.
641    ///
642    /// This is useful when a packed searcher could be constructed, but could
643    /// not be used to search a specific haystack. For example, if Teddy was
644    /// built but the haystack is smaller than ~34 bytes, then Teddy might not
645    /// be able to run.
646    fn find_in_slow(&self, haystack: &[u8], span: Span) -> Option<Match> {
647        self.rabinkarp.find_at(&haystack[..span.end], span.start)
648    }
649}
650
651impl SearchKind {
652    fn memory_usage(&self) -> usize {
653        match *self {
654            SearchKind::Teddy(ref ted) => ted.memory_usage(),
655            SearchKind::RabinKarp => 0,
656        }
657    }
658}
659
660/// An iterator over non-overlapping matches from a packed searcher.
661///
662/// The lifetime `'s` refers to the lifetime of the underlying [`Searcher`],
663/// while the lifetime `'h` refers to the lifetime of the haystack being
664/// searched.
665#[derive(Debug)]
666pub struct FindIter<'s, 'h> {
667    searcher: &'s Searcher,
668    haystack: &'h [u8],
669    span: Span,
670}
671
672impl<'s, 'h> Iterator for FindIter<'s, 'h> {
673    type Item = Match;
674
675    fn next(&mut self) -> Option<Match> {
676        if self.span.start > self.span.end {
677            return None;
678        }
679        match self.searcher.find_in(&self.haystack, self.span) {
680            None => None,
681            Some(m) => {
682                self.span.start = m.end();
683                Some(m)
684            }
685        }
686    }
687}
aho_corasick/packed/api.rs

aho_corasick/packed/
api.rs
