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