Swift-12：泛型

本文主要介绍泛型及其底层原理

泛型

泛型主要用于解决代码的抽象能力 + 代码的复用性

例如下面的例子，其中的T就是泛型

func test<T>(_ a: T, _ b: T)->Bool{
    return a == b
}

//经典例子swap，使用泛型，可以满足不同类型参数的调用
func swap<T>(_ a: inout T, _ b: inout T){
    let tmp = a
    a = b
    b = tmp
}

类型约束

在一个类型参数后面放置协议或者是类，例如下面的例子，要求类型参数T遵循Equatable协议

func test<T: Equatable>(_ a: T, _ b: T)->Bool{
    return a == b
}

当传入的参数是没有遵循Equatable协议时，会报错

关联类型

在定义协议时，使用关联类型给协议中用到的类型起一个占位符名称

• 此时的数组中的类型是Int

struct CJLStack {
    private var items = [Int]()

    mutating func push(_ item: Int){
        items.append(item)
    }

    mutating func pop() -> Int?{
        if items.isEmpty {
            return nil
        }
        return items.removeLast()
    }
}

• 如果想使用其他类型呢？可以通过协议来实现

protocol CJLStackProtocol {
    //协议中使用类型的占位符
    associatedtype Item
}
struct CJLStack: CJLStackProtocol{
    //在使用时，需要指定具体的类型
    typealias Item = Int
    private var items = [Item]()

    mutating func push(_ item: Item){
        items.append(item)
    }

    mutating func pop() -> Item?{
        if items.isEmpty {
            return nil
        }
        return items.removeLast()
    }
}

where语句

where语句主要用于 表明泛型需要满足的条件，即限制形式参数的要求，如下所示

//***********3、where语句：表明泛型需要满足的条件
protocol CJLStackProtocol {
    //协议中使用类型的占位符
    associatedtype Item
    var itemCount: Int {get}
    mutating func pop() -> Item?
    func index(of index: Int) -> Item
}
struct CJLStack: CJLStackProtocol{
    //在使用时，需要指定具体的类型
    typealias Item = Int
    private var items = [Item]()

    var itemCount: Int{
        get{
            return items.count
        }
    }

    mutating func push(_ item: Item){
        items.append(item)
    }

    mutating func pop() -> Item?{
        if items.isEmpty {
            return nil
        }
        return items.removeLast()
    }

    func index(of index: Int) -> Item {
        return items[index]
    }
}
/*
 where语句
 - T1.Item == T2.Item 表示T1和T2中的类型必须相等
 - T1.Item: Equatable 表示T1的类型必须遵循Equatable协议，意味着T2也要遵循Equatable协议
 */
func compare<T1: CJLStackProtocol, T2: CJLStackProtocol>(_ stack1: T1, _ stack2: T2) -> Bool where T1.Item == T2.Item, T1.Item: Equatable{
    guard stack1.itemCount == stack2.itemCount else {
        return false
    }

    for i in 0..<stack1.itemCount {
        if stack1.index(of: i) !=  stack2.index(of: i){
            return false
        }
    }
    return true
}

下面这种写法也是可以的

//写法二
protocol CJLStackProtocol {
    //协议中使用类型的占位符
    associatedtype Item
    var itemCount: Int {get}
    mutating func pop() -> Item?
    func index(of index: Int) -> Item
}
struct CJLStack: CJLStackProtocol{
    //在使用时，需要指定具体的类型
    typealias Item = Int
    private var items = [Item]()

    var itemCount: Int{
        get{
            return items.count
        }
    }

    mutating func push(_ item: Item){
        items.append(item)
    }

    mutating func pop() -> Item?{
        if items.isEmpty {
            return nil
        }
        return items.removeLast()
    }

    func index(of index: Int) -> Item {
        return items[index]
    }
}
extension CJLStackProtocol where Item: Equatable{}

• 当希望泛型指定类型时拥有特定功能，可以像下面这么写(在上述写法二的基础上增加extension)

//当希望泛型指定类型时拥有特定功能，可以像下面这么写
extension CJLStackProtocol where Item == Int{
    func test(){
        print("test")
    }
}
var s = CJLStack()
s.test()

<!--打印结果-->
test

• 如果将where后的Int改成Double类型，是无法找到test函数的

泛型函数

我们在上面介绍了泛型的基本语法，下面来分析下泛型的底层原理

以下面一个简单的泛型函数为例

//简单的泛型函数
func testGenric<T>(_ value: T) -> T{
    let tmp = value
    return tmp
}

class CJLTeacher {
    var age: Int = 18
    var name: String = "Kody"
}

