Swift のメソッドディスパッチを体感する

この記事は

この記事は、社内で共有した記事を Public にして供養＋アルファした内容です。

話すことは、Swiftのanyを支える Existential Container の挙動をたどってみた、的な話です。

（ただ、社内で共有したやつを雑に再編集しているだけなので、おかしいところがあったら Fix するのでお知らせください。）

Protocol と存在型

例えば、Swiftで以下のような Protocol と構造体を用意したとします

protocol SomeProtocol {
  func call()
}

struct Some1: SomeProtocol {
  var value: Int

  init(value: Int) { self.value = value}

  func call() {
    print("\(value)")
  }
}

struct Some2: SomeProtocol {
  var value1: Int
  var value2: Int

  init(value1: Int, value2: Int) { 
    self.value1 = value1
    self.value2 = value2
}

  func call() {
    print("\(value1) \(value2)")
  }
}

これらを使って以下のようなコードを書くと、もちろんコンパイルは通ります

let someValue1 = Some1(value: 0)
let someValue2: any SomeProtocol = Some1(value: 1)
let someValue3 = Some2(value1: 2, value2: 3)
let someArray: [any SomeProtocol] = [someValue1, someValue2, someValue3]

また、someArray を利用した以下のコードもコンパイルは通りますし、someArray で順番に入れたとおり Some1 と Some2 の call は呼ばれます

for some in someArray {
   some.call()
}

疑問を持ってみる

先ほどまでのコードを見ても、普通に Swift を書いている人から見ると「そりゃ通るだろ」と思うかもしれませんが、あえて疑問を持ってみましょう。あえて上げるなら以下の２つでしょうか

• それぞれの型は内容は違うはずなのに、実行時になぜ事故らない？
• それぞれの型のcallの実装、なんでちゃんと正しいのが呼ばれるの？

それぞれの型の内容は違うはずなのに、実行時になぜ事故らない？

Some1 は一つだけIntの変数が存在しますが、 Some2 は２つもあります。

また、

struct Some3: SomeProtocol {
  var string: String
  ...
  
