//! 内存分配 API

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

#[cfg(not(test))]
use core::intrinsics;
use core::intrinsics::{min_align_of_val, size_of_val};

use core::ptr::Unique;
#[cfg(not(test))]
use core::ptr::{self, NonNull};

#[stable(feature = "alloc_module", since = "1.28.0")]
#[doc(inline)]
pub use core::alloc::*;

#[cfg(test)]
mod tests;

extern "Rust" {
    // 这些是调用分配器的魔术符号。rustc 生成它们以调用 `__rg_alloc` 等。
    // 如果有 `#[global_allocator]` 属性 (扩展该属性宏的代码生成那些函数)，或者调用 std 中的默认实现 (`__rdl_alloc` 等。
    //
    // 在 `library/std/src/alloc.rs` 中)。
    // LLVM 14 和更早版本的 rustc fork 还对这些函数名称进行了特殊处理，以便能够分别优化它们，如 `malloc`、`realloc` 和 `free`。
    //
    //
    #[rustc_allocator]
    #[rustc_nounwind]
    fn __rust_alloc(size: usize, align: usize) -> *mut u8;
    #[rustc_deallocator]
    #[rustc_nounwind]
    fn __rust_dealloc(ptr: *mut u8, size: usize, align: usize);
    #[rustc_reallocator]
    #[rustc_nounwind]
    fn __rust_realloc(ptr: *mut u8, old_size: usize, align: usize, new_size: usize) -> *mut u8;
    #[rustc_allocator_zeroed]
    #[rustc_nounwind]
    fn __rust_alloc_zeroed(size: usize, align: usize) -> *mut u8;

    #[cfg(not(bootstrap))]
    static __rust_no_alloc_shim_is_unstable: u8;
}

/// 全局内存分配器。
///
/// 此类型通过将调用转发到用 `#[global_allocator]` 属性注册的分配器 (如果有的话) 或 `std` crate 的默认值来实现 [`Allocator`] trait。
///
///
/// Note: 尽管此类型不稳定，但是可以通过 [`alloc` 中的 free 函数](self#functions) 访问其提供的功能。
///
///
#[unstable(feature = "allocator_api", issue = "32838")]
#[derive(Copy, Clone, Default, Debug)]
#[cfg(not(test))]
pub struct Global;

#[cfg(test)]
pub use std::alloc::Global;

/// 使用全局分配器分配内存。
///
/// 如果存在，则此函数将调用转发到用 `#[global_allocator]` 属性注册的分配器的 [`GlobalAlloc::alloc`] 方法，或者将其默认为 `std` crate。
///
///
/// 当 [`Global`] 类型的 `alloc` 方法和 [`Allocator`] trait 变得稳定时，应优先使用此函数，而不是 [`Global`] 类型的 `alloc` 方法。
///
/// # Safety
///
/// 请参见 [`GlobalAlloc::alloc`]。
///
/// # Examples
///
/// ```
/// use std::alloc::{alloc, dealloc, handle_alloc_error, Layout};
///
/// unsafe {
///     let layout = Layout::new::<u16>();
///     let ptr = alloc(layout);
///     if ptr.is_null() {
///         handle_alloc_error(layout);
///     }
///
///     *(ptr as *mut u16) = 42;
///     assert_eq!(*(ptr as *mut u16), 42);
///
///     dealloc(ptr, layout);
/// }
/// ```
///
///
#[stable(feature = "global_alloc", since = "1.28.0")]
#[must_use = "losing the pointer will leak memory"]
#[inline]
pub unsafe fn alloc(layout: Layout) -> *mut u8 {
    unsafe {
        // 确保我们不会意外地允许在稳定代码中省略分配器垫片，直到它真正稳定下来。
        //
        #[cfg(not(bootstrap))]
        core::ptr::read_volatile(&__rust_no_alloc_shim_is_unstable);

        __rust_alloc(layout.size(), layout.align())
    }
}

/// 使用全局分配器释放内存。
///
/// 如果存在，则此函数将调用转发到用 `#[global_allocator]` 属性注册的分配器的 [`GlobalAlloc::dealloc`] 方法，或者将其默认为 `std` crate。
///
///
/// 当 [`Global`] 类型的 `dealloc` 方法和 [`Allocator`] trait 变得稳定时，应优先使用此函数，而不是 [`Global`] 类型的 `dealloc` 方法。
///
/// # Safety
///
/// 请参见 [`GlobalAlloc::dealloc`]。
///
///
#[stable(feature = "global_alloc", since = "1.28.0")]
#[inline]
pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) {
    unsafe { __rust_dealloc(ptr, layout.size(), layout.align()) }
}

/// 使用全局分配器重新分配内存。
///
/// 如果存在，则此函数将调用转发到用 `#[global_allocator]` 属性注册的分配器的 [`GlobalAlloc::realloc`] 方法，或者将其默认为 `std` crate。
///
///
/// 当 [`Global`] 类型的 `realloc` 方法和 [`Allocator`] trait 变得稳定时，应优先使用此函数，而不是 [`Global`] 类型的 `realloc` 方法。
///
/// # Safety
///
/// 请参见 [`GlobalAlloc::realloc`]。
///
///
#[stable(feature = "global_alloc", since = "1.28.0")]
#[must_use = "losing the pointer will leak memory"]
#[inline]
pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
    unsafe { __rust_realloc(ptr, layout.size(), layout.align(), new_size) }
}

