realloc 0.1.1

//! A re-imagining of allocation in Rust from the ground-up. Fully `no_std` and
//! portable.
//!
//! Everything is built on top of the [`Allocator`] trait (and
//! [`AllocatorExt`]); the goal is to make allocation itself 100% safe. To that
//! end, it introduces the [`Alloc`] abstraction to ensure no allocation is
//! double-freed or freed in the wrong allocator.
//!
//! A secondary (but still very important) goal is genericity. For this, all
//! built-in allocations are fully generic over what allocator they use, as well
//! as the [strategy](Strategy) used to handle allocation failures.
//!
//! The feature flag `global` enables the [global allocator framework](global),
//! which allows one to set an allocator for all collections to use by default.
//!
//! The crate comes with built-in system allocators for Linux (via
//! `aligned_alloc`) and Windows (`_aligned_malloc`), but only with feature
//! `platform` enabled. (with both `global` and `platform`, the global allocator
//! is initially the platform allocator)
//!
//! A number of containers are defined in the crate (at the time of writing,
//! [`Box`] and [`Vec`], to varying degrees of completeness). Note that `Box` is
//! somewhat different to `std::box::Box`, due to the lack of compiler magic.
//!
//! It also provides certain portable predefined allocators (currently [`Arena`]
//! and [`Array`]). Of course, you can always define your own, and use them just
//! the same.
//! 
//! Note that while the whole crate is `no_std`, and aside from `platform` is
//! totally portable, it *does* make use of `core::sync::atomic`. If your
//! desired platform doesn't support atomics at all, this crate will not work.
#![no_std]
#![deny(rust_2018_idioms)]
#![warn(clippy::missing_safety_doc, missing_docs)]

mod alloc;
mod allocators;
mod brand;
mod containers;
mod layout;
mod lock;
mod r#static;
mod strategy;

pub use alloc::Alloc;
pub use allocators::{Arena, Array};
pub use brand::Brand;
pub use containers::export::*;
pub use layout::{Align, Layout};
pub use r#static::Static;
pub(crate) use strategy::FAILURE_MESSAGE;
pub use strategy::{Abort, Fallible, Optional, Panic, Strategy};

#[cfg(feature = "platform")]
mod platform;
#[cfg(feature = "platform")]
pub use platform::{platform, PlatformAllocator};

#[cfg(feature = "global")]
pub mod global;

/// The comprehensive set of errors an allocator is allowed to return.
#[non_exhaustive]
#[derive(Clone, Debug)]
pub enum Error {
    /// The allocator has run out of memory to yield.
    OutOfMemory,
    /// The layout passed to an allocation function (usually `grow`/`shrink`)
    /// was not within the expected parameters.
    ///
    /// For example, this could mean that the layout passed to `grow` was
    /// actually smaller than the original allocation, or that the specified
    /// alignment is not supported.
    InvalidLayout,
    /// [`dealloc_bytes`](Allocator::dealloc_bytes) was called on an [`Alloc`]
    /// from a different allocator.
    WrongAllocator,

    /// A collection's `new` method was called, but no global allocator was set.
    #[cfg(feature = "global")]
    NoGlobalAllocator,

    /// A platform-specific error occured. The allocator may choose to convey
    /// what exactly went wrong through other channels.
    #[cfg(feature = "platform")]
    PlatformError,

    /// An I/O-related error occured.
    IoError(recore::io::Error),
    /// A different kind of error occured. The allocator may choose to convey
    /// what exactly went wrong through other channels.
    Other,
}
recore::fmt::derive!(Debug for enum Error {
    OutOfMemory,
    InvalidLayout,
    WrongAllocator,
    #[cfg(feature = "global")]
    NoGlobalAllocator,
    #[cfg(feature = "platform")]
    PlatformError,
    IoError(e),
    Other,
});

/// A type capable of providing and freeing arbitrary chunks of uninitialized
/// memory on demand.
///
/// The attributes of a given chunk of memory (abstracted behind [`Alloc`]) are
/// defined by a [`Layout`]. These allocations live at least as long as the
/// allocator itself (but not necessarily any longer).
///
/// # Safety
///
/// - `self.brand()` must return a [`Brand`] *unique to this instance*. In
///   practice, this means each instance of this allocator must obtain its own
///   with [`Brand::new`].
/// - `self.dealloc` and reallocation methods must check that
///   `alloc.allocator().brand() == self.brand()`.
/// - All allocation methods must return an allocation of at least the size and
///   alignment expected by the given layout, including reallocation methods.
///   The returned `Alloc`'s `layout` field must be the layout given during
///   allocation.
pub unsafe trait Allocator {
    /// The unique brand of this allocator, that prevents allocations from other
    /// allocators from being freed in this one, and vice-versa.
    fn brand(&self) -> &Brand;

