Add support for sub-arenas that can be reset in a LIFO order, without resetting the whole bump arena

[fitzgen]

We should make this work out so that safety is guaranteed by the types. So a sub-arena should exclusively borrow its parent (whether that is the top-level arena or another sub-arena). And the sub-arena shouldn't expose its parent's lifetime, so that references allocated through the sub-arena cannot be used after we drop the sub-arena, and therefore it is safe for the sub-arena's Drop impl to reset the bump pointer to the point it was at when the sub-arena was constructed.

Unclear how to add support for backing bumpalo::collections::Vec et al with a sub-arena and even whether this is desirable vs just waiting for custom allocators to stabilize, now that there is movement there.

cc @cfallin

[zakarumych]

You can look at https://github.com/zakarumych/scoped-arena for an implementation of this.

[zakarumych]

API looks like this

let mut scope = Scope::new(); // creates root scope backed by `Global` allocator.
let mut proxy = scope.proxy();

{
  let scope = proxy.scope();
  let v: &mut usize = scope.to_scope(42);
  // 42 dropped here
  // memory will be reused.
}

[fitzgen]

Was thinking about this a little more today, came up with the following API:

/// The backing storage for bump allocation.
pub struct Region {
    _storage: (),
}

impl Region {
    /// Create a new region to bump into.
    pub fn new() -> Self {
        Region { _storage: () }
    }

    /// Get the allocation capability for this region.
    pub fn bump(&mut self) -> Bump<'_> {
        Bump(self, None)
    }
}

/// Capability to allocate inside some region. Optionally scoped.
pub struct Bump<'a>(&'a mut Region, Option<usize>);

impl Drop for Bump<'_> {
    fn drop(&mut self) {
        if let Some(scope) = self.1 {
            drop(scope);
            // TODO: reset the bump pointer to the start of this nested Bump's
            // scope.
        }
    }
}

impl<'a> Bump<'a> {
    /// Allocate into the region.
    pub fn alloc<T>(&self, value: T) -> &'a mut T {
        Box::leak(Box::new(value))
    }

    /// Get a nested `Bump` that will reset and free all of the things allocated
    /// within it upon drop.
    pub fn scope<'b>(&'b mut self) -> Bump<'b> {
        // Remember the current bump pointer; this is the scope of the nested
        // Bump.
        let scope = 1234;

        Bump(self.0, Some(scope))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn scopes() {
        let mut region = Region::new();
        let mut bump = region.bump();

        let outer = bump.alloc(1234);
        {
            let bump = bump.scope();
            let inner = bump.alloc(5678);

            assert_eq!(*inner, 5678, "can access scoped allocations");
            assert_eq!(*outer, 1234, "can still access allocations from outer scopes");
        }
    }
}

[That3Percent]

The requirements for bumpalo are different, but you might be inspired by the use of closures in second-stack as an API to ensure correct scoping: https://docs.rs/second-stack/0.3.4/second_stack/