regex_automata/util/prefilter/
mod.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
/*!
Defines a prefilter for accelerating regex searches.

A prefilter can be created by building a [`Prefilter`] value.

A prefilter represents one of the most important optimizations available for
accelerating regex searches. The idea of a prefilter is to very quickly find
candidate locations in a haystack where a regex _could_ match. Once a candidate
is found, it is then intended for the regex engine to run at that position to
determine whether the candidate is a match or a false positive.

In the aforementioned description of the prefilter optimization also lay its
demise. Namely, if a prefilter has a high false positive rate and it produces
lots of candidates, then a prefilter can overall make a regex search slower.
It can run more slowly because more time is spent ping-ponging between the
prefilter search and the regex engine attempting to confirm each candidate as
a match. This ping-ponging has overhead that adds up, and is exacerbated by
a high false positive rate.

Nevertheless, the optimization is still generally worth performing in most
cases. Particularly given just how much throughput can be improved. (It is not
uncommon for prefilter optimizations to improve throughput by one or two orders
of magnitude.)

Typically a prefilter is used to find occurrences of literal prefixes from a
regex pattern, but this isn't required. A prefilter can be used to look for
suffixes or even inner literals.

Note that as of now, prefilters throw away information about which pattern
each literal comes from. In other words, when a prefilter finds a match,
there's no way to know which pattern (or patterns) it came from. Therefore,
in order to confirm a match, you'll have to check all of the patterns by
running the full regex engine.
*/

mod aho_corasick;
mod byteset;
mod memchr;
mod memmem;
mod teddy;

use core::{
    borrow::Borrow,
    fmt::Debug,
    panic::{RefUnwindSafe, UnwindSafe},
};

#[cfg(feature = "alloc")]
use alloc::sync::Arc;

#[cfg(feature = "syntax")]
use regex_syntax::hir::{literal, Hir};

use crate::util::search::{MatchKind, Span};

pub(crate) use crate::util::prefilter::{
    aho_corasick::AhoCorasick,
    byteset::ByteSet,
    memchr::{Memchr, Memchr2, Memchr3},
    memmem::Memmem,
    teddy::Teddy,
};

/// A prefilter for accelerating regex searches.
///
/// If you already have your literals that you want to search with,
/// then the vanilla [`Prefilter::new`] constructor is for you. But
/// if you have an [`Hir`] value from the `regex-syntax` crate, then
/// [`Prefilter::from_hir_prefix`] might be more convenient. Namely, it uses
/// the [`regex-syntax::hir::literal`](regex_syntax::hir::literal) module to
/// extract literal prefixes for you, optimize them and then select and build a
/// prefilter matcher.
///
/// A prefilter must have **zero false negatives**. However, by its very
/// nature, it may produce false positives. That is, a prefilter will never
/// skip over a position in the haystack that corresponds to a match of the
/// original regex pattern, but it *may* produce a match for a position
/// in the haystack that does *not* correspond to a match of the original
/// regex pattern. If you use either the [`Prefilter::from_hir_prefix`] or
/// [`Prefilter::from_hirs_prefix`] constructors, then this guarantee is
/// upheld for you automatically. This guarantee is not preserved if you use
/// [`Prefilter::new`] though, since it is up to the caller to provide correct
/// literal strings with respect to the original regex pattern.
///
/// # Cloning
///
/// It is an API guarantee that cloning a prefilter is cheap. That is, cloning
/// it will not duplicate whatever heap memory is used to represent the
/// underlying matcher.
///
/// # Example
///
/// This example shows how to attach a `Prefilter` to the
/// [`PikeVM`](crate::nfa::thompson::pikevm::PikeVM) in order to accelerate
/// searches.
///
/// ```
/// use regex_automata::{
///     nfa::thompson::pikevm::PikeVM,
///     util::prefilter::Prefilter,
///     Match, MatchKind,
/// };
///
/// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["Bruce "])
///     .expect("a prefilter");
/// let re = PikeVM::builder()
///     .configure(PikeVM::config().prefilter(Some(pre)))
///     .build(r"Bruce \w+")?;
/// let mut cache = re.create_cache();
/// assert_eq!(
///     Some(Match::must(0, 6..23)),
///     re.find(&mut cache, "Hello Bruce Springsteen!"),
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// But note that if you get your prefilter incorrect, it could lead to an
/// incorrect result!
///
/// ```
/// use regex_automata::{
///     nfa::thompson::pikevm::PikeVM,
///     util::prefilter::Prefilter,
///     Match, MatchKind,
/// };
///
/// // This prefilter is wrong!
/// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["Patti "])
///     .expect("a prefilter");
/// let re = PikeVM::builder()
///     .configure(PikeVM::config().prefilter(Some(pre)))
///     .build(r"Bruce \w+")?;
/// let mut cache = re.create_cache();
/// // We find no match even though the regex does match.
/// assert_eq!(
///     None,
///     re.find(&mut cache, "Hello Bruce Springsteen!"),
/// );
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
#[derive(Clone, Debug)]
pub struct Prefilter {
    #[cfg(not(feature = "alloc"))]
    _unused: (),
    #[cfg(feature = "alloc")]
    pre: Arc<dyn PrefilterI>,
    #[cfg(feature = "alloc")]
    is_fast: bool,
    #[cfg(feature = "alloc")]
    max_needle_len: usize,
}

