core/str/pattern.rs
1//! The string Pattern API.
2//!
3//! The Pattern API provides a generic mechanism for using different pattern
4//! types when searching through a string.
5//!
6//! For more details, see the traits [`Pattern`], [`Searcher`],
7//! [`ReverseSearcher`], and [`DoubleEndedSearcher`].
8//!
9//! Although this API is unstable, it is exposed via stable APIs on the
10//! [`str`] type.
11//!
12//! # Examples
13//!
14//! [`Pattern`] is [implemented][pattern-impls] in the stable API for
15//! [`&str`][`str`], [`char`], slices of [`char`], and functions and closures
16//! implementing `FnMut(char) -> bool`.
17//!
18//! ```
19//! let s = "Can you find a needle in a haystack?";
20//!
21//! // &str pattern
22//! assert_eq!(s.find("you"), Some(4));
23//! // char pattern
24//! assert_eq!(s.find('n'), Some(2));
25//! // array of chars pattern
26//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u']), Some(1));
27//! // slice of chars pattern
28//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u'][..]), Some(1));
29//! // closure pattern
30//! assert_eq!(s.find(|c: char| c.is_ascii_punctuation()), Some(35));
31//! ```
32//!
33//! [pattern-impls]: Pattern#implementors
34
35#![unstable(
36 feature = "pattern",
37 reason = "API not fully fleshed out and ready to be stabilized",
38 issue = "27721"
39)]
40
41use crate::cmp::Ordering;
42use crate::convert::TryInto as _;
43use crate::slice::memchr;
44use crate::{cmp, fmt};
45
46// Pattern
47
48/// A string pattern.
49///
50/// A `Pattern` expresses that the implementing type
51/// can be used as a string pattern for searching in a [`&str`][str].
52///
53/// For example, both `'a'` and `"aa"` are patterns that
54/// would match at index `1` in the string `"baaaab"`.
55///
56/// The trait itself acts as a builder for an associated
57/// [`Searcher`] type, which does the actual work of finding
58/// occurrences of the pattern in a string.
59///
60/// Depending on the type of the pattern, the behavior of methods like
61/// [`str::find`] and [`str::contains`] can change. The table below describes
62/// some of those behaviors.
63///
64/// | Pattern type | Match condition |
65/// |--------------------------|-------------------------------------------|
66/// | `&str` | is substring |
67/// | `char` | is contained in string |
68/// | `&[char]` | any char in slice is contained in string |
69/// | `F: FnMut(char) -> bool` | `F` returns `true` for a char in string |
70/// | `&&str` | is substring |
71/// | `&String` | is substring |
72///
73/// # Examples
74///
75/// ```
76/// // &str
77/// assert_eq!("abaaa".find("ba"), Some(1));
78/// assert_eq!("abaaa".find("bac"), None);
79///
80/// // char
81/// assert_eq!("abaaa".find('a'), Some(0));
82/// assert_eq!("abaaa".find('b'), Some(1));
83/// assert_eq!("abaaa".find('c'), None);
84///
85/// // &[char; N]
86/// assert_eq!("ab".find(&['b', 'a']), Some(0));
87/// assert_eq!("abaaa".find(&['a', 'z']), Some(0));
88/// assert_eq!("abaaa".find(&['c', 'd']), None);
89///
90/// // &[char]
91/// assert_eq!("ab".find(&['b', 'a'][..]), Some(0));
92/// assert_eq!("abaaa".find(&['a', 'z'][..]), Some(0));
93/// assert_eq!("abaaa".find(&['c', 'd'][..]), None);
94///
95/// // FnMut(char) -> bool
96/// assert_eq!("abcdef_z".find(|ch| ch > 'd' && ch < 'y'), Some(4));
97/// assert_eq!("abcddd_z".find(|ch| ch > 'd' && ch < 'y'), None);
98/// ```
99pub trait Pattern: Sized {
100 /// Associated searcher for this pattern
101 type Searcher<'a>: Searcher<'a>;
102
103 /// Constructs the associated searcher from
104 /// `self` and the `haystack` to search in.
105 fn into_searcher(self, haystack: &str) -> Self::Searcher<'_>;
106
107 /// Checks whether the pattern matches anywhere in the haystack
108 #[inline]
109 fn is_contained_in(self, haystack: &str) -> bool {
110 self.into_searcher(haystack).next_match().is_some()
111 }
112
113 /// Checks whether the pattern matches at the front of the haystack
114 #[inline]
115 fn is_prefix_of(self, haystack: &str) -> bool {
116 matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
117 }
118
119 /// Checks whether the pattern matches at the back of the haystack
120 #[inline]
121 fn is_suffix_of<'a>(self, haystack: &'a str) -> bool
122 where
123 Self::Searcher<'a>: ReverseSearcher<'a>,
124 {
125 matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
126 }
127
128 /// Removes the pattern from the front of haystack, if it matches.
129 #[inline]
130 fn strip_prefix_of(self, haystack: &str) -> Option<&str> {
131 if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() {
132 debug_assert_eq!(
133 start, 0,
134 "The first search step from Searcher \
135 must include the first character"
136 );
137 // SAFETY: `Searcher` is known to return valid indices.
138 unsafe { Some(haystack.get_unchecked(len..)) }
139 } else {
140 None
141 }
142 }
143
144 /// Removes the pattern from the back of haystack, if it matches.
145 #[inline]
146 fn strip_suffix_of<'a>(self, haystack: &'a str) -> Option<&'a str>
147 where
148 Self::Searcher<'a>: ReverseSearcher<'a>,
149 {
150 if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() {
151 debug_assert_eq!(
152 end,
153 haystack.len(),
154 "The first search step from ReverseSearcher \
155 must include the last character"
156 );
157 // SAFETY: `Searcher` is known to return valid indices.
158 unsafe { Some(haystack.get_unchecked(..start)) }
159 } else {
160 None
161 }
162 }
163
164 /// Returns the pattern as utf-8 bytes if possible.
165 fn as_utf8_pattern(&self) -> Option<Utf8Pattern<'_>> {
166 None
167 }
168}
169/// Result of calling [`Pattern::as_utf8_pattern()`].
170/// Can be used for inspecting the contents of a [`Pattern`] in cases
171/// where the underlying representation can be represented as UTF-8.
172#[derive(Copy, Clone, Eq, PartialEq, Debug)]
173pub enum Utf8Pattern<'a> {
174 /// Type returned by String and str types.
175 StringPattern(&'a [u8]),
176 /// Type returned by char types.
177 CharPattern(char),
178}
179
180// Searcher
181
182/// Result of calling [`Searcher::next()`] or [`ReverseSearcher::next_back()`].
183#[derive(Copy, Clone, Eq, PartialEq, Debug)]
184pub enum SearchStep {
185 /// Expresses that a match of the pattern has been found at
186 /// `haystack[a..b]`.
187 Match(usize, usize),
188 /// Expresses that `haystack[a..b]` has been rejected as a possible match
189 /// of the pattern.
190 ///
191 /// Note that there might be more than one `Reject` between two `Match`es,
192 /// there is no requirement for them to be combined into one.
193 Reject(usize, usize),
194 /// Expresses that every byte of the haystack has been visited, ending
195 /// the iteration.
196 Done,
197}
198
199/// A searcher for a string pattern.
200///
201/// This trait provides methods for searching for non-overlapping
202/// matches of a pattern starting from the front (left) of a string.
203///
204/// It will be implemented by associated `Searcher`
205/// types of the [`Pattern`] trait.
206///
207/// The trait is marked unsafe because the indices returned by the
208/// [`next()`][Searcher::next] methods are required to lie on valid utf8
209/// boundaries in the haystack. This enables consumers of this trait to
210/// slice the haystack without additional runtime checks.
211pub unsafe trait Searcher<'a> {
212 /// Getter for the underlying string to be searched in
213 ///
214 /// Will always return the same [`&str`][str].
215 fn haystack(&self) -> &'a str;
216
217 /// Performs the next search step starting from the front.
218 ///
219 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches
220 /// the pattern.
221 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` can
222 /// not match the pattern, even partially.
223 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack has
224 /// been visited.
225 ///
226 /// The stream of [`Match`][SearchStep::Match] and
227 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
228 /// will contain index ranges that are adjacent, non-overlapping,
229 /// covering the whole haystack, and laying on utf8 boundaries.
230 ///
231 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
232 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
233 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
234 ///
235 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
236 /// might produce the stream
237 /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
238 fn next(&mut self) -> SearchStep;
239
240 /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next].
241 ///
242 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
243 /// of this and [`next_reject`][Searcher::next_reject] will overlap. This will return
244 /// `(start_match, end_match)`, where start_match is the index of where
245 /// the match begins, and end_match is the index after the end of the match.
246 #[inline]
247 fn next_match(&mut self) -> Option<(usize, usize)> {
248 loop {
249 match self.next() {
250 SearchStep::Match(a, b) => return Some((a, b)),
251 SearchStep::Done => return None,
252 _ => continue,
253 }
254 }
255 }
256
257 /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next]
258 /// and [`next_match()`][Searcher::next_match].
259 ///
260 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
261 /// of this and [`next_match`][Searcher::next_match] will overlap.
262 #[inline]
263 fn next_reject(&mut self) -> Option<(usize, usize)> {
264 loop {
265 match self.next() {
266 SearchStep::Reject(a, b) => return Some((a, b)),
267 SearchStep::Done => return None,
268 _ => continue,
269 }
270 }
271 }
272}
273
274/// A reverse searcher for a string pattern.
275///
276/// This trait provides methods for searching for non-overlapping
277/// matches of a pattern starting from the back (right) of a string.
278///
279/// It will be implemented by associated [`Searcher`]
280/// types of the [`Pattern`] trait if the pattern supports searching
281/// for it from the back.
282///
283/// The index ranges returned by this trait are not required
284/// to exactly match those of the forward search in reverse.
285///
286/// For the reason why this trait is marked unsafe, see the
287/// parent trait [`Searcher`].
288pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
289 /// Performs the next search step starting from the back.
290 ///
291 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]`
292 /// matches the pattern.
293 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]`
294 /// can not match the pattern, even partially.
295 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack
296 /// has been visited
297 ///
298 /// The stream of [`Match`][SearchStep::Match] and
299 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
300 /// will contain index ranges that are adjacent, non-overlapping,
301 /// covering the whole haystack, and laying on utf8 boundaries.
302 ///
303 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
304 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
305 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
306 ///
307 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
308 /// might produce the stream
309 /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`.
310 fn next_back(&mut self) -> SearchStep;
311
312 /// Finds the next [`Match`][SearchStep::Match] result.
313 /// See [`next_back()`][ReverseSearcher::next_back].
314 #[inline]
315 fn next_match_back(&mut self) -> Option<(usize, usize)> {
316 loop {
317 match self.next_back() {
318 SearchStep::Match(a, b) => return Some((a, b)),
319 SearchStep::Done => return None,
320 _ => continue,
321 }
322 }
323 }
324
325 /// Finds the next [`Reject`][SearchStep::Reject] result.
326 /// See [`next_back()`][ReverseSearcher::next_back].
327 #[inline]
328 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
329 loop {
330 match self.next_back() {
331 SearchStep::Reject(a, b) => return Some((a, b)),
332 SearchStep::Done => return None,
333 _ => continue,
334 }
335 }
336 }
337}
338
339/// A marker trait to express that a [`ReverseSearcher`]
340/// can be used for a [`DoubleEndedIterator`] implementation.
341///
342/// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need
343/// to follow these conditions:
344///
345/// - All results of `next()` need to be identical
346/// to the results of `next_back()` in reverse order.
347/// - `next()` and `next_back()` need to behave as
348/// the two ends of a range of values, that is they
349/// can not "walk past each other".
350///
351/// # Examples
352///
353/// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
354/// [`char`] only requires looking at one at a time, which behaves the same
355/// from both ends.
356///
357/// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
358/// the pattern `"aa"` in the haystack `"aaa"` matches as either
359/// `"[aa]a"` or `"a[aa]"`, depending on which side it is searched.
360pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
361
362/////////////////////////////////////////////////////////////////////////////
363// Impl for char
364/////////////////////////////////////////////////////////////////////////////
365
366/// Associated type for `<char as Pattern>::Searcher<'a>`.
367#[derive(Clone, Debug)]
368pub struct CharSearcher<'a> {
369 haystack: &'a str,
370 // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack`
371 // This invariant can be broken *within* next_match and next_match_back, however
372 // they must exit with fingers on valid code point boundaries.
373 /// `finger` is the current byte index of the forward search.
374 /// Imagine that it exists before the byte at its index, i.e.
375 /// `haystack[finger]` is the first byte of the slice we must inspect during
376 /// forward searching
377 finger: usize,
378 /// `finger_back` is the current byte index of the reverse search.
379 /// Imagine that it exists after the byte at its index, i.e.
380 /// haystack[finger_back - 1] is the last byte of the slice we must inspect during
381 /// forward searching (and thus the first byte to be inspected when calling next_back()).
382 finger_back: usize,
383 /// The character being searched for
384 needle: char,
385
386 // safety invariant: `utf8_size` must be less than 5
387 /// The number of bytes `needle` takes up when encoded in utf8.
388 utf8_size: u8,
389 /// A utf8 encoded copy of the `needle`
390 utf8_encoded: [u8; 4],
391}
392
393impl CharSearcher<'_> {
394 fn utf8_size(&self) -> usize {
395 self.utf8_size.into()
396 }
397}
398
399unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
400 #[inline]
401 fn haystack(&self) -> &'a str {
402 self.haystack
403 }
404 #[inline]
405 fn next(&mut self) -> SearchStep {
406 let old_finger = self.finger;
407 // SAFETY: 1-4 guarantee safety of `get_unchecked`
408 // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries
409 // (this is invariant)
410 // 2. `self.finger >= 0` since it starts at 0 and only increases
411 // 3. `self.finger < self.finger_back` because otherwise the char `iter`
412 // would return `SearchStep::Done`
413 // 4. `self.finger` comes before the end of the haystack because `self.finger_back`
414 // starts at the end and only decreases
415 let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
416 let mut iter = slice.chars();
417 let old_len = iter.iter.len();
418 if let Some(ch) = iter.next() {
419 // add byte offset of current character
420 // without re-encoding as utf-8
421 self.finger += old_len - iter.iter.len();
422 if ch == self.needle {
423 SearchStep::Match(old_finger, self.finger)
424 } else {
425 SearchStep::Reject(old_finger, self.finger)
426 }
427 } else {
428 SearchStep::Done
429 }
430 }
431 #[inline]
432 fn next_match(&mut self) -> Option<(usize, usize)> {
433 loop {
434 // get the haystack after the last character found
435 let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
436 // the last byte of the utf8 encoded needle
437 // SAFETY: we have an invariant that `utf8_size < 5`
438 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size() - 1) };
439 if let Some(index) = memchr::memchr(last_byte, bytes) {
440 // The new finger is the index of the byte we found,
441 // plus one, since we memchr'd for the last byte of the character.
442 //
443 // Note that this doesn't always give us a finger on a UTF8 boundary.
444 // If we *didn't* find our character
445 // we may have indexed to the non-last byte of a 3-byte or 4-byte character.
446 // We can't just skip to the next valid starting byte because a character like
447 // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find
448 // the second byte when searching for the third.
449 //
450 // However, this is totally okay. While we have the invariant that
451 // self.finger is on a UTF8 boundary, this invariant is not relied upon
452 // within this method (it is relied upon in CharSearcher::next()).
453 //
454 // We only exit this method when we reach the end of the string, or if we
455 // find something. When we find something the `finger` will be set
456 // to a UTF8 boundary.
457 self.finger += index + 1;
458 if self.finger >= self.utf8_size() {
459 let found_char = self.finger - self.utf8_size();
460 if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
461 if slice == &self.utf8_encoded[0..self.utf8_size()] {
462 return Some((found_char, self.finger));
463 }
464 }
465 }
466 } else {
467 // found nothing, exit
468 self.finger = self.finger_back;
469 return None;
470 }
471 }
472 }
473
474 // let next_reject use the default implementation from the Searcher trait
475}
476
477unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
478 #[inline]
479 fn next_back(&mut self) -> SearchStep {
480 let old_finger = self.finger_back;
481 // SAFETY: see the comment for next() above
482 let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
483 let mut iter = slice.chars();
484 let old_len = iter.iter.len();
485 if let Some(ch) = iter.next_back() {
486 // subtract byte offset of current character
487 // without re-encoding as utf-8
488 self.finger_back -= old_len - iter.iter.len();
489 if ch == self.needle {
490 SearchStep::Match(self.finger_back, old_finger)
491 } else {
492 SearchStep::Reject(self.finger_back, old_finger)
493 }
494 } else {
495 SearchStep::Done
496 }
497 }
498 #[inline]
499 fn next_match_back(&mut self) -> Option<(usize, usize)> {
500 let haystack = self.haystack.as_bytes();
501 loop {
502 // get the haystack up to but not including the last character searched
503 let bytes = haystack.get(self.finger..self.finger_back)?;
504 // the last byte of the utf8 encoded needle
505 // SAFETY: we have an invariant that `utf8_size < 5`
506 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size() - 1) };
507 if let Some(index) = memchr::memrchr(last_byte, bytes) {
508 // we searched a slice that was offset by self.finger,
509 // add self.finger to recoup the original index
510 let index = self.finger + index;
511 // memrchr will return the index of the byte we wish to
512 // find. In case of an ASCII character, this is indeed
513 // were we wish our new finger to be ("after" the found
514 // char in the paradigm of reverse iteration). For
515 // multibyte chars we need to skip down by the number of more
516 // bytes they have than ASCII
517 let shift = self.utf8_size() - 1;
518 if index >= shift {
519 let found_char = index - shift;
520 if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size())) {
521 if slice == &self.utf8_encoded[0..self.utf8_size()] {
522 // move finger to before the character found (i.e., at its start index)
523 self.finger_back = found_char;
524 return Some((self.finger_back, self.finger_back + self.utf8_size()));
525 }
526 }
527 }
528 // We can't use finger_back = index - size + 1 here. If we found the last char
529 // of a different-sized character (or the middle byte of a different character)
530 // we need to bump the finger_back down to `index`. This similarly makes
531 // `finger_back` have the potential to no longer be on a boundary,
532 // but this is OK since we only exit this function on a boundary
533 // or when the haystack has been searched completely.
534 //
535 // Unlike next_match this does not
536 // have the problem of repeated bytes in utf-8 because
537 // we're searching for the last byte, and we can only have
538 // found the last byte when searching in reverse.
539 self.finger_back = index;
540 } else {
541 self.finger_back = self.finger;
542 // found nothing, exit
543 return None;
544 }
545 }
546 }
547
548 // let next_reject_back use the default implementation from the Searcher trait
549}
550
551impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
552
553/// Searches for chars that are equal to a given [`char`].
554///
555/// # Examples
556///
557/// ```
558/// assert_eq!("Hello world".find('o'), Some(4));
559/// ```
560impl Pattern for char {
561 type Searcher<'a> = CharSearcher<'a>;
562
563 #[inline]
564 fn into_searcher(self, haystack: &str) -> Self::Searcher<'_> {
565 let mut utf8_encoded = [0; 4];
566 let utf8_size = self
567 .encode_utf8(&mut utf8_encoded)
568 .len()
569 .try_into()
570 .expect("char len should be less than 255");
571
572 CharSearcher {
573 haystack,
574 finger: 0,
575 finger_back: haystack.len(),
576 needle: self,
577 utf8_size,
578 utf8_encoded,
579 }
580 }
581
582 #[inline]
583 fn is_contained_in(self, haystack: &str) -> bool {
584 if (self as u32) < 128 {
585 haystack.as_bytes().contains(&(self as u8))
586 } else {
587 let mut buffer = [0u8; 4];
588 self.encode_utf8(&mut buffer).is_contained_in(haystack)
589 }
590 }
591
592 #[inline]
593 fn is_prefix_of(self, haystack: &str) -> bool {
594 self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
595 }
596
597 #[inline]
598 fn strip_prefix_of(self, haystack: &str) -> Option<&str> {
599 self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack)
600 }
601
602 #[inline]
603 fn is_suffix_of<'a>(self, haystack: &'a str) -> bool
604 where
605 Self::Searcher<'a>: ReverseSearcher<'a>,
606 {
607 self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
608 }
609
610 #[inline]
611 fn strip_suffix_of<'a>(self, haystack: &'a str) -> Option<&'a str>
612 where
613 Self::Searcher<'a>: ReverseSearcher<'a>,
614 {
615 self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack)
616 }
617
618 #[inline]
619 fn as_utf8_pattern(&self) -> Option<Utf8Pattern<'_>> {
620 Some(Utf8Pattern::CharPattern(*self))
621 }
622}
623
624/////////////////////////////////////////////////////////////////////////////
625// Impl for a MultiCharEq wrapper
626/////////////////////////////////////////////////////////////////////////////
627
628#[doc(hidden)]
629trait MultiCharEq {
630 fn matches(&mut self, c: char) -> bool;
631}
632
633impl<F> MultiCharEq for F
634where
635 F: FnMut(char) -> bool,
636{
637 #[inline]
638 fn matches(&mut self, c: char) -> bool {
639 (*self)(c)
640 }
641}
642
643impl<const N: usize> MultiCharEq for [char; N] {
644 #[inline]
645 fn matches(&mut self, c: char) -> bool {
646 self.iter().any(|&m| m == c)
647 }
648}
649
650impl<const N: usize> MultiCharEq for &[char; N] {
651 #[inline]
652 fn matches(&mut self, c: char) -> bool {
653 self.iter().any(|&m| m == c)
654 }
655}
656
657impl MultiCharEq for &[char] {
658 #[inline]
659 fn matches(&mut self, c: char) -> bool {
660 self.iter().any(|&m| m == c)
661 }
662}
663
664struct MultiCharEqPattern<C: MultiCharEq>(C);
665
666#[derive(Clone, Debug)]
667struct MultiCharEqSearcher<'a, C: MultiCharEq> {
668 char_eq: C,
669 haystack: &'a str,
670 char_indices: super::CharIndices<'a>,
671}
672
673impl<C: MultiCharEq> Pattern for MultiCharEqPattern<C> {
674 type Searcher<'a> = MultiCharEqSearcher<'a, C>;
675
676 #[inline]
677 fn into_searcher(self, haystack: &str) -> MultiCharEqSearcher<'_, C> {
678 MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
679 }
680}
681
682unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
683 #[inline]
684 fn haystack(&self) -> &'a str {
685 self.haystack
686 }
687
688 #[inline]
689 fn next(&mut self) -> SearchStep {
690 let s = &mut self.char_indices;
691 // Compare lengths of the internal byte slice iterator
692 // to find length of current char
693 let pre_len = s.iter.iter.len();
694 if let Some((i, c)) = s.next() {
695 let len = s.iter.iter.len();
696 let char_len = pre_len - len;
697 if self.char_eq.matches(c) {
698 return SearchStep::Match(i, i + char_len);
699 } else {
700 return SearchStep::Reject(i, i + char_len);
701 }
702 }
703 SearchStep::Done
704 }
705}
706
707unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
708 #[inline]
709 fn next_back(&mut self) -> SearchStep {
710 let s = &mut self.char_indices;
711 // Compare lengths of the internal byte slice iterator
712 // to find length of current char
713 let pre_len = s.iter.iter.len();
714 if let Some((i, c)) = s.next_back() {
715 let len = s.iter.iter.len();
716 let char_len = pre_len - len;
717 if self.char_eq.matches(c) {
718 return SearchStep::Match(i, i + char_len);
719 } else {
720 return SearchStep::Reject(i, i + char_len);
721 }
722 }
723 SearchStep::Done
724 }
725}
726
727impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}
728
729/////////////////////////////////////////////////////////////////////////////
730
731macro_rules! pattern_methods {
732 ($a:lifetime, $t:ty, $pmap:expr, $smap:expr) => {
733 type Searcher<$a> = $t;
734
735 #[inline]
736 fn into_searcher<$a>(self, haystack: &$a str) -> $t {
737 ($smap)(($pmap)(self).into_searcher(haystack))
738 }
739
740 #[inline]
741 fn is_contained_in<$a>(self, haystack: &$a str) -> bool {
742 ($pmap)(self).is_contained_in(haystack)
743 }
744
745 #[inline]
746 fn is_prefix_of<$a>(self, haystack: &$a str) -> bool {
747 ($pmap)(self).is_prefix_of(haystack)
748 }
749
750 #[inline]
751 fn strip_prefix_of<$a>(self, haystack: &$a str) -> Option<&$a str> {
752 ($pmap)(self).strip_prefix_of(haystack)
753 }
754
755 #[inline]
756 fn is_suffix_of<$a>(self, haystack: &$a str) -> bool
757 where
758 $t: ReverseSearcher<$a>,
759 {
760 ($pmap)(self).is_suffix_of(haystack)
761 }
762
763 #[inline]
764 fn strip_suffix_of<$a>(self, haystack: &$a str) -> Option<&$a str>
765 where
766 $t: ReverseSearcher<$a>,
767 {
768 ($pmap)(self).strip_suffix_of(haystack)
769 }
770 };
771}
772
773macro_rules! searcher_methods {
774 (forward) => {
775 #[inline]
776 fn haystack(&self) -> &'a str {
777 self.0.haystack()
778 }
779 #[inline]
780 fn next(&mut self) -> SearchStep {
781 self.0.next()
782 }
783 #[inline]
784 fn next_match(&mut self) -> Option<(usize, usize)> {
785 self.0.next_match()
786 }
787 #[inline]
788 fn next_reject(&mut self) -> Option<(usize, usize)> {
789 self.0.next_reject()
790 }
791 };
792 (reverse) => {
793 #[inline]
794 fn next_back(&mut self) -> SearchStep {
795 self.0.next_back()
796 }
797 #[inline]
798 fn next_match_back(&mut self) -> Option<(usize, usize)> {
799 self.0.next_match_back()
800 }
801 #[inline]
802 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
803 self.0.next_reject_back()
804 }
805 };
806}
807
808/// Associated type for `<[char; N] as Pattern>::Searcher<'a>`.
809#[derive(Clone, Debug)]
810pub struct CharArraySearcher<'a, const N: usize>(
811 <MultiCharEqPattern<[char; N]> as Pattern>::Searcher<'a>,
812);
813
814/// Associated type for `<&[char; N] as Pattern>::Searcher<'a>`.
815#[derive(Clone, Debug)]
816pub struct CharArrayRefSearcher<'a, 'b, const N: usize>(
817 <MultiCharEqPattern<&'b [char; N]> as Pattern>::Searcher<'a>,
818);
819
820/// Searches for chars that are equal to any of the [`char`]s in the array.
821///
822/// # Examples
823///
824/// ```
825/// assert_eq!("Hello world".find(['o', 'l']), Some(2));
826/// assert_eq!("Hello world".find(['h', 'w']), Some(6));
827/// ```
828impl<const N: usize> Pattern for [char; N] {
829 pattern_methods!('a, CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher);
830}
831
832unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> {
833 searcher_methods!(forward);
834}
835
836unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> {
837 searcher_methods!(reverse);
838}
839
840impl<'a, const N: usize> DoubleEndedSearcher<'a> for CharArraySearcher<'a, N> {}
841
842/// Searches for chars that are equal to any of the [`char`]s in the array.
843///
844/// # Examples
845///
846/// ```
847/// assert_eq!("Hello world".find(&['o', 'l']), Some(2));
848/// assert_eq!("Hello world".find(&['h', 'w']), Some(6));
849/// ```
850impl<'b, const N: usize> Pattern for &'b [char; N] {
851 pattern_methods!('a, CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher);
852}
853
854unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
855 searcher_methods!(forward);
856}
857
858unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
859 searcher_methods!(reverse);
860}
861
862impl<'a, 'b, const N: usize> DoubleEndedSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {}
863
864/////////////////////////////////////////////////////////////////////////////
865// Impl for &[char]
866/////////////////////////////////////////////////////////////////////////////
867
868// Todo: Change / Remove due to ambiguity in meaning.
869
870/// Associated type for `<&[char] as Pattern>::Searcher<'a>`.
871#[derive(Clone, Debug)]
872pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern>::Searcher<'a>);
873
874unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
875 searcher_methods!(forward);
876}
877
878unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
879 searcher_methods!(reverse);
880}
881
882impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}
883
884/// Searches for chars that are equal to any of the [`char`]s in the slice.
885///
886/// # Examples
887///
888/// ```
889/// assert_eq!("Hello world".find(&['o', 'l'][..]), Some(2));
890/// assert_eq!("Hello world".find(&['h', 'w'][..]), Some(6));
891/// ```
892impl<'b> Pattern for &'b [char] {
893 pattern_methods!('a, CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
894}
895
896/////////////////////////////////////////////////////////////////////////////
897// Impl for F: FnMut(char) -> bool
898/////////////////////////////////////////////////////////////////////////////
899
900/// Associated type for `<F as Pattern>::Searcher<'a>`.
901#[derive(Clone)]
902pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern>::Searcher<'a>)
903where
904 F: FnMut(char) -> bool;
905
906impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
907where
908 F: FnMut(char) -> bool,
909{
910 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
911 f.debug_struct("CharPredicateSearcher")
912 .field("haystack", &self.0.haystack)
913 .field("char_indices", &self.0.char_indices)
914 .finish()
915 }
916}
917unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
918where
919 F: FnMut(char) -> bool,
920{
921 searcher_methods!(forward);
922}
923
924unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
925where
926 F: FnMut(char) -> bool,
927{
928 searcher_methods!(reverse);
929}
930
931impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}
932
933/// Searches for [`char`]s that match the given predicate.
934///
935/// # Examples
936///
937/// ```
938/// assert_eq!("Hello world".find(char::is_uppercase), Some(0));
939/// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1));
940/// ```
941impl<F> Pattern for F
942where
943 F: FnMut(char) -> bool,
944{
945 pattern_methods!('a, CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
946}
947
948/////////////////////////////////////////////////////////////////////////////
949// Impl for &&str
950/////////////////////////////////////////////////////////////////////////////
951
952/// Delegates to the `&str` impl.
953impl<'b, 'c> Pattern for &'c &'b str {
954 pattern_methods!('a, StrSearcher<'a, 'b>, |&s| s, |s| s);
955}
956
957/////////////////////////////////////////////////////////////////////////////
958// Impl for &str
959/////////////////////////////////////////////////////////////////////////////
960
961/// Non-allocating substring search.
962///
963/// Will handle the pattern `""` as returning empty matches at each character
964/// boundary.
965///
966/// # Examples
967///
968/// ```
969/// assert_eq!("Hello world".find("world"), Some(6));
970/// ```
971impl<'b> Pattern for &'b str {
972 type Searcher<'a> = StrSearcher<'a, 'b>;
973
974 #[inline]
975 fn into_searcher(self, haystack: &str) -> StrSearcher<'_, 'b> {
976 StrSearcher::new(haystack, self)
977 }
978
979 /// Checks whether the pattern matches at the front of the haystack.
980 #[inline]
981 fn is_prefix_of(self, haystack: &str) -> bool {
982 haystack.as_bytes().starts_with(self.as_bytes())
983 }
984
985 /// Checks whether the pattern matches anywhere in the haystack
986 #[inline]
987 fn is_contained_in(self, haystack: &str) -> bool {
988 if self.len() == 0 {
989 return true;
990 }
991
992 match self.len().cmp(&haystack.len()) {
993 Ordering::Less => {
994 if self.len() == 1 {
995 return haystack.as_bytes().contains(&self.as_bytes()[0]);
996 }
997
998 #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
999 if self.len() <= 32 {
1000 if let Some(result) = simd_contains(self, haystack) {
1001 return result;
1002 }
1003 }
1004
1005 self.into_searcher(haystack).next_match().is_some()
1006 }
1007 _ => self == haystack,
1008 }
1009 }
1010
1011 /// Removes the pattern from the front of haystack, if it matches.
1012 #[inline]
1013 fn strip_prefix_of(self, haystack: &str) -> Option<&str> {
1014 if self.is_prefix_of(haystack) {
1015 // SAFETY: prefix was just verified to exist.
1016 unsafe { Some(haystack.get_unchecked(self.as_bytes().len()..)) }
1017 } else {
1018 None
1019 }
1020 }
1021
1022 /// Checks whether the pattern matches at the back of the haystack.
1023 #[inline]
1024 fn is_suffix_of<'a>(self, haystack: &'a str) -> bool
1025 where
1026 Self::Searcher<'a>: ReverseSearcher<'a>,
1027 {
1028 haystack.as_bytes().ends_with(self.as_bytes())
1029 }
1030
1031 /// Removes the pattern from the back of haystack, if it matches.
1032 #[inline]
1033 fn strip_suffix_of<'a>(self, haystack: &'a str) -> Option<&'a str>
1034 where
1035 Self::Searcher<'a>: ReverseSearcher<'a>,
1036 {
1037 if self.is_suffix_of(haystack) {
1038 let i = haystack.len() - self.as_bytes().len();
1039 // SAFETY: suffix was just verified to exist.
1040 unsafe { Some(haystack.get_unchecked(..i)) }
1041 } else {
1042 None
1043 }
1044 }
1045
1046 #[inline]
1047 fn as_utf8_pattern(&self) -> Option<Utf8Pattern<'_>> {
1048 Some(Utf8Pattern::StringPattern(self.as_bytes()))
1049 }
1050}
1051
1052/////////////////////////////////////////////////////////////////////////////
1053// Two Way substring searcher
1054/////////////////////////////////////////////////////////////////////////////
1055
1056#[derive(Clone, Debug)]
1057/// Associated type for `<&str as Pattern>::Searcher<'a>`.
1058pub struct StrSearcher<'a, 'b> {
1059 haystack: &'a str,
1060 needle: &'b str,
1061
1062 searcher: StrSearcherImpl,
1063}
1064
1065#[derive(Clone, Debug)]
1066enum StrSearcherImpl {
1067 Empty(EmptyNeedle),
1068 TwoWay(TwoWaySearcher),
1069}
1070
1071#[derive(Clone, Debug)]
1072struct EmptyNeedle {
1073 position: usize,
1074 end: usize,
1075 is_match_fw: bool,
1076 is_match_bw: bool,
1077 // Needed in case of an empty haystack, see #85462
1078 is_finished: bool,
1079}
1080
1081impl<'a, 'b> StrSearcher<'a, 'b> {
1082 fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
1083 if needle.is_empty() {
1084 StrSearcher {
1085 haystack,
1086 needle,
1087 searcher: StrSearcherImpl::Empty(EmptyNeedle {
1088 position: 0,
1089 end: haystack.len(),
1090 is_match_fw: true,
1091 is_match_bw: true,
1092 is_finished: false,
1093 }),
1094 }
1095 } else {
1096 StrSearcher {
1097 haystack,
1098 needle,
1099 searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
1100 needle.as_bytes(),
1101 haystack.len(),
1102 )),
1103 }
1104 }
1105 }
1106}
1107
1108unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
1109 #[inline]
1110 fn haystack(&self) -> &'a str {
1111 self.haystack
1112 }
1113
1114 #[inline]
1115 fn next(&mut self) -> SearchStep {
1116 match self.searcher {
1117 StrSearcherImpl::Empty(ref mut searcher) => {
1118 if searcher.is_finished {
1119 return SearchStep::Done;
1120 }
1121 // empty needle rejects every char and matches every empty string between them
1122 let is_match = searcher.is_match_fw;
1123 searcher.is_match_fw = !searcher.is_match_fw;
1124 let pos = searcher.position;
1125 match self.haystack[pos..].chars().next() {
1126 _ if is_match => SearchStep::Match(pos, pos),
1127 None => {
1128 searcher.is_finished = true;
1129 SearchStep::Done
1130 }
1131 Some(ch) => {
1132 searcher.position += ch.len_utf8();
1133 SearchStep::Reject(pos, searcher.position)
1134 }
1135 }
1136 }
1137 StrSearcherImpl::TwoWay(ref mut searcher) => {
1138 // TwoWaySearcher produces valid *Match* indices that split at char boundaries
1139 // as long as it does correct matching and that haystack and needle are
1140 // valid UTF-8
1141 // *Rejects* from the algorithm can fall on any indices, but we will walk them
1142 // manually to the next character boundary, so that they are utf-8 safe.
1143 if searcher.position == self.haystack.len() {
1144 return SearchStep::Done;
1145 }
1146 let is_long = searcher.memory == usize::MAX;
1147 match searcher.next::<RejectAndMatch>(
1148 self.haystack.as_bytes(),
1149 self.needle.as_bytes(),
1150 is_long,
1151 ) {
1152 SearchStep::Reject(a, mut b) => {
1153 // skip to next char boundary
1154 while !self.haystack.is_char_boundary(b) {
1155 b += 1;
1156 }
1157 searcher.position = cmp::max(b, searcher.position);
1158 SearchStep::Reject(a, b)
1159 }
1160 otherwise => otherwise,
1161 }
1162 }
1163 }
1164 }
1165
1166 #[inline]
1167 fn next_match(&mut self) -> Option<(usize, usize)> {
1168 match self.searcher {
1169 StrSearcherImpl::Empty(..) => loop {
1170 match self.next() {
1171 SearchStep::Match(a, b) => return Some((a, b)),
1172 SearchStep::Done => return None,
1173 SearchStep::Reject(..) => {}
1174 }
1175 },
1176 StrSearcherImpl::TwoWay(ref mut searcher) => {
1177 let is_long = searcher.memory == usize::MAX;
1178 // write out `true` and `false` cases to encourage the compiler
1179 // to specialize the two cases separately.
1180 if is_long {
1181 searcher.next::<MatchOnly>(
1182 self.haystack.as_bytes(),
1183 self.needle.as_bytes(),
1184 true,
1185 )
1186 } else {
1187 searcher.next::<MatchOnly>(
1188 self.haystack.as_bytes(),
1189 self.needle.as_bytes(),
1190 false,
1191 )
1192 }
1193 }
1194 }
1195 }
1196}
1197
1198unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
1199 #[inline]
1200 fn next_back(&mut self) -> SearchStep {
1201 match self.searcher {
1202 StrSearcherImpl::Empty(ref mut searcher) => {
1203 if searcher.is_finished {
1204 return SearchStep::Done;
1205 }
1206 let is_match = searcher.is_match_bw;
1207 searcher.is_match_bw = !searcher.is_match_bw;
1208 let end = searcher.end;
1209 match self.haystack[..end].chars().next_back() {
1210 _ if is_match => SearchStep::Match(end, end),
1211 None => {
1212 searcher.is_finished = true;
1213 SearchStep::Done
1214 }
1215 Some(ch) => {
1216 searcher.end -= ch.len_utf8();
1217 SearchStep::Reject(searcher.end, end)
1218 }
1219 }
1220 }
1221 StrSearcherImpl::TwoWay(ref mut searcher) => {
1222 if searcher.end == 0 {
1223 return SearchStep::Done;
1224 }
1225 let is_long = searcher.memory == usize::MAX;
1226 match searcher.next_back::<RejectAndMatch>(
1227 self.haystack.as_bytes(),
1228 self.needle.as_bytes(),
1229 is_long,
1230 ) {
1231 SearchStep::Reject(mut a, b) => {
1232 // skip to next char boundary
1233 while !self.haystack.is_char_boundary(a) {
1234 a -= 1;
1235 }
1236 searcher.end = cmp::min(a, searcher.end);
1237 SearchStep::Reject(a, b)
1238 }
1239 otherwise => otherwise,
1240 }
1241 }
1242 }
1243 }
1244
1245 #[inline]
1246 fn next_match_back(&mut self) -> Option<(usize, usize)> {
1247 match self.searcher {
1248 StrSearcherImpl::Empty(..) => loop {
1249 match self.next_back() {
1250 SearchStep::Match(a, b) => return Some((a, b)),
1251 SearchStep::Done => return None,
1252 SearchStep::Reject(..) => {}
1253 }
1254 },
1255 StrSearcherImpl::TwoWay(ref mut searcher) => {
1256 let is_long = searcher.memory == usize::MAX;
1257 // write out `true` and `false`, like `next_match`
1258 if is_long {
1259 searcher.next_back::<MatchOnly>(
1260 self.haystack.as_bytes(),
1261 self.needle.as_bytes(),
1262 true,
1263 )
1264 } else {
1265 searcher.next_back::<MatchOnly>(
1266 self.haystack.as_bytes(),
1267 self.needle.as_bytes(),
1268 false,
1269 )
1270 }
1271 }
1272 }
1273 }
1274}
1275
1276/// The internal state of the two-way substring search algorithm.
1277#[derive(Clone, Debug)]
1278struct TwoWaySearcher {
1279 // constants
1280 /// critical factorization index
1281 crit_pos: usize,
1282 /// critical factorization index for reversed needle
1283 crit_pos_back: usize,
1284 period: usize,
1285 /// `byteset` is an extension (not part of the two way algorithm);
1286 /// it's a 64-bit "fingerprint" where each set bit `j` corresponds
1287 /// to a (byte & 63) == j present in the needle.
1288 byteset: u64,
1289
1290 // variables
1291 position: usize,
1292 end: usize,
1293 /// index into needle before which we have already matched
1294 memory: usize,
1295 /// index into needle after which we have already matched
1296 memory_back: usize,
1297}
1298
1299/*
1300 This is the Two-Way search algorithm, which was introduced in the paper:
1301 Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.
1302
1303 Here's some background information.
1304
1305 A *word* is a string of symbols. The *length* of a word should be a familiar
1306 notion, and here we denote it for any word x by |x|.
1307 (We also allow for the possibility of the *empty word*, a word of length zero).
1308
1309 If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
1310 *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
1311 For example, both 1 and 2 are periods for the string "aa". As another example,
1312 the only period of the string "abcd" is 4.
1313
1314 We denote by period(x) the *smallest* period of x (provided that x is non-empty).
1315 This is always well-defined since every non-empty word x has at least one period,
1316 |x|. We sometimes call this *the period* of x.
1317
1318 If u, v and x are words such that x = uv, where uv is the concatenation of u and
1319 v, then we say that (u, v) is a *factorization* of x.
1320
1321 Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
1322 that both of the following hold
1323
1324 - either w is a suffix of u or u is a suffix of w
1325 - either w is a prefix of v or v is a prefix of w
1326
1327 then w is said to be a *repetition* for the factorization (u, v).
1328
1329 Just to unpack this, there are four possibilities here. Let w = "abc". Then we
1330 might have:
1331
1332 - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
1333 - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
1334 - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
1335 - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")
1336
1337 Note that the word vu is a repetition for any factorization (u,v) of x = uv,
1338 so every factorization has at least one repetition.
1339
1340 If x is a string and (u, v) is a factorization for x, then a *local period* for
1341 (u, v) is an integer r such that there is some word w such that |w| = r and w is
1342 a repetition for (u, v).
1343
1344 We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
1345 call this *the local period* of (u, v). Provided that x = uv is non-empty, this
1346 is well-defined (because each non-empty word has at least one factorization, as
1347 noted above).
1348
1349 It can be proven that the following is an equivalent definition of a local period
1350 for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
1351 all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
1352 defined. (i.e., i > 0 and i + r < |x|).
1353
1354 Using the above reformulation, it is easy to prove that
1355
1356 1 <= local_period(u, v) <= period(uv)
1357
1358 A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
1359 *critical factorization*.
1360
1361 The algorithm hinges on the following theorem, which is stated without proof:
1362
1363 **Critical Factorization Theorem** Any word x has at least one critical
1364 factorization (u, v) such that |u| < period(x).
1365
1366 The purpose of maximal_suffix is to find such a critical factorization.
1367
1368 If the period is short, compute another factorization x = u' v' to use
1369 for reverse search, chosen instead so that |v'| < period(x).
1370
1371*/
1372impl TwoWaySearcher {
1373 fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
1374 let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
1375 let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);
1376
1377 let (crit_pos, period) = if crit_pos_false > crit_pos_true {
1378 (crit_pos_false, period_false)
1379 } else {
1380 (crit_pos_true, period_true)
1381 };
1382
1383 // A particularly readable explanation of what's going on here can be found
1384 // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically
1385 // see the code for "Algorithm CP" on p. 323.
1386 //
1387 // What's going on is we have some critical factorization (u, v) of the
1388 // needle, and we want to determine whether u is a suffix of
1389 // &v[..period]. If it is, we use "Algorithm CP1". Otherwise we use
1390 // "Algorithm CP2", which is optimized for when the period of the needle
1391 // is large.
1392 if needle[..crit_pos] == needle[period..period + crit_pos] {
1393 // short period case -- the period is exact
1394 // compute a separate critical factorization for the reversed needle
1395 // x = u' v' where |v'| < period(x).
1396 //
1397 // This is sped up by the period being known already.
1398 // Note that a case like x = "acba" may be factored exactly forwards
1399 // (crit_pos = 1, period = 3) while being factored with approximate
1400 // period in reverse (crit_pos = 2, period = 2). We use the given
1401 // reverse factorization but keep the exact period.
1402 let crit_pos_back = needle.len()
1403 - cmp::max(
1404 TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
1405 TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
1406 );
1407
1408 TwoWaySearcher {
1409 crit_pos,
1410 crit_pos_back,
1411 period,
1412 byteset: Self::byteset_create(&needle[..period]),
1413
1414 position: 0,
1415 end,
1416 memory: 0,
1417 memory_back: needle.len(),
1418 }
1419 } else {
1420 // long period case -- we have an approximation to the actual period,
1421 // and don't use memorization.
1422 //
1423 // Approximate the period by lower bound max(|u|, |v|) + 1.
1424 // The critical factorization is efficient to use for both forward and
1425 // reverse search.
1426
1427 TwoWaySearcher {
1428 crit_pos,
1429 crit_pos_back: crit_pos,
1430 period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
1431 byteset: Self::byteset_create(needle),
1432
1433 position: 0,
1434 end,
1435 memory: usize::MAX, // Dummy value to signify that the period is long
1436 memory_back: usize::MAX,
1437 }
1438 }
1439 }
1440
1441 #[inline]
1442 fn byteset_create(bytes: &[u8]) -> u64 {
1443 bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
1444 }
1445
1446 #[inline]
1447 fn byteset_contains(&self, byte: u8) -> bool {
1448 (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
1449 }
1450
1451 // One of the main ideas of Two-Way is that we factorize the needle into
1452 // two halves, (u, v), and begin trying to find v in the haystack by scanning
1453 // left to right. If v matches, we try to match u by scanning right to left.
1454 // How far we can jump when we encounter a mismatch is all based on the fact
1455 // that (u, v) is a critical factorization for the needle.
1456 #[inline]
1457 fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1458 where
1459 S: TwoWayStrategy,
1460 {
1461 // `next()` uses `self.position` as its cursor
1462 let old_pos = self.position;
1463 let needle_last = needle.len() - 1;
1464 'search: loop {
1465 // Check that we have room to search in
1466 // position + needle_last can not overflow if we assume slices
1467 // are bounded by isize's range.
1468 let tail_byte = match haystack.get(self.position + needle_last) {
1469 Some(&b) => b,
1470 None => {
1471 self.position = haystack.len();
1472 return S::rejecting(old_pos, self.position);
1473 }
1474 };
1475
1476 if S::use_early_reject() && old_pos != self.position {
1477 return S::rejecting(old_pos, self.position);
1478 }
1479
1480 // Quickly skip by large portions unrelated to our substring
1481 if !self.byteset_contains(tail_byte) {
1482 self.position += needle.len();
1483 if !long_period {
1484 self.memory = 0;
1485 }
1486 continue 'search;
1487 }
1488
1489 // See if the right part of the needle matches
1490 let start =
1491 if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) };
1492 for i in start..needle.len() {
1493 if needle[i] != haystack[self.position + i] {
1494 self.position += i - self.crit_pos + 1;
1495 if !long_period {
1496 self.memory = 0;
1497 }
1498 continue 'search;
1499 }
1500 }
1501
1502 // See if the left part of the needle matches
1503 let start = if long_period { 0 } else { self.memory };
1504 for i in (start..self.crit_pos).rev() {
1505 if needle[i] != haystack[self.position + i] {
1506 self.position += self.period;
1507 if !long_period {
1508 self.memory = needle.len() - self.period;
1509 }
1510 continue 'search;
1511 }
1512 }
1513
1514 // We have found a match!
1515 let match_pos = self.position;
1516
1517 // Note: add self.period instead of needle.len() to have overlapping matches
1518 self.position += needle.len();
1519 if !long_period {
1520 self.memory = 0; // set to needle.len() - self.period for overlapping matches
1521 }
1522
1523 return S::matching(match_pos, match_pos + needle.len());
1524 }
1525 }
1526
1527 // Follows the ideas in `next()`.
1528 //
1529 // The definitions are symmetrical, with period(x) = period(reverse(x))
1530 // and local_period(u, v) = local_period(reverse(v), reverse(u)), so if (u, v)
1531 // is a critical factorization, so is (reverse(v), reverse(u)).
1532 //
1533 // For the reverse case we have computed a critical factorization x = u' v'
1534 // (field `crit_pos_back`). We need |u| < period(x) for the forward case and
1535 // thus |v'| < period(x) for the reverse.
1536 //
1537 // To search in reverse through the haystack, we search forward through
1538 // a reversed haystack with a reversed needle, matching first u' and then v'.
1539 #[inline]
1540 fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
1541 where
1542 S: TwoWayStrategy,
1543 {
1544 // `next_back()` uses `self.end` as its cursor -- so that `next()` and `next_back()`
1545 // are independent.
1546 let old_end = self.end;
1547 'search: loop {
1548 // Check that we have room to search in
1549 // end - needle.len() will wrap around when there is no more room,
1550 // but due to slice length limits it can never wrap all the way back
1551 // into the length of haystack.
1552 let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
1553 Some(&b) => b,
1554 None => {
1555 self.end = 0;
1556 return S::rejecting(0, old_end);
1557 }
1558 };
1559
1560 if S::use_early_reject() && old_end != self.end {
1561 return S::rejecting(self.end, old_end);
1562 }
1563
1564 // Quickly skip by large portions unrelated to our substring
1565 if !self.byteset_contains(front_byte) {
1566 self.end -= needle.len();
1567 if !long_period {
1568 self.memory_back = needle.len();
1569 }
1570 continue 'search;
1571 }
1572
1573 // See if the left part of the needle matches
1574 let crit = if long_period {
1575 self.crit_pos_back
1576 } else {
1577 cmp::min(self.crit_pos_back, self.memory_back)
1578 };
1579 for i in (0..crit).rev() {
1580 if needle[i] != haystack[self.end - needle.len() + i] {
1581 self.end -= self.crit_pos_back - i;
1582 if !long_period {
1583 self.memory_back = needle.len();
1584 }
1585 continue 'search;
1586 }
1587 }
1588
1589 // See if the right part of the needle matches
1590 let needle_end = if long_period { needle.len() } else { self.memory_back };
1591 for i in self.crit_pos_back..needle_end {
1592 if needle[i] != haystack[self.end - needle.len() + i] {
1593 self.end -= self.period;
1594 if !long_period {
1595 self.memory_back = self.period;
1596 }
1597 continue 'search;
1598 }
1599 }
1600
1601 // We have found a match!
1602 let match_pos = self.end - needle.len();
1603 // Note: sub self.period instead of needle.len() to have overlapping matches
1604 self.end -= needle.len();
1605 if !long_period {
1606 self.memory_back = needle.len();
1607 }
1608
1609 return S::matching(match_pos, match_pos + needle.len());
1610 }
1611 }
1612
1613 // Compute the maximal suffix of `arr`.
1614 //
1615 // The maximal suffix is a possible critical factorization (u, v) of `arr`.
1616 //
1617 // Returns (`i`, `p`) where `i` is the starting index of v and `p` is the
1618 // period of v.
1619 //
1620 // `order_greater` determines if lexical order is `<` or `>`. Both
1621 // orders must be computed -- the ordering with the largest `i` gives
1622 // a critical factorization.
1623 //
1624 // For long period cases, the resulting period is not exact (it is too short).
1625 #[inline]
1626 fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
1627 let mut left = 0; // Corresponds to i in the paper
1628 let mut right = 1; // Corresponds to j in the paper
1629 let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1630 // to match 0-based indexing.
1631 let mut period = 1; // Corresponds to p in the paper
1632
1633 while let Some(&a) = arr.get(right + offset) {
1634 // `left` will be inbounds when `right` is.
1635 let b = arr[left + offset];
1636 if (a < b && !order_greater) || (a > b && order_greater) {
1637 // Suffix is smaller, period is entire prefix so far.
1638 right += offset + 1;
1639 offset = 0;
1640 period = right - left;
1641 } else if a == b {
1642 // Advance through repetition of the current period.
1643 if offset + 1 == period {
1644 right += offset + 1;
1645 offset = 0;
1646 } else {
1647 offset += 1;
1648 }
1649 } else {
1650 // Suffix is larger, start over from current location.
1651 left = right;
1652 right += 1;
1653 offset = 0;
1654 period = 1;
1655 }
1656 }
1657 (left, period)
1658 }
1659
1660 // Compute the maximal suffix of the reverse of `arr`.
1661 //
1662 // The maximal suffix is a possible critical factorization (u', v') of `arr`.
1663 //
1664 // Returns `i` where `i` is the starting index of v', from the back;
1665 // returns immediately when a period of `known_period` is reached.
1666 //
1667 // `order_greater` determines if lexical order is `<` or `>`. Both
1668 // orders must be computed -- the ordering with the largest `i` gives
1669 // a critical factorization.
1670 //
1671 // For long period cases, the resulting period is not exact (it is too short).
1672 fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize {
1673 let mut left = 0; // Corresponds to i in the paper
1674 let mut right = 1; // Corresponds to j in the paper
1675 let mut offset = 0; // Corresponds to k in the paper, but starting at 0
1676 // to match 0-based indexing.
1677 let mut period = 1; // Corresponds to p in the paper
1678 let n = arr.len();
1679
1680 while right + offset < n {
1681 let a = arr[n - (1 + right + offset)];
1682 let b = arr[n - (1 + left + offset)];
1683 if (a < b && !order_greater) || (a > b && order_greater) {
1684 // Suffix is smaller, period is entire prefix so far.
1685 right += offset + 1;
1686 offset = 0;
1687 period = right - left;
1688 } else if a == b {
1689 // Advance through repetition of the current period.
1690 if offset + 1 == period {
1691 right += offset + 1;
1692 offset = 0;
1693 } else {
1694 offset += 1;
1695 }
1696 } else {
1697 // Suffix is larger, start over from current location.
1698 left = right;
1699 right += 1;
1700 offset = 0;
1701 period = 1;
1702 }
1703 if period == known_period {
1704 break;
1705 }
1706 }
1707 debug_assert!(period <= known_period);
1708 left
1709 }
1710}
1711
1712// TwoWayStrategy allows the algorithm to either skip non-matches as quickly
1713// as possible, or to work in a mode where it emits Rejects relatively quickly.
1714trait TwoWayStrategy {
1715 type Output;
1716 fn use_early_reject() -> bool;
1717 fn rejecting(a: usize, b: usize) -> Self::Output;
1718 fn matching(a: usize, b: usize) -> Self::Output;
1719}
1720
1721/// Skip to match intervals as quickly as possible
1722enum MatchOnly {}
1723
1724impl TwoWayStrategy for MatchOnly {
1725 type Output = Option<(usize, usize)>;
1726
1727 #[inline]
1728 fn use_early_reject() -> bool {
1729 false
1730 }
1731 #[inline]
1732 fn rejecting(_a: usize, _b: usize) -> Self::Output {
1733 None
1734 }
1735 #[inline]
1736 fn matching(a: usize, b: usize) -> Self::Output {
1737 Some((a, b))
1738 }
1739}
1740
1741/// Emit Rejects regularly
1742enum RejectAndMatch {}
1743
1744impl TwoWayStrategy for RejectAndMatch {
1745 type Output = SearchStep;
1746
1747 #[inline]
1748 fn use_early_reject() -> bool {
1749 true
1750 }
1751 #[inline]
1752 fn rejecting(a: usize, b: usize) -> Self::Output {
1753 SearchStep::Reject(a, b)
1754 }
1755 #[inline]
1756 fn matching(a: usize, b: usize) -> Self::Output {
1757 SearchStep::Match(a, b)
1758 }
1759}
1760
1761/// SIMD search for short needles based on
1762/// Wojciech Muła's "SIMD-friendly algorithms for substring searching"[0]
1763///
1764/// It skips ahead by the vector width on each iteration (rather than the needle length as two-way
1765/// does) by probing the first and last byte of the needle for the whole vector width
1766/// and only doing full needle comparisons when the vectorized probe indicated potential matches.
1767///
1768/// Since the x86_64 baseline only offers SSE2 we only use u8x16 here.
1769/// If we ever ship std with for x86-64-v3 or adapt this for other platforms then wider vectors
1770/// should be evaluated.
1771///
1772/// For haystacks smaller than vector-size + needle length it falls back to
1773/// a naive O(n*m) search so this implementation should not be called on larger needles.
1774///
1775/// [0]: http://0x80.pl/articles/simd-strfind.html#sse-avx2
1776#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
1777#[inline]
1778fn simd_contains(needle: &str, haystack: &str) -> Option<bool> {
1779 let needle = needle.as_bytes();
1780 let haystack = haystack.as_bytes();
1781
1782 debug_assert!(needle.len() > 1);
1783
1784 use crate::ops::BitAnd;
1785 use crate::simd::cmp::SimdPartialEq;
1786 use crate::simd::{mask8x16 as Mask, u8x16 as Block};
1787
1788 let first_probe = needle[0];
1789 let last_byte_offset = needle.len() - 1;
1790
1791 // the offset used for the 2nd vector
1792 let second_probe_offset = if needle.len() == 2 {
1793 // never bail out on len=2 needles because the probes will fully cover them and have
1794 // no degenerate cases.
1795 1
1796 } else {
1797 // try a few bytes in case first and last byte of the needle are the same
1798 let Some(second_probe_offset) =
1799 (needle.len().saturating_sub(4)..needle.len()).rfind(|&idx| needle[idx] != first_probe)
1800 else {
1801 // fall back to other search methods if we can't find any different bytes
1802 // since we could otherwise hit some degenerate cases
1803 return None;
1804 };
1805 second_probe_offset
1806 };
1807
1808 // do a naive search if the haystack is too small to fit
1809 if haystack.len() < Block::LEN + last_byte_offset {
1810 return Some(haystack.windows(needle.len()).any(|c| c == needle));
1811 }
1812
1813 let first_probe: Block = Block::splat(first_probe);
1814 let second_probe: Block = Block::splat(needle[second_probe_offset]);
1815 // first byte are already checked by the outer loop. to verify a match only the
1816 // remainder has to be compared.
1817 let trimmed_needle = &needle[1..];
1818
1819 // this #[cold] is load-bearing, benchmark before removing it...
1820 let check_mask = #[cold]
1821 |idx, mask: u16, skip: bool| -> bool {
1822 if skip {
1823 return false;
1824 }
1825
1826 // and so is this. optimizations are weird.
1827 let mut mask = mask;
1828
1829 while mask != 0 {
1830 let trailing = mask.trailing_zeros();
1831 let offset = idx + trailing as usize + 1;
1832 // SAFETY: mask is between 0 and 15 trailing zeroes, we skip one additional byte that was already compared
1833 // and then take trimmed_needle.len() bytes. This is within the bounds defined by the outer loop
1834 unsafe {
1835 let sub = haystack.get_unchecked(offset..).get_unchecked(..trimmed_needle.len());
1836 if small_slice_eq(sub, trimmed_needle) {
1837 return true;
1838 }
1839 }
1840 mask &= !(1 << trailing);
1841 }
1842 false
1843 };
1844
1845 let test_chunk = |idx| -> u16 {
1846 // SAFETY: this requires at least LANES bytes being readable at idx
1847 // that is ensured by the loop ranges (see comments below)
1848 let a: Block = unsafe { haystack.as_ptr().add(idx).cast::<Block>().read_unaligned() };
1849 // SAFETY: this requires LANES + block_offset bytes being readable at idx
1850 let b: Block = unsafe {
1851 haystack.as_ptr().add(idx).add(second_probe_offset).cast::<Block>().read_unaligned()
1852 };
1853 let eq_first: Mask = a.simd_eq(first_probe);
1854 let eq_last: Mask = b.simd_eq(second_probe);
1855 let both = eq_first.bitand(eq_last);
1856 let mask = both.to_bitmask() as u16;
1857
1858 mask
1859 };
1860
1861 let mut i = 0;
1862 let mut result = false;
1863 // The loop condition must ensure that there's enough headroom to read LANE bytes,
1864 // and not only at the current index but also at the index shifted by block_offset
1865 const UNROLL: usize = 4;
1866 while i + last_byte_offset + UNROLL * Block::LEN < haystack.len() && !result {
1867 let mut masks = [0u16; UNROLL];
1868 for j in 0..UNROLL {
1869 masks[j] = test_chunk(i + j * Block::LEN);
1870 }
1871 for j in 0..UNROLL {
1872 let mask = masks[j];
1873 if mask != 0 {
1874 result |= check_mask(i + j * Block::LEN, mask, result);
1875 }
1876 }
1877 i += UNROLL * Block::LEN;
1878 }
1879 while i + last_byte_offset + Block::LEN < haystack.len() && !result {
1880 let mask = test_chunk(i);
1881 if mask != 0 {
1882 result |= check_mask(i, mask, result);
1883 }
1884 i += Block::LEN;
1885 }
1886
1887 // Process the tail that didn't fit into LANES-sized steps.
1888 // This simply repeats the same procedure but as right-aligned chunk instead
1889 // of a left-aligned one. The last byte must be exactly flush with the string end so
1890 // we don't miss a single byte or read out of bounds.
1891 let i = haystack.len() - last_byte_offset - Block::LEN;
1892 let mask = test_chunk(i);
1893 if mask != 0 {
1894 result |= check_mask(i, mask, result);
1895 }
1896
1897 Some(result)
1898}
1899
1900/// Compares short slices for equality.
1901///
1902/// It avoids a call to libc's memcmp which is faster on long slices
1903/// due to SIMD optimizations but it incurs a function call overhead.
1904///
1905/// # Safety
1906///
1907/// Both slices must have the same length.
1908#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] // only called on x86
1909#[inline]
1910unsafe fn small_slice_eq(x: &[u8], y: &[u8]) -> bool {
1911 debug_assert_eq!(x.len(), y.len());
1912 // This function is adapted from
1913 // https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memmem/util.rs#L32
1914
1915 // If we don't have enough bytes to do 4-byte at a time loads, then
1916 // fall back to the naive slow version.
1917 //
1918 // Potential alternative: We could do a copy_nonoverlapping combined with a mask instead
1919 // of a loop. Benchmark it.
1920 if x.len() < 4 {
1921 for (&b1, &b2) in x.iter().zip(y) {
1922 if b1 != b2 {
1923 return false;
1924 }
1925 }
1926 return true;
1927 }
1928 // When we have 4 or more bytes to compare, then proceed in chunks of 4 at
1929 // a time using unaligned loads.
1930 //
1931 // Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is
1932 // that this particular version of memcmp is likely to be called with tiny
1933 // needles. That means that if we do 8 byte loads, then a higher proportion
1934 // of memcmp calls will use the slower variant above. With that said, this
1935 // is a hypothesis and is only loosely supported by benchmarks. There's
1936 // likely some improvement that could be made here. The main thing here
1937 // though is to optimize for latency, not throughput.
1938
1939 // SAFETY: Via the conditional above, we know that both `px` and `py`
1940 // have the same length, so `px < pxend` implies that `py < pyend`.
1941 // Thus, dereferencing both `px` and `py` in the loop below is safe.
1942 //
1943 // Moreover, we set `pxend` and `pyend` to be 4 bytes before the actual
1944 // end of `px` and `py`. Thus, the final dereference outside of the
1945 // loop is guaranteed to be valid. (The final comparison will overlap with
1946 // the last comparison done in the loop for lengths that aren't multiples
1947 // of four.)
1948 //
1949 // Finally, we needn't worry about alignment here, since we do unaligned
1950 // loads.
1951 unsafe {
1952 let (mut px, mut py) = (x.as_ptr(), y.as_ptr());
1953 let (pxend, pyend) = (px.add(x.len() - 4), py.add(y.len() - 4));
1954 while px < pxend {
1955 let vx = (px as *const u32).read_unaligned();
1956 let vy = (py as *const u32).read_unaligned();
1957 if vx != vy {
1958 return false;
1959 }
1960 px = px.add(4);
1961 py = py.add(4);
1962 }
1963 let vx = (pxend as *const u32).read_unaligned();
1964 let vy = (pyend as *const u32).read_unaligned();
1965 vx == vy
1966 }
1967}