Swiftのオーバーロード選択のスコア規則

Swiftは関数やメソッドをオーバーロードすることができます。例えば下記のようなコードを書けます。

```swift
func f(_ a: Int) {}

func f(_ a: Int?) {}
```

この時、`f(3)`という呼び出しは、2つある`f`のうち、1つ目の定義の方の呼び出しになる事はよく知られています。

では、下記のコードではどうなるでしょうか。

```swift
func f(_ a: Int?) {}

func f(_ a: Any) {}
```

この場合に`f(3)`がどちらの呼び出しになるかはよくわからない人が多いと思います。

この記事では、Swiftがこういったケースでどのようにオーバーロードを選択するのか説明します。

# 推論解のスコア

Swiftコンパイラのアーキテクチャでは、オーバーロードの解決は、型推論器の役割になります。型推論器がオーバーロードごとの仮の解を複数発見した後、その複数の解に対して優先度付けをして、最も良いものを決定します。その優先度付けには複数の仕組みが組み込まれているのですが、ここではスコアについて説明します。

Swiftコンパイラには、複数の種類のスコアがあり、種類ごとに点数を計上します。種類ごとに高さが決められており、高い種類のスコアの点数から順に比較していきます。直感的には、そのまま数字を繋げて十進数だと思って読めば良いです(ある種類の点数が9以下である限り)。このスコアの比較の様子をコンパイラにオプションを与えることで観察することができます。

下記のコードをコンパイラに与えてみます。

```swift
// code01.swift

func f(_ a: Int?) { print("Optional") }

func f(_ a: Any) { print("Any") }

f(3)
```

コマンドは下記のようにします。

```
$ swiftc -dump-ast -Xfrontend -debug-constraints code01.swift 
```

すると、250行ほどの出力が得られるのですが、抜粋すると下記のような部分があります。

```
---Initial constraints for the given expression---
(call_expr type='()' location=code01.swift:5:1 range=[code01.swift:5:1 - line:5:4] arg_labels=_:
  (overloaded_decl_ref_expr type='$T0' location=code01.swift:5:1 range=[code01.swift:5:1 - line:5:1] name=f number_of_decls=2 function_ref=single decls=[
    code01.(file).f@code01.swift:1:6,
    code01.(file).f@code01.swift:3:6])
  (paren_expr type='($T1)' location=code01.swift:5:3 range=[code01.swift:5:2 - line:5:4]
    (integer_literal_expr type='$T1' location=code01.swift:5:3 range=[code01.swift:5:3 - line:5:3] value=3 builtin_initializer=**NULL** initializer=**NULL**)))
```

これは、ASTで表されたこの式の部分を解析する事を示す出力です。`call_expr`が関数呼び出しで、`overloaded_decl_ref_expr`はオーバーロードされた関数の参照です。その中に`name=f`と書いてあるので、これがオーバーロードされた`f`を呼び出している箇所であるとわかります。また、行番号5の部分を見てもわかります。

ここで`overloaded_decl_ref_expr`の中に`type='$T0'`と書かれているところも重要です。これは型変数というもので、型推論器にとって未確定の型を示します。型推論器はこの型変数に割り当てる型を推論します。これは関数の型を示しているので、この型変数に割り当てられる型を確認する事で、オーバーロードされた関数がいずれに決定したのかが後にわかります。

さて、その下に下記のような出力があります。

