diff options
Diffstat (limited to 'library/core/src/str/pattern.rs')
| -rw-r--r-- | library/core/src/str/pattern.rs | 1686 |
1 files changed, 1686 insertions, 0 deletions
diff --git a/library/core/src/str/pattern.rs b/library/core/src/str/pattern.rs new file mode 100644 index 000000000..031fb8e8b --- /dev/null +++ b/library/core/src/str/pattern.rs @@ -0,0 +1,1686 @@ +//! The string Pattern API. +//! +//! The Pattern API provides a generic mechanism for using different pattern +//! types when searching through a string. +//! +//! For more details, see the traits [`Pattern`], [`Searcher`], +//! [`ReverseSearcher`], and [`DoubleEndedSearcher`]. +//! +//! Although this API is unstable, it is exposed via stable APIs on the +//! [`str`] type. +//! +//! # Examples +//! +//! [`Pattern`] is [implemented][pattern-impls] in the stable API for +//! [`&str`][`str`], [`char`], slices of [`char`], and functions and closures +//! implementing `FnMut(char) -> bool`. +//! +//! ``` +//! let s = "Can you find a needle in a haystack?"; +//! +//! // &str pattern +//! assert_eq!(s.find("you"), Some(4)); +//! // char pattern +//! assert_eq!(s.find('n'), Some(2)); +//! // array of chars pattern +//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u']), Some(1)); +//! // slice of chars pattern +//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u'][..]), Some(1)); +//! // closure pattern +//! assert_eq!(s.find(|c: char| c.is_ascii_punctuation()), Some(35)); +//! ``` +//! +//! [pattern-impls]: Pattern#implementors + +#![unstable( + feature = "pattern", + reason = "API not fully fleshed out and ready to be stabilized", + issue = "27721" +)] + +use crate::cmp; +use crate::fmt; +use crate::slice::memchr; + +// Pattern + +/// A string pattern. +/// +/// A `Pattern<'a>` expresses that the implementing type +/// can be used as a string pattern for searching in a [`&'a str`][str]. +/// +/// For example, both `'a'` and `"aa"` are patterns that +/// would match at index `1` in the string `"baaaab"`. +/// +/// The trait itself acts as a builder for an associated +/// [`Searcher`] type, which does the actual work of finding +/// occurrences of the pattern in a string. +/// +/// Depending on the type of the pattern, the behaviour of methods like +/// [`str::find`] and [`str::contains`] can change. The table below describes +/// some of those behaviours. +/// +/// | Pattern type | Match condition | +/// |--------------------------|-------------------------------------------| +/// | `&str` | is substring | +/// | `char` | is contained in string | +/// | `&[char]` | any char in slice is contained in string | +/// | `F: FnMut(char) -> bool` | `F` returns `true` for a char in string | +/// | `&&str` | is substring | +/// | `&String` | is substring | +/// +/// # Examples +/// +/// ``` +/// // &str +/// assert_eq!("abaaa".find("ba"), Some(1)); +/// assert_eq!("abaaa".find("bac"), None); +/// +/// // char +/// assert_eq!("abaaa".find('a'), Some(0)); +/// assert_eq!("abaaa".find('b'), Some(1)); +/// assert_eq!("abaaa".find('c'), None); +/// +/// // &[char; N] +/// assert_eq!("ab".find(&['b', 'a']), Some(0)); +/// assert_eq!("abaaa".find(&['a', 'z']), Some(0)); +/// assert_eq!("abaaa".find(&['c', 'd']), None); +/// +/// // &[char] +/// assert_eq!("ab".find(&['b', 'a'][..]), Some(0)); +/// assert_eq!("abaaa".find(&['a', 'z'][..]), Some(0)); +/// assert_eq!("abaaa".find(&['c', 'd'][..]), None); +/// +/// // FnMut(char) -> bool +/// assert_eq!("abcdef_z".find(|ch| ch > 'd' && ch < 'y'), Some(4)); +/// assert_eq!("abcddd_z".find(|ch| ch > 'd' && ch < 'y'), None); +/// ``` +pub trait Pattern<'a>: Sized { + /// Associated searcher for this pattern + type Searcher: Searcher<'a>; + + /// Constructs the associated searcher from + /// `self` and the `haystack` to search in. + fn into_searcher(self, haystack: &'a str) -> Self::Searcher; + + /// Checks whether the pattern matches anywhere in the haystack + #[inline] + fn is_contained_in(self, haystack: &'a str) -> bool { + self.into_searcher(haystack).next_match().is_some() + } + + /// Checks whether the pattern matches at the front of the haystack + #[inline] + fn is_prefix_of(self, haystack: &'a str) -> bool { + matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _)) + } + + /// Checks whether the pattern matches at the back of the haystack + #[inline] + fn is_suffix_of(self, haystack: &'a str) -> bool + where + Self::Searcher: ReverseSearcher<'a>, + { + matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j) + } + + /// Removes the pattern from the front of haystack, if it matches. + #[inline] + fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> { + if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() { + debug_assert_eq!( + start, 0, + "The first search step from Searcher \ + must include the first character" + ); + // SAFETY: `Searcher` is known to return valid indices. + unsafe { Some(haystack.get_unchecked(len..)) } + } else { + None + } + } + + /// Removes the pattern from the back of haystack, if it matches. + #[inline] + fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> + where + Self::Searcher: ReverseSearcher<'a>, + { + if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() { + debug_assert_eq!( + end, + haystack.len(), + "The first search step from ReverseSearcher \ + must include the last character" + ); + // SAFETY: `Searcher` is known to return valid indices. + unsafe { Some(haystack.get_unchecked(..start)) } + } else { + None + } + } +} + +// Searcher + +/// Result of calling [`Searcher::next()`] or [`ReverseSearcher::next_back()`]. +#[derive(Copy, Clone, Eq, PartialEq, Debug)] +pub enum SearchStep { + /// Expresses that a match of the pattern has been found at + /// `haystack[a..b]`. + Match(usize, usize), + /// Expresses that `haystack[a..b]` has been rejected as a possible match + /// of the pattern. + /// + /// Note that there might be more than one `Reject` between two `Match`es, + /// there is no requirement for them to be combined into one. + Reject(usize, usize), + /// Expresses that every byte of the haystack has been visited, ending + /// the iteration. + Done, +} + +/// A searcher for a string pattern. +/// +/// This trait provides methods for searching for non-overlapping +/// matches of a pattern starting from the front (left) of a string. +/// +/// It will be implemented by associated `Searcher` +/// types of the [`Pattern`] trait. +/// +/// The trait is marked unsafe because the indices returned by the +/// [`next()`][Searcher::next] methods are required to lie on valid utf8 +/// boundaries in the haystack. This enables consumers of this trait to +/// slice the haystack without additional runtime checks. +pub unsafe trait Searcher<'a> { + /// Getter for the underlying string to be searched in + /// + /// Will always return the same [`&str`][str]. + fn haystack(&self) -> &'a str; + + /// Performs the next search step starting from the front. + /// + /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches + /// the pattern. + /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` can + /// not match the pattern, even partially. + /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack has + /// been visited. + /// + /// The stream of [`Match`][SearchStep::Match] and + /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done] + /// will contain index ranges that are adjacent, non-overlapping, + /// covering the whole haystack, and laying on utf8 boundaries. + /// + /// A [`Match`][SearchStep::Match] result needs to contain the whole matched + /// pattern, however [`Reject`][SearchStep::Reject] results may be split up + /// into arbitrary many adjacent fragments. Both ranges may have zero length. + /// + /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"` + /// might produce the stream + /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]` + fn next(&mut self) -> SearchStep; + + /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next]. + /// + /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges + /// of this and [`next_reject`][Searcher::next_reject] will overlap. This will return + /// `(start_match, end_match)`, where start_match is the index of where + /// the match begins, and end_match is the index after the end of the match. + #[inline] + fn next_match(&mut self) -> Option<(usize, usize)> { + loop { + match self.next() { + SearchStep::Match(a, b) => return Some((a, b)), + SearchStep::Done => return None, + _ => continue, + } + } + } + + /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next] + /// and [`next_match()`][Searcher::next_match]. + /// + /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges + /// of this and [`next_match`][Searcher::next_match] will overlap. + #[inline] + fn next_reject(&mut self) -> Option<(usize, usize)> { + loop { + match self.next() { + SearchStep::Reject(a, b) => return Some((a, b)), + SearchStep::Done => return None, + _ => continue, + } + } + } +} + +/// A reverse searcher for a string pattern. +/// +/// This trait provides methods for searching for non-overlapping +/// matches of a pattern starting from the back (right) of a string. +/// +/// It will be implemented by associated [`Searcher`] +/// types of the [`Pattern`] trait if the pattern supports searching +/// for it from the back. +/// +/// The index ranges returned by this trait are not required +/// to exactly match those of the forward search in reverse. +/// +/// For the reason why this trait is marked unsafe, see them +/// parent trait [`Searcher`]. +pub unsafe trait ReverseSearcher<'a>: Searcher<'a> { + /// Performs the next search step starting from the back. + /// + /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` + /// matches the pattern. + /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` + /// can not match the pattern, even partially. + /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack + /// has been visited + /// + /// The stream of [`Match`][SearchStep::Match] and + /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done] + /// will contain index ranges that are adjacent, non-overlapping, + /// covering the whole haystack, and laying on utf8 boundaries. + /// + /// A [`Match`][SearchStep::Match] result needs to contain the whole matched + /// pattern, however [`Reject`][SearchStep::Reject] results may be split up + /// into arbitrary many adjacent fragments. Both ranges may have zero length. + /// + /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"` + /// might produce the stream + /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`. + fn next_back(&mut self) -> SearchStep; + + /// Finds the next [`Match`][SearchStep::Match] result. + /// See [`next_back()`][ReverseSearcher::next_back]. + #[inline] + fn next_match_back(&mut self) -> Option<(usize, usize)> { + loop { + match self.next_back() { + SearchStep::Match(a, b) => return Some((a, b)), + SearchStep::Done => return None, + _ => continue, + } + } + } + + /// Finds the next [`Reject`][SearchStep::Reject] result. + /// See [`next_back()`][ReverseSearcher::next_back]. + #[inline] + fn next_reject_back(&mut self) -> Option<(usize, usize)> { + loop { + match self.next_back() { + SearchStep::Reject(a, b) => return Some((a, b)), + SearchStep::Done => return None, + _ => continue, + } + } + } +} + +/// A marker trait to express that a [`ReverseSearcher`] +/// can be used for a [`DoubleEndedIterator`] implementation. +/// +/// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need +/// to follow these conditions: +/// +/// - All results of `next()` need to be identical +/// to the results of `next_back()` in reverse order. +/// - `next()` and `next_back()` need to behave as +/// the two ends of a range of values, that is they +/// can not "walk past each other". +/// +/// # Examples +/// +/// `char::Searcher` is a `DoubleEndedSearcher` because searching for a +/// [`char`] only requires looking at one at a time, which behaves the same +/// from both ends. +/// +/// `(&str)::Searcher` is not a `DoubleEndedSearcher` because +/// the pattern `"aa"` in the haystack `"aaa"` matches as either +/// `"[aa]a"` or `"a[aa]"`, depending from which side it is searched. +pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {} + +///////////////////////////////////////////////////////////////////////////// +// Impl for char +///////////////////////////////////////////////////////////////////////////// + +/// Associated type for `<char as Pattern<'a>>::Searcher`. +#[derive(Clone, Debug)] +pub struct CharSearcher<'a> { + haystack: &'a str, + // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack` + // This invariant can be broken *within* next_match and next_match_back, however + // they must exit with fingers on valid code point boundaries. + /// `finger` is the current byte index of the forward search. + /// Imagine that it exists before the byte at its index, i.e. + /// `haystack[finger]` is the first byte of the slice we must inspect during + /// forward searching + finger: usize, + /// `finger_back` is the current byte index of the reverse search. + /// Imagine that it exists after the byte at its index, i.e. + /// haystack[finger_back - 1] is the last byte of the slice we must inspect during + /// forward searching (and thus the first byte to be inspected when calling next_back()). + finger_back: usize, + /// The character being searched for + needle: char, + + // safety invariant: `utf8_size` must be less than 5 + /// The number of bytes `needle` takes up when encoded in utf8. + utf8_size: usize, + /// A utf8 encoded copy of the `needle` + utf8_encoded: [u8; 4], +} + +unsafe impl<'a> Searcher<'a> for CharSearcher<'a> { + #[inline] + fn haystack(&self) -> &'a str { + self.haystack + } + #[inline] + fn next(&mut self) -> SearchStep { + let old_finger = self.finger; + // SAFETY: 1-4 guarantee safety of `get_unchecked` + // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries + // (this is invariant) + // 2. `self.finger >= 0` since it starts at 0 and only increases + // 3. `self.finger < self.finger_back` because otherwise the char `iter` + // would return `SearchStep::Done` + // 4. `self.finger` comes before the end of the haystack because `self.finger_back` + // starts at the end and only decreases + let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) }; + let mut iter = slice.chars(); + let old_len = iter.iter.len(); + if let Some(ch) = iter.next() { + // add byte offset of current character + // without re-encoding as utf-8 + self.finger += old_len - iter.iter.len(); + if ch == self.needle { + SearchStep::Match(old_finger, self.finger) + } else { + SearchStep::Reject(old_finger, self.finger) + } + } else { + SearchStep::Done + } + } + #[inline] + fn next_match(&mut self) -> Option<(usize, usize)> { + loop { + // get the haystack after the last character found + let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?; + // the last byte of the utf8 encoded needle + // SAFETY: we have an invariant that `utf8_size < 5` + let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) }; + if let Some(index) = memchr::memchr(last_byte, bytes) { + // The new finger is the index of the byte we found, + // plus one, since we memchr'd for the last byte of the character. + // + // Note that this doesn't always give us a finger on a UTF8 boundary. + // If we *didn't* find our character + // we may have indexed to the non-last byte of a 3-byte or 4-byte character. + // We can't just skip to the next valid starting byte because a character like + // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find + // the second byte when searching for the third. + // + // However, this is totally okay. While we have the invariant that + // self.finger is on a UTF8 boundary, this invariant is not relied upon + // within this method (it is relied upon in CharSearcher::next()). + // + // We only exit this method when we reach the end of the string, or if we + // find something. When we find something the `finger` will be set + // to a UTF8 boundary. + self.finger += index + 1; + if self.finger >= self.utf8_size { + let found_char = self.finger - self.utf8_size; + if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) { + if slice == &self.utf8_encoded[0..self.utf8_size] { + return Some((found_char, self.finger)); + } + } + } + } else { + // found nothing, exit + self.finger = self.finger_back; + return None; + } + } + } + + // let next_reject use the default implementation from the Searcher trait +} + +unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> { + #[inline] + fn next_back(&mut self) -> SearchStep { + let old_finger = self.finger_back; + // SAFETY: see the comment for next() above + let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) }; + let mut iter = slice.chars(); + let old_len = iter.iter.len(); + if let Some(ch) = iter.next_back() { + // subtract byte offset of current character + // without re-encoding as utf-8 + self.finger_back -= old_len - iter.iter.len(); + if ch == self.needle { + SearchStep::Match(self.finger_back, old_finger) + } else { + SearchStep::Reject(self.finger_back, old_finger) + } + } else { + SearchStep::Done + } + } + #[inline] + fn next_match_back(&mut self) -> Option<(usize, usize)> { + let haystack = self.haystack.as_bytes(); + loop { + // get the haystack up to but not including the last character searched + let bytes = haystack.get(self.finger..self.finger_back)?; + // the last byte of the utf8 encoded needle + // SAFETY: we have an invariant that `utf8_size < 5` + let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) }; + if let Some(index) = memchr::memrchr(last_byte, bytes) { + // we searched a slice that was offset by self.finger, + // add self.finger to recoup the original index + let index = self.finger + index; + // memrchr will return the index of the byte we wish to + // find. In case of an ASCII character, this is indeed + // were we wish our new finger to be ("after" the found + // char in the paradigm of reverse iteration). For + // multibyte chars we need to skip down by the number of more + // bytes they have than ASCII + let shift = self.utf8_size - 1; + if index >= shift { + let found_char = index - shift; + if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size)) { + if slice == &self.utf8_encoded[0..self.utf8_size] { + // move finger to before the character found (i.e., at its start index) + self.finger_back = found_char; + return Some((self.finger_back, self.finger_back + self.utf8_size)); + } + } + } + // We can't use finger_back = index - size + 1 here. If we found the last char + // of a different-sized character (or the middle byte of a different character) + // we need to bump the finger_back down to `index`. This similarly makes + // `finger_back` have the potential to no longer be on a boundary, + // but this is OK since we only exit this function on a boundary + // or when the haystack has been searched completely. + // + // Unlike next_match this does not + // have the problem of repeated bytes in utf-8 because + // we're searching for the last byte, and we can only have + // found the last byte when searching in reverse. + self.finger_back = index; + } else { + self.finger_back = self.finger; + // found nothing, exit + return None; + } + } + } + + // let next_reject_back use the default implementation from the Searcher trait +} + +impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {} + +/// Searches for chars that are equal to a given [`char`]. +/// +/// # Examples +/// +/// ``` +/// assert_eq!("Hello world".find('o'), Some(4)); +/// ``` +impl<'a> Pattern<'a> for char { + type Searcher = CharSearcher<'a>; + + #[inline] + fn into_searcher(self, haystack: &'a str) -> Self::Searcher { + let mut utf8_encoded = [0; 4]; + let utf8_size = self.encode_utf8(&mut utf8_encoded).len(); + CharSearcher { + haystack, + finger: 0, + finger_back: haystack.len(), + needle: self, + utf8_size, + utf8_encoded, + } + } + + #[inline] + fn is_contained_in(self, haystack: &'a str) -> bool { + if (self as u32) < 128 { + haystack.as_bytes().contains(&(self as u8)) + } else { + let mut buffer = [0u8; 4]; + self.encode_utf8(&mut buffer).is_contained_in(haystack) + } + } + + #[inline] + fn is_prefix_of(self, haystack: &'a str) -> bool { + self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack) + } + + #[inline] + fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> { + self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack) + } + + #[inline] + fn is_suffix_of(self, haystack: &'a str) -> bool + where + Self::Searcher: ReverseSearcher<'a>, + { + self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack) + } + + #[inline] + fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> + where + Self::Searcher: ReverseSearcher<'a>, + { + self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack) + } +} + +///////////////////////////////////////////////////////////////////////////// +// Impl for a MultiCharEq wrapper +///////////////////////////////////////////////////////////////////////////// + +#[doc(hidden)] +trait MultiCharEq { + fn matches(&mut self, c: char) -> bool; +} + +impl<F> MultiCharEq for F +where + F: FnMut(char) -> bool, +{ + #[inline] + fn matches(&mut self, c: char) -> bool { + (*self)(c) + } +} + +impl<const N: usize> MultiCharEq for [char; N] { + #[inline] + fn matches(&mut self, c: char) -> bool { + self.iter().any(|&m| m == c) + } +} + +impl<const N: usize> MultiCharEq for &[char; N] { + #[inline] + fn matches(&mut self, c: char) -> bool { + self.iter().any(|&m| m == c) + } +} + +impl MultiCharEq for &[char] { + #[inline] + fn matches(&mut self, c: char) -> bool { + self.iter().any(|&m| m == c) + } +} + +struct MultiCharEqPattern<C: MultiCharEq>(C); + +#[derive(Clone, Debug)] +struct MultiCharEqSearcher<'a, C: MultiCharEq> { + char_eq: C, + haystack: &'a str, + char_indices: super::CharIndices<'a>, +} + +impl<'a, C: MultiCharEq> Pattern<'a> for MultiCharEqPattern<C> { + type Searcher = MultiCharEqSearcher<'a, C>; + + #[inline] + fn into_searcher(self, haystack: &'a str) -> MultiCharEqSearcher<'a, C> { + MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() } + } +} + +unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> { + #[inline] + fn haystack(&self) -> &'a str { + self.haystack + } + + #[inline] + fn next(&mut self) -> SearchStep { + let s = &mut self.char_indices; + // Compare lengths of the internal byte slice iterator + // to find length of current char + let pre_len = s.iter.iter.len(); + if let Some((i, c)) = s.next() { + let len = s.iter.iter.len(); + let char_len = pre_len - len; + if self.char_eq.matches(c) { + return SearchStep::Match(i, i + char_len); + } else { + return SearchStep::Reject(i, i + char_len); + } + } + SearchStep::Done + } +} + +unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> { + #[inline] + fn next_back(&mut self) -> SearchStep { + let s = &mut self.char_indices; + // Compare lengths of the internal byte slice iterator + // to find length of current char + let pre_len = s.iter.iter.len(); + if let Some((i, c)) = s.next_back() { + let len = s.iter.iter.len(); + let char_len = pre_len - len; + if self.char_eq.matches(c) { + return SearchStep::Match(i, i + char_len); + } else { + return SearchStep::Reject(i, i + char_len); + } + } + SearchStep::Done + } +} + +impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {} + +///////////////////////////////////////////////////////////////////////////// + +macro_rules! pattern_methods { + ($t:ty, $pmap:expr, $smap:expr) => { + type Searcher = $t; + + #[inline] + fn into_searcher(self, haystack: &'a str) -> $t { + ($smap)(($pmap)(self).into_searcher(haystack)) + } + + #[inline] + fn is_contained_in(self, haystack: &'a str) -> bool { + ($pmap)(self).is_contained_in(haystack) + } + + #[inline] + fn is_prefix_of(self, haystack: &'a str) -> bool { + ($pmap)(self).is_prefix_of(haystack) + } + + #[inline] + fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> { + ($pmap)(self).strip_prefix_of(haystack) + } + + #[inline] + fn is_suffix_of(self, haystack: &'a str) -> bool + where + $t: ReverseSearcher<'a>, + { + ($pmap)(self).is_suffix_of(haystack) + } + + #[inline] + fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> + where + $t: ReverseSearcher<'a>, + { + ($pmap)(self).strip_suffix_of(haystack) + } + }; +} + +macro_rules! searcher_methods { + (forward) => { + #[inline] + fn haystack(&self) -> &'a str { + self.0.haystack() + } + #[inline] + fn next(&mut self) -> SearchStep { + self.0.next() + } + #[inline] + fn next_match(&mut self) -> Option<(usize, usize)> { + self.0.next_match() + } + #[inline] + fn next_reject(&mut self) -> Option<(usize, usize)> { + self.0.next_reject() + } + }; + (reverse) => { + #[inline] + fn next_back(&mut self) -> SearchStep { + self.0.next_back() + } + #[inline] + fn next_match_back(&mut self) -> Option<(usize, usize)> { + self.0.next_match_back() + } + #[inline] + fn next_reject_back(&mut self) -> Option<(usize, usize)> { + self.0.next_reject_back() + } + }; +} + +/// Associated type for `<[char; N] as Pattern<'a>>::Searcher`. +#[derive(Clone, Debug)] +pub struct CharArraySearcher<'a, const N: usize>( + <MultiCharEqPattern<[char; N]> as Pattern<'a>>::Searcher, +); + +/// Associated type for `<&[char; N] as Pattern<'a>>::Searcher`. +#[derive(Clone, Debug)] +pub struct CharArrayRefSearcher<'a, 'b, const N: usize>( + <MultiCharEqPattern<&'b [char; N]> as Pattern<'a>>::Searcher, +); + +/// Searches for chars that are equal to any of the [`char`]s in the array. +/// +/// # Examples +/// +/// ``` +/// assert_eq!("Hello world".find(['l', 'l']), Some(2)); +/// assert_eq!("Hello world".find(['l', 'l']), Some(2)); +/// ``` +impl<'a, const N: usize> Pattern<'a> for [char; N] { + pattern_methods!(CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher); +} + +unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> { + searcher_methods!(forward); +} + +unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> { + searcher_methods!(reverse); +} + +/// Searches for chars that are equal to any of the [`char`]s in the array. +/// +/// # Examples +/// +/// ``` +/// assert_eq!("Hello world".find(&['l', 'l']), Some(2)); +/// assert_eq!("Hello world".find(&['l', 'l']), Some(2)); +/// ``` +impl<'a, 'b, const N: usize> Pattern<'a> for &'b [char; N] { + pattern_methods!(CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher); +} + +unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> { + searcher_methods!(forward); +} + +unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> { + searcher_methods!(reverse); +} + +///////////////////////////////////////////////////////////////////////////// +// Impl for &[char] +///////////////////////////////////////////////////////////////////////////// + +// Todo: Change / Remove due to ambiguity in meaning. + +/// Associated type for `<&[char] as Pattern<'a>>::Searcher`. +#[derive(Clone, Debug)] +pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern<'a>>::Searcher); + +unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> { + searcher_methods!(forward); +} + +unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> { + searcher_methods!(reverse); +} + +impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {} + +/// Searches for chars that are equal to any of the [`char`]s in the slice. +/// +/// # Examples +/// +/// ``` +/// assert_eq!("Hello world".find(&['l', 'l'] as &[_]), Some(2)); +/// assert_eq!("Hello world".find(&['l', 'l'][..]), Some(2)); +/// ``` +impl<'a, 'b> Pattern<'a> for &'b [char] { + pattern_methods!(CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher); +} + +///////////////////////////////////////////////////////////////////////////// +// Impl for F: FnMut(char) -> bool +///////////////////////////////////////////////////////////////////////////// + +/// Associated type for `<F as Pattern<'a>>::Searcher`. +#[derive(Clone)] +pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern<'a>>::Searcher) +where + F: FnMut(char) -> bool; + +impl<F> fmt::Debug for CharPredicateSearcher<'_, F> +where + F: FnMut(char) -> bool, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_struct("CharPredicateSearcher") + .field("haystack", &self.0.haystack) + .field("char_indices", &self.0.char_indices) + .finish() + } +} +unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F> +where + F: FnMut(char) -> bool, +{ + searcher_methods!(forward); +} + +unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F> +where + F: FnMut(char) -> bool, +{ + searcher_methods!(reverse); +} + +impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {} + +/// Searches for [`char`]s that match the given predicate. +/// +/// # Examples +/// +/// ``` +/// assert_eq!("Hello world".find(char::is_uppercase), Some(0)); +/// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1)); +/// ``` +impl<'a, F> Pattern<'a> for F +where + F: FnMut(char) -> bool, +{ + pattern_methods!(CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher); +} + +///////////////////////////////////////////////////////////////////////////// +// Impl for &&str +///////////////////////////////////////////////////////////////////////////// + +/// Delegates to the `&str` impl. +impl<'a, 'b, 'c> Pattern<'a> for &'c &'b str { + pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s); +} + +///////////////////////////////////////////////////////////////////////////// +// Impl for &str +///////////////////////////////////////////////////////////////////////////// + +/// Non-allocating substring search. +/// +/// Will handle the pattern `""` as returning empty matches at each character +/// boundary. +/// +/// # Examples +/// +/// ``` +/// assert_eq!("Hello world".find("world"), Some(6)); +/// ``` +impl<'a, 'b> Pattern<'a> for &'b str { + type Searcher = StrSearcher<'a, 'b>; + + #[inline] + fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> { + StrSearcher::new(haystack, self) + } + + /// Checks whether the pattern matches at the front of the haystack. + #[inline] + fn is_prefix_of(self, haystack: &'a str) -> bool { + haystack.as_bytes().starts_with(self.as_bytes()) + } + + /// Removes the pattern from the front of haystack, if it matches. + #[inline] + fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> { + if self.is_prefix_of(haystack) { + // SAFETY: prefix was just verified to exist. + unsafe { Some(haystack.get_unchecked(self.as_bytes().len()..)) } + } else { + None + } + } + + /// Checks whether the pattern matches at the back of the haystack. + #[inline] + fn is_suffix_of(self, haystack: &'a str) -> bool { + haystack.as_bytes().ends_with(self.as_bytes()) + } + + /// Removes the pattern from the back of haystack, if it matches. + #[inline] + fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> { + if self.is_suffix_of(haystack) { + let i = haystack.len() - self.as_bytes().len(); + // SAFETY: suffix was just verified to exist. + unsafe { Some(haystack.get_unchecked(..i)) } + } else { + None + } + } +} + +///////////////////////////////////////////////////////////////////////////// +// Two Way substring searcher +///////////////////////////////////////////////////////////////////////////// + +#[derive(Clone, Debug)] +/// Associated type for `<&str as Pattern<'a>>::Searcher`. +pub struct StrSearcher<'a, 'b> { + haystack: &'a str, + needle: &'b str, + + searcher: StrSearcherImpl, +} + +#[derive(Clone, Debug)] +enum StrSearcherImpl { + Empty(EmptyNeedle), + TwoWay(TwoWaySearcher), +} + +#[derive(Clone, Debug)] +struct EmptyNeedle { + position: usize, + end: usize, + is_match_fw: bool, + is_match_bw: bool, + // Needed in case of an empty haystack, see #85462 + is_finished: bool, +} + +impl<'a, 'b> StrSearcher<'a, 'b> { + fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> { + if needle.is_empty() { + StrSearcher { + haystack, + needle, + searcher: StrSearcherImpl::Empty(EmptyNeedle { + position: 0, + end: haystack.len(), + is_match_fw: true, + is_match_bw: true, + is_finished: false, + }), + } + } else { + StrSearcher { + haystack, + needle, + searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new( + needle.as_bytes(), + haystack.len(), + )), + } + } + } +} + +unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> { + #[inline] + fn haystack(&self) -> &'a str { + self.haystack + } + + #[inline] + fn next(&mut self) -> SearchStep { + match self.searcher { + StrSearcherImpl::Empty(ref mut searcher) => { + if searcher.is_finished { + return SearchStep::Done; + } + // empty needle rejects every char and matches every empty string between them + let is_match = searcher.is_match_fw; + searcher.is_match_fw = !searcher.is_match_fw; + let pos = searcher.position; + match self.haystack[pos..].chars().next() { + _ if is_match => SearchStep::Match(pos, pos), + None => { + searcher.is_finished = true; + SearchStep::Done + } + Some(ch) => { + searcher.position += ch.len_utf8(); + SearchStep::Reject(pos, searcher.position) + } + } + } + StrSearcherImpl::TwoWay(ref mut searcher) => { + // TwoWaySearcher produces valid *Match* indices that split at char boundaries + // as long as it does correct matching and that haystack and needle are + // valid UTF-8 + // *Rejects* from the algorithm can fall on any indices, but we will walk them + // manually to the next character boundary, so that they are utf-8 safe. + if searcher.position == self.haystack.len() { + return SearchStep::Done; + } + let is_long = searcher.memory == usize::MAX; + match searcher.next::<RejectAndMatch>( + self.haystack.as_bytes(), + self.needle.as_bytes(), + is_long, + ) { + SearchStep::Reject(a, mut b) => { + // skip to next char boundary + while !self.haystack.is_char_boundary(b) { + b += 1; + } + searcher.position = cmp::max(b, searcher.position); + SearchStep::Reject(a, b) + } + otherwise => otherwise, + } + } + } + } + + #[inline] + fn next_match(&mut self) -> Option<(usize, usize)> { + match self.searcher { + StrSearcherImpl::Empty(..) => loop { + match self.next() { + SearchStep::Match(a, b) => return Some((a, b)), + SearchStep::Done => return None, + SearchStep::Reject(..) => {} + } + }, + StrSearcherImpl::TwoWay(ref mut searcher) => { + let is_long = searcher.memory == usize::MAX; + // write out `true` and `false` cases to encourage the compiler + // to specialize the two cases separately. + if is_long { + searcher.next::<MatchOnly>( + self.haystack.as_bytes(), + self.needle.as_bytes(), + true, + ) + } else { + searcher.next::<MatchOnly>( + self.haystack.as_bytes(), + self.needle.as_bytes(), + false, + ) + } + } + } + } +} + +unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> { + #[inline] + fn next_back(&mut self) -> SearchStep { + match self.searcher { + StrSearcherImpl::Empty(ref mut searcher) => { + if searcher.is_finished { + return SearchStep::Done; + } + let is_match = searcher.is_match_bw; + searcher.is_match_bw = !searcher.is_match_bw; + let end = searcher.end; + match self.haystack[..end].chars().next_back() { + _ if is_match => SearchStep::Match(end, end), + None => { + searcher.is_finished = true; + SearchStep::Done + } + Some(ch) => { + searcher.end -= ch.len_utf8(); + SearchStep::Reject(searcher.end, end) + } + } + } + StrSearcherImpl::TwoWay(ref mut searcher) => { + if searcher.end == 0 { + return SearchStep::Done; + } + let is_long = searcher.memory == usize::MAX; + match searcher.next_back::<RejectAndMatch>( + self.haystack.as_bytes(), + self.needle.as_bytes(), + is_long, + ) { + SearchStep::Reject(mut a, b) => { + // skip to next char boundary + while !self.haystack.is_char_boundary(a) { + a -= 1; + } + searcher.end = cmp::min(a, searcher.end); + SearchStep::Reject(a, b) + } + otherwise => otherwise, + } + } + } + } + + #[inline] + fn next_match_back(&mut self) -> Option<(usize, usize)> { + match self.searcher { + StrSearcherImpl::Empty(..) => loop { + match self.next_back() { + SearchStep::Match(a, b) => return Some((a, b)), + SearchStep::Done => return None, + SearchStep::Reject(..) => {} + } + }, + StrSearcherImpl::TwoWay(ref mut searcher) => { + let is_long = searcher.memory == usize::MAX; + // write out `true` and `false`, like `next_match` + if is_long { + searcher.next_back::<MatchOnly>( + self.haystack.as_bytes(), + self.needle.as_bytes(), + true, + ) + } else { + searcher.next_back::<MatchOnly>( + self.haystack.as_bytes(), + self.needle.as_bytes(), + false, + ) + } + } + } + } +} + +/// The internal state of the two-way substring search algorithm. +#[derive(Clone, Debug)] +struct TwoWaySearcher { + // constants + /// critical factorization index + crit_pos: usize, + /// critical factorization index for reversed needle + crit_pos_back: usize, + period: usize, + /// `byteset` is an extension (not part of the two way algorithm); + /// it's a 64-bit "fingerprint" where each set bit `j` corresponds + /// to a (byte & 63) == j present in the needle. + byteset: u64, + + // variables + position: usize, + end: usize, + /// index into needle before which we have already matched + memory: usize, + /// index into needle after which we have already matched + memory_back: usize, +} + +/* + This is the Two-Way search algorithm, which was introduced in the paper: + Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675. + + Here's some background information. + + A *word* is a string of symbols. The *length* of a word should be a familiar + notion, and here we denote it for any word x by |x|. + (We also allow for the possibility of the *empty word*, a word of length zero). + + If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a + *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p]. + For example, both 1 and 2 are periods for the string "aa". As another example, + the only period of the string "abcd" is 4. + + We denote by period(x) the *smallest* period of x (provided that x is non-empty). + This is always well-defined since every non-empty word x has at least one period, + |x|. We sometimes call this *the period* of x. + + If u, v and x are words such that x = uv, where uv is the concatenation of u and + v, then we say that (u, v) is a *factorization* of x. + + Let (u, v) be a factorization for a word x. Then if w is a non-empty word such + that both of the following hold + + - either w is a suffix of u or u is a suffix of w + - either w is a prefix of v or v is a prefix of w + + then w is said to be a *repetition* for the factorization (u, v). + + Just to unpack this, there are four possibilities here. Let w = "abc". Then we + might have: + + - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde") + - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab") + - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi") + - u is a suffix of w and v is a prefix of w. ex: ("bc", "a") + + Note that the word vu is a repetition for any factorization (u,v) of x = uv, + so every factorization has at least one repetition. + + If x is a string and (u, v) is a factorization for x, then a *local period* for + (u, v) is an integer r such that there is some word w such that |w| = r and w is + a repetition for (u, v). + + We denote by local_period(u, v) the smallest local period of (u, v). We sometimes + call this *the local period* of (u, v). Provided that x = uv is non-empty, this + is well-defined (because each non-empty word has at least one factorization, as + noted above). + + It can be proven that the following is an equivalent definition of a local period + for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for + all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are + defined. (i.e., i > 0 and i + r < |x|). + + Using the above reformulation, it is easy to prove that + + 1 <= local_period(u, v) <= period(uv) + + A factorization (u, v) of x such that local_period(u,v) = period(x) is called a + *critical factorization*. + + The algorithm hinges on the following theorem, which is stated without proof: + + **Critical Factorization Theorem** Any word x has at least one critical + factorization (u, v) such that |u| < period(x). + + The purpose of maximal_suffix is to find such a critical factorization. + + If the period is short, compute another factorization x = u' v' to use + for reverse search, chosen instead so that |v'| < period(x). + +*/ +impl TwoWaySearcher { + fn new(needle: &[u8], end: usize) -> TwoWaySearcher { + let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false); + let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true); + + let (crit_pos, period) = if crit_pos_false > crit_pos_true { + (crit_pos_false, period_false) + } else { + (crit_pos_true, period_true) + }; + + // A particularly readable explanation of what's going on here can be found + // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically + // see the code for "Algorithm CP" on p. 323. + // + // What's going on is we have some critical factorization (u, v) of the + // needle, and we want to determine whether u is a suffix of + // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use + // "Algorithm CP2", which is optimized for when the period of the needle + // is large. + if needle[..crit_pos] == needle[period..period + crit_pos] { + // short period case -- the period is exact + // compute a separate critical factorization for the reversed needle + // x = u' v' where |v'| < period(x). + // + // This is sped up by the period being known already. + // Note that a case like x = "acba" may be factored exactly forwards + // (crit_pos = 1, period = 3) while being factored with approximate + // period in reverse (crit_pos = 2, period = 2). We use the given + // reverse factorization but keep the exact period. + let crit_pos_back = needle.len() + - cmp::max( + TwoWaySearcher::reverse_maximal_suffix(needle, period, false), + TwoWaySearcher::reverse_maximal_suffix(needle, period, true), + ); + + TwoWaySearcher { + crit_pos, + crit_pos_back, + period, + byteset: Self::byteset_create(&needle[..period]), + + position: 0, + end, + memory: 0, + memory_back: needle.len(), + } + } else { + // long period case -- we have an approximation to the actual period, + // and don't use memorization. + // + // Approximate the period by lower bound max(|u|, |v|) + 1. + // The critical factorization is efficient to use for both forward and + // reverse search. + + TwoWaySearcher { + crit_pos, + crit_pos_back: crit_pos, + period: cmp::max(crit_pos, needle.len() - crit_pos) + 1, + byteset: Self::byteset_create(needle), + + position: 0, + end, + memory: usize::MAX, // Dummy value to signify that the period is long + memory_back: usize::MAX, + } + } + } + + #[inline] + fn byteset_create(bytes: &[u8]) -> u64 { + bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a) + } + + #[inline] + fn byteset_contains(&self, byte: u8) -> bool { + (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0 + } + + // One of the main ideas of Two-Way is that we factorize the needle into + // two halves, (u, v), and begin trying to find v in the haystack by scanning + // left to right. If v matches, we try to match u by scanning right to left. + // How far we can jump when we encounter a mismatch is all based on the fact + // that (u, v) is a critical factorization for the needle. + #[inline] + fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output + where + S: TwoWayStrategy, + { + // `next()` uses `self.position` as its cursor + let old_pos = self.position; + let needle_last = needle.len() - 1; + 'search: loop { + // Check that we have room to search in + // position + needle_last can not overflow if we assume slices + // are bounded by isize's range. + let tail_byte = match haystack.get(self.position + needle_last) { + Some(&b) => b, + None => { + self.position = haystack.len(); + return S::rejecting(old_pos, self.position); + } + }; + + if S::use_early_reject() && old_pos != self.position { + return S::rejecting(old_pos, self.position); + } + + // Quickly skip by large portions unrelated to our substring + if !self.byteset_contains(tail_byte) { + self.position += needle.len(); + if !long_period { + self.memory = 0; + } + continue 'search; + } + + // See if the right part of the needle matches + let start = + if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) }; + for i in start..needle.len() { + if needle[i] != haystack[self.position + i] { + self.position += i - self.crit_pos + 1; + if !long_period { + self.memory = 0; + } + continue 'search; + } + } + + // See if the left part of the needle matches + let start = if long_period { 0 } else { self.memory }; + for i in (start..self.crit_pos).rev() { + if needle[i] != haystack[self.position + i] { + self.position += self.period; + if !long_period { + self.memory = needle.len() - self.period; + } + continue 'search; + } + } + + // We have found a match! + let match_pos = self.position; + + // Note: add self.period instead of needle.len() to have overlapping matches + self.position += needle.len(); + if !long_period { + self.memory = 0; // set to needle.len() - self.period for overlapping matches + } + + return S::matching(match_pos, match_pos + needle.len()); + } + } + + // Follows the ideas in `next()`. + // + // The definitions are symmetrical, with period(x) = period(reverse(x)) + // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v) + // is a critical factorization, so is (reverse(v), reverse(u)). + // + // For the reverse case we have computed a critical factorization x = u' v' + // (field `crit_pos_back`). We need |u| < period(x) for the forward case and + // thus |v'| < period(x) for the reverse. + // + // To search in reverse through the haystack, we search forward through + // a reversed haystack with a reversed needle, matching first u' and then v'. + #[inline] + fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output + where + S: TwoWayStrategy, + { + // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()` + // are independent. + let old_end = self.end; + 'search: loop { + // Check that we have room to search in + // end - needle.len() will wrap around when there is no more room, + // but due to slice length limits it can never wrap all the way back + // into the length of haystack. + let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) { + Some(&b) => b, + None => { + self.end = 0; + return S::rejecting(0, old_end); + } + }; + + if S::use_early_reject() && old_end != self.end { + return S::rejecting(self.end, old_end); + } + + // Quickly skip by large portions unrelated to our substring + if !self.byteset_contains(front_byte) { + self.end -= needle.len(); + if !long_period { + self.memory_back = needle.len(); + } + continue 'search; + } + + // See if the left part of the needle matches + let crit = if long_period { + self.crit_pos_back + } else { + cmp::min(self.crit_pos_back, self.memory_back) + }; + for i in (0..crit).rev() { + if needle[i] != haystack[self.end - needle.len() + i] { + self.end -= self.crit_pos_back - i; + if !long_period { + self.memory_back = needle.len(); + } + continue 'search; + } + } + + // See if the right part of the needle matches + let needle_end = if long_period { needle.len() } else { self.memory_back }; + for i in self.crit_pos_back..needle_end { + if needle[i] != haystack[self.end - needle.len() + i] { + self.end -= self.period; + if !long_period { + self.memory_back = self.period; + } + continue 'search; + } + } + + // We have found a match! + let match_pos = self.end - needle.len(); + // Note: sub self.period instead of needle.len() to have overlapping matches + self.end -= needle.len(); + if !long_period { + self.memory_back = needle.len(); + } + + return S::matching(match_pos, match_pos + needle.len()); + } + } + + // Compute the maximal suffix of `arr`. + // + // The maximal suffix is a possible critical factorization (u, v) of `arr`. + // + // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the + // period of v. + // + // `order_greater` determines if lexical order is `<` or `>`. Both + // orders must be computed -- the ordering with the largest `i` gives + // a critical factorization. + // + // For long period cases, the resulting period is not exact (it is too short). + #[inline] + fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) { + let mut left = 0; // Corresponds to i in the paper + let mut right = 1; // Corresponds to j in the paper + let mut offset = 0; // Corresponds to k in the paper, but starting at 0 + // to match 0-based indexing. + let mut period = 1; // Corresponds to p in the paper + + while let Some(&a) = arr.get(right + offset) { + // `left` will be inbounds when `right` is. + let b = arr[left + offset]; + if (a < b && !order_greater) || (a > b && order_greater) { + // Suffix is smaller, period is entire prefix so far. + right += offset + 1; + offset = 0; + period = right - left; + } else if a == b { + // Advance through repetition of the current period. + if offset + 1 == period { + right += offset + 1; + offset = 0; + } else { + offset += 1; + } + } else { + // Suffix is larger, start over from current location. + left = right; + right += 1; + offset = 0; + period = 1; + } + } + (left, period) + } + + // Compute the maximal suffix of the reverse of `arr`. + // + // The maximal suffix is a possible critical factorization (u', v') of `arr`. + // + // Returns `i` where `i` is the starting index of v', from the back; + // returns immediately when a period of `known_period` is reached. + // + // `order_greater` determines if lexical order is `<` or `>`. Both + // orders must be computed -- the ordering with the largest `i` gives + // a critical factorization. + // + // For long period cases, the resulting period is not exact (it is too short). + fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize { + let mut left = 0; // Corresponds to i in the paper + let mut right = 1; // Corresponds to j in the paper + let mut offset = 0; // Corresponds to k in the paper, but starting at 0 + // to match 0-based indexing. + let mut period = 1; // Corresponds to p in the paper + let n = arr.len(); + + while right + offset < n { + let a = arr[n - (1 + right + offset)]; + let b = arr[n - (1 + left + offset)]; + if (a < b && !order_greater) || (a > b && order_greater) { + // Suffix is smaller, period is entire prefix so far. + right += offset + 1; + offset = 0; + period = right - left; + } else if a == b { + // Advance through repetition of the current period. + if offset + 1 == period { + right += offset + 1; + offset = 0; + } else { + offset += 1; + } + } else { + // Suffix is larger, start over from current location. + left = right; + right += 1; + offset = 0; + period = 1; + } + if period == known_period { + break; + } + } + debug_assert!(period <= known_period); + left + } +} + +// TwoWayStrategy allows the algorithm to either skip non-matches as quickly +// as possible, or to work in a mode where it emits Rejects relatively quickly. +trait TwoWayStrategy { + type Output; + fn use_early_reject() -> bool; + fn rejecting(a: usize, b: usize) -> Self::Output; + fn matching(a: usize, b: usize) -> Self::Output; +} + +/// Skip to match intervals as quickly as possible +enum MatchOnly {} + +impl TwoWayStrategy for MatchOnly { + type Output = Option<(usize, usize)>; + + #[inline] + fn use_early_reject() -> bool { + false + } + #[inline] + fn rejecting(_a: usize, _b: usize) -> Self::Output { + None + } + #[inline] + fn matching(a: usize, b: usize) -> Self::Output { + Some((a, b)) + } +} + +/// Emit Rejects regularly +enum RejectAndMatch {} + +impl TwoWayStrategy for RejectAndMatch { + type Output = SearchStep; + + #[inline] + fn use_early_reject() -> bool { + true + } + #[inline] + fn rejecting(a: usize, b: usize) -> Self::Output { + SearchStep::Reject(a, b) + } + #[inline] + fn matching(a: usize, b: usize) -> Self::Output { + SearchStep::Match(a, b) + } +} |