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