use crate::cmp;
use crate::fmt::{self, Debug};
use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator};
use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator};

/// 同时迭代其他两个迭代器的迭代器。
///
/// 这个 `struct` 是由 [`zip`] 或 [`Iterator::zip`] 创建的。
/// 有关更多信息，请参见他们的文档。
#[derive(Clone)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Zip<A, B> {
    a: A,
    b: B,
    // index，len 和 a_len 仅由 zip 的专用版本使用
    index: usize,
    len: usize,
    a_len: usize,
}
impl<A: Iterator, B: Iterator> Zip<A, B> {
    pub(in crate::iter) fn new(a: A, b: B) -> Zip<A, B> {
        ZipImpl::new(a, b)
    }
    fn super_nth(&mut self, mut n: usize) -> Option<(A::Item, B::Item)> {
        while let Some(x) = Iterator::next(self) {
            if n == 0 {
                return Some(x);
            }
            n -= 1;
        }
        None
    }
}

/// 将参数转换为迭代器并压缩它们。
///
/// 有关更多信息，请参见 [`Iterator::zip`] 的文档。
///
/// # Examples
///
/// ```
/// use std::iter::zip;
///
/// let xs = [1, 2, 3];
/// let ys = [4, 5, 6];
///
/// let mut iter = zip(xs, ys);
///
/// assert_eq!(iter.next().unwrap(), (1, 4));
/// assert_eq!(iter.next().unwrap(), (2, 5));
/// assert_eq!(iter.next().unwrap(), (3, 6));
/// assert!(iter.next().is_none());
///
/// // 嵌套 zip 也可以：
/// let zs = [7, 8, 9];
///
/// let mut iter = zip(zip(xs, ys), zs);
///
/// assert_eq!(iter.next().unwrap(), ((1, 4), 7));
/// assert_eq!(iter.next().unwrap(), ((2, 5), 8));
/// assert_eq!(iter.next().unwrap(), ((3, 6), 9));
/// assert!(iter.next().is_none());
/// ```
#[stable(feature = "iter_zip", since = "1.59.0")]
pub fn zip<A, B>(a: A, b: B) -> Zip<A::IntoIter, B::IntoIter>
where
    A: IntoIterator,
    B: IntoIterator,
{
    ZipImpl::new(a.into_iter(), b.into_iter())
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> Iterator for Zip<A, B>
where
    A: Iterator,
    B: Iterator,
{
    type Item = (A::Item, B::Item);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        ZipImpl::next(self)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        ZipImpl::size_hint(self)
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        ZipImpl::nth(self, n)
    }

    #[inline]
    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
    where
        Self: TrustedRandomAccessNoCoerce,
    {
        // SAFETY: `ZipImpl::__iterator_get_unchecked` 与 `Iterator::__iterator_get_unchecked` 具有相同的安全要求。
        //
        unsafe { ZipImpl::get_unchecked(self, idx) }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> DoubleEndedIterator for Zip<A, B>
where
    A: DoubleEndedIterator + ExactSizeIterator,
    B: DoubleEndedIterator + ExactSizeIterator,
{
    #[inline]
    fn next_back(&mut self) -> Option<(A::Item, B::Item)> {
        ZipImpl::next_back(self)
    }
}

// Zip 专用 trait
#[doc(hidden)]
trait ZipImpl<A, B> {
    type Item;
    fn new(a: A, b: B) -> Self;
    fn next(&mut self) -> Option<Self::Item>;
    fn size_hint(&self) -> (usize, Option<usize>);
    fn nth(&mut self, n: usize) -> Option<Self::Item>;
    fn next_back(&mut self) -> Option<Self::Item>
    where
        A: DoubleEndedIterator + ExactSizeIterator,
        B: DoubleEndedIterator + ExactSizeIterator;
    // 与 `Iterator::__iterator_get_unchecked` 具有相同的安全要求
    unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item
    where
        Self: Iterator + TrustedRandomAccessNoCoerce;
}

// 解决专业化的限制，要求在中间实现中重复 `default` 实现。
//
macro_rules! zip_impl_general_defaults {
    () => {
        default fn new(a: A, b: B) -> Self {
            Zip {
                a,
                b,
                index: 0, // unused
                len: 0,   // unused
                a_len: 0, // unused
            }
        }

        #[inline]
        default fn next(&mut self) -> Option<(A::Item, B::Item)> {
            let x = self.a.next()?;
            let y = self.b.next()?;
            Some((x, y))
        }

        #[inline]
        default fn nth(&mut self, n: usize) -> Option<Self::Item> {
            self.super_nth(n)
        }

        #[inline]
        default fn next_back(&mut self) -> Option<(A::Item, B::Item)>
        where
            A: DoubleEndedIterator + ExactSizeIterator,
            B: DoubleEndedIterator + ExactSizeIterator,
        {
            // 下面的函数体只使用 `self.a/b.len()` 和 `self.a/b.next_back()`，并不会经常调用 `next_back`，所以这个实现在 `TrustedRandomAccessNoCoerce` 专业化中是安全的
            //
            //

            let a_sz = self.a.len();
            let b_sz = self.b.len();
            if a_sz != b_sz {
                // 将 a，b 调整为相等的长度
                if a_sz > b_sz {
                    for _ in 0..a_sz - b_sz {
                        self.a.next_back();
                    }
                } else {
                    for _ in 0..b_sz - a_sz {
                        self.b.next_back();
                    }
                }
            }
            match (self.a.next_back(), self.b.next_back()) {
                (Some(x), Some(y)) => Some((x, y)),
                (None, None) => None,
                _ => unreachable!(),
            }
        }
    };
}

// 通用 Zip 实现
#[doc(hidden)]
impl<A, B> ZipImpl<A, B> for Zip<A, B>
where
    A: Iterator,
    B: Iterator,
{
    type Item = (A::Item, B::Item);

    zip_impl_general_defaults! {}

    #[inline]
    default fn size_hint(&self) -> (usize, Option<usize>) {
        let (a_lower, a_upper) = self.a.size_hint();
        let (b_lower, b_upper) = self.b.size_hint();

        let lower = cmp::min(a_lower, b_lower);

        let upper = match (a_upper, b_upper) {
            (Some(x), Some(y)) => Some(cmp::min(x, y)),
            (Some(x), None) => Some(x),
            (None, Some(y)) => Some(y),
            (None, None) => None,
        };

        (lower, upper)
    }

    default unsafe fn get_unchecked(&mut self, _idx: usize) -> <Self as Iterator>::Item
    where
        Self: TrustedRandomAccessNoCoerce,
    {
        unreachable!("Always specialized");
    }
}

#[doc(hidden)]
impl<A, B> ZipImpl<A, B> for Zip<A, B>
where
    A: TrustedRandomAccessNoCoerce + Iterator,
    B: TrustedRandomAccessNoCoerce + Iterator,
{
    zip_impl_general_defaults! {}

    #[inline]
    default fn size_hint(&self) -> (usize, Option<usize>) {
        let size = cmp::min(self.a.size(), self.b.size());
        (size, Some(size))
    }

    #[inline]
    unsafe fn get_unchecked(&mut self, idx: usize) -> <Self as Iterator>::Item {
        let idx = self.index + idx;
        // SAFETY: 调用者必须遵守 `Iterator::__iterator_get_unchecked` 的契约。
        //
        unsafe { (self.a.__iterator_get_unchecked(idx), self.b.__iterator_get_unchecked(idx)) }
    }
}

#[doc(hidden)]
impl<A, B> ZipImpl<A, B> for Zip<A, B>
where
    A: TrustedRandomAccess + Iterator,
    B: TrustedRandomAccess + Iterator,
{
    fn new(a: A, b: B) -> Self {
        let a_len = a.size();
        let len = cmp::min(a_len, b.size());
        Zip { a, b, index: 0, len, a_len }
    }

    #[inline]
    fn next(&mut self) -> Option<(A::Item, B::Item)> {
        if self.index < self.len {
            let i = self.index;
            // 由于 get_unchecked 执行可以 panic 的代码，因此我们事先增加了计数器，以便不会按照 TrustedRandomAccess 的要求访问相同的索引两次
            //
            self.index += 1;
            // SAFETY: `i` 小于 `self.len`，因此小于 `self.a.len()` 和 `self.b.len()`
            unsafe {
                Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
            }
        } else if A::MAY_HAVE_SIDE_EFFECT && self.index < self.a_len {
            let i = self.index;
            // 如上所述，在执行可能 panic 的代码之前递增
            self.index += 1;
            self.len += 1;
            // 匹配基本实现的潜在副作用
            // SAFETY: 我们只是检查 `i` <`self.a.len()`
            unsafe {
                self.a.__iterator_get_unchecked(i);
            }
            None
        } else {
            None
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.len - self.index;
        (len, Some(len))
    }

    #[inline]
    fn nth(&mut self, n: usize) -> Option<Self::Item> {
        let delta = cmp::min(n, self.len - self.index);
        let end = self.index + delta;
        while self.index < end {
            let i = self.index;
            // 由于 get_unchecked 执行可以 panic 的代码，因此我们事先增加了计数器，以便不会按照 TrustedRandomAccess 的要求访问相同的索引两次
            //
            self.index += 1;
            if A::MAY_HAVE_SIDE_EFFECT {
                // SAFETY: 使用 `cmp::min` 计算 `delta` 可确保 `end` 小于或等于 `self.len`，因此 `i` 也小于 `self.len`。
                //
                //
                unsafe {
                    self.a.__iterator_get_unchecked(i);
                }
            }
            if B::MAY_HAVE_SIDE_EFFECT {
                // SAFETY: 与上述相同。
                unsafe {
                    self.b.__iterator_get_unchecked(i);
                }
            }
        }

        self.super_nth(n - delta)
    }

    #[inline]
    fn next_back(&mut self) -> Option<(A::Item, B::Item)>
    where
        A: DoubleEndedIterator + ExactSizeIterator,
        B: DoubleEndedIterator + ExactSizeIterator,
    {
        if A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT {
            let sz_a = self.a.size();
            let sz_b = self.b.size();
            // 将 a，b 调整为相等的长度，确保只有 `next_back` 的第一个调用能够做到这一点，否则在调用 `get_unchecked()` 之后，我们将打破对 `self.next_back()` 的调用限制。
            //
            //
            if sz_a != sz_b {
                let sz_a = self.a.size();
                if A::MAY_HAVE_SIDE_EFFECT && sz_a > self.len {
                    for _ in 0..sz_a - self.len {
                        // 由于 next_back() 可能 panic 我们预先增加计数器以保持 Zip 的状态与底层迭代器源同步
                        //
                        self.a_len -= 1;
                        self.a.next_back();
                    }
                    debug_assert_eq!(self.a_len, self.len);
                }
                let sz_b = self.b.size();
                if B::MAY_HAVE_SIDE_EFFECT && sz_b > self.len {
                    for _ in 0..sz_b - self.len {
                        self.b.next_back();
                    }
                }
            }
        }
        if self.index < self.len {
            // 由于 get_unchecked 执行可以 panic 的代码，因此我们事先增加了计数器，以便不会按照 TrustedRandomAccess 的要求访问相同的索引两次
            //
            self.len -= 1;
            self.a_len -= 1;
            let i = self.len;
            // SAFETY: `i` 小于 `self.len` 的前一个值，该值也小于或等于 `self.a.len()` 和 `self.b.len()`
            //
            unsafe {
                Some((self.a.__iterator_get_unchecked(i), self.b.__iterator_get_unchecked(i)))
            }
        } else {
            None
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> ExactSizeIterator for Zip<A, B>
where
    A: ExactSizeIterator,
    B: ExactSizeIterator,
{
}

#[doc(hidden)]
#[unstable(feature = "trusted_random_access", issue = "none")]
unsafe impl<A, B> TrustedRandomAccess for Zip<A, B>
where
    A: TrustedRandomAccess,
    B: TrustedRandomAccess,
{
}

#[doc(hidden)]
#[unstable(feature = "trusted_random_access", issue = "none")]
unsafe impl<A, B> TrustedRandomAccessNoCoerce for Zip<A, B>
where
    A: TrustedRandomAccessNoCoerce,
    B: TrustedRandomAccessNoCoerce,
{
    const MAY_HAVE_SIDE_EFFECT: bool = A::MAY_HAVE_SIDE_EFFECT || B::MAY_HAVE_SIDE_EFFECT;
}

#[stable(feature = "fused", since = "1.26.0")]
impl<A, B> FusedIterator for Zip<A, B>
where
    A: FusedIterator,
    B: FusedIterator,
{
}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<A, B> TrustedLen for Zip<A, B>
where
    A: TrustedLen,
    B: TrustedLen,
{
}

impl<A, B> UncheckedIterator for Zip<A, B>
where
    A: UncheckedIterator,
    B: UncheckedIterator,
{
}

// 任意选择 zip 迭代的左侧作为可提取的 "source"，这将需要负 trait bounds 才能尝试
//
#[unstable(issue = "none", feature = "inplace_iteration")]
unsafe impl<A, B> SourceIter for Zip<A, B>
where
    A: SourceIter,
{
    type Source = A::Source;

    #[inline]
    unsafe fn as_inner(&mut self) -> &mut A::Source {
        // SAFETY: 将不安全的函数转发到具有相同要求的不安全的函数
        unsafe { SourceIter::as_inner(&mut self.a) }
    }
}

// 由于 SourceIter 转发到了左侧，所以我们在这里也这样做
#[unstable(issue = "none", feature = "inplace_iteration")]
unsafe impl<A: InPlaceIterable, B: Iterator> InPlaceIterable for Zip<A, B> {}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A: Debug, B: Debug> Debug for Zip<A, B> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        ZipFmt::fmt(self, f)
    }
}

trait ZipFmt<A, B> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result;
}

impl<A: Debug, B: Debug> ZipFmt<A, B> for Zip<A, B> {
    default fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Zip").field("a", &self.a).field("b", &self.b).finish()
    }
}

impl<A: Debug + TrustedRandomAccessNoCoerce, B: Debug + TrustedRandomAccessNoCoerce> ZipFmt<A, B>
    for Zip<A, B>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // 在包含的迭代器上调用 fmt 是 *not 安全的*，因为一旦我们开始迭代，它们就处于奇怪的，可能不安全的状态。
        //
        f.debug_struct("Zip").finish()
    }
}

