offline 1.1.0

//! Things that require [`alloc`].
//!
//! [`alloc`]: ::alloc
#![allow(clippy::alloc_instead_of_core)]

use alloc::alloc::{AllocError, Allocator, Global};
use core::{alloc::Layout, fmt, ptr::NonNull};

#[cfg(all(feature = "alloc", not(feature = "nightly")))]
use allocator_api2 as alloc;
#[cfg(all(feature = "alloc", feature = "nightly"))]
use stdalloc as alloc;

use crate::{Align, Alignment, DynAlign};

/// Dynamic version of [`Overalign`].
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug)]
pub struct DynOveralign<A: Allocator = Global> {
    /// Alignment.
    pub align: DynAlign,

    /// Allocator.
    pub alloc: A,
}
impl DynAlign {
    /// Create a [`DynOveralign`] with this alignment.
    pub const fn overalign<A: Allocator>(self, alloc: A) -> DynOveralign<A> {
        DynOveralign { align: self, alloc }
    }
}

/// Dynamic version of [`Underalign`].
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default, Debug)]
pub struct DynUnderalign<A: Allocator = Global> {
    /// Alignment.
    pub align: DynAlign,

    /// Allocator.
    pub alloc: A,
}
impl DynAlign {
    /// Create a [`DynUnderalign`] with this alignment.
    pub const fn underalign<A: Allocator>(self, alloc: A) -> DynUnderalign<A> {
        DynUnderalign { align: self, alloc }
    }
}

/// Allocator that forces minimum alignment, similar to [`Aligned`].
///
/// [`Aligned`]: crate::Aligned
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct Overalign<const N: usize, A: Allocator = Global>(pub A)
where
    Align<N>: Alignment;
impl<const N: usize, A: Allocator + fmt::Debug> fmt::Debug for Overalign<N, A>
where
    Align<N>: Alignment,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let (buf, len) = const {
            let mut buf = *b"Overalign<{1 << 63}>";
            let len = if N < (1 << 10) {
                buf[16] = b'0' + (N.trailing_zeros() as u8);
                buf[17] = b'}';
                buf[18] = b'>';
                19
            } else {
                let exp = N.trailing_zeros() as u8;
                buf[16] = b'0' + (exp / 10);
                buf[17] = b'0' + (exp % 10);
                20
            };
            (buf, len)
        };

        // SAFETY: We only output valid UTF-8.
        let s = unsafe { str::from_utf8_unchecked(&buf[..len]) };

        f.debug_tuple(s).field(&self.0).finish()
    }
}

/// Overalign layout.
#[inline]
fn overalign_layout(align: DynAlign, layout: Layout) -> Option<Layout> {
    layout.align_to(align.to_usize()).ok()
}

/// Common code for [`Overalign::allocate`] and [`Overalign::allocate_zeroed`].
#[inline]
fn overalign_allocate(
    align: DynAlign,
    allocate: impl FnOnce(Layout) -> Result<NonNull<[u8]>, AllocError>,
    layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
    let overaligned_layout = overalign_layout(align, layout).ok_or(AllocError)?;
    allocate(overaligned_layout)
}

/// Common code for [`Overalign::grow`], [`Overalign::grow_zeroed`], and [`Overalign::shrink`].
#[inline]
fn overalign_resize(
    align: DynAlign,
    resize: impl FnOnce(NonNull<u8>, Layout, Layout) -> Result<NonNull<[u8]>, AllocError>,
    ptr: NonNull<u8>,
    old_layout: Layout,
    new_layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
    // SAFETY: Caller must have allocated the pointer successfully.
    let overaligned_old_layout = unsafe { overalign_layout(align, old_layout).unwrap_unchecked() };
    let overaligned_new_layout = overalign_layout(align, new_layout).ok_or(AllocError)?;

    resize(ptr, overaligned_old_layout, overaligned_new_layout)
}

