//! 字符串模式 API。
//!
//! Pattern API 提供了泛型机制，用于在搜索字符串时使用不同的模式类型。
//!
//! 有关更多详细信息，请参见 traits [`Pattern`]，[`Searcher`]，[`ReverseSearcher`] 和 [`DoubleEndedSearcher`]。
//!
//! 尽管此 API 不稳定，但是它通过 [`str`] 类型的稳定 API 公开。
//!
//! # Examples
//!
//! [`Pattern`] 是 [`&str`][`str`]、[`char`]、[`char`] 的切片以及实现 `FnMut(char) -> bool` 的函数和闭包的稳定 API 中的 [implemented][pattern-impls]。
//!
//!
//! ```
//! let s = "Can you find a needle in a haystack?";
//!
//! // &str 模式
//! assert_eq!(s.find("you"), Some(4));
//! // 字符模式
//! assert_eq!(s.find('n'), Some(2));
//! // 字符模式数组
//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u']), Some(1));
//! // 切片的字符模式
//! assert_eq!(s.find(&['a', 'e', 'i', 'o', 'u'][..]), Some(1));
//! // 闭包模式
//! assert_eq!(s.find(|c: char| c.is_ascii_punctuation()), Some(35));
//! ```
//!
//! [pattern-impls]: Pattern#implementors
//!
//!
//!
//!

#![unstable(
    feature = "pattern",
    reason = "API not fully fleshed out and ready to be stabilized",
    issue = "27721"
)]

use crate::cmp;
use crate::cmp::Ordering;
use crate::fmt;
use crate::slice::memchr;

// Pattern

/// 字符串模式。
///
/// `Pattern<'a>` 表示实现类型可以用作在 [`&'a str`][str] 中搜索的字符串模式。
///
/// 例如，`'a'` 和 `"aa"` 都是在字符串 `"baaaab"` 中的索引 `1` 处匹配的模式。
///
/// 这个 trait 本身充当关联的 [`Searcher`] 类型的构建器，该类型执行在字符串中查找模式的实际工作。
///
///
/// 根据模式的类型，诸如 [`str::find`] 和 [`str::contains`] 之类的方法的行为可能会改变。
/// 下表描述了其中一些行为。
///
/// | Pattern type             | Match condition                           |
/// |--------------------------|-------------------------------------------|
/// | `&str`                   | is substring                              |
/// | `char`                   | is contained in string                    |
/// | `&[char]`                | any char in slice is contained in string  |
/// | `F: FnMut(char) -> bool` | `F` returns `true` for a char in string   |
/// | `&&str`                  | is substring                              |
/// | `&String`                | is substring                              |
///
/// # Examples
///
/// ```
/// // &str
/// assert_eq!("abaaa".find("ba"), Some(1));
/// assert_eq!("abaaa".find("bac"), None);
///
/// // char
/// assert_eq!("abaaa".find('a'), Some(0));
/// assert_eq!("abaaa".find('b'), Some(1));
/// assert_eq!("abaaa".find('c'), None);
///
/// // &[char; N]
/// assert_eq!("ab".find(&['b', 'a']), Some(0));
/// assert_eq!("abaaa".find(&['a', 'z']), Some(0));
/// assert_eq!("abaaa".find(&['c', 'd']), None);
///
/// // &[char]
/// assert_eq!("ab".find(&['b', 'a'][..]), Some(0));
/// assert_eq!("abaaa".find(&['a', 'z'][..]), Some(0));
/// assert_eq!("abaaa".find(&['c', 'd'][..]), None);
///
/// // FnMut(char) -> bool
/// assert_eq!("abcdef_z".find(|ch| ch > 'd' && ch < 'y'), Some(4));
/// assert_eq!("abcddd_z".find(|ch| ch > 'd' && ch < 'y'), None);
/// ```
///
///
///
///
pub trait Pattern<'a>: Sized {
    /// 此模式的关联搜索者
    type Searcher: Searcher<'a>;

    /// 从 `self` 和 `haystack` 构造关联的搜索器以进行搜索。
    ///
    fn into_searcher(self, haystack: &'a str) -> Self::Searcher;

    /// 检查模式是否与 haystack 中的任何位置匹配
    #[inline]
    fn is_contained_in(self, haystack: &'a str) -> bool {
        self.into_searcher(haystack).next_match().is_some()
    }

    /// 检查模式是否在 haystack 的前面匹配
    #[inline]
    fn is_prefix_of(self, haystack: &'a str) -> bool {
        matches!(self.into_searcher(haystack).next(), SearchStep::Match(0, _))
    }

    /// 检查模式是否与 haystack 的后面匹配
    #[inline]
    fn is_suffix_of(self, haystack: &'a str) -> bool
    where
        Self::Searcher: ReverseSearcher<'a>,
    {
        matches!(self.into_searcher(haystack).next_back(), SearchStep::Match(_, j) if haystack.len() == j)
    }

    /// 如果匹配，则从 haystack 的正面删除模式。
    #[inline]
    fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
        if let SearchStep::Match(start, len) = self.into_searcher(haystack).next() {
            debug_assert_eq!(
                start, 0,
                "The first search step from Searcher \
                 must include the first character"
            );
            // SAFETY: 已知 `Searcher` 返回有效索引。
            unsafe { Some(haystack.get_unchecked(len..)) }
        } else {
            None
        }
    }

    /// 如果匹配，则从 haystack 的后面删除模式。
    #[inline]
    fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
    where
        Self::Searcher: ReverseSearcher<'a>,
    {
        if let SearchStep::Match(start, end) = self.into_searcher(haystack).next_back() {
            debug_assert_eq!(
                end,
                haystack.len(),
                "The first search step from ReverseSearcher \
                 must include the last character"
            );
            // SAFETY: 已知 `Searcher` 返回有效索引。
            unsafe { Some(haystack.get_unchecked(..start)) }
        } else {
            None
        }
    }
}

// Searcher

/// 调用 [`Searcher::next()`] 或 [`ReverseSearcher::next_back()`] 的结果。
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
pub enum SearchStep {
    /// 表示已在 `haystack[a..b]` 找到匹配的模式。
    ///
    Match(usize, usize),
    /// 表示已拒绝 `haystack[a..b]` 作为该模式的可能匹配。
    ///
    /// 注意，两个 `Match` 之间可能有多个 `Reject`，不需要将它们组合为一个。
    ///
    ///
    Reject(usize, usize),
    /// 表示已访问 haystack 的每个字节，从而结束了迭代。
    ///
    Done,
}

/// 字符串模式的搜索者。
///
/// 这个 trait 提供了从字符串的前面 (左边) 开始搜索模式的非重叠匹配的方法。
///
/// 将通过 [`Pattern`] trait 的相关 `Searcher` 类型实现。
///
/// 这个 trait 被标记为不安全，因为 [`next()`][Searcher::next] 方法返回的索引必须位于 haystack 中的有效 utf8 边界上。
/// 这使 trait 的使用者可以对 haystack 进行切片，而无需进行其他运行时检查。
///
///
///
///
pub unsafe trait Searcher<'a> {
    /// 要在其中搜索的底层字符串的 Getter
    ///
    /// 总是返回相同的 [`&str`][str]。
    fn haystack(&self) -> &'a str;

    /// 从头开始执行下一个搜索步骤。
    ///
    /// - 如果 `haystack[a..b]` 与模式匹配，则返回 [`Match(a, b)`][SearchStep::Match]。
    /// - 如果 `haystack[a..b]` 甚至部分不匹配，则返回 [`Reject(a, b)`][SearchStep::Reject]。
    /// - 如果已访问 haystack 的每个字节，则返回 [`Done`][SearchStep::Done]。
    ///
    /// 直到 [`Done`][SearchStep::Done] 的 [`Match`][SearchStep::Match] 和 [`Reject`][SearchStep::Reject] 值流将包含相邻，不重叠，覆盖整个 haystack 并位于 utf8 边界上的索引范围。
    ///
    ///
    /// [`Match`][SearchStep::Match] 结果需要包含整个匹配的模式，但是 [`Reject`][SearchStep::Reject] 结果可以分为任意多个相邻的片段。两个范围的长度都可以为零。
    ///
    /// 例如，模式 `"aaa"` 和 haystack `"cbaaaaab"` 可能产生流 `[Reject(0, 1), Reject(1, 2), Match(2, 5), Reject(5, 8)]`
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    fn next(&mut self) -> SearchStep;

    /// 查找下一个 [`Match`][SearchStep::Match] 结果。请参见 [`next()`][Searcher::next]。
    ///
    /// 与 [`next()`][Searcher::next] 不同，不能保证此和 [`next_reject`][Searcher::next_reject] 的返回范围会重叠。
    /// 这将返回 `(start_match, end_match)`，其中 start_match 是匹配开始的索引，end_match 是匹配结束后的索引。
    ///
    ///
    #[inline]
    fn next_match(&mut self) -> Option<(usize, usize)> {
        loop {
            match self.next() {
                SearchStep::Match(a, b) => return Some((a, b)),
                SearchStep::Done => return None,
                _ => continue,
            }
        }
    }

    /// 查找下一个 [`Reject`][SearchStep::Reject] 结果。请参见 [`next()`][Searcher::next] 和 [`next_match()`][Searcher::next_match]。
    ///
    /// 与 [`next()`][Searcher::next] 不同，不能保证此和 [`next_match`][Searcher::next_match] 的返回范围会重叠。
    ///
    ///
    #[inline]
    fn next_reject(&mut self) -> Option<(usize, usize)> {
        loop {
            match self.next() {
                SearchStep::Reject(a, b) => return Some((a, b)),
                SearchStep::Done => return None,
                _ => continue,
            }
        }
    }
}

