library/core/src/str/pattern.rs

   1 //! The string Pattern API.
   2 //!
   3 //! The Pattern API provides a generic mechanism for using different pattern
   4 //! types when searching through a string.
   5 //!
   6 //! For more details, see the traits [`Pattern`], [`Searcher`],
   7 //! [`ReverseSearcher`], and [`DoubleEndedSearcher`].
   8 //!
   9 //! Although this API is unstable, it is exposed via stable APIs on the
  10 //! [`str`] type.
  11 //!
  12 //! # Examples
  13 //!
  14 //! [`Pattern`] is [implemented][pattern-impls] in the stable API for
  15 //! [`&str`][`str`], [`char`], slices of [`char`], and functions and closures
  16 //! implementing `FnMut(char) -> bool`.
  17 //!
  18 //! ```
  19 //! let s = "Can you find a needle in a haystack?";
  20 //!
  21 //! // &str pattern
  22 //! assert_eq!(s.find("you"), Some(4));
  23 //! // char pattern
  24 //! assert_eq!(s.find('n'), Some(2));
  25 //! // array of chars pattern
  26 //! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u']), Some(1));
  27 //! // slice of chars pattern
  28 //! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u'][..]), Some(1));
  29 //! // closure pattern
  30 //! assert_eq!(s.find(|c: char| c.is_ascii_punctuation()), Some(35));
  31 //! ```
  32 //!
  33 //! [pattern-impls]: Pattern#implementors
  34
  35 #![unstable(
  36     feature = "pattern",
  37     reason = "API not fully fleshed out and ready to be stabilized",
  38     issue = "27721"
  39 )]
  40
  41 use crate::cmp;
  42 use crate::fmt;
  43 use crate::slice::memchr;
  44
  45 // Pattern
  46
  47 /// A string pattern.
  48 ///
  49 /// A `Pattern<'a>` expresses that the implementing type
  50 /// can be used as a string pattern for searching in a [`&'a str`][str].
  51 ///
  52 /// For example, both `'a'` and `"aa"` are patterns that
  53 /// would match at index `1` in the string `"baaaab"`.
  54 ///
  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.
  58 ///
  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.
  62 ///
  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                              |
  71 ///
  72 /// # Examples
  73 ///
  74 /// ```
  75 /// // &str
  76 /// assert_eq!("abaaa".find("ba"), Some(1));
  77 /// assert_eq!("abaaa".find("bac"), None);
  78 ///
  79 /// // char
  80 /// assert_eq!("abaaa".find('a'), Some(0));
  81 /// assert_eq!("abaaa".find('b'), Some(1));
  82 /// assert_eq!("abaaa".find('c'), None);
  83 ///
  84 /// // &[char; N]
  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);
  88 ///
  89 /// // &[char]
  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);
  93 ///
  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);
  97 /// ```
  98 pub trait Pattern<'a>: Sized {
  99     /// Associated searcher for this pattern
 100     type Searcher: Searcher<'a>;
 101
 102     /// Constructs the associated searcher from
 103     /// `self` and the `haystack` to search in.
 104     fn into_searcher(self, haystack: &'a str) -> Self::Searcher;
 105
 106     /// Checks whether the pattern matches anywhere in the haystack
 107     #[inline]
 108     fn is_contained_in(self, haystack: &'a str) -> bool {
 109         self.into_searcher(haystack).next_match().is_some()
 110     }
 111
 112     /// Checks whether the pattern matches at the front of the haystack
 113     #[inline]
 114     fn is_prefix_of(self, haystack: &'a str) -> bool {
 115         matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
 116     }
 117
 118     /// Checks whether the pattern matches at the back of the haystack
 119     #[inline]
 120     fn is_suffix_of(self, haystack: &'a str) -> bool
 121     where
 122         Self::Searcher: ReverseSearcher<'a>,
 123     {
 124         matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
 125     }
 126
 127     /// Removes the pattern from the front of haystack, if it matches.
 128     #[inline]
 129     fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
 130         if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() {
 131             debug_assert_eq!(
 132                 start, 0,
 133                 "The first search step from Searcher \
 134                  must include the first character"
 135             );
 136             // SAFETY: `Searcher` is known to return valid indices.
 137             unsafe { Some(haystack.get_unchecked(len..)) }
 138         } else {
 139             None
 140         }
 141     }
 142
 143     /// Removes the pattern from the back of haystack, if it matches.
 144     #[inline]
 145     fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
 146     where
 147         Self::Searcher: ReverseSearcher<'a>,
 148     {
 149         if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() {
 150             debug_assert_eq!(
 151                 end,
 152                 haystack.len(),
 153                 "The first search step from ReverseSearcher \
 154                  must include the last character"
 155             );
 156             // SAFETY: `Searcher` is known to return valid indices.
 157             unsafe { Some(haystack.get_unchecked(..start)) }
 158         } else {
 159             None
 160         }
 161     }
 162 }
 163
 164 // Searcher
 165
 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]`.
 171     Match(usize, usize),
 172     /// Expresses that `haystack[a..b]` has been rejected as a possible match
 173     /// of the pattern.
 174     ///
 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
 179     /// the iteration.
 180     Done,
 181 }
 182
 183 /// A searcher for a string pattern.
 184 ///
 185 /// This trait provides methods for searching for non-overlapping
 186 /// matches of a pattern starting from the front (left) of a string.
 187 ///
 188 /// It will be implemented by associated `Searcher`
 189 /// types of the [`Pattern`] trait.
 190 ///
 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
 197     ///
 198     /// Will always return the same [`&str`][str].
 199     fn haystack(&self) -> &'a str;
 200
 201     /// Performs the next search step starting from the front.
 202     ///
 203     /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches
 204     ///   the pattern.
 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
 208     ///   been visited.
 209     ///
 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.
 214     ///
 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.
 218     ///
 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;
 223
 224     /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next].
 225     ///
 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.
 230     #[inline]
 231     fn next_match(&mut self) -> Option<(usize, usize)> {
 232         loop {
 233             match self.next() {
 234                 SearchStep::Match(a, b) => return Some((a, b)),
 235                 SearchStep::Done => return None,
 236                 _ => continue,
 237             }
 238         }
 239     }
 240
 241     /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next]
 242     /// and [`next_match()`][Searcher::next_match].
 243     ///
 244     /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
 245     /// of this and [`next_match`][Searcher::next_match] will overlap.
 246     #[inline]
 247     fn next_reject(&mut self) -> Option<(usize, usize)> {
 248         loop {
 249             match self.next() {
 250                 SearchStep::Reject(a, b) => return Some((a, b)),
 251                 SearchStep::Done => return None,
 252                 _ => continue,
 253             }
 254         }
 255     }
 256 }
 257
 258 /// A reverse searcher for a string pattern.
 259 ///
 260 /// This trait provides methods for searching for non-overlapping
 261 /// matches of a pattern starting from the back (right) of a string.
 262 ///
 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.
 266 ///
 267 /// The index ranges returned by this trait are not required
 268 /// to exactly match those of the forward search in reverse.
 269 ///
 270 /// For the reason why this trait is marked unsafe, see the
 271 /// parent trait [`Searcher`].
 272 pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
 273     /// Performs the next search step starting from the back.
 274     ///
 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
 280     ///   has been visited
 281     ///
 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.
 286     ///
 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.
 290     ///
 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;
 295
 296     /// Finds the next [`Match`][SearchStep::Match] result.
 297     /// See [`next_back()`][ReverseSearcher::next_back].
 298     #[inline]
 299     fn next_match_back(&mut self) -> Option<(usize, usize)> {
 300         loop {
 301             match self.next_back() {
 302                 SearchStep::Match(a, b) => return Some((a, b)),
 303                 SearchStep::Done => return None,
 304                 _ => continue,
 305             }
 306         }
 307     }
 308
 309     /// Finds the next [`Reject`][SearchStep::Reject] result.
 310     /// See [`next_back()`][ReverseSearcher::next_back].
 311     #[inline]
 312     fn next_reject_back(&mut self) -> Option<(usize, usize)> {
 313         loop {
 314             match self.next_back() {
 315                 SearchStep::Reject(a, b) => return Some((a, b)),
 316                 SearchStep::Done => return None,
 317                 _ => continue,
 318             }
 319         }
 320     }
 321 }
 322
 323 /// A marker trait to express that a [`ReverseSearcher`]
 324 /// can be used for a [`DoubleEndedIterator`] implementation.
 325 ///
 326 /// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need
 327 /// to follow these conditions:
 328 ///
 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".
 334 ///
 335 /// # Examples
 336 ///
 337 /// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
 338 /// [`char`] only requires looking at one at a time, which behaves the same
 339 /// from both ends.
 340 ///
 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> {}
 345
 346 /////////////////////////////////////////////////////////////////////////////
 347 // Impl for char
 348 /////////////////////////////////////////////////////////////////////////////
 349
 350 /// Associated type for `<char as Pattern<'a>>::Searcher`.
 351 #[derive(Clone, Debug)]
 352 pub struct CharSearcher<'a> {
 353     haystack: &'a str,
 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
 361     finger: usize,
 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()).
 366     finger_back: usize,
 367     /// The character being searched for
 368     needle: char,
 369
 370     // safety invariant: `utf8_size` must be less than 5
 371     /// The number of bytes `needle` takes up when encoded in utf8.
 372     utf8_size: usize,
 373     /// A utf8 encoded copy of the `needle`
 374     utf8_encoded: [u8; 4],
 375 }
 376
 377 unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
 378     #[inline]
 379     fn haystack(&self) -> &'a str {
 380         self.haystack
 381     }
 382     #[inline]
 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)
 402             } else {
 403                 SearchStep::Reject(old_finger, self.finger)
 404             }
 405         } else {
 406             SearchStep::Done
 407         }
 408     }
 409     #[inline]
 410     fn next_match(&mut self) -> Option<(usize, usize)> {
 411         loop {
 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.
 420                 //
 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.
 427                 //
 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()).
 431                 //
 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));
 441                         }
 442                     }
 443                 }
 444             } else {
 445                 // found nothing, exit
 446                 self.finger = self.finger_back;
 447                 return None;
 448             }
 449         }
 450     }
 451
 452     // let next_reject use the default implementation from the Searcher trait
 453 }
 454
 455 unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
 456     #[inline]
 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)
 469             } else {
 470                 SearchStep::Reject(self.finger_back, old_finger)
 471             }
 472         } else {
 473             SearchStep::Done
 474         }
 475     }
 476     #[inline]
 477     fn next_match_back(&mut self) -> Option<(usize, usize)> {
 478         let haystack = self.haystack.as_bytes();
 479         loop {
 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;
 496                 if index >= shift {
 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));
 503                         }
 504                     }
 505                 }
 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.
 512                 //
 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;
 518             } else {
 519                 self.finger_back = self.finger;
 520                 // found nothing, exit
 521                 return None;
 522             }
 523         }
 524     }
 525
 526     // let next_reject_back use the default implementation from the Searcher trait
 527 }
 528
 529 impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
 530
 531 /// Searches for chars that are equal to a given [`char`].
 532 ///
 533 /// # Examples
 534 ///
 535 /// ```
 536 /// assert_eq!("Hello world".find('o'), Some(4));
 537 /// ```
 538 impl<'a> Pattern<'a> for char {
 539     type Searcher = CharSearcher<'a>;
 540
 541     #[inline]
 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();
 545         CharSearcher {
 546             haystack,
 547             finger: 0,
 548             finger_back: haystack.len(),
 549             needle: self,
 550             utf8_size,
 551             utf8_encoded,
 552         }
 553     }
 554
 555     #[inline]
 556     fn is_contained_in(self, haystack: &'a str) -> bool {
 557         if (self as u32) < 128 {
 558             haystack.as_bytes().contains(&(self as u8))
 559         } else {
 560             let mut buffer = [0u8; 4];
 561             self.encode_utf8(&mut buffer).is_contained_in(haystack)
 562         }
 563     }
 564
 565     #[inline]
 566     fn is_prefix_of(self, haystack: &'a str) -> bool {
 567         self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
 568     }
 569
 570     #[inline]
 571     fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
 572         self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack)
 573     }
 574
 575     #[inline]
 576     fn is_suffix_of(self, haystack: &'a str) -> bool
 577     where
 578         Self::Searcher: ReverseSearcher<'a>,
 579     {
 580         self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
 581     }
 582
 583     #[inline]
 584     fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
 585     where
 586         Self::Searcher: ReverseSearcher<'a>,
 587     {
 588         self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack)
 589     }
 590 }
 591
 592 /////////////////////////////////////////////////////////////////////////////
 593 // Impl for a MultiCharEq wrapper
 594 /////////////////////////////////////////////////////////////////////////////
 595
 596 #[doc(hidden)]
 597 trait MultiCharEq {
 598     fn matches(&mut self, c: char) -> bool;
 599 }
 600
 601 impl<F> MultiCharEq for F
 602 where
 603     F: FnMut(char) -> bool,
 604 {
 605     #[inline]
 606     fn matches(&mut self, c: char) -> bool {
 607         (*self)(c)
 608     }
 609 }
 610
 611 impl<const N: usize> MultiCharEq for [char; N] {
 612     #[inline]
 613     fn matches(&mut self, c: char) -> bool {
 614         self.iter().any(|&m| m == c)
 615     }
 616 }
 617
 618 impl<const N: usize> MultiCharEq for &[char; N] {
 619     #[inline]
 620     fn matches(&mut self, c: char) -> bool {
 621         self.iter().any(|&m| m == c)
 622     }
 623 }
 624
 625 impl MultiCharEq for &[char] {
 626     #[inline]
 627     fn matches(&mut self, c: char) -> bool {
 628         self.iter().any(|&m| m == c)
 629     }
 630 }
 631
 632 struct MultiCharEqPattern<C: MultiCharEq>(C);
 633
 634 #[derive(Clone, Debug)]
 635 struct MultiCharEqSearcher<'a, C: MultiCharEq> {
 636     char_eq: C,
 637     haystack: &'a str,
 638     char_indices: super::CharIndices<'a>,
 639 }
 640
 641 impl<'a, C: MultiCharEq> Pattern<'a> for MultiCharEqPattern<C> {
 642     type Searcher = MultiCharEqSearcher<'a, C>;
 643
 644     #[inline]
 645     fn into_searcher(self, haystack: &'a str) -> MultiCharEqSearcher<'a, C> {
 646         MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
 647     }
 648 }
 649
 650 unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
 651     #[inline]
 652     fn haystack(&self) -> &'a str {
 653         self.haystack
 654     }
 655
 656     #[inline]
 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);
 667             } else {
 668                 return SearchStep::Reject(i, i + char_len);
 669             }
 670         }
 671         SearchStep::Done
 672     }
 673 }
 674
 675 unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
 676     #[inline]
 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);
 687             } else {
 688                 return SearchStep::Reject(i, i + char_len);
 689             }
 690         }
 691         SearchStep::Done
 692     }
 693 }
 694
 695 impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}
 696
 697 /////////////////////////////////////////////////////////////////////////////
 698
 699 macro_rules! pattern_methods {
 700     ($t:ty, $pmap:expr, $smap:expr) => {
 701         type Searcher = $t;
 702
 703         #[inline]
 704         fn into_searcher(self, haystack: &'a str) -> $t {
 705             ($smap)(($pmap)(self).into_searcher(haystack))
 706         }
 707
 708         #[inline]
 709         fn is_contained_in(self, haystack: &'a str) -> bool {
 710             ($pmap)(self).is_contained_in(haystack)
 711         }
 712
 713         #[inline]
 714         fn is_prefix_of(self, haystack: &'a str) -> bool {
 715             ($pmap)(self).is_prefix_of(haystack)
 716         }
 717
 718         #[inline]
 719         fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
 720             ($pmap)(self).strip_prefix_of(haystack)
 721         }
 722
 723         #[inline]
 724         fn is_suffix_of(self, haystack: &'a str) -> bool
 725         where
 726             $t: ReverseSearcher<'a>,
 727         {
 728             ($pmap)(self).is_suffix_of(haystack)
 729         }
 730
 731         #[inline]
 732         fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
 733         where
 734             $t: ReverseSearcher<'a>,
 735         {
 736             ($pmap)(self).strip_suffix_of(haystack)
 737         }
 738     };
 739 }
 740
 741 macro_rules! searcher_methods {
 742     (forward) => {
 743         #[inline]
 744         fn haystack(&self) -> &'a str {
 745             self.0.haystack()
 746         }
 747         #[inline]
 748         fn next(&mut self) -> SearchStep {
 749             self.0.next()
 750         }
 751         #[inline]
 752         fn next_match(&mut self) -> Option<(usize, usize)> {
 753             self.0.next_match()
 754         }
 755         #[inline]
 756         fn next_reject(&mut self) -> Option<(usize, usize)> {
 757             self.0.next_reject()
 758         }
 759     };
 760     (reverse) => {
 761         #[inline]
 762         fn next_back(&mut self) -> SearchStep {
 763             self.0.next_back()
 764         }
 765         #[inline]
 766         fn next_match_back(&mut self) -> Option<(usize, usize)> {
 767             self.0.next_match_back()
 768         }
 769         #[inline]
 770         fn next_reject_back(&mut self) -> Option<(usize, usize)> {
 771             self.0.next_reject_back()
 772         }
 773     };
 774 }
 775
 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,
 780 );
 781
 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,
 786 );
 787
 788 /// Searches for chars that are equal to any of the [`char`]s in the array.
 789 ///
 790 /// # Examples
 791 ///
 792 /// ```
 793 /// assert_eq!("Hello world".find(['l', 'l']), Some(2));
 794 /// assert_eq!("Hello world".find(['l', 'l']), Some(2));
 795 /// ```
 796 impl<'a, const N: usize> Pattern<'a> for [char; N] {
 797     pattern_methods!(CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher);
 798 }
 799
 800 unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> {
 801     searcher_methods!(forward);
 802 }
 803
 804 unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> {
 805     searcher_methods!(reverse);
 806 }
 807
 808 /// Searches for chars that are equal to any of the [`char`]s in the array.
 809 ///
 810 /// # Examples
 811 ///
 812 /// ```
 813 /// assert_eq!("Hello world".find(&['l', 'l']), Some(2));
 814 /// assert_eq!("Hello world".find(&['l', 'l']), Some(2));
 815 /// ```
 816 impl<'a, 'b, const N: usize> Pattern<'a> for &'b [char; N] {
 817     pattern_methods!(CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher);
 818 }
 819
 820 unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
 821     searcher_methods!(forward);
 822 }
 823
 824 unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
 825     searcher_methods!(reverse);
 826 }
 827
 828 /////////////////////////////////////////////////////////////////////////////
 829 // Impl for &[char]
 830 /////////////////////////////////////////////////////////////////////////////
 831
 832 // Todo: Change / Remove due to ambiguity in meaning.
 833
 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);
 837
 838 unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
 839     searcher_methods!(forward);
 840 }
 841
 842 unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
 843     searcher_methods!(reverse);
 844 }
 845
 846 impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
 847
 848 /// Searches for chars that are equal to any of the [`char`]s in the slice.
 849 ///
 850 /// # Examples
 851 ///
 852 /// ```
 853 /// assert_eq!("Hello world".find(&['l', 'l'] as &[_]), Some(2));
 854 /// assert_eq!("Hello world".find(&['l', 'l'][..]), Some(2));
 855 /// ```
 856 impl<'a, 'b> Pattern<'a> for &'b [char] {
 857     pattern_methods!(CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
 858 }
 859
 860 /////////////////////////////////////////////////////////////////////////////
 861 // Impl for F: FnMut(char) -> bool
 862 /////////////////////////////////////////////////////////////////////////////
 863
 864 /// Associated type for `<F as Pattern<'a>>::Searcher`.
 865 #[derive(Clone)]
 866 pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern<'a>>::Searcher)
 867 where
 868     F: FnMut(char) -> bool;
 869
 870 impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
 871 where
 872     F: FnMut(char) -> bool,
 873 {
 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)
 878             .finish()
 879     }
 880 }
 881 unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
 882 where
 883     F: FnMut(char) -> bool,
 884 {
 885     searcher_methods!(forward);
 886 }
 887
 888 unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
 889 where
 890     F: FnMut(char) -> bool,
 891 {
 892     searcher_methods!(reverse);
 893 }
 894
 895 impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}
 896
 897 /// Searches for [`char`]s that match the given predicate.
 898 ///
 899 /// # Examples
 900 ///
 901 /// ```
 902 /// assert_eq!("Hello world".find(char::is_uppercase), Some(0));
 903 /// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1));
 904 /// ```
 905 impl<'a, F> Pattern<'a> for F
 906 where
 907     F: FnMut(char) -> bool,
 908 {
 909     pattern_methods!(CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
 910 }
 911
 912 /////////////////////////////////////////////////////////////////////////////
 913 // Impl for &&str
 914 /////////////////////////////////////////////////////////////////////////////
 915
 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);
 919 }
 920
 921 /////////////////////////////////////////////////////////////////////////////
 922 // Impl for &str
 923 /////////////////////////////////////////////////////////////////////////////
 924
 925 /// Non-allocating substring search.
 926 ///
 927 /// Will handle the pattern `""` as returning empty matches at each character
 928 /// boundary.
 929 ///
 930 /// # Examples
 931 ///
 932 /// ```
 933 /// assert_eq!("Hello world".find("world"), Some(6));
 934 /// ```
 935 impl<'a, 'b> Pattern<'a> for &'b str {
 936     type Searcher = StrSearcher<'a, 'b>;
 937
 938     #[inline]
 939     fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> {
 940         StrSearcher::new(haystack, self)
 941     }
 942
 943     /// Checks whether the pattern matches at the front of the haystack.
 944     #[inline]
 945     fn is_prefix_of(self, haystack: &'a str) -> bool {
 946         haystack.as_bytes().starts_with(self.as_bytes())
 947     }
 948
 949     /// Removes the pattern from the front of haystack, if it matches.
 950     #[inline]
 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()..)) }
 955         } else {
 956             None
 957         }
 958     }
 959
 960     /// Checks whether the pattern matches at the back of the haystack.
 961     #[inline]
 962     fn is_suffix_of(self, haystack: &'a str) -> bool {
 963         haystack.as_bytes().ends_with(self.as_bytes())
 964     }
 965
 966     /// Removes the pattern from the back of haystack, if it matches.
 967     #[inline]
 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)) }
 973         } else {
 974             None
 975         }
 976     }
 977 }
 978
 979 /////////////////////////////////////////////////////////////////////////////
 980 // Two Way substring searcher
 981 /////////////////////////////////////////////////////////////////////////////
 982
 983 #[derive(Clone, Debug)]
 984 /// Associated type for `<&str as Pattern<'a>>::Searcher`.
 985 pub struct StrSearcher<'a, 'b> {
 986     haystack: &'a str,
 987     needle: &'b str,
 988
 989     searcher: StrSearcherImpl,
 990 }
 991
 992 #[derive(Clone, Debug)]
 993 enum StrSearcherImpl {
 994     Empty(EmptyNeedle),
 995     TwoWay(TwoWaySearcher),
 996 }
 997
 998 #[derive(Clone, Debug)]
 999 struct EmptyNeedle {
1000     position: usize,
1001     end: usize,
1002     is_match_fw: bool,
1003     is_match_bw: bool,
1004     // Needed in case of an empty haystack, see #85462
1005     is_finished: bool,
1006 }
1007
1008 impl<'a, 'b> StrSearcher<'a, 'b> {
1009     fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
1010         if needle.is_empty() {
1011             StrSearcher {
1012                 haystack,
1013                 needle,
1014                 searcher: StrSearcherImpl::Empty(EmptyNeedle {
1015                     position: 0,
1016                     end: haystack.len(),
1017                     is_match_fw: true,
1018                     is_match_bw: true,
1019                     is_finished: false,
1020                 }),
1021             }
1022         } else {
1023             StrSearcher {
1024                 haystack,
1025                 needle,
1026                 searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
1027                     needle.as_bytes(),
1028                     haystack.len(),
1029                 )),
1030             }
1031         }
1032     }
1033 }
1034
1035 unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
1036     #[inline]
1037     fn haystack(&self) -> &'a str {
1038         self.haystack
1039     }
1040
1041     #[inline]
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;
1047                 }
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),
1054                     None => {
1055                         searcher.is_finished = true;
1056                         SearchStep::Done
1057                     }
1058                     Some(ch) => {
1059                         searcher.position += ch.len_utf8();
1060                         SearchStep::Reject(pos, searcher.position)
1061                     }
1062                 }
1063             }
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
1067                 // valid UTF-8
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;
1072                 }
1073                 let is_long = searcher.memory == usize::MAX;
1074                 match searcher.next::<RejectAndMatch>(
1075                     self.haystack.as_bytes(),
1076                     self.needle.as_bytes(),
1077                     is_long,
1078                 ) {
1079                     SearchStep::Reject(a, mut b) => {
1080                         // skip to next char boundary
1081                         while !self.haystack.is_char_boundary(b) {
1082                             b += 1;
1083                         }
1084                         searcher.position = cmp::max(b, searcher.position);
1085                         SearchStep::Reject(a, b)
1086                     }
1087                     otherwise => otherwise,
1088                 }
1089             }
1090         }
1091     }
1092
1093     #[inline]
1094     fn next_match(&mut self) -> Option<(usize, usize)> {
1095         match self.searcher {
1096             StrSearcherImpl::Empty(..) => loop {
1097                 match self.next() {
1098                     SearchStep::Match(a, b) => return Some((a, b)),
1099                     SearchStep::Done => return None,
1100                     SearchStep::Reject(..) => {}
1101                 }
1102             },
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.
1107                 if is_long {
1108                     searcher.next::<MatchOnly>(
1109                         self.haystack.as_bytes(),
1110                         self.needle.as_bytes(),
1111                         true,
1112                     )
1113                 } else {
1114                     searcher.next::<MatchOnly>(
1115                         self.haystack.as_bytes(),
1116                         self.needle.as_bytes(),
1117                         false,
1118                     )
1119                 }
1120             }
1121         }
1122     }
1123 }
1124
1125 unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
1126     #[inline]
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;
1132                 }
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),
1138                     None => {
1139                         searcher.is_finished = true;
1140                         SearchStep::Done
1141                     }
1142                     Some(ch) => {
1143                         searcher.end -= ch.len_utf8();
1144                         SearchStep::Reject(searcher.end, end)
1145                     }
1146                 }
1147             }
1148             StrSearcherImpl::TwoWay(ref mut searcher) => {
1149                 if searcher.end == 0 {
1150                     return SearchStep::Done;
1151                 }
1152                 let is_long = searcher.memory == usize::MAX;
1153                 match searcher.next_back::<RejectAndMatch>(
1154                     self.haystack.as_bytes(),
1155                     self.needle.as_bytes(),
1156                     is_long,
1157                 ) {
1158                     SearchStep::Reject(mut a, b) => {
1159                         // skip to next char boundary
1160                         while !self.haystack.is_char_boundary(a) {
1161                             a -= 1;
1162                         }
1163                         searcher.end = cmp::min(a, searcher.end);
1164                         SearchStep::Reject(a, b)
1165                     }
1166                     otherwise => otherwise,
1167                 }
1168             }
1169         }
1170     }
1171
1172     #[inline]
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(..) => {}
1180                 }
1181             },
1182             StrSearcherImpl::TwoWay(ref mut searcher) => {
1183                 let is_long = searcher.memory == usize::MAX;
1184                 // write out `true` and `false`, like `next_match`
1185                 if is_long {
1186                     searcher.next_back::<MatchOnly>(
1187                         self.haystack.as_bytes(),
1188                         self.needle.as_bytes(),
1189                         true,
1190                     )
1191                 } else {
1192                     searcher.next_back::<MatchOnly>(
1193                         self.haystack.as_bytes(),
1194                         self.needle.as_bytes(),
1195                         false,
1196                     )
1197                 }
1198             }
1199         }
1200     }
1201 }
1202
1203 /// The internal state of the two-way substring search algorithm.
1204 #[derive(Clone, Debug)]
1205 struct TwoWaySearcher {
1206     // constants
1207     /// critical factorization index
1208     crit_pos: usize,
1209     /// critical factorization index for reversed needle
1210     crit_pos_back: usize,
1211     period: 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.
1215     byteset: u64,
1216
1217     // variables
1218     position: usize,
1219     end: usize,
1220     /// index into needle before which we have already matched
1221     memory: usize,
1222     /// index into needle after which we have already matched
1223     memory_back: usize,
1224 }
1225
1226 /*
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.
1229
1230     Here's some background information.
1231
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).
1235
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.
1240
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.
1244
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.
1247
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
1250
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
1253
1254     then w is said to be a *repetition* for the factorization (u, v).
1255
1256     Just to unpack this, there are four possibilities here. Let w = "abc". Then we
1257     might have:
1258
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")
1263
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.
1266
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).
1270
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
1274     noted above).
1275
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|).
1280
1281     Using the above reformulation, it is easy to prove that
1282
1283         1 <= local_period(u, v) <= period(uv)
1284
1285     A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
1286     *critical factorization*.
1287
1288     The algorithm hinges on the following theorem, which is stated without proof:
1289
1290     **Critical Factorization Theorem** Any word x has at least one critical
1291     factorization (u, v) such that |u| < period(x).
1292
1293     The purpose of maximal_suffix is to find such a critical factorization.
1294
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).
1297
1298 */
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);
1303
1304         let (crit_pos, period) = if crit_pos_false > crit_pos_true {
1305             (crit_pos_false, period_false)
1306         } else {
1307             (crit_pos_true, period_true)
1308         };
1309
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.
1313         //
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
1318         // is large.
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).
1323             //
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()
1330                 - cmp::max(
1331                     TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
1332                     TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
1333                 );
1334
1335             TwoWaySearcher {
1336                 crit_pos,
1337                 crit_pos_back,
1338                 period,
1339                 byteset: Self::byteset_create(&needle[..period]),
1340
1341                 position: 0,
1342                 end,
1343                 memory: 0,
1344                 memory_back: needle.len(),
1345             }
1346         } else {
1347             // long period case -- we have an approximation to the actual period,
1348             // and don't use memorization.
1349             //
1350             // Approximate the period by lower bound max(|u|, |v|) + 1.
1351             // The critical factorization is efficient to use for both forward and
1352             // reverse search.
1353
1354             TwoWaySearcher {
1355                 crit_pos,
1356                 crit_pos_back: crit_pos,
1357                 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
1358                 byteset: Self::byteset_create(needle),
1359
1360                 position: 0,
1361                 end,
1362                 memory: usize::MAX, // Dummy value to signify that the period is long
1363                 memory_back: usize::MAX,
1364             }
1365         }
1366     }
1367
1368     #[inline]
1369     fn byteset_create(bytes: &[u8]) -> u64 {
1370         bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
1371     }
1372
1373     #[inline]
1374     fn byteset_contains(&self, byte: u8) -> bool {
1375         (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
1376     }
1377
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.
1383     #[inline]
1384     fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1385     where
1386         S: TwoWayStrategy,
1387     {
1388         // `next()` uses `self.position` as its cursor
1389         let old_pos = self.position;
1390         let needle_last = needle.len() - 1;
1391         'search: loop {
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) {
1396                 Some(&b) => b,
1397                 None => {
1398                     self.position = haystack.len();
1399                     return S::rejecting(old_pos, self.position);
1400                 }
1401             };
1402
1403             if S::use_early_reject() && old_pos != self.position {
1404                 return S::rejecting(old_pos, self.position);
1405             }
1406
1407             // Quickly skip by large portions unrelated to our substring
1408             if !self.byteset_contains(tail_byte) {
1409                 self.position += needle.len();
1410                 if !long_period {
1411                     self.memory = 0;
1412                 }
1413                 continue 'search;
1414             }
1415
1416             // See if the right part of the needle matches
1417             let start =
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;
1422                     if !long_period {
1423                         self.memory = 0;
1424                     }
1425                     continue 'search;
1426                 }
1427             }
1428
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;
1434                     if !long_period {
1435                         self.memory = needle.len() - self.period;
1436                     }
1437                     continue 'search;
1438                 }
1439             }
1440
1441             // We have found a match!
1442             let match_pos = self.position;
1443
1444             // Note: add self.period instead of needle.len() to have overlapping matches
1445             self.position += needle.len();
1446             if !long_period {
1447                 self.memory = 0; // set to needle.len() - self.period for overlapping matches
1448             }
1449
1450             return S::matching(match_pos, match_pos + needle.len());
1451         }
1452     }
1453
1454     // Follows the ideas in `next()`.
1455     //
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)).
1459     //
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.
1463     //
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'.
1466     #[inline]
1467     fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1468     where
1469         S: TwoWayStrategy,
1470     {
1471         // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1472         // are independent.
1473         let old_end = self.end;
1474         'search: loop {
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())) {
1480                 Some(&b) => b,
1481                 None => {
1482                     self.end = 0;
1483                     return S::rejecting(0, old_end);
1484                 }
1485             };
1486
1487             if S::use_early_reject() && old_end != self.end {
1488                 return S::rejecting(self.end, old_end);
1489             }
1490
1491             // Quickly skip by large portions unrelated to our substring
1492             if !self.byteset_contains(front_byte) {
1493                 self.end -= needle.len();
1494                 if !long_period {
1495                     self.memory_back = needle.len();
1496                 }
1497                 continue 'search;
1498             }
1499
1500             // See if the left part of the needle matches
1501             let crit = if long_period {
1502                 self.crit_pos_back
1503             } else {
1504                 cmp::min(self.crit_pos_back, self.memory_back)
1505             };
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;
1509                     if !long_period {
1510                         self.memory_back = needle.len();
1511                     }
1512                     continue 'search;
1513                 }
1514             }
1515
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;
1521                     if !long_period {
1522                         self.memory_back = self.period;
1523                     }
1524                     continue 'search;
1525                 }
1526             }
1527
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();
1532             if !long_period {
1533                 self.memory_back = needle.len();
1534             }
1535
1536             return S::matching(match_pos, match_pos + needle.len());
1537         }
1538     }
1539
1540     // Compute the maximal suffix of `arr`.
1541     //
1542     // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1543     //
1544     // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1545     // period of v.
1546     //
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.
1550     //
1551     // For long period cases, the resulting period is not exact (it is too short).
1552     #[inline]
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
1559
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;
1566                 offset = 0;
1567                 period = right - left;
1568             } else if a == b {
1569                 // Advance through repetition of the current period.
1570                 if offset + 1 == period {
1571                     right += offset + 1;
1572                     offset = 0;
1573                 } else {
1574                     offset += 1;
1575                 }
1576             } else {
1577                 // Suffix is larger, start over from current location.
1578                 left = right;
1579                 right += 1;
1580                 offset = 0;
1581                 period = 1;
1582             }
1583         }
1584         (left, period)
1585     }
1586
1587     // Compute the maximal suffix of the reverse of `arr`.
1588     //
1589     // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1590     //
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.
1593     //
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.
1597     //
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
1605         let n = arr.len();
1606
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;
1613                 offset = 0;
1614                 period = right - left;
1615             } else if a == b {
1616                 // Advance through repetition of the current period.
1617                 if offset + 1 == period {
1618                     right += offset + 1;
1619                     offset = 0;
1620                 } else {
1621                     offset += 1;
1622                 }
1623             } else {
1624                 // Suffix is larger, start over from current location.
1625                 left = right;
1626                 right += 1;
1627                 offset = 0;
1628                 period = 1;
1629             }
1630             if period == known_period {
1631                 break;
1632             }
1633         }
1634         debug_assert!(period <= known_period);
1635         left
1636     }
1637 }
1638
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 {
1642     type Output;
1643     fn use_early_reject() -> bool;
1644     fn rejecting(a: usize, b: usize) -> Self::Output;
1645     fn matching(a: usize, b: usize) -> Self::Output;
1646 }
1647
1648 /// Skip to match intervals as quickly as possible
1649 enum MatchOnly {}
1650
1651 impl TwoWayStrategy for MatchOnly {
1652     type Output = Option<(usize, usize)>;
1653
1654     #[inline]
1655     fn use_early_reject() -> bool {
1656         false
1657     }
1658     #[inline]
1659     fn rejecting(_a: usize, _b: usize) -> Self::Output {
1660         None
1661     }
1662     #[inline]
1663     fn matching(a: usize, b: usize) -> Self::Output {
1664         Some((a, b))
1665     }
1666 }
1667
1668 /// Emit Rejects regularly
1669 enum RejectAndMatch {}
1670
1671 impl TwoWayStrategy for RejectAndMatch {
1672     type Output = SearchStep;
1673
1674     #[inline]
1675     fn use_early_reject() -> bool {
1676         true
1677     }
1678     #[inline]
1679     fn rejecting(a: usize, b: usize) -> Self::Output {
1680         SearchStep::Reject(a, b)
1681     }
1682     #[inline]
1683     fn matching(a: usize, b: usize) -> Self::Output {
1684         SearchStep::Match(a, b)
1685     }
1686 }