#![unstable(feature = "raw_vec_internals", reason = "unstable const warnings", issue = "none")]

use core::alloc::LayoutError;
use core::cmp;
use core::intrinsics;
use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties};
use core::ptr::{self, NonNull, Unique};
use core::slice;

#[cfg(not(no_global_oom_handling))]
use crate::alloc::handle_alloc_error;
use crate::alloc::{Allocator, Global, Layout};
use crate::boxed::Box;
use crate::collections::TryReserveError;
use crate::collections::TryReserveErrorKind::*;

#[cfg(test)]
mod tests;

#[cfg(not(no_global_oom_handling))]
enum AllocInit {
    /// 新存储器的内容未初始化。
    Uninitialized,
    /// 确保将新内存清零。
    Zeroed,
}

/// 一个底层的实用程序，用于更符合人体工程学地分配、重新分配和释放堆上的内存缓冲区，而不必担心所涉及的所有极端情况。
///
/// 此类型非常适合构建自己的数据结构，例如 Vec 和 VecDeque。
/// 特别是：
///
/// * 在零大小类型上生成 `Unique::dangling()`。
/// * 在零长度分配上产生 `Unique::dangling()`。
/// * 避免释放 `Unique::dangling()`。
/// * 捕获容量计算中的所有溢出 (将它们提升为 "容量溢出" panics)。
/// * 防止 32 位系统分配超过 `isize::MAX` 字节。
/// * 防止您的长度溢出。
/// * 调用 `handle_alloc_error` 进行错误分配。
/// * 包含 `ptr::Unique`，因此为用户提供了所有相关的好处。
/// * 使用分配器返回的多余资源来使用最大可用容量。
///
/// 无论如何，此类型不会检查它管理的内存。当丢弃后，它会释放其内存，但不会尝试丢弃其内容。
/// 由 `RawVec` 的用户来处理存储在 `RawVec` 中的实际内容。
///
/// 注意，零大小类型的余量始终是无限的，因此 `capacity()` 始终返回 `usize::MAX`。
/// 这意味着与 `Box<[T]>` 进行双向交互时需要小心，因为 `capacity()` 不会产生长度。
///
///
#[allow(missing_debug_implementations)]
pub(crate) struct RawVec<T, A: Allocator = Global> {
    ptr: Unique<T>,
    cap: usize,
    alloc: A,
}

impl<T> RawVec<T, Global> {
    /// HACK(Centril): 之所以存在，是因为稳定的 `const fn` 只能调用稳定的 `const fn`，所以他们不能调用`Self::new()`。
    ///
    /// 如果您更改 `RawVec<T>::new` 或依赖项，请注意不要引入任何真正不稳定的东西。
    ///
    ///
    pub const NEW: Self = Self::new();

    /// 创建最大的 `RawVec` (在系统堆上) 而不分配。
    /// 如果 `T` 的大小为正，则表示 `RawVec` 的容量为 `0`。
    /// 如果 `T` 的大小为零，则生成一个容量为 `usize::MAX` 的 `RawVec`。
    /// 对于实现延迟分配很有用。
    ///
    #[must_use]
    pub const fn new() -> Self {
        Self::new_in(Global)
    }

    /// 创建 `RawVec` (在系统堆上)，该 `RawVec` 具有 `[T; capacity]` 的确切容量和对齐要求。
    /// 这等效于 `capacity` 为 `0` 或 `T` 为零大小时调用 `RawVec::new`。
    /// 请注意，如果 `T` 的大小为零，这意味着您将无法获得具有请求容量的 `RawVec`。
    ///
    /// # Panics
    ///
    /// 如果请求的容量超过 `isize::MAX` 字节，就会出现 panics。
    ///
    /// # Aborts
    ///
    /// 在 OOM 上中止。
    ///
    ///
    #[cfg(not(any(no_global_oom_handling, test)))]
    #[must_use]
    #[inline]
    pub fn with_capacity(capacity: usize) -> Self {
        Self::with_capacity_in(capacity, Global)
    }

    /// 类似于 `with_capacity`，但保证缓冲区为零。
    #[cfg(not(any(no_global_oom_handling, test)))]
    #[must_use]
    #[inline]
    pub fn with_capacity_zeroed(capacity: usize) -> Self {
        Self::with_capacity_zeroed_in(capacity, Global)
    }
}