/// 反向搜索字符串模式。
///
/// 这个 trait 提供了从字符串的后面 (右边) 开始搜索模式的非重叠匹配的方法。
///
/// 如果该模式支持从后面搜索它，则将通过 [`Pattern`] trait 的关联 [`Searcher`] 类型实现。
///
///
/// 这个 trait 返回的索引范围不需要与反转的正向搜索的索引范围完全匹配。
///
/// 关于这个 trait 被标记为不安全的原因，请参见父 trait [`Searcher`]。
///
///
///
///
pub unsafe trait ReverseSearcher<'a>: Searcher<'a> {
    /// 从后面开始执行下一个搜索步骤。
    ///
    /// - 如果 `haystack[a..b]` 与模式匹配，则返回 [`Match(a, b)`][SearchStep::Match]。
    /// - 如果 `haystack[a..b]` 甚至部分不匹配，则返回 [`Reject(a, b)`][SearchStep::Reject]。
    /// - 如果已访问 haystack 的每个字节，则返回 [`Done`][SearchStep::Done]
    ///
    /// 直到 [`Done`][SearchStep::Done] 的 [`Match`][SearchStep::Match] 和 [`Reject`][SearchStep::Reject] 值流将包含相邻，不重叠，覆盖整个 haystack 并位于 utf8 边界上的索引范围。
    ///
    ///
    /// [`Match`][SearchStep::Match] 结果需要包含整个匹配的模式，但是 [`Reject`][SearchStep::Reject] 结果可以分为任意多个相邻的片段。两个范围的长度都可以为零。
    ///
    /// 例如，模式 `"aaa"` 和 haystack `"cbaaaaab"` 可能会产生流 `[Reject(7, 8), Match(4, 7), Reject(1, 4), Reject(0, 1)]`。
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    fn next_back(&mut self) -> SearchStep;

    /// 查找下一个 [`Match`][SearchStep::Match] 结果。
    /// 请参见 [`next_back()`][ReverseSearcher::next_back]。
    #[inline]
    fn next_match_back(&mut self) -> Option<(usize, usize)> {
        loop {
            match self.next_back() {
                SearchStep::Match(a, b) => return Some((a, b)),
                SearchStep::Done => return None,
                _ => continue,
            }
        }
    }

    /// 查找下一个 [`Reject`][SearchStep::Reject] 结果。
    /// 请参见 [`next_back()`][ReverseSearcher::next_back]。
    #[inline]
    fn next_reject_back(&mut self) -> Option<(usize, usize)> {
        loop {
            match self.next_back() {
                SearchStep::Reject(a, b) => return Some((a, b)),
                SearchStep::Done => return None,
                _ => continue,
            }
        }
    }
}

/// 一个标记 trait，表示 [`ReverseSearcher`] 可用于 [`DoubleEndedIterator`] 实现。
///
/// 为此，[`Searcher`] 和 [`ReverseSearcher`] 的 impl 需要遵循以下条件：
///
/// - `next()` 的所有结果必须与 `next_back()` 的结果相反 (顺序相反)。
/// - `next()` 和 `next_back()` 需要表现为一个值范围的两端，即它们不能作为 "walk past each other"。
///
/// # Examples
///
/// `char::Searcher` 是 `DoubleEndedSearcher`，因为搜索 [`char`] 只需要一次查看一个，从两端的行为相同。
///
/// `(&str)::Searcher` 不是 `DoubleEndedSearcher`，因为 haystack `"aaa"` 中的模式 `"aa"` 匹配为 `"[aa]a"` 或 `"a[aa]"`，具体取决于从哪一侧搜索。
///
///
///
///
///
///
///
///
///
pub trait DoubleEndedSearcher<'a>: ReverseSearcher<'a> {}

/////////////////////////////////////////////////////////////////////////////
// 字符的 Impl
/////////////////////////////////////////////////////////////////////////////

/// `<char as Pattern<'a>>::Searcher` 的关联类型。
#[derive(Clone, Debug)]
pub struct CharSearcher<'a> {
    haystack: &'a str,
    // 安全不变量: `finger`/`finger_back` 必须是 `haystack` 的有效 utf8 字节索引。可以在 *next_match 和 next_match_back 之内* 破坏该不变量，但是它们必须在有效的代码点边界上用手指退出。
    //
    //
    /// `finger` 是前向搜索的当前字节索引。
    /// 想象一下，它存在于其索引的字节之前，即
    /// `haystack[finger]` 是我们在前向搜索期间必须检查的切片的第一个字节
    ///
    finger: usize,
    /// `finger_back` 是反向搜索的当前字节索引。
    /// 想象一下，它存在于其索引的字节之后，即
    /// haystack[finger_back - 1] 是在向前搜索期间必须检查的片的最后一个字节 (因此，在调用 next_back()) 时要检查的第一个字节)。
    ///
    finger_back: usize,
    /// 要搜索的字符
    needle: char,

    // 安全不变量: `utf8_size` 必须小于 5
    /// 当用 utf8 编码时，`needle` 占用的字节数。
    utf8_size: usize,
    /// `needle` 的 utf8 编码副本
    utf8_encoded: [u8; 4],
}

unsafe impl<'a> Searcher<'a> for CharSearcher<'a> {
    #[inline]
    fn haystack(&self) -> &'a str {
        self.haystack
    }
    #[inline]
    fn next(&mut self) -> SearchStep {
        let old_finger = self.finger;
        // SAFETY: 1-4 保证 `get_unchecked` 的安全
        // 1. `self.finger` 和 `self.finger_back` 保持在 unicode 边界上 (这是不变的)
        // 2. `self.finger >= 0` 因为它从 0 开始并且只会增加
        // 3. `self.finger < self.finger_back` 因为否则字符 `iter` 将返回 `SearchStep::Done`
        // 4.
        // `self.finger` 出现在 haystack 的末尾之前，因为 `self.finger_back` 从末尾开始并且只会减少
        //
        //
        let slice = unsafe { self.haystack.get_unchecked(old_finger..self.finger_back) };
        let mut iter = slice.chars();
        let old_len = iter.iter.len();
        if let Some(ch) = iter.next() {
            // 添加当前字符的字节偏移，而无需重新编码为 utf-8
            //
            self.finger += old_len - iter.iter.len();
            if ch == self.needle {
                SearchStep::Match(old_finger, self.finger)
            } else {
                SearchStep::Reject(old_finger, self.finger)
            }
        } else {
            SearchStep::Done
        }
    }
    #[inline]
    fn next_match(&mut self) -> Option<(usize, usize)> {
        loop {
            // 找到最后一个字符后得到 haystack
            let bytes = self.haystack.as_bytes().get(self.finger..self.finger_back)?;
            // utf8 编码的指针的最后一个字节
            // SAFETY: 我们有一个不变的 `utf8_size < 5`
            let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
            if let Some(index) = memchr::memchr(last_byte, bytes) {
                // 新手指是我们找到的字节的索引加一个，因为我们对字符的最后一个字节进行了记忆。
                //
                // 请注意，这并不总是使我们能够了解 UTF8 的边界。
                // 如果没有找到我们的字符，我们可能已经索引到 3 字节或 4 字节字符的非最后一个字节。
                // 我们不能只跳到下一个有效的起始字节，因为像ꁁ (U+A041 YI SYLLABLE PA)，utf-8 `EA 81 81` 这样的字符将使我们在搜索第三个字节时总是找到第二个字节。
                //
                //
                // 但是，这完全可以。
                // 尽管我们拥有 self.finger 在 UTF8 边界上的不变量，但在这个方法中并不依赖这个不变量 (在 CharSearcher::next () 中依赖此不变量)。
                //
                // 仅当到达字符串末尾或找到某些内容时，才退出此方法。当我们发现某些东西时，`finger` 将被设置为 UTF8 边界。
                //
                //
                //
                //
                //
                //
                self.finger += index + 1;
                if self.finger >= self.utf8_size {
                    let found_char = self.finger - self.utf8_size;
                    if let Some(slice) = self.haystack.as_bytes().get(found_char..self.finger) {
                        if slice == &self.utf8_encoded[0..self.utf8_size] {
                            return Some((found_char, self.finger));
                        }
                    }
                }
            } else {
                // 一无所获，退出
                self.finger = self.finger_back;
                return None;
            }
        }
    }

    // 让 next_reject 使用搜索器 trait 的默认实现
}