```
  $T1 literal conforms to ExpressibleByIntegerLiteral [[locator@0x7fade80c2598 [IntegerLiteral@code01.swift:5:3]]];
  ($T1) -> $T2 applicable fn $T0 [[locator@0x7fade80c26d8 [Call@code01.swift:5:1 -> apply function]]];
  ($T1 fully_bound literal=3 involves_type_vars bindings={(subtypes of) (default from ExpressibleByIntegerLiteral) Int})
  (attempting disjunction choice $T0 bound to decl code01.(file).f@code01.swift:1:6 : (Int?) -> () at code01.swift:1:6 [[locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1]]];
    (overload set choice binding $T0 := (Int?) -> ())
    ($T1 bindings={(subtypes of) Int})
    Initial bindings: $T1 := Int
    (attempting type variable $T1 := Int
      (increasing score due to value to optional)
      (found solution 0 0 0 0 0 0 0 0 1 0 0 0)
    )
  )
  (attempting disjunction choice $T0 bound to decl code01.(file).f@code01.swift:3:6 : (Any) -> () at code01.swift:3:6 [[locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1]]];
    (overload set choice binding $T0 := (Any) -> ())
    ($T1 literal=3 bindings={(subtypes of) Any; (subtypes of) (default from ExpressibleByIntegerLiteral) Int})
    Initial bindings: $T1 := Any, $T1 := Int
    (attempting type variable $T1 := Any
      (increasing score due to non-default literal)
      (solution is worse than the best solution)
    )
    (attempting type variable $T1 := Int
      (increasing score due to empty-existential conversion)
      (found solution 0 0 0 0 0 0 0 0 0 1 0 0)
    )
  )
```

この中に、`found solution`と書かれた行が2つあります。これは型推論器が解の選択過程において2つの解を発見した事を現しています。そして、その中に`0`と`1`の並びがありますが、これがスコアです。

スコアは整数の並びになっており、左の桁ほど高く、同じ桁同士では値が大きいほど高いです。最終的に、スコアが最も低い解が選択されます。低いほど選択されやすいので、スコアというよりコストと考えたほうが直感的にわかりやすいかもしれません。(スコアというのはコンパイラ内部でこの概念に与えられている名称です)

さらに続きを見ると下記の出力があります。

```
--- Solution #0 ---
Fixed score: 0 0 0 0 0 0 0 0 1 0 0 0
Type variables:
  $T1 as Int @ locator@0x7fade80c2598 [IntegerLiteral@code01.swift:5:3]
  $T0 as (Int?) -> () @ locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1]
  $T2 as () @ locator@0x7fade80c2658 [Call@code01.swift:5:1 -> function result]

Overload choices:
  locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1] with code01.(file).f@code01.swift:1:6 as f: (Int?) -> ()


Constraint restrictions:
  Int to Optional<Int> is [value-to-optional]

Disjunction choices:
```

これは2つある解のうち、解0番の中身を現しています。ポイントは、型変数`$T0`に`(Int?) -> ()`が割り当てられていることです。これは引数の型が`Int?`である方の`f`を選択する事を示しています。
そしてスコアは`0 0 0 0 0 0 0 0 1 0 0 0`です。右から4番目の桁が1になっています。

