//! 内存分配 API

#![stable(feature = "alloc_module", since = "1.28.0")]

mod global;
mod layout;

#[stable(feature = "global_alloc", since = "1.28.0")]
pub use self::global::GlobalAlloc;
#[stable(feature = "alloc_layout", since = "1.28.0")]
pub use self::layout::Layout;
#[stable(feature = "alloc_layout", since = "1.28.0")]
#[rustc_deprecated(
    since = "1.52.0",
    reason = "Name does not follow std convention, use LayoutError",
    suggestion = "LayoutError"
)]
#[allow(deprecated, deprecated_in_future)]
pub use self::layout::LayoutErr;

#[stable(feature = "alloc_layout_error", since = "1.50.0")]
pub use self::layout::LayoutError;

use crate::fmt;
use crate::ptr::{self, NonNull};

/// `AllocError` 错误表示分配失败，这可能是由于资源耗尽或将给定输入参数与此分配器组合在一起时出错所致。
///
///
///
#[unstable(feature = "allocator_api", issue = "32838")]
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
pub struct AllocError;

// (对于 trait 错误的下游隐含我们需要此功能)
#[unstable(feature = "allocator_api", issue = "32838")]
impl fmt::Display for AllocError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("memory allocation failed")
    }
}

/// `Allocator` 的实现可以分配，增长，收缩和释放通过 [`Layout`][] 描述的任意数据块。
///
/// `Allocator` 之所以将其设计为在 ZST，引用或智能指针上实现，是因为如果不更新指向已分配内存的指针，则无法移动具有 `MyAlloc([u8; N])` 之类的分配器。
///
/// 与 [`GlobalAlloc`][] 不同，`Allocator` 允许零大小的分配。
/// 如果基础分配器不支持此功能 (例如 jemalloc) 或返回空指针 (例如 `libc::malloc`)，则必须由实现捕获。
///
/// ### 当前分配的内存
///
/// 某些方法要求通过分配器 *currently* 分配存储块。这意味着:
///
/// * 该内存块的起始地址先前由 [`allocate`]，[`grow`] 或 [`shrink`] 返回，并且
///
/// * 内存块随后并未被释放，其中的块要么通过传递到 [`deallocate`] 直接释放，要么通过传递到返回 `Ok` 的 [`grow`] 或 [`shrink`] 进行了更改。
///
/// 如果 `grow` 或 `shrink` 返回了 `Err`，则传递的指针保持有效。
///
/// [`allocate`]: Allocator::allocate
/// [`grow`]: Allocator::grow
/// [`shrink`]: Allocator::shrink
/// [`deallocate`]: Allocator::deallocate
///
/// ### 内存拟合
///
/// 有些方法要求布局适合内存块。
/// 对于到 "fit" 的布局，存储块意味着 (或者，对于到 "fit" 的存储块，布局意味着) 必须满足以下条件:
///
/// * 必须以与 [`layout.align()`] 相同的对齐方式分配该块，并且
///
/// * 提供的 [`layout.size()`] 必须在 `min ..= max` 范围内，其中:
///   - `min` 是最近用于分配块的布局的大小，并且
///   - `max` 是从 [`allocate`]，[`grow`] 或 [`shrink`] 返回的最新实际大小。
///
/// [`layout.align()`]: Layout::align
/// [`layout.size()`]: Layout::size
///
/// # Safety
///
/// * 从分配器返回的内存块必须指向有效内存并保持其有效性，直到丢弃实例及其所有克隆为止，
///
/// * 克隆或移动分配器不得使此分配器返回的内存块无效。克隆的分配器的行为必须类似于相同的分配器，并且
///
/// * 指向 [*currently allocated*] 的存储块的任何指针都可以传递给分配器的任何其他方法。
///
/// [*currently allocated*]: #currently-allocated-memory
///
///
///
///
///
///
///
///
///
///
///
#[unstable(feature = "allocator_api", issue = "32838")]
pub unsafe trait Allocator {
    /// 尝试分配一块内存。
    ///
    /// 成功后，返回满足 `layout` 大小和对齐保证的 [`NonNull<[u8]>`][NonNull]。
    ///
    /// 返回的块的大小可能大于 `layout.size()` 指定的大小，并且可能已初始化或未初始化其内容。
    ///
    /// # Errors
    ///
    /// 返回 `Err` 表示内存已耗尽，或者 `layout` 不满足分配器的大小或对齐约束。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是恐慌或终止，但是这不是严格的要求。
    /// (具体来说: 在一个底层的原生分配库上实现此 trait 是 *合法的*，该本地分配库在内存耗尽时中止。)
    ///
    /// 鼓励希望因分配错误而终止计算的客户调用 [`handle_alloc_error`] 函数，而不是直接调用 `panic!` 或类似方法。
    ///
    ///
    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
    ///
    ///
    ///
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;

