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