impl Prefilter {
    /// Create a new prefilter from a sequence of needles and a corresponding
    /// match semantics.
    ///
    /// This may return `None` for a variety of reasons, for example, if
    /// a suitable prefilter could not be constructed. That might occur
    /// if they are unavailable (e.g., the `perf-literal-substring` and
    /// `perf-literal-multisubstring` features aren't enabled), or it might
    /// occur because of heuristics or other artifacts of how the prefilter
    /// works.
    ///
    /// Note that if you have an [`Hir`] expression, it may be more convenient
    /// to use [`Prefilter::from_hir_prefix`]. It will automatically handle the
    /// task of extracting prefix literals for you.
    ///
    /// # Example
    ///
    /// This example shows how match semantics can impact the matching
    /// algorithm used by the prefilter. For this reason, it is important to
    /// ensure that the match semantics given here are consistent with the
    /// match semantics intended for the regular expression that the literals
    /// were extracted from.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hay = "Hello samwise";
    ///
    /// // With leftmost-first, we find 'samwise' here because it comes
    /// // before 'sam' in the sequence we give it..
    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["samwise", "sam"])
    ///     .expect("a prefilter");
    /// assert_eq!(
    ///     Some(Span::from(6..13)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    /// // Still with leftmost-first but with the literals reverse, now 'sam'
    /// // will match instead!
    /// let pre = Prefilter::new(MatchKind::LeftmostFirst, &["sam", "samwise"])
    ///     .expect("a prefilter");
    /// assert_eq!(
    ///     Some(Span::from(6..9)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn new<B: AsRef<[u8]>>(
        kind: MatchKind,
        needles: &[B],
    ) -> Option<Prefilter> {
        Choice::new(kind, needles).and_then(|choice| {
            let max_needle_len =
                needles.iter().map(|b| b.as_ref().len()).max().unwrap_or(0);
            Prefilter::from_choice(choice, max_needle_len)
        })
    }

    /// This turns a prefilter selection into a `Prefilter`. That is, in turns
    /// the enum given into a trait object.
    fn from_choice(
        choice: Choice,
        max_needle_len: usize,
    ) -> Option<Prefilter> {
        #[cfg(not(feature = "alloc"))]
        {
            None
        }
        #[cfg(feature = "alloc")]
        {
            let pre: Arc<dyn PrefilterI> = match choice {
                Choice::Memchr(p) => Arc::new(p),
                Choice::Memchr2(p) => Arc::new(p),
                Choice::Memchr3(p) => Arc::new(p),
                Choice::Memmem(p) => Arc::new(p),
                Choice::Teddy(p) => Arc::new(p),
                Choice::ByteSet(p) => Arc::new(p),
                Choice::AhoCorasick(p) => Arc::new(p),
            };
            let is_fast = pre.is_fast();
            Some(Prefilter { pre, is_fast, max_needle_len })
        }
    }

    /// This attempts to extract prefixes from the given `Hir` expression for
    /// the given match semantics, and if possible, builds a prefilter for
    /// them.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from an [`Hir`]
    /// expression, and use to find an occurrence of a prefix from the regex
    /// pattern.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hir = syntax::parse(r"(Bruce|Patti) \w+")?;
    /// let pre = Prefilter::from_hir_prefix(MatchKind::LeftmostFirst, &hir)
    ///     .expect("a prefilter");
    /// let hay = "Hello Patti Scialfa!";
    /// assert_eq!(
    ///     Some(Span::from(6..12)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "syntax")]
    pub fn from_hir_prefix(kind: MatchKind, hir: &Hir) -> Option<Prefilter> {
        Prefilter::from_hirs_prefix(kind, &[hir])
    }

    /// This attempts to extract prefixes from the given `Hir` expressions for
    /// the given match semantics, and if possible, builds a prefilter for
    /// them.
    ///
    /// Note that as of now, prefilters throw away information about which
    /// pattern each literal comes from. In other words, when a prefilter finds
    /// a match, there's no way to know which pattern (or patterns) it came
    /// from. Therefore, in order to confirm a match, you'll have to check all
    /// of the patterns by running the full regex engine.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from multiple
    /// `Hir` expressions expression, and use it to find an occurrence of a
    /// prefix from the regex patterns.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hirs = syntax::parse_many(&[
    ///     r"(Bruce|Patti) \w+",
    ///     r"Mrs?\. Doubtfire",
    /// ])?;
    /// let pre = Prefilter::from_hirs_prefix(MatchKind::LeftmostFirst, &hirs)
    ///     .expect("a prefilter");
    /// let hay = "Hello Mrs. Doubtfire";
    /// assert_eq!(
    ///     Some(Span::from(6..20)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[cfg(feature = "syntax")]
    pub fn from_hirs_prefix<H: Borrow<Hir>>(
        kind: MatchKind,
        hirs: &[H],
    ) -> Option<Prefilter> {
        prefixes(kind, hirs)
            .literals()
            .and_then(|lits| Prefilter::new(kind, lits))
    }

    /// Run this prefilter on `haystack[span.start..end]` and return a matching
    /// span if one exists.
    ///
    /// The span returned is guaranteed to have a start position greater than
    /// or equal to the one given, and an end position less than or equal to
    /// the one given.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from an [`Hir`]
    /// expression, and use it to find an occurrence of a prefix from the regex
    /// pattern.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hir = syntax::parse(r"Bruce \w+")?;
    /// let pre = Prefilter::from_hir_prefix(MatchKind::LeftmostFirst, &hir)
    ///     .expect("a prefilter");
    /// let hay = "Hello Bruce Springsteen!";
    /// assert_eq!(
    ///     Some(Span::from(6..12)),
    ///     pre.find(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn find(&self, haystack: &[u8], span: Span) -> Option<Span> {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.pre.find(haystack, span)
        }
    }

    /// Returns the span of a prefix of `haystack[span.start..span.end]` if
    /// the prefilter matches.
    ///
    /// The span returned is guaranteed to have a start position equivalent to
    /// the one given, and an end position less than or equal to the one given.
    ///
    /// # Example
    ///
    /// This example shows how to build a prefilter directly from an [`Hir`]
    /// expression, and use it to find an occurrence of a prefix from the regex
    /// pattern that begins at the start of a haystack only.
    ///
    /// ```
    /// use regex_automata::{
    ///     util::{prefilter::Prefilter, syntax},
    ///     MatchKind, Span,
    /// };
    ///
    /// let hir = syntax::parse(r"Bruce \w+")?;
    /// let pre = Prefilter::from_hir_prefix(MatchKind::LeftmostFirst, &hir)
    ///     .expect("a prefilter");
    /// let hay = "Hello Bruce Springsteen!";
    /// // Nothing is found here because 'Bruce' does
    /// // not occur at the beginning of our search.
    /// assert_eq!(
    ///     None,
    ///     pre.prefix(hay.as_bytes(), Span::from(0..hay.len())),
    /// );
    /// // But if we change where we start the search
    /// // to begin where 'Bruce ' begins, then a
    /// // match will be found.
    /// assert_eq!(
    ///     Some(Span::from(6..12)),
    ///     pre.prefix(hay.as_bytes(), Span::from(6..hay.len())),
    /// );
    ///
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    #[inline]
    pub fn prefix(&self, haystack: &[u8], span: Span) -> Option<Span> {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.pre.prefix(haystack, span)
        }
    }

    /// Returns the heap memory, in bytes, used by the underlying prefilter.
    #[inline]
    pub fn memory_usage(&self) -> usize {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.pre.memory_usage()
        }
    }

    /// Return the length of the longest needle
    /// in this Prefilter
    #[inline]
    pub fn max_needle_len(&self) -> usize {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.max_needle_len
        }
    }

    /// Implementations might return true here if they believe themselves to
    /// be "fast." The concept of "fast" is deliberately left vague, but in
    /// practice this usually corresponds to whether it's believed that SIMD
    /// will be used.
    ///
    /// Why do we care about this? Well, some prefilter tricks tend to come
    /// with their own bits of overhead, and so might only make sense if we
    /// know that a scan will be *much* faster than the regex engine itself.
    /// Otherwise, the trick may not be worth doing. Whether something is
    /// "much" faster than the regex engine generally boils down to whether
    /// SIMD is used. (But not always. Even a SIMD matcher with a high false
    /// positive rate can become quite slow.)
    ///
    /// Even if this returns true, it is still possible for the prefilter to
    /// be "slow." Remember, prefilters are just heuristics. We can't really
    /// *know* a prefilter will be fast without actually trying the prefilter.
    /// (Which of course we cannot afford to do.)
    #[inline]
    pub fn is_fast(&self) -> bool {
        #[cfg(not(feature = "alloc"))]
        {
            unreachable!()
        }
        #[cfg(feature = "alloc")]
        {
            self.is_fast
        }
    }
}

