omochi/overload-score.md

## overload-score.md

      
    Raw
  

              overload-score.md
            
          
    slidenumber: true
autoscale: true
Swiftのオーバーロード選択のスコア規則12種類

@omochimetaru

わいわいswiftc #16


オーバーロードと型推論


Swiftにはオーバーロードがあるので、コンパイラは、ある関数呼び出しがどの関数定義に対応するか推論する。


どの関数を選ぶかは型推論と相互に関係するため、オーバーロード選択は型推論機構に統合されている。

func f(_ a: Int) -> Int { return a }

func f(_ a: Float) -> Float { return a }

func main() {
    let a = f(Int(0))
    
    let b: Float = f(0)
}


型推論器は、オーバーロードなどが絡んだ場合に、複数の有効な解を発見することがある。

func f(_ a: Int) -> Int { return a }

func f(_ a: Int?) -> Int? { return a }

func main() {
    let a = f(Int(0))
}


複数の有効な解がある場合、優先度規則により最優先解を決定する。


その優先度規則において、最初に適用される最も基本となる規則として、スコア規則がある。


スコア規則


1つの推論解に対してスコアを計算する。


スコアは12個の整数の組。


より左の桁ほど支配的。


値が低いほど解としての優先度が高い。ペナルティやコストと捉えられる。


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

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

f(3) // => Any

$ swiftc -dump-ast -Xfrontend -debug-constraints c1.swift 

--- Solution #0 ---
Fixed score: 0 0 0 0 0 0 0 0 1 0 0 0
Type variables:
  $T2 as () @ locator@0x7f9ce18abc58 [Call@c1.swift:5:1 -> function result]
  $T1 as Int @ locator@0x7f9ce18abb98 [IntegerLiteral@c1.swift:5:3]
  $T0 as (Int?) -> () @ locator@0x7f9ce18aba00 [OverloadedDeclRef@c1.swift:5:1]

--- Solution #1 ---
Fixed score: 0 0 0 0 0 0 0 0 0 1 0 0
Type variables:
  $T2 as () @ locator@0x7f9ce18abc58 [Call@c1.swift:5:1 -> function result]
  $T1 as Int @ locator@0x7f9ce18abb98 [IntegerLiteral@c1.swift:5:3]
  $T0 as (Any) -> () @ locator@0x7f9ce18aba00 [OverloadedDeclRef@c1.swift:5:1]


12種類のスコア値


12桁の値それぞれは、推論解に含まれる暗黙変換の回数などに対応している。


以降では、12種類すべての定義を見ていく。


ヘッダー定義¹

/// Describes an aspect of a solution that affects its overall score, i.e., a
/// user-defined conversions.
enum ScoreKind {
  // These values are used as indices into a Score value.

  /// A fix needs to be applied to the source.
  SK_Fix,
  /// A reference to an @unavailable declaration.
  SK_Unavailable,
  /// A use of a disfavored overload.
  SK_DisfavoredOverload,
  /// An implicit force of an implicitly unwrapped optional value.
  SK_ForceUnchecked,
  /// A user-defined conversion.
  SK_UserConversion,
  /// A non-trivial function conversion.
  SK_FunctionConversion,
  /// A literal expression bound to a non-default literal type.
  SK_NonDefaultLiteral,
  /// An implicit upcast conversion between collection types.
  SK_CollectionUpcastConversion,
  /// A value-to-optional conversion.
  SK_ValueToOptional,
  /// A conversion to an empty existential type ('Any' or '{}').
  SK_EmptyExistentialConversion,
  /// A key path application subscript.
  SK_KeyPathSubscript,
  /// A conversion from a string, array, or inout to a pointer.
  SK_ValueToPointerConversion,

  SK_LastScoreKind = SK_ValueToPointerConversion,
};


SK_Fixが最も高コスト、SK_ValueToPointerConversionが最も低コスト。


以下便宜上、最も低コストなSK_ValueToPointerConversionをランク1とする。


ランク1 SK_ValueToPointerConversion


String, Array, inoutからポインタへの暗黙変換コスト

func f(_ a: UnsafePointer<Int>) { print("Pointer") }

func f(_ a: [Int]) { print("Array") }

let a: [Int] = [1, 2, 3]

f(a) // => Array

  (attempting disjunction choice $T0 bound to decl c2.(file).f@c2.swift:1:6 : 
  (UnsafePointer<Int>) -> () at c2.swift:1:6 [[locator@0x7f9daa815400 [OverloadedDeclRef@c2.swift:7:1]]];
    (overload set choice binding $T0 := (UnsafePointer<Int>) -> ())
    (increasing score due to value-to-pointer conversion)
    (found solution 0 0 0 0 0 0 0 0 0 0 0 1)
  )


