//! 内存分配 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]` 属性 (扩展该属性的代码宏将生成这些函数)，或调用 libstd 中的默认实现 (`__rdl_alloc` 等)。
    //
    // 在 `library/std/src/alloc.rs` 中)。
    // LLVM 的 rustc fork 还对这些函数名称进行特殊处理，以便分别优化它们，例如 `malloc`，`realloc` 和 `free`。
    //
    //
    #[rustc_allocator]
    #[rustc_allocator_nounwind]
    fn __rust_alloc(size: usize, align: usize) -> *mut u8;
    #[rustc_allocator_nounwind]
    fn __rust_dealloc(ptr: *mut u8, size: usize, align: usize);
    #[rustc_allocator_nounwind]
    fn __rust_realloc(ptr: *mut u8, old_size: usize, align: usize, new_size: usize) -> *mut u8;
    #[rustc_allocator_nounwind]
    fn __rust_alloc_zeroed(size: usize, align: usize) -> *mut u8;
}

/// 内存分配器。
///
/// 此类型通过将调用转发到用 `#[global_allocator]` 属性注册的分配器 (如果有的话) 或 `std` crate 的默认值来实现 [`Allocator`] trait。
///
///
/// Note: 尽管此类型不稳定，但是可以通过 [free functions in `alloc`](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, Layout};
///
/// unsafe {
///     let layout = Layout::new::<u16>();
///     let ptr = alloc(layout);
///
///     *(ptr as *mut u16) = 42;
///     assert_eq!(*(ptr as *mut u16), 42);
///
///     dealloc(ptr, layout);
/// }
/// ```
///
///
#[stable(feature = "global_alloc", since = "1.28.0")]
#[inline]
pub unsafe fn alloc(layout: Layout) -> *mut u8 {
    unsafe { __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")]
#[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")]
#[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)
            },
        }
    }
}

/// 唯一指针的分配器。
// 这个函数不能展开。如果是这样，MIR 代码生成将失败。
#[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(ptr.cast().into(), layout)
    }
}

// # 分配错误处理程序

#[cfg(not(no_global_oom_handling))]
extern "Rust" {
    // 这是调用 alloc 错误处理程序的神奇符号。
    // rustc 生成它以调用 `__rg_oom` (如果存在 `#[alloc_error_handler]`)，否则调用 (`__rdl_oom`) 以下的默认实现。
    //
    #[rustc_allocator_nounwind]
    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")]
#[cfg(all(not(no_global_oom_handling), not(test)))]
#[rustc_allocator_nounwind]
#[cold]
pub fn handle_alloc_error(layout: Layout) -> ! {
    unsafe {
        __rust_alloc_error_handler(layout.size(), layout.align());
    }
}

// 对于分配测试，可以直接使用 `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(any(target_os = "hermit", test))))]
#[doc(hidden)]
#[allow(unused_attributes)]
#[unstable(feature = "alloc_internals", issue = "none")]
pub mod __alloc_error_handler {
    use crate::alloc::Layout;

    // 通过生成的 `__rust_alloc_error_handler` 调用

    // 如果没有 `#[alloc_error_handler]`
    #[rustc_std_internal_symbol]
    pub unsafe extern "C" fn __rdl_oom(size: usize, _align: usize) -> ! {
        panic!("memory allocation of {} bytes failed", size)
    }

    // 如果有 `#[alloc_error_handler]`
    #[rustc_std_internal_symbol]
    pub unsafe extern "C" fn __rg_oom(size: usize, align: usize) -> ! {
        let layout = unsafe { Layout::from_size_align_unchecked(size, align) };
        extern "Rust" {
            #[lang = "oom"]
            fn oom_impl(layout: Layout) -> !;
        }
        unsafe { oom_impl(layout) }
    }
}

/// 将克隆专用于预分配的未初始化内存。
/// 由 `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) };
    }
}