SwiftのGenericsとProtocolの実装

SwiftのGenericsとProtocolの実装について簡潔に解説する。

```
Apple Swift version 4.2.1 (swiftlang-1000.11.42 clang-1000.11.45.1)
Target: x86_64-apple-darwin18.2.0
```

# ジェネリックな型の実行時表現

下記の`take`関数の`X`型のように、ジェネリックな型があるとする。

```swift
func take<X>(_ x: X) { ... }
```

Swiftは静的な型システムを持っているが、ジェネリクスにおいてはどのような型が渡されても動作できなければならないので、コンパイラは型について抽象化されたコードを生成する。この抽象化はコンパイルステージにおいてLLVM-IRを生成する段階で実現されるため、LLVM-IRを観察する事で確認できる。

## ジェネリクスを実現する生成コードの観察

上記の`take`関数であれば、下記のようなLLVM-IR関数が生成される。

```llvm
define hidden swiftcc void @"$S1a4takeyyxlF"(
    %swift.opaque* noalias nocapture, 
    %swift.type* %X) #0
```

`X`型の引数`x`は、`%swift.opaque*`という型になっている。これはopaque pointerと言って、要するに参照先の型が不明なポインタの事である。加えて、`%swift.type*`型の引数`%X`が渡されている。`%swift.type`はMetatypeという型を現す型の事だ。この関数が使用されるときには、引数はどんな型であってもそのポインタに変換される。そして、コンパイル時に解決された型パラメータの型のMetatypeが渡される。

## Metatypeの説明

MetatypeはSwift言語においても直接取り扱う事ができるオブジェクトで、下記のように型名や`type(of:)`関数によって取得できる。

```swift
let intType: Int.Type = Int.self
let a: Int = 1
let aType: Any.Type = type(of: a)
```

また、staticメソッドなどはMetatypeに対するメソッドとして扱われている。

```swift
print(Int.bitWidth) // 64
```

## シグネチャと生成コードの対応

ジェネリックな型を持つ引数がopaque pointerにコンパイルされることと、ジェネリックな型についてのMetatypeが渡されることは独立している。例えば、ジェネリックパラメータの数は変わらないまま、同じジェネリック型を持つ引数が増えた場合、opaque pointerは引数の数だけ渡されるが、Metatypeの数は変化しない。以下に例を示す。

```swift
func take<X>(_ x1: X, _ x2: X)
```

```llvm
define hidden swiftcc void @"$S1a4takeyyx_xtlF"(
    %swift.opaque* noalias nocapture, 
    %swift.opaque* noalias nocapture, 
    %swift.type* %X) #0
```

また、引数の表現を生成する処理と、ジェネリックシグネチャについての引数を追加する処理は独立している。例えば、ジェネリックではない引数が追加された場合、その引数を生成した後、ジェネリックパラメータについてのMetatypeの引数が末尾に生成される。以下に例を示す。

```swift
func take<X>(_ x1: X, _ x2: Int)
```

```llvm
define hidden swiftcc void @"$S1a4takeyyx_SitlF"(
    %swift.opaque* noalias nocapture, 
    i64, 
    %swift.type* %X) #0
```

## ジェネリックな型に対する操作

ジェネリックな型の値に対しては、それの実行時の真の型に関わらず、コピーや破棄を行う事ができる。下記のコードでは、`x`を`a`にコピーする処理や、関数脱出時に`a`を破棄する処理が行われる。

```swift
func take<X>(_ x: X) {
    let a = x
}
```

このような、ジェネリックな型に対する処理は、真の型によってするべき処理が異なる。参照型の場合は、参照先のオブジェクトの参照カウンタを操作せねばならない。値型の場合は、そのサイズが型により異なるし、保持しているプロパティに対しても処理をしなければならない。例えば、値型がプロパティとして参照型を持っている場合、その値型がコピーされるときには、その参照型の参照先のオブジェクトの参照カウンタを増加させねばならない。

## Value Witness Table

こうした処理内容は型によって異なるため、その処理を行う関数がMetatypeから取り出せるようになっている。具体的には、そうした操作をまとめたValue Witness Tableというテーブルがあり、Metatypeからその型を操作するためのValue Witness Tableが取り出せるようになっている。

# プロトコルの実行時表現

Swiftではある型の特性を宣言するための言語機能としてprotocolがある。基本的な用途として、メソッドを所持している事を現す事ができる。以下に例を示す。

```swift
protocol P {
    func proc1()
    func proc2()
}
```

これをジェネリクスと合わせて使う事により、ジェネリックな型に対して、その型があるプロトコルに準拠する事を制約できる。


```swift
func take<X>(_ x: X) where X : P
```

## プロトコル制約を実現する生成コードの観察

上記の関数をコンパイルして生成されるLLVM-IR関数は下記のようになる。

```llvm
define hidden swiftcc void @"$S1a4takeyyxAA1PRzlF"(
    %swift.opaque* noalias nocapture, 
    %swift.type* %X, 
    i8** %X.P) #0
```

ただのジェネリックパラメータだった場合と比べて、`i8**`型の引数`%X.P`が追加されている。これは`X`型についての実行時の情報を表現するために追加された引数である。

## シグネチャと生成コードの対応

準拠するプロトコルが増えたり、ジェネリックパラメータが増えた場合の例を示す。

```swift
func take<X, Y>(_ x: X, _ y: Y) where
    X : P,
    X : Q,
    Y : P
```

このように、XはPに加えてQにも準拠させ、さらにPだけに準拠するYを追加したとする。すると、LLVM-IR関数は下記のようになる。

```llvm
define hidden swiftcc void @"$S1a4takeyyx_q_tAA1PRzAA1QRzAaCR_r0_lF"(
    %swift.opaque* noalias nocapture, 
    %swift.opaque* noalias nocapture, 
    %swift.type* %X, 
    %swift.type* %Y, 
    i8** %X.P, 
    i8** %X.Q, 
    i8** %Y.P) #0
```

まず、引数2つに対応するopaque pointerが2つ生成され、次に、XとYの実行時の型のMetatypeが生成され、最後に、それらのプロトコル準拠に対応する値が生成される。

## Protocol Witness Table

ジェネリックパラメータがプロトコルに準拠する事に対応して渡されている`%X.P`などの引数は、Protocol Witness Tableを示すポインタである。Protocol Witness Tableとは、あるジェネリック型の値が、そのプロトコルとして振る舞うときに必要な操作をまとめた関数テーブルである。

# 更に詳しく

より詳細に解説した際の発表資料

SwiftのGenericsとProtocolの実装
https://speakerdeck.com/omochi/swiftfalsegenericstoprotocolfalseshi-zhuang

AppleのSwift開発者が解説している動画

2017 LLVM Developers’ Meeting: “Implementing Swift Generics ”
https://www.youtube.com/watch?v=ctS8FzqcRug