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",
43 use crate::slice::memchr;
49 /// A `Pattern<'a>` expresses that the implementing type
50 /// can be used as a string pattern for searching in a [`&'a str`][str].
52 /// For example, both `'a'` and `"aa"` are patterns that
53 /// would match at index `1` in the string `"baaaab"`.
55 /// The trait itself acts as a builder for an associated
56 /// [`Searcher`] type, which does the actual work of finding
57 /// occurrences of the pattern in a string.
59 /// Depending on the type of the pattern, the behaviour of methods like
60 /// [`str::find`] and [`str::contains`] can change. The table below describes
61 /// some of those behaviours.
63 /// | Pattern type | Match condition |
64 /// |--------------------------|-------------------------------------------|
65 /// | `&str` | is substring |
66 /// | `char` | is contained in string |
67 /// | `&[char]` | any char in slice is contained in string |
68 /// | `F: FnMut(char) -> bool` | `F` returns `true` for a char in string |
69 /// | `&&str` | is substring |
70 /// | `&String` | is substring |
76 /// assert_eq!("abaaa".find("ba"), Some(1));
77 /// assert_eq!("abaaa".find("bac"), None);
80 /// assert_eq!("abaaa".find('a'), Some(0));
81 /// assert_eq!("abaaa".find('b'), Some(1));
82 /// assert_eq!("abaaa".find('c'), None);
85 /// assert_eq!("ab".find(&['b', 'a']), Some(0));
86 /// assert_eq!("abaaa".find(&['a', 'z']), Some(0));
87 /// assert_eq!("abaaa".find(&['c', 'd']), None);
90 /// assert_eq!("ab".find(&['b', 'a'][..]), Some(0));
91 /// assert_eq!("abaaa".find(&['a', 'z'][..]), Some(0));
92 /// assert_eq!("abaaa".find(&['c', 'd'][..]), None);
94 /// // FnMut(char) -> bool
95 /// assert_eq!("abcdef_z".find(|ch| ch > 'd' && ch < 'y'), Some(4));
96 /// assert_eq!("abcddd_z".find(|ch| ch > 'd' && ch < 'y'), None);
98 pub trait Pattern<'a>: Sized {
99 /// Associated searcher for this pattern
100 type Searcher: Searcher<'a>;
102 /// Constructs the associated searcher from
103 /// `self` and the `haystack` to search in.
104 fn into_searcher(self, haystack: &'a str) -> Self::Searcher;
106 /// Checks whether the pattern matches anywhere in the haystack
108 fn is_contained_in(self, haystack: &'a str) -> bool {
109 self.into_searcher(haystack).next_match().is_some()
112 /// Checks whether the pattern matches at the front of the haystack
114 fn is_prefix_of(self, haystack: &'a str) -> bool {
115 matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
118 /// Checks whether the pattern matches at the back of the haystack
120 fn is_suffix_of(self, haystack: &'a str) -> bool
122 Self::Searcher: ReverseSearcher<'a>,
124 matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
127 /// Removes the pattern from the front of haystack, if it matches.
129 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
130 if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() {
133 "The first search step from Searcher \
134 must include the first character"
136 // SAFETY: `Searcher` is known to return valid indices.
137 unsafe { Some(haystack.get_unchecked(len..)) }
143 /// Removes the pattern from the back of haystack, if it matches.
145 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
147 Self::Searcher: ReverseSearcher<'a>,
149 if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() {
153 "The first search step from ReverseSearcher \
154 must include the last character"
156 // SAFETY: `Searcher` is known to return valid indices.
157 unsafe { Some(haystack.get_unchecked(..start)) }
166 /// Result of calling [`Searcher::next()`] or [`ReverseSearcher::next_back()`].
167 #[derive(Copy, Clone, Eq, PartialEq, Debug)]
168 pub enum SearchStep {
169 /// Expresses that a match of the pattern has been found at
170 /// `haystack[a..b]`.
172 /// Expresses that `haystack[a..b]` has been rejected as a possible match
175 /// Note that there might be more than one `Reject` between two `Match`es,
176 /// there is no requirement for them to be combined into one.
177 Reject(usize, usize),
178 /// Expresses that every byte of the haystack has been visited, ending
183 /// A searcher for a string pattern.
185 /// This trait provides methods for searching for non-overlapping
186 /// matches of a pattern starting from the front (left) of a string.
188 /// It will be implemented by associated `Searcher`
189 /// types of the [`Pattern`] trait.
191 /// The trait is marked unsafe because the indices returned by the
192 /// [`next()`][Searcher::next] methods are required to lie on valid utf8
193 /// boundaries in the haystack. This enables consumers of this trait to
194 /// slice the haystack without additional runtime checks.
195 pub unsafe trait Searcher<'a> {
196 /// Getter for the underlying string to be searched in
198 /// Will always return the same [`&str`][str].
199 fn haystack(&self) -> &'a str;
201 /// Performs the next search step starting from the front.
203 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches
205 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` can
206 /// not match the pattern, even partially.
207 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack has
210 /// The stream of [`Match`][SearchStep::Match] and
211 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
212 /// will contain index ranges that are adjacent, non-overlapping,
213 /// covering the whole haystack, and laying on utf8 boundaries.
215 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
216 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
217 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
219 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
220 /// might produce the stream
221 /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
222 fn next(&mut self) -> SearchStep;
224 /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next].
226 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
227 /// of this and [`next_reject`][Searcher::next_reject] will overlap. This will return
228 /// `(start_match, end_match)`, where start_match is the index of where
229 /// the match begins, and end_match is the index after the end of the match.
231 fn next_match(&mut self) -> Option<(usize, usize)> {
234 SearchStep::Match(a, b) => return Some((a, b)),
235 SearchStep::Done => return None,
241 /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next]
242 /// and [`next_match()`][Searcher::next_match].
244 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
245 /// of this and [`next_match`][Searcher::next_match] will overlap.
247 fn next_reject(&mut self) -> Option<(usize, usize)> {
250 SearchStep::Reject(a, b) => return Some((a, b)),
251 SearchStep::Done => return None,
258 /// A reverse searcher for a string pattern.
260 /// This trait provides methods for searching for non-overlapping
261 /// matches of a pattern starting from the back (right) of a string.
263 /// It will be implemented by associated [`Searcher`]
264 /// types of the [`Pattern`] trait if the pattern supports searching
265 /// for it from the back.
267 /// The index ranges returned by this trait are not required
268 /// to exactly match those of the forward search in reverse.
270 /// For the reason why this trait is marked unsafe, see them
271 /// parent trait [`Searcher`].
272 pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
273 /// Performs the next search step starting from the back.
275 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]`
276 /// matches the pattern.
277 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]`
278 /// can not match the pattern, even partially.
279 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack
282 /// The stream of [`Match`][SearchStep::Match] and
283 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
284 /// will contain index ranges that are adjacent, non-overlapping,
285 /// covering the whole haystack, and laying on utf8 boundaries.
287 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
288 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
289 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
291 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
292 /// might produce the stream
293 /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`.
294 fn next_back(&mut self) -> SearchStep;
296 /// Finds the next [`Match`][SearchStep::Match] result.
297 /// See [`next_back()`][ReverseSearcher::next_back].
299 fn next_match_back(&mut self) -> Option<(usize, usize)> {
301 match self.next_back() {
302 SearchStep::Match(a, b) => return Some((a, b)),
303 SearchStep::Done => return None,
309 /// Finds the next [`Reject`][SearchStep::Reject] result.
310 /// See [`next_back()`][ReverseSearcher::next_back].
312 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
314 match self.next_back() {
315 SearchStep::Reject(a, b) => return Some((a, b)),
316 SearchStep::Done => return None,
323 /// A marker trait to express that a [`ReverseSearcher`]
324 /// can be used for a [`DoubleEndedIterator`] implementation.
326 /// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need
327 /// to follow these conditions:
329 /// - All results of `next()` need to be identical
330 /// to the results of `next_back()` in reverse order.
331 /// - `next()` and `next_back()` need to behave as
332 /// the two ends of a range of values, that is they
333 /// can not "walk past each other".
337 /// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
338 /// [`char`] only requires looking at one at a time, which behaves the same
341 /// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
342 /// the pattern `"aa"` in the haystack `"aaa"` matches as either
343 /// `"[aa]a"` or `"a[aa]"`, depending from which side it is searched.
344 pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
346 /////////////////////////////////////////////////////////////////////////////
348 /////////////////////////////////////////////////////////////////////////////
350 /// Associated type for `<char as Pattern<'a>>::Searcher`.
351 #[derive(Clone, Debug)]
352 pub struct CharSearcher<'a> {
354 // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack`
355 // This invariant can be broken *within* next_match and next_match_back, however
356 // they must exit with fingers on valid code point boundaries.
357 /// `finger` is the current byte index of the forward search.
358 /// Imagine that it exists before the byte at its index, i.e.
359 /// `haystack[finger]` is the first byte of the slice we must inspect during
360 /// forward searching
362 /// `finger_back` is the current byte index of the reverse search.
363 /// Imagine that it exists after the byte at its index, i.e.
364 /// haystack[finger_back - 1] is the last byte of the slice we must inspect during
365 /// forward searching (and thus the first byte to be inspected when calling next_back()).
367 /// The character being searched for
370 // safety invariant: `utf8_size` must be less than 5
371 /// The number of bytes `needle` takes up when encoded in utf8.
373 /// A utf8 encoded copy of the `needle`
374 utf8_encoded: [u8; 4],
377 unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
379 fn haystack(&self) -> &'a str {
383 fn next(&mut self) -> SearchStep {
384 let old_finger = self.finger;
385 // SAFETY: 1-4 guarantee safety of `get_unchecked`
386 // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries
387 // (this is invariant)
388 // 2. `self.finger >= 0` since it starts at 0 and only increases
389 // 3. `self.finger < self.finger_back` because otherwise the char `iter`
390 // would return `SearchStep::Done`
391 // 4. `self.finger` comes before the end of the haystack because `self.finger_back`
392 // starts at the end and only decreases
393 let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
394 let mut iter = slice.chars();
395 let old_len = iter.iter.len();
396 if let Some(ch) = iter.next() {
397 // add byte offset of current character
398 // without re-encoding as utf-8
399 self.finger += old_len - iter.iter.len();
400 if ch == self.needle {
401 SearchStep::Match(old_finger, self.finger)
403 SearchStep::Reject(old_finger, self.finger)
410 fn next_match(&mut self) -> Option<(usize, usize)> {
412 // get the haystack after the last character found
413 let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
414 // the last byte of the utf8 encoded needle
415 // SAFETY: we have an invariant that `utf8_size < 5`
416 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
417 if let Some(index) = memchr::memchr(last_byte, bytes) {
418 // The new finger is the index of the byte we found,
419 // plus one, since we memchr'd for the last byte of the character.
421 // Note that this doesn't always give us a finger on a UTF8 boundary.
422 // If we *didn't* find our character
423 // we may have indexed to the non-last byte of a 3-byte or 4-byte character.
424 // We can't just skip to the next valid starting byte because a character like
425 // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find
426 // the second byte when searching for the third.
428 // However, this is totally okay. While we have the invariant that
429 // self.finger is on a UTF8 boundary, this invariant is not relied upon
430 // within this method (it is relied upon in CharSearcher::next()).
432 // We only exit this method when we reach the end of the string, or if we
433 // find something. When we find something the `finger` will be set
434 // to a UTF8 boundary.
435 self.finger += index + 1;
436 if self.finger >= self.utf8_size {
437 let found_char = self.finger - self.utf8_size;
438 if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
439 if slice == &self.utf8_encoded[0..self.utf8_size] {
440 return Some((found_char, self.finger));
445 // found nothing, exit
446 self.finger = self.finger_back;
452 // let next_reject use the default implementation from the Searcher trait
455 unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
457 fn next_back(&mut self) -> SearchStep {
458 let old_finger = self.finger_back;
459 // SAFETY: see the comment for next() above
460 let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
461 let mut iter = slice.chars();
462 let old_len = iter.iter.len();
463 if let Some(ch) = iter.next_back() {
464 // subtract byte offset of current character
465 // without re-encoding as utf-8
466 self.finger_back -= old_len - iter.iter.len();
467 if ch == self.needle {
468 SearchStep::Match(self.finger_back, old_finger)
470 SearchStep::Reject(self.finger_back, old_finger)
477 fn next_match_back(&mut self) -> Option<(usize, usize)> {
478 let haystack = self.haystack.as_bytes();
480 // get the haystack up to but not including the last character searched
481 let bytes = haystack.get(self.finger..self.finger_back)?;
482 // the last byte of the utf8 encoded needle
483 // SAFETY: we have an invariant that `utf8_size < 5`
484 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
485 if let Some(index) = memchr::memrchr(last_byte, bytes) {
486 // we searched a slice that was offset by self.finger,
487 // add self.finger to recoup the original index
488 let index = self.finger + index;
489 // memrchr will return the index of the byte we wish to
490 // find. In case of an ASCII character, this is indeed
491 // were we wish our new finger to be ("after" the found
492 // char in the paradigm of reverse iteration). For
493 // multibyte chars we need to skip down by the number of more
494 // bytes they have than ASCII
495 let shift = self.utf8_size - 1;
497 let found_char = index - shift;
498 if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size)) {
499 if slice == &self.utf8_encoded[0..self.utf8_size] {
500 // move finger to before the character found (i.e., at its start index)
501 self.finger_back = found_char;
502 return Some((self.finger_back, self.finger_back + self.utf8_size));
506 // We can't use finger_back = index - size + 1 here. If we found the last char
507 // of a different-sized character (or the middle byte of a different character)
508 // we need to bump the finger_back down to `index`. This similarly makes
509 // `finger_back` have the potential to no longer be on a boundary,
510 // but this is OK since we only exit this function on a boundary
511 // or when the haystack has been searched completely.
513 // Unlike next_match this does not
514 // have the problem of repeated bytes in utf-8 because
515 // we're searching for the last byte, and we can only have
516 // found the last byte when searching in reverse.
517 self.finger_back = index;
519 self.finger_back = self.finger;
520 // found nothing, exit
526 // let next_reject_back use the default implementation from the Searcher trait
529 impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
531 /// Searches for chars that are equal to a given [`char`].
536 /// assert_eq!("Hello world".find('o'), Some(4));
538 impl<'a> Pattern<'a> for char {
539 type Searcher = CharSearcher<'a>;
542 fn into_searcher(self, haystack: &'a str) -> Self::Searcher {
543 let mut utf8_encoded = [0; 4];
544 let utf8_size = self.encode_utf8(&mut utf8_encoded).len();
548 finger_back: haystack.len(),
556 fn is_contained_in(self, haystack: &'a str) -> bool {
557 if (self as u32) < 128 {
558 haystack.as_bytes().contains(&(self as u8))
560 let mut buffer = [0u8; 4];
561 self.encode_utf8(&mut buffer).is_contained_in(haystack)
566 fn is_prefix_of(self, haystack: &'a str) -> bool {
567 self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
571 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
572 self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack)
576 fn is_suffix_of(self, haystack: &'a str) -> bool
578 Self::Searcher: ReverseSearcher<'a>,
580 self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
584 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
586 Self::Searcher: ReverseSearcher<'a>,
588 self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack)
592 /////////////////////////////////////////////////////////////////////////////
593 // Impl for a MultiCharEq wrapper
594 /////////////////////////////////////////////////////////////////////////////
598 fn matches(&mut self, c: char) -> bool;
601 impl<F> MultiCharEq for F
603 F: FnMut(char) -> bool,
606 fn matches(&mut self, c: char) -> bool {
611 impl<const N: usize> MultiCharEq for [char; N] {
613 fn matches(&mut self, c: char) -> bool {
614 self.iter().any(|&m| m == c)
618 impl<const N: usize> MultiCharEq for &[char; N] {
620 fn matches(&mut self, c: char) -> bool {
621 self.iter().any(|&m| m == c)
625 impl MultiCharEq for &[char] {
627 fn matches(&mut self, c: char) -> bool {
628 self.iter().any(|&m| m == c)
632 struct MultiCharEqPattern<C: MultiCharEq>(C);
634 #[derive(Clone, Debug)]
635 struct MultiCharEqSearcher<'a, C: MultiCharEq> {
638 char_indices: super::CharIndices<'a>,
641 impl<'a, C: MultiCharEq> Pattern<'a> for MultiCharEqPattern<C> {
642 type Searcher = MultiCharEqSearcher<'a, C>;
645 fn into_searcher(self, haystack: &'a str) -> MultiCharEqSearcher<'a, C> {
646 MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
650 unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
652 fn haystack(&self) -> &'a str {
657 fn next(&mut self) -> SearchStep {
658 let s = &mut self.char_indices;
659 // Compare lengths of the internal byte slice iterator
660 // to find length of current char
661 let pre_len = s.iter.iter.len();
662 if let Some((i, c)) = s.next() {
663 let len = s.iter.iter.len();
664 let char_len = pre_len - len;
665 if self.char_eq.matches(c) {
666 return SearchStep::Match(i, i + char_len);
668 return SearchStep::Reject(i, i + char_len);
675 unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
677 fn next_back(&mut self) -> SearchStep {
678 let s = &mut self.char_indices;
679 // Compare lengths of the internal byte slice iterator
680 // to find length of current char
681 let pre_len = s.iter.iter.len();
682 if let Some((i, c)) = s.next_back() {
683 let len = s.iter.iter.len();
684 let char_len = pre_len - len;
685 if self.char_eq.matches(c) {
686 return SearchStep::Match(i, i + char_len);
688 return SearchStep::Reject(i, i + char_len);
695 impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}
697 /////////////////////////////////////////////////////////////////////////////
699 macro_rules! pattern_methods {
700 ($t:ty, $pmap:expr, $smap:expr) => {
704 fn into_searcher(self, haystack: &'a str) -> $t {
705 ($smap)(($pmap)(self).into_searcher(haystack))
709 fn is_contained_in(self, haystack: &'a str) -> bool {
710 ($pmap)(self).is_contained_in(haystack)
714 fn is_prefix_of(self, haystack: &'a str) -> bool {
715 ($pmap)(self).is_prefix_of(haystack)
719 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
720 ($pmap)(self).strip_prefix_of(haystack)
724 fn is_suffix_of(self, haystack: &'a str) -> bool
726 $t: ReverseSearcher<'a>,
728 ($pmap)(self).is_suffix_of(haystack)
732 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
734 $t: ReverseSearcher<'a>,
736 ($pmap)(self).strip_suffix_of(haystack)
741 macro_rules! searcher_methods {
744 fn haystack(&self) -> &'a str {
748 fn next(&mut self) -> SearchStep {
752 fn next_match(&mut self) -> Option<(usize, usize)> {
756 fn next_reject(&mut self) -> Option<(usize, usize)> {
762 fn next_back(&mut self) -> SearchStep {
766 fn next_match_back(&mut self) -> Option<(usize, usize)> {
767 self.0.next_match_back()
770 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
771 self.0.next_reject_back()
776 /// Associated type for `<[char; N] as Pattern<'a>>::Searcher`.
777 #[derive(Clone, Debug)]
778 pub struct CharArraySearcher<'a, const N: usize>(
779 <MultiCharEqPattern<[char; N]> as Pattern<'a>>::Searcher,
782 /// Associated type for `<&[char; N] as Pattern<'a>>::Searcher`.
783 #[derive(Clone, Debug)]
784 pub struct CharArrayRefSearcher<'a, 'b, const N: usize>(
785 <MultiCharEqPattern<&'b [char; N]> as Pattern<'a>>::Searcher,
788 /// Searches for chars that are equal to any of the [`char`]s in the array.
793 /// assert_eq!("Hello world".find(['l', 'l']), Some(2));
794 /// assert_eq!("Hello world".find(['l', 'l']), Some(2));
796 impl<'a, const N: usize> Pattern<'a> for [char; N] {
797 pattern_methods!(CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher);
800 unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> {
801 searcher_methods!(forward);
804 unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> {
805 searcher_methods!(reverse);
808 /// Searches for chars that are equal to any of the [`char`]s in the array.
813 /// assert_eq!("Hello world".find(&['l', 'l']), Some(2));
814 /// assert_eq!("Hello world".find(&['l', 'l']), Some(2));
816 impl<'a, 'b, const N: usize> Pattern<'a> for &'b [char; N] {
817 pattern_methods!(CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher);
820 unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
821 searcher_methods!(forward);
824 unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
825 searcher_methods!(reverse);
828 /////////////////////////////////////////////////////////////////////////////
830 /////////////////////////////////////////////////////////////////////////////
832 // Todo: Change / Remove due to ambiguity in meaning.
834 /// Associated type for `<&[char] as Pattern<'a>>::Searcher`.
835 #[derive(Clone, Debug)]
836 pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern<'a>>::Searcher);
838 unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
839 searcher_methods!(forward);
842 unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
843 searcher_methods!(reverse);
846 impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
848 /// Searches for chars that are equal to any of the [`char`]s in the slice.
853 /// assert_eq!("Hello world".find(&['l', 'l'] as &[_]), Some(2));
854 /// assert_eq!("Hello world".find(&['l', 'l'][..]), Some(2));
856 impl<'a, 'b> Pattern<'a> for &'b [char] {
857 pattern_methods!(CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
860 /////////////////////////////////////////////////////////////////////////////
861 // Impl for F: FnMut(char) -> bool
862 /////////////////////////////////////////////////////////////////////////////
864 /// Associated type for `<F as Pattern<'a>>::Searcher`.
866 pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern<'a>>::Searcher)
868 F: FnMut(char) -> bool;
870 impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
872 F: FnMut(char) -> bool,
874 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
875 f.debug_struct("CharPredicateSearcher")
876 .field("haystack", &self.0.haystack)
877 .field("char_indices", &self.0.char_indices)
881 unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
883 F: FnMut(char) -> bool,
885 searcher_methods!(forward);
888 unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
890 F: FnMut(char) -> bool,
892 searcher_methods!(reverse);
895 impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}
897 /// Searches for [`char`]s that match the given predicate.
902 /// assert_eq!("Hello world".find(char::is_uppercase), Some(0));
903 /// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1));
905 impl<'a, F> Pattern<'a> for F
907 F: FnMut(char) -> bool,
909 pattern_methods!(CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
912 /////////////////////////////////////////////////////////////////////////////
914 /////////////////////////////////////////////////////////////////////////////
916 /// Delegates to the `&str` impl.
917 impl<'a, 'b, 'c> Pattern<'a> for &'c &'b str {
918 pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s);
921 /////////////////////////////////////////////////////////////////////////////
923 /////////////////////////////////////////////////////////////////////////////
925 /// Non-allocating substring search.
927 /// Will handle the pattern `""` as returning empty matches at each character
933 /// assert_eq!("Hello world".find("world"), Some(6));
935 impl<'a, 'b> Pattern<'a> for &'b str {
936 type Searcher = StrSearcher<'a, 'b>;
939 fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> {
940 StrSearcher::new(haystack, self)
943 /// Checks whether the pattern matches at the front of the haystack.
945 fn is_prefix_of(self, haystack: &'a str) -> bool {
946 haystack.as_bytes().starts_with(self.as_bytes())
949 /// Removes the pattern from the front of haystack, if it matches.
951 fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
952 if self.is_prefix_of(haystack) {
953 // SAFETY: prefix was just verified to exist.
954 unsafe { Some(haystack.get_unchecked(self.as_bytes().len()..)) }
960 /// Checks whether the pattern matches at the back of the haystack.
962 fn is_suffix_of(self, haystack: &'a str) -> bool {
963 haystack.as_bytes().ends_with(self.as_bytes())
966 /// Removes the pattern from the back of haystack, if it matches.
968 fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> {
969 if self.is_suffix_of(haystack) {
970 let i = haystack.len() - self.as_bytes().len();
971 // SAFETY: suffix was just verified to exist.
972 unsafe { Some(haystack.get_unchecked(..i)) }
979 /////////////////////////////////////////////////////////////////////////////
980 // Two Way substring searcher
981 /////////////////////////////////////////////////////////////////////////////
983 #[derive(Clone, Debug)]
984 /// Associated type for `<&str as Pattern<'a>>::Searcher`.
985 pub struct StrSearcher<'a, 'b> {
989 searcher: StrSearcherImpl,
992 #[derive(Clone, Debug)]
993 enum StrSearcherImpl {
995 TwoWay(TwoWaySearcher),
998 #[derive(Clone, Debug)]
1004 // Needed in case of an empty haystack, see #85462
1008 impl<'a, 'b> StrSearcher<'a, 'b> {
1009 fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
1010 if needle.is_empty() {
1014 searcher: StrSearcherImpl::Empty(EmptyNeedle {
1016 end: haystack.len(),
1026 searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
1035 unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
1037 fn haystack(&self) -> &'a str {
1042 fn next(&mut self) -> SearchStep {
1043 match self.searcher {
1044 StrSearcherImpl::Empty(ref mut searcher) => {
1045 if searcher.is_finished {
1046 return SearchStep::Done;
1048 // empty needle rejects every char and matches every empty string between them
1049 let is_match = searcher.is_match_fw;
1050 searcher.is_match_fw = !searcher.is_match_fw;
1051 let pos = searcher.position;
1052 match self.haystack[pos..].chars().next() {
1053 _ if is_match => SearchStep::Match(pos, pos),
1055 searcher.is_finished = true;
1059 searcher.position += ch.len_utf8();
1060 SearchStep::Reject(pos, searcher.position)
1064 StrSearcherImpl::TwoWay(ref mut searcher) => {
1065 // TwoWaySearcher produces valid *Match* indices that split at char boundaries
1066 // as long as it does correct matching and that haystack and needle are
1068 // *Rejects* from the algorithm can fall on any indices, but we will walk them
1069 // manually to the next character boundary, so that they are utf-8 safe.
1070 if searcher.position == self.haystack.len() {
1071 return SearchStep::Done;
1073 let is_long = searcher.memory == usize::MAX;
1074 match searcher.next::<RejectAndMatch>(
1075 self.haystack.as_bytes(),
1076 self.needle.as_bytes(),
1079 SearchStep::Reject(a, mut b) => {
1080 // skip to next char boundary
1081 while !self.haystack.is_char_boundary(b) {
1084 searcher.position = cmp::max(b, searcher.position);
1085 SearchStep::Reject(a, b)
1087 otherwise => otherwise,
1094 fn next_match(&mut self) -> Option<(usize, usize)> {
1095 match self.searcher {
1096 StrSearcherImpl::Empty(..) => loop {
1098 SearchStep::Match(a, b) => return Some((a, b)),
1099 SearchStep::Done => return None,
1100 SearchStep::Reject(..) => {}
1103 StrSearcherImpl::TwoWay(ref mut searcher) => {
1104 let is_long = searcher.memory == usize::MAX;
1105 // write out `true` and `false` cases to encourage the compiler
1106 // to specialize the two cases separately.
1108 searcher.next::<MatchOnly>(
1109 self.haystack.as_bytes(),
1110 self.needle.as_bytes(),
1114 searcher.next::<MatchOnly>(
1115 self.haystack.as_bytes(),
1116 self.needle.as_bytes(),
1125 unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
1127 fn next_back(&mut self) -> SearchStep {
1128 match self.searcher {
1129 StrSearcherImpl::Empty(ref mut searcher) => {
1130 if searcher.is_finished {
1131 return SearchStep::Done;
1133 let is_match = searcher.is_match_bw;
1134 searcher.is_match_bw = !searcher.is_match_bw;
1135 let end = searcher.end;
1136 match self.haystack[..end].chars().next_back() {
1137 _ if is_match => SearchStep::Match(end, end),
1139 searcher.is_finished = true;
1143 searcher.end -= ch.len_utf8();
1144 SearchStep::Reject(searcher.end, end)
1148 StrSearcherImpl::TwoWay(ref mut searcher) => {
1149 if searcher.end == 0 {
1150 return SearchStep::Done;
1152 let is_long = searcher.memory == usize::MAX;
1153 match searcher.next_back::<RejectAndMatch>(
1154 self.haystack.as_bytes(),
1155 self.needle.as_bytes(),
1158 SearchStep::Reject(mut a, b) => {
1159 // skip to next char boundary
1160 while !self.haystack.is_char_boundary(a) {
1163 searcher.end = cmp::min(a, searcher.end);
1164 SearchStep::Reject(a, b)
1166 otherwise => otherwise,
1173 fn next_match_back(&mut self) -> Option<(usize, usize)> {
1174 match self.searcher {
1175 StrSearcherImpl::Empty(..) => loop {
1176 match self.next_back() {
1177 SearchStep::Match(a, b) => return Some((a, b)),
1178 SearchStep::Done => return None,
1179 SearchStep::Reject(..) => {}
1182 StrSearcherImpl::TwoWay(ref mut searcher) => {
1183 let is_long = searcher.memory == usize::MAX;
1184 // write out `true` and `false`, like `next_match`
1186 searcher.next_back::<MatchOnly>(
1187 self.haystack.as_bytes(),
1188 self.needle.as_bytes(),
1192 searcher.next_back::<MatchOnly>(
1193 self.haystack.as_bytes(),
1194 self.needle.as_bytes(),
1203 /// The internal state of the two-way substring search algorithm.
1204 #[derive(Clone, Debug)]
1205 struct TwoWaySearcher {
1207 /// critical factorization index
1209 /// critical factorization index for reversed needle
1210 crit_pos_back: usize,
1212 /// `byteset` is an extension (not part of the two way algorithm);
1213 /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
1214 /// to a (byte & 63) == j present in the needle.
1220 /// index into needle before which we have already matched
1222 /// index into needle after which we have already matched
1227 This is the Two-Way search algorithm, which was introduced in the paper:
1228 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
1230 Here's some background information.
1232 A *word* is a string of symbols. The *length* of a word should be a familiar
1233 notion, and here we denote it for any word x by |x|.
1234 (We also allow for the possibility of the *empty word*, a word of length zero).
1236 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
1237 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
1238 For example, both 1 and 2 are periods for the string "aa". As another example,
1239 the only period of the string "abcd" is 4.
1241 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
1242 This is always well-defined since every non-empty word x has at least one period,
1243 |x|. We sometimes call this *the period* of x.
1245 If u, v and x are words such that x = uv, where uv is the concatenation of u and
1246 v, then we say that (u, v) is a *factorization* of x.
1248 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
1249 that both of the following hold
1251 - either w is a suffix of u or u is a suffix of w
1252 - either w is a prefix of v or v is a prefix of w
1254 then w is said to be a *repetition* for the factorization (u, v).
1256 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
1259 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
1260 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
1261 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
1262 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
1264 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
1265 so every factorization has at least one repetition.
1267 If x is a string and (u, v) is a factorization for x, then a *local period* for
1268 (u, v) is an integer r such that there is some word w such that |w| = r and w is
1269 a repetition for (u, v).
1271 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
1272 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
1273 is well-defined (because each non-empty word has at least one factorization, as
1276 It can be proven that the following is an equivalent definition of a local period
1277 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
1278 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
1279 defined. (i.e., i > 0 and i + r < |x|).
1281 Using the above reformulation, it is easy to prove that
1283 1 <= local_period(u, v) <= period(uv)
1285 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
1286 *critical factorization*.
1288 The algorithm hinges on the following theorem, which is stated without proof:
1290 **Critical Factorization Theorem** Any word x has at least one critical
1291 factorization (u, v) such that |u| < period(x).
1293 The purpose of maximal_suffix is to find such a critical factorization.
1295 If the period is short, compute another factorization x = u' v' to use
1296 for reverse search, chosen instead so that |v'| < period(x).
1299 impl TwoWaySearcher {
1300 fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
1301 let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
1302 let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);
1304 let (crit_pos, period) = if crit_pos_false > crit_pos_true {
1305 (crit_pos_false, period_false)
1307 (crit_pos_true, period_true)
1310 // A particularly readable explanation of what's going on here can be found
1311 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
1312 // see the code for "Algorithm CP" on p. 323.
1314 // What's going on is we have some critical factorization (u, v) of the
1315 // needle, and we want to determine whether u is a suffix of
1316 // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
1317 // "Algorithm CP2", which is optimized for when the period of the needle
1319 if needle[..crit_pos] == needle[period..period + crit_pos] {
1320 // short period case -- the period is exact
1321 // compute a separate critical factorization for the reversed needle
1322 // x = u' v' where |v'| < period(x).
1324 // This is sped up by the period being known already.
1325 // Note that a case like x = "acba" may be factored exactly forwards
1326 // (crit_pos = 1, period = 3) while being factored with approximate
1327 // period in reverse (crit_pos = 2, period = 2). We use the given
1328 // reverse factorization but keep the exact period.
1329 let crit_pos_back = needle.len()
1331 TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
1332 TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
1339 byteset: Self::byteset_create(&needle[..period]),
1344 memory_back: needle.len(),
1347 // long period case -- we have an approximation to the actual period,
1348 // and don't use memorization.
1350 // Approximate the period by lower bound max(|u|, |v|) + 1.
1351 // The critical factorization is efficient to use for both forward and
1356 crit_pos_back: crit_pos,
1357 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
1358 byteset: Self::byteset_create(needle),
1362 memory: usize::MAX, // Dummy value to signify that the period is long
1363 memory_back: usize::MAX,
1369 fn byteset_create(bytes: &[u8]) -> u64 {
1370 bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
1374 fn byteset_contains(&self, byte: u8) -> bool {
1375 (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
1378 // One of the main ideas of Two-Way is that we factorize the needle into
1379 // two halves, (u, v), and begin trying to find v in the haystack by scanning
1380 // left to right. If v matches, we try to match u by scanning right to left.
1381 // How far we can jump when we encounter a mismatch is all based on the fact
1382 // that (u, v) is a critical factorization for the needle.
1384 fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1388 // `next()` uses `self.position` as its cursor
1389 let old_pos = self.position;
1390 let needle_last = needle.len() - 1;
1392 // Check that we have room to search in
1393 // position + needle_last can not overflow if we assume slices
1394 // are bounded by isize's range.
1395 let tail_byte = match haystack.get(self.position + needle_last) {
1398 self.position = haystack.len();
1399 return S::rejecting(old_pos, self.position);
1403 if S::use_early_reject() && old_pos != self.position {
1404 return S::rejecting(old_pos, self.position);
1407 // Quickly skip by large portions unrelated to our substring
1408 if !self.byteset_contains(tail_byte) {
1409 self.position += needle.len();
1416 // See if the right part of the needle matches
1418 if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) };
1419 for i in start..needle.len() {
1420 if needle[i] != haystack[self.position + i] {
1421 self.position += i - self.crit_pos + 1;
1429 // See if the left part of the needle matches
1430 let start = if long_period { 0 } else { self.memory };
1431 for i in (start..self.crit_pos).rev() {
1432 if needle[i] != haystack[self.position + i] {
1433 self.position += self.period;
1435 self.memory = needle.len() - self.period;
1441 // We have found a match!
1442 let match_pos = self.position;
1444 // Note: add self.period instead of needle.len() to have overlapping matches
1445 self.position += needle.len();
1447 self.memory = 0; // set to needle.len() - self.period for overlapping matches
1450 return S::matching(match_pos, match_pos + needle.len());
1454 // Follows the ideas in `next()`.
1456 // The definitions are symmetrical, with period(x) = period(reverse(x))
1457 // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
1458 // is a critical factorization, so is (reverse(v), reverse(u)).
1460 // For the reverse case we have computed a critical factorization x = u' v'
1461 // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
1462 // thus |v'| < period(x) for the reverse.
1464 // To search in reverse through the haystack, we search forward through
1465 // a reversed haystack with a reversed needle, matching first u' and then v'.
1467 fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1471 // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1473 let old_end = self.end;
1475 // Check that we have room to search in
1476 // end - needle.len() will wrap around when there is no more room,
1477 // but due to slice length limits it can never wrap all the way back
1478 // into the length of haystack.
1479 let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
1483 return S::rejecting(0, old_end);
1487 if S::use_early_reject() && old_end != self.end {
1488 return S::rejecting(self.end, old_end);
1491 // Quickly skip by large portions unrelated to our substring
1492 if !self.byteset_contains(front_byte) {
1493 self.end -= needle.len();
1495 self.memory_back = needle.len();
1500 // See if the left part of the needle matches
1501 let crit = if long_period {
1504 cmp::min(self.crit_pos_back, self.memory_back)
1506 for i in (0..crit).rev() {
1507 if needle[i] != haystack[self.end - needle.len() + i] {
1508 self.end -= self.crit_pos_back - i;
1510 self.memory_back = needle.len();
1516 // See if the right part of the needle matches
1517 let needle_end = if long_period { needle.len() } else { self.memory_back };
1518 for i in self.crit_pos_back..needle_end {
1519 if needle[i] != haystack[self.end - needle.len() + i] {
1520 self.end -= self.period;
1522 self.memory_back = self.period;
1528 // We have found a match!
1529 let match_pos = self.end - needle.len();
1530 // Note: sub self.period instead of needle.len() to have overlapping matches
1531 self.end -= needle.len();
1533 self.memory_back = needle.len();
1536 return S::matching(match_pos, match_pos + needle.len());
1540 // Compute the maximal suffix of `arr`.
1542 // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1544 // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1547 // `order_greater` determines if lexical order is `<` or `>`. Both
1548 // orders must be computed -- the ordering with the largest `i` gives
1549 // a critical factorization.
1551 // For long period cases, the resulting period is not exact (it is too short).
1553 fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
1554 let mut left = 0; // Corresponds to i in the paper
1555 let mut right = 1; // Corresponds to j in the paper
1556 let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1557 // to match 0-based indexing.
1558 let mut period = 1; // Corresponds to p in the paper
1560 while let Some(&a) = arr.get(right + offset) {
1561 // `left` will be inbounds when `right` is.
1562 let b = arr[left + offset];
1563 if (a < b && !order_greater) || (a > b && order_greater) {
1564 // Suffix is smaller, period is entire prefix so far.
1565 right += offset + 1;
1567 period = right - left;
1569 // Advance through repetition of the current period.
1570 if offset + 1 == period {
1571 right += offset + 1;
1577 // Suffix is larger, start over from current location.
1587 // Compute the maximal suffix of the reverse of `arr`.
1589 // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1591 // Returns `i` where `i` is the starting index of v', from the back;
1592 // returns immediately when a period of `known_period` is reached.
1594 // `order_greater` determines if lexical order is `<` or `>`. Both
1595 // orders must be computed -- the ordering with the largest `i` gives
1596 // a critical factorization.
1598 // For long period cases, the resulting period is not exact (it is too short).
1599 fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize {
1600 let mut left = 0; // Corresponds to i in the paper
1601 let mut right = 1; // Corresponds to j in the paper
1602 let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1603 // to match 0-based indexing.
1604 let mut period = 1; // Corresponds to p in the paper
1607 while right + offset < n {
1608 let a = arr[n - (1 + right + offset)];
1609 let b = arr[n - (1 + left + offset)];
1610 if (a < b && !order_greater) || (a > b && order_greater) {
1611 // Suffix is smaller, period is entire prefix so far.
1612 right += offset + 1;
1614 period = right - left;
1616 // Advance through repetition of the current period.
1617 if offset + 1 == period {
1618 right += offset + 1;
1624 // Suffix is larger, start over from current location.
1630 if period == known_period {
1634 debug_assert!(period <= known_period);
1639 // TwoWayStrategy allows the algorithm to either skip non-matches as quickly
1640 // as possible, or to work in a mode where it emits Rejects relatively quickly.
1641 trait TwoWayStrategy {
1643 fn use_early_reject() -> bool;
1644 fn rejecting(a: usize, b: usize) -> Self::Output;
1645 fn matching(a: usize, b: usize) -> Self::Output;
1648 /// Skip to match intervals as quickly as possible
1651 impl TwoWayStrategy for MatchOnly {
1652 type Output = Option<(usize, usize)>;
1655 fn use_early_reject() -> bool {
1659 fn rejecting(_a: usize, _b: usize) -> Self::Output {
1663 fn matching(a: usize, b: usize) -> Self::Output {
1668 /// Emit Rejects regularly
1669 enum RejectAndMatch {}
1671 impl TwoWayStrategy for RejectAndMatch {
1672 type Output = SearchStep;
1675 fn use_early_reject() -> bool {
1679 fn rejecting(a: usize, b: usize) -> Self::Output {
1680 SearchStep::Reject(a, b)
1683 fn matching(a: usize, b: usize) -> Self::Output {
1684 SearchStep::Match(a, b)