Array design sketch

[geoffromer]

I'm starting to sketch out a proposal for arrays and slices. Here's what I have in mind:

• StaticArray(T, N) is basically equivalent to std::array<T, N>, except that it's the fundamental fixed-size array type, not a library wrapper for something else.
• BoxedArray(T) is roughly equivalent to std::unique_ptr<T[]>: provides the API of an array whose size is fixed when the array is created (i.e. at run-time), and is implemented in terms of a single uniquely-owned pointer.
• RuntimeSizedArray(T) is what that pointer points to: an array whose size is fixed when the array is created (i.e. at run-time). It has no standard C++ counterpart, but it's somewhat comparable to a C variable-length array or flexible array member. It's an unsized type, which will make it awkward to work with, so I expect people to use BoxedArray(T) unless they specifically need to avoid the indirection and/or the ownership semantics.

Resizable arrays and other pure library types are out of scope (BoxedArray is a pure library type, but I'm including it because RuntimeSizedArray would look kind of alarming on its own).

These types will all support subscripting with i64, and have Length and Slice methods. I expect them to eventually support iteration, equality comparison, ordering, and hashing, but we don't have interface designs for those yet. We might also want to define an Array(T) interface expressing all that, but I'm not sure whether that will be useful.

They will all support initialization from a tuple of the appropriate size, if the tuple element types are all convertible to T.

• Slice(T) is basically equivalent to std::span<T>. It supports all the same operations as the array types except for equality, ordering, and hashing (which I'd like to leave as future work because they're an utter minefield), and also supports assignment.

Names are all subject to bikeshedding, and we may want to have a more concise and/or "built-in feeling" type syntax for Slice, StaticArray, and perhaps BoxedArray, but I don't plan to include that in the initial proposal.

The proposal won't cover multidimensionality because we don't have a design for variadics yet, and because I'm undecided about whether to use these types for the multidimensional case (where things like Length and iteration get awkward), or have a separate family of types for that.

Any thoughts on whether this sounds like the right general direction?

[fowles]

Why is RuntimeSizedArray(T) not a Slice(T)? Does RuntimeSizedArray(T) know its size or is that expected to be held externally?

[tkoeppe]

Is the RuntimeSizedArray(T) usable on its own? If so, wouldn't it have to carry an array cookie like in C++/Itanium-ABI to allow for correct object destruction? And if so, should we instead make that an explicit part of the language design, so as to avoid duplicating information (in cases where the size is both in the array cookie and in the library type like BoxedArray)?

[fowles]

How can RuntimeSizedArray(T) own its contents if it can be a flexible array member?

Is the thing I am missing here that RuntimeSizedArray(T) has no indirection? It is a value type of dynamic size?

[geoffromer]

How can RuntimeSizedArray(T) own its contents if it can be a flexible array member?

Is the thing I am missing here that RuntimeSizedArray(T) has no indirection? It is a value type of dynamic size?

Yes, exactly.

[geoffromer]

Does RuntimeSizedArray(T) know its size or is that expected to be held externally?

That's a good question. I'd like the answer to be "yes" for safety/usability reasons, but StaticArray and RuntimeSizedArray are supposed to be the lowest-level array types available, so if we think Carbon will have use cases for non-size-carrying arrays, it'd have to be "no".

On further reflection, I suspect the existence of things like sized delete and destroying delete is pretty solid evidence that there are important use cases for non-size-carrying dynamic arrays, and so RuntimeSizedArray(T) won't know its own size. I'm also realizing that since it doesn't carry its own size, it won't support most of the API I listed above; pretty much everything besides subscripting and slicing would require it to know its length.

Is the RuntimeSizedArray(T) usable on its own? If so, wouldn't it have to carry an array cookie like in C++/Itanium-ABI to allow for correct object destruction? And if so, should we instead make that an explicit part of the language design, so as to avoid duplicating information (in cases where the size is both in the array cookie and in the library type like BoxedArray)?

It will be usable on its own, but not exactly friendly to use on its own. In particular, you'll need to explicitly supply the size when deallocating it (and might need to manually destroy its elements first).

[fowles]

This reminds me of something I occasionally want in C++. Make the destructor an overload set where people can explicitly call a dtor with args. For this case, you would add a dtor with a size argument and delete the zero arg dtor.

[foxtran]

RuntimeSizedArray(T) is close to Fortran's allocatable arrays. With standard library, in Fortran, it is possible to reallocate them.