// SAFETY: Correctness of our API is deferred to underlying allocator.
unsafe impl<const N: usize, A: Allocator> Allocator for Overalign<N, A>
where
    Align<N>: Alignment,
{
    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        overalign_allocate(<Align<N>>::DYN, |layout| self.0.allocate(layout), layout)
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        overalign_allocate(
            <Align<N>>::DYN,
            |layout| self.0.allocate_zeroed(layout),
            layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        overalign_resize(
            <Align<N>>::DYN,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.0.grow(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        overalign_resize(
            <Align<N>>::DYN,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe {
                self.0.grow_zeroed(ptr, old_layout, new_layout)
            },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn shrink(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        overalign_resize(
            <Align<N>>::DYN,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.0.shrink(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        // SAFETY: Caller must have allocated this pointer successfully.
        let overaligned_layout =
            unsafe { overalign_layout(<Align<N>>::DYN, layout).unwrap_unchecked() };

        // SAFETY: Guaranteed by caller.
        unsafe {
            self.0.deallocate(ptr, overaligned_layout);
        }
    }
}

// SAFETY: Correctness of our API is deferred to underlying allocator.
unsafe impl<A: Allocator> Allocator for DynOveralign<A> {
    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        overalign_allocate(self.align, |layout| self.alloc.allocate(layout), layout)
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        overalign_allocate(
            self.align,
            |layout| self.alloc.allocate_zeroed(layout),
            layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        overalign_resize(
            self.align,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.alloc.grow(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        overalign_resize(
            self.align,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe {
                self.alloc.grow_zeroed(ptr, old_layout, new_layout)
            },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn shrink(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        overalign_resize(
            self.align,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.alloc.shrink(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
        // SAFETY: Caller must have allocated this pointer successfully.
        let overaligned_layout = unsafe { overalign_layout(self.align, layout).unwrap_unchecked() };

        // SAFETY: Guaranteed by caller.
        unsafe {
            self.alloc.deallocate(ptr, overaligned_layout);
        }
    }
}

/// Allocator that reduces alignment, similar to [`Misaligned`].
///
/// [`Misaligned`]: crate::Misaligned
#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
pub struct Underalign<const N: usize, A: Allocator = Global>(pub A)
where
    Align<N>: Alignment;
impl<const N: usize, A: Allocator + fmt::Debug> fmt::Debug for Underalign<N, A>
where
    Align<N>: Alignment,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let (buf, len) = const {
            let mut buf = *b"Underalign<{1 << 63}>";
            let len = if N < (1 << 10) {
                buf[17] = b'0' + (N.trailing_zeros() as u8);
                buf[18] = b'}';
                buf[19] = b'>';
                20
            } else {
                let exp = N.trailing_zeros() as u8;
                buf[17] = b'0' + (exp / 10);
                buf[18] = b'0' + (exp % 10);
                21
            };
            (buf, len)
        };

        // SAFETY: We only output valid UTF-8.
        let s = unsafe { str::from_utf8_unchecked(&buf[..len]) };

        f.debug_tuple(s).field(&self.0).finish()
    }
}

/// Overalign layout and add padding sufficient for misalignment.
#[inline]
fn overalign_layout_for_misalign(align: DynAlign, layout: Layout) -> Option<Layout> {
    Some(
        align
            .padding_layout()
            .extend(layout.align_to(align.to_usize()).ok()?)
            .ok()?
            .0
            .pad_to_align(),
    )
}

/// Misalign pointer that was correctly overaligned.
#[inline]
unsafe fn misalign(ptr: NonNull<[u8]>, original_layout: Layout, align: DynAlign) -> NonNull<[u8]> {
    let orig_align = original_layout.align();
    let offset = align.to_usize().saturating_sub(orig_align);

    // SAFETY: We explicitly extend the layout to allow this offset,
    // and remove it from the returned pointer to prevent it from being
    // abused by the callee.
    unsafe { NonNull::slice_from_raw_parts(ptr.cast::<u8>().byte_add(offset), ptr.len() - offset) }
}

/// Realign pointer that was correctly misaligned.
#[inline]
unsafe fn realign(ptr: NonNull<u8>, align: DynAlign) -> NonNull<u8> {
    // SAFETY: We started with a pointer that was aligned, so, we're just
    // returning it back to how it was allocated.
    unsafe {
        let align_offset = ptr.align_offset(align.to_usize());
        if align_offset == 0 {
            ptr
        } else {
            ptr.cast::<u8>().byte_sub(align.to_usize() - align_offset)
        }
    }
}

/// Common code for [`Underalign::allocate`] and [`Underalign::allocate_zeroed`].
#[inline]
fn underalign_allocate(
    align: DynAlign,
    allocate: impl FnOnce(Layout) -> Result<NonNull<[u8]>, AllocError>,
    layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
    let overaligned_layout = overalign_layout_for_misalign(align, layout).ok_or(AllocError)?;
    let ptr = allocate(overaligned_layout)?;

    // SAFETY: We called `overalign_for_misalign` first.
    let misaligned_ptr = unsafe { misalign(ptr, layout, align) };

    Ok(misaligned_ptr)
}

/// Common code for [`Underalign::grow`], [`Underalign::grow_zeroed`], and [`Underalign::shrink`].
#[inline]
fn underalign_resize(
    align: DynAlign,
    resize: impl FnOnce(NonNull<u8>, Layout, Layout) -> Result<NonNull<[u8]>, AllocError>,
    misaligned_ptr: NonNull<u8>,
    old_layout: Layout,
    new_layout: Layout,
) -> Result<NonNull<[u8]>, AllocError> {
    // SAFETY: Guaranteed by caller, who was given a `misalign`ed pointer.
    let ptr = unsafe { realign(misaligned_ptr, align) };

    // SAFETY: Caller must have allocated the pointer successfully.
    let overaligned_old_layout =
        unsafe { overalign_layout_for_misalign(align, old_layout).unwrap_unchecked() };
    let overaligned_new_layout =
        overalign_layout_for_misalign(align, new_layout).ok_or(AllocError)?;

    let new_ptr = resize(ptr, overaligned_old_layout, overaligned_new_layout)?;

    // SAFETY: We called `overalign_for_misalign` first.
    let new_misaligned_ptr = unsafe { misalign(new_ptr, new_layout, align) };

    Ok(new_misaligned_ptr)
}

// SAFETY: Correctness of our API is deferred to underlying allocator.
unsafe impl<const N: usize, A: Allocator> Allocator for Underalign<N, A>
where
    Align<N>: Alignment,
{
    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        underalign_allocate(<Align<N>>::DYN, |layout| self.0.allocate(layout), layout)
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        underalign_allocate(
            <Align<N>>::DYN,
            |layout| self.0.allocate_zeroed(layout),
            layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        underalign_resize(
            <Align<N>>::DYN,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.0.grow(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        underalign_resize(
            <Align<N>>::DYN,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe {
                self.0.grow_zeroed(ptr, old_layout, new_layout)
            },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn shrink(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        underalign_resize(
            <Align<N>>::DYN,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.0.shrink(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    unsafe fn deallocate(&self, misaligned_ptr: NonNull<u8>, layout: Layout) {
        // SAFETY: Guaranteed by caller, who was given a `misalign`ed pointer.
        let ptr = unsafe { realign(misaligned_ptr, <Align<N>>::DYN) };

        // SAFETY: Caller must have allocated this pointer successfully.
        let overaligned_layout =
            unsafe { overalign_layout_for_misalign(<Align<N>>::DYN, layout).unwrap_unchecked() };

        // SAFETY: Guaranteed by caller.
        unsafe {
            self.0.deallocate(ptr, overaligned_layout);
        }
    }
}

// SAFETY: Correctness of our API is deferred to underlying allocator.
unsafe impl<A: Allocator> Allocator for DynUnderalign<A> {
    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        underalign_allocate(self.align, |layout| self.alloc.allocate(layout), layout)
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        underalign_allocate(
            self.align,
            |layout| self.alloc.allocate_zeroed(layout),
            layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        underalign_resize(
            self.align,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.alloc.grow(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn grow_zeroed(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        underalign_resize(
            self.align,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe {
                self.alloc.grow_zeroed(ptr, old_layout, new_layout)
            },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    #[cfg_attr(test, mutants::skip)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    unsafe fn shrink(
        &self,
        ptr: NonNull<u8>,
        old_layout: Layout,
        new_layout: Layout,
    ) -> Result<NonNull<[u8]>, AllocError> {
        underalign_resize(
            self.align,
            // SAFETY: Guaranteed by caller.
            |ptr, old_layout, new_layout| unsafe { self.alloc.shrink(ptr, old_layout, new_layout) },
            ptr,
            old_layout,
            new_layout,
        )
    }

    #[inline]
    unsafe fn deallocate(&self, misaligned_ptr: NonNull<u8>, layout: Layout) {
        // SAFETY: Guaranteed by caller, who was given a `misalign`ed pointer.
        let ptr = unsafe { realign(misaligned_ptr, self.align) };

        // SAFETY: Caller must have allocated this pointer successfully.
        let overaligned_layout =
            unsafe { overalign_layout_for_misalign(self.align, layout).unwrap_unchecked() };

        // SAFETY: Guaranteed by caller.
        unsafe {
            self.alloc.deallocate(ptr, overaligned_layout);
        }
    }
}

#[cfg(test)]
mod tests {
    use alloc::{
        alloc::{AllocError, Allocator, Global},
        vec::Vec,
    };
    use core::{alloc::Layout, ptr::NonNull};

    #[cfg(all(feature = "alloc", not(feature = "nightly")))]
    use allocator_api2 as alloc;
    #[cfg(all(feature = "alloc", feature = "nightly"))]
    use stdalloc as alloc;

    use crate::alloc::{Overalign, Underalign};

    macro_rules! check_overaligned_vec {
        ($t:ty, $align:literal) => {{
            let mut vec = <Vec<$t, _>>::new_in(Overalign::<$align>(Global));
            for len in 0..$align {
                vec.push(0);
                vec.shrink_to_fit();
                assert_eq!(
                    vec.as_ptr().align_offset($align),
                    0,
                    concat!(
                        "Vec<",
                        stringify!($t),
                        "> (len {}) was not ",
                        stringify!($align),
                        "-aligned"
                    ),
                    len,
                );
            }
        }};
    }

    macro_rules! check_underaligned_vec {
        ($t:ty, $align:literal) => {{
            let mut vec = <Vec<$t, _>>::new_in(Underalign::<$align>(Global));
            for len in 0..$align {
                vec.push(0);
                vec.shrink_to_fit();
                let mut power = align_of::<$t>();
                loop {
                    power <<= 1;
                    if power >= $align {
                        break;
                    }
                    assert_ne!(
                        vec.as_ptr().align_offset(power),
                        0,
                        concat!(
                            "Vec<",
                            stringify!($t),
                            "> (len {}) when ",
                            stringify!($align),
                            "-misaligned was {}-aligned"
                        ),
                        len,
                        power,
                    );
                }
            }
        }};
    }

    #[test]
    fn test_debug_overalign() {
        assert_eq!(
            format!("{:?}", Overalign::<{ 1 << 0 }>(Global)),
            "Overalign<{1 << 0}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Overalign::<{ 1 << 9 }>(Global)),
            "Overalign<{1 << 9}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Overalign::<{ 1 << 10 }>(Global)),
            "Overalign<{1 << 10}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Overalign::<{ 1 << 11 }>(Global)),
            "Overalign<{1 << 11}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Overalign::<{ 1 << 21 }>(Global)),
            "Overalign<{1 << 21}>(Global)"
        );
    }

    #[test]
    fn test_debug_underalign() {
        assert_eq!(
            format!("{:?}", Underalign::<{ 1 << 0 }>(Global)),
            "Underalign<{1 << 0}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Underalign::<{ 1 << 9 }>(Global)),
            "Underalign<{1 << 9}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Underalign::<{ 1 << 10 }>(Global)),
            "Underalign<{1 << 10}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Underalign::<{ 1 << 11 }>(Global)),
            "Underalign<{1 << 11}>(Global)"
        );
        assert_eq!(
            format!("{:?}", Underalign::<{ 1 << 21 }>(Global)),
            "Underalign<{1 << 21}>(Global)"
        );
    }

    #[test]
    fn test_trivial_overaligned_vec() {
        check_overaligned_vec!(u8, 1);
        check_overaligned_vec!(u16, 1);
        check_overaligned_vec!(u16, 2);
        check_overaligned_vec!(u32, 1);
        check_overaligned_vec!(u32, 2);
        check_overaligned_vec!(u32, 4);
        check_overaligned_vec!(u64, 1);
        check_overaligned_vec!(u64, 2);
        check_overaligned_vec!(u64, 4);
        check_overaligned_vec!(u64, 8);
        check_overaligned_vec!(u128, 1);
        check_overaligned_vec!(u128, 2);
        check_overaligned_vec!(u128, 4);
        check_overaligned_vec!(u128, 8);
        check_overaligned_vec!(u128, 16);
    }

    #[test]
    fn test_nontrivial_overaligned_vec() {
        check_overaligned_vec!(u8, 2);
        check_overaligned_vec!(u8, 4);
        check_overaligned_vec!(u8, 8);
        check_overaligned_vec!(u8, 16);
        check_overaligned_vec!(u8, 32);
        check_overaligned_vec!(u8, 64);
        check_overaligned_vec!(u8, 128);
        check_overaligned_vec!(u8, 256);
        check_overaligned_vec!(u8, 512);
        check_overaligned_vec!(u16, 4);
        check_overaligned_vec!(u16, 8);
        check_overaligned_vec!(u16, 16);
        check_overaligned_vec!(u16, 32);
        check_overaligned_vec!(u16, 64);
        check_overaligned_vec!(u16, 128);
        check_overaligned_vec!(u16, 256);
        check_overaligned_vec!(u16, 512);
        check_overaligned_vec!(u32, 8);
        check_overaligned_vec!(u32, 16);
        check_overaligned_vec!(u32, 32);
        check_overaligned_vec!(u32, 64);
        check_overaligned_vec!(u32, 128);
        check_overaligned_vec!(u32, 256);
        check_overaligned_vec!(u32, 512);
        check_overaligned_vec!(u64, 16);
        check_overaligned_vec!(u64, 32);
        check_overaligned_vec!(u64, 64);
        check_overaligned_vec!(u64, 128);
        check_overaligned_vec!(u64, 256);
        check_overaligned_vec!(u64, 512);
        check_overaligned_vec!(u128, 32);
        check_overaligned_vec!(u128, 64);
        check_overaligned_vec!(u128, 128);
        check_overaligned_vec!(u128, 256);
        check_overaligned_vec!(u128, 512);
    }

    #[test]
    fn test_trivial_underaligned_vec() {
        check_underaligned_vec!(u8, 1);
        check_underaligned_vec!(u16, 1);
        check_underaligned_vec!(u16, 2);
        check_underaligned_vec!(u32, 1);
        check_underaligned_vec!(u32, 2);
        check_underaligned_vec!(u32, 4);
        check_underaligned_vec!(u64, 1);
        check_underaligned_vec!(u64, 2);
        check_underaligned_vec!(u64, 4);
        check_underaligned_vec!(u64, 8);
        check_underaligned_vec!(u128, 1);
        check_underaligned_vec!(u128, 2);
        check_underaligned_vec!(u128, 4);
        check_underaligned_vec!(u128, 8);
        check_underaligned_vec!(u128, 16);
    }

    #[test]
    fn test_nontrivial_underaligned_vec() {
        check_underaligned_vec!(u8, 2);
        check_underaligned_vec!(u8, 4);
        check_underaligned_vec!(u8, 8);
        check_underaligned_vec!(u8, 16);
        check_underaligned_vec!(u8, 32);
        check_underaligned_vec!(u8, 64);
        check_underaligned_vec!(u8, 128);
        check_underaligned_vec!(u8, 256);
        check_underaligned_vec!(u8, 512);
        check_underaligned_vec!(u16, 4);
        check_underaligned_vec!(u16, 8);
        check_underaligned_vec!(u16, 16);
        check_underaligned_vec!(u16, 32);
        check_underaligned_vec!(u16, 64);
        check_underaligned_vec!(u16, 128);
        check_underaligned_vec!(u16, 256);
        check_underaligned_vec!(u16, 512);
        check_underaligned_vec!(u32, 8);
        check_underaligned_vec!(u32, 16);
        check_underaligned_vec!(u32, 32);
        check_underaligned_vec!(u32, 64);
        check_underaligned_vec!(u32, 128);
        check_underaligned_vec!(u32, 256);
        check_underaligned_vec!(u32, 512);
        check_underaligned_vec!(u64, 16);
        check_underaligned_vec!(u64, 32);
        check_underaligned_vec!(u64, 64);
        check_underaligned_vec!(u64, 128);
        check_underaligned_vec!(u64, 256);
        check_underaligned_vec!(u64, 512);
        check_underaligned_vec!(u128, 32);
        check_underaligned_vec!(u128, 64);
        check_underaligned_vec!(u128, 128);
        check_underaligned_vec!(u128, 256);
        check_underaligned_vec!(u128, 512);
    }

    // this mostly exists to ensure we deallocate for failing tests,
    // so, we don't need coverage for it
    #[allow(clippy::undocumented_unsafe_blocks)]
    #[cfg_attr(any(feature = "nightly", coverage_nightly), coverage(off))]
    fn check_layout(alloc: impl Allocator, small: Layout, too_big: Layout) {
        assert!(alloc.allocate(too_big).is_err());

        struct Alloc<'a, A: Allocator> {
            ptr: NonNull<u8>,
            layout: Layout,
            alloc: &'a A,
        }
        impl<A: Allocator> Alloc<'_, A> {
            fn grow(&mut self, layout: Layout) -> Result<(), AllocError> {
                let new_ptr = unsafe { self.alloc.grow(self.ptr, self.layout, layout) }?;
                self.ptr = new_ptr.cast();
                self.layout = layout;
                Ok(())
            }
        }
        impl<A: Allocator> Drop for Alloc<'_, A> {
            fn drop(&mut self) {
                unsafe {
                    self.alloc.deallocate(self.ptr, self.layout);
                }
            }
        }

        let mut handle = Alloc {
            ptr: alloc.allocate(small).unwrap().cast(),
            layout: small,
            alloc: &alloc,
        };
        assert!(handle.grow(too_big).is_err());
    }

    #[test]
    fn test_layout_edge_cases() {
        let small = Layout::new::<u8>();
        let big = const {
            match Layout::from_size_align(isize::MAX as usize, 1) {
                Ok(layout) => layout,
                Err(_) => unreachable!(),
            }
        };
        let nearly_big = const {
            match Layout::from_size_align(isize::MIN.unsigned_abs() - 512, 1) {
                Ok(layout) => layout,
                Err(_) => unreachable!(),
            }
        };

        check_layout(Overalign::<512>(Global), small, big);
        check_layout(Underalign::<512>(Global), small, big);
        check_layout(Underalign::<512>(Global), small, nearly_big);
    }

    #[test]
    fn test_falliable_allocators() {
        let small = Layout::new::<u8>();
        let big = Layout::new::<u64>();

        struct Smol;

        #[allow(clippy::undocumented_unsafe_blocks)]
        unsafe impl Allocator for Smol {
            fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
                if layout.size() > 4 {
                    Err(AllocError)
                } else {
                    Global.allocate(layout)
                }
            }
            unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
                unsafe { Global.deallocate(ptr, layout) }
            }
        }

        check_layout(Overalign::<2, Smol>(Smol), small, big);
        check_layout(Underalign::<2, Smol>(Smol), small, big);
    }
}