impl<T, A: Allocator> RawVec<T, A> {
    // 微小的 Vecs 是愚蠢的。跳转到：
    // - 如果元素大小为 1，则为 8，因为任何堆分配器都可能会将少于 8 个字节的请求舍入为至少 8 个字节。
    //
    // - 如果元素大小适中 (<= 1 KiB)，则为 4。
    // - 1 否则，为了避免为非常短的 Vecs 浪费太多空间。
    pub(crate) const MIN_NON_ZERO_CAP: usize = if mem::size_of::<T>() == 1 {
        8
    } else if mem::size_of::<T>() <= 1024 {
        4
    } else {
        1
    };

    /// 类似于 `new`，但是在返回的 `RawVec` 的分配器选择上进行了参数化。
    ///
    pub const fn new_in(alloc: A) -> Self {
        // `cap: 0` means "unallocated".  忽略大小为零的类型。
        Self { ptr: Unique::dangling(), cap: 0, alloc }
    }

    /// 类似于 `with_capacity`，但是在返回的 `RawVec` 的分配器选择上进行了参数化。
    ///
    #[cfg(not(no_global_oom_handling))]
    #[inline]
    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
        Self::allocate_in(capacity, AllocInit::Uninitialized, alloc)
    }

    /// 类似于 `with_capacity_zeroed`，但是在返回的 `RawVec` 的分配器选择上进行了参数化。
    ///
    #[cfg(not(no_global_oom_handling))]
    #[inline]
    pub fn with_capacity_zeroed_in(capacity: usize, alloc: A) -> Self {
        Self::allocate_in(capacity, AllocInit::Zeroed, alloc)
    }

    /// 使用指定的 `len` 将整个缓冲区转换为 `Box<[MaybeUninit<T>]>`。
    ///
    /// 请注意，这将正确地重构可能已执行的所有 `cap` 更改。(有关详细信息，请参见类型说明。)
    ///
    /// # Safety
    ///
    /// * `len` 必须大于或等于最近请求的容量，并且
    /// * `len` 必须小于或等于 `self.capacity()`。
    ///
    /// 请注意，请求的容量和 `self.capacity()` 可能有所不同，因为分配器可能会整合并返回比请求更大的内存块。
    ///
    ///
    pub unsafe fn into_box(self, len: usize) -> Box<[MaybeUninit<T>], A> {
        // 仔细检查安全要求的一半 (我们不能检查另一半)。
        debug_assert!(
            len <= self.capacity(),
            "`len` must be smaller than or equal to `self.capacity()`"
        );

        let me = ManuallyDrop::new(self);
        unsafe {
            let slice = slice::from_raw_parts_mut(me.ptr() as *mut MaybeUninit<T>, len);
            Box::from_raw_in(slice, ptr::read(&me.alloc))
        }
    }

    #[cfg(not(no_global_oom_handling))]
    fn allocate_in(capacity: usize, init: AllocInit, alloc: A) -> Self {
        // 不要在这里分配，因为 `Drop` 不会在 `capacity` 被释放时释放 0.
        if T::IS_ZST || capacity == 0 {
            Self::new_in(alloc)
        } else {
            // 我们在这里避免使用 `unwrap_or_else`，因为它会使生成的 LLVM IR 数量膨胀。
            //
            let layout = match Layout::array::<T>(capacity) {
                Ok(layout) => layout,
                Err(_) => capacity_overflow(),
            };
            match alloc_guard(layout.size()) {
                Ok(_) => {}
                Err(_) => capacity_overflow(),
            }
            let result = match init {
                AllocInit::Uninitialized => alloc.allocate(layout),
                AllocInit::Zeroed => alloc.allocate_zeroed(layout),
            };
            let ptr = match result {
                Ok(ptr) => ptr,
                Err(_) => handle_alloc_error(layout),
            };

            // 分配器当前返回一个 `NonNull<[u8]>`，其长度与请求的大小相匹配。
            // 如果情况发生变化，此处的容量应更改为 `ptr.len() / mem::size_of::<T>()`。
            //
            Self {
                ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) },
                cap: capacity,
                alloc,
            }
        }
    }

    /// 从指针，容量和分配器重构 `RawVec`。
    ///
    /// # Safety
    ///
    /// 必须通过给定的 `capacity` 分配 `ptr` (通过给定的分配器 `alloc`)。
    /// 对于大小类型，`capacity` 不能超过 `isize::MAX`。
    /// (仅在 32 位系统上需要考虑)。
    /// ZST vectors 的容量最多为 `usize::MAX`。
    /// 如果 `ptr` 和 `capacity` 来自通过 `alloc` 创建的 `RawVec`，则可以保证。
    ///
    #[inline]
    pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, alloc: A) -> Self {
        Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap: capacity, alloc }
    }

    /// 获取分配开始处的裸指针。
    /// 请注意，如果 `capacity == 0` 或 `T` 的大小为零，则为 `Unique::dangling()`。
    /// 在前一种情况下，您必须小心。
    #[inline]
    pub fn ptr(&self) -> *mut T {
        self.ptr.as_ptr()
    }

    /// 获取分配的容量。
    ///
    /// 如果 `T` 的大小为零，则它将始终为 `usize::MAX`。
    #[inline(always)]
    pub fn capacity(&self) -> usize {
        if T::IS_ZST { usize::MAX } else { self.cap }
    }

    /// 返回支持此 `RawVec` 的分配器的共享引用。
    pub fn allocator(&self) -> &A {
        &self.alloc
    }

    fn current_memory(&self) -> Option<(NonNull<u8>, Layout)> {
        if T::IS_ZST || self.cap == 0 {
            None
        } else {
            // 我们可以在这里使用 Layout::array 来确保不存在 isize 和 usize 溢出，并且可以假设处理步幅和大小之间的差异，但是这个内存已经被分配，所以我们知道它不会溢出，目前 rust 不支持这种类型。
            // 所以我们可以通过跳过一些检查并避免展开来做得更好。
            //
            //
            let _: () = const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) };
            unsafe {
                let align = mem::align_of::<T>();
                let size = mem::size_of::<T>().unchecked_mul(self.cap);
                let layout = Layout::from_size_align_unchecked(size, align);
                Some((self.ptr.cast().into(), layout))
            }
        }
    }

    /// 确保缓冲区至少包含足够的空间来容纳 `len + additional` 元素。
    /// 如果还没有足够的容量，则将重新分配足够的空间以及舒适的松弛空间，以摊销 *O*(1) 行为。
    ///
    /// 如果会不必要地使其自身成为 panic，则将限制此行为。
    ///
    /// 如果 `len` 超过 `self.capacity()`，则可能无法实际分配请求的空间。
    /// 这并不是真的不安全，但是依赖于这个函数行为的不安全代码可能会被破坏。
    ///
    /// 这是实现 `extend` 之类的批量推送操作的理想选择。
    ///
    /// # Panics
    ///
    /// 如果新容量超过 `isize::MAX` 字节，就会出现 panics。
    ///
    /// # Aborts
    ///
    /// 在 OOM 上中止。
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[inline]
    pub fn reserve(&mut self, len: usize, additional: usize) {
        // 当已经有足够的容量时，调用者希望这个函数非常便宜。
        // 因此，我们将所有的调整大小和错误处理逻辑从 grow_amortized 和 handle_reserve 移到一个调用之后，同时确保如果比较失败，这个函数很可能被内联为一个比较和一个调用。
        //
        //
        #[cold]
        fn do_reserve_and_handle<T, A: Allocator>(
            slf: &mut RawVec<T, A>,
            len: usize,
            additional: usize,
        ) {
            handle_reserve(slf.grow_amortized(len, additional));
        }

        if self.needs_to_grow(len, additional) {
            do_reserve_and_handle(self, len, additional);
        }
    }

    /// `reserve()` 的专用版本，仅由 hot 且经常实例化的  `Vec::push()` 使用，它会进行自己的容量检查。
    ///
    #[cfg(not(no_global_oom_handling))]
    #[inline(never)]
    pub fn reserve_for_push(&mut self, len: usize) {
        handle_reserve(self.grow_amortized(len, 1));
    }

    /// 与 `reserve` 相同，但在出错时返回，而不是 panic 或中止。
    pub fn try_reserve(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
        if self.needs_to_grow(len, additional) {
            self.grow_amortized(len, additional)
        } else {
            Ok(())
        }
    }

    /// 确保缓冲区至少包含足够的空间来容纳 `len + additional` 元素。
    /// 如果尚未分配，将重新分配所需的最小可能内存量。
    /// 通常，这恰好是必需的内存量，但是原则上分配器可以自由地提供比我们要求的更多的内存。
    ///
    ///
    /// 如果 `len` 超过 `self.capacity()`，则可能无法实际分配请求的空间。
    /// 这并不是真的不安全，但是依赖于这个函数行为的不安全代码可能会被破坏。
    ///
    /// # Panics
    ///
    /// 如果新容量超过 `isize::MAX` 字节，就会出现 panics。
    ///
    /// # Aborts
    ///
    /// 在 OOM 上中止。
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    pub fn reserve_exact(&mut self, len: usize, additional: usize) {
        handle_reserve(self.try_reserve_exact(len, additional));
    }

    /// 与 `reserve_exact` 相同，但在出错时返回，而不是 panic 或中止。
    pub fn try_reserve_exact(
        &mut self,
        len: usize,
        additional: usize,
    ) -> Result<(), TryReserveError> {
        if self.needs_to_grow(len, additional) { self.grow_exact(len, additional) } else { Ok(()) }
    }

    /// 将缓冲区缩小到指定的容量。
    /// 如果给定的数量为 0，则实际上完全释放。
    ///
    /// # Panics
    ///
    /// 如果给定数量大于当前容量，就会出现 panic。
    ///
    /// # Aborts
    ///
    /// 在 OOM 上中止。
    #[cfg(not(no_global_oom_handling))]
    pub fn shrink_to_fit(&mut self, cap: usize) {
        handle_reserve(self.shrink(cap));
    }
}

