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