/// 一个迭代器，其项可以有效随机访问
///
/// # Safety
///
/// 迭代器的 `size_hint` 必须精确且调用便宜。
///
/// `TrustedRandomAccessNoCoerce::size` 不能被覆盖。
///
/// `Self` 的所有子类型和所有超类型也必须实现 `TrustedRandomAccess`。
/// 特别是，这意味着具有非不变参数的类型通常不能具有依赖于此类参数上的任何 trait bounds 的 `TrustedRandomAccess` 的 impl，除了来自相应 struct/enum 定义本身的边界，或涉及 traits 本身的边界与此类似的保证。
///
///
/// 如果 `Self: ExactSizeIterator` 则 `self.len()` 必须始终产生与 `self.size()` 一致的结果。
///
/// 如果是 `Self: Iterator`，那么只要满足以下条件，`<Self as Iterator>::__iterator_get_unchecked(&mut self, idx)` 就必须是安全的调用。
///
/// 1. `0 <= idx` 和 `idx < self.size()`。
/// 2. 如果是 `Self: !Clone`，则 `self.__iterator_get_unchecked(idx)` 永远不会在 `self` 上使用相同的索引多次调用。
/// 3. `self.__iterator_get_unchecked(idx)` 被调用后，`self.next_back()` 最多只会被调用 `self.size() - idx - 1` 次。
/// 如果克隆 `Self: Clone` 和 `self`，则分别为 `self` 及其克隆计算此数字，但 `self.next_back()` 调用发生在 `self` 和克隆的克隆计数之前。
/// 4. 调用 `self.__iterator_get_unchecked(idx)` 后，将仅在 `self` 或 `self` 的任何新克隆上调用以下方法：
///     * `std::clone::Clone::clone`
///     * `std::iter::Iterator::size_hint`
///     * `std::iter::DoubleEndedIterator::next_back`
///     * `std::iter::ExactSizeIterator::len`
///     * `std::iter::Iterator::__iterator_get_unchecked`
///     * `std::iter::TrustedRandomAccessNoCoerce::size`
/// 5. 如果 `T` 是 `Self` 的子类型，则允许将 `self` 强制转换为 `T`。如果在 `self.__iterator_get_unchecked(idx)` 已经被调用之后 `self` 被强制为 `T`，那么除了 4. 也可以在 `T` 类型的结果值上调用。允许多个这样的强制步骤。
///    关于 2. 和 3.，在 `self` 上调用 `__iterator_get_unchecked(idx)` 或 `next_back()` 的次数和 `T` 类型的结果值 (以及子子类型的进一步强制结果) 相加，它们的总和不得超过指定的界限。
///
/// 此外，考虑到这些条件，它必须保证：
///
/// * 它不会更改从 `size_hint` 返回的值
/// * 假设实现了所需的 traits，在调用 `self.__iterator_get_unchecked(idx)` 后，在 `self` 上调用上面列出的方法必须是安全的。
/// * 调用 `self.__iterator_get_unchecked(idx)` 后丢弃 `self` 也必须是安全的。
/// * 如果 `T` 是 `Self` 的子类型，那么将 `self` 强制转换为 `T` 必须是安全的。
///
///
///
///
///
///
///
///
///
///
///
///
///
///
// FIXME: 阐明与 SourceIter/InPlaceIterable 的交互。
// 应该允许在 `__iterator_get_unchecked` 之后调用 `SourceIter::as_inner`。
//
#[doc(hidden)]
#[unstable(feature = "trusted_random_access", issue = "none")]
#[rustc_specialization_trait]
pub unsafe trait TrustedRandomAccess: TrustedRandomAccessNoCoerce {}