unsafe impl<'a> ReverseSearcher<'a> for CharSearcher<'a> {
    #[inline]
    fn next_back(&mut self) -> SearchStep {
        let old_finger = self.finger_back;
        // SAFETY: 请参见上面的 next() 注释
        let slice = unsafe { self.haystack.get_unchecked(self.finger..old_finger) };
        let mut iter = slice.chars();
        let old_len = iter.iter.len();
        if let Some(ch) = iter.next_back() {
            // 减去当前字符的字节偏移，而无需重新编码为 utf-8
            //
            self.finger_back -= old_len - iter.iter.len();
            if ch == self.needle {
                SearchStep::Match(self.finger_back, old_finger)
            } else {
                SearchStep::Reject(self.finger_back, old_finger)
            }
        } else {
            SearchStep::Done
        }
    }
    #[inline]
    fn next_match_back(&mut self) -> Option<(usize, usize)> {
        let haystack = self.haystack.as_bytes();
        loop {
            // 使 haystack 达到但不包括搜索到的最后一个字符
            let bytes = haystack.get(self.finger..self.finger_back)?;
            // utf8 编码的指针的最后一个字节
            // SAFETY: 我们有一个不变的 `utf8_size < 5`
            let last_byte = unsafe { *self.utf8_encoded.get_unchecked(self.utf8_size - 1) };
            if let Some(index) = memchr::memrchr(last_byte, bytes) {
                // 我们搜索了被 self.finger 偏移的切片，添加 self.finger 以补偿原始索引
                //
                let index = self.finger + index;
                // memrchr 将返回我们希望找到的字节的索引。
                // 如果是 ASCII 字符，这确实是我们希望的新手指 ("after" 是反向迭代范式中找到的 char)。
                //
                // 对于多字节字符，我们需要跳过的字节数比 ASCII 多
                //
                //
                let shift = self.utf8_size - 1;
                if index >= shift {
                    let found_char = index - shift;
                    if let Some(slice) = haystack.get(found_char..(found_char + self.utf8_size)) {
                        if slice == &self.utf8_encoded[0..self.utf8_size] {
                            // 将手指移到找到的字符之前 (即，在其起始索引处)
                            self.finger_back = found_char;
                            return Some((self.finger_back, self.finger_back + self.utf8_size));
                        }
                    }
                }
                // 我们不能在这里使用 finger_back=index-size + 1。
                // 如果找到不同大小字符的最后一个字符 (或不同字符的中间字节)，则需要将 finger_back 降低到 `index`。
                // 同样，这使 `finger_back` 不再有可能位于边界上，但这是可以的，因为我们仅在边界上或在完全搜索 haystack 时退出此函数。
                //
                //
                // 与 next_match 不同，这不存在 utf-8 中重复字节的问题，因为我们正在搜索最后一个字节，并且仅当反向搜索时才可以找到最后一个字节。
                //
                //
                //
                //
                //
                self.finger_back = index;
            } else {
                self.finger_back = self.finger;
                // 一无所获，退出
                return None;
            }
        }
    }

    // 让 next_reject_back 使用 Searcher trait 中的默认实现
}

impl<'a> DoubleEndedSearcher<'a> for CharSearcher<'a> {}

/// 搜索等于给定 [`char`] 的字符。
///
/// # Examples
///
/// ```
/// assert_eq!("Hello world".find('o'), Some(4));
/// ```
impl<'a> Pattern<'a> for char {
    type Searcher = CharSearcher<'a>;

    #[inline]
    fn into_searcher(self, haystack: &'a str) -> Self::Searcher {
        let mut utf8_encoded = [0; 4];
        let utf8_size = self.encode_utf8(&mut utf8_encoded).len();
        CharSearcher {
            haystack,
            finger: 0,
            finger_back: haystack.len(),
            needle: self,
            utf8_size,
            utf8_encoded,
        }
    }

    #[inline]
    fn is_contained_in(self, haystack: &'a str) -> bool {
        if (self as u32) < 128 {
            haystack.as_bytes().contains(&(self as u8))
        } else {
            let mut buffer = [0u8; 4];
            self.encode_utf8(&mut buffer).is_contained_in(haystack)
        }
    }

    #[inline]
    fn is_prefix_of(self, haystack: &'a str) -> bool {
        self.encode_utf8(&mut [0u8; 4]).is_prefix_of(haystack)
    }

    #[inline]
    fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
        self.encode_utf8(&mut [0u8; 4]).strip_prefix_of(haystack)
    }

    #[inline]
    fn is_suffix_of(self, haystack: &'a str) -> bool
    where
        Self::Searcher: ReverseSearcher<'a>,
    {
        self.encode_utf8(&mut [0u8; 4]).is_suffix_of(haystack)
    }

    #[inline]
    fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
    where
        Self::Searcher: ReverseSearcher<'a>,
    {
        self.encode_utf8(&mut [0u8; 4]).strip_suffix_of(haystack)
    }
}

/////////////////////////////////////////////////////////////////////////////
// 用于 MultiCharEq 包装器的 Impl
/////////////////////////////////////////////////////////////////////////////

#[doc(hidden)]
trait MultiCharEq {
    fn matches(&mut self, c: char) -> bool;
}

impl<F> MultiCharEq for F
where
    F: FnMut(char) -> bool,
{
    #[inline]
    fn matches(&mut self, c: char) -> bool {
        (*self)(c)
    }
}

impl<const N: usize> MultiCharEq for [char; N] {
    #[inline]
    fn matches(&mut self, c: char) -> bool {
        self.iter().any(|&m| m == c)
    }
}

impl<const N: usize> MultiCharEq for &[char; N] {
    #[inline]
    fn matches(&mut self, c: char) -> bool {
        self.iter().any(|&m| m == c)
    }
}

impl MultiCharEq for &[char] {
    #[inline]
    fn matches(&mut self, c: char) -> bool {
        self.iter().any(|&m| m == c)
    }
}

struct MultiCharEqPattern<C: MultiCharEq>(C);

#[derive(Clone, Debug)]
struct MultiCharEqSearcher<'a, C: MultiCharEq> {
    char_eq: C,
    haystack: &'a str,
    char_indices: super::CharIndices<'a>,
}

impl<'a, C: MultiCharEq> Pattern<'a> for MultiCharEqPattern<C> {
    type Searcher = MultiCharEqSearcher<'a, C>;

    #[inline]
    fn into_searcher(self, haystack: &'a str) -> MultiCharEqSearcher<'a, C> {
        MultiCharEqSearcher { haystack, char_eq: self.0, char_indices: haystack.char_indices() }
    }
}

unsafe impl<'a, C: MultiCharEq> Searcher<'a> for MultiCharEqSearcher<'a, C> {
    #[inline]
    fn haystack(&self) -> &'a str {
        self.haystack
    }

    #[inline]
    fn next(&mut self) -> SearchStep {
        let s = &mut self.char_indices;
        // 比较内部字节切片迭代器的长度以找到当前 char 的长度
        //
        let pre_len = s.iter.iter.len();
        if let Some((i, c)) = s.next() {
            let len = s.iter.iter.len();
            let char_len = pre_len - len;
            if self.char_eq.matches(c) {
                return SearchStep::Match(i, i + char_len);
            } else {
                return SearchStep::Reject(i, i + char_len);
            }
        }
        SearchStep::Done
    }
}