  func call() {
    print("\(string)")
  }

と String の変数を持ったとしても、動きます。これらの違いってどんな感じに吸収されているのでしょうか？

それぞれの型のcallの実装、なんでちゃんと正しいのが呼ばれるの？

someArray はいわば SomeProtocol の情報しかありません。なのに、

// 冒頭のコードに以下を加えて実行してみる

let someValue1 = Some1(value: 0)
let someValue2: any SomeProtocol = Some1(value: 1)
let someValue3 = Some2(value1: 2, value2: 3)
let someArray: [any SomeProtocol] = [someValue1, someValue2, someValue3]

for some in someArray {
   some.call()
}

// 実行結果:
// 0
// 1
// 2 3

どうやって Some1 と Some2、 Some3 の実装を呼べているのでしょうか？

Existential Container

これらは、 Existential Container という技術で実現されています。Existential は、このあと話す　Existential Type(存在型) という単語から来ています。順に見ていきましょう

Existential Type（存在型）

var value: any SomeProtocol

この、some の値の型が Existential Type（存在型）と呼ばれるものです

注意: SomeProtocol が Existential Type ではない。あくまで value の型が Existential Type

公式のドキュメントには、こんな感じのことが書いてありますが、私達が把握している動作とそう違いは有りません。

In Swift, we consider protocols to be types. A value of protocol type has an existential type, meaning that we don't know the concrete type until run-time (and even then it varies), but we know that the type conforms to the given protocol.

Swift　では、私達はプロトコルを型として考慮している。プロトコルの型の値は存在型を持つ。つまりは、私達は具体的な型は実行時までわからない（し、変化し続ける）が、その指定したプロトコルに準拠してあることはわかる

引用元: https://github.com/apple/swift/blob/main/docs/Generics.rst#subtype-polymorphism

Existential Container

簡単に言えば、この Existential Type を実装するための技術です。

具体的な Existential Container の利用例

以下のコードでは、どのように Existential Container が使われているのか覗いてみましょう

let some: any SomeProtocol = Some1(...)

Existential Container を考慮して、実行時に実際に動作するコードを（普段書く Swift のコードから隠れているものも含めて）展開するとこうなります。

// EConteiner はとりあえず Existential Container を表現するために用意した型。実際には存在しない
let some: EConteiner = EConteiner()
let someValue = Some1(...)
some.buffer[0] = someValue.value
some.metadata.vwt = someValue.vwt
some.witnessTables = someValue.witnessTables

具体的にそれぞれどういう意味なのかは、あとの方で話すのでとりあえず「ざっとこんなもんか」と覚えててください

Existential Container のサイズと、別の変数のサイズの違い

ちなみに、存在型で宣言された変数と別の変数、別のプロトコルによる存在型の変数のサイズは、MemoryLayout.size で調べるとこのようになります

protocol SomeProtocol {
  func call()
}

protocol SomeProtocol2 {
  func call1() 
  func call2()
}

struct Some1: SomeProtocol {
  var value = 1000
  func call() { }
}

struct Some2: SomeProtocol2 {
  func call1() { }
  func call2() { }
}

// Existential Type の変数
let some1: any SomeProtocol = Some1()
print(MemoryLayout.size(ofValue: some1)) // 40 byte (Buffer[3] + Metadata + Witness Table)

// そうじゃない型の変数
let some1NonExistensial = Some1()
print(MemoryLayout.size(ofValue: some1NonExistensial)) // 8 byte (Int64)

// ↑とは別の Existential Type の変数
let some2: any SomeProtocol2 = Some2()
print(MemoryLayout.size(ofValue: some2)) // 40 byte (Buffer[3] + Metadata + Witness Table)

存在型のほうが若干サイズは大きく、かつ互いに違う存在型どうしの変数のサイズは一緒です。なぜかというと、Existential Type は違えど、Existential Container のメモリ上のレイアウトや仕組みが同じだからです。

Existential Container の構造

では、EConteiner はどうなっているのでしょうか

struct EConteiner {
   var buffer: [Any] // すでに 3ワード分値が入るように容量が取られている. あと `Any` は正しくないけど便宜上そう書く、正確には C++ における void* 
   // 実際は void* という `Any` とはまた別物だけど ”何でも入る” という雰囲気でみていただけると
   // void* - 型を考慮せずにアドレスだけをぶっこめるC++の型
   var metadata Metadata // 型のメタデータのレコード。どの型にもある
   var witnessTables: [WitnessTable] // WitnessTable の情報
}

Existential Container の buffer

型の変数の値を格納します (Some1 だったら value、Some2 だったら x y)

var buffer: [Any] // すでに 3ワード分値が入るように容量が取られている. あと `Any` は正しくないけど便宜上そう書く、正確には C++ における void* 

※ ワード とはCPUの処理をするデータの単位のこと（レジスタの長さ）を指します。たとえば　64bit CPUは １ワード　= 64bit

ref: https://www.amazon.co.jp/dp/477419607X （だったと思う。それか NAND2Tetris の書籍）

Existential Container の buffer

「んじゃあ x, y, z, w とかやったらInt(64)x4 で ３ワード超えるじゃん」、と思うかもしれません。実は、その時はその分確保できる別のヒープ領域を作ってぶち込み、 buffer[0] にそのヒープ領域の先頭のアドレスを書きます。そして、必要に応じてそのヒープ領域にアクセスします。

しかし、「これだけだと、実行時にどういうふうにヒープ領域にアクセスすればいいかわからんのでは？ 」となるでしょう。これは、この後話す Value Witness Table が解決します。

Existential Container の MetaData

MetaDataは、その型の情報のレコードを指します。たとえば、型の種類とか（enum or class or struct）です。ここに実は、Value Witness Table とよばれる、大事なレコードがあります

ref: https://github.com/apple/swift/blob/main/docs/ABI/TypeMetadata.rst

Value Witness Table

その型を アロケーション・コピーやデストラクトする際の関数のポインタを格納しています。アラインメントやストライドといった、型の構造に必要な情報もつまっています。ちゃんとしたタイミングでそれらが呼ばれます。

※ ここらへんのアラインメントやストライドなどの単語とか、さっきのワードとかそういうの気になるなら一度 https://www.amazon.co.jp/dp/477419607X を読むと手っ取り早いです

語弊を生みそうなので言っておくと、　Existential Container だけが持っているわけじゃない。すべての型が持っています。

Existential Container の witnessTable

Protocol Witness Table と呼ばれる、Dynamic Mehtod Dispatch で見られる関数テーブルです。コンパイル時に Protocol の準拠に合わせて生成されます。

このコードで考えてみましょう

protocol SomeProtocol {
  func call()
}

struct Some1: SomeProtocol {
  func call() { }
}

struct Some2: SomeProtocol {
  func call() { }
}

コンパイル時に生成される Witness Table を覗いてみます。Swiftの中観言語である Swift Intermediate Language (SIL) のコードを覗いてみましょう

$ swiftc some.swift -emit-sil -o some.sil

抜粋したものが ↓ です

sil_witness_table hidden Some1: SomeProtocol module some {
  method #SomeProtocol.call: <Self where Self : SomeProtocol> (Self) -> () -> () : @$s4some5Some1VAA12SomeProtocolA2aDP4callyyFTW	// protocol witness for SomeProtocol.call() in conformance Some1
}

sil_witness_table hidden Some2: SomeProtocol module some {
  method #SomeProtocol.call: <Self where Self : SomeProtocol> (Self) -> () -> () : @$s4some5Some2VAA12SomeProtocolA2aDP4callyyFTW	// protocol witness for SomeProtocol.call() in conformance Some2
}

仮想関数テーブルとの違い

ちなみにクラスなどで使われている「仮想関数テーブル」との違いを言語化してみましょう。

• 仮想テーブル

