Swift. Generics

Maxim Krylov
6 min readAug 2, 2020

Here is a quick introduction, along with the full articles list

Generics can be used when defining a function

// Generic functionfunc swapTwoValues<T>(_ first: inout T, _ second: inout T) {
let temp = first
first = second
second = temp
}
var firstInt = 3
var secondInt = 5
swapTwoValues(&firstInt, &secondInt)
var firstString = "hello"
var secondString = "world"
swapTwoValues(&firstString, &secondString)

<T> is called a type parameter list. It can have single or multiple parameters

func someFunc<T, U, V>(_ first: T, _ second: U) -> V { ... }

Generics can also be used when defining a class, structure, or enum

// Generic custom typestruct Stack<Element> {
var items = [Element]()
mutating func push(_ item: Element) {
items.append(item)
}
mutating func pop() -> Element {
return items.removeLast()
}
}
var stringStack = Stack<String>()
stringStack.push("one")
stringStack.push("two")
var intStack = Stack<Int>()
intStack.push(1)
intStack.push(2)

When extending a generic custom type, the type parameter list should be omitted. All type parameters are taken from the initial type declaration

extension Stack {
var topItem: Element? {
return items.isEmpty ? nil : items[items.count - 1]
}
}

For specifying that a type parameter must inherit from a specific class or conform to a particular protocol, there should be used type constraints

func someFunc<T: SomeClass, U: SomeProtocol>(someT: T, someU: U) {     
...
}

Type constraints, themselves, make generic types more specific. As a result, it allows using code that requires some specific compatibilities

func findIndex<T: Equatable>(of valueToFind: T, in array: [T]) -> Int? {
for (index, value) in array.enumerated() {
// requires conformance to Equatable
if value == valueToFind {
return index
}
}
return nil
}

For defining a generic protocol, instead of a type parameter list, there should be declared associated types

// Generic protocolprotocol SomeProtocol {
associatedtype T
func someFunc(_ value: T)

associatedtype U
func anotherFunc(_ value: U)
}

When conforming to that protocols, types (structures, classes, or enums) may specify which exact type should replace a protocol associated type. To make it explicitly they use typealias

class SomeClass: SomeProtocol {
typealias T = Int
func someFunc(_ value: Int) { print(value) }

typealias U = String
func anotherFunc(_ value: String) { print(value) }
}

However, typealias can be easily omitted. And then Swift infers associated types implicitly

class SomeClass: SomeProtocol {
func someFunc(_ value: Int) { print(value) }
func anotherFunc(_ value: String) { print(value) }
}

Moreover, associated types can be replaced with generic type parameters when adopting a protocol

protocol SomeProtocol {
associatedtype U
func someFunc(_ value: U)
}
class SomeClass<T> { }extension SomeClass: SomeProtocol {
func someFunc(_ value: T) { }
}

Associated types also support constraints based on conformance to a protocol or inheritance from a class

protocol SomeProtocol {
associatedtype T: AnotherProtocol
func someFunc(_ value: T)
}

Generic Where Clause

Generic where clause allows setting requirements on generic type parameters or associated types. The requirements can be the following: types must conform to a protocol, types must inherit from a class, and types must be the same or equal to a specific type

where clause stays before the opening curly brace of a type or a function body

// "Conformance to a protocol" example
class SomeClass<T> where T: SomeProtocol { }
...// "Inheritance from a class" example
protocol SomeProtocol {
associatedtype U where U: SomeClass
}
...// "Types must be the same or equal to a specific type" example
// U is associated type
func someFunc<T1: SomeProtocol, T2: SomeProtocol>(t1: T1, t2: T2) where T1.U == T2.U, T1.U == Int { }

where clause can also be used when extending a generic custom type or a protocol. In this case, the extension is available only when the type satisfies all requirements

extension Stack where Element: Equatable {
func isTop(_ item: Element) -> Bool {
guard let topItem = items.last else {
return false
}
return item == topItem
}
}

Under the Hood

Important. Before reading the text below, take a look at Swift. Method Dispatch

There are two ways of working with generics in Swift: runtime way (boxing of generic values at runtime) and compile-time way (generic code turns into specific code for a particular type at compile-time, it is also called generic specialization)

Runtime Way

When following this way, Swift creates a single block of generic code for any type T. No matter what the initial type is, the value is passed into the generic function additionally with type metadata