//传入Int类型
testGenric(10)
//传入元组
testGenric((10, 20))
//传入实例对象
testGenric(CJLTeacher())

从上面的代码中可以看出，泛型函数可以接受任何类型

疑问：那么泛型是如何区分不同的参数，来管理不同类型的内存呢？

• 查看SIL代码，并没有什么内存相关的信息

• 查看IR代码，从中可以得出VWT中存放的是 size（大小）、alignment（对齐方式）、stride（步长）、destory、copy（函数）

  所以VWT+PWT的存储结构图示如下所示

源码分析

• 在swift-source中搜索valueWitnesses（在Metadata.h中）
  对于每一个类型（Int或者自定义），都在metadata中存储了一个VWT（用来管理当前类型的值）

• 继续来到Metadataimpl.h文件，查看其中的元组的源码

然后回到刚开始的泛型函数testGenric

func testGenric<T>(_ value: T) -> T{
    //tmp在栈上申请空间，如何知道申请多大呢?可以通过metadata中存储的vwt得知
    //copy
    let tmp = value
    //destory
    return tmp
}

其IR代码的详细分析如下

; Function Attrs: argmemonly nounwind willreturn 泛型函数
declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1
; %swift.type* %T 表示 传入类型的matadata
define hidden swiftcc void @"$s4main10testGenricyxxlF"(%swift.opaque* noalias nocapture sret %0, %swift.opaque* noalias nocapture %1, %swift.type* %T) #0 {
entry:
  %T1 = alloca %swift.type*, align 8
  %tmp.debug = alloca i8*, align 8
  %2 = bitcast i8** %tmp.debug to i8*
  call void @llvm.memset.p0i8.i64(i8* align 8 %2, i8 0, i64 8, i1 false)
  store %swift.type* %T, %swift.type** %T1, align 8
  %3 = bitcast %swift.type* %T to i8***
  %4 = getelementptr inbounds i8**, i8*** %3, i64 -1
  ; valueWitnesses 值目录表，将其存入了 %swift.vwtable* 中
  %T.valueWitnesses = load i8**, i8*** %4, align 8, !invariant.load !46, !dereferenceable !47
  ; 做了一个类型转换
  %5 = bitcast i8** %T.valueWitnesses to %swift.vwtable*
  ; 在valueWitnesses中获取当前这个类型的size大小
  %6 = getelementptr inbounds %swift.vwtable, %swift.vwtable* %5, i32 0, i32 8
  %size = load i64, i64* %6, align 8, !invariant.load !46
  ; 然后根据获取的size，分配内存空间
  %7 = alloca i8, i64 %size, align 16
  call void @llvm.lifetime.start.p0i8(i64 -1, i8* %7)
  %8 = bitcast i8* %7 to %swift.opaque*
  ; 初始化tmp的内存空间
  store i8* %7, i8** %tmp.debug, align 8
  %9 = getelementptr inbounds i8*, i8** %T.valueWitnesses, i32 2
  %10 = load i8*, i8** %9, align 8, !invariant.load !46
  ; copy 拷贝
  %initializeWithCopy = bitcast i8* %10 to %swift.opaque* (%swift.opaque*, %swift.opaque*, %swift.type*)*
  %11 = call %swift.opaque* %initializeWithCopy(%swift.opaque* noalias %8, %swift.opaque* noalias %1, %swift.type* %T) #6
  %12 = call %swift.opaque* %initializeWithCopy(%swift.opaque* noalias %0, %swift.opaque* noalias %8, %swift.type* %T) #6
  %13 = getelementptr inbounds i8*, i8** %T.valueWitnesses, i32 1
  %14 = load i8*, i8** %13, align 8, !invariant.load !46
  ; destory 销毁
  %destroy = bitcast i8* %14 to void (%swift.opaque*, %swift.type*)*
  call void %destroy(%swift.opaque* noalias %8, %swift.type* %T) #6
  %15 = bitcast %swift.opaque* %8 to i8*
  call void @llvm.lifetime.end.p0i8(i64 -1, i8* %15)
  ret void
}

所以，从IR代码中可以得知，当前泛型是通过ValueWitnessTable来进行内存操作的

源码调试

调试分为两种，值类型和引用类型

引用类型调试

• 源码调试如下

• 在retain函数中加断点调试

• 通过lldb调试如下：obj中存储CJLTeacher变量

结论：对于引用类型，会调用retain进行引用计数+1，对于destory来说，就会调用release进行引用计数-1

• 泛型类型使用VWT进行内存管理，VWT由编译器生成，其存储了该类型的size、alignment以及针对该类型的基本内存操作
• 当对泛型类型进行内存操作时（例如：内存拷贝）时，最终会调用对应泛型的VWT中的基本内存操作
• 泛型类型不同，其对应的VWT也不同

值类型调试

• 在initializeWithTake方法中加断点

结论：值类型是通过当前内存的copy、move来进行内存拷贝。对于destory，内部调用析构函数

总结

• 对于一个值类型，例如Integer，

  • 1、该类型的copy和move操作会进行内存拷贝，

  • 2、destory操作则不进行任何操作

• 对于一个引用类型，如class，

  • 1、该类型的copy操作会对引用计数+1，

  • 2、move操作会拷贝指针，而不会更新引用计数；

  • 3、destory操作会对引用计数-1

泛型函数传入函数的分析

上面都是对变量进行的分析，那么一问来了

如果泛型函数中传的是一个函数呢？

代码如下所示，此时传入的m，是传入的整个结构体吗？

//如果此时传入的是一个函数呢？
func makeIncrement() -> (Int) -> Int{
    var runningTotal = 10
    return {
        runningTotal += $0
        return runningTotal
    }
}

func testGenric<T>(_ value: T){}

//m中存储的是一个结构体：{i8*, swift type *}
let m = makeIncrement()
testGenric(m)

• 分析IR代码

define i32 @main(i32 %0, i8** %1) #0 {
entry:
  %2 = alloca %swift.function, align 8
  %3 = bitcast i8** %1 to i8*
  ; s4main13makeIncrementS2icyF 调用makeIncrement函数，返回一个结构体 {函数调用地址， 捕获值的内存地址}
  %4 = call swiftcc { i8*, %swift.refcounted* } @"$s4main13makeIncrementS2icyF"()
     ; 闭包表达式的地址
  %5 = extractvalue { i8*, %swift.refcounted* } %4, 0
     ; 捕获值的引用类型
  %6 = extractvalue { i8*, %swift.refcounted* } %4, 1

  ; 往m变量地址中存值
    ; 将 %5 存入 swift.function*结构体中（%swift.function = type { i8*, %swift.refcounted* }）
    ; s4main1myS2icvp ==>  main.m : (Swift.Int) -> Swift.Int，即全局变量 m
  store i8* %5, i8** getelementptr inbounds (%swift.function, %swift.function* @"$s4main1myS2icvp", i32 0, i32 0), align 8

  ; 将值放入 f 这个变量中，并强转为指针
  store %swift.refcounted* %6, %swift.refcounted** getelementptr inbounds (%swift.function, %swift.function* @"$s4main1myS2icvp", i32 0, i32 1), align 8
    ; 将%2 强转为 i8*（即 void*）
  %7 = bitcast %swift.function* %2 to i8*
  call void @llvm.lifetime.start.p0i8(i64 16, i8* %7)

  ; 取出 function中 闭包表达式的地址
  %8 = load i8*, i8** getelementptr inbounds (%swift.function, %swift.function* @"$s4main1myS2icvp", i32 0, i32 0), align 8
  %9 = load %swift.refcounted*, %swift.refcounted** getelementptr inbounds (%swift.function, %swift.function* @"$s4main1myS2icvp", i32 0, i32 1), align 8

  ; 将返回的闭包表达式 当做一个参数传入 方法，所以 retainCount+1
  %10 = call %swift.refcounted* @swift_retain(%swift.refcounted* returned %9) #2

  ; 创建了一个对象，存储了 <{ %swift.refcounted, %swift.function }>*
  %11 = call noalias %swift.refcounted* @swift_allocObject(%swift.type* getelementptr inbounds (%swift.full_boxmetadata, %swift.full_boxmetadata* @metadata, i32 0, i32 2), i64 32, i64 7) #2
  ; 将 %swift.refcounted* %11 强转成了一个结构体类型
  %12 = bitcast %swift.refcounted* %11 to <{ %swift.refcounted, %swift.function }>*

  ; 取出 %swift.function （最终的结果就是往 <{ %swift.refcounted, %swift.function }> 的%swift.function 中存值 ==> 做了间接的转换与传递） 
  %13 = getelementptr inbounds <{ %swift.refcounted, %swift.function }>, <{ %swift.refcounted, %swift.function }>* %12, i32 0, i32 1
  ; 取出 <i8*, %swift.function>的首地址
  %.fn = getelementptr inbounds %swift.function, %swift.function* %13, i32 0, i32 0
  ; 将 i8* 放入 i8** %.fn 中（即创建的数据结构 <{ %swift.refcounted, %swift.function }> 的 %swift.function 中）
  store i8* %8, i8** %.fn, align 8
  %.data = getelementptr inbounds %swift.function, %swift.function* %13, i32 0, i32 1
  store %swift.refcounted* %9, %swift.refcounted** %.data, align 8
  %.fn1 = getelementptr inbounds %swift.function, %swift.function* %2, i32 0, i32 0
  ; 将 %swift.refcounted 存入 %swift.function 中
  store i8* bitcast (void (%TSi*, %TSi*, %swift.refcounted*)* @"$sS2iIegyd_S2iIegnr_TRTA" to i8*), i8** %.fn1, align 8
  %.data2 = getelementptr inbounds %swift.function, %swift.function* %2, i32 0, i32 1
  store %swift.refcounted* %11, %swift.refcounted** %.data2, align 8

  ; 将%2强转成了 %swift.opaque* 类型，其中 %2 就是  %swift.function内存空间，即存储的东西（函数地址 + 捕获值地址）
  %14 = bitcast %swift.function* %2 to %swift.opaque*
  ; sS2icMD ==> demangling cache variable for type metadata for (Swift.Int) -> Swift.Int 即函数的metadata
  %15 = call %swift.type* @__swift_instantiateConcreteTypeFromMangledName({ i32, i32 }* @"$sS2icMD") #9

  ; 调用 testGenric 函数
  call swiftcc void @"$s4main10testGenricyyxlF"(%swift.opaque* noalias nocapture %14, %swift.type* %15)
  ......