unsafe impl<'a, C: MultiCharEq> ReverseSearcher<'a> for MultiCharEqSearcher<'a, C> {
    #[inline]
    fn next_back(&mut self) -> SearchStep {
        let s = &mut self.char_indices;
        // 比较内部字节切片迭代器的长度以找到当前 char 的长度
        //
        let pre_len = s.iter.iter.len();
        if let Some((i, c)) = s.next_back() {
            let len = s.iter.iter.len();
            let char_len = pre_len - len;
            if self.char_eq.matches(c) {
                return SearchStep::Match(i, i + char_len);
            } else {
                return SearchStep::Reject(i, i + char_len);
            }
        }
        SearchStep::Done
    }
}

impl<'a, C: MultiCharEq> DoubleEndedSearcher<'a> for MultiCharEqSearcher<'a, C> {}

/////////////////////////////////////////////////////////////////////////////

macro_rules! pattern_methods {
    ($t:ty, $pmap:expr, $smap:expr) => {
        type Searcher = $t;

        #[inline]
        fn into_searcher(self, haystack: &'a str) -> $t {
            ($smap)(($pmap)(self).into_searcher(haystack))
        }

        #[inline]
        fn is_contained_in(self, haystack: &'a str) -> bool {
            ($pmap)(self).is_contained_in(haystack)
        }

        #[inline]
        fn is_prefix_of(self, haystack: &'a str) -> bool {
            ($pmap)(self).is_prefix_of(haystack)
        }

        #[inline]
        fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
            ($pmap)(self).strip_prefix_of(haystack)
        }

        #[inline]
        fn is_suffix_of(self, haystack: &'a str) -> bool
        where
            $t: ReverseSearcher<'a>,
        {
            ($pmap)(self).is_suffix_of(haystack)
        }

        #[inline]
        fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str>
        where
            $t: ReverseSearcher<'a>,
        {
            ($pmap)(self).strip_suffix_of(haystack)
        }
    };
}

macro_rules! searcher_methods {
    (forward) => {
        #[inline]
        fn haystack(&self) -> &'a str {
            self.0.haystack()
        }
        #[inline]
        fn next(&mut self) -> SearchStep {
            self.0.next()
        }
        #[inline]
        fn next_match(&mut self) -> Option<(usize, usize)> {
            self.0.next_match()
        }
        #[inline]
        fn next_reject(&mut self) -> Option<(usize, usize)> {
            self.0.next_reject()
        }
    };
    (reverse) => {
        #[inline]
        fn next_back(&mut self) -> SearchStep {
            self.0.next_back()
        }
        #[inline]
        fn next_match_back(&mut self) -> Option<(usize, usize)> {
            self.0.next_match_back()
        }
        #[inline]
        fn next_reject_back(&mut self) -> Option<(usize, usize)> {
            self.0.next_reject_back()
        }
    };
}

/// `<[char; N] as Pattern<'a>>::Searcher` 的关联类型。
#[derive(Clone, Debug)]
pub struct CharArraySearcher<'a, const N: usize>(
    <MultiCharEqPattern<[char; N]> as Pattern<'a>>::Searcher,
);

/// `<&[char; N] as Pattern<'a>>::Searcher` 的关联类型。
#[derive(Clone, Debug)]
pub struct CharArrayRefSearcher<'a, 'b, const N: usize>(
    <MultiCharEqPattern<&'b [char; N]> as Pattern<'a>>::Searcher,
);

/// 搜索等于数组中任何 [`char`] 的字符。
///
/// # Examples
///
/// ```
/// assert_eq!("Hello world".find(['o', 'l']), Some(2));
/// assert_eq!("Hello world".find(['h', 'w']), Some(6));
/// ```
impl<'a, const N: usize> Pattern<'a> for [char; N] {
    pattern_methods!(CharArraySearcher<'a, N>, MultiCharEqPattern, CharArraySearcher);
}

unsafe impl<'a, const N: usize> Searcher<'a> for CharArraySearcher<'a, N> {
    searcher_methods!(forward);
}

unsafe impl<'a, const N: usize> ReverseSearcher<'a> for CharArraySearcher<'a, N> {
    searcher_methods!(reverse);
}

/// 搜索等于数组中任何 [`char`] 的字符。
///
/// # Examples
///
/// ```
/// assert_eq!("Hello world".find(&['o', 'l']), Some(2));
/// assert_eq!("Hello world".find(&['h', 'w']), Some(6));
/// ```
impl<'a, 'b, const N: usize> Pattern<'a> for &'b [char; N] {
    pattern_methods!(CharArrayRefSearcher<'a, 'b, N>, MultiCharEqPattern, CharArrayRefSearcher);
}

unsafe impl<'a, 'b, const N: usize> Searcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
    searcher_methods!(forward);
}

unsafe impl<'a, 'b, const N: usize> ReverseSearcher<'a> for CharArrayRefSearcher<'a, 'b, N> {
    searcher_methods!(reverse);
}

/////////////////////////////////////////////////////////////////////////////
// &[char] 的 Impl
/////////////////////////////////////////////////////////////////////////////

// Todo: 由于含糊不清，请更改 / 删除。

/// `<&[char] as Pattern<'a>>::Searcher` 的关联类型。
#[derive(Clone, Debug)]
pub struct CharSliceSearcher<'a, 'b>(<MultiCharEqPattern<&'b [char]> as Pattern<'a>>::Searcher);

unsafe impl<'a, 'b> Searcher<'a> for CharSliceSearcher<'a, 'b> {
    searcher_methods!(forward);
}

unsafe impl<'a, 'b> ReverseSearcher<'a> for CharSliceSearcher<'a, 'b> {
    searcher_methods!(reverse);
}

impl<'a, 'b> DoubleEndedSearcher<'a> for CharSliceSearcher<'a, 'b> {}

/// 搜索等于切片中任何 [`char`] 的字符。
///
/// # Examples
///
/// ```
/// assert_eq!("Hello world".find(&['l', 'l'] as &[_]), Some(2));
/// assert_eq!("Hello world".find(&['l', 'l'][..]), Some(2));
/// ```
impl<'a, 'b> Pattern<'a> for &'b [char] {
    pattern_methods!(CharSliceSearcher<'a, 'b>, MultiCharEqPattern, CharSliceSearcher);
}

/////////////////////////////////////////////////////////////////////////////
// Impl for F: FnMut(char) -> bool
/////////////////////////////////////////////////////////////////////////////

/// `<F as Pattern<'a>>::Searcher` 的关联类型。
#[derive(Clone)]
pub struct CharPredicateSearcher<'a, F>(<MultiCharEqPattern<F> as Pattern<'a>>::Searcher)
where
    F: FnMut(char) -> bool;

impl<F> fmt::Debug for CharPredicateSearcher<'_, F>
where
    F: FnMut(char) -> bool,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("CharPredicateSearcher")
            .field("haystack", &self.0.haystack)
            .field("char_indices", &self.0.char_indices)
            .finish()
    }
}
unsafe impl<'a, F> Searcher<'a> for CharPredicateSearcher<'a, F>
where
    F: FnMut(char) -> bool,
{
    searcher_methods!(forward);
}

unsafe impl<'a, F> ReverseSearcher<'a> for CharPredicateSearcher<'a, F>
where
    F: FnMut(char) -> bool,
{
    searcher_methods!(reverse);
}

impl<'a, F> DoubleEndedSearcher<'a> for CharPredicateSearcher<'a, F> where F: FnMut(char) -> bool {}

