//! `Vec` 的就地迭代和收集特化
//!
//! Note: 本文档记录了 Vec 内部结构，以下部分解释了实现细节，最好与本模块的源代码一起阅读。
//!
//! 本模块的特化适用于 `source.adapter().adapter().adapter().collect::<Vec<U>>()` 形式的迭代器
//! 其中 `source` 是从 [`Vec<T>`]、[`Box<[T]>`][box] (通过转换为 `Vec`) 或 [`BinaryHeap<T>`] 获得的拥有迭代器，每个适配器每个步骤消耗一个或多个项 (由 [`InPlaceIterable`] 表示)，提供对 `source` 的传递访问 (通过 [`SourceIter`])，从而提供底层分配.
//! 最后，`T` 和 `U` 的布局必须具有相同的大小和对齐方式，目前通过 const eval 而不是专门的 [`SpecFromIter`] 实现中的 trait bounds 来确保的。
//!
//! [`BinaryHeap<T>`]: crate::collections::BinaryHeap
//! [box]: crate::boxed::Box
//!
//! 通过扩展，在其 `FromIterator` 实现中内部使用 `collect::<Vec<_>>()` 的其他一些集合也从中受益。
//!
//! 对底层源的访问通过私有 [`AsVecIntoIter`] trait 进行进一步的间接层，以隐藏其他集合可能在内部使用 `vec::IntoIter` 的实现细节。
//!
//! 就地迭代取决于几个不安全的 traits 的交互，迭代器管道中多个部分的实现细节，并且通常需要跨多个结构体进行整体推理，因为迭代器是协作执行的，而不是让中央 evaluator/visitor 结构执行所有迭代器组件。
//!
//!
//! # 读取和写入相同的分配
//!
//! 就其本质而言，就地收集意味着迭代器的 reader 和 writer 端使用相同的分配。由于 `try_fold()` (在 [`SpecInPlaceCollect`] 中使用) 在迭代期间需要对迭代器的引用，这意味着我们不能交替读取值和获取要写入的引用。
//! 相反，必须在 reader 和 writer 端使用裸指针。
//!
//! [`InPlaceIterable`] 要求确保写入操作永远不会破坏尚未读取的项。
//!
//! # 布局约束
//!
//! [`Allocator`] 要求 `allocate()` 和 `deallocate()` 具有匹配的对齐方式和大小。
//! 此外，这种特化对于 ZST 没有意义，因为不需要避免重新分配，而且它会使指针运算更加困难。
//!
//! [`Allocator`]: core::alloc::Allocator
//!
//! # Drop- 和 panic 安全
//!
//! 迭代可能会出现 panic，需要丢弃已写入的部分以及源的其余部分。迭代也可以保留一些必须丢弃的未消耗的源项。
//! 所有这些丢弃进而会导致 panic，然后必须泄漏分配或中止，以避免双重丢弃。
//!
//! 这由 sink 项 (`U`) 的 [`InPlaceDrop`] 守卫和剩余源项 (`T`) 的 [`vec::IntoIter::forget_allocation_drop_remaining()`] 处理。
//!
//! 如果丢弃任何剩余的源 (`T`) panic，则 [`InPlaceDstBufDrop`] 将处理项丢弃已收集的 Z0sink2 项 (`T`) 并释放分配。
//!
//! [`vec::IntoIter::forget_allocation_drop_remaining()`]: super::IntoIter::forget_allocation_drop_remaining()
//!
//! # O(1) 收集
//!
//! 当迭代器实现 [`TrustedRandomAccessNoCoerce`] 以让优化器看到它是一个带有单个 [induction variable] 的计数循环时，主迭代本身会进一步特化。这可以将一些迭代器变成一个 noop，也就是说，它将迭代器从 O(n) 减少到 O(1)。
//! 这种特殊的优化非常易变，并不总是有效，请参见 [#79308]
//!
//! [#79308]: https://github.com/rust-lang/rust/issues/79308
//! [induction variable]: https://en.wikipedia.org/wiki/Induction_variable
//!
//! 由于通过该 trait 的未经检查的访问不会推进 `IntoIter` 的读取指针，这将与上述关于丢弃尾部的要求进行不合理的交互。
//! 但是由于 `IntoIter` 的正常 `Drop` 实现会遇到同样的问题，因此只有在项没有析构函数时才实现 `TrustedRandomAccessNoCoerce` 是正确的。因此，该隐式要求也使特化可以安全地用于就地收集。
//! 请注意，这个安全问题是关于 `impl Drop for IntoIter` 的正确性，而不是 `InPlaceIterable` 的保证。
//!
//! # 适配器实现
//!
//! 适配器的不变量记录在 [`SourceIter`] 和 [`InPlaceIterable`] 中，但是由于多种原因，有时是非本地原因，使它们正确可能相当微妙。
//! 例如，`InPlaceIterable` 对 [`Peekable`] 实现是有效的，除了它是有状态的、可克隆的并且 `IntoIter` 的克隆实现缩短了底层分配，这意味着如果迭代器已被窥视然后被克隆，则不再有足够的空间，从而破坏了不变量 ([#85322])。
//!
//! [#85322]: https://github.com/rust-lang/rust/issues/85322
//! [`Peekable`]: core::iter::Peekable
//!
//! # Examples
//!
//! 通过这种特化优化的一些案例，可以在 `Vec` 基准测试中找到更多:
//!
//! ```rust
//! # #[allow(dead_code)]
//! /// 将 usize vec 转换为 isize one。
//! pub fn cast(vec: Vec<usize>) -> Vec<isize> {
//!   // 不分配、释放或 panic。在 optlevel>=2 时，它不会循环。
//!   // 当然，这种特殊情况可以也应该用 `into_raw_parts` 和 `from_raw_parts` 来代替。
//!   //
//!   vec.into_iter().map(|u| u as isize).collect()
//! }
//! ```
//!
//! ```rust
//! # #[allow(dead_code)]
//! /// 丢弃 `src` 中的剩余项，如果 `T` 和 `U` 的布局匹配，则返回由原始分配支持的空 Vec。
//! /// 否则它返回一个新的空 vec。
//! ///
//! pub fn recycle_allocation<T, U>(src: Vec<T>) -> Vec<U> {
//!   src.into_iter().filter_map(|_| None).collect()
//! }
//! ```
//!
//! ```rust
//! let vec = vec![13usize; 1024];
//! let _ = vec.into_iter()
//!   .enumerate()
//!   .filter_map(|(idx, val)| if idx % 2 == 0 { Some(val+idx) } else {None})
//!   .collect::<Vec<_>>();
//!
//! // 等效于以下内容，但不需要边界检查
//!
//! let mut vec = vec![13usize; 1024];
//! let mut write_idx = 0;
//! for idx in 0..vec.len() {
//!    if idx % 2 == 0 {
//!       vec[write_idx] = vec[idx] + idx;
//!       write_idx += 1;
//!    }
//! }
//! vec.truncate(write_idx);
//! ```
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
//!
use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce};
use core::mem::{self, ManuallyDrop, SizedTypeProperties};
use core::ptr::{self};

