Refactor Initialize and AllocateUsing core traits

[Robbepop]

The AllocateUsing ink_core trait has severe problems.

Type Safety

When calling T::allocate_using(&mut alloc) the caller is returned with a T and may use it as a properly initialized one of its kind. However, in some cases (e.g. for static storage entities during contract instantiation or for dynamic storage entities) this might not be true since a proper initialization for the type could be missing.

We should try to find a better API that circumvents this problem by making it impossible or at least user-friendly to use the underlying T incorrectly.

Compile-time computability

Since ink! tries to put as much computation into compile time to safe gas it is especially important to minimize what needs to be re-computed for every contract call or instantiation.

One problem with Rust const_fn is that we cannot define const fn trait methods. This renders any approach based on Rust traits useless for our purpose of moving as many computations as possible to compile time.

The best possible approach allows for modular building blocks (e.g. as current AllocateUsing does while also enabling compile-time computations in current Rust.

New Interface

The new proposed interface to address the type safety problems is the following:
(Note that this new interface does not solve our problems with compile-time computability since we are still using traits.)

Old

/// Types implementing this trait can be allocated on the storage by storage allocators.
pub trait AllocateUsing
where
    Self: Sized,
{
    /// Allocates an uninitialized instance of `Self` using
    /// the given storage allocator.
    ///
    /// # Safety
    ///
    /// Unsafe because the storage contents of the resulting instance
    /// are uninitialized. Operating on uninitialized storage may result
    /// in panics or even in undefined behaviour.
    unsafe fn allocate_using<A>(alloc: &mut A) -> Self
    where
        A: Allocate;
}

Proposed

/// Intermediate root storage allocation.
///
/// Used to avoid having to `unwrap` multiple nested `MaybeUninit`
/// in a storage allocation scheme so that we only have a single
/// root `MaybeUninit` at the end and all other internal allocated
/// entities are simply childs of that one.
pub struct RootAllocated<'a, A, T> {
    /// The allocator using throughout the nested allocation.
    pub alloc: &'a mut A,
    /// The storage marker of the root type.
    ///
    /// Since the root type is constructed at the end of the nested
    /// allocation routine we carry its type around until the point
    /// of usage.
    marker: core::marker::PhantomData<fn() -> T>,
}

impl<'a, A, T> RootAllocated<'a, A, T> {
    /// Create a new root allocation.
    fn new(alloc: &'a mut A) -> Self {
        Self {
            alloc,
            marker: Default::default(),
        }
    }

    /// Finalize the root allocation.
    fn finalize(self, constructor: impl Fn() -> T) -> MaybeUninit<T> {
        MaybeUninit::new(constructor())
    }
}

/// A maybe uninitialized storage entity.
///
/// A `MaybeUninit` in ink! is received from creating a `RootAllocated`
/// through the `AllocateUsing` trait and represents an entity that might
/// have already been initialized but whether that is the case is known
/// by the state of execution.
///
/// # Drop
///
/// Dropping a `MaybeUninit<T>` won't call `T`'s `Drop` implementation since
/// it might have not yet been initialized which would cause unspecified behaviour.
///
/// # Note
///
/// There are mainly 3 different states in which we can have a `MaybeUninit`.
///
/// 1. When instantiating a contract we have to allocate and initialize the
///    static storage entities. This is when the user of a `MaybeUninit` should
///    generally use the [`try_default_init`] method followed by a real instantiation
///    routine.
///    A `ManuallyDrop` is returned for this case since we do not `Drop` static storage.
/// 2. When calling a contract we have to re-allocate our static storage entities but
///    can assume that they have already been initialized during the initialization.
///    A user in this state should generally call [`assume_init`] and be done.
///    A `ManuallyDrop` is returned for this case since we do not `Drop` static storage.
/// 3. When creating a storage entity dynamically using the dynamic storage allocator
///    we have to allocate the entity on the storage and initialize it accordingly.
///    For this case a user should generally call [`initialize`] to finalize the entity.
///    Unlike in the other cases we return a `T` here since dynamically allocated storage
///    entities must deallocate upon `Drop`.
pub struct MaybeUninit<T> {
    /// The allocated but maybe uninitialized storage entity.
    inner: ManuallyDrop<T>,
}

impl<T> MaybeUninit<T> {
    /// Creates a new `MaybeUninit` from the given `T`.
    fn new(inner: T) -> Self {
        Self { inner: ManuallyDrop::new(inner) }
    }

    /// Assumes that the inner `T` has already been initialized.
    ///
    /// # Note
    ///
    /// Use this when the entity is a static storage entity and has
    /// already been initialized, e.g. during a contract call.
    pub fn assume_init(self) -> ManuallyDrop<T> {
        self.inner
    }
}

impl<T> MaybeUninit<T>
where
    T: Initialize,
{
    /// Tries to default initialize the inner `T`.
    ///
    /// Note that not all `T` can be default initialized so users of this
    /// API cannot be guaranteed to have a properly initialized storage entity
    /// after this operation.
    ///
    /// # Note
    ///
    /// Use this when the entity is a static storage entity and has not yet
    /// been initialized, e.g. during a contract instantiation.
    pub fn try_default_init(mut self) -> ManuallyDrop<T> {
        self.inner.try_default_initialize();
        self.inner
    }

    /// Properly initializes the inner `T` using the given arguments.
    ///
    /// # Note
    ///
    /// Use this when the entity is a dynamic storage entity.
    pub fn initialize(self, args: <T as Initialize>::Args) -> T {
        self.inner.initialize_into(args)
    }
}

/// Types implementing this trait can be allocated on the storage by storage allocators.
pub trait AllocateUsing
where
    Self: Sized,
{
    /// Allocates an uninitialized instance of `Self` using the given allocator.
    ///
    /// The whole point behind splitting `allocate_using` and `allocate_internally_using`
    /// is to allow user friendly implementations that provide type-safety in order to make
    /// it clear that allocated instances are not necessarily initialized already.
    ///
    /// # Note
    ///
    /// This is used for root elements only and should not be implemented by users.
    /// Implementers of `AllocateUsing` shall only implement [`allocate_internally_using`].
    fn allocate_using<A>(alloc: &mut A) -> MaybeUninit<Self>
    where
        A: Allocate,
    {
        let mut root = RootAllocated::new(alloc);
        let allocated = Self::allocate_internally_using(&mut root);
        root.finalize(move || allocated)
    }

    /// Allocates an uninitialized instance of `Self` under the given root element.
    ///
    /// # Design
    ///
    /// Read more in the docs of [`allocate_using`]
    /// for more information about the design rational.
    ///
    /// # Note
    ///
    /// This is the only trait function that shall be implemented by implementers.
    fn allocate_internally_using<A, T>(root: &mut RootAllocated<A, T>) -> Self
    where
        A: Allocate;
}

Derive Macros

If we had derive macros for the ink_core traits the refactoring would be even easier because users wouldn't have to change all the implementations on their side. So we should also provide derive macros for Flush, AllocateUsing as well as Initialize to make future refactorings of the same traits easier and cause less trouble.

[Robbepop]

Superseeded by #280.