]> git.proxmox.com Git - rustc.git/blob - src/libcore/str/pattern.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / 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 }