Compile-Time Values and Integer Generics

Evolution Discussion
1

Hi Swift Forums. :waving_hand:

Together with @kubamracek, @Joe_Groff, @tbkka and @Douglas_Gregor we have been discussing a path forward for the interaction of the work-in-progress @const feature and the feasibility and possible designs for allowing @const integer values to be specified as arguments to integer generic parameters. Currently, only literal integer values are allowed. We would like to propose a design for how this would work and would like to get your feedback on it early on - please let us know what you think!
The text below will use the example of InlineArray a bunch, but the discussion applies to Integer Generics broadly.

Goal

With the current state of Integer Generics proposal, programmers can only use literal values to specify generic arguments. With the work-in-progress @const compile-time values proposal, it becomes desirable to loosen this restriction and allow programmers to specify any @const integer value as the generic argument. Then, for example, InlineArray can be specified using an expression for the size parameter:

@const let line_size: Int = 128
...
let foo: InlineArray<4 * line_size, Int>

Type-Checking Without Knowing Concrete Values of @const Variables

The key aspect of the @const design that calls for care in how compile-time values interact with integer generics is that @const values do not participate in the Type System. Compile-time knowability is a property of values (variables, parameters, etc.) and computation (expressions, functions, etc.) thereof, but never the corresponding type (See the (Non-)Participation in the Type System section in the Pitch).
This means the type-checker has no way to discern what the concrete value of the integer generic parameter is. When using a non-literal @const argument, the value is therefore opaque. This has several implications:

  1. Mangling of entities containing integer generic parameters with @const value arguments must be performed without knowledge of the argument value, i.e. instances of the same type with an integer generic parameter which differ by the generic argument value will be mangled as the same opaque type, during type-checking.
  2. When the integer generic argument value is not known during type-checking, function overloading based on such values specified to an integer generic parameter is not possible.

For (1), downstream from type-checking, the compiler will ultimately resolve the @const value to a concrete integer value, and be able to ensure that instances of a given type with the same integer generic argument value end up with an identical runtime mangling and type representation.

Proposed Solution

Treat all instances of types with a generic integer parameter as having an opaque integer value argument. All types which vary only in the possible value of an integer generic parameter are considered equal in the type-checker, but get distinct integer-generic-argument-specific runtime metadata.

This means the following variables have the same type according to the type-checker:

let foo : InlineArray<2, Int>
let bar : InlineArray<4, Int>

And that the following is not valid:

public func foo(_ input: InlineArray<4, Int>) { ... }
public func foo(_ input: InlineArray<2+2, Int>) { ... } ❌ error: cannot overload 'foo' based on solely integer generic argument values
public func foo(_ input: InlineArray<2, Int>) { ... } ❌ error: cannot overload 'foo' based on solely integer generic argument values

We expect that programmers will be able to work around this restriction by encapsulating their integer-value-generic types in structures, or defining their API as integer-value-generic in the first place.

This design requires an additional post-type-checking and post-@const-evaluation mandatory diagnostic/verification stage for several possible issues which may arise. For example:

vat foo : InlineArray<2, Int>
foo = [1,2,3,4] // ❌ error: cannot assign value of type 'InlineArray<4, Int>' to type 'InlineArray<2, Int>'

The type-checker will determine that the values on both the LHS and the RHS of the assignment operation to foo are of InlineArray<{Opaque-Int-Value}, Int>. The subsequent aforementioned diagnostic pass will exist in the compilation stage which is able to compare argument values and issue the diagnostic in the example.
Similarly, this must be done for all other instances where an assignment is performed. Another example:

func foo(_ input: InlineArray<2, Int>) -> InlineArray<4, Int> { ... }

let bar = foo([1, 2, 3]) ❌ error: cannot assign value of type 'InlineArray<3, Int>' to type 'InlineArray<2, Int>'
let baz: InlineArray<2, Int> = foo([1, 2]) ❌ error: cannot assign value of type 'InlineArray<4, Int>' to type 'InlineArray<2, Int>'

Multiple Overloads From Different Modules

Further ambiguity emerges if multiple modules provide different overloads which differ only in the integer generic parameter argument value. For example:

// ModuleA:
func foo(_ input: InlineArray<2, Int>) { ... }

// Module B:
func foo(_ input: InlineArray<4, Int>) { ... }

// Client:
import A
import B
foo([1, 2]) ❌ error: ambigous refernce to 'foo'

Here, in order to be able to call foo, the user would have to explicitly disambiguate it with the module name, e.g. ModuleA.foo regardless of the concrete type of the argument value.

Runtime type equality

This design preserves the ability to express runtime type equality checks for all types with integer generic parameters. That is, at runtime:

InlineArray<8, Int>.Type == InlineArray<16, Int>.Type // ❌ false
InlineArray<8 * 2, Int>.Type == InlineArray<16, Int>.Type // ✅ true

Regardless of the fact that the type-checker is not able to distinguish the comparison, with each type getting a unique runtime mangling which uses the resolved @const concrete value.

Same-Type Constraints

