Refactor arena API to permit reuse, play nicely with new

[nikomatsakis]

For a variety of reasons, I think the arena API should be restructured. This is part of a larger plan to better enable smart pointers and I didn't intend to start by writing out about arenas, but my hand was forced by #10390 where I found myself elaborating on the arena plan in a comment, so let me go ahead and write this down.

Goals of this plan:

• Enable arena allocations to be safely reused, lowering total memory use
• Enable arenas to play nicely with a hypothetical new(arena) ... operator
• Avoid unsafe transmutes that work around the type system

In a nutshell, I would like to change arena's signature from:

struct Arena { ... }
impl Arena {
    fn new() -> Arena { }
    fn alloc<'a, T>(&'a self, x: T) -> &'a T { }
}

to:

struct MemoryPool { ... }
struct Arena<'pool> { pool: &'pool mut MemoryPool, .. }
struct ArenaAlloc<'pool, T> { ptr: &'pool mut T }
impl<'pool> Arena<'pool> {
    fn init(pool: &'pool mut MemoryPool) { ... }
    fn alloc<T>(&mut self) -> ArenaAlloc<'pool, T> {
        // consult a free list, else alloc from pool
    }
    fn free<T>(&mut self, alloc: ArenaAlloc<'pool, T>) {
        // use a free list
    }
}

// ArenaAlloc is a smart pointer that acts like an owned pointer
impl<'pool, T> Deref<T> for ArenaAlloc<'pool, T> { ... }
impl<'pool, T> MutDeref<T> for ArenaAlloc<'pool, T> { ... }
impl Drop for ArenaAlloc<'pool, T> { fn drop(&mut self) { } }

The memory pool would be the thing that holds the memory. When it is destroyed, the memory is freed. The arena is the allocator itself. distinction between the memory pool and the arena is kind of meaningless and unfortunate. The end goal is to have the arena type be parameterized by a lifetime ('pool) that corresponds to the lifetime of the returned values, rather than having the lifetime of the returned values be derived from the lifetime of the self pointer in the alloc() call. At the moment, this requires another object to tie the lifetime to, hence the "memory pool".

The motivations for this change are:

1. It allows us to remove the unsafe code that makes an arena artificially mutable.

2. It will play better with a future new(arena) Expr operator, because it allows us to fit in with a (higher-kinded) allocator trait that looks something like:

   trait Allocator { // Ptr :: * => *
   fn alloc(&mut self) -> Ptr;
   }

The implementation would look something like this (waving hands wildly with respect to syntax):

impl<'pool> Allocator<ArenaAlloc<'pool, ..>> for Arena<'pool> {
    fn alloc<T>(&mut self) -> ArenaAlloc<'pool, T> { ... }
}

ArenaAlloc would be smart pointer that acts like an owned pointer.

The downside of this is that to create an arena, at least today -- and pending the resolution of #3511 -- you would have to do two steps:

let mut pool = MemoryPool::init();
let mut arena = Arena::init(&mut pool);
// now I can use arena

If we resolve #3511 in favor of inference, one could write:

let mut arena = Arena::init(&mut MemoryPool::init());

but it is still necessary for the MemoryPool to be created by the caller, so that the caller can free it.

To solve this without a distinct object, we'd need a different kind of lifetime: more or less the 'self people sometime ask for, a lifetime that is associated with a struct and means "as long as it lives". This is a separate feature request and I'll open an issue about it, but I'm a bit handwavy on how it will work.

cc @pnkfelix (per our discussion about reaps)

[nikomatsakis]

Note: this plan is not quite actionable, I think it relies on a few features (most obviously the deref trait; less obviously #10445) that are not yet implemented.

[thestinger]

I started sketching out the container side of an allocator API before hitting #8059. With an implementation of vectors and unique pointers taking an allocator type parameter and an allocator instance via a with_alloc constructor, it's easy to build any other containers like trees or hash tables on top of them with allocator parameters too.

https://github.com/thestinger/rust-core/blob/master/core/vec.rs

[nikomatsakis]

One thing we have to be careful of: multiple memory pools and arenas can share the same 'pool lifetime with this API. This means that a "free()" call might get an arena allocation from a different memory pool instead of this one. This could be dangerous. We could address this with a dynamic check (annoying) or by refactoring the API so that one creates and works with an arena like so:

struct MemoryPool { ... } // this is private and becomes an implementation detail

impl Arena {
    fn init() -> Arena { ... } // this is private!

    pub fn with<A, R>(a: A, f: <'a> |&'a mut Arena<'a>, A| -> R) -> R {
        let mut pool = MemoryPool::init();
        let mut arena = Arena::init(&mut pool);
        f(&mut arena, a)
    }
}

This has the advantage of hiding the memory pool and being more compatible with the Message API that I proposed. I passed an extra A argument so as to permit moves into the closure, since this is effectively a once fn.

[steveklabnik]

triage: arena isn't going to be stabilized for quite some time. I'd probably just close this, as it's quite old and so much has changed, but i'll leave that up to @nikomatsakis

[nikomatsakis]

Sure, not sure how much it helps to have it around.