impl<T, A: Allocator> RawVec<T, A> {
    /// 如果缓冲区需要增长才能满足所需的额外容量，则返回。
    /// 主要用于无需内联 `grow` 就可以进行内联预留调用。
    fn needs_to_grow(&self, len: usize, additional: usize) -> bool {
        additional > self.capacity().wrapping_sub(len)
    }

    fn set_ptr_and_cap(&mut self, ptr: NonNull<[u8]>, cap: usize) {
        // 分配器当前返回一个 `NonNull<[u8]>`，其长度与请求的大小相匹配。
        // 如果情况发生变化，此处的容量应更改为 `ptr.len() / mem::size_of::<T>()`。
        //
        self.ptr = unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) };
        self.cap = cap;
    }

    // 此方法通常实例化很多次。因此，我们希望它尽可能小，以缩短编译时间。
    // 但是我们也希望它的尽可能多的内容是静态可计算的，以使生成的代码运行得更快。
    // 因此，精心编写此方法，以便所有依赖 `T` 的代码都在其中，而尽可能多的不依赖 `T` 的代码都在非 `T` 泛型的函数中。
    //
    //
    //
    //
    fn grow_amortized(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
        // 这是通过调用上下文来确保的。
        debug_assert!(additional > 0);

        if T::IS_ZST {
            // 因为当 `elem_size` 为 X 时我们返回 `usize::MAX` 的容量
            // 0，到达此处必定意味着 `RawVec` 已满。
            return Err(CapacityOverflow.into());
        }

        // 不幸的是，我们对这些检查无能为力。
        let required_cap = len.checked_add(additional).ok_or(CapacityOverflow)?;

        // 这保证了指数增长。
        // 倍增不会溢出，因为 `cap <= isize::MAX` 和 `cap` 的类型是 `usize`。
        let cap = cmp::max(self.cap * 2, required_cap);
        let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap);

        let new_layout = Layout::array::<T>(cap);

        // `finish_grow` 是非泛型的，而不是 `T`。
        let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?;
        self.set_ptr_and_cap(ptr, cap);
        Ok(())
    }

    // 此方法的约束与 `grow_amortized` 上的约束大致相同，但是此方法通常实例化的频率较低，因此不太重要。
    //
    //
    fn grow_exact(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
        if T::IS_ZST {
            // 由于我们在类型大小为时返回 `usize::MAX` 的容量
            // 0，到达此处必定意味着 `RawVec` 已满。
            return Err(CapacityOverflow.into());
        }

        let cap = len.checked_add(additional).ok_or(CapacityOverflow)?;
        let new_layout = Layout::array::<T>(cap);

        // `finish_grow` 是非泛型的，而不是 `T`。
        let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?;
        self.set_ptr_and_cap(ptr, cap);
        Ok(())
    }

    #[cfg(not(no_global_oom_handling))]
    fn shrink(&mut self, cap: usize) -> Result<(), TryReserveError> {
        assert!(cap <= self.capacity(), "Tried to shrink to a larger capacity");

        let (ptr, layout) = if let Some(mem) = self.current_memory() { mem } else { return Ok(()) };
        // 看到 current_memory() 为什么这个断言在这里
        let _: () = const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) };
        let ptr = unsafe {
            // `Layout::array` 在这里不能溢出，因为容量更大时，它会更早溢出。
            //
            let new_size = mem::size_of::<T>().unchecked_mul(cap);
            let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
            self.alloc
                .shrink(ptr, layout, new_layout)
                .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })?
        };
        self.set_ptr_and_cap(ptr, cap);
        Ok(())
    }
}

