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