//! 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));//! // 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]/// 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)Lines 1–500 of 1598. Load more
//! 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)); //! // 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] /// 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)