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