src/libcore/str/pattern.rs

   1 //! The string Pattern API.
   2 //!
   3 //! For more details, see the traits [`Pattern`], [`Searcher`],
   4 //! [`ReverseSearcher`], and [`DoubleEndedSearcher`].
   5
   6 #![unstable(
   7     feature = "pattern",
   8     reason = "API not fully fleshed out and ready to be stabilized",
   9     issue = "27721"
  10 )]
  11
  12 use crate::cmp;
  13 use crate::fmt;
  14 use crate::slice::memchr;
  15 use crate::usize;
  16
  17 // Pattern
  18
  19 /// A string pattern.
  20 ///
  21 /// A `Pattern<'a>` expresses that the implementing type
  22 /// can be used as a string pattern for searching in a `&'a str`.
  23 ///
  24 /// For example, both `'a'` and `"aa"` are patterns that
  25 /// would match at index `1` in the string `"baaaab"`.
  26 ///
  27 /// The trait itself acts as a builder for an associated
  28 /// `Searcher` type, which does the actual work of finding
  29 /// occurrences of the pattern in a string.
  30 pub trait Pattern<'a>: Sized {
  31     /// Associated searcher for this pattern
  32     type Searcher: Searcher<'a>;
  33
  34     /// Constructs the associated searcher from
  35     /// `self` and the `haystack` to search in.
  36     fn into_searcher(self, haystack: &'a str) -> Self::Searcher;
  37
  38     /// Checks whether the pattern matches anywhere in the haystack
  39     #[inline]
  40     fn is_contained_in(self, haystack: &'a str) -> bool {
  41         self.into_searcher(haystack).next_match().is_some()
  42     }
  43
  44     /// Checks whether the pattern matches at the front of the haystack
  45     #[inline]
  46     fn is_prefix_of(self, haystack: &'a str) -> bool {
  47         matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
  48     }
  49
  50     /// Checks whether the pattern matches at the back of the haystack
  51     #[inline]
  52     fn is_suffix_of(self, haystack: &'a str) -> bool
  53     where
  54         Self::Searcher: ReverseSearcher<'a>,
  55     {
  56         matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
  57     }
  58 }
  59
  60 // Searcher
  61
  62 /// Result of calling `Searcher::next()` or `ReverseSearcher::next_back()`.
  63 #[derive(Copy, Clone, Eq, PartialEq, Debug)]
  64 pub enum SearchStep {
  65     /// Expresses that a match of the pattern has been found at
  66     /// `haystack[a..b]`.
  67     Match(usize, usize),
  68     /// Expresses that `haystack[a..b]` has been rejected as a possible match
  69     /// of the pattern.
  70     ///
  71     /// Note that there might be more than one `Reject` between two `Match`es,
  72     /// there is no requirement for them to be combined into one.
  73     Reject(usize, usize),
  74     /// Expresses that every byte of the haystack has been visited, ending
  75     /// the iteration.
  76     Done,
  77 }
  78
  79 /// A searcher for a string pattern.
  80 ///
  81 /// This trait provides methods for searching for non-overlapping
  82 /// matches of a pattern starting from the front (left) of a string.
  83 ///
  84 /// It will be implemented by associated `Searcher`
  85 /// types of the `Pattern` trait.
  86 ///
  87 /// The trait is marked unsafe because the indices returned by the
  88 /// `next()` methods are required to lie on valid utf8 boundaries in
  89 /// the haystack. This enables consumers of this trait to
  90 /// slice the haystack without additional runtime checks.
  91 pub unsafe trait Searcher<'a> {
  92     /// Getter for the underlying string to be searched in
  93     ///
  94     /// Will always return the same `&str`
  95     fn haystack(&self) -> &'a str;
  96
  97     /// Performs the next search step starting from the front.
  98     ///
  99     /// - Returns `Match(a, b)` if `haystack[a..b]` matches the pattern.
 100     /// - Returns `Reject(a, b)` if `haystack[a..b]` can not match the
 101     ///   pattern, even partially.
 102     /// - Returns `Done` if every byte of the haystack has been visited
 103     ///
 104     /// The stream of `Match` and `Reject` values up to a `Done`
 105     /// will contain index ranges that are adjacent, non-overlapping,
 106     /// covering the whole haystack, and laying on utf8 boundaries.
 107     ///
 108     /// A `Match` result needs to contain the whole matched pattern,
 109     /// however `Reject` results may be split up into arbitrary
 110     /// many adjacent fragments. Both ranges may have zero length.
 111     ///
 112     /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
 113     /// might produce the stream
 114     /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
 115     fn next(&mut self) -> SearchStep;
 116
 117     /// Finds the next `Match` result. See `next()`
 118     ///
 119     /// Unlike next(), there is no guarantee that the returned ranges
 120     /// of this and next_reject will overlap. This will return (start_match, end_match),
 121     /// where start_match is the index of where the match begins, and end_match is
 122     /// the index after the end of the match.
 123     #[inline]
 124     fn next_match(&mut self) -> Option<(usize, usize)> {
 125         loop {
 126             match self.next() {
 127                 SearchStep::Match(a, b) => return Some((a, b)),
 128                 SearchStep::Done => return None,
 129                 _ => continue,
 130             }
 131         }
 132     }
 133
 134     /// Finds the next `Reject` result. See `next()` and `next_match()`
 135     ///
 136     /// Unlike next(), there is no guarantee that the returned ranges
 137     /// of this and next_match will overlap.
 138     #[inline]
 139     fn next_reject(&mut self) -> Option<(usize, usize)> {
 140         loop {
 141             match self.next() {
 142                 SearchStep::Reject(a, b) => return Some((a, b)),
 143                 SearchStep::Done => return None,
 144                 _ => continue,
 145             }
 146         }
 147     }
 148 }
 149
 150 /// A reverse searcher for a string pattern.
 151 ///
 152 /// This trait provides methods for searching for non-overlapping
 153 /// matches of a pattern starting from the back (right) of a string.
 154 ///
 155 /// It will be implemented by associated `Searcher`
 156 /// types of the `Pattern` trait if the pattern supports searching
 157 /// for it from the back.
 158 ///
 159 /// The index ranges returned by this trait are not required
 160 /// to exactly match those of the forward search in reverse.
 161 ///
 162 /// For the reason why this trait is marked unsafe, see them
 163 /// parent trait `Searcher`.
 164 pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
 165     /// Performs the next search step starting from the back.
 166     ///
 167     /// - Returns `Match(a, b)` if `haystack[a..b]` matches the pattern.
 168     /// - Returns `Reject(a, b)` if `haystack[a..b]` can not match the
 169     ///   pattern, even partially.
 170     /// - Returns `Done` if every byte of the haystack has been visited
 171     ///
 172     /// The stream of `Match` and `Reject` values up to a `Done`
 173     /// will contain index ranges that are adjacent, non-overlapping,
 174     /// covering the whole haystack, and laying on utf8 boundaries.
 175     ///
 176     /// A `Match` result needs to contain the whole matched pattern,
 177     /// however `Reject` results may be split up into arbitrary
 178     /// many adjacent fragments. Both ranges may have zero length.
 179     ///
 180     /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
 181     /// might produce the stream
 182     /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`
 183     fn next_back(&mut self) -> SearchStep;
 184
 185     /// Finds the next `Match` result. See `next_back()`
 186     #[inline]
 187     fn next_match_back(&mut self) -> Option<(usize, usize)> {
 188         loop {
 189             match self.next_back() {
 190                 SearchStep::Match(a, b) => return Some((a, b)),
 191                 SearchStep::Done => return None,
 192                 _ => continue,
 193             }
 194         }
 195     }
 196
 197     /// Finds the next `Reject` result. See `next_back()`
 198     #[inline]
 199     fn next_reject_back(&mut self) -> Option<(usize, usize)> {
 200         loop {
 201             match self.next_back() {
 202                 SearchStep::Reject(a, b) => return Some((a, b)),
 203                 SearchStep::Done => return None,
 204                 _ => continue,
 205             }
 206         }
 207     }
 208 }
 209
 210 /// A marker trait to express that a `ReverseSearcher`
 211 /// can be used for a `DoubleEndedIterator` implementation.
 212 ///
 213 /// For this, the impl of `Searcher` and `ReverseSearcher` need
 214 /// to follow these conditions:
 215 ///
 216 /// - All results of `next()` need to be identical
 217 ///   to the results of `next_back()` in reverse order.
 218 /// - `next()` and `next_back()` need to behave as
 219 ///   the two ends of a range of values, that is they
 220 ///   can not "walk past each other".
 221 ///
 222 /// # Examples
 223 ///
 224 /// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
 225 /// `char` only requires looking at one at a time, which behaves the same
 226 /// from both ends.
 227 ///
 228 /// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
 229 /// the pattern `"aa"` in the haystack `"aaa"` matches as either
 230 /// `"[aa]a"` or `"a[aa]"`, depending from which side it is searched.
 231 pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
 232
 233 /////////////////////////////////////////////////////////////////////////////
 234 // Impl for char
 235 /////////////////////////////////////////////////////////////////////////////
 236
 237 /// Associated type for `<char as Pattern<'a>>::Searcher`.
 238 #[derive(Clone, Debug)]
 239 pub struct CharSearcher<'a> {
 240     haystack: &'a str,
 241     // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack`
 242     // This invariant can be broken *within* next_match and next_match_back, however
 243     // they must exit with fingers on valid code point boundaries.
 244     /// `finger` is the current byte index of the forward search.
 245     /// Imagine that it exists before the byte at its index, i.e.
 246     /// `haystack[finger]` is the first byte of the slice we must inspect during
 247     /// forward searching
 248     finger: usize,
 249     /// `finger_back` is the current byte index of the reverse search.
 250     /// Imagine that it exists after the byte at its index, i.e.
 251     /// haystack[finger_back - 1] is the last byte of the slice we must inspect during
 252     /// forward searching (and thus the first byte to be inspected when calling next_back())
 253     finger_back: usize,
 254     /// The character being searched for
 255     needle: char,
 256
 257     // safety invariant: `utf8_size` must be less than 5
 258     /// The number of bytes `needle` takes up when encoded in utf8
 259     utf8_size: usize,
 260     /// A utf8 encoded copy of the `needle`
 261     utf8_encoded: [u8; 4],
 262 }
 263
 264 unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
 265     #[inline]
 266     fn haystack(&self) -> &'a str {
 267         self.haystack
 268     }
 269     #[inline]
 270     fn next(&mut self) -> SearchStep {
 271         let old_finger = self.finger;
 272         // SAFETY: 1-4 guarantee safety of `get_unchecked`
 273         // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries
 274         //    (this is invariant)
 275         // 2. `self.finger >= 0` since it starts at 0 and only increases
 276         // 3. `self.finger < self.finger_back` because otherwise the char `iter`
 277         //    would return `SearchStep::Done`
 278         // 4. `self.finger` comes before the end of the haystack because `self.finger_back`
 279         //    starts at the end and only decreases
 280         let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
 281         let mut iter = slice.chars();
 282         let old_len = iter.iter.len();
 283         if let Some(ch) = iter.next() {
 284             // add byte offset of current character
 285             // without re-encoding as utf-8
 286             self.finger += old_len - iter.iter.len();
 287             if ch == self.needle {
 288                 SearchStep::Match(old_finger, self.finger)
 289             } else {
 290                 SearchStep::Reject(old_finger, self.finger)
 291             }
 292         } else {
 293             SearchStep::Done
 294         }
 295     }
 296     #[inline]
 297     fn next_match(&mut self) -> Option<(usize, usize)> {
 298         loop {
 299             // get the haystack after the last character found
 300             let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
 301             // the last byte of the utf8 encoded needle
 302             // SAFETY: we have an invariant that `utf8_size < 5`
 303             let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
 304             if let Some(index) = memchr::memchr(last_byte, bytes) {
 305                 // The new finger is the index of the byte we found,
 306                 // plus one, since we memchr'd for the last byte of the character.
 307                 //
 308                 // Note that this doesn't always give us a finger on a UTF8 boundary.
 309                 // If we *didn't* find our character
 310                 // we may have indexed to the non-last byte of a 3-byte or 4-byte character.
 311                 // We can't just skip to the next valid starting byte because a character like
 312                 // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find
 313                 // the second byte when searching for the third.
 314                 //
 315                 // However, this is totally okay. While we have the invariant that
 316                 // self.finger is on a UTF8 boundary, this invariant is not relied upon
 317                 // within this method (it is relied upon in CharSearcher::next()).
 318                 //
 319                 // We only exit this method when we reach the end of the string, or if we
 320                 // find something. When we find something the `finger` will be set
 321                 // to a UTF8 boundary.
 322                 self.finger += index + 1;
 323                 if self.finger >= self.utf8_size {
 324                     let found_char = self.finger - self.utf8_size;
 325                     if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
 326                         if slice == &self.utf8_encoded[0..self.utf8_size] {
 327                             return Some((found_char, self.finger));
 328                         }
 329                     }
 330                 }
 331             } else {
 332                 // found nothing, exit
 333                 self.finger = self.finger_back;
 334                 return None;
 335             }
 336         }
 337     }
 338
 339     // let next_reject use the default implementation from the Searcher trait
 340 }
 341
 342 unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
 343     #[inline]
 344     fn next_back(&mut self) -> SearchStep {
 345         let old_finger = self.finger_back;
 346         // SAFETY: see the comment for next() above
 347         let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
 348         let mut iter = slice.chars();
 349         let old_len = iter.iter.len();
 350         if let Some(ch) = iter.next_back() {
 351             // subtract byte offset of current character
 352             // without re-encoding as utf-8
 353             self.finger_back -= old_len - iter.iter.len();
 354             if ch == self.needle {
 355                 SearchStep::Match(self.finger_back, old_finger)
 356             } else {
 357                 SearchStep::Reject(self.finger_back, old_finger)
 358             }
 359         } else {
 360             SearchStep::Done
 361         }
 362     }
 363     #[inline]
 364     fn next_match_back(&mut self) -> Option<(usize, usize)> {
 365         let haystack = self.haystack.as_bytes();
 366         loop {
 367             // get the haystack up to but not including the last character searched
 368             let bytes = if let Some(slice) = haystack.get(self.finger..self.finger_back) {
 369                 slice
 370             } else {
 371                 return None;
 372             };
 373             // the last byte of the utf8 encoded needle
 374             // SAFETY: we have an invariant that `utf8_size < 5`
 375             let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
 376             if let Some(index) = memchr::memrchr(last_byte, bytes) {
 377                 // we searched a slice that was offset by self.finger,
 378                 // add self.finger to recoup the original index
 379                 let index = self.finger + index;
 380                 // memrchr will return the index of the byte we wish to
 381                 // find. In case of an ASCII character, this is indeed
 382                 // were we wish our new finger to be ("after" the found
 383                 // char in the paradigm of reverse iteration). For
 384                 // multibyte chars we need to skip down by the number of more
 385                 // bytes they have than ASCII
 386                 let shift = self.utf8_size - 1;
 387                 if index >= shift {
 388                     let found_char = index - shift;
 389                     if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size)) {
 390                         if slice == &self.utf8_encoded[0..self.utf8_size] {
 391                             // move finger to before the character found (i.e., at its start index)
 392                             self.finger_back = found_char;
 393                             return Some((self.finger_back, self.finger_back + self.utf8_size));
 394                         }
 395                     }
 396                 }
 397                 // We can't use finger_back = index - size + 1 here. If we found the last char
 398                 // of a different-sized character (or the middle byte of a different character)
 399                 // we need to bump the finger_back down to `index`. This similarly makes
 400                 // `finger_back` have the potential to no longer be on a boundary,
 401                 // but this is OK since we only exit this function on a boundary
 402                 // or when the haystack has been searched completely.
 403                 //
 404                 // Unlike next_match this does not
 405                 // have the problem of repeated bytes in utf-8 because
 406                 // we're searching for the last byte, and we can only have
 407                 // found the last byte when searching in reverse.
 408                 self.finger_back = index;
 409             } else {
 410                 self.finger_back = self.finger;
 411                 // found nothing, exit
 412                 return None;
 413             }
 414         }
 415     }
 416
 417     // let next_reject_back use the default implementation from the Searcher trait
 418 }
 419
 420 impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
 421
 422 /// Searches for chars that are equal to a given char
 423 impl<'a> Pattern<'a> for char {
 424     type Searcher = CharSearcher<'a>;
 425
 426     #[inline]
 427     fn into_searcher(self, haystack: &'a str) -> Self::Searcher {
 428         let mut utf8_encoded = [0; 4];
 429         let utf8_size = self.encode_utf8(&mut utf8_encoded).len();
 430         CharSearcher {
 431             haystack,
 432             finger: 0,
 433             finger_back: haystack.len(),
 434             needle: self,
 435             utf8_size,
 436             utf8_encoded,
 437         }
 438     }
 439
 440     #[inline]
 441     fn is_contained_in(self, haystack: &'a str) -> bool {
 442         if (self as u32) < 128 {
 443             haystack.as_bytes().contains(&(self as u8))
 444         } else {
 445             let mut buffer = [0u8; 4];
 446             self.encode_utf8(&mut buffer).is_contained_in(haystack)
 447         }
 448     }
 449
 450     #[inline]
 451     fn is_prefix_of(self, haystack: &'a str) -> bool {
 452         self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
 453     }
 454
 455     #[inline]
 456     fn is_suffix_of(self, haystack: &'a str) -> bool
 457     where
 458         Self::Searcher: ReverseSearcher<'a>,
 459     {
 460         self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
 461     }
 462 }
 463
 464 /////////////////////////////////////////////////////////////////////////////
 465 // Impl for a MultiCharEq wrapper
 466 /////////////////////////////////////////////////////////////////////////////
 467
 468 #[doc(hidden)]
 469 trait MultiCharEq {
 470     fn matches(&mut self, c: char) -> bool;
 471 }
 472
 473 impl<F> MultiCharEq for F
 474 where
 475     F: FnMut(char) -> bool,
 476 {
 477     #[inline]
 478     fn matches(&mut self, c: char) -> bool {
 479         (*self)(c)
 480     }
 481 }
 482
 483 impl MultiCharEq for &[char] {
 484     #[inline]
 485     fn matches(&mut self, c: char) -> bool {
 486         self.iter().any(|&m| m == c)
 487     }
 488 }
 489
 490 struct MultiCharEqPattern<C: MultiCharEq>(C);
 491
 492 #[derive(Clone, Debug)]
 493 struct MultiCharEqSearcher<'a, C: MultiCharEq> {
 494     char_eq: C,
 495     haystack: &'a str,
 496     char_indices: super::CharIndices<'a>,
 497 }
 498
 499 impl<'a, C: MultiCharEq> Pattern<'a> for MultiCharEqPattern<C> {
 500     type Searcher = MultiCharEqSearcher<'a, C>;
 501
 502     #[inline]
 503     fn into_searcher(self, haystack: &'a str) -> MultiCharEqSearcher<'a, C> {
 504         MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
 505     }
 506 }
 507
 508 unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
 509     #[inline]
 510     fn haystack(&self) -> &'a str {
 511         self.haystack
 512     }
 513
 514     #[inline]
 515     fn next(&mut self) -> SearchStep {
 516         let s = &mut self.char_indices;
 517         // Compare lengths of the internal byte slice iterator
 518         // to find length of current char
 519         let pre_len = s.iter.iter.len();
 520         if let Some((i, c)) = s.next() {
 521             let len = s.iter.iter.len();
 522             let char_len = pre_len - len;
 523             if self.char_eq.matches(c) {
 524                 return SearchStep::Match(i, i + char_len);
 525             } else {
 526                 return SearchStep::Reject(i, i + char_len);
 527             }
 528         }
 529         SearchStep::Done
 530     }
 531 }
 532
 533 unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
 534     #[inline]
 535     fn next_back(&mut self) -> SearchStep {
 536         let s = &mut self.char_indices;
 537         // Compare lengths of the internal byte slice iterator
 538         // to find length of current char
 539         let pre_len = s.iter.iter.len();
 540         if let Some((i, c)) = s.next_back() {
 541             let len = s.iter.iter.len();
 542             let char_len = pre_len - len;
 543             if self.char_eq.matches(c) {
 544                 return SearchStep::Match(i, i + char_len);
 545             } else {
 546                 return SearchStep::Reject(i, i + char_len);
 547             }
 548         }
 549         SearchStep::Done
 550     }
 551 }
 552
 553 impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}
 554
 555 /////////////////////////////////////////////////////////////////////////////
 556
 557 macro_rules! pattern_methods {
 558     ($t:ty, $pmap:expr, $smap:expr) => {
 559         type Searcher = $t;
 560
 561         #[inline]
 562         fn into_searcher(self, haystack: &'a str) -> $t {
 563             ($smap)(($pmap)(self).into_searcher(haystack))
 564         }
 565
 566         #[inline]
 567         fn is_contained_in(self, haystack: &'a str) -> bool {
 568             ($pmap)(self).is_contained_in(haystack)
 569         }
 570
 571         #[inline]
 572         fn is_prefix_of(self, haystack: &'a str) -> bool {
 573             ($pmap)(self).is_prefix_of(haystack)
 574         }
 575
 576         #[inline]
 577         fn is_suffix_of(self, haystack: &'a str) -> bool
 578             where $t: ReverseSearcher<'a>
 579         {
 580             ($pmap)(self).is_suffix_of(haystack)
 581         }
 582     }
 583 }
 584
 585 macro_rules! searcher_methods {
 586     (forward) => {
 587         #[inline]
 588         fn haystack(&self) -> &'a str {
 589             self.0.haystack()
 590         }
 591         #[inline]
 592         fn next(&mut self) -> SearchStep {
 593             self.0.next()
 594         }
 595         #[inline]
 596         fn next_match(&mut self) -> Option<(usize, usize)> {
 597             self.0.next_match()
 598         }
 599         #[inline]
 600         fn next_reject(&mut self) -> Option<(usize, usize)> {
 601             self.0.next_reject()
 602         }
 603     };
 604     (reverse) => {
 605         #[inline]
 606         fn next_back(&mut self) -> SearchStep {
 607             self.0.next_back()
 608         }
 609         #[inline]
 610         fn next_match_back(&mut self) -> Option<(usize, usize)> {
 611             self.0.next_match_back()
 612         }
 613         #[inline]
 614         fn next_reject_back(&mut self) -> Option<(usize, usize)> {
 615             self.0.next_reject_back()
 616         }
 617     }
 618 }
 619
 620 /////////////////////////////////////////////////////////////////////////////
 621 // Impl for &[char]
 622 /////////////////////////////////////////////////////////////////////////////
 623
 624 // Todo: Change / Remove due to ambiguity in meaning.
 625
 626 /// Associated type for `<&[char] as Pattern<'a>>::Searcher`.
 627 #[derive(Clone, Debug)]
 628 pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern<'a>>::Searcher);
 629
 630 unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
 631     searcher_methods!(forward);
 632 }
 633
 634 unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
 635     searcher_methods!(reverse);
 636 }
 637
 638 impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
 639
 640 /// Searches for chars that are equal to any of the chars in the array
 641 impl<'a, 'b> Pattern<'a> for &'b [char] {
 642     pattern_methods!(CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
 643 }
 644
 645 /////////////////////////////////////////////////////////////////////////////
 646 // Impl for F: FnMut(char) -> bool
 647 /////////////////////////////////////////////////////////////////////////////
 648
 649 /// Associated type for `<F as Pattern<'a>>::Searcher`.
 650 #[derive(Clone)]
 651 pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern<'a>>::Searcher)
 652 where
 653     F: FnMut(char) -> bool;
 654
 655 impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
 656 where
 657     F: FnMut(char) -> bool,
 658 {
 659     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 660         f.debug_struct("CharPredicateSearcher")
 661             .field("haystack", &self.0.haystack)
 662             .field("char_indices", &self.0.char_indices)
 663             .finish()
 664     }
 665 }
 666 unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
 667 where
 668     F: FnMut(char) -> bool,
 669 {
 670     searcher_methods!(forward);
 671 }
 672
 673 unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
 674 where
 675     F: FnMut(char) -> bool,
 676 {
 677     searcher_methods!(reverse);
 678 }
 679
 680 impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}
 681
 682 /// Searches for chars that match the given predicate
 683 impl<'a, F> Pattern<'a> for F
 684 where
 685     F: FnMut(char) -> bool,
 686 {
 687     pattern_methods!(CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
 688 }
 689
 690 /////////////////////////////////////////////////////////////////////////////
 691 // Impl for &&str
 692 /////////////////////////////////////////////////////////////////////////////
 693
 694 /// Delegates to the `&str` impl.
 695 impl<'a, 'b, 'c> Pattern<'a> for &'c &'b str {
 696     pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s);
 697 }
 698
 699 /////////////////////////////////////////////////////////////////////////////
 700 // Impl for &str
 701 /////////////////////////////////////////////////////////////////////////////
 702
 703 /// Non-allocating substring search.
 704 ///
 705 /// Will handle the pattern `""` as returning empty matches at each character
 706 /// boundary.
 707 impl<'a, 'b> Pattern<'a> for &'b str {
 708     type Searcher = StrSearcher<'a, 'b>;
 709
 710     #[inline]
 711     fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> {
 712         StrSearcher::new(haystack, self)
 713     }
 714
 715     /// Checks whether the pattern matches at the front of the haystack
 716     #[inline]
 717     fn is_prefix_of(self, haystack: &'a str) -> bool {
 718         haystack.as_bytes().starts_with(self.as_bytes())
 719     }
 720
 721     /// Checks whether the pattern matches at the back of the haystack
 722     #[inline]
 723     fn is_suffix_of(self, haystack: &'a str) -> bool {
 724         haystack.as_bytes().ends_with(self.as_bytes())
 725     }
 726 }
 727
 728 /////////////////////////////////////////////////////////////////////////////
 729 // Two Way substring searcher
 730 /////////////////////////////////////////////////////////////////////////////
 731
 732 #[derive(Clone, Debug)]
 733 /// Associated type for `<&str as Pattern<'a>>::Searcher`.
 734 pub struct StrSearcher<'a, 'b> {
 735     haystack: &'a str,
 736     needle: &'b str,
 737
 738     searcher: StrSearcherImpl,
 739 }
 740
 741 #[derive(Clone, Debug)]
 742 enum StrSearcherImpl {
 743     Empty(EmptyNeedle),
 744     TwoWay(TwoWaySearcher),
 745 }
 746
 747 #[derive(Clone, Debug)]
 748 struct EmptyNeedle {
 749     position: usize,
 750     end: usize,
 751     is_match_fw: bool,
 752     is_match_bw: bool,
 753 }
 754
 755 impl<'a, 'b> StrSearcher<'a, 'b> {
 756     fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
 757         if needle.is_empty() {
 758             StrSearcher {
 759                 haystack,
 760                 needle,
 761                 searcher: StrSearcherImpl::Empty(EmptyNeedle {
 762                     position: 0,
 763                     end: haystack.len(),
 764                     is_match_fw: true,
 765                     is_match_bw: true,
 766                 }),
 767             }
 768         } else {
 769             StrSearcher {
 770                 haystack,
 771                 needle,
 772                 searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
 773                     needle.as_bytes(),
 774                     haystack.len(),
 775                 )),
 776             }
 777         }
 778     }
 779 }
 780
 781 unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
 782     #[inline]
 783     fn haystack(&self) -> &'a str {
 784         self.haystack
 785     }
 786
 787     #[inline]
 788     fn next(&mut self) -> SearchStep {
 789         match self.searcher {
 790             StrSearcherImpl::Empty(ref mut searcher) => {
 791                 // empty needle rejects every char and matches every empty string between them
 792                 let is_match = searcher.is_match_fw;
 793                 searcher.is_match_fw = !searcher.is_match_fw;
 794                 let pos = searcher.position;
 795                 match self.haystack[pos..].chars().next() {
 796                     _ if is_match => SearchStep::Match(pos, pos),
 797                     None => SearchStep::Done,
 798                     Some(ch) => {
 799                         searcher.position += ch.len_utf8();
 800                         SearchStep::Reject(pos, searcher.position)
 801                     }
 802                 }
 803             }
 804             StrSearcherImpl::TwoWay(ref mut searcher) => {
 805                 // TwoWaySearcher produces valid *Match* indices that split at char boundaries
 806                 // as long as it does correct matching and that haystack and needle are
 807                 // valid UTF-8
 808                 // *Rejects* from the algorithm can fall on any indices, but we will walk them
 809                 // manually to the next character boundary, so that they are utf-8 safe.
 810                 if searcher.position == self.haystack.len() {
 811                     return SearchStep::Done;
 812                 }
 813                 let is_long = searcher.memory == usize::MAX;
 814                 match searcher.next::<RejectAndMatch>(
 815                     self.haystack.as_bytes(),
 816                     self.needle.as_bytes(),
 817                     is_long,
 818                 ) {
 819                     SearchStep::Reject(a, mut b) => {
 820                         // skip to next char boundary
 821                         while !self.haystack.is_char_boundary(b) {
 822                             b += 1;
 823                         }
 824                         searcher.position = cmp::max(b, searcher.position);
 825                         SearchStep::Reject(a, b)
 826                     }
 827                     otherwise => otherwise,
 828                 }
 829             }
 830         }
 831     }
 832
 833     #[inline]
 834     fn next_match(&mut self) -> Option<(usize, usize)> {
 835         match self.searcher {
 836             StrSearcherImpl::Empty(..) => loop {
 837                 match self.next() {
 838                     SearchStep::Match(a, b) => return Some((a, b)),
 839                     SearchStep::Done => return None,
 840                     SearchStep::Reject(..) => {}
 841                 }
 842             },
 843             StrSearcherImpl::TwoWay(ref mut searcher) => {
 844                 let is_long = searcher.memory == usize::MAX;
 845                 // write out `true` and `false` cases to encourage the compiler
 846                 // to specialize the two cases separately.
 847                 if is_long {
 848                     searcher.next::<MatchOnly>(
 849                         self.haystack.as_bytes(),
 850                         self.needle.as_bytes(),
 851                         true,
 852                     )
 853                 } else {
 854                     searcher.next::<MatchOnly>(
 855                         self.haystack.as_bytes(),
 856                         self.needle.as_bytes(),
 857                         false,
 858                     )
 859                 }
 860             }
 861         }
 862     }
 863 }
 864
 865 unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
 866     #[inline]
 867     fn next_back(&mut self) -> SearchStep {
 868         match self.searcher {
 869             StrSearcherImpl::Empty(ref mut searcher) => {
 870                 let is_match = searcher.is_match_bw;
 871                 searcher.is_match_bw = !searcher.is_match_bw;
 872                 let end = searcher.end;
 873                 match self.haystack[..end].chars().next_back() {
 874                     _ if is_match => SearchStep::Match(end, end),
 875                     None => SearchStep::Done,
 876                     Some(ch) => {
 877                         searcher.end -= ch.len_utf8();
 878                         SearchStep::Reject(searcher.end, end)
 879                     }
 880                 }
 881             }
 882             StrSearcherImpl::TwoWay(ref mut searcher) => {
 883                 if searcher.end == 0 {
 884                     return SearchStep::Done;
 885                 }
 886                 let is_long = searcher.memory == usize::MAX;
 887                 match searcher.next_back::<RejectAndMatch>(
 888                     self.haystack.as_bytes(),
 889                     self.needle.as_bytes(),
 890                     is_long,
 891                 ) {
 892                     SearchStep::Reject(mut a, b) => {
 893                         // skip to next char boundary
 894                         while !self.haystack.is_char_boundary(a) {
 895                             a -= 1;
 896                         }
 897                         searcher.end = cmp::min(a, searcher.end);
 898                         SearchStep::Reject(a, b)
 899                     }
 900                     otherwise => otherwise,
 901                 }
 902             }
 903         }
 904     }
 905
 906     #[inline]
 907     fn next_match_back(&mut self) -> Option<(usize, usize)> {
 908         match self.searcher {
 909             StrSearcherImpl::Empty(..) => loop {
 910                 match self.next_back() {
 911                     SearchStep::Match(a, b) => return Some((a, b)),
 912                     SearchStep::Done => return None,
 913                     SearchStep::Reject(..) => {}
 914                 }
 915             },
 916             StrSearcherImpl::TwoWay(ref mut searcher) => {
 917                 let is_long = searcher.memory == usize::MAX;
 918                 // write out `true` and `false`, like `next_match`
 919                 if is_long {
 920                     searcher.next_back::<MatchOnly>(
 921                         self.haystack.as_bytes(),
 922                         self.needle.as_bytes(),
 923                         true,
 924                     )
 925                 } else {
 926                     searcher.next_back::<MatchOnly>(
 927                         self.haystack.as_bytes(),
 928                         self.needle.as_bytes(),
 929                         false,
 930                     )
 931                 }
 932             }
 933         }
 934     }
 935 }
 936
 937 /// The internal state of the two-way substring search algorithm.
 938 #[derive(Clone, Debug)]
 939 struct TwoWaySearcher {
 940     // constants
 941     /// critical factorization index
 942     crit_pos: usize,
 943     /// critical factorization index for reversed needle
 944     crit_pos_back: usize,
 945     period: usize,
 946     /// `byteset` is an extension (not part of the two way algorithm);
 947     /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
 948     /// to a (byte & 63) == j present in the needle.
 949     byteset: u64,
 950
 951     // variables
 952     position: usize,
 953     end: usize,
 954     /// index into needle before which we have already matched
 955     memory: usize,
 956     /// index into needle after which we have already matched
 957     memory_back: usize,
 958 }
 959
 960 /*
 961     This is the Two-Way search algorithm, which was introduced in the paper:
 962     Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
 963
 964     Here's some background information.
 965
 966     A *word* is a string of symbols. The *length* of a word should be a familiar
 967     notion, and here we denote it for any word x by |x|.
 968     (We also allow for the possibility of the *empty word*, a word of length zero).
 969
 970     If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
 971     *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
 972     For example, both 1 and 2 are periods for the string "aa". As another example,
 973     the only period of the string "abcd" is 4.
 974
 975     We denote by period(x) the *smallest* period of x (provided that x is non-empty).
 976     This is always well-defined since every non-empty word x has at least one period,
 977     |x|. We sometimes call this *the period* of x.
 978
 979     If u, v and x are words such that x = uv, where uv is the concatenation of u and
 980     v, then we say that (u, v) is a *factorization* of x.
 981
 982     Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
 983     that both of the following hold
 984
 985       - either w is a suffix of u or u is a suffix of w
 986       - either w is a prefix of v or v is a prefix of w
 987
 988     then w is said to be a *repetition* for the factorization (u, v).
 989
 990     Just to unpack this, there are four possibilities here. Let w = "abc". Then we
 991     might have:
 992
 993       - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
 994       - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
 995       - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
 996       - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
 997
 998     Note that the word vu is a repetition for any factorization (u,v) of x = uv,
 999     so every factorization has at least one repetition.
1000
1001     If x is a string and (u, v) is a factorization for x, then a *local period* for
1002     (u, v) is an integer r such that there is some word w such that |w| = r and w is
1003     a repetition for (u, v).
1004
1005     We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
1006     call this *the local period* of (u, v). Provided that x = uv is non-empty, this
1007     is well-defined (because each non-empty word has at least one factorization, as
1008     noted above).
1009
1010     It can be proven that the following is an equivalent definition of a local period
1011     for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
1012     all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
1013     defined. (i.e., i > 0 and i + r < |x|).
1014
1015     Using the above reformulation, it is easy to prove that
1016
1017         1 <= local_period(u, v) <= period(uv)
1018
1019     A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
1020     *critical factorization*.
1021
1022     The algorithm hinges on the following theorem, which is stated without proof:
1023
1024     **Critical Factorization Theorem** Any word x has at least one critical
1025     factorization (u, v) such that |u| < period(x).
1026
1027     The purpose of maximal_suffix is to find such a critical factorization.
1028
1029     If the period is short, compute another factorization x = u' v' to use
1030     for reverse search, chosen instead so that |v'| < period(x).
1031
1032 */
1033 impl TwoWaySearcher {
1034     fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
1035         let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
1036         let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);
1037
1038         let (crit_pos, period) = if crit_pos_false > crit_pos_true {
1039             (crit_pos_false, period_false)
1040         } else {
1041             (crit_pos_true, period_true)
1042         };
1043
1044         // A particularly readable explanation of what's going on here can be found
1045         // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
1046         // see the code for "Algorithm CP" on p. 323.
1047         //
1048         // What's going on is we have some critical factorization (u, v) of the
1049         // needle, and we want to determine whether u is a suffix of
1050         // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
1051         // "Algorithm CP2", which is optimized for when the period of the needle
1052         // is large.
1053         if needle[..crit_pos] == needle[period..period + crit_pos] {
1054             // short period case -- the period is exact
1055             // compute a separate critical factorization for the reversed needle
1056             // x = u' v' where |v'| < period(x).
1057             //
1058             // This is sped up by the period being known already.
1059             // Note that a case like x = "acba" may be factored exactly forwards
1060             // (crit_pos = 1, period = 3) while being factored with approximate
1061             // period in reverse (crit_pos = 2, period = 2). We use the given
1062             // reverse factorization but keep the exact period.
1063             let crit_pos_back = needle.len()
1064                 - cmp::max(
1065                     TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
1066                     TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
1067                 );
1068
1069             TwoWaySearcher {
1070                 crit_pos,
1071                 crit_pos_back,
1072                 period,
1073                 byteset: Self::byteset_create(&needle[..period]),
1074
1075                 position: 0,
1076                 end,
1077                 memory: 0,
1078                 memory_back: needle.len(),
1079             }
1080         } else {
1081             // long period case -- we have an approximation to the actual period,
1082             // and don't use memorization.
1083             //
1084             // Approximate the period by lower bound max(|u|, |v|) + 1.
1085             // The critical factorization is efficient to use for both forward and
1086             // reverse search.
1087
1088             TwoWaySearcher {
1089                 crit_pos,
1090                 crit_pos_back: crit_pos,
1091                 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
1092                 byteset: Self::byteset_create(needle),
1093
1094                 position: 0,
1095                 end,
1096                 memory: usize::MAX, // Dummy value to signify that the period is long
1097                 memory_back: usize::MAX,
1098             }
1099         }
1100     }
1101
1102     #[inline]
1103     fn byteset_create(bytes: &[u8]) -> u64 {
1104         bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
1105     }
1106
1107     #[inline]
1108     fn byteset_contains(&self, byte: u8) -> bool {
1109         (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
1110     }
1111
1112     // One of the main ideas of Two-Way is that we factorize the needle into
1113     // two halves, (u, v), and begin trying to find v in the haystack by scanning
1114     // left to right. If v matches, we try to match u by scanning right to left.
1115     // How far we can jump when we encounter a mismatch is all based on the fact
1116     // that (u, v) is a critical factorization for the needle.
1117     #[inline]
1118     fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1119     where
1120         S: TwoWayStrategy,
1121     {
1122         // `next()` uses `self.position` as its cursor
1123         let old_pos = self.position;
1124         let needle_last = needle.len() - 1;
1125         'search: loop {
1126             // Check that we have room to search in
1127             // position + needle_last can not overflow if we assume slices
1128             // are bounded by isize's range.
1129             let tail_byte = match haystack.get(self.position + needle_last) {
1130                 Some(&b) => b,
1131                 None => {
1132                     self.position = haystack.len();
1133                     return S::rejecting(old_pos, self.position);
1134                 }
1135             };
1136
1137             if S::use_early_reject() && old_pos != self.position {
1138                 return S::rejecting(old_pos, self.position);
1139             }
1140
1141             // Quickly skip by large portions unrelated to our substring
1142             if !self.byteset_contains(tail_byte) {
1143                 self.position += needle.len();
1144                 if !long_period {
1145                     self.memory = 0;
1146                 }
1147                 continue 'search;
1148             }
1149
1150             // See if the right part of the needle matches
1151             let start =
1152                 if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) };
1153             for i in start..needle.len() {
1154                 if needle[i] != haystack[self.position + i] {
1155                     self.position += i - self.crit_pos + 1;
1156                     if !long_period {
1157                         self.memory = 0;
1158                     }
1159                     continue 'search;
1160                 }
1161             }
1162
1163             // See if the left part of the needle matches
1164             let start = if long_period { 0 } else { self.memory };
1165             for i in (start..self.crit_pos).rev() {
1166                 if needle[i] != haystack[self.position + i] {
1167                     self.position += self.period;
1168                     if !long_period {
1169                         self.memory = needle.len() - self.period;
1170                     }
1171                     continue 'search;
1172                 }
1173             }
1174
1175             // We have found a match!
1176             let match_pos = self.position;
1177
1178             // Note: add self.period instead of needle.len() to have overlapping matches
1179             self.position += needle.len();
1180             if !long_period {
1181                 self.memory = 0; // set to needle.len() - self.period for overlapping matches
1182             }
1183
1184             return S::matching(match_pos, match_pos + needle.len());
1185         }
1186     }
1187
1188     // Follows the ideas in `next()`.
1189     //
1190     // The definitions are symmetrical, with period(x) = period(reverse(x))
1191     // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
1192     // is a critical factorization, so is (reverse(v), reverse(u)).
1193     //
1194     // For the reverse case we have computed a critical factorization x = u' v'
1195     // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
1196     // thus |v'| < period(x) for the reverse.
1197     //
1198     // To search in reverse through the haystack, we search forward through
1199     // a reversed haystack with a reversed needle, matching first u' and then v'.
1200     #[inline]
1201     fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1202     where
1203         S: TwoWayStrategy,
1204     {
1205         // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1206         // are independent.
1207         let old_end = self.end;
1208         'search: loop {
1209             // Check that we have room to search in
1210             // end - needle.len() will wrap around when there is no more room,
1211             // but due to slice length limits it can never wrap all the way back
1212             // into the length of haystack.
1213             let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
1214                 Some(&b) => b,
1215                 None => {
1216                     self.end = 0;
1217                     return S::rejecting(0, old_end);
1218                 }
1219             };
1220
1221             if S::use_early_reject() && old_end != self.end {
1222                 return S::rejecting(self.end, old_end);
1223             }
1224
1225             // Quickly skip by large portions unrelated to our substring
1226             if !self.byteset_contains(front_byte) {
1227                 self.end -= needle.len();
1228                 if !long_period {
1229                     self.memory_back = needle.len();
1230                 }
1231                 continue 'search;
1232             }
1233
1234             // See if the left part of the needle matches
1235             let crit = if long_period {
1236                 self.crit_pos_back
1237             } else {
1238                 cmp::min(self.crit_pos_back, self.memory_back)
1239             };
1240             for i in (0..crit).rev() {
1241                 if needle[i] != haystack[self.end - needle.len() + i] {
1242                     self.end -= self.crit_pos_back - i;
1243                     if !long_period {
1244                         self.memory_back = needle.len();
1245                     }
1246                     continue 'search;
1247                 }
1248             }
1249
1250             // See if the right part of the needle matches
1251             let needle_end = if long_period { needle.len() } else { self.memory_back };
1252             for i in self.crit_pos_back..needle_end {
1253                 if needle[i] != haystack[self.end - needle.len() + i] {
1254                     self.end -= self.period;
1255                     if !long_period {
1256                         self.memory_back = self.period;
1257                     }
1258                     continue 'search;
1259                 }
1260             }
1261
1262             // We have found a match!
1263             let match_pos = self.end - needle.len();
1264             // Note: sub self.period instead of needle.len() to have overlapping matches
1265             self.end -= needle.len();
1266             if !long_period {
1267                 self.memory_back = needle.len();
1268             }
1269
1270             return S::matching(match_pos, match_pos + needle.len());
1271         }
1272     }
1273
1274     // Compute the maximal suffix of `arr`.
1275     //
1276     // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1277     //
1278     // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1279     // period of v.
1280     //
1281     // `order_greater` determines if lexical order is `<` or `>`. Both
1282     // orders must be computed -- the ordering with the largest `i` gives
1283     // a critical factorization.
1284     //
1285     // For long period cases, the resulting period is not exact (it is too short).
1286     #[inline]
1287     fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
1288         let mut left = 0; // Corresponds to i in the paper
1289         let mut right = 1; // Corresponds to j in the paper
1290         let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1291         // to match 0-based indexing.
1292         let mut period = 1; // Corresponds to p in the paper
1293
1294         while let Some(&a) = arr.get(right + offset) {
1295             // `left` will be inbounds when `right` is.
1296             let b = arr[left + offset];
1297             if (a < b && !order_greater) || (a > b && order_greater) {
1298                 // Suffix is smaller, period is entire prefix so far.
1299                 right += offset + 1;
1300                 offset = 0;
1301                 period = right - left;
1302             } else if a == b {
1303                 // Advance through repetition of the current period.
1304                 if offset + 1 == period {
1305                     right += offset + 1;
1306                     offset = 0;
1307                 } else {
1308                     offset += 1;
1309                 }
1310             } else {
1311                 // Suffix is larger, start over from current location.
1312                 left = right;
1313                 right += 1;
1314                 offset = 0;
1315                 period = 1;
1316             }
1317         }
1318         (left, period)
1319     }
1320
1321     // Compute the maximal suffix of the reverse of `arr`.
1322     //
1323     // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1324     //
1325     // Returns `i` where `i` is the starting index of v', from the back;
1326     // returns immediately when a period of `known_period` is reached.
1327     //
1328     // `order_greater` determines if lexical order is `<` or `>`. Both
1329     // orders must be computed -- the ordering with the largest `i` gives
1330     // a critical factorization.
1331     //
1332     // For long period cases, the resulting period is not exact (it is too short).
1333     fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize {
1334         let mut left = 0; // Corresponds to i in the paper
1335         let mut right = 1; // Corresponds to j in the paper
1336         let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1337         // to match 0-based indexing.
1338         let mut period = 1; // Corresponds to p in the paper
1339         let n = arr.len();
1340
1341         while right + offset < n {
1342             let a = arr[n - (1 + right + offset)];
1343             let b = arr[n - (1 + left + offset)];
1344             if (a < b && !order_greater) || (a > b && order_greater) {
1345                 // Suffix is smaller, period is entire prefix so far.
1346                 right += offset + 1;
1347                 offset = 0;
1348                 period = right - left;
1349             } else if a == b {
1350                 // Advance through repetition of the current period.
1351                 if offset + 1 == period {
1352                     right += offset + 1;
1353                     offset = 0;
1354                 } else {
1355                     offset += 1;
1356                 }
1357             } else {
1358                 // Suffix is larger, start over from current location.
1359                 left = right;
1360                 right += 1;
1361                 offset = 0;
1362                 period = 1;
1363             }
1364             if period == known_period {
1365                 break;
1366             }
1367         }
1368         debug_assert!(period <= known_period);
1369         left
1370     }
1371 }
1372
1373 // TwoWayStrategy allows the algorithm to either skip non-matches as quickly
1374 // as possible, or to work in a mode where it emits Rejects relatively quickly.
1375 trait TwoWayStrategy {
1376     type Output;
1377     fn use_early_reject() -> bool;
1378     fn rejecting(a: usize, b: usize) -> Self::Output;
1379     fn matching(a: usize, b: usize) -> Self::Output;
1380 }
1381
1382 /// Skip to match intervals as quickly as possible
1383 enum MatchOnly {}
1384
1385 impl TwoWayStrategy for MatchOnly {
1386     type Output = Option<(usize, usize)>;
1387
1388     #[inline]
1389     fn use_early_reject() -> bool {
1390         false
1391     }
1392     #[inline]
1393     fn rejecting(_a: usize, _b: usize) -> Self::Output {
1394         None
1395     }
1396     #[inline]
1397     fn matching(a: usize, b: usize) -> Self::Output {
1398         Some((a, b))
1399     }
1400 }
1401
1402 /// Emit Rejects regularly
1403 enum RejectAndMatch {}
1404
1405 impl TwoWayStrategy for RejectAndMatch {
1406     type Output = SearchStep;
1407
1408     #[inline]
1409     fn use_early_reject() -> bool {
1410         true
1411     }
1412     #[inline]
1413     fn rejecting(a: usize, b: usize) -> Self::Output {
1414         SearchStep::Reject(a, b)
1415     }
1416     #[inline]
1417     fn matching(a: usize, b: usize) -> Self::Output {
1418         SearchStep::Match(a, b)
1419     }
1420 }