func test<T>(value: T) -> T {
let copy = value
print(copy)
return copy
}
// kind of runtimelet myStruct = MyStruct()
test(value: myStruct, metadata: MyStruct.metadata)
// muStruct value is stored in value buffer

But because different types (value and reference) behave differently, Swift uses a value buffer for storing their values, and Value Witness Table for having an ability to allocate memory on the heap for them, and to copy, move, and destroy their values through a single interface

Swift builds VWT for any type at compile-time

When MyStruct is generic itself, it gets more challenging to determine the type metadata because MyStruct<Int> and MyStruct<String> are different on any level of the program. And they also have different VWTs

In this case, Swift builds a metadata pattern based on the structure metadata. Then it combines the pattern with T metadata for getting the result information about the type, and also for having correct VWT

// kind of runtimefunc test<T>(value: MyStruct<T>, tMetadata: T.Type) {
let myStructMetadata =
get_generic_metadata(MyStruct.metadataPattern, tMetadata)
}
let myStruct = MyStruct<Int>()
test(value: myStruct, tMetadata: Int.metadata)

When using constraints, Swift passes additional information about the constraint types to the function

func compareAndDraw<T>(first: T, second: T)
where T: Equatable, T: Drawable {
if first == second { // Equtable
first.draw() // Drawable
second.draw() // Drawable
}
}
compareAndDraw(first: MyStruct(), second: MyStruct())

In this case, for computing the function at runtime, there should be known pointers to == and draw() methods of MyStruct. For having those pointers, Swift passes Protocol Witness Table of Equatable and Drawable as additional parameters into the function

// kind of runtimecompareAndDraw(first: MyStruct(),
second: MyStruct(),
metadata: MyStruct.metadata,
myStructIsEquatable: Equatable.pwt,
myStructIsDrawable: Drawable.pwt)

The runtime way is less efficient than the compile-time one. Swift follows this way when it can’t determine a particular type to substitute for a generic one within the compilation process (e.g., the type is defined in another module)

Compile-time Way or Specialization

The compile-time way is a quite efficient optimization of generic code

Swift creates a separate function for each particular type during the compilation process, binding T with that type. It is called static polymorphism (or parametric polymorphism)

func isEqual<T: Equatable>(first: T, second: T) -> Bool {
return first == second
}
isEqual(first: 1, second: 2)
isEqual(first: "one", second: "one")
isEqual(first: MyStruct(), second: MyStruct)
// kind of runtimeisEqual(first: Int, second: Int) { ... }
isEqual(first: String, second: String) { ... }
isEqual(first: MyStruct, second: MyStruct) { ... }

If the compile-time way is available, using generic code, constrained by protocols, is more efficient than using the protocols directly because:

  • there are no existential containers and, as a result, no extra heap allocations (if using structures)
  • instead of having Table Dispatch any time when calling a protocol method, there can be used Direct Dispatch, because of taking a structure as a parameter type
function draw(copy: Drawable) {
copy.draw()
}
draw(copy: MyStruct()) // always Table Dispatch (PWT)// vsfunction draw<T: Drawable>(copy: T) {
copy.draw()
}
draw(copy: MyStruct()) // Direct Dispatch
// because at runtime it will be
// function draw(copy: MyStruct) { ... }

Moreover, when applying compile-time way optimizations, Swift can do inlining code to decrease the number of function calls

function draw(copy: MyStruct) {
copy.draw()
}
// before inlining code
draw(copy: MyStruct())
// after inlining code
MyStruct().draw()

Along with generic functions, compile-time way optimizations can also be applied to generic types

struct Pair {
var first: Drawable
var second: Drawable
}
Pair(first: MyStruct(), second: MyStruct())// vsstruct Pair<T: Drawable> {
var first: T
var second: T
}
Pair(first: MyStruct(), second: MyStruct()) // more efficient

Again, when using a generic type, there are no existential containers because Swift at compile-time can determine a particular type that is stored inside a generic structure instance, which is being created. And that type doesn’t change at runtime

In generic types, because MyStruct is a structure, first and second properties are stored inline on the stack, as the whole enclosing structure Pair. No heap allocations there. Static Dispatch is used when calling methods of first and second, or Pair structure itself

The compile-time way is available when Swift has a type definition during the compilation of generic code. It happens if both type definition and generic code are placed in the same file. If they are separated from each other but still placed in the same module, applying whole module optimization (is on by default since Xcode 10) enables considering the whole module as one file, and as a result, having generic specialization within the module

Resources

--

--

Maxim Krylov
Maxim Krylov

No responses yet