//! 内存分配 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")]
#[deprecated(
    since = "1.52.0",
    note = "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::error::Error;
use crate::fmt;
use crate::ptr::{self, NonNull};

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

#[unstable(
    feature = "allocator_api",
    reason = "the precise API and guarantees it provides may be tweaked.",
    issue = "32838"
)]
impl Error for 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`，而不是 panic 或中止，但是这不是严格的要求。
    /// (具体来说：在一个底层的原生分配库上实现此 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`，而不是 panic 或中止，但是这不是严格的要求。
    /// (具体来说：在一个底层的原生分配库上实现此 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` 引用的内存块的所有权已转移到此分配器。
    /// 对旧 `ptr` 的任何访问都是未定义行为，即使分配是就地增长的。
    /// 新返回的指针是现在访问这块内存的唯一有效指针。
    ///
    /// 如果此方法返回 `Err`，则该存储块的所有权尚未转移到此分配器，并且该存储块的内容未更改。
    ///
    /// # Safety
    ///
    /// * `ptr` 必须通过这个分配器来表示一块内存 [*currently allocated*]。
    /// * `old_layout` 必须 [*fit*] 该内存块 (`new_layout` 参数不需要适合它。)。
    /// * `new_layout.size()` 必须大于或等于 `old_layout.size()`。
    ///
    /// 请注意，`new_layout.align()` 不必与 `old_layout.align()` 相同。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    ///
    /// # Errors
    ///
    /// 如果新布局不符合分配器的大小和分配器的对齐约束，或者如果增长失败，则返回 `Err`。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是 panic 或中止，但是这不是严格的要求。
    /// (具体来说：在一个底层的原生分配库上实现此 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()`。
    ///
    /// 请注意，`new_layout.align()` 不必与 `old_layout.align()` 相同。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    ///
    /// # Errors
    ///
    /// 如果新布局不符合分配器的大小和分配器的对齐约束，或者如果增长失败，则返回 `Err`。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是 panic 或中止，但是这不是严格的要求。
    /// (具体来说：在一个底层的原生分配库上实现此 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` 引用的内存块的所有权已转移到此分配器。
    /// 对旧 `ptr` 的任何访问都是未定义行为，即使分配已就地收缩。
    /// 新返回的指针是现在访问这块内存的唯一有效指针。
    ///
    /// 如果此方法返回 `Err`，则该存储块的所有权尚未转移到此分配器，并且该存储块的内容未更改。
    ///
    /// # Safety
    ///
    /// * `ptr` 必须通过这个分配器来表示一块内存 [*currently allocated*]。
    /// * `old_layout` 必须 [*fit*] 该内存块 (`new_layout` 参数不需要适合它。)。
    /// * `new_layout.size()` 必须小于或等于 `old_layout.size()`。
    ///
    /// 请注意，`new_layout.align()` 不必与 `old_layout.align()` 相同。
    ///
    /// [*currently allocated*]: #currently-allocated-memory
    /// [*fit*]: #memory-fitting
    ///
    /// # Errors
    ///
    /// 如果新的布局不符合分配器的大小和分配器的对齐约束，或者缩小失败，则返回 `Err`。
    ///
    /// 鼓励实现在内存耗尽时返回 `Err`，而不是 panic 或中止，但是这不是严格的要求。
    /// (具体来说：在一个底层的原生分配库上实现此 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) }
    }
}