//! 切片的迭代器使用的宏。

// 当 T 是 ZST 时收缩迭代器，将长度设置为 `new_len`。
// `new_len` 不得超过 `self.len()`。
macro_rules! zst_set_len {
    ($self: ident, $new_len: expr) => {{
        #![allow(unused_unsafe)] // 我们有时会在不安全的区域内使用

        // SAFETY: 和 `invalid(_mut)` 一样，但是宏不知道调用那个函数的哪个版本，所以开码。
        //
        $self.end = unsafe { mem::transmute::<usize, _>($new_len) };
    }};
}

// 当 T 是 ZST 时收缩迭代器，将长度减少 `n`。
// `n` 不得超过 `self.len()`。
macro_rules! zst_shrink {
    ($self: ident, $n: ident) => {
        let new_len = $self.end.addr() - $n;
        zst_set_len!($self, new_len);
    };
}

// 内联 is_empty 和 len 会产生巨大的性能差异
macro_rules! is_empty {
    ($self: ident) => {
        if T::IS_ZST { $self.end.addr() == 0 } else { $self.ptr.as_ptr() as *const _ == $self.end }
    };
}

macro_rules! len {
    ($self: ident) => {{
        #![allow(unused_unsafe)] // 我们有时会在不安全的区域内使用

        if T::IS_ZST {
            $self.end.addr()
        } else {
            // 为了摆脱一些边界检查 (参见 `position`)，我们使用 ptr_sub 而不是 offset_from (由 `codegen/slice-position-bounds-check` 测试。)
            //
            // SAFETY: 通过类型不变指针对齐和 `start <= end`
            unsafe { $self.end.sub_ptr($self.ptr.as_ptr()) }
        }
    }};
}

