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 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 /// This stores `str` rather than bytes so callers cannot describe
176 /// non-UTF-8 string patterns through this API.
177 StringPattern(&'a str),
178 /// Type returned by char types.
179 CharPattern(char),
180}
181
182// Searcher
183
184/// Result of calling [`Searcher::next()`] or [`ReverseSearcher::next_back()`].
185#[derive(Copy, Clone, Eq, PartialEq, Debug)]
186pub enum SearchStep {
187 /// Expresses that a match of the pattern has been found at
188 /// `haystack[a..b]`.
189 Match(usize, usize),
190 /// Expresses that `haystack[a..b]` has been rejected as a possible match
191 /// of the pattern.
192 ///
193 /// Note that there might be more than one `Reject` between two `Match`es,
194 /// there is no requirement for them to be combined into one.
195 Reject(usize, usize),
196 /// Expresses that every byte of the haystack has been visited, ending
197 /// the iteration.
198 Done,
199}
200
201/// A searcher for a string pattern.
202///
203/// This trait provides methods for searching for non-overlapping
204/// matches of a pattern starting from the front (left) of a string.
205///
206/// It will be implemented by associated `Searcher`
207/// types of the [`Pattern`] trait.
208///
209/// The trait is marked unsafe because the indices returned by the
210/// [`next()`][Searcher::next] methods are required to lie on valid utf8
211/// boundaries in the haystack. This enables consumers of this trait to
212/// slice the haystack without additional runtime checks.
213pub unsafe trait Searcher<'a> {
214 /// Getter for the underlying string to be searched in
215 ///
216 /// Will always return the same [`&str`][str].
217 fn haystack(&self) -> &'a str;
218
219 /// Performs the next search step starting from the front.
220 ///
221 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]` matches
222 /// the pattern.
223 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]` can
224 /// not match the pattern, even partially.
225 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack has
226 /// been visited.
227 ///
228 /// The stream of [`Match`][SearchStep::Match] and
229 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
230 /// will contain index ranges that are adjacent, non-overlapping,
231 /// covering the whole haystack, and laying on utf8 boundaries.
232 ///
233 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
234 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
235 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
236 ///
237 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
238 /// might produce the stream
239 /// `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
240 fn next(&mut self) -> SearchStep;
241
242 /// Finds the next [`Match`][SearchStep::Match] result. See [`next()`][Searcher::next].
243 ///
244 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
245 /// of this and [`next_reject`][Searcher::next_reject] will overlap. This will return
246 /// `(start_match, end_match)`, where start_match is the index of where
247 /// the match begins, and end_match is the index after the end of the match.
248 #[inline]
249 fn next_match(&mut self) -> Option<(usize, usize)> {
250 loop {
251 match self.next() {
252 SearchStep::Match(a, b) => return Some((a, b)),
253 SearchStep::Done => return None,
254 _ => continue,
255 }
256 }
257 }
258
259 /// Finds the next [`Reject`][SearchStep::Reject] result. See [`next()`][Searcher::next]
260 /// and [`next_match()`][Searcher::next_match].
261 ///
262 /// Unlike [`next()`][Searcher::next], there is no guarantee that the returned ranges
263 /// of this and [`next_match`][Searcher::next_match] will overlap.
264 #[inline]
265 fn next_reject(&mut self) -> Option<(usize, usize)> {
266 loop {
267 match self.next() {
268 SearchStep::Reject(a, b) => return Some((a, b)),
269 SearchStep::Done => return None,
270 _ => continue,
271 }
272 }
273 }
274}
275
276/// A reverse searcher for a string pattern.
277///
278/// This trait provides methods for searching for non-overlapping
279/// matches of a pattern starting from the back (right) of a string.
280///
281/// It will be implemented by associated [`Searcher`]
282/// types of the [`Pattern`] trait if the pattern supports searching
283/// for it from the back.
284///
285/// The index ranges returned by this trait are not required
286/// to exactly match those of the forward search in reverse.
287///
288/// For the reason why this trait is marked unsafe, see the
289/// parent trait [`Searcher`].
290pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
291 /// Performs the next search step starting from the back.
292 ///
293 /// - Returns [`Match(a, b)`][SearchStep::Match] if `haystack[a..b]`
294 /// matches the pattern.
295 /// - Returns [`Reject(a, b)`][SearchStep::Reject] if `haystack[a..b]`
296 /// can not match the pattern, even partially.
297 /// - Returns [`Done`][SearchStep::Done] if every byte of the haystack
298 /// has been visited
299 ///
300 /// The stream of [`Match`][SearchStep::Match] and
301 /// [`Reject`][SearchStep::Reject] values up to a [`Done`][SearchStep::Done]
302 /// will contain index ranges that are adjacent, non-overlapping,
303 /// covering the whole haystack, and laying on utf8 boundaries.
304 ///
305 /// A [`Match`][SearchStep::Match] result needs to contain the whole matched
306 /// pattern, however [`Reject`][SearchStep::Reject] results may be split up
307 /// into arbitrary many adjacent fragments. Both ranges may have zero length.
308 ///
309 /// As an example, the pattern `"aaa"` and the haystack `"cbaaaaab"`
310 /// might produce the stream
311 /// `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`.
312 fn next_back(&mut self) -> SearchStep;
313
314 /// Finds the next [`Match`][SearchStep::Match] result.
315 /// See [`next_back()`][ReverseSearcher::next_back].
316 #[inline]
317 fn next_match_back(&mut self) -> Option<(usize, usize)> {
318 loop {
319 match self.next_back() {
320 SearchStep::Match(a, b) => return Some((a, b)),
321 SearchStep::Done => return None,
322 _ => continue,
323 }
324 }
325 }
326
327 /// Finds the next [`Reject`][SearchStep::Reject] result.
328 /// See [`next_back()`][ReverseSearcher::next_back].
329 #[inline]
330 fn next_reject_back(&mut self) -> Option<(usize, usize)> {
331 loop {
332 match self.next_back() {
333 SearchStep::Reject(a, b) => return Some((a, b)),
334 SearchStep::Done => return None,
335 _ => continue,
336 }
337 }
338 }
339}
340
341/// A marker trait to express that a [`ReverseSearcher`]
342/// can be used for a [`DoubleEndedIterator`] implementation.
343///
344/// For this, the impl of [`Searcher`] and [`ReverseSearcher`] need
345/// to follow these conditions:
346///
347/// - All results of `next()` need to be identical
348/// to the results of `next_back()` in reverse order.
349/// - `next()` and `next_back()` need to behave as
350/// the two ends of a range of values, that is they
351/// can not "walk past each other".
352///
353/// # Examples
354///
355/// `char::Searcher` is a `DoubleEndedSearcher` because searching for a
356/// [`char`] only requires looking at one at a time, which behaves the same
357/// from both ends.
358///
359/// `(&str)::Searcher` is not a `DoubleEndedSearcher` because
360/// the pattern `"aa"` in the haystack `"aaa"` matches as either
361/// `"[aa]a"` or `"a[aa]"`, depending on which side it is searched.
362pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}
363
364/////////////////////////////////////////////////////////////////////////////
365// Impl for char
366/////////////////////////////////////////////////////////////////////////////
367
368/// Associated type for `<char as Pattern>::Searcher<'a>`.
369#[derive(Clone, Debug)]
370pub struct CharSearcher<'a> {
371 haystack: &'a str,
372 // safety invariant: `finger`/`finger_back` must be a valid utf8 byte index of `haystack`
373 // This invariant can be broken *within* next_match and next_match_back, however
374 // they must exit with fingers on valid code point boundaries.
375 /// `finger` is the current byte index of the forward search.
376 /// Imagine that it exists before the byte at its index, i.e.
377 /// `haystack[finger]` is the first byte of the slice we must inspect during
378 /// forward searching
379 finger: usize,
380 /// `finger_back` is the current byte index of the reverse search.
381 /// Imagine that it exists after the byte at its index, i.e.
382 /// haystack[finger_back - 1] is the last byte of the slice we must inspect during
383 /// forward searching (and thus the first byte to be inspected when calling next_back()).
384 finger_back: usize,
385 /// The character being searched for
386 needle: char,
387
388 // safety invariant: `utf8_size` must be less than 5
389 /// The number of bytes `needle` takes up when encoded in utf8.
390 utf8_size: u8,
391 /// A utf8 encoded copy of the `needle`
392 utf8_encoded: [u8; 4],
393}
394
395impl CharSearcher<'_> {
396 fn utf8_size(&self) -> usize {
397 self.utf8_size.into()
398 }
399}
400
401unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
402 #[inline]
403 fn haystack(&self) -> &'a str {
404 self.haystack
405 }
406 #[inline]
407 fn next(&mut self) -> SearchStep {
408 let old_finger = self.finger;
409 // SAFETY: 1-4 guarantee safety of `get_unchecked`
410 // 1. `self.finger` and `self.finger_back` are kept on unicode boundaries
411 // (this is invariant)
412 // 2. `self.finger >= 0` since it starts at 0 and only increases
413 // 3. `self.finger < self.finger_back` because otherwise the char `iter`
414 // would return `SearchStep::Done`
415 // 4. `self.finger` comes before the end of the haystack because `self.finger_back`
416 // starts at the end and only decreases
417 let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
418 let mut iter = slice.chars();
419 let old_len = iter.iter.len();
420 if let Some(ch) = iter.next() {
421 // add byte offset of current character
422 // without re-encoding as utf-8
423 self.finger += old_len - iter.iter.len();
424 if ch == self.needle {
425 SearchStep::Match(old_finger, self.finger)
426 } else {
427 SearchStep::Reject(old_finger, self.finger)
428 }
429 } else {
430 SearchStep::Done
431 }
432 }
433 #[inline]
434 fn next_match(&mut self) -> Option<(usize, usize)> {
435 loop {
436 // get the haystack after the last character found
437 let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
438 // the last byte of the utf8 encoded needle
439 // SAFETY: we have an invariant that `utf8_size < 5`
440 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size() - 1) };
441 if let Some(index) = memchr::memchr(last_byte, bytes) {
442 // The new finger is the index of the byte we found,
443 // plus one, since we memchr'd for the last byte of the character.
444 //
445 // Note that this doesn't always give us a finger on a UTF8 boundary.
446 // If we *didn't* find our character
447 // we may have indexed to the non-last byte of a 3-byte or 4-byte character.
448 // We can't just skip to the next valid starting byte because a character like
449 // ꁁ (U+A041 YI SYLLABLE PA), utf-8 `EA 81 81` will have us always find
450 // the second byte when searching for the third.
451 //
452 // However, this is totally okay. While we have the invariant that
453 // self.finger is on a UTF8 boundary, this invariant is not relied upon
454 // within this method (it is relied upon in CharSearcher::next()).
455 //
456 // We only exit this method when we reach the end of the string, or if we
457 // find something. When we find something the `finger` will be set
458 // to a UTF8 boundary.
459 self.finger += index + 1;
460 if self.finger >= self.utf8_size() {
461 let found_char = self.finger - self.utf8_size();
462 if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
463 if slice == &self.utf8_encoded[0..self.utf8_size()] {
464 return Some((found_char, self.finger));
465 }
466 }
467 }
468 } else {
469 // found nothing, exit
470 self.finger = self.finger_back;
471 return None;
472 }
473 }
474 }
475
476 // let next_reject use the default implementation from the Searcher trait
477}
478
479unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
480 #[inline]
481 fn next_back(&mut self) -> SearchStep {
482 let old_finger = self.finger_back;
483 // SAFETY: see the comment for next() above
484 let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
485 let mut iter = slice.chars();
486 let old_len = iter.iter.len();
487 if let Some(ch) = iter.next_back() {
488 // subtract byte offset of current character
489 // without re-encoding as utf-8
490 self.finger_back -= old_len - iter.iter.len();
491 if ch == self.needle {
492 SearchStep::Match(self.finger_back, old_finger)
493 } else {
494 SearchStep::Reject(self.finger_back, old_finger)
495 }
496 } else {
497 SearchStep::Done
498 }
499 }
500 #[inline]
501 fn next_match_back(&mut self) -> Option<(usize, usize)> {
502 let haystack = self.haystack.as_bytes();
503 loop {
504 // get the haystack up to but not including the last character searched
505 let bytes = haystack.get(self.finger..self.finger_back)?;
506 // the last byte of the utf8 encoded needle
507 // SAFETY: we have an invariant that `utf8_size < 5`
508 let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size() - 1) };
509 if let Some(index) = memchr::memrchr(last_byte, bytes) {
510 // we searched a slice that was offset by self.finger,
511 // add self.finger to recoup the original index
512 let index = self.finger + index;
513 // memrchr will return the index of the byte we wish to
514 // find. In case of an ASCII character, this is indeed
515 // were we wish our new finger to be ("after" the found
516 // char in the paradigm of reverse iteration). For
517 // multibyte chars we need to skip down by the number of more
518 // bytes they have than ASCII
519 let shift = self.utf8_size() - 1;
520 if index >= shift {
521 let found_char = index - shift;
522 if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size())) {
523 if slice == &self.utf8_encoded[0..self.utf8_size()] {
524 // move finger to before the character found (i.e., at its start index)
525 self.finger_back = found_char;
526 return Some((self.finger_back, self.finger_back + self.utf8_size()));
527 }
528 }
529 }
530 // We can't use finger_back = index - size + 1 here. If we found the last char
531 // of a different-sized character (or the middle byte of a different character)
532 // we need to bump the finger_back down to `index`. This similarly makes
533 // `finger_back` have the potential to no longer be on a boundary,
534 // but this is OK since we only exit this function on a boundary
535 // or when the haystack has been searched completely.
536 //
537 // Unlike next_match this does not
538 // have the problem of repeated bytes in utf-8 because
539 // we're searching for the last byte, and we can only have
540 // found the last byte when searching in reverse.
541 self.finger_back = index;
542 } else {
543 self.finger_back = self.finger;
544 // found nothing, exit
545 return None;
546 }
547 }
548 }
549
550 // let next_reject_back use the default implementation from the Searcher trait
551}
552
553impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}
554
555/// Searches for chars that are equal to a given [`char`].
556///
557/// # Examples
558///
559/// ```
560/// assert_eq!("Hello world".find('o'), Some(4));
561/// ```
562impl Pattern for char {
563 type Searcher<'a> = CharSearcher<'a>;
564
565 #[inline]
566 fn into_searcher<'a>(self, haystack: &'a str) -> Self::Searcher<'a> {
567 let mut utf8_encoded = [0; char::MAX_LEN_UTF8];
568 let utf8_size = self
569 .encode_utf8(&mut utf8_encoded)
570 .len()
571 .try_into()
572 .expect("char len should be less than 255");
573
574 CharSearcher {
575 haystack,
576 finger: 0,
577 finger_back: haystack.len(),
578 needle: self,
579 utf8_size,
580 utf8_encoded,
581 }
582 }
583
584 #[inline]
585 fn is_contained_in(self, haystack: &str) -> bool {
586 if (self as u32) <