use crate::cmp;
use crate::fmt;
use crate::mem;
use crate::num::NonZeroUsize;
use crate::ptr::NonNull;

// 虽然此函数在一个地方使用过，并且可以内联其实现，但是以前的尝试使 rustc 变慢了:
//
//
// * https://github.com/rust-lang/rust/pull/72189
// * https://github.com/rust-lang/rust/pull/79827
//
const fn size_align<T>() -> (usize, usize) {
    (mem::size_of::<T>(), mem::align_of::<T>())
}

/// 一块内存的布局。
///
/// `Layout` 的实例描述了特定的内存布局。
/// 您将 `Layout` 作为输入分配给分配器。
///
/// 所有布局都具有关联的大小和 2 的幂次对齐。
///
/// (请注意，布局不要求具有非零大小，即使 `GlobalAlloc` 要求所有内存请求的大小为非零。
/// 调用方必须确保满足这样的条件，使用要求较宽松的特定分配器，或者使用更宽松的 `Allocator` 接口。)
///
///
///
#[stable(feature = "alloc_layout", since = "1.28.0")]
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
#[lang = "alloc_layout"]
pub struct Layout {
    // 请求的内存块的大小，以字节为单位。
    size_: usize,

    // 请求的内存块的对齐方式，以字节为单位。
    // 我们确保这始终是 2 的幂，因为像 `posix_memalign` 这样的 API 都需要这样做，并且强加给 Layout 构造函数是一个合理的约束。
    //
    //
    // (但是，我们类似地不要求 `align>= sizeof(void *)`, even though that is* also* a requirement of `posix_memalign`.)
    //
    //
    align_: NonZeroUsize,
}

