This is the 22nd day of my participation in the August More Text Challenge

This article mainly introduces generics and their underlying principles

The generic

Generics are primarily used to address code abstraction + code reuse

For example, in the following example, T is generic

Func test<T>(_ a: T, _ b: T)->Bool{return a == b} func swap<T>(_ a: inout T, _ b: inout T){ let tmp = a a = b b = tmp }Copy the code

Type constraints

Placing a protocol or class after a type parameter, such as the following example, requires that the type parameter T conform to the Equatable protocol

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

When the incoming parameter is not followedEquatableAn error message is displayed during the protocol

Association types

When defining a protocol, use an association type to give a placeholder name to the type used in the protocol

  • The type of the array is 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() } }Copy the code
  • What if you want to use another type? canBy protocol
Protocol CJLStackProtocol {// associatedType Item} struct CJLStack: 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() } }Copy the code

Where clause

The WHERE statement is mainly used to indicate the conditions that generics need to satisfy, namely the requirements that restrict formal parameters, as shown below

Protocol CJLStackProtocol {// AssociatedType Item var itemCount: CJLStackProtocol {// associatedType Item var itemCount: CJLStackProtocol {// associatedType Item var itemCount: Int {get} mutating func pop() -> Item? func index(of index: Int) -> Item } struct CJLStack: 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 statement -t1. Item == t2. Item indicates that the types in T1 and T2 must be the same. */ func compare<T1: CJLStackProtocol, T2: 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 }Copy the code

This is also possible

Protocol CJLStackProtocol {associatedType Item var itemCount: CJLStackProtocol {associatedType Item var itemCount: CJLStackProtocol Int {get} mutating func pop() -> Item? func index(of index: Int) -> Item } struct CJLStack: 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{}Copy the code
  • When you want toGenerics have specific capabilities when they specify types, you can write extension as follows (add extension on the basis of above method 2).
// When you want a generic type to specify a type, Where Item == Int{func test(){print("test")}} var s = CJLStack() s.test() <! Print the result --> testCopy the code
  • We cannot find test if we change the Int after where to a Double

Generic function

We’ve covered the basic syntax of generics, but now we’ll look at the underlying principles of generics

Take the following simple generic function for example

Func testGenric<T>(_ value: T) -> T{let TMP = value return TMP} class CJLTeacher {var age: Int = 18 var name: String = "Kody"} // pass Int testGenric(10) // pass tuple testGenric((10, 20)) // pass instance object testGenric(CJLTeacher())Copy the code

As you can see from the above code, generic functions can accept any type

Question: How do generics distinguish between different parameters to manage different types of memory?

  • Look at the SIL code, there is no memory related information

  • Look at the IR codeVWTIs stored insize(size),alignment(Alignment),stride(Step size)destory,copy(function)

So the storage structure of VWT+PWT is shown below

Source code analysis

  • Search in swift-sourcevalueWitnesses(In metadata.h)

For each type (Int or custom), one is stored in metadataVWT(Used to manage values of the current type)

  • Continue to come toMetadataimpl.hFile, check it outtuplesThe source of

Then go back to the generic function testGenric where we started

Func testGenric<T>(_ value: T) -> T{func testGenric<T>(_ value: T) -> T{func testGenric<T>(_ value: T) -> T{ //copy let TMP = value //destory return TMP}Copy the code

A detailed analysis of its IR code is as follows

; Function Attrs: Argmemonly NounWind WillReturn The general function declare void @llvm.lifetime.start.p0i8(i64 IMmarg, i8* nocapture) #1; %swift.type* %T Indicates the incoming type. 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 ; % t. valueWitnesses = load I8 **, i8** %4, align 8,! invariant.load ! 46,! dereferenceable ! 47. Example: %5 = bitcast i8** %T.value witnesses to % swif.vwtable *; Example: getelementptr inbounds % swif. vwtable, % swif. vwtable* %5, i32 0, example: getelementptr inbounds % swif. vwtable, % swif. vwtable* %5, i32 0, i32 8 %size = load i64, i64* %6, align 8, ! invariant.load ! 46. And then based on the size I got, %7 = alloca i8, i64 %size, align 16 call void @llvm.lifetime.start.p0i8(i64-1, i8* %7) %8 = bitcast i8* %7 to %swift.opaque* ; Store i8* %7, i8** %tmp.debug, align 8 %9 = getelementptr inbounds i8*, i8** %. i32 2 %10 = load i8*, i8** %9, align 8, ! invariant.load ! 46. 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 %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 }Copy the code

So, as you can see from IR code, the current generics do memory operations through ValueWitnessTable

The source code to debug

There are two types of debugging, value types and reference types

Reference type debugging

  • Source code debugging is as follows

  • inretainFunction to add breakpoint debugging

  • Debugging through LLDB is as follows:objStored in theCJLTeacher variable

conclusion: is called for reference typesretainReference counting+ 1fordestoryRelease is called for reference counting- 1

  • Generic type useVWTforMemory management, VWT is generated by the compiler, which stores the size, alignment, and basic memory operations for the type
  • When a memory operation is performed on a generic type (for example, a memory copy), the base memory operation in the VWT corresponding to the generic type is eventually invoked
  • The VWT for each generic type is different

Value type debugging

  • ininitializeWithTakeAdd breakpoint to method

conclusion: The value type isCopy and move the current memory to copy the memory. fordestoryInside,Call the destructor

conclusion

  • For a value type, such as Integer,

    • 1. This type of copy and move operations make memory copies.

    • The destory operation does not perform any operation

  • For a reference type, such as class,

    • 1. This type of copy does a reference count of +1,

    • Move copies Pointers without updating reference counts.

    • The destory operation will count the reference to -1

Generic functions pass in function analysis

These are all analyses of variables, so here comes the question

What if a generic function is passed a function?

The code looks like this. Is the m passed in the whole structure?

// What if a function is passed in? func makeIncrement() -> (Int) -> Int{ var runningTotal = 10 return { runningTotal += $0 return runningTotal } } func TestGenric <T>(_ value: T){} let m = makeIncrement() testGenric(m)Copy the code
  • Analyzing IR code
define i32 @main(i32 %0, i8** %1) #0 { entry: %2 = alloca %swift.function, align 8 %3 = bitcast i8** %1 to i8* ; S4main13makeIncrementS2icyF makeIncrement function called, returns a structure {address function call, Capture value memory address} % 4 = call swiftcc {i8 * % swift. The refcounted *} @ "$s4main13makeIncrementS2icyF ();" The address of the closure expression %5 = ExtractValue {i8*, %swift.refcounted*} %4, 0; The reference type %6 = ExtractValue {i8*, %swift.refcounted*} %4, 1; Store value in m variable address; Return %5 to the swift. Function * structure (%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 ; Put the value in the variable f, ** Getelementptr inbounds (% swif.function, counted count of store % swif.refcounted * %6, % swif.refcounted ** getelementptr inbounds (%swift. %swift.function* @"$s4main1myS2icvp", i32 0, i32 1), align 8 ; Function * %2 to i8* call void @llvm.lifetime.start.p0i8(i64 16, i8* %7); %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 ; The method was passed the returned closure expression as a parameter, so retainCount+ 1% 10 = Call %swift.refcounted* @swift_retain(% swif.refcounted * returned %9) #2; Creates an object, Counted <{%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 ; Refcounted * %11 = bitcast %swift. Refcounted * %11 to <{%swift. Refcounted * %11 counted, {%swift. %swift.function }>* ; Return %swift.function (the final result is to <{%swift.refcounted, {%swift.function}> count ==> counted) %13 = getelementptr inbounds <{%swift.refcounted, %swift.function }>, <{ %swift.refcounted, %swift.function }>* %12, i32 0, i32 1 ; Function > %. Fn = getelementptr inbounds % swif. function, % swif. function* %13, i32 0, i32 0; Store i8* %8, i8** %.fn, ** counted i8** %.fn (in %swift.function of the created data structure <{%swift.refcounted, %swift.function}>) 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 ; Store i8* bitcast (void (%TSi*, %TSi*, counted %swift.refcounted) %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 * where %2 = %swift. Function %14 = bitcast %swift. Function * %2 to %swift. Opaque *; SS2icMD ==> demangling cache variable for type metadata for (swift.int) -> swift. Int %swift.type* @__swift_instantiateConcreteTypeFromMangledName({ i32, i32 }* @"$sS2icMD") #9 ; Call swiftcc void @"$s4main10testGenricyyxlF"(% swif.opaque * noalias nocapture %14, %swift.type* %15) ......Copy the code

The underlying structure of a generic function passed in

Copy the structure of the above logic

// What if a function is passed in? 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){let PTR = UnsafeMutablePointer<T>. Allocate (capacity: allocate) 1) ptr.initialize(to: Function * %13 = getelementptr inbounds <{%swift. Refcounted, %swift. Function}>, {%swift. <{ %swift.refcounted, %swift.function }>* %12, i32 0, I32 1 - Call method %14 -> %2 %14 = bitcast % swif. function* %2 to % swif.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. The function. The captureValue} print (CTX) pointee) value) / / capture value is 10} / / m is stored in a structure: {i8*, swift type *} let m = makeIncrement() testGenric(m) <! Print the result --> 10Copy the code

Therefore, when passing a generic function, there will be a layer of wrapping, which means that the function value and type in M will not be directly passed to testGenric. Instead, there will be a layer of abstraction, which aims to solve the problems in the process of passing different types

conclusion

  • Generics are primarily used to address code abstraction and improve code reuse

  • If a generic complies with a protocol, then the specific type is required to comply with a protocol when used

  • When defining a protocol, you can use an association type to give a placeholder name to the type used in the protocol

  • The WHERE statement is primarily used to indicate conditions that generics need to satisfy, namely requirements that restrict formal parameters

  • Generic types use VWT for memory management (that is, to distinguish between types by VWT), which is generated by the compiler and stores the size, alignment, and basic memory operations for that type

    • 1. When a memory operation is performed on a generic type (e.g., memory copy), the basic memory operation in the VWT corresponding to the generic type is eventually called
    • 2. Different generic types have different VWT
  • Having specific functionality when you want generics to specify types can be done with Extension

  • For generic functions, there are several cases:

    • The incoming is aValue types, such as Integer,
      • 1. This type of copy and move operations make memory copies.

      • The destory operation does not perform any operation

    • The incoming is aReference types, such as a class,
      • 1. This type of copy does a reference count of +1,

      • Move copies Pointers without updating reference counts.

      • The destory operation will count the reference to -1

    • ifGeneric functionThe incoming is afunctionIn the process of passing, there will be a layer of wrapping, in short, is not directly the functionFunction value + typeFor generic functions, instead, a layer of abstraction is made, mainly forSolve different types of delivery problems