/// 搜索与给定谓词匹配的 [`char`]。
///
/// # Examples
///
/// ```
/// assert_eq!("Hello world".find(char::is_uppercase), Some(0));
/// assert_eq!("Hello world".find(|c| "aeiou".contains(c)), Some(1));
/// ```
impl<'a, F> Pattern<'a> for F
where
    F: FnMut(char) -> bool,
{
    pattern_methods!(CharPredicateSearcher<'a, F>, MultiCharEqPattern, CharPredicateSearcher);
}

/////////////////////////////////////////////////////////////////////////////
// Impl for &&str
/////////////////////////////////////////////////////////////////////////////

/// 委托给 `&str` 的 impl。
impl<'a, 'b, 'c> Pattern<'a> for &'c &'b str {
    pattern_methods!(StrSearcher<'a, 'b>, |&s| s, |s| s);
}

/////////////////////////////////////////////////////////////////////////////
// &str 的 Impl
/////////////////////////////////////////////////////////////////////////////

/// 非分配子字符串搜索。
///
/// 将模式 `""` 处理为在每个字符边界处返回空匹配项。
///
///
/// # Examples
///
/// ```
/// assert_eq!("Hello world".find("world"), Some(6));
/// ```
impl<'a, 'b> Pattern<'a> for &'b str {
    type Searcher = StrSearcher<'a, 'b>;

    #[inline]
    fn into_searcher(self, haystack: &'a str) -> StrSearcher<'a, 'b> {
        StrSearcher::new(haystack, self)
    }

    /// 检查模式在 haystack 的前面是否匹配。
    #[inline]
    fn is_prefix_of(self, haystack: &'a str) -> bool {
        haystack.as_bytes().starts_with(self.as_bytes())
    }

    /// 检查模式是否与 haystack 中的任何位置匹配
    #[inline]
    fn is_contained_in(self, haystack: &'a str) -> bool {
        if self.len() == 0 {
            return true;
        }

        match self.len().cmp(&haystack.len()) {
            Ordering::Less => {
                if self.len() == 1 {
                    return haystack.as_bytes().contains(&self.as_bytes()[0]);
                }

                #[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
                if self.len() <= 32 {
                    if let Some(result) = simd_contains(self, haystack) {
                        return result;
                    }
                }

                self.into_searcher(haystack).next_match().is_some()
            }
            _ => self == haystack,
        }
    }

    /// 如果匹配，则从 haystack 的正面删除模式。
    #[inline]
    fn strip_prefix_of(self, haystack: &'a str) -> Option<&'a str> {
        if self.is_prefix_of(haystack) {
            // SAFETY: 前缀刚刚被验证为存在。
            unsafe { Some(haystack.get_unchecked(self.as_bytes().len()..)) }
        } else {
            None
        }
    }

    /// 检查模式是否与 haystack 的后面匹配。
    #[inline]
    fn is_suffix_of(self, haystack: &'a str) -> bool {
        haystack.as_bytes().ends_with(self.as_bytes())
    }

    /// 如果匹配，则从 haystack 的后面删除模式。
    #[inline]
    fn strip_suffix_of(self, haystack: &'a str) -> Option<&'a str> {
        if self.is_suffix_of(haystack) {
            let i = haystack.len() - self.as_bytes().len();
            // SAFETY: 后缀刚刚被验证为存在。
            unsafe { Some(haystack.get_unchecked(..i)) }
        } else {
            None
        }
    }
}

/////////////////////////////////////////////////////////////////////////////
// 两路子串搜索器
/////////////////////////////////////////////////////////////////////////////

#[derive(Clone, Debug)]
/// `<&str as Pattern<'a>>::Searcher` 的关联类型。
pub struct StrSearcher<'a, 'b> {
    haystack: &'a str,
    needle: &'b str,

    searcher: StrSearcherImpl,
}

#[derive(Clone, Debug)]
enum StrSearcherImpl {
    Empty(EmptyNeedle),
    TwoWay(TwoWaySearcher),
}

#[derive(Clone, Debug)]
struct EmptyNeedle {
    position: usize,
    end: usize,
    is_match_fw: bool,
    is_match_bw: bool,
    // 在 haystack 为空时需要，请参见 #85462
    is_finished: bool,
}

impl<'a, 'b> StrSearcher<'a, 'b> {
    fn new(haystack: &'a str, needle: &'b str) -> StrSearcher<'a, 'b> {
        if needle.is_empty() {
            StrSearcher {
                haystack,
                needle,
                searcher: StrSearcherImpl::Empty(EmptyNeedle {
                    position: 0,
                    end: haystack.len(),
                    is_match_fw: true,
                    is_match_bw: true,
                    is_finished: false,
                }),
            }
        } else {
            StrSearcher {
                haystack,
                needle,
                searcher: StrSearcherImpl::TwoWay(TwoWaySearcher::new(
                    needle.as_bytes(),
                    haystack.len(),
                )),
            }
        }
    }
}

unsafe impl<'a, 'b> Searcher<'a> for StrSearcher<'a, 'b> {
    #[inline]
    fn haystack(&self) -> &'a str {
        self.haystack
    }

    #[inline]
    fn next(&mut self) -> SearchStep {
        match self.searcher {
            StrSearcherImpl::Empty(ref mut searcher) => {
                if searcher.is_finished {
                    return SearchStep::Done;
                }
                // 空针拒绝每个字符并匹配它们之间的每个空字符串
                let is_match = searcher.is_match_fw;
                searcher.is_match_fw = !searcher.is_match_fw;
                let pos = searcher.position;
                match self.haystack[pos..].chars().next() {
                    _ if is_match => SearchStep::Match(pos, pos),
                    None => {
                        searcher.is_finished = true;
                        SearchStep::Done
                    }
                    Some(ch) => {
                        searcher.position += ch.len_utf8();
                        SearchStep::Reject(pos, searcher.position)
                    }
                }
            }
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                // TwoWaySearcher 会产生有效的 *Match* 索引，只要它能够正确匹配，并且在 char 边界处分割，并且 haystack 和 needle 是有效的 UTF-8 *Rejects* 可以落入任何索引，但是我们将手动将它们移至下一个字符边界，以便它们是 utf-8 安全的。
                //
                //
                //
                //
                if searcher.position == self.haystack.len() {
                    return SearchStep::Done;
                }
                let is_long = searcher.memory == usize::MAX;
                match searcher.next::<RejectAndMatch>(
                    self.haystack.as_bytes(),
                    self.needle.as_bytes(),
                    is_long,
                ) {
                    SearchStep::Reject(a, mut b) => {
                        // 跳到下一个字符边界
                        while !self.haystack.is_char_boundary(b) {
                            b += 1;
                        }
                        searcher.position = cmp::max(b, searcher.position);
                        SearchStep::Reject(a, b)
                    }
                    otherwise => otherwise,
                }
            }
        }
    }

    #[inline]
    fn next_match(&mut self) -> Option<(usize, usize)> {
        match self.searcher {
            StrSearcherImpl::Empty(..) => loop {
                match self.next() {
                    SearchStep::Match(a, b) => return Some((a, b)),
                    SearchStep::Done => return None,
                    SearchStep::Reject(..) => {}
                }
            },
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                let is_long = searcher.memory == usize::MAX;
                // 写出 `true` 和 `false` 的情况，以鼓励编译器分别专门处理这两种情况。
                //
                if is_long {
                    searcher.next::<MatchOnly>(
                        self.haystack.as_bytes(),
                        self.needle.as_bytes(),
                        true,
                    )
                } else {
                    searcher.next::<MatchOnly>(
                        self.haystack.as_bytes(),
                        self.needle.as_bytes(),
                        false,
                    )
                }
            }
        }
    }
}

unsafe impl<'a, 'b> ReverseSearcher<'a> for StrSearcher<'a, 'b> {
    #[inline]
    fn next_back(&mut self) -> SearchStep {
        match self.searcher {
            StrSearcherImpl::Empty(ref mut searcher) => {
                if searcher.is_finished {
                    return SearchStep::Done;
                }
                let is_match = searcher.is_match_bw;
                searcher.is_match_bw = !searcher.is_match_bw;
                let end = searcher.end;
                match self.haystack[..end].chars().next_back() {
                    _ if is_match => SearchStep::Match(end, end),
                    None => {
                        searcher.is_finished = true;
                        SearchStep::Done
                    }
                    Some(ch) => {
                        searcher.end -= ch.len_utf8();
                        SearchStep::Reject(searcher.end, end)
                    }
                }
            }
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                if searcher.end == 0 {
                    return SearchStep::Done;
                }
                let is_long = searcher.memory == usize::MAX;
                match searcher.next_back::<RejectAndMatch>(
                    self.haystack.as_bytes(),
                    self.needle.as_bytes(),
                    is_long,
                ) {
                    SearchStep::Reject(mut a, b) => {
                        // 跳到下一个字符边界
                        while !self.haystack.is_char_boundary(a) {
                            a -= 1;
                        }
                        searcher.end = cmp::min(a, searcher.end);
                        SearchStep::Reject(a, b)
                    }
                    otherwise => otherwise,
                }
            }
        }
    }

    #[inline]
    fn next_match_back(&mut self) -> Option<(usize, usize)> {
        match self.searcher {
            StrSearcherImpl::Empty(..) => loop {
                match self.next_back() {
                    SearchStep::Match(a, b) => return Some((a, b)),
                    SearchStep::Done => return None,
                    SearchStep::Reject(..) => {}
                }
            },
            StrSearcherImpl::TwoWay(ref mut searcher) => {
                let is_long = searcher.memory == usize::MAX;
                // 写出 `true` 和 `false`，例如 `next_match`
                if is_long {
                    searcher.next_back::<MatchOnly>(
                        self.haystack.as_bytes(),
                        self.needle.as_bytes(),
                        true,
                    )
                } else {
                    searcher.next_back::<MatchOnly>(
                        self.haystack.as_bytes(),
                        self.needle.as_bytes(),
                        false,
                    )
                }
            }
        }
    }
}