impl Layout {
    /// 从给定的 `size` 和 `align` 创建 `Layout`，或者如果不满足以下任何条件，则返回 `LayoutError`:
    ///
    /// * `align` 不能为零，
    ///
    /// * `align` 必须是 2 的幂
    ///
    /// * `size`, 当四舍五入到最接近的 `align` 倍数时，一定不能溢出 (即，四舍五入的值必须小于或等于 `usize::MAX`)。
    ///
    ///
    ///
    ///
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "const_alloc_layout", since = "1.50.0")]
    #[inline]
    pub const fn from_size_align(size: usize, align: usize) -> Result<Self, LayoutError> {
        if !align.is_power_of_two() {
            return Err(LayoutError);
        }

        // (2 的幂表示 align=0。)

        // 舍入后的大小为:
        //   size_rounded_up = (size + align - 1) & !(align - 1);
        //
        // 从上面我们知道 align! =0。
        // 如果加法 (align-1) 没有溢出，则四舍五入是可以的。
        //
        // 相反，&-masking with! (align-1) 将仅减去低位。
        // 因此，如果总和发生溢出，则 &-mask cannot 减去足以抵消该溢出。
        //
        //
        // 以上暗示检查总和溢出是否必要和充分。
        //
        if size > usize::MAX - (align - 1) {
            return Err(LayoutError);
        }

        // SAFETY: `from_size_align_unchecked` 的条件已在上面进行了检查。
        //
        unsafe { Ok(Layout::from_size_align_unchecked(size, align)) }
    }

    /// 创建一个布局，绕过所有检查。
    ///
    /// # Safety
    ///
    /// 此函数不安全，因为它无法验证 [`Layout::from_size_align`] 的前提条件。
    ///
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "alloc_layout", since = "1.36.0")]
    #[inline]
    pub const unsafe fn from_size_align_unchecked(size: usize, align: usize) -> Self {
        // SAFETY: 调用者必须确保 `align` 大于零。
        Layout { size_: size, align_: unsafe { NonZeroUsize::new_unchecked(align) } }
    }

    /// 此布局的存储块的最小大小 (以字节为单位)。
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "const_alloc_layout", since = "1.50.0")]
    #[inline]
    pub const fn size(&self) -> usize {
        self.size_
    }

    /// 此布局的存储块的最小字节对齐。
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "const_alloc_layout", since = "1.50.0")]
    #[inline]
    pub const fn align(&self) -> usize {
        self.align_.get()
    }

    /// 创建一个适合保存 `T` 类型值的 `Layout`。
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "alloc_layout_const_new", since = "1.42.0")]
    #[inline]
    pub const fn new<T>() -> Self {
        let (size, align) = size_align::<T>();
        // SAFETY: Rust 保证 align 为 2 的幂，并且 size + align 组合保证适合我们的地址空间。
        // 结果，如果未对 panics 进行最佳优化，请在此处使用未经检查的构造函数，以免插入 panics 的代码。
        //
        //
        unsafe { Layout::from_size_align_unchecked(size, align) }
    }

    /// 产生描述记录的布局，该记录可用于为 `T` 分配支持结构 (可以是 trait 或其他未定义大小的类型，例如切片)。
    ///
    ///
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[inline]
    pub fn for_value<T: ?Sized>(t: &T) -> Self {
        let (size, align) = (mem::size_of_val(t), mem::align_of_val(t));
        debug_assert!(Layout::from_size_align(size, align).is_ok());
        // SAFETY: 有关为什么使用不安全成员的信息，请参见 `new` 中的基本原理。
        unsafe { Layout::from_size_align_unchecked(size, align) }
    }

    /// 产生描述记录的布局，该记录可用于为 `T` 分配支持结构 (可以是 trait 或其他未定义大小的类型，例如切片)。
    ///
    /// # Safety
    ///
    /// 仅在满足以下条件时，此函数才可以安全调用:
    ///
    /// - 如果 `T` 是 `Sized`，则调用该函数始终是安全的。
    /// - 如果 `T` 的未定义大小的尾部为:
    ///     - [slice]，则切片尾部的长度必须是一个初始化整数，并且 *entire 值*(动态尾部长度 + 静态大小的前缀) 的大小必须适合 `isize`。
    ///     - [trait object]，则指针的 vtable 部分必须指向通过未调整大小的强制性获得的 `T` 类型的有效 vtable，并且 *entire 值*(动态尾部长度 + 静态大小的前缀) 的大小必须适合 `isize`。
    ///
    ///     - (unstable) [extern type]，则此函数始终可以安全调用，但可能会 panic 或以其他方式返回错误的值，因为外部类型的布局未知。
    ///     这与在外部类型尾巴上引用 [`Layout::for_value`] 时的行为相同。
    ///     - 否则，保守地不允许调用此函数。
    ///
    /// [trait object]: ../../book/ch17-02-trait-objects.html
    /// [extern type]: ../../unstable-book/language-features/extern-types.html
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[unstable(feature = "layout_for_ptr", issue = "69835")]
    pub unsafe fn for_value_raw<T: ?Sized>(t: *const T) -> Self {
        // SAFETY: 我们将这些函数的先决条件传递给调用者
        let (size, align) = unsafe { (mem::size_of_val_raw(t), mem::align_of_val_raw(t)) };
        debug_assert!(Layout::from_size_align(size, align).is_ok());
        // SAFETY: 有关为什么使用不安全成员的信息，请参见 `new` 中的基本原理。
        unsafe { Layout::from_size_align_unchecked(size, align) }
    }

    /// 创建一个悬空的 `NonNull`，但此 Layout 非常适合该 `NonNull`。
    ///
    /// 请注意，该指针值可能表示一个有效的指针，这意味着不得将其用作 "not yet initialized" 标记值。
    /// 延迟分配的类型必须通过其他某种方式来跟踪初始化。
    ///
    ///
    #[unstable(feature = "alloc_layout_extra", issue = "55724")]
    #[rustc_const_unstable(feature = "alloc_layout_extra", issue = "55724")]
    #[inline]
    pub const fn dangling(&self) -> NonNull<u8> {
        // SAFETY: align 保证为非零
        unsafe { NonNull::new_unchecked(self.align() as *mut u8) }
    }

    /// 创建一个描述记录的布局，该记录可以保留与 `self` 相同的布局值，但也与对齐方式 `align` 对齐 (以字节为单位)。
    ///
    ///
    /// 如果 `self` 已经满足规定的对齐方式，则返回 `self`。
    ///
    /// 请注意，无论返回的布局是否具有不同的对齐方式，此方法都不会在整体大小上添加任何填充。
    /// 换句话说，如果 `K` 的大小为 16，则 `K.align_to(32)`*仍* 的大小为 16。
    ///
    /// 如果 `self.size()` 和给定的 `align` 的组合违反 [`Layout::from_size_align`] 中列出的条件，则返回错误。
    ///
    ///
    ///
    ///
    ///
    #[stable(feature = "alloc_layout_manipulation", since = "1.44.0")]
    #[inline]
    pub fn align_to(&self, align: usize) -> Result<Self, LayoutError> {
        Layout::from_size_align(self.size(), cmp::max(self.align(), align))
    }

    /// 返回必须在 `self` 之后插入的填充量，以确保以下地址满足 `align` (以字节为单位)。
    ///
    /// 例如，如果 `self.size()` 为 9，则 `self.padding_needed_for(4)` 返回 3，因为这是获得 4 对齐地址所需的最小填充字节数 (假设相应的存储块从 4 对齐地址开始)。
    ///
    ///
    /// 如果 `align` 不是 2 的幂，则此函数的返回值没有意义。
    ///
    /// 注意，返回值的实用程序要求 `align` 小于或等于整个分配的内存块的起始地址的对齐方式。满足此约束的一种方法是确保 `align <= self.align()`。
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[unstable(feature = "alloc_layout_extra", issue = "55724")]
    #[rustc_const_unstable(feature = "const_alloc_layout", issue = "67521")]
    #[inline]
    pub const fn padding_needed_for(&self, align: usize) -> usize {
        let len = self.size();

        // 向上取整的值为:
        //   len_rounded_up = (len + align - 1) & !(align - 1);
        // 然后返回填充差异: `len_rounded_up - len`.
        //
        // 我们在整个过程中都使用模块化的算法:
        //
        // 1. align 保证 > 0，因此 align - 1 始终有效。
        //
        // 2.
        // `len + align - 1` &-mask with `!(align - 1)` 最多可以溢出 `align - 1`，因此 &-mask with `!(align - 1)` 将确保 `len_rounded_up` 本身为 0。
        //
        //    因此，当返回的填充添加到 `len` 时，将产生 0，该填充简单地满足了 `align` 的对齐方式。
        //
        // (当然，尝试以上述方式分配其大小和填充溢出的内存块无论如何都会导致分配器产生错误。)
        //
        //
        //
        //

        let len_rounded_up = len.wrapping_add(align).wrapping_sub(1) & !align.wrapping_sub(1);
        len_rounded_up.wrapping_sub(len)
    }

    /// 通过将布局的大小四舍五入到布局的对齐方式的倍数来创建布局。
    ///
    ///
    /// 这等效于将 `padding_needed_for` 的结果添加到布局的当前大小。
    ///
    #[stable(feature = "alloc_layout_manipulation", since = "1.44.0")]
    #[inline]
    pub fn pad_to_align(&self) -> Layout {
        let pad = self.padding_needed_for(self.align());
        // 这不会溢出。引用 Layout 的不变式:
        // > `size`, 当四舍五入到 `align` 的最接近倍数时，
        // > 不得溢出 (即，四舍五入的值必须小于
        // > `usize::MAX`)
        let new_size = self.size() + pad;

        Layout::from_size_align(new_size, self.align()).unwrap()
    }

    /// 创建一个布局，以描述 `self` 的 `n` 实例的记录，并在每个实例之间使用适当的填充量，以确保为每个实例提供其请求的大小和对齐方式。
    /// 成功后，返回 `(k, offs)`，其中 `k` 是数组的布局，`offs` 是数组中每个元素的起点之间的距离。
    ///
    /// 算术溢出时，返回 `LayoutError`。
    ///
    ///
    ///
    ///
    #[unstable(feature = "alloc_layout_extra", issue = "55724")]
    #[inline]
    pub fn repeat(&self, n: usize) -> Result<(Self, usize), LayoutError> {
        // 这不会溢出。引用 Layout 的不变式:
        // > `size`, 当四舍五入到 `align` 的最接近倍数时，
        // > 不得溢出 (即，四舍五入的值必须小于
        // > `usize::MAX`)
        let padded_size = self.size() + self.padding_needed_for(self.align());
        let alloc_size = padded_size.checked_mul(n).ok_or(LayoutError)?;

        // SAFETY: 已知 self.align 是有效的，并且 alloc_size 已被填充。
        //
        unsafe { Ok((Layout::from_size_align_unchecked(alloc_size, self.align()), padded_size)) }
    }

    /// 创建一个布局，描述 `self` 的记录，后跟 `next` 的记录，包括确保 `next` 正确对齐但必须填充 *no trailing* 的所有必要填充。
    ///
    /// 为了匹配 C 表示形式的布局 `repr(C)`，应在扩展了所有字段的布局后调用 `pad_to_align`。
    /// (由于未指定，因此无法匹配默认的 Rust 表示形式布局 `repr(Rust)`。)
    ///
    /// 请注意，最终布局的对齐方式将是 `self` 和 `next` 的最大对齐方式，以确保两个部分的对齐方式。
    ///
    /// 返回 `Ok((k, offset))`，其中 `k` 是串联记录的布局，`offset` 是嵌入在串联记录中的 `next` 起始位置的相对位置 (以字节为单位) (假定记录本身从偏移量 0 开始)。
    ///
    ///
    /// 算术溢出时，返回 `LayoutError`。
    ///
    /// # Examples
    ///
    /// 要计算 `#[repr(C)]` 结构体的布局以及字段与其字段布局的偏移量，请执行以下操作:
    ///
    /// ```rust
    /// # use std::alloc::{Layout, LayoutError};
    /// pub fn repr_c(fields: &[Layout]) -> Result<(Layout, Vec<usize>), LayoutError> {
    ///     let mut offsets = Vec::new();
    ///     let mut layout = Layout::from_size_align(0, 1)?;
    ///     for &field in fields {
    ///         let (new_layout, offset) = layout.extend(field)?;
    ///         layout = new_layout;
    ///         offsets.push(offset);
    ///     }
    ///     // 记得用 `pad_to_align` 来完成!
    ///     Ok((layout.pad_to_align(), offsets))
    /// }
    /// # // 测试它是否有效
    /// # #[repr(C)] struct S { a: u64, b: u32, c: u16, d: u32 }
    /// # let s = Layout::new::<S>();
    /// # let u16 = Layout::new::<u16>();
    /// # let u32 = Layout::new::<u32>();
    /// # let u64 = Layout::new::<u64>();
    /// # assert_eq!(repr_c(&[u64, u32, u16, u32]), Ok((s, vec![0, 8, 12, 16])));
    /// ```
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[stable(feature = "alloc_layout_manipulation", since = "1.44.0")]
    #[inline]
    pub fn extend(&self, next: Self) -> Result<(Self, usize), LayoutError> {
        let new_align = cmp::max(self.align(), next.align());
        let pad = self.padding_needed_for(next.align());

        let offset = self.size().checked_add(pad).ok_or(LayoutError)?;
        let new_size = offset.checked_add(next.size()).ok_or(LayoutError)?;

        let layout = Layout::from_size_align(new_size, new_align)?;
        Ok((layout, offset))
    }

    /// 创建一个布局，该布局描述 `self` 的 `n` 实例的记录，每个实例之间没有填充。
    ///
    /// 请注意，与 `repeat` 不同，即使给定的 `self` 实例正确对齐，`repeat_packed` 也不能保证 `self` 的重复实例将正确对齐。
    /// 换句话说，如果使用 `repeat_packed` 返回的布局来分配数组，则不能保证数组中的所有元素都将正确对齐。
    ///
    /// 算术溢出时，返回 `LayoutError`。
    ///
    ///
    ///
    ///
    ///
    ///
    #[unstable(feature = "alloc_layout_extra", issue = "55724")]
    #[inline]
    pub fn repeat_packed(&self, n: usize) -> Result<Self, LayoutError> {
        let size = self.size().checked_mul(n).ok_or(LayoutError)?;
        Layout::from_size_align(size, self.align())
    }

    /// 创建一个布局，描述 `self` 和 `next` 的记录，两者之间没有其他填充。
    /// 由于没有插入填充，因此 `next` 的对齐方式是无关紧要的，并且不会将 *at all* 合并到结果布局中。
    ///
    ///
    /// 算术溢出时，返回 `LayoutError`。
    ///
    #[unstable(feature = "alloc_layout_extra", issue = "55724")]
    #[inline]
    pub fn extend_packed(&self, next: Self) -> Result<Self, LayoutError> {
        let new_size = self.size().checked_add(next.size()).ok_or(LayoutError)?;
        Layout::from_size_align(new_size, self.align())
    }

    /// 创建一个布局，描述 `[T; n]` 的记录。
    ///
    /// 算术溢出时，返回 `LayoutError`。
    #[stable(feature = "alloc_layout_manipulation", since = "1.44.0")]
    #[inline]
    pub fn array<T>(n: usize) -> Result<Self, LayoutError> {
        let (layout, offset) = Layout::new::<T>().repeat(n)?;
        debug_assert_eq!(offset, mem::size_of::<T>());
        Ok(layout.pad_to_align())
    }
}

#[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"
)]
pub type LayoutErr = LayoutError;

/// 给 `Layout::from_size_align` 或其他 `Layout` 构造函数的参数不满足其记录的约束。
///
///
#[stable(feature = "alloc_layout_error", since = "1.50.0")]
#[non_exhaustive]
#[derive(Clone, PartialEq, Eq, Debug)]
pub struct LayoutError;

// (对于 trait 错误的下游隐含我们需要此功能)
#[stable(feature = "alloc_layout", since = "1.28.0")]
impl fmt::Display for LayoutError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("invalid parameters to Layout::from_size_align")
    }
}