// 该函数在 `RawVec` 外部，以最大程度地减少编译时间。有关详细信息，请参见 `RawVec::grow_amortized` 上方的注释。
// (`A` 参数并不重要，因为实际上看到的不同 `A` 类型的数量比 `T` 类型的数量小得多。)
//
//
#[inline(never)]
fn finish_grow<A>(
    new_layout: Result<Layout, LayoutError>,
    current_memory: Option<(NonNull<u8>, Layout)>,
    alloc: &mut A,
) -> Result<NonNull<[u8]>, TryReserveError>
where
    A: Allocator,
{
    // 在此处检查错误，以最小化 `RawVec::grow_*` 的大小。
    let new_layout = new_layout.map_err(|_| CapacityOverflow)?;

    alloc_guard(new_layout.size())?;

    let memory = if let Some((ptr, old_layout)) = current_memory {
        debug_assert_eq!(old_layout.align(), new_layout.align());
        unsafe {
            // 分配器检查对齐是否相等
            intrinsics::assume(old_layout.align() == new_layout.align());
            alloc.grow(ptr, old_layout, new_layout)
        }
    } else {
        alloc.allocate(new_layout)
    };

    memory.map_err(|_| AllocError { layout: new_layout, non_exhaustive: () }.into())
}

unsafe impl<#[may_dangle] T, A: Allocator> Drop for RawVec<T, A> {
    /// 释放 `RawVec` 所拥有的内存，而无需尝试丢弃其内容。
    fn drop(&mut self) {
        if let Some((ptr, layout)) = self.current_memory() {
            unsafe { self.alloc.deallocate(ptr, layout) }
        }
    }
}

