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/

[kuroahna]

Hi @fitzgen just curious if there's any activity for this feature as I'm interested in creating a sub-arena from the main arena for temporary allocations.

I was reading https://nullprogram.com/blog/2023/09/27/ and was interested in doing something similar to

getlines takes two arenas, “permanent” and “scratch”. The former is for objects that will be returned to the caller. The latter is for temporary objects whose lifetime ends when the function returns. They have stack lifetimes just like local variables.
Objects are not explicitly freed. Instead, all allocations from a scratch arena are implicitly freed upon return. This would include error return paths automatically.

Currently I'm creating a separate scratch/temporary arena that's not scoped under the main arena