ランク2 SK_KeyPathSubscript


[keyPath: keyPath] の呼び出し

struct Cat {
    var name: String = "tama"
}

var a = Cat()
let name = a[keyPath: \.name]
print(name) // => tama
  ($T1 bindings={(supertypes of) Cat})
  Initial bindings: $T1 := Cat
  (attempting type variable $T1 := Cat
    (overload set choice binding $T2 := @lvalue String)
    ($T7 bindings={(supertypes of) WritableKeyPath<Cat, String>})
    Initial bindings: $T7 := WritableKeyPath<Cat, String>
    (attempting type variable $T7 := WritableKeyPath<Cat, String>
      (found solution 0 0 0 0 0 0 0 0 0 0 1 0)
    )
  )


struct Cat {
    var name: String = "tama"
    
    subscript(keyPath keyPath: KeyPath<Cat, String>) -> String {
        return "mike"
    }
}

var a = Cat()
let name = a[keyPath: \.name]
print(name) // => mike

ランク3 SK_EmptyExistentialConversion


Anyへの変換

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

func f(_ a: UnsafePointer<Int>) { print("Pointer") }

let a: [Int] = [1, 2, 3]

f(a) // => Pointer

ランク4 SK_ValueToOptional


Optionalへの変換

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

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

let a: Int = 1

f(a) // => Any

ランク5 SK_CollectionUpcastConversion


Array, Dictionary, Setの暗黙アップキャスト

class Animal {}
class Cat: Animal {}

func f(_ a: [Animal]) { print("[Animal]") }

func f(_ a: [Cat]) { print("[Cat]") }

let a: [Cat] = [Cat()]