This design has an implication of not allowing same-“type“ constraints on integer generic parameter values, because the type-checker would be unable to determine which type instances such constraints apply to during type-checking and overload resolution. For example:

extension InlineArray where Count == 8 { ... } // ❌ error: though shall not use integer generic argument values for same-"type" constraints

Alternate Design

Treat all instances of types with a generic integer parameter as having an opaque integer value argument. All types which vary only in the specified value of an integer generic argument are considered distinct in the type-checker.
This differs from the Proposed Design above in considering types which have a different declaration/spelling of the integer generic argument value as being distinct types for the purposes of type-checking. Mangling of the type therefore depends on the content of the argument integer-valued expression.
This means the following variables have the same type according to the type-checker:

let foo : InlineArray<2, Int>
let bar : InlineArray<2, Int>

As do the following:

let foo : InlineArray<2+2, Int>
let bar : InlineArray<2+2, Int>

But the following do not:

@const let x = 2+2
let foo : InlineArray<x, Int> = [1,2,3,4] as! InlineArray<x, Int>
var bar : InlineArray<2+2, Int>
bar = foo // ❌ error: cannot assign value of type 'InlineArray<x, Int>' to type 'InlineArray<2+2, Int>'

Because the type distinction is enforced based on the declaration references and the spelling of the argument expression, API where integer-generic types are used as parameter types requires explicit type conversion annotations, for example:

@const let key_size = 4
func foo(_ input: InlineArray<key_size, Int>) { ... }
...
let input: InlineArray<key_size, Int> = [1,2,3,4] as! ...
foo(input) // ✅

let data: InlineArray<4, Int> = [1,2,3,4]
foo(data) // ❌ error: cannot assign value of type 'InlineArray<4, Int>' to type 'InlineArray<key_size, Int>'
foo([1,2,3,4]) // ❌ error: cannot assign value of type 'InlineArray<4, Int>' to type 'InlineArray<key_size, Int>'

In order to be able to use values of not-identically-defined generic integer arguments, programmers would be required to spell out the type conversion to match that of the assignee/parameter:

// Hypothetical explicit compile-time verifiable type identity specifier syntax
foo(data as! InlineArray<key_size, Int>)
foo([1,2,3,4] as! InlineArray<key_size, Int>)

Where the as! can be lowered to a compile-time post-@const-evaluation static check.

This design has the same effect on runtime type equality and same-“type” constraints and multiple-module overloads as the Proposed Design above. However, while function overloading based on the distinct specification of the integer generic argument is possible, it also allows overloading based on a different spelling of an otherwise-same runtime value:

public func foo(_ input: InlineArray<4, Int>) { ... }
public func foo(_ input: InlineArray<2, Int>) { ... } ✅
public func foo(_ input: InlineArray<2+2, Int>) { ... } ✅ // Note that this may have a different implementation from the '4' variant, despite accepting the same *runtime* type argument...

Discussion

We believe that the requirement to match the exact integer generic argument specified on every use site - variable assignment, function argument, etc, carries excessive burden on the programmer and that function overloading based on the integer generic argument does not justify it. With the proposed design, with fully-opaque (and always equal) integer generic values in the type-checker, the compiler is still able to provide the required type safety guarantees after @const value resolution post type-checking without requiring any additional explicit clarifications at the use site. Furthermore, the ability to specify functions generic over the integer values and an expectation that e.g. size-specific InlineArray values can be wrapped in a struct reduces the severity of the restriction on overloading.

12 Likes
2

I would like to suggest that the use of value types in generic signatures be handled a little differently.

Rather than having some special case for integer generic types, I think it might be nicer and cleaner if we consider the generic type signature (the stuff in <...>) to be a constructor call of the meta type.

All meta type methods and properties would need to be constrained to be @const, and all meta type declarations would need to be hashable so the compiler can compare and merge types.

Then instance properties on the meta type would be accessible as static immutable properties at runtime on instances of the type.

Consider InlineArray to be something like:

struct InlineArray {
    meta {
        let size: Int
        let type: Type

        @const
        init(_ size: Int, _ element: Element.Type) { ... }
    }
}

This would allow for custom constructors, such as a matrix constructor taking init(square: Int, _ type: Element.self), that would be used by calling InlineArray<square: 5, Float>. Since the meta type would be created at compile time and a hash evaluated, it could be compared to other invocations such as InlineArray<square: 5, InlineArray<5, Float>>.

Possibly, the meta type could also have some optional methods for the compiler—things like sizing methods or other utilities that the compiler could call if defined. I could imagine a type that wants to reserve a raw binary block of storage of X bytes; the meta type could provide this through a reservedSize(for: MemoryMode) -> UInt method, or a static method like size(of: Self.self) -> UInt

And even possible methods that the compiler can use to determine copy-on-write behavior could be added down the road to enable the creation of custom types

6 Likes
3

Does this approach rule out arithmetic generics?

Am I ever able to write func concat<D>(_ value: Int, Vector<D>) -> Vector<D + 1> in the future?

11 Likes