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

// 内联 is_empty 和 len 会产生巨大的性能差异
macro_rules! is_empty {
    // 我们对 ZST 迭代器的长度进行编码的方式，这对 ZST 和非 ZST 均有效。
    //
    ($self: ident) => {
        $self.ptr.as_ptr() as *const T == $self.end
    };
}

// 为了摆脱某些边界检查 (请参见 `position`)，我们以某种出乎意料的方式来计算长度。
// (通过 `codegen/slice-position-bounds-check` 测试。)
macro_rules! len {
    ($self: ident) => {{
        #![allow(unused_unsafe)] // 我们有时会在不安全的区域内使用

        let start = $self.ptr;
        let size = size_from_ptr(start.as_ptr());
        if size == 0 {
            // 该 _cannot_ 使用 `unchecked_sub`，因为我们依靠包装来表示长 ZST 切片迭代器的长度。
            //
            ($self.end as usize).wrapping_sub(start.as_ptr() as usize)
        } else {
            // 我们知道 `start <= end` 可以比需要签名处理的 `offset_from` 做得更好。
            // 通过在此处设置适当的标志，我们可以告诉 LLVM，这有助于消除边界检查。
            // SAFETY: 根据类型不变量，`start <= end`
            //
            let diff = unsafe { unchecked_sub($self.end as usize, start.as_ptr() as usize) };
            // 通过还告诉 LLVM 指针相隔一个类型大小的精确倍数，它可以将 `len() == 0` 优化到 `start == end`，而不是 `(end - start) < size`。
            //
            // SAFETY: 通过类型不变，指针将对齐，因此它们之间的距离必须是指针大小的倍数
            //
            //
            unsafe { exact_div(diff, size) }
        }
    }};
}

// `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)}
        }

        // 当 T 为 ZST 时，通过将迭代器的末尾向后移动 `n` 来缩小迭代器。
        // `n` 不得超过 `self.len()`。
        macro_rules! zst_shrink {
            ($self: ident, $n: ident) => {
                $self.end = ($self.end as * $raw_mut u8).wrapping_offset(-$n) as * $raw_mut T;
            }
        }

        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: isize) -> * $raw_mut T {
                if mem::size_of::<T>() == 0 {
                    zst_shrink!(self, offset);
                    self.ptr.as_ptr()
                } else {
                    let old = self.ptr.as_ptr();
                    // SAFETY: 调用者保证 `offset` 不超过 `self.len()`，因此此新指针位于 `self` 内，因此保证为非空。
                    //
                    self.ptr = unsafe { NonNull::new_unchecked(self.ptr.as_ptr().offset(offset)) };
                    old
                }
            }

            // Helper 函数，用于通过 `offset` 元素向后移动迭代器的末尾，并返回新的末尾。
            //
            // 不安全，因为偏移不得超过 `self.len()`。
            #[inline(always)]
            unsafe fn pre_dec_end(&mut self, offset: isize) -> * $raw_mut T {
                if mem::size_of::<T>() == 0 {
                    zst_shrink!(self, offset);
                    self.ptr.as_ptr()
                } else {
                    // SAFETY: 调用者保证 `offset` 不超过 `self.len()`，这保证不会溢出 `isize`。
                    // 同样，结果指针位于 `slice` 的范围内，这满足了 `offset` 的其他要求。
                    //
                    self.end = unsafe { self.end.offset(-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 {
                    assume(!self.ptr.as_ptr().is_null());
                    if mem::size_of::<T>() != 0 {
                        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 mem::size_of::<T>() == 0 {
                        // 我们必须这样做，因为 `ptr` 可能永远不会为 0，但 `end` 可能是 (由于包装)。
                        //
                        self.end = self.ptr.as_ptr();
                    } 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 as isize);
                    Some(next_unchecked!(self))
                }
            }

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

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

            #[doc(hidden)]
            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 {
                    assume(!self.ptr.as_ptr().is_null());
                    if mem::size_of::<T>() != 0 {
                        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) {
                    // 该迭代器现在为空。
                    self.end = self.ptr.as_ptr();
                    return None;
                }
                // SAFETY: 我们无所适从。`pre_dec_end` 即使对 ZST 来说也是正确的。
                unsafe {
                    self.pre_dec_end(n as isize);
                    Some(next_back_unchecked!(self))
                }
            }

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

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

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 {}
    };
}