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