/// 使用全局分配器分配零初始化内存。
///
/// 如果存在，则此函数将调用转发到用 `#[global_allocator]` 属性注册的分配器的 [`GlobalAlloc::alloc_zeroed`] 方法，或者将其默认为 `std` crate。
///
///
/// 当 [`Global`] 类型的 `alloc_zeroed` 方法和 [`Allocator`] trait 变得稳定时，应优先使用此函数，而不是 [`Global`] 类型的 `alloc_zeroed` 方法。
///
/// # Safety
///
/// 请参见 [`GlobalAlloc::alloc_zeroed`]。
///
/// # Examples
///
/// ```
/// use std::alloc::{alloc_zeroed, dealloc, Layout};
///
/// unsafe {
///     let layout = Layout::new::<u16>();
///     let ptr = alloc_zeroed(layout);
///
///     assert_eq!(*(ptr as *mut u16), 0);
///
///     dealloc(ptr, layout);
/// }
/// ```
///
///
#[stable(feature = "global_alloc", since = "1.28.0")]
#[must_use = "losing the pointer will leak memory"]
#[inline]
pub unsafe fn alloc_zeroed(layout: Layout) -> *mut u8 {
    unsafe { __rust_alloc_zeroed(layout.size(), layout.align()) }
}

#[cfg(not(test))]
impl Global {
    #[inline]
    fn alloc_impl(&self, layout: Layout, zeroed: bool) -> Result<NonNull<[u8]>, AllocError> {
        match layout.size() {
            0 => Ok(NonNull::slice_from_raw_parts(layout.dangling(), 0)),
            // SAFETY: `layout` 的大小不为零，
            size => unsafe {
                let raw_ptr = if zeroed { alloc_zeroed(layout) } else { alloc(layout) };
                let ptr = NonNull::new(raw_ptr).ok_or(AllocError)?;
                Ok(NonNull::slice_from_raw_parts(ptr, size))
            },
        }
    }