/// 双向子字符串搜索算法的内部状态。
#[derive(Clone, Debug)]
struct TwoWaySearcher {
    // constants
    /// 临界分解指数
    crit_pos: usize,
    /// 倒针的临界分解指数
    crit_pos_back: usize,
    period: usize,
    /// `byteset` 是一个扩展 (不是双向算法的一部分) ；
    /// 它是一个 64 位 "fingerprint"，其中每个设置位 `j` 对应于针中存在的 (字节 & 63) == j。
    ///
    byteset: u64,

    // variables
    position: usize,
    end: usize,
    /// 索引到我们已经匹配过的针
    memory: usize,
    /// 索引到针之后，我们已经匹配了
    memory_back: usize,
}

/*
    This is the Two-Way search algorithm, which was introduced in the paper:
    Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675.

    Here's some background information.

    A *word* is a string of symbols. The *length* of a word should be a familiar
    notion, and here we denote it for any word x by |x|.
    (We also allow for the possibility of the *empty word*, a word of length zero).

    If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be a
    *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == x[i+p].
    For example, both 1 and 2 are periods for the string "aa". As another example,
    the only period of the string "abcd" is 4.

    We denote by period(x) the *smallest* period of x (provided that x is non-empty).
    This is always well-defined since every non-empty word x has at least one period,
    |x|. We sometimes call this *the period* of x.

    If u, v and x are words such that x = uv, where uv is the concatenation of u and
    v, then we say that (u, v) is a *factorization* of x.

    Let (u, v) be a factorization for a word x. Then if w is a non-empty word such
    that both of the following hold

      - either w is a suffix of u or u is a suffix of w
      - either w is a prefix of v or v is a prefix of w

    then w is said to be a *repetition* for the factorization (u, v).

    Just to unpack this, there are four possibilities here. Let w = "abc". Then we
    might have:

      - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde")
      - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab")
      - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi")
      - u is a suffix of w and v is a prefix of w. ex: ("bc", "a")

    Note that the word vu is a repetition for any factorization (u,v) of x = uv,
    so every factorization has at least one repetition.

    If x is a string and (u, v) is a factorization for x, then a *local period* for
    (u, v) is an integer r such that there is some word w such that |w| = r and w is
    a repetition for (u, v).

    We denote by local_period(u, v) the smallest local period of (u, v). We sometimes
    call this *the local period* of (u, v). Provided that x = uv is non-empty, this
    is well-defined (because each non-empty word has at least one factorization, as
    noted above).

    It can be proven that the following is an equivalent definition of a local period
    for a factorization (u, v): any positive integer r such that x[i] == x[i+r] for
    all i such that |u| - r <= i <= |u| - 1 and such that both x[i] and x[i+r] are
    defined. (i.e., i > 0 and i + r < |x|).

    Using the above reformulation, it is easy to prove that

        1 <= local_period(u, v) <= period(uv)

    A factorization (u, v) of x such that local_period(u,v) = period(x) is called a
    *critical factorization*.

    The algorithm hinges on the following theorem, which is stated without proof:

    **Critical Factorization Theorem** Any word x has at least one critical
    factorization (u, v) such that |u| < period(x).

    The purpose of maximal_suffix is to find such a critical factorization.

    If the period is short, compute another factorization x = u' v' to use
    for reverse search, chosen instead so that |v'| < period(x).

*/
impl TwoWaySearcher {
    fn new(needle: &[u8], end: usize) -> TwoWaySearcher {
        let (crit_pos_false, period_false) = TwoWaySearcher::maximal_suffix(needle, false);
        let (crit_pos_true, period_true) = TwoWaySearcher::maximal_suffix(needle, true);

        let (crit_pos, period) = if crit_pos_false > crit_pos_true {
            (crit_pos_false, period_false)
        } else {
            (crit_pos_true, period_true)
        };

        // 关于发生的事情的特别可读的解释可以在 Crochemore 和 Rytter 的书 "Text Algorithms"，第 13 章中找到。
        // 具体看 "Algorithm CP" 的代码 p.
        // 323.
        //
        // 这是怎么回事，我们有一些关键的因数分解 (u，v)，我们想确定 u 是否为 & v [.. period] 的后缀。
        // 如果是这样，我们使用 "Algorithm CP1"。
        // 否则，我们将使用 "Algorithm CP2"，这是针对针的周期较大而优化的。
        //
        //
        if needle[..crit_pos] == needle[period..period + crit_pos] {
            // 短期情况下 - 周期是精确的，需要为倒针 x=u'v' 计算一个单独的临界分解，其中 | v'|<period(x)。
            //
            // 已知时期加快了这一进程。
            // 请注意，x= "acba" 之类的情况可以正好分解为因数 (crit_pos=1，期间 = 3)，而可以由近似的逆向因数 (crit_pos=2，期间 = 2) 进行分解。
            // 我们使用给定的逆因式分解，但要保留精确的周期。
            //
            //
            //
            //
            let crit_pos_back = needle.len()
                - cmp::max(
                    TwoWaySearcher::reverse_maximal_suffix(needle, period, false),
                    TwoWaySearcher::reverse_maximal_suffix(needle, period, true),
                );

            TwoWaySearcher {
                crit_pos,
                crit_pos_back,
                period,
                byteset: Self::byteset_create(&needle[..period]),

                position: 0,
                end,
                memory: 0,
                memory_back: needle.len(),
            }
        } else {
            // 长期情况 - 我们近似于实际时间，请勿使用记忆。
            //
            //
            // 通过下限 max(|u|, |v|) + 近似计算周期 1.
            // 临界分解有效地用于正向搜索和反向搜索。
            //

            TwoWaySearcher {
                crit_pos,
                crit_pos_back: crit_pos,
                period: cmp::max(crit_pos, needle.len() - crit_pos) + 1,
                byteset: Self::byteset_create(needle),

                position: 0,
                end,
                memory: usize::MAX, // 虚拟值表示周期长
                memory_back: usize::MAX,
            }
        }
    }

    #[inline]
    fn byteset_create(bytes: &[u8]) -> u64 {
        bytes.iter().fold(0, |a, &b| (1 << (b & 0x3f)) | a)
    }

    #[inline]
    fn byteset_contains(&self, byte: u8) -> bool {
        (self.byteset >> ((byte & 0x3f) as usize)) & 1 != 0
    }

