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