/// A trait for abstracting over prefilters. Basically, a prefilter is
/// something that do an unanchored *and* an anchored search in a haystack
/// within a given span.
///
/// This exists pretty much only so that we can use prefilters as a trait
/// object (which is what `Prefilter` is). If we ever move off of trait objects
/// and to an enum, then it's likely this trait could be removed.
pub(crate) trait PrefilterI:
    Debug + Send + Sync + RefUnwindSafe + UnwindSafe + 'static
{
    /// Run this prefilter on `haystack[span.start..end]` and return a matching
    /// span if one exists.
    ///
    /// The span returned is guaranteed to have a start position greater than
    /// or equal to the one given, and an end position less than or equal to
    /// the one given.
    fn find(&self, haystack: &[u8], span: Span) -> Option<Span>;

    /// Returns the span of a prefix of `haystack[span.start..span.end]` if
    /// the prefilter matches.
    ///
    /// The span returned is guaranteed to have a start position equivalent to
    /// the one given, and an end position less than or equal to the one given.
    fn prefix(&self, haystack: &[u8], span: Span) -> Option<Span>;

    /// Returns the heap memory, in bytes, used by the underlying prefilter.
    fn memory_usage(&self) -> usize;

    /// Implementations might return true here if they believe themselves to
    /// be "fast." See [`Prefilter::is_fast`] for more details.
    fn is_fast(&self) -> bool;
}