    // `Two-Way` 的主要思想之一是，我们将针分解成两半 (u，v)，然后开始尝试通过从左到右扫描在 haystack 中查找 v。
    // 如果 v 匹配，我们尝试通过从右到左扫描来匹配 u。
    // 当我们遇到不匹配时，我们可以跳多远，这全都基于以下事实: (u，v) 是针的关键分解因数。
    //
    //
    #[inline]
    fn next<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
    where
        S: TwoWayStrategy,
    {
        // `next()` 使用 `self.position` 作为它的游标
        let old_pos = self.position;
        let needle_last = needle.len() - 1;
        'search: loop {
            // 如果我们假设切片以 isize 的范围为边界，请检查我们在位置上是否有空间可以搜索 + needle_last 不会溢出。
            //
            //
            let tail_byte = match haystack.get(self.position + needle_last) {
                Some(&b) => b,
                None => {
                    self.position = haystack.len();
                    return S::rejecting(old_pos, self.position);
                }
            };

            if S::use_early_reject() && old_pos != self.position {
                return S::rejecting(old_pos, self.position);
            }

            // 快速跳过与子字符串无关的大部分内容
            if !self.byteset_contains(tail_byte) {
                self.position += needle.len();
                if !long_period {
                    self.memory = 0;
                }
                continue 'search;
            }

            // 看看针的右边是否匹配
            let start =
                if long_period { self.crit_pos } else { cmp::max(self.crit_pos, self.memory) };
            for i in start..needle.len() {
                if needle[i] != haystack[self.position + i] {
                    self.position += i - self.crit_pos + 1;
                    if !long_period {
                        self.memory = 0;
                    }
                    continue 'search;
                }
            }

            // 看看针头的左部分是否匹配
            let start = if long_period { 0 } else { self.memory };
            for i in (start..self.crit_pos).rev() {
                if needle[i] != haystack[self.position + i] {
                    self.position += self.period;
                    if !long_period {
                        self.memory = needle.len() - self.period;
                    }
                    continue 'search;
                }
            }

            // 我们找到了一个匹配！
            let match_pos = self.position;

            // Note: 添加 `self.period` 而不是 `needle.len()` 以具有重叠的匹配项
            self.position += needle.len();
            if !long_period {
                self.memory = 0; // 设置为 `needle.len() - self.period` 进行重叠匹配
            }

            return S::matching(match_pos, match_pos + needle.len());
        }
    }

    // 遵循 `next()` 中的思想。
    //
    // 定义是对称的，period(x) = period(reverse(x)) 和 local_period(u, v) = local_period(reverse(v), reverse(u))，所以如果 (u, v) 是一个临界分解，那么 (reverse(v), reverse(u)) 也是。
    //
    //
    // 对于相反的情况，我们已经计算出临界分解系数 x=u'v' (字段 `crit_pos_back`)。我们需要 `|u| < period(x)` 对于前移情况，因此 `|v'| < period(x)` 反之。
    //
    // 为了通过 haystack 反向搜索，我们通过带有反向针的反向 haystack 向前搜索，首先匹配 u'，然后匹配 v'。
    //
    //
    //
    //
    #[inline]
    fn next_back<S>(&mut self, haystack: &[u8], needle: &[u8], long_period: bool) -> S::Output
    where
        S: TwoWayStrategy,
    {
        // `next_back()` 使用 `self.end` 作为它的游标 -- 因此 `next()` 和 `next_back()` 是独立的。
        //
        let old_end = self.end;
        'search: loop {
            // 检查我们是否有余地可以搜索 - needle.len() 在没有更多空间时会回绕，但是由于切片长度的限制，它永远无法回绕到 haystack 的长度。
            //
            //
            //
            let front_byte = match haystack.get(self.end.wrapping_sub(needle.len())) {
                Some(&b) => b,
                None => {
                    self.end = 0;
                    return S::rejecting(0, old_end);
                }
            };

            if S::use_early_reject() && old_end != self.end {
                return S::rejecting(self.end, old_end);
            }

            // 快速跳过与子字符串无关的大部分内容
            if !self.byteset_contains(front_byte) {
                self.end -= needle.len();
                if !long_period {
                    self.memory_back = needle.len();
                }
                continue 'search;
            }

            // 看看针头的左部分是否匹配
            let crit = if long_period {
                self.crit_pos_back
            } else {
                cmp::min(self.crit_pos_back, self.memory_back)
            };
            for i in (0..crit).rev() {
                if needle[i] != haystack[self.end - needle.len() + i] {
                    self.end -= self.crit_pos_back - i;
                    if !long_period {
                        self.memory_back = needle.len();
                    }
                    continue 'search;
                }
            }

            // 看看针的右边是否匹配
            let needle_end = if long_period { needle.len() } else { self.memory_back };
            for i in self.crit_pos_back..needle_end {
                if needle[i] != haystack[self.end - needle.len() + i] {
                    self.end -= self.period;
                    if !long_period {
                        self.memory_back = self.period;
                    }
                    continue 'search;
                }
            }

            // 我们找到了一个匹配！
            let match_pos = self.end - needle.len();
            // Note: 子 self.period 而不是 needle.len() 具有重叠的匹配项
            self.end -= needle.len();
            if !long_period {
                self.memory_back = needle.len();
            }

            return S::matching(match_pos, match_pos + needle.len());
        }
    }

    // 计算 `arr` 的最大后缀。
    //
    // 最大后缀是 `arr` 的可能的关键因式分解 (u，v)。
    //
    // 返回 (`i`, `p`)，其中 `i` 是 v 的起始索引，`p` 是 v 的周期 v.
    //
    // `order_greater` 确定词法顺序是 `<` 还是 `>`。
    // 必须计算两个阶数 - `i` 最大的阶数给出了关键的因式分解。
    //
    //
    // 对于长时间的情况，结果周期不精确 (太短)。
    //
    #[inline]
    fn maximal_suffix(arr: &[u8], order_greater: bool) -> (usize, usize) {
        let mut left = 0; // 对应论文中的 i
        let mut right = 1; // 对应论文 j
        let mut offset = 0; // 对应于论文中的 k，但从 0 开始
        // 匹配基于 0 的索引。
        let mut period = 1; // 对应于论文中的 p

        while let Some(&a) = arr.get(right + offset) {
            // 当 `right` 是时，`left` 将是入站的。
            let b = arr[left + offset];
            if (a < b && !order_greater) || (a > b && order_greater) {
                // 后缀较小，到目前为止是整个前缀。
                right += offset + 1;
                offset = 0;
                period = right - left;
            } else if a == b {
                // 通过重复当前期间前进。
                if offset + 1 == period {
                    right += offset + 1;
                    offset = 0;
                } else {
                    offset += 1;
                }
            } else {
                // 后缀较大，请从当前位置重新开始。
                left = right;
                right += 1;
                offset = 0;
                period = 1;
            }
        }
        (left, period)
    }

    // 计算 `arr` 倒数的最大后缀。
    //
    // 最大后缀是 `arr` 的可能的关键因式分解 (u'，v')。
    //
    // 从后面返回 `i`，其中 `i` 是 v' 的起始索引；
    // 到达 `known_period` 周期时立即返回。
    //
    // `order_greater` 确定词法顺序是 `<` 还是 `>`。
    // 必须计算两个阶数 - `i` 最大的阶数给出了关键的因式分解。
    //
    //
    // 对于长时间的情况，结果周期不精确 (太短)。
    fn reverse_maximal_suffix(arr: &[u8], known_period: usize, order_greater: bool) -> usize {
        let mut left = 0; // 对应论文中的 i
        let mut right = 1; // 对应论文 j
        let mut offset = 0; // 对应于论文中的 k，但从 0 开始
        // 匹配基于 0 的索引。
        let mut period = 1; // 对应于论文中的 p
        let n = arr.len();

        while right + offset < n {
            let a = arr[n - (1 + right + offset)];
            let b = arr[n - (1 + left + offset)];
            if (a < b && !order_greater) || (a > b && order_greater) {
                // 后缀较小，到目前为止是整个前缀。
                right += offset + 1;
                offset = 0;
                period = right - left;
            } else if a == b {
                // 通过重复当前期间前进。
                if offset + 1 == period {
                    right += offset + 1;
                    offset = 0;
                } else {
                    offset += 1;
                }
            } else {
                // 后缀较大，请从当前位置重新开始。
                left = right;
                right += 1;
                offset = 0;
                period = 1;
            }
            if period == known_period {
                break;
            }
        }
        debug_assert!(period <= known_period);
        left
    }
}

// TwoWayStrategy 允许该算法尽可能快地跳过不匹配项，或者以相对较快地发出 `reject` 的模式下工作。
//
trait TwoWayStrategy {
    type Output;
    fn use_early_reject() -> bool;
    fn rejecting(a: usize, b: usize) -> Self::Output;
    fn matching(a: usize, b: usize) -> Self::Output;
}

/// 跳过以尽快匹配间隔
enum MatchOnly {}

impl TwoWayStrategy for MatchOnly {
    type Output = Option<(usize, usize)>;

    #[inline]
    fn use_early_reject() -> bool {
        false
    }
    #[inline]
    fn rejecting(_a: usize, _b: usize) -> Self::Output {
        None
    }
    #[inline]
    fn matching(a: usize, b: usize) -> Self::Output {
        Some((a, b))
    }
}

/// 定期发出拒绝
enum RejectAndMatch {}

impl TwoWayStrategy for RejectAndMatch {
    type Output = SearchStep;

    #[inline]
    fn use_early_reject() -> bool {
        true
    }
    #[inline]
    fn rejecting(a: usize, b: usize) -> Self::Output {
        SearchStep::Reject(a, b)
    }
    #[inline]
    fn matching(a: usize, b: usize) -> Self::Output {
        SearchStep::Match(a, b)
    }
}

