src/libcore/str/pattern.rs

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