V-table和witness table

我们知道,执行方法时,首先要查找到正确的方法,然后执行.能够在编译期确定执行方法的方式叫做静态分派static dispatch,无法在编译期确定,只能在运行时去确定执行方法的分派方式叫做动态分派dynamic dispatch.
静态分派更快,而且静态分派可以进行内联等进一步的优化操作,使得执行更快速,性能更高.
但是对于多态的情况,我们不能在编译期确定最终的类型,这里就用到了dynamic dispatch动态分派.动态分派的实现是,每种类型都会创建一张表,表内是一个包含了方法指针的数组.
对于类class来说,每个类型都会创建虚函数表指针,指向一个叫做V-Table的表.拥有继承关系的子类会在虚函数表内通过继承顺序(C++可以实现多继承)去展示虚函数表指针.
但是对于swift来说,class类和struct结构体的实现是不同的,而属于结构体的协议Protocol,可以拥有属性和实现方法,管理Protocol Type方法分派的表就叫做Protocol Witness Table.

witness table内部结构

witness table

什么是value witness table

value witness table

说完witness table的结构,我们讨论一下,在编译器内部实现中,SIL(swift intermediate language)内部是如何实现vtable和witness table的.

V-Table在SIL的实现

decl ::= sil-vtable
sil-vtable ::= 'sil_vtable' identifier '{' sil-vtable-entry* '}'

sil-vtable-entry ::= sil-decl-ref ':' sil-linkage? sil-function-name

SIL使用 class_method, super_method, objc_method, 和 objc_super_method 操作来实现类方法的动态分派.
类的每一个方法,都被映射到SIL的方法实现

class A {
  func foo()
  func bar()
  func bas()
}

sil @A_foo : $@convention(thin) (@owned A) -> ()
sil @A_bar : $@convention(thin) (@owned A) -> ()
sil @A_bas : $@convention(thin) (@owned A) -> ()

sil_vtable A {
  #A.foo!1: @A_foo
  #A.bar!1: @A_bar
  #A.bas!1: @A_bas
}

class B : A {
  func bar()
}

sil @B_bar : $@convention(thin) (@owned B) -> ()

sil_vtable B {
  #A.foo!1: @A_foo
  #A.bar!1: @B_bar
  #A.bas!1: @A_bas
}

class C : B {
  func bas()
}

sil @C_bas : $@convention(thin) (@owned C) -> ()

sil_vtable C {
  #A.foo!1: @A_foo
  #A.bar!1: @B_bar
  #A.bas!1: @C_bas
}

需要注意的是,vtable中的方法声明是指向最后的衍生类的方法的.swift的AST持有了声明的重载关系,并用于在SIL的vtable中查找衍生类的重载方法.
为了防止SIL的方法是thunk,方法名使用了原始方法实现的连接(linkage)作为前缀.

Witness Tables在编译期内SIL阶段的实现

decl ::= sil-witness-table
sil-witness-table ::= 'sil_witness_table' sil-linkage?
                      normal-protocol-conformance '{' sil-witness-entry* '}'

SIL将泛型动态分派所需的信息编码为witness表.这些信息用于在生成二进制码时产生运行时分配表(runtime dispatch table).也可以用于对特定通用函数的SIL优化.每个明确的一致性声明都会产生witness表.通用类型的所有实例共享一个通用witness表.衍生类会继承基类的witness表.

protocol-conformance ::= normal-protocol-conformance //一般协议一致性
protocol-conformance ::= 'inherit' '(' protocol-conformance ')'  //继承关系的协议一致性
protocol-conformance ::= 'specialize' '<' substitution* '>'    //通用类型特化的协议一致性和标明类型降级的替换(substitution)
                         '(' protocol-conformance ')'
protocol-conformance ::= 'dependent'
normal-protocol-conformance ::= identifier ':' identifier 'module' identifier

witness的关键在于协议一致性.它是对于具体类型协议一致性的唯一标识.

• 一般的协议一致性通过它们遵守的协议方法进行命名.属于该类型或扩展的组件,需要提供遵守协议方法的声明,实现方法必须严格和协议需求一一对应.
• 派生类如何遵守从基类继承的协议,会体现为继承协议一致性(inherited protocol conformance),实现是简单引用基类的协议一致性即可.
• 如果通用类型的实例遵守一个协议,是通过特化一致性的方式去实现的.将通用参数和普通一致性进行绑定,将参数用于通用类型.
  witness table只会直接关联标准一致性.继承和特定一致性是在标准一致性下的间接引用.

sil-witness-entry ::= 'base_protocol' identifier ':' protocol-conformance
sil-witness-entry ::= 'method' sil-decl-ref ':' sil-function-name
sil-witness-entry ::= 'associated_type' identifier
sil-witness-entry ::= 'associated_type_protocol'
                      '(' identifier ':' identifier ')' ':' protocol-conformance

witness table由以下内容构成

• 基协议项提供的对于协议一致性的引用,可以用于witness协议的继承协议
• 方法项将协议中要求方法映射为SIL中实现了witness类型的方法.每个方法项必须对应witness协议中的要求方法
• associate type关联类型项将必须实现的协议方法中的关联类型映射为符合witness的类型.注意witness类似是一个资源级别的swift类型,不是SIL类型(上面分析过SIL类型和swift类型的区别).关联类型项必须覆盖witness协议中的所有强制关联项.
• 关联类型协议项将关联类型中的协议映射为关联类型的协议一致性.

参考

• swift memorylayout
• witness table video
• protocol types pdf
• makeing the value witness table reference relative