src/libcore/str/pattern.rs

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