    /// 行为类似于 `allocate`，但也确保返回的内存被零初始化。
    ///
    /// # Errors
    ///
    /// 返回 `Err` 表示内存已耗尽，或者 `layout` 不满足分配器的大小或对齐约束。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是恐慌或终止，但是这不是严格的要求。
    /// (具体来说: 在一个底层的原生分配库上实现此 trait 是 *合法的*，该本地分配库在内存耗尽时中止。)
    ///
    /// 鼓励希望因分配错误而终止计算的客户调用 [`handle_alloc_error`] 函数，而不是直接调用 `panic!` 或类似方法。
    ///
    ///
    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
    ///
    ///
    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        let ptr = self.allocate(layout)?;
        // SAFETY: `alloc` 返回有效的内存块
        unsafe { ptr.as_non_null_ptr().as_ptr().write_bytes(0, ptr.len()) }
        Ok(ptr)
    }

    /// 释放 `ptr` 引用的内存。
    ///
    /// # Safety
    ///
    /// * `ptr` 必须通过此分配器表示一个内存块 [*currently allocated*]，并且
    /// * `layout` 必须 [*fit*] 该内存块。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);

    /// 尝试扩展内存块。
    ///
    /// 返回一个新的 [`NonNull<[u8]>`][NonNull]，其中包含一个指针和分配的内存的实际大小。该指针适用于保存 `new_layout` 描述的数据。
    /// 为此，分配器可以扩展 `ptr` 引用的分配以适合新的布局。
    ///
    /// 如果返回 `Ok`，则 `ptr` 引用的内存块的所有权已转移到此分配器。
    /// 内存可能已释放，也可能尚未释放，除非已通过此方法的返回值再次将其转移回调用方，否则应将其视为不可用。
    ///
    /// 如果此方法返回 `Err`，则该存储块的所有权尚未转移到此分配器，并且该存储块的内容未更改。
    ///
    /// # Safety
    ///
    /// * `ptr` 必须通过此分配器表示一个内存 [*currently allocated*] 块。
    /// * `old_layout` 必须 [*fit*] 该内存块 (`new_layout` 参数不需要适合它。)。
    /// * `new_layout.size()` 必须大于或等于 `old_layout.size()`。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    ///
    /// # Errors
    ///
    /// 如果新布局不符合分配器的大小和分配器的对齐约束，或者如果增长失败，则返回 `Err`。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是恐慌或终止，但是这不是严格的要求。
    /// (具体来说: 在一个底层的原生分配库上实现此 trait 是 *合法的*，该本地分配库在内存耗尽时中止。)
    ///
    /// 鼓励希望因分配错误而终止计算的客户调用 [`handle_alloc_error`] 函数，而不是直接调用 `panic!` 或类似方法。
    ///
    ///
    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
    ///
    ///
    ///
    ///
    ///
    ///
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        debug_assert!(
            new_layout.size() >= old_layout.size(),
            "`new_layout.size()` must be greater than or equal to `old_layout.size()`"
        );

        let new_ptr = self.allocate(new_layout)?;

        // SAFETY: 因为 `new_layout.size()` 必须大于或等于 `old_layout.size()`，所以旧的和新的内存分配对于 `old_layout.size()` 字节的读取和写入均有效。
        // 另外，由于尚未分配旧分配，因此它不能与 `new_ptr` 重叠。
        // 因此，调用 `copy_nonoverlapping` 是安全的。
        // 调用者必须遵守 `dealloc` 的安全保证。
        //
        unsafe {
            ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_layout.size());
            self.deallocate(ptr, old_layout);
        }

        Ok(new_ptr)
    }

    /// 行为类似于 `grow`，但也确保在返回新内容之前将其设置为零。
    ///
    /// 成功调用后，该存储块将包含以下内容
    /// `grow_zeroed`:
    ///   * 字节 `0..old_layout.size()` 从原始分配中保留。
    ///   * 字节 `old_layout.size()..old_size` 将保留还是清零，具体取决于分配器的实现。
    ///   `old_size` 指的是 `grow_zeroed` 调用之前的内存块的大小，它可能大于分配时最初请求的大小。
    ///   * 字节 `old_size..new_size` 被清零。`new_size` 是指 `grow_zeroed` 调用返回的存储块的大小。
    ///
    /// # Safety
    ///
    /// * `ptr` 必须通过此分配器表示一个内存 [*currently allocated*] 块。
    /// * `old_layout` 必须 [*fit*] 该内存块 (`new_layout` 参数不需要适合它。)。
    /// * `new_layout.size()` 必须大于或等于 `old_layout.size()`。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    ///
    /// # Errors
    ///
    /// 如果新布局不符合分配器的大小和分配器的对齐约束，或者如果增长失败，则返回 `Err`。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是恐慌或终止，但是这不是严格的要求。
    /// (具体来说: 在一个底层的原生分配库上实现此 trait 是 *合法的*，该本地分配库在内存耗尽时中止。)
    ///
    /// 鼓励希望因分配错误而终止计算的客户调用 [`handle_alloc_error`] 函数，而不是直接调用 `panic!` 或类似方法。
    ///
    ///
    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
    ///
    ///
    ///
    ///
    ///
    ///
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        debug_assert!(
            new_layout.size() >= old_layout.size(),
            "`new_layout.size()` must be greater than or equal to `old_layout.size()`"
        );

        let new_ptr = self.allocate_zeroed(new_layout)?;

        // SAFETY: 因为 `new_layout.size()` 必须大于或等于 `old_layout.size()`，所以旧的和新的内存分配对于 `old_layout.size()` 字节的读取和写入均有效。
        // 另外，由于尚未分配旧分配，因此它不能与 `new_ptr` 重叠。
        // 因此，调用 `copy_nonoverlapping` 是安全的。
        // 调用者必须遵守 `dealloc` 的安全保证。
        //
        unsafe {
            ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_layout.size());
            self.deallocate(ptr, old_layout);
        }

        Ok(new_ptr)
    }

    /// 尝试缩小内存块。
    ///
    /// 返回一个新的 [`NonNull<[u8]>`][NonNull]，其中包含一个指针和分配的内存的实际大小。该指针适用于保存 `new_layout` 描述的数据。
    /// 为此，分配器可以缩小 `ptr` 引用的分配以适合新的布局。
    ///
    /// 如果返回 `Ok`，则 `ptr` 引用的内存块的所有权已转移到此分配器。
    /// 内存可能已释放，也可能尚未释放，除非已通过此方法的返回值再次将其转移回调用方，否则应将其视为不可用。
    ///
    /// 如果此方法返回 `Err`，则该存储块的所有权尚未转移到此分配器，并且该存储块的内容未更改。
    ///
    /// # Safety
    ///
    /// * `ptr` 必须通过此分配器表示一个内存 [*currently allocated*] 块。
    /// * `old_layout` 必须 [*fit*] 该内存块 (`new_layout` 参数不需要适合它。)。
    /// * `new_layout.size()` 必须小于或等于 `old_layout.size()`。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    ///
    /// # Errors
    ///
    /// 如果新的布局不符合分配器的大小和分配器的对齐约束，或者缩小失败，则返回 `Err`。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是恐慌或终止，但是这不是严格的要求。
    /// (具体来说: 在一个底层的原生分配库上实现此 trait 是 *合法的*，该本地分配库在内存耗尽时中止。)
    ///
    /// 鼓励希望因分配错误而终止计算的客户调用 [`handle_alloc_error`] 函数，而不是直接调用 `panic!` 或类似方法。
    ///
    ///
    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
    ///
    ///
    ///
    ///
    ///
    ///
    unsafe fn shrink(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        debug_assert!(
            new_layout.size() <= old_layout.size(),
            "`new_layout.size()` must be smaller than or equal to `old_layout.size()`"
        );

        let new_ptr = self.allocate(new_layout)?;

        // SAFETY: 因为 `new_layout.size()` 必须小于或等于 `old_layout.size()`，所以旧的和新的内存分配对于 `new_layout.size()` 字节的读取和写入均有效。
        // 另外，由于尚未分配旧分配，因此它不能与 `new_ptr` 重叠。
        // 因此，调用 `copy_nonoverlapping` 是安全的。
        // 调用者必须遵守 `dealloc` 的安全保证。
        //
        unsafe {
            ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), new_layout.size());
            self.deallocate(ptr, old_layout);
        }

        Ok(new_ptr)
    }

    /// 为此 `Allocator` 实例创建 "by reference" 适配器。
    ///
    /// 返回的适配器还实现了 `Allocator`，将仅借用此适配器。
    #[inline(always)]
    fn by_ref(&self) -> &Self
    where
        Self: Sized,
    {
        self
    }
}

#[unstable(feature = "allocator_api", issue = "32838")]
unsafe impl<A> Allocator for &A
where
    A: Allocator + ?Sized,
{
    #[inline]
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        (**self).allocate(layout)
    }

    #[inline]
    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        (**self).allocate_zeroed(layout)
    }

    #[inline]
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        // SAFETY: 调用者必须坚持安全保证
        unsafe { (**self).deallocate(ptr, layout) }
    }

    #[inline]
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        // SAFETY: 调用者必须坚持安全保证
        unsafe { (**self).grow(ptr, old_layout, new_layout) }
    }

    #[inline]
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        // SAFETY: 调用者必须坚持安全保证
        unsafe { (**self).grow_zeroed(ptr, old_layout, new_layout) }
    }

    #[inline]
    unsafe fn shrink(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        // SAFETY: 调用者必须坚持安全保证
        unsafe { (**self).shrink(ptr, old_layout, new_layout) }
    }
}