use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec};

/// 专业化标记，用于在重用源分配时将迭代器管道收集到 Vec 中，即
/// 在适当的位置执行管道。
#[rustc_unsafe_specialization_marker]
pub(super) trait InPlaceIterableMarker {}

impl<T> InPlaceIterableMarker for T where T: InPlaceIterable {}

impl<T, I> SpecFromIter<T, I> for Vec<T>
where
    I: Iterator<Item = T> + SourceIter<Source: AsVecIntoIter> + InPlaceIterableMarker,
{
    default fn from_iter(mut iterator: I) -> Self {
        // 请参见模块文档中的 "布局约束" 部分。
        // 我们在这里依赖常量优化，因为这些条件目前不能表示为 trait bounds
        if T::IS_ZST
            || mem::size_of::<T>()
                != mem::size_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>()
            || mem::align_of::<T>()
                != mem::align_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>()
        {
            // 回退到更通用的实现
            return SpecFromIterNested::from_iter(iterator);
        }

        let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe {
            let inner = iterator.as_inner().as_into_iter();
            (
                inner.buf.as_ptr(),
                inner.ptr,
                inner.buf.as_ptr() as *mut T,
                inner.end as *const T,
                inner.cap,
            )
        };

        // SAFETY: `dst_buf` 和 `dst_end` 是缓冲区的开始和结束。
        let len = unsafe { SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf, dst_end) };

        let src = unsafe { iterator.as_inner().as_into_iter() };
        // 检查 SourceIter 契约是否得到维护警告：如果不是，我们甚至可能无法做到这一点
        //
        debug_assert_eq!(src_buf, src.buf.as_ptr());
        // 检查 InPlaceIterable 契约。只有迭代器推进了源指针，这才是可能的。
        // 如果它通过 TrustedRandomAccess 使用未经检查的访问，则源指针将停留在其初始位置，我们不能将其用作引用
        //
        if src.ptr != src_ptr {
            debug_assert!(
                unsafe { dst_buf.add(len) as *const _ } <= src.ptr,
                "InPlaceIterable contract violation, write pointer advanced beyond read pointer"
            );
        }

        // 分配的所有权和新的 `T` 值暂时移至 `dst_guard`。
        // 这是安全的，因为 `forget_allocation_drop_remaining` 在任何 panic 发生之前立即忘记分配以避免任何重复释放，然后继续丢弃源尾部的任何剩余值。
        //
        //
        // Note: TrustedRandomIteratorNoCoerce 契约 (由下面的 SpecInPlaceCollect 使用) 不允许对源的这种访问。但是请参见模块文档中的 "O(1) collect" 部分，为什么这仍然可以。
        //
        //
        //
        let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap };
        src.forget_allocation_drop_remaining();
        mem::forget(dst_guard);

        let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) };

        vec
    }
}