/// SIMD 搜索短针基于 Wojciech Muła 的 `SIMD-friendly algorithms for substring searching`[0]
///
/// 它通过探测整个 vector 宽度的针的第一个和最后一个字节，在每次迭代中跳过 vector 宽度 (而不是像双向那样的针长度)，并且仅在矢量化探针指示潜在匹配时才进行完整的针比较.
///
///
/// 由于 x86_64 基线只提供 SSE2，我们在这里只使用 u8x16。
/// 如果我们为 x86-64-v3 发布 std 或将其改编为其他平台，则应评估更宽的 vectors。
///
/// 对于小于 vector-size + needle length 的干草堆，它会回落到一个简单的 O(n*m) 搜索，所以这个实现不应该在更大的 needle 上调用。
///
/// [0]: http://0x80.pl/articles/simd-strfind.html#sse-avx2
///
///
///
///
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
#[inline]
fn simd_contains(needle: &str, haystack: &str) -> Option<bool> {
    let needle = needle.as_bytes();
    let haystack = haystack.as_bytes();

    debug_assert!(needle.len() > 1);

    use crate::ops::BitAnd;
    use crate::simd::mask8x16 as Mask;
    use crate::simd::u8x16 as Block;
    use crate::simd::{SimdPartialEq, ToBitMask};

    let first_probe = needle[0];
    let last_byte_offset = needle.len() - 1;

    // 用于第二个 vector 的偏移量
    let second_probe_offset = if needle.len() == 2 {
        // 永远不要放弃 len=2 针，因为探针将完全覆盖它们并且没有退化的情况。
        //
        1
    } else {
        // 尝试几个字节以防针的第一个和最后一个字节相同
        let Some(second_probe_offset) = (needle.len().saturating_sub(4)..needle.len()).rfind(|&idx| needle[idx] != first_probe) else {
            // 如果我们找不到任何不同的字节，则回退到其他搜索方法，否则我们可能会遇到一些退化的情况
            //
            return None;
        };
        second_probe_offset
    };

    // 如果 haystack 太小而不适合，则进行简单搜索
    if haystack.len() < Block::LANES + last_byte_offset {
        return Some(haystack.windows(needle.len()).any(|c| c == needle));
    }

    let first_probe: Block = Block::splat(first_probe);
    let second_probe: Block = Block::splat(needle[second_probe_offset]);
    // 第一个字节已经被外循环检查过。
    // 要验证匹配，只需比较余数。
    let trimmed_needle = &needle[1..];

    // 这个 #[cold] 是承重的，拆之前做 benchmark...
    let check_mask = #[cold]
    |idx, mask: u16, skip: bool| -> bool {
        if skip {
            return false;
        }

        // 这也是。优化很奇怪。
        let mut mask = mask;

        while mask != 0 {
            let trailing = mask.trailing_zeros();
            let offset = idx + trailing as usize + 1;
            // SAFETY: 掩码在 0 到 15 个尾随零之间，我们跳过一个已经比较过的额外字节，然后取 trimmed_needle.len() 字节。
            // 这是在外循环定义的范围内
            unsafe {
                let sub = haystack.get_unchecked(offset..).get_unchecked(..trimmed_needle.len());
                if small_slice_eq(sub, trimmed_needle) {
                    return true;
                }
            }
            mask &= !(1 << trailing);
        }
        return false;
    };

    let test_chunk = |idx| -> u16 {
        // SAFETY: 这需要至少 LANES 字节在 idx 处可读，这是由循环范围确保的 (见下面的评论)
        //
        let a: Block = unsafe { haystack.as_ptr().add(idx).cast::<Block>().read_unaligned() };
        // SAFETY: 这需要 LANES + block_offset 字节在 idx 处可读
        let b: Block = unsafe {
            haystack.as_ptr().add(idx).add(second_probe_offset).cast::<Block>().read_unaligned()
        };
        let eq_first: Mask = a.simd_eq(first_probe);
        let eq_last: Mask = b.simd_eq(second_probe);
        let both = eq_first.bitand(eq_last);
        let mask = both.to_bitmask();

        return mask;
    };

    let mut i = 0;
    let mut result = false;
    // 循环条件必须确保有足够的余量来读取 LANE 字节，不仅在当前索引处，而且在由 block_offset 移动的索引处
    //
    const UNROLL: usize = 4;
    while i + last_byte_offset + UNROLL * Block::LANES < haystack.len() && !result {
        let mut masks = [0u16; UNROLL];
        for j in 0..UNROLL {
            masks[j] = test_chunk(i + j * Block::LANES);
        }
        for j in 0..UNROLL {
            let mask = masks[j];
            if mask != 0 {
                result |= check_mask(i + j * Block::LANES, mask, result);
            }
        }
        i += UNROLL * Block::LANES;
    }
    while i + last_byte_offset + Block::LANES < haystack.len() && !result {
        let mask = test_chunk(i);
        if mask != 0 {
            result |= check_mask(i, mask, result);
        }
        i += Block::LANES;
    }

    // 处理不适合 LANES 大小步骤的尾巴。
    // 这只是重复相同的过程，但作为右对齐块而不是左对齐块。
    // 最后一个字节必须与字符串结尾完全齐平，这样我们就不会错过任何一个字节或读取越界。
    //
    let i = haystack.len() - last_byte_offset - Block::LANES;
    let mask = test_chunk(i);
    if mask != 0 {
        result |= check_mask(i, mask, result);
    }

    Some(result)
}

/// 比较短切片是否相等。
///
/// 它避免了对 libc 的 memcmp 的调用，由于 SIMD 优化，它在长切片上速度更快，但它会产生调用开销。
///
///
/// # Safety
///
/// 两个切片必须具有相同的长度。
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))] // 只调用 x86
#[inline]
unsafe fn small_slice_eq(x: &[u8], y: &[u8]) -> bool {
    debug_assert_eq!(x.len(), y.len());
    // 这个函数改编自
    // https://github.com/BurntSushi/memchr/blob/8037d11b4357b0f07be2bb66dc2659d9cf28ad32/src/memmem/util.rs#L32

    // 如果我们没有足够的字节来一次加载 4 个字节，则回退到原始的慢速版本。
    //
    //
    // 可能的替代方案: 我们可以将 copy_nonoverlapping 与掩码而不是循环结合使用。
    // 对其进行基准测试。
    if x.len() < 4 {
        for (&b1, &b2) in x.iter().zip(y) {
            if b1 != b2 {
                return false;
            }
        }
        return true;
    }
    // 当我们有 4 个或更多字节要比较时，然后使用未对齐的加载一次以 4 个为一组进行。
    //
    // 另外，为什么加载 4 字节而不是 8 字节? 原因是这个特定版本的 memcmp 很可能会被调用。
    // 这意味着，如果我们执行 8 字节加载，则更高比例的 memcmp 调用将使用上面较慢的变体。
    // 话虽如此，这只是一个假设，仅得到基准的松散支持。
    // 这里可能会有一些改进。
    // 不过，这里的主要内容是优化延迟，而不是吞吐量。
    //
    //
    //

    // SAFETY: 通过上面的条件，我们知道 `px` 和 `py` 的长度相同，所以 `px < pxend` 意味着 `py < pyend`。
    //
    // 因此，在下面的循环中解释 `px` 和 `py` 都是安全的。
    //
    // 此外，我们将 `pxend` 和 `pyend` 设置为 `px` 和 `py` 实际结束之前的 4 个字节。
    // 因此，保证循环外的最终解引是有效的。
    // (最后的比较将与在循环中对不是四的倍数的长度进行的最后比较重叠。)
    //
    // 最后，我们不必担心这里的对齐问题，因为我们进行的是未对齐的加载。
    //
    //
    //
    unsafe {
        let (mut px, mut py) = (x.as_ptr(), y.as_ptr());
        let (pxend, pyend) = (px.add(x.len() - 4), py.add(y.len() - 4));
        while px < pxend {
            let vx = (px as *const u32).read_unaligned();
            let vy = (py as *const u32).read_unaligned();
            if vx != vy {
                return false;
            }
            px = px.add(4);
            py = py.add(4);
        }
        let vx = (pxend as *const u32).read_unaligned();
        let vy = (pyend as *const u32).read_unaligned();
        vx == vy
    }
}