#[cfg(feature = "alloc")]
impl<P: PrefilterI + ?Sized> PrefilterI for Arc<P> {
    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn find(&self, haystack: &[u8], span: Span) -> Option<Span> {
        (&**self).find(haystack, span)
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn prefix(&self, haystack: &[u8], span: Span) -> Option<Span> {
        (&**self).prefix(haystack, span)
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn memory_usage(&self) -> usize {
        (&**self).memory_usage()
    }

    #[cfg_attr(feature = "perf-inline", inline(always))]
    fn is_fast(&self) -> bool {
        (&**self).is_fast()
    }
}

/// A type that encapsulates the selection of a prefilter algorithm from a
/// sequence of needles.
///
/// The existence of this type is a little tricky, because we don't (currently)
/// use it for performing a search. Instead, we really only consume it by
/// converting the underlying prefilter into a trait object, whether that be
/// `dyn PrefilterI` or `dyn Strategy` (for the meta regex engine). In order
/// to avoid re-copying the prefilter selection logic, we isolate it here, and
/// then force anything downstream that wants to convert it to a trait object
/// to do trivial case analysis on it.
///
/// One wonders whether we *should* use an enum instead of a trait object.
/// At time of writing, I chose trait objects based on instinct because 1) I
/// knew I wasn't going to inline anything and 2) there would potentially be
/// many different choices. However, as of time of writing, I haven't actually
/// compared the trait object approach to the enum approach. That probably
/// should be litigated, but I ran out of steam.
///
/// Note that if the `alloc` feature is disabled, then values of this type
/// are (and should) never be constructed. Also, in practice, for any of the
/// prefilters to be selected, you'll need at least one of the `perf-literal-*`
/// features enabled.
#[derive(Clone, Debug)]
pub(crate) enum Choice {
    Memchr(Memchr),
    Memchr2(Memchr2),
    Memchr3(Memchr3),
    Memmem(Memmem),
    Teddy(Teddy),
    ByteSet(ByteSet),
    AhoCorasick(AhoCorasick),
}

impl Choice {
    /// Select what is believed to be the best prefilter algorithm for the
    /// match semantics and sequence of needles given.
    ///
    /// This selection algorithm uses the needles as given without any
    /// modification. For example, if `[bar]` is given, then this doesn't
    /// try to select `memchr` for `b`. Instead, it would select `memmem`
    /// for `bar`. If callers would want `memchr` selected for `[bar]`, then
    /// callers should massages the literals themselves. That is, callers are
    /// responsible for heuristics surrounding which sequence of literals is
    /// best.
    ///
    /// What this selection algorithm does is attempt to use the fastest
    /// prefilter that works for the literals given. So if `[a, b]`, is given,
    /// then `memchr2` is selected.
    ///
    /// Of course, which prefilter is selected is also subject to what
    /// is available. For example, if `alloc` isn't enabled, then
    /// that limits which prefilters can be selected. Similarly, if
    /// `perf-literal-substring` isn't enabled, then nothing from the `memchr`
    /// crate can be returned.
    pub(crate) fn new<B: AsRef<[u8]>>(
        kind: MatchKind,
        needles: &[B],
    ) -> Option<Choice> {
        // An empty set means the regex matches nothing, so no sense in
        // building a prefilter.
        if needles.len() == 0 {
            debug!("prefilter building failed: found empty set of literals");
            return None;
        }
        // If the regex can match the empty string, then the prefilter
        // will by definition match at every position. This is obviously
        // completely ineffective.
        if needles.iter().any(|n| n.as_ref().is_empty()) {
            debug!("prefilter building failed: literals match empty string");
            return None;
        }
        // BREADCRUMBS: Perhaps the literal optimizer should special case
        // sequences of length two or three if the leading bytes of each are
        // "rare"? Or perhaps, if there are two or three total possible leading
        // bytes, regardless of the number of literals, and all are rare...
        // Then well, perhaps we should use memchr2 or memchr3 in those cases?
        if let Some(pre) = Memchr::new(kind, needles) {
            debug!("prefilter built: memchr");
            return Some(Choice::Memchr(pre));
        }
        if let Some(pre) = Memchr2::new(kind, needles) {
            debug!("prefilter built: memchr2");
            return Some(Choice::Memchr2(pre));
        }
        if let Some(pre) = Memchr3::new(kind, needles) {
            debug!("prefilter built: memchr3");
            return Some(Choice::Memchr3(pre));
        }
        if let Some(pre) = Memmem::new(kind, needles) {
            debug!("prefilter built: memmem");
            return Some(Choice::Memmem(pre));
        }
        if let Some(pre) = Teddy::new(kind, needles) {
            debug!("prefilter built: teddy");
            return Some(Choice::Teddy(pre));
        }
        if let Some(pre) = ByteSet::new(kind, needles) {
            debug!("prefilter built: byteset");
            return Some(Choice::ByteSet(pre));
        }
        if let Some(pre) = AhoCorasick::new(kind, needles) {
            debug!("prefilter built: aho-corasick");
            return Some(Choice::AhoCorasick(pre));
        }
        debug!("prefilter building failed: no strategy could be found");
        None
    }
}

/// Extracts all of the prefix literals from the given HIR expressions into a
/// single `Seq`. The literals in the sequence are ordered with respect to the
/// order of the given HIR expressions and consistent with the match semantics
/// given.
///
/// The sequence returned is "optimized." That is, they may be shrunk or even
/// truncated according to heuristics with the intent of making them more
/// useful as a prefilter. (Which translates to both using faster algorithms
/// and minimizing the false positive rate.)
///
/// Note that this erases any connection between the literals and which pattern
/// (or patterns) they came from.
///
/// The match kind given must correspond to the match semantics of the regex
/// that is represented by the HIRs given. The match semantics may change the
/// literal sequence returned.
#[cfg(feature = "syntax")]
pub(crate) fn prefixes<H>(kind: MatchKind, hirs: &[H]) -> literal::Seq
where
    H: core::borrow::Borrow<Hir>,
{
    let mut extractor = literal::Extractor::new();
    extractor.kind(literal::ExtractKind::Prefix);

    let mut prefixes = literal::Seq::empty();
    for hir in hirs {
        prefixes.union(&mut extractor.extract(hir.borrow()));
    }
    debug!(
        "prefixes (len={:?}, exact={:?}) extracted before optimization: {:?}",
        prefixes.len(),
        prefixes.is_exact(),
        prefixes
    );
    match kind {
        MatchKind::All => {
            prefixes.sort();
            prefixes.dedup();
        }
        MatchKind::LeftmostFirst => {
            prefixes.optimize_for_prefix_by_preference();
        }
    }
    debug!(
        "prefixes (len={:?}, exact={:?}) extracted after optimization: {:?}",
        prefixes.len(),
        prefixes.is_exact(),
        prefixes
    );
    prefixes
}

/// Like `prefixes`, but for all suffixes of all matches for the given HIRs.
#[cfg(feature = "syntax")]
pub(crate) fn suffixes<H>(kind: MatchKind, hirs: &[H]) -> literal::Seq
where
    H: core::borrow::Borrow<Hir>,
{
    let mut extractor = literal::Extractor::new();
    extractor.kind(literal::ExtractKind::Suffix);

    let mut suffixes = literal::Seq::empty();
    for hir in hirs {
        suffixes.union(&mut extractor.extract(hir.borrow()));
    }
    debug!(
        "suffixes (len={:?}, exact={:?}) extracted before optimization: {:?}",
        suffixes.len(),
        suffixes.is_exact(),
        suffixes
    );
    match kind {
        MatchKind::All => {
            suffixes.sort();
            suffixes.dedup();
        }
        MatchKind::LeftmostFirst => {
            suffixes.optimize_for_suffix_by_preference();
        }
    }
    debug!(
        "suffixes (len={:?}, exact={:?}) extracted after optimization: {:?}",
        suffixes.len(),
        suffixes.is_exact(),
        suffixes
    );
    suffixes
}