    /// Create an allocation of a certain layout, treating it as bytes.
    ///
    /// Note that this can then be converted to an arbitrary `Alloc<T>` via
    /// [`Alloc::cast`].
    fn alloc_bytes(&self, layout: Layout) -> Result<Alloc<'_, u8>, Error>;

    /// Free an allocation.
    ///
    /// If `alloc` is not from `self`, must do nothing.
    ///
    /// Note that any `Alloc<T>` can be converted to `Alloc<u8>` via
    /// [`Alloc::cast`].
    fn dealloc_bytes<'this>(&'this self, alloc: Alloc<'this, u8>);

    /// Returns a zero-sized allocation.
    ///
    /// This should never actually allocate.
    fn dangling(&self, align: Align) -> Alloc<'_, u8>;

    /// The total size available to be allocated.
    ///
    /// Note that this number may not be accurate; at best, it could be merely a
    /// lower or upper bound.
    fn total_size(&self) -> Option<usize> { None }

    /// The remaining amount of memory available to be allocated.
    ///
    /// Note that this number may not be accurate; at best, it could be merely a
    /// lower or upper bound.
    fn remaining_size(&self) -> Option<usize> { None }

    /// Like [`alloc_bytes`](Allocator::alloc_bytes), but guarantees that it is
    /// filled with zeroes.
    ///
    /// The default definition simply uses `alloc_bytes` and `memset`; certain
    /// allocators may see performance benefits from overriding this.
    fn alloc_zeroed(&self, layout: Layout) -> Result<Alloc<'_, u8>, Error> {
        let new = self.alloc_bytes(layout)?;
        // SAFETY: this ptr is valid for exactly `layout.size` bytes
        unsafe { new.ptr().cast::<u8>().write_bytes(0, layout.size) };
        Ok(new)
    }

    /// Transform a given allocation to a new layout (generally to grow/shrink
    /// it).
    ///
    /// If `alloc` is from a different allocator, must return
    /// [`Error::WrongAllocator`].
    ///
    /// Note that the only times this *must* reallocate are if the given
    /// allocation is not large enough (including extra space), or if the
    /// alignment of the allocation is less than the new alignment.
    ///
    /// See also [`grow`](Allocator::grow) and [`shrink`](Allocator::shrink), to
    /// which the default implementation for this method delegates.
    fn realloc<'this>(
        &'this self,
        alloc: Alloc<'this, u8>,
        layout: Layout,
    ) -> Result<Alloc<'this, u8>, Error> {
        if alloc.allocator().brand() != self.brand() {
            return Err(Error::WrongAllocator);
        }

        if alloc.layout().size > layout.size {
            self.grow(alloc, layout)
        } else {
            self.shrink(alloc, layout)
        }
    }

    /// Transform a given allocation to a new layout (generally to grow it).
    /// Copies previous data into the first bytes of the new allocation, with
    /// the remaining bytes uninitialized.
    ///
    /// If `alloc` is from a different allocator, must return
    /// [`Error::WrongAllocator`].
    ///
    /// Note that the only times this *must* reallocate are if the given
    /// allocation is not large enough (including extra space), or if the
    /// alignment of the allocation is less than the new alignment.
    ///
    /// The default implementation simply creates a new allocation and copies
    /// over the data; some allocators may be able to grow allocations more
    /// intelligently, in which case it would be wise to override this method.
    fn grow<'this>(
        &'this self,
        alloc: Alloc<'this, u8>,
        layout: Layout,
    ) -> Result<Alloc<'this, u8>, Error> {
        if alloc.allocator().brand() != self.brand() {
            return Err(Error::WrongAllocator);
        }

        if layout.size <= alloc.size() && layout.align <= alloc.align() {
            return Ok(alloc);
            // return Err(Error::InvalidLayout);
        }

        let new = self.alloc_bytes(layout)?;
        let size = new.size().min(alloc.size());
        // SAFETY: this ptr is valid for exactly `new.size()` bytes, and the old
        // ptr is valid for exactly `alloc.size` bytes; therefore, the minimum
        // of the two is definitely safe.
        unsafe { new.ptr().cast::<u8>().copy_from(alloc.ptr().cast(), size) };

        Ok(new)
    }

    /// Transform a given allocation to a new layout (generally to shrink it).
    /// Copies over as much data from the original allocation as will fit.
    ///
    /// If `alloc` is from a different allocator, must return
    /// [`Error::WrongAllocator`].
    ///
    /// Note that the only times this *must* reallocate are if the given
    /// allocation is not large enough (including extra space), or if the
    /// alignment of the allocation is less than the new alignment.
    ///
    /// The default implementation simply creates a new allocation and copies
    /// over the data; some allocators may be able to shrink allocations more
    /// intelligently, in which case it would be wise to override this method.
    fn shrink<'this>(
        &'this self,
        alloc: Alloc<'this, u8>,
        layout: Layout,
    ) -> Result<Alloc<'this, u8>, Error> {
        if alloc.allocator().brand() != self.brand() {
            return Err(Error::WrongAllocator);
        }

        if layout.size >= alloc.size() && layout.align <= alloc.align() {
            return Ok(alloc);
            // return Err(Error::InvalidLayout);
        }

        let new = self.alloc_bytes(layout)?;
        let size = new.size().min(alloc.size());
        // SAFETY: this ptr is valid for exactly `new.size()` bytes, and the old
        // ptr is valid for exactly `alloc.size` bytes; therefore, the minimum
        // of the two is definitely safe.
        unsafe { new.ptr().cast::<u8>().copy_from(alloc.ptr().cast(), size) };

        Ok(new)
    }
}