    // SAFETY: 与 `Allocator::grow` 相同
    #[inline]
    unsafe fn grow_impl(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
        zeroed: bool,
    ) -> 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()`"
        );

        match old_layout.size() {
            0 => self.alloc_impl(new_layout, zeroed),

            // SAFETY: `new_size` 为非零值，因为根据安全条件的要求，`old_size` 大于或等于 `new_size`。
            // 调用者必须遵守的其他条件
            old_size if old_layout.align() == new_layout.align() => unsafe {
                let new_size = new_layout.size();

                // `realloc` 可能会检查 `new_size >= old_layout.size()` 或类似的东西。
                intrinsics::assume(new_size >= old_layout.size());

                let raw_ptr = realloc(ptr.as_ptr(), old_layout, new_size);
                let ptr = NonNull::new(raw_ptr).ok_or(AllocError)?;
                if zeroed {
                    raw_ptr.add(old_size).write_bytes(0, new_size - old_size);
                }
                Ok(NonNull::slice_from_raw_parts(ptr, new_size))
            },

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

#[unstable(feature = "allocator_api", issue = "32838")]
#[cfg(not(test))]
unsafe impl Allocator for Global {
    #[inline]
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        self.alloc_impl(layout, false)
    }

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

    #[inline]
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        if layout.size() != 0 {
            // SAFETY: `layout` 的大小非零，调用者必须保持其他条件
            //
            unsafe { dealloc(ptr.as_ptr(), layout) }
        }
    }

    #[inline]
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        // SAFETY: 调用者必须遵守所有条件
        unsafe { self.grow_impl(ptr, old_layout, new_layout, false) }
    }

    #[inline]
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        // SAFETY: 调用者必须遵守所有条件
        unsafe { self.grow_impl(ptr, old_layout, new_layout, true) }
    }

    #[inline]
    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()`"
        );

        match new_layout.size() {
            // SAFETY: 调用者必须遵守条件
            0 => unsafe {
                self.deallocate(ptr, old_layout);
                Ok(NonNull::slice_from_raw_parts(new_layout.dangling(), 0))
            },

            // SAFETY: `new_size` 不为零。调用者必须遵守的其他条件
            new_size if old_layout.align() == new_layout.align() => unsafe {
                // `realloc` 可能会检查 `new_size <= old_layout.size()` 或类似的东西。
                intrinsics::assume(new_size <= old_layout.size());

                let raw_ptr = realloc(ptr.as_ptr(), old_layout, new_size);
                let ptr = NonNull::new(raw_ptr).ok_or(AllocError)?;
                Ok(NonNull::slice_from_raw_parts(ptr, new_size))
            },

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

/// 唯一指针的分配器。
#[cfg(all(not(no_global_oom_handling), not(test)))]
#[lang = "exchange_malloc"]
#[inline]
unsafe fn exchange_malloc(size: usize, align: usize) -> *mut u8 {
    let layout = unsafe { Layout::from_size_align_unchecked(size, align) };
    match Global.allocate(layout) {
        Ok(ptr) => ptr.as_mut_ptr(),
        Err(_) => handle_alloc_error(layout),
    }
}

#[cfg_attr(not(test), lang = "box_free")]
#[inline]
// 该签名必须与 `Box` 相同，否则将发生 ICE。
// 当添加了 `Box` 的附加参数 (如 `A: Allocator`) 时，也必须在此处添加该参数。
// 例如，如果 `Box` 更改为 `struct Box<T: ?Sized, A: Allocator>(Unique<T>, A)`，则该函数也必须更改为 `fn box_free<T: ?Sized, A: Allocator>(Unique<T>, A)`。
//
//
pub(crate) unsafe fn box_free<T: ?Sized, A: Allocator>(ptr: Unique<T>, alloc: A) {
    unsafe {
        let size = size_of_val(ptr.as_ref());
        let align = min_align_of_val(ptr.as_ref());
        let layout = Layout::from_size_align_unchecked(size, align);
        alloc.deallocate(From::from(ptr.cast()), layout)
    }
}

// # 分配错误处理程序

#[cfg(not(no_global_oom_handling))]
extern "Rust" {
    // 这是调用 alloc 错误处理程序的神奇符号。
    // rustc 生成它以调用 `__rg_oom` (如果存在 `#[alloc_error_handler]`)，否则调用 (`__rdl_oom`) 以下的默认实现。
    //
    fn __rust_alloc_error_handler(size: usize, align: usize) -> !;
}

/// 由于内存分配错误或失败而中止。
///
/// 鼓励希望响应分配错误而中止计算的内存分配 API 调用程序调用此函数，而不是直接调用 `panic!` 或类似方法。
///
///
/// 该函数的默认行为是将一条消息打印到标准错误并中止该进程。
/// 可以将其替换为 [`set_alloc_error_hook`] 和 [`take_alloc_error_hook`]。
///
/// [`set_alloc_error_hook`]: ../../std/alloc/fn.set_alloc_error_hook.html
/// [`take_alloc_error_hook`]: ../../std/alloc/fn.take_alloc_error_hook.html
///
///
#[stable(feature = "global_alloc", since = "1.28.0")]
#[rustc_const_unstable(feature = "const_alloc_error", issue = "92523")]
#[cfg(all(not(no_global_oom_handling), not(test)))]
#[cold]
pub const fn handle_alloc_error(layout: Layout) -> ! {
    const fn ct_error(_: Layout) -> ! {
        panic!("allocation failed");
    }

    fn rt_error(layout: Layout) -> ! {
        unsafe {
            __rust_alloc_error_handler(layout.size(), layout.align());
        }
    }

    unsafe { core::intrinsics::const_eval_select((layout,), ct_error, rt_error) }
}

// 对于分配测试，可以直接使用 `std::alloc::handle_alloc_error`。
#[cfg(all(not(no_global_oom_handling), test))]
pub use std::alloc::handle_alloc_error;

#[cfg(all(not(no_global_oom_handling), not(test)))]
#[doc(hidden)]
#[allow(unused_attributes)]
#[unstable(feature = "alloc_internals", issue = "none")]
pub mod __alloc_error_handler {
    // 如果没有 `#[alloc_error_handler]`，则通过生成的 `__rust_alloc_error_handler` 调用。
    //
    #[rustc_std_internal_symbol]
    pub unsafe fn __rdl_oom(size: usize, _align: usize) -> ! {
        extern "Rust" {
            // 该符号由 __rust_alloc_error_handler 旁边的 rustc 发出。
            // 它的值取决于 - Zoom={panic,abort} 编译器选项。
            static __rust_alloc_error_handler_should_panic: u8;
        }

        #[allow(unused_unsafe)]
        if unsafe { __rust_alloc_error_handler_should_panic != 0 } {
            panic!("memory allocation of {size} bytes failed")
        } else {
            core::panicking::panic_nounwind_fmt(format_args!(
                "memory allocation of {size} bytes failed"
            ))
        }
    }
}

/// 将克隆专用于预先分配的、未初始化的内存。
/// 由 `Box::clone` 和 `Rc`/`Arc::make_mut` 使用。
pub(crate) trait WriteCloneIntoRaw: Sized {
    unsafe fn write_clone_into_raw(&self, target: *mut Self);
}

impl<T: Clone> WriteCloneIntoRaw for T {
    #[inline]
    default unsafe fn write_clone_into_raw(&self, target: *mut Self) {
        // 分配 *first* 后，优化器可以就地创建克隆的值，而跳过本地并移动。
        //
        unsafe { target.write(self.clone()) };
    }
}

impl<T: Copy> WriteCloneIntoRaw for T {
    #[inline]
    unsafe fn write_clone_into_raw(&self, target: *mut Self) {
        // 我们始终可以就地复制，而无需涉及本地值。
        unsafe { target.copy_from_nonoverlapping(self, 1) };
    }
}