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

/// 同时迭代其他两个迭代器的迭代器。
///
/// 这个 `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
///
/// ```
/// #![feature(iter_zip)]
/// use std::iter::zip;
///
/// let xs = [1, 2, 3];
/// let ys = [4, 5, 6];
/// for (x, y) in zip(&xs, &ys) {
///     println!("x:{}, y:{}", x, y);
/// }
///
/// // 嵌套 zip 也可以:
/// let zs = [7, 8, 9];
/// for ((x, y), z) in zip(zip(&xs, &ys), &zs) {
///     println!("x:{}, y:{}, z:{}", x, y, z);
/// }
/// ```
#[unstable(feature = "iter_zip", issue = "83574")]
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]
    #[doc(hidden)]
    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
    where
        Self: TrustedRandomAccess,
    {
        // 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 + TrustedRandomAccess;
}

// 通用 Zip 实现
#[doc(hidden)]
impl<A, B> ZipImpl<A, B> for Zip<A, B>
where
    A: Iterator,
    B: Iterator,
{
    type Item = (A::Item, B::Item);
    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,
    {
        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!(),
        }
    }

    #[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: TrustedRandomAccess,
    {
        unreachable!("Always specialized");
    }
}

#[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
        }
    }

    #[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)) }
    }
}

#[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,
{
    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,
{
}

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

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

#[unstable(issue = "none", feature = "inplace_iteration")]
// 限制于以下项: 复制，因为不清楚 Zip 对 TrustedRandomAccess 的使用与源的 Drop 实现之间的交互。
//
// 另一种方法返回源已被逻辑高级化的次数 (需要调用 next()) 才能正确丢弃源的其余部分。
//
//
unsafe impl<A: InPlaceIterable, B: Iterator> InPlaceIterable for Zip<A, B> where A::Item: Copy {}

#[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 + TrustedRandomAccess, B: Debug + TrustedRandomAccess> 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` 必须精确且调用便宜。
///
/// `size` 可能不会被覆盖。
///
/// `<Self as Iterator>::__iterator_get_unchecked` 在满足以下条件的情况下必须安全。
///
/// 1. `0 <= idx` 和 `idx < self.size()`。
/// 2. 如果是 `self: !Clone`，则永远不会在 `self` 上使用相同的索引多次调用 `get_unchecked`。
/// 3. 调用 `self.get_unchecked(idx)` 之后，最多只会调用 `self.size() - idx - 1` 次 `next_back`。
/// 4. 调用 `get_unchecked` 之后，将仅在 `self` 上调用以下方法:
///     * `std::clone::Clone::clone()`
///     * `std::iter::Iterator::size_hint()`
///     * `std::iter::DoubleEndedIterator::next_back()`
///     * `std::iter::Iterator::__iterator_get_unchecked()`
///     * `std::iter::TrustedRandomAccess::size()`
///
/// 此外，考虑到这些条件，它必须保证:
///
/// * 它不会更改从 `size_hint` 返回的值
/// * 假设已实现所需的 traits，则在调用 `get_unchecked` 之后在 `self` 上调用上面列出的方法必须是安全的。
///
/// * 调用 `get_unchecked` 后丢弃 `self` 也必须是安全的。
///
///
///
///
#[doc(hidden)]
#[unstable(feature = "trusted_random_access", issue = "none")]
#[rustc_specialization_trait]
pub unsafe trait TrustedRandomAccess: 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)]
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 + TrustedRandomAccess> SpecTrustedRandomAccess for I {
    unsafe fn try_get_unchecked(&mut self, index: usize) -> Self::Item {
        // SAFETY: 调用者必须遵守 `Iterator::__iterator_get_unchecked` 的契约。
        //
        unsafe { self.__iterator_get_unchecked(index) }
    }
}