fn write_in_place_with_drop<T>(
    src_end: *const T,
) -> impl FnMut(InPlaceDrop<T>, T) -> Result<InPlaceDrop<T>, !> {
    move |mut sink, item| {
        unsafe {
            // 这里的 InPlaceIterable 契约无法精确验证，因为 try_fold 对源指针有一个唯一的引用，我们所能做的就是检查它是否仍在范围内
            //
            //
            debug_assert!(sink.dst as *const _ <= src_end, "InPlaceIterable contract violation");
            ptr::write(sink.dst, item);
            // 由于这会执行用户代码，这可能会导致 panic，因此我们必须在每一步之后 bump 指针。
            //
            sink.dst = sink.dst.add(1);
        }
        Ok(sink)
    }
}

/// 一个用于保存就地迭代收集循环的专用实现的 Helper trait
trait SpecInPlaceCollect<T, I>: Iterator<Item = T> {
    /// 将迭代器 (`self`) 收集到目标缓冲区 (`dst`) 中并返回收集的项数。`end` 是分配的最后一个可写元素，用于边界检查。
    ///
    /// 这个方法是专门的，它的一个实现使用 `Iterator::__iterator_get_unchecked` 调用，`TrustedRandomAccessNoCoerce` 绑定在 `I` 上，这意味着这个方法的调用者必须考虑 trait 的安全条件。
    ///
    ///
    ///
    ///
    unsafe fn collect_in_place(&mut self, dst: *mut T, end: *const T) -> usize;
}

impl<T, I> SpecInPlaceCollect<T, I> for I
where
    I: Iterator<Item = T>,
{
    #[inline]
    default unsafe fn collect_in_place(&mut self, dst_buf: *mut T, end: *const T) -> usize {
        // 使用 try-fold，因为
        // - 对于某些迭代器适配器，它可以更好地进行矢量化
        // - 与大多数内部迭代方法不同，它只需要一个 &mut self
        // - 它让我们把写指针穿进它的内部，最后把它拿回来
        let sink = InPlaceDrop { inner: dst_buf, dst: dst_buf };
        let sink =
            self.try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(end)).unwrap();
        // 迭代成功，不要丢弃 head
        unsafe { ManuallyDrop::new(sink).dst.sub_ptr(dst_buf) }
    }
}

impl<T, I> SpecInPlaceCollect<T, I> for I
where
    I: Iterator<Item = T> + TrustedRandomAccessNoCoerce,
{
    #[inline]
    unsafe fn collect_in_place(&mut self, dst_buf: *mut T, end: *const T) -> usize {
        let len = self.size();
        let mut drop_guard = InPlaceDrop { inner: dst_buf, dst: dst_buf };
        for i in 0..len {
            // 安全性: InplaceIterable 契约保证，对于我们读取的每个元素，底层存储中的一个插槽将被释放，我们可以立即写回结果。
            //
            //
            unsafe {
                let dst = dst_buf.add(i);
                debug_assert!(dst as *const _ <= end, "InPlaceIterable contract violation");
                ptr::write(dst, self.__iterator_get_unchecked(i));
                // 由于这会执行用户代码，这可能会导致 panic，因此我们必须在每一步之后 bump 指针。
                //
                drop_guard.dst = dst.add(1);
            }
        }
        mem::forget(drop_guard);
        len
    }
}

/// 用于就地迭代特化的内部助手 trait。
///
/// 目前这仅由 [`vec::IntoIter`] 实现 - 返回对自身的引用 - 并且 [`binary_heap::IntoIter`] 将返回对其内部表示的引用。
///
/// 由于这是一个内部 trait，它隐藏了 `binary_heap::IntoIter` 在内部使用 `vec::IntoIter` 的实现细节。
///
/// [`vec::IntoIter`]: super::IntoIter
/// [`binary_heap::IntoIter`]: crate::collections::binary_heap::IntoIter
///
/// # Safety
///
/// 就地迭代依赖于 `vec::IntoIter` 的实现细节，最重要的是它不会在迭代过程中创建对整个分配的引用，只是创建裸指针
///
///
///
#[rustc_specialization_trait]
pub(crate) unsafe trait AsVecIntoIter {
    type Item;
    fn as_into_iter(&mut self) -> &mut super::IntoIter<Self::Item>;
}