  • クラスにテーブルポインタが貼られてる
  • なのでメソッドを探すときは、クラス経由で見に行く

• Witness テーブル

  • コンテナごとにポインタが貼られる
  • なのでメソッドを探すときは、コンテナ経由で見に行く

ref: https://www.amazon.co.jp/dp/4797376686

sil_witness_table の内容を解説

• hidden はアクセス修飾子で元のコードに public をつけると消えます

Method entries map a method requirement of the protocol to a SIL function that implements that method for the witness type. One method entry must exist for every required method of the witnessed protocol.

• protocol の実装要求に対して、その型の実装している関数への参照です
  • つまりは、Existential Container が特定のメソッドをコールする際に、Container にあるpwtを参照します

ref: https://github.com/apple/swift/blob/main/docs/SIL.rst#witness-tables

関数コール

存在型への関数コールについては、SILの段階で特別なコールになります

まずは普通の関数コールについて見てみましょう (Static Method Dispatch)

func hello() {}
hello()

静的に関数への参照をとって、それをコール(apply)しています (Static Dispatch)

%2 = function_ref @$s4some5helloyyF : $@convention(thin) () -> () // user: %3
%3 = apply %2() : $@convention(thin) () -> ()

では、これはどうでしょう？

protocol SomeProtocol {
  func call()
}

struct Some1: SomeProtocol {
  func call() { }
}

let some: any SomeProtocol = Some1()
some.call()

SILにすれば実態がわかります

%9 = open_existential_addr immutable_access %3 : ..
%10 = witness_method $@opened("...") SomeProtocol, #SomeProtocol.call ... // 長過ぎるので省略しているが引数として %9 を渡している
%11 = apply %10<@opened("...") SomeProtocol>(%9) : $@convention(witness_method: SomeProtocol)

くっそ複雑にみえるけど一つづつ理解すれば簡単です

open_existential_addr

• open_existential_addr は名前の通り、第1引数のオブジェクトの Existential Container を開いています

%9 = open_existential_addr immutable_access %3 : ..

ref: https://github.com/apple/swift/blob/main/docs/SIL.rst#open-existential-addr

• witness_method Protocol Witness Table から読むべき関数への参照を引っ張っている

witness_method

%10 = witness_method $@opened("...") SomeProtocol, #SomeProtocol.call ... // 長過ぎるので省略しているが引数として %9 を渡しています

• その取ってきた参照で関数をコールしています

%11 = apply %10<@opened("...") SomeProtocol>(%9) : $@convention(witness_method: SomeProtocol)

• ちなみに存在型じゃなかったら Static Dispatch してコールされます
• 値型・finalな型・関数・extensionの　関数は　Static Dispatch　と決まっています
  • なので Class だったら普通に　Static Dispatch。そんときは class_method 命令でコールをします

struct Some1: SomeProtocol {
  func call() { }
}

let some = Some1()
some.call()

%9 = function_ref @$s4some5Some1V4callyyF : $@convention(method) (Some1) -> () // user: %10
%10 = apply %9(%8) : $@convention(method) (Some1) -> ()

本当に witness は Dynamic Method Dispatch?

witness_method の命令には具体的な関数のシグネチャが出ていないので、その時点ではどの関数が呼ばれるかはわからないということになります。ちなみに Static Methodo Dispatch として紹介した方はシグネチャが出ています。

ここまで学んだことから人力 Dynamic Method Dispatch してみよう

このコードでやってみましょう

struct Some1: SomeProtocol {
  var value: Int = 100
  func call() { }
}

let some: SomeProtocol = Some1()
some.call()

まずはコンパイルする時

まず、Witness Table をつくります

struct Some1: SomeProtocol {
  var value: Int = 100
  func call() { }
}

/*
Value Witness Table@1
- Some1.allocate()
- Some1.deallocate()
...
*/
/*
Protocol Witness Table@1
- Some1.call: SomeProtocol conformance
*/

let some: SomeProtocol = Some1()
some.call()

実行時 その１

Existential Container を作ります

struct Some1: SomeProtocol {
  var value: Int = 100
  func call() { }
}
/*
Value Witness Table@1
- Some1.allocate()
- Some1.deallocate()
...
*/
/*
Protocol Witness Table@1
- Some1.call: SomeProtocol conformance
*/

let some: any SomeProtocol = Some1()
/*
let some = ExistensialContainer()
some.buffer[0] = some.value
some.vwt = Value Witness Table@1
some.metadata.pwt = Protocol Witness Table@1
*/
some.call()

実行時 その2

レシーバのコンテナの情報を元に、関数への参照を protocol witness table から引っ張ってきて、それをコールします

let some: any SomeProtocol = Some1()
/*
let some = ExistensialContainer()
some.buffer[0] = some.value
some.vwt = Value Witness Table@1
some.metadata.pwt = Protocol Witness Table@1
*/
some.call()
/*
Container "some" にある protocol witness table が参照している関数の実装への参照を取ってくる
*/

おわり

罠

実は罠もあります。以下のコードは何が表示されるでしょう？

protocol Animal {
}

extension Animal {
  func speak() {
    print("あにまー！")
  }
}


struct Cat: Animal {
  func speak() {
    print("ねこー！")
  }
}

let cat: any Animal = Cat()
cat.speak()

実は Static Method Dispatch

「「「あにまー！」」」

• extension は Static Method　Dispatch なのでこうなる。
• 解決方法は、Animal　の本定義の方に speak() を書いて witness table を生成させる、という感じです

SILでのコールを見てみる

• たしかに Static Method　Dispatch してます

%9 = open_existential_addr immutable_access %3 : $*Animal ...
// function_ref Animal.speak()
%10 = function_ref @$s4some6AnimalPAAE5speakyyF : ...
%11 = apply %10<@opened("D986EF36-B10C-11EC-AE1D-ACDE48001122") Animal>

まとめ

• Method Dispatch は奥が深い

参考文献

• https://developer.apple.com/videos/play/wwdc2016/416/
  • わかりやすけど Metadata 周りの話が一切ないのが罠。多分昔と今で違う可能性がある
• https://github.com/apple/swift/blob/main/docs/ABI/TypeMetadata.rst
  • Metadata 周りを知りたいならまずこれ
• https://github.com/apple/swift/blob/main/docs/SIL.rst
  • SIL のバイブルだけど、BNF で書かれた文法規則が古い・間違っていることが多い。
    • Contribute チャンス (1回できた)
• https://github.com/apple/swift/blob/main/docs/ABI/TypeLayout.rst
  • 型のメモリレイアウト について詳しく書いてあるが TODO が長年放置されている気がする
• https://speakerdeck.com/kateinoigakukun/konpairakaraniu-jie-kuswift-method-dispatch-1
  • unsafeBitCast をした場合とか最適化をした場合について詳しく書いてある
• https://www.amazon.co.jp/dp/4797376686
  • 仮想テーブルの解説がわかりやすい。あと仮想テーブルの考え方を元にしたジェネリクスのテクニックが面白い
    • だいぶ忘れたのでまた読みたい