// `Iter` 和 `IterMut` 迭代器的共享定义
macro_rules! iterator {
    (
        struct $name:ident -> $ptr:ty,
        $elem:ty,
        $raw_mut:tt,
        {$( $mut_:tt )?},
        {$($extra:tt)*}
    ) => {
        // 返回第一个元素并将迭代器的起点向前移动 1.
        // 与内联函数相比，极大地提高了性能。
        // 迭代器不能为空。
        macro_rules! next_unchecked {
            ($self: ident) => {& $( $mut_ )? *$self.post_inc_start(1)}
        }

        // 返回最后一个元素并将迭代器的末尾向后移动 1.
        // 与内联函数相比，极大地提高了性能。
        // 迭代器不能为空。
        macro_rules! next_back_unchecked {
            ($self: ident) => {& $( $mut_ )? *$self.pre_dec_end(1)}
        }

        impl<'a, T> $name<'a, T> {
            // 用于从迭代器创建切片的 Helper 函数。
            #[inline(always)]
            fn make_slice(&self) -> &'a [T] {
                // SAFETY: 迭代器是从具有指针 `self.ptr` 和长度 `len!(self)` 的切片创建的。
                // 这样可以保证满足 `from_raw_parts` 的所有先决条件。
                //
                unsafe { from_raw_parts(self.ptr.as_ptr(), len!(self)) }
            }

            // Helper 函数，用于通过 `offset` 元素向前移动迭代器的开始，并返回旧的开始。
            //
            // 不安全，因为偏移不得超过 `self.len()`。
            #[inline(always)]
            unsafe fn post_inc_start(&mut self, offset: usize) -> * $raw_mut T {
                let old = self.ptr;
                if T::IS_ZST {
                    zst_shrink!(self, offset);
                } else {
                    // SAFETY: 调用者保证 `offset` 不超过 `self.len()`，因此此新指针位于 `self` 内，因此保证为非空。
                    //
                    self.ptr = unsafe { self.ptr.add(offset) };
                }
                old.as_ptr()
            }

            // Helper 函数，用于通过 `offset` 元素向后移动迭代器的末尾，并返回新的末尾。
            //
            // 不安全，因为偏移不得超过 `self.len()`。
            #[inline(always)]
            unsafe fn pre_dec_end(&mut self, offset: usize) -> * $raw_mut T {
                if T::IS_ZST {
                    zst_shrink!(self, offset);
                    self.ptr.as_ptr()
                } else {
                    // SAFETY: 调用者保证 `offset` 不超过 `self.len()`，这保证不会溢出 `isize`。
                    // 同样，结果指针位于 `slice` 的范围内，这满足了 `offset` 的其他要求。
                    //
                    self.end = unsafe { self.end.sub(offset) };
                    self.end
                }
            }
        }

        #[stable(feature = "rust1", since = "1.0.0")]
        impl<T> ExactSizeIterator for $name<'_, T> {
            #[inline(always)]
            fn len(&self) -> usize {
                len!(self)
            }

            #[inline(always)]
            fn is_empty(&self) -> bool {
                is_empty!(self)
            }
        }

        #[stable(feature = "rust1", since = "1.0.0")]
        impl<'a, T> Iterator for $name<'a, T> {
            type Item = $elem;

            #[inline]
            fn next(&mut self) -> Option<$elem> {
                // 可以用切片实现，但这避免了边界检查

                // SAFETY: `assume` 调用是安全的，因为非 ZST 上的切片必须具有非空结束指针。
                // `next_unchecked!` 的调用是安全的，因为我们先检查迭代器是否为空。
                //
                unsafe {
                    if !<T>::IS_ZST {
                        assume(!self.end.is_null());
                    }
                    if is_empty!(self) {
                        None
                    } else {
                        Some(next_unchecked!(self))
                    }
                }
            }

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

            #[inline]
            fn count(self) -> usize {
                len!(self)
            }

            #[inline]
            fn nth(&mut self, n: usize) -> Option<$elem> {
                if n >= len!(self) {
                    // 该迭代器现在为空。
                    if T::IS_ZST {
                        zst_set_len!(self, 0);
                    } else {
                        // SAFETY: 如果 T 不是 ZST，则 end 不能为 0，因为 ptr 不为 0 并且 end>=ptr
                        unsafe {
                            self.ptr = NonNull::new_unchecked(self.end as *mut T);
                        }
                    }
                    return None;
                }
                // SAFETY: 我们无所适从。`post_inc_start` 甚至对 ZST 来说也做对了。
                unsafe {
                    self.post_inc_start(n);
                    Some(next_unchecked!(self))
                }
            }

            #[inline]
            fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
                let advance = cmp::min(len!(self), n);
                // SAFETY: 通过构造，`advance` 不超过 `self.len()`。
                unsafe { self.post_inc_start(advance) };
                NonZeroUsize::new(n - advance).map_or(Ok(()), Err)
            }

            #[inline]
            fn last(mut self) -> Option<$elem> {
                self.next_back()
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            //
            //
            #[inline]
            fn for_each<F>(mut self, mut f: F)
            where
                Self: Sized,
                F: FnMut(Self::Item),
            {
                while let Some(x) = self.next() {
                    f(x);
                }
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            //
            //
            #[inline]
            fn all<F>(&mut self, mut f: F) -> bool
            where
                Self: Sized,
                F: FnMut(Self::Item) -> bool,
            {
                while let Some(x) = self.next() {
                    if !f(x) {
                        return false;
                    }
                }
                true
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            //
            //
            #[inline]
            fn any<F>(&mut self, mut f: F) -> bool
            where
                Self: Sized,
                F: FnMut(Self::Item) -> bool,
            {
                while let Some(x) = self.next() {
                    if f(x) {
                        return true;
                    }
                }
                false
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            //
            //
            #[inline]
            fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
            where
                Self: Sized,
                P: FnMut(&Self::Item) -> bool,
            {
                while let Some(x) = self.next() {
                    if predicate(&x) {
                        return Some(x);
                    }
                }
                None
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            //
            //
            #[inline]
            fn find_map<B, F>(&mut self, mut f: F) -> Option<B>
            where
                Self: Sized,
                F: FnMut(Self::Item) -> Option<B>,
            {
                while let Some(x) = self.next() {
                    if let Some(y) = f(x) {
                        return Some(y);
                    }
                }
                None
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            // 另外，`assume` 避免了边界检查。
            //
            #[inline]
            #[rustc_inherit_overflow_checks]
            fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
                Self: Sized,
                P: FnMut(Self::Item) -> bool,
            {
                let n = len!(self);
                let mut i = 0;
                while let Some(x) = self.next() {
                    if predicate(x) {
                        // SAFETY: 通过循环不变量，我们可以保证处于边界内：
                        // 当 `i >= n` 时，`self.next()` 返回 `None`，循环中断。
                        unsafe { assume(i < n) };
                        return Some(i);
                    }
                    i += 1;
                }
                None
            }

            // 我们覆盖了使用 `try_fold` 的默认实现，因为此简单实现生成的 LLVM IR 更少，并且编译速度更快。
            // 另外，`assume` 避免了边界检查。
            //
            #[inline]
            fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
                P: FnMut(Self::Item) -> bool,
                Self: Sized + ExactSizeIterator + DoubleEndedIterator
            {
                let n = len!(self);
                let mut i = n;
                while let Some(x) = self.next_back() {
                    i -= 1;
                    if predicate(x) {
                        // SAFETY: `i` 必须低于 `n`，因为它始于 `n`，并且仅在减小。
                        //
                        unsafe { assume(i < n) };
                        return Some(i);
                    }
                }
                None
            }

            #[inline]
            unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
                // SAFETY: 调用者必须保证 `i` 在底层切片的边界内，因此 `i` 不能溢出 `isize`，并且返回的引用保证引用切片的元素，因此保证是有效的。
                //
                // 还要注意，调用者也保证，我们永远不会再用相同的索引调用，并且不会调用其他访问这个子切片的方法，所以在 `IterMut` 的情况下，返回的引用是可变的是有效的
                //
                //
                //
                //
                //
                //
                //
                unsafe { & $( $mut_ )? * self.ptr.as_ptr().add(idx) }
            }

            $($extra)*
        }

        #[stable(feature = "rust1", since = "1.0.0")]
        impl<'a, T> DoubleEndedIterator for $name<'a, T> {
            #[inline]
            fn next_back(&mut self) -> Option<$elem> {
                // 可以用切片实现，但这避免了边界检查

                // SAFETY: `assume` 调用是安全的，因为非 ZST 上的切片必须具有非空结束指针。
                // `next_back_unchecked!` 的调用是安全的，因为我们先检查迭代器是否为空。
                //
                unsafe {
                    if !<T>::IS_ZST {
                        assume(!self.end.is_null());
                    }
                    if is_empty!(self) {
                        None
                    } else {
                        Some(next_back_unchecked!(self))
                    }
                }
            }

            #[inline]
            fn nth_back(&mut self, n: usize) -> Option<$elem> {
                if n >= len!(self) {
                    // 该迭代器现在为空。
                    if T::IS_ZST {
                        zst_set_len!(self, 0);
                    } else {
                        self.end = self.ptr.as_ptr();
                    }
                    return None;
                }
                // SAFETY: 我们无所适从。`pre_dec_end` 即使对 ZST 来说也是正确的。
                unsafe {
                    self.pre_dec_end(n);
                    Some(next_back_unchecked!(self))
                }
            }

            #[inline]
            fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
                let advance = cmp::min(len!(self), n);
                // SAFETY: 通过构造，`advance` 不超过 `self.len()`。
                unsafe { self.pre_dec_end(advance) };
                NonZeroUsize::new(n - advance).map_or(Ok(()), Err)
            }
        }

        #[stable(feature = "fused", since = "1.26.0")]
        impl<T> FusedIterator for $name<'_, T> {}

        #[unstable(feature = "trusted_len", issue = "37572")]
        unsafe impl<T> TrustedLen for $name<'_, T> {}

        impl<'a, T> UncheckedIterator for $name<'a, T> {
            unsafe fn next_unchecked(&mut self) -> $elem {
                // SAFETY: 调用者保证至少还有一项。
                unsafe {
                    next_unchecked!(self)
                }
            }
        }

        #[stable(feature = "default_iters", since = "1.70.0")]
        impl<T> Default for $name<'_, T> {
            /// 创建一个空的切片迭代器。
            ///
            /// ```
            #[doc = concat!("# use core::slice::", stringify!($name), ";")]
            #[doc = concat!("let iter: ", stringify!($name<'_, u8>), " = Default::default();")]
            /// assert_eq!(iter.len(), 0);
            /// ```
            fn default() -> Self {
                (& $( $mut_ )? []).into_iter()
            }
        }
    }
}

macro_rules! forward_iterator {
    ($name:ident: $elem:ident, $iter_of:ty) => {
        #[stable(feature = "rust1", since = "1.0.0")]
        impl<'a, $elem, P> Iterator for $name<'a, $elem, P>
        where
            P: FnMut(&T) -> bool,
        {
            type Item = $iter_of;

            #[inline]
            fn next(&mut self) -> Option<$iter_of> {
                self.inner.next()
            }

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

        #[stable(feature = "fused", since = "1.26.0")]
        impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P> where P: FnMut(&T) -> bool {}
    };
}