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