I'm trying to understand how to find protocol method's implementation.
I know that Swift uses an Existential Container for fixed-size storage in Stack memory which manages how to describe an instance of a struct in memory. and it has a Value Witness Table (VWT) and Protocol Witness Table (PWT)
VWTs know how to manage real value in instance of struct (their lifecycle) and PWTs know the implementation of protocol's method.
But I want know the relation between the instance of a struct and the "existential container".
Does an instance of struct have a pointer which refers to an existential container?
How does an instance of a struct know its existential container?
Preface: I don't know how much background knowledge you have, so I might over-explain to make sure my answer is clear.
Also, I'm doing this to the best of my ability, off by memory. I might mix up some details, but hopefully this answer could at least point you towards further reading.
See also:
In Swift, protocols can be used "as a type", or as a generic constraint. The latter case looks like so:
protocol SomeProtocol {}
struct SomeConformerSmall: SomeProtocol {
// No ivars
}
struct SomeConformerBig: SomeProtocol {
let a, b, c, d, e, f, g: Int // Lots of ivars
}
func fooUsingGenerics<T: SomeProtocol>(_: T) {}
let smallObject = SomeConformerSmall()
let bigObject = SomeConformerBig()
fooUsingGenerics(smallObject)
fooUsingGenerics(bigObject)
The protocol is used as a constraint for type-checking at compile time, but nothing particularly special happens at runtime (for the most part). Most of the time, the compiler will produced monomorphized variants of the foo function, as if you had defined fooUsingGenerics(_: SomeConformerSmall) or fooUsingGenerics(_: SomeConformerBig) to begin with.
When a protocol is "used like a type", it would look like this:
func fooUsingProtcolExistential(_: SomeProtocol) {}
fooUsingGenerics(smallObject)
fooUsingGenerics(bigObject)
As you see, this function can be called using both smallObject and bigObject. The problem is that these two objects have different sizes. This is a problem: how will the compiler know how much stack space is necessary to allocate for the arguments of this function, if the arguments can be different sizes? It must do something to help fooUsingProtcolExistential accommodate that.
Existential containers are the solution. When you pass a value where a protocol type is expected, the Swift compiler will generate code that automagically boxes that value into an "existential container" for you. As currently defined, an existential container is 4 words in size:
When the value being stored is less than 3 words in size (e.g. SomeConformerSmall), the value is packed directly inline into that 3 word buffer. If the value is more than 3 words in size (e.g. SomeConformerSmall), a ARC-managed box is allocated on the heap, and the value is copied into there. A pointer to this box is then copied into the first word of the existential container (the last 2 words are unused, IIRC).
This introduces a new issue: suppose that fooUsingProtcolExistential wanted to forward along its parameter to another function. How should it pass the EC? fooUsingProtcolExistential doesn't know whether the EC contains a value-inline (in which case, passing the EC just entails copying its 4 words of memory), or heap-allocated (in which case, passing the EC also requires an ARC retain on that heap-allocated buffer).
To remedy this, the Protocol Witness Table contains a pointer to a Value Witness Table (VWT). Each VWT defines the a standard set of function pointers, that define how the EC can be allocated, copied, deleted, etc. Whenever a protocol existential needs to be manipulated in someway, the VWT defines exactly how to do so.
So now we have a constant-size container (which solves our heterogeneously-sized parameter passing problem), and a way to move the container around. What can we actually do with it?
Well at a minimum, values of this protocol type must at least define the required members (initializers, properties (stored or computed), functions and subscripts) that the protocol defines.
But each conforming type might implement these members in a different way. E.g. some struct might satisfy a method requirement by defining the method directly, but another class might satisfy it by inheriting the method from a superclass. Some might implement a property as a stored property, others as a computed property, etc.
Handling these incompatibilities is the primary purpose of the Protocol Witness Table. There's one of these tables per protocol conformance (e.g. one for SomeConformerSmall and one for SomeConformerBig). They contain a set of function pointers with point to the implementations of the protocols' requirements. While the pointed-to functions might be in different places, the PWT's layout is consistent for the protocol is conforms to. As a result, fooUsingProtcolExistential is able to look at the PWT of an EC, and use it to find the implementation of a protocol method, and call it.
So in short: