V-table和witness table

我們知道,執(zhí)行方法時,首先要查找到正確的方法,然后執(zhí)行.能夠在編譯期確定執(zhí)行方法的方式叫做靜態(tài)分派static dispatch,無法在編譯期確定,只能在運行時去確定執(zhí)行方法的分派方式叫做動態(tài)分派dynamic dispatch.
靜態(tài)分派更快,而且靜態(tài)分派可以進行內(nèi)聯(lián)等進一步的優(yōu)化操作,使得執(zhí)行更快速,性能更高.
但是對于多態(tài)的情況,我們不能在編譯期確定最終的類型,這里就用到了dynamic dispatch動態(tài)分派.動態(tài)分派的實現(xiàn)是,每種類型都會創(chuàng)建一張表,表內(nèi)是一個包含了方法指針的數(shù)組.
對于類class來說,每個類型都會創(chuàng)建虛函數(shù)表指針,指向一個叫做V-Table的表.擁有繼承關(guān)系的子類會在虛函數(shù)表內(nèi)通過繼承順序(C++可以實現(xiàn)多繼承)去展示虛函數(shù)表指針.
但是對于swift來說,class類和struct結(jié)構(gòu)體的實現(xiàn)是不同的,而屬于結(jié)構(gòu)體的協(xié)議Protocol,可以擁有屬性和實現(xiàn)方法,管理Protocol Type方法分派的表就叫做Protocol Witness Table.

witness table內(nèi)部結(jié)構(gòu)

witness table

什么是value witness table

value witness table

說完witness table的結(jié)構(gòu),我們討論一下,在編譯器內(nèi)部實現(xiàn)中,SIL(swift intermediate language)內(nèi)部是如何實現(xiàn)vtable和witness table的.

V-Table在SIL的實現(xiàn)

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 操作來實現(xiàn)類方法的動態(tài)分派.
類的每一個方法,都被映射到SIL的方法實現(xiàn)

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持有了聲明的重載關(guān)系,并用于在SIL的vtable中查找衍生類的重載方法.
為了防止SIL的方法是thunk,方法名使用了原始方法實現(xiàn)的連接(linkage)作為前綴.

Witness Tables在編譯期內(nèi)SIL階段的實現(xiàn)

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

SIL將泛型動態(tài)分派所需的信息編碼為witness表.這些信息用于在生成二進制碼時產(chǎn)生運行時分配表(runtime dispatch table).也可以用于對特定通用函數(shù)的SIL優(yōu)化.每個明確的一致性聲明都會產(chǎn)生witness表.通用類型的所有實例共享一個通用witness表.衍生類會繼承基類的witness表.

protocol-conformance ::= normal-protocol-conformance //一般協(xié)議一致性
protocol-conformance ::= 'inherit' '(' protocol-conformance ')'  //繼承關(guān)系的協(xié)議一致性
protocol-conformance ::= 'specialize' '<' substitution* '>'    //通用類型特化的協(xié)議一致性和標(biāo)明類型降級的替換(substitution)
                         '(' protocol-conformance ')'
protocol-conformance ::= 'dependent'
normal-protocol-conformance ::= identifier ':' identifier 'module' identifier

witness的關(guān)鍵在于協(xié)議一致性.它是對于具體類型協(xié)議一致性的唯一標(biāo)識.

• 一般的協(xié)議一致性通過它們遵守的協(xié)議方法進行命名.屬于該類型或擴展的組件,需要提供遵守協(xié)議方法的聲明,實現(xiàn)方法必須嚴(yán)格和協(xié)議需求一一對應(yīng).
• 派生類如何遵守從基類繼承的協(xié)議,會體現(xiàn)為繼承協(xié)議一致性(inherited protocol conformance),實現(xiàn)是簡單引用基類的協(xié)議一致性即可.
• 如果通用類型的實例遵守一個協(xié)議,是通過特化一致性的方式去實現(xiàn)的.將通用參數(shù)和普通一致性進行綁定,將參數(shù)用于通用類型.
  witness table只會直接關(guān)聯(lián)標(biāo)準(zhǔn)一致性.繼承和特定一致性是在標(biāo)準(zhǔn)一致性下的間接引用.

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由以下內(nèi)容構(gòu)成

• 基協(xié)議項提供的對于協(xié)議一致性的引用,可以用于witness協(xié)議的繼承協(xié)議
• 方法項將協(xié)議中要求方法映射為SIL中實現(xiàn)了witness類型的方法.每個方法項必須對應(yīng)witness協(xié)議中的要求方法
• associate type關(guān)聯(lián)類型項將必須實現(xiàn)的協(xié)議方法中的關(guān)聯(lián)類型映射為符合witness的類型.注意witness類似是一個資源級別的swift類型,不是SIL類型(上面分析過SIL類型和swift類型的區(qū)別).關(guān)聯(lián)類型項必須覆蓋witness協(xié)議中的所有強制關(guān)聯(lián)項.
• 關(guān)聯(lián)類型協(xié)議項將關(guān)聯(lián)類型中的協(xié)議映射為關(guān)聯(lián)類型的協(xié)議一致性.

參考

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