core/str/
pattern.rs

1//! The string Pattern API.
2//!
3//! The Pattern API provides a generic mechanism for using different pattern
4//! types when searching through a string.
5//!
6//! For more details, see the traits [`Pattern`], [`Searcher`],
7//! [`ReverseSearcher`], and [`DoubleEndedSearcher`].
8//!
9//! Although this API is unstable, it is exposed via stable APIs on the
10//! [`str`] type.
11//!
12//! # Examples
13//!
14//! [`Pattern`] is [implemented][pattern-impls] in the stable API for
15//! [`&str`][`str`], [`char`], slices of [`char`], and functions and closures
16//! implementing `FnMut(char) -> bool`.
17//!
18//! ```
19//! let s = "Can you find a needle in a haystack?";
20//!
21//! // &str pattern
22//! assert_eq!(s.find("you"), Some(4));
23//! // char pattern
24//! assert_eq!(s.find('n'), Some(2));
25//! // array of chars pattern
26//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u']), Some(1));
27//! // slice of chars pattern
28//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u'][..]), Some(1));
29//! // closure pattern
30//! assert_eq!(s.find(|c: char| c.is_ascii_punctuation()), Some(35));
31//! ```
32//!
33//! [pattern-impls]: Pattern#implementors
34
35#![unstable(
36    feature = "pattern",
37    reason = "API not fully fleshed out and ready to be stabilized",
38    issue = "27721"
39)]
40
41use crate::cmp::Ordering;
42use crate::convert::TryInto as _;
43use crate::slice::memchr;
44use crate::{cmp, fmt};
45
46// Pattern
47
48/// A string pattern.
49///
50/// A `Pattern` expresses that the implementing type
51/// can be used as a string pattern for searching in a [`&str`][str].
52///
53/// For example, both `'a'` and `"aa"` are patterns that
54/// would match at index `1` in the string `"baaaab"`.
55///
56/// The trait itself acts as a builder for an associated
57/// [`Searcher`] type, which does the actual work of finding
58/// occurrences of the pattern in a string.
59///
60/// Depending on the type of the pattern, the behavior of methods like
61/// [`str::find`] and [`str::contains`] can change. The table below describes
62/// some of those behaviors.
63///
64/// | Pattern type             | Match condition                           |
65/// |--------------------------|-------------------------------------------|
66/// | `&str`                   | is substring                              |
67/// | `char`                   | is contained in string                    |
68/// | `&[char]`                | any char in slice is contained in string  |
69/// | `F: FnMut(char) -> bool` | `F` returns `true` for a char in string   |
70/// | `&&str`                  | is substring                              |
71/// | `&String`                | is substring                              |
72///
73/// # Examples
74///
75/// ```
76/// // &str
77/// assert_eq!("abaaa".find("ba"), Some(1));
78/// assert_eq!("abaaa".find("bac"), None);
79///
80/// // char
81/// assert_eq!("abaaa".find('a'), Some(0));
82/// assert_eq!("abaaa".find('b'), Some(1));
83/// assert_eq!("abaaa".find('c'), None);
84///
85/// // &[char; N]
86/// assert_eq!("ab".find(&['b', 'a']), Some(0));
87/// assert_eq!("abaaa".find(&['a', 'z']), Some(0));
88/// assert_eq!("abaaa".find(&['c', 'd']), None);
89///
90/// // &[char]
91/// assert_eq!("ab".find(&['b', 'a'][..]), Some(0));
92/// assert_eq!("abaaa".find(&['a', 'z'][..]), Some(0));
93/// assert_eq!("abaaa".find(&['c', 'd'][..]), None);
94///
95/// // FnMut(char) -> bool
96/// assert_eq!("abcdef_z".find(|ch| ch > 'd' && ch < 'y'), Some(4));
97/// assert_eq!("abcddd_z".find(|ch| ch > 'd' && ch < 'y'), None);
98/// ```
99pub trait Pattern: Sized {
100    /// Associated searcher for this pattern
101    type Searcher<'a>: Searcher<'a>;
102
103    /// Constructs the associated searcher from
104    /// `self` and the `haystack` to search in.
105    fn into_searcher(self, haystack: &str) -> Self::Searcher<'_>;
106
107    /// Checks whether the pattern matches anywhere in the haystack
108    #[inline]
109    fn is_contained_in(self, haystack: &str) -> bool {
110        self.into_searcher(haystack).next_match().is_some()
111    }
112
113    /// Checks whether the pattern matches at the front of the haystack
114    #[inline]
115    fn is_prefix_of(self, haystack: &str) -> bool {
116        matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
117    }
118
119    /// Checks whether the pattern matches at the back of the haystack
120    #[inline]
121    fn is_suffix_of<'a>(self, haystack: &'a str) -> bool
122    where
123        Self::Searcher<'a>: ReverseSearcher<'a>,
124    {
125        matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
126    }
127
128    /// Removes the pattern from the front of haystack, if it matches.
129    #[inline]
130    fn strip_prefix_of(self, haystack: &str) -> Option<&str> {
131        if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() {
132            debug_assert_eq!(
133                start, 0,
134                "The first search step from Searcher \
135                 must include the first character"
136            );
137            // SAFETY: `Searcher` is known to return valid indices.
138            unsafe { Some(haystack.get_unchecked(len..)) }
139        } else {
140            None
141        }
142    }
143
144    /// Removes the pattern from the back of haystack, if it matches.
145    #[inline]
146    fn strip_suffix_of<'a>(self, haystack: &'a str) -> Option<&'a str>
147    where
148        Self::Searcher<'a>: ReverseSearcher<'a>,
149    {
150        if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() {
151            debug_assert_eq!(
152                end,
153                haystack.len(),
154                "The first search step from ReverseSearcher \
155                 must include the last character"
156            );
157            // SAFETY: `Searcher` is known to return valid indices.
158            unsafe { Some(haystack.get_unchecked(..start)) }
159        } else {
160            None
161        }
162    }
163
164    /// Returns the pattern as utf-8 bytes if possible.
165    fn as_utf8_pattern(&self) -> Option<Utf8Pattern<'_>> {
166        None
167    }
168}
169/// Result of calling [`Pattern::as_utf8_pattern()`].
170/// Can be used for inspecting the contents of a [`Pattern`] in cases
171/// where the underlying representation can be represented as UTF-8.
172#[derive(Copy, Clone, Eq, PartialEq, Debug)]
173pub enum Utf8Pattern<'a> {
174    /// Type returned by String and str types.
175    StringPattern(&'a [u8]),
176    /// Type returned by char types.
177    CharPattern(char),
178}
179
180// Searcher
181
182/// Result of calling [`Searcher::next()`] or [`ReverseSearcher::next_back()`].
183#[derive(Copy, Clone, Eq, PartialEq, Debug)]
184pub enum SearchStep {
185    /// Expresses that a match of the pattern has been found at
186    /// `haystack[a..b]`.
187    Match(usize, usize),
188    /// Expresses that `haystack[a..b]` has been rejected as a possible match
189    /// of the pattern.
190    ///
191    /// Note that there might be more than one `Reject` between two `Match`es,
192    /// there is no requirement for them to be combined into one.
193    Reject(usize, usize),
194    /// Expresses that every byte of the haystack has been visited, ending
195    /// the iteration.
196    Done,
197}
198
199/// A searcher for a string pattern.
200///
201/// This trait provides methods for searching for non-overlapping
202/// matches of a pattern starting from the front (left) of a string.
203///
204/// It will be implemented by associated `Searcher`
205/// types of the [`Pattern`] trait.
206///
207/// The trait is marked unsafe because the indices returned by the
208/// [`next()`][Searcher::next] methods are required to lie on valid utf8
209/// boundaries in the haystack. This enables consumers of this trait to
210/// slice the haystack without additional runtime checks.
211pub unsafe trait Searcher<'a> {
212    /// Getter for the underlying string to be searched in
213    ///
214    /// Will always return the same [`&str`][str].
215    fn haystack(&self) -> &'a str;
216
217    /// Performs the next search step starting from the front.
218    ///
219    /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches
220    ///   the pattern.
221    /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` can
222    ///   not match the pattern, even partially.
223    /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack has
224    ///   been visited.
225    ///
226    /// The stream of [`Match`][SearchStep::Match] and
227    /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
228    /// will contain index ranges that are adjacent, non-overlapping,
229    /// covering the whole haystack, and laying on utf8 boundaries.
230    ///
231    /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
232    /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
233    /// into arbitrary many adjacent fragments. Both ranges may have zero length.
234    ///
235    /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
236    /// might produce the stream
237    /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
238    fn next(&mut self) -> SearchStep;
239
240    /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next].
241    ///
242    /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
243    /// of this and [`next_reject`][Searcher::next_reject] will overlap. This will return
244    /// `(start_match, end_match)`, where start_match is the index of where
245    /// the match begins, and end_match is the index after the end of the match.
246    #[inline]
247    fn next_match(&mut self) -> Option<(usize, usize)> {
248        loop {
249            match self.next() {
250                SearchStep::Match(a, b) => return Some((a, b)),
251                SearchStep::Done => return None,
252                _ => continue,
253            }
254        }
255    }
256
257    /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next]
258    /// and [`next_match()`][Searcher::next_match].
259    ///
260    /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
261    /// of this and [`next_match`][Searcher::next_match] will overlap.
262    #[inline]
263    fn next_reject(&mut self) -> Option<(usize, usize)> {
264        loop {
265            match self.next() {
266                SearchStep::Reject(a, b) => return Some((a, b)),
267                SearchStep::Done => return None,
268                _ => continue,
269            }
270        }
271    }
272}
273
274/// A reverse searcher for a string pattern.
275///
276/// This trait provides methods for searching for non-overlapping
277/// matches of a pattern starting from the back (right) of a string.
278///
279/// It will be implemented by associated [`Searcher`]
280/// types of the [`Pattern`] trait if the pattern supports searching
281/// for it from the back.
282///
283/// The index ranges returned by this trait are not required
284/// to exactly match those of the forward search in reverse.
285///
286/// For the reason why this trait is marked unsafe, see the
287/// parent trait [`Searcher`].
288pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
289    /// Performs the next search step starting from the back.
290    ///
291    /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]`
292    ///   matches the pattern.
293    /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]`
294    ///   can not match the pattern, even partially.
295    /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack
296    ///   has been visited
297    ///
298    /// The stream of [`Match`][SearchStep::Match] and
299    /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
300    /// will contain index ranges that are adjacent, non-overlapping,
301    /// covering the whole haystack, and laying on utf8 boundaries.
302    ///
303    /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
304    /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
305    /// into arbitrary many adjacent fragments. Both ranges may have zero length.
306    ///
307    /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
308    /// might produce the stream
309    /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`.
310    fn next_back(&mut self) -> SearchStep;
311
312    /// Finds the next [`Match`][SearchStep::Match] result.
313    /// See [`next_back()`][ReverseSearcher::next_back].
314    #[inline]
315    fn next_match_back(&mut self) -> Option<(usize, usize)> {
316        loop {
317            match self.next_back() {
318                SearchStep::Match(a, b) => return Some((a, b)),
319                SearchStep::Done => return None,
320                _ => continue,
321            }
322        }
323    }
324
325    /// Finds the next [`Reject`][SearchStep::Reject] result.
326    /// See [`next_back()`][ReverseSearcher::next_back].
327    #[inline]
328    fn next_reject_back(&mut self) -> Option<(usize, usize)> {
329        loop {
330            match self.next_back() {
331                SearchStep::Reject(a, b) => return Some((a, b)),
332                SearchStep::Done => return None,
333                _ => continue,
334            }
335        }
336    }
337}
338
339/// A marker trait to express that a [`ReverseSearcher`]
340/// can be used for a [`DoubleEndedIterator`] implementation.
341///
342/// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need
343/// to follow these conditions:
344///
345/// - All results of `next()` need to be identical
346///   to the results of `next_back()` in reverse order.
347/// - `next()` and `next_back()` need to behave as
348///   the two ends of a range of values, that is they
349///   can not "walk past each other".
350///
351/// # Examples
352///
353/// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
354/// [`char`] only requires looking at one at a time, which behaves the same
355/// from both ends.
356///
357/// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
358/// the pattern `"aa"` in the haystack `"aaa"` matches as either
359/// `"[aa]a"` or `"a[aa]"`, depending on which side it is searched.
360pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
361
362/////////////////////////////////////////////////////////////////////////////
363// Impl for char
364/////////////////////////////////////////////////////////////////////////////
365
366/// Associated type for `<char as Pattern>::Searcher<'a>`.
367#[derive(Clone, Debug)]
368pub struct CharSearcher<'a> {
369    haystack: &'a str,
370    // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack`
371    // This invariant can be broken *within* next_match and next_match_back, however
372    // they must exit with fingers on valid code point boundaries.
373    /// `finger` is the current byte index of the forward search.
374    /// Imagine that it exists before the byte at its index, i.e.
375    /// `haystack[finger]` is the first byte of the slice we must inspect during
376    /// forward searching
377    finger: usize,
378    /// `finger_back` is the current byte index of the reverse search.
379    /// Imagine that it exists after the byte at its index, i.e.
380    /// haystack[finger_back - 1] is the last byte of the slice we must inspect during
381    /// forward searching (and thus the first byte to be inspected when calling next_back()).
382    finger_back: usize,
383    /// The character being searched for
384    needle: char,
385
386    // safety invariant: `utf8_size` must be less than 5
387    /// The number of bytes `needle` takes up when encoded in utf8.
388    utf8_size: u8,
389    /// A utf8 encoded copy of the `needle`
390    utf8_encoded: [u8; 4],
391}
392
393impl CharSearcher<'_> {
394    fn utf8_size(&self) -> usize {
395        self.utf8_size.into()
396    }
397}
398
399unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
400    #[inline]
401    fn haystack(&self) -> &'a str {
402        self.haystack
403    }
404    #[inline]
405    fn next(&mut self) -> SearchStep {
406        let old_finger = self.finger;
407        // SAFETY: 1-4 guarantee safety of `get_unchecked`
408        // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries
409        //    (this is invariant)
410        // 2. `self.finger >= 0` since it starts at 0 and only increases
411        // 3. `self.finger < self.finger_back` because otherwise the char `iter`
412        //    would return `SearchStep::Done`
413        // 4. `self.finger` comes before the end of the haystack because `self.finger_back`
414        //    starts at the end and only decreases
415        let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
416        let mut iter = slice.chars();
417        let old_len = iter.iter.len();
418        if let Some(ch) = iter.next() {
419            // add byte offset of current character
420            // without re-encoding as utf-8
421            self.finger += old_len - iter.iter.len();
422            if ch == self.needle {
423                SearchStep::Match(old_finger, self.finger)
424            } else {
425                SearchStep::Reject(old_finger, self.finger)
426            }
427        } else {
428            SearchStep::Done
429        }
430    }
431    #[inline]
432    fn next_match(&mut self) -> Option<(usize, usize)> {
433        loop {
434            // get the haystack after the last character found
435            let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
436            // the last byte of the utf8 encoded needle
437            // SAFETY: we have an invariant that `utf8_size < 5`
438            let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size() - 1) };
439            if let Some(index) = memchr::memchr(last_byte, bytes) {
440                // The new finger is the index of the byte we found,
441                // plus one, since we memchr'd for the last byte of the character.
442                //
443                // Note that this doesn't always give us a finger on a UTF8 boundary.
444                // If we *didn't* find our character
445                // we may have indexed to the non-last byte of a 3-byte or 4-byte character.
446                // We can't just skip to the next valid starting byte because a character like
447                // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find
448                // the second byte when searching for the third.
449                //
450                // However, this is totally okay. While we have the invariant that
451                // self.finger is on a UTF8 boundary, this invariant is not relied upon
452                // within this method (it is relied upon in CharSearcher::next()).
453                //
454                // We only exit this method when we reach the end of the string, or if we
455                // find something. When we find something the `finger` will be set
456                // to a UTF8 boundary.
457                self.finger += index + 1;
458                if self.finger >= self.utf8_size() {
459                    let found_char = self.finger - self.utf8_size();
460                    if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
461                        if slice == &self.utf8_encoded[0..self.utf8_size()] {
462                            return Some((found_char, self.finger));
463                        }
464                    }
465                }
466            } else {
467                // found nothing, exit
468                self.finger = self.finger_back;
469                return None;
470            }
471        }
472    }
473
474    // let next_reject use the default implementation from the Searcher trait
475}
476
477unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
478    #[inline]
479    fn next_back(&mut self) -> SearchStep {
480        let old_finger = self.finger_back;
481        // SAFETY: see the comment for next() above
482        let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
483        let mut iter = slice.chars();
484        let old_len = iter.iter.len();
485        if let Some(ch) = iter.next_back() {
486            // subtract byte offset of current character
487            // without re-encoding as utf-8
488            self.finger_back -= old_len - iter.iter.len();
489            if ch == self.needle {
490                SearchStep::Match(self.finger_back, old_finger)
491            } else {
492                SearchStep::Reject(self.finger_back, old_finger)
493            }
494        } else {
495            SearchStep::Done
496        }
497    }
498    #[inline]
499    fn next_match_back(&mut self) -> Option<(usize, usize)> {
500        let haystack = self.haystack.as_bytes();
501        loop {
502            // get the haystack up to but not including the last character searched
503            let bytes = haystack.get(self.finger..self.finger_back)?;
504            // the last byte of the utf8 encoded needle
505            // SAFETY: we have an invariant that `utf8_size < 5`
506            let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size() - 1) };
507            if let Some(index) = memchr::memrchr(last_byte, bytes) {
508                // we searched a slice that was offset by self.finger,
509                // add self.finger to recoup the original index
510                let index = self.finger + index;
511                // memrchr will return the index of the byte we wish to
512                // find. In case of an ASCII character, this is indeed
513                // were we wish our new finger to be ("after" the found
514                // char in the paradigm of reverse iteration). For
515                // multibyte chars we need to skip down by the number of more
516                // bytes they have than ASCII
517                let shift = self.utf8_size() - 1;
518                if index >= shift {
519                    let found_char = index - shift;
520                    if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size())) {
521                        if slice == &self.utf8_encoded[0..self.utf8_size()] {
522                            // move finger to before the character found (i.e., at its start index)
523                            self.finger_back = found_char;
524                            return Some((self.finger_back, self.finger_back + self.utf8_size()));
525                        }
526                    }
527                }
528                // We can't use finger_back = index - size + 1 here. If we found the last char
529                // of a different-sized character (or the middle byte of a different character)
530                // we need to bump the finger_back down to `index`. This similarly makes
531                // `finger_back` have the potential to no longer be on a boundary,
532                // but this is OK since we only exit this function on a boundary
533                // or when the haystack has been searched completely.
534                //
535                // Unlike next_match this does not
536                // have the problem of repeated bytes in utf-8 because
537                // we're searching for the last byte, and we can only have
538                // found the last byte when searching in reverse.
539                self.finger_back = index;
540            } else {
541                self.finger_back = self.finger;
542                // found nothing, exit
543                return None;
544            }
545        }
546    }
547
548    // let next_reject_back use the default implementation from the Searcher trait
549}
550
551impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
552
553/// Searches for chars that are equal to a given [`char`].
554///
555/// # Examples
556///
557/// ```
558/// assert_eq!("Hello world".find('o'), Some(4));
559/// ```
560impl Pattern for char {
561    type Searcher<'a> = CharSearcher<'a>;
562
563    #[inline]
564    fn into_searcher(self, haystack: &str) -> Self::Searcher<'_> {
565        let mut utf8_encoded = [0; 4];
566        let utf8_size = self
567            .encode_utf8(&mut utf8_encoded)
568            .len()
569            .try_into()
570            .expect("char len should be less than 255");
571
572        CharSearcher {
573            haystack,
574            finger: 0,
575            finger_back: haystack.len(),
576            needle: self,
577            utf8_size,
578            utf8_encoded,
579        }
580    }
581
582    #[inline]
583    fn is_contained_in(self, haystack: &str) -> bool {
584        if (self as u32) < 128 {
585            haystack.as_bytes().contains(&(self as u8))
586        } else {
587            let mut buffer = [0u8; 4];
588            self.encode_utf8(&mut buffer).is_contained_in(haystack)
589        }
590    }
591
592    #[inline]
593    fn is_prefix_of(self, haystack: &str) -> bool {
594        self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
595    }
596
597    #[inline]
598    fn strip_prefix_of(self, haystack: &str) -> Option<&str> {
599        self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack)
600    }
601
602    #[inline]
603    fn is_suffix_of<'a>(self, haystack: &'a str) -> bool
604    where
605        Self::Searcher<'a>: ReverseSearcher<'a>,
606    {
607        self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
608    }
609
610    #[inline]
611    fn strip_suffix_of<'a>(self, haystack: &'a str) -> Option<&'a str>
612    where
613        Self::Searcher<'a>: ReverseSearcher<'a>,
614    {
615        self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack)
616    }
617
618    #[inline]
619    fn as_utf8_pattern(&self) -> Option<Utf8Pattern<'_>> {
620        Some(Utf8Pattern::CharPattern(*self))
621    }
622}
623
624/////////////////////////////////////////////////////////////////////////////
625// Impl for a MultiCharEq wrapper
626/////////////////////////////////////////////////////////////////////////////
627
628#[doc(hidden)]
629trait MultiCharEq {
630    fn matches(&mut self, c: char) -> bool;
631}
632
633impl<F> MultiCharEq for F
634where
635    F: FnMut(char) -> bool,
636{
637    #[inline]
638    fn matches(&mut self, c: char) -> bool {
639        (*self)(c)
640    }
641}
642
643impl<const N: usize> MultiCharEq for [char; N] {
644    #[inline]
645    fn matches(&mut self, c: char) -> bool {
646        self.iter().any(|&m| m == c)
647    }
648}
649
650impl<const N: usize> MultiCharEq for &[char; N] {
651    #[inline]
652    fn matches(&mut self, c: char) -> bool {
653        self.iter().any(|&m| m == c)
654    }
655}
656
657impl MultiCharEq for &[char] {
658    #[inline]
659    fn matches(&mut self, c: char) -> bool {
660        self.iter().any(|&m| m == c)
661    }
662}
663
664struct MultiCharEqPattern<C: MultiCharEq>(C);
665
666#[derive(Clone, Debug)]
667struct MultiCharEqSearcher<'a, C: MultiCharEq> {
668    char_eq: C,
669    haystack: &'a str,
670    char_indices: super::CharIndices<'a>,
671}
672
673impl<C: MultiCharEq> Pattern for MultiCharEqPattern<C> {
674    type Searcher<'a> = MultiCharEqSearcher<'a, C>;
675
676    #[inline]
677    fn into_searcher(self, haystack: &str) -> MultiCharEqSearcher<'_, C> {
678        MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
679    }
680}
681
682unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
683    #[inline]
684    fn haystack(&self) -> &'a str {
685        self.haystack
686    }
687
688    #[inline]
689    fn next(&mut self) -> SearchStep {
690        let s = &mut self.char_indices;
691        // Compare lengths of the internal byte slice iterator
692        // to find length of current char
693        let pre_len = s.iter.iter.len();
694        if let Some((i, c)) = s.next() {
695            let len = s.iter.iter.len();
696            let char_len = pre_len - len;
697            if self.char_eq.matches(c) {
698                return SearchStep::Match(i, i + char_len);
699            } else {
700                return SearchStep::Reject(i, i + char_len);
701            }
702        }
703        SearchStep::Done
704    }
705}
706
707unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
708    #[inline]
709    fn next_back(&mut self) -> SearchStep {
710        let s = &mut self.char_indices;
711        // Compare lengths of the internal byte slice iterator
712        // to find length of current char
713        let pre_len = s.iter.iter.len();
714        if let Some((i, c)) = s.next_back() {
715            let len = s.iter.iter.len();
716            let char_len = pre_len - len;
717            if self.char_eq.matches(c) {
718                return SearchStep::Match(i, i + char_len);
719            } else {
720                return SearchStep::Reject(i, i + char_len);
721            }
722        }
723        SearchStep::Done
724    }
725}
726
727impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}
728
729/////////////////////////////////////////////////////////////////////////////
730
731macro_rules! pattern_methods {
732    ($a:lifetime, $t:ty, $pmap:expr, $smap:expr) => {
733        type Searcher<$a> = $t;
734
735        #[inline]
736        fn into_searcher<$a>(self, haystack: &$a str) -> $t {
737            ($smap)(($pmap)(self).into_searcher(haystack))
738        }
739
740        #[inline]
741        fn is_contained_in<$a>(self, haystack: &$a str) -> bool {
742            ($pmap)(self).is_contained_in(haystack)
743        }
744
745        #[inline]
746        fn is_prefix_of<$a>(self, haystack: &$a str) -> bool {
747            ($pmap)(self).is_prefix_of(haystack)
748        }
749
750        #[inline]
751        fn strip_prefix_of<$a>(self, haystack: &$a str) -> Option<&$a str> {
752            ($pmap)(self).strip_prefix_of(haystack)
753        }
754
755        #[inline]
756        fn is_suffix_of<$a>(self, haystack: &$a str) -> bool
757        where
758            $t: ReverseSearcher<$a>,
759        {
760            ($pmap)(self).is_suffix_of(haystack)
761        }
762
763        #[inline]
764        fn strip_suffix_of<$a>(self, haystack: &$a str) -> Option<&$a str>
765        where
766            $t: ReverseSearcher<$a>,
767        {
768            ($pmap)(self).strip_suffix_of(haystack)
769        }
770    };
771}
772
773macro_rules! searcher_methods {
774    (forward) => {
775        #[inline]
776        fn haystack(&self) -> &'a str {
777            self.0.haystack()
778        }
779        #[inline]
780        fn next(&mut self) -> SearchStep {
781            self.0.next()
782        }
783        #[inline]
784        fn next_match(&mut self) -> Option<(usize, usize)> {
785            self.0.next_match()
786        }
787        #[inline]
788        fn next_reject(&mut self) -> Option<(usize, usize)> {
789            self.0.next_reject()
790        }
791    };
792    (reverse) => {
793        #[inline]
794        fn next_back(&mut self) -> SearchStep {
795            self.0.next_back()
796        }
797        #[inline]
798        fn next_match_back(&mut self) -> Option<(usize, usize)> {
799            self.0.next_match_back()
800        }
801        #[inline]
802        fn next_reject_back(&mut self) -> Option<(usize, usize)> {
803            self.0.next_reject_back()
804        }
805    };
806}
807
808/// Associated type for `<[char; N] as Pattern>::Searcher<'a>`.
809#[derive(Clone, Debug)]
810pub struct CharArraySearcher<'a, const N: usize>(
811    <MultiCharEqPattern<[char; N]> as Pattern>::Searcher<'a>,
812);
813
814/// Associated type for `<&[char; N] as Pattern>::Searcher<'a>`.
815#[derive(Clone, Debug)]
816pub struct CharArrayRefSearcher<'a, 'b, const N: usize>(
817    <MultiCharEqPattern<&'b [char; N]> as Pattern>::Searcher<'a>,
818);
819
820/// Searches for chars that are equal to any of the [`char`]s in the array.
821///
822/// # Examples
823///
824/// ```
825/// assert_eq!("Hello world".find(['o', 'l']), Some(2));
826/// assert_eq!("Hello world".find(['h', 'w']), Some(6));
827/// ```
828impl<const N: usize> Pattern for [char; N] {
829    pattern_methods!('a, CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher);
830}
831
832unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> {
833    searcher_methods!(forward);
834}
835
836unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> {
837    searcher_methods!(reverse);
838}
839
840impl<'a, const N: usize> DoubleEndedSearcher<'a> for CharArraySearcher<'a, N> {}
841
842/// Searches for chars that are equal to any of the [`char`]s in the array.
843///
844/// # Examples
845///
846/// ```
847/// assert_eq!("Hello world".find(&['o', 'l']), Some(2));
848/// assert_eq!("Hello world".find(&['h', 'w']), Some(6));
849/// ```
850impl<'b, const N: usize> Pattern for &'b [char; N] {
851    pattern_methods!('a, CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher);
852}
853
854unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
855    searcher_methods!(forward);
856}
857
858unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
859    searcher_methods!(reverse);
860}
861
862impl<'a, 'b, const N: usize> DoubleEndedSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {}
863
864/////////////////////////////////////////////////////////////////////////////
865// Impl for &[char]
866/////////////////////////////////////////////////////////////////////////////
867
868// Todo: Change / Remove due to ambiguity in meaning.
869
870/// Associated type for `<&[char] as Pattern>::Searcher<'a>`.
871#[derive(Clone, Debug)]
872pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern>::Searcher<'a>);
873
874unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
875    searcher_methods!(forward);
876}
877
878unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
879    searcher_methods!(reverse);
880}
881
882impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
883
884/// Searches for chars that are equal to any of the [`char`]s in the slice.
885///
886/// # Examples
887///
888/// ```
889/// assert_eq!("Hello world".find(&['o', 'l'][..]), Some(2));
890/// assert_eq!("Hello world".find(&['h', 'w'][..]), Some(6));
891/// ```
892impl<'b> Pattern for &'b [char] {
893    pattern_methods!('a, CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
894}
895
896/////////////////////////////////////////////////////////////////////////////
897// Impl for F: FnMut(char) -> bool
898/////////////////////////////////////////////////////////////////////////////
899
900/// Associated type for `<F as Pattern>::Searcher<'a>`.
901#[derive(Clone)]
902pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern>::Searcher<'a>)
903where
904    F: FnMut(char) -> bool;
905
906impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
907where
908    F: FnMut(char) -> bool,
909{
910    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
911        f.debug_struct("CharPredicateSearcher")
912            .field("haystack", &self.0.haystack)
913            .field("char_indices", &self.0.char_indices)
914            .finish()
915    }
916}
917unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
918where
919    F: FnMut(char) -> bool,
920{
921    searcher_methods!(forward);
922}
923
924unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
925where
926    F: FnMut(char) -> bool,
927{
928    searcher_methods!(reverse);
929}
930
931impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}
932
933/// Searches for [`char`]s that match the given predicate.
934///
935/// # Examples
936///
937/// ```
938/// assert_eq!("Hello world".find(char::is_uppercase), Some(0));
939/// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1));
940/// ```
941impl<F> Pattern for F
942where
943    F: FnMut(char) -> bool,
944{
945    pattern_methods!('a, CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
946}
947
948/////////////////////////////////////////////////////////////////////////////
949// Impl for &&str
950/////////////////////////////////////////////////////////////////////////////
951
952/// Delegates to the `&str` impl.
953impl<'b, 'c> Pattern for &'c &'b str {
954    pattern_methods!('a, StrSearcher<'a, 'b>, |&s| s, |s| s);
955}
956
957/////////////////////////////////////////////////////////////////////////////
958// Impl for &str
959/////////////////////////////////////////////////////////////////////////////
960
961/// Non-allocating substring search.
962///
963/// Will handle the pattern `""` as returning empty matches at each character
964/// boundary.
965///
966/// # Examples
967///
968/// ```
969/// assert_eq!("Hello world".find("world"), Some(6));
970/// ```
971impl<'b> Pattern for &'b str {
972    type Searcher<'a> = StrSearcher<'a, 'b>;
973
974    #[inline]
975    fn into_searcher(self, haystack: &str) -> StrSearcher<'_, 'b> {
976        StrSearcher::new(haystack, self)
977    }
978
979    /// Checks whether the pattern matches at the front of the haystack.
980    #[inline]
981    fn is_prefix_of(self, haystack: &str) -> bool {
982        haystack.as_bytes().starts_with(self.as_bytes())
983    }
984
985    /// Checks whether the pattern matches anywhere in the haystack
986    #[inline]
987    fn is_contained_in(self, haystack: &str) -> bool {
988        if self.len() == 0 {
989            return true;
990        }
991
992        match self.len().cmp(&haystack.len()) {
993            Ordering::Less => {
994                if self.len() == 1 {
995                    return haystack.as_bytes().contains(&self.as_bytes()[0]);
996                }
997
998                #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
999                if self.len() <= 32 {
1000                    if let Some(result) = simd_contains(self, haystack) {
1001                        return result;
1002                    }
1003                }
1004
1005                self.into_searcher(haystack).next_match().is_some()
1006            }
1007            _ => self == haystack,
1008        }
1009    }
1010
1011    /// Removes the pattern from the front of haystack, if it matches.
1012    #[inline]
1013    fn strip_prefix_of(self, haystack: &str) -> Option<&str> {
1014        if self.is_prefix_of(haystack) {
1015            // SAFETY: prefix was just verified to exist.
1016            unsafe { Some(haystack.get_unchecked(self.as_bytes().len()..)) }
1017        } else {
1018            None
1019        }
1020    }
1021
1022    /// Checks whether the pattern matches at the back of the haystack.
1023    #[inline]
1024    fn is_suffix_of<'a>(self, haystack: &'a str) -> bool
1025    where
1026        Self::Searcher<'a>: ReverseSearcher<'a>,
1027    {
1028        haystack.as_bytes().ends_with(self.as_bytes())
1029    }
1030
1031    /// Removes the pattern from the back of haystack, if it matches.
1032    #[inline]
1033    fn strip_suffix_of<'a>(self, haystack: &'a str) -> Option<&'a str>
1034    where
1035        Self::Searcher<'a>: ReverseSearcher<'a>,
1036    {
1037        if self.is_suffix_of(haystack) {
1038            let i = haystack.len() - self.as_bytes().len();
1039            // SAFETY: suffix was just verified to exist.
1040            unsafe { Some(haystack.get_unchecked(..i)) }
1041        } else {
1042            None
1043        }
1044    }
1045
1046    #[inline]
1047    fn as_utf8_pattern(&self) -> Option<Utf8Pattern<'_>> {
1048        Some(Utf8Pattern::StringPattern(self.as_bytes()))
1049    }
1050}
1051
1052/////////////////////////////////////////////////////////////////////////////
1053// Two Way substring searcher
1054/////////////////////////////////////////////////////////////////////////////
1055
1056#[derive(Clone, Debug)]
1057/// Associated type for `<&str as Pattern>::Searcher<'a>`.
1058pub struct StrSearcher<'a, 'b> {
1059    haystack: &'a str,
1060    needle: &'b str,
1061
1062    searcher: StrSearcherImpl,
1063}
1064
1065#[derive(Clone, Debug)]
1066enum StrSearcherImpl {
1067    Empty(EmptyNeedle),
1068    TwoWay(TwoWaySearcher),
1069}
1070
1071#[derive(Clone, Debug)]
1072struct EmptyNeedle {
1073    position: usize,
1074    end: usize,
1075    is_match_fw: bool,
1076    is_match_bw: bool,
1077    // Needed in case of an empty haystack, see #85462
1078    is_finished: bool,
1079}
1080
1081impl<'a, 'b> StrSearcher<'a, 'b> {
1082    fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
1083        if needle.is_empty() {
1084            StrSearcher {
1085                haystack,
1086                needle,
1087                searcher: StrSearcherImpl::Empty(EmptyNeedle {
1088                    position: 0,
1089                    end: haystack.len(),
1090                    is_match_fw: true,
1091                    is_match_bw: true,
1092                    is_finished: false,
1093                }),
1094            }
1095        } else {
1096            StrSearcher {
1097                haystack,
1098                needle,
1099                searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
1100                    needle.as_bytes(),
1101                    haystack.len(),
1102                )),
1103            }
1104        }
1105    }
1106}
1107
1108unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
1109    #[inline]
1110    fn haystack(&self) -> &'a str {
1111        self.haystack
1112    }
1113
1114    #[inline]
1115    fn next(&mut self) -> SearchStep {
1116        match self.searcher {
1117            StrSearcherImpl::Empty(ref mut searcher) => {
1118                if searcher.is_finished {
1119                    return SearchStep::Done;
1120                }
1121                // empty needle rejects every char and matches every empty string between them
1122                let is_match = searcher.is_match_fw;
1123                searcher.is_match_fw = !searcher.is_match_fw;
1124                let pos = searcher.position;
1125                match self.haystack[pos..].chars().next() {
1126                    _ if is_match => SearchStep::Match(pos, pos),
1127                    None => {
1128                        searcher.is_finished = true;
1129                        SearchStep::Done
1130                    }
1131                    Some(ch) => {
1132                        searcher.position += ch.len_utf8();
1133                        SearchStep::Reject(pos, searcher.position)
1134                    }
1135                }
1136            }
1137            StrSearcherImpl::TwoWay(ref mut searcher) => {
1138                // TwoWaySearcher produces valid *Match* indices that split at char boundaries
1139                // as long as it does correct matching and that haystack and needle are
1140                // valid UTF-8
1141                // *Rejects* from the algorithm can fall on any indices, but we will walk them
1142                // manually to the next character boundary, so that they are utf-8 safe.
1143                if searcher.position == self.haystack.len() {
1144                    return SearchStep::Done;
1145                }
1146                let is_long = searcher.memory == usize::MAX;
1147                match searcher.next::<RejectAndMatch>(
1148                    self.haystack.as_bytes(),
1149                    self.needle.as_bytes(),
1150                    is_long,
1151                ) {
1152                    SearchStep::Reject(a, mut b) => {
1153                        // skip to next char boundary
1154                        while !self.haystack.is_char_boundary(b) {
1155                            b += 1;
1156                        }
1157                        searcher.position = cmp::max(b, searcher.position);
1158                        SearchStep::Reject(a, b)
1159                    }
1160                    otherwise => otherwise,
1161                }
1162            }
1163        }
1164    }
1165
1166    #[inline]
1167    fn next_match(&mut self) -> Option<(usize, usize)> {
1168        match self.searcher {
1169            StrSearcherImpl::Empty(..) => loop {
1170                match self.next() {
1171                    SearchStep::Match(a, b) => return Some((a, b)),
1172                    SearchStep::Done => return None,
1173                    SearchStep::Reject(..) => {}
1174                }
1175            },
1176            StrSearcherImpl::TwoWay(ref mut searcher) => {
1177                let is_long = searcher.memory == usize::MAX;
1178                // write out `true` and `false` cases to encourage the compiler
1179                // to specialize the two cases separately.
1180                if is_long {
1181                    searcher.next::<MatchOnly>(
1182                        self.haystack.as_bytes(),
1183                        self.needle.as_bytes(),
1184                        true,
1185                    )
1186                } else {
1187                    searcher.next::<MatchOnly>(
1188                        self.haystack.as_bytes(),
1189                        self.needle.as_bytes(),
1190                        false,
1191                    )
1192                }
1193            }
1194        }
1195    }
1196}
1197
1198unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
1199    #[inline]
1200    fn next_back(&mut self) -> SearchStep {
1201        match self.searcher {
1202            StrSearcherImpl::Empty(ref mut searcher) => {
1203                if searcher.is_finished {
1204                    return SearchStep::Done;
1205                }
1206                let is_match = searcher.is_match_bw;
1207                searcher.is_match_bw = !searcher.is_match_bw;
1208                let end = searcher.end;
1209                match self.haystack[..end].chars().next_back() {
1210                    _ if is_match => SearchStep::Match(end, end),
1211                    None => {
1212                        searcher.is_finished = true;
1213                        SearchStep::Done
1214                    }
1215                    Some(ch) => {
1216                        searcher.end -= ch.len_utf8();
1217                        SearchStep::Reject(searcher.end, end)
1218                    }
1219                }
1220            }
1221            StrSearcherImpl::TwoWay(ref mut searcher) => {
1222                if searcher.end == 0 {
1223                    return SearchStep::Done;
1224                }
1225                let is_long = searcher.memory == usize::MAX;
1226                match searcher.next_back::<RejectAndMatch>(
1227                    self.haystack.as_bytes(),
1228                    self.needle.as_bytes(),
1229                    is_long,
1230                ) {
1231                    SearchStep::Reject(mut a, b) => {
1232                        // skip to next char boundary
1233                        while !self.haystack.is_char_boundary(a) {
1234                            a -= 1;
1235                        }
1236                        searcher.end = cmp::min(a, searcher.end);
1237                        SearchStep::Reject(a, b)
1238                    }
1239                    otherwise => otherwise,
1240                }
1241            }
1242        }
1243    }
1244
1245    #[inline]
1246    fn next_match_back(&mut self) -> Option<(usize, usize)> {
1247        match self.searcher {
1248            StrSearcherImpl::Empty(..) => loop {
1249                match self.next_back() {
1250                    SearchStep::Match(a, b) => return Some((a, b)),
1251                    SearchStep::Done => return None,
1252                    SearchStep::Reject(..) => {}
1253                }
1254            },
1255            StrSearcherImpl::TwoWay(ref mut searcher) => {
1256                let is_long = searcher.memory == usize::MAX;
1257                // write out `true` and `false`, like `next_match`
1258                if is_long {
1259                    searcher.next_back::<MatchOnly>(
1260                        self.haystack.as_bytes(),
1261                        self.needle.as_bytes(),
1262                        true,
1263                    )
1264                } else {
1265                    searcher.next_back::<MatchOnly>(
1266                        self.haystack.as_bytes(),
1267                        self.needle.as_bytes(),
1268                        false,
1269                    )
1270                }
1271            }
1272        }
1273    }
1274}
1275
1276/// The internal state of the two-way substring search algorithm.
1277#[derive(Clone, Debug)]
1278struct TwoWaySearcher {
1279    // constants
1280    /// critical factorization index
1281    crit_pos: usize,
1282    /// critical factorization index for reversed needle
1283    crit_pos_back: usize,
1284    period: usize,
1285    /// `byteset` is an extension (not part of the two way algorithm);
1286    /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
1287    /// to a (byte & 63) == j present in the needle.
1288    byteset: u64,
1289
1290    // variables
1291    position: usize,
1292    end: usize,
1293    /// index into needle before which we have already matched
1294    memory: usize,
1295    /// index into needle after which we have already matched
1296    memory_back: usize,
1297}
1298
1299/*
1300    This is the Two-Way search algorithm, which was introduced in the paper:
1301    Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
1302
1303    Here's some background information.
1304
1305    A *word* is a string of symbols. The *length* of a word should be a familiar
1306    notion, and here we denote it for any word x by |x|.
1307    (We also allow for the possibility of the *empty word*, a word of length zero).
1308
1309    If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
1310    *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
1311    For example, both 1 and 2 are periods for the string "aa". As another example,
1312    the only period of the string "abcd" is 4.
1313
1314    We denote by period(x) the *smallest* period of x (provided that x is non-empty).
1315    This is always well-defined since every non-empty word x has at least one period,
1316    |x|. We sometimes call this *the period* of x.
1317
1318    If u, v and x are words such that x = uv, where uv is the concatenation of u and
1319    v, then we say that (u, v) is a *factorization* of x.
1320
1321    Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
1322    that both of the following hold
1323
1324      - either w is a suffix of u or u is a suffix of w
1325      - either w is a prefix of v or v is a prefix of w
1326
1327    then w is said to be a *repetition* for the factorization (u, v).
1328
1329    Just to unpack this, there are four possibilities here. Let w = "abc". Then we
1330    might have:
1331
1332      - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
1333      - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
1334      - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
1335      - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
1336
1337    Note that the word vu is a repetition for any factorization (u,v) of x = uv,
1338    so every factorization has at least one repetition.
1339
1340    If x is a string and (u, v) is a factorization for x, then a *local period* for
1341    (u, v) is an integer r such that there is some word w such that |w| = r and w is
1342    a repetition for (u, v).
1343
1344    We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
1345    call this *the local period* of (u, v). Provided that x = uv is non-empty, this
1346    is well-defined (because each non-empty word has at least one factorization, as
1347    noted above).
1348
1349    It can be proven that the following is an equivalent definition of a local period
1350    for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
1351    all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
1352    defined. (i.e., i > 0 and i + r < |x|).
1353
1354    Using the above reformulation, it is easy to prove that
1355
1356        1 <= local_period(u, v) <= period(uv)
1357
1358    A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
1359    *critical factorization*.
1360
1361    The algorithm hinges on the following theorem, which is stated without proof:
1362
1363    **Critical Factorization Theorem** Any word x has at least one critical
1364    factorization (u, v) such that |u| < period(x).
1365
1366    The purpose of maximal_suffix is to find such a critical factorization.
1367
1368    If the period is short, compute another factorization x = u' v' to use
1369    for reverse search, chosen instead so that |v'| < period(x).
1370
1371*/
1372impl TwoWaySearcher {
1373    fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
1374        let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
1375        let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);
1376
1377        let (crit_pos, period) = if crit_pos_false > crit_pos_true {
1378            (crit_pos_false, period_false)
1379        } else {
1380            (crit_pos_true, period_true)
1381        };
1382
1383        // A particularly readable explanation of what's going on here can be found
1384        // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
1385        // see the code for "Algorithm CP" on p. 323.
1386        //
1387        // What's going on is we have some critical factorization (u, v) of the
1388        // needle, and we want to determine whether u is a suffix of
1389        // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
1390        // "Algorithm CP2", which is optimized for when the period of the needle
1391        // is large.
1392        if needle[..crit_pos] == needle[period..period + crit_pos] {
1393            // short period case -- the period is exact
1394            // compute a separate critical factorization for the reversed needle
1395            // x = u' v' where |v'| < period(x).
1396            //
1397            // This is sped up by the period being known already.
1398            // Note that a case like x = "acba" may be factored exactly forwards
1399            // (crit_pos = 1, period = 3) while being factored with approximate
1400            // period in reverse (crit_pos = 2, period = 2). We use the given
1401            // reverse factorization but keep the exact period.
1402            let crit_pos_back = needle.len()
1403                - cmp::max(
1404                    TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
1405                    TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
1406                );
1407
1408            TwoWaySearcher {
1409                crit_pos,
1410                crit_pos_back,
1411                period,
1412                byteset: Self::byteset_create(&needle[..period]),
1413
1414                position: 0,
1415                end,
1416                memory: 0,
1417                memory_back: needle.len(),
1418            }
1419        } else {
1420            // long period case -- we have an approximation to the actual period,
1421            // and don't use memorization.
1422            //
1423            // Approximate the period by lower bound max(|u|, |v|) + 1.
1424            // The critical factorization is efficient to use for both forward and
1425            // reverse search.
1426
1427            TwoWaySearcher {
1428                crit_pos,
1429                crit_pos_back: crit_pos,
1430                period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
1431                byteset: Self::byteset_create(needle),
1432
1433                position: 0,
1434                end,
1435                memory: usize::MAX, // Dummy value to signify that the period is long
1436                memory_back: usize::MAX,
1437            }
1438        }
1439    }
1440
1441    #[inline]
1442    fn byteset_create(bytes: &[u8]) -> u64 {
1443        bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
1444    }
1445
1446    #[inline]
1447    fn byteset_contains(&self, byte: u8) -> bool {
1448        (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
1449    }
1450
1451    // One of the main ideas of Two-Way is that we factorize the needle into
1452    // two halves, (u, v), and begin trying to find v in the haystack by scanning
1453    // left to right. If v matches, we try to match u by scanning right to left.
1454    // How far we can jump when we encounter a mismatch is all based on the fact
1455    // that (u, v) is a critical factorization for the needle.
1456    #[inline]
1457    fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1458    where
1459        S: TwoWayStrategy,
1460    {
1461        // `next()` uses `self.position` as its cursor
1462        let old_pos = self.position;
1463        let needle_last = needle.len() - 1;
1464        'search: loop {
1465            // Check that we have room to search in
1466            // position + needle_last can not overflow if we assume slices
1467            // are bounded by isize's range.
1468            let tail_byte = match haystack.get(self.position + needle_last) {
1469                Some(&b) => b,
1470                None => {
1471                    self.position = haystack.len();
1472                    return S::rejecting(old_pos, self.position);
1473                }
1474            };
1475
1476            if S::use_early_reject() && old_pos != self.position {
1477                return S::rejecting(old_pos, self.position);
1478            }
1479
1480            // Quickly skip by large portions unrelated to our substring
1481            if !self.byteset_contains(tail_byte) {
1482                self.position += needle.len();
1483                if !long_period {
1484                    self.memory = 0;
1485                }
1486                continue 'search;
1487            }
1488
1489            // See if the right part of the needle matches
1490            let start =
1491                if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) };
1492            for i in start..needle.len() {
1493                if needle[i] != haystack[self.position + i] {
1494                    self.position += i - self.crit_pos + 1;
1495                    if !long_period {
1496                        self.memory = 0;
1497                    }
1498                    continue 'search;
1499                }
1500            }
1501
1502            // See if the left part of the needle matches
1503            let start = if long_period { 0 } else { self.memory };
1504            for i in (start..self.crit_pos).rev() {
1505                if needle[i] != haystack[self.position + i] {
1506                    self.position += self.period;
1507                    if !long_period {
1508                        self.memory = needle.len() - self.period;
1509                    }
1510                    continue 'search;
1511                }
1512            }
1513
1514            // We have found a match!
1515            let match_pos = self.position;
1516
1517            // Note: add self.period instead of needle.len() to have overlapping matches
1518            self.position += needle.len();
1519            if !long_period {
1520                self.memory = 0; // set to needle.len() - self.period for overlapping matches
1521            }
1522
1523            return S::matching(match_pos, match_pos + needle.len());
1524        }
1525    }
1526
1527    // Follows the ideas in `next()`.
1528    //
1529    // The definitions are symmetrical, with period(x) = period(reverse(x))
1530    // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
1531    // is a critical factorization, so is (reverse(v), reverse(u)).
1532    //
1533    // For the reverse case we have computed a critical factorization x = u' v'
1534    // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
1535    // thus |v'| < period(x) for the reverse.
1536    //
1537    // To search in reverse through the haystack, we search forward through
1538    // a reversed haystack with a reversed needle, matching first u' and then v'.
1539    #[inline]
1540    fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1541    where
1542        S: TwoWayStrategy,
1543    {
1544        // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1545        // are independent.
1546        let old_end = self.end;
1547        'search: loop {
1548            // Check that we have room to search in
1549            // end - needle.len() will wrap around when there is no more room,
1550            // but due to slice length limits it can never wrap all the way back
1551            // into the length of haystack.
1552            let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
1553                Some(&b) => b,
1554                None => {
1555                    self.end = 0;
1556                    return S::rejecting(0, old_end);
1557                }
1558            };
1559
1560            if S::use_early_reject() && old_end != self.end {
1561                return S::rejecting(self.end, old_end);
1562            }
1563
1564            // Quickly skip by large portions unrelated to our substring
1565            if !self.byteset_contains(front_byte) {
1566                self.end -= needle.len();
1567                if !long_period {
1568                    self.memory_back = needle.len();
1569                }
1570                continue 'search;
1571            }
1572
1573            // See if the left part of the needle matches
1574            let crit = if long_period {
1575                self.crit_pos_back
1576            } else {
1577                cmp::min(self.crit_pos_back, self.memory_back)
1578            };
1579            for i in (0..crit).rev() {
1580                if needle[i] != haystack[self.end - needle.len() + i] {
1581                    self.end -= self.crit_pos_back - i;
1582                    if !long_period {
1583                        self.memory_back = needle.len();
1584                    }
1585                    continue 'search;
1586                }
1587            }
1588
1589            // See if the right part of the needle matches
1590            let needle_end = if long_period { needle.len() } else { self.memory_back };
1591            for i in self.crit_pos_back..needle_end {
1592                if needle[i] != haystack[self.end - needle.len() + i] {
1593                    self.end -= self.period;
1594                    if !long_period {
1595                        self.memory_back = self.period;
1596                    }
1597                    continue 'search;
1598                }
1599            }
1600
1601            // We have found a match!
1602            let match_pos = self.end - needle.len();
1603            // Note: sub self.period instead of needle.len() to have overlapping matches
1604            self.end -= needle.len();
1605            if !long_period {
1606                self.memory_back = needle.len();
1607            }
1608
1609            return S::matching(match_pos, match_pos + needle.len());
1610        }
1611    }
1612
1613    // Compute the maximal suffix of `arr`.
1614    //
1615    // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1616    //
1617    // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1618    // period of v.
1619    //
1620    // `order_greater` determines if lexical order is `<` or `>`. Both
1621    // orders must be computed -- the ordering with the largest `i` gives
1622    // a critical factorization.
1623    //
1624    // For long period cases, the resulting period is not exact (it is too short).
1625    #[inline]
1626    fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
1627        let mut left = 0; // Corresponds to i in the paper
1628        let mut right = 1; // Corresponds to j in the paper
1629        let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1630        // to match 0-based indexing.
1631        let mut period = 1; // Corresponds to p in the paper
1632
1633        while let Some(&a) = arr.get(right + offset) {
1634            // `left` will be inbounds when `right` is.
1635            let b = arr[left + offset];
1636            if (a < b && !order_greater) || (a > b && order_greater) {
1637                // Suffix is smaller, period is entire prefix so far.
1638                right += offset + 1;
1639                offset = 0;
1640                period = right - left;
1641            } else if a == b {
1642                // Advance through repetition of the current period.
1643                if offset + 1 == period {
1644                    right += offset + 1;
1645                    offset = 0;
1646                } else {
1647                    offset += 1;
1648                }
1649            } else {
1650                // Suffix is larger, start over from current location.
1651                left = right;
1652                right += 1;
1653                offset = 0;
1654                period = 1;
1655            }
1656        }
1657        (left, period)
1658    }
1659
1660    // Compute the maximal suffix of the reverse of `arr`.
1661    //
1662    // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1663    //
1664    // Returns `i` where `i` is the starting index of v', from the back;
1665    // returns immediately when a period of `known_period` is reached.
1666    //
1667    // `order_greater` determines if lexical order is `<` or `>`. Both
1668    // orders must be computed -- the ordering with the largest `i` gives
1669    // a critical factorization.
1670    //
1671    // For long period cases, the resulting period is not exact (it is too short).
1672    fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize {
1673        let mut left = 0; // Corresponds to i in the paper
1674        let mut right = 1; // Corresponds to j in the paper
1675        let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1676        // to match 0-based indexing.
1677        let mut period = 1; // Corresponds to p in the paper
1678        let n = arr.len();
1679
1680        while right + offset < n {
1681            let a = arr[n - (1 + right + offset)];
1682            let b = arr[n - (1 + left + offset)];
1683            if (a < b && !order_greater) || (a > b && order_greater) {
1684                // Suffix is smaller, period is entire prefix so far.
1685                right += offset + 1;
1686                offset = 0;
1687                period = right - left;
1688            } else if a == b {
1689                // Advance through repetition of the current period.
1690                if offset + 1 == period {
1691                    right += offset + 1;
1692                    offset = 0;
1693                } else {
1694                    offset += 1;
1695                }
1696            } else {
1697                // Suffix is larger, start over from current location.
1698                left = right;
1699                right += 1;
1700                offset = 0;
1701                period = 1;
1702            }
1703            if period == known_period {
1704                break;
1705            }
1706        }
1707        debug_assert!(period <= known_period);
1708        left
1709    }
1710}
1711
1712// TwoWayStrategy allows the algorithm to either skip non-matches as quickly
1713// as possible, or to work in a mode where it emits Rejects relatively quickly.
1714trait TwoWayStrategy {
1715    type Output;
1716    fn use_early_reject() -> bool;
1717    fn rejecting(a: usize, b: usize) -> Self::Output;
1718    fn matching(a: usize, b: usize) -> Self::Output;
1719}
1720
1721/// Skip to match intervals as quickly as possible
1722enum MatchOnly {}
1723
1724impl TwoWayStrategy for MatchOnly {
1725    type Output = Option<(usize, usize)>;
1726
1727    #[inline]
1728    fn use_early_reject() -> bool {
1729        false
1730    }
1731    #[inline]
1732    fn rejecting(_a: usize, _b: usize) -> Self::Output {
1733        None
1734    }
1735    #[inline]
1736    fn matching(a: usize, b: usize) -> Self::Output {
1737        Some((a, b))
1738    }
1739}
1740
1741/// Emit Rejects regularly
1742enum RejectAndMatch {}
1743
1744impl TwoWayStrategy for RejectAndMatch {
1745    type Output = SearchStep;
1746
1747    #[inline]
1748    fn use_early_reject() -> bool {
1749        true
1750    }
1751    #[inline]
1752    fn rejecting(a: usize, b: usize) -> Self::Output {
1753        SearchStep::Reject(a, b)
1754    }
1755    #[inline]
1756    fn matching(a: usize, b: usize) -> Self::Output {
1757        SearchStep::Match(a, b)
1758    }
1759}
1760
1761/// SIMD search for short needles based on
1762/// Wojciech Muła's "SIMD-friendly algorithms for substring searching"[0]
1763///
1764/// It skips ahead by the vector width on each iteration (rather than the needle length as two-way
1765/// does) by probing the first and last byte of the needle for the whole vector width
1766/// and only doing full needle comparisons when the vectorized probe indicated potential matches.
1767///
1768/// Since the x86_64 baseline only offers SSE2 we only use u8x16 here.
1769/// If we ever ship std with for x86-64-v3 or adapt this for other platforms then wider vectors
1770/// should be evaluated.
1771///
1772/// For haystacks smaller than vector-size + needle length it falls back to
1773/// a naive O(n*m) search so this implementation should not be called on larger needles.
1774///
1775/// [0]: http://0x80.pl/articles/simd-strfind.html#sse-avx2
1776#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
1777#[inline]
1778fn simd_contains(needle: &str, haystack: &str) -> Option<bool> {
1779    let needle = needle.as_bytes();
1780    let haystack = haystack.as_bytes();
1781
1782    debug_assert!(needle.len() > 1);
1783
1784    use crate::ops::BitAnd;
1785    use crate::simd::cmp::SimdPartialEq;
1786    use crate::simd::{mask8x16 as Mask, u8x16 as Block};
1787
1788    let first_probe = needle[0];
1789    let last_byte_offset = needle.len() - 1;
1790
1791    // the offset used for the 2nd vector
1792    let second_probe_offset = if needle.len() == 2 {
1793        // never bail out on len=2 needles because the probes will fully cover them and have
1794        // no degenerate cases.
1795        1
1796    } else {
1797        // try a few bytes in case first and last byte of the needle are the same
1798        let Some(second_probe_offset) =
1799            (needle.len().saturating_sub(4)..needle.len()).rfind(|&idx| needle[idx] != first_probe)
1800        else {
1801            // fall back to other search methods if we can't find any different bytes
1802            // since we could otherwise hit some degenerate cases
1803            return None;
1804        };
1805        second_probe_offset
1806    };
1807
1808    // do a naive search if the haystack is too small to fit
1809    if haystack.len() < Block::LEN + last_byte_offset {
1810        return Some(haystack.windows(needle.len()).any(|c| c == needle));
1811    }
1812
1813    let first_probe: Block = Block::splat(first_probe);
1814    let second_probe: Block = Block::splat(needle[second_probe_offset]);
1815    // first byte are already checked by the outer loop. to verify a match only the
1816    // remainder has to be compared.
1817    let trimmed_needle = &needle[1..];
1818
1819    // this #[cold] is load-bearing, benchmark before removing it...
1820    let check_mask = #[cold]
1821    |idx, mask: u16, skip: bool| -> bool {
1822        if skip {
1823            return false;
1824        }
1825
1826        // and so is this. optimizations are weird.
1827        let mut mask = mask;
1828
1829        while mask != 0 {
1830            let trailing = mask.trailing_zeros();
1831            let offset = idx + trailing as usize + 1;
1832            // SAFETY: mask is between 0 and 15 trailing zeroes, we skip one additional byte that was already compared
1833            // and then take trimmed_needle.len() bytes. This is within the bounds defined by the outer loop
1834            unsafe {
1835                let sub = haystack.get_unchecked(offset..).get_unchecked(..trimmed_needle.len());
1836                if small_slice_eq(sub, trimmed_needle) {
1837                    return true;
1838                }
1839            }
1840            mask &= !(1 << trailing);
1841        }
1842        false
1843    };
1844
1845    let test_chunk = |idx| -> u16 {
1846        // SAFETY: this requires at least LANES bytes being readable at idx
1847        // that is ensured by the loop ranges (see comments below)
1848        let a: Block = unsafe { haystack.as_ptr().add(idx).cast::<Block>().read_unaligned() };
1849        // SAFETY: this requires LANES + block_offset bytes being readable at idx
1850        let b: Block = unsafe {
1851            haystack.as_ptr().add(idx).add(second_probe_offset).cast::<Block>().read_unaligned()
1852        };
1853        let eq_first: Mask = a.simd_eq(first_probe);
1854        let eq_last: Mask = b.simd_eq(second_probe);
1855        let both = eq_first.bitand(eq_last);
1856        let mask = both.to_bitmask() as u16;
1857
1858        mask
1859    };
1860
1861    let mut i = 0;
1862    let mut result = false;
1863    // The loop condition must ensure that there's enough headroom to read LANE bytes,
1864    // and not only at the current index but also at the index shifted by block_offset
1865    const UNROLL: usize = 4;
1866    while i + last_byte_offset + UNROLL * Block::LEN < haystack.len() && !result {
1867        let mut masks = [0u16; UNROLL];
1868        for j in 0..UNROLL {
1869            masks[j] = test_chunk(i + j * Block::LEN);
1870        }
1871        for j in 0..UNROLL {
1872            let mask = masks[j];
1873            if mask != 0 {
1874                result |= check_mask(i + j * Block::LEN, mask, result);
1875            }
1876        }
1877        i += UNROLL * Block::LEN;
1878    }
1879    while i + last_byte_offset + Block::LEN < haystack.len() && !result {
1880        let mask = test_chunk(i);
1881        if mask != 0 {
1882            result |= check_mask(i, mask, result);
1883        }
1884        i += Block::LEN;
1885    }
1886
1887    // Process the tail that didn't fit into LANES-sized steps.
1888    // This simply repeats the same procedure but as right-aligned chunk instead
1889    // of a left-aligned one. The last byte must be exactly flush with the string end so
1890    // we don't miss a single byte or read out of bounds.
1891    let i = haystack.len() - last_byte_offset - Block::LEN;
1892    let mask = test_chunk(i);
1893    if mask != 0 {
1894        result |= check_mask(i, mask, result);
1895    }
1896
1897    Some(result)
1898}
1899
1900/// Compares short slices for equality.
1901///
1902/// It avoids a call to libc's memcmp which is faster on long slices
1903/// due to SIMD optimizations but it incurs a function call overhead.
1904///
1905/// # Safety
1906///
1907/// Both slices must have the same length.
1908#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] // only called on x86
1909#[inline]
1910unsafe fn small_slice_eq(x: &[u8], y: &[u8]) -> bool {
1911    debug_assert_eq!(x.len(), y.len());
1912    // This function is adapted from
1913    // https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memmem/util.rs#L32
1914
1915    // If we don't have enough bytes to do 4-byte at a time loads, then
1916    // fall back to the naive slow version.
1917    //
1918    // Potential alternative: We could do a copy_nonoverlapping combined with a mask instead
1919    // of a loop. Benchmark it.
1920    if x.len() < 4 {
1921        for (&b1, &b2) in x.iter().zip(y) {
1922            if b1 != b2 {
1923                return false;
1924            }
1925        }
1926        return true;
1927    }
1928    // When we have 4 or more bytes to compare, then proceed in chunks of 4 at
1929    // a time using unaligned loads.
1930    //
1931    // Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is
1932    // that this particular version of memcmp is likely to be called with tiny
1933    // needles. That means that if we do 8 byte loads, then a higher proportion
1934    // of memcmp calls will use the slower variant above. With that said, this
1935    // is a hypothesis and is only loosely supported by benchmarks. There's
1936    // likely some improvement that could be made here. The main thing here
1937    // though is to optimize for latency, not throughput.
1938
1939    // SAFETY: Via the conditional above, we know that both `px` and `py`
1940    // have the same length, so `px < pxend` implies that `py < pyend`.
1941    // Thus, dereferencing both `px` and `py` in the loop below is safe.
1942    //
1943    // Moreover, we set `pxend` and `pyend` to be 4 bytes before the actual
1944    // end of `px` and `py`. Thus, the final dereference outside of the
1945    // loop is guaranteed to be valid. (The final comparison will overlap with
1946    // the last comparison done in the loop for lengths that aren't multiples
1947    // of four.)
1948    //
1949    // Finally, we needn't worry about alignment here, since we do unaligned
1950    // loads.
1951    unsafe {
1952        let (mut px, mut py) = (x.as_ptr(), y.as_ptr());
1953        let (pxend, pyend) = (px.add(x.len() - 4), py.add(y.len() - 4));
1954        while px < pxend {
1955            let vx = (px as *const u32).read_unaligned();
1956            let vy = (py as *const u32).read_unaligned();
1957            if vx != vy {
1958                return false;
1959            }
1960            px = px.add(4);
1961            py = py.add(4);
1962        }
1963        let vx = (pxend as *const u32).read_unaligned();
1964        let vy = (pyend as *const u32).read_unaligned();
1965        vx == vy
1966    }
1967}