桁に対応する定義は[ソースコードのこちら](https://github.com/apple/swift/blob/1be86adbfc8f9c178e3bbfdc66340f7aa526a40b/lib/Sema/ConstraintSystem.h#L632)を見るとわかります。それによると、4番目は`SK_ValueToOptional`であり、これは型`T`を型`T?`に変換する時に加算されるスコアです。

さらに続きをみると下記の出力があります。

```
--- Solution #1 ---
Fixed score: 0 0 0 0 0 0 0 0 0 1 0 0
Type variables:
  $T1 as Int @ locator@0x7fade80c2598 [IntegerLiteral@code01.swift:5:3]
  $T0 as (Any) -> () @ locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1]
  $T2 as () @ locator@0x7fade80c2658 [Call@code01.swift:5:1 -> function result]

Overload choices:
  locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1] with code01.(file).f@code01.swift:3:6 as f: (Any) -> ()


Constraint restrictions:
  Int to Any is [existential]
```

こちらは2つ目の解である解1番の詳細です。先と同様に`$T0`の割当を見ると`(Any) -> ()`になっているので、これは`Any`を受けるオーバーロードの選択であるとわかります。そして、スコアは`0 0 0 0 0 0 0 0 0 1 0 0`です。

こちらは右から3番目が1になっています。3番目は`SK_EmptyExistentialConversion`で、`Any`への変換があると加算されるスコアです。

続きには下記の出力があります。

```
---Solution---
Fixed score: 0 0 0 0 0 0 0 0 0 1 0 0
Type variables:
  $T1 as Int @ locator@0x7fade80c2598 [IntegerLiteral@code01.swift:5:3]
  $T0 as (Any) -> () @ locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1]
  $T2 as () @ locator@0x7fade80c2658 [Call@code01.swift:5:1 -> function result]

Overload choices:
  locator@0x7fade80c2400 [OverloadedDeclRef@code01.swift:5:1] with code01.(file).f@code01.swift:3:6 as f: (Any) -> ()


Constraint restrictions:
  Int to Any is [existential]

Disjunction choices:
```

ここは採用された解が出ている部分で、`(Any) -> ()`のオーバーロードが選ばれた事がわかります。

続きには下記のように、解となる型が割り当てられたASTの出力もあります。

```
---Type-checked expression---
(call_expr type='()' location=code01.swift:5:1 range=[code01.swift:5:1 - line:5:4] arg_labels=_:
  (declref_expr type='(Any) -> ()' location=code01.swift:5:1 range=[code01.swift:5:1 - line:5:1] decl=code01.(file).f@code01.swift:3:6 function_ref=single)
  (paren_expr type='(Any)' location=code01.swift:5:3 range=[code01.swift:5:2 - line:5:4]
    (erasure_expr implicit type='Any' location=code01.swift:5:3 range=[code01.swift:5:3 - line:5:3]
      (integer_literal_expr type='Int' location=code01.swift:5:3 range=[code01.swift:5:3 - line:5:3] value=3 builtin_initializer=Swift.(file).Int.init(_builtinIntegerLiteral:) initializer=**NULL**))))
```

`overloaded_decl_ref_expr`が`declref_expr`に変更され、`type='(Any) -> ()'`になっていることから、`Any`を受けるオーバーロードが選ばれたことがわかります。

この2つの比較の場合は、左の桁のほうが影響が大きいので、4桁目が`1`になっている`Int?`の方がスコアが高く、スコアが低い`Any`の方が選択されます。

# スコアの例

その他のスコアとして、6桁目に`SK_NonDefaultLiteral`があります。これはリテラルがデフォルト型にならない場合に加算されるスコアです。

Swiftのリテラルは、リテラルの種類に応じて、割り当てることができる型が決まっているのですが、その中でも特別にデフォルトの型が決まっています。例えば、`1`のような整数リテラルの場合は`Int`、`1.0`のような小数リテラルの場合は`Double`です。

例えば下記のコードを考えてみましょう。

```swift
// SK_EmptyExistentialConversion
func f(_ a: Any) { print("Any") }

// SK_ValueToOptional
func f(_ a: Int?) { print("Optional") }

// SK_NonDefaultLiteral
func f(_ a: Float) { print("Float") }

f(3)
```

コメントでそれぞれの呼び出しで加算されるスコアを書いてあります。それぞれ3, 4, 6桁目なので、下のものほどスコアが高く、選ばれにくいです。

実際に実行してみると、`Any`と出力されます。

そして、1つ目の`f`をコメントアウトすると、`Optional`と出力され、2つ目の`f`もコメントアウトして初めて`Float`と出力されます。

呼び出しの行を`f(3.0)`に変更した場合も、`Float`は小数リテラルのデフォルト型ではないので、`Any`の方が優先されます。

もしかしたら「`Any`の吸い込みは強い」といったような経験的な感覚を持っている方もいるかもしれませんが、この結果を意外に感じる方が多いのではないでしょうか。

Swiftコードを書いていて、オーバーロードの選択優先度が重要になる場面に出会ったら、正確な振る舞いを理解する上でこの記事を参考にしてもらえると幸いです。