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.
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.
11 //! The string Pattern API.
13 //! For more details, see the traits `Pattern`, `Searcher`,
14 //! `ReverseSearcher` and `DoubleEndedSearcher`.
16 #![unstable(feature = "pattern",
17 reason
= "API not fully fleshed out and ready to be stabilized",
28 /// A `Pattern<'a>` expresses that the implementing type
29 /// can be used as a string pattern for searching in a `&'a str`.
31 /// For example, both `'a'` and `"aa"` are patterns that
32 /// would match at index `1` in the string `"baaaab"`.
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
>;
41 /// Constructs the associated searcher from
42 /// `self` and the `haystack` to search in.
43 fn into_searcher(self, haystack
: &'a
str) -> Self::Searcher
;
45 /// Checks whether the pattern matches anywhere in the haystack
47 fn is_contained_in(self, haystack
: &'a
str) -> bool
{
48 self.into_searcher(haystack
).next_match().is_some()
51 /// Checks whether the pattern matches at the front of the haystack
53 fn is_prefix_of(self, haystack
: &'a
str) -> bool
{
54 match self.into_searcher(haystack
).next() {
55 SearchStep
::Match(0, _
) => true,
60 /// Checks whether the pattern matches at the back of the haystack
62 fn is_suffix_of(self, haystack
: &'a
str) -> bool
63 where Self::Searcher
: ReverseSearcher
<'a
>
65 match self.into_searcher(haystack
).next_back() {
66 SearchStep
::Match(_
, j
) if haystack
.len() == j
=> true,
74 /// Result of calling `Searcher::next()` or `ReverseSearcher::next_back()`.
75 #[derive(Copy, Clone, Eq, PartialEq, Debug)]
77 /// Expresses that a match of the pattern has been found at
80 /// Expresses that `haystack[a..b]` has been rejected as a possible match
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.
86 /// Expresses that every byte of the haystack has been visited, ending
91 /// A searcher for a string pattern.
93 /// This trait provides methods for searching for non-overlapping
94 /// matches of a pattern starting from the front (left) of a string.
96 /// It will be implemented by associated `Searcher`
97 /// types of the `Pattern` trait.
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 underlying string to be searched in
106 /// Will always return the same `&str`
107 fn haystack(&self) -> &'a
str;
109 /// Performs the next search step starting from the front.
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
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.
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.
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
;
129 /// Find the next `Match` result. See `next()`
131 fn next_match(&mut self) -> Option
<(usize, usize)> {
134 SearchStep
::Match(a
, b
) => return Some((a
, b
)),
135 SearchStep
::Done
=> return None
,
141 /// Find the next `Reject` result. See `next()`
143 fn next_reject(&mut self) -> Option
<(usize, usize)> {
146 SearchStep
::Reject(a
, b
) => return Some((a
, b
)),
147 SearchStep
::Done
=> return None
,
154 /// A reverse searcher for a string pattern.
156 /// This trait provides methods for searching for non-overlapping
157 /// matches of a pattern starting from the back (right) of a string.
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.
163 /// The index ranges returned by this trait are not required
164 /// to exactly match those of the forward search in reverse.
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.
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
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.
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.
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
;
189 /// Find the next `Match` result. See `next_back()`
191 fn next_match_back(&mut self) -> Option
<(usize, usize)>{
193 match self.next_back() {
194 SearchStep
::Match(a
, b
) => return Some((a
, b
)),
195 SearchStep
::Done
=> return None
,
201 /// Find the next `Reject` result. See `next_back()`
203 fn next_reject_back(&mut self) -> Option
<(usize, usize)>{
205 match self.next_back() {
206 SearchStep
::Reject(a
, b
) => return Some((a
, b
)),
207 SearchStep
::Done
=> return None
,
214 /// A marker trait to express that a `ReverseSearcher`
215 /// can be used for a `DoubleEndedIterator` implementation.
217 /// For this, the impl of `Searcher` and `ReverseSearcher` need
218 /// to follow these conditions:
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".
228 /// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
229 /// `char` only requires looking at one at a time, which behaves the same
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
> {}
237 /////////////////////////////////////////////////////////////////////////////
238 // Impl for a CharEq wrapper
239 /////////////////////////////////////////////////////////////////////////////
243 fn matches(&mut self, c
: char) -> bool
;
244 fn only_ascii(&self) -> bool
;
247 impl CharEq
for char {
249 fn matches(&mut self, c
: char) -> bool { *self == c }
252 fn only_ascii(&self) -> bool { (*self as u32) < 128 }
255 impl<F
> CharEq
for F
where F
: FnMut(char) -> bool
{
257 fn matches(&mut self, c
: char) -> bool { (*self)(c) }
260 fn only_ascii(&self) -> bool { false }
263 impl<'a
> CharEq
for &'a
[char] {
265 fn matches(&mut self, c
: char) -> bool
{
266 self.iter().any(|&m
| { let mut m = m; m.matches(c) }
)
270 fn only_ascii(&self) -> bool
{
271 self.iter().all(|m
| m
.only_ascii())
275 struct CharEqPattern
<C
: CharEq
>(C
);
277 #[derive(Clone, Debug)]
278 struct CharEqSearcher
<'a
, C
: CharEq
> {
281 char_indices
: super::CharIndices
<'a
>,
286 impl<'a
, C
: CharEq
> Pattern
<'a
> for CharEqPattern
<C
> {
287 type Searcher
= CharEqSearcher
<'a
, C
>;
290 fn into_searcher(self, haystack
: &'a
str) -> CharEqSearcher
<'a
, C
> {
292 ascii_only
: self.0.only_ascii(),
295 char_indices
: haystack
.char_indices(),
300 unsafe impl<'a
, C
: CharEq
> Searcher
<'a
> for CharEqSearcher
<'a
, C
> {
302 fn haystack(&self) -> &'a
str {
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
);
318 return SearchStep
::Reject(i
, i
+ char_len
);
325 unsafe impl<'a
, C
: CharEq
> ReverseSearcher
<'a
> for CharEqSearcher
<'a
, C
> {
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
);
338 return SearchStep
::Reject(i
, i
+ char_len
);
345 impl<'a
, C
: CharEq
> DoubleEndedSearcher
<'a
> for CharEqSearcher
<'a
, C
> {}
347 /////////////////////////////////////////////////////////////////////////////
349 macro_rules
! pattern_methods
{
350 ($t
:ty
, $pmap
:expr
, $smap
:expr
) => {
354 fn into_searcher(self, haystack
: &'a
str) -> $t
{
355 ($smap
)(($pmap
)(self).into_searcher(haystack
))
359 fn is_contained_in(self, haystack
: &'a
str) -> bool
{
360 ($pmap
)(self).is_contained_in(haystack
)
364 fn is_prefix_of(self, haystack
: &'a
str) -> bool
{
365 ($pmap
)(self).is_prefix_of(haystack
)
369 fn is_suffix_of(self, haystack
: &'a
str) -> bool
370 where $t
: ReverseSearcher
<'a
>
372 ($pmap
)(self).is_suffix_of(haystack
)
377 macro_rules
! searcher_methods
{
380 fn haystack(&self) -> &'a
str {
384 fn next(&mut self) -> SearchStep
{
388 fn next_match(&mut self) -> Option
<(usize, usize)> {
392 fn next_reject(&mut self) -> Option
<(usize, usize)> {
398 fn next_back(&mut self) -> SearchStep
{
402 fn next_match_back(&mut self) -> Option
<(usize, usize)> {
403 self.0.next_match_back()
406 fn next_reject_back(&mut self) -> Option
<(usize, usize)> {
407 self.0.next_reject_back()
412 /////////////////////////////////////////////////////////////////////////////
414 /////////////////////////////////////////////////////////////////////////////
416 /// Associated type for `<char as Pattern<'a>>::Searcher`.
417 #[derive(Clone, Debug)]
418 pub struct CharSearcher
<'a
>(<CharEqPattern
<char> as Pattern
<'a
>>::Searcher
);
420 unsafe impl<'a
> Searcher
<'a
> for CharSearcher
<'a
> {
421 searcher_methods
!(forward
);
424 unsafe impl<'a
> ReverseSearcher
<'a
> for CharSearcher
<'a
> {
425 searcher_methods
!(reverse
);
428 impl<'a
> DoubleEndedSearcher
<'a
> for CharSearcher
<'a
> {}
430 /// Searches for chars that are equal to a given char
431 impl<'a
> Pattern
<'a
> for char {
432 type Searcher
= CharSearcher
<'a
>;
435 fn into_searcher(self, haystack
: &'a
str) -> Self::Searcher
{
436 CharSearcher(CharEqPattern(self).into_searcher(haystack
))
440 fn is_contained_in(self, haystack
: &'a
str) -> bool
{
441 if (self as u32) < 128 {
442 haystack
.as_bytes().contains(&(self as u8))
444 let mut buffer
= [0u8; 4];
445 self.encode_utf8(&mut buffer
).is_contained_in(haystack
)
450 fn is_prefix_of(self, haystack
: &'a
str) -> bool
{
451 CharEqPattern(self).is_prefix_of(haystack
)
455 fn is_suffix_of(self, haystack
: &'a
str) -> bool
where Self::Searcher
: ReverseSearcher
<'a
>
457 CharEqPattern(self).is_suffix_of(haystack
)
461 /////////////////////////////////////////////////////////////////////////////
463 /////////////////////////////////////////////////////////////////////////////
465 // Todo: Change / Remove due to ambiguity in meaning.
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
);
471 unsafe impl<'a
, 'b
> Searcher
<'a
> for CharSliceSearcher
<'a
, 'b
> {
472 searcher_methods
!(forward
);
475 unsafe impl<'a
, 'b
> ReverseSearcher
<'a
> for CharSliceSearcher
<'a
, 'b
> {
476 searcher_methods
!(reverse
);
479 impl<'a
, 'b
> DoubleEndedSearcher
<'a
> for CharSliceSearcher
<'a
, 'b
> {}
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
);
486 /////////////////////////////////////////////////////////////////////////////
487 // Impl for F: FnMut(char) -> bool
488 /////////////////////////////////////////////////////////////////////////////
490 /// Associated type for `<F as Pattern<'a>>::Searcher`.
492 pub struct CharPredicateSearcher
<'a
, F
>(<CharEqPattern
<F
> as Pattern
<'a
>>::Searcher
)
493 where F
: FnMut(char) -> bool
;
495 impl<'a
, F
> fmt
::Debug
for CharPredicateSearcher
<'a
, F
>
496 where F
: FnMut(char) -> bool
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
)
506 unsafe impl<'a
, F
> Searcher
<'a
> for CharPredicateSearcher
<'a
, F
>
507 where F
: FnMut(char) -> bool
509 searcher_methods
!(forward
);
512 unsafe impl<'a
, F
> ReverseSearcher
<'a
> for CharPredicateSearcher
<'a
, F
>
513 where F
: FnMut(char) -> bool
515 searcher_methods
!(reverse
);
518 impl<'a
, F
> DoubleEndedSearcher
<'a
> for CharPredicateSearcher
<'a
, F
>
519 where F
: FnMut(char) -> bool {}
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
);
526 /////////////////////////////////////////////////////////////////////////////
528 /////////////////////////////////////////////////////////////////////////////
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
);
535 /////////////////////////////////////////////////////////////////////////////
537 /////////////////////////////////////////////////////////////////////////////
539 /// Non-allocating substring search.
541 /// Will handle the pattern `""` as returning empty matches at each character
543 impl<'a
, 'b
> Pattern
<'a
> for &'b
str {
544 type Searcher
= StrSearcher
<'a
, 'b
>;
547 fn into_searcher(self, haystack
: &'a
str) -> StrSearcher
<'a
, 'b
> {
548 StrSearcher
::new(haystack
, self)
551 /// Checks whether the pattern matches at the front of the haystack
553 fn is_prefix_of(self, haystack
: &'a
str) -> bool
{
554 haystack
.is_char_boundary(self.len()) &&
555 self == &haystack
[..self.len()]
558 /// Checks whether the pattern matches at the back of the haystack
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()..]
568 /////////////////////////////////////////////////////////////////////////////
569 // Two Way substring searcher
570 /////////////////////////////////////////////////////////////////////////////
572 #[derive(Clone, Debug)]
573 /// Associated type for `<&str as Pattern<'a>>::Searcher`.
574 pub struct StrSearcher
<'a
, 'b
> {
578 searcher
: StrSearcherImpl
,
581 #[derive(Clone, Debug)]
582 enum StrSearcherImpl
{
584 TwoWay(TwoWaySearcher
),
587 #[derive(Clone, Debug)]
595 impl<'a
, 'b
> StrSearcher
<'a
, 'b
> {
596 fn new(haystack
: &'a
str, needle
: &'b
str) -> StrSearcher
<'a
, 'b
> {
597 if needle
.is_empty() {
601 searcher
: StrSearcherImpl
::Empty(EmptyNeedle
{
612 searcher
: StrSearcherImpl
::TwoWay(
613 TwoWaySearcher
::new(needle
.as_bytes(), haystack
.len())
620 unsafe impl<'a
, 'b
> Searcher
<'a
> for StrSearcher
<'a
, 'b
> {
622 fn haystack(&self) -> &'a
str {
627 fn next(&mut self) -> SearchStep
{
628 match self.searcher
{
629 StrSearcherImpl
::Empty(ref mut searcher
) => {
630 // empty needle rejects every char and matches every empty string between them
631 let is_match
= searcher
.is_match_fw
;
632 searcher
.is_match_fw
= !searcher
.is_match_fw
;
633 let pos
= searcher
.position
;
634 match self.haystack
[pos
..].chars().next() {
635 _
if is_match
=> SearchStep
::Match(pos
, pos
),
636 None
=> SearchStep
::Done
,
638 searcher
.position
+= ch
.len_utf8();
639 SearchStep
::Reject(pos
, searcher
.position
)
643 StrSearcherImpl
::TwoWay(ref mut searcher
) => {
644 // TwoWaySearcher produces valid *Match* indices that split at char boundaries
645 // as long as it does correct matching and that haystack and needle are
647 // *Rejects* from the algorithm can fall on any indices, but we will walk them
648 // manually to the next character boundary, so that they are utf-8 safe.
649 if searcher
.position
== self.haystack
.len() {
650 return SearchStep
::Done
;
652 let is_long
= searcher
.memory
== usize::MAX
;
653 match searcher
.next
::<RejectAndMatch
>(self.haystack
.as_bytes(),
654 self.needle
.as_bytes(),
657 SearchStep
::Reject(a
, mut b
) => {
658 // skip to next char boundary
659 while !self.haystack
.is_char_boundary(b
) {
662 searcher
.position
= cmp
::max(b
, searcher
.position
);
663 SearchStep
::Reject(a
, b
)
665 otherwise
=> otherwise
,
672 fn next_match(&mut self) -> Option
<(usize, usize)> {
673 match self.searcher
{
674 StrSearcherImpl
::Empty(..) => {
677 SearchStep
::Match(a
, b
) => return Some((a
, b
)),
678 SearchStep
::Done
=> return None
,
679 SearchStep
::Reject(..) => { }
683 StrSearcherImpl
::TwoWay(ref mut searcher
) => {
684 let is_long
= searcher
.memory
== usize::MAX
;
685 // write out `true` and `false` cases to encourage the compiler
686 // to specialize the two cases separately.
688 searcher
.next
::<MatchOnly
>(self.haystack
.as_bytes(),
689 self.needle
.as_bytes(),
692 searcher
.next
::<MatchOnly
>(self.haystack
.as_bytes(),
693 self.needle
.as_bytes(),
701 unsafe impl<'a
, 'b
> ReverseSearcher
<'a
> for StrSearcher
<'a
, 'b
> {
703 fn next_back(&mut self) -> SearchStep
{
704 match self.searcher
{
705 StrSearcherImpl
::Empty(ref mut searcher
) => {
706 let is_match
= searcher
.is_match_bw
;
707 searcher
.is_match_bw
= !searcher
.is_match_bw
;
708 let end
= searcher
.end
;
709 match self.haystack
[..end
].chars().next_back() {
710 _
if is_match
=> SearchStep
::Match(end
, end
),
711 None
=> SearchStep
::Done
,
713 searcher
.end
-= ch
.len_utf8();
714 SearchStep
::Reject(searcher
.end
, end
)
718 StrSearcherImpl
::TwoWay(ref mut searcher
) => {
719 if searcher
.end
== 0 {
720 return SearchStep
::Done
;
722 let is_long
= searcher
.memory
== usize::MAX
;
723 match searcher
.next_back
::<RejectAndMatch
>(self.haystack
.as_bytes(),
724 self.needle
.as_bytes(),
727 SearchStep
::Reject(mut a
, b
) => {
728 // skip to next char boundary
729 while !self.haystack
.is_char_boundary(a
) {
732 searcher
.end
= cmp
::min(a
, searcher
.end
);
733 SearchStep
::Reject(a
, b
)
735 otherwise
=> otherwise
,
742 fn next_match_back(&mut self) -> Option
<(usize, usize)> {
743 match self.searcher
{
744 StrSearcherImpl
::Empty(..) => {
746 match self.next_back() {
747 SearchStep
::Match(a
, b
) => return Some((a
, b
)),
748 SearchStep
::Done
=> return None
,
749 SearchStep
::Reject(..) => { }
753 StrSearcherImpl
::TwoWay(ref mut searcher
) => {
754 let is_long
= searcher
.memory
== usize::MAX
;
755 // write out `true` and `false`, like `next_match`
757 searcher
.next_back
::<MatchOnly
>(self.haystack
.as_bytes(),
758 self.needle
.as_bytes(),
761 searcher
.next_back
::<MatchOnly
>(self.haystack
.as_bytes(),
762 self.needle
.as_bytes(),
770 /// The internal state of the two-way substring search algorithm.
771 #[derive(Clone, Debug)]
772 struct TwoWaySearcher
{
774 /// critical factorization index
776 /// critical factorization index for reversed needle
777 crit_pos_back
: usize,
779 /// `byteset` is an extension (not part of the two way algorithm);
780 /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
781 /// to a (byte & 63) == j present in the needle.
787 /// index into needle before which we have already matched
789 /// index into needle after which we have already matched
794 This is the Two-Way search algorithm, which was introduced in the paper:
795 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
797 Here's some background information.
799 A *word* is a string of symbols. The *length* of a word should be a familiar
800 notion, and here we denote it for any word x by |x|.
801 (We also allow for the possibility of the *empty word*, a word of length zero).
803 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
804 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
805 For example, both 1 and 2 are periods for the string "aa". As another example,
806 the only period of the string "abcd" is 4.
808 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
809 This is always well-defined since every non-empty word x has at least one period,
810 |x|. We sometimes call this *the period* of x.
812 If u, v and x are words such that x = uv, where uv is the concatenation of u and
813 v, then we say that (u, v) is a *factorization* of x.
815 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
816 that both of the following hold
818 - either w is a suffix of u or u is a suffix of w
819 - either w is a prefix of v or v is a prefix of w
821 then w is said to be a *repetition* for the factorization (u, v).
823 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
826 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
827 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
828 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
829 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
831 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
832 so every factorization has at least one repetition.
834 If x is a string and (u, v) is a factorization for x, then a *local period* for
835 (u, v) is an integer r such that there is some word w such that |w| = r and w is
836 a repetition for (u, v).
838 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
839 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
840 is well-defined (because each non-empty word has at least one factorization, as
843 It can be proven that the following is an equivalent definition of a local period
844 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
845 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
846 defined. (i.e. i > 0 and i + r < |x|).
848 Using the above reformulation, it is easy to prove that
850 1 <= local_period(u, v) <= period(uv)
852 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
853 *critical factorization*.
855 The algorithm hinges on the following theorem, which is stated without proof:
857 **Critical Factorization Theorem** Any word x has at least one critical
858 factorization (u, v) such that |u| < period(x).
860 The purpose of maximal_suffix is to find such a critical factorization.
862 If the period is short, compute another factorization x = u' v' to use
863 for reverse search, chosen instead so that |v'| < period(x).
866 impl TwoWaySearcher
{
867 fn new(needle
: &[u8], end
: usize) -> TwoWaySearcher
{
868 let (crit_pos_false
, period_false
) = TwoWaySearcher
::maximal_suffix(needle
, false);
869 let (crit_pos_true
, period_true
) = TwoWaySearcher
::maximal_suffix(needle
, true);
871 let (crit_pos
, period
) =
872 if crit_pos_false
> crit_pos_true
{
873 (crit_pos_false
, period_false
)
875 (crit_pos_true
, period_true
)
878 // A particularly readable explanation of what's going on here can be found
879 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
880 // see the code for "Algorithm CP" on p. 323.
882 // What's going on is we have some critical factorization (u, v) of the
883 // needle, and we want to determine whether u is a suffix of
884 // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
885 // "Algorithm CP2", which is optimized for when the period of the needle
887 if &needle
[..crit_pos
] == &needle
[period
.. period
+ crit_pos
] {
888 // short period case -- the period is exact
889 // compute a separate critical factorization for the reversed needle
890 // x = u' v' where |v'| < period(x).
892 // This is sped up by the period being known already.
893 // Note that a case like x = "acba" may be factored exactly forwards
894 // (crit_pos = 1, period = 3) while being factored with approximate
895 // period in reverse (crit_pos = 2, period = 2). We use the given
896 // reverse factorization but keep the exact period.
897 let crit_pos_back
= needle
.len() - cmp
::max(
898 TwoWaySearcher
::reverse_maximal_suffix(needle
, period
, false),
899 TwoWaySearcher
::reverse_maximal_suffix(needle
, period
, true));
905 byteset
: Self::byteset_create(&needle
[..period
]),
910 memory_back
: needle
.len(),
913 // long period case -- we have an approximation to the actual period,
914 // and don't use memorization.
916 // Approximate the period by lower bound max(|u|, |v|) + 1.
917 // The critical factorization is efficient to use for both forward and
922 crit_pos_back
: crit_pos
,
923 period
: cmp
::max(crit_pos
, needle
.len() - crit_pos
) + 1,
924 byteset
: Self::byteset_create(needle
),
928 memory
: usize::MAX
, // Dummy value to signify that the period is long
929 memory_back
: usize::MAX
,
935 fn byteset_create(bytes
: &[u8]) -> u64 {
936 bytes
.iter().fold(0, |a
, &b
| (1 << (b
& 0x3f)) | a
)
940 fn byteset_contains(&self, byte
: u8) -> bool
{
941 (self.byteset
>> ((byte
& 0x3f) as usize)) & 1 != 0
944 // One of the main ideas of Two-Way is that we factorize the needle into
945 // two halves, (u, v), and begin trying to find v in the haystack by scanning
946 // left to right. If v matches, we try to match u by scanning right to left.
947 // How far we can jump when we encounter a mismatch is all based on the fact
948 // that (u, v) is a critical factorization for the needle.
950 fn next
<S
>(&mut self, haystack
: &[u8], needle
: &[u8], long_period
: bool
)
952 where S
: TwoWayStrategy
954 // `next()` uses `self.position` as its cursor
955 let old_pos
= self.position
;
956 let needle_last
= needle
.len() - 1;
958 // Check that we have room to search in
959 // position + needle_last can not overflow if we assume slices
960 // are bounded by isize's range.
961 let tail_byte
= match haystack
.get(self.position
+ needle_last
) {
964 self.position
= haystack
.len();
965 return S
::rejecting(old_pos
, self.position
);
969 if S
::use_early_reject() && old_pos
!= self.position
{
970 return S
::rejecting(old_pos
, self.position
);
973 // Quickly skip by large portions unrelated to our substring
974 if !self.byteset_contains(tail_byte
) {
975 self.position
+= needle
.len();
982 // See if the right part of the needle matches
983 let start
= if long_period { self.crit_pos }
984 else { cmp::max(self.crit_pos, self.memory) }
;
985 for i
in start
..needle
.len() {
986 if needle
[i
] != haystack
[self.position
+ i
] {
987 self.position
+= i
- self.crit_pos
+ 1;
995 // See if the left part of the needle matches
996 let start
= if long_period { 0 }
else { self.memory }
;
997 for i
in (start
..self.crit_pos
).rev() {
998 if needle
[i
] != haystack
[self.position
+ i
] {
999 self.position
+= self.period
;
1001 self.memory
= needle
.len() - self.period
;
1007 // We have found a match!
1008 let match_pos
= self.position
;
1010 // Note: add self.period instead of needle.len() to have overlapping matches
1011 self.position
+= needle
.len();
1013 self.memory
= 0; // set to needle.len() - self.period for overlapping matches
1016 return S
::matching(match_pos
, match_pos
+ needle
.len());
1020 // Follows the ideas in `next()`.
1022 // The definitions are symmetrical, with period(x) = period(reverse(x))
1023 // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
1024 // is a critical factorization, so is (reverse(v), reverse(u)).
1026 // For the reverse case we have computed a critical factorization x = u' v'
1027 // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
1028 // thus |v'| < period(x) for the reverse.
1030 // To search in reverse through the haystack, we search forward through
1031 // a reversed haystack with a reversed needle, matching first u' and then v'.
1033 fn next_back
<S
>(&mut self, haystack
: &[u8], needle
: &[u8], long_period
: bool
)
1035 where S
: TwoWayStrategy
1037 // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1039 let old_end
= self.end
;
1041 // Check that we have room to search in
1042 // end - needle.len() will wrap around when there is no more room,
1043 // but due to slice length limits it can never wrap all the way back
1044 // into the length of haystack.
1045 let front_byte
= match haystack
.get(self.end
.wrapping_sub(needle
.len())) {
1049 return S
::rejecting(0, old_end
);
1053 if S
::use_early_reject() && old_end
!= self.end
{
1054 return S
::rejecting(self.end
, old_end
);
1057 // Quickly skip by large portions unrelated to our substring
1058 if !self.byteset_contains(front_byte
) {
1059 self.end
-= needle
.len();
1061 self.memory_back
= needle
.len();
1066 // See if the left part of the needle matches
1067 let crit
= if long_period { self.crit_pos_back }
1068 else { cmp::min(self.crit_pos_back, self.memory_back) }
;
1069 for i
in (0..crit
).rev() {
1070 if needle
[i
] != haystack
[self.end
- needle
.len() + i
] {
1071 self.end
-= self.crit_pos_back
- i
;
1073 self.memory_back
= needle
.len();
1079 // See if the right part of the needle matches
1080 let needle_end
= if long_period { needle.len() }
1081 else { self.memory_back }
;
1082 for i
in self.crit_pos_back
..needle_end
{
1083 if needle
[i
] != haystack
[self.end
- needle
.len() + i
] {
1084 self.end
-= self.period
;
1086 self.memory_back
= self.period
;
1092 // We have found a match!
1093 let match_pos
= self.end
- needle
.len();
1094 // Note: sub self.period instead of needle.len() to have overlapping matches
1095 self.end
-= needle
.len();
1097 self.memory_back
= needle
.len();
1100 return S
::matching(match_pos
, match_pos
+ needle
.len());
1104 // Compute the maximal suffix of `arr`.
1106 // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1108 // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1111 // `order_greater` determines if lexical order is `<` or `>`. Both
1112 // orders must be computed -- the ordering with the largest `i` gives
1113 // a critical factorization.
1115 // For long period cases, the resulting period is not exact (it is too short).
1117 fn maximal_suffix(arr
: &[u8], order_greater
: bool
) -> (usize, usize) {
1118 let mut left
= 0; // Corresponds to i in the paper
1119 let mut right
= 1; // Corresponds to j in the paper
1120 let mut offset
= 0; // Corresponds to k in the paper, but starting at 0
1121 // to match 0-based indexing.
1122 let mut period
= 1; // Corresponds to p in the paper
1124 while let Some(&a
) = arr
.get(right
+ offset
) {
1125 // `left` will be inbounds when `right` is.
1126 let b
= arr
[left
+ offset
];
1127 if (a
< b
&& !order_greater
) || (a
> b
&& order_greater
) {
1128 // Suffix is smaller, period is entire prefix so far.
1129 right
+= offset
+ 1;
1131 period
= right
- left
;
1133 // Advance through repetition of the current period.
1134 if offset
+ 1 == period
{
1135 right
+= offset
+ 1;
1141 // Suffix is larger, start over from current location.
1151 // Compute the maximal suffix of the reverse of `arr`.
1153 // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1155 // Returns `i` where `i` is the starting index of v', from the back;
1156 // returns immediately when a period of `known_period` is reached.
1158 // `order_greater` determines if lexical order is `<` or `>`. Both
1159 // orders must be computed -- the ordering with the largest `i` gives
1160 // a critical factorization.
1162 // For long period cases, the resulting period is not exact (it is too short).
1163 fn reverse_maximal_suffix(arr
: &[u8], known_period
: usize,
1164 order_greater
: bool
) -> usize
1166 let mut left
= 0; // Corresponds to i in the paper
1167 let mut right
= 1; // Corresponds to j in the paper
1168 let mut offset
= 0; // Corresponds to k in the paper, but starting at 0
1169 // to match 0-based indexing.
1170 let mut period
= 1; // Corresponds to p in the paper
1173 while right
+ offset
< n
{
1174 let a
= arr
[n
- (1 + right
+ offset
)];
1175 let b
= arr
[n
- (1 + left
+ offset
)];
1176 if (a
< b
&& !order_greater
) || (a
> b
&& order_greater
) {
1177 // Suffix is smaller, period is entire prefix so far.
1178 right
+= offset
+ 1;
1180 period
= right
- left
;
1182 // Advance through repetition of the current period.
1183 if offset
+ 1 == period
{
1184 right
+= offset
+ 1;
1190 // Suffix is larger, start over from current location.
1196 if period
== known_period
{
1200 debug_assert
!(period
<= known_period
);
1205 // TwoWayStrategy allows the algorithm to either skip non-matches as quickly
1206 // as possible, or to work in a mode where it emits Rejects relatively quickly.
1207 trait TwoWayStrategy
{
1209 fn use_early_reject() -> bool
;
1210 fn rejecting(a
: usize, b
: usize) -> Self::Output
;
1211 fn matching(a
: usize, b
: usize) -> Self::Output
;
1214 /// Skip to match intervals as quickly as possible
1217 impl TwoWayStrategy
for MatchOnly
{
1218 type Output
= Option
<(usize, usize)>;
1221 fn use_early_reject() -> bool { false }
1223 fn rejecting(_a
: usize, _b
: usize) -> Self::Output { None }
1225 fn matching(a
: usize, b
: usize) -> Self::Output { Some((a, b)) }
1228 /// Emit Rejects regularly
1229 enum RejectAndMatch { }
1231 impl TwoWayStrategy
for RejectAndMatch
{
1232 type Output
= SearchStep
;
1235 fn use_early_reject() -> bool { true }
1237 fn rejecting(a
: usize, b
: usize) -> Self::Output { SearchStep::Reject(a, b) }
1239 fn matching(a
: usize, b
: usize) -> Self::Output { SearchStep::Match(a, b) }