//! Bump allocator for compiler data structures.

//!

//! Provides a simple arena-style allocator that allocates from a contiguous

//! byte buffer. Memory is never freed individually - the entire arena is

//! reset at once. This is ideal for compiler passes where all allocations

//! have the same lifetime.

@test mod tests;

/// Largest byte extent representable by allocator APIs.

constant MAX_EXTENT: u32 = 0xFFFFFFFF;

/// Error thrown by allocator.

export union AllocError {

    /// Allocator is out of memory.

    OutOfMemory,

}

/// Bump allocator backed by a byte slice.

///

/// Allocations are made by advancing an offset pointer. Individual allocations

/// cannot be freed; instead, the entire arena is reset at once via [`reset`].

export record Arena {

    /// Backing storage.

    data: *mut [u8],

    /// Current allocation offset in bytes.

    offset: u32,

}

/// Create a new arena backed by the given byte slice.

export fn new(data: *mut [u8]) -> Arena {

    return Arena { data, offset: 0 };

}

/// Allocate `size` bytes with the given alignment.

///

/// `size` must be nonzero and `alignment` must be a nonzero power of two.

/// Returns an opaque pointer to the allocated memory. Throws `AllocError` if

/// the arena is exhausted or its offset lies beyond the backing storage. The

/// caller is responsible for casting to the appropriate type and initializing

/// the memory.

export fn alloc(arena: *mut Arena, size: u32, alignment: u32) -> *mut opaque throws (AllocError) {

    assert alignment > 0;

    assert (alignment & (alignment - 1)) == 0;

    assert size > 0;

    let capacity = arena.data.len as u32;

    if arena.offset > capacity {

        throw AllocError::OutOfMemory;

    }

    let available = capacity - arena.offset;

    let padding = (0 - arena.offset) & (alignment - 1);

    if padding > available {

        throw AllocError::OutOfMemory;

    }

    let alignedAvailable = available - padding;

    if size > alignedAvailable {

        throw AllocError::OutOfMemory;

    }

    let aligned = arena.offset + padding;

    let newOffset = aligned + size;

    let base: *mut u8 = &mut arena.data[aligned];

    set arena.offset = newOffset;

    return base as *mut opaque;

}

/// Reset the arena, allowing all memory to be reused.

///

/// The caller must not use any allocation from this arena after the reset.

/// Does not zero the memory.

export unsafe fn reset(arena: *mut Arena) {

    set arena.offset = 0;

}

/// Save the current arena state for later restoration.

export fn save(arena: *Arena) -> u32 {

    return arena.offset;

}

/// Restore the arena to a previously saved state, reclaiming all

/// allocations made since that point.

///

/// The caller must not use an allocation reclaimed by this operation.

export unsafe fn restore(arena: *mut Arena, savedOffset: u32) {

    set arena.offset = savedOffset;

}

/// Returns the number of bytes currently allocated.

export fn used(arena: *Arena) -> u32 {

    return arena.offset;

}

/// Returns the number of bytes remaining in the arena.

export fn remaining(arena: *Arena) -> u32 {

    return arena.data.len as u32 - arena.offset;

}

/// Return an exclusive view of the remaining buffer.

///

/// The caller must end access through the view before another arena operation.

export unsafe fn remainingBuf(arena: *mut Arena) -> *mut [u8] {

    return &mut arena.data[arena.offset..];

}

/// Commit `size` bytes of allocation and advance the offset.

///

/// The caller must provide a size within the view returned by [`remainingBuf`]

/// and must end access through that view before another arena operation.

export unsafe fn commit(arena: *mut Arena, size: u32) {

    assert size <= remaining(arena), "alloc::commit: size exceeds remaining capacity";

    set arena.offset += size;

}

/// Allocate a slice of `count` elements, each of `size` bytes with given alignment.

///

/// Returns a type-erased slice that should be cast to the appropriate `*[T]`.

/// The slice length is set to `count` (element count, not bytes).

/// Throws `AllocError` if the arena is exhausted or the total byte extent

/// cannot be represented by `u32`.

export fn allocSlice(arena: *mut Arena, size: u32, alignment: u32, count: u32) -> *mut [opaque] throws (AllocError) {

    if count == 0 {

        return &mut [];

    }

    if size > MAX_EXTENT / count {

        throw AllocError::OutOfMemory;

    }

    let ptr = try alloc(arena, size * count, alignment);

    return @sliceOf(ptr, count);

}

/// Generic allocator interface.

///

/// Bundles an allocation function with an opaque context pointer so that

/// any allocation strategy (arena, free-list, mmap, pool) can be used

/// through a uniform interface. The `func` field is called with the context

/// pointer, a byte size and an alignment, and must return a pointer to

/// the allocated memory or panic on failure.

export record Allocator {

    /// Allocation function. Returns a pointer to `size` bytes

    /// aligned to `alignment`, or panics on failure.

    func: fn(*mut opaque, u32, u32) -> *mut opaque,

    /// Opaque context pointer passed to `func`.

    ctx: *mut opaque,

}

/// Create an `Allocator` backed by an `Arena`.

export fn arenaAllocator(arena: *mut Arena) -> Allocator {

    return Allocator {

        func: arenaAllocFn,

        ctx: arena as *mut opaque,

    };

}

/// Arena allocation function conforming to the `Allocator` interface.

fn arenaAllocFn(ctx: *mut opaque, size: u32, alignment: u32) -> *mut opaque {

    let arena = ctx as *mut Arena;

    return try! alloc(arena, size, alignment);

}