// 中央函数，用于保留错误处理。
#[cfg(not(no_global_oom_handling))]
#[inline]
fn handle_reserve(result: Result<(), TryReserveError>) {
    match result.map_err(|e| e.kind()) {
        Err(CapacityOverflow) => capacity_overflow(),
        Err(AllocError { layout, .. }) => handle_alloc_error(layout),
        Ok(()) => { /* yay */ }
    }
}

// 我们需要保证以下几点：
// * 我们永远不会分配 `> isize::MAX` 字节大小的对象。
// * 我们不会溢出 `usize::MAX`，而实际上分配得太少。
//
// 在 64 位上，我们只需要检查溢出，因为尝试分配 `> isize::MAX` 字节肯定会失败。
// 在 32 位和 16 位上，我们需要为此添加一个额外的保护措施，以防我们运行在可以使用 user-space 中所有 4GB 的平台上，例如 PAE 或 x32。
//
//

#[inline]
fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> {
    if usize::BITS < 64 && alloc_size > isize::MAX as usize {
        Err(CapacityOverflow.into())
    } else {
        Ok(())
    }
}

// 一个负责报告容量溢出的中央函数。
// 这将确保与这些 panics 相关的代码生成最少，因为在整个模块中只有一个位置 panics 而不是一堆。
//
#[cfg(not(no_global_oom_handling))]
fn capacity_overflow() -> ! {
    panic!("capacity overflow");
}