// 对该文件看似无关紧要的代码更改可能会对编译时间产生可衡量的性能影响，至少部分原因是布局代码从各种集合的许多实例中调用，导致不得不多次优化多余的 IR。
//
// 您的性能直觉毫无用处。运行性能。
//
//

use crate::cmp;
use crate::error::Error;
use crate::fmt;
use crate::mem;
use crate::ptr::{Alignment, 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, Hash)]
#[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: Alignment,
}

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

        // SAFETY: 刚刚检查了 align 是两个的幂。
        Layout::from_size_alignment(size, unsafe { Alignment::new_unchecked(align) })
    }

    #[inline(always)]
    const fn max_size_for_align(align: Alignment) -> usize {
        // (2 的幂表示 align=0。)

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

    /// 内部辅助构造函数跳过重新验证对齐有效性。
    #[inline]
    const fn from_size_alignment(size: usize, align: Alignment) -> Result<Self, LayoutError> {
        if size > Self::max_size_for_align(align) {
            return Err(LayoutError);
        }

        // SAFETY: 上面检查了 Layout::size 不，变体。
        Ok(Layout { size, align })
    }

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

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

    /// 此布局的存储块的最小字节对齐。
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "const_alloc_layout_size_align", since = "1.50.0")]
    #[must_use = "this returns the minimum alignment, \
                  without modifying the layout"]
    #[inline]
    #[rustc_allow_const_fn_unstable(ptr_alignment_type)]
    pub const fn align(&self) -> usize {
        self.align.as_usize()
    }

    /// 创建一个适合保存 `T` 类型值的 `Layout`。
    #[stable(feature = "alloc_layout", since = "1.28.0")]
    #[rustc_const_stable(feature = "alloc_layout_const_new", since = "1.42.0")]
    #[must_use]
    #[inline]
    pub const fn new<T>() -> Self {
        let (size, align) = size_align::<T>();
        // SAFETY: 如果类型被实例化，rustc 已经确保它的布局是有效的。
        // 使用未检查的构造函数来避免插入需要优化的 panic 代码路径。
        //
        unsafe { Layout::from_size_align_unchecked(size, align) }
    }

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

    /// 产生描述记录的布局，该记录可用于为 `T` 分配支持结构 (可以是 trait 或其他未定义大小的类型，例如切片)。
    ///
    /// # Safety
    ///
    /// 仅在满足以下条件时，此函数才可以安全调用：
    ///
    /// - 如果 `T` 是 `Sized`，则调用该函数始终是安全的。
    /// - 如果 `T` 的未定义大小的尾部为：
    ///     - [slice]，则切片尾部的长度必须是初始化的整数，并且 *entire 值*(动态尾部长度 + 静态大小的前缀) 的大小必须适合 `isize`。
    ///     - 一个 [trait 对象][trait object]，那么指针的 vtable 部分必须指向一个由 unsizing coercion 获得的类型 `T` 的有效 vtable，并且整个值 (动态尾部长度 + 静态大小前缀) 的大小必须适合 `isize`。
    ///
    ///     - 一个不稳定的 [外部类型][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")]
    #[rustc_const_unstable(feature = "const_alloc_layout", issue = "67521")]
    #[must_use]
    pub const 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)) };
        // SAFETY: 请参见 `new` 中的基本原理，了解为什么要使用不安全的变体。
        unsafe { Layout::from_size_align_unchecked(size, align) }
    }

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

    /// 创建一个描述记录的布局，该记录可以保留与 `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")]
    #[must_use = "this returns the padding needed, \
                  without modifying the `Layout`"]
    #[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` 最多可以溢出 `align - 1`，所以 &-mask 和 `!(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")]
    #[rustc_const_unstable(feature = "const_alloc_layout", issue = "67521")]
    #[must_use = "this returns a new `Layout`, \
                  without modifying the original"]
    #[inline]
    pub const fn pad_to_align(&self) -> Layout {
        let pad = self.padding_needed_for(self.align());
        // 这不会溢出。引用布局的不变量：
        // > `size`，当四舍五入到最接近的 `align` 倍数时，
        // > 不得溢出 isize (即，四舍五入的值必须是
        // > 小于或等于 `isize::MAX`)
        let new_size = self.size() + pad;

        // SAFETY: 填充大小保证不超过 `isize::MAX`。
        unsafe { Layout::from_size_align_unchecked(new_size, self.align()) }
    }

    /// 创建一个布局，以描述 `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> {
        // 这不会溢出。引用布局的不变量：
        // > `size`，当四舍五入到最接近的 `align` 倍数时，
        // > 不得溢出 isize (即，四舍五入的值必须是
        // > 小于或等于 `isize::MAX`)
        let padded_size = self.size() + self.padding_needed_for(self.align());
        let alloc_size = padded_size.checked_mul(n).ok_or(LayoutError)?;

        // 此处调用安全构造函数以强制执行 isize 大小限制。
        let layout = Layout::from_size_alignment(alloc_size, self.align)?;
        Ok((layout, 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)?;

        // 此处调用安全构造函数以强制执行 isize 大小限制。
        let layout = Layout::from_size_alignment(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)?;
        // 此处调用安全构造函数以强制执行 isize 大小限制。
        Layout::from_size_alignment(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)?;
        // 此处调用安全构造函数以强制执行 isize 大小限制。
        Layout::from_size_alignment(new_size, self.align)
    }

    /// 创建一个布局，描述 `[T; n]` 的记录。
    ///
    /// 在算术溢出或总大小超过 `isize::MAX` 时，返回 `LayoutError`。
    ///
    #[stable(feature = "alloc_layout_manipulation", since = "1.44.0")]
    #[rustc_const_unstable(feature = "const_alloc_layout", issue = "67521")]
    #[inline]
    pub const fn array<T>(n: usize) -> Result<Self, LayoutError> {
        // 减少我们需要对每个 `T` 进行单态化的代码量。
        return inner(mem::size_of::<T>(), Alignment::of::<T>(), n);

        #[inline]
        const fn inner(
            element_size: usize,
            align: Alignment,
            n: usize,
        ) -> Result<Layout, LayoutError> {
            // 我们需要检查关于大小的两件事:
            //  - 总大小不会溢出 `usize`，并且
            //  - 总大小仍然适合 `isize`。
            // 通过使用除法，我们可以用一个阈值检查它们。
            // 这通常是个坏主意，但幸运的是，这里的元素大小和对齐方式是常量，所以编译器会折叠所有这些。
            //
            if element_size != 0 && n > Layout::max_size_for_align(align) / element_size {
                return Err(LayoutError);
            }

            let array_size = element_size * n;

            // SAFETY: 我们刚刚在上面检查过，即使四舍五入到对齐，`array_size` 也不会超过 `isize::MAX`。
            //
            // `Alignment` 保证它是二的幂。
            unsafe { Ok(Layout::from_size_align_unchecked(array_size, align.as_usize())) }
        }
    }
}

#[stable(feature = "alloc_layout", since = "1.28.0")]
#[deprecated(
    since = "1.52.0",
    note = "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;

#[stable(feature = "alloc_layout", since = "1.28.0")]
impl Error for 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")
    }
}