Feature: Slice with capacity

[straight-shoota]

A slice in Crystal is just a fat pointer, an address and a size. That together describes a concrete region of memory.
This is good for representing a fixed number of elements.
Then there's Array which is a very dynamic data structure. You can add and remove elements, and it resizes its buffer dynamically (currently, it only grows, but there's #8209).

We're missing something in between: A data structure that holds a dynamic number of elements in a fixed size buffer. A flexible container backed by a static memory buffer. It has methods such as push and pop, which are typical for dynamically sized list types, but unavailable in Slice.
This could be represented as a slice with capacity: It consists of an address, the currently occupied size, and the capacity.
Conceptually, Slice would be equivalent to a "slice with capacity" where size and capacity are identical.

A very rudimentary implementation is the BraceStack type from #15607. It only supports push and pop, because this specific use case doesn't need more. But it could easily implement Indexable::Mutable. Shift and unshift could also be implemented, but they'd always require a memcpy (or another field to hold the start offset, like Array does).

A major downside over an array is of course that the memory backend is limited. This type never allocates or reallocates.

This brings us to the benefits: Pointers into the buffer are safe and in sync because it never changes the memory location. And it allows using arbitrary backends for the buffer, including putting it on the stack to avoid allocations entirely.

A related type is Pointer::Appender which also supports the push operation, but nothing else (I suppose it could support more if necessary). But the main restriction is that it's unbound. It is not aware of capacity.

Crystal::SmallDeque is a very similar type in the internal API of the standard library. It's basically the equivalent of Deque instead of Array. And it's hard-wired to a StaticArray backend, so the capacity is fixed at compile-time.

An inlined StaticArray might not be ideal for a general purpose implementation. I think there's great value in being able to handle any memory buffer (i.e. a Slice), which gives the user full flexibility about where it's allocated.

[ysbaddaden]

That would be very nice. There are definitely use cases where we can expect an array to never be larger than N yet still need to accommodate from 0 to N elements.

I wrote StackArray(T, N) some years ago to have a bounded dynamic array allocated on the stack.