f(a) // => [Cat]

  (attempting disjunction choice $T0 bound to decl rank5.(file).f@rank5.swift:4:6 : 
  ([Animal]) -> () at rank5.swift:4:6 [[locator@0x7fbeeb0aa000 [OverloadedDeclRef@rank5.swift:10:1]]];
    (overload set choice binding $T0 := ([Animal]) -> ())
    (attempting disjunction choice [Cat] bind [Animal] [deep equality] 
        [[locator@0x7fbeeb0aa3c8 [Call@rank5.swift:10:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
    )
    (attempting disjunction choice [Cat] arg conv [Animal] [array-upcast] 
        [[locator@0x7fbeeb0aa3c8 [Call@rank5.swift:10:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
      (increasing score due to collection upcast conversion)
      (found solution 0 0 0 0 0 0 0 1 0 0 0 0)
    )
  )


複合

class Animal {}
class Cat: Animal {}

func f(_ a: [Cat?]) { print("[Cat?]") }

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

func f(_ a: [Animal]) { print("[Animal]") }

let a: [Cat] = [Cat()]

f(a) // => [Animal]

  (attempting disjunction choice $T0 bound to decl rank5.(file).f@rank5.swift:4:6 : ([Cat?]) -> () at rank5.swift:4:6 
  [[locator@0x7fed5c001c00 [OverloadedDeclRef@rank5.swift:12:1]]];
    (overload set choice binding $T0 := ([Cat?]) -> ())
    (attempting disjunction choice [Cat] bind [Cat?] [deep equality] 
        [[locator@0x7fed5c002040 [Call@rank5.swift:12:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
    )
    (attempting disjunction choice [Cat] arg conv [Cat?] [array-upcast] 
        [[locator@0x7fed5c002040 [Call@rank5.swift:12:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
      (increasing score due to collection upcast conversion)
      (increasing score due to value to optional)
      (found solution 0 0 0 0 0 0 0 1 1 0 0 0)
    )
  )
  (attempting disjunction choice $T0 bound to decl rank5.(file).f@rank5.swift:6:6 : ([Any]) -> () at rank5.swift:6:6 
  [[locator@0x7fed5c001c00 [OverloadedDeclRef@rank5.swift:12:1]]];
    (overload set choice binding $T0 := ([Any]) -> ())
    (attempting disjunction choice [Cat] bind [Any] [deep equality] 
        [[locator@0x7fed5c002040 [Call@rank5.swift:12:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
    )
    (attempting disjunction choice [Cat] arg conv [Any] [array-upcast] 
        [[locator@0x7fed5c002040 [Call@rank5.swift:12:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
      (increasing score due to collection upcast conversion)
      (increasing score due to empty-existential conversion)
      (found solution 0 0 0 0 0 0 0 1 0 1 0 0)
    )
  )
  (attempting disjunction choice $T0 bound to decl rank5.(file).f@rank5.swift:8:6 : ([Animal]) -> () at rank5.swift:8:6 
  [[locator@0x7fed5c001c00 [OverloadedDeclRef@rank5.swift:12:1]]];
    (overload set choice binding $T0 := ([Animal]) -> ())
    (attempting disjunction choice [Cat] bind [Animal] [deep equality] 
        [[locator@0x7fed5c002040 [Call@rank5.swift:12:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
    )
    (attempting disjunction choice [Cat] arg conv [Animal] [array-upcast] 
        [[locator@0x7fed5c002040 [Call@rank5.swift:12:1 -> apply argument -> comparing call argument #0 to parameter #0]]];
      (increasing score due to collection upcast conversion)
      (found solution 0 0 0 0 0 0 0 1 0 0 0 0)
    )
  )


ランク6 SK_NonDefaultLiteral


リテラルが非デフォルト型になる

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

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

f(0) // => Int?

ランク7 SK_FunctionConversion


関数型の暗黙変換

class Animal {}
class Cat: Animal {}

// 0 0 0 0 0 1 0 0 1 0 0 0
func f(_ g: () -> Cat?) { print("() -> Cat?") }

// 0 0 0 0 0 1 0 0 0 0 0 0
func f(_ g: () -> Animal) { print("() -> Animal") }

// 0 0 0 0 0 0 0 0 1 0 0 0
func f(_ g: (() -> Cat)?) { print("(() -> Cat)?") }

func g() -> Cat { Cat() }

f(g) // => (() -> Cat)?

ランク8 SK_UserConversion


Objective-Cサポート時に、メタタイプからAnyObjectなどへの変換

class Cat {}

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

func f(_ a: Cat.Type) { print("Cat.Type") }

f(Cat.self) // => Cat.Type


ソース²

    if (getASTContext().LangOpts.EnableObjCInterop) {
      // These conversions are between concrete types that don't need further
      // resolution, so we can consider them immediately solved.
      auto addSolvedRestrictedConstraint
        = [&](ConversionRestrictionKind restriction) -> TypeMatchResult {
          addRestrictedConstraint(ConstraintKind::Subtype, restriction,
                                  type1, type2, locator);
          return getTypeMatchSuccess();
        };
      
      if (auto meta1 = type1->getAs<MetatypeType>()) {
        if (meta1->getInstanceType()->mayHaveSuperclass()
            && type2->isAnyObject()) {
          increaseScore(ScoreKind::SK_UserConversion);
          return addSolvedRestrictedConstraint(
                           ConversionRestrictionKind::ClassMetatypeToAnyObject);
        }
        // Single @objc protocol value metatypes can be converted to the ObjC
        // Protocol class type.
        auto isProtocolClassType = [&](Type t) -> bool {
          if (auto classDecl = t->getClassOrBoundGenericClass())
            if (classDecl->getName() == getASTContext().Id_Protocol
                && classDecl->getModuleContext()->getName()
                    == getASTContext().Id_ObjectiveC)
              return true;
          return false;
        };
        
        if (auto protoTy = meta1->getInstanceType()->getAs<ProtocolType>()) {
          if (protoTy->getDecl()->isObjC()
              && isProtocolClassType(type2)) {
            increaseScore(ScoreKind::SK_UserConversion);
            return addSolvedRestrictedConstraint(
                    ConversionRestrictionKind::ProtocolMetatypeToProtocolClass);
          }
        }
      }
      if (auto meta1 = type1->getAs<ExistentialMetatypeType>()) {
        // Class-constrained existential metatypes can be converted to AnyObject.
        if (meta1->getInstanceType()->isClassExistentialType()
            && type2->isAnyObject()) {
          increaseScore(ScoreKind::SK_UserConversion);
          return addSolvedRestrictedConstraint(
                     ConversionRestrictionKind::ExistentialMetatypeToAnyObject);
        }
      }
    }

User Conversion 🤔

後述


ランク9 SK_ForceUnchecked


IUO(T!)の暗黙unwrap

// 0 0 0 1 0 0 0 0 0 0 0 0
func f(_ a: Int) { print("Int") }

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

var a: Int! = 1

f(a)

ランク10 SK_DisfavoredOverload


@_disfavoredOverloadが付いてるとコストが生じる

@_disfavoredOverload
func f(_ a: Int) { print("Int") }

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

let a: Int = 1
f(a) // => Int?


今年の5月に実装 ³


SwiftUIで使われてる😲


// /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform \
// /Developer/SDKs/iPhoneOS13.2.sdk/System/Library/Frameworks \
// /SwiftUI.framework/Modules/SwiftUI.swiftmodule/arm64.swiftinterface

@available(iOS 13.0, OSX 10.15, tvOS 13.0, watchOS 6.0, *)
extension Button where Label == SwiftUI.Text {
  public init(_ titleKey: SwiftUI.LocalizedStringKey, action: @escaping () -> Swift.Void)
  @_disfavoredOverload public init<S>(_ title: S, action: @escaping () -> Swift.Void) 
    where S : Swift.StringProtocol
}

ランク11 SK_Unavailable


@availableで無効になっていると付く。
最終的にエラーになる。

// 0 1 0 0 0 0 0 0 0 0 0 0
@available(*, unavailable)
func f(_ a: Int) { print("Int") }

let a: Int = 1
f(a)

/*
 rank11.swift:6:1: error: 'f' is unavailable
 f(a)
 ^
 rank11.swift:3:6: note: 'f' has been explicitly marked unavailable here
 func f(_ a: Int) { print("Int") }
      ^
 */

ランク12 SK_Fix


「もしかして」機能のために生成された仮説に付与される。

func f(a: Int) { print("Int") }

let a: Int = 1
f(b: a)

/*
 rank12.swift:4:2: error: incorrect argument label in call (have 'b:', expected 'a:')
 f(b: a)
  ^~
   a
 */

---Constraint solving for the expression at [rank12.swift:4:1 - line:4:7]---
  (overload set choice binding $T0 := (Int) -> ())
  (overload set choice binding $T1 := Int)
(attempting fix [fix: re-label argument(s)] @ locator@0x7fdfbb0e55b0 [Call@rank12.swift:4:1])
(increasing score due to attempting to fix the source)

Score: 1 0 0 0 0 0 0 0 0 0 0 0
Type Variables:
  $T0 [lvalue allowed] as (Int) -> () @ locator@0x7fdfbb0e5400 [DeclRef@rank12.swift:4:1]
  $T1 [lvalue allowed] as Int @ locator@0x7fdfbb0e5488 [DeclRef@rank12.swift:4:6]
  $T2 as () @ locator@0x7fdfbb0e5510 [Call@rank12.swift:4:1 -> function result]

Active Constraints:

Inactive Constraints:
Resolved overloads:
  selected overload set choice a: $T1 == Int
  selected overload set choice f: $T0 == (Int) -> ()


Fixes:
  [fix: re-label argument(s)] @ locator@0x7fdfbb0e55b0 [Call@rank12.swift:4:1]
  (found solution 1 0 0 0 0 0 0 0 0 0 0 0)


このFix機構の解説が10月に公式ブログで公開された⁴


User Conversion


TypeChecker.rst⁵


Swiftの推論器について書かれた文書


そこに出てくる謎コード

struct X {
  // user-defined conversions
  func [conversion] __conversion () -> String { /* ... */ }
  func [conversion] __conversion () -> Int { /* ... */ }
}

func f(_ i : Int, s : String) { }

var x : X
f(10.5, x)

Gitで歴史調査


User Conversionの実装⁶

Implement simplification of conversion constraints for user-defined
conversions.

Swift SVN r2730

DougGregor committed on 24 Aug 2012


WWDCでSwift発表 2014/6/2


User Conversionの禁止⁷

Ban __conversion functions.

Swift SVN r21015

DougGregor committed on 5 Aug 2014


User Conversionの削除⁸

Remove user-defined conversions from the type checker.

Swift SVN r21379

DougGregor committed on 22 Aug 2014


Swift1.0がXcode6と共に配布 2014/9/9


SK_UserConversionを現在の用途で使用⁹

Type checker: Increase the score of metatype-to-object conversions.

Swift SVN r27415

jckarter committed on 17 Apr 2015


Swift2.0がXcode7と共に配布 2015/9/21

Footnotes


lib/Sema/ConstraintSystem.h ↩


lib/Sema/CSSimplify.cpp ↩


https://github.com/apple/swift/pull/24799 ↩


New Diagnostic Architecture Overview ↩


docs/TypeChecker.rst ↩


fa474ee750edb7a3d34a767e02426f4509041698 ↩


9d5ba31daa8f63a333e9fb993e5204923a46f98c ↩


397f4a98880f82e439b1c4164885abb21cd56d09 ↩


be7c339af86142217686f10e039349924226e9ea ↩