/// A collection of
/// non-[dyn-compatible](https://doc.rust-lang.org/reference/items/traits.html#dyn-compatibility)
/// helper methods for [`Allocator`].
///
/// Automatically implemented for all `Allocator`s.
///
/// # Safety
///
/// - All allocation methods must return an allocation of at least the size and
///   alignment expected by the given layout, including reallocation methods.
///   The returned `Alloc`'s `layout` field must be the given layout.
pub unsafe trait AllocatorExt: Allocator {
    /// Creates an allocation suitable for a given type `T`.
    ///
    /// Shortcut for `self.alloc_bytes(Layout::of::<T>())`.
    fn alloc<T>(&self) -> Result<Alloc<'_, T>, Error> {
        self.alloc_bytes(Layout::of::<T>())
            .map(|alloc| alloc.cast())
    }

    /// Free an allocation.
    ///
    /// If `alloc` is not from `self`, must do nothing.
    fn dealloc<'this, T>(&'this self, alloc: Alloc<'this, T>) {
        self.dealloc_bytes(alloc.cast())
    }

    /// Creates an allocation suitable for a given type `T`, and populates it
    /// with a given value. If allocation fails, returns the value along with
    /// the error value.
    fn alloc_with<T>(&self, data: T) -> Result<Alloc<'_, T>, (T, Error)> {
        let mut ptr = match self.alloc::<T>() {
            Ok(ptr) => ptr,
            Err(e) => return Err((data, e)),
        };
        ptr.write(data);
        Ok(ptr)
    }

    /// A convenience method for coercing this to a trait object.
    fn as_dyn(&self) -> &dyn Allocator
    where
        Self: Sized,
    {
        self
    }
}

// SAFETY: the default implementation essentially forwards the safety invariants
// to the `Allocator` impl, which is also `unsafe`
unsafe impl<A: Allocator + ?Sized> AllocatorExt for A {}

// SAFETY: the implementation forwards the safety invariants to the underyling
// `Allocator` impl
unsafe impl<A: Allocator + ?Sized> Allocator for &A {
    fn brand(&self) -> &Brand {
        (*self).brand()
    }

    fn alloc_bytes(&self, layout: Layout) -> Result<Alloc<'_, u8>, Error> {
        (*self).alloc_bytes(layout)
    }

    fn dealloc_bytes<'this>(&'this self, alloc: Alloc<'this, u8>) {
        (*self).dealloc_bytes(alloc)
    }

    fn dangling(&self, align: Align) -> Alloc<'_, u8> {
        (*self).dangling(align)
    }

    fn alloc_zeroed(&self, layout: Layout) -> Result<Alloc<'_, u8>, Error> {
        (*self).alloc_zeroed(layout)
    }

    fn realloc<'this>(
        &'this self,
        alloc: Alloc<'this, u8>,
        layout: Layout,
    ) -> Result<Alloc<'this, u8>, Error> {
        (*self).realloc(alloc, layout)
    }

    fn grow<'this>(
        &'this self,
        alloc: Alloc<'this, u8>,
        layout: Layout,
    ) -> Result<Alloc<'this, u8>, Error> {
        (*self).grow(alloc, layout)
    }

    fn shrink<'this>(
        &'this self,
        alloc: Alloc<'this, u8>,
        layout: Layout,
    ) -> Result<Alloc<'this, u8>, Error> {
        (*self).shrink(alloc, layout)
    }
}