仿写泛型函数传入函数时的底层结构

仿写上述逻辑的结构

//如果此时传入的是一个函数呢？
struct HeapObject {
    var type: UnsafeRawPointer
    var refCount1: UInt32
    var refCount2: UInt32
}
struct FunctionData<T> {
    var ptr: UnsafeRawPointer
    var captureValue: UnsafePointer<T>
}
struct Box<T> {
    var refCounted: HeapObject
    var value: T
}
struct GenData<T> {
    var ref: HeapObject
    var function: FunctionData<T>
}

func makeIncrement() -> (Int) -> Int{
    var runningTotal = 10
    return {
        runningTotal += $0
        return runningTotal
    }
}

func testGenric<T>(_ value: T){
    //查看T的存储
    let ptr = UnsafeMutablePointer<T>.allocate(capacity: 1)
    ptr.initialize(to: value)
    /*
     - 将 %13的值给了 %2即 %swift.function*
     %13 = getelementptr inbounds <{ %swift.refcounted, %swift.function }>, <{ %swift.refcounted, %swift.function }>* %12, i32 0, i32 1

     - 调用方法 %14 -> %2
     %14 = bitcast %swift.function* %2 to %swift.opaque*
     call swiftcc void @"$s4main10testGenricyyxlF"(%swift.opaque* noalias nocapture %14, %swift.type* %15)
     */
    let ctx = ptr.withMemoryRebound(to: FunctionData<GenData<Box<Int>>>.self, capacity: 1) {
        $0.pointee.captureValue.pointee.function.captureValue
    }
    print(ctx.pointee.value)//捕获的值是10
}

//m中存储的是一个结构体：{i8*, swift type *}
let m = makeIncrement()
testGenric(m)

<!--打印结果-->
10

所以当是一个泛型函数传递过程中，会做一层包装，意味着并不会直接的将m中的函数值、type给testGenric函数，而是做了一层抽象，目的是解决不同类型在传递过程中的问题

总结

• 泛型主要用于解决代码的抽象能力，以及提升代码的复用性

• 如果一个泛型遵循了某个协议，则在使用时，要求具体的类型也是必须遵循某个协议的

• 在定义协议时，可以使用关联类型给协议中用到的类型起一个占位符名称

• where语句主要用于表明泛型需要满足的条件，即限制形式参数的要求

• 泛型类型使用VWT进行内存管理（即通过VWT区分不同类型），VWT由编译器生成，其存储了该类型的size、alignment以及针对该类型的基本内存操作

  • 1、当对泛型类型进行内存操作时（例如：内存拷贝）时，最终会调用对应泛型的VWT中的基本内存操作
  • 2、泛型类型不同，其对应的VWT也不同

• 当希望泛型指定类型时拥有特定功能，可以通过extension实现

• 对于泛型函数来说，有以下几种情况：

  • 传入的是一个值类型，例如Integer，

    • 1、该类型的copy和move操作会进行内存拷贝，

    • 2、destory操作则不进行任何操作

  • 传入的是一个引用类型，如class，

    • 1、该类型的copy操作会对引用计数+1，

    • 2、move操作会拷贝指针，而不会更新引用计数；

    • 3、destory操作会对引用计数-1

  • 如果泛型函数传入的是一个函数，在传递过程中，会做一层包装，简单来说，就是不会直接将函数的函数值+type给泛型函数，而是做了一层抽象，主要是用于解决不同类型的传递问题