This manifesto outlines a plan to add compound types corresponding to fixed-size scoped-storage homogenous containers.
- Bring a fixed-size, scoped-storage array type to Swift
- Use declaration and dereference syntax similar to
Array. Possibly other members too. - Support using definitive initialization per element, to avoid having to initialize the whole array at once with a dummy value to then have the elements immediately replaced with their real values.
- Support using multiple dimensions, instead of faking it with nested one-dimensional arrays.
- Give context that LLVM could use their array and/or SIMD primitives as needed.
- Support more kinds of arrays and array segments from C interfaces.
- Support using arrays as a register-storage type as needed (The type probably has to fit within the processor's SIMD types.)
Add a new chapter, "More Compound Types," probably between the "Opaque Types" and "Automatic Reference Counting" chapters. It'll have the following sub-chapters.
(not done)
(not done)
- There is a new keyword used in statements:
reify. - There is a new keyword that starts with a number sign:
#indexOf. - There are new tokens reserved as punctuation and can’t be used as custom operators:
_!,_?,!.., and?..
A compound type is a type without a name, defined in the Swift language itself. There are three compound types: function types, tuple types, and grid array types. A compound type may contain named types and other compound types. For example, the tuple type (Int, (Int, Int)) contains two elements: The first is the named type Int, and the second is another compound type (Int, Int).
Swift provides three models of containers for storing general elements as a single block: standard arrays, grid arrays, and grid array templates.
Standard arrays are a syntactic sugar provided for the Swift standard library Array<Element> type:
[ type ]
In other words, the following two declarations are equivalent:
let someArray: Array<String> = ["Alex", "Brian", "Dave"]
let someArray: [String] = ["Alex", "Brian", "Dave"]In both cases, the constant someArray is declared as an array of strings. The elements of an array can be accessed through subscripting by specifying a valid index value in square brackets: someArray[0] refers to the element at index 0, "Alex".
You can create multidimensional standard arrays by nesting pairs of square brackets, where the name of the base type of the elements is contained in the innermost pair of square brackets. For example, you can create a three-dimensional array of integers using three sets of square brackets:
var array3D: [[[Int]]] = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]]When accessing the elements in a multidimensional array, the left-most subscript index refers to the element at that index in the outermost array. The next subscript index to the right refers to the element at that index in the array that’s nested one level in. And so on. This means that in the example above, array3D[0] refers to [[1, 2], [3, 4]], array3D[0][1] refers to [3, 4], and array3D[0][1][1] refers to the value 4.
Unlike standard arrays, grid arrays lock their length at initialization but keep the storage for their elements inline with other objects in the same scope. Grid arrays use a syntax similar to standard arrays, but precede the element type with a list of extents, one for each index axis. Some adaptations of the previous someArray are:
let someArray: [3 ; String] = ["Alex", "Brian", "Dave"]
let someArray: [_ ; String] = ["Alex", "Brian", "Dave"]In both cases, the constant someArray is declared as a linear grid-array of strings. The first array is a compile-time sized array, since its only extent is an immediate bound, which are indicated by using an integer literal for the bound. The second array is a run-time sized array, since its only extent is a deferred bound, which are indicated by using a placeholder token; the array's length is determined by the count of terms of the initializing array literal. If that second array is declared in a code block, the compiler may optimize it to a compile-time sized array (always if it doesn't escape, otherwise it depends on context). Individual elements may be dynamically dereferenced with a subscript, or statically dereferenced with an index number, such as either someArray[0] or someArray.0 for "Alex".
Besides creating multidimensional grid arrays via nesting:
var array3D: [2 ; [2 ; [2 ; Int]]] = [[[1, 2], [3, 4]], [[5, 6], [7, 8]]]Grid arrays using multiple coordinates may be declared with a more compact, inline syntax:
var array3D: [2, 2, 2 ; Int] = [1, 2, 3, 4, 5, 6, 7, 8]The indices for a specific element are specified in a single subscript call, such as array3D[0, 1, 1] for 4. The subscript call cannot take fewer arguments (i.e. no partial dereference). When assigned from an array literal, the grid is flattened and each element corresponds to a set of indices in lexicographic order, where the rightmost index varies the fastest. The flattened mapped order is also an element's static index, such as array3D.3 for 4.
Grid arrays used in enumeration case payloads must use immediate bounds for all extents.
Grid array templates describe families of grid array types, acting like constraints, and possibly existentials. A template is distinguished from a grid array type by either having at least one existential bound in the extent list, having an opaque type for the element type, or both.
let someArray: some [_! ; String] = ["Alex", "Brian", "Dave"]
let someArray: some [_? ; String] = ["Alex", "Brian", "Dave"]In both cases, the constant someArray is declared as a linear grid-array of strings. This time, the exact types are hidden behind an opaque type of a grid array template that is existential in the extent list. The list specifies exactly one extent. For the first array, the implied extent must be determined at compile-time. For the second array, the implied extent may be determined at run-time.
A template that is existential in only the extent list may be used as an existential type. A template that is existential in at least the element type may only be used as a constraint.
func processStrings<T: [?.. ; some StringProtocol]>(_ strings: T) { /*...*/ }
func processStringList(_ strings: [_? ; String]) { processStrings(strings) }The processStrings function takes a single grid array as an argument. Said argument's type may have any number of extents (including zero), may be a run-time sized array, and have any element type as long as that type conforms to StringProtocol, such as String or Substring. The processStringList function takes a single linear grid-array of String as an argument, where the argument's extent could be determined at run-time.
For a detailed discussion of the Swift standard library Array type, see Arrays. For a detailed discussion of grid arrays and grid array templates, see Grid Arrays.
Grammar of an Array Type
array-type → [ grid-specifieropt type ]
grid-specifier → grid-specifier-listopt ;
grid-specifier-list → singular-grid-specifier-list ,opt
grid-specifier-list → singular-grid-specifier-list , length-agnostic-existential-grid-specifier
grid-specifier-list → length-agnostic-existential-grid-specifiersingular-grid-specifier-list → singular-grid-specifier
singular-grid-specifier-list → singular-grid-specifier , singular-grid-specifier-listsingular-grid-specifier → definitive-grid-specifier | existential-grid-specifier
definitive-grid-specifier → immediate-grid-specifier | deferred-grid-specifier
immediate-grid-specifier → integer-literal
deferred-grid-specifier → _
existential-grid-specifier → _! | _?
length-agnostic-existential-grid-specifier → !.. | ?..
In contexts that don’t impose a compile-time total size of objects, objects can have a type whose size is deferred until runtime. These loosely-sized types are defined as either:
- A grid array with at least one runtime-sized extent.
- A grid array with a loosely-sized type as its element type.
- A tuple with at least one member that is of a loosely-sized type.
Objects of these types can only be declared in:
- Code blocks, including at the top level.
- Type-level stored properties.
- Instance-level stored properties for a
class. - Function arguments.
They cannot be used for:
- Computed properties.
- Instance-level stored properties for a
struct. - A payload for an
enumcase, or part thereof. - Function returns.
If not initialized at declaration or by a single post-declaration assignment, loosely-sized types need to be reified before being initialized in piecemeal.
For more on loosely-sized types, see Flexible Compound Types.
primary-expression → grid-index-expression
Within a for-inout loop, a grid index expression reveals the index coordinates of the selected loop variable during an iteration. The loop variable can be for any active loop, not just for the innermost one. (If multiple loops use the same identifier for their loop variables, the innermost one is used.) It has the type of [N ; Int], where N is the number of extents the loop's targeted grid array.
let array: [3 ; String] = ["a", "b", "c"]
for e inout array {
print(e, #indexOf(e))
}
/*
Prints:
a [0]
b [1]
c [2]
*/Grammar of a Grid Index Expression
grid-index-expression → #indexOf ( identifier )
An explicit member expression allows access to the members of a named type, a tuple, grid array, grid array template, or a module. It consists of a period (.) between the item and the identifier of its member.
Sub-Sub-Chapter "Explicit Member Expression", Add New Paragraphs After the Third One and Its Code Block
The members of a grid array are implicitly named using integers generated by translating an element's index coordinates to their lexicographic order, where the rightmost index varies the fastest, starting from zero. For example:
let a: [; Int] = [0], c: [2, 2 ; Int] = [3, 4, 5, 6]
var b: [2 ; Int] = [1, 2]
b.0 = a.0 // b[0] assigned the only element of a (i.e. a[[]])
b.1 = c.3 // b[1] assigned c[1, 0] (or c[[1, 0]])
// Now b is [0, 5]Both grid arrays and grid array templates can have additional members to support their pseudo-protocols. (Author note: need to fill this in, or possibly remove it, after doing the guide chapters.)
A subscript expression provides subscript access for named types using the getter and setter of the corresponding subscript declaration, or the equivalent built-in access operations for grid arrays and existentials of grid array templates. It has the following form:
statement → reification-statement
Loop statements allow a block of code to be executed repeatedly, depending on the conditions specified in the loop. Swift has four loop statements: a for-in statement, a while statement, a repeat-while statement, and a for-inout statement.
loop-statement → for-in-out-statement
A for-inout statement allows a block of code to be executed once for each element of a grid array. If the array wasn't completely initialized when starting the loop, any element that receives an assignment during the looping statement will be initialized, leaving the array definitively initialized if no uninitialized element skips initialization.
A for-inout statement has the following form:
foriteminoutarray{
statements
}
Where the item is a proxy for the current element of the targeted array. The proxy's type is the array's element type; the proxy has the same immutable vs. mutable vs. mutable-until-initialized status as the array. A grid-index expression can be used to determine which element of the array is being touched. The visitation order of elements is unspecified to allow optimization.
Since the initialization state of the entire array may be in flux during the loop, it is an error to use any instance-level properties/methods of the array in the code block when the array isn't considered completely initialized, including accessing other elements (or the current element outside of the proxy). Even after initialization, it is an error to apply mutation to the array during a loop except for the current element's proxy. After a proxy is initialized (if not already) for a mutable array, the proxy can be used for an inout function argument.
Grammar of a For-In-Out Statement
for-in-out-statement → for identifier inout expression code-block
(Author note: I don't know how much of this, if any, should be moved to the guide.)
When one of these types of objects:
- A compile-time sized grid array using at least one deferred extent,
- An opaque type constrained by a grid array template,
- A loosely-sized type,
is declared without an initial expression, then definitive initialization cannot take place until the shapes and element types of all contained grid arrays are finalized. A reification statement declares the needed finalization. The statement specifies its target object or sub-object then that object's final type.
typealias MyType = (Int, [_ ; [_? ; Bool]], some [_!, _! ; some Codable])
// This will be sized at compile-time if it doesn't escape, run-time sized otherwise.
let someArray: [_ ; MyType]
// Note that the element type's second member's element type stays as-is,
// because it's an existential.
reify someArray as [3 ; (Int, [8 ; [_? ; Bool]], [16, 25 ; Double])]Any final type chosen must abide by:
- If the target object is a grid array, the final type is a copy of the target's type except:
- Each non-immediate extent is replaced by an immediate extent. Replaced values must be compile-time constants (i.e. integer literals) unless that extent is run-time sized. It is an error to use a negative value for an extent.
- If the element type can qualify for reification, then it's replaced by a reified version.
- If the target object is an opaque type constrained by a grid array template:
- The final type must be a grid array type that conforms to the template, but doesn't need further reification.
- If the target object is a tuple, the final type is a copy of the target's type except:
- Any members whose type qualifies for reification must have their type replaced by a reified version.
A reification statement cannot target an element of a grid array or sub-object thereof. Reify a qualifying outer object instead, which locks the same finalization for all elements of the grid array.
// Reuse the same "MyType" and un-reified "someArray" from the last example.
// Both errors: cannot reify an element of an un-reified array
reify someArray.0 as (Int, [8 ; [_? ; Bool]], [16, 25 ; Double])
reify someArray[1] as (Int, [8 ; [_? ; Bool]], [16, 25 ; Double])
// OK: reify the array, which reifies each element (if not empty)
reify someArray as [3 ; (Int, [8 ; [_? ; Bool]], [16, 25 ; Double])]An object or sub-object may be reified multiple times, via identical or overlapping targets, but the final result must be the same each time.
// Reuse the same "MyType" from two examples ago.
let tuple: MyType
reify tuple.1 as [8 ; [_? ; Bool]]
reify tuple as (Int, [8 ; [_? ; Bool]], [16, 25 ; Double])
// Error: tuple.2 is inconsistent
reify tuple.2 as [3, 100 ; UInt]Reification can occur in a code branch, as long as a target gets reified at least once before its definitive initialization starts. For a named type, reification of stored instance properties must occur in each designated initializer. If the object is not a loosely-sized type, then the results of reification must be the same across all code paths (branches and/or initializers).
class Sample1 {
var someArray: [_ ; Int]
init(_ flag: Bool) {
if flag {
reify someArray as [3 ; Int]
} else {
reify someArray as [4 ; Int] // OK
}
}
}
struct Sample2 {
// This grid array has its sized fixed at compile time.
var someArray: some [_! ; Int]
init(_ dummy: Int) {
reify someArray as [3 ; Int]
//...
}
init(_ dummy1: Double, _ dummy2: Bool) {
reify someArray as [4 ; Int] // Inconsistent with the first initializer
//...
}
}Grammar of a Reification Statement
reification-statement → reify expression as type
- Immediate specifiers (i.e. integers) match another immediate specifier only if they have the same value.
- Immediate specifiers subtype any other kind of specifier.
- A deferred specifier ("
_") matches itself. - A deferred specifier subtypes both the deferred existential specifier ("
_?") and deferred length-agnostic existential specifier ("?.."). - An immediate existential specifier ("
_!") matches itself. - An immediate existential specifier subtypes any other existential specifier.
- A deferred existential specifier matches itself.
- A deferred existential specifier subtypes the deferred length-agnostic existential specifier.
- An immediate length-agnostic existential specifier ("
!..") matches itself. - An immediate length-agnostic existential specifier subtypes the deferred length-agnostic existential specifier.
- A deferred length-agnostic existential specifier matches itself.
Grid Specifier Lists: When Comparing Potential "Subtype" X to Non-Identical Potential "Super-type" Y
- If two specifier lists have the same length, compare corresponding specifiers, starting from the first from each list.
- (Remember that a specifier list can have at most one length-agnostic specifier, and it must be last.)
- X can be longer than Y only if Y ends with a length-agnostic specifier and all members of the suffix of X can match/subtype Y's last specifier. The non-last specifiers of Y have to match/super-type the prefix of X.
- Y cannot be longer than X.
- X and Y must have the same element type.
- The specifier list of X must be a "subtype" of the list for Y.
- If Y's element type is not an opaque type, then it must be the same as X's element type.
- If Y's element type is an opaque type, X's element type must conform to Y's element type's constraint.
- The specifier list of X must match or "subtype" the list for Y.
- If Y's element type is not an opaque type, then it must be the same as X's element type.
- If Y's element type is an opaque type, but X's element type is not, then X's element type must conform to Y's element type's constraint.
- If both X and Y's element types are opaque, then X's element type's constraint must match or refine Y's element type's constraint.
- The specifier list of X must match or "subtype" the list for Y.
For a grid array with N total elements of type T, it should have a stride that is N times the stride of T.
For C compatibility, grid arrays should have the same layout as the current tuple adaptation. For example, a [2, 3 ; [5 ; Int]] array should be compatible with an ((Int, Int, Int, Int, Int), (Int, Int, Int, Int, Int), (Int, Int, Int, Int, Int), (Int, Int, Int, Int, Int), (Int, Int, Int, Int, Int), (Int, Int, Int, Int, Int)) tuple. A grid array with one element has the same representation as the bare element type; an empty grid array has the same representation as Void.
Grid arrays should replace homogenous tuples when mapping over C arrays where the extents are known. When C has a function with an array segment for a parameter or declares an extern array without specifying its length, then either a grid array with a deferred bound or an opaque grid array template with immediate existential bounds may be used. Since C doesn't have true multi-dimensional arrays, it will take an artisan's touch to know when to keep the Swift version as nested arrays or to make the extents inline. C's variable-length array feature also maps to grid arrays with deferred bounds (but now run-time sized).
If a grid array is initialized with an array literal, then at most one extent cannot be immediate. The count of terms in the literal is divided by the product of the other extents to determine the value of the deferred extent. There must not be a remainder from the division. When all extents are immediate, their product must equal the number of terms in the literal.
// The second extent is determined to be 3.
let a: some [2, _! ; Int] = [1, 2, 3, 4, 5, 6]
// Error: The number of terms isn't divisible by 15.
let b: [_, 3, 5 ; Int] = [1, 2, 3, 4, 5, 6, 7]When declaring a grid array of grid arrays with an initial array literal, and some of the inner array's extents are not immediate, then those extents have to be consistent across every outer element.
// The length of the inner arrays is 3.
let a: [2 ; [_ ; Int]] = [[1, 2, 3], [2, 3, 4]]
// Error: The lengths of the inner arrays are inconsistent.
let b: [_ ; some [_! ; Int]] = [[1, 2, 3, 4], [3, 4], [5, 6, 6, 7]]
// Same error as "b"; run-time sized grid arrays do NOT support ragged configurations!
let c: [3 ; [_, 2 ; Int]] = [[1, 2, 3, 4], [3, 4], [5, 6, 6, 7]]If a grid array has zero elements, then none of the following methods can be used. A grid array has zero elements if at least one extent has the value of zero. (A zero-dimensional grid array has one element.)
An element for a grid array with N dimensions can be dereferenced using a subscript with N Int arguments. (Once variadic generics are supported, anything conforming to BinaryInteger should work.) A particular argument must have a value of at least 0 and less than the value of the corresponding extent. A subscript call cannot use an empty argument list, so this method can't work for a zero-dimension grid array.
An element for a grid array with N dimensions can be dereferenced using a subscript with an [N ; Int] argument. (We should support any [N ; T] where T conforms to BinaryInteger.) Each element of the argument array has the same restrictions as the separate-argument version above. For a zero-dimensional array, use a value of type [0 ; Int] as the argument.
An element for a N-dimensional grid array with M elements total can be dereferenced using a tuple index member, where the index can range from zero to one less than M. The index numbers are checked for validity at compile-time unless the array's size can't be determined until run-time. A run-time error occurs if the index number is out of range. To get the index number for a given element, get all M values of [N ; Int] that are valid arguments for the subscript that takes an array parameter. Arrange those values in lexicographic order, and the rank of a given index-array in that list is the corresponding element's tuple index member. For instance, .0 is the member for the first element of a grid array (including the sole element of a zero-dimensional grid array or any other grid array that has exactly one element). A four-element one-dimensional grid array has members .0, .1, .2, and .3, corresponding to theArray[0], theArray[1], theArray[2], and theArray[3], respectively. The two-by-two grid array has the same four tuple index members, but now they correspond to the2dArray[0, 0], the2dArray[0, 1], the2dArray[1, 0], and the2dArray[1, 1], respectively. (The correspondences are the same whether the array uses either row- or column-major storage order.)
Should there be functions to convert one-dimensional grid arrays to/from homogenous tuples? Probably needs variadic generics.
Need function to break up a grid array into two along a given index axis and an index on that axis.
Need function to fuse two grid arrays along a given axis. The two arrays need to have the same number of dimensions and the same values for corresponding extents except for the axis that will be merged together. Probably needs to wait until values can be used with a generic parameter declaration (since that's where the merger axis needs to specified at).
Should there be a function to convert a grid array to any other grid array type as long as both types have the same stride and have the same innermost non-array element?
Need function that takes a grid array and a closure to escape an array to an Unsafe*BufferPointer. (It needs to escape instead of being a straight punning because the array may be implemented as a SIMD type!) There needs to be a way to get a list mapping each array index to a memory offset, so we can do that mapping during the Unsafe*BufferPointer escaping functions. (The buffer offsets are the same as the tuple index when we're using C order. They won't be the same for Fortran order!)
The access level of a grid array type or grid array template is the level of its element type.
(If we someday support compile-time named constants and/or expressions, and their use for grid array extents, then the access level of a grid array type or grid array template is the most restrictive out of the element type and any named/calculated extent values.)
(not done)
Since loosely-sized types cannot be used in contexts that require stored sub-objects with fixed strides, just letting said types effortlessly match generic parameters may be a mistake. The “loose Any” protocol is a super-type of Any to provides another constraint. Any will still be the default for un-tagged generic parameters.
Should loose Any be allowed to work as an existential type, like Any can?
- Should there be an attribute on (multidimensional) grid arrays that they store their elements in Fortran order (i.e. column-major order)?
- Should there be an attribute to suggest that a grid array should be implemented as an SIMD type?
If we get rid of the .0, .1, etc. syntax, then the only way to definitively initialize a grid array would be with an initial expression, a whole-object assignment, or a for-inout loop. (We can't use subscripts because the arguments may be run-time defined, preventing non-trivial determination of DI.) I'm strangely OK with making a rule that piecemeal DI has to go through for-inout loops. There are still complications with:
- Is it OK to have multiple
for-inoutloops for a grid array? (Leaning towards yes) - Is it OK if some of the loops are behind
if/elseor similar code branches? (yes) - Do we allow loops that have some way to skip an element from being initialized, like:
continuebreakthrow, but the catch is soon enough after the loop such that the array is still around- Having code branches, but not every branch has an initialzing event
- Straight up not having an initializing event within the loop
How much work do/should we put in before/between/after each for-inout loop to check the initialization status of grid array elements? Should we optimize to skip the checks when the loop touches every element (i.e. no continue/break/throw and every branch has an initializing event)?
- Could we remove some restrictions on where loosely-sized types can go? Specifically, could they be adapted for function returns and computed properties (at least for functions that don't need C compatibility)?
- When we have a potential subtype X and super-type Y, and both types' element types are not opaque, should there be a relationship if Y's element type is a super-type of X's element type? Right now there isn't, so
[3 ; Int]currently is not a subtype of[3 ; Int?]. Allowing element-level sub-typing upgrade to the array-level is easy if the element types share a to-the-metal representation, so element-level type punning translates to array-level type punning. But if the element types don't share a representation, then going to an array-level super-type requires many calls of the element-level conversion function. - Should grid arrays conform to
Equatableif the element type does? The problem is if arrays that share a shape and element type, but different storage attributes (like row- vs. column-major order) should be comparable. With different storage philosophies, you can't just do raw comparisons between buffers; at least one of the iterated arrays has to jump around in memory. Similar issues exist forHashable,Decodable, andEncodablesupport. - Should zero- or one-dimensional grid arrays conform to
Comparablewhen their element type does? For consistency (but not implementation), there is the same problem as withEquatablewhether arrays with different storage orders should be comparable. - Should classes and tuples be limited to only one stored member of a loosely-sized type. (When a tuple needs to be compatible with C, the loosely-sized member needs to be last. In other cases, we'll do that secretly as needed.) What about in code blocks? If code blocks wouldn't need to be restricted to one loosely-sized variable, I'm not sure why classes/tuples would. (That last statement made me waffle on whether to ask this at all.)
(not done)