/// 与 [`TrustedRandomAccess`] 类似，但没有任何要求 / 保证对 `__iterator_get_unchecked` 之后的子类型进行强制转换 (这里不允许！)，并且没有子类型 / 超类型实现 `TrustedRandomAccessNoCoerce` 的要求。
///
///
/// 这个 trait 是在 PR #85874 中创建的，以修复 issue #85873 的健全性而不会出现性能回归。
/// 它可能会发生变化，因为我们可能想要构建一个更普遍有用 (用于性能优化) 和更复杂的 trait 或 trait 层次结构来替换或扩展 [`TrustedRandomAccess`] 和 `TrustedRandomAccessNoCoerce`。
///
///
///
#[doc(hidden)]
#[unstable(feature = "trusted_random_access", issue = "none")]
#[rustc_specialization_trait]
pub unsafe trait TrustedRandomAccessNoCoerce: Sized {
    // 方便的方法。
    fn size(&self) -> usize
    where
        Self: Iterator,
    {
        self.size_hint().0
    }
    /// `true` 如果获取迭代器元素可能有副作用。
    /// 记住要考虑内部迭代器。
    const MAY_HAVE_SIDE_EFFECT: bool;
}

/// 类似于 `Iterator::__iterator_get_unchecked`，但不需要编译器知道 `U: TrustedRandomAccess`。
///
///
/// ## Safety
///
/// 相同的要求直接调用 `get_unchecked`。
#[doc(hidden)]
#[inline]
pub(in crate::iter::adapters) unsafe fn try_get_unchecked<I>(it: &mut I, idx: usize) -> I::Item
where
    I: Iterator,
{
    // SAFETY: 调用者必须遵守 `Iterator::__iterator_get_unchecked` 的契约。
    //
    unsafe { it.try_get_unchecked(idx) }
}

unsafe trait SpecTrustedRandomAccess: Iterator {
    /// 如果是 `Self: TrustedRandomAccess`，调用 `Iterator::__iterator_get_unchecked(self, index)` 一定是安全的。
    ///
    unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item;
}

unsafe impl<I: Iterator> SpecTrustedRandomAccess for I {
    default unsafe fn try_get_unchecked(&mut self, _: usize) -> Self::Item {
        panic!("Should only be called on TrustedRandomAccess iterators");
    }
}

unsafe impl<I: Iterator + TrustedRandomAccessNoCoerce> SpecTrustedRandomAccess for I {
    #[inline]
    unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
        // SAFETY: 调用者必须遵守 `Iterator::__iterator_get_unchecked` 的契约。
        //
        unsafe { self.__iterator_get_unchecked(index) }
    }
}