Attempt to combine several proposals

[TimDiekmann]

As there are several proposals on how to modify the Alloc trait, I tried to combine most of the proposed changes. With this issue I would like to try to create a basis for what the new Alloc trait might look like. It might be easier to continue working with it to test new features.

Issues, I took into account:

• Rename Alloc to AllocRef #8: I chose to rename Alloc to AllocRef, no strong opinion here.
• Separate dealloc from Alloc into other trait #9: Also separate realloc into a ReallocRef trait as implementing an allocator will be the unusual case, but grants the user more possibilities to use it.
• Box<T, A: BuildAlloc> #12
• Ban zero-sized allocations #16: For simplicity I sticked to std::alloc::Layout and did not implement something like a LayoutBuilder or NonZeroLayout.
• Remove Alloc::{alloc,dealloc}_array and Alloc::{alloc,dealloc}_oneAPIs #18: I think it's better to leave them out in the first iteration to be conservative. It can always be added later.
• Associated Err type for the Alloc trait #23: I want to try out how far the associated error type can improve the API

For simplicity I skipped the _excess and _in_place API as it does not change.

Starting with the BuildAlloc trait:

// `Sized` is required for `AllocRef`
pub trait BuildAlloc: Sized {
    type AllocRef: AllocRef<BuildAlloc = Self>;

    unsafe fn build_alloc(&mut self, ptr: NonNull<u8>, layout: Layout) -> Self::AllocRef;
}

The Alloc trait got separated into AllocRef, ReallocRef, and DeallocRef:

pub trait DeallocRef: Sized {
    unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout);
}

pub trait ReallocRef {
    type DeallocRef: DeallocRef;
    type Error;

    unsafe fn realloc(
        &mut self,
        ptr: NonNull<u8>,
        layout: Layout,
        new_size: usize,
    ) -> Result<NonNull<u8>, Self::Error>;
}

pub trait AllocRef: DeallocRef {
    type BuildAlloc: BuildAlloc<AllocRef = Self>;
    type ReallocRef: ReallocRef<DeallocRef = Self>;
    // Not necessarily the same Error as in `ReallocError`
    type Error;

    // Note that `alloc` and `alloc_zeroed` does not need to be unsafe anymore as zero
    // sized layouts are not allowed. This requires something like `NonZeroLayout` to 
    // hold this
    fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, Self::Error>;
    #[allow(unused_variables)]
    fn alloc_zeroed(&mut self, layout: Layout) -> Result<NonNull<u8>, Self::Error> {
        unimplemented!()
    }
    fn get_build_alloc(&mut self) -> Self::BuildAlloc;
}

I wrote a small sealed trait for determine infallible allocation:

mod private {
    pub trait Infallible {}
    impl Infallible for ! {}
    impl Infallible for core::convert::Infallible {}
}

For Box I chose not to use Box<T, D: BuildDealloc> for three reasons:

• calling Box::new_in could not deduce D as new_in takes AllocRef
• AllocRef can directly be stored as DeallocRef
• BuildAlloc can be created by AllocRef, BuildDealloc (if exists) can be created from DeallocRef

pub struct Box<T: ?Sized, D: DeallocRef>(Unique<T>, D);

impl<T, A: AllocRef> Box<T, A> {
    // Thanks to the associated error type, we can add two methods, a fallible and 
    // an infallible one.
    // To maintain backwards compatibility, Box could default `A` to something like
    // `AbortAlloc<Global>` which aborts on failure thus enabling `new_in` by default.
    pub fn new_in(x: T, a: A) -> Self
    where
        A::Error: private::Infallible,
    {
        if let Ok(b) = Self::try_new_in(x, a) {
            b
        } else {
            unreachable!("Infallible allocation failed")
        }
    }

    pub fn try_new_in(x: T, mut a: A) -> Result<Self, A::Error> {
        let layout = Layout::new::<T>();
        let mut ptr = a.alloc(layout)?.cast();
        unsafe {
            *ptr.as_mut() = x;
        }
        Ok(Self(ptr.into(), a))
    }
}

I also put this in a playground.

[TimDiekmann]

Actually I missed some details of #12 in conjunction with #9.
As theocrafting won't help very much here, I'm closing this for now and will post a new Issue in a few days with another attempt.