1 //! The string Pattern API.
3 //! The Pattern API provides a generic mechanism for using different pattern
4 //! types when searching through a string.
6 //! For more details, see the traits [`Pattern`], [`Searcher`],
7 //! [`ReverseSearcher`], and [`DoubleEndedSearcher`].
9 //! Although this API is unstable, it is exposed via stable APIs on the
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`.
19 //! let s = "Can you find a needle in a haystack?";
22 //! assert_eq!(s.find("you"), Some(4));
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));
33 //! [pattern-impls]: Pattern#implementors
37 reason = "API not fully fleshed out and ready to be stabilized",
42 use crate::cmp::Ordering;
44 use crate::slice::memchr;
50 /// A `Pattern<'a>` expresses that the implementing type
51 /// can be used as a string pattern for searching in a [`&'a str`][str].
53 /// For example, both `'a'` and `"aa"` are patterns that
54 /// would match at index `1` in the string `"baaaab"`.
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.
60 /// Depending on the type of the pattern, the behaviour of methods like
61 /// [`str::find`] and [`str::contains`] can change. The table below describes
62 /// some of those behaviours.
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 |
77 /// assert_eq!("abaaa".find("ba"), Some(1));
78 /// assert_eq!("abaaa".find("bac"), None);
81 /// assert_eq!("abaaa".find('a'), Some(0));
82 /// assert_eq!("abaaa".find('b'), Some(1));
83 /// assert_eq!("abaaa".find('c'), None);
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);
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);
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);
99 pub trait Pattern<'a>: Sized {
100 /// Associated searcher for this pattern
101 type Searcher: Searcher<'a>;
103 /// Constructs the associated searcher from
104 /// `self` and the `haystack` to search in.
105 fn into_searcher(self, haystack: &'a str) -> Self::Searcher;
107 /// Checks whether the pattern matches anywhere in the haystack
109 fn is_contained_in(self, haystack: &'a str) -> bool {
110 self.into_searcher(haystack).next_match().is_some()
113 /// Checks whether the pattern matches at the front of the haystack
115 fn is_prefix_of(self, haystack: &'a str) -> bool {
116 matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
119 /// Checks whether the pattern matches at the back of the haystack
121 fn is_suffix_of(self, haystack: &'a str) -> bool
123 Self::Searcher: ReverseSearcher<'a>,
125 matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
128 /// Removes the pattern from the front of haystack, if it matches.
130 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
131 if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() {
134 "The first search step from Searcher \
135 must include the first character"
137 // SAFETY: `Searcher` is known to return valid indices.
138 unsafe { Some(haystack.get_unchecked(len..)) }
144 /// Removes the pattern from the back of haystack, if it matches.
146 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
148 Self::Searcher: ReverseSearcher<'a>,
150 if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() {
154 "The first search step from ReverseSearcher \
155 must include the last character"
157 // SAFETY: `Searcher` is known to return valid indices.
158 unsafe { Some(haystack.get_unchecked(..start)) }
167 /// Result of calling [`Searcher::next()`] or [`ReverseSearcher::next_back()`].
168 #[derive(Copy, Clone, Eq, PartialEq, Debug)]
169 pub enum SearchStep {
170 /// Expresses that a match of the pattern has been found at
171 /// `haystack[a..b]`.
173 /// Expresses that `haystack[a..b]` has been rejected as a possible match
176 /// Note that there might be more than one `Reject` between two `Match`es,
177 /// there is no requirement for them to be combined into one.
178 Reject(usize, usize),
179 /// Expresses that every byte of the haystack has been visited, ending
184 /// A searcher for a string pattern.
186 /// This trait provides methods for searching for non-overlapping
187 /// matches of a pattern starting from the front (left) of a string.
189 /// It will be implemented by associated `Searcher`
190 /// types of the [`Pattern`] trait.
192 /// The trait is marked unsafe because the indices returned by the
193 /// [`next()`][Searcher::next] methods are required to lie on valid utf8
194 /// boundaries in the haystack. This enables consumers of this trait to
195 /// slice the haystack without additional runtime checks.
196 pub unsafe trait Searcher<'a> {
197 /// Getter for the underlying string to be searched in
199 /// Will always return the same [`&str`][str].
200 fn haystack(&self) -> &'a str;
202 /// Performs the next search step starting from the front.
204 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches
206 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` can
207 /// not match the pattern, even partially.
208 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack has
211 /// The stream of [`Match`][SearchStep::Match] and
212 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
213 /// will contain index ranges that are adjacent, non-overlapping,
214 /// covering the whole haystack, and laying on utf8 boundaries.
216 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
217 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
218 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
220 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
221 /// might produce the stream
222 /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
223 fn next(&mut self) -> SearchStep;
225 /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next].
227 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
228 /// of this and [`next_reject`][Searcher::next_reject] will overlap. This will return
229 /// `(start_match, end_match)`, where start_match is the index of where
230 /// the match begins, and end_match is the index after the end of the match.
232 fn next_match(&mut self) -> Option<(usize, usize)> {
235 SearchStep::Match(a, b) => return Some((a, b)),
236 SearchStep::Done => return None,
242 /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next]
243 /// and [`next_match()`][Searcher::next_match].
245 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
246 /// of this and [`next_match`][Searcher::next_match] will overlap.
248 fn next_reject(&mut self) -> Option<(usize, usize)> {
251 SearchStep::Reject(a, b) => return Some((a, b)),
252 SearchStep::Done => return None,
259 /// A reverse searcher for a string pattern.
261 /// This trait provides methods for searching for non-overlapping
262 /// matches of a pattern starting from the back (right) of a string.
264 /// It will be implemented by associated [`Searcher`]
265 /// types of the [`Pattern`] trait if the pattern supports searching
266 /// for it from the back.
268 /// The index ranges returned by this trait are not required
269 /// to exactly match those of the forward search in reverse.
271 /// For the reason why this trait is marked unsafe, see the
272 /// parent trait [`Searcher`].
273 pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
274 /// Performs the next search step starting from the back.
276 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]`
277 /// matches the pattern.
278 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]`
279 /// can not match the pattern, even partially.
280 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack
283 /// The stream of [`Match`][SearchStep::Match] and
284 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
285 /// will contain index ranges that are adjacent, non-overlapping,
286 /// covering the whole haystack, and laying on utf8 boundaries.
288 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
289 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
290 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
292 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
293 /// might produce the stream
294 /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`.
295 fn next_back(&mut self) -> SearchStep;
297 /// Finds the next [`Match`][SearchStep::Match] result.
298 /// See [`next_back()`][ReverseSearcher::next_back].
300 fn next_match_back(&mut self) -> Option<(usize, usize)> {
302 match self.next_back() {
303 SearchStep::Match(a, b) => return Some((a, b)),
304 SearchStep::Done => return None,
310 /// Finds the next [`Reject`][SearchStep::Reject] result.
311 /// See [`next_back()`][ReverseSearcher::next_back].
313 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
315 match self.next_back() {
316 SearchStep::Reject(a, b) => return Some((a, b)),
317 SearchStep::Done => return None,
324 /// A marker trait to express that a [`ReverseSearcher`]
325 /// can be used for a [`DoubleEndedIterator`] implementation.
327 /// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need
328 /// to follow these conditions:
330 /// - All results of `next()` need to be identical
331 /// to the results of `next_back()` in reverse order.
332 /// - `next()` and `next_back()` need to behave as
333 /// the two ends of a range of values, that is they
334 /// can not "walk past each other".
338 /// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
339 /// [`char`] only requires looking at one at a time, which behaves the same
342 /// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
343 /// the pattern `"aa"` in the haystack `"aaa"` matches as either
344 /// `"[aa]a"` or `"a[aa]"`, depending from which side it is searched.
345 pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
347 /////////////////////////////////////////////////////////////////////////////
349 /////////////////////////////////////////////////////////////////////////////
351 /// Associated type for `<char as Pattern<'a>>::Searcher`.
352 #[derive(Clone, Debug)]
353 pub struct CharSearcher<'a> {
355 // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack`
356 // This invariant can be broken *within* next_match and next_match_back, however
357 // they must exit with fingers on valid code point boundaries.
358 /// `finger` is the current byte index of the forward search.
359 /// Imagine that it exists before the byte at its index, i.e.
360 /// `haystack[finger]` is the first byte of the slice we must inspect during
361 /// forward searching
363 /// `finger_back` is the current byte index of the reverse search.
364 /// Imagine that it exists after the byte at its index, i.e.
365 /// haystack[finger_back - 1] is the last byte of the slice we must inspect during
366 /// forward searching (and thus the first byte to be inspected when calling next_back()).
368 /// The character being searched for
371 // safety invariant: `utf8_size` must be less than 5
372 /// The number of bytes `needle` takes up when encoded in utf8.
374 /// A utf8 encoded copy of the `needle`
375 utf8_encoded: [u8; 4],
378 unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
380 fn haystack(&self) -> &'a str {
384 fn next(&mut self) -> SearchStep {
385 let old_finger = self.finger;
386 // SAFETY: 1-4 guarantee safety of `get_unchecked`
387 // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries
388 // (this is invariant)
389 // 2. `self.finger >= 0` since it starts at 0 and only increases
390 // 3. `self.finger < self.finger_back` because otherwise the char `iter`
391 // would return `SearchStep::Done`
392 // 4. `self.finger` comes before the end of the haystack because `self.finger_back`
393 // starts at the end and only decreases
394 let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
395 let mut iter = slice.chars();
396 let old_len = iter.iter.len();
397 if let Some(ch) = iter.next() {
398 // add byte offset of current character
399 // without re-encoding as utf-8
400 self.finger += old_len - iter.iter.len();
401 if ch == self.needle {
402 SearchStep::Match(old_finger, self.finger)
404 SearchStep::Reject(old_finger, self.finger)
411 fn next_match(&mut self) -> Option<(usize, usize)> {
413 // get the haystack after the last character found
414 let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
415 // the last byte of the utf8 encoded needle
416 // SAFETY: we have an invariant that `utf8_size < 5`
417 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
418 if let Some(index) = memchr::memchr(last_byte, bytes) {
419 // The new finger is the index of the byte we found,
420 // plus one, since we memchr'd for the last byte of the character.
422 // Note that this doesn't always give us a finger on a UTF8 boundary.
423 // If we *didn't* find our character
424 // we may have indexed to the non-last byte of a 3-byte or 4-byte character.
425 // We can't just skip to the next valid starting byte because a character like
426 // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find
427 // the second byte when searching for the third.
429 // However, this is totally okay. While we have the invariant that
430 // self.finger is on a UTF8 boundary, this invariant is not relied upon
431 // within this method (it is relied upon in CharSearcher::next()).
433 // We only exit this method when we reach the end of the string, or if we
434 // find something. When we find something the `finger` will be set
435 // to a UTF8 boundary.
436 self.finger += index + 1;
437 if self.finger >= self.utf8_size {
438 let found_char = self.finger - self.utf8_size;
439 if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
440 if slice == &self.utf8_encoded[0..self.utf8_size] {
441 return Some((found_char, self.finger));
446 // found nothing, exit
447 self.finger = self.finger_back;
453 // let next_reject use the default implementation from the Searcher trait
456 unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
458 fn next_back(&mut self) -> SearchStep {
459 let old_finger = self.finger_back;
460 // SAFETY: see the comment for next() above
461 let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
462 let mut iter = slice.chars();
463 let old_len = iter.iter.len();
464 if let Some(ch) = iter.next_back() {
465 // subtract byte offset of current character
466 // without re-encoding as utf-8
467 self.finger_back -= old_len - iter.iter.len();
468 if ch == self.needle {
469 SearchStep::Match(self.finger_back, old_finger)
471 SearchStep::Reject(self.finger_back, old_finger)
478 fn next_match_back(&mut self) -> Option<(usize, usize)> {
479 let haystack = self.haystack.as_bytes();
481 // get the haystack up to but not including the last character searched
482 let bytes = haystack.get(self.finger..self.finger_back)?;
483 // the last byte of the utf8 encoded needle
484 // SAFETY: we have an invariant that `utf8_size < 5`
485 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
486 if let Some(index) = memchr::memrchr(last_byte, bytes) {
487 // we searched a slice that was offset by self.finger,
488 // add self.finger to recoup the original index
489 let index = self.finger + index;
490 // memrchr will return the index of the byte we wish to
491 // find. In case of an ASCII character, this is indeed
492 // were we wish our new finger to be ("after" the found
493 // char in the paradigm of reverse iteration). For
494 // multibyte chars we need to skip down by the number of more
495 // bytes they have than ASCII
496 let shift = self.utf8_size - 1;
498 let found_char = index - shift;
499 if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size)) {
500 if slice == &self.utf8_encoded[0..self.utf8_size] {
501 // move finger to before the character found (i.e., at its start index)
502 self.finger_back = found_char;
503 return Some((self.finger_back, self.finger_back + self.utf8_size));
507 // We can't use finger_back = index - size + 1 here. If we found the last char
508 // of a different-sized character (or the middle byte of a different character)
509 // we need to bump the finger_back down to `index`. This similarly makes
510 // `finger_back` have the potential to no longer be on a boundary,
511 // but this is OK since we only exit this function on a boundary
512 // or when the haystack has been searched completely.
514 // Unlike next_match this does not
515 // have the problem of repeated bytes in utf-8 because
516 // we're searching for the last byte, and we can only have
517 // found the last byte when searching in reverse.
518 self.finger_back = index;
520 self.finger_back = self.finger;
521 // found nothing, exit
527 // let next_reject_back use the default implementation from the Searcher trait
530 impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
532 /// Searches for chars that are equal to a given [`char`].
537 /// assert_eq!("Hello world".find('o'), Some(4));
539 impl<'a> Pattern<'a> for char {
540 type Searcher = CharSearcher<'a>;
543 fn into_searcher(self, haystack: &'a str) -> Self::Searcher {
544 let mut utf8_encoded = [0; 4];
545 let utf8_size = self.encode_utf8(&mut utf8_encoded).len();
549 finger_back: haystack.len(),
557 fn is_contained_in(self, haystack: &'a str) -> bool {
558 if (self as u32) < 128 {
559 haystack.as_bytes().contains(&(self as u8))
561 let mut buffer = [0u8; 4];
562 self.encode_utf8(&mut buffer).is_contained_in(haystack)
567 fn is_prefix_of(self, haystack: &'a str) -> bool {
568 self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
572 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
573 self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack)
577 fn is_suffix_of(self, haystack: &'a str) -> bool
579 Self::Searcher: ReverseSearcher<'a>,
581 self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
585 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
587 Self::Searcher: ReverseSearcher<'a>,
589 self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack)
593 /////////////////////////////////////////////////////////////////////////////
594 // Impl for a MultiCharEq wrapper
595 /////////////////////////////////////////////////////////////////////////////
599 fn matches(&mut self, c: char) -> bool;
602 impl<F> MultiCharEq for F
604 F: FnMut(char) -> bool,
607 fn matches(&mut self, c: char) -> bool {
612 impl<const N: usize> MultiCharEq for [char; N] {
614 fn matches(&mut self, c: char) -> bool {
615 self.iter().any(|&m| m == c)
619 impl<const N: usize> MultiCharEq for &[char; N] {
621 fn matches(&mut self, c: char) -> bool {
622 self.iter().any(|&m| m == c)
626 impl MultiCharEq for &[char] {
628 fn matches(&mut self, c: char) -> bool {
629 self.iter().any(|&m| m == c)
633 struct MultiCharEqPattern<C: MultiCharEq>(C);
635 #[derive(Clone, Debug)]
636 struct MultiCharEqSearcher<'a, C: MultiCharEq> {
639 char_indices: super::CharIndices<'a>,
642 impl<'a, C: MultiCharEq> Pattern<'a> for MultiCharEqPattern<C> {
643 type Searcher = MultiCharEqSearcher<'a, C>;
646 fn into_searcher(self, haystack: &'a str) -> MultiCharEqSearcher<'a, C> {
647 MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
651 unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
653 fn haystack(&self) -> &'a str {
658 fn next(&mut self) -> SearchStep {
659 let s = &mut self.char_indices;
660 // Compare lengths of the internal byte slice iterator
661 // to find length of current char
662 let pre_len = s.iter.iter.len();
663 if let Some((i, c)) = s.next() {
664 let len = s.iter.iter.len();
665 let char_len = pre_len - len;
666 if self.char_eq.matches(c) {
667 return SearchStep::Match(i, i + char_len);
669 return SearchStep::Reject(i, i + char_len);
676 unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
678 fn next_back(&mut self) -> SearchStep {
679 let s = &mut self.char_indices;
680 // Compare lengths of the internal byte slice iterator
681 // to find length of current char
682 let pre_len = s.iter.iter.len();
683 if let Some((i, c)) = s.next_back() {
684 let len = s.iter.iter.len();
685 let char_len = pre_len - len;
686 if self.char_eq.matches(c) {
687 return SearchStep::Match(i, i + char_len);
689 return SearchStep::Reject(i, i + char_len);
696 impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}
698 /////////////////////////////////////////////////////////////////////////////
700 macro_rules! pattern_methods {
701 ($t:ty, $pmap:expr, $smap:expr) => {
705 fn into_searcher(self, haystack: &'a str) -> $t {
706 ($smap)(($pmap)(self).into_searcher(haystack))
710 fn is_contained_in(self, haystack: &'a str) -> bool {
711 ($pmap)(self).is_contained_in(haystack)
715 fn is_prefix_of(self, haystack: &'a str) -> bool {
716 ($pmap)(self).is_prefix_of(haystack)
720 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
721 ($pmap)(self).strip_prefix_of(haystack)
725 fn is_suffix_of(self, haystack: &'a str) -> bool
727 $t: ReverseSearcher<'a>,
729 ($pmap)(self).is_suffix_of(haystack)
733 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
735 $t: ReverseSearcher<'a>,
737 ($pmap)(self).strip_suffix_of(haystack)
742 macro_rules! searcher_methods {
745 fn haystack(&self) -> &'a str {
749 fn next(&mut self) -> SearchStep {
753 fn next_match(&mut self) -> Option<(usize, usize)> {
757 fn next_reject(&mut self) -> Option<(usize, usize)> {
763 fn next_back(&mut self) -> SearchStep {
767 fn next_match_back(&mut self) -> Option<(usize, usize)> {
768 self.0.next_match_back()
771 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
772 self.0.next_reject_back()
777 /// Associated type for `<[char; N] as Pattern<'a>>::Searcher`.
778 #[derive(Clone, Debug)]
779 pub struct CharArraySearcher<'a, const N: usize>(
780 <MultiCharEqPattern<[char; N]> as Pattern<'a>>::Searcher,
783 /// Associated type for `<&[char; N] as Pattern<'a>>::Searcher`.
784 #[derive(Clone, Debug)]
785 pub struct CharArrayRefSearcher<'a, 'b, const N: usize>(
786 <MultiCharEqPattern<&'b [char; N]> as Pattern<'a>>::Searcher,
789 /// Searches for chars that are equal to any of the [`char`]s in the array.
794 /// assert_eq!("Hello world".find(['l', 'l']), Some(2));
795 /// assert_eq!("Hello world".find(['l', 'l']), Some(2));
797 impl<'a, const N: usize> Pattern<'a> for [char; N] {
798 pattern_methods!(CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher);
801 unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> {
802 searcher_methods!(forward);
805 unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> {
806 searcher_methods!(reverse);
809 /// Searches for chars that are equal to any of the [`char`]s in the array.
814 /// assert_eq!("Hello world".find(&['l', 'l']), Some(2));
815 /// assert_eq!("Hello world".find(&['l', 'l']), Some(2));
817 impl<'a, 'b, const N: usize> Pattern<'a> for &'b [char; N] {
818 pattern_methods!(CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher);
821 unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
822 searcher_methods!(forward);
825 unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
826 searcher_methods!(reverse);
829 /////////////////////////////////////////////////////////////////////////////
831 /////////////////////////////////////////////////////////////////////////////
833 // Todo: Change / Remove due to ambiguity in meaning.
835 /// Associated type for `<&[char] as Pattern<'a>>::Searcher`.
836 #[derive(Clone, Debug)]
837 pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern<'a>>::Searcher);
839 unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
840 searcher_methods!(forward);
843 unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
844 searcher_methods!(reverse);
847 impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
849 /// Searches for chars that are equal to any of the [`char`]s in the slice.
854 /// assert_eq!("Hello world".find(&['l', 'l'] as &[_]), Some(2));
855 /// assert_eq!("Hello world".find(&['l', 'l'][..]), Some(2));
857 impl<'a, 'b> Pattern<'a> for &'b [char] {
858 pattern_methods!(CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
861 /////////////////////////////////////////////////////////////////////////////
862 // Impl for F: FnMut(char) -> bool
863 /////////////////////////////////////////////////////////////////////////////
865 /// Associated type for `<F as Pattern<'a>>::Searcher`.
867 pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern<'a>>::Searcher)
869 F: FnMut(char) -> bool;
871 impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
873 F: FnMut(char) -> bool,
875 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
876 f.debug_struct("CharPredicateSearcher")
877 .field("haystack", &self.0.haystack)
878 .field("char_indices", &self.0.char_indices)
882 unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
884 F: FnMut(char) -> bool,
886 searcher_methods!(forward);
889 unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
891 F: FnMut(char) -> bool,
893 searcher_methods!(reverse);
896 impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}
898 /// Searches for [`char`]s that match the given predicate.
903 /// assert_eq!("Hello world".find(char::is_uppercase), Some(0));
904 /// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1));
906 impl<'a, F> Pattern<'a> for F
908 F: FnMut(char) -> bool,
910 pattern_methods!(CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
913 /////////////////////////////////////////////////////////////////////////////
915 /////////////////////////////////////////////////////////////////////////////
917 /// Delegates to the `&str` impl.
918 impl<'a, 'b, 'c> Pattern<'a> for &'c &'b str {
919 pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s);
922 /////////////////////////////////////////////////////////////////////////////
924 /////////////////////////////////////////////////////////////////////////////
926 /// Non-allocating substring search.
928 /// Will handle the pattern `""` as returning empty matches at each character
934 /// assert_eq!("Hello world".find("world"), Some(6));
936 impl<'a, 'b> Pattern<'a> for &'b str {
937 type Searcher = StrSearcher<'a, 'b>;
940 fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> {
941 StrSearcher::new(haystack, self)
944 /// Checks whether the pattern matches at the front of the haystack.
946 fn is_prefix_of(self, haystack: &'a str) -> bool {
947 haystack.as_bytes().starts_with(self.as_bytes())
950 /// Checks whether the pattern matches anywhere in the haystack
952 fn is_contained_in(self, haystack: &'a str) -> bool {
957 match self.len().cmp(&haystack.len()) {
960 return haystack.as_bytes().contains(&self.as_bytes()[0]);
963 #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
964 if self.len() <= 32 {
965 if let Some(result) = simd_contains(self, haystack) {
970 self.into_searcher(haystack).next_match().is_some()
972 _ => self == haystack,
976 /// Removes the pattern from the front of haystack, if it matches.
978 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
979 if self.is_prefix_of(haystack) {
980 // SAFETY: prefix was just verified to exist.
981 unsafe { Some(haystack.get_unchecked(self.as_bytes().len()..)) }
987 /// Checks whether the pattern matches at the back of the haystack.
989 fn is_suffix_of(self, haystack: &'a str) -> bool {
990 haystack.as_bytes().ends_with(self.as_bytes())
993 /// Removes the pattern from the back of haystack, if it matches.
995 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> {
996 if self.is_suffix_of(haystack) {
997 let i = haystack.len() - self.as_bytes().len();
998 // SAFETY: suffix was just verified to exist.
999 unsafe { Some(haystack.get_unchecked(..i)) }
1006 /////////////////////////////////////////////////////////////////////////////
1007 // Two Way substring searcher
1008 /////////////////////////////////////////////////////////////////////////////
1010 #[derive(Clone, Debug)]
1011 /// Associated type for `<&str as Pattern<'a>>::Searcher`.
1012 pub struct StrSearcher<'a, 'b> {
1016 searcher: StrSearcherImpl,
1019 #[derive(Clone, Debug)]
1020 enum StrSearcherImpl {
1022 TwoWay(TwoWaySearcher),
1025 #[derive(Clone, Debug)]
1026 struct EmptyNeedle {
1031 // Needed in case of an empty haystack, see #85462
1035 impl<'a, 'b> StrSearcher<'a, 'b> {
1036 fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
1037 if needle.is_empty() {
1041 searcher: StrSearcherImpl::Empty(EmptyNeedle {
1043 end: haystack.len(),
1053 searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
1062 unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
1064 fn haystack(&self) -> &'a str {
1069 fn next(&mut self) -> SearchStep {
1070 match self.searcher {
1071 StrSearcherImpl::Empty(ref mut searcher) => {
1072 if searcher.is_finished {
1073 return SearchStep::Done;
1075 // empty needle rejects every char and matches every empty string between them
1076 let is_match = searcher.is_match_fw;
1077 searcher.is_match_fw = !searcher.is_match_fw;
1078 let pos = searcher.position;
1079 match self.haystack[pos..].chars().next() {
1080 _ if is_match => SearchStep::Match(pos, pos),
1082 searcher.is_finished = true;
1086 searcher.position += ch.len_utf8();
1087 SearchStep::Reject(pos, searcher.position)
1091 StrSearcherImpl::TwoWay(ref mut searcher) => {
1092 // TwoWaySearcher produces valid *Match* indices that split at char boundaries
1093 // as long as it does correct matching and that haystack and needle are
1095 // *Rejects* from the algorithm can fall on any indices, but we will walk them
1096 // manually to the next character boundary, so that they are utf-8 safe.
1097 if searcher.position == self.haystack.len() {
1098 return SearchStep::Done;
1100 let is_long = searcher.memory == usize::MAX;
1101 match searcher.next::<RejectAndMatch>(
1102 self.haystack.as_bytes(),
1103 self.needle.as_bytes(),
1106 SearchStep::Reject(a, mut b) => {
1107 // skip to next char boundary
1108 while !self.haystack.is_char_boundary(b) {
1111 searcher.position = cmp::max(b, searcher.position);
1112 SearchStep::Reject(a, b)
1114 otherwise => otherwise,
1121 fn next_match(&mut self) -> Option<(usize, usize)> {
1122 match self.searcher {
1123 StrSearcherImpl::Empty(..) => loop {
1125 SearchStep::Match(a, b) => return Some((a, b)),
1126 SearchStep::Done => return None,
1127 SearchStep::Reject(..) => {}
1130 StrSearcherImpl::TwoWay(ref mut searcher) => {
1131 let is_long = searcher.memory == usize::MAX;
1132 // write out `true` and `false` cases to encourage the compiler
1133 // to specialize the two cases separately.
1135 searcher.next::<MatchOnly>(
1136 self.haystack.as_bytes(),
1137 self.needle.as_bytes(),
1141 searcher.next::<MatchOnly>(
1142 self.haystack.as_bytes(),
1143 self.needle.as_bytes(),
1152 unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
1154 fn next_back(&mut self) -> SearchStep {
1155 match self.searcher {
1156 StrSearcherImpl::Empty(ref mut searcher) => {
1157 if searcher.is_finished {
1158 return SearchStep::Done;
1160 let is_match = searcher.is_match_bw;
1161 searcher.is_match_bw = !searcher.is_match_bw;
1162 let end = searcher.end;
1163 match self.haystack[..end].chars().next_back() {
1164 _ if is_match => SearchStep::Match(end, end),
1166 searcher.is_finished = true;
1170 searcher.end -= ch.len_utf8();
1171 SearchStep::Reject(searcher.end, end)
1175 StrSearcherImpl::TwoWay(ref mut searcher) => {
1176 if searcher.end == 0 {
1177 return SearchStep::Done;
1179 let is_long = searcher.memory == usize::MAX;
1180 match searcher.next_back::<RejectAndMatch>(
1181 self.haystack.as_bytes(),
1182 self.needle.as_bytes(),
1185 SearchStep::Reject(mut a, b) => {
1186 // skip to next char boundary
1187 while !self.haystack.is_char_boundary(a) {
1190 searcher.end = cmp::min(a, searcher.end);
1191 SearchStep::Reject(a, b)
1193 otherwise => otherwise,
1200 fn next_match_back(&mut self) -> Option<(usize, usize)> {
1201 match self.searcher {
1202 StrSearcherImpl::Empty(..) => loop {
1203 match self.next_back() {
1204 SearchStep::Match(a, b) => return Some((a, b)),
1205 SearchStep::Done => return None,
1206 SearchStep::Reject(..) => {}
1209 StrSearcherImpl::TwoWay(ref mut searcher) => {
1210 let is_long = searcher.memory == usize::MAX;
1211 // write out `true` and `false`, like `next_match`
1213 searcher.next_back::<MatchOnly>(
1214 self.haystack.as_bytes(),
1215 self.needle.as_bytes(),
1219 searcher.next_back::<MatchOnly>(
1220 self.haystack.as_bytes(),
1221 self.needle.as_bytes(),
1230 /// The internal state of the two-way substring search algorithm.
1231 #[derive(Clone, Debug)]
1232 struct TwoWaySearcher {
1234 /// critical factorization index
1236 /// critical factorization index for reversed needle
1237 crit_pos_back: usize,
1239 /// `byteset` is an extension (not part of the two way algorithm);
1240 /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
1241 /// to a (byte & 63) == j present in the needle.
1247 /// index into needle before which we have already matched
1249 /// index into needle after which we have already matched
1254 This is the Two-Way search algorithm, which was introduced in the paper:
1255 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
1257 Here's some background information.
1259 A *word* is a string of symbols. The *length* of a word should be a familiar
1260 notion, and here we denote it for any word x by |x|.
1261 (We also allow for the possibility of the *empty word*, a word of length zero).
1263 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
1264 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
1265 For example, both 1 and 2 are periods for the string "aa". As another example,
1266 the only period of the string "abcd" is 4.
1268 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
1269 This is always well-defined since every non-empty word x has at least one period,
1270 |x|. We sometimes call this *the period* of x.
1272 If u, v and x are words such that x = uv, where uv is the concatenation of u and
1273 v, then we say that (u, v) is a *factorization* of x.
1275 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
1276 that both of the following hold
1278 - either w is a suffix of u or u is a suffix of w
1279 - either w is a prefix of v or v is a prefix of w
1281 then w is said to be a *repetition* for the factorization (u, v).
1283 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
1286 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
1287 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
1288 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
1289 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
1291 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
1292 so every factorization has at least one repetition.
1294 If x is a string and (u, v) is a factorization for x, then a *local period* for
1295 (u, v) is an integer r such that there is some word w such that |w| = r and w is
1296 a repetition for (u, v).
1298 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
1299 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
1300 is well-defined (because each non-empty word has at least one factorization, as
1303 It can be proven that the following is an equivalent definition of a local period
1304 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
1305 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
1306 defined. (i.e., i > 0 and i + r < |x|).
1308 Using the above reformulation, it is easy to prove that
1310 1 <= local_period(u, v) <= period(uv)
1312 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
1313 *critical factorization*.
1315 The algorithm hinges on the following theorem, which is stated without proof:
1317 **Critical Factorization Theorem** Any word x has at least one critical
1318 factorization (u, v) such that |u| < period(x).
1320 The purpose of maximal_suffix is to find such a critical factorization.
1322 If the period is short, compute another factorization x = u' v' to use
1323 for reverse search, chosen instead so that |v'| < period(x).
1326 impl TwoWaySearcher {
1327 fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
1328 let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
1329 let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);
1331 let (crit_pos, period) = if crit_pos_false > crit_pos_true {
1332 (crit_pos_false, period_false)
1334 (crit_pos_true, period_true)
1337 // A particularly readable explanation of what's going on here can be found
1338 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
1339 // see the code for "Algorithm CP" on p. 323.
1341 // What's going on is we have some critical factorization (u, v) of the
1342 // needle, and we want to determine whether u is a suffix of
1343 // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
1344 // "Algorithm CP2", which is optimized for when the period of the needle
1346 if needle[..crit_pos] == needle[period..period + crit_pos] {
1347 // short period case -- the period is exact
1348 // compute a separate critical factorization for the reversed needle
1349 // x = u' v' where |v'| < period(x).
1351 // This is sped up by the period being known already.
1352 // Note that a case like x = "acba" may be factored exactly forwards
1353 // (crit_pos = 1, period = 3) while being factored with approximate
1354 // period in reverse (crit_pos = 2, period = 2). We use the given
1355 // reverse factorization but keep the exact period.
1356 let crit_pos_back = needle.len()
1358 TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
1359 TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
1366 byteset: Self::byteset_create(&needle[..period]),
1371 memory_back: needle.len(),
1374 // long period case -- we have an approximation to the actual period,
1375 // and don't use memorization.
1377 // Approximate the period by lower bound max(|u|, |v|) + 1.
1378 // The critical factorization is efficient to use for both forward and
1383 crit_pos_back: crit_pos,
1384 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
1385 byteset: Self::byteset_create(needle),
1389 memory: usize::MAX, // Dummy value to signify that the period is long
1390 memory_back: usize::MAX,
1396 fn byteset_create(bytes: &[u8]) -> u64 {
1397 bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
1401 fn byteset_contains(&self, byte: u8) -> bool {
1402 (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
1405 // One of the main ideas of Two-Way is that we factorize the needle into
1406 // two halves, (u, v), and begin trying to find v in the haystack by scanning
1407 // left to right. If v matches, we try to match u by scanning right to left.
1408 // How far we can jump when we encounter a mismatch is all based on the fact
1409 // that (u, v) is a critical factorization for the needle.
1411 fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1415 // `next()` uses `self.position` as its cursor
1416 let old_pos = self.position;
1417 let needle_last = needle.len() - 1;
1419 // Check that we have room to search in
1420 // position + needle_last can not overflow if we assume slices
1421 // are bounded by isize's range.
1422 let tail_byte = match haystack.get(self.position + needle_last) {
1425 self.position = haystack.len();
1426 return S::rejecting(old_pos, self.position);
1430 if S::use_early_reject() && old_pos != self.position {
1431 return S::rejecting(old_pos, self.position);
1434 // Quickly skip by large portions unrelated to our substring
1435 if !self.byteset_contains(tail_byte) {
1436 self.position += needle.len();
1443 // See if the right part of the needle matches
1445 if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) };
1446 for i in start..needle.len() {
1447 if needle[i] != haystack[self.position + i] {
1448 self.position += i - self.crit_pos + 1;
1456 // See if the left part of the needle matches
1457 let start = if long_period { 0 } else { self.memory };
1458 for i in (start..self.crit_pos).rev() {
1459 if needle[i] != haystack[self.position + i] {
1460 self.position += self.period;
1462 self.memory = needle.len() - self.period;
1468 // We have found a match!
1469 let match_pos = self.position;
1471 // Note: add self.period instead of needle.len() to have overlapping matches
1472 self.position += needle.len();
1474 self.memory = 0; // set to needle.len() - self.period for overlapping matches
1477 return S::matching(match_pos, match_pos + needle.len());
1481 // Follows the ideas in `next()`.
1483 // The definitions are symmetrical, with period(x) = period(reverse(x))
1484 // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
1485 // is a critical factorization, so is (reverse(v), reverse(u)).
1487 // For the reverse case we have computed a critical factorization x = u' v'
1488 // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
1489 // thus |v'| < period(x) for the reverse.
1491 // To search in reverse through the haystack, we search forward through
1492 // a reversed haystack with a reversed needle, matching first u' and then v'.
1494 fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1498 // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1500 let old_end = self.end;
1502 // Check that we have room to search in
1503 // end - needle.len() will wrap around when there is no more room,
1504 // but due to slice length limits it can never wrap all the way back
1505 // into the length of haystack.
1506 let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
1510 return S::rejecting(0, old_end);
1514 if S::use_early_reject() && old_end != self.end {
1515 return S::rejecting(self.end, old_end);
1518 // Quickly skip by large portions unrelated to our substring
1519 if !self.byteset_contains(front_byte) {
1520 self.end -= needle.len();
1522 self.memory_back = needle.len();
1527 // See if the left part of the needle matches
1528 let crit = if long_period {
1531 cmp::min(self.crit_pos_back, self.memory_back)
1533 for i in (0..crit).rev() {
1534 if needle[i] != haystack[self.end - needle.len() + i] {
1535 self.end -= self.crit_pos_back - i;
1537 self.memory_back = needle.len();
1543 // See if the right part of the needle matches
1544 let needle_end = if long_period { needle.len() } else { self.memory_back };
1545 for i in self.crit_pos_back..needle_end {
1546 if needle[i] != haystack[self.end - needle.len() + i] {
1547 self.end -= self.period;
1549 self.memory_back = self.period;
1555 // We have found a match!
1556 let match_pos = self.end - needle.len();
1557 // Note: sub self.period instead of needle.len() to have overlapping matches
1558 self.end -= needle.len();
1560 self.memory_back = needle.len();
1563 return S::matching(match_pos, match_pos + needle.len());
1567 // Compute the maximal suffix of `arr`.
1569 // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1571 // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1574 // `order_greater` determines if lexical order is `<` or `>`. Both
1575 // orders must be computed -- the ordering with the largest `i` gives
1576 // a critical factorization.
1578 // For long period cases, the resulting period is not exact (it is too short).
1580 fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
1581 let mut left = 0; // Corresponds to i in the paper
1582 let mut right = 1; // Corresponds to j in the paper
1583 let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1584 // to match 0-based indexing.
1585 let mut period = 1; // Corresponds to p in the paper
1587 while let Some(&a) = arr.get(right + offset) {
1588 // `left` will be inbounds when `right` is.
1589 let b = arr[left + offset];
1590 if (a < b && !order_greater) || (a > b && order_greater) {
1591 // Suffix is smaller, period is entire prefix so far.
1592 right += offset + 1;
1594 period = right - left;
1596 // Advance through repetition of the current period.
1597 if offset + 1 == period {
1598 right += offset + 1;
1604 // Suffix is larger, start over from current location.
1614 // Compute the maximal suffix of the reverse of `arr`.
1616 // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1618 // Returns `i` where `i` is the starting index of v', from the back;
1619 // returns immediately when a period of `known_period` is reached.
1621 // `order_greater` determines if lexical order is `<` or `>`. Both
1622 // orders must be computed -- the ordering with the largest `i` gives
1623 // a critical factorization.
1625 // For long period cases, the resulting period is not exact (it is too short).
1626 fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> 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
1634 while right + offset < n {
1635 let a = arr[n - (1 + right + offset)];
1636 let b = arr[n - (1 + left + offset)];
1637 if (a < b && !order_greater) || (a > b && order_greater) {
1638 // Suffix is smaller, period is entire prefix so far.
1639 right += offset + 1;
1641 period = right - left;
1643 // Advance through repetition of the current period.
1644 if offset + 1 == period {
1645 right += offset + 1;
1651 // Suffix is larger, start over from current location.
1657 if period == known_period {
1661 debug_assert!(period <= known_period);
1666 // TwoWayStrategy allows the algorithm to either skip non-matches as quickly
1667 // as possible, or to work in a mode where it emits Rejects relatively quickly.
1668 trait TwoWayStrategy {
1670 fn use_early_reject() -> bool;
1671 fn rejecting(a: usize, b: usize) -> Self::Output;
1672 fn matching(a: usize, b: usize) -> Self::Output;
1675 /// Skip to match intervals as quickly as possible
1678 impl TwoWayStrategy for MatchOnly {
1679 type Output = Option<(usize, usize)>;
1682 fn use_early_reject() -> bool {
1686 fn rejecting(_a: usize, _b: usize) -> Self::Output {
1690 fn matching(a: usize, b: usize) -> Self::Output {
1695 /// Emit Rejects regularly
1696 enum RejectAndMatch {}
1698 impl TwoWayStrategy for RejectAndMatch {
1699 type Output = SearchStep;
1702 fn use_early_reject() -> bool {
1706 fn rejecting(a: usize, b: usize) -> Self::Output {
1707 SearchStep::Reject(a, b)
1710 fn matching(a: usize, b: usize) -> Self::Output {
1711 SearchStep::Match(a, b)
1715 /// SIMD search for short needles based on
1716 /// Wojciech Muła's "SIMD-friendly algorithms for substring searching"[0]
1718 /// It skips ahead by the vector width on each iteration (rather than the needle length as two-way
1719 /// does) by probing the first and last byte of the needle for the whole vector width
1720 /// and only doing full needle comparisons when the vectorized probe indicated potential matches.
1722 /// Since the x86_64 baseline only offers SSE2 we only use u8x16 here.
1723 /// If we ever ship std with for x86-64-v3 or adapt this for other platforms then wider vectors
1724 /// should be evaluated.
1726 /// For haystacks smaller than vector-size + needle length it falls back to
1727 /// a naive O(n*m) search so this implementation should not be called on larger needles.
1729 /// [0]: http://0x80.pl/articles/simd-strfind.html#sse-avx2
1730 #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
1732 fn simd_contains(needle: &str, haystack: &str) -> Option<bool> {
1733 let needle = needle.as_bytes();
1734 let haystack = haystack.as_bytes();
1736 debug_assert!(needle.len() > 1);
1738 use crate::ops::BitAnd;
1739 use crate::simd::mask8x16 as Mask;
1740 use crate::simd::u8x16 as Block;
1741 use crate::simd::{SimdPartialEq, ToBitMask};
1743 let first_probe = needle[0];
1744 let last_byte_offset = needle.len() - 1;
1746 // the offset used for the 2nd vector
1747 let second_probe_offset = if needle.len() == 2 {
1748 // never bail out on len=2 needles because the probes will fully cover them and have
1749 // no degenerate cases.
1752 // try a few bytes in case first and last byte of the needle are the same
1753 let Some(second_probe_offset) = (needle.len().saturating_sub(4)..needle.len()).rfind(|&idx| needle[idx] != first_probe) else {
1754 // fall back to other search methods if we can't find any different bytes
1755 // since we could otherwise hit some degenerate cases
1761 // do a naive search if the haystack is too small to fit
1762 if haystack.len() < Block::LANES + last_byte_offset {
1763 return Some(haystack.windows(needle.len()).any(|c| c == needle));
1766 let first_probe: Block = Block::splat(first_probe);
1767 let second_probe: Block = Block::splat(needle[second_probe_offset]);
1768 // first byte are already checked by the outer loop. to verify a match only the
1769 // remainder has to be compared.
1770 let trimmed_needle = &needle[1..];
1772 // this #[cold] is load-bearing, benchmark before removing it...
1773 let check_mask = #[cold]
1774 |idx, mask: u16, skip: bool| -> bool {
1779 // and so is this. optimizations are weird.
1780 let mut mask = mask;
1783 let trailing = mask.trailing_zeros();
1784 let offset = idx + trailing as usize + 1;
1785 // SAFETY: mask is between 0 and 15 trailing zeroes, we skip one additional byte that was already compared
1786 // and then take trimmed_needle.len() bytes. This is within the bounds defined by the outer loop
1788 let sub = haystack.get_unchecked(offset..).get_unchecked(..trimmed_needle.len());
1789 if small_slice_eq(sub, trimmed_needle) {
1793 mask &= !(1 << trailing);
1798 let test_chunk = |idx| -> u16 {
1799 // SAFETY: this requires at least LANES bytes being readable at idx
1800 // that is ensured by the loop ranges (see comments below)
1801 let a: Block = unsafe { haystack.as_ptr().add(idx).cast::<Block>().read_unaligned() };
1802 // SAFETY: this requires LANES + block_offset bytes being readable at idx
1803 let b: Block = unsafe {
1804 haystack.as_ptr().add(idx).add(second_probe_offset).cast::<Block>().read_unaligned()
1806 let eq_first: Mask = a.simd_eq(first_probe);
1807 let eq_last: Mask = b.simd_eq(second_probe);
1808 let both = eq_first.bitand(eq_last);
1809 let mask = both.to_bitmask();
1815 let mut result = false;
1816 // The loop condition must ensure that there's enough headroom to read LANE bytes,
1817 // and not only at the current index but also at the index shifted by block_offset
1818 const UNROLL: usize = 4;
1819 while i + last_byte_offset + UNROLL * Block::LANES < haystack.len() && !result {
1820 let mut masks = [0u16; UNROLL];
1821 for j in 0..UNROLL {
1822 masks[j] = test_chunk(i + j * Block::LANES);
1824 for j in 0..UNROLL {
1825 let mask = masks[j];
1827 result |= check_mask(i + j * Block::LANES, mask, result);
1830 i += UNROLL * Block::LANES;
1832 while i + last_byte_offset + Block::LANES < haystack.len() && !result {
1833 let mask = test_chunk(i);
1835 result |= check_mask(i, mask, result);
1840 // Process the tail that didn't fit into LANES-sized steps.
1841 // This simply repeats the same procedure but as right-aligned chunk instead
1842 // of a left-aligned one. The last byte must be exactly flush with the string end so
1843 // we don't miss a single byte or read out of bounds.
1844 let i = haystack.len() - last_byte_offset - Block::LANES;
1845 let mask = test_chunk(i);
1847 result |= check_mask(i, mask, result);
1853 /// Compares short slices for equality.
1855 /// It avoids a call to libc's memcmp which is faster on long slices
1856 /// due to SIMD optimizations but it incurs a function call overhead.
1860 /// Both slices must have the same length.
1861 #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] // only called on x86
1863 unsafe fn small_slice_eq(x: &[u8], y: &[u8]) -> bool {
1864 debug_assert_eq!(x.len(), y.len());
1865 // This function is adapted from
1866 // https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memmem/util.rs#L32
1868 // If we don't have enough bytes to do 4-byte at a time loads, then
1869 // fall back to the naive slow version.
1871 // Potential alternative: We could do a copy_nonoverlapping combined with a mask instead
1872 // of a loop. Benchmark it.
1874 for (&b1, &b2) in x.iter().zip(y) {
1881 // When we have 4 or more bytes to compare, then proceed in chunks of 4 at
1882 // a time using unaligned loads.
1884 // Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is
1885 // that this particular version of memcmp is likely to be called with tiny
1886 // needles. That means that if we do 8 byte loads, then a higher proportion
1887 // of memcmp calls will use the slower variant above. With that said, this
1888 // is a hypothesis and is only loosely supported by benchmarks. There's
1889 // likely some improvement that could be made here. The main thing here
1890 // though is to optimize for latency, not throughput.
1892 // SAFETY: Via the conditional above, we know that both `px` and `py`
1893 // have the same length, so `px < pxend` implies that `py < pyend`.
1894 // Thus, derefencing both `px` and `py` in the loop below is safe.
1896 // Moreover, we set `pxend` and `pyend` to be 4 bytes before the actual
1897 // end of of `px` and `py`. Thus, the final dereference outside of the
1898 // loop is guaranteed to be valid. (The final comparison will overlap with
1899 // the last comparison done in the loop for lengths that aren't multiples
1902 // Finally, we needn't worry about alignment here, since we do unaligned
1905 let (mut px, mut py) = (x.as_ptr(), y.as_ptr());
1906 let (pxend, pyend) = (px.add(x.len() - 4), py.add(y.len() - 4));
1908 let vx = (px as *const u32).read_unaligned();
1909 let vy = (py as *const u32).read_unaligned();
1916 let vx = (pxend as *const u32).read_unaligned();
1917 let vy = (pyend as *const u32).read_unaligned();